package rec.probs;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Locale;

public class WordSolver {
	public class Piece{
		public final int row, column;
		public final char chr;
		public Piece(char chr, int row, int column){
			this.row = row;
			this.column = column;
			this.chr = chr;
		}

		@Override
		public boolean equals(Object o){
			if(o instanceof Piece == false) return false;
			Piece oth = (Piece) o;
			return oth.row == this.row && oth.column == this.column && oth.chr == this.chr;
		}

		@Override
		public String toString(){
			return this.row + "," + this.column + "=" + this.chr;
		}
	}

	private final Piece[][] grid;
	public static final Locale locale = Locale.forLanguageTag("tr");
	private final Piece[] adjacents = new Piece[8]; // For 4x4

	public WordSolver(char[][] grid){
		this.grid = new Piece[grid.length][];

		for(int i = 0; i < grid.length; i++){
			char[] row = grid[i];
			this.grid[i] = new Piece[row.length];
			int x = 0;

			for(char c : row){
				this.grid[i][x] = new Piece(Character.toLowerCase(c), i, x);
				x++;
			}
		}
	}

	public Piece getPiece(int row, int column){
		return isValid(row, column) ? this.grid[row][column] : null;
	}

	public boolean isValid(int row, int column){
		return row >= 0 && row < grid.length && column >= 0 && column < grid[row].length;
	}

	public void fillAdjacents(Piece piece, Piece[] adjacents, ArrayList<Piece> exclude){
		int index = 0;

		for(int column = piece.column - 1; column <= piece.column + 1; column++){
			for(int row = piece.row - 1; row <= piece.row + 1; row++){
				Piece adjacent = this.getPiece(row, column);

				if(adjacent != null && (row != piece.row || column != piece.column)){
					if(exclude != null && exclude.contains(adjacent)) continue;
					adjacents[index++] = adjacent;
				}
			}
		}

		if(index < adjacents.length) adjacents[index] = null;
	}

	public void permutate(ArrayList<Piece> head, Piece piece){
		if(head.size() == 0) head.add(piece);
		this.fillAdjacents(piece, adjacents, head);

		head.add(null);
		int index = 0, last = head.size() - 1;


		while(index < adjacents.length && adjacents[index] != null){
			Piece adjacent = adjacents[index++];

			head.set(last, adjacent);
			permutate(head, adjacent);
		}

		head.remove(last);
	}

	private boolean search(ArrayList<Piece> head, String word, Piece piece, int index){
		if(index == word.length()) return true;
		if(head.size() == 0) head.add(piece);
		Piece[] adjacents = new Piece[8];
		char cmp = word.charAt(index);
		this.fillAdjacents(piece, adjacents, head);
		head.add(null);
		int i = 0, last = head.size() - 1;

		while(i < adjacents.length && adjacents[i] != null){
			Piece p = adjacents[i++];

			if(p.chr == cmp){
				head.set(last, p);
				if(search(head, word, p, index + 1)) return true;
			}
		}

		head.remove(last);
		return false;
	}

	private final ArrayList<Piece> test = new ArrayList<Piece>();
	public boolean search(String word){
		word = word.trim().toLowerCase();
		char first = word.charAt(0);

		for(int r = 0; r < grid.length; r++){
			for(int c = 0; c < grid[r].length; c++){
				Piece p = this.grid[r][c];

				if(p.chr == first) test.clear();
				if(p.chr == first && this.search(test, word, p, 1)) return true;
			}
		}

		return false;
	}

	public static void main(String[] args) {
		WordSolver solver = new WordSolver(new char[][]{
				{'A', 'M', 'A', 'C'},
				{'L', 'T', 'I', 'I'},
				{'L', 'N', 'A', 'D'},
				{'Y', 'R', 'İ', 'Y'}
		});
		Locale.setDefault(locale);

		int count = 0;
		long start = System.currentTimeMillis();
		try {
			BufferedReader dict = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\Yengas\\Desktop\\WordList\\turkishWords.lst"), "UTF-8"));
			String line = null;

			while((line = dict.readLine()) != null){
				if(solver.search(line)){ System.out.println(line); count++; }
			}

			dict.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
				System.out.println("Took: " + (System.currentTimeMillis() - start) + "ms");
		System.out.println("Found: " + count);
	}

}