[QUIZ] Cookie Monster (#178)

[Matthew Moss]

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

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/rubyquiz/>.

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

 

[Jesús Gabriel y Galán]

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
## 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[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.length - 1).downto(0) do |j|
#skip the -1 so they don't get updated
next if field[j][0] == -1
dest = get_possible_destinations(field,i,j)
unless dest.empty?
add = dest.max {|x,y| x[0] <=> y[0]}
field[j][0] += add[0]
field[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[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[j]
path = []
until current[1].nil?
path << current[1]
current[1] == :E ? j += 1 : i += 1
current = field[j]
end
puts path.join(",")



Thanks for the quiz.

Jesus.

 

[brabuhr]

## 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/master/178

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 == 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.)

 

[Holger Mack]

[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]

## Cookie Monster (#178)

My simple search:

#!/usr/bin/env ruby -wKU

def search(field, current = {:x => 0, :y => 0, :cookies => field[0]
[0], ath => ""})
%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[ath] << 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]

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/Cookie_Monster

Thanks

Michal

-d

 

[toomln]

## 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[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

 

[toomln]

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]

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

 

[Matthew Moss]

Summary coming tomorrow.

 

[Redd Vinylene]

Summary coming tomorrow.

I've tried contacting you many times now, is there any particular
reason why you won't respond?

 

[Matthew Moss]

I've tried contacting you many times now, is there any particular
reason why you won't respond?

You sent me email once, not many times... once.

It was a rubyquiz suggestion. Do you have a particular question about
it?

 

[Matthew Moss]

My apologies, that was supposed to be sent in email, not to the list.
Redd, if you have any specific questions, please send them to me in
email, not here.

 

[Robert Dober]

My apologies, that was supposed to be sent in email, not to the list.
Redd, if you have any specific questions, please send them to me in
email, not here.

Actually I see this more as an opportunity to clear things up for
others too. I too was slightly disappointed when you did not reply to
my quiz suggestion.
But than it was a pleasant surprise when you featured the quiz,
although it was not a great success .
Anyway you are doing a great job here and I feel OP should understand
that your time is limited. I guess you are aware that people would
like having answers to their mails and therefore I concluded that you
just had no time to reply, such is life .

Keep the good work up.

Cheers
Robert

--=20
C'est v=E9ritablement utile puisque c'est joli.

Antoine de Saint Exup=E9ry

 

[Matthew Moss]

Anyway you are doing a great job here and I feel OP should understand
that your time is limited. =A0I guess you are aware that people would
like having answers to their mails and therefore I concluded that you
just had no time to reply, such is life .

There have been some quite significant, personal changes in my life in
the last few months. As y'all have seen, there have been a number of
weeks where I've been unable to quiz you. (In fact, as I mention in
the summary just posted, there will be no quiz tomorrow.)

Along with those changes has been a fair amount of business,
disorganization and distraction by more important things. I've even
had to evaluate a couple times whether I could continue doing this,
though I do think I can at the current time.

So while I've glanced at all the quiz suggestions, I do need to go
back over then and get in touch with each of the authors to flesh out
those quizzes. It's not my usual habit to reply to messages (of any
sort) unless I have something to say... so I apologize to anyone who
was expecting a message back, even if just to say "I got your
message." I'll try to do that from now on.

Keep the good work up.

Thanks!