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 in Code Sharing 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 // 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


  • SimeonSimeon Admin Mod
    Posts: 5,705

    Nice exploration of DFS. I love visualising algorithms.

    I think the first sound type is much better.

    Included a picture here:

    Depth First Search

  • :-D Thamks for comment!

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

  • SimeonSimeon Admin Mod
    Posts: 5,705

    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:


  • 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.

Sign In or Register to comment.