エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

Prologはビットマップイメージの夢を見るか

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