# Hex Ed — Python — #adventofcode Day 11

**Date:**

**Series:**Advent of Code 2017

Series

This post is part of the series Advent of Code 2017

- Reflections on #aoc2017
- The Halting Problem — Python — #adventofcode Day 25
- Electromagnetic Moat — Rust — #adventofcode Day 24
- Coprocessor Conflagration — Haskell — #adventofcode Day 23
- Sporifica Virus — Rust — #adventofcode Day 22
- Fractal Art — Python — #adventofcode Day 21
- Particle Swarm — Python — #adventofcode Day 20
- A Series of Tubes — Rust — #adventofcode Day 19
- Duet — Haskell — #adventofcode Day 18
- Spinlock — Rust/Python — #adventofcode Day 17
- Permutation Promenade — Julia — #adventofcode Day 16
- Dueling Generators — Rust — #adventofcode Day 15
- Disk Defragmentation — Haskell — #adventofcode Day 14
- Packet Scanners — Haskell — #adventofcode Day 13
- Digital Plumber — Python — #adventofcode Day 12
- > Hex Ed — Python — #adventofcode Day 11 <
- Knot Hash — Haskell — #adventofcode Day 10
- Stream Processing — Haskell — #adventofcode Day 9
- I Heard You Like Registers — Python — #adventofcode Day 8
- Recursive Circus — Ruby — #adventofcode Day 7
- Memory Reallocation — Python — #adventofcode Day 6
- A Maze of Twisty Trampolines — C++ — #adventofcode Day 5
- High Entropy Passphrases — Python — #adventofcode Day 4
- Spiral Memory — Go — #adventofcode Day 3
- Corruption Checksum — Python — #adventofcode Day 2
- Inverse Captcha — Coconut — #adventofcode Day 1
- Advent of Code 2017: introduction

Today’s challenge is to help a program find its child process, which has become lost on a hexagonal grid. We need to follow the path taken by the child (given as input) and calculate the distance it is from home along with the furthest distance it has been at any point along the path.

!!! commentary
I found this one quite interesting in that it was very quick to solve. In fact, I got lucky and my first quick implementation (`max(abs(l))`

below) gave the correct answer in spite of missing an obvious not-so-edge case. Thinking about it, there’s only a ⅓ chance that the first incorrect implementation would give the wrong answer!

```
The code is shorter, so you get more words today. ☺
```

There are a number of different co-ordinate systems on a hexagonal grid (I discovered while reading up after solving it…). I intuitively went for the system known as ‘axial’ coordinates, where you pick two directions aligned to the grid as your x and y axes: note that these won’t be perpendicular. I chose ne/sw as the x axis and se/nw as y, but there are three other possible choices. That leads to the following definition for the directions, encoded as numpy `array`

s because that makes some of the code below neater.

```
import numpy as np
STEPS = {d: np.array(v) for d, v in
[('ne', (1, 0)), ('se', (0, -1)), ('s', (-1, -1)),
('sw', (-1, 0)), ('nw', (0, 1)), ('n', (1, 1))]}
```

`hex_grid_dist`

, given a location `l`

calculates the number of steps needed to reach that location from the centre at `(0, 0)`

. Notice that we can’t simply use the Manhattan distance here because, for example, one step north takes us to `(1, 1)`

, which would give a Manhattan distance of 2. Instead, we can see that moving in the n/s direction allows us to increment or decrement both coordinates at the same time:

- If the coordinates have the same sign: move n/s until one of them is zero, then move along the relevant ne or se axis back to the origin; in this case the number of steps is greatest of the absolute values of the two coordinates
- If the coordinates have opposite signs: move independently along the ne and se axes to reduce each to 0; this time the number of steps is the
*sum*of the absolute values of the two coordinates

```
def hex_grid_distance(l):
if sum(np.sign(l)) == 0: # i.e. opposite signs
return sum(abs(l))
else:
return max(abs(l))
```

Now we can read in the path followed by the child and follow it ourselves, tracking the maximum distance from home along the way.

```
path = input().strip().split(',')
location = np.array((0, 0))
max_distance = 0
for step in map(STEPS.get, path):
location += step
max_distance = max(max_distance, hex_grid_distance(location))
distance = hex_grid_distance(location)
print("Child process is at", location, "which is", distance, "steps away")
print("Greatest distance was", max_distance)
```

## Webmentions

You can respond to this post, "Hex Ed — Python — #adventofcode Day 11", by:
liking, boosting or replying to a tweet or toot that mentions it; or
sending a webmention from your own site to `https://erambler.co.uk/blog/day-11/`

## Comments

*Powered by Cactus Comments 🌵*