Jan dwite 2009 Q5

DanielG · **Posted:** Sat Jan 17, 2009 6:35 pm

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

saltpro15 · **Posted:** Sat Jan 17, 2009 7:16 pm

we used BFS and got 0/5 Sad

A.J · **Posted:** Sat Jan 17, 2009 7:29 pm

what is your team name saltpro?

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

saltpro15 · **Posted:** Sat Jan 17, 2009 8:18 pm

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

saltpro15 · **Posted:** Sat Jan 17, 2009 8:48 pm

Turing:

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 · **Posted:** Sat Jan 17, 2009 9:45 pm

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 · **Posted:** Sat Jan 17, 2009 10:44 pm

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 · **Posted:** Sun Jan 18, 2009 12:01 am

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 · **Posted:** Sun Jan 18, 2009 12:37 am

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 · **Posted:** Sun Jan 18, 2009 8:41 am

lol AJ, I see what you mean about the code being similar Razz

. 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

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members