# Created by Michael Broughton on 2013-08-30

# 1. Given 2 dictionaries, return a list of (key,value) pairs that differ.
#    Missing keys are considered different.
# 2. Given a list of [key,value0,value1,value2,...] lists, return a list
#    containing all lists of combinations for the values.
#    IE: Given [['a',1,2],['b',3,4]] return [[1,3],[1,4],[2,3],[2,4]] 
# 3. Given a URL, return the Nth link found on the page.
# 4. Given a directory and a file-extension, return all files/directories
#    below that point that end in that extension.
# 5. Given positive integer N, return a list of all primes < N.
# 6. Given an integer N, return its Euler totient.
# 7. Given a string S, find all word pairs in S that form anagrams of each
#    other. Return them in sorted order as a list of tuples per grouping.
#    Example: Guido was happy once he solved the pycon challenge and won a heap of prizes!
#    Yields: [(('happy', 'once'), ('heap', 'pycon'),)]
# 8. Build a Roman Numeral calculator. Given two strings, return their sum
#    as a Roman Numeral.

from collections import defaultdict
from HTMLParser  import HTMLParser
from itertools   import chain
from itertools   import combinations
from itertools   import count
from itertools   import dropwhile
from itertools   import ifilter
from itertools   import izip
from itertools   import product
from itertools   import takewhile
from operator    import mul
from os          import walk
from os.path     import join
from os.path     import relpath
from urllib2     import urlopen

first_arg    = lambda *args:args[0]
no_arg       = lambda *args:None
return_true  = lambda func:lambda x:first_arg(True,func(x))
loop         = lambda func,iter:no_arg(*dropwhile(return_true(func),iter))

p1_pairs     = lambda keys,*d:((k,D[k]) for k in keys for D in d)
p1_common    = lambda D1,D2:D1.viewkeys()&D2.viewkeys()
p1_diff      = lambda D1,D2:D1.viewkeys()-D2.viewkeys()
p1_intersect = lambda D1,D2:(k for k in p1_common(D1,D2) if D1[k]!=D2[k])
p1_different = lambda D1,D2:p1_pairs(p1_intersect(D1,D2),D1,D2)
p1_missing   = lambda D1,D2:p1_pairs(p1_diff(D1,D2),D1)
p1_join      = lambda M1,D,M2:list(chain(M1,D,M2))

def problem_1(D1,D2):
 return p1_join(p1_missing(D1,D2),p1_different(D1,D2),p1_missing(D2,D1))

p2_values    = lambda seq:(key_values[1:] for key_values in seq)

def problem_2(seq):
 return [list(prod) for prod in product(*p2_values(seq))]

p3_href_attr = lambda attr:attr[0]=='href'
p3_attrs     = lambda attrs:chain(attrs,(('href',None),))
p3_get_href  = lambda attrs:next(ifilter(p3_href_attr,p3_attrs(attrs)))[1]
p3_append    = lambda seq,href:seq.append(href) if href is not None else None
p3_store_a   = lambda attrs,seq:p3_append(seq,p3_get_href(attrs))
p3_check_a   = lambda tag,attrs,seq:p3_store_a(attrs,seq)if tag=='a'else None
p3_lower_a   = lambda tag,attrs,seq:p3_check_a(tag.lower(),attrs,seq)
p3_starttag  = lambda seq:lambda tag,attrs,seq=seq:p3_lower_a(tag,attrs,seq)
p3_setattr   = lambda html,cb:setattr(html,'handle_starttag',cb)
p3_set_cb    = lambda html,seq:p3_setattr(html,p3_starttag(seq))
p3_callback  = lambda html,seq:first_arg(html,p3_set_cb(html,seq))
p3_feed      = lambda page,html,seq:p3_callback(html,seq).feed(page)
p3_all_a     = lambda page,html,seq:first_arg(seq,p3_feed(page,html,seq))
p3_get_nth   = lambda N,seq:seq[N] if 0<=N<len(seq) else None
p3_nth_a     = lambda N,page:p3_get_nth(N,p3_all_a(page,HTMLParser(),[]))
p3_format    = lambda url:url if url.startswith('http') else 'http://'+url

def problem_3(url,N):
 return p3_nth_a(N-1,urlopen(p3_format(url)).read())

p4_join      = lambda base:lambda path:join(base,path)
p4_ends      = lambda path,ext:path.endswith(ext)
p4_filter    = lambda join,path,ext:(join(p) for p in path if p4_ends(p,ext))
p4_path      = lambda base,ext:lambda path:p4_filter(p4_join(base),path,ext)
p4_both      = lambda filter,dir,file:chain(filter(dir),filter(file))
p4_find      = lambda ext,base,dir,file:p4_both(p4_path(base,ext),dir,file)
p4_rel_find  = lambda dir,ext,b,d,f:p4_find(ext,relpath(b,dir),d,f)
p4_chain     = lambda paths:list(chain(*paths))

def problem_4(dir,ext):
 return p4_chain(p4_rel_find(dir,ext,*w) for w in walk(dir))

p5_map_qp    = lambda D,q,p:D.setdefault(q+p,[]).append(p)
p5_unmap_q   = lambda D,q:D.pop(q,None)
p5_mark      = lambda D,q:D.update({q*q:[q]})
p5_multiples = lambda D,q:[p5_map_qp(D,q,p) for p in D[q]]
p5_composite = lambda D,q:no_arg(p5_multiples(D,q),p5_unmap_q(D,q))
p5_prime     = lambda D,q:first_arg(q,p5_mark(D,q))
p5_check_q   = lambda D,q:p5_prime(D,q) if q not in D else p5_composite(D,q)
p5_iter      = lambda n,D:(p5_check_q(D,q) for q in xrange(2,n))
p5_sieve     = lambda n:(p for p in p5_iter(n,{}) if p is not None)

def problem_5(n):
 return list(p5_sieve(n))

p6_object    = lambda n:type('N',tuple(),dict(n=n))
p6_reduce    = lambda n,i:n/i if n/i%i else p6_reduce(n/i,i)
p6_limit     = lambda N:lambda i:first_arg(i,setattr(N,'n',p6_reduce(N.n,i)))
p6_mod       = lambda N:lambda i:N.n%i==0
p6_gte       = lambda N:lambda i:N.n>=i
p6_count     = lambda:chain((2,),count(3,2))
p6_generator = lambda A,B,C:(A(i) for i in ifilter(B,takewhile(C,p6_count())))
p6_methods   = lambda N:(p6_limit(N),p6_mod(N),p6_gte(N))
prime_factor = lambda n:p6_generator(*p6_methods(p6_object(n)))

def problem_6(n):
 return int(reduce(mul,(1-1.0/pf for pf in prime_factor(n)),n))

p7_strip     = lambda word:word.strip(',.?!:;"\'')
p7_clean     = lambda words:[p7_strip(word) for word in words]
p7_split     = lambda sentence:p7_clean(sentence.split())
p7_lower     = lambda words:(word.lower() for word in words)
p7_sorted    = lambda words:tuple(sorted(words))
p7_letters   = lambda words:tuple(sorted(chain(*p7_lower(words))))
p7_word_pair = lambda words:combinations(words,2)
p7_append    = lambda D,words:D[p7_letters(words)].append(p7_sorted(words))
p7_map_pairs = lambda D:lambda words:p7_append(D,words)
p7_loop      = lambda words,D:loop(p7_map_pairs(D),p7_word_pair(words))
p7_mapping   = lambda words,D:first_arg(D,p7_loop(words,D))
p7_words     = lambda words:p7_mapping(words,defaultdict(list)).itervalues()
p7_pairs     = lambda pairs:[tuple(pair) for pair in pairs if len(pair) > 1]

def problem_7(sentence):
 return p7_pairs(p7_words(p7_split(sentence)))

p8_RN        = lambda a='IVXLCDM':a
p8_tens      = lambda a=p8_RN()[::2]:a
p8_fives     = lambda a=p8_RN()[1::2]:a
p8_e_update  = lambda D,mul,pairs:D.update({a*mul:b for a,b in pairs})
p8_e_tens    = lambda D:p8_e_update(D,5,izip(p8_tens(),p8_fives()))
p8_e_fives   = lambda D:p8_e_update(D,2,izip(p8_fives(),p8_tens()[1:]))
p8_equiv     = lambda D:first_arg(D,p8_e_tens(D),p8_e_fives(D))
p8_s_group   = lambda RN=p8_RN():(RN[i:i+3] for i in xrange(0,len(RN)-2,2))
p8_s_update  = lambda D,x,y,z:D.update({x+y:x*4,x+z:y+x*4})
p8_subtr     = lambda D:first_arg(D,[p8_s_update(D,*g) for g in p8_s_group()])
equivalent   = lambda a=p8_equiv({}):a
subtractive  = lambda a=p8_subtr({}):a
additive     = lambda a={v:k for k,v in subtractive().iteritems()}:a
p8_key       = lambda rn,RN=p8_RN():RN.index(rn[0])
p8_ascend    = lambda a=sorted(equivalent(),key=p8_key):a
p8_pred      = lambda map:lambda str,key:str.replace(key,map[key])
p8_replace   = lambda str,map,keys=None:reduce(p8_pred(map),keys or map,str)
p8_sort      = lambda rn:''.join(sorted(rn,key=p8_key,reverse=True))
p8_combine   = lambda rn:p8_replace(rn,equivalent(),p8_ascend())
p8_compress  = lambda rn:p8_replace(rn,additive())
p8_expand    = lambda rn:p8_replace(rn.upper(),subtractive())

def problem_8(RN1,RN2):
 return p8_compress(p8_combine(p8_sort(p8_expand(RN1)+p8_expand(RN2))))