Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 DWITE round 4 question 4
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Insectoid




PostPosted: 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
Sponsor
sponsor
CodeMonkey2000




PostPosted: 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 Sad
Insectoid




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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
Sponsor
sponsor
DanielG




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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. Confused
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




PostPosted: 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. Confused

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




PostPosted: 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. Confused

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
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 15 Posts ]
Jump to:   


Style:  
Search: