mena = open('L2names.txt').read().split()
P = len(mena)
cisla_ludi = { mena[i]:i for i in range(P) }
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
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] )
def prem(kto,kde): return P*kto + kde + 1
podmienky = []
for p in range(P): podmienky.append( [ prem(p,q) for q in range(P) ] )
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) ] )
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) ] )
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()
import subprocess
riesenie = subprocess.check_output( './glucose L2sat.txt | tail -n 1', shell=True )
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 }
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 ] )