Hacker News new | ask | show | jobs
by j4cobgarby 797 days ago
the best I can find for [7, 5, 3] is:

7 5 3

7 1 4 3

2 5 1 4 3

2 5 1 7

2 6 7

2 1 5 7

3 5 7

4 comments

What I found:

753 7512 762 7152 34152 3417 357

That's the same as your solution but in reverse.

It's not possible in 4 steps or less, because if you ignore the no-duplicates-rule, there is only 1 possibility and that one has duplicates. It's not possible in 5 steps, because you would not end up with an odd length list again. Solutions will always have an even number of steps. So six must be shortest.

I came to the exact same solution.

My feel for this type of puzzle is that there is a 'gravity' from the higher to lower value integers. So you want to help integers flow from the 7 to the 3. The state of the list then represents a sieve that dynamically restricts the flow paths from one step to the next. So at any time step your possible paths to flow the integers from 7 to 3 are quite restricted.

The first step of 753 -> 7143 may seem arbitrary at first, but you quickly realise that most other options result in long awkward paths where you move integers back and forth, or deadends.

For example, if you decide to split the 7 first your valid moves are 753 -> 6153 or 753 -> 1653. The first move still leaves you overloaded at the left most position, and you still need another split because you cant combine 1+5 or 5+3 due to duplicates or exceeding 7. So you don't really feel closer. Same with 1653, putting you in a position where all combinations exceed 7, and you need to further breakdown numbers, but you've already used up all your valid odd numbers, so you have to break 6 into 2 and 4 -> 12453. This is a dead end.

Fun morning coffee puzzle.

The following should be all the smallest solutions for [7, 5, 3]:

753 7512 34512 3462 34152 3417 357

753 7512 762 7152 34152 3417 357

753 7512 762 3462 34152 3417 357

753 7143 25143 2643 21543 2157 357

753 7143 25143 2643 267 2157 357

753 7143 25143 2517 267 2157 357

Discovered using SAT/SMT

Another 7-step version:

7 5 3

7 1 4 3

2 5 1 4 3

2 6 4 3

2 6 7

2 1 5 7

3 5 7