challenges

commit c15792675fc786490972c8339aad85604e2ed8c0
parent f584873f4cf647ee365893af4a749dff0a396f21
Author: Ryan Wolf <rwolf@borderstylo.com>
Date:   Sun, 27 Feb 2011 23:40:44 -0800

completed hyperpublic challenge

Diffstat:
M
hyperpublic/README.md
 | 
11
++++++++++-
A
hyperpublic/challenge2.lua
 | 
33
+++++++++++++++++++++++++++++++++

2 files changed, 43 insertions(+), 1 deletion(-)
diff --git a/hyperpublic/README.md b/hyperpublic/README.md
@@ -17,7 +17,6 @@
      OOOX
      OOOO
      OOOO
-          
 
     Use the input file here to determine what the highest influence score is among 100 random Hyperpublic users. To compute the answer to problem 1, append the top 3 influence totals together in descending order. (For example if they are 17, 5, and 3 then submit 1753)
 
@@ -40,3 +39,13 @@
     Amazingly, they've all accomplished these totals in the minimum number of tasks possible in order to reach each amount. For example, if their total was 6 points they would have accomplished this in just 2 tasks (2 "Add Thing" tasks), as opposed to accomplishing it by 3 "Add Place" tasks. Your job is to compute how many total tasks each user has completed. After you've done so, find the answer to Problem 2 using the following formula:
 
     Problem 2 Answer = Doug's total tasks * Jordan's total tasks * Eric's total tasks * Jonathan's total tasks
+
+    Congratulations. You are web-scale!
+
+    You've successfully completed the Hyperpublic Programming Challenge. Awesome!
+
+    Here's your completion token: XXXXXXXX Email it to us!
+
+    Email your completion token to challenge@hyperpublic.com, along with any code you've written to help solve the challenge, and you'll be entered in the prize raffle to take place on Monday, February 28.
+
+    Hyperpublic is working on big problems around local data capture, search, indexing, and classification, and we're always looking for great hackers to bounce ideas off of. If you're interested in free office space and/or hearing more about Hyperpublic, let us know in your email.
diff --git a/hyperpublic/challenge2.lua b/hyperpublic/challenge2.lua
@@ -0,0 +1,33 @@
+#!/usr/bin/lua
+
+denoms = {98, 42, 23, 17, 3, 2}
+
+opt = {}
+
+function min (n)
+  opt[n] = math.huge
+  for i,denom in ipairs(denoms) do
+    if denom == n then
+      opt[n] = 1
+      return
+    end
+    if (denom < n) and opt[n - denom] then
+      soln = opt[n - denom] + 1
+      if soln < opt[n] then opt[n] = soln end
+    end
+  end
+end
+
+for i=2,2349 do
+  min(i)
+end
+
+answer = 1
+
+for i,points in ipairs({2349, 2102, 2001, 1747}) do
+  t = opt[points]
+  print(t)
+  answer = answer * t
+end
+
+print(answer)