[m-dev.] ICFP Contest: Written parse_trace.m and dump.m

Ralph Becket rafe at cs.mu.OZ.AU
Mon Jun 30 00:21:17 AEST 2003

Peter Moulder, Sunday, 29 June 2003:
> Using Ralph's car.m and fix.m to interpret commands (brake etc.),
> I've written some code to read in Een.trc and produce something in the
> format of Een.dump.  However, currently the two dumps don't match.
> I haven't yet found the cause of the discrepancy.

Is the discrepancy large?

On reflection, I think it was a mistake to rename div to / and mul to *,
since that may hide some bugs.  However, using a tagged representation
should ensure that fixes and ints are not confused.

One obvious bug in fix.m is that section 2 of the spec. points out that
for div and mul, "32 bits is not enough for implementing these
operations."  The quickest solution is probably to use the integer
library rather than just int, although performance wouldn't be great
(integer.m uses base 2^14).

I'm pretty shattered, so I'll knock off until the morning.  Here's my
plan for the rest of the solution:

(1) Optimise the route by pruning unnecessary vertices - that is, if the
route specifies ABC and there is no obstacle on the direct route from A
to C, then we should simplify ABC to just AC.

(2) Handle the corner at B while taking the route ABC by turning while
- The sharpest, slowest turn on the route ABC is obtained by coming to a
  halt at B, turning to face C, then accelerating away.
- The widest, fastest turn is obtained by not braking at all and turning
  constantly until the orientation of the car changes from AB to BC
  (then we have to identify the starting point for the turn on AB such
  that it finishes on BC. (*))
- The slowest, sharpest turn can be "morphed" into wider, faster turns
  by braking less.
So, the corner optimiser should start with the fastest turn and then
try, say, the four sharper turns leading up to the slowest turn, picking
the fastest one that works.

(*) We should be careful that we are not travelling too fast on exiting
a turn, in the sense that we cannot then stop before hitting something.

[Note that we can combine turning with accelaration in a single action.]

Hmm.  The above description sounds fairly easy to implement.  I'll put
it off until tomorrow morning, unless there are any keen insomniacs left
out there!

-- Ralph
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au

More information about the developers mailing list