Battle Dev RegionsJob - Mars 2017 : Exercice 4/5 : Prise de la Pastille

battle_dev_regionsjob_201703_prise_de_la_pastille.py

"""
Ma solution Python à l'avant dernier exercice de la Battle Dev RegionsJob - Mars 2017 [1], Prise de la Pastille.
À retrouver et tester à partir d'ici: https://www.isograd.com/FR/solutionconcours.php?contest_id=23

Le code n'est pas optimisé et provoque parfois l'erreur "Maximum execution time has been reached".
"""

#*******
#* Read input from STDIN
#* Use: echo or print to output your result to STDOUT, use the /n constant at the end of each result line.
#* Use: sys.stderr.write() to display debugging information to STDERR
#* ***/
import sys

lines = []
for line in sys.stdin:
	lines.append(line.rstrip('\n'))
	
# Pour debug    
def lprint(s): sys.stderr.write(s+'\n')
    
lprint('\n'.join(lines[1:]))

# Début soluce
def init_map(lines):
    map_ = [[c for c in l] for l in lines]
    h = len(map_)
    Ms = set()
    for x in range(h):
        for y in range(h):
            if map_[x][y] == 'C':
                C = (x, y)
            elif map_[x][y] == 'M':
                Ms.add((x, y))
            elif map_[x][y] == 'O':
                O = (x, y)
            if map_[x][y] in ['C', 'M', 'O']:
                map_[x][y] = '.'
    return map_, C, Ms, O
    
def can_move_to(map_, from_):
    h = len(map_)
    to = []
    x, y = from_
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        x2, y2 = (x-i) % h, (y-j) % h
        if map_[x2][y2] ==  '.':
            to.append((x2, y2))
    return to
    
def move_phantoms(map_, Ms):
    Ms2 = Ms.copy()
    for M in Ms:
        Ms2.update(can_move_to(map_, M))
    return Ms2

def find(map_, C, Ms, O, t=0):
    if (C in Ms) or (O in Ms):
        return 0
    elif C == O:
        return t
    else:
        Ms2 = move_phantoms(map_, Ms)
        return max(find(map_, C2, Ms2, O, t+1) for C2 in can_move_to(map_, C))

# Exécution de la solution
print(find(*init_map(lines[1:])))