/aocg/ - Advent of Code 2018 General #24

I can't do 7.

>tfw the bar for brainlets gets higher each day

Attached: 1488372116910.jpg (645x968, 47K)

What part are you stuck on?

adventofcode.com/2018/leaderboard/private/view/368748?order=stars

I didn't consent to being datamined.

What? Are you telling that there will be real problems in the future? It's the first time I do AoC.

>more than half the Jow Forumsderboard has been FILTERED

The part where I read the wikipedia page for topological sorting and got even more filtered.

>For every 17 people who did the first problem, only ~2 of them have made it as far as the latest problem.

Attached: 1522867480147.jpg (3840x2400, 323K)

You shouldn't read such thing. You should go ahead and thunk about the problem.

What do you mean, "real problems"?

87, one more. Oh yeah!!!!!!!!!!!!!

Since now, we only have jokes.

Unlike C++, math is not a costless abstraction. Don't waste precious brain nodules trying to understand the problem from a higher perspective when it is perfectly soluble at the immediate level.

Oh, you're bragging.

You don't know, who I am, what I did, and the kind of problems I solve at work.

i'm a brainlet that got filtered day 7p2. still here to root for our user. i want to ask him what resources helped him the most? and how do i begin to be as good as him.

>i'm a brainlet that got filtered day 7p2.
What blocked you. Do you need help?

If you refuse to water your brain seeds and put healthy animal poop on them they will not grow.
For day 7 part 1 you just need to keep track of a few things.
First populate a dict with every letter in the alphabet as keys, then read through the dependency data line by line. Each time you find a step that depends on another step, populate your dict so that all letters have their dependencies in their values.
In your loop, you should start by populating a list of candidates for the next instruction step. Then simply check which instructions in that dict that have not been completed (track that however you want) And which are not already in the candidates list are added to the candidates list. Sort the candidates alphabetically so that the first element in the candidates list is the one that is completed this loop. You add it sequentially to the end of your final answer, but the important thing is that, since this dependency-less step is being completed, you need to remove any instance of it in your main dict's values for every key that depended on it. That way, when the loop starts again, it will populate some new candidates to the candidates list because their dependencies are all complete.

You almost certainly don't need all of this instruction and there are different methods, just pick and choose the parts you want.

for 7p2 i felt like i had to manage a lot of spaghetti and the bugs probably somewhere among my spaghetti.
i'm still gonna continue, i still also got messed up on part 2 from last night.

You shouldn't get so dramatic, user. People brag.

>for 7p2 i felt like i had to manage a lot of spaghetti
It's not a big problem, so get rid of your old code and restart from scratch with a good alg in mind, could be a good start. Just code your alg until the end.

wikipedia pages on math and science are not written to be understood. The information is too dense and the writing is far to complicated.
>a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
What the fuck does that even mean?

Here's my part1 solution in psudocode:
>generate a dictionary (associative array) where the keys are the instructions and the values are their dependencies
>>{ 'A': ['C'], 'B': ['A'], 'C': [ ], 'D': ['A'], 'E': ['B', 'D', 'F'], 'F': ['C'] }
>find all the steps with no dependencies
>put the list into alphabetical order
>>the first step in that list is the next one you have to do
>modify the dictionary so that the step you did is removed completely
>>remove its key and remove it from any dependency array
>restart the process with finding all the steps without dependencies

sorry senpai

You don't a clever algorithm for topological sort. The input is small enough you can just brute force it.
Basic idea is to loop through all the tasks A-Z, and for each one, if (1) it isn't done yet, and (2) all the tasks that have to happen before it (according to the input) are already done, then this is the task you're supposed to do in the current iteration. Do multiple iterations of this whole thing until all of the tasks are done.

For part 2 it's more complicated, but you can reuse the "find the task you're supposed to do next" part as a helper function.

I'm a little bit drunk.

>What the fuck does that even mean?
It's obvious, it means, that it's a morphism (fuck anglo-saxon and the stupid word homomorphism) from an ordered set to a totally ordered set. Something that preserve order.

fuck it, im going to slap a GDPR complaint on this shit site. brainlet uprising!!

Finally got around to day 7, was not that bad aside from using the wrong variable name in part 2 (was too tired to notice).
Tried today's with a recursive solution, it nearly but didn't work I think because variables were being clobbered.
Going to use a stack for it when I do it. I'm about to pass out from tiredness so someone else will have to FUCKpost the second the puzzle unlocks instead of me. Best of luck for the anons who are awake on time.

I joined the leaderboard.
And I'm reminded of what's there to dislike about the scoring. I don't have time for this until the European evening.
At least I can display my 16 stars there.

>First populate a dict with every letter in the alphabet as keys
Even better, populate the dict with all of the letters found in the input.

>I'm a little bit drunk.
Eh, don't worry about it. The post was substantive. I was being a jerk attacking your possible intent instead of discussing the content.

Careful with that, if you end up only populating the dict with keys that have dependencies as you would normally append, you'll end up missing your whole initial candidates list.

Fell for that one myself.

you can reuse 90% of your code of task1 for task2
just a worker int[5] needed and a for loop

That's why I said all the letters. As in parents and dependencies. That way you won't have extra keys and even if more keys than the A-Z are added, you will have them in your candidates list.

1.3 with the big one. You have a big margin user.

>you'll end up missing your whole initial candidates list
Happened to me first but then I did and made sure I got all letters mentioned, not just the one with dependencies

probably a common concept, but day7 made me realize that you can represent a sparse matrix with two hash tables. i feel like that's something that'll come in handy knowing.

day 2 ex 2
don't bully me for my slowness please, i'm learning perl6 with this for fun : - )
my @lines = "input".IO.lines>>.comb;

(@lines X @lines).hyper.map: -> @p {
my @out = ();
my @l1 = @p[0].cache;
my @l2 = @p[1].cache;
for ^@l1.elems {
@out.push( @l1[$_] eq @l2[$_] ?? @l2[$_] !! "#" );
}
if @out.Bag == 1 {say "found"; say [~] @out; exit}
}

When you often ask a question, a hash table can be very useful. In the case of a graph, what are the ancestors fo such node? What are the successor of such node? Try to spot such questions, and use a hash table when needed.

Eh, nvm. You can only need one hash table to represent a sparse matrix, of course. But you can use two to represent a sparse connection matrix.

MOM LOOK I'M FAMOUS

Attached: 1524337027994.jpg (680x535, 77K)

My brainlet self is about to start trying question 7 again.
I should be looking into priority queues, right?

Do you know how to schedule events?

I use facebook, mostly.

I don't know what to say.

At each steps, you have running tasks and a end time for those task. So the min of those end time is your next event, wheen you must update the state.

>I should be looking into priority queues, right?
I pajeeted out of this by sorting my queue's entries after each iteration of the main loop

I used an adjacency list for the graph itself, and implemented it as a dict of letters to sets of other letters. Also, my worker elves were represented by tuples in a list, with each tuple containing the letter being worked on and the current progress.

based

Is it true that State is a useless abstraction unless you're using the lens library?

i really feel proud of myself for getting this far

>Is it true that State is a useless abstraction
No.

are you RSSG?

no, i'm one of the anonymous users

tried to make my rust solution a little more rusty.

use std::str::FromStr;

struct Node {
metadata: Vec,
children: Vec,
}

impl Node {
fn from_iter(iter: &mut Iterator) -> Option {
let child_count = iter.next()?;
let meta_count = iter.next()?;

let children = (0..child_count)
.map(|_| Node::from_iter(iter))
.collect::()?;

let metadata: Vec = iter.take(meta_count).collect();

if metadata.len() == meta_count {
Some(Node { children, metadata })
} else {
None
}
}

fn part_1(&self) -> usize {
self.metadata.iter().sum::() + self.children.iter().map(Node::part_1).sum::()
}

fn part_2(&self) -> usize {
if self.children.is_empty() {
self.metadata.iter().sum()
} else {
self.children
.iter()
.enumerate()
.map(
|(i, c)| match self.metadata.iter().filter(|m| **m == i + 1).count() {
0 => 0,
count => count * c.part_2(),
},
)
.sum()
}
}
}

impl FromStr for Node {
type Err = &'static str;

fn from_str(s: &str) -> Result {
let mut iter = s
.split_whitespace()
.map(|s| s.parse())
.take_while(Result::is_ok)
.flatten();
Node::from_iter(&mut iter).ok_or("parse error")
}
}

fn main() {
let input = include_str!("../input").trim();
let root: Node = input.parse().unwrap();

println!("{}", root.part_1());
println!("{}", root.part_2());
}

Runs in ~5 ms on my shitty laptop. At first I tried to implement FromIterator for Option, but that's not possible because of the orphan rule :(

> The input is small enough you can just brute force it.

This is what makes these kind of lame sometimes. Some of these problems might actually require interesting algorithms with good enough inputs, but I'm not gonna waste time doing big brain coding when I can just do something easy

That's why we have bigboy.

>can't even print text without resorting to macros

the absolute state of Rust

>And please don't talk about continue/break, those two keywords are an abomination.
Oh I see, you're retarded.

If only you knew.

Attached: 4f5[1].png (455x455, 80K)

I hope that you'll be here at day 25, because I will.

Attached: maxresdefault.jpg (1280x720, 83K)

I feel really sad for this user, I hope they kept trying and figured it out!!

Attached: chrome_2018-12-08_18-17-43.png (728x272, 197K)

We're 90.

Me too. It's probably mostly just the picture, but it feels like leaving somebody behind.

Only jumped on board today
Bashed them all out over the course of a few hours, was a lotta fun
What languages are people going for?
Python seems like the obvious one cause you can just jump in and try things with no boilerplate needed but no doubt some of you enjoy making things as hard as possible for yourselves

time to catch a bit of sleep before the next puzzle hits at fucking 6AM

>What languages are people going for?
OCaml of course. That's what I used for prototyping. And when speed matters (ie. bigboys) C.

Using haskell which also requires basically no boilerplate

3 gazillion hours in gimp

Attached: advent of trees.png (999x1000, 1.2M)

Haskell because I want to play around with it and because its abstractions are really well suited for algorithm puzzles. I'll switch to python or sepples if I can't get a Haskell solution to run within a minute.

Out of interest, for day 5, the one with the polymers, how did you guys approach that?
My implementation was slow as fuck, I basically had a method which removed the first pair of 'reactive units' and I would call it repeatedly until the method didn't change the input anymore.
For part 2 I just looped over the letters, removed 'xX' from the input and then called part 1
It took like 5 mins to run :(

Runs original in ~7ms, small boy in ~3.5s, big boy in ~30s.
Could be faster but it's good enough for aoc
import Data.Tree
import Data.Attoparsec.Text
import qualified Data.Text.IO as T
import System.Environment

main :: IO ()
main = do
contents

use a stack

Create a stack. Iterate through each character in the polymer string: if the current character and the character at the top of the stack form a "reactive pair", pop the stack; otherwise, push the current character to it.

Learning Go. If you already know python then I think doing the whole thing in that would be a bit of a cop-out

>scan character
>is it the anti of the stack top?
>if yes, pop stack
>if no, push to stack
I implemented it with parsec so instead of a stack it's a recursive function, but recursion is a push/eval stack, so the idea is the same

That's fair enough, I want to focus on my approach to the problem rather than the actual language
Need to improve my algorithms knowledge desu

>can only figure out part 1 of each day
looks like I'm not saving christmas

Attached: hiro.jpg (450x350, 39K)

>but recursion is a push/eval stack
I've never considered this, neat

This year has had a smoother difficulty curve than last, so it's been nice for learning a new language - one or two new features a day and I'm now pretty comfortable with it as the problems get tricky

>use a stack
or the non-electron bloat way, 2 pointers into the string simulating a stack

you must be joking

most part 2s are easier than the distance puzzle

>2468 people with 1 star on day 7
Really? Did you guys find part 2 to be that hard?

part 2

Attached: out.png (1935x1935, 1.41M)

What "string"? You're traversing a character stream!

Are the inputs the same for everyone or does it change?

>part2 sum values in the nodes
shit graph

It took me a very long time to do it, yeah.

They change.

no*

goddammit

the one in /aoc/2018/inputs/day05.in
but ha bonus points if anyone solved it over https lol

Very pretty user what did you use to make that

I end up doing part 1 so badly that I would have to rewrite the entire thing over to get the answer to part 2 out of it.