11
\$\begingroup\$

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.
\$\endgroup\$
27
  • 2
    \$\begingroup\$ What's the point of denoting the destination when there is only one space you can move an apple to? \$\endgroup\$ Sep 13, 2014 at 6:20
  • \$\begingroup\$ What if my brute-force solution runs in a reasonable amount of time? There are only 700M states - easily enumerable in the matter of minutes. Define "reasonable amount of time". \$\endgroup\$ Sep 13, 2014 at 6:21
  • \$\begingroup\$ @JanDvorak Per "What's the point" - good call. That hadn't occurred to me. I'm defining reasonable here to be less than the amount of time required to brute force the solution ;) \$\endgroup\$
    – Orby
    Sep 13, 2014 at 6:23
  • \$\begingroup\$ Does your definition of "reasonable" mean we should first implement the brute-force solution, then anything that's faster counts? \$\endgroup\$ Sep 13, 2014 at 6:25
  • \$\begingroup\$ Is final order of bucket important? \$\endgroup\$
    – AMK
    Sep 13, 2014 at 6:26

3 Answers 3

4
\$\begingroup\$

Score: 448

My idea is to sort them consecutively, starting with 1. This gives us the nice property that when we want to move the space to the previous/next basket, we know exactly which of the two apples there we have to move - the max/min one, respectively. Here is the test breakdown:

#1: 62     #6: 40
#2: 32     #7: 38
#3: 46     #8: 50
#4: 50     #9: 54
#5: 40    #10: 36

Total score: 448 moves

The code can be golfed a lot more, but better quality of the code will motivate additional answers.

C++ (501 bytes)

#include <cstdio>
#define S(a,b) a=a^b,b=a^b,a=a^b;
int n=14,a[14],i,j,c,g,p,q;
int l(int x){for(j=0;j<n;++j)if(a[j]==x)return j;}
int sw(int d){
    p=l(0);q=p+d;
    if(a[q]*d>a[q^1]*d)q^=1;
    printf("%d,", a[q]);
    S(a[q],a[p])
}
int main(){
    for(;j<n;scanf("%d", a+j),j++);
    for(;++i<n;){
        c=l(i)/2;g=(i-1)/2;
        if(c-g){
            while(l(0)/2+1<c)sw(2);
            while(l(0)/2>=c)sw(-2);
            while(l(i)/2>g){sw(2);if(l(i)/2>g){sw(-2);sw(-2);}}
        }
    }
}

Further improvements may be switching to C and trying to lower the score by starting from the large values downwards (and them eventually combining both solutions).

\$\endgroup\$
3
  • 1
    \$\begingroup\$ A substring of your code already forms a C program. Specifically, it could work in C by simply deleting the first line. \$\endgroup\$
    – feersum
    Sep 13, 2014 at 8:31
  • \$\begingroup\$ @feersum You're right. At the beginning, I had more C++ specific code, but after that with the switch to C in mind, it seems I got rid of it. \$\endgroup\$
    – yasen
    Sep 13, 2014 at 8:42
  • \$\begingroup\$ Could you specify that you've changed the input format in your solution to make it more clear to those who try to verify it? \$\endgroup\$
    – Orby
    Sep 13, 2014 at 19:41
2
\$\begingroup\$

C, 426 448

This sorts apples one at a time from 1 to 13 similar to yasen's method, except whenever it has an opportunity to move a larger number up or a smaller number down, it will take it. Sadly, this only improves performance on the first test problem, but its a small improvement. I made a mistake when running the test problems. It seems I've simply reimplemented yasen's method.

#1: 62    #6: 40
#2: 32    #7: 38
#3: 46    #8: 50
#4: 50    #9: 54
#5: 40    #10: 36

It takes input without braces or commas, e.g.

8 2 11 13 3 12 6 10 4 0 1 7 9 5

Here is the golfed code coming in at 423 bytes counting a few unnecessary newlines (could probably be golfed more, but I expect this score to be beaten):

#define N 7
#define F(x,y) for(y=0;y<N*2;y++)if(A[y]==x)break;
#define S(x,y) x=x^y,y=x^y,x=x^y;
#define C(x,y) ((A[x*2]==y)||(A[x*2+1]==y))
A[N*2],i,j,d,t,b,a,n,s,v,u,w,g;main(){for(;i<N*2;i++)scanf("%d",A+i);g=1;while
(!v){F(0,i);b=i/2;F(g,u);w=u/2;d=b<w?1:-1;n=(b+d)*2;a=(b+d)*2+1;if(A[n]>A[a])
S(n,a);t=d-1?a:n;printf("%d,",A[t]);S(A[i],A[t]);while(C((g-1)/2,g))g++;v=1;for
(j=0;j<N*2;j++)if(!C(j/2,(j+1)%(N*2)))v=0;}}

And the ungolfed code, which also prints the score:

#include <stdio.h>
#include <stdlib.h>

#define N 7

int apples[N*2];

int find(int apple)
{
    int i;
    for (i = 0; i < N*2; i++) {
        if (apples[i] == apple)
            return i;
    }    
}

void swap(int i, int j)
{
    int temp;
    temp = apples[i];
    apples[i] = apples[j];
    apples[j] = temp;
}

int contains(int bucket, int apple)
{
    if ((apples[bucket * 2] == apple) || (apples[bucket * 2 + 1] == apple))
        return 1;
    return 0;
}

int is_solved()
{
    int i, j;
    for (i = 0; i < N * 2; i++) {
        j = (i + 1) % (N * 2);
        if (!contains(i / 2, j))
            return 0;
    }
    return 1;
}

int main()
{
    int i, j, dir, bucket, max, min, score;
    int target_i, target_bucket, target;

    /* Read the arrangement */
    for (i = 0; i < N*2; i++) {
        scanf("%d ", apples + i);
    }

    target = 1;
    while (1) {

        i = find(0);
        bucket = i / 2;
        target_i = find(target);
        target_bucket = target_i / 2;

        /* Change the direction of the sort if neccesary */
        if (bucket < target_bucket) dir = 1;
        else dir = -1;

        /* Find the biggest and smallest apple in the next bucket */
        if (apples[(bucket + dir) * 2] < apples[(bucket + dir) * 2 + 1]) {
            min = (bucket + dir) * 2;
            max = (bucket + dir) * 2 + 1;
        } else {
            min = (bucket + dir) * 2 + 1;
            max = (bucket + dir) * 2;
        }

        /* If we're going right, move the smallest apple. Otherwise move the
           biggest apple */
        if (dir == 1) {
            printf("%d, ", apples[min]);
            swap(i, min);
            score++;
        } else {
            printf("%d, ", apples[max]);
            swap(i, max);
            score++;
        }

        /* Find the next apple to sort */
        while (contains((target - 1) / 2, target))
            target++;

        /* If we've solved it then quit */
        if (is_solved())
            break;
    }
    printf("\n");
    printf("%d\n", score);
}
\$\endgroup\$
2
\$\begingroup\$

Python 3 - 121

This implements a depth-first searching with increasing depth until it finds a solution. It uses a dictionary to store visited states so that it doesn't visit them again unless with a higher depth window. When deciding which states to check, it uses the number of misplaced elements as a heuristic, and only visits the best states possible. Note that since the order of the elements within their bucket does not matter, it always maintains an ordering within the buckets. This makes it easier to check if an element is misplaced.

The input is an array of ints, with the first int being the number of buckets.

So for instance, for #8 (this one takes a very long time to run on my machine, the others finish in seconds):

c:\python33\python.exe apples.py 7 3 4 10 9 8 12 2 6 5 1 11 13 7 0

Here are the results on the test set: #1: 12, #2: 12, #3: 12, #4: 12, #5: 11, #6: 11, #7: 10, #8: 14, #9: 13, #10: 14

Here is the code:

import sys    

BUCKETS = int(sys.argv[1])    

# cleans a state up so it is in order
def compressState(someState):
  for i in range(BUCKETS):
    if(someState[2*i] > someState[2*i + 1]):
      temp = someState[2*i]
      someState[2*i] = someState[2*i + 1]
      someState[2*i + 1] = temp
  return someState    

state = compressState([int(x) for x in sys.argv[2:]])
print('Starting to solve', state)
WINNINGSTATE = [x for x in range(1, BUCKETS*2 - 1)]
WINNINGSTATE.append(0)
WINNINGSTATE.append(BUCKETS*2 - 1)
maxDepth = 1
winningMoves = []
triedStates = {}    

# does a depth-first search
def doSearch(curState, depthLimit):
  if(curState == WINNINGSTATE):
    return True
  if(depthLimit == 0):
    return False
  myMoves = getMoves(curState)
  statesToVisit = []
  for move in myMoves:
    newState = applyMove(curState, move)
    tns = tuple(newState)
    # do not visit a state again unless it is at a higher depth (more chances to win from it)
    if(not ((tns in triedStates) and (triedStates[tns] >= depthLimit))):
      triedStates[tns] = depthLimit
      statesToVisit.append((move, newState[:], stateScore(newState)))
  statesToVisit.sort(key=lambda stateAndScore: stateAndScore[2])
  for stv in statesToVisit:
    if(stv[2] > statesToVisit[0][2]):
      continue
    if(doSearch(stv[1], depthLimit - 1)):
      winningMoves.insert(0, stv[0])
      return True
  return False    

# gets the moves you can make from a given state
def getMoves(someState):
  # the only not-allowed moves involve the bucket with the 0
  allowedMoves = []
  for i in range(BUCKETS):
    if((someState[2*i] != 0) and (someState[2*i + 1] != 0)):
      allowedMoves.append(someState[2*i])
      allowedMoves.append(someState[2*i + 1])
  return allowedMoves    

# applies a move to a given state, returns a fresh copy of the new state
def applyMove(someState, aMove):
  newState = someState[:]
  for i in range(BUCKETS*2):
    if(newState[i] == 0):
      zIndex = i
    if(newState[i] == aMove):
      mIndex = i
  if(mIndex % 2 == 0):
    newState[mIndex] = 0
  else:
    newState[mIndex] = newState[mIndex-1]
    newState[mIndex-1] = 0
  newState[zIndex] = aMove
  if((zIndex % 2 == 0) and (newState[zIndex] > newState[zIndex+1])):
    newState[zIndex] = newState[zIndex+1]
    newState[zIndex+1] = aMove
  return newState    

# a heuristic for how far this state is from being sorted
def stateScore(someState):
  return sum([1 if someState[i] != WINNINGSTATE[i] else 0 for i in range(BUCKETS*2)])    

# go!
while(True):
  triedStates[tuple(state)] = maxDepth
  print('Trying depth', maxDepth)
  if(doSearch(state, maxDepth)):
    print('winning moves are: ', winningMoves)
    break
  maxDepth += 1
\$\endgroup\$
3
  • \$\begingroup\$ I've upvoted this because it is useful to see optimal solutions, but notice that this does not run in polynomial time in the number of buckets per move as required by the question. I don't believe that any algorithm which produces an optimal solution (in general) can run in polynomial time. \$\endgroup\$
    – Orby
    Sep 16, 2014 at 2:11
  • \$\begingroup\$ For the first test problem, your program generates 10, 8, 1, 12, 6, 7, 11, 3, 5, 13, 4, 9, which is not a valid solution. I think you may have misunderstood the question. Notice the question states that "You can move any apple from one bucket to an adjacent bucket" i.e. the bucket to the right or left of it (not an arbitrary bucket). \$\endgroup\$
    – Orby
    Sep 16, 2014 at 4:09
  • \$\begingroup\$ Oh, I totally missed the adjacency restriction! After I posted this I had a nagging suspicion that the running time restriction was violated too. I wasn't 100% sure as I was writing it, because the dynamic programming element of avoiding repeated states confused me. Thanks for the upvote even though this fails on two counts; this is a fun puzzle and I'll see if I can come up with a better, valid answer. \$\endgroup\$
    – R.T.
    Sep 16, 2014 at 13:26

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.