using System;

using System.Collections.Generic;

using System.Linq;

​

namespace VLQChallenge

{

    class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("Variable Length Quantity (VLQ) Encoder/Decoder");

            Console.WriteLine("================================================");

            while (true)

            {

                Console.WriteLine("\nChoose an option:");

                Console.WriteLine("1. Encode integer to VLQ");

                Console.WriteLine("2. Decode VLQ to integer");

                Console.WriteLine("3. Show explanation");

                Console.WriteLine("4. Exit");

                Console.Write("Enter your choice (1-4): ");

                string choice = Console.ReadLine();

                switch (choice)

                {

                    case "1":

                        EncodeMode();

                        break;

                    case "2":

                        DecodeMode();

                        break;

                    case "3":

                        ShowExplanation();

                        break;

                    case "4":

                        Console.WriteLine("Goodbye!");

                        return;

                    default:

                        Console.WriteLine("Invalid choice. Please enter 1, 2, 3, or 4.");

                        break;

                }

            }

        }

        static void EncodeMode()

        {

            Console.Write("Enter an integer to encode (0 to 2^63): ");

            string input = Console.ReadLine();

            if (ulong.TryParse(input, out ulong number))

            {

                try

                {

                    byte[] encoded = IntToVlq(number);

                    Console.WriteLine($"Encoded VLQ: [{string.Join(", ", encoded)}]");

                    Console.WriteLine($"Binary representation: [{string.Join(", ", encoded.Select(b => Convert.ToString(b, 2).PadLeft(8, '0')))}]");

                    // Show step-by-step breakdown for better understanding

                    Console.WriteLine("\nStep-by-step breakdown:");

                    ShowEncodingSteps(number, encoded);

                }

                catch (Exception ex)

                {

                    Console.WriteLine($"Error: {ex.Message}");

                }

            }

            else

            {

                Console.WriteLine("Invalid input. Please enter a valid non-negative integer.");

            }

        }

        static void DecodeMode()

        {

            Console.Write("Enter VLQ bytes separated by commas (e.g., 134,195,23): ");

            string input = Console.ReadLine();

            try

            {

                string[] parts = input.Split(',');

                byte[] vlqBytes = new byte[parts.Length];

                for (int i = 0; i < parts.Length; i++)

                {

                    if (!byte.TryParse(parts[i].Trim(), out vlqBytes[i]))

                    {

                        Console.WriteLine($"Invalid byte value: {parts[i].Trim()}");

                        return;

                    }

                }

                ulong decoded = VlqToInt(vlqBytes);

                Console.WriteLine($"Decoded integer: {decoded}");

                Console.WriteLine($"Binary input: [{string.Join(", ", vlqBytes.Select(b => Convert.ToString(b, 2).PadLeft(8, '0')))}]");

                // Show step-by-step breakdown

                Console.WriteLine("\nStep-by-step breakdown:");

                ShowDecodingSteps(vlqBytes, decoded);

            }

            catch (Exception ex)

            {

                Console.WriteLine($"Error: {ex.Message}");

            }

        }

        static void ShowExplanation()

        {

            Console.WriteLine("\nVariable Length Quantity (VLQ) Explanation:");

            Console.WriteLine("==========================================");

            Console.WriteLine();

            Console.WriteLine("VLQ is a way to encode integers using a variable number of bytes.");

            Console.WriteLine("Each byte uses 7 bits for data and 1 bit (MSB) as a continuation flag.");

            Console.WriteLine();

            Console.WriteLine("Key concepts:");

            Console.WriteLine("- MSB (Most Significant Bit) = 1: More bytes follow");

            Console.WriteLine("- MSB = 0: This is the last byte");

            Console.WriteLine("- Only the lower 7 bits of each byte contain actual data");

            Console.WriteLine("- Values are stored in big-endian format (most significant bytes first)");

            Console.WriteLine();

            Console.WriteLine("Examples:");

            Console.WriteLine("- 127 → [127] (fits in 7 bits, no continuation needed)");

            Console.WriteLine("- 128 → [129, 0] (needs 2 bytes: 129=128+1 with MSB set, then 0)");

            Console.WriteLine("- 16383 → [255, 127] (255=128+127 with MSB set, then 127)");

            Console.WriteLine();

            Console.WriteLine("Encoding process:");

            Console.WriteLine("1. Convert number to base-128 representation");

            Console.WriteLine("2. Set MSB=1 for all bytes except the last");

            Console.WriteLine("3. Set MSB=0 for the last byte");

            Console.WriteLine();

            Console.WriteLine("Decoding process:");

            Console.WriteLine("1. Remove MSB from each byte to get 7-bit values");

            Console.WriteLine("2. Combine values using powers of 128");

            Console.WriteLine("3. Result = sum of (value * 128^position)");

        }

        static byte[] IntToVlq(ulong value)

        {

            if (value == 0)

                return new byte[] { 0 };

            List<byte> result = new List<byte>();

            // Convert to base 128 and collect digits

            while (value > 0)

            {

                result.Add((byte)(value & 0x7F)); // Get lower 7 bits

                value >>= 7; // Divide by 128

            }

            // Reverse to get big-endian order

            result.Reverse();

            // Set continuation bit (MSB) for all bytes except the last

            for (int i = 0; i < result.Count - 1; i++)

            {

                result[i] |= 0x80; // Set MSB to 1

            }

            return result.ToArray();

        }

        static ulong VlqToInt(byte[] vlqBytes)

        {

            ulong result = 0;

            for (int i = 0; i < vlqBytes.Length; i++)

            {

                byte currentByte = vlqBytes[i];

                // Check if this should be the last byte

                bool isLastByte = (currentByte & 0x80) == 0;

                // Get the 7-bit value

                ulong value = (ulong)(currentByte & 0x7F);

                // Add to result

                result = (result << 7) | value;

                // If this was supposed to be the last byte, we're done

                if (isLastByte)

                {

                    // Verify we've processed all bytes

                    if (i != vlqBytes.Length - 1)

                    {

                        throw new ArgumentException($"Invalid VLQ: byte {i} has MSB=0 but is not the last byte");

                    }

                    break;

                }

            }

            // Check that the last byte was properly marked

            if ((vlqBytes[vlqBytes.Length - 1] & 0x80) != 0)

            {

                throw new ArgumentException("Invalid VLQ: last byte must have MSB=0");

            }

            return result;

        }

        static void ShowEncodingSteps(ulong originalValue, byte[] encoded)

        {

            Console.WriteLine($"Original value: {originalValue}");

            // Show base-128 breakdown

            ulong temp = originalValue;

            List<ulong> base128Digits = new List<ulong>();

            while (temp > 0)

            {

                base128Digits.Add(temp % 128);

                temp /= 128;

            }

            base128Digits.Reverse();

            Console.WriteLine($"Base-128 digits: [{string.Join(", ", base128Digits)}]");

            for (int i = 0; i < encoded.Length; i++)

            {

                bool hasContinuation = (encoded[i] & 0x80) != 0;

                byte dataValue = (byte)(encoded[i] & 0x7F);

                Console.WriteLine($"Byte {i + 1}: {encoded[i]} = {dataValue} + {(hasContinuation ? "128 (continuation bit)" : "0 (final byte)")}");

            }

        }

        static void ShowDecodingSteps(byte[] vlqBytes, ulong result)

        {

            Console.WriteLine("Decoding calculation:");

            ulong runningTotal = 0;

            for (int i = 0; i < vlqBytes.Length; i++)

            {

                bool hasContinuation = (vlqBytes[i] & 0x80) != 0;

                byte dataValue = (byte)(vlqBytes[i] & 0x7F);

                ulong contribution = (ulong)dataValue << (7 * (vlqBytes.Length - 1 - i));

                Console.WriteLine($"Byte {i + 1}: {vlqBytes[i]} → data={dataValue}, contribution={dataValue} × 128^{vlqBytes.Length - 1 - i} = {contribution}");

                runningTotal += contribution;

            }

            Console.WriteLine($"Total: {runningTotal}");

        }

    }

}