面试智力题 - V2EX

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3962 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

第 1 条附言 · 2014-01-24 22:14:04 +08:00

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

第 2 条附言 · 2014-01-25 17:52:54 +08:00

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

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

第 3 条附言 · 2014-01-25 18:05:12 +08:00

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

tile

Configuration

white

56 条回复 • 2016-05-23 17:44:00 +08:00

zhttty

2014-01-24 16:26:13 +08:00

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

lentrody

2014-01-24 16:48:15 +08:00

其实就是4X4拼图？

c742435

2014-01-24 17:01:08 +08:00

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

c742435

2014-01-24 17:05:19 +08:00

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

casparchen

2014-01-24 17:27:48 +08:00

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

acros

2014-01-24 17:31:12 +08:00

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

alexrezit

2014-01-24 17:34:09 +08:00

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

gongweixin

2014-01-24 18:18:35 +08:00

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

FrankFang128

2014-01-24 18:24:06 +08:00

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

66beta

2014-01-24 18:28:54 +08:00

算法题，好难

c742435

2014-01-24 18:34:59 +08:00

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

@66beta
@gongweixin
@FrankFang128 求指教

c742435

2014-01-24 18:35:52 +08:00

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

2014-01-24 18:36:07 +08:00

我擦格式全乱了，，，，

alexrezit

2014-01-24 18:37:58 +08:00

@gongweixin
有很大区别么?

txx

2014-01-24 18:47:59 +08:00

BFS 很难么？

raptium

2014-01-24 19:25:36 +08:00 via iPhone

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

zhufenggood

2014-01-24 19:40:35 +08:00

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

felix021

2014-01-24 19:57:07 +08:00 via Android

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

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

ruoyu0088

2014-01-24 20:21:25 +08:00

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

ruoyu0088

2014-01-24 20:26:39 +08:00

https://gist.github.com/8596346

ruoyu0088

2014-01-24 20:38:07 +08:00

这个是代码：

https://gist.github.com/8596484

c742435

2014-01-24 20:47:18 +08:00

a 算出来啦是DDRRULLDRRRULLDRDLLUURURDDDR

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

c742435

2014-01-24 20:49:36 +08:00

话说怎么贴代码呢？在贴一次乱的吧不好意思
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

2014-01-24 20:53:11 +08:00

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

http://jsbin.com/ariWinuc/2

c742435

2014-01-24 21:01:38 +08:00

@P233 好像不太对呀

P233

2014-01-24 21:05:12 +08:00

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

Muninn

2014-01-24 21:05:42 +08:00

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

felix021

2014-01-24 22:11:53 +08:00

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

chairuosen

2014-01-24 22:34:47 +08:00

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

chairuosen

2014-01-24 22:40:26 +08:00

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

P233

2014-01-24 22:43:02 +08:00

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

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

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

P233

2014-01-24 22:45:02 +08:00

@chairuosen 赞

Muninn

2014-01-24 22:54:33 +08:00

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

chairuosen

2014-01-24 23:03:26 +08:00

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

ETiV

2014-01-25 00:51:05 +08:00 via iPhone

看上去好像魔方……

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

nan0kai

2014-01-25 08:18:13 +08:00

@chairuosen FF显示畸形

P233

2014-01-25 08:42:31 +08:00

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

两个版本

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

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

liushuaikobe

2014-01-25 10:32:19 +08:00

我也收到这封邮件了 +1

chairuosen

2014-01-25 12:57:07 +08:00

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

felix021

2014-01-25 17:39:10 +08:00

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

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

c742435

2014-01-25 18:08:43 +08:00

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

chairuosen

2014-01-25 18:42:57 +08:00

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

sgissb1

2014-01-25 19:13:35 +08:00

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

doskoi

2014-01-28 03:23:27 +08:00

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

ruoyu0088

2014-01-28 06:24:49 +08:00

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

doskoi

2014-01-28 11:58:07 +08:00

@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

2014-01-28 12:09:33 +08:00

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

https://www.glowing.com/jobs

PS：看来要换题了

felix021

2014-01-28 12:11:56 +08:00

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

allenhsu

2014-01-28 12:59:05 +08:00

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

ruoyu0088

2014-01-28 19:40:51 +08:00

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

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

你也应该写两个target_status。

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

ruoyu0088

2014-01-28 19:47:35 +08:00

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

doskoi

2014-01-29 14:12:08 +08:00

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

songkaiape

2016-05-23 17:31:30 +08:00

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

songkaiape

2016-05-23 17:37:16 +08:00

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

songkaiape

2016-05-23 17:38:14 +08:00

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

songkaiape

2016-05-23 17:44:00 +08:00

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