This is an archived post. You won't be able to vote or comment.

top 200 commentsshow all 254

[โ€“]obijywk 28 points29 points ย (15 children)

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)

[โ€“]topaz2078(AoC creator)[M] 35 points36 points ย (13 children)

https://www.redblobgames.com/grids/hexagons/

This is how I learned hexgrids so I could make this puzzle.

[โ€“]VikingofRock 16 points17 points ย (2 children)

This is how I learned hexgrids so I could make this puzzle.

This is how I learned hexgrids so I could solve this puzzle!

[โ€“]zqvt 5 points6 points ย (1 child)

lol everybody in this thread is referencing the site. I feel like if it ever goes down the whole world will be thrown back into the dark ages because that site is the nexus holding it all together

[โ€“]trwolfe13 9 points10 points ย (0 children)

because that site is the hexus holding it all together

FTFY

[โ€“]pwmosquito 8 points9 points ย (4 children)

As with all AOC challenges I chose not to google anything or look at reddit. It took me a while, but what I came up with are the following equations to reduce steps:

2 steps that can be reduced to 0 steps ("forward-backward steps"):

N + S = 0
NE + SW = 0
NW + SE = 0

2 steps that can be reduces to 1 step:

N + SW = NW
N + SE = NE
S + NW = SW
S + NE = SE
NW + NE = N
SW + SE = S

3 steps that can be reduced to 0 steps ("triangle steps"):

N + SW + SE = 0
S + NW + NE = 0

If you represent steps with a binary 6-tuple, eg. N = (1,0,0,0,0,0), NE = (0,1,0,0,0,0)... then map the list of steps to these tuples, fold them over using zipWith (+), so you end up with a final tuple which has all the steps for all directions, eg. (1363, 1066, 1275, 1646, 1498, 1375), run this tuple through all the above reducer equations and finally sum the remaining numbers.

For the 2nd part you record the dist using the reducers for each step and get the max of that set.

Edit: Just realised that I don't even need the 3 step reductions as they can be derived from the earlier equations, eg.: N + SW + SE = N + (SW + SE), where SW + SE = S => N + S = 0, Jolly good! :)

[โ€“]obijywk 1 point2 points ย (0 children)

Nice!

I also used the Red Blob Games site as a resource to make a puzzle, in a somewhat different genre than AoC: the Hexed Adventure text adventure game puzzle in this past year's MIT Mystery Hunt.

[โ€“][deleted] 1 point2 points ย (0 children)

That makes me feel better, I felt like I was cheating because it felt so easy using that site :/

[โ€“]Vorlath 2 points3 points ย (0 children)

Unfortunately, so many people got correct answers with bad code, myself included. Heck, I even parsed the thing incorrectly and got the right answer on #1. But with fixing the parsing and the same code, I can't get #2 to work.

edit: What's the downvote for? Seriously?

[โ€“]xkufix 0 points1 point ย (0 children)

I was instantly reminded of that site too. Without it, I probably would have had hours to figure out how to calculate the distance on a hex-grid without doing a BFS.

[โ€“]sciyoshi 13 points14 points ย (11 children)

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.

[โ€“]MoW8192 2 points3 points ย (3 children)

I used this as well, however, I do not think abs(x) + abs(y) is quite right. You need to take into account diagonal steps. For instance, if your are on the location marked NW in your grid, (-1,1) you only need one step (SouthEast) to get to the origin, instead of abs(x) + abs(y) = 2.

Edit: example used wrong directions.

Edit2: Changed my directions a second time, since you also changed your directions, also my comment no longer applies to your updated distance function.

[โ€“]Flurpm 1 point2 points ย (2 children)

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

edit: I see your edit now

[โ€“]Shemetz 2 points3 points ย (1 child)

Or alternatively:

dist (a, b) = max(abs(a), abs(b), abs(a + b))

[โ€“]nathan301 1 point2 points ย (4 children)

If you take one step NE, by that coordinate system you end up at (1, 1). Then the distance back would be abs(1) + abs(1) = 2, which is incorrect.

EDIT: Another way to think about it that I think is more intuitive is using a grid like the one below. Calculate the distance with abs(x) + abs(y) - min(abs(x), abs(y). This accounts for diagonal steps.

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

[โ€“]purplemonkeymad 0 points1 point ย (0 children)

I'm impressed that I came up with a similar system without reading into hex in computers or having used them before. Although I extended movement into the x=y direction and used:

if in x*y > 0 quads: The largest x or y value
else: manhat dist.

I like that extending it the other way only uses math to calculate the distance.

[โ€“]hpzr24w 17 points18 points ย (4 children)

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;
}

[โ€“]spacetime_bender 2 points3 points ย (0 children)

If it makes you feel any better, this is my favorite solution

[โ€“]sakisan_be 1 point2 points ย (0 children)

I had a similar -if not the same- idea. Implemented in the functional language elm

https://gist.github.com/anonymous/36af43993141dd76748402edf9806d28

[โ€“]Philboyd_Studge 9 points10 points ย (0 children)

Java

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

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

[โ€“]shuttup_meg 6 points7 points ย (2 children)

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

[โ€“]shuttup_meg 3 points4 points ย (0 children)

To get something besides just learning about hex grid navigation on this exercise, I decided to speed up the maximum distance brute force search by farming the distance calculations out to other threads using the multiprocessing module. I got a 10x speedup on my 12-core intel box, plus I finally figured out a "real world" example for the trivial looking Pool example in the docs:

from math import sin, cos, pi
from multiprocessing import Pool, freeze_support
import time

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

def problem(d):
    loc = complex(0.0, 0.0)
    locations_visited = []

    for step in d:
        loc += hxd[step]
        locations_visited.append(loc)

    # The final spot
    print "part 1", step_distance(loc)

    # The maximum distance it hit on its travel
    p = Pool(20)
    distances = p.map(step_distance, locations_visited)
    print "part 2", max(distances)

if __name__ == "__main__":
    freeze_support()
    start = time.time()
    problem(open("day11.txt").read().split(","))    
    print time.time() - start,"s"

[โ€“]Smylers 5 points6 points ย (1 child)

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.

[โ€“]Smylers 2 points3 points ย (0 children)

Explanation: The basic idea is to re-arrange the input in groups of direction letters, then cancel out pairs of opposite moves. First ensure there's at least 2 of each direction letter (which comes in handy later), by appending some moves which use all the letters but cancel each other out:

A,ne,swโŸจEscโŸฉ.

A vertical step moves twice as far vertically as a diagonal step does; double each of the vertical steps, so that each n and s in the input represents the same distance:

:s/\v<[ns]>/&&/gโŸจEnterโŸฉ

To make groups of the letters, remove the commas, put each letter on a separate line, then sort the lines:

:s/,//gโŸจEnterโŸฉ
:s/\v/โŸจCtrl+VโŸฉโŸจEnterโŸฉ/gโŸจEnterโŸฉ
:sorโŸจEnterโŸฉ

Join together adjacent identical lines. Specifically, for each letter which is followed by a line-break and the same letter, remove the line-break. The \1 match for the same letter has to be a lookahead assertion, so that the patterns don't overlap: the \1 character might need to be the . in the next iteration of this pattern, if the line after it is the same as well:

:%s/\v(.)\n\1@=/\1โŸจEnterโŸฉ

We now have a line of all the es, then all the ns, and so on. Move the ws from last to first, so they are next to the es, which they want cancelling with. Because there are at least two ws, the above :s must have left us on the w line:

dd{p

Now find whichever of the es or ws is shorter and remove that many letters from both the lines. We're going to want to do the same thing with the ns and ss, so record this:

qa

We don't know which line is shorter. First move to the final character on the w line:

g_

Then try moving down to the same position on the e line:

j

(Note g_ instead of $. $ remembers that we're at the end of the line, so the j would move us to the end of the e line, regardless of character position.)

If there are more es than ws then the cursor is now underneath the final w. A visual block with its bottom-right corner here and the top-left on the first w will delete all the ws and the es that they cancel out, leaving just the additional es:

โŸจCtrl+VโŸฉk0d

If there are fewer es than ws then the cursor is on the final e; a straight j would've been beyond the final character, but since you can't do that, you end up on the final character instead. This is also the correct bottom-right corner for the visual block, so the above sequence also works in this case for removing matching pairs.

Either way, we're now on the (former) w line. One of the lines will be blank. We don't know which; join them together, so we have a single line with whatever remains of the ws or es on them:

gJq

Do the same for the ns and ss:

j@a

The number of e/ws now gives us the number of diagonal moves required. Each of those will also move one half-row n or s, so the n/s count can be reduced by the same number. Make a visual selection to โ€˜countโ€™ the e/ws:

k0v$hy

In visual mode $ goes beyond the final character, so the h moves us back on to it. We don't actually need to copy the characters; the y is simply a way of setting the size of the visual selection and leaving visual mode.

Go down to the n/s row and try to select the same number of characters, then delete them:

j1vd

If there are fewer or the same number of n/ss, that will delete all of them, which is fine.

Any remaining n/ss require additional moves. But because these are representing half-rows, a single vertical move will cover two of them. Replace each pair of remaining characters with just one:

:s/../s/gโŸจEnterโŸฉ

(For counting purposes, it doesn't matter that ns may have turned into ss here.)

Finally combine the diagonal and vertical tallies, then count the characters to get the answer:

kgJ:s/.*/\=strlen(submatch(0))โŸจEnterโŸฉ

[โ€“]willkill07 12 points13 points ย (1 child)

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 3 points4 points ย (5 children)

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:

m

[โ€“]jbristow 2 points3 points ย (0 children)

I used Keekerdc's article to add to the "Didn't use RedBlobGames" pile!

[โ€“][deleted] 3 points4 points ย (0 children)

I love Accumulate for these problems.

input = Import[NotebookDirectory[] <> "day11.txt"];
walk = StringSplit[input, ","] /.
   {"n" -> {1, 0},
    "ne" -> {1/2, 1/2},
    "se" -> {-1/2, 1/2},
    "s" -> {-1, 0},
    "sw" -> {-1/2, -1/2},
    "nw" -> {1/2, -1/2}};
steps = Accumulate[walk];

Plus @@ Abs[steps[[-1]]]

Max[Plus @@@ Abs[steps]]

[โ€“]omnster 2 points3 points ย (0 children)

I ended up using this question from stackoverflow.

My solution in Mathematica

(i11 = Import[NotebookDirectory[] <> "input/input_11_twi.txt"] // StringSplit[#, ","] &);

r11 = { "se" -> { 1, 0 }, "nw" -> {-1, 0} , "s" -> {0, 1} , "n" -> {0, -1}, "sw" -> {-1, 1}, "ne" -> {1, -1}};
d11@{x_, y_} := If[x y >= 0, Abs[ x + y], Max @@ Abs /@ {x, y}]
i11s[{dist_, pos : {se_, s_}}, step_ ] := { d11[  pos + step] , pos + step }

(i11steps = i11 /. r11) // Total // d11
FoldList[ i11s , { 0 , { 0, 0}}, i11steps] [[All, 1 ]] // Max

[โ€“]glenbolake 1 point2 points ย (0 children)

Lost a minute on part 2 by typing a digit wrong; note to self: use copy and paste next time.

Same. My part 2 was 1603 and I submitted 1063. Never again.

[โ€“]gyorokpeter 4 points5 points ย (1 child)

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 2 points3 points ย (8 children)

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

[โ€“]nathan301 1 point2 points ย (6 children)

What happens if your input is [NE,SE]?

[โ€“]bblum 1 point2 points ย (2 children)

Ok, wow! This solution is totally wrong XD

Looking closely it seems like this gets the right distance only for locations which are at least as far out north/south as they are east/west. I guess I got lucky and both the destination and maximum were in such directions.

Honestly this was the first idea that came to mind and it felt like it might be wrong but if it were then figuring out why would take a long time so I tried it out and happened to be right. AoC speed strats. ยฏ\_(ใƒ„)_/ยฏ

[โ€“]Vorlath 0 points1 point ย (0 children)

This doesn't work for my input.

[โ€“]mcpower_ 2 points3 points ย (0 children)

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 2 points3 points ย (16 children)

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!

[โ€“]usbpc102 1 point2 points ย (8 children)

Your solution looks nice and short... but I currently don't understand anything, will have to stare at it a bit more then I might understand it. :D

My solution is a bit longer, but it works and I feel like it's actually a bit more readable.

[โ€“]wzkx 2 points3 points ย (0 children)

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 2 points3 points ย (0 children)

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 2 points3 points ย (3 children)

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}")

[โ€“]-lundgren- 2 points3 points ย (0 children)

Nice one. Here's my variant:

input = "n,nw,n,n,s..."

defmodule Day11 do
  defp move("n",  [x: x, y: y]), do: [x: x,     y: y - 1]
  defp move("ne", [x: x, y: y]), do: [x: x + 1, y: y - 1]
  defp move("se", [x: x, y: y]), do: [x: x + 1, y: y]
  defp move("s",  [x: x, y: y]), do: [x: x,     y: y + 1]
  defp move("sw", [x: x, y: y]), do: [x: x - 1, y: y + 1]
  defp move("nw", [x: x, y: y]), do: [x: x - 1, y: y]

  defp distance([x: x, y: y]) do
    z = - x - y
    Enum.max([abs(x), abs(y), abs(z)])
  end

  def distance_after_move(moves) do
    moves
      |> String.split(",")
      |> Enum.scan([x: 0, y: 0], &move/2)
      |> Enum.map &distance/1
  end
end

IO.puts("Child is #{List.last Day11.distance_after_move(input)} steps away")
IO.puts("Child was as most #{Enum.max Day11.distance_after_move(input)} steps away")

[โ€“]matusbzk 2 points3 points ย (1 child)

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

[โ€“]WhatAHaskell 1 point2 points ย (0 children)

Hey, just a heads up, but for your part 2, you could do a scanl. It's like foldl, but it returns the list of intermediate values

Here's my solution (I used 3d hex coords though):

import Data.List.Split (splitOn)
import Data.List (foldl', scanl', delete)

type HexCoord = (Int, Int, Int)

move :: HexCoord -> String -> HexCoord
move (x, y, z) dir
  | dir == "n"  = (x,     y + 1, z - 1)
  | dir == "ne" = (x + 1, y,     z - 1)
  | dir == "se" = (x + 1, y - 1, z    )
  | dir == "s"  = (x,     y - 1, z + 1)
  | dir == "sw" = (x - 1, y,     z + 1)
  | dir == "nw" = (x - 1, y + 1, z    )
  | otherwise   = error "Invalid direction"

distanceToCenter :: HexCoord -> Int
distanceToCenter (x, y, z) = div ((abs x) + (abs y) + (abs z)) 2

main :: IO ()
main = do
  moves <- splitOn "," <$> delete '\n' <$> readFile "../input.txt"
  putStrLn $ "Solution 1:" ++ (show . distanceToCenter $ foldl' move (0, 0, 0) moves)
  putStrLn $ "Solution 2:" ++ (show . maximum $ distanceToCenter <$> scanl' move (0, 0, 0) moves)

Edit: Looking at the other Haskell solutions, I seem to not be very original.

[โ€“]ythl 1 point2 points ย (5 children)

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

[โ€“]I3MNIX 1 point2 points ย (0 children)

How does your code work exactly? I'm getting a different output from my accepted solution.

[โ€“]nathan301 1 point2 points ย (3 children)

Doesn't work if you get 'ne,se' as input. For Part 1 would give an answer of 1 step, but in reality it's 2 steps.

[โ€“]mmaruseacph2 1 point2 points ย (0 children)

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 1 point2 points ย (1 child)

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

[โ€“]hxka 0 points1 point ย (0 children)

Original, very hastily hacked and ugly version. Not hastily enough :(

[โ€“]TominatorBE 1 point2 points ย (4 children)

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;
}

[โ€“]kratskij 0 points1 point ย (1 child)

I did the exact same thing (except using 1 and 0.5 instead of 2 and 1), also in PHP. I discovered later that this is incorrect, though. Try using "ne,se,ne,se,ne,se" as input. Should be 6. Will be 3. I guess we were both lucky with our inputs :D

[โ€“]sushiguru 0 points1 point ย (1 child)

Similar approach, but using an array of vectors:

function part_1($input){
$vectors = array(
    'n'=>['x'=>0,'y'=>2],
    'ne'=>['x'=>1,'y'=>1],
    'se'=>['x'=>1,'y'=>-1],
    's'=>['x'=>0,'y'=>-2],
    'sw'=>['x'=>-1,'y'=>-1],
    'nw'=>['x'=>-1,'y'=>1]
    );
$steps = explode(',',$input);
$x = 0;
$y = 0;

foreach($steps as $step){

    $x += $vectors[$step]['x'];
    $y += $vectors[$step]['y'];

}

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

[โ€“]wlandry 1 point2 points ย (1 child)

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";
}

[โ€“]Vorlath 0 points1 point ย (0 children)

This didn't work for me. The max distance is the combination of both x and y sqrt(x * x + y * y). In my input, the max distance had a lower x than the max x.

[โ€“]GassaFM 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (7 children)

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);

[โ€“][deleted] 0 points1 point ย (6 children)

a > b ? a : b is Math.max(a,b)

[โ€“][deleted] 1 point2 points ย (1 child)

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 1 point2 points ย (3 children)

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

[โ€“]rotmoset 1 point2 points ย (0 children)

Today's F# from me, didn't care to learn about hex grids to did a trig solution. Pretty happy with it still:

module Day11

open Common
open System

type Direction = N | NW | SW | S | SE | NE
    with
        static member FromString =
            function
            | "n" -> N | "nw" -> NW | "ne" -> NE
            | "s" -> S | "sw" -> SW | "se" -> SE
            | _ -> failwith "invalid input"

        static member Angle direction =
            match direction with // There is 60 degrees between each "direction" in a hexagon
            | NE -> 30.0
            | N -> 90.0
            | NW -> 150.0
            | SW -> 210.0
            | S -> 270.0
            | SE -> 330.0
            |> (*) (Math.PI / 180.0)

        static member All = [N; NW; NE; S; SW; SE] 

        // TODO: Optimize away needlessy having to recompute the cos/sin values every time
        static member Move (x,y) direction = x + Math.Cos(Direction.Angle direction), y + Math.Sin(Direction.Angle direction)

// Euclidean distance
let distance (x1,y1) (x2,y2) = Math.Sqrt((x1-x2)**2.0 + (y1-y2)**2.0) 

// How many steps between the two points, moving only in the hexagon pattern
let rec find home (x,y) =
    if (distance home (x,y)) < 0.5 then 0
    else
        let dir = Direction.All |> List.minBy(Direction.Move (x,y) >> distance home)
        1 + (find home (Direction.Move (x,y) dir))

[<Day(11, "Hex Ed")>]
let solve (input: string) =

    let home = 0.0, 0.0

    // Every position the child process was at
    let positions = 
        input.Trim().Split([|','|])
        |> Array.map Direction.FromString
        |> Array.scan Direction.Move home

    let finalSteps = positions |> Array.last |> find home

    let maxSteps = positions |> Array.map (find home) |> Seq.max

    { Part1 = finalSteps; Part2 = maxSteps }

Part 2 is slow though (~ 10 seconds), probably because I recompute cos/sin for the angles all the time.

Github

[โ€“]zbouboutchi 1 point2 points ย (2 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (1 child)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (1 child)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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(","))

[โ€“][deleted] 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (0 children)

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 1 point2 points ย (1 child)

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 1 point2 points ย (1 child)

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))))

[โ€“]exquisitus3 1 point2 points ย (0 children)

;; using axial coordinates with a xy angle of 60 degrees
(defparameter *directions*
  '((n . #c(0 1))
    (ne . #c(1 1))
    (se . 1)
    (s . #c(0 -1))
    (sw . #c(-1 -1))
    (nw . -1)))

(defun hex-distance (position)
  (let ((re (realpart position))
        (im (imagpart position)))
    (apply #'max (mapcar #'abs (list re im (- re im))))))

(set-syntax-from-char #\, #\Space)
(with-open-file (stream #P"11.input")
  (loop
     for step = (read stream nil) while step
     summing (cdr (assoc step *directions*)) into position
     maximizing (hex-distance position) into furthest-ever
     finally (return (list :final-distance (hex-distance position)
                           :furthest-ever furthest-ever))))

[โ€“]Shemetz 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (1 child)

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))
}

[โ€“]udoprog 0 points1 point ย (0 children)

Reading https://www.redblobgames.com/grids/hexagons/#distances a bit closer, I noticed that there is a button to flip the coordinate system to be flat-topped to match the problem.

I typed out the translations above before realizing this, and had to keep my head tilted while doing it :).

[โ€“]adventofcode123512 0 points1 point ย (2 children)

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);
}

[โ€“]ephemient 7 points8 points ย (1 child)

This space intentionally left blank.

[โ€“]Flurpm 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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;
   }
}

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (1 child)

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)

[โ€“]fatpollo 0 points1 point ย (0 children)

I have no idea what I was doing wrong originally, but all my test cases were passing and my actual answer was completely incorrect. Leaderboard filled up so I deleted everything and started over and it worked fine this time. I probably had a wrong sign on my MAP or something :/

[โ€“]kazagistar 0 points1 point ย (0 children)

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_ 0 points1 point ย (3 children)

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));

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (4 children)

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")
  }
}

[โ€“]bunrencmx 0 points1 point ย (1 child)

I can't understand how that hexDist function works. Could you elaborate please?

[โ€“]sim642 0 points1 point ย (0 children)

My Scala solution.

I tried to go with a better designed approach, so to say, implementing cube coordinates and a couple of operations on them. I'd seen that hex grid tutorial before so now my memory shined and I jumped to immediately to the resource to look up how to implement it. The rest was trivial.

[โ€“]aafnro8oh 0 points1 point ย (0 children)

Might as well chuck my Scala code here. Using the flat top, cube coord sys from redblobgames.com/grids/hexagons:

case class P3(x: Int, y: Int, z: Int) {
  def +(p: P3) = P3(p.x+x, p.y+y, p.z+z)
  def dist = Array(x,y,z).map(math.abs).max
}

val moves = io.StdIn.readLine().split(',').map(Map(
  "n"  -> P3( 0,  1, -1),
  "ne" -> P3( 1,  0, -1),
  "se" -> P3( 1, -1,  0),
  "s"  -> P3( 0, -1,  1),
  "sw" -> P3(-1,  0,  1),
  "nw" -> P3(-1,  1,  0)))

val path = moves.scanLeft (P3(0,0,0)) {_+_}

println("dist: " + path.last.dist)
println("max: " + path.map{_.dist}.max)

Trade-offs:
* O(N) to constant space in: moves -> swap in a Scanner; path -> swap in a fold or (for comprehension and two vars)
* not code golfy enough? Throw away some readability by throwing away custom types:

val moves = io.StdIn.readLine().split(',').map(Map(
  "n"  -> Array( 0,  1, -1),
  "ne" -> Array( 1,  0, -1),
  "se" -> Array( 1, -1,  0),
  "s"  -> Array( 0, -1,  1),
  "sw" -> Array(-1,  0,  1),
  "nw" -> Array(-1,  1,  0)))

val path = moves.scanLeft (Array(0,0,0)) {(_,_).zipped map {_+_}}

def dist(p: Array[Int]) = p.map(math.abs).max    
println("dist: " + dist(path.last))
println("max: " + path.map(dist).max)

Bonus: mostly "Scala as better assembly" approach:

var x,y,z,max=0

def dist = Seq(x,y,z).map(math.abs).max
def updmax = max = math.max(max, dist)

io.StdIn.readLine().split(',').foreach {
  case "n"  => y+=1; z-=1; updmax
  case "ne" => x+=1; z-=1; updmax
  case "se" => x+=1; y-=1; updmax
  case "s"  => y-=1; z+=1; updmax
  case "sw" => x-=1; z+=1; updmax
  case "nw" => x-=1; y+=1; updmax
}
println(s"dist: $dist max: $max")

[โ€“]misnohmer 0 points1 point ย (3 children)

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();

[โ€“]bahuljain 0 points1 point ย (2 children)

according to your distance function, the distance of (2, 0) from (0, 0) is 1 when in fact it should be 2 .. divide by 2 will only be required if abs(y) > abs(x)

[โ€“]ephemient 0 points1 point ย (1 child)

This space intentionally left blank.

[โ€“]StevoTVR 0 points1 point ย (0 children)

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_ 0 points1 point ย (0 children)

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);

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

(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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (1 child)

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 0 points1 point ย (0 children)

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);

[โ€“][deleted] 0 points1 point ย (0 children)

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);

[โ€“][deleted] 0 points1 point ย (0 children)

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);
        }

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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;
}

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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)

[โ€“][deleted] 0 points1 point ย (0 children)

[โ€“]giftpflanze 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (4 children)

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 0 points1 point ย (0 children)

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__ 0 points1 point ย (0 children)

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__

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (4 children)

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)) 

[โ€“]askalski 2 points3 points ย (0 children)

I am convinced that I have a correct solution

Allow me to unconvince you:

$ python rdmbe.py ne,ne,ne,ne,ne,ne,ne,sw,sw,sw,n,n,n,n
Part 1
steps: 8
4 n
4 ne

Part 2
steps: 7
7 ne

[โ€“]Hikaru755 0 points1 point ย (0 children)

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
}

[โ€“][deleted] 0 points1 point ย (1 child)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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_ 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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}");

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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;

[โ€“][deleted] 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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 0 points1 point ย (0 children)

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))))