Character insertion on letterboards

Question

You know those letterboards outside old-style cinemas which show upcoming films - perhaps you have a miniature one in your home?

If you've operated one, you'll know that you can normally add letters from either side of a row. But the slots (in which you slide letters) are thin, so it's impossible to swap the order of two letters once you've put them on.

Thus, you can't just go putting the letters on in any order - there's a restricted set of orders which actually work...

---

More formally:

Given a string \$ S \$, an ordered list \$ \sigma= (\sigma_i)_{i=0}^k \$ of characters, we will say \$ S \$ is \$\sigma\$-writable if it is possible to write \$ S \$ on a (initially empty) row of a letterboard, by adding (all) the characters from \$ \sigma \$, in order. Characters can be inserted on either side of the row, but can not pass over existing characters.

For example, ABBA is (B,A,B,A)-writable, by the following process:

                (empty row)
--> B           (insert B from left)
--> AB          (insert A from left)
    ABB  <--    (insert B from right)
    ABBA <--    (insert A from right)    

But it is not (A,A,B,B)-writable, since after inserting the initial two As, there is no way to put a B in between them.

Trivially, every \$ S \$ is not \$\sigma\$-writable if \$ \sigma \$ is not a permutation of the characters of \$ S \$.

---

The Challenge

Your task is to write a program which, given a string \$ S \$ of ASCII uppercase letters, and list \$\sigma\$, determines whether \$ S \$ is \$\sigma\$-writable. This is code-golf, so the shortest code wins!

You may assume \$ \sigma \$ has the same length as \$ S \$, although you may not assume it is a permutation of \$ S \$.

---

Test Cases

In the format \$ S \$, \$ \sigma \$ (as a string).

Truthy inputs:

ORATOR, OTRARO
SEWER, EWSER
COOL, COOL
CHESS, SEHSC
AWAXAYAZ, AXYAWAZA
SERENE, ERENES

Falsy inputs:

SEWER, EWSRE
BOX, BOY
ABACUS, ACABUS
SSSASSS, SSSSASS

Answer 1

Jelly, 8 bytes

ŒPUṚ;"Ɗi

Try it online!

Takes the letter-list \$\sigma\$ on the left and the target word \$S\$ on the right, returning a non-negative integer (truthy) if the word can be formed and 0 (falsy) otherwise.

Inspired by a brief exchange with caird coinheringaahing.

ŒP          Powerset of σ: list of all sublists of σ, not necessarily contiguous.
  U         Reverse each, then
   Ṛ        reverse the entire list,
    ;"Ɗ     and concatenate corresponding elements of the unmodified powerset:
ŒPUṚ;"Ɗ     it's ordered so that each sublist's complement is at the complementary index.
       i    Find the first index of S in that result, or 0 if not found.

Answer 2

J, ²² 18 bytes

e.((,.~,,.),.)/@|.

Try it online!

This builds up all possibilities recursively using a single reduction.

• @|. Since J evaluates from right to left, first we reverse our candidate list.
• ((,.~,,.) )/ This simply left-zips the next left element in the reduction with the results so far ,. and cats that , with the right-zip ,.~ of the results so far, thereby giving us all possibilities (since the only way to proceed is to left-append or right-append each next element to what we already have).
  • (( ),.)/ You might wonder about this extra ,.. This is a J technicality that arises because the zips require the right side to be a table. But in the first step of the reduction, the right side is an atom, and this extra ,. table-izes that atom. In later steps, when the right side is already a table, table-ize has no effect.

Answer 3

Factor + math.combinatorics, 64 bytes

[ all-subsets dup [ reverse ] map reverse [ prepend ] 2map in? ]

Port of Unrelated String's Jelly answer.

Try it online!

And my original answer:

---

Factor, 74 69 bytes

[ { ""} swap [ '[ _ prefix dup reverse 2array ] map-flat ] each in? ]

Try it online!

Iterative approach. Works roughly like this:

EWSER
^
E
----------------------
EWSER
 ^
WE EW
----------------------
EWSER
  ^
SWE WES SEW EWS
----------------------
EWSER
   ^
ESWE SWEE EWES WESE ESEW SEWE EEWS EWSE
----------------------
EWSER
    ^
RESWE ESWER RSWEE SWEER REWES EWESR RWESE WESER RESEW ESEWR RSEWE SEWER REEWS EEWSR REWSE EWSER

Then check if the first input is in this final list.

Answer 4

Python 3, 68 65 bytes

f=lambda s,x,a="":x and f(s,y:=x[1:],x[0]+a)|f(s,y,a+x[0])or a==s

Try it online!

Answer 5

Brachylog, 12 10 bytes

-2 bytes thanks to Fatalize

Ė|k↰;?tᵗpc

A predicate that takes the list of characters \$\sigma\$ as its input parameter and the string \$S\$ as its output parameter, succeeding if \$S\$ is \$\sigma\$-writable and failing if it is not. (Both \$\sigma\$ and \$S\$ are taken as Brachylog strings.) Try it online!

Explanation

The predicate is recursive:

Ė|k↰;?tᵗpc
Ẹ            Base case: input and output are both the empty string
 |           Or (recursive case):
   ↰         Call this predicate recursively on
  k          The input with its last character removed
    ;?tᵗ     Put the result in a list with the original input's last character
        p    Try both permutations of that list
         c   Concatenate the elements into a single string
             which must match the output parameter

Answer 6

JavaScript (ES6), 45 bytes

Expects two strings as (S)(sigma). Same recursive approach as 97.100.97.109.

S=>g=([c,...b],o)=>c?g(b,[o]+c)|g(b,c+o):o==S

Try it online!

Answer 7

Jelly, 12 bytes

Employs the inverse test of a post by pxeger - here.

JŒ!<ƝṢƑ$Ƈịċ⁸

A dyadic Link that accepts the sign, \$S\$, on the left and the deck of letters, \$\sigma\$, on the right and yields a positive integer (truthy) if possible or \$0\$ (falsey) if not.

Try it online! Or see the test-suite.

How?

First, this constructs a list of all permutations of the indices of \$S\$ which do not decrease after their first increase.

e.g. for \$S\$ of length four:

[1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[3, 2, 1, 4]
[4, 1, 2, 3]
[4, 2, 1, 3]
[4, 3, 1, 2]
[4, 3, 2, 1]

It then uses these to index into the deck, \$\sigma\$, to construct all the possible signs and counts the occurrences of the sign, \$S\$.

JŒ!<ƝṢƑ$Ƈịċ⁸ - Link: list of characters S, list of characters D (sigma)
J            - range of length (S) -> [1,2,3,...,length(S)]
 Œ!          - all permutations
        Ƈ    - filter keep those for which:
       $     -   last two links as a monad:
    Ɲ        -     for neighbouring pairs:
   <         -       less than?
      Ƒ      -     is invariant under?:
     Ṣ       -       sort
         ị   - index into (D) (vectorises)
           ⁸ - chain's left argument = S
          ċ  - count occurrences

Answer 8

Curry (PAKCS), 33 bytes

[]![]=1
(x:s?s++[x])!(t++[x])=s!t

Try it online!

Returns 1 for truthy, and nothing otherwise. It might return the same 1 multiple times for truthy result.

Answer 9

sclin, 26 bytes

^set"__ _`"Q rev"++"dip :?

Try it here! Port of Unrelated String's clever answer.

For testing purposes (use -i flag if running locally):

"ORATOR""OTRARO", "SEWER""EWSER", "COOL""COOL", "CHESS""SEHSC", "AWAXAYAZ""AXYAWAZA",.
"SEWER""EWSRE", "BOX""BOY", "ABACUS""ACABUS", "SSSASSS""SSSSASS",.
,` ( ,_. ) map
^set"__ _`"Q rev"++"dip :?

Explanation

Prettified version:

^set ( __ _` ) Q rev \++ dip :?

Assuming inputs S, σ:

• ^set powerset of σ
• ( __ _` ) Q duplicate, reverse each, reverse
• rev \++ dip prepend to powerset
• :? whether S is in resulting array

---

sclin, 38 bytes

1<>: _` ,_"\++ Q rev ++ +`"fold rev :?

Try it here!

For testing purposes (use -i flag if running locally):

"ORATOR""OTRARO", "SEWER""EWSER", "COOL""COOL", "CHESS""SEHSC", "AWAXAYAZ""AXYAWAZA",.
"SEWER""EWSRE", "BOX""BOY", "ABACUS""ACABUS", "SSSASSS""SSSSASS",.
,` ( ,_. ) map
1<>: _` ,_ "\++ Q rev ++ +`"fold rev :?

Explanation

Prettified version:

1<>: _` ,_ ( \++ Q rev ++ +` ) fold rev :?

Assuming inputs S, σ:

• 1<>: split σ into head and tail
• _` ,_ (...) fold fold over tail with head as initial accumulator...
  • \++ Q vectorized suffix
  • rev ++ vectorized prefix
  • +` concat prefixes and suffixes, thereby preserving flatness of accumulator
• rev :? whether S exists in resulting array of prefixes/suffixes

Answer 10

05AB1E (legacy), 7 bytes

æÂís+Iå

Port of @UnrelatedString's Jelly answer, so make sure to upvote him/her as well!
Inputs in the order \$\sigma,S\$. Outputs 1/0 for truthy/falsey respectively.

Try it online or verify all test cases.

Explanation:

æ        # Get the powerset of the (first) implicit input `σ`
 Â       # Bifurcate it; short for Duplicate & Reverse copy
  í      # Reverse each string in this reversed copy
   s     # Swap so the unmodified powerset-list is at the top of the stack
    +    # †Concatenate the strings at the same positions in the list together
     Iå  # Check if the second input `S` is in this list
         # (after which the result is output implicitly)

†: The + is the reason for the legacy version of 05AB1E (built in Python), which allows concatenation of strings and vectorizes. In the new version of 05AB1E (build in Elixir), the s+ should have been øíJ instead: try it online.

Answer 11

Japt, 11 bytes

Takes σ as the first input.

à
íiUmÔÔ øV

Try it

à\níiUmÔÔ øV     :Implicit input of strings U=σ & V=S
à                :Combinations of U
 \n              :Reassign to U
   í             :Interleave U with
     Um          :  Map U
       Ô         :    Reverse
        Ô        :  Reverse
    i            :Reduce each pair by prepending
          øV     :Does the resulting array contain V

Answer 12

C (clang), ^{134 132} 131 bytes

-1 byte thanks to ceilingcat!

o;*t;f(*r,a,b,s){r?t=r,s="",*t=0:0;*t|=!strcmp(a,s);for(int v=2,c=*(char*)b;v--&&c;f(0,a,b+1,o))asprintf(&o,"%s%s",v?s:&c,v?&c:s);}

Try it online!

Answer 13

Charcoal, 17 bytes

⊞υωＦＳ≔⁺⁺ιυ⁺υιυ№υＳ

Try it online! Link is to verbose version of code. Takes the list as the first argument and the string as the second argument and outputs a - for each order of insertions that writes the string (this is always even because the first character can be inserted from either side). Explanation:

⊞υω

Start with an empty board.

ＦＳ

Loop over the list of characters.

≔⁺⁺ιυ⁺υιυ

Prefix and suffix the character to all of the strings found so far.

№υＳ

Output the number of occurrences of the desired string.

Answer 14

Nibbles, 7 bytes (14 nibbles)

?!.\;`_0$\$@:

Nibbles port of Unrelated String's Jelly answer: upvote that one!

?!.\;`_0$\$@:
     `_0$       # all subsequences of arg1
    ;           # (save that for later)
   \            # reverse the list
  .      \$     # and map over it reversing each subsequence
 !              # now zip this together with
           @    # the saved of subsequences
            :   # by concatenation
?               # and find the index of arg2
                # (or 0 if not found)

Answer 15

Python 3.8 (pre-release), 88 bytes

f=lambda a,b,s={}:f(a,b[1:],{b[0]+t for t in s}|{t+b[0]for t in s}|{b[0]})if b else{a}&s

Try it online!

I rewrote it using sets and recursion, empty set is falsy, builds up a set of increasing string that get appended and prepended by the next character.