5
$\begingroup$

Based on a comment currently on this answer, I have as much as A;~A; but this doesn't preclude palindromes.

What can I add to complete this search term?

$\endgroup$
2
  • 2
    $\begingroup$ I have a solution which works partially: instead of getting all matching words, you have to specify a length in advance. Is that acceptable? $\endgroup$
    – bobble
    Mar 21, 2022 at 19:58
  • $\begingroup$ @bobble yes it should be. If a more general solution comes along I may end up favouring that one potentially. $\endgroup$ Mar 21, 2022 at 20:21

2 Answers 2

4
$\begingroup$

Syntax

Even-length words of known length, using length 6 as an example:

A~B;B~A;|A|=3;|B|=3;!=A<B

or

AC~B;BC~A;|A|=3;|B|=3;|C|=0;!=A<B

Odd-length words of known length, using length 7 as an example:

AC~B;BC~A;|A|=3;|B|=3;|C|=1;!=A<B


Thought process

First, I'll reason through how to do this for even-length words. It's simpler to think about, and odd-length words are just a little extension at the end.

Even-length words

If we want to exclude palindromes we're going to have to leverage the "difference constraint" tool:

A difference constraint consists of an exclamation mark followed by an equals sign, followed by a sequence of variables. All these variables are constrained to have values different from one another.

Note the word "variables". The moment a tilde ~ is used to reverse something, you've created a compound pattern, which is different. This difference constraint part of the system must look like this:

!=AB

What do we want to be different? The start and end of the should-not-be-a-palindrome. Specifically, the first half should not match the reverse of the second half. Without losing any generality, let's have A be the first half and B the reverse of the second half. One of the words in the system will be A~B. The other, or the reverse of the first word, will be B~A. Now the system looks like:

A~B;B~A;!=AB

You may have noticed it seems we're right back to the original problem... palindromes are showing up in the list! This is because though we required the two halves of the word to not equal each other, we did not require the halves to be halves, at least not in the sense of "half the length". Therefore things like b·ob / bo·b d·eed / dee·d got through. To force halves to be halves, we need to constrain their lengths. Let's look at how to do that:

A length constraint consists of a sequence of variables bounded on both sides by vertical bar characters |, followed by an equals sign, followed by a length specification as described under ‘Qualified patterns’ above (without the colon).

The section it's referring to says:

A pattern can be further qualified by prepending a length specification. This can be:

  • a number followed by a colon, which allows only matches of that length, or
  • a number followed by a hyphen and a colon, which allows only matches of at least that length, or
  • a hyphen followed by a number and a colon, which allows only matches of at most that length, or
  • a number followed by a hyphen, another number and a colon, which allows only matches in the specified range of lengths.

Note that none of these allow for any sort of variables for the length. To force two lengths to be the same, we'll need to force them to both be equal to the same constant, as opposed to having them be equal to each other or both equal to some variable. Arbitrarily, let's make the word be of length 6, which means each half should be of length 3. The system now is:

A~B;B~A;|A|=3;|B|=3;!=AB

Almost there. Each pair of words is coming up twice in the results, as the values of A and B swap to form another legal solution. To fix this we'll leverage another part of the "difference constraints" section:

If a ‘less than’ symbol appears between two of the variables, the variable to its left is constrained to be ‘less than’ the variable to its right; and likewise, mutatis mutandis, for the ‘greater than’ symbol.

Either a < or > symbol will make it so only one assignment (of two strings to A and B respectively) is a legal solution. Arbitrarily picking < gives:

A~B;B~A;|A|=3;|B|=3;!=A<B

Odd-length words

Now to extend this pattern to work with odd-length words. To prevent palindromes here, it is sufficient to only look at the sections on either side of the central letter. The central letter of an odd-length word will always palindromically match itself anyways.

Most of the structure from the even-length word finder can stay. We just need to insert a letter into the middle of both A~B and B~A. However, we can't use . or its cousins which match any number of letters, because the central letter must be the same between both words. Introduce a new length-1 variable C and sneak it in between the halves:

AC~B;BC~A;|A|=3;|B|=3;|C|=1;!=A<B

A very similar pattern can be used to find even-length words. Adapt by forcing C to be of length 0 instead. This is equivalent to having C not be present at all, as in the previous even-length word finder-pattern.

AC~B;BC~A;|A|=3;|B|=3;|C|=0;!=A<B

$\endgroup$
1
  • $\begingroup$ You can combine even and odd with |C|=0-1, too $\endgroup$
    – justhalf
    Mar 22, 2022 at 8:16
6
$\begingroup$

With palindromes

Here's a different way to find all words that form a (possibly identical) word when reversed:

>&<
Look, it even makes a cute face!

Explanation

  • > matches a (multi-letter) word
  • & is a logical AND
  • < matches the reverse of a (multi-letter) word

Without palindromes

Here's a way to remove the palindromes:

>&<&(0*1|.0*1.|..0*1..|...0*1...)

Explanation

  • & is another logical AND
  • ( and ) enclose a group
  • 0*1 matches a word with different initial and final letters
    • 0 matches a letter
    • * matches a (possibly empty) string
    • 1 matches a letter different from 0
  • each | is a logical OR
  • .0*1. matches a word with different second and penultimate letters
    • . matches a letter (the two .s can be different, although it does not matter here)
  • ..0*1.. matches a word with different third and antepenultimate letters
  • ...0*1... matches a word with different fourth and preantepenultimate letters

Ultimately, this restricts the list to words that differ in two letters that are the same distance from either end, i.e., non-palindromic words. Observe that, barring further extension, it would fail to include a non-palindromic word that differed only in its fifth and propreantepenultimate letters, e.g., aaaabcaaaa. However, the longest words found are less than 10 letters long, so this suffices.

$\endgroup$

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.