[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.)
If you have a solution you'd like to share see the Solutions page for instructions.