14
$\begingroup$

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.

enter image description here

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.

enter image description here

Note: I added 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:

enter image description here

$\endgroup$
  • $\begingroup$ No fair, no fair! :) $\endgroup$ – Chowzen Jun 6 '18 at 2:51
  • $\begingroup$ LOL at the flavour text! $\endgroup$ – Phylyp Jun 6 '18 at 2:51
10
$\begingroup$

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:

  1. Immediately toss the barrel down on its side to the right
  2. 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.
  3. 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
  4. 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.
  5. 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.
  6. 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.)
  7. 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.
  8. Use Building Block 3, and move two spaces to the left again.
  9. 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.
enter image description here
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.)
enter image description here
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.)
enter image description here
One sequence that works here is 10 moves long: "DDDLUURDDD". This specific sequence probably can't be improved, and it's actually nicely symmetrical.
enter image description here

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.)
enter image description here
One sequence that works here is 10 moves long: "LDLDRRULUL". This specific sequence probably can't be improved, and it's actually nicely symmetrical.
enter image description here

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).
enter image description here

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:

enter image description here

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).
enter image description here

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.)
enter image description here

$\endgroup$
  • $\begingroup$ Yes, this is definitely a valid solution. A horribly inefficient one, but valid. $\endgroup$ – Riley Jun 6 '18 at 12:33
  • $\begingroup$ @Riley I thought about it a little more, and I've added a much shorter solution, though it's probably still not minimal since it's the same sort of structure. $\endgroup$ – ManyPinkHats Jun 6 '18 at 15:29
  • $\begingroup$ 161 moves? You better hope Riley hasn't been skipping on his core muscle exercises! 🙂 $\endgroup$ – Phylyp Jun 6 '18 at 15:32
  • 2
    $\begingroup$ I just realized a really silly way to improve the second strategy even further. Sub-150, here I come! $\endgroup$ – ManyPinkHats Jun 6 '18 at 15:40
  • $\begingroup$ These gifs are really satisfying. I'm mesmerised. $\endgroup$ – LinuxBlanket Jun 6 '18 at 16:31
0
$\begingroup$

Ok this is a long journey for the barrel...

Denote U as Up, R as Right, D as Down, and L as Left.

1. DDDLDLL
2. 5 x (DUR) DU
3. ULURD
4. 5 x (DUL) DU
5. URULD
6. Repeat 2, 3, 4, 5
7. URR
8. DLUDLU DRRRU DRUDRU
9. DDLUL
10. URDURD ULLLD ULDULD

$\endgroup$
  • $\begingroup$ Perhaps you have misunderstood the rules about the barrel movement, or I have misunderstood your answer. After the barrel moves DDDL, it will be unable to move down again, because it has reached the edge of the board. $\endgroup$ – Riley Jun 6 '18 at 4:32
  • $\begingroup$ Whoops, I'm sorry I was assuming the barrel to be 1x1x1 >< $\endgroup$ – athin Jun 6 '18 at 4:35
  • 4
    $\begingroup$ I've added a gif of random barrel movement so that everything should be clear now :) $\endgroup$ – Riley Jun 6 '18 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.