Σκοτεινός Λαβύρινθος

[k33theod]

Για όσους βαριούνται

αλλά είναι δύσκολο

 

https://py.checkio.org/mission/dark-labyrinth/

 

Με λίγα λόγια ο παίκτης μας είναι σε ένα λαβύρινθο και έχει ένα flashlight. Από τη κάθε θέση μπορεί να βλέπει με το φακό ένα κομμάτι του λαβύρινθου το οποίο προσομοιάζεται με ένα δισδιάστατο "πίνακα"

με '.' διάδρομος 'Χ' τοίχος '?' άγνωστο. (όπως στο link)

πχ

("???XXX",
"???...",
"???X.X",
"XXXX.X",
"X...PX",
"XXXX.X",
"???X.X",
"???...",
"???X.X",
"???X.X",
"???..X",
"???XXX")

 

 

πρέπει να γράψουμε ένα πρόγραμμα που να επιστρέφει σειρά από κινήσεις πχ 'NSWEENS' μία ή περισσότερες  με N north

S south E east W west που να βγάζει τον παίκτη από τον λαβύρινθο σε λιγότερες από 250 κινήσεις

 

To πρόγραμμά μας καλλείται από το test environment μέχρι να συμπηρωθούν οι κινήσεις ή να βρούμε την έξοδο ή να πέσουμε στον τοίχο 

 

 

[kaliakman]

Που ειναι η έξοδος?

Όταν δεις ένα κομμάτι μπορείς να ανανεώσεις τον πίνακα?

Αν ναι, τότε μια απλη αναδρομή ή dfs το λύνουν εύκολα.

[k33theod]

H έξοδος αν εμφανιστεί θα έχει το γράμμα 'E'

Τι εννοείς ανανεώσεις

Τον νέο πίνακα θα σου τον δώσει το περιβάλλον του παιχνιδιού.

Φαντάσου ότι παίζεις το παιχνίδι ή ακόμα καλύτερα ότι είσαι σε ένα λαβύρινθο σκοτείνό και έχεις ένα πολύ δυνατό φακό μόνο και ένα λαπτοπ 

Χρόνο πολύ βήματα λίγα 

[hh12]

Δεν διαβασα κατι τετοιο στην εκφωνηση, οποτε να σημειωσω οτι θα πρεπει ο παιχτης να μπορει να αφηνει καποιο σημαδι πισω του ετσι ωστε να ξερει απο που εχει περασει και απο που οχι δηλ. να κραταμε καπως τις αδιεξοδους που εχει πετυχει. Θα μπορουσε να υλοποιηθει αναδρομικα αλλα θα ηταν κατι σαν brute-forcing. Βασικα το brute-forcing ειναι αναποφευκτο αλλα νομιζω πως εχω σκεφτει εναν λιγο πιο εξυπνο αλγοριθμο. Θα το δουλεψω μολις εχω χρονο και θα ποσταρω το κωδικα.

[k33theod]

Εγώ το προσπαθώ με άλλο σκεπτικό αλλά ακόμα δεν το έλυσα

BAM! You in the wall at 5, 6.

 

στο 2ο τεστ που σημαίνει μάλλον ότι έναν λαβύρινθο τον πέρασα

H main μου είναι αυτή

def find_path(visible):#main function
  global maze
  global path
  center=[15,15]
  lista1=make_list(visible)#I conver the tuple of stings into a list
  start=get_position(lista1,'P')#I get coords of player
  if get_position(lista1,'E'): # Looking for Exodous if there is
    target=get_position(lista1,'E') #I make the coords of exodous the target 
    
    path1=find_path1(lista1, start, target, '.') #I take the path to the target
    return path1 # Return the path !!!VICTORY
  else: 
    if path: #if there is a global path
      lista1=paste_part1(lista1,maze) #first i update the lista1 with data from maze 
      maze=paste_part2(maze,lista1) #Then i paste updated lista1 to maze 
      start=get_position(maze,'P')
      path=find_path1(maze, start, find_unknown_target(maze), '.')# I find a path in maze '?' with '.' neighbor
      return path[:-2] #I return the path cutted of 2 positions (to the shortest angle or cross)
    else: # if there is no global path
      maze=paste_part(maze,lista1,*center) #i paste lista1 to the middle of maze
      start=get_position(maze,'P')
      path=find_path1(maze, start, find_unknown_target(maze), '.') #I create the first path
      return path[:-2] #return it as above

Συνολικά είναι 190 γραμμές κώδικα 

κάπου με τις ανανεώσεις των πινάκων έχω λάθος (για αυτό κοπανάω στον τοίχο)

 

Το σπαστικό είναι όταν βλέπεις τις λύσεις και βλέπεις ότι κάποιος το έλυσε με 10-20 γραμμές

Επεξ/σία 6 Δεκεμβρίου 2016 από k33theod

[kaliakman]

Εγώ ακόμα δεν έχω καταλάβει τι παραπάνω έχει από έναν απλό λαβύρινθο πέρα του ότι δεν ξέρεις από την αρχή τι γίνεται.

 

Δες εδώ μήπως σε βοηθήσει:

https://www.cs.bu.edu/teaching/alg/maze/

 

και αν θες να σου δείξω και την επαναληπτική λύση αυτού του προβλήματος.

[k33theod]

θα προσπαθήσω να εξηγήσω 

 

γράφεις το πρόγραμμα σου που επιστρέφει ένα string πχ 'NEEEESW' 

Αυτό το string εκτελείται και μετακινεί την θέση του παίκτη την 'P' δηλαδή 

 

από την νέα θέση το πρόγραμμα ξανατρέχει στο νεό όμως λαβύρινθο που βλέπει ο φακός εάν βλέπει άλλο κομμάτι και παράγει ένα νεό path πχ 'ΕΕΕΕ'

θα πρέπει να έχεις βγει  πριν το άθροισμα από το length των path να υπερβεί το 250 

 

εξηγώ και τον τρόπο που εγώ προσπαθώ να το λύσω με τον κώδικά παραπάνω

 

Το πρώτο πράγμα που κάνω κάθε φορά είναι να ψάχνω για την έξοδο 'E' αν υπάρχει τρέχω τον path_finder και εφόσον έχω ακόμα κινήσεις βγαίνω και τελειώνει

εάν δεν υπάρχει πηγαίνω σε ένα σημείο που θα μου παράγει καινούγιο κομμάτι του λαβύρινθου τέτοια σημεία είναι διασταυρώσεις ή γωνίες.

Τις πληροφορίες κάθε κομματιού τις βάζω σε ένα πίνακα global τον οποίο αναννεώνω κάθε φορά ώστε να μήν ξαναγυρνάω στα ίδια σημεία

Σαν να έχω ένα μεγάλλο κομμάτι χαρτί και να σχεδιάζω ότι βλέπω .

Σίγουρα υπάρχουν και άλλες λύσεις έτσι το σκέφτηκα εγώ.

 

path_finder έχω γράψει ένα δικό μου δεν έχει πολύ σχέση με το link σου τον αλγόριθμο το είδα σε ένα site που δεν θυμάμαι τώρα,

[hh12]

Εγώ το προσπαθώ με άλλο σκεπτικό αλλά ακόμα δεν το έλυσα

BAM! You in the wall at 5, 6.

 

στο 2ο τεστ που σημαίνει μάλλον ότι έναν λαβύρινθο τον πέρασα

H main μου είναι αυτή

def find_path(visible):#main function
  global maze
  global path
  center=[15,15]
  lista1=make_list(visible)#I conver the tuple of stings into a list
  start=get_position(lista1,'P')#I get coords of player
  if get_position(lista1,'E'): # Looking for Exodous if there is
    target=get_position(lista1,'E') #I make the coords of exodous the target 
    
    path1=find_path1(lista1, start, target, '.') #I take the path to the target
    return path1 # Return the path !!!VICTORY
  else: 
    if path: #if there is a global path
      lista1=paste_part1(lista1,maze) #first i update the lista1 with data from maze 
      maze=paste_part2(maze,lista1) #Then i paste updated lista1 to maze 
      start=get_position(maze,'P')
      path=find_path1(maze, start, find_unknown_target(maze), '.')# I find a path in maze '?' with '.' neighbor
      return path[:-2] #I return the path cutted of 2 positions (to the shortest angle or cross)
    else: # if there is no global path
      maze=paste_part(maze,lista1,*center) #i paste lista1 to the middle of maze
      start=get_position(maze,'P')
      path=find_path1(maze, start, find_unknown_target(maze), '.') #I create the first path
      return path[:-2] #return it as above

Συνολικά είναι 190 γραμμές κώδικα 

κάπου με τις ανανεώσεις των πινάκων έχω λάθος (για αυτό κοπανάω στον τοίχο)

 

Το σπαστικό είναι όταν βλέπεις τις λύσεις και βλέπεις ότι κάποιος το έλυσε με 10-20 γραμμές

 

Σε 20 γραμμες νομιζω πως το μονο που μπορεις να κανεις ειναι μια αναδρομικη bruteforce.

 

Εγω εχω σκεφτει καθε φορα που ειναι σε καποια θεση και εχει να επιλεξει σε πιο σημειο του οριζοντα να κατευθυνθει, να ψαχνει ποσες επιλογες-διασταυρωσεις εχει το καθε σημειο. Υστερα να πηγαινει σε αυτο με τις περισσοτερες και τα υπολοιπα να τα βαζει σε μια λιστα (η οποια θα λειτουργησει στη συνεχεια σαν στιβα) και να την κατατασει σε φθηνουσα σειρα. Αμα δε βρει το δρομο και γυρισει πισω θα κατευθυνθει στη κατευθυνση του επομενου στοιχειου της στοιβας. Αυτη η λιστα-στιβα θα ειναι μεσα σε μια αλλη λιστα-στιβα. Αυτη θα περιλαμβανει για καθε σημειο μια λιστα-στιβα η οποια θα περιεχει τις δυνατες επιλογες. Δεν ξερω αν εγινα κατανοητος

[k33theod]

Σε 20 γραμμες νομιζω πως το μονο που μπορεις να κανεις ειναι μια αναδρομικη bruteforce.

 

 

Μην το λες αυτό υπάρχουν κάποιοι που λύνουν προβλήματα αλλιώς 

Στον ανοιχτό λαβύρινθο έγώ είχα 50+ γραμμές κώδικα με ένα κομμάτι που πήρα έτοιμο από ένα βιβλίο αλλιώς πήγαινα 70

κοίτα τι έγραψαν άλλοι ούτε 20 γραμμές

import random
def checkio(m):
    x = 1
    y = 1
    a=''
    while (x!=10 or y!=10):
        q=random.randrange(1,5,1)
        if q==1 and m[x][y+1]==0:
            a+='E'
            y+=1
        if q==2 and m[x+1][y]==0:
            a+='S'
            x+=1
        if q==3 and m[x][y-1]==0:
            a+='W'
            y-=1
        if q==4 and m[x-1][y]==0:
            a+='N'
            x-=1
    return(a)

[kaliakman]

Και αυτό λύνει τι? Εγώ βλέπω ότι ξεκινάνε πάντα από το (1,1) και τελειώνουν πάντα άμα φτάσουν στο (10,10).

Άμα είναι να βγάζει μονοπατι όλο το λαβύρινθο και να τελειώνει μετά απο πολλή ωρα...

[k33theod]

Ναι και εγώ αυτό αναρωτιέμαι όταν βλέπω τον κώδικά μερικών

 

Το παραπάνω σε βγάζει από ένα λαβύρινθο που το start είναι στο 1,1  και το target στο 10,10

M='ADFGVX'
def g(k,m):
    k=sorted(set(k),key=k.index)
    yield from[j for i in sorted(range(len(k)),key=k.__getitem__)for j in range(i,len(m),len(k))]
def encode(m,s,k):
    x=[M[i]for c in m.lower()if c.isalpha()or c.isdigit()for i in divmod(s.index(c),6)]
    return ''.join(x[i]for i in g(k,x))
def decode(m,s,k):
    x=list(m)
    for i,c in zip(g(k,m),m)[i]=c
    return ''.join(s[6*M.index(x[i])+M.index(x[i+1])]for i in range(0,len(m),2))
​

To παραπάνω κάνει κρυπτογράφηση και αποκρυπτογράφηση

σε αυτό το πρόβλημα https://py.checkio.org/mission/adfgvx-cipher/

που εγώ έγραψα 150 γραμμές

Οπότε ότι κάποιος έχει λύσει το dark labyrinth με 20 ή λιγότερες γραμμές είναι πολύ πιθανό 

[kaliakman]

Αυτός δεν είναι κώδικας. Και εγώ μπορώ να γράψω one liner σε C και να μην καταλαβαίνει κανείς τι γίνεται. Το θέμα είναι ο κώδικας να διαβάζεται και όχι να θέλει αποκρυπτογραφηση.

 

Επίσης στο προηγούμενο μπορεί να το λύνει αλλά είναι πολύ ειδικό γιατί ας πούμε αν βάλεις έναν που να μην έχει μονοπατι, πάει.

Επίσης εκτυπωνει και τα βήματα του backtracking..

Δεν ξέρω τι ζητάει η άσκηση αλλά συνήθως εκτυπωνεις μόνο το μονοπατι.

[k33theod]

Αυτός δεν είναι κώδικας. Και εγώ μπορώ να γράψω one liner σε C και να μην καταλαβαίνει κανείς τι γίνεται. Το θέμα είναι ο κώδικας να διαβάζεται και όχι να θέλει αποκρυπτογραφηση.

 

Επίσης στο προηγούμενο μπορεί να το λύνει αλλά είναι πολύ ειδικό γιατί ας πούμε αν βάλεις έναν που να μην έχει μονοπατι, πάει.

Επίσης εκτυπωνει και τα βήματα του backtracking..

Δεν ξέρω τι ζητάει η άσκηση αλλά συνήθως εκτυπωνεις μόνο το μονοπατι.

https://py.checkio.org/mission/open-labyrinth/

Δεν έχει σχέση όπως το συνδέεις με σωστό κώδικα, είναι παιχνίδι για τριβή με τη γλώσσα αν σου αρέσει να λύνεις και προβλήματα. Γράφεις ότι θέλεις αρκεί να περνάει τα τεστ.

Το συγκεκριμένο είναι στην πρώτο στην κατηγορία creative solutions με 77 ψήφους ανάμεσα σε 2100 λύσεις. 

Οι κριτές δεν ήταν τόσο αυστηροί σαν εσένα 

[kaliakman]

https://py.checkio.org/mission/open-labyrinth/

Δεν έχει σχέση όπως το συνδέεις με σωστό κώδικα, είναι παιχνίδι για τριβή με τη γλώσσα αν σου αρέσει να λύνεις και προβλήματα. Γράφεις ότι θέλεις αρκεί να περνάει τα τεστ.

Το συγκεκριμένο είναι στην πρώτο στην κατηγορία creative solutions με 77 ψήφους ανάμεσα σε 2100 λύσεις. 

Οι κριτές δεν ήταν τόσο αυστηροί σαν εσένα 

Αυτά που είπα ήταν για το αλλό που έδειξες. Ο αλγόριθμος του λαβυρίνθου είναι πολύ καλός για το συγκεκριμένο πρόβλημα!

[hh12]

https://py.checkio.org/mission/open-labyrinth/

Δεν έχει σχέση όπως το συνδέεις με σωστό κώδικα, είναι παιχνίδι για τριβή με τη γλώσσα αν σου αρέσει να λύνεις και προβλήματα. Γράφεις ότι θέλεις αρκεί να περνάει τα τεστ.

Το συγκεκριμένο είναι στην πρώτο στην κατηγορία creative solutions με 77 ψήφους ανάμεσα σε 2100 λύσεις. 

Οι κριτές δεν ήταν τόσο αυστηροί σαν εσένα 

 

Creative μπορει να ειναι ομως δεν ειναι ο πιο γρηγορος