1. J. Särnbratt and O. Düsterdieck
Calling
NAV.append(AI_ST(C, N))
will return an AI with the default values, the default values give quicker runtime and worse score.
The times below is from our school computer, the specs of which are unknown but probably comparable to a standard PC.
Below stats are for C=10, N=20, iterations=1000000
AI_ST(C, N, far=12, turnLength=0)
runtime: 2 minutes
score: 1.0
AI_ST(C, N, far=15, turnLength=1)
runtime: 5 minutes
score: 0.965
AI_ST(C, N, far=15, turnLength=3) (the same as AI_ST(C, N))
runtime: 10 minutes
score: 0.96
AI_ST(C, N, far=19, turnLength=5)
runtime: 15 minutes
score: 0.95
AI_ST(C, N, far=19, turnLength=8)
runtime: 25 minutes
score: 0.93
Number of competitors: 5
– Profiling: smart turner 15 1
*Score for this round: 0.958438
*Time for this round: 29 seconds
– Profiling: smart turner 15 2
*Score for this round: 0.9590235
*Time for this round: 43 seconds
– Profiling: smart turner 15 3
*Score for this round: 0.959436
*Time for this round: 58 seconds
– Profiling: smart turner 15 4
*Score for this round: 0.9520705
*Time for this round: 71 seconds
– Profiling: smart turner 15 5
*Score for this round: 0.948906
*Time for this round: 85 seconds
How our algorithm works:
To achieve the lowest score we try to fill the bus as efficiently as possible.
Our measure of efficiency is having as few empty seats during the next N steps as possible.
This is done by first choosing a route and then packing the bus as efficiently as possible during this route.
Each route is given a score, the route with the highest score is chosen.
Choosing a route:
The routes chosen are:
Continue in the current direction for F steps.
Go in opposite direction for F steps.
Go f steps in current direction, and then (F-f) steps in opposite direction.
Packing the bus:
For all passengers currently waiting we calculate:
1. How far they will sit on the bus using current route.
2. How far the bus will travel before picking them up.
The list of passengers is sorted according to these two values.
The passengers are added in order to the bus if they fit.
(In this step “added” means that the passenger contributes to the score of this route, only passengers picked up immediately from the best route are actually added.)
Scoring the route:
Since the passengers added very late are less likely to actually be picked up, they are weighted.
When the best route is chosen, the passengers picked up on the first station of the best route is returned by step().
Busy bus 