fork download
copy 
  1. class GoldMaze
  2.   attr_accessor :n,:score, :count, :sum, :maze
  3.   def initialize n,level,maze=[]
  4.     @n = n
  5.     @level=level
  6.     if maze == []
  7.       @maze = n.times.map { |i| n.times.map { |j| rand(10) } }
  8.     else
  9.       @maze = maze
  10.     end
  11.     @x = n/2
  12.     @y = n/2
  13.     @maze[@y][@x] = 0
  14.     @score = 0
  15.     @bestsofar = 0
  16.     @count = 0
  17.     @sum = 0
  18.     @maze.each do |row|
  19.       row.each do |cell|
  20.         @sum += cell
  21.       end
  22.     end
  23.   end
  24.  
  25.   # pattern tells which cells have been visited. Bitmap.
  26.   # path shows the path being followed. e.g. 'urdl'
  27.   def find n, x, y, pattern, score, path
  28.     @count += 1
  29.     bit = @n*x+y
  30.     s2 = score
  31.     cell = 0
  32.     cell = @maze[y][x] if @maze[y][x] != ' ' and @maze[y][x] != '*' and pattern[bit]==0
  33.     s2 += cell
  34.     return [0,path] if pattern[bit] == 1
  35.     return [0,path] if @maze[y][x] == 0
  36.     return [0,path] if s2 + 9 * (@level - n) <= @bestsofar and pattern[bit]==0
  37.  
  38.     @bestsofar = s2  if n == @level and s2 > @bestsofar
  39.     return [s2,path] if n == @level 
  40.  
  41.     n2 = n+1
  42.     p2 = pattern | (1 << @n*x+y)
  43.  
  44.     cands = [['r',(x+1)%@n, y], ['l',(x-1)%@n, y], ['d',x,(y+1)%@n], ['u',x,(y-1)%@n] ].map do |dir,x,y|
  45.       bit = @n*x+y
  46.       value = 0
  47.       value = @maze[y][x] if @maze[y][x] != ' ' and pattern[bit] == 0
  48.       [value, dir,x,y]
  49.     end
  50.  
  51.     cands.map do |_,dir,x,y|
  52.       find(n2, x, y, p2, s2, path+dir)
  53.     end.sort.last
  54.  
  55.   end
  56.  
  57. end
  58.  
  59. n = 5
  60. level = 20
  61. maze = GoldMaze.new 5,level, [[9, 1, 3, 1, 9], [6, 3, 2, 4, 1], [0, 7, 1, 7, 7], [5, 4, 9, 4, 9], [7, 9, 1, 5, 5]]
  62. maze.maze[n/2][n/2] = ' '
  63.  
  64. start = Time.now
  65. optimum = maze.find(0,maze.n/2,maze.n/2,0,0,'')
  66. puts "CPU: #{Time.now-start}"
  67. puts optimum
  68.  
  69. # Result:
  70. #CPU: 16.577948
  71. #115
  72. #rrdrdruuululululdddr
Time limit exceeded #stdin #stdout 5s 7988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UOAMZO
language:
Ruby (ruby 2.5.5)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!