Edit - Code Golf Stack Exchange

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Rev

Required fields*

Error-correct text

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.

Answer*

# [C (gcc)], <s>260</s> <s>259</s> <s>247</s> <s>226</s> <s>223</s> <s>217</s> <s>215</s> <s>214</s> <s>198</s> 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!][TIO-k7mu9pru]

[C (gcc)]: https://gcc.gnu.org/
[TIO-k7mu9pru]: https://tio.run/##7VJNbxMxEL3nV4xaCSWNkxaaUonVqnDgUIlK0CMhlRyvk3V3d5z6o8kmlN/ADf4Nl/K7wti7LQXEiRtqDpuRPfP83psnBnMhtts62TtP3@zcfvmYH3zYKY6eXI5uP6@r4@/fRvbs@aeDlI/XL9ej9WJUwyUb7B7uVv746vZrlu0kIucGkBXMMc8ME2yVzLrhcM/2NjNtupjW6bPDBAeDRJz4FF8cMHOySg1zoe6FFpOej3HCRPjr1xNWpHVSUL@5SO243sN@MemJpi76OElC4fp@cpGukputQgcVV9i91irrdTYdiJzs@Ojw6STpwDJXpYTuXDrbtb0ewP4@nEuegUYJChfeQamo5A44OFXJDtBvE7@gZtAlJbEOg6/KUi9hWnIs4pQlBHB5C8SA5AAqIU2oKu6cwjnoWWxx0rphAwswIy7JT9jFoqxBGkPjQhsjhVOagDXYYacZIXh7P0Mjb00Q3g3AKJdwzUsv6aVemAgtN52b7SkSr4ZIhMulNjVwzOiRLDBrT5bK5cCJgxKxM6p6ryt6k5RYoSQKGeecLKXQVeWxbWUt60y6lnQDf6@B7u50oTO6BG6CFSJHdeXJP5eT8RL5lJZkZKlikVFxLYkZWZepuXK8hIw7DppOweN94y9cwuIRZWmHcMax/stlJGD99JIIBofbc0CtrGSNytzbhrWlaNUwDfsl8pkXMoPMm@id4WgrZW0AnxldxSVb7Q15Rbic5AgZZAzh9W8ePdDPY6LaK4K1XuTt26zN7h@5aOyy4QFaljO@tbrJmTbkGN45RpusohncyhCm1b9kQjxm4n/MxOljJh4z8SAT74Y/AA "C (gcc) – 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#mu7q030円dd",
 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;
 }

If this is an answer to a challenge…

…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one. Explanations of your answer make it more interesting to read and are very much encouraged.
…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.

More generally…

…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).

Draft saved

Draft discarded

Edit Summary*

Cancel

\$\begingroup\$ 198: y=23;f(char*s){char*R="\x17|h0\"k5&j4\x10zm7\x7f""4sM6~0=a[z@z4zp4y j,-#3#mu7q030円dd",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
– Bubbler

2020年03月09日 06:37:42 +00:00
Commented Mar 9, 2020 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
– Mitchell Spector

2020年03月09日 07:10:05 +00:00
Commented Mar 9, 2020 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
– Mitchell Spector

2020年03月11日 04:50:44 +00:00
Commented Mar 11, 2020 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
– ceilingcat

2020年03月11日 06:43:49 +00:00
Commented Mar 11, 2020 at 6:43
\$\begingroup\$ Strange. I’ve mostly used TIO for bash. \$\endgroup\$

Mitchell Spector
– Mitchell Spector

2020年03月11日 06:47:09 +00:00
Commented Mar 11, 2020 at 6:47

Add a comment |

How to Edit

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

How to Format

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or **bold**
indent code by 4 spaces
backtick escapes `like _so_`
quote by placing > at start of line
to make links (use https whenever possible)

<https://example.com>

[example](https://example.com)

<a href="https://example.com">example</a>
MathJax equations \$\sin^2 \theta\$

formatting help »
answering help »

MathJax help »

How to Tag

A tag is a keyword or label that categorizes your question with other, similar questions. Choose one or more (up to 5) tags that will help answerers to find and interpret your question.

complete the sentence: my question is about...
use tags that describe things or concepts that are essential, not incidental to your question
favor using existing popular tags
read the descriptions that appear below the tag

If your question is primarily about a topic for which you can't find a tag:

combine multiple words into single-words with hyphens (e.g. code-golf), up to a maximum of 35 characters
creating new tags is a privilege; if you can't yet create a tag you need, then post this question without it, then ask the community to create it for you

popular tags »