On Fri, Sep 26, 2008 at 4:53 PM, Matthew Moss <matthew.moss / gmail.com> wrote:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> ## Cookie Monster (#178)

> Cookie Monster is trying to walk through the Cookie Forest and consume
> as many cookies as possible. However, there are many different paths
> that Cookie Monster can take, and he isn't sure which way is the best
> way. Help him eat as many cookies as possible by writing a program
> which finds the optimal path from the upper left part of the forest to
> the bottom right. Cookie Monster can only move south and east. There
> are also several thorn patches through which he cannot cross. The
> forest can be represented as a grid of numbers, where the number
> represents the amount of cookies in that acre and -1 represents an
> impassible thorn patch. An example forest is provided below:

Hi,

Thanks for the fun quizzes. This is my solution:

It starts from the last square moving backwards (same row, east to west,
then previous row, etc), calculating the better path, noting in each "node"
which is the optimal direction and the sum of cookies for that path.
At the end, the number of cookies is the value of the first node, and
the program
follows the directions in each node to report the path. I represent
the forest as
a  two dimension array, where each position is an array of the number of cookies
and the direction to follow. I also take into account squares that
shouldn't be passable
because both their east and south neighbours are impassable:

1 50 -1
1 -1 2
1 1 1

The square with 50 cookies is not passable, cause would lead to a dead-end,
so when processing it I change it to a -1 so that upper neighbours don't take it
into account.


data =<<EOD
1  3  0  5 -1  7 -1 -1  0  4  2  1
-1  3  2  1 -1  4 -1  5  3 -1  1  0
5  4  8 -1  3  2  2 -1  4 -1  0  0
2  1  0  4  1 -1  8  0  2 -1  2  5
1  4  0  1 -1  0  3  2  2  4  1  4
0  1  4  1  1  6  1  4  5  2  1  0
3  2  5  2  0  7 -1  2  1  0 -1  3
0 -1  4 -1 -1  3  5  1  4  2  1  2
5  4  8 -1  3  2  2 -1  4 -1  0  0
2  1  0  4  1 -1  8  0  2 -1  2  5
1  3  0  5 -1  7 -1 -1  0  4  2  1
0  0  3  1  5  2  1  5  4  1  3  3
EOD

def get_possible_destinations field,i,j
	destinations = []
	south = (field[i+1] || [])[j]
	if south && south[0] != -1
		destinations << [south[0], :S]
	end
	east = field[i][j+1]
	if east && east[0] != -1
		destinations << [east[0], :E]
	end
	destinations
end


field = data.map {|line| line.split.map {|e| [e.to_i, nil]}}
(field.length - 1).downto(0) do |i|
	(field[i].length - 1).downto(0) do |j|
		#skip the -1 so they don't get updated
		next if field[i][j][0] == -1
		dest = get_possible_destinations(field,i,j)
		unless dest.empty?
			add = dest.max {|x,y| x[0] <=> y[0]}
			field[i][j][0] += add[0]
			field[i][j][1] = add[1]
		else
			# This square is not passable, since it
			# doesn't have any valid destination, unless
			# it's the lower-right corner.
			field[i][j][0] = -1 unless (i == field.length - 1 && j ==
field.last.length - 1)
		end
	end
end

puts "Number of cookies: #{field[0][0][0]}"

i = j = 0
current = field[i][j]
path = []
until current[1].nil?
	path << current[1]
	current[1] == :E ? j += 1 : i += 1
	current = field[i][j]
end
puts path.join(",")



Thanks for the quiz.

Jesus.