1
\$\begingroup\$

I am practicing python, and in order to brush up my skill, I am trying the programming contest site AtCoder's past problems.

Daydream

Basically, you are given an input string and have to output YES if the string is constructed with choices of 4 different words ('dream', 'dreamer', 'erase', 'eraser'), otherwise NO.

I implemented as following.

I am aware that there are much better solutions out there, but mine also should work. However, even though first 3 cases were accepted as answers, but other 15 cases fails, and I cannot figure out why my code could fail.

ddee = ('dream', 'dreamer', 'erase', 'eraser')

def match_and_move(s, t, i):
    """checks if string s starts with any of the 4 choices starting from index i"""
    if s == t:
        return True
    for word in ddee:
        if s.startswith(word, i):
            if match_and_move(s, t+word, i+len(word)):
                return True
    return False

S = input()
T = ''
print('YES' if match_and_move(S, T, 0) else 'NO')

What am I doing wrong here?

Any assistance would be appreciated.

Thank you in advanced.

EDIT :

Because this is programming contest site, I was not provided with the input file for the all 18 tests.
I just know that first 3 tests were marked 'AC - Accepted' and other 15 tests were marked 'RE - Runtime Error' without actual error being displayed.
I performed test on my own based on the requirements (as well as the example provided by them on the question page).
At least I know that this code is working as they intended even if it is partially.

EDIT 2 / Answer :

Since this question is closed, I cannot place a separate answer.

Further testing my code, I was looking further in to the constraints.

  • 1≦|S|≦10^5
  • s consists of lowercase English letters.

I prepared a string that is 7000 characters long 'dreamerdreamer...dreamer' which should return 'YES' as this is just a repeat of 'dreamer' which is one of the 4 phrases.

And I received following error.

RecursionError: maximum recursion depth exceeded in comparison

Which is self explanatory. (and is also something @VincentRG has suggested)

import sys 
sys.setrecursionlimit(10**6) 

By adding above, on my PC this program is working with this large input. 5 more problems are solved on the website, and 10 of the website's test were returning Memory Limit Exception, which also make sense.

\$\endgroup\$
2
  • \$\begingroup\$ I have edited my post. I do know that the code is working as I intend it to work. I am only provided with limited error report 15 cases that failed \$\endgroup\$
    – ghints
    Feb 2 '20 at 17:43
  • \$\begingroup\$ Thank you very much greybeard for your edit. It is much clearer than how I was writing! \$\endgroup\$
    – ghints
    Feb 2 '20 at 19:42
2
\$\begingroup\$

It seems to be fine. What are the failing cases' inputs? Following your link I only see 3 cases which should indeed work.

However, I see there's a limitation of time and memory usage at the beginning, and that S max length is 100000. Your code might for example exceed maximum recursion depth. I think a simpler solution would be to use regex. For example (and I added a long sample):

import re
import random

regexPattern = "^(dream(er)?|eraser?)*$"
sampleList = [
    "erasedream",
    "dreameraser",
    "dreamerer"]

# just add a looooooong sample
longSample = ""
mandatoryWords = ["dream", "dreamer", "erase", "eraser"]
while True:
    addWord = mandatoryWords[random.randint(0, 3)]

    if len(longSample) + len(addWord) > 100000:
        break
    else:
        longSample += addWord

sampleList.append(longSample)

for sample in sampleList:
    match = re.fullmatch(regexPattern, sample)

    if match != None:
        print("YES")
    else:
        print("NO")

outputs

YES
YES
NO
YES
\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much for your answer. Unfortunately, I guess due to the fact that it is programming contest, I do not get to see the solution's input file :(. \$\endgroup\$
    – ghints
    Feb 2 '20 at 8:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.