# оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 04:27
Оценка: 17 (4) +2
просьба ногами не бить, а если и бить, то не больно. и не всем сразу, а по очереди.

знаю, что вы мы ищем тестовые задания, которые можно написать минут за полчаса и которые определяют профпригодность кандидата, причем покрывают широкий профиль общих вопросов и при этом не приводятся в качестве примеров наглядной агитации в каждом втором букваре.

вот тут жизнь подкинула интересную тему, сносящую крышу и отсутствующую в гугле. захотелось найти средство для замены пробелов в скриптах на питоне на символы табуляции. вопрос задавался 100500 раз, но каждый раз на него давались ответы в стиле "emacs это не только ценный мех" или "в vim'е это делается одним жестом руки" и предлагалось заменять четыре (!) пробела одним символом табуляции.

что за бред?! в питоне не настолько жестко специфицированная система отступов. не обязательно четыре. если текущий уровень вложенности имеет M отступов, то следующий уровень вложенности N, где M < N, а вот для выхода из N нужно отступить на M пробелов. кстати, в руководстве на питон это доходчиво описано и даже даются подсказки как реализовать парсер.

впрочем, тут не обходится без подводных камней, на которых обламывается даже плагин colorer для FAR'а, который воспринимает """ xxxx \"""" как комментарий, забывая о том, что '\"' обрабатывается особым образом.

короче, предлагаю кандидату (особенно на роль сеньора) написать скрипт, заменяющий пробелы символами табуляции (и, в качестве бонуса, обрабатывающий скрипты где есть и то, и другое), а затем проверить его программу на следующем примере. если она не развалится, то смело можно брать:


# http://docs.python.org/reference/lexical_analysis.html
def perm(l):
        # Compute the list of all permutations of l
    if len(l) <= 1:
                  return [l]
    r = []
    for i in range(len(l)):
             s = l[:i] + l[i + 1:]
             p = perm(s)
             """ hello, world !
                     of rasta/ \"""
             """
             for x in p:
              r.append(l[i : i + 1] + x)
              if 1 == 1:
                       if  6  == 999:
                         if 9 == 666: pass
    return r
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re: # оригинальное тестовое задание
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 07.08.12 04:44
Оценка:
По мне так это даже проще разворачивания списка на бумажке (если предположить что эта задача делается не на бумажке и мы поддерживаем не всю грамматику питона, а только приведенную в примере)... Ну, я это к тому, что вопрос подобного типа задать очень даже стоит, но что прям уж сразу "если она не развалится, то смело можно брать", я как-то даже не уверен
Re: # оригинальное тестовое задание
От: serra  
Дата: 07.08.12 05:55
Оценка: -2
М> минут за полчаса

Если что-то не редактируется при помощи sed, то это надо делать на аналоге lex & yacc

Минимальное время написания на них чего либо для человека последний раз видевшего их в ВУЗ-е 10 лет назад — 1 час (практически проверено)
Re[2]: # оригинальное тестовое задание
От: serra  
Дата: 07.08.12 06:08
Оценка:
С чем несогласны?

1) с необходимостью использования yacc ?
(типа, вы круты в написании рекурсивных парсеров, и всем потом с этим нестандартом мучаться — документировать, обучать и т.д.?)

2) с временнОй оценкой ?
Ну вы сначала поищите бесплатный открытый yacc-генератор под какой-нибудь современный язык,
потом прочитайте документацию к нему.
Сомневаюсь, что быстрее получится

У меня просто была ровно такая задача на практике.
Вы меня обвиняете в тупизне и тормознутости.
Обосновывайте.
Re[2]: # оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 06:12
Оценка:
Здравствуйте, kaa.python, Вы писали:

KP> По мне так это даже проще разворачивания списка на бумажке

KP> (если предположить что эта задача делается не на бумажке и
KP> мы поддерживаем не всю грамматику питона, а только приведенную в примере)...
эээ.... а какую грамматику поддерживать-то? там совсем немного подводных камней.
например,

def foo():
      if  1 == 1:
             a = [1,
2,3,4];
             return 0;


тем более, что упомянутый плагин для FAR'а валится на конструкции """ \""", так что это задача не только на сообразительность, но и внимательность к мелочам. разворот списка -- гм, ну во-первых, это известная тема, во-вторых, в общем случае решения нет. в том же питоне нам доподлинно неизвестна реализация списков и если она составляет O(N), то мы попадаем на производительность. а если создаем временный список -- при плохой сборке мусора это двойной расход памяти.

то есть разворот списка тесно связан с возможностями конкретного языка, причем эти возможности под капотом.

> Ну, я это к тому, что вопрос подобного типа задать очень даже стоит, но что прям уж сразу

> "если она не развалится, то смело можно брать", я как-то даже не уверен
"смело брать" это, конечно, шутка. чувак может быть умным, но неадекватным. или адекватным, но ленивым. или безынициативным. или...

но на мой скромный взгляд эта задача с одной стороны простая, а с другой достаточно оригинальная. тут даже гуглом можно разрешить пользоваться (ибо там ответа нет, а те ответы, что есть -- неправильные)
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re[2]: # оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 06:17
Оценка:
Здравствуйте, serra, Вы писали:

М>> минут за полчаса


S>Если что-то не редактируется при помощи sed, то это надо делать на аналоге lex & yacc

мы говорим о конвертации пробелов в табуляцию. у питона в этом смысле очень простая логика. пишется за пол-часа с чистого листа (включая отладку и скидку на стресс при собеседовании).

S>Минимальное время написания на них чего либо для человека последний

S>раз видевшего их в ВУЗ-е 10 лет назад — 1 час (практически проверено)
зачем тут lex & yacc ? тогда уж проще готовый навороченный IDE взять, который это делает по хоткею.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re[3]: # оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 06:32
Оценка:
Здравствуйте, serra, Вы писали:

S>С чем несогласны?


S>1) с необходимостью использования yacc ?

S> (типа, вы круты в написании рекурсивных парсеров,
S> и всем потом с этим нестандартом мучаться — документировать, обучать и т.д.?)
кого документировать? кого обучать? пример парсера, решающего сходную задачу идет вместе с питоном (reindent.py) и это далеко не самый простой вариант, хотя там всего 250 строк кода, реально (с учетом, что пример тестовый) будет сильно меньше.

S> У меня просто была ровно такая задача на практике.

S> Вы меня обвиняете в тупизне и тормознутости.
S> Обосновывайте.
я уложился в 50 строк на питоне, причем писал "размашисто" и поддержал кучу фич (типа убить висячие пробелы и табы в конце строк, сохранить файл под винду или никсы).

там парсер нужен _только_ для обработки ситуаций вида:
a = [1, # ops!!!
2]
и
a = "hello,"\
"world";
print a

еще можно на pindent.py взглянуть (тоже идет с питоном). там уже вполне окейный такой парсер, понимающий ключевые слова.\

на фига что-то еще?
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re: # оригинальное тестовое задание
От: THESERG  
Дата: 07.08.12 06:38
Оценка: 1 (1)
скрипт тоже на питоне писать?
Re: # оригинальное тестовое задание
От: MTD https://github.com/mtrempoltsev
Дата: 07.08.12 06:39
Оценка:
Вот результат работы скрипта:

# http://docs.python.org/reference/lexical_analysis.html
def perm(l):
    # Compute the list of all permutations of l
    if len(l) <= 1:
        return [l]
    r = []
    for i in range(len(l)):
        s = l[:i] + l[i + 1:]
        p = perm(s)
        """ hello, world !
                     of rasta/ \"""
             """
        for x in p:
            r.append(l[i : i + 1] + x)
            if 1 == 1:
                if  6  == 999:
                    if 9 == 666: pass
    return r


Я правильно понял задачу?
Re[3]: # оригинальное тестовое задание
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 07.08.12 07:36
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>эээ.... а какую грамматику поддерживать-то? там совсем немного подводных камней.


Да любую, например ту, которую ты только что привел. Основная мысль в том, что если надо еще изучать спеки по питону и допустимым вариантам форматирования, за пределами примера, это потребует больше времени.
Re[2]: # оригинальное тестовое задание
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 07.08.12 07:38
Оценка: -1
Здравствуйте, serra, Вы писали:

S>Если что-то не редактируется при помощи sed, то это надо делать на аналоге lex & yacc

S>Минимальное время написания на них чего либо для человека последний раз видевшего их в ВУЗ-е 10 лет назад — 1 час (практически проверено)

Человека который начнет втыкивать lex & yacc туда, где надо несколько пробелов посчитать, можно сразу с собеседования выгонять, как не понимающего что такое "писать простой код".
Re[3]: # оригинальное тестовое задание
От: serra  
Дата: 07.08.12 08:09
Оценка: -1
KP> что такое "писать простой код".

Код не должен быть излишне навороченным.

Если граматика может быть сведена к регулярным выражениям — то sed, о чем было сказано сразу
При требовании учитывать строки, комментарии и переносы строк — использование yacc
это не излишне, а в самый раз.

Мщих предлагал так же использовать готовую IDE.
Вообще-то это идеальный вариант, когда ничего писать не надо!
Re[4]: # оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 12:34
Оценка:
Здравствуйте, serra, Вы писали:

KP>> что такое "писать простой код".


S>При требовании учитывать строки, комментарии и переносы строк — использование yacc

S>это не излишне, а в самый раз.
в таком случае, в сабжевом контексте сортировки и развороты списков решаются библиотечными средствами, а гору фудзи сдвигает толпа нанятых гастробайтеров.


S> Мщих предлагал так же использовать готовую IDE.

S> Вообще-то это идеальный вариант, когда ничего писать не надо!
как раз предлагал не использовать, т.к. моя IDE -- far. и ставить монстра для решения задачи минут на полчаса -- это слишком
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re: # оригинальное тестовое задание
От: sumson Россия  
Дата: 07.08.12 14:52
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>написать скрипт, заменяющий пробелы символами табуляции

написал за полчаса на flex(это макосовский вариант lex):

%{
%}

%option c++
%option yywrap
%option stack
%pointer

spaces   [ ]{4}
%%

{spaces}   { 
    REJECT;
    std::cout << "\t";
}

%%

int main( int /* argc */, char** /* argv */ )
{
    FlexLexer* lexer = new yyFlexLexer;
    while(lexer->yylex() != 0)
     ;
    return 0;
}

int yyFlexLexer::yywrap()
{
    return 1;
}

перенести это содержимое в файл с расширением ll

далее в терминале набираем:
flex --c++ <you-file-name>.ll
g++ -W -Wall -Wextra -ansi -g lex.yy.cc -o test


потом запускаем test
далее копируем код из поста в терминал и получаем такой же в ответ но уже с табуляцией вместо 4 пробелов
Я знаю, как управлять Вселенной. И скажите, зачем же мне бежать за миллионом?!(c)
Re[2]: # оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 16:00
Оценка:
Здравствуйте, sumson, Вы писали:

S>Здравствуйте, мыщъх, Вы писали:


S>далее копируем код из поста в терминал и получаем

S>такой же в ответ но уже с табуляцией вместо 4 пробелов
а если там три пробела? или два? или один? или пять?
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re[2]: # оригинальное тестовое задание
От: MTD https://github.com/mtrempoltsev
Дата: 07.08.12 16:00
Оценка:
Здравствуйте, sumson, Вы писали:

S>написал за полчаса на flex(это макосовский вариант lex):


1. flex — это улучшенный lex, а не маковский lex
2. То что вы написали не будет делать то, что нужно по условию задачи
Re[3]: # оригинальное тестовое задание
От: MTD https://github.com/mtrempoltsev
Дата: 07.08.12 16:03
Оценка:
Здравствуйте, мыщъх, Вы меня игнорируете?

здесь
Автор: MTD
Дата: 07.08.12


Правда там движок RSDN вместо табов по 4 пробела вставил
Re[3]: # оригинальное тестовое задание
От: sumson Россия  
Дата: 07.08.12 16:04
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>Здравствуйте, sumson, Вы писали:


S>>Здравствуйте, мыщъх, Вы писали:


S>>далее копируем код из поста в терминал и получаем

S>>такой же в ответ но уже с табуляцией вместо 4 пробелов
М>а если там три пробела? или два? или один? или пять?

во первых вот обновлённый вариант, в прошлом нашёл баг
%{
int tabs = 0;
%}

%option c++
%option yywrap

spaces   [ ]{4}
%%

{spaces}   { 
    tabs++;
}

. {
    if(tabs > 0)
    {
        for(;tabs > 0;tabs--)
        {
            std::cout << "\t";
        }
    }
    ECHO;
}

%%

int main( int /* argc */, char** /* argv */ )
{
    FlexLexer* lexer = new yyFlexLexer;
    while(lexer->yylex() != 0)
     ;
    return 0;
}

int yyFlexLexer::yywrap()
{
    return 1;
}

во вторых если будет подряд меньше 4 пробелов то пропустит через себя без изменений
если больше, например 5 то на выходе будет табуляция и пробел, если 6 то табуляция и 2 пробела и так далее
можно менять значение 4 на любое другое которое предполагается в качестве замены на табуляцию
Я знаю, как управлять Вселенной. И скажите, зачем же мне бежать за миллионом?!(c)
Re[2]: # оригинальное тестовое задание
От: мыщъх США http://nezumi-lab.org
Дата: 07.08.12 16:07
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>Вот результат работы скрипта:


MTD>
MTD>        p = perm(s)
MTD>        """ hello, world !
MTD>                     of rasta/ \"""
MTD>             """
^^^^^^^^^^^^^^^^^^^^^^
MTD>        for x in p:
MTD>


MTD>Я правильно понял задачу?



смущает, что подчеркнутый комментарий сместился на один символ вправо (хотя на работу скрипта это и не влияет), а так зачот, да.

кстати, тут есть один _очень_ интересный момент. все мы знаем, чтобы временно "выключить" код девы юзают комменты и потому ситуацию следующего вида надо обрабатывать

if a == b:
#         print "a == b"
         foo(a);


смысл тут в том, что за знаком '#' могут быть пробелы, которые так же полезно конвертировать в табуляцию.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re[3]: # оригинальное тестовое задание
От: MTD https://github.com/mtrempoltsev
Дата: 07.08.12 16:18
Оценка:
М>смущает, что подчеркнутый комментарий сместился на один символ вправо (хотя на работу скрипта это и не влияет), а так зачот, да.

Это потому, что до левых кавычек табуляция, а потом пошел текст и пробелы в нем я решил, что менять на табуляцию неправильно.

М>смысл тут в том, что за знаком '#' могут быть пробелы, которые так же полезно конвертировать в табуляцию.


Этот момент, да, не учел.

По времени у меня ушло минут 40, код на питоне около 50 строчек так, что как тестовое задание — вполне
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.