Dmitry Astapov (_adept_) wrote,
Dmitry Astapov
_adept_

Category:

PythonChallenge.com in Haskell, уровни 0-4

По чьей-то ссылке наткнулся на очередной сайт с загадками вида "вычисли 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) питоновский список), и я пока обломался их решать.
Tags: haskell, pythonchallenge, квесты
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 40 comments