任意の文字列を出力するなるべく短いBrainf*ckの生成 [JavaScript]

作り終えて暫くするとコード見返してもわからなくなるので備忘録としてここに残すことにした
初投稿なのでかなり見にくいと思います
申し訳ないです…

先にこちら実物です https://mcbeeringi.github.io/amuse/bf.html

[21/01/20 14:31]追記
コードに不備があったので改良しました

[22/02/06 14:57]追記
作り直した!

#動機
Twitterで突然リプにBrainfckがやって来たので
なんとかしてBrainfckでスマートに秒で返せるようにしたかった

#設計
メモリは 255の次が0つまり8bit 書き込める数は無限 とする
##アルゴリズム
当時(今も)自身が手書きする際のアルゴリズムをそのまま書き起こすことにした
(もちろん最善とは限らないです)
計算はcpuが頑張ってくれるのでいくらでも試行させられる素晴らしい

この手のコードを生成する↓

++[>++>---<<-]>+.--.

大体の流れ
　1.ASCIIで近い文字同士をグループにまとめる
　2.それぞれのグループで一番最初の文字になるべく近い数の最大公約数を求める
　3.最初のループ+端数調整→出力

変数は二つ
「近い文字同士」　……8bitなのでその半分未満→0~127
「なるべく近い数の最大公約数」　……探索でゴリ押す…?
この二つの数で長さが決定される

##ポインタの移動によるコスト
ループの後調整をしながら出力をする段階でももちろんポインタは移動する
これに直接影響を与えるのがグループの並び順
これをなんらかの方法で最適化することで最終的な文字数の削減が見込める

インデックス並び替えとでも呼ぼうか
この処理を1と2の間に挟む

具体的には
隣接するグループインデックスの組み合わせを頻度順に書き出して
頻度が高いものから結晶が成長するようなイメージで一列に繋げて
繋げられなかったグループ番号を付け足して
既存のグループインデックスをそれで置き換える
という流れ

見るからに大変
ここで一番苦労した

なおこれでは多数派のインデックスが優先されてしまい
他の少数派の登場回数が多数派を上回っていても無視されるので
おそらく最善ではない

#ひたすら書く
##グループにまとめる
最初にBfに出力させたい文字列 s を用意する
このあとこの文字列を生で使う予定もないのでここでは配列で置き換える

// s='Hello World!'

s=s.split('').map(x=>x.charCodeAt(0)).filter(x=>x<256);// ASCII以外は無視
console.log('raw',s);

// >> "raw", [72,101,108,108,111,32,87,111,114,108,100,33]

　
これを適当な閾値 md(max distance) を設けて0-1=255があることに注意しながらグループ分けする
全体的に変数の名前の付け方がひどいです申し訳ない

// md=10;

var ind=[0],	// それぞれの文字がどのグループに属しているかのindex
    clm=[[s[0]]],	// グループを二次元の配列に入れる (column 直訳で列)
                 	// 0グループの最初は一番最初の文字を入れておく
    tmp={};	// テンポラリ
s.slice(1).forEach((x,i)=>{i++;	// 最初の文字を切ってforEachで回す
	tmp.mini=-1;	// 最終的に一番近いグループインデックスをここに書く (minimum index)
	tmp.mind=Number(md)+1;	// その距離 これ未満のときにこれとtmp.miniを更新
	clm.forEach((y,j)=>{	// 各グループに対して
		tmp.last=y[y.length-1];	// そのグループの最後の値
		tmp.dist=Math.abs(tmp.last-x);	// との距離
		tmp.dist=Math.min(tmp.dist,256-tmp.dist);	//逆回りも考慮
		if(tmp.dist<tmp.mind){	// 距離が今までより短かったら更新
			tmp.mind=tmp.dist;
			tmp.mini=j;
		}
	});
	if(tmp.mini==-1){	// 属せるグループがない場合は新しいグループを作成
		ind[i]=clm.length;
		clm[ind[i]]=[x];
	}else{			// 属せるグループがある場合はそこに入れる
		ind[i]=tmp.mini;
		clm[ind[i]].push(x);
	}
});
console.log('index',ind);
console.log('data',clm);

// >> "index", [0,1,1,1,1,2,3,1,1,1,1,2]
// >> "data", [[72],[101,108,108,111,111,114,108,100],[32,33],[87]]

##インデックス並び替え
インデックス並び替えの処理を作る

と言ってもいきなりは辛いのでゴールの確認から
専用の関数 freq を作ってインデックスのみを投げて最適化してもらう

// 現状の確認
console.log('index',ind);
console.log('data',clm);

var freq_=freq(ind);	//　最適化したインデックス
ind=ind.map(x=>freq_.indexOf(x));	// 置換する
clm=freq_.map(x=>clm[x]);	// グループごと並び替える

//最適化後
console.log('index',ind);
console.log('data',clm);

//もう一度最適化をする意味がないことの検証
console.log(freq(ind));	// これは0,1,2…になるはず

肝心のfreq関数

もいきなりは辛いので形から
頻度順に並び替えた組を再び別の関数に投げる
ちなみに二桁以上のインデックスがある場合はうまく機能しないが
下手な閾値を設定しない限りそこまで大量のインデックスが来ることもないので
直しました

const freq=inp=>{
	var inpm=[...new Array(Math.max(...inp)+1).keys()];	// 0~インデックスの最大値の配列
	if(inpm.length<3){	//インデックスが十分に少ないときは無駄な操作になるのでそのまま返す
		console.log('freq skipped',inpm);
		return inpm;
	}

	// 全隣り合わせを列挙してゾロ目カットと並び順が逆なものは昇順に書き換え
	var arr=inp.map((x,i,c)=>{if(c[i+1])return[x,c[i+1]];})
			.filter(x=>x&&x[0]!=x[1]).map(x=>x[0]>x[1]?[x[1],x[0]]:x);

	// 頻度の計測 (海外のページ参考 元ページ見つかりませんでした…)
	var fq={};arr.forEach(x=>fq[x]=0);
	var s=arr.filter(x=>++fq[x]==1);
	s.sort((a,b)=>fq[b]-fq[a]);
	// s に頻度が高かった組み合わせから重複なく入っている

	// 頻度をもとに繋げる
	var tmp,out=[];
	while(true){
		tmp=joinPair(s);	// return [ 繋げた結果, 繋げられなかった組 ];
					//(1組だけ渡したときはつなげられたものとして返す)
		out=out.concat(tmp[0]);
		s=tmp[1];	// 繋げられなかったものはもう一度試す
		if(tmp[1].length==0)break;
	}

	// 途中で欠けたインデックスを補完する	
	out=out.concat(inpm.filter(x=>out.indexOf(x)==-1));
	console.log('freq',out);
	return out;
}

渡された組を繋げる関数
joinPairを作る
何をもって成功とするかが難しい

const joinPair=x=>{
	var indm=x.reduce((a,y)=>Math.max(y[0],y[1],a),0); 	// 最大値
	console.log('joinPair',x,indm);

 	// 一次元の座標x=indmに原点を作ってそこに最頻の組を置く
	var ind=new Array(indm+1).fill(null),  	// どの位置にどのインデックスが入ったか
	s=new Array(indm).concat(x[0].split(''));

 	// すでに配置した最頻は消去
	x.shift();
	ind[s[indm]]=indm;  	// 最初の組の位置を記録
	ind[s[indm+1]]=indm+1;

	// 組同士を繋げる
	var flag=true;
	while(flag){
		flag=false;
		x=x.map((e,i)=>{
			if(ind[e[0]]&&!ind[e[1]]){
				if(!(s[ind[e[0]]+1]+1)){s[ind[e[0]]+1]=e[1];ind[e[1]]=ind[e[0]]+1;}//ok
				else if(!(s[ind[e[0]]-1]+1)){s[ind[e[0]]-1]=e[1];ind[e[1]]=ind[e[0]]-1;}//ok
			}//doom
			else if(!ind[e[0]]&&ind[e[1]]){
				if(!(s[ind[e[1]]+1]+1)){s[ind[e[1]]+1]=e[0];ind[e[0]]=ind[e[1]]+1;}//ok
				else if(!(s[ind[e[1]]-1]+1)){s[ind[e[1]]-1]=e[0];ind[e[0]]=ind[e[1]]-1;}//ok
			}//doom
			else if(!ind[e[0]]&&!ind[e[1]])return e;//pass
			//else if(ind[e[0]]&&ind[e[1]])//doom
			flag=true;console.log(e,s,ind);
		});
		// 繋げられなかった組も再配置できるか試す
		x=x.filter(y=>y);
		console.log(x);
	}
	// nullの除去 +1で0抜け回避
	return [s.filter(e=>e+1),x];
}

以上3つを繋げるとこんなかんじ
ここでの例はHello World!ではないです(短すぎる)
長いほど威力を発揮します

const freq=inp=>{
	const joinPair=x=>{
		var indm=x.reduce((a,y)=>Math.max(y[0],y[1],a),0);
		console.log('joinPair',x,indm);
		var ind=new Array(indm+1).fill(null),s=new Array(indm).concat(x[0]);
		x.shift();ind[s[indm]]=indm;ind[s[indm+1]]=indm+1;
		var flag=true;
		while(flag){
			flag=false;
			x=x.map((e,i)=>{
				if(ind[e[0]]&&!ind[e[1]]){
					if(!(s[ind[e[0]]+1]+1)){s[ind[e[0]]+1]=e[1];ind[e[1]]=ind[e[0]]+1;}//ok
					else if(!(s[ind[e[0]]-1]+1)){s[ind[e[0]]-1]=e[1];ind[e[1]]=ind[e[0]]-1;}//ok
				}//doom
				else if(!ind[e[0]]&&ind[e[1]]){
					if(!(s[ind[e[1]]+1]+1)){s[ind[e[1]]+1]=e[0];ind[e[0]]=ind[e[1]]+1;}//ok
					else if(!(s[ind[e[1]]-1]+1)){s[ind[e[1]]-1]=e[0];ind[e[0]]=ind[e[1]]-1;}//ok
				}//doom
				else if(!ind[e[0]]&&!ind[e[1]])return e;//pass
				//else if(ind[e[0]]&&ind[e[1]])//doom
				flag=true;console.log(e,s,ind);
			});
			x=x.filter(y=>y);console.log(x);
		}
		return [s.filter(e=>e+1),x];
	}
	var inpm=[...new Array(Math.max(...inp)+1).keys()];
	if(inpm.length<3){console.log('freq skipped',inpm);return inpm;}
	var arr=inp.map((x,i,c)=>{if(c[i+1])return[x,c[i+1]];})
		.filter(x=>x&&x[0]!=x[1]).map(x=>x[0]>x[1]?[x[1],x[0]]:x);
	//freq sort
	var fq={};arr.forEach(x=>fq[x]=0);
	var s=arr.filter(x=>++fq[x]==1);
	s.sort((a,b)=>fq[b]-fq[a]);
	//arr
	var tmp,out=[];
	while(true){
		tmp=joinPair(s);out=out.concat(tmp[0]);s=tmp[1];
		if(tmp[1].length==0)break;
	}
	out=out.concat(inpm.filter(x=>out.indexOf(x)==-1));console.log('freq',out);
	return out;
}

console.log('index',ind);console.log('data',clm);
var freq_=freq(ind);ind=ind.map(x=>freq_.indexOf(x));clm=freq_.map(x=>clm[x]);
console.log('index',ind);console.log('data',clm);console.log('test',freq(ind));


// >> "index", [0,1,1,1,1,1,0,2,1,1,0,3,3,0,1,0,0,4,3,2,0,1,0,3,5]
// >> "data", [[99,101,103,105,100,101,105,100],[111,110,115,111,108,108,111,110,110],[46,44],[40,39,39,41],[120],[59]]
// >> "joinPair", [[0,1],[0,3],[0,2],[1,2],[0,4],[3,4],[2,3],[3,5]], 5
// >> [0,3], [null,null,null,null,3,0,1], [5,6,null,4,null,null]
// >> [0,2], [null,null,null,null,3,0,1], [5,6,null,4,null,null]
// >> [1,2], [null,null,null,null,3,0,1,2], [5,6,7,4,null,null]
// >> [0,4], [null,null,null,null,3,0,1,2], [5,6,7,4,null,null]
// >> [3,4], [null,null,null,4,3,0,1,2], [5,6,7,4,3,null]
// >> [2,3], [null,null,null,4,3,0,1,2], [5,6,7,4,3,null]
// >> [3,5], [null,null,null,4,3,0,1,2], [5,6,7,4,3,null]
// >> []
// >> []
// >> "freq", [4,3,0,1,2,5]
// >> "index", [2,3,3,3,3,3,2,4,3,3,2,1,1,2,3,2,2,0,1,4,2,3,2,1,5]
// >> "data", [[120],[40,39,39,41],[99,101,103,105,100,101,105,100],[111,110,115,111,108,108,111,110,110],[46,44],[59]]
// >> "test", [0,1,2,3,4,5]

やっとインデックス並べ替えができました
慰労困憊
結晶が育つみたいで綺麗ですね()

##最大公約数なのか…?

各グループの最初の数を集めて

tmp=clm.map(x=>x[0]);

これでうまい具合にループで作るのでした

ここで問題
Q.
　0~255までの数A,B,C,D…があって
　ax+a'=A
　bx+b'=B
　cx+c'=C
　dx+d'=D
　…
　のとき
　x+a+b+c+d+…+|a'|+|b'|+|c'|+|d'|+…が最小になるxを求めよ。

A.
　知るか!
　とりあえず4あたりから√256まで探索するぞ!

→探索します!!!

// jsのroundが特殊であることと今回必要なのは5捨6入なので用意する
const round=x=>-Math.sign(x)*Math.round(-Math.abs(x)),
slm=arr=>{	// (search loop minimum)
	var m=Number.POSITIVE_INFINITY,s,tmp;
	for(var i=4;i<=16;i++){
		tmp=arr.map(x=>Math.abs(x>127?256-x:x))	// 逆回り
		       .map(x=>round(x/i)+x%i)
		       .reduce((a,b)=>a+b)+i;	// 合計
		if(tmp<m){m=tmp;s=i;}	//更新
		console.log(i,tmp);
	}
	console.log('slm',s);
	return s;
};

// >> 4, 81
// >> 5, 69
// >> 6, 64
// >> 7, 60
// >> 8, 57
// >> 9, 55
// >> 10, 51
// >> 11, 66
// >> 12, 52
// >> 13, 68
// >> 14, 46
// >> 15, 72
// >> 16, 53
// >> "slm", 14

どうやらHello World!の場合はx=14が最適のようです
この結果を使ってグループの先頭に端数を除いた値を追加しておきます

md=slm(tmp);
tmp=tmp.map((x,i)=>{
	var r=round((x>127?x-256:x)/md);
	clm[i].unshift(r<0?256+r*md:r*md);
	return r;
});
console.log('boot',tmp);	// 端数
// >> "boot", [5,7,2,6]

##ループ+端数→出力

ラストスパート
計算結果をBrainf*ckに落としていきます

s='+'.repeat(md)+'[';	// さっきのx=14
tmp.forEach(x=>s+='>'+(x>0?'+':'-').repeat(Math.abs(x)));	// x*__
s+='<'.repeat(tmp.length)+'-]>';
ind.forEach((x,i)=>{
	var p=x-(ind[i-1]||0),to=clm[x][1]-clm[x][0];clm[x].shift();
	// 目的のグループまでポインタを移動
	s+=(p>0?'>':'<').repeat(Math.abs(p));
	// 逆回り注意してメモリに書く
	p=Math.abs(to);s+=(to>0^p>128?'+':'-').repeat(p>128?256-p:p)+'.';
	console.log(i,x,s);console.log(clm);
});
console.log('result:',s.length,s);

// >> 0, 0, "++++++++++++++[>+++++>+++++++>++>++++++<<<<-]>++."
// >> [[72],[98,101,108,108,111,111,114,108,100],[28,32,33],[84,87]]
// >> 1, 1, "++++++++++++++[>+++++>+++++++>++>++++++<<<<-]>++.>+++."
// >> [[72],[101,108,108,111,111,114,108,100],[28,32,33],[84,87]]
// >> 中略
// >> 10, 1, "++++++++++++++[>+++++>+++++++>++>++++++<<<<-]>++.>+++.+++++++..+++.>++++.>+++.<<.+++.------.--------."
// >> [[72],[100],[32,33],[87]]
// >> 11, 2, "++++++++++++++[>+++++>+++++++>++>++++++<<<<-]>++.>+++.+++++++..+++.>++++.>+++.<<.+++.------.--------.>+."
// >> [[72],[100],[33],[87]]

// >> "result:", 104, "++++++++++++++[>+++++>+++++++>++>++++++<<<<-]>++.>+++.+++++++..+++.>++++.>+++.<<.+++.------.--------.>+."

完成です!
Hello World!が104字で出来ました

#まとめ
私が探した限りHello World!の最小は105字までしか見つからなかったので
104字が出て来た瞬間はとても嬉しかったです

コードまみれ & とても長い記事になっちゃいました
記事書くの向いてないのがよくわかりました()
最後まで読んでくださりありがとうございます