Parking lot supervisor

Question

Introduction

You are a supervisor of a parking lot and your manager is preparing for shrinking the size to the extreme.

It is a simplified and adapted version of a problem in last year's PAT top-level.

Challenge

You are asked to calculate how many cars are in the lot at the same time, at most.

Standard rules apply. And this is a code-golf so shortest code wins.

First line is the quantity of entries (no more than 100,000, your input may not contain this line if you like, for it is only a makeshift to determine where input ends). The following text contains one entry per line. And each entry includes three numbers:

<Car plate number> <Time (seconds) since open> <0(In) | 1(Out)>

Modification 2: It is OK to use an array of triples as input.

Modification 3: You can change the order of numbers in one entry. And you can choose which to use. (see the Remarks section)

The input is guaranteed to be valid, assuming that:

• Car plate number is a integer in the range of 10000 ~ 99999
• Time is a integer in the range of 0 ~ 86400

And

• Entries are not necessarily chronologically ordered.
• There is no car before the first second.
• There is not necessarily no car after the last second.
• A car would not leave before it gets in.
• Car plate number is unique. (but a same car may visit for more than one time)
• So it is impossible for a car to enter the lot when it is already in it.
• A same car wouldn't go in and out at the same time.
• A car is considered to be in the lot at the time of in / out.

Example 1

Input

11
97845 36000 1
75487 16500 1
12345 16 0
75486 3300 0
12345 6500 1
97845 32800 0
12345 16400 0
97846 16501 1
97846 16500 0
75486 8800 1
75487 3300 0

Output

3

Explanation

At 16500, car 12345 and 75487 were in the parking lot.

Example 2

I made this because I found many code failed on it.

Input (with first line left out)

12345 16400 0
12345 16500 1
75487 16500 0
75487 16600 1

Output

2

Explanation

At 16500, car 12345 and 75487 were in the parking lot.

Remarks

Actually, not all three are required for the output. At least, you only need plate+time or in/out+time for the result. But the algorithm is slightly different under two circumstances, so the choice of being shorter stays unknown in a certain language. And of course you can use all of three numbers. So I leave them in the challenge.

Answer 1

Mathematica, 33 bytes

-Min@Accumulate[2#2-1&@@@Sort@#]&

I had to read the problem statement better to realize that there's a much simpler algorithm that doesn't require the license plate information.

Unnamed function returning an integer; the input format is a list of ordered triples in the form {time, 0|1, license plate}. We start by Sorting, which makes the list chronological and also breaks time-ties by sorting 0s before 1s; then 2#2-1&@@@ keeps the arrival/departure information and forgets the rest, and also converts 0s to -1s.

Accumulate calculates the running totals of that list; the result is a list of the negatives of the numbers of cars in the parking lot after every arrival/departure. Then Min picks the smallest (most negative) of these and the negative sign is stripped.

Mathematica, 56 bytes

Max[<|#|>~Count~0&/@FoldList[List,{},#3->#2&@@@Sort@#]]&

The original submission (the first several comments refer to this submission). Unnamed function returning an integer; the input format is a list of ordered triples in the form {time, 0|1, license plate}.

The reason we choose to put the time entry first and the in/out entry second is so that Sort@# sorts the list chronologically, and records arrivals before departures if they're simultaneous. After that, #3->#2&@@@ returns a list of "rules" of the form license plate -> 0|1, still sorted chronologically.

Then, FoldList[List,{},...] creates a list of all the initial segments of that list of rules. Actually, it really messes up those initial segments; the kth initial segment ends up being a list with one rule at depth 2, one rule at depth 3, ..., and one rule at depth k+1. (FoldList[Append,{},...] would yield the more natural result.) However, <|#|> turns each of these initial segments into an "association", which has two desirable effects: first, it completely flattens the nested-list structure we just created; and second, it forces later rules to override earlier rules, which is exactly what we need here—for any car that has left the parking lot, the record of its initial entry is now completely gone (and similarly for cars that re-enter).

So all that's left to do is to Count how many 0s there are in each of these associations, and take the Max.

Answer 2

Haskell, 76 63 61 bytes

2 bytes saved by a variation of @nimi's suggestion.

f l=maximum$scanl1(+)[(-1)^c|i<-[0..8^6],(_,b,c)<-l,i==2*b+c]

Expects the argument as a list of triples in the order given by the problem statement.

For each possible time (and some more), we search first for coming and then for leaving car events and turn them to a list of plus or minus ones. We take the partial sums of this list and then the maximun of these partial sums.

Answer 3

PHP 7.1, 126 117 bytes

for(;$s=file(i)[++$i];)$d[+substr($s,6)][$s[-2]]++;ksort($d);foreach($d as$a){$r=max($r,$n+=$a[0]);$n-=$a[1];}echo$r;

takes input from file i, ignores first line. Run with -r.
Requires a trailing newline in input. Replace -2 with -3 for Windows.

breakdown

# generate 2-dim array; first index=time, second index=0/1 (in/out);
# values=number of cars arriving/leaging; ignore plate number
for(;$s=file(i)[++$i];) # read file line by line (includes trailing newline)
    $d[+substr($s,6)][$s[-2]]++;    # substring to int=>time, last but one character=>1/0
ksort($d);                      # sort array by 1st index (time)
foreach($d as$a)    # loop through array; ignore time
{
    $r=max($r,                      # 2. update maximum count
        $n+=$a[0]                   # 1. add arriving cars to `$n` (current no. of cars)
    );
    $n-=$a[1];                      # 3. remove leaving cars from `$n`
}
echo$r;                         # print result

Answer 4

C, 147 bytes

A complete program, reads input from stdin.

int r[86402]={},u,i,n,t;g(s,o){for(;s<86401;n<r[s]?n=r[s]:0,++s)r[s+o]+=o?-1:1;}main(){for(n=0;scanf("%d%d%d",&u,&t,&i)==3;g(t,i));printf("%d",n);}

Try it on ideone.

Answer 5

Octave , 50, 64 38 bytes

@(A)-min(cumsum(sortrows(A)(:,2)*2-1))

Same as @Greg Martin 's Mathematica answer

The function gets an array with 3 columns [time, i/o,plateN]

previous answer:

@(A){[t,O]=A{:};max(cumsum(sparse({++t(!O),t}{2},1,!O*2-1)))}{2}

The function only gets two inputs t: time and O: I/O from first two element of a cell array A that contains triple inputs!

A sparse matrix created to count for each recorded time number of existing cars . For it time of out + 1 is considered for car exit and corresponding 1 change to -1 and 0 changed to 1.
Use of sparse here is very important since multiple cars may arrive or leave at the same time.
Then cumulative sum computed representing number of current cars in the lot and max of it is found.

Answer 6

JavaScript (ES6), 63 73 71 bytes

d=>Math.max(...d.sort((a,[b,c])=>a[s=0]-b||a[1]-c).map(e=>s+=1-e[1]*2))

This accepts input as an array of entries ordered [time, inout, plate]. Unfortunately due to the fact that identical inout times means that both cars are considered in the lot at the moment in time, the sorting algorithm must order 0 prior to 1, which costed 11 bytes.

Credits

• I saved 1 byte by moving the shift and multiplication inside the map function completely (thanks Neil).
• I saved another two bytes by using a destructured argument in the sort function (thanks edc65).

Demo

// test the two examples
console.log([[[36000,1],[16500,1],[16,0],[3300,0],[6500,1],[32800,0],[16400,0],[16501,1],[16500,0],[8800,1],[3300,0]],[[16400,0],[16500,1],[16500,0],[16600,1]]].map(
// answer submission
d=>Math.max(...d.sort((a,[b,c])=>a[s=0]-b||a[1]-c).map(e=>s+=1-e[1]*2))
));

Answer 7

JavaScript (ES6), 83 … 68 70 bytes

EDIT: fixed to support the 2nd example

Takes input as an array of [in_out, time, plate] arrays. But the plate column is actually ignored.

a=>a.sort(([a,b],[c,d])=>b-d||a-c).map(v=>a=(n+=1-v[0]*2)<a?a:n,n=0)|a

Test

let f =

a=>a.sort(([a,b],[c,d])=>b-d||a-c).map(v=>a=(n+=1-v[0]*2)<a?a:n,n=0)|a

console.log(f([
  [1, 36000, 97845],
  [1, 16500, 75487],
  [0, 16,    12345],
  [0, 3300,  75486],
  [1, 6500,  12345],
  [0, 32800, 97845],
  [0, 16400, 12345],
  [1, 16501, 97846],
  [0, 16500, 97846],
  [1, 8800,  75486],
  [0, 3300,  75487]
]));

console.log(f([
  [0, 16400, 12345],
  [1, 16500, 12345],
  [0, 16500, 75487],
  [1, 16600, 75487]
]));