Решавање на сите 42 верзии на сложувалката за напивки за Хари Потер

На крајот од книгата „Хари Потер и филозофскиот камен“ има една интересна загатка. Хари и Хермиона влегуваат во собата, по што влезовите во неа се блокирани од магичен оган, а од неа можат само да ја решат следнава загатка:

Пред вас е опасност, а зад вас е спасот,
Ќе ти помогнат двајца, кои ќе ги најдеш меѓу нас;
Со еден од седумте напред ќе продолжите да се движите
Другиот веднаш ќе ве врати назад.
Кај нас двајца ќе најдете само вино од коприва,
И три носат смрт, стојат во низа скришум.
Затоа, изберете кој ви е судено да го вкусите,
За да го направите ова, даваме четири совети.
Залудно отровот се обидуваше да ја скрие својата смртоносна топлина,
Секогаш ќе го најдете лево од виното,
И знајте дека оние што се на рабовите имаат поинаков подарок,
Но, ако сакате да одите понатаму, никој нема да помогне.
Се разликуваме по големина, од раб до раб,
Твојата смрт не седи во помала, но не и во поголема;
Второ од десниот крај и второ од лево
Имаат вкус на близнаци, иако изгледаат поинаку.

[од „народниот превод“ на книгата „Хари Потер и филозофскиот камен“]

Едноставно кажано, тие треба да сфатат во кои шишиња кои напивки содржат.

Во оваа статија ќе ги решиме сите 42 можни варијанти на оваа загатка користејќи програмирање и ќе нацртаме график на резултатите (како на сликата погоре, само многу поголем).

Чекај малку, од каде 42 опции?

Тоа е затоа што локациите на „помалите“ и „поголемите“ напивки не се наведени. Поголемиот може да биде на едно од седумте места, што дава 6 преостанати опции за помалото, вкупно 7 * 6 \u42d 42. Нема да може да се дознае точно кој аранжман го имала на ум ЈК Роулинг при доаѓањето со оваа загатка, освен ако таа не каже за тоа на вашиот Твитер. Во меѓувреме, додека не дојде тој неизбежен ден, можеме да избереме случајна верзија и да работиме со неа. Сепак, нема да има гаранции за неговата решливост, поради што работиме за општо добро, решавајќи ги сите XNUMX варијанти на сложувалката (или докажувајќи ја нивната нерешливост).

ДА ОДЛУЧЕТЕ ВЕЌЕ

Прво, еве ги сите ограничувања на сложувалката, преформулирани на едноставен начин:

1. Има две безопасни напивки, 3 отруени, една која ви овозможува да одите напред и една што ви овозможува да се вратите назад.
2. Лево од секоја од двете безопасни напивки е отровна.
3. Напивките од двете страни се различни и ниту една од нив не ви дозволува да одите напред.
4. Најголемите и најмалите шишиња не содржат отров.
5. Второто шише лево и второто шише десно ја содржат истата напивка.

Како да се справите со тоа? Размислете за следнава опција. Забележете дека, како што вели загатката, во редот има 1 шише помало од сите други по големина и 1 шише поголемо од сите други.

Ајде да се обидеме глупаво да ги поминеме сите опции - земете по едно шише и изберете ги сите можни опции за содржината.

На пример, првото шише не може да содржи напивка што нè движи напред поради ограничувањето број 3. Исто така, не содржи безбедна напивка поради ограничувањето бр. 2 - никаков отров не може да се стави лево од него. Ова ни остава со опциите Poisoned Potion и Returning Potion. Ајде да ги пробаме двете опции.

На следните слики, зелените напивки се отров, портокаловите напивки се безбедни пијалоци, сините напивки се движат наназад, а виолетовите напивки се движат напред.

Да го повториме овој процес за двете работни опции - земете го второто шише и наизменично пробајте ги сите валидни опции за содржина. Ова ќе ни го даде следново:

Продолжувајќи во оваа насока и отфрлајќи ги сите работни опции во кои некое шише не може да се наполни со напивка без да се прекршат наведените ограничувања, ќе дојдеме до единствената прифатлива опција:

Нормално, немавме гаранции да најдеме решение. Можеби нема да има решение, или може да има повеќе од едно (а ако имате повеќе од едно решение, тоа е еквивалентно на фактот дека загатката не може да се реши, бидејќи не се знае која од напивките е точна).

Примената на алгоритмот на сите варијанти ни ги дава следните решенија. 8 опции за загатки се решливи, 8 немаат решенија, а 26 имаат повеќе решенија.

Повеќе за решенијата

Дали има нешто заедничко помеѓу сите решени варијанти на сложувалката? Да! Ве молиме имајте предвид дека во нив најмалите или најголемите шишиња се на 2 или 6 места. Ова ни овозможува да заклучиме дека 2. и 6. шишиња содржат безбедни напивки поради ограничувањата #4 и #5. Без овој чекор, не можеме да ја елиминираме можноста овие шишиња да содржат отров, и на крајот да дојдеме до неколку можни решенија. Исто така решените опции бараат второто „специјално“ шише (најмало или најголемо) да биде на 3 или 4 место. Во спротивно, не може да се најде точната локација на напивката која не движи напред.

Резултатите од

Ќе завршам со цитат од книгата.

Хермајни дишеше гласно, а Хари беше изненаден кога виде дека таа се смешка - тоа беше последното нешто на што можеше да се сети. „Брилијантно“, рече Хермајни. „Тоа не е магија - тоа е логика, загатка. Многу од најголемите волшебници немаат ни трошка логика и би биле заглавени тука засекогаш“.

Но, еј, можеби можеме да ја откриеме канонската верзија на сложувалката врз основа на дијалогот од книгата:

„Се разбира“, рече таа. „Најмалото шише ќе не однесе низ црниот оган и до Каменот“.

...

„Која ќе те остави да се вратиш низ пурпурниот оган?

Хермајни покажа на тркалезно шише на десната страна од редот.

По ѓаволите. Оваа опција сепак ни дава неколку решенија. Твитер, ДР.

Код

Доколку ве интересира кодот за решавање на оваа загатка и цртање дијаграми, можете Download here.

Извор: www.habr.com