Coding Challenge

[Επισκέπτης]

Υπάρχει κάποιος που να έχει υλοποιήσει το παρακάτω πρόβλημα σε κώδικα ?

 

An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king’s wine.

Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle.

Unfortunately, they do not know which one. To make matters worse, the poison the spy used was very deadly; just one drop diluted even a billion to one will still kill someone.

Even so, the poison works slowly; it takes a full month for one person to die.

Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expanding at most O(log n) of his taste testers.

[albNik]

Λιγοτερο απο Ο(logn). Μονο ενας tester χρειάζεται Ο(1) να δοκιμασει ολα τα κρασια.

Ας πουμε καθε λεπτο δοκιμάζει απο 1 μπουκάλι  8:01, 8:02, 8:03 ... 

Οταν πεθανει μετα απο 30 μερες κοιταμε την ωρα  π.χ. στις 8:55 ξέρουμε οτι ήταν το μπουκαλι νούμερο 55. 

[GReaperEx]

10 ώρες πριν, albNik είπε

Λιγοτερο απο Ο(logn). Μονο ενας tester χρειάζεται Ο(1) να δοκιμασει ολα τα κρασια.

Ας πουμε καθε λεπτο δοκιμάζει απο 1 μπουκάλι  8:01, 8:02, 8:03 ... 

Οταν πεθανει μετα απο 30 μερες κοιταμε την ωρα  π.χ. στις 8:55 ξέρουμε οτι ήταν το μπουκαλι νούμερο 55. 

Λέει "a full month", όχι "30 days exactly". Το spec είναι πολύ γενικό για να υποθέσεις τόσο μεγάλη ακρίβεια.

Μια "ρεαλιστική" λύση θα ήταν να εκμεταλλευτούμε τον παλιό, καλό μας φίλο: την δυαδική αριθμητική.

Έστω Ν μπουκάλια κρασί. Αν κάθε τέστερ έχει τον δικό του αριθμό Μ, τότε πρέπει να δοκιμάζει τα μπουκάλια με αριθμούς "n" όπου ((n / 2^{⌈log(N)-M⌉}) % 2 == 0). Μετά από ένα μήνα, αν υποθέσουμε ότι t_M είναι η ακολουθία της κατάστασης όλων των τέστερ και "νεκρός"=1, "ζωντανός"=0, τότε μπορούμε να βρούμε τον αριθμό του δηλητηριασμένου κρασιού με αυτή τη σούμα:

Επεξ/σία 9 Μαρτίου 2020 από GReaperEx

[Επισκέπτης]

8 ώρες πριν, GReaperEx είπε

Λέει "a full month", όχι "30 days exactly". Το spec είναι πολύ γενικό για να υποθέσεις τόσο μεγάλη ακρίβεια.

Μια "ρεαλιστική" λύση θα ήταν να εκμεταλλευτούμε τον παλιό, καλό μας φίλο: την δυαδική αριθμητική.

Έστω Ν μπουκάλια κρασί. Αν κάθε τέστερ έχει τον δικό του αριθμό Μ, τότε πρέπει να δοκιμάζει τα μπουκάλια με αριθμούς "n" όπου ((n / 2^{⌈log(N)-M⌉}) % 2 == 0). Μετά από ένα μήνα, αν υποθέσουμε ότι t_M είναι η ακολουθία της κατάστασης όλων των τέστερ και "νεκρός"=1, "ζωντανός"=0, τότε μπορούμε να βρούμε τον αριθμό του δηλητηριασμένου κρασιού με αυτή τη σούμα:

και εγω αυτο σκεφτηκα αλλα πως θα γινει σε κωδικα ? Εκει κολλαω οχι στο θεωρητικο κομματι. 

[albNik]

Η πιο απλα αν εχεις τη δυαδικη παρασταση σε bits του N και ο καθενας εχει απο ενα bit. Ο καθε τεστερ δοκιμαζει ολα τα μπουκαλια με το δικο του bit 1 (περιπου τα μισα). Στο τελος φτιαχνεις τον αριθμο βαζοντας στην αντίστοιχη θεση το bit 1 σε οσους πεθαναν και 0 στις αλλες.

[Επισκέπτης]

Αν εχουμε 11 μπουκαλια παιρνουμε 

00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000
00001001
00001010
00001011

οποτε για καθε ενα bit θελουμε αλλο taster. 

Το θεμα είναι πως θα γινει αυτο για δυναμικο n σε κωδικα ?

[albNik]

Για 11 (μεχρι 16) θες 4 tasters.

ο πρωτος δοκιμαζει τα 8 μπουκαλια οπου το πρωτο bit ειναι παντα on 1000, 1001, 1010,1011, 1100,1101,1110 ,1111,

ο δευτερος τα 8 οπου το δευτερο bit ειναι on 0100, 0101,0110,0111, 1100,1101,1110,1111,  

Οσοι πεθανουν σχηματίζεις τον αριθμο

 

[GReaperEx]

43 λεπτά πριν, Kugashira είπε

Το θεμα είναι πως θα γινει αυτο για δυναμικο n σε κωδικα ?

Με δυαδικά AND, OR, NOT και ολισθήσεις. Για παράδειγμα, στη C++ θα ήταν:

poison = 0;

// Για τη δοκιμή
if (n & (1 << i)) {
    taste(i, n);
}

// Για το αποτέλεσμα
if (dead(i)) {
    poison |= 1 << i;
}

 

Επεξ/σία 9 Μαρτίου 2020 από GReaperEx

[Επισκέπτης]

Ορίστε και μια (ελεεινή και τρισάθλια) υλοποίηση σε Python:

 

n = input("How many bottles? ")

tasters = len(format(n,"b"))

dead_tasters = [str(input("Is taster {} dead (press 1 for yes, 0 for no)? ".format(taster))) for taster in range(tasters)]

print("The poisoned bottle is number {}".format(int("".join(dead_tasters), 2)))

 

[Επισκέπτης]

24 λεπτά πριν, GReaperEx είπε

Με δυαδικά AND, OR, NOT και ολισθήσεις. Για παράδειγμα, στη C++ θα ήταν:

poison = 0;

// Για τη δοκιμή
if (n & (1 << i)) {
    taste(i, n);
}

// Για το αποτέλεσμα
if (dead(i)) {
    poison |= 1 << i;
}

το taste και το dead τι θα είναι ? Συναρτήσεις έτσι? (τι θα περιέρχουν)

[GReaperEx]

8 λεπτά πριν, Kugashira είπε

το taste και το dead τι θα είναι ? Συναρτήσεις έτσι? (τι θα περιέρχουν)

Ναι, τις έγραψα για να κάνω πιο ευανάγνωστο το παράδειγμα. Λογικά το "taste()" γίνεται πρώτα, και καθορίζει ποιος τέστερ θα γευτεί ποιο μπουκάλι. Το "dead()" διαβάζει τα αποτελέσματα του μήνα που πέρασε και σου λέει ποιοι έχουν πεθάνει.

[Επισκέπτης]

58 λεπτά πριν, GReaperEx είπε

Ναι, τις έγραψα για να κάνω πιο ευανάγνωστο το παράδειγμα. Λογικά το "taste()" γίνεται πρώτα, και καθορίζει ποιος τέστερ θα γευτεί ποιο μπουκάλι. Το "dead()" διαβάζει τα αποτελέσματα του μήνα που πέρασε και σου λέει ποιοι έχουν πεθάνει.

Μήπως θα μπορούσες να με βοηθήσεις στην υλοποίηση τους ? Δηλαδή πως θα χωρίζουμε ανάλογα με τα μπιτς τους τεστερς και πως τον 'νεκρο' με ένα random generator (ίσως?)

[archer100]

https://github.com/tieubao/til/issues/151

[Επισκέπτης]

53 λεπτά πριν, archer100 είπε

https://github.com/tieubao/til/issues/151

Στην θεωρία καλά είναι ! Κώδικας ?

[archer100]

n=int(input('type the count of bottles:'))

bottles=[bin(i)[2:] for i in range(1,n+1)]

tasters_count=max([len(i) for i in bottles])

result=''

for i in range(tasters_count):

	result+=input('Type 1 if taster-i died else type 0: ')

print('The poisoned bottle is bottle:' + str(bottles.index(result)))

Ένα παράδειγμα σε Python. Αν οι tasters είναι πολλοί, απλά να εισαχθεί το αποτέλεσμα σαν αλυσίδα 1 και 0, ΝΑΙ και ΟΧΙ, κλπ δεν έχει σημασία