《编程之美》上面的蚂蚁爬杆的算法

在论坛上看到别人在讨论编程之美上面的蚂蚁爬杆的算法，题目是改编的，我是看了改编后的题目之后才在别人的回复中知道这题目的原题在《编程之美》这本书上

下面是改编后的题目，

Problem
有一根m厘米的细木杆，杆上非始末端不同位置存在k个蚂蚁。蚂蚁的目标是全部从木杆上离开，但在细木杆上只会朝前走或调头而不能后退。当任意两只蚂蚁碰头时，会同时调头朝反方向走。假定木杆很细，只能同时通过一只蚂蚁；蚂蚁长度可忽略且每秒钟可以走1厘米的距离。

Input
本题给定数据为两行，第一行是整数m（25<m<100）；
第二行为k个整数（2<=k<=5），分别代表k个蚂蚁的位置；值代表离木杆始端的距离，若为正数则蚂蚁开始时头朝向末端，为负数则蚂蚁开始时头朝向始端。

Output
对于给定数据和规则，输出蚂蚁全部离开需要的秒数t及最后离开蚂蚁的初始位置值k（带正负号），用空格分开。

Sample Input
27
3 -7 11 -17 23

Sample Output
24 11

原题目是给定，杆长为27和蚂蚁的位置3，7，11，17，23，但是蚂蚁的方向未知，求所有蚂蚁离开的最小时间和所有蚂蚁离开的最大时间。

看到这个题目，我的第一想法是模拟整个过程，从而得知最后一只蚂蚁离开的时间，但是我不甘于只实现找出最后一次蚂蚁离开的时间，所以写了段能够计算每只蚂蚁离开的时间的代码，这段代码没有算法可言，纯模拟整个过程，代码如下：

def ant(m, *position):
    t = 0
    p = {i:i for i in position}
    temp = []
    result = []
    while True:
        t += 1
        p= {k:v+1 for k,v in p.items()}
        for i in tuple(p.keys()):
            if abs(p[i]) in (0,m):
                result.append((i,t))
                p.pop(i)
        if p == {}:
            return result
        temp = [abs(i) for i in p.values()]
        for k,v in p.items():
            if temp.count(abs(v)) == 2:
                p[k] = -v
print(ant(27,3,-7,11,-17,23))

→[(23, 4), (3, 7), (-17, 16), (-7, 17), (11, 24)]

后来看了别人在论坛里的回复才知道有《灵魂算法》，即蚂蚁是否调头，都跟最后一次蚂蚁离开的的时间无关，因此可以认为蚂蚁能够穿过对方而不需要调头，因此称这为灵魂算法。上面这段代码在计算时也没有考虑到两只蚂蚁可能在非整数位置相遇的情况，应该说没有准确模拟整个过程，这段代码的计算结果也只有第一只蚂蚁离开的时间和最后一只蚂蚁离开的时间是对的，其余的全不对。

考虑到蚂蚁可能在非整数位置相遇，并且蚂蚁在整数时时刻必然在整数位置，我又加了一段代码，在整数时刻判断当两只蚂蚁对向行走且距离小于2时，两只蚂蚁互换位置，这样一来在下一个整数时刻时，两只蚂蚁一定还在整数时刻，它们的位置还是正确的，虽然在这个过程中他们穿过了对方的身体，但这样的效果就好像他们碰到对方后调头了一样。

蚂蚁为什么在整数时刻一定在整数位置？简单证明以备忘，初始位置时，所有的蚂蚁都在整数位置，1秒种移动一厘米，两只蚂蚁如果要在非整数位置相遇，那么他们一定在前一个整数时候处于相邻的两个整数位置，如16，－17，这样一来他们才有可能在非整数位置相遇，考虑到所有蚂蚁的速度都相等，其实他们只能16.5这样的位置相遇。
下面这段代码中有考虑到蚂蚁可能在16.5这样的位置相遇，所以程序中有判断当两只蚂蚁对向且距离小于2时互换位置，如a,b两只蚂蚁的初始位置和方向分别为16和－17，他们会在16.5的位置相遇然后调头，在下一秒时，a,b的位置和方向就是-16和17。
如果在进行下一秒的移动前，交换16和－17，，交换后a,b的位置分别为－17和16，在下一秒移动后a,b分别+1，其位置就是-16和17，看到了吧，交换位置就是碰头然后调头的简捷算法。

def ant(m, *position):
    t = 0
    p = {i:i for i in position}
    temp = []
    result = []
    x = []
    while True:
        t += 1
        x = sorted(((k,v) for k,v in p.items()), key = lambda j: abs(j[1]))
        for i in range(len(x)-1):
            if x[i][1] > 0 and x[i+1][1] < 0 and x[i+1][1] + x[i][1] > -2:
                p[x[i][0]] = x[i+1][1]
                p[x[i+1][0]] = x[i][1]
        p = {k:v+1 for k,v in p.items()}
        for i in tuple(p.keys()):
            if abs(p[i]) in (0,m):
                result.append((i,t))
                p.pop(i)
        if p == {}:
            return result
        temp = [abs(i) for i in p.values()]
        for k,v in p.items():
            if temp.count(abs(v)) == 2:
                p[k] = -v

print(ant(27,3,-7,11,-17,23))

→ [(23, 4), (-7, 7), (-17, 16), (3, 17), (11, 24)]

上面这个想法虽对，但是代码却写得不正确，唉，功夫还不够还得练习，但是没功夫调试了，因为已经有了更好的算法。

def ant(m, *args):
    p = sorted(args, key = abs)
    t = [-i for i in p if i<0] + [m - i for i in p if i >0]
    return sorted((k,v) for k,v in zip(t,p))
print(ant(27,3,-7,11,-17,23))

这面这四行代码实现了前面两段20几行代码才实现的功能，而且更加高效，经过验证，示例中的计算结果是正确的，跟第一段代码的结果一样
真是很讽刺，第一段代码没有考虑到蚂蚁在非整数位置相遇的情况，但是计算结果却是正确的，大概是在这个例子中，蚂蚁确实没有在非整数位置相遇，所以计算结果正确，第二段中却增加了不正确的代码，所以结果不对。

第三段代码是根据自己的想法写出来的，
已知长度和5只蚂蚁的位置和方法，(27,3,-7,11,-17,23)
那么这5只蚂蚁离开的时间就等于
其初始位置为（-7，－17，3，11，23）时灵魂穿过相遇的蚂蚁所需要的时间，由这个想法才写出了上在3行代码就实现的算法。
代码的含义：
p = sorted(args, key = abs)， 将蚂蚁按照他们的位置排序，不考虑其方向。
t = [-i for i in p if i<0] + [m- i for i in p if i >0]  将朝向始端（0端）的蚂蚁放在前边，将朝向末端的蚂蚁放在后边（此例中为27端），并计算他们离开杆子的时间。
return sorted((k,v) for k,v in zip(t,p))  按照蚂蚁先后离开的顺序排序，计算完毕，退出程序。

（3,-7,11,-17,23）不严密证明如下：
p3表示初始位置在3的蚂蚁，下同

p3遇到p7时是在位置5，然后调头至0退出，所经过的距离为（5－3+5） ＝7，即相当于p3好像其初始位置为－7时所经历的时间，

p-7调头就好像其初始位置为3一样，
同时p11与p-17碰头就好像其初始位置分别为p-17和p11一样
重新假设位置的p-7，已经假设其位置为3，它不会与不会调头的p11碰头，因为他们同向，如果p11调头就表明它碰到了逆向的蚂蚁，那就可以假设p11的初始位置为其碰到的第一个逆向的蚂蚁。p11再与p-7（已经假设其位置方向为3），那样就可以假设p-7的初始位置为p11的假设位置，即p-17，却除-7之外的第一只逆向的蚂蚁。

排在第一只朝27端前边的所有蚂蚁是朝向0端的，那们他们离开时不会有与其它蚂蚁碰头的机会，它离开的时间就是其位置的绝对值，这样就可以不参与与其它蚂蚁假定交换位置。
所以需要参与假定交换位置的排在第一的蚂蚁一定是朝向27端的即初始位置方向>0，他离开的时间就是依次向末端找到的第一只与其对向的蚂蚁即初始位置方向<0，本例中p3离开的时间就是p－7位置的最快离开时间。
p-7已经与p3假定交换位置，所以p-7现在的假定位置方向>0，同理它的离开时间也为依次向末端找第一只位置方向<0的蚂蚁，本例中p-7的最终假定位置就是-17

剩下的所有的蚂蚁的假定位置方向均朝向末端，即>0，那么它们离开的时间就是剩下的所有的假定的交换位置离开所需要的时间。

不严密的证明，不保证这段代码正确，求证明过程或者验证。

上面这段第三段代码的讲解啰嗦不堪，我估计自己以后都要看迷糊了，这是论坛里的证明过程，简洁明了，给转过来了。

设两蚁相遇，则交换灵魂，而肉体掉头行驶。
以 3 -7 11 -17 23 为例，
第一个负数为-7，则说明-7的灵魂在左边第一个掉下去，耗时7秒。而承载起灵魂的肉体一定是左边第一个数3
第二个负数为-17，则说明-17的灵魂在左边第二个掉下去，耗时17秒。而承载起灵魂的肉体一定是左边第二个数-7
右边亦复如是

并且他还用C++重新实现了上述代码。
也转在这里了。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void ant( int m, std::initializer_list<int> k )
{
    // python: p = sorted(args, key = abs)
    vector<int> v1( k );
    sort( v1.begin(), v1.end(), [](int a, int b){ return abs(a)<abs(b); } );

    // python: t = [i for i in p if i<0] + [ for i in p if i >0]
    vector<int> v2( k );
    sort( v2.begin(), v2.end(), [](int a, int b){ return a<0&&b<0 ? a>b : a<b; } );

    // python: zip(-t或m-t,p)
    vector<pair<int,int>> v3;
    for( size_t i=0; i!=k.size(); ++i )
        v3.push_back( make_pair(v2[i]>0?m-v2[i]:0-v2[i], v1[i]) );
    // python: sorted zip
    sort( v3.begin(), v3.end(), [](pair<int,int> a, pair<int,int> b){ return a.first<b.first; } );

    // python: print
    for( auto v : v3 )
        cout << " (" << v.first << ',' << v.second << ')';
    cout << endl;
}

int main()
{
    ant( 27, {3,-7,11,-17,23} );

    return 0;
}

再贴一个自己写的lua版的，计算方法一样，怎么lua写出来的这么长，还是python的最短。

function ant(m,...)
    local arg = table.pack(...)

    table.sort(arg, function(a,b)
        return math.abs(a) < math.abs(b)
    end)

    p = {}
    for _,v in ipairs(arg) do
        if v < 0 then
            table.insert(p, -v)
        end
    end

    for _,v in ipairs(arg) do
        if v > 0 then
            table.insert(p, m-v)
        end
    end

    tbl = {}
    for i,v in ipairs(arg) do
        table.insert(tbl,{p[i], v})
    end
    table.sort(tbl,function(a,b)
        return a[1] < b[1]
    end)

    for _,v in pairs(tbl) do
        print(v[1], v[2])
    end
end

ant(27,3,-7,11,-17,23)

原贴地址：