[inspired by http://www.dgp.toronto.edu/~flaps/progprobs.html]

Consider these base-10 digits: 123456789. If you insert spaces between them, you get various sequences of numbers:

1 2 3 4 5 6 7 8 9 12 3 4 5 67 8 9 1 2 34 5 6 7 89 12 34 56 78 9 1 23456 78 9 12345 6789 etc.

1) Write a program that generates all possible combinations of those digits.

How many are there?

Now let's insert a maximum of 8 addition or subtraction operators between the numbers, like this:

1+2+3+4+5+6+7-8+9 12-3+4+5-67-8+9 1+2+34+5-6-7-89 12-34+56+78+9 1+23456-78-9 12345+6789 etc.

Notice that those arithmetic expressions equate to different values:

1+2+3+4+5+6+7-8+9 = 29 12-3+4+5-67-8+9 = -48 1+2+34+5-6-7-89 = -60 12-34+56+78+9 = 121 1+23456-78-9 = 23370 12345+6789 = 19134 etc.

2) Write a program that generates all possible expressions in this way.

How many sum to 100?

3) Write a program that finds all such expressions for any sum.

Which sum is the most popular, i.e. has the most expressions?

4) Bonus: We can haz pretty data viz?

Like how about a histogram of the number of expressions with sums from -23456788 to 123456789. (A log scale might help. Maybe binning, too.)

- Michelle Fullwood's solution is an IPython notebook
- Allen Downey's solution is an IPython notebook
- Josh McGrath's solution is hotdate.py

If you have a solution you'd like to share see the Solutions page for instructions.