/aocg/ - Advent of Code 2017 General #25

Previous thread: Don't crash the system edition

adventofcode.com/
>Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.
You need to register with an account but you can appear as anonymous.

The new leaderboard with empty space is
join-code: 43046-941b8011

The old (full) leaderboard is
join-code: 194764-c554ff91

Other urls found in this thread:

ghostbin.com/paste/vk3u2
pastebin.com/pu3tksHU
pastebin.com/vYTECnZe
pastebin.com/RH4nf92F
wiki.c2.com/?MakeItWorkMakeItRightMakeItFast
adventofcode.com/2017/day/23
github.com/petertseng/adventofcode-rb-2017/blob/master/21_fractal_art.rb
matt.might.net/articles/phd-school-in-pictures/
youtube.com/watch?v=wbdvo019mgM
youtube.com/watch?v=3NuFVQk_CCs
twitter.com/SFWRedditImages

in a scale from 1 to buttdevastation how hard do you think tonight's puzzle will be?

Last puzzle doesn't have 2nd part (2nd part is "have other 49 starts"). I expect it to be slightly harder but not butthurt. Wonder what shiny secret will be revealed on the calendar.
This year had very little graph searches, shame.

oblig. index post:
ghostbin.com/paste/vk3u2
- links to all /aocg/ 2017 threads
- links to first post after each puzzle was posted

>it's another "you can't just recursively calculate all possible values, you have to update the map with the new values" episode

>quite a lot of the first posts by day link directly to FUCK
Classy.

My input, visualized with networkx, and the correct path traced with paint

started feeling like a bit of a meme/cliche after a while tho

what's with the self edges?

Oh fuck, these fucking components can be rotated too? JUST

cmon lads, it's just a "max-est path in a graph" problem that's small enough that even brainlet solutions finish in a few seconds.
Just takes a bit to get the graph representation and traversal algo right.

>trying to be superior towards random people on Sup Forums

well, I supppose when you nowhere close to match top10 in leaderboards you have to resort to small prey

Yeah but it was a pain in the ass to add and delete each component twice.

>nowhere close to match top10 in leaderboards
pfft, as if it even makes sense to try
gotta pick yer battles m8
>you have to resort to small prey
now you're talking my language

but srsly, it really gets my dick hard (lel ebin rick morty ref, etc) to help others along with hints n shit. So who's struggling with what?

Are you doing 1 component -> 1 node?

cuz I tried that route and algo complexity started exploding.
then I did 1 port -> 1 node, and it became much easier

I have a map where the keys are ports and the values are lists of ports, and each component is added twice, in both orientations. So 3/7 would add 7 to the list associated with 3, and 3 to the list associated with 7. Both my solutions take almost exactly 1 sec to finish. How fast is your solution?

Pic related is the map created from the test input. (Ignore shit like "\n", the Erlang shell has a habit of printing lists that only contain some ASCII characters as strings).

>File: file.png (2.36 MB, 2316x1306)
>2.36 MB
Jesus fuck dude, I'm working with 16KB/s here. Throw in a single-color background alternative for us low-bandwidth folks.

>Both my solutions take almost exactly 1 sec to finish. How fast is your solution?
Doesn't make sense to make a comparison on vastly different CPUs, I'm running on a x86 pocket watch that seems to run ~3x slower than normal CPUs. Makes more sense to run both on the same box. You got a complete, self-contained piece of code I can run?

what are you talking about?

It needs an Erlang shell to be run, so it's not that self-contained.
Part 1: pastebin.com/pu3tksHU
Part 2: pastebin.com/vYTECnZe
Input: pastebin.com/RH4nf92F (just paste it into the Erlang shell and assign it to a variable)

In some previous cases you ended up re-calculating the same value a gorillion times when you did recursion the dumb way, and I thought that is happening here too. I was wrong tho, the reason my program ended up crashing was that it got stuck in an infinite loop because of the 45/45 component (I wasn't deleting visited components).

>responding on purely functional solution with purely procedural solution
package main

import "fmt"

var (
maxLength = 0
maxScore = 0
graph = make(map[int][]int)
)

func score(path []int) int {
sum := 0
for i := 0; i < len(path); i++ {
sum += path[i]
if i != 0 && i != len(path)-1 {
sum += path[i]
}
}
return sum
}

func inPath(start, end int, path []int) bool {
for i := 0; i < len(path)-1; i++ {
if (path[i] == start && path[i+1] == end) ||
(path[i+1] == start && path[i] == end) {
return true
}
}
return false
}

func search(path []int) {
if len(path) > maxLength {
maxLength = len(path)
maxScore = score(path)
} else if len(path) == maxLength && score(path) > maxScore {
maxScore = score(path)
}
for _, n := range graph[path[len(path)-1]] {
if !inPath(path[len(path)-1], n, path) {
newPath := make([]int, len(path), len(path)+1)
copy(newPath, path)
newPath = append(newPath, n)
search(newPath)
}
}
}

func main() {
var start, end int
for {
if v, err := fmt.Scanf("%v/%v\n", &start, &end); err != nil || v != 2 {
break
}
if _, ok := graph[start]; !ok {
graph[start] = []int{}
}
if _, ok := graph[end]; !ok {
graph[end] = []int{}
}
graph[start] = append(graph[start], end)
graph[end] = append(graph[end], start)
}
search([]int{0})
fmt.Println(maxScore)
}

I could have some memory on keeping the path in shared linked list and checking the visited nodes in O(1) way, till fast.
351.334478ms

>apt-get install erlang
>Need to get 39.6 MB of archives
Ah crap, not happening tonight at 16KB/s.

Alternatively, if you can be arsed:
case class Port(compId: Int, portId: Int, weight: Int) {
override val hashCode = (compId, portId).hashCode
var sibling: Port = null // necessary evil to avoid sibling.get
var peers = Array.empty[Port] }

def parseGraph(lines: Iterator[String]) = {
val compPortPairs = for( (l,cid)
a.peers = for {
b maxl || (l == maxl && w > maxw)) {
maxl = l
maxw = w } } }

val t0 = System.currentTimeMillis
for (inPort

Ran it, is 707 supposed to be the number of milliseconds?

yup
>println(System.currentTimeMillis-t0) // msec elapsed
>println(maxw) // weight of max lenght / max weight path

Neat, guess the mutable set version ought to run in ~450 ms, and the custom set in ~250 if the speedups stay the same

>lenght
I blame the keyboard

I've made all days so far but I've never come up with overly convoluted solution which gives subsecond result. Should I just end it right now on Christmas?

>never came up with overly convoluted solution which gives subsecond result
srspost: consider your priorities. Not worth it for getting the puzzle solved. Worth it for learning how to write faster code.
>Should I just end it right now on Christmas?
obviously¡

How do people even learn it? I learned most of the programming from my school/work projects. But rarely do I come in contact with these programming hacks.

> still havent finished day 21 or day 24
i really just want to save christmas

>rarely do I come in contact with these programming hacks
Consider reading the fucking manual for your language of choice

Well if it takes reading source code for every built-in function I don't think it's worth it.

Eh, there's enough material in computer science to last you a lifetime of learning.
Thus the question becomes what to prioritize. Gotta paretto optimize that bitch, ya dig? E.g. 20% of the material will help you in 80% of the cases, so don't autistically drill down into stuff that you'll most likely never need.

Now, which parts do you find difficult?
- basic programming language usage?
- application libraries?
- general algorithms and data structures?
That is, what do you feel you're not good enough in; even better - provide an example. E.g. "All these peeps talked about hexagonal coordinate systems on day 11 and I feel like a brainlet for not thinking it up myself" or something.

>20% of the material will help you in 80% of the cases, so don't autistically drill down into stuff that you'll most likely never need.
In other words, don't DFS where you should BFS dat dere knowledge graph

>reading source code for every built-in function
that's fucking retarded
JUST
- be aware of the general concepts (basic data structures & algorithms)
- occasionally spend half an hour figuring out how they're done in your language (ideally idiomatically)
- search around about your language's strong points and weak points
- occasionally keep an ear out for other languages and their pros/cons compared to yours
- right tool for the job - you wouldn't do web dev in assembly, you'd have an easier time doing a parser/compiler in haskal than in c, you'd have an easier time doing mutable data heavy algos in languages that don't declare jihad on mutability, and so on.

> tfw my friend, a classmate who barely ever does programming riddles, solved both parts of day 24 in about 10 minutes

programming just makes me feel like an inadequate brainlet.

>documentation is the same thing as source code
The absolute state of CS education

I'd say choosing the right method or 'putting it together'. I'm familiar about data structures, common algorithms, graphs, techniques and heuristics.
But sometimes I struggle to put it all together. For example:
- Day 23 - I tried to avoid the naive brute force (DFS/BFS) for so long, trying to find some structure in the data or some hint that would show that this is a special case of the longest path route (converting it to directed acyclic graph) to get linear algorithm.
- Day 22 - I would have never guessed to reverse engineer the input had I not read it here on /aocg/
- Day 21 - No problems, used set() to track non-clean coordinates. Part 2 took 20 seconds this way. Others figured out using simple 2D array is faster and effective (i mean it's basic space-time tradeoff principle)
- Day 20 - Completely buffled. Initially created dictionary with all permutated left hand sides of rules pointing to their right side. Then just brute force it using this dictionary. Took several minutes. (Later found solution that is able to perform 30K iterations in ~300ms)

What I meant was that documentation simply states the description, basic usage and examples. All of which I am already familiar with. But sometimes on stackoverflow some user finds 5 different way to get the same result and posts the execution times for some randomly generated data.
And the fastest way is almost never the straight-forward built-in function but rather some golfed combination of lambdas and side-effects.

You know how those guys on stackoverflow figure out 5 different ways to get the same result? They read the fucking manual

Well obviously I've been reading it wrong until today. Then I will make sure to read it more carefully next time.

>choosing the right method
>Day 23
Did you mean day 24?
>- I tried to avoid the naive brute force (DFS/BFS) for so long
Yup, did it in the past (and present, occasionally) myself. Try to remind yourself of the old project priorities mantra: wiki.c2.com/?MakeItWorkMakeItRightMakeItFast

If you can do the naive shit in 10 minutes and it runs for 5 seconds, it gets you to the "puzzle solved" state faster than [30 minutes to think up fancy algo + 0.5 sec runtime]. Sometimes that's the wrong approach (rarely, depending on the specifics), but in general, timebox the "think up fancy algo" to a few minutes, whip up the direct approach, get it solved, then you have time to optimize.

>Day 22
I think you have an off-by-one error there, dude.
>I would have never guessed to reverse engineer the input had I not read it here on /aocg/
It's hinted at in the problem description
>adventofcode.com/2017/day/23
>The coprocessor's ultimate goal is to determine the final value left in register h once the program completes. Technically, if it had that... it wouldn't even need to run the program.
Though I admit I just stroll by /aocg/ and read up the discussion (excluding solutions) to avoid the gotchas, so I probably also went in the RE direction due to /aocg/

>No problems, used set() to track non-clean coordinates. Part 2 took 20 seconds this way. Others figured out using simple 2D array is faster and effective (i mean it's basic space-time tradeoff principle)
Sounds good to me - "make it work, make it right, make it fast"

>Initially created dictionary with all permutated left hand sides of rules pointing to their right side. Then just brute force it using this dictionary. Took several minutes.
Odd, the 8-to-1 dict approach ought to take less than a minute - good enough for the "Make it work" stage. Hell, I started with a 1-to-1 dict and 50s runtimes.

>Later found solution that is able to perform 30K iterations in ~300ms
Alright, now I'm curious. What was it?

This year I got my first job as a junior developer.

Last year, shortly before I was hired, I tried aoc and mad either to day 12 before my knowledge and time reached their limits.

This year I'll count just completing it as a win. Next year I can worry about the auptimisation of my solutions.

T. Spent two hours writing a brute force DFS solution to day 24

Keep in mind that although it's "some user on stackoverflow," there are a lot of users on stackoverflow, so only one has to know the arcane combination of features that exactly solves the problem, and as you use the same language more you'll discover those features (either from testing or from reading about them) and be able to execute on them. Also, remember that some people on StackOverflow literally helped develop the languages they are answering in, so they are probably going to know a lot more about its inner workings than you by default.

Don't get discouraged just because someone else knows more than you.

Found the solution. I remember it wrong, it was 300ms for 10,000 iterations not 30,000.
Solution:
github.com/petertseng/adventofcode-rb-2017/blob/master/21_fractal_art.rb

According to the author:
1000 iters ~130ms
10000 iters ~300ms
100000 iters ~6seconds

to keep a balanced POV, google "Programming competitions correlate negatively with being good on the job" and the related discussions in the usual circlejerks (hn, leddit, etc)

For the goal of being a good worker, consider that the current owners of half your waking life Mon-Fri just want to optimize long-term (or short-term) profit. In other words, to keep tech debt under control, reduce risks, deliver deliverables, etc - depending on the industry and company.
Hell, I had a recent graduate at our place, who didn't know what a set was, after several months on the job. Don't think that affected him too negatively in the grand scheme of things.

For the goal of being "smarter than those other people. I'll show them, I'll show them all!", yeah, go nuts.

Wrote a recursive DFS which ended up working nicely but probably isn't that efficient. Hard part was finding time between all the eating and drinking I have planned for day 24 and 25

Yup, the usual "comparing their highlight reels to your 'behind the scenes'" stuff. Was that selection bias or?
That and knowledge is multi-dimensional
> matt.might.net/articles/phd-school-in-pictures/
, most people are retarded in a few directions, and great in a few other

>I had a recent graduate at our place, who didn't know what a set was, after several months on the job
wait, how does hiring completely incompetent people help a business optimize profit ?

I could see that, you can't have the mindset that you want to write the fastest code, you have to have the mindset that you write the most maintainable code that runs fast enough. On top of that, you never just have to solve one problem, once you're finished with one part of the code there is always another feature to write or bug to fix.

>completely incompetent
that's where you're wrong, kiddo

business doesn't care about your autism, it only cares if you can deliver. Dude could deliver well enough to have the company extend his contract after the trial period.

Now knowing what a set is - embarrassing? Yep. Real life consequences? Well, the workers in the company collaborate, since they aren't retarded. I saw he had a problem that needed a set., dude was doing it himself with a list. I introduced him to sets with pen, paper and code in 5 minutes, and from there on after he knew how to use sets.

That does show he had some fundamental gaps in his knowledge, but he was QA, so gaps in DS&A had a much smaller effect on his performance.

good observations. To further extend: most times it's useful to consider the priorities of the environment you are in.
- Line of business code? Maintainability and extensibility are high priorities. Defensive coding to survive the onslaught of pajeets (see also: half of Java/C#'s raison d'être)
- SV webshit startup? MVP as fast as possible, "move fast and break shit", gotta show growth and get bought.
- University ivory tower research-level code? Elegance, trendies hype-techniques to increase chance of getting published and cited. Publish or perish baby, gotta get em grants.
- AoC style puzzles? Choose your own adventure
- FastAsPossible-to-write smug
- FastAsPossible-to-run smug
- RustAsPossible "protecting against memory leaks and data races in a single-threaded 50-liner" smug
- LispAsPossible "I haven't heard of the lisp curse" smug
- Elegant "muh readability" smug
- etc

>Hard part was finding time between all the eating and drinking I have planned for day 24 and 25
good priorities m8

>we somehow ended up with 25 threads for 25 days

Thread-preserving bump

Final boss fight soon

Penultimate calendar update
If posterity wants to read day 23 they'll have to find the image from the archive

So since I've got nothing better to do, I'm trying the puzzles from pass years.
In this puzzle am I supposed to implement a MD5 hash?

I think the intention is that you use an existing MD5 implementation

15 minutes left

12 minutes left

i dropped off the wagon around day 15 since i've been visiting family since then. how many lads have stayed in it all the way since day one?

>how many lads have stayed in it all the way since day one?
little over 20

I'm number one on the private leaderboard with my co-workers. They're mostly a bunch of normies who go to bed at 10pm though so a week in all but two gave up when it was apparent I'd always be winning by nature of the fact I stay up until 4am.

the full leaderboard has 21 guys with 24 gold stars (out of 150 that joined the leaderboard at the beginning of the month)

lets have a moment of silence for those we lost along the way

There's still about 30 of us left
There might be more in the other leaderboard

10 MINUTES

LESS THAN 2 MINUTES BE FOR FINAL BATTLE!!

ALL UNITS! CHECK YOUR COMPILERS AND YOUR MACHINES!!
MAY GOD BE WITH YOU THIS CHRISTMAS!

PREPARE FOR DROP!

merry xmas guys

FUCK

the first two weeks i stayed up til midnight to do this stuff every day to get a good score even though i'm a brainlet who'd take like one/two hours to do even the easy ones. i have a normal 9 am job so it was tiring.

then i missed like two days in a row and dropped 10 leaderboard spots and lost my resolve to continue

this doesn't seem hard at all after just skimming the prompt.

so i assume i'm overlooking one specific aspect of this that will make it double black diamond difficult

>xiaowucl has 4 seconds between first star and second
how?

>10 points
Press F

There is no second part. You just click a button at the bottom and get it automatically.

FUCK

Check again, friend :^)

>00:17:48 252
Are you serious? So many people did it that fast?

That wasn't hard.

This one wasn't even a hard one. The was no string parsing of input. It was just write some logic rules to manipulate a pointer, then do a sum at the end. They didn't even make you do 10 trillion loops or anything stupid.

Fantastic job user!
That is what I want to see!

Congratulations to #193354 for refuting the chinks and defeating the redditors!

Merry Christmas to all and to all a good night

Apparently I'm a total brainlet for writing a parser and interpreter instead of just hardcoding the program from the input. Ranked #77 and #74 as a result. But, I only needed #83 or better on each part in order to win:

From all of Sup Forums, well done user

I guess I lost time writing some stupid parsing
def day25():
L = []
for abc in get_input().split('\n\n'):
L += [abc.split('\n')]
tape = dict()
i = 0
instr = 1
tape[i] = 0
letters = "ABCDEF"
for step in range(12656374):
if i not in tape:
tape[i] = 0
if tape[i] == 0:
k = 0
else:
k = 4
if L[instr][k+2][-2:] == "1.":
tape[i] = 1
else:
tape[i] = 0
if L[instr][k+3][-3:] == "ht.":
i += 1
else:
i -= 1
letter = L[instr][k+4][-2]
instr = letters.index(letter)+1
checksum = 0
for i in tape:
if tape[i]:
checksum += 1
print(checksum)

Ran in 27 seconds

>defaultdict(lambda: 0)
int()?

You kept a near 200 point lead for a long time and only barely had to cash it out in the end
Way to take home the gold for the glory of anonymous posters

I just hardcoded it and it took too long. Got ranked 242 and I'm shocked this shit code worked on the first try
def AOC25(file):
state = 0
tape = [0]
x = 0
def extendtape(x):
while len(tape) >> 1 < abs(x):
index = 1+len(tape) >> 1
for _ in range(2): tape.insert(index, 0)
for i in range(12629077):
if state == 0 and tape[x] == 0:
tape[x] = 1
x += 1
state = 1
elif state == 0 and tape[x] == 1:
tape[x] = 0
x -= 1
state = 1
elif state == 1:
if tape[x] == 0:
x += 1
state += 1
elif tape[x] == 1:
x -= 1
elif state == 2:
if tape[x] == 0:
tape[x] = 1
x += 1
state += 1
elif tape[x] == 1:
tape[x] = 0
x -= 1
state = 0
elif state == 3:
if tape[x] == 0:
tape[x] = 1
x -= 1
state += 1
elif tape[x] == 1:
x -= 1
state = 5
elif state == 4:
if tape[x] == 0:
tape[x] = 1
x -= 1
state = 0
elif tape[x] == 1:
tape[x] = 0
x -= 1
state -= 1
elif state == 5:
if tape[x] == 0:
tape[x] = 1
x += 1
state = 0
elif tape[x] == 1:
x -= 1
state -= 1
extendtape(x)

yield sum(tape)

My first instinct was to make a parser, then when I pasted the input to a text file I realized it was only 12 rules for 6 states. I guess they wanted to give us a break on Christmas so we could get out early to go be with our
>families

>/ourguy/ did it
Your autism is an inspiration to us all.

/ourguy/ wins!!!
Sup Forums wins again!!!
Its a Christmas miracle!

Congratulations user!!
Here is your prize (pic related)

MERRY CHRISTMAS TOO ALL AND TO ALL GOOD NIGHT!!!
youtube.com/watch?v=wbdvo019mgM

based god. just shamed all of those smug pricks linking to their github thinking they'd be winners

Post pretty pictures to congratulate user

>tfw still on day 7 part 2
>tfw never figured out day 3 part 2
I will never not be a brainlet

literally a typing speed contest.

Congrats user #193354

Got rank 515 for part 1, might've done better if I didn't stumble specifying my states.

youtube.com/watch?v=3NuFVQk_CCs
To everyone
Be happy anons

we did it Sup Forumsuys, we saved christmas!!

How the fuck do people write it in under 5 minutes.