Communications of the ACM
Last Byte
Tidy Towers
Credit: Vecteezy
You are given a tower consisting of identical cubes, each of which has the same colors on the vertical sides in the same clockwise order as in Figure 1. The goal is for all cubes to be aligned in that all colors are the same vertically. A tower with such an alignment is called tidy.
Figure 1. The vertical sides of each cube consist of the colors red, green, blue, and yellow in clockwise order.
Two kinds of operations are allowed: rotate a cube and then all cubes above it rotate as well or rotate a cube c1 and hold a cube c2 above c1 so that neither cube c2 nor the cubes above c2 rotate but all cubes starting with c1 and up to the cube just below c2 rotate.
Warm-Up: How many operations does it take to make the tower of Figure 2 tidy?
Figure 2. An operation consists of rotating a consecutive subsequence of the cubes in the tower. A tidy tower has all the same colors facing forward. How many operations are required to make this tower tidy?
Solution to the Warm-Up: Just two. Rotate the yellow at height two so that the cubes at heights two, three, six, and seven all have blue facing forward. Then rotate the cube at height four while holding the cube at height six steady. The two rotations make the rotated cubes present blue facing forward.
Now that you have the hang of it, here is a challenge.
Question 1: In this question, I indicate the forward-facing side with R, G, B, Y representing red, green, blue, and yellow respectively where the leftmost cube corresponds to the bottom cube (position 0): RGBYRGBYBGBGBG. Can you make this tower tidy in eight moves or less?
Solution for eight moves: RGBYRGBYBGBGBG → (rotate by one position at position 1 and hold at position 2) RRGBYRGBGRGRGR → (rotate by one position at position 2 and hold at position 3) RRRBYRGBGRGRGR → (rotate by two positions at position 3 and hold at position 4) RRRRYRGBGRGRGR → (rotate by one at position 4 and hold at position 5) RRRRRRGBGRGRGR → (rotate by one at position 6 and hold at position 9) RRRRRRRGRRGRGR → (rotate by one at position 7 and hold at position 8) RRRRRRRRRRGRGR → (rotate by one at position 10 and hold at position 11) RRRRRRRRRRRRGR → (rotate by one at position 12 and hold at position 13) RRRRRRRRRRRRRR
Now that you have the hang of it, here is a challenge.
As a single-person game, what can we say about this problem? Clearly, it does not help to rotate the bottom cube without holding other cubes. Any consecutive aligned cubes should be rotated together or not rotated at all.
Question: If we take all consecutive aligned cubes and pretend they are a single cube, then the number of cubes in the remaining pile less all those already aligned with the bottom cube is an upper bound on the number of moves required. Can you give an example with four cubes to show it is sometimes possible to require fewer turns than the upper bound?
As a single-person game, what can we say about this problem?
Solution: There are many possible solutions, but here is one: RGBG. The upper bound would be three, but in fact two moves are sufficient. RGBG → (rotate by one at position 1) RRGR → (rotate at position 2 by one and hold at position 3) RRRR.
Upstart 1: Try to find an algorithm with a tight bound for the single-player game. Please describe in words and provide code in Python or C.
Now, let us consider the following two-person game: Bob and Alice play a game of tidying the tower. The same operations are allowed except that neither player is allowed to rotate a block that either player has already both touched and rotated (even if that rotation is a complete rotation that does not change the orientation of the block). Play continues until all blocks have been touched and rotated. At any point, a tower is said to be k-tidy if all but k of its blocks are tidy. Call the smallest k for which player A creates a k-tidy tower over the course of play minA. Call the smallest k for which player B creates a k-tidy tower over the course of play minB. Intuitively, minA is the closest A has come to making the tower tidy. Similarly for minB. If minA < minB, then A wins. If minA > minB, then B wins. If they are tied, then the player who performs the last rotation loses.
Upstart 2: Given a tower and given that Alice moves first, does either player have a winning strategy? If so, what is it?
Footnotes
All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to Upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2023 ACM, Inc.
No entries found