This week the #puzzle is: Can You Take the Heat? #combinatorics #coding #recursion

In the YouTube show, “Hot Ones,” guests answer interview questions while consuming 10 hot sauces, one at a time, ranked in increasing spiciness from 1 to 10.

You have been invited on as a guest and want to prepare for the show. However, you don’t feel like purchasing all 10 sauces in advance. Your plan is to purchase fewer sauces, and then to combine sauces together for any you are missing. For example, if you are missing sauce #7, then you can instead simultaneously consume sauces #3 and #4, since 3 + 4 = 7. (I know the spiciness of the sauces isn’t linear, but for the purposes of this puzzle, let’s assume it is.)

After some pencil-and-paper scratch work, you realize you only need four spices.

… for how many sets of four spice numbers is it possible to generate all the numbers from 1 to 10 using each spice at most once?

And for extra credit:

You’re prepping for a new show, “Hotter Ones,” which has spices ranked from 1 to 100. Let N be the minimum number of spices needed to generate all the numbers from 1 to 100.

For how many sets of N spice numbers is it possible to generate all the numbers from 1 to 100 using each spice at most once? (Note that I am not asking for the value of N; that’s just something you’ll need to figure out en route to your answer.)

Can You Take the Heat?

Highlight to reveal (possibly incorrect) solution:

Program

First a note. No, this isn’t just the “how many different kinds of coins do you need for paying all amounts of money”, as a coin can be used more than one time. No, this isn’t just the “how many weights do you need for weighing all weights”, as that is done on a scale and a weight can be used to subtract from the total.

Thankfully it’s related to these problems, so they got me thinking in the right way.

How many sauces (or chilis) needed to get all strengths 1-10? ⌈log₂(10)⌉ = 4. It might be the chilis 1, 2, 4 and 8.

Recursion is a beautiful way to look at the problem. To begin with, we need chili 1, otherwise we can’t get to a (combined) strength of 1. Likewise, we need chili 2, otherwise we can’t get to a (combined) strength of 2. (1 + 1 isn’t allowed.) With chilis 1 and 2, we have access to combined strengths 1, 2 and 3 (and 0 — no chilis).

• Choice A1: skip chili 3 and go straight to chili 4.
  • Choice B1: skip chili 4 and go straight to chili 5.
    • …
  • Choice B2: add chili 4.
    • Choice C1: skip chili 5 and go straight to chili 6.
      • …
    • Choice C2: add chili 5.
      • …
• Choice A2: add chili 3.
  • Choice B1: skip chili 4 and go straight to chili 5.
    • …
  • Choice B2: add chili 4.
    • Choice C1: skip chili 5 and go straight to chili 6.
      • …
    • Choice C2: add chili 5.
      • …

The next step is to try adding chili 3. (A2.) With chilis 1, 2 and 3, we have access to strengths 1, 2, 3, 4, 5 and 6 (and 0). We already had access to 0-3. Now we also have access to 0+3 (actually we already had that one), 1+3, 2+3 and 3+3. The recursion bit is to then go on to try adding chili 4. (A2B2.)

The alternative to adding chili 3 is not to do it. (A1.) We then again try adding chili 4. (A1B2.) Or not. (A1B1.)

This is what I do in my program. When I have a bunch of chilis giving me all the strengths 1-10, I count it.

Result: 8.

And for extra credit:

Update program to use 100 chilis instead.

Result: 1014.