# CGAC2022 Day 23: North Pole Railroads

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

Santa and the Elves are secretly preparing for a new tourist train service, called "North Pole Railroads". The train will travel through various sightseeing spots near the North Pole.

As a part of this project, they want to know how many seats they will need. They already have the list of travels for each passenger (given as "from station X to station Y"), which is thanks to the same magic that lets Santa know which children are nice. Each station is numbered from 1, starting from the North Pole.

The Elves are arguing over how to determine the number of seats. One option is to absolutely minimize the number of seats needed. Elves will decide which passenger will take which seat. Two passengers with strictly overlapping travel cannot share a seat (e.g. one is (1, 3) and the other is (2, 4)), but a travel that ends at X is not overlapping with another that starts at X.

Given the list of X, Y pairs that represent the travel of each passenger, output how many seats will be needed for North Pole Railroads.

Standard rules apply. The shortest code in bytes wins.

## Test cases

(1, 2), (2, 3), (1, 3), (3, 4) -> 2
1---2---3---4
AAA BBB DDD
CCCCCCC

(1, 3), (1, 3), (3, 6), (3, 6) -> 2
1...3...6
AAA CCC
BBB DDD

(1, 5), (2, 8), (6, 9), (5, 7), (4, 6) -> 3
1...2...3...4...5...6...7...8...9
AAAAAAAAAAAAAAA DDDDDDD
BBBBBBBBBBBBBBBBBBBBBBB
EEEEEEE CCCCCCCCCCC

• Am I allowed 0-indexing of station numbers?
– Neil
Commented Dec 23, 2022 at 0:23
• @Neil It doesn't matter. The test cases can be interpreted as "there is Station 0, but no one boards there". Commented Dec 23, 2022 at 0:58
• Can we take input as two lists: starts and ends of the travels? Commented Dec 23, 2022 at 7:14
• @pajonk That's fine. Commented Dec 24, 2022 at 1:29
• Can the number of stations that exist be taken (as an additional input)?
– m90
Commented Dec 29, 2022 at 10:27

# Python 3, 48 bytes

lambda a:max(sum(p<x<[q]for*p,q in a)for x in a)


Try it online!

# Python 3, 50 bytes

lambda a:max(sum(p<=x<q for p,q in a)for x,y in a)


Try it online!

• 48 requires pairs to be lists. Commented Dec 23, 2022 at 12:24

# J, 24 20 bytes

[:>./[:+/1=,.I."#./]


Attempt This Online!

Found independently, but conceptually very similar to tsh's python approach.

• We find the "insert before" index of every left endpoint within every reversed range
• This will be 1 iff the left endpoint is contained within the range
• We sum all the ones for each left endpoint, giving us a count of how many ranges that endpoint is contained in
• Take the max of all the counts

## J, 24 bytes

[:>./[:#/.~@;<@i.@-+&.>]


Try it online!

• Generates all stops for each person (not including the endpoint), so eg 1 4 becomes 1 2 3.
• Groups the combined list of all stops by stop, and get a count.
• Returns the max count.

# R, 40 bytes

\(x,y)max(table(unlist(Map(seq,x,y-1))))


Attempt This Online!

Takes input as two vectors - of starts and ends of the travels.

# Vyxal, 5 bytes

rfĊ↑t


Try it online! Takes a list of start stations and a list of end stations.

r     # range (vectorises)
f    # flatten
Ċ   # counts of every element
↑  # get the maximum element by its tail
t # tail


## Vyxal, 7 bytes

∩÷rfĊ↑t


Try it online! The original solution, taking a list of pairs. This transposes ∩ then item splits ÷ first, before continuing with the solution above.

# Factor, 56 bytes

[ [ last2 [a,b) ] map concat histogram values supremum ]


Try it online!

                    ! { { 1 5 } { 2 8 } { 6 9 } { 5 7 } { 4 6 } }
[ last2 [a,b) ] map ! { { 1 2 3 4 } { 2 3 4 5 6 7 } { 6 7 8 } { 5 6 } { 4 5 } }
concat              ! { 1 2 3 4 2 3 4 5 6 7 6 7 8 5 6 4 5 }
histogram           ! H{ { 1 1 } { 2 2 } { 3 2 } { 4 3 } { 5 3 } { 6 3 } { 7 2 } { 8 1 } }
values              ! { 1 2 2 3 3 3 2 1 }
supremum            ! 3


M:($+:{@_Na,b}MUa)Ma  Try It Online! # Charcoal, 1917 15 bytes Ｉ⌈ＥθΣＥθ№…⌊λ⌈λ⌊ι  Try it online! Link is to verbose version of code. Edit: Saved 2 bytes by using Minimum and Maximum to obtain the starting and ending stations for each passenger. Saved a further 2 bytes by only checking the starting stations instead of all stations, which allowed me to rewrite the expression to make it work on TIO as well as ATO. Explanation:  θ Input journeys Ｅ Map over passengers θ Input journeys Ｅ Map over passengers № Count of ⌊ Starting station of ι Outer passenger in … Range from ⌊ Starting station of λ Inner passenger to ⌈ Ending station of λ Inner passenger Σ Take the sum ⌈ Take the maximum Ｉ Cast to string Implicitly print  • I can confirm this is correct. Commented Dec 23, 2022 at 1:26 # Jelly, 7 bytes ‘r"FĠẈṀ  Try it online! -2 bytes: Takes start stations and end stations as separate lists. ‘r"FĠẈṀ ‘ - increment r" - vectorized range F - flatten Ġ - group indices by value Ẉ - lengths Ṁ - maximum  # JavaScript (ES6), 61 bytes -3 thanks to @l4m2 a=>a.map(g=([p,q])=>p<q&&g([p+1,q],m+=m<(g[p]=-~g[p])),m=0)|m  Try it online! • 61 – l4m2 Commented Dec 23, 2022 at 3:30 # Python3, 237 bytes: lambda x:min(f(x)) def f(x): q=[(x,[])] while q: a,b=q.pop(0) if[]==a:yield len(b);continue for I,i in enumerate(b): if all(y<=a[0][0]or a[0][1]<=x for x,y in i):q+=[(a[1:],b[:I]+[[*i,a[0]]]+b[I+1:])] q+=[(a[1:],b+[[a[0]]])]  Try it online! # Nibbles, 9 bytes (18 nibbles) /.=~+!$_~>$,@$,$]  Takes input as lists of start stations and end stations. /.=~+!$_~>$,@$,$] !$_           # zip input lists together
~          # using function:
>$# drop inp1 elements ,@ # from range 1..inp2 + # now flatten the list of lists =~ # and group elements$     # by their own values;
.            ,\$   # get the length of each group
/                  # and fold over this list
]  #   returning the maximum


# Jelly, 7 bytes

r/ṖṬ)SṀ


A monadic Link that accepts a list of pairs of station numbers for the passengers and yields the minimum seat count.

Try it online!

### How?

r/ṖṬ)SṀ - Link: list of pairs of positive integers, P
)   - for each (board, alight) in P:
/      -   reduce by:
r       -     inclusive range -> [board, board+1, ..., alight]
Ṗ     -   pop (the passenger does not need their seat at their destination)
Ṭ    -   untruth - e.g. [3,4,5] -> [0,0,1,1,1]
S  - sum (the columns of that)
Ṁ - maximum


# Excel (ms365), 111 bytes

Formula in D1:

=MAX(BYROW(A1:B5,LAMBDA(a,LET(x,SEQUENCE(MAX(a)-MIN(a),,MIN(a)+1),MAX(COUNTIFS(A1:A5,"<="&x,B1:B5,">"&x),1)))))


import Data.Ix
import Data.List
s=maximum.map length.group.sort.concat.map(init.range)


Try it online!

# x86-64 machine code, 33 bytes

92 99 31 C9 57 56 AF 75 02 FF C9 AF 75 02 FF C1 FF CE 75 F2 5E 5F 39 D1 0F 47 D1 FF C8 75 E5 92 C3


Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes an array of pairs of 32-bit integers with the address in RDI and the length in ESI, and takes the number of stations in EDI.

This program runs backwards through the stations, keeping track of the number of passengers on the train, and the answer is the highest that number has been.

In assembly:

f:
xchg edx, eax   # Switch the number of stations into EAX.
cdq             # Set EDX to 0 by sign-extending EAX.
xor ecx, ecx    # Set ECX to 0.
# EAX will hold the current station, ECX the current number of passengers,
#  and EDX the highest number of passengers so far.
next_station:
push rdi        # Save the value of RDI onto the stack.
push rsi        # Save the value of RSI onto the stack.
next_passenger:
scasd           # Compare EAX and the value at address RDI, advancing the pointer.
jne s0          # (That value is the starting station.) Jump if they are unequal.
dec ecx         # (If they are equal) Subtract 1 from the current passenger count.
s0:
scasd           # Compare EAX and the value at address RDI, advancing the pointer.
jne s1          # (That value is the ending station.) Jump if they are unequal.
inc ecx         # (If they are equal) Add 1 to the current passenger count.
s1:
dec esi         # Subtract 1 from ESI, counting down from the number of passengers.
jnz next_passenger  # Jump back, to repeat, if it's not zero.
pop rsi         # Restore the value of RSI from the stack.
pop rdi         # Restore the value of RDI from the stack.
cmp ecx, edx    # Compare the current passenger count and EDX.
cmova edx, ecx  # If the current passenger count is higher, set EDX to that.
dec eax         # Subtract 1 from EAX, progressing backwards through the stations.
jnz next_station# Jump back, to repeat, if it's not zero.
xchg edx, eax   # Switch the highest passenger count into EAX (to be returned).
ret             # Return.


# C (gcc), 137134133 132 bytes

-2 byte thanks to @ceilingcat

m;n;k;i;q;l;main(c,v)int**v;{for(;++n-l;k=0)for(i=1;i++<c;m=fmax(k+=atoi(v[i++-1])<=n&n<q,m))l=fmax(q=atoi(v[i]),l);printf("%d",m);}


Try it online!

# 05AB1E, 8 bytes

εŸ¨}˜D¢à


Explanation:

ε      # Map over each pair of the (implicit) input-list:
Ÿ     #  Pop the pair, and push a list in the inclusive range of it
¨    #  Remove the last item (the destination-seat)
}˜     # After the map: flatten the list of lists
D    # Duplicate it
¢   # Pop both, and count how many times each occurs
à  # Pop and leave the maximum count
# (which is output implicitly as result)
`