10
\$\begingroup\$

Given a non-empty list/vector of positive integers, write a function to check the following conditions in as few bytes as possible.

  1. Take the first integer (the key, or k1) and check that the next k1 values have no duplicate values, excluding instances of k1.
  2. Take the last integer (the second key, or k2) and check that the k2 values before k2 have no duplicate values, excluding instances of k2.

Note that both keys, k1 and k2, are elements of the list/vector as either key could contain the other.

Also, k1 and/or k2 can be greater than the number of integers within the list, which means you should check every element of the list except for instances of the given key for duplicates.

If both steps return True, return True, else, return False.

NOTE: It should be rather intuitive that searching for duplicates within the first k1+1 elements excluding instances of k1 will exclude the first element, or k1. Some answers I've seen "pop" k1 off the list and do the test on the next k1 elements. Either method yields the same results. This is also true for k2 and it's test.

Test Cases

[5,1,2,5,3,4,3] is TRUE because [k1=5][1,2,5,3,4] has no duplicates, nor does [5,3,4][k2=3] have any duplicates, excluding instances of k3. 

[6,9,12,15,18,19,8,8,3] is FALSE because [k1=6][9,12,15,18,19,8] has no duplicates while [19,8,8][k2=3] has a duplicate.

[100,100,100,100,101,102,3] is TRUE because [k1=100][100,100,100,101,102,3] has no duplicates, and [100,101,102][k2=3] has no duplicates.

[100,100,100,100,101,102,4] is FALSE. [k1=100][100,100,100,101,102,4] has no duplicates, but [100,100,101,102][k2=4] has duplicates.

[6,6,6,6,6,6,6,3,3,3,3] is TRUE. [k1=6][6,6,6,6,6,6] has no duplicates, excluding instances of k1, and [3,3,3][k2=3] has no duplicates, excluding instances of k2.

[1,2] is TRUE (clearly)

[1] is TRUE (clearly)
\$\endgroup\$
8
  • 8
    \$\begingroup\$ I would argue that the empty list falls under "undefined behavior" since there is no "first" or "last" element to look at! \$\endgroup\$
    – Value Ink
    Jan 4, 2020 at 1:18
  • 1
    \$\begingroup\$ Can you expand upon why [3, 3, 3] "has no duplicates"? It naively seems to me that there are at least 2 3s, so I would say that's a duplicate. \$\endgroup\$
    – Chas Brown
    Jan 4, 2020 at 6:26
  • 4
    \$\begingroup\$ @ChasBrown I think this part should be made a bit more explicit, but the important point here is that the value of the key (\$3\$ in this example) is always excluded from the test (see: excluding k1 and excluding k2). \$\endgroup\$
    – Arnauld
    Jan 4, 2020 at 9:49
  • 2
    \$\begingroup\$ Okay that's better! \$\endgroup\$
    – Chas Brown
    Jan 5, 2020 at 6:58
  • \$\begingroup\$ @ValueInk and others, if I update the challenge so that the empty list is undefined, would that change anyone's answers? I could make it self-defined, where the users answer could be any type of answer, False, True, or undefined. Thoughts? \$\endgroup\$
    – Sumner18
    Jan 6, 2020 at 14:16

11 Answers 11

4
\$\begingroup\$

JavaScript (ES6),  88 75 71  69 bytes

a=>(g=_=>!a.reverse().some(o=(v,i,[k])=>v-k&&o[v]&(o[v]=i<=k)))()&g()

Try it online!

Commented

The function \$g\$ reverses the input array and performs the test with the resulting leading key.

g= _ =>               // g takes no explicit input
  !a.reverse()        // reverse the input array a[]
  .some(o =           // we use the object o to store encountered values
    (v, i,            // for each value v at position i in a[],
           [k]) =>    // with k = leading value:
      v - k &&        //   abort if v is equal to the key
      o[v] &          //   otherwise, test whether o[v] is already set
      (o[v] = i <= k) //   and i is less than or equal to the key,
                      //   in which case o[v] is set
  )                   // end of some()

The main function simply invokes \$g\$ twice.

a => g() & g()
\$\endgroup\$
3
  • \$\begingroup\$ I thought I could read JavaScript okay. I thought wrong. \$\endgroup\$
    – Sumner18
    Jan 3, 2020 at 22:51
  • \$\begingroup\$ Syntactically, what is happening here: .some(o = ? A callback function is expected -- why is it ok to use an assignment to a callback instead? \$\endgroup\$
    – Jonah
    Jan 8, 2020 at 4:40
  • 1
    \$\begingroup\$ @Jonah In JavaScript, assignments are a type of expression, and such "assignment expressions" evaluate to the value being assigned. In this case, o=()=>{} is an expression evaluating to a function value, which is passed as an argument to .some(). \$\endgroup\$
    – darrylyeo
    Jan 8, 2020 at 4:57
3
\$\begingroup\$

Jelly, 12 bytes

,Uḣ⁹ḟQƑʋḢ$€Ạ

Try it online!

A monadic link taking a list of integers and returning a Jelly Boolean (1 for True, 0 for False).

Explanation

,U            | Pair with reversed list
       ʋḢ$€   | For each pair, do the following as a dyad using the popped head as the right argument y:
  ḣ⁹          | - First y integers
    ḟ         | - Filter out y
     QƑ       | - Check if invariant when uniquified
           Ạ  | All
\$\endgroup\$
3
\$\begingroup\$

Python 2, 95 88 75 74 bytes

lambda x:all(A[:A[0]+1].count(a)<2for A in[x,x[::-1]]for a in A if a-A[0])

Try it online!

7 bytes saved thx to Jo King; then 8 more thx to Value Ink; and then 5 more from Jo King; and 1 byte thx to mypetition pointing out an extra space.

Function taking a list of ints; returns False/True.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'm pretty sure you can check in A instead of in A[:A[0]+1] to save 8 bytes. You're only counting entries within the slice anyways, so if the same value is outside the slice, it's not going to affect the count either way. (Same goes for the alternate answer, which saves 3 bytes.) \$\endgroup\$
    – Value Ink
    Jan 8, 2020 at 0:21
  • \$\begingroup\$ @ValueInk and Jo King: Thanks, gentle-persons! \$\endgroup\$
    – Chas Brown
    Jan 8, 2020 at 3:28
  • \$\begingroup\$ Your code has a useless trailing space, so you actually have a score of 74. \$\endgroup\$
    – mypetlion
    Jan 8, 2020 at 22:01
2
\$\begingroup\$

Charcoal, 31 bytes

∨¬⮌θ⬤E⟦⮌θθ⟧✂⮌ι⁰⊟ι¹⬤ι∨⁼№ιλ¹⁼λ§ι⁰

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, which is - for true and nothing for false. Explanation:

∨¬⮌θ

If the reversed list is empty then the result is true. (Don't ask me why I need to reverse the list first... I think the implicit input uses a subtly different data type or something.)

⬤E⟦⮌θθ⟧

Check the list both backwards and forwards.

✂⮌ι⁰⊟ι¹

Slice the last n elements of the reversed list where n is the last element.

⬤ι∨⁼№ιλ¹⁼λ§ι⁰

Check that each element is either unique or equal to the first element.

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

Python 3.8 (pre-release), 138 \$\cdots\$ 102 91 bytes

lambda x:all(len(set(t:=[e for e in l[1:l[0]+1]if e-l[0]]))==len(t)for l in[x,x[::-1]]if l)

Try it online!

Saved 11 bytes thanks to @JoKing!!!

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

Perl 5 -MList::Util=uniq,head -pF,, 71 66 bytes

sub b{(@_=grep$_-@_[0],head$_[0]+1,@_)==uniq@_}$_=b(reverse@F)*b@F

Try it online!

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

Ruby, 64 56 bytes

Mimics the JavaScript answer in that it takes a helper function and checks the array and its reversed version, but the check for uniqueness is done by taking the subarray based on the key, removing all copies of the key, then checking if the (modified) subarray matches its deduplicated version.

-8 bytes by improving the empty list check, and golfing the deduplication code.

->a{g=->f=0,*a{a=a[0,f]-[f];a&a==a};g[*a]&g[*a.reverse]}

Try it online!

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

05AB1E, 13 bytes

‚εć©£®KDÙQ}P

Port of @NickKennedy's Jelly answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

            # Bifurcate the (implicit) input-string; short for Duplicate & Reverse copy
 ‚           # Pair this reversed input with the duplicated input
  ε          # Map over the inner lists of this pair:
   ć         #  Extract the head; pop and push remainder-list and first item
    ©        #  Store this head in variable `®` (without popping)
     £       #  Leave the first `®` items from the remainder-list
      ®K     #  Remove all `®` (if present)
        DÙ   #  Duplicate this list, and uniquifiy it
          Q  #  And check if it's still the same
  }P         # After the map, check if both were truthy
             # (which is output implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

J, 36 28 bytes

*&({.(-:~.)@-.~}.{.~{.<.#)|.

Try it online!

  • *&( )|. Take the original input (implicit in the hook) and its reverse |., and multiply the boolean values * produced by transforming them with the verb in parens &( )

Let's break down the verb in parens...

  • }.{.~{.<.# From the beheaded }. input take {.~ this many elements: The smaller of <. the first element {. and the length of the list #
  • {.( )@-.~ And from that remove all instances of -.~ the first element of the list {. and @ apply the inner verb in parens...
  • (-:~.) Is the list identical to -: its uniq ~.?
\$\endgroup\$
1
\$\begingroup\$

R, 72 71 70 bytes

`-`=function(l)!anyDuplicated(head(l,l[1]+1),l[1])
-(l=scan())&-rev(l)

Try it online!

Saved a byte thanks to Sumner18.

\$\endgroup\$
4
  • \$\begingroup\$ Couldn't you shave a byte by not aliasing x=l[1] and just using head(l,l[1]+1),l[1])? \$\endgroup\$
    – Sumner18
    Jan 8, 2020 at 19:50
  • 1
    \$\begingroup\$ @Sumner18 why yes I can. Thanks! \$\endgroup\$
    – Giuseppe
    Jan 8, 2020 at 20:26
  • \$\begingroup\$ @Sumner18 something like this would be possible if the keys were guaranteed to be strictly less than the length of the list. \$\endgroup\$
    – Giuseppe
    Jan 8, 2020 at 21:13
  • \$\begingroup\$ I contemplated doing just that with the inputs, but I wanted to diversify the inputs a little bit. I can't make the challenge too easy. \$\endgroup\$
    – Sumner18
    Jan 8, 2020 at 21:50
1
\$\begingroup\$

Husk, 13 bytes

S¤&ΓȯS=uΣSx↑↔

Try it online! The function does the k1 test for the both the list and its reverse.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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