=== Trash World Inbox ===
Last time, I built the wardialer. My top scores were 22549/49/1.
Quackles submitted three different solutions to the puzzle with a whole lot of explanation. Nice.
Full disclosure, one of the reasons for featuring thread submissions in my updates is so everyone reading this elsewhere (LP Beach, SA, or the archive) can see them. But of course I do have to make a decision on what to actually show to keep it interesting for all readers.
I think I need to summarize Quackles' submissions a bit to make this work. If you want to see them in full, they're posted in the SA thread.
The first solution has 3 EXAs. One sends the static digits of the phone number, the other handles placeholder digits. The way it works is that the first one asks the second one for a digit whenever it sees the placeholder letter, and the second just keeps the current value of all placeholders in the X register, incrementing it by 1 each round, and uses SWIZ to send the separate digits to the first EXA, whenever the first EXA prompts it. It is told when a phone number works and then saves the placeholder digits to a file.
The third EXA just sits in the home host waiting for the result. At the end, the first EXA sends all the static digits to the third EXA, and asks the second EXA whenever a placeholder comes up.
This solution runs at 83681/97/2.
Quackles's second solution runs at 61718/141/2. It still uses the placeholders-in-X with SWIZ trick. The main difference is that the first and second EXAs now both have the full phone number, so the second EXA doesn't need to be prompted to send a placeholder. They can just make sure that the dialing loop is perfectly synced up and send their own digits when their turn comes. For sending the digits to the third EXA, something similar to the first solution was used. I'm thinking it might be very slightly faster to have the second EXA handle that entirely but I didn't check.
The main issue with this solution is that there are lots of wasted cycles, because for every digit, both EXAs need to test if it's for them or not. Quackles solved that in solution number 3.
I'll post that in full. Note that Quackles is calling the main dialing loop the "kernel".
Oh my.Quackles wrote:After the partial success of my last solution, I was thinking about how I had minimized the number of cycles needed for each step of the 'kernel' loop that actually emitted the digits. It was clear that it wasn't possible to optimize the loop further as it was, especially with the conditional logic involved in the loop (TEST F > -1, JUMP, TEST EOF, etc.)
So a crazy idea came through my head: what if the loop where the EXA rattled off the digits didn't have any conditional logic at all?
It turns out this is possible, though it took me several days to write. The basic idea works like this: we transform the list of 11 digits into a series of roughly 22 values (11 pairs of two values each). Each pair of values is an offset to seek by, and a digit to display; the EXA that runs the central loop can simply do SEEK F / COPY F #DIAL 11 times (!) to send all the digits to the modem.
The reason we do this is for a simple reason: not only do we get a fast dialing procedure, we can make sure all the placeholder digits are the last three digits in the file. Since the dialing EXA deliberately reads the digits out of order, when the time comes to increment the placeholder digits, we can just start from the end of the file, and work backwards if more than one placeholder needs to be updated at once.
The code below works in two stages. In the first stage, we do the setup. This is most of the lines of code but very little of the total cycles. In the second stage, we dial and record the numbers. This is simple, but slower.
Setup: Basic File Structure
There are three EXAs involved in setup: the parser-recorder, which parses the provided phone number; the offset calculator, which is responsible for 'wiring up' the connections to the placeholders at the end of the file, and the main EXA, which does a bunch of the setup math and will also do the dialing. All three start in the main host.
Critically, the parser-recorder and main EXAs start in local mode, while the offset calculator starts in global mode. This will be critical when routing messages between EXAs.The first part of the parser-recorder's code has it parse the file with the phone number. Any digit gets sent to the main EXA, while any placeholder gets a '1' sent to the offset calculator, so that the calculator can count the placeholders. Once the end of the file is reached, the parser-recorder sends a '0' to the offset calculator to let it know to take over.Code: Select all
;PARSER-RECORDER EXA, SETUP PHASE 1 GRAB 300 MARK SAYNUMLOOP COPY F X TEST X > -1 ;DIGIT = T, PLACEHOLDER = F TJMP SEND MODE ;GLOBAL COPY 1 X MARK SEND COPY X M ;DIGIT TO MAIN EXA, OR 1 TO OFFSET CALCULATOR TJMP SEND2 MODE ;LOCAL MARK SEND2 TEST EOF FJMP SAYNUMLOOP MODE ;GLOBAL - TO OFFSET CALCULATOR COPY 0 M ;TELL CALCULATOR TO GOThe offset calculator first counts the placeholders as cued by the parser-recorder. Once it receives a 0, it switches modes and starts sending 0s to the main EXA directly. It always sends one more 0 than there are placeholders. The main EXA is recording all the digits it receives, so this ensures it always receives a total of 12 digits, for a total of 25 values in the file (12 pairs of numbers plus an extra offset after the placeholders).Code: Select all
;OFFSET CALCULATOR EXA, SETUP PHASE 1 ;COUNT PLACEHOLDERS MARK PHCOUNT COPY M T ADDI X T X TJMP PHCOUNT ;X IS NOW 1-3 ;THIS SETS UP THE PLACEHOLDERS AT THE END OF THE FILE MODE ;LOCAL ADDI X 1 T MARK PADFILE COPY 0 M SUBI T 1 T TJMP PADFILEThe main EXA hasn't done much yet. Once it finishes receiving the 12 digits from the other two EXAs, it will have 8-10 pairs with digit values, 1-3 pairs which will hold placeholders, and an extra pair between them to serve as a buffer (if the buffer isn't there, it causes a nasty edge case when an offset leading to a placeholder is a 0).Code: Select all
;MAIN EXA, SETUP PHASE 1 ;COPY NON-PLACEHOLDER VALUES INTO FILE, WITH GENERIC OFFSETS ;ALSO COPY IN BLANKS FOR PLACEHOLDERS/PADDING MAKE COPY 0 F COPY 12 T MARK SETUP1 COPY M F COPY 0 F SUBI T 1 T TJMP SETUP1
The next step is to calculate the offsets so that the digits are dialed in the correct order. We pick up again with the parser-recorder.
Setup: Offset CalculationThe parser-recorder goes back and runs through the phone number pattern file again. However, this time, it's looking for the position (the offset) of each placeholder in the file. These position(s) are transmitted over global M to the offset calculator.Code: Select all
;PARSER-RECORDER EXA, SETUP PHASE 2 SEEK -9999 COPY 0 X MARK PHOFFSETLOOP TEST F > -1 FJMP PHFOUND ADDI X 1 X JUMP PHOFFLOOPEND MARK PHFOUND COPY X M ;SEND PLACEHOLDER OFFSETS TO OFFSET CALCULATOR MARK PHOFFLOOPEND TEST EOF FJMP PHOFFSETLOOPThe offset calculator takes these positions and expands them into a pair of instructions that are sent to the main EXA. Specifically, it tells the main EXA which offset in the file to write to, and the value to write to it. When the SEEK F loop hits that offset later, it will jump ahead the correct number of places, to the placeholder digit to send to #DIAL. (The correct number of places is (8 - [position of placeholder, counting from 0] + [number of which nth placeholder this is, starting from 1]) x 2.)Code: Select all
;OFFSET CALCULATOR EXA, SETUP PHASE 2 ;OK! FILE IS ALL FIGURED OUT. NOW WE JUST NEED TO SET THE OFFSETS. SUBI 4 X X ;PH COUNT OF 1, 2, 3 => 3, 2, 1 (NEEDED FOR CALCULATIONS) MARK PHLOOP MODE ;GLOBAL - LISTENING TO PARSER-RECORDER COPY M T MODE ;LOCAL - SENDING TO MAIN EXA MULI T 2 M ;SEEK TO TARGET OFFSET IN FILE ;OFFSET FORMULA IS (8-T+X)*2 SUBI 8 T T ADDI T X T MULI T 2 M ;THE VALUE TO WRITE TO THAT OFFSET - MAIN EXA DOES THE REST ADDI X 1 X TEST X < 4 COPY T M ;1 = STILL CALCULATING PLACEHOLDER OFFSETS TJMP PHLOOP
The offset calculator also keeps track of the number of placeholders left, and cues the main EXA when it's time to move on. Once that happens, it will halt.The main EXA has the big job. As cued by the offset calculator, it jumps to the specific place in the file and writes the offset that it will use to jump to the placeholder digit later. However, it has to write a corresponding 'jump back' offset after the digit so the dialing loop returns to the correct place in the regular digits.Code: Select all
;MAIN EXA, SETUP PHASE 2 ;BUNCHA MATH HERE MARK SETUP2 SEEK -9999 SEEK M ADDI M 1 X ;BACK-TO-BACK PLACEHOLDER TEST: HAS THIS OFFSET BEEN WRITTEN TO? COPY F T TJMP BACK2BACK ;NORMAL PLACEHOLDER JUMP - WRITE OUR VALUES AND BE DONE WITH IT SEEK -1 SUBI X 1 F ;WRITE STARTING VALUE SEEK X ;JUMP TO AFTER THE PLACEHOLDER DIGIT ADDI X 1 X MULI X -1 X COPY X F ;WRITE ENDING 'JUMP BACK' VALUE JUMP SETUP2END ;BACK-TO-BACK PLACEHOLDERS - DON'T WRITE OUR VALUE. INSTEAD ERASE THE OLD 'JUMP BACK' VALUE AND WRITE A NEW ONE TWO PLACES ATER IT MARK BACK2BACK SEEK T SEEK 1 COPY F T TJMP B2BOK SEEK 1 ;BONUS EDGE CASE - THREE PLACEHOLDERS IN A ROW COPY F T MARK B2BOK SEEK -1 COPY 0 F ;ERASE PREVIOUS JUMPBACK VALUE SEEK 1 SUBI T 2 F ;WRITE NEW JUMPBACK VALUE AFTER MARK SETUP2END ;CHECK FOR END COPY M T ;ARE THERE MORE PLACEHOLDERS? TJMP SETUP2
Under normal circumstances, with the pattern that's set up above with all the digits in order at the start, the 'jump back' value is (regular value + 2) x -1. However, there's an unfortunate edge case.
Sometimes, placeholders appear back-to-back in the file. When this happens, we don't write the first offset. Instead, we find the 'jump back' value that was previously there, set it to 0 (which will cause SEEK F to move to the next value in the file without jumping), and write a new 'jump back' value after the next placeholder digit. The new 'jump back' value is equal to (previous jump back value) - 2.
The way we can tell if a back-to-back placeholder is coming up is by looking at the place where we'd write the first offset. If it's a 0, the offset hasn't been used and it's not a back-to-back situation. If it's some other number, the offset has been used, and we switch to the back-to-back code. This is the main reason why we have a pair of buffer values in between the digits and placeholders; this ensures that if we jump to a placeholder, the offset that causes the jump will always be nonzero.
To make matters worse, we have to account for the very special case of three placeholders in a row! If the 'jump back' offset we'd erase is already a 0, then we've been here once before - we can simply move forward two more places in the file if this happens to sort out this issue.
Confused yet? Once all that math and jumping around is done, a file that originally looked like this...
9, 4, 0, 1, 7, 7, X, X, 9, 6, X
...will end up looking like this:
0, 9, 0, 4, 0, 1, 0, 7, 0, 7, 6, 9, 0, 6, 6, 0, 0, 0, 0, 0, -10, 0, -8
We can separate that out a bit. Numbers marked with a * are 'jump forward' offsets, while negative numbers are 'jump back' offsets. Placeholder digits are marked with a #:
0, 9, 0, 4, 0, 1, 0, 7, 0, 7, *6, 9, 0, 6, *6, 0, 0, #0, 0, #0, -10, #0, -8
This also divides it into three blocks, showing the digits, buffer zone, and placeholders. This is what we needed for everything else to be as fast as it should be.
See if you can follow it yourself! Treat each first digit you run into as an offset (SEEK F) and each second digit as to be broadcasted. Remember that SEEK F also advances the file pointer, so SEEK F with a 0 moves your focus in the file 1 place forward.
Main Loop
At this point, it's time for the main EXA to do the actual dialing.This code is where the magic happens. The main EXA enters the modem and uses SEEK F / COPY F #DIAL 11 times to dial the number. (I couldn't fit a @REP 11 and stay in the 150-instruction limit, so I had to make do with a loop of two @REP 5s and an extra left over.)Code: Select all
;MAIN EXA, MAIN LOOP ;OK! TIME TO GO OUT INTO THE BIG BAD WIDE WORLD ;AND DIAL SOME PHONE NUMBERS LINK 800 MODE ;GLOBAL - SEND TO RECORDER ;THIS IS WHERE THE MAGIC HAPPENS MARK DIAL SEEK -9999 COPY 2 T MARK DIALLOOP @REP 5 ;COULDN'T FIT 11 TIMES, HAD TO MAKE DO WITH 5x2+1 SEEK F COPY F #DIAL @END SUBI T 1 T TJMP DIALLOOP SEEK F COPY F #DIAL COPY #DIAL T FJMP INCREMENT ;IF NUMBER FOUND: PLAY IT BACK OVER GLOBAL M COPY -1 #DIAL SEEK -9999 COPY 11 T MARK PLAYBACKLP SEEK F COPY F M SUBI T 1 T TJMP PLAYBACKLP COPY M T FJMP DONE ;ADD TO PLACEHOLDER DIGITS MARK INCREMENT SEEK 9999 SEEK -2 MARK INCREMENT2 ADDI F 1 X SEEK -1 MODI X 10 F TEST X > 9 SEEK -3 TJMP INCREMENT2 JUMP DIAL ;AND WE'RE DONE MARK DONE WIPE
Once the number is dialed, the EXA checks #DIAL to see what turned up.
If a number is found, the main EXA readies itself to send the message to the recorder; it does this by rewinding to the start of the file and doing SEEK F / COPY F M 11 times (with a loop this time, to save space). These values will be picked up by the parser-recorder EXA, which remains in the host to record the phone numbers. The recorder EXA will cue the main EXA whether to continue or halt.
Once a number has been broadcast to the recorder (or not), the main EXA (if it didn't halt) increments the placeholders. It does by going to the second-last value in the file. This is the first placeholder. It adds 1 and writes it to the file; if the result is over 0, it backtracks two more places to the next placeholder and adds 1, and so on. Then it jumps back to the dial loop to start the process all over again.The parser-recorder now switches into recorder mode, recording 88 values in 8 groups of 11. This is a very simple loop, which also sends the count of remaining phone numbers over M to act as a confirmation code. That's it.Code: Select all
;PARSER-RECORDER EXA, MAIN LOOP DROP GRAB 301 COPY 8 X MARK WRITEOUTER COPY 11 T MARK WRITELOOP COPY M F SUBI T 1 T TJMP WRITELOOP SUBI X 1 X COPY X T COPY T M TJMP WRITEOUTER
Conclusion
This took days to code, most of which was debugging and kicking out edge cases. But it's been worth it. 40251/145/1. I'm quite proud of this, and this is where I'll declare victory.
Yeah, this is quite hard to follow. It gets easier if you can step through the code, so I uploaded Quackles' full solution here so it can easily be copy-pasted into the game
Remember that last optimization I did, where the location of the last placeholder was stored in the file, and I could just do a SEEK F?
In summary, Quackles took that and applied it to the whole program. That way you can just do 11 SEEK F, COPY F #DIAL instructions and that's it.
The setup to get there is quite convoluted though.
Since the strategy is so different, Quackles' solution is hard to compare to mine. I suspect this code is about as fast as my solution before I made the ODD/EVEN EXA split. A round of dialing takes Quackles 22 cycles. With my negative numbers and MODI it only took 11 cycles. However, I think Quackles saves cycles during the INCREMENT part by having the placeholders together at the end, so it evens out.
My code didn't require nearly as much fiddling at the start though. My program size was much smaller, which gave me enough space to implement the odd/even split. This roughly doubled the speed. Quackles' solution is very neat, but I'm even more convinced now that that MODI trick is the way to go for a top score.
=== School Management System ===
I don't know why we need to hack a school to sign someone up for a class, but fine. Let's do this.
OST: Network Exploration
The assignment:
- Replace ENGLISH with AP ENGLISH (file 300) in selenium_wolf's child's class schedule (file 235).
- Because those two classes are most likely not offered at the same time, you may need to rearrange the rest of their schedule to make it fit. Modify the schedule so that they are taking the same classes but at different times when necessary. A full list of classes offered is available in file 200.
- Note that there will only be one valid schedule.
- Also note that AP ENGLISH will only be offered once and each other class will be offered no more than twice.
Hm. "Modify the schedule" sounds quite complicated. Let's just do it one step at a time.
Most of the files are student's schedules. There are two other files.
The one in the cafeteria says: "Today's menu. Entrees: Hamburger, Chicken Burger, Veggie Burger, Sloppy Joe's. Salads: Taco Salad, Chef's Salad. Fresh Fruit: Apple Slicers, Tangerine, Seedless Grapes, Mixed Fruit Cup."
The file in the gymnasium says: "Attention students: Keep your hands and feet to yourself. This is not a "Kung Fu Dungeon". Be respectful of your fellow classmates."
And yes, setting the #POWR in the gymnasium to 0 turns the lights off in the digicam feed.
Enough distractions, let's get to the task.
Good to note, selenium_wolf's kid is always in grade 11.
I'm considering this general approach:
1. Remove ENGLISH class from the student's schedule.
2. Add AP ENGLISH to the file, in the right spot.
3. Check if it is at the same time as another class. If so, remove it, find the other moment that class is offered, and add that.
4. Repeat 3 until there is no more overlap.
Let's find out if that works.
The first step is easy enough. XA goes grab file 234 and finds ENGLISH (which it gets from XB over M), then deletes it.
For AP ENGLISH, I need to look it up in file 200. XB has nothing better to do, so it gets this task.
XB finds it in file 200, then sends both the time and name of the class over M.
XA finds a class planned at the same time so it can insert AP ENGLISH in the right spot. This code will fail if there's a gap in the schedule (the exact time for AP ENGLISH isn't found). However, if that happens we know we're done and can just insert it as the final value and finish up. This will also work if we're trying to insert other classes later.
So, for now I'll just add a TEST EOF to this loop and TJMP FINISH and I'll implement FINISH later.
To find the next value, I can mostly reuse the code. If XA copies the overwritten class to M, XB can load it into X, and just reuse the FINDAPENGLISH loop to find it.
The only difference is that XB might first run into the scheduled class that was just overwritten. We don't want to copy that because then it would just keep swapping the class in that time slot forever.
Code: Select all
;XA
LINK 800
LINK 800
COPY M X
LINK 802
GRAB 235
SEEK 2
MARK FINDENGLISH
SEEK 1
TEST X = F
FJMP FINDENGLISH
SEEK -2
VOID F
VOID F
COPY M X
MARK REPLACELP
SEEK -9999
SEEK 1
MARK FINDTIME
SEEK 1
TEST EOF
TJMP FINISH
TEST F = X
FJMP FINDTIME
COPY F M
SEEK -1
COPY M F
SEEK -2
COPY M X
TEST F = X
FJMP REPLACELP
COPY 0 M
COPY M X
JUMP REPLACELP
MARK FINISH
NOOPAt this point, XB will start looking for the class that was just overwritten. Once it finds it, it sends the time on M. XA compares this time to the time that was just used. If it's the same, XA tells XB by sending a 0 and waits for XB to send a different time. In either case, XA then jumps into REPLACELP to replace the next value.
Since every class occurs only twice, there's no need to check XB's second time, it'll always be different.
XB now looks like this.
Code: Select all
;XB
GRAB 300
COPY F M
COPY F X
DROP
LINK 800
GRAB 200
MARK FINDAPENGLISH
SEEK 1
TEST X = F
FJMP FINDAPENGLISH
SEEK -2
COPY F M
COPY M T
SEEK 1
FJMP FINDAPENGLISH
COPY X M
COPY T X
SEEK -9999
JUMP FINDAPENGLISHIf the M value is not zero this means XA was happy with the time and immediately sent the next class to find.
If it's not zero, it's actually the name of the next class to find another time for. The class that goes in the current spot in XA is sent over M now, and the next class is copied from T to X and used for the next round.
Once XA hits FINISH, all entries are in the right order, except the final one which needs to be inserted into an empty spot.
File insertions in EXAPUNKS are hard. At this point I realized something. If I can assume the last rescheduled class will always take the place of the original ENGLISH class (meaning there's no gaps in the schedule), I don't need to insert anything. Instead, I can start by scheduling AP_ENGLISH, and then repeat the loop to move other classes around, until something replaces ENGLISH. At that point, everything is in order and I just need to stop the EXAs.
Code: Select all
;XA
LINK 800
LINK 800
LINK 802
GRAB 235
COPY M X
MARK REPLACELP
SEEK -9999
SEEK 1
MARK FINDTIME
SEEK 1
TEST F = X
FJMP FINDTIME
COPY F M
SEEK -1
COPY M F
SEEK -2
COPY M X
TEST F = X
FJMP REPLACELP
COPY 0 M
COPY M X
JUMP REPLACELPCode: Select all
;XB
GRAB 300
COPY F T
COPY F X
DROP
LINK 800
REPL ENGLISH_CHECK
GRAB 200
MARK FINDAPENGLISH
SEEK 1
TEST X = F
FJMP FINDAPENGLISH
SEEK -2
COPY F M
COPY M T
SEEK 1
FJMP FINDAPENGLISH
COPY X M
MODE
COPY T M
MODE
COPY T X
SEEK -9999
JUMP FINDAPENGLISH
MARK ENGLISH_CHECK
MODE
COPY T X
MARK CHECK
TEST M = X
FJMP CHECK
KILL
LINK 800
LINK 802
KILL
My assumption was correct, this works. 717/55/8. Top percentiles are 608, 39 and 3.
Thinking about optimizations, activity is doable. Start off with one EXA, REPL it once to grab 200, then move the original forward into the grade 11 node. And instead of the KILLs add extra logic to each EXA to die if they get some specific M message or something.
As for speed, I got a minor improvement to 710 by unrolling the XA FINDTIME loop. Unrolling the loop itself doesn't save anything because you need the conditional checks anyway, but it does allow you to combine that SEEK 1 outside the loop with the first iteration of SEEK 1 inside the loop. Perhaps bigger improvements are possible by changing something in the search order, or have more efficient/less M communication. Less M communication might also save some cycles.
I'll leave the actual optimizations to the thread this time. Next update, x10x10x needs help to get back their anime.
Well, this is something.
I can see an open network that's... I can't even tell how big.
