読者です 読者をやめる 読者になる 読者になる

ぶらり途中 Power Set の旅

Power Set

久々に少しづつ刻んでいったので思考の変遷を辿る.

まず,142byte.羃集合なので,脳直でそのままビットを調べて作っていた初版.

main=interact$f.p.read
f x='{':foldr1(&)x++"}"
a&b=a++", "++b
p n="0":[f[p(n-1)!!x|x<-[0..n],odd$i(`div`2)a!!x]|a<-[1..i(2^)0!!n-1]]
i=iterate

134byte.142byteを少し弄っただけ.

main=interact$f.p.read
f x='{':foldr1(\a b->a++", "++b)x++"}"
p n="0":[f[p(n-1)!!a|a<-[0..n],odd$div x$2^a]|x<-[1..iterate(2^)0!!n-1]]

128byte.入力の1,2,4のみにターゲットを合わせてiterateを消した.あまり美しくない.Haskell golfの場合,美しいと思えないのはまだ縮むシグナルかな.

main=interact$f.p.read
f x='{':foldr1(\a b->a++", "++b)x++"}"
p(n+1)="0":[f[p n!!a|a<-[0..n],odd$div x$2^a]|x<-[1..n*5^div n 2]]

120byte.転換点その1.foldlで羃集合を構成していくように変更.

main=interact$f.(iterate(map f.foldl(#)[[]])[]!!).read
x#a=x++map(++[a])x
f[]="0"
f x='{':foldr1(\a b->a++", "++b)x++"}"

117byte.120byteからfoldr1の中を少し弄っただけ.

main=interact$f.(iterate(map f.foldl(#)[[]])[]!!).read
x#a=x++map(++[a])x
f[]="0"
f x='{':foldr1((++).(++", "))x++"}"

97byte.転換点その2.fを1箇所にまとめるため,1回余分にiterateしてlastを取る.ついでに冪集合の生成だけでなく文字列化までfoldl時に行う.

main=interact$last.(iterate(map(('{':).(++"}")).foldl(#)["0"])[]!!).read
x#a=x++a:map(++", "++a)x

95byte.最終版.97byte版から'{'だけはfoldlの中でくっつけるようにしてmapを軽量化.

main=interact$last.(iterate(map(++"}").foldl(#)["{0"])[]!!).read
x#a=x++('{':a):map(++", "++a)x

転換点2つがgolf上クリティカルだった点.やっぱこういう問題はHaskellの美しさがぱない.