Perplex City - We Love Puzzles

One thing you might have missed -- I almost did -- is that the digits can be in any order, despite them appearing in numeric order in all of the examples. (So the answer isn't 211, if that's what you were going for.)

Rather than going for a systematic processing of all possible digit, +/- combinations, I tried randomly allocating them.

An equal weighting of concatenate (33% of times), add (33%) and subtract (33%) is fine for finding the solutions for the smaller numbers, but it takes increasingly longer for larger numbers. I therefore changed the weighting to favour concatenate (80%) over addition (10%) and subtraction (10%). This gives a high probability of finding the solution within a relatively short amount of time (about 5 minutes of computing time on my machine).

9876543211

19960

when you test the correct answer you have to try every possible sequence of digits with every combination of +,-,concat. Because of this, I wrote my program (in bash script) to go throught them all in order logging each result to a file then sort them to find the smallest missing number.

Firstly, I worked out, on paper, all the unique combinations of the way the numbers could be concatenated ie

10
9 1
8 2
8 1 1
.
.
.
1 1 1 1 1 1 1 1 1 1

Then I eliminated from this list all those combination that looked like they would produce too high an answer, these being all those that started with 6 or higher, other then the [6 4] combination

This left the combinations

[6,4],
[5,5],
[5,4,1],
[5,3,2],
[5,3,1,1],
[5,2,2,1],
[5,2,1,1,1],
[5,1,1,1,1,1],
[4,4,2],
[4,4,1,1],
[4,3,3],
[4,3,2,1],
[4,3,1,1,1],
[4,2,2,2],
[4,2,2,1,1],
[4,2,1,1,1,1],
[4,1,1,1,1,1,1],
[3,3,3,1],
[3,3,2,2],
[3,3,2,1,1],
[3,3,1,1,1,1],
[3,2,2,2,1],
[3,2,2,1,1,1],
[3,2,1,1,1,1,1],
[3,1,1,1,1,1,1,1],
[2,2,2,2,2],
[2,2,2,2,1,1],
[2,2,2,1,1,1,1],
[2,2,1,1,1,1,1,1],
[2,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1]

Then I looped through each of the combinations of the 10 digits (all 10! of them), and applied each of the formats to each of the combinations, according to the following high level logic

for each permutation of numbers
...for each combination
......if max poss value of perm/comb > current max
.........compute & store all variations of +/-
......end
......if new max > old max
.........print out newly found numbers
.........delete combinations that can't produce a higher max than currently found
......end
...end
end

Thats about it really, the rest is in the detail of the implementation