Google Code Jam 2013 - Problem D

Treasure.py

import collections

# set to False if any of the chest contains no keys at all
could_check_deadlock = False

def treasure():
    """
        used to solve google code jam 2013 - Problem D
    """
    in_f = open('D-small-attempt4.in', 'r')
    out_f = open('D-small-attempt4_output.txt', 'w')
    num_of_case = int(in_f.readline().rstrip('\n'))
    # print "num of cases:{}".format(num_of_case)
    for i in range(1, num_of_case+1):
        solve_case(in_f, out_f, i)
        
def solve_case(in_f, out_f, case_index):
    """
    solve each case
    """
    # get basic case info
    print "start handling case #{}".format(case_index)
    basic_info = in_f.readline().rstrip('\n').split(" ")
    num_of_starting_key = int(basic_info[0])
    num_of_chest = int(basic_info[1])
    print (num_of_starting_key, num_of_chest)
    starting_key_list = in_f.readline().rstrip('\n').split(" ")

    # parse the entire case
    available_key_list = starting_key_list
    required_key_list = []
    # each element chest_map represents a chest in this way: chest_index(1 based), chest_type, key_list
    chest_map = []
    for chest_index in range(1, num_of_chest+1):
        chest_info = in_f.readline().rstrip('\n').replace(" 0", "").split(" ")
        required_key_list.append(chest_info[0])
        chest_key_list = chest_info[1:]
        if not len(chest_key_list):
            could_check_deadlock = False
        else:
            available_key_list = available_key_list + chest_key_list
        chest_info.insert(0, str(chest_index))
        chest_map.append(chest_info)
    # print "required_key_list:{}".format(required_key_list)
    # print "available_key_list:{}".format(available_key_list)
    # print "chest_map:{}".format(chest_map)

    if not is_enough_keys(out_f, case_index, available_key_list, required_key_list):
        return
    if not is_starting_key_list_useful(out_f, case_index, starting_key_list, required_key_list):
        return
    if not has_enough_required_keys(out_f, case_index, starting_key_list, available_key_list, required_key_list, chest_map):
        return

    # after all the sanity checks, start hunting!
    # TODO: need to change the brute force solution later...
    current_solution_route = ""
    solve_result = solve_current_treasure(current_solution_route, starting_key_list, chest_map, available_key_list)
    if not solve_result:
        out_f.write("Case #{}: IMPOSSIBLE\n".format(case_index))
    elif solve_result in ["NKFLC", "DL", "SCDL"]:
        out_f.write("Case #{}: IMPOSSIBLE\n".format(case_index))
    else:
        out_f.write("Case #{}:{}\n".format(case_index, solve_result))
        
def solve_current_treasure(current_solution_route, current_key_list, current_chest_map, available_key_list):
    """
        Return the solved chest sequence str, None if it is Impossible to solve
    """
    #TODO: instead of using list, should using string, so the value get remained even after a failed try.
    #TODO: do all the sanity checks again.
    # base condition check:
    # print "---------------------------solve_current_treasure-------------------------"
    # print "current_solution_route:{}".format(current_solution_route)
    # print "current_key_list:{}".format(current_key_list)
    # print "current_chest_map:{}".format(current_chest_map)
    len_of_current_chest_map = len(current_chest_map)
    if len(current_key_list) == 0:
        # print "return None as no keys"
        return None
    if len_of_current_chest_map == 1:
        # print "try solution {}-{}".format(current_solution_route, current_chest_map[0][0])
        if current_chest_map[0][1] in current_key_list:
            # print "return ----------solution str --------------{}".format(current_solution_route + " " + current_chest_map[0][0])
            return current_solution_route + " " + current_chest_map[0][0]
        else:
            # indicates that this is not solvable.
            # print "return None as no key for last chest"
            return None
    # before brute force, apply some short circuits:
    if could_check_deadlock and is_deadlock_reached(current_chest_map, current_key_list):
        # print "deadlock detected"
        return "DL"

    #if is_self_containing_deadlock(current_chest_map, available_key_list):
        # print "self containing deadlock detected"
        #return "SCDL"

    # Do something and recursive
    for i in range(0, len_of_current_chest_map):
        # print "try solution {}-{}".format(current_solution_route, current_chest_map[i][0])
        # try if open i-th chest will get a reasonable solution
        current_index = i
        chest_index = current_chest_map[current_index][0]
        chest_type = current_chest_map[current_index][1]
        if chest_type in current_key_list:
            # open i-th chest
            # the following operations need redo upon failure as this is passing by object not passing by value.
            temp_current_key_list = list(current_key_list)
            current_key_list.remove(chest_type)
            new_available_key_list = current_chest_map[current_index][2:]
            if len(new_available_key_list) > 0:
                current_key_list = current_key_list + new_available_key_list
            temp_current_chest_map = list(current_chest_map)
            current_chest_map.pop(current_index)
            solve_result = solve_current_treasure(current_solution_route + " " + chest_index, current_key_list, current_chest_map, available_key_list)
            if solve_result in ["NKFLC", "DL", "SCDL"]:
                return solve_result
            if solve_result:
                # print "return ----------solution str --------------{}".format(solve_result)
                return solve_result
            # print "pass as no solution for sub question"
            # redo all the failed operations so we could try a new route with old state.
            current_key_list = list(temp_current_key_list)
            current_chest_map = list(temp_current_chest_map)
        else:
            pass
            # print "pass as no suitable key for chest index:{}, chest type:{}".format(chest_index, chest_type)
    # print "return None as no solution found."
    return None

def has_starting_key_list(in_f, out_f, case_index, starting_key_list):
    """
        Sanity Check -- Short Circuit function
        return False if there is no starting keys at all.
        The question states "You already have at least one key" but I don't know why I decided not to trust it...
    """
    # print "starting_key_list:{}".format(starting_key_list)
    if not starting_key_list:
        # consume all the remaining case info lines
        for j in range(1, num_of_chest+1):
            chest_info = in_f.readline()
            pass
        # print "No starting keys"
        out_f.write("Case #{}: IMPOSSIBLE\n".format(case_index))
        return False
    return True
    
def is_enough_keys(out_f, case_index, available_key_list, required_key_list):
    """
        Sanity Check -- Short Circuit function
        return False if the number of keys are less than the number of chest
    """
    if len(available_key_list) < len(required_key_list):
        # print "Short of keys"
        out_f.write("Case #{}: IMPOSSIBLE\n".format(case_index))    
        return False
    return True

def is_starting_key_list_useful(out_f, case_index, starting_key_list, required_key_list):
    """
        Sanity Check -- Short Circuit function
        return False if any of the staring key could not open any of the chest.
    """
    for i in range(0, len(starting_key_list)):
        if starting_key_list[i] in required_key_list:
            return True
    # print "Unuseful starting keys"
    out_f.write("Case #{}: IMPOSSIBLE\n".format(case_index))    
    return False

def has_enough_required_keys(out_f, case_index, starting_key_list, available_key_list, required_key_list, chest_map):
    """
        Sanity Check -- Short Circuit function
        return False if there is a chest requires a key type which can not be found or less found in the available key list. 
        TODO: Further more, could remove the keys in the chest itself. Each chest should have a key counter.
    """
    available_key_counter = collections.Counter(available_key_list)
    required_key_counter = collections.Counter(required_key_list)
    # print available_key_counter
    # print required_key_counter
    for key_type, number in required_key_counter.iteritems():
        if required_key_counter[key_type] > available_key_counter[key_type]:
            # print "not enough required keys for key type: {}".format(key_type)
            out_f.write("Case #{}: IMPOSSIBLE\n".format(case_index))    
            return False
    return True

def is_deadlock_reached(current_chest_map, current_available_key_list):
    """
        return true if none of the remaining chests could be opened by the current available key list.
        this check is meaningful only if: in the initial chest map, there is no chest which contains no keys at all.
    """
    current_required_key_list = [chest_info[1] for chest_info in current_chest_map]
    current_required_key_list = list(set(current_required_key_list))
    for required_key in current_required_key_list:
        if required_key in current_available_key_list:
            return False
    return True

def is_self_containing_deadlock(current_chest_map, available_key_list):
    """
        return true if none of the remaining chests could be opened by the "outside world".
    """
    current_required_key_list = [chest_info[1] for chest_info in current_chest_map]
    available_key_list_from_outside_world = list(available_key_list)
    # print "------------------&&&&&&&&&&&&&&&&&--------------------------------------"
    # print current_required_key_list
    # print available_key_list
    for required_key in current_required_key_list:
        try:
            available_key_list_from_outside_world.remove(required_key)
        except:
            pass
    # print current_required_key_list
    # print available_key_list_from_outside_world
    for required_key in current_required_key_list:
        if required_key in available_key_list_from_outside_world:
            return False
    return True

if __name__ == '__main__':
    treasure()


# short circuits
#. Done 1. if there is no starting keys, False
#  Done 2. if len(available_key_list) < len(required_key_list)
#. Done 3. if the starting key is not suitable for any chests
#. 4. There is one type of chest w/o any keys. Take advantage of set
#. 5. total keys could not cover all the required chest keys.  might use Counter object.



#key_list
#chest_list
#required_key_list