Recent searches
Search options
Here's a puzzle game. I call it Reverse the List of Integers. How it works is, you start with a list of positive integers, (e.g. [7, 5, 3]) and your goal is to make the same list, in reverse ([3, 5, 7]). You have two moves you can make:
1) Split an integer into two smaller integers. (e.g. [7, 5, 3] → [6, 1, 5, 3])
2) Combine (add) two integers into a larger one. (e.g. reverse the last e.g.)
There are two restrictions that seem natural for making this into an interesting game:
1) You can never make an integer greater than the largest integer in the original list.
2) You can never make a move that results in the same integer appearing in the list more than once.
With these rules, even pretty simple lists can make non-trivial puzzles. (Try it with [7, 5, 3].) Some questions:
1) What are good algorithms, or even general strategies, for solving these?
2) For a given n, there must be some puzzle where n is the largest number in the list, and the number of moves required to solve the puzzle is maximized. What does the sequence of maximal required moves look like as a function of n? What do the "hardest" puzzles look like? Is there a way to determine either without using brute force?
@two_star ooh, very interesting!
@two_star On a related note, the lists with given maximum n (EDIT: and with the most terms, I forgot to mention) seem most constrained.
Another thought: those rules neatly block the strategies that most literally use palindromes.
@two_star That first thought wasn't very clear, even after the edit. What I meant is, among starting lists with the same biggest number n, the ones with more terms/greater sums look hardest to work with.
If a list uses, say, *all* the numbers 1-n, there are obviously no moves. But [12 8 5 3 2 1] also manages to block itself with just 12/2=6 terms. (And a moment's thought shows ceil(n/2) terms are needed to prevent the n term from splitting.)
@SevenNinths There are lists where the largest number can split, but a solution is still impossible. I'm wondering if this can ever happen with fewer than ceil(n/2) terms.
@two_star Can [5, 2] be reversed? I had trouble with all n=5, but maybe I should have written more down.
Looks like no. That would be an example then.
@SevenNinths For that matter, [6, 2] is also not reversible.
@SevenNinths @two_star Sure:
5 2
1 4 2
3 4
1 2 4
2 5
@specificprotagonist @SevenNinths I was probably not sufficiently clear about this, but you are only meant to be able to combine numbers in adjacent positions in the list.
@two_star Conjecture: if a list of two integers has at least one greater than 6, reversal requires no more or less than four moves.
Notes: By parity on the length of the list, only even numbers of moves can work. Also, two moves can't reverse a list, except by using an invalid position.
Outline: Choose distinct positive integers x, y, z such that the larger integer in the starting list is x+y+z and the smaller is either x or x+y. One of these sequences of steps should work, provided other collisions are avoided:
1. xyz x
xy z x
xy zx
x y zx
x yzx
2. xyz xy
xyz x y
xy z x y
xy zx y
xy zxy
@two_star Thought this was really neat so I built it here:
@two_star Clarification on the rules. Can you only sum two adjacent integers? If not, are there any restrictions on where the newly added number goes in the list?
@michaelmior Correct. Only adjacent integers.
@fn Oh, dear. Well, that explains the descending hordes.
@two_star 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.
@two_star For n=8 it's [1,3,5,8,7,4] with a minimum of 74 moves!
@3z326f7x If you can get n=9, it might be enough to have evidence of a connection to some sequence in the OEIS. See https://oeis.org/search?q=14%2C+26%2C+74&language=english&go=Search
@two_star For n=9 it's [4,7,5,2,3,6,9] with a minimum of 86 moves!
This took 3 hours to run, n=10 would be about 7 days, which is a little too much for me.
Here's the code: http://codepad.org/MFu6DLwg
@two_star I got nerd sniped :) and created https://github.com/unrealwill/ReverseListPuzzle to explore all the solutions, with graph algorithms.
@GistNoesis Very nice! I'm happy that you and others have found cool things to do with this.
@two_star I'm finding hard questions where the least length, not considering the largest number, arriving at (for all numbers less than 10):
For length 2: [1,6]
For length 3: [1,6,3]
For length 4: [4,8,6,5]
For length 5: [5,7,9,4,8]
@tianshuo I'd expect the maximal solution sequence length (with no restriction on largest number) to be bounded for a given list length. Once the largest number is too much larger than the list length, there is too much "breathing room" and problems get easier. But proving that you have found the largest length n puzzle could be hard.
@two_star You are right, the reason why problems are hard, is that there is just "suitable breathing room", if there is too little, then there won't be a solution, but when the numbers are too big, especially the largest number, gives a lot of gaps. But the definition is "too big" isn't trivial, for example, the largest number>4*second largest number doesn't even work for [1,5]
@two_star I've explored this puzzle exhaustively through n=12, and found the worst case to be {6:14, 7:26, 8:74, 9:86, 10:126, 11:106, 12:130}. I'm almost certain the worst case for 13 is 136, and I've found a case for 14 that requires 172 moves. I'm currently adding an OEIS entry.
@rokicki Fascinating that it actually goes down for 11!
@two_star Indeed! I was surprised. The distance-172 case at n=14 that I've found is [6,11,8,2,7,10,9,12,4,1,14,3] if anyone wants to test their solver.
@two_star And this one [3,14,9,1,2,6,12,4,13,5,11,8] takes 202 moves to solve!
@two_star ...and another question that comes to (my) mind --> Can we 'rank' a list with o(n) algo and give it a difficulty score?
@surfer Putting a number to "difficulty" is tricky. A list with a long solution, but with no branches in the graph of accessible lists isn't difficult, just tedious. Maybe "expected number of 'wrong' choices if random moves are taken at each step". (Excluding reversing the last move, probably.) We'd still have to define "wrong" carefully. (Is any move that results in a longer than necessary shortest path to the goal wrong?) Anyway, this seems like a start, but it might not capture "difficulty" perfectly. And the algorithmic complexity is going to depend on properties of the accessible list graph. But certainly not o(n).