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

121–130 of 188 posts

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

#121

Post by CyberDildonics »

317070 wrote: post #103
Shorel wrote: post #80

Earlier quoted context omitted.

"Dynamic programming" is jargon from competitive programming. It sounds a lot more sophisticated than it is. In reality, it is nothing more than memoization of function calls into an array.

> In reality, it is nothing more than memoization of function calls into an array. No, it's the next step after memoization. Recursion is the slowest approach of implementing many algorithms, as it will duplicate a lot of computation of subproblems. It solves a lot of subproblems many times. Memoization is a cheap fix, it will not solve subproblems multiple times. It stores subproblems it has already solved, along wi…

Keeping the intermediate results of computations is just called programming. They go into a variable or a data structure like a vector or a hash map.

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

#122

Post by lupire »

CamperBob2 wrote: post #96
selfie wrote: post #20

Could a constraint solver just rip through this problem?

It was interesting to see GPT4 fail at it: https://chat.openai.com/share/02c12bbe-43cd-40da-b5df-33681d... Not a bad benchmark problem. It didn't get very far, but maybe the next release will.

ChatGPT can't write programs or do logic to solve problems whole solutions aren't already in its input.

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

#123

Post by Someone »

dwallin wrote: post #112
Someone wrote: post #61

Earlier quoted context omitted.

The charm of towers of Hanoi is that you can make a physical version where the legality of moves is easily verified because of the differently sized blocks. I think the “you cannot have towers with the same amount of blocks” rule will make this a lot less charming, certainly if any of the numbers are larger than, say, 10. There also is the issue of adding pegs, but that’s solvable by fixing the number of stacks (the…

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 length of the sum of the numbers you start with (in the [4,5,6] example that would be 15). Next, place the cylinders for the starting position in the gutter in the order given, so that it completely fills it. Keep the others elsewhere.

Allowed moves then are:

- replace two cylinders that are side by side in the gutter by one of the sum of their lengths that you have available.

- replace a cylinder in the gutter by two available cylinders that together have the same length.

I think this way to visualize the game also might lead to a physical construction, but I don’t see on yet.

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

#124

Post by klyrs »

ahahahahah wrote: post #110
jxding wrote: post #107

Earlier quoted context omitted.

It does seem like [n,n+1] is always unsolvable!

[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?

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

#126

Post by fragmede »

minikomi wrote: post #53
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

Jumping in with my janky version: http://poyo.co/list-of-integers/

I really like the visual aspect of your implementation

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

#127

Post by CamperBob2 »

lupire wrote: post #122
CamperBob2 wrote: post #96

Earlier quoted context omitted.

It was interesting to see GPT4 fail at it: https://chat.openai.com/share/02c12bbe-43cd-40da-b5df-33681d... Not a bad benchmark problem. It didn't get very far, but maybe the next release will.

ChatGPT can't write programs or do logic to solve problems whole solutions aren't already in its input.

It applied logical reasoning, just not quite enough of it. When it gets 10x better, which it will, it will be smarter than either of us.

For those who don't find that prospect fascinating, other sites beckon.

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

#128

Post by adotbacon »

ahahahahah wrote: post #110
jxding wrote: post #107

Earlier quoted context omitted.

It does seem like [n,n+1] is always unsolvable!

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

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] is problematic and probably [5,6,7].

[4,5,6]

--> [3,1,5,6] --> 6 can't break into 3, nor 5/1. It can do 4/2, but then 5 can't split. 5 also can't split.

--> [4,2,3,6] --> [4,2,3,1,5] --> [6,4,5] --> 4 can't split into 2/2. It can split to 3/1 but then 5 can't split

--> 6 can't initially split at all because 3/3, 4/2, and 5/1 are invalid

Even if [6,7,8] has a solution, I'm sure [6,7,8,9] does not.

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

#129

Post by dhartmei »

two-star wrote: post #101

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.

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.

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

#130

Post by [deleted] »

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.

[deleted]
Post reply on HN