我喜欢利用业余时间研究算法,以提高我的算法设计技能。我将Jane Street的月度难题作为我的“每月挑战”。我曾经开发过算法来解决他们十月的谜题,并通过手动解决了他们的11月难题。
我通过手动解决了他们11月的难题(Hooks #6),但这只是因为我不确定如何计算地解决涉及带有编号边框的网格问题(以及未来的难题)。我不确定如何为这种类型的问题打好基础。
例如,他们的许多问题都涉及到一个带有边框数字的二维网格。此外,一个经常出现的主题是,无论在网格中放置什么,都必须满足涉及从网格的不同侧面观察该数字的多个条件。例如,如果我有以下2乘2网格,其边界外有4个数字:
我通过手动解决了他们11月的难题(Hooks #6),但这只是因为我不确定如何计算地解决涉及带有编号边框的网格问题(以及未来的难题)。我不确定如何为这种类型的问题打好基础。
例如,他们的许多问题都涉及到一个带有边框数字的二维网格。此外,一个经常出现的主题是,无论在网格中放置什么,都必须满足涉及从网格的不同侧面观察该数字的多个条件。例如,如果我有以下2乘2网格,其边界外有4个数字:
_ _
5| | 45
5|_ _| 15
Place four numbers in the grid such that, when you
look at the grid from the left, at least one number
in that row is the border number.
In the case of the top left of the 2 by 2 grid,
looking at it from the left means the number 5 must be in either (0,0) or (0,1).
In addition, when looking at that row from the right, the product
of the numbers in the row must equal the boundary number on the right.
In the case of the top right of the 2 by 2 grid,
looking at it from the right means the number 9 must be in either (0,0)
or (0,1), as 9 * 5 = 45.
Hence, the first row in the 2 by 2 grid can either be 5 and 9, or 9 and 5.
解决这个问题的其中一种方法是手动操作:
(0,0) = 5, (0,1) = 9, (1,0) = 5, (1,1) = 3
但是我该如何进行计算?
我该如何将这些基于网格位置的具有不同条件的问题转换为代码?
谢谢!