Masalah

Bayangkan 7 ember berbaris berturut-turut. Setiap ember dapat memuat paling banyak 2 apel. Ada 13 apel berlabel 1 hingga 13. Mereka didistribusikan di antara 7 ember. Sebagai contoh,

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

Di mana 0 mewakili ruang kosong. Urutan di mana apel muncul dalam setiap ember tidak relevan (misalnya {5,4} setara dengan {4,5}).

Anda dapat memindahkan apel apa pun dari satu ember ke ember yang berdekatan, asalkan ada ruang di ember tujuan untuk apel lain. Setiap gerakan dijelaskan oleh jumlah apel yang ingin Anda pindahkan (yang tidak ambigu karena hanya ada satu ruang kosong). Misalnya, menerapkan langkah

7

dengan pengaturan di atas akan menghasilkan

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

Objektif

Tulis program yang membaca pengaturan dari STDIN dan mengurutkannya ke dalam pengaturan berikut

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

menggunakan gerakan sesedikit mungkin. Sekali lagi, urutan di mana apel muncul dalam setiap ember tidak relevan. Urutan ember tidak masalah. Seharusnya menampilkan gerakan yang digunakan untuk mengurutkan setiap pengaturan yang dipisahkan oleh koma. Sebagai contoh,

13, 7, 6, ...

Skor Anda sama dengan jumlah jumlah gerakan yang diperlukan untuk menyelesaikan pengaturan berikut:

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

Ya, masing-masing pengaturan ini memiliki solusi.

Aturan

• Solusi Anda harus dijalankan dalam waktu polinomial dalam jumlah ember per gerakan. Intinya adalah menggunakan heuristik pintar.
• Semua algoritma harus deterministik.
• Jika terjadi seri, hitungan byte terpendek akan menang.

Nilai: 448

Ide saya adalah untuk mengurutkannya secara berurutan, dimulai dengan 1. Ini memberi kita properti bagus bahwa ketika kita ingin memindahkan ruang ke keranjang sebelumnya / berikutnya, kita tahu persis mana dari dua apel yang harus kita pindahkan - maks / min satu, masing-masing. Berikut ini adalah rincian tesnya:

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

Total score: 448 moves

Kode ini dapat lebih banyak bermain golf, tetapi kualitas kode yang lebih baik akan memotivasi jawaban tambahan.

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

Perbaikan lebih lanjut mungkin beralih ke C dan mencoba untuk menurunkan skor dengan mulai dari nilai-nilai besar ke bawah (dan mereka akhirnya menggabungkan kedua solusi).

C, 426 448

Jenis apel ini satu per satu dari 1 hingga 13 mirip dengan metode yasen , kecuali setiap kali ia memiliki peluang untuk memindahkan jumlah yang lebih besar ke atas atau jumlah yang lebih kecil ke bawah, ia akan menerimanya. Sayangnya, ini hanya meningkatkan kinerja pada masalah tes pertama, tetapi peningkatan kecil. Saya membuat kesalahan saat menjalankan masalah tes. Sepertinya saya sudah cukup menerapkan metode yasen.

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

Dibutuhkan input tanpa kawat gigi atau koma, mis

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

Berikut adalah kode golf yang datang dengan kecepatan 423 byte yang menghitung beberapa baris baru yang tidak perlu (mungkin bisa lebih banyak golf, tetapi saya berharap skor ini dapat dikalahkan):

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

Dan kode ungolfed, yang juga mencetak skor:

#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

Ini mengimplementasikan pencarian kedalaman-pertama dengan meningkatkan kedalaman hingga menemukan solusi. Ini menggunakan kamus untuk menyimpan status yang dikunjungi sehingga tidak mengunjunginya lagi kecuali dengan jendela kedalaman yang lebih tinggi. Saat memutuskan negara mana yang akan diperiksa, ia menggunakan jumlah elemen yang salah tempat sebagai heuristik, dan hanya mengunjungi negara terbaik. Perhatikan bahwa karena urutan elemen dalam ember mereka tidak masalah, ia selalu mempertahankan pemesanan dalam ember. Ini membuatnya lebih mudah untuk memeriksa apakah suatu elemen salah tempat.

Input adalah array int, dengan int pertama adalah jumlah ember.

Jadi misalnya, untuk # 8 (yang ini membutuhkan waktu sangat lama untuk berjalan di komputer saya, yang lain selesai dalam hitungan detik):

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

Berikut adalah hasil pada set tes: # 1: 12, # 2: 12, # 3: 12, # 4: 12, # 5: 11, # 6: 11, # 7: 10, # 8: 14, # 9: 13, # 10: 14

Ini kodenya:

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