4 ms·

Hi. I'm the post's author. This was something I dashed off quickly, so I was a bit imprecise in the language. Clarifications: Only positive integers are meant

Hi. I'm the post's author. This was something I dashed off quickly, so I was a bit imprecise in the language. Clarifications: Only positive integers are meant to be allowed. (Zero excluded.) Combining is meant to work on adjacent pairs of integers. If this is used in coding interviews, I deny any responsibility. Unless it's used in interviewing me, in which case I will totally take credit.

davidalayachew 2y ago
Thanks for posting this. I made a playable version of your game too. Bundled inside is algorithms for solving it as well. https://github.com/davidalayachew/ReverseTheListOfIntegers https://github.com/davidalayachew/ReverseTheListOfIntegers
sltkr 2y ago
Should we assume the numbers are initially positive and distinct, too?
- Sebb767 2y ago
  They must be, because otherwise you'd never be allowed to split or combine to create the final list.
  - sltkr 2y ago
    Good point!
  - keefle 2y ago
    Technically there are cases in which you can. The repeated values will act like separators that you cannot act on (because once you act on one, as you said one cannot create the final list again), but then it becomes multiple instances of the puzzle which seems pointless
dhartmei 2y ago
Brute-force says the hardest puzzle for n=6 is [1,6,3] with a minimum of 14 moves. And for n=7 it's [5,4,1,2,7] with a minimum of 26 moves.
klyrs 2y ago
For whatever it's worth, zero gets you absolutely nowhere; there's no harm in allowing it.
GistNoesis 2y ago
I got nerd sniped :) and created https://github.com/unrealwill/ReverseListPuzzle https://github.com/unrealwill/ReverseListPuzzle to explore all the solutions, with graph algorithms.
- davidalayachew 2y ago
  Lol, they got me too. Mine has an algorithm to find a solution quickly, and another to find the shortest solution possible. I also created a very rudimentary GUI so that the game could be played. I'll clean the GUI up later though. https://github.com/davidalayachew/ReverseTheListOfIntegers https://github.com/davidalayachew/ReverseTheListOfIntegers

davidalayachew 2y ago

Thanks for posting this. I made a playable version of your game too. Bundled inside is algorithms for solving it as well. https://github.com/davidalayachew/ReverseTheListOfIntegers https://github.com/davidalayachew/ReverseTheListOfIntegers

sltkr 2y ago

Should we assume the numbers are initially positive and distinct, too?

Sebb767 2y ago
They must be, because otherwise you'd never be allowed to split or combine to create the final list.
- sltkr 2y ago
  Good point!
- keefle 2y ago
  Technically there are cases in which you can. The repeated values will act like separators that you cannot act on (because once you act on one, as you said one cannot create the final list again), but then it becomes multiple instances of the puzzle which seems pointless

dhartmei 2y ago

Brute-force says the hardest puzzle for n=6 is [1,6,3] with a minimum of 14 moves. And for n=7 it's [5,4,1,2,7] with a minimum of 26 moves.

klyrs 2y ago

For whatever it's worth, zero gets you absolutely nowhere; there's no harm in allowing it.

GistNoesis 2y ago

I got nerd sniped :) and created https://github.com/unrealwill/ReverseListPuzzle https://github.com/unrealwill/ReverseListPuzzle to explore all the solutions, with graph algorithms.

davidalayachew 2y ago
Lol, they got me too. Mine has an algorithm to find a solution quickly, and another to find the shortest solution possible. I also created a very rudimentary GUI so that the game could be played. I'll clean the GUI up later though. https://github.com/davidalayachew/ReverseTheListOfIntegers https://github.com/davidalayachew/ReverseTheListOfIntegers