The blog of dlaa.me
Tag: "Miscellaneous"
  • Hour of No Code [Solving Day 1 Part 1 of Advent of Code 2016 without writing any code]
    Thursday, December 15th 2016

    Advent of Code is a cool idea! Author Eric Wastl describes it as "a series of small programming puzzles for a variety of skill levels". I thought I might work through the first few days with non-programmer children, so I read the description of Day 1: No Time for a Taxicab:

    [...] start at the given coordinates [...] and face North. Then, follow the provided sequence: either turn left (L) or right (R) 90 degrees, then walk forward the given number of blocks [...]

    Following simple, mechanical steps seemed like a fine introduction to programming for young people, so I signed in and requested the data for Part 1 of the puzzle.

    Oh...

    You see, while the examples Eric provides are quite simple, the actual input is over 150 steps and some of the distances are three-digit numbers. So while this puzzle is perfect for a small programming challenge, it'd be too tedious to work through manually.

    Unless...

    What if we could solve the programming puzzle without any programming?

    What if we could solve it with something familiar to non-developers?

    What if we could solve it with a basic spreadsheet???

    Hmmm...

    Let's try!

    We'll be using Google Sheets because it's free, easy to use, and convenient. (But any decent spreadsheet will do.) And we'll be working with the sample data (not the actual puzzle data) so as not to give too much away. Keep reading to see all the steps - or follow along in a spreadsheet if you want to get your hands dirty.

    Good, let's start with the sample data:

    R5, L5, R5, R3 leaves you 12 blocks away.

    To understand why and familiarize yourself with the puzzle, read about taxicab geometry and work through the steps on paper first. It's important to realize that R and L steps do not necessarily alternate and that the direction at the end of each step depends on the direction at the beginning of the step. However, given the state after N steps, the state after step N+1 is completely defined by that direction and distance.

    Spreadsheets typically go "down", so let's set ours up like that by adding the steps to a Data column (leaving row 2 blank for reasons that will be clear later):

    A
    1 Data
    2
    3 R5
    4 L5
    5 R5
    6 R3

    Each step contains two pieces of information: the Direction to turn and the Distance to move. Let's start by pulling them apart so we can deal with them separately. The LEFT and RIGHT functions are our friends here (with a little help from LEN). The Direction is simply the first character of the data, or =LEFT(A3, 1) (assuming we're looking at row 3, the first value). And the Distance is just the rest of the string, or =RIGHT(A3, LEN(A3)-1).

    Type those formulas into cells B3 and C3 and replicate the formulas down to row 6. (Your spreadsheet program should automatically update the formulas for rows 4-6 to be relative to their respective cells.) Done correctly, that gives the following:

    A B C
    1 Data Direction Distance
    2
    3 R5 R 5
    4 L5 L 5
    5 R5 R 5
    6 R3 R 3

    We'd like to turn the Direction letter into a number so we can do math on it - the IF function works nicely for that. By using -1 to represent a left turn and 1 to represent a right turn, use the formula =IF(B3="L", -1, 1) to create a Rotation field for row 3 (and then replicate the formula down):

    A B C D
    1 Data Direction Distance Rotation
    2
    3 R5 R 5 1
    4 L5 L 5 -1
    5 R5 R 5 1
    6 R3 R 3 1

    Now let's use Rotation to create a Heading that tracks where the player is pointing after each move. The four possible values are North, East, South, and West - it's convenient to use the numbers 0, 1, 2, and 3 respectively. Because we're adding and subtracting numbers to determine the Heading, it's possible to get values outside that range (ex: 3 + 1 = 4). Just like with a 12-hour clock (11am + 2 hours = 1pm), we'll use modular arithmetic to stay within the desired range. The starting direction is North, so we'll seed an initial Heading by putting the value 0 in cell E2. (See, I told you row 2 would be useful!) After that, the MOD function can be used to figure out the new Heading by adding the Rotation to the current value: =MOD(E2 + D3, 4). Replicating this formula down gives the following:

    A B C D E
    1 Data Direction Distance Rotation Heading
    2 0
    3 R5 R 5 1 1
    4 L5 L 5 -1 0
    5 R5 R 5 1 1
    6 R3 R 3 1 2

    Knowing a Heading and a Distance means we can track of the X and Y coordinates as the player moves around the city. If the player is facing East and moves forward, the X coordinate will increase by that Distance; if facing West, it will decrease. Similarly, a move facing North will increase the Y coordinate, while a move South will decrease it. The CHOOSE function allows us to represent this quite easily. The only catch is that CHOOSE indices are 1-based and our Heading values are 0-based, so we need to adjust for that by adding 1. After seeding 0 values for the starting X and Y coordinates in row 2, we can update the X coordinate with =F2 + CHOOSE(E3+1, 0, C3, 0, -C3) and the Y coordinate with =G2 + CHOOSE(E3+1, C3, 0, -C3, 0). Replicating those formulas down leads to:

    A B C D E F G
    1 Data Direction Distance Rotation Heading X Y
    2 0 0 0
    3 R5 R 5 1 1 5 0
    4 L5 L 5 -1 0 5 5
    5 R5 R 5 1 1 10 5
    6 R3 R 3 1 2 10 2

    Now all that's left to solve the puzzle is to compute the taxicab distance of each X/Y coordinate from the starting point. Well, that's just the magnitude of the X coordinate added to the magnitude of the Y coordinate and that can be expressed using the ABS function: =ABS(F3) + ABS(G3). Replicating that down gives the following, final, table and the answer to the sample puzzle:

    A B C D E F G H
    1 Data Direction Distance Rotation Heading X Y Taxicab Distance from Start
    2 0 0 0
    3 R5 R 5 1 1 5 0 5
    4 L5 L 5 -1 0 5 5 10
    5 R5 R 5 1 1 10 5 15
    6 R3 R 3 1 2 10 2 12

    Sure enough, the taxicab distance after the final move (cell H6) is 12 - just like the sample said it should be! And we figured that out without writing any "code" at all - we simply came up with few small formulas to methodically break the problem down into little pieces we could solve with a spreadsheet. That may not quite be coding (in the usual sense), but it sure is programming!

    PS - Having definitively established that you are 1337 with a spreadsheet, you might be looking for other challenges... Good news: Part 2 of the Advent of Code taxicab problem has been left as an exercise for the reader! :)

    Tags: Miscellaneous Technical
  • Sky-Hole Revisited [Pi-Hole in a cloud VM for easy DNS-based ad-blocking]
    Monday, November 21st 2016

    I wrote about my adventures running a Pi-Hole in the cloud for DNS-based ad-blocking roughly a year ago. In the time since, I've happily used a Sky-Hole for all the devices and traffic at home. When updating my Sky-Hole virtual machine recently, I used a simpler approach than before and wanted to briefly document the new workflow.

    For more context on why someone might want to use a DNS-based ad-blocker, please refer to the original post.

    Installation

    1. Create an Ubuntu Server virtual machine with your cloud provider of choice (such as Azure or AWS)

      Note: Thanks to improvements by the Pi-Hole team, it's now able to run in the smallest virtual machine size

    2. Connect via SSH and update the package database:

      sudo apt-get update

    3. Install Pi-Hole:

      curl -L https://install.pi-hole.net | bash

      Note: Running scripts directly from the internet is risky, so consider using the alternate install instead

    4. Open the dnsmasq configuration file:

      sudo nano /etc/dnsmasq.d/01-pihole.conf

    5. Turn off logging by commenting-out the corresponding line:

      #log-queries

    6. Open the Pi-Hole configuration file:

      sudo nano /etc/pihole/setupVars.conf

    7. Update it to use an invalid address for blocked domains:

      IPv4_address=0.0.0.0

    8. Re-generate the block list:

      sudo /opt/pihole/gravity.sh

    9. Verify the block list looks reasonable:

      cat /etc/pihole/gravity.list

    10. Verify logging is off:

      cat /var/log/pihole.log

    11. Reboot to ensure everything loads successfully:

      sudo reboot

    12. Grant access to the virtual machine's public IP address by opening the relevant network ports (incoming UDP and TCP on port 53)

    Don't forget

    If you use a Pi-Hole regularly, please consider donating to the Pi-Hole project so the maintainers can continue developing and improving it.

    Tags: Miscellaneous Technical Web
  • Catch common Markdown mistakes as you make them [markdownlint is a Visual Studio Code extension to lint Markdown files]
    Tuesday, December 8th 2015

    The lightweight, cross-platform Visual Studio Code editor recently gained support for extensions, third party packages that add or enhance capabilities of the tool. Of particular interest to me are linters, syntax checkers that help avoid mistakes and maintain consistency when working with a language (either code or markup). I've previously written about markdownlint, a Node.js linter for the Markdown markup language. After looking at the VS Code API, it seemed straightforward to create a markdownlint extension for Code. I did so and published markdownlint to the extension gallery where it can be installed via the command ext install markdownlint. What's nice about editor integration for a linter is that feedback is immediate and interactive: mistakes are highlighted as they're made and it's easy to click a link for information about any rule violation.

    If linting Markdown is something that interests you, please try the markdownlint extension for VS Code and share your feedback!

    Tags: Miscellaneous Node.js Technical
  • Pie in the Sky-Hole [A Pi-Hole in the cloud for ad-blocking via DNS]
    Monday, August 24th 2015

    Inspired by Marco Arment's recent post about blocking advertisements on the web, I decided to explore the same idea. However, while Marco focuses on the annoyance of advertisements, I am interested in the security benefits of removing them. There have been numerous incidents of otherwise respectable websites compromising the security of their users due to the advertisements they include. Searches for "web site hacked 'ad network'" on Google and Bing provide some examples; another is this XSS attack on Troy Hunt's site, which is interesting thanks to the detailed analysis Troy provides. Popular sites of all kinds have been compromised in this way, and one might argue they should be treated as attackers because of the approach used to serve third-party ads.

    Marco's article describes an in-browser solution for ad-blocking, but I prefer something that automatically protects all the machines on my network (at least, while they're using the network; see below). So I set out looking for something that works at the network level and came across Pi-Hole, a DNS-based ad-blocker for the Raspberry Pi. Aside from the fact that I don't own a Pi, this seemed like exactly what I wanted. ;)

    Fortunately, there are no actual dependencies on Pi hardware, so I decided to create my own Pi-Hole on a server in the cloud - thus the name "Sky-Hole". To do so, I opened the Microsoft Azure Portal, created a small virtual machine running Ubuntu Server 15.04, and configured it according to the manual instructions for Pi-Hole (with a few customizations outlined below). Then I updated my wireless router to use Sky-Hole as the DNS server for my home network - and all my devices stopped showing advertisements!

    Directions

    I used a minimal set of steps to configure the Sky-Hole and list them below so they're easy to reproduce. I made a couple of tweaks to the Pi-Hole process along the way and explain them in turn.

    First, create a virtual machine to run everything on (I've used both Microsoft Azure and Amazon Web Services, but any provider should do). Then, install dnsmasq:

    sudo apt-get -y install dnsmasq
    sudo update-rc.d dnsmasq enable
    sudo mv /etc/dnsmasq.conf /etc/dnsmasq.orig
    sudo nano /etc/dnsmasq.conf
    

    Configure dnsmasq.conf as follows (replacing "sky-hole" on the last line with the host name of your virtual machine):

    domain-needed
    bogus-priv
    no-resolv
    server=8.8.8.8
    server=8.8.4.4
    interface=eth0
    listen-address=127.0.0.1
    cache-size=10000
    log-queries
    log-facility=/var/log/pihole.log
    local-ttl=300
    addn-hosts=/etc/pihole/gravity.list
    host-record=sky-hole,127.0.0.1,::1
    

    The addn-hosts option is meant to be optional, but I needed it because /etc/hosts was not updated by gravity.sh. The host-record option was necessary to avoid a "sudo: unable to resolve host" error which showed up whenever I enabled dnsmasq. (Though this may be an artifact of the default virtual machine configuration under Azure.)

    Update 2015-08-30: host-record was similarly necessary on AWS, where the automatically-assigned host name was of the form ip-123-123-123-123.

    Now, download the Pi-Hole script and run it to generate the list of domain names to block:

    sudo curl -o /usr/local/bin/gravity.sh https://raw.githubusercontent.com/jacobsalmela/pi-hole/master/gravity.sh
    sudo chmod 755 /usr/local/bin/gravity.sh
    sudo /usr/local/bin/gravity.sh
    sudo sed -i "s/^[0-9\.]\+\s/0.0.0.0 /g" /etc/pihole/gravity.list
    

    The last line is my own and replaces the virtual machine's IP address with an unusable 0.0.0.0 address when redirecting undesirable sites. Because I'm not running a web server on the Sky-Hole, this seems like a more appropriate way to block unwanted domain names. (Besides, hostname -I in Azure reports the virtual machine's internal address which is on a private network.)

    Restart dnsmasq to apply the changes:

    sudo service dnsmasq restart
    

    Now, test things locally via ping, dig, nslookup (or similar) to verify that desirable domain names are returned as-is and undesirable ones are blocked by returning the 0.0.0.0 IP. Assuming that's the case, update the virtual machine to accept incoming UDP traffic on port 53 (per the DNS specification) and test again from a different machine. If everything is working as expected, configure your router to use the Sky-Hole's public IP address for DNS resolution. This automatically applies to all devices on the local network and avoids the need to update each one manually.

    Update 2015-08-30: You may also want to enable TCP traffic on port 53 (per RFC 5966).

    Congratulations, you're done!

    Notes

    • The nice thing about this approach is that it covers all the machines on your network. However, it can only protect machines when they're connected to that network. Taking a phone or tablet elsewhere or using cellular data exempts a device from this kind of protection.
      • So this may be an argument in favor of per-device ad-blocking - though perhaps as a strategy to be used in addition to (rather than instead of) a network-wide approach.
    • When creating the virtual machine, I used the Basic A1 size which would cost about $34.97 per month on Azure (though I don't plan to leave it running very long).
      • I tried the A0 size first (which would have cost $13.39 per month on Azure), but it ran out of memory building the domain list, seemingly due to this known issue.
    • As I note above, I chose not to configure a local web server on my Sky-Hole. While doing so offers interesting benefits, it didn't seem compelling for the purposes of this experiment and I preferred to keep thing simple. Should you choose to, directions are available in the Pi-Hole documentation.
    • If you end up using Pi-Hole like this (or on its own) please consider donating to the author, Jacob Salmela, to help support his work.

    Conclusion

    I'm only been running Sky-Hole for a couple of days, but the usability and performance improvements for some sites are quite noticeable. More importantly, it seems to me the browsing experience is necessarily safer by virtue of removing not just a subset of traffic, but the subset which is most likely to contain unwanted content.

    As an experiment and a learning experience, Sky-Hole has been a successful side-project. I hope others find it interesting or thought-provoking and I welcome comments on improving or enhancing the approach!

    Tags: Miscellaneous Technical Web
  • Extensibility is a wonderful thing [A set of Visual Studio Code tasks for common npm functionality in Node.js and io.js]
    Thursday, April 30th 2015

    Yesterday at its Build conference, Microsoft released the Visual Studio Code editor which is a lightweight, cross-platform tool for building web and cloud applications. I've been using internal releases for a while and highly recommend trying it out!

    One thing I didn't know about until yesterday was support for Tasks to automate common steps like build and testing. As the documentation shows, there's already knowledge of common build frameworks, including gulp for Node.js and io.js. But for simple Node projects I like to automate via npm's scripts because they're simple and make it easy to integrate with CI systems like Travis. So I whipped up a simple tasks.json for Code that handles build, test, and lint for typical npm configurations. I've included it below for anyone who's interested.

    Note: Thanks to metadata, the build and test tasks are recognized as such by Code and easily run with the default hotkeys Ctrl+Shift+B and Ctrl+Shift+T.

    Enjoy!

     

    {
      "version": "0.1.0",
      "command": "npm",
      "isShellCommand": true,
      "suppressTaskName": true,
      "tasks": [
        {
          // Build task, Ctrl+Shift+B
          // "npm install --loglevel info"
          "taskName": "install",
          "isBuildCommand": true,
          "args": ["install", "--loglevel", "info"]
        },
        {
          // Test task, Ctrl+Shift+T
          // "npm test"
          "taskName": "test",
          "isTestCommand": true,
          "args": ["test"]
        },
        {
          // "npm run lint"
          "taskName": "lint",
          "args": ["run", "lint"]
        }
      ]
    }
    

    Updated 2015-05-02: Added --loglevel info to npm install for better progress reporting

    Updated 2016-02-27: Added isShellCommand, suppressTaskName, and updated args to work with newer versions of VS Code

    Tags: Node.js Miscellaneous
  • Solving puzzles at 30,000 feet [An iterative solution for the "Is this a binary search tree?" programming problem]
    Tuesday, April 7th 2015

    Sitting on a plane recently looking for a distraction, I recalled a programming challenge by James Michael Hare: Little Puzzlers-Is Tree a Binary Search Tree?. All I had to work with was a web browser, so I used JavaScript to come up with a solution. James subsequently blogged a recursive implementation in C# which is quite elegant. Wikipedia's Binary search tree page uses the same approach and C++ for its verification sample.

    Because I did things a little differently, I thought I'd share - along with a few thoughts:

    /**
     * Determines if a tree of {value, left, right} nodes is a binary search tree.
     * @param {Object} root Root of the tree to examine.
     * @returns {Boolean} True iff root is a binary search tree.
     */
    function isBinarySearchTree(root) {
      var wrapper, node, stack = [{ node: root }];
      while (wrapper = stack.pop()) {
        if (node = wrapper.node) {
          if ((node.value <= wrapper.min) || (wrapper.max <= node.value)) {
            return false;
          }
          stack.push({ node: node.left, min: wrapper.min, max: node.value },
                     { node: node.right, min: node.value, max: wrapper.max });
        }
      }
      return true;
    }
    

    Notes:

    • Tree nodes are assumed to have a numeric value and references to their left and right nodes (both possibly null).
      • I used the name value (vs. data) because it is slightly more specific.
    • I decided on an iterative algorithm because it has two notable advantages over recursion:
      • In the worst case for a tree with N nodes, an iterative solution has bookkeeping for N/2 nodes (when starting to process the leaf nodes of a balanced tree assuming nodes were queued) whereas a recursive solution has bookkeeping for all N nodes (when processing the deepest node of a completely unbalanced tree).
        • Because there are two recursive calls, I don't think tail recursion can be counted on to fix the worst-case behavior.
      • The memory used for bookkeeping by an iterative solution comes from the heap which is generally much larger than the thread stack.
      • To be fair, neither advantage is likely to be significant in practice - but they make good discussion points during an interview. :)
    • The iterative algorithm has a disadvantage:
      • Bookkeeping requires an additional object type (wrapper in the code above) which associates the relevant min and max bounds with pending node instances.
        • ... unless you avoid the wrapper by augmenting the node elements themselves.
          • ... which is quite easy in JavaScript thanks to its dynamic type system.
        • The creation/destruction of wrapper objects creates additional memory pressure.
          • Although these objects are short-lived and therefore low-impact for typical garbage collection algorithms.
    • I intended the code to be concise, so I made use of assignments in conditional expressions.
    • The code uses a stack (vs. a queue) because stacks tend to be simpler than queues - especially when implemented with an array.
    • I made use of the fact that comparing a number to undefined evaluates to false so I could avoid specifying explicit minimum/maximum values (as in the Wikipedia example) or making HasValue checks (as in James's example).
    • If you have a different approach or a suggestion to simplify this one, please share!
      • And note: I'm interested in algorithmic changes, not tweaks like removing extra parenthesis. :)
    Tags: Miscellaneous Technical
  • A quick programming challenge with money [Counting and enumerating the ways to break a $1 bill]
    Tuesday, December 2nd 2014

    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();
        }
    }
    
    Tags: Miscellaneous Technical
  • Welcome to the new blog, same as the old blog. But different! [Hosting my blog at a new location on a new framework]
    Tuesday, March 25th 2014

    I've had blog since 2006. It's called Delay's Blog and - for a time - was among the top most visited blogs on MSDN. MSDN hosts its blogs on the Telligent platform and has a team of people whose job it is to keep things running. This is a nice perk and that team makes it easy for Microsoft employees to reach a wide audience. I had a good run and I appreciate all their efforts!

    However, I'm something of a control freak and tinkerer and I've always thought it would be nice to own the whole content pipeline. So I decided a number of months ago to migrate this blog to my own site instead. Of course, there are a wealth of good blogging platforms I could have chosen, and lots that are based on the ASP.NET stack I use for the rest of my site.

    But I didn't choose any of them - instead, I've written my own blogging platform based on the Node.js stack. While I'll be the first to acknowledge there's an element of NIH going on [ :) ], there were other considerations:

    • Node.js presents a good learning opportunity for a .NET guy like myself
    • My current job is all about HTML/CSS/JavaScript, so Node.js is a great fit
    • The Node.js community is very active and NPM has a wealth of great packages
    • Though I like typing posts in HTML, I want to experiment with Markdown
    • By writing my own blog, I have complete control (evil laugh...)

    Development happened in small bits and pieces over many weeks and bus rides; the result is the blog you're reading now.

    For the curious, here's what I used to build the site:

    And here are a few of the features I implemented:

    • Post content is HTML or Markdown (original posts were migrated directly)
    • Support for both posts (in the timeline) and pages (separate, linkable content)
    • Responsive design scales/scrolls wide content and moves the sidebar when narrow
    • Database-less implementation makes content easy to deploy with Git
    • Short, deterministic, human-readable URLs for posts and pages
    • Pre-blogging support via automatic "go live" times for posts
    • Automatic server-side syntax highlighting for code samples
    • Simple, quick, semi-relevance-based search across all posts
    • Tags, archives, paged content, RSS, and other standard blog stuff

    For convenience, I've migrated all the existing content from MSDN so I can reference it in one place (here!). For continuity, I've left the posts on MSDN, with comments disabled and a pointer to this site for new content.

    As expected, developing my own blogging platform on a new framework was a great learning experience; I had a good time doing it and am happy to finally have complete control over my (blogging) destiny.

    I even queued up new ideas for blog posts along the way! :)

    Tags: Miscellaneous Node.js
  • Is it still cheating if you come up with the cheat yourself? [Simple code to solve a "sliding pieces" puzzle]
    Tuesday, July 16th 2013

    I was playing around with one of those "rearrange the pieces on the board" puzzles recently and realized I was stumped after unsuccessfully making the same moves over and over and over...:|

    Aside: If you're not familiar with sliding puzzles, the 15-puzzle and Klotski puzzle are both classic examples.

     

    For the particular puzzle I was stuck on, the board looks like:

      ######
     #      #
     #      #
     #      #
    #        #
     #  ##  #
     #  ##  #
      ##  ##

    And uses the following seven pieces:

    AA  BB  CC  DD   E  FF   G
    AA  BB  CC  D   EE   F   GG

    The challenge is to get the 'A' piece from here:

      ######
     #      #
     #      #
     #      #
    #        #
     #AA##  #
     #AA##  #
      ##  ##

    To here:

      ######
     #      #
     #      #
     #      #
    #        #
     #  ##AA#
     #  ##AA#
      ##  ##

    With the starting state:

      ######
     #DDBBFF#
     #DEBBGF#
     #EECCGG#
    #   CC   #
     #AA##  #
     #AA##  #
      ##  ##

    Go ahead and give it a try if you want a challenge! You can make your own puzzle out of paper cutouts or build something with interlocking cubes (which I can say from experience works quite well).

    Aside: I'm not going to reveal where the original puzzle came from because I don't want to spoil it for anyone. But feel free to leave a comment if it looks familiar!

     

    Now, maybe the puzzle's solution is/was obvious to you, but like I said, I was stuck. As it happens, I was in a stubborn mood and didn't want to admit defeat, so I decided to write a simple program to solve the puzzle for me!

    I'd done this before (many years ago), and had a decent sense of what was involved; I managed to bang out the solution below pretty quickly. My goal was to solve the puzzle with minimal effort on my part - so the implementation favors simplicity over performance and there's a lot of room for improvement. Still, it finds the solution in about a second and that's more than quick enough for my purposes.:)

    I've included the complete implementation below. The code should be fairly self-explanatory, so read on if you're interested in one way to solve something like this. Two things worth calling out are that this approach is guaranteed to find the solution with the fewest number of moves and it can handle arbitrarily-shaped pieces and boards - both of which flow pretty naturally from the underlying design.

    There's not much more to say - except that you should feel free to reuse the code for your own purposes!

     

    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;
    
    // Quick (minimally-optimized) solver for a typical "slide the pieces" puzzle.
    // * Implements breadth-first search to guarantee it finds the optimal solution
    // * Detects already-seen states and avoids analyzing them again
    // * Handles arbitrarily shaped pieces and irregular/non-contiguous boards
    // Performance notes:
    // * Board.GetHashCode is called *very* often; keeping it fast is ideal
    // * Board.IsValid is also called frequently and should be quick to run
    // * Board._locations could have the board location removed (it's always 0)
    // * It may be more efficient check validity before creating Board instances
    class SlidePuzzleSolver
    {
        public static void Main()
        {
    #if DEBUG
            // Quick sanity check of the Board class
            var test = new Board();
            Debug.Assert(test.IsValid);
            Debug.Assert(!test.IsSolved);
    #endif
    
            // Stopwatch is handy for measuring/improving performance
            var stopwatch = new Stopwatch();
            stopwatch.Start();
    
            // Initialize
            Board start = new Board();
            Board solved = null;
            var seen = new HashSet<Board>(start); // IEqualityComparer<Board>
            var todo = new Queue<Board>();
            todo.Enqueue(start);
            seen.Add(start);
    
            // Keep going as long as there are unseen states...
            while (0 < todo.Count)
            {
                // Get the next board and process its moves
                var board = todo.Dequeue();
                foreach (var move in board.GetMoves())
                {
                    if (move.IsSolved)
                    {
                        // Solved!
                        solved = move;
                        todo.Clear();
                        break;
                    }
                    if (!seen.Contains(move))
                    {
                        // Enqueue the new state
                        todo.Enqueue(move);
                        seen.Add(move);
                    }
                }
            }
    
            // Write elapsed time to debug window
            stopwatch.Stop();
            Debug.WriteLine("Elapsed time: {0}ms", stopwatch.ElapsedMilliseconds);
    
            // Reverse the solved->start parent chain
            Debug.Assert(null != solved);
            var solution = new Stack<Board>();
            while (null != solved)
            {
                solution.Push(solved);
                solved = solved.Parent;
            }
    
            // Display the solution start->solved
            foreach (var board in solution)
            {
                board.Show();
            }
        }
    
        // Representation of a board and the arrangement of pieces on it
        // (IEqualityComparer<Board> is used by HashSet<Board> above)
        private class Board : IEqualityComparer<Board>
        {
            // Constants for board size
            private const int Width = 10;
            private const int Height = 8;
    
            // Statics for pieces and moves
            private static readonly IReadOnlyList<Piece> _pieces;
            private static readonly IReadOnlyList<int> _deltas;
    
            static Board()
            {
                // Initialize (shared) piece instances
                // Pieces are defined by cells they occupy as deltas from their origin (top-left)
                // Cells are numbered 0..N going from top-left to bottom-right
                // The board is treated as a piece, but never allowed to move
                var pieces = new List<Piece>();
                pieces.Add(new Piece('A', 0, 1, 10, 11)); // Square
                pieces.Add(new Piece('B', 0, 1, 10, 11)); // Square
                pieces.Add(new Piece('C', 0, 1, 10, 11)); // Square
                pieces.Add(new Piece('D', 0, 1, 10));     // 'L'
                pieces.Add(new Piece('E', 1, 10, 11));    // 'L'
                pieces.Add(new Piece('F', 0, 1, 11));     // 'L'
                pieces.Add(new Piece('G', 0, 10, 11));    // 'L'
                pieces.Add(new Piece('#', 2, 3, 4, 5, 6, 7, 11, 18, 21, 28, 31, 38, 40, 49, 51, 54, 55, 58, 61, 64, 65, 68, 72, 73, 76, 77)); // Irregular board shape
                _pieces = pieces.AsReadOnly();
                // Initialize move deltas (each represents one cell left/right/up/down)
                _deltas = new int[] { -1, 1, -Width, Width };
            }
    
            // Piece locations
            private readonly int[] _locations;
    
            // Parent board
            public Board Parent { get; private set; }
    
            // Create starting state of the puzzle
            public Board()
            {
                // Board piece (last element) is always at offset 0
                _locations = new int[] { 52, 14, 34, 12, 22, 16, 26, 0 };
            }
    
            // Create a board from its parent
            private Board(Board parent, int[] locations)
            {
                Parent = parent;
                _locations = locations;
            }
    
            // Get the valid moves from the current board state
            public IEnumerable<Board> GetMoves()
            {
                // Try to move each piece (except for the board)...
                for (var p = 0; p < _pieces.Count - 1; p++)
                {
                    // ... in each direction...
                    foreach (var delta in _deltas)
                    {
                        // ... to create the corresponding board...
                        var locations = (int[])_locations.Clone();
                        locations[p] += delta;
                        var board = new Board(this, locations);
                        // ... and return it if it's valid
                        if (board.IsValid)
                        {
                            yield return board;
                        }
                    }
                }
            }
    
            // Checks whether a board is valid (i.e., has no overlapping cells)
            public bool IsValid
            {
                get
                {
                    // Array to track occupied cells
                    var locations = new bool[Width * Height];
                    // For each piece (including the board)...
                    for (var p = 0; p < _pieces.Count; p++)
                    {
                        var piece = _pieces[p];
                        var offsets = piece.Offsets;
                        // ... for each cell it occupies...
                        for (var o = 0; o < offsets.Length; o++)
                        {
                            // ... check if the cell is occupied...
                            var location = _locations[p] + offsets[o];
                            if (locations[location])
                            {
                                // Already occupied; invalid board
                                return false;
                            }
                            // ... and mark it occupied
                            locations[location] = true;
                        }
                    }
                    return true;
                }
            }
    
            // Checks if the board is solved
            public bool IsSolved
            {
                get
                {
                    // All that matters in *this* puzzle is whether the 'A' piece is at its destination
                    return (56 == _locations[0]);
                }
            }
    
            // Show the board to the user
            public void Show()
            {
                // Clear the console
                Console.Clear();
                // For each piece (including the board)...
                for (var p = 0; p < _pieces.Count; p++)
                {
                    var piece = _pieces[p];
                    // ... for each offset...
                    foreach (var offset in piece.Offsets)
                    {
                        // ... determine the x,y of the cell...
                        var location = _locations[p] + offset;
                        var x = location % Width;
                        var y = location / Width;
                        // ... and plot it on the console
                        Console.SetCursorPosition(x, y);
                        Console.Write(piece.Marker);
                    }
                }
                // Send the cursor to the bottom and wait for a key
                Console.SetCursorPosition(0, Height);
                Console.ReadKey();
            }
    
            // IEqualityComparer<Board> implemented on this class for convenience
    
            // Checks if two boards are identical
            public bool Equals(Board x, Board y)
            {
                return Enumerable.SequenceEqual(x._locations, y._locations);
            }
    
            // Gets a unique-ish hash code for the board
            // XORs the shifted piece locations into an int
            public int GetHashCode(Board b)
            {
                var hash = 0;
                var shift = 0;
                foreach (var i in b._locations)
                {
                    hash ^= (i << shift);
                    shift += 4;
                }
                return hash;
            }
        }
    
        // Representation of a piece, its visual representation, and the cells it occupies
        private class Piece
        {
            public char Marker { get; private set; }
            public int[] Offsets { get; private set; }
    
            public Piece(char marker, params int[] offsets)
            {
                Marker = marker;
                Offsets = offsets;
            }
        }
    }
    Tags: Miscellaneous Technical
  • Back online! [MSDN blogging platform upgraded, comments re-enabled, new content on the way...]
    Tuesday, May 25th 2010

    My last post talked about the upcoming MSDN blogging platform upgrade. That upgrade took place during last week and new posts/comments for this blog were consequently disabled.

    Today, I'm happy to report the upgrade was successfully completed and this blog is back online! I have some new articles in the queue and look forward to posting them soon...

    Thank you for your patience - I hope you enjoy the new blogging platform!

    Tags: Miscellaneous