| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
Turbo
Site Admin
Зарегистрирован: 19.02.2006
Сообщения: 248
|
 Добавлено: Ср Апр 16, 2008 8:39 am Заголовок сообщения: Ваши решения для задачи "RegExp мастер" |
 |
|
В этой теме можно обсудить ваш подход к решению этой задачи.
А также меня интересует каких по вашему мнению не хватает тестовых данных для каждой из задач? Как поменять текст и тесты для задач про E-Mail и адрес сайта? В общем всю необходимую информацию по уязвимости тестовых данных. |
|
| Вернуться к началу |
|
 |
iffy
Зарегистрирован: 23.03.2006
Сообщения: 3
|
| Добавлено: Ср Апр 16, 2008 12:24 pm Заголовок сообщения: |
|
|
Вопросы:
1 подзадачу кероме как вот так:
^abcdefghijklmnopqrstuv18340$
можно было решить?
Как решали 9 подзадачу, про пароль.
Я правильно понимаю что надо было сгенерить оооочень длинный перебор всех возможных вариантов?
№ 2, 3, 5, 6, 10 - это всё просто, на мой взгляд.
Только в 10-ой так и не добавили правильного теста. Проходили варианты вроде:
а12345
=12345
№ 4 и 7:
Я нашёл варианты в инете и подкорректировал их под условие задачи. |
|
| Вернуться к началу |
|
|
zhengxi
Зарегистрирован: 25.03.2008
Сообщения: 19
|
| Добавлено: Ср Апр 16, 2008 12:30 pm Заголовок сообщения: |
|
|
| iffy писал(а): | Вопросы:
1 подзадачу кероме как вот так:
^abcdefghijklmnopqrstuv18340$
можно было решить?
|
До перетестирования работало: ^.{25}0$
| iffy писал(а): |
Как решали 9 подзадачу, про пароль.
Я правильно понимаю что надо было сгенерить оооочень длинный перебор всех возможных вариантов?
|
Да, но 18kb где-то получатся
Из-за лимита в 10к пришлось не полностью соблюсти условие |
|
| Вернуться к началу |
|
|
Stanislav Markevich
Зарегистрирован: 21.02.2006
Сообщения: 12
Откуда: Москва
|
| Добавлено: Ср Апр 16, 2008 12:38 pm Заголовок сообщения: |
|
|
| zhengxi писал(а): |
Из-за лимита в 10к пришлось не полностью соблюсти условие |
[A-Za-z0-9_] заменилось на . ? 
А во второй задаче наличие скобок {} как то можно было учесть чтобы два варианта не рассматривать? |
|
| Вернуться к началу |
|
|
rand08
Зарегистрирован: 22.03.2008
Сообщения: 5
|
| Добавлено: Ср Апр 16, 2008 12:39 pm Заголовок сообщения: |
|
|
По первой до перетестирования прокатывало
.{26}0$
9-ую сгенерил regex на все варианты. Всего 6Кб заняло, но можно было немного переписать на меньший размер, просто смысла не было.
Код генератора:
| Код: | #include <stdio>
#include <stdlib>
int main() {
int d[][3] = {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,1,0},{2,0,1}};
char* ss[] = {"[A-Z]+","[0-9]+", "[a-z]+"};
// ...
for (int perm = 0; perm < 6; perm++)
for (int i1 = 0; i1 <5> 1) printf(".{%d,}", i1); else if (i1==1) printf(".+"); else printf(".*"); printf(ss[d[perm][0]]);
if (i1 < 5) printf("(");
for (int i2 = 0; i1 + i2 <5> 1) printf(".{%d,}", i2); else if (i2==1) printf(".+"); else printf(".*"); printf(ss[d[perm][1]]);
if (i1 + i2 < 5) printf("(");
for (int i3 = 0; i1 + i2 + i3 <5> 1) printf(".{%d,}", i3); else if (i3==1) printf(".+"); else printf(".*"); printf(ss[d[perm][2]]);
if (i4 > 1) printf(".{%d,}", i4); else if (i4==1) printf(".+"); else printf(".*");
if (i1 + i2 + i3 != 5) printf("|");
}
if (i1 + i2 < 5) printf(")");
if (i1+i2!=5) printf("|");
}
if (i1 < 5) printf(")");
if (i1!=5||perm!=5) printf("|");
}
// ...
return 0;
} |
Последний раз редактировалось: rand08 (Ср Апр 16, 2008 1:09 pm), всего редактировалось 2 раз(а) |
|
| Вернуться к началу |
|
|
zhengxi
Зарегистрирован: 25.03.2008
Сообщения: 19
|
| Добавлено: Ср Апр 16, 2008 12:43 pm Заголовок сообщения: |
|
|
| Stanislav Markevich писал(а): | | zhengxi писал(а): |
Из-за лимита в 10к пришлось не полностью соблюсти условие |
[A-Za-z0-9_] заменилось на . ?
|
Да. Что там \w работает позже узнал, возможно и влезло бы в 10к корректное решение.
| Stanislav Markevich писал(а): |
А во второй задаче наличие скобок {} как то можно было учесть чтобы два варианта не рассматривать? |
(\{|^) .... (}|$) |
|
| Вернуться к началу |
|
|
pperm
Зарегистрирован: 25.02.2007
Сообщения: 26
|
| Добавлено: Ср Апр 16, 2008 2:13 pm Заголовок сообщения: Re: Ваши решения для задачи "RegExp мастер" |
|
|
| Turbo писал(а): | В этой теме можно обсудить ваш подход к решению этой задачи.
А также меня интересует каких по вашему мнению не хватает тестовых данных для каждой из задач? Как поменять текст и тесты для задач про E-Mail и адрес сайта? В общем всю необходимую информацию по уязвимости тестовых данных. |
Лучший способ все-таки для большенства задания написать чекеры... т.е посмотреть множество которая задает регулярное выражение... Чекеры можно написать наверное для большенства заданий... |
|
| Вернуться к началу |
|
|
Werewolf
Зарегистрирован: 16.03.2007
Сообщения: 28
|
| Добавлено: Ср Апр 16, 2008 3:41 pm Заголовок сообщения: |
|
|
| zhengxi писал(а): |
Да. Что там \w работает позже узнал, возможно и влезло бы в 10к корректное решение. |
А там \w работало?? Вот блин... (
После перетестирования по первой прокатило:
abcdefghijk.+0$
Да и ваще во всех задачах можно было кое-где схитрить )
Например для hex цифры написать [a-f0-F], а в некоторых местах даже [^Zz]
Вместо [A-Za-z] писать [A-z]
Новый тест на дату вроде был неплохой - прошел только полностью валидный regex.
На мыло тест ужасный, проходит такое:
^[^@]+@[^.@]+\.[^.]+$
и тд.
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu. |
|
| Вернуться к началу |
|
|
iffy
Зарегистрирован: 23.03.2006
Сообщения: 3
|
| Добавлено: Ср Апр 16, 2008 4:37 pm Заголовок сообщения: |
|
|
Ага, это не ожидано про \w !
В последний день как раз проверил A-z и 0-F - порадовался что проходит, а так да - опять же косяк это.
Как писал выше в 10 подзадаче проходит ^[^0][0-9]{5}$
Turbo - видимо тесты надо увеличивать в разы. |
|
| Вернуться к началу |
|
|
Werewolf
Зарегистрирован: 16.03.2007
Сообщения: 28
|
| Добавлено: Ср Апр 16, 2008 5:43 pm Заголовок сообщения: |
|
|
levlam, можешь рассказать, где ты выражение на 3 буквы сделал? )
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu. |
|
| Вернуться к началу |
|
|
levlam
Зарегистрирован: 25.01.2007
Сообщения: 11
|
| Добавлено: Ср Апр 16, 2008 6:18 pm Заголовок сообщения: |
|
|
| Werewolf писал(а): | | levlam, можешь рассказать, где ты выражение на 3 буквы сделал? ) |
В 9 задаче(проверка надёжности пароля) проходило такое выражение:
1|P |
|
| Вернуться к началу |
|
|
Turbo
Site Admin
Зарегистрирован: 19.02.2006
Сообщения: 248
|
| Добавлено: Ср Апр 16, 2008 7:39 pm Заголовок сообщения: |
|
|
| levlam писал(а): | | Werewolf писал(а): | | levlam, можешь рассказать, где ты выражение на 3 буквы сделал? ) |
В 9 задаче(проверка надёжности пароля) проходило такое выражение:
1|P |
Какие нужны тесты что бы это не работало? =) |
|
| Вернуться к началу |
|
|
Werewolf
Зарегистрирован: 16.03.2007
Сообщения: 28
|
| Добавлено: Ср Апр 16, 2008 9:38 pm Заголовок сообщения: |
|
|
| Turbo писал(а): | | Какие нужны тесты что бы это не работало? =) |
Как минимум 1P
А лучше
1234567890
ABCDE...XYZ
abcd...xyz
Если развивать дальше, то надо уже брать различные комбинации )
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu. |
|
| Вернуться к началу |
|
|
DAle
Зарегистрирован: 21.02.2006
Сообщения: 24
|
| Добавлено: Ср Апр 16, 2008 10:22 pm Заголовок сообщения: |
|
|
| Turbo писал(а): | | levlam писал(а): | | Werewolf писал(а): | | levlam, можешь рассказать, где ты выражение на 3 буквы сделал? ) |
В 9 задаче(проверка надёжности пароля) проходило такое выражение:
1|P |
Какие нужны тесты что бы это не работало? =) |
Я в шоке )) Какие нужны тесты, чтобы это работало, лучше скажи? В общем, огромная просьба: не добавлять эту задачу на spoj. |
|
| Вернуться к началу |
|
|
DAle
Зарегистрирован: 21.02.2006
Сообщения: 24
|
| Добавлено: Чт Апр 17, 2008 12:21 am Заголовок сообщения: Re: Ваши решения для задачи "RegExp мастер" |
|
|
| Turbo писал(а): | | В этой теме можно обсудить ваш подход к решению этой задачи. |
Напишу, пожалуй, еще раз. Не нужно эту задачу добавлять на спож. Она при любых тестах превращается в угадайку. И ничего ей не поможет.
По задаче 9.. Не знаю, правильно я понял или нет, но я думал, что на входе может быть только строчка, состоящая из букв, цифр и подчеркивания. Если понимать условие так (то есть можно использовать '.'), то у меня получился регэксп около 6 килобайт. Если же на вводе может быть что угодно, то . можно заменить на \w. Будет около 7к. Без \w, наверное, не получится.
Регэксп вроде бы вполне правильный, учитывающий, например, случаи, когда пароль начинается с >= 8 подчеркиваний. |
|
| Вернуться к началу |
|
|
|
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
