再次写这篇博文，也算是一次回归吧。许久不写文字，发现说话也不太顺溜了，就此以这段开码开个头吧。

题目：一老人带一条狗，同夫妻二人及男孩女孩各俩（七人加一条狗）由河左岸到右岸，有渡船一只，在如下规则下，问多少次方可全部过河？

规则：1. 可撑船有三人：老人，丈夫，妻子。2. 渡船每次至多携带两位，但至少有一位撑船者。3. 狗在老人的掌控之下才不会伤及他人，但可独处。4. 丈夫喜男孩而不喜女孩，故男孩不可与妻子独处。5. 妻子喜欢女孩而不喜男孩，故女孩不可与丈夫独处

lua的解决代码：

local live = {
    "oldman",
    "dog",
    "husband",
    "wife",
    "boy",
    "girl",
}

local group = {
    "oldman", "dog", 
    "oldman", "boy",
    "oldman", "girl",
    "wife", "girl",
    "husband", "boy",
    "wife", "oldman",
    "husband", "oldman",
    "husband", "wife",
    "husband", false,
    "oldman", false,
    "wife", false, 
}

local round = 0
local left, lefthistory, right, righthistory = {}, {}, {}, {}

local function print_side(side)
    print(string.format("side:%d, n=%d, oldman=%d, dog=%d, husband=%d, wife=%d, boy=%d, girl=%d"
            , side.flag and 1 or 0, side.n, side.oldman, side.dog, side.husband, side.wife, side.boy, side.girl))
end

local function isferryman(live)
    return live == "oldman" or live == "wife" or live == "husband"
end

local function checkload(side, ferryman, host)
    if side[ferryman] <= 0 then return false end
    if side[host] ~= nil and side[host] <=0 then return false end
    return true
end

local function checkside(side)
    if side.oldman == 0
        and side.n > 1
        and side.dog == 1 then
        return false
    end

    if side.husband == 0
        and side.wife == 1
        and side.boy > 0 then
        return false
    end

    if side.husband == 1
        and side.wife == 0
        and side.girl > 0 then
        return false
    end

    return true
end


local function compareside(a, b)
    for k, v in pairs(a) do
        if a[k] ~= b[k] then return false end 
    end

    return true
end


local function checkhistory(side)
    local history = side.flag and righthistory or lefthistory

    for i = 1, #history do
        if compareside(side, history[i]) then return false end
    end

    return true
end

local function copyside(side)
    local target = {}
    for k, v in pairs(side) do
        target[k] = v
    end

    return target
end

local function onboat(side, ferryman, host)
    side[ferryman] = side[ferryman] - 1
    side.n = side.n - 1
    if host then
        side[host] = side[host] - 1
        side.n = side.n - 1
    end
end

local function downboat(side, ferryman, host)
    side[ferryman] = side[ferryman] + 1
    side.n = side.n + 1
    if host then
        side[host] = side[host] + 1
        side.n = side.n + 1
    end
end

local function gothrough(startside, endside, flag)
    if flag and endside.n == 0 then return true end

    local ferryman, host

    local i, z, s
    if flag then
        i = #group - 1
        z = 1
        s = -2
    else
        i = 1
        z = #group
        s = 2
    end

    for i = i, z, s do
        if isferryman(group[i]) then
            ferryman = group[i]
            host = group[i + 1]

            if checkload(startside, ferryman, host) then
                onboat(startside, ferryman, host)
                downboat(endside, ferryman, host)

                if checkside(startside) and checkside(endside) then

                    if checkhistory(startside) then
                        if flag then
                            righthistory[#righthistory + 1] = copyside(startside)
                        else
                            lefthistory[#lefthistory + 1] = copyside(startside)
                        end

                        if gothrough(endside, startside, not flag) then
                            round = round + 1
                            print(string.format("round:%d left%s--%sright, ferryman:%s, host:%s"
                            , round
                            , startside.flag and "<" or ""
                            , startside.flag and "" or ">"
                            , ferryman
                            , host or ""))
                            return true
                        end
                    end
                end

                onboat(endside, ferryman, host)
                downboat(startside, ferryman, host)

            end
        end
    end

end

local function init_data()

    left.n = 8
    left.flag = false

    right.n = 0
    right.flag = true

    for _, v in ipairs(live) do
        left[v], right[v] = 1, 0
    end
    left.boy = 2
    left.girl = 2

end

local function start()
    init_data()

    print("orginal data:")
    print_side(left)
    print_side(right)

    print("begin puzzle:")
    if gothrough(left, right, false) then
        print("finished data:")
    else
        print("fail puzzle!")
    end

    print_side(left)
    print_side(right)
end

local function main()
    start()
end

main()

博主先写的C版，后拿lua来练了个手，发现代码还能少50行，就此。

• 相关文章