"The Ministry of Truth" challenge

Question

I'm trying to solve Codeeval's The Ministry of Truth challenge, and have hit 97.5% - is anyone able to spot where my code is missing the last 2.5%? The percentage indicates that one or more of their test cases is failing.

Here's the question - I've used the original wording because I'm worried if I give my version of the problem then it'll be one that misses that 2.5% edge case:

Challenge Description:

It's 1984, and you are working as an official at the Ministry of Truth. You have intersected a message subjected to Big Brother's doctrine.

Your task is to delete letters from certain "utterances" in order to replace them with an "utterance" approved by the Ministry.

A "word" is a single sequence of Latin letters, and an "utterance" is a sequence of multiple words and spaces.

To compare two "utterances," you have to replace all blocks of spaces with one space. Utterances are considered to be identical when resulting expressions match.

One line contains two different expressions separated by semicolon ';'. The first expression is the original utterance, and the second one is the utterance you want to get.

If you cannot fulfill the order, print a single line «I cannot fix history». Otherwise, output the original utterance by replacing the letters that must be erased with underscore and by replacing all blocks of white spaces with a single white space.

Sample input lines:

Higher meaning;Hi mean
this is impossible;im possible
twenty   two minutes;two minutes
Higher meaning;e

Sample output lines:

Hi____ mean___
I cannot fix history
______ two minutes
____e_ _______

Here's the code so far (Python 3):

import sys
import re


with open(sys.argv[1], 'r') as f:
    for line in f:
        line = line.strip()
        if not line:
            continue
        
        original, target = line.split(';')
        
        # Replace contiguous spaces with one space
        original = re.sub(r"\s+", " ", original)
        
        # Split target into targets
        targets = target.split()
        
        redacted, current_target, i, not_possible, space_next = '', 0, 0, False, False
        while i < len(original):
            if not space_next and current_target is not None and targets and len(targets) > 0 and len(original) >= i+len(targets[current_target]) and original[i:i+len(targets[current_target])] == targets[current_target]:
                redacted += targets[current_target]
                i += len(targets[current_target])
                
                if current_target < len(targets)-1:
                    current_target += 1
                    space_next = True
                else:
                    current_target = None
            
            elif original[i] == ' ':
                 redacted += ' '
                 space_next = False
                 i += 1
            else:
                redacted += '_'
                i += 1
        
        print('I cannot fix history' if current_target is not None else redacted)

Answer 1

For the overall program structure, I suggest:

• Using fileinput instead of explicitly using sys.argv[1]. Your program would automatically switch between sys.stdin and the named file.
• Breaking out the redaction logic into its own function, because each line is a self-contained problem with well-defined inputs and outputs.

To perform the redaction, I suggest using regular expressions, since this is just a pattern-matching problem. You've used the re module already, so you might as well go all the way.

import fileinput
import re

def redact(original, target):
    matched = False
    def replacement(m):
        matched = True
        s = list(m.string)
        for g in range(1, 1 + len(m.groups())):
            for i in range(m.start(g), m.end(g)):
                s[i] = ' ' if s[i] == ' ' else '_'
        return ''.join(s)

    # Replace contiguous spaces with one space
    original = re.sub(r"\s+", " ", original)
    pattern = re.compile(
        '^(.*?)' +
        '( .*?|.*? )'.join(re.escape(c) for c in target.split(' ')) +
        '(.*?)$'
    )
    result = pattern.sub(replacement, original)
    return 'I cannot fix history' if matched else result

if __name__ == '__main__':
    for line in fileinput.input():
        line = line.strip()
        if not line:
            continue
        print(redact(*line.split(';', 1)))

Answer 2

The challenge is very vaguely specified, and your code gives the correct output for all the examples. So far so good. We can't really know what the output should be in unspecified corner cases.

However, a common corner case is empty input. I notice you output «I cannot fix history» in case the right-hand-side of the input is empty. On the other hand the last example implies that when all words from right have been used, the remaining words from left are replaced with underscores. It would be logical to treat an empty right side as if the words were used up from start, ie. replace all words from left with underscores.

The code seems more complicated than necessary. Instead of looping with a character index i, split both sides into words, loop word by word, and use the in operator to check for substrings.