Object-Oriented Software Development: May 2019

Just by change I stumpled upon a nice approach to proving that XSLT processors are Turing Complete. This approach by Unidex involves a XSLT definition that implements the Turing Machine and an example language of writing Turing machines in XML.

(Note that the page is there for quite some time so when it's down somewhere in future, use the WayBackMachine to access it)

If you want to try it, download the XSLT, download the example and put the two together with a simple snippet:

        static void Main(string[] args)
        {
            var transform = new XslCompiledTransform();
            transform.Load(XmlReader.Create(File.Open("turing.xslt", FileMode.Open)));

            StringBuilder sb = new StringBuilder();
            StringWriter sw = new StringWriter(sb);

            var p = new XsltArgumentList();
            p.AddParam("tape", "", "199");
            transform.Transform(XmlReader.Create(File.Open("turing.xml", FileMode.Open)), p, sw);

            Console.WriteLine(sb.ToString());

            Console.ReadLine();
        }

Running this yields

Step number = 1
Tape        = 199
Tape head     ^
State       = go_right
Next symbol = 1
Next state  = go_right
Movement    = right

Step number = 2
Tape        = 199
Tape head      ^
State       = go_right
Next symbol = 9
Next state  = go_right
Movement    = right

Step number = 3
Tape        = 199
Tape head       ^
State       = go_right
Next symbol = 9
Next state  = go_right
Movement    = right

Step number = 4
Tape        = 199
Tape head        ^
State       = go_right
Next symbol =
Next state  = increment
Movement    = left

Step number = 5
Tape        = 199
Tape head       ^
State       = increment
Next symbol = 0
Next state  = increment
Movement    = left

Step number = 6
Tape        = 190
Tape head      ^
State       = increment
Next symbol = 0
Next state  = increment
Movement    = left

Step number = 7
Tape        = 100
Tape head     ^
State       = increment
Next symbol = 2
Next state  = stop
Movement    = left

The Turing machine has halted.
Final state = stop
Final tape  =  200
Tape head     ^

Years ago I've blogged on a challenge which was to implement a simple tetris game. This new reloaded version is a direct one-to-one translation to vanilla Javascript and runs in a browser. Feel free to learn from the code and/or reuse it in any way. Note that the UP key has to be pressed to start the game.

(Re)start: up
Moves: left/right/down/space

The code:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>

    <script>

        var pieceMove = {
            left:   'left',
            right:  'right',
            up:     'up',
            down:   'down',
            rotate: 'rotate'
        };
    
        function board() {
            this.MARGIN      = 5;
            this.SIZEX       = 10;
            this.SIZEY       = 40;
            this.BLOCKSIZE   = 10;
            this.PIECESTARTX = 8;
    
            var i, j;
    
            this.squares = new Array( this.MARGIN + this.SIZEX + this.MARGIN );
            for ( i=0; i < this.squares.length; i++ )
                this.squares[i] = new Array( this.MARGIN + this.SIZEY + this.MARGIN );
    
            // fill the margin 
            for ( i=0; i < this.MARGIN + this.SIZEX + this.MARGIN; i++ )
                for ( j=0; j < this.MARGIN; j++ )
                    this.squares[i][j] = this.squares[i][j + this.SIZEY + this.MARGIN] = true;
            for ( i=0; i < this.MARGIN; i++ )
                for ( j=0; j < this.MARGIN + this.SIZEY + this.MARGIN; j++ )
                    this.squares[i][j] = this.squares[i + this.SIZEX + this.MARGIN][j] = true;        
    
            this.currentPiece  = piece.getRandomPiece();
            this.currentPieceX = this.PIECESTARTX;
            this.currentPieceY = this.MARGIN;        
    
            this.score         = 0;
        }
    
        board.prototype.obtainContext = function(canvas) {
            this.context       = canvas.getContext('2d');     
            this.contextWidth  = canvas.width;
            this.contextHeight = canvas.height;       
        }
    
        board.prototype.paint = function() {
            
            var i, j;
    
            this.context.fillStyle = 'white';
            this.context.fillRect(0, 0, this.contextWidth, this.contextHeight);
    
            // background
            this.context.fillStyle = 'black';
    
            for ( i=0; i < this.SIZEX; i++ )
                for ( j=0; j < this.SIZEY; j++ )
                    if ( this.squares[this.MARGIN + i][this.MARGIN + j] )
                        this.context.fillRect( i * this.BLOCKSIZE, j * this.BLOCKSIZE, this.BLOCKSIZE, this.BLOCKSIZE );
    
            // piece
            if ( this.currentPiece ) {
                for ( i=0; i < this.currentPiece.SIZE; i++ )
                    for ( j=0; j < this.currentPiece.SIZE; j++ )
                        if ( this.currentPiece.blockData[i][j] ) {
                            this.context.fillRect( (this.currentPieceX - this.MARGIN + i) * this.BLOCKSIZE, ( this.currentPieceY - this.MARGIN + j ) * this.BLOCKSIZE, 
                                                    this.BLOCKSIZE, this.BLOCKSIZE);
                        }
            }    

            // score
            this.context.fillStyle = 'red';
            this.context.fillText( this.score, 5, 10 );
        }
    
        /* Advance one step of the game */
        board.prototype.autoUpdate = function() {

            this.removeFullLines();
    
            if ( this.currentPiece ) {
                var _newX = this.currentPieceX;
                var _newY = this.currentPieceY + 1;
    
                if ( this.isLegalPosition( this.currentPiece, _newX, _newY ) ) {
                    this.currentPieceY = _newY;
                }
                else {
                    this.absorbCurrentPiece();
    
                    this.currentPiece  = piece.getRandomPiece();
                    this.currentPieceX = this.PIECESTARTX;
                    this.currentPieceY = this.MARGIN;
    
                    if ( !this.isLegalPosition( this.currentPiece, this.currentPieceX, this.currentPieceY ) ) {
                        this.score = 'Game over: ' + this.score;
                        this.currentPiece = null;

                        return false;
                    }
                }
            }    

            return true;
        }
    
        /* Remove all full lines */
        board.prototype.removeFullLines = function() {
            var fullLineNumber = -1;
            do
            {
                fullLineNumber = this.getPossibleFullLine();
                if ( fullLineNumber >= 0 )
                    this.removeLine( fullLineNumber );
            } while ( fullLineNumber >= 0 );
        }
    
        /* Check if one of lines is possibly filled */
        board.prototype.getPossibleFullLine = function() {
            for ( var j = 0; j < this.SIZEY; j++ )
            {
                var isFull = true;
                for ( var i = 0; i < this.SIZEX; i++ )
                    isFull &= this.squares[this.MARGIN + i][this.MARGIN + j];
    
                if ( isFull )
                    return j + this.MARGIN;
            }
    
            return -1;
        }
    
        /* Remove selected line */
        board.prototype.removeLine = function( lineNumber ) {
            for ( var j = lineNumber; j > this.MARGIN; j-- )
                for ( var i=this.MARGIN; i < this.SIZEX + this.MARGIN; i++ )
                    this.squares[i][j] = this.squares[i][j - 1];
    
            this.score += 1;
        }
    
        /* Copy piece data to board's block data. Called only when piece becomes "solid", non-movable. */
        board.prototype.absorbCurrentPiece = function() {
            if ( this.currentPiece )
                for ( var i=0; i < this.currentPiece.SIZE; i++ )
                    for ( var j=0; j < this.currentPiece.SIZE; j++ )
                        if ( this.currentPiece.blockData[i][j] )
                            this.squares[i + this.currentPieceX][j + this.currentPieceY] = true;
        }
    
        /* Moves current piece into a new position, if possible */
        board.prototype.moveCurrentPiece = function(move) {
    
            var _newPiece = this.currentPiece;
            var _newX     = this.currentPieceX;
            var _newY     = this.currentPieceY;
    
            if ( this.currentPiece )
            {
                if ( move == pieceMove.rotate ) _newPiece = piece.rotate( this.currentPiece );
                if ( move == pieceMove.left )   _newX = this.currentPieceX - 1;
                if ( move == pieceMove.right )  _newX = this.currentPieceX + 1;
                if ( move == pieceMove.down )   _newY = this.currentPieceY + 1;
    
                // move only if legal position
                if ( this.isLegalPosition( _newPiece, _newX, _newY ) )
                {
                    this.currentPiece  = _newPiece;
                    this.currentPieceX = _newX;
                    this.currentPieceY = _newY;
                }
            }
        }
    
        /* Is the new possible position of a piece "legal" in a sense that the piece doesn't overlap with non-empty cells */
        board.prototype.isLegalPosition = function( piece, pieceX, pieceY ) {
            for ( var i=0; i < piece.SIZE; i++ )
                for ( var j=0; j < piece.SIZE; j++ )
                    if ( piece.blockData[i][j] &&
                         this.squares[i + pieceX][j + pieceY]
                        )
                        return false;
    
                return true;
        }
    
        function piece(r0, r1, r2, r3, r4) {
            this.SIZE = 5;
    
            var i;
    
            this.blockData = new Array( this.SIZE );
            for ( i=0; i < this.SIZE; i++ )
                this.blockData[i] = new Array( this.SIZE );
    
            for ( i=0; i<this.SIZE; i++ ) {
                this.blockData[i][0] = r0[i];
                this.blockData[i][1] = r1[i];
                this.blockData[i][2] = r2[i];
                this.blockData[i][3] = r3[i];
                this.blockData[i][4] = r4[i];
            }
        }
    
        piece.rotate = function( source ) {
            if ( source == piece.i_horiz ) return piece.i_vert;
            if ( source == piece.i_vert )  return piece.i_horiz;
    
            if ( source == piece.z_lefthoriz ) return piece.z_leftvert;
            if ( source == piece.z_leftvert )  return piece.z_lefthoriz;
    
            if ( source == piece.z_righthoriz ) return piece.z_rightvert;
            if ( source == piece.z_rightvert )  return piece.z_righthoriz;
    
            if ( source == piece.l_l1 ) return piece.l_l2;
            if ( source == piece.l_l2 ) return piece.l_l3;
            if ( source == piece.l_l3 ) return piece.l_l4;
            if ( source == piece.l_l4 ) return piece.l_l1;
    
            if ( source == piece.r_l1 ) return piece.r_l2;
            if ( source == piece.r_l2 ) return piece.r_l3;
            if ( source == piece.r_l3 ) return piece.r_l4;
            if ( source == piece.r_l4 ) return piece.r_l1;
    
            return piece.box;
        }
    
        piece.getRandomPiece = function() {
            var _next = Math.floor( Math.random() * 6 );
            switch ( _next ) {
                case 1  : return piece.z_lefthoriz;
                case 2  : return piece.z_righthoriz;
                case 3  : return piece.l_l1;
                case 4  : return piece.r_l1;
                case 5  : return piece.i_horiz;
                default : return piece.box;
            }
        }
    
        piece.box = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.i_horiz = new piece(
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.i_vert = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 1, 1, 1, 1 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.z_lefthoriz = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 0, 1, 1, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.z_leftvert = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 1, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.z_righthoriz = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 0, 1, 1, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.z_rightvert = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 1, 0 ],
            [0, 0, 0, 1, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.l_l1 = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 1, 0, 0, 0 ],
            [0, 1, 1, 1, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.l_l2 = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 1, 0, 0, 0 ],
            [0, 1, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.l_l3 = new piece(
            [0, 0, 0, 0, 0 ],
            [1, 1, 1, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.l_l4 = new piece(
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 1, 1, 0, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.r_l1 = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 1, 0 ],
            [0, 1, 1, 1, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.r_l2 = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 0, 1, 1, 0 ],
            [0, 0, 0, 1, 0 ],
            [0, 0, 0, 1, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.r_l3 = new piece(
            [0, 0, 0, 0, 0 ],
            [0, 0, 1, 1, 1 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
        piece.r_l4 = new piece(
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 0, 0 ],
            [0, 0, 1, 1, 0 ],
            [0, 0, 0, 0, 0 ],
            [0, 0, 0, 0, 0 ]        
        );
    
        
        var _board;
    
        var _interval;              // current frame interval
        var _speedinterval = 15000; // speed up every 15 sec

        var _intervalHandle;
    
        /*
            * This advances one frame
            */
        function tick() {
            _board.paint();
            if ( _board.autoUpdate() ) {
                _intervalHandle = setTimeout( tick, _interval);
            }
        }
    
        /*
            * This fires every 15 seconds and decreases the timeout of the other timer
            */
        function speedup() {
            if ( _interval > 20 )
                _interval -= 10;
        }
    
        function init(canvas) {
            _interval      = 200;

            _board = new board();
            _board.obtainContext(canvas);
        
            _intervalHandle = setTimeout( tick, _interval ); 
        }

        (function main(){
                        
            window.addEventListener('load', function() {
                var canvas = document.getElementById('tetris');

                canvas.addEventListener('click', function() {
                    if ( _intervalHandle )
                        clearTimeout( _intervalHandle );
                    init(canvas);
                });
                
                setInterval( speedup, _speedinterval );
            } );
    
            window.addEventListener( 
                'keydown', 
                function(e) {
                    //e.preventDefault();
                    if ( e.keyCode == 37 ) // arrow left
                        _board.moveCurrentPiece( pieceMove.left );
                    if ( e.keyCode == 39 ) // arrow right
                    _board.moveCurrentPiece( pieceMove.right );
                    if ( e.keyCode == 40 ) // arrow down
                        _board.moveCurrentPiece( pieceMove.down );
                    if ( e.keyCode == 32 ) // space
                        _board.moveCurrentPiece( pieceMove.rotate );
    
                    _board.paint();
                }
            );

        })();
    
    </script>
    <style>
        #welcome {
            border: 1px solid black;
            font: 10px tahoma;
            width: 100px;
        }
        #tetris {
            border: 1px solid black;
        }
    </style>    
</head>
<body>

    <div id="welcome">
        Moves: left/right/down/space
        Click: (re)start.
    </div>
    <div>
        <canvas id="tetris" width="100" height="400">
        </canvas>
    </div>

</body>
</html>

Object-Oriented Software Development

Monday, May 20, 2019

Your XSLT processor is Turing Complete

Thursday, May 9, 2019

Tetris challenge - reloaded (Javascript)

Followers

Total Pageviews