10067 - Playing with Wheels

[mehankit7]

While submitting the following code, I am getting run time error!! .. Please Help.

Code: Select all

import java.util.*;
import java.io.*;

public class Wheels {
	public static void main(String[] args) throws IOException{
		BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(inp.readLine());
		while(test>0){
			String start = inp.readLine();
			StringTokenizer sm = new StringTokenizer(start," ");
			String temp = new String("");
			while(sm.hasMoreTokens()){
				temp = temp+sm.nextToken();	
			}
			int st = Integer.parseInt(temp);
			String end = inp.readLine();
			StringTokenizer sm2 = new StringTokenizer(end," ");
			String temp2 = new String("");
			while(sm2.hasMoreTokens()){
				temp2 = temp2 + sm2.nextToken();
			}
			int en = Integer.parseInt(temp2);
			int f = Integer.parseInt(inp.readLine());
			int forbid[] = new int[f];
			int i =0;
			while(i<f){
				String temp3 = new String("");
				StringTokenizer z = new StringTokenizer(inp.readLine()," ");
				while(z.hasMoreTokens()){
					temp3 = temp3+z.nextToken();
				}
				forbid[i] = Integer.parseInt(temp3);
				i++;		
			}
			System.out.println(compute(st,en,forbid));
			if(test!=1){
				String s = inp.readLine();
			}
			test--;
		}
	}

	public static int compute(int st, int end, int[] forbid){
		if(st==end) return 0;
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.offer(st);
		HashMap<Integer,Boolean> discovered = new HashMap<Integer,Boolean>();
		discovered.put(st,true);
		HashMap<Integer,Integer> cost = new HashMap<Integer,Integer>();
		cost.put(st,0);
		while(!q.isEmpty()){

			int current = q.poll();
			int k = 0;
			int[] child = construct(current);
			while(k<8){
				if(child[k]==end)return cost.get(current)+1;
				if(!search(forbid,child[k])){
					if(!discovered.containsKey(child[k])){
						discovered.put(child[k],true);
						q.offer(child[k]);
						cost.put(child[k],cost.get(current)+1);
					}
				}
				k++;
			}
		}
		return -1;
	}

	public static boolean search(int[] forbid,int val){
		for(int i =0;i<forbid.length;i++){
			if(forbid[i]==val) return true;
		}
		return false;
	}

	public static int[] construct(int current){
		int res[] = new int[8];
		int digs[] = new int[4];
		digs[3] = current%10;
		int temp = (current%100);
		digs[2] = temp/10;
		digs[1] = (current%1000)/100;
		digs[0] = (current%10000)/1000;

		if(digs[0]==9) {
			res[0] = digs[1]*100 + digs[2]*10 + digs[3];
		}
		else{
			res[0] = (digs[0]+1)*1000 + digs[1]*100 + digs[2]*10 + digs[3];
		}
		if(digs[1]==9) {
			res[1] = digs[0]*1000 + digs[2]*10 + digs[3];
		}
		else{
			res[1] = (digs[1]+1)*100 + digs[0]*1000 + digs[2]*10 + digs[3];
		}
		if(digs[2]==9) {
			res[2] = digs[0]*1000 + digs[1]*100 + digs[2]*0 + digs[3];
		}
		else{
			res[2] = digs[0]*1000 + digs[1]*100 + (digs[2]+1)*10 + digs[3];
		}
		if(digs[3]==9) {
			res[3] = digs[0]*1000 + digs[1]*100 + digs[2]*10 + digs[3]*0;
		}
		else{
			res[3] = (digs[0])*1000 + digs[1]*100 + digs[2]*10 + digs[3]+1;
		}


		if(digs[0]==0) {
			res[4] = 9000 + digs[1]*100 + digs[2]*10 + digs[3];
		}
		else{
			res[4] = (digs[0]-1)*1000 + digs[1]*100 + digs[2]*10 + digs[3];
		}
		if(digs[1]==0) {
			res[5] = digs[0]*1000 + digs[2]*10 + digs[3]+900;
		}
		else{
			res[5] = (digs[1]-1)*100 + digs[0]*1000 + digs[2]*10 + digs[3];
		}
		if(digs[2]==0) {
			res[6] = 90+digs[0]*1000 + digs[1]*100 + digs[2]*0 + digs[3];
		}
		else{
			res[6] = digs[0]*1000 + digs[1]*100 + (digs[2]-1)*10 + digs[3];
		}
		if(digs[3]==0) {
			res[7] = 9+digs[0]*1000 + digs[1]*100 + digs[2]*10 + digs[3]*0;
		}
		else{
			res[7] = (digs[0])*1000 + digs[1]*100 + digs[2]*10 + digs[3]-1;
		}
		return res;

	}
}

[mehankit7]

I think its giving NumberFormatException. But do not know why! Please help!

[Monty]

Tried every test case in this thread and I pass all of them, still I keep getting WA.. Not sure what else to do, I made sure I handled cases where the start is the target, the target is in the forbidden list, 9+1 goes to 0, 0-1 goes to 9. Are there any other elementary cases I could be tripping up on? Thanks


10 Cases:

Code: Select all

10
9 9 9 9
9 9 9 9
1
9 9 9 9

9 9 9 9
0 0 0 0
1
0 0 0 0

9 9 9 9
0 0 0 0
1
9 9 9 9

3 3 4 2
1 2 0 9
1
3 4 4 2

9 9 9 9
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5

9 9 9 9
0 0 1 1
3
8 9 0 7
6 5 4 2
2 3 4 5

0 0 0 0
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5

1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
6 5 7 9
8 5 7 9

1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
0 0 0 0
8 5 7 9

1 7 1 0
7 0 0 0
6
1 9 0 7
1 4 2 2
1 3 4 5
4 4 4 4
2 5 0 9
1 1 7 9

My Output:

Code: Select all

0
-1
4
10
5
6
1
11
11
8

[brianfry713]

AC output for your input:

Code: Select all

-1
-1
-1
10
5
6
1
11
11
8

[Monty]

But even the UVA toolkit returns exactly what I have for that input... Check it out

http://uvatoolkit.com/problemssolve.php#10067

Is it wrong then?

Thanks

[brianfry713]

On this case:
1
9 9 9 9
0 0 0 0
1
9 9 9 9

The code I just submitted and got AC with returns -1, if you'd rather believe your WA code and UVAtoolkit's 4 that's up to you, let us know if you can get AC with that logic. Others in this thread that have got AC agreed that it should be -1.

[Monty]

Alright, even after altering my code to produce the same results as yours for the first three cases I still get WA. Is there any other critical input that could be messing it up? I thought it could be the formatting so I removed the new line from the last output (which has never been an issue in other problems), still WA after 1.1 seconds. Thanks

[brianfry713]

No critical input besides what you've posted, I used a straightforward BFS.

[drseergio]

I believe I have written a working solution in Java yet I get rejections because of "runtime error". It seems to be caused by NumberFormatException during input>int conversion. I do not understand what sort of input is being provided to cause it. I have tried all test cases from this thread plus some additional ones and it works just fine on my machine. I've tried several variations of the integer conversion code and I still get the same result.

Does anyone has ideas on what could be causing problems here? I've seen similar threads from other Java folks without any follow-up.

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

class Main {
  public static int COMBINATIONS = 10000;

  static class Graph {
    public EdgeNode[] edges;
    public boolean[] invalid;
    public boolean[] discovered;
    public int[] parent;

    class EdgeNode {
      public Integer y;
      public EdgeNode next;

      public EdgeNode(Integer y) {
        this.y = y;
      }
    }

    public Graph() {
      edges = new EdgeNode[COMBINATIONS];
      parent = new int[COMBINATIONS];
      invalid = new boolean[COMBINATIONS];
      discovered = new boolean[COMBINATIONS];

      for (int i = 0; i < COMBINATIONS; i++) {
        List<Integer> neighbors = getNeighbors(i);
        Iterator<Integer> it = neighbors.iterator();

        while (it.hasNext()) {
          insertEdge(i, it.next(), true);
        }
      }
    }

    public void bfs(int start) {
      int v, y;
      EdgeNode p;

      for (int i = 0; i < COMBINATIONS; i++) {
        parent[i] = -1;
        discovered[i] = false;
      }

      LinkedList<Integer> queue = new LinkedList<Integer>();
      queue.add(start);
      discovered[start] = true;

      while (!queue.isEmpty()) {
        v = queue.pollLast();
        p = this.edges[v];

        while (p != null) {
          y = p.y;
          if (!invalid[y] && !discovered[y]) {
            queue.push(y);
            discovered[y] = true;
            parent[y] = v;
          }
          p = p.next;
        }
      }
    }

    public int findPath(int start, int end) {
      if ((start == end) || (end == -1)) {
        return 0;
      } else {
        return 1 + findPath(start, parent[end]);
      }
    }

    private void insertEdge(int x, int y, boolean directed) {
      EdgeNode node = new EdgeNode(y);
      node.next = this.edges[x];
      this.edges[x] = node;
    }

    private List<Integer> getNeighbors(Integer combination) {
      List<Integer> neighbors = new LinkedList<Integer>();
      int digit, temp = combination;

      for (int i = 0; i < 4; i++) {
        digit = temp % 10;
        temp = temp / 10;

        if (digit == 0) {
          neighbors.add(combination + 9 * (int) Math.pow(10, i));
          neighbors.add(combination + (int) Math.pow(10, i));
        } else if (digit == 9) {
          neighbors.add(combination - 9 * (int) Math.pow(10, i));
          neighbors.add(combination + (int) -Math.pow(10, i));
        } else {
          neighbors.add(combination + (int) -Math.pow(10, i));
          neighbors.add(combination + (int) Math.pow(10, i));
        }
      }

      return neighbors;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int cases = Integer.parseInt(br.readLine().trim()), invalidCases = 0, source = 0, destination = 0;
    Graph graph = new Graph();

    for (int y = 0; y < cases; y++) {

      source = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));
      destination = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));

      invalidCases = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));

      for (int i = 0; i < invalidCases; i++) {
        graph.invalid[Integer.parseInt(br.readLine().replaceAll("[^0-9]", ""))] = true;
      }

      graph.bfs(source);

      if (graph.parent[destination] == -1) {
        sb.append("-1\n");
      } else {
        sb.append(graph.findPath(source, destination) + "\n");
      }

      if (y != (cases-1)) {
        br.readLine();
      }
    }

    System.out.print(sb);
  }
}

[brianfry713]

My AC C++ code reads the input using cin >> int.

[drseergio]

I've been solving another problem and ran into a similar problem. I think the issue is with how I use BufferedReader. In the other problem I was able to fix it by using Scanner object. I will check this out further and will update the thread once I am able to submit it.

[ygge]

I had the same problem, got Runtime error for my submission in Java.
I played around a bit and got it to accepted when i didn't assume that there was an empty row between test cases but instead read row after row until I got a row that had som info when I needed it:

Code: Select all

    private static int parseNumber(BufferedReader in) throws IOException {
        String row;
        while ((row = in.readLine()).trim().length() == 0);
        return Integer.parseInt(row.replaceAll(" ", ""), 10);
    }

[achan8501]

On this case:
1
9 9 9 9
0 0 0 0
1
9 9 9 9

The code I just submitted and got AC with returns -1, if you'd rather believe your WA code and UVAtoolkit's 4 that's up to you, let us know if you can get AC with that logic. Others in this thread that have got AC agreed that it should be -1.

My AC code returns 4 on that input, but -1 for
1
9 9 9 9
0 0 0 0
1
0 0 0 0
One can only assume that the case you proposed was not in the test data at all.

Edit: In fact, my output matches his line for line, so there should be no troublesome cases in the judge at all.

[mourad.ghafiri]

i used the most efficient algorithm and also i handled all cases i think it'll give a wrong answer but still wrong answer ...

any one can help!!

Code: Select all

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;

class LockState implements Comparable<LockState>{
	String value;
	int hn=0;
	int gn=1;
	int fn=0;
	LockState prev=null;
	
	public LockState() {
		
	}
	
	public LockState(String value) {
		this.value=value;
	}
	
	@Override
	public String toString() {
		return this.value + " fn = "+this.fn;
	}

	public int compareTo(LockState s) {
		if(this.fn==s.fn) return 0;
		else if(this.fn>s.fn) return 1;
		else return -1;
	}
	
}

public class Main{
	
	static Vector<String> Visited = new Vector<String>();
	static String initCong = "";
	static String goalConf = "";
	public static void main(String[] args) {
	
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int nf ;
		
		
		for (int i = 0; i < n; i++) {
			String forbidden;
			Visited.clear();
			initCong="";
			goalConf="";
			if(i != 0) in.nextLine();
			for (int j = 0; j < 4; j++) {
				initCong+= String.valueOf(in.nextInt());
			}
			
			for (int j = 0; j < 4; j++) {
				goalConf+= String.valueOf(in.nextInt());
			}

			nf = in.nextInt();
			for (int j = 0; j < nf; j++) {
				forbidden="";
				for (int k = 0; k < 4; k++) {
					forbidden+= String.valueOf(in.nextInt());
				}
				Visited.add(forbidden);
			}
			
			if(i!=n-1){
				System.out.print(A_Star(new LockState(initCong)));
			}
			else {
				System.out.println(A_Star(new LockState(initCong)));
			}
		}

	}
	
	static int heuristic(String state){
		int g=0;
		for (int i = 0; i < state.length(); i++) {
			int xi= state.charAt(i) - 48;
			int xj= goalConf.charAt(i) - 48;
			if((xi<5 && xj>5) || (xi>5 && xj<5)){
				g+=(10-Math.abs(xi-xj))%10;
			}
			else g+=(Math.abs(xi-xj))%10;
		}
		
		return g;
	}
	

	
	static Vector<LockState> getNextStates(LockState state){
		Vector<LockState> neighbours = new Vector<LockState>();
		LockState next;
		for (int i = 0; i < state.value.length(); i++) {
			char[] tabchar = state.value.toCharArray();
			int charint = state.value.charAt(i)-48;
			if(charint==0){
				tabchar[i]='1';
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
				
				tabchar[i]='9';
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
			}
			else {
				tabchar[i]=(char)('0'+(charint+1)%10);
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
				
				tabchar[i]=(char)('0'+(charint-1)%10);
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
			}
		}

		return neighbours;
	}
	
	static int A_Star(LockState s0){
		PriorityQueue<LockState> prqueue = new PriorityQueue<LockState>();
		Vector<LockState> nexts;
		if(initCong.compareTo(goalConf)==0) return 0;
		if(Visited.contains(goalConf)) return -1;
		prqueue.add(s0);	
		while(!prqueue.isEmpty()){
			LockState test = prqueue.poll();
			if(test.value.equals(goalConf)){

				return test.gn-1;
			}
			
			Visited.add(test.value);
			
			nexts=getNextStates(test);
			
			for (int i = 0; i < nexts.size(); i++) {
				if(!Visited.contains(nexts.elementAt(i).value)){
					nexts.elementAt(i).prev=test;
					nexts.elementAt(i).gn+=test.gn;
					nexts.elementAt(i).fn=nexts.elementAt(i).gn+nexts.elementAt(i).hn;
					prqueue.add(nexts.elementAt(i));
				}
			}

		}
		return -1;
	}
	
}

[mourad.ghafiri]

finally it is AC
i had a problem in the heuristic function it is incorrect and also i replaced system.out.println in each case by a BuffredString to add up the reslt of each case
and here it is , it works
thank you guys for !!