[Community Puzzle] The Michelangelo Code

Puzzles
#14

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.

#15

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.

#16

Thanks! I have passed all validators now! appreciate it very much.

#17

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.

#18

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) …

#19

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
#20

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
#21

Based on your example you are not checking the distance between the letters.
You need to look for for evenly spaced letters.

Second test case:

To be or not to be that is the question Whe (ignored)

Thertisnoblerinthemindtosuffe
Rtheslingsandarrowsofoutrageo
Usfortuneortotakearmsagainsta
Seaoftroublesandbyopposingend
T

hem To die to sleep No more and by a sleep to say we end The heartache and the thousand natural shocks That flesh is heir to (ignored)

1 Like
#23

Hello,
I pass the 5 tests but the fourth validator takes too long in Python. An idea ?

#24

Look at this earlier comment:

#25

[quote="[Community Puzzle] The Michelangelo Code, post:19, topic:190722"]
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.
[/quote]

Yes, that’s why my step varies from 0 to len(text)//len(word). In your example, if the text is 400 with words of 4, I test the step from 0 to 100. Am I understanding correctly?

#26

Yes, you seem to understand the idea of not trying step sizes that are too large. But do you just generate all possible steps through the text once, or do you effectively rebuild all the possible steps for each word in the list?

#27

the uppercases are converted to lowercase not ignored :neutral_face:

#28

It is ignored in the sense that no matter how you change the case (uppercase/lowercase) of the input string, your code should still produce the same output.

1 Like
#29

It doesn’t say to ignore uppercase letters; it says to ignore capitalization.

1 Like
#30

i guess you re right just having it next to the character that will get removed confused me and i wasted some time trying to figured it out

#31

I pass all tests, but fails validator #1 and #4.
It’s very frustrating. Any hint?

#32

Describe what your current code does (don’t give full code, just describe it) so we can see what hints can be given.

#33

My code:
First I remove all non-alphabetical char from text, and lowercase remaining ones.
Then for each word:
find first letter of word in text
for each position found
given word length and remaining text length, compute all possible steps (space between letters of word)
for each ‘step’, check if word if found in text
Among all words found in text, print text with the longest one, capitalizing evenly spaced letters from word.

#34

Sounds all right to me, looks like there may be bugs in the implementation.

Try this custom case. It is similar to Validator 1 but not the same.

wartime advert in the midwest of the state
4
protection
width
bide
curfews

The output should be:

WartImeaDverTintH

1 Like