informatiCup / informatiCup2022

Abfahrt! Der InformatiCup 2022
22 stars 3 forks source link

Depart and detrain timing #16

Closed DieGoldeneEnte closed 2 years ago

DieGoldeneEnte commented 2 years ago

Consider the following input.txt:

# Bahnhöfe: str(ID)
[Stations]
S1 10
S2 10
S3 10
S4 10

# Strecken: str(ID) str(Anfang) str(Ende) dec(Länge) int(Kapazität)
[Lines]
L1 S1 S2 2 1
L2 S2 S3 5 1
L3 S3 S4 1 1

# Züge: str(ID) str(Startbahnhof)/* dec(Geschwindigkeit) int(Kapazität)
[Trains]
T1 S1 2 50

# Passagiere: str(ID) str(Startbahnhof) str(Zielbahnhof) int(Gruppengröße) int(Ankunftszeit)
[Passengers]
P1 S1 S4 50 10

This is a network with train and passenger at s and target station at t (numbers represent line length):

s------(4)------x-------(5)--------x---(1)------t

and the following output.txt:

[Train:T1]
2 Depart L1
3 Depart L2
5 Depart L3

[Passenger:P1]
1 Board T1
6 Detrain

According to the simulator this is valid. As far as I understand the specification, the train needs

In practice this output only has

In my opinion the correct minimum output.txt should be:

[Train:T1]
2 Depart L1
4 Depart L2
7 Depart L3

[Passenger:P1]
1 Board T1
9 Detrain
Top-Ranger commented 2 years ago

The simulator is working as defined, I'll explain it for your input:

2 Depart L1

The train depatures at round two and travels in round two for a distance of 2. Since this is also the length of the line, it arrives at the Station in round two.

3 Depart L2
5 Depart L3

The train depatures at round five and travels in round five for a distance of 1 and arrives at the station theoretically in round 5,5. Since the simulation has discrere steps, it arrives in round six.

DieGoldeneEnte commented 2 years ago

I messed up the input I send, the visualization is what I actually used (L1 has length 4), which according to the simulator is still valid. This is the correct input.txt:

# Bahnhöfe: str(ID)
[Stations]
S1 10
S2 10
S3 10
S4 10

# Strecken: str(ID) str(Anfang) str(Ende) dec(Länge) int(Kapazität)
[Lines]
L1 S1 S2 4 1
L2 S2 S3 5 1
L3 S3 S4 1 1

# Züge: str(ID) str(Startbahnhof)/* dec(Geschwindigkeit) int(Kapazität)
[Trains]
T1 S1 2 50

# Passagiere: str(ID) str(Startbahnhof) str(Zielbahnhof) int(Gruppengröße) int(Ankunftszeit)
[Passengers]
P1 S1 S4 50 10

But even for the input with L1 having a length of 2 another issue still remains: As you say the train arrives in round six, but according to the specification

Dabei ist zu beachten, dass bei einem Zug in der Abfahrts- und Ankunftsrunde keine Passagiere einsteigen oder aussteigen können.

and the passengers can detrain in round 6 anyways.

The simulation only has a problem if I increase the length of L1 to 5.

If I understand you correctly a train can move to a station in one time step and from a station in the same time step effectively moving double the distance if driving through a station.

I believe a note in the specification would help, if this is intended behavior, since it is counterintuitive.

Top-Ranger commented 2 years ago

The solution is still correct:

  1. P1 Boards
  2. T1 leaves S1, T1 is at 2/4 on L1
  3. T1 is at 4/4 on L1 therefore T1 reaches S2, T1 leaves S2, T1 is at 2/5 on L2
  4. T1 is at 4/5 on L2
  5. T1 is at 5/5 on L2 therefore T1 reaches S3, T1 leaves S3, T1 is at 1/1 on L3 therefore T1 reaches S4
  6. P1 detrains
DieGoldeneEnte commented 2 years ago

OK, thanks. It seems I misunderstood the model, since I assumed a train can only perform one action (driving/departing) in a round.

Thanks for the clarification.

jfreyberg commented 2 years ago

Since the train does not move in timestep 1 and 6 according to this solution, the train only moves in timestep 2-5 i.e. during 4 timesteps. Since speed of the train is 2, in 4 timesteps it should be able to move 8 length units at maximum. However, the sum of the line lengths is 4 + 5 + 1 = 10.

This is because according to your solution in timestep 3 the train moves 2 units of length on line L1 and another 2 on line L2. I do not believe that this is the intended behavior of the model as it clearly violates the underlying assumptions of line length and speed.