Thread: 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.

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.

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?

I was using long for "i" instead of int.Sorted that.

--- Update ---

How do you think I can move forward with this 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.

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.

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?

	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.

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

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.

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.

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.

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:

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:

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:

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:

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

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.

if(index==N){
	    		dfs(start,N);
	    	}

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.

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.

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.