V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
felix021
V2EX  ›  分享发现

面试智力题

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

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


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

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

    }
    }



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

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

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

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

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


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

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

    两个版本

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

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

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

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

    https://www.glowing.com/jobs

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