To jest golf golfowy .

W tym wyzwaniu będziemy pisać programy / funkcje, które rozwiązują zagadki „ Rycerze i Łowcy ”.

tło

Znajdziesz się na wyspie ... itd. ... każda osoba na wyspie oprócz ciebie jest rycerzem lub łajdakiem .

Rycerze mogą składać tylko prawdziwe oświadczenia.

Łotr może składać tylko fałszywe oświadczenia.

Nie chcę rygorystycznie definiować „oświadczenia”, ale powiemy, że oświadczenie jest czymkolwiek, co jest albo „prawdziwe”, albo „fałszywe”. Zauważ, że wyklucza to zdania paradoksalne.

Na potrzeby tego wyzwania napotkasz grupy wyspiarzy; złożą ci oświadczenia.

Twoim zadaniem jest ustalenie, kto jest rycerzem, a kto łotrem.

Wejście:

Otrzymasz (w dowolnym rozsądnym formacie) następujące informacje:

• Lista obecnych osób. Zostaną nazwane wielkimi literami „AZ”. Narzucony przez nie limit liczby osób nie zostanie przekroczony.

• Oświadczenia, które składa każda osoba. Poniżej znajdują się ważne szczegóły na ten temat.

Wynik

Następnie wydrukujesz (w dowolnym rozsądnym formacie), czym jest każda osoba. Na przykład, jeśli byliby gracze A B C Di Abył rycerzem, ale reszta to łajdaki, możesz wyjść

A: 1
B: 0
C: 0
D: 0

Ważne szczegóły:

• Wielkie litery alfabetu AZ odnoszą się do wyspiarzy.

• Znaki 0(zero) i 1(jeden) odnoszą się odpowiednio do „Knave” i „Knight”. (Możesz dowolne dwa inne znaki inne niż AZ, o ile określisz)

• Każdy obecny wyspiarz może złożyć dowolną naturalną liczbę oświadczeń lub może nic nie mówić.

• W instrukcjach można używać normalnych operatorów logicznych ( IS *, AND, OR, NOT ). Oprócz tego, praw de Morgana i warunkowe mogą być użyte. Poniżej znajdują się przykłady, w jaki sposób mogą być prezentowane w formie mówionej, a następnie w jaki sposób mogą być wprowadzane do twojego programu.

(* w bardziej technicznych uwagach. Operator „IS” jest naprawdę używany jako zabezpieczenie (co nie jest operatorem logicznym). Kiedy mówię „A jest rycerzem”, naprawdę mam na myśli, że „A jest członkiem zestawu Knights ". Prawdziwym operatorem byłby„ ϵ ”. Dla uproszczenia zamiast tego użyjemy„ = ”.)

Korzystam z następujących (możesz używać czegokolwiek, o ile jest to uzasadnione i spójne):

• ^ I
• v LUB
• = JEST
• ~ NIE
• => IMPLIKACJE
• X:Osoba X twierdzi, że ...

Osoba Z może wykonać dowolną kombinację dowolnego z następujących rodzajów oświadczeń:

Osoba Z mówi, że ...

1. Osoba A jest rycerzem.

   Z: A = 1

2. Osoba Q jest Łowcą.

   Z: Q = 0

3. Jestem rycerzem.

   Z: Z = 1

4. Osoba A jest rycerzem LUB Osoba B jest rycerzem.

   Z: ( A = 1 ) v ( B = 1)

5. Osoba C jest rycerzem, a ja jestem Knave.

   Z: ( C = 1 ) ^ ( Z = 0 )

6. Osoba R NIE jest rycerzem.

   Z: ~( R = 1 )

Ponadto dane wejściowe mogą również wykorzystywać prawa De Morgana

7. NIE jest prawdą, że zarówno osoba A, jak i osoba B są Łotrami

   Z: ~( ( A = 0 ) ^ ( B = 0 ) )

8. Fałszem jest, że osoba A lub osoba B jest rycerzem

   Z: ~( ( A = 1 ) v ( B = 1) )

Wreszcie można zastosować warunki warunkowe i ich negacje

9. Jeśli jestem rycerzem, osoba B jest Knave

   Z: ( Z = 1 ) => ( B = 0 )

10. NIE jest prawdą, że jeśli osoba B jest rycerzem, to osoba C jest podstępem.

    Z: ~( ( B = 1 ) => ( C = 0 ) )

Uwagi na temat warunków warunkowych

Sprawdź wikipedię, aby uzyskać więcej informacji.

Instrukcja warunkowa przybiera postać p => q , gdzie p i q same są instrukcjami. p jest „poprzednikiem”, a q jest „konsekwencją”. Oto kilka przydatnych informacji

• Negacja warunku wygląda następująco: ~ (p => q) jest równoważne p ^ ~ q

• Fałszywa przesłanka implikuje wszystko. To znaczy: jeśli p jest fałszem, to dowolna instrukcja p => q jest prawdą, niezależnie od tego, czym jest q . Na przykład: „jeśli 2 + 2 = 5, to jestem Spiderman” to prawdziwe stwierdzenie.

Kilka prostych przypadków testowych

Przypadki te są podane w następujący sposób (1), w jaki sposób przedstawilibyśmy problem w mowie (2), w jaki sposób moglibyśmy przedstawić komputerowi (3) prawidłowe dane wyjściowe, które może dać komputer.

1. Osoba A i osoba B podchodzą do ciebie na drodze i składają następujące oświadczenia:

   Odp .: B to łotr lub ja jestem rycerzem.

   B: A jest rycerzem.

Odpowiedź:

B to Rycerz, a A to Rycerz.

Wejście:

A B        # Cast of Characters
A: ( B = 0 ) v ( A = 1)
B: A = 1

Wynik:

    A = 1
    B = 1
    

2. Osoby A, B i F podchodzą do ciebie na drodze i składają następujące oświadczenia:

   Odp .: Jeśli jestem rycerzem, B jest Knave.

   B: Jeśli to prawda, to F też jest Knave.

Odpowiedź:

A to Rycerz, B to Knave, F to Rycerz.

Wejście

A B F
A: ( A = 1 ) => ( B = 0 )
B: ( A = 1 ) => ( F = 0 ) 

Wynik:

    A = 1
    B = 0
    F = 1
    

3. Q, X i W podchodzą do ciebie na drodze i składają następujące oświadczenia:

   W: To nieprawda, że ​​zarówno Q, jak i X są Rycerzami.

   P: To prawda.

   X: Jeśli to, co mówi W, jest prawdą, to co mówi Q, jest fałszywe.

Odpowiedź:

W i Q są Rycerzami. X to Łotr.

Wejście

Q X W
W: ~( ( Q = 1 ) ^ ( X = 1 ) )
Q: W = 1
X: ( W = 1 ) => ( Q = 0 )

Wynik

    W = 1
    Q = 1
    X = 0
    

Istnieje podobne wyzwanie sprzed 3 lat, które koncentruje się na analizie składni i nie zawiera warunkowych ani De Morgana. A zatem, jak twierdzę, jest wystarczająco różny pod względem ukierunkowania i wdrożenia, aby uniknąć tego problemu.

To wyzwanie zostało na krótko zakończone jako oszustwo. Od tego czasu został ponownie otwarty.

Twierdzę, że to wyzwanie jest przede wszystkim inne. Drugie wyzwanie koncentruje się na analizie angielskiego, ale tak nie jest. Po drugie, używa tylko AND i OR, podczas gdy używa to warunkowe i pozwala na rozwiązywanie wielu innych zagadek. Ostatecznie pytanie brzmi: czy odpowiedzi na to wyzwanie można w prosty sposób zastąpić tym, i uważam, że włączenie warunków warunkowych i negacji warunkowych zapewnia wystarczającą złożoność, że należy wprowadzić bardziej zdecydowane zmiany, aby aby sprostać temu wyzwaniu.

Python 3, 450 342 307 bajtów

Edycja: okazuje się, że zapomniałem importu ...

Moje pierwsze rozwiązanie wykorzystuje elastyczne nazewnictwo zapytań

from functools import*
def g(c,r):c=c.split();l,y=len(c),range;d=[dict((c[i],n>>i&1)for i in y(l))for n in y(2**l)];return[n[1]for n in[[eval(reduce(lambda x,y:x.replace(y,str(d[i][y])),d[i],')and '.join(['not',''][d[i][s[0]]]+'('+s[2:].replace('->','<1or')for s in r)+')')),d[i]]for i in y(len(d))]if n[0]]

Możesz zadzwonić do powyższego za pomocą

g('Q X W', ['W: not( ( Q == 1 ) and ( X == 1 ) )','Q: W == 1', 'X: ( W == 1 ) -> ( Q == 0 )'])

Następny tutaj używa tego samego formatu zapytań, co widziany w PO, nie ma też niektórych modyfikacji, które wprowadziłem w pierwszym. Ma 417 bajtów, ponieważ konwertuje między dwoma formatami.

from functools import*
def g(c,r):c=c.split();l,y=len(c),range;d=[{**dict((c[i],n>>i&1)for i in y(l)),**{'v':'or','^':'and','=':'==','~':'not'}}for n in y(2**l)];f=lambda r,c:reduce(lambda x,y:x.replace(y,str(c[y])),c,('(0<1'+''.join([')^ '+['~',''][c[t[0]]]+'('+t[1]for t in[s.split(":")for s in r]])+')').replace('=>','<1or'));return[dict((o,j) for o,j in n[0].items() if o in c) for n in[[d[i],eval(f(r,d[i]))]for i in y(len(d))]if n[1]]

Można to nazwać:

g('Q X W', ['W: ~( ( Q = 1 ) ^ ( X = 1 ) )','Q: W = 1', 'X: ( W = 1 ) => ( Q = 0 )'])

Oboje wracają

[{'X': 0, 'W': 1, 'Q': 1}]

Niegolfowane Objaśnienie:

from functools import *
def knight_and_knaves(cast,rules):
    # turns 'A B C' into ['A','B','C']
    cast = cast.split()
    # gets all numbers that can fit in len(cast) bits
    bitmasks = range(2 ** len(cast))
    # for every bitmask, apply the value for a bit to the boolean value for each cast member.
    # This returns a dictionary of all possible outcomes.
    d=[dict((cast[i], n>>i & 1) for i in range(len(cast))) for n in bitmasks]
    # Split rules at colon
    rules = [s.split(":")for s in rules]
    # Turns list of rules into one python expression, joins each rule with ')and ', maybe a 'not' depending on if the hypothesis has the rule as a lie, and '('.
    # Also replaces '->' with '<1or' which is equivalent to it. Also starts with '(True' and ends with ')' to resolve missing parentheses
    transform_rules = lambda d, rules: ('(True' + ''.join([')and ' + ['not', ''][d[rule[0]]] + '(' + rule[1].replace('->','<1or') for rule in rules]) + ')')
    # Applys transform_rules on each outcome and evaluates the result, storing it into a list of lists where each element is [outcome, value]
    outcomes=[[d[i],eval(reduce(lambda x,y:x.replace(y,str(d[i][y])),d[i],transform_rules(d[i], rules)))] for i in range(len(d))]
    # Filters outcomes if value is True
    return[n[0]for n in outcomes if n[1]]

Drugie rozwiązanie wymaga również 3.5 (nie 3.4) ze względu na użycie PEP 448

Mathematica, 80 bajtów

F[c_,s_]:=Select[Thread[c->#]&/@{True,False}~Tuples~Length@c,And@@Equal@@@s/.#&]

Wyjaśnienie

Funkcja Fprzyjmuje dwa argumenty,

• c jest listą imion wszystkich postaci,
• s to lista instrukcji, z których każda zawiera dwie części - kto co mówi.

Na przykład są trzy znaki, Q, X i W.

characters={q,x,w};

I mówią:

statements=
   {{w, !((q==True)&&(x==True))   },
    {q, w==True                   },
    {x, Implies[w==True,q==False] }};

gdzie Truei Falseoznacza odpowiednio Rycerzy i Łotrów. Następnie

F[characters, statements]

da {{q->True, x->False, w->True}}, co oznacza, że ​​istnieje tylko jedno rozwiązanie, w którym Q i W są Rycerzami, podczas gdy X jest Knave. Jeśli istnieje więcej niż jedno rozwiązanie, wynik będzie wyglądał{{...},{...},...}

Algorytm jest bardzo prosty. {True,False}~Tuples~Length@cdaje wszystkie możliwe kombinacje Rycerzy i Łotrów pomiędzy postaciami. Następnie Thread[c->#]&/@zbuduj tablicę reguł na podstawie tych kombinacji. W przypadku dwóch znaków A i B tablica będzie

{{a->True, b->True },
 {a->True, b->False},
 {a->False,b->True },
 {a->False,b->False}}

Zastępując instrukcje jednym wierszem tych reguł, otrzymamy tablicę wyglądającą

{{True,True},{True,False},{False,False}}

Pierwsza kolumna tej tablicy to tożsamości mówców, a druga kolumna wskazuje, czy ich stwierdzenia są prawdziwe, czy fałszywe. Prawidłowe rozwiązanie wymaga zgodności między tożsamościami mówców a ich oświadczeniami. Powyższa tablica oznacza, że ​​ta kombinacja nie jest rozwiązaniem, ponieważ drugi mówca, rycerz, składa niepoprawne stwierdzenie.

Select[...,And@@Equal@@@s/.#&]

dokonuje podstawień i wybiera te kombinacje, które spełniają warunek.

Ruby, 128

Jest to ten sam algorytm, co wszyscy, wypróbuj wszystkie możliwe kombinacje noże i rycerzy i zobacz, które laski. Mam inny, nad którym pracuję, ale myślę, że będzie on dłuższy (choć bardziej interesujący).

Dane wejściowe instrukcji muszą być:

• & I
• | LUB
• == JEST
• ! NIE
• > IMPLIKACJE
• X: Osoba X twierdzi, że ...

Wymagam także, aby każda instrukcja i pod-instrukcja były w nawiasach. Jedynym problemem związanym z tą wersją jest to, że przechodzi ona co najwyżej 2 ^ 26 iteracji, a jeśli nie wszystkie są łotrami, co najmniej 2 ^ (26-n) iteracji ! Mówiąc z perspektywy, oznacza to, że jeśli są dwie osoby, a przynajmniej jedna nie jest łotrem, zajmie to co najmniej 16 777 216 iteracji !

Aby to ograniczyć, przesyłam następujące w 168 bajtów. Sub 26do #{o.size}wyciąć go z powrotem do 161.

->s{o=s[/.*?$/].split
i=0
eval h=o.zip(("%0#{o.size}b"%i+=1).chars).map{|k|k*?=}*?;until h&&o.all?{|t|!s[/#{t}:(.*)$/]||eval("(#{t}<1)^(#{$1.gsub(?>,'!=true||')})")}
h}

Ale jeśli zamiast tego mogę użyć tablicy osób i mapy instrukcji, np .:

c[[?A, ?B],
  {
    ?A=> "( B == 0 ) | ( A == 1)",
    ?B=> "A == 1"
  }
 ]

Potem zmniejszam do 128.

->o,s{i=0
eval h=o.zip(("%026b"%i+=1).chars).map{|k|k*?=}*?;until h&&s.all?{|t,k|eval("(#{t}<1)^(#{k.gsub(?>,'!=true||')})")}
h}