CodeEval-Hard-Challenge-182

CodeEval-Hard-Challenge-182.cs

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

namespace CodeEval
{
	internal class Program
	{
		// Hard, longest path of unique characters
		// https://www.codeeval.com/open_challenges/182/

		private static void Main(string[] args)
		{
			var sw = new Stopwatch(); sw.Start();
			//string[] l = System.IO.File.ReadAllLines(args[0]);
			string[] l = {"qttiwkajeerhdgpikkeaaabwl" ,	"vavprkykiloeizzt","skwajgaaxqpfcxmadpwaraksnkbgcaukbgli","kaja",	"bjzanjikh"};

			// Observe the following properties
			// - UNIQUE string
			// - only chars a-z
			// Strategy: 
			// - Save current chars in a bool array 0-25 ( 'a'-'a' = 0 )
			//	- Breadth Depth Search -> all directions, starting from every position. (neighbours are automatically canceled due to unique-string property)			

			foreach (string tc in l)
			{
				int result = 0, sizeN = (int)Math.Sqrt(tc.Length);
				char[][] matrix = new char[sizeN][];
				var q = new Queue<Tuple<int, int, int, bool[]>>();	// x, y, chars processed
				for (int i = 0; i < sizeN; i++)
				{
					matrix[i] = new char[sizeN];
					for (int j = 0; j < sizeN; j++)
					{
						matrix[i][j] = tc[(i * sizeN) + j];
						// add starting point to queue
						q.Enqueue(new Tuple<int, int, int, bool[]>(i, j, 0, new bool[26]));
					}

					//Console.WriteLine(String.Join(",",matrix[i]));
				}
				// start searching brah!
				while (q.Count > 0)
				{
					var curItem = q.Dequeue();
					int x = curItem.Item1, y = curItem.Item2, index = matrix[x][y] - 'a';

					// check uniqueness -> optimization 1, do this before copy array
					if (curItem.Item4[index]) { continue; }
					bool[] chars = new bool[26];
					// you NEED to make a copy, otherwise the reference array is passed around in various tuples
					Array.Copy(curItem.Item4, chars, 26);	

					chars[index] = true;

					// check length
					//int curLength = curItem.Item4.Count(a => a); // optimization 2! LINQ is expensive, just pass the count around, it will only increase
					int curLength = curItem.Item3 + 1;
					if (curLength > result) { result = curLength; }
					
					// add neighbours
					if (x - 1 >= 0) { q.Enqueue(new Tuple<int, int, int, bool[]>(x - 1, y, curLength, chars)); }
					if (x + 1 < sizeN) { q.Enqueue(new Tuple<int, int, int, bool[]>(x + 1, y, curLength, chars)); }
					if (y - 1 >= 0) { q.Enqueue(new Tuple<int, int, int, bool[]>(x, y - 1, curLength, chars)); }
					if (y + 1 < sizeN) { q.Enqueue(new Tuple<int, int, int, bool[]>(x, y + 1, curLength, chars)); }
				}
				Console.Out.WriteLine(result);
			}
			sw.Stop();
			Console.WriteLine(String.Format("Done in {0} ticks", sw.ElapsedTicks));
			Console.ReadLine();
		}
	}
}