Note: in the actual submission, the rs are replaced with nonprintable or invalid-UTF-8 bytes; see the hexdump below. I've used r to represent them in this post and in the TIO link, because all unimplemented commands in Befunge-98 have identical semantics to r.
50050050050050050050050050050050050050050xxxxxnnnnn#####;;;;;~~~~~:::::~~~~~-----!!!!!!!!!!;;;;;@@@@@,,,,,.....;;;;;#####\\\\\kkkkkrrrrr'''''#####-----:::::ccccc-----*****#####rrrrr!!!!!;;;;;#####-----aaaaa~~~~~+++++;;;;;#####11111kkkkkrrrrr22222+++++;;;;;
Try it online!
Hexdump
This is the actual submission, as an xxd reversible hex dump.
00000000: 3530 3035 3030 3530 3035 3030 3530 3035 5005005005005005
00000010: 3030 3530 3035 3030 3530 3035 3030 3530 0050050050050050
00000020: 3035 3030 3530 3035 3078 7878 7878 6e6e 050050050xxxxxnn
00000030: 6e6e 6e23 2323 2323 3b3b 3b3b 3b7e 7e7e nnn#####;;;;;~~~
00000040: 7e7e 3a3a 3a3a 3a7e 7e7e 7e7e 2d2d 2d2d ~~:::::~~~~~----
00000050: 2d21 2121 2121 2121 2121 213b 3b3b 3b3b -!!!!!!!!!!;;;;;
00000060: 4040 4040 402c 2c2c 2c2c 2e2e 2e2e 2e3b @@@@@,,,,,.....;
00000070: 3b3b 3b3b 2323 2323 235c 5c5c 5c5c 6b6b ;;;;#####\\\\\kk
00000080: 6b6b 6bff ffff ffff 2727 2727 2723 2323 kkk.....'''''###
00000090: 2323 2d2d 2d2d 2d3a 3a3a 3a3a 6363 6363 ##-----:::::cccc
000000a0: 632d 2d2d 2d2d 2a2a 2a2a 2a23 2323 2323 c-----*****#####
000000b0: 0000 0000 0021 2121 2121 3b3b 3b3b 3b23 .....!!!!!;;;;;#
000000c0: 2323 2323 2d2d 2d2d 2d61 6161 6161 7e7e ####-----aaaaa~~
000000d0: 7e7e 7e2b 2b2b 2b2b 3b3b 3b3b 3b23 2323 ~~~+++++;;;;;###
000000e0: 2323 3131 3131 316b 6b6b 6b6b c1c1 c1c1 ##11111kkkkk....
000000f0: c132 3232 3232 2b2b 2b2b 2b3b 3b3b 3b3b .22222+++++;;;;;
Strategy/algorithm
Looks at characters in pairs from the start of the program. If they're:
- not equal, deletes the first character of the pair;
- equal but not
// nor ##, moves onto the next pair;
- equal and
// or ##, moves onto the next line.
The idea is that if programs in practical languages are using "hide where my code is" techniques rather than proper radiation-hardening techniques, we should be able to find the start of the real code. If the program starts with a large number of repetitive no-ops, we can skip over those because every consecutive pair in a long string of repeated characters is equal; if it starts with a comment marker consisting of repeated characters, that's in most practical languages probably going to be ////… \n or #####… \n and we can skip to the next line; if it starts with a comment/literal marker that doesn't consist of repeated characters (such as /*) we can in most cases simply delete the first character of the marker to uncomment the chaff code, which will also typically break a program because the chaff isn't valid code. (Python also has ''' and """ as literal markers, but these have an odd length so we damage the marker rather than the useless contents inside.) So there's a reasonable chance that the first or second character we delete will end up breaking the program we're attacking.
Installation
Install appropriate packages for building C programs (on Ubuntu, this is build-essential), and download https://catseye.tc/distfiles/fbbi-1.0-2015.0729.zip, then:
unzip fbbi-1.0-2015.0729.zip
cd fbbi-1.0-2015.0729/
(cd src; make)
Run programs using bin/ffbi programfilename (while in the ffbi-1.0-2015.0729/ directory created during the install).
Explanation
Radiation hardening
This is based on a technique discovered by Martin Ender for this answer, which is a little difficult to explain to people who don't know Befunge-98, but I'm going to try anyway.
It works using the x command; you can think of this command as taking a pair of coordinates interpreted as a vector, and creating something line-like (a "Lahey line") in 2D space by repeatedly moving in the direction of the vector (and the exact opposite direction) starting from itself. For example, if an x is given the coordinates (2,1), it creates the following Lahey line (which is also an actual line) in 2D space (marked with + signs), stretching out to infinity in both directions:
+..........
..+........
....x......
......+....
........+..
..........+
Unlike actual lines, though, which pass through every point on them, specifying a vector like (2, 0) gives you a Lahey line that only passes through some of the squares along it:
.+.+.+.x.+.+.+.+.
While the x command is in effect, the Befunge-98 interpreter basically acts as though all the commands that aren't on the Lahey line don't exist. This means that if we can set up an appropriate Lahey line that passes through every fifth character of the program (starting at the first x that remains in the program after radiation damage), and every character from then on (including the x) is repeated five times, any four characters can be deleted from the program and yet it will still have identical behaviour to the original version – in either case, the set of non-hidden characters from the x onwards are identical. (The idea is that before the location of the first deletion, the Lahey line passes through the first character of each set of five; between the first and second deletions, it passes through the second character of each set of five, etc., with the last character of the set being used after the fourth deletion.)
Befunge has a lot of commands that cancel the effect of x (including, most notably, x itself, plus pretty much all the flow control commands). That made this program a fairly awkward restricted-source challenge, as I had to write some nontrivial program logic with most of the flow control commands missing. However, the fact that x cancels the old Lahey line before creating a new one is useful in setting up the appropriate Lahey line delta, of (5, 0). The idea is to start by putting a lot of 5s and 0s on the stack in the repetitive 050 050 050 … pattern (the stack starts with a zero on it, so the leading 0 can be omitted); each of these patterns (if non-irradiated) will be interpreted as either (5, 0) or (0, 5) depending on its distance from the top of the stack, and the interpretation of two adjacent patterns alternates between (5, 0) or (0, 5) unless radiation hits the upper copy of the pattern. Because there are many more than four copies of the pattern on the stack, there's thus guaranteed to be a (5, 0) pair on the stack somewhere if it's interpreted as pairs from the top. Also, there's nothing but 0s and 5s on the stack, so any pair must be (0, 0), (0, 5), (5, 0), or (5, 5).
Now, consider what happens when the x command gets run. If its argument is (5, 0), it creates the Lahey line that we want, and the program continues in its radiation-hardened way. If it's (0, 0), (0, 5) or (5, 5), then the Lahey line that's created misses our program altogether; (0, 5) and (5, 5) are vertical and diagonal lines that cross our program only at a single point, and the Lahey line (0, 0) is a special case that's inherently a single point. In these cases, therefore, everything in the program apart from the x we just ran gets hidden, so the interpreter has no choice but to run the x again (exiting is always explicit in Befunge), taking the next pair from the stack. Thus, with a one-liner program like this, the behaviour of x inherently looks at pairs of values at a time along the stack until it finds the (5, 0) that must exist, and thus is guaranteed to create a Lahey line that runs along the program in the correct way to radiation-harden it.
(There are many more 050 patterns in this program than are actually required for the radiation hardening to survive four deletions – the idea is to be able to survive for more than four rounds if the opponent is primarily attacking the start of the program, because most damage there is survivable; to eliminate the (5, 0) pattern entirely, a number of deletions equal to the number of 5s is required.)
How to do flow control
When writing the main body of the program, because almost all flow control commands cancel the Lahey line, ; … ;# and kr are pretty much all I had to work with.
; … ; is a jump, and adding #s in various places controls whether the jump is taken or skipped when executing the code in forward and/or reverse order (it also sometimes has the unfortunate side effect of skipping one character beyond the end of the jump, because # is a skip command, but this is easy to work around by repositioning characters; it just makes the program harder to read).
kr is a method of creating a conditional without breaking the Lahey line, but it's very quirky (the semantics of k are famously confusing). This combination pops the stack, then does nothing if a 0 was popped, reverses the execution direction if an odd or negative number was popped (for different reasons in the two cases), and its semantics are too complicated to easily describe if an even positive number was popped – this program therefore uses only the arguments 0 and 1, to keep the behaviour of kr easy to understand.
r on its own reverses the execution direction unconditionally, which was useful in one place (as #r, which reverses the execution direction only if it's currently going to the left).
As usual for Befunge-98, it's possible to replace r with any invalid command, so I picked NUL, plus two high-bit-set characters that aren't valid UTF-8, in the hope of confusing programs that don't have binary-safe input routines. (FBBI itself is binary-safe if run on a Unix-like system, like the one being used in this challenge.) The command in question is nonetheless written as r in this post, as that's the "official" name for it.
Doing the actual work
Once the x command gets hit, here's what the remaining program along hte Lahey line looks like, and how it works (there's also some junk 0s and 5s at the start but they never again get executed):
xn#;~:~-!!;@,.;#\kr'#-:c-*#r!;#-a~+;#1kr2+;
x establish Lahey line
n clean stack (pop all the 5s)
#; jump label, no-op right now
From this point onwards, the element currently on the top of the stack (which at this point is a 0 because the stack has just been cleaned) counts the number of bytes that the program has read.
xn#;~:~-!!;@,.;#\kr'#-:c-*#r!;#-a~+;#1kr2+;
~ read byte
: copy it
~ read another byte
- subtract
!! cast to bool (like in C)
; ;# jump … to jump label + skip
kr reverse direction if truthy
A truthy value at this point means that the two bytes we read were different, so it's time to select the first of the two bytes and exit the program. Top of the stack at this point is the first of the two bytes; the second stack element is its index (because it's still unchanged from the start of the main loop).
xn#;~:~-!!;@,.;#\kr'#-:c-*#r!;#-a~+;#1kr2+;
\ swap
;# jump label, no-op going left
. output integer then space
, output raw byte
@ exit program
Very convenient that Befunge's "output integer then space" command is usable in this challenge (because it requires a space after the integer)! If the format didn't allow/require a space there, the integer-to-decimal conversion would take up much, much more room and probably reduce the amount of radiation hardening available as a consequence.
If the two bytes the program read are the same, the program continues by checking to see if they're // and/or ##, via arithmetic on character codes:
xn#;~:~-!!;@,.;#\kr'#-:c-*#r!;#-a~+;#1kr2+;
'#- subtract char code of `#`
: * multiply by (itself
c- minus 12)
#r no-op if going right
! logical not
; ;# jump … to jump label + skip
kr reverse direction if truthy
The direction reverse here happens if, in C syntax, !(d*(d-12)), where d is the first byte of the pair minus the character code of #; # and / have character codes that differ by 12, so this is true if the byte is # or / (the multiplication * is being used like a logical AND). In this case, the strategy is to skip until finding a newline. The top of the stack at this point is the byte counter, because everything else has been popped, and that gets update while looking for the newline:
xn#;~:~-!!;@,.;#\kr'#-:c-*#r!;#-a~+;#1kr2+;
+ 1 add 1 to top of stack
;# jump label, no-op going left
~ read byte
-a subtract 10
;# jump label, no-op going left
! logical not
r reverse direction
! logical not again
; ;# jump … to jump label + skip
kr reverse direction if truthy
In other words, the program adds 1 to the byte counter, then reads the next byte, and continues doing this until a newline was read. (This shares some of the code from the previous case – in that case, the ! is executed once, so that the loop is exited/not entered if the character isn't / or #, but in this loop, the same ! is executed twice, so that the loop is exited if the character is a newline. In one-line Befunge-98, opportunities like this to use the same character in both directions are rare, but fun when they happen.)
If the byte pair was something other than // or ##, or when the newline has been found, the program's main loop continues:
xn#;~:~-!!;@,.;#\kr'#-:c-*#r!;#-a~+;#1kr2+;
2+ add 2 to top of stack
#; ; jump … to jump label
This skips over the xn at the start, and also skips over any of the 0s and 5s that happen to fall on the Lahey line. (In Befunge-98, execution wraps, but it wraps along the Lahey line rather than toroidally around the program, so the same set of characters will be executed after the wrap; the program's length modulo 5 is irrelevant.)
The program "forgot" to add 2 to the byte counter after the pair was checked, so it gets done here; the reason for postponing it is that less stack manipulation is needed to set it here (because there's no need to remember the first character of the pair at this location in order to check whether it's / or #, so the byte counter is the only thing on the stack at this point), and postponing it still produces the correct results because addition is commutative, so it doesn't matter whether we add the 2 before or after adding the 1s. (The skip-to-newline loop doesn't actually inspect the byte counter, just increment it.)
This program doesn't actually work for all inputs – I didn't add any code to handle EOF, rather the hope is that it won't be given input for which the algorithm reaches EOF before reaching a termination condition. I think this is probably a reasonable tradeoff – code to handle EOF given the stringent restrictions on control flow would make the program much longer and thus reduce the amount of radiation it could withstand, as I'd have to use a higher-frequency Lahey line to fit it all into 256 bytes.
