154
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Feb 12 '18 at 9:00
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ – 0 ' Feb 12 '18 at 9:15
  • \$\begingroup\$ Is the input list guaranteed to be nonempty? \$\endgroup\$ – Zgarb Feb 13 '18 at 20:55
  • \$\begingroup\$ @Zgarb yes. It'll be nonempty. \$\endgroup\$ – stanri Feb 14 '18 at 5:42
  • \$\begingroup\$ Related maths question: math.stackexchange.com/questions/205049/… \$\endgroup\$ – Pureferret Feb 15 '18 at 11:40

16 Answers 16

69
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ -1 byte by replacing !!a[1]& with a[1]&&, since any truthy value can be returned \$\endgroup\$ – Herman L Feb 12 '18 at 10:30
  • \$\begingroup\$ @HermanLauenstein Thanks, that seems OK indeed. (Now, a[1]* is even shorter.) \$\endgroup\$ – Arnauld Feb 12 '18 at 10:36
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – Neil Feb 12 '18 at 15:53
  • \$\begingroup\$ @Neil By looking at the revision history of this post, I'm sure you can tell that I didn't realize that immediately either... :) \$\endgroup\$ – Arnauld Feb 12 '18 at 16:00
  • \$\begingroup\$ Think you can replace ?a[-n]^=1:0 with &&a[-n]^=1 for -1, can’t test (on mobile) \$\endgroup\$ – Stan Strum Feb 13 '18 at 0:15
45
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice! I really like this bt byte ptr [esp + eax], ebx. \$\endgroup\$ – Arnauld Feb 12 '18 at 16:19
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – Jester Feb 14 '18 at 0:56
  • \$\begingroup\$ Thanks for the ideas! You have secured your place in the golfer's paradise, if there is one :) \$\endgroup\$ – anatolyg Feb 14 '18 at 19:56
  • 5
    \$\begingroup\$ I think we can all agree that Golfers paradise is hell for everyone else. \$\endgroup\$ – Adonalsium Feb 16 '18 at 13:44
19
\$\begingroup\$

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.

\$\endgroup\$
17
\$\begingroup\$

Jelly,  24 22 19  18 bytes

-2 since we are no longer required to handle an empty list
-1 switching from join, j@, 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)

d3ZIỊoSH;µƝFf9Ḷ¤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;µƝ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)

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)
\$\endgroup\$
  • \$\begingroup\$ How does it come out to 19 bytes when there's a bunch of unicode characters? \$\endgroup\$ – Izkata Feb 18 '18 at 20:58
  • \$\begingroup\$ @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. \$\endgroup\$ – Jonathan Allan Feb 18 '18 at 21:06
15
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Clever use of the Y register. \$\endgroup\$ – Weijun Zhou Feb 13 '18 at 7:42
  • \$\begingroup\$ Another issue on github. \$\endgroup\$ – Weijun Zhou Feb 13 '18 at 7:51
  • 1
    \$\begingroup\$ I coincidentally had already fixed that bug, but hadn't deployed it until just now. (it doesn't affect my program) \$\endgroup\$ – recursive Feb 13 '18 at 8:16
  • 1
    \$\begingroup\$ It may sound strange, but you can drop the first v and include 1 as falsy value. 2 and above are truthy. \$\endgroup\$ – Weijun Zhou Feb 13 '18 at 14:12
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @WeijunZhou I got true for 213, what's wrong? \$\endgroup\$ – tsh Feb 12 '18 at 9:36
  • \$\begingroup\$ Nothing is wrong, sorry for it. \$\endgroup\$ – Weijun Zhou Feb 12 '18 at 9:38
  • \$\begingroup\$ Now since OP clarified, fails for 144. \$\endgroup\$ – Weijun Zhou Feb 12 '18 at 9:45
  • 1
    \$\begingroup\$ @WeijunZhou should been fixed; 2 more bytes... \$\endgroup\$ – tsh Feb 12 '18 at 9:47
  • \$\begingroup\$ In case you were wondering, a Retina 0.8.2 port seems to work out at 98 bytes. \$\endgroup\$ – Neil Feb 12 '18 at 13:22
6
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ !(d%2) => d%2<1 should work. \$\endgroup\$ – Zacharý Mar 29 '18 at 13:53
  • \$\begingroup\$ 256 bytes \$\endgroup\$ – Zacharý Nov 13 '18 at 15:49
  • \$\begingroup\$ I learned a new trick: int s[] => int*s. I think that'll work. \$\endgroup\$ – Zacharý Nov 14 '18 at 13:07
2
\$\begingroup\$

Perl, 135 bytes (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()}

Slightly ungolfed version

@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()
}

Outputs via exit code. 0 is truthy, any other value is falsy. As per meta consensus, STDERR output in the failure case is ignored.

There's probably a quicker way to check the "can't jump over" rule than simply listing all the possibilities.

\$\endgroup\$
2
\$\begingroup\$

MATL, 42 41 39 bytes

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

This produces

  • a non-empty column vector containing only non-zero numbers as truthy output; or
  • a non-empty column vector containing at least a zero as falsy.

Here you can read why these outputs are respectively truthy and falsy. Try it online!

Or verify all test cases, with footer code that includes the standard test for truthiness/falsiness.

\$\endgroup\$
2
\$\begingroup\$

Stax, 73 72 66 65 bytesCP437

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

79 bytes when unpacked,

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

Run and debug online!

or run the batch test, where meX is a header so that Stax can process multiline input.

Implementation without using hash.Outputs strictly positive number (actually the number of failed tests) for falsy cases and 0 for truthy ones.

Explanation

d clears the input stack. The input is in variable x anyway.

4{cAs-5F generates first part of the middle-node list.

132396978714EE hardcodes the second part of the middle-node list.

L3/ Collects all elements in main stack and divide into parts each containing 3 elements, the result is array a, which is just the array of all invalid 3-node groups.

{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mE For each invalid node list, perform the following checks. The result of the check results are anded using the **. Since there are 8 invalid node lists, the result of this code will be an array of 8 elements. The final E dispatches the array to its individual elements on the main stack.

xs:I get the index of the node list elements in the input array.

Bc0<A*++ If the index of "middle node" (e.g. 5 in the node set 1,5,9) is -1 (which means it doesn't exist in the input array), change the index to 9.

cEd:-1= test whether the two "terminal nodes" (e.g. 1,5 in the node set 1,5,9) are adjacent in the input array.

sccHs|M= test whether the transformed index of the "middle node" is larger than those of the two "terminal nodes", which includes two cases: the "middle node" is missing, or the "middle node" comes after the two "terminal nodes"

s{U>m|A tests whether both indexes of the "end nodes" are nonnegative. (i.e. they both appear in the input).

Two additional tests are performed,

x%2< tests whether the input array is a singleton.

xu%x%=! tests whether are nodes that have been visited twice.

There are 10 test result on the main stack (one for each of the invalid node list, plus two additional tests).

L|+ collects the 10 elements and adds them. |a could have also been used which simply checks whether there are any truthy elements on the array.

Implicit output.

\$\endgroup\$
2
\$\begingroup\$

Java, 375 355 bytes

-20 bytes thanks to Zacharý

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

This is a port of this answer and it works on the same principles

\$\endgroup\$
  • \$\begingroup\$ Woah. You're anwering in Java. \$\endgroup\$ – Zacharý Feb 23 '18 at 3:18
  • \$\begingroup\$ 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;} should work (order of operations) \$\endgroup\$ – Zacharý Feb 23 '18 at 3:20
  • \$\begingroup\$ You can change (d==2) to just d==2, I overlooked that before. \$\endgroup\$ – Zacharý Mar 9 '18 at 16:34
  • \$\begingroup\$ d%2==0 => d%2<1 \$\endgroup\$ – Zacharý Mar 29 '18 at 13:54
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 33 bytes

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

Test suite.

Uses 0-based indexing.

Explanation

q{@U9.nm+mc|g1aZksd2-MC.DR3d_dC,t –> Full program. Input: a list L from STDIN.

                               ,t –> Pair L with L without the first element.
                              C   –> Transpose.
       m                          –> Map over the list of pairs (2-element lists):
        +mc|g1aZksd2-MC.DR3d      –> The function to be mapped (variable: d):
                         R d          –> For each element of d ...
                       .D 3           –> ... Take its divmod by 3.
                      C               –> Tranpose.
                    -M                –> Reduce each by subtraction.
         m                            –> For each difference (variable: k):
            g1aZl                     –> Is |k| ≤ 1?
           |     sd                   –> If that's falsy, replace it by the sum of d.
          c        2                  –> Divide by 2.
        +                   _d    –> Append the reverse of d to the result of mapping.
     .n                           –> Flatten.
  @U9                             –> Take the intersection with (ℤ ∩ [0; 9)).
 {                                –> Deduplicate.
q                                 –> And check whether the result equals L.

Alternative approach for 34 bytes:

q{sI#I#+Fm+,hdcR2+MCd]edCtBK.DR3QK
\$\endgroup\$
0
\$\begingroup\$

Japt, 35 bytes

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

Try it online!

Slightly ungolfed & How it works

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?

Ported the idea from this Jelly solution, with some difference in determining potential jumps:

  • The Jelly answer uses divmod to see if a pair has difference of 2 when applied /3 or %3.
  • This answer uses only %3 and checks if the difference is 0 or 2. If the difference is 0, the two cells are vertically aligned, and non-jumps still share the property of (X+Y)%2 != 0.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.