DWITE round 4 question 4
Author |
Message |
Insectoid
|
Posted: Thu Jan 15, 2009 7:06 pm Post subject: DWITE round 4 question 4 |
|
|
This isn't a thread complaining about the question. It's a thread about you guys helping me finish question 4, and explaining where I went wrong.
Basically, it gets stuck and moves in strange ways.
Here's my code:
Turing: |
var input : int
var output : int
var startX : array 1 .. 5 of int
var startY : array 1 .. 5 of int
var targetX : array 1 .. 5 of int
var targetY : array 1 .. 5 of int
var stepsTaken : array 1 .. 5 of int
var map : array 1 .. 8 of array 1 .. 8 of array 1 .. 5 of string
var steps : array 1 .. 8 of array 1 .. 8 of array 1 .. 5 of int
var line : string
setscreen ("text")
for z : 1 .. 5
for x : 1 .. 8
for y : 1 .. 8
steps (x ) (y ) (z ) := 99999999
end for
end for
end for
open : input, "DATA4.txt", get
for z : 1 .. 5
stepsTaken (z ) := 0
for y : 1 .. 8
get : input, line
for x : 1 .. 8
map (x ) (y ) (z ) := line (x )
if line (x ) = "A" then
startX (z ) := x
startY (z ) := y
elsif line (x ) = "B" then
targetX (z ) := x
targetY (z ) := y
end if
end for
end for
end for
close : input
for z : 1 .. 1
loop
put startX (z ), " ", startY (z )
exit when startX (z ) = targetX (z ) and startY (z ) = targetY (z )
if startY (z ) < 8 and startX (z ) < 8 then
if map ((startX (z ) + 1) ((startY (Z )+ 1)
if startY (z ) < 8 then
if map (startX (z )) (startY (z ) + 1) (z ) ~ = "#" and steps (startX (z )) (startY (z ) + 1) (z ) > stepsTaken (z ) then
startY (z ) + = 1
stepsTaken (z ) + = 1
steps (startX (z )) (startY (z )) (z ) := stepsTaken (z )
end if
end if
if startY (z ) > 1 then
if map (startX (z )) (startY (z ) - 1) (z ) ~ = "#" and steps (startX (z )) (startY (z ) - 1) (z ) > stepsTaken (z ) then
startY (z ) - = 1
stepsTaken (z ) + = 1
steps (startX (z )) (startY (z )) (z ) := stepsTaken (z )
end if
end if
if startX (z ) < 8 then
if map (startX (z ) + 1) (startY (z )) (z ) ~ = "#" and steps (startX (z ) + 1) (startY (z )) (z ) > stepsTaken (z ) then
startX (z ) + = 1
stepsTaken (z ) + = 1
steps (startX (z )) (startY (z )) (z ) := stepsTaken (z )
end if
end if
if startX (z ) > 1 then
if map (startX (z ) - 1) (startY (z )) (z ) ~ = "#" and steps (startX (z ) - 1) (startY (z )) (z ) > stepsTaken (z ) then
startX (z ) - = 1
stepsTaken (z ) + = 1
steps (startX (z )) (startY (z )) (z ) := stepsTaken (z )
end if
end if
end loop
end for
open : output, "OUT4.txt", put
close : output
|
startY and startX are actually the current X and Y of the dot. I realize I haven't coded in the diagonals, mostly due to my misreading the question and thinking they weren't allowed. I really want this one finished. I can't just get this far and not finish a maze.
Help is much appreciated. |
|
|
|
|
|
Sponsor Sponsor
|
|
|
CodeMonkey2000
|
Posted: Thu Jan 15, 2009 7:49 pm Post subject: RE:DWITE round 4 question 4 |
|
|
Your algorithm isn't correct. This is a straight forward BFS. Google the BFS algorithm. I haven't coded in turing for a while, so I can't give you an example |
|
|
|
|
|
Insectoid
|
Posted: Thu Jan 15, 2009 8:50 pm Post subject: RE:DWITE round 4 question 4 |
|
|
This is what HeavenAgain explained to me (at least, how I interpreted it). I believe it would work. The idea is, you keep let the thing wander through spots with more 'steps' until it gets stuck, or hits the target. Then you do it again, and eventually it will have found the shortest path to the end, and...well, it makes sense to me. |
|
|
|
|
|
saltpro15
|
Posted: Thu Jan 15, 2009 8:51 pm Post subject: Re: DWITE round 4 question 4 |
|
|
My team "the awesome swatcats", got this question 5/5, here's our code
Turing: |
var IN, OUT : int
open : IN, "DATA4.txt", get
open : OUT, "OUT4.txt", put
var b : array 0 .. 9, 0 .. 9 of string
type coord :
record
x, y : int
end record
var F : coord
var start : array 1 .. 1 of coord
var tempInput : string
var DEPTH : int := 1
procedure BFS (queue : array 1 .. * of coord, depth : int, fin : coord )
% var nextQueue : flexible array 1 .. 0 of coord
% for i : 1 .. upper (thisQueue)
% if thisQueue (i).x = fin.x and thisQueue (i).y = fin.y then
% % END
% DEPTH := depth
% return
% end if
%
% for dx : -1 .. 1
% for dy : -1 .. 1
% if b (thisQueue (i).x + dx) (thisQueue (i).y + dy) ~= "#" then
% var TEMP : string
% TEMP := b (thisQueue (i).y + dy) (thisQueue (i).x + dx - 1) + "X" +
% b (thisQueue (i).y + dy) (thisQueue (i).x + dx + 1)
% b (thisQueue (i).y + dy) := TEMP
% % b (thisQueue (i).x + dx) (thisQueue (i).y + dy) := "#"
% var U : int := upper (nextQueue) + 1
% new nextQueue, U
%
% nextQueue (U).x := thisQueue (i).x + dx
% nextQueue (U).y := thisQueue (i).y + dy
%
% for y : 0 .. 9
% put b (y)
% end for
% delay (250)
% end if
% end for
% end for
% end for
var neighbours : flexible array 1 .. 0 of coord
for i : 1 .. upper (queue )
if queue (i ).x = fin.x and queue (i ).y = fin.y then
% FOUND
DEPTH := depth
return
end if
for dx : - 1 .. 1
for dy : - 1 .. 1
var neighbourX := queue (i ).x + dx
var neighbourY := queue (i ).y + dy
if b (neighbourX, neighbourY ) = "." or b (neighbourX, neighbourY ) = "B" then
new neighbours, upper (neighbours ) + 1
neighbours (upper (neighbours )).x := neighbourX
neighbours (upper (neighbours )).y := neighbourY
b (neighbourX, neighbourY ) := "-"
end if
end for
end for
end for
BFS (neighbours, depth + 1, fin )
end BFS
for asdf : 1 .. 5
DEPTH := 0
for i : 0 .. 9
b (0, i ) := "X"
b (9, i ) := "X"
b (i, 0) := "X"
b (i, 9) := "X"
end for
for decreasing y : 8 .. 1
get : IN, tempInput
for x : 1 .. 8
if tempInput (x ) = "B" then
F.x := x
F.y := y
end if
if tempInput (x ) = "A" then
start (1).x := x
start (1).y := y
end if
b (x, y ) := tempInput (x )
end for
end for
% for x : 0 .. 9
% for y : 0 .. 9
% put b (x, y)..
% end for
% put ""
% end for
% put "Start : ", start (1).x, ", ", start (1).y
% put "FIN : ", F.x, ", ", F.y
% put "Fin : ", F.x, ", ", F.y
BFS (start, DEPTH, F )
put : OUT, DEPTH
end for
| [/syntax][/quote] |
|
|
|
|
|
CodeMonkey2000
|
Posted: Thu Jan 15, 2009 9:14 pm Post subject: Re: RE:DWITE round 4 question 4 |
|
|
insectoid @ Thu Jan 15, 2009 8:50 pm wrote: This is what HeavenAgain explained to me (at least, how I interpreted it). I believe it would work. The idea is, you keep let the thing wander through spots with more 'steps' until it gets stuck, or hits the target. Then you do it again, and eventually it will have found the shortest path to the end, and...well, it makes sense to me.
That is somewhat right. But that's not what your code does. |
|
|
|
|
|
Insectoid
|
Posted: Thu Jan 15, 2009 9:26 pm Post subject: RE:DWITE round 4 question 4 |
|
|
It's not what my code does, because I haven't finished it. The current incarnation (should) either get stuck by looping in on itself of hit the target (B), once. It will not yet run multiple times to find the shortest path. |
|
|
|
|
|
HeavenAgain
|
Posted: Thu Jan 15, 2009 9:44 pm Post subject: RE:DWITE round 4 question 4 |
|
|
the algorithm should look something like this (recursive), but first we should assume all position takes infinite amount of steps to walk to.
code: | walk(currentX, currentY, stepsItTakes)
{
if the our current position is invalid or out of bound
then break
if the stepsItTakes to get to the current position is less than what we have before
then we replace it with the current stepsItTakes
else
break
walk(currentX-1, currentY, stepsItTakes+1) // going down the grid
// so on... according to the valid walking directions that is given
} |
|
|
|
|
|
|
CodeMonkey2000
|
Posted: Fri Jan 16, 2009 10:19 am Post subject: Re: DWITE round 4 question 4 |
|
|
The non-recursive approach:
put the starting position in a stack
set the path length to get to the starting position to 0, and everywhere else to infinity.
while (our stack isn't empty){
get the top position in the stack, and delete it.
Loot at all the places you can go to from this position, and see if it is better to go there from this vertex.
If it is, push those verticies in the stack, and set the new path length to that vertex} |
|
|
|
|
|
Sponsor Sponsor
|
|
|
DanielG
|
Posted: Fri Jan 16, 2009 10:21 am Post subject: RE:DWITE round 4 question 4 |
|
|
There are multiple correct turing solutions (and solutions in other languages) you can see just by going to the dwite site, they should give you an idea of what you should be doing, and what you are doing wrong. |
|
|
|
|
|
Brightguy
|
Posted: Sat Jan 17, 2009 3:23 am Post subject: Re: DWITE round 4 question 4 |
|
|
Well... how do you intend to update steps when stepsTaken is never decreased?
HeavenAgain: That should do fine on 5x5 mazes but is inefficient in general.
CodeMonkey2000: Good, except you mean to use a queue instead of a stack. |
|
|
|
|
|
A.J
|
Posted: Sat Jan 17, 2009 11:39 am Post subject: Re: DWITE round 4 question 4 |
|
|
Although I used BFS, much easier-to-code algorithms could also suffice (like DFS or memoization)
DFS can easily suffice for this, and it is really easy to code |
|
|
|
|
|
saltpro15
|
Posted: Sat Jan 17, 2009 12:13 pm Post subject: RE:DWITE round 4 question 4 |
|
|
My team also used a BFS to solve it |
|
|
|
|
|
HeavenAgain
|
Posted: Sat Jan 17, 2009 6:09 pm Post subject: Re: DWITE round 4 question 4 |
|
|
Brightguy @ Sat Jan 17, 2009 4:23 am wrote: HeavenAgain: That should do fine on 5x5 mazes but is inefficient in general..
I cannot think of another good reason why it is inefficient, other than the overhead.
Also for learning purpose, I think the recursion approach is much easier to understand. Which is why I posted it in the first place. |
|
|
|
|
|
Brightguy
|
Posted: Sat Jan 17, 2009 8:36 pm Post subject: Re: DWITE round 4 question 4 |
|
|
HeavenAgain @ Sat Jan 17, 2009 6:09 pm wrote: I cannot think of another good reason why it is inefficient, other than the overhead.
In breadth-first search you only have to visit every vertex once, since you've found the shortest path there once a vertex is added to the queue. In depth-first search you don't have this property and your code will probably end up visiting most vertices many times.
For example, in an open field DFS will take off in a straight line until it reaches an edge, then it will go in some other direction and eventually make its way to the other side of the field. Before finding the shortest way to the other side (just walk there directly) it will find a bunch of paths which go in the wrong direction and then turn around! |
|
|
|
|
|
A.J
|
Posted: Sun Jan 18, 2009 12:15 am Post subject: Re: DWITE round 4 question 4 |
|
|
Brightguy wrote:
HeavenAgain @ Sat Jan 17, 2009 6:09 pm wrote: I cannot think of another good reason why it is inefficient, other than the overhead.
In breadth-first search you only have to visit every vertex once, since you've found the shortest path there once a vertex is added to the queue. In depth-first search you don't have this property and your code will probably end up visiting most vertices many times.
For example, in an open field DFS will take off in a straight line until it reaches an edge, then it will go in some other direction and eventually make its way to the other side of the field. Before finding the shortest way to the other side (just walk there directly) it will find a bunch of paths which go in the wrong direction and then turn around!
thats what makes BFS better than DFS
However, for a small maze like this, DFS easily suffices...........and it is relatively much faster to code, so u'll end up getting a higher mark on DWITE |
|
|
|
|
|
|
|