Σανίκα

[Χουργιατς]

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

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

Η οργισμένη που την έβαλαν να δουλέψει Σανίκα λοιπόν, σας δίνει ένα λαπτοπάκι με έναν φάκελο ανοικτό. Ο φάκελος περιέχει 251 αρχεία με ονόματα ό,τι νάναι, μα γραμμένα στην ίδια γλώσσα προγραμματισμού της αρεσκείας σας. Τα 250 αρχεία περιέχουν κώδικες οι οποίο εκτελούν μια ορισμένη δουλίτσα, η οποία δε μας νοιάζει τι είναι. Μας νοιάζει όμως να βρούμε τα πέντε αρχεία τα οποία εκτελούν τη δουλειά γρηγορότερα. Προς αυτό, το 251ο αρχείο με το όνομα yolo.extension, είναι ένα πρόγραμμα το οποίο δέχεται πέντε αρχεία ως είσοδο, και επιστρέφει τα ονόματα τους διατεταγμένα από το γρηγορότερο στο πιο αργό. Για παράδειγμα, αν τα αρχεία είναι τα file1.extension, file2.extension,...,file5.extension τότε η κλήση της yolo έχει τη μορφή

yolo(file1,file2,....,file5)

και η επιστροφή της είναι για παράδειγμα [file4,file3,file1,file2,file5], όπου το γρηγορότερο αρχείο για τη δουλειά είναι το file4 και το πιο αργό το file5.

Τo ερώτημα για εσάς είναι το εξής. Ποσες φορές θα πρέπει να τρέξουμε τη yolo ώστε να βρούμε τα πέντε γρηγορότερα αρχεία;
Ως μπονους, η Σανίκα ζητά να βρείτε και ποιά είναι αυτά, με χρήση κώδικα.
Έχετε δικαίωμα να μετονομάσετε όλα τα αρχεία του φακέλου, αν αυτό βοηθά (που δεν θα έπρεπε), αλλά θα πρέπει να το κάνετε μέσω της γλώσσας της αρεσκείας σας.


Αν επιτύχετε, θα έχετε την ευτυχία να ακούσετε τη Σανίκα να σας ανακοινώνει πως θα επικοινωνήσουν αυτοί μαζί σας.
Καλή επιτυχία!

[Nameless Ghoul]

Σπάμε το σύνολο αρχείων σε πεντάδες. 250/5 = 50. Τρέχουμε την yolo 50 φορές και έχουμε 50 ονόματα αρχείων με κώδικα αρχείων που είναι πιο γρήγορα από όλα τα υπόλοιπα.

Σπάμε την 50αδα σε 10 πεντάδες και επαναλαμβάνουμε ομοιοτρόπως. Έτσι, έχουμε, σε κάθε πέρασμα, τον ακόλουθο αριθμό εκτελέσεων της yolo:

50
10
2
1

Σύνολο 63 φορές θα τρέξουμε τη yolo, μέχρι στιγμής.

Δεν τελειώσαμε όμως. Έτσι βρήκαμε τον γρηγορότερο κώδικα. Το ζητούμενο είναι να βρούμε τους πέντε γρηγορότερους.

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

2 (επί 9 αρχείων)
1 (επί 2 αρχείων) -> βρήκαμε το δεύτερο γρηγορότερο. Το αφαιρούμε από την 9-αδα, και πάμε:
2 (επί 8 αρχείων)
1 (επί 2 αρχείων) -> βρήκαμε το τρίτο. Το αφαιρούμε από την 8-αδα, και πάμε:
2 (επί 7 αρχείων)
1 (επί 2 αρχείων) -> βρήκαμε το τέταρτο. Το αφαιρούμε από την 7-άδα και πάμε:
2 (επί 6 αρχείων)
1 (επί 2 αρχείων) -> βρήκαμε το πέμπτο, τελειώσαμε.

Η δεύτερη φάση είχε 12 εκτελέσεις.

Σύνολο: 75 εκτελέσεις.

Θα κάτσω να γράψω τον κώδικα αργότερα, γιατί πρέπει να ξαναρχίσω δουλειά. Η πρώτη φάση είναι μια χούφτα γραμμές, γίνεται αναδρομικά. Η δεύτερη είναι ένα επίσης μικρό loop.

[Yochanan]

Σπάμε το σύνολο αρχείων σε πεντάδες. 250/5 = 50. Τρέχουμε την yolo 50 φορές και έχουμε 50 ονόματα αρχείων με κώδικα αρχείων που είναι πιο γρήγορα από όλα τα υπόλοιπα.

ΝG, αυτό είναι σίγουρο; Δλδ δε γίνεται να εχεις φαση που παιρνεις (τυχαια) μια 5αδα απο πχ 5 πολυ αργα και ενταξει βρηκες το πιο γρηγορο τους αλλα αυτο παλι ειναι πολυ αργο σε σχεση με το μ.ο.;

[Yochanan]

Με τον τρόπο που υπέδειξε ο NG νομίζω θα χρειαζόταν να τρέξεις 315 φορές (δλδ τις 63 που εξήγησε χ 5).

[shrike]

Με τον τρόπο που υπέδειξε ο NG νομίζω θα χρειαζόταν να τρέξεις 315 φορές (δλδ τις 63 που εξήγησε χ 5).

Αυτό σκέφτηκα κι εγώ. Με τον τρόπο που προτείνει, στις πρώτες 50 φορές που το τρέχει θα πάρει τα 50 αρχεία που είναι πιο γρήγορα σε σχέση με τις πεντάδες τους, όχι τα 50 πιο γρήγορα γενικά. Μπορεί (ακραίο παράδειγμα, αλλά γιατί όχι;) η πρώτη πεντάδα να έχει τα 5 πιο γρήγορα αρχεία γενικά, αλλά με την διαδικασία αυτή θα πάρει μόνο το γρηγορότερο απ' αυτά, να το συγκρίνει με τα υπόλοιπα και θα ξεσκαρτάρει τα επόμενα 4 γρηγορότερα.

[Spearman]

Τo ερώτημα για εσάς είναι το εξής. Ποσες φορές θα πρέπει να τρέξουμε τη yolo ώστε να βρούμε τα πέντε γρηγορότερα αρχεία;

63 άμα είσαι τέρμα κωλόφαρδος (βρήκες τα πέντε γρηγορότερα με την πρώτη) κ 125 αν είσαι τέρμα γκαντέμης (η γρηγορότερη πεντάδα περιέχει το τελευταίο που εξετάζεις) . Οι περισσότεροι κάπου ενδιάμεσα. Τουλάχιστον έτσι λέει ο αλγόριθμος που σκέφτηκα τώρα :-).

[Nameless Ghoul]

Σπάμε το σύνολο αρχείων σε πεντάδες. 250/5 = 50. Τρέχουμε την yolo 50 φορές και έχουμε 50 ονόματα αρχείων με κώδικα αρχείων που είναι πιο γρήγορα από όλα τα υπόλοιπα.

ΝG, αυτό είναι σίγουρο; Δλδ δε γίνεται να εχεις φαση που παιρνεις (τυχαια) μια 5αδα απο πχ 5 πολυ αργα και ενταξει βρηκες το πιο γρηγορο τους αλλα αυτο παλι ειναι πολυ αργο σε σχεση με το μ.ο.;

Μάλλον δεν το διατύπωσα σωστά.

Κάθε φορά που παίρνεις μια τυχαία πεντάδα, ναι, το πιο γρήγορο της πεντάδας μπορεί να είναι πιο αργό από το μ.ο., αλλά αυτό δεν είναι πρόβλημα, θα απορριφθεί σε επόμενο γύρο. Σημασία έχει οτι κανένα από τα άλλα 4 δεν είναι ταχύτερο, άρα αποκλείεται να είναι στην τοπ 5-αδα. Γι'αυτό τα τέσσερα από τα 5 μπορείς να τα απορρίψεις.

[Nameless Ghoul]

Πιο συγκεκριμένα: Στις 50 πεντάδες του πρώτου γύρου, ένας από τους νικητές είναι ο ταχύτερος όλων. Δεν ξέρουμε ποιος ακόμα, γιαυτό παίρνουμε τους 50 νικητές και τους υποβάλουμε σε 20 γύρο, κ.ο.κ.

[Yochanan]

Δε διαφωνω καθολου οτι με τον τροπο που είπες θα βρισκεις παντα το ταχυτερο με 63 τρεξιματα της γιολο. Αυτο που πιστευω ομως ειναι οτι δεν θα βρισκονται και τα υπολοιπα 4 ταχυτερα μεσα στα 10 πρωτα που βρηκες/ Τουλάχιστον οχι παντα και οχι ολα.

[Spiros252]

Τρέχουμε τη yolo με 5 αρχεία τη φορά.
Μετονομαζουμε ταυτόχρονα κάθε αρχείο, με το χρόνο του ως file name.
Έχοντας τρέξει τη yolo 50 φορές βρισκουμε στο φάκελο τα 5 γρηγορότερα με μια ταξινόμηση κατά όνομα αρχείου.

[shrike]

Πιο συγκεκριμένα: Στις 50 πεντάδες του πρώτου γύρου, ένας από τους νικητές είναι ο ταχύτερος όλων. Δεν ξέρουμε ποιος ακόμα, γιαυτό παίρνουμε τους 50 νικητές και τους υποβάλουμε σε 20 γύρο, κ.ο.κ.

Νομίζω ότι κάνεις κάποιο λάθος. Όπως είπα και πιο πάνω, μ' αυτόν τον τρόπο βρίσκεις τους "νικητές" της κάθε πεντάδας και στη συνέχεια ασχολείσαι μ' αυτούς τους 50. Μπορεί τα 4 υπόλοιπα που απορρίπτεις κάθε πεντάδας (και δεν ξανασχολείσαι μαζί τους) να είναι ταχύτερα από κάποια από τα 50 που κρατάς.

Τρέχουμε τη yolo με 5 αρχεία τη φορά.
Μετονομαζουμε ταυτόχρονα κάθε αρχείο, με το χρόνο του ως file name.
Έχοντας τρέξει τη yolo 50 φορές βρισκουμε στο φάκελο τα 5 γρηγορότερα με μια ταξινόμηση κατά όνομα αρχείου.

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

[shrike]

Στην αρχή σκέφτηκα να τρέχει η yolo nested. Το πρόβλημα είναι ότι δεν επιστρέφει κάποιο μοναδικό αποτέλεσμα αλλά είτε κάποιο string με τα ονόματα των αρχείων με κάποιο delimiter ή κάποιο array με τα ονόματα (δεν ξέρω τι επιστρέφει).

Επίσης, ακόμα κι αν υπάρχει τρόπος να δουλέψει αυτό, φαντάζομαι ότι αν κάνεις την yolo nest σε βάθος (πχ) 3, θα μετράει ως 3 + 1 κλήσεις της και όχι σαν μία, άρα δεν κερδίζεις τίποτα.

Έχω την εντύπωση, ότι πρέπει να γίνουν χιλιάδες συγκρίσεις (κάθε αρχείο με όλα τα υπόλοιπα), αλλά θα κάτσω να (συ)σκεφτώ (μετά του εαυτού μου) σε λίγο στο προσωπικό μου παλάτι σκέψης* για κάτι πιο σύνθετο αλλά λιγότερο χρονοβόρο.



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

[Χουργιατς]

63 άμα είσαι τέρμα κωλόφαρδος (βρήκες τα πέντε γρηγορότερα με την πρώτη) κ 125 αν είσαι τέρμα γκαντέμης (η γρηγορότερη πεντάδα περιέχει το τελευταίο που εξετάζεις) . Οι περισσότεροι κάπου ενδιάμεσα. Τουλάχιστον έτσι λέει ο αλγόριθμος που σκέφτηκα τώρα :-).

Πιθανοτικώς σωστό σε βρίσκω μα δεν έχεις τρόπο να ξες ότι πέτυχες με τη μία την γρηγορότερη 5άδα αν δεν τα ψάξεις όλα.



***************************************************************************


Να σταθώ λίγο και στο ποστ...

Τρέχουμε τη yolo με 5 αρχεία τη φορά.
Μετονομαζουμε ταυτόχρονα κάθε αρχείο, με το χρόνο του ως file name.
Έχοντας τρέξει τη yolo 50 φορές βρισκουμε στο φάκελο τα 5 γρηγορότερα με μια ταξινόμηση κατά όνομα αρχείου.

Ναι, με τροποποίηση της γιολο, και με μετονομασία μπορείς κάλλιστα.
- Ένας σκοπός αυτών των προβλημάτων δεν είναι μόνο η λύση μα και η δημιουργικότητα στη χαλάρωση των περιορισμών.
Προσωπικά θα σε προσλάμβανα στο καπάκι αν έδινες απάντηση μόνο τους κώδικες.



Φυσικά, το ερώτημα παραμένει ανοιχτό υπό τους περιορισμούς που έχουν τεθεί.



Ένα σχόλιο για το τέλος.
Οποιαδήποτε ομοιότητα της Σανίκα με υπαρκτούς χαρακτήρες
είναι απολύτως σκόπιμη
και η έμπνευση για το είδος οφείλεται σε προσωπική μου ατυχή συνδιαλλαγή
με την 22χρονη μειονοτική υπεύθυνη προμόσιον
της PTC

Καλησπέρες

[Pillars]

..Ο φάκελος περιέχει 251 αρχεία με ονόματα ό,τι νάναι, μα γραμμένα στην ίδια γλώσσα προγραμματισμού της αρεσκείας σας. Τα 250 αρχεία περιέχουν κώδικες οι οποίο εκτελούν μια ορισμένη δουλίτσα, η οποία δε μας νοιάζει τι είναι. Μας νοιάζει όμως να βρούμε τα πέντε αρχεία τα οποία εκτελούν τη δουλειά γρηγορότερα. Προς αυτό, το 251ο αρχείο με το όνομα yolo.extension, είναι ένα πρόγραμμα το οποίο δέχεται πέντε αρχεία ως είσοδο, και επιστρέφει τα ονόματα τους διατεταγμένα από το γρηγορότερο στο πιο αργό. Για παράδειγμα, αν τα αρχεία είναι τα file1.extension, file2.extension,...,file5.extension τότε η κλήση της yolo έχει τη μορφή

yolo(file1,file2,....,file5)

και η επιστροφή της είναι για παράδειγμα [file4,file3,file1,file2,file5], όπου το γρηγορότερο αρχείο για τη δουλειά είναι το file4 και το πιο αργό το file5.

Τo ερώτημα για εσάς είναι το εξής. Ποσες φορές θα πρέπει να τρέξουμε τη yolo ώστε να βρούμε τα πέντε γρηγορότερα αρχεία;
Ως μπονους, η Σανίκα ζητά να βρείτε και ποιά είναι αυτά, με χρήση κώδικα.
Έχετε δικαίωμα να μετονομάσετε όλα τα αρχεία του φακέλου, αν αυτό βοηθά (που δεν θα έπρεπε), αλλά θα πρέπει να το κάνετε μέσω της γλώσσας της αρεσκείας σας.

Καλή σπαζοκεφαλιά!
Δεν είμαι προγραμματιστής αλλά πρόχειρα για να κάνω την δουλειά μου θα το πάλευα κάπως έτσι...

Αν το τρέξουμε 1+245 έτσι θα μας δώσει μόνο τα 4 καλύτερα
FileRate(5) = yolo (file1,file2,file3,file4,file5)
For i As Integer = 6 To 250
FileRate(5) = yolo (fileRate1,fileRate2,fileRate3,fileRate4,file(i))
Next

Για να πάρω 5 καλύτερα θα είμαι λίγο σπάταλος οπότε πάμε για 1+2x245
FileRate(5) = yolo (file1,file2,file3,file4,file5)
For i As Integer = 6 To 250
xfile=fileRate.n1
fileRate(5) = yolo (fileRate.n2,fileRate.n3,fileRate.n4,fileRate.n5,file(i))
fileRate(5) = yolo (fileRate.n1,fileRate.n2,fileRate.n3,fileRate.n4,xfile)
Next
Είμαι κοντά;

[Nameless Ghoul]

Κύριοι, έχετε δίκιο. Λάθος μου. Επεξεργάζομαι νέα λύση διορθωμένη, θα επανέλθω.