Facebook Careers Puzzle—usrbincrash solution in Ruby

From Facebook’s Job Puzzles page:

You are on a cargo plane full of commercial goods when the pilot announces that the plane is short on fuel. Unless cargo is ejected from the plane, you will run out of fuel and crash. The pilot provides you with the number of pounds of weight that must be ejected from the plane. Fortunately, the manifest of the plane is both completely accurate, digitized, and you are a programmer of some repute. Unfortunately, your boss is going to be extremely unhappy, and wants you to exactly minimize the losses to the absolute minimum possible without crashing the plane. The manifest does not contain the exact quantities of every type of good, because you have so many on board. You may assume that you will not run out of any good in the course of saving the plane. You also realize this kind of program could be handy to others who find themselves in similar situations.

Write a program that takes a single argument on the command line. This argument must be a file name, which contains the input data. The program should output to standard out the minimum losses your boss will incur from your ejection of goods (see below). Your program will be tested against several manifests of several crashing planes; each with different data. Additionally, your program must be fast, and give the correct answer.

This puzzle is interesting in that there are many ways to approach it. It’s a modified Knapsack problem: we are trying to go over a certain weight while minimizing the cost. There is no limit to how many times each object can be used, making the problem easier in terms of complexity.

I originally solved it very quickly using a naive recursive approach. While correct, it was very inefficient and would blow the stack when any large weight was used as input, even if the problem was easy.

My final solution used the following algorithm:

• Sort objects by weight/cost, higher ratios (most efficient) first.
• Delete objects that will never be used, which are those that are less efficient and weigh more than a more efficient object.
• Keep using the most efficient object until you equal or go over the target weight. If you hit it spot on, return the cost.
• If you go over, subtract the weight and recursively repeat the step above with the next most efficient object to determine if less cost can be achieved.

The following solution in Ruby passed the Facebook puzzle robot:

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

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

# From memoize gem
def memoize(name)
 cache = {}
 (class<<self; self; end).send(:define_method, name) do |*args|
   cache[args] = super unless cache.has_key?(args)
   cache[args]
 end
 cache
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

# Recursive is clean but blows stack on large inputs!
def optimize(weight)
  return 0 if weight <= 0

  best = nil
  $items.each do |item|
    c = optimize(weight - item.weight) + item.cost
    best = c if best.nil? || c < best
  end
  best
end
memoize :optimize

# Finally, something that works, somewhat ugly though =\
def optimize3(weight, cost=0, items = $items)
  return cost if weight <= 0 || items.empty?
  # puts "#{weight}\t#{cost}\t#{items.collect{|i| i.weight}.join(' ')}"
  same_ratio = items.find_all { |i| i.ratio == items[0].ratio }
  global_best = nil
  same_ratio.size.times do |x|
    if weight % items[x].weight == 0
      return items[x].cost * (weight / items[x].weight) + cost
    end

    best = (x == 0) ? items[x].cost * (weight / items[x].weight + 1) + cost : nil

    (items - [items[x]]).each do |item|
      if x == 0
        c = optimize3(weight % items[x].weight, items[x].cost * (weight / items[x].weight) + cost, items - [items[x]])
      else
        c = optimize3(weight - items[x].weight, items[x].cost + cost, items)
      end
      best = c if (best.nil? || c < best)
    end
    global_best = best if best && (global_best.nil? || best < global_best)
  end
  global_best
end
memoize :optimize3

total_weight = input.gets.to_i

# Populate items array
Item = Struct.new(:weight, :cost, :ratio)
while line = input.gets do
  break if line.empty?
  item, weight, cost = line.split(/\s+/)
  $items << Item.new(weight.to_i, cost.to_i, weight.to_f / cost.to_f)
end
$items = $items.sort_by { |i| [i.ratio, i.weight] }.reverse # Larger ratios first

# Some pruning of redundant items
$items.each do |b|
  $items.delete_if { |i| i.weight > b.weight && i.ratio < b.ratio }
end

puts "#{optimize3(total_weight)}\n"