Recently I´m involved in an Flash project. I´m building a large dynamic website. Can´t tell you which, but I will post a link here when it´s finished. Before this I did not really have much Flash experience. I´ve once used it for a nice menu in my website and I’ve helped my girlfriend Sylvia in the past with scripting some small Flash applications. One being a War Child sponsor game, an other a real simple application to view what a cinema had to offer. Neither of these required much skills from my side. Sylvia did all the graphic design, pointed me to where to put the scripts and the intended behavior. The applications where of the sort that could easily been done in a combination of HTML+CSS+JavaScript as well.

This time it’s all different. This project is really pushing the boundaries of Flash player 8.0 and therefore I needed to get a much better understanding of the inner workings of Flash and ActionScript to get the most out of it. I was helped a lot by gotoAndLearn and kirupa for the basics of the flash professional 8 environment and the ActionScript 2.0 language. And I really loved the good documentation that’s available on adobe.com, especially the ActionScript 2.0 Language Reference as2lr.pdf.

Okay the project is well on it’s way now. And I consider that putting the project in Flash was the right choice. Doing this project with other technology would have cost us far more time. Flash is good documented and reasonably supported by most browsers. However there are a few problems I had with ActionScript. For example I find the lack of support for basic String operation shocking. I had to put a simple String Toolkit together for my usage. It’s build from piece of code that I found on codebehind.com.Originally the author wrote the code as an extension to the build in String data-type. I made the choice to put the code in an StringToolkit class, because I think this makes it easier to isolate the code for future reuse. If you know of any advantages of putting the code in the String prototype please let me know!

class StringToolkit
{

// this replace function is case sensitive, if you try to replace
// ‘cat’ with ‘dog’ it will not recognize a match with ‘Cat’.
public static function replace(s:String, pattern:String, replacement:String):String
{
return s.split(pattern).join(replacement);
}// trim function, used for replacing double spaces with singe spaces
// and trimming leading and trailing spaces from a string
public static function trim()
{

// trim from middle
var trimmed = this;
if(trimmed.indexOf(” “) >= 0)
{

while(trimmed.indexOf(” “) != -1)
{

trimmed = trimmed.replace(” “, ” “);

}

}// trim from start
if(trimmed.indexOf(” “) == 0)
{

while(trimmed.indexOf(” “) == 0)
{

trimmed = trimmed.substring(1, trimmed.length);

}

}

// trim from end
if(trimmed.indexOf(” “) == trimmed.length-1)
{

while(trimmed.indexOf(” “) == trimmed.length-1)
{

trimmed = trimmed.substring(0, trimmed.length-1);

}

}

return trimmed;

}

// convert first character of a string to uppercase
public static function firstCharUpper(s:String)
{

return s.substring(0, 1).toUpperCase() + s.substring(1, s.length);

}

// replaces a word with case insensitivity. this is somewhat more
// complicated. essentially it goes through a lowercase copy of
// the string and replaces the desired word with the new word and
// concatenates the original-case version of the string around it
// special thanks to Gareth Kirwan for writing this for me in JS first!
public static function fullreplace(s:String, matchwhat:String, replacewith:String):String
{

var returnstring = “”;
var matches = rawfind(s,matchwhat);var atindex = 0;
var endat = matches.length – 1;

for(var i=0; i<matches.length; i++)
{

var matchedword = matches[i];returnstring += s.substr(atindex, matchedword.length);

if(i < endat)
{

returnstring += replacewith;

}

atindex += matchedword.length + matchwhat.length;

}

return returnstring;

}

// used by fullreplace function, this function returns
// an array of the lowercase string split by the lowercase
// word we’re replacing
public static function rawfind(s:String ,match:String):Array
{

var sources = s.toLowerCase();
match = match.toLowerCase();
return sources.split(match);

}

}

And here is a toolkit with some extra XML functionality:

class XMLToolkit
{

// special DOM interface “getElementsTagByName” method
// targetName [string]
// returnValue [array / null] : node list
//
// var elements = MyXML.getElementsByTagName(“targetName”);
// for (var i = 0; i < elements.length; i++) {
// var item = elements[i].firstChild.nodeValue;
// }

public static function getElementsByTagName(node, targetName):Array {
// index of return value
var index = 0;
// return value
var returnValue = new Array();

diverDown(node,targetName);

if (returnValue.length == 0) returnValue = null;

return returnValue;

// local function
function diverDown(node,targetName) {
var nodeList = node.childNodes;
for (var i = 0; i < nodeList.length; i++) {
if (nodeList[i].nodeType == 1 && nodeList[i].hasChildNodes) {
if (nodeList[i].nodeName == targetName) {
for (var n = 0; n < nodeList[i].parentNode.childNodes.length; n++) {
if (nodeList[i].parentNode.childNodes[n].nodeName == targetName) {
returnValue[index] = nodeList[i].parentNode.childNodes[n];
index++;
}
}
return;
} else {
diverDown(nodeList[i], targetName);
}
}
}
index = 0;
}
}
}

Again this code is borrowed and modified.

Just now I noticed that Flash Player 9.0 is released. https://www.macromedia.com/go/getflashplayer Nice. Supposedly it’s 10 times as fast as Flash Player 8.0 and the new ActionScript Virtual Machine 2 should support ActionScript 3.0. And ActionScript 3.0 has much better String functionality! But as far as I know Flex 2 (which is still in Beta fase) is the only tool that you can use to build ActionScript 3.0 applications. And Flex is just a programming environment, no graphic tools for as far as I know. So very limited support for building multimedia applications.

So Flash 8 Professional is still the best I can get for targeting the flash player I think. Please notify me if I’m missing something.

Mutilated Chessboard

June 4, 2006

I recenty bought this really nice book from nl.bol.com (dutch online book-cd-dvd-and-more-store, like a kind of amazon); “The COLOSSAL BOOK of SHORT PUZZLES and PROBLEMS” – Martin Gardner.The book contains lots of short mathematical puzzles. Just now I came across this interesting one.

Mutilated Chessboard

The props for this problem are a chessboard and 32 dominoes. Each domino is of such size that is exactly covers two adjacent squares on the board. The 32 dominoes therefore cover all 64 of the chessboard squares. But now suppose we cut off two squares at diagonally opposite corners of the board and discard one of the dominoes, as show in the figure. Is it possible to place the 31 dominoes on the board so that all the remaining squares are covered? If so, show how it can be done. If not, prove it impossible.

Mutilated Chessboard

Well as a programmer I could easily think of a program that could determine the solvability of this problem by trying brute force to find a solution. It’s very simple to make this a deciding/ending process, as I will demonstrate later.

But off course this puzzle is unsolvable for a very simple reason. Every domino can only be placed so that it covers 1 white and 1 black square. Because two white squares are taken out of the game, the best coverage you can get is placing 30 domino’s on the board, leaving 2 black squares uncovered.

I would not have known how to instruct my pc to find this prove.

But there’s another interesting question to ask now that we solved the mutilated chessboard puzzle. Suppose that any two squares of opposite color are removed from the chessboard, can the remaining 62 squares always be completely covered?

Now this is a question that my programming skills can solve in no time. Here is the code with wich I proved the answer to the question to be true. (Computer runs this proof within one second).

public class MutilatedChessboardSolutionsFinder {

public static void main(String[] args) {

MutilatedChessboardSolutionsFinder mcsf = new MutilatedChessboardSolutionsFinder();
if(mcsf.isEveryBlackWhiteCombinationSolvable())
System.out.println(“Yes!”);
else
System.out.println(“No!”);

}

public MutilatedChessboardSolutionsFinder() {}

public boolean isEveryBlackWhiteCombinationSolvable()
{

//true until proven differently
boolean allBlackWhiteCombinationsAreSolvable = true;

//pick a white square

for(int whitesquare = 0; whitesquare < 64;)
{

int wrow = whitesquare/8;
int wcolumn = whitesquare%8;

//pick a black square

int blacksquare;
if(wcolumn < 7) blacksquare = whitesquare+1;
else blacksquare = whitesquare+2;
for(; blacksquare < 64;)

{

int brow = blacksquare/8;
int bcolumn = blacksquare%8;

//is this combination solvable
boolean board[][] = = new boolean[8][8];
board[wrow][wcolumn] = true;
board[brow][bcolumn] = true;
if(!isSolvable(board)) return false;

if(bcolumn < 6) blacksquare+=2;
else if(bcolumn == 6) blacksquare+=3;
else if(bcolumn == 7) blacksquare++;

}

if(wcolumn < 6) whitesquare+=2;
else if(wcolumn == 6) whitesquare+=3;
else if(wcolumn == 7) whitesquare++;

}

return allBlackWhiteCombinationsAreSolvable;

}

private boolean isSolvable(boolean[][] board)
{

return isSolvable(board,0);

}

private boolean isSolvable(boolean[][] board, int from)
{

//printBoard(board);

for(int i=from;i<64;i++) {

int row = i/8;
int column = i%8;
if(!board[row][column])
{

boolean horizontal = false;
boolean vertical = false;
//try vertical
if((row<7) && (!board[row+1][column]))
{

board[row][column] = true;
board[row+1][column] = true;
vertical = isSolvable(board,i+1);
if(!vertical) {

board[row][column] = false;
board[row+1][column] = false;

}

}
//if failed try horizontal
if(!vertical && (column < 7) && (!board[row][column+1]))
{

board[row][column] = true;
board[row][column+1] = true;
horizontal = isSolvable(board,i+2);
if(!horizontal) {

board[row][column] = false;
board[row][column+1] = false;

}

}
return (horizontal || vertical);

}

}

return true;

}

private void printBoard(boolean[][] board)
{

System.out.println(“”);
for(int i = 0; i < 8; i++)
{

String line = “”;
for(int j= 0; j < 8 ; j++)
{

line += ((board[i][j])?”X”:”.”)+” “;

}
System.out.println(line);

}

}
}

So the answer is “yes” and I solved it by programming. So am I happy and proud now? No not really. The answer section of the book gives me a simple and elegant proof. I’m a bit jealous, I wish I wrote that.

Removing ay two squares of opposite colors divides the closed path (one square wide) into two segments. Each segment must contain an even number of squares that alternate colors. Obviously eacht segment can be covered with n dominoes, where n is half the number of squares in the segment. Think of the dominoes as little boxcars that can be placed end to end along each of the two segments. Hence the task is always solvable.

Mutilated Chessboard Proof

Damn I really want to get better at this puzzle solving. This problem and a few more reminded me of a book I have here somewhere. “How to Solve It” – Polya. I never really read it, but I remember from the prologue, the advise to analyse your problem and generate as much facts from it as you can. If I had done this I would probably have understand the “Mutilated Chessboard” puzzle and others much better. I’m gonna try to train myself to really think about things, not to easily resorting to known approaches, not to easily resorting to brute force solutions. I’m starting to appreciate the elegance of real proofs. The kind of proofs demonstrate a deep understanding of the problem. I got a lot to learn. I did not get through “How to Solve It”, but I hope that “The COLOSSAL BOOK of SHORT PUZZLES and PROBLEMS” will be more my kind of read.