larrytc

So, I was at the Worlds Science Festival the other day.  Ah, New York is a wonderful place to live.

There was an atheist group near one of the corners of the Washington Square park.  As I was walking by, some dude tried to give me a leaflet about doubting God, probably trying to lead me into buying the related book. (I forgot the title, though it was worded provocatively.. but not enough for me to remember it.  I guess it's tough to beat "The God Delusion".)

Of course, being the master New Yorker that I am, I was going into my "ignore people on the street" routine, when I thought better of it, and said, "You're preaching to the choir!"

The guy was flabbergasted, but quickly recovered enough to not be amused.

"You think this is funny?"

I just smiled and walked away.. (into the sunset)

So despite almost certainly advancing, I'll have to wake up early again tomorrow.  Joy.

	ArrayList[,] cache = new ArrayList[51,51];
	bool[,] done = new bool[51,51];	
	public ArrayList go( int left, int right ) {
		if ( done[left,right] ) return cache[left,right];
		int[] c = new int[26];
		for ( int i = left; i <= right; i++ )
			c[ s[i] - 'a' ]++;
			
		bool d = true;
		for ( int i = 0; i < 26; i++ ) if ( c[i] > 1 ) d = false;
		
		if ( d ) {
			ArrayList ret = new ArrayList();
			ret.Add( s.Substring( left, right - left + 1 ) );
			return ret;
		}
		
		ArrayList best = null;
		for ( int i = left; i < right; i++ ) {
			// split on between i, i, i + 1, right
			ArrayList now = go( left, i );
			ArrayList now2 = go( i + 1, right );

			for ( int k = 0; k < now2.Count; k++ ) now.Add( now2[k] );
			now.Sort();

			if ( best == null ) best = now;
			if ( better( now, best ) ) {
				best = new ArrayList();
				for ( int k = 0; k < now.Count; k++ ) best.Add( now[k] );
			}			
		}
		done[left,right] = true;
		cache[left,right] = best;
		return best;
	}