package com.gmail.bleed1979.ptt;

import java.util.ArrayList;
import java.util.List;

public class Battle {
	
	private static boolean isLegal(StringBuffer[][] table, int people, int sleep) {
		//	check bigger than sleep
		for(int j = 0; j < table[0].length; ++j) {
			int counter = 0;
			for(int i = 0; i < table.length; ++i) {
				if(table[i][j].length() > 0 && table[i][j].toString().equals("sleep")) {
					++counter;
				}
			}
			if(counter > sleep) {
				return false;
			}
		}
		
		//	check different round
		for(int j = 0; j < table[0].length; ++j) {
			int[] fight = new int[people + 1];
			for(int i = 0; i <= people; ++i) {
				fight[i] = 0;
			}
			for(int i = 0; i < table.length; ++i) {
				if(table[i][j].length() > 0 && !table[i][j].toString().equals("sleep")) {
					String[] array = table[i][j].toString().split("_");
					int i1 = Integer.parseInt(array[0]);
					int i2 = Integer.parseInt(array[1]);
					fight[i1] += 1;
					fight[i2] += 1;
					for(int k = 0; k <= people; ++k) {
						if(fight[k] > 1) {
							return false;
						}
					}
				}
			}
		}
		return true;
	}
	
	private static void dfs(StringBuffer[][] table, List<String> list, int index, int sleep, StringBuffer flag) {
		if("false".equals(flag.toString())) {
			if(index == list.size()) {
				flag = new StringBuffer("true");
			} else {
				for(int i = 0; i < table.length; ++i) {
					for(int j = 0; j < table[i].length; ++j) {
						if(table[i][j].length() == 0) {
							table[i][j].append(list.get(index));
							if(isLegal(table, list.size(), sleep)) {
								dfs(table, list, index + 1, sleep, flag);
								if("true".equals(flag.toString())) {
									break;
								}
							}
							table[i][j] = new StringBuffer();
						}
					}
					if("true".equals(flag.toString())) {
						break;
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		final int round = 6, people = 8;
		int sleep = 6 - (8 / 2);
		
		//	generate string
		List<String> list = new ArrayList<String>();
		int[] fight = new int[people + 1];
		for(int i = 0; i <= people; ++i) {
			fight[i] = 0;
		}
		
		for(int i = 1; i <= people; ++i) {
			for(int k = 0; k < list.size(); ++k) {
				String[] array = list.get(k).split("_");
				if(array[1].equals("" + i)) {
					++fight[i];
				}
			}
			for(int j = people; j >= 1; --j) {
				if(i != j && fight[i] < round) {
					boolean flag = false;
					for(int k = 0; k < list.size(); ++k) {
						String[] array = list.get(k).split("_");
						String str1 = "" + i;
						String str2 = "" + j;
						if((str1.equals(array[0]) && str2.equals(array[1])) || 
								(str1.equals(array[1]) && str2.equals(array[0])) || 
								fight[j] >= round) {
							flag = true;
							break;
						}
					}
					if(flag) {
						continue;
					} else {
						String str = i + "_" + j;
						list.add(str);
						++fight[i];
					}
				}
			}
		}
		System.out.println("list size is " + list.size());
		for(int i = 0; i < round * sleep; ++i) {
			list.add("sleep");
		}
		for(int i = 0; i < list.size(); ++i) {
			System.out.println(list.get(i));
		}
		System.out.println("total need " + list.size());
		
		StringBuffer[][] table = null;
		for(int i = 6; i <= 100; ++i) {	//	i is time section
			System.out.print(i + " ");
			StringBuffer sbGameOver = new StringBuffer("false");
			
			table = new StringBuffer[round][i];
			for(int j = 0; j < round; ++j) {
				for(int k = 0; k < i; ++k) {
					table[j][k] = new StringBuffer();
				}
			}
			
			dfs(table, list, 0, sleep, sbGameOver);
			if("true".equals(sbGameOver.toString())) {
				break;
			}
		}
		
		if(table != null) {
			System.out.println("answer is");
			for(int i = 0; i < table.length; ++i) {
				for(int j = 0; j < table[i].length; ++j) {
					System.out.print(table[i][j] + "  ");
				}
				System.out.println();
			}
		} else {
			System.out.println("no answer");
		}
	}
}