Nagrody

Nr 1 ( nagrodzony )

Wrzucę 50 powtórzeń za pierwszą prawidłową odpowiedź

Nr 2 ( nagrodzony )

Wrzucę kolejne 100 powtórzeń za najkrótszą prawidłową odpowiedź.

Nr 3 ( otwarty na zgłoszenia) )

Wrzucę 200 powtórzeń dla pierwszego z istotnie krótszą prawidłową odpowiedzią. Znaczące, co najwyżej 45% obecnie najkrótszej odpowiedzi ( 564 bajtów x 0,45 = maks. 254 bajtów ).

Gra

Pamiętasz klasyczną grę „ Nine Men's Morris ” czy po prostu „ Mill ”? Istnieje odmiana o nazwie Three Men's Morris, która jest trochę jak zmienny kółko i krzyżyk.

Zasady

Oto pusta plansza gry:

   a   b   c
1 [ ]–[ ]–[ ]
   | \ | / |
2 [ ]–[ ]–[ ]
   | / | \ |
3 [ ]–[ ]–[ ]

[ ] jest polem i |–/\ reprezentuje trasy między tymi polami.

Gra rozgrywana jest przez dwóch graczy 1i 2którzy każdego Place 3 żetony na planszy. To się już zdarzyło i jesteśmy w grze. Gra zostaje wygrana, jeśli jeden gracz może utworzyćmill pionowy lub poziomy rząd 3 żetonów gracza.

Tokeny można przenosić na planszy wzdłuż linii łączących, zgodnie z tą zasadą:

Do dowolnego sąsiedniego pustego położenia (tj. Od położenia krawędzi do środka lub od środka do położenia krawędzi lub od położenia krawędzi do sąsiedniej pozycji krawędzi

Gracz musi wykonać ruch, chyba że nie ma sąsiedniej pustej pozycji, w którym to przypadku ruch jest pomijany.

Wyzwanie

Jesteś graczem, 1a twój ruch jest następny. Napisz program lub funkcję, która określa, czy:

• możesz wymusić wygraną 2 lub mniej ruchami ( ostateczna wygrana )
• możesz wygrać 2 lub mniej ruchami, jeśli twój przeciwnik popełni błąd ( możliwa wygrana )
• nie możesz wygrać z 2 lub mniej ruchami, ponieważ potrzebujesz więcej ruchów lub ponieważ ruchy wymuszone prowadzą przeciwnika do zwycięstwa ( niemożliwe do wygrania )

Wymagania

• Nawet jeśli zdecydowanie wygrasz, gdy nudzisz przeciwnika na śmierć, twój program musi zakończyć się w określonym czasie.
• Możesz napisać program lub funkcję.

Wejście

Gracze są reprezentowani przez 1i 2. 0określa wolne pole. Możesz przyjmować dane wejściowe jako macierz lub tablicę.

Określony

A         B         C         D
2 1 0  |  2 1 0  |  1 0 1  |  1 2 2
2 1 2  |  0 1 0  |  1 0 2  |  2 1 O
0 0 1  |  2 2 1  |  0 2 2  |  O O 1

A: [2,1,0,2,1,2,0,0,1]
B: [2,1,0,0,1,0,2,2,1]
C: [1,0,1,1,0,2,0,2,2]
D: [1,2,2,2,1,0,0,0,1]

Możliwy

A         B         C
1 0 1  |  1 0 1  |  1 2 2
1 2 2  |  1 2 0  |  0 0 1
2 0 0  |  2 0 2  |  2 1 0

A: [1,0,1,1,2,2,2,0,0]
B: [1,0,1,1,2,0,2,0,2]
C: [1,2,2,0,0,1,2,1,0]

Niemożliwy

A         B    
1 0 0  |  1 2 0
1 2 2  |  2 1 0
2 0 1  |  1 2 0

A: [1,0,0,1,2,2,2,0,1]
B: [1,2,0,2,1,0,1,2,0]

Wynik

Twój program powinien wypisać / zwrócić buźkę:

• Zdecydowana wygrana: :)
• Możliwa wygrana: :|
• Nie można wygrać: :(

Przykłady

Zdecydowana wygrana w dwóch ruchach:

[2][1][ ] 1. [2][1][ ]
[2][1][2] -> [2][1][2]
[ ][ ][1]    [ ][1][ ]

[2][1][ ] 1. [2][1][ ]    [ ][1][ ] 2. [ ][ ][1]
[ ][1][ ] -> [ ][ ][1] -> [2][ ][1] -> [2][ ][1]
[2][2][1]    [2][2][1]    [2][2][1]    [2][2][1]

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][ ][2] -> [1][ ][2] -> [1][ ][2] -> [ ][ ][2]
[ ][2][2]    [ ][2][2]    [2][ ][2]    [2][ ][2]

Możliwe zwycięstwo w dwóch ruchach:

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2]    [2][ ][2]    [2][ ][ ]    [2][ ][ ]

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2]    [2][ ][2]    [2][ ][ ]    [2][ ][ ]

[1][2][2] 1. [ ][2][2]    [2][ ][2] 2. [1][2][2]
[ ][ ][1] -> [1][ ][1] -> [1][ ][1] -> [1][1][1]
[2][1][ ]    [2][1][ ]    [2][1][ ]    [2][ ][ ]

Nie można wygrać w dwóch ruchach:

[1][ ][ ]
[1][2][2]
[2][ ][1]

Premia

W przypadku, gdy możliwa jest określona wygrana, a Twój program generuje ruchy jednej drogi do sukcesu, a także a1:a2(1 ruch) lub a1:a2,a3:b2(2 ruchy), możesz wycofać 30% liczby bajtów.

To jest golf golfowy - wygrywa więc najkrótsza odpowiedź w bajtach. Standardowe luki są niedozwolone.

_{Podziękowania dla Petera Taylora, który naprawił kilka błędów i poprawił brzmienie w piaskownicy .}

Haskell, 580 564 441 bajtów

Tak daleko mogę teraz grać w golfa. Nie jestem pewien, czy inne języki to pokonają.

Wywołaj mlistę takich jak [[2,1,0],[2,1,2],[0,0,1]](Definite A).

import Data.Array
r=[0..2]
p?f=[(x,y)|x<-r,y<-r,f!y!x==p]
p%f=all(==x)xs||all(==y)ys where(x:xs,y:ys)=unzip$p?f
s p x y f=f//[(y,f!y//[(x,p)])]
p#f=[s 0 x y$s p u v f|a@(x,y)<-p?f,b@(u,v)<-0?f,((x-u)*(y-v)==0&&abs(x+y-u-v)==1)||elem(1,1)[a,b]]
p&f|p#f>[]=p#f|0<1=[f]
e=any
i a p f=e(a$e(p%))(map(map(p&))(map((3-p)&)$p&f))||e(p%)(p&f)
l=listArray(0,2)
f(True,_)=":)"
f(False,True)=":|"
f _=":("
m=putStrLn.f.(\f->(i all 1 f,i e 1 f)).l.map l

Kod testowy:

da = [[2,1,0],[2,1,2],[0,0,1]]
db = [[2,1,0],[0,1,0],[2,2,1]]
dc = [[1,0,1],[1,0,2],[0,2,2]]
dd = [[1,2,2],[2,1,0],[0,0,1]]
pa = [[1,0,1],[1,2,2],[2,0,0]]
pb = [[1,0,1],[1,2,0],[2,0,2]]
pc = [[1,2,2],[0,0,1],[2,1,0]]
ia = [[1,0,0],[1,2,2],[2,0,1]]
ib = [[1,2,0],[2,1,0],[1,2,0]]
al = [da,db,dc,dd,pa,pb,pc,ia,ib]

mapM_ m al zwroty:

:)
:)
:)
:)
:|
:|
:|
:(
:(

C # - 739 663 bajtów

Kompletny program, odczytuje dane wejściowe z argv i wydaje się działać. Uruchom to jak

ThreeMill 1 2 1 1 2 0 0 0 2

Jeśli ta metoda wprowadzania danych jest niedopuszczalna, chętnie ją zmienię (nigdy nie lubię używać argv).

using System;using System.Linq;class P{static void Main(string[]A){var I=new[]{0,3,6,1,4,7,2,5,8};Func<string[],string>J=S=>S[0]+S[1]+S[2]+" "+S[3]+S[4]+S[5]+" "+S[6]+S[7]+S[8]+" ";Func<string[],string,int>W=(B,p)=>(J(B)+J(I.Select(i=>B[i]).ToArray())).Contains(p+p+p)?1:0;Func<string[],string,string[][]>V=(B,p)=>I.SelectMany(a=>I.Where(b=>a!=b&B[a]==p&B[b]=="0"&(a==4|b==4|a-b==3|b-a==3|((a-b==1|b-a==1)&a/3==b/3))).Select(b=>{var N=(string[])B.Clone();N[b]=p;N[a]="0";return N;})).DefaultIfEmpty(B).ToArray();int h,G;Console.WriteLine(":"+"(|))"[V(A,"1").Max(z=>((h=0)<(G=V(z,"2").Sum(j=>V(j,"1").Max(q=>W(q,"1")-W(q,"2"))+h++*0))?1:0)+(h>G?W(z,"1")*2:2))]);}}

Nie byłem skłonny publikować tego wczoraj, ponieważ nie byłem w stanie dużo zagrać w golfa (nie miałem tyle czasu i być może nie trenowałem), ale ponieważ nie otrzymałem jeszcze odpowiedzi, „ W każdym razie opublikuję to, z pewnością nie spodziewam się nagrody, wolałbym, żeby trafił do kogoś, kto włoży trochę więcej wysiłku przed wysłaniem!

Edytować: zastąpiłem wszystkie boole intami, co oznaczało, że mogłem lepiej wykorzystać Linq, i udało mi się zwinąć obie pętle foreach, dając duże oszczędności. Jestem nieco zaskoczony, że hlicznik działa ... ++ jest tak subtelnym narzędziem.

Program jest bardzo prosty, po prostu bada każdy możliwy zestaw ruchów (przechowuje stan planszy w ciągu []). Powtarza wszystkie nasze możliwe ruchy (tablice, które z nich wynikają) i zlicza liczbę odpowiedzi naszego przeciwnika, które możemy pokonać ( ). Jeśli uda nam się wygrać, to jest to możliwe i dodajemy 1 do sumy, jeśli możemy wygrać je wszystkie, jest to określony i dodajemy 2 do sumy. Niektóre maksimum jest zatem naszym najlepszym możliwym wynikiem, i indeksujemy ciąg „(|))”, aby zwrócić odpowiednią twarz. Zauważ, że potrzebujemy dodatkowego „)”, ponieważ suma może wynosić 2 lub 3, jeśli jest to określona (możliwe, że nie jesteśmy w stanie pokonać żadnych odpowiedzi, które już wygrały za pierwszym razem, więc możliwa kontrola to odrobinę wprowadzające w błąd).G ), czyli te, które wygrywamy, a on nie. Liczy także liczbę możliwych odpowiedzi (h

Program sprawdza zwycięstwo, wytwarzając ciąg z planszy, czyli oddzielone spacjami rzędy i kolumny, i po prostu szuka ciągu 3 postaci gracza w tym ciągu (np. „201 201 021 220 002 111” to wygraj dla nas)

using System;
using System.Linq; // all important

class P
{
    static void Main(string[]A) // transform to int?
    {
        var I=new[]{0,3,6,1,4,7,2,5,8}; // vertical indexes
        Func<string[],string>J=S=>S[0]+S[1]+S[2]+" "+S[3]+S[4]+S[5]+" "+S[6]+S[7]+S[8]+" "; // joins the strings up, so that there is a space separating each group of three (including at end)
        Func<string[],string,int>W=(B,p)=>(J(B)+J(I.Select(i=>B[i]).ToArray())).Contains(p+p+p)?1:0; // checks if a particular player wins
        Func<string[],string,string[][]>V=(B,p)=>I.SelectMany(a=>I // for each imagineable move
            .Where(b=>a!=b&B[a]==p&B[b]=="0"&(a==4|b==4|a-b==3|b-a==3|((a-b==1|b-a==1)&a/3==b/3))) // where it's legal
            .Select(b=>{var N=(string[])B.Clone();N[b]=p;N[a]="0";return N;}) // select the resulting board
        ).DefaultIfEmpty(B) // allow not-moving
        .ToArray();

        int h, // h stores the number of responses the opponent has to each move
        G; // G stores the number of responses by the opponent we can beat

        Console.WriteLine(":"+"(|))"[ // we index into this to decide which smiley
            V(A,"1").Max(z=>
                    ((h=0)<(G=V(z,"2").Sum(j=>V(j,"1").Max(q=>W(q,"1")-W(q,"2"))+h++*0))?1:0) // if there is atleast 1 reponse by the opponent we can beat, we can possibly win
                    +(h>G?W(z,"1")*2:2) // if there are moves which we can't win, then if we have already won (one-move), else, we can definitely win
                   ) // sum is therefore 0 if impossible, 1 if possible, >2 (no more than 3) if definite 
            ]);

    }
}

Oto mój skrypt testowy:

ThreeMill 2 1 0 2 1 2 0 0 1
ThreeMill 2 1 0 0 1 0 2 2 1
ThreeMill 1 0 1 1 0 2 0 2 2
ThreeMill 1 2 2 2 1 0 0 0 1

ThreeMill 1 0 1 1 2 2 2 0 0
ThreeMill 1 0 1 1 2 0 2 0 2
ThreeMill 1 2 2 0 0 1 2 1 0

ThreeMill 1 0 0 1 2 2 2 0 1
ThreeMill 1 2 1 1 2 0 0 0 2
ThreeMill 1 0 1 2 0 2 1 0 2

Które wyjścia

:)
:)
:)
:)
:|
:|
:|
:(
:|
:)

PowerShell 576 550 bajtów

Nie będę tak łatwo odstraszać - jeśli nie mogę uzyskać C # poniżej 631 bajtów, będę musiał użyć innego języka! Mam nadzieję, że Leif Willerts straci 5 bajtów z jego odpowiedzi, ponieważ zdecydowałem, że nie przepadam za PowerShellem, może po prostu muszę spojrzeć na to obiektywnie pod względem liczby bajtów ...

To jest skrypt, uruchamiasz go . .\mill.ps1 "201102021". To całkiem dobrze kopia mojej odpowiedzi w języku C #, tylko w języku, z którym nie mam doświadczenia. Nie poczyniłem zbyt wiele wysiłku, aby zagrać w golfa, ponieważ zajęło to tak dużo czasu, aby zacząć pracę, i jest już dość kompaktowy.

Edycja: nie można po prostu zostawić tam tych [Math]::Floorpołączeń

param($U);$I=0,3,6,1,4,7,2,5,8;function J($S){($S[0..2]+" "+$S[3..5]+" "+$S[6..8]-join"").Contains($p*3)}function W($D,$p){(J $D)-or(J $D[$I])}function V($Q,$C){$I|%{$a=$_;$I|?{$a-ne$_-and$Q[$a]-eq$c-and$Q[$_]-eq"0"-and($a-eq4-or$_-eq4-or$a-$_-eq3-or$_-$a-eq3-or(($a-$_-eq1-or$_-$a-eq1)-and$a/3-$a%3/3-eq$_/3-$_%3/3))}|%{$b=$Q[0..8];$b[$_]=$c;$b[$a]=0;$b-join''}}|%{$n=1}{$n=0;$_}{if($n){$Q}}}$e=$f=0;V $U "1"|%{$h=0;$x=$_;V $x "2"|%{$k=0;(V $_ "1"|%{if((W $_ "1")-and!(W $_ "2")){$k=$e=1}});$h+=1-$k};if($h-eq0-or(W $x "1")){$f=2}};":"+"(|))"[$e+$f]

Jeśli opisujesz, jak to działa ... odpowiedź w języku C # jest dla Ciebie, ale mam nadzieję, że komentarze wyraźnie ją wyjaśnią. Średniki mogą nie pasować idealnie do polecenia jednowierszowego, nie jestem jeszcze pewien, gdzie są potrzebne i nie są, i nie skopiowałem ich z powrotem, gdy umieściłem całość w jednym wierszu.

param($U); # take input as argument

$I=0,3,6,1,4,7,2,5,8; # cols

function J($S){ # checks if this is a winning string
($S[0..2]+" "+$S[3..5]+" "+$S[6..8]-join"").Contains($p*3)}

function W($D,$p){ # checks if this is a winning board
(J $D)-or(J $D[$I])} # $D[$I] reorganises into columns

function V($Q,$C){ # yields all valid moves from position $Q for player $C
$I|%{$a=$_;$I| # for each possible move
?{$a-ne$_-and$Q[$a]-eq$c-and$Q[$_]-eq"0"-and($a-eq4-or$_-eq4-or$a-$_-eq3-or$_-$a-eq3-or(($a-$_-eq1-or$_-$a-eq1)-and$a/3-$a%3/3-eq$_/3-$_%3/3))}| # where legal
%{$b=$Q[0..8];$b[$_]=$c;$b[$a]=0;$b-join''}}| # make the move (copy $Q to an array, modify, join into a string)
%{$n=1}{$n=0;$_}{if($n){$Q}}} # if empty, return $Q - I am confident this can be achieved with commas, and [0], and maybe a +, but I don't want to think about it

$e=$f=0; # possible, definite

V $U "1"|%{ # for all our possible moves
$h=0;$x=$_; # $k is whether we win all of these
  V $x "2"| # for all opponent's responses
  %{$k=0;(V $_ "1"| # for all our responses
  %{if((W $_ "1")-and!(W $_ "2")){$k=$e=1}});$h+=1-$k}; # if we can win and he can't, then things are looking good, set $e to 1 (possible win)

  if($h-eq0-or(W $x "1")){$f=2} # if we win every move, or we have already won, it's a definite
};

":"+"(|))"[$e+$f] # smile, it's all over

Skrypt testowy (PowerShell):

. .\mill.ps1 "210212001"
. .\mill.ps1 "210010221"
. .\mill.ps1 "101102022"
. .\mill.ps1 "122210001"

. .\mill.ps1 "101122200"
. .\mill.ps1 "101120202"
. .\mill.ps1 "122001210"

. .\mill.ps1 "100122201"
. .\mill.ps1 "121120002"
. .\mill.ps1 "101202102"

. .\mill.ps1 "100122201"
. .\mill.ps1 "120210120"

Wyjście:

:)
:)
:)
:)
:|
:|
:|
:(
:|
:)
:(
:(

Python 3, 566 557 bajtów

Będę musiał sprawdzić, czy mogę dalej grać w golfa, czy też mogę uzyskać 30% premii, ale po dłuższym zwlekaniu oto moja odpowiedź.

def t(g,x=1,r=0,z=0):
 m=[[1,3,4],[0,2,4],[2,4,5],[0,4,6],[0,1,2,3,5,6,7,8],[2,4,8],[3,4,7],[4,6,8],[4,5,7]];a=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]];z=z or[[],[],[],[]];s=0
 if r>3:return z
 for i in a:
  if g[i[0]]==g[i[1]]==g[i[2]]>0:s=g[i[0]];break
 z[r]+=s,
 for q in range(9):
  i=g[q]
  if i==x:
   for p in m[q]:
    if g[p]<1:n=g[:];n[q],n[p]=n[p],n[q];z=t(n,3-x,r+1,z)
 if r:return z
 else:
  w=l=0
  for j in range(4):w=w or 1in z[j];l=l or 2in z[j]
  if l<1and w:return":)"
  elif w<1and l:return":("
  else:return":|"

Nie golfowany:

def three_mens_morris(grid, player=1, rec=0, w_l=0, p=0):
    moves = [[1,3,4],[0,2,4],[2,4,5],[0,4,6],[0,1,2,3,5,6,7,8],[2,4,8],[3,4,7],[4,6,8],[4,5,7]]
    w_l = w_l or [[],[],[],[]]
    if rec == 4: return w_l
    result = check_grid(grid)
    w_l[rec].append(result)
    for sq_1 in range(len(grid)):
        piece = grid[sq_1]
        if piece == player:
            for sq_2 in moves[sq_1]:
                if grid[sq_2] == 0:
                    new_grid = grid.copy()
                    new_grid[sq_1],new_grid[sq_2]=new_grid[sq_2],new_grid[sq_1]
                    w_l = three_mens_morris(new_grid,3-player,rec+1,w_l)
    if p: print(w_l)
    if rec:
        return w_l
    else:
        win = loss = 0
        for i in range(4):
            if 1 in w_l[i]:
                win = 1
            elif 2 in w_l[i]:
                loss = 1
        if p:print(win,loss)
        if loss==0 and win:
            return ":)"
        elif loss and win==0:
            return ":("
        else:
            return ":|"

def check_grid(grid):
    rows = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
    for i in rows:
        if grid[i[0]]==grid[i[1]]==grid[i[2]] and grid[i[0]]:
            return grid[i[0]]
    return 0