'''
Script om een 'Futoshiki' puzzle op te lossen
'''

# eerst even een eenvoudige definitie van de futoshiki...

# een tekst-futoshiki wordt gegeven als een list met negen strings met negen
# karaters. intern gebruiken we matrices (lists of lists), voor de groter dan
# en kleinder dan een paar globals voor de getallen worden veel vaker matrices
# gemaakt en gekopieerd, de values hiervan zijn weer lists met de nog mogelijke
# getallen. Een stipje in een tekst-futoshiki komt dus over een met de list
# [1,2,3,4,5]

# template
futo_template = [ '. . . . .',
                  '         ',
                  '. . . . .',
                  '         ',
                  '. . . . .',
                  '         ',
                  '. . . . .',
                  '         ',
                  '. . . . .']  

# Noord Hollands dagblad 10 Oktober 2015
nhd_10_10_2015 = [ '.<. . . .',
                   '         ',
                   '. .<. . .',
                   '^        ',
                   '. .<. . .',
                   '         ',
                   '. . 2 .>.',
                   '  v     v',
                   '.<. . .<.']  

# Noord Hollands dagblad 24 Oktober 2015
nhd_24_10_2015 = [ '.<. .>. .',
                   '         ',
                   '. . . .>.', 
                   'v        ',
                   '. . .>. .', 
                   '    ^    ',
                   '.<. . . .', 
                   '        v',
                   '.<. 3 . .']  


from copy import copy, deepcopy
from itertools import product
from sys import exit
from operator import mul

# some defines
LT = 1
GT = 2   
N = 5
map_hor = {None : ' ', LT : '<', GT : '>'}
map_ver = {None : ' ', LT : '^', GT : 'v'}

# some globals
row_ltgt = [[None for _ in range(N)] for _ in range(N)]
col_ltgt = [[None for _ in range(N)] for _ in range(N)]


# Een aantal functies om de tekst futoshiki's in te kunnen lezen

def numbers_from_char(c):
    if c == '.' : return range(1, N + 1)
    if c in '123456789': return [int(c)]
    raise ValueError, 'Whoops, wrongs number character in definition'

def row_lt_gt_from_char(c):
    if c == '<': return LT
    if c == '>': return GT
    if c == ' ': return None
    raise ValueError, 'Whoops, wrongs row character in definition:  %c' % (c)
    
def col_lt_gt_from_char(c):
    if c == '^': return LT
    if c == 'v': return GT
    if c == ' ': return None
    raise ValueError, 'Whoops, wrongs col character in definition:  %c' % (c)


def from_text(t):

    global row_ltgt
    global col_ltgt

    sol  = [[None for _ in range(N)] for _ in range(N)]

    # numbers
    for row, col in product(range(N), range(N)):
        sol[row][col] = numbers_from_char(t[row * 2][col * 2])

    # row_ltgt
    for row, col in product(range(N), range(N-1)):
        row_ltgt[row][col] = row_lt_gt_from_char(t[row * 2][col * 2+ 1])

    # col_ltgt
    for row, col in product(range(N-1), range(N)):
        col_ltgt[row][col] = col_lt_gt_from_char(t[row * 2+ 1][col * 2])

    return sol

# en een print routine

def print_sol(sol, remark = None):

    global row_ltgt
    global col_ltgt

    s = ''
    s += '-' * 79 + '\n'
    if remark:
        s += remark + '\n'
        s += '-' * 79 + '\n'
    for row in range(N):
        s += '    '
        for col in range(N):
            tmp = ''
            if len(sol[row][col]):
                for item in sol[row][col]:
                    tmp += str(item)
            s += (tmp + '     ')[:5]
            s += ' ' + map_hor[row_ltgt[row][col]] + ' ' 
        s += '\n'
        s += '    '
        for col in range(N):
            s += map_ver[col_ltgt[row][col]] + '       '
        s += '\n'
    s += '-' * 79 + '\n'
    print s


# een aantal wegstreep functies

def remove(l, val):
    if val in l:
        l.remove(val)

def remove_val_and_above(l, val):
    for i in range(val, N+1):
        if i >= val and i in l:
            l.remove(i)

def strike_through_less_than(lhs, rhs):
    remove_val_and_above(lhs, max(rhs))

def inplace_strike_through_singles(sol):
    '''Enkelvoudigen in zelfde kolom, rij wegstrepen'''

    for row, col in product(range(N), range(N)):
        if len(sol[row][col]) == 1:
            val = sol[row][col][0]
            for row2 in range(N):
                if row != row2:
                    remove(sol[row2][col], val)
            for col2 in range(N):
                if col != col2:
                    remove(sol[row][col2], val)

def inplace_strike_through_ltgt_row(sol):
    '''wegstrepen wat kan bij horizontale > en < tekens'''

    for row, col in product(range(N), range(N-1)):
        if row_ltgt[row][col] == LT:
            strike_through_less_than(sol[row][col], sol[row][col + 1])
        if row_ltgt[row][col] == GT:
            strike_through_less_than(sol[row][col + 1], sol[row][col])

def inplace_strike_through_ltgt_col(sol):
    '''wegstrepen wat kan bij verticale > en < tekens'''

    for row, col in product(range(N-1), range(N)):
        if col_ltgt[row][col] == LT:
            strike_through_less_than(sol[row][col], sol[row + 1][col])
        if col_ltgt[row][col] == GT:
            strike_through_less_than(sol[row + 1][col], sol[row][col])


# twee essentiele functies

def is_still_possible(sol):
    '''
    Check of deze oplossing uberhaupt nog mogelijk is...
    '''

    # op z'n minst nog 1 mogelijkheid voor elke positie?
    for row, col in product(range(N), range(N)):
        if len(sol[row][col]) < 1:
            return False

    # alle getallen nog aanwezig in row en col?
    for row in range(N):
        s = set()
        for col in range(N):
            for val in sol[row][col]:
                s.add(val)
        if len(s) != N:
            return False
        
    for col in range(N):
        s = set()
        for row in range(N):
            for val in sol[row][col]:
                s.add(val)
        if len(s) != N:
            return False

    # geen doublures in eenlingen
    for row in range(N):
        s = set()
        for col in range(N):
            if len(sol[row][col]) == 1:
                val = sol[row][col][0]
                if val in s:
                    return False
                s.add(val)
        
    for col in range(N):
        s = set()
        for row in range(N):
            if len(sol[row][col]) == 1:
                val = sol[row][col][0]
                if val in s:
                    return False
                s.add(val)

    # voldoen we nog aan de < en > tekens?
    for row, col in product(range(N), range(N)):
        if row_ltgt[row][col] == LT:
            if min(sol[row][col]) > max(sol[row][col + 1]):
                return False
        if row_ltgt[row][col] == GT:
            if min(sol[row][col + 1]) > max(sol[row][col]):
                return False

    for row, col in product(range(N), range(N)):
        if col_ltgt[row][col] == LT:
            if min(sol[row][col]) > max(sol[row + 1][col]):
                return False
        if col_ltgt[row][col] == GT:
            if min(sol[row + 1][col]) > max(sol[row][col]):
                return False

    # oke, het lijkt nog mogelijk
    return True

def is_solved(sol):

    # hebben we op elke positie 1 mogelijkheid?
    for row, col in product(range(N), range(N)):
        if len(sol[row][col]) != 1:
            return False

    # hebben we op elke row, col alle cijfers
    for row in range(N):
        s = set()
        for col in range(N):
            s.add(sol[row][col][0])
        if len(s) != N:
            return False
        
    for col in range(N):
        s = set()
        for row in range(N):
            s.add(sol[row][col][0])
        if len(s) != N:
            return False

    # voldoen we aan de < en > tekens?
    for row, col in product(range(N), range(N-1)):
        if row_ltgt[row][col] == LT:
            if sol[row][col][0] > sol[row][col + 1][0]:
                return False
        if row_ltgt[row][col] == GT:
            if sol[row][col + 1][0] > sol[row][col][0]:
                return False

    for row, col in product(range(N-1), range(N)):
        if col_ltgt[row][col] == LT:
            if sol[row][col][0] > sol[row + 1][col][0]:
                return False
        if col_ltgt[row][col] == GT:
            if sol[row + 1][col][0] > sol[row][col][0]:
                return False
    
    # Yes, dan is de futoshiki opgelost!
    return True


def strike_through(sol):
    '''
    Streept zo veel mogelijk weg

    Deze functie wil alleen maar oplossingen die nog mogelijk zijn en
    geeft ook alleen maar oplossingen terug die nog mogelijk zijn.
    '''
    if not is_still_possible(sol):
        raise ValueError, 'strike_through wil alleen nog mogelijke sol\'s'

    new_sol = deepcopy(sol)

    # alle 3 inplace_strike_through functies maar eens proberen
    for fun in [ inplace_strike_through_singles,
                  inplace_strike_through_ltgt_row,
                  inplace_strike_through_ltgt_col  ] :

        try_sol = deepcopy(new_sol)
        fun(try_sol)
        if is_still_possible(try_sol):
            new_sol = deepcopy(try_sol)

    # als er iets verandert is gaan we door, recurse!
    if new_sol == sol:
        return sol
    else:
        return strike_through(new_sol)

def best_guesses(sol):
    '''
    Zoekt het vakje met de minste mogelijkheden en geeft de mogelijke
    oplosingen door met dat vakje ingevuld met een enkelvoudige.
    '''
    n_map = {} 
    for row, col in product(range(N), repeat=2):
        n = len(sol[row][col])
        if n > 1:
            n_map[n] = (row, col)

    if len(n_map) >= 1:
        keys = n_map.keys()
        min_key = min(keys)
        best_row, best_col = n_map[min_key]
        for val in sol[best_row][best_col]:
            try_sol = deepcopy(sol)
            try_sol[best_row][best_col] = [val]
            if is_still_possible(try_sol):
                yield try_sol


def number_of_possibilities(sol):
    # voor de gein een beetje abstract en/of cryptisch
    return reduce(mul, 
                    [len(sol[row][col]) for 
                        row, col in product(range(N), repeat=2)], 1)


def solve(sol):

    sol = strike_through(sol)

    if is_solved(sol):
        print_sol(sol, 'Jaah gelukt...')
        exit(0)

    # nog niet geslaagd, we gaan door
    for guess in best_guesses(sol):
        solve(guess)


# het echte werk!
def main():
    sol = from_text(nhd_24_10_2015)
    print_sol(sol, 'Start futoshiki')
    print 'Aantal mogelijkheden:', number_of_possibilities(sol)
    solve(sol)

if __name__ == '__main__':
    main()