18
\$\begingroup\$

Given a list of positive integers, give the longest contiguous sublist which contains at most 1 pair of identical items. In the case of a tie return any of the solutions.

This is so the goal is to minimize your source code with answers being scored in bytes.

Test cases

[] -> []
[1,2,3] -> [1,2,3]
[1,2,2,3] -> [1,2,2,3]
[2,2,3,2,4] -> [2,3,2,4]
[1,2,1,3,2] -> [2,1,3,2]
[1,2,3,1,4,1,2,3,4,5,1] -> [1,2,3,4,5,1]
[1,2,3,2] -> [1,2,3,2]
\$\endgroup\$
5
  • \$\begingroup\$ I don't understand, is this submission asking us to rewrite the filterDuplicates functions or something? \$\endgroup\$
    – logic
    Jan 30 at 12:52
  • \$\begingroup\$ @logic It is asking you to write a program or function which takes a list of positive integers and gives the lonest contiguous sublist which contains 1 or fewer pairs of identical elements. If you have a more specific question about any of the terms I can answer it, but I don't currently know where you are struggling. \$\endgroup\$
    – Wheat Wizard
    Jan 30 at 12:54
  • \$\begingroup\$ Isn't the answer ambiguous? What makes [1,2,3,1,4,1,2,3,4,5,1] -> [1,2,3,4,5,1] the correct solution? Couldn't [1,2,3,1,4,1,2,3,4,5,1] -> [4,1,2,3,4,5] also be a valid solution? \$\endgroup\$
    – Alderath
    Jan 31 at 12:36
  • 1
    \$\begingroup\$ @Alderath " In the case of a tie return any of the solutions." \$\endgroup\$
    – Wheat Wizard
    Jan 31 at 12:36
  • \$\begingroup\$ @WheatWizard Sorry. My bad. Sometimes my brain silently discards small pieces of instructions... \$\endgroup\$
    – Alderath
    Jan 31 at 12:38

18 Answers 18

8
\$\begingroup\$

Jelly, 10 bytes

Ẇœ-QḊƊÐḟṪȯ

Try it online!

How?

Ẇœ-QḊƊÐḟṪȯ - Link: list, A
Ẇ          - substrings (well, non-empty ones) sorted by length then left to right
      Ðḟ   - filter discard those for which this is truthy:
     Ɗ     -   last three links as a monad:
   Q       -     distinct values
 œ-        -     multiset difference - remove one of each value from A
    Ḋ      -     dequeue - remove one from this list if there are any
                         - [] is falsey
        Ṫ  - tail - one of, or the, longest one
                  - unless A was [] in which case zero
         ȯ - logical OR with A - replace that zero with []

Alternatively, Ẇœ-QLỊƲƇṪȯ.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Nice use of and Ðḟ - I had this 11 byter \$\endgroup\$ Jan 30 at 0:25
  • \$\begingroup\$ Þ works with your 11 too, but still need the ȯ to handle the empty list unfortunately. \$\endgroup\$ Jan 30 at 0:57
  • \$\begingroup\$ What is the definition of bytes in Code Golf? len(bytes("Ẇœ-QḊƊÐḟṪȯ", 'utf-8')) == 22 \$\endgroup\$
    – batisteo
    Jan 31 at 8:56
  • 1
    \$\begingroup\$ @batisteo the raw source-code itself is 10 bytes, the representation above is just making use of a mapping -- Jelly's code-page, which is linked to by the "bytes" in the header. Hence counting the bytes of the Unicode characters you see above is not the source-code byte count for scoring purposes. \$\endgroup\$ Jan 31 at 12:11
6
\$\begingroup\$

JavaScript (Node.js), 64 bytes

f=(a,...r)=>a[new Set(a).size+1]?f(...r,a.slice(1),a.pop()&&a):a

Try it online!


Python 3, 58 bytes

f=lambda l,*r:len(l)>1+len({*l})and f(*r,l[1:],l[:-1])or l

Try it online!

Yet another question solved with same pattern?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ -1 on the Python one I think. \$\endgroup\$
    – loopy walt
    Jan 29 at 9:10
6
\$\begingroup\$

Brachylog, 14 12 10 bytes

-2 bytes thanks to xash

⊇.ọtᵐ×≤2&s

Try it online!

Explanation

We're looking for a sublist in which each element occurs only once, except that one element may occur twice.

Makes use of this very helpful tip from Unrelated String.

⊇.ọtᵐ×≤2&s
            The input
⊇           Sublist (not necessarily contiguous), trying longest first
 .          The result is the output
  ọ         Generate a list of [element, count] pairs
   tᵐ       Get the last element of each pair (list of counts)
     ×      Product
      ≤2    Is less than or equal to 2
        &s  Also, the output is a contiguous sublist of the input
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 9b by checking if product of the occurrence counts is less or equal 2: Try it online! \$\endgroup\$
    – xash
    Jan 30 at 0:13
  • 2
    \$\begingroup\$ The &s is necessary so that the output is a contiguous sublist of the input, but that still saves 2 bytes. Thanks! \$\endgroup\$
    – DLosc
    Jan 30 at 4:50
4
\$\begingroup\$

Jelly, 11 bytes

ẆµĠẈ’SỊµƇṪȯ

Try It Online!

-1 byte thanks to Jonathan Allan

ẆµĠẈ’SỊµƇṪȯ   Main Link
Ẇ             all sublists
 µ     µƇ     filter
  Ġ           - group indices of equal elements
   Ẉ          - length of each group
    ’         - subtract one from each length
     S        - sum of these (total number of duplicate elements)
      Ị       - is this insigificant? (between -1 and 1)
         Ṫ    take the last (longest) element
          ȯ   logical OR; if the output is 0 (only happens if input
              is []), return the input instead, which fixes [] being
              output as 0
\$\endgroup\$
1
  • 2
    \$\begingroup\$ ȯ will do the job at the end there. \$\endgroup\$ Jan 28 at 22:46
3
\$\begingroup\$

Japt -h, 14 bytes

Feel like I'm missing a trick here :\

ã fÈÊɶXâ ÊÃiU

Try it

\$\endgroup\$
2
  • \$\begingroup\$ 12? \$\endgroup\$
    – AZTECCO
    Jan 28 at 22:47
  • \$\begingroup\$ Also 10 could work if longer sublists are at the end but not sure \$\endgroup\$
    – AZTECCO
    Jan 28 at 22:49
3
\$\begingroup\$

Python 3, 68 bytes

f=lambda l:len(l)>1+len({*l})and max(f(l[1:]),f(l[:-1]),key=len)or l

Try it online!

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

Haskell, 108 83 bytes

f [email protected](u:q)|0:(0<$l)<[0|x<-l,y<-q,x==y]=f(init$l)!f q
f q=q
a!b|(a<$a)>(a<$b)=a|1>0=b

Try it online!

  • Thanks to @Wheat Wizard for saving so many many bytes!

g : counts duplicates. -> moved to list comprehension in f by Wheat Wizard , the tricky part is here and deserves an explanation

f(u:q)|
(0<$q)       list 0s for each element 
<            compared to
[0|x<-q,y<-q,x==y] list of 0s for each equal pairs in the powerset

Note that we use tail so that one potential dupe is already counted and the lists must be the same, if not there is more than 1 dupe, in that case we search.. Else we skip this and f q=q match giving the result.

a!b : selects longer list.
flist : if list is not ok choose from head or tail else return it

\$\endgroup\$
5
  • \$\begingroup\$ 96 \$\endgroup\$
    – Wheat Wizard
    Jan 30 at 0:34
  • 1
    \$\begingroup\$ It doesn't work because 0 is a num. You can use () instead which it likes but a is shorter. \$\endgroup\$
    – Wheat Wizard
    Jan 30 at 0:42
  • 1
    \$\begingroup\$ Yeah, it's an easy fix though: 80 \$\endgroup\$
    – Wheat Wizard
    Jan 30 at 0:53
  • \$\begingroup\$ I think that my trick actually does not work. It fails on [1,2,3,2]. I incorrectly assumed that the solution would always start with one of the elements in the pair. Fixing it costs 5 bytes \$\endgroup\$
    – Wheat Wizard
    Jan 30 at 2:41
  • \$\begingroup\$ @Wheat Wizard I managed to use the trick partially, at least I think it works \$\endgroup\$
    – AZTECCO
    Jan 30 at 5:41
2
\$\begingroup\$

Retina 0.8.2, 78 bytes

M!&r`.*\d\b
.*\b(\d+)(?=.*,\1\b),(.*\b(\d+)\b.*,\3\b)
$2
O$^`((,)|\d)+
$#2
1G`

Try it online! Link includes test cases. Explanation:

M!&r`.*\d\b

Take all of the suffixes.

.*\b(\d+)(?=.*,\1\b),(.*\b(\d+)\b.*,\3\b)
$2

Truncate them at the second last duplicate. (Since we need this longish regex to check for two pairs/three of a kind, it turns out to be golfier to truncate the prefixes than to filter on all sublists.)

O$^`((,)|\d)+
$#2

Sort by descending number of elements.

1G`

Take the first.

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

Ruby, 63 bytes

f=->l,s=1{l[-s]&&f[l,s+1]||l.each_cons(s).find{|q|q.uniq[s-2]}}

Try it online!

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

Burlesque, 28 bytes

su<-{f:)-]g_2<=j{1==}al&&}fe

Try it online!

su           # All substrings from shortest to longest
<-           # Reverse (longest first)
{
 f:          # Frequency list as (count, val) sorted by count
 )-]         # Map head (get counts)
 g_          # Split into head + tail
 2<=         # Head is 2 or 1
 j           # Swap
 {1==}al     # Tails all 1s
 &&          # Logical AND
}fe          # Find the first element for which
\$\endgroup\$
2
\$\begingroup\$

R, 162 bytes

Or R>=4.1, 148 bytes by replacing two function occurrences with \s.

function(v,a=apply(combn(rep(seq(v),2),2),2,function(x,t=table(k<-v[x[1]:x[2]]))if(x[1]<=x[2]&all(t%in%1:2)&sum(t==2)<2)k))"if"(sum(v),a[order(-lengths(a))[1]],v)

Try it online!

I was hoping for some ingenious answer from better R golfers here, but it looks like I have to post my boring straightforward one first for some motivation.

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

Factor + math.unicode, 77 bytes

[ f suffix all-subseqs [ histogram values 1 v-n Σ 2 < ] find-last nip sift ]

Try it online!

Explanation

  • f suffix ... sift Work around the fact that all-subseqs blows up on an empty input. Add f to the input and remove it with sift at the end. (This doesn't change anything since we're only adding one.)
  • all-subseqs [ ... ] find-last nip Find the last/largest subsequence of the input that returns true when the given quotation is called on it.

The quotation to find-last works by taking a histogram of the input, subtracting 1 from all the counts, taking the sum, and checking whether the sum is less than two. For instance:

             ! { 2 2 3 2 4 }
histogram    ! H{ { 2 3 } { 3 1 } { 4 1 } }
values       ! { 3 1 1 }
1 v-n        ! { 2 0 0 }
Σ            ! 2
2 <          ! f
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 47 bytes

f[s=___,[email protected]:s,s]/;Total[[email protected]{a}-1]<2=a

Try it online!

Input and output a Sequence of values.


Wolfram Language (Mathematica), 48 bytes

[email protected]*Select[Total[[email protected]#-1]<2&]@*Subsequences

Try it online!

Input and output a list.

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

Haskell, 80 bytes

import Data.List
l=length
head.sortOn(\x->(l(x\\nub x)>1,-l x)).(tails=<<).inits

Try it online!

Get all infixes, sort by (invalid, -length), return the first one.

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

Charcoal, 40 38 bytes

≔⟦⟧ηFθ«⊞υιW‹¹ΣEυ›μ⌕υλ≔Φυμυ¿›LυLη≔Iυη»η

Try it online! Link is to verbose version of code. Explanation:

≔⟦⟧η

Start with no longest sublist.

Fθ«

Loop over the input terms.

⊞υι

Append the term to the predefined empty list.

W‹¹ΣEυ›μ⌕υλ

While the current sublist contains more than one duplicate...

≔Φυμυ

... remove the first term from the sublist.

¿›LυLη

If the sublist is longer than the longest sublist so far, then...

≔Iυη

... save a copy of the sublist (because we're going to push to the original, and we need to cast it to string anyway).

»η

Output the longest sublist (which we already cast to string above).

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

Husk, 10 9 bytes

Edit: -1 byte thanks to Razetime

►LfoεṠ-uQ

Try it online!

►           # output the (first) element with maximum...
 L          # ...length...
            # ...from among:
         Q  # all contiguous sublists, 
  fo        # filtered by:
      Ṡ-    # the difference between...
        u   # ...itself and unique elements of itself...
    ε       # ...has length 1.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ -1: ►LfoεṠ-uQ, ε checks size of the list as well \$\endgroup\$
    – Razetime
    Feb 1 at 8:26
  • \$\begingroup\$ @Razetime - Thanks! I need to re-read the docs, I guess... \$\endgroup\$ Feb 1 at 8:43
  • \$\begingroup\$ @Razetime - BTW: last day to try to crack this... \$\endgroup\$ Feb 1 at 8:44
  • \$\begingroup\$ oh, i see. I did not notice this thread. \$\endgroup\$
    – Razetime
    Feb 1 at 8:51
1
\$\begingroup\$

JavaScript (Node.js), 79 75 bytes

f=(X,a)=>X[h=new Set([w,...x]=X).size+1]?(a=f(x),b=f(X,X.pop()),a[h]?a:b):X

Try it online!

AnttiP's idea, can't read golfing language so don't know if that's source

JavaScript (Node.js), 89 bytes

f=(x,h,L=0,a=x.filter(y=x=>!(y[x]=h+=[y[x]])[20]&&++L),b=x[0]?f(x.slice(1)):[])=>b[L]?b:a

Try it online!

Is it usual to be 6-8x longer than golfing language or this is quite golfable?

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

05AB1E, 11 bytes

ŒʒgyÙg-!}éθ

Try it online or verify all test cases.

Explanation:

Π       # Get all sublists of the (implicit) input-list
 ʒ       # Filter this list of sublists by:
  g      #  Get the length of the sublist
   y     #  Push the sublist again
    Ù    #  Uniquify its items
     g   #  Pop and push the length of this uniquified list as well
      -  #  Subtract the lengths from one another
       ! #  Check if this is either 0 or 1 by taking the faculty, which will
         #  result in [1,1,2,6,24,120,...] for [0,1,2,3,4,5,...] respectively,
         #  and only 1 is truthy in 05AB1E
 }é      # After the filter: sort the remaining sublists from shortest to longest
   θ     # Pop and keep just the last (longest)
         # (after which it is output implicitly as result)
\$\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.