Sticky Keyboard
Statement
Goal
Oh no, the keyboard is sticky and sometimes keys have repeated twice and sometimes keys haven't been activated after pressed. Not only that but the problem wasn't discovered until after some documents have been written.Fortunately, the problem isn't too bad and only happens once in a while. Instead of retyping all the documents you will write a program to correct the issue.
Your program will read a document and use the document as both the source to find correct words and to fix words with missing letters or letters that are duplicated by accident. Preserve the placement of all non-letters, like punctuation.
For example the following document
6
once upon a little while,
the moon came out and began to smile.
smile it-did all night long,
until the sun arose at dawn.
iit-did linger high in broad day light,
before under cloud it dd take flight.
Here we have two examples of 'it' spelt correctly to fix the one instance of 'iit'
and two examples of 'did' spelt correctly to fix the one instance of 'dd'
The incorrect word must have less instances than the number of instances the correct word. Therefore 'did' is not changed to 'dd', because 'did' has 2 instances and 'dd' only has 1.
Incorrect words have either 1 letter doubled (like 'iit') or 1 letter missing (like 'dd') but not both. For example 'dii' should not be corrected to 'did' if 'dii' existed in the above document.
Do not use words that are not in the document, for example do not hard code common English words. There is no guarantee that the words in the documents are English or any Earthly language. Also, the documents are precisely crafted such that they will only work if the only vocabulary that is used is from the document itself.
Input
line 1 : integer N number of lines
next N lines: Document lines
next N lines: Document lines
Output
N lines: Corrected document lines
Constraints
The document length is less than 20 lines and less than 256 characters per line. "Words" consist only of lower case ascii characters from a-z. For example isn't is considered 2 words isn and t because the ' cannot be inside a word for this puzzle.
Example
Input
1 dont fix it
Output
dont fix it
Tags
Machine learning
Difficulty
Medium
Test cases
If it aint broke Test
Input
1
dont fix it
Output
dont fix it
if it aint broke Validator
Input
1
it must be a fluke
Output
it must be a fluke
One repeat letterr Test
Input
1
if you dont succeed try again, try again, then try agaiin!
Output
if you dont succeed try again, try again, then try again!
One repeat letterr Validator
Input
1
one fish two fish red fish blue fiish.
Output
one fish two fish red fish blue fish.
Repeat earlier Test
Input
2
if you dont succeed
tryy try again then try again
Output
if you dont succeed
try try again then try again
Repeat earlier Validator
Input
2
one fishh two fish
red fish blue fish
Output
one fish two fish
red fish blue fish
Dropped letters Test
Input
5
if you see someting today that you dont
like, do the right thing and d nothing.
go on and see something you do like.
maybe on another day,
and maybe see another something
Output
if you see something today that you dont
like, do the right thing and do nothing.
go on and see something you do like.
maybe on another day,
and maybe see another something
Dropped letters Validator
Input
5
why, sometimes i beleve as many as six
impossible things before breakfast.
if it is impossible then sometimes
i dont believe and if it is as possible
as possible then sometimes i do believe
Output
why, sometimes i believe as many as six
impossible things before breakfast.
if it is impossible then sometimes
i dont believe and if it is as possible
as possible then sometimes i do believe
So much stickiness Test
Input
16
it was all very well to say "drink me,"
but th wise little aliice was not going
to do that in a hurry. "no, ill look
first," she said, "and see whether it
is marked poison or not." chapter 1,
down the rabbit-hole. "but it is no
use now," thought poor alice, "too
pretend to be two people! why,
theres hardly enough of me left
to make one respectable person!"
chapter 1, down the rabbit-hole.
"curiouser and curiouser!" cried
alice (she was so much surprised,
that for the moment she quite forgot
how to speak good english). chapter 2,
the pool of tears
Output
it was all very well to say "drink me,"
but the wise little alice was not going
to do that in a hurry. "no, ill look
first," she said, "and see whether it
is marked poison or not." chapter 1,
down the rabbit-hole. "but it is no
use now," thought poor alice, "to
pretend to be two people! why,
theres hardly enough of me left
to make one respectable person!"
chapter 1, down the rabbit-hole.
"curiouser and curiouser!" cried
alice (she was so much surprised,
that for the moment she quite forgot
how to speak good english). chapter 2,
the pool of tears
So much stickiness Validator
Input
13
it was all very well to say "drink me,"
but the wise little alice was not going to do that
in a hurry. "no, ill look first," she said,
"and see whether it is marked poison or not."
chapter 1, down the rabbit-hole.
"but it is no use now," thought poor alce,
"to pretend to be two people! why, theres hardly
enough of me left to make one respectable person!"
chappter 1, down the rabbit-hole.
"curiouser and curiouser!" cried alice (she was
so much surprised, that for the moment she quite
forgot how to speak good english). chapter 2,
the pool of tears
Output
it was all very well to say "drink me,"
but the wise little alice was not going to do that
in a hurry. "no, ill look first," she said,
"and see whether it is marked poison or not."
chapter 1, down the rabbit-hole.
"but it is no use now," thought poor alice,
"to pretend to be two people! why, theres hardly
enough of me left to make one respectable person!"
chapter 1, down the rabbit-hole.
"curiouser and curiouser!" cried alice (she was
so much surprised, that for the moment she quite
forgot how to speak good english). chapter 2,
the pool of tears
Zorbishian Alien Language Test
Input
15
vg jnf nyy irel jryy gb fnl "qevax zr,"
ohg gu jvfr yvggyr nyvvpr jnf abg tbvat
gb qb gung va n uheel. "ab, vyy ybbx
svefg," fur fnvq, "naq frr jurgure vg
vf znexrq cbvfba be abg." puncgre 1,
qbja gur enoovg-ubyr. "ohg vg vf ab
hfr abj," gubhtug cbbe nyvpr, "gbb
cergraq gb or gjb crbcyr! jul, gurerf
uneqyl rabhtu bs zr yrsg gb znxr bar
erfcrpgnoyr crefba!" puncgre 1, qbja
gur enoovg-ubyr. "phevbhfre naq
phevbhfre!" pevrq nyvpr (fur jnf fb
zhpu fhecevfrq, gung sbe gur zbzrag
fur dhvgr sbetbg ubj gb fcrnx tbbq
ratyvfu). puncgre 2, gur cbby bs grnef
Output
vg jnf nyy irel jryy gb fnl "qevax zr,"
ohg gur jvfr yvggyr nyvpr jnf abg tbvat
gb qb gung va n uheel. "ab, vyy ybbx
svefg," fur fnvq, "naq frr jurgure vg
vf znexrq cbvfba be abg." puncgre 1,
qbja gur enoovg-ubyr. "ohg vg vf ab
hfr abj," gubhtug cbbe nyvpr, "gb
cergraq gb or gjb crbcyr! jul, gurerf
uneqyl rabhtu bs zr yrsg gb znxr bar
erfcrpgnoyr crefba!" puncgre 1, qbja
gur enoovg-ubyr. "phevbhfre naq
phevbhfre!" pevrq nyvpr (fur jnf fb
zhpu fhecevfrq, gung sbe gur zbzrag
fur dhvgr sbetbg ubj gb fcrnx tbbq
ratyvfu). puncgre 2, gur cbby bs grnef
Zorbishian Alien Language Validator
Input
17
uf ime mxx hqdk iqxx fa emk "pduzw yq,"
ngf ftq iueq xuffxq mxuoq ime zaf
sauzs fa pa ftmf uz m tgddk. "za,
uxx xaaw rudef," etq emup, "mzp
eqq itqftqd uf ue ymdwqp baueaz
ad zaf." otmbfqd 1, paiz ftq
dmnnuf-taxq. "ngf uf ue za geq
zai," ftagstf baad mxoq, "fa bdqfqzp
fa nq fia bqabxq! itk, ftqdqe tmdpxk
qzagst ar yq xqrf fa ymwq azq
dqebqofmnxq bqdeaz!" otmbbfqd
1, paiz ftq dmnnuf-taxq. "ogduageqd
mzp ogduageqd!" oduqp mxuoq (etq ime
ea ygot egdbdueqp, ftmf rad ftq
yayqzf etq cgufq radsaf tai fa ebqmw
saap qzsxuet). otmbfqd 2, ftq baax ar
fqmde
Output
uf ime mxx hqdk iqxx fa emk "pduzw yq,"
ngf ftq iueq xuffxq mxuoq ime zaf
sauzs fa pa ftmf uz m tgddk. "za,
uxx xaaw rudef," etq emup, "mzp
eqq itqftqd uf ue ymdwqp baueaz
ad zaf." otmbfqd 1, paiz ftq
dmnnuf-taxq. "ngf uf ue za geq
zai," ftagstf baad mxuoq, "fa bdqfqzp
fa nq fia bqabxq! itk, ftqdqe tmdpxk
qzagst ar yq xqrf fa ymwq azq
dqebqofmnxq bqdeaz!" otmbfqd
1, paiz ftq dmnnuf-taxq. "ogduageqd
mzp ogduageqd!" oduqp mxuoq (etq ime
ea ygot egdbdueqp, ftmf rad ftq
yayqzf etq cgufq radsaf tai fa ebqmw
saap qzsxuet). otmbfqd 2, ftq baax ar
fqmde
Example Test
Input
6
once upon a little while,
the moon came out and began to smile.
smile it did all night long,
until the sun arose at dawn.
iit did linger high in broad day light,
before under cloud it dd take flight.
Output
once upon a little while,
the moon came out and began to smile.
smile it did all night long,
until the sun arose at dawn.
it did linger high in broad day light,
before under cloud it did take flight.
Example but different Validator
Input
7
once upon a little while
the moon came out and began to smile
smile i did all night long
until the sun arose at dawn
it didd linger high in broad day light
before under cloud it did take flight
potato
Output
once upon a little while
the moon came out and began to smile
smile it did all night long
until the sun arose at dawn
it did linger high in broad day light
before under cloud it did take flight
potato
Solution language
Solution
Stub generator input