分拣几个苹果！

Question

问题

想象一下，7个水桶排成一排。每个桶最多可盛2个苹果。有13个苹果标记为1到13，它们分布在这7个桶中。例如,

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

其中0表示空空间。苹果出现在每个桶中的顺序与此无关(例如，{5,4}相当于{4,5})。

你可以把任何苹果从一个桶移到一个相邻的桶里，前提是目的地桶里有另一个苹果的空间。每一个动作都是用你想移动的苹果数量来描述的(这是明确的，因为只有一个空空间)。例如，应用移动

7

到上面的安排会导致

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

目标

编写程序，从STDIN读取安排并将其排序为以下安排

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

使用尽可能少的动作。同样，苹果出现在每个桶里的顺序是不相关的。桶的顺序很重要。它应该输出用逗号分隔的每一种排列所用的动作。例如,

13, 7, 6, ...

您的分数等于解决下列安排所需的移动次数之和：

{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}

是的，每一种安排都有解决办法。

规则

• 您的解决方案必须以每次移动的桶数在多项式时间内运行。关键是要使用聪明的启发式方法。
• 所有算法都必须是确定性的。
• 如果出现平数，最短字节计数将获胜。

Answer 1

评分: 448

我的想法是连续排序，从1开始。这给了我们一个很好的特性，当我们想把空间移到前一个/下一个篮子时，我们确切地知道我们必须移动的两个苹果中的哪一个--最大/最小一个。这是测试的细目：

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

Total score: 448 moves

代码可以得到更多的支持，但是更好的代码质量会激发出更多的答案。

C++ (501个字节)

#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);}}
        }
    }
}

进一步的改进可能是切换到C，并试图通过从大值向下开始(并最终将这两种解决方案结合起来)来降低分数。

Answer 2

Python3-121

这实现了深度优先搜索和增加深度，直到它找到一个解决方案。它使用字典来存储已访问的状态，这样它就不会再次访问它们，除非具有更高的深度窗口。在决定要检查哪个状态时，它使用错位元素的数量作为启发，并且只访问尽可能好的状态。注意，因为元素在桶中的顺序并不重要，所以它总是在桶中保持顺序。这使得检查一个元素是否放错位置变得更容易了。

输入是一个int数组，第一个int是桶数。

例如，对于#8 (这个在我的机器上运行需要很长的时间，其他的在几秒钟内完成)：

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

以下是测试集的结果：#1: 12，#2: 12，#3: 12，#4: 12，#5: 11，#6: 11，#7: 10，#8: 14，#9: 13，#10: 14

以下是代码：

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