Implementing Takuzu (part one) : Algorithms for the masses

Implementing Takuzu (part one)

When I described my newfound fondness for Takuzu, or the binary puzzle, I had in mind writing some code to implement it as a playable game. Because I’m into JavaScript these days, I decided to attack the project as a web page.

So, first of all: the web page as an HTML5 document:

<!DOCTYPE html>
<html>
<head>
  <meta charset="UTF-8" />
  <title>Binary puzzle</title>
  <link rel="stylesheet" type="text/css" media="all" href="styles-01.css" />
  <script type="text/javascript" src="http://ajax.microsoft.com/ajax/jQuery/jquery-1.7.1.min.js"></script>
</head>
<body>
  <div id="board"></div>
  <script type="text/javascript" src="playTakuzu-01.js"></script>
</body>
</html>

(Since I’m going to be updating the CSS and JavaScript as we go along, I’ve suffixed their filenames with version numbers.)

This page has a single div named “board” as presentation. My plan is to add a playable Takuzu board (as an HTML table) to that div via JavaScript and jQuery. This has several benefits for me: first, I get to play around with modifying the DOM with jQuery and, second, I have better things to do than layout an 8×8 HTML table by hand. Thanks, but no thanks. (All right, since I’m going to be adding event handlers to the cells of the board, I’ll be using jQuery anyway, so why not go the whole hog?)

Here’s the basic CSS for now:

* {margin:0;padding:0;}
table {border-collapse:collapse;border-spacing:0;}

#board {width:960px;margin:10px auto;}
#board table {margin:0 auto;}
#board td{border:1px solid #dfdfdf;padding:5px;text-align:center;width:15px;cursor:pointer;}

It is pretty basic, merely displaying the Takuzu-board-as-HTML-table centered, and drawing some light grey borders around the cells. We’ll get fancy as we move on.

Now the fun starts. As I said, I’m going to draw the table with JavaScript and jQuery. First of all, I’ll make this an auto-execute document ready function:

"use strict";

$(function () {
  // code here
});

The “use strict” declaration is to force me to write good JavaScript. It doesn’t obviate the need to use JSLint or JSHint, but it does warn me at run-time of some nasty code. Next up, I’ll declare an array to contain the Takuzu board I’m going to display and initialize it from a string. (The example puzzle comes from BinaryPuzzle.com.)

  var boardData = [];
  boardData = "0 0 11 1   00    10    1 0 0 0 01  1   1 11  0    1 0   0    1  ".split('');

This simple array will do for now, although I can already see a use case to making it an array of objects rather than an array of strings.

Now the real meat: let’s build the HTML table that represents the board:

  var zeroFill = function (n, len) {
    var s = n.toString();
    while (s.length < len) {
      s = "0" + s;
    }
    return s;
  };

  var drawBoard = function () {
    var board = $("#board"),
        row, col, index = 0,
        idValue,
        boardHtml = "";

    boardHtml += "<table id='boardTable'>"
    boardHtml += "<tbody>";

    for (row = 0; row < 8; row++) {
      boardHtml += "<tr>";

      for (col = 0; col < 8; col++) {
        idValue = "cell" + zeroFill(index, 4);
        boardHtml += "<td id='" + idValue + "' class='cell'>";

        boardHtml += boardData[index];
        index += 1;

        boardHtml += "</td>";
      }

      boardHtml += "</tr>";
    }

    boardHtml += "</tbody>";
    boardHtml += "</table>";

    board.append(boardHtml);
  };

In essence, I create a string containing the HTML for the table and then append it to the named div from the HTML file (append in jQuery terms means add it as a child to the given element, after the last current child). I name the entire table and I name each cell (with every cell having the same class, just in case I need it). It works, but boy is that some nasty string building. For example, it’s hard to see that all elements are properly terminated. There are lots of angle brackets all over, there are repeated substrings (“table”, “tbody”, etc), there are attributes defined as hard-to-parse concatenations, and so on.

An alternative is to add elements (using append()) one by one as fully-formed children (so add the table to the div, the tbody to the table, etc), but that is much, much slower (basically avoid altering the DOM unnecessarily or too often).

Although that code worked, I disliked it sufficiently to build a reusable object that knew how to create HTML:

(function () {
  window.takuzu = {};
})();

(function ($, $t) {
  $t.htmlGenerator = {};
  var $tgh = $t.htmlGenerator,
      stack = [],
      s = "";

  $tgh.clear = function () {
    stack = [];
    s = "";
  };

  $tgh.start = function (name, attrs) {
    stack.push(name);
    if (typeof attrs === "undefined") {
      s += "<" + name + ">";
    } 
    else {
      s += "<" + name;
      for (var attr in attrs) {
        if (attrs.hasOwnProperty(attr)) {
          s += " " + attr + "='" + attrs[attr] + "'";
        }
      }
      s += ">";
    }
  };
    
  $tgh.finish = function () {
    var name = stack.pop();
    s += "</" + name + ">";
  };

  $tgh.addText = function (text) {
    s += text;
  };

  $tgh.get = function () {
    return s;
  };

})(jQuery, takuzu);

The first auto-execute function creates an empty global takuzu object. The second populates it with a single object called htmlGenerator that has various methods to create properly-formed HTML. (Note: this is at present a singleton. If I have need of two HTML generators at the same time, I shall have to create a better model.) The start() method takes in an element name and an object of attributes for that element. It’ll either create a bare starting tag, or one with a “name=value” series of attributes. (Note, by the way, the use of hasOwnProperty() to make sure we only add attributes from object properties that have been explicitly declared in our code.) The element name is pushed onto an internal stack.

The finish() method writes out an ending tag by popping off the current element name from the internal stack. To retrieve the HTML generated we use the get() method. All in all, this object is easier to test as well.

The code to generate the board-as-table now looks like this:

  var drawBoard = function() {
    var board = $("#board"),
        g = takuzu.htmlGenerator,
        row, col, index = 0,
        idValue;
    
    g.clear();
    g.start("table", {id: "boardTable"});
    g.start("tbody");

    for (row = 0; row < 8; row++) {
      g.start("tr");

      for (col = 0; col < 8; col++) {
        idValue = "cell" + zeroFill(index, 4);
        g.start("td", {id: idValue, class: "cell"});

        g.addText(boardData[index]);
        index += 1;

        g.finish();
      }
    
      g.finish();
    }

    g.finish();
    g.finish();

    board.append(g.get());
  };

Which is easier to read since we’ve now got rid of all of those repeated strings and angle brackets in string delimiters and other bits and pieces. (Note to self: in reading this code, I’m not sure that “finish” is the best method name for completing an element. To be revisited.)

OK, that’s it for this particular episode. You can test out the part 1 code here. Next time, we’ll add some event handlers.

Now playing:
Hall, Daryl - I'm in a Philly Mood
(from Soul Alone)

Fri 17-Aug-2012 5:20 PM Blog / tags: takuzu binary-puzzle

Loading links to posts on similar topics...

previous post next post

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

Emphasize with italics: surround word with underscores _emphasis_
Emphasize strongly: surround word with double-asterisks **strong**
Link: surround text with square brackets, url with parentheses [text](url)
Inline code: surround text with backticks `IEnumerable`
Unordered list: start each line with an asterisk, space * an item
Ordered list: start each line with a digit, period, space 1. an item
Insert code block: start each line with four spaces
Insert blockquote: start each line with right-angle-bracket, space > Now is the time...

by Julian M Bucknall