Facebook Careers Puzzle—usrbincrash Revisited

This is a followup to my old solution.

So, I apparently have readers! Thank you for writing and contacting me on numerous occasions. I enjoy discussing and discovering algorithms, so keep them coming.

Many of you have pointed out that my greedy solution doesn’t work, and you’re completely right. Here’s an example I was sent:

    1250
    LJS93K       1300       10500
    A            1200       6000
    J38ZZ9       700        4750
    B            550        3300
    HJ394L       200        3250
    O1IE82       75         10250

    Following your algorithm, it seems to instantly eliminate a necessary
    ingredient for the optimum solution, which to me is one J38ZZ9 and one "B", totaling $8050.

For some reason, I couldn’t figure out the recurrence relationship for dynamic programming by myself until one of you showed it to me. Thanks, now it’s MINE!!!

Anyways, I re-implemented it and like this one better, since it’s optimal, although it does take O(nW) time instead of like, O(n) for my old one. I also implemented the easy GCD optimization and use a different pruning algorithm that works in all cases (while the old one deleted possible candidates, it worked with the greedy algorithm).

The following solution in Ruby passed the Facebook puzzle robot:

(usrbincrash.rb) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#!/usr/bin/ruby
# Usr Bin Crash puzzle
# Kanwei Li, 2009

def gcd(a, b)
  while a != b
    if a > b
      a = a-b
    else
      b = b-a
    end
  end
  a
end

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

$items = [] # Store array of items as a global so we don't have to pass it around

def optimize(total_weight)
  table = []

  (0...total_weight).each do |cur_weight|
    best = nil
    $items.each_with_index do |item, i|
      c = item.cost
      item_weight = item.weight
      if item_weight <= cur_weight
        c += table[cur_weight - item_weight]
      end
      best = c if best.nil? || c < best
    end
    table[cur_weight] = best
  end

  table[total_weight-1]
end

total_weight = input.gets.to_i

# Populate items array
Item = Struct.new(:weight, :cost)
while line = input.gets do
  break if line.empty?
  item, weight, cost = line.split(/\s+/)
  $items << Item.new(weight.to_i, cost.to_i)
end

# $items.sort! { |a, b| b.weight <=> a.weight }
$items.each do |b|
  $items.delete_if { |i| i.weight < b.weight && (i.weight.to_f / b.weight) * i.cost > b.cost }
end

overall_gcd = gcd($items[0].weight, total_weight)
(1...$items.size).each { |i| overall_gcd = gcd(overall_gcd, $items[i].weight) }

$items.each { |i| i.weight /= overall_gcd }
total_weight /= overall_gcd

puts "#{optimize(total_weight)}\n"
Posted on