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

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

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

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

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

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

Yes

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

Yes

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

Yes

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

Yes

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

Только результаты всё равно разные

Yes

в смысле «check»?

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

Хехе, это я даже не удосужился пролистать донизу :)

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

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

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

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

Minimal pattern length (in points): 5

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

в смысле «check»?

Наверное, а что это за смысл «check»?

В смысле «галочка» в списке

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

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

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

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

такое

как вот 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

для условия

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

Это естессно, я просто не въехал, что такое uncarry, а про gcd я б не подумал, что такая функция может быть в языке

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

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

Вершины не должны находиться в прямой видимости. Видимо в этом твоя ошибка.

Чего?

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

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

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

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

Попробуй еще так: заменить ф-цию 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

Да, это размещения вроде, если я правильно помню название

Блин, точно нам товарищ подсказывает

http://habrastorage.org/storage2/a8d/a54/c76/a8da54c767c3dd690ea32e5dfa6cb8ab...

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

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

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

зачем же читать, ctrl+f решает.

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

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

это будет

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

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

Аналогично.

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

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

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

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

Да, я зашел в тупик, господа

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

o x o
o o o
x o o

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

Получил тот же ответ: http://ideone.com/UcgOPh

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

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

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

389488 — это все пароли, 387488 — больше 3х хопов.

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

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

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

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