矩形の中の矩形

オフラインリアルタイムどう書くE14 の中で、@yancya さんが書かれたターゲットとなる矩形（配列の配列）を取り出すコードがスマートだったので、Prolog で書いてみました。

• https://gist.github.com/yancya/cfdafda3a7c80866f25e17887e0c8ca1#file-main-rb-L110-L114

Ruby

今回の問題の特徴から解くために向きは影響しないため、解答のコードでは transposeは 1 回ですが、下記の例では向きを元に戻すため再度 transpose しています。

rect = %w(12345 23456 34567 45678).map(&:chars).map {|row| row.map(&:to_i) }
# => [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8]]
rect.each_cons(3).map {|rows| rows.transpose.each_cons(3).map(&:transpose) }.flatten(1)
# => [[[1, 2, 3], [2, 3, 4], [3, 4, 5]],
#     [[2, 3, 4], [3, 4, 5], [4, 5, 6]],
#     [[3, 4, 5], [4, 5, 6], [5, 6, 7]],
#     [[2, 3, 4], [3, 4, 5], [4, 5, 6]],
#     [[3, 4, 5], [4, 5, 6], [5, 6, 7]],
#     [[4, 5, 6], [5, 6, 7], [6, 7, 8]]]

Prolog

GNU Prolog で実装しています。

extract(Offset, Length, List, Extract) :-
  append(Left, ExtractRight, List),
  append(Extract, _Right, ExtractRight),
  length(Left, Offset),
  length(Extract, Length).

subrectangle(Width, Height, Rectangle, SubRectangle) :-
  extract(_, Height, Rectangle, Rows),
  maplist(extract(_, Width), Rows, SubRectangle).

subrectangle.prolog という名前で保存して、gprolog コマンドで GNU Prolog を起動します。

| ?- ['subrectangle.prolog'].
| ?- findall(S, subrectangle(3, 3, [[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7],[4,5,6,7,8]], S), SS).

SS = [[[1,2,3],[2,3,4],[3,4,5]],[[2,3,4],[3,4,5],[4,5,6]],[[3,4,5],[4,5,6],[5,6,7]],[[2,3,4],[3,4,5],[4,5,6]],[[3,4,5],[4,5,6],[5,6,7]],[[4,5,6],[5,6,7],[6,7,8]]]

例えば、3 x 3 のリストのリストの要素の合計を表す述語を用意しておくと、

sum3x3([[A11, A12, A13], [A21, A22, A23], [A31, A32, A33]], Sum) :-
  Sum is A11 + A12 + A13 + A21 + A22 + A23 + A31 + A32 + A33.

それを満たす組み合わせを得ることができます。

| ?- subrectangle(3, 3, [[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7],[4,5,6,7,8]], S), sum3x3(S, 45), !.

S = [[3,4,5],[4,5,6],[5,6,7]]

次回はどう書くの問題を解くコードを Prolog で書きます。つづく。

いつか読むはずっと読まない：かはく

国立科学博物館、通称かはく。

始祖鳥・ロンドン標本が来ています（2017/06/11 まで）。

かはくは一度入ると３、４時間でてこられなくなるので危険です。

国立科学博物館のひみつ

国立科学博物館のひみつ 地球館探検編