面试智力题

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

[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