Wydrukuj prostokąt Pentomino

16

Napisz program lub funkcję, która nie przyjmuje danych wejściowych, ale drukuje lub zwraca ciągły tekst prostokąta utworzonego z 12 różnych pentominoów :

12 pentominoes

Prostokąt może mieć dowolne wymiary i być w dowolnej orientacji, ale wszystkie 12 pentomino musi być użyte dokładnie raz, więc będzie miało obszar 60. Każdy inny pentomino musi składać się z innego drukowalnego znaku ASCII (nie musisz używać litery z góry).

Na przykład, jeśli zdecydujesz się na wyjście z tego prostokąta pentomino 20 × 3:

Rozwiązanie 3x20

Dane wyjściowe Twojego programu mogą wyglądać mniej więcej tak:

00.@@@ccccF111//=---
0...@@c))FFF1//8===-
00.ttttt)))F1/8888=-

Alternatywnie, może być łatwiej grać w golfa w tym rozwiązaniu 6 × 10:

000111
203331
203431
22 444
2   46
57 666
57769!
58779!
58899!
5889!!

Każde rozwiązanie prostokąta wystarczy, twój program musi tylko wydrukować jedno. (Końcowy znak nowej linii w wyjściu jest w porządku).

Ta wspaniała witryna zawiera mnóstwo rozwiązań dla różnych wymiarów prostokąta i prawdopodobnie warto je przejrzeć, aby upewnić się, że Twoje rozwiązanie jest jak najkrótsze. To jest golf golfowy, wygrywa najkrótsza odpowiedź w bajtach.

code-golf kolmogorov-complexity geometry grid Hobby Calvina
źródło
15
Bonus, jeśli jest to „quine” w Piecie.
mbomb007
@ mbomb007 To prawie niemożliwe, mając tylko 12 bloków do gry: P
Sp3000,
Nie sądzę, że na granicach powinny być dozwolone miejsca. Ale skoro tak, czy mogę pominąć końcowe spacje? Czy dostanę premię, jeśli wydrukuję pionowe rozwiązanie 5x12 ze znakiem I spacji na końcu?
John Dvorak,
@ Sp3000 co powiesz na program Piet złożony w całości z rozwiązań pentomino-prostokąt?
John Dvorak,
@JanDvorak Nie możesz pominąć końcowych spacji, jeśli je masz. Są to znaki, podobnie jak reszta ASCII do wydruku.
Calvin's Hobbies

Odpowiedzi:

1

Pyth, 37 bajtów

jc4.HC"&f3ªªwril3:[·)ÌDU[r)ÌDA»

Demonstracja

Stosuje bardzo proste podejście: użyj bajtów szesnastkowych jako liczb. Konwertuj na liczbę szesnastkową, podstawowa 256 to koduje. To daje magiczny ciąg powyżej. Aby zdekodować, użyj podstawowej funkcji dekodera 256 języka Pyth, przekonwertuj na szesnastkowy, podziel na 4 części i dołącz do znaku nowej linii.

isaacg
źródło
5

CJam (44 bajty)

Podany w formacie xxd, ponieważ zawiera znaki kontrolne (w tym surową kartę, która gra naprawdę źle z MarkDown):

0000000: 2202 7e0d 8ef3 570d e085 e168 cf27 092c
0000010: a235 0c22 3235 3662 3562 332f 5f2c 2c2e
0000020: 7b32 2f27 412b 662b 7d7a 4e2a

który dekoduje do czegoś na wzór

"MAGIC STRING"256b5b3/_,,.{2/'A+f+}zN*

Nieznacznie pozbawione golfa demo online, które nie zawiera znaków kontrolnych, a zatem dobrze gra z funkcjami biblioteki dekodowania URI przeglądarki.

Podstawową zasadą jest to, że ponieważ żaden kawałek nie obejmuje więcej niż 5 rzędów, możemy kodować przesunięcie względem funkcji liniowej numeru wiersza w sposób zwarty (w zasadzie w podstawie 5, chociaż nie próbowałem ustalić, czy zawsze tak będzie) ).

Peter Taylor
źródło
5

Bash + typowe narzędzia Linux, 50

xxd -s20 -p -c2 $0
#<30 bytes of binary data>

Aby odtworzyć to z zakodowanego base64:

base64 -d <<< eHhkIC1zMjAgLXAgLWMyICQwCiMiImaSaZlmkDAAMwSjRKNEqoGogYhRVVF7UXu7d3s= > pent.sh

Ponieważ istnieje 12 pentomino, ich kolory można łatwo zakodować w hex hexb.

Wynik:

$ ./pent.sh
2222
6692
6999
6690
3000
3304
a344
a344
aa81
a881
8851
5551
7b51
7bbb
777b
$
Cyfrowa trauma
źródło
4

J, 49 bajtów

u:64++/\|:3#.inv 1377859090 1567813024 1337683230

Możesz wybierać litery w taki sposób, aby maksymalne przyrosty między literami sąsiadującymi pionowo to 2. Używamy tego faktu do kodowania przyrostów pionowych w bazie3. Następnie tworzymy sumy bieżące i dodajemy przesunięcie, aby uzyskać kody ASCII liter.

Zdecydowanie do gry w golfa. (Jeszcze nie znalazłem sposobu na wprowadzenie liczb o rozszerzonej dokładności base36, ale prosty base36 powinien zaoszczędzić 3 bajty sam.)

Wynik:

AAA
ABA
BBB
DBC
DCC
DCC
DEE
DFE
FFE
FGE
FGG
GGH
HHH
IIH
JII
JJI
JKK
JKL
KKL
LLL

Wypróbuj online tutaj.

randomra
źródło
Bardzo dobrze. Przy kodowaniu base-256 zastosowanie tej różnicy w CJam daje 33 bajty ( wersja 48-bajtowa bez b256 ).
Peter Taylor
To jest niesamowite! Będzie również działał z 4x15, który dobrze działałby do pakowania czterech liczb w bajt, jeśli przechowujesz dane szerokości zamiast długości. Potrzebujesz układu, w którym U pentomino jest skierowane we właściwą stronę. Link zawiera wiele pytań.
Level River St
@steveverrill Potrzebujesz do tego początkowego przesunięcia, ponieważ w pierwszym wierszu będą znajdować się więcej niż 4 elementy, więc nie możesz ich zakodować w base4. Przy tym dodatkowym przesunięciu (np. 3#i.5Który jest 0 0 0 1 1 1 ... 4 4 4) może on działać, ale prawdopodobnie nie będzie krótszy (przynajmniej tak, jak próbowałem).
randomra
2

Microscript II , 66 bajtów

Zacznijmy od prostej odpowiedzi.

"00.@@@ccccF111//=---\n0...@@c))FFF1//8===-\n00.ttttt)))F1/8888=-"

Brawo niejawny druk.

SuperJedi224
źródło
1

Rubin

Rev 3, 55 bajtów

i=1
'S, OJ1*$HCH(#%0'.bytes{|e|puts "%x"%i+=e*130&9011}

Jako dalszy rozwój pomysłu Randomry, rozważ poniższą tabelę wyników i różnic. Tabela różnic może być skompresowana jak poprzednio i rozszerzona przez pomnożenie przez 65 = binarne 1000001 i zastosowanie maski 11001100110011. Jednak Ruby nie działa przewidywalnie z 8-bitowymi znakami (zwykle interpretuje je jako Unicode).

Co zaskakujące, ostatnia kolumna jest całkowicie parzysta. Z tego powodu w kompresji możemy wykonać przesunięcie praw do danych. Dzięki temu wszystkie kody mają 7 bitów ASCII. W rozszerzeniu po prostu mnożymy przez 65 * 2 = 130 zamiast 65.

Pierwsza kolumna jest również całkowicie równa. Dlatego w razie potrzeby możemy dodać 1 do każdego elementu (32 do każdego bajtu), aby uniknąć znaków kontrolnych. Niechciane 1 jest usuwane za pomocą maski 10001100110011 = 9011 zamiast 11001100110011.

Solution 59 of document linked in question

Start0001

Out  Diff
2223 2222
2433 0210
2433 0000
4445 2012
6555 2110
6577 0022
6687 0110
6887 0200
8897 2010
aa99 2202
caa9 2010
cab9 0010
cbbb 0102
cdbd 0202
cddd 0020

Chociaż używam 15 bajtów do tabeli, tak naprawdę używam tylko 6 bitów każdego bajtu, co w sumie daje 90 bitów. W rzeczywistości istnieje tylko 36 możliwych wartości dla każdego bajtu, co w sumie daje 2,21E23 możliwości. To zmieściłoby się w 77 bitach entropii.

Rev 2, 58 bajtów, stosując podejście przyrostowe Randomry

i=0
'UPEIP@bPHPBETTEPRADT'.bytes{|e|puts "%x"%i+=e*65&819}

Wreszcie coś krótszego niż naiwne rozwiązanie. Przyrostowe podejście Randomry, z metodą obejścia z Rev 1.

Rev 1, 72 bajty, wersja 0 gry w golfa

Wprowadzono pewne zmiany w linii bazowej, aby uwzględnić zmianę kolejności kodu ze względu na grę w golfa, ale nadal wprowadzono to dłużej niż naiwne rozwiązanie.

i=0
'UPUIYD&!)$&V*).);c+*'.bytes{|e|i+=1;puts "%x"%(i/2*273+(e*65&819))}

Przesunięcia są kodowane w każdym znaku ciągu magicznego w bazie 4 w formacie BAC, tj. Z 1-mi reprezentującymi prawy symbol, 16-mi reprezentującymi środkowy symbol, a lewy symbol ustawia się w pozycji 4. Aby je wyodrębnić, kod ascii jest mnożony przez 65 (binarny 1000001), aby dać BACBAC, a następnie jest dodawany do 819 (binarny 1100110011), aby dać .A.B.C.

Niektóre kody ascii mają ustawiony siódmy bit, tzn. Są o 64 wyższe od wymaganej wartości, aby uniknąć znaków kontrolnych. Ponieważ ten bit jest usuwany przez maskę 819, jest to nieistotne, z wyjątkiem sytuacji, gdy wartość Cwynosi 3, co powoduje przeniesienie. gTrzeba to poprawić tylko w jednym miejscu (zamiast tego musimy użyć c.)

Rev 0, wersja bez golfa

a= %w{000 010 000 201 100 100 011 021 110 120 011 112 111 221 211 221 122 123 112 222}
i=2
a.each{|e|puts "%x"%(i/2*273+e.to_i(16));i+=1}

Wynik

111
121
222
423
433
433
455
465
665
675
677
778
888
998
a99
aa9
abb
abc
bbc
ccc

Wyjaśnienie

Od następującego rozwiązania odejmuję linię bazową, podając przesunięcie, które przechowuję jako dane. Linia bazowa jest regenerowana jako liczba szesnastkowa w kodzie o i/2*273(273 po przecinku = 111 szesnastkowo).

solution   baseline   offset
AAA        AAA        000
ABA        AAA        010
BBB        BBB        000
DBC        BBB        201
DCC        CCC        100
DCC        CCC        100
DEE        DDD        011
DFE        DDD        021
FFE        EEE        110
FGE        EEE        120
FGG        FFF        011
GGH        FFF        112
HHH        GGG        111
IIH        GGG        221
JII        HHH        211
JJI        HHH        221
JKK        III        122
JKL        III        123
KKL        JJJ        112
LLL        JJJ        222
Level River St
źródło
Wygląda to tak samo jak moje, ale udało ci się uniknąć pojedynczej delty 4, która zmusiła mnie do zakodowania w bazie 5. Wygląda na to, że wybrałem niewłaściwe etykietowanie elementów.
Peter Taylor,
Zobaczyłem twoją odpowiedź po opublikowaniu mojej. Nie mogę podążać za Cjamem, ale z tego, co powiedziałeś w swojej odpowiedzi, jest to podobne podejście. Właściwie mam tylko jeden 3w całej tabeli (tuż u dołu), więc myślę, że zwiększając linię bazową o nieco więcej niż 0,5 w każdej linii, można faktycznie użyć bazy 3. Możesz spróbować tego. (Z powodów golfowych wydaje się, że będę musiał nieco zmienić linię bazową, co daje mi raczej więcej 3, i niestety wygląda na to, że będzie o 1 bajt dłuższy niż naiwne rozwiązanie w Ruby.)
Level River St
W przypadku, gdy wcześniej nie byłem jasny, chciałem pogratulować ci wykonania lepszej pracy niż ja, a nie oskarżyć cię o kopiowanie. I nie zamierzam próbować używać tempa wzrostu wynoszącego 2,5, ponieważ nie sądzę, że pobije to podejście kodowania różnic losowych.
Peter Taylor,
@PeterTaylor dzięki, dostałem, że mi gratulujesz. Z drugiej strony, najpierw wpadłeś na ten sam pomysł i skróciłeś go, więc gratuluję również tobie. Dzięki podejściu różnicowemu randomry mogę wreszcie stać się krótszy niż naiwne rozwiązanie. Działa również dobrze w 4x15 (biorąc pod uwagę odpowiedni układ pentomino). W ten sposób zrobiłbym to w C lub innym języku, który działa dobrze z ciągami 8.bit. Ponieważ Ruby obsługuje Unicode, próbuje interpretować ciągi 8-bitowe jako Unicode i może dawać denerwujące komunikaty o błędach.
Level River St
0

Foo, 66 bajtów

"00.@@@ccccF111//=---\n0...@@c))FFF1//8===-\n00.ttttt)))F1/8888=-"
Teoc
źródło
To jest znak po znaku identyczny z powyższym rozwiązaniem Microscript II ... Zakładam, że te języki są powiązane?
Darrel Hoffman,
1
@DatrelHoffman nie bardzo, foo po prostu drukuje wszystko w cudzysłowie
Teoc