[Question]
  [
You know those letterboards outside old-style cinemas which show upcoming films - perhaps you have a miniature one in your home?
[![enter image description here](https://i.stack.imgur.com/E5cdlm.png)](https://i.stack.imgur.com/E5cdlm.png)
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 **A**s, 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](/questions/tagged/code-golf "show questions tagged '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]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
≈íPU·πö;"∆äi
```
[Try it online!](https://tio.run/##y0rNyan8///opIDQhztnWSsd68r8f3i5g/6jpjX//0dHK/kHOYb4BynpKCj5hwQ5BvkrxXLpRCsFu4a7ggVdw4OBDLCYs7@/D0gITENEPFyDg0FCwa4ewc4QMcdwxwjHSMcokLBjRCSQG@WIaWaQK0TMyT8CJOLkHwnV7eToHAo20tHZ0QnIgugMDnYMhtoEYQPFYwE "Jelly ‚Äì 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](https://chat.stackexchange.com/transcript/message/62244870#62244870).
```
≈í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]
# [J](http://jsoftware.com/), 22 18 bytes
```
e.((,.~,,.),.)/@|.
```
[Try it online!](https://tio.run/##bY5LC8IwEITv@RXRyyrUqBfBgOAmpHgQAtlKH@BBpCIiCD4OBfGv15A2noRdmPkGdvbSLgdyvl8M5BKADQWc@Epy4Amfcel3Irh227StxWiUiE@SiLGf6fot2jGrj@cbh@z@ep4b6J11mFkH/ORl5tDZGJDJTcdNTl71WFu7DTSICDeGKFAyG9IRY44FlliFBIvS@wqB9Wl6uD6av23ORKxsEaCy5e@oQr3rylCj8jKeIEKKb3QGWPsF "J ‚Äì 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]
# [Factor](https://factorcode.org/) + `math.combinatorics`, 64 bytes
```
[ all-subsets dup [ reverse ] map reverse [ prepend ] 2map in? ]
```
Port of Unrelated String's [Jelly answer](https://codegolf.stackexchange.com/a/253679/97916).
[Try it online!](https://tio.run/##ZVBBasMwELz7FfuB5tBjCy1rI5pCiUBKsB2Tg@Io1MSRZUluKCFvd9c1pIIKtBrN7I7EHFUdOjdu5Pvq7QmU913t4aSd0S143Q/a1NoTCh76C1inQ/i2rjEBzip8LuruvG@MIouG5p6T5JoArf5yBS5wzQXwtUDB4XbnJcuZAJZLqn9sxvnHXCJuyaSk/qXMIhZzLLDELWBREt4iaf/NBYtGUl7QLmOTFLONBMwwpSP6nJQop0dnQMotGStQbfvgh/1vDIfBQgVOf2nnNewoB3u/VVNCVpsD8Y@T0JhX2I3HOdiXiVmMPw "Factor ‚Äì Try It Online")
And my original answer:
---
# [Factor](https://factorcode.org/), ~~74~~ 69 bytes
```
[ { ""} swap [ '[ _ prefix dup reverse 2array ] map-flat ] each in? ]
```
[Try it online!](https://tio.run/##ZZBPS8QwEMXv/RSPvXhyDx4VlLQUVxADzS5ttywS6hSD3f5JUmsp/ew1a0ELBjJ5/N7MJJlC5rbW80E8vTzeQhpT5wYfpCsqUegBhtqOqpwMpNZyMCiVJS1Lg7w@N6okve2sclC5FEPWoO3RaLJ2aLSqLO48b/TgVtuP4BHb8wh8H7GIY/rlIozDCGEsXPyjAefPS1ixXSiEy9@JYEVZzBKWsiNYkjp9ZM773zwKVyU@T9xO1018FhwEWMB8d6weJwQTl0sX4ZzJmzOM2GwmmF42yHCV4fXy7UJ94a1roOmTtCHc/EwNJ5xlc12U0jpJMn@Hqh5wmotl4vfOxXb@Bg "Factor ‚Äì 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]
# [Python 3](https://docs.python.org/3.8/), ~~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!](https://tio.run/##VZDBasMwDIbveQrhU0x92NhlBHxQgqGHgcHuSNKQg0cXVujSEGfgwt49sx2PrSf/@iTrlzTdlo/r@PQ8zes68Iv5fDsZsMwxwwkpHJjxBENu2a3grnsseua6h35n6HeEzOxCTK8zGM7tusxf7xY4dBnkRCo8SEUYEHlQqCShLGAtahGpqLUXG6ykfAksvgnthdaBabHXVYJYY4MtHgPHpvXhEQnN@iwbzMX@ef83USJ9LmUTUCnb324lVq/RAyssvUoTao06eW86Wfg1/WngPEJctJjm87jk4RKO0rv8Ns19wfoD "Python 3.8 (pre-release) ‚Äì Try It Online")
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), ~~12~~ 10 bytes
*-2 bytes thanks to [Fatalize](https://codegolf.stackexchange.com/users/41723/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!](https://tio.run/##SypKTM6ozMlPN/r//8i0muxHbRus7Usebp1ekPz/f7RSopKOUhIQQ@jY/0qJSUmJSgA "Brachylog ‚Äì 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]
# JavaScript (ES6), 45 bytes
Expects two strings as `(S)(sigma)`. Same recursive approach as [97.100.97.109](https://codegolf.stackexchange.com/a/253669/58563).
```
S=>g=([c,...b],o)=>c?g(b,[o]+c)|g(b,c+o):o==S
```
[Try it online!](https://tio.run/##fY/NCoJAFEb3PkXMykHzAYIxrjLQIhiYa/iXC51UinCiolXvbo62Smk1Z/gO9373Ur7Kh7qfb891p09137Aemd8yO1eu53lV4WrKfLVt7crNdeEo@jaoHE03mjHsle4e@lp7V93ajU2EhEhIQgeKJEhBKLV@FOQxHw0eo4GZEAqxN/n0zuMdRzQ58h2GCwLEkEAKmXEgSYdvBoSunBU5doRa//pIvjAvEImJA5EuLQsgPIx1IITA0PxgRMBv5YkHqf8A "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
Employs the inverse test of a post by [pxeger](https://codegolf.stackexchange.com/users/97857/pxeger) - [here](https://codegolf.stackexchange.com/a/243174/53748).
```
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!](https://tio.run/##ATQAy/9qZWxsef//SsWSITzGneG5osaRJMaH4buLxIvigbj///8iU1RBVElPTiL/IklPVEFOVFMi "Jelly ‚Äì Try It Online")** Or see the [test-suite](https://tio.run/##y0rNyan8/9/r6CRFm2NzH@5cdGyiyrH2h7u7j3Q/atzx//By/UdNa/7/j45W8g9yDPEPUtJRUPIPCXIM8leK5dKJVgp2DXcFC7qGBwMZYDFnf38fkBCYhoh4uAYHg4SCXT2CnSFijuGOEY6RjlEgYceISCA3yhHTzCBXiJiTfwRIxMk/EqrbydE5FGyko7OjE5AF0Rkc7BgMtQnCBorHAgA "Jelly ‚Äì Try It Online").
### 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]
# [Curry (PAKCS)](https://www.informatik.uni-kiel.de/%7Epakcs/), 33 bytes
```
[]![]=1
(x:s?s++[x])!(t++[x])=s!t
```
[Try it online!](https://tio.run/##Sy4tKqrULUjMTi7@/z86VjE61taQS6PCqti@WFs7uiJWU1GjBMKwLVYs@Z@bmJmnYKug5B/kGOIfpKSgCGSGBDkG@Sv9BwA "Curry (PAKCS) ‚Äì Try It Online")
Returns `1` for truthy, and nothing otherwise. It might return the same `1` multiple times for truthy result.
[Answer]
# [sclin](https://github.com/molarmanful/sclin), 26 bytes
```
^set"__ _`"Q rev"++"dip :?
```
[Try it here!](https://replit.com/@molarmanful/try-sclin) 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](https://github.com/molarmanful/sclin), 38 bytes
```
1<>: _` ,_"\++ Q rev ++ +`"fold rev :?
```
[Try it here!](https://replit.com/@molarmanful/try-sclin)
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]
# [05AB1E (legacy)](https://github.com/Adriandmen/05AB1E/tree/fb4a2ce2bce6660e1a680a74dd61b72c945e6c3b), 7 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
√¶√Ç√≠s+I√•
```
Port of [*@UnrelatedString*'s Jelly answer](https://codegolf.stackexchange.com/a/253679/52210), 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](https://tio.run/##MzBNTDJM/f//8LLDTYfXFmt7Hl76/7@To5Mjl6OTkyMA) or [verify all test cases](https://tio.run/##Vc1BCsIwEAXQq0i2dqEL1@UnBLoQBjItSVsKKngCQejWhQfwDrrzFLmJF4nTZKPZTOYx82ezO56253Sda7X63B8rVc@HLsVXvMX3ZR3iM1VpHJWGhqoUtJSpGhW1Do5EyKEll816tk6IrbdFDNFeIJelZ9uwWaCxzFkQengMOdsjoMdQXC793pNsZ/@yNfXSawpl3kB3nDdgupLN8sALlo/o9AU).
**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](https://github.com/Adriandmen/05AB1E/tree/fb4a2ce2bce6660e1a680a74dd61b72c945e6c3b) (built in Python), which allows concatenation of strings and vectorizes. In the [new version of 05AB1E](https://github.com/Adriandmen/05AB1E) (build in Elixir), the `s+` should have been `√∏√≠J` instead: [try it online](https://tio.run/##ASEA3v9vc2FiaWX//8Omw4LDrcO4w61KScOl//9CQUJBCkFCQkE).
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Takes `œÉ` as the first input.
```
√†
√≠iUm√î√î √∏V
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=4ArtaVVt1NQg%2bFY&input=Ik9UUkFSTyIKIk9SQVRPUiI)
```
√†\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]
# [C (clang)](http://clang.llvm.org/), ~~134~~ ~~132~~ 131 bytes
-1 byte thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/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!](https://tio.run/##dVHLboMwELzzFa4lEBAjkRxjocggpBwqIeFUebQ5EDekSAlEtpseUn691Iak0EN82d2Z2Vlrl3nsmJWHpqmwK3FuuxxlaIeEc@UzGXAkAgiRKwN/6ivBd/AkJGens50pCc4rbhelBJdggljg2uwj466zwxfPsyym3HxtNhqjynEyceZKm9tWhaApTAHRZSamFlPBYlPlVjfa65QVpe0YVwOo1xoCuRfydQsC0IH6wSQliySFSGWLlKQJRD1H42XcUvGS6qRnoiR51kQXB/g8plQTNJ7TaMiQJVmRNdlokqzWqtyQR7PSeMiEyUrjYbL@5xeS6KUdRSIS6mzgRSmht390@YD1EfDbosZGG9XyQbv9Qm3Gx92Wii1W9SgAE6cV9RvTSr4Xn0cJ8B@ortFh6N5@T8AIjFXhO734dj91PARMoYaa728lfNTZ@d7aa6Nuflh@zA6i8b5@AQ "C (clang) ‚Äì Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 17 bytes
```
‚äûœÖœâÔº¶Ôº≥‚âî‚Å∫‚Å∫ŒπœÖ‚Å∫œÖŒπœÖ‚ÑñœÖÔº≥
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gtDhDo1RHoVzTmistv0hBwzOvoLQkuKQoMy9dQ1NTwbG4ODM9TyMgp7QYQmTqKJRq6iiA2UB9mZqaIAFrrgCgjhIN5/xSIAkURzVG0/r//2BXj2BnLmcP1@Dg/7plOQA "Charcoal ‚Äì 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]
# [Nibbles](http://golfscript.com/nibbles/index.html), 7 bytes (14 nibbles)
```
?!.\;`_0$\$@:
```
[Nibbles](http://golfscript.com/nibbles/index.html) port of [Unrelated String's Jelly answer](https://codegolf.stackexchange.com/a/253679/95126): 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)
```
[![enter image description here](https://i.stack.imgur.com/2d4TY.jpg)](https://i.stack.imgur.com/2d4TY.jpg)
[Answer]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 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!](https://tio.run/##VdDBaoQwEADQu18RPBRlc2jppQgeRgnsoTSQ2UVd8aCsocLWFZNCi/XbbeJmaT1l8pLJTGb41u/X/vllGJdFxpf6oznXpKYNVfE0RzIwYfkUVXRqysdqp4m8jkSTridq/pn0zuqGLMxhJ0lD2otqp3p@UIseP1tFYlJ6JPCRCfbGfEr8NUA/pJa5gAMXlvlBgOCOkWVsVZaZRIcp56/W1tXRniFaQ7bH1CFkkEMBJ@uQF2Z7Aj/0Ks@TtWnuX0t/RQRzyQnPLSW8uL@WQHpca0AKyfHeOCICutq32JUwY1H0yw5m/X80jF2vAxkYDMPN@a2b7YXlFw "Python 3.8 (pre-release) ‚Äì 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.
]