# načítame si zoznam mien, očíslujeme si ľudí číslami 0..P-1

mena       = open('L2names.txt').read().split()
P          = len(mena)
cisla_ludi = { mena[i]:i for i in range(P) }

# načítame si mapu
# navštíviteľné pozície na mape si očíslujeme 0..N-1
# navyše si samostatne očíslujeme domy 0..P-1 a pre každý si zapamätáme jeho súradnice

mapa            = [ [ y for y in x.strip() ] for x in open('L2map.txt').readlines() ]
R               = len(mapa)
C               = len(mapa[0])
cisla_policok   = [ [ None for c in range(C) ] for r in range(R) ]
policka_domov   = []

N = 0
for r in range(R):
    for c in range(C):
        if mapa[r][c] == 'O':
            policka_domov.append( N )
        if mapa[r][c] in 'OX':
            cisla_policok[r][c] = N
            N += 1

# spočítame si najkratšie vzdialenosti pre každú dvojicu políčok (a teda každú dvojicu domov)

vzdialenosti = [ [ 0 if i==j else 987654321 for j in range(N) ] for i in range(N) ]

for r in range(R):
    for c in range(C):
        if cisla_policok[r][c] is not None:
            for dr,dc in [ (-1,0), (1,0), (0,-1), (0,1) ]:
                nr, nc = r+dr, c+dc
                if not (0 <= nr < R and 0 <= nc < C): continue
                if cisla_policok[nr][nc] is not None:
                    vzdialenosti[ cisla_policok[r][c] ][ cisla_policok[nr][nc] ] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            vzdialenosti[i][j] = min( vzdialenosti[i][j], vzdialenosti[i][k] + vzdialenosti[k][j] )

# vytvoríme SAT program popisujúci, kto kde môže bývať

# pre každého človeka a každé číslo domu budeme mať premennú "býva tento človek v tomto dome?"
# nasledujúca pomocná funkcia z čísla človeka a čísla domu spraví číslo premennej

def prem(kto,kde): return P*kto + kde + 1

podmienky = []

# 1. každý človek niekde býva

for p in range(P): podmienky.append( [ prem(p,q) for q in range(P) ] )

# 2. žiadni dvaja ľudia nebývajú tam isto

for p in range(P):
    for q in range(P):
        if p < q:
            for d in range(P):
                podmienky.append( [ -prem(p,d), -prem(q,d) ] )

# 3. ak máme dvojicu čo má bývať vo vzdialenosti d, zakážeme im ostatné dvojice domov

for line in open('L2distances.txt').readlines():
    x, y, d = line.strip().split()
    x, y, d = cisla_ludi[x], cisla_ludi[y], int(d)

    for i in range(P):
        for j in range(P):
            if vzdialenosti[ policka_domov[i] ][ policka_domov[j] ] != d:
                podmienky.append( [ -prem(x,i), -prem(y,j) ] )

# SAT program zapíšeme do súboru

f = open('L2sat.txt','w')
f.write('p cnf {} {}\n'.format( 26*26, len(podmienky) ) )
for podmienka in podmienky:
    for x in podmienka: f.write('{} '.format(x))
    f.write('0\n')
f.close()

# SAT program vyriešime externým solverom

import subprocess
riesenie = subprocess.check_output( './glucose L2sat.txt | tail -n 1', shell=True )

# z riešenia vyparsujeme, kto kde býva

premenne = [ int(x) for x in riesenie.split()[1:-1] ]
kladne_premenne = [ x-1 for x in premenne if x > 0 ]
kam_patri = { x//P : x%P for x in kladne_premenne }

# vypočítame vzdialenosti, ktoré odovzdať

for line in open('L2pairs.txt').readlines():
    x, y = line.strip().split()
    cx, cy = cisla_ludi[x], cisla_ludi[y]
    domx, domy = kam_patri[cx], kam_patri[cy]
    polickox, polickoy = policka_domov[domx], policka_domov[domy]
    print( vzdialenosti[ polickox ][ polickoy ] )