Solution to the XKCD cartoon (http://xkcd.com/287/) NP-Complete.

README.md

I beefed an interview with AirBNB last week when my interviewee asked me to solve the NP-Complete problem described in this XKCD comic.

I got in my head almost immediately and got lost trying to design a recursive solution - instead attempting to iterate over the possibilities and then sub-iterate over a smaller set while keeping track of price.

Clear of the interview by a few days (and with a rejection letter in the inbox 😎) I wanted to try the problem again - starting from the very basic question: what are all the possible combinations of a N lengthed array of i length?

In the simplest form - how many 3-letter combinations can be produced from ['a', 'b', 'c']?

def possibilities(options, steps, prefix=nil)
  combos = []
  options.each do |option|
    option = prefix + option if prefix
    if steps > 1
      combos.concat(possibilities(options, steps - 1, option))
    else
      combos << option
    end
  end
  combos
end

p possibilities(['a', 'b', 'c'], 3)

which outputs:

["aaa", "aab", "aac", "abb", "abc", "acc", "bbb", "bbc", "bcc", "ccc"]

Then I rewrote the possibilities method to concatenate arrays - not strings:

def possibilities(options, steps, prefix=nil)
  combos = []
  options.each do |option|
    option = [prefix, option].flatten if prefix
    if steps > 1
      combos.concat(possibilities(options, steps - 1, option))
    else
      combos << option
    end
  end
  combos
end

p possibilities(['a', 'b', 'c'], 3)

leading to:

[["a", "a", "a"], ["a", "a", "b"], ["a", "a", "c"], ["a", "b", "a"], ["a", "b", "b"], ["a", "b", "c"], ["a", "c", "a"], ["a", "c", "b"], ["a", "c", "c"], ["b", "a", "a"], ["b", "a", "b"], ["b", "a", "c"], ["b", "b", "a"], ["b", "b", "b"], ["b", "b", "c"], ["b", "c", "a"], ["b", "c", "b"], ["b", "c", "c"], ["c", "a", "a"], ["c", "a", "b"], ["c", "a", "c"], ["c", "b", "a"], ["c", "b", "b"], ["c", "b", "c"], ["c", "c", "a"], ["c", "c", "b"], ["c", "c", "c"]]

Before moving back to the actual XKCD problem - there are definitely some inefficiencies in this approach, see how the above ouput has both ["a", "c", "c"] and ["c", "c", "a"]. One way to improve the iteration would be to pass in the growing finished combos array into the recursive steps and check whether that particular combination already exists in the array - and to skip it.

Ruby enumerable's inject method is great for this - as it accepts a an initial argument. Rewriting my method to use inject it looked like this:

def possibilities(options, steps, progress=[], prefix=nil)
  options.inject(progress) do |progress, option|
    option = [prefix, option].flatten if prefix
    if steps > 1
      progress = possibilities(options, steps - 1, progress, option)
    else
      progress << option
    end
    progress
  end
end

The two big changes: the parent's array is replaced (not concatenated) with the recursive functions results - and both functions now accept an argument for the progress (defaulting to an empty array if not set).

I could then proceed to improving the function by removing duplicates by standardizing the format of the sub-elements (by sorting) and then only adding new elements:

def possibilities(options, steps, progress=[], prefix=nil)
  options.inject(progress) do |progress, option|
    option = [prefix, option].flatten.sort if prefix
    if steps > 1
      progress = possibilities(options, steps - 1, progress, option)
    else
      progress << option unless progress.index option
    end
    progress
  end
end

Which produces the much more concise:

[["a", "a", "a"], ["a", "a", "b"], ["a", "a", "c"], ["a", "b", "b"], ["a", "b", "c"], ["a", "c", "c"], ["b", "b", "b"], ["b", "b", "c"], ["b", "c", "c"], ["c", "c", "c"]]

This can then be partially applied to the XKCD's problem set:

options = {
  mixed_fruit: 215,
  french_fries: 275,
  side_salad: 335,
  hot_wings: 355,
  mozzarella_sticks: 420,
  sampler_plate: 580
}

def possibilities(options, steps, progress=[], prefix=nil)
  options.inject(progress) do |progress, option|
    option = [prefix, option].flatten.sort if prefix
    if steps > 1
      progress = possibilities(options, steps - 1, progress, option)
    else
      progress << option unless progress.index option
    end
    progress
  end
end

p possibilities(options.keys, 7).count

Will generate any N possible combinations for the given menu. And I can guess there'll never be more than seven items in an order - because the smallest order (mixed_fruit is $2.15 - so at most there are seven mixed_fruit in an order).

In fact we can simplify this to:

budget = 1505
least_priced = options.values.sort.first
combos = possibilities(options.keys, budget / least_priced)
p combos.select do |combo|
  combo.inject(0) { |sum, item| options[item] + sum } == budget
end

But you'll notice this still takes a lot of time and intuitively I know that I'm still generating possibilities like [:sampler_plate, :sampler_plate, :sampler_plate, :sampler_plate, :sampler_plate, :sampler_plate, :sampler_plate] which costs $40.60 - so I'm wasting time on combinations that violate the conditions of the problem. To improve on the efficiency you can move the price calculation into the recursive possibilities function (instead of using step).

np_complete.rb

options = {
  mixed_fruit: 215,
  french_fries: 275,
  side_salad: 335,
  hot_wings: 355,
  mozzarella_sticks: 420,
  sampler_plate: 580
}

def possibilities(options, budget, progress=[], prefix=nil)
  options.keys.inject(progress) do |combo, option|
    price = options[option]
    option = [prefix, option].flatten.sort if prefix
    if budget - price > 0
      combo = possibilities(options, budget - price, combo, option)
    else
      combo << option unless combo.index option
    end
    combo
  end
end

def print_answer(combos, options, justify)
  puts '-'.rjust(justify, '-')
  combos.each do |combo|
    total = 0
    combo.each do |item|
      total += options[item]
      puts "#{item}: $#{sprintf('%.2f',options[item]/100.0)}".rjust(justify)
    end
    puts "TOTAL: $#{sprintf('%.2f', total/100.0)}".rjust(justify)
    puts '-'.rjust(justify, '-')
  end
end

def price_out(options, budget)
  least_expensive = options.values.sort.first

  combos = possibilities(options, budget)
  print_answer(combos.select do |combo|
    sum = combo.inject(0) { |sum, item| sum + options[item] }
    sum == 1505
  end, options, 25)
end

price_out(options, 1505)

output.txt

$ ruby np_complete.rb
-------------------------
       mixed_fruit: $2.15
       mixed_fruit: $2.15
       mixed_fruit: $2.15
       mixed_fruit: $2.15
       mixed_fruit: $2.15
       mixed_fruit: $2.15
       mixed_fruit: $2.15
            TOTAL: $15.05
-------------------------
         hot_wings: $3.55
         hot_wings: $3.55
       mixed_fruit: $2.15
     sampler_plate: $5.80
            TOTAL: $15.05
-------------------------

you might enjoy this, my solution to the same problem, also presented as a code challenge in an interview

https://github.com/stephancom/xkcd-287