#!/usr/bin/python

################################################################################
# checker.py
#
# Shaden Smith - July 2011 (updated September 2012)
#
# Accepts a solution to the weighted sequence problem through STDIN and verifies
# solution.
################################################################################

import sys
import re # regex engine
import itertools

from Sequence import Sequence, Node

# Exit codes
SAT = 10             # input
UNSAT = 20            # input
EXIT_SUCCESS = 0
EXIT_FAILURE = 1
EXIT_WARN = 1

class Checker:
    
    def __init__(self):
        # intialize sequence
        self.seq = Sequence()

    def parseInstance(self):
        # filename is ARGV[2]        
        instance_file = sys.argv[2]
        f = open(instance_file)

        # Grab instance information from file
        for line in f:
            for elem in line.split():
                # check for leaf definition
                m = re.search("leafWeightCardinality\((\d+),(\d+),(\d+)\)", elem)
                if m:
                    self.seq.leaves[int(m.group(1))] = Node(int(m.group(2)), int(m.group(3)))

                # check for max_total_weight
                m = re.search("max_total_weight\((\d+)\)", elem)
                if m:
                    self.seq.maxCost = int(m.group(1))

        if self.seq.maxCost == -1:
            sys.exit(EXIT_WARN)
    
    def parseSolution(self):
        """ Read solution from STDIN and store data in self.seq"""
        # Work through each word of input given to us
        for line in sys.stdin.readlines():
            for elem in line.split():
                print(line)

                # check for color
                m = re.search("posColor\((\d+),(\w+)\)", elem)
                if m:
                    self.seq.posColor[int(m.group(1))] = m.group(2)

                # check for leafPos
                # leafPos[myPos] = myLeaf
                # NOTE: This is reversed from encodings. Since we want to find
                # a leaf given a position, lookup is easier this way.
                m = re.search("leafPos\((\d+),(\d+)\)", elem)
                if m:
                    self.seq.leafPos[int(m.group(2))] = int(m.group(1))

    def checkSat(self):
        """ After solution is parsed, check solution for validity."""
        # Compute the individual cost of each leaf first
        for i in range(1, len(self.seq.leafPos)):
            currLeaf = self.seq.leaves[self.seq.leafPos[i]]

            if self.seq.posColor[i] == "green":
                self.seq.leafCost[i] = currLeaf.c + currLeaf.w
    
            elif self.seq.posColor[i] == "red":
                # if it's the first colored position, grab weight of left leaf
                if i == 1:
                    self.seq.leafCost[i] = currLeaf.w + \
                        self.seq.leaves[self.seq.leafPos[0]].w
                else:
                    # otherwise just add weight of leaf plus cost of right
                    self.seq.leafCost[i] = currLeaf.w + self.seq.leafCost[i-1]
        
            elif self.seq.posColor[i] == "blue":
                if i == 1:
                    self.seq.leafCost[i] = currLeaf.c + \
                        self.seq.leaves[self.seq.leafPos[0]].w
                else:
                    self.seq.leafCost[i] = currLeaf.c + self.seq.leafCost[i-1]
            
        # now sum leafCost to find total cost of sequence
        self.seq.cost = sum(self.seq.leafCost.values())

        if len(self.seq.leafPos) > 0 and self.seq.cost <= self.seq.maxCost:
            sys.exit(EXIT_SUCCESS)
        else:
            sys.exit(EXIT_FAILURE)

    # Brute-force check for a solution to the problem. This runs in O(n!)
    # based on the number of leaves.
    def checkUnsat(self):
        totalCost = [0] * len(self.seq.leaves)
        minVal = [0] * len(self.seq.leaves)

        # compute minVal for each leaf
        for i in range(len(self.seq.leaves)):
            l = self.seq.leaves[i+1]
            minVal[i] = min(l.w, l.c)

        # iterate over all permutations of leaves
        for currSeq in itertools.permutations(range(len(self.seq.leaves))):

            # Assign optimal coloring and compute total cost

            # cost[0] = leaf[0].w
            totalCost[0] = self.seq.leaves[currSeq[0]+1].w

            # Start coloring at the second node
            for i in range(1, len(currSeq)):
                l = self.seq.leaves[currSeq[i]+1] # leaves are named 1..n but indexed 0..n-1
                totalCost[i] = min([l.w + l.c, \
                    minVal[currSeq[i]] + totalCost[i-1]])

            # Compute cost of sequence
            if sum(totalCost[1:]) <= self.seq.maxCost:
                sys.exit(EXIT_FAILURE)

        sys.exit(EXIT_SUCCESS)

if __name__ == "__main__":
    print(" running ")
    main = Checker()
    main.parseInstance()
    
    # check return code given
    exit_code = int(sys.argv[1])
    if exit_code == SAT:
        main.parseSolution()
        main.checkSat()
    elif exit_code == UNSAT:
        main.checkUnsat()       

