Part 22: StreetSmarts GIS Database

Part 22 - StreetSmarts GIS Database

=== Trash World Inbox ===

A low size solution. Quite straightforward - while the 'main' EXA is dialing, a payload EXA goes back to read the payload file to X and T. It then waits for a message from the dialing EXA, and LINKs to the radio host when it gets it. There it overwrites the playlist. COPY F F is a way to check if you're at the end of the file yet. If not, it takes the value at the F cursor and writes it to the next location. Doesn't matter since it gets overwritten anyway. I didn't know COPY F F was legal, since you can't do something like ADDI F F X. But it is, and it's necessary here because X and T are already occupied.


=== StreetSmarts GIS Database ===


That was surprisingly easy.
People are requesting the single, humming it to themselves, buying the album...
Just because they've heard it before.
Is that really all it takes?



Two votes for "more complex", but 3 for this one.

Mass media is a sham.

It's seeming that way.
Hmm.
Girl you need to get a cluuuue...
I just can't not get over yoooou!
Oops. I guess it is pretty catchy.

I didn't know AIs could get an earworm.





Next up, hacking a GIS database.

Theory: The inconsistency of ratings depends on context.
We made a hit by picking a generic pop song and artificially boosting its exposure.
But there are other domains where this isn't possible.
For example, you couldn't change people's behavior by giving a Last Stop store a five-star rating in a restaurant guide.
That would be ridiculous.



All votes but one for "You never know".

You never know...

This is why we need to experiment.


OST: Network Exploration

The assignment:
- Each host contains a list of restaurants and their ratings, from one to five stars (file 200). Locate the entry that corresponds to the Last Stop on Eddy Street and change its rating from one to five stars.
- The name of the target restaurant and its location within the GIS grid is available in file 300. The first coordinate is the number of times to move east, while the second coordinate is the number of times to move north (positive) or south (negative).
- For more information see "Network Exploration: Geographic Information Systems" in the second issue of the zine.

Let's see what the zine has to teach us.



We're dealing with a StreetSmarts system here. I'm just wondering what that would look like for any city that isn't grid based.

Also, since GIS is short for Geographic Information System, it's pronounced GIS, not GIS.



As you can see there's one or two restaurants in each block. There's also a compass needle to conveniently show us which way is which. East (the first value in file 300) is to the top right, while north is to the top left.

Let's start building.

I think it'd be convenient to have one EXA stay home to just transmit the coordinates:
East, then north/south, and finally the name of the restaurant to look up in the file.

The 'walking' EXA should first go the right "east" position (can I call it longitude?):

If the east value starts at 0, XB shouldn't move at all from the starting grid space, so it skips the loop. Otherwise it LINKs until the number of steps becomes zero.

The north-south (latitude) code has to deal with negative values, so it's more complicated:

First I check if the value is negative, if so it jumps to GOSOUTH. If not, I first check if it's zero, in which case we're done. From there on I use the T register again for the countdown so I can use the TJMP without TEST when the EXA is in the right place.

Finally, grab the file, and find the right restaurant. Since any restaurant has at least 1 star, I can copy the first star and write that to the file four times.





This initial solution runs at 48/40/6. The top percentiles are 26, 25 and 6 respectively.

Activity is already optimized at 6. That makes sense, because 6 is how many steps it takes to get to the far corners of the grid, so that'll correspond to the highest-activity test case. Time to improve the other metrics.

First of all, we can speed up the search within the file. Since there's never more than 2 restaurants in a file, the following solution works:

Check if it's the first value. If not, it's the second value, so SEEK to the star just beyond it. This drops the cycle count to 37.

For the next improvement, I considered that specifically going for the correct grid space is a bit slow with all the tests if the EXA is there yet. Since the restaurant we're looking for exists in only one place, I just can have EXA REPLs check everywhere.

It's a bit fiddly to have the EXAs only go where they need to be and not visit nodes several times.

From the start, XB REPLs itself into south-, north- and eastbound copies. It also jumps to GRABFILE in case the restaurant is in the initial grid space.

The south- and north-bound EXAs each link in their directions twice, leaving eastbound and GRABFILE EXAs behind. This is all written out instead of using @REP so I have manual control over when to use REPL and when a JUMP suffices, to prevent creating extra EXAs.

The eastbound EXAs link in their directions three times, leaving GRABFILE instances behind so the entire grid is covered.

Finally, in the GRABFILE code, after SEEKing for the second restaurant entry, it has to test if that's the correct one. If there's only one entry, the TEST makes this EXA die, and if it's the wrong one, the DIVI by zero will do so.

27/41/20.

Notice that I always do the REPL to the moving EXAs first, and that I start with SOUTH and NORTH before EAST. Moving to the back of the grid takes the longest so it's important to optimize it as much as possible. I also tried making the eastbound EXA spawn columns of south/north-bound ones but that was slightly slower.

There's one more cycle to be saved here, though.

It's actually slightly faster to first spawn the eastbound EXA in the farthest south and north columns, and then go back to see if the skipped file isn't the right one. 26 cycles.

I tried more tweaking with the movement order but I couldn't get it better than this.


Finally, for size, the most straightforward trick is to just use loops instead of unrolls. Remove all speed optimizations in favour of simpler code:

Down to 49/32/20. The directional loops would go on forever, except those EXAs just die as soon as they can't link any further.

For the next improvement, we need to reuse lines. This 29-line solution does so:
Basically, I rewrote the LINKing logic to the slower solution where the eastbound EXA splits off in north- and southbound ones. Then by rearranging the REPLs, I can use a fallthrough to turn the eastbound ones south. Also, the START mark means I don't need the initial set of REPLs anymore.

Finally, I can combine the southbound and northbound loops by putting the LINK ids in a register:

This clocks in at 47/27/20. I'll leave the further improvement to the top percentile size of 25 lines to the threads.

Oh.
Apparently, that Last Stop location is getting mobbed.
Processing.
People are choosing to believe the guide even when it's obviously wrong...
Why would they think Last Stop has actual good food?
And why did the guide change their behavior, but not the highway sign?



Here is the first vote.

Before I finish for today, do you remember when I posted that story from the first zine, way back in episode 7? It was a couple of pages long.

The second zine contains the last half of the story, here it is.

Click the images for higher resolution.





Next time, we'll have another hacker battle.

Time for the next opponent.
Are you ready?