Eckenspiel

Kocha · 28. Januar 2005

Hallo Leute

Ich hab da so ne Aufgabe, bei der ich die Lösung einfach nicht finde :O

Es geht um diese Rätsel, die auf allen möglichen Fernsehsendern jede Nacht laufen.
Eines davon ist ein Spiel, man hat eine Matrix von Buchstaben und muss herausfinden, wie oft sich das gesuchte Wort darin befindet.

Also zb. hier:

PETERG
EPTDFP
TERGGF
XTTARD
PPGRGF

kommt das Wort "PETER" 8mal vor.

Nun verlangt die Aufgabe, dass die Matrix aus einer Datei eingelesen wird, das Wort per Kommandozeilenparameter mitgegeben wird und das Programm dann ausspuckt, wie oft sich das Wort darin befindet.

Das Wort wird um die Ecke gelesen, diagonal ist nicht.
Die Bewegungsrichtung darf sich dabei beliebig oft ändern, allerdings darf ein Buchstabe ein Buchstabe im selben Wort nicht mehrere Male verwendet werden.

Nun ist das Problem, dass die Länge des Wortes, das man übergibt, dynamisch ist. Folglich kann man das ganze ja nicht einfach mit mehreren Schlaufen lösen. Also eine Verkettung der Art:

for(i=0;i<laenge_der_matrix*höhe_der_matrix;i++) //für jeden Anfangsbuchstaben
{
for(j=0;j<4;j++) // für alle Möglichkeiten des 2. Buchstabens
{
for(l=0;l<3;l++) //für alle Möglichkeiten des 3. Buchstabens
{
... //Wenn alle 3 Buchstaben stimmen, anzahl++
}
}
}

Man kann ja nicht eine dynamische Anzahl for-Schlaufen machen

Oder gibt's die und ich komm bloss nich drauf?

Möglicherweise hatte einer von Euch die Aufgabe auch mal im Studium, wäre echt froh, wenn mir jemand helfen könnte.

Grüsse

PS: Falls ich nich verständlich formuliert hab, ist hier das Aufgabenblatt, es ist die unterste Aufgabe, Aufgabe 3

x_Red_Eagle_x · 29. Januar 2005

Hört sich startk nach einer Rekursion an:

Man übergibt einen Buchstaben an eine Funktionion und diese Überprüft ob an den angrenzenden Felder der nächste Buchstabe auftritt.
Falls dies der Fall ist wird die Funktion wieder aufgerufen mit dem benachbarten Buchstaben.

Abbruchbedingung wäre wenn das Wort gefunden wurde (letzter Buchstabe erreicht) od. wenn kein benachbarter Buchstabe vorhanden ist.

mfg

Kocha · 29. Januar 2005

Also eine Funktion, die sich selbst aufruft? :O

zb.:

Code:

public int check(char[][] matrix, char[] wort, int pos_x, int pos_y, int buchstabe, int[][] not_pos){
int anzahl=0;

// Buchstaben eins weiter links

Boolean verboten=false;
for(int i=0;i<buchstabe;i++){
if(not_pos[1][i]==pos_y-1&&not_pos[0][i]==pos_x)verboten=true;
}
if (pos_y-1>-1&&verboten==false&&matrix[pos_x][pos_y-1]==wort[buchstabe]){
not_pos[0][buchstabe]=pos_x;
not_pos[1][buchstabe]=pos_y-1;
if(buchstabe=wort.length)anzahl++;
else anzahl=anzahl+this(matrix,wort,pos_x,pos_y-1,buchstabe+1,not_pos);
}

// Buchstaben eins weiter rechts

verboten=false;
for(int i=0;i<buchstabe;i++){
if(not_pos[1][i]==pos_y+1&&not_pos[0][i]==pos_x)verboten=true;
}
if (pos_y+1>-1&&verboten==false&&matrix[pos_x][pos_y+1]==wort[buchstabe]){
not_pos[0][buchstabe]=pos_x;
not_pos[1][buchstabe]=pos_y+1;
anzahl=anzahl+this(matrix,wort,pos_x,pos_y+1,buchstabe+1,not_pos);
if(buchstabe=wort.length)anzahl++;
else anzahl=anzahl+this(matrix,wort,pos_x,pos_y+1,buchstabe+1,not_pos);
}

// Buchstaben eins weiter oben

verboten=false;
for(int i=0;i<buchstabe;i++){
if(not_pos[0][i]==pos_x-1&&not_pos[1][i]==pos_y)verboten=true;
}
if (pos_x-1>-1&&verboten==false&&matrix[pos_x-1][pos_y]==wort[buchstabe]){
not_pos[0][buchstabe]=pos_x-1;
not_pos[1][buchstabe]=pos_y;
anzahl=anzahl+this(matrix,wort,pos_x-1,pos_y,buchstabe+1,not_pos);
if(buchstabe=wort.length)anzahl++;
else anzahl=anzahl+this(matrix,wort,pos_x,pos_y-1,buchstabe+1,not_pos);
}

// Buchstaben eins weiter unten

verboten=false;
for(int i=0;i<buchstabe;i++){
if(not_pos[1][i]==pos_x+1&&not_pos[1][i]==pos_y)verboten=true;
}
if (pos_x+1>-1&&verboten==false&&matrix[pos_x+1][pos_y]==wort[buchstabe]){
not_pos[0][buchstabe]=pos_x;
not_pos[1][buchstabe]=pos_y+1;
anzahl=anzahl+this(matrix,wort,pos_x+1,pos_y,buchstabe+1,not_pos);
if(buchstabe=wort.length)anzahl++;
else anzahl=anzahl+this(matrix,wort,pos_x+1,pos_y,buchstabe+1,not_pos);
}

return anzahl;

}

Thomas Darimont · 29. Januar 2005

Hallo!

Gibt's da vielleicht noch mehr Beispiele um einen "vielleicht" vorhandenen Algorithmus zu testen?

Gruß Tom

Kocha · 29. Januar 2005

Als Beispiel kannst ja eigntlich alles nehmen, zb. im oberen Beispiel statt PETER nimmst RETEP oder RE oder wie auch immer.

Oder nimmst ne zb. EEE und machst ne Datei wie

ERZUEEE
EEISERE
ERTUERE

Wären 16 :-(

Hier, ich hab's soweit fertig, is aber vielleicht nicht sonderlich schön geschrieben

Code:

import java.io.*;

/**
 *
 * 
 */
public class Main {
    
    /** Creates a new instance of Main */
    public Main() {
    }
    public int check(char[][] matrix, char[] wort, int pos_x, int pos_y, int buchstabe, int[][] not_pos,int zeile,int breite){
        int anzahl=0;
        int tmp=0;
        // Buchstaben eins weiter links
        Boolean verboten=false;
        for(int i=0;i<buchstabe;i++){
            if(not_pos[1][i]==pos_y-1&&not_pos[0][i]==pos_x)verboten=true;
        }
        if (pos_y-1>-1&&verboten==false){
            if(matrix[pos_x][pos_y-1]==wort[buchstabe]){
                not_pos[0][buchstabe]=pos_x;
                not_pos[1][buchstabe]=pos_y-1;
                if(buchstabe==wort.length-1)anzahl++;
                else anzahl=anzahl+check(matrix,wort,pos_x,pos_y-1,buchstabe+1,not_pos,zeile,breite);
            }
        }
        // Buchstaben eins weiter rechts

        verboten=false;
        for(int i=0;i<buchstabe;i++){
            if(not_pos[1][i]==pos_y+1&&not_pos[0][i]==pos_x)verboten=true;
        }
        if (pos_y+1<breite&&verboten==false){
            if(matrix[pos_x][pos_y+1]==wort[buchstabe]){
                not_pos[0][buchstabe]=pos_x;
                not_pos[1][buchstabe]=pos_y+1;
                if(buchstabe==wort.length-1)anzahl++;
                else anzahl=anzahl+check(matrix,wort,pos_x,pos_y+1,buchstabe+1,not_pos,zeile,breite);
            }
        }
        // Buchstaben eins weiter oben

        verboten=false;
        for(int i=0;i<buchstabe;i++){
            if(not_pos[0][i]==pos_x-1&&not_pos[1][i]==pos_y)verboten=true;
        }
        if (pos_x-1>-1&&verboten==false){
            if(matrix[pos_x-1][pos_y]==wort[buchstabe]){
                not_pos[0][buchstabe]=pos_x-1;
                not_pos[1][buchstabe]=pos_y;
                if(buchstabe==wort.length-1)anzahl++;
                else anzahl=anzahl+check(matrix,wort,pos_x-1,pos_y,buchstabe+1,not_pos,zeile,breite);
            }
        }
        // Buchstaben eins weiter unten

        verboten=false;
        for(int i=0;i<buchstabe;i++){
            if(not_pos[0][i]==pos_x+1&&not_pos[1][i]==pos_y)verboten=true;
        }
        if (pos_x+1<zeile&&verboten==false){
            if(matrix[pos_x+1][pos_y]==wort[buchstabe]){
                not_pos[0][buchstabe]=pos_x+1;
                not_pos[1][buchstabe]=pos_y;
                if(buchstabe==wort.length-1)anzahl++;
                else anzahl=anzahl+check(matrix,wort,pos_x+1,pos_y,buchstabe+1,not_pos,zeile,breite);
            }
        }

        return anzahl;

}
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        char[][] tmp=new char[1024][1024];
        char[] wort;
        int anzahl=0;
        int zeile=0;
        int laenge=0;
        int i=0;
        int j=0;
        if(args.length!=1){
            System.out.println("Aufruf: java eckenspiel.Main \"Gesuchtes Wort\"");
            System.exit(1);
        }
        
        wort=args[0].toCharArray();

        for (i=0;i<args[0].length();i++){
            wort[i]=args[0].charAt(i);
        }
        
        
        String filename = "ecke.txt";
        try {
            BufferedReader reader = new BufferedReader(new FileReader(filename));
            String inputLine; // a line of input from the file
            while (true) {    // exit with break
                inputLine = reader. readLine();
                if (inputLine == null) break;
                if (laenge==0) laenge=inputLine.length();
                for (i=0;i<inputLine.length();i++){
                    tmp[zeile][i]=inputLine.charAt(i);
                }
                zeile++;
            }
            reader. close();
	}
	catch (FileNotFoundException e) {
            System. out. println(" Error: " + filename + " not found");
            System.exit(2);
	}
	catch (IOException e) {
            System. out. println(" I/ O error while reading");
            System.exit(3);
	}
        
        char[][] chrs=new char[zeile][laenge];
        for (i=0;i<zeile;i++){
            for(j=0;j<laenge;j++){
                chrs[i][j]=tmp[i][j];
            }
        }
        int[][] notmatrix=new int[2][wort.length];
        Main app=new Main();
        
        for(i=0;i<zeile;i++){
            for(j=0;j<laenge;j++){
                if(chrs[i][j]==wort[0]){
                    if(wort.length>1){
                        for(int k=0;k<wort.length;k++){
                            notmatrix[0][k]=-1;
                            notmatrix[1][k]=-1;
                        }
                        notmatrix[0][0]=i;
                        notmatrix[1][0]=j;
                        anzahl=anzahl+app.check(chrs,wort,i,j,1,notmatrix,zeile,laenge);
                    }
                    else{
                        anzahl++;
                    }
                }
            }
        }
                
        System.out.println("Anzahl "+String.valueOf(wort)+" in "+filename+": "+anzahl);
    
    }
}

//Edit: Hab mich verzählt :-(

Kocha · 1. Februar 2005

Hattest Du noch ne andere Idee, Tom? :O

Thomas Darimont · 1. Februar 2005

LOL!

Hab auch 16 rausgehabt und dachte das mein Algorithmus nicht funktionieren würde ^^ ;-)
Poste heute Abend mal meine Version...

Gruß Tom

Kocha · 1. Februar 2005

Entschuldige, ich bin ein Dummkopf :-(

Okay, ich freu mich schon drauf, bis denn dann

Thomas Darimont · 1. Februar 2005

Hallo!

... leider funktioniert das ganze mit dem zweiten Beispiel nicht... bekomme 28 als Ergebnis ... die suche nach Peter hingegen liefert jedoch das korrekte Ergebnis: 8.

Code:

/*
 * Created on 29.01.2005@15:23:29
 *
 * TODO Licence info
 */
package de.tutorials;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author Administrator
 *
 * TODO Explain me
 */
public class Cruncher {

    private String str = "PETER";

    char[] sA = str.toCharArray();

    char[][] data = { { 'P', 'E', 'T', 'E', 'R', 'G' },
            { 'E', 'P', 'T', 'D', 'F', 'P' }, { 'T', 'E', 'R', 'G', 'G', 'F' },
            { 'X', 'T', 'T', 'A', 'R', 'D' }, { 'R', 'E', 'T', 'E', 'R', 'G' },
            { 'P', 'P', 'G', 'R', 'G', 'F' } };

    private static final int UP = -1;

    private static final int DOWN = 1;

    private static final int LEFT = -1;

    private static final int RIGHT = 1;

    private int cnt;

    private List visited = new ArrayList();

    public static void main(String[] args) {
        new Cruncher().crunch();
    }

    /**
     * 
     */
    private void crunch() {
        System.out.println("Eingangsdaten:");
        printData();
        clearData();
        System.out.println("\nBereinigte Eingangsdaten:");
        printData();

        char startC = sA[0];
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[0].length; j++) {
                char c = data[i][j];
                if (c == startC)
                    doDeepSearch(i, j, c, 0);
            }
        }

        System.out.println();
        System.out.println(cnt);
    }

    /**
     * @param i
     * @param j
     */
    private void doDeepSearch(int i, int j, char c, int idx) {
        if (idx == 0) {
            visited.clear();
        }

        if (c == sA[sA.length - 1] && idx == sA.length - 1) {
            ++cnt;
            return;
        }

        if (sA[idx] == c) {
            Point[] posibilities = new Point[4];

            posibilities[0] = checkUp(i, j, idx + 1);
            posibilities[1] = checkDown(i, j, idx + 1);
            posibilities[2] = checkLeft(i, j, idx + 1);
            posibilities[3] = checkRight(i, j, idx + 1);

            if (posibilities[0] == null && posibilities[1] == null
                    && posibilities[2] == null && posibilities[3] == null) {
                visited.clear();
                return;
            }

            for (int k = 0; k < posibilities.length; k++) {
                Point point = posibilities[k];
                if (point == null)
                    continue;
                else {
                    doDeepSearch(point.y, point.x, sA[idx + 1], idx + 1);
                }
            }
        }
    }

    /**
     * @param i
     * @param j
     * @param k
     * @return
     */
    private Point checkUp(int i, int j, int k) {

        int x = j;
        int y = i + UP;

        if (y < 0)
            return null;

        if (!(data[y][x] == sA[k]))
            return null;

        Point p = new Point(x, y);

        p = justVisited(p);

        return p;
    }

    /**
     * @param p
     * @return
     */
    private Point justVisited(Point p) {
        Point pTmp = p;
        for (Iterator iter = visited.iterator(); iter.hasNext();) {
            Point p0 = (Point) iter.next();
            if (p0.equals(pTmp)) {
                pTmp = null;
                break;
            }
        }

        if (pTmp != null)
            visited.add(pTmp);

        return pTmp;
    }

    /**
     * @param i
     * @param j
     * @param k
     * @return
     */
    private Point checkDown(int i, int j, int k) {

        int x = j;
        int y = i + DOWN;

        if (y >= data.length)
            return null;

        if (!(data[y][x] == sA[k]))
            return null;

        Point p = new Point(x, y);

        p = justVisited(p);

        return p;
    }

    /**
     * @param i
     * @param j
     * @param k
     * @return
     */
    private Point checkLeft(int i, int j, int k) {

        int x = j + LEFT;
        int y = i;

        if (x < 0)
            return null;

        if (!(data[y][x] == sA[k]))
            return null;

        Point p = new Point(x, y);

        p = justVisited(p);

        return p;
    }

    /**
     * @param i
     * @param j
     * @param k
     * @return
     */
    private Point checkRight(int i, int j, int k) {

        int x = j + RIGHT;
        int y = i;

        if (x >= data[0].length)
            return null;

        if (!(data[y][x] == sA[k]))
            return null;

        Point p = new Point(x, y);

        p = justVisited(p);

        return p;
    }

    /**
     * 
     */
    private void clearData() {
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                if (str.indexOf(data[i][j]) < 0) {
                    data[i][j] = ' ';
                }
            }
        }
    }

    /**
     * 
     */
    private void printData() {
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                System.out.print(data[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}

Gruß Tom

torsch2711 · 2. Februar 2005

Mal eine kurze frage, wo bitte schön bekommt ihr die 8 Peters her?

Entweder hab ich ne eingeschränkte wahrnehmung oder ich raff's einfach nicht

Ich komm immer auf 4 Peter's

Ansonsten habt ihr berücksichtigt, das eigentlich nur wenn ein P oder R an dem Punkt auftaucht und dieses noch nicht rekursiv abgearbeitet wurde berücksichtigt werden muss?
P für den Anfang des Wortes, R falls es rückwärts geschrieben ist und mal ganz ehrlich ich finde nicht das wenn ein peter schon gezählt wurde auch noch rückwärts gezählt werden darf, da diese Buchstabenkombination schon gezählt wurde.

Oder ist dies erlaubt? Wenn ja finde ich diese regel irgendwie nicht ganz schlüssig, da
hier ein und derselbe Peter 2 mal gezählt wird.....

Gruss Torsten

Eckenspiel

Kocha

Gesperrt

x_Red_Eagle_x

Erfahrenes Mitglied

Kocha

Gesperrt

Thomas Darimont

Erfahrenes Mitglied

Kocha

Gesperrt

Kocha

Gesperrt

Thomas Darimont

Erfahrenes Mitglied

Kocha

Gesperrt

Thomas Darimont

Erfahrenes Mitglied

torsch2711

Erfahrenes Mitglied

Neue Beiträge