https://www.codingame.com/training/easy/the-michelangelo-code
Send your feedback or ask for help here!
Created by @snoyes,validated by @mbbentley,@Coding_4_Fun and @David_Augusto_Villa.
If you have any issues, feel free to ping them.
Print the section of TEXT that contains the longest hidden WORD
How to resolve a tie when there are multiple hidden words found, and the hidden words have the same length?
The situation isn’t supposed to arise. Have you found such a case?
Needs better test cases please… I am able to pass all test cases but my script fails validator 03 “Be puntcual” (<-- typo btw) and 04 “Tempus fugit”
1 Like
At this moment, your current test cases may not have the tie situation. But you still have the responsibility to define the specification to close all loopholes. Test cases can be updated or added later by anyone. Coders often define their own test cases for debugging too. People adding a test case rely on your statement to determine what is acceptable.
You can specify such a tie situation is not allowed. You can define further rules to resolve any tie situation. Anything is better than doing nothing.
I have edited the description to specify there will be no such ties.
Fixed the typo.
What kind of failure? Do you get a different answer, or a timeout? Can you share your code?
I think it shouldn’t be in easy section ! It’s way more difficult than the other problems in this section.
Thanks for the reply. I’ve sent you my code and screenshots via direct message 
I was a bit afraid about the thousandesque numbers in the constraints because it means that you have to pay attention to your time complexity but actually it wasn’t that complicated.
What makes it definitively not too hard is that the step is always the same between letters of an hidden word.
Focusing on this makes the searching method quite straightforward.
I have added a test case to help you through validator 4.
I first failed only validator 1 because I interpreted evenly as the space between letters is an even number.
I had to look at the validator to understand that the spacing was odd.
Ha - I didn’t even notice all the tests happened to have spacing with the same parity! I’ve edited one of the test cases to avoid that.
1 Like
When it says “ignore punctuation, capitalization, and spacing” does that mean that after converting to all lowercase it’s safe to remove all characters in the TEXT and WORDs other than the letters a-z before starting to look for an answer? I’m doing that and pass all five test cases, but I fail “Be punctual” and “Tempus fugit” when I submit. You’re sure there are no ties, right? I’m sorting the WORDS by length descending before starting to look for an answer and stop immediately on the first match.
after converting to all lowercase it’s safe to remove all characters in the TEXT and WORDs other than the letters a-z
Correct.
You’re sure there are no ties, right?
Yes.
If you’ll share your code, I don’t mind running it to see if it’s an incorrect answer or an optimization issue that times out.
Thanks! I have passed all validators now! appreciate it very much.
I solved it first in Python and encountered no problems at all. But then my solution in C++ did get timeout with fourth validator. Working neither with the same algorithm as I used in Python, nor with a slightly optimized one. I think I have to ditch the C++ “string” data type for the “char *” and write my own search function that is based on Boyer-Moore string-search.
I tried with regular expressions - which works for small amount of words. But times out with the big list.
Any hint how to speed up the search, any special algo or optimization tip? (Many words start with same prefix or have the same length) …
There are several ways to pick out letters from the sample text - every second letter, every third letter, every fourth letter, etc. You want to build each of those only once, rather than building each one over again for every word in the list. You want to only consider arrangements that have a real chance - if the text is only 400 characters, and all the words in the list are at least 4 characters, then considering “every 200th letter” is a waste of time.
2 Likes
I am struggeling at the 2nd test:
Why is “RnottobEthatiSthequestIonwhethertiSnoblerinThemindtosuffertheslingsANdarrowsofoutrageousfortuneortotakearmsagainstaseaoftroublesandbyopposingendthemtodietosleepnomoreandbyasleeptosayweendtheheartaChE”
Not correct, but this is “ThertisnoblerinthemindtosuffertheslingsandarrowsofoutrageousfortuneortotakearmsagainstaseaoftroublesandbyopposingendT”
(missing the other upper case letters, as i can not see the full answer)
1 Like