"""
cs_riddles.py -- V.1.1, Feb 14 2007, by leonardo maffi

This Python (V.2.5) code contains few solutions to "Hardcore tech-interview style riddles
and mathematical puzzles.", URL:
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml

I have chosen some of the most interesting, avoiding some boring or too much difficult ones.

Some riddles that I may do in the future (see the end of this code):
dynamicProgramming, datingPossibilities, sweetheartMixTape, closestPoint
"""


if 1:
    doc = """
    BINARY TREE PRINT
    How would you print out the data in a binary tree, level by level, starting at the top?
    http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#binaryTreePrint
    """
    print doc
    from collections import defaultdict # Python V.2.5
    # btreeprint is present among my software, possible URL:
    # http://www.fantascienza.net/leonardo/so/btreeprint.py
    from btreeprint import N, btreestr

    def fulltree(n, i=0):
        "Return the full binary tree of order n, represented with N() nodes."
        return N(i, fulltree(n-1, i*2+1), fulltree(n-1, i*2+2)) if n else None

    def visit_by_level1(tree, depth=0, levels=None):
        "My solution, I think this is simpler to understand"
        if levels is None:
            levels = defaultdict(list)
        if tree is not None:
            levels[depth].append(tree.data)
            visit_by_level1(tree.left, depth+1, levels)
            visit_by_level1(tree.right, depth+1, levels)
        return levels

    t = fulltree(5)
    print btreestr(t)
    print "\nvisit_by_level1:"
    print visit_by_level1(t)

    def visit_by_level2(S):
        "Alternative solution that I have found around."
        T = set()
        for node in S:
            print node.data,
            if node.left is not None:
                T.add(node.left)
            if node.right is not None:
                T.add(node.right)
        if T:
            visit_by_level2(T)

    print "\nvisit_by_level2:"
    visit_by_level2(set([t]))
    print "\n"


if 0:
    # NTH FROM END
    # Find the nth element from the end of a linked list (where n < size of list).
    # Note: asked at m$ interviews.
    # http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#nthFromEnd

    # Possible solutions I can see:
    # 1) If you have N memory elements (for the pointers or for the data), you can
    #    use a queue implemented as a circular array. While you scan the list you can
    #    push elements there until they are finished. Then the precedent element of the
    #    last one is the n-1-th element. If len(list)<n it may return None because the
    #    queue is all initialized with None.
    #    http://en.wikipedia.org/wiki/Circular_queue
    # 2) Scan the list twice, the first time to find its len, the second time stopping at the
    #    len-n element. Requires just 1 cell of memory to store the index, then you can store
    #    there n-k and decrement until it's zero.
    # 3) - Start from the head with pointer p1, go on n elements on the list.
    #    - Then define a p2 pointer and set it at the head of the list
    #    - Then make p1 and p2 pointers go on in parallel
    #    - When the p1 is at the end, p2 points the desired element
    #    - This algorithm may be a bit faster than the second because there may be
    #      a bitmore memory locality, but probably not enough to justify the added
    #      complexity. So I'd like to use the second solution, that's a bit simpler

    class Circularqueue:
        "Empty class still. Just a placeholder"
        def __init__(self, n):
            self.queue = [None] * n
            self.head = 0
            self.tail = -1
        def push(self): pass
        def pop(self): pass
        def clear(self): pass
        def __len__(self): pass
        def __str__(self): pass
        def __repr__(self): pass
        def __iter__(self): pass
        def __eq__(self, other): pass
        def __ne__(self, other): pass
        def __cmp__(self, other): pass
        def __nonzero__(self): pass
        def __hash__(self):
            raise TypeError("Circularqueue objects are unhashable.")


if 1:
    doc = """
    MISSING INTEGER IN ARRAY

    You have a 99 cell array. In each cell you put an integer belonging to the
    set {1,2,...,100}. No two cells contain the same integer. Thus when the
    array filling is complete, one of the integers from 1 to 100 is not present
    in the array. Determine which integer is missing from the array. (The lower
    the running time of your algorithm, the better.)"""
    print doc
    assert sum(range(1,101)) == 5050
    from random import randint
    r = range(1, 101)
    del r[randint(0, 99)]
    assert len(r) == 99
    print 5050 - sum(r)
    print r, "\n"


if 1:
    doc = """
    Write a function which converts a number into an Excel spreadsheet column name.
      0 = A
      ...
      25 = Z
      26 = AA
      ...
      701 = ZZ
      702 = AAA
    """
    print doc
    from string import uppercase
    from baseconvert import baseconvert

    def excel_conv(n):
        power26 = 1
        i = 0
        tot = -1
        while n > tot:
            power26 *= 26
            tot = tot + power26
            i += 1
        n -= sum(26 ** i for i in xrange(1, i))
        result = baseconvert(n, inbase=10, outbase=26, outdigits=uppercase)
        return result.rjust(i, "A")

    print [excel_conv(n) for n in [0, 25, 26, 701, 702]]
    print [excel_conv(i) for i in xrange(1000)]
    print


if 1:
    # MAXIMAL SUM IN INTEGER ARRAY
    # http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#maximalSumIntegerArray"
    print "Solution from 'Programming pearls' book:"
    data = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]

    max_so_far = 0.0
    max_ending_here = 0.0
    for el in data:
        max_ending_here = max(max_ending_here + el, 0)
        max_so_far = max(max_so_far, max_ending_here)
    print max_so_far
    print


if 1:
    doc = """
    Find the second smallest integer in an array of n integers.
    Runtime restraint: n + O(log n) comparisons."""
    print "The pythonic solution is to use the standar library as much as possible:"
    class N:
        ncmp = 0
        def __init__(self, n): self.n = n
        def __repr__(self): return repr(self.n)
        def __cmp__(self, other):
            N.ncmp += 1
            return cmp(self.n, other.n)

    from random import uniform

    data = [N(uniform(-10000, 10000)) for _ in xrange(10000)]
    from heapq import nsmallest
    print nsmallest(2, data)[1]
    print "N.comparisons:", N.ncmp
    print


if 1:
    print """
    TIDY RING PROBLEM:
    This isn't contained into: www.ocf.berkeley.edu/~wwu/riddles/cs.shtml
    Problm: given a list of pairs (i, j), that means the element with index i is joined with the
    element with index j. The pairs of the whole list represent a single ring. The pairs and the
    indices inside a pair are unsorted. Create the clean sequence of indices starting from 0.
    """
    chain = [(2, 0), (3, 1), (4, 2), (6, 3), (7, 6), (7, 0), (8, 5), (8, 4), (9, 5), (9, 1)]
    npoints = len(chain)

    from collections import defaultdict
    chain_dict = defaultdict(list)
    for p1, p2 in chain:
        chain_dict[p1].append(p2)
        chain_dict[p2].append(p1)

    print chain_dict
    # {0: [2, 7], 1: [3, 9], 2: [0, 4], 3: [1, 6], 4: [2, 8], 5: [8, 9], 6: [3, 7], 7: [6, 0], 8: [5, 4], 9: [5, 1]}

    last_point = 0
    chain = []
    for i in xrange(npoints):
        point_pair = chain_dict[last_point]
        point = (point_pair[0] if point_pair[0] in chain_dict else point_pair[1])
        del chain_dict[last_point]
        chain.append(last_point)
        last_point = point
    print chain
    # Output: [0, 2, 4, 8, 5, 9, 1, 3, 6, 7]



"""
4 Other interesting riddles:


CLOSEST POINT
You are given coordinates for a set of N points on a 2D plane. After
preprocessing those points in some manner of your own discretion, you are
given a new point v = (x,y). Now your task is to determine which of the
original N points is closest in Euclidean distance to v. Devise the best
algorithm (lowest big-Oh runtime) you can to accomplish this task.

Note 1: From a Mojave Networks tech-interview.
Note 2: Exactly how much time you can spend preprocessing is not specified,
  but I think it's reasonable to say it shouldn't be exponential. After
  preprocessing, the interviewer did give a runtime that your algorithm should
  meet for determining the point closest to v. However, I won't give that away,
  because it could be too much of a hint; furthermore, I am uncertain if an
  even better runtime does not exist.
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#closestPoint



DYNAMIC PROGRAMMING
A burglar breaks into an electronics store. He has a bag of volume V, and he
sees N different gadgets, each with its own price value. He wants to choose
gadgets that maximize the value of his steal, while maintaining his volume
constraint. Write a dynamic programming algorithm that calculates which
objects should be chosen, and the value of the optimal steal.
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#dynamicProgramming



DATING POSSIBILITIES
E is a set of boys and girls. P is a set of unordered pairs (x,y) of those
boys and girls. If two people are in a pair, then they would be willing to
go on a romantic date. List out all the possible dating combinations that
could occur in one night, such that no person dates more than one other
person that night. (Technically: Generate all subsets of P such that no
person is used more than once per subset.)

Example:
  E = { Alice, Bob, Cole, Doris }
  P = { (Alice,Bob) (Alice,Cole) (Bob,Doris) (Cole,Doris) }

A maximal number of dating scenarios that could occur in one night, such
that no one dates more than one person in the same night:
  {(Alice,Bob)}
  {(Alice,Cole)}
  {(Bob,Doris)}
  {(Cole,Doris)}
  {(Alice,Bob),(Cole,Doris)}
  {(Alice,Cole),(Bob,Doris)}
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#datingPossibilities



SWEETHEART MIX TAPE
Willywutang is organizing a mix tape for his overseas sweetheart, April
Underwood. The tape will have her top N songs of all time. Willy was going
to determine the order of these songs on his own, but then April found out
about his little project. Being an obnoxiously demanding woman, she has now
given Willy a price function f which takes a pair of songs [si,sj] as input,
and returns a real number that quantifies exactly how good song sj sounds
after song si, in her opinion. (Note that f([si,sj]) may not be equal to
f([sj,si]).)

Write an O(n^2 * 2^n) algorithm for Willywutang that will determine a song order
which maximizes the total transition goodness of the mix tape. (If the
maximum is not achieved, Willy will be dumped.)

Note 1: Adapted from UC Berkeley, Spring 2001 Final Exam for CS170 (
  Efficient Algorithms and Intractable Problems). Approximate time you would
  get for this problem: 30 mins. Storyline by me :)
 Note 2: This problem is pretty hard.
  http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#sweetheartMixTape
"""