面试智力题

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

[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