def extract_die(xdyz)
  grps = xdyz.split(/\+|-/)

  grps_spl = grps.first.split('d')
  x = grps_spl.first.to_f
  y = grps_spl.last.to_f

  z = 0

  if grps.size == 2
    z = grps.last.to_f
    if xdyz.include? '-'
      z = z * -1.0
    end
  end

  return x, y, z
end

# n choose k
def combinations(n, k)
  n = n.to_i
  k = k.to_i
  return 1 if k == 0 or k == n
  (k + 1 .. n).reduce(:*) / (1 .. n - k).reduce(:*)
end

# Summation to find likelihood of total score points from n rolls of an s-sided die
# Uspensky, J. V. Introduction to Mathematical Probability. New York: McGraw-Hill, pp. 23-24, 1937.
def total_score_probability(points,n,s)
  sum_start = 0
  sum_end = ((points-n)/s.to_f).floor

  summation = (sum_start..sum_end).map{|k|
    term1 = (-1) ** k
    term2 = combinations(n, k)
    term3 = combinations((points - s*k - 1), (n-1))
    term1*term2*term3
  }.inject(:+)

  summation * (1/(s**n))
end


def calculate_chance(xdyz, zombie_health)
  x, y, z = extract_die xdyz

  min_score = zombie_health - z
  max_score = x * y

  begin
    chance = (min_score.to_i..max_score.to_i).map{ |points|
      total_score_probability(points, x, y)
    }.inject(:+).round(6)

    sprintf("%.6f", chance)
  rescue
    nil
  end
end

lines = File.open('actual_problem.txt').readlines.map(&:chomp)
zombie_count = lines[0]
zombies = lines[1..-1].each_slice(2).to_a
zombies.each_with_index do |zombie, idx|
  case_number = idx + 1
  zombie_health = zombie.first.split(' ').first.to_f
  dice = zombie.last.split(' ')
  chance = dice.map {|xdyz|
    calculate_chance xdyz, zombie_health
  }.reject(&:nil?).max
  if chance.empty?
    chance = "0.000000"
  end
  puts "Case ##{case_number}: #{chance}"
end

But I messed up.

My code took too long to run. It finished running in about five and minutes. Initially, I made the mistake of outputting nil instead of "0.000000" for the case where chance.zero?. I didn't think through all the edge cases! And I got zero points because there was malformatting in my output!

A mistake was made, but definitely confirming my suspicions that this was simply a tool of the recruiting process.

Let it be known: I have the utmost respect for developers who can code perfect solutions, thinking through each edge case. Interviewing is certainly a skill in of itself, straightforwardly improvable through solving coder challenges like the Facebook Hacker Cup and TopCoder. I've dedicated myself to the slow mastery of this craft. Until I am invited with open arms into the dojos of Facebook, Amazon or Alphabet/Google, I (out of necessity) prefer consulting to make more money as developer.

And if I wanted to win the challenge (being honest with myself, of course I did!), I would have been wise to warm up with the easier problems.

There's room to improve

Facebook's official solutions: https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-qualification-round-solutions/1593063774042851

Optimizing my solutions,...

For example, you code use the parallel gem to speed up performance.

zombie_chances = Parallel.map(zombies) do |zombie|
  zombie_health = zombie.first.split(' ').first.to_f
  dice = zombie.last.split(' ')
  chance = dice.map {|xdyz|
    calculate_chance xdyz, zombie_health
  }.reject(&:nil?).max
  if chance.nil?
    chance = "0.000000"
  end
  chance
end
zombie_chances.each_with_index do |chance, case_number|
  puts "Case ##{case_number + 1}: #{chance}"
end
            

You could improve by writing an n-choose-k extension in C. I haven't written a Ruby extension in C yet, but I feel like it is coming up in my journey as a developer. For me, it would be pragmatic instead to memoize the combinations and total_score_probability methods.

It also makes sense running the code on a DigitalOcean droplet. It will cost you less than $1 to rent a box — with 64GB memory & 20 core processors — for an hour. You can even choose to deploy an image with ruby already installed. If you want to sign up for the DigitalOcean cloud, use my referral link here in order to get a $10 credit. I'll also get a credit, allaying my $200+ monthly personal server habit.

Anyway, thanks for reading. The efforts writing the blog post were conducted in service of the below advertisement. Additionally to the DigitalOcean referral link, there are also Amazon affiliate links embedded.