#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# a graphical Depth First Search example

edited February 2012 Posts: 3
``````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
// 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

``````
Tagged:

Posts: 5,070

Nice exploration of DFS. I love visualising algorithms.

I think the first sound type is much better.

Included a picture here:

• Posts: 3

:-D Thamks for comment!

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

Posts: 5,070

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)`

• Posts: 622

fun to watch

• edited February 2012 Posts: 3

Thanks a lot!

• Posts: 2,820

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