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.
źródło
Odpowiedzi:
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:
Kod może być znacznie bardziej golfowy, ale lepsza jakość kodu motywuje dodatkowe odpowiedzi.
C ++ (501 bajtów)
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).
źródło
C
426448Sortuje 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.Wymaga wprowadzania bez nawiasów klamrowych lub przecinków, np
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):
I niekluczony kod, który również drukuje wynik:
źródło
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):
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:
źródło