To pierwszy z serii wyzwań Island Golf. Następne wyzwanie
Biorąc pod uwagę wyspę w sztuce ASCII, wygeneruj optymalną ścieżkę do jej opłynięcia.
Wejście
Twój wkład będzie w prostokątną siatkę składającą się z dwóch znaków reprezentujących ląd i wodę. W poniższych przykładach ziemia jest #
i woda jest .
, ale możesz zastąpić dowolne dwa różne znaki, które chcesz.
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........
Zawsze będzie co najmniej jeden żeton ziemi. Wszystkie kafelki ziemi będą sąsiadować (tzn. Jest tylko jedna wyspa). Płytki wodne również będą przylegające (tj. Nie będzie żadnych jezior). Zewnętrzna krawędź siatki będzie stanowić płytki wodne. Kafelki lądowe nie zostaną połączone po przekątnej: tzn. Nigdy nie zobaczysz czegoś takiego
....
.#..
..#.
....
Wynik
Twój kod musi generować tę samą siatkę, z narysowanym najkrótszym okrążeniem . W poniższych przykładach narysowano ścieżkę dookoła o
, ale możesz zastąpić dowolną postać, o ile różni się ona od twoich postaci lądowych i wodnych.
Opłynięcie jest prosta krzywa zamknięta, sporządzony wyłącznie na płytki wodnych, które całkowicie otacza wszystkie płytki wylądować na siatce. Połączenia ukośne są dozwolone. Na przykład jest to opłynięcie powyższej wyspy (ale nie najkrótszej):
.ooooo.....
o..##.oo...
o.#####.o..
o.#######o.
o#########o
ooo#######o
..o#####.#o
..oo####..o
....oooooo.
Długość okrążenia oblicza się w następujący sposób: Dla każdej pary sąsiadujących ze sobą płytek na ścieżce, jeśli są one połączone poziomo lub pionowo, dodaj 1; jeśli są połączone po przekątnej, dodaj √2. Długość powyższej ścieżki wynosi 22 + 7√2 (≈ 31,9).
Najkrótsza opłynięcie jest opłynięcie z najkrótszym długości. Twój program powinien wypisać dowolną ścieżkę, która spełnia ten warunek. W przypadku większości wysp istnieje wiele możliwych rozwiązań. Oto jedno rozwiązanie dla powyższej wyspy o długości 10 + 13√2 (≈ 28,4):
...oo......
..o##oo....
.o#####oo..
.o#######o.
o#########o
.o.#######o
..o#####.#o
...o####.o.
....ooooo..
Detale
Twoje rozwiązanie może być pełnym programem lub funkcją . Każda z domyślnych metod wejścia i wyjścia jest akceptowalna.
Dane wejściowe i wyjściowe mogą być ciągiem wieloliniowym lub listą ciągów. Jeśli twój język ma inny typ znaków niż ciągi jednoznakowe, możesz zastąpić „listę znaków” wyrazem „ciąg” w poprzednim zdaniu. Jeśli twój język musi wprowadzić wysokość i / lub szerokość siatki, możesz to zrobić. Twój wynik może (opcjonalnie) mieć jeden końcowy znak nowej linii. Jak wspomniano powyżej, możesz użyć dowolnych trzech różnych znaków zamiast #.o
(w zgłoszeniu określ, których znaków używasz).
Przypadki testowe
A. Wyspy z unikalnymi najkrótszymi opłynięciami:
...
.#.
...
.o.
o#o
.o.
......
.####.
......
.oooo.
o####o
.oooo.
......
......
..##..
...#..
......
......
......
..oo..
.o##o.
..o#o.
...o..
......
.......
.#####.
...#...
...#...
.#####.
.......
.ooooo.
o#####o
o..#..o
o..#..o
o#####o
.ooooo.
.......
...#...
...#...
.#####.
...#...
...#...
.......
...o...
..o#o..
.o.#.o.
o#####o
.o.#.o.
..o#o..
...o...
.......
.#####.
.##..#.
..#..#.
.......
.ooooo.
o#####o
o##..#o
.o#..#o
..oooo.
B. Przykład wyspy z wieloma możliwymi rozwiązaniami:
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........
Możliwe wyniki:
....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##oo..
..oo....
....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##.o..
..ooo...
....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##oo..
..oo....
....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##.o..
..ooo...
C. Duży przypadek testowy jako Gist
To jest golf-golf : wygrywa najkrótszy kod w każdym języku.
Odpowiedzi:
Mathematica (wersja 9), 165 bajtów
Ładna, krótka
ConvexHullMesh
funkcja, której używał Greg Martin, została wprowadzona tylko w wersji Mathematica 10, więc pomyślałem, że spróbuję bez niej, używając mojej starożytnej wersji Mathematica 9. Udało mi się jednak nieco ją skrócić! Jest to funkcja, która przyjmuje i zwraca listę łańcuchów (z.
,#
io
jako symbole).Wyjaśnienie:
Characters@# /. {"."->0, "#"->1}
zamienia dane wejściowe na macierz0
s i1
s."o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#
następnie wykorzystuje potężne (ale wyjątkowo duże bajt…) możliwości przetwarzania obrazu Mathematiki, aby najpierw wypełnić wypukły kadłub wyspy (taki kształt uzyskałbyś, gdybyś rozciągnął wokół niego kawałek sznurka), a następnie wyznaczył granicę. Następnie mnożymy tę macierz przez ciąg,"o"
aby uzyskać macierz0
s i"o"
s (dzięki imponującej zdolności Mathematica do dostosowywania typów), i dodajemy to do"#"
macierzy wyspy.""<>#& /@ (... /. {0->"."})
zamienia tę macierz"o"
s,"#"
si0
na macierz"o"
s,"#"
si"."
i łączy każdy wiersz w ciąg.Kiedy testujemy to na przykładzie B , otrzymujemy wynik
[Edytuj, dzięki Gregowi Martinowi:] Jeśli wolno nam używać tablic znaków zamiast list ciągów, możemy przyciąć to do 144 bajtów:
źródło
MorphologicalComponents[#, Method->"ConvexHull"]
:) Możesz zaoszczędzić jeszcze więcej bajtów, zakładając, że dane wejściowe są już podzielone na znaki, a także zwracając tablicę znaków 2D.MorphologicalComponents
!f[{"...",".#.","..."}]
i wystąpiły błędy.f
. (Cóż, ściśle mówiąc, to jest to po średniku.) Aby wywołać funkcję, wpisz całą rzecz do okna Mathematica, a następnie[
swoje dane wejściowe, a]
więc powinno to wyglądać mniej więcej tak:f@m_:=m(1-m[[2,2]]) . . . #/.{"."->0,"#"->1}]&[{"...", ".#.", "..."}]
(skrót od spacji).(Ale przejdź do rozwiązania Notatree , lepiej!)
Mathematica, 168 bajtów
Czysta funkcja przyjmująca tablicę znaków 2D jako dane wejściowe i zwracająca tablicę znaków 2D. Wersja łatwiejsza do odczytania:
Linia 1 definiuje funkcję,
n
która wytwarza (najmniejszą) odległość między punktemx
na płaszczyźnie a zestawemy
innych punktów. Wiersz 2 inicjuje zmiennąi
na wejściu, zarówno w celu późniejszego rozwiązania niejednoznaczności curry, jak i możliwości modyfikacji jej w celu uzyskania ostatecznego wyniku; wiersz 2 definiuje również funkcję,p
która zwraca współrzędne wszystkich wystąpień jej wejściai
.W linii 3
p["#" | "."]
reprezentuje każdą współrzędną z mapy wejściowej (ponieważ wszystkie jej znaki są albo"#"
albo"."
), więct
jest funkcją, która wybiera tylko te współrzędne, które spełniają jeszcze nieokreśloną właściwość. W wierszu 4i~Part~## = "o"
zmienią kilka wpisówi
postaci"o"
; znaki te zostaną wybrane z zestawu możliwych współrzędnych zgodnie z materiałami w liniach 5-8. A linia 9 po prostu zwraca odpowiedź po jej obliczeniu.Dobra, infrastruktura zakończona, teraz do faktycznego obliczenia.
ConvexHullMesh
jest wbudowanym programem Mathematica do obliczania wypukłego kadłuba zestawu punktów (najmniejszego wypukłego wielokąta zawierającego te punkty). Moralnie rzecz biorąc, powinno to „wypełnić” zatoczki i fiordy wyspy (która jests = p@"#"
), aby wykluczyć je z naszej cykli nawigacji. Jest mały problem zConvexHullMesh
tym, kiedy ten zestaw punktów jest w linii (dziękuję, przypadek testowy nr 2), który rozwiązujemy, dodając nieco przesuniętą wersjęs
do siebie w linii 7. To wyjście jest wielokątem, więc linie 7 -9 (t[...~RegionMember~# &]
) tworzy listę punktów o współrzędnych całkowitych w tym wielokącie. Wreszcie, linia 5 i koniec linii 9 obliczają wszystkie punkty, które znajdują się w odległości dokładnie 1 (stąd nie 0) od tego zestawu punktów całkowitych; ten zestaw staje się ścieżką okrężną.Poniżej znajduje się wynik dla dużego przypadku testowego na łączu PO. Zwróć uwagę na lewy górny róg, niezwykłe wybory, kiedy wybrać się na zachód, a na południowy zachód, wskazując na fakt, że zasłania niewidzialną linię nachylenia -2/3 między dwoma półwyspami (wspomniany odcinek linii jest częścią granicy wypukłego kadłuba).
źródło
char
typ; w takim przypadkuchar
zamiast łańcucha można zastosować tablicę.Python 3, 779 bajtów (wcięcie za pomocą tabulatorów)
To jest cały program. Odczytuje dane wejściowe ze standardowego wejścia i drukuje je na standardowe wyjście. Stdin musi kończyć się EOF. Przykład uruchom z dużym wejściem: https://ideone.com/XIfYY0
Pomysł jest prosty: oblicza najmniejsze ośmiokątne granice i rysuje komórki, które znajdują się we wszystkich obliczonych granicach i przecinają co najmniej jedną krawędź.
źródło
sys.stdin
jako danych wejściowych.input()
, uzyskanie multilinii wykonałoby zadanie i kosztowało mniej bajtówR(0,x)
zR(x)
P
if
;L(generator expression)
=>[generator expression]
;F
,r
iB
wydają się być używane tylko raz na sztukę, dzięki czemu można je wstawiać.JavaScript (ES6),
369343 bajtówObjaśnienie: Łańcuch jest podzielony na tablicę znaków (nie jestem pewien, czy dane wejściowe z tablicy znaków są dopuszczalne). Tablica jest następnie iterowana i lokalizowane są pozycje wszystkich kwadratów ziemi. Linie ograniczające podane przez równania
x - y = o
,x = p
,x + y = q
,y = r
,y - x = t
,-x = u
,-x - y = v
,-y = w
są określone tak, że maksymalny możliwy parametr jest wybrany, gdzie wszystkie kłamstwa ziemi poza linię. To powoduje zamknięcie wyspy w ośmiokącie. Współrzędne narożników ośmiokąta są łatwo obliczane na podstawie parametrów, a komórki na jego krawędzi są wypełniane. Tablica jest następnie ponownie łączona w ciąg. Powód, dla którego wystarczy ośmiokąt, jest następujący:Rozważ narożnik ośmiokąta. W pewnym momencie wzdłuż dwóch krawędzi ścieżka będzie ograniczona przez ląd, ponieważ zbudowaliśmy ośmiokąt tak, aby dotykał ziemi tak blisko, jak to możliwe. Jeśli w samym rogu nie ma ziemi, ścieżka może obrać alternatywne trasy, jak pokazano po prawej stronie, ale nadal jest to ta sama liczba kroków ortogonalnych i ukośnych, więc odległość pozostaje niezmieniona.
źródło
rest of arguments
parametr....p
w różnych miejscach.) Restrukturyzacja to coś innego (chociaż operator rozkładania może być użyty w destrukcji).Python 3.5,
224, 263, 234218 bajtówGrał w golfa o kolejne 16 bajtów, pozbywając się funkcji zagnieżdżonej i czyniąc ją jednowierszową.
Gra w golfa poza 29 bajtami:
Dane wejściowe to pojedynczy ciąg znaków używający „~” dla oceanu, „X” dla lądu i „o” dla granicy. (Użycie „X” zapisuje bajt dla „>” zamiast „==”)
Wersja mniej golfowa z komentarzami:
źródło
C # 7 -
414369327 bajtówEdycja : przełączono na pętlę 1D, przetwarzanie
i
ij
w locieEdycja : zmieniono metodę wprowadzania, zwiniętą tabelę wyszukiwania i przełączono na dobrze zdefiniowane początkowe granice ... i usunięto niepotrzebne miejsce w ostatniej zewnętrznej pętli for
Wypróbuj online
Kompletny program, bierze wkład standard w drukuje go na standardowe wyjście, zastosowań
#
,.
orazo
. Dla każdej komórki oblicza „profil” (czyli odległość w 8 kierunkach (dla wygody wydaje się, że jest to dziewiąta, ale zawsze tak jest0
), i zapisuje maksimum każdego z nich. Następnie zapisuje całą mapę ponownie i zastępuje każdą komórkę, która jest zarówno na granicy, jak i poza nią, znakiem „o”. Skomentowany kod poniżej wyjaśnia, jak to wszystko działa.Zgodnie z moją odpowiedzią „Uratuj gęsi przed wyginięciem” daje to najmniejszy ośmiokąt (ważne okrążenie z największym obszarem), który ogranicza wyspę.
Uwaga : raz w życiu używam czegoś z obecnej dekady, a ten kod wymaga kompilacji w C # 7. Jeśli nie masz C # 7, jest jeden wiersz, który będzie musiał zostać zastąpiony, co jest wyraźnie zaznaczone w kodzie.
Przykładowe użycie i dane wyjściowe:
Sformatowany i skomentowany kod:
źródło