Εισαγωγή
Στο Toyland, τα τρένα είναι πάντα απασχολημένα, μεταφέροντας θησαυρούς σε όλη την πόλη, από γυαλιστερές μπίλιες μέχρι σπάνια τουβλάκια.
Οι ράγες πάνω στις οποίες κινούνται είναι φτιαγμένες από πολύχρωμα κομμάτια σε σχήμα ντόμινο, καθένα σημαδεμένο με δύο αριθμούς.
Για να κινηθούν τα τρένα, τα ντόμινο πρέπει να σχηματίσουν μια τέλεια αλυσίδα όπου τα νούμερα ταιριάζουν.
Σήμερα, μια επείγουσα παράδοση σπάνιων παιχνιδιών περιμένει.
Σου έχουν δώσει ένα σετ κομματιών ράγας για να εξετάσεις.
Αν μπορούν να σχηματίσουν μια συνεχή αλυσίδα, το τρένο θα ξεκινήσει, φέρνοντας χαμόγελα σε όλο το Toyland.
Αν όχι, το σετ θα πεταχτεί και θα δοκιμαστεί ένα άλλο.
Τα παιχνίδια υπολογίζουν σε σένα για να λύσεις αυτό το παζλ.
Θα ενώσουν τα ντόμινο τις ράγες και θα βάλουν το τρένο να κυλήσει, ή θα μείνει το σετ πίσω;
Οδηγίες
Φτιάξε μια αλυσίδα από ντόμινο.
Βρες έναν τρόπο να διατάξεις ένα δεδομένο σύνολο από πέτρες ντόμινο, ώστε να σχηματίσουν μια σωστή αλυσίδα ντόμινο.
Στην αλυσίδα, οι τελείες στο ένα μισό μιας πέτρας πρέπει να ταιριάζουν με τις τελείες στο γειτονικό μισό μιας διπλανής πέτρας.
Επιπλέον, οι τελείες στα μισά των πετρών που δεν έχουν γείτονες (την πρώτη και την τελευταία πέτρα) πρέπει να ταιριάζουν μεταξύ τους.
Για παράδειγμα, με δεδομένες τις πέτρες [2|1], [2|3] και [1|3] θα πρέπει να υπολογίσεις κάτι
σαν [1|2] [2|3] [3|1] ή [3|2] [2|1] [1|3] ή [1|3] [3|2] [2|1] κ.λπ., όπου ο πρώτος και ο τελευταίος αριθμός είναι οι ίδιοι.
Για τις πέτρες [1|2], [4|1] και [2|3] η αλυσίδα που προκύπτει δεν είναι έγκυρη: ο πρώτος και ο τελευταίος αριθμός του [4|1] [1|2] [2|3] δεν είναι οι ίδιοι.
4 != 3
Κάποιες περιπτώσεις δοκιμών μπορεί να χρησιμοποιούν διπλότυπες πέτρες σε μια λύση αλυσίδας· υπόθεσε ότι χρησιμοποιούνται πολλά σετ ντόμινο.
Υλοποίηση
Όρισε μία μόνο συνάρτηση Go, τη MakeChain, η οποία δέχεται ένα slice από ντόμινα και προσπαθεί να κατασκευάσει μια νόμιμη αλυσίδα από ντόμινα.
Η MakeChain πρέπει να έχει την ακόλουθη υπογραφή:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
Το αποτέλεσμα ok τύπου bool δείχνει αν η δεδομένη λίστα από ντόμινα εισόδου μπορεί να τακτοποιηθεί σε μια νόμιμη αλυσίδα.
Μια κενή λίστα εισόδου θεωρείται νόμιμη, και ένα μόνο ντόμινο του οποίου οι πλευρές είναι ίδιες θεωρείται επίσης νόμιμο.
Το αποτέλεσμα "chain" είναι ένα slice από μηδέν ή περισσότερα ντόμινα, τακτοποιημένα σε μια σειρά που δείχνει τη νόμιμη αλυσίδα.
Είναι αποδεκτό (και αναμενόμενο) ότι τα ντόμινα στο "input" μπορεί να χρειαστεί να περιστραφούν, ώστε κάθε πλευρά να ταιριάζει με το γειτονικό της ντόμινο στην αλυσίδα.
Τα ντόμινα στην αρχή και στο τέλος της αλυσίδας πρέπει επίσης να ταιριάζουν μεταξύ τους στην εξωτερική τους πλευρά.
Αν το δεδομένο slice εισόδου από ντόμινα δεν μπορεί να τακτοποιηθεί σε μια νόμιμη αλυσίδα, η MakeChain μπορεί να επιστρέψει nil για το αποτέλεσμα "chain", αλλά πρέπει να επιστρέψει false για το αποτέλεσμα ok.
Επειδή μπορεί να υπάρχουν περισσότερες από μία νόμιμες διατάξεις αλυσίδας για μια δεδομένη λίστα εισόδου, όταν το ok είναι true, το πρόγραμμα δοκιμών θα ελέγξει την αλυσίδα μόνο για εγκυρότητα.
