15
\$\begingroup\$

Given a non-empty list of integers between 1 and 9 inclusive, find the longest contiguous sublist such that the number of occurrences of each element (of the sublist) within the sublist is equal (not the number of consecutive occurrences, just the total count). You may return any non-empty subset of the solutions.

Examples

Input                         ->  Output

1, 2, 3                           [1, 2, 3]
1, 2, 2, 3, 3, 4                  [2, 2, 3, 3]
1, 2, 3, 3, 4, 4, 3, 3, 2, 1      [3, 3, 4, 4], [3, 4, 4, 3], [4, 4, 3, 3]
1, 1, 1, 1, 1                     [1, 1, 1, 1, 1]
1, 2, 3, 2, 1                     [1, 2, 3], [3, 2, 1]
1, 2, 3, 4, 4, 3                  [1, 2, 3, 4], [3, 4, 4, 3]
3, 2, 3, 4, 4, 3                  [3, 4, 4, 3]
  • this is , so the shortest code in bytes wins
  • Standard Loopholes are forbidden, as usual
  • I/O may be in any reasonable format. You can do I/O with a string of digits since all inputs will be between 1 and 9, for example (this is mostly to allow regex solutions if anyone can figure that out).
\$\endgroup\$
1
  • 5
    \$\begingroup\$ This question was in the Sandbox (visible to 10k+). Imaginary brownie points for matching/beating my 8-byte Jelly solution. \$\endgroup\$ – hyper-neutrino May 12 at 15:00

23 Answers 23

7
\$\begingroup\$

Brachylog, 8 7 bytes

⊇.ọtᵛ&s

Try it online!

s generates all sublists of consecutive elements, though not in order of length, but in order of prefix (so [1,2,3] [1,2] [1] [2,3] [2] [3]). on the other hand does generate longer sets first, but only guarantees element order, not that they are consecutive. So we check that later for +1 byte.

⊇.ọtᵛ&s  The (implicit) input                        [1,1,2,3]
⊇        has an (ordered) subset                     [1,2,3]
 .       that is the output,                
  ọ      which elements grouped&counted by identity  [[1,1],[2,1],[3,1]]
   tᵛ    have the same number of occurences.         1
      &  The input                                   [1,1,2,3]
       s has consecutive elements                    [1,2,3]
         that is the (implicit) output.
         
\$\endgroup\$
2
  • \$\begingroup\$ Before the edit, I was about to say "FWIW, identity should be , but since every element is a single digit = does work too" \$\endgroup\$ – Unrelated String May 12 at 15:49
  • 1
    \$\begingroup\$ @UnrelatedString yeah, I actually intended to use proper identity, but mix the symbols up sometimes – especially if it doesn't change the output. :-) \$\endgroup\$ – xash May 12 at 15:53
7
\$\begingroup\$

Jelly, 8 7 bytes

ẆĠẈEƊƇṪ

Try it online!

How it works

ẆĠẈEƊƇṪ - Main link. Takes L on the left
Ẇ       - All non-empty contiguous sublists of L, longest last
    ƊƇ  - Keep those sublists S for which the following is true:
 Ġ      -   Group the indices of S by the elements
  Ẉ     -   Length of each
   E    -   All equal?
      Ṫ - Get the last (i.e. the longest) element
\$\endgroup\$
3
  • \$\begingroup\$ Wow, you're very fast at coding in Jelly! \$\endgroup\$ – hyper-neutrino May 12 at 15:01
  • 1
    \$\begingroup\$ also yes this is exactly the solution I had \$\endgroup\$ – hyper-neutrino May 12 at 15:01
  • 8
    \$\begingroup\$ @hyper-neutrino i am speed :P \$\endgroup\$ – Dude coinheringaahing May 12 at 15:01
7
\$\begingroup\$

Husk, 9 7 5 bytes

►ṠË#Q

Try it online!

-2 using the return value of Ë in max by.

-2 from Leo.

Explanation

►ṠË#Q
    Q all sublists (unsorted)
►     max by:
 ṠË       all elements of the list are equal by: (if all equal, returns len+1)
   #      count of occurrences in in the list
\$\endgroup\$
2
  • \$\begingroup\$ Nice use of maxby! And you can save two more bytes with : Try it online! \$\endgroup\$ – Leo May 13 at 0:07
  • \$\begingroup\$ Should remind myself that combinators also work on higher order function \$\endgroup\$ – Razetime May 13 at 2:39
7
\$\begingroup\$

JavaScript (Node.js), 86 bytes

f=(h,...t)=>new Set(c=[],h.map(x=>c[x]=-~c[x])).size<3?h:f(...t,h.slice(1),h.pop()&&h)

Try it online!

Use Breadth-First Search, so you may avoid comparing its length.

A terrible \$O(n\cdot2^n)\$ time complexity. Luckly we only care about its length.

Codes for checking equal number occurrence is copied from Arnauld's answer.


Python 3, 63 bytes

f=lambda l,*t:l*(len({*map(l.count,l)})<2)or f(*t,l[1:],l[:-1])

Try it online!

This Python answer is based on att's answer by applying BFS to it.

Comparing to JS, Python is good at creating sets, function auto bind, get length, array slicing when you are golfing.

\$\endgroup\$
5
\$\begingroup\$

Scala, 84 bytes

_.tails.flatMap(_.inits)filter(l=>l.map(x=>l.count(_==x)).toSet.size<2)maxBy(_.size)

Try it in Scastie!

_.tails                //All suffixes
  .flatMap(_.inits)    //All prefixes of those suffixes (all subsequences)
  filter(l=>           //Keep the ones where
    l.map(x=>l.count(_==x))  //The counts of all the elements
      .toSet.size<2          //Has 0 or 1 distinct elements
  )maxBy(_.size)       //Find the biggest such subsequence
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 8 bytes

ŒʒD¢Ë}éθ

Try it online!

Π         # all sublists of the input
 ʒ   }     # filter by:
   ¢       #   counts of each value
  D        #   in a copy of the sublist
    Ë      #   are all counts equal?
      é    # sort the remaining sublists by length
       θ   # take the last one

Alternatively, sort first, reverse and take the first sublist that satisfies the condition:

ŒéR.ΔD¢Ë

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Japt -h, 10 bytes

ã kÈü üÊÊÉ

Try it

ã kÈü üÊÊÉ     :Implicit input of array
ã              :Subsections (sorted by length)
  k            :Remove elements that return falsey (0)
   È           :When passed through the following function
    ü          :  Group by value
      ü        :  Group by
       Ê       :    Length
        Ê      :  Length
         É     :  Minus 1
               :Implicit output of last element in resulting array
\$\endgroup\$
5
\$\begingroup\$

Python 3, 73 bytes

f=lambda l:l*(len({*map(l.count,l)})<2)or max(f(l[1:]),f(l[:-1]),key=len)

Try it online!

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

05AB1E, 9 8 bytes

ŒʒD¢Ë}éθ

Try it online!

Π    all sublists
ʒ     keep those such that
D     duplicate
¢     count, vectorizes
Ë     all equal
}
é     sort by length
θ     last

\$\endgroup\$
3
  • 5
    \$\begingroup\$ two identical osabie answers \$\endgroup\$ – Razetime May 12 at 15:33
  • \$\begingroup\$ @Razetime this was actually created before the other one \$\endgroup\$ – Recursive Co. May 12 at 15:39
  • \$\begingroup\$ @ophact I think I had the 8 bytes a few seconds earlier, but it is fine to keep both answers. \$\endgroup\$ – ovs May 12 at 15:47
4
\$\begingroup\$

JavaScript (ES6), 108 bytes

Returns the rightmost solution.

a=>a.map((_,n)=>a.map((_,i)=>(b=a.slice(i,i-~n))[new Set(b.map(x=>c[x]=-~c[x],c=[])&&c).size-2+n]?o=b:0))&&o

Try it online!

Commented

a =>                       // a[] = input array
  a.map((_, n) =>          // for n = 0 to len(a) - 1:
    a.map((_, i) =>        //   for i = 0 to len(a) - 1:
      ( b =                //     define b[] as the sub-array of length
        a.slice(i, i - ~n) //     at most n + 1 starting at index i
      )[                   //
        new Set(           //     build a set consisting of the number of
          b.map(x =>       //     occurrences of each distinct entry in b[],
            c[x] = -~c[x], //     using another array c[] to keep track of
            c = []         //     these counts
          )                //     the set will always include 'undefined'
                           //     because c[0] is never updated
          && c             //
        ).size             //     which is why we expect its size to be 2
        - 2 + n            //     make sure that b[new Set().size - 2 + n]
      ]                    //     is defined (i.e. b[] is long enough and
                           //     the number of occurrences are all equal)
      ?                    //     if so:
        o = b              //       update the output
      :                    //     else:
        0                  //       do nothing
    )                      //   end of inner map()
  )                        // end of outer map()
  && o                     // return o
\$\endgroup\$
1
  • \$\begingroup\$ new Set(c=[],b.map(x=>c[x]=-~c[x])) \$\endgroup\$ – tsh May 13 at 4:03
4
\$\begingroup\$

Python 3.8 (pre-release), 104 bytes

lambda x:max((a for i in range(len(x)+1)for j in range(i)if len({*map((a:=x[j:i]).count,a)})<2),key=len)

Try it online!

-1 thanks to @ophact

-24 thanks to @pxeger

-10 thanks to @hyper-neutrino

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Seems like <2 works instead of ==1? I'm not as proficient in python compared to js though. \$\endgroup\$ – Recursive Co. May 12 at 16:24
  • 1
    \$\begingroup\$ dict(...) can be {**...}. But it's actually shorter counting manually: Try it online! \$\endgroup\$ – pxeger May 12 at 16:25
  • 1
    \$\begingroup\$ -5 on pxeger's if you map with x[i:j].count \$\endgroup\$ – hyper-neutrino May 12 at 16:27
  • 1
    \$\begingroup\$ Actually a Counter already has a .values() method because it's a subclass of dict, so the {**...} is unnecessary (not that it matters any more) \$\endgroup\$ – pxeger May 12 at 16:28
  • 1
    \$\begingroup\$ -5 using walrus and bring ophact's <2 back: tio.run/… \$\endgroup\$ – hyper-neutrino May 12 at 16:32
4
\$\begingroup\$

R, 104 98 96 95 bytes

function(L,n=seq(!L)){for(i in n)for(j in n)if(!sd(table(a<-L[i:j])+!1:2)&sum(T|1)<j-i+2)T=a;T}

Try it online!

Ugly straightforward approach. Can't wait for a nice R solution!

-6 bytes thanks to @Dominic
-1 byte thanks to @Giuseppe

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

Haskell, 92 bytes

last.sortOn l.filter((<2).l.nub.map l.group.sort).(>>=tails).inits
l=length
import Data.List

Try it online!

Either Haskell is not the language for this challenge, or I'm not the Haskeller for this challenge1.


1 Yup, I know, it's the latter.

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

J, 38 33 bytes

0{(1=&#[:=#/.~)\\.(\:#&>)@#&,<\\.

Try it online!

-5 thanks to xash!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ With monadic = and double \\. for less boxing: 33b \$\endgroup\$ – xash May 12 at 17:51
  • 1
    \$\begingroup\$ Very nice. Thanks @xash. \$\endgroup\$ – Jonah May 12 at 17:55
2
\$\begingroup\$

JavaScript, 122 bytes

f=(n,p=t=n.length)=>n.find((e,i)=>i+p<=t&(l=n.slice(i,i+p)).every(x=>(z=m=>l.filter(w=>w==m).length)(x)==z(e)))?l:f(n,p-1)

One must marvel at the sheer length of counting the number of occurrences in a list.

A recursive function which checks all lists of length p for one satisfying the OP's conditions, and if there exists one, return it, otherwise return f(n,p-1)

Suggestions are welcome for golfing.

\$\endgroup\$
4
  • \$\begingroup\$ Just a minor golf, but you can use w-m instead of w==m (counting the number of occurrences of not m eventually leads to the same results). \$\endgroup\$ – Arnauld May 12 at 16:53
  • \$\begingroup\$ You can save another byte by using !some(...X-Y...) instead of every(...X==Y...). \$\endgroup\$ – Arnauld May 12 at 17:02
  • \$\begingroup\$ @Arnauld I understand your first suggestion, but I'm not sure why your second saves another. Is it not just the same number of bytes as the first one? \$\endgroup\$ – Recursive Co. May 12 at 17:03
  • \$\begingroup\$ !some is just as long as every, but - is shorter than ==. \$\endgroup\$ – Arnauld May 12 at 17:04
2
\$\begingroup\$

Factor, 63 58 56 bytes

[ all-subseqs [ histogram values all-eq? ] filter last ]

Try it online!

              [                          ] filter last   ! Select the last/largest..
  all-subseqs                                            ! ..subsequence..
                histogram values                         ! ..whose elements occur..
                                 all-eq?                 ! ..the same number of times.
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

Last@*Select[Equal@@Counts@#&]@*Subsequences

Try it online!

Get all subsequences (ordered), select the ones with equal occurrences, take the last of those.

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

Retina, 71 bytes

Lw`.+
%(`$
¶$`
1%O`.
1%L$`(.)\1*
$.&
)L$`^(.+)(¶.+)\2*$
$1
N^$`
$.&
0G`

Try it online! Link includes test cases. Takes input as a string of digits. Explanation:

Lw`.+

Get all substrings of the input.

%(`
)`

Loop over each substring.

$
¶$`

Duplicate the substring.

1%O`.

Sort the duplicate into order.

1%L$`(.)\1*
$.&

Get the run lengths.

L$`^(.+)(¶.+)\2*$
$1

If the run lengths are equal, then keep the substring, otherwise keep nothing.

N^$`
$.&

Sort all of the remaining substrings in descending order of length.

0G`

Keep only the longest remaining substring.

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

Python 2, 140 132 bytes

-8 bytes thanks to @hyper-neutrino for space saving and replacing def with lambda!

I was using python3 to code until I found that it works for Python2 too, not too much, just an iterative solution.

lambda n:max([r for r in [n[i:a]for a in range(len(n)+1)for i in range(len(n))if a-i>1]if len(set(r.count(s)for s in r))<2],key=len)

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You only use l twice, so it's better to make this a lambda and just put len(n) in twice. Also, you have two extra spaces. tio.run/##XY3BDsIgEER/… \$\endgroup\$ – hyper-neutrino May 13 at 5:14
1
\$\begingroup\$

Charcoal, 40 bytes

FEθ✂θκFEι…ι⊕λF⁼⌊Eκ№κλ⌈Eκ№κλ⊞υκΦυ⁼Lι⌈EυLλ

Try it online! Link is to verbose version of code. Takes input as a string of digits and outputs all maximal length substrings with the given condition. Explanation:

FEθ✂θκ

Loop over all nontrivial suffixes of the input.

FEι…ι⊕λ

Loop over all nontrivial prefixes of the suffix.

F⁼⌊Eκ№κλ⌈Eκ№κλ

Take the frequencies of the elements and check whether they are all the same.

⊞υκ

Record all substrings that satisfy the condition.

Φυ⁼Lι⌈EυLλ

Output the longest such substrings.

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

Ruby, 69 bytes

->r,*w{r,*w=w<<r[0..-2]<<r[1..-1]while r.map{|x|r.count x}.uniq[1];r}

Try it online!

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

yuno (abandoned), 7 bytes

ッシュフェドゥッキッカ;テ

xxd using Jelly's codepage:

00000000: 87a0 9a6d 6bfe 0b                        ⁷ɦȤmk“¿

Disclaimer: some language features were added after this challenge. However, they weren't really made to be tailored to this challenge, all of these are things I'd planned previously. If I really wanted to, I could've reasonably made built-ins much more suited ot this challenge, but I have those on my wishlist right now as they're a lot more specific.

ッシュフェドゥッキッカ;テ   Full Program
ッシュ             All sublists, in increasing order of length then position
   フェ      ;    Filter-lambda; keep elements that:
     ドゥ         (duplicate top of stack)
       ッキ       special count; if counting occurrences of a list that is not found, but any of its elements are, vectorize (recurses)
         ッカ     all-equal?
            テ   last element
\$\endgroup\$
2
  • \$\begingroup\$ So, it is a code page which render a single byte to multiple katakana? \$\endgroup\$ – tsh May 13 at 5:36
  • \$\begingroup\$ @tsh yes, that's how it works. i will admit it's a bit weird and maybe wasn't the best idea :P \$\endgroup\$ – hyper-neutrino May 13 at 15:47
0
\$\begingroup\$

Python 3.8, 98 bytes

Another not-very-successful python3 attempt

f=lambda l,i=0:(a:=l[i%(L:=len(l)):][:L-i//L])*(i%L<=i//L)*(len({*map(a.count,a)})<2)or f(l,i+1)

a less condensed version

def f(l, i=0):
 L = len(l)
 a = l[i%L:][:L-i//L]
 return a * (i%L<=i//L) * (len({*map(a.count,a)})<2) or f(l,i+1)
\$\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.