type BusRoute = record first : 0..29; interval: 1..59; { in fact, first < interval <= 59 - first } howoften: 2..60; { howoften = 1 + (59 - first) div interval } end;The lower bound on

Observe that the problem statement implies
`first < interval`,
since buses are known to arrive *throughout the entire hour*.
If `first >= interval`, then there would have been
a stop earlier than `first` at time `first-interval >= 0`,
which contradicts the definition of `first`.
Also observe that the second bus arrives at time `first+interval` and
since buses are known to stop at least twice we therefore have
`first + interval <= 59`.
This explains the bounds on `interval`.
The upper bound on `first` can be obtained by adding the
inequalities for `first`:

first < interval first <= 59 - interval ------------------------ + 2*first < 59from which we infer

first + (howoften-1)*interval <= 59 first + howoften *interval > 59These can be rewritten into

59-first - interval < (howoften-1) * interval <= 59-firstfrom which we infer

Here is procedure for writing a bus route in a graphically appealing way. It is useful during devopment and will help understand the problem better.

procedure GraphBusRoute(var f: text; b: BusRoute); var i: integer; begin with b do begin write(f, 1:first+1) ; i := first + interval ; while (i <= 59) do begin write(f, 1:interval) ; i := i + interval end { while } ; write(f, ' ':62-i+interval) ; writeln(f, '[', first:2, ',', interval:2, ',', howoften:2, ']') end { with } end { GraphBusRoute } ;

000000000011111111112222222222333333333344444444445555555555 012345678901234567890123456789012345678901234567890123456789 1 1 1 1 1 [ 0,13, 5] 1 1 1 1 1 [ 3,12, 5] 1 1 1 1 1 1 1 [ 5, 8, 7]

var s: integer; { s = # unaccounted arrivals = sum a[0..59] } a: array[0..59] of integer; { a[t] = # unaccounted arrivals at time t }Procedure

000000000011111111112222222222333333333344444444445555555555 012345678901234567890123456789012345678901234567890123456789 1 1 1 2 1 1 11 1 1 2 1 111 total = 17Compare this to the graphs of the bus routes shown above. The three rows of the bus routes nicely add up to the row of unaccounted arrival times in the input.

The input is read from file `inp` by procedure `ReadInput`:

procedure ReadInput; { read input into s and a } var i, j: integer; begin if Test then writeln('Reading input') ; readln(inp, s) ; if Test then writeln('Number of stops = ', s:1) ; for i:=0 to 59 do a[i] := 0 ; for i:=1 to s do begin read(inp, j) ; inc(a[j]) end { for i } ; readln(inp) ; if Test then begin GraphUnaccounted ; writeln end end { ReadInput } ;

The following function `Fits` determines whether a given
bus route `b` fits with the arrivals `a`,
that is, whether all stops of `b` occur in `a`:

function Fits(b: BusRoute): boolean; { check whether b fits with a, that is, all arrivals of b occur in a } { global: a } var i, j: integer; begin with b do begin i := first ; j := 60 ; { bounded linear search for earliest a[first + k*interval] = 0 } while i < j do if a[i] <> 0 then i := i+interval else j := i ; Fits := (i >= 60) end { with } end { Fits } ;

Candidate bus routes will be stored in global array `c`
and counted in integer `n`:

var n: integer; { # candidate bus routes } c: array[0..899] of BusRoute; { c[0..n-1] are candidate bus routes }Procedure

procedure FindBusRoutes; { post: c[0..n-1] are all bus routes fitting with a } { global: a, n, c } var f, i: integer; begin if Test then begin writeln('Finding candidate bus routes') ; WriteTimes end { if } ; n := 0 ; for f:=0 to 29 do begin if a[f] <> 0 then begin for i:=f+1 to 59-f do begin with c[n] do begin first := f ; interval := i ; howoften := 1 + (59 - f) div i end { with c[n] } ; if Fits(c[n]) then begin { another candidate } if Test then GraphBusRoute(c[n]) ; inc(n) end { if } end { for i } end { if } end { for f } ; if Test then writeln('Number of candidate bus routes = ', n:1) end { FindBusRoutes } ;Procedure

First of all, the check `if a[f] <> 0` was inserted
to cut off impossible bus routes as early as possible
(otherwise, for values of `f` with `a[f]=0`,
all possible values of `i` would be tried in vain).

Second, one might be tempted to optimize a little more.
For instance,
the computation of `howoften` could have been done only
if `Fits(c[n])` turned out successful.
Also, the function `Fits` could be adapted to exploit
the fact that `a[f] <> 0` was already tested,
by starting `Fits` with `i := first+interval` instead of
`i := first`.
The main reasons for not doing so are that these changes do not
speed up things considerably (try it),
and that they may complicate later uses or changes of `Fits`
(such as using `howoften` in `Fits`).

As an example of `FindBusRoutes` consider the
diagnostic output produced when reading
the example input from the problem statement
and finding the candidate bus routes.
The 17 stops of this input give rise to 42 candidate bus routes,
of which only eight stop more than twice.

Here is an overview of the number of candidate bus routes in each test:

test number of number of case arrivals candidates ---- -------- ---------- 0 17 42 1 12 24 2 44 237 3 43 375 4 31 136 5 40 201 6 70 365

type Schedule = array [0..16] of BusRoute;A schedule is written by the following procedure:

procedure WriteSchedule(var f: text; sc: Schedule; len: integer); var i: integer; begin for i:=0 to len-1 do with sc[i] do writeln(f, first:2, ' ', interval:2) ; if Test then writeln(f, '-----') end { WriteSchedule } ;Using the candidate bus routes we can do straighforward

var t: longint; { # schedules found so far } freq: array [1..17] of longint; { freq[p] = # schedules with p bus routes } p: integer; { # buses in partial schedule so far } m: integer; { # buses in best schedule so far } sched: Schedule; { sched[0..p-1] is schedule so far } best: Schedule; { best[0..m-1] is best schedule so far }Variables

Note that, according to the problem statement, the order of bus routes in a schedule is irrelevant (``the order of the bus routes does not matter'') and that a bus route may occur more than once (``buses from different routes may arrive at the same time''). To avoid duplication of work we will put bus routes in a schedule in the same order as they appear in the list of candidates and we allow multiple occurrences of the same bus route.

The state of the backtracking process is captured by the variables
`s`, `a`, `p`, and `sched`.
The bus routes `sched[0..p-1]` account for part of the arrival times,
and the unaccounted arrival times are represented by `a`
(and `s`).
Procedure `Use` extends the current partial schedule with
a given bus route and updates the state variables:

procedure Use(b: BusRoute); { global: s, a, p, sched } var i: integer; begin sched[p] := b ; inc(p) ; with b do begin i := first ; while (i <= 59) do begin dec(a[i]) ; i := i+interval end { while } ; s := s - howoften end { with } ; if Trace then begin WriteSchedule(output, sched, p) ; GraphUnaccounted(output) end { if } end { Use } ;Similarly, procedure

procedure RemoveLast; { global: s, a, p, sched } var i: integer; begin dec(p) ; with sched[p] do begin i := first ; while (i <= 59) do begin inc(a[i]) ; i := i+interval end { while } ; s := s + howoften end { with } end { Remove } ;The recursive procedure

procedure FindSchedules(k: integer); { global: s, a, n, c, p, sched, m, best, t, freq } { Find all schedules sched[0..r-1] with p <= r <= 17 such that bus routes sched[0..p-1] are as given, sched[p..r-1] accounts for a and uses only bus routes from c[k..n-1] } begin if s = 0 then { nothing left to account for } ScheduleFound else if p = 17 then { too many bus routes: ignore } else { try each candidate c[k..n-1] that fits } while k < n do begin if Fits(c[k]) then begin Use(c[k]) ; FindSchedules(k) ; RemoveLast end { if } ; inc(k) end { while } end { FindSchedules } ;

procedure ComputeAnswer; begin FindBusRoutes ; if Test then writeln('Finding schedules') ; for p:=1 to 16 do freq[p] := 0 ; t := 0 ; p := 0 ; m := 18 ; FindSchedules(0) ; if Test then begin writeln('Number of schedules = ', t:1) ; WriteFrequencies(out) end { if } end { ComputeAnswer } ;For the 17 arrival times in the problem statement,

This method is incorporated in Program 1. It is too slow for the second test input with 44 arrival times. Program 1 quickly finds a schedule with four bus routes (the minimum) but then continues to look for (non-existing) improvements. Apparently there are many (longer) schedules for this test case.

procedure FindBestSchedule(k: integer); { global: s, a, n, c, p, sched, m, best } { Find all schedules sched[0..r-1] with p <= r < m such that bus routes sched[0..p-1] are as given, sched[p..r-1] accounts for a and uses only bus routes from c[k..n-1] } { pre: p < m } begin if s = 0 then { nothing left to account for } ScheduleFound else { try all candidates c[k..n-1] that fit } while (k < n) and (p+1 <> m) do begin if Fits(c[k]) then begin Use(c[k]) ; FindBestSchedule(k) ; RemoveLast end { if } ; inc(k) end { while } end { FindBestSchedule } ;Note that we have not written

else if p+1 = m then { too many bus routes: ignore } else { try all candidates c[k..n-1] that fit } while k < n do beginbecause

This idea is incorporated in Program 2. This program indeed only tries one schedule for input-1.txt and input-2.txt. However, on the other input files it still takes (too) long.

Program 2 might benefit from another order for the candidates, because if it finds a good schedule early on, then the built-in cut-off mechanism is more efficient. Since we are interested in schedules with the fewest bus routes, each bus route in the schedule should account for as many arrivals as possible. Therefore, we might first try bus routes that make many stops.

Program 3 sorts the candidate bus routes
on `howoften` as they are found.
The diagnostic output for the input
in the problem statement shows the sorted
list of 42 candidate bus routes.
Sorting turns out to make only a small difference.
Program 3 still takes too long for input-3.txt.

procedure FindBestSchedule(k: integer); { global: s, a, n, c, p, sched, m, best } { Find all schedules sched[0..r-1] with p <= r < m such that bus routes sched[0..p-1] are as given, sched[p..r-1] accounts for a and uses only bus routes from c[k..n-1] } { pre: p < m } begin if s = 0 then { nothing left to account for } ScheduleFound else begin { try all candidates c[k..n-1] that fit } while (k < n) {c}and (c[k].howoften > s) do inc(k) ; while (k < n) {c}and (p + 1 + (s-1) div c[k].howoften < m) do begin if Fits(c[k]) then begin Use(c[k]) ; FindBestSchedule(k) ; RemoveLast end { if } ; inc(k) end { while } end { else } end { FindBestSchedule } ;The first while-loop skips candidate bus route that make too many stops for the remaining unaccounted arrival times. The second while-loop breaks off as soon as the remaining candidate bus routes make so few stops that improvement is no longer possible. Note that I have written

Observe that this technique only works if the list of candidate bus routes is
sorted on `howoften`.
In that case a *lower bound* can be given on the number of bus routes
needed to complete the schedule.
The technique is sometimes called *branch-and-bound*.
It is used in Program 4,
which is so effective that all six input files are done in an instant.
For all of them only one or two (complete) schedules are considered.

Write an auxiliary program that generates all bus routes, sorts them on how often they stop, and then puts this data in a file `routes.dat'. Investigate whether using this file, instead of generating them inside the main program, can speed up the generation of all candidates.

Tom Verhoeff

Eindhoven University of Technology