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

[Asfodelus]

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

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

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

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

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

[mr.touchwood]

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

Αρχικά πιάνω 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)

[konfou]

Για απλοποίηση έστω το πρόβλημα με 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 μορφοποίηση συμβόλου

[Asfodelus]

Can You Solve the Poison Wine Challenge? | Infinite Series | PBS Digital

[Asfodelus]

Και μια λύση που βρέθηκε σε ένα backup

#include <array>
#include <bitset>
#include <iostream>
#include <random>
#include <cassert>

using namespace std;

// Return the number of bit required
// C++ ceil is not constexpr (yet),  so better create
// a custom function to get the number of bits need it
constexpr int getBins(int bootles) {
    auto num = log2(bootles);
    auto inum = static_cast<std::int32_t>(num);
    if (num == static_cast<float>(inum)) {
        return inum + 1;
    }
    return inum + (num > 0 ? 1 : 0);
}

int main() {
    constexpr auto bottles = 15;
    constexpr auto bins = getBins(bottles);

    // Initialize randomness and get a random bottle
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, bottles - 1);
    auto poison = dis(gen);

    cout << "The spy put  poison at bottle " << poison << ", or ("
         << std::bitset<bins>(poison) << ").\n";

    cout << "\nAnd the king order to number the " << bottles
         << "  bottles like this \n";
    std::array<std::bitset<bins>, bottles> bottles_collection;
    for (int i = 0; i < bottles; i++) {
        auto bottle = bitset<bins>(i + 1);
        bottles_collection[i] = bottle;
        cout << i << ":\t" << bottle << endl;
    }

    cout << "\nAnd the king order to make  " << bins << "  cocktails.\n";
    cout << "And in cocktail with number N put from bottles that have N bit "
            "equal to '1'.\n";

    std::array<std::bitset<bottles>, bins> cocktails_collection;
    for (int i = 0; i < bins; i++) {
        for (int j = 0; j < bottles; j++) {
            if (bottles_collection[j][i] == 1) {
                cocktails_collection[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < bins; i++) {
        cout << "And Bottle " << i << " (" << cocktails_collection[i]
             << ") have drops from bottles :";
        for (int j = 0; j < bottles; j++) {
            if (cocktails_collection[i][j] == 1) {
                cout << " '" << j << "'";
            }
        }
        cout << endl;
    }

    cout << "\nAnd the king orders  " << bins
         << " 'volunteers' to drink the cocktails.\n";
    std::bitset<bins> the_poison_bottle(0);
    for (int i = 0; i < bins; i++) {
        cout << "And volunteer Number " << i << " drinks the Cocktail " << i << "("
             << cocktails_collection[i] << ")";
        if (cocktails_collection[i][poison - 1] == 1) {
            cout << "\n\t and survives the evil king (for now)";
            the_poison_bottle[i] = 1;
        } else {
            cout << "\n\t and makes an appointment with the undertakers";
        }
        cout << endl;
    }

    cout << "\nAnd the wise king decide not to drink from bottle with the label ("
         << the_poison_bottle << ").\n";
    cout << "So they order to drop the bottle with the number "
         << the_poison_bottle.to_ullong() << "." << endl;


    assert(the_poison_bottle.to_ullong() == poison);
    return 0;
}

Και η έξοδος

The spy put  poison at bottle 7, or (0111).

And the king order to number the 15  bottles like this 
0:	0001
1:	0010
2:	0011
3:	0100
4:	0101
5:	0110
6:	0111
7:	1000
8:	1001
9:	1010
10:	1011
11:	1100
12:	1101
13:	1110
14:	1111

And the king order to make  4  cocktails.
And in cocktail with number N put from bottles that have N bit equal to '1'.
And Bottle 0 (101010101010101) have drops from bottles : '0' '2' '4' '6' '8' '10' '12' '14'
And Bottle 1 (110011001100110) have drops from bottles : '1' '2' '5' '6' '9' '10' '13' '14'
And Bottle 2 (111100001111000) have drops from bottles : '3' '4' '5' '6' '11' '12' '13' '14'
And Bottle 3 (111111110000000) have drops from bottles : '7' '8' '9' '10' '11' '12' '13' '14'

And the king orders  4 'volunteers' to drink the cocktails.
And volunteer Number 0 drinks the Cocktail 0(101010101010101)
	 and survives the evil king (for now)
And volunteer Number 1 drinks the Cocktail 1(110011001100110)
	 and survives the evil king (for now)
And volunteer Number 2 drinks the Cocktail 2(111100001111000)
	 and survives the evil king (for now)
And volunteer Number 3 drinks the Cocktail 3(111111110000000)
	 and makes an appointment with the undertakers

And the wise king decide not to drink from bottle with the label (0111).
So they order to drop the bottle with the number 7.