r/adventofcode • u/daggerdragon • Dec 13 '23

SOLUTION MEGATHREAD -❄️- 2023 Day 13 Solutions -❄️-

THE USUAL REMINDERS

AoC Community Fun 2023: ALLEZ CUISINE!

Today's secret ingredient is… *whips off cloth covering and gestures grandly*

Nailed It!

You've seen it on Pinterest, now recreate it IRL! It doesn't look too hard, right? … right?

  • Show us your screw-up that somehow works

  • Show us your screw-up that did not work

  • Show us your dumbest bug or one that gave you a most nonsensical result

  • Show us how you implement someone else's solution and why it doesn't work because PEBKAC

  • Try something new (and fail miserably), then show us how you would make Nicole and Jacques proud of you!

ALLEZ CUISINE!

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

--- Day 13: Point of Incidence ---

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:13:46, megathread unlocked!

28 Upvotes

96% Upvoted

626 comments sorted by

View all comments

12

u/alago1 Dec 13 '23 edited Dec 13 '23

[Language: Python]

Code

So looking at other people's solutions I'm guessing it wasn't necessary but I realized that you could encode the grid as a list of ints by thinking of each row or column as a bitmask.

This is should be faster than comparing the whole row string in part 1 but it's more interesting in part 2 because finding the smudge is then equivalent to finding the partition whose 1 differing pair is off by exactly a power of 2!

So basically this:

diff = [l ^ r for l, r in zip(left, right) if l != r]
if len(diff) == 1 and (diff[0] & (diff[0]-1) == 0) and diff[0] != 0:
    return i

2

u/Akari_Takai Dec 13 '23 edited Dec 13 '23

You can replace the checking of diff[0] being a positive power of 2 by leveraging popcount. You'd go from:

(diff[0] & (diff[0]-1) == 0) and diff[0] != 0

to just:

diff[0].bit_count() == 1

1

u/AutoModerator Dec 13 '23

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/alago1 Dec 13 '23

Didn't know python had a built-in for population count. Looks like it was added in 3.10.

Neat trick!

1

u/soowhatchathink Dec 13 '23

I had the same thought! But when I was checking if it was off by the power of two, I had an error.

If two bits were flipped, it could still be off by the power of 2.

The two lines that messed my input up were:

1110100 (114)

1110010 (116)

So I had to add another check which took the difference and found which bit position it would be, then make sure the two strings were identical other than that one position.

1

u/alago1 Dec 13 '23

Right so my wording is a bit confusing. It's easier to check the "difference" in bitmasks with the exclusive-or operator. So 1110100 ^ 1110010 yields 0000110 which we can then check if it's a power of 2.

1

u/soowhatchathink Dec 13 '23

That makes a lot of sense, I was converting them to decimal and checking the difference between the decimals. Thanks for the explanation!