a graphical Depth First Search example


t={{}}
r={}
rpt={}    --real position table
lu=0      --length unit
topc=210  --the most light gray val
cl=15
stp=math.floor(topc/cl)
cc=255    --current color
rlim=6
dlim=7
lu = math.floor(HEIGHT/(2+rlim+2))
if dlim >rlim then
    dlim, rlim = rlim, dlim
end
function rpt_init()
    lw=lu/4    --line width
    --lw=0    --line width
    xlist, ylist = {}, {}
    for x = 1, 1+rlim do
        table.insert(xlist, lu*(x+1))
    end
    for y = 1, 1+dlim do
        table.insert(ylist, HEIGHT-lu*(y+1))
    end
    rpt['x']=xlist
    rpt['y']=ylist
end
function decode_chr(lp, c)
    --logic position, step char 
    -- -> new logic position
    local nlpx, nlpy = lp[1], lp[2]
    if "R" == c then
        nlpx = nlpx + 1
    elseif "D" then
        nlpy = nlpy + 1
    end
    return {nlpx, nlpy}
end
function decode_str(s, cd)
    local lps = { 1, 1 }
    local lpe = nil
    local cd = cd or topc
    local dtvctr = {0,0}
    if "number" == type(cd) then
        stroke(cd)
    else
        stroke(unpack(cd))
    end
    strokeWidth(lw)
    lineCapMode(SQUARE)
    line(rpt["x"][1]-lw/2,rpt["y"][1],rpt["x"][1]+lw/2,rpt["y"][1])
    lineCapMode(PROJECT)
    for i, c in ipairs(s) do
        lpe = decode_chr(lps, c)
        if "R" == c then
            dtvctr = {lw/2,0}
        else
            dtvctr = {0,-lw/2}
        end
        
        line(
            rpt['x'][lps[1]] + dtvctr[1],
            rpt['y'][lps[2]] + dtvctr[2],
            rpt['x'][lpe[1]] + dtvctr[1],
            rpt['y'][lpe[2]] + dtvctr[2])
        lps = lpe
    end
end
function next_step(stat)
    local r = {}
    local dsum=0
    local rsum=0
    for i, v in ipairs(stat) do
        if "R"==v then
            rsum = rsum + 1
        elseif "D"==v then
            dsum = dsum + 1
        end
    end
    
    local t={{"R",rlim, rsum}, {"D",dlim, dsum}}
    if math.random() < 0.5 then
        t[1], t[2] = t[2], t[1]
    end
    for i, v in ipairs(t) do
        local sn, lm, sm = unpack(v)
        if sm < lm then
            nt={unpack(stat)}
            table.insert(nt, sn)
            table.insert(r, nt)
        end
    end
    
    return r
end
-- Use this function to perform your initial setup
function setup()
    print([[
// problem No.5
// Admaster
// 2014-77
]])
    rpt_init()
    noSmooth()
    iparameter("cl", 0, 30, 15)
    parameter('curs', 0, 1)
    prevcurs=curs
    curi=0
    watch("curi")
    sndes={
        SOUND_BLIT, SOUND_JUMP, SOUND_PICKUP,
        SOUND_SHOOT, SOUND_RANDOM
    }
    iparameter("sndi", 1, #sndes, 2)
    background(0, 0, 0, 255)
end
function hlas()
    --highlight a solve
    if curs ~= prevcurs then
        curi = math.ceil(curs*#r)
        prevcurs = curs
    end
    --stroke(13, 104, 207, 104)
    if r[curi] then
        decode_str(r[curi], {208,14,48,158})
    end
end
-- This function gets called once every frame
function draw()
    background(0,0,0,255)
    stp=math.floor(topc/cl)
    for i, v in pairs({unpack(r, #r-cl, #r-1) }) do
        local cdpth=math.floor(i*stp)
        decode_str(v, {cdpth/2,cdpth,cdpth/2,158})
    end
    hlas()
    if t[1] then
        c = t[1]
        table.remove(t, 1)
        if #c == rlim+dlim then
            decode_str(c, {13,104,207,158})
            table.insert(r, c)
            sound(sndes[sndi], string.byte(c[#c])*20)
            --print(#r, table.concat(c))
        end
        for i, v in ipairs(next_step(c)) do
            table.insert(t, 1, v)
        end
    end
end

Thanks a lot!

Nice exploration of DFS. I love visualising algorithms.

I think the first sound type is much better.

Included a picture here:

Depth First Search

:smiley: Thamks for comment!

And… could you tell me how to upload and show a picture in discussion please? oTL

To upload a picture you have to host it somewhere — so for example you could take a screenshot and post it to twitter, then take that link and use this format on the forums to embed the image:

![Description](http://url.to/image.jpg)

fun to watch

@BladeWang - I asked the same questions at one point. Check out my discussion here.