Является ли мой шаблон Swipe законным?

154

Большинство Android-смартфонов позволяют пользователю использовать образец пальца, чтобы открыть свой телефон:

шаблонный замок

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

вход

Сетка обозначена построчно с 1 по 9:

1 2 3   
4 5 6   
7 8 9

Входные данные - это число, состоящее из узлов, посещенных от первого до последнего. Например, приведенный выше рисунок является 12357.

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

Поправка: индексирование 0-8 допускается, так как многие языки индексируют от 0. Если вы используете 0-8, необходимо указать это в начале вашего ответа и соответствующим образом скорректировать контрольные примеры.

правила

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

  • Истинный шаблон должен содержать как минимум один удар, поэтому минимум 2 узла.

  • Невозможно пропустить не посещенный узел напрямую в соответствии с другим. Например, 13 ложно, потому что 2 не посещается и находится в прямой линии.

  • Можно только пропустить посещенный узел. 42631 является примером этого.

  • В противном случае линии могут пересекаться. Например, 1524 - это правда.

  • Предположим, ширина узла незначительна и игнорирует практические вопросы (толщина пальца и т. Д.). Таким образом, 16 - это правда, хотя в действительности это может быть немного сложнее.

Тестовые случаи

1 -> false     
12 -> true   
13 -> false   
16 -> true  
31 -> false   
33 -> false  
137 -> false   
582 -> true  
519 -> true  
1541 -> false  
12357 -> true    
15782 -> true   
19735 -> false  
42631 -> true   
157842 -> true  
167294385 -> true   
297381645 -> false   
294381675 -> true

Это , поэтому выигрывает наименьшее количество байтов.

stanri
источник
2
Связанный.
Мартин Эндер
Гарантирован ли список ввода непустым?
Згарб
@ Згарб, да. Это будет непусто.
Станри
Вопрос по математике: math.stackexchange.com/questions/205049/…
Pureferret

Ответы:

69

JavaScript (ES6), 64 байта

Принимает ввод как массив чисел. Ложные значения равны 0 или NaN . Истинные значения являются строго положительными целыми числами.

a=>a[p=1]*a.every(n=>a[p=a[n&p&p*n%5<0|~(p-=n)==9&&p/2]&&-n]^=p)

Контрольные примеры

Как?

преамбула

Две цифры располагаются вертикально, горизонтально или по диагонали, если:

  • они оба странные, отличаются друг от друга и отличаются от 5 (рисунок 1)
  • ИЛИ они оба четные и их сумма равна 10 (рисунок 2)

    противоположные цифры

Кроме того, цифра, стоящая между двумя противоположными цифрами n и p , равна (n + p) / 2 .

Отформатированный исходный код

a =>
  // force a falsy result if a[1] is undefined
  a[p = 1] *
  // walk through all values n in a[]
  a.every(n =>
    // access either a[-n] or a[undefined]
    a[
      // set p to either -n or undefined
      p =
        // read either a[0] or a[in_between_digit]
        a[
          n & p & p * n % 5 < 0 | ~(p -= n) == 9
          && p / 2
        ]
        && -n
    ]
    // toggle the flag
    ^= p
  )

Отслеживание предыдущих цифр

Флаги для посещенных цифр хранятся с отрицательными индексами во входном массиве a , чтобы они не сталкивались с его исходными элементами.

  • Если p установлено в -n :

    Если текущая цифра n ранее не была выбрана, a[-n] ^= -nбудет установлен флаг, и every()цикл будет продолжен на следующей итерации. В противном случае он сбросит флажок и немедленно прервет цикл.

  • Если p установлено в undefined :

    a[undefined] ^= undefinedприводит к 0 , что также приводит к сбою цикла.

Обнаружение противоположных цифр

Следующее выражение используется для проверки того, являются ли текущая цифра n и предыдущая цифра -p противоположными цифрами, как определено в преамбуле:

n & p & ((p * n) % 5 < 0) | ~(p -= n) == 9

что эквивалентно:

n & p & ((p * n) % 5 < 0) | (p -= n) == -10

Примечание. В JS результат по модулю имеет тот же знак, что и дивиденд.

Это можно интерпретировать как:

(n is odd AND -p is odd AND (neither -p or n is equal to 5)) OR (n + -p = 10)

Следовательно, это выражение возвращает 1, если и только если n и -p являются противоположными цифрами или они являются одной и той же нечетной цифрой. Поскольку цифра не может быть выбрана дважды, об этом последнем случае все равно правильно заботятся.

Если это выражение возвращает 1 , мы тестируем a [p / 2] (где p теперь равно отрицательной сумме цифр), чтобы узнать, посещалась ли ранее «промежуточная цифра». В противном случае мы проверяем [0], который гарантированно верен.

О первой итерации

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

Мы достигаем этого, инициализируя p в 1 , потому что для любого n в [1 .. 9] :

  • (1 * n) % 5 не может быть отрицательным
  • ~(1 - n) не может быть равным 9

Оригинальный ответ, 90 байт

Удалено из этого поста, чтобы оно не стало слишком многословным. Вы можете увидеть это здесь .

Arnauld
источник
-1 байт путем замены !!a[1]&на a[1]&&, так как может быть возвращено любое истинное значение
Herman L
@HermanLauenstein Спасибо, это действительно нормально. (Теперь a[1]*еще короче.)
Арно
1
Я отчаянно пытался придумать формулу для has a node directly in line, я не понимал, что это будет так просто ...
Нил
@Neil Глядя на историю изменений этого поста, я уверен, что вы можете сказать, что я тоже не сразу это осознал ... :)
Арнаулд
Думаю , вы можете заменить ?a[-n]^=1:0с &&a[-n]^=1на -1, не может проверить (на мобильный)
Stan бренчать
45

32-битный машинный код x86, 62 60 байт

HexDump:

33 c0 60 8b f2 33 db 99 80 f9 02 72 2d ad 50 0f
ab c2 72 25 3b c3 77 01 93 2b c3 d1 e8 72 14 68
92 08 0e 02 0f a3 5c 04 ff 5f 73 07 03 d8 0f a3
da 73 06 5b e2 d7 61 40 c3 58 61 c3

Он получает длину списка в ecxи указатель на первый элемент в edxи возвращает результат в al:

__declspec(naked) bool __fastcall check(int length, const int* list)

Есть 8 строк, которые содержат узел в середине:

1 - 3
4 - 6
7 - 9
1 - 7
2 - 8
3 - 9
1 - 9
3 - 7

Я сгруппировал их по разнице между большим и меньшим числом.

Разница 2: 3 строки (начиная с 1, 4 или 7)
    1 - 3
    4 - 6
    7 - 9
Разница 4: 1 линия (начиная с 3)
    3 - 7
Разница 6: 3 строки (начиная с 1, 2 или 3)
    1 - 7
    2 - 8
    3 - 9
Разница 8: 1 строка (начиная с 1)
    1 - 9

Затем я преобразовал это в двумерную таблицу поиска, индексированную по полуразнице и меньшему числу:

76543210
--------
10010010 - half-difference 1
00001000 - half-difference 2
00001110 - half-difference 3
00000010 - half-difference 4

Это делает «волшебное» растровое изображение 32 битами. Чтобы проиндексировать его, код помещает его в стек. Затем он извлекает один байт, используя один индекс, и из этого байта извлекает один бит, используя другой индекс. Все это с помощью одной инструкции:

bt byte ptr [esp + eax - 1], ebx; // -1 because half-difference is 1-based

Если растровое изображение показывает, что в середине есть узел, его легко вычислить - прибавьте половину разницы к меньшему числу.

Источник сборки:

    xor eax, eax;   // prepare to return false
    pushad;         // save all registers
    mov esi, edx;   // esi = pointer to input list
    xor ebx, ebx;   // ebx = previously encountered number = 0
    cdq;            // edx = bitmap of visited numbers = 0

    cmp cl, 2;      // is input list too short?
    jb bad_no_pop;  // bad!

again:
    lodsd;          // read one number
    push eax;

    bts edx, eax;   // check and update the bitmap
    jc bad;         // same number twice? - bad!

    cmp eax, ebx;   // sort two recent numbers (ebx = minimum)
    ja skip1;
    xchg eax, ebx;
skip1:

    // Check whether the line crosses a node
    sub eax, ebx;   // calculate half the difference
    shr eax, 1;
    jc skip_cross;  // odd difference? - no node in the middle

    push 0x020e0892;// push magic bitmap onto stack
    bt byte ptr [esp + eax - 1], ebx; // is there a node in the middle?
    pop edi;
    jnc skip_cross; // no - skip the check

    add ebx, eax;   // calculate the node in the middle
    bt edx, ebx;    // was it visited?
    jnc bad;        // no - bad!

skip_cross:
    pop ebx;
    loop again;

    // The loop was finished normally - return true
    popad;          // restore registers
    inc eax;        // change 0 to 1
    ret;            // return

    // Return false
bad:
    pop eax;        // discard data on stack
bad_no_pop:
    popad;          // restore registers
    ret;            // return
anatolyg
источник
Приятно! Мне очень нравится это bt byte ptr [esp + eax], ebx.
Арно
5
Приятно видеть решение сборки :) Вы можете использовать cdqвместо , xor edx, edxкак eaxравно нулю. Кроме того , вы можете сложить dec eaxв bt [esp + eax - 1], ebxкоторый такой же длины , но затем позволяет удалить inc ebxпозже. Это должно сэкономить вам два байта.
Шут
Спасибо за идеи! Вы обеспечили себе место в раю для
игроков
5
Я думаю, что мы все можем согласиться с тем, что рай для игроков в гольф это ад для всех остальных.
Адональсиум
19

Python 2 , 140 131 114 104 99 байт

-2 байта благодаря Джонатану Фреху
-5 байтов благодаря Часу Брауну

v={0};k=input()
for l,n in zip(k,k[1:])or q:(2**n+~2**l)%21%15%9==5<v-{l+n>>1}==v>q;v|={l};n in v>q

Попробуйте онлайн!

Объяснение:

# full program, raising a NameError for invalid input
v={0}            # set of visited nodes
k=input()        # load pattern
# iterate through adjacent pairs, if there is no pair, raise a NameError
for l,n in zip(k,k[1:])or q:
  # detect moves skipping over nodes, details below
  (2**n + ~2**l) % 21 % 15 % 9 == 5 < v - {l+n >> 1} == v > q
  v |= {l}       # add the last node to the set of visited nodes
  n in v > q     # if the current node was previously visited, raise a NameError

Попробуйте онлайн!

Только 8 пар узлов имеют узел между ними. Пара узлов может быть представлена ​​в виде одного целого числа по формуле 2^a-2^b-1. Это число может быть сокращено повторением по модулю:

a  b  2^a-2^b-1  (2^a-2^b-1)%21%15%9
1  3         -7                    5
1  7       -127                    5
1  9       -511                    5
2  8       -253                    5
3  1          5                    5
3  7       -121                    5
3  9       -505                    5
4  6        -49                    5
6  4         47                    5
7  1        125                    5
7  3        119                    5
7  9       -385                    5
8  2        251                    5
9  1        509                    5
9  3        503                    5
9  7        383                    5

(2**n+~2**l)%21%15%9==5сначала проверяется, присутствует ли такая пара, затем v-{l+n>>1}==vпроверяется (a+b)/2, не был ли посещен промежуточный узел, который задан , и еще не qвызвано NameError. Используя цепное сравнение между этими парами, следующее сравнение выполняется только тогда, когда вернулось предыдущее True.

овс
источник
17

Желе ,  24 22 19  18 байт

-2, так как нам больше не нужно обрабатывать пустой список
-1, переключаясь с соединения j@на конкатенацию ;(пропущенный элемент не должен встречаться в середине для используемого метода, находясь в начале трио, это хорошо )
-2 переход от P¬aSHк oSH(OK, чтобы иметь два результата , так как мы сплющить, половина 1является , 0.5который отфильтровывает в любом случае, и имеющие несколько равных результатов не влияет на используемом методе либо)
-1 Благодаря г Xcoder (0-индексированному вход разрешен)

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼

Монадическая ссылка, содержащая список целых чисел [0,8]и возвращающая истинное значение ( 1), если оно разрешено, и значение Falsey ( 0), если нет.

Попробуйте онлайн! или посмотрите набор тестов .

Как?

Просматривает каждую соседнюю пару 0-индексированных узлов в списке ввода. Если целочисленное деление на три из двух отличается на 2, они находятся в верхнем и нижнем рядах, если по модулю на три из двух отличается на 2, они находятся в левом и правом столбцах. Сумма таких пар, разделенная на две, представляет собой либо нулевой индексированный средний узел линии с тремя узлами, либо нецелое значение - поэтому эти значения сначала вставляются перед 0-индексированной парой, а затем фиктивные узлы (как 0.5или3.5) удаляются, результирующий список списков сглаживается, а затем дедуплицируется (для получения сохраненных в порядке, уникальных записей) и, наконец, сравнивается с входными данными - для легкого пролистывания все это в конечном итоге будет неактивным, а незаконным один из них добавит недостающие средние узлы и / или удалит повторяющиеся узлы (обратите внимание, что для входного списка длиной 1 не требуется специальный регистр, поскольку у него нет соседних пар):

d3ZIỊoSH;µƝFf9Ḷ¤Q⁼ - left input is a list of integers   e.g. [3,4,7,1,2,8,3]
          µƝ       - perform the chain to the left for adjacent pairs:
                   - e.g. for [a,b] in:   [3,4]         [4,7]         [7,1]         [1,2]         [2,8]         [8,3]
 d3                -   divmod by 3        [[1,0],[1,1]] [[1,1],[2,1]] [[2,1],[0,1]] [[0,1],[0,2]] [[0,2],[2,2]] [[2,2],[1,0]]
   Z               -   transpose          [[1,1],[0,1]] [[1,2],[1,1]] [[2,0],[1,1]] [[0,0],[1,2]] [[0,2],[2,2]] [[2,1],[2,0]]
    I              -   differences        [0,1]         [1,0]         [-2,0]        [0,1]         [2,0]         [-1,-2]
     Ị             -   abs(v)<=1          [1,1]         [1,1]         [0,1]         [1,1]         [0,1]         [1,0]
       S           -   sum (of [a,b])      7            11            8              3            10            11
      o            -   OR (vectorises)    [1,1]         [1,1]         [8,1]         [1,1]         [10,1]        [1,11]
        H          -   halve (vectorises) [0.5,0.5]     [0.5,0.5]     [4,0.5]       [0.5,0.5]     [5,0.5]       [0.5,5.5]
         ;         -   concatenate        [0.5,0.5,3,4] [0.5,0.5,4,7] [4,0.5,7,1]   [0.5,0.5,1,2] [5,0.5,2,8]   [0.5,5.5,8,3]
            F      - flatten              [0.5,0.5,3,4,  0.5,0.5,4,7,  4,0.5,7,1,    0.5,0.5,1,2,  5,0.5,2,8,    0.5,5.5,8,3]
                ¤  - nilad followed by link(s) as a nilad:
              9    -   literal nine
               Ḷ   -   lowered range = [0,1,2,3,4,5,6,7,8]
             f     - filter keep          [        3,4,          4,7,  4,    7,1,            1,2,  5,    2,8,         ,8,3]
                 Q  - deduplicate          [3,4,7,1,2,5,8]
                  ⁼ - equal to the input?  e.g. 0 (here because 5 was introduced AND because 3 was removed from the right)

Предыдущий метод

Желе ,  36  35 байт

9s3;Z$;“Æ7a‘DZ¤;U$;©0m€2iị®oµƝFQ⁼ȧȦ

Попробуйте онлайн! или посмотрите набор тестов .

Как?

Подобно вышеописанному, но создает все возможности трехузловой линии и выполняет поиск (вместо проверки при использовании divmod для проверки и деления пополам суммы для среднего узла).

Сначала построим список из трех узловых линий:

9s3;Z$;“Æ7a‘DZ¤;U$;©0
9s3                   - nine (implicit range) split into threes = [[1,2,3],[4,5,6],[7,8,9]]
     $                - last two links as a monad:
    Z                 -   transpose = [[1,4,7],[2,5,8],[6,7,9]]
   ;                  -   concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9]]
              ¤       - nilad followed by link(s) as a nilad:
       “Æ7a‘          -   code-page index list = [13,55,97]
            D         -   decimal (vectorises) = [[1,3],[5,5],[9,7]]
             Z        -   transpose = [[1,5,9],[3,5,7]]
      ;               - concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]
                 $    - last two links as a monad:
                U     -   upend = [[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3]]
               ;      -   concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3]]
                    0 - literal zero (to cater for non-matches in the main link since ị, index into, is 1-based and modular the 0th index is the rightmost)
                  ;   - concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
                   ©  - copy the result to the register

Сейчас принимается решение:

...m€2iị®oµƝFQ⁼ȧȦ - left input is a list of integers               e.g. [4,5,8,2,3,9,4]
          µƝ      - perform the chain to the left for adjacent pairs:
                  - i.e. for [a,b] in [[4,5],[5,8],[8,2],[2,3],[3,9],[9,4]]
...               -   perform the code described above = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
   m€2            -   modulo-2 slice €ach = [[1,3],[4,6],[3,9],[1,7],[2,8],[6,9],[1,9],[3,7],[3,1],[6,4],[9,7],[7,1],[8,2],[9,3],[9,1],[7,3],[0]]
      i           -   index of [a,b] in that (or 0 if not there)    e.g. [0,0,13,0,6,0]
        ®         -   recall from register = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
       ị          -   index into (1-based & modular)     e.g. [0,0,[8,5,2],0,[3,6,9],0]
         o        -   OR [a,b]           e.g. [[4,5],[5,8],[8,5,2],[2,3],[3,6,9],[9,4]]
            F     - flatten                          e.g. [4,5,5,8,8,5,2,2,3,3,6,9,9,4]
             Q    - deduplicate                                    e.g. [4,5,8,2,3,6,9]
              ⁼   - equal to the input?                            e.g. 0 (here because 6 was introduced AND because 4 was removed from the right)
                Ȧ - any and all? (0 if input is empty [or contains a falsey value when flattened - no such input], 1 otherwise)
               ȧ  - AND (to force an empty input to evaluate as 1 AND 0 = 0)
Джонатан Аллан
источник
Как получается 19 байтов, когда есть куча символов Юникода?
Изката
@Izkata Jelly использует свою собственную кодовую страницу, которую вы можете увидеть, нажав «байты» в заголовке. В своей необработанной байтовой форме каждый из символов Unicode, которые вы видите в исходном коде, представляет собой только один байт.
Джонатан Аллан
15

Stax , 28 байт

æ¡_t¿♂≥7▼├öä▒╨½╧£x╪╨┌i╒ë╖¢g•

Запустить его

Это производит 0 для ложного, и положительные целые числа для истинного. Соответствующее представление ascii той же программы таково.

cu=x%v*x2BF1379E-%_|+YA=!*yhxi(#+*

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

cu=                                 First: no duplicates
   x%v*                             Second: length of input minus 1
       x2B                          Get all adjacent pairs  
          F                         For each pair, execute the rest
           1379E-%                  a) Any digits that are not 1, 3, 7, 9?
                  _|+Y              Get sum of pair, and store in Y register
                      A=!           b) Sum is not equal to 10?
                         *          c) multiply; logical and: a, b
                          yh        half of y; this will be equal to the
                                        number directly between the current
                                        pair if there is one
                            xi(#    d) has the middle number been observed yet?
                                +   e) plus; logical or: c, d
                                 *  multiply by the accumulated value so far
рекурсивный
источник
Умное использование Yреестра.
Вейцзюнь Чжоу
Еще одна проблема на GitHub.
Вейцзюнь Чжоу
1
По совпадению я уже исправил эту ошибку, но не развернул ее до сих пор. (это не влияет на мою программу)
рекурсивный
1
Это может звучать странно, но вы можете отбросить первое vи включить в 1качестве ложного значения. 2и выше правдивы.
Вейцзюнь Чжоу
10

JavaScript, 112 байт

x=>/^(?!.*(.).*\1|[^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93))../.test(x)

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

Благодаря Нилу, измените, )(?!чтобы |сохранить 3 байта.

ТТГ
источник
@ WeijunZhou Я получил правду за 213, что не так?
TSH
Ничего плохого, извините за это.
Вейцзюнь Чжоу
Теперь, так как ОП выяснил, не удается 144.
Вейцзюнь Чжоу
1
@ WeijunZhou должно быть исправлено; Еще 2 байта ...
Tsh
Если вам интересно, порт Retina 0.8.2 работает на 98 байт.
Нейл
6

Сетчатка 0.8.2 , 98 байт

Под влиянием ответа ТШ . Я попытался «перефразировать» его, чтобы он был противоположным, сопоставляя недопустимые пролистывания, затем «Anti-grepping».

A`(.).*\1|^([^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93)|.$)

Попробуйте онлайн

mbomb007
источник
6

Шелуха , 25 20 байт

S=öufΛ¦1ΣẊ§Jzo½+em‰3

Принимает список целых чисел с индексацией на основе 0. Возвращает 0 или 1. Попробуйте онлайн!

объяснение

Я украл некоторые идеи из ответа Jonathan Allan's Jelly . Идея та же: вставьте новый «средний узел» между каждой соседней парой, отфильтруйте те, которые не являются реальными узлами, удалите дубликаты и сравните с исходным списком. Если исходный список содержит дубликаты, результат ложный. Если список пропускает не посещенный узел, то он присутствует в обработанном списке между соответствующей парой, и результатом является ложь. Если входные данные являются одноэлементными, обработанный список будет пустым, и результат будет ложным. В противном случае это правда.

S=öufΛ¦1ΣẊ§Jzo½+em‰3  Implicit input, say [0,4,6,7,1]
                 m‰3  Divmod each by 3: L = [[0,0],[1,1],[2,0],[2,1],[0,1]]
         Ẋ§Jzo½+e     This part inserts the middle node between adjacent nodes.
         Ẋ            Do this for each adjacent pair, e.g. [1,1],[2,0]:
          §           Apply two functions and combine results with third.
            zo½+      First function:
            z         Zip with
               +      addition,
             o½       then halve: N = [3/2,1/2]
                e     Second function: pair: P = [[1,1],[2,0]]
           J          Combining function: join P with N: [[1,1],[3/2,1/2],[2,0]]
                      Result is a list of such triples.
        Σ             Concatenate: [[0,0],[1/2,1/2],[1,1],[1,1],[3/2,1/2],...,[0,1]]
    f                 Keep only those pairs
     Λ                both of whose elements
      ¦1              are divisible by 1, i.e. are integers: [[0,0],[1,1],[1,1],,...,[0,1]]
   u                  Remove duplicates: [[0,0],[1,1],[2,0],[2,1],[0,1]]
S=ö                   Is the result equal to L? Implicitly print 1 or 0.
Zgarb
источник
3

C ++, 267 256 байт

#define R)return 0
#define H(a,q)if(d==q&&n==a&&!m[a]R;
int v(int s[],int l){if(l<2 R;int m[10]{},i=1,p=s[0],d,n;for(;i<l;++i){m[p]=1;if(m[s[i]]R;d=(d=p-s[i])<0?-d:d;if(d%2<1){n=(p+s[i])/2;H(5,4)H(5,8)H(2,2)H(5,2)H(8,2)H(4,6)H(5,6)H(6,6)}p=s[i];}return 1;}

Чтобы проверить, не пропускает ли шаблон невидимый узел, он выполняет несколько вещей:

  1. Вычислить, dгде dнаходится числовая разница между текущим узлом и последним узлом.
  2. Если dэто нечетно, тогда нет необходимости проверять, он не может пропустить узел.
  3. Если dравно 4или 8, то переход между узлами 1-9или 3-7, так что проверьте узел5
  4. Если dравно 2, а средний узел ( (last_node + current_node)/2) равен 2,5 или 8, то проверьте средний узел
  5. Если d6, то же, что и раньше, но с 4, 5или6

Параметры - int[]это количество элементов. Возвращает, intкоторый можно интерпретировать как boolтип

HatsuPointerKun
источник
!(d%2)=> d%2<1должно работать.
Захари
256 байтов
Zacharý
Я узнал новый трюк: int s[]=> int*s. Я думаю, что это сработает.
Захари
2

Perl, 135 байт (134+ -n)

@a{split//}=1;(@{[/./g]}==keys%a&&/../)||die();for$c(qw/132 465 798 174 285 396 195 375/){$c=~/(.)(.)(.)/;/^[^$3]*($1$2|$2$1)/&&die()}

Слегка негольфированная версия

@a{split//} = 1;
(@{[/./g]} == keys %a && /../) || die();
for $c (qw/132 465 798 174 285 396 195 375/) {
  $c=~/(.)(.)(.)/;
  /^[^$3]*($1$2|$2$1)/&&die()
}

Выходы через код выхода. 0правда, любая другая ценность ложная. Согласно мета-консенсусу , вывод STDERR в случае сбоя игнорируется.

Вероятно, есть более быстрый способ проверить правило «не перепрыгнуть», чем просто перечислить все возможности.

Сильвио Майоло
источник
2

MATL , 42 41 39 байт

9:IeXKi"Ky@=&fJ*+XK+y&fJ*+Em~zw0@(]z8<v

Это производит

  • непустой вектор-столбец, содержащий только ненулевые числа в качестве достоверного вывода; или же
  • непустой вектор-столбец, содержащий по крайней мере ноль в качестве фальсификации.

Здесь вы можете прочитать, почему эти выводы являются соответственно правдивыми и ложными. Попробуйте онлайн!

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

Луис Мендо
источник
2

Stax , 73 72 66 65 байт CP437

ÉWyƒ▬ºJOTƒw-H┌↓&ⁿç↨¼<ü6π║¢S○j⌂zXΣE7≈╩╕╤ö±÷C6▒☼■iP-↑⌐¥]╩q|+zΦ4Φ·¥Ω

79 байт при распаковке,

d4{cAs-5F132396978714EEL3/{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEx%2<xu%x%=!L|+

Запускать и отлаживать онлайн!

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

Внедрение без использования hash.Outputs строго положительное число ( на самом деле количество неудачных испытаний) для falsy случаев и 0для truthy них.

объяснение

dочищает входной стек В xлюбом случае, входные данные являются переменными .

4{cAs-5F генерирует первую часть списка среднего узла.

132396978714EE жестко кодирует вторую часть списка средних узлов.

L3/Собирает все элементы в главном стеке и делит на части, каждая из которых содержит 3 элемента, в результате получается массив a, который является просто массивом всех недопустимых групп из 3 узлов.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEДля каждого неверного списка узлов выполните следующие проверки. Результат проверки проверяется andс помощью **. Поскольку существует 8 недопустимых списков узлов, результатом этого кода будет массив из 8 элементов. Финал Eотправляет массив отдельным элементам в главном стеке.

xs:I получить индекс элементов списка узлов во входном массиве.

Bc0<A*++Если индекс «среднего узла» (например, 5в наборе узлов 1,5,9) равен -1(что означает, что он не существует во входном массиве), измените индекс на 9.

cEd:-1=проверить, являются ли два "терминальных узла" (например, 1,5в наборе узлов 1,5,9) смежными во входном массиве.

sccHs|M= проверить, больше ли преобразованный индекс «среднего узла», чем у двух «терминальных узлов», что включает в себя два случая: «средний узел» отсутствует или «средний узел» идет после двух «терминальных узлов»

s{U>m|Aпроверяет, являются ли оба индекса «конечных узлов» неотрицательными. (т.е. они оба появляются на входе).

Два дополнительных теста выполнены,

x%2< проверяет, является ли входной массив одноэлементным.

xu%x%=! проверяет, были ли узлы, которые были посещены дважды.

В главном стеке 10 результатов теста (по одному на каждый из списка недопустимых узлов, плюс два дополнительных теста).

L|+собирает 10 элементов и добавляет их. |aмог также использоваться, который просто проверяет, есть ли какие-либо истинные элементы в массиве.

Неявный вывод.

Вейцзюнь Чжоу
источник
2

Java, 375 355 байт

-20 байт благодаря Захари

int v(int s[]){int[]m=new int[10];int i=1,p=s[0],d,n,l=s.length;if(l<2)return 0;for(;i<l;++i){m[p]=1;if(m[s[i]]!=0)return 0;d=(d=p-s[i])<0?-d:d;if(d%2==0){n=(p+s[i])/2;if((d==4||d==8)&&n==5&&m[5]==0)return 0;if(d==2&&(n==2&&m[2]==0||n==5&&m[5]==0||n==8&&m[8]==0))return 0;if(d==6&&(n==4&&m[4]==0||n==5&&m[5]==0||n==6&&m[6]==0))return 0;}p=s[i];}return 1;}

Это порт этого ответа, и он работает на тех же принципах

HatsuPointerKun
источник
Ого. Вы раздражаетесь на Java.
Захари
int v(int s[]){int[]m=new int[10];int i=1,p=s[0],d,n,l=s.length;if(l<2)return 0;for(;i<l;++i){m[p]=1;if(m[s[i]]!=0)return 0;d=(d=p-s[i])<0?-d:d;if(d%2==0){n=(p+s[i])/2;if((d==4||d==8)&&n==5&&m[5]==0)return 0;if((d==2)&&(n==2&&m[2]==0||n==5&&m[5]==0||n==8&&m[8]==0))return 0;if(d==6&&(n==4&&m[4]==0||n==5&&m[5]==0||n==6&&m[6]==0))return 0;}p=s[i];}return 1;}должен работать (порядок операций)
Zacharý
Вы можете изменить (d==2)на просто d==2, я не замечал этого раньше.
Захари
d%2==0=>d%2<1
Захари
0

Pyth , 33 байта

q{@U9.nm+mc|g1aZksd2-MC.DR3d_dC,t

Тестирование.

Использует индексирование на основе 0.

объяснение

q {@ U9.nm + mc | g1aZksd2-MC.DR3d_dC, t -> Полная программа. Вход: список L из STDIN.

                               , t -> Соединить L с L без первого элемента.
                              C -> Транспонировать.
       m -> Карта списка пар (списки из 2 элементов):
        + mc | g1aZksd2-MC.DR3d -> Функция для отображения (переменная: d):
                         R d -> Для каждого элемента d ...
                       .D 3 -> ... Возьмите его divmod на 3.
                      C -> Транспонировать.
                    -M -> Уменьшить каждый путем вычитания.
         m -> Для каждой разности (переменная: k):
            g1aZl -> Is | k | ≤ 1?
           | sd -> Если это неверно, замените его на сумму d.
          c 2 -> Разделить на 2.
        + _d -> Добавить обратный d к результату отображения.
     .n -> Свести.
  @ U9 -> Возьмите пересечение с (ℤ ∩ [0; 9)).
 {-> Дубликат.
q -> И проверьте, равен ли результат L.

Альтернативный подход для 34 байтов :

q{sI#I#+Fm+,hdcR2+MCd]edCtBK.DR3QK
Мистер Xcoder
источник
0

Japt , 35 байт

eUä@[(Xu3 aYu3)¥1ªX+Y ÷2XY]Ãc f9o)â

Попробуйте онлайн!

Слегка разгромленный и как это работает

eUä@[(Xu3 aYu3)¥1ªX+Y ÷2XY]Ãc f9o)â

Implicit beginning U(input) and some arbitrary sequence conversions

UeUä@[(Xu3 aYu3)==1||X+Y ÷2XY]} c f9o)â

  Uä             Convert the input array into length-2 subsections and map...
    @[ ... ]}      function of X,Y which returns an array of...
      Xu3 aYu3==1||X+Y ÷2          (abs(X%3 - Y%3)==1||X+Y)/2,
                         XY        X, Y
  c              Flatten the result of mapping
    f9o          Intersect with range(9)
        â        Take unique elements, preserving order
Ue             Is the result the same as original array?

Портировал идею из этого решения Jelly , с некоторым различием в определении потенциальных скачков:

  • В ответе Jelly используется divmod, чтобы увидеть, имеет ли пара разницу 2 при применении /3или %3.
  • Этот ответ использует только %3и проверяет, равна ли разница 0 или 2. Если разница равна 0, две ячейки выровнены по вертикали, и непереходы все еще имеют свойство (X+Y)%2 != 0.
фонтанчик для питья
источник
0

Python 2 , 97 байт

Основано на ответе ovs, но на 2 байта короче и менее загадочно. Просто конвертирует индексы в 2d координаты и проверяет четность. Предполагает 0-8 индексов.

v={9}
s=input()
for n,l in zip(s[1:]or q,s):n/3+l/3&1|n%3+l%3&1or n+l>>1in v or q;v|={l};n in v>q

Попробуйте онлайн!

Лучано
источник