Το γνωστό (;) ‘Secret Santa’, όπου μία παρέα κάνει μία κλήρωση για το ποιος θα πάρει (μυστικά) δώρο Χριστουγέννων σε ποιον, έχει κάποια προβλήματα όταν γίνεται με τον συνηθισμένο τρόπο, δηλαδή με χαρτάκια σε ένα μπολ όπου ένας-ένας οι παίκτες τραβάνε για να δουν σε ποιον θα πάρουν δώρο.
Τα δύο βασικότερα προβλήματα είναι:
οι πιθανότητες στα αποτελέσματα δεν είναι μοιρασμένες ίσα με αυτόν τον τρόπο (περιγράφει με λεπτομέρειες αυτό το πρόβλημα η Hannah Fry) και
είναι πολύ πιθανό και συνηθισμένο κάποιος από την παρέα να τραβήξει το δικό του όνομα και η διαδικασία να πρέπει να ξεκινήσει από την αρχή, ξανά και ξανά και ξανά…
Σκέφτηκα λοιπόν να φτιάξω ένα προγραμματάκι το οποίο κάνει ανακάτεμα όλης της λίστας και αναθέτει ταυτόχρονα σε όλους τους παίκτες από ένα αποτέλεσμα, ώστε να μοιράζονται οι πιθανότητες σωστά (δεν μειώνεται το pool κάθε φορά που κάποιος παίκτης παίρνει το αποτέλεσμά του). Χρησιμοποιεί επίσης αναδρομή για να εξασφαλίσει ότι δεν θα ανατεθεί σε κάποιον ο εαυτός του.
Χρησιμοποιήσα Qt με C++. Το interface δεν μπορώ να κρίνω αν είναι αρκετά intuitive γιατί εγώ ήδη ξέρω τι έκανα…!
Ευχαριστούμε για το πρόγραμμα. Επέτρεψε μου μερικές παρατηρήσεις. Κατ αρχή συγχαρητήρια για την σωστή χρήση της shuffle. Πίσω κάνει χρήση ενός καλού αλγόριθμου και κατανοείς την ανάγκη χρήσης μιας καλής πηγής εντροπίας.
Αλλά κάνεις ένα σοβαρό λάθος στην αναδρομή. Κάθε αναδρομή πρέπει να έχει μια εμφανή συνθήκη για το πότε τερματίζει. Υπάρχει η θεωρητική περίπτωση (που γίνετε πολύ πρακτική αν έχεις να χειριστείς μερικά εκατομμύρια χρήστες) η αναδρομή ποτέ να μην τερματίσει. Επίσης δεν έχεις καμία εγγύηση πως η καινούργια λύση θα είναι καλύτερη. Μπορεί να έχει έτσι την αλγοριθμική πολυπλοκότητα μιας bogosort (εντάξει υπερβάλω λιγάκι με αυτή την πρόταση).
Μια εναλλακτική υλοποίηση θα ήταν να χρησιμοποιούσες κάτι σαν την set_intersection για να εντοπίσεις τα κοινά στοιχεία. Έτσι θα έχεις έτσι ένα σίγουρα όχι μεγαλύτερο πρόβλημα να λύσεις (και πιθανολογικά σχεδόν σίγουρα μικρότερο) κάτι που μπορεί να γίνει εύκολα αναδρομικά. Ο κώδικά βέβαια θα γίνει έτσι πολύ πιο πολύπλοκος (και δεν μπορείς να τα μεταφέρεις στο τέλος όπως αφελώς έγραψα στην πρώτη έκδοση αυτού). Αν το υλοποιούσα μάλλον θα υλοποιούσα έτσι ώστε να απέφευγα από την αρχή το πρόβλημα.
Ξέρω διυλίζω τον κώνωπα με τα παραπάνω . Σε ευχαριστώ που μου έδωσες ένα δύσκολο πρόβλημα να σκεφτώ και καλές γιορτές.
. Σε ευχαριστώ που μου έδωσες ένα δύσκολο πρόβλημα να σκεφτώ και καλές γιορτές.