In [ ]:

    

# Imports
import unittest
import random
import operator
import itertools


    

In [ ]:

    

# Linked List Class
class LinkedList(object):

    def __init__(self, value=None, head=None, tail=None):
        self.head = head
        self.tail = tail
        self.value = value

    def __str__(self):
        return str((self.head.value if self.head is not None else None,
                    self.value,
                    self.tail.value if self.tail is not None else None,
                    ))

    def to_list(self):
        current = self
        values = []
        while current and current.value is not None:
            values.append(current.value)
            current = current.tail
        return values

def generate(values):
    current = head = LinkedList()
    for value in values:
        current.value = value
        current.tail = LinkedList()
        current.tail.head = current
        current = current.tail
    current.head.tail = None
    return head


    

In [ ]:

    

# 3.1 - Three in One

""" I don't like this question. Why would anyone ever want to do this? Weird. I'll do it later. """

class ThreeInOne(object):
    def __init__(self):
        pass

class Test(unittest.TestCase):
    def test(self):
        num = 10
        linkedList = generate(range(num) * 2)
        self.assertListEqual(remove_dups(linkedList).to_list(), range(num))

unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))


    

In [ ]:

    

# 3.2 - Stack Min

class MinStack(list):

    def __init__(self):
        list.__init__(self)
        self._minStack = []

    def append(self, value):
        list.append(self, value)
        if len(self) == 1 or value <= self.min():
            self._minStack.append(value)

    def pop(self):
        value = list.pop(self)
        if value == self.min():
            self._minStack.pop()
        return value

    def min(self):
        return self._minStack[-1]

class Test(unittest.TestCase):

    def test1(self):
        minStack = MinStack()
        values = range(3)
        for i in values:
            minStack.append(i)
        self.assertEqual(minStack.min(), min(values))

    def test2(self):
        minStack = MinStack()
        values = range(3)[::-1]
        for i in values:
            minStack.append(i)
        self.assertEqual(minStack.min(), min(values))

    def test3(self):
        minStack = MinStack()
        values = [3] * 3
        for i in values:
            minStack.append(i)
        self.assertEqual(minStack.min(), min(values))

    def test4(self):
        minStack = MinStack()
        values = [3] * 3 + [2] + [3] * 3
        for i in values:
            minStack.append(i)
        self.assertEqual(minStack.min(), min(values))
        for i in range(len(minStack)):
            self.assertEqual(minStack.min(), min(minStack))
            minStack.pop()

unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))


    

In [ ]:

    

# 3.3 - Stack of Plates

class SuperStack(list):

    def __init__(self, maxSize=10):
        list.__init__(self)
        self._maxSize = maxSize

    def push(self, value):
        if len(self) == 0 or len(self[-1]) == self._maxSize:
            self.append([])
        self[-1].append(value)

    def pop(self):
        if len(self) > 0:
            value = self[-1].pop()
            if len(self[-1]) == 0:
                list.pop(self)
            return value
        raise IndexError('pop from empty list')

class Test(unittest.TestCase):

    def test(self):
        stack = SuperStack(2)
        values = range(3)
        for i in values:
            stack.push(i)
        self.assertEqual(stack.pop(), max(values))

unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))


    

In [ ]:

    

# 3.4 - Queue via Stacks

def flip_stacks(a, b):
    for _ in range(len(a)):
        b.append(a.pop())

class QueueViaStacks(object):

    def __init__(self):
        self.a = []
        self.b = []

    def push(self, value):
        flip_stacks(self.a, self.b)
        self.a.append(value)
        flip_stacks(self.b, self.a)

    def pop(self):
        return self.a.pop()

    def peek(self):
        return self.a[-1]

    def __len__(self):
        return len(self.a)

    def is_empty(self):
        return len(self.a) == 0

    def __repr__(self):
        return str([self.a, self.b])

class Test(unittest.TestCase):

    def test1(self):
        values = range(10)
        queue = QueueViaStacks()
        for v in values:
            queue.push(v)
        self.assertEqual(queue.pop(), values[0])

    def test2(self):
        numValues = 10
        values = random.sample(range(numValues), numValues)
        queue = QueueViaStacks()
        for v in values:
            queue.push(v)
        self.assertEqual(queue.pop(), values[0])

unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))


    

In [ ]:

    

# 3.5 - Sort Stack

def sort_stack(stack):

    sort = []
    while len(stack) > 0:
        temp = stack.pop()
        found = False
        while not found:
            stack.append(sort.pop())
            found = (temp >= value)
        sort.append(temp)
    return sort

class Test(unittest.TestCase):

    def test1(self):
        values = range(10)
        queue = QueueViaStacks()
        for v in values:
            queue.push(v)
        self.assertEqual(queue.pop(), values[0])

    def test2(self):
        numValues = 10
        values = random.sample(range(numValues), numValues)
        queue = QueueViaStacks()
        for v in values:
            queue.push(v)
        self.assertEqual(queue.pop(), values[0])

unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))


    

In [ ]:

    

# 3.6 - Animal Shelter

""" I'd rather continue to the other chapter. """