using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using XenoGears.Assertions;
using XenoGears.Functional;
using XenoGears.Logging.Formatters;

namespace Editor
{
    public static class Program
    {
        #region Utils
        
        private static void Dump(this Object o)
        {
            if (Equals(o, String.Empty)) Console.WriteLine();
            else Console.WriteLine(o.ToLog());
        }

        static Program()
        {
            for (var i = 0; i < top; ++i)
            {
                fs[i] = int.MinValue;
                fpn[i] = int.MinValue;
                fpm[i] = int.MinValue;
                fpd[i] = "?";

                for (var j = 0; j < top; ++j)
                {
                    gs[i, j] = int.MinValue;
                    gpn[i, j] = int.MinValue;
                    gpm[i, j] = int.MinValue;
                    gpd[i, j] = "?";
                }
            }
        }

        static void print(int[] a)
        {
            var ss = new string[a.Width()];
            for (var i = 0; i < a.Width(); ++i)
            {
                ss[i] =
                    a[i] == int.MaxValue ? "*" :
                    a[i] == int.MinValue ? "?" :
                    a[i].ToString();
            }

            print(ss);
        }

        static void print(int[,] a)
        {
            var ss = new string[a.Height(), a.Width()];
            for (var i = 0; i < a.Height(); ++i)
            {
                for (var j = 0; j < a.Width(); ++j)
                {
                    ss[i, j] =
                        a[i, j] == int.MaxValue ? "*" :
                        a[i, j] == int.MinValue ? "?" :
                        a[i, j].ToString();
                }
            }

            print(ss);
        }

        static void print(string[] a)
        {
            Console.WriteLine(a.StringJoin());
        }

        static void print(string[,] a)
        {
            var cols = new int[a.Width()];
            for (var j = 0; j < a.Width(); j++)
            {
                cols[j] = j.ToString().Length;
            }

            for (var i = 0; i < a.Height(); i++)
            {
                for (var j = 0; j < a.Width(); j++)
                {
                    var len = a[i, j].Length;
                    if (cols[j] < len) cols[j] = len;
                }
            }

//            var max_col = cols.Max();
            var all_col = cols.Sum();
            var max_row = a.Height().ToString().Length;

            var buf = new StringBuilder();
//            buf.Append("".PadRight(max_row) + "   ");
//            0.UpTo(a.Width() - 1).ForEach(j =>
//            {
//                buf.Append(j.ToString().PadRight(cols[j]));
//                buf.Append(j.ToString().PadRight(max_col));
//                if (j < a.Width() - 1) buf.Append(" ");
//            });
//            buf.Append(Environment.NewLine);

//            buf.Append("".PadRight(max_row) + "   ");
//            buf.Append(new String('-', all_col + a.Width() - 1));
//            buf.Append(new String('-', a.Width() * (max_col + 1) - 1));
//            buf.Append(Environment.NewLine);

            for (var i = 0; i < a.Height(); i++)
            {
//                buf.Append(i.ToString().PadRight(max_row) + " | ");

                for (var j = 0; j < a.Width(); j++)
                {
                    buf.Append(a[i, j].PadRight(cols[j]));
//                    buf.Append(a[i, j].PadRight(max_col));
                    if (j < a.Width() - 1) buf.Append(" ");
                }
                if (i < a.Height() - 1) buf.Append(Environment.NewLine);
            }

            Console.WriteLine(buf.ToString());
        }

        static void printctx()
        {
            print(fs);
            print(fpn);
            print(fpm);
            "".Dump();
            print(gs);
            "".Dump();
            print(gpn);
            "".Dump();
            print(gpm);
            "".Dump();
            print(gpd);
        }
        
        #endregion

        private static int[] fs = new int[top];
        private static int[] fpn = new int[top];
        private static int[] fpm = new int[top];
        private static String[] fpd = new String[top];

        private static int f(int n)
        {
            if (n < 0 || n >= top) return int.MaxValue;

            if (fs[n] == int.MinValue)
            {
                if (n == 0)
                {
                    fs[n] = 0;
                    fpn[n] = int.MaxValue;
                    fpm[n] = int.MaxValue;
                }
                else
                {
                    int a_value = int.MaxValue, a_index = int.MaxValue;
                    for (var k = 0; k <= n; ++k)
                    {
                        var g_value = g(n - 1, k);
                        if (g_value < a_value)
                        {
                            a_value = g_value;
                            a_index = k;
                        }
                    }

                    a_value = a_value == int.MaxValue ? int.MaxValue : a_value + 1;

                    int ctrlv_value = int.MaxValue, ctrlv_index = int.MaxValue;
                    for (var k = 0; k <= n; ++k)
                    {
                        var g_value = g(n - k, k);
                        if (g_value < ctrlv_value)
                        {
                            ctrlv_value = g_value;
                            ctrlv_index = k;
                        }
                    }

                    ctrlv_value = ctrlv_value == int.MaxValue ? int.MaxValue : ctrlv_value + 1;

                    var min_value = Math.Min(a_value, ctrlv_value);
                    fs[n] = min_value;

                    if (min_value == int.MaxValue)
                    {
                        fpn[n] = int.MaxValue;
                        fpm[n] = int.MaxValue;
                        fpd[n] = "*";
                    }
                    else if (min_value == a_value)
                    {
                        fpn[n] = n - 1;
                        fpm[n] = a_index;
                        fpd[n] = "a";
                    }
                    else
                    {
                        fpn[n] = n - ctrlv_index;
                        fpm[n] = ctrlv_index;
                        fpd[n] = "p";
                    }
                }
            }

            return fs[n];
        }

        private static int[,] gs = new int[top, top];
        private static int[,] gpn = new int[top, top];
        private static int[,] gpm = new int[top, top];
        private static String[,] gpd = new String[top, top];

        private static int g(int n, int m)
        {
            if (n < 0 || n >= top) return int.MaxValue;
            if (m < 0 || m >= top) return int.MaxValue;

            if (gs[n, m] == int.MinValue)
            {
                if (m > n)
                {
                    gs[n, m] = int.MaxValue;
                    gpn[n, m] = int.MaxValue;
                    gpm[n, m] = int.MaxValue;
                    gpd[n, m] = "*";
                }
                else if (n == 0)
                {
                    gs[n, m] = 0;
                    gpn[n, m] = int.MaxValue;
                    gpm[n, m] = int.MaxValue;
                    gpd[n, m] = "*";
                }
                else
                {
                    var a_value = g(n - 1, m) == int.MaxValue ? int.MaxValue : g(n - 1, m) + 1;

                    var ctrlv_value = int.MaxValue;
                    if (m != 0) ctrlv_value = g(n - m, m) == int.MaxValue ? int.MaxValue : g(n - m, m) + 1;

                    int ctrlac_value = int.MaxValue, ctrlac_index = int.MaxValue;
                    if (m == n)
                    {
                        for (var k = 0; k < m; ++k)
                        {
                            var g_value = g(n, k);
                            if (g_value < ctrlac_value)
                            {
                                ctrlac_value = g_value;
                                ctrlac_index = k;
                            }
                        }
                    }

                    ctrlac_value = ctrlac_value == int.MaxValue ? int.MaxValue : ctrlac_value + 2;

                    var min_value = Math.Min(a_value, Math.Min(ctrlv_value, ctrlac_value));
                    gs[n, m] = min_value;

                    if (min_value == int.MaxValue)
                    {
                        gpn[n, m] = int.MaxValue;
                        gpm[n, m] = int.MaxValue;
                        gpd[n, m] = "*";
                    }
                    else if (min_value == a_value)
                    {
                        gpn[n, m] = n - 1;
                        gpm[n, m] = m;
                        gpd[n, m] = "a";
                    }
                    else if (min_value == ctrlv_value)
                    {
                        gpn[n, m] = n - m;
                        gpm[n, m] = m;
                        gpd[n, m] = "p";
                    }
                    else
                    {
                        gpn[n, m] = n;
                        gpm[n, m] = ctrlac_index;
                        gpd[n, m] = "c";
                    }
                }
            }

            return gs[n, m];
        }

        private static String path(int i)
        {
            var length = f(i);
            var steps = new List<String>();
            if (length == int.MaxValue) return "path does not exist";

            int n = i, m = fpm[i];
            int pn = fpn[i], pm = fpm[i]; var pd = fpd[i];
            steps.Insert(0, pd);
//            String.Format("pn = {0}, pm = {1}, pd = {2}",
//                pn == int.MinValue ? "?" : pn == int.MaxValue ? "*" : pn.ToString(),
//                pm == int.MinValue ? "?" : pm == int.MaxValue ? "*" : pm.ToString(),
//                pd).Dump();
            n = pn; m = pm;

            while (n != int.MaxValue && m != int.MaxValue)
            {
                pn = gpn[n, m];
                pm = gpm[n, m];
                pd = gpd[n, m];

                steps.Insert(0, pd);
//                String.Format("pn = {0}, pm = {1}, pd = {2}",
//                    pn == int.MinValue ? "?" : pn == int.MaxValue ? "*" : pn.ToString(),
//                    pm == int.MinValue ? "?" : pm == int.MaxValue ? "*" : pm.ToString(),
//                    pd).Dump();

                n = pn;
                m = pm;
            }

            steps = steps.Where(step => step != "*").ToList();
            (steps.Count() + steps.Count(step => step == "c") == length).AssertTrue();
            if (steps.Count() == 0) return "path is empty";
            return steps.StringJoin(", ");
        }

        private const int from = 100;
        private const int to = 150;
        private const int top = to + 1;

        static void Main(string[] args)
        {
            var data = new String[to - from + 1, 5];
            from.UpTo(to).ForEach(i =>
            {
                data[i - from, 0] = i.ToString();
                data[i - from, 1] = "=>";
                data[i - from, 2] = f(i).ToString();
                data[i - from, 3] = ":";
                data[i - from, 4] = path(i).ToString();
            });

            print(data);
        }
    }
}