Advent Of Code 2024

mybearworld

Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)

gilbert_given_189

mybearworld wrote:
Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)

Same for me. I even made a toggle for it.

Day 10 - Discussion

N3q8ryccAARurqo9wAIAAAAAAAAjAAAAAAAAAI1j9SXLnlrbjhFnRULkuAynTfW9U5l8TuvQBH1E
m6giW1HufV1DN6CF4zlMLB9TptbPKBhDZEJgXEU/uXeuF/m7KhUldHq3XY7VyPT+oACntJCNcIl+
hUAdbVgMqlZH+W8E0xf7OsRDUwPWOJzYOdqFi9GE0xHHFyYplcbX3uTe27WwmwWrHrO6C3ef8NaY
OqEfH91zYNR1Y6v4ZD3ZhbCRqs9dWZgSlVwmSpbio8jaLOkjyWqV90XrDKEKPLe9gt0CPFeEG5ns
8QiF6erE+E+ugvIxBR28+j+kkzRmgUu261ex4Ix22XJeLpkrDHWYttnZcjM+v773V0xzVMJ0nvtd
bgncv0xSB4nI3T0PydBAn+06R/k3JvxnKzwZ2iWQuBdTAFV9mBOoVVgX4+RgI9j4DjHj4VyNycsE
qbB78nzE10L8PbtUp6jr6txP638dj1NW1EGBMnYsmd7BIan8Qaalyf3DCn4Oo1YLQx+yPdeQHjiZ
Ub7epGeVcgwS6UmvHOT5lBi8v+varPJWyvUk2IabH+OIE1vTXjawn5UiX44SFcz4m2a7ir4sgQTg
y/abDytDE8ezfPZy7/SiE/30hgcmRvtBRsEaL8yYdDNtFYmq3Nmf+7BXF0D0HPsA2fx9QKFHNtvq
vgVYPhJ27OzxHEk9wkaOxZvcoJBL6ZqDzWYHGul5Lnh4mLNwmob+2gwiyJ3+a9zX0VVWcPMDdJUb
weN8m1zsinvOPOU0LOw1xK7GYDbMbE7GYx/w6bkuk6liu0QLhTcAAIEzB64P1UQ9YRck0c/kBCgF
Lxd2gY5mgh+6C9ScIrOdKl+88WdCY+QzxUZn50yK51lmKuv7X1qgvwQLr6td0bHuftzaaYZk+CvL
1ormJVZxl4gV5NHvm61Hyw/A00495dO6UN+tv/fQGq+b8zlOvv6bDlaewcHx+DKoWAAAABcGgkAB
CYCAAAcLAQABIwMBAQVdABAAAAyAngoBJBgF+AAA

davidtheplatform

mybearworld wrote:
Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)

This is pretty common for some reason. I did it correctly the first time but for part 2 I just had to comment out 1 line

ideapad-320

mybearworld wrote:
Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)

That was almost me on day 5.

ideapad-320

gilbert_given_189 wrote:
mybearworld wrote:
Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)
Same for me. I even made a toggle for it.

Day 10 - Discussion
N3q8ryccAARurqo9wAIAAAAAAAAjAAAAAAAAAI1j9SXLnlrbjhFnRULkuAynTfW9U5l8TuvQBH1E
m6giW1HufV1DN6CF4zlMLB9TptbPKBhDZEJgXEU/uXeuF/m7KhUldHq3XY7VyPT+oACntJCNcIl+
hUAdbVgMqlZH+W8E0xf7OsRDUwPWOJzYOdqFi9GE0xHHFyYplcbX3uTe27WwmwWrHrO6C3ef8NaY
OqEfH91zYNR1Y6v4ZD3ZhbCRqs9dWZgSlVwmSpbio8jaLOkjyWqV90XrDKEKPLe9gt0CPFeEG5ns
8QiF6erE+E+ugvIxBR28+j+kkzRmgUu261ex4Ix22XJeLpkrDHWYttnZcjM+v773V0xzVMJ0nvtd
bgncv0xSB4nI3T0PydBAn+06R/k3JvxnKzwZ2iWQuBdTAFV9mBOoVVgX4+RgI9j4DjHj4VyNycsE
qbB78nzE10L8PbtUp6jr6txP638dj1NW1EGBMnYsmd7BIan8Qaalyf3DCn4Oo1YLQx+yPdeQHjiZ
Ub7epGeVcgwS6UmvHOT5lBi8v+varPJWyvUk2IabH+OIE1vTXjawn5UiX44SFcz4m2a7ir4sgQTg
y/abDytDE8ezfPZy7/SiE/30hgcmRvtBRsEaL8yYdDNtFYmq3Nmf+7BXF0D0HPsA2fx9QKFHNtvq
vgVYPhJ27OzxHEk9wkaOxZvcoJBL6ZqDzWYHGul5Lnh4mLNwmob+2gwiyJ3+a9zX0VVWcPMDdJUb
weN8m1zsinvOPOU0LOw1xK7GYDbMbE7GYx/w6bkuk6liu0QLhTcAAIEzB64P1UQ9YRck0c/kBCgF
Lxd2gY5mgh+6C9ScIrOdKl+88WdCY+QzxUZn50yK51lmKuv7X1qgvwQLr6td0bHuftzaaYZk+CvL
1ormJVZxl4gV5NHvm61Hyw/A00495dO6UN+tv/fQGq+b8zlOvv6bDlaewcHx+DKoWAAAABcGgkAB
CYCAAAcLAQABIwMBAQVdABAAAAyAngoBJBgF+AAA

how. do. i. decrypt. that.

gilbert_given_189

ideapad-320 wrote:
gilbert_given_189 wrote:
mybearworld wrote:
Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)
Same for me. I even made a toggle for it.

Day 10 - Discussion
N3q8ryccAARurqo9wAIAAAAAAAAjAAAAAAAAAI1j9SXLnlrbjhFnRULkuAynTfW9U5l8TuvQBH1E
m6giW1HufV1DN6CF4zlMLB9TptbPKBhDZEJgXEU/uXeuF/m7KhUldHq3XY7VyPT+oACntJCNcIl+
hUAdbVgMqlZH+W8E0xf7OsRDUwPWOJzYOdqFi9GE0xHHFyYplcbX3uTe27WwmwWrHrO6C3ef8NaY
OqEfH91zYNR1Y6v4ZD3ZhbCRqs9dWZgSlVwmSpbio8jaLOkjyWqV90XrDKEKPLe9gt0CPFeEG5ns
8QiF6erE+E+ugvIxBR28+j+kkzRmgUu261ex4Ix22XJeLpkrDHWYttnZcjM+v773V0xzVMJ0nvtd
bgncv0xSB4nI3T0PydBAn+06R/k3JvxnKzwZ2iWQuBdTAFV9mBOoVVgX4+RgI9j4DjHj4VyNycsE
qbB78nzE10L8PbtUp6jr6txP638dj1NW1EGBMnYsmd7BIan8Qaalyf3DCn4Oo1YLQx+yPdeQHjiZ
Ub7epGeVcgwS6UmvHOT5lBi8v+varPJWyvUk2IabH+OIE1vTXjawn5UiX44SFcz4m2a7ir4sgQTg
y/abDytDE8ezfPZy7/SiE/30hgcmRvtBRsEaL8yYdDNtFYmq3Nmf+7BXF0D0HPsA2fx9QKFHNtvq
vgVYPhJ27OzxHEk9wkaOxZvcoJBL6ZqDzWYHGul5Lnh4mLNwmob+2gwiyJ3+a9zX0VVWcPMDdJUb
weN8m1zsinvOPOU0LOw1xK7GYDbMbE7GYx/w6bkuk6liu0QLhTcAAIEzB64P1UQ9YRck0c/kBCgF
Lxd2gY5mgh+6C9ScIrOdKl+88WdCY+QzxUZn50yK51lmKuv7X1qgvwQLr6td0bHuftzaaYZk+CvL
1ormJVZxl4gV5NHvm61Hyw/A00495dO6UN+tv/fQGq+b8zlOvv6bDlaewcHx+DKoWAAAABcGgkAB
CYCAAAcLAQABIwMBAQVdABAAAAyAngoBJBgF+AAA
how. do. i. decrypt. that.

$ base64 -d > day-n.7z

ideapad-320

gilbert_given_189 wrote:
ideapad-320 wrote:
gilbert_given_189 wrote:
mybearworld wrote:
Day 10 - Discussion

For part one, I spent a while trying to figure out why my code wasn't giving me the correct output for the examples. Rereading the question, I had apparently understood it incorrectly, so I needed to make some changes. Part two, then, was exactly what I'd accidentally done before! That was a very easy part two lol

(And unrelatedly, can we finally get actual tuples for JavaScript? Having to store coordinates as strings is very annoying.)
Same for me. I even made a toggle for it.

Day 10 - Discussion
N3q8ryccAARurqo9wAIAAAAAAAAjAAAAAAAAAI1j9SXLnlrbjhFnRULkuAynTfW9U5l8TuvQBH1E
m6giW1HufV1DN6CF4zlMLB9TptbPKBhDZEJgXEU/uXeuF/m7KhUldHq3XY7VyPT+oACntJCNcIl+
hUAdbVgMqlZH+W8E0xf7OsRDUwPWOJzYOdqFi9GE0xHHFyYplcbX3uTe27WwmwWrHrO6C3ef8NaY
OqEfH91zYNR1Y6v4ZD3ZhbCRqs9dWZgSlVwmSpbio8jaLOkjyWqV90XrDKEKPLe9gt0CPFeEG5ns
8QiF6erE+E+ugvIxBR28+j+kkzRmgUu261ex4Ix22XJeLpkrDHWYttnZcjM+v773V0xzVMJ0nvtd
bgncv0xSB4nI3T0PydBAn+06R/k3JvxnKzwZ2iWQuBdTAFV9mBOoVVgX4+RgI9j4DjHj4VyNycsE
qbB78nzE10L8PbtUp6jr6txP638dj1NW1EGBMnYsmd7BIan8Qaalyf3DCn4Oo1YLQx+yPdeQHjiZ
Ub7epGeVcgwS6UmvHOT5lBi8v+varPJWyvUk2IabH+OIE1vTXjawn5UiX44SFcz4m2a7ir4sgQTg
y/abDytDE8ezfPZy7/SiE/30hgcmRvtBRsEaL8yYdDNtFYmq3Nmf+7BXF0D0HPsA2fx9QKFHNtvq
vgVYPhJ27OzxHEk9wkaOxZvcoJBL6ZqDzWYHGul5Lnh4mLNwmob+2gwiyJ3+a9zX0VVWcPMDdJUb
weN8m1zsinvOPOU0LOw1xK7GYDbMbE7GYx/w6bkuk6liu0QLhTcAAIEzB64P1UQ9YRck0c/kBCgF
Lxd2gY5mgh+6C9ScIrOdKl+88WdCY+QzxUZn50yK51lmKuv7X1qgvwQLr6td0bHuftzaaYZk+CvL
1ormJVZxl4gV5NHvm61Hyw/A00495dO6UN+tv/fQGq+b8zlOvv6bDlaewcHx+DKoWAAAABcGgkAB
CYCAAAcLAQABIwMBAQVdABAAAAyAngoBJBgF+AAA
how. do. i. decrypt. that.
$ base64 -d > day-n.7z

echo "text" | base64 -d > day-n.7z

you gonna be releasing encryption keys yet?

ideapad-320

Day 10
Bonus points if you can do both parts in linear time (linear to the area, not the side length).

50_scratch_tabs

ideapad-320 wrote:
(#87)
you gonna be releasing encryption keys yet?

I tried with an online 7z decoder, and any password worked.

davidtheplatform

ideapad-320 wrote:
Day 10
Bonus points if you can do both parts in linear time (linear to the area, not the side length).

Part 1:

aW1wb3J0IG51bXB5IGFzIG5wCgpjbGFzcyBOb2RlOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHZhbHVlKToKICAgICAgICBpZiB2YWx1ZSA9PSAnLic6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSAtMgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSBpbnQodmFsdWUpCiAgICAgICAgc2VsZi5vdXQgPSBbTm9uZSwgTm9uZSwgTm9uZSwgTm9uZV0KICAgIGRlZiBfX3N0cl9fKHNlbGYpOgogICAgICAgIHJldHVybiBmJycnIHsnfCcgaWYgc2VsZi5vdXRbMF0gZWxzZSAnICd9CnsnLScgaWYgc2VsZi5vdXRbM10gZWxzZSAnICd9e3NlbGYudmFsdWV9eyctJyBpZiBzZWxmLm91dFsxXSBlbHNlICcgJ30KIHsnfCcgaWYgc2VsZi5vdXRbMl0gZWxzZSAnICd9ICcnJwoKbWFwMSA9IFtdCndpdGggb3BlbignMTAudHh0JykgYXMgZjoKICAgIGZvciBsaW5lIGluIGYucmVhZGxpbmVzKCk6CiAgICAgICAgbWFwMS5hcHBlbmQobGlzdChsaW5lLnJlcGxhY2UoJ1xuJywgJycpKSkKICAgIAptYXAyID0gbnAuZW1wdHkoKGxlbihtYXAxKSsyLCBsZW4obWFwMVswXSkrMiksIGR0eXBlPU5vZGUpCmZvciB5IGluIHJhbmdlKGxlbihtYXAyKSk6CiAgICBmb3IgeCBpbiByYW5nZShsZW4obWFwMlt5XSkpOgogICAgICAgIG1hcDJbeSwgeF0gPSBOb2RlKC0yKQpmb3IgeSBpbiByYW5nZShsZW4obWFwMSkpOgogICAgZm9yIHggaW4gcmFuZ2UobGVuKG1hcDFbeV0pKToKICAgICAgICBtYXAyW3krMSwgeCsxXSA9IE5vZGUobWFwMVt5XVt4XSkKemVyb3MgPSBbXQpmb3IgeSBpbiByYW5nZShsZW4obWFwMSkrMSk6CiAgICBmb3IgeCBpbiByYW5nZShsZW4obWFwMVswXSkrMSk6CiAgICAgICAgY3VyID0gbWFwMlt5LCB4XQogICAgICAgIGlmIGN1ci52YWx1ZSA9PSAwOgogICAgICAgICAgICB6ZXJvcy5hcHBlbmQoKHgsIHkpKQogICAgICAgIGlmIG1hcDJbeS0xLCB4XS52YWx1ZSA9PSBjdXIudmFsdWUgKyAxOgogICAgICAgICAgICBjdXIub3V0WzBdID0gbWFwMlt5LTEsIHhdCiAgICAgICAgaWYgbWFwMlt5LCB4KzFdLnZhbHVlID09IGN1ci52YWx1ZSArIDE6CiAgICAgICAgICAgIGN1ci5vdXRbMV0gPSBtYXAyW3ksIHgrMV0KICAgICAgICBpZiBtYXAyW3krMSwgeF0udmFsdWUgPT0gY3VyLnZhbHVlICsgMToKICAgICAgICAgICAgY3VyLm91dFsyXSA9IG1hcDJbeSsxLCB4XQogICAgICAgIGlmIG1hcDJbeSwgeC0xXS52YWx1ZSA9PSBjdXIudmFsdWUgKyAxOgogICAgICAgICAgICBjdXIub3V0WzNdID0gbWFwMlt5LCB4LTFdCgoKcyA9IDAKZGVmIGNoZWNrX2hlYWQoeCwgeSk6CiAgICBnbG9iYWwgcwogICAgaWYgKHgsIHkpIGluIGNoZWNrX2hlYWQudmlzaXRlZDoKICAgICAgICByZXR1cm4KICAgIGNoZWNrX2hlYWQudmlzaXRlZC5hZGQoKHgsIHkpKQogICAgbm9kZSA9IG1hcDJbeSwgeF0KICAgIGlmIG5vZGUudmFsdWUgPT0gOToKICAgICAgICBzICs9IDEKICAgICAgICByZXR1cm4KICAgIGlmIG5vZGUudmFsdWUgPT0gLTI6CiAgICAgICAgcmV0dXJuCiAgICBpZiBub2RlLm91dFswXToKICAgICAgICBjaGVja19oZWFkKHgsIHktMSkKICAgIGlmIG5vZGUub3V0WzFdOgogICAgICAgIGNoZWNrX2hlYWQoeCsxLCB5KQogICAgaWYgbm9kZS5vdXRbMl06CiAgICAgICAgY2hlY2tfaGVhZCh4LCB5KzEpCiAgICBpZiBub2RlLm91dFszXToKICAgICAgICBjaGVja19oZWFkKHgtMSwgeSkKCmZvciB6ZXJvIGluIHplcm9zOgogICAgY2hlY2tfaGVhZC52aXNpdGVkID0gc2V0KCkKICAgIGNoZWNrX2hlYWQoemVyb1swXSwgemVyb1sxXSkKCnByaW50KHMpCg==

Part 2:

aW1wb3J0IG51bXB5IGFzIG5wCgpjbGFzcyBOb2RlOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHZhbHVlKToKICAgICAgICBpZiB2YWx1ZSA9PSAnLic6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSAtMgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSBpbnQodmFsdWUpCiAgICAgICAgc2VsZi5vdXQgPSBbTm9uZSwgTm9uZSwgTm9uZSwgTm9uZV0KICAgIGRlZiBfX3N0cl9fKHNlbGYpOgogICAgICAgIHJldHVybiBmJycnIHsnfCcgaWYgc2VsZi5vdXRbMF0gZWxzZSAnICd9CnsnLScgaWYgc2VsZi5vdXRbM10gZWxzZSAnICd9e3NlbGYudmFsdWV9eyctJyBpZiBzZWxmLm91dFsxXSBlbHNlICcgJ30KIHsnfCcgaWYgc2VsZi5vdXRbMl0gZWxzZSAnICd9ICcnJwoKbWFwMSA9IFtdCndpdGggb3BlbignMTAudHh0JykgYXMgZjoKICAgIGZvciBsaW5lIGluIGYucmVhZGxpbmVzKCk6CiAgICAgICAgbWFwMS5hcHBlbmQobGlzdChsaW5lLnJlcGxhY2UoJ1xuJywgJycpKSkKCm1hcDIgPSBucC5lbXB0eSgobGVuKG1hcDEpKzIsIGxlbihtYXAxWzBdKSsyKSwgZHR5cGU9Tm9kZSkKZm9yIHkgaW4gcmFuZ2UobGVuKG1hcDIpKToKICAgIGZvciB4IGluIHJhbmdlKGxlbihtYXAyW3ldKSk6CiAgICAgICAgbWFwMlt5LCB4XSA9IE5vZGUoLTIpCmZvciB5IGluIHJhbmdlKGxlbihtYXAxKSk6CiAgICBmb3IgeCBpbiByYW5nZShsZW4obWFwMVt5XSkpOgogICAgICAgIG1hcDJbeSsxLCB4KzFdID0gTm9kZShtYXAxW3ldW3hdKQp6ZXJvcyA9IFtdCmZvciB5IGluIHJhbmdlKGxlbihtYXAxKSsxKToKICAgIGZvciB4IGluIHJhbmdlKGxlbihtYXAxWzBdKSsxKToKICAgICAgICBjdXIgPSBtYXAyW3ksIHhdCiAgICAgICAgaWYgY3VyLnZhbHVlID09IDA6CiAgICAgICAgICAgIHplcm9zLmFwcGVuZCgoeCwgeSkpCiAgICAgICAgaWYgbWFwMlt5LTEsIHhdLnZhbHVlID09IGN1ci52YWx1ZSArIDE6CiAgICAgICAgICAgIGN1ci5vdXRbMF0gPSBtYXAyW3ktMSwgeF0KICAgICAgICBpZiBtYXAyW3ksIHgrMV0udmFsdWUgPT0gY3VyLnZhbHVlICsgMToKICAgICAgICAgICAgY3VyLm91dFsxXSA9IG1hcDJbeSwgeCsxXQogICAgICAgIGlmIG1hcDJbeSsxLCB4XS52YWx1ZSA9PSBjdXIudmFsdWUgKyAxOgogICAgICAgICAgICBjdXIub3V0WzJdID0gbWFwMlt5KzEsIHhdCiAgICAgICAgaWYgbWFwMlt5LCB4LTFdLnZhbHVlID09IGN1ci52YWx1ZSArIDE6CiAgICAgICAgICAgIGN1ci5vdXRbM10gPSBtYXAyW3ksIHgtMV0KCgpkZWYgY2hlY2tfaGVhZCh4LCB5KToKICAgIGdsb2JhbCBzCiAgICBpZiAoeCwgeSkgaW4gY2hlY2tfaGVhZC52aXNpdGVkLmtleXMoKToKICAgICAgICByZXR1cm4gY2hlY2tfaGVhZC52aXNpdGVkWyh4LCB5KV0KCiAgICBub2RlID0gbWFwMlt5LCB4XQogICAgaWYgbm9kZS52YWx1ZSA9PSA5OgogICAgICAgIHMgKz0gMQogICAgICAgIHJldHVybiAxCiAgICBpZiBub2RlLnZhbHVlID09IC0yOgogICAgICAgIHJldHVybiAwCiAgICB0ID0gMAogICAgaWYgbm9kZS5vdXRbMF06CiAgICAgICAgdCArPSBjaGVja19oZWFkKHgsIHktMSkKICAgIGlmIG5vZGUub3V0WzFdOgogICAgICAgIHQgKz0gY2hlY2tfaGVhZCh4KzEsIHkpCiAgICBpZiBub2RlLm91dFsyXToKICAgICAgICB0ICs9IGNoZWNrX2hlYWQoeCwgeSsxKQogICAgaWYgbm9kZS5vdXRbM106CiAgICAgICAgdCArPSBjaGVja19oZWFkKHgtMSwgeSkKICAgIGNoZWNrX2hlYWQudmlzaXRlZFsoeCwgeSldID0gdAogICAgcmV0dXJuIHQKCmNoZWNrX2hlYWQudmlzaXRlZCA9IHt9CnMgPSAwCmZvciB6ZXJvIGluIHplcm9zOgogICAgcyArPSBjaGVja19oZWFkKHplcm9bMF0sIHplcm9bMV0pCgpwcmludChzKQo=

Both are O(area * # of trailheads). I'm not sure that a true O(area) solution is possible (not that it matters for official inputs, this code runs in a few dozen ms if you don't count importing numpy)
The only difference between part 1 and 2 is how it handles already-visited tiles.

Last edited by davidtheplatform (Dec. 11, 2024 04:52:32)

davidtheplatform

Day 11 - Discussion
This one was fast. Part 1 is really easy and a brute force solution works well, but then part 2 forces a non-brute-force solution*. I think this is the first day where you can't do brute force. It took me a few minutes to think of the right solution but implementing it isn't very hard.
This was also the first day where I didn't get both answers correct on the first try due to a few small bugs (and putting in the answer for a test case instead of the real input).
[Fun fact: this problem is almost identical to 2021 day 6 but with slightly different splitting rules.]

*unless your computer can store a quadrillion numbers
My solution (no peeking @gilbert_given_189):

d2l0aCBvcGVuKCcxMS50eHQnKSBhcyBmOgogICAgbGluZSA9IGYucmVhZCgpLnJlcGxhY2UoJ1xuJywgJycpCgpzdG9uZXMxID0gW2ludChpKSBmb3IgaSBpbiBsaW5lLnNwbGl0KCcgJyldCgpzdG9uZXMgPSB7fQpkZWYgYWRkX3N0b25lKHMsIG4pOgogICAgZ2xvYmFsIHN0b25lcwogICAgaWYgcyBub3QgaW4gc3RvbmVzOgogICAgICAgIHN0b25lc1tzXSA9IDAKICAgIHN0b25lc1tzXSArPSBuCiAgICAKZm9yIHMgaW4gc3RvbmVzMToKICAgIGFkZF9zdG9uZShzLCAxKQoKcmVzdWx0cyA9IHt9CmRlZiBhcHBseV9ydWxlczIocywgbik6CiAgICBnbG9iYWwgcmVzdWx0cwogICAgaWYgcyBpbiByZXN1bHRzLmtleXMoKToKICAgICAgICBmb3IgaSBpbiByZXN1bHRzW3NdOgogICAgICAgICAgICBhZGRfc3RvbmUoaSwgbikKICAgICAgICByZXR1cm4KICAgIGlmIHMgPT0gMDoKICAgICAgICBvID0gKDEsKQogICAgZWxpZiBsZW4oc3RyKHMpKSAlIDIgPT0gMDoKICAgICAgICBtaWRkbGUgPSBsZW4oc3RyKHMpKSAvLyAyCiAgICAgICAgbyA9IChpbnQoc3RyKHMpWzptaWRkbGVdKSwgaW50KHN0cihzKVttaWRkbGU6XSkpCiAgICBlbHNlOgogICAgICAgIG8gPSAocyAqIDIwMjQsKQogICAgcmVzdWx0c1tzXSA9IG8KICAgIGFwcGx5X3J1bGVzMihzLCBuKQoKZGVmIGZsYXR0ZW4oKToKICAgIGdsb2JhbCBzdG9uZXMKICAgIG5ld19zdG9uZXMgPSBbXQogICAgZm9yIHN0b25lIGluIHN0b25lczoKICAgICAgICBpZiB0eXBlKHN0b25lKSA9PSBpbnQ6CiAgICAgICAgICAgIG5ld19zdG9uZXMuYXBwZW5kKHN0b25lKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIG5ld19zdG9uZXMuYXBwZW5kKHN0b25lWzBdKQogICAgICAgICAgICBuZXdfc3RvbmVzLmFwcGVuZChzdG9uZVsxXSkKICAgIHN0b25lcyA9IG5ld19zdG9uZXMKCmRlZiBzdGVwKCk6CiAgICBnbG9iYWwgc3RvbmVzCiAgICB0b19hcHBseSA9IHN0b25lcy5jb3B5KCkKICAgIHN0b25lcyA9IHt9CiAgICBmb3IgaSBpbiB0b19hcHBseToKICAgICAgICBhcHBseV9ydWxlczIoaSwgdG9fYXBwbHlbaV0pCgoKZm9yIGkgaW4gcmFuZ2UoNzUpOiAjIG9yIDI1IGZvciBwYXJ0IDEKICAgIHN0ZXAoKQoKdG90YWwgPSAwCmZvciBpIGluIHN0b25lczoKICAgIHRvdGFsICs9IHN0b25lc1tpXQpwcmludCh0b3RhbCkK

Overall, it was worth staying up late for. 8/10.

Last edited by davidtheplatform (Dec. 11, 2024 05:43:40)

gilbert_given_189

Day 11 - Discussion
I thought the second part would be easy, but boy am I wrong. [I tried to use queues to slow down the memory buildup, but I don't think that's effective enough. My program is still crunching numbers.]

davidtheplatform

gilbert_given_189 wrote:
Day 11 - Discussion
I thought the second part would be easy, but boy am I wrong. [I tried to use queues to slow down the memory buildup, but I don't think that's effective enough. My program is still crunching numbers.]

How are you storing the numbers/stones?

gilbert_given_189

davidtheplatform wrote:
gilbert_given_189 wrote:
Day 11 - Discussion
I thought the second part would be easy, but boy am I wrong. [I tried to use queues to slow down the memory buildup, but I don't think that's effective enough. My program is still crunching numbers.]
How are you storing the numbers/stones?

They're on a queue, storing the stone number and depth (blinks). This is done to hopefully reduce memory buildup. But even with a single stone, I only managed to get up to 51 blinks, and the queue size is on hundreds of millions. And that is with PyPy and multiprocessing.
I know I need some sort of pruning or memoization to alleviate this, but I don't know how to implement that. I know that stones with the even digit condition makes one more stone on a blink (and that is what I'm tracking), but more than that I don't know.

Oh no, now the swap space is filling up… I had bad feelings with this…
Edit: it died. It got into 51 pages before the OOM killer stopper caught up.

Last edited by gilbert_given_189 (Dec. 11, 2024 10:54:40)

ideapad-320

davidtheplatform wrote:

ideapad-320 wrote:
Day 10
Bonus points if you can do both parts in linear time (linear to the area, not the side length).

Part 1:

aW1wb3J0IG51bXB5IGFzIG5wCgpjbGFzcyBOb2RlOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHZhbHVlKToKICAgICAgICBpZiB2YWx1ZSA9PSAnLic6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSAtMgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSBpbnQodmFsdWUpCiAgICAgICAgc2VsZi5vdXQgPSBbTm9uZSwgTm9uZSwgTm9uZSwgTm9uZV0KICAgIGRlZiBfX3N0cl9fKHNlbGYpOgogICAgICAgIHJldHVybiBmJycnIHsnfCcgaWYgc2VsZi5vdXRbMF0gZWxzZSAnICd9CnsnLScgaWYgc2VsZi5vdXRbM10gZWxzZSAnICd9e3NlbGYudmFsdWV9eyctJyBpZiBzZWxmLm91dFsxXSBlbHNlICcgJ30KIHsnfCcgaWYgc2VsZi5vdXRbMl0gZWxzZSAnICd9ICcnJwoKbWFwMSA9IFtdCndpdGggb3BlbignMTAudHh0JykgYXMgZjoKICAgIGZvciBsaW5lIGluIGYucmVhZGxpbmVzKCk6CiAgICAgICAgbWFwMS5hcHBlbmQobGlzdChsaW5lLnJlcGxhY2UoJ1xuJywgJycpKSkKICAgIAptYXAyID0gbnAuZW1wdHkoKGxlbihtYXAxKSsyLCBsZW4obWFwMVswXSkrMiksIGR0eXBlPU5vZGUpCmZvciB5IGluIHJhbmdlKGxlbihtYXAyKSk6CiAgICBmb3IgeCBpbiByYW5nZShsZW4obWFwMlt5XSkpOgogICAgICAgIG1hcDJbeSwgeF0gPSBOb2RlKC0yKQpmb3IgeSBpbiByYW5nZShsZW4obWFwMSkpOgogICAgZm9yIHggaW4gcmFuZ2UobGVuKG1hcDFbeV0pKToKICAgICAgICBtYXAyW3krMSwgeCsxXSA9IE5vZGUobWFwMVt5XVt4XSkKemVyb3MgPSBbXQpmb3IgeSBpbiByYW5nZShsZW4obWFwMSkrMSk6CiAgICBmb3IgeCBpbiByYW5nZShsZW4obWFwMVswXSkrMSk6CiAgICAgICAgY3VyID0gbWFwMlt5LCB4XQogICAgICAgIGlmIGN1ci52YWx1ZSA9PSAwOgogICAgICAgICAgICB6ZXJvcy5hcHBlbmQoKHgsIHkpKQogICAgICAgIGlmIG1hcDJbeS0xLCB4XS52YWx1ZSA9PSBjdXIudmFsdWUgKyAxOgogICAgICAgICAgICBjdXIub3V0WzBdID0gbWFwMlt5LTEsIHhdCiAgICAgICAgaWYgbWFwMlt5LCB4KzFdLnZhbHVlID09IGN1ci52YWx1ZSArIDE6CiAgICAgICAgICAgIGN1ci5vdXRbMV0gPSBtYXAyW3ksIHgrMV0KICAgICAgICBpZiBtYXAyW3krMSwgeF0udmFsdWUgPT0gY3VyLnZhbHVlICsgMToKICAgICAgICAgICAgY3VyLm91dFsyXSA9IG1hcDJbeSsxLCB4XQogICAgICAgIGlmIG1hcDJbeSwgeC0xXS52YWx1ZSA9PSBjdXIudmFsdWUgKyAxOgogICAgICAgICAgICBjdXIub3V0WzNdID0gbWFwMlt5LCB4LTFdCgoKcyA9IDAKZGVmIGNoZWNrX2hlYWQoeCwgeSk6CiAgICBnbG9iYWwgcwogICAgaWYgKHgsIHkpIGluIGNoZWNrX2hlYWQudmlzaXRlZDoKICAgICAgICByZXR1cm4KICAgIGNoZWNrX2hlYWQudmlzaXRlZC5hZGQoKHgsIHkpKQogICAgbm9kZSA9IG1hcDJbeSwgeF0KICAgIGlmIG5vZGUudmFsdWUgPT0gOToKICAgICAgICBzICs9IDEKICAgICAgICByZXR1cm4KICAgIGlmIG5vZGUudmFsdWUgPT0gLTI6CiAgICAgICAgcmV0dXJuCiAgICBpZiBub2RlLm91dFswXToKICAgICAgICBjaGVja19oZWFkKHgsIHktMSkKICAgIGlmIG5vZGUub3V0WzFdOgogICAgICAgIGNoZWNrX2hlYWQoeCsxLCB5KQogICAgaWYgbm9kZS5vdXRbMl06CiAgICAgICAgY2hlY2tfaGVhZCh4LCB5KzEpCiAgICBpZiBub2RlLm91dFszXToKICAgICAgICBjaGVja19oZWFkKHgtMSwgeSkKCmZvciB6ZXJvIGluIHplcm9zOgogICAgY2hlY2tfaGVhZC52aXNpdGVkID0gc2V0KCkKICAgIGNoZWNrX2hlYWQoemVyb1swXSwgemVyb1sxXSkKCnByaW50KHMpCg==

Part 2:

aW1wb3J0IG51bXB5IGFzIG5wCgpjbGFzcyBOb2RlOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHZhbHVlKToKICAgICAgICBpZiB2YWx1ZSA9PSAnLic6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSAtMgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHNlbGYudmFsdWUgPSBpbnQodmFsdWUpCiAgICAgICAgc2VsZi5vdXQgPSBbTm9uZSwgTm9uZSwgTm9uZSwgTm9uZV0KICAgIGRlZiBfX3N0cl9fKHNlbGYpOgogICAgICAgIHJldHVybiBmJycnIHsnfCcgaWYgc2VsZi5vdXRbMF0gZWxzZSAnICd9CnsnLScgaWYgc2VsZi5vdXRbM10gZWxzZSAnICd9e3NlbGYudmFsdWV9eyctJyBpZiBzZWxmLm91dFsxXSBlbHNlICcgJ30KIHsnfCcgaWYgc2VsZi5vdXRbMl0gZWxzZSAnICd9ICcnJwoKbWFwMSA9IFtdCndpdGggb3BlbignMTAudHh0JykgYXMgZjoKICAgIGZvciBsaW5lIGluIGYucmVhZGxpbmVzKCk6CiAgICAgICAgbWFwMS5hcHBlbmQobGlzdChsaW5lLnJlcGxhY2UoJ1xuJywgJycpKSkKCm1hcDIgPSBucC5lbXB0eSgobGVuKG1hcDEpKzIsIGxlbihtYXAxWzBdKSsyKSwgZHR5cGU9Tm9kZSkKZm9yIHkgaW4gcmFuZ2UobGVuKG1hcDIpKToKICAgIGZvciB4IGluIHJhbmdlKGxlbihtYXAyW3ldKSk6CiAgICAgICAgbWFwMlt5LCB4XSA9IE5vZGUoLTIpCmZvciB5IGluIHJhbmdlKGxlbihtYXAxKSk6CiAgICBmb3IgeCBpbiByYW5nZShsZW4obWFwMVt5XSkpOgogICAgICAgIG1hcDJbeSsxLCB4KzFdID0gTm9kZShtYXAxW3ldW3hdKQp6ZXJvcyA9IFtdCmZvciB5IGluIHJhbmdlKGxlbihtYXAxKSsxKToKICAgIGZvciB4IGluIHJhbmdlKGxlbihtYXAxWzBdKSsxKToKICAgICAgICBjdXIgPSBtYXAyW3ksIHhdCiAgICAgICAgaWYgY3VyLnZhbHVlID09IDA6CiAgICAgICAgICAgIHplcm9zLmFwcGVuZCgoeCwgeSkpCiAgICAgICAgaWYgbWFwMlt5LTEsIHhdLnZhbHVlID09IGN1ci52YWx1ZSArIDE6CiAgICAgICAgICAgIGN1ci5vdXRbMF0gPSBtYXAyW3ktMSwgeF0KICAgICAgICBpZiBtYXAyW3ksIHgrMV0udmFsdWUgPT0gY3VyLnZhbHVlICsgMToKICAgICAgICAgICAgY3VyLm91dFsxXSA9IG1hcDJbeSwgeCsxXQogICAgICAgIGlmIG1hcDJbeSsxLCB4XS52YWx1ZSA9PSBjdXIudmFsdWUgKyAxOgogICAgICAgICAgICBjdXIub3V0WzJdID0gbWFwMlt5KzEsIHhdCiAgICAgICAgaWYgbWFwMlt5LCB4LTFdLnZhbHVlID09IGN1ci52YWx1ZSArIDE6CiAgICAgICAgICAgIGN1ci5vdXRbM10gPSBtYXAyW3ksIHgtMV0KCgpkZWYgY2hlY2tfaGVhZCh4LCB5KToKICAgIGdsb2JhbCBzCiAgICBpZiAoeCwgeSkgaW4gY2hlY2tfaGVhZC52aXNpdGVkLmtleXMoKToKICAgICAgICByZXR1cm4gY2hlY2tfaGVhZC52aXNpdGVkWyh4LCB5KV0KCiAgICBub2RlID0gbWFwMlt5LCB4XQogICAgaWYgbm9kZS52YWx1ZSA9PSA5OgogICAgICAgIHMgKz0gMQogICAgICAgIHJldHVybiAxCiAgICBpZiBub2RlLnZhbHVlID09IC0yOgogICAgICAgIHJldHVybiAwCiAgICB0ID0gMAogICAgaWYgbm9kZS5vdXRbMF06CiAgICAgICAgdCArPSBjaGVja19oZWFkKHgsIHktMSkKICAgIGlmIG5vZGUub3V0WzFdOgogICAgICAgIHQgKz0gY2hlY2tfaGVhZCh4KzEsIHkpCiAgICBpZiBub2RlLm91dFsyXToKICAgICAgICB0ICs9IGNoZWNrX2hlYWQoeCwgeSsxKQogICAgaWYgbm9kZS5vdXRbM106CiAgICAgICAgdCArPSBjaGVja19oZWFkKHgtMSwgeSkKICAgIGNoZWNrX2hlYWQudmlzaXRlZFsoeCwgeSldID0gdAogICAgcmV0dXJuIHQKCmNoZWNrX2hlYWQudmlzaXRlZCA9IHt9CnMgPSAwCmZvciB6ZXJvIGluIHplcm9zOgogICAgcyArPSBjaGVja19oZWFkKHplcm9bMF0sIHplcm9bMV0pCgpwcmludChzKQo=

Both are O(area * # of trailheads). I'm not sure that a true O(area) solution is possible (not that it matters for official inputs, this code runs in a few dozen ms if you don't count importing numpy)
The only difference between part 1 and 2 is how it handles already-visited tiles.

It is possible. Think of when a path splits, each branch has the same number of ways to get to it, but when a path merges, they add. It can be done with a fixed number of cases of a area-sized array, it's O(area).

gilbert_given_189

Day 11 - Solution
I finally figured it out.

Spoilers!

Here's something I found whilst scrambling for a solution.
1
2024
20 24
2 0 2 4
4048 1 4048 8096
Notice that the 1-stone “generates” itself after 4 blinks (or depths, as I called them earlier). I thought this would be a good place to prune the search tree, since we have a recurring relation here. (at this time I still thought we have a tree to search on, thus the usage of the word “depth”)

The initial idea I had is to track “generators”. The generator adds the stone counter and registres more generators on the recurrence part. With the above example, the program registers a “power-1 generator of 1” first. Blink, the generator adds 0 to the stone counter. Blink, add 1. Blink, add 2. Blink, add 0, register “power-1 generator of 8096” and “power-2 generator of 4048” (since 1 generates 2 4048-stones). However, not all numbers are equal to each other. 175, for example, doesn't generate itself, even after ~30 blinks, so these have to be treated specially.

It is at this point the penny dropped. I don't need to track who's generating stones: the numbers already did. I could have just tracked the numbers instead, since all of them do the same thing. This lead into an iterative solution, rather than a recursive one like I was simulating, and that got me into the solution.

Chess Battle Advanced.

N3q8ryccAAQcbb5ZLgIAAAAAAAAiAAAAAAAAANJ0gxSeGbUxBk0umntbsUtBgPlZt0kl+ySrQ4mU
mPMMfo8S345H/wqWcXvySrrlN42YwR7QE9vEN9BGwC9xJFSYz2QTb0Rgjk4/p+fauSdSvXhguTWu
DOUou8Pm+hx8SIsiv09yUtpSvEJi4m3RKDp4IsOY/A4L8pbVi0evAl1YzbN3D+R9A38iJIVMIcmx
CI+/ONMvne4q+8NTzWPtwamRoYfpO7ZCplI4Kxiw0lrFDno7vFmVgsXVT/KRdCVfR25WTG5YxOx3
r6gQdJvcckR8BKzSW+Z/AFQLYi5cFzm7FbtZCFsDwP37weNlOltm+ety75YCCOrGXi3EcwdlOkav
Gbev5yCB//6Jv+kfDMsSHF+ggGaFvrd6p8yxyfjGim0iwNZRv+zFe7b9/HngsoZrnItV0mb+Tk3/
gl4mwtkNGYAbtAf1URgW1Sb2jCK5JWFwuiC/OLfbuWiHebFjCO5BGvbbcpD2ZqgL4x2PD82aevYA
HAwV/Ua2BAEc/ndydo2qJIBLvEfoXMeYZrOBHxQaeu8I8PCTtEmBSTF2NmfQglgZ3zqJlz2WEA1u
ZXSvt2MJfaIAAIEzB64P1Tu4PRck0c/kBCgFLxd2gY29G9NkeNFvOTJ/DAqMMWu+3zJIfrt6mFYa
+MAwPrDlkKIFUqJQevqucqyaASa4Du54IEK5OI3+IOpU7NVeoPTodguk84LPh22deddL9FxCjGzz
LXcTOdGczRTXMgJn7+45184AAAAXBoGwAQl+AAcLAQABIwMBAQVdABAAAAyAngoB6WNF1gAA

Encrypted using a different, much easier password. I unfortunately cannot disclose the password used in my earlier solutions, but I can repost them in plaintext, if you want it.

Last edited by gilbert_given_189 (Dec. 12, 2024 17:12:15)

mybearworld

Day 11 - Discussion

I already started late today because I was busy this morning, which definitely did not help my time today

Day 11 - Solution

As the task probably expected, for part 1 I just [kept track of the stones in an array, looping over them 25 times to get the new state]. That did not at all work for part 2. What I ended up doing was [tracking the number of times a number sliced in two instead - adding that to the length of the original array results in the correct answer.]. That doesn't require me to [keep all the stones in memory and iterate through an ever-growing array 75 times]. Combining that with [caching the function output when it's called with the same current number and amount of blinks left], which I am actually kind of surprised was better because [that has to mean that there's a lot of instances of values converging to the same thing], [it finally completed (in about 347ms)].

mybearworld

Day 11 - Discussion

Also, the input today was kind of funny - they're normally really long, and mine today was a whole 37 bytes.

gilbert_given_189

mybearworld wrote:
Day 11 - Discussion

Also, the input today was kind of funny - they're normally really long, and mine today was a whole 37 bytes.

For a good reason: you don't want to track thousands of rocks growing at an exponential rate.

ideapad-320

Day 11
I used a depth-first solution (recursion), so I never had issues with running out of RAM. My issue was it was to slow. After I fixed my code, part 2 runs in under a .1s

Last edited by ideapad-320 (Dec. 12, 2024 14:58:56)

Discuss Scratch