オフラインどう書くE10の解答

問題はこちら->http://mtsmfm.github.io/2016/12/03/doukaku-e10.html

Prolog,Julia ,Ruby,Nimで解いています。
かなり前の下書きを修正してJulia,Nimでは最近のバージョンで動くよう一部変更しました。

まずPrologで解きました。
操作（OX）と全体の中の黒の正方形の位置（角、辺、中）によって場合分します。
元の黒い正方形が角
　X->黒が辺に2個、中に2個に変化、白が2個増加、
　O->黒が角に1個,辺に2個,中に2個に変化,白が2個増加
元の黒い正方形が辺
　X->黒が辺に1個、中に3個に変化、白が1個増加、
　O->黒が辺に2個,中に3個に変化,白が1個増加
元の黒い正方形が中
　X->黒が中に4個に変化、白が1個増加、
　O->黒が中に5個に変化,白が0個増加
この情報はp/5に入っています。
p(OまたはX,[元の黒が角、辺、中の場合の白の増加数],[元の黒が角の場合の角、辺、中の黒の数],[元の黒が辺の場合の角、辺、中の黒の数],[元の黒が中の場合の角、辺、中の黒の数])
更にXの場合それまであった白領域は一つにつながります。
これらを踏まえ、最初の操作後の白の数と各々の位置の黒の数を初期値としてsolve1に渡し、
solve1(OXのリスト,白の数,[角の黒の数,辺の黒の数,中の黒の数],白の数の戻り値)
操作のたびにcal/3で変化を計算します。
cal(OまたはX,[白の数,角の黒の数,辺の黒の数,中の黒の数],それぞれの数の戻り値のリスト)

```Prolog
%swi-Prolog  version 7.4.2
%start.
%:-initialization(start).   %for ideone

p('O',[2,1,0],[1,2,2],[0,2,3],[0,0,5]).
p('X',[2,1,1],[0,2,2],[0,1,3],[0,0,4]).

solve1([],W,_,W).
solve1([X|T],W,[K,H,N],R):-
     cal(X,[W,K,H,N],[W1,K1,H1,N1]),solve1(T,W1,[K1,H1,N1],R).

solve([H|T],W):-H=='O'->solve1(T,4,[4,0,1],W);solve1(T,5,[0,4,0],W).

cal(OX,[W,K,H,N],[W1,K1,H1,N1]):-
     !,p(OX,[WK,WH,WN],[KK,HK,NK],[KH,HH,NH],[KN,HN,NN]),
     (OX=='X'->W0=1;W0=W),W1 is W0+K*WK+H*WH+N*WN,
     K1 is K*KK+H*KH+N*KN,H1 is K*HK+H*HH+N*HN,N1 is K*NK+H*NH+N*NN.

disp(R,N):-number_chars(N1,N),
     (R==N1->Str=" pass ";Str=" fail "),write(Str),write(R),write("\n").

start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0).

pre([]).
pre([_,B,N|T]):-atom_chars(B,L),solve(L,R),disp(R,N),pre(T).

%start.

str("0       X       5
1       O       4
2       XX      5
3       OX      10
4       XO      9
5       XOO     17
6       OXX     21
7       OXO     18
8       OOOX    130
9       OXXO    29
10      XXOX    81
11      XOXXO   89
12      OOOOX   630
13      OXOOO   66
14      OXOXOX  2001
15      OXOXXO  417
16      OXXOXX  1601
17      XXXOXOO 345
18      OOOOOXO 3258
19      OXXOXXX 6401").
```
次いでJuliaを用いて具体的に配置を求め、その後白の領域の数を求めてみました。
一辺が3を操作数だけ累乗した数の升目を表す配列を用意し、
n番目の操作時には一片を3^(n-1)等分した大きさの黒い四角を対象とします。
この過程は速さも十分で問題なかったのですが、白の領域の数を数える過程(pin)で、
一つの領域を確定するのにある座標から4方向の座標を探索するのですが、
ここに深さ優先の再帰を使うとスタックオーバーフローが起きてしまいます。
そこで本命のプログラムを作成済みの気楽さで他の方の解答を拝見し、
@mtsmfmさんの解答が幅優先探索のように見受けられましたので、
->https://github.com/mtsmfm/doukaku/blob/master/20161127/doukaku.rb
幅優先だとメモリが足りないのではと思っていましたが、試しに幅優先で書き直してみました。
set のほうが selより早いようです。

```Julia
#Julia 1.6.2

const     data=[[1,0],[0,1],[-1,0],[0,-1]]

function solve(s)
　function pin(set)
     l=Set{Array{Int,1}}()
     for (x,y) in set
         if fi[x,y]==1
             fi[x,y]=10
             for (cx,cy) in data
                  x1=x+cx
                  y1=y+cy
                  if x1>0 && y1>0 && x1<w+1 && y1<w+1 && fi[x1,y1]==1
                      push!(l,[x1,y1])
                  end
             end
         end
     end
     if l!=Set()
        pin(l)
     end
  end
  sum=0
  n=length(s)
  w=3^n
  fi=zeros(Int,w,w)
  for i in 0:n-1
     m=3^i
     v=div(w,m)
     u=div(v,3)
     for j in 1:m,k in 1:m
               x=(j-1)*v+1
               y=(k-1)*v+1
               if fi[x,y]==0
                  for i1 in 0:u-1,j1 in 0:u-1
                        if s[i+1]=='O'
                           fi[x+u+i1,y+j1]=1
                           fi[x+i1,y+u+j1]=1
                           fi[x+u*2+i1,y+u+j1]=1
                           fi[x+u+i1,y+u*2+j1]=1
                       else
                           fi[x+i1,y+j1]=1
                           fi[x+u*2+i1,y+j1]=1
                           fi[x+u+i1,y+u+j1]=1
                           fi[x+i1,y+u*2+j1]=1
                           fi[x+u*2+i1,y+u*2+j1]=1
                       end
                   end
               end
         end
    end
    for x in 1:w,y in 1:w
        if fi[x,y]==1
            sum=sum+1
            pin(Set([[x,y]])) 
        end
    end
 return sum
end

function main()
  @time print(solve("OXXOXX"))
  @time print(solve("OXOXOX"))
  @time print(solve("OXXOXXX"))
end

main()
```
これでオーバーフローは回避できましたが実行時間が結構長かったので、
@mtsmfmさんの解答がRubyでしたのでRubyにうつしてみました。
いろいろ試してみましたがSetよりArrayのほうが早いようです。
ただし、Arrayで座標の重複を避けるためその要素を調べると非常に遅くなりますので、
重複量は問題になるほどでもなさそうですしそこは甘受しています。
「どう書く」のRubyに練達された方々のに比べると稚拙ですが、Juliaよりすこし高速でした。
先入観に反していて驚きました。Juliaにもっと早くなる書き方があるのでしょうか。

```Ruby
#version 3.0.1
require "benchmark"

 def pin1(sel,w,fi,data)
      l=[]
      sel.each do |x,y|
        if fi[x][y]==1
         fi[x][y]=10
         data.each do |cx,cy|
            x1=x+cx
            y1=y+cy
            if x1>=0 && y1>=0 && x1<w && y1<w && fi[x1][y1]==1
                l.push([x1,y1])
            end
         end
        end
     end
     if l!=[]
        pin1(l,w,fi,data)
     end
  end

def solve(s)
    sum=0
    n=s.size
    w=3**n
    fi=Array.new(w){ Array.new(w) }
    data=[[1,0],[0,1],[-1,0],[0,-1]]
    for i in 0..n-1
       m=3**i
       v=w/m
       u=v/3
       for j in 0..m-1
        for k in 0..m-1
               x=j*v
               y=k*v
               if fi[x][y].nil?
                  for i1 in 0..u-1
                    for j1 in 0..u-1
                        if s[i]=='O'
                           fi[x+u+i1][y+j1]=
                           fi[x+i1][y+u+j1]=
                           fi[x+u*2+i1][y+u+j1]=
                           fi[x+u+i1][y+u*2+j1]= 1
                       else
                           fi[x+i1][y+j1]=
                           fi[x+u*2+i1][y+j1]=
                           fi[x+u+i1][y+u+j1]=
                           fi[x+i1][y+u*2+j1]=
                           fi[x+u*2+i1][y+u*2+j1]= 1
                       end
                    end
                   end
               end
         end
      end
    end
    for x in 0..w-1
      for y in 0..w-1
        if fi[x][y]==1
            sum=sum+1
            pin1([[x,y]],w,fi,data)     #こちらのほうが早い
        end
      end
    end
 return sum
end

def main()
 p Benchmark.measure {p solve("OXXOXX")}
 p Benchmark.measure {p solve("OXOXOX")}
 p Benchmark.measure {p solve("OXXOXXX")} 
end

main()
```
Juliaでオーバーフローしたり、結構時間がかかったりましたので、Nimではどうか試してみました。
NimはAtom editorの上でパズルを解く程度なら、インタプリタと同じような感覚で使えて便利です。
for loopや配列などの書き方が、rubyに似ているのでrubyからうつしました。
予想に反しPinの部分を再帰で書くとまだオーバーフローが起きるため、
再帰を使わないよう工夫しました。
さすがに早いです。（Rubyで再帰とwhieの実行時間に大差ありません）
空のSeqを使わずにsel1にpop,addを用いたら遅くなりました。

```Nim
#version v 0.19.4

import os,strutils,sequtils,times
import math   #これがないと累乗が使えない

type
    Field=seq[seq[int]]
    Sel=seq[array[0..1, int]]
var
    fi:Field

const
    data=[[1,0],[0,1],[-1,0],[0,-1]]

proc solve(s:string)=
    var sum=0
    let n=len(s)
    let w= 3^n
    var col : seq[int]
    col = @[]
    for i in 0..w-1:
         col.add(0)
    fi = @[]
    for j in 0..w-1:
         fi.add(col)

    proc pin(sel:Sel)=
      var sel1=sel
      var l2:Sel
      while sel1 != @[]:    #再帰だとスタックオーバー
        l2= @[]
        for tmp in sel1:
            let x=tmp[0]
            let y=tmp[1]
            if fi[x][y]==1:
                 fi[x][y]=10
                 for xy in data:
                      let x1=x+xy[0]
                      let y1=y+xy[1]
                      if  x1>=0 and y1>=0 and x1<w and y1<w and fi[x1][y1]==1:
                          l2.add([x1,y1])
        sel1=l2

    for i in 0..n-1:
        var m=3^i
        var v=w div m
        var u=v div 3
      # print(u)
        for j in 0..m-1:
             for k in 0..m-1:
                 var x=j*v
                 var y=k*v
                 if fi[x][y]==0:
                #  print(x,y)
                    for i1 in 0..u-1:
                         for j1 in 0..u-1:
                              if s[i]=='O':
                                   fi[x+u+i1][y+j1]= 1
                                   fi[x+i1][y+u+j1]= 1
                                   fi[x+u*2+i1][y+u+j1]= 1
                                   fi[x+u+i1][y+u*2+j1]= 1
                              else:
                                   fi[x+i1][y+j1]= 1
                                   fi[x+u*2+i1][y+j1]= 1
                                   fi[x+u+i1][y+u+j1]= 1
                                   fi[x+i1][y+u*2+j1]= 1
                                   fi[x+u*2+i1][y+u*2+j1]= 1

    for x in 0..w-1:
        for y in 0..w-1:
            if fi[x][y]==1:
                 sum=sum+1
                 pin(@[[x,y]])
    echo sum

template time(s): float =
    let t0 = cpuTime()
    s
    cpuTime() - t0

proc main()=
    echo time(solve("OXXOXX"))
    echo time(solve("OXOXOX"))
    echo time(solve("OXXOXXX"))
main()

```