Clojurians Log v2

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

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

'Some, but not down the rabbit hole'

Discrete Voronoi? ¯\(ツ)/¯

looks like it!

Well, to really prove that the minimum box approach works, a proof is needed and that proof is not entirely trivial. The roll that Manhattan distance plays over Euclidian one is quite neat

do go on

I just made assumptions like the ape that I am.

I’d love a link or something w/ more info if you happen to have it!

I did go with assumptions to solve it first, and it worked. But to achieve a non heuristic solution I had to do some math, which I found fun

Well my original solution turned out to be the right one, but prove it wasn't completely trivial

Can u tell me what approach to solve day6 did u use?

uh, I would say, “brute force with loads of assumptions” 😄

let’s see, part 1 - make a bounding box sig bigger than the points (500x500), remove all ids on the edges, sum the remaining areas, and take the max

part 2 - assume a bounding box that encompasses all points is big enough, check every point in the box for inclusion in the “good zone”

What do you mean with "ids on the edge" ?

uh, I gave an id to every input point

But what does it mean for a coord to be "on the edge"

on the edge of the bounding box

like, points that comprise the edges of the bounding box

But do u mean points that r exactly on the edge, or the ones that r closer 2 it?

the ones exactly on the edge

Im sure there are cases where there are coordinates that are no on the edge that have infinite areas

how can that be?

Day 6: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_06.cljc

He tried to choose a box big enough that anything out that far would be infinite.

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

Super not proud of my six, but here it is: https://gitlab.com/randall.mason/advent-of-code/blob/master/src/advent_of_code_2018/day06.clj

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

My day 7: https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle07.clj#L64

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

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

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

hopefully later today

@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”

@erwinrooijakkers e.g.: https://github.com/borkdude/advent-of-cljc/blob/master/src/aoc/y2017/d02/mfikes.cljc#L20

My solution for Day 7 https://github.com/benfle/advent-of-code-2018/blob/master/day7.clj

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

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.

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.

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

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

I've got a similar situation

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

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

https://github.com/mattly/advent-2018/blob/master/clojure/resources/07.txt

@ihabunek input in PM

I'm fairly sure I have a bug

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

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

thanks

so i'm guessing you have a bug

ok cool

thanks

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

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

@borkdude I had 3 letters to begin with

ok, so alphabetically that is - right?

found my bug

@borkdude yes you try each in turn alphabetically

ok

boom, got it, thanks again

\o/

@borkdude let me check

I think I found my bug as well

what was it? 🙂

cool, then I won't give any hints 🙂

still figuring out, but I’m close…

got it right 😄

now part two… 😕

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

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

same, but too high

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

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

@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 😁

Thanks for the stream and the answers

My pleasure!

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

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?

on step 1 that is

sample data must definitely be missing edge case

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

I forgot one of them in the beginning

oh. Part one. I am sorry 😞

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

no problem

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?

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

Good luck 🍀

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

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

On CI:

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

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

code: https://github.com/borkdude/advent-of-cljc/blob/master/src/aoc/y2018/d07/borkdude.cljc

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

(mfikes start typing, there it comes…)

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

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

I got it only working by mimicking that every second

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

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

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

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

just add one in the return then 😛

@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…

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

Time for some blasphemy

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

MY EYES!

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

nice, you optimized your Clojure code

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

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

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

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

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

I know.

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.

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

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

https://www.reddit.com/r/adventofcode/comments/a43k6z/day_seven_part_two_example_confusion/

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.

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

and this solution is fast!

but also not that pretty 🙂

I’m not sure if today has a pretty solution

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

Day 7: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_07.cljc

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.

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

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

@gklijs I got 14 as well a couple of times

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.

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

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

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

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

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.

same here

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

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.

you mean an algorithm with a name?

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

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

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

which is ugly, but it works

Instead of just leaving you with a problem description.

yeah, you had to read very closely.

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.

which I did not do at first 🙂

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

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 🙂

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

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?

@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.

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.

oh ok

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.

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

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

https://en.wikipedia.org/wiki/Topological_sorting

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.

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'

This means that the work on E finishes at second 15

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

I sent this to Eric: https://twitter.com/mfikes/status/1071169374587899905

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.

https://github.com/orb/advent2018/blob/master/src/advent2018/day7.clj#L43

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.

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.

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

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

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

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

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.

I did this by removing he unblocked edges from the graph

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

and by doing so, A and F becoming visitable

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

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

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?

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

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

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

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