История изменений

Исправление LINUX-ORG-RU, 24.06.26 02:37 (текущая версия) :

#!/usr/bin/env lua

local input =
[[
a → b, c, d, z
b → d, e, f, z
c → d, e, f, z
d → e, f, z
e → f, z
f → g, h, j, z
g → h, i, j, z
h → i, j, k, z
i → j, k, l, z
j → k, m, z
k → l, n, o, z
l → m, z
m → n, o, z
n → o, z
o → p, z
p → q, z
q → r, z
r → s, z
s → t, u, z
t → u, v, z
u → v, w, z
v → w, z
w → x, y, z
x → y, z
y → z
z → (нет исходящих)
]]

local paths = { }

for start,list,val in input:gmatch('(%w)%s+→(.-)\n') do
    paths[start] = { }
    for v in list:gmatch('%s+(%w)') do
        if not paths[start][v] then
           paths[start][v] = v
        end
    end
    ---
    for k, p in pairs(paths) do
        for x,v in pairs(p) do
            if x == start  then
               p[x] = paths[start]
            end
        end
    end
end

local count = 0

local function trace(path,name)
    for k,v in pairs(path) do
        if k == 'z' then
           io.write(name..'z \n')
           count = count + 1
        else
           trace(v,name..k..' -> ')
        end
    end
end

trace(paths['a'],'')
print(count)

...
22061

Не сразу понял, долго тупил. Затем ещё дольше тупил почему у меня 51599 путей выходит, пока не понял что я ищу все пути от всех к z, а надо только от a к z

Исходная версия LINUX-ORG-RU, 24.06.26 02:35:


local input =
[[
a → b, c, d, z
b → d, e, f, z
c → d, e, f, z
d → e, f, z
e → f, z
f → g, h, j, z
g → h, i, j, z
h → i, j, k, z
i → j, k, l, z
j → k, m, z
k → l, n, o, z
l → m, z
m → n, o, z
n → o, z
o → p, z
p → q, z
q → r, z
r → s, z
s → t, u, z
t → u, v, z
u → v, w, z
v → w, z
w → x, y, z
x → y, z
y → z
z → (нет исходящих)
]]

local paths = { }

for start,list,val in input:gmatch('(%w)%s+→(.-)\n') do
    paths[start] = { }
    for v in list:gmatch('%s+(%w)') do
        if not paths[start][v] then
           paths[start][v] = v
        end
    end
    ---
    for k, p in pairs(paths) do
        for x,v in pairs(p) do
            if x == start  then
               p[x] = paths[start]
            end
        end
    end
end

local count = 0

local function trace(path,name)
    for k,v in pairs(path) do
        if k == 'z' then
           io.write(name..'z \n')
           count = count + 1
        else
           trace(v,name..k..' -> ')
        end
    end
end

trace(paths['a'],'')
print(count)

...
22061