3 ms·

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

by thih9 3y ago

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 https://en.m.wikipedia.org/wiki/Tower_of_Hanoi

seventytwo 3y ago
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.
- thaumasiotes 3y ago
  No, not at all. In a Towers of Hanoi model, this is a completely trivial game. You'd reverse [7, 5, 3] by picking four discs off the first peg and putting them back down on the third peg. The rules here only allow you to move stuff a single peg away from its origin.
  - GilbertErik 3y ago
    In Towers of Hanoi, you're only allowed to pick up one disc at a time, so it's not completely trivial. It's simply operation intensive... kinda like Reverse the List of Integers [1] https://en.wikipedia.org/wiki/Tower_of_Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi
    - tczMUFlmoNk 3y ago
      They're not suggesting picking up multiple discs at a time: [3,2,1][][] => [3,2][][1] => [3][][1,2] => [][][1,2,3] In effect, they're just observing that the algorithm "while x := A.pop(): B.push(x)" reverses A onto B.
      - thaumasiotes 3y ago
        Of course I'm suggesting picking up multiple discs at a time. That's the whole idea. Compare thih9's comment: > 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. All my comment did was to point out that this description doesn't work, because the rules here are not similar to the rules of Towers of Hanoi. Under the rules of the original comment, here's how you reverse the list [7, 5, 3]: +++++++ +++++ +++ +++(----) +++++ +++(++++) It's a simple, one-step process, and this will be true for any list of three integers. A list of four or five will take two steps, a list of six or seven will take three, etc. In all cases, reversing the list is completely trivial, because thih9 introduced a rule, allowing you to simply swap two numbers, that isn't present in the original ruleset.
_nalply 3y ago
Yeah... Make a browser game out of it?
Someone 3y ago
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 triangular number for n is about ½n², so it certainly need not be larger than twice the square root of the number of blocks). You can even make it smaller to get a variation on this game where the length of the list is limited.
- dwallin 3y ago
  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 simple rule for guaranteed reversible starting formations (if one even exists).
  - lupire 3y ago
    Post holes are useless, because you can split left and then split back to the right. So all you need are the n tokens. Hanoi isn't a good model for this, because the posts are not fixed in place and the units are all identical. It's a bad physical game because the player has to do all the work to enforce the rules. The environment doesn't provide any useful assistance.
  - Someone 3y ago
    > 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.

by thih9 3y ago

seventytwo 3y ago

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.

thaumasiotes 3y ago
No, not at all. In a Towers of Hanoi model, this is a completely trivial game. You'd reverse [7, 5, 3] by picking four discs off the first peg and putting them back down on the third peg. The rules here only allow you to move stuff a single peg away from its origin.
- GilbertErik 3y ago
  In Towers of Hanoi, you're only allowed to pick up one disc at a time, so it's not completely trivial. It's simply operation intensive... kinda like Reverse the List of Integers [1] https://en.wikipedia.org/wiki/Tower_of_Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi
  - tczMUFlmoNk 3y ago
    They're not suggesting picking up multiple discs at a time: [3,2,1][][] => [3,2][][1] => [3][][1,2] => [][][1,2,3] In effect, they're just observing that the algorithm "while x := A.pop(): B.push(x)" reverses A onto B.
    - thaumasiotes 3y ago
      Of course I'm suggesting picking up multiple discs at a time. That's the whole idea. Compare thih9's comment: > 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. All my comment did was to point out that this description doesn't work, because the rules here are not similar to the rules of Towers of Hanoi. Under the rules of the original comment, here's how you reverse the list [7, 5, 3]: +++++++ +++++ +++ +++(----) +++++ +++(++++) It's a simple, one-step process, and this will be true for any list of three integers. A list of four or five will take two steps, a list of six or seven will take three, etc. In all cases, reversing the list is completely trivial, because thih9 introduced a rule, allowing you to simply swap two numbers, that isn't present in the original ruleset.

_nalply 3y ago

Yeah... Make a browser game out of it?

Someone 3y ago

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 triangular number for n is about ½n², so it certainly need not be larger than twice the square root of the number of blocks). You can even make it smaller to get a variation on this game where the length of the list is limited.

dwallin 3y ago
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 simple rule for guaranteed reversible starting formations (if one even exists).
- lupire 3y ago
  Post holes are useless, because you can split left and then split back to the right. So all you need are the n tokens. Hanoi isn't a good model for this, because the posts are not fixed in place and the units are all identical. It's a bad physical game because the player has to do all the work to enforce the rules. The environment doesn't provide any useful assistance.
- Someone 3y ago
  > 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.