問題はこちら->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,[白の数,角の黒の数,辺の黒の数,中の黒の数],それぞれの数の戻り値のリスト)
%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 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にもっと早くなる書き方があるのでしょうか。
#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を用いたら遅くなりました。
#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()