The Bridle-Line of the Ombrel Salt Road

Commission of the Drovers' Guild of Ombrel. At first light the salt caravan leaves Bitwick for the Ombrel Flats. Its pack-beasts cross the Flats in single file, and the Guild has written down which beast may walk where. Set the line before dawn.

Write bridleOrder(beasts, rules).

• beasts is a list of distinct names. Each name is a non-empty string with no spaces. The list may be empty, and it holds at most 8 names.
• rules is a list of strings. Each rule is exactly three words separated by single spaces, in one of these four forms:

| Rule | Meaning | |---|---| | A before B | A's place is strictly earlier in the line than B's, at any distance. | | A beside B | The places of A and B differ by exactly 1, in either order. | | A apart B | The places of A and B do not differ by exactly 1. | | A at k | A stands at place k. k is a whole number written in decimal, with 1 <= k <= len(beasts). |

Places are numbered from 1 at the front of the line. Every name in a rule appears in beasts. In the before, beside and apart forms, A and B are always different beasts. rules may be empty.

A line is a list holding every beast exactly once, front first. A line is valid when every rule holds.

Return the lexicographically smallest valid line. To compare two lines, find the first place where they differ: the line with the smaller name at that place is smaller. Names are compared by ordinary string comparison, character by character on character codes. So "Ash" < "Ashk" < "Bede", and every uppercase letter sorts before every lowercase letter.

If no valid line exists, return an empty list. If beasts is empty, return an empty list.