Example of dynamic programming problem

coins.coffee

# Simply rounds to four digits
dp = (num) ->
  Math.round(10000*num)/10000

# Calculates empirical probability of 
lazyCheck = (P, k) ->
  RUNS = 500000
  avg = 0
  for i in [1..RUNS]
    heads = P.reduce(((a,c) ->
      a += if Math.random() < c then 1 else 0), 0)
    avg += if heads == k then 1 else 0
  dp avg / RUNS

# Verifies algorithm result
verify = (got, exp) ->
  if Math.abs(got - exp) > 0.01
    throw Error 'Looks like this went wrong!'

# Calculates the probability of tossing k heads out of N coin tosses,
# where N is the number of coins and where coin i has a chance P[i] of
# landing heads.
#
# Returns probability, general algorithmic cost (taps) and algorithm
# cache hits.
findP = (P, k) ->

  cache = P.map -> new Array k
  [taps, hits] = [0,0]

  pOfKCoinsFromI = (k, i) ->

    ++taps # increment taps

    # Logging if 'log' is supplied as argument
    console.log "P (k: #{k},\ti: #{i})" if opt.log and !opt.cache

    rem = P.length - i
    # Early exit if the required heads exceeds the remaining coins.
    return 0 if k > rem or k < 0

    # Work with the cache
    if opt.cache and (hit = cache[i][k])?
      console.log "Cache hit!\tP(k:#{k},\ti:#{i}) =\t#{hit}" if opt.log
      ++hits
      return hit

    # Else recursively calculate the remainder
    switch rem
      when 0 then 0
      when 1 then (if k is 1 then P[i] else 1 - P[i])
      else
        cache[i][k] =
          P[i] * pOfKCoinsFromI((k - 1), (i + 1)) +
          (1 - P[i]) * pOfKCoinsFromI(k, (i + 1))

  p: dp pOfKCoinsFromI k, 0
  hits: hits, taps: taps


# Usage: coffee coin.coffee N k <cache> <log>
# Where N is the number of coins to be flipped, and k is
# the number of coins to take as heads.
args = process.argv[2..]
[N, k, optstrs...] = args.map (a) -> (parseInt a, 10) or a

# Load in options.
# cache  - Will use a cache for reused subproblems
# log    - Will log calls to P(k,i), where k is the number of
#          heads and i is the index inside P from which to calculate.
# verify - Will run a check at the end using empirical data to verify
#          that the algorithm has come out with something sane.
opt = {}
opt[o] = true for o in optstrs

# Generate random probabilities for now, to 2 places.
P = [1..N].map -> dp Math.random()

console.log\
( "Probability of selecting #{k} heads from P[i]s...\n"
, if P.length > 5 then "P = [ #{P[0..2]}... #{P[P.length - 1]} ]" else P )

result = findP P, k
verify result, (lazyCheck P, k) if opt.verify?

console.log """\n
Calculated #{result.p} with algorithm.
Algorithm taps: #{result.taps}, cache hits: #{result.hits}
Percentage of runs that were cache hits: #{(100*result.hits/result.taps).toFixed 2}%
\t"""