面试智力题

[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. 我真的不是来骗答案然后去面试的……

嗯 准确一点说 的确是算法题，单纯靠脑力计算出路径不太现实，不过因为是发在码农论坛，就没说得那么严谨了。。。

本来想用C写个基于bit field来状态压缩的，后来算了下，发现也就2^16 * 16种状态，计算量还挺小，干脆用python随便写写了。

我做出来的最短路径是32步：RRDLLURRRDLLURDDLDRURDLULLDRUULU，你呢？

39L @chairuosen 同学基于@P233的代码改造出来的游戏最终版，供参考 http://jsbin.com/eZUKUPI/11

[zhttty]

我真的不是来骗答案然后去面试的……+1

[lentrody]

其实就是4X4拼图？

[c742435]

@lentrody 也不完全是，毕竟拼图的每一块都不一样 这个每个红的都一样。

[c742435]

其实也就C(16,8) = 12870种状态，穷举就完了。

[casparchen]

@c742435 问题是问最短的路径。。

[acros]

不算智力题吧，算法...

[alexrezit]

和这个东西同理吧... 搜一下 tile game algorithm?

[gongweixin]

@alexrezit 不太一样的， 你的这个每块都是唯一的

[FrankFang128]

这不算智力题，已经是算法题的了。

[66beta]

算法题，好难

[c742435]

@casparchen 好吧 不是12870种，我忽略了光标所在的状态。我写了个示例代码 你可以看看我的思路 不过肯定有错，没跑出来……

@66beta
@gongweixin
@FrankFang128 求指教

[c742435]

package {

import flash.display.Sprite;
import flash.text.TextField;

public class Untitled extends Sprite {
public function Untitled() {

var a:Array = new Array;
a[0xf00ff] = "";

var counter:int = 0;
work(0x00ff, 15, "");
trace(counter);

function work(v:uint, p:int, s:String):void
{
counter += 1;
if(0 == counter % 100)
{
trace(counter);
}
if(0x5858 == v)
{
trace("a[" + 0x5858 + "]=" + a[v]);
}

if(s.length > 600)
return;

if((p & 3) < 3)
{
test(1, "U");
}

if((p & 3) > 0)
{
test(-1, "D");
}

if(p < 12)
{
test(4, "L");
}

if(p > 3)
{
test(-4, "R");
}

function test(n:int, sadd:String):void
{
var tempV:uint = calc(n);
var tempS:String;
var index:int = tempV | ((p + n) << 16);
if(!a[index])
{
tempS = s + sadd;
a[index] = tempS;
work(tempV, p + n, tempS);
}
}

function calc(n:int):uint
{
var fromMask:int = 1 << p;//原有位置被置为目标位置的值
var toMask:int = 1 << (p + n);//目标位置被置为0（光标位置总是为0）

return v & (0xffff ^ toMask) & (0xffff ^ fromMask) | ( (v & toMask ) && fromMask);

}
}



}
}
}

[c742435]

我擦 格式全乱了，，，，

[alexrezit]

@gongweixin
有很大区别么?

[txx]

BFS 很难么？

[raptium]

我也收到这邮件了……
Glow 对吧？

[zhufenggood]

https://glowing.com/jobs/mobiledeveloper#mtop

[felix021]

@raptium 对，说得很高大上，还说是paypal/linkedin什么的联合创始人的创业公司。

@txx 不难，不过可能还需要在裸的bfs上做很多优化。

[ruoyu0088]

就是广度搜索：我的旧电脑也不需要3秒钟。

[ruoyu0088]

https://gist.github.com/8596346

[ruoyu0088]

这个是代码：

https://gist.github.com/8596484

[c742435]

a 算出来啦 是DDRRULLDRRRULLDRDLLUURURDDDR

我的之前不小心搞成深搜了 应该是广搜

[c742435]

话说怎么贴代码呢？在贴一次乱的吧 不好意思
package {

import flash.display.Sprite;
import flash.text.TextField;

public class Untitled extends Sprite {
public function Untitled() {

var a:Array = new Array;
a[0xf00ff] = "";

var task:Vector.<VPS> = new Vector.<VPS>;
task.push(new VPS(0x00ff, 15, ""));

var counter:int = 0;

while(task.length)
{
work();
}

function work():void
{

if(!task.length)
{
return;
}

var vps:VPS = task.shift();
var v:uint = vps.v, p:int = vps.p, s:String = vps.s;

if(0x5a5a == v && 0 == p)
{
trace("a[" + ((p << 16) | v) + "]=" + s);
}

if((p & 3) < 3)
{
test(1, "U");
}

if((p & 3) > 0)
{
test(-1, "D");
}

if(p < 12)
{
test(4, "L");
}

if(p > 3)
{
test(-4, "R");
}

function test(n:int, sadd:String):void
{
var tempV:uint = calc(n);
var tempS:String;
var index:int = tempV | ((p + n) << 16);
if(!a[index])
{
tempS = s + sadd;
a[index] = tempS;

task.push(new VPS(tempV, p+n, tempS));
}
}

function calc(n:int):uint
{
var fromMask:int = 1 << p;//原有位置被置为目标位置的值
var toMask:int = 1 << (p + n);//目标位置被置为0（光标位置总是为0）

return v & (0xffff ^ toMask) & (0xffff ^ fromMask) | ( (v & toMask ) && fromMask);

}
}



}
}
}



class VPS
{
var v:uint;
var p:int;
var s:String;
function VPS(v:uint, p:int, s:String)
{
this.v = v;
this.p = p;
this.s = s;
}
}

[P233]

算法不懂，写个模拟器给大家玩

http://jsbin.com/ariWinuc/2

[c742435]

@P233 好像不太对呀

[P233]

@c742435 好像有点问题，先去吃饭回来后再修改 :)

[Muninn]

@P233 哈哈 模拟器不能点怎么玩
输入字母也太。。。
要是实时输入字母可以动把字母记录下来也不错

[felix021]

@c742435 先贴到gist，然后把gist的url贴上来救星了。

[chairuosen]

@P233
把你的改了改http://jsbin.com/eZUKUPI/1
做成游戏了 =。=

[chairuosen]

@chairuosen 咦？ 连接呢 http://jsbin.com/eZUKUPI/1

[P233]

@c742435 动画除了问题，js 控制 css 延时一直不太会写，去掉动画效果就正常了

http://jsbin.com/ariWinuc/3/


@Muninn 多谢指点，马上再完善一下 :)

[P233]

@chairuosen 赞

[Muninn]

哈哈 赞一下好多人这么花精力去玩的态度

[chairuosen]

http://jsbin.com/eZUKUPI/5
又改了改，ESC重置

[ETiV]

看上去好像魔方……

我可以毫不费力的把一个完好的魔方拧出乱七八糟的样子

[nan0kai]

@chairuosen FF显示畸形

[P233]

@c742435 又折腾了一下 DDRRULLDRRRULLDRDLLUURURDDDR 好像不对（之前写的有点问题），最后白框在 “右下角” 而不是左上角。

两个版本

去掉了动画，输入指令显示最终结果
http://jsbin.com/ariWinuc/8/

加了动画效果的按键版本，很不完善，指令不能输入太快，最好也不要出界，不知如何 fix，请大家多指点
http://jsbin.com/ariWinuc/7/

[liushuaikobe]

我也收到这封邮件了 +1

[chairuosen]

@nan0kai box-sizing的原因。。好了 http://jsbin.com/eZUKUPI/11/

[felix021]

@c742435 你这个答案形状上确实是一样了，但是旋转了180度吧？

我做出来的最短路径是32步：RRDLLURRRDLLURDDLDRURDLULLDRUULU

[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 的用法，谢谢楼主分享