Anagram finder in JavaScript

This is the JavaScript implementation of the anagram program. The problem and the solution is described in the main anagram article. Do read that article first.

Also, you may find the C++ article helpful, since it describes member data and functions in some detail, not repeated here. This article describes only the differences between the C++ implementation and this implementation.

Click the “Add terrible poem” button, then the “Run” button.

The output is not very nicely laid out. Instead it is identical to the output of all the other implementations of this program. Handy for verifying the correctness of the output.


Text to search for anagrams:

Find anagrams of lengths from   to  xxx


The number at the beginning of each result line is the number of anagram words. The number before each anagram word is the character offset, starting from zero, of the match. The offset refers to the string, not displayed, that has been stripped of all characters except letters. Before stripping, the poem is 697 characters long, after stripping it is 512 characters long.


The source code

The source code is very close to the C++ implementation. It uses only a very basic subset of JavaScript, HTML and CSS, and should work in any browser. But I confess that it has only really been tested with a few different browsers.

The HTML code

This HTML code (anagram.html) is for a stand-alone page. It differs just a little from the code used for the demonstration above.

<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="UTF-8"/>
    <script type='text/javascript'  src='sprintf.js'                   ></script>
    <script type='text/javascript'  src='anagram.js'                   ></script>
    <link   type='text/css'        href='anagram.css' rel='stylesheet'/>
  </head>
  <body>
    <h1>Anagrams in Javascript</h1>
    Text to search for anagrams:
    <input type="button" value="Clear text" onclick="on_clear_text()"/>
    <input type="button" value="Append terrible poem" onclick="on_append_poem()"/><br/>
    <textarea id="forrest" rows="15" cols="90" onchange="on_textarea_change()" onkeyup="on_textarea_change()"></textarea>
    <br/>
    Find anagrams of lengths from&nbsp;
    <input type="text" name="from" id="from" size="2" maxlength="2" value="4" onblur="on_range_blur(this,  4)"/>
    &nbsp;to&nbsp;
    <input type="text" name="to"   id="to"   size="2" maxlength="2" value="10" onblur="on_range_blur(this, 10)"/>
    <input type="button" value="Reset lengths" onclick="on_reset_lengths()"/>
    <span id="length">xxx</span>
    <p/>
    <input type="button" value="Run" class="nospacing"  onclick="on_run  ()"/>

    <pre id="log"></pre>
  </body>
</html>

The CSS code

This CSS code (anagram.css) is also for a stand-alone page. There is some additional CSS (anagram-std.css, not show here) used above, just to undo WordPress’ theme, which wreacs havoc with input elements.

input[type="button"] { margin-left: 5em; min-width: 8em; }
input.nospacing      { margin-left: inherit; }
pre#log {
    border:             0 solid green;
    border-left-width:  7pt;
    padding:            5pt 1em;
    background-color:  #ddd;
}
span#length { margin-left: 5em; }

The JavaScript code

This is anagram.js. Note that the callbacks are connected in the HTML source.

The application code end at the line window.onload....

The rest is two classes for call stacks, one for a whole call stack, and one for an entry in the call stack. Very handy for debugging.

"use strict";

var g = {
    output_text: "",
    poem:     "Find me, find the Swedish daughter - // Thaw my frosted tegument!\n" +
              "Dry the azured skylit water, // Sky my everlasting tent.\n\n" +
              "Who spied, who spied that awful spot? // O find me! Find the woodman's daughter!\n" +
              "Ask the stream: \"Why tellst thou not // The truth thou knowst - the tragic slaughter?\"\n\n" +
              "Ask the tiger, ask the sun // Whither riding, what my plight?\n" +
              "Till the given day be run, // Till the burning of the night.\n\n" +
              "Thyme, I saw Thyme flow'ring here // A creature white trapped in a gin,\n" +
              "Panting like a hunted deer // Licking still the bloodied skin.\n\n" +
              "With clues surveyed so wondrous laden, // Hunt the ground beneath thy feet!\n" +
              "Find me, find me now, thy maiden, // I will kiss thee when we meet.\n"
};

function output() {
    var s = sprintf(...arguments);
    g.output_text += s + "\n";
}

function debug() {
    var s = sprintf(...arguments);
    var call_stack = new CallStack;
    console.log("Call stack is \n%s", call_stack.toString());
    console.log(sprintf("%s: %s", call_stack.entries[1].prefix(), s));
}

function on_reset_lengths() {
    document.getElementById("from").value =  4;
    document.getElementById("to"  ).value = 10;
}

function on_clear_text() {
    document.getElementById("forrest").value = "";
    on_textarea_change();
    debug("Cleared text");
}

function on_append_poem() {
    document.getElementById("forrest").value += g.poem;
    on_textarea_change();
}

function on_range_blur(field, dval) {
    var val = +field.value;
    if (isNaN(val)) val = dval;
    if (val <  3) val =  3;
    if (val > 15) val = 15;
    field.value = val;
}

function on_textarea_change() {
    var l = document.getElementById("forrest").value.length;
    var el = document.getElementById("length");
    el.innerHTML = sprintf("#chars = %d", l);
}

function get_unified(s) { //--- s is an array of char; returns a string
    const rval = s.slice();
    rval.sort();
    return rval.join("");
}

function Word(offset, value) {
    this.offset  = offset;             //--- integer
    this.value   = value.join("");     //--- string "QWERTY"
    this.unified = get_unified(value); //--- string "EQRTWY"
}

Word.prototype = {
    toString: function() {
        return sprintf("Word<%3d %s %s>", this.offset, this.value, this.unified);
    },
    compareTo: function(b) {  //--- Array.sort() does not use this method; see compare_words() below
        if (this.unified > b.unified) return +1;
        if (this.unified < b.unified) return -1;
        return this.offset - b.offset;
    }
};

function AnagramFinder(text, len) {
    this.text       = text;
    this.len        = +len;
    this.words      = [];
    this.accepted   = [];
    this.low_offset = 0;
    this.MINIMUM    = 3;
    var last = text.length - len;
    for (var n = 0; n <= last; n++) {
        var nlen = n + this.len;
        var sl = text.slice(n, nlen);
        this.words[n] = new Word(n, text.slice(n, nlen));
    }
}

AnagramFinder.prototype = { };

AnagramFinder.prototype.add_candidate = function(cand) {
    false && debug("Looking at candidate %s", cand);
    if (cand.offset < this.low_offset)
        return;
    for (var i in this.accepted)
        if (this.accepted[i].value == cand.value)
            return;
    0 && debug("     Added candidate %s", cand);
    this.accepted.push(cand);
    this.low_offset = cand.offset + this.len;
}

AnagramFinder.prototype.print_one_result = function() {
    var s = sprintf("%3d:", this.accepted.length);
    for (var i in this.accepted)
        s += sprintf(" %4d:%s", this.accepted[i].offset, this.accepted[i].value);
    output(s);
}

AnagramFinder.prototype.add_range = function(begin, end) {
    if (end-begin >= this.MINIMUM) {
        0 && log("add_range(%2d, %2d)", begin, end);
        this.accepted = [];
        this.low_offset = 0;
        for (var n = begin; n < end; n++)
            this.add_candidate(this.words[n]);
        if (this.accepted.length >= this.MINIMUM)
            this.print_one_result();
    }
}

AnagramFinder.prototype.find_all = function() {
    this.words.sort(compare_words);
    var begin = 0;
    for (var n = 1; n < this.words.length; n++) {
        if (this.words[n].unified != this.words[begin].unified) {
            this.add_range(begin, n);
            begin = n;
        }
    }
    this.add_range(begin, this.words.length);
}

function compare_words(a, b)
{
    return a.compareTo(b);
}

function on_run() {
    g.output_text = "";
    var from = +document.getElementById("from").value;
    var to   = +document.getElementById("to"  ).value;
    var s = document.getElementById("forrest").value.toUpperCase();
    var text = [];

    if (from <  3) {  alert("from is too small"   );  return; }
    if (from > 15) {  alert("from is too large"   );  return; }
    if (to   <  3) {  alert("to is too small"     );  return; }
    if (to   > 15) {  alert("to is too large"     );  return; }
    if (from > to) {  alert("to is less than from");  return; }

    for (var i in s) {
        var ch = s[i];
        if (ch >= 'A' && ch <= 'Z')
            text.push(ch);
    }
    output("Letter count = %d", text.length);
    for (var len = from; len <= to; len++) {
        var af = new AnagramFinder(text, len);
        if (len > from) output("");
        output("len = %d", len);
        af.find_all();
    }
    document.getElementById("log").innerHTML = g.output_text;
}

function on_load() {
    on_textarea_change();
    on_clear_text();
}

window.onload = on_load;

// on_clear_text@file:///h/hamren/src/anagrams/02-using-sort/anagram.js:40:5

var split_call_stack_entry_re = new RegExp('^(.*)@(.*)://([^/]*)(/.*)/([^:]*):(\\d+):(\\d+)');

function CallStackEntry(entry_no, text) {   //--- Constructor
    const matches = text.match(split_call_stack_entry_re);
    var i = 1;
    try {
        this.func_name = matches[i++];  //---  on_clear_text
        this.protocol  = matches[i++];  //---  https
        this.host      = matches[i++];  //---  www.sdu.se
        this.dir_name  = matches[i++];  //---  /h/hamren/src/anagrams/02-using-sort
        this.base_name = matches[i++];  //---  anagram.js
        this.line_no   = matches[i++];  //---  40
        this.column    = matches[i++];  //---   5
    } catch (ex) {
        this.func_name = "<undef>";
        this.protocol  = "<undef>";
        this.host      = "<undef>";
        this.dir_name  = "<undef>";
        this.base_name = "<undef>";
        this.line_no   = "<undef>";
        this.column    = "<undef>";
    }
}

CallStackEntry.prototype.toString = function() {
    return sprintf("<%s @ %s  %s  %s / %s : %s : %s>\n",
          this.func_name, this.protocol, this.host, this.dir_name, this.base_name, this.line_no, this.column);
}

CallStackEntry.prototype.prefix = function() {
    var len    = 30-this.base_name.length;
    var format = sprintf("%%3d:%%s %%%ds()", len > 0 ? len : 1);
    return sprintf(format, this.line_no, this.base_name, this.func_name);
}

function CallStack() {   //--- Constructor
    this.entries = [];

    try {
        throw new Error();
    } catch (ex) {
        var lines = ex.stack.split("\n");
        for (var i in lines) {
            if (!lines[i].length)
                break;
            this.entries.push(new CallStackEntry(i, lines[i]));
        }
    }
}

CallStack.prototype.toString = function() {
    var rval = "";
    for (var i in this.entries)
        rval += this.entries[i];
    return rval;
}

sprintf() in JavaScript

For completeness, here is sprintf.js, an implementation of sprintf() that is used in the program. I’m no longer sure where I got it from, but it may be from the sprintf-js package.

/* globals window, exports, define */

(function(window) {
    'use strict'

    var re = {
        not_string: /[^s]/,
        not_bool: /[^t]/,
        not_type: /[^T]/,
        not_primitive: /[^v]/,
        number: /[diefg]/,
        numeric_arg: /[bcdiefguxX]/,
        json: /[j]/,
        not_json: /[^j]/,
        text: /^[^\x25]+/,
        modulo: /^\x25{2}/,
        placeholder: /^\x25(?:([1-9]\d*)\$|\(([^\)]+)\))?(\+)?(0|'[^$])?(-)?(\d+)?(?:\.(\d+))?([b-gijostTuvxX])/,
        key: /^([a-z_][a-z_\d]*)/i,
        key_access: /^\.([a-z_][a-z_\d]*)/i,
        index_access: /^\[(\d+)\]/,
        sign: /^[\+\-]/
    }

    function sprintf() {
        var key = arguments[0], cache = sprintf.cache
        if (!(cache[key])) {
            cache[key] = sprintf.parse(key)
        }
        return sprintf.format.call(null, cache[key], arguments)
    }

    sprintf.format = function(parse_tree, argv) {
        var cursor = 1, tree_length = parse_tree.length, node_type = '', arg, output = [], i, k, match, pad, pad_character, pad_length, is_positive = true, sign = ''
        for (i = 0; i < tree_length; i++) {
            node_type = get_type(parse_tree[i])
            if (node_type === 'string') {
                output[output.length] = parse_tree[i]
            }
            else if (node_type === 'array') {
                match = parse_tree[i] // convenience purposes only
                if (match[2]) { // keyword argument
                    arg = argv[cursor]
                    for (k = 0; k < match[2].length; k++) {
                        if (!arg.hasOwnProperty(match[2][k])) {
                            throw new Error(sprintf('[sprintf] property "%s" does not exist', match[2][k]))
                        }
                        arg = arg[match[2][k]]
                    }
                }
                else if (match[1]) { // positional argument (explicit)
                    arg = argv[match[1]]
                }
                else { // positional argument (implicit)
                    arg = argv[cursor++]
                }

                if (re.not_type.test(match[8]) && re.not_primitive.test(match[8]) && get_type(arg) == 'function') {
                    arg = arg()
                }

                if (re.numeric_arg.test(match[8]) && (get_type(arg) != 'number' && isNaN(arg))) {
                    throw new TypeError(sprintf("[sprintf] expecting number but found %s", get_type(arg)))
                }

                if (re.number.test(match[8])) {
                    is_positive = arg >= 0
                }

                switch (match[8]) {
                    case 'b':
                        arg = parseInt(arg, 10).toString(2)
                    break
                    case 'c':
                        arg = String.fromCharCode(parseInt(arg, 10))
                    break
                    case 'd':
                    case 'i':
                        arg = parseInt(arg, 10)
                    break
                    case 'j':
                        arg = JSON.stringify(arg, null, match[6] ? parseInt(match[6]) : 0)
                    break
                    case 'e':
                        arg = match[7] ? parseFloat(arg).toExponential(match[7]) : parseFloat(arg).toExponential()
                    break
                    case 'f':
                        arg = match[7] ? parseFloat(arg).toFixed(match[7]) : parseFloat(arg)
                    break
                    case 'g':
                        arg = match[7] ? parseFloat(arg).toPrecision(match[7]) : parseFloat(arg)
                    break
                    case 'o':
                        arg = arg.toString(8)
                    break
                    case 's':
                        arg = String(arg)
                        arg = (match[7] ? arg.substring(0, match[7]) : arg)
                    break
                    case 't':
                        arg = String(!!arg)
                        arg = (match[7] ? arg.substring(0, match[7]) : arg)
                    break
                    case 'T':
                        arg = get_type(arg)
                        arg = (match[7] ? arg.substring(0, match[7]) : arg)
                    break
                    case 'u':
                        arg = parseInt(arg, 10) >>> 0
                    break
                    case 'v':
                        arg = arg.valueOf()
                        arg = (match[7] ? arg.substring(0, match[7]) : arg)
                    break
                    case 'x':
                        arg = parseInt(arg, 10).toString(16)
                    break
                    case 'X':
                        arg = parseInt(arg, 10).toString(16).toUpperCase()
                    break
                }
                if (re.json.test(match[8])) {
                    output[output.length] = arg
                }
                else {
                    if (re.number.test(match[8]) && (!is_positive || match[3])) {
                        sign = is_positive ? '+' : '-'
                        arg = arg.toString().replace(re.sign, '')
                    }
                    else {
                        sign = ''
                    }
                    pad_character = match[4] ? match[4] === '0' ? '0' : match[4].charAt(1) : ' '
                    pad_length = match[6] - (sign + arg).length
                    pad = match[6] ? (pad_length > 0 ? str_repeat(pad_character, pad_length) : '') : ''
                    output[output.length] = match[5] ? sign + arg + pad : (pad_character === '0' ? sign + pad + arg : pad + sign + arg)
                }
            }
        }
        return output.join('')
    }

    sprintf.cache = Object.create(null)

    sprintf.parse = function(fmt) {
        var _fmt = fmt, match = [], parse_tree = [], arg_names = 0
        while (_fmt) {
            if ((match = re.text.exec(_fmt)) !== null) {
                parse_tree[parse_tree.length] = match[0]
            }
            else if ((match = re.modulo.exec(_fmt)) !== null) {
                parse_tree[parse_tree.length] = '%'
            }
            else if ((match = re.placeholder.exec(_fmt)) !== null) {
                if (match[2]) {
                    arg_names |= 1
                    var field_list = [], replacement_field = match[2], field_match = []
                    if ((field_match = re.key.exec(replacement_field)) !== null) {
                        field_list[field_list.length] = field_match[1]
                        while ((replacement_field = replacement_field.substring(field_match[0].length)) !== '') {
                            if ((field_match = re.key_access.exec(replacement_field)) !== null) {
                                field_list[field_list.length] = field_match[1]
                            }
                            else if ((field_match = re.index_access.exec(replacement_field)) !== null) {
                                field_list[field_list.length] = field_match[1]
                            }
                            else {
                                throw new SyntaxError("[sprintf] failed to parse named argument key")
                            }
                        }
                    }
                    else {
                        throw new SyntaxError("[sprintf] failed to parse named argument key")
                    }
                    match[2] = field_list
                }
                else {
                    arg_names |= 2
                }
                if (arg_names === 3) {
                    throw new Error("[sprintf] mixing positional and named placeholders is not (yet) supported")
                }
                parse_tree[parse_tree.length] = match
            }
            else {
                throw new SyntaxError("[sprintf] unexpected placeholder")
            }
            _fmt = _fmt.substring(match[0].length)
        }
        return parse_tree
    }

    var vsprintf = function(fmt, argv, _argv) {
        _argv = (argv || []).slice(0)
        _argv.splice(0, 0, fmt)
        return sprintf.apply(null, _argv)
    }

    /**
     * helpers
     */
    function get_type(variable) {
        if (typeof variable === 'number') {
            return 'number'
        }
        else if (typeof variable === 'string') {
            return 'string'
        }
        else {
            return Object.prototype.toString.call(variable).slice(8, -1).toLowerCase()
        }
    }

    var preformattedPadding = {
        '0': ['', '0', '00', '000', '0000', '00000', '000000', '0000000'],
        ' ': ['', ' ', '  ', '   ', '    ', '     ', '      ', '       '],
        '_': ['', '_', '__', '___', '____', '_____', '______', '_______'],
    }
    function str_repeat(input, multiplier) {
        if (multiplier >= 0 && multiplier <= 7 && preformattedPadding[input]) {
            return preformattedPadding[input][multiplier]
        }
        return Array(multiplier + 1).join(input)
    }

    /**
     * export to either browser or node.js
     */
    if (typeof exports !== 'undefined') {
        exports.sprintf = sprintf
        exports.vsprintf = vsprintf
    }
    if (typeof window !== 'undefined') {
        window.sprintf = sprintf
        window.vsprintf = vsprintf

        if (typeof define === 'function' && define.amd) {
            define(function() {
                return {
                    sprintf: sprintf,
                    vsprintf: vsprintf
                }
            })
        }
    }
})(typeof window === 'undefined' ? this : window);

You can reach me by email at “lars dash 7 dot sdu dot se” or by telephone +46 705 189090

View source for the content of this page.