Challenge #5 – Napkin Navigation

24 December 2018 Solved Twig Easy

You have been contacted by an anonymous stranger to help meet a very tight deadline. The stranger has only a few hours to visit specific houses and deliver a special package to each of them. You have been given a complex formula in the form of a line of twig code that when executed reveals the next house to visit, however the code is far too cumbersome.

There’s no time to lose, you must reverse engineer a complex formula to something that anyone can calculate, even while steering a herd of reindeer through the dark. All you have to work with is a napkin and your cunning.

{{ (max(range(n, 1, 2)|batch(4)[1]) + n) / 2 % 4 }}

The twig code takes a positive integer n and outputs a number between 0 and 3, each signaling the direction in which to move along the map to reach the next house. You have been given a napkin with the map along with a legend of the directions.

Napkin Navigation Map

Your challenge is to simplify the formula so that for each house number n, the direction to turn can be calculated as quickly as possible. Once you've done that, help the stranger by calculating the route to take through the map of houses.

Challenge

The challenge is to refactor the formula above to its simplest form. Then use it to calculate the path through the map of house numbers, starting at the circled house number and calculating the direction to move for each house number n, ending when you run out of numbers.

Rules

The formula should be refactored so that it is easy to calculate in your head. The formula as well as the route of house numbers should be submitted.

Tips

This is a twig-only challenge that you can literally solve on a napkin, so you don’t even need to leave the dinner table!

Hat tip to Lindsey DiLoreto and Andrew Welch for their suggestions and input.

Solution

Let’s begin by breaking down the twig code into its various components. This will allow us to parse it in the correct order.

{{ (max(range(n, 1, 2)|batch(4)[1]) + n) / 2 % 4 }}

The first part of the formula is a max function which itself contains a range function. Evaluating range(n, 1, 2) results in an array of numbers starting at n and ending at 1 with a step of 2 (the value to increment or decrement, as is the case).

[ n, n-2, n-4, n-6, n-8, n-10, n-12, n-14, ... ]

To this we need to apply the batch filter with a batch size of 4, which will result in an array of arrays (a multi-dimensional array), each containing 4 elements.

[ [ n, n-2, n-4, n-6], [ n-8 , n-10, n-12, n-14 ], ... ]

We then fetch the element at position 1, which is the second element since array indexes always start at 0.

[ n-8 , n-10, n-12, n-14 ]

Now we can finally apply the max function to this array which will give us the number with the largest value, which since the array is in descending order will be the first element, n-8. What we are left with is an algebraic formula which we can simplify one step at a time.

(n - 8 + n) / 2 % 4

(2n - 8) / 2 % 4

2(n - 4) / 2 % 4

n - 4 % 4

The modulo operator % calculates the remainder of an integer division, so any number n % 4 will always result in a number between 0 and 3.

0 % 4 => 0
1 % 4 => 1
2 % 4 => 2
3 % 4 => 3
4 % 4 => 0
5 % 4 => 1
6 % 4 => 2
7 % 4 => 3

Since adding or subtracting 4 from n will not change the result, we can simplify the formula even further.

{{ n % 4 }}

Now all we need to do to calculate the direction in which to move, is plug a number into n and we will get a value between 0 and 3, indicating in which direction to move according to the legend that accompanied the map.

We could take it a step further and use the cycle function to automatically give us a textual representation of the direction to take for any given n.

{{ cycle(['up', 'down', 'left', 'right'], n) }}

Finally, starting at house number 25 and using the formula above results in the following path.

{{ cycle(['up', 'down', 'left', 'right'], 25) }}   // down
{{ cycle(['up', 'down', 'left', 'right'], 37) }}   // down
{{ cycle(['up', 'down', 'left', 'right'], 19) }}   // right
{{ cycle(['up', 'down', 'left', 'right'], 31) }}   // right
{{ cycle(['up', 'down', 'left', 'right'], 33) }}   // down
{{ cycle(['up', 'down', 'left', 'right'], 69) }}   // down
{{ cycle(['up', 'down', 'left', 'right'], 51) }}   // right
{{ cycle(['up', 'down', 'left', 'right'], 35) }}   // right
{{ cycle(['up', 'down', 'left', 'right'], 40) }}   // up
{{ cycle(['up', 'down', 'left', 'right'], 28) }}   // up
{{ cycle(['up', 'down', 'left', 'right'], 24) }}   // up
{{ cycle(['up', 'down', 'left', 'right'], 11) }}   // right

But hey, why use a map scribbled on a scrap of paper when you can encode the map as a multi-dimensional array and write a recursive macro to guide your sleigh? At least that’s what Patrick Harington must have thought when he came up with his fantastical solution, be sure to check it out.

{% set map = [
    [32, 16, 25, 37, 31, 64, 62],
    [47, 67, 37, 14, 77, 58, 11],
    [22, 35, 19, 31, 33, 16, 24],
    [34, 57, 95, 79, 69, 66, 28],
    [82, 65, 88, 14, 51, 35, 40],
    [72, 29, 18, 53, 47, 12, 22],
    [62, 74, 38, 63, 26, 73, 47]
] %}

A happy start to 2019 to everyone!!

Submitted Solutions

  • Patrick Harrington
  • Philip Thygesen