Pairs at every distance

Question

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 code-golf, 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]

Answer 1

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!

Answer 2

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

Answer 3

Rust, 63 bytes

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

Attempt This Online!

Answer 4

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?

Answer 5

J, ¹⁸ 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
  

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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.

Answer 13

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

Answer 14

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!

Answer 15

APL (Dyalog Classic), 15 bytes

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

Try it online!

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

Answer 16

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.

Answer 17

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

Answer 18

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

Answer 19

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)

Answer 20

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.

Answer 21

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

Answer 22

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!

Answer 23

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.

Answer 24

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.

Answer 25

Vyxal, 7 bytes

v=ṘÞḋṠA

Try it Online!

Lyxal never posted my golf, so here goes

Answer 26

Scala, 94 bytes

Golfed version. Try it online!

def f(a:Seq[Int])={var b=a.length;(1 to b).map{i=>(i to b).map{j=>a(j-1)-a(j-i)}.product}.sum}

Ungolfed version. Try it online!

object PariGpToScala {
  def main(args: Array[String]): Unit = {
    val testCases = List(
      List(1, 1),
      List(1, 1, 1),
      List(3, 3, 7, 3),
      List(2, 2, 1, 2, 2),
      List(2, 1, 2, 2, 2),
      List(1, 3, 1, 3, 1, 1),
      List(1, 1, 3, 2, 3, 1, 2, 1),
      List(1, 1, 1, 1, 1, 1, 2, 1),
      List(1, 2),
      List(1, 2, 1),
      List(1, 2, 3, 4),
      List(3, 1, 3, 1, 3),
      List(3, 1, 1, 3, 1),
      List(1, 3, 1, 1, 3, 1),
      List(1, 1, 2, 2, 2, 2, 1, 1),
      List(1, 1, 1, 1, 1, 1, 1, 2)
    )

    testCases.foreach { testCase =>
      println(s"${testCase.mkString("[", ", ", "]")} -> ${f(testCase)}")
    }
  }

  def f(a: List[Int]): Int = {
    (1 to a.length).map { i =>
      (i to a.length).map { j =>
        a(j - 1) - a(j - i)
      }.product
    }.sum
  }
}