首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
探索世界的好奇心万岁
Udacity
网易公开课
Godel, Escher, Bach: An Eternal Golden Braid
V2EX  ›  分享发现

面试智力题

  •  
  •   felix021 · 2014-01-24 16:23:06 +08:00 · 7147 次点击
    这是一个创建于 2093 天前的主题,其中的信息可能已经有所发展或是发生改变。
    挺搞笑的,收到一封猎头邮件,附送一道智力题,说是能解出就联系她……贴出来大家齐欢乐~

    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
    56 回复  |  直到 2016-05-23 17:44:00 +08:00
        1
    zhttty   2014-01-24 16:26:13 +08:00
    我真的不是来骗答案然后去面试的……+1
        2
    lentrody   2014-01-24 16:48:15 +08:00
    其实就是4X4拼图?
        3
    c742435   2014-01-24 17:01:08 +08:00
    @lentrody 也不完全是,毕竟拼图的每一块都不一样 这个每个红的都一样。
        4
    c742435   2014-01-24 17:05:19 +08:00   ♥ 1
    其实也就C(16,8) = 12870种状态,穷举就完了。
        5
    casparchen   2014-01-24 17:27:48 +08:00
    @c742435 问题是问最短的路径。。
        6
    acros   2014-01-24 17:31:12 +08:00
    不算智力题吧,算法...
        7
    alexrezit   2014-01-24 17:34:09 +08:00


    和这个东西同理吧... 搜一下 tile game algorithm?
        8
    gongweixin   2014-01-24 18:18:35 +08:00
    @alexrezit 不太一样的, 你的这个每块都是唯一的
        9
    FrankFang128   2014-01-24 18:24:06 +08:00
    这不算智力题,已经是算法题的了。
        10
    66beta   2014-01-24 18:28:54 +08:00
    算法题,好难
        11
    c742435   2014-01-24 18:34:59 +08:00
    @casparchen 好吧 不是12870种,我忽略了光标所在的状态。我写了个示例代码 你可以看看我的思路 不过肯定有错,没跑出来……

    @66beta
    @gongweixin
    @FrankFang128 求指教
        12
    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);

    }
    }



    }
    }
    }
        13
    c742435   2014-01-24 18:36:07 +08:00
    我擦 格式全乱了,,,,
        14
    alexrezit   2014-01-24 18:37:58 +08:00
    @gongweixin
    有很大区别么?
        15
    txx   2014-01-24 18:47:59 +08:00
    BFS 很难么?
        16
    raptium   2014-01-24 19:25:36 +08:00 via iPhone
    我也收到这邮件了……
    Glow 对吧?
        17
    zhufenggood   2014-01-24 19:40:35 +08:00
        18
    felix021   2014-01-24 19:57:07 +08:00 via Android
    @raptium 对,说得很高大上,还说是paypal/linkedin什么的联合创始人的创业公司。

    @txx 不难,不过可能还需要在裸的bfs上做很多优化。
        19
    ruoyu0088   2014-01-24 20:21:25 +08:00
    就是广度搜索:我的旧电脑也不需要3秒钟。
        20
    ruoyu0088   2014-01-24 20:26:39 +08:00
        21
    ruoyu0088   2014-01-24 20:38:07 +08:00   ♥ 1
        22
    c742435   2014-01-24 20:47:18 +08:00
    a 算出来啦 是DDRRULLDRRRULLDRDLLUURURDDDR

    我的之前不小心搞成深搜了 应该是广搜
        23
    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;
    }
    }
        24
    P233   2014-01-24 20:53:11 +08:00
    算法不懂,写个模拟器给大家玩

    http://jsbin.com/ariWinuc/2
        25
    c742435   2014-01-24 21:01:38 +08:00   ♥ 1
    @P233 好像不太对呀
        26
    P233   2014-01-24 21:05:12 +08:00
    @c742435 好像有点问题,先去吃饭回来后再修改 :)
        27
    Muninn   2014-01-24 21:05:42 +08:00   ♥ 1
    @P233 哈哈 模拟器不能点怎么玩
    输入字母也太。。。
    要是实时输入字母可以动把字母记录下来也不错
        28
    felix021   2014-01-24 22:11:53 +08:00
    @c742435 先贴到gist,然后把gist的url贴上来救星了。
        29
    chairuosen   2014-01-24 22:34:47 +08:00   ♥ 2
    @P233
    把你的改了改http://jsbin.com/eZUKUPI/1
    做成游戏了 =。=
        30
    chairuosen   2014-01-24 22:40:26 +08:00
        31
    P233   2014-01-24 22:43:02 +08:00   ♥ 1
    @c742435 动画除了问题,js 控制 css 延时一直不太会写,去掉动画效果就正常了

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


    @Muninn 多谢指点,马上再完善一下 :)
        32
    P233   2014-01-24 22:45:02 +08:00
        33
    Muninn   2014-01-24 22:54:33 +08:00
    哈哈 赞一下好多人这么花精力去玩的态度
        34
    chairuosen   2014-01-24 23:03:26 +08:00
    http://jsbin.com/eZUKUPI/5
    又改了改,ESC重置
        35
    ETiV   2014-01-25 00:51:05 +08:00 via iPhone
    看上去好像魔方……

    我可以毫不费力的把一个完好的魔方拧出乱七八糟的样子
        36
    nan0kai   2014-01-25 08:18:13 +08:00
    @chairuosen FF显示畸形
        37
    P233   2014-01-25 08:42:31 +08:00   ♥ 1
    @c742435 又折腾了一下 DDRRULLDRRRULLDRDLLUURURDDDR 好像不对(之前写的有点问题),最后白框在 “右下角” 而不是左上角。

    两个版本

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

    加了动画效果的按键版本,很不完善,指令不能输入太快,最好也不要出界,不知如何 fix,请大家多指点
    http://jsbin.com/ariWinuc/7/
        38
    liushuaikobe   2014-01-25 10:32:19 +08:00
    我也收到这封邮件了 +1
        39
    chairuosen   2014-01-25 12:57:07 +08:00   ♥ 1
    @nan0kai box-sizing的原因。。好了 http://jsbin.com/eZUKUPI/11/
        40
    felix021   2014-01-25 17:39:10 +08:00
    @c742435 你这个答案形状上确实是一样了,但是旋转了180度吧?

    我做出来的最短路径是32步:RRDLLURRRDLLURDDLDRURDLULLDRUULU
        41
    c742435   2014-01-25 18:08:43 +08:00
    @felix021 en,我的代码中有一句
    if(0x5a5a == v && 0 == p)
    替换为
    if(0x5a5a == v && 15 == p)
    就可以得到正确答案了~
        42
    chairuosen   2014-01-25 18:42:57 +08:00
    @P233 动画过程加个锁,按键没锁再执行
        43
    sgissb1   2014-01-25 19:13:35 +08:00
    类似华容道的算法题,这要怎么推算才能找到规律。。。。
        44
    doskoi   2014-01-28 03:23:27 +08:00
    @ruoyu0088 思路是对的,你的电脑只要3秒应该是因为后面的记录都出现过在visited里了,因为你的copy_bit只操作了b2, b1的状态没改变,所以后面的0和1的count都乱了。
        45
    ruoyu0088   2014-01-28 06:24:49 +08:00
    @doskoi 你是说我的程序结果不正确吗?你再想想为什么不用操作b1的状态。
        46
    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分钟。

    不对或在不优的地方请指出,谢谢。
        47
    allenhsu   2014-01-28 12:09:33 +08:00
    弱弱地飘过,我是这家公司的,当初应聘我用的 bitmap + 一个 currentPos 来描述状态的,大家有兴趣欢迎投简历啊,可以联系我或者直接到官网投简历。

    https://www.glowing.com/jobs

    PS:看来要换题了
        48
    felix021   2014-01-28 12:11:56 +08:00
    @allenhsu 赞你,不过这是一道题用到死的节奏啊?好像大家都是这个题。。
        49
    allenhsu   2014-01-28 12:59:05 +08:00
    @felix021 这个只是个提交简历的门槛,基本上对后面的面试不会有很大影响。
        50
    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了。
        51
    ruoyu0088   2014-01-28 19:47:35 +08:00
    @doskoi 那个代码不做任何修改,直接复制粘贴运行,应该能得到最优解吧,我的旧电脑上不到3秒。
        52
    doskoi   2014-01-29 14:12:08 +08:00
    @ruoyu0088 瞭了,我在ruby里重新打了一遍,性能低很多。。
        53
    songkaiape   2016-05-23 17:31:30 +08:00
    挖坟,楼主这一句我没看懂, visited = set(start_node['state']) ,这里应该意思是用列表存储访问过的状态吧,我觉得应该使用列表, visited=[],visited.append(start_node['state']),但是神奇的是楼主的代码和我改了之后的跑的结果一样。。。而且楼主之前的代码比我改了之后的快很多,不是很懂求解释
        54
    songkaiape   2016-05-23 17:37:16 +08:00
    @songkaiape 好吧=。=我发现了。。其实这个 visited 并没有用来当作判断的条件。。。
        55
    songkaiape   2016-05-23 17:38:14 +08:00
    @songkaiape 所以按照楼主的意思其实还是应该用 List 才对。不过用了反而性能下降了。。
        56
    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 的用法,谢谢楼主分享
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2288 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 34ms · UTC 14:27 · PVG 22:27 · LAX 07:27 · JFK 10:27
    ♥ Do have faith in what you're doing.