/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu

in C#: Michael Gärtner
************************************************/

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;

namespace Logofatu
{
    class P12Compactation
    {
        private static CultureInfo englishCulture = CultureInfo.CreateSpecificCulture("en-US");

        private static String FileInputName = "tests.in";
        private static String FileOutputName = "tests.out";

        private static bool comaptibleCharacters(char c1, char c2)
        {
            return c1.Equals(c2) || c1.Equals('X') || c2.Equals('X');
        }

        private static bool compatibleLines(string str1, string str2)
        {
            int len = str1.Length;
            if ( len != str2.Length )
                return false;
            for ( int i = 0; i < len; i++ )           
                if ( !comaptibleCharacters(str1[i], str2[i]) )
                    return false;
            return true;
        }

        private static char mergeChars(char c1, char c2)
        {
            return comaptibleCharacters(c1, c2) ? (c1.Equals('X') ? c2 : c1) : '*';
        }

        private static String mergeLines(string str1, string str2)
        {
            int len = str1.Length;
            if ( len != str2.Length )
                return null;
            char[] chars = new char[len];
            for ( int i = 0; i < len; i++ )
                chars[i] = mergeChars(str1[i], str2[i]);
            return new String(chars);
        }

        private static void recExactCompact(List<String> v, List<String> vRet)
        {
            List<String> vCopy = new List<String>(v);
            bool compact = true;
            for ( int i = 0; i < vCopy.Count - 1; i++ )           
                for ( int j = i+1; j < vCopy.Count; j++ )
                    if ( compatibleLines(vCopy[i],vCopy[j]) )
                    {
                        compact = false;
                        String str = mergeLines(vCopy[i], vCopy[j]);
                        vCopy.RemoveAt(i);
                        vCopy.RemoveAt(j - 1);
                        vCopy.Add(str);
                        recExactCompact(vCopy, vRet);
                    }
            if ( compact )
            {
                if ( vRet.Count > vCopy.Count )
                {
                    vRet.Clear();
                    for ( int i = 0; i < vCopy.Count; i++ )
                        vRet.Add(vCopy[i]);                    
                }
                return;
            }
        }

        private static double doRecExactCompact(List<String> v, List<String> vRet, StreamWriter sw)
        {
            recExactCompact(v, vRet);
            sw.Write(v.Count); sw.Write(' ');
            sw.WriteLine(v[0].Length);
            sw.Write(vRet.Count); sw.Write(' ');
            sw.Write((vRet.Count * 100.0 / v.Count).ToString("F4",englishCulture));
            sw.WriteLine('%');
            sw.WriteLine();
            foreach ( String s in vRet )
            {
                sw.WriteLine(s);
            }
            return vRet.Count * 100.0 / v.Count;
        }

        static void Main(string[] args)
        {
            StreamReader sr = null;
            StreamWriter sw = null;
            try
            {
                sw = new StreamWriter(FileOutputName);
                sr = new StreamReader(FileInputName);
                List<String> v = new List<string>();
                while ( !sr.EndOfStream )
                {
                    v.Add(sr.ReadLine());
                }
                List<String> vRet = new List<string>(v);
                doRecExactCompact(v, vRet, sw);
            }
            catch ( IOException ex )
            {
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex.ToString());
            }
            finally
            {
                if ( sr != null )
                {
                    sr.Close();
                }
                if ( sw != null )
                {
                    sw.Close();
                }
            }
        }
    }
}