prologのメモ化に関して
https://qiita.com/smallbigcats/items/f6747ae2001d8f39c05a
の記事を書く過程で、最初に見つけた問題です。
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord22irrpas/
メモ化を想定した問題とのコメントによりたどり着きました。
まずはindexが0からの二次元配列が使えるNimでと思い、Nimでプログラムしてみましたが、
後で述べるようにPrologのメモ化の例題には向かなかったようです。
久しぶりでNimで書いたら文法を忘れていて苦労しました。
どちらも初心者ですがJuliaのほうが書きやすそうです。
ざっと説明します。
基本的に、最後のセルから、その左と下側に接しているセルの数値を足して己が数値にするという再帰プログラムですが、
私の頭では隣接関係の計算法がわかりませんでしたので、二次元配列を二つ作り、supoにセルの配置を記述しました。
具体的には、大きなセルのすべての配列要素に、同じ文字列(問題のセルを指定する文字列)を代入しました。
そして、supoのほうで、隣接関係を把握しつつ、rectの方に数値を代入しました。
左上のセルだけ特別扱いだったり、似たコードを繰り返したりで不満ですが、いい方法がわかりません。
ところで、まずはメモ化を意識しないプログラムからと思っていたのですが、
下記のようなプログラムになっていました。
四角形の図形問題は二次元配列を使いたくなりますし、使えば値を代入したくなりますが、
こういうのもメモ化というのでしょうか。
確かに"#これが入るとメモ化"とコメントしてある部分を省いても正解が出るのですが。
import times, os
var
rect:seq[seq[int]] #procのparameterの値を変えられないのでグローバル変数にする
supo:seq[seq[string]]
proc ston(str:string):array[4,int]=
var tmp:array[4,int]
for i in 0..3:
tmp[i]=str[i].int-48 #parseIntはcharには使えない
return tmp
proc change(i,j:int):int=
var sum=0
if rect[i][j]>=0:
return rect[i][j]
elif supo[i][j]!="":
var nl=ston(supo[i][j])
var x=nl[0]+1
sum=sum+change(x,nl[1])
if nl[2]>1:
for x in nl[0]+2..nl[0]+nl[2]:
if (supo[x][nl[1]]=="") or (supo[x-1][nl[1]]!=supo[x][nl[1]]):
sum=sum+change(x,nl[1])
var y=nl[1]+1
sum=sum+change(nl[0],y)
if nl[3]>1:
for y in nl[1]+2..nl[1]+nl[3]:
if (supo[nl[0]][y]=="") or (supo[nl[0]][y-1]!=supo[nl[0]][y]):
sum=sum+change(nl[0],y)
var sum1=sum mod 100
for x in nl[0]+1..nl[0]+nl[2]: #これが入るとメモ化
for y in nl[1]+1..nl[1]+nl[3]: #これが入るとメモ化
rect[x][y]=sum1 #これが入るとメモ化
return sum1
else:
sum=sum+change(i-1,j)
sum=sum+change(i,j-1)
var sum1=sum mod 100
rect[i][j]=sum1 #これが入るとメモ化
return sum1
proc solve(nx,ny:int,sq:seq[string])=
var
col : seq[int]
col1:seq[string]
col = @[]
col1= @[]
for i in 0..ny:
col.add(-1)
col1.add("")
rect = @[]
supo= @[]
for j in 0..nx:
rect.add(col)
supo.add(col1)
rect[1][1]=1
for i in 0..nx:
rect[i][0]=0
for i in 0..ny:
rect[0][i]=0
for str in sq:
var nl=ston(str)
for i in 1..nl[2]:
for j in 1..nl[3]:
supo[nl[0]+i][nl[1]+j]=str
var val=supo[1][1]
if val != "" : #一番左が大きくなった時特別扱い
for i in 1..nx:
for j in 1..ny:
if supo[i][j]==val:
rect[i][j]=1
var res=change(nx,ny)
echo(res)
solve(2,3,@["0021"])
solve(3,3,@["1221","0021","0131"])
solve(3,6,@["0024","0432","2013"])
solve(9,9,@["1177"])
solve(9,9,@["1019","3019","5019","7019"])
solve(9,9,@["2234","8412","0792","6421","1681"])
solve(8,7,@["5422","6022","2262","1522","3422","0122","0322","2032","6621","4621","0512","7412","5012"])
solve(9,9,@["3324","5217","8116","2312","7314","6414","3061","7721","1231","1514","3712"])
本ページの主旨とは違いますが、二重のforループを横方向のループの始点を後ろにずらしながら
繰り返すことで解くプログラムも作ってみました。
この問題に関してはメモ化よりやや早いようです。
import times, os
var
rect:seq[seq[int]] #procのparameterの値を変えられないのでグローバル変数にする
supo:seq[seq[string]]
proc ston(str:string):array[4,int]=
var tmp:array[4,int]
for i in 0..3:
tmp[i]=str[i].int-48
return tmp
proc change(nx,ny:int)=
var pos:seq[int]
pos = @[]
for i in 0..ny:
pos.add(1)
while pos[ny]<=nx:
for j in 1..ny:
block xloop:
var px=pos[j]
for i in px..nx:
if rect[i][j]>=0:
pos[j]=i+1
continue
var sum=0
if supo[i][j]!="":
var nl=ston(supo[i][j])
var x=nl[0]+1
if rect[x][nl[1]]<0:
break xloop
sum=sum+rect[x][nl[1]]
if nl[2]>1:
for x in nl[0]+2..nl[0]+nl[2]:
if rect[x][nl[1]]<0:
break xloop
if (supo[x][nl[1]]=="") or (supo[x-1][nl[1]]!=supo[x][nl[1]]):
sum=sum+rect[x][nl[1]]
var y=nl[1]+1
if rect[nl[0]][y]<0:
break xloop
sum=sum+rect[nl[0]][y]
if nl[3]>1:
for y in nl[1]+2..nl[1]+nl[3]:
if rect[nl[0]][y]<0:
break xloop
if (supo[nl[0]][y]=="") or (supo[nl[0]][y-1]!=supo[nl[0]][y]):
sum=sum+rect[nl[0]][y]
var sum1=sum mod 100
for x in nl[0]+1..nl[0]+nl[2]:
for y in nl[1]+1..nl[1]+nl[3]:
rect[x][y]=sum1
pos[j]=nl[0]+nl[2]+1
elif rect[i-1][j]>=0 and rect[i][j-1]>=0:
sum=sum+rect[i-1][j]
sum=sum+rect[i][j-1]
var sum1=sum mod 100
rect[i][j]=sum1
pos[j]=i+1
proc solve(nx,ny:int,sq:seq[string])=
var
col : seq[int]
col1:seq[string]
col = @[]
col1= @[]
for i in 0..ny:
col.add(-1)
col1.add("")
rect = @[]
supo= @[]
for j in 0..nx:
rect.add(col)
supo.add(col1)
rect[1][1]=1
for i in 0..nx:
rect[i][0]=0
for i in 0..ny:
rect[0][i]=0
for str in sq:
var nl=ston(str)
for i in 1..nl[2]:
for j in 1..nl[3]:
supo[nl[0]+i][nl[1]+j]=str
var val=supo[1][1]
if val != "" : #一番左が大きくなった時特別扱い
for i in 1..nx:
for j in 1..ny:
if supo[i][j]==val:
rect[i][j]=1
change(nx,ny)
echo(rect[nx][ny])
solve(2,3,@["0021"])
solve(3,3,@["1221","0021","0131"])
solve(3,6,@["0024","0432","2013"])
solve(9,9,@["1177"])
solve(9,9,@["1019","3019","5019","7019"])
solve(9,9,@["2234","8412","0792","6421","1681"])
solve(8,7,@["5422","6022","2262","1522","3422","0122","0322","2032","6621","4621","0512","7412","5012"])
solve(9,9,@["3324","5217","8116","2312","7314","6414","3061","7721","1231","1514","3712"])