Meandering Thought

I have recently been reading the book Game Theory and Strategy by Phillip Straffin.  It was suggested to me by my mathematics teacher Patroklos Benatos.  He suggested I read this book for an introduction to the study of Game Theory.  It has been excellent reading and inspired me to develop an application that aids one in finding a solution to a zero sum game matrix.       So lets take a look at the code.  The constructor of the application sets up some TextFields that will be used throughout the calculation of the matrix game solution.   These text fields will be filled with the cells of the matrix that hold the largest column entry, the smallest row entry, and any saddle points present in the matrix.  A for() loop ( Line 45 ) is used to generate random entries in the cells of the matrix such that  -10< n < 10 where n is the payoff of that cell.  I chose a 4x4 matrix for the size of this matrix.  I am planning to allow the user to alter the mxn dimensions in a future iteration of this application, but for now the size of the generated matrix is static.  After generating  the payoffs for the 16 cells of the matrix at random the code runs the function checkForSaddlePoints().     

The first thing performed in the execution of checkForSaddlePoints()  is the TextFields ( Line 99 ) that identify the Greatest Column Payoffs , the Least Row Payoffs, and the Saddle Points are restored to their original forms.  At this point the TextFields do not identify any entries in the matrix.  As the loops and calculations ahead in the code execute.  The for() loop ( line 110 ) begins by extracting each key from the Dictionary object.  

Each key object is a TextField which was stored in the Dictionary ( line 65 ).   The object at d[ key ] stores the column and row index for this TextField.  Now that the code has identified one TextField, its column index, and its row index, its time to start storing and the largest column and least row entries in the matrix.  The aColumn array is used to keep track of which columns have been already checked for their largest entries.  The aRow Array is used to keep track of which rows have been already  checked for their least entries. If for example a certain column has not been checked for its largest entry the code inside the if( aColumn[c] != true ) will execute ( line 120 ), in turn running the method findGreatestEntryInColumn() which evaluates every entry in this particular column c.  After identifying this entry in said column, it will be differentiated by coloring its text red.  Its entry information will also be stored on greatestColumns Array for later use when checking for the existence of saddle points.  The evaluation of if( aRow[r] != true ) works in exactly the same way ( line 132 ). After this evaluation is complete, the code can then determine if a saddle point is present in the matrix by checking if any of the Greatest Column entries coincide the with Least Row entries. ( line 150 ).  

    And here is the code that make this whole thing work ::  

 
/**
 * This class is the controlling entity of Game Theory Matrix Solver
 *
 * Copyright (c) 2008 Gregory Sogorka.
 */
package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.text.TextField;
	import flash.text.TextFieldType;
	import flash.utils.Dictionary;
 
	public class Gametheory_Experiment extends Sprite
	{
		private var d 					: Dictionary;
		private var columnAlert 		: TextField;
		private var rowAlert 			: TextField;
		private var saddlePointAlert 	: TextField;
		private var totalColumns		: int;
		private var totalRows			: int;
		private var xPos				: int = 100;
 
		public function Gametheory_Experiment()
		{
			d = new Dictionary();
 
			columnAlert 		= new TextField();
			columnAlert.x 		= xPos;
			columnAlert.y 		= 20;
			columnAlert.width 	= 350;
			addChild( columnAlert );
 
			rowAlert = new TextField();
			rowAlert.x = xPos;
			rowAlert.y = 40;
			rowAlert.width = 350;
			addChild( rowAlert );
 
			saddlePointAlert = new TextField();
			saddlePointAlert.x = xPos;
			saddlePointAlert.y = 60;
			saddlePointAlert.width = 350;
			addChild( saddlePointAlert );
 
			for( var i : int = 0; i<4; i++ ){
 
				for( var j : int = 0; j<4; j++ ){
 
					var t 	: TextField = new TextField();
					var num : Number 	= Math.floor( Math.random() * 10 );
					t.text 				= ( Math.random() > .5 )?String(num):String(-1*num);
					t.border 			= true;
					t.borderColor 		= 0x00000000;
					addChild( t );
 
					t.x = j*20.5;
					t.y = i*20.5;
					t.width = 20;
					t.height = 20;
					t.type = TextFieldType.INPUT;
					t.addEventListener( Event.CHANGE, textChange );
 
					d[t]=	{ row : i, column : j };
 
				}
			}
 
			totalColumns = j;
			totalRows = i;
 
			checkForSaddlePoints();
 
		}
 
		private function textChange( e : Event ) : void
		{
			checkForSaddlePoints();
		}
 
		private function getAllValuesInColumn( i : int ) : Array {
 
			var a : Array= new Array();
			for( var key : Object in d ) {
				if( d[key]["column"] == i ) a.push( { column : d[key]["column"], row : d[key]["row"], value : TextField( key ).text } ); 
 
			}
 
			return a;
		}
		private function checkForSaddlePoints() : void {
 
			columnAlert.htmlText 			= "<font size='8' color='#ff0000'>Greatest Column Entry</font> at : ";
			rowAlert.htmlText 				= "<font size='8' color='#0000ff'>Least Row Entry</font> at : ";
			saddlePointAlert.htmlText 		= "<font size='8' color='#A2627A'>Saddle Points</font> at : ";
			resetTextFieldColors();
 
			var aColumn 		: Array = new Array();
			var aRow 			: Array = new Array();		
 
			var greatestColumns : Array = new Array();
			var lowestRows		: Array = new Array();
 
			for( var key : Object in d )
			{
				//key is a textfield;
				//c is TextField( key ) column index;
				//r is TextField( key ) row index;
				var c : Number 		= d[key]["column"];
				var r : Number 		= d[key]["row"];
				var t : TextField 	= TextField( key );
 
				//If we've not encountered this column before lets decide what its greatest entry is an object holding that info to o
				if( aColumn[c] != true )
				{
					var o : Object    = findGreatestEntryInColumn( c, t );
					//Change the color of the largest column entry
					getTextFieldByCoordinate( o["row"], o["column"] ).textColor = 0xffff0000;
					columnAlert.htmlText += "<font size='8'> ["+o["row"]+" , "+o["column"] +"] </font>"
					//So further interations of our for() loop don't reevaluate this column
					aColumn[c] = true;
					greatestColumns.push( o );
				}
 
				//If we've not encountered this row before lets decide what its least entry is an object holding that info to or
				if( aRow[r] != true )
				{
					var or : Object = findLowestEntryInRow( r, t );
					//Change the color of the lowest row entry cell.
					getTextFieldByCoordinate( or["row"], or["column"] ).textColor = 0xff0000ff;
					rowAlert.htmlText += "<font size='8'> ["+or["row"]+" , "+or["column"] +"] </font>";
 
					aRow[r] = true;
					lowestRows.push( or );
				}
 
			}
 
		// Basically the dimensions of our MxN matrix
		var cLength : int = greatestColumns.length;
		var rLength : int = lowestRows.length;
 
		for( var i : Number =0;i< cLength; i++ ){
			var oCol : Object = greatestColumns[i];
 
			for( var j : Number=0; j< lowestRows.length; j++ )
			{
				var oRow : Object = lowestRows[j];
				//Check if the greatest column entry is the same as any of the least row entries
				if( oCol["row"] == oRow["row"] && oCol["column"] == oRow["column"] )
				{
					//
					saddlePointAlert.htmlText += "<font size='8'> ["+oCol["row"]+" , "+oCol["column"]+"] </font>";
					//Change the color of the saddle point cell to purple
					getTextFieldByCoordinate( oCol["row"],oCol["column"]).textColor= 0xffA2627A;
				}
			}
		}
 
	}
 
		private function findLowestEntryInRow( row : Number, changed : TextField ) : Object {
 
			var o : Object = { column : d[changed]["column"], row : d[changed]["row"] };
 
			var least : Number= Number( changed.text );
 
			for( var key : Object in d ) {
 
				if( d[key]["row"] == row ) {
					var t : TextField 	= TextField( key );
					var n : Number		= Number( t.text );
 
					if( n < least ){
						least = n;
						o=  { row : d[key]["row"], column : d[key]["column"] };
					}
				}
			}
 
			return o;
 
		}
 
		private function findGreatestEntryInColumn( col : Number, changed : TextField ) : Object
		{
			var o 			: Object = { column : d[changed]["column"], row : d[changed]["row"] };
			var greatest 	: Number = Number( changed.text );
 
			for( var key : Object in d ) {
 
				if( d[key]["column"] == col ) {
 
					var t : TextField = TextField( key );
					var n : Number = Number( t.text );
 
					if( n > greatest ){
						greatest = n;
						o = { column : d[key]["column"], row : d[key]["row"] };
					}
				}
			}
 
			return o;
		}
 
		private function getTextFieldByCoordinate( row : int, column : int ) : TextField {
 
			var t : TextField;
 
			for( var key : Object in d ) {
				if( d[key]["column"] == column && d[key]["row"] == row ) t= TextField( key );
			}
 
			return t;
 
		}
 
		private function resetTextFieldColors() : void {
			for( var key : Object in d ) {
				TextField( key ).textColor =0;
 
			}
		}
 
	}
 
	}
 

  Here is a link to the source code.   Feel free to send me any comments, suggestions, or optimizations for this code.   Source 

I've been working with the Flare visualization libraries a bunch lately and found myself wanting to use new shapes to represent nodes of a graph.  With a little research I found its possible to implement the IRenderer interface and set a custom renderer for each node.  This is a pretty simple implementation, but from it I think one can see the possibilities for more complex shapes / colors in data representations.  The following is the client code that sets up the graph and visits each node setting its renderer property ::

 
package {
 
	import com.extralongfingers.graphs.client.render.RoundBlockRenderer;
	import com.extralongfingers.graphs.client.utils.GraphUtil;
 
	import flare.animate.Transitioner;
	import flare.vis.Visualization;
	import flare.vis.data.NodeSprite;
	import flare.vis.data.Tree;
	import flare.vis.operator.layout.TreeMapLayout;
 
	import flash.display.Sprite;
	import flash.geom.Rectangle;
 
	public class Flare_RoundedBlockShapeRenderer extends Sprite
	{
		public function Flare_RoundedBlockShapeRenderer()
		{
			_init();
		}
 
		private function _init() : void
		{
			var t 		: Tree 			= GraphUtil.balancedTree(12,1);
			var vis 	: Visualization = new Visualization( t );
			vis.bounds 					= new Rectangle(0,0,250,250);
 
			vis.data.nodes.visit( _nodeVisit );
 
			var _tml 	: TreeMapLayout = new TreeMapLayout( "size" );
			vis.operators.add( _tml );
			addChild( vis );
			vis.update( new Transitioner(2) ).play();
 
		}
 
		private function _nodeVisit( n : NodeSprite ) : void
		{
			n.renderer 	= RoundBlockRenderer.instance;
			n.shape		= RoundBlockRenderer.ROUNDED_BLOCK;
			n.fillColor = Math.random() * 0xffffffff;
			n.size 		= Math.random();
		}
	}
}
 

And here is my implementation of a custom Renderer called RoundedBlockRenderer that draws a block for the TreeMapLayout with rounded corners instead of 90 degree angle corners.

 
 
package com.extralongfingers.graphs.client.render
{
	import flare.vis.data.DataSprite;
	import flare.vis.data.render.IRenderer;
 
	import flash.display.GradientType;
	import flash.display.Graphics;
	import flash.geom.Matrix;
 
	public class RoundBlockRenderer implements IRenderer
	{
 
		public static const ROUNDED_BLOCK : String = "roundedblock";
 
		private static var _instance:RoundBlockRenderer = new RoundBlockRenderer();
 
		public var _defaultSize:Number;
 
		public static function get instance():RoundBlockRenderer { return _instance; }
 
		public function RoundBlockRenderer(defaultSize : Number = 6)
		{
			this._defaultSize = defaultSize;
		}
 
		public function render(d:DataSprite):void
		{
			var size:Number = d.size * _defaultSize;
			var g : Graphics = d.graphics;
			g.clear();
			var _n : Number = Math.random();
			g.beginGradientFill( 	GradientType.LINEAR,
									[ 0xffffffff* _n,0xaaaaaaaa* _n, 0x8c8c8cff* _n, 0x000000 ],
									[ .8, .8, .8, .8 ],
									[ 0,96, 128, 180 ],
									new Matrix()
								);
 
			switch( d.shape ) {
 
				case ROUNDED_BLOCK:
					g.drawRoundRect(d.u-d.x, d.v-d.y, d.w, d.h, 8, 8);
				break;
			}
 
		}
 
	}
}
 

Source Code ::Rounded Block Renderer Source.

And yet another visualization of an actionscript code framework :: PureMVC :: 

Here's another visualization of an actionscript framework. This time its the very simple Adobe Cairngorm framework.  I also tried out using the Transitioner Class from the Flare framework to straighten the edges of the graph when the visualization loads.  

Here is another visualization much like the Papervision 3d visualization in the previous post.  I'm going to keep posting these code visualizations for actionscript libraries in the coming days as I get more time. 

So I've become quite interested in the Flare actionscript library for graphing and started playing around with it this weekend.  Using the example given here ::: Flare Dependency Graph , I wrote some perl that parses an actionscript source tree and creates a JSON file suitable for import into the Flare libraries.  So here is what Papervision looks like when graphed using Flare ::: 

I've been playing around with recursive functions in actionscript for a bit now and yesterday came across this pretty cool one for reversing a string.  The code follows :  

 
function Reverse(s : String ) :  String {
	var tmp : String = null;
 
   if ( s.length == 1 )  return s;
   else
   {
	   var sLast 		: String = s.substr( s.length -1, s.length );
	   var sRemainder 	: String = s.substr( 0, s.length -1 );
	  tmp = sLast + Reverse( sRemainder );
	  return tmp;
   }
}
 
var str : String = "abcdef";
trace( Reverse( str ) );
 

This little diagram I drew out helped me understand what the execution stack looked like :   

After reading the book Code Generation in Action I found I was in need of an simple and easy way to roll out Flex project foundations.  I create a script that works with a set of template files to build the standard project directory structure, a set of specified views, and a set of basic commands that add the views to a canvas and init the application.  The following shows the command line invocation of the perl that creates a Flex project with 5 separate views :

# ./generate.pl  usage : generate.pl domain applicationName view1 view2 .. view98 view99

# ./generate.pl extralongfingers mynewapplication helpbutton startbutton stopbutton extralongfingersbutton holymountbutton 

After that runs we have a set of directories that looks like this :

    Each view specified on the command line created a mxml file in the root directory of the namespace and a corresponding controller in the com.extralongfingers.mynewapplication.client.controllers directory.  If you run the script you will see that each mxml view registers itself with the controller that shares its name.  The script also creates an application mxml file call Mynewapplication.mxml in the root of the directory structure. This mxml application serves as the entry point for the app and proceeds to run the BuildViews Command upon initialization wherein all the mxml views are instantiated and proceed to link up with their controllers.  I'm planning to clean up this perl a bit in order to modularize things a bit more and hope to submit to cpan soon.  Let me know what you think and if you found this useful.  I've been doing a lot with code generation lately so come back soon for my AMF PHP remoting gateway generator.         Flex Generation Framework Source

I always found the MovieClipHelper.as of the Pixlib framework useful for rolling out applications in a quick and straightforward manner.  Although the newest iteration of the framework  LowRA is a useful and powerful xml driven environment to roll out RIAs, I still find the need for a manager to hold references to all my views.  The power of a centralized repository of all views and standard methods for x, y manipulation is great to have around for any project.  I've also been looking through the Vegas framework and was unable to find a View Management tool along the same lines.  So I decided to roll my own using Pixlib as a basis and Vegas as my environment.   This little class does most of the things you'll find in the Pixlib version like holding all view references in a hash map.  This design principle makes managing views incredibly easy.  By just defining a single enum file of static strings, you can uniquely name all the views of your application and then subsequently access those views from anywhere in the application.  I find this useful when managing sizing and positioning of multiple views that are dependent upon one another.  So herein follows a quick and dirty ViewManager designed for Sprites in AS3. 

 
package com.extralongfingers.definitionalliterature.client.util
{
	import flash.display.DisplayObject;
 
	import vegas.data.map.HashMap;
 
	import flash.geom.Point;
	import flash.events.EventDispatcher;
	import flash.display.Sprite;
 
	/**
	 * @author Gregory Sogorka
	 */
	public class ViewHelper
	{
		public var view 			: Sprite;
		public var _dispatcher  	: EventDispatcher = new EventDispatcher();
		private static var _a 		: HashMap = new HashMap();
		private var _sName			: String;
 
		function ViewHelper( s : String, spr : Sprite )
		{
			if( spr == null ) trace( " You must pass a Sprite to the constructor.");
 
			else
			{
				view = spr;
				_setName( s );
			}
		}
 
		public function setVisible( b : Boolean ) : void
		{
			if ( b )
			{
				show();
			}
			else
			{
				hide();
			}
		}
 
		public function hide() : void
		{
			view.visible = false;
		}
 
		public function show() : void
		{
			view.visible = true;
		}
 
		public function move( x : Number, y : Number ) : void
		{
			view.x = x;
			view.y = y;
		}
 
		public function getPosition() : Point
		{
			return new Point( view.x, view.y );
		}
 
		public function setSize( w : Number, h : Number ) : void
		{
			view.width = w;
			view.height = h;
		}
 
		public function getSize() : Point
		{
			return new Point( view.width, view.height );
		}
 
		public function getName() : String
		{
			return _sName;
		}
 
		public function release() : void
		{
			ViewHelper._unregister( _sName );
			_sName = null;
		}	
 
		public function isVisible() : Boolean
		{
			return view.visible;
		}
 
		public static function getMovieClipHelper( sName:String ) : ViewHelper
		{
			if (!ViewHelper._a.containsKey( sName ) )
			{
				trace( "Can't find ViewHelper instance with '" + sName + "' name." );
			}
			return _a.get( sName );
		}
 
		public static function isRegistered( sName:String ) : Boolean
		{
			return ViewHelper._a.containsKey( sName );
		}
 
		//Private methods.
 
		private function _setName( name:String ) : void
		{
			if ( ViewHelper._register( name, this ) ) _sName = name;
		}
 
		private static function _register( sName:String, oHelper:ViewHelper ) : Boolean
		{
			if ( ViewHelper._a.containsKey( sName ) )
			{
				trace( "ViewHelper instance is already registered with '" + sName + "' name." );
				return false;
			}
			else
			{
				ViewHelper._a.put( sName, oHelper );
				return true;
			}
		}
 
		private static function _unregister( sName:String ) : void
		{
			ViewHelper._a.remove( sName );
		}
 
	}
}
 

    If you have any suggestions or improvements that might make this type of thing work even better drop me a line.

Started reading the book Introduction to Algorithms by Cormen, Leiserson, Rivet, & Stein.  And figured I would start posting my algorithmic implementations in actionscript for those in the community who are interested.  First up is a quick and dirty implementation of insertion sort in two forms: 1. Sort in ascending order 2. Sort in descending order.  This is pretty simple stuff once you wrap your head around the while loop. I'm interested to see more about how O,  notation, and    notation can help us to determine upper bound running times of recursive operations.  I'll keep you all posted as I discover more on this.  And now for the increasing insertion sort code:  

 
//Insertion Sort
 
var arr : Array    = new Array(4, 3,2324, 28, 999, 821, 423,22, 21, 2, 1);
var j    : Number = 0;
 
for( j; j < arr.length; j++)
{
	var key 	: Number = arr[j];
	var i 		: Number = j-1;
 
	while( i > -1 && arr[i] > key )
	{
		arr[i+1] = arr[i];
		i= i-1;
	}
 
	arr[i+1] = key;
}
 
trace( arr );
 

And the decreasing insertion sort code :

 
 
var arr : Array = new Array ( 1, 2, 3,99, 22, 33, 4, 55, 44545, 23, 4 );
 
for( var j : Number = 0; j< arr.length; j++ )
{
	var key : Number = arr[j];
	var i     : Number = j-1;
 
	while( i > -1 && arr[i] < key )
	{
		arr[i+1] = arr[i];
		i= i-1;
	}
 
	arr[ i+1] = key;
}
 
trace( arr );
 

If anyone in the New York City area is interested in jointly studying this topic with me drop me a line.