OMG WTF BBQ!

On 6/27/06, Daniel Martin <martin / snowplow.org> wrote:
> "Matthew Moss" <matthew.moss.coder / gmail.com> writes:
>
> > (You'll also see people here going the opposite route, to make it as
> > fast as possible no holds bars...  both are optimization problems.)
>
> I'm now tempted to /really/ go the opposite route, and make the
> calculation as painfully slow as possible, and use up gobs of memory
> while I'm at it.
>
> Something like this monstrosity.
>
> It's not just expensive memory-wise, creating temporary two-element
> arrays all over the place, and pre-filling the hash with a load of
> different singleton objects, it's also expensive CPU-wise: the code
> depends on a slew of callcc invocations, which are slow to begin with
> and to top that the algorithm itself is fundamentally O(n*2^n), so will
> take ages on even the fastest hardware.
>
> On my fast machine, I really didn't want to run this for more than 20
> rows.  I'm not letting this code anywhere near my slow machine.
>
> $ time ruby painful_ppt.rb 20 > /dev/null
>
> real    0m54.559s
> user    0m53.421s
> sys     0m0.921s
>
> For comparison, on the same machine my second solution gives these times:
>
> $ time ruby ppt.rb 1000 > /dev/null
>
> real    0m27.440s
> user    0m25.186s
> sys     0m2.171s
>
> Despite its usefulness as an example of how NOT to program, though, I
> do think that this code illustrates a nice feature of Pascal's
> triangle: namely, that the number at any spot represents the number of
> paths to that spot from the top point in the triangle, if you only
> move down-and-right or down-and-left.
>
> ================ painful_ppt.rb ===============
> #!ruby
>
> $coin_spots = []
>
> # This function returns true the first time, but sets
> # things up so that reflip causes it to return false
> # to the same spot in the program.
> def flip_coin
>   # does amb(true,false), but without all the machinery
>   callcc { |c|
>     $coin_spots.push(c)
>     return true
>   }
>   false
> end
>
> # Go back to the last time flip_coin returned true, and
> # make it return false this time.
> def reflip
>   $coin_spots.pop.call
> end
>
> def pp_pascal(n)
>   ptri = {}
>   n.times { |p|
>     (2*n - 1).times { |q|
>       g = Object.new
>       class << g
>         def coerce(o); 0.coerce(o); end
>         def +(o); o; end
>         def to_s; ""; end
>         def inspect; "g"; end
>       end
>       ptri[[p,q]] = g
>     }
>   }
>   # So now ptri has this grid of "g" objects, from
>   # [(0 ... n), (0 ... 2*n-1)]
>   # now walk down the triangle, starting at [0,n-1] and
>   # at each step flipping a coin to either increase or decrease
>   # the "q" coordinate.
>   if flip_coin then
>     (0 ... n).inject(n-1){ |q,p|
>       ptri[[p,q]] = ptri[[p,q]]+1
>       q + (flip_coin ? 1 : -1)
>     }
>     reflip
>   else
>     width = (ptri[[n-1,n-1]]+ptri[[n-1,n]]).to_s.length
>     fmt = ["%#{width}s"] * 2 * n
>     fmt.pop
>     fmt[0] = "%1s"
>     fmt[-1] = "%s"
>     n.times { |p|
>       pascal_row = (0 ... fmt.size).map{|q| ptri[[p,q]]}
>       pascal_row.zip(fmt){|v,f| print(f%v)}
>       puts ""
>     }
>   end
> end
>
> if __FILE__ == $0
>   n = 4
>   n = ARGV[0].to_i if ARGV[0]
>   pp_pascal(n)
> end
>
> __END__
>
>