Comment Stripper - new problem 242

Hi,

I looked at one of the solutions posted and am suspicious that it would fail the following test case:

print('newline character: \n.')

Or in general any string in which a backslash is followed by something other than a quote or a backslash. Do there exist test cases like that in the tests?

Feels like my long lost cousin ... :)

Ah, my mistake - I only skim read the problem statement and didn't notice that. I figured that the disclaimers would essentially mean you wouldn't do something tricky like:

print(r'\\'') # this is a bit evil

In the test cases :-).

The reason I decided to do some of the later problems is that I occasionally talk to someone else that uses the site regularly and they'll describe the problems they're doing. After that I sometimes get the desire to do the problem we were talking about

gardengnome & HouseDwarf ...

Ah, just ran that in the interpreter and that is indeed not correct. I misunderstood the semantics of raw strings. It looks like they probably mean "accept a normal string literal but don't convert any of the escapes when converting it to its value". I thought they would have different definitions for what follows the backslash than normal string literals. I found it surprising, for instance, that:

print(r'\'')   # is fine - prints: \'
print(r'\\'')  # is not fine
print(r'\\\'') # is fine - prints: \\\'

In which case if the actual meaning of raw string is to process a normal string literal but don't process the escapes when converting it to its value then I can't think of much more tricky stuff that you can do... The only other trick I can think of is:

print(''' this's evil ''')

Which would break solutions naive to triple quotes...

With regard to the difficulty of this problem: the actual ask and format of the solution is a little unclear to me. Is the regexp supposed to match only the comment part, or a whole line with the comment being one of matched groups? What format should the replacement pattern take - a string, no quotes, single quotes, double quotes?

I thought about this problem a little more and wrote a solution that is triple quote aware (I've posted that as my solution now - I think it's quite readable for what it is). I've spent a while trying to think of anything that would break it, but I can't think of any special cases it can't handle. If anyone else can I'd be interested to know :-). Edit: to be clear - I'll be interested in any valid line of python that breaks my solution (other than triple quote strings across multiple lines). After messing around with raw strings a bit I think that my solution should handle them.

Oh, and by the way, because of the comment I decided to look up when K&R was written and when regex became a thing. K&R was written in 1978, and regular expressions were devised in the 1950s. I figured I'd look this up as I think of regular expressions as "mathsy" and C as "engineery", so thought regular expressions would be older. Personally, my main memory of regular expressions is automata theory and language hierarchies at university, where it had a very "theoretical" feel. I think that the kind of regular expressions that we use day to day aren't actually regular expressions as they add some operations which are strictly more powerful than formal regular expressions (depending on the implementation).

Also, when thinking about writing a regular expression to match this I considered that if the problem were too difficult to write a regular expression by hand it might be easier to write a DFA and then convert that to a regular expression. I didn't previously know whether there existed a DFA to RE conversion algorithm, but figured there probably did and that DFA and RE are equivalent. Anyway, I looked it up and found there do indeed exist DFA to RE conversion algorithms like this. I don't know how far down the regular expression rabbit hole you want to go on this site, but I think making a problem where the easiest way to generate a regular expression to solve the problem is writing a DFA to RE compiler could be fun XD.

I would not wish this problem on my worst enemy. Took me quite a bit of time to figure out the subtle flaw in my regex (needed [^\\'] instead of [^'] and [^\\"] instead of [^"]) On the bright side, my solution seems to be the shortest, though I didn't make it handle triple quotes, and maybe it's still wrong but no test case covers the flaw.

Fun fact: There exist poly-time algorithms for minimizing DFAs (and the minimal DFA for a regular language is unique). Meanwhile minimizing regexs is NP-Hard.

Vadim, Hi! Glad to hear from you again!

Ha-ha. Imagine someone left such a subtle flaw in production code to next generation of developers :)

But I wonder... About DFA... We now have problems on turing machine... though it is a bit larger than DFA, we can employ it for the original task (of stripping comments from C code)... And I remember there was some suggestion of problem related to TM from you also!

Obviously we should have a problem where we use a TM that can simulate an arbitrary TM on an arbitrary input sequence. :P

In other words, a problem where you have to create a Universal Turing Machine (UTM).

As for doing this comment stripping problem by implementing it as a TM... I would honestly think that doing this problem w/ a TM would be easier than doing it with Regex, as TMs are essentially nothing but DFAs which are able to have some specific side effects. And a DFA is the most natural solution to this comment stripping problem in my opinion (after struggling w/ making the regex I drew out the DFA and tried to base the regex off that).