Sunday, 20 April 2014

optimization - Barrel - Part 3


An entry in Fortnightly Topic Challenge #35: Restricted Title 1. Title based on this xkcd.
This is a continuation of Barrel - Part 1 and Barrel - Part 2, but this puzzle is still self-contained.
Continued in Barrel - Part 4 and Barrel - Part 5.




Having excelled at your previous two barrel warehouse management jobs, you have been promoted to the honorable position of Barrel Sorter! I know what you're thinking, that sounds more like a demotion. But just go with it; let's say it has a higher salary. Anyway, it's just like Bucket Sort, but with barrels (not really).


First, some terminology that comes with the new job:



  • A barrel is said to face up or down if the opening is on the top or bottom, respectively.

  • A nest is a group of barrels positioned such that for any two barrels in the group, one of them is inside the other. All barrels in a nest are either up-facing or down-facing.


  • A nest is sorted if all of its barrels are facing up.

  • A sorting platform is a platform used for sorting (duh). A platform can hold at most one nest. For your job, you only have two sorting platforms.

  • A barrel is available if you can see it from above. That is, it isn't inside a down-facing barrel.

  • A barrel is empty if it doesn't contain any other barrels.


To sort barrels, you have two possible operations, which have different effects for up-facing and down-facing barrels:



  • Flip: You may take an up-facing available barrel and invert it. Doing so will also invert all barrels inside of the one you flip. Or you may take a down-facing, available, empty barrel and invert it.

  • Move: You may take an up-facing available barrel and move it to the other sorting platform. Doing so will also move the barrels inside of it. Or you may take a down-facing available barrel and move it to the other sorting platform. Doing so will not move the barrels inside of it. In either case, when you move barrel(s) to a new platform, you must be able to place them directly onto the other platform from above, without inverting any barrels, and while keeping everything a nest on both platforms.



Here are the six barrels you need to sort. In the end, you should have one sorted nest on one of the platforms. Oh, and please do this in the minimum number of operations. :)


enter image description here



Answer



My best so far is



11 operations: Move the upside down barrels to the other platform, flipping each on the way, and then stack everything up starting with the smallest barrel.



Calling the barrels A-F with A being the largest one:



1: Move A

2: Flip A
3: Move C
4: Flip C
5: Move E
6: Flip E
7: Move F
8: Move E (containing F)
9: Move D (containing EF)
10: Move C (containing DEF)
11: Move B (containing CDEF)




I think I could shave off at least one move if I were allowed to flip a face-down barrel with its contents, but sadly that isn't an option. (EDIT: not that sadly, it turns out. Flipping those would allow a trivial, boring 6-move solution.)


No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...