Problem
Imagine 7 buckets lined up in a row. Each bucket can contain at most 2 apples. There are 13 apples labeled 1 through 13. They are distributed among the 7 buckets. For example,
{5,4}, {8,10}, {2,9}, {13,3}, {11,7}, {6,0}, {12,1}
Where 0 represents the empty space. The order in which the apples appear within each bucket is not relevant (e.g. {5,4} is equivalent to {4,5}).
You can move any apple from one bucket to an adjacent bucket, provided there is room in the destination bucket for another apple. Each move is described by the number of the apple you wish to move (which is unambiguous because there is only one empty space). For example, applying the move
7
to the arrangement above would result in
{5,4}, {8,10}, {2,9}, {13,3}, {11,0}, {6,7}, {12,1}
Objective
Write a program that reads an arrangement from STDIN and sorts it into the following arrangement
{1,2}, {3,4}, {5,6}, {7,8}, {9,10}, {11,12}, {13,0}
using as few moves as possible. Again, the order in which the apples appear within each bucket is not relevant. The order of the buckets does matter. It should output the moves used to sort each arrangement seperated by commas. For example,
13, 7, 6, ...
Your score is equal to the sum of the number of moves required to solve the following arrangements:
{8, 2}, {11, 13}, {3, 12}, {6, 10}, {4, 0}, {1, 7}, {9, 5}
{3, 1}, {6, 9}, {7, 8}, {2, 11}, {10, 5}, {13, 4}, {12, 0}
{0, 2}, {4, 13}, {1, 10}, {11, 6}, {7, 12}, {8, 5}, {9, 3}
{6, 9}, {2, 10}, {7, 4}, {1, 8}, {12, 0}, {5, 11}, {3, 13}
{4, 5}, {10, 3}, {6, 9}, {8, 13}, {0, 2}, {1, 7}, {12, 11}
{4, 2}, {10, 5}, {0, 7}, {9, 8}, {3, 13}, {1, 11}, {6, 12}
{9, 3}, {5, 4}, {0, 6}, {1, 7}, {12, 11}, {10, 2}, {8, 13}
{3, 4}, {10, 9}, {8, 12}, {2, 6}, {5, 1}, {11, 13}, {7, 0}
{10, 0}, {12, 2}, {3, 5}, {9, 11}, {1, 13}, {4, 8}, {7, 6}
{6, 1}, {3, 5}, {11, 12}, {2, 10}, {7, 4}, {13, 8}, {0, 9}
Yes, each of these arrangements has a solution.
Rules
- Your solution must run in polynomial time in the number of buckets per move. The point is to use clever heuristics.
- All algorithms must be deterministic.
- In the event of a tie, the shortest byte count wins.