Advent of Code

[Davef]

I did day18 part 1 with no library calls and minimal c with recursion

(click to show/hide)

static __int64 eval(const char *& s)
{
__int64 ret=0,op='+',n=0;

for (;*s; s++)
{
if (*s>='0'&&*s<='9') n=10*n+*s-'0';     // build up integer
else if ((*s=='*')||(*s=='+')) op = *s;  // save the op
else if (*s=='(' || (s[-1]>='0'&&s[-1]<='9')|| (*s==')') )
{
if (*s=='(') { s++; n = eval(s); s++; }  // recurse for brackets
ret += (op=='+')*n;    // do +
ret *= op=='*'?n:1;    // *
n = 0;
}

if (*s==')') break;
}

return ret;
}

Part 2 I went a bit wild and used a c++ string class. Feeling a bit dirty.

(click to show/hide)

// find matching bracket
int matching(const char *p)
{
int c = 0;
for (int i = 0; p; i++)
{
if (p=='(') c++;
if (p==')') { c--; if (!c) return i; }
}

return -1;
}

static __int64 eval2(CString s)
{
int n = s.Find('(');
if (n>=0)
{
int n2 = matching(s);
s = s.Left(n) + fmt64(eval2(s.Mid(n+1, n2-n-1))) + s.Mid(n2+1);
return eval2(s);
}

if ((n = s.Find('*'))>=0)
return eval2(s.Left(n))*eval2(s.Mid(n+1));

if ((n = s.Find('+'))>=0)
return eval2(s.Left(n)) + eval2(s.Mid(n+1));

return atoll(Trim(s));
}

[grams]

Day 19:

(click to show/hide)

I reckon parsing with a spreadsheet is a bit too hard but I did use one to turn the rules into a monster regex that worked perfectly full time for Part 1.

Part 2 I did by looking at the rules.

0: 8 11
8: 42 | 42 8
11: 42 31 | 42 11 31

Which implies every valid string has (n+m) instances of 42 followed by m instances of 31, where n and m are both >= 1. So I extracted the 31 and 42 regexes and made a table to build and try giant slow regexes for different values of m (n >= 1 is handled by the + operator). Max actually needed was m=5.

https://docs.google.com/spreadsheets/d/1c3sM2aFwMljOh9K5EcRXms9jCB55ErwjGsTzpp89TjM/edit?usp=sharing

[tonycollinet]

I have to confess, 19p2 has me beat.

[grams]

I have to confess, 19p2 has me beat.

(click to show/hide)

If your root rules are the same as mine you can completely ignore the recursion and just feed "0: 42 42 31" and various other valid combinations into your code from part 1. It does explicitly say in today's task that you only need it to work for the rules you have, not to be general purpose.

[Greenbank]

(click to show/hide)

Split this into two stages (well 2 for part one and then a third for part 2 when you have to write a slightly different calculation function).

First of all you need a function/method/procedure/whatever to calculate the value of the string assuming there are no parentheses.

So, given the string "1 + 2 * 3 + 4 * 5 + 6" you need to be able to parse this and come up with an answer.

For part 1 this is relatively simple as you simply read it in from left to right and apply the operations as you see them.
curr = 1
curr + 2 = 3
curr * 3 = 9
curr + 4 = 13
curr * 5 = 65
curr + 6 = 71

But this obviously doesn't deal with parentheses. But, as others have hinted, you don't really need to worry too much about them. Just look for what you can calculate, if the the string is:-

"( ( ( 3 + ( 2 * 4 + 5 ) * 2 ) + 1 ) + 2 ) + 3"

Then you just need to deal with what you can deal with, and that is strings that don't have parentheses.

So either use grams approach and look through the string for the last opening parenthesis followed by the next closing parenthesis. That gets you the string "(2 * 4 + 5)" which you can work out using your earlier function to be 13 and so you replace "(2 * 4 + 5)" by 13 to get:-

"( ( ( 3 + 13 * 2 ) + 1 ) + 2 ) + 3"

Now you repeat the previous step and process "(3 + 13 * 2 )" to get "32", giving you "( ( 32 + 1 ) + 2 ) + 3" and so on through "( 33 + 2 ) + 3", "35 + 3" to "38".

If you want to use regex then I looked for an opening parenthesis following by any number of characters that weren't another opening parethensis and then a closing parenthesis. That allowed me to pull out the chunks that could be solved by the function/method/procedure/whatever developed earlier.

Then part (2) was just a different version of the calculation function, the parentheses will be dealt with in exactly the same way as before.

So given a string of "1 + 2 * 3 + 4 * 5 + 6" we know that addition should be performed first, so we look for every occurrence of "<numbers>  + <numbers>" and replace those with the answers, e.g.

"1 + 2" -> 3
"3 + 4" -> 7
"5 + 6" -> 11

giving:-

"3 * 7 * 11" = "231"

Again, this is just applied to each sum enclosed by parentheses (that doesn't have any other sub clauses in it).

[Greenbank]

(click to show/hide)

I didn't use regex or anything like that for this problem.

I used a recursive solution that, surprisingly, gave the correct answer quickly (solving both parts in less than a second) with minimal hassle.

I just started off with a string of "0" and, upon recursion, the function would attempt to replace the first number in the current string with each of the corresponding possibilities.

With each recursion the start of the string would grow with a number of a's and b's before the first number appeared, so I could bail on any attempts where the current string didn't match the start of the string I was attempting to check. This was possible as there was no way for the rules to change what characters had already been laid down before the first number.

I thought I would need to modify it to spot when the string was too long but this never happened.

So, in my rules, I had:-

0: 8 11
8: 42
42: 69 48 | 12 41
...

Where 69 was "a" and 12 was "b".

So if I was trying to match "bbbb" for example, it would go:-

"0" and find rule "0" -> "8 11" to give:-
"8 11", and checking rule "8" -> "42" to give: "42 11"
"42 11", and checking rule "42" -> "69 48" or "12 41",
so first try: "69 48 11"
  "69 48 11" and checking rule "69" -> "a" we get "a 48 11" but this would only give strings starting with "a" and our string starts with "b" so no match here
second try: "42" -> "12 41" to give "12 41 11"
  "12 41 11" and checking rule "12" -> "b" we get "b 41 11" and so the [ab] characters on the left hand side ("b") match the first bits of the string we want to match, so it continues and recurses, etc.

No other early bail was required, it ran quickly for both strings that matched and strings that didn't match.

Given this, part 2 was a doddle, I just replaced the 8 and 11 rules and it ran straight away giving the right answer first time. No tweaks to the algorithm required. I submitted my answer for part two a whole 75 seconds after my answer for part one.

As others have said, it was specifically designed not to be overly tricky, it could have included so many levels of nesting/recursion/loops that would have made lots of naive algorithms spin for days. Luckily it didn't.

[Diver300]

I'm struggling on day 19. After some effort I got an algorithm to run that produces 2^21 rules, each of 24 characters in length. The length isn't set in the algorithm, the 24 is what comes out of the data.

None of those match the messages.

I've run through the first option for each rule set and it seems to work out to the first rule that my algorithm produces.

[Diver300]

I'm struggling on day 19. After some effort I got an algorithm to run that produces 2^21 rules, each of 24 characters in length. The length isn't set in the algorithm, the 24 is what comes out of the data.

None of those match the messages.

I've run through the first option for each rule set and it seems to work out to the first rule that my algorithm produces.

I've just realised my counting of the matches with the messages was wrong. I've done the first part.

[tonycollinet]

I've reached the point where the time to solve the puzzles is longer than the available time I have each day. I'm going to carry on, but no longer attempt to keep up. Falling of the back of the peloton as it were

[grams]

Day 20 part 1:

(click to show/hide)

There's a shortcut to find the tiles for the answer without worrying about all the others

[Croft]

Day 20 part 1:

(click to show/hide)

There's a shortcut to find the tiles for the answer without worrying about all the others

(click to show/hide)

Which probably explains why the completion times for part 2 are so much longer because (as far as I can see) that shortcut won't work for the second part.

[Greenbank]

2020 day 20. That was fun. I was in and out doing various bits so my time was rather fragmented.

Probably took me 90 minutes or so whilst actually sat at a computer, but that was spread out over ~8h or so, and some of those other 6.5h not at a computer were spent thinking about various bits so it would have taken me more than 90 minutes if I sat down to do it in one go (or maybe I would have gained some time not being so distracted or having to mentally get back into it, anyway, who knows).

Spotted the trick for part 1 and did that quite quickly, obviously part 2 renders that trick not so useful, but it does help with how you need to go about the major chunk of part 2.

Annoying as I had an off by one error in part 2 that meant I got the correct answer for the example but not for my input (always fun when that happens). Also annoying that I had to go out this afternoon for a long walk and only fixed it when back (within 2 minutes!), so it could have been finished 3h earlier.

Interesting problem. Was good to break it down into little chunks and solve each of those (with some testing!) and see it all assemble together to give the answer.

[EDIT] I don't look at the leaderboards until I've got both stars so I never really know whether it's a hard problem or whether I'm just missing something obvious. It's my best placing on part 2 so far this year (3141) which taking into account the large amount of time away from the computer, is good going.

[Ben T]

Found day 19 part 2 quite hard but have done it now.

(click to show/hide)

Rule 0 is just 8..11.
Rule 8 is just 42, or 42..8 => so just 42 repeated any number of times.
Rule 11 is 42..31 or 42..11..31. So in other words, 11 = 42..31 | 42..42..31..31 | 42..42..42..31..31..31| etc    - i.e. 42 n times, then 31 that same number of times.

So rule zero is therefore
42{1,}..42{m}..31{m}
therefore
42{n}..31{m} where n >= m+1

(click to show/hide)

first resolve all the other rules (or at least 31 and 42, which probably involves resolving the others) to regexes, then
for each line, keep matching 31 at the end, keep track of how many times you have matched 31, and if the remainder matches 41 that many times + 1, you have a match.

Code: [Select]

private static bool IsMatch(string line)
{
    string wip = line;
    int end31s = 0;
    while(true)
    {
        string newwip = Regex.Replace(wip, $"{rule31}$", "");
        if(newwip != wip) end31s++;
        else return false;

        if(Regex.IsMatch(newwip, $"^{rule42}{{{end31s+1},}}$")) return true;

        wip = newwip;
    }
}



[grams]

Day 20 parts 1 and 2:
https://docs.google.com/spreadsheets/d/1pMovEAF1L-UlmCy6rSLCFxMGXzA6VrhzESYRUmPPTQY/edit?usp=sharing

(click to show/hide)

This was a ludicrous amount of work. Using the corners form part 1 you can build out the whole image as all edges are unique. Then you have to build out the image, remembering to flip the data in each tile (which I completely forgot to do first time). Then you have to try out all orientations of the whole image until you find any sea monsters. Then you have to check the lines for a second sea monster. Then possibly a third.

If you wanted to shortcut all this, just count the hashes in your tiles, guess a plausible number of sea monsters and multiply by 15 and deduct it.

[Greenbank]

(click to show/hide)

...
If you wanted to shortcut all this, just count the hashes in your tiles, guess a plausible number of sea monsters and multiply by 15 and deduct it.

(click to show/hide)

I did think that it'd be possible to do this with a binary search but Eric obviously foresaw this and you stop getting the "that's too high" or "that's too low" hints after a few incorrect attempts. The delays between guess attempts also grows I think.

[Davef]

I thought the second part of today’s was a bit of a slog. Certainly no solution I could see in a few lines of code though I could see what I had to do -  plenty of opportunity for errors.

[Davef]

Day 21 part 2 seemed rather trivial. Perhaps I had over-solved part 1.

[Croft]

(click to show/hide)

I think day 21, which I enjoyed, would be more interesting if it didn't include the worked example. The puzzle here is in translating the problem into, what turns out to be, a couple of simple set operations. The worked example makes that possible as a pattern matching exercise rather than the more interesting logical reasoning.

[Davef]

(click to show/hide)

I think day 21, which I enjoyed, would be more interesting if it didn't include the worked example. The puzzle here is in translating the problem into, what turns out to be, a couple of simple set operations. The worked example makes that possible as a pattern matching exercise rather than the more interesting logical reasoning.

(click to show/hide)

Seemed oddly similar to day 16

For me, part 2 was “now sort your results into alphabetical order”!

[Diver300]

Day 21 part 2 seemed rather trivial. Perhaps I had over-solved part 1.

I can't see how part 1 can be solved without going most of the way to solving part 2.

(click to show/hide)

As with Day 16, where columns could be matched to rows by finding rows that only matched one column, and eliminating those columns for other rows, Day 21's list of ingredients could be matched to allergens by eliminating ingredients known to only match one allergen.

I suspect that may be a property of puzzles with unique solutions. Problems in real life aren't so simple.

The solution to Day 21 part 1 probably doesn't need allergens to be uniquely allocated to ingredients. I had done that allocation before submitting my answer to part 1

[grams]

Day 21:
https://docs.google.com/spreadsheets/d/1jEu0iCON4JgT1V5ee8U4zAsdBD3f9Ly33wvktBDqNfQ/edit?usp=sharing

(click to show/hide)

I spent a *long* time looking at the example and not understanding it at all. The "each allergen only appears in one ingredient" didn't really click and doesn't fit how allergens work. Not a great framing device. And yeah, a rehash of Day 16.

Also I wasted a lot of time wondering why it wouldn't work because I'd lost 1 of the allergens completely with a wonky cell reference.

The AoC code wouldn't accept my answer. After wondering if my data was bad or the site was broken, I realised I'd also lost 50 ingredients to the same mistake. FFS.

I can't see how part 1 can be solved without going most of the way to solving part 2.

See the "alternative" tab on my spreadsheet. For each allergen, only ingredients that appear in every food that mentions that allergen are candidates to be an allergen. Only 8 ingredients have that property for at least one allergen. I'm not sure if that's guaranteed to be true, but it is for the data you're given.

[Greenbank]

Day 20 alternative input: https://gist.github.com/alexgreenbank/3a5dcb1a2854321558509247b1ed78e4

[grams]

Day 20 alternative input: https://gist.github.com/alexgreenbank/3a5dcb1a2854321558509247b1ed78e4

Needs more sea monsters.
https://docs.google.com/spreadsheets/d/1dhOAv1rMzblj7Y6POpbM1DPKnj3eypgsz0fC5JPrXas/edit#gid=901221645

[Davef]

Day 20 alternative input: https://gist.github.com/alexgreenbank/3a5dcb1a2854321558509247b1ed78e4

Lost on me as my solution didn’t actually rotate or stitch together the data but just kept the original data along with a list of transformations. With hindsight this was a mistake because although efficient once working it was hellish to debug. It also means I can could not visualise your data without writing some more code.

[Davef]

Day 22 done. Back to fine tuning my day 17 part 2 multidimensional life.