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