Tackling problem

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• November 6th, 2013, 09:17
keepStriving
Tackling problem
TopCoder Statistics - Problem Statement

I was wondering if anyone could give me any tips on how to go about solving the following problem, the guide says that it is a dynamic programming problem, I have an inkling that I could do recursion and store the values somehow. Though not sure how to implement the code.
• November 6th, 2013, 11:57
Norm
Re: Tackling problem
• November 6th, 2013, 13:22
keepStriving
Re: Tackling problem
Code :

```public class UnsealTheSafe {         public long countPasswords(int N){   for(int i = 0;i<N;i++){   } } }```
This is my code so far, which is diddly squat. I am unsure of how to approach it.
• November 6th, 2013, 14:08
Norm
Re: Tackling problem
Try doing some design work with paper and pencil before trying to write any code. Until you get some ideas on what the code is supposed to do and then refine that down to a solid design, you can't start writing code.
• November 6th, 2013, 14:52
copeg
Re: Tackling problem
Break the problem down, as Norm said do some design work first. For example, think if there is any data structure you know of which looks similar to that of the picture (or could be used to store the structure/rules), then think how you can use that data structure to calculate a solution
• November 7th, 2013, 06:27
keepStriving
Re: Tackling problem
Code :

```import java.util.ArrayList; import java.util.HashMap; import java.util.Map;   public class UnsealTheSafe {   public static void main(String[] args){     System.out.println(countPasswords(2));   }   public static long countPasswords(int N){ Map<Integer, ArrayList<Integer>>matching =new HashMap<Integer,ArrayList<Integer>>();   ArrayList<Integer>matchingOne = new ArrayList<Integer>(); matchingOne.add(2); matchingOne.add(4); matching.put(1,matchingOne);   ArrayList<Integer>matchingTwo = new ArrayList<Integer>(); matchingTwo.add(1); matchingTwo.add(3); matchingTwo.add(5); matching.put(2,matchingTwo);   ArrayList<Integer>matchingThree = new ArrayList<Integer>(); matchingThree.add(2); matchingThree.add(6); matching.put(3, matchingThree);   ArrayList<Integer>matchingFour = new ArrayList<Integer>(); matchingFour.add(1); matchingFour.add(5); matchingFour.add(7); matching.put(4, matchingFour);   ArrayList<Integer>matchingFive = new ArrayList<Integer>(); matchingFive.add(2); matchingFive.add(4); matchingFive.add(6); matchingFive.add(8); matching.put(5,matchingFive);   ArrayList<Integer>matchingSix = new ArrayList<Integer>(); matchingSix.add(3); matchingSix.add(5); matchingSix.add(9); matching.put(6,matchingSix);   ArrayList<Integer>matchingSeven = new ArrayList<Integer>(); matchingSeven.add(4); matchingSeven.add(8); matchingSeven.add(0); matching.put(7,matchingSeven);   ArrayList<Integer>matchingEight = new ArrayList<Integer>(); matchingEight.add(5); matchingEight.add(7); matchingEight.add(9); matching.put(8,matchingEight);   ArrayList<Integer>matchingNine = new ArrayList<Integer>(); matchingNine.add(6); matchingNine.add(8); matching.put(9,matchingNine);   ArrayList<Integer>matchingZero = new ArrayList<Integer>(); matchingZero.add(7); matching.put(0,matchingZero);   long count = 0; //if first number is i for(long i = 0;i<10;i++){ //loop through array list of possible combinations if first number is i for(int j = 0;j<matching.get(i).size();j++){ if(count==N){ break; } matching.get(j); count++; }   }   return count; }   }```
Thanks for bearing with me guys, this is the code I've come up with so far. Though I get a null pointer exception at "for(int j = 0;j<matching.get(i).size();j++){".
How would I go about make the loop recursive?
• November 7th, 2013, 07:05
Norm
Re: Tackling problem
Quote:

get a null pointer exception at "for(int j = 0;j<matching.get(i).size();j++){".
Check both matching and what get(i) returns for a null value.
• November 7th, 2013, 08:58
keepStriving
Re: Tackling problem
I was using long for "i" instead of int.Sorted that.

--- Update ---

How do you think I can move forward with this problem?
• November 7th, 2013, 09:37
copeg
Re: Tackling problem
Quote:

Originally Posted by keepStriving
How do you think I can move forward with this problem?

Did you decide on a data structure? An algorithm? What is it and why?
• November 7th, 2013, 10:08
keepStriving
Re: Tackling problem
I chose a hash map which has a integer denoting the button pressed as a key, and an arraylist as a value which would show adjacencies that could then be accessed in turn. I'm stuck on what algorithm to use to actually put this into practice, I think recursion could be used as iteration is confusing me with regards to how I am going to loop over the first button pressed, then its adjacencies and then its adjacencies etc.
• November 7th, 2013, 12:17
copeg
Re: Tackling problem
Quote:

Originally Posted by keepStriving
I chose a hash map which has a integer denoting the button pressed as a key, and an arraylist as a value which would show adjacencies that could then be accessed in turn. I'm stuck on what algorithm to use to actually put this into practice, I think recursion could be used as iteration is confusing me with regards to how I am going to loop over the first button pressed, then its adjacencies and then its adjacencies etc

I suggest taking a step back and if you have not, draw the problem out on paper. If you want a tiny hint, scroll down to read the hint below. If not, don't keep reading (and let me know if you wish me to remove the hint).

Hint: there is one data structure in particular that nicely represents the keypad, and a corresponding algorithm that loops 'over the first button pressed, then its adjacencies and then its adjacencies etc'. See List of data structures - Wikipedia, the free encyclopedia
• November 7th, 2013, 16:47
keepStriving
Re: Tackling problem
I've set myself on the tree, though I'm unsure of how to implement a non binary tree in java, many resources I have come across say to create a separate tree class which I can't do. I have understood the concept though no idea how to program. :confused:
• November 7th, 2013, 20:25
copeg
Re: Tackling problem
Quote:

Originally Posted by keepStriving
I've set myself on the tree, though I'm unsure of how to implement a non binary tree in java, many resources I have come across say to create a separate tree class which I can't do. I have understood the concept though no idea how to program. :confused:

That's good right? Always fun to learn something new! A tree would work of course, but another tiny hint if you don't mind it: a tree doesn't allow for circular paths which, if you consider each button/number a node, the problem allows for.
• November 8th, 2013, 07:50
keepStriving
Re: Tackling problem
Hopefully I'll try it with a tree some other time. I've decided to go with multidimensional array.
So far this is the code, just missing the biggest piece in the puzzle which is to start going into other adjacencies and continue the while loop somehow. Do you have any more hints?
Code :

``` public static long countPasswords(int N){   //password keys long[][] adjacencies = {{7}, {2,4}, {1,3,5}, {2,6}, {1,5,7}, {2,4,6,8}, {3,5,9}, {4,8,0}, {5,7,9}, {6,8}}; //keeps track of total number of steps long count = 0;     //loop through all adjacenies for(int i = 0;i<adjacencies.length;i++){ //loop through i in adjacencies for(int j = 0;j<adjacencies[i].length;j++){ //keeps track of if N has been reached while going through into various adjacencies long shortCount = 0; //condition for while loop boolean condition = true; //while loop while(condition == true){ //if N has been reached then if(shortCount == N){ break; } /*----------------------------------------------------------------- need to somehow go through values and then their values etc. till N reached --------------------------------------------------------------------*/   shortCount++; } count += shortCount; } } return count; } }```

Thank you for your help so far, I'm not trying to get you to do it for me, just struggling with something I've never tried before.
• November 8th, 2013, 14:07
keepStriving
Re: Tackling problem
I suppose graph is what you were trying to hint out to me which seems to fit right with the problem.
• November 8th, 2013, 15:10
copeg
Re: Tackling problem
Quote:

Originally Posted by keepStriving
I suppose graph is what you were trying to hint out to me which seems to fit right with the problem.

Yes! Together with a traversal/search algorithm (recursion seems the most obvious way to go about the search). My advice would be to write down in pseudo-code how you'd tackle this, first thinking about it from the perspective of a single node before extrapolating out into the full problem (and code). If you've never programmed graphs before, then glance at some webpages describing them in detail, what problems they can solve, how they can be programmed, and how they can be searched.
• November 9th, 2013, 12:49
keepStriving
Re: Tackling problem
Code :

```public static long countPasswords(int N){   boolean[][] adjacencyList = new boolean[10][10];     for(int i=0;i<10;i++){ for(int j=0;j<10;j++){ if(i==0){ if(j==7){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==1){ if(j==2){ adjacencyList[i][j] = true; }else if(j==4){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==2){ if(j==1){ adjacencyList[i][j] = true; }else if(j==3){ adjacencyList[i][j] = true; }else if(j==5){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false;; } }else if(i==3){ if(j==2){ adjacencyList[i][j] = true; }else if(j==6){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==4){ if(j==1){ adjacencyList[i][j] = true; }else if(j==5){ adjacencyList[i][j] = true; }else if(j==7){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==5){ if(j==2){ adjacencyList[i][j] = true; }else if(j==4){ adjacencyList[i][j] = true; }else if(j==6){ adjacencyList[i][j] = true; }else if(j==8){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==6){ if(j==3){ adjacencyList[i][j] = true; }else if(j==5){ adjacencyList[i][j] = true; }else if(j==9){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==7){ if(j==4){ adjacencyList[i][j] = true; }else if(j==8){ adjacencyList[i][j] = true; }else if(j==0){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==8){ if(j==5){ adjacencyList[i][j] = true; }else if(j==7){ adjacencyList[i][j] = true; }else if(j==9){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }else if(i==9){ if(j==6){ adjacencyList[i][j] = true; }else if(j==8){ adjacencyList[i][j] = true; }else{ adjacencyList[i][j] = false; } }   } }   if(N==0||N==1){ return 1L; }   for(int i = 0;i<adjacencyList.length;i++){ for(int j = 0;j<adjacencyList.length;j++){ if(adjacencyList[i][j]== true){ return countPasswords(N-1); } } } return -1; } }```
This is the code so far, I have created an adjacency matrix which is created each time recursion occurs with 0 as the root node though I know I'm going wrong somewhere with the recursion, I think I may be going wrong with regards to the value of N, how do you think I can make N decrease effectively.
• November 9th, 2013, 15:16
keepStriving
Re: Tackling problem
I know I need to do DFS which will stop by somehow stop when it reaches N.
Do you think I should leave this problem and try to find easier problems to do with graphs as the more research I do the more I'm baffled by the problem.
• November 9th, 2013, 21:28
copeg
Re: Tackling problem
Quote:

Originally Posted by keepStriving
Do you think I should leave this problem and try to find easier problems to do with graphs as the more research I do the more I'm baffled by the problem.

This is up to you. I don't know how much experience you have had with graphs or graph traversal. If none, then perhaps take a step back and learn them a bit in a more simple context. But at the same time the problem isn't supposed to be easy (in fact, aside from the ill intentions of 'Josh' it is a great problem), so don't let a little struggle hold you back.
• November 10th, 2013, 12:53
keepStriving
Re: Tackling problem
I have no experience, it's the first time I've come across the graph data structure so getting somewhat frustrated by the problem though also really interested by the topic of graph theory, once I get some experience with the topic it should help me tackle harder problems. Also finding resources more scant. I'll keep plodding on.
• November 15th, 2013, 11:14
keepStriving
Re: Tackling problem
I have made progress though am stuck at a particular point for each vertex, I can only get it to dfs through one adjacency instead of all adjacencies. So for example the vertex 2 has the adjacencies 1,5 and 3. Though I can only get it to compute for 1, it's not backtracking it seems. Here is my code, it has multiple classes. Feel free to move thread to "What's wrong with my code section" if you wish to do so.
Graph Class:
Code :

```public class Graph{     private final int MAX_VERTS = 20; private Vertex vertexList[];//array of vertices private int adjMat[][];//adjacency matrix private int nVerts;//current number of vertices private StackX theStack; //--------------------------------------------------------- public Graph() { vertexList = new Vertex[MAX_VERTS];   adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int j = 0;j<MAX_VERTS;j++){ //set adjacency matrix to 0 for(int k = 0;k<MAX_VERTS;k++){ adjMat[j][0] = 0; } } theStack = new StackX(); }//end of constructor //--------------------------------------------------------- public void addVertex(char lab){//argument is label vertexList[nVerts++] = new Vertex(lab); } //----------------------------------------------------------- public void addEdge(int start, int end){ adjMat[start][end] = 1; adjMat[end][start] = 1; } //----------------------------------------------------------- public void displayVertex(int v){ System.out.println(vertexList[v].label); } //------------------------------------------------------------ public int dfs(int start, int N){ vertexList[start].wasVisited = true;//begin and mark at 0 displayVertex(start);//display It theStack.push(start);//Push it int index = 1; while(!theStack.isEmpty()){ //until stack empty   if(index==N){ break; }   //get and unvisited vertex adjacent to stack top int v = getAdjUnvisitedVertex(theStack.peek()); if(v==-1){ //if no such vertex theStack.pop(); }else{ vertexList[v].wasVisited = true; //mark it displayVertex(v); //display it theStack.push(v); //push it } index++; }//end while   //stack is empty so we're done for(int j = 0;j<nVerts;j++){ vertexList[j].wasVisited = false; } return index - 1;//minus as don't count initial }//end dfs   //--------------------------------------------------------------- public int getAdjUnvisitedVertex(int v){ for(int j = 0;j<nVerts;j++){ if(adjMat[v][j]==1 && vertexList[j].wasVisited==false){ return j; } } return -1; } //end getAdjUn //-------------------------------------------------------------------- }//end class graph```

Stack class:
Code :

```import java.awt.*; public class StackX {   private final int SIZE = 20; private int[] st; private int top;   public StackX() { st = new int[SIZE]; //make array top = -1; }   public void push(int j){ st[++top] = j; ///Put item on stack }   public int pop(){ return st[top--]; //take item off stack }   public int peek(){ return st[top]; //peek at top of stack }   public Boolean isEmpty(){ return (top == -1); } } //end class StackX```

Vertex Class:
Code :

```public class Vertex{     public char label; // label for Vertex public boolean wasVisited;   public Vertex(char lab) { label = lab; wasVisited = false; }   }//end class vertex```

Main running Class:
Code :

```public class Main{       public static void main(String[] args){ Graph graph = new Graph(); graph.addVertex('0'); //0 graph.addVertex('1'); //1 graph.addVertex('2'); //2 graph.addVertex('3'); //3 graph.addVertex('4'); //4 graph.addVertex('5'); //5 graph.addVertex('6'); //6 graph.addVertex('7'); //7 graph.addVertex('8'); //8 graph.addVertex('9'); //9   graph.addEdge(0, 7); graph.addEdge(1,2); graph.addEdge(1, 4); graph.addEdge(2, 3); graph.addEdge(2, 5); graph.addEdge(3, 6); graph.addEdge(4, 5); graph.addEdge(4, 7); graph.addEdge(5, 6); graph.addEdge(5, 8); graph.addEdge(6, 9); graph.addEdge(7, 8); graph.addEdge(8, 9);   int count = 0; System.out.println("Visits: "); for(int i = 0;i<=9;i++){ count += (graph.dfs(i,2));   } System.out.println("-------------------------"); System.out.println(count); }//end main }//end class Main```
• November 15th, 2013, 11:33
copeg
Re: Tackling problem
Think about how the current dfs method is working:
Code :

```1 Gets the node and adds to stack: 2 finds the next unvisited neighbor 3 if you've reached the max count: end 4 else go to (1)```

Its that end that's the culprit - you need to somehow backtrack at step 3, for instance going from 3 to 2 recursively. This lets the algorithm backtrack, but also note that as you backtrack nodes that were visited should marked as unvisited.
• November 15th, 2013, 14:43
keepStriving
Re: Tackling problem
This is what I have changed which allows me in the example of 2 to go through all adjacencies 1, 3 and 5 though when it is finished it keep repeating 2 till it gets an error. Why is it doing this? Shouldn't it break out automatically once the stack is empty.
Code :

```if(index==N){ dfs(start,N); }```
• November 15th, 2013, 18:34
keepStriving
Re: Tackling problem
I have done the recursion to backtrack though don't understand your point here "but also note that as you backtrack nodes that were visited should marked as unvisited." Why would I do this as when I backtrack I don't want to go back to the same vertex, shouldn't I keep it as visited.
• November 16th, 2013, 07:37
keepStriving
Re: Tackling problem
I've managed to sort out that problem and can now get the correct values for all individual vertexes and their respective adjacencies, though when I try to count them all together I get an array out of bound exception, otherwise it seems to work fine for individual inputs.

Code :

```int count = 0; for(int i = 0;i<10;i++){ count += graph.dfs(i, 2); } System.out.println(count);```

This is strange as if I don't do a for loop and do e.g. count += graph.dfs(2,2), I get the correct result.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last