Wyobraź sobie następujący scenariusz: grasz pancernikami z przyjacielem, ale decydujesz się oszukiwać. Zamiast przesuwać statek po tym, jak strzela do miejsca, w którym był twój statek, decydujesz się nie umieszczać żadnych statków. Mówisz mu, że wszystkie jego strzały są chybione, dopóki nie da się tak ustawić statków.
Musisz napisać funkcję lub pełny program, który w jakiś sposób przyjmuje 3 argumenty: rozmiar pola, listę wielkości rozmiarów statków i listę zdjęć.
Pole walki
Jednym z podanych parametrów jest rozmiar płyty. Pole bitwy to kwadrat komórek, a podany parametr to po prostu jedna strona kwadratu.
Na przykład poniżej znajduje się tablica o rozmiarze 5.
Współrzędne w polu są określone jako ciąg 2-składnikowy: litera, po której następuje liczba. W niektórych przypadkach możesz polegać na literach.
Litera określa kolumnę, liczba określa wiersz komórki (indeksowany 1). Na przykład na powyższym zdjęciu podświetlona komórka jest oznaczona "D2"
.
Ponieważ jest tylko 26 liter, pole nie może być większe niż 26 x 26.
Statki
Statki są liniami prostymi złożonymi z 1 lub więcej bloków. Ilość statków jest określona na liście, gdzie pierwszy element to liczba statków 1-komórkowych, druga - statków 2-komórkowych i tak dalej.
Na przykład lista [4,1,2,0,1]
utworzyłaby następujący zestaw wysyłkowy:
Umieszczone na polu bitwy statki nie mogą się przecinać ani nawet dotykać. Nawet z zakrętami. Mogą jednak dotykać krawędzi pola.
Poniżej znajduje się przykład prawidłowego rozmieszczenia statków:
Możesz założyć, że dla danego zestawu zawsze istnieje miejsce na pustej planszy o danym rozmiarze.
Wydajność
Jeśli takie rozmieszczenie statków istnieje, musisz wyprowadzić dowolny z nich.
Program musi wypisać oddzieloną nową linią macierz znaków ascii dowolnego z 3 typów - jeden oznacza pustą komórkę, jeden - kawałek statku, a drugi - komórkę oznaczoną jako „brak”. Żadne inne znaki nie powinny być wyprowadzane.
Na przykład,
ZZ@Z
\@@Z
@\\Z
\Z\\
(W tym przykładzie zdefiniowałem @
pustą komórkę, komórkę \
„pominiętą” i Z
wysyłkę)
Jeśli takie miejsce nie istnieje, program / funkcja powinna powrócić bez wypisywania czegokolwiek.
Wejście
Jeśli zdecydujesz się stworzyć program w pełnej wersji, to zależy od ciebie, w jaki sposób wprowadzane są listy, niektóre mogą przechodzić przez argumenty, inne przez stdin.
To jest golf golfowy , wygrywa najmniejsza liczba znaków.
Przykład zoptymalizowanego rozwiązania bez gry w golfa można znaleźć tutaj.
Skompiluj -std=c99
, pierwszy argument to rozmiar planszy, pozostałe argumenty to wielkość statku. Oddzielona od linii nowa lista strzałów jest podana na standardowym ekranie. Przykład:
./a 4 1 1 1 <<< $'A2\nA4\nB3\nC3\nC4\D4'
źródło
26x26
? Naszkicowałem rozwiązanie oparte na wyrażeniach regularnych i rekurencji i staje się ono bardzo powolne = bezużyteczne dla pól więcej niż6x6
. Albo robię coś bardzo głupiego, albo brak odpowiedzi oznacza, że inni też nie odnoszą sukcesu.10x10
dla4,3,2,1
zestawuOdpowiedzi:
GolfScript, 236 znaków
Dane wejściowe podano na STDIN. Pierwsza linia zawiera rozmiar i liczbę statków, każda następna linia współrzędnych jednego strzału.
Przykład:
Pomyślałem, że także to wyzwanie powinno mieć co najmniej jedną odpowiedź na GolfScript. Ostatecznie stało się to bardzo niemiłosłowskie ze względu na zastosowany algorytm, który faworyzuje wydajność w stosunku do krótkości.
Kod z adnotacjami:
źródło
SWI-Prolog,
536441 1 bajtów1 koniec linii UNIX, ostatnia nowa linia nie jest liczona
Wersja z usuniętymi wszystkimi optymalizacjami ( 441 bajtów):
Ponieważ kod został zmieniony w celu zminimalizowania liczby bajtów, nie będzie już akceptować listy zdjęć, które mają duplikaty.
Wersja z podstawową optymalizacją, w pełni golfa ( 536 → 506 bajtów)
Wdrażam podstawowe kontrole ( licz liczbę niezbędnych bloków statku ), aby kod wychodził szybciej w przypadku wyraźnie niemożliwych przypadków. Kod jest również odporny na powielanie na liście dotychczasowych strzałów.
Poniżej znajduje się (nieco) czytelna wersja ze szczegółowymi komentarzami:
Format zapytania:
Przykładowe zapytanie (przy użyciu próbki w pytaniu):
źródło
Matlab - 536 znaków
Zaktualizowano: Znacznie mniejsze formatowanie wyjściowe, usunięto niektóre białe znaki pętli.
Zaktualizowano: Dodano wersję golfową
Zaktualizowano: Dodano wersję komentowaną, zmniejszono wersję gry w golfa o ~ 100 znaków
Oto wersja golfowa.
Oto kilka próbek.
Duża linia z „kron” (u dołu kodu bez golfa) jest moją ulubioną częścią tego. Zapisuje „1” we wszystkich lokalizacjach na mapie, które sąsiadują z daną pozycją. Czy widzisz jak to działa? Wykorzystuje iloczyn tensora Kroneckera, mnożenie macierzy i indeksuje mapę jako szyk liniowy ...
źródło
Python, 464 znaki
Wejście (standardowe wejście):
Wynik:
Działa przy użyciu liczb całkowitych zawierających mapy bitowe różnych funkcji:
źródło
[::-1]
która sprawia, że najpierw wypróbowuje najdłuższy statek. Cofa się także, gdy tylko znajdzie statek, którego nie może umieścić.Python, 562 znaki, -8 z brzydkim wyjściem, +4? do wywołania bash
Uwaga: poziomy wcięcia to spacja, tab, tab + spacja, tab + tab oraz tab + tab + spacja. Oszczędza to kilka znaków przed używaniem spacji.
Zastosowanie i przykład :
Pobiera dane wejściowe z argumentów wiersza poleceń. Wysyła puste miejsce jako spację, strzał jako
.
i@
jako część statku:Gdy nie można go rozwiązać, nic nie drukuje:
Jest
2>X
to pomijanie komunikatu o błędzie, ponieważ program kończy działanie, zgłaszając wyjątek. Dodaj karę +4, jeśli zostaniesz uznany za sprawiedliwy. W przeciwnym razie musiałbym zrobić a,try: ... except:0
aby go stłumić, co i tak zajęłoby więcej postaci.Mogę również wydrukować dane wyjściowe jako liczby (
0
,1
i2
), aby zgolić 8 znaków, ale cenię sobie estetykę.Objaśnienie :
Reprezentuję tablicę jako listę liczb całkowitych o rozmiarze 2 większym niż wejście, aby uniknąć konieczności sprawdzania granic.
0
przedstawia pustą przestrzeń,1
strzał i2
statek. Przeglądam listę zdjęćQ
i zaznaczam wszystkie zdjęcia. Przekształcam listę statków na jawną listęX
statków, np .[4, 0, 2, 0, 1]
Staje się[5, 3, 3, 1, 1, 1, 1]
. Jest to prosty algorytm cofania: w kolejności malejącej, spróbuj umieścić statek, a następnie spróbuj umieścić pozostałe statki. Jeśli to nie działa, wypróbuj następne gniazdo. Gdy tylko się powiedzie, lista statkówX
jest pusta, a uzyskanie dostępuX[0]
powoduje wyjątek, który kończy działanie programu. Reszta to po prostu ciężka gra w golfa (początkowo 1615 znaków).źródło
Perl,
455 447 437 436 422418Zębaty:
Spodziewam się, że można go dalej grać w golfa (np. W
eval<>
przypadku wstępnie sformatowanego wejścia, ponieważ widzę, że jest OK (?)), A także kilka innych rzeczy (50$
sigili? Nie, zostaną).Szybkość, jak powiedziałem wcześniej, może być problemem (od chwilowego (patrz przykład poniżej) do bardzo bardzo długiego), w zależności od tego, gdzie rozwiązanie znajduje się na drzewie rekurencyjnym, ale niech będzie to kwestia przestarzałego używanego sprzętu. Zrobię wersję zoptymalizowaną później, bez rekurencji i 2-3 innych oczywistych sztuczek.
Działa tak: 3 linie są przesyłane przez STDIN:
~
jest oceanem (rozwiązanie artystyczne, prawda),o
ax
s to statki i strzały. Pierwsze 5 linii otrzymuje dane i przygotowuje nasze „pole bitwy”.$N
jest rozmiarem,@S
jest rozwiniętą tablicą statków (np.1 1 1 1 2 3 3 5
jak wyżej),$f
jest łańcuchem reprezentującym pole bitwy (rzędy z połączonymi znakami nowej linii). Dalej jest podprogram rekurencyjny, który oczekuje aktualnego stanu pola bitwy i listy pozostałych statków. Sprawdza od lewej do prawej, od góry do dołu i próbuje umieścić każdy statek w każdej pozycji, zarówno poziomo, jak i pionowo (patrz? Dojrzały do optymalizacji, ale to będzie później). Poziomy statek jest oczywistym zastąpieniem wyrażenia regularnego, pionowy nieco trudniejszy - bitowa manipulacja ciągiem, aby zastąpić w „kolumnie”. W przypadku sukcesu (H, V lub oba) nowe niedostępne pozycje są oznaczone symbolem!
, i przechodzi do następnej iteracji. I tak dalej.Edycja: OK, oto 594 bajty (gdy nie ma wcięcia) wersja, która faktycznie próbuje być użyteczna (tj. Szybka) - zoptymalizowana według moich najlepszych możliwości, wciąż wdrażając te same techniki - rekurencja (aczkolwiek wykonywana „ręcznie”) i wyrażenia regularne. Utrzymuje „stos” -
@A
- tablica stanów, które warto zbadać. „Stan” to 4 zmienne: bieżący ciąg pola bitwy, indeks, od którego należy rozpocząć próbę umieszczenia statków, odniesienie do tablicy pozostałych statków oraz indeks następnego statku do wypróbowania. Początkowo jest jeden „stan” - początek pustego ciągu, wszystkie statki. Przy dopasowaniu (H lub V, patrz wyżej), aktualny stan jest przesuwany w celu późniejszego zbadania, zaktualizowany stan (z umieszczonym statkiem i zaznaczonymi niedostępnymi pozycjami) jest przesuwany i blok jest restartowany. Po osiągnięciu końca pola bitwy bez powodzenia,@A
sprawdzany jest następny dostępny stan z (jeśli występuje).Inne optymalizacje to: brak ponownego uruchamiania od samego początku łańcucha, próba umieszczenia dużych statków jako pierwsza, nie sprawdzenie statku o tym samym rozmiarze, jeśli poprzedni nie powiodło się w tej samej pozycji, + może coś innego (jak brak
$&
zmiennej itp.)..
OTOH, to wciąż trwa wiecznie na niemożliwy przypadek
6 5 4 3 2 1
w powyższym przykładzie. Może praktyczna wersja powinna wyjść natychmiast, jeśli całkowity tonaż statku przekroczy pojemność pola bitwy.źródło
Rozwiązanie C #
źródło
size=1 ships={1} moves={"A1"}
.Java, 1178
Tak o wiele za długo.
Nie golfowany:
Próbka wejściowa
Próbka-wynik
Z
O
nieudany strzał#
część statku_
strzelaj tutaj dalej ;-)Zobacz na ideone.com
Obsługa wprowadzania oczekuje spacji wokół liczb /
;
i nie zadziała inaczej.Najpierw stawiam duże statki, ponieważ mają mniej miejsc do przejścia. Jeśli chcesz, aby przełączyć się na małą pierwszy można zastąpić
pop()
przezremove(0)
ipush(s)
przezadd(0,s)
nawet zastąpienie tylko jeden z dwóch powinien nadal prowadzić ważnego programu.Jeśli zezwolisz statkom na stykanie się ze sobą,
g(int,int)
funkcję tę można znacznie uprościć lub usunąć.źródło