10422 - Knights in FEN

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10422 - Knights in FEN

Post by brianfry713 » Thu Sep 13, 2012 7:44 pm

Yes I know it's WA code, it's exactly the same code you posted as being WA code. Run your code on this input (copied from Sedefcho's post above):

Code: Select all

9
01011
110 1
01110
01010
00100
10110
01 11
10111
01001
00000
11111
01111
00 11
00001
00000
11111
01111
00110
00001
000 0
11111
0111 
00111
00001
00000
11111
00111 
00111
0 001
00000
11011
110 1
00110
01010
00100
11111
01111 
0011 
00001
00000
11111
01111 
0001 
10001
00000
If the output you get doesn't match:

Code: Select all

Unsolvable in less than 11 move(s).
Solvable in 7 move(s).
Solvable in 0 move(s).
Solvable in 3 move(s).
Solvable in 1 move(s).
Solvable in 8 move(s).
Unsolvable in less than 11 move(s).
Solvable in 2 move(s).
Solvable in 4 move(s).
(and it doesn't). Then that might help explain why that code is getting WA.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 10422 - Knights in FEN

Post by afruizc » Sun Dec 09, 2012 8:12 am

Im getting WA and I don't know why. My code passes all I/O posted int this thread. The idea is to run BFS for the first 10 layers, then stop. After that, I get the input and see if there is a solutions so far. If there is, I output it, if not, I output the "Unsolvable in less than 11 move(s).".

Here is my code:

Code: Select all

Cut after AC
Last edited by afruizc on Wed Dec 12, 2012 10:00 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10422 - Knights in FEN

Post by brianfry713 » Tue Dec 11, 2012 12:36 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

mourad.ghafiri
New poster
Posts: 6
Joined: Thu Dec 20, 2012 9:25 pm

10422 - Knights in FEN : WA !!!

Post by mourad.ghafiri » Sat Dec 22, 2012 8:58 am

hello guys please can you help me
i represent the problem as a graph and then i used the A* algorithm whit heuristic equals to the out of place knights it converges rapidly to the answer but i don't know where exatly the problem

here is my code

Code: Select all

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

class State implements Comparable<State>{
	String value;
	int hn;
	int gn=1;
	int fn;
	
	@Override
	public String toString() {
		return value+" "+hn+"\n";
	}

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

public class Knights_in_FEN {
	
	static char[][] initCong = {{'w','b','w','b','b'}, // sample
								{'b','b','w','e','b'},
								{'w','b','b','b','w'},
								{'w','b','w','b','w'},
								{'w','w','b','w','w'}};

	
	static char[][] goal = {{'b','b','b','b','b'},
						    {'w','b','b','b','b'},
						    {'w','w','e','b','b'},
						    {'w','w','w','w','b'},
						    {'w','w','w','w','w'}};
	
	static Vector<String> visited = new Vector<String>();

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		StringBuffer reslut = new StringBuffer("");
		
		int n = Integer.valueOf(in.nextLine());
		for (int i = 0; i <n; i++) {
			visited.clear();
			for (int j = 0; j < 5; j++) {
				String t = in.nextLine();
				for (int k = 0; k < 5; k++) {
					
					if(t.charAt(k)==' ') initCong[j][k]='e';
					if(t.charAt(k)=='1') initCong[j][k]='b';
					if(t.charAt(k)=='0') initCong[j][k]='w';
				}
			}
			
			State first = new State();
			first.value=boardToString(initCong);
			int nbr_steps = A_start(first); 
			if(nbr_steps!=-1) {
				if(i!=n-1) reslut.append("Solvable in "+nbr_steps+" move(s).\n");
				else reslut.append("Solvable in "+nbr_steps+" move(s).");
			}
			else{
				if(i!=n-1) reslut.append("Unsolvable in less than 11 move(s).\n");
				else reslut.append("Unsolvable in less than 11 move(s).");
			}
		}
		System.out.print(reslut);
		
		
	}
	
	
	
	static String boardToString(char[][] board){
		String sboard="";
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				sboard+=board[i][j];
			}
		}
		return sboard;
	}
	
	static char[][] StringToBoard(String sboard){
		char[][] board = new char[5][5];
		int i=0,j=0;
		
		for (int k = 0; k < sboard.length(); k++) {
			board[i][j]=sboard.charAt(k);
			j++;
			if(j==5){
				j=0;
				i++;
			}
		}
		return board;
	}
	
	static void printState(char[][] board){
		
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				System.out.print(board[i][j]+" ");
			}
			System.out.println();
		}
		
	}
	static boolean canImoveTo(char[][] board,int i,int j){
		if(i>=5 || j>=5 || i<0 || j<0 || board[i][j]!='e') return false;
		return true;
	}
	
	
	static int heuristic(char[][] board){
		int h=0;
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if(board[i][j]!=goal[i][j]) h++;
			}
		}
		
		return h;
	}
	
	static Vector<State> getNextStates(State state){
		Vector<State> nextstates = new Vector<State>();
		
		char[][] board;
		State s;
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				board=StringToBoard(state.value);
				if(board[i][j]!='e'){
					if(canImoveTo(board, i+1,j+2)){
						board[i+1][j+2]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					if(canImoveTo(board, i+1,j-2)){
						board[i+1][j-2]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					if(canImoveTo(board, i+2,j+1)){
						board[i+2][j+1]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					if(canImoveTo(board, i+2,j-1)){
						board[i+2][j-1]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					
					
					if(canImoveTo(board, i-1,j+2)){
						board[i-1][j+2]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					if(canImoveTo(board, i-1,j-2)){
						board[i-1][j-2]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					if(canImoveTo(board, i-2,j+1)){
						board[i-2][j+1]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
					if(canImoveTo(board, i-2,j-1)){
						board[i-2][j-1]=board[i][j];
						board[i][j]='e';
						s = new State();
						s.value=boardToString(board);
						s.hn=heuristic(board);
						nextstates.add(s);
						board=StringToBoard(state.value);
					}
					
				}
			}
		}
		
		return nextstates;
	}
	
	static int A_start(State s0){
		
		PriorityQueue<State> queue = new PriorityQueue<State>();
		queue.add(s0);
		String sgoal = boardToString(goal);
		
		while(!queue.isEmpty()){
			
			State s = queue.poll();
			if(s.gn>10) return -1;
			if(s.value.compareTo(sgoal)==0) return s.gn-1;
			
			
			visited.add(s.value);
			Vector<State> nextstates = getNextStates(s);
			
			for (int i = 0; i < nextstates.size(); i++) {
				if(!visited.contains(nextstates.elementAt(i))){
					nextstates.elementAt(i).gn+=s.gn;
					nextstates.elementAt(i).fn=nextstates.elementAt(i).gn+nextstates.elementAt(i).hn;
					 queue.add(nextstates.elementAt(i));
				}
			}
		}
		
		return -1;
	}
}
or if someone of you does have some samples of inputs and correct outputs for this problem.

my solution gives as a result for some samples :

Code: Select all

9
01011 
110 1 
01110 
01010 
00100 
10110 
01 11 
10111 
01001 
00000 
11111
01111 
00 11 
00001 
00000 
11111 
01111 
00110 
00001 
000 0
11111 
0111  
00111 
00001 
00000
11111 
00111  
00111 
0 001 
00000
11011 
110 1 
00110 
01010 
00100
11111 
01111  
0011  
00001 
00000
11111
01111  
0001  
10001 
00000
Unsolvable in less than 11 move(s).
Solvable in 7 move(s).
Solvable in 0 move(s).
Solvable in 3 move(s).
Solvable in 1 move(s).
Solvable in 8 move(s).
Unsolvable in less than 11 move(s).
Solvable in 2 move(s).
Solvable in 4 move(s).

mourad.ghafiri
New poster
Posts: 6
Joined: Thu Dec 20, 2012 9:25 pm

Re: 10422 - Knights in FEN : WA !!!

Post by mourad.ghafiri » Sun Dec 23, 2012 3:58 am

ok it works fine...

it has just problem in using StingBuffred ; i used a direct System.out.println and it works :)

and i had a shift in the cost (gn) ... it must start with 0 .

Post Reply

Return to “Volume 104 (10400-10499)”