Prologにハマっています。今日も「どう書く」の過去問から。
Prologでビットマップイメージを扱う。さてどうしたものか。
結局のところ。Prolog界に足を踏み入れたばかりの初級者では想像もつきませんでした。なので、ビット列をそのまま0と1のリストにして扱ってみました。
今回のコードを書いていて、面白いと感じたのが16進数の文字列(文字コードのリスト)とビット列(0と1からなるリスト)の変換です。
hexbin
という述語を用意したのですが、後述のコードを見てもらうとわかるとおり、16進数の文字(文字コード)とビット列が一対一で対応しています。と、いうことは。第1引数が決まると第2引数が決まり、また第2引数が決まれば第1引数が決まる、という関係になっています。
これを利用すると、16進数→ビット列という変換と、ビット列→16進数という変換のどちらもがhexbin
でできてしまうということです。
実例。
?- hexbin("5b8", B), writeln(B). [0,1,0,1,1,0,1,1,1,0,0,0]
?- hexbin(H, [0,1,0,1,1,0,1,1,1,0,0,0]), format("~s~n", [H]). 5b8
おもしろい。
解法の考え方は。
rotate_right_index
で移動先のインデクス列を作成して、そのインデクスをもとにmap
でビットを写像しています(写像しているという意味でmap
という名前にしてしまいましたが、高階関数としてよくでてくるmapとは別物です)。このとき、変換後のビット列の長さが4の倍数になるように長さを指定して、変換後のビット列がその長さに満たないばあいは0でパディングするようにしています。その前と後ろでhexbin
を使い、16進数文字列とビット列のリストの変換をしています。
以下、コード。
hexbin([], []). hexbin([ 48|Hs], [0,0,0,0|Bs]) :- hexbin(Hs, Bs). hexbin([ 49|Hs], [0,0,0,1|Bs]) :- hexbin(Hs, Bs). hexbin([ 50|Hs], [0,0,1,0|Bs]) :- hexbin(Hs, Bs). hexbin([ 51|Hs], [0,0,1,1|Bs]) :- hexbin(Hs, Bs). hexbin([ 52|Hs], [0,1,0,0|Bs]) :- hexbin(Hs, Bs). hexbin([ 53|Hs], [0,1,0,1|Bs]) :- hexbin(Hs, Bs). hexbin([ 54|Hs], [0,1,1,0|Bs]) :- hexbin(Hs, Bs). hexbin([ 55|Hs], [0,1,1,1|Bs]) :- hexbin(Hs, Bs). hexbin([ 56|Hs], [1,0,0,0|Bs]) :- hexbin(Hs, Bs). hexbin([ 57|Hs], [1,0,0,1|Bs]) :- hexbin(Hs, Bs). hexbin([ 97|Hs], [1,0,1,0|Bs]) :- hexbin(Hs, Bs). hexbin([ 98|Hs], [1,0,1,1|Bs]) :- hexbin(Hs, Bs). hexbin([ 99|Hs], [1,1,0,0|Bs]) :- hexbin(Hs, Bs). hexbin([100|Hs], [1,1,0,1|Bs]) :- hexbin(Hs, Bs). hexbin([101|Hs], [1,1,1,0|Bs]) :- hexbin(Hs, Bs). hexbin([102|Hs], [1,1,1,1|Bs]) :- hexbin(Hs, Bs). rotate_right_index(Size, Rs) :- N is Size * Size - 1, rotate_right_index(Size, N, Rs), !. rotate_right_index(Size, 0, [I]) :- I is Size - 1. rotate_right_index(Size, N, [R|Rs]) :- X is N mod Size, Y is N div Size, R is X * Size + Size - Y - 1, N1 is N - 1, rotate_right_index(Size, N1, Rs). map(0, [], _, []). map(N, [], Ss, [0|Rs]) :- N > 0, N1 is N - 1, map(N1, [], Ss, Rs). map(N, [I|Is], Ss, [R|Rs]) :- nth0(I, Ss, R), N1 is N - 1, map(N1, Is, Ss, Rs). sample2([N,58|Src], [N,58|Dst]) :- Size is N - 48, Length is (Size ** 2 + 3) div 4 * 4, hexbin(Src, S), rotate_right_index(Size, Indexes), map(Length, Indexes, S, R), hexbin(Dst, R). test(Src) :- sample2(Src, Dst), format("~s~n", [Dst]). tests :- test("3:5b8"), test("1:8"), test("2:8"), test("2:4"), test("2:1"), test("3:5d0"), test("4:1234"), test("5:22a2a20"), test("5:1234567"), test("6:123456789"), test("7:123456789abcd"), test("7:fffffffffffff"), test("7:fdfbf7efdfbf0"), test("8:123456789abcdef1"), test("9:112233445566778899aab").
実行結果。
$ swipl -s sample2.pl -g tests -t halt 3:de0 1:8 2:4 2:1 2:2 3:5d0 4:0865 5:22a2a20 5:25b0540 6:09cc196a6 7:f1a206734b258 7:ffffffffffff8 7:ffffffffffc00 8:f0ccaaff78665580 9:b23da9011d22daf005d40