An entry in Fortnightly Topic Challenge #35: Restricted Title 1. Title based on this xkcd.
This is a continuation of Barrel - Part 1, Barrel - Part 2, Barrel - Part 3, and Barrel - Part 4, but this puzzle is still self-contained.
You and your boss have a conversation:
Boss: Hey, nice job managing the barrel warehouse this fortnight! I know it hasn't been easy.
You: No problem, I just transferred all the workload to Puz- uh... I mean thank you!
Boss: Anyway, I just have one final task for you. Do you think you could paint-
You: eager to finish your job, immediately splatters all of the available paint at the only barrel in the entire warehouse.
Boss: -the floor.
You: Oops.
Boss: Way to go, that was all of the available paint, and you just splattered it at the only barrel in the entire warehouse. Now in order to paint the floor, you'll have to roll that one barrel around until the whole floor is painted. And because we have such a limited supply of paint, you can't waste any of it by repainting squares!
You: Sorry. I'll get right to it. Frantically types question into Puzzling.SE using second person instead of first person in order to hide the fact that you are actually just trying to get strangers on the internet to do your work for you, even though it's not working because you're unnecessarily making it really obvious throughout the included conversation and especially in the italics.
To review,
- A barrel takes up one space when upright, and two spaces when laid down.
- Barrel movement works as in the following image (solid barrels can move to their adjacent outlines, assuming those spaces exist). Laid down barrels can roll to the side and be propped up. Upright barrels can be tipped over.
Painting Specifics
- When the painted side of the barrel touches the ground, the squares it occupies get painted.
- When a square gets painted, that square's paint dries instantaneously. That way, unpainted sides of the barrel do not become painted when they touch a painted square.
- You are not allowed to repaint any square, as per your boss's instructions.
Here is the warehouse. The single barrel is standing up with red paint on the side facing right. Please show how to paint the whole floor by just moving the barrel around, and without repainting any squares. You are not required to do so in the minimum number of moves.
Note: I added no-computers because I want the steps to be created by hand. But I will of course allow you to create an animated gif of a solution, or an interactive game (e.g. in flash) to make it easier to test your solutions.
Hint if you get stuck:
Yes, it is possible. :)
EDIT: In case anyone's confused about barrel movement and/or paint rules, here's a gif of some random movement:
Answer
Not required to do it in the minimum number of moves, eh? Well, "Inefficient" is my middle name! Actually, it's 'Pink', but whatever.
Let's build a horribly inefficient solution by first making some useful-but-inefficient building blocks, and then strategically-but-inefficiently combining them together!
Based on the moves I ended up creating, my strategy is this:
- Immediately toss the barrel down on its side to the right
- Using Building Block 1, make a sequence of moves that takes a barrel flat-right on its painted side to a position exactly two spaces below and still flat-right on its painted side, without painting anything else at all.
- Use Building Block 1 again, so that the barrel is now 4 spaces below where it was at the end of step 1, and a total of six spaces have been painted
- Using Building Block 2, make a sequence of moves that takes a barrel flat-right on its painted side to a position exactly three spaces above and still flat-right on its painted side, without painting anything else at all.
- Use Building Block 1 twice, so that the barrel is now 5 spaces below where it was at the end of step 1, and the right two columns are completely painted.
- Using Building Block 3, make a sequence of moves that takes a barrel flat-right on its painted side to a position exactly two spaces left and still flat-right on its painted side, without painting anything else at all. (The barrel is now flat on its painted side in the centre of the bottom row.)
- Repeat steps 2 through 5, but rotated 180 degrees, so that the barrel paints the entirety of the middle two columns, and finishes centre at the top.
- Use Building Block 3, and move two spaces to the left again.
- Repeat steps 2 through 5, so that the barrel paints the entirety of the last/left two columns.
Alright, before we get to actually making the Building Blocks, let's establish a fact that will define what I mean by a particular block being 'useful'.
If a particular building block only moves the barrel within a 4x4 space, starting in a corner, then this is 'useful' because we can start anywhere and achieve the desired movement by some combination of reflecting left-right, reflecting up-down, and inverting the sequence entirely. (If this isn't clear, we'll see some concrete examples in the building blocks below.)
Let's make Building Block 1!
The goal for Building Block 1 is a sequence of moves, in a 4x4 region, that moves the barrel lying right on its painted side in a corner, to lying right on its painted side two spaces below that, without painting anything else in between.
There may be shorter sequences than this, but the one I used was 20 moves long: "DDDLUURDLDRRULDLURDR". (Given how many times this block is repeated in some fashion, any improvement here is represented twelvefold in the overall sequence.)
Now it's easier to see why restricting the block to a 4x4 region is useful; we can immediately repeat this exact same sequence to move the barrel down-two again, whereas if the Building Block went lower than its prescribed 4x4 region, we couldn't do the same repeat as easily. Similarly, if went any further left than its prescribed 4x4 region, we wouldn't be able to use it when the barrel is in the middle columns at all.
In the strategy above, I also use this for painting the leftmost columns, where this clearly won't fit anymore. But in that case, all I have to do is swap every "left" with "right" and vice versa, to get a horizontal reflection that still moves down 2.
This is also used in the strategy to move from the fourth row to the bottom row, which also isn't possible using this sequence directly. However, inverting the sequence by going through it backwards and reversing each direction can be said to move the barrel two spaces up, ending in a corner. Now we can take this inverted sequence and reflect it vertically to get the desired down-two result ending in a corner.
Building Block 2!
The goal for Building Block 2 is a sequence of moves, in a 4x4 region, that moves the barrel lying right on its painted side in a corner, to lying right on its painted side three spaces below that, without painting anything else in between. (In the strategy, it's first used to move the barrel up rather than down, but this can be done by swapping every "up" with "down" and vice versa, to get a vertical reflection that moves up three.)
One sequence that works here is 10 moves long: "DDDLUURDDD". This specific sequence probably can't be improved, and it's actually nicely symmetrical.
Building Block 3!
The goal for Building Block 3 is a sequence of moves, in a 4x4 region, that moves the barrel lying right on its painted side in a corner, to lying right on its painted side two space left, without painting anything else in between. (In the strategy, it's first used to move the barrel starting in the bottom-right corner of the grid, but I can show the sequence here starting in the top-right corner and then swap every "up" with "down" and vice versa, to get a vertical reflection.)
One sequence that works here is 10 moves long: "LDLDRRULUL". This specific sequence probably can't be improved, and it's actually nicely symmetrical.
Putting it all together:
Building Blocks 1, 2, and 3 are respectively 20, 10, and 10 moves each. Altogether, this strategy takes 291 moves. It's immediately obvious that this can be improved: this strategy specifically works by taking convoluted routes just to avoid painting the ground. There are several spots where this can be shortcut; I hope that, by keeping the strategy consistent, this answer is still understandable despite how large it is.
The final sequence is:001: "R" (step 1) then 002–041: "DDDLUURDLDRRULDLURDR" + "DDDLUURDLDRRULDLURDR" (steps 2 and 3; Building Block 1 twice) then 042–051: "UUULDDRUUU" (step 4; Building Block 2, reflected vertically) then 052–091: "LDLURDRULLDRDLUURDDD" + "LDLURDRULLDRDLUURDDD" (step 5; Building Block 1 twice, inverted and reflected vertically) then 092–101: "LULURRDLDL" (step 6; Building Block 3, reflected vertically) then 102–191: "UUURDDLURULLDRURDLUL" + "UUURDDLURULLDRURDLUL" + "DDDRUULDDD" + "RURDLULDRRULURDDLUUU" + "RURDLULDRRULURDDLUUU" (step 7; steps 2–5 rotated 180°) then 192–201: "LDLDRRULUL" (step 8; Building Block 3) then 202–291: "DDDRUULDRDLLURDRULDL" + "DDDRUULDRDLLURDRULDL" + "UUURDDLUUU" + "RDRULDLURRDLDRUULDDD" + "RDRULDLURRDLDRUULDDD" (step 9; steps 2–5 reflected horizontally).
Overall, this is a solution, but it's also meant to be a framework and some helpful sequences for anybody who wants to work toward an actually efficient solution. Given that there's only 36 floor tiles to paint—which means 18 times when the paint side of the barrel lands down—I suspect there's a sub-150 move solution.
EDIT: Improved solution in 161 moves.
One of the main inefficiencies in the original strategy is Building Block 1; in the new strategy, Building Block 1 is dismissed entirely, and the path is reorganized to use Blocks 2 and 3, and the simple movement of 'roll 4 spaces down'.
Because the paint is on the side of the barrel, covering the 36 floor tiles has to be done in 18 parts. In both strategies, the 18 parts are always 3 in each row, but this is not the only way it can be done.
The original order of the 18 parts (left) and the new order (right) are pictured below:
The new path is:
First, move down-down-right into position 1.
Second, use Building Block 3 twice to move along the fourth row, right-to-left.
Third, use Building Block 2 to move up to the top row.
Fourth, use Building Block 3 twice to move along the top row, left-to-right.
Fifth, roll down four times into the fifth row.
From here, keep using Block 3 to move along each row, and then using either Block 2 to move three rows up or 'roll 4 down' to move four rows down.
The final sequence is:
001-003: "DDR" (step 1) then 004–023: "LULURRDLDL" + "LULURRDLDL" (step 2; Building Block 3 twice, reflected vertically) then 024–033: "UUURDDLUUU" (step 3; Building Block 2, rotated 180°) then 034–053: "RDRDLLURUR" + "RDRDLLURUR" (step 4; Building Block 3 twice, reflected horizontally) then 054–057: "DDDD" (step 5; roll down from row 1 to row 5) then 058–077: "LULURRDLDL" + "LULURRDLDL" (step 2; Building Block 3 twice, reflected vertically) then 078–087: "UUURDDLUUU" (step 3; Building Block 2, rotated 180°) then 088–107: "RDRDLLURUR" + "RDRDLLURUR" (step 4; Building Block 3 twice, reflected horizontally) then 108–111: "DDDD" (step 5; roll down from row 1 to row 5) then 112–131: "LULURRDLDL" + "LULURRDLDL" (step 2; Building Block 3 twice, reflected vertically) then 132–141: "UUURDDLUUU" (step 3; Building Block 2, rotated 180°) then 142–161: "RDRDLLURUR" + "RDRDLLURUR" (step 4; Building Block 3 twice, reflected horizontally).EDIT again
Thought of another improvement. Since rolling up/down 4 is more efficient than the 10-move Building Block 3 used to go along the rows, the Block 3 movement along rows 1 and 5 can be combined, and similarly the Block 3 movement along rows 2 and 6 can be combined. (That is, instead of doing two Block 3s in one row, a single roll4, and then two Block 3s; replace that with immediately moving to the other row with a roll4, then Block 3, roll4, Block 3, roll4.)
Replacing a 44-move sequence to do the two rows with a 32-move sequence accomplishing exactly the same saves 12 moves; this is done twice, bringing the current move count down from 161 to 137. (This satisfies my original goal of 150, so I'll stop here. Getting below 100 may be possible, but it would almost definitely require a different strategy from this, like a different layout of how to split the floor into 18 pairs for painting.)
No comments:
Post a Comment