-----------------------------------

DanielG

Sat Jan 17, 2009 6:35 pm


Jan dwite 2009 Q5

-----------------------------------

did anyone other then me not use BFS/DFS and still get 5/5 on question 5?


-----------------------------------

saltpro15

Sat Jan 17, 2009 7:16 pm


RE:Jan dwite 2009 Q5

-----------------------------------

we used BFS and got 0/5 :(


-----------------------------------

A.J

Sat Jan 17, 2009 7:29 pm


Re: Jan dwite 2009 Q5

-----------------------------------

what is your team name saltpro?

cuz we used BFS and got 5/5 (we were 8th place)


-----------------------------------

saltpro15

Sat Jan 17, 2009 8:18 pm


RE:Jan dwite 2009 Q5

-----------------------------------

my team was the awesome swatcats, we were 36th, probably would have been 20 something if we got Q5


-----------------------------------

saltpro15

Sat Jan 17, 2009 8:48 pm


Re: Jan dwite 2009 Q5

-----------------------------------


var IN, OUT : int
open : IN, "DATA5.txt", get
open : OUT, "OUT5.txt", put

type coord :
    record
        x, y, z : int
    end record

var start : array 1 .. 1 of coord
var F : coord
var DEPTH : int := 0

var lay : int
get : IN, lay

var tempStr : string

var b : array 0 .. 6, 0 .. 6, 0 .. lay + 1 of string


procedure BFS (queue : array 1 .. * of coord, depth : int, fin : coord)
    var next : flexible array 1 .. 0 of coord
    for i : 1 .. upper (queue)
        if queue (i).x = fin.x and queue (i).y = fin.y and queue (i).z = fin.z then
            % FOUND
            DEPTH := depth
            return
        end if

        for dx : -1 .. 1
            for dy : -1 .. 1
                if not (abs (dx) = 1 and abs (dy) = 1) then
                    var nextX := queue (i).x + dx
                    var nextY := queue (i).y + dy
                    var nextZ := queue (i).z + 1

                   
                    if b (nextX, nextY, nextZ) = "." or b (nextX, nextY, nextZ) = "B" then
                        var U := upper (next) + 1
                        new next, U
                        next (U).x := nextX
                        next (U).y := nextY
                        next (U).z := nextZ
                    end if

                end if

            end for
        end for
    end for

    BFS (next, depth + 1, fin)
end BFS

for asdf : 1 .. 5     
    DEPTH := 0

    for z : 1 .. upper (b, 3)
        for i : 0 .. 6
            b (0, i, z) := "#"
            b (6, i, z) := "#"
            b (i, 0, z) := "#"
            b (i, 6, z) := "#"
        end for
    end for

    for x : 0 .. 6
        for y : 0 .. 6
            b (x, y, 0) := "#"
            b (x, y, upper (b, 3)) := "#"
        end for
    end for

    for z : 1 .. lay
        for decreasing y : 5 .. 1
            get : IN, tempStr
            for x : 1 .. 5
                if tempStr (x) = "B" then
                    F.x := x
                    F.y := y
                    F.z := z
                end if
                if tempStr (x) = "A" then
                    start (1).x := x
                    start (1).y := y
                    start (1).z := z
                end if
                b (x, y, z) := tempStr (x)
            end for
        end for
    end for

    

    BFS (start, DEPTH, F)
    
    put : OUT, DEPTH
    % put Time.Elapsed / 1000
end for


someone want to tell me why this is a 0/5 ?  not complaining, I just want to know what to change for next time


-----------------------------------

DanielG

Sat Jan 17, 2009 9:45 pm


RE:Jan dwite 2009 Q5

-----------------------------------

I personally find the non recursive (using a while loop/[just loop in turing]) approach to be easier and  to work better for BFS, just look at your recursive function, you are calling the function only after the previous has completely finished.
flexibles arrays are bad (especially in turing), but that's another matter.

About your current code, I noticed that you only get lay before your 5 runs, which would cause your program to (assuming everything else worked) only work for the first test case. 

Other than that I can't see immediately what was wrong with your code, try looking at other's code and seeing what is different (don't try mine, as I used a completely different method)


-----------------------------------

Dan

Sat Jan 17, 2009 10:44 pm


RE:Jan dwite 2009 Q5

-----------------------------------

I am a bit behind in looking in to complaints about cases where the judge may have screwed up. However remeber that there is a set time limit for how long the code is allowed to run for.

Also rember that the judge changes the order of the test cases in the file, the one shown on the site is just an example so try testing your code with the test cases in a diffrent order as well.


-----------------------------------

A.J

Sun Jan 18, 2009 12:01 am


Re: Jan dwite 2009 Q5

-----------------------------------

hey saltpro

compare your BFS code for 4 and 5 with mine (as it is almost identical surprisingly)

though i do agree with DanielG......the 'manual' BFS method is better in turing , and also a bit easier to understand (and perhaps to code also) making it ideal to use


-----------------------------------

DanielG

Sun Jan 18, 2009 12:37 am


RE:Jan dwite 2009 Q5

-----------------------------------

I just realized the easiest way to do this question (that is at the same time efficient, and I don't think anyone did).
All you need is floodfill, since if you can reach a place, it's distance would be the frame number (-1 if you start from 1).


-----------------------------------

saltpro15

Sun Jan 18, 2009 8:41 am


RE:Jan dwite 2009 Q5

-----------------------------------

lol AJ, I see what you mean about the code being similar :P.  Oh well, we handed our Q5 in with 29 minutes left and with 1 minute left it still hadn't marked, so maybe that was it.  No worries though, next round we'll just hand it in first