骞胯タ鑷不鍖烘秷璐硅€呮潈鐩婁繚鎶ゅ鍛樹細

Question

Every day, you spot zero or more animal species, and keep a log. For example, the first day you see a kangaroo and a koala, the second day, a koala and a zebra, just a koala the third day, and a kangaroo the fourth day.

[['kangaroo','koala'], ['koala','zebra'], ['koala'], ['kangaroo']]

That means for a streak of three days, you can say that you saw an animal you haven't yet mentioned within that streak: kangaroo, zebra, koala (starting from the first day), or zebra, koala, kangaroo (starting from the second day).

Your task: Write a program or function which computes the length of the longest streak of "new animal not yet mentioned in this streak".

Input

An array of array of strings, in whatever format. (You can take an array of dicts, for instance, or a CSV file...) Each string is lowercase letters only. There may be days with no entries. There will be at least one day. There won't be any repeats within a day. You may take animals sorted within a day.

Output

A number, the length of the longest streak.

Scoring

Code golf.

Sample data (more welcome)

[[], [], [], []]

=> 0

[['kangaroo','koala'], ['koala','zebra'], ['koala'], ['kangaroo']]

=> 3

[['fish','donkey','horse','cow'],['horse'],['cow','horse','cat','dog','giraffe'],['horse','cow','hamster'],['horse','cat','hamster','giraffe'],['horse','cow'],['cow'],['horse','cat']],

=> 6

[['wolf'],['fish','dog'], ['fish','dog'], ['fish','dog'],['fish','dog','cat'],['fish','dog'],['cat','wolf']]

=> 4

[['dog','cat','lion'],[],['fish'],['fish'],['fish'],['dog'],['fish'],['fish']]

=> 2

Answer 1

Jelly, 10 bytes

??pQ??$???

A monadic Link that accepts a list of lists of animals and yields the maximal number of contiguous days during which one could reference a unique animal from each day's observation.

Try it online! Or see the test-suite.

How?

??pQ??$??? - Link: DailyObservations
?          - contiguous sublists of {DailyObservations} -> Streaks (from shortest to longest)
       ?   - keep those {Streaks} for which:
      $    -   last two links as a monad - f(Streak):
 ?p        -     Cartesian product of {Streak}'s items
     ?     -     keep those for which:
    ?      -       is invariant under?:
   Q       -         deduplicate
        ?  - length of each of the {remaining Streaks}
         ? - tail -> length of longest remaining streak (or zero if none remain)

---

Note: ?? rather than ?L because tailing an empty list, as remaining Streaks becomes when no animals are seen on any day, yields the integer 0, and integers have length 1)

Answer 2

Python 3, 94 bytes

f=lambda l,s=[]:max(map(len,s+[l and[f]*f(l[1:],[t+[a]for t in s+[[]]for a in{*l[0]}-{*t}])]))

Try it online!

Alternate (same byte count):

f=lambda l,s=[]:max(map(len,s+[l and[f]*f(l[1:],[t|{a}for t in s+[set()]for a in{*l[0]}-t])]))

Answer 3

JavaScript (ES6), 87 bytes

f=([a=[],...b],o=f,n=0)=>Math.max(n,b+b&&f(b),...a.map(s=>o[s]||f(b,{...o,[s]:1},n+1)))

Try it online!

Commented

f = (           // f is a recursive function taking:
  [             //
    a = [],     //   a[] = next list of animals (empty by default)
    ...b        //   b[] = array of remaining lists
  ],            //
  o = f,        //   o = object to store selected animals
  n = 0         //   n = number of animals in o
) =>            //
Math.max(       // get the maximum of:
  n,            //   the current value of n
  b + b &&      //   if b[] is not empty:
    f(b),       //     the result of a recursive call with b[]
                //     (previous values of o and n are discarded)
  ...a.map(s => //   for each animal s in a[]:
    o[s] ||     //     abort if this animal was already selected (*)
    f(          //     otherwise, do a recursive call:
      b,        //       pass b[]
      {         //       build a new object with:
        ...o,   //         the content of o
        [s]: 1  //         a new entry with key s and value 1
      },        //
      n + 1     //       increment n
    )           //     end of recursive call
  )             //   end of map()
)               // end of Math.max()

_{(*) We return 1 if we abort. This is safe because reaching that part of the code means that there's at least one non-empty list of animals and the answer is at least 1.}

Answer 4

Brachylog, 10 9 (or 11?) bytes

{s??≠l}??

Try it online!

In the corner case where we never see an animal on any day, this program fails instead of returning 0. I would argue that's a reasonable behavior, but if it needs to output 0, here is an 11-byte solution:

{s??≠l}?,0?

Try it online!

Explanation

Brachylog's logic-based paradigm is good for this kind of challenge. Unfortunately, the "contiguous sublist" builtin s doesn't try sublists in order of length but in order of initial index, so we need a workaround.

{s??≠l}??
{     }?   List all possible outputs to the following nested predicate:
 s           Contiguous sublist of the input
  ??         Take some element from each element of that list
    ≠        The result must have no two elements that are equal
     l       Take the length
        ?  Maximum

Answer 5

Python3, 177 bytes

def f(o):
 q,r=[(o[i:],[])for i in range(len(o))],[0]
 for o,m in q:
  if o and(c:=[j for j in o[0]if j not in m]):q+=[(o[1:],m+[j])for j in c]
  else:r+=[len(m)]
 return max(r)

Try it online!

Answer 6

Charcoal, 37 bytes

Ｆθ??ΣＥ∨υ?υ?Ｅι?ＯΦκ?ν?κμμυＪ??ＯＥυＬκ???Ｉ?

Attempt This Online! Link is to verbose version of code. Explanation:

Ｆθ?

Loop over the input list of lists of animals.

?ΣＥ∨υ?υ?Ｅι?ＯΦκ?ν?κμμυ

For each streak so far (or an empty streak if there are none; this happens on the first day and on the day after seeing no animals) and for each animal, calculate the streak that ends in that animal, starting from the animal after its previous appearance (if any; if this is a new animal then its index will be -1 and all previous animals are kept).

Ｊ??ＯＥυＬκ??

Keep track of the length of the longest streak found (if any).

?Ｉ?

Output the length of the longest streak.

Answer 7

Python 3, 109 bytes

^{I won't be surprised if we can make do without importing in fewer bytes}

from itertools import*
f=lambda d:len(d)and max(f(d[1:]),f(d[:-1]),*{len({*p})for p in product(*d)}&{len(d)})

Try it online!

How?

from itertools import* # get access to the `product` function
f=lambda d:            # f is a function of d - f(d):
  len(d)               #   get the length of d
    and                #     logical AND (short-circuits if d = [], returning 0)
  max(...)             #   maximum of:
    f(d[1:])           #     a) call f with a beheaded d
    f(d[:-1])          #     b) call f with a betailed d
    *                  #     c...) unpacked:
          &            #        intersection of:
     {...}             #          1. set of:
     for p in          #               for each p in:
       product(*d)     #                 the Cartesian product of d's animal lists:
         len({*p})     #                   distinct animal count in p
           {len(d)}    #          2. singleton set of the length of d

Answer 8

Nekomata, 6 bytes

q?~?#?

Attempt This Online!

A port of DLosc's Brachylog answer. Non-determinism is very useful for this kind of challenge.

q?~?#?
q           Find a contiguous subsequence of the input
 ?          For each element in that subsequence
  ~             Choose an element from the list
   ?        Check that all elements in the result are unique
    #       Take the length
     ?      Find the maximum possible value of that length