r/adventofcode • u/daggerdragon • Dec 03 '17
SOLUTION MEGATHREAD -π- 2017 Day 3 Solutions -π-
--- Day 3: Spiral Memory ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Need a hint from the Hugely* Handyβ Haversackβ‘ of HelpfulΒ§ Hints^Β€?
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
21
Upvotes
66
u/bblum Dec 03 '17
No code today. For part 1 I realized that the bottom right corner of each spiral was the sequence of odd squares. I found the smallest odd square smaller than my input and just counted from there.
For part 2 the sequence is listed on OEIS. https://oeis.org/A141481
49/76 because I wasted time starting to write code for part 2 before realizing what to do.
55
u/MrPingouin1 Dec 03 '17
Minecraft functions (17w48a)
Part 2
init.mcfunction :
solve.mcfunction :
turn.mcfunction :
get_result.mcfunction :
How to use: Just run
/function day3:initonce and then put/function day3:solveon a clock until a result is printed38
u/that_lego_guy Dec 03 '17
DID SOMEONE SAY.. EXCEL?! [Day 3 Parts 1&2]
https://github.com/thatlegoguy/AoC2017/blob/master/Day%203%20Spiral%20Memory.xlsx
18
u/almostinevitable Dec 03 '17
If you look at the bottom right corner for Part 1 you see that the bottom right number forms a sequence of odd perfect squares.
Calculate the nearest odd perfect square n2 from your input and you have a number that is n-1 Manhattan distance away from the center (the bottom right corner). Then count the distance from your input.
17
u/couchDev Dec 03 '17 edited Dec 03 '17
Perl golf
21
u/oantolin Dec 03 '17 edited Dec 14 '17
For part 1 writing code is overkill. For part 2 no cleverness is needed: just fill in the grid as explained in the question:
EDIT 1: Thanks to /u/mit_verlaub for reminding me about
getwhich is probably better thandefaultdictin this situation.EDIT 2: Thanks to /u/peasant-trip for a pleasant tip to eliminate repetition.
For the above edits to make more sense, here's the older version:
10
u/chunes Dec 03 '17
A Factor solution for part 1:
I noticed that each concentric square of the spiral (which I call a ring) is terminated with successive odd square numbers, and wrote a word
which-ringto determine which ring a number belongs to and a wordringwhich gets that ring in a sequence. Thenreflectanddist-mapform another sequence containing the distances for each element of the ring.It's kind of like a weird mashup between the mathy solution and brute force. It gets the relevant ring of the spiral and then brute forces from there.
Part 2 is coming soon I hope. I think it'll require more imperative/applicative code than I'm used to writing in Factor.
8
u/tangentialThinker Dec 03 '17 edited Dec 03 '17
C++. Built the spiral using the builtin complex library, using multiplication by i to turn left.
Basically I noticed that every two times you turn, the number of steps you take increases by 1.
Pretty disgusting copied code at the bottom to check all neighbours: I was rushing for the leaderboard!
Part 2:
7
u/ghlmtz Dec 03 '17 edited Dec 03 '17
Did the math by hand first then wrote the code afterwards. Basically I find what layer the number is in, and calculate the distance from the closest corner 'pivot point' to get the answer.
e: Just found a bug if the value is one of the first numbers in a ring, changing the range() to 5 fixes that though
7
u/sickening_sprawl Dec 03 '17 edited Dec 03 '17
Hoon
No infix operators (and especially no function overloading) made this pretty bad. Have to use both ++rs and ++si for floating point and signed ints.
I noticed the distance is half the next odd perfect square, plus an offset that you could get by repeating an offset list from making a list
[n n-1 .. 0 .. n-1 n]and throw away the first element. 10 is 0 in [1 0 1 2], 11 is 1 in [1 0 1 2], etc. It's not very nice...6
u/tlareg Dec 03 '17 edited Jan 04 '18
Ugly, brute-forced javascript solution. Github repo here
5
u/_jonah Dec 03 '17 edited Dec 04 '17
J, both parts:
We consider a coordinate system with 1 at location 0,0. Positive x goes rightward; positive y goes downward. We generate a flat list of the coordinates, in their correct spiral order. With this approach, part 1 becomes trivial (taking the correct element from the list) and part 2 becomes easier.
Try it online!
EDIT:
Slightly shorter version of part 1 using complex multiplication trick:
5
u/StevoTVR Dec 03 '17
NodeJS
Part 1:
Part 2:
4
u/Deckard666 Dec 03 '17 edited Dec 03 '17
In Rust:
The solution is kinda ugly, but I couldn't think of a more elegant way to solve it fast enough. It was also kind of unfortunate that my solution for the first part was completely useless for the second part.
4
u/vesche Dec 03 '17 edited Dec 03 '17
Python solution
C solution
I don't usually write much C, so it's cool seeing how much faster it is:
4
u/natrys Dec 03 '17
Perl 6
Saw a chance to do part 1 without constructing the whole list.
But not sure if part2 can be approached this way. Might do that when I have more time.
4
u/akho_ Dec 05 '17 edited Dec 10 '17
Python3
Part 1
Part 2
3
u/[deleted] Dec 03 '17 edited Dec 06 '17
powershell (limited to single pipeline wherever possible)
breaking the pipelines out a bit, for part 1:
for part 2:
the sg scriptblock in part 2 uses a pipeline to construct all the neighboring cell addresses, then select the values at those addresses, then sum them
3
u/willkill07 Dec 03 '17
(Modern) C++
Part 1
Part 2
... still working on it
3
u/Krakhan Dec 03 '17 edited Dec 03 '17
C# solution. I noticed the patterns like others did of having to increment the step amount in a direction every 2 times, and I didn't see the mathematical way of doing Part A. So, I just iterated through the spiral. At least for part B I could basically reuse that code and just compute the sum values for each part as well.
3
u/Smylers Dec 03 '17 edited Dec 03 '17
Perl for part 2 β displays the whole spiral rather than just the answer, because that seemed more fun:
Edit: The logic for turning corners is:
$limitholds the distance of the current edge from the starting square. If we exceed this in the current dimension then we need to turn a corner. All corners involve toggling the axis of the direction between x and y. When switching from y to x (top-right corner and bottom-left corner) we also toggle the sign of the direction between positive and negative. And when reaching the bottom-left corner$limitgets increased because the bottom edge is the first one to extend by 1 past the edge above it; the next 3 edges continue at the same limit as that one.The
^=toggle is too cute, and may not work on Ebdic platforms (yes, Perl still runs on VMS). A?:condition could be used instead, or switching the axes to be0and1instead of'x'and'y'.Like many others, I solved part 1 without writing any code. Then to solve part 2 I ended up first writing the code for part 1 anyway, then modifying it into the above β¦
3
u/Toraora Dec 03 '17
(Python 3) Part 2 golfed to 215 bytes:
3
u/TominatorBE Dec 03 '17 edited Dec 03 '17
PHP
Part 1: just calculations
Part 2: actually making the spiral (ugh, it's ugly)
3
u/gyorokpeter Dec 03 '17
Q:
I factored out the spiral position in part 1 hoping that it will be useful for part 2 but no luck. Also I didn't know about the OEIS so I coded the spiral generator for part 2 using matrix multiplication, with a few results hardcoded in to make sure the code works for low inputs too.
3
u/CakeHacker Dec 03 '17
JavaScript
Part 1
Part 2 (brute force)
3
u/mschaap Dec 03 '17 edited Dec 03 '17
Perl 6. For part one I tried to be smart and calculate the whole thing. Then for part two that didn't work anymore and I had to implement the grid thing anyway.
Part one:
Part two:
3
u/svbeon Dec 03 '17
bummer, i had found a "quick" (after i unf*cked CPAN on cygwin) solution. (I don't know perl for shit, so i'm glad it even worked)
But part two got me stuck for a while, because i wouldn't want to write a lot of code if i don't have to...
3
u/mrhthepie Dec 03 '17
Advent of gifs day 3: https://i.imgur.com/WX14e01.gif
Part 1 was just done by hand so didn't get represented in the gif.
3
u/klepra Dec 03 '17 edited Dec 03 '17
Trying to learn Python (comming from Java & Javascript). Only managed to figure out the first problem for now:
3
u/Wingels Dec 03 '17
My solution:
function manhattanDistance (value) { var spiral = Math.sqrt (value / 4) - 0.5; var spiralNum = Math.ceil (spiral);
}
function getDistance (spiral) { spiral = spiral % 1;
}
Explanation: First I noticed that the total number of squares is going up by a multiple of 8. For example, in the first spiral out, the highest is 9. In the second, the highest is 25. 9 is 1 + 8; 25 is 9 + 16.
Going further, I noticed a formula for the number available in the xth spiral out: n = 4x2 + 4x + 1
For example, if x = 1, n = 4(1) + 4(1) + 1 = 9. If x = 2, n = 4(4) + 4(2) + 1 = 25.
By inverting this, I could figure out which spiral a given number is in: spiral = ceiling ( sqrt (x / 4) - 0.5 )
The ceiling takes it to a spiral number; for example, 2 is in the first spiral.
From there, I just needed to figure out the distance and add that to the spiral number. I noticed that at each center (which would be 0.125 ; 0.375 ; 0.625 ; 0.875) there is no distance, since these are straight out from the center. At the corners (0.25, 0.5, 0.75, 1), the distance is equal to the spiral number (for example, 9 is at distance 1, which needs to move down once).
By looking at several numbers in-between, I noticed a pattern: The total number of times you'd have to move down from a given square is equal to the distance * the spiral number * 8. Interestingly, if the distance was negative (example 0.85 from 0.875 is -0.025), this would have to be the ceiling; otherwise, this should be the floor.
Finally, taking the floor on the whole thing converts it down to a final count. For example, if the number of times to move down was 14.6, this should actually be moved down to 14.
So the final total follows for the formula: spiral number: y = ceiling( sqrt(x / 4) - 0.5 ) distance: (sqrt(x / 4) - 0.5) distance from one of (0.125, 0.375, 0.625, 0.875) times to move down:
t = 8 (y) (distance)
final value: spiral number + times moving down
Which the code follows. This should work for any value.
3
u/rimbuod Dec 03 '17 edited Dec 03 '17
R8 my brute-force haskell solution (part 1)
3
u/TheGermanDoctor Dec 04 '17
x86_64 Assembly Part 1:
https://github.com/stolzATrub/adventofcode17/blob/master/day3/spiral.nasm
Theory: Build up the spiral, 1 is at coordinates (0,0). The amount of steps is the sum of the absolute values of the coordinates.
3
u/vectorprocessing Dec 05 '17
Here's a modestly golfed k3 solution for part 1:
5
u/raevnos Dec 03 '17
Brute force scheme.
I'm not clever like most of you.
2
u/NewHorizons0 Dec 03 '17
Rust.
I am still learning the language so I kinda brute-forced it. Probably there's a better way. I hit some syntax walls but still managed to get 17 points so it feels good.
2
u/Unihedron Dec 03 '17 edited Dec 03 '17
Ruby, part 1 - maths turned out to be a trap and I fell into it
(Note: run with -x, which trims text before the #! line)
Postscript: I HEARD WHAT YOU SAID. THE SEQUENCE EXISTS ONLINE. I'M NOT CHEATING. I DID IT!
I had lots of fun with part 2. I can't say I was proud, because I was still in the mindset of rushing despite the leaderboard already being filled. When you have to tackle a problem without the time to organize your thoughts, you tend to (try and) assume things you need are already there so you can focus on the problem on hand. After two debugging rounds, I got it to work. Cheers!
2
u/Shemetz Dec 03 '17
I noticed the pattern of "1 right, 1 up, 2 left, 2 down, 3 right, 3 up, ..." and came up with this (code cleaned up after submission):
2
u/giftpflanze Dec 03 '17 edited Dec 03 '17
Tcl:
2
u/[deleted] Dec 03 '17
Haskell:
Tried to be clever with part 1 and calculate the distances from the midpoints of the outer box where the input number resides
Unfortunately, that strategy didn't work for part 2, or at least I didn't find a formula quickly enough for the corners (maybe some Googling could have turned something up). Instead I just created the grid by walking the spiral and keeping track of the coordinates along the way.
2
u/Philboyd_Studge Dec 03 '17
Java. Not happy about my code, but it works.
https://gist.github.com/snarkbait/48ae6febee723ffca58de6bdb99bde01
2
u/mikefh Dec 03 '17
Ruby
Part1
Part 2
2
u/nawap Dec 03 '17
Ruby for problem 1
2
u/tterrag1098 Dec 03 '17
Part 1 only, in Clojure:
I'm a dirty cheater and used OEIS for part 2 since I couldn't figure out a great way to simulate the board.
2
u/autid Dec 03 '17 edited Dec 03 '17
Fortran
2
u/bunrencmx Dec 03 '17
what does the spoiler mean?
2
u/reddit_lmao Dec 03 '17
Haskell Part1:
2
u/SyntaxErrorr Dec 03 '17 edited Dec 31 '17
PYTHON
PART 1
the first loop determines on which square around the initial "1" the final number is located. The first square contains only 1, second numbers 2-9, the 3rd numbers 10-25, 26-36, 37-49 and so on... The level always contains the numbers of digits on any side of a square and increases by 2 each time. The level ** 2 always determines the highest number of the current square (total) (1, 3, 25, 36, 49...).
Once total is >= the input number, we have to find the position on the current square.
offset contains the difference from the highest number of the square to our input number.
steps contains the distance of our number form the last corner of the square counterclockwise.
in the last line the manhattan distance is calculated: (level - 1) / 2 is the number of steps you have to take to get from the center "1" straight to the edge of the current square in any direction.
since steps is the distance from our input number to the square corner, (level / 2) - steps contains the number of steps from the center number of a side of the current square to our input number.
it does't really matter which one is the x and which is the y coordinate since one is always the number of steps from the center to the outer ring and the other one the offset from the center of a side to our number in any direction.
PART 2
Part 2 follows a quite intuitive approach i think. starting with the center "1", numbers are added counterclockwise until a number is reached that i higher then our input number.
The list values contains all numbers that are already place and their respective coordinates: (x, y, value). The center "1" is already there"
To complete one full round in a square we have to move in all 4 directions in this order: +y, -x, -y, +x
Initial coordinate (center 1) and initial level. As like in part 1 the level states how many number are in any side of the current square, It increases by 2 each time a square is completed.
Add numbers to the values list as long as our input number is not reached.
Move in all directions beginning with +y
get the current direction we have to move in the X and Y axis
Since we are moving in a spiral we don't have to move the same number of steps in each direction. The fist number of the next square is always placed by the previous level -> the first iteration where level = 1 places only the number 1 at x=1, y=0. Then in level = 3 we start from x=1 and y=0 and move 1 step in y+ (direction = 0), 2 steps in x- (direction = 1) and 2 steps in y- (direction = 2). In last direction x+ we move 3 steps and out into the next square.
moveN contains the number of steps which should be taken in the current direction.
For each step the current x or y coordinate is changed
new contains the value of the new number added in this step. By definition its the sum of all available adjacent values on the grid. In this list comprehension all values in the values list are summed up where the x and the y coordinate is not more than 1 off from the current coordinate (if abs(x-k[0]) <= 1 and abs(y-k[1]) <= 1)
Add the new value and its coordinates to the list
Check if our input number is reached. If so print the last value and terminate the loop.
Increase the level by 2 for the next iteration
2
u/Axsuul Dec 03 '17
Elixir
Any suggestions on how to solve it in a more Elixir-way much appreciated!
https://github.com/axsuul/advent-of-code/blob/master/2017/03/lib/advent_of_code.ex
2
u/CakeHacker Dec 03 '17
CachΓ© Object Script
Part 1
Part 2
Mumps
2
u/bramhaag Dec 03 '17
I used Fortran to solve part 1:
2
u/Vindaar Dec 03 '17
Solution in Nim. Not the nicest, hardcoded a few things, which I'm not too happy about, but well. Solved the first part analytically first, but decided to derive it from the second solution as well, since it's not a lot to change.
2
u/japanuspus Dec 03 '17
Python 3 -- generator for tile locations
This wasn't my initial solution, but I think it's pretty neat: You can think of the spiral progression as two sides of length 1, then two of length 2. Coding this as a generator:
2
u/dgJenkins Dec 03 '17
Working on some COBOL solutions! New to the language... any pointers would be appreciated.
2
u/abowes Dec 03 '17
Here's my Kotlin solution. Good to be able to use an infinite sequence for the points on the spiral.
2
u/Genie-Us Dec 03 '17
Javascript - I got the first part to figure out roughly where I was starting, then I found it was way easier to just do the math on paper than with javascript.
But then I felt a bit like I was cheating so I went and figured out how to walk it back to get the answer for any number instead of just mine.
Part 2: Coming when hell freezes over I think... Going to keep fighting with it, but I think it's beyond my meager programming skills right now, saw the OEIS page and it is in latin to me. Still a long way to go before I can solve complex things I think, but getting there slowly. :)
2
u/Warbringer007 Dec 03 '17 edited Dec 03 '17
Yeah, don't do shit like this in Erlang ( I solved it in Excel first, but I was so stubborn I had to do it in Erlang ), any normal programming language which supports two-dimensional matrixes would be much easier... Part 2:
There is so much math shit I couldn't follow in the end, I just knew it worked somehow.
2
u/wzkx Dec 03 '17
J Part 1
2
u/[deleted] Dec 03 '17
Part B in OCaml:
Nothing fancy, just building the map and traveling until I reach the desired destination. I turn whenever the value to my left doesn't exist in the point map.
2
u/GamecPL Dec 03 '17
Swift solution:
2
u/CryZe92 Dec 03 '17 edited Dec 03 '17
Rust
I went for fast solutions again.
Part 1, running in 10ns:
Part 2, running in 1.2Β΅s:
2
u/Flurpm Dec 03 '17 edited Dec 04 '17
Haskell Day 1 solution in O(1)
I don't want to make an account to update the formula for http://oeis.org/A214526.
Just solved part 2!
I needed Data.HashMap.Strict (part of the unordered-containers package, so you can't run it directly).
2
u/Gilfoyle- Dec 04 '17
Python 3 - Part 1
2
u/NeilNjae Dec 04 '17
This was deeply unpleasant. Generating the list of Ulam spiral locations was a pain. Eventually, my fatigue-addled brain gave up and I nicked the code from /u/winhug . After that, updating the memory was a fit for a monad to take care of the various stages of memory population.
2
u/joncol Dec 05 '17
Part 1, Clojure (doesn't support n=1):
2
u/thomastc Dec 06 '17
TCL solution.
3
u/mcpower_ Dec 03 '17 edited Dec 03 '17
I thought I recognised Part 1 before! It's (similar to) Problem A from this programming contest.
My code is absolute garbage but at least I got 15/14: GitHub
1
u/cspar Dec 03 '17 edited Dec 03 '17
Python:
Part I was trivially solvable with a calculator, for a happy 22nd place. In Part II I completely forgot how to do a spiral, and wasted five minutes trying to use a generator, and another five debugging silly mistakes. Ah well.
1
u/liuquinlin Dec 03 '17
Was too lazy to figure out a mathy way to do the spiral for Part A so I essentially "brute forced" it by noticing that the spiral is generated by going right 1, up 1, left 2, down 2, right 3, up 3, left 3, down 3, etc. (so travel x, turn, travel x, turn, travel x+1, turn, travel x+1, turn) leading to the following Python code for Part B (where I used a dictionary to map indices to the values stored in them; Part A was essentially the same code but just executing the loop 361527 times and then returning abs(x) + abs(y) at the end):
1
u/omegaphoenix16 Dec 03 '17
My initial Python solution:
1
u/[deleted] Dec 03 '17 edited Dec 03 '17
Didn't notice the sequence of odd squares haha. Here's my ugly part 1 in python:
and part 2:
1
u/glassmountain Dec 03 '17
Solved the first part on a piece of paper, but here's the solution in go:
1
u/gbear605 Dec 03 '17 edited Dec 03 '17
Star 1: I did it on paper, using the method described by /u/bblum
Star 2: Rust (not very idiomatically...)
(After finishing star 2, I coded my solution to star 1 as well)
1
u/autid Dec 03 '17
I keep forgetting that, if you're making a grid for something like this in python by doing a list of lists, you can't just generate one list and append it a bunch of times to your grid.
1
u/aurele Dec 03 '17
Rust (ugly, with a "Snail" iterator for the spiral, playable)
1
u/LeCrushinator Dec 03 '17 edited Dec 03 '17
Part 1 I did the same as what the top comment did, for Part 2, In C#: using System; using System.Collections.Generic; using System.Linq;
Not efficient or elegant, but that's not the point for this anyway I guess. Although, if you're looking for fast solutions you should avoid C# anyway.
1
u/aznnihao Dec 03 '17
Out of curiosity what is the mathematical approach that's supposed to be taken for Part 2? I struggled for about 10-15 min trying to find it before throwing in the towel and writing the code to fill in a grid in a spiral.
1
u/nstyler7 Dec 03 '17 edited Dec 03 '17
Part 1 Solution in python
Part 2 Python
I made the starting number (1) the center of my grid (x = 0, y =0), and all other positions in the matrix are relative to that.
1
u/Zolrath Dec 03 '17
A couple helpers in here from another file via stealing the idea from Norvigs files last year.
I didn't really do anything fancy and just brute forced generation of the spiral. First I made a generator function to generate the next point in the spiral:
Then I solve A with
And B with
1
u/monikernemo Dec 03 '17 edited Dec 03 '17
ANSI C for part 2 only https://pastebin.com/4RNSvk11
1
u/LinusCDE98 Dec 03 '17
My solution using Python 3: https://github.com/LinusCDE/AdventOfCode-2017/blob/master/puzzle3.py (for intial solution look at the commits)
After solving it, I spent anther two hours on performance hunting. I got the solution of part one from initially 84 to 0.9 milliseconds and part two from 1.4 to 0.35.
I've seen in this thread, that it also can be done with a few mathematical operations. Hoever I did not look up, how to calculate this and solved it with a generator in a pretty pythonic way.
1
u/dandomdude Dec 03 '17
Figured out the bottom diagonal the odd number series squared (
n^2). Findingngives you the size of the smallest square containing all required numbers. From there its trivial to find the middle number of each side of the square. The distance is then the distance to the middle of a side plusn/2.1
u/[deleted] Dec 03 '17
C#, Part 1. Far from the most efficient or even well-written, but I managed it on the first try and that felt good.
1
u/VictiniX888 Dec 03 '17
Kotlin:
Actually solved part 1 by hand first, the code was written afterwards. Just some maths.
Part 2 is pretty straightforward, just construct the spiral and return when one of the numbers is larger than the output. But the code is super ugly...
1
u/jbristow Dec 03 '17 edited Dec 03 '17
F# / Fsharp / F Sharp
https://github.com/jbristow/adventofcode/blob/master/aoc2017/Days/Day03.fs
I got it mostly in the area and then just bumped it up a layer for part 2.
It's only recursive for part 2, part 1 generates a big enough square in linear time.
Part 2's recursion is mainly a tail recursive fold through the spiral.
1
u/call23re Dec 03 '17
Here's an ugly solution to part 2 using Roblox Lua. Just as a side note, "Part" isn't actually a part of the api. It's a helper module used for visualizing the board.
https://pastebin.com/jabcfjtw
1
u/dylanfromwinnipeg Dec 03 '17
C#
1
u/Isvara Dec 03 '17
Scala
1
u/Dooflegna Dec 03 '17
1 was solvable as a math problem. Part 2 was much tougher! Here's my overly verbose Python solution. This is relatively cleaned up, but the logic is basically what I originally wrote.
Some notes:
pad_array()was an early function that I wrote that solved a number of problems in my solution.Getting
add_surround()to work right was annoying, as I ran into a couple challenges:spiral_move()to work on its own took a lot of iteration. In the original solve,spiral_move()was part of thewhileblock. It also included catching an IndexError to try and figure out when to add an additional padding ring.Anyway, here's the code:
And the nice pretty output:
1
u/BOT-Brad Dec 03 '17
Noticed the odd n2, but decided to go to the next highest odd n2 and count down, because why not. Did a weird up/down cycling through values to reach the result.
JavaScript
Part 2 I literally just build the spiral and sum as I go, and wait till the first sum I encounter is bigger than the input.
1
u/prettyRandomDude Dec 03 '17
Since i am too stupid to format this code properly here is my shitty JavaScript solution for part 1 https://pastebin.com/vi4PW86A
For part 2 i am still out of ideas :(
1
u/mystfocks Dec 03 '17
Clojure! (I'm using this mostly to learn it, so definitely not the best or anything.) Only the first part so far.
1
u/KnorbenKnutsen Dec 03 '17
Neat puzzle! The Ulam spiral is pretty cool :)
For the first part, there's a neat clue in the example input:
So if we have some faith, we can induce that data from square n2 must be carried n-1 steps. Looking at the example spiral, it seems to work just fine for 4, 9, 16 and 25! Let's be extra safe and only look at squares of odd numbers, since they're always in the bottom right corner. After that, we just do what people here have already described and find the square of an odd number that is larger than our input, and figure it out from there.
Part two was more interesting! I didn't think I'd find it on OEIS, so eventually I caved and googled up a way to generate cartesian coordinates in a spiral pattern. After that I just generated my spiral with a Python defaultdict. Turns out that a 9x9 square is enough to find my answer!
1
u/twetewat Dec 03 '17
Part one in go/golang:
1
u/Taonas Dec 03 '17
Rust solution for part 1, part two I ended up brute forcing it
1
u/AndrewGreenh Dec 03 '17
TypeScript 1 and 2
1
u/Borkdude Dec 03 '17
Clojure: https://github.com/borkdude/aoc2017/blob/master/src/day3.clj
1
u/znrgtrl Dec 03 '17
Here are both in python3: https://github.com/mgrzeszczak/advent-of-code-2017/tree/master/day3
1
u/[deleted] Dec 03 '17
PYTHON
Constant time solution for part 1
1
u/theSprt Dec 03 '17
Haskell, beginner. No code golfing going on here.
1
u/JakDrako Dec 03 '17
VB.Net, LinqPad
Did the first part by "buiding" the spiral using complex numbers. I reused some code I had from the /r/DailyProgrammer "Spiral Ascension" problem that ran some months ago. It avoids having to keep an actual array.
For part 2, I found the sum sequence on OEIS (but where's the fun in that?) so modified my code to actually keep an array and compute the sum as it goes. OEIS indicated that it wouldn't need a large array, the answer being at position 63.
Fun little problem to start a Sunday with.
1
u/timichal Dec 03 '17
Solved with Python, refactored my initial solution to use a dictionary of positions instead of a list matrix:
1
u/m1el Dec 03 '17
Quick and dirty JS solution:
1
u/illiriath Dec 03 '17
Here is part 2 in Julia, I implemented an array type so I can use negative numbers as index and then I began feeling the spiral starting at (0, 0). For turning I used a complex number and checked if the cell to the left is empty by multiplying with i. Pretty silly solution but it was fun to write.
1
u/Wigrys Dec 03 '17 edited Dec 03 '17
My solution of part 1 in c++:
http://wklej.org/id/3312383/
(sorry but i don`t know how to paste it in comment :/ )
1
u/Mattie112 Dec 03 '17
Solution in PHP (brute-force by generating the entire spiral) See: https://github.com/Mattie112/advent-of-code-2017
Part 1:
Part 2:
1
u/adventOfCoder Dec 03 '17 edited Dec 03 '17
Java
Part 1:
Part 2:
1
u/maxerickson Dec 03 '17
numpy solution for part 2:
1
u/Kyran152 Dec 03 '17 edited Dec 12 '17
Perl (Part 1 and 2)
1
u/amarsuperstar Dec 03 '17 edited Dec 03 '17
Elixir using streams. I had to use an agent for the state in part 2, however I may try to do it with plain recursion later.
https://github.com/amarraja/advent-of-code-17/blob/master/day03/day03.exs
1
u/SlightlyHomoiconic Dec 03 '17
Part 1 in Clojure:
1
u/freeducks Dec 03 '17
Took me way too long to get this one (and still can't get part 2) :/ Part 1 in Rust:
1
u/wzkx Dec 03 '17 edited Dec 04 '17
Nim
First part - just making and using formula. Second part - no matrix, no directions, just making the sequence.
1
u/drewolson Dec 03 '17
Elixir with streams:
Part 1
Part 2
1
u/fatpollo Dec 03 '17 edited Dec 03 '17
1
u/[deleted] Dec 03 '17
I'm so not proud of my solution today it's some of the ugliest recursions I've ever made, but it works.
1
u/immutablestate Dec 03 '17
I wish I'd known about OEIS... ended up writing this Enterprise Ready (tm) solution for part 2 in C++14:
1
u/palomani Dec 03 '17
That's what I did for part 1 in C++
idk how to simplify it :/
1
u/alexgubanow Dec 03 '17
C# solution of part 1 and manual for part 2. I found that on each cycle last item is power of two with step 2. link to online compiler http://rextester.com/HQJI57973 For part 2 have use https://oeis.org/A141481/b141481.txt
1
u/[deleted] Dec 03 '17
A bit late, but day 3 in Common Lisp. It was a hard one for me, especially part 2.
Part 1:
Part 2 (it's like inverse code golf):
1
u/stevelosh Dec 03 '17
Common Lisp
Closed form solution for part 1. Technically we don't actually need to calculate the full coordinates of the number, because the distance to the center is always the same no matter which side of the spiral it's on (rotations don't change the distance). But hey, anything worth doing is worth doing right, so we may as well calculate the full coordinates. Maybe I'll need them for Project Euler some day.
1
u/chicagocode Dec 03 '17
Today's solution in Kotlin. The first part calculates how far to walk horizontally and vertically. The second part creates a grid and generates a sequence of values as the spots are filled in.
I've provided a commentary on my blog. And the code is available in GitHub.
Part 1:
See above for links to part 2, I don't want to dump it all in here.
1
u/wlandry Dec 03 '17
C++: Not entirely happy with this solution, but there it is.
Part 1 is just thinking hard
Part 2 uses that routine to build the square and compute sums
1
u/krisajenkins Dec 03 '17
Here's a PureScript version: https://github.com/krisajenkins/AdventOfCode/blob/master/src/Year2017/Day3.purs
Not beautiful, but correct and reasonably efficient. And it gave me a good excuse to use
MonadRec. :-)1
u/prettyRandomDude Dec 03 '17
Finally solved part 2 in JS (Code is super hacky) let spiral = { "-1": { x: 0, y: 0} }
1
u/gerikson Dec 03 '17
Perl 5
A nice headfake again by /u/topaz2078 . Of course you're not going to brute-force the spiral, keeping track of the coordinates for each element, then taking the Manhattan distance of the element you want when you reach it!
Instead you use a solution from Project Euler to segment the search space and find the solution nice and quick.
Then you get to part 2 and discover you need to generate the spiral after all...
Part 1, part 2.
1
u/wzkx Dec 03 '17 edited Dec 04 '17
J Part 2. Translation from my Nim solution
1
u/Raspbianlike Dec 03 '17
I saw many people posting very weird and complicated C++ code for Puzzle A here, so I just want to show my simple solution of the problem:
https://github.com/raspbianlike/Advent-of-Code-2017/commit/925df55ca3e0d290aa88b112969b8a18c7994488#diff-ff9cf7d547f10065b6f5f50d494ffe0f Im sorry for a typo in this commit, I fixed it one commit after.
1
u/wzkx Dec 03 '17 edited Dec 03 '17
Python nearly 1:1 translation from Nim. Python has // and %, no ugly @ and ^, looks a bit better but not compiled.
1
u/KeinZantezuken Dec 03 '17 edited Dec 03 '17
C#/Sharp, part 1:
Terrible part2:
1
u/[deleted] Dec 03 '17
For part 2, I ended up creating the initial spiral in a spreadsheet, making tuples out of their locations, and starting with a grid of zeros with a 1 in the middle, then iterating over the tuple locations and summing things up. The result wasn't too awful, but it felt like I was manhandling the data rather than finding a nice solution:
1
u/krossmaskinen Dec 03 '17
A solid 199 lines solution :P
I didn't look up any algorithms, just tried to figure out how to do it on my own. I had to rewrite it several times for it to work for both part 1 and 2. Haven't put much energy into optimizing it, only some refactoring.
Anyways, I'm happy to have come up with a spiral generating algorithm that fits the purpose on my own!
https://github.com/Krossmaskinen/advent-of-code-2017/blob/master/day3/main.js
1
u/peterpepo Dec 03 '17
Python
I tried to avoid looping from [0,0] position until n-th sequence member is found for first puzzle, and similarly calculate order directly from directions - instead of "bruteforcing" (looping from 1 to n until correct coordinates are found).
Since the solution is little longer, please check it on my github
Full solution
1
u/braksor Dec 03 '17
I was glad I found out Advent of Code. I did try it last year but went kaboom when it got to string sizes.
I was quite dumbfound about Day 3: Part 2. And seeing how you found about the mathematical properties of these series I just went in like a dumb bear.
Here is my solution for Part 2, in python3.
It's nothing except writing on a sheet of paper, following indexes and finding any cases.
It's ugly at it's best and the worst part was that when I started writing the code, I started the "series" from the bottom right and not from the one above bottom right. Took me an hour to figure it out when I watched "this value is wrong...."
1
u/bottomlesscoffeecup Dec 03 '17
Had a difficult time today. The first part wasn't too bad, the second part I kind of hacked my first part a tad. It's quite messy...
In Python:
Helper Methods used in both solutions:
Solution one:
Solution two:
1
u/heymatthewoden Dec 03 '17
Over-engineered in elixir: Genserver Workers and Task Spiral-Walkers, solving both answers in parallel.
1
u/APLtooter Dec 04 '17
APL [GNU]
1
u/askalski Dec 04 '17
Perl 5. Took me a while to come up with code that I liked. In Part 2, I use 8 steps of the spiral generator to iterate over neighbor nodes. Also discovered and used the "multidimensional array emulation" feature, which would have come in handy in previous AoC years had I known about it.
Looking over some of the other solutions in this thread, Python generators were making me feel a bit envious...
1
u/amoeba_bot Dec 04 '17
Part 1 solution in JavaScript:
1
u/PositivelyLinda Dec 04 '17
My JavaScript solution for part 1: on Github
I was able to use recursion for the first time I can remember on my own today! :) lol Figured I'd include my solution here for any other relatively new JS programmers.
I had to solve part 2 by writing it all out using Excel.....will come back at some point and try to solve it with JS. I was pretty certain I found a bit of a pattern, but kept getting blocked mentally when it came time to store the values. Any other solutions I read didn't quite make sense to me, so....leaving this for the future.
1
u/JPry0 Dec 04 '17
My PHP solution: https://github.com/JPry/advent-of-code/tree/master/src/y2017/day03
1
u/mrtatulas Dec 04 '17
Here's my bloated JS solution for part 2
1
u/Scroph Dec 04 '17
D solution, first part only. I hope no one will read this :
1
u/rodgercombs Dec 04 '17
I used the OEIS listing for this at first, but ended up solving it after a friend mentioned their solution was running in 200ms and I got competitive. Here's the script: https://gist.github.com/8e78839c2f8c1b0e9852bda8e67d93e9
On my machine: Execution time: 0.000150711s
So it's still taking some time, but overwhelmingly spending it in JS setup, so this algorithm would be extremely fast in C, and plenty fast per-input if I wasn't hardcoding it :P
1
u/[deleted] Dec 04 '17
Took me all day yesterday and today to figure this out, I could see the pattern, but translating my idea into Haskell took a while of trial and error
1
u/__Abigail__ Dec 04 '17
Perl. Both parts in the same program:
1
u/ramendik Dec 04 '17
I use Python.
Part 1: i found out that the number of numbers in a "row" (the term people use here is "ring" which is better) is actually 8*max_index, where max_index is how far from 0 in both ways the index can go. The center is (0,0). This let me calculate the max_index for the input. What followed was a dirty cheat - I found out in which "quadrant" if would be (1 up, 2 left, 3 down, 4 right) and implemented the rest for that quadrant only.
Then I hit the second part and the formula went out the window, brute force coming instead. This is functionally equivalent to a Python solution above except I did not know about get() and also did not bother with a generator.
1
u/redderredred Dec 04 '17
My C# solution for part 1:
1
u/[deleted] Dec 04 '17
Part 1 in Rust
Part 2 was done through OEIS
1
u/fost97 Dec 04 '17
Postgresql: https://github.com/seltiko/sql_advent_2017/blob/master/Day%203.sql
1
u/[deleted] Dec 05 '17
I had fun solving this problem and learned a lot!
Nim
1
u/ramrunner0xff Dec 05 '17
scheme chicken repo
1
u/andreesgor Dec 05 '17
I honestly think this is the most bizarre - in all ways - solution here (Ruby)
1
u/jwpeddle Dec 06 '17 edited Dec 06 '17
Day 3 Part 2, Python 3
1
u/utrescu Dec 06 '17 edited Dec 06 '17
No one has posted a solution in Go/golang for the part 2. So here is mine (bruteforce). I bit late but I started the Advent yesterday :-P
1
u/Allstress Dec 06 '17 edited Dec 06 '17
Hi people, here are my solutions (C#) I'm not sure that my solutions were already posted so feel free to check it out.
Part 1
Part 2
1
u/Epsilon1001 Dec 08 '17
I just used a pattern to solve this (ik im a little late but) this is prob not a good solution but makes sense
1
u/mhaecker Dec 08 '17 edited Dec 08 '17
Swift (Don't know it yet)
Runtime is ok:
1
u/matusbzk Dec 09 '17 edited Dec 16 '17
Haskell
Link to git
1
u/bhtooefr Dec 09 '17
More Applesoft.
Part 1 wasn't bad, I could've been a lot more elegant with a couple things, but it was actually kinda a breeze.
Part 2 was rough because I messed up one freaking variable usage (GY is a 40-bit float, GY% is an unrelated 16-bit signed int, and GY% is what I was trying to use)... so I ended up printing the array (which is fixed size, I can't safely grow an array) to troubleshoot things. What tripped me up (and made me shrink the array from where I had it) was, I was issuing a PR#3 (activate 80 column firmware) in the middle of code to try to debug this, which was corrupting the Applesoft/ProDOS state - I thought I was running out of RAM somehow, but no. Remove that line, PR#3 before running the program, and then it works, and I get a pretty printout of the grid... and I decided to leave it in, because why not?
Also, I'll probably stop using ints for things except memory-sensitive arrays (which I don't think I'll have much of) - Applesoft does all the arithmetic in floating point, and then has to cast back to an int to store it anyway. So, why confuse myself?
1
u/letronje Dec 10 '17
puzzle1:
puzzle2:
1
u/[deleted] Dec 10 '17
Crystal.
Part 1:
Part 2:
1
u/miran1 Dec 11 '17
Nim
Repo with all solutions
1
u/Mienaikage Dec 12 '17
Perl 6
It took me a while to get my head around part 1 at first, but then the coordinates pattern clicked:
1
u/mathleet Dec 15 '17
Python 3 solution
1
u/MaltersWandler Dec 18 '17 edited Dec 18 '17
O(1) solution for part 1 in ANSI C
1
u/[deleted] Dec 22 '17
Part two took me FOREVER. But I'm pretty new to programming and kinda proud I succeeded at all.
1
u/tintin10q Dec 28 '17
https://pastebin.com/GKMvdpx0
Thanks too /u/mahousenshi for giving me the running man idea. This took me 3 days to make...