Mathematic!
April 20, 2024 11:19 AM Subscribe
Over on Mathstodon.xyz, Alexandre Muñiz comes up with an interesting puzzle game:
The creator clarified some rules in a related Hacker News discussion:
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: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.
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.
The creator clarified some rules in a related Hacker News discussion:
Only positive integers are meant to be allowed. (Zero excluded.)Note that not all lists are solvable, but perhaps figuring that out is part of the challenge...
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.
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]
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
posted by Arctic Circle at 12:18 PM on April 21
« Older Phish at The Sphere | Not quite Mathematic! Newer »
posted by GenjiandProust at 3:09 PM on April 20 [2 favorites]