Is My Swipe Pattern Legal?

  • Most Android smartphones allow the user to use a swipe pattern to open their phone:



    pattern lock



    Certain patterns are legitimate, and others are impossible. Given an input swipe pattern, return a truthy or falsy indicating if the given input pattern is legal or not.



    Input



    The grid is labelled row-wise 1 through 9:



    1 2 3   
    4 5 6
    7 8 9


    The input is a number comprised of the nodes visited from first to last. For example, the swipe pattern above is 12357.



    Input can be a decimal number, string or list of numbers. It will not contain 0 because there is no node 0.



    Amendment: indexing 0-8 is allowed since a lot of languages index from 0. If you use 0-8, it'll be necessary to indicate as such at the beginning of your answer and adjust the test cases accordingly.



    Rules




    • Every node starts as unvisited initially and may only be visited once. Any pattern which visits a node more than once is falsy.


    • A truthy pattern must contain at least one swipe, so a minimum of 2 nodes.


    • It's not possible to skip over an unvisited node directly in line with another.
      For example, 13 is falsy because 2 is unvisited and directly in line.


    • It is only possible to skip over a visited node. 42631 is an example of this.


    • Lines may cross otherwise. For example, 1524 is truthy.


    • Assume node widths are insignificant and ignore practical issues (finger thickness, etc). So 16 is truthy even though it may be slightly harder to achieve in reality.




    Test Cases



    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


    This is , so the fewest number of bytes wins.


    Is the input list guaranteed to be nonempty?

    @Zgarb yes. It'll be nonempty.

  • JavaScript (ES6), 64 bytes



    Takes input as an array of numbers. Falsy values are 0 or NaN. Truthy values are strictly positive integers.



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


    Test cases





    let f =

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

    console.log('[Truthy]')
    console.log([
    [1,2],
    [1,6],
    [5,8,2],
    [5,1,9],
    [1,2,3,5,7],
    [1,5,7,8,2],
    [1,6,7,2,9,4,3,8,5],
    [4,2,6,3,1],
    [1,5,7,8,4,2],
    [2,9,4,3,8,1,6,7,5]
    ]
    .map(f).join(' '))

    console.log('[Falsy]')
    console.log([
    [1],
    [1,3],
    [3,1],
    [3,3],
    [1,3,7],
    [1,5,4,1],
    [1,9,7,3,5],
    [2,9,7,3,8,1,6,4,5]
    ]
    .map(f).join(' '))





    How?



    Preamble



    Two digits are vertically, horizontally or diagonally opposed if:




    • they are both odd, different from each other and different from 5 (figure 1)

    • OR they are both even and their sum is 10 (figure 2)



      opposed digits




    Besides, the digit standing between two opposed digits n and p is equal to (n + p) / 2.



    Formatted source code



    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
    )


    Keeping track of previous digits



    Flags for visited digits are stored at negative indices in the input array a, so that they don't collide with its original elements.




    • If p is set to -n:



      If the current digit n was not previously selected, a[-n] ^= -n will set the flag and let the every() loop go on with the next iteration. Otherwise, it will clear the flag and force the loop to fail immediately.


    • If p is set to undefined:



      a[undefined] ^= undefined results in 0, which also forces the loop to fail.




    Detecting opposed digits



    The following expression is used to test whether the current digit n and the previous digit -p are opposed digits, as defined in the preamble:



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


    which is equivalent to:



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


    Note: In JS, the result of the modulo has the same sign as the dividend.



    It can be interpreted as:



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


    Therefore, this expression returns 1 if and only if n and -p are opposed digits or they are the same odd digit. Because a digit can't be selected twice, this latter case is correctly taken care of anyway.



    If this expression returns 1, we test a[p / 2] (where p is now equal to the negated sum of the digits) in order to know whether the 'in-between digit' was previously visited. Otherwise, we test a[0] which is guaranteed to be truthy.



    About the first iteration



    The first iteration is a special case, in that there is no previous digit and we want it to be unconditionally successful.



    We achieve that by initializing p to 1, because for any n in [1 .. 9]:




    • (1 * n) % 5 can't be negative

    • ~(1 - n) can't be equal to 9






    Original answer, 90 bytes



    Removed from this post so that it doesn't get too verbose. You can see it here.


    -1 byte by replacing `!!a[1]&` with `a[1]&&`, since any truthy value can be returned

    @HermanLauenstein Thanks, that seems OK indeed. (Now, `a[1]*` is even shorter.)

    I was desperately trying to think of a formula for `has a node directly in line`, I didn't realise it would be so simple...

    @Neil By looking at the revision history of this post, I'm sure you can tell that I didn't realize that immediately either... :)

    Think you can replace `?a[-n]^=1:0` with `&&a[-n]^=1` for -1, can’t test (on mobile)

    @StanStrum Only `&&(a[-n]^=1)` would work, costing +1 byte.

    @arnauld if you don't mind, would you explain how you chose the original hash function you used for the original solution? Did you apply some specific number-theoretic algorithm to choose the constants and/or the particular multiply-mod-mod construction—or did you engage in trial and error with some prime numbers?

    @SarahG Nothing really sophisticated here. The constants were found by brute-forcing over arbitrary ranges.

  • x86 32-bit machine code, 62 60 bytes



    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


    It receives the length of the list in ecx and a pointer to the first element in edx, and returns the result in al:



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


    There are 8 lines that contain a node in the middle:



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


    I grouped them according to the difference between the bigger and the smaller number.



    Difference 2: 3 lines (starting at 1, 4 or 7)
    1 - 3
    4 - 6
    7 - 9
    Difference 4: 1 line (starting at 3)
    3 - 7
    Difference 6: 3 lines (starting at 1, 2 or 3)
    1 - 7
    2 - 8
    3 - 9
    Difference 8: 1 line (starting at 1)
    1 - 9


    Then, I converted that to a 2-D lookup table indexed by half-difference and smaller number:



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


    This makes a "magic" bitmap of 32 bits. To index it, the code pushes it into the stack. Then, it extracts one byte using one index, and from that byte, it extracts one bit using the other index. All this using one instruction:



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


    If the bitmap indicates that there is a node in the middle, it's easy to calculate - add half the difference to the smaller number.



    Assembly source:



        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

    Nice! I really like this `bt byte ptr [esp + eax], ebx`.

    Nice to see assembly solution :) You can use `cdq` instead of `xor edx, edx` as `eax` is zero. Also, you can fold the `dec eax` into `bt [esp + eax - 1], ebx` which is same length but then allows you to remove the `inc ebx` later. This should save you two bytes.

    Thanks for the ideas! You have secured your place in the golfer's paradise, if there is one :)

    I think we can all agree that Golfers paradise is hell for everyone else.

  • Python 2, 140 131 114 104 99 bytes



    -2 bytes thanks to Jonathan Frech

    -5 bytes thanks to Chas Brown





    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


    Try it online!



    Explanation:





    # 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


    Try it online!



    Only 8 pairs of nodes have a node in between them. A pair of nodes can be represented as a single integer by the formula 2^a-2^b-1. This number can be shortened by repeated modulo:



    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 first checks if such a pair is present, then v-{l+n>>1}==v tests whether the node in between, which is given by (a+b)/2, was not visited yet and q raises a NameError. By using chained comparison between these pairs, the next comparison is only executed when the previous returned True.


  • Jelly,  24 22 19 18  17 bytes




    -2 since we are no longer required to handle an empty list

    -1 switching from join, [email protected], to concatenate, ; (the missed item does not need to be encountered in the middle for the method employed, being at the start of the trio is fine)

    -2 switching from P¬aSH to oSH(OK to have two results since we flatten, half of 1 is 0.5 which is filtered out anyway, and having multiple equal results has no affect on the method employed either)

    -1 Thanks to Mr. Xcoder (0-indexed input is allowed)

    -1 using the (newer) invariance quick, Ƒ, and filter-keep quick alias, Ƈ.



    d3ZIỊoSH;µƝFḞƑƇQ⁼


    A monadic link taking a list of integers in [0,8] and returning a truthy value (1) if legal and a falsey value (0) if not.



    Try it online! or see a test-suite.



    How?



    Looks at each adjacent pair of 0-indexed nodes in the input list. If the integer division by three of the two differs by 2 they are on the top and bottom rows, if the modulo by three of the two differs by 2 they are in the left and right columns. The sum of such pairs divided by two is either the 0-indexed mid-node of a three-node-line or a non-integer value -- so these values are first inserted in-front of the 0-indexed pair and then any bogus nodes (like 0.5 or 3.5) are removed, the resulting list of lists is flattened and then de-duplicated (to yield order-preserved, unique entries) and finally compared to the input - for a legal swipe all of this will end up being a no-op while illegal ones will add missing mid-nodes and/or remove duplicate nodes (note that no special casing is required for an input list of length 1 since it has no adjacent pairs):



    d3ZIỊoSH;µƝFḞƑƇ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]
    Ƈ - keep those for which:
    Ƒ - is invariant under?:
    Ḟ - floor [ 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)





    Previous method



    Jelly,  36  35 bytes



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


    Try it online! or see a test-suite.



    How?



    Similar to the above but constructs all three-node-line possibilities and performs look-up (rather than checking as it goes using divmod to test and halving the sum for the mid-node).



    Firstly the construction of the list of three-node-lines:



    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


    Now the decision making:



    ...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)

    How does it come out to 19 bytes when there's a bunch of unicode characters?

    @Izkata Jelly uses its own code-page, which you can see by clicking "bytes" in the header. In its raw byte-form each of the Unicode characters you can see in the source-code is only a single byte.

  • Stax, 28 bytes



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


    Run it



    It produces 0 for false, and positive integers for true. The corresponding ascii representation of the same program is this.



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


    The general idea is calculate several necessary conditions for legal swipe patterns and multiply them all together.



    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

    Clever use of the `Y` register.

    Another issue on github.

    I coincidentally had already fixed that bug, but hadn't deployed it until just now. (it doesn't affect my program)

    It may sound strange, but you can drop the first `v` and include `1` as falsy value. `2` and above are truthy.

  • JavaScript, 112 bytes



    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)


    Maybe some regex based language should be more shorter. But I don't know.





    f=
    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)

    <input id=i oninput=o.value=(f(i.value)?'':'in')+'valid'> is <output id=o>





    Thanks to Neil, change )(?! to | save 3 bytes.


    @WeijunZhou I got true for 213, what's wrong?

    Nothing is wrong, sorry for it.

    Now since OP clarified, fails for `144`.

    @WeijunZhou should been fixed; 2 more bytes...

    In case you were wondering, a Retina 0.8.2 port seems to work out at 98 bytes.

    Can you not use `|` instead of `)(?!`?

    @Neil I probably got 98 bytes a different way than you did, but I couldn't get it shorter.

    @mbomb007 I failed to save my answer, but I think yours closely resembles it.

    -6: `x=>/.../.test(x)` -> `/.../.test`

    @Makonede js won’t bind the regex to this by default (as what Python do).

  • Husk, 25 20 bytes



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


    Takes a list of integers with 0-based indexing.
    Returns 0 or 1.
    Try it online!



    Explanation



    I stole some ideas from Jonathan Allan's Jelly answer.
    The idea is the same: insert a new "average node" between each adjacent pair, filter out those that are not actual nodes, remove duplicates and compare to the original list.
    If the original list contains duplicates, the result is falsy.
    If the list skips an unvisited node, then it is present in the processed list between the corresponding pair, and the result is falsy.
    If the input is a singleton, the processed list is empty, and the result is falsy.
    Otherwise, it is truthy.



    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.

  • Retina 0.8.2, 98 bytes


    Influenced by tsh's answer. I tried to "rephrase" it to be the opposite, matching invalid swipes, then 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)|.$)

    Try it online


  • C++, 267 256 bytes



    #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;}


    To check if the pattern does not skip over a unvisited node, it does several things :




    1. Calculate d where d is the numerical difference between the current node and the last node.

    2. If d is odd, then there's no need to check, it can't skip over a node.

    3. If d is equal to 4 or 8, then the jump is between nodes 1-9 or 3-7, so check node 5

    4. If d is 2, and the middle node ( (last_node + current_node)/2 ) is either 2,5 or 8, then check the middle node

    5. If d is 6, same check as before but with 4,5 or 6



    The parameters are an int[] and it's element count.
    It returns an int which can be interpreted as a bool type


    `!(d%2)` => `d%2<1` should work.

    I learned a new trick: `int s[]` => `int*s`. I think that'll work.

    212 bytes – Try It Online")

  • Python 2, 97 bytes



    Based on ovs' answer but 2 bytes shorter and less cryptic. Just converts indexes to 2d coordinates and tests parity. Assumes 0-8 indexes.





    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


    Try it online!


License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM