Product Array - Interview Question

Friday, December 17, 2010 by gradbot

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

Thursday, December 16, 2010 by gradbot

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

Wednesday, July 7, 2010 by gradbot

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);
    }
};

Filed under , , , having 2 comments  

Cartesian Tree Sort - Skew Heap

Monday, June 28, 2010 by gradbot

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);
    }
};

Filed under , , , having 0 comments  

Cartesian Tree Sort - Revisited

Friday, June 25, 2010 by gradbot

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);
    }
};

Filed under , , , having 0 comments  

Cartesian Tree Sort

Thursday, June 24, 2010 by gradbot

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);
        }
    }
};

Filed under , , , having 0 comments  

Insertion Sort

Monday, June 21, 2010 by gradbot

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);
    }
};

Filed under , , , having 0 comments  

Priority Queue & Heap Sort

Thursday, June 10, 2010 by gradbot

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();
    }   
};

Filed under , , , having 0 comments  

Heap Sort

Wednesday, June 9, 2010 by gradbot

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);    
    }
};

Filed under , , , having 0 comments  

Selection Sort

Tuesday, June 8, 2010 by gradbot

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);  
    }
};

Filed under , , , having 0 comments  

Quick Sort

Friday, June 4, 2010 by gradbot

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);
};

Filed under , , , having 0 comments  

Gnome Sort

Thursday, June 3, 2010 by gradbot

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++;
        }
    }
};

Filed under , , , having 0 comments  

Comb Sort

Wednesday, June 2, 2010 by gradbot

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;
}
}
}
};


Filed under , , , having 0 comments  

Odd-even Sort

Tuesday, June 1, 2010 by gradbot

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;
}
}
}
};


Filed under , , , having 0 comments  

Cocktail Sort

Monday, May 31, 2010 by gradbot

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;
}
}
}
};


Filed under , , , having 0 comments  

Bubble Sort

by gradbot

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;
}
}
}
};


Filed under , , , having 0 comments  

Pi Day

Sunday, March 14, 2010 by gradbot

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]

Filed under , , having 0 comments  

Moving on with F# Development

Sunday, January 17, 2010 by gradbot

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()

Filed under , having 0 comments