Help us understand the problem. What is going on with this article?

オフラインどう書く第22回、メモ化?

More than 1 year has passed since last update.

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"])
smallbigcats
30年以上の日曜プログラマ。 スパゲッティプログラムの癖が抜けません。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away