26
\$\begingroup\$

Python string parsing has quite a few edge cases. This is a string:

"a"

Putting 2 strings immediately after each other implicitly concatenates them, so this is also a string:

"a""a"

However, if you put 3 quotes in a row, it will create a "triple quoted string" which can only be ended by another 3 quotes in a row. A triple quoted string can contain other quotes. These quotes will not end the string unless there are 3 of them. Thus this is valid:

"""a"a"""

Of course, you can combine these together, so this is a valid string:

"""a""""a"

And this:

"""""aaa"""""""""

3 quotes in a row outside a string always starts a triple quoted string, even if such a string would be invalid. There is no backtracking.

A string is not valid if:

  1. Any a appears outside of a string literal (would get SyntaxError: invalid syntax in python) OR
  2. The end of the sequence is inside a string literal (would get SyntaxError: unterminated string literal (detected at line 1) in python)

Your task

Given a string containing 2 distinct characters, one representing a double quote and another representing the letter "a" (most letters except b, u, r, and f would work exactly the same, you don't need to concern yourself with that detail), determine if it would be a valid python string, or invalid syntax.

You do not need to consider single quotes or how double and single quotes normally interact.

An array of booleans or an array of bytes would also be a valid input method. Thus some valid representations for "a" include $2$, [0,1,0], or [False, True, False].

This is , shortest answer wins.

Test Cases

Truthy Falsy
"a" (1-1) "a (1)
"a""a" (1-2-1) "a"a" (1-1-1)
"""a"a""" (3-1-3) ""a"a""" (2-1-3)
"""a""""a" (3-4-1) """a"""a" (3-3-1)
"""""aaa""""""""" (5-9) """""aaa"""""""" (5-8)
"""""""""""" (12) """"""aaa""""""""" (6-8)
"a""a""a""a" (1-2-2-2-1) """" (4)
"a""" (1-3) a
"" (2) """a" (3-1)
"""""" (6) """"""" (7)
"""""""" (8) a"""""" (6)

eval or exec or ast.literal_eval would be valid answers, though I hope to see more creative python answers as well.

\$\endgroup\$
13
  • \$\begingroup\$ Can the input have any two distinct characters, or can we restrict ahead of time which characters are used? \$\endgroup\$ Oct 28, 2022 at 15:25
  • 1
    \$\begingroup\$ Suggested test-case "a""""a""". \$\endgroup\$ Oct 28, 2022 at 15:44
  • 1
    \$\begingroup\$ @mousetail Sorry, "a""""""" (1-7) (truthy) is indeed already covered by """""aaa""""""""" (5-9). It's a test case where we have an open single-quote when the prefix is a""""""" (so single closing quote + open&closing triple quotes). (I've deleted my comment above.) \$\endgroup\$ Oct 28, 2022 at 16:28
  • 3
    \$\begingroup\$ I think the spec could be clearer that (if I understand right), Python identifies triple quotes greedily, and does not do any backtracking on a failed parse, so that, four example, four quotes are taken as a triple quote followed by a single quote (invalid) and not as two pairs of singles quotes (valid). \$\endgroup\$
    – xnor
    Oct 28, 2022 at 21:34
  • 2
    \$\begingroup\$ "one representing any alphanumeric character" - this is not entirely correct, as some letters can be used as string prefixes - e.g. b"" is a valid string. Maybe you should simplify to "one representing a" \$\endgroup\$
    – pxeger
    Oct 29, 2022 at 5:44

15 Answers 15

11
\$\begingroup\$

Python, 57 bytes

lambda s:not re.sub(r'("""|"(?!"")).*?\1','',s)
import re

Attempt This Online!

Python 3.11, 53 bytes

lambda s:not re.sub(r'("("")?+).*?\1','',s) 
import re

This requires Python 3.11 which that scandalously outdated ato does not support ;-P

\$\endgroup\$
0
7
\$\begingroup\$

Retina 0.8.2, 23 22 bytes

^(?>("(?>""|)).*?\1)+$

Try it online! Link includes test cases. Explanation:

^

Match must start at the beginning of the string.

(?>...)+$

After each quoted segment is matched, it cannot be backtracked and reevaluated. Instead, further quoted segments must be matched until the end of the string is reached.

("(?>""|))

Three quotes must be matched if possible, otherwise one. This decision cannot be changed later.

.*?\1

Match the closing quote(s) as early as possible.

Edit: Saved 1 byte thanks to @Mukundan314.

\$\endgroup\$
1
6
\$\begingroup\$

C (GCC), 132 130 109 108 bytes

-12 bytes thanks to @ceilingcat

-9 bytes thanks to @jdt

-1 bytes thanks to @c--

#define T bcmp(s,"\"\"\"",n)
n;g(char*s){for(n=3;~n;n-=2)if(!T){for(s+=n;T**s;s++);return*s&&g(s+n);}n=!*s;}

Try it online!

Note: 3 bytes can be shaved by changing the quote char.

\$\endgroup\$
0
5
\$\begingroup\$

Jelly, 25 bytes (no built-in); 2 bytes (built-in)

Built-in

The two-byte built-in ŒV (evaluate Python code) works as a full program when given the raw input enclosed in ''' - the exit code identifies the result: \$0\$ if valid, \$1\$ if not.

Aside: The zero-byte program, when given the raw input, will actually give the evaluated string if valid, or the input if not. However, this does not conform with defaults.

Non built-in

Ạ3ƤḢḤ‘ɓẠ⁹ƤḢ×TƊḟḶ}+Ḣ
ḊÇ¡ÐL

A monadic Link that accepts a list of \$1\$s ("s) and \$0\$s (as) and yields an empty list (falsey) if valid or a non-empty list (truthy) if not.

Try it online! Or see the test-suite.

How?

Ạ3ƤḢḤ‘ɓẠ⁹ƤḢ×TƊḟḶ}+Ḣ - Helper Link, prefix length that may be removed: list of 1s and 0s, L
 3Ƥ                 - for overlapping infixes of length 3:
Ạ                   -   all?
   Ḣ                - head -> 1 if L starts with three 1s, 0 otherwise
    Ḥ               - double
     ‘              - increment -> 3 if L starts with three 1s, 1 otherwise
      ɓ             - new dyadic Link - f(L, Y=that)
        ⁹Ƥ          - for overlapping infixes of length Y:
       Ạ            -   all?
             Ɗ      - last three links as a monad - f(Z=that):
          Ḣ         -   head (alters Z) and yield
            T       -   truthy indices (of the altered Z)
           ×        -   multiply (vectorises)
               Ḷ}   - lowered range (Y) -> [0] or [0,1,2])
              ḟ     - filter discard (these invalid locations)
                 +  - add Y (vectorises)
                  Ḣ - head (the empty list yields 0)

ḊÇ¡ÐL - Main Link: list of 1s and 0s, L
   ÐL - repeat while results are distinct applying:
  ¡   -   repeat...
 Ç    -   ...number of times: call the helper Link - f(current L)
Ḋ     -   ...action: dequeue
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 59 bytes

Wθ≔⎇⌕θ"""∧∧¬⌕θ"⊖№θ"✂θ⊕§⌕Aθ"¹Lθ¹∧⊖№θ"""✂θ⁺⁶⌕✂θ³Lθ¹"""Lθ¹θ⁼θω

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for valid quotes, nothing if not. Explanation:

Wθ

Repeat until the input becomes the empty string (because all quoted substrings were successfully parsed) or zero (because an error occurred).

≔⎇⌕θ"""

If the input does not begin with """, then...

∧∧¬⌕θ"⊖№θ"✂θ⊕§⌕Aθ"¹Lθ¹

... it must begin with " and contain at least two ", in which case slice it after the second ", otherwise...

∧⊖№θ"""✂θ⁺⁶⌕✂θ³Lθ¹"""Lθ¹θ

... it must begin contain at leat two """, in which case slice it after the second """.

⁼θω

Output whether the input was valid.

\$\endgroup\$
4
\$\begingroup\$

Regex (Javascript/PCRE), 31 28 bytes

  • -3 bytes thanks to Neil and Mukundan314
^(""$|"a+"|"""("?"?a)*""")+$

Try it on regexr

Basically:

  • Empty single-quoted string may appear only at the end
  • A single-quoted string outside the end must contain at least one element, this makes it unambiguous with a triple quoted string. Since "stock" regex has no way to prevent backtracking there must be no ambiguity.
  • A triple quoted string may contain up to 2 quotes in a row. These quotes may not be at the end. If they where at the end they would end the string early. Unlike single quoted strings tripple quoted ones may be empty without introducing ambiguity.
\$\endgroup\$
2
  • \$\begingroup\$ I think "{0,2}a saves a byte over the use of alternations? \$\endgroup\$
    – Neil
    Oct 29, 2022 at 20:22
  • 1
    \$\begingroup\$ @Neil, two more bytes can be saved by doing "?"?a \$\endgroup\$ Oct 30, 2022 at 14:24
4
\$\begingroup\$

x86-64 machine code, 24 bytes

E2 03 6A 06 59 B0 14 AE 7B F6 18 D2 D2 C0 24 01 83 C9 03 00 D0 78 EE C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of a null-terminated byte string consisting of " and x in RDI, and returns 0 or 1 in AL. The starting point is after the first 2 bytes.


This uses a single-pass algorithm: it processes each character of the string in order. The validity condition can be checked by a DFA like this:

An incomplete DFA, with seven states S, N0, N1, N2, T0, T1, and T2, connected by quote transitions in that order. There is also a quote transition from T2 to N0, and x transitions from S and N1 to S and from T0, T1, and T2 to T0. The start state is N0. States N0 and N2 are accepting.

(Technically, to satisfy the most common definition of a DFA, we would need to fill in the missing transitions, pointing them to a sink state. But the program can easily return before the end of the string, so this is not a problem.)

We number the states 7, 6, 5, 4, 3, 2, 1 in the order shown, so that implementing the " transition is easy: subtract 1, and if the result is 0, change it to 6. The current state number is held in RCX.

The x character and the null terminator can be handled together, as follows:

N0/N2 Other
NUL Success Failure
x Failure S/T

The "S/T" case is implemented by bitwise-ORing the state number with 3, which changes it to 3 or 7 as appropriate.

In assembly:

q:  loop n          # (For ") Decrease RCX by 1, and jump if the result is not 0.
f:  push 6; pop rcx # (When it hits 0, or at the start) Set RCX to 6.
n:  mov al, 0x14    # Set AL to 0x14.
    scasb           # Read a byte from the string, advancing the pointer,
                    #  and set flags based on AL minus that byte.
    jpo q           # Jump if the sum of the bits is odd (true only for ").
    sbb dl, dl  # Subtract DL+CF from DL, making it 0 for NUL or -1 for x.
    rol al, cl  # Rotate AL left by the low byte of RCX, the state number...
    and al, 1   # ...and keep only the low bit, which is 1 only for state 4 or 6.
    or ecx, 3   # Bitwise-OR ECX with 3, changing 1–3 to 3 and 4–7 to 7.
    add al, dl  # Add DL to AL, making 1 for success, 0 for failure, -1 for S/T.
    js n        # Jump (to continue processing the string) if it's negative.
    ret         # Return.
\$\endgroup\$
3
\$\begingroup\$

05AB1E (legacy), 2 1 2 bytes

§g

-1 byte by changing an explicit evaluate as Python (.E) to an implicit one (§)
+1 byte because apparently the default is truthy/falsey when it's unspecified. I was under the impression two distinguished values were the default, unless truthy/falsey was mentioned specifically.

Input wrapped in a list (as-is, since 05AB1E uses "/""" for string-quotes as well).
Outputs 1 for truthy or nothing for falsey.

Try it online or verify all test cases

Explanation:

§   # Cast the (implicit) input to a string, which is implicitly evaluated as Python†
    # (if it was invalid Python, it will stop the program and output nothing)
 g  # Pop and push the length, to make the truthy cases explicit 1
    # (after which the truthy case is output implicitly with trailing newline)

† This only applies to the legacy version of 05AB1E, which is build in Python. In the new version of 05AB1E (build in Elixir), this wouldn't work.


05AB1E, 34 bytes

ΔU17SbεXr¡D¬õQ©sg3@*i¦¦yýëX}}®è}õQ

Less boring approach without Python eval. Uses 1 instead of " in the inputs.
Not the shortest approach, but at least it works. 🤷

Try it online or verify all test cases.

Explanation:

Δ                   # Continue until the result no longer changes
                    # (using the implicit input-string in the first iteration):
 U                  #  Pop the current string, and store it in variable `X`
 17S                #  Push pair [1,7]
    b               #  Convert each to binary: [1,111] (these are the quotes to check)
     ε              #  Map over them:
      X             #   Push string `X`
       s            #   Swap so the current (binary) quote is at the top
        ¡           #   Split string `X` on this single/triple (binary) quote
         D          #   Duplicate the split list
          ¬         #   Push its first item (without popping)
           õQ       #   Check that the first item is an empty string
                    #   (which means string `X` starts with the current (binary) quote)
             ©      #   Store this 0 or 1 in variable `®` (without popping)
         s          #   Swap so the split list is at the top again
          g         #   Pop and push its length
           3@       #   Check that this length is >=3
                    #   (which means there is a matching closing quote)
              *i    #   If both checks are truthy:
                ¦   #    Remove the empty first string
                 ¦  #    As well as the second string
                yý  #    Then join it with the (binary) quote again
               ë    #   Else:
                X   #    Simply keep `X` as is
               }    #   Close the if-else statement
     }              #  Close the map
      ®             #  Push the last `®` result for the triple-quote
       è            #  0-based index this check into the pair
}                   # After the loop:
 õQ                 # Check if what remains is an empty string
                    # (after which the result is output implicitly)
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Not sure this complies with the defaults for decision-problem because only 1 is truthy in 05AB1E and this isn't giving two distinct, fixed outputs. \$\endgroup\$ Oct 28, 2022 at 18:52
  • 2
    \$\begingroup\$ @JonathanAllan Ah, I was under the impression any two distinct values was the default, and truthy/falsey if specified specifically. I've fixed it at the cost of 1 byte. \$\endgroup\$ Oct 29, 2022 at 12:55
  • \$\begingroup\$ @KevinCruijssen wait does it mean mine is wrong too? \$\endgroup\$
    – DialFrost
    Oct 30, 2022 at 2:00
  • \$\begingroup\$ @DialFrost Depends. I assume that Vyxal has an if truthy builtin. If [0] is truthy and passes that if and [] is falsey and does not, it's valid. In 05AB1E only 1 is truthy and everything else is falsey. \$\endgroup\$ Oct 30, 2022 at 10:34
2
\$\begingroup\$

Whython, 20 bytes

lambda s:eval(s)+s?0

Just getting the obvious out of the way.

Attempt This Online!

Explanation

Whython is mostly Python 3, but with a couple added features. Here, we use the rescue operator ?, which returns its left operand unless it raises an exception, in which case it returns its right operand instead. So if the argument s represents a valid string, eval(s) returns that string. Since the string can be empty, we concatenate s to it to make sure the result is nonempty and therefore truthy. If s is not a valid string, eval(s) errors, so we return 0 (falsey) instead.

\$\endgroup\$
2
\$\begingroup\$

GolfScript, 18 bytes

'"""'/['"']+2%{~}%

Try it online!

Split on ``` and eval each. Why 18 bytes though? :(

\$\endgroup\$
2
\$\begingroup\$

Regex (Perl or PCRE), 21 bytes

^(?>("("")?+).*?\1)+$

Test online on Regex101

The idea to use a backreference was inspired by @Neil's answer. I wrote the rest myself, but most of it ended up the same (probably because there's only one shortest way to express the algorithm, so two golfers will come to the same conclusions).

The Regex101 link uses the /gm flags in order to test multiple inputs at once – the problem as stated takes only a single input, so those flags aren't required and aren't part of the submission. (The existence of Regex101 establishes "regex" as a valid programming language by itself for the purposes of this site, as Regex101 acts as an interpreter for the language.)

Explanation

^(?>("("")?+).*?\1)+$
^                   $    Only the input as a whole matches
 (                )+     The input must consist of one or more of:
    (       )              a group named \1, which consists of
     "                     one double quote,
      ("")                 followed by two more double quotes
          ?+                 if they are present at that point in the input,
             .*            followed by any number of any characters,
               ?             the shortest number which leads to a match,
                \1         followed by another copy of \1,
  ?>                     but try only the first possibility for each block

Here, each block has its own \1, i.e. the delimiter is allowed to be different for each block.

Normally, regexes can backtrack if one potential parse doesn't work, to try a different potential parse. This solution therefore has to contain a couple of backtracking-blockers in order to ensure that if Python would reject a parse, we also reject the input rather than backtracking:

  • The + on "("")?+ means that if three double-quotes are present in a row at that point of the input, all three double-quotes must be included in \1, the variable that holds the delimeter; the regex engine isn't allowed to go back and try with just one. This ensures that """a" is correctly rejected, by preventing it being parsed as """a".
  • The ?> means that once the first possibility for a string in the input has been discovered, that must be used as a section when matching for the string as a whole; the regex engine isn't allowed to go back and try a different section. Because of the ? on .*?, sections are tested shortest to longest, so in this situation, the restriction imposed by ?> can equivalently be stated as "if any prefix of the input is a valid string, that prefix must be interpreted as the string, don't look for any longer prefixes that might also be valid". This ensures that """a"""" is correctly rejected, by preventing it being viewed as a" within triple quotes (because """a""" is a valid string that will be tested first).

Regex (Perl or PCRE, no backreferences), 25 bytes

^(?>""".*?"""|"a+"|""$)+$

Test online on Regex101

The thing that first inspired me to try answering this question with regex is that the set of allowed answers is a regular expression in the mathematical sense – you can solve it purely with a finite state automaton. Here's an answer that demonstrates that.

It's pretty similar to the previous solution, except that there are separate cases for the " and """ delimiters. When using """, the string can be empty; as in the previous answer, there's a backtracking-blocker (here ?>) present to ensure that only the first """ is matched. When using ", then the regex needs to disallow possibilities that would start with """. The only such possibility is an empty string followed by another string, so we ensure that either the string is nonempty (i.e. it contains a+, i.e. one or more a), or else that we have an empty string at the end of input (written in regex syntax as ""$).

As a side note, the fact that the set of answers is a regular expression in the mathematical sense implies that problem can also be solved without backtracking-blockers at all (meaning that no evaluation order hints are required either). However, the solution would likely be somewhat longer; the best I've found is ^("""("{0,2}a)*"""|"a+"|""$)+$ at 30 bytes.

\$\endgroup\$
1
\$\begingroup\$

Turing Machine Code, 147 bytes

0 " _ r 1
0 _ _ * haltA
1 " _ r 2
1 a _ r S
2 " _ r T
2 _ _ * haltA
S a _ r S
S " _ r 0
T a _ r T
T " _ r 3
3 " _ r 4
3 a _ r T
4 " _ r 0
4 a _ r T

Try it online!

The input string is valid iff the machine halts on state haltA. Note that the machine is basically a DFA.

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 84 bytes

n;S;g(char*s){n=bcmp(s,S="\"\"\"",3)?1:3;S=strstr(s+n,S+3-n);n=*s-34?!*s:S&&g(S+n);}

Try it online!

Require 32-bit or +5 byte long

\$\endgroup\$
0
\$\begingroup\$

Vyxal, 1 byte

Try it Online!

Python eval and inputs as a list. Returns a a list [0] if true and an empty list [] if false.

\$\endgroup\$
0
\$\begingroup\$

Python (built-in), 4 bytes (built-in), JS (TODO)

Because I'm evil and mousetail allowed me to.

exec

I'll add a C answer later. A C answer has already been added, so I'll add a JS answer by 19 November 2022.

Note: there are other answers that deserve your upvote, rather than this one.

\$\endgroup\$
12
  • \$\begingroup\$ You can post your C as a seperate answer \$\endgroup\$
    – mousetail
    Oct 29, 2022 at 15:06
  • \$\begingroup\$ I know, but I don't mind. \$\endgroup\$ Oct 29, 2022 at 15:12
  • 5
    \$\begingroup\$ That's the same as just exec. You don't need to create the lambda. \$\endgroup\$
    – The Thonnu
    Oct 29, 2022 at 15:54
  • \$\begingroup\$ Where else does the input come in through? \$\endgroup\$ Oct 29, 2022 at 16:13
  • \$\begingroup\$ @py3_and_c_programmer - 4 bytes, Try it online! \$\endgroup\$
    – The Thonnu
    Oct 29, 2022 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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