Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α22.15 · Zoomba: συντομότερη διαδρομή σε δωμάτιο

Εργασία 3 (2023-24), Άσκηση 1 · Δυσκολία ★★★ · programming · Κεφάλαια: 22, 13, 12

Η Εργασία 3 είναι προαιρετικά ομαδική (ομάδες μέχρι 2 άτομα) και κάθε repository πρέπει να έχει ένα αρχείο AUTHORS με μία γραμμή για κάθε άτομο (sdi, GitHub username, όνομα).

Οι ρομποτικές σκούπες Roomba κάνουν τυχαίες βόλτες στον χώρο αντί να πάνε κατευθείαν στο σημείο που χρειάζεται καθάρισμα, με αποτέλεσμα να κολλάνε (Σχήμα 1 της εκφώνησης) ή να αδειάζει η μπαταρία τους. Η δική μας ρομποτική σκούπα, η Zoomba, διαθέτει ραντάρ που σκανάρει το δωμάτιο, δημιουργεί τον “χάρτη” του και εντοπίζει το σημείο που χρειάζεται επειγόντως καθαρισμό. Αυτό που μας λείπει είναι ένα υποσύστημα που παίρνει τον χάρτη του δωματίου και το σημείο-στόχο καθαρισμού και επιστρέφει τις κινήσεις που πρέπει να ακολουθήσει η Zoomba μας. Η γραφή αυτού του υποσυστήματος είναι το ζητούμενο αυτής της άσκησης.

Τεχνικές Προδιαγραφές

• Repository Name: progintro/hw3-<YourTeamName>
• README Filepath: zoomba/README.md
• C Filepath: zoomba/src/zoomba.c

• Το πρόγραμμα θα πρέπει να δέχεται από την πρότυπη είσοδο (stdin) τα δεδομένα του δωματίου στο οποίο βρίσκεται. Συγκεκριμένα, η είσοδος θα έχει την ακόλουθη γενική μορφή:

  ROOM_DIMENSION_N
  ZOOMBA_X ZOOMBA_Y ZOOMBA_TARGET_X ZOOMBA_TARGET_Y
  ROOM_ENCODED_AS_1s_AND_0s
  

  Η πρώτη γραμμή θα περιέχει την διάσταση του τρέχοντος δωματίου ως ακέραιο (μόνο τετράγωνα δωμάτια είναι δεκτά για το πρωτότυπό μας), την τρέχουσα θέση της zoomba σε καρτεσιανές συντεταγμένες (ακέραιοι), την θέση στόχο την οποία πρέπει να καθαρίσει σε καρτεσιανές συντεταγμένες (ακέραιοι) και τέλος τον χάρτη του τρέχοντος δωματίου κωδικοποιημένο ως 1 και 0 - όπου 1 δηλώνει την παρουσία κάποιου εμποδίου ενώ 0 δηλώνει ανοιχτό χώρο. Οποιαδήποτε είσοδος δεν ακολουθεί την παραπάνω μορφή θα πρέπει να κάνει το πρόγραμμα να τερματίζει με κωδικό εξόδου (exit code) 1. Ομοίως και αν οι συντεταγμένες που δόθηκαν είναι λανθασμένες - για παράδειγμα αν η θέση της zoomba ή του στόχου είναι πάνω σε εμπόδιο - το πρόγραμμα πρέπει να τερματίζει με κωδικό εξόδου

  1. Για παράδειγμα, μια πιθανή είσοδος είναι η ακόλουθη - μπορείτε να την συγκρίνετε με την απεικόνιση στο Σχήμα 2:

  10
  1 8 8 1
  0000000000
  0110000000
  0110000000
  0100000000
  0110000000
  0111111100
  0000000000
  0000000000
  0000001110
  0000000000
  

  Το Σχήμα 2 της εκφώνησης δείχνει τον χάρτη ως πλέγμα 10 × 10 με τα εμπόδια, την αρχική θέση της Zoomba (ένα γρανάζι, πάνω δεξιά) και την περιοχή που χρειάζεται καθάρισμα (κόκκινο X, κάτω αριστερά). Μια από τις λύσεις που θέλουμε να επιλέξει η Zoomba αποτελείται από 14 βήματα: DDDDDDLLLLLLLD. Παρατηρήστε ότι υπάρχουν πάνω από μία βέλτιστες λύσεις.

• Στην έξοδό του το πρόγραμμά σας πρέπει να τυπώνει τις κινήσεις που πρέπει να πραγματοποιήσει η zoomba προκειμένου να φτάσει στον στόχο στην πρότυπη έξοδο (stdout). Για εξοικονόμηση υλικών, η zoomba μας μπορεί να κινηθεί μόνο πάνω (U - Up), κάτω (D - Down), αριστερά (L - Left) και δεξιά (R - Right) οπότε όλες οι λύσεις πρέπει να εκφραστούν με αυτούς τους τέσσερις χαρακτήρες. Η λύση πρέπει να είναι η συντομότερη δυνατή σε αριθμό κινήσεων της zoomba (θεωρούμε ότι όλες οι κινήσεις έχουν το ίδιο ενεργειακό κόστος). Για παράδειγμα, η λύση που εικονίζεται στο Σχήμα 2 θα έχει την ακόλουθη μορφή:

  DDDDDDLLLLLLLD
  

  Παρατηρήστε ότι είναι η βέλτιστη από απόψεως αριθμού κινήσεων - φτάνει στον στόχο μόλις σε 14 βήματα. Αφού τυπώσει την λύση, το πρόγραμμα πρέπει να τερματίζει με κωδικό εξόδου (exit code) 0. Εάν δεν υπάρχει καμία λύση επειδή η θέση δεν είναι προσβάσιμη, το πρόγραμμά μας πρέπει να τυπώνει “0” και πάλι να τερματίζει με κωδικό εξόδου 0.

• Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr): gcc -Ofast -Wall -Wextra -Werror -pedantic -o zoomba zoomba.c -lm
• Ένα αρχείο που να περιέχει στοιχεία εισόδου και ένα εξόδου διαφορετικά από αυτά της άσκησης. Συγκεκριμένα προτείνουμε να βάλετε έναν συνδυασμό που θεωρείται ότι είναι δύσκολος να γίνει σωστός.
  • input Filepath: zoomba/test/input
  • output Filepath: zoomba/test/output
• Μέγιστη διάσταση δωματίου: 10000.
• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 30 δευτερόλεπτα.

Παρακάτω παραθέτουμε την αλληλεπίδραση με μια ενδεικτική λύση:

$ echo | ./zoomba
Incorrect room input provided.
$ echo $?
1
$ cat impossible
10
1 8 8 1
0100000000
0110000000
0110000000
0100000000
0110000000
0111111111
0000000000
0000000000
0000001110
0000000000
$ ./zoomba < impossible
0
$ echo $?
0
$ cat input
10
1 8 8 1
0000000000
0110000000
0110000000
0100000000
0110000000
0111111100
0000000000
0000000000
0000001110
0000000000
$ ./zoomba < input
DDDDDDLLLLDLLL

Παρατηρήστε ότι η λύση είναι διαφορετική απ’ ό,τι εικονίζεται στο Σχήμα 2 αλλά παρόλα αυτά είναι σωστή και μία από τις βέλτιστες. Παρακάτω παραθέτουμε μερικά ακόμα παραδείγματα. Φυσικά καλό είναι να δοκιμάσετε και εσείς το πρόγραμμά σας με διάφορα δωμάτια που είναι εντός προδιαγραφών ώστε να ελέγξετε την ορθότητα και την αποδοτικότητα της λύσης σας.

$ cat maze
10
1 8 8 1
1111111101
0000000101
0111110101
0001000101
1101011101
0001010001
0111010111
0101010101
0001010101
0001000001
$ ./zoomba < maze
DDDDLLDDDDLLUUUUUURRUULLLLLLDDRRDDLLDDDR

Στον φάκελο https://github.com/progintro/data/tree/main/zoomba μπορείτε να βρείτε και μεγαλύτερα παραδείγματα (τα μεγαλύτερα είναι συμπιεσμένα για λόγους χώρου, μπορείτε να τα αποσυμπιέσετε χρησιμοποιώντας την εντολή tar). Μερικές ενδεικτικές εκτελέσεις ακολουθούν (έχουμε “κόψει” το output για λόγους χώρου):

$ time ./zoomba < tricky1000
UUUUUUU...UUUUUUUUULUURRRRR...RRRRRRRRRRRR

real    0m0.197s
user    0m0.145s
sys     0m0.052s
$ time ./zoomba < impossible1000
0

real    0m0.155s
user    0m0.121s
sys     0m0.034s

time ./zoomba < maze100
DDDDLLL...DDLLDDD

real    0m0.003s
user    0m0.003s
sys     0m0.000s
$ ./zoomba < maze100 | wc -c
2472
$ ./zoomba < maze100 | md5sum -
5b2b80b22c12408e82e10b2bbb625c48
$ ./zoomba < guernica10000 | wc -c
19173
$ time ./zoomba < guernica10000 | md5sum -
873bb6d49f1d6a6e36dc261cf3d79788  -

real    0m11.406s
user    0m10.233s
sys     0m1.176s

Προκειμένου να βελτιστοποιήσετε την λύση σας ίσως χρειαστεί (όχι αναγκαστικά!) να εμβαθύνετε σε θέματα αναζήτησης πέρα από αυτά που συζητήσαμε στο μάθημα - οι ενότητες 2-4 της Τεχνητής Νοημοσύνης της σχολής είναι ένα παράδειγμα από πηγές που μπορούν να σας βοηθήσουν σε αυτήν την κατεύθυνση.

Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης. Για τις υποβολές με την καλύτερη χρονική απόδοση θα υπάρχει bonus βαθμολογία: η πρώτη υποβολή θα λάβει +100%, η δεύτερη +70% και η τρίτη +40%.

Υπόδειξη

Το δωμάτιο είναι ένας γράφος με κόμβους τα ελεύθερα κελιά και ακμές τις τέσσερις κινήσεις· η συντομότερη διαδρομή σε γράφο χωρίς βάρη βρίσκεται με αναζήτηση κατά πλάτος (BFS) με ουρά, αποθηκεύοντας για κάθε κελί από πού ήρθατε ώστε να ανακατασκευάσετε τη διαδρομή στο τέλος (ανάποδα). Για N = 10000 ο χάρτης έχει 10^8 κελιά: δεσμεύστε δυναμικά συμπαγείς πίνακες (π.χ. ένα byte ανά κελί) και αποφύγετε την αναδρομή, που θα γέμιζε τη στοίβα. Από το παράδειγμα του Σχήματος 2 βγάλτε ποια συντεταγμένη είναι η γραμμή και ποια η στήλη, και ελέγξτε προσεκτικά κάθε παράβαση της μορφής εισόδου.

Αριθμός στον οδηγό: Α22.15 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: hw-2023-hw3-zoomba · Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2023-hw3-zoomba.html · Markdown (GitHub)