fp.2012-05

fp.2012-05.bash

#!/bin/bash

# данный скрипт является решением задачи майского (2012) конкурса по
# функциональному программированию
# http://users.livejournal.com/_darkus_/650933.html
#
# fp.2012-05.bash (c) 2012 alexander barakin aka sash-kan <al@barak.in>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

# имя файла с задачами; его можно скачать по ссылке, выложенной организатором
# конкурса: http://www.onlinedisk.ru/file/869603/
# либо отсюда (без ввода captcha): http://barak.in/dl/FPC_May2012_tsk.zip
# файл нужно положить в тот же каталог, из которого будет запускаться данный
# скрипт
f=FPC_May2012_tsk.zip

# набор мета-шаблонов, их структура:
# <знак><пробел>/<шаблон>/
# или
# <знак><пробел>/<шаблон>/<пробел>/<уточняющий шаблон>/!
# где <знак> - это знак арифметической операции, которую надо будет применить к
# числам, содержащимся в задаче, подпадающей под <шаблон>·
# <уточняющий шаблон> применяется как логическое отрицание (подробнее - ниже)·
p="* / по [0-9]+ .* ((всего|вместе)\?|на всех?) /
* / каждой .* всего\? $/
* / (каждый|по) .* Сколько всего /
* /кажд.*вместе/
/ /( поровну|колько .* кажд)/
/ / Сколько стоит один/
+ / (Сколько всего \w+ \w+ на|Сколько всего (у|на|\w+\?)) /
+ / (Сколько вместе|в об[ое]их|через|за два) /
+ / (Сколько стало|На скольких всего) /
+ / Сколько \w+ вместе\? / / по [0-9]/!
+ / Сколько (\w+ )?\w+ всего\?/ / (на каждой|по [0-9]+) /!
- / (которых [0-9]+ было .* Сколько|меньше\.|лишних|первоначально\?|назад\?|Из них) /
- /\. Всего было [0-9]/
- /Сколько.* (продолж|остал|не принялось|завяло)/"

# сначала распаковывается файл с задачами
unzip -p $f | \
# с помощью gnu tr окончания строк приводятся к принятым в операционной системе
# gnu:
tr -d '\r' | \
# а вот это - "самый главный" вызов gnu sed·
# в качестве параметра (sed -f <(<программа, формирующая команды>)) он
# принимает сформированные из мета-шаблонов команды, написанные на его
# собственном языке·
# программой, формирующей команды, также является gnu sed, о процессе
# формировании написано ниже·
# в качестве входных данных этот вызов gnu sed принимает эстафету от gnu tr и
# отправляет обработанные данные дальше, финальному вызову gnu sed (о нём см.
# ниже)·
# этот вызов gnu sed и производит самую главную работу: выполняя команды,
# переданные ему с помощью параметра "-f", он "вычисляет", какую же
# арифметическую операцию следует применить к каждой из ста тысяч задач,
# получаемых им в виде набора строк на stdin·
# единственное производимое им действие - добавление в начало строки этого
# самого "вычисленного" знака арифметической операции·
sed -r -f <(\
# на stdout выводятся мета-шаблоны (они содержатся в переменной "p")
echo "$p" | \
# и преобразовываются с помощью gnu sed к командам, понятным самому gnu sed·
# из каждого мета-шаблона получается команда вида:
# /<шаблон>/{s/^/<знак> /}
# или, при наличии в мета-шаблоне уточняющего шаблона:
# /<шаблон>/{/<уточняющий шаблон>/!S/^/<Знак> /}
# суть первого вариант команды:
# при совпадении обрабатываемой строки с <шаблон> выполняется команда "s"
# (которая, собственно, и производит нужную нам замену)
# суть второго варианта команды:
# команда "s" выполняется лишь при совпадении строки с <шаблон> и
# _не_совпадении с <уточняющий шаблон> (обратите внимание на символ "!" между
# "/<уточняющий шаблон>/" и командой "s", именно он наделяет отрицающей логикой
# <уточнающий шаблон>)·
# синтаксис команды "s":
# sXшаблонXзаменаX
# здесь "X" - произвольный символ-разделитель (главное, чтобы у одной команды
# "s" он был один и тот же);
# во всём скрипте вы можете встретить целых три варианта употребления этого
# символа-разделителя: "/", "!" и "#"·
sed -r 's#^(.) (/[^/]+/)( (.*))?#\2{\4s!^!\1 !}#') |\
# здесь из строк извлекаются: первый символ (знак арифметической операции) и
# два числа·
# из этих трёх элементов формируется микропрограмма для gnu bc вида:
# if(<число1> > <число2>) <число1><знак><число2> else <число2><знак><число1> 
# подчиняясь такой микропрограмме, gnu bc подставит первое число в качестве
# первого операнда в требующейся нам арифметической операции если первое число
# больше второго, и наоборот (вторым), есле меньше·
sed -r 's/^(.).* ([0-9]+)[ ,].* ([0-9]+)[ .].*$/if(\2>\3) \2\1\3 else \3\1\2/' |\
# теперь с помощью gnu bc производим необходимые вычисления·
# строки, получаемые gnu bc, имеют вид (это вторая задача в данном случае,
# звучащая как "На море плавало 89 орлов и несколько журавлей. Всего было 184
# птиц. Сколько птиц второго вида плавало на водоёме?")
# "if(89>184) 89-184 else 184-89"
# выполнив эту микропрограмму, gnu bc выведет в данной строке "95"
bc | \
# конечный результат упаковывается с помощью gnu gzip, и записывается в файл
# fp.2012-05.result.gz
gzip > fp.2012-05.result.gz

# дополнительное чтение:
# 1. Джеффри Фридл, «регулярные выражения»
# 2. info sed (это команда, выводящая документацию по gnu sed)
# 3. info bc (это команда, выводящая документацию по gnu bc)
# 4. info tr; info gzip, man unzip, man bash