Hello,
I’m going throught Near-Palindromes puzzle but it kind of hard to understand what is a Near-Palindromes exactly. Furthermore tests doesn’t help a lot because there are too many words and it’s impossible to know on which ones our algorithme fails.
Anyone can provide a clear explanation of what is a near palindrome ?
I was thinking to levenshtein length between the two half of a word but it doesn’t work…
Thanks
Swann
Levenshtein’s a good way to put it, though I wouldn’t want it on the statement, that’s exactly as detailed as it should be.
So if I’m not mistaken, a word A is a near-palindrome iff there exists a word B such that Lev_dist(A,B)=1 and B is a palindrome.
Just run through all strings near the original one.
I am also having a problem with this puzzle.
The ‘expected’ result is illogical.
Test case: Multiple words
My output: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001100000000010000000010010100000000000000000000000000000000000000000000010000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000010000000000100000000000000000000000000000000000000000001
Found: 0000000000000000000000000000000…00000000000000000000000000000000000000000000001000011000000000
Expected: 0000000000000000000000000000000…00000000000000000000000000000000000000000000001000011000000001
If you look at this substring in expected: ‘1000011’,
there are four zeroes.
But in my output there are five: ‘10000011’,
and there is no complaint about that. Very weird.
The result given in the test case tab also has five zeroes there.
I am unable to complete this puzzle.
It wouldn’t be the first time we observe quirks on large IOs, so take this with a grain of salt, but…
The correct output string for this test case is:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001100000000110000000010010100000000000000000000000000000000000000000000010000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000100000000000001000000000000000000000000000000000000000000000010000000000100000000000000000000000000000000000000000001
Your output string is:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001100000000010000000010010100000000000000000000000000000000000000000000010000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000010000000000100000000000000000000000000000000000000000001
It is wrong in 0-indexed positions 266 (false positive) and 422 (false negative).
At a cursory glance, I don’t see the string “1 four zeros 11” in the expected output string at all, so this is indeed a likely bug of the comparing program. (ping CG staff)
I have a similar issue with test case 5:
I don’t know for which word(s) I have output wrong digit(s) 
If your problems are on the tests, you can always copy/paste the input and expected output and compare offline, on your own hardware.
I’ll admit it is a major nuisance, though. Sorry I can’t do much more!
I was trying to say that the bug (similar to the one stated by Lupilum above) is preventing me from doing a meaningful comparison 
Yours doesn’t look so similar to Lupilum’s if you scratch the surface. The judge output is worthless in both of your cases. I wrote those tests, let me break the news first hand: a backslash or a null byte is not part of them.
But in his case we were able to compare the results anway by taking the 0s and 1s from the output pane and from the test list’s expected output, and compare them outside of the website.
That’s what I was suggesting you did too.
Thanks JBM. Sad that I can’t tell which 0s and 1s are incorrect by comparing my 0s and 1s and the expected 0s and 1s. Now I have to scan 850 words in test 5 manually…
Now if only we could come up with come invention to compare those 0s and 1s faster than by hand. That would be some kind of a revolution, wouldn’t it? 
In test #5, for instance, you can see clearly that the third word “ada” is supposed to be recognized as a near-palindrome.
I would say that qualifies as “zero letters away” from a palindrome in my book.
It would be nice to say more explicitely in the problem definition that palindromes qualify as near-palindromes. That would avoid some head scratching for those who designed an algorithm that carefully avoids recognizing palindromes 
That’s a debate we already had during puzzle approval, but you’re only having issues with it because you’re trying to read too much into it.
“ada” is a near-palindrome because it’s exactly one letter away from palindrome “adda”. Or “aa”. Or “aca”.
Being zero letters away from… anything, really, is completely beside the point.
So no, we’re not going to mention whether palindromes are near-palindromes or not, because their case is fully covered by the statement text already.
well, I wrote more complicated code just to make sure you needed exactly one change to reach a palindrome, but I suppose that was just one way to read the rules.
What’s preventing it from being exactly one change away from one of the palindromes I provided above?
Any palindrome is a near-palindrome, i.e. exactly one letter away from a palindrome: if it is of odd size, double (or change, or delete) the central letter; if it is of even size, add anything as central letter (or delete one of the two current central letters). There is no need to mention/clarify that in the statement as the problem solver is supposed to figure that out by himself I guess.
According to eggheads “a d-near-palindrome is a string of Hamming distance at most d from its reverse” so this official defintion indeed implies a palindrome is a d-near-palindrome for every d in [0, +inf[, and the problem asks to detect 1-near-palindromes, hereby called “near-palindrome” for brevity.
For mundane users, this might sound like saying a hit is considered a near miss though
FWIW, I wasn’t aware of “d-near palindromes” at time of problem setting, so calling them near-palindromes “for brevity” fits, but is historically inaccurate.
To be completely fair, this puzzle was set in a rush for other reasons.
Sorry, I didn’t mean to be rude and I apologize if I was.
I was just joking about what some people consider obvious while others don’t.
What would a brute force solution look like from your point of view?