Kjo detyrë është caktuar me qëllim që të vërejmë zgjidhje të cilat bazohen në  ‘pattern-recognition’. Për të zgjidhur këtë detyrë së pari duhet të analizohet problemi, të vizualizohet në mënyrë abstrakte zgjidhja duke krijuar një algoritëm. Më pas vjen implementimi i kësaj zgjidhje në gjuhën e caktuar programuese.

Çfarë është ideja pas kësaj detyre? Kërkesa ishte që të shkruhet një kod që merr në hyrje një tabelë të lojës tic tac toe dhe tregon statusin e asaj loje. Pra, të tregojë se a kemi fitues, barazim apo është lojë e papërfunduar. Zgjidhja poashtu duhet ta vërej nëse tabela është e pa vlefshme.

Loja tic tac toe është një lojë e thjeshtë me laps dhe letër për dy lojtarë të cilët luajnë me radhë duke vendosur X ose O në një tabelë 3x3. Lojtari i cili ia del mbanë të vendosë tri shenja në një linjë qoftë ajo horizontalisht, vertikalisht apo diagonal shpallet fitues. Loja mund të përfundojë edhe pa fitues nëse janë vendosur të gjitha shenjat, mirëpo nuk plotësohet kushti i mësipërm.

Tash, çfarë është extended tic tac toe ose tic tac toe e zgjeruar? Është po e njëjta lojë, mirëpo tabela e lojës është e madhësisë NxN dhe fituesi duhet të grumbullojë N shenja në linjë horizontale, vertikale apo diagonale.

Programi është i supozuar që të kthej vetëm një përgjigjje për çfarëdo hyrje që merr, dhe përgjigja ka 6 opsione të mundshme që mund të jenë:

X moves - kjo përgjigje kthehet nëse është radha e X të luaj

O moves - kjo përgjigje kthehet nëse është radha e O të luaj

X wins - kjo përgjigje kthehet nëse X ka fituar lojën (pra janë N X-e të rendiura në ndonjë linjë horizontale, vertikale apo diagonale)

O wins - kjo përgjigje kthehet nëse O ka fitur lojën

Draw - kjo përgjigje kthehet nëse nuk ka më mundësi për të luajtur, mirëpo as X as O nuk kanë fituar

Invalid - kjo përgjigje kthehet nëse duke ditur radhën (x luan gjithmonë i pari) ka renditje të pakuptimtë të figurave në tabelë (pra një tabelë vetëm me një O të lëvizur është invalide sepse O ka luajtur pa radhë, një tabelë që pasi ka fituar X po fiton edhe O është invalide sepse loja mbaron me fitoren e njëres shenjë, një tabele e cila ka 3 "X-e" të luajtur dhe vetëm 1 "O" është invalide sepse shihet se X ka luajtur një herë pa radhë)

Teksti si i dhënë në detyrë mund të lexohet në këtë link: https://www.hackerrank.com/contests/gjirafa/challenges/extended-tic-tac-toe dhe gjithashtu nëse deshironi, ju ftojmë të bëni prapë submit në këtë detyrë dhe të ushtroni të gjeni zgjidhje të ndryshme.

Nga gjithsej 130 prova që janë bërë për këtë detyrë, 20 kanë rezulutar të sakta apo rreth 15% e provave. Andaj mund ta konsiderojmë si një detyrë mesatarisht të vështirë.

Per të zgjidhur këtë detyrë njëherë diskutojmë zgjidhjen e mundshme, ofrojmë argumente, shtjellojmë metodat e ofruara dhe e kthejmë në kod këtë detyrë. Kodi i kësaj detyre do të jetë në C#, mirëpo e njëjta logjikë mund të përdoret për zgjidhjen e kësaj detyre edhe në gjuhët tjera programuese.

Alogritmi që zgjidh këtë problem i cili është i krijuar bazuar në këta tre hapa është:

Hapi 1: Caktojmë nëse tabela e dhëne në formë matrice është valide apo jo

• Është tabelë valide: Vazhdojmë në hapin e dytë
• Nuk është tabelë valide: Lajmërojme nëpërmjet mesazhit se kemi të bëjmë me një tabelë jo valide

Hapi 2: Kontrollojmë nëse matrica ka fitues

• Tabela nuk ka fitues: Vazhdojmë në hapin e tretë
• Tabela ka fitues: Tregojmë fituesin nëpërmjet mesazhit

Hapi 3: Kontrollojmë nëse matrica ka levizje

• Nuk ka më levizje: Lajmrojmë barazimin nëpërmjet mesazhit
• Ka levizje: Tregojmë kush ka radhën e lëvizjes nëpërmjet mesazhit

Paraqitja e agloritmit në kod:

public static string Solve(int n, List<string> list)
{
    var message = "invalid";
    var matrix = ConvertToMatrix(n, list);
    var isValid = CheckValidity(matrix);
    if (!isValid) return message;
    var hasWinner = CheckWinner(matrix, out message);
    if (hasWinner) return message;
    var hasMoves = CheckMoves(matrix, out message);
    return message;
}

Zgjidhja e kësaj detyre mund të bëhet në mënyra të ndryshme, mirëpo këtu kemi bërë një zgjidhje që nuk është më e mira nga aspekti kohor, mirëpo vetëm e sqaron mirë logjikën e detyrës. Për zgjidhjen e kësaj detyre në mënyrë më optimale, do duhej që shumë metoda që janë të ndara të bashkoheshin për të kryer të njëjtën detyrë:

Hapi 0 në zgjidhjen e detyrës, është konvertimi i tabelës së dhënë në hyrje në një matricë int[,] e cila na mundëson manovrimin më të lehtë, gjithashtu në këtë qasje X-të në tabelë i kemi zëvendësuar me 1, O-të, i kemi zëvendësuar me -1, ndërsa hapësirat i kemi zëvendësuar me 0. 

Kjo pjesë në kod duket kështu:

private static int[,] ConvertToMatrix(int n, List<string> list)
{
    var matrix = new int[n, n];
    for (var i = 0; i < n; i++)
    {
        for (var j = 0; j < list[i].Length; j++)
        {
            matrix[i, j] = list[i][j] switch
            {
                'X' => 1,
                'O' => -1,
                _ => 0
            };
        }
    }
    return matrix;
}

Hapi 1 në zgjidhjen e detyrës është kontrollimi i validitetit të tabelës e që bëhet nga metoda CheckValidity()

private static bool CheckValidity(int[,] inputMatrix)
{
    var matrixSum = 0;
    for (int i = 0; i < inputMatrix.GetLength(0); i++)
    {
        for (int j = 0; j < inputMatrix.GetLength(0); j++)
        {
            matrixSum += inputMatrix[i, j];
        }
    }
    /*
     * since we replace all X with 1
     * and we replaced all O with -1
     * a well constricted matrix can have one X more than O
     * or a total sum between 0 and 1
     */

    return matrixSum == 0 || matrixSum == 1;
}

Hapi 2 në zgjidhjen e detyrës është kontrollimi nëse tabela ka fitues, e që në rastin tonë bëhet shumë thjeshtë vetëm duke mbledhur shumën e tabelës për secilin rresht, kolonë apo diagonale. Nëse shuma e llogaritur në atë drejtim është N apo -N, atëherë aty kemi të bëjmë me drejtim fitues.

private static bool CheckWinner(int[,] inputMatrix, out string message)
{
    message = "invalid";
    var count = inputMatrix.GetLength(0);
    // We could have used a different structure instead of INT
    var dictionary = new Dictionary<string, int>
    {
        ["DL"] = 0, // diagonal left (starting point 0,0)
        ["DR"] = 0 // diagonal right (starting point 0, N-1)
    };
    for (int i = 0; i < count; i++)
    {
        dictionary[$"R{i}"] = 0; // For each row we add a new key R0, R1, .. R(N-1)
        dictionary[$"C{i}"] = 0; // For each column we add a new key C0, C1, .. C(N-1)
    }

    for (int i = 0; i < count; i++)
    {
        for (int j = 0; j < count; j++)
        {
            var inputValue = inputMatrix[i, j];
            if (i == j) // We have the left diagonal
                dictionary["DL"] += inputValue;
            if (i + j == count - 1) // We have the right diagonal
                dictionary["DR"] += inputValue;
            dictionary[$"R{i}"] += inputValue; // We are iterating through Rows(i)
            dictionary[$"C{j}"] += inputValue;  // We are iterating through Columns(j)
        }
    }

    var winners = dictionary.Where(x => Math.Abs(x.Value) == count).ToList();
    // If there are no winners we will report that there is no winner
    if (winners.Count == 0)
        return false;
    // If there are more than one winner, we will report that there is a winner 
    // From the construct of the code it will write the default message: "invalid"
    if (winners.Count > 1)
        return true;
    // If we have only one winner we will check which player has won
    var key = winners[0].Key;
    var winner = 0;
    switch (key)
    {
        case "DL":
            winner = inputMatrix[0, 0];
            break;
        case "DR":
            winner = inputMatrix[0, count - 1];
            break;
        default:
        {
            if (key.StartsWith("R"))
            {
                var row = int.Parse(key.Replace("R", ""));
                winner = inputMatrix[row, 0];
                break;
            }
            else
            {
                var column = int.Parse(key.Replace("C", ""));
                winner = inputMatrix[0, column];
                break;
            }
        }
    }

    message = winner == 1 ? "X wins" : "O wins";
    return true;
}

Hapi 3 në zgjidhjen e detyrës është kontrollimi nëse ka lëvizje. Pasi që jemi duke kontrolluar një tabelë valide atëherë kontrollojmë nëse ka ndonjë element me vlerë zero, dhe bazuar në shumën e kësaj matrice se a është 0 apo 1 konstatojmë cila shenjë ka radhën e lëvizjes:

private static bool CheckMoves(int[,] inputMatrix, out string message)
{
    // If we have no moves, it is draw by deffault
    message = "draw";
    var hasMoves = false;
    var matrixSum = 0;
    for (var i = 0; i < inputMatrix.GetLength(0); i++)
    {
        for (var j = 0; j < inputMatrix.GetLength(0); j++)
        {
            if (inputMatrix[i, j] == 0)
                hasMoves = true;
            // We con use some static variables, at the first initialization of matrix
            // We can by default remove the need for those two iterations
            matrixSum += inputMatrix[i, j];
        }
    }

    if (!hasMoves) return false;
    // Since X moves first (sum == 0, X moves) (sum == 1, O moves)
    message = matrixSum == 1 ? "O moves" : "X moves";
    return true;
}

Me përfundimin e këtij hapi, mund të konstatojmë se detyra është e zgjidhur.