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.
Here's the problem statement. I took a screenshot using the awesome FireShot chrome extension.
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"?
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:
.+https://www.google.com/search\?sourceid=.+ie=UTF-8&q=(.+)&oq=.+
**SEARCH:$1
^((?!\*\*SEARCH).)*$
(leave it blank)Recapping the research process, the steps were:
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.
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.
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.
Download the free article on Legal Ideas for software development, and then join our mailing list.
Get our articles on "Finding Clients" and "Communication" for free.