Advent of Code

[telstarbox]

I've solved a couple of the puzzles from last year using Excel (formulae not Visual Basic) but it's clearly not the best solution for most of them. I don't know any specific programming languages so would you recommend any particular one for having a go at this year's puzzles?

[Croft]

If all programming languages are new to you, I think the best choice would be the one you would most like to learn. Most are going to be languages that at least could be used to answer the AoC challenges, so really it's about what might motivate you to learn any one of them.

Some common candidates would be Python (probably the sweet spot between ease of learning and suitability for AoC-type questions), Javascript (or one of its variants such as Typescript) and Java. But there are plenty more to chose from (someone in the last couple of years set themselves the challenges of using a different language for every question - that's 50 over two years! But not something I would recommend unless you have a lot of time on your hands and feel the need to have programmed in 50 languages).

[SoreTween]

VBA is a perfectly decent programming language for tasks at this level, why not just use that as you have it available?  Most other languages will have a learning curve associated with the tools, excel VBA is about as simple as it gets in that respect. Plus excel formulae are well suited to some puzzles, use whatever works best for each and keep it all together in one file.  You'll soon start subliminally learning about code re-use too.

Aside: addictive innit.

[David Martin]

It has started off gently enough though the part twos are a bit more complex than typical from previous years. I am left thinking there must be a better/more efficient way to solve some of them.

[Ben T]

Day 1 part 2 looks like there might be a Dynamic Programming solution but I can't see exactly what it is at the moment.

[vorsprung]

Did day 1 and 2 with perl one liners.  Although the second part of day 2 was a bit long

Not sure if ICBA to carry on with this

[Croft]

Did day 1 and 2 with perl one liners.  Although the second part of day 2 was a bit long

Not sure if ICBA to carry on with this

You can join the YACF leaderboard with the code 48462-ea506236. And it does get quite addictive (and the puzzles more varied).

[Greenbank]

Caught up with day 1 and 2 now I'm back from a weekend away. Nice gentle start.

(click to show/hide)

The naive O(n^2) solution for day 2 part two is to just compare each possible pair of IDs and count how many characters are different and output if the strings only differ by one character, but that'd be boring...

There's a nice O(n) solution though.

(click to show/hide)

Add each ID minus its 1st character to an empty hash checking for a match, if there's a match than that's your answer.
Add each ID minus its 2nd character to an empty hash checking for a match, ...
...Repeat to the length of all of the IDs...

[vorsprung]

Jo,

I am anonymous user #241788  apparently

[Greenbank]

Jo left here a long time ago.

Forgot to say, now that it has started I can now legitimately wear my AoC t-shirt.

[Greenbank]

(click to show/hide)

Guessed I'd need to keep track of the individual patches for part b so hardly any changes required for the second part.

Waiting for the first tricky one...

[David Martin]

Is it just me or are they quite involved with no obvious 'simple algorithm'? Day 4 took me a while - not difficult, just involved.

(click to show/hide)

It seemed to be very time consuming with lots of iterating over data structures. I have a thought over how it might go better using something like numpy.

[Ben T]

Yes, not a difficult algorithm but like you say involved. https://github.com/bjtaylor1/AoC2018/blob/master/Day04/Program.cs (link contains spoiler). Didn't take long but I did use classes where I normally wouldn't have to bother.

[Greenbank]

Day 4 wasn't about a specific algorithm, it was just about using appropriate data structures for the job. The better choice of data structure the easier it would be to implement the solution.

That and...

(click to show/hide)

sorting the input up front, even a simple lexical sort on an array of input lines was enough

With some of the puzzles there's usually only one (high-level) algorithm that will work in a reasonable time frame, and certainly only one (high-level) algorithm that would work if the input was considerably larger (which would show up the inefficient algorithm choices).

There's a number of different ways that you could have approached day 4, all perfectly valid.

I guess it highlights the fact that it's important to know when to optimise something, or choose to correct algorithm, and when you can just get away with anything that works.

[Ben T]

(click to show/hide)

Initially stored the sequence in a string to do the removals, this took ~5 seconds for part 1.
Optimized by the fact that in .net a string is stored as one contigious block of memory whereas a StringBuilder isn't.
This takes it from 5 seconds to 1 second as it doesn't have to keep repeatedly allocating memory of the order of the size of the input.
Not sure if java or python do the same thing.

Part 2 takes 26 seconds as would be expected, but the simple insertion of AsParallel() reduces it to about 14/15 seconds.

https://github.com/bjtaylor1/AoC2018/blob/df318310a7039c8db55d3cf48e879447346dba0d/Day05/Program.cs

[Greenbank]

Ooh, if we're doing timings...

(click to show/hide)

Naive regex based solutions (in perl):-

5.1: 0.3s
5.2: 7.53s

On the same machine and implemented as a double linked list and minimising memory allocation (in C):-

5.1: 0.003s
5.2: 0.033s

All single threaded, no parallelism applied to either implementation.

[Ben T]

Hmm. Interesting. Code?
Only reason I'm curious is if single threaded, I would have expected 5.2 to take 26 times as long as 5.1. Your perl solution did, but C took only 11 times longer, so are you doing some sort of BFS/DFS type search?

[Greenbank]

There's an initial cost to parsing the input string which will mean part 2 won't take exactly 26 times as long as the first.

Code and comments:

(click to show/hide)

perl: http://www.greenbank.org/aoc/2018_day5_pl.txt (only does part 2 but easy to adapt to do part 1, just do the main loop once with a non-existent base like _ )

C: http://www.greenbank.org/aoc/2018_day5.c.txt

Doesn't use any form of searching, it does a linear scan along a double linked list, if it removes anything (either it's the base that needs removing or a pair like aA or Dd) then it moves back to the previous item in case that now matches the next item.

The orig pointers are there to rebuild the next/prev pointers for the next scan along the list for the next base.

[telstarbox]

For day 1 part 2 - do you need to use more than one loop of the input text? It's confusing me lots!

[Greenbank]

For day 1 part 2 - do you need to use more than one loop of the input text? It's confusing me lots!

"
Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.
"

[David Martin]

My code for day 5 is obviously inefficient (it does a lot of string allocation) in Python

(click to show/hide)

I read the input int a string, then scan it repeatedly removing pairs (abs(ord(string

• ) - ord(string([x+1])) == 32 is broadly the test used - appending positions that pass to a new string and skipping those that don't)

I might try building the data structure as a tree or a linked list, with iterative pruning as I go but I can't quite get my head around the process as I am fighting a wee cold at the moment.

[Pickled Onion]

(click to show/hide)

You don't need to keep going over the whole string, when you've done a removal you just need to back up one character, the string up to that point has already been scanned

(click to show/hide)

   while($i<$#data){
      $data[$i] ne $data[$i+1] && uc$data[$i] eq uc$data[$i+1]
         ? splice @data, $i--, 2
         : $i++;
   }

[Greenbank]

Day 6 was nicely different.

(click to show/hide)

Initial naive implementations:-

Part 1: 8.83s 3.85s with an obvious optimisation
Part 2: 5.34s 1.99s with different search/fill algorithm

Thinking about ways of making them faster...

[Ben T]

Day 6 is interesting, weirdly I found part 1 harder than part 2.

(click to show/hide)

I used 'fuzzy logic' for part 1.

Couldn't see a 'proper' way to eliminate ones whose areas were infinite.

I thought a convex hull algorithm was needed to eliminate ones whose areas were infinite, but it wouldn't, because if 'D' in the example was one square to the left, it would still be inside the hull, but anything to the left of it (and not up or down) is nearer to it than to any other location, ergo its area would be infinite.

I only summed up the areas inside the rectangular bounding box, but to eliminate any that were infinite, I simply drew a big circle round all the coordinates, and any coordinate that is the nearest to a point on that circle must have an infinite area. 

https://github.com/bjtaylor1/AoC2018/blob/master/Day06/Program.cs

[Greenbank]

(click to show/hide)

Couldn't see a 'proper' way to eliminate ones whose areas were infinite.
...
I only summed up the areas inside the rectangular bounding box, but to eliminate any that were infinite, I simply drew a big circle round all the coordinates, and any coordinate that is the nearest to a point on that circle must have an infinite area.
...

(click to show/hide)

You only have to consider points on a rectangular bounding box that cover the minimum/maximum co-ordinates in the dataset, not a bigger circle/box.

Looking at the example given:-

Code: [Select]

aaaaa.cccc
aAaaa.cccc
aaaddecccc
aadddeccCc
..dDdeeccc
bb.deEeecc
bBb.eeee..
bbb.eeefff
bbb.eeffff
bbb.ffffFf

If you take any point on the outside then the next furthest distant square must belong to the same area as it is only +1 on the manhattan distance, to get to it from any other square would require more than +1 on the manhattan distance, so it can never belong to any other area.

i.e. consider this portion of the left hand side:-

Code: [Select]

1a
2.
3b

1 can only ever belong to 'a'. 3 can only ever belong to 'b'.

By the same logic 2 must be '.' because nothing can uniquely get to it in a shorter distance if two things can get to the square to the right of it in the same manhattan distance. Since moving left is moving away from all points (as we're beyond the minimum x co-ordinate) then the manhattan distances can only increase each time.

So, any points on the rectangular bounding box that belong to a single area mean that area is infinite.