Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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 code-golf so the goal is to minimize your source code with answers being scored in bytes.
[] -> []
[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]
Ẇœ-QḊƊÐḟṪȯ
Ẇœ-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ỊƲƇṪȯ.
Þ works with your 11 too, but still need the ȯ to handle the empty list unfortunately.
\$\endgroup\$
Jan 30 at 0:57
bytes in Code Golf? len(bytes("Ẇœ-QḊƊÐḟṪȯ", 'utf-8')) == 22
\$\endgroup\$
f=(a,...r)=>a[new Set(a).size+1]?f(...r,a.slice(1),a.pop()&&a):a
f=lambda l,*r:len(l)>1+len({*l})and f(*r,l[1:],l[:-1])or l
Yet another question solved with same pattern?
-2 bytes thanks to xash
⊇.ọtᵐ×≤2&s
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
&s is necessary so that the output is a contiguous sublist of the input, but that still saves 2 bytes. Thanks!
\$\endgroup\$
ẆµĠẈ’SỊµƇṪȯ
-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
f=lambda l:len(l)>1+len({*l})and max(f(l[1:]),f(l[:-1]),key=len)or l
f l@(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
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
0 is a num. You can use () instead which it likes but a is shorter.
\$\endgroup\$
[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\$
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.
su<-{f:)-]g_2<=j{1==}al&&}fe
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
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)
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.
math.unicode, 77 bytes[ f suffix all-subseqs [ histogram values 1 v-n Σ 2 < ] find-last nip sift ]
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
f[s=___,Longest@a:s,s]/;Total[Counts@{a}-1]<2=a
Input and output a Sequence of values.
Last@*Select[Total[Counts@#-1]<2&]@*Subsequences
Input and output a list.
import Data.List
l=length
head.sortOn(\x->(l(x\\nub x)>1,-l x)).(tails=<<).inits
Get all infixes, sort by (invalid, -length), return the first one.
≔⟦⟧ηＦθ«⊞υιＷ‹¹ΣＥυ›μ⌕υλ≔Φυμυ¿›ＬυＬη≔Ｉυη»η
Try it online! Link is to verbose version of code. Explanation:
≔⟦⟧η
Start with no longest sublist.
Ｆθ«
Loop over the input terms.
⊞υι
Append the term to the predefined empty list.
Ｗ‹¹ΣＥυ›μ⌕υλ
While the current sublist contains more than one duplicate...
≔Φυμυ
... remove the first term from the sublist.
¿›ＬυＬη
If the sublist is longer than the longest sublist so far, then...
≔Ｉυη
... 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).
Edit: -1 byte thanks to Razetime
►LfoεṠ-uQ
► # 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.
►LfoεṠ-uQ, ε checks size of the list as well
\$\endgroup\$
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
AnttiP's idea, can't read golfing language so don't know if that's source
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
Is it usual to be 6-8x longer than golfing language or this is quite golfable?
Œʒ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)
[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\$