Mock CCC (WCC)

[A.J]

thats it, here are the REVISED versions of Senior and Junior WCC (and you want to find the # of paths for Thor that is LESS than that of the guests)

[chili5]

Hm, how long is this going to go? I wouldn't mind talking about the questions. Like what is the concepts behind S3? I have no idea how to do those optimal path through a maze questions.

[saltpro15]

optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site

[A.J]

well, I think you meant Breadth First Search , but Best First Search exists too.

And as only2 people sent me their solutions in about 1 month, I think it is safe to say that people can discuss the solutions (or ask me for some of them)

[saltpro15]

yes A.J. is correct, it's Breadth

[chili5]

Okay thanks guys! I found a very helpful tutorial on recursion:

http://compsci.ca/v3/viewtopic.php?t=9581

Curious as to how people handled S2.

My solution:

CODE:

import java.io.*; import java.util.*; /**  *  * @author James  */ public class s2 {     public static int nX = 0, nY = 0, nZ = 0; // coordinates     public static boolean bGood = true; // if a test succeeded = true     public static void main(String[] args) throws IOException {         Scanner sin = new Scanner(new FileReader("s2.txt"));         int nIns; // number of instructions         String sIns; // the instruction         int nN; // number of units to move                 nIns = sin.nextInt();         for (int i=0;i<nIns;i++) {             sIns = sin.next();             nN = sin.nextInt();             move(sIns,nN);         }         if (bGood = true) {             System.out.println("Time to go pirating while living in the yellow submarine!");         } else {             System.out.println("Oh well, I guess it is back to our ancient Viking ship…");         }         sin.close();     }     public static void move(String sIns, int nN) {         if (sIns.equals("fd")) {             // move forward on x nN units             nX += nN;             if (nX >= 0) {                 bGood = true;             } else {                 bGood = false;             }                     } else if (sIns.equals("bk")) {             nX -= nN;             if (nX >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("rt")) {             nY += nN;             if (nY >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("lt")) {             nY -= nN;             if (nY >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("up")) {             nZ += nN;             if (nZ >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if(sIns.equals("dn")) {             nZ -= nN;             if (nZ >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else {             if (nZ == nN) {                 bGood = true;             } else {                 bGood = false;             }         }     } }

Anybody get anything better?

[Analysis Mode]

saltpro15 @ Wed Mar 18, 2009 2:36 pm wrote:

optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site

Well, you're kind of unclear there. If the maze has one exit, use DFS. If there are multiple exits, use BFS.

[A.J]

Analysis Mode wrote:

saltpro15 @ Wed Mar 18, 2009 2:36 pm wrote:

optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site

Well, you're kind of unclear there. If the maze has one exit, use DFS. If there are multiple exits, use BFS.

Not necessarily, Analysis Mode. You can interchangeably use either (although I am not sure whether that sentence is grammatically correct ). It is the algorithm's complexity and what the question is asking specifically you must take into account.

chili5 wrote:

Curious as to how people handled S2.

My solution:

CODE:

import java.io.*; import java.util.*; /**  *  * @author James  */ public class s2 {     public static int nX = 0, nY = 0, nZ = 0; // coordinates     public static boolean bGood = true; // if a test succeeded = true     public static void main(String[] args) throws IOException {         Scanner sin = new Scanner(new FileReader("s2.txt"));         int nIns; // number of instructions         String sIns; // the instruction         int nN; // number of units to move                 nIns = sin.nextInt();         for (int i=0;i<nIns;i++) {             sIns = sin.next();             nN = sin.nextInt();             move(sIns,nN);         }         if (bGood = true) {             System.out.println("Time to go pirating while living in the yellow submarine!");         } else {             System.out.println("Oh well, I guess it is back to our ancient Viking ship…");         }         sin.close();     }     public static void move(String sIns, int nN) {         if (sIns.equals("fd")) {             // move forward on x nN units             nX += nN;             if (nX >= 0) {                 bGood = true;             } else {                 bGood = false;             }                     } else if (sIns.equals("bk")) {             nX -= nN;             if (nX >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("rt")) {             nY += nN;             if (nY >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("lt")) {             nY -= nN;             if (nY >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("up")) {             nZ += nN;             if (nZ >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if(sIns.equals("dn")) {             nZ -= nN;             if (nZ >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else {             if (nZ == nN) {                 bGood = true;             } else {                 bGood = false;             }         }     } }

Anybody get anything better?

Although your code does work (at least I think it should), there is a lot of redundant code. Since the question is asking you to check if the depth matches the given checks, all you really need to store is the 'z' position.....but your method is correst, good job .

[A.J]

Analysis Mode wrote:

saltpro15 @ Wed Mar 18, 2009 2:36 pm wrote:

optimal paths in a maze are usually found with a BFS or a DFS algorithm, by which I mean Best First Search and Depth First Search. There are some excellent articles on them on this site

Well, you're kind of unclear there. If the maze has one exit, use DFS. If there are multiple exits, use BFS.

Not necessarily, Analysis Mode. You can interchangeably use either (although I am not sure whether that sentence is grammatically correct ). It is the algorithm's complexity and what the question is asking specifically you must take into account.

chili5 wrote:

Curious as to how people handled S2.

My solution:

CODE:

import java.io.*; import java.util.*; /**  *  * @author James  */ public class s2 {     public static int nX = 0, nY = 0, nZ = 0; // coordinates     public static boolean bGood = true; // if a test succeeded = true     public static void main(String[] args) throws IOException {         Scanner sin = new Scanner(new FileReader("s2.txt"));         int nIns; // number of instructions         String sIns; // the instruction         int nN; // number of units to move                 nIns = sin.nextInt();         for (int i=0;i<nIns;i++) {             sIns = sin.next();             nN = sin.nextInt();             move(sIns,nN);         }         if (bGood = true) {             System.out.println("Time to go pirating while living in the yellow submarine!");         } else {             System.out.println("Oh well, I guess it is back to our ancient Viking ship…");         }         sin.close();     }     public static void move(String sIns, int nN) {         if (sIns.equals("fd")) {             // move forward on x nN units             nX += nN;             if (nX >= 0) {                 bGood = true;             } else {                 bGood = false;             }                     } else if (sIns.equals("bk")) {             nX -= nN;             if (nX >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("rt")) {             nY += nN;             if (nY >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("lt")) {             nY -= nN;             if (nY >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if (sIns.equals("up")) {             nZ += nN;             if (nZ >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else if(sIns.equals("dn")) {             nZ -= nN;             if (nZ >= 0) {                 bGood = true;             } else {                 bGood = false;             }         } else {             if (nZ == nN) {                 bGood = true;             } else {                 bGood = false;             }         }     } }

Anybody get anything better?

Although your code does work (at least I think it should), there is a lot of redundant code. Since the question is asking you to check if the depth matches the given checks, all you really need to store is the 'z' position.....but your method is correst, good job .

[chili5]

So it would be good to learn both DFS and BFS? I keep thinking they just apply to graphs though.

So really you could have ignored any command that had anything to do with the x or y axis?

[Analysis Mode]

oh yes you should. Two different concepts, to be applied in different scenarios. Substituting one for the other could lead to TLE.

[saltpro15]

Basically, if you're maze is more "open" with more clear space, you want to use a DFS, since it is easier to code and takes less time to write. But, if the maze is cluttered with lots of paths and objects, you have to use BFS, else your program can run for hours on end

[Analysis Mode]

OK. Let me rephrase. If i'm asking you for the shortest path between the start and end of a maze, BFS / Dijkstra's (depending on whether or not edges are weighted (not based on path length)) If i'm asking you if it's possible to reach the end from the start, DFS (connectivity in a graph).

And if there's a lot of open space, definitely not DFS. First off, when you reach the end, it is not guaranteed that you have the optimal answer, whereas BFS does. And the time complexity increases exponentially as the grid size increases (I think).

[A.J]

I don't think it is exponentially (although I'm notorious for being wrong in my suppositions). And about the DFS/BFS, now it is clearer....I agree with you there. If the graph is weighted, Dijkstra is optimal, although there are other methods.

[DanielG]

I believe it is in fact exponential, since I can't think of any polynomial equation that would fit for it, I suppose it just has a very small multiplier for the exponent.