Skip to main content
deleted 2 characters in body
Source Link
Mitch Schwartz
  • 5.9k
  • 1
  • 27
  • 26

Brainfuck, 177 bytes

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formatted:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Expects input without a trailing newline. Prints \x00 for false and \x01 for true.

Try it online.

This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current postfixsuffix, then move to the next postfixsuffix if a match is found, otherwise backtrack.

At the beginning, the string is reversed and a sentinel \x01 is placed at the end.

The tape is divided into 4-cell nodes. The memory layout of a node is:

c h x 0

where c is the character, h is a flag for whether the character is in the first half of a repeated prefix, and x is a flag to keep track of the current pair of characters being compared. The h flags stay in place while the x flags form a moving window.

If the string is pairable, the pointer lands next to the sentinel at the end of the main loop; otherwise, the pointer falls off the left side of the string while backtracking.

Brainfuck, 177 bytes

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formatted:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Expects input without a trailing newline. Prints \x00 for false and \x01 for true.

Try it online.

This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current postfix, then move to the next postfix if a match is found, otherwise backtrack.

At the beginning, the string is reversed and a sentinel \x01 is placed at the end.

The tape is divided into 4-cell nodes. The memory layout of a node is:

c h x 0

where c is the character, h is a flag for whether the character is in the first half of a repeated prefix, and x is a flag to keep track of the current pair of characters being compared. The h flags stay in place while the x flags form a moving window.

If the string is pairable, the pointer lands next to the sentinel at the end of the main loop; otherwise, the pointer falls off the left side of the string while backtracking.

Brainfuck, 177 bytes

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formatted:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Expects input without a trailing newline. Prints \x00 for false and \x01 for true.

Try it online.

This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current suffix, then move to the next suffix if a match is found, otherwise backtrack.

At the beginning, the string is reversed and a sentinel \x01 is placed at the end.

The tape is divided into 4-cell nodes. The memory layout of a node is:

c h x 0

where c is the character, h is a flag for whether the character is in the first half of a repeated prefix, and x is a flag to keep track of the current pair of characters being compared. The h flags stay in place while the x flags form a moving window.

If the string is pairable, the pointer lands next to the sentinel at the end of the main loop; otherwise, the pointer falls off the left side of the string while backtracking.

Source Link
Mitch Schwartz
  • 5.9k
  • 1
  • 27
  • 26

Brainfuck, 177 bytes

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formatted:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Expects input without a trailing newline. Prints \x00 for false and \x01 for true.

Try it online.

This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current postfix, then move to the next postfix if a match is found, otherwise backtrack.

At the beginning, the string is reversed and a sentinel \x01 is placed at the end.

The tape is divided into 4-cell nodes. The memory layout of a node is:

c h x 0

where c is the character, h is a flag for whether the character is in the first half of a repeated prefix, and x is a flag to keep track of the current pair of characters being compared. The h flags stay in place while the x flags form a moving window.

If the string is pairable, the pointer lands next to the sentinel at the end of the main loop; otherwise, the pointer falls off the left side of the string while backtracking.