Advent of Code 2017 - Any interest for a CodeRanch leaderboard?

[Liutauras Vilda]

Day 5 both parts done. Racket yet again. There are languages you work with, and there are languages you love - racket is the latter.

[Tim Cooke]

I too am up to date, just got Day 5 done on my lunch break. I'm keeping going with Erlang and I'm really enjoying the language. Perhaps for some future puzzles I will be able to make use of the Actor model and make use of more than the one CPU core I've been overusing so far.

[Stephan van Hulst]

I just got started and finished day 3. I'm using Java 9. Here's my solution: https://github.com/Nibsi/Advent-of-Code/tree/master/src/aoc/y17/d3

I might have over-engineered it a little, using 9 classes, but I like it when my code reads fluently.

[Liutauras Vilda]

Stephan, obviously you have putted a lot effort. That code looks neat and with well thought. I need to analyse it to understand how all its parts work. It is very interesting to see different angles to tackle problem.

[Stephan van Hulst]

I didn't write any comments, but I can give a quick explanation here. My model is a two dimensional matrix that can grow in both positive and negative directions. A state machine known as a "turtle" starts at cell (0,0), moves forward (towards the right), rotates counter-clockwise, moves forward again, and then rotates counter-clockwise again. This makes it move in a semi-circle. It then increments its speed (the number of cells it moves when moving forward), and repeats the process to visit the matrix in an outwardly spiraling motion. The turtle can be given an operation that it performs when it visits a cell, and it will fire an event when it uses the operation to update the value of a cell.

For the second problem, the operation to compute the new value of a cell is based on the adjacent cells. The listener simply updates a variable that keeps track of the last value that was computed. When this value is greater than the problem input, the turtle stops moving and it outputs the last computed value.

[Stephan van Hulst]

I simplified the Turtle somewhat, so my previous explanation is not completely accurate anymore.

[Tim Cooke]

Your solution Stephan is similar in principle to mine. Although mine is horribly inefficient as it takes about 20 minutes to complete. My colleague has since informed me there is a math based solution and suggested I Google "spiral matrix". I expect that is much faster to compute.

[Liutauras Vilda]

Thanks for explanation Stephan.

Tim Cooke wrote:Although mine is horribly inefficient as it takes about 20 minutes to complete.

Maybe from now on let's share execution time, it is yet another interesting figure we can track.

For me all the solutions ran and gave an answer in a blink of an eye (well, with an exception of today's second part, it took about 2-3 minutes, but there were nearly 30_000_000 steps to calculate/exit). And racket is considered to be a slow language.

For the Day 3 part 2 (same as for part 1) I simply used to track and maintain current spiral's circle and previous circle, that means at most were dealing with 2 datasets were each from other were differ in 8 elements - so everything ran super fast as these are fairly small in amount of elements.

[Tim Cooke]

Likewise, my solution to Day 5 Part 2 took a number of minutes to conclude. Erlang is not for fast number crunching.

[Piet Souris]

Hmm... the counting system is now working much to my disadvantage! So be it.

For day 3 I imagined the matrix to be covering the x-y plane, with integer coordinates. So, cell 1-> [0,0], cell 2 -> [1,0],...cell 5 -> [-1, 1], ...,  cell 25 -> [2, -2] ad infinitum. For these coordinates I simply used the plain old Point.
Then I devised two functions, Point getCoordinates(int cellnr) and int getCellNumber[Point p). The second one was a bit trickier than I expected. But having these two functions made part 1 a triviality and part 2 (with a function 'getNeighbors') pretty simple.

[Liutauras Vilda]

Piet Souris wrote:Hmm... the counting system is now working much to my disadvantage!

I too think there is someting not quite right. I was quite surprised I jumped over you even with one star less than you, while day or two ago you were far ahead me. So something is out of sync in my opinion.

[Piet Souris]

Well, "I will be back" in the weekend!    

[Stephan van Hulst]

All my solutions finish instantaneously. Here's my solution for day 5: https://github.com/Nibsi/Advent-of-Code/blob/master/src/aoc/y17/d5/Execution.java

[Tim Cooke]

I'm leading the CodeRanch folks on the leaderboard.... for now.

Day 6 was a whole lot of array manipulation which proved tricky enough as Erlang doesn't really do random access on arrays and definitely not mutability on arrays. For example, setting to zero element at index idx of array nums:

Most languages:nums[idx] = 0;
Erlang:NewNums = lists:sublist(Nums, Idx - 1) ++ [0] ++ lists:nthtail(Idx, Nums).

[Stephan van Hulst]

https://github.com/Nibsi/Advent-of-Code/blob/master/src/main/java/nl/nibsi/aoc/y17/d6/MemoryDistribution.java

[Stephan van Hulst]

I guess to reach the top of the leaderboard I have to get up at 6 AM XD

[Liutauras Vilda]

I'm up-to-date too. It was slightly more difficult than it looked from the first glance, even though the "chef-d'oeuvre" is just 27 lines. #Racket #Recursion #List_Processing

[Tim Cooke]

My brain is having a lot of bother with Day 7 Part 2. I just can't fix a solution together. Perhaps I'll fuel up on dinner and try again later.

How are you guys finding it?

[Stephan van Hulst]

More difficult than expected. There were some little pitfalls in calculating the final value. In broad strokes, this is what I did:

1) Build a tree structure out of the input.
2) Map the tree to an analogous tree containing cumulative weights for each program.
3) Find an unbalanced program by comparing each child of the root with their siblings by cumulative weight.
4) Repeat step 3 recursively for the unbalanced program instead of the root, until you find an unbalanced program that doesn't have unbalanced children.
5) Get the difference in weight between that program and one of its siblings.
6) Add the difference in weight to the program's original weight. This is the final answer.

[Liutauras Vilda]

A bit stuck, created mess, now deleted everything and going to pool for a swim to relax and will start over.

Most hard finding to populate data with racket in right data structures.

I hope the logical part will be easier.

At the moment at least thinking that logical part should be decent enough once able to identify node has childs and be able to calculate them. If their childs have childs, calculate them too. Results separate by few main trees and see which is unbalanced first.

But will see once there at that point.

[Liutauras Vilda]

I nailed it.

(define (sum-tree t)
  (cond [(is-leaf? t) (get-weight-of t)]
        [else (+ (get-weight-of t)
                 (apply + (map (λ (e) (sum-tree e)) (get-children-of t))))]))

(define (find-unbalanced-node-in t)
  (let ([weights (map (λ (e) (sum-tree e)) (get-children-of t))])
    (cond [(apply = weights) (cons t (get-weight-of t))]
          [else (find-unbalanced-node-in (list-ref (get-children-of t) (get-unbalanced-index weights 0)))])))

That's the full logic of calculating sum/weight of the given tree and traversing further, but this time unbalanced tree, over and over, until offending node is found.

I learned from this exercise a lot - i.e. how to deal with racket hash tables.
Here's how I populate hash tables from the passed (get-elements input) function. I do some data cleaning first, i.e.: removing commas from children names, then converting i.e. (4) to actual number so would be easier to use when populating hash table. That's concise!:

(define weights (make-hash))
(define children (make-hash))
(for-each (λ (e) (hash-set! weights (first e) (second e))) (get-elements input))
(for-each (λ (e) (hash-set! children (first e) (drop e 3))) (filter (λ (e) (> (length e) 2)) (get-elements input)))

And the rest are just methods such as: get-weight-of, get-children-of from the hash tables above and use in an initially showed function.
Until this exercise I didn't use much functional programming techniques, but this puzzle proved them to be very handy.

[Stephan van Hulst]

Looks great Liutauras!

I have to admit that my solution turned into a monstrosity over time. I wrote a lot of reusable generic data structures. I think I'll rewrite it to tailor it to just this exact problem and then I'll commit it to my repository. Later today I'll look at the new challenge.

[Stephan van Hulst]

Day 8 is up: https://github.com/Nibsi/Advent-of-Code/tree/master/src/main/java/nl/nibsi/aoc/y17/d8

This one was quite easy.

[Liutauras Vilda]

Looks great

While my yesterday's solution to second part was the most elegant of mine, today's is most crap, which don't want to look at even for a second anymore. I might will rewrite it, though. I need to learn how objects in racket work - that seem to be the paradigm (OO) was handy in this exercise.

Anyway, solved both parts several hours ago too.

Tim, I'm not happy about the guy who's leading the board (however, wish him lovely coming Merry Christmas, I believe he is a good guy in his heart) - clearly the timezone works better for him. I woke up 7 AM, and out of curiosity went to have a look what this day gave us - and he (and one or two more) had it solved already - that's a JokeBoard, not a LeaderBoard anymore.

I'm serious! Of course I'm not serious, trust me

[Stephan van Hulst]

For me it was the other way around. The code I wrote for yesterday's puzzle started out elegant, but became a sloppy mess because I was running late in meeting some friends for an evening of music and drinks. I didn't even commit it because it looks so gross XD

[Liutauras Vilda]

Hi,

Day 9 Problem 1. It looks straight forward to be honest. Implemented with stack. Since racket doesn't have stack implementation, I implemented it myself as it looks to me most straight forward way to go with this task, so - for the given tests in problem description, my current algorithm passes all tests, however, on real input my stack implementation throws an error as trying to pop closing "}" when has no open "{" in stack.

Could somebody please do me a favor and check on your algoritm if given to me data goes through and gives some answer to you. Of course please don't tell answer, just tell please that data goes through and the answer doesn't end with **69. Big thanks.

Input data attached.

[Liutauras Vilda]

Found silly bug, please ignore my previous post.

[Liutauras Vilda]

Up-to-date.

Started very late today, so bunch of people had solved it already.

Did some shopping, at work we are able (voluntarily) to take some hanging cards from the Christmas tree with specified ages either of girls or boys so we could buy some presents for those often forgotten and in with less capabilities families, so took two cards (11 yrs girl and 9 yrs boy), and the weather to be honest wasn't that bad, so also went to the food market in London's South Bank which is outside and enjoyed some polish hot-dog - healthy stuff, you know..

What learned today, that Racket doesn't have stack implementation, that's one, but you can write your own very quick using lists, so I did, and second, it has RackUnit library, which is close to JUnit, cool stuff.

[Piet Souris]

Up-to-date.

If anyone is interested: https://github.com/PietSnot/AdventOfCode2017/tree/master/src/adventofcode2017

No particular problems, exercise 7 was more tedious than difficult.

[Stephan van Hulst]

I must ask Piet, why is half your code in Dutch and half in English?

[Piet Souris]

No particular reason, but I do get fed up sometimes from English, thinking "why the heck am I using English terms?". If I write programs for myself the names I choose are mostly Dutch, unless when some non Dutch speaking person must see the code. In this case I didn't think many would watch my code, and then this mix slips in automatically.

[Liutauras Vilda]

Just sat down by today's part II. I guess I'm going to stuck on this for a while. It seems it will take some time to understand what is being asked by researching its separate pieces.

[Liutauras Vilda]

Day 10 both parts done, part 1, part 2.

Second part looked very scary at first, but once read couple of times at a slow pace and took small steps, all went better than I expected.

[Stephan van Hulst]

In comparison to the other days so far, the second part of yesterday's puzzle went into a much more different path than the first part.

Overall I found yesterday's puzzle disappointing because it almost quite literally stated what to do.

I fell into two traps though. First, I forgot that if you use a start and an end index to select a range in a circular buffer, you can't differentiate between zero elements and all elements. Secondly, when converting a byte to a hexadecimal string, I forgot to pad with leading zeros. That second one confused me for a while because my algorithm worked fine for all the test cases.

[Tim Cooke]

I had a weekend away from the computer so playing catch up here. Just done Day 8 puzzles this morning. Gave up on Day 7 Part 2 for now, I'll hopefully get back to it.

[Stephan van Hulst]

I solved part two of today's problem in quadratic time by recalculating the distance from the origin to the current location, for each step in the input. I could have made the algorithm run in linear time, but I preferred the intuitiveness of my initial code.

https://github.com/Nibsi/Advent-of-Code/tree/master/src/main/java/nl/nibsi/aoc/y17/d11

[Liutauras Vilda]

Same here. For the simplicity recalculating distance after the each further made step from the starting position up to that step. Mine solutions is rather primitive, might even boring.

[Piet Souris]

Yesterday was easy (10), though a bit tedious, today (11) was very easy. I devised a coordinate system for the hexagons, and a translation map for the six possible moves. Then applying a reduce, starting from (0,0). Well, that was the plan, but somehow the compiler could not infer one of the types in this reduce. Don't know why not. But an old fashioned for-loop did the trick.

[Stephan van Hulst]

Can you show the code for your reduction that didn't work? Maybe I can give some pointers.

I'm actually a little bit disappointed that most of the problems aren't prohibitively expensive to crack if your solution isn't within some time complexity class. On the other hand, I'm also aware that these puzzles need to be fun for novice programmers.

[Piet Souris]

hi Stephan,

thanks for the offer, but I just figured it out. I'll explain what I did wrong, I think it might be illustrative to others. Here goes:

it is about exercise 11. As said, I devised a simple coordinate system for the hexagons. Then I have a map called 'translations', with key the six possible strings "n", "ne", et cetera, and value the translations that go with the keys (in the form of Points) and finally a List<String> called moves, that is just the input file.

What I planned to do was a reduce:

Point point = new Point(0, 0);
Point targetPoint = moves.stream()
    .reduce(point, (Point p, String s) -> {
            Point t = translations.get(s); 
            p.translate(t.x, t.y);
            return p;
        }
    )
;

What I just discovered was that I am using the two-parameter version of reduce. That version demands a BinaryOperator in stead of a BiFunction (here: my (Point p, String s) -> ...).
But I could not "make chocolate" from the error report.
I should have used the three-parameterversion instead, although it is unclear what that third parameter should be in my case.
Even simpler: I could have done:

Point targetPoint = moves.stream()
    .map(s -> translations.get(s))
    .reduce(point, (p, q) -> new Point(p.x + q.x, p.y +  q.y))  // or: (p, q) -> {p.translate(q.x, q.y); return p;}
;

The exercises have been quite easy (apart from exercise 3), but that is in my case a good thing. Having to solve the exercise in the evening is doable sofar. If we were given real braintwisters, then it is impossible for many to keep up with the tempo. I guess if you want more difficult problems, try project Euler and the like. There you have no time pressure, only sometimes the feeling that some problem is unsolvable for a normal being...