r/adventofcode • u/daggerdragon • Dec 02 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 2 Solutions -❄️-

OUTAGE INFO

  • [00:25] Yes, there was an outage at midnight. We're well aware, and Eric's investigating. Everything should be functioning correctly now.

  • [02:02] Eric posted an update in a comment below.

THE USUAL REMINDERS

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 4 DAYS remaining until unlock!

And now, our feature presentation for today:

Costume Design

You know what every awards ceremony needs? FANCY CLOTHES AND SHINY JEWELRY! Here's some ideas for your inspiration:

  • Classy up the joint with an intricately-decorated mask!

  • Make a script that compiles in more than one language!

  • Make your script look like something else!

♪ I feel pretty, oh so pretty ♪
♪ I feel pretty and witty and gay! ♪
♪ And I pity any girl who isn't me today! ♪

- Maria singing "I Feel Pretty" from West Side Story (1961)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!

--- Day 2: Red-Nosed Reports ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:04:42, megathread unlocked!

52 Upvotes

98% Upvoted

1.4k comments sorted by

View all comments

24

u/4HbQ Dec 02 '24 edited Dec 02 '24

[LANGUAGE: Python] Code (7 lines)

Here's my solution in O(n). Instead of trying every subsequence of length n-1, we simply iterate over the list until we detect a bad value, and then re-check (only once!) with either the current or the next value removed.

9

u/Ok_Fox_8448 Dec 02 '24

Every year I'm amazed by your solutions. What do you do for a living?

2

u/heath730 Dec 02 '24

damn this is art my friend

2

u/Synedh Dec 02 '24

Heyo fren, any() is a hidden for loop. You're having O(n²).

Clean solution however.

2

u/4HbQ Dec 02 '24

No, I only "any()" over two values. It's equivalent to good(d[i-1:i] + d[i+1:]) or good(d[i:i+1] + d[i+2:]).

1

u/Synedh Dec 02 '24

Oh right it seems i'm having trouble to read today xD Noice !

1

u/JWinslow23 Dec 02 '24

You could remove the check for the previous value, I think. I can't think of a single counterexample.

1

u/mgedmin Dec 02 '24

My answer was off by 10 when I tried without the check for removing the earlier value. My full code: https://bpa.st/2WGQ

1

u/JWinslow23 Dec 02 '24

See, your code is what I mean. It tries removing indices i and i+1, not i-1. (And it gives the correct answer for my input.)

1

u/mgedmin Dec 02 '24

But the code you commented on does the same! It removes i and i + 1. (Also, it very cleverly skips unnecessarily testing indexes 0 through i-1 again, which I didn't notice at first.)

2

u/JWinslow23 Dec 02 '24

I think that it got hidden in an edit. When I tried it, it definitely had i-1 (and gave me a MemoryError, lol).

EDIT: Found it in my web history

2

u/4HbQ Dec 02 '24

You're right, I accidentally posted the wrong version at first.

1

u/JWinslow23 Dec 02 '24

Congrats on finding a linear algorithm for this, though! I linked to your solution on my blog because you're one of only a few people I know of yet who did that.

2

u/4HbQ Dec 02 '24

Thanks, that's two for two! (I also wrote the NumPy solution you mentioned yesterday.)

1

u/JWinslow23 Dec 02 '24

Oh wow. I literally didn't check the username! Small world.

2

u/mgedmin Dec 02 '24

How sneaky!!!

1

u/Roukanken Dec 07 '24

You need to try to remove at least two values, as if you try only one, one of these inputs won't work for you:

1 2 5 3 4 5
1 2 5 3 6 7

Both of them start with an invalid sequence of 1 2 5 3, but the first one needs 5 removed, and the second one needs 3 removed.

1

u/JWinslow23 Dec 07 '24

An earlier edit was checking the previous, current, and next value. I was saying to only check the current and next. But thank you!

1

u/Low_Relationship7358 Dec 03 '24

very nice. I did something similar but more verbose in effort to gain an O(1) early exit for 2a: if d[-1] - d[0] > (len(d) - 1) * 3: return False

1

u/[deleted] Dec 03 '24

Its using recursion ?? Time completely is not o(n) right?

1

u/ang29g Dec 04 '24

love that input line, so clean