Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Here's a puzzle game. I call it Reverse the List of Integers

mathstodon.xyz

Post reply on HN
Print view View original

141–150 of 188 posts

Re: Here's a puzzle game. I call it Reverse the List of Integers

#141

Post by adotbacon »

madcaptenor wrote: post #136
adotbacon wrote: post #128

Earlier quoted context omitted.

Yeah, the [n,n+1] is only a problem when there isn't enough wiggle room between the numbers. ex: [2,3] and [3,4] [3,4] --> [1,2,4] --> 4 can't split because 2/2 and 3/1 are invalid --> 4 can't initially split because 2/2 and 3/1 are both invalid [5,6] --> [5,4,2] --> [5,1,3,2] --> [6,3,2] --> [6,5] [7,8] --> [7,3,5] --> [7,1,2,5] --> [8,2,5] --> [8,7] When you add more numbers, you need more wiggle room. So, [4,5,6]…

A solution for [6,7,8,9]: 6,7,8,9 6,3,4,8,9 6,3,4,8,2,7 9,4,8,2,7 9,4,8,2,1,6 9,4,3,5,2,1,6 9,7,5,2,1,6 9,7,5,3,6 9,7,8,6 9,5,2,8,6 9,5,2,1,7,6 9,5,3,7,6 9,8,7,6

Wow, well done! I found [6,7,8] as well:

6,7,8

6,7,5,3

6,7,1,4,3

6,8,4,3

6,8,7

6,3,5,7

6,2,1,5,7

8,1,5,7

8,6,7

8,4,2,1,6

8,4,3,6

8,7,6

Re: Here's a puzzle game. I call it Reverse the List of Integers

#143

Post by jojojaf »

self wrote: post #2

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]). Operations: 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.) Restrictions: 1) You can never make an integer greater than the largest integer in the original list. 2) You can never make a move…

Can you only add adjacent integers?

Re: Here's a puzzle game. I call it Reverse the List of Integers

#144

Post by klyrs »

klyrs wrote: post #124
ahahahahah wrote: post #110

Earlier quoted context omitted.

[9,8] -> [6,3,8] -> [6,2,1,8] -> [6,2,9] -> [8,9]

Indeed, [n, n-1] [n-3, 3, n-1] [n-3, 2, 1, n-1] [n-3, 2, n] [n-1, n] Works for all n greater than... 6?

Optimizing self-response! That fails for six because n-3 and 3 co-occur. With a slight modification we can make it work for all n>5

  [n, n-1]
  [2, n-2, n-1]
  [2, n-3, 1, n-1]
  [2, n-3, n]
  [n-1, n]
edit: and it's not hard to show that n<6 are impossible, so the solution above is optimal in that sense.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#145

Post by dwallin »

Someone wrote: post #123
dwallin wrote: post #112

Earlier quoted context omitted.

You can make a physical version by having one fixed height pole for each integer up to the max, and then an equal number of post holes. Eg. If you wanted to support a game up to the integer 10 you would need 10 posts with lengths from 1 to 10 units, and 10 post holes. The biggest issue with this game is that there's no guarantee that any arbitrary starting state has a valid solution. A much needed improved would be a…

> If you wanted to support a game up to the integer 10 you would need 10 posts with lengths from 1 to 10 units, and 10 post holes. You’d also need a way to represent the order of the posts (the game is about a list of integers, not a set , so you can’t move from [4,5,6] to [10,5], for example) I think a halfway decent visualization is one where you have n different cylinders of lengths 1 through n and a gutter of len…

I really like this. I could see constructing a physical artifact for a specific case of this game.

According to another comment, the best puzzle with a high number of 6 is [1,6,3] with a minimum of 14 moves.

This would mean you have 6 total rods, and two gutters. The puzzle gutter with a length of 10, and the storage gutter with a length of 11.

If you want more visual symmetry a high number of 7 allows you potentially 2 gutters of length 14.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#146

Post by OskarS »

Neat little problem! You could do SAT-solvers and stuff, but it's also obviously a graph search problem: each state is a vertex, each edge is an operation that leads to another vertex. So, obviously: Dijkstra works (or really just BFS, since the edges are unweighted), but not the fastest in the world.

The fun one to play with would be A-star, but you'd have to find a suitable heuristic. One obvious candidate is that if you have target list that is X long and a current list that is Y long, then you need at least abs(Y - X) steps to get there (since each step either adds or removes a number). That's admissable and would probably speed up the search quite a bit compared to regular BFS, but you could probably do a lot better. I'm thinking a heuristic based on the number of inversions or something.

I would suspect if you found a really good heuristic for A-star, that's about as good as you're going to get. Though maybe there's something more clever I'm not spotting.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#147

Post by sltkr »

Sebb767 wrote: post #138
sltkr wrote: post #116

Earlier quoted context omitted.

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

They must be, because otherwise you'd never be allowed to split or combine to create the final list.

Good point!

Re: Here's a puzzle game. I call it Reverse the List of Integers

#148

Post by Someone »

dwallin wrote: post #145
Someone wrote: post #123

Earlier quoted context omitted.

> If you wanted to support a game up to the integer 10 you would need 10 posts with lengths from 1 to 10 units, and 10 post holes. You’d also need a way to represent the order of the posts (the game is about a list of integers, not a set , so you can’t move from [4,5,6] to [10,5], for example) I think a halfway decent visualization is one where you have n different cylinders of lengths 1 through n and a gutter of len…

I really like this. I could see constructing a physical artifact for a specific case of this game. According to another comment, the best puzzle with a high number of 6 is [1,6,3] with a minimum of 14 moves. This would mean you have 6 total rods, and two gutters. The puzzle gutter with a length of 10, and the storage gutter with a length of 11. If you want more visual symmetry a high number of 7 allows you potentiall…

Thinking it through a bit more, I would consider a variation on this game, where you don’t have a list but a ring buffer.

Then, you can replace the linear gutter by a circular one and replace the cylinders by parts of a torus. That would make for a cooler look of the game (on the other hand: how would you easily see you’ve completed the puzzle?)

Unfortunately, you won’t be able to put the ‘spare’ parts in a concentric circle as that would have a different radius.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#149

Post by plg94 »

b3orn wrote: post #68
sour-taste wrote: post #45

I thought the game was cool so I built a little version of it here: https://blaise.gg/number_game/index.html

Interesting, it appears I've encountered an impossible combination of numbers: [2, 5, 1, 3] The only possible move is to add 1 and 3. Can't ever split a 2 as that would result in [1, 1], can't split the 5 because that would be [4, 1] or [3, 2], can't split the 3, as that would be [2, 1] or [1, 2], can't add the 5 to anything as that would be larger than 5.

I was given [1,2] in the second run. Even easier to see it's impossible.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#150

Post by semi-extrinsic »

I made a completely graphical representation of this game in P5.js - it turned out quite intuitive I think.

The integers are represented by the number of edges in each straight section.

https://editor.p5js.org/semi-extrinsic/sketches/IKOjwE7Vb

Post reply on HN