The cartographer's table

Problem

Palma de Mallorca, 1375. Yehuda draws sea charts, and his table can hold at most cap open charts; the rest sleep rolled up in the cellar.

You get requests, the numbers of the charts he will look at, in order (whole numbers; the list may be empty and may repeat), and cap, a whole number greater than 0. The table starts empty. For each request: if the chart is already on the table, he does not go down, and that chart becomes the most recently used one. If it is not, he goes down for it; if the table already holds cap charts, he first takes back the one that has gone unused the longest, and the new one becomes the most recent. Return a whole number: how many times he went down.

With [1, 2, 3, 1, 4, 2] and cap 3: he goes down for 1, 2 and 3. Chart 1 is already there, so he stays, and now 2 is the one unused the longest. For 4 he goes down and takes back 2; for 2 he goes down again and takes back 3, now the oldest. He went down 5 times.

Examples

• The example

  [1, 2, 3, 1, 4, 2], 3 → 5

• Using it saves it

  [1, 2, 1, 3, 1, 2], 2 → 4

• Always the same one

  [4, 4, 4, 4], 1 → 1

• Room for just one

  [1, 2, 1, 2], 1 → 4

• They all fit

  [3, 1, 3, 2, 1], 5 → 3

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def trips_down(requests, cap):
    pass

function tripsDown(requests, cap) {
}