Advent of Code

[David Martin]

Array index munging today. With a bit of input parsing thrown in.

[Oaky]

There is some pretty rank coding on display there..

It is deliberately perverse,  this guy has form for it.  I believe it was the same person who posted a solution for one day of last years AoC using a Synacor challenge VM.

[David Martin]

I wasn't talking about the sheer brutality of the explicit regexs but some of the other code snippets that get posted.

[red marley]

One of the things I like about AoC is that it works with multiple levels of coding skill and experience and on multiple levels. I can use it with my first year computing students as well as get experienced computer science academic colleagues interested. Some solutions can be created with spreadsheets and even on paper, while others benefit from highly specialised languages. Inevitably there will be some pretty clumsy attempts being shared - but again, this is one of the rewarding educational aspects of the challenge, seeing how not to approach a problem as well as what works.

[Oaky]

I wasn't talking about the sheer brutality of the explicit regexs but some of the other code snippets that get posted.

Ahhh,  I understand now.

I saw one solution posted in which I could see a clear bug (that I knew to be a bug because I initially did the same myself, but it was smoked out of my code by the unit tests I'd written).  The author was fessing up to that bug (and another one) which individually would have got him the wrong answer, but coincidentally conspired to cancel out.

[David Martin]

Ah, definitely a step up. Part one done - straightforward once I remembered to

(click to show/hide)

strip the trailing newline

Part 2 is readily tractable but just need to think a little bit further.

[Pickled Onion]

My computer is busted, trying to solve them on a phone would be a challenge too far. I'll have to catch up at the weekend   

[red marley]

Day 9 (decompression)

(click to show/hide)

Initially I accumulated the processed string as I uncompressed it. This was largely for debugging and was fine for the first part. For the second just had to replace the string with a long* integer that kept track of the uncompressed length. Luckily for me, I had created a pure function to do the uncompressing for part 1 so it was easy to adapt to call recursively for part 2.

I suspect the bigger challenge would have been for Eric Wastl in generating the inputs for the challenge as it is very easy to create compressed sequences for part 2 that generate infinite length strings.

* had to be 64 bit as with my input at least, the resulting decompressed string was 10,780,403,063 characters long.

[David Martin]

Day 9 (decompression)

(click to show/hide)

Initially I accumulated the processed string as I uncompressed it. This was largely for debugging and was fine for the first part. For the second just had to replace the string with a long* integer that kept track of the uncompressed length. Luckily for me, I had created a pure function to do the uncompressing for part 1 so it was easy to adapt to call recursively for part 2.

I suspect the bigger challenge would have been for Eric Wastl in generating the inputs for the challenge as it is very easy to create compressed sequences for part 2 that generate infinite length strings.

* had to be 64 bit as with my input at least, the resulting decompressed string was 10,780,403,063 characters long.

Is that not part of the challenge (dealing with integer overflows)? i fail to see how an infinite length string could be produced from finite input with that decompression method.

it was a straightforward recursive function to tot up the lengths and only match each pattern once.

[tom_e]

My computer is busted, trying to solve them on a phone would be a challenge too far. I'll have to catch up at the weekend

  I made the mistake of starting one on the phone because it looked pretty easy.  I did succeed, but it was quite painful.

[red marley]

I fail to see how an infinite length string could be produced from finite input with that decompression method.

(click to show/hide)

An example of never completing:

(5x1)(5x1)ADVENT

will firstly consume the compression instruction (5x1) leading to the insertion of the next 5 characters which are also (5x1). So after the first decompression the string of remaining characters is exactly the same as the original string meaning the processing will never get to the end.

If you replace the above with

(5x2)(5x2)ADVENT

after each decompression, the remaining text to process will the same as the previous one but with an extra (5x2) at the start, so the string grows infinitely.

[David Martin]

I fail to see how an infinite length string could be produced from finite input with that decompression method.

(click to show/hide)

An example of never completing:

(5x1)(5x1)ADVENT

will firstly consume the compression instruction (5x1) leading to the insertion of the next 5 characters which also (5x1) so after the first decompression the string of remaining characters is exactly the same as the original string so the processing will never get to the end.

If you replace the above with

(5x2)(5x2)ADVENT

after each decompression, the remaining text to process will the same as the previous one but with an extra (5x2) at the start, so the string grows infinitely.

OK, I see where you are going with that but you are wrong. given that a compressed string must be formed from an uncompressed string, and given the uncompressed string is [A-Z]+ the compressed string given in your example will never occur. I admit that an invalid string can break the algorithm, but a simple check that all processing instructions are complete (ie contain N characters after the instruction where the instruction is (NxY)) should suffice.

[red marley]

I would agree if Eric Wastl was generating the potentially tens of thousands of compressed files used by this challenge by applying the compression algorithm to multi-gigabyte originals, that would be all you need to guarantee a 'good' compression sequence. But clearly, the scale of this means he will have been generating the compressed strings directly and algorithmically, and that was my point about his input generating challenge being a significant one.

[David Martin]

But all you need to do is generate a string of valid commands from other valid commands. it is straightforward. You don't need to start with the uncompressed file.

[red marley]

I'm probably digging myself into a hole here by failing to understand the elegance of your suggested approach to input generation, but :

(5x2)ADVENT generates a valid (finite) uncompressed sequence. And (5xn) is in principle a valid compression command, where n is any integer. But (5xn) applied to that valid sequence renders it invalid. What would be a simple way of detecting such invalid modifications (other than the trivial case of always inserting a non-compression sequence of at least 5 characters after a compression command)?

[David Martin]

You ensure that n is len(what follows the command) or greater.

So (5xn)ADVENT is fine but as (5xn)ADVENT is of length 10, the smallest thing that can be included is (10xn)(5xn)ADVENT. Anything less is invalid

So to generate the input you cna basically reverse the grammar definition


text := [Expansion]?[text][text]?

Expansion :=  (Zxlen{following text}) where Y is the length of the following [text] and Z >1

buildtext :
    text = null
    loop until break:
         text = text + random select:
             (random integer x length of)buildtext
             character in [A-Z]
            break
    return text

so text=buildtext will give you, for suitable random parameterisation, a valid compressed string.

• for given models of random

[red marley]

^---- Nice. (I think, but I've become distracted by the day 10 challenge)

[red marley]

Day 10 (bot dancing)

The challenges are getting more interesting, and finally varying a little more from the pattern matching that has dominated the first week or so. With the possible exception of the first day, I think the difficulty curve over time is better than last year as it feels more of a steady increase in effort.

As for today...

(click to show/hide)

I initially misinterpreted the challenge in assuming the instructions were issued serially, so wasted time not getting a workable answer.

Once I realised that you initialise all the bots with values or donation instructions then set them off to interact, this became more fun. It took me a while to work out, from the toy example, how the output registers related to the values held by bot 2 so wasn't sure how to provide the answer. When I finally realised that you don't use the output registers to answer part 1 at all, it became an easy task to query for the bot that held 61 and 17.

And because I had been mistakenly examining the output registers before I understood what part 1 required, the second part was trivial.

[David Martin]

(click to show/hide)

It is a simple(ish) graph traversal of the sort I like. I split off the values and built the graph first of all.
I then initialised it with the values and let it run. Each bot waits till it has two values before trying to compare and pass on.
(it would have helped avoid some frustration if I had not inadvertently switched the high and low bots on initialisation and was wondering why I couldn't get the answer)
Part 2 was likewise a slight tweak to get the answer.

[David Martin]

And a dotified version of the solution to today's

dotfile by David Martin, on Flickr

[Diver300]

Is the order of applications of the bot rules important?

I got the first part, once some of the chips end up at outputs, I've got 14 bots, each holding one chip, and nothing further happens.

Any suggestions?

[David Martin]

Yes, you have to give the bots the inputs and they only transfer when they have both chips to compare. The graph is acyclic.

(click to show/hide)

I built a simple class for the bot that included the rule for comparison and where the high and low values were. It had a method where it could receive a chip. WHne it received two chips it would compare them and pass them on to the relevant next step (bot or output).
Split the commands into bot and value ones, and runt he bot ones first to build up the network. Then feed the values in and see where they end up (the outputs).

[David Martin]

The first proper hard one today.

(click to show/hide)

It looks like a finite state machine with branch and bound to determine the routes but there are a lot of potential states.
I'm tempted to brute force tree walk through all valid moves, recording each state and the number of moves it took to get there.
There may be a better way as this is not an acyclic graph. Each move can be done in both directions and you may get to a state via multiple valid moves.
Still some thinking to do. That may be this afternoons challenge.

[David Martin]

There is a recursion depth issue. Still bruteforcing it. There may be a way to optimise the strategy but I haven't worked out how to do that yet. This is taking some time. maybe I should set a search order based on energy minimisation?

ETA: Part 1 done. Part 2 adds substantially and my approach may not be suitable. There has to be a smarter way of doing this but I don't see it.

As a measure of difficulty I should plot my leaderboard position against time. It might be quicker to do a binary search of the final answer, waiting a minute between each input than to calculate the answer using my 'crawl the whole net' approach.

ETA:
There is a smarter way.

(click to show/hide)

The problem is recursive in the same manner as towers of Hanoi or the classic Husbands and Wives. There are positions in H&W from which it is insoluble. The twist is having more than two positions and my brain cannot sort out more than that there is an algorithm behind it.

However, it still looks like a binary search on the correct answer is quicker than brute forcing it.

[David Martin]

Brute force mostly won the day. Got to a position that was a maximum of 6 off but wasn't sure if it was optimal. It wasn't. Iterated back through the odd numbers till I got the right one. There is a one then five then ten minute delay between answer submissions..