# CodeJam 2009 Qualification C

This time we’ll focus on Qualification C problem, entitled Welcome to Code Jam.

So you’ve registered. We sent you a welcoming email, to welcome you to code jam. But it’s possible that you still don’t feel welcomed to code jam. That’s why we decided to name a problem “welcome to code jam.” After solving this problem, we hope that you’ll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you’re probably wondering why it’s there. But if you read it very carefully, you might notice that we have written the words “welcome to code jam” several times: 400263727 times in total. After all, it’s easy to look through the paragraph and find a ‘w’; then find an ‘e’ later in the paragraph; then find an ‘l’ after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase “welcome to code jam”.

To be more precise, given a text string, you are to determine how many times the string “welcome to code jam” appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], …, input[s[18]] is the string “welcome to code jam”.

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Yeah… like it would make any difference, besides the trimmed result… 😛

Here’s our code:

```# "Constants" - gotta be careful because there's no native solution in python
target = "welcome to code jam"
nullify= '-'

# Our "solve for X" function
def rec(line, pointer, letterIndex, times):

#If our letterIndex turned out the same as our phrase length, we can count
if (letterIndex == len(target)-1):
times += 1
return times

#If not, we've got work to do. While we still have the current expected letter on the string, do
while line[pointer:len(line)].count(target[letterIndex+1]) > 0:
#print "Searching letter %c, %d occurrences left on line \"%s\" from position %d" % (target[int(letterIndex+1)], line[pointer:len(line)].count(target[letterIndex+1]), line, pointer)

#Go look for the next letter, from where the current letter is
times = rec(line, line.index(target[letterIndex+1], pointer, len(line)), letterIndex+1, times)
#"Erase" our current letter position, so we don't search it again from here
line = line[:pointer]+line[pointer:len(line)].replace(target[letterIndex+1], nullify, 1)

return times

line = raw_input()
cases = int(line)

# Solve test cases
for i in range(cases):
line = raw_input()

times = 0
letterIndex = -1
pointer = 0

times = rec(line, pointer, letterIndex, times)

# Prints only last 4 digits
fnum = "%04d" % times
print "Case #%d: %s" % (int(i+1), fnum[max(0,len(fnum)-4):len(fnum)])

exit()
```

I’ve added comments on the code to describe what it does (I love command cascades, as you can see with all these connected string splits), but essentially: