esolangを書く、の2
この記事は、TSG Advent Calendar 2016 - Adventar の14日目のために公開されました。
先日のやつ esolangを書く - 忖度 の続きです。
今回はどちらも素手で書くのが困難な言語なので、pythonでソースコードを出力させます。
先にネタバレしておくと、WhiteSpaceはアセンブリ言語っぽくて、ferNANDoは論理回路っぽいなと思いました。計算機システムとハードウェア構成法ですね。
WhiteSpace
これすごい好き(与えられたお題を様々なesolangで解くハッカソンらしい) pic.twitter.com/HMYHIiZjUl
— Fukumu Tsutsumi (@levelfour_) November 26, 2016
これです。駒場祭に展示させたかったので当日に書きました。
ソースコードは
です。
どちらも読みにくくて仕方がないので、書くために使ったpythonのソースコードを載せます。
#coding: utf-8 from Tkinter import Tk def i2w(x): res = "" if x>=0: res += " " else: res += "\t" x *= -1 ad = '' while x>0: ad = ("\t" if x%2==1 else " ") + ad x /= 2 res += " " + ad return res #http://www.kembo.org/whitespace/tutorial.html #http://koturn.hatenablog.com/entry/2015/08/10/000000 def push(x): return " " + i2w(x) + "\n" geti = "\t\n\t\t" getc = "\t\n\t " outi ="\t\n \t" endp = "\n\n\n" heap_s = "\t\t " heap_l = "\t\t\t" dup = " \n " add = "\t " sub = "\t \t" mul = "\t \n" mod = "\t \t\t" div = "\t \t " swap = " \n\t" def mark(x): return "\n " + x + "\n" def jmpng(x): #負だったら飛ぶやつ return "\n\t\t" + x + "\n" def load(x): return push(x) + heap_l def store(x): return push(x) + swap + heap_s r = Tk() r.clipboard_clear() #s = push(0) + geti + push(0) + heap_l + outi + endp s = ( push(100) + store(1) + #カウンタをheap(1)に push(0) + store(2) + #答えをheap(2)に mark("\t \t ") + #ラベル load(2) + push(2) + mul + #ansを二倍 push(0) + getc + load(0) + #入力をpush push(ord('0')) + sub + add + store(2) + #getcの結果を足してstore load(1) + #カウンタロード push(1) + sub + dup + store(1) + #デクリメントしてstore. push(0) + swap + sub + jmpng("\t \t ") + #正だったら飛ぶ load(2) + outi + #出力 endp ) r.clipboard_append(s) #print getc + getc + endp[:-1]
中ほどに載っているリファレンスとインタプリタを参考にしました。
whitespaceはいちおうスタック型言語ですが、スタックに対するランダムアクセスがあったり、heap領域が使えたりするので、ふつうの言語と遜色なく書けます。実質アセンブリみたいなもんです。
今回は、IdeoeのWhiteSpaceインタプリタの内部実装がHaskellだったので、整数の大きさに制限がないです。
そのため、アルゴリズムは
i = 100 ans = 0 while i>0: ans = ans * 2 + getc() - 48 i -- puti(ans)
みたいな感じでしました。実質アセンブリでしたね。(for文のとこ、先にロードしてデクリメントしてから比較ジャンプするとことか)
ferNANDo
ferNANDo - Esolang :: 仕様
FerNANDo – Try it online! :: インタプリタ
Brainf*ckやBefungeやWhiteSpaceは有名ですが、これは初耳でした。その他の言語が高性能に思えるくらい仕様がシンプルでした。
仕様の簡単な説明
変数名は何でも可(ただし?は特別)。最初は全て0で初期化されている。
命令は3種類のみ。
nand
a b c
と書くと、a に b NAND cの結果が代入される。
a b
と書くと、a に a NAND bの結果が代入される。
ループ
hogehuga
と、1行に1変数だけ書くと、上に全く同じ行がなければ特に何もせず、上に同様に hogehuga とだけ書かれた行があった場合、hogehuga が1なら上の行にジャンプし、0ならそのまま次の行に移る。
解法
見ての通り全変数が1bitのみで演算がNANDしかない言語です。
こんなんでプログラミングできるんかいなと思う人がいるかもしれませんが、いちおうNANDがあればANDやORやNOTができるので論理演算には事欠かず、またループも可能だし入出力もできるので問題を解けるポテンシャルがあるように思えます。(実際にwikiのサンプルコードの中にルール30をシュミレートするプログラムが書いてありました。ルール110ができればチューリング完全なので、多分ferNANDoもチューリング完全なのではないでしょうか)*1
で、実際に解いてみました。
#coding: utf-8 from Tkinter import Tk init = """ 0 0 0 0 0 0 1 1 1 """ var_num = 0 def getv(): #一桁変数は避ける。 global var_num var_num += 1 return 'v' + str(var_num) def getvs(x): if x==1: return getv() else: return [getv() for i in xrange(x)] #一時変数名の衝突を防ぐためにdで深さを入れる。 #あと、同じ名前が入ってきても大丈夫なように設計しましょう... #具体的には、sに代入したあとに、aやbを参照すると壊れてる可能性がある。 def nand(s,a,b): # s = a nand b return "%s %s %s\n" % (s,a,b) def one(a): #aに1を代入 return nand(a,a,'0') def not_(s,a): #s = !a return nand(s,a,a) def zero(a): #aに1を代入 return one(a) + not_(a,a) def and_(s,a,b): # s = a & b return nand(s,a,b) + not_(s,s) def mov(s,a): # s := a return and_(s,a,a) def or_(s,a,b): # s = a | b return not_(a,a) + not_(b,b) + nand(s,a,b) def xor(s,a,b): # s = a ^ b ta,tb,mb = getvs(3) return mov(mb,b) + not_(ta,a) + not_(tb,b) + nand(s,a,tb) + nand(tb,ta,mb) + nand(s,s,tb) def ha(c,s,a,b): #ハーフアダー。 #s = a ^ b #c = a & b ma, mb = getvs(2) return mov(ma,a) + mov(mb,b) + xor(s,ma,mb) + and_(c,ma,mb) def fa(c,s,p,q,r): #フルアダー。 #s = a ^ b #c = a & b mp, mq, mr, tp= getvs(4) return ( mov(mp,p) + mov(mq,q) + mov(mr,r) + ha(c,s,mp,mq) + ha(tp,s,s,mr) + or_(c,tp,c) ) def inc(ds): #dsで表される配列をインクリメントする。 tp,tq = getvs(2) res = one(tp) for s in ds: res += and_(tq,tp,s) res += xor(s,tp,s) res += mov(tp,tq) return res def neq(r,cs,ds): #csとdsを比べた結果をrに格納する。等しいなら0。 res = zero(r) tt = getv() for p,q in zip(cs,ds): res += xor(tt,p,q) res += or_(r,r,tt) return res def add(c,cs,ds): #cs += ds, cには桁上がりが入る nc,ns = getvs(2) res = zero(nc) for p,q in zip(cs,ds): res += fa(nc,ns,nc,p,q) res += mov(p,ns) res += mov(c,nc) return res def movv(cs,ds): #cs := ds res = "" for t,d in zip(cs,ds): res += mov(t,d) return res def sub(c,cs,ds): #cs += ds, cには負数でないかどうかが入る td = getvs(len(ds)) res = movv(td,ds) for t in td: res += not_(t,t) res += inc(td) res += add(c,cs,td) return res def geq(r,ds,cs): #ds>=csか td = getvs(len(ds)) return movv(td,ds) + sub(r,td,cs) #+ "0 0 1 1 %s %s %s %s" % (td[3],td[2],td[1],td[0]) + "\n" def lls(ds): #論理左シフト res = "" for i in range(0,len(ds)-1)[::-1]: res += mov(ds[i+1],ds[i]) res += mov(ds[0],'0') return res def andv(ds,a): #ds = map(lambda x: x & a,ds) res = "" for d in ds: res += and_(d,d,a) return res def nibai(dss): #4bitリトルインディアン(10進)のものを各桁ごとに上から2倍していく ls = len(dss) res = "" tp,tq = getvs(2) tds = getvs(4) for i in range(0,ls-1)[::-1]: ds = dss[i] res += geq(tp,ds,['1','0','1','0']) #res += movv(tds,['0','1','0','1']) #res += andv(tds,tp) #res += sub(tq,ds,tds) res += sub(tq,ds,[tp,'0',tp,'0']) res += add(tq,dss[i+1],[tp,'0','0','0']) res += lls(ds) return res r = Tk() r.clipboard_clear() cnt = ['c' + str(i) for i in xrange(10)] ans = [['a' + str(i) + ',' + str(j) for j in xrange(4)] for i in xrange(33)] s = ( init + movv(cnt,['0'] * 10) + "" ) for ds in ans: s += movv(ds,['0'] * 4) tp = getv() s += ( 'x' + "\n" + nibai(ans) + 'x x x x x x x x b' + "\n" + add(tp,ans[0],['b','0','0','0']) + inc(cnt) + #"0 0 1 1 %s %s %s %s" % (cnt[3],cnt[2],cnt[1],cnt[0]) + "\n" + #geq(tp,cnt,['1','1','0','0']) + #"0 0 1 1 0 0 0 %s" % tp + "\n" + neq('x',cnt,map(chr,map(ord,'0001100100'[::-1]))) + #neq('x',cnt,map(chr,map(ord,'0000000110'[::-1]))) + 'x' + "\n" + "" ) for ds in ans[::-1]: s += ("0 0 1 1 %s %s %s %s" % (ds[3],ds[2],ds[1],ds[0])) + "\n" print len(s) r.clipboard_append(s)
ハーフアダーとかフルアダーとかインクリメンタとかアダーとかがあるのでもう論理回路ですね。
おおまかなアルゴリズムとしては、
counter = '0000000000' loop ans <- ans * 2 x x x x x x x b ans <- ans + 1 loop <- counter < '0001100100' loop print ans
みたいな感じですかね。
ansを二倍する部分は、そもそも4bitのものを35桁分持ってないといけないので、ループを回すことができず、各桁について、
c <- ans[i] >= '0101' ans[i+1] += '000c' ans[i] -= '0c0c' ans[i] <<= 1
みたいなことを35回書いてどうにかしました。
で、これで解けるのですが、これで出力するとコードの長さが約35万文字になりました。
今回は提出システムを@hakatashiが作ってくれたのですが、システムの都合上1万文字に抑えてくれと言われたので、ここからさらに論理圧縮をしてコード長を1/35にすることになりました。
最終的には、
#coding: utf-8 from Tkinter import Tk init = """ 0 0 0 0 0 0 1 1 1 """ def nand(s,a,b): # s = a nand b if s==a: #10242 -> 10162 return "%s %s\n" % (s,b) elif s==b: return "%s %s\n" % (s,a) return "%s %s %s\n" % (s,a,b) def one(a): #aに1を代入 return nand(a,a,'0') def not_(s,a): #s = !a if s==a: #174122 -> 144684 return "%s %s\n" % (s,'1') else: return nand(s,a,a) def zero(a): #aに0を代入 #return one(a) + not_(a,a) return "%s 1 1\n" % a #144684 -> 144098 def and_(s,a,b): # s = a & b return nand(s,a,b) + not_(s,s) def mov(s,a): # s := a return and_(s,a,a) def or_(s,a,b): # s = a | b return not_(a,a) + not_(b,b) + nand(s,a,b) def xor(s,a,b): # s = a ^ b tc,td,te = ('A','B','C') if a==s: te = s #10162 -> 9798 return ( nand(tc,a,b) + nand(td,a,tc) + nand(te,b,tc) + nand(s,td,te) #144098 -> 119922 ) def inc(ds): #dsで表される配列をインクリメントする。 tp,tq = ('D','E') res = one(tp) for s in ds: res += and_(tq,tp,s) res += xor(s,tp,s) res += mov(tp,tq) return res def neq(r,cs,ds): #csとdsを比べた結果をrに格納する。等しいなら0。 res = zero(r) tt = 'F' for p,q in zip(cs,ds): res += xor(tt,p,q) res += or_(r,r,tt) return res def add0or5(a,b,c,r): # cba += r0r をする tp,ic,ib = ('G','H','I') #return add(tp,[a,b,c],[r,'0',r]) res = "" res += and_(ib,a,r) res += and_(ic,ib,b) res += xor(ic,ic,r) res += xor(c,c,ic) res += xor(b,b,ib) res += xor(a,a,r) return res def sub5(r,a,b,c,d): # dcba -= 0101 をする。で、rに、dcba += 1011の繰り上がりの結果が入る ib,ic,id,ir = ('J','K','L','M') #38372 -> 15662 res = "" res += not_(a,a) res += not_(ic,b) res += nand(ic,ic,a) res += nand(id,ic,c) res += not_(d,d) res += nand(ir,id,d) # 10498 -> 10242 res += xor(b,b,a) res += xor(c,c,ic) res += xor(d,d,id) res += not_(r,ir) return res def mo5sub5(r,ds): #if ds>=5 then {ds -= 5; r=1;} else {r=0;} tq = 'N' res = "" res += sub5(r,ds[0],ds[1],ds[2],ds[3]) res += add0or5(ds[0],ds[1],ds[2],r) #res += zero(ds[3]) #シフトするので不要。 11935 -> 11711 return res def lls(ds): #論理左シフト res = "" for i in range(0,len(ds)-1)[::-1]: res += mov(ds[i+1],ds[i]) return res def nibai(dss): #4bitリトルインディアン(10進)のものを各桁ごとに上から2倍していく ls = len(dss) res = "" tp,tq = ('O','P') for i in range(0,ls-1)[::-1]: ds = dss[i] res += mo5sub5(tp,ds) res += not_(dss[i+1][0],tp) #119922 -> 90322 #print ds, res += lls(ds) #print ds return res #変数名をAからRまで割り振ることにより、 #14807 -> 11935 var_num = 0 def getv(): global var_num var_num += 1 res = "" nv = var_num d = 127-33 ok = True while nv>0: nc = nv%d+33 res += chr(nc) nv /= d if len(res)<=1: c = res[0] if c=='0' or c=='1' or c=='?' or (ord('A') <= ord(c) and ord(c) <= ord('R')): #11511 -> 10704 return getv() return res def getvs(x): if x==1: return getv() else: return [getv() for i in xrange(x)] r = Tk() r.clipboard_clear() import sys ketan = 33 if len(sys.argv)>=2: ketan = 3 ans = [[getv() for j in xrange(4)] for i in xrange(ketan)] cnt = [getv() for i in xrange(7)] #38372 -> 38030 s = ( init + "" ) s += ( 'Q' + "\n" + nibai(ans) + 'Q Q Q Q Q Q Q Q R' + "\n" + mov(ans[0][0],'R') + #15662 -> 14807 inc(cnt) + neq('Q',cnt,map(chr,map(ord,'1100100'[::-1]))) + 'Q' + "\n" + "" ) for ds in ans[::-1]: s += ("0 0 1 1 %s %s %s %s" % (ds[3],ds[2],ds[1],ds[0])) + "\n" print len(s) r.clipboard_append(s)
となりました。
改善点としては、
- 出来る限り1文字変数名が多く使われるようにする
- 加算、減算の数値がほぼ一定(0か5)なのでアダーを使わず回路を直に書き込む
- nandやxorなどで同じ記号を使っているならその分短く書くことができる
とかですかね。論理圧縮すると回路ががりがり縮んでいきました。
最終的に、9798文字になったので、晴れてACを貰うことができました。
感想
BFやBefungeやWhiteSpaceのいかに書きやすいことか!!
