Historia
Moja firma wysyła cotygodniowy biuletyn do wszystkich osób w firmie. W tych biuletynach znajduje się zagadka wraz z okrzykiem do kogokolwiek w firmie, który jako pierwszy wysłał e-maila / zapewnił rozwiązanie zagadki z zeszłego tygodnia. Większość z tych zagadek jest dość trywialna i naprawdę dość nudna dla firmy technologicznej, ale był jeden, kilka miesięcy temu, który przykuł moją uwagę.
Oryginalna zagadka:
Biorąc pod uwagę poniższy kształt:
Masz liczby naturalne od 1 do 16. Dopasuj je wszystkie do tego kształtu, tak aby wszystkie ciągłe rzędy i ciągłe kolumny sumowały się do 29.
Na przykład jedno takie rozwiązanie tej układanki (które było rozwiązaniem „kanonicznym”, które przesłałem do newslettera) było następujące:
Jednak w trakcie jego rozwiązywania znalazłem dość interesujące informacje:
- Istnieje znacznie więcej rozwiązań niż tylko jedno; w rzeczywistości istnieje 9 368 rozwiązań.
- Jeśli rozszerzysz zestaw reguł, aby wymagać tylko, aby wiersze i kolumny były sobie równe, niekoniecznie 29, otrzymasz 33 608 rozwiązań:
- 4440 rozwiązań za sumę 27.
- 7400 rozwiązań za sumę 28.
- 9 368 Rozwiązania za sumę 29.
- 6 096 Rozwiązania za sumę 30.
- 5 104 Rozwiązania za sumę 31.
- 1200 rozwiązań za sumę 32.
Więc ja i moi współpracownicy (choć głównie tylko mój menedżer, ponieważ był jedyną osobą poza mną z umiejętnościami programowania „ogólnego przeznaczenia”) podjąłem wyzwanie, które trwało przez większą część miesiąca - mieliśmy inną, faktyczną pracę - powiązane obowiązki, które musieliśmy wykonać - aby spróbować napisać program, który znalazłby każde rozwiązanie w najszybszy możliwy sposób.
Oryginalne statystyki
Pierwszy program, który napisałem w celu rozwiązania problemu, po prostu sprawdzał losowe rozwiązania w kółko i zatrzymywał się, gdy znalazł rozwiązanie. Jeśli przeprowadziłeś analizę matematyczną tego problemu, prawdopodobnie już wiesz, że to nie powinno działać; ale jakoś miałem szczęście i zajęło programowi tylko minutę, aby znaleźć jedno rozwiązanie (to, które zamieściłem powyżej). Powtarzanie uruchomień programu często trwało nawet 10 lub 20 minut, więc oczywiście nie było to rygorystyczne rozwiązanie problemu.
Przeszedłem na rozwiązanie rekurencyjne, które powtarzało się przez każdą możliwą permutację układanki i odrzuciłem wiele rozwiązań na raz, eliminując sumy, które się nie sumowały. IE, jeśli pierwszy wiersz / kolumna, którą porównywałem, nie były już równe, mógłbym natychmiast przestać sprawdzać tę gałąź, wiedząc, że nic innego permutowanego w układankę by tego nie zmieniło.
Korzystając z tego algorytmu, osiągnąłem pierwszy „właściwy” sukces: program mógł wygenerować i wypluć wszystkie 33 608 rozwiązań w około 5 minut.
Mój kierownik miał inne podejście: wiedząc na podstawie mojej pracy, że jedyne możliwe rozwiązania miały sumy 27, 28, 29, 30, 31 lub 32, napisał rozwiązanie wielowątkowe, które sprawdzało możliwe sumy tylko dla tych konkretnych wartości. Udało mu się uruchomić program w zaledwie 2 minuty. Więc powtórzyłem ponownie; Hashowałem wszystkie możliwe sumy 3/4 cyfr (na początku programu; jest to liczone w całkowitym czasie wykonywania) i użyłem „częściowej sumy” wiersza do wyszukania pozostałej wartości na podstawie wcześniej ukończonego wiersza, a nie testowanie wszystkich pozostałych wartości i skrócenie czasu do 72 sekund. Potem z pewną logiką wielowątkowości zredukowałem ją do 40 sekund. Mój menedżer zabrał program do domu, przeprowadził optymalizację jego działania i obniżył go do 12 sekund. Zmieniłem kolejność oceny wierszy i kolumn,
Najszybsze którekolwiek z nas dostało nasze programy po miesiącu wynosiło 0,15 sekundy dla mojego menedżera i 0,33 sekundy dla mnie. Skończyło się jednak twierdzeniem, że mój program był szybszy, odkąd program mojego menedżera, podczas gdy go znalazł wszystkie rozwiązania, nie drukował ich w pliku tekstowym. Jeśli dodał tę logikę do swojego kodu, często zajmowało to 0,4-0,5 sekundy.
Od tamtej pory pozwoliliśmy sobie na przetrwanie w naszym osobistym wyzwaniu, ale oczywiście pozostaje pytanie: może ten program można przyspieszyć?
To wyzwanie, które zamierzam wam postawić.
Twoje wyzwanie
Parametry, nad którymi pracowaliśmy, złagodziły zasadę „suma 29”, aby zamiast tego były „równe sumom wszystkich wierszy / kolumn”, i dla was również ustawię tę regułę. Wyzwanie jest zatem następujące: Napisz program, który znajdzie (i drukuje!) Wszystkie rozwiązania tej zagadki w najkrótszym możliwym czasie. Zamierzam wyznaczyć pułap zgłaszanych rozwiązań: jeśli program zajmuje więcej niż 10 sekund na stosunkowo przyzwoitym komputerze (<8 lat), prawdopodobnie jest zbyt wolny, aby go policzyć.
Mam też kilka bonusów za układankę:
- Czy możesz uogólnić rozwiązanie tak, aby działało ono dla dowolnego zestawu 16 liczb, nie tylko
int[1,16]
? Wynik pomiaru czasu byłby oceniany na podstawie oryginalnego zestawu numerów podpowiedzi, ale przekazywany przez tę ścieżkę kodową. (-10%) - Czy potrafisz napisać kod w sposób, który z wdziękiem obsługuje i rozwiązuje za pomocą zduplikowanych liczb? To nie jest tak proste, jak mogłoby się wydawać! Rozwiązania „wizualnie identyczne” powinny być unikalne w zestawie wyników. (-5%)
- Czy potrafisz obsłużyć liczby ujemne? (-5%)
Możesz także spróbować wygenerować rozwiązanie, które obsługuje liczby zmiennoprzecinkowe, ale oczywiście nie wstrząśnij, jeśli zawiedzie całkowicie. Jeśli znajdziesz solidne rozwiązanie, może być warta dużej premii!
Pod każdym względem „Obroty” są uważane za unikalne rozwiązania. Tak więc rozwiązanie będące tylko rotacją innego rozwiązania liczy się jako rozwiązanie własne.
IDE, które mam na komputerze, to Java i C ++. Mogę przyjmować odpowiedzi z innych języków, ale może być konieczne podanie linku do strony, w której mogę uzyskać łatwe do skonfigurowania środowisko wykonawcze dla Twojego kodu.
źródło
Odpowiedzi:
C - blisko 0,5 sek
Ten bardzo naiwny program daje wszystkie rozwiązania w pół sekundy na moim 4-letnim laptopie. Bez wielowątkowości, bez mieszania.
Windows 10, Visual Studio 2010, rdzeń procesora I7 64 bit
Wypróbuj online na ideone
źródło
int inuse[16];
just,int inuse;
a następnie użyć operatorów bitowych do manipulowania nim. Wydaje się, że nie zwiększa tak bardzo prędkości , ale trochę pomaga.dumbbench --precision=.01 -vvv --initial=500 ./solve
C ++ - 300 milisekund
Na żądanie dodałem własny kod, aby rozwiązać tę zagadkę. Na moim komputerze trwa on średnio 0,310 sekundy (310 milisekund), ale w zależności od wariancji może działać tak szybko, jak 287 milisekund. Bardzo rzadko widzę, jak wzrasta powyżej 350 milisekund, zwykle tylko wtedy, gdy mój system jest obciążony innym zadaniem.
Czasy te oparte są na autoreportowaniu zastosowanym w programie, ale przetestowałem również przy użyciu zewnętrznego timera i otrzymałem podobne wyniki. Narzut w programie wydaje się dodawać około 10 milisekund.
Również mój kod nie dość obsługiwać duplikaty poprawnie. Może rozwiązać je, ale nie eliminuje „wizualnie identycznych” rozwiązań z zestawu rozwiązań.
źródło
0.1038s +/- 0.0002
A teraz czas na Twój kod z uproszczonymi danymi wyjściowymi:0.0850s +/- 0.0001
Możesz więc zaoszczędzić ~ 18ms, przynajmniej na moim komputerze. Uruchomiłem obie wersje ponadProlog - 3 minuty
Ten rodzaj układanki wydaje się idealnym przykładem użycia dla Prologa. Więc stworzyłem rozwiązanie w Prologu! Oto on:
Niestety nie jest tak szybki, jak się spodziewałem. Może ktoś bardziej obeznany z programowaniem deklaratywnym (lub konkretnie Prologiem) może zaoferować kilka wskazówek dotyczących optymalizacji. Możesz wywołać regułę
puzzle
za pomocą następującego polecenia:Wypróbuj online tutaj . Możesz podstawić dowolną liczbę zamiast
29
s w kodzie, aby wygenerować wszystkie rozwiązania. Na obecnym etapie wszystkie 29 rozwiązań znajduje się w około 30 sekund, więc znalezienie wszystkich możliwych rozwiązań powinno zająć około 3 minut.źródło