～技术宅真可怕～#1 - 2023-12-13 22:31
NekoNull
虽然进度已经过半了才想起来写，不过还是推荐各位班友都来一起玩！
（如果真的去玩了，欢迎在本贴后回复自己的体验/疑惑/想法！）
官网：https://adventofcode.com/2023
## 这是什么？
- （官网）：Advent of Code 是一个编程谜题的圣诞日历，适合各种技能水平和技能水平的人解决，可以用任何你喜欢的编程语言来完成。人们用它们作为面试准备、公司培训、大学课程作业、练习问题、速度比赛，或者互相挑战。
- （人话）：可以看作圣诞版leetcode；在12/1~12/25的期间内，每天（UTC-5 0点，UTC+8 13点）会放出一个题目；每个题目分为两个部分，第一部分相对简单，第二部分会更深入也会更难；每完成一个部分就会获得一个小星星⭐（one gold star）
## 参加有条件吗？
- （官网）：参与者不需要计算机科学背景，只需要一点编程知识和一些问题解决能力就可以走得很远。也不需要高端电脑；每个问题都有一个解决方案，在十年前的硬件上最多可以在15秒内完成。
- （我自己的经验）：我是今年首次参加，体感如果你学过任何一门计算机语言，有基础的编程知识，应该就可以开始玩了；几乎所有题目的第一部分都可以暴力解出来，第二部分就可能需要一些技巧。
## 和其他的 OJ（Online Judge）有什么不同？
- 提交结果而不是代码：每个部分的结果都是一个数字，只需要提交这个数字就可以了
- 没有时间/内存限制：如果想不到高效的解法，暴力硬算也未尝不可
- 没有编程语言限制：甚至可以用 Excel / Minecraft 或者任何图灵完备的工具来完成
## 这是比赛吗？
- 如果你想体验激烈的比赛，官网有个排行榜，每天全球前100位解出题目的玩家可以获得积分
- 但如果你只是想玩，完全当作单机游戏也没问题，不需要和任何人比较；题目一旦放出就会一直存在（12/25最后一天结束之后也是如此），今天做不出来也可以之后再试试
## 我卡关了
- 这很正常
- 可以选择死磕：样例结果一致吗？有没想到的边界条件？手动构造几个更强的输入？
- 也可以参加讨论：官方 SubReddit 通常会很有帮助，油管上也会有人放出讲解视频，Github 上也会有人同步更新自己的解答
---
12/25：完结撒花 🎄
自己的解法扔 Github 了（超级糟糕的代码，建议不要参考）
另外还排了一个非常主观的本年度题目难度排行榜：
难度 / 题目（所在天数）
- SSR （没做出来）：21
- SR （做了很久 / 暴力解 / 看了思路）：5, 8, 10, 12, 16, 17, 18, 19, 20, 23, 24, 25
- R（得仔细想想）：1, 3, 13, 14
- N（有手就行）：2, 6, 7, 9, 11, 15, 22
最后祝各位班友 2023 圣诞快乐 & 2024 新年快乐！
（如果真的去玩了，欢迎在本贴后回复自己的体验/疑惑/想法！）
官网：https://adventofcode.com/2023
## 这是什么？
- （官网）：Advent of Code 是一个编程谜题的圣诞日历，适合各种技能水平和技能水平的人解决，可以用任何你喜欢的编程语言来完成。人们用它们作为面试准备、公司培训、大学课程作业、练习问题、速度比赛，或者互相挑战。
- （人话）：可以看作圣诞版leetcode；在12/1~12/25的期间内，每天（UTC-5 0点，UTC+8 13点）会放出一个题目；每个题目分为两个部分，第一部分相对简单，第二部分会更深入也会更难；每完成一个部分就会获得一个小星星⭐（one gold star）
## 参加有条件吗？
- （官网）：参与者不需要计算机科学背景，只需要一点编程知识和一些问题解决能力就可以走得很远。也不需要高端电脑；每个问题都有一个解决方案，在十年前的硬件上最多可以在15秒内完成。
- （我自己的经验）：我是今年首次参加，体感如果你学过任何一门计算机语言，有基础的编程知识，应该就可以开始玩了；几乎所有题目的第一部分都可以暴力解出来，第二部分就可能需要一些技巧。
## 和其他的 OJ（Online Judge）有什么不同？
- 提交结果而不是代码：每个部分的结果都是一个数字，只需要提交这个数字就可以了
- 没有时间/内存限制：如果想不到高效的解法，暴力硬算也未尝不可
- 没有编程语言限制：甚至可以用 Excel / Minecraft 或者任何图灵完备的工具来完成
## 这是比赛吗？
- 如果你想体验激烈的比赛，官网有个排行榜，每天全球前100位解出题目的玩家可以获得积分
- 但如果你只是想玩，完全当作单机游戏也没问题，不需要和任何人比较；题目一旦放出就会一直存在（12/25最后一天结束之后也是如此），今天做不出来也可以之后再试试
## 我卡关了
- 这很正常
- 可以选择死磕：样例结果一致吗？有没想到的边界条件？手动构造几个更强的输入？
- 也可以参加讨论：官方 SubReddit 通常会很有帮助，油管上也会有人放出讲解视频，Github 上也会有人同步更新自己的解答
---
12/25：完结撒花 🎄
自己的解法扔 Github 了（超级糟糕的代码，建议不要参考）
另外还排了一个非常主观的本年度题目难度排行榜：
难度 / 题目（所在天数）
- SSR （没做出来）：21
- SR （做了很久 / 暴力解 / 看了思路）：5, 8, 10, 12, 16, 17, 18, 19, 20, 23, 24, 25
- R（得仔细想想）：1, 3, 13, 14
- N（有手就行）：2, 6, 7, 9, 11, 15, 22
最后祝各位班友 2023 圣诞快乐 & 2024 新年快乐！
（说来惭愧，毕业之后算法几乎已经忘光了，自己整了一个小时没整出来，最后求助copliot chat才做出来，作为程序员有些失败）
虽然数据的确很特殊（中心开始，边缘/中心轴线没有障碍），但是计算的时候要分很多块，太容易 off by 1了，就算出错了估计都查不出来...
据说还真的可以二次拟合？但是需要很特定的x（65, 65+131, 65+131*2）
P.S. 看了别人的题解，可以观察到题目中大部分位置其实都只有一个可选的前进方向，在图上可以把这类点忽略（or 合并，不太确定 coalesce 怎么翻译合适），这样可以大幅减小最后需要暴力的图上边的数量
P.S. 看了看别人的题解，基本上 p2 都是用数学库解方程了（理论上可以手写高斯消元？）
看了一下输入一共只有500个规则，也就是最多将数轴分成500段，每个段选一个点暴力，就从4000^4降到500^4种可能，大概4e10这个量级，跑个几分钟应该就行了，最后跑了15分钟搞出了结果。还有一点上面的口胡，似乎符号执行模拟的时候复杂度已经不低于这个暴力，没写不清楚跑起来是什么样的。
（翻了翻reddit上的讨论，有人说通解可能是个PSPACE级别的问题）
确实也只能依赖数据搞一搞（
回想起以前比赛的时候，经典上来口胡一个非常复杂的做法，然后占着机时半天调不出来
中间去试了一下 z3 玩玩，问了问 GPT，它给的代码无法排除掉子循环（也就是它会输出类似，1-2-3，4-5-4，6-7-6，这样的东西）。
好像没有之前玩过的解数独类似的东西的建模那么trivial，有点不太懂。
我的实现：GitHub。
我也留一个主观的难度分段（可能参照我退役几年前的 XCPC 和省赛命题经验）：
- Medium Hard: 21
- Medium: 18, 19, 22
- Medium Easy: 5, 7, 10, 12, 14, 23, 25
- Easy (简单思维、简单实现或简单算法的模板): 3, 8, 11, 16, 17
- Very Easy (对着题意模拟): 1, 2, 4, 6, 9, 15
- 排除: 13（题面写的看不懂），20（需要参考题面未指明的数据性质），24（过圣诞节摸了，不想做）