Obviously Santa Claus lives very secluded at the North Pole (or wherever he lives...). But he also needs the internet and television and all that and wants to stay well connected with his friends like the Easter Bunny. Well, it's not always easy living in such isolation. The messages he receives and sends usually contain some transmission errors...
So one day he thought that error-correcting codes (ECCs) would be a good idea to avoid these errors. In 2023, he became aware of Hadamard codes. Thanks to the sample implementations that the participants submitted, everything worked smoothly in the end! However, this time he wanted to do things more efficiently. He wants to implement systematic Reed-Solomon codes.
Analysis from the penultimate year showed that erasure errors were the most prevalent type of error in the messages. For this reason, you don't need to care about the Berlekamp-Massey algorithm or similar. There is a much simpler way to correct this type of error. He just cannot remember the name of the approach, but he thinks that you may know about it from a few days ago... Can you help him out?
Inspired from https://coord.info/GC18X1D.
The first input line contains the alphabet A (5 <= len(A) <= 1024), whose i-th symbol shall be encoded as the element i-1 in the finite field ℤ/pℤ, where p = len(A) is always prime.
The second line contains e,α,n,k,l. e is a character that was not in the alphabet A and whose purpose it is to indicate erasures ("erasure symbol"). α is the chosen primitive element from the previously mentioned ring for the encoding. You don't need to double-check whether it actually is a primitive element. n is the total length per message and k is the amount of actual message symbols within each message block. l is the amount of received message blocks.
Here follow l lines - each corresponding to one block of the message. Each block is obviously n characters long and contains k message symbols and n-k redundancy symbols (the message symbols are always the first k symbols in each line/block). You can assume that no other symbol than those in the alphabet A and the erasure symbol e appear in the message.
The programme should print the decoded message Santa Claus is looking for on the console - without any remaining erasure symbols and still with the redundancy symbols. You can assume that each message can be decoded and not too many errors have occurred during transmission.
Do not trim any "unnecessary" symbols from the output — refer to the example!
abcdefghijklmnopqrstuvwxyz .- ?,14,28,21,5 hallo lieber ??????? rdcq-ht nac?tsmann? ich ??ll ?vs?hc? zu w??hnacht?? ein? xfq?gh? playst???on. lie?e ? zz?akkh gruesse dei??????? qxh.sjc
hallo lieber weih- rdcq-ht nachtsmann. ich will .vsthcy zu weihnachten eine xfqighl playstation. liebe zzrakkh gruesse dein nico qxh.sjc
Please log in to submit a question...
Please log in to submit a solution...