 Fighting the Zombie: Solving Facebook Hacker Cup 2017 Qualification Round, Problem 3

## Fighting the Zombie

### Solving the Facebook Hacker Cup 2017 Qualification Round, Problem 3 Zombies! This is from Zombieland, starring Jesse Eisenberg, who also happened to play Mark Zuckerberg in The Social Network

### How it all began

It was Friday night. I checked my email and saw that the Facebook Hacker Cup had started. It was late at night, I had tons of more important priorities, the Facebook HC felt like it was probably mostly a recruiting ploy, and yet... I wanted to play.

After checking out the problems, I decided to start with the hardest problem because it was worth the most points.

### Problem statement

Here's the problem statement. I took a screenshot using the awesome FireShot chrome extension. ### Breaking it down

This felt an awful lot like school, confirming my suspicions that it was mostly a recruiting ploy. First off, it was a word problem, which reminded me of standardized tests. And in undergrad, I took a lot of math, and this felt an awful lot like a math problem.

The essence of the problem is: "how do you find the likelihood of the total value of n-rolls of s-sided dice to meet or exceed some number of points, p"?

### So what was the problem solving process

When I was in high school, we had this club called the Friends of Millard Fillmore, its name a nod to an obscure American president. The point of the club was doing a research scavenger hunt: we were given esoteric questions and we had to provide solutions that were backed up by primary or secondary sources. By senior year, I was the co-captain. One of the major life lessons I learned there (other than how to support teammates) was be persistent with research – the more ways I could think to frame or rephrase my question or possible answers, the more likely I could comb through the results in pursuit of meaningful information yield.

Here are the searches I tried, in chronological order.

```dnd get expected value of die
dice probability uby
dnd expected value of die
convert expected value to likelihood of
expected value probability density ruby
Bernoulli outcomes ruby
dnd probability of a die exceeding
cumulative distribution function
get distribution of die
dnd hit pobability fomrula
dnd statistics
pobability of n-sided die exceeding value
probability of dnd die rolls  or higher
closed form dnd probability
binomial distrirbution calculator
probability of getting at least die rolls
probability total dice rolls
expand generating function
summing coefficients
generating functions in ruby
get expanded form of dice probability
ruby symbolic math
generating function closed form coefficient
coefficient die generating function
extract coefficient generating function
generating function probability
get coefficients fom geneating function
mathematica generating functions
dice geneating function mathematics
seriescoefficient
python generating function coefficients
generating form dice closed form
Uspensky dice
```

I also did lots of navigating through suggested StackExchange questions, especially on the math & stats forums

By the way, to harvest my search history, I did an export Chrome history using instructions here to get my history into JSON.

Then, I cleaned it up using Sublime Text:

1. I manually found the first mention of Hacker Cup and deleted all text below
2. Then I did a find and replace to add an identifier to all search queries:

Find What:
``.+https://www.google.com/search\?sourceid=.+ie=UTF-8&q=(.+)&oq=.+``

Replace With:
``**SEARCH:\$1``

3. Then I deleted all lines not starting with **SEARCH:

Find What:
``^((?!\*\*SEARCH).)*\$``

Replace With:
(leave it blank)

4. Then I did a "unique lines" permute:

Edit ▲Permute Lines ▲ Unique

and then a "reverse lines" to get it in chronological order:

Edit ▲Permute Lines ▲ Reverse

Recapping the research process, the steps were:

1. Re-learn that adding the coefficients from the generating function of a die roll could be used to estimate probabilities.
2. Find the closed-form solution, because in math, some advanced genius has figured out a closed form solution for almost everything. It's one of the most beautiful things about mathematics. I ultimately found it on the Wolfram MathWorld dice page, who got it from
``Uspensky, J. V. Introduction to Mathematical Probability. New York: McGraw-Hill, pp. 23-24, 1937.`` Anyway, this formula tells you "the probability of obtaining p points (a roll of p) on n s-sided dice".

Therefore, remembering my discrete math, I would just have to sum all of the probabilities from that of the minimum damage value to that of the maximum obtainable points from rolling n s-sided dice.

3. Translate into Ruby

### Here's the code.

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

zombie_count = lines
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

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.   