# Number of FIFO cache misses

This challenge is really simple (and a precursor to a more difficult one!).

Given an array of resource accesses (simply denoted by nonnegative integers) and a parameter n, return the number of cache misses it would have assuming our cache has capacity n and uses a first-in-first-out (FIFO) ejection scheme when it is full.

Example:

4, [0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 0, 1, 2, 3]
0 = not in cache (miss), insert, cache is now 
1 = not in cache (miss), insert, cache is now [0, 1]
2 = not in cache (miss), insert, cache is now [0, 1, 2]
3 = not in cache (miss), insert, cache is now [0, 1, 2, 3]
0 = in cache (hit), cache unchanged
1 = in cache (hit), cache unchanged
2 = in cache (hit), cache unchanged
3 = in cache (hit), cache unchanged
4 = not in cache (miss), insert and eject oldest, cache is now [1, 2, 3, 4]
0 = not in cache (miss), insert and eject oldest, cache is now [2, 3, 4, 0]
0 = in cache (hit), cache unchanged
1 = not in cache (miss), insert and eject oldest, cache is now [3, 4, 0, 1]
2 = not in cache (miss), insert and eject oldest, cache is now [4, 0, 1, 2]
3 = not in cache (miss), insert and eject oldest, cache is now [0, 1, 2, 3]


So in this example there were 9 misses. Maybe a code example helps explain it better. In Python:

def num_misses(n, arr):
misses = 0
cache = []
for access in arr:
if access not in cache:
misses += 1
cache.append(access)
if len(cache) > n:
cache.pop(0)
return misses


Some further testcases (which contains a hint towards the next challenge - notice anything curious?):

0, [] -> 0
0, [1, 2, 3, 4, 1, 2, 3, 4] -> 8
2, [0, 0, 0, 0, 0, 0, 0] -> 1
3, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 9
4, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 10


Shortest code in bytes wins.

• I was looking at the last statement notice anything curious? for a while now... and just noticed, increasing the cache capacity doesn't necessarily decrease the number of misses?! Jun 11, 2018 at 19:37
• @JungHwanMin Correct! In fact, how much worse it can get is unbounded.
– orlp
Jun 11, 2018 at 19:45
• Can we output the number in unary? Jun 11, 2018 at 22:26
• Known as Bélády's anomaly and FIFO is the classic example. The anomaly is unbounded. Jun 11, 2018 at 23:05
• @dylnan No, sorry.
– orlp
Jun 12, 2018 at 6:56

# JavaScript (ES6), 55 bytes

### Method #1: the cache overwrites the input

Takes input in currying syntax (cache_size)(list).

n=>a=>a.map(x=>a[a.indexOf(x,k>n&&k-n)<k||k++]=x,k=0)|k


Try it online!

### How?

We overwrite the input array a[ ] with the cache, using a separate pointer k initialized to 0.

We use a.indexOf(x, k > n && k - n) < k to test whether x is in the cache.

The cache can't grow faster than the original array is walked through, so each value is guaranteed to be found, either within or beyond the cache window (i.e. indexOf() will never return -1).

A value is in the cache if it is found at an index between max(0, k - n) and k - 1 (both bounds included), in which case we do a[true] = x. This only affects a property of the underlying object behind a[ ] but does not alter the array a[ ]. Otherwise, we do a[k++] = x.

### Example

Below are the different steps for the input [1, 1, 2, 3, 3, 2, 1, 4] with a cache size of 2:

• bold borders: map() pointer
• brackets: cache pointer k
• orange: current cache window
• yellow: expired cache values # JavaScript (ES6), 57 bytes

### Method #2: the cache is appended at the end of the input

Takes input in currying syntax (cache_size)(list).

n=>a=>a.map(x=>n*~a.indexOf(~x,-n)||a.push(~x)&k++,k=0)|k


Try it online!

### How?

Because the input array a[ ] is guaranteed to contain non-negative integers, we can safely append the cache at the end of a[ ] by using the one-complement ~x of each value x.

We use n * ~a.indexOf(~x, -n) to test whether ~x is found among the last n values. Whenever this test fails, we append ~x to a[ ] and increment the number of misses k.

### Example

Below are the different steps for the same example as above, using this method. Because cache values are simply appended at the end of the array, there is no explicit cache pointer. f n=length.foldl(\r x->[x|all(/=x)$take n r]++r)[]  Try it online! Based on Lynn's method of storing the whole cache history and taking its length. Unary output would be a bit shorter: Haskell, 47 bytes n?l=1<$foldl(\r x->[x|all(/=x)$take n r]++r)[]l  Try it online! # Python 2, 58 bytes lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[]))  Try it online! Thanks to ovs for 3 bytes, and xnor for 3 more. • You should be able to save bytes by putting a set after c+=, since for some reason it converts to a list for you. – xnor Jun 11, 2018 at 20:17 • (ah, yes, c+={i}-set(c[-n:]) works, for positive n. But nimi pointed out that c[-n:] is wrong for n == 0, so I can’t use +=, and hence that trick – too bad.) – Lynn Jun 11, 2018 at 20:58 • @Lynn Ah, I see. reduce still saves bytes: lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[])). – xnor Jun 11, 2018 at 22:51 # R, 6964 62 bytes function(n,A,K={}){for(i in A)K=c(i[!i%in%K[0:n]],K);sum(K|1)}  Try it online! Thanks to JayCe for suggesting some improvements, and DigEmAll for another couple! • I guess the + in front of Fis for f(0,{}) to return 0? Jun 11, 2018 at 19:28 • @JayCe yep, a classic golf in tandem with F as a pre-initialized return value. Jun 11, 2018 at 19:30 • a small improvemement. Also if unary output is accepted you can probably save some bytes. Jun 12, 2018 at 0:29 • @JayCe found some more bytes! Jun 12, 2018 at 0:36 • @JDL yeah, a shame about the q but still a nice idea! Using NA is less good than using {} since I actually care about the length here (and I'm not actually popping elements from the cache). Jun 13, 2018 at 10:28 ## Haskell, 61 58 bytes n!a|let(a:b)#c|elem a c=b#c|1<2=1+b#take n(a:c);_#_=0=a#[]  Try it online! n!a| =a#[] -- take input 'n' and a list 'a' -- and call # with the initial list and an empty cache let -- bind function '#': (a:b)#c -- if there's at least one element 'a' left in the list |elem a c=b#c -- and it's in the cache, go on with the same cache -- and the remainder of the list |1<2= -- else (i.e. cache miss) 1+ -- add one to the recursive call of b# -- the remainder of the list and take n(a:c) -- the first n elements of 'a' prepended to the cach _#_=0 -- if there's no element in the list, return 0  Edit: -3 bytes thanks to @Lynn. # 05AB1E, 17 16 bytes )svDyå_i¼y¸ìI£]¾  Try it online! Explanation ) # wrap the stack in a list sv # for each item y in input list D # duplicate current list yå_i # if y is not contained in the current list ¼ # increment counter y¸ì # prepend y to the current list I£ # keep the first input elements ]¾ # end loop and push counter  # Kotlin, 82 69 bytes {a,n->a.fold(List(0){0}){c,v->if(v!in c.takeLast(n))c+v else c}.size}  Takes input as an IntArray, not the typical List<Int> (which shouldn't be a problem.) This uses the approach of "build a cache history and count its length". Try it online! ## Explanation { a, n -> // lambda where a is accesses and n is cache size a.fold(List(0){0}) { c, v -> // fold on empty list if(v !in c.takeLast(n)) // if resource is not in last n cache inserts c + v // insert to cache list else c // return cache as is }.size // length of cache list is number of inserts }  ### Creating an empty list Kotlin does not have collection literals, but it does have some functions to create new collections. The proper way to create an empty List<Int> is simply: List<Int>()  but it is shorter if we abuse the size and initializer args to do this: List(0){0} List(0) // List of size 0 { 0 } // with generator returning 0  Because the generator lambda returns 0, Kotlin infers the type of this list as List<Int>, and the size of 0 means this list is empty. # Perl 6, 48 bytes {my@c;$_∈@c.tail($^n)||push @c,$_ for @^o;+@c}


Test it

{  # bare block with placeholder params $n,@o my @c; # cache$_ ∈ @c.tail($^n) # is the current value in the last bit of the cache || push @c,$_       # if not add it to the cache

for                   # do this for all of

@^o;                # the input array

+@c                   # numify the cache (the count)
}


# Java 8, 96 bytes

A curried lambda taking a cache size (int) and access list (mutable java.util.List<Integer>) and returning an int.

s->a->{int w=0,m=0,i;for(int r:a)m+=(i=a.indexOf(r))<w&i<s?0:s<1?1:1+0*a.set(w++%s,r);return m;}


Try It Online

## Ungolfed

This uses the first (up to) s slots in the input list for the cache.

s ->
a -> {
int
w = 0,
m = 0,
i
;
for (int r : a)
m +=
(i = a.indexOf(r)) < w & i < s ?
0
s < 1 ?
1
: 1 + 0*a.set(w++ % s, r)
;
return m;
}


## Acknowledgments

• bugfix thanks to nimi

# Pyth,  16 15 18 14  13 bytes

Saved 1 byte thanks to isaacg.

luaW-H>QGGHEY


Test suite!

This challenge is very well suited to Pyth's u structure.

### How it works

luaW-H>QGGHEY     Full program. Q = the cache length, E = the list.
u         E      Reduce E with G = current value and H = corresponding element
Y     With starting value Y, which is preinitialised to [] (empty list).
W              Conditional application. If...
-H            ... Filtering H on absence of...
>QG         ... The last Q elements of G...
... Yields a truthy value (that is, H is not in G[-Q:]), then...
a      GH       ... Append H to G.
... Otherwise, return G unchanged (do not append H at all).
l                  Get the length of the result.

• aW-H>QGGH beats ?}H<GQG+HG by 1 Jun 12, 2018 at 4:04
• @isaacg Thanks! I initially had +G*]H!}H>QG, but when I golfed it I really haven't thought of W... Nice! Jun 12, 2018 at 6:12
• What exactly does u do? Jun 12, 2018 at 15:06
• @dylnan u is a reduce with intial value operator. Just like Jelly's ƒ Jun 12, 2018 at 15:29

# Wolfram Language (Mathematica), 60 59 bytes

Tr[k={};n=#;k~Take~UpTo@n~FreeQ~#&&k~PrependTo~#&/@#2;1^k]&


Try it online!

### Using pattern-matching, 60 bytes

Length[#2//.{p___,a_,q___,a_,r___}/;Tr[1^{q}]<#:>{p,a,q,r}]&


I really like this one better, but it's 1 byte longer...

Try it online!

# Japt, 16 bytes

;£A¯V øX ªAiXÃAl


Try it

## Explanation

                     :Implicit input of array U and integer V
£                   :Map over each X in U
; A                  :  Initially the empty array
¯V                :  Slice to the Vth element
øX             :  Contains X?
ª           :  Logical OR
AiX        :  Prepend X to A
Ã       :End map
Al     :Length of A


# K4, 42 40 bytes

Solution:

{*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[x]\y}


Examples:

q)k)f:{*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[x]\y}
q)f[0;1 2 3 4 1 2 3 4]
8
q)f[2;0 0 0 0 0 0 0]
1
q)f[3;3 2 1 0 3 2 4 3 2 1 0 4]
9
q)f[4;3 2 1 0 3 2 4 3 2 1 0 4]
10


Explanation:

For the inner function, y is the cache, z is the request and x is the cache size.

{*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[x]\y} / the solution
{                                      } / lambda taking 2 args
{                         }       / lambda taking 3 args
[x]\y  / iterate over lambda with each y
*|y        / last (reverse, first) y
y:           / assign to y
z in              / is z in y?
~                  / not
r:                   / assign result to r (true=1,false=0)
( ;     )                     / 2-element list
z,y                      / join request to cache
x#                         / take x from cache (limit size)
y                            / (else) return cache unchanged
,                              / enlist this result
r,                               / join with r
1_                                  / drop the first result
1+/                                    / sum up (starting from 1)
*                                       / take the first result


Notes:

There is probably a nicer way to do all of this, but this is the first way that came to mind.

The function can be ran like this for 36 bytes:

q)k)*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}\3 2 1 0 3 2 4 3 2 1 0 4
10


Alternative - using a global variable to store state (not very K-like), 42 bytes:

{m::0;(){$[z in y;y;[m+:1;x#z,y]]}[x]\y;m}  # Brain-Flak, 172 bytes (([{}]<>)<{({}(()))}{}>)<>([]){{}<>((({})<{({}()<<>(({})<({}<>({}<>))>)<>>)}{}>)<<>(({})([{}]<>{<>(){[()](<{}>)}{}<><({}()<<>({}<>)>)>}{})){(<{}{}>)}{}>)<>([])}{}<>({}[]<>)  Try it online! # Initialize cache with n -1s (represented as 1s) (([{}]<>)<{({}(()))}{}>)<> # For each number in input ([]){{} # Keep n on third stack <>((({})< # For last n cache entries, compute difference between entry and new value {({}()<<>(({})<({}<>({}<>))>)<>>)}{} >)< # Get negation of current entry and... <>(({})([{}]<> { # Count cache hits (total will be 1 or 0) <>(){[()](<{}>)}{} # while moving entries back to right stack <><({}()<<>({}<>)>)> }{} )) # If cache hit, don't add to cache {(<{}{}>)}{} >) <>([])}{} # Compute cache history length minus cache size (to account for the initial -1s) <>({}[]<>)  # Jelly, 18 bytes Ṗɼṛ;ɼe®Uḣ⁴¤C$¡€ṛLɼ


Try it online!

Takes the list as the first argument and cache capacity as second argument.

Ṗɼṛ;ɼe®Uḣ⁴¤C$¡€ṛLɼ ɼ Apply to the register: Ṗ Pop. This initializes the register to the empty list. ṛ Right argument. Yields the list of addresses. € For each element in the list ¡ If{ e the element is in ¤ nilad{ ® the register U reversed ḣ first... ⁴ (cache depth) number of elements } C Complement. 1 <-> 0. Easier to type this than "not".$          Combines everything up to e into a monad
}
Then{
ɼ                    Apply to the register and store the result
;                     Append the element
}
ṛ   Right argument:
ɼ Apply to the register:
L  Length


# Ruby, 43 40 bytes

->s,a,*r{a.count{|*x|r!=r=(r|x).pop(s)}}


Try it online!

Thanks histocrat for shaving 3 bytes.

• Nice answer! You can save a couple bytes by initializing r as part of the argument list: ->s,a,*r which also provides the bonus feature that the caller can prime the cache by passing extra arguments :) Jun 13, 2018 at 20:17
• Oh, and similarly to cast x into an array: .count{|*x| Jun 13, 2018 at 20:29

# C (gcc), 112 110 108 bytes

f(x,y,z)int*y;{int*i=y+z,b[x],m=0;for(wmemset(b,z=-1,x);i-y;y++)wmemchr(b,*y,x)?:++m*x?b[z=++z%x]=*y:0;x=m;}


Try it online!

Slightly less golfed

f(x,y,z)int*y;{
int*i=y+z,b[x],m=0;
for(wmemset(b,z=-1,x);i-y;y++)
wmemchr(b,*y,x)?:
++m*
x?
b[z=++z%x]=*y
:
0;
x=m;
}


# C (gcc), 156 bytes

s,n,m,i,j;f(x,_)int*_;{int c[x];n=m=0;for(i=0;i<x;++i)c[i]=-1;for(i=s=0;_[i]>=0;++i,s=0){for(j=0;j<x;++j)s|=(c[j]==_[i]);if(!s){c[n++]=_[i];m++;n%=x;}}x=m;}


Try it online!

Description:

s,n,m,i,j;                       // Variable declaration
f(x,_)int*_;{                    // F takes X (the cache size) and _ (-1-terminated data)
int c[x];                    // declare the cache
n=m=0;                       // next queue insert pos = 0, misses = 0
for(i=0;i<x;++i)c[i]=-1;     // initialize the cache to -1 (invalid data)
for(i=s=0;_[i]>=0;++i,s=0){  // for each datum in _ (resetting s to 0 each time)
for(j=0;j<x;++j)         // for each datum in cache
s|=(c[j]==_[i]);     // set s if item found
if(!s){                  // if no item found
c[n++]=_[i];         // add it to the cache at position n
n%=x;                // move to next n position (with n++)
}} x=m;}                 // 'return' m by assigning to first argument

• Suggest wmemset(c,-1,x) instead of n=m=0;for(i=0;i<x;++i)c[i]=-1, n=m=i=s=0 instead of i=s=0, for(j=x;j--;) instead of for(j=0;j<x;++j), and s||(c[n++]=_[i],m++,n%=x); instead of if(!s){c[n++]=_[i];m++;n%=x;} Jun 12, 2018 at 0:34

# JavaScript (Node.js), 44 bytes

n=>a=>a.map(y=t=>y[t]+n>p||(y[t]=++p),p=0)|p


Try it online!

# Jelly, 17 bytes

Ṗœ|Ṛḣ⁴\$Ṛʋ\-;⁸e"ċ0


Try it online!

Full program.

Argument 1: stack (Python 3 list of integers)
Argument 2: n (Python 3 integer)

# Rust, 129 bytes

|l:&[_],s|if s>0{let(mut c,mut m)=(vec![-1;s],0);for n in l.iter(){if!c.contains(n){c.remove(0);c.push(*n);m+=1;}}m}else{l.len()}


Try it online!

## Ungolfed

|l: &[isize], s: usize| {
if s > 0 {
let mut c = vec![-1; s];
let mut m = 0;
for n in l.iter() {
if !c.contains(n) {
c.remove(0);
c.push(*n);
m += 1;
}
}
m
} else {
l.len()
}
}


# Stax, 15 bytes

Ç═╛¢s▲▬╓í±°☻÷hi


Run and debug it