Advent Of Code 2024

gilbert_given_189

Day 5 - Discussion
This day's quite a doozy. I did catch it early (unlike the first four days), but my solution is quite slow. Even PyPy took a second to process my input.
I did get confused on how to fix the list of updates, and my solution… isn't the best, but eventually I made it through.

Day 5 - Solution
Using a different format now.

N3q8ryccAASklkocDwMAAAAAAAAiAAAAAAAAAIk4j+fAB1FTUBDwDzmEi7YY7Nbb08XL42XG4DDH
0oGrfWtd2OJ6IQgVFSo1Jj0mIrPzxdR1ksrCoKF7cJYj7ENG2ST/PSa2u0st3qPAQT2HXNoZqSBt
YMjORRQA6Y2COftv/3uiZmVliUwhuDFq4bvPkmR2mPivjKiDGarwNt6rHJMC6s7+CfOFqN3e70qJ
qxQVLsT64hUxT129TAWckjqsmaDua7CTMrpc67JTWhOiQSVFj9VA/7AuUEWj1jnCLc7hGjEA8q47
HRLOOlbsDB9NOsxTyX6cQgv1xcvdee1dG++tz93n0e1z3siqSW8wtK/6QnwxItyUZhdvqNSFIjSw
xhm5u9LvN11dw1vAQo6LvJbs9Bcvko7tQF3/wz8OOz41oHJHsEe6oQJd4TufvmKsS2AqTj34dFak
4TeSs/FUqk6TW69w5UaURpjyMKShOjC4rB9q1ZQJUzm/MwoQSGd7PwIQ9Lxzv39lqzmZOu5VVy1L
QiHlC5M1F5pYvZ2jeUiSYPjT1hiQvpbVCbIQfkiDA5iRkAz+cGZLo6jpyrv+d4Zt/FiKQbWTT0gF
hsPiAPFJHhtyXJyCJ/2T7fUjR2aqaSrytZYEoCPorZncnUPeeE6pNlgK+X2ss/Rs0/THe+sxeM0G
QQ+VP7TU5k3ryIINiNYNBiS7WgKJWVT8qKErNlZx9TgZnaNcK9Gq12v8nepUq4tPY+EcssLB5EXK
Txd/GlTR4qAPZmgJOlHYD1v5fk3XVH8KBGkHo9TkFYW0xJ74lXS3M7OsQHqTNxHJtvgAuq2FhPk9
ERdPog5CdNklvdhmdaOoSUopOJLRSxRomM4pCwtbRinMT0MxkDCtqxDCc/cM1I0XHkDZZpD+TlX3
MGUTxwAAgTMHrg/VRgM1FmwnAeD7MSU25BKye0MDkgyJMtCou58p3V8ZZgdttDCGaenpZ+rcHoFg
wvdi78GR6rXuB9Got/VGLEQlVsulalNUBA6DgnfGseia+VY9qw0ywFx9fT2Znqtwaa85aDUHzMDd
cM4McvshRNb37wIKvWB6wAAXBoKQAQl/AAcLAQABIwMBAQVdABAAAAyAngoB+z3WrgAA

Last edited by gilbert_given_189 (Dec. 5, 2024 09:09:21)

ideapad-320

How do I decrypt that base64?

mybearworld

Day 5 - DIscussion

Day 4 seems to have been an outlier in being weirdly more difficult? This was easier again.

applejuiceproduc

mybearworld wrote:
Day 5 - DIscussion

Day 4 seems to have been an outlier in being weirdly more difficult? This was easier again.

That's good to hear since I didn't have time to do any more than read the question today, so I have to do 2 tomorrow

gilbert_given_189

mybearworld wrote:
Day 5 - DIscussion

Day 4 seems to have been an outlier in being weirdly more difficult? This was easier again.

Is it easier to your head, or for the computer? Mine's definitely not the latter.
Though I'm not sure how you did Day 4. For me, I tried [using as much string ops, a makeshift transpose function, and some skewing to do the diagonals for part 1, and SciPy's convolve2d function for part 2.]
(someone told me to hide the spoilers, but I don't think it's working properly)

Last edited by gilbert_given_189 (Dec. 6, 2024 04:59:27)

davidtheplatform

Pro tip: put spoilers inside [color] tags with the color set to #00000000, which makes the text invisible unless you highlight it.
For example:

[color=#00000000]Spoiler text...[/color]

produces: >>> Spoiler text… <<<

EDIT: here's a better template by gilbert_given_189:

[][[/][u][color=#00000000]<>[/u][/color][]][/]

Example: [Spoiler text…]

Last edited by davidtheplatform (Dec. 6, 2024 19:23:26)

gilbert_given_189

davidtheplatform wrote:
Pro tip: put spoilers inside [color] tags with the color set to #00000000, which makes the text invisible unless you highlight it.
For example:
[color=#00000000]Spoiler text...[/color]
produces: >>> Spoiler text… <<<

I though Day 4 is over? I do know I can hide text though.

gilbert_given_189

Day 6 - Discussion
First part is not a problem. I struggled on the second part, but only because I flipped the comparison of [whether or not the guard loops.] Whoops.

Day 6 - Solution

N3q8ryccAAR4Kis2UQMAAAAAAAAjAAAAAAAAADR0BqZnsul9aIQaOWVDIwABXlAsM8m4dxzp+BwY
fa7qaZDzENhKR70k+NQv2344G6uQAkiqbRbpi35/W/IGXuWib1OQjWvDFyqjQq4TnMDPVq0zGdvv
BiKx16bSaIaTAcZ5tOwZf65FSjf/dhkn7YoZ5G3xNCPz5C5vR+G8+IPS03EP86TzhF4dQQ0gvf+h
93sUHaEP5DC3xQlXcmVho9I27bSymkVCgJ4+rT0EVjCL+Sb9yXfQ2uFBn9NdCFJCoOptmi9QBm/Q
6Nbl2XO5ETWTlSBbOTXwH99jsBD7W+VRuHXlf1YJoN64NcIQjps//cRxOL2FK6gA+Ceg9+Pi4uw6
LaEH1+Xe8bv1uE1k0BU8z6eJtP0BCqsDhwgIWE+renMF9H9/YyJa9XPdYOL1kpIaDRCqDqvFdX9l
HllvAR+cgZHVhsuAeS3/fl0GXi/Hw0qUvzzShgBd9+p6hQT2ESnRtvAp2Vl7H0G202linUn8WxAK
79/3/TDpt+RwDgOfs9x06gDYFZrPVEZzZEK+h0XSvjWZvtcAX4UbqCKH7Q3of8LhPWXfmfckB0hp
NoMfNqNoU1yPxnnagpgUto5HLpt1wcpLTKXCa2er/WJsVYL8dEkFhusW6MwmgRP8kycJJvMdETXX
wXEsmhhVVNVI1BnrEvZJ9hQ+ijqZYOF8XPpCh19oIZqKw4MUzFGfObSewdBpuRgFOwRjquk3SVmJ
uI+BB+YwHKyviJra+g60lMkspZGf22rXk4i1tI4Hv737orm2Dg7O+n8SS55oil8lc7KU+FyicDDf
QFqoRXvHrU2ekQezpe8aIdfZqlj1u7lWgkUQhWDjGHyz9GZgcvQkWp1N2Lis556vlxAVpDuGumMH
2pTSRYymo98fcxfQETavz8wVCYI9ZC3fdxQDHKBbW6xvauhq4HyAKwj8mWwI+oj85iZcbI746lOK
GY6wSfM5T4qI388AAIEzB64P1UduRRck0c/kBCgFLxd2gY3ANhQEjKAoYzc7OTqsR/WT4L0hn4C/
uKApElFu6hDtslyLJN9xiZQgsyfqbRo/aC0mwxjR/ks3nXtFrKo5b3VP5Ch3f0HBVrB3EnAVvNNJ
Y1cyotVEPp3wNzviVrasUiEiM92hGYMAAAAXBoLQAQmAgQAHCwEAASMDAQEFXQAQAAAMgJ4KAQ7S
94UAAA==

mybearworld

gilbert_given_189 wrote:
(#45)
Though I'm not sure how you did Day 4. For me, I tried [using as much string ops, a makeshift transpose function, and some skewing to do the diagonals for part 1, and SciPy's convolve2d function for part 2.]

I iterated through the string looking for “X”s, checked for “M”s around that, from which point I knew the direction so I could check “A” and “S” from there for part 1. For part 2, I just had to check for “A”s and had to check if the tiles around it were fitting.

Day 6 - Discussion

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHHHHHHHH I got it now

Last edited by mybearworld (Dec. 6, 2024 14:55:04)

davidtheplatform

Day 6 discussion
Did anyone do a non brute force solution? I [looped through every location, and if the guard had visited it in part 1, check if it loops.] This is really slow for some reason, it took 15 minutes to run even with a python compiler (i used codon, pypy was a little bit slower)

davidtheplatform

gilbert_given_189 wrote:
davidtheplatform wrote:
Pro tip: put spoilers inside [color] tags with the color set to #00000000, which makes the text invisible unless you highlight it.
For example:
[color=#00000000]Spoiler text...[/color]
produces: >>> Spoiler text… <<<
I though Day 4 is over? I do know I can hide text though.

I didn't see your post with spoiler tags until now somehow. I also added a template for your method to #46

davidtheplatform wrote:
Day 6 discussion
Did anyone do a non brute force solution? I [looped through every location, and if the guard had visited it in part 1, check if it loops.] This is really slow for some reason, it took 15 minutes to run even with a python compiler (i used codon, pypy was a little bit slower)

I made some optimizations: [1. Replaced the map with a numpy array. My solution copies the map for every tile it checks and the numpy copy method is really fast. 2. Replaced an array of states with a set. Both of these combined makes the code run in about 30 seconds in normal python]

mybearworld

davidtheplatform wrote:
(#50)
Day 6 discussion
Did anyone do a non brute force solution? I [looped through every location, and if the guard had visited it in part 1, check if it loops.] This is really slow for some reason, it took 15 minutes to run even with a python compiler (i used codon, pypy was a little bit slower)

I mostly did that - [I went through the grid as in part 1, but for every position that hasn't been seen before, I went through the grid again but with that position marked as an obstacle - I didn't need to loop through the positions that won't matter anyways like that.] But it's also a complete buggy mess, and took 14 seconds to complete lol (I do use Deno with no external libraries though, not Python with numpy)

Last edited by mybearworld (Dec. 6, 2024 19:34:41)

davidtheplatform

mybearworld wrote:
davidtheplatform wrote:
(#50)
Day 6 discussion
Did anyone do a non brute force solution? I [looped through every location, and if the guard had visited it in part 1, check if it loops.] This is really slow for some reason, it took 15 minutes to run even with a python compiler (i used codon, pypy was a little bit slower)
I mostly did that - [I went through the grid as in part 1, but for every position that hasn't been seen before, I went through the grid again but with that position marked as an obstacle - I didn't need to loop through the positions that won't matter anyways like that.] But it's also a complete buggy mess, and took 14 seconds to complete lol (I do use Deno with no external libraries though, not Python with numpy)

Can you explain the spoiler text more? I think we did the same thing but I'm not sure.

It's odd that part 2 uses a pure brute force solution - I remember reading that the problems are designed such that they can all be solved in less than a second if you use the right method, and most solutions I see run for longer than this.
Looking at other people's solutions, almost none of them reduce the search space beyond [only checking the tiles the guard touches in an unmodified map].
There is one interesting solution. It [records where each turn is and where it ends up, then uses this record to jump through the map until it reaches the new obstacle. I'm guessing this was the intended optimization, but its odd that only two people found it. ] (I can't include a link unfortunately).

50_scratch_tabs

Hello! I'm doing the Advent of Code. This is my first year doing it. I'm not reading the discussion because I'm not caught up yet, but I just wanted to say hi. I'll come back after I get caught up.

50_scratch_tabs

mybearworld wrote:
Day 4 - Discussion

Part 2 felt way easier than part 1 for me. Fewer lines of code, too.

WHAT??? I'm still working on day 4 part 2.

gilbert_given_189

davidtheplatform wrote:
Day 6 discussion
Did anyone do a non brute force solution? I [looped through every location, and if the guard had visited it in part 1, check if it loops.] This is really slow for some reason, it took 15 minutes to run even with a python compiler (i used codon, pypy was a little bit slower)

And this is why I use PyPy. The problem literally asked you to check every solution.

I think you could do some pruning on the search by [only considering obstacles that affect the initial guard's path], but I abandoned that idea because of that silly comparison mistake. Also, on my input, it's not that much faster than brute force (it's like 33% faster, though I think you can get half if you [also consider the guard's direction, rather than their positions only]).

Last edited by gilbert_given_189 (Dec. 7, 2024 04:05:35)

50_scratch_tabs

gilbert_given_189 wrote:
davidtheplatform wrote:
Day 6 discussion
Did anyone do a non brute force solution? I [looped through every location, and if the guard had visited it in part 1, check if it loops.] This is really slow for some reason, it took 15 minutes to run even with a python compiler (i used codon, pypy was a little bit slower)
And this is why I use PyPy. The problem literally asked you to check every solution.

I think you could do some pruning on the search by [only considering obstacles that affect the initial guard's path], but I abandoned that idea because of that silly comparison mistake. Also, on my input, it's not that much faster than brute force (it's like 33% faster).

I just brute forced it and walked away. The most interesting part I thought of was detecting loops . I created a list of items that contain a position and direction, and if the current solution is in the list, it realizes that it's looping.

Last edited by 50_scratch_tabs (Dec. 7, 2024 04:06:44)

gilbert_given_189

Day 7 - Discussion
This is the fastest day so far. Looks like my venture into the esolanging world hasn't gone into waste, as I have done something like this on a BASIC-like esolang I'm procrastinating on developing

Day 7 - Solution

3q8ryccAASXp86BEgIAAAAAAAAjAAAAAAAAAEztZHcyVa50mUMJ5STOdrP4V5WvRtF/qXsFaryV
Ryw6a4/B14NhmQ+VAmN+qBceK/MNyFnvApmgJpIy4IcKxMhooZozpf+5D4443fY0RfmVtmfy/24X
VBCchnBI6Uf2Fq+IdAWQmZykMnbtAv4xQfvGrWzjwBsRJVS1qEOTnLQ0f5Yx1s04PQb0pbVL3wIx
QEjfJHIiCXIBv5Te/l8q27s1CBSdk1DpYbHvvDt+jrRaykHkT+ugAxwQCMDRzgnuyTJMRYRxGoyN
/BU/v3H8F4s8dt3YgWfPB653xCd6MHWNGsFKRLxIW/zf1YUyPdJMoBGSO3Fa5Gakv+cgVcaKGPQz
Mu1F19lzssbeYJ12BfzPbqrnblmg58mizDnPvxlRBpbl/HsXVodl3URFpO0We/cMq1KnK2qsjpO2
9a2E2wW6WT0eUpzUZWOpAEVP9heWN2cNwFvWjlwyDP9qCTF9Ofh3kUuzk71JGw/1IRfnjm8jljn2
vw8njw5jGlMXGQftcV8pKGNkiGI85BtWZI+fXKblI3rOAACBMweuD9U7ArUWbCcB4PsxJTbkErJ7
QkInYKd97ZOhndFFIZSxsBmZxdQgtzEWWEOw8ULwgWZd5xln96ZgbxFlKt9pnKZlqKfGzPV82VeA
Xh3+ddeRuL7y1J1mK1Z8ovUgwn2UVKwW7QZ5C9GbI3hxlkdZsJ7GVe/iFMDrtAAAABcGgZABCYCC
AAcLAQABIwMBAQVdABAAAAyAngoBD4FY+AAA

mybearworld

Day 7 - Discussion

My times today are terrible because I started really late, but this was probably the easiest part 2 yet - I had to add a single line for it.

50_scratch_tabs

How do you decode the solutions? It looks like base64, yet…

Discuss Scratch