The blog of dlaa.me
Archive: December, 2016
  • 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
  • Just another rando with a polyfill [math-random-polyfill.js is a browser-based polyfill for JavaScript's Math.random() that tries to make it more random]
    Thursday, December 8th 2016

    JavaScript's Math.random() function has a well-deserved reputation for not generating truly random numbers. (Gasp!) Modern browsers offer a solution with the crypto.getRandomValues() function that new code should be using instead. However, most legacy scripts haven't been - and won't be - updated for the new hotness.

    I wanted to improve the behavior of legacy code and looked around for a polyfill of Math.random() that leveraged crypto.getRandomValues() to generate output, but didn't find one. It seemed straightforward to implement, so I created math-random-polyfill.js with the tagline: A browser-based polyfill for JavaScript's Math.random() that tries to make it more random.

    You can learn more about math-random-polyfill.js on its GitHub project page which includes the following:

    The MDN documentation for Math.random() explicitly warns that return values should not be used for cryptographic purposes. Failing to heed that advice can lead to problems, such as those documented in the article TIFU by using Math.random(). However, there are scenarios - especially involving legacy code - that don't lend themselves to easily replacing Math.random() with crypto.getRandomValues(). For those scenarios, math-random-polyfill.js attempts to provide a more random implementation of Math.random() to mitigate some of its disadvantages.

    ...

    math-random-polyfill.js works by intercepting calls to Math.random() and returning the same 0 <= value < 1 based on random data provided by crypto.getRandomValues(). Values returned by Math.random() should be completely unpredictable and evenly distributed - both of which are true of the random bits returned by crypto.getRandomValues(). The polyfill maps those values into floating point numbers by using the random bits to create integers distributed evenly across the range 0 <= value < Number.MAX_SAFE_INTEGER then dividing by Number.MAX_SAFE_INTEGER + 1. This maintains the greatest amount of randomness and precision during the transfer from the integer domain to the floating point domain.

    I've included a set of unit tests meant to detect the kinds of mistakes that would compromise the usefulness of math-random-polyfill.js. The test suite passes on the five (most popular) browsers I tried, which leads me to be cautiously optimistic about the validity and viability of this approach. :)

    Tags: Technical Web