C# 2D-Array, Zahlenfolge zählen

[cfHxqA]

Hallo, ich stehe irgendwie völlig auf dem Schlauch. Es ist vom Funktionsprinzip eig. zu verstehen und klingt auch nicht besonders schwer? Aber ich finde keinen wirklich Ansatz zur möglichen Lösung.

Ich habe ein 2D-Array. Es ist 8x8. Jedes Feld kann zahlen zwischen 1-7 beinhalten. Nun will ich pro/Reihe in der Vertikalen als auch Horizontalen die Zahlen "zurückgeben", welche mindestens 3x in Folge hintereinander bzw. untereinander sind. Somit besteht theoretisch pro/Reihe die Möglichkeit das zwei Zahlenfolgen möglich sind.


Jetzt die eigentliche Frage: WIE kann ich nur die Zahlen zurückgeben die mindestens 3x in Folge in der Breite als auch Höhe sind!? Gerne mit Index. Ich habe nun einiges ausprobiert, weder mit Iteration noch Rekursion bin ich zum gewünschten Ergebnis gekommen - oder ich sehe den Wald vor lauter Bäumen nicht...?


Edit:
Ich hatte bereits den Ansatz einfach das aktuelle Feld zu prüfen, ob es mit dem vorherigen übereinstimmt bzw. mit dem nächsten Feld. Im Fall ja, wird die Funktion wiederholt. Ansonsten eben die Funktion mit dem Index weitergeführt, was NICHT dem Feld entsprochen hat. Solange, bis die Reihe zu Ende ist und dann eben eine Reihe runter.

Die Theorie klappt wunderbar, in der Praxis sieht es völlig anders aus.

 

[evilnear]

da dein array recht klein ist lass ich mal mögliche optimierungen weg. mein erster ansatz wäre das weiter aufzubrechen, zuerst über jede zahl einzeln iterieren, dann pro zahl einmal alle zeilen und einmal jede spalte durchgehen. für jede zahl dann ein zähler bis 3 der bei treffer inkrementiert und nach jeder zeile/spalte ein bit zum bestätigen des dreifachen vorkommens.
gewiss ist diese lösung nicht optimal

 

[cfHxqA]

Naja, mit jeder Zahl einzeln iterieren komme ich ja nicht zudem ergebnis, was ich wollte. Theoretisch, müsste ja eig. nur das jeweilige Feld geprüft werden und das folgende Feld. Du beginnst mit X0 und gehst dann weiter bis X7.

Somit kannst dann Feld für Feld fortlaufend prüfen und wenn eine Zahl nicht zur vorherigen passt, die bisher Liste zurückgeben und von der letzten stelle wieder anfangen?

Ein beispiel ist im Anhang. Die Zahlen müssen in Folge stehen und es sollen auch nur diese gezählt werden. Somit wären theoretisch pro/Reihe (Horizontal) 2x Kombinationen möglich - müssen nicht, können.

 

[evilnear]

aso, den part hatte ich übersehen. das ergibt ne menge raum für optimierungen aber ich würde bei meinem ersten ansatz bleiben wollen, natürlich mit der kleinen anpassung den zähler bei mismatch zurückzusetzen oder so.

 

[Shio]

Ich würds mit nem <int, int>Dictionary machen.
Als Key die jeweilige Zahl und dann bei jedem Auftreten die Value des Keys um eins höher zählen.
Über Linq kannste dir dann die Keys rausziehen die mindestens 3mal aufgetreten sind.

 

[Nero1]

Jenachdem ob du von unten auch wieder oben rauskommen kannst oder nicht müsste man das hier mit beachten, aber ich könnte mir denken du gehst wie folgt vor:

Für jedes Element pro Zeile
    Prüfe, ob das Element daneben oder darunter den gleichen Wert enthält
    Wenn ja, gehe in diese Richtung weiter
        Ist die Anzahl der Ergebnisse < 3 verwerfe diese Richtung
    Wenn nicht gehe zum nächsten Element und prüfe erneut

Das kann man natürlich noch sehr viel optimieren, indem man auf die Grenzen der Matrix achtet und insbesondere, wenn man nicht valide oder auch valide Reihen gefunden hat, welche Bereiche dann nicht mehr zu überprüfen sind, aber das ist denke ich ein guter erster Ansatz. Ansonsten geht auch ein anderer Weg, ein 8x8 Array ist so simpel, da ist bei wenigen Durchläufen die Effizienz egal. Wenn abzusehen ist, dass man es generisch auf N x M (mit N und M >> 10) ausdehnen kann sollte man da schon eher drauf achten, weil dann der Aufwand ohne Optimierung anfängt wirklich enorm zu werden.

 

[Panzenbaby]

Das wäre mein Ansatz:
Da du in jeder Zeile 8 Felder hast, die einen von 8 Werten annehmen können, würde ich diese auch nutzen um die Werte zu zählen.

Etwas konkreter:

int[] outArray = new int[inArray.length];
for (int i = 0; i < inArray.length; i++) {
    int value = inArray[i];
    outArray[value - 1] = outArray[value - 1] + 1;
}

Jetzt musst du nur noch schauen welcher value in outArray >= 3 ist und wieder eins auf den index addieren.

 

[cfHxqA]

@Nero1 Das Prinzip verfolge ich bereits, jedoch mit Iteration. Das Problem dabei ist oder aktuell, dass zusätzlich die Ergebnisse zum Aktuellen Ergebnis hinzugefügt werden und nicht separat, als neues Ergebnis.

Nachtrag: Ich habe das Problem nun gelöst bekommen. Ich habe die Lösung für das Problem mal hinzugefügt. Falls jemand mal das selbige Problem haben sollte und nach einer Lösung sucht. Es wird die Position der Felder zurückgegeben, die aneinander liegen - in der Horizontalen.

    private static List<List<Point>> Test(int[][] Matrix, Point Position, List<List<Point>> Pos) {
      if (Position.Y < Matrix.Length && Position.X < Matrix[Position.Y].Length) {
        if (Similar(Matrix, new Point(Position.X, Position.Y), new Point(Position.X + 1, Position.Y))) {
          List<Point> List = Pos.LastOrDefault();
          if (List == null) List = new List<Point>();

          List.Add(new Point(Position.X, Position.Y));
          List.Add(new Point(Position.X + 1, Position.Y));

          Pos.Remove(Pos.LastOrDefault());
          Pos.Add(List.Distinct().ToList());
        } else Pos.Add(new List<Point>());

        return Test(Matrix, new Point(Position.X + 1, Position.Y), Pos);
      } else {
        if (Position.Y < Matrix.Length && Position.X == Matrix[Position.Y].Length)
          return Test(Matrix, new Point(0, Position.Y + 1), Pos);
      }

      return Pos.Where(Entity => Entity.Count > 0).ToList();
    }

 

[lynxx]

Hoppla, ich dachte das wäre ein einfaches Array und da es ja wohl für das Spiel aus C# Algorithmus für Kombinationen? sein soll fängt meine Routine am Ende (unten) des Array an, da ja wenn das verschwindet und neue runterfallen sich mehr Kombinationen ergeben.

Naja, hier der Code falls es jemand interessiert:

using System;
using System.Text;

namespace FindEntries {
    class Program {
        const int ArraySize = 8;

        static void Main(string[] args) {
            int[] gameArray = {
                4,1,2,2,3,3,4,4,
                1,1,2,2,3,3,4,4,
                1,2,3,3,4,4,5,5,
                3,2,3,3,4,4,5,5,
                3,3,4,5,5,3,1,2,
                2,3,4,3,7,5,7,6,
                4,4,5,5,6,6,7,7,
                4,4,5,5,6,6,7,7
            };

            // GameArray auf 3 gleiche prüfen
            EntryMatch match = findTripple(gameArray, ArraySize);

            if (match != null) {
                // Ausgeben ab welchem Index, wieviele und die Richtung
                Console.WriteLine("Match gefunden an ID: " + match.Index + " Anzahl: " + match.Count + " Richtung: " + match.Richtung);

                StringBuilder sb = new StringBuilder();
                if (match.Richtung == Ausrichtung.horizontal) {
                    // String für Horizontale Treffer erzeugen
                    for (int i = match.Index; i < match.Index + match.Count; i++) {
                        sb.Append(gameArray[i].ToString());
                        if (i < match.Index + match.Count - 1)
                            sb.Append(",");
                    }
                }
                else {
                    // String für Vertikale Treffer erzeugen
                    for (int i = match.Index; i < match.Index + (match.Count * ArraySize); i+= ArraySize) {
                        sb.Append(gameArray[i].ToString());
                        if (i < match.Index + ((match.Count - 1) * ArraySize))
                            sb.Append(",");
                    }
                }
                // Treffer ausgeben
                Console.WriteLine("Matches: "+sb.ToString());
            }
            else
                Console.WriteLine("No Match");

            Console.ReadKey();
        }


        // Findet drei gleiche oder mehr im Array
        static EntryMatch findTripple(int[] array, int arrayWidth) {
            EntryMatch result = null;

            // Horizontal zuerst, Vertikal danach - falls gewünscht einfach die beiden aufrufe tauschen
            result = checkHorizontal(array, arrayWidth);
            if (result != null)
                return result;

            result = checkVertical(array, arrayWidth);
            if (result != null)
                return result;

            return null;
        }

        // Vertikale Prüfung
        static EntryMatch checkVertical(int[] array, int arrayWidth) {
            for (int j = 0; j < arrayWidth; j++) {
                int lastIdx = array[j];
                int count = 1;
                for (int i = arrayWidth; i < arrayWidth * arrayWidth; i += arrayWidth) {
                    int newIdx = array[j + i];
                    if (newIdx == lastIdx)
                        count++;
                    else {
                        if (count >= 3)
                            return new EntryMatch(j + i - (count * arrayWidth), count, Ausrichtung.vertikal);
                        count = 1;
                        lastIdx = newIdx;
                    }

                }
                if (count >= 3)
                    return new EntryMatch(j + (arrayWidth * arrayWidth) - (count * arrayWidth), count, Ausrichtung.vertikal);
            }
            return null;
        }

        // Horizontale Prüfung vom Ende des Array aufwärts
        static EntryMatch checkHorizontal(int[] array, int arrayWidth) {
            for (int j = (arrayWidth - 1) * arrayWidth; j > 0; j -= arrayWidth) {
                int lastIdx = array[j];
                int count = 1;
                for (int i = 1; i < arrayWidth; i++) {
                    int newIdx = array[j + i];
                    if (newIdx == lastIdx)
                        count++;
                    else {
                        if (count >= 3)
                            return new EntryMatch(j + i - count, count, Ausrichtung.horizontal);
                        count = 1;
                        lastIdx = newIdx;
                    }
                }
                if (count >= 3)
                    return new EntryMatch(j + arrayWidth - count, count, Ausrichtung.horizontal);
            }
            return null;
        }
    }

    public enum Ausrichtung {
        horizontal,
        vertikal
    }

    public class EntryMatch {
        public int Index { get; }
        public int Count { get; }
        public Ausrichtung Richtung { get; }

        public EntryMatch(int index, int count, Ausrichtung richtung) {
            this.Index = index;
            this.Count = count;
            this.Richtung = richtung;
        }
    }
}

 

[cfHxqA]

@lynxx Vielen Dank! Ich werde es mir noch einmal zu Gemüte führen.


Ja, mit dem nach unten Fallen ist schon richtig. Ich lasse die ganze Matrix so oft wiederholen, bis keine Kombination mehr möglich ist. Es wird immer die letzte Matrix mit der gelösten Kombination übergeben. Somit hast Du praktisch eine Endlosschleife, bis nichts mehr möglich ist. Im Anschluss werden die 0-Nullen einfach um einen Index nach oben versetzt - bis diese ganz am Anfang sind.

 

[marcOcram]

Da @lynxx schon eine Lösung gepostet hat, kann ich meine schnelle Lösung als Anregung ja auch noch posten: https://dotnetfiddle.net/XCDCNC

Das Spielfeld wird zufällig generiert, deswegen gibt es manchmal Treffer und manchmal keinen.

using System;
using System.Collections.Generic;
                    
public class Program
{
    public static void Main()
    {
        int[,] board = CreateRandomFilledBoard();

        Console.WriteLine("Board: ");
        Console.WriteLine();
        PrintBoard(board);

        List<Match> matches = FindMatches(board);

        Console.WriteLine();
        foreach (Match match in matches)
        {
            Console.WriteLine(match.Direction + " match at (" + match.IndexX + "," + match.IndexY + ")");
        }
    }

    private static List<Match> FindMatches(int[,] board)
    {
        List<Match> matches = new List<Match>();

        for (int y = 0; y < board.GetLength(1); ++y)
        {
            for (int x = 0; x < board.GetLength(0); ++x)
            {
                Match match = FindMatchFor(board, x, y);

                if (match != null)
                {
                    matches.Add(match);
                }
            }
        }

        return matches;
    }

    private static Match FindMatchFor(int[,] board, int xIndex, int yIndex)
    {
        const int MINIMUM_MATCH_COUNT = 3;

        List<Match> matches = new List<Match>();

        int searchValue = board[xIndex, yIndex];

        {
            // search horizontal
            int remainingIndexCount = (board.GetLength(0) - xIndex) - 1;
            if (remainingIndexCount >= (MINIMUM_MATCH_COUNT - 1))
            {
                int length = 1;
                for (int i = 0; i < remainingIndexCount; ++i)
                {
                    if (board[xIndex + 1 + i, yIndex] == searchValue)
                    {
                        length++;
                    }
                    else
                    {
                        if (length >= MINIMUM_MATCH_COUNT)
                        {
                            return new Match()
                            {
                                Direction = Match.MatchDirection.Horizontal,
                                Length = length,
                                IndexX = xIndex,
                                IndexY = yIndex
                            };
                        }

                        break;
                    }
                }
            }
        }

        {
            // search vertical
            int remainingIndexCount = (board.GetLength(1) - yIndex) - 1;
            for (int y = yIndex; y < board.GetLength(1); ++y)
            {
                int length = 1;
                for (int i = 0; i < remainingIndexCount; ++i)
                {
                    if (board[xIndex, yIndex + 1 + i] == searchValue)
                    {
                        length++;
                    }
                    else
                    {
                        if (length >= MINIMUM_MATCH_COUNT)
                        {
                            return new Match()
                            {
                                Direction = Match.MatchDirection.Vertical,
                                Length = length,
                                IndexX = xIndex,
                                IndexY = yIndex
                            };
                        }

                        break;
                    }
                }
            }
        }

        return null;
    }

    private static void PrintBoard(int[,] board)
    {
        Console.Write("   ");
        for (int x = 0; x < board.GetLength(0); ++x)
        {
            Console.Write(" " + x);
        }
        
        Console.WriteLine();
        Console.Write(" --");
        for (int x = 0; x < board.GetLength(0); ++x)
        {
            Console.Write("--");
        }
        
        Console.WriteLine();
        
        for (int y = 0; y < board.GetLength(1); ++y)
        {
            Console.Write(y + "| ");
            
            for (int x = 0; x < board.GetLength(0); ++x)
            {
                Console.Write(" " + board[x, y]);
            }

            Console.Write(" ");
            Console.WriteLine();
        }
    }

    private class Match
    {
        public enum MatchDirection
        {
            Horizontal,
            Vertical
        }

        public MatchDirection Direction { get; set; }

        public int IndexX { get; set; }

        public int IndexY { get; set; }

        public int Length { get; set; }
    }

    private static int[,] CreateRandomFilledBoard()
    {
        // these could be parameter of the method
        const int MAX_DIMENSION_X = 8;
        const int MAX_DIMENSION_Y = 8;
        const int MIN_BOARD_VALUE = 0;
        const int MAX_BOARD_VALUE = 7;

        int[,] board = new int[MAX_DIMENSION_X, MAX_DIMENSION_Y];

        Random random = new Random(Guid.NewGuid().GetHashCode());

        for (int i = 0; i < board.GetLength(0); ++i)
        {
            for (int j = 0; j < board.GetLength(1); ++j)
            {
                board[i, j] = random.Next(MIN_BOARD_VALUE, MAX_BOARD_VALUE + 1);
            }
        }

        return board;
    }
}

 

[lynxx]

Da @lynxx schon eine Lösung gepostet hat, kann ich meine schnelle Lösung als Anregung ja auch noch posten: https://dotnetfiddle.net/XCDCNC

Das Spielfeld wird zufällig generiert, deswegen gibt es manchmal Treffer und manchmal keinen.

Gefällt mir, leider sind mir zwei Fehler aufgefallen:

        // 1,1,1,1 wird nicht gefunden weil der horizontale Treffer zuerst gefunden
        // wird und dann der Index erhöht wird
        int[,] board = {
            { 1,1,1,1,2,3,4,5 },
            { 1,0,6,4,2,3,4,5 },
            { 1,1,2,3,3,4,5,6 },
            { 2,3,4,5,5,6,3,2 },
            { 2,3,4,5,5,6,3,2 },
            { 3,4,5,7,6,3,2,1 },
            { 4,5,7,6,3,2,1,0 },
            { 1,4,5,7,6,3,2,1 }
        };

        // 1,1,1,1 und 1,1,1 wird gefunden, weil nach dem Fund
        // direkt wieder im nächsten Index gesucht wird
        int[,] board = {
            { 1,1,1,1,2,3,4,5 },
            { 0,0,6,4,2,3,4,5 },
            { 1,1,2,3,3,4,5,6 },
            { 2,3,4,5,5,6,3,2 },
            { 2,3,4,5,5,6,3,2 },
            { 3,4,5,7,6,3,2,1 },
            { 4,5,7,6,3,2,1,0 },
            { 1,4,5,7,6,3,2,1 }
        };

Dieser Code https://dotnetfiddle.net/cQipbE sollte beide Probleme beheben.

using System;
using System.Collections.Generic;
                    
public class Program {
    const int MINIMUM_MATCH_COUNT = 3;
    const int MAX_DIMENSION_X = 8;
    const int MAX_DIMENSION_Y = 8;
    const int MIN_BOARD_VALUE = 0;
    const int MAX_BOARD_VALUE = 7;

    public static void Main() {
        //int[,] board = CreateRandomFilledBoard();
        int[,] board = {
            { 1,1,1,1,2,3,4,5 },
            { 1,0,6,4,2,3,4,5 },
            { 1,1,2,3,3,4,5,6 },
            { 2,3,4,5,5,6,3,2 },
            { 2,3,4,5,5,6,3,2 },
            { 3,4,5,7,6,3,2,1 },
            { 4,5,7,6,3,2,1,0 },
            { 1,4,5,7,6,3,2,1 }
        };

        Console.WriteLine("Board: ");
        Console.WriteLine();
        PrintBoard(board);

        List<Match> matches = FindMatches(board);

        Console.WriteLine();
        foreach (Match match in matches)
            Console.WriteLine(match.Direction + " match at (" + match.IndexX + "," + match.IndexY + ") Length: " + match.Length);
        
        if (matches.Count == 0)
            Console.WriteLine("No matches.");
    }

    private static List<Match> FindMatches(int[,] board) {
        List<Match> matches = new List<Match>();

        for (int y = 0; y < board.GetLength(1); y++) {
            for (int x = 0; x < board.GetLength(0); x++) {
                Match match = FindMatchForVertical(board, x, y);

                if (match != null)
                    matches.Add(match);

                match = FindMatchForHorizontal(board, x, y);

                if (match != null) {
                    matches.Add(match);
                    y += match.Length - 1;
                }
            }
        }

        return matches;
    }

    // search horizontal
    private static Match FindMatchForHorizontal(int[,] board, int xIndex, int yIndex) {
        int searchValue = board[xIndex, yIndex];
        int remainingIndexCount = (board.GetLength(0) - xIndex) - 1;
        if (remainingIndexCount >= (MINIMUM_MATCH_COUNT - 1)) {
            int length = 1;
            for (int i = 0; i < remainingIndexCount; ++i) {
                if (board[xIndex + 1 + i, yIndex] == searchValue)
                    length++;
                else {
                    if (length >= MINIMUM_MATCH_COUNT)
                        return new Match(xIndex, yIndex, length, Match.MatchDirection.Horizontal);

                    break;
                }
            }
        }
        return null;
    }

    // search vertical
    private static Match FindMatchForVertical(int[,] board, int xIndex, int yIndex) {
        int searchValue = board[xIndex, yIndex];
        int remainingIndexCount = (board.GetLength(1) - yIndex) - 1;
        for (int y = yIndex; y < board.GetLength(1); y++) {
            int length = 1;
            for (int i = 0; i < remainingIndexCount; i++) {
                if (board[xIndex, yIndex + 1 + i] == searchValue)
                    length++;
                else {
                    if (length >= MINIMUM_MATCH_COUNT)
                        return new Match(xIndex, yIndex, length, Match.MatchDirection.Vertical);

                    break;
                }
            }
        }

        return null;
    }

    private static void PrintBoard(int[,] board) {
        Console.Write("   ");
        for (int x = 0; x < board.GetLength(0); x++)
            Console.Write(" " + x);
        
        Console.WriteLine();
        Console.Write(" --");
        for (int x = 0; x < board.GetLength(0); x++) 
            Console.Write("--");
        
        Console.WriteLine();
        
        for (int y = 0; y < board.GetLength(1); y++) {
            Console.Write(y + "| ");
            
            for (int x = 0; x < board.GetLength(0); x++)
                Console.Write(" " + board[x, y]);

            Console.Write(" ");
            Console.WriteLine();
        }
    }

    private class Match {
        public enum MatchDirection {
            Horizontal,
            Vertical
        }
        
        public Match(int IndexX, int IndexY, int Length, MatchDirection Direction) {
            this.IndexX = IndexX;
            this.IndexY = IndexY;
            this.Length = Length;
            this.Direction = Direction;
        }

        public int IndexX { get; }

        public int IndexY { get; }

        public int Length { get; }

        public MatchDirection Direction { get; }

    }

    private static int[,] CreateRandomFilledBoard() {
        int[,] board = new int[MAX_DIMENSION_X, MAX_DIMENSION_Y];

        Random random = new Random(Guid.NewGuid().GetHashCode() + Environment.TickCount);

        for (int i = 0; i < board.GetLength(0); i++)
            for (int j = 0; j < board.GetLength(1); j++)
                board[i, j] = random.Next(MIN_BOARD_VALUE, MAX_BOARD_VALUE + 1);
        
        return board;
    }
}