37
\$\begingroup\$

Correct a single-letter typo in a fixed text.

Input: The paragraph below but with exactly one typo, where a single letter a-zA-Z is replaced by a different letter a-zA-Z. To be clear, the letter isn't replaced everywhere it appears, but just in that one place. For example, the first word "In" might become "IZ". Non-letter characters like spaces or punctuation cannot be affected.

Output: The paragraph exactly as below, without the typo. A trailing newline is OK.

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

TIO with text

The text is taken from the Wikipedia article Error detection and correction. But, your code may not fetch the text from Wikipedia or elsewhere, as per the standard loophole.

Any site-default string I/O is acceptable. Fewest bytes wins. Please check that your solution works for all 23001 possible inputs, if you're able to run that much.

\$\endgroup\$

15 Answers 15

20
\$\begingroup\$

Python 2, 136 ... 97 96 bytes

def f(s,n=0):k=s[:n>>7]+chr(n%128)+s[n/128+1:];return 0x2e838ca8118c7496+hash(k)and f(s,n+1)or k

Try it online!

Simply replace each character in the given input with each possible letter, then check if the hash matches the correct string. I use Python 2 hash function, which is deterministic and has no collision within our search space.

This program checks if the function returns correct output for all possible input. It takes ~2 hours to run on my computer

Thanks @Jitse for saving -22 bytes with recursion!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan yes I have, will post the collision check soon \$\endgroup\$ – Surculose Sputum Mar 9 at 3:09
  • \$\begingroup\$ Snap! Will do, thanks for pointing it out. \$\endgroup\$ – Surculose Sputum Mar 9 at 3:32
  • 1
    \$\begingroup\$ If the hash is indeed 64 bits and roughly random, it seems very likely it will give no false matches with two-character changes, but a check would indeed be good. \$\endgroup\$ – xnor Mar 9 at 3:34
  • 1
    \$\begingroup\$ @JonathanAllan took a long time, but I checked and all inputs return the correct output. \$\endgroup\$ – Surculose Sputum Mar 9 at 4:28
  • 1
    \$\begingroup\$ Assuming sufficiently high recursion limit and stack size, you can write it as a recursive function for 98 bytes. Can't show examples in this TiO link, because it will exceed the character limit of this comment. \$\endgroup\$ – Jitse Mar 9 at 10:23
13
\$\begingroup\$

MATLAB with Communications Toolbox, 88 64 59 bytes

Z=rsdec(gf([+input('') 879 323],10),532,530);disp([Z.x ''])

This uses a (1023, 1021) Reed-Solomon code shortened to (532, 530). This is a systematic, non-binary code with alphabet size 1023, which can correct any single-symbol error.

The number 1023 has been selected because, in Reed-Solomon codes, both the alphabet size and the maximum input length must be of the form n = 2m−1 for m integer. Since the input text has alphabet size bounded by 95 (number of printable ASCII characters) and length 530, m = 9 (n = 511) would be too small, and m = 10 (n = 1023) is enough.

The error-correcting code has first been applied to the input message to obtain the parity bits. This has been done offline. The submitted program only implements the decoder.

Encoder

Each ASCII character in the input is considered as a symbol from a 1023-size alphabet, and then the code is applied using the gf and rsenc functions.

Note that the code is not part of the submitted solution, and is not golfed.

x = 'In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.';
x_ext = [zeros(1,491) double(x)]; % convert to code points. Zero-pad to length 1021
y_ext = rsenc(gf(x_ext, 10), 1023, 1021); % encode
y = y_ext(492:end); % remove zero padding
y = double(y.x); % convert to double
check_symbols = y(numel(x)+1:end)

This gives check_symbols = [879 323]. The encoded codeword is the input expressed as code points with these two numbers appended.

Decoder

This is a program that reads the input text as a string from STDIN and displays the corrected text in STDOUT.

Z=rsdec(gf([+input('') 879 323],10),532,530);disp([Z.x ''])

The parity-check symbols are appended to the code points of the input, and the result is provided to the decoder with code parameters 532, 530, which define the shortened code. This causes the decoder to implicitly assume zero-padding. The gf and rsdec functions are used for this. The result Z is converted to char.

Note that + is used instead of double to save bytes; and similarly, [... ''] is used instead of char(...).

Example run

enter image description here

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Thank you, I learned something new! \$\endgroup\$ – Cris Luengo Mar 9 at 15:19
11
\$\begingroup\$

Jelly,  30  25 bytes

JœPjⱮØẠɗ€⁸Ẏ1,ȷ9ḥ⁼“×Ṙ*-’ƲƇ

A full program printing the result (as a monadic Link it yields a list of one list of characters).

Try it online!

How?

Changes each character (including non-A-Za-z ones) to every character in A-Za-z and checks if a hashed value is equal to that of the required input. The hash function was chosen so that none of the \$450 \times 51 + 79 \times 52 = 27058\$ possible states for each \$451 \times 51 = 23001\$ inputs hash to the same value as the expected output*.

The program to check for collisions is here (I split the 2-char check into 5 parts and ran for over 1h to completion).

* smaller hash functions might work for just visited states which could save bytes (although if a collision does exist further on than the correct match then an must be appended).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Is the hash enough that any change of two letters produces a different result? I think you need that so that an input with a one-letter change doesn't have a different one-letter change where the resulting two-letter change gives the same hash as the original text. \$\endgroup\$ – xnor Mar 9 at 3:02
  • \$\begingroup\$ Good point, quite possibly not. I think checking might take a while ...deleting. \$\endgroup\$ – Jonathan Allan Mar 9 at 3:06
  • 1
    \$\begingroup\$ It was not, but now is ...and could probably be smaller. \$\endgroup\$ – Jonathan Allan Mar 9 at 12:21
10
\$\begingroup\$

C (gcc), 260 259 247 226 223 217 215 214 198 189 bytes

y;*R=L"ė|h0\"k5&j4Đzm7ſ4sM6~0=a[z@z4zp4y j,-#3#mu7qĘdd";char n,k,t,u,r,c,x;f(char*s){for(n=y=23;n--;c?u=n:0,r?x=r,t=n:0)for(r=R[n],c=R[n+y],k=y;k--;r^=s[y*n+k])c^=s[y*k+n];s[y*t+u]^=x;}

Try it online!


Now with 9 fewer bytes, thanks to @ceilingcat!


Thanks to @Bubbler for golfing 16 bytes off!

I haven't updated the readable version to include @Bubbler's modifications, but the biggest improvement is in the XOR computation loop. The shorter approach starts at the desired values R[n] and R[n+23], and repeatedly does an XOR, which will yield 0 at the end (except at the bad character). My answer had the loop starting at 0, and checking for the values R[n] and R[n+23] at the end.


I've added a readable version of the code, commented and with whitespace, at the end of the answer.


This doesn't use an md5sum or hash function, since that's not available in C without using an external library. Here's how this program works instead:

Imagine the input text, except for the final '.', arranged in a square. The XOR of each row and the XOR of each column are computed, and they're compared with the correct XOR values from the original text. One row XOR value and one column XOR value will not be what they should, and that tells you which character to fix, and which bits to flip to make it right.



Here's the more readable version of my last version of the code (before @Bubbler and @ceilingcat's improvements), commented and with whitespace:

f(char*s)
   {
/*****
   The original text contains 530 characters.

   Using the fact that 23 * 23 = 529, view the text as
   arranged in a 23 x 23 square (plus the '.' at the end,
   which doesn't matter since it can't be changed).
*****/

// The string R below is 46 characters long.
// It consists of the XOR of each of the 23 rows in the original text,
// folllowed by the XOR of each of the 23 columns.
    char *R = "\x17|h0\"k5&j4\x10zm7\x7f""4sM6~0=a[z@z4zp4y j,-#3#mu7q\030dd",
         n,k,t,u,r,c,x;

    for (n = 23; n--; )
       {
// Compute the XOR of row n of the input string, and store it in r.
// In the same loop, compute the XOR of column n of the input, and store it in c.
        r = c = 0;

        for (k = 23; k--; )
           {
            r ^= s[23*n+k];
            c ^= s[23*k+n];
           }

// If the computed row value doesn't equal the row value from the original text,
// save the bad row number in t.  Also save (in x) the bits that are wrong.
        if (r-R[n])
          {
           t=n;
           x=r^R[n];
          }

// If the computed column value doesn't equal the column value from the original text,
// save the bad column number in u.  There's no need to save the bits that are wrong,
// since they're guaranteed to be the same as the bits that are wrong for the row.
        u = c-R[n+23] ? n : u; // Golfed equivalent of:
                               // if (c != R[n+23]) u=n;
       }

// Fix the bad character, which is in row t and column u, by flipping the bits in x.
     s[23*t+u]^=x;
    }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 198: y=23;f(char*s){char*R="\x17|h0\"k5&j4\x10zm7\x7f""4sM6~0=a[z@z4zp4y j,-#3#mu7q\030dd",n=y,k,t,u,r,c,x;for(;n--;r?x=r,t=n:0){r=R[n];c=R[n+y];for(k=y;k--;r^=s[y*n+k])c^=s[y*k+n];c?u=n:0;}s[y*t+u]^=x;} \$\endgroup\$ – Bubbler Mar 9 at 6:37
  • \$\begingroup\$ @Bubbler Thank you! That's clever golfing -- especially starting at R[n] and R[n+23] and aiming at 0, instead of starting at 0 and aiming at R[n] and R[n+23]. \$\endgroup\$ – Mitchell Spector Mar 9 at 7:10
  • \$\begingroup\$ @ceilingcat Thank you -- it looks like it's actually 185 bytes now. I'm kind of surprised that it works with R declared as an int * (implicitly) instead of as a char *. \$\endgroup\$ – Mitchell Spector Mar 11 at 4:50
  • \$\begingroup\$ There is a bug in the way TIO counts bytes in C files. Change the language into "bash" and see how long it is. \$\endgroup\$ – ceilingcat Mar 11 at 6:43
  • \$\begingroup\$ Strange. I’ve mostly used TIO for bash. \$\endgroup\$ – Mitchell Spector Mar 11 at 6:47
8
+100
\$\begingroup\$

Ruby, 122 121 119 113 bytes

->s{s[a=(0..9).sum{|x|",JEDI>(:6#"[x].ord==(0..529).sum{|w|s[w].ord*w[x]}%84?0:2**x}]=""<<50998-s.sum+s[a].ord;s}

Try it online!

How:

Compare partial sums applying different masks to the string:

In information theory and coding theory with applicati [...]
X X X X X X X X X X X X X X X X X X X X X X X X X X X  -> "I nomto hoyad [...]"
XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX -> "Innfmaonhey d [...]"
XXXX    XXXX    XXXX    XXXX    XXXX    XXXX    XXXX   -> "In imatiheord [...]"

With 10 partial sums (and the total sum of the original string) we have enough information to detect and fix a single error.

Incidentally, the partial sums modulo 84 converted to ASCII form the word "JEDI" and an Australian smiley, which I hope bring some imaginary bonus point.

Why not hash?

From the Ruby documentation:

The hash value for an object may not be identical across invocations or implementations of Ruby. If you need a stable identifier across Ruby invocations and implementations you will need to generate one with a custom method.

I'm lazy. That's why.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Clever. Is there a name for this error-correction technique? It's similar to Hamming codes, but on base-84 digits rather than on bits. \$\endgroup\$ – David Cary Mar 11 at 9:25
  • \$\begingroup\$ I don't know if it has a name, it's a generalization of parity check / hamming code, base 84 is for the specific case, because the characters we need are all in range 65-122 (so any number > 57 would do) and all partials sums of this string modulo 84 are printable ASCII. Checking single bits would require more code. \$\endgroup\$ – G B Mar 11 at 13:01
6
\$\begingroup\$

Python 3, 83 bytes

def f(s,t=118,u=-10340):
 for x in s:t-=x-96;u-=t
 *l,=s;l[u//t]+=t;return bytes(l)

Try it online!

We compute a custom numerical checksum that let us locate and fix the error. This means don't need to try possible changes until we find one that works. As a result, the code run very fast, letting us test all 23,001 possible inputs in under 2 seconds in the linked TIO.

Input and output are as bytestrings, which requires Python 3.

The checksum

It's a bit easier to understand the idea using the code below.

def f(s):
 t=50998-sum(s)
 k=13447420-sum(i*x for i,x in enumerate(s))
 i=k//t
 l=list(s)
 l[i]+=t
 return bytes(l)

Try it online!

The core is the checksum, which gives two values. The correct string (and only it) gives the values (50998, 13447420), which are used in the code above.

def checksum(s):
 t=sum(s)
 u=sum(i*x for i,x in enumerate(s))
 return(t,u)

Try it online!

The checksum not only lets us know whether the string is correct, but the difference from the checksum to the real string lets us deduce what the error is and fix it. This doesn't rely on the typoes being with letters.

How does it work?

The checksum consists of two parts, each of which is a number.

The part t=sum(s) is simply the sum of the (ASCII) values in the string. Given a string with a single typo from the original, we can figure out the numerical difference between the original and typoed character by comparing the sum to the original's sum of 50998. For example, if we find a sum of 51001, we know that the typo increased a character by 3, such as a->d or M->P.

So, we know the amount that the character is off, but not which one. That is, we don't know the index. For that, we use the additional information given in the second value u of the checksum,

u=sum(i*x for i,x in enumerate(s))

Here, we add up all the characters, but each one is given a multiplier equal to its index, so zero times the initial character plus one times the next one, up to 529 times the last one.

The idea is similar to a classic puzzle:

You have 10 bags of coins. Each bag has 10 gold coins that each weigh 10 grams, except one bag is filled with lighter counterfeits that each weigh 9 grams but otherwise look normal. You have a digital scale that displays exact numerical weight. How can you determine which bag has the counterfeits, using only a single weighing?

The solution is to number the bags 1 to 10, and put 1 coin from bag 1 on the scale, 2 coins from bag 2, up to 10 coins from bag 10. That's 55 coins total, so if all the coins had been real, they'd weigh 550 grams. But, each counterfeit coins lowers the total weight by 1 gram. So, since the fake bag will contribute its index-number of underweight coins, which is however many grams under 550 we see. This tell uses which bag is fake. (We could also have zero-indexed 0-9 and used 45 coins.)

The checksum u works just like this. Suppose that the typo is index j, and it's off by an amount d as determined by the first checksum value t. Then, the index j will contribute to the error in u with a multiplier equal to j, so it will be off by j*d. Knowing both d and j*d lets us find the typoed index j by dividing.

Fixing the error

The error is fixed as *l,=s;l[u//t]+=t;return bytes(l). This converts the string to a list, modifies the indexed value in place with +=, and then converts back a bytestring. This is pretty ugly. Note that strings and bytestring are immutable in Python, unlike lists, so we couldn't just modify the string directly.

I'm still not really clear what default string I/O permits, despite having given it the go-ahead in the challenge. If we can do input and output on lists of ASCII values, then we can save a lot of code, especially by modifying the input list in place.

61 bytes

def f(l,t=118,u=-10340):
 for x in l:t-=x-96;u-=t
 l[u//t]+=t

Try it online!

Optimizations

def f(s,t=118,u=-10340):
 for x in s:t-=x-96;u-=t
 *l,=s;l[u//t]+=t;return bytes(l)

We save some characters in the above code with a few optimizations.

Instead of computing the checksum values (t,u) and subtracting the target values, we get the differences directly by initializing t and u to to their target values and subtracting the contributions for each character iteratively. Passing in the original string would make them end up both as zero, giving a divide-by-zero error in the code.

Instead of using enumerate to compute the weighted sum u, we repeatedly subtract the running sum t, which subtracts each character value successively more times. This effectively computes the weighted sum for the reversed string, that is with the biggest weights at the front. But we end up with a negative index that goes from the back, so it works out.

Finally, we are able to obtain shorter-to-write checksum values (t,u) = (118,-10340) instead of (50998, 13447420) by using a slightly different checksum that first subtracts 96 from each ASCII value. This is the rounded average ASCII value for the text, so subtracting it makes the string values average out to roughly zero. This make the checksums have both positive and negative summands that make them close to zero. These values of (118,-10340) are tantalizingly close to being one digit shorter, and one is negative, but I didn't see a way to shorten them.

I was originally planning to do all checksums computations modulo some prime to make the resulting values shorter to write, but they are short enough anyway that it's not nearly worth it, even without the optimization above.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

JavaScript (Node.js), 78 bytes

This is a port of xnor's great answer.

s=>(t=118,u=10340,g=k=>Buffer(s).map(x=>(u+=t-=k&x-96)-531*t?x:x+t))(g(~0))+''

Try it online!


JavaScript (Node.js),  121 118  116 bytes

s=>[...s+'jEIM'].some(c=>[...s].some(C=>Buffer(o=p+c+s.slice(++i)).map(c=>k=k*99^c,k=p+=C)|k==0x6B9400B8,i=p=''))&&o

Try 10 random test cases online!

How?

Replacement letters

All letters in the original paragraph appear at least twice, except j, E, I and M that appear only once and may disappear in the modified paragraph.

That's why we do:

[...s + 'jEIM'].some(c => ...)

This way, it is guaranteed that each possible replacement letter is tried.

Hash

Using a built-in hash would be rather lengthy in Node:

require('crypto').createHash('md5').update(string).digest('hex')

Instead of that, we use the following custom 32-bit hash:

Buffer(string).map(c => k = k * 99 ^ c, k = 0)

This was (rather painfully) tested against all possible inputs.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Interesting that a 32-bit hash succeeds here. The number of possible two-character changes is 1265169625, which as about 29% of 2^32, so it comes out close. But I guess you have more wiggle room because your hashes actually use more than 32 bits due to truncating before multiplying by 97 rather than after. \$\endgroup\$ – xnor Mar 10 at 12:17
  • \$\begingroup\$ @xnor I've now tested the formula k=k*N^c for all \$N\in[1..99]\$. The only working values are \$97\$ and \$99\$. \$N=95\$ was promising as the decimal representation of the hash value was one byte shorter, but it eventually failed. \$\endgroup\$ – Arnauld Mar 10 at 19:21
  • \$\begingroup\$ I just remembered this question of yours, which makes me wonder if ideas here can improve your answer there. \$\endgroup\$ – xnor Mar 27 at 22:26
  • \$\begingroup\$ Since my challenge has a similar premise to yours, I was probably inspired by it without realizing. So thanks for the idea! \$\endgroup\$ – xnor Mar 27 at 22:32
5
\$\begingroup\$

Perl 5 -MDigest::MD5=md5_base64 -F, 86 bytes

map{//;for$j(a..z,A..Z){$_=$j;(aNCL7lqAQsi7llQYWh7r8A eq md5_base64@F)&&say@F}$_=$'}@F

Try it online!

Brute force method. Runs each character position through all possibilities until it finds that the md5 checksum matches the original message.

Proof that no other single character change matches the checksum.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Did you check that the md5 sum doesn't have any collisions for the inputs in this challenge? \$\endgroup\$ – Luis Mendo Mar 9 at 11:27
  • \$\begingroup\$ @LuisMendo Yes. \$\endgroup\$ – Xcali Mar 9 at 16:46
  • \$\begingroup\$ I suggest you include that information in the answer text. Without that it's not guaranteed that it works \$\endgroup\$ – Luis Mendo Mar 9 at 17:55
  • \$\begingroup\$ As I noted on Jonathan Allan's answer, you'd actually need to check that no two-character change gives the same md5, since you're looking at one-character changes from the input which already has a one-character change. Probabilistically, this is almost certainly true with a 64 bit hash. \$\endgroup\$ – xnor Mar 10 at 13:56
4
\$\begingroup\$

C (gcc), 181 163 bytes

n,*R=L"[z@z4zp4y j,-#3#mu7qĘddė|h0\"k5&j4Đzm7ſ4sM6~0=a",u,v,x,y;f(char*s){for(n=529;n--;s[n]^=u&v)for(y=23,u=R[n/y+y],v=R[x=n%y];y--;u^=s[n-x+y])v^=s[23*y+x];}

Try it online!

-13 bytes thanks to @ceilingcat using the L-string trick. -5 bytes by moving the remaining local variables to the global scope; it doesn't matter if they are int or char because the ultimate destination is s[n]^=u&v, i.e. assignment to char.

A small improvement over Mitchell Spector's C answer. Instead of keeping track of which row and column have the typo, this one computes for every char the XOR-sums of its own row and column. If both are nonzero (they are necessarily equal), correct the current cell (which is the only offending cell) right away.

Commented

// declare global(?) variables n,u,v,x,y
// and initialize *R to point to the XOR hash array
n,*R=L"[z@z4zp4y j,-#3#mu7qĘddė|h0\"k5&j4Đzm7ſ4sM6~0=a",u,v,x,y;

// the function: takes char array and modifies it in place
f(char*s){
  // loop over first 529 chars backwards...
  for(n=529;n--;s[n]^=u&v)
    // loop over the chars on the same row/col as n,
    // initialize u=row hash, v=col hash
    for(y=23,u=R[n/y+y],v=R[x=n%y];y--;
      // collect XOR sums of row/col
      u^=s[n-x+y])v^=s[23*y+x];
    // at this point, go back to s[n]^=u&v
    // i.e. fix the typo if both sums are nonzero
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice golfing :) \$\endgroup\$ – Mitchell Spector Mar 9 at 7:18
4
\$\begingroup\$

PHP, 91 bytes

for(;($a=$argn)[$i];$i++){for($j=9;++$j<123;crc32($a)!=3603504069?:die($a))$a[$i]=chr($j);}

Try it online!

Brute force version, actually checking with replacing each letter with all ASCII between codes 10 and 122 (many useless checks, but it saves bytes for example initializing $j to 9 instead of 64, those results can't be positive anyway)

As noted by @LuisMendo and @PeterCordes (thanks), this works because crc32 can reliably detect every burst of up to 32 bit errors, and in the ASCII-encoded input, replacing a character will cause a burst of 14 (7*2) bit errors at most.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @LuisMendo thanks for this precision, adding it to the answer! \$\endgroup\$ – Kaddath Mar 9 at 13:14
  • 2
    \$\begingroup\$ Phrasing: CRC32 can detect some longer errors, but I think the key point here is that it can detect every possible burst of up to 32 bit-errors. Or that it can reliably detect a burst of up to 32 bit errors. (And that a wrong replacement attempt will have up to 2x 7 = 14 bit errors; that's the harder criterion for false positives.) \$\endgroup\$ – Peter Cordes Mar 10 at 8:40
2
\$\begingroup\$

APL (Dyalog Unicode), 94 bytes

g←252|1⊥⊢⍪⎕AV⍳⊣
252|⊢+0,⍨∘(,'⊂⍷≠Eæ×(í/7Ãs·¨\=Ш⍎ëáØ@'∘g∘.⌊⍨'#⌿O⍒`=~{└⊤Üã/cëÖ¶⌹⌹bð'g⍉)23 23⍴-

Try it online!

Uses the vector of Unicode codepoints as the I/O format. Otherwise it would cost me 11 bytes to convert from/to strings:

APL (Dyalog Unicode), 105 bytes

g←252|1⊥⊢⍪⎕AV⍳⊣
⎕UCS 252|46,⍨∘(,-+'⊂⍷≠Eæ×(í/7Ãs·¨\=Ш⍎ëáØ@'∘g∘.⌊⍨'#⌿O⍒`=~{└⊤Üã/cëÖ¶⌹⌹bð'g⍉)23 23⍴-∘⎕UCS

Try it online!

Uses the row/col checksum approach as in Mitchell Spector's C answer. Because bitwise XOR is not a built-in function in APL, I had to use plain sum and negation instead.

How it works

g←252|1⊥⊢⍪⎕AV⍳⊣  ⍝ Auxiliary function: checksums g matrix → checksum vector
          ⎕AV⍳⊣  ⍝ Convert string written in APL SBCS to integer
        ⊢⍪       ⍝ Append the checksum vector at the bottom of the matrix
      1⊥         ⍝ Column-wise sum
  252|           ⍝ Modulo 252

⍝ Main function: Correct the typo based on checksum
252|⊢+0,⍨∘(,'⊂⍷≠Eæ×(í/7Ãs·¨\=Ш⍎ëáØ@'∘g∘.⌊⍨'#⌿O⍒`=~{└⊤Üã/cëÖ¶⌹⌹bð'g⍉)23 23⍴-
23 23⍴-  ⍝ Negate each element and reshape into 23x23 matrix, discarding the last '.'
(...)    ⍝ Pass to the inner tacit function...
'...'g⍉    ⍝ Check rows against the row checksums
∘.⌊⍨       ⍝ Outer product by minimum (rows and columns reversed) with...
'...'∘g    ⍝ Check columns against the column checksums
           ⍝ Result = all-zero matrix except at the typo (difference mod 252)
,          ⍝ Flatten the result
0,⍨∘     ⍝ Append a zero to account for the last '.'
252|⊢+   ⍝ Fix the typo using the offset
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Java 10, 140 139 137 bytes

s->{var r=s;for(int i=0;;i++)for(var c='z';c>65;c-=c==97?7:1)if((r=s.substring(0,i)+c+s.substring(i+1)).hashCode()==0xA89D0862)return r;}

-2 bytes thanks to @ceilingcat.

Try it online.

Explanation:

Also uses an hash like most other answers. The hash of the expected text is -1466103710. All other possible double replacements of letters cause no collisions, which has been verified locally with this test program. (Obviously times out on TIO since it has to do \$(52\times 530)^2=759\text{,}553\text{,}600\$ iterations, including calculating the hash-code and substituting characters in each iteration. It takes between 8 and 9 minutes locally.)

s->{                    // Method with String as both parameter and return-type
  var r=s;              //  Result-String (starting at the input to save bytes)
  for(int i=0;;i++)     //  Loop `i` upwards from 0 indefintely:
    for(var c='z';c>65; //   Inner loop over the characters `c` in the ASCII range ['z','A']
        c-=c==97?7:1)   //   skipping the characters "`_^]\[" between 'a' and 'Z':
      if((r=s           //    Set `r` to the input-String,
             .substring(0,i)+c+s.substring(i+1))
                        //    with the `i`'th character replaced with `c`
         .hashCode()==0xA89D0862)
                        //    And if its hash-code is -1466103710:
        return r;}      //     Return `r` as result
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Regarding the hash collision test, as I commented to Jonathan Allan: "Is the hash enough that any change of two letters produces a different result? I think you need that so that an input with a one-letter change doesn't have a different one-letter change where the resulting two-letter change gives the same hash as the original text." \$\endgroup\$ – xnor Mar 10 at 12:09
  • 1
    \$\begingroup\$ Maybe I'm not clear on how your code is working. So the input to the function is some single-letter replacement \$a_n\$ of the original text \$e\$. As I understand, you iterate and try every single-letter replacement of the input string \$a_n\$, which produces strings that are two letters off from \$e\$. Then, if one of these two-letter changes from \$e\$ has the same hash as \$e\$, then you'd output it. \$\endgroup\$ – xnor Mar 10 at 12:53
  • 1
    \$\begingroup\$ @xnor Ah, now I understand what you meant. Hmm, you're completely right. I will delete for now and modify my collision program to verify it's (hopefully) correct. \$\endgroup\$ – Kevin Cruijssen Mar 10 at 12:56
  • 1
    \$\begingroup\$ @xnor Undeleted. Luckily for me, it was indeed valid. I've modified the test script (although it's too slow to run on TIO). \$\endgroup\$ – Kevin Cruijssen Mar 10 at 14:17
  • 2
    \$\begingroup\$ With a 32-bit hash, you had about a 6% chance of bad collision, so you only needed a little luck, and looks like you got it :) \$\endgroup\$ – xnor Mar 10 at 14:25
2
\$\begingroup\$

C (gcc), 125 bytes

Note: my code includes 2 unprintable characters \x0c and \0x01 in the string literal which aren't visible in the snippet.

b,i,j,m,n;C(char*T){b=i=n=0;for(;i<10;b|=("N<Syr4Zd"[i]!=m)<<i++)for(m=j=0;T[j];n^=!i*T[j++])m^=(1&j>>i)*T[j];T[b]^=120^n;}

Try it online!

The ith character in the literal is the XOR of all the characters in the original text at positions whose ith bit is 1. The program performs the same XOR on the modified text. The computed value will be different iff the modified character is in a position with ith bit 1. This gives us all the bits of the modified character's position.

Finally, we modify the character such that the XOR of all characters is that of the original text(120).

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I was just thinking that the binary number magic trick I remember from when I was a child would make a good approach to this (if you haven't seen it, check out, for example, norsemathology.org/wiki/index.php?title=Binary_Cards ). But then I went online and saw that you already did it! I do like this method. \$\endgroup\$ – Mitchell Spector Mar 18 at 3:20
2
\$\begingroup\$

Charcoal, 52 49 bytes

θJ↨²⮌E =&%ce9KG*¬⁼§γΣEΦθ&μX²κ⌕γλι⁰§γ⁻²⁸ΣEθ∧⁻κⅈ⌕γι

Try it online! Link is to verbose version of code. Works with all printable ASCII, not just letters. I originally wanted to do a Hamming check on all of the letters in the input but I was too ill to implement that at the time and by the time I got better I realised that @GB's modular sums would suit Charcoal better anyway. Explanation:

θ

Print the input string.

E =&%ce9KG*

Loop over 10 partial sums. These characters are the result of cyclically indexing the appropriate sum from the correct input back into the predefined printable ASCII variable.

ΣEΦθ&μX²κ⌕γλ

Filter on the desired characters for this sum and take the sum of their indices within the predefined printable ASCII variable.

J↨²⮌...¬⁼§γ...ι⁰

Interpret those sums that don't match as a number in base 2 LSB first, and jump to that character, which will be the incorrect character.

§γ⁻²⁸ΣEθ∧⁻κⅈ⌕γι

Subtract the sum of all the other printable character indices from 28 which gives the index (modulo 95) of the current character.

@xnor's algorithm can be implemented in 42 bytes:

θ≔⁻⁵⁰⁹⁹⁸ΣEθ℅ιηJ÷⁻¹³⁴⁴⁷⁴²⁰ΣEθ×℅ικη⁰§γ⁺η⌕γKK

Try it online! Link is to verbose version of code. Works with all printable ASCII, not just letters, but fails if the input is correct (would cost 3 bytes to fix). Explanation:

θ

Print the input string.

≔⁻⁵⁰⁹⁹⁸ΣEθ℅ιη

Calculate the size of the error.

J÷⁻¹³⁴⁴⁷⁴²⁰ΣEθ×℅ικη⁰

Calculate and jump to the position of the error.

§γ⁺η⌕γKK

Correct the character that is in error.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Python 3, 364 bytes

Output is bz2 encoded. Input is ignored. Code contains unprintable characters, so here is the hex version. Utf-8 encoded version is 55 bytes regular code + 309 bytes compressed data. See commented lines in the header of the TIO link.

import bz2
lambda s:bz2.decompress(b'BZh91AY&SY\xd3\xaa\xfe\xfd\x00\x00(\x15\x80@\x05\x02"?\xf7\xff\xa00\x01F\n\x86\x82bI\xfa\x14\xf4&\x99\r\n\x00\x06\x80\x00\x04\xa6\x84\x9a\x9e\xd455<\xa6\x99\x19\x10o\xcf|b5oN"\x06V\xab\xd0\xa3\x8awA\xbb}\x8a=\xa6\xcc\x9b#\x1a\xcd\x94Q\x83%Lp\xc9-n\x99\xd9\xee\xb5\xbc\xb4xc\x1a\xeaz\x03\xe49*\x90\xc9E\xf8\xa1y\xb7q\xcb!O\xbeA\xf5\rj\xd9Vg2\xec\xe9&A\x08\xb0\x91\x0c\xde\x05_m\xeb.\xa8\x9a~\x0b?\xec\x0e+\x14\xf0q\x05\x19\xa3O\x84\xb0\xbb\xea\xb6\xc3d\xab\xa6\xa3\x1b\x02c\xd3\x8fE\x99F\xf8\xdf\x07\x95\xdam\x10\x1b!\xb0m\xd7m\xb9\xdf\x9d:&\x0e\x13\xa4{S\xa3\x9ao\x95\x98\r\x995#\xdb\xbb\x17\x1d`2\xd0\x1d7$\xb5E\xe1Y9\xf4u\xbd\xcc9\x01va\x0e\x12\x7fA\x06\xa6[\xceg>\x05\xc8T\xaf\x87\x1a\t\x18Hcq\x87\x04\xa2\xa5\xf8\xc2\x0643\xbci\x14\x14\xbe5\xd77\x99w\'\xba&\r\x19b\x1ck\x16\x10&v\xd0\xb9\xe1W\xc3\x82{\xbe\xdb-\x81\xb0\xac\xc8A\xfc]\xc9\x14\xe1BCN\xab\xfb\xf4').decode('ascii')

Try it online!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.