Asp Forum - [QUIZ] Cookie Monster (#178

Matthew Moss

9/26/2008 2:54:00 PM

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

<http://splatbang.com/rub....

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Cookie Monster (#178)

_Quiz description provided by Lee Jarvis._

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:

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

--
Matthew Moss <matthew.moss@gmail.com>

15 Answers

Jesús Gabriel y Galán

9/28/2008 3:07:00 PM

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.

brabuhr

9/28/2008 4:40:00 PM

On 9/26/08, Matthew Moss <matthew.moss@gmail.com> wrote:
> ## Cookie Monster (#178)
>
> _Quiz description provided by Lee Jarvis._
>
> 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.

I worked up 2 solutions. For the code, forest maps, and sample output:

http://github.com/fjc/rubyquiz/tree/...

First, solution number 2:

Since Cookie Monster can only make one of 2 moves at any given time, I
thought I would use (binary) integers to store his possible paths.
So, for example, for a 2x2 forest his only possible paths are
South->East or East->South: encode one as "10" and the other as "01".
Then, for a 3x3 forest, his moves would range from
South->South->East->East to East->East->South->South: "0011" to
"1100":

min_path = ("1" * (ysize - 1)).to_i(2)
max_path = (("1" * (ysize - 1)) << ("0" * (xsize - 1))).to_i(2)

Then a brute-force loop through all the possible paths:

min_path.upto(max_path) do |path|
x, y, eats = 0, 0, map[0][0]

begin
path_len.times do |i|
path[i] == 0 ? x += 1 : y += 1
raise if map[x][y] < 0
eats += map[x][y]
end
rescue
end

if eats > best_eats
best_eats = eats
best_path = path
end
end

The first solution I worked on was to use a Ruby Astar implementation
by Marcin Coles (I found this library on rubyforge while I was playing
with the rubyist's wig-wug homework assignment). I had to modify the
stock behavior of the library to fit within the constraints of the
Cookie Monster problem:

* On-disk format of the map was different
* Use -1 instead of 0 to indicate a wall/thorn
* Higher-number locations are preferred

I originally abandoned this because I couldn't understand why it
wasn't eating an optimal number of cookies. After I wrote the above
version, I compared the two and saw they both produced the same path,
but different counts! So, I swapped x and y into the correct
positions on lines 73 and 81. Code excerpt:

require "astar/AMap.rb"

class CookieMonsterAMap < AStar::AMap
# override to munge the costmap array for the constraints of the
cookie monster problem
def initialize(costmap)
#...
end

# override load to return this class instead of the parent AMap class
def self.load(filename)
#...
end

# override to only generate South and East successors
def generate_successor_nodes(anode)
#...
end
end

###################################################
# based on AStar tester by Marcin Coles 27/Sep/2007

amap = CookieMonsterAMap.load(ARGV[0] || "map.txt")
cmap = amap.costmap

start, finish = amap.co_ord(0, 0), amap.co_ord(cmap[0].size - 1, cmap.size - 1)

goal = amap.astar(start, finish)
raise "Lost in forest @_@" unless goal

puts "The path:"
current, cookies = goal, 0
while current.parent do
x, y = current.x, current.y
cookies += amap.original_costmap[y][x]

print "[#{x}, #{y}] <- "
current = current.parent
end
x, y = current.x, current.y
puts "[#{x}, #{y}]"

cookies += amap.original_costmap[y][x]

Output comparison:

178.rb, map 01, Eaten: 1, 0.040u 0.010s 0:00.01
178.rb, map 02, Eaten: 7, 0.050u 0.010s 0:00.09
178.rb, map 03, Eaten: 19, 0.030u 0.010s 0:00.00
178.rb, map 04, Eaten: 23, 0.060u 0.000s 0:00.02
178.rb, map 05, Eaten: 25, 0.080u 0.030s 0:00.14
178.rb, map 06, Eaten: 32, 0.240u 0.020s 0:00.22
178.rb, map 07, Eaten: 40, 0.870u 0.110s 0:01.05
178.rb, map 08, Eaten: 48, 3.630u 0.240s 0:03.95
178.rb, map 09, Eaten: 56, 14.390u 1.090s 0:16.06
178.rb, map 10, Eaten: 60, 57.620u 3.880s 1:01.81
178.rb, map 12, Eaten: 65, 232.480u 14.420s 4:09.59
178.rb, map 12, Eaten: 74, 949.270u 62.310s 17:06.38

178_aster.rb, map01, 1 cookie, 0.040u 0.010s 0:00.03
178_aster.rb, map02, 7 cookies, 0.050u 0.000s 0:00.05
178_aster.rb, map03, 19 cookies, 0.070u 0.000s 0:00.01
178_aster.rb, map04, 23 cookies, 0.060u 0.010s 0:00.04
178_aster.rb, map05, 25 cookies, 0.060u 0.020s 0:00.06
178_aster.rb, map06, 32 cookies, 0.080u 0.010s 0:00.04
178_aster.rb, map07, 40 cookies, 0.080u 0.040s 0:00.09
178_aster.rb, map08, 48 cookies, 0.110u 0.020s 0:00.12
178_aster.rb, map09, 56 cookies, 0.130u 0.030s 0:00.12
178_aster.rb, map10, 60 cookies, 0.170u 0.040s 0:00.20
178_aster.rb, map11, 65 cookies, 0.210u 0.060s 0:00.26
178_aster.rb, map12, 74 cookies, 0.330u 0.050s 0:00.36

(Times are a single run on an OLPC XO.)

Christian Neukirchen

9/28/2008 9:29:00 PM

# A simple recursive solution, not very efficient.
# One could use dynamic programming, similar to what I used in
# http://chneuk.../repos/blogcode/dynprog-h...

@maze = [
[ 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],
]
def @maze.max_x; size - 1; end
def @maze.max_y; map { |x| x.size - 1 }.min; end

def traceback(x, y, steps, score)
if x == 0 && y == 0
[score+@maze[x][y], steps+[[x,y]]]
elsif x < 0 || y < 0 || @maze[x][y] < 0
[-1, steps]
else
[traceback(x-1, y, steps+[[x,y]], score+@maze[x][y]),
traceback(x, y-1, steps+[[x,y]], score+@maze[x][y])
].max
end
end

score, steps = traceback(@maze.max_x, @maze.max_y, [], 0)

puts "Optimal pathway: #{score} cookies."
0.upto(@maze.max_x) { |x|
0.upto(@maze.max_y) { |y|
print steps.include?([x, y]) ? "[#{@maze[x][y]}]" : ("%2d " % @maze[x][y])
}
puts
}

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Holger Mack

9/29/2008 7:16:00 AM

[Note: parts of this message were removed to make it a legal post.]

Hi,

my solution is also a recursive path finding algorithm, but stores
intermediate results. The idea behind the solution is that the best path to
a position is either coming from north or west, depending on whether the
path up to the northern or western square is better, i.e. allows to collect
more cookies. Non crossing can be handled very naturally in this framework.
In order to not calculate the same path over and over again I use a hash to
store optimal paths for each square.

Thank you for this quiz. I learned a lot, especially I never used a hash
with block in this way.

Regards
Holger

# array representing forest
data = [
[ 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]
]

# hash storing [number of cookies, path to this field]
# for each position [x, y]

path = Hash.new do |hash, key|

x, y = key

# 1) outside forest or no crossing
if x<0 || y<0 || data[y][x] == -1 then
hash[key] = [-1, nil]

# 2) Starting Position
elsif key == [0, 0] then
hash[key] = [data[y][x], "."]

# 3) otherwise
else
cookies = data[y][x]

# 3a) cookies and path to the northern field
c_north, p_north = path[[x, y-1]]
# 3b) cookies and path to the western field
c_west, p_west = path[[x-1, y]]

# if both are impossible to reach, this one also is
if !p_north and !p_west then
hash[key] = [-1, nil]

# take the path with more cookies and add s/e step and number of
cookies
elsif c_north > c_west then
hash[key] = [cookies + c_north, p_north+"s"]
else
hash[key] = [cookies + c_west, p_west+"e"]
end
end
end

# print number of cookies and path for the lower right corner
puts path[[11,11]]

James Gray

9/29/2008 10:11:00 PM

On Sep 26, 2008, at 9:53 AM, Matthew Moss wrote:

> ## Cookie Monster (#178)

My simple search:

#!/usr/bin/env ruby -wKU

def search(field, current = {:x => 0, :y => 0, :cookies => field[0]
[0], :path => ""})
%w[E S].map do |direction|
new_best = Marshal.load(Marshal.dump(current))
if direction == "E"
new_best[:x] += 1
next new_best if new_best[:x] >= field.first.length
else
new_best[:y] += 1
next new_best if new_best[:y] >= field.length
end
next new_best if field[new_best[:y]][new_best[:x]] < 0
new_best[:cookies] += field[new_best[:y]][new_best[:x]]
new_best[:path] << direction
search(field, new_best)
end.max { |a, b| a[:cookies] <=> b[:cookies] }
end

puzzle = <<END_PUZZLE
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
END_PUZZLE

require "pp"
pp search(puzzle.map { |row| row.split.map { |n| n.to_i } })

__END__

James Edward Gray II

darren kirby

9/29/2008 10:18:00 PM

quoth the Michal Suchanek:

>
> Also I am wondering: are there only male cookie monsters?
>
> It comes strange to me that the cookie monster is referred to as "he"
> because in my mother tongue monsters are normally female, and you have
> to be more specific when talking about a male monster.
> As for English I thought monsters are normally referred to as "it".

Not 'a' cookie monster, 'Cookie Monster':
http://en.wikipedia.org/wiki/Cook...

> Thanks
>
> Michal

-d
--
darren kirby :: Part of the problem since 1976 :: http://badco...
"...the number of UNIX installations has grown to 10, with more expected..."
- Dennis Ritchie and Ken Thompson, June 1972

ThoML

9/29/2008 10:35:00 PM

> ## Cookie Monster (#178)
>
> _Quiz description provided by Lee Jarvis._
>
> Cookie Monster is trying to walk through the Cookie Forest and consume
> as many cookies as possible.

Has somebody created a big or difficult maze?

Here is my take on this.

Okay, I now realized that my cookie monster is on a diet and tries to
minimize the number of cookies consumed. Oh well. No time to change
that now.

Regards,
Thomas.

#!/usr/bin/env ruby

class CookieMonster
INF = 1.0 / 0

def initialize
@rows = nil
@cols = nil
@maze = []
@graph = Hash.new do |h,k|
h[k] = Hash.new do |i,l|
i[l] = INF
end
end
@path = Hash.new do |h,k|
h[k] = Hash.new do |i,l|
i[l] = [nil, INF]
end
end
end

def read(io=DATA)
top = io.lineno
while !io.eof?
i = io.lineno - top
row = io.readline.strip.split(/\s+/)
@maze << row
row.each_with_index do |w, p|
v = w.to_i
v = INF if v == -1
@path[0][0] = [nil, v] if i == 0 and p == 0
@graph[i][p] = v
end
end
@cols ||= row.size
@rows ||= io.lineno - top + 1
self
end

def walk
0.upto(@rows - 1) do |y|
edges = @graph[y]
0.upto(@cols - 1) do |x|
next if y == 0 and x == 0
weight = edges[x]
_, c0 = @path[y][x-1]
_, c1 = @path[y-1][x]
if c0 < c1
@path[y][x] = [false, c0 + weight]
elsif c1 < INF
@path[y][x] = [true, c1 + weight]
else
@path[y][x] = [false, INF]
end
end
end
self
end

def draw
canvas = []
x0 = @rows - 1
y0 = @cols - 1
y = @maze.size
@maze.reverse.each do |row|
y -= 1

line = []
rest = false
row.each_with_index.to_a.reverse.each do |cell, x|
if rest or x == 0 or x > x0
line.unshift(' %2d' % cell)
else
down, _ = @path[y][x]
if down
x0 = x
rest = true
line.unshift(' %2d' % cell)
else
line.unshift(' _%2d' % cell)
end
end
end
canvas.unshift(line.join)

break if y == 0
line = []
row.each_with_index.to_a.reverse.each do |cell, x|
if x != x0
line.unshift(' ')
else
down, _ = @path[y][x]
line.unshift(down ? ' |' : ' ')
end
end
canvas.unshift(line.join)

end
puts canvas.join("\n")
self
end

end

if __FILE__ == $0
cm = CookieMonster.new
if ARGV.empty?
cm.read.walk.draw
else
ARGV.each do |f|
puts f
File.open(f) do |io|
cm.read(io).walk.draw
end
puts
end
end
end

__END__
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

ThoML

9/30/2008 6:14:00 AM

> Okay, I now realized that my cookie monster is on a diet

An All-you-can-eat-patch:

--- q178a.rb 2008-09-30 08:13:01.357212800 +0200
+++ q178b.rb 2008-09-30 08:11:12.540742400 +0200
@@ -12 +12 @@
- i[l] = INF
+ i[l] = -INF
@@ -17 +17 @@
- i[l] = [nil, INF]
+ i[l] = [nil, -INF]
@@ -30 +30 @@
- v = INF if v == -1
+ v = -INF if v == -1
@@ -48 +48 @@
- if c0 < c1
+ if c0 > c1
@@ -50 +50 @@
- elsif c1 < INF
+ elsif c1 > -INF
@@ -53 +53 @@
- @path[y][x] = [false, INF]
+ @path[y][x] = [false, -INF]

Harry Kakueki

9/30/2008 6:54:00 AM

>
> 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:
>

Here is my solution.
It only works for square forests.
It finds and stores every possible path then outputs the best one.
So, it is not very fast ( about 30 sec. ).
But it is short and (hopefully) easy to read.

str = <<DATA
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
DATA

forest, choices, paths = [],[],[]
str.each {|x| forest << x.strip.split(/\s+/).map{|x| x.to_i}}
top = forest[0].length - 1
nums = (0..top).map {Array.new}
(0...2**top).each do |x|
nums[x.to_s(2).split(//).map{|f| f.to_i}.inject{|a,b| a+b}] <<
x.to_s(2).rjust(top,"0")
end

(0..top).each{|x| nums[x].each{|y| nums[top-x].each{|z| choices << (y+z)}}}

choices.each do |a|
trypath = []
south,east = 0,0
trypath << forest[south][east]
a.split(//).each do |c|
south += 1 if c == "0"
east += 1 if c == "1"
trypath << forest[south][east]
break if forest[south][east] == -1
end
paths << trypath unless trypath.include?(-1)
end

p paths.max{|x,y| x.inject{|a,b| a+b} <=> y.inject{|a,b| a+b} }

Harry

--
A Look into Japanese Ruby List in English
http://www.kakueki.com/ruby...

Matthew Moss

10/2/2008 2:13:00 PM

Summary coming tomorrow.

comp.lang.ruby

[QUIZ] Cookie Monster (#178

Matthew Moss

Jesús Gabriel y Galán

brabuhr

Christian Neukirchen

Holger Mack

James Gray

darren kirby

ThoML

ThoML

Harry Kakueki

Matthew Moss

x Login to ForumsZone