Προγραμματιστική πρόκληση Νο 11: O κακός άρχοντας

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

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

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

Σε ένα μήνα έχει τα γενέθλια του και κάτι πρέπει να γίνει σύντομα. Φτιάξε ένα αλγόριθμο και υλοποίησε ένα πρόγραμμα που να βοηθήσει τον άρχοντα να απολαύσει ένα ποτήρι κρασί στα γενέθλια του. Καλό για τα χωράφια είναι να χρησιμοποιήσεις το πολύ 10 χωρικούς.

Hint: Σκέψου στην γλώσσα του επεξεργαστή[

Αυτή είναι μια λύση που σκέφτηκα. Η υλοποίηση δεν είναι πολύ ψαγμένη, αλλά η σκέψη πρέπει να είναι σωστή.

Αρχικά πιάνω 10 χωρικούς και τους δίνω να πιουν κρασί ως εξής:
ο 1ος πίνει από τα μπουκάλια 0, 2, 4, 6, 8, 10… (δηλαδή 1 πίνει, 1 όχι)
ο 2ος πίνει από τα μπουκάλια 0, 1, 4, 5, 8, 9… (δηλαδή 2 πίνει, 2 όχι)
ο 3ος πίνει από τα μπουκάλια 0, 1, 2, 3, 8, 9, 10, 11… (δηλαδή 4 πίνει, 4 όχι) κοκ

# -*- coding: utf-8 -*-
import time
for i in range(10):
    switch_every = pow(2, i)
    counter = 1

    for j in range(1000):
        if (counter<=switch_every):
            drink(villager[i], wine bottle[j]) # Ο χωρικός i πίνει το μπουκάλι j
        counter += 1
        if (counter == 2*switch_every): # Έχει πιει όσα μπουκάλια πρέπει και έχει αφήσει άλλα τόσα
            counter = 1

time.sleep(2629746) #Περιμένουμε 1 μήνα για τα αποτελέσματα

Έστω ότι έχουμε τον πίνακα villagers[10] στον οποίο:

  • Αν villager[i] == 0, τότε είναι νεκρός
  • Αν villager[i] == 1, τότε είναι ζωντανός

Μετατρέποντας τον πίνακα villager σε decimal, παίρνω το νοθευμένο μπουκάλι

poisoned_bottle = 0
for i in range(10):
    if (villager[i] == 0):
        poisoned_bottle += pow(2, i)
print(poisoned_bottle)
2 Likes

Για απλοποίηση έστω το πρόβλημα με 8 μπουκάλια, όπου επιλέγεται τυχαία
ένα από αυτά να έχει δηλητήριο. Για παράδειγμα έστω το n = 3.

Το διάστημα [0 .. 7] μπορεί να αναπαρασταθεί από το λιγότερο τρία bits
(καθώς 2^3 \ge 8 = \dim [ 0 .. 7]), όπου το κάθε ένα αποτελεί ένα
άτομο/δοκιμαστή. Η θέση του επιλεγμένα τυχαίου μπουκαλιού σε binary
είναι n_2=0b011 (για σύγκριση στη λύση).

Το κάθε άτομο δοκιμάζει από όλα τα μπουκάλια που αντιστοιχούν στους
συνδυασμούς που έχουν το bit που αναπαριστά το άτομο ενεργό. Συνεπώς το
καθένα πίνει τα ακόλουθα

p = 0: 0b__1 = [0b001, 0b011, 0b101, 0b111] = [1, 3, 5, 7] (has 3; dies)
p = 1: 0b_1_ = [0b010, 0b011, 0b110, 0b111] = [2, 3, 6, 7] (has 3; dies)
p = 2: 0b1__ = [0b100, 0b101, 0b110, 0b111] = [4, 5, 6, 7]

Αν τώρα φτιάξουμε ένα binary όπου το bit είναι μονάδα αν το αντίστοιχο
άτομο πεθαίνει προκύπτει και το μπουκάλι με το δηλητήριο. Δηλαδή στο
παράδειγμα εδώ είναι n_2=0b001 + 0b010 = 0b011.

Η γενική ιδεά βασικά είναι πως το κάθε άτομο δίνει πληροφορία για το bit
στο οποίο αντιστοιχεί, ανάλογα με το αν πεθαίνει (1, αλλάζει κατάσταση)
ή ζει (0, μένει στην αρχική κατάσταση).

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

bitsreq(n) = Int(ceil(log2(n)))

Αυτό προκύπτει παίρνοντας τη συνθήκη

2^\text{bits} \ge n \Rightarrow \text{bits} \ge \log_2 n \Rightarrow \text{bits}_\text{req} = ⌈ \log_2 n ⌉

Για δοκιμή στο πρόβλημα γίνεται αρχικοποίηση ενός array με μηδενικές
τιμές (ασφαλή, δεν περιέχεται δηλητήριο), επιλέγεται τυχαία κάποιο, και
αλλάζει η τιμή του σε 1 (δηλητήριο). Επίσης βρίσκονται τα απαιτούμενα
bits χρησιμοποιώντας τη προηγούμενη συνάρτηση.

nmax = 1000
arr = fill(0, nmax)
indx = rand(1:nmax)
arr[indx] = 1
bits = bitsreq(nmax)
# bitsreq(1000) = 10

Στη συνέχεια δημιουργούνται κάποιες βοηθητικές συναρτήσεις. Eπειδή η
Julia είναι index-1 γλώσσα, έτσι πως έχω γράψει το κώδικα, το αποτέλεσμα
0 αντιστοιχεί στη τιμή 1000 (γενικά nmax). Οπότε στο τελικό
αποτελέσμα κάνω την διόρθωση αυτή.

chkbit(n, p) = @. n & (1 << p) != 0
drinks(p) = chkbit(1:nmax, p)
dies(p) = in(1, view(arr, drinks(p)))
fix1(x) = x == 0 ? nmax : x

Τελικά βρίσκονται τα άτομα που πεθαίνουν, το οποίο δίνει ένα binary
αριθμό. Μετατρέποντας τον αριθμό αυτό σε δεκαδικό προκύπτει το μπουκάλι
με το δηλητήριο.

bin = join(Int.(map(dies, (bits - 1):-1:0)))
res = fix1(parse(Int, bin, base=2))
res == indx
# true

Αν θυμάμαι σωστά περίπου αυτή είναι η θεωρία πίσω από το 20Q παιχνίδι
και το Akinator. Βασικά κάθε απάντηση δίνει γνώση για ένα bit. Αν και
στο δεύτερο εφαρμόζονται και fuzzy τεχνικές γιατί μερικοί παράμετροι
είναι άγνωστοι ή ισχύουν μερικώς.

Διόρθωση: LaTeX μορφοποίηση συμβόλου

1 Like