LINUX.ORG.RU

Осваиваю haskell, или привет быдлокодерам хабра

 ,


0

3

Начал я намедни изучение замечательного языка илитки haskell и решил реализовать подсчет комбинаций пароля из «Уязвимость графического пароля». Скачиваем прогу по ссылке и сохраняем как lockpattern.hs.

Автором статьи подсчитано, что число возможных вариантов равно 389488. А теперь самое интересное:

┌─[vonavi@desktop] - [~/Dropbox/progs/haskell/test] - [Вс июл 27, 13:05]
└─[$] <> ghc lockpattern.hs       
┌─[vonavi@desktop] - [~/Dropbox/progs/haskell/test] - [Вс июл 27, 13:15]
└─[$] <> ./lockpattern 
Pattern-lock size (in points): 3
Minimal pattern length (in points): 5
Number of pattern combinations: 138480
Результат на хабре не верен?! И это при овер-дохера перепостов, сотнях кодеров и тысяч посещений! Может их мозг сожрал Ктулху?

P.S. Есть парочка косвенных подтверждений, что моя прога правильная.

★★★★★

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

esandmann ()
Ответ на: комментарий от esandmann

Ну тут надо же быть дураком, чтобы не заметить, что у вас разные входные данные

Разные - это какие?

Нужно задать начальные условия:

Направление имеет значение

Yes

Каждую точку можно пройти лишь однажды

Yes

Для соединения двух точек они должны быть в прямой видимости. То есть первая может быть соединена пальцем со второй, но не с третьей.

Yes

Количество точек: от 5 до 9. Назовём один росчерк, одно соединение — хопом. То есть у нас может быть от 4 до 8 хопов.

Yes

iVS ★★★★★ ()

Вообще смотрю и думаю, какая муть этот каскель. как вот connectJoints работает, я так и не понял (хотя работает верно, я проверил с ghci ;)

esandmann ()
Ответ на: комментарий от esandmann

Ты вывод смотри, там эти его Hops от 1 считаются. Т.е. от 1 до 8 включительно.

Хоп — это соединение между точками, соответственно точек в линии на одну больше. Поэтому условие

Количество точек: от 5 до 9. Назовём один росчерк, одно соединение — хопом. То есть у нас может быть от 4 до 8 хопов.

соответствует моему

Minimal pattern length (in points): 5

Очевидно, максимальное кол-во точек — 9. Вот и получаем кол-во соединений от 4 до 8.

iVS ★★★★★ ()
Ответ на: комментарий от iVS

Да не, у него на первой картинке это, а далее я не смотрел.

http://img-fotki.yandex.ru/get/6445/83739833.26/0_b4e12_855e3db0_XL.png.jpg

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

uncurry gcd (a `jminus` b) == 1 = True

такое

esandmann ()
Ответ на: комментарий от esandmann

как вот connectJoints работает, я так и не понял

Математика. Есть две точки (x1, y1) и (x2, y2) с целыми координатами. Можно, скажем, построить треугольник (x1,y1), (x2,y2), (x1,y2). Задача сводится к построению подобного треугольника с (x1,y1'), (x2',y2'), (x1,y2') с целыми x2', y2'. Можно доказать, что коэффициент подобия кратен 1/НОД(x2-x1, y2-y1). Отсюда и следует

НОД(x2-x1, y2-y1) == 1

для условия

Для соединения двух точек они должны быть в прямой видимости. То есть первая может быть соединена пальцем со второй, но не с третьей.

iVS ★★★★★ ()
Ответ на: комментарий от esandmann

http://img-fotki.yandex.ru/get/6445/83739833.26/0_b4e12_855e3db0_XL.png.jpg

Кстати, эта картинка наглядно демонстрирует ошибку в алгоритме. Возьмем линию из 7 хопов (8 точек), ее не всегда можно соединить с последней пустой точкой (она не всегда находится в прямой видимости). Значит, кол-во линий с 7 хопами больше, чем с 8. А на картинке они равны.

iVS ★★★★★ ()
Ответ на: комментарий от crowbar

Чего?

Для соединения двух точек они должны быть в прямой видимости. То есть первая может быть соединена пальцем со второй, но не с третьей.

esandmann ()
Ответ на: комментарий от crowbar

Можно выбрать такое соединение (даже визуально это видно на поле 3x3) из 7 точек, что ни по какому другому пути их до 8 не продолжить. Вроде всё логично

esandmann ()
Ответ на: комментарий от esandmann

Вот такой вот вариант возможен (зеленый хоп — последний): http://itmages.ru/image/view/1806061/6fb57fd8

Автор статьи имел ввиду, что для соединения двух _непройденных_ точек, между ними не должно быть других _непройденных_. В комментах ниже он это подтверждает.

crowbar ()
Ответ на: комментарий от esandmann

Попробуй еще так: заменить ф-цию connectJoints:

connectJoints :: Joint -> Joint -> Bool
connectJoints a b = True
Мы игнорируем условие, что точки должны быть в прямой видимости. Тогда
┌─[vonavi@desktop] - [~/Dropbox/progs/haskell/test] - [Вс июл 27, 14:45]
└─[$] <> ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l lockpattern.hs 
[1 of 1] Compiling Main             ( lockpattern.hs, interpreted )
Ok, modules loaded: Main.
*Main> main
Pattern-lock size (in points): 3
Minimal pattern length (in points): 5
Number of pattern combinations: 982800
*Main> product [1..9] + product [2..9] + product [3..9] + product [4..9] + product [5..9]
982800
Похоже на правду.

iVS ★★★★★ ()
Ответ на: комментарий от esandmann

Походу можно связываться с любой близкой точкой. Но тогда в случае 9 точек ничто не мешает нам взять их все по любому пути, так что это перестановка из 9 элементов, то есть 362880, а не 140704. Хабробляди опять соснули, поздравляю коллега!

esandmann ()
Ответ на: комментарий от crowbar

Автор статьи имел ввиду, что для соединения двух _непройденных_ точек, между ними не должно быть других _непройденных_. В комментах ниже он это подтверждает.

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

iVS ★★★★★ ()
Ответ на: комментарий от esandmann

Как я понял из комментариев, можно соединять любую точку с любой, главное, чтобы она активировалась только один раз. Получаем тупо количество перестановок, и, например, для

Количество точек: от 5 до 9. Назовём один росчерк, одно соединение — хопом. То есть у нас может быть от 4 до 8 хопов.

это будет

*Main> product [1..9] + product [2..9] + product [3..9] + product [4..9] + product [5..9]
982800

Хабробляди опять соснули, поздравляю коллега!

Аналогично.

iVS ★★★★★ ()
Ответ на: комментарий от crowbar

Ты не можешь провести линию из точки 1:1 в точку 3:3, не активировав при этом точку 2:2

Активируется 3:3 только тогда, когда 2:2 уже активирована?

iVS ★★★★★ ()
Ответ на: комментарий от iVS

3:3 всегда активируется, если она не была активна до этого. Но если линия пересекла неактивную точку 2:2, то она тоже активируется и тем самым разбивает отрезок на два.

crowbar ()

Там ещё могут быть ньюансы. Например, точно помню, что в одной из первых версий ICS нельзя было поставить такой паттерн. А вот в более поздних версиях:

o x o
o o o
x o o
разрешили.

EXL ★★★★★ ()

И ещё, там был учтен вектор узора?
Так как {1:1, 2:2, 2:3} != {2:3, 2:2, 1:1}

EXL ★★★★★ ()

esandmann, crowbar: oбновил lockpattern.hs: http://pastebin.com/3D66XDCc
Теперь вот как:

*Main> :l lockpattern
[1 of 1] Compiling Main             ( lockpattern.hs, interpreted )
Ok, modules loaded: Main.
*Main> main
Pattern-lock size (in points): 3
Minimal pattern length (in points): 5
Number of pattern combinations: 387488
Забавно, отличается на одну цифру от авторского:

Автором статьи подсчитано, что число возможных вариантов равно 389488

Видимо, у него банальная описка.

iVS ★★★★★ ()
Ответ на: комментарий от crowbar

Ого, на хабре точно описка, см. мой ответ выше.

iVS ★★★★★ ()
Ответ на: комментарий от crowbar

389488 — это все пароли

У меня получилось 389497, но не суть, видимо, один какой-то частный случай не рассмотрел (видимо засчитал 9 линий длиной в одну точку).

387488 — больше 3х хопов

Больше 4х хопов.

iVS ★★★★★ ()
Последнее исправление: iVS (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.