Advent of Code 5: Binary Boarding

This was an interesting one, but still comparable to an "easy" Leetcode problem (I'm sure this will get tougher as the days go by): Day 5 - Advent of Code 2020

The analysis of each seat is a variation of a Binary Search. What I did is one function that given a string returns the number associated with it. That way you can call it for the 0-6 and 7-9 parts of the string. After that, the first part is easy, just getting the max. The second part is also relatively easy: sort the entries, and then go one by one from the very beginning looking for the first gap. Once found, that's your solution. Code is down below, cheers, ACC.


static void Main(string[] args)
{
    FileInfo fi = new FileInfo(args[0]);
    StreamReader sr = fi.OpenText();
    List list = new List();
    int max = 0;
    while (!sr.EndOfStream)
    {
        string str = sr.ReadLine().Trim();
        if (!String.IsNullOrEmpty(str))
        {
            int val = SeatNumber(str.Substring(0, 7)) * 8 + SeatNumber(str.Substring(7));
            list.Add(val);
            max = Math.Max(max, val);
        }
    }
    sr.Close();
    Console.WriteLine("Max: {0}", max);

    int[] arr = list.ToArray();
    Array.Sort(arr);
    int seed = arr[0];
    for (int i = 0; i < arr.Length; i++)
    {
        if (seed != arr[i])
        {
            Console.WriteLine("Missing: {0}", seed);
            break;
        }
        seed++;
    }
}

public static int SeatNumber(string str)
{
    int left = 0;
    int right = (int)Math.Pow(2, str.Length) - 1;

    for (int i = 0; i < str.Length; i++)
    {
        int mid = (left + right) / 2;
        if (str[i] == 'F' || str[i] == 'L') right = mid - 1;
        else left = mid + 1;
    }

    return left;
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons