Aby uzyskać więcej informacji, obejrzyj ten film i przejdź do A276523, aby uzyskać powiązaną sekwencję.
Układanka Mondrian (dla liczby całkowitej n
) jest następująca:
Dopasuj nie przystające prostokąty do n*n
kwadratowej siatki. Jaka jest najmniejsza możliwa różnica między największym a najmniejszym prostokątem?
Dla 6
optymalnej różnicy M(6)
jest 5
i można to wykazać w następujący sposób:
___________
| |S|_______|
| | | L |
| |_|_______|
| | | |
| |_____|___|
|_|_________| (fig. I)
Największy prostokąt (L) ma powierzchnię 2 * 4 = 8
, a najmniejszy prostokąt (S) ma powierzchnię 1 * 3 = 3
. Dlatego różnica jest taka 8 - 3 = 5
.
Należy pamiętać, że obecnie nie n > 44
znaleziono optymalnych rozwiązań .
Twoim zadaniem jest stworzenie programu, który generuje siatkę Mondrian, która zawiera (nieoptymalne) rozwiązanie, biorąc pod uwagę liczbę całkowitą n
.
Zostaniesz przetestowany na liczbach od 100 do 150. Twój wynik za każdy test będzie różnicą między największym i najmniejszym prostokątem. Twój łączny wynik to suma wyników wszystkich testów od 100 do 150.
Musisz przedstawić swoje wyniki w następujący sposób:
{number}
{grid}
Gdzie number
jest wynik (różnica między największym a najmniejszym) i grid
wynosi albo:
- Sznurek z wieloma liniami lub
- Dwuwymiarowa lista.
Siatka MUSI wyraźnie pokazywać, gdzie prostokąt zaczyna się i kończy.
Zasady:
- Twój program musi mieścić się w twojej odpowiedzi.
- Twój program musi wypisać wartość dla dowolnej liczby od 100 do 150 w ciągu 1 godziny na nowoczesnym laptopie.
- Twój program musi generować to samo rozwiązanie dla liczby całkowitej przy
n
każdym uruchomieniu programu. - Musisz podać link do wyników wszystkich 51 rozwiązań (używając Pastebin, Github Gist ... cokolwiek, naprawdę).
- Musisz mieć co najmniej dwa prostokąty na kwadratowej siatce dla swojego rozwiązania.
źródło
Odpowiedzi:
Piet, 9625
(W końcu to działa!)
Ludzie tego zażądali, więc oto jest. Jest to niezwykle naiwne rozwiązanie (zasadniczo takie samo jak luźne górne granice na stronie OEIS): dzieli każdy kwadrat na tylko dwa prostokąty.
Ta lista zawiera szczegóły w dwóch plikach:
?
jest monit o wprowadzenie, a następnie natychmiast wynik wyjściowy, a następnie siatka.Wyjaśnienie
Ten program ma jeden numer
N
jako dane wejściowe. Jeśli liczba jest nieparzysta, wynikiem jest liczba; jeśli parzysty, wynik jest dwa razy większy niż liczba.Po wypisaniu wyniku, reszta lewej strony programu jest wydawana na wypełnienie stosu pięcioma partiami następujących informacji:
N
)_
spacji)|
)Prawa strona programu pobiera każdy zestaw czterech wartości i drukuje tę część siatki.
źródło
C 6108
Wykorzystuje rekurencyjną (naprawdę iteracyjną) wersję minimalnego rozwiązania. Zamiast dzielić kwadrat na dwa prostokąty, z których jeden jest nieco większy niż połowa powierzchni, dzieli go na N prostokątów. Pierwszy prostokąt jest więc nieco większy niż
1/N
całkowity obszar. Następnie biorąc resztę, program dzieli prostokąt nieco większy niż1/(N-1)
reszta i tak dalej, aż resztę zajmie tylko jako ostatni prostokąt. Prostokąty są odcinane od reszty spiralnie zgodnie z ruchem wskazówek zegara, więc najpierw u góry, potem po prawej itd.Ponieważ jest to bardzo bezpośrednia metoda zamiast przeszukiwania szerokiej przestrzeni, działa szybko - zajmuje około 25 sekund (na Raspberry Pi) po 74 rozwiązań dla każdego zestawu problemów.
Moim zamiarem jest wykorzystanie tych wyników, aby lepiej poinformować algorytm wyszukiwania o bardziej wyrafinowanym podejściu.
Dane wyjściowe dają wynik i rysunek (ascii) oraz współrzędne wierzchołków prostokątów. Wierzchołki są w kolejności zgodnej z ruchem wskazówek zegara, zaczynając od lewego górnego rogu danego prostokąta.
Opracowany przy użyciu gcc 4.9.2-10.
Wyniki na https://github.com/JaySpencerAnderson/mondrian
Kod:
źródło
C - 2982
Ten program realizuje wyszukiwanie za pomocą szerokiego zestawu wyników. Ważną częścią praktycznego poszukiwania było wczesne niepowodzenie i / lub zejście złymi ścieżkami.
Generuje to zestaw prostokątów do rozważenia dla rozwiązania. Zestaw wygenerowanych prostokątów pozwala uniknąć tych o wymiarach, które nie byłyby przydatne. Na przykład, jeśli program próbuje znaleźć rozwiązanie kwadratu 128 x 128, podzielonego na 8 prostokątów, wygeneruje prostokąt o wymiarach 128 x 16. Nie wygeneruje tego, że ma wymiary 120 x 17, ponieważ nie ma szansy na wygenerowanie prostokąta o szerokości 8 do wypełnienia luki na końcu 120.
Początkowa strategia umieszczania prostokątów polega na umieszczeniu ich po wewnętrznej stronie obwodu kwadratu (funkcja budowania). W ten sposób algorytm otrzymuje dość szybką informację zwrotną na każdym rogu, czy istnieje problem z wybraną sekwencją. Umieszczając prostokąty, logika stale obserwuje, aby zobaczyć, czy pojawią się luki w przestrzeni, które są zbyt wąskie dla jakiegokolwiek prostokąta. Po pomyślnym wypełnieniu obwodu strategia zmienia się na próbę dopasowania pozostałego miejsca do pozostałych prostokątów (funkcja dopasowania).
Inną rzeczą, która może być interesująca jest to, że implementuje transakcje z wycofywaniem stosów prostokątów.
Ten program nie próbuje znaleźć najlepszego możliwego dopasowania. Otrzymuje budżet (64) i kończy pracę, gdy znajdzie pierwsze rozwiązanie. Jeśli to nigdy nie znajdzie rozwiązania, zwiększamy budżet (o 16) i próbujemy ponownie. Wymagany czas (na laptopie Dell z procesorem I7) wahał się od znacznie poniżej minuty do 48 minut dla 150 na boku (149 na stronie zajęło mniej niż 2 minuty). We wszystkich 51 rozwiązaniach zastosowano 11 prostokątów. Wyniki 51 rozwiązań wahały się od 41 do 78. Powodem, dla którego użyłem 11 prostokątów było to, że wynik był niższy niż przy mniejszej liczbie prostokątów i wyglądało na to, że 12 prostokątów zajmie znacznie więcej niż wyznaczona godzina.
Rozwiązania i kod można znaleźć na stronie https://github.com/JaySpencerAnderson/mondrian . Są to dwa pliki my4 *.
BTW, jeśli skompilujesz to do „my4” i wykonasz to w następujący sposób: „./my4 -h”, da ci to użytkowanie. Jeśli chcesz zobaczyć, jak działa, spróbuj czegoś takiego jak „./my4 -l 50 -n 8”. Jeśli zmienisz „#if 0” na „#if 1”, wyświetli pozostałe miejsce na ekranie. Jeśli chcesz to zmienić, aby renderować prostokąty, poszukaj jednego miejsca, w którym kod wykonuje „graf (spacja, bok)” i zamiast tego zmień to na „graf (stos wywołań, bok)”. Proponuję również zmienić początkowy budżet z 64 na 32, jeśli chcesz bawić się rozwiązaniami dla kwadratów o szerokości około 50. Rozwiązanie dla mniejszych kwadratów będzie miało lepszy wynik przy mniejszym budżecie.
Poniższy program działa. Sprawdź github pod kątem pełnego kodu (z użyciem, komentarzami itp.).
źródło