3
\$\begingroup\$

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)
\$\endgroup\$
  • 2
    \$\begingroup\$ What is meant by 97.5 % ? Is it measured by (their opinion of) code cleanliness, or is there a failing test case? \$\endgroup\$ – Simon Forsberg Jun 20 '15 at 14:16
  • \$\begingroup\$ From your description, it seems that the code does not work as intended since you don't get the result you want. While including the challenge description is already a big improvement, we can't reopen the question if the code does not work as intended to the best of your knowledge :/ \$\endgroup\$ – Morwenn Jun 22 '15 at 8:43
  • 2
    \$\begingroup\$ I'd consider 97.5% to be substantially working. As per the help center guidelines, unexpected edge cases are OK. \$\endgroup\$ – 200_success Jun 22 '15 at 9:03
  • \$\begingroup\$ @200_success I'd agree if this question was asking for a general review, but it seems to be specifically asking for us to hunt down the bugs. \$\endgroup\$ – Ben Aaronson Jun 22 '15 at 15:10
  • \$\begingroup\$ @BenAaronson As per our rules, answers can address any issues, not just the specific requests in the question. \$\endgroup\$ – 200_success Jun 22 '15 at 15:30
4
\$\begingroup\$

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)))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Oh lol yes that does seem easier. I think this solution "grew" as I tested it, and I could definitely simplify it by doing that. I'll try and work out if there was a specific reason why I didn't do that. \$\endgroup\$ – Robert Grant Jun 23 '15 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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