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

class Program
{
    // funkce vraci znak s negaci nad pismenem
    static string Overbar(string s)
    {
        return s switch
        {
            "A" => "Ā",  // a s negaci
            "B" => "B̄", // b s negaci
            "C" => "C̄", // c s negaci
            "D" => "D̄", // d s negaci
            _ => s       // jinak vrati puvodni znak
        };
    }

    static void Main()
    {
        do
        {
            string[,] map = new string[4, 4];  // prazdna 4x4 karnaugh mapa

            // inicializace vsech bunek na "N" (nezadano)
            for (int r = 0; r < 4; r++)
                for (int c = 0; c < 4; c++)
                    map[r, c] = "N";

            // zadavani hodnot pro kazdou bunku
            for (int r = 0; r < 4; r++)
            {
                for (int c = 0; c < 4; c++)
                {
                    Console.Clear();
                    map[r, c] = "K";  // oznaci aktualni bunku
                    PrintMap(map, true); // vykresli mapu s instrukcemi
                    Console.Write($"Zadej hodnotu pro ({r},{c}) [0 = záporná, 1 = kladná, X = nevadí]: ");
                    string input = Console.ReadLine()!.Trim().ToUpper();
                    if (input != "0" && input != "1" && input != "X") input = "0"; // default na 0
                    map[r, c] = input;
                }
            }

            Console.Clear();
            Console.WriteLine("Karnaughova mapa:");
            PrintMap(map, false); // vykresli hotovou mapu

            Console.WriteLine("\nZjednodušený výraz:");
            string result = CalculateExpression(map); // spocita zjednoduseny bool vyraz
            Console.WriteLine(result);

            Console.WriteLine("\nPokračovat? (Y/N nebo Escape)"); //tohle je jen kontrola jestli bylo zmacknuty N nebo Y aby se program vypl
            ConsoleKeyInfo keyInfo = Console.ReadKey(true);
            if (keyInfo.Key == ConsoleKey.N || keyInfo.Key == ConsoleKey.Escape)
                break;
        } while (true);
    }

    static void PrintMap(string[,] map, bool showInstructions) //funguje jako legenda pro pochopeni programu a vypisuje se nonstop
    {
        string[] rowLabels = { "(ĀB̄)", "(ĀB)", "(AB)", "(A B̄)" };
        string[] colLabels = { "(C̄D̄)", "(C̄D)", "(CD)", "(C D̄)" };
        Console.Write("       ");
        foreach (var col in colLabels)
            Console.Write(col.PadRight(6));
        Console.WriteLine();

        for (int r = 0; r < 4; r++)
        {
            Console.Write(rowLabels[r].PadRight(8));
            for (int c = 0; c < 4; c++)
                Console.Write(map[r, c].PadRight(6));
            Console.WriteLine();
        }

        if (showInstructions)
        {
            Console.WriteLine();
            Console.WriteLine("Legenda:");
            Console.WriteLine("0 = záporná hodnota (FALSE)");
            Console.WriteLine("1 = kladná hodnota (TRUE)");
            Console.WriteLine("X = nevadí (Don't Care) - může být 0 nebo 1");
            Console.WriteLine("K = aktuální vybraná buňka");
            Console.WriteLine("N = zatím nezadáno (není specifikováno)");
            Console.WriteLine();
        }
    }

    // hlavni funkce na vypocet zjednoduseneho vyrazu
    static string CalculateExpression(string[,] map)
    {
        // prevod mapy na cisla: 1 = TRUE, 0 = FALSE, -1 = X (dont care)
        int[,] binMap = new int[4, 4];
        for (int r = 0; r < 4; r++)
            for (int c = 0; c < 4; c++)
                binMap[r, c] = map[r, c] == "1" ? 1 : map[r, c] == "X" ? -1 : 0;

        var terms = new List<string>(); // sem se budou pridavat vysledne cleny

        // gray kod pro radky a sloupce
        // zakladni matematicky princip: sousedici bunky se lisí jen v jednom bitu
        string[] rowGray = { "00", "01", "11", "10" };
        string[] colGray = { "00", "01", "11", "10" };

        bool[,] used = new bool[4, 4]; // zaznam, ktere bunky uz byly pokryty

        // funkce kontroluje, jestli blok bunek je validni pro sjednoceni
        bool CheckGroup(int rStart, int cStart, int height, int width)
        {
            bool hasOne = false; // musi byt alespon jedna 1
            for (int dr = 0; dr < height; dr++)
            {
                for (int dc = 0; dc < width; dc++)
                {
                    int rr = (rStart + dr) % 4; // wraparound mapy po radcich
                    int cc = (cStart + dc) % 4; // wraparound mapy po sloupcich
                    if (binMap[rr, cc] == 0) return false; // pokud je 0, blok nelze pouzit
                    if (binMap[rr, cc] == 1) hasOne = true; // aspon jedna 1
                }
            }
            return hasOne;
        }

        // oznaci bunky v bloku jako pouzite
        void MarkUsed(int rStart, int cStart, int height, int width)
        {
            for (int dr = 0; dr < height; dr++) // projdi vsechny radky bloku
                for (int dc = 0; dc < width; dc++) // projdi vsechny sloupce bloku
                {
                    int rr = (rStart + dr) % 4; // vypocitej index radku s wraparoundem po 4
                    int cc = (cStart + dc) % 4; // vypocitej index sloupce s wraparoundem po 4
                    used[rr, cc] = true; // oznac bunku jako pouzitou, aby se dalsi bloky na ni nepripocitavaly
                }
        }

        // prevede blok bunek na minimalizovany logicky clan (A,B,C,D s negacemi)
        string GroupToTerm(int rStart, int cStart, int height, int width)
        {
            var rowsBits = new List<string>(); // sem ulozime gray kody radku pro blok
            var colsBits = new List<string>(); // sem ulozime gray kody sloupcu pro blok
            for (int dr = 0; dr < height; dr++)
                rowsBits.Add(rowGray[(rStart + dr) % 4]); // pridej gray kod radku s wraparoundem
            for (int dc = 0; dc < width; dc++)
                colsBits.Add(colGray[(cStart + dc) % 4]); // pridej gray kod sloupce s wraparoundem

            string term = ""; // inicializace vysledneho logickeho clenu

            // A je urceno prvnim bitem radku
            bool A_const = true; // predpokladame, ze hodnota A je konstantni v bloku
            char A_val = rowsBits[0][0]; // vezmeme prvni hodnotu A z prvniho radku
            foreach (var rb in rowsBits)
                if (rb[0] != A_val) A_const = false; // pokud se nektery radek lisi, A neni konstantni
            if (A_const) term += A_val == '0' ? Overbar("A") : "A"; // pridame A nebo A negaci do termu

            // B je urceno druhem bitem radku
            bool B_const = true; // predpokladame, ze B je konstantni
            char B_val = rowsBits[0][1]; // vezmeme hodnotu B z prvniho radku
            foreach (var rb in rowsBits)
                if (rb[1] != B_val) B_const = false; // pokud se nektery radek lisi, B vynechame
            if (B_const) term += B_val == '0' ? Overbar("B") : "B"; // pridame B nebo B negaci

            // C je urceno prvnim bitem sloupce
            bool C_const = true; // predpokladame konstantni C
            char C_val = colsBits[0][0]; // vezmeme hodnotu C z prvniho sloupce
            foreach (var cb in colsBits)
                if (cb[0] != C_val) C_const = false; // pokud se nektery sloupec lisi, C vynechame
            if (C_const) term += C_val == '0' ? Overbar("C") : "C"; // pridame C nebo C negaci

            // D je urceno druhem bitem sloupce
            bool D_const = true; // predpokladame konstantni D
            char D_val = colsBits[0][1]; // vezmeme hodnotu D z prvniho sloupce
            foreach (var cb in colsBits)
                if (cb[1] != D_val) D_const = false; // pokud se nektery sloupec lisi, D vynechame
            if (D_const) term += D_val == '0' ? Overbar("D") : "D"; // pridame D nebo D negaci

            if (term == "") // pokud zadna promenna neni konstantni v bloku
                term = "1"; // pak clan je jen logicka 1 (pravda)

            return term; // vrat minimalizovany logicky clan
        }

        // vsechny mozne velikosti bloku, od nejvetsi po nejmensi pro maximalni minimalizaci
        var blockSizes = new List<(int h, int w)>
{
    (4, 4), (4, 2), (2, 4), (4, 1), (1, 4), (2, 2), (2, 1), (1, 2), (1,1)
};

        // projdi vsechny bloky a vytvor minimalizovane cleny
        foreach (var (h, w) in blockSizes) // pro kazdou velikost bloku
        {
            for (int r0 = 0; r0 < 4; r0++) // pro kazdy radek jako start bloku
            {
                for (int c0 = 0; c0 < 4; c0++) // pro kazdy sloupec jako start bloku
                {
                    if (CheckGroup(r0, c0, h, w)) // pokud je blok validni (obsahuje jen 1 a X a alespon jednu 1)
                    {
                        string term = GroupToTerm(r0, c0, h, w); // preved blok na minimalizovany clan
                        bool coversNew = false; // kontrola, jestli blok kryje nove bunky

                        // zjisti, jestli blok obsahuje alespon jednu novou bunku
                        for (int dr = 0; dr < h; dr++)
                            for (int dc = 0; dc < w; dc++)
                            {
                                int rr = (r0 + dr) % 4; // wraparound radku
                                int cc = (c0 + dc) % 4; // wraparound sloupcu
                                if (!used[rr, cc]) coversNew = true; // pokud je bunky nove nepouzita, nastav true
                            }

                        // pokud kryje nove bunky a term jeste neni pridany, pridej ho
                        if (coversNew && !terms.Contains(term))
                        {
                            terms.Add(term); // pridej clan do vysledneho seznamu
                            MarkUsed(r0, c0, h, w); // oznac bunky jako pouzite
                        }
                    }
                }
            }
        }

        if (terms.Count == 0) // pokud se nenasel zadny validni blok
            return "0"; // vrat logickou nulu
        return string.Join(" + ", terms); // jinak spoj vsechny cleny logickym OR

    }
}