benchmark/bm_app_pentomino.rb

   1 #!/usr/local/bin/ruby
   2 # This program is contributed by Shin Nishiyama
   3
   4
   5 # modified by K.Sasada
   6
   7 NP = 5
   8 ROW = 8 + NP
   9 COL = 8
  10
  11 $p = []
  12 $b = []
  13 $no = 0
  14
  15 def piece(n, a, nb)
  16   nb.each{|x|
  17     a[n] = x
  18     if n == NP-1
  19       $p << [a.sort]
  20     else
  21       nbc=nb.dup
  22       [-ROW, -1, 1, ROW].each{|d|
  23         if x+d > 0 and not a.include?(x+d) and not nbc.include?(x+d)
  24           nbc << x+d
  25         end
  26       }
  27       nbc.delete x
  28       piece(n+1,a[0..n],nbc)
  29     end
  30   }
  31 end
  32
  33 def kikaku(a)
  34   a.collect {|x| x - a[0]}
  35 end
  36 def ud(a)
  37   kikaku(a.collect {|x| ((x+NP)%ROW)-ROW*((x+NP)/ROW) }.sort)
  38 end
  39 def rl(a)
  40   kikaku(a.collect {|x| ROW*((x+NP)/ROW)+ROW-((x+NP)%ROW)}.sort)
  41 end
  42 def xy(a)
  43   kikaku(a.collect {|x| ROW*((x+NP)%ROW) + (x+NP)/ROW }.sort)
  44 end
  45
  46 def mkpieces
  47   piece(0,[],[0])
  48   $p.each do |a|
  49     a0 = a[0]
  50     a[1] = ud(a0)
  51     a[2] = rl(a0)
  52     a[3] = ud(rl(a0))
  53     a[4] = xy(a0)
  54     a[5] = ud(xy(a0))
  55     a[6] = rl(xy(a0))
  56     a[7] = ud(rl(xy(a0)))
  57     a.sort!
  58     a.uniq!
  59   end
  60   $p.uniq!.sort! {|x,y| x[0] <=> y[0] }
  61 end
  62
  63 def mkboard
  64   (0...ROW*COL).each{|i|
  65     if i % ROW >= ROW-NP
  66       $b[i] = -2
  67     else
  68       $b[i] = -1
  69     end
  70     $b[3*ROW+3]=$b[3*ROW+4]=$b[4*ROW+3]=$b[4*ROW+4]=-2
  71   }
  72 end
  73
  74 def pboard
  75   return # skip print
  76   print "No. #$no\n"
  77   (0...COL).each{|i|
  78     print "|"
  79     (0...ROW-NP).each{|j|
  80       x = $b[i*ROW+j]
  81       if x < 0
  82         print "..|"
  83       else
  84         printf "%2d|",x+1
  85       end
  86     }
  87     print "\n"
  88   }
  89   print "\n"
  90 end
  91
  92 $pnum=[]
  93 def setpiece(a,pos)
  94   if a.length == $p.length then
  95     $no += 1
  96     pboard
  97     return
  98   end
  99   while $b[pos] != -1
 100     pos += 1
 101   end
 102   ($pnum - a).each do |i|
 103     $p[i].each do |x|
 104       f = 0
 105       x.each{|s|
 106         if $b[pos+s] != -1
 107           f=1
 108           break
 109         end
 110       }
 111       if f == 0 then
 112         x.each{|s|
 113           $b[pos+s] = i
 114         }
 115         a << i
 116         setpiece(a.dup, pos)
 117         a.pop
 118         x.each{|s|
 119           $b[pos+s] = -1
 120         }
 121       end
 122     end
 123   end
 124 end
 125
 126 mkpieces
 127 mkboard
 128 $p[4] = [$p[4][0]]
 129 $pnum = (0...$p.length).to_a
 130 setpiece([],0)
 131
 132
 133 __END__
 134
 135 # original
 136
 137 NP = 5
 138 ROW = 8 + NP
 139 COL = 8
 140
 141 $p = []
 142 $b = []
 143 $no = 0
 144
 145 def piece(n,a,nb)
 146   for x in nb
 147     a[n] = x
 148     if n == NP-1
 149       $p << [a.sort]
 150     else
 151       nbc=nb.dup
 152       for d in [-ROW, -1, 1, ROW]
 153         if x+d > 0 and not a.include?(x+d) and not nbc.include?(x+d)
 154           nbc << x+d
 155         end
 156       end
 157       nbc.delete x
 158       piece(n+1,a[0..n],nbc)
 159     end
 160   end
 161 end
 162
 163 def kikaku(a)
 164   a.collect {|x| x - a[0]}
 165 end
 166 def ud(a)
 167   kikaku(a.collect {|x| ((x+NP)%ROW)-ROW*((x+NP)/ROW) }.sort)
 168 end
 169 def rl(a)
 170   kikaku(a.collect {|x| ROW*((x+NP)/ROW)+ROW-((x+NP)%ROW)}.sort)
 171 end
 172 def xy(a)
 173   kikaku(a.collect {|x| ROW*((x+NP)%ROW) + (x+NP)/ROW }.sort)
 174 end
 175
 176 def mkpieces
 177   piece(0,[],[0])
 178   $p.each do |a|
 179     a0 = a[0]
 180     a[1] = ud(a0)
 181     a[2] = rl(a0)
 182     a[3] = ud(rl(a0))
 183     a[4] = xy(a0)
 184     a[5] = ud(xy(a0))
 185     a[6] = rl(xy(a0))
 186     a[7] = ud(rl(xy(a0)))
 187     a.sort!
 188     a.uniq!
 189   end
 190   $p.uniq!.sort! {|x,y| x[0] <=> y[0] }
 191 end
 192
 193 def mkboard
 194   for i in 0...ROW*COL
 195     if i % ROW >= ROW-NP
 196       $b[i] = -2
 197     else
 198       $b[i] = -1
 199     end
 200     $b[3*ROW+3]=$b[3*ROW+4]=$b[4*ROW+3]=$b[4*ROW+4]=-2
 201   end
 202 end
 203
 204 def pboard
 205   print "No. #$no\n"
 206   for i in 0...COL
 207     print "|"
 208     for j in 0...ROW-NP
 209       x = $b[i*ROW+j]
 210       if x < 0
 211         print "..|"
 212       else
 213         printf "%2d|",x+1
 214       end
 215     end
 216     print "\n"
 217   end
 218   print "\n"
 219 end
 220
 221 $pnum=[]
 222 def setpiece(a,pos)
 223   if a.length == $p.length then
 224     $no += 1
 225     pboard
 226     return
 227   end
 228   while $b[pos] != -1
 229     pos += 1
 230   end
 231   ($pnum - a).each do |i|
 232     $p[i].each do |x|
 233       f = 0
 234       for s in x do
 235         if $b[pos+s] != -1
 236           f=1
 237           break
 238         end
 239       end
 240       if f == 0 then
 241         for s in x do
 242           $b[pos+s] = i
 243         end
 244         a << i
 245         setpiece(a.dup, pos)
 246         a.pop
 247         for s in x do
 248           $b[pos+s] = -1
 249         end
 250       end
 251     end
 252   end
 253 end
 254
 255 mkpieces
 256 mkboard
 257 $p[4] = [$p[4][0]]
 258 $pnum = (0...$p.length).to_a
 259 setpiece([],0)