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

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

Prologでビットテトリス

Prologにハマっています。いろんな意味で。
今日も「どう書く」の過去問から。


前回に引き続き、ビット操作です。
今回も数値のままビット操作をする根性がなかったので、0と1からなるリストに変換して操作しています。が、ビット演算をさけてとおれず、Prolog上での初のビット演算。0と1の論理積をしているだけですがビット演算。

Prologのビット演算の論理積論理和演算子はおもしろい形をしています。

Z0 is X0 /\ Y0. % 論理積
Z1 is X1 \/ Y1. % 論理和

(バックスラッシュが¥記号になって表示されているかもしれません。いわゆる全角文字で書くと /\ と \/ です)


数学や論理学で使われる記号「∧」「∨」を模した形になっています。


前回、hexbitが16進数文字列とビット列(0と1だけからなるリスト)の相互の変換に使えるのがおもしろいと書きました。今回は「xx-xx-xx」のようにハイフンを挟んだ形の16進数文字列を変換する必要がありました。しばらく考えて次のように書いたところ…

hex2bin([S0,S1], [B0,B1,B2,B3,B4,B5,B6,B7]) :-
    hexbin([S0,S1], [B4,B5,B6,B7,B0,B1,B2,B3]).
hex2bin([S0,S1,45|Hs], [B0,B1,B2,B3,B4,B5,B6,B7|Bs]) :-
    hexbin([S0,S1], [B4,B5,B6,B7,B0,B1,B2,B3]),
    hex2bin(Hs, Bs).

…これもまたハイフン付きの16進数文字列とビット列の相互の変換に使えてしまいました。白状すると、いまだ「書いたら動いた」というレベルです。それでも「書いたら」ができるぐらいにはPrologがしみ込んできた気がしてきています。
ちなみに。今回のhexbinは前回のものとはちょっと違っていて、下位ビットがリストの先にくるようにしています。なのでhex2binも上位ニブルと下位ニブルを入れ替えるようになっています。


今回はそんな感じ。


以下、コード。

hexbin([], []).
hexbin([ 48|Hs], [0,0,0,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 49|Hs], [1,0,0,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 50|Hs], [0,1,0,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 51|Hs], [1,1,0,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 52|Hs], [0,0,1,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 53|Hs], [1,0,1,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 54|Hs], [0,1,1,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 55|Hs], [1,1,1,0|Bs]) :- hexbin(Hs, Bs).
hexbin([ 56|Hs], [0,0,0,1|Bs]) :- hexbin(Hs, Bs).
hexbin([ 57|Hs], [1,0,0,1|Bs]) :- hexbin(Hs, Bs).
hexbin([ 97|Hs], [0,1,0,1|Bs]) :- hexbin(Hs, Bs).
hexbin([ 98|Hs], [1,1,0,1|Bs]) :- hexbin(Hs, Bs).
hexbin([ 99|Hs], [0,0,1,1|Bs]) :- hexbin(Hs, Bs).
hexbin([100|Hs], [1,0,1,1|Bs]) :- hexbin(Hs, Bs).
hexbin([101|Hs], [0,1,1,1|Bs]) :- hexbin(Hs, Bs).
hexbin([102|Hs], [1,1,1,1|Bs]) :- hexbin(Hs, Bs).

hex2bin([S0,S1], [B0,B1,B2,B3,B4,B5,B6,B7]) :-
    hexbin([S0,S1], [B4,B5,B6,B7,B0,B1,B2,B3]).
hex2bin([S0,S1,45|Hs], [B0,B1,B2,B3,B4,B5,B6,B7|Bs]) :-
    hexbin([S0,S1], [B4,B5,B6,B7,B0,B1,B2,B3]),
    hex2bin(Hs, Bs).

delete_col([], [], []).
delete_col([0|Bs], [S|Ss], [S|Ds]) :-
    delete_col(Bs, Ss, Ds).
delete_col([1|Bs], [1|Ss], Ds) :-
    delete_col(Bs, Ss, Ds1),
    append(Ds1, [0], Ds).

delete_line(_, [], []).
delete_line(Bs, [S0,S1,S2,S3,S4,S5,S6,S7|Ss], [D0,D1,D2,D3,D4,D5,D6,D7|Ds]) :-
    delete_col(Bs, [S0,S1,S2,S3,S4,S5,S6,S7], [D0,D1,D2,D3,D4,D5,D6,D7]),
    delete_line(Bs, Ss, Ds).

and_line([], [1,1,1,1,1,1,1,1]).
and_line([S0,S1,S2,S3,S4,S5,S6,S7|Ss], [D0,D1,D2,D3,D4,D5,D6,D7]) :-
    and_line(Ss, [B0,B1,B2,B3,B4,B5,B6,B7]),
    D0 is S0 /\ B0,
    D1 is S1 /\ B1,
    D2 is S2 /\ B2,
    D3 is S3 /\ B3,
    D4 is S4 /\ B4,
    D5 is S5 /\ B5,
    D6 is S6 /\ B6,
    D7 is S7 /\ B7.

ord2(Src, Dst) :-
    hex2bin(Src, S),
    and_line(S, M),
    delete_line(M, S, D),
    hex2bin(Dst, D).

test(S) :-
    ord2(S, D),
    format("~s~n", [D]).

tests :-
    test("ff-2f-23-f3-77-7f-3b"),
    test("01"),
    test("00"),
    test("7a-4e"),
    test("56-b6"),
    test("12-12-12"),
    test("de-ff-7b"),
    test("95-be-d0"),
    test("7c-b0-bb"),
    test("7a-b6-31-61"),
    test("32-0e-23-82"),
    test("ff-7f-bf-df-ef"),
    test("75-df-dc-6e-42"),
    test("62-51-ef-c7-f8"),
    test("0c-47-8e-dd-5d-17"),
    test("aa-58-5b-6d-9f-1f"),
    test("ff-55-d5-75-5d-57"),
    test("fe-fd-fb-f7-ef-df-bf"),
    test("fd-fb-f7-ef-df-bf-7f"),
    test("d9-15-b5-d7-1b-9f-de"),
    test("38-15-fd-50-10-96-ba"),
    test("fe-fd-fb-f7-ef-df-bf-7f").


実行結果。

$ swipl -s ord2.pl -g tests -t halt
1f-03-00-1c-0d-0f-06
00
00
0c-02
08-14
00-00-00
0a-0f-05
05-1e-20
1c-20-2b
3a-56-11-21
18-06-11-40
0f-07-0b-0d-0e
35-5f-5c-2e-02
22-11-6f-47-78
04-23-46-6d-2d-0b
52-28-2b-35-4f-0f
0f-00-08-04-02-01
7e-7d-7b-77-6f-5f-3f
7e-7d-7b-77-6f-5f-3f
69-05-55-67-0b-4f-6e
18-05-7d-20-00-46-5a
fe-fd-fb-f7-ef-df-bf-7f