?

Log in

No account? Create an account
dump -0f - /dev/mind
Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов
PythonChallenge.com in Haskell, уровни 0-4 
2nd-Mar-2007 08:40 am
По чьей-то ссылке наткнулся на очередной сайт с загадками вида "вычисли URL следующей страницы". При ближайшем рассмотрении оказалось, что головоломка рассчитана на программистов и предполагает использование Python-а.

Just for fun я попробовал сделать ее на Haskell. И вот что получилось...

(Помимо нижеследующего текста у меня также сохранился screencast самого процесса решения, правда - с английскими комментариями. Любопытствующие кликают сюда. Как-нибудь на днях напишу о том, как был сделан screencast - оказалось, что процесс далеко не такой тривиальный, как я думал)

module Main where

import Data.Char
import Data.List
import Network.HTTP
import Network.URI
import Network.Browser
import Data.Maybe

main = print "Doing pythonchallenge.com in Haskell :)"

---------------
-- Уровень 0 --
ch0 = print $ 2^38

-- Результат: 
-- *Main> ch1
-- 274877906944

---------------
-- Уровень 1 --

ch1_text = "g fmnc wms bgblr rpylqjyrc gr zw fylb. 
  rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmle.
  sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj."

-- Судя по картинке, прилагающейся к тексту задания, это - простой циклический подстановочный шифр с шагом 2.
-- Проще говоря, каждая буква сдвинута по алфавиту на две позиции назад.
-- Будем декодировать при помощи словаря подстановок:
dict = zip ['a'..'z'] (drop 2 $ cycle ['a'..'z'])

-- Получаем список пар:
-- *Main> take 10 dict
-- [('a','c'),('b','d'),('c','e'),('d','f'),('e','g'),('f','h'),('g','i'),('h','j'),('i','k'),('j','l')]
-- *Main> lookup 'o' dict
-- Just 'q'
-- *Main> lookup ' ' dict
-- Nothing

-- В исходном тексте есть не только буквы, но и точки-запятые, пробелы и т.п. Их декодировать не надо.
-- Сделаем свой аналог 'lookup' для этих целей:
translate c = case lookup c dict of
                Nothing -> c
                Just t  -> t

-- Собственно, результат:
ch1 = map translate ch1_text

-- *Main> ch1
-- "i hope you didnt translate it by hand. thats what computers are for. doing it in by hand is inefficient and 
--  that's why this text is so long. using string.maketrans() is recommended. now apply on the url." 
-- *Main> map translate "map"
-- "ocr"

---------------
-- Уровень 2 --

-- В длинном-длинном тексте, который можно увидеть, сделав 'View page source', надо найти "редкие буквы". 
-- Поначалу я думал, что надо посчитать, какие символы входят в текст реже всего и вывести их, но похоже,
-- что задачка значительно проще: буквы (а не спец. символы) в этом тексте действительно выстречаются крайне
-- редко. И надо найти и вывести именно их. 
ch2 = do
 txt <- readFile "ch2_text.in"
 return $ filter isAlpha txt

-- *Main> ch2
-- "equality"

---------------
-- Уровень 3 --
-- В длинном-длинном тексте необходимо найти все прописные буквы, окруженные с двух сторон ровно тремя строчными.
-- Очевидно, что это задачка на использование regexp-ов. Исключительно хохмы ради я решил ее без регекспов :)

-- Для начала разбиваем текст на последовательности, состоящие из букв одного регистра:
sameRegister x y = isLower x == isLower y
tokenize = groupBy sameRegister

-- *Main> tokenize "AAAAbbbCCdEfffGhIjjj"
-- ["AAAA","bbb","CC","d","E","fff","G","h","I","jjj"]

-- Разбиваем поток токенов на тройки:
triplicate lst = zip3 lst (drop 1 lst) (drop 2 lst)

-- *Main> triplicate $ tokenize "AAAAbbbCCdE"
-- [("AAAA","bbb","CC"),("bbb","CC","d"),("CC","d","E")]

-- Эта функция проверяет, попадает ли конкретная тройка под условия задачи.
guardedLetter (tok1, tok2, tok3) = 
  and [ all isUpper tok1, length tok1 == 3
      , all isUpper tok3, length tok3 == 3
      , all isLower tok2, length tok2 == 1]

-- *Main> guardedLetter ("AAA","b","CCC")
-- True
-- *Main> guardedLetter ("aaa","B","ccc")
-- False

-- Функция-helper, извлекающая средний элемент из тройки
extractLetter (_,l,_) = l

-- Складываем все вместе:
ch3 =
  do txt <- readFile "ch3_text.in"
     return $ concatMap extractLetter $ filter guardedLetter $ triplicate $ tokenize txt

-- *Main> ch3
-- "linkedlist"

---------------
-- Уровень 4 --

-- Дан URL, оканчивающийся числом. Страница, адресованная данным URL-ом, содержит в теле другое число.
-- Подставив это число в URL, получаем адрес следующей страницы такой же структуры и т.п. 
-- Задача - пройти эту цепочку до конца и не задолбаться :)

-- Я до сих пор почти не пользовался модулями Network.*, поэтому наверняка мой код можно переписать в 5 раз короче :)

-- Эта функция вытягивает страницу с указаным адресом и возращает ее тело в виде строки.
slurpPage address = 
  do (Right result) <- simpleHTTP $ defaultGETRequest $ fromJust $ parseURI address
     return $ rspBody result

-- Берем число-параметр, вытаскиваем соотв. страницу, вынимаем из нее ключ, возвращаем его.
getNextKey key =
  do let base = "http://www.pythonchallenge.com/pc/def/linkedlist.php?nothing="
     txt <- slurpPage $ base ++ key
     return $ last $ words txt

-- Берем начальное число-параметр, идем по цепочке страниц до тех пор, пока можем вытаскивать
-- из тела страницы следующее число.
loopTheLoop key =
  do next_k <- getNextKey key
     case (all isDigit next_k) of
          True -> do putStrLn (key ++ " -> " ++ next_k)
                     loopTheLoop next_k
          False -> return next_k

-- Результат: "peak"





Дальше задачи становится гораздо более python-specific (например, прохождение следующего уровня начинается с того, что нужно десериализовать из файла (при помощи модуля pickle) питоновский список), и я пока обломался их решать.
Comments 
2nd-Mar-2007 06:52 am (UTC)
Красиво.

Начинаю думать о том, что надо бы изучить Haskell...
2nd-Mar-2007 07:39 am (UTC)
Первое замечание (текст пока не читал): ссылку поправь.
2nd-Mar-2007 01:02 pm (UTC)
Интересно, сколько еще я буду наступать на эти грабли? :)
(Deleted comment)
2nd-Mar-2007 02:47 pm (UTC) - Re: список
Это то, что де-сериализуется в пятом задании, так?
2nd-Mar-2007 08:24 am (UTC)
ссылка "очередной сайт" битая (вместо href="pythonchallenge.com" лучше бы href="http://pythonchallenge.com", а то firefox бунтует)
2nd-Mar-2007 08:46 am (UTC)
сделал всё то же на перле :-) прикольно
не могу вдуплить, что делать дальше с leak help :-/
(Deleted comment)
2nd-Mar-2007 08:50 am (UTC)
Замечательная иллюстрация того факта, что каждой задаче нужен свой инструмент.
Уровень 1: , выскакивает калькулятор, 2^38
Уровень 2: Хаскель, однострочник с явным разбором двух левых случаев (лень было оптимизировать): \x -> if x `elem` ['a'..'x'] then succ $ succ x else if x == 'y' then 'a' else if x == 'z' then 'b' else x
Уровень 3: Загружаем текст в emacs, регэкспом выкидываем всё, что не буква.
Уровень 4: Загружаем текст в emacs, регэкспом помечаем тегами всё, что удовлетворяет критерию, другим регэкспом удаляем всё, что вне тегов, третьим - заменяем каждое вхождение на соотв. букву.
Уровень 5: bash:
a=12345; while a=`wget -q -O - http://pythonchallenge.com/pc/def/linkedlist.php?nothing=$a | grep -o '[0-9]+'`; do echo $a; done

Пояснения (чтобы в man не заглядывать): "-q" - подавить вывод диагностических сообщений (нафиг они мне), "-O -" - выдавать документы на стандартный вывод, "-o" - выводить только проматчившуюся часть. В двух случаях облома меняем в этой строке начальное значение a и продолжаем. В конце - смотрим последнюю найденную страницу в браузере.
2nd-Mar-2007 08:52 am (UTC)
Блин, теги съелись: Уровень 1 - <NumLock>, выскакивает калькулятор, 2^38 <Enter>
(Deleted comment)
(Deleted comment)
(Deleted comment)
2nd-Mar-2007 09:14 am (UTC)
sameRegister x y = isLower x == isLower y
tokenize = groupBy sameRegister
2nd-Mar-2007 01:58 pm (UTC)
Точно, туплю. Спасибо :)
2nd-Mar-2007 12:11 pm (UTC)
А screencast почему то отвратительного качества...
2nd-Mar-2007 01:58 pm (UTC)
Который во flash-е, или который "download original file"?
17th-May-2007 06:28 pm (UTC)
Так это… как screencast'ы-то делать?
This page was loaded May 25th 2019, 6:03 pm GMT.