Problem

Wyobraź sobie 7 wiader ustawionych w rzędzie. Każde wiadro może zawierać maksymalnie 2 jabłka. Istnieje 13 jabłek oznaczonych od 1 do 13. Są one rozdzielone między 7 wiader. Na przykład,

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

Gdzie 0 oznacza puste miejsce. Kolejność pojawiania się jabłek w każdym wiadrze nie jest istotna (np. {5,4} jest równoważny {4,5}).

Możesz przenieść dowolne jabłko z jednego wiadra do sąsiedniego wiadra, pod warunkiem, że jest miejsce w wiadrze docelowym na kolejne jabłko. Każdy ruch jest opisany numerem jabłka, które chcesz przenieść (co jest jednoznaczne, ponieważ jest tylko jedno puste miejsce). Na przykład zastosowanie ruchu

7

powyższe rozwiązanie spowodowałoby

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

Cel

Napisz program, który odczyta zestawienie ze STDIN i posortuje go w następujący sposób

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

używając jak najmniej ruchów. Ponownie kolejność, w której jabłka pojawiają się w każdym wiadrze, nie ma znaczenia. Kolejność wiader ma znaczenie. Powinien generować ruchy używane do sortowania każdego układu oddzielonego przecinkami. Na przykład,

13, 7, 6, ...

Twój wynik jest równy sumie liczby ruchów wymaganych do rozwiązania następujących układów:

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

Tak, każde z tych rozwiązań ma rozwiązanie.

Zasady

• Twoje rozwiązanie musi działać w czasie wielomianowym w liczbie segmentów na ruch. Chodzi o to, by użyć sprytnej heurystyki.
• Wszystkie algorytmy muszą być deterministyczne.
• W przypadku remisu wygrywa najkrótsza liczba bajtów.

Wynik: 448

Moim pomysłem jest sortowanie ich kolejno, zaczynając od 1. Daje nam to miłą właściwość, że kiedy chcemy przenieść przestrzeń do poprzedniego / następnego koszyka, wiemy dokładnie, które z dwóch jabłek musimy przenieść - max / odpowiednio min. Oto podział testu:

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

Total score: 448 moves

Kod może być znacznie bardziej golfowy, ale lepsza jakość kodu motywuje dodatkowe odpowiedzi.

C ++ (501 bajtów)

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

Dalszymi ulepszeniami może być przejście na C i próba obniżenia wyniku, zaczynając od dużych wartości w dół (i ostatecznie łącząc oba rozwiązania).

C 426 448

Sortuje jabłka pojedynczo od 1 do 13, podobnie jak metoda yasen , z wyjątkiem przypadków, gdy ma możliwość przesunięcia większej liczby w górę lub mniejszej liczby, zabierze ją. Niestety poprawia to tylko wydajność pierwszego problemu testowego, ale jest to niewielka poprawa. Popełniłem błąd podczas uruchamiania problemów testowych. Wygląda na to, że po prostu ponownie wdrożyłem metodę yasen.

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

Wymaga wprowadzania bez nawiasów klamrowych lub przecinków, np

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

Oto kod do gry w golfa o długości 423 bajtów, zliczający kilka niepotrzebnych nowych linii (prawdopodobnie można by grać w golfa więcej, ale spodziewam się, że ten wynik zostanie pobity):

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

I niekluczony kod, który również drukuje wynik:

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

Python 3 - 121

To wdraża wyszukiwanie od pierwszej głębokości z rosnącą głębokością, aż znajdzie rozwiązanie. Używa słownika do przechowywania odwiedzonych stanów, aby nie odwiedzał ich ponownie, chyba że ma okno o większej głębokości. Przy podejmowaniu decyzji, które stany sprawdzić, wykorzystuje liczbę źle umieszczonych elementów jako heurystykę i odwiedza tylko najlepsze możliwe stany. Należy pamiętać, że ponieważ kolejność elementów w ich segmencie nie ma znaczenia, zawsze zachowuje porządek w segmentach. Ułatwia to sprawdzenie, czy element nie został umieszczony.

Dane wejściowe to tablica liczb całkowitych, przy czym pierwszą liczbą całkowitą jest liczba segmentów.

Na przykład dla wersji 8 (ta zajmuje bardzo dużo czasu na mojej maszynie, pozostałe kończą się w kilka sekund):

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

Oto wyniki z zestawu testowego: # 1: 12, # 2: 12, # 3: 12, # 4: 12, # 5: 11, # 6: 11, # 7: 10, # 8: 14, # 9: 13, # 10: 14

Oto kod:

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