面试智力题

[felix021]

挺搞笑的，收到一封猎头邮件，附送一道智力题，说是能解出就联系她……贴出来大家齐欢乐～

You must solve this puzzle to apply
There're 7 red tiles, 8 blue titles and one white title in a 4 x 4 plane. We could only move the white tile. When moving it, the white tile swaps the position with the adjacent tile. L, R, U, D are corresponding to four directions which the tile could be moved to (Left, Right, Up, Down) For example, starting from configuration (S), by the move sequence RDRDLwe reach the configuration (E). Now, starting from configuration (S), find the shortest way to reach configuration (T).



What is the move sequence of the path ?

p.s. 我真的不是来骗答案然后去面试的……

[c742435]

@felix021 en,我的代码中有一句
if(0x5a5a == v && 0 == p)
替换为
if(0x5a5a == v && 15 == p)
就可以得到正确答案了~

[chairuosen]

@P233 动画过程加个锁，按键没锁再执行

[sgissb1]

类似华容道的算法题，这要怎么推算才能找到规律。。。。

[doskoi]

@ruoyu0088 思路是对的，你的电脑只要3秒应该是因为后面的记录都出现过在visited里了，因为你的copy_bit只操作了b2, b1的状态没改变，所以后面的0和1的count都乱了。

[ruoyu0088]

@doskoi 你是说我的程序结果不正确吗？你再想想为什么不用操作b1的状态。

[doskoi]

@ruoyu0088 我bitwise和python都不算熟悉，请赐教。

你的code，我把target换成了图E的状态，也就是文中RDRDL
target_status = (9, int("0011011100010011", 2))
按照算法应该会返回DRRDL。但是我从return route2和visited.add(status2)的输出来看，不是这样的。

在copy_bit中，我试着重新判断了下b1和b2的值，并且他们一个为0一个不为0的情况下，根据是b1或b2的情况不同，分别把他们设置成0何1，做到模拟移动方块的操作。这样再来运算即可得出图E和图T的状态，分别0.2秒和25分钟。

不对或在不优的地方请指出，谢谢。

[allenhsu]

弱弱地飘过，我是这家公司的，当初应聘我用的 bitmap + 一个 currentPos 来描述状态的，大家有兴趣欢迎投简历啊，可以联系我或者直接到官网投简历。

https://www.glowing.com/jobs

PS：看来要换题了

[felix021]

@allenhsu 赞你，不过这是一道题用到死的节奏啊？好像大家都是这个题。。

[allenhsu]

@felix021 这个只是个提交简历的门槛，基本上对后面的面试不会有很大影响。

[ruoyu0088]

@doskoi 所以我的程序中的target_status是两个：

target_status = {(0, int("1010010110100101",2)),
(0, int("1010010110100100",2))}

你也应该写两个target_status。

当然修改一下copy_bit，把b1对应的比特设置为0，就不需要两个target了。

[ruoyu0088]

@doskoi 那个代码不做任何修改，直接复制粘贴运行，应该能得到最优解吧，我的旧电脑上不到3秒。

[doskoi]

@ruoyu0088 瞭了，我在ruby里重新打了一遍，性能低很多。。

[songkaiape]

挖坟，楼主这一句我没看懂， visited = set(start_node['state']) ，这里应该意思是用列表存储访问过的状态吧，我觉得应该使用列表， visited=[],visited.append(start_node['state'])，但是神奇的是楼主的代码和我改了之后的跑的结果一样。。。而且楼主之前的代码比我改了之后的快很多，不是很懂求解释

[songkaiape]

@songkaiape 好吧=。=我发现了。。其实这个 visited 并没有用来当作判断的条件。。。

[songkaiape]

@songkaiape 所以按照楼主的意思其实还是应该用 List 才对。不过用了反而性能下降了。。

[songkaiape]

@songkaiape 哦不对=。=好像只有第一句是错误的，用 set 的话应该是这样 visited = set(),visited.add(start_node['state']) ,直接 visited = set(start_node['state'])会变成{'0','2','1'}而不是{‘ 2011001100110011 ’}，我的 py3 不知道是不是环境一样。不过学到了 SET 的用法，谢谢楼主分享