Ктулхи у банку: як ми вирішували ICFPC 2015

Невеликий звіт про те, як ми вирішували ICFP Contest 2015. Ми брали участь в даному змаганні вперше, однак результат вийшов досить непоганий. Можна пошукати нас в таблиці проміжних результатів під ім'ям «WILD BASHKORT MAGES». Фінальні результати очікуються протягом декількох найближчих тижнів, коли організатори протестують всі рішення на повному наборі тестів.



В цьому році в якості завдання пропонувалося написати решалку (або ІІ, кому як зручніше) для гексагонального тетрису. Все як у звичайному тетрисе — укладаємо фігурки, прибираємо заповнені рядки, отримуючи за це окуляри. Рішення повинно працювати для різних розмірів ігрового поля і укладаються фігурок довільної конфігурації. Команди дій з фігурками (переміщення і повороти) кодуються звичайними символами, в результаті рішенням є рядок команд. За спеціальні секретні послідовності символів в рядку-рішенні, звані power words, даються додаткові бонусні очки. За сюжетом — дані рядка іменувалися даваром, і організатори збирали його для того, щоб відстрочити пробудження Ктулху.

Читати далі →

Рішення задачі «AAAAAA» із Facebook Hacker Cup методом динамічного програмування на B-Prolog

Є багато матеріалу за рішенням заплутаних завдань на Пролозі (наприклад, сторінка Hakan Kjellerstrand про B-Prolog). Однак часто наводяться завдання, які створювалися для вирішення вручну (мають маленьке простір пошуку), або спочатку орієнтовані на рішення за допомогою логічного програмування.

Я хочу показати моє рішення на Пролозі завдання AAAAAA з першого раунду Facebook Hacker Cup 2014. Завдання має досить великий простір пошуку і створена з прицілом на рішення досвідченими спортивними програмістами на поширених мовах програмування.

Читати далі →

Переклад підручника по алгоритмах

  
 
Радий повідомити, що вийшов переклад відмінного підручника Дасгупта, Пападімітріу, Вазірані «Алгоритми», над яким я працював останні кілька років. У книзі багато алгоритми пояснені набагато коротше і простіше, ніж в інших підручниках: з одного боку, без зайвого формалізується, з іншого — без втрати математичної строгості. Відкрийте книгу на якому-небудь відомому вам алгоритмі і переконаєтеся в цьому. =)
 
Загалом, угощайтесь: друкований варіант перекладу , електронний варіант перекладу (PDF) , друкований варіант оригіналу , електронний варіант оригіналу (PDF) .
 
Читати далі →