Perl-лом по расписанию! Google-календарь заполняй!

Смеркалось. Улицы заполнялись свежим вечерним воздухом.
-- Что мы будем делать сегодня, брейн?
-- Как и всегда, в первое сентября, - парсить расписание с tt.kubstu.ru!

Первым делом сливаем жертву на эвм, ну например эту. Самый простой способ преобразовать текст в текст -- с помощью perl и regex. Поэтому сегодня мы будем точить навыки perl-погамистра. Расчехляем perl и приветствуем Larry Wall-a:

$ perl -v

This is perl, v5.10.1 (*) built for i686-cygwin-thread-multi-64int
(with 13 registered patches, see perl -V for more detail)

Copyright 1987-2009, Larry Wall

Perl под windows можно найти в cygwin (это такой tools set из мира linux портированный под windows).

Парсить будем по-колхозному -- регулярками. Скажу вам по секрету, что я жутко ленив и парсер написал только ко второму семестру 4-го курса, примерно тогда у меня завелся телефон на Android. Каждый семестр вручную заполнять календарь как-то не серьезно, а иметь расписание в кармане хочется.

Импортированное расписание

Если вам просто нужно заставить скрипт работать, то достаточно настроить параметры в разделе констант в самом начале скрипта.

#!/usr/bin/perl
#
# export-csv.pl
#
#  Created on: 06.02.2012
#     Project: ExportScheduleToCSV
#     License: GPLv3
#
#  Copyright (c) 2012 brunql
#

use constant {
        INPUT_FILENAME          => "5.1.08.K.PO1.htm",
        
        FIRST_STUDY_DAY         => 3,
        FIRST_STUDY_MONTH       => 9, 
        FIRST_STUDY_YEAR        => 12,
        
        LAST_STUDY_MONTH        => 12
};

Небольшое описание работы скрипта. Начнем с открытия html-файла для чтения, а выхлоп в виде файлов с расписанием лекций и расписанием занятий -- для записи.

open(IMPORT, INPUT_FILENAME) || die("Open import file failed");

open(EXPORT_LECTURES, ">schedule_lectures.csv") || die("Open export file failed");
open(EXPORT_PRACTICE, ">schedule_practice.csv") || die("Open export file failed");

Согласно документации Google-календаря записываем заголовок колонок в CSV-формате:

$Titles = "Subject,Start Date,Start Time,End Date,End Time," . 
          "All Day Event,Description,Location,Private\n";

print EXPORT_LECTURES $Titles;
print EXPORT_PRACTICE $Titles;

Начинаем построчно читать входной файл и проверять каждую строку на соответствие первой регулярке, которая отвечает за дни недели:

while (<IMPORT>)
{
    if (/   \<th colspan="3" class="dow"\>&nbsp;\<\/th\>
            \<th colspan="7" class="dow( cb)?"\>(.+)\<\/th\>/x) {
        $DayOfWeek++;
        print "\nDay of week:$DayOfWeek\n";
    }

Промахнулись? Тогда поищем следы лекций и практических занятий в текущей строке:

elsif (/
    \<tr(\ class="bg")?\>
    \<td\>(?<N>\d)\<\/td\>
    \<td\ class="terms"\>
      (?<StartTime>\d\d:\d\d)\<br(\ \/)?\>(?<EndTime>\d\d:\d\d)
    \<\/td\>
    \<td\ class="bt_(?<FirstTypeIndex>\d)"\>
      (  \<span\ class="_p"\>(?<FirstType>.+)\<\/span\>
         \<span\ class="_s"\>&nbsp;\<\/span\>
      |  &nbsp; )
    \<\/td\>
    \<td\>(?<FirstSubject>.+?)
      (\<div\ class="note"\>(?<FirstSubjectNote>\(.+\))\<\/div\>)?
    \<\/td\>
    \<td(\ class=".")?\>(?<FirstLocation>.+)\<\/td\>
    \<td\>(?<FirstTeacher>.+)\<\/td\>
    \<td\ class="bt_(?<SecondTypeIndex>\d)"\>
      (  \<span\ class="_p"\>(?<SecondType>.+)\<\/span\>
         \<span\ class="_s"\>&nbsp;\<\/span\>
      |  &nbsp; )
    \<\/td\>
    \<td\>(?<SecondSubject>.+?)
      (\<div\ class="note"\>(?<SecondSubjectNote>\(.+\))\<\/div\>)?
    \<\/td\>
    \<td(\ class=".")?\>(?<SecondLocation>.+)\<\/td\>
    \<td\>(?<SecondTeacher>.+)\<\/td\>\<\/tr\>
/x)

С помощью этой кучи слабо читаемых символов мы заполняем хэш %+ нашими парами занятий с четной и нечетной недели. Конструкции вида (?<Name>Regex) превращаются в именованный массив %+{Name} = Regex, который для наглядности сразу переименовываем в %Lesson.

Теперь нам нужно избавиться от некоторых лишних символов в найденных текстах:

    %Lesson = %+;
    foreach $key (keys %Lesson) {
        $Lesson{$key} =~ s/ //;
        $Lesson{$key} =~ s/\,/\ /;
        $Lesson{$key} =~ s/\s+/ /g;
    }

И заполнить календарь до конца учебного семестра, просто пробегаемся по неделям, заполняя сначала первую, а потом вторую:

    while ($DateMonth <= LAST_STUDY_MONTH) 
        {
            $Date = GetDateDayOfWeek();        

            if ($FirstSubject && $DateMonth <= LAST_STUDY_MONTH && 
                  $WeekCount < $FirstSubjectWeeks) {
                $line = "$N. $FirstLocation $FirstSubject $FirstType " . 
                        "$FirstSubjectNote,$Date,$StartTime,$Date,$EndTime," . 
                        "False,$FirstTeacher,$FirstLocation,Private\n";
                if ($FirstTypeIndex == 1) {
                    print EXPORT_LECTURES $line;
                } else {
                    print EXPORT_PRACTICE $line;
                }
            }

            AddWeek();
            $Date = GetDateDayOfWeek();
        
            if ($SecondSubject && $DateMonth <= LAST_STUDY_MONTH && 
                  $WeekCount < $SecondSubjectWeeks) {
                $line = "$N. $SecondLocation $SecondSubject $SecondType " . 
                        "$SecondSubjectNote,$Date,$StartTime,$Date,$EndTime," . 
                        "False,$FirstTeacher,$SecondLocation,Private\n";
                if ($SecondTypeIndex == 1) {
                    print EXPORT_LECTURES $line;
                } else {
                    print EXPORT_PRACTICE $line;
                }
            }

            AddWeek();
        }

Некоторые части скрипта опущены, полный исходный код можно найти на bitbucket.org.

Полученные файлы *.csv импортируются в календарь с помощью менюшки "Другие календари".

Удачи!

Фибоначчи на Haskell, во имя бобра!

Последнее время меня дико прет от функциональных языков программирования. Началось с Visual Prolog, который как известно поддерживает несколько парадигм программирования - функциональную, логическую и процедурную. Он очень удобен для декларативного описания задач и решения их "в лоб" за счет встроенного в язык перебора с возвратами (backtracking). Но сегодня не о нем, итак Haskell.

Haskell - кристально чистый функциональный язык программирования. Лямбда-функции (lambda), сопоставление с образцом (pattern matching), ленивые вычисления (lazy evaluation), каррирование (currying), длинная арифметика (arbitrary-precision integers), строгая, статическая типизация с автоматическим выводом типов - вот лишь несколько самых броских фишек языка.

Лаконичность синтаксиса программ на Haskell просто потрясающая!

К примеру данный код производит вычисление N-го числа последовательности Фибоначчи:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Шикарно, не правда ли?

Время работы простого рекурсивного алгоритма (согласно SICP)

Потребление памяти простого рекурсивного алгоритма

Он конечно выполняет свою функцию, но порождает древовидно-рекурсивный процесс (пара новых веток на каждом вызове), что сильно сказывается на памяти и производительности. 

Простая итеративная версия данного алгоритма: 

fib_iter n = f n 0 1 0
    where f n k a b 
        | n == k    = a
        | otherwise = f n (k + 1) (a + b) a

Время работы итеративной версии

Потребление памяти итеративной версии алгоритма

Выглядит она конечно менее очевидно, но если заметить, что в a и b на каждом шаге хранится текущее и следующее число последовательности, а завершается хвостовая рекурсия когда счетчик k дойдет до искомого n, то все становится понятно.

Ну и на закуску, хитрая итеративная версия вычисления чисел Фибоначчи (подробнее в упражнении 1.19 из SICP):

fib_fast_iter n = f 1 0 0 1 n
    where f a b p q n
        | n == 0         = b
        | n `mod` 2 == 0 = f a b (q^2 + p^2) (q^2 + 2 * p * q) (n `div` 2)
        | otherwise      = f (b * q + a * q + a * p) (b * p + a * q) p q (n - 1)

Время работы быстрой итеративной версии

Потребление памяти быстрой итеративной версии алгоритма 

В следующий раз расскажу, как просто тестировать код на Haskell.