using System;
using System.Collections.Generic;
using System.Linq;

namespace Arithmetic {

    class Program {

        static void Main(string[] args) {
            var message = "AAABBBCCDD";
            var code = "BBC";

            var symbols = CalculateProbs(message);

            Console.WriteLine("Original list\n");
            DisplayList(symbols);

            var codeWord = GetCodeWord(symbols, code);
            var tag = (codeWord.High + codeWord.Low) / 2;
            Console.WriteLine($"\nTag({codeWord.Name}) = " +
                $"({codeWord.High} + {codeWord.Low}) / 2 = {tag}");
        }


        static List<Symbol> CalculateProbs(string message) {
            var uniqueChars = message.Distinct().ToList();

            var symbols = new List<Symbol>();
            foreach (var item in uniqueChars) {
                double probability = message.Count(c => c == item) / (double)message.Length;
                symbols.Add(new Symbol(item, probability));
            }

            symbols = symbols.OrderBy(i => i.Name).OrderBy(i => i.Probability).ToList();

            for (int i = 0; i < symbols.Count; i++) {
                symbols[i].Low = symbols.Take(i).Sum(s => s.Probability);
                symbols[i].High = symbols.Take(i + 1).Sum(s => s.Probability);
            }

            symbols.Reverse();

            return symbols;
        }

        static Symbol GetCodeWord(List<Symbol> symbols, string code) {
            var currentChar = code[0];
            code = code.Substring(1);

            var symbol = symbols.Find(s => s.Name == currentChar);
            var high = symbol.High;
            var low = symbol.Low;

            foreach (var item in symbols) {
                item.High = high;
                item.Low = low + (high - low) * item.Low;
                high = item.Low;
            }

            symbols.Last().Low = low;

            Console.WriteLine($"\nExamining ({symbol.Name})\n");
            DisplayList(symbols);

            if (code.Length > 1) return GetCodeWord(symbols, code);

            return symbols.Find(i => i.Name == char.Parse(code));
        }

        static void DisplayList(List<Symbol> symbols) {
            symbols.ForEach(i => Console.WriteLine($"\t{i.High}\n{i.Name}"));
            Console.WriteLine($"\t{symbols.Last().Low}");
        }
    }

    class Symbol {

        public Symbol(char name, double probability) {
            Name = name;
            Probability = probability;
        }

        public char Name { get; set; }
        public double Low { get; set; }
        public double High { get; set; }
        public double Probability { get; set; }
    }
}