Skip to content

Instantly share code, notes, and snippets.

@vestige
Forked from you-ssk/gist:3973734
Created October 30, 2012 11:03
Show Gist options
  • Save vestige/3979625 to your computer and use it in GitHub Desktop.
Save vestige/3979625 to your computer and use it in GitHub Desktop.
class Maze
def initialize(w,h,input)
@len_map = Hash.new
@len_map[[w-1,h-1]] = 1
make_fence(input)
end
def make_fence(input)
lr, tb = [], []
input.each_with_index do |e,i|
e.map!{|c| c==1 ? false : true}
lr << e if i.even?
tb << e if i.odd?
end
@lr = lr.map{|e| [false,e,false].flatten}
@tb = tb.transpose.map{|e| [false,e,false].flatten}
end
def cell(i,j)
[@tb[i][j], @lr[j][i+1], @tb[i][j+1], @lr[j][i]]
end
def length
count = 1
until @len_map[[0,0]]
s = @len_map.select{|k,v| v == count}
break if s.size == 0
count += 1
s.each do |k,v|
i,j = k[0], k[1]
w = cell(i,j)
@len_map[[i,j-1]] = count if w[0] && !@len_map[[i,j-1]]
@len_map[[i,j+1]] = count if w[2] && !@len_map[[i,j+1]]
@len_map[[i+1,j]] = count if w[1] && !@len_map[[i+1,j]]
@len_map[[i-1,j]] = count if w[3] && !@len_map[[i-1,j]]
end
end
@len_map[[0,0]] || 0
end
end
inputs = File.open('input.txt').map do |l|
l.split.map{|e| Integer(e)}
end
until inputs.empty?
w, h = inputs.shift
break if w==0 and h==0
input = []
(h*2-1).times do input << inputs.shift end
m = Maze.new(w,h,input)
p m.length
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment