The Roster of the Night Watch

The wall of bitwick needs one watcher a night for the coming season, and the captain's rules for filling the roster are pinned beside the board.

Write watchRoster(nights, guards, feuds), which returns the season's roster.

The data

• nights — an integer, 0 or more. The nights are numbered 1 through nights.
• guards — a list of records, each with:
• name: a string of lowercase letters; all names are distinct,
• rest: an integer 0 or more, the nights of rest this guard demands after standing watch,
• max: an integer 0 or more, the most nights this guard will stand all season,
• busy: a list of night numbers this guard cannot stand (possibly empty, in any order).
• feuds — a list of two-element lists of names: two guards who will not stand on consecutive nights. Feuds are mutual, every name in them appears in guards, and a name may appear in several pairs.

Filling the roster

Nights are settled one at a time, from night 1 up to night nights. For night d, a guard is *eligible* when all four of these hold:

• d is not in their busy list;
• they have been given strictly fewer than max nights so far (that is, among nights 1 through d-1);
• they have been given no night so far, or else d - L > rest, where L is the latest night they were given;
• d is 1, or night d-1 was left unstood, or the guard who stood night d-1 is not in a feud pair with them.

Among the eligible guards, night d goes to the one who wins on the first rule that separates them:

1. fewest nights given so far; 2. longest since last on watch — a guard given no night so far beats every guard who has been given one, and between two who have been given nights, the one whose latest night L is smaller wins; 3. smallest name, compared character by character.

If no guard is eligible, night d is left unstood and no guard's record changes.

The return value

A list of length nights. The entry at position d-1 is the name of the guard who stood night d, or null (None in Python) if night d was left unstood.