Mathematic!

April 20, 2024 11:19 AM

Over on Mathstodon.xyz, Alexandre Muñiz comes up with an interesting 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.

User @ch33zer chimes in with a basic web implementation (followed by other attempts, including a visual version), and @GistNoesis offers some code for exploring the problem space to brute-force solutions.

The creator clarified some rules in a related Hacker News discussion:

Only positive integers are meant to be allowed. (Zero excluded.)

Combining is meant to work on adjacent pairs of integers.

Note that not all lists are solvable, but perhaps figuring that out is part of the challenge...

posted by Rhaomi (3 comments total)

This was kind of fun. It feels like a version of The Tower of Hanoi (which feels a little racist to me, but that seems to be what it is called).
posted by GenjiandProust at 3:09 PM on April 20 [2 favorites]

Note that not all lists are solvable, but perhaps figuring that out is part of the challenge.
It's hardly the Halting Problem. The criteria is that the difference between consecutive elements in the list isn't bigger than the maximum in the list (so you can't combine them) or you can't break an element into numbers already in the list.

It's probably more challenging to see if there's no chain of transformations without breaching these criteria. I think the test would be to see if you run out of unique n counting down from the largest number in the set.
posted by k3ninho at 6:47 AM on April 21 [1 favorite]

This sounds straightforward for a satisfiability solver. It would give you a solution sequence of <= N steps or prove that no such sequence exists.
posted by Arctic Circle at 12:18 PM on April 21