13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Are car plate numbers always 5 digits long? \$\endgroup\$ – Titus Jan 7 '17 at 18:22
  • 1
    \$\begingroup\$ @Titus I believe numbers from 10000 to 99999 are always 5 digits long. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 18:30
  • 3
    \$\begingroup\$ Gee I´m blind today. \$\endgroup\$ – Titus Jan 7 '17 at 18:31
  • \$\begingroup\$ I assume a car can't enter again before leaving leaving the first time? It doesn't seem to be stated explicitly. \$\endgroup\$ – John Dvorak Jan 7 '17 at 19:01
  • \$\begingroup\$ @JanDvorak eh sorry. No it cannot. It is implied by car plate number is unique because in reality it is impossible for one same car to enter the lot when it is already in it. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 19:03
7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Will this always do the right thing if cars come and go at the same time? \$\endgroup\$ – Christian Sievers Jan 7 '17 at 19:57
  • \$\begingroup\$ Your answer may be wrong. The maximum doesn't necessarily happen when a car entered once again so it is unsafe to erase entries using association. See this picture: i.imgur.com/D5xUl3z.png Obviously there are 3 cars at 16500. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 20:02
  • \$\begingroup\$ @KeyuGan: I didn't claim that the maximum happens when a car re-enters. Note that my solution counts the number of cars in the parking lot at the time of every single entry/departure, and takes the maximum of those. \$\endgroup\$ – Greg Martin Jan 7 '17 at 20:07
  • 1
    \$\begingroup\$ Maybe you could try the example 2. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 20:13
  • 1
    \$\begingroup\$ Personally I agree with you. :) What I have done is to copy the definition from the original problem. The major difference is that the original one requires car plates being recognized from images and printed as the final result. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 20:59
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Drop the import and use [(-1)^c|i<-[1..86400],(_,b,c)<-l,i==b]. \$\endgroup\$ – nimi Jan 7 '17 at 19:00
  • \$\begingroup\$ I need the incoming cars before the outgoing ones, so it is a bit more complicated, but I could still save 2 bytes with your idea. Thanks! \$\endgroup\$ – Christian Sievers Jan 7 '17 at 19:33
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Sorry you may use an array of triples as input if you are writing a function. My friends and I believe it is a good way to make non-golfing language more competitive if we are talking about a problem without complicated input. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 19:08
  • \$\begingroup\$ @KeyuGan:Thanks for the hint; but with an array as input, I´d need a function, and that would costs two bytes, both with an array of triplets and with a triplet of arrays. functions, array mapping and custom sort are bulky in PHP. Only way I could save anything would be my prepared $d as input or sorted input (by time and in/out). And thast would take too much from the challenge. Aligned input ttttt i plate would save 17 bytes, 19 more with the count aligned with the plate number. \$\endgroup\$ – Titus Jan 8 '17 at 7:19
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I believe it is safe to remove spaces between %d \$\endgroup\$ – Keyu Gan Jan 7 '17 at 20:49
  • \$\begingroup\$ Oops, thanks. I don't use scanf enough, I guess. \$\endgroup\$ – owacoder Jan 7 '17 at 20:51
  • \$\begingroup\$ I love cin. LOL \$\endgroup\$ – Keyu Gan Jan 7 '17 at 20:55
  • \$\begingroup\$ 118 bytes \$\endgroup\$ – ceilingcat Oct 11 '18 at 6:46
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I remember Octave support cell array, which means you may only use one array of triples as input. The restriction is according to the edition before M5 and it states 'an array of triples'. I have clarified it in M5 \$\endgroup\$ – Keyu Gan Jan 7 '17 at 21:40
  • \$\begingroup\$ @KeyuGan I think your new invented restriction is unnecessary increased 14 bytes of my code. so You are new to this site it is better to have questions with minimal number of restrictions to attract more contributors. \$\endgroup\$ – rahnema1 Jan 7 '17 at 22:00
2
\$\begingroup\$

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))
));

\$\endgroup\$
  • \$\begingroup\$ It seems your code doesn't work well on d=[[16400,75487,0],[16500,75487,1],[16500,99999,0],[16600,99999,1]]; I supposed it should print 2? \$\endgroup\$ – Keyu Gan Jan 7 '17 at 21:12
  • \$\begingroup\$ Well in the 4-entry test case, there are only 2 cars. I have formatted it to meet your input order. \$\endgroup\$ – Keyu Gan Jan 7 '17 at 21:15
  • \$\begingroup\$ @KeyuGan sorry for the misunderstanding, I didn't realize you were referring to the second example. It's fixed now. \$\endgroup\$ – Patrick Roberts Jan 7 '17 at 21:43
  • \$\begingroup\$ I know your algorithm doesn't depend on plate number. However I suggest it should be included in the definition of input order, just leave it to the last ;) \$\endgroup\$ – Keyu Gan Jan 7 '17 at 21:48
  • 1
    \$\begingroup\$ @edc65 actually, only 2 bytes, not 4. This is also 71 bytes: d=>Math.max(...d.sort(([a,b],[c,d])=>a-b||c-d).map(e=>s+=1-e[1]*2,s=0)) \$\endgroup\$ – Patrick Roberts Jan 8 '17 at 10:21
2
\$\begingroup\$

JavaScript (ES6), 8368 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]
]));

\$\endgroup\$
  • \$\begingroup\$ Reading the in_out column instead of the plate column should save you six bytes: v=>n+=1-v[2]*2. \$\endgroup\$ – Neil Jan 7 '17 at 20:41
  • \$\begingroup\$ This is incorrect for the second example, so if you edit this again, you'll need to take that into account. (Since the last edit on this was before the second example was added, it's technically exempt from complying to it, and I'm not at all jealous!) \$\endgroup\$ – Patrick Roberts Jan 7 '17 at 21:49
  • \$\begingroup\$ @PatrickRoberts Will try to fix that when I'm back in front of a computer ^^ \$\endgroup\$ – Arnauld Jan 7 '17 at 21:52
  • \$\begingroup\$ @Neil Good catch! I had to rewrite it anyway to support the 2nd example, but I ended up following your advice. \$\endgroup\$ – Arnauld Jan 8 '17 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.