A puzzle a day
是一个拼图玩具。玩具包括一块拼图板和8个拼图块。拼图板上显示了1-12月份还有1-31日期,拼图块形状各不相同,玩法是先选定一个某月某日
,然后将拼图块放入拼图板中,使得最终所有其他的格子都被覆盖,而只剩下选定的某月
和某日
的格子。
我在第一眼看到这个玩具的时候,就被它的数据结构
深深吸引 -- 每一天都有一个新挑战,而且每个拼图块的样子都各不相同,利用留下的空位来传递信息,并且没有多余的空格。这是一个非常精致的谜题。
你可能会有疑问:每一天都能解出来吗?
是的!但是这个结论不是那么显然。后面你会看到,我是如何通过编程解决了这个问题。
我首先通过编程解决这个问题。然后,在我得到结果之后,我意识到这是一个很好的全栈开发
的示例项目,其中不仅有算法,还有数据库设计、数据处理与分析、web项目搭建等等技术点。所以我打算以这个玩具为主题,写一系列文章:
A puzzle a day
,实现最小功能产品(MVP)首先定义这个问题的数据结构。所谓数据结构,通俗地讲就是“如何将问题的现状用数据描述出来”。
好的数据结构可以大大简化问题的描述与分析过程。一个优秀的程序员,应当具备足够强的表达力,这是一个长期训练的过程。
我们先入为主,开一个头:
拼图板使用二维数组来描述。
* * * * * *
* * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * *
拼图块使用字母来“象形”地描述拼图块可以旋转、翻转,但是记法保持不变。
---+----+----+-----+------+-----+------+-------
CC | OO | PP | SS | sss | L | l | f
C | OO | PP | S | ss | L | l | ff
CC | OO | P | SS | | LLL | l | f
| | | | | | ll | f
---+----+----+-----+------+-----+------+-------
另外记录“空格”为“2”。那么,上面的图片中的结果就可以表示为:
L C 2 C S S
L C C C s S
L L L s s S S
O O l s P P P
O O l s f P P
O O l f f f f
2 l l