#!/usr/bin/python3
#
# Try to solve puzzles from https://logic.puzzlebaron.com/
#
# See if we can parse the text, then establish relationships
# amongs the selections to derive a solution.
#

import sys
import re
import configparser
import pprint

IGNORE_WORDS = { 'the', 'a', }

# We need 28 labels for columns/rows.
LABELS = ''.join(chr(i) for i in range(ord('A'), ord('Z')+1)) + 'ab'


def main(puz):
    p = configparser.ConfigParser(
          converters={ 'lower': cvt_lower,
                       'choices': cvt_choices,
                       }
          )
    p.read(puz)

    g = p['general']
    clues = extract_clues(g.getlower('clues'))
    print('CLUES:', '\n    '.join(clues))

    axes = [ Axis(p, c) for c in g.getchoices('axes') ]

    cfg = Config(axes, g.getchoices('subject'))
    #print('SNAMES:', cfg.snames)

    # Parse the clues.
    pc = [ ]
    for clue in clues:
        parsed = parse_clue(clue, cfg)
        print('--[human]>', [v.output() for v in parsed])
        pc.append(parsed)

    while True:
        for clue in pc:
            used = cfg.apply_clue(clue)
            if used:
                # The clue was used, and cfg.solution was modified.
                # Restart, to try all the clues again.
                break
        else:
            # No clues were used. We're done. Print out the solution
            # (or, at least what we have so far).
            cfg.print_solution()
            break  # from the while loop


def cvt_lower(s):
    return s.lower()
def cvt_choices(s):
    return [ c.strip() for c in s.lower().split(',') ]


def extract_clues(t):
    clues = [ ]
    for l in t.strip().splitlines():
        c = l.rstrip('.')
        c = RE_PUNCT.sub('', c)
        clues.append(c)
    return clues
# Remove leading clue numbers.
RE_CLUE = re.compile(r'[0-9]+\.\s*|[,;:]')
# Remove punctuation.
RE_PUNCT = re.compile(r'[,;:!]')


def parse_clue(clue, cfg):
    words = list(clue.split())
    print('PARSE:', words)
    while True:
        for i in range(len(words)):
            w = words[i]
            if type(w) != str:  # avoid isinstance() (skip str subclasses)
                continue

            # Ignore some basic words:
            if w in IGNORE_WORDS:
                del words[i]
                break  # restart the word-parsing loop

            # Is this an easy map to a Choice?
            choice = cfg.find_choice(w)
            if choice:
                words[i] = choice
                continue  # no change in length of words[]

            match = cfg.leads.get(w)
            if match:
                # WORD_COUNT, CHOICE(AXIS, VALUE)
                wc, v = match
                value = ' '.join(words[i:i+wc])
                #print('LEAD: %r %r %r' % (wc, v, value))
                if value == v.value:
                    words[i:i+wc] = [ v ]
                    break  # restart the word-parsing loop

            op = OPERATORS.get(w)
            if op:
                words[i] = op(w)
                continue  # no change in length of words[]

            ### more algorithms to map this word to something
            ### skip it for now
            words[i] = Skip(w)

        else:
            # No strings were found. Exit the WHILE.
            break

    print('--[1]>')
    pprint.pprint(words)
    print('--[1]')

    # Apply the PATTERNS
    apply_patterns(words)
    print('--[2]>', words)
    return words


def apply_patterns(words):
    "Modify WORDS by applying PATTERNS replacements."

    while True:
        # Try substitutions IN ORDER, according to PATTERNS
        for classes, func in PATTERNS:
            if replace_with(words, classes, func):
                # A replacement occurred. Restart the scanning loop.
                break
        else:
            # No replacements were performed. We're done.
            return


def replace_with(words, classes, func):
    """Try and replace multi-values with something new.

    Returns False, if no replacement occurred.
    Returns True, if WORDS was modified by a replacement.
    """

    count = len(classes)
    #print('CLASSES:', ','.join(c.__name__ for c in classes))

    for i in range(len(words) - count + 1):
        # Do the words match this sequence of classes?

        #print('WORDS:', ','.join(w.__class__.__name__ for w in words[i:]))

        for j in range(count):
            if not isinstance(words[i+j], classes[j]):
                # Nope. Break, to try the next subrange.
                break
        else:
            # All the words/classes matched at this position.
            new = func(*words[i:i+count])
            #print('...TESTED:', new)
            if new is not None:
                print('REPLACING:', words[i:i+count], '->', new)
                words[i:i+count] = new
                print('-->', words)
                return True
            # Didn't reduce. Continue for the next subrange.

    # No matches found.
    return False


def reduce_dup(*args):
    "[Axis(a), optional-Of, Choice(a,..)] should be Choice(a,..)."
    if args[0].name == args[-1].axis.name:
        return [ args[-1] ]
    return None  # no change

def reduce_remove(v1):
    "Unconditionally remove this word."
    return [ ]

def reduce_exclusive2(v1, v2, v3, v4, v5):
    "Params: CHOICE [is] EITHER CHOICE OR CHOICE."
    return [ Exclusive2(v1, v3, v5) ]

def reduce_exclusive4(v1, v2, v3, v4, v5, v6, v7):
    "Params: OF CHOICE [and] CHOICE [,] ONE [is] CHOICE [and] OTHER [is] CHOICE."
    return [ Exclusive4(v2, v3, v5, v7) ]

def reduce_unit(v1, v2):
    "Fold a unit into its value/choice."
    if v2 in v1.axis.units:
        return [ v1 ]
    return None

def reduce_relative(v1, v2, v3=None):
    """Params: CHOICE {RELATIVE} UNIT.

    Example: 2 more inches
    """
    if not v1.axis.ordered or not isinstance(v1.value, int):
        return None
    v2.value = int(v1.value)
    v2.unit = v3  # may be None
    v2.axis = v1.axis
    return [ v2 ]

def reduce_relative2(v1, v2, v3, v4, v5):
    """Params: SKIP AXIS {RELATIVE} THAN CHOICE.

    Example: 1 inch more than Sharon.

    Note: AXIS maybe different from CHOICE.axis. The above example, it means
      that the "inches" AXIS is 1 more than whatever "Sharon" will solve to.
    """
    if not v2.ordered:
        return None
    try:
        value = int(v1)
    except ValueError:
        # It didn't convert, so this pattern does not match.
        return None
    v3.value = value
    #v3.unit = v2.axis.unit
    v3.axis = v2
    return [ v3, v4, v5 ]  # RELATIVE doesn't incorporate subject. Keep it.

def reduce_choice(v1, v2, v3):
    "Params: CHOICE OF SUBJECT."
    return [ v1 ]

def reduce_negative(v1, v2, v3, v4):
    "Params: NEITHER CHOICE NOR CHOICE."
    return [ NegativeAlternate(v2, v4) ]


class Config(object):
    def __init__(self, axes, snames):
        self.axes = axes
        self.snames = set(Subject(n) for n in snames)

        self.leads = { }
        self.units = set()

        for axis in self.axes:
            # If any of the choices are multi-word, then we'll use this set of
            # "leaders" to look for them.
            if issubclass(axis.t, str):
                for c in axis.choices:
                    s = c.split()
                    if len(s) > 1:
                        self.leads[s[0]] = (len(s), Choice(axis, c))

            self.units.update(axis.units)
        #print('UNITS:', self.units)
        #print('LEADS:', self.leads)

        # All axes should have the same count of choices.
        count = len(axes[0].choices)
        for axis in axes:
            assert len(axis.choices) == count
        self.index = dict((axes[i], i) for i in range(len(axes)))
        self.n2a = dict((a.name, a) for a in self.axes)

        # Make sure to construct a new list on each iter, so they
        # don't multiple-reference a solution.
        self.solutions = dict( ((axes[a1].name, c1, axes[a2].name, c2), None)
                               for a1 in range(len(axes))
                               for a2 in range(a1+1, len(axes))
                               for c1 in axes[a1].choices
                               for c2 in axes[a2].choices
                               )
        print('SOLUTIONS:', len(self.solutions))
        #pprint.pprint(self.solutions)
        #sys.exit(0)

    def find_choice(self, word):
        for axis in self.axes:
            try:
                #print('CVT:', axis.t, word)
                cvt = axis.t(word)
            except ValueError:
                # The value did not convert.
                pass
            else:
                #print('LOOK', axis.name, cvt)
                # Look for the converted value.
                value = self._maybe_from(axis, cvt)
                if value:
                    return Choice(axis, cvt)
            if word in axis.alts:
                return axis
            if word in axis.units:
                return Unit(word)
            if word.startswith('$'):
                amount = Dollar(word[1:])
                value = self._maybe_from(axis, amount, True)
                if value:
                    return Choice(axis, value)
                continue

            match = RE_POSSESSIVE.match(word)
            if match:
                name = Name(match.group(1))
                value = self._maybe_from(axis, name, True)
                if value:
                    return Choice(axis, value)
                continue

            ### more checks

        find = next((s for s in self.snames if s == word), None)
        if find:
            return find

        # No easy match found.
        return None

    def _maybe_from(self, axis, value, strict_type=False):
        #print('MAYBE:', cat, value, strict_type)

        # All values in an axis have a specific type. If VALUE cannot
        # match the type, then just bail.
        if strict_type and type(value) != type(axis.choices[0]):
            return None

        # See if we can find a match.
        return next((v for v in axis.choices if v == value), None)

    def mark(self, c1, c2, how):
        # All solutions keys use the ordered axes.
        i1 = self.index[c1.axis]
        i2 = self.index[c2.axis]
        #print('ORDERING:', c1.axis.name, i1, c2.axis.name, i2)
        if i1 > i2:
            #print('--> swapping')
            c2, c1 = c1, c2

        a1n = c1.axis.name
        v1 = c1.value
        a2n = c2.axis.name
        v2 = c2.value
        key = (a1n, v1, a2n, v2)

        # Mark the location.
        self._simple_mark(key, how)

    def eliminate(self):
        "Use process of elimination to mark solutions."

        print('ELIMINATE:')
        while True:
            prior = self.solutions.copy()

            # Find each "found" solution (aka True), and eliminate others
            # within that axis-pair. Then reflect negatives across axes.
            for key, answer in self.solutions.items():
                if answer is not True:
                    continue
                # KEY is (axis1-name, value1, axis2-name, value2)
                a1n, v1, a2n, v2 = key

                print('True: %s[%s] / %s[%s]' % key)

                a1 = self.n2a[a1n]
                a2 = self.n2a[a2n]

                # Names to axes, to indexes.
                i1 = self.index[a1]
                i2 = self.index[a2]
                assert i1 < i2

                # For each location in this (axis, axis) grid for these choices,
                # mark them negatively.
                for v in a1.choices:
                    if v != v1:
                        self._simple_mark((a1n, v, a2n, v2), False)
                for v in a2.choices:
                    if v != v2:
                        self._simple_mark((a1n, v1, a2n, v), False)

                # Find negatives on other axes, and reflect them.
                # Basically: if A1:V1/A2:V2 is True, and A1:V1/A3:V3 is
                # False, then mark A2:V2/A3:V3 as False.
                # "John is 5. John is not Blond. Thus, 5 is not Blond."
                for i in range(len(self.axes)):
                    ra = self.axes[i]  # Reflect axis
                    if i < i1:
                        print('BOX/1:', ra.name, '/', a1n)
                        print('BOX/1:', ra.name, '/', a2n)
                        for v in ra.choices:
                            k = (ra.name, v, a1n, v1)
                            if self.solutions[k] is False:
                                rk = (ra.name, v, a2n, v2)
                                self._simple_mark(rk, False)
                            k = (ra.name, v, a2n, v2)
                            if self.solutions[k] is False:
                                rk = (ra.name, v, a1n, v1)
                                self._simple_mark(rk, False)
                    elif i > i1 and i < i2:
                        print('BOX/2:', a1n, '/', ra.name)
                        print('BOX/2:', ra.name, '/', a2n)
                        for v in ra.choices:
                            k = (a1n, v1, ra.name, v)
                            if self.solutions[k] is False:
                                rk = (ra.name, v, a2n, v2)
                                self._simple_mark(rk, False)
                            k = (ra.name, v, a2n, v2)
                            if self.solutions[k] is False:
                                rk = (a1n, v1, ra.name, v)
                                self._simple_mark(rk, False)
                    elif i > i2:
                        print('BOX/3:', a1n, '/', ra.name)
                        print('BOX/3:', a2n, '/', ra.name)
                        for v in ra.choices:
                            k = (a1n, v1, ra.name, v)
                            if self.solutions[k] is False:
                                rk = (a2n, v2, ra.name, v)
                                self._simple_mark(rk, False)
                            k = (a2n, v2, ra.name, v)
                            if self.solutions[k] is False:
                                rk = (a1n, v1, ra.name, v)
                                self._simple_mark(rk, False)

                # Done, for this particular found-solution. Keep looking.
                #end:for

            # Visit each axis-pair, and look for TBD solutions where the
            # rest of the row/column have been marked negative. We can
            # then mark the remaining solution as True, via elimination.

            # Marker for the VARIABLE in row/column. For scanning the
            # solutions, we'll reduce them to a new table with two
            # types of keys:
            #   (A1name, VARIABLE, A2name, Value2)
            #   (A1name, Value1, A2name, VARIABLE)
            # these represent a row/col and what was found.
            VARIABLE = tuple('*')

            # Modified key, per above, mapping to:
            #   True: this row/col has been solved
            #   False: this row/col cannot be solved (too many TBD)
            #   None/missing: no information yet
            #   <value>: this value is *possibly* a solution

            # Note: if we find that a row/col has been solved (that is: we
            # saw a True) *and* we discover a TBD in the solutions, then
            # throw an assert. At this point, such TBDs should be resolved.
            found = { }
            for key, what in self.solutions.items():
                a1n, v1, a2n, v2 = key
                if what:
                    found[(a1n, VARIABLE, a2n, v2)] = True
                    found[(a1n, v1, a2n, VARIABLE)] = True
                elif what is None:
                    k = (a1n, VARIABLE, a2n, v2)
                    v = found.get(k)
                    assert v is not True  # we're broken
                    if v is None:
                        # v1n may be a solution, through elimination
                        found[k] = v1
                    elif v is not False:
                        # A prior thought on solution. Nopes.
                        found[k] = False

                    # Test other direction.
                    k = (a1n, v1, a2n, VARIABLE)
                    v = found.get(k)
                    assert v is not True  # we're broken
                    if v is None:
                        # v1n may be a solution, through elimination
                        found[k] = v2
                    elif v is not False:
                        # A prior thought on solution. Nopes.
                        found[k] = False

            #print('FOUND:')
            #pprint.pprint(found)
            for k, v in found.items():
                if v in (True, False, None):
                    continue
                print('FOUND ELIMINATION:', k, v)
                if k[1] is VARIABLE:
                    ek = (k[0], v, k[2], k[3])
                else:
                    assert k[3] is VARIABLE
                    ek = (k[0], k[1], k[2], v)
                self._simple_mark(ek, True)

            # If no changes were made, then exit.
            if self.solutions == prior:
                print('--> done')
                return
            print('--> CHANGES made')

            # Loop to look for more changes.
            #end:while

    def _simple_mark(self, key, how):
        old = self.solutions[key]
        if old != how:
            assert old is None  # better be TBD
            self.solutions[key] = how

    def _choice_to_index(self, c):
        axis = self.axes[self.index[c.axis.name]]
        return axis.index[c.value]

    def apply_clue(self, clue):

        prior = self.solutions.copy()

        ### likely: fold these solution mechanisms into classes, not here

        if len(clue) == 2:
            # CHOICE1 goes with CHOICE2
            if isinstance(clue[0], Choice) and isinstance(clue[1], Choice):
                self.mark(clue[0], clue[1], True)

        elif len(clue) == 3:
            if isinstance(clue[0], Choice) and isinstance(clue[2], Choice):
                if isinstance(clue[1], More):
                    a1 = clue[0].axis
                    v1 = clue[1].value
                    a2 = clue[1].axis
                    a3 = clue[2].axis
                    v3 = clue[2].value

                    # Choice1 is compared against C2, thus they cannot
                    # be the same.
                    self.mark(clue[0], clue[2], False)

                    # Discover which choices are possible.
                    possible = clue[1].possible(clue[2].axis, clue[2].value)
                    print('POSSIBLE<More>:', possible)

                    # Walk through the choices, marking them False if they
                    # are not possible.
                    

                elif isinstance(clue[1], Less):
                    # Choice1 is compared against C2, thus they cannot
                    # be the same.
                    self.mark(clue[0], clue[2], False)

                    # Discover which choices are possible.
                    possible = clue[1].possible(clue[2].axis, clue[2].value)
                    print('POSSIBLE<Less>:', possible)

        # Apply some various elimination rules.
        self.eliminate()

        # Has the solution set changed?
        return self.solutions != prior

    def print_solution(self):
        v = self.solutions.values()
        print('SOLUTION: len:', len(v))
        print('--> True: ', len([x for x in v if x]))
        print('--> False:', len([x for x in v if x is False]))
        print('--> None: ', len([x for x in v if x is None]))

        acount = len(self.axes)
        count = len(self.axes[0].choices)  # all axes have same count

        ### print matrix
        legend = [ ]
        A = ord('A')
        for i in range(acount):
            for j in range(count):
                label = chr(A + i*count + j)
                legend.append((label, self.axes[i].choices[j]))

        # Print axis/axis in same ordering as the website:
        #   - last axis, across for each other axis
        #   - next-to-last axis, across for some
        #   - prior axis, etc
        #   etc
        order = [ (acount - 1, range(acount - 1)) ] \
                + [ (i, range(i)) for i in range(acount - 2, 0, -1) ]
        #print('ORDER:', order)

        print(' ',
              ''.join('|' + ''.join(LABELS[i*count:(i+1)*count] + '|' for i in range(acount - 1))))
        for a1, a2r in order:
            for c1 in range(count):
                v1 = self.axes[a1].choices[c1]
                label = chr(A + a1*count + c1)
                row = [ label, ' ' ]
                for a2 in a2r:
                    #print('SQUARE:', self.axes[a1].name, self.axes[a2].name)
                    row.append('|')
                    for v2 in self.axes[a2].choices:
                        if a1 <= a2:
                            key = (self.axes[a1].name,
                                   v1,
                                   self.axes[a2].name,
                                   v2)
                        else:
                            key = (self.axes[a2].name,
                                   v2,
                                   self.axes[a1].name,
                                   v1)
                        #print('KEY:', key)
                        solved = self.solutions[key]
                        row.append(SOLVE_MAP[solved])
                row.append('|')
                print(''.join(row))

        print('Legend:\n', *['%s: %s\n' % (l, v) for l, v in legend])

SOLVE_MAP = { None: ' ', True: 'X', False: '.', }
RE_POSSESSIVE = re.compile("(.*)'s?$")


class Axis(object):
    "An axis of the puzzle's choice groups."

    def __init__(self, parser, name):
        self.name = name

        spec = parser[name]
        self.t, self.ordered = TYPEMAP[spec.get('type', fallback='str')]
        self.choices = [ self.t(c) for c in spec.getchoices('choices') ]
        self.alts = set(spec.getchoices('alts') or ())
        #print('ALTS:', name, self.alts)
        #print('AXIS:', name, self.t, self.choices, self.ordered, self.alts)
        self.units = set(spec.getchoices('unit') or ())
        #print('UNIT:', self.units)

        self.index = dict((self.choices[i], i) for i in range(len(self.choices)))

    def __repr__(self):
        return 'Axis("%s")' % (self.name,)

    def output(self):
        return self.name


class Choice(object):
    def __init__(self, axis, value):
        self.axis = axis
        self.value = value

    def __repr__(self):
        return 'Choice(%r, %r)' % (self.axis, self.value)

    def output(self):
        if hasattr(self.value, 'output'):
            return self.value.output()
        return self.value


class _named_str(str):
    def __repr__(self):
        ### doesn't really work if quotes are in SELF. meh.
        return '%s("%s")' % (self.__class__.__name__, self,)
    def output(self):
        return str(self)
class Subject(_named_str): pass
class Name(_named_str): pass
class Skip(_named_str): pass
class Unit(_named_str): pass

class _operator(_named_str): pass
class Either(_operator): pass
class Or(_operator): pass
class And(_operator): pass
class Of(_operator): pass
class One(_operator): pass
class Than(_operator): pass
class Neither(_operator): pass
class Nor(_operator): pass
class Other(_operator): pass

class _relative(_operator):
    # fallback values, attached to class
    value = None
    unit = None
    axis = None
    def __repr__(self):
        return '%s(%s, "%s", %s)' % (self.__class__.__name__, self.value, self.unit, self.axis)
class More(_relative):
    alts = 'larger', 'older',

    def possible(self, axis, referent):
        "Find choices on AXIS that are MORE than REFERENT."
        assert self.axis.ordered  ### move to initializer?
        assert axis.ordered
        return [ v for v in axis.choices if v > referent ]

class Less(_relative):
    alts = 'smaller', 'younger',

    def possible(self, axis, referent):
        "Find choices on AXIS that are LESS than REFERENT."
        assert self.axis.ordered  ### move to initializer?
        assert axis.ordered
        return [ v for v in axis.choices if v < referent ]

class Dollar(int):
    def __repr__(self):
        return 'Dollar(%d)' % (self,)
    def output(self):
        return int(self)

class Exclusive2(object):
    def __init__(self, c, r1, r2):
        self.c = c
        self.r1 = r1
        self.r2 = r2
    def __repr__(self):
        return 'Exclusive2(%r, %r, %r)' % (self.c, self.r1, self.r2)
    def output(self):
        return '%s one of (%s, %s)' % (self.c, self.r1, self.r2)

class Exclusive4(object):
    def __init__(self, c1, c2, r1, r2):
        self.c1 = c1
        self.c2 = c2
        self.r1 = r1
        self.r2 = r2
    def __repr__(self):
        return 'Exclusive4(%r, %r, %r, %r)' % (self.c1, self.c2, self.r1, self.r2)
    def output(self):
        return 'of %s and %s, one is %s and the other is %s' % (self.c1, self.c2, self.r1, self.r2)

class NegativeAlternate(object):
    def __init__(self, a1, a2):
        self.a1 = a1
        self.a2 = a2
    def __repr__(self):
        return 'NegativeAlternate(%r, %r)' % (self.a1, self.a2)
    def output(self):
        return 'neither %s nor %s' % (self.a1, self.a2)


OPERATORS = dict(
    (c.__name__.lower(), c) for c in globals().values()
    if isinstance(c, type) and issubclass(c, _operator)
    )
for _c in tuple(OPERATORS.values()):
    OPERATORS.update((a, _c) for a in getattr(_c, 'alts', ()))
del _c
#print('OPERATORS:', OPERATORS)

# This is (CLASSES, REDUCE_FUNC). Order is important.
PATTERNS = [
    # Match against stuff before removal
    ((Choice, Of, Subject), reduce_choice),

    # We may have parsed a value as a Choice. Maybe fix
    # Might need to convert a choice into a plain integer
    ((Choice, _relative, Unit), reduce_relative),
    ((Choice, _relative), reduce_relative),

    # Or convert an unrecognized string into an integer
    ((Skip, Axis, _relative, Than, Choice), reduce_relative2),
    #Skip("1"), Axis("sizes"), Larger(None, "None", None), Than("than"), Choice(Axis("prices"), Dollar(140)), Subject("pair")]

    # Other patterns
    ((Neither, Choice, Nor, Choice), reduce_negative),
    ((Choice, Unit), reduce_unit),
    ((Axis, Of, Choice), reduce_dup),
    ((Axis, Choice), reduce_dup),
    ((Choice, Either, Choice, Or, Choice), reduce_exclusive2),
    ((Of, Choice, Choice, One, Choice, Other, Choice), reduce_exclusive4),

    # Trim these out, to simplify matching.
    ((Skip,), reduce_remove),
    ((Subject,), reduce_remove),

    # Leave some unused operators for end-processing.
    ((And,), reduce_remove),
    ((Than,), reduce_remove),
    ]


# Allowed type names in the config, and if they are ordered.
TYPEMAP = {
    'int':    (int,    True),
    'float':  (float,  True),
    'dollar': (Dollar, True),
    'str':    (str,    False),
    'name':   (Name,   False),
    }


if __name__ == '__main__':
    if len(sys.argv) != 2:
        print('USAGE: logic.py PUZZLE_FILE')
        sys.exit(1)
    main(sys.argv[1])