Tablica wyników
Oto surowe wyniki (tj. Liczby domino) dla przesłania VisualMelon. Zamienię je w znormalizowane wyniki opisane poniżej, gdy pojawi się więcej odpowiedzi. Istniejące rozwiązanie może teraz rozwiązać wszystkie obwody w teście:
Author Circuit: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
VisualMelon 39 45 75 61 307 337 56 106 76 62 64 62 182 64 141 277 115 141 92 164 223 78 148 371 1482 232 107 782 4789 5035 1314 3213 200 172 1303 3732 97596 156889 857
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Legend:
I - invalid circuit
B - circuit too big
W - circuit computes wrong function
T - exceeded time limit
Wyzwanie
To jest możliwe budowanie prostych bramek logicznych z domino. Stąd, łącząc te lub w inny sposób, dowolne funkcje binarne można obliczyć za pomocą domina.
Ale oczywiście każdy, kto grał w domino (z wyjątkiem Robina Paula Weijers) doświadczył rozczarowania, gdy ich zabrakło. Dlatego chcemy korzystać z naszych domino tak wydajnie, jak to możliwe, abyśmy mogli wykonać naprawdę interesujące obliczenia z posiadanego materiału.
Zauważ, że nie możesz wytworzyć niezerowego wyjścia z zerowego wejścia per se, więc będziemy musieli dodać „linię zasilania”, która biegnie wzdłuż twojej konfiguracji i z której możesz wyciągnąć 1
s w dowolnym momencie.
Twoje zadanie
Biorąc pod uwagę funkcję boolowską z M
wejściami i N
wyjściami ( f: {0,1}^M --> {0,1}^N
dla nachylenia matematycznego), stwórz obwód domina z możliwie najmniejszą liczbą domino, który oblicza tę funkcję. Będziesz za pomocą symboli |
, -
, /
, \
do reprezentowania w domino w różnych orientacjach.
Wkład
Otrzymasz dane za pomocą argumentów wiersza poleceń:
[command for your solver] M N f
gdzie M
i N
są dodatnimi liczbami całkowitymi i f
jest tabelą prawdy oddzieloną przecinkami w porządku kanonicznym. Oznacza to, że f
będzie zawierać 2^M
wartości długości N
. Np. Gdyby M = N = 2
i pierwszy bit na wyjściu był funkcją AND, podczas gdy drugi bit był funkcją OR, f
odczytałby się
00,01,01,11
Wydajność
Napisz do STDOUT siatkę ASCII reprezentującą konfigurację domina. Twoja konfiguracja musi mieścić się w następujących ramach
/////.../////
????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
- Górny rząd składa się całkowicie z
/
, a na lewo domino z pewnością zostanie przewrócone na początku - to twoja linia energetyczna. - Lewa kolumna zawiera twoje dane wejściowe. Każda
I
może być spacją lub a|
, tak że istnieją dokładnieM
|
s. - Prawa kolumna składa się z twoich wyników. Każda
O
może być spacją lub a|
, tak że istnieją dokładnieN
|
s. - Zauważ, że przed pierwszym
|
wejściem lub wyjściem jest co najmniej jeden pusty . .
Wskazują, że siatka może być dowolnie duża.- Możesz wypełnić
?
w dowolny sposób.
Zauważ, że dolne dane wejściowe zmieniają się najszybciej podczas przeglądania tabeli prawdy, podczas gdy górne dane wejściowe dotyczą 0
pierwszej połowy danych wyjściowych i 1
drugiej połowy.
Zasady
Domino rozprzestrzeniają się, jak określono w Golfing for Domino Day . Krótko mówiąc, jeśli przedstawiamy spadające kierunki jako litery
Q W E
A D
Z X C
to są wszystkie unikalne kombinacje, które mogą się rozprzestrzeniać (jak również ich rotacje i odbicia):
D| -> DD D\ -> DE D/ -> DC
C| -> CD C/ -> CC
C -> C C -> C C -> C
| D - X / C
Wszystkie powyższe zasady są stosowane jednocześnie na każdym etapie. Jeśli dwie z tych reguł są w konflikcie (tj. Płytka jest jednocześnie popychana w dwóch ważnych przeciwnych kierunkach), dotknięta płytka nie spadnie i zostanie skutecznie zablokowana na pozostałą część symulacji.
Ograniczenia
M
iN
nigdy nie przekroczy 6.- Twój solver musi wytworzyć obwód w ciągu N * 2 M sekund .
- Twój solver nie może zużywać więcej niż 1 GB pamięci . To jest miękki limit, ponieważ będę go monitorował ręcznie i zabiję twój proces, jeśli znacznie / stale przekroczy ten limit.
- Żaden obwód nie może zawierać więcej niż 8 000 000 komórek lub 1 000 000 domino .
- Twoje zgłoszenie musi być deterministyczne . Dozwolone jest używanie generatorów liczb pseudolosowych, ale muszą one używać zakodowanego ziarna (które można dowolnie optymalizować).
Punktacja
Dla każdego obwodu niech D
będzie łączna liczba domino w twoim obwodzie i B
najniższa liczba domino z tym obwodem została rozwiązana (przez ciebie lub innego uczestnika). Następnie twój wynik dla tego obwodu jest 10,000 * B / D
zaokrąglany w dół. Jeśli nie udało Ci się rozwiązać obwodu, twój wynik wynosi 0. Twój ogólny wynik będzie sumą ponad zestaw testów przypadków. Obwody, które nie zostały jeszcze rozwiązane przez nikogo, nie zostaną uwzględnione w całkowitej punktacji.
Każdy uczestnik może dodać jeden przypadek testowy do testu porównawczego (a wszystkie pozostałe zgłoszenia zostaną ponownie ocenione, w tym nowy przypadek testowy).
Plik testu porównawczego można znaleźć na GitHub .
Przykłady
Oto kilka nieoptymalnie rozwiązanych przykładów.
Stała 1
1 1
1,1
///////
/
| |||
Liczba domino: 12
LUB brama
2 1
0,1,1,1
///////////
|||||/
|||||
|||||\
Liczba domino: 28
I brama
2 1
0,0,0,1
///////////////////
\-/
- -
|||||/|\ /|||/
/ -
- \-
\- \ -
|||||\ / \ /
|\ |||||
Liczba domino: 62
Zamień pasy
2 2
00,10,01,11
////////////
||||/ \||||
/\
\/
||||\ /||||
Liczba domino: 36
Dodatkowe uwagi
Reguły propagacji są takie, że linie ukośne mogą się krzyżować przy użyciu rombu (patrz ostatni przykład), nawet jeśli jeden z nich upada przed sobą (w przeciwieństwie do prawdziwych domino).
Na początek możesz użyć (nie zminimalizowanych) bramek logicznych w tej siatce i spróbować połączyć ich jak najmniej. Przez proste (non-optymalny) sposób budowania dowolnych funkcji logicznych z AND, OR i NOT bram, rzucić okiem na koniunkcyjnej i dysjunktywny Normal Form.
W repozytorium GitHub znajduje się weryfikator do testowania kodu, który będzie również używany do oceny wszystkich zgłoszeń. To generuje surowe wyniki (liczba domino) i zapisuje je w pliku do przetworzenia przez osobnego strzelca (także w tym repozytorium) w celu uzyskania ostatecznych wyników.
Dokumentacja ogólna znajduje się w dwóch plikach Ruby, ale controller.rb
zajmuje dwa przełączniki wiersza poleceń przed plikiem testu:
-v
daje ci więcej mocy wyjściowej, w tym rzeczywiste obwody produkowane przez twój solver.-c
pozwala wybrać podzbiór testu, który chcesz przetestować. Podaj żądane obwody jako listę oddzielonych przecinkami indeksów 1. Możesz także użyć zakresów Rubiego, abyś mógł zrobić coś takiego-c 1..5,10,15..20
.
Podaj w swojej odpowiedzi:
- Twój kod
- Polecenie (skompiluj i) uruchom kod. Zapytam cię, gdzie uzyskać niezbędne kompilatory / tłumacze, jeśli ich nie mam.
- Dodatkowa tabela prawdy z nazwą, która zostanie dodana jako przypadek testowy do testu porównawczego. (Jest to opcjonalne, ale zdecydowanie zalecane).
Będę testować wszystkie zgłoszenia w systemie Windows 8.
źródło
Odpowiedzi:
C # - rozwiązanie masywne, powolne i nieefektywne
Spowiedź: napisałem to rozwiązanie jakiś czas temu, gdy pytanie wciąż było w piaskownicy, ale nie jest zbyt dobre: możesz zrobić lepiej!
Edycja: zastąpiono nudne rozwiązanie mniej nudną, bardziej elastyczną i ogólnie lepszą metodą
Uruchamiasz program, kompilując zi
csc dominoPrinter.cs
przekazując argumenty do pliku wykonywalnego, na przykład (4-bitowy moduł sprawdzający liczbę pierwszą):Wyjaśnienie:
„Drukarka Domino” to 3-etapowy program:
Etap 1 : „Solver” generuje drzewo wyrażeń „ifnot” i „lub” operacji binarnych z podanymi danymi wejściowymi, a „1” z linii energetycznej, są 2 sposoby, w zależności od liczby danych wejściowych:
Jeśli jest mniej niż 4 wejścia, program rozwiązuje problem najmniejszej liczby operacji
Jeśli są 4 lub więcej wejść, program przerywa każdy 8-bitowy fragment wyjścia, a następnie łączy wyniki w celu uzyskania pożądanego wyjścia. Brutalne bity, jeśli są elastyczne: im więcej brutalnych bitów, tym mniejsze rozwiązanie, ale dłuższy czas pracy.
„Solver” zajmuje cały czas (a przynajmniej kiedyś), a także stanowi większość kodu. Uważam, że istnieje dobrze udokumentowane, szybkie, mało wymagające pamięci i prawdopodobnie optymalne rozwiązanie tego problemu, ale gdzie byłoby zabawę w szukaniu go?
Drzewo wyrażeń (brute) dla 4-bitowego sprawdzania liczb pierwszych jest
gdzie liczby są indeksami danych wejściowych.
Etap 2 : „Organizator” pobiera drzewo wyrażeń jako dane wejściowe i składa układ „szkieletu”, który dokładnie opisuje układ domina wykonany z zestawu nakładających się komórek 4x5. Poniżej znajduje się szkielet brutalnego 4-bitowego sprawdzania liczb pierwszych (musisz zmienić
bruteBase
zmienną całkowitą w linii 473 na 4 (lub większą), aby uzyskać ten wynik).Dane wyjściowe składają się skutecznie z dwóch części: „ewaluatora” po prawej stronie, który jest tworzony z drzewa wyrażeń ze stopnia 1, oraz „tablicy rozdzielczej” po lewej stronie, która zamienia i dzieli dane wejściowe, tak aby dotarły do właściwe miejsca dla „oceniającego” do obsługi.
W tym momencie istnieje spore pole do kompaktowania układu, ale program wykonuje obecnie bardzo niewiele takich prac. Kod tego etapu jest okropny, ale pod nim dość prosty (patrz metoda „orifnot”). Dane wyjściowe są przekazywane do etapu 3.
Etap 3 : „Drukarka” pobiera dane wyjściowe z „organizera” i drukuje odpowiednie nakładające się na siebie „komórki” 4x5 wraz z linią energetyczną. Poniżej znajduje się animacja brutalnego 4-bitowego sprawdzania liczb pierwszych sprawdzającego, czy 5 jest liczbą pierwszą.
Kod braku wcięcia ma na celu uniknięcie przekroczenia limitu znaków SE 30k, który w innym przypadku :
Dodatkowy przypadek testowy:
To sprawdza, czy dwa sąsiednie (nie zawijające) bity są jednocześnie 1 (np. Prawda dla 0110, ale fałsz dla 0101 i 1001)
źródło
I
i której wyniki określają nowy układ domina