4. O žabách a hadoch vzorové riešenie

>>> 1 3 2 3
<<< 1 2
>>> 3 4 2 1
<<< 0 4
>>> 1 2 3 4
<<< 4 0

Táto úloha mala veľa rôznych spôsobov ako získať nejaký počet bodov. Ak napríklad skúšame všetky možnosti, hneď máme jeden, s trochou šťastia aj dva body. Ak však začneme využívať informácie zo vstupu, veľmi ľahko sa dostaneme na 4 body. Stačí totiž zistiť aké 4 farby potrebujeme, a postupne vyskúšať všetky ich variácie. Ak si však podobnú stratégiu skúsime ručne odohrať, zistíme, že od súpera dostávame viac informácii o riešení ako využívame a môžeme implementovať rôzne vylepšenia.

#!/usr/bin/python3
from itertools import permutations

c = []

for i in range(1, 7):
    print(i, i, i, i)
    a, b = map(int, input().split())
    for j in range(a):
        c.append(i)

for i in permutations(c):
    print(*i)
    a, b = map(int, input().split())
    if a == 4:
        break

Vzorové riešenie

Nebudeme to ďalej naťahovať, a povieme si, ako sa dopracovať ku riešeniu ktoré to zvláda na 5 tipov. Na začiatok si treba uvedomiť, že všetkých možností je len \(6^4\) teda 1296. To vôbec nie je veľa, teda ide nám najmä o hľadanie stratégie a nie ani tak o časovú zložitosť.

S každým tipom dostaneme od protihráča celkom veľa informácie. Každá odpoveď nám totiž rozdelí tých 1296 možností na tie, ktoré heslo môžu byť, a tie, ktoré heslo byť nemôžu. To, do ktorej skupiny patrí ktoré štvorčíslie, zistíme veľmi jednoducho, keď si spočítame, akú odpoveď by nám dal protihráč na náš tip, ak by dané štvorčíslie bolo heslo. Keď toto spravíme pre každú jednu možnosť, budeme mať nový zoznam prípustných možností, ktorý už bude výrazne kratší.

S takýmto pozorovaním sa už ľahko dostaneme na 8 až 10 bodov, podľa toho, ako si vyberieme ďalší tip. Ak si povieme, že vylosujeme náhodne z ostávajúcich možností, tak to niekedy vydá a niekedy nie. My by sme však chceli riešenie, ktoré funguje vždy na 5 tipov. Na to potrebujeme vybrať ten správny tip. Ak napríklad vieme, že 1122 má dve zhody, asi nebude najlepší tip 1123, ale viac nám povie napríklad 3344.

Najlepší je teda taký tip, ktorý vyradí najviac možností. Ako však taký tip nájsť, keď nepoznáme heslo? Povedzme, že po prvom tipe sme si vytvorili vyššie popísaný zoznam možných hesiel. Teraz chceme o nejakom nasledujúcom tipe zistiť, ako dobrý je. To budeme merať tak, že si pre každé možné heslo zistíme, akú odpoveď by sme dostali a pre každú možnú odpoveď (tých je 14) spočítame, koľko možných hesiel by nám ostalo, ak by sme danú odpoveď dostali. Nevieme však, akú odpoveď dostaneme, tak rátajme s najhoršou možnosťou. Teda takou, ktorá by vyradila najmenej hesiel. Keď si takéto číslo zrátame o každom možnom tipe, vieme si ľahko vybrať ten, ktorý vyradí najviac možností v najhoršom prípade. Treba si však uvedomiť, že niekedy môže byť najlepší aj tip, ktorý heslom určite nebude (ako v príklade v predošlom odseku). Aj bez tohoto pozorovania však už dostaneme 9 bodov.

Táto technika sa volá minmax, lebo najprv si pre každý tip zistíme minimum jeho prínosu a potom zoberieme maximum z týchto možností. Dá sa takmer univerzálne aplikovať na hry, kde nepoznáme ťah súpera, ale vieme nejakým spôsobom odsimulovať všetky jeho možnosti. Treba však myslieť na to, že výsledok nemusí byť optimálny, nakoľko napríklad v tejto úlohe sa vôbec nepozeráme na ťahy ktoré budú nasledovať¹.

Časová zložitosť

Časová zložitosť nás trochu potrápi, podľa toho, ako dôslední chceme byť. Označme \(f\) počet farieb a \(n\) dĺžku hesla. Povedzme pre jednoduchosť, že porovnanie dvoch tipov robíme v \(O(n^2)\)². Prefiltrovať tipy podľa odpovede, ktorú dostaneme, nám potom trvá \(O(f^nn^2)\). Ďalší krok je, že pre každý možný tip (\(O(f^n)\)) zisťujeme, pre každé možné heslo (\(O(f^n)\)), akú odpoveď by sme dostali (\(O(n^2)\)). Možných odpovedí je tiež \(n^2\), teda najlepšiu z nich tiež nájdeme v \(O(n^2)\). Výsledná časová zložitosť jedného tipu teda bude \(O(f^{2n}n^2)\). Pamäťová zložitosť je \(O(f^n)\).

Najhorší možný počet ťahov je takmer nemožné ručne odhadnúť na 5, preto sa jednoducho odvoláme na to, že skúsiť všetky skryté heslá nie je tak ťažké.

#!/usr/bin/python3
from collections import defaultdict 
from itertools import product

odpovede = [(0,0),(0,1),(0,2),(0,3),(0,4),
            (1,0),(1,1),(1,2),(1,3),
            (2,0),(2,1),(2,2),
            (3,0),
            (4,0)]

def diff(a,b):
    a=list(a)
    b=list(b)
    right = 0
    notright = 0
    for i in range(len(a)):
        if a[i] == b[i]:
            right += 1
            a[i] = -1
            b[i] = -2
    for i in range(len(a)):
        for j in range(len(a)):
            if a[i] == b[j]:
                notright += 1
                b[j] = -2
                break
    return(right, notright)


n = 4
m = 6
s = set(product(range(1, m + 1), repeat=n))
all = s.copy()
t = (1, 1, 2, 2)
used = [t]
print(*t)
while True:
    a, b = map(int, input().split())
    if a == n:
        break
    s = {i for i in s if diff(used[-1], list(i)) == (a, b)}
    besttip = []
    minmax = 12345678
    for a in all:
        if a in used:
            continue
        m = defaultdict(int)
        for pos in s:
            ans = diff(a, pos)
            m[ans] += 1

        m = max(m.values())
        if m < minmax or (m == minmax and a in s):
            minmax = m
            besttip = a
    used.append(besttip)
    print(*besttip)