Tag Archives: Math

Python lambda sample usage

This will be a very brief post on the sample usage of python’s lambda function.  The following code is an identity function that will return the argument passed in. Nothing too special but it will help demonstrate the syntax. In this case I’m defining the symbol id to the lambda function.

id = lambda x: x

The following snippet contains some sample use cases of the id symbol.

print(id(2)) # prints integer 2
print(id("Hello World")) # prints string "Hello World"

Here is a code snippet that is a bit more useful. The following code is a bit hack that finds the least significant bit(LSB) in a number, meaning the lowest bit that is used to generate the given number.

lsb = lambda x: x & (-x)

As an example, passing in 8 (1000) will return 8 as the LSB. When a more complex number like 6 (0110) is passed in the LSB will be 2.

print( lsb(8) ) # prints 8
print( lsb(6) ) # prints 2

You can also nest lambda’s together in Python. The next code snippet finds the sum of two numbers.

sum = lambda x: lambda y: x+y

So, how do you define the value of y when lambda expressions only take in a single argument? Well when you define the values of x and y in the expression, you use two sets of parenthesis. Each parenthesis will pass in the argument into the targeted lambda function.

print(sum(2)(2)) # prints 4
print(sum(2)(4)) # prints 6
print(sum(2)("Hello World")) # raises type error

My last code snippet defines a symbol min as a lambda expression. Min is contains a nested lambda expression that uses a bit hack to compare two integer values.

min = lambda x: lambda y: y ^((x^y) & -(x<y))

Here is a sample use case min.

print(min(2)(4)) # prints 2
print(min(4)(2)) # prints 2

Additional Resources:
http://en.wikipedia.org/wiki/Lambda_calculus

Lecture 2A – Higher Order Procedures: Structure and Interpretation of Computer Programs
[youtube:http://www.youtube.com/watch?feature=player_embedded&v=erHp3r6PbJk%5D

Python Module Spotlight: HDF5

I wanted to try coding a python program that used a Strassen algorithm to multiply two extremely large matrices.   I my first hunch was to use numpy and after a bit of googling I found my way to this SO question.

http://stackoverflow.com/questions/3218645/handling-large-dense-matrices-in-python

People who answer their own questions are nice, but anyway this HDF5 library looks promising. I’m going to spend some time today an maybe next weekend attempting to code this.

http://alfven.org/wp/hdf5-for-python/

Low Level Bit Hacks You Absolutely Must Know – Peteris Krumins

Enjoy,

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

Introduction to Sorting Algorithms

I’ve just starting watching lectures of the Introduction to Algorithms class hosted on Harvard’s OpenCourseWare.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/

The class is taught by Erik Demaine, Ronald Rivest, and Srinivas Devadas.  Ronald was also one of the co-authors the book Introduction to Algorithms, a good book worth checking out.

I figure good place to start would be to write up a few sorting algorithms I’m already familiar with and see if I optimize them while going through the lectures.  Here are is my non-optimized Java code.

To make my life a little easier, I made an abstract class called Algorithm to hide some ugly code and make sure my sorting algorithm class just have a sort() method.

*Note: I’ve did this in a VM and I don’t have a flash drive with me at the moment. I just rewrote these objects but they may contain some typos. Later I copy and paste them here along with a few others I made.

package algorithms;

public abstract class Algorithm(){
    public int[] arr;
    public int count = 0;

    public Algorithm(int[] arr){
        this.arr = arr;
        long start = System.nanoTime();

        printTestingWelcomeMessage();
        printArrType();
        print();
        printTestingLineSepartor();

        long nanoTime = (System.nanoTime() - start);

        // There is a loss of precision when converting to microseconds but,
        // it's hard to cry over the loss of a faction of a mircosecond.
        System.out.println("Time: "
            + (nanoTime / 1000) + " microseconds || "
            + nanoTime + " nanoseconds || "
            + (nanoTime * (Math.pow(10,-6)) + " milliseconds"
        );

        System.out.println("Moves: " ( (count != 0) ? count : "?") );
    }
    protected abstract void sort();
    protected abstract void printTestingWelcomeMessage();

    public int[] get(){ return(arr); }

    public void swap(int x, int y){
        int temp = arr[x];
        arr[x] = arr[y]
        arr[y] = temp;
        count++;
    }

    public void print(){
        System.out.println("[");
        for(int i = 0; i < arr.length; i++)
            if(i <= arr.length)
                System.out.print(arr[i]+ ", ");
            else if( i == (arr.length -1) )
                System.out.println(arr[i]+"]\n");
    
    private void printArrType(){
        if(arr.length > 1)
            System.out.println( (arr[0] - arr[1] == 1) ? ("Inverse Sequence Matrix") : ("Random Values Matrix") );
        else
            System.err.println("Single Value Matrix");
    }

    private void printTestingLineSepartor(){
        System.out.println("________________________");
    }
}

Now that’s out of the way lets get to the fun part. I wrote most of these algorithms with help from WikiBook’s Sorting Algorithm page. If you want any more additional information about these algorithms, check out Wikipedia, cool things can be found there.

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting

First up, the classic and extremely inefficient, bubble sort algorithm.

package algorithms;

public BubbleSort extends Algorithm{

    public BubbleSort(int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Bubble Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        int i = 0;

       while( i < (arr.length - 1))             if( arr[i] > arr[i+1]){
                swap(i,i+1);
                i=0;
            }
            else
                i++

    }
}

I’ve found another way to code a heap sort in java so I’ve made a class for each version. The first up is using priority queue and I really like this version for the lite coding and speed.

package algorithms;

public PriorityQueHeapSort extends Algorithm{

    public PriorityQueHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Priority Queue Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
         PriorityQueue heap = new PriorityQueue(arr.length);

        for(int elem : arr)
            heap.add(elem);

        for(int i; i < arr.length; i++)
            arr[i] = heap.remove();
    }
}

Sadly, this version is a tad bit too slow for my tastes so I’ve made another heap sort using the in-place method. You are about too see why I liked the priority queue version. I didn’t bother cleaning up the source code much. The code one big iteration loop with nested if statements that work off the branches.

package algorithms;

public InPlaceHeapSort extends Algorithm{

    public InPlaceHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting In-Place Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        for(int i = 0; i < arr.length; i++){             while( i > 0 ){
                int p = (i-1)/2;

                if(arr[i] > arr[p])
                    swap(i,p);
                else
                    break;
            }
        }

        for(int i= arr.length; i > 0;){
            swap(0,--i);

            int n = 0;

            while(true){
                int left = (n*2) + 1;

                if(left >= i)
                    break;

                int right = left+1;

                if(right >=i){
                    if(arr[left] > arr[n])
                        swap(left,n);
                    break;
                }

                if(arr[left] > arr[n])
                    if(arr[left] > arr[right]){
                        swap(left,n);
                        n = left;
                        continue;
                    }
                    else{
                        swap(right, n);
                        n = right;
                        continue;
                    }
                else
                    if(arr[right] > arr[n]){
                        swap(right, n);
                        n = right;
                        continue;
                    }
                    else
                        break;
            }
        }
    }
}

Next algorithm up is quick sort. Like the namesake it’s a pretty quick sorting algorithm. Other sorting algorithms that are faster exists but this one gets the most attention.

public QuickSort extends Algorithm{

    public QuickSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Quick Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        divideAndConquer(0, (arr.length -1));
    }

    private void divideAndConquer(int low, int high){
        int x = low;
        int y = high;
        int pivot = arr[low+ (high-low)/2];

        while(x < y){
            while(arr[x] < pivot)                 x++;             while(arr[y] > pivot)
                y++;

            if( x                 swap(x,y)
                x++;
                y--;
            }
        }

        if(low < y)
            divideAndConquer(low, y);

        else if(x < high)
            divideAndConquer(x, high);
    }
}

For completion sake I included my test harness. I used two different types of matrices. One matrix I used was an array arrange with a inverse sequence, the bubble sort’s worst nightmare.

[5,4,3,2,1]

Along with an array filled with random integers.

public class Run{
    int[] arrInverse;
    int[] arrRandom;
    Random rand;

    public Run(int MAX){
        rand = new Random();
        arrInverse = new int[MAX];
        arrRandom = new int[MAX];

        for(int i = 0; i < arrInverse.length; i++)
            arrInverse[i] = (arrInverse.length - i);

        for(int i = 0; i < arrRandom.length; i++)
            arrRandom[i] = (arrRandom.length - i);
    }
   // I've omitted my other methods but they are all set up the same.
   public void testBubbleSort(){
       new BubbleSort(arrInverse);
       new BuubleSort(arrRandom);
   }

   public void testQuickSort(){
       new QuickSort(arrInverse);
       new QuickSort(arrRandom);
   }
}

Reworked Sierpinski Triangle JavaScript

I’m just about done reworking the recursive function to plot the mid points of a triangle and create nested triangles within it. I still have to tweak it a bit because I want the middle triangle to be the color of the canvas. Not entirely sure how to do that yet but I’ll update this post when I figure it out.

Also this was a pretty good read:
http://sixrevisions.com/html/canvas-element/
Continue reading

Sierpinski Triangle in JApplet

I made this simple Sierpinski triangle JApplet for a demonstration of a recursive function for my Programming Logic cheat sheet.
Continue reading

Binary Heap in Java

I’ve found code for making a binary heap based off an array list. It seemed like a neat way to code for a simple heap but I would still preferred to stick with binary trees.  Anyway, I stumbled upon this link while browsing the binary heap wikipedia page.

http://en.wikipedia.org/wiki/Binary_heap

https://sites.google.com/site/indy256/algo-en/binary_heap
Continue reading

A Moore Machine

I think someone found my blog today by Googling for a Moore machine example in C#, lol.  I will admit a Moore machine is the best kind of machine, no offense Turing and f%*k Mealy.  As for explanation of what’s a Moore machine your SOL, even I don’t have the time or energy to try present this one but here are few resources to get you going.

Continue reading

Tactics Sharp Quick Grid Redesign

I spent about a hour redesigning the grid class and here is what I got so far. I didn’t even try compiling it yet so reader be ware.
Continue reading

Lambda Expressions && Dictionaries && Arrays

I’ve worked on the grid class of Tactics Sharp a little bit. Here is the source, it’s still incomplete. Also here is a good MSDN article on Lambda Expressions in C#. http://blogs.msdn.com/b/ericwhite/archive/2006/10/03/lambda-expressions.aspx

Grid class source

using System;
using System.Collections.Generic;
/*
    Note this is still under development, contains errors and missing functions.
 */
namespace Tactics_Sharp {
    internal class Grid {
        // Grid pointer object
        public class Point{
            private Int32 _row, _col; 
            public Point()                       { this._row = -1; this._col = -1; }      
            public Point(Int32 _row, Int32 _col) { this._row = _row; this._col = _col; }  
            public void setRow(Int32 _row)       { this._row = _row; }  
            public void setCol(Int32 _col)       { this._col = _col; }
            public Int32 getRow()                { return this._row; }
            public Int32 getCol()                { return this._col; }
        }

        private Int32   MAX_ROW, MAX_COL;
        private Int32[] _arr;
        private Point _ptr;

        public Grid() { this._arr = null; this.MAX_ROW = -1; this.MAX_COL = -1; }
        public virtual void init(Int32 _row, Int32 _col) {
            this.MAX_ROW = _row; this.MAX_COL = _col;
            this._arr = new Int32[this.MAX_ROW * this.MAX_COL];
            this._ptr = new Point();
        }
        public virtual Int32 getMAX_ROW() { return this.MAX_ROW; }
        public virtual Int32 getMAX_COL() { return this.MAX_COL; }

        //ToDo: Make tenary check
        public virtual void movePointer(Int32 row, Int32 col) { this._ptr.setRow(row); this._ptr.setCol(col); }
        public virtual Int32 getValue() {
            if( (this._ptr.getRow() >= 0 && this._ptr.getCol() >= 0) || (this._ptr.getRow() < this.MAX_ROW && this._ptr.getCol() < this.MAX_COL) )
                return this._arr[this._ptr.getRow() * this.MAX_COL + this._ptr.getCol()]; 
            else
                return -1; // !Error
        }
        public virtual void setValue(Int32 _val) {
            if ( (this._ptr.getRow() >= 0 && this._ptr.getCol() >= 0) || (this._ptr.getRow() < this.MAX_ROW && this._ptr.getCol() < this.MAX_COL) )
                if ( _val >= 0 && _val < this.MAX_ROW && _val < this.MAX_ROW )
                    this._arr[this._ptr.getRow() * this.MAX_COL + this._ptr.getCol()] = _val;            
        }
        public virtual void print() {
            Console.WriteLine("Multi-Array Contents");
            for(int _row = 0; _row < this.MAX_ROW; _row++) {
                Console.WriteLine();
                for(int _col = 0; _col < this.MAX_COL; _col++)
                    Console.Write(this._arr[_row * this.MAX_COL + _col]);
            }
            Console.WriteLine();
        }
    }

    internal sealed class GameBoard : Grid {
        /*
            Some of you might have a few questions about the dictionary object occupants, like why need array if 
            you can have a dictionary of characters and points.  Couldn't you just use the point objects to keep  
            track and manipulate the character's position.  Yeah, probably but where's the point in that.
         */
        public Dictionary<Character, Point> occupants = new Dictionary<Character,Point>();
        public GameBoard(Int32 _row, Int32 _col) { base.init(_row, _col); }

        public override void movePointer(Int32 _row, Int32 _col) { base.movePointer(_row, _col); }
        public override void setValue(int _val)                  { base.setValue(_val); }
        public override Int32 getValue()                         { return base.getValue(); }
        public void add(Character _char)                         { this.occupants.Add( _char, new Point() ); }
        public void add(Character _char, Int32 _row, Int32 _col) {
            if ((_row >= 0 && _col >= 0) || (_row < base.getMAX_ROW() && _col < base.getMAX_COL()))
                this.occupants.Add(_char, new Point(_row, _col));
            else
                this.occupants.Add(_char, new Point(_row, _col)); 
        }
       
        public void populate() {
            foreach (Character _char in this.occupants.Keys){
                base.movePointer(this.occupants[_char].getRow(), this.occupants[_char].getCol() );
                base.setValue(_char._ID);
            }
        }

        public void test() {
            base.print();
            foreach( Character var in this.occupants.Keys )
                Console.WriteLine(var.getName() +" @ [" + occupants[var].getRow() + "," + occupants[var].getCol() +"]" );
        }
             
    }
}

Character class, only added an id value.

using System;
using System.Collections.Generic;

namespace Tactics_Sharp {
    internal class Character : IComparable {

        [Flags] //-State of character.
        public enum CharState { Normal = 0x0, Death = 0x1, Asleep = 0x2, Burn = 0x4, Frozen = 0x8, Paralyze = 0x10, Poison = 0x20, Confuse = 0x40 }

        // - Character's Vitals && Skills
        private Dictionary<String, Int32> _skills;
        private Dictionary<String, Int32> _vitals;
        private CharState _state;
        public String _name;
        public Int32 _ID;

        public Character() {
            this._state = CharState.Normal;
            this._skills = new Dictionary<String, Int32>() { 
                { "Punch", 0 }, { "Weapon", 0 }, { "Evade", 0}, { "Steal", 0 }, 
                { "Block", 0 }, { "Fire", 0 }, { "Lighting", 0 }, { "Heal", 0 },  
                { "Bite", 0 }, { "Claw", 0 } };
            this._vitals = new Dictionary<String, Int32>() { { "HP", 0 }, { "MP", 0 }, { "LVL", 0 } };
            this._ID = -1;
        }

        // - Virtual Derived Classes
        public virtual Int32                     CompareTo(Object _obj) { return this.CompareTo(_obj); }
        public virtual String                    getName() { return this._name;  }
        public virtual void                      setName(String _name) { this._name = _name; }
        public virtual Dictionary<String, Int32> getVitals() { return this._vitals; }
        public virtual Dictionary<String, Int32> getSkills() { return this._skills; }
        public virtual void                      incrementSkill(String key) { this._skills[key]++; }
        public virtual void                      incrementVitals(String key) { this._vitals[key]++; }
        public virtual Int32                     indexSkill(String key) { return this._skills[key]; }
        public virtual Int32                     indexVital(String key) { return this._vitals[key]; }
        public virtual CharState                 getState() { return this._state; }

        public virtual void setSkill(String key, Int32 val) {
            if (val >= 0 && val <= 100)
                this._skills[key] = val;
        }
        public virtual void setVital(String key, Int32 val) {
            if (val >= 0)
                this._vitals[key] = val;
        }
        public virtual void setState(CharState _state) {
            if (_state != (this._state & _state))  // - Checks if class is deactive  
                this._state = this._state | _state;  // - Adds state
        }
        public virtual void removeState(CharState _state) {
            if (_state == (this._state & _state))   // - Checks if class is active
                this._state = this._state ^ _state; // - Removes state
        }

        // Human Character Class
        internal sealed class Human : Character, IComparable {
            [Flags]
            public enum CharClass { Squire = 0x0, Knight = 0x1, Monk = 0x2, Mage = 0x4, Archer = 0x8, Theif = 0x10 }
            public CharClass _class;
            public Human(String _name, Int32 _ID) { base._name = _name; base._ID = _ID; this._class = new CharClass(); }

            // Locals Functions
            public void promote(CharClass _class) {
                if (_class != (this._class & _class))    // - Checks if class is deactive 
                    this._class = this._class | _class;  // - Adds class
            }
            public void demote(CharClass _class) {
                if (_class == (this._class & _class))   // - Checks if class is active
                    this._class = this._class ^ _class; // - Removes class
            }

            // Base Class Functions
            public override Int32 CompareTo(Object _obj) { return base.CompareTo(_obj); }
            public override string getName() { return base.getName(); }
            public override Dictionary<String, Int32> getSkills() { return base.getSkills(); }
            public override Dictionary<String, Int32> getVitals() { return base.getVitals(); }
            public override void incrementSkill(String key) { base.incrementSkill(key); }
            public override void incrementVitals(String key) { base.incrementVitals(key); }
            public override Int32 indexSkill(String key) { return base.indexSkill(key); }
            public override Int32 indexVital(String key) { return base.indexVital(key); }
            public override void setSkill(String key, Int32 val) { base.setSkill(key, val); }
            public override void setVital(String key, Int32 val) { base.setVital(key, val); }
        }

        // Dragon Character Class
        internal sealed class Dragon : Character, IComparable {
            [Flags]
            public enum CharClass { Brainfuck = 0x0, Packrat = 0x1, ANTLR = 0x2, PLY = 0x4, SWIG = 0x8 }
            public CharClass _class;

            public Dragon(String _name, Int32 _ID) { base._name = _name; base._ID = _ID; this._class = new CharClass(); }

            // Locals Functions
            public void promote(CharClass _class) {
                if (_class != (this._class & _class))      // - Checks if class is deactive 
                    this._class = this._class | _class; }  // - Adds class
            
            public void demote(CharClass _class) {
                if (_class == (this._class & _class))      // - Checks if class is active
                    this._class = this._class ^ _class; }  // - Removes class
            
            // Base Class Functions
            public override Int32                     CompareTo(Object _obj) { return base.CompareTo(_obj); }
            public override string                    getName() { return base.getName(); }
            public override Dictionary<String, Int32> getSkills() { return base.getSkills(); }
            public override Dictionary<String, Int32> getVitals() { return base.getVitals(); }
            public override void                      incrementSkill(String key) { base.incrementSkill(key); }
            public override void                      incrementVitals(String key) { base.incrementVitals(key); }
            public override Int32                     indexSkill(String key) { return base.indexSkill(key); }
            public override Int32                     indexVital(String key) { return base.indexVital(key); }
            public override void                      setSkill(String key, Int32 val) { base.setSkill(key, val); }
            public override void                      setVital(String key, Int32 val) { base.setVital(key, val); }
        }
    }
}

Test class with a lambda expression:

using System;
using System.Collections.Generic;

namespace Tactics_Sharp {
    class Run {
        public delegate void StandardOutput();

        static void Main(string[] args) {
            GameBoard board = new GameBoard(5, 5);
            Character.Human Bit = new Character.Human("Bit Diddler", 1);
            Character.Dragon Aho = new Character.Dragon("Aho", 9);

            StandardOutput SO = () => {
                board.add(Bit, 0, 0);
                board.add(Aho, 0, 1);
                board.populate();
                board.test();
                Console.ReadLine();
            };
            SO();
        }
    }
}

Tactics Sharp – Character Design Update

Still haven’t figured out how to get dictionary iteration working smoothly yet but here is the source code. I added back the character classes and state enums. I’m skipping the dictionary issues for now and moving on. Next I’m either going back to the grid to track and move around the characters or start working out attacking events. Also I’ll try to throw in a lambda function where I can.
Continue reading

Tactics Sharp – Character Design

Just spent around 45 minutes playing around with some code.  Here is what I came up with, Bit Diddler would be proud.

Continue reading

Hex to Binary via the Nibble Method

Here a quick way to preform base conversions between binary and hexadecimal.
Continue reading

Statistics Made Accessible – R

R is a GNU alternative to Stephen Wolfram’s Mathematica.

Continue reading

Coding A Fibonacci Sequence

Here is something for the fans of the television show Touch.

def foo(first, second, position):
if(position == 1):
return (first);
elif(position == 2):
return (second);
else:
return (foo(first,second, position-1) + foo(first,second,position - 2));
print(foo(3,9,10))