"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__