青蛙过河问题

我很早就看到这个问题(最早是在一款经典的解密类游戏里),玩法很简单:每只青蛙都可以向前或者越过前面的青蛙跳一格(跟小时候的六角玻璃弹子棋很像:)),直到全部跳到对面。

具体的编程就是简单的穷举法了,因为左右对称,所以有两种解法。直接上个Python代码:

Python语言: 青蛙过河
#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# 计算青蛙跳石头过河问题:
# 每只青蛙可以向前跳一步到空的石头或越过前面的一只青蛙跳到石头
# 初始状态:>>>+<<<
# 最终状态:<<<+>>>
# +为空石头,>和<为方向相反的青蛙

trace_stack = []

def recursive(frog_list, final_list):
    global trace_stack

    if frog_list == final_list:
        trace_stack.append(frog_list)
        return True

    index = frog_list.index('+')

    # 空石头右边第一只
    if index+1 < len(frog_list):
        if frog_list[index+1] == '<':
            temp = frog_list[:]
            temp[index],temp[index+1] = temp[index+1],temp[index]
            if recursive(temp, final_list):
                trace_stack.append(frog_list)
                return True

        # 空石头右边第二只
        if index+2 < len(frog_list):
            if frog_list[index+2] == '<':
                temp = frog_list[:]
                temp[index],temp[index+2] = temp[index+2],temp[index]
                if recursive(temp, final_list):
                    trace_stack.append(frog_list)
                    return True

    # 空石头左边第一只
    if index1 >= 0:
        if frog_list[index1] == '>':
            temp = frog_list[:]
            temp[index],temp[index1] = temp[index1],temp[index]
            if recursive(temp, final_list):
                trace_stack.append(frog_list)
                return True

        # 空石头左边第二只
        if index2 >= 0:
            if frog_list[index2] == '>':
                temp = frog_list[:]
                temp[index],temp[index2] = temp[index2],temp[index]
                if recursive(temp, final_list):
                    trace_stack.append(frog_list)
                    return True

    return False

def main():
    global trace_stack
    frog_count = 3
    frog_str = '>'*frog_count + '+' + '<'*frog_count
    frog_list = [i for i in frog_str]
    final_list = frog_list[:]
    final_list.reverse()

    if recursive(frog_list, final_list):
        try:
            while True:
                line = trace_stack.pop()
                print "".join(line)
        except:
            pass

if __name__ == "__main__":
    main()

运行结果:

二手路由器上玩OpenWrt

在淘宝上淘到一个二手家用路由器RG100A-AA,让老板预刷了OpenWrt,这下有的玩了:)。

OpenWrt基于嵌入式Linux,适合于路由器等嵌入式设备,最早源于LinkSys公司WRT54G系列路由器产品的开源代码。话说LinkSys一开始是美国的两个台湾移民开的,早期主要生产交换机、路由器刚好赶上上世纪90年代的网络化浪潮,直到2007年被思科收购(思科不愧为收购狂人)。LinkSys在美国还是有一定名气的,思科也不敢贸然把LinkSys出厂商标都换成Cisco。扯远了,就是基于WRT54G系列路由器的开源代码,孵化出一连串开源系统,比较有名的是OpenWrt、DD-WRTTomato

至于OpenWrt的功能可以用强大形容,一般路由器有的它有、没有的它也有,wiki上有列出一长串功能,我最感兴趣的功能是:

  1. 支持文件系统,任意安装软件,有的折腾。
  2. 支持SSH端口转发和VPN,这个具体用来干什么,我就不说了。
  3. 支持一个USB接口,接个外接硬盘,运行个BT什么的,可以脱机下东西了。
  4. 也用USB接个摄像头,搞个在线监控也不错,一起一直想在Linux下做的。

废话少说,我用电脑接RG100A-AA的LAN口,WAN口(OpenWrt默认RG100A-AA的LAN4为WAN口)接家里的路由器就算搭好了。赶忙登陆OpenWrt的Web界面,界面很华丽,功能很强大,貌似用Lua写的。不过悲催的是设置WAN口时老是掉线,居然连Ping都没反应,只能冒险爆路由器菊花复位了,还好救活了。全部设置好后体验了下还不错,除了启动有点慢和有点发热。

接下来就慢慢享受OpenWrt的乐趣了。