Istnieje 40 sposobów, w jakie ukierunkowana ścieżka hamiltonowska może być ułożona na siatce 3 × 3:
Ta grafika ( dzięki Sp3000! ) Pokazuje tylko 20 nieukierowanych ścieżek. Przemierzaj każdą kolorową linię w obu kierunkach dla 40 kierowanych ścieżek.
Wyzwanie
Używając tylko ASCII do wydruku , napisz siatkę znaków 3 × 3, na przykład:
ABC
DEF
GHI
Gdy każda z 40 kierowanych ścieżek jest odczytywana z tej siatki jako 40 jednowierszowych, 9-znakowych programów, celem jest, aby każdy program wyświetlał unikalną liczbę całkowitą od 1 do 40. Wykonanie tego dla wszystkich 40 ścieżek wydaje się trudne i mało prawdopodobne, więc musisz tylko sprawić, by działał na jak największej liczbie ścieżek.
Zwycięzcą zostanie zgłoszenie, którego 40 programów ścieżek wyprowadzi najbardziej wyraźne liczby od 1 do 40. Tiebreaker przechodzi do wcześniejszego zgłoszenia.
Programy ścieżek, które popełniają błąd lub nie wypisują liczb całkowitych od 1 do 40 lub wypisują liczby całkowite, których nie obejmuje już inny program ścieżek, nie są liczone. Konkretnie:
- Programy z błędami podczas kompilacji, uruchamiania lub wychodzenia nie są liczone. Ostrzeżenia są w porządku.
- Programy, które nie wypisują liczb całkowitych od 1 do 40 lub wyprowadzają coś nieznacznie zniekształconego, takie jak
-35
lub35 36
nie są liczone. - Programy wymagające danych wejściowych od użytkownika, aby wygenerować dane wyjściowe, nie są liczone.
- Programy, które nigdy się nie kończą, nie są liczone.
- Od teraz na programy, które nie są deterministyczne nie są liczone.
- W przeciwnym razie prawidłowe programy, które generują liczbę całkowitą od 1 do 40, którą inny prawidłowy program już wypisał, nie są liczone. (Pierwszy program jest liczony.)
- Tylko programy, które generują liczby całkowite reprezentujące liczby od 1 do 40 (włącznie) są liczone do twojej sumy. Oczekuje się, że liczby będą miały zwykły
1
,2
...39
,40
format, chyba że nie jest to normą dla twojego języka. (Końcowy znak nowej linii w wyjściu jest w porządku). - Liczba numerów wyjściowych programów i ich kolejność nie ma znaczenia. Liczy się tylko liczba różnych liczb całkowitych z prawidłowych programów.
Wszystkie programy ścieżki muszą być uruchamiane w tym samym języku. Jednak „programami” mogą być w rzeczywistości funkcje (bez wymaganych argumentów) lub polecenia REPL , a także pełne programy, które wypisują lub zwracają docelową liczbę całkowitą. Możesz mieszać i dopasowywać funkcje, polecenia REPL i pełne programy.
Twoje 9 drukowalnych znaków ASCII nie musi być rozróżnionych.
Przykład
Jeśli twoja siatka 3 × 3 była
ABC
DEF
GHI
a twoje 40 programów i wyników wyglądało tak
ABCFEDGHI -> 26
ABCFIHEDG -> 90
ABCFIHGDE -> 2
ABEDGHIFC -> syntax error
ADEBCFIHG -> prints 40 but then errors
ADGHEBCFI -> 6
ADGHIFCBE -> 6
ADGHIFEBC -> 6
CBADEFIHG -> runtime error
CBADGHEFI -> 3
CBADGHIFE -> 4
CFEBADGHI -> -32
CFIHEBADG -> 38.0
CFIHGDABE -> "36"
EDABCFIHG -> 33
EFCBADGHI -> no output
EHGDABCFI -> compilation error
EHIFCBADG -> 8
GDABCFEHI -> 22
GHEDABCFI -> 41
IHGDEFCBA -> 0
GDEHIFCBA -> '9'
EDGHIFCBA -> +10
CFIHGDEBA -> 11
GHIFCBEDA -> error
IFCBEHGDA -> error
EBCFIHGDA -> prints 23 but then loops infinitely
CBEFIHGDA -> randomly prints either 24 or 44
GHIFEDABC -> error
IFEHGDABC -> 30
EFIHGDABC -> 39
IHGDABEFC -> 7
GDABEHIFC -> 29
EBADGHIFC -> -1
GHIFCBADE -> 26
IHGDABCFE -> 1
IFCBADGHE -> error
GDABCFIHE -> no output
IHEFCBADG -> no output
IFCBADEHG -> "quack"
Twój wynik wyniósłby 14, ponieważ istnieje 14 różnych liczb całkowitych od 1 do 40 prawidłowych danych wyjściowych, a mianowicie 26 2 6 3 4 33 8 22 11 30 39 7 29 1
.
źródło
123654789
Odpowiedzi:
PARI / GP - 24
PARI / GP ignoruje spacje między cyframi, więc
1 8 2
na przykład jest traktowany jako182
. To samo może działać dla Perla, zastępując spacje podkreśleniami. Nie wyczerpałem całej przestrzeni wyszukiwania, więc mogą być lepsi kandydaci.Program może być dostarczony do gp jako
gp -q -f program.gp
lub interaktywnie w repl.Wydajność
Wszystkie wartości oprócz 4 mieszczą się w wymaganym zakresie, z 12 zduplikowanymi wpisami.
Aktualizacja
Skończyłem chrupanie, jest sześć różnych 23 i tylko jedna 24 (czytana wierszami):
Program, którego użyłem do chrupania, jest poniżej. PARI / GP ma ograniczone możliwości przetwarzania łańcucha znaków, więc radzą sobie głównie z tablicami znaków (aka
Vecsmall
). Badane operatorzy+
,-
,*
,\
(Gr podłogi)%
,;
(rozdzielacz ekspresji zasadniczo usuwa wszystko przed nim) i(miejsca, jak to opisano powyżej).
^
Można również dodać operatora wykładnika , ale staje się on zbyt wolny, aby przeprowadzić wyczerpujące testy.źródło
Deadfish , 18
To był właściwie pierwszy język, którego wypróbowałem, zanim wziąłem pod uwagę operatorów infix. Publikuję to teraz dla samej wesołości na myśl, że Deadfish może być do czegoś przydatny.
Dla tych, którzy nie znają Deadfisha,
i
jest to przyrost,s
jest kwadratowy io
jest wyprowadzany, a akumulator zaczyna się od 0 (nie ma tu również czwartej instrukcjid
dekrementacji). Fakt, że nie mamy automatycznego drukowania i musimy go używać,o
jest główną wadą, ale zaskakująco Deadfish nie robi tutaj zbyt strasznie, biorąc pod uwagę wszystkie te kwestie. Okazuje się, że optymalne ustawienie operatora wyjściowego znajduje się na środku.źródło
Python REPL i wiele innych,
2223Najważniejsze spostrzeżenie: jeśli pokolorujesz siatkę jak szachownicę, ścieżka naprzemiennie zmienia kolor siatki, gdy idzie i zaczyna się i kończy na tym samym kolorze.
Wciąż brutalne wymuszanie na lepsze.Próbowanie z+*%
(a nawet w**
przypadku języków, w których^
występuje potęgowanie) niestety nie przyniosło nic lepszego. Próbowałem także wrzucać bitowe operatory i tylko^
(xor) wydawało się łagodnie pomagać, ale wyszukiwanie trwało zbyt długo, więc się poddałem.źródło
6+7*5%6%4
,6+7*4%6%5
i6+8*4%6%5
(od lewej do prawej, od góry do dołu), i nic więcej.+
i-
na rogach / centrum? Ponieważ są one zarówno jednoargumentowe, jak i operatory binarne, powinno to nadal skutkować wszystkimi prawidłowymi wyrażeniami. Jest mało prawdopodobne, że przyniesie lepsze rozwiązanie, ale przynajmniej powiększy przestrzeń wyszukiwania. Hmm, to może być problem, ponieważ możesz skończyć z sekwencjami operatorów.J, 15
Daje to tylko prawidłowe liczby, ale wiele z nich to duplikaty. Unikalne wartości to
17 11 16 28 31 23 13 10 21 33 18 24 22 29 27
. Możesz zdecydowanie lepiej, zmieniając operatorów i zaangażowane liczby całkowite.źródło
Yes
.> <>, 36 *
Jeśli masz szczęście!
Ponieważ wyzwanie nie wymaga deterministycznego kodu, musimy jedynie udowodnić, że możliwe jest (nawet jeśli jest to nieprawdopodobne) zwrócenie 36 liczb i gotowe.To chyba dobrze, dopóki trwało.(Dla tych, którzy nie znają> <>, świetne wprowadzenie można znaleźć tutaj )
Zdecydowałem się użyć instrukcji „x” w> <>, która losowo zmienia kierunek wskaźników instrukcji w górę, w dół, w lewo lub w prawo. Ponieważ nasz kod będzie tylko jedną linią, oznacza to, że możemy patrzeć tylko na przypadki, gdy idzie w prawo lub w lewo, ponieważ jeśli wskaźnik wzrośnie lub spadnie, po prostu ponownie uderzy w instrukcję „x”.
Instrukcja „n” wyskakuje na górze stosu i drukuje go. Jeśli jednak stos jest pusty i nie ma nic do wyskoczenia, pojawia się błąd.
Instrukcja „l” po prostu przesuwa długość stosu na stos (i na szczęście dla nas nie wysyła błędu, jeśli stos jest pusty), więc na przykład, jeśli stos byłby pusty i wywołano by „l”, to pchnąłby 0 na stosie. Gdybyśmy teraz ponownie wywołali „l”, to ponieważ stos zawiera jeden element (0), wypchnąłby 1 na górę stosu, a teraz oznaczałoby to, że na stosie byłyby dwie rzeczy, a to oznaczałoby, że jeśli mielibyśmy ponownie wywołać „l”, wcisnęlibyśmy 2 na stos itp. Możemy więc użyć „l”, aby wypchnąć dowolny numer na stos za pomocą metody pokazanej wcześniej.
„;” instrukcja kończy program.
Pomysł użycia „x” polega na tym, że na przykład, jeśli w kodzie było tylko jedno „x” (gdzie A, B, C, D to niektóre instrukcje):
Program wykonałby A, a następnie B, a następnie C, a po osiągnięciu „x” mielibyśmy dwie możliwości: kod albo nadal idzie w prawo i uderza w „;” i wychodzi lub idzie w lewo i wykonuje C, a następnie A, a następnie D i dopiero potem wychodzi. Więc jeśli nasz kod zawiera jeden „x”, program uzyskuje dwa możliwe przepływy programu, z których możemy wybrać najbardziej odpowiedni program.
Jeśli są dwa lub więcej znaków „x”, wówczas uzyskujemy nieskończoną liczbę możliwych przepływów programu.
Nasz kod ma pięć znaków „x”, ponadto każdy z nich znajduje się w „początkowej komórce” ścieżek hamiltonowskich, co oznacza, że każdy program rozpocznie się od „x”, a każdy program będzie miał strukturę:
Gdzie A, B, C, D należą do {; , n, l, l} Oznacza to, że istnieje tylko 12 unikalnych programów. Ponadto, ponieważ zawsze zaczynamy od litery „x”, możemy spojrzeć na przypadek, gdy program odchodzi w lewo, więc programy symetryczne można również traktować tak samo. Do symetrii istnieje tylko 6 różnych możliwych programów. Tylko 4 z nich występują w programach generowanych jako ścieżki hamiltonowskie:
Spójrzmy na pierwszy program „xnxlxlx; x”, jeśli pójdziemy od razu w pierwszym kroku, uderzymy w komendę print, która spowoduje błąd, ponieważ nie mamy nic na stosie. Jeśli pójdziemy w lewo, uderzymy w polecenie zakończenia programu. Dlatego nie możemy wyprowadzić żadnej liczby z tych programów.
Drugi program, „xlxnxlx; x”, jest o wiele bardziej obiecujący, ponieważ po przejściu w prawo na początku zero jest umieszczane na stosie, jeśli następnie pójdziemy w lewo przy następnym „x”, nasz stos zyskuje jeden, a następnie idąc znowu w prawo mamy 2, które możemy następnie wydrukować i kontynuować od razu, aby zakończyć program. Możemy zaobserwować, że faktycznie możemy wydrukować dowolną liczbę parzystą , ponieważ w części „xlx” na początku możemy osiągnąć pewną liczbę dowolnych rozmiarów, przechodząc w prawo, a potem w lewo, a następnie ponownie w określoną liczbę razy.
Podobnie można zauważyć, że trzeci program xnxlx; xlx może wypisać dowolną liczbę nieparzystą , przechodząc w lewo na początku, a następnie powtarzając procedurę „xlx” tylko tym razem w lewo, a potem w prawo, a potem w lewo.
Czwarty program jest zasadniczo taki sam jak drugi program i może generować dowolną liczbę parzystą .
Tak więc dla wymaganych programów mamy:
To 4 programy, które nie mogą wyprowadzić liczb wyjściowych, 20, które mogą wypisać dowolną liczbę parzystą, 16, które mogą wypisać dowolną liczbę nieparzystą. Ponieważ istnieje dokładnie 20 liczb parzystych i co najmniej 16 liczb nieparzystych w zakresie od 1 do 40, to z pewnym prawdopodobieństwem istnieje możliwość, że przez ten blok kodu będzie 36 różnych liczb w zakresie od 1 do 40.
źródło
GolfScript, 8
Obecnie najwyższe rozwiązanie punktowe. : PByło miło, dopóki trwało.Programy
źródło
0)1#2#3(4
15 lat. Piękna symetria też.CJam, 14
Poniżej działających programów:
Generowane wartości to: [1, 3, 4, 11, 13, 14, 20, 21, 22, 23, 24, 30, 31, 33]
źródło
dc (20)
32 wyjścia, 20 z nich odrębnych (oznaczonych a
$
)2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 16, 20, 22, 24, 25, 32, 34, 40
źródło