"""
Student code for Word Wrangler game
"""
#http://www.codeskulptor.org/#user43_aMTfqwQh6UpMic3_8.py

import urllib2
import codeskulptor
import poc_wrangler_provided as provided
import random

WORDFILE = "assets_scrabble_words3.txt"


# Functions to manipulate ordered word lists

def remove_duplicates(list1):
    """
    Eliminate duplicates in a sorted list.

    Returns a new sorted list with the same elements in list1, but
    with no duplicates.

    This function can be iterative.
    """
    if not list1:
        return list1
    ans = [list1[0]]
    for item in list1:
        if item != ans[-1]:
            ans.append(item)
    return ans

def intersect(list1, list2):
    """
    Compute the intersection of two sorted lists.

    Returns a new sorted list containing only elements that are in
    both list1 and list2.

    This function can be iterative.
    """
    #Filter works, but is too slow for large lists like the dictionary
    #filter(lambda x: x in list2, list1)
    
    ans = []
    first = list(list1)
    second = list(list2)
    while first and second:
        if first[0] == second[0]:
            ans.append(first.pop(0))
            second.pop(0)
        elif first[0] < second[0]:
            first.pop(0)
        elif first[0] > second[0]:
            second.pop(0)
    return ans
    

# Functions to perform merge sort

def merge(list1, list2):
    """
    Merge two sorted lists.

    Returns a new sorted list containing those elements that are in
    either list1 or list2.

    This function can be iterative.
    """   
    merged = []
    first = list(list1)
    second = list(list2)
    while len(merged) < len(list1) + len(list2) and first and second:
        if first[0] < second[0]:
            merged.append(first.pop(0))
        else:
            merged.append(second.pop(0))
    merged += first
    merged += second
    return merged
                
def merge_sort(list1):
    """
    Sort the elements of list1.

    Return a new sorted list with the same elements as list1.

    This function should be recursive.
    """
    if len(list1) <= 1:
        return list1
    half = len(list1)/2
    return merge(merge_sort(list1[0:half]), merge_sort(list1[half:]))

# Function to generate all strings for the word wrangler game

def gen_all_strings(word):
    """
    Generate all strings that can be composed from the letters in word
    in any order.

    Returns a list of all strings that can be formed from the letters
    in word.

    This function should be recursive.
    """
    if not word:
        return [""]
    if len(word) == 0:
        return [word]
    first = word[0]
    rest = word[1:]
    old_all_strings = gen_all_strings(rest)
    new_strings = []
    for item in old_all_strings:
        for index in range(len(item)+1):
            new_strings.append(first.join([item[0:index], item[index:]]))
    all_strings = old_all_strings + new_strings
    return all_strings

# Function to load words from a file

def load_words(filename):
    """
    Load word list from the file named filename.

    Returns a list of strings.
    """
    url = codeskulptor.file2url(filename)
    netfile = urllib2.urlopen(url)
    words = []
    for line in netfile.readlines():
        words.append(line.strip())
    return words

def run():
    """
    Run game.
    """
    words = load_words(WORDFILE)
    wrangler = provided.WordWrangler(words, remove_duplicates, 
                                     intersect, merge_sort, 
                                     gen_all_strings)
    provided.run_game(wrangler)

# Uncomment when you are ready to try the game
#run()