| Bytes | Lang | Time | Link |
|---|---|---|---|
| 017 | 05AB1E | 250814T091306Z | Kevin Cr |
| 081 | Dyalog APL | 250811T175319Z | Aaron |
| 031 | Uiua | 250811T003151Z | nyxbird |
| 106 | Prolog SWI | 250809T022650Z | 0 |
| 083 | JavaScript ES6 | 250806T103734Z | Arnauld |
| 094 | Python 3 | 250807T053958Z | tata |
| 006 | Nekomata | 250807T021100Z | alephalp |
| 109 | Python 3 | 250806T200922Z | Jonathan |
| 177 | Python3 | 250806T184230Z | Ajax1234 |
| 911 | Brachylog | 250806T171826Z | DLosc |
| 010 | Jelly | 250806T165726Z | Jonathan |
| 037 | Charcoal | 250806T165346Z | Neil |
05AB1E, 17 bytes
ÎŒε.«âε¸˜ÐÙQsg*]M
Try it online or verify all test cases.
Explanation:
Î # Push 0 and the input-list
Π# Get all sublists of this input-list
ε # Map over each sublist:
.« # Reduce it by:
â # Cartesian product of two lists
ε # Inner map over each resulting list:
¸ # Wrap it into a list (work-around for singleton values)
˜ # Flatten it to a list of strings
Ð # Triplicate the current list of strings
Ù # Uniquify the top copy
Q # Check that it equals to the other copy (aka, all values are unique)
s # Swap to get the list of strings
g # Pop and push its length
* # Multiply it to the unique-check
] # Close the nested maps
M # Push the largest value on the stack, including inside (nested) lists
# (which is output implicitly as result)
Minor note: there seems to be a bug in 05AB1E, because ...0M instead of Î...M should have worked the same for edge test-case [[],[],[],[]], but results in an empty string instead: try it online..
Dyalog APL, 81 chars
{0⌈⌈/+/¨⊃,/{⍵∘{⊃⊆⍨≠⍵↓⍺}¨¯1+⍳≢⍵}¨⊃,/{0=≢⍵:0⋄⊃{,⍺∘.,⍵}/⍵}¨{⍵⊆⍨0≠≢¨⍵}(⊂∪⊃,/⍵)⍳¨⍵}
(⊂∪⊃,/⍵)⍳¨⍵} # Find the index of each element of the sublists against a uniquified flattened list
{⍵⊆⍨0≠≢¨⍵} # Partition the input into sections not containing empty list
⊃{ }/⍵}¨ # For each of the sections, reduce with this function
,⍺∘.,⍵ # Combine every element of the left with every element of the right. This gives all the possible choices of selection
0=≢⍵:0 # Unless the input was empty in which case return 0
⊃,/ # Flatten that a bit
{ }¨ # Then for each of these possible selections
¯1+⍳≢⍵ # Generate 0..length-1
⍵∘{ }¨ # and combine with the input
⍵↓⍺ # Dropping right many elements from left; this lets the streak start from anywhere in the list
⊃⊆⍨≠ # Partition over its own nub sieve to break possible streaks up
⊃,/ # Flatten
+/¨ # Sum each of them to get the streak length
⌈/ # Find the max of all streak lengths
0⌈ # and max with zero in case the previous was empty
💎
Created with the help of Luminespire.
Thanks to @Mat_rdv for suggestions and noting where the previous solution failed. I did not both golfing this down again afterwards because @Mat_rdv's answer in the comment is vastly superior at 52 chars.
Uiua, 31 bytes
⬚0/↥⊜(/↥♭≡⧅(⊗1⧆⇌)/(♭₂◇⊞⊂))±⊸≡◇⧻
±⊸≡◇⧻ # find non-[] days
⊜( # for each partition without []:
/(♭₂◇⊞⊂) # reduce by cartesian product
≡⧅( # for each prefix:
⊗1⧆⇌) # reverse, and find the first duplicate's index
/↥♭) # find the maximum across all
⬚0/↥ # find the maximum (default to 0)
so many parentheses.....
Prolog (SWI), 106 bytes
D-P-L:-D=[Y|R],(member(X,Y),\+member(X,P),R-[X|P]-L;R-[]-L);length(P,L).
D+M:-setof(L,D-[]-L,X),last(X,M).
Explanation
Ungolfed
streak(Log,Prev,Length) :-
Log=[Day|Rest],
( member(Animal,Day), \+ member(Animal,Prev), streak(Rest,[Animal|Prev],Length);
streak(Rest,[],Length)
);
length(Prev,Length).
max_streak(Log,Max) :- setof(Length,streak(Log,[],Length),Streaks), last(Streaks,Max).
The program defines two predicates. max_streak/2 is the main predicate which has the list representing the animal log as its first argument and produces the output by unifying it with its second argument. The other predicate, streak/3, takes the animal log as its first argument, a list representing the previously recorded streak animals (initially []) as its second argument, and the length of the possible streak as its third argument. It is important to note this length does not need to be that of the longest streak, so streak([[dog,cat]],[],0) is considered true, since, while suboptimal, a zero day streak is possible with that log of animals.
max_streak/2 works by using setof\3 to create the sorted list Streaks of all values of Length that satisfy the predicate streak(Log,[],Length), which will be a list of all possible lengths of streaks, sorted from least to greatest.
Then we produce the output by unifying Max with the last, and therefore greatest, element of Streaks using the last/2 predicate.
In streak/3 I make heavy use of Prolog's backtracking to briefly (and incredibly inefficiently) find possible streak lengths.
There are three branches that Prolog will check when streak/3 is called.
The first branch
Log=[Day|Rest], member(Animal,Day), \+ member(Animal,Prev), streak(Rest,[Animal|Prev],Length)
This branch gets the next day of the log and then attempts to find an animal in it that has not been previously used in the current streak.
If successful we add the animal to our streak and proceed onto checking the next day.
Note that, since we are finding all solutions to streak/3, Prolog's interpreter will end up attempting streaks with each possible animal in the log that was not already in the streak.
The second branch
Log=[Day|Rest],streak(Rest,[],Length)
This branch throws out the current streak and starts a new streak with the remaining days.
The third branch
length(Prev,Length)
The third branch forms the base case of the recursive predicate. No matter what the input, it is always valid to not try to add any more days to the streak, at which point we can determine its length.
Because Prolog is finding all values of Length that satisfy streak(Log,[],Length) it will traverse the second and third branches of streak/3 even when the first is satisfied. This ensures that the program considers all possible streaks.
JavaScript (ES6), 83 bytes
-4 thanks to @tata
f=([a,...b],o=f,n=0)=>a?Math.max(n,f(b),...a.map(s=>o[s]||f(b,{...o,[s]:1},n+1))):n
Commented
f = ( // f is a recursive function taking:
[ //
a, // a[] = next list of animals
...b // b[] = array of remaining lists
], //
o = f, // o = object to store selected animals
n = 0 // n = number of animals in o
) => //
a ? // if a[] is defined:
Math.max( // get the maximum of:
n, // the current value of n
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()
: // else:
n // return n
(*) 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.
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}])]))
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])]))
Nekomata, 6 bytes
qᵐ~ů#Å
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
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)})
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
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)
Brachylog, 10 9 (or 11?) bytes
{s∋ᵐ≠l}ᶠ⌉
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⌉
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
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)
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.