Part 45: Motor Vehicle Administration

Part 45 - Motor Vehicle Administration

=== Trash World Inbox ===

Quackles posted an improvement for Bloodlust Online.
Nice. I don't really have anything to add to this explanation, but I tried to take your code and optimize it further.

First of all, moving all the M reads to the latest possible moment brings the result down to 138 cycles. So, start XB with LINK 800; COPY 800 T; COPY M X in that order, giving XA time to prepare. And before each search loop, first do the GRAB/SEEK and only then COPY from M. It's a bit less waiting overall.

Secondly I noticed one test in particular being slow which means it's time for cheese.

Reversing the searches is not that hard: Just replace SEEK -9999; SEEK 1 with SEEK 9999; SEEK -2 and the SEEK 2 inside the loop with a SEEK -4.

You can do this with all searches except the first one, because you'll never get the EOF condition that makes the EXAs in the wrong host stop. If you do this, the timing changes for every test, and it's not obvious how. For instance, if you reverse SEARCHLOOP2 only, the slowest test becomes test case #99. For this solution you need a 5th KILL because another test case is so fast that it reaches the hideout before the TALISMAN seeker is dead. 130 cycles.

If you reverse all three of SEARCHLOOP 4, 5 and 6 together, the fastest test case is #76, which is equally fast as #99 was before, but because the speed-up happens after the KILLs the 5th KILL isn't necessary and it takes only 129 cycles. Reversing loops 4, 5, 6 as well as 2 makes some test much slower so that combination is no good.

I can also reverse the searching of the hosts, by starting from 805 and and counting down. Doing this for second search slows things down, but doing it for the first saves two cycles. However, this requires the extra KILL again, so we're down to 128.

The top percentile is 117. Let's try the last trick up my sleeve: more loop unrolling. You can put @REPs after each MARK SEARCHLOOP, until just before the JUMP. The effectiveness of this is limited by how many loops the slowest test needs. It's mostly trial and error for how many repetitions you need.
But it gets us to 117/136/21, exactly the top percentile for cycles.


=== Motor Vehicle Administration ===




Looks like NthDimension needs some help with scheduling their driving test.



OST: Behind the Scenes

The assignment:
- There is a list of appointments (file 200) in storage that contains an appointment for NthDimension (file 300) to take his driving test. Remove the appointment from the list of appointments, change the date to today's date (#DATE register), and insert it between today's appointments and tomorrow's appointments.
- To gain access to the storage host you will need to unlock it by writing the lowest ticket number to the #NEXT register. Each EXA in public is holding a ticket; terminate them all to find the ticket of the next EXA to be served.
- Note that writing an incorrect ticket number to the #NEXT register will fail the leave no trace requirement.

Well, NthDimension's real name is William Kapoor.

First of all, see that test track? Kinda reminds me of the baseball court in an earlier assignment.



Going around it, including into that rightmost host, and making it back home safely, nets you the Steam achievement DRIVING_TEST: Keep a safe distance as you reverse into the space. Neat.

For the actual assignment, I first need to get access to the storage host. From checking the first 5 test cases, it looks like the file IDs of the ticket numbers are always consecutive numbers in the 200s range, and that the ticket number is just the file number with a letter added. If that's the case, this is easy. I just have to find the lowest file id.
KILL the 5 waiting EXAs (their number appears to be constant), make REPLs to find the lowest ticket number. As soon as one finds it, it KILLs the original EXA so it stops trying to look for the rest, then sends its ticket number to #NEXT to open access to the STORAGE host.

To move NthDimension forward in the schedule file, I do need to find his entry first. I could get the date from the register and his name from file 200, but his entry is the only one where I'm certain the type of appointment is TEST, which I'll need to copy.



The new link that opens is 800, so XA goes there, grabs file 200, and then looks for NthDimension's name. I made XB to make the data juggling a bit easier. It starts by sending NthDimension's name to XA. When XA finds it, the file pointer is one step beyond the name on the TEST keyword. It sends TEST to XB for later use, then deletes NthDimension's original entry.

Next, I need to find the place in the file to insert his entry. In some tests, there are schedule items for today. I don't think there are ever items that are in the past. So I just need to find the first item that doesn't match today's date and insert the new entry before that.

The main issue is that file insertion is hard, because writing to an existing position in a file overwrites it instead of inserts. I need to shuffle everything forward.

My first thought was something along this direction:
- Read the date of the next scheduled item (the one that will be overwritten) to X.
- Write today's date to that position.
- Read the name at the next position to T.
- Write the date from X there.
- Read the next value to X.
- Write T to that position.
- Repeat the swaps with X and T until the whole file is updated.

- Then do this two more times, for inserting the name and the schedule type.

The three loops would make this slow, but more importantly it won't work because at the end of the file it will try to read an empty spot before writing, causing the EXA to crash. This could be resolved with an EOF check but in half the cases, T holds the active value to swap so I can't overwrite that with a TEST without making the code much more complex.

Because this would be slow anyway, I think it's better to use the other EXA for juggling data.

It took some fiddling but I came up with this solution:

After cleaning up NthDimension's original entry, XA does a simple loop to find the first instance where the date doesn't match the current date.

Then it first loads the TEST keyword in T, because after this, XB can focus completely on data juggling.

XA sends the date of the other appointment over M, and writes the new date from #DATE. It sends the name of the other appointment over M, then writes NthDimension's name (which is still in X, conveniently). Finally, it sends the other appointment's schedule type over M, and writes the TEST keyword into the file.

Then, XA enters an insert loop in which the value in the file is buffered in X, the previous value is read from M and written to the file, and then X is sent over M. This continues until EOF is reached.

XB stores values in X, T, and F. That fits perfectly: dates in X, names in T and schedule types in F. Then it sends them back in the right order. Some garbage is left in file 300 but since that's in the home host, it doesn't matter.

Once XA reaches EOF it reads the final values from XB and just sends 0 whenever XB asks for a new value. That means a 0 ends up in XB's T, so it leaves the loop and stops automatically.

I did try to make this code faster by not using the X buffer in XA. It might work, but it'd mean juggling a 4th value in XB, or handling only two values at a time. This adds complexity because I'd somehow need to switch from the initial handling of 3 values (for copying NthDimension's entry) to two. It also means you don't know where in the loop the EXA is when it's done copying (because the file has groups of 3 entries). The additional logic makes the code much harder to get right so I decided to stick to this solution.

This code runs at 549/76/8, with top percentiles of 241, 53 and 7.

I feel I spent enough time on this, so I'll leave optimizations to you.



Next time, I help out Ghast.


My body was turning into junk
Strange networks I made EXAs spelunk
I heard my system's voice
EMBER gave me no choice
Uploaded, I'm now an EXAPUNK.