Fork me on GitHub
#adventofcode
<
2018-12-07
>
potetm02:12:37

> You emerge from the chimney to find a circle of your peers. Hark! A spot has been left for you! You take a seat, and they inform you that they’re having a Christmas Eve Retrospective. > > Your mission is to write all of your mad, sad, and glad moments on postcards. You have three minutes. If you fail, Santa will send you back to the North Pole where you’ll spend the next year shoveling coal for the naughty boys and girls.

8
Average-user02:12:10

I find very satisfying when is possible/necessary to apply discrete mathematics to really solve a problem, so day 6 has been my favourite this year. Like there is always Project Euler but it is too much oriented in number theory or similar topics

fellshard02:12:32

'Some, but not down the rabbit hole'

fellshard02:12:54

Discrete Voronoi? ¯\(ツ)

potetm02:12:28

looks like it!

fellshard04:12:38

Holy crap. Note to self: type hint more. Those box warnings are gonna be super helpful, and the emacs integration helps narrow it right down

rymndhng08:12:14

whew, #7's part 2 was quite a grind, but ultimately fun to model scheduling in clojure!

pesterhazy08:12:07

@rymndhng agreed, this was fun. Would love to see your solution

pesterhazy08:12:46

I wonder if recursion via loop is the best way to approach this - I did end up with a lot of nested conditionals

borkdude10:12:34

I thought I could use tree-seq for day 7, but depth-first doesn’t work here… I haven’t solved it yet

borkdude10:12:43

hopefully later today

borkdude10:12:20

@erwinrooijakkers note that there are 2 other solutions in 2017 that also don’t work for the given input. These solution probably have overlooked a small edge case. You’re still welcome to submit the code, but maybe do a println in the test “TODO: fix for this input”

taylor14:12:54

these are starting to get too difficult to solve at 11pm CST 💤

✔️ 4
gklijs14:12:36

For me they're there 6 in the morning, I do get up early, bu then I first have to travel, work, travel, cook, except for at most 30 minutes in the morning, which is to short.

ihabunek14:12:16

6am for me too, not really meant for us european types. i like sleep too much to even attempt solving them at that ungodly hour.

borkdude14:12:11

I have four different letters that I can start with. If I choose the first one alphabetically, there is no answer.

borkdude14:12:24

Should I just try them all, or is there some logic to this?

mattly14:12:43

I've got a similar situation

mattly14:12:21

but then I'm not sure I don't have a bug

ihabunek14:12:51

if you give me your input, i can try my solution and tell you if it gives an answer

mattly15:12:52

I'm fairly sure I have a bug

borkdude15:12:40

I’m probably having a bug too, because none of the starting letters give an outcome, while my code works for the example

ihabunek15:12:39

@mattly @borkdude yeah, both of your inputs give me a solution similar to what I got.

ihabunek15:12:47

so i'm guessing you have a bug

benoit15:12:57

@borkdude I think the first letters should be handled the same way you handle the normal case.

borkdude15:12:57

@ihabunek do you only have one letter to begin with?

benoit15:12:12

@borkdude I had 3 letters to begin with

borkdude15:12:21

ok, so alphabetically that is - right?

mattly15:12:26

found my bug

benoit15:12:05

@borkdude yes you try each in turn alphabetically

mattly15:12:55

boom, got it, thanks again

borkdude15:12:52

I think I found my bug as well

helios15:12:14

what was it? 🙂

ihabunek15:12:19

cool, then I won't give any hints 🙂

borkdude15:12:52

still figuring out, but I’m close…

borkdude15:12:06

got it right 😄

borkdude15:12:14

now part two… 😕

borkdude17:12:05

LOL, my answer for part 2 was too low. So I tried +1… to test if I had a off by one error, and I did.. now I still need to fix it

😆 12
fellshard17:12:59

Had off by one here as well for quite a while.

potetm17:12:51

same, but too high

potetm17:12:20

The fix was to decrement my counter by 1 🙈 🙉 🙊

potetm17:12:02

https://www.twitch.tv/timpote — with shoutouts to the channel 🙂

4
meikemertsch19:12:05

Thanks for the stream and the answers

potetm19:12:50

My pleasure!

rymndhng18:12:26

@pesterhazy here's what I got for day 7: https://github.com/rymndhng/advent-of-clojure/blob/master/src/advent_2018/07.clj I modelled part 2 with a lazy sequence 😁

simple_smile 8
meikemertsch19:12:27

Hi folks! I am still pretty new to Clojure (and haven’t programmed any in … years.). My colleagues started AoC and I thought that’s perfect for doing some programming. Does anyone mind having a look at my code and giving me some pointers of what can be better / faster / more clear or any other way useful? Here’s a gist. I also included my test file… https://gist.github.com/MeikeMertsch/6a14074aa336f4d377c5d0fb6a01ca2b

adammiller19:12:07

finally getting around to this one today. I also am getting the correct answer on their sample data, but on real data it's not correct. Anyone else have some sample data and answer that I can use to test?

meikemertsch19:12:47

have you considered both the difference in time as well as the count of workers?

meikemertsch19:12:01

I forgot one of them in the beginning

meikemertsch19:12:05

oh. Part one. I am sorry 😞

adammiller19:12:05

this is on step 1 where i'm getting wrong answer (although it's fine for the test data)

meikemertsch19:12:24

Do you want to show your code? Then I can tell you if I spot where you’re making an assumption that isn’t right?

adammiller19:12:53

I don't mind but I think I may have found it....working on it now. Thanks though!

meikemertsch19:12:03

Good luck 🍀

adammiller19:12:16

on step 1 that is

adammiller19:12:45

sample data must definitely be missing edge case

borkdude19:12:50

Testing aoc.y2018.d07.borkdude
part-2 took 56.77 msecs
part-1 took 2.43 msecs

🚀 8
borkdude19:12:00

Testing aoc.y2018.d07.borkdude
part-2 took 45.78 msecs
part-1 took 1.70 msecs

4
borkdude19:12:27

On CI:

Testing aoc.y2018.d07.borkdude
part-2 took 25.26 msecs
part-1 took 1.25 msecs

borkdude19:12:45

This wasn’t an easy one for me… lots of println

borkdude19:12:46

I wouldn’t be surprised if there was a very elegant short solution to this

borkdude20:12:41

(mfikes start typing, there it comes…)

mfikes20:12:49

Im getting off-by one as well, wondering if AoC itself has a bug.

borkdude20:12:18

it’s a bit finicky to get the loop exactly like in the example page

borkdude20:12:39

I got it only working by mimicking that every second

gklijs20:12:30

I'm just kind of done, also have the of by one. It's kind of one the example page itself. Somehow you need one second without anybody doing anything

benoit20:12:30

Part 2 was challenging for me too. Which is why I broke down the algorithm into little step functions.

benoit20:12:15

@gklijs I think you're right. I also used the fact that all workers were idle for the definition of done.

taylor20:12:25

can't tell if I'm getting older & dumber or if the difficulty ramp is steeper this year

gklijs20:12:44

just add one in the return then 😛

borkdude20:12:03

@taylor somehow I managed to do AoC every day last year, but I wasn’t sure if I was going to do that this year…

taylor20:12:59

yeah, at some point the problems (at least to me) start becoming complex in a... non-gratifying way. Last year it was the last few days

gklijs20:12:29

Time for some blasphemy

gklijs20:12:52

Main part of the java solution

private static Integer go(final Map<Character, Set<Character>> graph, final int workers, final int additionalSeconds) {
        int workersWorking = 0;
        List<Character> done = new ArrayList<>();
        Map<Character, Integer> atWork = new HashMap<>();
        int timeSpend = 0;
        while(! graph.isEmpty()){
            Character nextTask = nextTask(graph, done);
            while(nextTask != null && workersWorking <= workers){
                workersWorking++;
                atWork.put(nextTask, nextTask - 64 + additionalSeconds);
                graph.remove(nextTask);
                nextTask = nextTask(graph, done);
            }
            int progresTimeBy = atWork.values().stream().reduce(Integer.MAX_VALUE, (o,n) -> n < o ? n : o);
            timeSpend+= progresTimeBy;
            List<Character> justCompleted = new ArrayList<>();
            for(Map.Entry<Character, Integer> entry : atWork.entrySet()){
                if(entry.getValue() == progresTimeBy){
                    justCompleted.add(entry.getKey());
                }else{
                    entry.setValue(entry.getValue() - progresTimeBy);
                }
            }
            for(Character complete : justCompleted){
                atWork.remove(complete);
                done.add(complete);
                workersWorking--;
            }
        }
        return timeSpend + 1;
    }

taylor20:12:06

MY EYES!

😉 4
meikemertsch20:12:57

What are those dots in…. wait… that’s Java 😮 😱

borkdude20:12:26

nice, you optimized your Clojure code

pesterhazy23:12:07

Those curly braces take a while getting used to but after while you stop seeing them

borkdude20:12:49

@taylor yeah, last year there were some fun insight, like https://en.wikipedia.org/wiki/Ulam_spiral

borkdude20:12:05

and on another day bhauman had some very nice solution with tree-seq, I still remember that one

ClashTheBunny20:12:27

It would be really nice if I didn't have to sign up for a bunch of different accounts to get more test data...

borkdude20:12:25

@clashthebunny the creator of AoC was a bit worried about me doing that: https://github.com/borkdude/advent-of-cljc/issues/6

gklijs20:12:30

If you know the value from the cookie you can get their data

ClashTheBunny20:12:19

I just wish there were other options, like give me 5 test cases generated the same way as you do the normal ones that aren't actually for credit.

gklijs20:12:33

It's worse, the example doesn't match with the actual value needed

borkdude20:12:23

usually if there are problems, look at https://www.reddit.com/r/adventofcode/ to verify if it’s a real one

borkdude20:12:43

Message from the global leaderboard: > Because of a bug in the day 6 puzzle that made it unsolvable for some users until about two hours after unlock, day 6 is worth no points on the global leaderboard.

borkdude20:12:55

oh yes, str/join can be called without a sep. so I don’t have to do (apply str coll) which I’m very used to. https://github.com/borkdude/advent-of-cljc/blob/master/src/aoc/y2018/d07/iamdrowsy.cljc#L36

borkdude20:12:17

and this solution is fast!

drowsy20:12:30

but also not that pretty 🙂

borkdude20:12:01

I’m not sure if today has a pretty solution

adammiller20:12:48

step 1 pretty small simple....step 2 i'm still working on so I don't know yet!

adammiller21:12:49

although i had problem with step 1 where my solution worked great for their test data but not the real one. Had to create some of my own examples to realize my issue.

taylor21:12:59

same, I struggled with a bad approach for two hours b/c it passed on the simple example

gklijs21:12:45

In that case I start to doubt my solution.. I get 14 on the example, but correct answer on the actual one, but a co-worker has the 'correct' answer in both cases

borkdude21:12:43

@gklijs I got 14 as well a couple of times

norman21:12:07

I didn’t have any major non-obvious bugs, but I did make a false start. My first pass through, I traversed the graph from leafs to head. Choosing the most expensive node that didn’t depend on anything not yet traversed.

Ben Grabow22:12:11

@norman @adammiller Would either of you mind explaining how the graph-based solution works, or sharing your solutions? I know intuitively I should be able to use the graph to find the unblocked tasks at each step but I can't wrap my mind around the details.

norman22:12:49

part2 is not very clean, and I think now I even see a a bug, but part 1 is a relatively straightforward traversal using loop. I’ll step through it here.

norman22:12:13

I represented the graph exactly like a the input. I have a vector of edges like [“C” “A”] which means there is an edge from C to A.

norman22:12:05

A very simple approach is to maintain a list of nodes you’ve visited and a list of nodes you haven’t visited

norman22:12:07

Then have a function that picks an unvisited node that is reachable and visit it. (move it from the unvisited list to the visited list) You repeat until you are done

norman22:12:11

In my solution here, I maintain the graph, the nodes list (everything I can visit) and the visited list (in order)

norman22:12:58

The function next-work does the job of selecting the next node I should visit (the lowest of all the ones I can visit).

Ben Grabow22:12:06

I think what is tripping me up is how to find the newly unblocked nodes by traversing the dep graph from a newly completed node. Right now I'm doing a bunch of filtering over the entire list of nodes.

norman22:12:43

I did this by removing he unblocked edges from the graph

☝️ 4
norman22:12:31

So if I visit “C” , I remove [“C” “A”] and [“C” “F”] from the graph

norman22:12:56

and by doing so, A and F becoming visitable

norman22:12:25

In removing the edges like this I only have to ask for any node N if there as an edge [? N].

norman22:12:54

If you don’t remove the edges, you’d jave to ask if there is an edge [? N] where ? is not visited

Ben Grabow22:12:43

It seems like I need two graphs, one of X -blocks-> Y and one of Y -is-blocked-by-> X. I follow the first graph to find the potentially unblocked nodes when a node is completed, and I use (and modify) the second graph to figure out if a potentially unblocked node is actually unblocked. Without those I think I need to do some set-based or iteration-based queries along the way. Does that sound right?

norman23:12:53

You could invert the graph, but there’s really no need

norman23:12:34

If there is a edge [“X” “Y”], which means “X” before “Y”, if you’ve visited “X” then you can disregard the edge. There’s nothing more to check

Ben Grabow23:12:09

Makes sense. Thanks for the explanation, it helped a lot!

norman21:12:36

This produced an equivalent traversal for the sample input, but not the test input

norman21:12:20

Changing the traversal required only changing two words, so thankfully my poor decision didn’t cost much

adammiller21:12:10

did the same exact thing, and yes it was pretty simple to switch from depth to head traversal.

borkdude21:12:32

Testing aoc.y2018.d07.borkdude
part-2 took 25.33 msecs
part-1 took 1.19 msecs

Testing aoc.y2018.d07.iamdrowsy
part-2 took 11.15 msecs
part-1 took 1.73 msecs

Testing aoc.y2018.d07.mfikes
part-2 took 21.22 msecs
part-1 took 39.40 msecs

mfikes21:12:18

FWIW my part-1 was initially faster, but since perf was good enough, I made part-1 be based on running part-2 in 2nd gear.

borkdude21:12:54

yeah, I liked your refactor. I was tempted to do the same

borkdude21:12:07

but I chose to move the common things into a delay instead

borkdude21:12:28

which is ugly, but it works

mfikes21:12:44

I had some false starts trying to sort first and then write a stable topological sort. I finally made progress when I carefully read the sample solution sequence and essentially wrote an imitation of that description.

mfikes21:12:03

In other words, that bulleted list under the graph is essentially an algorithm.

borkdude21:12:38

you mean an algorithm with a name?

mfikes21:12:07

Nah, I just mean: They are telling you one way to actually solve the problem.

mfikes21:12:35

Instead of just leaving you with a problem description.

borkdude21:12:18

yeah, you had to read very closely.

taylor21:12:50

which I did not do at first 🙂

mfikes21:12:44

Yeah, I didn't read that part initially (it is arguably not essential), and doggedly pursued my own path. When I saw the word "available" in that description, that did the trick for me.

mfikes21:12:43

Perhaps many readers stop right at the sentence "If more than one step is ready, choose the step which is first alphabetically." (Recognizing that it is a partial order that it turned into a total order by that constraint.)

4
potetm00:12:41

(sorted-set) helps a little here, I think

4
Ben Grabow00:12:04

sorted-set is also useful in part 2 for keeping track of the in-progress tasks, sorted by time of completion.

gklijs01:12:01

I can't quickly check for myself right now, but if you add something to a 'sorted-set' it might be added out of place? The documentation isn't clear, in Java it's a specific type of set which does keep order.

Ben Grabow02:12:47

(conj (conj (conj (sorted-set) 1) 2) 0) => #{0 1 2}

Ben Grabow02:12:40

Sorry, that's terribly formatted.

(-> (sorted-set)
    (conj 1)
    (conj 2)
    (conj 0)) => #{0 1 2}

potetm02:12:17

@gklijs I’m assuming it’s always natural sorting by default.

potetm02:12:32

(same as the java set)

potetm02:12:21

So letters will stay in alphabetic order

gklijs05:12:02

just tries in the repl (def test-set (sorted-set "d" "c" "r" "m" "a")) gives #{"a" "c" "d" "m" "r"} and (conj "n" test-set) evaluates as #{"a" "c" "d" "m" "n" "r"}

gklijs05:12:11

so it works

mfikes21:12:33

We need to get Wastl to add {:year 2018} to that little "year clicker" in the upper left of the main part of the page 🙂

👌 4
borkdude21:12:48

I wonder how much fun Eric Wastl had by creating this. Oh, do these two things in one iteration sometimes so people get an off by one error probably

Ben Grabow22:12:35

Interesting that on my data set and @borkdude’s data set I never had more than 5 tasks ready at a time, so I never ran out of workers. I engineered my solution (incorrectly I think) to handle a backlog of ready tasks but it never came into use. I wonder if this is true for all data sets?

benoit22:12:15

@ben.grabow I think you were right to do it this way. There was no way to know this from the description of the problem.

Ben Grabow22:12:04

I say "incorrectly" because I think my implementation is wrong, not because it's unnecessary. I am taking items out of the backlog in the order they were unblocked, when I should be taking out in alphabetical order at the time a worker is available.

Ben Grabow22:12:11

@norman @adammiller Would either of you mind explaining how the graph-based solution works, or sharing your solutions? I know intuitively I should be able to use the graph to find the unblocked tasks at each step but I can't wrap my mind around the details.

adammiller22:12:52

I only did that in the first part. Haven't done the 2nd part yet, although i was trying a similar solution but no luck as of yet.

fellshard22:12:43

The visual chart they give for part 2 basically tells how to interpret it, I think

fellshard22:12:06

Each letter on each row represents a full second starting at that number that is dedicated to that work

fellshard22:12:30

So the first row says 'starting at time 0, C is being worked on for one second, meaning that work on C will continue until at least the 1-second mark; it fills that entire first second.

fellshard22:12:06

Extend that to the penultimate row, where the last piece of work is being done: 'starting at time 14, E is being worked on for one second'

fellshard22:12:28

This means that the work on E finishes at second 15

fellshard22:12:12

Being consistent in how you frame each step in terms of the overall time is a bit tricky, for sure

mfikes22:12:18

👍 36
clj 24
metal 4
Ben Grabow22:12:07

Later tonight I'm going to take another stab at d6p2. I think it can be wildly efficient. If my reasoning is correct, then the "total manhattan distance" map has a consistent x-profile at every y-value, and a consistent y-profile at every x-value. To get the solution you compute one x-profile, one y-profile, then you can use those two profile to compute the rest of the "total manhattan distance" map without looking up the points at all. I feel like this would be instantly obvious when looking at a visual representation of the answer.

Ben Grabow00:12:31

Nifty, it worked. Brought the run time down from 30 secs for my naive brute force solution to 100 msecs for the efficient solution. I think there's room for improvement still, but it's super satisfying to find the efficient solution hidden in the rubble.

👌 4
fellshard00:12:13

It makes sense. The manhattan distance function would just look like a 3-d inverted pyramid centered on that point (e.g. \/ ), and the sum of distances is just gonna be the sum of those functions, which in turn are just the sums of the 2-d cross-sections