1
$\begingroup$

A 3x4 grid contains a heavy stone in each cell. Walking from a cell to an adjacent cell (horizontally or vertically) without any stones requires 1 second. Moving one stone from a cell to an adjacent cell requires 2 seconds. Moving two stones from a cell to an adjacent cell requires 4 seconds. Starting from a corner of the grid, how quickly can you move all the stones and place them into a single cell?

You may need a computer to solve this.

$\endgroup$
  • 1
    $\begingroup$ Is there a clever way to solve this? It looks like the "best" way is going to be tedious enumeration of the possibilities, rather than any interesting logic. $\endgroup$ – Deusovi Feb 12 at 6:08
  • 1
    $\begingroup$ There are some simple observations that reduce the search space considerably. Actually if you try to solve it you will find there are not that many good options. I am happy for people to use a computer. Actually I will add that in. $\endgroup$ – Dmitry Kamenetsky Feb 12 at 6:10
  • 6
    $\begingroup$ This seems like more of a programming challenge then a puzzle, then. A puzzle should require some significant insight that leads to the solution, not "simple observations" leading to a programming task. $\endgroup$ – Deusovi Feb 12 at 6:32
  • 2
    $\begingroup$ I've added computer science tag. Is that better now? You can stop downvoting me, because this is a good puzzle. $\endgroup$ – Dmitry Kamenetsky Feb 12 at 9:35
  • 3
    $\begingroup$ When you move a stone, do you have to be in the same cell as the stone? Assuming yes to that question, do you stay in the same cell or move to the adjacent cell you move the stone to? $\endgroup$ – Jaap Scherphuis Feb 12 at 12:42
5
$\begingroup$

I can do it in

50 seconds!

The first thing to notice is that each stone takes 2 seconds to move to the adjacent cell. Even if you're moving 2 stones at once, it still takes 2 seconds per stone to move. So, to figure out the best cell to move them all, all you have to do is:

Find a cell that will take the least amount of moves to get all the stones to. Since the board is symmetric, you only need to consider 4 cells:

             012  101  123  212
             123  212  012  101
             234  323  123  212
             345  434  234  323

Total moves:  30   26   24   20

The last configuration only requires

20 moves - 40 seconds total, so that's the best one. Notice that since it's symmetric any one of the 2 middle cells can be used.

40 seconds is the least amount of time to actually move the stones. To minimize the total time it takes, you have to minimize the time it takes you to go get the stones from the final cell. Going to get one stone at a time will not work, because you will need to go out more often. So you have to make sure to bring back at least two stones every time you go out. You have 11 stones to collect, and can only carry 2 stones at a time, so you'll need to leave at least 6 times. Here's what the times look like to get to the stones to bring them back:

212
x0x
xxx
323

As you can see

I x'ed out the second stones that you will pick up on the way back from each outing. So the final time to get the stones is 13 seconds.

But wait! You don't actually start in the final cell, you start in the corner. That means you can eliminate one of the times that it takes you to get to the corner from the final cell. The other answers here decided to eliminate the 2 second corner (for some reason? LOL, I only jest!), but if you eliminate the 3 second corner, the total time will be 40 + 10 = 50 seconds!

Ok, to make things clear, here's the final solution:

You are in a corner. Grab the stone, move up, grab another stone, move up then move right. Time: 10 seconds.
Go down, go down.Time: 2 seconds.
Grab stone, move up, grab stone, move up. Time: 6 seconds.
Go down, go down, go right. Time: 3 seconds.
Grab stone, move up, grab stone, move up, move left. Time: 10 seconds.
Move up, move left. Time: 2 seconds.
Grab a stone, move down, grab a stone, move right. Time: 6 seconds.
Move up, move right. Time: 2 seconds.
Grab a stone, move down, grab a stone, move left. Time: 6 seconds.
Move up. Time: 1 second.
Grab a stone, move down. Time: 2 seconds.
Total time: 10 + 2 + 6 + 3 + 10 + 2 + 6 + 2 + 6 + 1 + 2 = 50 seconds.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Great solution! Can we prove that this is optimal? $\endgroup$ – Dmitry Kamenetsky Jun 4 at 7:42
1
$\begingroup$

Here is a solution that takes 51 seconds.

Start in the lower left corner. Move stone up, move 2 stones right. We are at the place with 3 stones. (6 seconds)

1111
.311
.111
Go to top left corner, move right, move 2 stones down. We are at the place with 5 stones. (+8 seconds)
..11
.511
.111
Go down, move up. We are at the place with 6 stones. (+3 seconds)
..11
.611
..11
Go to top right corner, move stones two times to the left, then down. (+13 seconds)
....
.811
..11
Do the same with the two stones in the last row. (+13 seconds) Then go twice to the right, move the two stones to the pile. (+8 seconds).

Total time: 51 seconds.

| improve this answer | |
$\endgroup$
  • $\begingroup$ @SOLO thanks, corrected $\endgroup$ – daw Feb 12 at 19:56
1
$\begingroup$

Going directly from A to B (the distance being $d$) while carrying $2n+m$ ($m<2$) stones takes $(4n+2m)d$ while you're carrying stones, and $(n-1+m)d$ while your hands are free, so you have to spend $(5n+3m-1)d$ seconds.

If you want to go from A to C with the possibility to drop some weight on B, you can just ignore it and spend $(5n+3m-1)d$ seconds like before, but you end up taking no less time with the other option.

In an open chain of adjacent cells, let's look at how long it will take to move stuff from consecutive cells and put it into the last cell:

Cells..........Time...................................Result...........Total Time
1..................1*2=2................................2......................2
2..................2=2*1+0, 5*1+0*3-1=4......3......................6
3..................3=2*1+1, 5*1+1*3-1=7......4.....................13
4...................9..............................................................22
5..................12.............................................................34
6..................14.............................................................48
7..................17.............................................................65
8..................19.............................................................84
9..................22...........................................................106
10................24...........................................................130

It takes longer to take one stone from two adjacent cells each and move it to the third cell than just going to the first cell and moving all the stones along the way. However, you can otherwise save your total time by completing smaller chains adding up to a larger chain's "cell" no if the path has a lot of twists and turns. Also, the closer the destination cell is the center, the better.

...S
.F..
....

It takes 13+2+6+2+6+2+6+3+6+4=50 seconds to clear the non-dotted cells and then finish up the two dots:

baaa
bFd.
ccd.


Prove you can't do any better:

You move everything into a single cell. Since you can move $x$ stones in $2x$ seconds by one cell at least, you can get a conservative estimate by measuring the distances to the destination:

F123
1234
2345

1F12
2123
3234

1234
F123
1234

2123
1F12
2123

In the first board, the total distance is 30, making the minimum time 30*2=60 and the destination suboptimal. The second gives 48, the third 52 (you have to go back with free hands at some point, so we can rule it out too), and the fourth 40. In the second case, even if you bulldoze away two cells, you can add two stones to the destination at most in every trip to the cell without free-hand travels, making you take more than 4 secs in free-hand travels. The fourth destination must be the correct one, and if we can prove free-hand travels never take less than 10 seconds in less than 50 in total, it will be even better.

Bulldozing more than 3 cells at a time is just plain impractical when you have better options.

If you start from the left side, you'll have to travel to the other corners yourself (3+3+2=8 secs). You shouldn't put yourself in a position to travel to the middle cell in the rightmost column again, so you'll end up leaving a gap to the diagonal right cells of the destination no matter what (another 2 seconds, ie. at least 50).

If you start from the right side, you'll have to travel to the other corners by yourself (3+2+2=7 secs). The first travel to the destination with stones includes 1 free-hand second. After that, you shouldn't put yourself in a position to travel to the middle cell in the rightmost column again, so you'll end up leaving a gap to the diagonal right cells of the destination no matter what (another 2 seconds, ie. at least 50).

| improve this answer | |
$\endgroup$

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.