The blog of dlaa.me

I pay attention to spelling. Maybe it's because I'm not a very good speller. Maybe it's because I have perfectionist tendencies. Maybe it's just a personality flaw.

Whatever the reason, I'm always looking for ways to avoid mistakes.

Some time ago, I wrote a code analysis rule for .NET/FxCop. More recently I shared two command-line programs to extract strings and comments from C#/JavaScript and followed up with a similar extractor for HTML/XML.

Those tools work well, but I also wanted something GUI for a more natural fit with UI-centric workflows. I prototyped a simple WPF app that worked okay, but it wasn't as ubiquitously available as I wanted. Surprisingly often, I'd find myself on a machine without latest version of the tool. (Classic first world problem, I know...) So I decided to go with a web app instead.

The key observation was that modern browsers already integrate with the host operating system's spell-checker via the spellcheck HTML attribute. By leveraging that, my app would automatically get a comprehensive dictionary, support for multiple languages, native-code performance, and support for the user's custom dictionary. #winning!

Aside: The (very related) forceSpellCheck API isn't supported by any browser I've tried. Fortunately, it's not needed for Firefox, its absence can be coded around for Chrome, and there's a simple manual workaround for Internet Explorer. Click the "Help / About" link in the app for more information.

 

Inspired by web browsers' native support for spell-checking, I've created Spell✔ (a.k.a. SpellV), a simple app that makes it easy to spell-check with a browser. Click the link to try it out now - it's offline-enabled, so you can use it again later even without a network connection!

To import content, Spell✔ supports pasting text from the clipboard, drag-dropping a file, or browsing the folder structure. For a customized experience, you can switch among multiple views of the data, including:

• Original text (duh...)
• Unique words, sorted alphabetically and displayed compactly for easy scanning
• HTML/XML content (including text, comments, and attributes)
• JSON content (string values only)
• JavaScript code comments and string literals

Read more about how Spell✔ works, how it was built, or check out the code on the GitHub page for SpellV!

Sunday evening I happened across a blog post by Josh Smith about finding all the ways to break a $1 bill. Specifically, the goal is to:

Count the number of ways to combine coins worth 100, 50, 25, 10, 5, and 1 cent for a total value of 100 cents

As Josh says, it's a fun challenge and I encourage you to stop reading now and solve it!

Seriously: Stop now. Spoilers ahead...

I took his advice and sat down with pen, paper, and a self-imposed 30 minute time limit. I came up with the C# solution below just before time ran out. As I note in the code, I forgot one line (though I caught it when typing up the solution). Less embarrassingly, this implementation worked correctly the first time I ran it. What's more, it's flexible with regard to the target amount and number/value of the coins (both of which are passed as parameters to the constructor). For bonus points, it outputs all the combinations it finds along the way.

I've added some comments to the code to outline the general algorithm. There are some opportunities to refactor for clarity and an implicit assumption values are passed in decreasing order, but otherwise I'm pretty happy with how it turned out.

If you take on the challenge and come up with something interesting, please leave a note - I'd love to see other approaches!

 

using System;

// Problem: Count (and output) all ways to make $1 with U.S. coins (100, 50, 25, 10, 5, 1 cents).
// Inspiration: http://ijoshsmith.com/2014/11/30/getting-into-functional-programming-with-swift/

class BreakADollar
{
    public static void Main()
    {
        // Entry point/test harness
        Console.WriteLine("Total possibilities: {0}",
            new BreakADollar(
                100,
                new[] { 100, 50, 25, 10, 5, 1 })
            .Invoke());
    }

    // Input
    private readonly int _target;
    private readonly int[] _values;
    // State
    private readonly int[] _counts;
    private int _ways;

    public BreakADollar(int target, int[] values)
    {
        // Initialize
        _target = target;
        _values = values;
        _counts = new int[values.Length];
        _ways = 0;
    }

    public int Invoke()
    {
        // Start the recursive process and return the result
        Recurse(0, 0);
        return _ways;
    }

    private bool Recurse(int i, int sum)
    {
        if (_target == sum)
        {
            // Met the target, done here
            ShowCounts();
            _ways++;
            return false;
        }
        else if (i == _counts.Length)
        {
            // Out of values, keep looking
            return true;
        }
        else if (sum < _target)
        {
            // Search, using increasing counts of current value
            while (Recurse(i + 1, sum))
            {
                _counts[i]++; // Note: Missed this line at first
                sum += _values[i];
            }
            // Reset and continue
            _counts[i] = 0;
            return true;
        }
        else
        {
            // Exceeded the target, done here
            return false;
        }
    }

    private void ShowCounts()
    {
        // Show the count for each value
        for (var i = 0; i < _counts.Length; i++)
        {
            Console.Write("{0}:{1} ", _values[i], _counts[i]);
        }
        Console.WriteLine();
    }
}