Will deliver some more posts today! 😀 Gotta hurry!

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

# Get header
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:

• Read phrase;
• Start from position 0 on recursive function;
• The function first checks if we’re looking for beyond the last “welcome to the code jam” letter; scores a point if so 🙂
• Not being at the end, checks if we have the expected letter on the phrase;
• If we have, branches to look for the next letter from the current letter and mark so it won’t be searched again;
  else, return how many times we could complete “welcome to code jam” with phrase letters so far.

Evolving the posts with small and clear code (at least for my standards) is the intention, guess I could make it this time. 🙂 Happy jammin’!