Programming Warmups

Fruchterhash.java

package test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

/**
 * A not-very-efficient hashmap with an array as a base.
 * 
 * @author eric
 * 
 */
public class Fruchterhash {
	A[] a1 = new A[1];
	int size = 0;

	public void resize(final int size) {
		A[] t = a1;
		a1 = new A[size];
		this.size = 0;
		for (int i = 0; i < t.length; i++) {
			if (t[i] != null)
				put(t[i]);
		}
	}

	public void put(final A a) {
		int slot = a.key % a1.length;
		while (a1[slot] != null && a1[slot].key != a.key) {
			slot = (slot + 1) % a1.length;
		}
		if (a1[slot] != null)
			size--;
		a1[slot] = a;
		size++;

		if (size > a1.length * .7) {
			resize(a1.length * 2);
		}
	}

	public A remove(final int key) {
		int flag = key % a1.length;
		int slot = flag;
		do {
			if (a1[slot].key == key) {
				A a = a1[slot];
				a1[slot] = null;
				size--;
				return a;
			} else
				slot = (slot + 1) % a1.length;

		} while (flag != slot);
		return null;
	}

	public A get(final int key) {
		int flag = key % a1.length;
		int slot = flag;
		do {
			if (a1[slot] != null && a1[slot].key == key)
				return a1[slot];
			else
				slot = (slot + 1) % a1.length;

		} while (flag != slot);
		return null;
	}

	/**
	 * The hashable thing.
	 * 
	 * @author eric
	 * 
	 */
	public class A {
		final int key;
		final Object o;

		@Override
		public boolean equals(Object a) {
			if (a instanceof A)
				return key == ((A) a).key && o == ((A) a).o;
			else
				return false;
		}

		public A(int k, Object o) {
			this.key = k;
			this.o = o;
		}
	}

	@Test
	public void test() {
		A a1 = new A(1, "f");
		A a1_1 = new A(1, "7");
		A a2 = new A(300, "4");

		Fruchterhash h = new Fruchterhash();

		assertFalse(a1.equals(a1_1));
		assertTrue(a1.equals(a1));
		assertFalse(a1.equals("dd"));
		assertFalse(a1.equals(a2));

		h.put(a1);
		assertTrue(h.get(1).equals(a1));

		h.remove(1);
		assertTrue(h.get(1) == null);

		h.put(a1);
		h.put(a1);
		h.put(a1_1);
		assertTrue(h.size == 1);

		h.put(a2);
		assertTrue(h.size == 2);

		assertFalse(h.get(1).equals(a1));
		assertTrue(h.get(1).equals(a1_1));
		assertTrue(h.get(a2.key).equals(a2));
	}
}

Pattern.cs

using System;
using regex;

namespace regex
{
	public class Regex
	{
		public static void Main(string[] args) {
			var pattern = "ab*ba";
			var str = "abfbbbbbbbaba";

			Console.WriteLine(parse(pattern, str));
		}

		//char (excluding *) and *
		//* takes up 0 or more random chars
		public static bool parse(string pattern, string str) {
			if (pattern.Length > 0 && str.Length == 0)
				return false;
			if (pattern.Length == 0 && str.Length > 0)
				return false;
			else if (pattern.Length == 0 && str.Length == 0)
				return true;

			char pChar = pattern [0];
			if (pChar == '*') {
				bool result = false;
				result = result | parse (pattern.Substring (1), str); //0 chars
				result = result | parse (pattern.Substring (1), str.Substring (1)); //1 random
				result = result | parse (pattern, str.Substring (1)); //1+ random
				return result;
			} else if (pChar == str [0]) {
				return parse (pattern.Substring (1), str.Substring (1));
			}

			//This shouldn't ever happen!
			return false;
		}
	}
}

warmup.py

# Find the optimal weight for a Knapsack and list of items
# K: Integer weight capacity of Knapsack
# I: list of item tuples (weight, value)
#    All weights must be integers and greater than 0.
# returns: The optimal value for K, plus an optimal list of items
def knapsack (K, I): # [v]
    vMemo, iMemo = [0] * (K + 1), []
    for i in range(K+1): iMemo += [[]]
    for k in range (1, K + 1):
        for item in I:
            w, v = item
            for subK in range(k - 1, -1, -1):
                if subK + w <= k and vMemo[k] < vMemo[subK] + v:
                    iMemo[k], vMemo[k] = iMemo[subK] + [item], vMemo[subK] + v
    return vMemo[K], iMemo[K]

def quicksort(li):
    if len(li) <= 1:
        return li
    left, right = [], []
    for i in li[1:]:
        if i < li[0]:
            left += [i]
        else:
            right += [i]   
    return quicksort(left) + [li[0]] + quicksort(right)

def mergesort(li):
    if len(li) <= 1:
        return li
    left = mergesort(li[:len(li) / 2])
    right = mergesort(li[len(li) / 2:])
    result = []
    while left or right:
        if left and right:
            if left[0] < right[0]:
                result += [left[0]]
                left = left[1:]
            else:
                result += [right[0]]
                right = right[1:]
        elif left and not right:
            result += left
            left = []
        else:
            result += right
            right = []
    return result

Warmup1.cs

using System;
using VectorMath;
using Sorts;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
using graph;

namespace test
{
	class MainClass
	{
		public static void Man (string[] args)
		{
			Node n1 = new Node (1);
			Node n2 = new Node (2);
			Node n3 = new Node (3);
			Node n4 = new Node (4);

			n1.DefineEdge (n4, 10);
			n2.DefineEdge (n3, 1);
			n3.DefineEdge (n4, 7);

			n1.DefineEdge (n2, 1);
			n3.DefineEdge (n1, 10);

			Console.WriteLine (n1);
			Console.WriteLine (n2);
			Console.WriteLine (n3);
			Console.WriteLine (n4);

			Console.WriteLine ("\n");

			var result = GraphUtils.UCS (n1, n4);
			Console.WriteLine (string.Join ("->", result.path));
			Console.WriteLine(result.dist);
		}
	}
}

namespace Sorts {

	public class SortUtils <T> where T : IComparable<T> {

		public static List<T> QuickSort (List<T> list) {
			if (list.Count <= 1)
				return list;

			T pivot = list [0];

			List<T> less = new List<T> ();
			List<T> greater = new List<T> ();

			for (int i = 1; i < list.Count; i++) {
				if (list [i].CompareTo (pivot) <= 0)
					less.Add (list [i]);
				else
					greater.Add (list [i]);
			}

			less = QuickSort (less);
			greater = QuickSort (greater);

			less.Add (pivot);
			less.AddRange (greater);

			return less;
		}

		public static List<T> MergeSort(List<T> list) {
			if (list.Count <= 1)
				return list;

			var half = list.Count / 2;
			var missing = list.Count % 2;

			// partition
			List<T> left = new List<T>(list.Take (half));
			List<T> right = new List<T>(list.Skip (half).Take (half + missing));

			left = MergeSort (left);
			right = MergeSort (right);

			// mix

			List<T> result = new List<T> ();

			while (left.Count > 0 || right.Count > 0) {
				if (left.Count == 0) {
					result.AddRange (right);
					right.Clear ();
				} else if (right.Count == 0) {
					result.AddRange (left);
					left.Clear ();
				} else {
					T lVal = left [0], rVal = right [0];
					if (lVal.CompareTo (rVal) <= 0) {
						result.Add (lVal);
						left.RemoveAt (0);
					} else {
						result.Add (rVal);
						right.RemoveAt (0);
					}
				}
			}

			return result;
		}
	}
}

namespace VectorMath
{
	class Vector2
	{
		public readonly double x, y;

		private double cached_mag = -1;

		public Vector2 (double x, double y)
		{
			this.x = x;
			this.y = y;
		}

		public static Vector2 operator + (Vector2 a, Vector2 b)
		{
			return new Vector2 (a.x + b.x, a.y + b.y);
		}

		public static Vector2 operator - (Vector2 a, Vector2 b)
		{
			return new Vector2 (a.x - b.x, a.y - b.y);
		}

		public static Vector2 operator * (Vector2 a, double b)
		{
			return new Vector2 (a.x + b, a.y + b);
		}

		public static Vector2 operator * (Vector2 a, Vector2 b)
		{
			return new Vector2 (a.x * b.x, a.y * b.y);
		}

		public double Dot (Vector2 b)
		{
			return (this.x * b.x) + (this.y * b.y);
		}

		public double Mag ()
		{
			if (cached_mag != -1)
				return cached_mag;
			else
				return cached_mag = Math.Sqrt (this.Dot (this));
		}

		public Vector2 Unit()
		{
			if (this.x == 0 && this.y == 0)
				return new Vector2 (0, 0);
			return this * (1D / this.Mag ());
		}

		public override string ToString()
		{
			return "(" + this.x + ", " + this.y + ")";
		}
	}
}

namespace graph
{

	public class NodeComparator : Comparer<Node> {
		public override int Compare(Node a, Node b) {
			return -1 * a.distanceFromStart.CompareTo (b.distanceFromStart);
		}
	}

	public class Node {
		public object data;
		public double distanceFromStart = double.MaxValue;
		public Dictionary<Node, double> edges = new Dictionary<Node, double>();

		public Node(object data) {
			this.data = data;
		}

		public void DefineEdge(Node node, double dist) {
			this.edges.Add (node, dist);
		}

		public override string ToString ()
		{
			string r = data.ToString();
			r += " [";
			foreach (var node in edges.Keys) {
				r += node.data + " ";
			}
			return r + "]";
		}
	}

	public class GraphUtils {

		public class SearchResult
		{
			public LinkedList<Node> path = new LinkedList<Node>();
			public double dist = 0;
		}

		public static SearchResult BFS(Node start, Node goal) {
			LinkedList<Node> frontierQueue = new LinkedList<Node> ();
			frontierQueue.AddFirst (start);

			HashSet<Node> exploredSet = new HashSet<Node> ();
			HashSet<Node> frontierSet = new HashSet<Node> ();
			frontierSet.Add (start);

			Dictionary<Node, Node> parents = new Dictionary<Node, Node>();

			while (frontierQueue.Count > 0 && !exploredSet.Contains (goal)) {
				Node exploring = frontierQueue.First();
				frontierQueue.RemoveFirst();

				frontierSet.Remove (exploring);
				exploredSet.Add (exploring);

				foreach (var node in exploring.edges.Keys) {
					if (!exploredSet.Contains (node) && !frontierSet.Contains (node)) {
						frontierQueue.AddLast (node);
						frontierSet.Add (node);

						parents [node] = exploring;
					}
				}
			}

			var result = new SearchResult ();

			if (!exploredSet.Contains (goal))
				return result;

			Node current = goal;
			while (true) {
				result.path.AddFirst (current);
				if (current == start)
					break;
				result.dist += parents [current].edges [current];
				current = parents [current];
			}

			return result;
		}

		public static SearchResult DFS(Node start, Node goal) {
			LinkedList<Node> frontierQueue = new LinkedList<Node> ();
			frontierQueue.AddFirst (start);

			HashSet<Node> exploredSet = new HashSet<Node> ();
			HashSet<Node> frontierSet = new HashSet<Node> ();
			frontierSet.Add (start);

			Dictionary<Node, Node> parents = new Dictionary<Node, Node>();
			Dictionary<Node, double> costFromStart = new Dictionary<Node, double>();
			costFromStart.Add (start, 0);

			while (frontierQueue.Count > 0 && !exploredSet.Contains (goal)) {

				frontierQueue = new LinkedList<Node>(frontierQueue.OrderByDescending (o => (costFromStart [o])).ToList());

				Node exploring = frontierQueue.First();
				frontierQueue.RemoveFirst();

				frontierSet.Remove (exploring);
				exploredSet.Add (exploring);

				foreach (var node in exploring.edges.Keys) {
					if (!exploredSet.Contains (node) && !frontierSet.Contains (node)) {
						frontierQueue.AddFirst (node);
						frontierSet.Add (node);
						parents [node] = exploring;
						costFromStart [node] = costFromStart [exploring] + exploring.edges [node];
					}
				}
			}

			var result = new SearchResult ();

			if (!exploredSet.Contains (goal))
				return result;

			Node current = goal;
			while (true) {
				result.path.AddFirst (current);
				if (current == start)
					break;
				result.dist += parents [current].edges [current];
				current = parents [current];
			}

			return result;
		}

		public static SearchResult UCS(Node start, Node goal) {
			SortedSet<Node> frontierQueue = new SortedSet<Node> (new NodeComparator());
			frontierQueue.Add (start);
			start.distanceFromStart = 0;

			HashSet<Node> exploredSet = new HashSet<Node> ();

			Dictionary<Node, Node> parents = new Dictionary<Node, Node>();

			while (frontierQueue.Count > 0 && !exploredSet.Contains (goal)) {

				Node exploring = frontierQueue.First();
				frontierQueue.Remove (exploring);

				exploredSet.Add (exploring);

				foreach (var node in exploring.edges.Keys) {
					if (!exploredSet.Contains (node)) {
						frontierQueue.Add (node);

						var cost = exploring.distanceFromStart + exploring.edges [node];
						if (node.distanceFromStart > cost) {
							node.distanceFromStart = cost;
							parents [node] = exploring;
						}
					}
				}
			}

			var result = new SearchResult ();

			if (!exploredSet.Contains (goal))
				return result;

			Node current = goal;
			while (true) {
				result.path.AddFirst (current);
				if (current == start)
					break;
				result.dist += parents [current].edges [current];
				current = parents [current];
			}

			return result;
		}
	}
}