Обучение Haskell — работа в Москве

Для работы В решении задания: Варианты практического задания Интерпретаторы Моделирование машины Тьюринга Машина Тьюринга (МТ), формализующая понятие алгоритма, состоит из: ? бесконечной одномерной ленты, разделённой на ячейки; ? головки, работающей как детерминированный конечный автомат. В ячейках могут быть записаны символы некоторого конечного алфавита, а также особый символ, помечающий “пустые“ ячейки. Головка в каждый момент находится в одном из допустимых состояний и может перемещаться влево и вправо по ленте, читать и записывать символы в ячейки. При запуске МТ на ленте записано входное слово в заданном алфавите, а головка находится в начальном состоянии на первом символе этого слова, слева и справа от слова записаны пустые символы. Далее МТ работает по шагам, согласно правилам перехода (их набор образует программу машины). Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого головкой символа, записать в эту клетку новый символ, перейти в новое состояние и переместить головку на одну клетку влево или вправо, либо же остаться на месте. Некоторые состояния машины могут быть помечены как терминальные, и переход в любое из них означает остановку работы, результатом при этом является слово, записанное к этому моменту на ленте. Предлагается смоделировать работу МТ, визуализируя этот процесс для произвольных входных слов и программы (набора правил перехода). Модель МТ должна выполнять загрузку программы из файла, ввод исходного слова, установку головки на его начало, а затем запуск процесса его обработки по шагам, согласно программе. При этом на любом шаге пользователь может прервать и затем продолжить работу МТ (альтернативой является пошаговый режим, при котором после каждого шага работы происходит останов). 2 Описание программы для МТ в виде файла должно включать задание алфавита символов (для входных слов), множества состояний головки с указанием начального и конечных состояний, а также правил перехода. Формат описания может быть предложен самостоятельно или же можно воспользоваться одним из языков разметки (например, JSON, YAML, TOML). Интерпретатор подмножества языка Паскаль Требуется реализовать интерпретатор программы, записанной на подмножестве языка Паскаль. Синтаксис подмножества задаётся следующими БНФ-правилами (фигурные скобки означают повторение заключённой в них конструкции 0, 1 или произвольное число раз). программа ::= program имя; раздел_переменных раздел_операторов имя ::= идентификатор раздел_переменных ::= var секция {; секция}; секция ::= имя {, имя} : тип тип ::= integer | boolean конст._бз ::= цифра {цифра} логич._значение::= true | false раздел_операторов ::= begin оператор {; оператор} end. оператор ::= оператор_присваивания | оператор_вывода | составной_оператор | оператор_цикла_с_предусловием | оператор_выбора | условный_оператор оператор_присваивания ::= имя:=выражение выражение ::= простое_выражение | простое_выражение операция_отношения простое_выражение операция_отношения ::= > | < | <> | <= | >= | = простое_выражение ::= слагаемое | простое_выражение операция_сложения слагаемое операция_сложения ::= + | - | or слагаемое ::= множитель | слагаемое операция_умножения множитель множитель ::= имя | (выражение) | конст._бз | логич._значение | not множитель операция_умножения ::= * | div | mod | and оператор_вывода ::= writeln(список_элементов) список_элементов ::= элемент{,элемент} элемент ::= выражение составной_оператор ::= begin оператор{; оператор} end оператор_цикла_с_предусловием ::= while выражение do оператор оператор_выбора ::= case выражение of вариант {; вариант} endcase вариант ::= метка_варианта : оператор метка_варианта ::= константа | логическое_значение условный_оператор ::= if выражение then оператор else оператор Интерпретатор паскаль-программ выполняет: ? ввод паскаль-программы из текстового файла; ? перевод программы во внутреннее представление (синтаксическое дерево); ? интерпретацию (вычисление) синтаксически правильной программы (по построенному внутреннему представлению). В ходе перевода паскаль-программы во внутреннее представление и его интерпретации необходимо выявлять возможные ошибки (не менее 5 ошибок), и при их обнаружении выводить диагностические сообщения. Перечень обнаруживаемых ошибок может включать: o нарушение баланса открывающих и закрывающих скобок в выражениях; o нарушения синтаксиса записи операторов, в том числе – баланса операторных скобок begin и end, а также case и endcase; o неописанный или дважды описанный идентификатор; o несоответствие типов в операторе присваивания и в выражении; o неверный тип выражения в условном операторе и операторе цикла; o run-time ошибки: переменная без значения, деление на ноль, зацикливание. 3 Интерпретатор диалекта языка Лисп Реализовать интерпретатор диалекта языка программирования Лисп, включающего его функциональное ядро и расширяющего понимание S-выражения. S-выражение охватывает: ? атомы: IAMATOM, numberp, setf и т.п. ? числа: 10, 34.2, ... ? строки : “hello, world!“ и т.п. ? пустой список: nil или () ? точечные пары , например: (“wrld“ . 2) . Кроме базового набора функций Лиспа (car, cdr, cons, eq, atom, quote , eval, cond) диалект включает 10-15 других встроенных функций: предикаты (numberp, atomp, listp, =), функции работы со списками (append, list и др.), средства определения пользовательских функций(lambda, defun, let). Допускаются императивные конструкции (например, setq, setf). Интерпретатор лисп-программы должен включать парсер, переводящий ее в абстрактное синтаксическое дерево (и осуществляющий синтаксический анализ), и модуль, выполняющий ее вычисление в простой интерактивной среде программирования (REPL). Конвертация форматов Конвертировать заданный текстовый файл из одного формата в другой формат. Имя исходного файла и имя результирующего файла задаются как аргументы командной строки. Возможен следующий выбор форматов (два из трех): ? JSON (https://ru.wikipedia.org/wiki/JSON) ? XML (https://en.wikipedia.org/wiki/XML). ? YAML (https://en.wikipedia.org/wiki/YAML) В программе необходимо определить внутреннее представление для описания основных объектов выбранных форматов. Регулярные грамматики и конечные автоматы Построение конечного автомата по грамматике По заданному тексту регулярной (леволинейной или праволинейной) формальной грамматики построить соответствующий конечный автомат для распознавания предложений языка, порождаемого этой грамматикой. Грамматика задаётся как конечный набор правил вида T = aN|b, альтернативы в правых частях правил не могут быть пустыми. Нетерминальные символы грамматики записываются заглавными (большими) латинскими буквами, а терминальные – строчными (маленькими). Начальный символ грамматики обозначается буквой H (для праволинейной) или S (для леволинейной грамматики). Построенный автомат представляет собой ориентированный и помеченный граф. Вершины графа соответствуют состояниям автомата и помечены нетерминальными символами грамматики; в множество вершин входят начальное и заключительное состояния H и S. Рёбра графа соответствуют переходам между состояниями автомата и помечены терминальными символами грамматики. Граф можно реализовать в виде списка входящих в него рёбер, для каждого ребра указываются метки соединяемых вершин и метка_ребра. На вход программы подаётся текст грамматики, возможно, без разделяющих пробелов, но правила грамматики разделены точкой с запятой, к примеру: H=aN|bN;N=cN|d. В случае недетерминированности полученного по грамматике автомата необходимо построить эквивалентный ему детерминированный автомат (детерминированный автомат, распознающий тот же самый язык). Итоговый автомат может быть визуализирован либо выведен в виде набора ребер. 4 Построение регулярной грамматики по конечному автомату По заданному конечному автомату восстановить соответствующую регулярную леволинейную (или праволинейную) формальную грамматику, включающую алфавиты (множества) терминальных и нетерминальных символов и набор правил грамматики, а также начальный символ грамматики: H (для праволинейной) или S (для леволинейной) . Конечный автомат представляется как ориентированный граф, вершины которого соответствуют состояниям автомата и помечены нетерминальными символами грамматики, в множество вершин входит начальное состояние H и заключительное S. Рёбра графа соответствуют переходам между состояниями автомата и помечены терминальными символами грамматики. Граф представлен в текстовом файле, каждое ребро записывается на отдельной строке. Граф можно реализовать в виде списка входящих в него рёбер, для каждого ребра указываются метки соединяемых вершин и метка_ребра. Результирующая (восстановленной по конечному автомату) регулярная грамматика должна быть выведена в виде текста, каждое правило (с альтернативами) – в отдельной строке. В записи грамматики нетерминальные символы грамматики записываются заглавными (большими) латинскими буквами, а терминальные – строчными (маленькими). Правая и левая часть каждого правила разделяются знаком равенства =, а сами правила – знаком ; , в тексте правила нет пробелов, например: В=aN|bN;N=cN|d. Исходный конечный автомат может быть как детерминированным, так и недетерминированным. В полном решении задачи в случае недетерминированности автомата необходимо построить, кроме грамматики, эквивалентный ему детерминированный автомат (детерминированный автомат, распознающий тот же самый язык). Расчет чека (“кассовый аппарат“) Реализовать процедуру расчета стоимости покупки для заданной корзины с товарами и выдачи соответствующего чека, с учетом бонусной карты покупателя. Каждый товар в магазине характеризуется названием, ценой и категорией (не менее 3 категорий, и в каждой не менее 7 товаров). Корзина покупателя представляет собой набор товаров и количество каждого из них. Бонусная карта содержит информацию о дне рождения покупателя и процентах скидки по карте (до 7%). Программа получает на вход (в командной строке или интерактивно): – имя файла с информацией о товарах в магазине; – имя файла с информацией о корзине покупателя; – имя файла с информацией о бонусной карте покупателя (может отсутствовать). Скидка может быть рассчитана по нескольким правилам (не менее 2-3), например, при покупке нескольких товаров из одной категории, при покупке более чем на определённую сумму и т.п. Итоговый чек должен печататься в удобочитаемом виде и содержать: ? название конкретного товара, количество, цену за единицу и его полную стоимость; ? полную стоимость всей покупки без учёта скидок; ? информацию о скидках, если они применимы; ? полную стоимость всей покупки с учётом скидок. Программа должна обрабатывать следующие ошибки, при которых расчет чека невозможен: o неверный формат данных во входных файлах; o отрицательные цены или отрицательное количество товаров в корзине; o проценты скидки на бонусной карте, отрицательные или превышающие 7 %. Если же в корзине встречается товар, для которого нет информации о цене (возможно, из-за отсутствия в продаже) – в этом случае нужно напечатать предупреждение и сформировать чек, не включая в него этот товар. 5 Интерактивные ассистенты Программная поддержка записи к специалисту Известно недельное расписание работы специалистов одного конкретного профиля (врача/нотариуса/парикмахера/тату-мастера и др.), с местами (“окошками“) для записи к ним. Специалист может предоставлять несколько видов услуг/процедур с разной стоимостью и временем приема/обслуживания. Необходимо реализовать программу, помогающую пользователю записаться к одному из специалистов, в нужные/возможные день и время. Текущее расписание специалиста задается в текстовом файле (для каждого специалиста – свой файл) и содержит позиции, уже занятые для записи (не менее 5 записей). Задается также стоимость услуг/процедур и их длительность. Текстовые файлы всех специалистов считываются программой перед началом диалога, и строится внутреннее представление расписания/ий, при этом возможно выявление ошибок формата записи входных файлов. Исходный запрос пользователя содержит его идентификатор (ФИО, емейл или номер телефона), остальное может быть определено не полностью (например, не задано желаемое время/день недели или не указана нужная услуга), и определяется в ходе диалога с пользователем. В диалоге уточняются все детали записи, предлагаются возможные ее варианты (а в случае ошибок ввода делаются подсказки). В конце диалога выводится детальное описание произведенной записи к специалисту. Диалог может допускать возможность отмены или изменения записи (с учетом текущего состояния расписания), вывод всех записей пользователя. По запросу для конкретного специалиста может быть выведено его итоговое расписание на неделю. Ассистент в бронировании Требуется реализовать программу, в диалоге с которой пользователь может забронировать номер в гостинице/столик в кафе или др. Для гостиницы известны вид номеров и их количество, посуточная оплата, а также их текущая занятость на ближайшую неделю. Для кафе – количество столиков с определенным числом посадочных мест, их местоположение (у окна/внутри зала/др.), стоимость бронирования (может зависеть от дня недели, времени дня, числа гостей), уже забронированные/занятые столики. Вся эта информация о гостинице/кафе задается в текстовом файле и включает данные об уже забронированных/занятых номерах гостиницы/столиках кафе. Исходный запрос пользователя на бронирование может быть определен частично (например, не задан вид номера гостиницы или не указано число посадочных мест для столика кафе), и в ходе диалога ему предлагаются возможные варианты бронирования и уточняются все его детали (в случае ошибок ввода делаются подсказки). В конце диалога выводится детальное описание произведенного бронирования. Диалог может допускать возможность отмены или изменения бронирования. Также по специальному запросу может быть выведена (для администрации гостиницы/кафе) вся информация о забронированных на неделю номерах/столиках. В программе необходимо определить и использовать внутреннее представление занятости гостиницы/кафе и всех произведенных бронирований на рассматриваемую неделю. Поисковики Поисковик товаров В нескольких “базах данных” хранятся сведения об одном виде товара, продаваемого компаниями (это могут быть квартиры, или автомобили, или телефоны, или подписка на тариф мобильной связи или др. – выбрать конкретный вид товара). Каждая компания имеет свою базу, исходно задаваемую текстовым файлом, с записями о товарах (не менее 10 записей). Каждая запись в базе описывает конкретный товар выбранного вида: его цену и другие характеристики (например, для квартиры: метраж, расположение, число комнат и др.), не менее 5 различных характеристик. 6 Требуется реализовать программу, выполняющую по запросу пользователя поиск товара по нескольким (3-5) базам компаний. Поисковый запрос может включать только часть характеристик искомого товара, но задавать ограничения по цене и указание конкретной компании. Программа-поисковик находит все подходящие запросу товары и выводит данные о них в виде, удобном для сравнения, с указанием продающей компании. Запрос может быть повторен с уточнением или изменением ряда характеристик товара. При выводе цены товара может быть произведен ее перерасчет с учетом бонусных баллов, которые пользователь может иметь в ряде компаний. Программа-поисковик в начале своей работы получает на вход (в командной строке или интерактивно): – имена текстовых файлов с описаниями баз компаний, в которых будет производиться поиск; – имя файла с данными о бонусных баллах пользователя. После считывания входной информации программа обрабатывает поисковые запросы пользователя, задаваемые интерактивно. В своей работе поисковик опирается на внутреннее представление баз рассматриваемых компаний, при их загрузке во внутреннее представление должны выявляться и диагностироваться ошибки установленного формата данных. При обработке запроса пользователя также необходимо проверять на корректность введенные данные, выдавая сообщения об ошибках и предоставляя подсказки (например, какие значения могут быть у данной характеристики товара и в каком формате их вводить). Агрегатор авиарейсов Реализовать программу для интерактивного поиска дешевого/удобного варианта перелета, по базам рейсов нескольких авиакомпаний. База рейсов каждой компании, исходно задаваемая текстовым файлом, содержит следующие данные о перелётах: ? номер рейса (включает код авиакомпании); ? аэропорт и город вылета и аэропорт и город прилёта; ? время вылета и прилёта; ? недельное расписание (по каким дням недели осуществляется перелёт); ? стоимость перелёта (можно рассмотреть несколько тарифов); ? количество оставшихся билетов на рейс (с учетом тарифа) на ближайшие 1-2 недели. Исходный поисковый запрос пользователя включает: город вылета, город назначения, дату вылета, опционально может быть задано требование только прямого рейса (т.е. отсутствие пересадок), ограничение стоимости перелета, количество билетов на перелет. Программа- агрегатор находит все варианты перелёта (с учетом всех баз ), в том числе с пересадками (если они допускаются, но не более трех пересадок) и выдаёт результаты поиска в виде, удобном для просмотра и сравнения. Найденные варианты перелета должны включать самый дешёвый перелёт, самый быстрый перелёт, варианты без пересадки (если таковые есть) и далее все остальные. Итоговая стоимость для перелета с пересадками суммирует стоимости отдельных участков полета и учитывает необходимое число билетов. Возможен пересчёт стоимости такого перелета (удешевление) , если стыковочные рейсы выполняются одной авиакомпанией (менее удобный, но дешёвый вариант). Поисковый запрос может быть повторен с уточнением или изменением ряда параметров перелета. Более сложный вариант запроса может включать фильтры-ограничения на число пересадок, конкретную авиакомпанию, день вылета, желаемый тариф и т.п. В своей работе агрегатор опирается на внутреннее представление баз рейсов авиакомпаний. При обработке запроса пользователя необходимо выявлять возможные ошибки (например, указание города, в который нет рейсов и т.п.). 7 Kanban-доска Kanban-доска – инструмент для визуализации рабочего процесса в ходе выполнения задач проекта. Самые простые доски состоят из трех колонок: «сделать» (To Do), «в процессе» (In Progress) и «сделано» (Done). Каждая колонка заполняется карточками выполняемых задач с их описанием. Для новой задачи после создания ее карточки она помещается в самую левую колонку. По мере работы над задачей ее статус меняется и пользователь доски обновляет ее статус, перемещая ее карточку из одной колонки в другую. Карточка состоит из идентификатора (обычно числового) задачи, её заголовка и текстового описания. Дополнительными характеристиками/атрибутами задачи могут быть: o дата дедлайна ее исполнения; o тип задачи из определённого множества (баг/фича/вопрос/тестирование и т.п.); o произвольные текстовые метки/теги (обычно указывают часть программной системы, к которой относится задача: backend, frontend, tests, integration, ...). У задачи может быть назначен исполнитель из заранее определённого списка пользователей. Требуется реализовать визуализацию Kanban-доски, с предоставлением пользователю графического интерфейса для: ? создания новых задач, а также изменения и удаления существующих; ? переноса задачи между колонками, с возможным изменением ответственного за задачу (из заранее определённого списка пользователей). Головоломка-игра Реализовать с использованием графического интерфейса одну из игр-головоломок для ее решения одним игроком: Чайнворд, Wordle, Судоку. Чайнворд – это Линейный кроссворд, т.е. разновидность кроссворда, где слова образуют линию/цепочку, в которой каждое следующее слово начинается с последней буквы предыдущего слова. Игроку задается цепочка пустых клеток, в которую надо вписать слова по их описанию. Игровая программа должна загружать головоломку из текстового файла и выполнять ее визуализацию: ? показ пустых клеток для букв цепочки слов (пустой цепочки), возможны варианты: в виде прямой линии, спирали, змейкой, в виде расположенных цепочкой квадратов или др. способом; ? занесение в ячейки-точки пересечения слов номеров слов (в списке их описаний); ? показ нумерованного списка с описаниями значений слов. Следует предусмотреть для загрузки несколько конкретных головоломок (не менее 5), которые выбираются случайно или согласно сложности головоломки (которая может зависеть, например, от числа слов в цепочке). Можно реализовать выбор пользователем варианта расположения цепочки слов на экране при ее загрузке из файла. В ходе решения головоломки игровая программа может: o делать подсказки букв; o показывать верно угаданные слова; o проверять правильность решения после ввода очередного слова или же после решения всей головоломки. Wordle – это игра, где нужно угадать слово из пяти букв за шесть попыток. В начале игры необходимо вписать любое слово в верхний ряд игрового поля, представляющего собой 6 рядов по 5 пустых ячеек в каждом. Если хотя бы одна буква в этом слове соответствует загаданному, то она подсветится зелёным, когда стоит в нужном месте, и жёлтым, когда стоит не на месте. Если все ячейки вашего слова остаются серыми, значит, в искомом слове вообще нет этих букв. Аналогичным образом подсвечиваются буквы на экранной клавиатуре, расположенной внизу и используемой для ввода букв. Версия на английском и на русском. 8 Игровая программа должна осуществлять загрузку словаря загадываемых слов из входного текстового файла. При старте очередной игры загадываемое слово должно выбираться из этого словаря произвольным образом, по окончании игры выдается сообщение об успехе или же показывается загаданное слово. Игровая программа также ведет подсчет доли удачно отгаданных слов. Судоку – головоломка, в которой игровое поле представляет собой квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Всё игровое поле состоит из 81 клетки, и в начале игры в некоторых клетках уже стоят числа (от 1 до 9). От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз. Правильно составленная головоломка имеет только одно решение. Сложность головоломки зависит не от количества изначально заполненных клеток, а от методов, которые необходимо применить для решения. Самые простые головоломки можно решить, если на каждом шаге есть хотя бы одна клетка, куда подходит только одно число. Игровая программа должна загружать головоломку из файла и выполнять визуализацию игрового поля и заполненных клеток. Следует предусмотреть для загрузки несколько конкретных головоломок (не менее 5), которые выбираются случайно или согласно запрошенной/установленной сложности. В ходе решения головоломки игровая программа позволяет вводить цифры в клетки квадрата, и при этом может: ? проверять правильность ввода очередной цифры; ? визуально выделять правильно заполненные фрагменты поля; ? делать подсказки (например, показать, какие цифры можно поставить в данную клетку); ? запускать автоматический решатель головоломки. Автоматическое решение головоломки может быть реализовано несколькими способами, используя стратегии, моделирующие решение человеком, и последовательно пробуя эти стратегии, начиная с самой простой. Графическая игра Реализовать с использованием графического интерфейса одну из следующих игр для одного игрока: тетрис, змейка, арканоид или др. Игровая программа должна генерировать картину игры, визуализировать картину и движущие объекты, отслеживать реакции пользователя-игрока и не должна допускать его действий, не допустимых по правилам игры. Также необходимо определять момент завершения игры/сессии и демонстрировать пользователю-игроку результат (для нескольких сессий игры – общий счет). Возможна реализация пользовательских уровней игры (с пунктом меню для выбора уровня), а также ограничение прохождения уровня по времени. Игровая программа для 2 игроков Реализовать одну из настольных игр, например: реверси, шашки, шахматы, нарды, го. Предполагается применение методов ИИ для моделирования игрока-противника. Игровая программа должна: ? визуализировать игровое поле и объекты-фигуры на нем; ? предоставлять возможность игры в режиме «человек против человека»; ? не допускать недопустимых по правилам игры ходов игроков; ? показывать возможные ходы для выбранной фигуры; ? определять момент победы или ничьей и демонстрировать игрокам результат. Моделирование игрока-противника (расчет его очередного хода) может быть реализовано на основе методов искусственного интеллекта: для таких игр применяется Альфа-бета-процедура или более простая минимаксная процедур