Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Pathfinder (Algorithmen)

Du und deine Freunde besuchen den Weihnachtsmarkt in Adatown, welcher weiterherum berühmt ist für seine köstlichen Leckereien. Um den alljährlichen Besucher-Ansturm meistern zu können, hat der Veranstalter dieses Jahr die Fressbuden-Zelte in einem quadratischen Raster aufgestellt. Dabei hat er besonders beliebte Fressbuden gleich mehrfach aufgestellt, damit sich keine langen Schlangen bilden. Der Zutritt zum Gelände erfolgt dabei ausschliesslich über die Bude oben links, bei welcher Glühwein ausgeschenkt wird, der Ausgang befindet sich auf der gegenüberliegenden Seite (unten rechts), um einerseits den Strom der Besucher aufrechtzuerhalten, andererseits natürlich auch, damit die Besucher möglichst viele Stände besuchen. Jedes Fressbuden-Zelt kann übrigens immer nur seitwärts verlassen werden (sprich horizontal oder vertikal).

 

Du und deine Freunde haben sich nun einen Plan der Fressbunde besorgt:

 

1
Glühwein

B
Raclette

5
Wienerli

6
Magenbrot

2
Zimtbrötchen

3
Honigmakrelen

4
Pfeffernüsse

7
Fondue

3
Honigmakrelen

A
Zuckerwatte

9
Spiessli

8
Nasi Goreng

4
Pfeffernüsse

7
Fondue

A
Zuckerwatte

B
Raclette

 

Ihr startet also zwingend oben bei der Bude 1, wo es Glühwein gibt und kommt ganz am Schluss bei der Bude B unten rechts vorbei, bei der es Raclette gibt.

 

Da ihr keine Lust habt, auf dem Weg dorthin zweimal dasselbe zu degustieren (einmal Fondue reicht auch wirklich), sucht ihr nun nach einem Weg durch all die Fressbuden, bei dem ihr bei jeder Köstlichkeit genau ein einziges Mal vorbei kommt. Ihr wollte dabei weder durch bereits besuchte Buden laufen noch wollt ihr durch Buden durchlaufen, deren Köstlichkeiten ihr bereits in einer anderen Buden bereits probiert habt.

Natürlich wird das nächste Jahr wieder ausgebaut. Damit ihr nicht nochmals den kürzesten Weg suchen müsst, schreibt ihr gleich ein Programm, das den kürzesten Weg mit allen Leckereien selbst findet und testet diesen auch gleich noch an dem folgenden Raster aus:

----------------------------------------------------

Beispiel-Raster (Variante 5x5)

1 2 3 B 9
6 3 A 4 7
C 4 2 4 8
6 5 A B C
7 8 9 2 D

Gesetzter Startpunkt: Oben links (1)

Gesetzter Zielpunkt: Unten rechts (D)

Anzahl Zeichen: 13 (123456789ABCD)

----------------------------------------------------

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

3 Lösung(en)

DCL 1 COL(4,4)                                    
     ,5 VALUE  CHAR(1)                            
     ,5 USED   BIT(1)                             
     ;                                            
DCL TRACE(11) BIN FIXED(31);                      
DCL ZWOUT(11) CHAR(1);                            
DCL DF_ZWOUT CHAR(11) BASED(ADDR(ZWOUT(1)));      
DF_ZWOUT = '';                                    
DCL IX_TRACE BIN FIXED(31) INIT(0);               
                                                  
COL(1,1).VALUE = '1';                             
COL(1,2).VALUE = 'B';                             
COL(1,3).VALUE = '5';                             
COL(1,4).VALUE = '6';                             
COL(2,1).VALUE = '2';                             
COL(2,2).VALUE = '3';                             
COL(2,3).VALUE = '4';                             
COL(2,4).VALUE = '7';                             
COL(3,1).VALUE = '3';                             
COL(3,2).VALUE = 'A';                             
COL(3,3).VALUE = '9';                             
COL(3,4).VALUE = '8';                             
COL(4,1).VALUE = '4';                             
COL(4,2).VALUE = '7';                             
COL(4,3).VALUE = 'A';                             
COL(4,4).VALUE = 'B';                             
                                                  
COL(1,1).USED  = '0'B;                        
COL(1,2).USED  = '0'B;                        
COL(1,3).USED  = '0'B;                        
COL(1,4).USED  = '0'B;                        
COL(2,1).USED  = '0'B;                        
COL(2,2).USED  = '0'B;                        
COL(2,3).USED  = '0'B;                        
COL(2,4).USED  = '0'B;                        
COL(3,1).USED  = '0'B;                        
COL(3,2).USED  = '0'B;                        
COL(3,3).USED  = '0'B;                        
COL(3,4).USED  = '0'B;                        
COL(4,1).USED  = '0'B;                        
COL(4,2).USED  = '0'B;                        
COL(4,3).USED  = '0'B;                        
COL(4,4).USED  = '0'B;                        
                                              
DCL XMIN BIN FIXED(31) INIT(1);               
DCL XMAX BIN FIXED(31) INIT(4);               
DCL YMIN BIN FIXED(31) INIT(1);               
DCL YMAX BIN FIXED(31) INIT(4);               
DCL SW_END BIT(1) INIT('0'B);                 
DCL POS_X BIN FIXED(31) INIT(1);              
DCL POS_Y BIN FIXED(31) INIT(1);              
DCL KOLEFT  BIN FIXED(31) VALUE(1);           
DCL KORIGHT BIN FIXED(31) VALUE(2);           
DCL KOUP    BIN FIXED(31) VALUE(3);           
DCL KODOWN  BIN FIXED(31) VALUE(4);           
DCL SAVE_MOVE BIN FIXED(31) INIT(0);          
DCL KO_MAXMOVE BIN FIXED(31) VALUE(11);                                
                                                                       
/* INIT: BEGIN */                                                      
  IX_TRACE = 1;                                                        
  ZWOUT(1) = COL(XMIN,YMIN).VALUE;                                     
  COL(XMIN,YMIN).USED  = '1'B;                                         
/* INIT: END */                                                        
                                                                       
DO WHILE(SW_END = '0'B);                                               
  CALL FMOVE;                                                          
  IF SAVE_MOVE = KODOWN THEN DO;                                       
    CALL TRACE_REM;                                                    
    IF IX_TRACE = 0 THEN SW_END = '1'B;                                
  END;                                                                 
END;                                                                   
                                                                       
/*-------------------------------------------------------------------*/

FMOVE: PROC();                                                         
  SELECT(SAVE_MOVE);                                                   
    WHEN(KOLEFT  - 1) CALL FDOMOVE(KOLEFT);                            
    WHEN(KORIGHT - 1) CALL FDOMOVE(KORIGHT);                           
    WHEN(KOUP    - 1) CALL FDOMOVE(KOUP);                              
    WHEN(KODOWN  - 1) CALL FDOMOVE(KODOWN);                            
    OTHER;                                                             
  END;                                                                 
END FMOVE;                                                             
                                                                       
/*-------------------------------------------------------------------*/
                                                                       
FDOMOVE: PROC(DIR);                                                   
  DCL DIR       BIN FIXED(31);                                        
  DCL NEW_POS_X BIN FIXED(31);                                        
  DCL NEW_POS_Y BIN FIXED(31);                                        
                                                                      
  SAVE_MOVE = DIR;                                                    
                                                                      
  NEW_POS_X = POS_X;                                                  
  NEW_POS_Y = POS_Y;                                                  
  SELECT(DIR);                                                        
    WHEN(KOLEFT)  NEW_POS_X -= 1;                                     
    WHEN(KORIGHT) NEW_POS_X += 1;                                     
    WHEN(KOUP)    NEW_POS_Y -= 1;                                     
    WHEN(KODOWN)  NEW_POS_Y += 1;                                     
    OTHER;                                                            
  END;                                                                
                                                                      
  /* Test: Ausserhalb Matrix? */                                      
  IF NEW_POS_X < XMIN ! NEW_POS_X > XMAX !                            
     NEW_POS_Y < YMIN ! NEW_POS_Y > YMAX THEN DO;                     
    PUT SKIP LIST('    > Ausserhalb Matrix' !!                        
                  ' (' !! TRIM(CHAR(NEW_POS_X)) !!                    
                  ',' !! TRIM(CHAR(NEW_POS_Y)) !! ')');               
    RETURN;                                                           
  END;                                                                
                                                                      
  /* Test: Pos nicht bereits verwendet? */                            
  IF COL(NEW_POS_X,NEW_POS_Y).USED = '1'B THEN DO;                    
    PUT SKIP LIST('    > Bereits verwendete Position' !!       
                  ' (' !! TRIM(CHAR(NEW_POS_X)) !!             
                  ',' !! TRIM(CHAR(NEW_POS_Y)) !! ')');        
    RETURN;                                                    
  END;                                                         
                                                               
  /* Test: Inhalt nicht bereits verwendet? */                  
  IF TRACE_CHK(COL(NEW_POS_X,NEW_POS_Y).VALUE) = '1'B THEN DO; 
    PUT SKIP LIST('    > Bereits verwendeter Wert ' !!         
                  COL(NEW_POS_X,NEW_POS_Y).VALUE);             
    RETURN;                                                    
  END;                                                         
                                                               
  /* Test: Finale Koord zu früh erreicht? */                   
  IF NEW_POS_X = XMAX & NEW_POS_Y = YMAX &                     
    IX_TRACE < (KO_MAXMOVE - 1) THEN DO;                       
    PUT SKIP LIST('    > Zu wenig Züge');                      
    RETURN;                                                    
  END;                                                         
                                                               
  /* Alles okay */                                             
  POS_X = NEW_POS_X;                                           
  POS_Y = NEW_POS_Y;                                           
  COL(POS_X,POS_Y).USED = '1'B;                                
  CALL TRACE_ADD(DIR);                                         
                                                               
  /* Test: Finale Koord erreicht? */                           
  IF NEW_POS_X = XMAX & NEW_POS_Y = YMAX &                     
    IX_TRACE = KO_MAXMOVE THEN DO;                                     
    PUT SKIP LIST('    > Ziel erreicht');                              
    SW_END = '1'B;                                                     
  END;                                                                 
                                                                       
END FDOMOVE;                                                           
                                                                       
/*-------------------------------------------------------------------*/
                                                                       
TRACE_ADD: PROC(DIR);                                                  
  DCL DIR  BIN FIXED(31);                                              
  IX_TRACE += 1;                                                       
  TRACE(IX_TRACE) = DIR;                                               
  ZWOUT(IX_TRACE) = COL(POS_X,POS_Y).VALUE;                            
  PUT SKIP LIST('+' !! DF_ZWOUT !! ' (' !!                             
                TRIM(CHAR(POS_X)) !! ',' !! TRIM(CHAR(POS_Y)) !! ')'); 
  SAVE_MOVE = 0;                                                       
END TRACE_ADD;                                                         
                                                                       
/*-------------------------------------------------------------------*/

TRACE_REM: PROC();                                                     
  COL(POS_X,POS_Y).USED = '0'B;                                        
  SAVE_MOVE = TRACE(IX_TRACE);                                         
  SELECT(TRACE(IX_TRACE));                                             
    WHEN(KOLEFT)  POS_X += 1;                                          
    WHEN(KORIGHT) POS_X -= 1;                                          
    WHEN(KOUP)    POS_Y += 1;                                          
    WHEN(KODOWN)  POS_Y -= 1;                                          
    OTHER;                                                             
  END;                                                                 
  TRACE(IX_TRACE) = 0;                                                 
  ZWOUT(IX_TRACE) = '';                                                
  IX_TRACE -= 1;                                                       
  PUT SKIP LIST('-' !! DF_ZWOUT);                                      
END TRACE_REM;                                                         
                                                                       
/*-------------------------------------------------------------------*/
                                                                       
TRACE_CHK: PROC(CHKSTR) RETURNS(BIT(1));                               
  DCL CHKSTR CHAR(01);                                                 
  DCL CHKIN  BIN FIXED(31) INIT(0);                                    
  DO CHKIN = 1 TO IX_TRACE;                                            
    IF ZWOUT(CHKIN) = CHKSTR THEN RETURN('1'B);                        
  END;                                                                 
  RETURN('0'B);                                                        
END TRACE_CHK;                                                         
                                                                       
/*-------------------------------------------------------------------*/


                

Lösung von: Valentin Marolf (AXA)

#Author: Sebastian Bach
#02.03.2016


#######Definitions########

import collections
coord=""
def new():
    global rows;
    rows=eval(raw_input("Please enter the number of rows: "));
    global cols;
    cols=eval(raw_input("Please enter the number of columns: "));
    chars=raw_input("Please enter all used characters seperated by ';': ");
    global chars;
    chars=chars.split(';');
    global coord;
    coord= [''];
    temp= [''];
    for i in range(1, rows+1):
        for j in range(1, cols+1):
            field=""
            while field not in chars or field=="":
                string="Please enter character of field " + str(i) + ":" + str(j) + ": ";
                field=raw_input(string);
            temp.append(field);
        coord.append(temp);
        temp= [''];

def init():
    global start;
    start=raw_input("Please enter the coordinates of the starting field seperated by ';' (row;column): ");
    start=start.split(';');
    global startType
    startType=coord[int(start[0])][int(start[1])];
    global end;
    end=raw_input("Please enter the coordinates of the destination field seperated by ';' (row;column): ");
    end=end.split(';');
    global endType
    endType=coord[int(end[0])][int(end[1])];
    global charsEnd;
    charsEnd=chars
    charsEnd.remove(str(endType));

def initVars():
    global way;
    way=[];
    global typeway;
    typeway=[];
    global old;
    old=[];
    global opp;
    opp=[];


def script(old):
    way.append(old);
    oldType=coord[int(old[0])][int(old[1])];
    typeway.append(oldType);
    print "UFeld: " +str(old)+" ;Typ: " +str(oldType);
    opp=[];
    neighbours=[];
    for i in range(1, 5):
        temp=[];
        for j in range(1, 3):
            temp.append('');
        neighbours.append(temp);
        temp=[];
    if old[1]!=cols:
        neighbours[0][1]=int(old[1])+1;
        neighbours[0][0]=int(old[0]);
    if old[1]!=1:
        neighbours[1][1]=int(old[1])-1;
        neighbours[1][0]=int(old[0]);
    if old[0]!=rows:
        neighbours[2][1]=int(old[1]);
        neighbours[2][0]=int(old[0])+1;
    if old[0]!=1:
        neighbours[3][1]=int(old[1]);
        neighbours[3][0]=int(old[0])-1;
    for n in neighbours:
        if n!=['','']:
            nType=coord[int(n[0])][int(n[1])];
            if nType not in typeway:
                if nType!=endType:
                    opp.append(n);
                    print "Appended "+str(n)+" to oppotunities"; 
                elif str(n[0])==str(end[0]) and str(n[1])==str(end[1]):
                    if collections.Counter(typeway)==collections.Counter(charsEnd) : #alle Elemente im Verlauf
                        way.append(n);
                        typeway.append(nType);
                        print('\n\nAll Chars -->finished\n\nResult:\n');
                        return 'true';
                else:
                    print str(n)+"=="+str(end)+"?";
    if opp==[]:
        way.pop();
        typeway.pop();
        return 'false';
    all=0
    false=0
    for o in opp:
        all+=1
        r=script(o)
        if r=='true':
            return 'true';
        elif r=='false':
            false+=1
    if opp==[] or false==all:
        way.pop();
        typeway.pop();
        return 'false';

	
####Main_Script####



print("This is the pathfinding script for http://www.programmieraufgaben.ch/aufgabe/pathfinder/ow782ug0\n");
new();
init();
initVars();
old=[ int(start[0]), int(start[1]) ];
r=script(old);
if r=='false':
    print 'No way found';
else:
	count=1;
	for s in way:
		print "The "+str(count)+". field is "+str(s)+" with Value "+str(coord[int(s[0])][int(s[1])]);
		count+=1;

                

Lösung von: Name nicht veröffentlicht

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

const uint8_t feld_aufgabe[4][4] = {
    {0x1, 0xb, 0x5, 0x6},
    {0x2, 0x3, 0x4, 0x7},
    {0x3, 0xa, 0x9, 0x8},
    {0x4, 0x7, 0xa, 0xb}
};

uint8_t max_x = 5; // 4;
uint8_t max_y = 5; // 4;
uint16_t alleFelderMask = 0x3ffe; // 0xffe;

const uint8_t feld[5][5] = {
    {0x1, 0x2, 0x3, 0xb, 0x9},
    {0x6, 0x3, 0xa, 0x4, 0x7},
    {0xc, 0x4, 0x2, 0x4, 0x8},
    {0x6, 0x5, 0xa, 0xb, 0xc},
    {0x7, 0x8, 0x9, 0x2, 0xd}
};

typedef struct {
    uint8_t x, y;
} weg_punkt_t;

bool pathfinder(int8_t x, int8_t y, uint16_t besuchteFelder, weg_punkt_t* weg) {
    uint16_t bitmaskFeld;
    // gibt es das Feld ?
    if ((x < 0) || (x >= max_x) || (y < 0) || (y >= max_y)) {
        return false; 
    }
    // Feld noch nicht besucht ?
    bitmaskFeld = 1 << feld[y][x];
    if ((bitmaskFeld & besuchteFelder) == 0) {
        besuchteFelder |= bitmaskFeld; // Feld als besucht markieren
        weg->x = x; // Wegpunkt in List eintragen
        weg->y = y;
        //printf("%x (%d, %d) %04x\n", feld[y][x], x, y, besuchteFelder);
        if ((x == (max_x-1)) && (y == (max_y-1)) && (besuchteFelder == alleFelderMask)) {
            return true; // Lösung gefunden
        } else {
            if (pathfinder(x + 1, y, besuchteFelder, &weg[1])) {
                return true;
            } else if (pathfinder(x, y + 1, besuchteFelder, &weg[1])) {
                return true;
            } else if (pathfinder(x - 1, y, besuchteFelder, &weg[1])) {
                return true;
            } else if (pathfinder(x, y - 1, besuchteFelder, &weg[1])) {
                return true;
            } else {
                return false;
            }
        }
    } else {
        return false;
    }
}

int main() {
    uint8_t i = 0;
    weg_punkt_t weg[13];
    if (pathfinder(0, 0, 0, weg)) {
        printf("Optimalen Weg gefunden\n");
        for (i = 0; i < 13; i++) {
            uint8_t feldNr = feld[weg[i].y][weg[i].x];
            printf("%x (%d, %d)\n", feldNr, weg[i].x, weg[i].y);
        }
        return 0;
    } else {
        printf("Keinen optimalen Weg gefunden\n");
        return 1;
    }
}

                

Lösung von: Martin Boekhoff (PTScientists)

Verifikation/Checksumme:

Beispiel-Trace-Log:

+12          (2,1)                       
+123         (3,1)                       
+1234        (4,1)                       
+12347       (4,2)                       
+12347A      (3,2)                       
+12347A9     (3,3)                       
+12347A98    (3,4)                       
-12347A9                                 
-12347A                                       
-12347                                        
+12347A      (4,3)                            
+12347A9     (3,3)                            
+12347A98    (3,4)                            
-12347A9                                      
-12347A                                       
-12347                                        
-1234                                         
-123                                          
+123A        (3,2)                            
+123A7       (4,2)                                   
+123A74      (4,1)                                   
-123A7                                               
-123A                                                
+123A9       (3,3)                                   
+123A94      (2,3)                                   
+123A945     (1,3)                                   
+123A945B    (1,2)                                   
-123A945                                             
+123A9456    (1,4)                                   
+123A94567   (2,4)                     
+123A945678  (3,4)                     
+123A945678B (4,4)                     

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: Mittel
Webcode: ow78-2ug0
Autor: Valentin Marolf (AXA)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen