ダメダメ日記

code jamの練習問題File fix-itを考えてみた。
http://code.google.com/codejam/contest/dashboard?c=635101#s=p0
ディレクトリを探索して、与えられたディレクトリ階層を作るために既存ディレクトリに
後何回mkdirしなければならないかを解く問題。
ディレクトリ階層はツリー構造なので、ツリー構造のトラバーサルで解くべき問題なのだと
思ったのだが、ツリーのデータ構造をさくっとかけない私は、
何かもっと別の方法で強引にとけないかと、色々考えてみた。


思いついたのは、ArrayListを二次元にした可変調の二次元配列に
そのまんまディレクトリ階層を読み込んで、重複を読み飛ばして何個異なるtokenが
存在するかをカウントし、そこから既存のディレクトリ数を引けばいいのではないかと
なぜか思った。すくなくともサンプル入力を机上でとくことを考えると
それでもうまくいきそうに思えた。
ところが人間にとって簡単なこの解き方は、コードにしようとすると中々うまくいかない。

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

public class CountDir {
	public static void main(String[] args) {
		int cases; 	//ケース数
		int existsCount;	//既存dir数
		int createCount;	//欲しいdir数

		//可変二次元配列の行
		ArrayList<Object> listRows = new ArrayList<Object>();	

		try {
			//ケース数、既存dir数、欲しいdir数などを読み込む
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			cases = Integer.parseInt(reader.readLine());	//ケース数読み込み

			//StringTokenizerでスペース区切りのトークンを分解
			StringTokenizer st = new StringTokenizer(reader.readLine());
			existsCount = Integer.parseInt(st.nextToken());	//既存dir数取得
			createCount = Integer.parseInt(st.nextToken());	//欲しいdir数取得

			//ケースの一行目を先に読み込む
			String line = reader.readLine();

			int maxColumnLength = 0;	//カラムの最大長

			//各ケース回ループ
			for(int i = 0; i < cases; ){

				//スラッシュで始まっている場合、dir行として読み込む
				if(line.charAt(0) == '/'){

					//カラムの長さ
					int ColumnLength = 0;
						
					//可変二次元配列の列
					ArrayList<String> listColumn = new ArrayList<String>();
				
					//スラッシュを区切り文字としてdirをtokenに区切る
					st = new StringTokenizer(line, "/ ");
					
					//dirの一行分トークンを一つずつ読み込む
					while(st.hasMoreTokens()) {
						String token = st.nextToken();
						listColumn.add(token);
						ColumnLength++;
					}

					//カラムの長さが最大なら更新
					if(ColumnLength > maxColumnLength){
						maxColumnLength = ColumnLength;
					}

					//一行分のColumnをRowに追加
					listRows.add(listColumn);

					//読み終われば次の行を読む
					line = reader.readLine();

				//スペースで始まれる行で終了させるための仮の処置
				} else if(line.charAt(0) == ' ') {
					i++;	//ケース数をインクリメント

					//前ケースの結果表示部
					for(int k = 0; listRows.size() > k; k++){
						ArrayList<String> listColumn = new ArrayList<String>();
						listColumn = (ArrayList)listRows.get(k);

						for(int j = 0; listColumn.size() > j; j++){
							System.out.println(listColumn.get(j));
						}
					}

					//可変二次元配列の行を初期化
					listRows = new ArrayList<Object>();	

				//スラッシュで始まらない場合はケースの結果表示後次のケースのdir数の行として読み込む
				} else {
					int ans = 0;		//答え
					int missMatch = 0; 	//不一致
					int displayCase = i + 1;//表示するケース番号
					
					//コピー用二次元配列(行と列が逆)
					String copyTables[][] = new String[maxColumnLength][listRows.size()];

					//コピー用二次元配列にコピー
					for(int x = 0; listRows.size() > x; x++){
						for(int y = 0; ((ArrayList)listRows.get(x)).size() > y; y++){
							copyTables[y][x] = (String)((ArrayList)listRows.get(x)).get(y);
						}
					}
	
					//コピー用二次元配列にコピー
					for(int x = 0; copyTables.length > x; x++){
						for(int y = 0; copyTables[x].length > y; y++){
							for(int z = ((ArrayList)listRows).size()-1; z > 0; z--){
								//要素数が大きすぎないか
								if((x >= (((ArrayList)listRows.get(y)).size()) == false)&&(copyTables[x][z] != null)){
									if(copyTables[x][z].equals((String)((ArrayList)listRows.get(y)).get(x)) == false){
										//不一致数インクリメント、重複カウント防止
										missMatch++;
										copyTables[x][z] = (String)((ArrayList)listRows.get(y)).get(x);
									}
								}
							}
						}
						//下階層があればインクリメント
						missMatch++;
					}
									
					//結果表示
					ans = missMatch - existsCount;
					System.out.println("Case #" + displayCase + ": " + ans);

					//Tokenizerで分解
					st = new StringTokenizer(line);
					
					//既存dir数取得			
					existsCount = Integer.parseInt(st.nextToken());	
	
					//欲しいdir数取得
					createCount = Integer.parseInt(st.nextToken());	

					//可変二次元配列の行を初期化
					listRows = new ArrayList<Object>();		

					line = reader.readLine();	//次の行を読み込み
					i++;			//ケース数をインクリメント
					maxColumnLength = 0;	//カラム最大長をリセット

				}
			}

		}catch(Exception e) {
			System.out.println(e);
		}
	}
}


こんな感じで書いてみた。
基本的には一旦ArrayListの二次元配列にディレクトリ構造をそのまんま表のように読み込んで、
階層構造を根からたどる都合上一時的に固定長二次元配列にいれてループをまわし、
異なるディレクトリがでてくるたびにカウントし、下の階層にいくときにもカウントする、
というふうにカウントを増やした後、既存ディレクトリの数だけカウントを減らしてみた。
結果は全然だめ。
なんだろう、下の階層へいくときのインクリメントが余計な仕事をしているようにも思えるのだが、
そもそもやっぱりツリー構造のトラバーサルで解かないとだめなのだろうか・・・