gistfile1.rb

# solves the puzzle from https://gist.github.com/1925593
# unpolished version - i'm tired

input = (<<EOF).split("\n").map{|row| row.split(//).map(&:intern)}
-------------
|           |
|           U
|*   * * * *|
|           |
|     #     |
|           |
|           |
-------------
EOF

Field = Struct.new(:weight, :x, :y, :total, :from)

def positions input
  clerks, mouse, cheese = [], nil, nil 
  input.each_with_index do |row, y|
    row.each_with_index do |col, x|
      clerks << [x, y] if col == :*
      mouse = [x, y] if col == :U
      cheese = [x, y] if col == :'#'
    end
  end
  [clerks, mouse, cheese]
end

def create_field input, clerks
  Array.new(input.size) do |row|
    Array.new(input.first.size) do |col|
      Field.new(
        case input[row][col]
        when :-, :|, :* then 1000
        else 100.0 / 1000**clerks.map{|x, y| Math.sqrt((x-col)**2 + (y-row)**2)}.min
        end, col, row, 1000)
    end
  end
end

def flood_fill field
  (1...field.size-1).each do |y|
    (1...field.first.size-1).each do |x|
      f = field[y][x]
      others = [field[y-1][x], field[y][x-1], field[y+1][x], field[y][x+1]]
      others.each do |o|
        f.total, f.from = o.total + f.weight, o if o.total + f.weight < f.total
      end
    end
  end
end

clerks, mouse, cheese = positions(input)
field = create_field(input, clerks)

# score for hole is zero
field[mouse.last][mouse.first].total = 0

# hardcore brute force - there are better (faster) ways
(field.size * field.first.size).times {flood_fill field}

# backtrack path from cheese to the hole
f, count = field[cheese.last][cheese.first], 1
while f.from do
  f = f.from
  input[f.y][f.x] = '.'
  count += 1
end

# output input plus path
input.each do |row|
  puts row.join
end

puts count