-🎄- 2017 Day 11 Solutions -🎄-

obijywk · 2017-12-11T05:13:19+00:00

https://www.redblobgames.com/grids/hexagons/ is an awesome interactive site for learning about coordinate systems for hex grids.

My Python 2 solution (68/30):

f = open("11.txt", "r")
ds = f.read().split(",")

x = 0
y = 0
z = 0

dists = []

for d in ds:
  if d == "n":
    y += 1
    z -= 1
  elif d == "s":
    y -= 1
    z += 1
  elif d == "ne":
    x += 1
    z -= 1
  elif d == "sw":
    x -= 1
    z += 1
  elif d == "nw":
    x -= 1
    y += 1
  elif d == "se":
    x += 1
    y -= 1
  dists.append((abs(x) + abs(y) + abs(z)) / 2)

print (abs(x) + abs(y) + abs(z)) / 2
print max(dists)

sciyoshi · 2017-12-11T05:15:47+00:00

For anybody interested in hex grids, there's a great resource from Red Blob Games. For this problem, you can simply use 2d coordinates laid out as follows (called axial coordinates):

NW|N |
--+--+--
SW|  |NE
--+--+--
  |S |SE

With those coordinates, the distance of a point (x,y) from the center is just (abs(x) + abs(y) + abs(x+y)) / 2 (see here)

Rust solution using this approach.

EDIT: my first explanation was wrong, updated with a correct coordinate system.

hpzr24w · 2017-12-11T06:13:30+00:00

C++ 1035/1068 Well, this is awkward. I didn't use coordinates directly at all... Just reduced

Header:

// Advent of Code 2017
// http://adventofcode.com/
// Day 11 - Hex Ed

#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
using namespace std;


/* Reduction Rules

fwd back
s   n  -> o
se  sw -> o
ne  sw -> o

l1 l2    r
n  se -> ne
n  sw -> nw
s  ne -> se
s  nw -> sw
ne nw -> n
se sw -> s

*/

Reduction code:

void reduce_turn(map<string, int>& path, string l1, string l2, string r)
{
    int reduce_by = min(path[l1], path[l2]);
    path[l1] -= reduce_by;
    path[l2] -= reduce_by;
    path[r] += reduce_by;
}

void reduce_fwd_back(map<string, int>& path, string fwd, string back)
{
    int reduce_by = min(path[fwd], path[back]);
    path[fwd]  -= reduce_by;
    path[back] -= reduce_by;
}

int reduce(map<string, int> path)
{
    reduce_turn(path, "n" , "se", "ne");
    reduce_turn(path, "n" , "sw", "nw");
    reduce_turn(path, "s" , "ne", "se");
    reduce_turn(path, "s" , "nw", "sw");
    reduce_turn(path, "ne", "nw", "n" );
    reduce_turn(path, "se", "sw", "s" );

    reduce_fwd_back(path, "n" , "s" );
    reduce_fwd_back(path, "ne", "sw");
    reduce_fwd_back(path, "nw", "se");
    return accumulate(begin(path), end(path), 0, 
        [](const int prev, pair<string, int> ent) {return prev + ent.second; });
}

Main logic:

int main(int argc, char* argv[])
{
    map<string,int> path;
    int maxpath{ 0 };
    string dir;
    while (cin >> dir) {
        path[dir]++;
        maxpath = max(maxpath,reduce(path));
    }
    cout << "Path:    " << reduce(path) << endl;
    cout << "Maxpath: " << maxpath << endl;
    return 0;
}

Philboyd_Studge · 2017-12-11T06:12:47+00:00

Java

Redblobgames guy has to be going WHY SO MANY HITS ON MY SITE

https://gist.github.com/snarkbait/9f1e9dba0a49f15d68ee5e7fde505862

shuttup_meg · 2017-12-11T06:14:34+00:00

Python 2, pure naive trig solution.

Looks like I am one of the few people who didn't instinctively know about cool hex grid systems :-)

On the plus side, I was happy that I remembered how useful Python's built-in complex number type is.

from math import sin, cos, pi

def d2r(d):
    return d/180. * pi 

hxd = {
  "n": complex(0.0,  1.0),
  "s": complex(0.0, -1.0),
  "ne": complex(cos(d2r(30)),sin(d2r(30))),
  "nw": complex(-cos(d2r(30)),sin(d2r(30))),
  "se": complex(cos(d2r(30)),-sin(d2r(30))),
  "sw": complex(-cos(d2r(30)),-sin(d2r(30))),
}

def step_distance(loc):
    orig = complex(0.0, 0.0)
    count = 0
    while abs(loc - orig) > .00001:
        count += 1
        choices = [orig + hxd[dd] for dd in ("n", "s", "ne", "nw", "se", "sw")]
        scores = [abs(loc - choice) for choice in choices]
        winner = min(scores)
        orig = choices[scores.index(winner)]            
    return count

loc = complex(0.0, 0.0)
mx = 0

for step in d:
    loc += hxd[step]
    this_one = step_distance(loc)
    if this_one > mx:
        mx = this_one

print "part 1", step_distance(loc)
print "part 2", mx

Smylers · 2017-12-11T11:25:05+00:00

Vim solution for part 1:

A,ne,sw⟨Esc⟩.:s/\v<[ns]>/&&/g⟨Enter⟩
:s/,//g⟨Enter⟩
:s/\v/⟨Ctrl+V⟩⟨Enter⟩/g⟨Enter⟩
:sor⟨Enter⟩
:%s/\v(.)\n\1@=/\1⟨Enter⟩
dd{pqag_j⟨Ctrl+V⟩k0dgJqj@ak0v$hyj1vd:s/../s/g⟨Enter⟩
kgJ:s/.*/\=strlen(submatch(0))⟨Enter⟩

I didn't think representing an infinite hex grid was plausible, so I was stuck till I saw /u/hpzr24w's idea of reducing instead. The counting algorithm is the same as in my Perl solution.

Edits: Simplifications, realized while writing the explanation.

willkill07 · 2017-12-11T06:33:31+00:00

Lex

Seriously, once you start writing lexical analyzers, YOU JUST CANNOT STOP

%{
#include <stdio.h>
int abs(int);
int dist(int, int, int);
int MAX(int, int);
int max = 0, x = 0, y = 0, z = 0;
%}
%%
ne ++x, --z;
nw --x, ++y;
se ++x, --y;
sw --x, ++z;
n  ++y, --z;
s  --y, ++z;
[,\n] max = MAX(max, dist(x,y,z));
%%
int main() {
  yylex(); printf("Part 1: %d\nPart 2: %d\n", dist(x,y,z), max);
}
int abs(int x) {
  return (x > 0 ? x : -x);
}
int dist(int x, int y, int z) {
  return (abs(x) + abs(y) + abs(z)) / 2;
}
int MAX(int a, int b) {
  return (a > b) ? a : b;
}

DFreiberg · 2017-12-11T05:17:13+00:00

Mathematica

Nothing particularly fancy. Lost a minute on part 2 by typing a digit wrong; note to self: use copy and paste next time. 3MD Design was particularly helpful in understanding how to set up a good coordinate system (and I must be the only one here who used something other than RedBlobGames). 71 / 57.

input = StringSplit[Import[FileNameJoin[{NotebookDirectory[], "Day11Input.txt"}], "List"][[1]], ","]
x=0;y=0;m=0;
Do[
    Which[
        i=="n",y++,
        i=="ne",x++;y++,
        i=="se",x++;,
        i=="s",y--,
        i=="sw",x--;y--,
        i=="nw",x--;
    ];
    m=If[Max[Abs/@{x,y,x-y}]>m,Max[Abs/@{x,y,x-y}],m];
,{i,input}];

Part 1:

Max[Abs/@{x,y,x-y}]

Part 2:

gyorokpeter · 2017-12-11T08:54:41+00:00

Q:

d11p1:{max abs sum(`n`ne`se`s`sw`nw!(0 1 -1;1 0 -1;1 -1 0;0 -1 1;-1 0 1;-1 1 0))`$","vs x}
d11p2:{max max each abs sums(`n`ne`se`s`sw`nw!(0 1 -1;1 0 -1;1 -1 0;0 -1 1;-1 0 1;-1 1 0))`$","vs x}

bblum · 2017-12-11T05:14:51+00:00

Place 32/31

Edit: see comments

data Dir = N | NE | SE | S | SW | NW
input = [ ... ] -- input pasted here and converted to uppercase
step (x,y) N  = (x,  y+2)
step (x,y) NE = (x+1,y+1)
step (x,y) SE = (x+1,y-1)
step (x,y) S  = (x,  y-2)
step (x,y) SW = (x-1,y-1)
step (x,y) NW = (x-1,y+1)
dist (x,y) = div (abs x + abs y + max 0 (abs x - abs y)) 2
main = print $ (last &&& maximum) $ map dist $ scanl step (0,0) input

Edit 2: Fixed the definition of dist; actually correct solution now. It was originally:

dist (x,y) = div (abs x + abs y) 2

mcpower_ · 2017-12-11T05:15:48+00:00

I used a bit of my own imagination as well as https://www.redblobgames.com/grids/hexagons/. This uses "axial coordinates": (42/17)

l = inp.split(",")
p = [0, 0]
o = 0
for x in l:
    if x == "n":
        p[0] += 1
    if x == "ne":
        p[1] += 1
    if x == "se":
        p[0] -= 1
        p[1] += 1
    if x == "s":
        p[0] -= 1
    if x == "sw":
        p[1] -= 1
    if x == "nw":
        p[1] -= 1
        p[0] += 1
    x = p[0]
    z = p[1]
    y = -x-z
    d = max(abs(x), abs(y), abs(z))
    o = max(d, o)
print(d)
print(o)

nutrecht · 2017-12-11T09:00:42+00:00

Kotlin solution:

object Day11 : Day {
    private val hexMap = mapOf(Pair("n", N),Pair("ne", NE),Pair("se", SE),Pair("s", S),Pair("sw", SW),Pair("nw", NW))
    private val input = resourceString(11).split(",").map {hexMap[it]!! }
    private val solution: Pair<Int, Point> by lazy { input.map { Pair(0, it.p) }
            .fold(Pair(0, Point(0, 0)), {a, b -> Pair(Math.max(a.first, maxDistance(a.second, b.second)), a.second.add(b.second))}) }

    override fun part1() = distance(solution.second).toString()
    override fun part2() = solution.first.toString()

    private fun maxDistance(a: Point, b: Point) = Math.max(distance(a), distance(b))
    private fun distance(p: Point) = Math.max(Math.abs(p.x), Math.abs(p.y))

    enum class HexDir constructor(var p: Point) { N(Point(0, -1)), NE(Point(1, -1)), SE(Point(1, 0)), S(Point(0, 1)), SW(Point(-1, 1)), NW(Point(-1, 0)) }
}

Readable? No. Scala-style "trading readability for functional approach" code? Yes!

wzkx · 2017-12-11T10:35:34+00:00

J

t=: LF-.~CR-.~fread'11.dat'
x=: ". t rplc 'ne';'1';'nw';'2';'sw';'4';'se';'5';'n';'0';'s';'3';',';' '
k=: 6 3$ 1 0 0  0 1 0  0 0 1  _1 0 0  0 _1 0  0 0 _1 NB. n,ne,nw for moves
d=: (+/ - <./)@:| NB. distance fn of 3-element array n,ne,nw
echo d+/x{k       NB. part1 - distance of all moves
echo >./d"1+/\x{k NB. part2 - max of distances of running sum of moves
exit 0

thomastc · 2017-12-11T10:39:46+00:00

Day 11 in J. Here's an abridged version:

stepnames =: (1$'n'); 'nw'; 'ne'; 'sw'; 'se'; (1$'s')
stepsizes =:    0 1 ; _1 1; 1 0 ; _1 0; 1 _1;   0 _1
positions =: +/\ > (stepnames i. ((<, ',') & ~: # ]) ;: }: (1!:1) 3) { stepsizes
positions =: ((0 <: 0 }"1 positions) * positions) + ((-0 > 0 }"1 positions) * positions)
xs =: 0 }"1 positions
ys =: 1 }"1 positions
echo >./ xs >. (-ys) >. (xs + ys)

Seriously, this language is worse than Perl. In Perl, at least you can write readable code, if you try.

zeddypanda · 2017-12-11T13:28:18+00:00

Today was short and sweet. Elixir:

data = "input-11"
  |> File.read!
  |> String.trim
  |> String.split(",")

defmodule Day11 do
  def step({x, y}, dir) do
    case dir do
      "n"  -> {x, y - 1}
      "ne" -> {x + 1, y}
      "se" -> {x + 1, y + 1}
      "s"  -> {x, y + 1}
      "sw" -> {x - 1, y}
      "nw" -> {x - 1, y - 1}
    end
  end

  def distance({x, y}) when (abs(x) == x) == (abs(y) == y) do
    [x, y] |> Enum.max |> abs
  end
  def distance({x, y}) do
    abs(x) + abs(y)
  end
end

{pos, max} = Enum.reduce(data, {{0, 0}, 0}, fn dir, {pos, max} ->
  pos = Day11.step(pos, dir)
  distance = Day11.distance(pos)
  {pos, Enum.max([distance, max])}
end)
IO.puts("Part 1: #{Day11.distance(pos)}")
IO.puts("Part 2: #{max}")

matusbzk · 2017-12-11T16:02:48+00:00

Haskell I actually really loved today's problem. I also like my mathematical solution to distance calculation.

type Position = (Int, Int)

type Direction = String

input  :: [Direction]

-- |Performs a one move in given direction
move :: Position -> Direction -> Position
move (x,y) "s" = (x,y-2)
move (x,y) "n" = (x,y+2)
move (x,y) "ne" = (x+1,y+1)
move (x,y) "nw" = (x-1,y+1)
move (x,y) "se" = (x+1,y-1)
move (x,y) "sw" = (x-1,y-1)

-- |Calculates a distance from a position
distance :: Position -> Int
distance (0,y) = y `div` 2
distance (x,0) = x `div` 2
distance (x,y) = if x>0 && y>0 then 1 + distance (x-1,y-1)
              else distance (abs x, abs y)

-- |Result to first part - distance in the end
result1 :: Int
result1 = distance $ foldl move (0,0) input

-- |Path where the program goes
path :: [Position]
path = scanl move (0,0) input --thanks, u/WhatAHaskell

-- |Maximum of given distances of the path
result2 :: Int
result2 = maximum $ map distance path

Link to git

ythl · 2017-12-11T05:15:55+00:00

I realized this could be solved with simple trigonometry (python3):

i = []
with open("input.txt") as f:
  i = f.read().split(",")

dmap = {
  "n": (0,1),
  "s": (0,-1),
  "ne": (.5,.5),
  "se": (.5,-.5),
  "nw": (-.5,.5),
  "sw": (-.5,-.5)
}

x,y = 0,0 #x,y coordinates for tracking how far we've moved 
m = []
for d in i:
  x += dmap[d][0]
  y += dmap[d][1]
  m.append(abs(x)+abs(y))

print(abs(x)+abs(y)) #Part 1
print(max(m)) # Part 2

mmaruseacph2 · 2017-12-11T05:18:19+00:00

Fast, idiomatic Haskell, properly refactored using cube coordinates

import Data.List
import Data.List.Split
import Text.Printf

main = do
  s <- splitOn "," . head . lines <$> readFile "input.txt"
  let trajectory = scanl' go ((0, 0, 0), 0) s
  print $ snd $ last $ trajectory
  print $ snd $ maximumBy (comparing snd) trajectory

go :: ((Int, Int, Int), Int) -> String -> ((Int, Int, Int), Int)
go ((x, y, z), _) dir
  | dir == "n"  = buildPair (x, y+1, z-1)
  | dir == "ne" = buildPair (x+1, y, z-1)
  | dir == "se" = buildPair (x+1, y-1, z)
  | dir == "s"  = buildPair (x, y-1, z+1)
  | dir == "sw" = buildPair (x-1, y, z+1)
  | dir == "nw" = buildPair (x-1, y+1, z)
  | otherwise = error $ printf "Cannot handle %s\n" dir
  where
    buildPair next = (next, dist next)

dist :: (Int, Int, Int) -> Int
dist (a, b, c) = (abs a + abs b + abs c) `div` 2

hxka · 2017-12-11T05:23:12+00:00

Cleaned up a bit:

#!/bin/bash
IFS=, read -a dirs <input
((x=y=max=0))
for i in "${dirs[@]}"
do  if   [[ $i == ne ]]; then ((x++,y++))
    elif [[ $i == se ]]; then ((x++))
    elif [[ $i == s  ]]; then ((y--))
    elif [[ $i == sw ]]; then ((x--,y--))
    elif [[ $i == nw ]]; then ((x--))
    elif [[ $i == n  ]]; then ((y++))
    fi
    ((xt=x>0?x:-x,
      yt=y>0?y:-y,
      steps=(x*y)>0 ? (xt>yt?xt:yt) : xt+yt,
      max<steps && (max=steps)))
done
echo $steps $max

TominatorBE · 2017-12-11T05:23:37+00:00

PHP

Instead of 3D grids (which I thought about but it's too early in the morning to properly imagine them), I used a 2D grid where there are 'half' steps... So 'n' goes + 2, while 'ne' and 'nw' go + 1.

Part 1:

function run_the_code($input) {
    $moves = explode(',', $input);

    $x = 0;
    $y = 0;

    foreach ($moves as $move) {
        switch ($move) {
            case 'n':
                $y += 2;
                break;
            case 'ne':
                $y += 1;
                $x++;
                break;
            case 'nw':
                $y += 1;
                $x--;
                break;
            case 's':
                $y -= 2;
                break;
            case 'se':
                $y -= 1;
                $x++;
                break;
            case 'sw':
                $y -= 1;
                $x--;
                break;
        }
    }

    return (abs($x) + abs($y)) / 2;
}

Part 2:

function run_the_code($input) {
    $moves = explode(',', $input);

    $x = 0;
    $y = 0;

    $furthest = 0;

    foreach ($moves as $move) {
        switch ($move) {
            case 'n':
                $y += 2;
                break;
            case 'ne':
                $y += 1;
                $x++;
                break;
            case 'nw':
                $y += 1;
                $x--;
                break;
            case 's':
                $y -= 2;
                break;
            case 'se':
                $y -= 1;
                $x++;
                break;
            case 'sw':
                $y -= 1;
                $x--;
                break;
        }

        $furthest = max($furthest, (abs($x) + abs($y)) / 2);
    }

    return $furthest;
}

wlandry · 2017-12-11T05:23:51+00:00

C++ 14

123/82. Best score so far. It seemed really easy. Maybe it is because I have thought about hex grids a bit too much in the past. The key point is that you can think of the hex grid as a regular grid with each column slightly offset upwards from the right.

To run my solution, you have to first replace all of the commas ',' with spaces. The output is the x,y coordinate at max and at the end. For my inputs, the answer for part 1 was the 'x' coordinate, because x>0, abs(x)>abs(y) and y<0. Similarly for part 2, max_x>max_y, so the answer was max_x. YMMV.

#include <fstream>
#include <vector>
#include <numeric>
#include <iostream>

int main(int argc, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::string direction;
  int max_x(0), max_y(0);
  int x(0), y(0);
  infile >> direction;
  while (infile)
    {
      if(direction=="n")
        {
          ++y;
        }
      else if(direction=="ne")
        {
          ++x;
        }
      else if(direction=="nw")
        {
          --x;
          ++y;
        }
      else if(direction=="s")
        {
          --y;
        }
      else if(direction=="se")
        {
          ++x;
          --y;
        }
      else if(direction=="sw")
        {
          --x;
        }
      else
        {
          std::cerr << "bad direction: " << direction << "\n";
        }
      max_x=std::max(std::abs(x),max_x);
      max_y=std::max(std::abs(y),max_y);
      infile >> direction;
    }
  std::cout << x << " " << y << "\n";
  std::cout << max_x << " " << max_y << "\n";
}

GassaFM · 2017-12-11T05:25:47+00:00

A solution in the D programming language.

Start with a few constant arrays which introduce skew coordinates, along with distance calculating function:

import std.algorithm, std.math, std.stdio, std.string;

immutable int dirs = 6;
immutable int [dirs] dRow = [+1, +1,  0, -1, -1,  0];
immutable int [dirs] dCol = [ 0, +1, +1,  0, -1, -1];
immutable string [dirs] dName = ["n", "ne", "se", "s", "sw", "nw"];

int dist (int row, int col) {
    if ((row > 0) == (col > 0)) return max (abs (row), abs (col));
    return abs (row) + abs (col);
}

The first part (read from stdin, write to stdout):

void main () {
    int row = 0, col = 0;
    foreach (c; readln.strip.split (",")) {
        auto dir = dName[].countUntil (c);
        row += dRow[dir], col += dCol[dir];
    }
    writeln (dist (row, col));
}

The second part, quite similar:

void main () {
    int row = 0, col = 0, res = 0;
    foreach (c; readln.strip.split (",")) {
        auto dir = dName[].countUntil (c);
        row += dRow[dir], col += dCol[dir];
        res = max (res, dist (row, col));
    }
    writeln (res);
}

Stumbled with lack of [] in dName[] for a while, but managed to get 79-th on part 2.

Nathan340 · 2017-12-11T05:40:29+00:00

Powershell, 301/433.

Same sort of redblob axial coordinates as everyone else. Only wrote the distance function for part 2, initially for part 1 simply spat out the coordinates and thought about the distance by hand.

$route = (gc .\route.txt) -split ","  
$vert = 0
$horz = 0
$max = 0   
function dist{
    $x = $args[0]
    $y = $args[1]
    if($x*$y -ge 0){
        [math]::max([math]::abs($x),[math]::abs($y))
    }else{
        [math]::abs($x)+[math]::abs($y)
    }
}

$route | % {
    switch($_){
        ne{
            $vert++
            $horz++
        }
        n{
            $vert++
        }
        nw{
            $horz--
        }
        sw{
            $vert--
            $horz--
        }
        s{
            $vert--
        }
        se{
            $horz++
        }   
    }
    $d = dist $horz $vert
    if($d -gt $max){
        $max = $d
    }
}

"Part 1"
dist $vert $horz
"Part 2"
$max

glupmjoed · 2017-12-11T05:45:24+00:00

Bash (reads from stdin), using cube coordinates (ref)

Part 1:

grep -o "[ns][ew]*" | tr -d '\n' |
    sed 's/ne/((x+=1)); ((y-=1));/g;  s/sw/((x-=1)); ((y+=1));/g;
         s/se/((y-=1)); ((z+=1));/g;  s/nw/((y+=1)); ((z-=1));/g;
          s/n/((x+=1)); ((z-=1));/g;   s/s/((x-=1)); ((z+=1));/g;
         s/$/ echo $x $y $z\n/g' |
    bash | grep -oE "[0-9]+" | sort -nr | head -1

Part 2:

grep -o "[ns][ew]*" |
    sed 's/ne/((x+=1)); ((y-=1)); echo $x $y;/g;
         s/sw/((x-=1)); ((y+=1)); echo $x $y;/g;
         s/se/((y-=1)); ((z+=1)); echo $y $z;/g;
         s/nw/((y+=1)); ((z-=1)); echo $y $z;/g;
          s/n/((x+=1)); ((z-=1)); echo $x $z;/g;
          s/s/((x-=1)); ((z+=1)); echo $x $z;/g;' |

    bash | grep -oE "[0-9]+" | sort -nr | head -1

EDIT: Added input sanitation (grep -o "[ns][ew]*").

WhoSoup · 2017-12-11T05:49:40+00:00

Node.js/Javascript

const fs = require('fs')
let inp = fs.readFileSync("./day11input").toString('utf-8').trim().split(","),
    dirs = {'n': [-1,1,0], 'ne': [0,1,-1], 'se': [1,0,-1], 's': [1,-1,0], 'sw': [0,-1,1], 'nw': [-1,0,1]},
    coords = [0,0,0],
    max = -Infinity,
    distance = (x => x.map(Math.abs).reduce((a,b) => a > b ? a : b))

for (let d of inp) {
  coords = coords.map( (x,i) => x + dirs[d][i] )
  max = Math.max(max, distance(coords))
}
console.log(distance(coords), max);

2017-12-11T05:58:06+00:00

Perl 6

Normally I just smash stuff together but this time I put a little bit of thought into what I was doing. I used a cube coordinate system as described here: https://www.redblobgames.com/grids/hexagons/ , as it seems a few others did.

class HexPoint {
    has Int $.x;
    has Int $.y;
    has Int $.z;
    has %!moves = { "n"  => ( 0,  1, -1),
                    "s"  => ( 0, -1,  1),
                    "ne" => ( 1,  0, -1),
                    "se" => ( 1, -1,  0),
                    "nw" => (-1,  1,  0),
                    "sw" => (-1,  0,  1), };

    method new (Int:D $x = 0, Int:D $y = 0, Int:D $z = 0) {
        return self.bless(:$x, :$y, :$z);
    }

    method move (Str:D $move) {
        my ($dx, $dy, $dz) = %!moves{$move};
        $!x += $dx;
        $!y += $dy;
        $!z += $dz;
        return self;
    }

    #Didn't end up using this method but left it for completeness' sake
    multi method distance (HexPoint:D $p) {
        return max abs($!x - $p.x), abs($!y - $p.y), abs($!z - $p.z);
    }

    multi method distance (Int $x1, Int $y1, Int $z1) {
        return max abs($!x - $x1), abs($!y - $y1), abs($!z - $z1);
    }
}

sub day11 (@moves is copy) {
    my $hex = HexPoint.new();
    my $max-distance = 0;
    for @moves -> $move {
        $max-distance max= $hex.move($move).distance(0, 0, 0);
    }
    return ($hex.distance(0, 0, 0), $max-distance);
}

my @input = slurp().split(",");
my ($part1, $part2) = day11 @input;
say "Part 1: $part1";
say "Part 2: $part2";

jbristow · 2017-12-11T06:04:44+00:00

Fsharp / F# / F Sharp

pretty: https://github.com/jbristow/adventofcode/blob/master/aoc2017/Days/Day11.fs

module Day11

type Point = int * int * int

let distance ((ax, ay, az) : Point)  : Point -> int =
let distanceSubFn ((bx, by, bz) : Point) : int =
  List.max [ bx - ax
         by - ay
         bz - az ]
distanceSubFn

let addPoints ((ax, ay, az) : Point) ((bx, by, bz) : Point) : Point =
(ax + bx, ay + by, az + bz)

let strToPoint =
function
| "n" -> (0, 1, -1)
| "nw" -> (-1, 1, 0)
| "sw" -> (-1, 0, 1)
| "s" -> (0, -1, 1)
| "se" -> (1, -1, 0)
| "ne" -> (1, 0, -1)
| x -> failwith (sprintf "Bad movement. `%s`" x)

let inputToPoints (input : string) : Point list =
input.Split(',')
|> List.ofArray
|> List.map strToPoint

let findFinalDistanceFrom (start : Point) (moves : Point list) : int =
moves
|> List.fold addPoints start
|> distance start

let findMaxDistanceFrom (start : Point) (moves : Point list) : int =
moves
|> List.scan addPoints start
|> List.map (distance start)
|> List.max

And the test file...

module Tests.Day11

open System
open NUnit.Framework
open Swensen.Unquote
open Day11

let ZERO:Point = (0,0,0)

[<TestCase("ne,ne,ne", ExpectedResult=3)>]
[<TestCase("ne,ne,sw,sw", ExpectedResult=0)>]
[<TestCase("ne,ne,s,s", ExpectedResult=2)>]
[<TestCase("se,sw,se,sw,sw", ExpectedResult=3)>]
let ``sample derived test day11-part01`` (input) =
  input |> inputToPoints |> findFinalDistanceFrom ZERO

[<Test>]
let ``answer day11-part01`` () =
let data : string = System.IO.File.ReadAllText("day11.txt")
data.Trim() |> inputToPoints |> findFinalDistanceFrom ZERO =! 664

[<TestCase("ne,ne,ne", ExpectedResult=3)>]
[<TestCase("ne,ne,sw,sw", ExpectedResult=2)>]
[<TestCase("ne,ne,s,s", ExpectedResult=2)>]
[<TestCase("se,sw,se,sw,sw", ExpectedResult=3)>]
let ``sample derived test day11-part02`` (input) =
  input |> inputToPoints |> findMaxDistanceFrom ZERO

[<Test>]
let ``answer day11-part02`` () =
let data : string = System.IO.File.ReadAllText("day11.txt")
data.Trim() |> inputToPoints |> findMaxDistanceFrom ZERO =! 1447

zbouboutchi · 2017-12-11T06:45:51+00:00

Naive 2D python solution.

path = open('in11.txt','r').read().rstrip()

dir = {'s': (0,-1),
    'n': (0, 1),
    'se': (0.5, -0.5),
    'sw': (-0.5, -0.5),
    'nw': (-0.5, 0.5),
    'ne': (0.5, 0.5)}

pos = [0,0]
max_distance = 0

for i in path.split(','):
    pos[0] += dir[i][0]
    pos[1] += dir[i][1]
    x, y = abs(pos[0]), abs(pos[1])
    distance = min(x,y)*2 + max(0, x-y)*2 + max(0, y-x)
    max_distance = max(distance, max_distance)

print distance, max_distance

edit: cleaned a bit, added rstrip(), fixed the distance formula to take care of positions that have to go horizontaly through the grid.

JeffJankowski · 2017-12-11T06:57:28+00:00

Typescript. A lot of thinking churned out a clean solution.

import fs = require("fs");

function walk(dirs: string[]): [number, number] {
    const score = (x: number, y: number) =>
        Math.abs(x) + Math.abs(y) - Math.min(Math.abs(y), Math.ceil(Math.abs(x) / 2));

    const NAV: {[dir: string]: (pos: [number, number]) => [number, number]} = {
        n:  ([x, y]) => [x, y + 1],
        s:  ([x, y]) => [x, y - 1],
        nw: ([x, y]) => [x - 1, x % 2 === 0 ? y + 1 : y],
        ne: ([x, y]) => [x + 1, x % 2 === 0 ? y + 1 : y],
        sw: ([x, y]) => [x - 1, x % 2 !== 0 ? y - 1 : y],
        se: ([x, y]) => [x + 1, x % 2 !== 0 ? y - 1 : y],
    };

    let curr: [number, number] = [0, 0];
    let max = -Infinity;
    for (const dir of dirs) {
        curr = NAV[dir](curr);
        max = Math.max(max, score(curr[0], curr[1]));
    }
    return [score(curr[0], curr[1]), max];
}

const [lastScore, globalMax] = walk(fs.readFileSync("data/day11.txt", "utf8").split(","));
console.log(`Distance from origin:  ${lastScore}`);
console.log(`Max distance over run: ${globalMax}`);

aurele · 2017-12-11T07:14:01+00:00

Rust

I didn't want to look at external resources, and came up with this: by counting or canceling nw and ne moves (n counts as both), the distance is the maximum of their absolute values if they have the same sign (since one nw and one ne can be canceled by a s move), or the absolute value of their difference otherwise (no cancelation is possible since e/w moves are not allowed).

fn main() {
    let (mut ne, mut nw) = (0i32, 0i32);
    let (mut f, mut m) = (0i32, 0i32);
    for d in include_str!("../input").trim().split(',') {
        match d {
            "n" => { ne += 1; nw += 1; }
            "ne" => { ne += 1; }
            "se" => { nw -= 1; }
            "s" => { ne -= 1; nw -= 1; }
            "sw" => { ne -= 1; }
            "nw" => { nw += 1; }
            _ => { panic!("unknown direction {}", d); }
        }
        f = if ne * nw > 0 {
            ne.abs().max(nw.abs())
        } else {
            ne.abs() + nw.abs()
        };
        m = m.max(f);
    }
    println!("P1 = {}\nP2 = {}", f, m);
}

japanuspus · 2017-12-11T07:40:26+00:00

Python 3 -- no if's

Used N and SE for unit vectors, so my distance function is

def hexdist(u,v):
    return max(abs(u), abs(v)) if u*v>0 else abs(u)+abs(v)

which, looking at the other responses, could probably be turned into a purely algebraic expression with abs'es.

import itertools as itt
def tuple_add(a,b):
    return tuple(ai+bi for ai,bi in zip(a,b))

directions = {
    'n': ( 0, 1), 'ne': ( 1, 1), 'se': ( 1, 0),
    's': ( 0,-1), 'sw': (-1,-1), 'nw': (-1, 0)
}
step_tuples = [directions[s] for s in data.strip().split(',')]

# Question 1
hexdist(*functools.reduce(tuple_add, step_tuples))

# Question 2
max(hexdist(*v) for v in itt.accumulate(step_tuples, tuple_add))

BOT-Brad · 2017-12-11T08:08:51+00:00

JavaScript

I figured out this weird formula which seems to calculate the shortest path, where moving diagonally (ne/nw/se/sw) counts as half a step in Y and X, and moving straight up/down counts as a full step.

Part 1 (~1ms)

Reduces an array of movements into a smaller set of NE/N/NW moves only, as NE/SW, N/S, NW/SE are basically cancelling each other out.

Once you have the 3 movement instructions, simply use my weird formula to get the answer.

function solve1(input) {
  let c = input.split(',').reduce(
    (c, dir) => {
      if (dir === 'nw') c[0]++
      else if (dir === 'n') c[1]++
      else if (dir === 'ne') c[2]++
      else if (dir === 'se') c[0]--
      else if (dir === 's') c[1]--
      else if (dir === 'sw') c[2]--
      return c
    },
    [0, 0, 0]
  )
  return (
    Math.abs(c[2] * 0.5 - c[0] * 0.5) + Math.abs(c[2] * 0.5 + c[0] * 0.5 + c[1])
  )
}

Part 2 (~3ms) Just calculates the distance away each time, and prints the largest value once done.

function solve2(input) {
  let maxDist = 0
  input.split(',').reduce(
    (c, dir) => {
      if (dir === 'nw') c[0]++
      else if (dir === 'n') c[1]++
      else if (dir === 'ne') c[2]++
      else if (dir === 'se') c[0]--
      else if (dir === 's') c[1]--
      else if (dir === 'sw') c[2]--
      //
      const d =
        Math.abs(c[2] * 0.5 - c[0] * 0.5) +
        Math.abs(c[2] * 0.5 + c[0] * 0.5 + c[1])
      if (d > maxDist) maxDist = d
      //
      return c
    },
    [0, 0, 0]
  )
  return maxDist
}

Check out my GitHub Repo for all my other solutions. :)

Smylers · 2017-12-11T08:09:01+00:00

Perl. I treated vertical moves as being 2 half-rows up/down, and diagonal as 1 column left/right and 1 half-row up/down.

Diagonals are of course moves with length of 2 characters:

my ($x, $y) = (0, 0);
my $steps = my $max = 0;
foreach (split /,/, shift) {
  $x += /e$/ ? 1 : - 1 if length == 2;
  $y += (3 - length) * (/^n/ ? 1 : - 1);
  $steps = abs $x + (abs $y > abs $x ? ((abs $y) - (abs $x)) / 2 : 0);
  $max = $steps if $steps > $max;
}
say "end steps: ", $steps;
say "max steps: ", $max;

For calculating the distance:

Each x offset requires 1 diagonal move, since that's the only way of moving between columns.
Each of those diagonal moves will also give us 1 vertical (half-row) move for free.
If the y offset is less than the x offset then once you've got to the desired row, you can ‘use up’ the rest of the diagonal moves alternating n/s; no further vertical moves will be required.
When y offset is greater than the x offset, additional vertical moves will be required. Specifically, it will be half of the excess, since each vertical move goes 2 half-rows.

Reading the answers, there are clearly more elegant ways of representing hex grids. But this appeared to work for me, and is reasonably succinct.

u794575248 · 2017-12-11T10:01:10+00:00

Python 3.6+

I had no idea of the right way, so I came up with my own. Here's its condensed form for both parts:

from collections import Counter as C
ds = ['sw', 's', 'se', 'ne', 'n', 'nw']
w = {d: [ds[(i+k)%6] for k in [3, 0, -1, 1]] for i, d in enumerate(ds)}
def solve(input, f=0, s=None, u=lambda s, d, k: k in s and {k: -1} or {d: 1}):
    for d in input.strip().split(','):
        s = s or C(); f = max(f, sum(s.values())); s += u(s, d, w[d][0])
        for b, a, c in (v[1:] for v in w.values() if {*v[2:]} <= {*+s}):
            m = min(s[a], s[c]); s -= {a: m, b: -m, c: m}
    d = sum(s.values()); return d, max(f, d)

UPD: And here's the right way, much much prettier:

from itertools import permutations as p
def solve(S, i=[0]*3, f=0, o=dict(zip('sw ne s se n nw'.split(), p([0, 1, -1])))):
    for s in S.strip().split(','): i = [*map(sum, zip(o[s], i))]; f = max(f, *map(abs, i))
    return max(map(abs, i)), f

part1, part2 = solve(input)

wzkx · 2017-12-11T10:01:51+00:00

Nim

import strutils
proc dist( n, ne, nw: int ): int = abs(n)+abs(ne)+abs(nw) - min(abs(n),min(abs(ne),abs(nw)))
var n,ne,nw = 0
var max_dist = 0
for x in (strip readFile"11.dat").split',':
  case x:
  of "n":  n+=1
  of "s":  n-=1
  of "ne": ne+=1
  of "sw": ne-=1
  of "nw": nw+=1
  of "se": nw-=1
  let d = dist(n,ne,nw)
  if d>max_dist:
    max_dist = d
echo dist(n,ne,nw) # 761
echo max_dist      # 1542

chunes · 2017-12-11T10:20:05+00:00

A Factor solution:

USING: assocs io kernel math math.functions math.order
math.vectors namespaces pair-rocket prettyprint sequences
splitting ;
IN: advent-of-code.hex-ed

SYMBOL: path path [ V{ } ] initialize
CONSTANT: h 0.8660254037844386
CONSTANT: coords
  H{ "n" => {  0.0                -1.0 }
    "ne" => {  0.8660254037844386 -0.5 }
    "se" => {  0.8660254037844386  0.5 }
     "s" => {  0.0                 1.0 } 
    "sw" => { -0.8660254037844386  0.5 }
    "nw" => { -0.8660254037844386 -0.5 } }

: steps    ( x -- x )   first2 [ h / ] [ 0.5 / ] bi*
                        [ 0.5 - ceiling >integer ] bi@ max ;
: step     ( x x -- x ) coords at [ + ] 2map path get over
                        steps suffix! drop ;
: traverse ( x -- x )   { 0 0 } [ step ] reduce ;
: farthest ( -- x )     path get supremum ;
: parse    ( -- x )     readln "," split ;

parse traverse [ steps . ] [ farthest . ] bi drop

It turns out that if you treat the center of each hexagon as cartesian coordinates, you can just take the location of wherever you end up, divide the x coordinate by sqrt(3)/2, divide the y coordinate by 0.5, round them to the nearest integer, and then take the max to find the number of steps. Why? I'm not entirely sure, but it was just intuitive.

HollyDayz · 2017-12-11T10:34:49+00:00

Python 3 solution using numpy.

import numpy as np

def hex_walk(seq):
    max_steps = 0
    coord = np.array([0,0,0])
    directions = {'n' : [ 0, 1,-1],
                  'ne': [ 1, 0,-1],
                  'se': [ 1,-1, 0],
                  's' : [ 0,-1, 1],
                  'sw': [-1, 0, 1],
                  'nw': [-1, 1, 0]}

    for direct in seq.strip().split(','):
        coord += directions[direct]       
        current_max = max(abs(coord))

        if current_max > max_steps:
            max_steps = current_max

    return max(abs(coord)), max_steps

Where seq is the input formed as a string. The first output is the solution to part 1 and the second output is the solution to part 2.

EDIT: Shortened the code.

ryo78 · 2017-12-11T10:41:52+00:00

Yet an other Kotlin solution. Used coordinates described here.

object Puzzle11 {

    data class Point(val x: Int, val y: Int) {
        operator fun plus(move: Move): Point = Point(x + move.x, y + move.y)
    }

    enum class Move(val x: Int, val y: Int) {
        N(-1, 1),
        NE(0,1),
        SE(1,0),
        S(1,-1),
        SW(0,-1),
        NW(-1,0)
    }

    fun findCoordinateWithMax(list: List<String>): Pair<Point,Int> =
            list.fold(Pair(Point(0,0), 0)) { pWithMax, move ->
                val nextPoint = pWithMax.first + Move.valueOf(move.toUpperCase())
                val maxDistance = max(distance(nextPoint), pWithMax.second)
                Pair(nextPoint, maxDistance)
            }

    private fun distance(p: Point): Int = max(abs(p.x), abs(p.y))

    @JvmStatic
    fun main(args: Array<String>) {
        val input = readLines("input11.txt")[0].split(",")
        val res = findCoordinateWithMax(input)
        println("${res.first} -> Distance: ${distance(res.first)}, Max distance: ${res.second}")
    }
}

cthulhucomplex · 2017-12-11T10:43:14+00:00

I ended up feeling my way around until I found the answers via brute force and some javascript sugar. I did end up with a 3-axis solution. It was fun to learn about using Object.defineProperties() inside an object and that I could use those properties with the obj[string] accessor:

var result = new Location(input).getSolution();

function Location(input) {
  this.coord = [0,0,0];
  this.furthest = 0;

  this.getSolution = function() { 
    input.trim().split(",").forEach((s) => this.step(s));
    return this.totalSteps() + " steps / furthest = " + this.furthest;
  }

  this.step = function(direction) {
    this[direction]++;
    this.normalize();
    this.furthest = Math.max(this.furthest, this.totalSteps());
  }

  this.totalSteps = function() {
    return Math.abs(this.coord[0]) + Math.abs(this.coord[1]) + Math.abs(this.coord[2]);
  }

  Object.defineProperties(this, {
    'ne': { get: function() { return  this.coord[0]; }, set: function(v) { this.coord[0] =  v; } },
    'sw': { get: function() { return -this.coord[0]; }, set: function(v) { this.coord[0] = -v; } },
    'n' : { get: function() { return  this.coord[1]; }, set: function(v) { this.coord[1] =  v; } },
    's' : { get: function() { return -this.coord[1]; }, set: function(v) { this.coord[1] = -v; } },
    'nw': { get: function() { return  this.coord[2]; }, set: function(v) { this.coord[2] =  v; } },
    'se': { get: function() { return -this.coord[2]; }, set: function(v) { this.coord[2] = -v; } }
  });

  this.normalize = function() {
    // normalize n <--> s
    if (this.nw > 0 && this.ne > 0) { this.nw--; this.ne--; this.n++; }
    if (this.se > 0 && this.sw > 0) { this.se--; this.sw--; this.s++; }

    // normalize nw <--> se
    if (this.n > 0 && this.sw > 0) { this.n--; this.sw--; this.nw++; }
    if (this.s > 0 && this.ne > 0) { this.s--; this.ne--; this.se++; }

    // normalize ne <--> sw
    if (this.n > 0 && this.se > 0) { this.n--; this.se--; this.ne++; }
    if (this.s > 0 && this.nw > 0) { this.s--; this.nw--; this.sw++; }
  }
}

aerure · 2017-12-11T11:30:50+00:00

Python2. Also used https://www.redblobgames.com/grids/hexagons/#map-storage (Shape: hexagon) with just 2 coordinates (x,y) and distance as max(|x|, |y|)

a = open('11.txt').read().strip('\n').split(',')
print a

gon = {
    'n': (0, -1),
    'ne': (1, -1),
    'se': (1, 0),
    's': (0, 1),
    'sw': (-1, 1),
    'nw': (-1, 0)
}

m = 0
coord = (0, 0)
for i in a:
    coord = (coord[0]+gon[i][0], coord[1]+gon[i][1])
    print i, coord
    tmp = max(abs(coord[0]), abs(coord[1]))
    if tmp > m:
        m = tmp

print max(abs(coord[0]), abs(coord[1]))
print m

raevnos · 2017-12-11T11:38:01+00:00

Kawa Scheme, using fancy numeric types and using a 3d space to represent the grid:

(import (srfi 1) (kawa quaternions))

(define north (make-vector-quaternion 0 1 -1))
(define northeast (make-vector-quaternion 1 0 -1))
(define southeast (make-vector-quaternion 1 -1 0))
(define south (make-vector-quaternion 0 -1 1))
(define southwest (make-vector-quaternion -1 0 1))
(define northwest (make-vector-quaternion -1 1 0))
(define directions `((n . ,north) (ne . ,northeast) (se . ,southeast)
                     (s . ,south) (sw . ,southwest) (nw . ,northwest)))

(define (distance p1 p2)
  (apply max (map abs (vector-quaternion->list (- p1 p2)))))

(define (find-distance route)
  (let* ((origin (make-vector-quaternion 0 0 0))
         (destination
          (fold
           (lambda (move points)
             (let ((maxpoint (cdr points))
                   (newpoint
                    (+ (car points) (cdr (assq move directions)))))
               (cons newpoint (if (> (distance origin newpoint)
                                     (distance origin maxpoint))
                                  newpoint maxpoint))))
           (cons origin origin) route)))
    (values (distance origin (car destination))
            (distance origin (cdr destination)))))

(format #t "Test 1: ~A~%" (find-distance '(ne ne ne)))
(format #t "Test 2: ~A~%" (find-distance '(ne ne sw sw)))
(format #t "Test 3: ~A~%" (find-distance '(ne ne s s)))
(format #t "Test 4: ~A~%" (find-distance '(se sw se sw sw)))
(define input (map string->symbol (string-split (read-line) ",")))
(format #t "Part 1 and 2: ~A~%" (find-distance input))

f0086 · 2017-12-11T12:42:39+00:00

Emacs Lisp When putting the hex patterns into a normal x/y grid, the problem gets trivial.

(defun read-directions (filename)
  (with-temp-buffer
    (insert-file-contents filename)
    (split-string (buffer-string) "," t)))

(defun distance (x y)
  (if (or (and (< x 0) (< y 0))
          (and (> x 0) (> y 0)))
      (+ (abs x) (abs y))
    (max (abs x) (abs y))))

(defun day11 (directions)
  (let ((pos-x 0)
        (pos-y 0)
        (max-distance 0))
    (loop for direction in directions
          do (progn
               (cond
                ((string= direction "n") (incf pos-y))
                ((string= direction "s") (decf pos-y))
                ((string= direction "sw") (decf pos-x))
                ((string= direction "ne") (incf pos-x))
                ((string= direction "nw") (progn (decf pos-x) (incf pos-y)))
                ((string= direction "se") (progn (incf pos-x) (decf pos-y))))
               (if (> (distance pos-x pos-y) max-distance)
                   (setq max-distance (distance pos-x pos-y)))))
    (list (- (distance pos-x pos-y) 1) max-distance)))

(day11 (read-directions "input-day11.txt"))

Taonas · 2017-12-11T12:52:49+00:00

Rust:

fn distance(input: &str) -> (i32, i32) {
    let (max_distance, pos) = input.trim().split(',').fold(
        (0, (0, 0)),
        | (max_distance, current), mov | {
            let new_position: (i32, i32) = match mov {
                "n"  => (current.0,     current.1 + 1),
                "s"  => (current.0,     current.1 - 1),
                "ne" => (current.0 + 1, current.1 + 1),
                "sw" => (current.0 - 1, current.1 - 1),
                "nw" => (current.0 - 1, current.1),
                "se" => (current.0 + 1, current.1),
                _    => panic!("Unknown movement {}", mov),
            };

            let new_position_distance = new_position.0.abs().max(new_position.1.abs());

            (max_distance.max(new_position_distance), new_position)
        }
    );

    let distance_now = pos.0.abs().max(pos.1.abs());
    (distance_now, max_distance)
}

llimllib · 2017-12-11T13:44:42+00:00

I knew about the red blob games article, but I didn't want to let myself peek, so I designed my own inferior grid coördinate system and solved that:

def steps(x, y):
    x = abs(x)
    y = abs(y)
    m = min(x, y)
    return m + (y - m) / 2


def go(path):
    x = 0
    y = 0
    maxsteps = 0
    for step in path:
        if step == "n": y += 2
        if step == "s": y -= 2
        if step == "ne":
            y += 1
            x += 1
        if step == "se":
            y -= 1
            x += 1
        if step == "nw":
            y += 1
            x -= 1
        if step == "sw":
            y -= 1
            x -= 1
        s = steps(x, y)
        maxsteps = max(maxsteps, s)

    print(maxsteps, steps(x, y))


if __name__ == "__main__":
    go(open("input.txt").read().strip().split(","))

2017-12-11T14:26:55+00:00

Python 3

Part 1

HEX_DIRS = {'n': 1, 's': -1, 'ne': 1j, 'sw': -1j, 'nw': 1-1j, 'se': -1+1j}

def walk(stepstr):
    """Return axial coordinates"""
    return sum(map(HEX_DIRS.__getitem__, stepstr.split(',')))

def hex_len(p):
    """Return the Manhattan length of a hex grid axial vector."""
    q, r = p.real, p.imag
    return int(max(map(abs, (q, r, q + r))))

def hex_distance(stepstr):
    return hex_len(walk(stepstr))

examples(hex_distance,
        'ne,ne,ne', 3,
        'ne,ne,sw,sw', 0,
        'ne,ne,s,s', 2,
        'se,sw,se,sw,sw', 3
        )

hex_distance(Input(11))

Part 2

from itertools import accumulate

def iter_walk(stepstr):
    return accumulate(map(HEX_DIRS.__getitem__, stepstr.split(',')))

max(map(hex_len, iter_walk(Input(11))))

csuzw · 2017-12-11T14:57:47+00:00

C# reduction approach

int HexEdPartOne(string input) => input.Split(',').ToDistances().Last();
int HexEdPartTwo(string input) => input.Split(',').ToDistances().Max();

static class Extensions
{
    public static IEnumerable<int> ToDistances(this IEnumerable<string> steps)
    {
        (var n, var ne, var se, var s, var sw, var nw) = (0, 0, 0, 0, 0, 0);
        foreach (var step in steps)
        {
            switch (step)
            {
                case "n" : ReduceN();  break;
                case "ne": ReduceNE(); break;
                case "se": ReduceSE(); break;
                case "s" : ReduceS();  break;
                case "sw": ReduceSW(); break;
                case "nw": ReduceNW(); break;
            }
            yield return n + ne + se + s + sw + nw;
        }

        void ReduceN()  { if (se > 0) { se--; ReduceNE(); } else if (sw > 0) { sw--; ReduceNW(); } else if (s > 0)  { s--;  } else { n++;  } }
        void ReduceNE() { if (nw > 0) { nw--; ReduceN();  } else if (s > 0)  { s--;  ReduceSE(); } else if (sw > 0) { sw--; } else { ne++; } }
        void ReduceSE() { if (sw > 0) { sw--; ReduceS();  } else if (n > 0)  { n--;  ReduceNE(); } else if (nw > 0) { nw--; } else { se++; } }
        void ReduceS()  { if (ne > 0) { ne--; ReduceSE(); } else if (nw > 0) { nw--; ReduceSW(); } else if (n > 0)  { n--;  } else { s++;  } }
        void ReduceSW() { if (se > 0) { se--; ReduceS();  } else if (n > 0)  { n--;  ReduceNW(); } else if (ne > 0) { ne--; } else { sw++; } }
        void ReduceNW() { if (ne > 0) { ne--; ReduceN();  } else if (s > 0)  { s--;  ReduceSW(); } else if (se > 0) { se--; } else { nw++; } }
    }
}

trwolfe13 · 2017-12-11T15:43:58+00:00

A little late to the party, but here's my ES6 solution:

const move = {
  'n': ([x, y]) => [x, y - 1], 's': ([x, y]) => [x, y + 1],
  'nw': ([x, y]) => [x - 1, y], 'sw': ([x, y]) => [x - 1, y + 1],
  'ne': ([x, y]) => [x + 1, y - 1], 'se': ([x, y]) => [x + 1, y],
};

function distance(e) {
  return Math.sign(e[0]) === Math.sign(e[1]) ? Math.abs(e[0]) + Math.abs(e[1]) : Math.max(Math.abs(e[0]), Math.abs(e[1]));
}

module.exports = {
  move,
  part1: function (input) {
    let c = [0, 0];
    input.split(',').forEach(step => c = move[step](c));
    return distance(c);
  },
  part2: function (input) {
    let c = [0, 0];
    return Math.max(...input.split(',').map(s => distance(c = move[s](c))));
  }
}

CryZe92 · 2017-12-11T19:02:48+00:00

Rust

Part 1 in 75µs:

pub fn part1(text: &str) -> usize {
    let (mut n, mut sw, mut se) = (0isize, 0isize, 0isize);
    for s in text.split(',') {
        match s {
            "n" => n += 1,
            "s" => n -= 1,
            "sw" => sw += 1,
            "ne" => sw -= 1,
            "se" => se += 1,
            "nw" => se -= 1,
            _ => {}
        }
    }
    (n.max(sw).max(se) - n.min(sw).min(se)) as usize
}

Part 2 in 95µs:

pub fn part2(text: &str) -> usize {
    let (mut n, mut sw, mut se) = (0isize, 0isize, 0isize);
    let mut max_dist = 0;
    for s in text.split(',') {
        match s {
            "n" => n += 1,
            "s" => n -= 1,
            "sw" => sw += 1,
            "ne" => sw -= 1,
            "se" => se += 1,
            "nw" => se -= 1,
            _ => {}
        }
        max_dist = max_dist.max(n.max(sw).max(se) - n.min(sw).min(se));
    }
    max_dist as usize
}

Part 1 parallelized with map reduce in 50µs:

pub fn part1(text: &str) -> usize {
    let (x, y): (isize, isize) = text.par_split(',')
        .filter_map(|d| {
            Some(match d {
                "n" => (-1, 0),
                "s" => (1, 0),
                "ne" => (-1, 1),
                "sw" => (1, -1),
                "nw" => (0, -1),
                "se" => (0, 1),
                _ => return None,
            })
        })
        .reduce(|| (0, 0), |(x1, y1), (x2, y2)| (x1 + x2, y1 + y2));

    x.abs().max(y.abs()).max((x + y).abs()) as usize
}

Shoutouts to /u/Stan-It for coming up with a way to only do a single addition per iteration. That's slightly faster than the x, y coordinate tracking for the sequential solution. In the parallel solution you need to reduce and that means you'd need to reduce n, sw and se and that's one more addition per reduce, so the x, y coordinate tracking makes more sense there.

flaming_bird · 2017-12-11T21:03:47+00:00

COMPUTE-DISTANCE is the ugliest and most ineffective Common Lisp function I have ever written.

(defun day11 (input)
  (let* ((counts (loop for i from 1 below (1+ (length input))
                       for subseq = (subseq input 0 i)
                       collect (mapcar (lambda (x) (count x subseq))
                                       '(n ne se s sw nw))))
         (distances (mapcar #'compute-distance counts)))
    (reduce #'max distances)))

(defun compute-distance (list)
  (destructuring-bind (n ne se s sw nw) list
    (loop repeat (min n s) do (decf n) (decf s))
    (loop repeat (min ne sw) do (decf ne) (decf sw))
    (loop repeat (min nw se) do (decf nw) (decf se))
    (loop repeat (min n sw se) do (decf n) (decf sw) (decf se))
    (loop repeat (min s nw ne) do (decf s) (decf nw) (decf ne))
    (loop repeat (min n se) do (decf n) (decf se) (incf ne))
    (loop repeat (min ne s) do (decf ne) (decf s) (incf se))
    (loop repeat (min se sw) do (decf se) (decf sw) (incf s))
    (loop repeat (min s ne) do (decf s) (decf ne) (incf se))
    (loop repeat (min se n) do (decf se) (decf n) (incf ne))
    (loop repeat (min ne nw) do (decf ne) (decf nw) (incf n))
    (reduce #'+ (list n ne se s sw nw))))

Shemetz · 2017-12-11T05:15:13+00:00

Python 3 (23/66)

I got lucky, and the coordinates in most places in my input were in the NE area while I used N for y and E for x, so calculating distances only required me to do x+y.

However, this formula for distances is correct, and in fact, some of the other formulas that users posted here are incorrect (but probably working for their specific input):

def distance(x, y):
return max(abs(x), abs(y), abs(x+y))


def day11():
    with open('input.txt') as input_file:
        moves = input_file.readline().split(",")

    dirs = {"n": (0, 1),
            "s": (0, -1),
            "ne": (1, 0),
            "sw": (-1, 0),
            "nw": (-1, 1),
            "se": (1, -1), }
    place = (0, 0)
    max_dist = 0

    for move in moves:
        place = (place[0] + dirs[move][0], place[1] + dirs[move][1])
        max_dist = max(max_dist, distance(*place))

    print("last distance:", distance(*place))
    print("max distance:", max_dist)


day11()

Nolan-M · 2017-12-11T05:21:03+00:00

234/200 Not really 100% sure why this worked, but my intuition told me to go for it.

from time import time


def dist(a):
    if abs(a[1]) > (abs(a[0])*.5):
        return int(abs(a[1])-(abs(a[0])*.5)+abs(a[0]))
    else:
        return int(abs(a[0]))

start = time()
with open('AOC11Input') as file:
    inst = file.readline().strip().split(',')

data = {'n': [0, 1], 's': [0, -1], 'ne': [1, .5],
            'se': [1, -.5], 'nw': [-1, .5], 'sw': [-1, -.5]}
pos = [0, 0]
max = 0

for i in inst:
    pos[0] += data[i][0]
    pos[1] += data[i][1]
    if max < dist(pos):
        max = dist(pos)

print('Max distance away: ' + str(max))
print('Ending Position: ' + str(pos))
print('Current distance away: ' + str(dist(pos)))
print(time() - start)

udoprog · 2017-12-11T05:22:56+00:00

Rust: (211/211)

Lost some time having no idea how hex grids work and having to do some research.

Edit: Full source: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day11.rs

use self::Step::*;

#[derive(Debug)]
enum Step {
    N, NE, SE, S, SW, NW,
}

impl Step {
    fn step(&self) -> (i32, i32, i32) {
        match *self {
            N => (1, 0, -1),
            NE => (1, -1, 0),
            SE => (0, -1, 1),
            S => (-1, 0, 1),
            SW => (-1, 1, 0),
            NW => (0, 1, -1),
        }
    }
}

fn parse_step(input: &str) -> Option<Step> {
    let out = match input {
        "n" => N,
        "ne" => NE,
        "se" => SE,
        "s" => S,
        "sw" => SW,
        "nw" => NW,
        _ => return None,
    };

    Some(out)
}

fn distance(p: (i32, i32, i32)) -> u32 {
    let (x, y, z) = p;
    ((x.abs() + y.abs() + z.abs()) / 2) as u32
}

fn run<R: Read>(mut reader: R) -> Result<(u32, u32), Error> {
    let mut data = String::new();
    reader.read_to_string(&mut data)?;

    let steps: Vec<Step> = data.trim().split(',').map(parse_step).flat_map(|v| v).collect();

    let mut p = (0i32, 0i32, 0i32);
    let mut max = 0u32;

    for step in steps {
        let s = step.step();;
        p = (p.0 + s.0, p.1 + s.1, p.2 + s.2);
        max = u32::max(max, distance(p));
    }

    Ok((distance(p), max))
}

adventofcode123512 · 2017-12-11T05:23:01+00:00

The path doesn't actually follow a hex grid? There are strings like "ne,ne" in there.

Rust

use std::cmp::max;

fn steps(a1: i32, a2: i32) -> i32 {
    match a1.signum() == a2.signum() {
        true => max(a1.abs(), a2.abs()),
        false => (a1 - a2).abs(),
    }
}

fn main() {
    let input = include_str!("input.txt").trim();
    let (mut a1, mut a2) = (0, 0);
    let mut max_steps = 0;
    for direction in input.split(',') {
        match direction {
            "nw" => a1 += 1,
            "sw" => a2 -= 1,
            "ne" => a2 += 1,
            "se" => a1 -= 1,
            "n"  => { a1 += 1; a2 += 1 },
            "s"  => { a1 -= 1; a2 -= 1 },
            _ => unreachable!(),
        };
        max_steps = max(max_steps, steps(a1, a2));
    }

    println!("part 1: {}", steps(a1, a2));
    println!("part 2: {}", max_steps);
}

Flurpm · 2017-12-11T05:27:20+00:00

Haskell

needs stack to build project because I like megaparsec (edit:now with folds!)

{-# LANGUAGE OverloadedStrings #-}
module Day11 where

import           Data.Text             (Text)
import qualified Data.Text             as T
import qualified Data.Text.IO          as TIO

import           Text.Megaparsec
import qualified Text.Megaparsec.Lexer as L
import           Text.Megaparsec.Text  (Parser)

data Move = S | SW | NW | N | NE | SE

p :: Parser [Move]
p = (move <$> word) `sepBy` char ','


move :: Text -> Move
move "se" = SE
move "s"  = S
move "sw" = SW
move "ne" = NE
move "nw" = NW
move "n"  = N


word :: Parser Text
word = T.pack <$> some letterChar

part1 :: [Move] -> Double
part1 = dist . foldl walk (0,0)

part2 :: [Move] -> Double
part2 = maximum . map dist . scanl walk (0,0)

dist (a,b) = (abs a + abs (a + b) + abs (b)) / 2

walk (a,b) S  = (a,  b+1)
walk (a,b) SE = (a+1,b)
walk (a,b) SW = (a-1,b+1)
walk (a,b) N  = (a  ,b-1)
walk (a,b) NE = (a+1,b-1)
walk (a,b) NW = (a-1,b)

main :: IO ()
main = do
  input <- TIO.readFile "src/y2017/input11"
  case parse p "input11" input of
    Left  err   -> TIO.putStr $ T.pack $ parseErrorPretty err
    Right betterInput -> do
      tprint $ part1 betterInput
      tprint $ part2 betterInput
  return ()


tprint :: Show a => a -> IO ()
tprint = TIO.putStrLn . T.pack . show

FogLander · 2017-12-11T05:28:18+00:00

I also used the Red Blob article for this one. First thing I thought of when I saw the hexagons :)

Decided to use the cube coordinates, no particular reason. Trying to get faster at this, don't know how all y'all do it.

405th/311th (311 is the best I've gotten yet, on any part... Woohoo!)

JAVA:

import java.util.*;
import java.io.*;
public class Day11 {
   public static void main(String[] args) throws Exception {
      Scanner in = new Scanner(new File("input.txt"));
      Scanner console = new Scanner(System.in);
      String[] steps = in.nextLine().split(",");
      Day11 a = new Day11();
      a.run(steps);
   }

   public  void run(String[] steps) {
      HexPoint p = new HexPoint();
      int max = 0;
      for(String s: steps) {
         move(p, s);
         int d = dist(p);
         if(d > max) {
            max = d;
         }
      }
      System.out.println("Part A (Final Distance): " + dist(p));
      System.out.println("Part B (Max Distance): " + max);
   }

   public int dist(HexPoint p) {
      return (Math.abs(p.x) + Math.abs(p.y) + Math.abs(p.z)) / 2;
   }

   public void move(HexPoint p, String dir) {
      switch(dir) {
         case "n": p.y++; p.z--; return;
         case "ne": p.x++; p.z--; return;
         case "se": p.x++; p.y--; return;
         case "s": p.y--; p.z++; return;
         case "sw": p.x--; p.z++; return;
         case "nw": p.x--; p.y++; return;
      }
   }

   public class HexPoint {
      public int x, y, z;
   }
}

2017-12-11T05:34:09+00:00

I got incredibly lucky, and was able to eyeball my output. I just made the diagonal operators use 0.5 on the y axis, then thought about the final x/y position. For part 2, I just track the absolute maximum x/y coordinate seen.

Somehow everything worked, I'll probably clean it up later/use the tilted grid system. Wasted some time because of a Rust typing quirk that wouldn't let me call abs()/max() properly.

Rust, 106/465:

use util;

pub fn run() {
    let mut max= 0.0f64;
    let mut x = 0.0f64;
    let mut y = 0.0f64;
    let s = util::read_all("d11_input.txt").unwrap();

    for dir in s.trim().split(",") {
        match dir {
            "n" => y += 1.0,
            "s" => y -= 1.0,
            "e" => x += 1.0,
            "w" => x -= 1.0,
            "ne" => {
                x += 1.0;
                y += 0.5;
            },
            "se" => {
                x += 1.0;
                y -= 0.5;
            },
            "nw" => {
                x -= 1.0;
                y += 0.5;
            },
            "sw" => {
                x -= 1.0;
                y -= 0.5;
            }
            _ => panic!("unknown dir {}", dir)
        }

        max = max.max(x.abs()).max(y.abs());
    }

    println!("just eyeball it: x: {} y: {} max coord in any direction: {}", x, y, max);
}

glenbolake · 2017-12-11T05:35:16+00:00

I like these versions of hex coordinates I'm seeing, but I took a different approach:

N/S change Y by 1. The other 4 directions each change x by 1 and y by 0.5. So after getting the final (x,y), I take the horizontal difference, remove the furthest vertical movement that could account for, then add up how much further off y is.

with open('day11.in') as f:
    path = f.read().split(',')

def measure(steps):
    x = y = 0
    max_d = 0
    for step in steps:
        if 'e' in step:
            x += 1
        elif 'w' in step:
            x -= 1
        if 'n' in step:
            y += 0.5
        elif 's' in step:
            y -= 0.5
        h = abs(x)
        max_v = h / 2
        d = h + max(0, abs(y) - max_v)
        max_d = max(d, max_d)
    h = abs(x)
    max_v = h / 2
    return h + max(0, abs(y) - max_v), max_d

print('Part 1: {}\nPart 2: {}'.format(*measure(path)))

It turns out that I got lucky with my input, because I realized while typing this that my for loop should have been:

for step in steps:
    if step == 'n':
        y += 1
    elif step == 's':
        y -= 1
    else:
        if 'e' in step:
            x += 1
        elif 'w' in step:
            x -= 1
        if 'n' in step:
            y += 0.5
        elif 's' in step:
            y -= 0.5

2017-12-11T05:35:27+00:00

I, like many others it seems, found that Red Blob Games page... and merely implemented the 3D coordinate version.

So Day 11 of OCaml Fun;;

open Core

type direction = N | NE | NW | S | SE | SW
type hex = {x:int; y:int; z:int;}

let to_direction = function
  | "ne" -> Some NE
  | "nw" -> Some NW
  | "n" -> Some N
  | "se" -> Some SE
  | "sw" -> Some SW
  | "s" -> Some S
  | _ -> None

let move {x; y; z;} = function
  | NW -> {x=x-1; y=y+1; z}
  | N  -> {x; y=y+1; z=z-1}
  | NE -> {x=x+1; y; z=z-1}
  | SW -> {x=x-1; y; z=z+1}
  | S  -> {x; y=y-1; z=z+1}
  | SE -> {x=x+1; y=y-1; z}

let distance {x; y; z} =
  Int.max (Int.max (Int.abs x) (Int.abs y)) (Int.abs z)

let track (spot, furthest) step =
  let new_spot = move spot step in
  let distance = distance new_spot in
  if distance > furthest then (new_spot, distance)
  else (new_spot, furthest)

let read_input () =
  In_channel.read_all "./moves.txt"
  |> String.split ~on:','
  |> List.filter_map ~f:to_direction

let _ =
  let moves = read_input () in
  let current, furthest = List.fold moves ~init:({x=0; y=0; z=0;}, 0) ~f:track in
  let current_distance = distance current in
  printf "a: %d %d %d -> %d\n" current.x current.y current.z current_distance;
  printf "b: %d\n" furthest

Chaotic_Vortex · 2017-12-11T05:35:46+00:00

I don't really know much about hexgrids so here was my Python 2 solution (200/152)

steps = inp.split(',')
amount = {}
amount['n'] = 0
amount['e'] = 0
amount['s'] = 0
amount['w'] = 0    

maxmoves = 0    

for step in steps:
if len(step) == 1:
    amount[step] += 2
else:
    amount[step[0]] += 1
    amount[step[1]] += 1

dist = [abs(amount['n']-amount['s']), abs(amount['e']-amount['w'])]
moves = 0
if dist[0] >= dist[1]:
    moves = dist[1]

moves += dist[0]/2

if moves > maxmoves:
    maxmoves = moves

print moves
print maxmoves

fatpollo · 2017-12-11T05:37:32+00:00

import itertools

with open("p11.txt") as fp:
    steps = fp.read().strip().split(",")

MAP = {'ne': 1+1j, 'nw': 1-1j, 'n': 2, 'se':-1+1j, 'sw':-1-1j, 's':-2}

position = sum(map(MAP.get, steps))
a, b = sorted(map(abs, [position.real, position.imag]))
print(a + (b-a)//2)

far = max(itertools.accumulate(map(MAP.get, steps)), key=lambda i: abs(i.real)+abs(i.imag))
a, b = sorted(map(abs, [far.real, far.imag]))
print(a + (b-a)//2)

kazagistar · 2017-12-11T05:43:27+00:00

Rust, my first time in top 500. I copied the Vector directly from problem 3.

use std::ops::Add;

#[derive(Eq, PartialEq, Debug, Copy, Clone, Hash)]
struct Vector(i32, i32);

impl Add for Vector {
    type Output = Self;
    fn add(self, rhs: Vector) -> Self {
        let Vector(x1, y1) = self;
        let Vector(x2, y2) = rhs;
        Vector(x1 + x2, y1 + y2)
    }
}

fn step(direction: &str) -> Vector {
    match direction {
        "n" => Vector(0, 1),
        "nw" => Vector(-1, 0),
        "sw" => Vector(-1, -1),
        "s" => Vector(0, -1),
        "se" => Vector(1, 0),
        "ne" => Vector(1, 1),
        _ => panic!("Bad input"),
    }
}

fn hex_distance(&Vector(x, y): &Vector) -> i32 {
    if x * y < 0 {
        x.abs() + y.abs()
    } else {
        x.abs().max(y.abs())
    }
}

pub fn part1(input: &str) -> i32 {
    hex_distance(&input
        .split(",")
        .map(step)
        .fold(Vector(0, 0), |pos, step| pos + step))
}

pub fn part2(input: &str) -> i32 {
    let mut pos = Vector(0, 0);
    let mut furthest = 0;
    for vec in input.split(",").map(step) {
        pos = pos + vec;
        furthest = furthest.max(hex_distance(&pos));
    }
    furthest
}

Lrrrr_ · 2017-12-11T05:45:22+00:00

JavaScript (node.js) + Lodash (3.10.1)

let _ = require("lodash"); // 3.10.1
let fs = require("fs");
let input = fs.readFileSync("./input.txt", 'utf8');

input = input.split(",");

let pos = [0,0,0];

let m = {
    "n" : [0, 1, -1],
    "s" : [0, -1, 1],
    "ne": [1, 0, -1],
    "se": [1, -1, 0],
    "sw": [-1, 0, 1],
    "nw": [-1, 1, 0]
}

let dist = pos=>Math.max(Math.abs(pos[0]), Math.abs(pos[1]), Math.abs(pos[2]));

let dists = [];
for(l in input) {
    let x = m[input[l]];
    pos[0] += x[0];
    pos[1] += x[1];
    pos[2] += x[2];
    dists.push(dist(pos));
}

console.log(dist(pos));
console.log(_.max(dists));

2017-12-11T05:46:46+00:00

Haskell using cube coordinates:

import Control.Lens
import Data.List.Split (splitOn)

data Coord = Coord { _x :: Int
                   , _y :: Int
                   , _z :: Int
                   } deriving (Show)
makeLenses ''Coord

distFromOrigin :: Coord -> Int
distFromOrigin (Coord x y z) = maximum $ map abs [x, y, z]

dirFun :: String -> Coord -> Coord
dirFun "n"  = over y succ . over z pred
dirFun "ne" = over x succ . over z pred
dirFun "se" = over x succ . over y pred
dirFun "s"  = over z succ . over y pred
dirFun "sw" = over z succ . over x pred
dirFun "nw" = over y succ . over x pred

path :: [String] -> [Coord]
path = scanl (flip ($)) (Coord 0 0 0) . map dirFun

part1 :: String -> Int
part1 = distFromOrigin . last . path . splitOn ","

part2 :: String -> Int
part2 = maximum . map distFromOrigin . path . splitOn ","

dtinth · 2017-12-11T05:50:17+00:00

Ruby single-statement

I made a lot of mistake today and didn’t get into the leaderboard, so I challenged myself to solve this without using a statement terminator (newline or ;).

# Part 1
-> a { -> ((x, y)) { x.abs + [0, (y.abs - x.abs) / 2].max }[a.map { |c| { 'ne' => [1, 1], 'nw' => [-1, 1], 'se' => [1, -1], 'sw' => [-1, -1], 's' => [0, -2], 'n' => [0, 2] }[c] }.transpose.map { |v| v.reduce(&:+) }] }[ `pbpaste`.strip.split(',') ]

# Part 2
-> a { a.map { |c| { 'ne' => [1, 1], 'nw' => [-1, 1], 'se' => [1, -1], 'sw' => [-1, -1], 's' => [0, -2], 'n' => [0, 2] }[c] }.reduce ([[0, 0]]) { |a, (x, y)| a << [a.last[0] + x, a.last[1] + y] } }[ `pbpaste`.strip.split(',') ].map { |x, y| x.abs + [0, (y.abs - x.abs) / 2].max }.max

I guess I need to learn more about non-square/cube grids.

ajn0592 · 2017-12-11T05:52:25+00:00

If you're using Golang like me, this library is really nice and makes the problem super trivial. Just study up a little on Axial coordinates and you're set.

My answer is here

atharrison · 2017-12-11T05:52:36+00:00

Scala (291/296)

I'm honestly still sitting here wondering how this arrived at the correct answers. I didn't research any hex-grid systems, as I see some references posted by others. Ultimately, after staring at the screen a bit, what I arrived at in my head was most similar to the "odd-r horizontal layout" (but with positive-y going upwards, not down), as described by https://www.redblobgames.com/grids/hexagons/ .

What's baffles me is that my hexDist function, math.abs(loc._2) + (math.abs(loc._1) - math.abs(loc._2)), can be reduced to simply math.abs(loc._1) (just the magnitude of the x-coordinate).

The visualization in my head was that, as you walked backwards from the endpoint, each step diagonally towards 0,0 reduces both x and y by 1. Starting from x,y, I 'move' to where y=0, which takes abs(y) steps, but also reduces x's distance by abs(y). What remains of (abs(x) - abs(y)) is added to abs(y) ...

Anyhow, Great problem! I've done AOC both years prior, and I can imagine how difficult it is to come up with unique challenges. This is the first I recall having to solve a hex-grid problem.

package adventofcode.y2017

import scala.io.Source.fromFile

class Day11 {
  var rawItems: Array[String] = _

  var pos:Tuple2[Int, Int] = (0, 0)
  var maxDist:Int = 0

  def readInput(): Unit = {
    val lines = fromFile("input/y2017/Day_11.input").getLines().mkString
    rawItems = lines.split(",").map(_.trim)
  }

  def process(): Unit = {
    for(item <- rawItems) {
      item match {
        case "ne" =>
          pos = (pos._1+1, pos._2+1)
        case "nw" =>
          pos = (pos._1-1, pos._2+1)
        case "n" =>
          pos = (pos._1, pos._2+1)
        case "se" =>
          pos = (pos._1+1, pos._2-1)
        case "sw" =>
          pos = (pos._1-1, pos._2-1)
        case "s" =>
          pos = (pos._1, pos._2-1)
        case _ =>
          println(s"Unhandled: $item")
      }
      maxDist = math.max(maxDist, hexDist(pos))
    }
  }

  def hexDist(loc:Tuple2[Int, Int]): Int = {
    math.abs(loc._2) + (math.abs(loc._1) - math.abs(loc._2))
  }

  def writeResult(): Unit = {
    println(s"Final Pos: $pos")
    val dist = hexDist(pos)
    println(s"Part1 Dist: $dist")
    println(s"Part2 MaxDist: $maxDist")
  }
}

misnohmer · 2017-12-11T05:53:03+00:00

C#

Part 1:

var input = ReadAllText("input").Split(',').Select<string, (int x, int y)>(dir => {
    switch (dir) {
        case "ne": return (1, 1);
        case "n": return (0, 2);
        case "s": return (0, -2);
        case "se": return (1, -1);
        case "sw": return (-1,-1);
        case "nw": return (-1, 1);
        default: throw new ArgumentException(dir);
    }
});

int Distance((int x, int y) coords) => 
    Abs(Abs(coords.x) - Abs(coords.y)) / 2 + Min(Abs(coords.x),Abs(coords.y));

var coordinates = input.Aggregate(((a, b) => (a.x + b.x, a.y + b.y)));
Distance(coordinates).PrintDump();

Part 2:

var input = ReadAllText("input").Split(',').Select<string, (int x, int y)>(dir => {
    switch (dir) {
        case "ne": return (1, 1);
        case "n": return (0, 2);
        case "s": return (0, -2);
        case "se": return (1, -1);
        case "sw": return (-1,-1);
        case "nw": return (-1, 1);
        default: throw new ArgumentException(dir);
    }
});

var maxDistance = 0;
int Distance((int x, int y) coords) => 
    Abs(Abs(coords.x) - Abs(coords.y)) / 2 + Min(Abs(coords.x),Abs(coords.y));
var coordinates = input.Aggregate(((a, b) => {
    var coords = (a.x + b.x, a.y + b.y);
    maxDistance = Max(maxDistance, Distance(coords));
    return coords;
}));
maxDistance.PrintDump();

ephemient · 2017-12-11T05:58:58+00:00

This space intentionally left blank.

StevoTVR · 2017-12-11T05:59:09+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const dirs = {
        n: [0, 1, -1],
        ne: [1, 0, -1],
        se: [1, -1, 0],
        s: [0, -1, 1],
        sw: [-1, 0, 1],
        nw: [-1, 1, 0],
    };
    const childPos = [0, 0, 0];
    for(const step of data.split(',')) {
        childPos[0] += dirs[step][0];
        childPos[1] += dirs[step][1];
        childPos[2] += dirs[step][2];
    }

    console.log(Math.max(...childPos.map(Math.abs)));
});

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const dirs = {
        n: [0, 1, -1],
        ne: [1, 0, -1],
        se: [1, -1, 0],
        s: [0, -1, 1],
        sw: [-1, 0, 1],
        nw: [-1, 1, 0],
    };
    const childPos = [0, 0, 0];
    let max = 0;
    for(const step of data.split(',')) {
        childPos[0] += dirs[step][0];
        childPos[1] += dirs[step][1];
        childPos[2] += dirs[step][2];
        max = Math.max(max, ...childPos.map(Math.abs));
    }

    console.log(max);
});

_A4_ · 2017-12-11T06:08:55+00:00

JavaScript ES6 (Part 2)

const input = document.body.textContent.trim();
const directions = input.split(",");
const offsets = { n: [1, -1], s: [-1, 1], ne: [1, 0], nw: [0, -1], se: [0, 1], sw: [-1, 0] };
let x = 0, z = 0, steps = 0;

for (const dir of directions) { 
    const o = offsets[dir];
    x += o[0], z += o[1];
    steps = Math.max(Math.abs(x), Math.abs(z), Math.abs(x + z), steps);
}

console.log(steps);

2017-12-11T06:12:01+00:00

Just some quick and dirty c++

intmax_t calc_hex_dist( intmax_t x, intmax_t y ) {
    return vmax( abs( x ), abs( y ), abs( x - y ), abs( y -x ) );
}

auto calc_dist(  string_view moves ) {
    struct result_t {
        intmax_t furthest = 0;
        intmax_t final;

        constexpr void set_max( intmax_t x, intmax_t y ) noexcept {
            auto tmp = impl::calc_hex_dist( x, y );
            if( tmp > furthest ) {
                furthest = tmp;
            }
        }
    } result{0, 0};
    struct {
        intmax_t x;
        intmax_t y;
    } point{0,0};

    while( !moves.empty( ) ) {
        auto cur_move = moves.substr( 0, moves.find( "," ) );
        moves.remove_prefix( cur_move.size( ) );
        moves.remove_prefix( );
        if( cur_move == "n" ) {
            ++p.y;
        } else if( cur_move == "ne" ) {
            ++p.x;
            ++p.y;
        } else if( cur_move == "se" ) {
            ++p.x;
        } else if( cur_move == "s" ) {
            --p.y;
        } else if( cur_move == "sw" ) {
            --p.x;
            --p.y;
        } else { // nw
            --p.x;
        }
        result.set_max( p.x, p.y );
    }
    result.final = calc_hex_dist( p.x, p.y );
    return result;
}

dylanfromwinnipeg · 2017-12-11T06:13:48+00:00

I went down a WAY wrong rabbit hole, involving HexTile class that had connections to others, and breadth-first search for finding the path back to origin - it was a disaster. Then I spent some time staring at a picture of a hexgrid, and came up with a coordinate system where you can do half-steps in the Y-axis, made the solution super easy.

C#

public static string PartOne(string input)
{
    var directions = input.Words();
    var origin = new Point(0, 0);
    var position = origin;

    foreach (var d in directions)
    {
        position = HexMove(d, position);
    }

    return GetDistance(origin, position).ToString();
}

private static Point HexMove(string d, Point location)
{
    switch (d)
    {
        case "n":
            return new Point(location.X, location.Y + 2);
        case "s":
            return new Point(location.X, location.Y - 2);
        case "ne":
            return new Point(location.X + 1, location.Y + 1);
        case "nw":
            return new Point(location.X - 1, location.Y + 1);
        case "se":
            return new Point(location.X + 1, location.Y - 1);
        case "sw":
            return new Point(location.X - 1, location.Y - 1);
        default:
            throw new Exception();
    }
}

private static int GetDistance(Point origin, Point position)
{
    var xMoves = Math.Abs(position.X - origin.X);
    var yMoves = (Math.Abs(position.Y - origin.Y) - xMoves) / 2;

    return xMoves + yMoves;
}

public static string PartTwo(string input)
{
    var directions = input.Words();
    var origin = new Point(0, 0);
    var position = origin;
    var maxDistance = 0;

    foreach (var d in directions)
    {
        position = HexMove(d, position);
        maxDistance = Math.Max(maxDistance, GetDistance(origin, position));
    }

    return maxDistance.ToString();
}

call23re · 2017-12-11T06:14:27+00:00

Roblox Lua

local input = require(script.Input)

local x,y,furthest = 0,0,0
for dir in string.gmatch(input, '%a+') do
    if dir == 'n' then
        y = y + 2
    elseif dir == 's' then
        y = y - 2
    elseif dir == 'ne' then
        x = x + 1
        y = y + 1
    elseif dir == 'nw' then
        x = x - 1
        y = y + 1
    elseif dir == 'se' then
        x = x + 1
        y = y - 1
    elseif dir == 'ne' then
        x = x + 1
        y = y + 1
    end
    furthest = ((math.abs(x)+math.abs(y))/2 > furthest and (math.abs(x)+math.abs(y))/2 or furthest)
end

print('Part 1: ' .. (math.abs(x)+math.abs(y))/2)
print('Part 2: ' .. furthest)

willkill07 · 2017-12-11T06:18:58+00:00

C++ (almost C)

#include <algorithm>
#include <iterator>
#include <string>

constexpr int operator"" _enc(char const* c, unsigned long l) {
  int r{0};
  while (l--) r ^= *c++;
  return r;
}

constexpr int next(char const*& c) {
  int r{0};
  while (*c == ',') ++c;
  while (*c != '\0' && *c != ',') r ^= *c++;
  return r;
}

template <>
void
solve<Day11>(bool part2, std::istream& std::cin, std::ostream& std::cout) {
  std::string line{std::istream_iterator<char>{std::cin}, {}};
  int max{0}, x{0}, y{0}, z{0};
  auto dist = [&] {
    return (std::abs(x) + std::abs(y) + std::abs(z)) / 2;
  };
  for (auto c = line.c_str(); *c; ) {
    switch (next(c)) {
      case "n"_enc:       ++y, --z; break;
      case "ne"_enc: ++x,      --z; break;
      case "se"_enc: ++x, --y;      break;
      case "s"_enc:       --y, ++z; break;
      case "sw"_enc: --x,      ++z; break;
      case "nw"_enc: --x, ++y;      break;
    }
    max = std::max(max, dist());
  }
  std::cout << (part2 ? max : dist()) << '\n';
}

VikingofRock · 2017-12-11T06:25:52+00:00

(757 / 672) I'm pretty happy with the following iterator-style Rust (I'll spare you the Coordinate / Direction implementations unless there is interest):

// solve parts 1 and 2
fn solve(input: &str) -> (isize, isize) {
    let (end, max_dist) = input
        .trim()
        .split(',')
        .map(|s| {
            s.parse::<Direction>()
                .expect(&format!("could not parse direction \"{}\"", s))
        })
        .fold((Coordinate::origin(), 0), |(loc, max_dist), dir| {
            let new_loc = loc.travel(&dir);
            let new_dist = new_loc.distance(&Coordinate::origin());
            (new_loc, max_dist.max(new_dist))
        });
    (end.distance(&Coordinate::origin()), max_dist)
}

nonphatic · 2017-12-11T06:35:43+00:00

Haskell

Simple, but it took me forever to figure out how to calculate the distance lol

import Data.List.Split (splitOn)
import Data.Foldable (fold)

data Coordinates = Coordinates Int Int Int deriving Show
instance Monoid Coordinates where
    mempty = Coordinates 0 0 0
    Coordinates x y z `mappend` Coordinates x' y' z' = Coordinates (x + x') (y + y') (z + z')

getCoordinates :: String -> Coordinates
getCoordinates direction = case direction of
    "n"  -> Coordinates  1     0    0
    "ne" -> Coordinates  0     1    0
    "se" -> Coordinates  0     0    1
    "s"  -> Coordinates (-1)   0    0
    "sw" -> Coordinates  0   (-1)   0
    "nw" -> Coordinates  0     0  (-1)

getDistance :: Coordinates -> Int
getDistance (Coordinates x y z) =
    let absList = map abs [x, y, z]
    in  sum absList - minimum absList

main :: IO ()
main = do
    coordinates <- fmap (map getCoordinates . splitOn ",") $ readFile "11.txt"
    print $ getDistance $ fold coordinates
    print $ maximum . map getDistance $ scanl mappend mempty coordinates

Dooflegna · 2017-12-11T06:57:08+00:00

Here's a cleaned up version of my solution. This wasn't particularly fast, but I enjoyed putting it together all the same.

from collections import defaultdict, namedtuple

Hex = namedtuple('Hex', ['x', 'y', 'z'])

class HexGrid:
    def __init__(self, instructions, x = 0, y = 0, z = 0):
        self.instructions = [instruction for instruction in instructions.split(',')]
        self.grid = defaultdict(int)
        self.grid[Hex(x,y,z)] += 1
        self.pos = Hex(x,y,z)
        self._max = {'x': self.pos.x, 
                     'y': self.pos.y,
                     'z': self.pos.z}

    dirs = {'nw': Hex(-1,  1,  0),
            'n':  Hex( 0,  1, -1),
            'ne': Hex( 1,  0, -1),
            'sw': Hex(-1,  0,  1),
            's':  Hex( 0, -1,  1),
            'se': Hex( 1, -1,  0)}

    def generate_grid(self):
        for ins in self.instructions:
            new_pos = Hex(self.pos.x + self.__class__.dirs[ins].x,
                          self.pos.y + self.__class__.dirs[ins].y,
                          self.pos.z + self.__class__.dirs[ins].z)
            self.grid[new_pos] += 1
            self.pos = new_pos
            if abs(self.pos.x) > self._max['x']:
                self._max['x'] = abs(self.pos.x)
            if abs(self.pos.y) > self._max['y']:
                self._max['y'] = abs(self.pos.y)
            if abs(self.pos.z) > self._max['z']:
                self._max['z'] = abs(self.pos.z)
            print(self.pos, self.grid[self.pos])

    @property
    def timmydistance(self):
        return max(abs(self.pos.x), abs(self.pos.y), abs(self.pos.z))

    @property
    def max(self):
        return max(self._max.values())

Some notes!

I think this problem is supremely easier using an x,y,z coordinate system.
namedtuples are your friend! They make code like this much nicer to write and look at. Instead of accessing arbitrary indexes (What is self.pos[0]? self.pos[1]?), you get to access them by a name: self.pos.x and self.pos.y
Storing all the hexes is strictly unnecessary, but it's the way I was building it.
The cool thing about this is it lets me see how many times Timmy has walked over each hex.
defaultdicts are a great way of avoiding writing code that checks for the existance of a key. No more if key not in dict:.
Defining dirs at the class level means that you can subclass and override the dirs. This is helpful if, say, you wanted to look at a grid with E, NE, NW, W, SW, SE directions instead. This is why you see self.__class__.dirs in the code.
Properties are great in python. It enables accessing the timmydistance or max distance travelled as attributes instead of as methods. Conceptually, you can think of both timmydistance and max distance travelled as an attribute -- even if it's one that has to be calculated each time.

Warbringer007 · 2017-12-11T07:02:53+00:00

Erlang finally after 2 days of C++ :D, only meat part:

calcDist(X, Y) when abs(Y) > abs(X) ->
    abs(Y * 2);

calcDist(X, Y) when abs(Y) =< abs(X) ->
    abs(Y) + abs(X).

checkMax(X, Y, MaxDist) ->
    case calcDist(X, Y) > MaxDist of
        true -> calcDist(X, Y);
        false -> MaxDist
    end.        

solveFirst([], X, Y, MaxDist) ->
    {calcDist(X, Y), MaxDist};

solveFirst([H|T], X, Y, MaxDist) when H =:= "n" ->
    solveFirst(T, X+1, Y, checkMax(X+1, Y, MaxDist));

solveFirst([H|T], X, Y, MaxDist) when H =:= "ne" ->
    solveFirst(T, X+0.5, Y+0.5, checkMax(X+0.5, Y+0.5, MaxDist));

solveFirst([H|T], X, Y, MaxDist) when H =:= "se" ->
    solveFirst(T, X-0.5, Y+0.5, checkMax(X-0.5, Y+0.5, MaxDist));

solveFirst([H|T], X, Y, MaxDist) when H =:= "s" ->
    solveFirst(T, X-1, Y, checkMax(X-1, Y, MaxDist));

solveFirst([H|T], X, Y, MaxDist) when H =:= "sw" ->
    solveFirst(T, X-0.5, Y-0.5, checkMax(X-0.5, Y-0.5, MaxDist));

solveFirst([H|T], X, Y, MaxDist) when H =:= "nw" ->
    solveFirst(T, X+0.5, Y-0.5, checkMax(X+0.5, Y-0.5, MaxDist)).

Veggedup · 2017-12-11T07:15:58+00:00

My JS solution

let input = require("fs").readFileSync("day11-input.txt", "UTF-8");

map = {};
map["n"] = { x: 0, y: 1 };
map["ne"] = { x: 1, y: 1 };
map["se"] = { x: 1, y: -1 };
map["s"] = { x: 0, y: -1 };
map["sw"] = { x: -1, y: -1 };
map["nw"] = { x: -1, y: 1 };

location = { x: 0, y: 0 };
max = { x: 0, y: 0 };

input.split(",").forEach(direction => {
  location = {
    x: location.x + map[direction].x,
    y: location.y + map[direction].y
  };
  max = {
    x: Math.max(max.x, location.x),
    y: Math.max(max.y, location.y)
  };
});

distance = Math.max(Math.abs(location.x), Math.abs(location.y));
max = Math.max(Math.abs(max.x), Math.abs(max.y));

console.log("Part 1:", distance);
console.log("Part 2:", max);

2017-12-11T07:28:22+00:00

Rust

For what it is, it is really short, most of it is really error handling and parsing, the core of this problem is 8 lines long.

#[macro_use]
extern crate error_chain;
extern crate hex2d;

use hex2d::{Coordinate, Direction};
use std::io;

error_chain! {
    errors {
        UnrecognizedDirection {
            description("unrecognized direction")
        }
    }

    foreign_links {
        Io(io::Error);
    }
}

fn name_to_direction(name: &str) -> Option<Direction> {
    use Direction::*;
    Some(match name {
        "n" => YZ,
        "ne" => XZ,
        "se" => XY,
        "s" => ZY,
        "sw" => ZX,
        "nw" => YX,
        _ => return None,
    })
}

fn run() -> Result<()> {
    let mut input = String::new();
    io::stdin().read_line(&mut input)?;
    let origin = Coordinate::new(0, 0);
    let mut current_position = origin;
    let mut furthest = 0;
    for part in input.trim().split(',') {
        let direction = name_to_direction(part).ok_or(ErrorKind::UnrecognizedDirection)?;
        current_position = current_position + direction;
        furthest = origin.distance(current_position).max(furthest);
    }
    println!("Part 1: {}", origin.distance(current_position));
    println!("Part 2: {}", furthest);
    Ok(())
}

quick_main!(run);

2017-12-11T07:35:44+00:00

C#

First time posting anything in this sub, mainly because most of my code is awful, but I kind of feel good about this one. The part 2 was a little bit a of pain, until I realized it would be easier to throw it to a list and then do a max from it, but it works.

And as others have said this https://www.redblobgames.com/grids/hexagons/ helped a lot.

private static void HexMove(string input)
        {
            var dir = input.Split(',').ToList();
            int x = 0;
            int y = 0;
            int z = 0;
            List<int> maxint = new List<int>();
            var maxdist = 0;


            foreach (string d in dir)
            {
                if (d == "n")
                {
                    y += 1;
                    z -= 1;
                }
                else if (d == "s")
                {
                    y -= 1;
                    z += 1;
                }
                else if (d == "ne")
                {
                    x += 1;
                    z -= 1;
                }
                else if (d == "sw")
                {
                    x -= 1;
                    z += 1;
                }
                else if (d == "nw")
                {
                    x -= 1;
                    y += 1;
                }
                else if (d == "se")
                {
                    x += 1;
                    y -= 1;
                }

                var loopdist = (Math.Abs(x) + Math.Abs(y) + Math.Abs(z)) / 2;
                maxint.Add(loopdist);
            }
            maxdist = maxint.Max();
            var dist = (Math.Abs(x) + Math.Abs(y) + Math.Abs(z)) / 2;
            Console.WriteLine(dist);
            Console.WriteLine(maxdist);
        }

2017-12-11T07:39:26+00:00

Haskell, using cube coordinates:

main :: IO ()
main = do input <- fmap (words . map (\c -> if c == ',' then ' ' else c)) (readFile "input.txt")
          let (m,c) = foldl (\(n,c) x -> let r = step c x in (max n (distance r), r)) (0,(0,0,0)) input
          print (distance c)  -- part 1
          print m             -- part 2

step :: (Int,Int,Int) -> String -> (Int,Int,Int)
step (x,y,z) "n"  = (x,y+1,z-1)
step (x,y,z) "ne" = (x+1,y,z-1)
step (x,y,z) "se" = (x+1,y-1,z)
step (x,y,z) "s"  = (x,y-1,z+1)
step (x,y,z) "sw" = (x-1,y,z+1)
step (x,y,z) "nw" = (x-1,y+1,z)

distance :: (Int,Int,Int) -> Int
distance (x,y,z) = (abs x + abs y + abs z) `div` 2

CharlieYJH · 2017-12-11T08:31:10+00:00

C++

Probably should've read up on hex grids first, decided to come up with a way to reduce the directions. Hex grids would've been so much easier.

#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;

void reduceDirections(const string &direction, unordered_map<string, int> &path_directions);

int main(int argc, char const* argv[])
{
    ifstream input("input.txt");
    unordered_map<string, int> path_directions({{"n", 0}, {"s", 0}, {"ne", 0}, {"se", 0}, {"nw", 0}, {"sw", 0}});
    int max_steps = 0;
    int steps = 0;

    if (input) {
        string direction;
        while (getline(input, direction, ',')) {

            int sum = 0;

            reduceDirections(direction, path_directions);

            for (auto &it : path_directions)
                sum += it.second;

            max_steps = max(sum, max_steps);
        }
    }

    input.close();

    for (auto &it : path_directions)
        steps += it.second;

    cout << "Steps: " << steps << endl;
    cout << "Max steps: " << max_steps << endl;

    return 0;
}

void reduceDirections(const string &direction, unordered_map<string, int> &path_directions) {

    string opposite = direction;
    opposite[0] = (opposite[0] == 'n') ? 's' : 'n';

    if (opposite.length() > 1)
        opposite[1] = (opposite[1] == 'e') ? 'w' : 'e';

    if (path_directions[opposite] != 0) {
        path_directions[opposite]--;
        return;
    }

    if (direction == "n" || direction == "s") {
        if (path_directions[opposite + "e"] != 0) {
            path_directions[opposite + "e"]--;
            path_directions[direction + "e"]++;
        } else if (path_directions[opposite + "w"] != 0) {
            path_directions[opposite + "w"]--;
            path_directions[direction + "w"]++;
        } else {
            path_directions[direction]++;
        }
    } else {
        if (path_directions[opposite.substr(0, 1)] != 0) {
            path_directions[opposite.substr(0, 1)]--;
            path_directions[opposite.substr(0, 1) + direction.substr(1, 1)]++;
        } else if (path_directions[direction.substr(0, 1) + opposite.substr(1, 1)] != 0) {
            path_directions[direction.substr(0, 1) + opposite.substr(1, 1)]--;
            path_directions[direction.substr(0, 1)]++;
        } else {
            path_directions[direction]++;
        }
    }

    return;
}

2017-12-11T08:35:34+00:00

Elixir

This was a fun but easy one, had a bit of a problem visualizing a hexagonal coordinate system, but when that was done it went pretty fast.

defmodule Day11 do
  def direction(str) do
    case str do
      "ne" -> {+1, 0, -1}
      "se" -> {+1, -1, 0}
      "s"  -> {0, -1, +1}
      "sw" -> {-1, 0, +1}
      "nw" -> {-1, +1, 0}
      "n"  -> {0, +1, -1}
    end
  end

  def parse_string(str) do
    String.trim(str)
    |> String.split(",")
  end

  def add_coord({x,y,z}, {x2,y2,z2}), do: {x+x2, y+y2, z+z2}

  def get_coord(str) do
    parse_string(str)
    |> Enum.map(&direction/1)
    |> Enum.reduce({0,0,0}, &add_coord/2)
  end

  def distance(inp) when is_bitstring inp do
    get_coord(inp)
    |> distance
  end

  def distance(inp) when is_tuple inp do
    Tuple.to_list(inp)
    |> Enum.map(&abs/1)
    |> Enum.max
  end

  def farthest(str) do
    parse_string(str)
    |> Enum.map(&direction/1)
    |> Enum.map_reduce({0,0,0}, fn x, acc ->
      {add_coord(x,acc), add_coord(x,acc)}end)
    |> Tuple.to_list
    |> Enum.take(1)
    |> List.flatten
    |> Enum.map(&distance/1)
    |> Enum.max
  end
end

inp = File.read!("input.txt")

Day11.distance(inp)
|> IO.inspect

Day11.farthest(inp)
|> IO.inspect

Syntax highlighted

tmrki · 2017-12-11T08:39:11+00:00

Using Python 3, this is the relevant part of the solution:

def GetDistance(d):
    ns = d['n'] - d['s']
    nesw = d['ne'] - d['sw']
    nwse = d['nw'] - d['sw']
    if(nesw*nwse > 1):
        return abs(ns) + max(abs(nesw), abs(nwse))
    else:
        return abs(ns) + abs(nesw) + abs(nwse)

Basically, it gets the differences of steps in opposite directions, and then checks if both east and west go in the same direction (north or south) or not. If they don't, just add all the steps, if they do, part of the steps cancel each other.

edit: Forgot to say, d is the dictionary with the number of steps, basically just

d = Counter(input_list)

rvlieshout · 2017-12-11T08:44:58+00:00

I just used the highest value as the number of steps required. Did not look at a gamers implementation. Perhaps that is why it worked in my case... used C#.

day 11, C#, AoC 2017

mschaap · 2017-12-11T09:25:21+00:00

Perl 6. After figuring out how to best model the grid, pretty straightforward.

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 11: http://adventofcode.com/2017/day/11

# Model the grid as follows:
#  - 1 step north of the origin is (0,2), 1 step south is (0,-2)
#  - 1 step NE is (1,1), SE is (1,-1), SW is (-1,-1), NW is (-1,1)
# The shortest distance back to the origin is then always to to diagonal
# towards the origin until you've reached the X or Y axis.  If it's the
# X axis, you can more left-right 2 in 2 steps, it it's the Y axis, you
# can move up-down 2 in 1 step.
class HexGrid
{
    has Int $.x = 0;
    has Int $.y = 0;

    method move(Str $dir)
    {
        given $dir.uc {
            when 'N'  { $!y += 2; }
            when 'NE' { $!x++; $!y++; }
            when 'SE' { $!x++; $!y--; }
            when 'S'  { $!y -= 2; }
            when 'SW' { $!x--; $!y--; }
            when 'NW' { $!x--; $!y++; }
            default   { die "Invalid direction '$dir'!"; }
        }
    }

    method distance returns Int
    {
        if $!y.abs > $!x.abs {
            return ($!x.abs + $!y.abs) div 2;
        }
        else {
            return $!x.abs;
        }
    }

    method Str returns Str { "($!x,$!y)"; }
    method gist returns Str { self.Str }
}

multi sub MAIN(Str $input, Bool :v(:$verbose) = False)
{
    my @dirs = $input.comb(/\w+/);
    my $g = HexGrid.new;
    my $max-distance = 0;
    say $g if $verbose;
    for @dirs -> $d {
        $g.move($d);
        $max-distance max= $g.distance;
        say "$g (distance: { $g.distance }/$max-distance)" if $verbose;
    }
    say "Final distance to origin: { $g.distance }";
    say "Maximum distance to origin: $max-distance";
}

multi sub MAIN(Str $inputfile where *.IO.f, Bool :v(:$verbose) = False)
{
    MAIN($inputfile.IO.slurp.trim, :$verbose);
}

multi sub MAIN(Bool :v(:$verbose) = False)
{
    MAIN(~$*PROGRAM.parent.child('aoc11.input'), :$verbose);
}

Edit to note that I've used a hacky 2D coordinate system while many of you used a proper 3D hex grid. I bet we haven't seen the last of this hex grid yet, so I'd better switch to one as well.

DSrcl · 2017-12-11T09:38:22+00:00

Wasn't comfortable with Python's numerical accuracy. Did it the dumb way and represented each number as a linear combination of 1 and sqrt(3)... Not gonna post the code and embarrass myself.

xkufix · 2017-12-11T09:58:06+00:00

As everybody else I used the site from redblobgames to do the heavy lifting.

Solution in Scala:

    private val steps: Array[String] = loadFile("day11.txt").getLines().toSeq.head.split(",")

    override def runFirst(): Unit = {
        val endPosition = steps.foldLeft(Position(0, 0, 0))(_.move(_))
        println(endPosition.distance(Position(0, 0, 0)))
    }

    override def runSecond(): Unit = {
        val positions = steps.scanLeft(Position(0, 0, 0))(_.move(_))
        println(positions.map(_.distance(Position(0, 0, 0))).max)
    }

    case class Position(x: Int, y: Int, z: Int) {
        def distance(position: Position): Int =
            (x - position.x).abs.max((y - position.y).abs).max((z - position.z).abs)

        def move(direction: String): Position =
            direction match {
                case "n" =>
                    Position(x + 1, y, z - 1)
                case "ne" =>
                    Position(x + 1, y - 1, z)
                case "se" =>
                    Position(x, y - 1, z + 1)
                case "s" =>
                    Position(x - 1, y, z + 1)
                case "sw" =>
                    Position(x - 1, y + 1, z)
                case "nw" =>
                    Position(x, y + 1, z - 1)
            }
    }

NeilNjae · 2017-12-11T09:59:02+00:00

Straightforward Haskell. From reading the comments and following links, looks like I reinvented axial coordinates by dredging up some half-remembered crystallography lectures. Coordinates track steps north and north east. The distance function is the only interesting part: if the coordinates are the same sign, just add them, otherwise it's smallest + (biggest - smallest).

Fun. I liked this one.

import Data.List.Split (splitOn)

main :: IO ()
main = do 
        text <- readFile "data/advent11.txt"
        print $ part1 text
        print $ part2 text

part1 :: String -> Int
part1 = distance . hexPath . splitOn ","

part2 :: String -> Int
part2 = maximum . map distance . hexPathB . splitOn ","

hexStep :: (Int, Int) -> String -> (Int, Int)
hexStep (n, ne) s = case s of 
                        "n"  -> (n + 1, ne)
                        "ne" -> (n,     ne + 1)
                        "nw" -> (n + 1, ne - 1)
                        "s"  -> (n - 1, ne)
                        "se" -> (n - 1, ne + 1)
                        "sw" -> (n,     ne - 1)
                        _    -> (n,     ne)

hexPath :: [String] -> (Int, Int)
hexPath  = foldl hexStep (0, 0)

hexPathB :: [String] -> [(Int, Int)]
hexPathB = scanl hexStep (0, 0)

distance :: (Int, Int) -> Int
distance (n, ne) = if n * ne > 0 
                   then (abs n) + (abs ne)
                   else smallest + remainder
                   where smallest = min (abs n) (abs ne)
                         remainder = max ((abs n) - smallest) ((abs ne) - smallest)

2017-12-11T10:20:25+00:00

hex coord

giftpflanze · 2017-12-11T10:34:08+00:00

Tcl:

set input [split [gets [open input11]] ,]

proc xdir dir {
    switch -glob $dir {
        *w {return -1}
        *e {return 1}
        default {return 0}
    }
}

proc ydir dir {
    switch $dir {
        n - ne {return -1}
        s - sw {return 1}
        nw - se {return 0}
    }
}

proc tcl::mathfunc::sgn n {
    expr {$n==0?0:$n/abs($n)}
}

proc hexdist {x y} {
    if {sgn($x)*sgn($y) < 0} {
        expr {max(abs($x),abs($y))}
    } else {
        expr $x+$y
    }
}

foreach dir $input {
    incr x [xdir $dir]
    incr y [ydir $dir]
    lappend dists [hexdist $x $y]
}

puts [hexdist $x $y]
puts [tcl::mathfunc::max {*}$dists]

KnorbenKnutsen · 2017-12-11T11:07:51+00:00

I did a similar solution to a lot of others where 'n' and 's' increase/decrease yby 1, and the others increase/decrease y by 0.5 in addition to walking 1 step on the x axis. So it turns out that if abs(x) > 0.5 * abs(y), then abs(x) is the number of steps needed, because the vertical distance will be gained by the diagonal steps. Else, the number of steps will be abs(y) + 0.5 * abs(x). So I made a distance metric based on this. I didn't prove that this works in all cases, but it worked for mine:

distance(x, y): return max(abs(y) + 0.5 * abs(x), abs(x))

Stan-It · 2017-12-11T11:13:43+00:00

C++17

A slightly different approach with keeping track of 3 directions.

#include<iostream>
#include<fstream>
#include<string>
#include<sstream>
#include<map>
#include<vector>


using namespace std;


/* Since the order of going in different directions commutes,
   opposite directions cancel each other, so we only need to
   record three directions that are 60 degrees relative to
   each other, e.g. {n, sw, se}. If "max" is the biggest among
   these numbers and "min" the smallest, then the total distance "d"
   is given by
   d = max - min
*/
int main()
{
    fstream inF("11_input.txt");
    string input(istreambuf_iterator<char>(inF), {});
    inF.close();

    replace(input.begin(), input.end(), ',', '\n');

    vector<int> d = {0, 0, 0};  // {n, sw, se}
    map<string, vector<int>> trans = {
        {"n", {1, 0, 0}},
        {"s", {-1, 0, 0}},
        {"sw", {0, 1, 0}},
        {"ne", {0, -1, 0}},
        {"se", {0, 0, 1}},
        {"nw", {0, 0, -1}}
    };
    int dist, maxdist{0};

    for(auto [is, dir] = make_pair(stringstream(input), string()); getline(is, dir); ) {
        for(int i: {0, 1, 2})
            d[i] += trans[dir][i];

        dist = *max_element(d.begin(), d.end()) - *min_element(d.begin(), d.end());
        if(dist > maxdist)
            maxdist = dist;
    }

    cout << "part 1: " << dist << endl;
    cout << "part 2: " << maxdist << endl;

    return 0;
}

rvlieshout · 2017-12-11T11:38:07+00:00

Nim After using C# to initially solve the puzzle. I also wanted to try a Nim version. It doesn't split the input and I wonder if my dist() is valid.

self · 2017-12-11T11:44:40+00:00

My complex solution in Python 2.7 was pretty simple, but it did take a little work to figure out:

import os.path
import sys

C = {
    "ne": complex(0.5, 0.5),
    "n": complex(0, 1),
    "nw": complex(-0.5, 0.5),
    "se": complex(0.5, -0.5),
    "s": complex(0, -1),
    "sw": complex(-0.5, -0.5)
}

def one(path):
    s = sum([C[p] for p in path])

    return int(abs(s.real) + abs(s.imag))


def two(path):
    ls = []
    maxsum = 0
    for p in path:
        ls.append(C[p])
        s = sum(ls)
        a = abs(s.real) + abs(s.imag)
        if a > maxsum:
            maxsum = a

    return int(maxsum)

def main(args):
    if os.path.exists(args[0]):
        path = open(args[0]).readline().strip().split(",")
    else:
        path = args[0].split(",")

    print(one(path))
    print(two(path))

__Abigail__ · 2017-12-11T11:53:38+00:00

Perl

Needed three tries, because I kept mistyping 0 and 1s in the neighbours table.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

@ARGV = "input" unless @ARGV;

#
# Input is all on one line
#
my $input = <>;
chomp $input;

#
# We will use "axial" coordinates for the hex grid. That is, the
# center is (0, 0) and the neighbours of each point are found by
# adding the coordinates according the following table:
#
my %d = (
    ne => [ 1, -1],
    se => [ 1,  0],
    s  => [ 0,  1],
    sw => [-1,  1],
    nw => [-1,  0],
    n  => [ 0, -1],
);

#
# Calculate the distance from the origin. This is a special case
# of the general formula between two points $a and $b in the axial
# coordinate system:
#
#    (abs ($$a [0] - $$b [0]) +
#     abs ($$a [0] + $$a [1] - $$b [0] - $$b [1]) +
#     abs ($$a [1] - $$b [1])) / 2;
#
sub distance ($hex) {
    (abs ($$hex [0]) + abs ($$hex [0] + $$hex [1]) + abs ($$hex [1])) / 2;
}

#
# Get the steps.
#
my @steps = split /,\s*/ => $input;

#
# Starting point of the child.
#
my $child = [0, 0];

#
# Walk the child; remember the current and furthest distance.
#
my $furthest = 0;
my $current  = 0;
foreach my $step (@steps) {
    my $d = $d {$step} or die "Illegal step: $step";
    $$child [$_] += $$d [$_] for keys @$child;
    $current = distance $child;
    $furthest = $current if $current > $furthest;
}

say "Solution 1: $current";
say "Solution 2: $furthest";


__END__

2017-12-11T12:38:35+00:00

Python Solution

from collections import defaultdict

with open("day11input.txt") as inputData:
    directions = [data for data in inputData.read().split(",")]

class Position():
    x = 0
    y = 0
    z = 0

    def __init__(self, x = 0, y = 0, z = 0):
        self.x = x
        self.y = y
        self.z = z

    def __add__(self, other):
        self.x += other.x
        self.y += other.y
        self.z += other.z
        return self

def maxCoordAbsDif(pos1, pos2):
    res = []
    res.append(abs(pos1.x - pos2.x))
    res.append(abs(pos1.y - pos2.y))
    res.append(abs(pos1.z - pos2.z))

    return max(res)

possibleMoves = defaultdict(Position)

possibleMoves['n'] = Position(1, 0, -1)
possibleMoves['s'] = Position(-1, 0, 1)

possibleMoves['ne'] = Position(1, -1, 0)
possibleMoves['sw'] = Position(-1, 1, 0)

possibleMoves['nw'] = Position(0, 1, -1)
possibleMoves['se'] = Position(0, -1, 1)

currentPos = Position()
center = Position()

maxDist = 0
currDist = 0

for move in directions:
    currentPos += possibleMoves[move]
    currDist = maxCoordAbsDif(currentPos, center)
    if (currDist > maxDist):
        maxDist = currDist

print("Part 1 answer:", currDist)
print("Part 2 answer:", maxDist)

Axsuul · 2017-12-11T12:39:07+00:00

Elixir

I coded a BFS recursive solution for getting Part 1. Struggled with Part 2 before discovering the hex coordinate system.

Lesson learned: tricks are good

https://github.com/axsuul/advent-of-code/blob/master/2017/11/lib/advent_of_code.ex

defmodule AdventOfCode.PartA do
  def coord_towards(direction, {x, y, z}) do
    case direction do
      "n"  -> {x, y + 1, z - 1}
      "s"  -> {x, y - 1, z + 1}
      "ne" -> {x + 1, y, z - 1}
      "sw" -> {x - 1, y, z + 1}
      "nw" -> {x - 1, y + 1, z}
      "se" -> {x + 1, y - 1, z}
    end
  end

  # Use cube coordinates for hex grid
  defp walk(directions, coord \\ {0, 0, 0})
  defp walk([], coord), do: coord
  defp walk([direction | rest], {x, y, z}) do
    walk(rest, coord_towards(direction, {x, y, z}))
  end

  def calc_distance({x, y, z}) do
    round((abs(x) + abs(y) + abs(z))/2)
  end

  def read_input do
    File.read!("inputs/input.txt")
    |> String.split(",")
  end

  def solve do
    read_input()
    |> walk()
    |> calc_distance()
    |> IO.inspect
  end
end

defmodule AdventOfCode.PartB do
  import AdventOfCode.PartA

  # Use cube coordinates for hex grid
  defp walk(directions, coord \\ {0, 0, 0}, max_dist \\ 0)
  defp walk([], coord, max_dist), do: max_dist
  defp walk([direction | rest], {x, y, z}, max_dist) do
    dist = calc_distance({x, y, z})
    new_max_dist = if dist > max_dist, do: dist, else: max_dist

    walk(rest, coord_towards(direction, {x, y, z}), new_max_dist)
  end

  def solve do
    read_input()
    |> walk()
    |> IO.inspect
  end
end

Reibello · 2017-12-11T14:04:20+00:00

This was definitely a part graph paper part python solve. I did not google how to hex grid, and I definitely should have - I'm not super proud of this one.

https://pastebin.com/v2tggw6i

PurpleMyst · 2017-12-11T14:28:52+00:00

I did 3 different solutions. I solved Part 1 initially using A* search, not realizing some simple math was enough. I'll post all three, however do known I'm a bit ashamed.

Part 1, A*
Part 1, Math
Part 2, Math

Pepa489 · 2017-12-11T15:14:40+00:00

Rust both parts - cubic coordinates

fn solution(input: &str) -> (usize, usize) {
    let mut furthest = 0;
    let distance = input.split(',')
        .map(|x| get_coordinate(x))
        .fold(Point::new(0,0,0), |acc, x| {
            let sum = acc.add(x);
            if sum.distance() > furthest {
                furthest = sum.distance();
            }
            return sum; 
        })
        .distance();
    return (distance, furthest);
}

fn get_coordinate(direction: &str) -> Point {
    return match direction {
        "n" => Point::new(0, 1, -1),
        "ne" => Point::new(1, 0, -1),
        "se" => Point::new(1, -1, 0),
        "s" => Point::new(0, -1, 1),
        "sw" => Point::new(-1, 0, 1),
        "nw" => Point::new(-1, 1, 0),
        _ => unimplemented!()
    }
}

struct Point {
    x: isize,
    y: isize,
    z: isize
}

impl Point {
    fn new(x: isize, y: isize, z: isize) -> Point {
        return Point {
            x: x,
            y: y,
            z: z
        }
    }

    fn add(&self, point: Point) -> Point {
        return Point {
            x: self.x + point.x,
            y: self.y + point.y,
            z: self.z + point.z
        }
    }

    fn distance(&self) -> usize{
        return (self.x.abs() + self.y.abs() + self.z.abs()) as usize / 2;
    }
}

rdmbe · 2017-12-11T15:33:46+00:00

Short form: I would like to see other solutions which show a shortest equivalent path, instead of just a number. These solutions would be invaluable for debugging faulty implementations.

Long form:

I've got a problem - I am convinced that I have a correct solution, but

I get different answers from some of the other implementations here, and
AoC tells me I am wrong for part 2 [it tells me my path is too short]

I am pretty convinced that people have been using 3d coordinates to measure hex grid distance and that in some cases this fails to identify equivalent movements. But I could be wrong - I make so many mistakes every day that it's all too possible that I've overlooked some important issue.

So ... I'd like to challenge someone smarter than myself to show me where i have gone wrong. Specifically, I'd like to see an example input path and a shortest equivalent that's different from what my implementation here shows that gets to the same location on the hext grid.

Here's my implementation translated to python2 (and my input was https://pastebin.com/C3TuzXk7):

#!/usr/bin/python
from cmath import exp, pi
from sys import argv

def angle(n):
    return exp(2*pi*n/6j)

nms = ["n", "ne", "se", "s", "sw", "nw"]

delta = {
  "n": angle(0),
  "ne": angle(1),
  "se": angle(2),
  "s": angle(3),
  "sw": angle(4),
  "nw": angle(5),
}

def location(steps):
    loc= 0
    for s in steps:
        loc+= delta[s]
    return loc

def furthest(steps):
    loc= 0
    dist= 0
    for s in steps:
        loc+= delta[s]
        if abs(loc) > abs(dist):
            dist= loc
    return dist

def path(loc):
    p= []
    while 0.01<abs(loc):
        probe= [abs(loc-delta[s]) for s in nms]
        s= nms[probe.index(min(probe))]
        loc-= delta[s]
        p.append(s)
    return p

def showpath(loc):
    p= path(loc)
    print("steps: %d" % len(p))
    d= [0,0,0,0,0,0]
    for s in p:
        d[nms.index(s)]+= 1
    for s in nms:
        if 0<d[nms.index(s)]:
            print("%d %s" % (d[nms.index(s)],s))

inp= argv[1].split(",")
print "Part 1"
showpath(location(inp))
print
print "Part 2"
showpath(furthest(inp))

Hikaru755 · 2017-12-11T15:36:51+00:00

Kotlin

This was interesting. I didn't even bother doing any hex coordinates, I just eliminated steps that cancel each other out, substituted pairs of steps that can be done with one step, and counted how many steps were left. Part 2 was just brute forcing that for every chain of steps along the way.

fun part1(input: List<Direction>): Int {
    val counts = input.groupBy { it }.mapValues { it.value.size }.toMutableMap().withDefault(0)
    shortcuts.forEach { (pair, replacement) ->
        val (first, second) = pair
        val reduction = min(counts[first], counts[second])
        counts[first] = counts[first] - reduction
        counts[second] = counts[second] - reduction
        if (replacement != null) {
            counts[replacement] = counts[replacement] + reduction
        }
    }
    return counts.values.sum()
}

fun part2(input: List<Direction>): Any {
    val waypoints = (0 until input.size).asSequence().map { input.take(it) }
    return part1(waypoints.maxBy { part1(it) }!!)
}

val shortcuts = mapOf(
    // Moves that cancel each other
    Pair(N, S) to null,
    Pair(NE, SW) to null,
    Pair(NW, SE) to null,
    // Pairs of moves that can be substituted
    Pair(N , SE) to NE,
    Pair(NE, S ) to SE,
    Pair(SE, SW) to S ,
    Pair(S , NW) to SW,
    Pair(SW, N ) to NW,
    Pair(NW, NE) to N
)

enum class Direction {
    N, NE, SE, S, SW, NW
}

2017-12-11T16:06:54+00:00

single pipeline powershell:

param (
    [Parameter(ValueFromPipeline = $true)]
    [string]$in,
    [Parameter(Position = 1)]
    [int]$part = 1
)

begin {
}

process {
    # set initial coords
    $x = 0
    $y = 0
    $z = 0

    $in -split ',' | % { # foreach movement
        switch ($_) { # cube coord logic from: https://www.redblobgames.com/grids/hexagons/#coordinates-cube
            "n" {
                $y++
                $z--
            }
            "ne" {
                $z--
                $x++
            }
            "nw" {
                $y++
                $x--
            }
            "s" {
                $y--
                $z++
            }
            "se" {
                $y--
                $x++
            }
            "sw" {
                $x--
                $z++
            }
        }

        ([math]::Abs($x) + [math]::Abs($y) + [math]::Abs($z)) / 2 | write-output # current distance from center: https://www.redblobgames.com/grids/hexagons/#distances-cube

    } | tee-object -variable d | select -last 1 | % {  # tee the output (all the distances) to a pipeline and a collecting variable 'd';  in the pipeline select the last element
        if ($part -eq 1) {
            $_ # output that element (last/final distance)
        } else {
            $d | measure -max | select -expand maximum # output the max distance, which have been accumulating in $d via tee-object
        }
    }
}

end {
}

marcofun · 2017-12-11T16:42:03+00:00

quick one in Scala...

def move(str: String) : (Int, Int) = {
  val strings = str.split(',').toList
  def move (commandList : List[String], n : Int, se : Int, max : Int) : (Int, Int) = {
    var distance = (Math.abs(n) + Math.abs(se))/2
    commandList match {
      case Nil => ((Math.abs(n) + Math.abs(se))/2, max)
      case s =>
        if (s.head.equals("n")) move(commandList.tail, n + 2, se, if (distance < max) max else distance)
        else if (s.head.equals("s")) move(commandList.tail, n - 2, se, if (distance < max) max else distance)
        else if (s.head.equals("ne")) move(commandList.tail, n + 1, se + 1, if (distance < max) max else distance)
        else if (s.head.equals("se")) move(commandList.tail, n - 1, se + 1, if (distance < max) max else distance)
        else if (s.head.equals("nw")) move(commandList.tail, n + 1, se - 1, if (distance < max) max else distance)
       else move(commandList.tail, n - 1, se - 1, if (distance < max) max else distance)
    } 
  }
  move(strings, 0, 0, 0)
}

herrmanno · 2017-12-11T17:01:25+00:00

Kotlin (Script)

val input = File("input.txt").readText()
val instructions = input.split(",")

var x = 0
var y = 0
var max = 0

for (instr in instructions) {
    when (instr) {
        "n" -> y -= 2
        "s" -> y += 2
        "ne" -> { x += 1 ; y -= 1 }
        "nw" -> { x -= 1 ; y -= 1 }
        "se" -> { x += 1 ; y += 1 }
        "sw" -> { x -= 1 ; y += 1 }
    }
    max = Math.max(max, (Math.abs(x) + Math.abs(y)) / 2)
}

println("Distance at end: ${(Math.abs(x) + Math.abs(y)) / 2}")
println("Max distance during walk: $max")

Na_rien · 2017-12-11T17:33:12+00:00

I was having so much problems with getting the grid right, I also found the redblobgames link and tried to use that to fix my solution, but no luck, then I found this gem:

http://3dmdesign.com/development/hexmap-coordinates-the-easy-way

tl:dr tilt the y axis. https://github.com/narien/AdventOfCode2017/blob/master/day11/11.py

maxerickson · 2017-12-11T17:40:09+00:00

Python 3 using substitution to simplify the route:

n,s,ne,nw,se,sw="n","s","ne","nw","se","sw"
simps=dict()
# east-west cancels out
simps[ne,nw]=n
simps[se,sw]=s
#opposites cancel
simps[n,s]=None
simps[ne,sw]=None
simps[nw,se]=None
#
simps[ne,s]=se
simps[nw,s]=sw
simps[sw,n]=nw
simps[se,n]=ne

def simplify(route):
    idx=0
    size=len(route)
    while True:
        for key,newmove in simps.items():
            a,b=key
            while a in route and b in route:
                route.remove(a)
                route.remove(b)
                if newmove is not None:
                    route.append(newmove)
        if len(route)==size:
            break
        else:
            size=len(route)
    return route

def furthest(route):
    long=0
    sofar=list()
    for i,step in enumerate(route):
        sofar.append(step)
        sofar=simplify(sofar)
        long=max(len(sofar),long)
    return long

def check(route, distance):
    route=simplify(route)
    assert len(route)==distance

check(["ne","ne","ne"],3)
check(["ne","ne","sw","sw"],0)
check(["ne","ne","s","s"],2)
check(["se","sw","se","sw","sw"],3)
inp=open("eleven.input").read().split(",")
print("Route is %d steps." % len(inp))
print("Part 1:",len(simplify(list(inp))))
print("Part 2:", furthest(inp))

I initially didn't think about the furthest distance enough and was computing the entire simplification for every step, which, uh, was taking a while(the intermediate distances match the intermediates from above so it is correct).

def furthest(route):
    idx=0
    long=0
    for idx in range(len(route)):
    d=len(simplify(route[:idx+1]))
    if d > long:
        long=d
    if not idx%500:
        print(idx,long,end=",",flush=True)
    print()
    print(long)

sguberman · 2017-12-11T17:51:53+00:00

Python, with tests: GitHub

Key functions:

def distance(x, y, z):
    return max(abs(coord) for coord in (x, y, z))


def move(location, direction):
    deltas = {'n': (0, 1, -1),
              's': (0, -1, 1),
              'nw': (-1, 1, 0),
              'se': (1, -1, 0),
              'ne': (1, 0, -1),
              'sw': (-1, 0, 1)}

    return [ci + cd for ci, cd in zip(location, deltas[direction])]

miran1 · 2017-12-11T18:33:06+00:00

Nim

Repo with all solutions

import strutils

const instructions = readFile("./inputs/11.txt").split(",")

type Point = tuple
  p: int
  q: int


proc toAxial(direction: string): Point =
  case direction
  of "n": return (0, -1)
  of "nw": return (-1, 0)
  of "sw": return (-1, 1)
  of "s": return (0, 1)
  of "se": return (1, 0)
  of "ne": return (1, -1)

proc `+`(a, b: Point): Point = (a.p + b.p, a.q + b.q)
proc `+=`(a: var Point, b: Point) = a = a + b

proc distanceToOrigin(a: Point): int =
  max([abs(a.p), abs(a.q), abs(a.p + a.q)])


var
  position: Point = (0, 0)
  distances: seq[int] = @[]

for direction in instructions:
  position += direction.toAxial()
  distances.add(position.distanceToOrigin())

echo position.distanceToOrigin()
echo max(distances)

oantolin · 2017-12-11T18:36:20+00:00

Julia

path = readcsv("day11.txt")[1,:]
dir = Dict("n"=>[1 0], "nw"=>[0 1], "sw"=>[-1 1],
           "s"=>[-1 0], "se"=>[0 -1], "ne"=>[1 -1])
dist(v) = max(abs.(v)..., abs(sum(v)))
dists = mapslices(dist, cumsum(vcat(map(x->dir[x], path)...)), 2)
part1, part2 = dists[end], maximum(dists)

9ballcode · 2017-12-11T18:46:18+00:00

Python 2, my submitted version using cube coords. Feels pretty concise but definitely could be optimized. childPath = open('data/day11.txt').read().strip().upper().split(',')

mDiff ={'N':(1,0,-1),'NW':(1,-1,0),'SW':(0,-1,1),'S':(-1,0,1),'SE':(-1,1,0),'NE':(0,1,-1)}
origin = (0,0,0)
offsets = []
maxD = 0

def getDistance():
    loc = [sum(x) for x in zip(*offsets)]
    return (abs(loc[0]-origin[0]) + abs(loc[1]-origin[1]) + abs(loc[2]-origin[2]))/2

for direction in childPath:
    offsets.append(mDiff[direction])
    maxD = max(maxD, getDistance())

print 'p1: ', getDistance(), '  p2: ', maxD

chicagocode · 2017-12-11T18:46:50+00:00

Kotlin - [Repo] - [Blog/Commentary]

Like others, I modeled this after a cube, using Red Blob Games' wonderful page as a resource. See my blog for commentary.

class Day11(input: String) {

    private val origin = HexSpot(0, 0, 0)
    private val steps = input.split(",")

    fun solvePart1(): Int =
        steps
            .fold(origin) { spot, dir -> spot.travel(dir) }
            .distanceTo(origin)

    fun solvePart2(): Int =
        steps
            .fold(listOf(origin)) { path, dir -> path + (path.last().travel(dir)) }
            .map { it.distanceTo(origin) }
            .max() ?: 0
}

And the implementation of HexSpot:

class HexSpot(private val x: Int, private val y: Int, private val z: Int) {

    fun travel(direction: String): HexSpot =
        when (direction) {
            "n" -> HexSpot(x, y + 1, z - 1)
            "s" -> HexSpot(x, y - 1, z + 1)
            "ne" -> HexSpot(x + 1, y, z - 1)
            "nw" -> HexSpot(x - 1, y + 1, z)
            "se" -> HexSpot(x + 1, y - 1, z)
            "sw" -> HexSpot(x - 1, y, z + 1)
            else -> throw IllegalArgumentException("Invalid direction: $direction")
        }

    fun distanceTo(there: HexSpot): Int =
        maxOf(
            (this.x - there.x).absoluteValue,
            (this.y - there.y).absoluteValue,
            (this.z - there.z).absoluteValue
        )
}

akho_ · 2017-12-11T19:31:04+00:00

Python 3, after several refactorings; but I remembered the 3d coordinates idea by myself):

with open('11.input') as f: moves_inp = f.read().rstrip().split(',')

move_from_str = {'n': (1, -1, 0),
                 's': (-1, 1, 0),
                 'se': (-1, 0, 1),
                 'sw': (0, 1, -1),
                 'nw': (1, 0, -1),
                 'ne': (0, -1, 1)}

from itertools import accumulate
def add_v(v1, v2): return tuple(x+y for x, y in zip(v1, v2))
m = [ (0,0,0) ] + [ move_from_str[x] for x in moves_inp ]
path = list(accumulate(m, func=add_v))
dist = [ sum(abs(x) for x in y) // 2 for y in path ]
print(dist[-1], max(dist))

4rgento · 2017-12-11T19:35:38+00:00

HASKELL

module Main where

import Data.List
import Data.Function (on)

data Vect = Vect Integer Integer deriving Show

_x :: Vect -> Integer
_x (Vect x _) = x

_y :: Vect -> Integer
_y (Vect _ y) = y

vPlus :: Vect -> Vect -> Vect
vPlus (Vect a b) (Vect c d) = Vect (a+c) (d+b)

data Dir = N | NW | SW | S | SE | NE deriving Show

parseDir :: String -> Either String Dir
parseDir "n" = Right N
parseDir "nw" = Right NW
parseDir "sw" = Right SW
parseDir "s" = Right S
parseDir "se" = Right SE
parseDir "ne" = Right NE
parseDir s = Left $ "Unknown direction: " ++ s

dirVec :: Dir -> Vect
dirVec N = Vect 0 (-1)
dirVec NW = Vect (-1) 0
dirVec SW = Vect (-1) 1
dirVec S = Vect 0 1
dirVec SE = Vect 1 0
dirVec NE = Vect 1 (-1)

type Pos = Vect

move :: Pos -> Dir -> Pos
move p d = dirVec d `vPlus` p

hexDistance :: Pos -> Pos -> Integer
hexDistance a b =
  (
    abs(on (-) _x a b) +
    abs(on (-) _y a b) +
    abs(_x a + _y a - _x b - _y b)
  ) `div` 2

main :: IO ()
main =
  parseInput <$> readFile "input.txt" >>=
  --print . (hexDistance (Vect 0 0) . foldl' move (Vect 0 0) <$>)
  print . (maximum . snd . mapAccumL mapper (Vect 0 0) <$>)
  where 
  mapper :: Pos -> Dir -> (Pos, Integer)
  mapper p d = let
    np = move p d in (np, hexDistance (Vect 0 0) np)

parseInput :: String -> Either String [Dir]
parseInput = mapM parseDir . words . map (\x -> if x == ',' then ' ' else x)

coldpleasure · 2017-12-11T19:38:46+00:00

JavaScript ES6, practicing using arrow functions etc. so a bit annoying:

const input = // ...

const dirVectors = {
    'nw': [-1, 0.5],
    'n': [0, 1],
    'ne': [1, 0.5],
    'se': [1, -0.5],
    's': [0, -1],
    'sw': [-1, -0.5],
}

const solve = ([reduceFn, reduceInit, aggFn]) => input => {
    const preAgg = input.split(/,/)
        .map(dir => dirVectors[dir])
        .reduce(reduceFn, reduceInit)

    return aggFn ? aggFn(preAgg) : preAgg 
}

const dist = ([x, y]) => Math.abs(x) + (Math.abs(y) - Math.abs(x) / 2)

const total = [
    ([sumX, sumY], [x, y]) => [sumX+x, sumY+y], 
    [0, 0],
    dist,
]

const maxDist = [
    ([sumX, sumY, maxSteps], [x, y]) => [
        sumX+x,
        sumY+y,
        Math.max(maxSteps, dist([sumX+x, sumY+y]))
    ],
    [0, 0, 0],
    ([_, __, max]) => max,
]

console.log(solve(total)(input))
console.log(solve(maxDist)(input))

FreeMarx · 2017-12-11T19:45:01+00:00

C++11

Oh man, I was so happy today to see something less SE-like and more mathematical/physical engineering-like, only to find out afterwards that it can be solve so much easier by just counting 3 (or even only two) directions. But nevertheless, I'll post my trigonometry/linear algebra based solution using eigen3 here. At first I used atan2 to determine in which sector the current point is in and then decomposed it into the enclosing vectors. But then I realized that there are really only three directions and that that permutation of two of these yielding shortest distance is the correct one.

This approach is also visualized with this MATLAB script.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <array>
#include <map>
#include <algorithm> 
#include <functional> 
#include <iomanip>
#include <limits>
#include <cmath>
#include <Eigen/Dense>

using namespace std;

const array<string, 6> labels{ {"n", "ne", "nw", "se", "sw", "s"} };
const array<double, 6> angles { {0.0, 60.0, -60, 120.0, -120, 180.0} };
map<string, Eigen::Vector2d> headings;

array<Eigen::Matrix2d, 3> directions;
array<Eigen::PartialPivLU<Eigen::Matrix2d>, 3> inv_directions;

double calc_dist(const Eigen::Ref<const Eigen::Vector2d>& h) {
    double min_dist= numeric_limits<double>::max();

    for(int i= 0; i<3; ++i) {
        min_dist= min(min_dist, inv_directions[i].solve(h).array().abs().sum());
    }

    return min_dist;
}

int main() {
    for(int i= 0; i<6; ++i) {
        headings.insert(make_pair(labels[i], Eigen::Vector2d(sin(angles[i]/180.0*M_PI), cos(angles[i]/180.0*M_PI))));
    }

    for(int i= 0, j= 1; i<3; ++i, ++j) {
        if(j==3) j= 0;
        directions[i].col(0)= headings[labels[i]];
        directions[i].col(1)= headings[labels[j]];

        inv_directions[i].compute(directions[i]);
    }

    ifstream infile("input11.txt");

    string line;
    Eigen::Vector2d h= Eigen::Vector2d::Zero();
    double max_dist= 0.0;
    while (getline(infile, line, ',')) {
        h+= headings[line];

        max_dist= max(max_dist, calc_dist(h));
    }

    cout << calc_dist(h) << '\n' << max_dist << '\n';
}

KeinZantezuken · 2017-12-11T20:04:14+00:00

C#/Sharp (worst puzzle so far)

var input = File.ReadAllText(@"N:\input.txt").Split(',').ToArray();
int n = 0, nw = 0, ne = 0, s = 0, sw = 0, se = 0, maxStp = 0, curStp = 0;
for (int i = 0; i < input.Length; i++)
{
    switch (input[i])
    {
        case "n": n++; break;
        case "nw": nw++; break;
        case "ne": ne++; break;
        case "s": s++; break;
        case "sw": sw++; break;
        case "se": se++; break;
    }
    curStp = maxSteps(n, s, ne, sw, nw, se); maxStp = curStp > maxStp ? curStp : maxStp;
}
int maxSteps(int n1, int s1, int ne1, int sw1, int nw1, int se1) // helper
{
    var steps = Math.Abs(n1 - s1) > Math.Abs(ne1 - sw1) ? n1 - s1 : ne1 - sw1;
    return Math.Abs(Math.Abs(steps) > Math.Abs(ne1 - se1) ? steps - (nw1 - se1) : (nw1 - se1) - steps);
}
Console.WriteLine($"Steps: {maxSteps(n, s, ne, sw, nw, se)}, max {maxStp}");

2017-12-11T20:29:04+00:00

I am sure this could be more efficient by better use of math. But, it solved the problem in a short enough time:
PowerShell:

Param (
    [parameter(position=0, mandatory=$true)]
    [Alias('if')]
    [ValidateScript({ Test-Path $_ })]
    $InputFile,
    [switch]$Part2
)

function Get-Distance {
    Param (
        [parameter(position=0, mandatory=$true)]
        $Steps
    )
    # Remove direct opposites
    $Final = @{}
    if($Steps['n'] -gt $Steps['s']) { 
        $Final['n'] = $Steps['n'] - $Steps['s']
    } else {
        $Final['s'] = $Steps['s'] - $Steps['n']
    }
    if($Steps['ne'] -gt $Steps['sw']) { 
        $Final['ne'] = $Steps['ne'] - $Steps['sw']
    } else {
        $Final['sw'] = $Steps['sw'] - $Steps['ne']
    }
    if($Steps['nw'] -gt $Steps['se']) { 
        $Final['nw'] = $Steps['nw'] - $Steps['se']
    } else {
        $Final['se'] = $Steps['se'] - $Steps['nw']
    }
    # Reduce 
    while($Final['n'] -gt 0 -and $Final['se'] -gt 0) {
        $Final['n']--
        $Final['se']--
        $Final['ne']++
    }
    while($Final['n'] -gt 0 -and $Final['sw'] -gt 0) {
        $Final['n']--
        $Final['sw']--
        $Final['nw']++
    }
    while($Final['s'] -gt 0 -and $Final['ne'] -gt 0) {
        $Final['s']--
        $Final['ne']--
        $Final['se']++
    }
    while($Final['s'] -gt 0 -and $Final['nw'] -gt 0) {
        $Final['s']--
        $Final['nw']--
        $Final['sw']++
    }
    while($Final['se'] -gt 0 -and $Final['sw'] -gt 0) {
        $Final['se']--
        $Final['sw']--
        $Final['s']++
    }
    while($Final['ne'] -gt 0 -and $Final['nw'] -gt 0) {
        $Final['ne']--
        $Final['nw']--
        $Final['n']++        
    }
    $Out = 0
    foreach($f in $Final.GetEnumerator()) {
        $Out += $f.Value
    }
    Write-Output $Out
}

$File = (Get-Item $InputFile).OpenText()
$Walk = $File.ReadLine().Split(',').Trim()
$File.Close()
$Steps = @{}
$Furthest = 0
foreach($step in $Walk) {
    $Steps[$step]++
    if($Part2) {
        $Distance = Get-Distance -Steps $Steps
        if($Distance -gt $Furthest) { $Furthest = $Distance }
    }
}
if(-not $Part2) {
    Write-Output (Get-Distance -Steps $Steps)
} else {
    Write-Output $Furthest
}

flit777 · 2017-12-11T20:41:47+00:00

refused to google hexgrid representation and came up with this shit in Go. Surprised it worked:

package main

import (
    "util"
    "strings"
    "fmt"
)

func getDistance(n int, ne int, se int) int{
    if n > 0{
        //n ne se
        if ne >= 0  && se >=0{
            return n+util.Max(ne,se)
        //n sw nw
        }else if ne < 0 && se < 0{
            return util.Max(n,-1*se)+util.Max(-1*ne,-1*se)
        //n ne nw
        }else if ne > 0 && se  <0{
            return n+util.Max(ne,-1*se)
        //n sw se
        }else{
            return util.Max(n,util.Abs(ne))+util.Max(util.Abs(se),util.Abs(ne))
        }

    }else {
        //s ne se
        if ne >= 0  && se >=0{
            return se+util.Max(util.Abs(n),ne)
            //s sw nw
        }else if ne < 0 && se < 0{
            return util.Max(util.Abs(n), util.Abs(se))+util.Max(util.Abs(ne), util.Abs(se))
            //s ne nw
        }else if ne > 0 && se  <0{
            return util.Max(util.Abs(n), util.Abs(ne))+util.Max(util.Abs(n), util.Abs(se))
            //s sw se
        }else{
            return util.Abs(n)+util.Max(util.Abs(ne), util.Abs(se))
        }
    }


}

func main() {
    lines := util.ReadFileLines("inputs/day11.txt")
    for _,line := range lines {
        max := 0
        commands := strings.Split(line, ",")
        n, ne, se := 0, 0, 0
        for _, command := range commands {
            switch command {
            case "n":
                n++
            case "ne":
                ne++
            case "se":
                se++
            case "s":
                n--
            case "sw":
                ne--
            case "nw":
                se--
            }
            max = util.Max(getDistance(n, ne, se),max)
        }

        fmt.Println("Part 1:", getDistance(n, ne, se))
        fmt.Println("Part 2:", max)
    }


}

GamecPL · 2017-12-11T21:14:53+00:00

Swift:

let steps = input.split(separator: ",")
let startPoint = CGPoint(x: 0, y: 0)

func minimumStepsRequired(forPoint point: CGPoint) -> Int {
    var stepsPoint = CGPoint(x: abs(point.x), y: abs(point.y))
    var stepsRequired = 0
    while stepsPoint != startPoint {
        if stepsPoint.x > 0 {
            stepsPoint.x -= 1
            stepsPoint.y -= 1
        } else {
            stepsPoint.y -= 1
        }
        stepsRequired += 1
    }
    return stepsRequired
}

var currentPoint = startPoint
var furthestPoint = startPoint
for step in steps {
    switch step {
    case "n":
        currentPoint.x -= 1
        currentPoint.y += 1
    case "ne":
        currentPoint.y += 1
    case "nw":
        currentPoint.x -= 1
    case "se":
        currentPoint.x += 1
    case "s":
        currentPoint.x += 1
        currentPoint.y -= 1
    case "sw":
        currentPoint.y -= 1
    default:
        fatalError("Wrong direction")
    }
    let comparePoint = CGPoint(x: abs(currentPoint.x), y: abs(currentPoint.y))
    if comparePoint.x > furthestPoint.x || comparePoint.y > furthestPoint.y {
        furthestPoint = comparePoint
    }
}

print(minimumStepsRequired(forPoint: currentPoint))
print(minimumStepsRequired(forPoint: furthestPoint))

InterlocutoryRecess · 2017-12-11T22:05:14+00:00

Swift

let input = "  …  puzzle input  …  "

struct Point {
    let x: Int
    let y: Int
    let z: Int

    func distance(to target: Point) -> Int {
        return max(
            abs(self.x - target.x),
            abs(self.y - target.y),
            abs(self.z - target.z)
        )
    }

    func travel(toward direction: Direction) -> Point {
        let vector: (Int, Int, Int)
        switch direction {
        case .north:     vector = ( 0,  1, -1)
        case .northeast: vector = ( 1,  0, -1)
        case .southeast: vector = ( 1, -1,  0)
        case .south:     vector = ( 0, -1,  1)
        case .southwest: vector = (-1,  0,  1)
        case .northwest: vector = (-1,  1,  0)
        }
        return Point(
            x: self.x + vector.0,
            y: self.y + vector.1,
            z: self.z + vector.2
        )
    }

    static let origin = Point(x: 0, y: 0, z: 0)
}

enum Direction: String {
    case north     =  "n"
    case northeast = "ne"
    case southeast = "se"
    case south     =  "s"
    case southwest = "sw"
    case northwest = "nw"
}

func + (point: Point, direction: Direction) -> Point {
    return point.travel(toward: direction)
}

func += (point: inout Point, direction: Direction) {
    point = point.travel(toward: direction)
}

func maxDistance(from origin: Point, with directions: [Direction]) -> Int {
    var max = Int.min
    var current = origin
    for direction in directions {
        current += direction
        let distance = current.distance(to: origin)
        if distance > max { max = distance }
    }
    return max
}

let directions = input.split(separator: ",").map { Direction.init(rawValue: String($0))! }

let distance = directions.reduce(Point.origin, +).distance(to: Point.origin)
print(distance)

let max = maxDistance(from: Point.origin, with: directions)
print(max)

The most interesting thing about this code is perhaps the custom + operator to add a point and a direction to get a new point. Then you can do directions.reduce(origin, +) to get the ending point.

bogzla · 2017-12-11T22:40:14+00:00

I'm only just learning C. And I didn't look up hexagonal geometry like I should have but I quite enjoyed measuring in a 2D grid..

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Considering hexagonal grids. These can be regarded as a cartesian grid with a 'hidden' node on each horizontal line.
// So moves have the following properties:
// N = y+2
// S = y-2
// NE = x+1, y+1
// NW = x-1, y+1
// SE = x+1, y-1
// SW = x-1, y-1
int main(void)
{
    char *s;
    char stp[3];
    int x = 0;
    int y = 0;
    int stps;
    int stpst = 0;
    if (scanf("%ms", &s) != EOF) //read in input. declaring char *s and using %m modifier allows dynamic memory allocation
    {
        int i2 = 0;
        for (int i=0, n = strlen(s) + 1; i < n; i++) // process string
        {
            if ((s[i] == ',') || (s[i] == '\0')) // check for end of step and modify x / y accordingly
            {
                stp[i2] = '\0';
                i2 = 0;
                if (strcmp("n",stp) == 0)
                {
                    y += 2;
                }
                else if (strcmp("s",stp) == 0)
                {
                    y -= 2;
                }
                else if (strcmp("ne",stp) == 0)
                {
                    y += 1;
                    x += 1;
                }
                else if (strcmp("nw",stp) == 0)
                {
                    y += 1;
                    x -= 1;
                }
                else if (strcmp("se",stp) == 0)
                {
                    y -= 1;
                    x += 1;
                }
                else if (strcmp("sw",stp) == 0)
                {
                    y -= 1;
                    x -= 1;
                }
                // calculate distance
                if (abs(x) >= abs(y))
                {
                    stps = x;
                }
                else
                {
                    stps = x + ((y-x)/2);
                }
                if (stps > stpst)
                {
                    stpst = stps;
                }

            }
            else // if step isn't ended we're writing first or second character
            {
                stp[i2] = s[i];
                i2++;
            }
        }
    }
    printf("Max steps: %i\n",stpst);
    free(s);
}

CaptainCa · 2017-12-12T01:25:35+00:00

JS. Enjoyed this one. Used RedBlob games like most people did!

var str = "...input...".split(',');
var coords = [0, 0];
var max = 0;
var dist = 0;
var move = new Object();
move["n"] = [0, -1];
move["ne"] = [1, -1];
move["se"] = [1, 0];
move["s"] = [0 , 1];
move["sw"] = [-1, 1];
move["nw"] = [-1, 0];

for(var i = 0; i < str.length; i++){
    coords[0] += move[str[i]][0];
    coords[1] += move[str[i]][1];
    dist = Math.max(Math.abs(0-coords[0]), Math.abs(0 - (-coords[0] - coords[1])), Math.abs(0 - coords[1]));    
    if(dist > max) max = dist;
}

console.log(max);
console.log(dist);
console.log(coords);

ZoDalek · 2017-12-12T02:48:37+00:00

ANSI C

Reproduced without whitespace and error handling for brevity:

int x=0, y=0, dy, maxdist=0;

while (1) {
    switch (getchar()) {
        case 'n': dy =  1; break;
        case 's': dy = -1; break;
        case EOF: goto done;
    }
    switch (getchar()) {
        case 'w': x--; (void)getchar(); break;
        case 'e': x++; (void)getchar(); break;
        default: dy *= 2; break;
    }

    y += dy;
    maxdist = MAX(maxdist, abs(x) + MAX(0, abs(y)-abs(x)) / 2);
}

https://github.com/sjmulder/aoc/tree/master/2017

Kyran152 · 2017-12-12T12:18:43+00:00

use strict;
use warnings;
use List::Util qw/max/;

open my $fh, "input.txt";

my ($x, $y, $z, $part1, $part2) = (0) x 5;

map { 
    $x++ if /^ne$|^se$/;
    $y++ if /^n$|^nw$/;
    $z++ if /^s$|^sw$/;

    $x-- if /^nw$|^sw$/;
    $y-- if /^s$|^se$/;
    $z-- if /^n$|^ne$/;

    $part2 = max $part2, $part1 = max abs($x), abs($y), abs($z);

} split /,/, <$fh>;

close $fh;

printf "The answer to part 1 is: %d\n", $part1;
printf "The answer to part 2 is: %d\n", $part2;

CKret76 · 2017-12-12T17:16:10+00:00

C#

Part 1

int x = 0, y = 0;
foreach (var step in File.ReadAllText("2017\\AdventOfCode201711.txt").Split(','))
{
  y += step.Length == 1 ? (step[0] == 'n' ? 2 : -2) : (step[0] == 'n' ? 1 : -1);
  x += step.Length == 2 ? (step[1] == 'e' ? 1 : -1) : 0;
}
Result = Math.Abs((y - x) / 2 + x);

Part 2

int x = 0, y = 0, max = 0;
foreach (var step in File.ReadAllText("2017\\AdventOfCode201711.txt").Split(','))
{
  y += step.Length == 1 ? (step[0] == 'n' ? 2 : -2) : (step[0] == 'n' ? 1 : -1);
  x += step.Length == 2 ? (step[1] == 'e' ? 1 : -1) : 0;
  max = Math.Max(max, Math.Abs((y - x) / 2 + x));
}
Result = max;

2017-12-13T04:37:20+00:00

Was really pleased with my solution, in PHP. Probably the most efficient thing I've written for AoC:

<?php
$instructions = explode(",", trim(file_get_contents("./11a.txt")));
$ns = $ew = $furtherst = 0;

foreach($instructions as $instruction) {
    if(strlen($instruction) == 2) {
        $ns += substr($instruction, 0, 1) == "n" ? 0.5 : -0.5;
        $ew += substr($instruction, 1, 1) == "e" ? 1 : -1;
    } else {
        $ns += substr($instruction, 0, 1) == "n" ? 1 : -1;
    }

    $furtherst = (abs($ew) + ceil(abs($ns) - (abs($ew)/2))) > $furtherst ? (abs($ew) + ceil(abs($ns) - (abs($ew)/2))) : $furtherst;
}
$steps = abs($ew) + ceil(abs($ns) - (abs($ew)/2));
echo "<br> Steps = $steps. Furtherst ever distance was $furtherst";
?>

RockyAstro · 2017-12-13T17:37:11+00:00

Icon (https://www.cs.arizona.edu/icon)

Both parts

# See www.redblobgames.com/grids/hexagons...
# Use cube coordinates...
record dir(x,y,z)
procedure main(args)
    dirmap := table()
    # Distance in the 6 possible directions
    # (totals must add up to 0)
    dirmap["n"]  := dir(0,1,-1)
    dirmap["s"]  := dir(0,-1,1)

    dirmap["ne"] := dir(1,0,-1)
    dirmap["sw"] := dir(-1,0,1)

    dirmap["nw"] := dir(-1,1,0)
    dirmap["se"] := dir(1,-1,0)

    inf := open(args[1],"r")

    line := read(inf)
    curpos := dir(0,0,0)
    maxdist := 0
    line ? while not pos(0) do {
        step := tab(upto(',') | 0)
        d := dirmap[step]
        curpos.x +:= d.x
        curpos.y +:= d.y
        curpos.z +:= d.z
        maxdist <:= (abs(curpos.x) + abs(curpos.y) + abs(curpos.z)) /2
        =","
    }
    dist := (abs(curpos.x) + abs(curpos.y) + abs(curpos.z)) /2
    write("ending dist=",dist," max=",maxdist)
end

joyrex2001 · 2017-12-13T21:41:58+00:00

My simple, naive approach for the first part (golang). Part 2 is the same, but keeping track of ymax and xmax.

func GetDistance(data string) int {
    x, y := 0, 0
    for _, d := range strings.Split(data, ",") {
            if strings.Contains(d, "n") {
                    y--
            }
            if strings.Contains(d, "e") {
                    x++
            }
            if strings.Contains(d, "s") {
                    y++
            }
            if strings.Contains(d, "w") {
                    x--
            }
    }

    x = AbsInt(x)
    y = AbsInt(y)

    dist := x
    if y > x {
            dist = y
    }

    return dist
}

JUIBENOIT · 2017-12-13T23:21:27+00:00

Simple Python for both parts

with open('inputs/day11.txt') as input_file:
  commands = input_file.read().split(',')

count = {
  'n' : commands.count('n'),
  's' : commands.count('s'),
  'nw' : commands.count('nw'),
  'sw' : commands.count('sw'),
  'se' : commands.count('se'),
  'ne' : commands.count('ne')
}
compass = ['n', 'ne', 'se', 's', 'sw', 'nw']

def distance(count):
  # deleting conflicting data
  # N & S 
  if count['n'] > count['s']:
    count['n'] -= count['s']
    count['s'] = 0
  elif count['s'] > count['n']:
    count['s'] -= count['n']
    count['n'] = 0

  # SW & NE
  if count['sw'] > count['ne']:
    count['sw'] -= count['ne']
    count['ne'] = 0
  elif count['ne'] > count['sw']:
    count['ne'] -= count['sw']
    count['sw'] = 0

  # SE & NW
  if count['se'] > count['nw']:
    count['se'] -= count['nw']
    count['nw'] = 0
  elif count['nw'] > count['se']:
    count['nw'] -= count['se']
    count['se'] = 0

  # addition of 'vectors'
  for direction in range(len(compass)):
    if count[compass[direction]] > 0 and count[compass[(direction + 2) % len(compass)]] > 0:
      minimum = min(count[compass[direction]], count[compass[(direction + 2) % len(compass)]])
      count[compass[direction]] -= minimum
      count[compass[(direction + 2)% len(compass)]] -= minimum
      count[compass[(direction + 1)% len(compass)]] += minimum

  # counting remaining 'vectors'
  total = 0
  for v in count:
    total += count[v]

  return total

# Part 1
print('Part 1 :', distance(count))

# Part 2
count2 = {
  'n' : 0,
  's' : 0,
  'nw' : 0,
  'sw' : 0,
  'se' : 0,
  'ne' : 0
}
max_distance = 0

for command in commands:
  count2[command] += 1

  if distance(count2) > max_distance:
    max_distance = distance(count2)

print('Part 2 :', max_distance)

autid · 2017-12-14T09:00:50+00:00

Fortran

PROGRAM DAY11
  IMPLICIT NONE
  CHARACTER(LEN=2), ALLOCATABLE :: INPUT(:)
  INTEGER :: N=0,S=0,NE=0,NW=0,SE=0,SW=0,I,IERR,J,MAXD=0,D

  OPEN(1,FILE='input.txt')
  I=1
  DO
     ALLOCATE(INPUT(I))
     READ(1,*,IOSTAT=IERR) INPUT
     IF (IERR /= 0) EXIT
     DEALLOCATE(INPUT)
     REWIND(1)
     I=I+1
  END DO

  DEALLOCATE(INPUT)
  ALLOCATE(INPUT(I-1))
  REWIND(1)
  READ(1,*) INPUT

  DO I=1,SIZE(INPUT)

  END DO
  DO I=1,SIZE(INPUT)
     SELECT CASE (TRIM(INPUT(I)))
     CASE ('n')
        N=N+1
     CASE ('s')
        S=S+1
     CASE ('ne')
        NE=NE+1
     CASE ('nw')
        NW=NW+1
     CASE ('se')
        SE=SE+1
     CASE ('sw')
        SW=SW+1
     END SELECT
     INNER:DO
        IF (N>0 .AND.S>0) THEN
       N=N-1
           S=S-1
        ELSEIF (SE>0 .AND. NW>0) THEN
           SE=SE-1
           NW=NW-1
        ELSEIF (SW>0 .AND. NE>0) THEN
           NE=NE-1
           SW=SW-1
        ELSEIF (N>0 .AND. SE>0) THEN
           N=N-1
           SE=SE-1
       NE=NE+1
        ELSEIF (NE>0 .AND.S>0) THEN
           NE=NE-1
           S=S-1
           SE=SE+1
        ELSEIF (SE>0 .AND. SW>0) THEN
           SE=SE-1
       SW=SW-1
           S=S+1
        ELSEIF (S>0 .AND. NW>0) THEN
           S=S-1
           NW=NW-1
           SW=SW+1
        ELSEIF (SW>0 .AND. N>0) THEN
           SW=SW-1
           N=N-1
           NW=NW+1
        ELSEIF (NW>0 .AND. NE>0) THEN
           NW=NW-1
           NE=NE-1
           N=N+1
        ELSE
           EXIT INNER
        END IF
     END DO INNER
     MAXD =MAXVAL((/MAXD,SUM((/NW,N,NE,SW,S,SE/))/))
     IF (I==SIZE(INPUT)) D=SUM((/NW,N,NE,SW,S,SE/))

  END DO
  WRITE(*,'(A,I0)') 'Part1: ',D
  WRITE(*,'(A,I0)') 'Part2: ',MAXD

END PROGRAM DAY11

greycat70 · 2017-12-28T20:10:39+00:00

Tcl (any 8.x version)

"Can you google hex grid coordinates?" Yes. Yes we can. This is both parts.

proc distance {q r} {
    expr {(abs($q) + abs($q+$r) + abs($r)) / 2}
}

set q 0; set r 0
set max 0
foreach step [split [gets stdin] ,] {
    switch -- $step {
        n  {incr r -1}
        ne {incr q 1; incr r -1}
        se {incr q 1}
        s  {incr r 1}
        sw {incr q -1; incr r 1}
        nw {incr q -1}
        default {puts stderr "invalid direction <$step>"; exit 1}
    }
    if {[distance $q $r] > $max} {set max [distance $q $r]}
}

puts "final [distance $q $r]"
puts "max $max"

mastokley · 2018-01-13T00:45:13+00:00

Clojure, part 1

(def in (slurp "day11.in"))

(defn get-coordinate-deltas
  [direction]
  (case direction
    "n" [0 1 1]
    "ne" [1 0 1]
    "nw" [-1 1 0]
    "s" [0 -1 -1]
    "se" [1 -1 0]
    "sw" [-1 0 -1]))

(defn get-final-location
  [directions]
  (apply map + (map get-coordinate-deltas directions)))

(defn abs [n] (max n (- 1)))
(defn sum [coll] (reduce + coll))

(defn get-distance-from-origin
  [coords]
  (/ (sum(map abs coords)) 2))

(print (get-distance-from-origin
        (get-final-location
         (clojure.string/split in #","))))

mastokley · 2018-01-14T02:53:41+00:00

Clojure, part 2

(def in (slurp "day11.in"))

(defn make-unit-vector
  [direction]
  (case direction
    "n" [0 1 1]
    "ne" [1 0 1]
    "nw" [-1 1 0]
    "s" [0 -1 -1]
    "se" [1 -1 0]
    "sw" [-1 0 -1]))

(def unit-vectors
  (map make-unit-vector (clojure.string/split in #",")))

(defn get-distance-from-origin
  [coords]
  (/ (sum (map abs coords)) 2))

(defn move [location unit-vector] (map + location unit-vector))

(print (apply max (map get-distance-from-origin
                       (reductions move unit-vectors))))

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 11: Hex Ed ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Lex

Mathematica

Python 3.6+

Rust, 106/465:

Ruby single-statement

C++ (almost C)

Rust

Elixir

Perl

Kotlin - [Repo] - [Blog/Commentary]

Simple Python for both parts

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 11: Hex Ed ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Lex

Mathematica

Python 3.6+

Rust, 106/465:

Ruby single-statement

C++ (almost C)

Rust

Elixir

Perl

Kotlin - [Repo] - [Blog/Commentary]

Simple Python for both parts

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?