У 2012 році дослідники з лабораторії Ісікава Ватанабе Токійського університету створили робота-руку, який може грати в камінь-ножиці-папір із 100%-ним коефіцієнтом перемоги проти людини. Використовуючи високошвидкісну камеру, робот протягом однієї мілісекунди розпізнає, яку форму створює людська рука, а потім створює відповідну виграшну форму. © Вікіпедія.

Історія з епіграфу чудово демонструє, що до однієї тої самої події можна підходити по-різному. З точки зору алгоритму швидкого розпізнавання жестів достатно різних по  фізиології людей — то можна привітати дослідників з успіхом. Якщо подивитися з точки зору справедливості, то тих би самих японських розробників в справедливому селі беззлобно побили б, а робота-руку втопили б у найближчій річці. Бо нечесно. Це так само, коли на Паску хтось хитрий намагається стукатися фарбованим дерев’яним яйцем.

Варто зауважити, що існує інший підхід і навіть змагання алгоритмів для цієї гри.  Наприклад, Iocaine Powder, який виграв Перший міжнародний конкурс програмістів RoShamBo у 1999 році, використовує евристично розроблену компіляцію стратегій. Оптимальна стратегія або метастратегія вибирається на основі минулих результатів. Основними стратегіями, які він використовує, є зіставлення історії, частотний аналіз і випадкове вгадування. Його найсильніша стратегія, зіставлення історії, шукає послідовність у минулому, яка збігається з кількома останніми ходами, щоб передбачити наступний хід алгоритму. У частотному аналізі програма просто визначає хід, який найчастіше грають. Випадкова здогадка — це запасний метод, який використовується для запобігання нищівним втратам у разі невдачі інших стратегій.

Чого тільки не дізнаєшся у Вікіпедії! Привіт. Розглянемо задачу, створену за мотивами відомої гри. В старій версії сайту eolymp.com було вказано джерело задачі: 2007 ACM North America - Pacific Northwest, Problem A.

Умова:

Камінь, Ножиці чи Папір?

https://basecamp.eolymp.com/uk/problems/1215

У гру Камінь, Ножиці, Папір грають двоє. Кожен гравець на рахунок три одночасно вибирає один з трьох предметів. Гра триває певну наперед встановлену кількість раундів. Гравець, який виграє більшу частину раундів, оголошується переможцем. За заданою кількістю раундів та їх результатам необхідно визначити переможця.

Наступні правила описують правила перемоги:

• Камінь завжди перемагає Ножиці (Камінь раздавлює Ножиці)
• Ножиці завжди перемагають Папір (Ножиці ріжуть Папір)
• Папір завжди перемагає Камінь (Папір покриває Камінь)

Вхідні дані

Перший рядок містить кількість тестів t (0 < t < 1000). Перший рядок кожного тесту містить кількість раундів n (0 < n < 100), зіграних у гру Камінь, Ножиці, Папір. Кожен з наступних n рядків містить одну з великих літер R (Камінь), P (Папір) або S (Ножиці), пропуск і знову велику літеру R, P чи S. Перша літера позначає вибір першого гравця; друга літера - вибір другого гравця.

Вихідні дані

Для кожного тесту в окремому рядку вивести ім'я переможця (Player 1 чи Player 2). Якщо гра завершується унічию, вивести TIE.

Приклади

Вхідні дані:

3

2

R P

S R

3

P P

R S

S R

1

P R

Відповідь:

Player 2

TIE

Player 1

Пропоную залишити без розгляду питання кількості тестів і раундів. Вкладені цикли це чудово розв’язують і матеріалів в цьому напрямку — море. Давайте розглянемо задачу по суті.

Одна гра — це коли два учасники одночасно викидують фігуру. Це може бути або Камінь (Rock), або папір (Paper) або ножиці (Scissors).  Зліва записується буква фігури першого гравця, справа — буква фігури другого.

Пропоную піти простим шляхом. Записати всі можливі варіанти, які можуть випасти:

R R

R P

R S

P P

P R

P S

S R

S P

S S

Вісім варіантів. Чому саме вісім? Всі бачуть формулу? Якщо два учасника і три фігури (R P S), то виходить вісім. Якщо було б тих самих два учасника і чотири фігури, наприклад, RPSF то скільки було б варіантів? Можна виписати на листочку всі можливі і тоді, думаю, ви точно побачите формулу-залежність.

Пропоную вилучити «нічійні» варінти з наших восьми, залишилось шість:

R P

R S

P R

P S

S R

S P

Ділимо ці варінти на дві групи.  Нагадаю, що як зветься: камінь (R), папір (P), ножиці (S).

Запишемо ті варіанти, коли виграє перший гравець:

R S

P R

S P

Запишемо ті варіанти, коли виграє другий гравець:

R P

P S

S R

Формулюємо:

Якщо випадає комбінація R S або P R або S P, то додаємо один бал до кількості виграшів першого гравця, якщо випадає комбінація R P або P S або S R, то додаємо один бал до кількості виграшів другого гравця. Коли раунд завершується, аналізуємо кількості виграшів гравців і виводимо відповідне повідомлення, скидуємо лічильники виграшів і починаємо новий раунд.

Для тих, хто готовий писати код, успіхів. Для тих, хто не готовий — варіант кода є тут.

Успіхів!

У програмуванні багато чого можна робити по-різному. Підходи, методи, інструменти, оцінки якості варіантів, оптимізація — все це є цілим світом, різноманітним і захопливим. Пропоную сьогодні розглянути близьку, хоч і менш масштабну тему — взяти просту задачу і розв’язати її двома різними інструментами.  Обидва, звичайно, мають свої переваги і недоліки, отже буде про що подумати тим, хто таке любить.

Задача: Кульки

(https://basecamp.eolymp.com/uk/problems/113)

У продавця повітряних кульок є n кульок. Кожна з них має деякий колір. Але зовсім недавно Три Товстуни видали наказ, який дозволяє торгувати кульками тільки якогось одного кольору. Щоб не порушувати закон, але при цьому і не втратити прибуток, продавець вирішив перефарбувати деякі із своїх кульок.

Напишіть програму для визначення мінімальної кількості перефарбувань.

Вхідні дані

В першому рядку задано кількість кульок n (1 ≤ n ≤ 100000). Другий рядок містить n цілих чисел, в межах від 1 до 9, що визначає колір кульок (1 - синій, 2 - зелений, 3 - голубий, 4 - червоний, 5 - рожевий, 6 - жовтий, 7 - сірий, 8 - чорний, 9 - білий).

Вихідні дані

Виведіть мінімальну кількість кульок, які необхідно перефарбувати, щоб всі кульки були одного кольору.

Приклади

Вхідні дані #1

4

3 1 2 1

Відповідь #1

2

Вхідні дані #2

4

4 9 9 6

Відповідь #2

2

Вхідні дані #3

1

1

Відповідь #3

0

Проаналізувавши приклади бачимо, що задача нескладна.  Нам треба якомога менше кульок перефарбувати? Тоді давайте знайдемо, найбільшу кількість кульок одного кольору, а всі інші — перефарбуємо. Може бути варіант з повтором найбільшої кількості, наприклад 1 1 2 3 3. Але то не проблема, найбільша кількість кульок одного кольору — дві. А вже які ми будемо перефарбовувати, чи то 2 3 3 чи то 1 1 2 — для нашої задачі неважливо. В будь-якому варіанті перефарбувати доведеться три кульки.

В Python, як і в багатьох інших сучасних мовах програмування є можливість порахувати кількість елементів множини, що відповідає критерію. У нас в задачі всього дев’ять кольорів, тому давайте пошукаємо кількість кульок кожного кольору, знайдемо найбільшу з них і визначимо кількість кульок, які треба перефарбувати. Наприклад, так:

n = int(input())
b = [x for x in input().split()]
c1 = b.count('1')
c2 = b.count('2')
c3 = b.count('3')
c4 = b.count('4')
c5 = b.count('5')
c6 = b.count('6')
c7 = b.count('7')
c8 = b.count('8')
c9 = b.count('9')
print(n - max(c1, c2, c3, c4, c5, c6, c7, c8, c9))

Цей код здає задачу на 100%.  Можна поговорити про оптимальність, про красу коду, посварити за дев’ять змінних, може було б гарніше тримати дані по кількостям в списку. Це на ваш розсуд. Як на мене — цей розв’язок простий і зрозумілий. Традиційне запитання адептів уніфікованих рішень «А якщо кольорів буде не дев’ять, а стомільонів?» пропоную не розглядати, бо то буде інша умова, відповідно, інша задача і даний код може бути неоптимальним, а то і непрацюючим взагалі. Ми ж розглядаємо не універсальну, а конкретну задачу.

Але ж в Python так багато смачного… Є відчуття, що  код може бути гарніший. Може :) Давайте спробуємо Counter з модуля collections.

Припускаємо, що у нас є двадцять кульок різних кольорів, наприклад, таких

1 2 3 7 1 5 6 7 4 7 4 2 7 8 1 4 7 9 8 9

Давайте ми ці значення закинемо у список, а список віддамо в Counter. Що буде? Ось код:

from collections import Counter

n = int(input())

b = [x for x in input().split()]

c = Counter(b)

print(c)

Ось що буде:

Counter({'7': 5, '1': 3, '4': 3, '2': 2, '8': 2, '9': 2, '3': 1, '5': 1, '6': 1})

Кольору «7» — п’ять кульок, кольору «1» — три кульки, кольору «4» — три кульки і т.д.

І, очікувано, ми можемо визначити найбільш популярний колір:

print(c.most_common(1)[0][0])

І кількість кульок цього найпопулярнішого кольору:

print(c.most_common(1)[0][1])

Весь код розв’язку цієї задачі з використанням Counter:

from collections import Counter

n = int(input())

b = [x for x in input().split()]

c = Counter(b)

print(n - c.most_common(1)[0][1])

Як на мене, цей код теж має право на існування. Знайдуться ті, кому він подобається і ті, кому ні.  Буде тема для обговорення. Може кому  буде цікаво, в офіційному Python-help при поясненні Counter автори рахують кількість найпопулярніших слів в файлі hamlet.txt :)

Якщо вас зацікавила тема, у нас на «Плетиві» вже є стаття, де описано використання Counter,  там розв'язується задача «Покер».  

Успіхів!

Цінність задачі, що ми розглянемо, в тому, що для її розв’язку не треба серйозних знань з системних дисциплін. Задачу можна розв’язати лише за допомогою звичайної логіки, підгледівши синтаксис в міні-довідниках.

Умова:

Мінімальна кількість купюр
(https://basecamp.eolymp.com/uk/problems/2033)

Дано натуральне число N (8 ≤ N ≤ 1000000), яке визначає будь-яку цілочислову грошову суму ≤ 1000000. Відомо, що цілочислову грошову суму, більшу чи рівну 7 грошовим одиницям, можна видати лише купюрами номіналом у 2 та 5 грошових одиниць. Визначте, якою кількістю купюр у 2 та 5 грошових одиниць можна видати суму в N грошових одиниць, щоб їхня загальна кількість була найменшою.

Вхідні дані

Єдине число - задана сума.

Вихідні дані

Єдине число - шукана мінімальна кількість купюр.

Приклади

Вхідні дані:

9

Відповідь:

3

Логічним буде припущення, що для мінімізації кількості купюр, варто брати купюри більшого номіналу. Тобто, якщо нам треба набрати 10 гривень, то логічним буде спробувати брати більші купюри — в 5 гривень. Беремо таких дві штуки і у нас чудово набирається 10 гривень.

Записуємо: 10 = 5 + 5.

Відповіддю буде два – кількість купюр. Логічно? Логічно.

Проводимо наступний віртуальний експеримент. Припустимо, нам треба набрати 11 гривень і у нас так само — купюри в 5 і купюри в 2 гривні.

Беремо максимальну кількість купюр максимального номіналу. Що виходить?
11 = 5 + 5 + (1 це залишок)

А купюри в одну гривню у нас нема. Так само ми не розв’яжемо задачу якщо у нас в залишку буде 3 гривні, тобто якщо у нас в залишку буде непарне число. Що в такому випадку робити?

Пропоную наступний алгоритм: якщо залишок виходить непарним, то повертаємо назад одну купюру в 5 гривень, відповідно, залишок збільшується на 5 гривень і ми будемо його набирати купюрами в 2 гривні. П’ять — число непарне, відповідно після операції повернення залишок з непарного стане парним.

11 = 5 + 5 + 1. Ні, бо залишок (1) непарний, тому 11 = 5 + (6 це залишок). Відповідно, 11 = 5 + 2 + 2 + 2 (всього — чотири купюри).

Проведемо ще кілька  експериментів:

12 = 5 + 5 + 2 (три купюри)

13 = 5 + 5 + 3. Ні, бо залишок (3) непарний, тому 13 = 5 + 2 + 2 + 2 + 2 (п’ять купюр)

14 = 5 + 5 + 2 + 2 (чотири купюри)

15 = 5 + 5 + 5 (три купюри)

16 = 5 + 5 + 5 + 1. Ні, бо залишок (1) непарний, тому 16 = 5 + 5 + 2 + 2 + 2 (п’ять купюр)

17 = 5 + 5 + 5 + 2 (чотири купюри)

18 = 5 + 5 + 5 + 3. Ні, бо залишок (3) непарний, тому 18 = 5 + 5 + 2 + 2 + 2 + 2 (шість купюр)

Сподіваюсь, зрозуміло пояснив.  

Успіхів!

Іноді трапляється так, що умова задачі сформульована неточно. Буває, що в ній багато зайвих деталей, які відволікають. А іноді автори навмисно заплутують умову. Пропоную розглянути задачу «Сортуюча машина", в умові якої є приклад-пояснення. Проте алгоритм, описаний у прикладі, зовсім неоптимальний. Якщо зробити по-своєму, задача виявляється нескладною.

Умова:

Сортуюча машина
(https://www.eolymp.com/uk/problems/1144)

Є машина для сортування набору різних чисел. Вона має лише одну команду MOVE з одним аргументом. Ця команда переміщує число, вказане в аргументі, в кінець послідовності. Наприклад, щоб відсортувати масив чисел 19,7,8,25 у зростаючому порядку, потрібно виконати дві команди:

1. MOVE 19, отримаємо 7,8,25,19.
2. MOVE 25, отримаємо 7,8,19,25.

Для заданого набору чисел необхідно знайти мінімальну кількість команд MOVE, після виконання яких його елементи будуть упорядковані у зростаючому порядку.

Вхідні дані

Перший рядок містить кількість чисел n (n≤50). Другий рядок містить n цілих чисел у діапазоні від −1000 до 1000.

Вихідні дані

Виведіть мінімальну кількість команд MOVE, після виконання яких усі числа будуть упорядковані у зростаючому порядку.

Давайте розберемо приклад, представлений в умові.

У нас є послідовність: 19,7,8,25. І нам потрібно відсортувати її за зростанням.

Як це пропонується в умові ми робити не будемо. Робити це за алгоритмом, запропонованим в умові, складно. Спочатку нам потрібно перемістити число 19, але воно не є ані найбільшим, ані найменшим, чому варто починати саме з нього, з усім тим потрібно возитися. Пропоную інший підхід — метод стіни. Давайте після списку намалюємо червону стіну:

19,7,8,25|

Наступним кроком ми проаналізуємо список ліворуч від стіни. Може він вже відсортований. Тоді жодних переміщень робити  не потрібно, можна виводити нуль і йти спати. Якщо список не сортований, то виконуємо таку дію:

Знаходимо найбільше число, перекидуємо його за стіну і загинаємо палець кількості виконаних команд MOVE. Що у нас вийде в нашому прикладі?

19,7,8|25

Ми зробили одне переміщення і у нас тепер один загнутий палець.

Знову аналізуємо список ліворуч від стіни, він не сортований (19,7,8). Знову відшукуємо максимальний елемент, перекидуємо його за стіну і загинаємо ще один палець:

7,8|19, 25

Продовжуємо. Список ліворуч від стіни відсортований? Так. Чудово. Виводим кількість загнутих пальців і завершуємо роботу програми.

Уважний читач помітить, що числа справа від стіни при такому алгоритмі завжди будуть відсортовані. Тому ми можемо їх не переносити за стіну, а видаляти з несортованого списка, загинаючи палець.

Вхідні дані:

19,7,8,25

Не відсортований список? Тоді знаходимо максимум, видаляємо його, загинаємо палець. Що залишилось:

19,7,8

Не відсортований список? Тоді знаходимо максимум, видаляємо його, загинаємо ще один палець. Що залишилось:

7,8

Не відсортований список? Відсортований. Виводимо кількість загнутих пальців і завершуємо роботу програми.

Погодьтесь, цей спосіб значно простіший, ніж наведений в умові.

Який з цього всього можна зробити висновок?  Якщо ви досюди дочитали, то ви розумні. Сформулюйте самі )

Хто зрозумів моє пояснення  – можете написати код і здати задачу. У кого не виходить, натисність «детальніше» - побачите один з варіантів коду.

Успіхів!