Gra planszowa

W grze planszowej „ Carcassonne ” gracze umieszczają płytki, dopasowując ich krawędzie i zdobywając najwyższe wyniki, tworząc duże, ciągłe obszary terenu. Oto (z grubsza) rodzaje i ilości płytek zawartych w grze:

#01 x4 #02 x5 #03 x8 #04 x2

#05 x9 #06 x4 #07 x1 #08 x3

#09 x3 #10 x3 #11 x4 #12 x5

#13 x3 #14 x3 #15 x2 #16 x5

#17 x5 #18 x2 #19 x3 #20 x1

#21 x5 #22 x2 #23 x1 #24 x1

#25 x1

Zadanie

Musisz umieścić kafelek, dopasowując krawędzie, jednocześnie starając się utrzymać możliwie największe ciągłe obszary terenu.

Umieszczenie

• Płytki można umieszczać tylko na jednym (maksymalnie 4) pustych polach sąsiadujących z dowolnymi istniejącymi płytkami (lub płytkami) w obszarze gry.
• Płytki można obracać o 90, 180 lub 270 stopni.

Dopasowywanie krawędzi

• Krawędzie umieszczonej płytki muszą pasować do dotykających się krawędzi (do 4) sąsiadujących płytek, tj. Dotykające się piksele mają ten sam kolor.

Przyległy teren

• „Zamykanie obszaru terenu” odnosi się do umieszczenia płytki w taki sposób, że dalsze sąsiadujące obszary koloru nie mogłyby być kontynuowane przy dalszym umieszczaniu płytek.
• Jeśli możliwe jest alternatywne umieszczenie, należy je wybrać w stosunku do dowolnego położenia płytki, które zamknęłoby obszar terenu.
• Jeśli musisz wybrać jedną z wielu końcowych miejsc docelowych, wybierz dowolne. Jeśli musisz wybierać spośród wielu nie-zamkniętych miejsc docelowych, wybierz dowolne.
• Pomiń # ff00ff (piksele narożne) przy obliczaniu sąsiadujących obszarów. Pomiń także budynki, tj. Obszary koloru już całkowicie zamknięte w kafelku.

Wkład

• Dane wejściowe to dwa obrazy:

  1. Plac zabaw.

     • Początkowy obszar gry składa się z płytki #11(pojedynczej płytki).
     • Rozszerzony obszar gry utworzony jako wyjście musi być również obsługiwany jako wejście.

  2. Kafelek do umieszczenia.

     • Wszystkie przykładowe kafelki muszą być obsługiwane jako dane wejściowe.

• Określ pasujące krawędzie / ciągły teren, używając samych danych obrazu. Bez kodowania.

Wydajność

• Wyjście to obraz przedstawiający wynikowy obszar gry po umieszczeniu kafelka.
• Obraz musi być zgodny z twoim programem, tzn. Może być wykorzystany jako wejście do obszaru odtwarzania.
• Jeśli nie można umieścić kafelka, zwróć błąd.

Możesz to założyć

• Płytki mają zawsze rozmiar 55 na 55 pikseli
• Płytki będą zawsze miały kolory aktualnie używane w przykładowych kafelkach.

Notatki

• Twoja odpowiedź musi zawierać przykładowe wyniki po co najmniej 2 przejściach (zachęca się więcej).
• Jest to częściowe i niedokładne odwzorowanie oryginalnej gry planszowej, nie musisz stosować żadnych zasad i taktyk, które nie zostały tu wymienione.

Wynik

• Twój wynik to liczba bajtów przesłanych danych.
• Dane obrazu nie są uwzględniane w twoim wyniku.
• Najniższy wynik wygrywa.

Możesz napisać skrypt, który użyje twojego przesłania, aby zagrać w pełną grę, która może składać się z:

• Umieszczanie kafelka wybranego pseudolosowo z pełnego zestawu 85.
• Zwracanie kafelka do zestawu, jeśli nie można go umieścić.
• Powtarzanie do momentu umieszczenia każdego kafelka lub do momentu, gdy nie będzie można umieścić dwóch płytek z rzędu.

Nie zostanie uwzględniony w twojej liczbie bajtów ani nie poprawi twojego wyniku, ale prawdopodobnie zaoferuję nagrodę za tego rodzaju odpowiedź.

Perl 5 z PerlMagick: 875 789 763

Nie liczyłem linii zaczynającej się od sub w, która służy do sortowania pozycji w odległości od centrum, aby preferować kompaktowe rozwiązania (teraz działające poprawnie). W tej wersji unika się zamykania zgodnie z żądaniem, ale uważam, że przeciwieństwo jest bardziej interesujące i wierne grze. Aby to osiągnąć, zmień linię $s=$t if!grep...na $s=$t if grep....

use Image::Magick;
sub p{/x/;@o=$r->GetPixel(y=>$'+pop,x,$`+pop);"@o"}
sub o{$w=&p;"0 0 0"eq$w?3:&p eq$w}
sub f{$r->FloodfillPaint(y=>$J+$',x,$I+$&,channel,All,fill,@_)}
($i=Image::Magick->new)->Read(@ARGV);$r=$b=$i->[0];
$h=$b->Get(rows)+112;$:=$b->Get(width)+112;
$b->Extent(geometry,"$:x$h-56-56",background,none);
@v=grep p()eq"0 0 0",map{map-54+55*$_.x.($'*55-54),//..$:/55}1..$h/55;
sub w{$_=pop;/x/;abs($:-2*$`)+abs($h-2*$')}@v=sort{w($b)<=>w($a)}@v;
map{map{/x/;$I=$`;$J=$';$r=$b->Clone();
($t=$r)->Composite(image,$i->[1],x,$I,y=>$J);
if((o(27,0,27,-1)&o(0,27,-1,27)&o(27,54,27,55)&o(54,27,55,27))==1){
$s=$t if!grep{/../;$r=$t->Clone();f(none);f(red);
!grep{p()eq"1 0 0"}@v}
map{/..$/;($_,$&.$`)}map{($_.-1,$_.55)}10,27,45;
$o=$r=$t;}$i->[1]->Rotate(degrees,90)}($_)x4}@v;
$s||=$o or exit 1;$s->Trim();$s->Write("car.png")

Zastosowanie: perl car.pl board.png tile.png. Wynik zapisany w car.png. Status wyjścia to 1, jeśli nie można umieścić kafelka.

Skrypt do uruchomienia kompletnej gry. Zakłada ona, powyższy kod znajduje się w pliku car.pli płytki są przechowywane w tileskatalogu o nazwie 01.pngdo 25.png.

use List::Util shuffle;$x='00';
@t=shuffle map{($x++)x$_}split'',a4582941333353325523152111;
`cp tiles/11.png car.png`;
$i++,`perl car.pl car.png tiles/$_.png`,print"placed $i\n"for@t

Teraz działa to dość wolno. 8-12 minut na moim komputerze. Preferowane przy zamykaniu: przy unikaniu zamykania (uwaga: nic nie jest zamknięte).

Common Lisp, 2650 2221 1992 1186 1111 bajtów

Aktualizacja: „Łatwe” granie w golfa już wykonane, dalsze korzyści będą wymagać większych zmian.

Aktualizacja 2: Ponieważ konkurencja staje się coraz ostrzejsza, nowa wersja nie faworyzuje pozycji wewnątrz bieżącego prostokąta boiska (byłoby to dodatkowe 57 bajtów). Ta opcja, podobnie jak prosta optymalizacja prędkości, jest domyślnie włączona w wersji do pobrania z symulatorem, ale nie w oficjalnej odpowiedzi poniżej.

Aktualizacja 3: Niewielkie zmiany interfejsu dla zwiększenia liczby bajtów.

Stworzyłem również prosty internetowy interfejs użytkownika. Pełny pakiet (pojedynczy plik LISP i obrazy kafelków) można pobrać tutaj . Aby spróbować go zainstalować hunchentoot, zpnga png-readz quiclisp, obciążenie w carcassonne.lisp, i połączyć się localhost:8080. Kod został przetestowany na CCL / Windows i SBCL / Linux. Wyżej wymienione biblioteki są potrzebne tylko dla części interfejsu użytkownika / symulatora; samo rozwiązanie to zwykła ANSI Common Lisp.

(defun c(f p &aux b a s z(c 55))
  (macrolet((d(v l &body b)`(dotimes(,v,l),@b))
            (b(b c)`(d i c(d j c(setf,b,c))))
            (r(&rest p)`(aref,@p))
            (n(u v i j)`(and(setf l(*(f,u,v)l))
                            (find(r f(+,u,i)(+,v,j))`(0,(r f,u,v))))))
    (labels((p(p w)(d y(ceiling w 2)(d x(- w y y)(rotatef(r p y #6=(+ x y))(r p #6##7=(- w y))(r p #7##8=(- w x y))(r p #8#y)))))
            (a(y x)(or(if(= 0(r f y x))1 #4=(and(= 1(incf(r s y x)))(=(r f y x)z)(push`(,y,x)a)0))0))
            (f(y x)(setf z(r f y x))(if #4#(loop for((y x))= a while(pop a)maximize(+(a(1- y)x)(a y(1- x))(a(1+ y)x)(a y(1+ x))))1)))
      (d i 8(when(d x #1=(array-dimension f 0)(or(= 0(r f(- #1#52 i)x))(return t)))(setf f(adjust-array f`(#2=,(+ #1#c)#2#))))(p f(1- #1#)))
      (d i 4(d u #9=(/ #1#c)(d v #9#
        (let((y(* u c))(x(* v c))(l 9e9))
          (when(= 0(r f y x))
            (b #10=(r f(+ y i)(+ x j))(r p i j))
            (setf s(make-array`(,#1#,#1#))a())
            (ignore-errors(if(> #11=(*(loop for d from 1 to 53
                                            sum(+(n y #3=(+ x d)-1 0)(n #5=(+ y d)(+ 54 x)0 1)(n(+ 54 y)#3#1 0)(n #5#x 0 -1)))
                                      (1+ l))
                                (or(car b)0))
                             (setf b`(,#11#,i,y,x))))
            (b #10#0)))))
         (p p 54))
      (when b(d j(cadr b)(p p 54))(b(r f(+(third b)i)(+(nth 3 b)j))(r p i j)))
      `(,f,b))))

Wszystkie linie i odstępy między wierszami dotyczą wyłącznie kosmetyków, aby zapewnić czytelność, i nie są liczone do łącznej sumy.

Powinieneś wywołać funkcję cz dwoma argumentami: bieżącym polem gry i kafelkiem do umieszczenia. Oba powinny być tablicami 2D; kafelek 55x55 i pole wielokrotność tego. Dodatkowo pole pola musi być regulowane. Funkcja zwraca dwuelementową listę z nowym polem jako pierwszym argumentem. Drugi element dotyczy sytuacji, NILgdy kafelek nie może zostać umieszczony, lub w przeciwnym razie lista zawierająca współrzędne po lewej u góry i obrót najnowszego kafelka w tej tablicy oraz wynik dla tego kafelka. Informacje te można wykorzystać do celów wizualizacji.

Zauważ, że w kolejnych wywołaniach musisz użyć nowego pola zwróconego przez, cnawet jeśli drugim elementem listy jest NIL(oryginalna tablica mogła zostać adjust-arrayedytowana, a tym samym unieważniona).

Kod jest teraz nieco wolniejszy, optymalizacja liczby bajtów skutkuje zbędnymi obliczeniami. Poniższy przykład został ukończony w moim systemie za około trzy minuty.

Przykładowy przebieg dla wszystkich 85 kafelków:

Zrzut ekranu interfejsu sieciowego:

DarkBASIC Pro: 2078 1932 1744 bajtów

AKTUALIZACJA: Jeszcze więcej wysiłku w golfa

AKTUALIZACJA: Teraz w pełni spełnia specyfikację, w tym preferowanie opcji nie zamykających.

Wybrałem DarkBASIC, ponieważ chociaż jest dość szczegółowy, zapewnia niezwykle prosty i prosty zestaw poleceń do manipulowania obrazami.

Przesłałem plik EXE dla osób, które nie mają kompilatora DarkBASIC ( Windows ).

#constant m memblock
#constant f function
#constant k endfunction
#constant z exitfunction
#constant i image
#constant e endif
#constant t then
#constant o or
#constant s paste image
#constant n next
#constant r for
set i colorkey 0,20,0:load i "map.png",1:f$="next.png"
if file exist(f$)=0 t f$=str$(rnd(24)+1)+".png"
load i f$,2:make m from i 1,1:make m from i 2,2
global ts,h,j,u,v,td
ts=i width(2):h=i width(1):j=i height(1):u=h/ts:v=j/ts:td=ts*2
create bitmap 2,h+td+1,j+td+1:r b=1 to 4:r xx=0 to u+1:r yy=0 to v+1:x=xx*ts-1:y=yy*ts-1
cls 5120:s 1,ts,ts,1:if (a(x+1,y) o a(x,y+1) o a(x-ts,y) o a(x,y-ts)) and a(x,y)=0
x1=ts*xx:y1=ts*yy:make i from m 2,2:s 2,x1,y1,1
cl=0:r fd=0 to 1:r x2=1 to ts-2:r yt=0 to 1:y2=yt*ts-yt:y3=yt*ts+yt-1
aa=x2:ab=x2:ba=y2:bb=y3:t2=y1:r t3=0 to 1:p=point(x1+aa,y1+ba):q=point(x1+ab,y1+bb)
if p<>q and rgbg(q)<>20 and t2+b>0 t goto fa
if fd and p<>0xFF0000
if l(x1+aa,y1+ba,p)=0 t cl=1
e
aa=y2:ba=x2:bb=x2:ab=y3:t2=x1:n t3:n yt:n x2:n fd:dn=1:c=xx-1:g=yy-1:make i from m 3,2:if cl=0 t goto dm
e
fa:
n y:n x
d=ts/2:r x=0 to d:r y=0 to d-1:vx=ts-1-x:vy=ts-1-y:t1=rd(x,y):t2=rd(vy,x):wr(vy,x,t1):t1=rd(vx,vy):wr(vx,vy,t2):t2=rd(y,vx):wr(y,vx,t1):wr(x,y,t2):n x:n y:n b
dm:
if dn=0 t report error "Not placed"
p=c<0:q=g<0:t1=h+ts*(p o c>=u):t2=j+ts*(q o g>=v):cls 5120:p=ts*p:q=ts*q:s 1,p,q,1:s 3,c*ts+p,g*ts+q,1:get i 1,0,0,t1,t2,1:save i "map.png",1
end
f l(x,y,w)
if x<0 o y<0 o x>=h+td o y>=j+td t z 1
p=point(x,y)
if rgbg(p)=20 t z 1
if p<>w t z 0
dot x,y,0xFF0000:rt=l(x+1,y,p) o l(x-1,y,p) o l(x,y+1,p) o l(x,y-1,p)
k rt
f rd(x,y)
w=m dword(2,0):b=m dword(2,12+(y*w+x)*4)
k b
f wr(x,y,d)
w=m dword(2,0):write m dword 2,12+(y*w+x)*4,d
k
f a(x,y)
if x<0 o y<0 o x>=h o y>=j t z 0
b=m byte(1,15+(y*h+x)*4)
k b