Αναδρομή

Το Bao Loc είναι μια μικρή πόλη του Βιετνάμ μεταξύ της Ho Chi Minch – πρώην Shaigon – και της Da Lat. Στη wikipedia διαβάζουμε ότι έχει πληθυσμό περίπου 150 χιλιάδες κατοίκους ενώ στο αντίστοιχο λήμμα του wikitravel.org για το Bao Loc θα μάθουμε ότι δεν έχει και πολύ ενδιαφέρον να πάμε ως ταξιδιώτες καθότι το μόνο που μπορούμε να κάνουμε είναι να φάμε, να κοιμηθούμε και να χαρούμε το πάρκο και την λίμνη της πόλης στην οποία οι ντόπιοι συνηθίζουν να ψαρεύουν. Το ενδιαφέρον με το Bao Loc είναι ότι εκεί σύμφωνα με διάφορα δημοσιεύματα (όπως του the guardian) οι οχτάχρονοι μαθητές του (της τρίτης Δημοτικού) κλήθηκαν να λύσουν έναν γρίφο που δυσκολεύει ακόμα και ενήλικες καλούς στα μαθηματικά.

Ακολουθεί ο γρίφος αλλά και η περιγραφή του αλγορίθμου (και κατ’ επέκταση του προγράμματος) που πρέπει να γράψετε για να λύσει ο υπολογιστής τον γρίφο για εσάς.

Πάρκο-Λίμνη του Bao Loc

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

Γρίφος για Οχτάχρονα στο Bao Loc

Το ζητούμενο είναι να συμπληρωθούν όλα τα κενά του παραπάνω «φιδιού» με τους αριθμούς από το 1 έως το 9 (μια φορά ο κάθε ένας). Στο φίδι ισχύει η σειρά των πράξεων. Δηλαδή, μόνο το 13 πολλαπλασιάζεται με το δεύτερο κενό κουτάκι (και όχι το πρώτο κουτάκι συν το 13). Το πρόβλημα είναι αρκετά δύσκολο οπότε καλείστε να γράψετε πρόγραμμα στη ΓΛΩΣΣΑ το οποίο να δημιουργεί όλες τις μεταθέσεις των 9 αριθμών και να τις δοκιμάζει μία-μία μέχρι να βρεθεί η σωστή.

Όσοι θέλετε να το λύσετε με το χέρι σταματήστε να διαβάζετε – ακολουθεί μερική αποκάλυψη της λύσης

Επειδή, οι μεταθέσεις των 9 αριθμών είναι 9!=9·8·7·6·5·4·3·2·1=362880 που είναι πολύ μεγάλος αριθμός και η ΓλωσσοΜάθεια (στην οποία φαντάζομαι και εσείς όπως και εγώ δοκιμάζετε τα προγράμματά σας) βγάζει μήνυμα λάθους «Out of Memory» αν την ζορίσουμε, θα απλοποιήσουμε το πρόβλημα αποκαλύπτοντας μέρος της λύσης. Μία από τις πολλές λύσεις που υπάρχουν (ναι, υπάρχουν πολλές) ξεκινά με τα τρία πρώτα κουτάκια να έχουν τις τιμές 3, 2 και 1 αντίστοιχα. Οπότε, πρέπει στα υπόλοιπα 6 να μπουν οι αριθμοί 4, 5, 6, 7, 8 και 9 (πλέον έχουμε 6!=6·5·4·3·2·1=720 μεταθέσεις όλο κ’ όλο).
Οι μεταθέσεις n αντικειμένων (αριθμών) μπορούν να υπολογισθούν με τον αλγόριθμο Johnson–Trotter (ή για να είμαστε πιο δίκαιοι Steinhaus–Johnson–Trotter) ο οποίος χρησιμοποιεί το τέχνασμα του «κινητού» αντικειμένου. Ένα βέλος υπάρχει για κάθε αντικείμενο και δείχνει την κατεύθυνσή του (αρχικά τα αντικείμενα-αριθμοί είναι ταξινομημένα σε αύξουσα σειρά και όλα έχουν κατεύθυνση αριστερά). Ένα αντικείμενο λέγεται κινητό αν δείχνει σε ένα μικρότερο αντικείμενο (το τέρμα αριστερό αντικείμενο που δείχνει αριστερά δεν είναι ποτέ κινητό, αντίστοιχα και το τέρμα δεξιά). Κατά τα άλλα ο αλγόριθμος έχει ως εξής:
Όσο υπάρχουν κινητά αντικείμενα

Βρες το μεγαλύτερο κινητό αντικείμενο, έστω Κ

Αντιμετάθεσε το Κ με το διπλανό στο οποίο κοιτάει (και τα βελάκια τους)

Αντέστρεψε την κατεύθυνση όλων των αντικειμένων που είναι μεγαλύτερα του Κ

Για να λύσετε τον γρίφο μπορείτε να γράψετε πρόγραμμα στη ΓΛΩΣΣΑ και να το εκτελέσετε μέσω της ΓλωσσοΜάθειας το οποίο να κάνει τα εξής:

1. Να βάζει σε έναν πίνακα ακεραίων 6 θέσεων τους αριθμούς 4, 5, 6, 7, 8 και 9 και σε έναν άλλον πίνακα λογικών τιμών 6 θέσεων την τιμή ΑΛΗΘΗΣ σε όλες τις θέσεις (το ΑΛΗΘΗΣ σημαίνει ότι το αντικείμενο δείχνει αριστερά).
2. Να επαναλαμβάνει την ακόλουθη διαδικασία όσο υπάρχουν κινητά αντικείμενα και δεν έχει βρεθεί λύση στον γρίφο.
   1. Να βρίσκει το μεγαλύτερο κινητό αντικείμενο (έστω Κ) και την θέση του.
   2. Να το αντιμεταθέτει με το διπλανό του στο οποίο δείχνει (αντιμεταθέτοντας και τις κατευθύνσεις τους).
   3. Να αντιστρέφει την κατεύθυνση των αντικειμένων που είναι μεγαλύτερα του Κ.
3. Μετά το τέλος της επαναληπτικής διαδικασίας να εμφανίζει την λύση που βρήκε ή το μήνυμα «ΔΕΝ ΒΡΕΘΗΚΕ ΛΥΣΗ» σε περίπτωση που δεν βρεθεί λύση.

Αν έχετε καταλάβει πώς λειτουργεί ο αλγόριθμος Johnson–Trotter για τον υπολογισμό των μεταθέσεων αντικείμενων δεν θα είναι και τόσο δύσκολο να γράψετε το πρόγραμμα.

Βάλτε το να εκτελείται, φτιάξτε έναν καφέ (εντάξει, μάλλον όχι καφέ, φτιάξτε φυσικό χυμό πορτοκάλι) και ξεκινήστε να φρεσκάρετε την θεωρία της Ανάπτυξης Εφαρμογών σε Προγραμματιστικό Περιβάλλον. Μετά από λίγο (η καθυστέρηση οφείλεται στο ότι η ΓλωσσοΜάθεια χρησιμοποιεί διερμηνευτή – interpreter – και στο ότι προβάλει γραφικά την τρέχουσα εντολή, την κατάσταση της μνήμης κ.ο.κ.) και αν το πρόγραμμά σας είναι σωστό θα έχετε την λύση στον γρίφο για τους οχτάχρονους μαθητές της Bao Loc.

Μπορεί να σας φανεί κοπιαστική και δύσκολη άσκηση αλλά τουλάχιστον έχει νόημα. Θα λύσετε έναν γρίφο μέσω υπολογιστή. Σαν τον Alan Turing και τον γρίφο της μηχανής Enigma.