Adv2016/D13.1/Program.cs

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

namespace D13._1
{
    class Program
    {
        static bool IsOpenSpace((int x, int y) coord, int fav)
        {
            var n = (coord.x * coord.x) + (3 * coord.x) + (2 * coord.x * coord.y) + coord.y + (coord.y * coord.y) + fav;
            int nbits = 0;
            while (n > 0)
            {
                nbits += n & 1;
                n >>= 1;
            }
            return nbits % 2 == 0;
        }

        static readonly (int mx, int my)[] Moves = new [] { (-1, 0), (0, -1), (1, 0), (0, 1) };

        static int SolveMaze((int x, int y) start, (int x, int y) goal, int fav)
        {
            var queue = new Queue<((int x, int y), int step)>();
            var visited = new HashSet<(int, int)>();

            queue.Enqueue((start, 0));

            while (queue.Count > 0)
            {
                ((int x, int y) coord, int step) = queue.Dequeue();
                visited.Add(coord);

                if (coord == goal) return step;

                foreach (var (mx, my) in Moves)
                {
                    (int x, int y) ncoord = (coord.x + mx, coord.y + my);
                    if (ncoord.x < 0 || ncoord.y < 0) continue;

                    if (IsOpenSpace(ncoord, fav) == false) continue;
                    if (visited.Contains(ncoord) == true) continue;
                    queue.Enqueue((ncoord, step + 1));
                }
            }
            throw new Exception();
        }

        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();

            var answer = SolveMaze((1, 1), (31, 39), int.Parse(args[0]));
            Console.WriteLine($"The answer is : {answer}\n");

            sw.Stop();
            Console.WriteLine($"Execution time : {sw.ElapsedMilliseconds}ms");
        }
    }
}