using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// Breadth First Search on an implicit graph
// Find a shortest solution for the A2B problem
// with steps Increment, Minus, Double

namespace A2BFS
{
    class A2BFS
    {
        static void Main(string[] args)
        {
            A2BFS a = new A2BFS();
        }

        Dictionary<int, int> pi;    // Store predecessor
        Dictionary<int, int> d;     // Store depth
        Queue<int> Q;               //
        bool verb = false;          // Verbose mode
        bool mmag = false;          // doet operatie M mee
        int a; int b;               // Beginpoint and endpoint

        public A2BFS()
        {
            pi = new Dictionary<int, int>(); 
            d = new Dictionary<int, int>(); 
            Q = new Queue<int>();
            String[] toks = new String[1];
            bool c = true;  // continue??

            while (c)
            {
                Console.Write("-> ");
                toks = Console.ReadLine().Split();
                switch (toks[0])
                {
                    case "a": a = Int32.Parse(toks[1]); break;
                    case "b": b = Int32.Parse(toks[1]); break;
                    case "v": verb = !verb; break;
                    case "m": mmag = !mmag; break;
                    case "x": c = false; break;

                    case "s": // search
                        // if B<A and M is not allowed, no solution exists
                        if (a > b && !mmag)
                            { Console.WriteLine("Not possible."); break; }
                        search();
                        Console.WriteLine("{0} can be reached in {1} steps.", b, d[b]);
                        break;

                    case "h":
                        Console.WriteLine("Gerard's BFS from A 2 B");
                        Console.WriteLine("a/b: Set a or b (now {0} and {1}).", a, b);
                        Console.WriteLine("s  : Search.");
                        Console.WriteLine("v  : Toggle Verbose (now {0}).", verb);
                        Console.WriteLine("m  : Toggle use of M (now {0}).", mmag);
                        Console.WriteLine("x  : eXit.");
                        break;

                }
            }
        }

        private void search()
        {
            // Throw out all old stuff from previous searches
            pi.Clear(); d.Clear(); Q.Clear();

            // Start search by enqueing a
            d.Add(a, 0); Q.Enqueue(a); pi.Add(a, a); if (a == b) return;

            // Process untill Q empty
            while (Q.Count > 0)
            {
                int u = Q.Dequeue();

                // Successors of u are:  I(u) = u+1, maybe M(u) = u-1,  D(u) = 2u
                List<int> Suc = new List<int>();
                Suc.Add(u+1); if (mmag) Suc.Add(u-1); Suc.Add(2*u);

                foreach (int v in Suc)
                {
                    if (!pi.ContainsKey(v))
                    {
                        if (verb) Console.WriteLine(v + " is reached via " + u + " in " + (d[u] + 1) + " steps.");
                        Q.Enqueue(v);
                        pi.Add(v, u); d.Add(v, d[u]+1);

                        // Stop when b is found
                        if (v == b) return;
                    }
                }
            }
        }

    }
}