Mondrian Puzzle Sequence

11

Podziel n X nkwadrat na wiele nie przystających prostokątów o liczbach całkowitych. a(n)jest najmniejszą możliwą różnicą między największym a najmniejszym obszarem.

 ___________
| |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.

Biorąc pod uwagę liczbę całkowitą n>2, wyprowadzaj najmniejszą możliwą różnicę.

Wszystkie znane wartości sekwencji w momencie publikacji:

2, 4, 4, 5, 5, 6, 6, 8, 6, 7, 8, 6, 8, 8, 8, 8, 8, 9, 9, 9, 8, 9, 10, 9, 10, 9, 9, 11, 11, 10, 12, 12, 11, 12, 11, 10, 11, 12, 13, 12, 12, 12

Tak a(3)=2, a(4)=4...

OEIS A276523

Powiązane - to powiązane wyzwanie umożliwia nieoptymalne rozwiązania, ma ograniczenia czasowe i nie jest golfem kodowym.

Aby uzyskać więcej informacji, obejrzyj ten film autorstwa Numberphile

mbomb007
źródło

Odpowiedzi:

4

CJam, 178

ri_1a*a*L{_:+1&{_[3{_\zW%}*]{_z}%:e<_@={:A0=_1#:X0<{;A1>j}{X>0+0#AzX=0+0#,\,m*1ff+{[_$\~1a*0aX*\+a*A\..-_])s'-&{;}&}%{~j\:X;{Xa&!},Xaf+:$~}%_&}?}{j}?}{;La}?}j{,(},{::*$)\0=-}%:e<

Wypróbuj online . Jest jednak bardzo powolny, nie zalecałbym przekraczania 6.

Aby sprawdzić, czy naprawdę działa, możesz sprawdzić ten nieco zmodyfikowany program, który drukuje wszystkie możliwe partycje (każda partycja jest pokazana jako tablica par wymiarów prostokątnych).

aditsu zrezygnowało, ponieważ SE jest ZŁEM
źródło
Wow, czas ucieczki gwałtownie rośnie.
mbomb007
@ mbomb007 tak, całkiem spodziewane dla brutalnego rozwiązania. Właściwie dołączyłem kilka optymalizacji, aby uczynić go bardziej wydajnym. Jeśli je usunę, mogę sprawić, że będzie nieco mniejszy (i wolniejszy i bardziej głodny).
Aditsu odeszło, ponieważ SE ma wartość EVIL
6

Befunge, 708 bajtów

p&>:10p1-:>20p10g:20g\`v`\g02:-1\p00+1g<>g-#v_10g:*30p"~":40p50p060p070p$>^
1#+\#1<\1_^# !`0::-1$  _:00g3p\:00g2p00^^00:>#:


>>:2-#v_$30p50p60p70g1-70p
^<<<<<:#<<<<<<$$$_v#:!g87g78g79$  _v#!\-1:g88$<_ 98p87g97g*00 v:+!\`*84g++7<
^>$1-:77p1g:2g\3g1>78p97p87p10g97g->88p10g87g-0^!\-1:g89_v#-!\_$1-:v>/88g+7^
^|!-3$<   >\87g/88g+77++p:#v_$
^>:5->v   ^+g89%g78:\g77:-1<>98g88g48*577g387g97g98g88v ^>77g87g97v:^g78\+g<
^ v-4:_$77p88p98p:97p\:87p*^^g79g7>#8\#$_40pv5+"A"g77g< ^14g88g89g<>:87g%98^
^v_$88p98p97p87p:77p60g50g-:40g\`#^_$$>>>>>>>
 >#4!_::80p2g\3g*:90p30g`!v>>>#@>#.>#g^#0
^v:g06p03:-g09\2:g03g05g06_^^_7#<0#<g#<3#<1#<<`g04_$00g1->:#-8#10#\g#1`#:_>$
^>90g\-:0`*+:60p50g:90g-:0`*-:50p-80g70g:1+70p1p\!^

Wypróbuj online!

To oczywiście nie zdobędzie żadnych nagród za rozmiar, ale w rzeczywistości jest dość szybki, biorąc pod uwagę, że jest to podstawowa implementacja bruce force w ezoterycznym języku. W tłumaczu referencyjnym Befunge może obsłużyć do n = 6 w ciągu kilku sekund. Dzięki kompilatorowi może obsłużyć do n = 8, zanim zacznie się leniwie; n = 9 zajmuje kilka minut, a n = 10 jest zamykane przez 2 godziny.

Teoretycznie górna granica wynosi n = 11, zanim zabraknie nam pamięci (tj. Nie ma wystarczającej ilości miejsca na boisku, aby zmieścić większy kwadrat). Jednak w tym momencie czas obliczenia optymalnego rozwiązania jest prawdopodobnie dłuższy niż ktokolwiek byłby skłonny czekać, nawet po skompilowaniu.

Najlepszym sposobem, aby zobaczyć, jak działa algorytm, jest uruchomienie go w jednym z „wizualnych debuggerów” Befunge. W ten sposób możesz oglądać, jak próbuje dopasować różne rozmiary prostokąta do dostępnej przestrzeni. Jeśli chcesz „przewinąć do przodu” do punktu, w którym ma dobre dopasowanie, możesz umieścić punkt przerwania 4w sekwencji w $_40ppobliżu środka dziesiątej linii (9, jeśli zero). Wartość na górze stosu w tym punkcie jest bieżącą różnicą powierzchni.

Poniżej znajduje się animacja pokazująca kilka pierwszych klatek tego procesu dla n = 5:

Animacja pokazująca proces dopasowania prostokąta

Każdy odrębny prostokąt jest reprezentowany przez inną literę alfabetu. Należy jednak pamiętać, że końcowy prostokąt nigdy nie jest zapisywany, więc sekcja kwadratu będzie po prostu pusta.

Napisałem również wersję debugowania kodu, która wyświetla bieżący układ za każdym razem, gdy znajdzie nowe najlepsze dopasowanie ( Wypróbuj online! ). W przypadku mniejszych rozmiarów pierwsze dopasowanie jest często optymalnym rozwiązaniem, ale gdy miniesz n = 6, prawdopodobnie zobaczysz kilka prawidłowych, ale nieoptymalnych układów, zanim osiądzie na ostatecznym rozwiązaniu.

Najlepszy układ znaleziony dla n = 10 wygląda następująco:

H F F F A A A C C I
H F F F A A A C C I
H J G G A A A C C I
H J G G A A A C C I
H J D D D D D C C I
H J D D D D D C C I
H J K K K K K K K I
H J B B B E E E E I
H J B B B E E E E I
H J B B B L L L L L

12 - 4 = 8
James Holderness
źródło
1
Jesteś bogiem wśród befunge-rs.
Rɪᴋᴇʀ