проФорт

Форт и всё такое

Python Challenge 0-5

By exs. Saturday, March 17, 2007 12:00:00 PM

,

Решение The Python Challenge на Форте, а именно с использованием SPF 4.18 для Windows.

Задачки простые, но затрагивают много разных практических аспектов, как то: http, картинки, рисование, архивы, итп. Для решения надо использовать библиотеки из devel, т.е. получается хорошая иллюстрация существующих наработок для СП-Форта.

Внимание, spoiler! Далее будут приведены решения задачек!

Задания по сути состоят из двух частей : сначала надо понять что надо сделать, а потом собственно написать программулину. Здесь я буду формулировать задание только для второй части, т.е. описанием поиска самого задания в html странице и отгадывания запутанных указаний нагружать читателя не будем smile

Итак, приступим.

Задачка 0

Вычислить 2 в степени 38.

Решение

Соображаем что 238 больше чем 232 поэтому одним CELL'ом не обойдёмся (система 32-битная, CELL = 4 байта). Но 238 меньше чем 264 и поэтому двойных значений хватит.

<span style='color:#808080; '>\ 2**38</span>

<span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>S>D </span><span style='color:#008c00; '>38 </span><span style='color:#008c00; '>0 </span><span style='color:#800000; '>DO</span> D2* <span style='color:#800000; '>LOOP</span><span style='color:#000084; font-weight:bold; '> ; </span><span style='color:#000084; font-weight:bold; '>EXECUTE </span><span style='color:#000084; font-weight:bold; '>D.</span>



Задачка 1

Требуется выполнить простое преобразование над текстом, сдвинуть все латинские символы на 2 вправо в алфавите (моноалфавитная подстановка - простейшая разновидность, известная также как шифр Цезаря). Т.е. a переходит в c, а z в b.

Решение

<span style='color:#808080; '>\ K -> M</span>
<span style='color:#808080; '>\ O -> Q</span>
<span style='color:#808080; '>\ E -> G  </span>

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>BOUNDS </span><span style='color:#000084; '>~ygrek/lib/string.f</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>each</span>
   <span style='color:#000084; font-weight:bold; '>DUP </span><span style='color:#800000; '>[CHAR] </span><span style='color:#0000ff; '>a </span><span style='color:#000084; font-weight:bold; '>< </span><span style='color:#800000; '>IF </span><span style='color:#000084; font-weight:bold; '>EXIT </span><span style='color:#800000; '>THEN</span>
   <span style='color:#000084; font-weight:bold; '>DUP </span><span style='color:#800000; '>[CHAR] </span><span style='color:#0000ff; '>z </span><span style='color:#000084; font-weight:bold; '>> </span><span style='color:#800000; '>IF </span><span style='color:#000084; font-weight:bold; '>EXIT </span><span style='color:#800000; '>THEN</span>
   <span style='color:#800000; '>[CHAR] </span><span style='color:#0000ff; '>a </span><span style='color:#000084; font-weight:bold; '>-</span>
   <span style='color:#008c00; '>2 </span><span style='color:#000084; font-weight:bold; '>+</span>
   <span style='color:#800000; '>[CHAR] </span><span style='color:#0000ff; '>z </span><span style='color:#800000; '>[CHAR] </span><span style='color:#0000ff; '>a </span><span style='color:#000084; font-weight:bold; '>- </span><span style='color:#000084; font-weight:bold; '>1+ </span><span style='color:#000084; font-weight:bold; '>MOD</span>
   <span style='color:#800000; '>[CHAR] </span><span style='color:#0000ff; '>a </span><span style='color:#000084; font-weight:bold; '>+</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>decode</span> BOUNDS <span style='color:#800000; '>DO </span><span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>C@</span> each <span style='color:#000084; font-weight:bold; '>EMIT </span><span style='color:#800000; '>LOOP</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>string </span><span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>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.</span><span style='color:#000084; font-weight:bold; '>"</span><span style='color:#000084; font-weight:bold; '> ;</span>
<span style='color:#000084; font-weight:bold; '>CR</span> string decode

<span style='color:#000084; font-weight:bold; '>CR </span><span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>map</span><span style='color:#000084; font-weight:bold; '>"</span> decode



Задачка 2

Дан текст (смотрите html код страницы с заданием), требуется найти в нём редкие символы.

Решение

Заданный текст выделим в отдельный файл 2.in. Сначала соберём информацию и посмотрим что имеется ввиду под редким. Это делают collect и stats. Видим что редкие встречаются по одному разу. Пользуясь этим критерием - пробегаем текст ещё раз и получаем искомое слово-решение.

<span style='color:#808080; '>\ find rare characters in the mess below: see 2.in</span>

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>FILE </span><span style='color:#000084; '>~ac/lib/str5.f</span>
<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>BOUNDS </span><span style='color:#000084; '>~ygrek/lib/string.f</span>
<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>replace-str- </span><span style='color:#000084; '>~pinka/samples/2005/lib/replace-str.f</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>vector </span><span style='color:#000084; font-weight:bold; '>CREATE </span><span style='color:#000084; font-weight:bold; '>CELLS </span><span style='color:#000084; font-weight:bold; '>ALLOT </span><span style='color:#800000; '>DOES> </span><span style='color:#000084; font-weight:bold; '>SWAP </span><span style='color:#000084; font-weight:bold; '>CELLS </span><span style='color:#000084; font-weight:bold; '>+</span><span style='color:#000084; font-weight:bold; '> ;</span>
<span style='color:#008c00; '>256</span> vector <span style='color:#000084; font-weight:bold; '>chars</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>FILE-TEXT</span>
   FILE<span style='color:#000084; font-weight:bold; '> " </span><span style='color:#0000ff; '>{s}</span><span style='color:#000084; font-weight:bold; '>"</span>
   <span style='color:#000084; font-weight:bold; '>DUP</span><span style='color:#000084; font-weight:bold; '> " </span><span style='color:#0000ff; '>{CRLF}</span><span style='color:#000084; font-weight:bold; '>" </span><span style='color:#000084; font-weight:bold; '>""</span> replace-str-<span style='color:#808080; '> \ get rid of the unnedeed line endings</span>
   STR@<span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>collect</span> 
   <span style='color:#008c00; '>0 </span><span style='color:#000084; font-weight:bold; '>chars </span><span style='color:#008c00; '>256 </span><span style='color:#000084; font-weight:bold; '>CELLS </span><span style='color:#000084; font-weight:bold; '>ERASE</span>
   <span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>2.in</span><span style='color:#000084; font-weight:bold; '>"</span> FILE-TEXT BOUNDS <span style='color:#800000; '>DO </span><span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>C@ </span><span style='color:#000084; font-weight:bold; '>chars</span> 1+! <span style='color:#800000; '>LOOP</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>stats</span> 
   <span style='color:#008c00; '>255 </span><span style='color:#008c00; '>0 </span><span style='color:#800000; '>DO</span> 
    <span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>chars </span><span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#800000; '>IF </span><span style='color:#000084; font-weight:bold; '>CR </span><span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>EMIT </span><span style='color:#008c00; '>2 </span><span style='color:#000084; font-weight:bold; '>SPACES </span><span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>chars </span><span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span> 
   <span style='color:#800000; '>LOOP</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>solve</span> 
   <span style='color:#000084; font-weight:bold; '>CR</span> 
   <span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>2.in</span><span style='color:#000084; font-weight:bold; '>"</span> FILE-TEXT BOUNDS <span style='color:#800000; '>DO</span> 
     <span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>C@ </span><span style='color:#000084; font-weight:bold; '>chars </span><span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>= </span><span style='color:#800000; '>IF </span><span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>C@ </span><span style='color:#000084; font-weight:bold; '>EMIT </span><span style='color:#800000; '>THEN</span> 
   <span style='color:#800000; '>LOOP</span><span style='color:#000084; font-weight:bold; '> ;</span>

collect 
stats
solve



Задачка 3

Опять задан текст, а критерий поиска такой - последовательность из любых трёх заглавных символов, потом один прописной символ, и потом ещё три произвольных заглавных символа.

Решение

Воспользуемся простым конечным автоматом. Переменная counter используется для уменьшения числа состояний с 8 до 2-х. Схема автомата очень простая - путь успеха выделен жирным, при любом несоответствии идёт откат в начальное состояние, т.е. можно было обойтись простым набором IF'ов :



Не забудем удалить переводы строк из исходного текста.

<span style='color:#808080; '>\ One small letter, surrounded by EXACTLY three </span>
<span style='color:#808080; '>\ big bodyguards on each of its sides.</span>

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>FILE </span><span style='color:#000084; '>~ac/lib/str5.f</span>
<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>BOUNDS </span><span style='color:#000084; '>~ygrek/lib/string.f</span>
<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>replace-str- </span><span style='color:#000084; '>~pinka/samples/2005/lib/replace-str.f</span>
<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>состояние </span><span style='color:#000084; '>~profit/lib/chartable.f</span>

состояние s1
состояние s2

<span style='color:#000084; font-weight:bold; '>VARIABLE </span><span style='color:#000084; font-weight:bold; '>counter</span>
<span style='color:#008c00; '>0 </span><span style='color:#000084; font-weight:bold; '>VALUE </span><span style='color:#000084; font-weight:bold; '>ch</span>

s1
все: counter <span style='color:#000084; font-weight:bold; '>0!</span> ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>a </span><span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>z</span> диапазон: counter <span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#008c00; '>3 </span><span style='color:#000084; font-weight:bold; '>=</span> IF символ<span style='color:#800000; '> </span><span style='color:#000084; font-weight:bold; '>TO</span> ch s2 THEN  counter <span style='color:#000084; font-weight:bold; '>0!</span> ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>A </span><span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>Z</span> диапазон: counter 1+! ;

s2
все: counter <span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#008c00; '>3 </span><span style='color:#000084; font-weight:bold; '>=</span> IF ch <span style='color:#000084; font-weight:bold; '>EMIT</span> THEN  counter <span style='color:#000084; font-weight:bold; '>0!</span>  s1 ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>A </span><span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>Z</span> диапазон: counter 1+! ;

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>main</span>
  <span style='color:#008c00; '>1</span><span style='color:#800000; '> </span><span style='color:#000084; font-weight:bold; '>TO</span> размер-символа
  s1
  <span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>3.in</span><span style='color:#000084; font-weight:bold; '>"</span> 
 <span style='color:#808080; '> \ load-file 2DUP S>STR DUP</span>
  FILE<span style='color:#000084; font-weight:bold; '> " </span><span style='color:#0000ff; '>{s}</span><span style='color:#000084; font-weight:bold; '>"</span>
  <span style='color:#000084; font-weight:bold; '>DUP</span><span style='color:#000084; font-weight:bold; '> " </span><span style='color:#0000ff; '>{CRLF}</span><span style='color:#000084; font-weight:bold; '>" </span><span style='color:#000084; font-weight:bold; '>""</span> replace-str- 
  STR@ BOUNDS <span style='color:#800000; '>DO </span><span style='color:#800000; '>I </span><span style='color:#000084; font-weight:bold; '>C@</span> выполнить-один-раз <span style='color:#800000; '>LOOP</span>
  закончить-обработку<span style='color:#000084; font-weight:bold; '> ;</span>

main



Задачка 4

Требуется прокликать по ссылкам, выдирая адрес назначения из полученной на очередном шаге страницы. Воспользуемся словом GET-FILE из библиотеки ~ac/lib/lin/curl/curl.f. Потребуется libcurl (скачать). Положите curl.dll в системный каталог или рядом с spf.exe.

Решение

<span style='color:#808080; '>\ Follow the chain</span>

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>GET-FILE </span><span style='color:#000084; '>~ac/lib/lin/curl/curl.f</span>
<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>/STRING </span><span style='color:#000084; '>lib/include/string.f</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>url</span><span style='color:#808080; '> ( n -- s )</span> 
 <span style='color:#000084; font-weight:bold; '> " </span><span style='color:#0000ff; '>http://www.pythonchallenge.com/pc/def/linkedlist.php?nothing</span><span style='color:#0000ff; '>={n}</span><span style='color:#000084; font-weight:bold; '>"</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>NUMBER</span><span style='color:#808080; '> ( a u -- n -1 | 0 )</span>
  <span style='color:#008c00; '>0 </span><span style='color:#008c00; '>0 </span><span style='color:#000084; font-weight:bold; '>2SWAP </span><span style='color:#000084; font-weight:bold; '>>NUMBER </span><span style='color:#000084; font-weight:bold; '>NIP </span><span style='color:#800000; '>IF </span><span style='color:#000084; font-weight:bold; '>2DROP </span><span style='color:#000084; font-weight:bold; '>FALSE </span><span style='color:#800000; '>ELSE </span><span style='color:#000084; font-weight:bold; '>D>S </span><span style='color:#000084; font-weight:bold; '>TRUE </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> 

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>prompt </span><span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>and the next nothing is </span><span style='color:#000084; font-weight:bold; '>"</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>parse</span><span style='color:#808080; '> ( a u -- n )</span>
   prompt <span style='color:#000084; font-weight:bold; '>SEARCH </span><span style='color:#000084; font-weight:bold; '>0= </span><span style='color:#800000; '>IF </span><span style='color:#000084; font-weight:bold; '>2DROP </span><span style='color:#008c00; '>0 </span><span style='color:#000084; font-weight:bold; '>EXIT </span><span style='color:#800000; '>THEN</span>
   prompt <span style='color:#000084; font-weight:bold; '>NIP</span> /STRING
   NUMBER <span style='color:#000084; font-weight:bold; '>0= </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>0 </span><span style='color:#000084; font-weight:bold; '>EXIT </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>next</span> 
   <span style='color:#800000; '>BEGIN</span>
    <span style='color:#000084; font-weight:bold; '>DUP </span><span style='color:#000084; font-weight:bold; '>CR </span><span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>GO TO </span><span style='color:#000084; font-weight:bold; '>" </span><span style='color:#000084; font-weight:bold; '>.</span>
    url
    <span style='color:#000084; font-weight:bold; '>>R </span><span style='color:#000084; font-weight:bold; '>R@</span> STR@ GET-FILE <span style='color:#000084; font-weight:bold; '>R></span> STRFREE
    <span style='color:#000084; font-weight:bold; '>>R</span>
    <span style='color:#000084; font-weight:bold; '>R@</span> STR@ 
    <span style='color:#000084; font-weight:bold; '>2DUP </span><span style='color:#000084; font-weight:bold; '>CR </span><span style='color:#000084; font-weight:bold; '>TYPE</span> 
    <span style='color:#000084; font-weight:bold; '>parse</span>
    <span style='color:#000084; font-weight:bold; '>R></span> STRFREE
    <span style='color:#000084; font-weight:bold; '>DUP</span>
    <span style='color:#000084; font-weight:bold; '>0=</span>
   <span style='color:#800000; '>UNTIL</span>
   <span style='color:#000084; font-weight:bold; '>DROP</span> 
   <span style='color:#000084; font-weight:bold; '>CR </span><span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>STOP</span><span style='color:#000084; font-weight:bold; '>"</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>go </span><span style='color:#008c00; '>12345</span> next<span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#808080; '>\ spf 4.f 12345 next >> 4.log</span>



Задачка 5

Для решения этой задачи требуется PICKLE - модуль сериализации в Питоне Реализовывать его функционал - это слишком - пришлось подсмотреть ответ. google it :-(

FAQ:
Do I have to use Python to solve the riddles?
Most of the riddles can be solved with any language.
Currently, only riddles 5 and 23 require Python.
The hints in all riddles are geared towards Python programmers.


Продолжение следует smile

Эвересты и Марианские жёлобы ФортаСтроки в Форте и в СПФ в частности

How to use Quote function:

  1. Select some text
  2. Click on the Quote link

Write a comment

Comment
(BBcode and HTML is turned off for anonymous user comments.)

If you can't read the words, press the small reload icon.


Smilies