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

31–40 of 188 posts

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

#31

Post by DougBTX »

Sharlin wrote: post #29
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.

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.

> largest integer in the original list

So if the original list was [10, 1] and negative numbers were allowed, then [10, 2, -1] would be allowed.

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

#32

Post by thih9 »

orlp wrote: post #4

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

Technically the rules never state that when splitting an integer you have to put the new numbers in place of the old one, so...

[3, 2, 1]

[0, 2, 1, 3]

[2, 1, 3]

[0, 1, 2, 3]

[1, 2, 3]

I.e.: Split 3 into 3+0. Combine 0+2. Split 1 into 1+0. Combine 0+3 because rules don’t prohibit that either.

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

#33

Post by FL1ppY »

thih9 wrote: post #24
Karellen wrote: post #10

Earlier quoted context omitted.

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

Technically 1 is not smaller than 1 ;)

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

#34

Post by [deleted] »

thaumasiotes wrote: post #22
Karellen wrote: post #10

Earlier quoted context omitted.

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

[deleted]

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

#35

Post by Sharlin »

thih9 wrote: post #32
orlp wrote: post #4

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

Technically the rules never state that when splitting an integer you have to put the new numbers in place of the old one, so... [3, 2, 1] [0, 2, 1, 3] [2, 1, 3] [0, 1, 2, 3] [1, 2, 3] I.e.: Split 3 into 3+0. Combine 0+2. Split 1 into 1+0. Combine 0+3 because rules don’t prohibit that either.

Yeah, the problem is slightly underspecified, though it’s pretty obvious that you’re not allowed to do swaps as that obviously makes the problem trivial.

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

#36

Post by seventytwo »

thih9 wrote: post #25

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

Was just thinking this. There’s some differences, like the integers don’t have to be ordered biggest to smallest at any time, but it very much feels like Towers of Hanoi would be a good starting place to solve this.

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

#37

Post by thih9 »

Sharlin wrote: post #35
thih9 wrote: post #32

Earlier quoted context omitted.

Technically the rules never state that when splitting an integer you have to put the new numbers in place of the old one, so... [3, 2, 1] [0, 2, 1, 3] [2, 1, 3] [0, 1, 2, 3] [1, 2, 3] I.e.: Split 3 into 3+0. Combine 0+2. Split 1 into 1+0. Combine 0+3 because rules don’t prohibit that either.

Yeah, the problem is slightly underspecified, though it’s pretty obvious that you’re not allowed to do swaps as that obviously makes the problem trivial.

Not trivial - I do not see how to solve [3, 2, 1] without this kind of swapping. Perhaps we need to clarify the rules for a starting point first.

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

#38

Post by Etherlord87 »

thih9 wrote: post #32
orlp wrote: post #4

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

Technically the rules never state that when splitting an integer you have to put the new numbers in place of the old one, so... [3, 2, 1] [0, 2, 1, 3] [2, 1, 3] [0, 1, 2, 3] [1, 2, 3] I.e.: Split 3 into 3+0. Combine 0+2. Split 1 into 1+0. Combine 0+3 because rules don’t prohibit that either.

You're supposed to split an integer into two *smaller* integers.

3 is not smaller than 3, so you can't split 3 into 3+0.

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

#39

Post by thih9 »

Etherlord87 wrote: post #38
thih9 wrote: post #32

Earlier quoted context omitted.

Technically the rules never state that when splitting an integer you have to put the new numbers in place of the old one, so... [3, 2, 1] [0, 2, 1, 3] [2, 1, 3] [0, 1, 2, 3] [1, 2, 3] I.e.: Split 3 into 3+0. Combine 0+2. Split 1 into 1+0. Combine 0+3 because rules don’t prohibit that either.

You're supposed to split an integer into two *smaller* integers. 3 is not smaller than 3, so you can't split 3 into 3+0.

Oh, good spot. Yeah, no luck then.

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

#40

Post by Sharlin »

thih9 wrote: post #37
Sharlin wrote: post #35

Earlier quoted context omitted.

Yeah, the problem is slightly underspecified, though it’s pretty obvious that you’re not allowed to do swaps as that obviously makes the problem trivial.

Not trivial - I do not see how to solve [3, 2, 1] without this kind of swapping. Perhaps we need to clarify the rules for a starting point first.

I mean that if you allow swapping then every instance of the problem becomes trivial because swapping is all that reversing is. Doesn’t mean the problem as intended is always solvable.
Post reply on HN