23
\$\begingroup\$

Given a list \$X\$ of 2 or more integers, output whether, for all \$n\$ such that \$0 \leq n < length(X)-2\$, there exists a pair of equal integers in \$X\$ separated by exactly \$n\$ elements.

In other words: output whether, for all overlapping slices/windows of the input, there exists at least one slice/window of each length wherein the head of the slice/window equals the tail.

For example: [1, 1, 3, 2, 3, 1, 2, 1] will return truthy, because

[1, x, x, x, x, x, x, 1]
These 1s are separated by 6 elements, the most possible in an 8 element list,

[x, 1, x, x, x, x, x, 1]
These 1s are separated by 5 elements,

[1, x, x, x, x, 1, x, x]
These 1s are separated by 4 elements,

[x, 1, x, x, x, 1, x, x]
These 1s are separated by 3 elements,

[x, x, x, 2, x, x, 2, x]
These 2s are separated by 2 elements,

[x, x, 3, x, 3, 1, x, 1]
These 3s are separated by 1 element (as are the 1s, but either pair is sufficient),

[1, 1, x, x, x, x, x, x]
And these 1s are separated by 0 elements, the least possible.

But [1, 1, 2, 2, 1, 1] will return falsy, as there is no pair of equal elements separated by exactly one element. That is, there is no length 3 slice/window with a head equal to it's tail. See all length 3 slices/windows below:

[1, 1, 2]
   [1, 2, 2]
      [2, 2, 1]
         [2, 1, 1]

Standard I/O applies, input does not have to allow negatives, or input can be a string of characters, etc.

Anything reasonable as long as you're not cheating :)

This is , so shortest code in bytes wins!

Examples

Truthy

[1, 1]
[1, 1, 1]
[3, 3, 7, 3]
[2, 2, 1, 2, 2]
[2, 1, 2, 2, 2]
[1, 3, 1, 3, 1, 1]
[1, 1, 3, 2, 3, 1, 2, 1]
[1, 1, 1, 1, 1, 1, 2, 1]

Falsy

[1, 2]
[1, 2, 1]
[1, 2, 3, 4]
[3, 1, 3, 1, 3]
[3, 1, 1, 3, 1]
[1, 3, 1, 1, 3, 1]
[1, 1, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 2]
\$\endgroup\$
10
  • \$\begingroup\$ input does not have to allow negatives -> May the input contain 0's? \$\endgroup\$
    – Arnauld
    Jul 1 at 13:50
  • 1
    \$\begingroup\$ @Arnauld "etc", only if you want. EDIT: to elaborate; this isn't a challenge about integers so much as it's a challenge about matching pairs in a list. you can use church numerals for all I care :P \$\endgroup\$ Jul 1 at 13:52
  • 1
    \$\begingroup\$ It seems like this problem is also interesting from the perspective of fastest code/algorithm. The best algorithm I could think of is \$ O(n \sqrt{n \log(n)}) \$ \$\endgroup\$ Jul 2 at 14:54
  • \$\begingroup\$ @WheatWizard I don't understand your edit. I think it's wrong, as it seems to imply 1, 1, 3, 2, 3, 1, 2, 1 would return falsy, as 2 3 1 2 and 1 3 2 3 1 dont have the same head/tail (2 vs 1). I also don't see what's gained by using |X| in place of length(X). I'm reverting it for now. EDIT: i see that my original wording also had that mistake. This should be a tad better. Feel free to reword this version, but I still don't agree with using absolute value bars for length. Seems like a barrier for entry. \$\endgroup\$ Jul 3 at 15:15
  • \$\begingroup\$ The pre-existing wording made no sense at all. It used the term "pair" to refer to nothing at all. It is really that there are n pairs of one integer. \$\endgroup\$
    – Wheat Wizard
    Jul 3 at 15:20

25 Answers 25

9
\$\begingroup\$

Jelly, 11 8 6 bytes

Uses inverted boolean output.

IÐƤÄPẸ

Try it online!

 ÐƤ     # Map over each suffix:
I       #   Increments (differences between adjacent elements)
   Ä    # For each list, get cumulative sums
    PẸ  # Is there a zero in each column?

This is basically: Is there a zero on each diagonal of the subtraction table?. The naive implementation would be:

_þ`ŒDP€Ẹ

Try it online!

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

JavaScript (ES6), 39 bytes

Returns a Boolean value.

a=>a.every((_,d)=>a.some(v=>a[d++]==v))

Try it online!

Or 38 bytes with an inverted output, assuming the input list does not contain any 0:

a=>a.some((_,d)=>a.every(v=>a[d++]^v))

Try it online!

Commented

a =>                // given an array a[] of N entries
  a.every((_, d) => // for each distance d = 0 to N - 1:
    a.some(v =>     //   is there some value v at position i (implied) ...
      a[d++] == v   //     ... such that a[i + d] is equal to v?
                    //     (we increment d instead of storing i explicitly)
    )               //   end of some()
  )                 // end of every()
\$\endgroup\$
6
\$\begingroup\$

Vyxal, 12 11 bytes

żƛ?l'ṪǏ⁼;;A

Try it Online!

-1 thanks to EmanresuA but also -10 rep thanks to EmanresuA so now I have to edit the post so the upvote can be returned

Explained

żƛ?l'ṪǏ⁼;;A
żƛ           # For every number n in the range [0, len(input)]
  ?l         #   Overlapping windows of length n of the input
    'ṪǏ⁼;    #   Get all sublists where the list is the same after appending the head of the list to the list with the tail chopped off. That is, `a[:-1] + [a[0]] == a`
         ;   # End map
          A  # Are all the items truthy?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ 11 \$\endgroup\$
    – emanresu A
    Jul 1 at 13:00
  • \$\begingroup\$ @emanresuA that took me a bit to figure out how that worked lol \$\endgroup\$
    – lyxal
    Jul 1 at 13:08
  • \$\begingroup\$ 10 bytes (link does test cases) \$\endgroup\$
    – Steffan
    Jul 2 at 2:30
  • \$\begingroup\$ actually 8 \$\endgroup\$
    – Steffan
    Jul 2 at 2:50
  • \$\begingroup\$ alternative 8 not using inverted booleans \$\endgroup\$
    – Steffan
    Jul 2 at 2:53
5
\$\begingroup\$

J, 18 16 bytes

[:*/[:+.//.@|.e.

Try it online!

-2 thanks to ovs!

Explanation slightly out of date (can't update right now), but idea is same.

Consider 3 3 7 3:

  • -/~ Differences table:

    0 0 _4 0
    0 0 _4 0
    4 4  0 4
    0 0 _4 0
    
  • |. Reversed:

    0 0 _4 0
    4 4  0 4
    0 0 _4 0
    0 0 _4 0
    
  • 0&e./. Is there a zero in each diagonal going this way /:

    1 1 1 1 1 1 1
    
  • [:*/ Are they all 1:

    1
    
\$\endgroup\$
5
  • \$\begingroup\$ WTF that's incredible insight \$\endgroup\$ Jul 1 at 16:18
  • 1
    \$\begingroup\$ =/~ / monadic e. can save a couple bytes \$\endgroup\$
    – ovs
    Jul 1 at 16:19
  • 1
    \$\begingroup\$ @thejonymyster thanks, but note ovs had the same insight as well. \$\endgroup\$
    – Jonah
    Jul 1 at 16:40
  • \$\begingroup\$ @ovs Very nice, thanks! \$\endgroup\$
    – Jonah
    Jul 1 at 16:41
  • 1
    \$\begingroup\$ oh. i did not understand it ^_^; thank you i will have to study further \$\endgroup\$ Jul 1 at 16:41
5
\$\begingroup\$

MATL, 9 8 bytes

Saved one byte thanks to @Luis Mendo

&=T&XdaA

Try it online!

Explanation:

&=        # input == input'
  T       # get all diagonals from...
   &Xd    # spdiags (i.e. rotate matrix 45 degrees)
      a   # `any` applied to columns
       A  # all
\$\endgroup\$
3
  • \$\begingroup\$ @LuisMendo Ooh, I didn't realize that the comparison operators did that! That's a very handy feature. \$\endgroup\$
    – beaker
    Jul 2 at 13:44
  • 1
    \$\begingroup\$ @LuisMendo I was confused about the truthy/falsy definitions since some answers explicitly collapse to a single value at the end and some don't. I may leave it because I like the extra 'a' in 'tadaa!' \$\endgroup\$
    – beaker
    Jul 2 at 13:46
  • 1
    \$\begingroup\$ Also, a single-value result looks neater \$\endgroup\$
    – Luis Mendo
    Jul 2 at 17:56
4
\$\begingroup\$

Rust, 63 bytes

|k:&[u8]|(0..k.len()).all(|z|(z..k.len()).any(|q|k[q-z]==k[q]))

Attempt This Online!

\$\endgroup\$
4
\$\begingroup\$

MATL, 9 bytes

fqG&=&f-m

Outputs a truthy or falsy value, which is allowed by default. Specifically, outputs

  • a non-empty array containing only ones, which is truthy, or
  • an array containing at least a zero, which is falsy.

Try it online! Or verify all test cases, including truthiness/falsihood test.

How it works

     % Implicit input
f    % Find: gives indices of non-zeros. Since the input contains non-zero
     % integers, this gives [1 2 ... n] where n is the input length
q    % Subtract 1, element-wise. Gives [0 1 ... n-1]
G    % Push input again
&=   % Matrix of pairwise equality comparisons
&f   % Two-output find: gives row and column indices of nonzero (i.e. true) entries
-    % Subtract, element-wise
m    % Ismember. This gives an array containing only true (or 1) if 0, 1,... n-1
     % are all contained in the above result (note that 0 will always be contained)
     % Implicit display
\$\endgroup\$
3
\$\begingroup\$

Husk, 10 8 bytes

Πm▲∂↔´Ṫ=

Port of @ovs' second Jelly answer:

Is there a zero on each diagonal of the subtraction table?

-2 bytes thanks to @Steffan, by using this instead:

Is there a 1 on each diagonal of the equality table?

Outputs 1/0 for truthy/falsey respectively.

Try it online.

Explanation:

     ´    # Use the given input-argument twice,
      Ṫ   # to apply double-vectorized, creating a table
       =  # checking for each pair if they're equal
    ↔     # Reverse each inner row
   ∂      # Now pop and take all anti-diagonals of this matrix
          # (`∂↔` basically takes all diagonals of the matrix†)
 m        # Map over each diagonal-list:
  ▲       #  Maximum: check if any value in the diagonal-list is truthy
Π         # Product: check if all are truthy for each diagonal
          # (after which the result is output implicitly)

† Although Husk has an anti-diagonals builtin , it lacks a diagonals builtin. The reason for this is probably because the anti-diagonals can be computed on an infinite matrix, whereas this isn't the case for the diagonals, as assumed by @MartinEnder here.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't actually know husk, but here's 8 bytes. Returns 0 for falsy, and any other integer for truthy. \$\endgroup\$
    – Steffan
    Jul 2 at 3:05
  • \$\begingroup\$ @Steffan Thanks. I've changed the sum to a max to get a consistent 1/0 for truthy/falsey respectively. But smart to use an equality table instead of subtraction table! :) (And since this is only my 7th Husk answer, I honestly don't know Husk either ;p) \$\endgroup\$ Jul 2 at 9:10
3
\$\begingroup\$

05AB1E, 11 9 6 bytes

.s€αPO

Try it online or verify all testcases.

Returns zero if there are pairs at every distance, otherwise returns a non-zero number.

If this output format isn't allowed, it's +1 bytes for adding _ in the end (and then it returns 1 if there are pairs at every distance and 0 otherwise). Alternatively, if you are willing to stretch the output format more you can remove the O in the end, and then it returns a list containing only zeros iff there are pairs at every distance

.s    All suffixes
€     Map each suffix to:
 α    The absolute difference of each value in the suffix from the matching value in the input
P     Product of each list - it's zero iff there's at least one pair of equal elements with distance X
O     Sum - since all values are positive, this is zero iff all values in the map are zero
\$\endgroup\$
2
  • \$\begingroup\$ Smart approach, and great use of 05AB1E's truncating unequal sized lists with that .s€α! (And here is a test suite if you want one.) \$\endgroup\$ Jul 2 at 9:17
  • \$\begingroup\$ @KevinCruijssen thanks! I added the test suite \$\endgroup\$ Jul 2 at 9:28
2
\$\begingroup\$

Python NumPy, 51 bytes

lambda a:all(map((a==[*zip(a)]).trace,a.argsort()))

Attempt This Online!

Takes a numpy array.

How?

Mostly straightforward.zip and argsort are used to avoid the direct numpy import. zip does roughly the same as transpose. The comparison with a creates a boolean table of pairwise incidence. The diagonals of this table are the distance groups. Taking the trace at different offsets returns a positive (hence truthy) value if there is a pair at that distance. argsort seems to be the cheapest way to create the offsets 0,...,n-1 not necessarily in order but we don't care.

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

Clojure, 137 136 bytes

(defn h[c](loop[n(count c)](if(not(contains?(set(map #(=(first %)(last %))(partition n 1 c)))true))false(if(> n 2)(recur(dec n))true))))

Ungolfed:

(defn head-eq-tail [col]
  (loop [n  (count col)]
    (if (not (contains? (set (map #(= (first %) (last %)) (partition n 1 col))) true))
      false
      (if (> n 2)
        (recur (dec n))
        true))))
\$\endgroup\$
2
2
\$\begingroup\$

Desmos, 43 bytes

f(x)=∑_{y=1}^{x.length}abs(x[y...]-x).min

Uses 0 for truthy, and any other positive integer for falsey.

Try it on Desmos!

\$\endgroup\$
1
  • \$\begingroup\$ You can do (x[y...]-x)^2 instead of abs(x[y...]-x) for -1 byte. \$\endgroup\$
    – Aiden Chow
    Jul 11 at 4:24
2
\$\begingroup\$

Knight, 91 bytes

;=l~1;W E++'=x'=l+1l'P'1;=aT;=wF;W<=w+1w l;=bF;=s~1;W<=s+1s-l w=b|b?E+'x'sE+'x'+s w=a&a bOa

Enter each number in the input list on their own line, with a trailing newline.

Try It Online!

Also made a test suite cuz I'm bored lol

(Basically equivalent Python code: Try It Online!)

\$\endgroup\$
4
  • \$\begingroup\$ Congrats on figuring out semicolon! lol \$\endgroup\$
    – Steffan
    Aug 9 at 15:14
  • \$\begingroup\$ The trailing newline is only necessary in the JS interpreter. If you use the others it will be fine \$\endgroup\$
    – Steffan
    Aug 9 at 15:15
  • \$\begingroup\$ @Steffan Well I still don't really understand what it does but I found a reliable way to figure out where to put semicolons through a lot of trial and error. Basically, for every "indentation level" (like in python), put a semicolon in front of every statement except for the last statement in that indentation level. Seems to work so far. \$\endgroup\$
    – Aiden Chow
    Aug 10 at 2:44
  • \$\begingroup\$ Yes, that's exactly how you use it \$\endgroup\$
    – Steffan
    Aug 10 at 2:45
1
\$\begingroup\$

R, 56 bytes

\(x,n=seq(x),`?`=Map)any(\(i)all(\(j)x[j]-x[i+j]?n)?n-1)

Attempt This Online!

Outputs FALSE for truthy and NA for falsey.

\$\endgroup\$
1
\$\begingroup\$

C (clang), 78 bytes

h;r;d;i;f(*t,n){for(r=1,d=n;--d;r&=h)for(h=i=0;i+d<n;)h|=t[i]==t[i+++d];*t=r;}

Try it online!

Inputs a pointer to an array of integers and its length (because poiters in C carry no length info).
Returns, through the input pointer, \$1\$ if the array has pairs at every distance or \$0\$ otherwise.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 15 bytes

⊙θ⬤θ∨‹μκ⁻λ§θ⁻μκ

Try it online! Link is to verbose version of code. Outputs an inverted Charcoal boolean, i.e. - if there is a distance with no pair, nothing if there is a pair at every distance. Explanation:

 θ              Input array
⊙               Any distance satisfies
   θ            Input array
  ⬤             Every element satisfies
      μ         Current index
     ‹          Is less than
       κ        Current distance
    ∨           Logical Or
         λ      Current value
        ⁻       Does not equal
           θ    Input array
          §     Indexed by
             μ  Current index
            ⁻   Subtract
              κ Current distance
                Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Desmos, 63 bytes

k=l.length
f(l)=0^{∏_{n=2}^k∑_{i=n}^k0^{(l[i-n+1]-l[i])^2}}

Returns 0 if truthy, 1 if falsey.

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 12 bytes

āsŒʒ¬Qθ}€gêQ

I have the feeling this can be shorter. EDIT: And it defintely can: see @CommandMaster's 05AB1E answer, halve the size of mine.

I do like how this challenge can be done with a lot of different approaches, though.

Try it online or verify all test cases.

Explanation:

ā         # Push a list in the range [1, (implicit) input-length]
 s        # Swap so the input-list is at the top
  Π      # Pop and get all its sublists
   ʒ      # Filter this list of sublists by:
    ¬Qθ   #  Check if the first and last items are the same:
    ¬     #   Get the first item (without popping the list)
     Q    #   Check for each item if it's equal to this first item
      θ   #   Then pop and push the last check
   }€     # After the filter: map over each remaining sublist:
     g    #  Pop and push the length
      ê   # Sorted-uniquify this list of lengths
       Q  # Check if it's equal to the [1,length] list we created initially
          # (after which the result is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

Pyth, 13 12 bytes

*FsMqVRQ>LQU

Try it online! -- Truthy test suite -- Falsy test suite

Outputs zero for false, non-zero for true.

Pretty much a port of Command Master's 05AB1E answer but double the length :/

Pyth has a prefix function (._) but no suffix function, so building the suffixes costs a few extra bytes with >LQU.

\$\endgroup\$
1
\$\begingroup\$

R, 90 bytes

\(x,l=length,n=l(x),m=1:n)l(table(abs(outer(m,m,Vectorize(\(a,b)(x[a]==x[b])*(a-b))))))==n

Attempt This Online!

Just checking that all distances are represented in the matrix of distances (where elements are zeroed for non-matches).

\$\endgroup\$
1
\$\begingroup\$

Julia

52 bytes

!X=0:length(X)-1⊆[I[1]-I[2] for I=findall(X.==X')]

Attempt This Online!

45 bytes - thanks to @MarcMush

!X=keys(X)⊆findall(X.==X').|>x->x[1]-x[2]+1

Attempt This Online!

\$\endgroup\$
1
1
\$\begingroup\$

x86 32-bit machine code, 18 bytes

57 89 D7 49 AF 60 89 D6 F2 A7 61 E1 F7 0F 94 C0 5F C3

Try it online!

Following the fastcall calling convention, this takes the length of an array of 32-bit integers in ECX and its address in EDX, and returns 0 or 1 in AL.

In assembly:

f:  push edi      # Save EDI onto the stack.
    mov edi, edx  # Set EDI to the array address.
    dec ecx       # Subtract 1 from the length in ECX.
r:  scasd         # Advance EDI, also performing an unnecessary comparison.
    pusha         # Push all the registers onto the stack.
    mov esi, edx  # Set ESI to the array address.
                  # The distance between EDI and ESI increases each iteration.
    repne cmpsd   # Compare values at addresses EDI and ESI and advance both,
                  #  repeating ECX times but stopping if they are equal.
    popa          # Restore all registers' values from the stack.
    loopz r       # Subtract 1 from ECX, and jump back if it's nonzero
                  #  and the result of the last comparison is equal.
    setz al       # Set AL based on whether the result of the last comparison is equal.
    pop edi       # Restore the value of EDI from the stack.
    ret           # Return.
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 15 bytes

0∊1⊥⍳∘≢↓⍤¯1∘.=⍨

Try it online!

Returns 0 if there are such pairs, and 1 otherwise.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 7 bytes

v=ṘÞḋṠA

Try it Online!

Lyxal never posted my golf, so here goes

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

PARI/GP, 41 bytes

a->sum(i=1,#a,prod(j=i,#a,a[j]-a[j-i+1]))

Attempt This Online!

Returns 0 for truthy, other integers for falsy.

\$\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.