Экран блокировки Android

25

вступление

Вы сидите в зале заседаний в конце длинного стола. Вы оглядываетесь вокруг и видите Тима Кука, совет директоров Apple, призрака Стива Джобса и Джека Донахи. Apple созвала эту встречу, потому что они поняли, насколько холоднее экран блокировки Android, и хотят их 1-UP. Все в комнате смотрят на тебя, как призрак Стив кричит: «Помоги мне, Человек-КодГольф! Ты моя единственная надежда!»

Проблема

Экран блокировки Android представляет собой сетку точек 3 x 3, которую можно соединить, проведя пальцем от одной точки к другой, создавая путь. Паролем считается любой возможный путь, который включает любое количество точек и исключает любое количество точек. (На реальном телефоне длина пути должна быть не менее 4 точек. В этом случае игнорируйте это ограничение.) Apple планирует заменить сетку 3 x 3 сеткой M x N, которая равна (M * N) / 9. раз лучше!

Правила:

  • Путь с нулевой точкой не является паролем, но путь с 1 точкой
  • Путь может пересечь себя
  • Путь не может пересекаться непосредственно над точкой без включения этой точки
  • Точку можно использовать только один раз
  • Пути, которые идентичны по ротации, не являются тем же паролем
  • Пути, которые идентичны, но упорядочены в обратном порядке, не являются тем же паролем
  • Например, в сетке 3x3 с точками, пронумерованными от 1 до 9:

    1 2 3
    4 5 6
    7 8 9
    

    Некоторые допустимые пути:

    1
    3
    7,2,3
    1,5,9,2
    1,8,6,5,4
    4,2,3,5,6,7,8,9
    5,9,6,4
    

    И некоторые неверные пути:

    1,3
    1,9,5
    7,5,4,7
    4,6
    

    Ваш вход будет три числа:

    (M,N,d)
    

    Где сетка M x N, а d - длина пути

    1 <= M <= 16
    1 <= N <= 16
    1 <= d <= M * N
    

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

    Input:  2,2,1 
    Output: 4
    Input:  2,2,2
    Output: 12
    Input:  7,4,1
    Output: 28
    

    Применяются стандартные правила игры в гольф, самый короткий код выигрывает!

    //If I've made a mistake or the rules are unclear, please correct me!
    
    Platatat
    источник
    2
    Является ли введенная запятая строка или три отдельных параметра?
    user80551
    1
    @ user80551 Исходя из контекста, я думаю, что это будет строка, если она вводится в программу, или отдельные параметры, если она используется для вызова функции.
    user12205
    1
    @Platatat, не могли бы вы ответить на вопрос user80551, так как это действительно важно для разработки кода
    RononDex
    3
    Вы должны решить, будет ли установлен лимит времени для времени компиляции и выполнения данного решения. Без такого ограничения легко написать программу, которая теоретически проверяет, какая из всех 256!перестановок точек в сетке 16 x 16 представляет действительный шаблон разблокировки. На практике такая программа никогда не прекратится.
    Деннис
    3
    Но я сказал, что проблема была в системе блокировки Android ... Так почему бы мне не использовать те же правила, что и в системе блокировки Android?
    Плататат

    Ответы:

    14

    Python - 170 байт

    from fractions import*
    p=lambda m,n,d,l=0,s=set():d<1or sum([p(m,n,d-1,i,s|{i})for i in range(m*n)if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))])
    

    Я понимаю, что скобки внутри sum([...])не являются строго необходимыми, но есть большой штраф производительности за их отсутствие.

    Выход для всех 3х3:

    for i in range(4, 10):
      print p(3, 3, i)
    

    Производит:

    1624
    7152
    26016
    72912
    140704
    140704
    

    Для тестирования / подтверждения, первые 6 значений для доски 4х5:

    20
    262
    3280
    39644
    459764
    5101232
    

    4x5 - интересный случай для проверки, потому что он имеет 2x2, 3x3 и 2x4 скачка колышка.


    Краткое объяснение

    В общем, это исчерпывающий поиск с накопительной обрезкой. Например, поскольку p(3, 3, 4)1624, p(3, 3, 5)будет проверять только 8120 возможностей, а не наивно проверять все 15120. Большая часть логики содержится в условии:

    if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))
    

    На простом английском языке это можно понимать как:

    If no pegs have been used yet
         OR
       the target peg has not yet been used
         AND
       each of the pegs directly between the target peg and the
       current peg (a.k.a. "jumped over") have already been used
    
    Примо
    источник
    2
    Не могли бы вы объяснить, что здесь происходит в мире?
    ɐɔıʇǝɥʇuʎs
    1
    Вы можете сохранить несколько байтов, имея sнабор вместо списка. Я не вижу большого снижения производительности при отбрасывании скобок; с чего бы такое наказание?
    user2357112 поддерживает Monica
    1
    @ user2357112 один суммирует по генератору, другой по списку. С CPython вы правы, особой разницы нет (только примерно на 20% медленнее). С PyPy это более чем в 5 раз медленнее.
    Примо
    1
    @ user2357112 Наконец-то я понял, что вы имели в виду, определив sнабор. Мой урок питона на сегодня: {i}оценивается как set([i]). Я ожидал бы синтаксическую ошибку. Затем добавляется элемент к набору s|{i}, и он также i in sможет быть заменен на s&{i}.
    Примо