Intrinsic Programming by Erik Schulz

Solving Boggle

2011-03-16T19:18:00.000-07:00

Trie

function Trie(dictionary) {
  var trie = {};
  
  function insert(word, trie) {
    var word_length = word.length;
    
    if (word_length) {
      var next = trie;
      
      for (var i = 0; i < word_length; i++) {
        var char = word[i];
        
        if (char in next) {
          next = next[char];
        } else {
          var child = {};
          next[char] = child;
          next = child;      
        }
      }
      
      next['|'] = null;
    }
  }
  
  for (var i = 0, length = dictionary.length; i < length; i++) {
    insert(dictionary[i], trie);
  }
  
  // returns true for a word, null for a segment and false otherwise
  this.test = function(str) {
    var next = trie;
    
    for (var i = 0, str_length = str.length; i < str_length; i++) {
      var char = str[i];

      if (char in next) {
        next = next[char];
      } else {
        return null;
      }
    }
    
    return '|' in next;    
  }; 
}

Boggle Search

// main workhorse, depth first
function start_search(start_x, start_y, length_x, length_y, segment, trie, board, visited, results) {
  var min_y = Math.max(0, start_y - 1), 
      min_x = Math.max(0, start_x - 1),
      max_y = Math.min(length_y - 1, start_y + 1),
      max_x = Math.min(length_x - 1, start_x + 1);
      
  for (var y = min_y; y <= max_y; y++) {
    var visited_y = visited[y],
        board_y = board[y];
        
    for (var x = min_x; x <= max_x; x++) {
      if (!visited_y[x]) {
        var segment_new = segment + board_y[x],
            test = trie.test(segment_new);
        
        if (test === true) {
          results[segment_new] = true;
        }
        
        if (test !== null) {
          visited_y[x] = true;
          start_search(x, y, length_x, length_y, segment_new, trie, board, visited, results);
          visited_y[x] = false;
        }
      }
    }
  }
}

function search(trie, board) {
  var length_y = board.length,
      length_x = board[0].length;
  
  var visited = [];
  for (var y = 0; y < length_y; y++) {
    visited[y] = [];
    for (var x = 0; x < length_x; x++) {
      visited[y][x] = false;
    }
  }    
    
  var results = {};
  for (var y = 0; y < length_y; y++) {
    var visited_y = visited[y],
        board_y = board[y];
          
    for (var x = 0; x < length_x; x++) {
      visited_y[x] = true;
      start_search(x, y, length_x, length_y, board_y[x], trie, board, visited, results);
      visited_y[x] = false;
    }
  }
  
  var result_array = [];
  for (var word in results) {
    if (results.hasOwnProperty(word)) {
      result_array.push(word);
    }
  }
  
  result_array.sort();
  
  return result_array;  
}

Example Execution

function solve_boggle(dictionary) {
  var board = [
      ["d", "g", "f", "k"],
      ["o", "z", "a", "c"],
      ["b", "w", "k", "e"],
      ["b", "w", "k", "e"]
    ],
    trie = new Trie(dictionary),
    results = search(trie, board);
  
  $(".results").text(results.join(", "));
}

if (window.localStorage !== null && window.localStorage.dictionary) {
  solve_boggle(window.localStorage.dictionary.split(","), callback);
} else {
  function dictionary_load(data) {
    if (window.localStorage !== null) {
       window.localStorage.dictionary = data.join(",");
    }
    solve_boggle(data, callback);
  }

  $.getScript("http://goo.gl/8EhgZ");
}

Product Array - Interview Question

2010-12-17T09:52:00.000-08:00

Given an array of numbers return an array where each item is replaced by the product of all the other items in the array.

A trivial solution would be to multiply the elements repeatedly for each result giving an O(n^2) solution.

var productOfOthers = function(input) {
    var length = input.length;
    
    var result = [];
    for (var i = 0; i < length; i++) {
        result[i] = 1;
        for (var j = 0; j < length; j++) {
            if (i != j) {
                result[i] *= input[j];
            }
        }
    }
    return result;
};

You could get the total product first and then divide by each element for O(n) but you may introduce floating point error and you have to deal with dividing by zero.

var productOfOthers = function(input) {
    var length = input.length;
    
    var product = 1;
    for (var i = 0; i < length; i++) {
        product *= input[i];
    }
    
    var result = [];
    for (var i = 0; i < length; i++) {
        result[i] = product / input[i];
    }
    
    return result;
};

Taking advantage of Multiplications Associative property you can get minimal error in O(n) by making two runners, one forward and one backward, to calculate the result by result[i] = forward[i-1] * backward[i+1].

var productOfOthers = function(input) {
    var length = input.length;
    
    if (length <= 1) {
        if (length == 1) {
            return [input[0]];
        } else {
            return [];          
        }
    }
        
    var forward = [];
    var product = 1;
    for (var i = 0; i < length; i++) {
        product *= input[i];
        forward[i] = product;
    }

    var backward = [];
    var product = 1;
    for (var i = length - 1; i >= 0; i--) {
        product *= input[i];
        backward[i] = product;
    }
    
    var result = [];
    for (var i = 1; i < length - 1; i++) {
        result[i] = forward[i - 1] * backward[i + 1];
    }

    result[0] = backward[1];
    result[length - 1] = forward[length - 2];   
    
    return result;
};

Pots of Gold - Interview Question

2010-12-16T09:00:00.000-08:00

Given n pots of gold arranged in a line containing different quantities of coins. You are allowed to remove one pot of gold from either end and then another player gets to remove one. This is repeated until no pots remain. Write an algorithm to find the set of moves for collecting the most coins in a two player game. Assume your opponent also takes optimal moves.

var max_gold = function(pots) {
  var length = pots.length;
  if (length <= 1) {
    if (length == 1) {
      return {first: [pots[0]], second: []};
    } else {
      return {first: [], second: []};
    }
  }
  
  var left = max_gold(pots.slice(1));
  var right = max_gold(pots.slice(0, -1));
  
  var left_pot = pots[0]; 
  var right_pot = pots[length - 1];
  
  var left_total = left_pot + sum(left.second);
  var right_total = right_pot + sum(right.second);

  if (left_total >= right_total) {
    return {
      first: [left_pot].concat(left.second), 
      second: left.first
    };
  } else {
    return {
      first: [right_pot].concat(right.second),
      second: right.first
    };
  }
};

// sample input 
[11, 19, 18, 16, 1, 4, 7, 3, 6, 2]
// sample output
{first: [11, 18, 2, 3, 4], second: [19, 16, 6, 7, 1]}

This can be easily optimized from O(2^n) into O(n^2) by moving to array indexes and memoization. Note: I'm ignoring the cost of sum, slice and concat for BigO. If you only wanted the total then you could just keep track of it instead of an array and save a bunch of memory.

var max_gold = memoize(function(pots, start, stop) {
  if (start >= stop) {
    if (start == stop) {
      return {first: [pots[start]], second: []};
    } else {
      return {first: [], second: []};
    }
  }
  
  var left = max_gold(pots, start + 1, stop);
  var right = max_gold(pots, start, stop - 1);
  
  var left_pot = pots[start]; 
  var right_pot = pots[stop];
  
  var left_total = left_pot + sum(left.second);
  var right_total = right_pot + sum(right.second);

  if (left_total >= right_total) {
    return {
      first: [left_pot].concat(left.second), 
      second: left.first
    };
  } else {
    return {
      first: [right_pot].concat(right.second),
      second: right.first
    };
  }
});

var memoize = function(f) {
  var store = {};
  return function(pass_through, x, y) {
    var value;
    if (x in store) {
      if (y in store[x]) {
        value = store[x][y]; 
      } else {
        value = f(pass_through, x, y);
        store[x][y] = value;
      }
    } else {
      value = f(pass_through, x, y);
      store[x] = {};
      store[x][y] = value;
    }
    return value;
  }
};

You can remove the memoization with dynamic programming for extra speed at the cost of some readability.

var max_gold_dynamic = function(pots) {
  var length = pots.length;
  var gold_array = [];
  for (var start = length - 1; start >= 0; start--) {
    gold_array[start] = [];
    for (var stop = start; stop < length; stop++) {
      if (start >= stop) {
        if (start == stop) {
          gold_array[start][stop] = {first: [pots[start]], second: []};
          continue;
        } else {
          gold_array[start][stop] = {first: [], second: []};
          continue;
        }
      }
      
      var left = gold_array[start + 1][stop];
      var right = gold_array[start][stop - 1];
    
      var left_pot = pots[start]; 
      var right_pot = pots[stop];
      
      var left_total = left_pot + sum(left.second);
      var right_total = right_pot + sum(right.second);
    
      if (left_total >= right_total) {
        gold_array[start][stop] = {
          first: [left_pot].concat(left.second), 
          second: left.first
        };
      } else {
        gold_array[start][stop] = {
          first: [right_pot].concat(right.second),
          second: right.first
        };
      }
    }
  }
  return gold_array[0][length - 1];
};

Beating Quick Sort - Cartesian Tree Merge

2010-07-07T14:03:00.000-07:00

After looking at skew heap, merge sort and Cartesian tree, I figured there has to be a way to combine all three. My idea is to start with a cartesian tree, take its root as the first element and then merge its leafs in a way that skews them to the right. Children swapping is employed to keep the tree shallow. The number of comparisons required for this sort is consistently less than quick sort. I also changed the Cartesian tree generator to use a stack instead of a parent node to save memory.

A second test with partially sorted data.

algorithms.sort.cartesian_tree_merge = function(array, predicate) {
    var length = array.length;
    if (length <= 1) return;
    
    var root = {"value": array[0], "left": null, "right": null};
    var last = root;
    var stack = [];
    
    for (var i = 1; i < length; i++) {
        while(!predicate(last.value, array[i])) {
            if (stack.length) {
                last = stack.pop();
            } else {
                last = null;
                break;
            }
        }
        if (last) {
            last.right = {"value": array[i], "left": last.right, "right": null};
            stack.push(last);
            last = last.right;
        } else {
            root = {"value": array[i], "left": root, "right": null};
            last = root;
            stack.push(last);
        }
    }

    var swapChildren = function(node) {
        var temp = node.left;
        node.left = node.right;
        node.right = temp;
    };      
                
    var merge = function(left, right) {
        if (!left) {
            return right;
        }

        if (!right) {
            return left;
        }

        if (predicate(left.value, right.value)) {
            var insert = right;
            var next = left;
        } else {
            var insert = left;
            var next = right;
        }
        
        swapChildren(next);
        next.right = merge(insert, next.right);
        return next;
    };

    i = 0;
    while (root) {
        array[i] = root.value;
        i++;       
        root = merge(root.left, root.right);
    }
};

Cartesian Tree Sort - Skew Heap

2010-06-28T11:36:00.000-07:00

Since any heap tree, including Cartesian trees, degrade into sorted linked list when they are fully unbalanced it makes sense to try and unbalance the Cartesian tree. It turns out that a Skew heap works great for this. The following Cartesian skew tree now approaches the speed of quick sort (number of compares) for random data while maintaining linear time for nearly sorted data.

I added a quick sort for comparison.

algorithms.sort.cartesian_tree_skew = function(array, predicate, profile) {
    var swapChildren = function(node) {
        var temp = node.left;
        node.left = node.right;
        node.right = temp;
    };
    
    var length = array.length;
    if (length <= 1) return;
    
    // parent could be removed with the use of a stack
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    for (var i = 1; i < length; i++) {
        while(last && !predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
    
    i = 0;
    while (root) {
        array[i] = root.value;
        i++;

        if (!root.left) {
            root = root.right;
            continue;
        }
        
        if (!root.right) {
            root = root.left;
            continue;
        }

        if (predicate(root.left.value, root.right.value)) {
            var insert = root.right;
            root = root.left;
        } else {
            var insert = root.left;
            root = root.right;
        }

        var next = root;
        do {
            if (!next.right) {
                next.right = insert;
                break;
            }

            if (predicate(next.right.value, insert.value)) {
                next = next.right;
            } else {
                var temp = next.right;
                next.right = insert;
                swapChildren(insert);
                insert = temp;
            }
        } while (true);
    }
};

Cartesian Tree Sort - Revisited

2010-06-25T11:09:00.000-07:00

Thinking about Cartesian tree sort some more it seems logical to also use the Cartesian tree as the priority queue since it is already a heap. Performance appears to be the same without the extra memory requirement of an external priority queue.

algorithms.sort.cartesian_tree_erik = function(array, predicate) {
    var length = array.length;
    if (length <= 1) return;
            
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    for (var i = 1; i < length; i++) {
        while(last && predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
            
    var i = 0;
    while (root) {
        array[i] = root.value;
        i++;

        if (!root.left) {
            root = root.right;
            continue;
        }
                
        if (!root.right) {
            root = root.left;
            continue;
        }

        if (predicate(root.left.value, root.right.value)) {
            var insert = root.left;
            root = root.right;
        } else {
            var insert = root.right;
            root = root.left;
        }
                
        var next = root;
        do {
            if (!next.left) {
                next.left = insert;
                break;
            }
                    
            if (!next.right) {
                next.right = insert;
                break;
            }

            if (predicate(next.left.value, next.right.value)) {
                if (predicate(next.left.value, insert.value)) {
                    var temp = next.left;
                    next.left = insert;
                    insert = temp;
                } else {
                    next = next.left;
                }
            } else {
                if (predicate(next.right.value, insert.value)) {
                    var temp = next.right;
                    next.right = insert;
                    insert = temp;
                } else {
                    next = next.right;
                }      
            }
        } while (true);
    }
};

Cartesian Tree Sort

2010-06-24T20:55:00.000-07:00

Cartesian tree sort solves heap sort's problem of not taking advantage of partially sorted data by building a Cartesian tree. This tree is then traversed pre-prder inserting nodes into a priority queue. The nodes are removed from the priority queue as they are being inserted. Since the Cartesian tree is also a heap, nodes are not removed out of order. In the case of partially sorted data, the Cartesian tree degrades into an unbalanced tree resembling a linked list. Since there is only one element per row, the priority queue pushes and pops the same element without doing any comparisons.

This has θ(n log n) worse case running time and θ(n) running time for sorted data. Cartesian tree sort does require extra space for the tree and priority queue. Wikipedia on Cartesian tree sort.

This flattened Cartesian tree graph has a x-axis of the element index and a y-axis of the nodes depth. The root is the topmost dot. Cartesian trees can be built in linear time and will return the original data in order if the tree is traversed in-order.

algorithms.sort.cartesian_tree = function(array, predicate) {
    var queue = algorithms.queue.priority(function(a, b) {
        return predicate(a.value, b.value);
    });
    
    var length = array.length;
    if (length <= 1) return;
    
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    
    for (var i = 1; i < length; i++) {
        while(last && predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
    
    queue.add(root);
    array = [];
    while(!queue.empty()) {
        var node = queue.remove();
        
        array.push(node.value);
        
        if (node.left) {
            queue.add(node.left);
        }
        
        if (node.right) {
            queue.add(node.right);
        }
    }
};

Insertion Sort

2010-06-21T16:47:00.000-07:00

Insertion sort works by iterating over a list once starting from the left. It looks at each element and the previous element swapping them if they are out of order and it keeps swapping the same element, moving it left, until the comparison is correct or it is in the first position. Wikipedia on Insertion sort.

An interesting thing about insertion sort is that it often runs faster than many θ(n log n) algorithms for small datasets, 8-20 elements, even though its worse case runtime is θ(n^2).

algorithms.sort.insertion = function(array, predicate){
    var length = array.length;
    for (var start = 1; start < length; start++) {
        var i = start;
        do {
            if (predicate(array, i, i - 1)) {
                array.swap(i, i - 1);
            } else {
                break;
            }
            i--;
        } while (i);
    }
};

Priority Queue & Heap Sort

2010-06-10T22:34:00.000-07:00

A heap implementation of priority queue is very similar to heap sort and can easily be turned into one. The difference implementation wise is that the queue doesn't know the final heap size so it has to build the heap from the ground up. This requires finding parent nodes in the heap and not just child nodes. Performance is nearly identical except the queue requires extra N space. Both of these heap implementations don't take advantage of partially sorted list.

algorithms.queue.priority = function(predicate) {
    var siftDown = function(array, start, end) {
        var root = start;
        while (root * 2 + 1 <= end) {
            var child = root * 2 + 1;
            if (child < end && predicate(array, child, child + 1)) {
                child++;
            }
            if (predicate(array, root, child)) {
                array.swap(root, child);
                root = child;
            } else {
                return;
            }
        }
    };
    var siftUp = function(array, start, end) {
        var child = end;
        while (child > start) {
            var parent = Math.floor((child - 1) / 2);
            if (predicate(array, parent, child)) {
                array.swap(parent, child);
                child = parent;
            } else {
                return;
            }
        }
    };
    var that = {
        heap: [],
        add: function(value) {
            that.heap.push(value);
            siftUp(that.heap, 0, that.heap.length - 1);
        },
        remove: function() {
            that.heap.swap(0, that.heap.length - 1);
            siftDown(that.heap, 0, that.heap.length - 2);
            return that.heap.pop();
        }
    };
    return that;
};

algorithms.sort.heap_priority = function(array, predicate) {
    var queue = algorithms.queue.priority(predicate);
    var length = array.length;

    // turn list into a heap
    for (var i = 0; i < length; i++) {
        queue.add(array[i]);
    }

    // remove max value and restore heap property  
    for (var i = 0; i < length; i++) {
        array[i] = queue.remove();
    }   
};

Heap Sort

2010-06-09T17:36:00.000-07:00

Heap sort is similar to selection sort but instead of scanning the entire list for the minimal value it uses a heap to select the minimal value. There is an added step of rebuilding the heap every time the minimal value is removed. Heap sort's worst-case runtime is θ(n log n). In this implementation I use a max heap. Wikipedia on Heap sort.

algorithms.sort.heap = function(array, predicate) {
    var siftDown = function(start, end) {
        var root = start;
        while (root * 2 + 1 <= end) {
            var child = root * 2 + 1;
            if (child < end && predicate(array, child, child + 1)) {
                child++;
            }
            if (predicate(array, root, child)) {
                array.swap(root, child);
                root = child;
            } else {
                return;
            }
        }
    };
    
    var length = array.length;
    
    // turn list into a heap
    for (var start = Math.floor((length - 2) / 2); start >= 0; start--) {
        siftDown(start, length - 1);    
    }

    // remove max value and restore heap property    
    for (var end = length - 1; end > 0; end--) {
        array.swap(end, 0);  
        siftDown(0, end - 1);    
    }
};

Selection Sort

2010-06-08T18:04:00.000-07:00

The next set of sorts are based on selection sort. Selection sort works by finding the minimal value in a list and swapping it with the first position. This is repeated with the remainder of the list swapping the next minimal value with the second position and so forth until the list is sorted. Wikipedia on Selection sort.

algorithms.sort.selection = function(array, predicate) {
    var length = array.length;
    for (var start = 0; start < length; start++) {
        var min = start;
        for (var i = start; i < length; i++) {
            if (predicate(array, i, min)) {
                min = i;
            }
        }
        array.swap(start, min);  
    }
};

Quick Sort

2010-06-04T17:04:00.000-07:00

Quick sort is a classic divide and conquer algorithm. It works by picking a pivot element and dividing the list into two sub list based on if the elements are less than or grater than the pivot element. This is repeated with new pivots in the smaller lists until the list size equals one.

Implementing this algorithm in place is interesting since you don't know how many elements are going to go on each side of the pivot. To get around this you can swap the pivot element with the last element in the list. Then you iterate over the list moving all the elements less than the pivot before all the elements greater than the pivot. Once this is done you swap the last element again, which is the pivot, with the first element after all the elements less than the pivot. This puts the pivot in the middle and the first element that is greater than the pivot in the last position. The pivot is now in the correct position with all the elements less than it to the left and all the elements greater than it to the right. Wikipedia on Quick sort.

algorithms.sort.quick = function(array, predicate) {
    var quick = function(left, right) {
        if (right >= left) {
            var pivot = Math.floor((right + left) / 2);
            var store = left;
            array.swap(right, pivot);
            // right is now the pivot
            for (var i = left; i <= right; i++) {
                if (predicate(array, i, right)) {
                    array.swap(i, store);
                    store++;
                } 
            }
            array.swap(right, store);
            // right is no longer the pivot
            quick(left, store - 1);
            quick(store + 1, right);
        }
    };
    quick(0, array.length - 1);
};

Gnome Sort

2010-06-03T19:44:00.000-07:00

Gnome sort works by stepping forward in the list if two elements are in order. If they are out of order it swaps them and steps back. This behavior emulates insertion sort but with many swaps. Wikipedia on Gnome sort.

algorithms.sort.gnome = function(array, predicate){
    var i = 0;
    var length = array.length;
    while (i < length - 1) {
        if (!predicate(array, i, i + 1)) {
            array.swap(i, i + 1);
            if (i > 0) {
                i--;
            }
        } else {
            i++;
        }
    }
};

Comb Sort

2010-06-02T19:35:00.000-07:00

Comb sort tries to overcome bubble sorts problems by comparing values far away from one another at first and then slowly reducing the gap until it's comparing adjacent values.
Wikipedia on Comb sort.


algorithms.sort.comb = function(array, predicate){
    var found = true;
    var length = array.length;
    var shrink_factor = 1.247330950103979;
    var gap = length;
    while (found || gap > 1) {
        found = false;
        
        gap = gap / shrink_factor;     
        if (gap < 1) {
            gap = 1;
        }

        var i_gap = Math.ceil(gap);     
        for (var i = 0; i < length - i_gap; i++) {
            if (!predicate(array, i, i + i_gap)) {
                array.swap(i, i + i_gap);
                found = true;
            }
        }
    }
};

Odd-even Sort

2010-06-01T20:23:00.000-07:00

Odd-even sort is another bubble sort variant and is similar to cocktail sort since it makes alternating passes. Instead of changing directions like cocktail, it tests all the even elements in one pass and then all the odd elements in the next. Wikipedia on Odd-even sort.


algorithms.sort.odd_even = function(array, predicate){
    var found = true;
    var length = array.length;
    while (found) {
        found = false;
        for (var i = 0; i < length - 1; i += 2) {
            if (!predicate(array, i, i + 1)) {
                array.swap(i, i + 1);
                found = true;
            }
        }
        
        if (!found)
            break;
            
        for (var i = 1; i < length - 1; i += 2) {
            if (!predicate(array, i, i + 1)) {
                array.swap(i, i + 1);
                found = true;
            }
        }
    }
};

Cocktail Sort

2010-05-31T13:27:00.000-07:00

Cocktail sort is similar to bubble sort except it reverses directions when it reaches the end of the list instead of starting from the beginning. Wikipedia on cocktail sort.


algorithms.sort.cocktail = function(array, predicate){
    var found = true;
    var length = array.length;
    while (found) {
        found = false;
        for (var i = 0; i < length - 1; i++) {
            if (!predicate(array, i, i + 1)) {
                array.swap(i, i + 1);
                found = true;
            }
        }
        
        if (!found)
            break;
            
        for (var i = length - 1; i > 1; i--) {
            if (predicate(array, i, i - 1)) {
                array.swap(i, i - 1);
                found = true;
            }
        }
    }
};

Bubble Sort

2010-05-31T10:53:00.000-07:00

Inspired be Wikipedia's algorithm pages I decided to recreate their animations using JavaSrcipt and HTML5 canvas elements. IE 8 does not support canvas however new versions of all other modern browsers do. Mozilla Firefox, Google Chrome, Safari, and Opera.

Bubble sort works by looking at ever element in a list that is to be sorted and swapping adjacent pairs that are out of order. If it makes it to the end of the list without swapping any elements then it stops and the list is in order. If not then it starts at the beginning again. Wikipedia on Bubble Sort.


algorithms.sort.bubble = function(array, predicate){
    var found = true;
    var length = array.length;
    while (found) {
        found = false;
        for (var i = 0; i < length - 1; i++) {
            if (!predicate(array, i, i + 1)) {
                array.swap(i, i + 1);
                found = true;
            }
        }
    }
};

Pi Day

2010-03-14T12:11:00.000-07:00

Having noticed it was Pi day before Google alerted me to the fact, I'm feeling pretty dorky. Following some links I found the current record holder for the most digits of pi computed. Seeing his algorithm is recursive I thought "Hey I could write that in F# with bigint." So here I am on Pi day computing pi.

There is no square root method built in so I had to make my own. It takes about 30s on my i7 to compute the first 100,000 digits. I confirmed the results against the record holders data.

105790 // digits computed
"70150789337728658035712790913767420805655493624646" // digits 99951..100000


let A = 13591409I
let B = 545140134I
let C = 640320I

let a n = if n % 2I = 0I then (A + B * n) else -(A + B * n)
let p n = (2I*n - 1I) * (6I*n - 5I) * (6I*n - 1I)
let q n = n*n*n * C*C*C / 24I

let div2floor x =
    if x % 2I = 0I then
        x / 2I
    else
        (x - 1I) / 2I

let rec pqt n1 n2 =
    if n1 + 1I = n2 then
        (p n2, q n2, (a n2) * (p n2))
    else
        let m = div2floor (n1 + n2)
        let P1, Q1, T1 = pqt n1 m
        let P2, Q2, T2 = pqt m n2
        (P1*P2, Q1 * Q2, T1*Q2 + P1*T2)

let sqrtC length =
    let rec sqrt x y =
        let e = y - x * x
        let p = e / (2I * x)
        if p = 0I then
            x
        else
            sqrt (x + p) y
    let guess = 800I * bigint.Pow(10I, length / 2)
    let accuracy = bigint.Pow(10I, 2*(length / 2))
    sqrt guess (C * accuracy)

let pi n =
    let p, q, t = pqt 0I n
    let dividend = q
    let divisor = 12I * (t + q * A)
    
    let sign =
        if divisor < 0I then
            -divisor
        else
            divisor
    let length = int (bigint.Log10(sign))

    C * (sqrtC length) * dividend / divisor

let test = string (pi 8000I)
printfn "%A" test.Length
printfn "%A" test.[99951..100000]

Moving on with F# Development

2010-01-17T17:36:00.000-08:00

After a break from game development and finishing a work project in F#, I'm back and it's time for me to leave XNA behind and move on to a collection of specifically designed libraries. For my graphics engine I'm choosing ORGE by way of MORGE a .NET wrapper for it.

After digging into the C# SDK I figured a good start would be porting MorgeForm. To get this code to run install the SDK, create a project, set it to .NET 2.0, add a reference to Mogre_d (C:\MogreSDK\bin\Debug) and set the working directory to C:\MogreSDK\bin\Debug. The sample pulls resources through relative paths so you need to run in the SDK Debug directory.

On a side note I need to make my own custom theme for better syntax highlighting.

open System
open System.Windows.Forms
open System.Drawing

open Mogre

type OgreWindow(origin, hWnd) =
    //----------------------------------------------------- 
    // 1 enter ogre 
    //----------------------------------------------------- 
    let root = new Root()

    do  //----------------------------------------------------- 
        // 2 configure resource paths
        //----------------------------------------------------- 
        let cf = new ConfigFile()
        cf.Load("resources.cfg", "\t:=", true)

        // Go through all sections & settings in the file
        let seci = cf.GetSectionIterator()

        // Normally we would use the foreach syntax, which enumerates the values, but in this case we need CurrentKey too;
        while seci.MoveNext() do
            for pair in seci.Current do
                ResourceGroupManager.Singleton.AddResourceLocation(pair.Value, pair.Key, seci.CurrentKey)

        //----------------------------------------------------- 
        // 3 Configures the application and creates the window
        //----------------------------------------------------- 
        root.RenderSystem <- root.GetAvailableRenderers() |> Seq.find (fun rs -> rs.Name = "Direct3D9 Rendering Subsystem")
        root.RenderSystem.SetConfigOption("Full Screen", "No")
        root.RenderSystem.SetConfigOption("Video Mode", "640 x 480 @ 32-bit colour")

        root.Initialise(false) |> ignore
        let misc = new NameValuePairList()
        misc.["externalWindowHandle"] <- hWnd.ToString()
        let window = root.CreateRenderWindow("Simple Mogre Form Window", 0u, 0u, false, misc.ReadOnlyInstance)
        ResourceGroupManager.Singleton.InitialiseAllResourceGroups()

        //----------------------------------------------------- 
        // 4 Create the SceneManager
        // 
        //  ST_GENERIC = octree
        //  ST_EXTERIOR_CLOSE = simple terrain
        //  ST_EXTERIOR_FAR = nature terrain (depreciated)
        //  ST_EXTERIOR_REAL_FAR = paging landscape
        //  ST_INTERIOR = Quake3 BSP
        //----------------------------------------------------- 
        let sceneMgr = root.CreateSceneManager(SceneType.ST_GENERIC, "SceneMgr")
        sceneMgr.AmbientLight <- new ColourValue(0.5f, 0.5f, 0.5f)

        //----------------------------------------------------- 
        // 5 Create the camera 
        //----------------------------------------------------- 
        let camera = sceneMgr.CreateCamera("SimpleCamera")
        camera.Position <- new Vector3(0.0f, 0.0f, 100.0f)
        // Look back along -Z
        camera.LookAt(new Vector3(0.0f, 0.0f, -300.0f))
        camera.NearClipDistance <- 5.0f

        let viewport = window.AddViewport(camera)
        viewport.BackgroundColour <- new ColourValue(0.0f, 0.0f, 0.0f, 1.0f)

        let ent = sceneMgr.CreateEntity("ogre", "ogrehead.mesh")
        let node = sceneMgr.RootSceneNode.CreateChildSceneNode("ogreNode")
        node.AttachObject(ent)

    member this.Paint() =
        root.RenderOneFrame() |> ignore

    member this.Dispose() =
        if root <> null then
            root.Dispose()

type MogreForm() as this =
    inherit Form()

    let mogrePanel = new System.Windows.Forms.Panel()

    // Between Suspend and Resume Layout is normal form Designer Code
    do  base.SuspendLayout()

        mogrePanel.Location <- new System.Drawing.Point(0, 0)
        mogrePanel.Name <- "mogrePanel"
        mogrePanel.Size <- new System.Drawing.Size(483, 375)
        mogrePanel.TabIndex <- 0

        base.AutoScaleDimensions <- new System.Drawing.SizeF(6.0f, 13.0f)
        base.AutoScaleMode <- System.Windows.Forms.AutoScaleMode.Font
        base.ClientSize <- new System.Drawing.Size(483, 375)
        base.Controls.Add(mogrePanel)
        base.Name <- "MogreForm"
        base.Text <- "Simple F# Mogre Form";

        base.ResumeLayout(false)

        let mogreWin = new OgreWindow(Point(100, 30), mogrePanel.Handle)
        this.Disposed.Add(fun _ -> mogreWin.Dispose())
        this.Paint.Add(fun _ -> mogreWin.Paint())

let main() =
    Application.EnableVisualStyles()
    Application.SetCompatibleTextRenderingDefault(false)
    Application.Run(new MogreForm())

[]
do main()

XNA F# Breakout Clone - Model Tutorials

2009-05-07T15:52:00.001-07:00

I'm impressed by how easy it is to use Models in XNA and because of this I'm demoting my render engine to line drawing only. Here is how I went about getting Models into my game.

First you will need software to create models and Autodesk has a free version of just that. Autodesk Softimage Mod Tool 7.5
Watch this video so you can create and export your 3D models correctly. The video series and blog post can be found here.
Third you can follow the Microsoft tutorials to get your models in game Microsoft Tutorial on displaying a 3D Model or you can continue the blog from the previous step.
Finally you will need some video tutorials on how to use Autodesk to create more complex models. XSI Video Tutorials

XNA F# Breakout Clone - Project Homepage

Breakout Clone - Added Physics Engine and Sound - F# XNA

2009-05-03T15:14:00.000-07:00

I added the Farseer Physics Engine to my game along with XNA sound effects. I'm amazed by how easy it was to use this physics engine. Collisions are handled by Delegates which you create in F# by passing a function to the delegate constructor.


ball.Geometry.OnCollision <- 
    Geom.CollisionEventHandler(
        fun geom1 geom2 contactList -> true)

My current plan is to add different shapes to the blocks, different masses, and maybe events such as an explosion.

XNA F# Breakout Clone - Project Homepage

Knockout Clone - Discriminated Unions with F#

2009-04-27T08:09:00.000-07:00

F# supports discriminated unions. This along with pattern matching makes for some short and elegant code which quite frankly is awesome. Here's a small example.


type PieceType = Breakable | Solid

member this.needsDisposing() =
    match pieceType with
        | Breakable -> (life <= 0)         
        | Solid -> false

member this.points() =
    match pieceType with
        | Breakable -> 1
        | Solid -> 0

Here I use a property of type PieceType to both define when a piece on the board needs to be removed and if the piece returns a point when it is hit. The calling class has no knowledge of this state and filters out pieces based on the returned bool flag needsDisposing() along with adding whatever is returned by points() to the total point score.

XNA F# Breakout Clone - Project Homepage

Breakout Clone - Line Segment Intersection Algorithm

2009-04-19T10:51:00.000-07:00

For my next game Breakout, I need to detect collisions for a moving object. I choose line segments to represent object borders and motion. Calculating line segment intersections is a simple and fast algorithm and there are more advanced scan line algorithms to speed it up if needed. In order to use it, I take the ball's position and old position as the line segment for the ball.

The hard part of any collision algorithm is of course dealing with the collision. Detection is always easy because it's been done before. I'm doing collision with a simple reflection of the velocity off of the line segment it's intersecting. This works great until you collide close to another line segment and you happen to reflect to the other side of it. To fix this, I made the intersection and reflection algorithm recursive. This works great except for possible race conditions. Also, you no longer have a constant speed for your ball. A quick fix for the race condition is to check to make sure you can't intersect with the same line segment twice in a row. Having the ball move a little faster is acceptable.

Project Homepage

Here's a burn test where I had set the ball to a very high speed to see if it could escape it's enclosure or enter one of the other objects. In order to make any errors apparent, I added a line trail of a random colors behind the ball. This ends up filling in all of the movable area.

I must say it's pretty cool to see the ball travel to every little nook and cranny of the board. This must be how particle chaos works. Like a fragrance filling the room.

Tetris in XNA with F#

2009-04-11T17:08:00.000-07:00

I learned a few things on this project. One is that arrays are not the end all of data structures. My first instinct from my C++ background was to make a 2D array for the tetris game board. After wasting an hour or two I realized that it was over complicated and that a Set would work really well.

Basically each piece in the game is a set of tuple points. The game board boarder is a set of tuple points and the already fallen pieces is a set of pieces. I had to keep the concept of a piece in order to keep the color associated with each tuple point. This setup made collision detection simple. It was just a matter of Seq.union_all and Set.intersect

I'm pretty amazed by the relatively few lines of code it took me to recreate the game. The main game logic is incredibly small. Most of the code is spent setting up the system and handling user input/graphics.

Project Time: 13 hours
Project - Source Code

The game is played with the DPad and A/B buttons.

Learning from the Classics

2009-03-10T14:37:00.000-07:00

So I decided while working on my platformer that I need to reduce the number of jobs I'm undertaking while I program. In order to do that I'm dropping creative director and am instead recreating classic titles. I'm still project manager since I need to manage my time and my development goal has to be playability if I'm ever going to get anything playable.

The below list contains all the 2D video game genres I can think of. I'm going to pick a game and spend a few weeks recreating it and then move on to another game in a different genre. I hope to learn the different challenges associated with each genre and what game mechanics cross genres. I have other long term goals but i'll worry more about those once I have a few games playable.

2d paddle - knockout, pong
2d shooter - galaga, zanak, space invaders
2d platformer - metroid, mario, kurby, castlevania, sonic
2d puzzle - tetris, dr. mario, generic match 3 game
2d maze - pacman, frogger
2d hack & slash - gauntlet, zelda, diablo, crono trigger
2d fighter - street fighter
2d rpg - final fantasy, dragon warrior
2d simulation - simcity, trains
2d strategy - civilization
2d rts - starcraft, red alert, dune 2, lemmings
2d racing - r.c. pro am, excite bike, mario cart
2d board game - chess, checkers, go, othello
2d projectile - gorrila, scorched earth, tank

I'm going to contenue using F# and XNA as they have served me well so far.

Added runtime fx compilation and lighting

2009-02-17T21:33:00.000-08:00

I spent some time fighting with matrices to get the lighting correct but I'm happy now that I have a rotating and moving object in XNA that is lit from a single stationary source. I'm using the plastic shader that comes with NVIDIA FX Composer 2.5.

Here's my runtime code that compiles a fx file into an Effect.


let compileEffect(fileName : string)=
   let compiledEffect =
       Effect.CompileEffectFromFile(
           fileName,
           null,
           null,
           CompilerOptions.Debug,
           TargetPlatform.Windows)
   let effectCode =
       compiledEffect.GetEffectCode()
   new Effect(
       this.graphics.GraphicsDevice,
       effectCode,
       CompilerOptions.Debug,
       null)

source code

Moving along in XNA

2009-02-14T11:03:00.000-08:00

I added a shape class and some basic shapes made out of line segments. Along with this i added collision for the line segments with a player and mapped the first controller pad to control it. Jumping is very basic and gravity is simple.

Images from the project.

source code: github.com/gradbot/xna-f-sharp

Rotating Triangle in F#

2009-01-04T13:47:00.000-08:00

For my first project in F# I ported a simple C# XNA project that draws an rotating triangle. The original C# article can be found here.

I'm using Microsoft F#, September 2008 CTP (Community Technology Preview) and Microsoft XNA 3.0 CTP

You can download the complete solution here.


#I @"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.0\References\Windows\x86";;

#r @"Microsoft.Xna.Framework.dll";;
#r @"Microsoft.Xna.Framework.Game.dll";;

open System
open System.Collections.Generic

open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Audio
open Microsoft.Xna.Framework.Content
open Microsoft.Xna.Framework.Graphics
open Microsoft.Xna.Framework.Input
open Microsoft.Xna.Framework.Storage

type MyGame = 
    inherit Game
  
    val mutable graphics : GraphicsDeviceManager
    val mutable content : ContentManager
    val mutable effect : Effect
    val mutable world : Matrix
    val mutable view : Matrix
    val mutable projection : Matrix
  
    new() as this =
        {
            graphics = null
            content = null
            effect = null
            world = Matrix.Identity
            view = Matrix.Identity
            projection = Matrix.Identity
        }
        then
            this.graphics <- new GraphicsDeviceManager(this)
            this.content <- new ContentManager(this.Services)
            this.view <- 
                Matrix.CreateLookAt(
                    new Vector3(0.0f, 0.0f, 3.0f),
                    Vector3.Zero,
                    new Vector3(0.0f, 1.0f, 0.0f))
            this.projection <- 
                Matrix.CreatePerspectiveFieldOfView(
                    MathHelper.Pi / 4.0f,
                    (float32)this.Window.ClientBounds.Height / (float32)this.Window.ClientBounds.Width * 3.0f / 2.0f,
                    0.01f,
                    1000.0f)

    override this.Initialize() =
        base.Initialize()      
       
    override this.LoadContent() = 
        this.effect <- this.content.Load("colorfill")
       
    override this.Draw(gameTime) = 
        let gd = this.graphics.GraphicsDevice
        gd.Clear(Color.Green)
       
        let vertex = [|
            new VertexPositionColor(new Vector3(-0.5f, -0.5f, 0.0f), Color.Red);
            new VertexPositionColor(new Vector3(0.0f, 0.5f, 0.0f), Color.Blue);
            new VertexPositionColor(new Vector3(0.5f, -0.5f, 0.0f), Color.Yellow);
        |]

        gd.RenderState.CullMode <- CullMode.None
        gd.VertexDeclaration <- new VertexDeclaration(gd, VertexPositionColor.VertexElements)

        this.effect.Begin()

        for pass in this.effect.CurrentTechnique.Passes do
            pass.Begin()
            gd.DrawUserPrimitives(PrimitiveType.TriangleList, vertex, 0, 1)
            pass.End()

        this.effect.End()

    override this.Update(gameTime) = 
        if (GamePad.GetState(PlayerIndex.One).Buttons.Back = ButtonState.Pressed) then
            this.Exit()

        this.world <- this.world * Matrix.CreateRotationY(MathHelper.TwoPi / 360.0f)
        this.effect.Parameters.Item("WorldViewProj").SetValue(this.world * this.view * this.projection)
        base.Update(gameTime)
      
let game = new MyGame()
game.Run()

Expert F#

2008-12-26T12:55:00.001-08:00

I recently purchased Expert F# and I'm quite satisfied with it. It goes well beyond syntax and into best practices. It also includes some excellent glue work for various targets such as web development and managed Direct X. The level of detail it goes through means a slow read and it skips over trying to teach you the basics of programming. I read it in a few days verses an afternoon which is normal for me and a technical book.

I'm interested to see if the section on decoding compiler error messages will be useful at some point. The book covers Functional, Imperative, Object Oriented, and Language Oriented programming in F#. The section on OOP was a bit short however the book mentions that this section was kept short on purpose to help you get away from pure OOP. The few mastering chapters are really good at taking F#'s syntax and clarifying how it works.

I highly recommend this book based on it being information rich and fluff free.