The Let's Play Archive

EXAPUNKS

by Carbon dioxide

Part 51: CrystalAir International

Part 51 - CrystalAir International


=== Trash World Inbox ===

Quackles posted:

Here's the best solution I have.
code:
	;SETUP
LINK 800
GRAB 200
MARK NEXTFILE
COPY F X
REPL FILEBOT
COPY F M
VOID M 		;NOW WAIT FOR ACK
TEST EOF
FJMP NEXTFILE

	;HALTS TRYING TO HOLD TWO FILES
While the code is in one EXA, the EXA becomes three during running the code. This first EXA, the file manager, simply grabs the list of files and REPLs as needed to start recovering the next file in the set, passing in the name and address of the file.
code:
MARK FILEBOT
	;MAKES FILE, SENDS PROBES OUT TO COLLECT DATA
MAKE
COPY X F
COPY M F
MODE

MARK PROBE801	;GO TO DRIVE 1, COPY EVERYTHING THERE
COPY 801 T
REPL EXPLORER1
NOOP
NOOP
TEST MRD
FJMP PROBE801
VOID M

MARK COPY801
COPY M T
FJMP START802
COPY T F
@REP 5
COPY M F
@END
JUMP COPY801
The second EXA sits in the drive controller, holding the file that will be the 'clean' copy of the episode (we also keep the ID of the file to t. It sends out an 'explorer' EXA (using the routine EXPLORER1) to try and gain entry to the drive. If the link attempt fails (killing the explorer EXA), it will retry as often as needed.

Once the drive controller EXA is assured of the connection, it copies the contents of the file from the first drive, FAILs and all, to its own file. The value 0 never appears in the video files, so the drive controller EXA can interpret a 0 as a signal to cut the connection. However, we can be clever about this - every file's length is a multiple of 6 values, so we only need to check for 0 on the first value received out of every six! This speeds up the copying procedure.

(I'll detail the EXPLORER1 routine later, but it basically copies over the entire file in a speed-optimized way, using paralellism with REPL.)
code:
MARK START802	;GO TO DRIVE 2, BE JUDICIOUS
SEEK -9999
COPY F X
SEEK 1

MARK PROBE802
COPY 802 T
REPL EXPLORER2
NOOP
NOOP
TEST MRD
FJMP PROBE802
VOID M

COPY 0 X
MARK COPY802
TEST F > -9999
FJMP WRITE802
ADDI X 1 X
TEST EOF
FJMP COPY802
JUMP START803

MARK WRITE802
COPY X M
SEEK -1
COPY M F
COPY 0 X
TEST EOF
FJMP COPY802
The drive controller EXA now has to interpolate the values from the other two drives. However, for efficiency, we don't copy the entire file again. Instead, the drive controller EXA sends over an EXA using the EXPLORER2 routine.

The EXPLORER2 EXA will wait for instructions, then move forward through the file, copying over the value that's in a specific location.

To do its part, the drive controller EXA scans the existing 'clean' copy of the file for FAIL values (TEST F > -9999). It keeps track of the number of value in the file since the last FAIL value in X.

Once the drive controller finds a FAIL, it sends the value of X to the EXPLORER2 EXA. That EXA will move forward that many places in the file and report what it reads over global M. Then, the drive controller can patch the FAIL in its copy of the file with the received value.
code:
MARK START803	;ALSO BE JUDICIOUS WITH DRIVE 3
COPY 9999 M	;KILL 802 EXA
SEEK -9999
COPY F X
SEEK 1

MARK PROBE803
COPY 803 T
REPL EXPLORER2
NOOP
NOOP
TEST MRD
FJMP PROBE803
VOID M

COPY 0 X
MARK COPY803
TEST F > -9999
FJMP WRITE803
ADDI X 1 X
TEST EOF
FJMP COPY803
JUMP FINISH

MARK WRITE803
COPY X M
SEEK -1
COPY 0 X
COPY M F
TEST EOF
FJMP COPY803
After sending a 9999 over M to make the explorer EXA in the second drive halt (it will try to read past the end of the file), we repeat this process with the third drive. The third drive's explorer EXA also uses the EXPLORER2 read routine (but takes less time overall, since there are (hopefully) fewer FAIL values left in the drive controller's file).
code:
MARK FINISH
COPY 9999 M
MODE 
COPY 1 M 	;NOTIFY CONTROLLER FILE IS DONE
LINK -1
SEEK -9999
VOID F

	;HALTS TRYING TO LINK TO AN INVALID ADDRESS
With the completed file in our possession, the drive controller EXA halts the third explorer, notifies the file manager EXA that the file is fully recovered, clears the file address from where we were storing it at the start of the file, and delivers the file to our host.
code:
MARK EXPLORER1
LINK T
GRAB X
COPY 0 M	;WE MADE IT ACROSS!
MARK EXPLCOPY1
@REP 3
COPY F X
COPY F T
REPL EXPLSEND1	;SENDS BOTH VALUES
@END
TEST EOF
FJMP EXPLCOPY1
REPL NULL
COPY 0 M

	;HALTS TRYING TO LINK TO AN INVALID ADDRESS

MARK EXPLORER2
LINK T
GRAB X
COPY 0 M	;WE MADE IT ACROSS!
MARK EXPLCOPY2
SEEK M		;WHERE TO READ NEXT?
COPY F M
JUMP EXPLCOPY2

	;HALTS TRYING TO READ FROM EOF

MARK EXPLSEND1 	;SEND VALUES AND QUIT
COPY X M
COPY T M

MARK NULL
	;DUMMY REPL - USED TO WAIT FOR OTHER REPL'D EXAS TO CLEAR
This is the routines used by the explorer EXAs. The first routine, EXPLORER1 (and EXPLSEND1) copies the entire data of the file over M. However, sending a value over M has a 1-cycle startup delay on the part of the sender (but not the receiver). So, instead, the explorer EXA reads two values into X and T, then REPLs to EXPLSEND1.

While it reads the next two values, EXPLSEND1 sends the first two over M, then quits. There is only enough space for one REPLd EXA in eacha drive, so the next batch of values will wait while the first batch of values is sent.

Once we reach the end of the file, we use REPL NULL to wait for the last file sending EXA to clear. There are no instructions after MARK NULL, so the dummy EXA does nothing, while the explorer sends an 0, indicating end-of-file.


The second explorer routine, EXPLORER2, is much simpler. It reads a value over M telling it how many places forward to move in the file. It then sends back the value it finds there. This loops forever until it runs off the end of the file, which the drive controller EXA does deliberately by sending it a 9999 when it's time to finish with that drive.

4886/124/35. I do think it's possible to get a better result, but it'd involve a lot of paralellism, using REPL and local M to pipeline steps of the data processing.
You could probably find some low-hanging fruit with an approach that reads the entire file from each drive. The first read simply writes it to the file directly. The second read could read in and REPL off to test if a value was FAIL, and then write to the file... anyway, I'm happy with what I've achieved.
A nice speed improvement. Note the EXA has to start in LOCAL mode.

Quackles explains it well. The main speed-ups are in only sending values that failed before using the SEEK M trick, and also using a REPL to actually send data over M for the first file.

You need to send one EXA per drive per file across the broken links and I didn't want to deal with that which is why I did one drive at a time, but handling the files serially definitely makes the code easier to optimize.


=== CrystalAir International- Ticketing System ===



And just like that, we're at the last of our currently unlocked tasks.


OST: Code and Registers

The assignment:

- Each host in the network corresponds to a country and contains a list of tickets for flights (file 200) departing airports in that country, bound for airports either also in that country or in a connected country. Each ticket has the following values: ticket ID, departure airport, departure time, arrival airport, and arrival time.
- Book the sequence of flights in deadlock's itinerary (file 300) by deleting each ticket from its file in the network and adding the ticket ID to file 301, choosing the first valid flight that departs after the preceding flight arrives.
- Note that deadlock's itinerary will always begin in the USA, and that flight times may be compared with TEST.

Looks like the USA is always the host we're directly connecting to, and that the network layout is the same for all the tests. I also think the tickets in each country's file are ordered by departure time.

In this first test, our itinerary is DFW -> JFK -> CDG -> IBZ.

Also there's a little thing that confused me in this test case. It says "Remove the tickets from the files (0/2)" at the goals in the bottom left. There's 3 tickets to find, it actually says 2 because there's only two files to remove tickets from, since DFW and JFK are both in the US.

Well, to get started I'll find the first flight from DFW to JFK in the USA's file.

I wrote two EXAs for that:
code:
;XA

MARK START
GRAB 300

COPY F M

COPY F X

MARK SENDAGAIN
COPY X M
COPY M T
FJMP SENDAGAIN

SEEK -9999
VOID F
DROP
GRAB 301
COPY T F
DROP
JUMP START
XA stays at home and handles both files 300 and 301. It sends the departure airport over M, then it sends the arrival departure over M as long as it keeps getting zeroes back. Once it doesn't get a zero, it deletes the departure airport from file 300 (so the next pair of airports become departure and arrival), drops the file and writes the value it just got from M into file 301. Then it repeats. XB just has to make sure it sends the ticket number and this will work.

XB looks like this.
code:
;XB

LINK 800
GRAB 200
COPY M X
SEEK 1

MARK TRYNEXT
TEST X = F
TJMP POSSIBLYFOUND
SEEK 4
JUMP TRYNEXT

MARK POSSIBLYFOUND
SEEK 1
TEST M = F
TJMP FOUND
COPY 0 M
SEEK 2
JUMP TRYNEXT

MARK FOUND
COPY F X
SEEK -5
COPY F M
SEEK -1
@REP 5
VOID F
@END
.
It goes into the USA host, puts the departure airport in X, then starts looking for flights leaving from there. If it finds one, it requests the arrival airport over M and checks if that's a match too. If not, it sends a zero back and keeps looking. Otherwise, it SEEKs back to the ticket number, sends that on M, and removes all 5 values for the ticket from the file.

The next part is harder. The next airport can be in the same country or any adjacent country (I sure hope it can't be two countries over, that'd make the puzzle much harder). And we have to check the departure time as well. I wrote the last flight's arrival time to XB's X register for now but that won't fit.

Let's ignore the departure time for now and first build the search in adjacent countries.



After deleting the first ticket, XB now makes REPLs going in all four cardinal directions, and the original one stays where it is. They do a KILL, then GRAB the file. Then they all repeat the search code. This works efficiently because only one will have the file with the current departure airport. It's the only one that will ever ask for the arrival airport over M. All others will either reach EOF and die, or they'll stay busy until the next round, which is why I needed that KILL. It'll clear up leftovers from the previous round.

It's possible to shift things here a bit - I don't need the DROP, KILL and GRAB for the EXA that stays in the current country. But this kept the code simpler.

So, this code gets me the earliest known flight for each route. It still ignores departure times.

Also, the EXAs get stuck at the end looking for a final connection that doesn't exist. But let's fix the departure times issue first.

What I need to do is compare the arrival time of the last round with the departure time of this one. That's not going to fit in XB, so I'll have XA handle it as well.
code:
;XA

GRAB 300
SEEK 9999
COPY 0 F
SEEK -9999

MARK START

COPY F M
COPY F X
SEEK 9999

MARK SENDAGAIN
COPY X M
COPY M T
FJMP SENDAGAIN
SEEK -1
COPY F M
COPY M T
FJMP SENDAGAIN
SEEK -1
COPY T F

SEEK -9999
VOID F
DROP
GRAB 301
SEEK 9999
COPY M F
DROP
GRAB 300

JUMP START
XA now starts by writing a zero at the end of file 300, as a placeholder. If XA makes it past the first FJMP SENDAGAIN (after XB sends a success message), XA will send this value over M and wait for another message. If this is non-zero, the value is written over the placeholder. That value will actually be the new flight's departure time. So, every XB round starts with it getting the departure airport in X, then repeatedly receiving the arrival airport over M. When this combination is found, it asks for the departure time. If it doesn't match, it starts asking for the departure airport again.

XB now sends the ticket number as a third M message, which XA writes to file 301. I had to put in a SEEK 9999 in there because my code kept overwriting the first number. :sweatdrop:

XB needed significant changes to make this work.
code:
;XB

LINK 800
COPY M X

MARK SEARCH
KILL
GRAB 200
SEEK 1

MARK TRYNEXT
TEST X = F
TJMP POSSIBLYFOUND
SEEK 4
JUMP TRYNEXT

MARK POSSIBLYFOUND
SEEK 1
TEST M = F
TJMP FOUNDFLIGHT
COPY 0 M
SEEK 2
JUMP TRYNEXT

MARK FOUNDFLIGHT
COPY 1 M
SEEK -2
TEST F < M
FJMP FOUND
COPY 0 M
SEEK 3
JUMP TRYNEXT

MARK FOUND
SEEK 1
COPY F M
SEEK -5
COPY F M
SEEK -1
@REP 5
VOID F
@END
DROP

COPY M X

COPY 4 T
MARK SPREADOUT
REPL MOVE
SUBI T 1 T
TJMP SPREADOUT
JUMP SEARCH

MARK MOVE
ADDI 799 T T
LINK T
JUMP SEARCH
Basically, whenever a matching flight is found (FOUNDFLIGHT) it sends a 1 to XA as the first success message, then compares the departure time with the previous arrival time from XA. I needed to switch the logic here, because in the first round, XA will send a 0, and any test of 0 against a keyword (which the dates are) always return false. So, if the value from XA is zero, or if departure time in the file is NOT smaller than the previous arrival time, FJMP FOUND is executed. There's an edge case if the previous arrival time exactly matches this flight's departure time but I'm gonna assume the game doesn't care.

The SEEKs changed a bit to handle the extra jumping back and forth in the file.


This code writes the right result, but XA will tell XB to go find a flight from the final destination to... the arrival time, which makes no sense. XB can't find that and XA will wait for a response forever. Let's go fix that.

XA just needs some code at the bottom to check if only the final destination and the arrival time are left.
code:
SEEK 2
TEST EOF
SEEK -9999
FJMP START

COPY 0 M
While XB can test for this zero value and then just stop.
code:
COPY M X
TEST X = 0
TJMP END
Sadly it's not straightforward to use the divide by zero trick here, because dividing by a word also kills the EXA.




That was a quite nice puzzle, not nearly as hard to figure out as some of the other post-game ones. 345/83/25. Top percentiles are 136, 58 and 8.

For the speed, well, I do a lot of waiting on M. I'm sure that could be more efficient. Looking at the graphs, there's lots of people who somehow needed the full 150 lines of code to solve this. That high peak in the activity is probably what happens if you send an EXA to each country every round. The top percentile of 8 is interesting, though. You could send an EXA to each country once and have it start searching when getting a message on M, but there's 12 countries so that would still be an activity of 12. I think it involves something like only sending EXAs to neighbouring nodes when needed, but then actually keeping them there. So nodes that are completely in the wrong direction will never get visited and no link will be traversed twice.

Either that or there are actually some countries deadlock never wants to go to.


The next task is finally for Moss again. And as usual, Ember has some things to say.

Well, this is something.
I can see an open network that's... I can't even tell how big.
Imagine all the computers in the world were hooked up to each other, and you would start to get an idea of the size.
No way to know just how big until we explore, though.



You have no idea how much I missed this part. Here's the first vote!


A little bit later in the same conversation, Ember has another question.

Why, do you think it could be dangerous?



The second vote.