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

21–30 of 188 posts

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

#21

Post by tetris11 »

abetusk wrote: post #17
TylerE wrote: post #11

Earlier quoted context omitted.

The article specified a list of positive integers, and you can’t go smaller than the smallest initial value.

The constraints stated: * You can never make an integer greater than the largest integer in the original list. * You can never make a move that results in the same integer appearing in the list more than once. You can make a negative number and you can go lower than the smallest but not greater than the largest, so you're wrong on both counts.

It does feel implied albeit forgotten given the constrained nature of the task. Opening up the door to negative numbers feels like cheating.

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

#22

Post by thaumasiotes »

Karellen wrote: post #10
orlp wrote: post #4

It's not possible in general, e.g. [3, 2, 1] can't be reversed.

[3, 2, 1] has no valid modifications by the rules given. I wonder how little wiggle-room there needs to be for a solution to be possible? Does [4, 2, 1] have a solution? You can get to with [4, -1, 3, 1] with one step, but I'm not sure where you can go from there.

> You can get to with [4, -1, 3, 1] with one step, but I'm not sure where you can go from there.

Well, it's easy to show that you can't go anywhere from there:

1. You can't combine the 1 with the 3, because you'd have two 4s.

2. You can't combine the -1 with the 4, because you'd have two 3s.

3. You can't (usefully) combine the -1 with the 3, because that just means you never took your previous move of splitting that pair out of the 2.

Those are all the possible applications of the combining rule. You can't apply the splitting rule either:

1. Splitting the four into positive integers will cause a duplicate.

2. Splitting a negative number out of the four will violate the rule against numbers larger than 4.

3. Splitting the 3 has the same problems. You can't take out a negative number without leaving a residual of 4 or more, and you can't take out a positive number without leaving a residual of 1.

4. Taking a -1, -2, or -3 out of the 1 will leave a duplicate, and taking a positive value out of the 1 is impossible.

5. You can split the -1 into [-3, 2]. But at that point you need to get rid of the 1 in final position so that you can combine the -3 into the 4, and there isn't a way to do that. Once you've gotten here, your list already contains every legal positive value.

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

#24

Post by thih9 »

Karellen wrote: post #10
orlp wrote: post #4

It's not possible in general, e.g. [3, 2, 1] can't be reversed.

[3, 2, 1] has no valid modifications by the rules given. I wonder how little wiggle-room there needs to be for a solution to be possible? Does [4, 2, 1] have a solution? You can get to with [4, -1, 3, 1] with one step, but I'm not sure where you can go from there.

Technically there are valid modifications, you can modify [3,2,1] into [3,2,0,1]; but yes, this doesn’t change much.

Edit: disregard that, indeed the integers need to be smaller.

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

#25

Post by thih9 »

This can be transformed into a problem with pegs and moving blocks.

Like tower of hanoi[1], but you can add or remove empty pegs, blocks are the same size and can be stacked in any order, you can move as many blocks as you want and you cannot have towers with the same amount of blocks.

Unless you want to deal with negative integers, then it would get more tricky.

[1]: https://en.m.wikipedia.org/wiki/Tower_of_Hanoi

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

#27

Post by roenxi »

Karellen wrote: post #10
orlp wrote: post #4

It's not possible in general, e.g. [3, 2, 1] can't be reversed.

[3, 2, 1] has no valid modifications by the rules given. I wonder how little wiggle-room there needs to be for a solution to be possible? Does [4, 2, 1] have a solution? You can get to with [4, -1, 3, 1] with one step, but I'm not sure where you can go from there.

To be pedantic, this isn't the operation he gave - "split an integer into 2 smaller integers" is the operation, but 2 into [3, -1] is splitting it into a larger and smaller integer.

Read literally, the numbers are constrained to not jump over the 0. It might depend on interpretation (absolute value or distance from positive infinity?); but negatives are tricky to handle with these rules and I think they might be illegal.

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

#29

Post by Sharlin »

abetusk wrote: post #17
TylerE wrote: post #11

Earlier quoted context omitted.

The article specified a list of positive integers, and you can’t go smaller than the smallest initial value.

The constraints stated: * You can never make an integer greater than the largest integer in the original list. * You can never make a move that results in the same integer appearing in the list more than once. You can make a negative number and you can go lower than the smallest but not greater than the largest, so you're wrong on both counts.

However, as a result of #1, you in fact cannot make negative integers. It’s not possible to split a nonnegative integer into two lesser-or-equal integers such that either of them is negative.

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

#30

Post by [deleted] »

tetris11 wrote: post #21
abetusk wrote: post #17

Earlier quoted context omitted.

The constraints stated: * You can never make an integer greater than the largest integer in the original list. * You can never make a move that results in the same integer appearing in the list more than once. You can make a negative number and you can go lower than the smallest but not greater than the largest, so you're wrong on both counts.

It does feel implied albeit forgotten given the constrained nature of the task. Opening up the door to negative numbers feels like cheating.

[deleted]
Post reply on HN