# Question
Title: The number of distinct words in a sentence
Challenge: Find the number of distinct words in a sentence

Your task is to write a program that takes a sentence as input and returns the number of distinct words in it. For this challenge, words are defined as consecutive sequences of letters, digits, and underscores ('\_').

Input:

* A string containing a sentence. The length of the sentence will not exceed 1000 characters.

Output:

* An integer indicating the number of distinct words in the sentence.

Examples:

```
Input: "The quick brown fox jumps over the lazy dog"
Output: 8

```

Explanation: The sentence contains 9 words, 8 of which are distinct: "The", "quick", "brown", "fox", "jumps", "over", "lazy", and "dog"

```
Input: "To be, or not to be, that is the question"
Output: 8

```

Explanation: The sentence contains 8 distinct words: "To", "be", "or", "not", "that", "is", "the", and "question".

```
Input: "Hello, World!"
Output: 2

```

Explanation: The sentence contains 2 distinct words: "Hello" and "World".

```
Input: "hello-world2"
Output: 2

```

Explanation: Two distinct words, "hello" and "world2" separated by hyphen.

```
Input: "Hello, World! Hello!"
Output: 2

```

Explanation: Only "Hello" and "World" are two distinct words here.

Scoring: This is a code golf challenge, so the goal is to minimize the size of your code while still producing correct output for all test cases. In case of a tie, the earliest submission wins. Good luck!

# Answer
# Bash \+ GNU utils, 28

```
grep -Eo \\w+|sort -fu|wc -l

```

Try it online!
> 5 votes

# Answer
# jq, ~~53 52~~ 50 bytes

***-1 byte** by Neil for recognizing splitting on just `\W` works since we handle empty strings anyway. **-2 bytes** by me for realizing I could `ascii_downcase` first, saving a `.` and a `|`*

```
ascii_downcase+":"|[splits("\\W")]|unique|length-1

```

~~Try it online! Try it online!~~  Try it online!

Equivalent 50 byte answer:

```
ascii_downcase+":"|split("\\W";"")|unique|length-1

```

Thanks to chune's answer for inspiring me to try golfing `splits("\\W+")` instead of `match("\\W+";"g")`. Turns out, despite having to work around the empty string being matched in some cases, it is two bytes shorter!

For those curious, here's the `match` method:

```
[match("\\w+";"g").string|ascii_downcase]|unique|length

```
> 5 votes

# Answer
# Python, 54 bytes

```
lambda s:len({*re.findall('\w+',s.lower())})
import re

```

Attempt This Online!
> 5 votes

# Answer
# Perl `-p`, 24 bytes

```
$_=grep!$s{+lc}++,/\w+/g

```

Attempt This Online!

-1 byte thanks to Kjetil S
> 4 votes

# Answer
# JavaScript, 46 bytes

```
s=>new Set(s.toLowerCase().match(/\w+/g)).size

```

Try it online!
> 3 votes

# Answer
# Zsh, 36 bytes

```
<<<${#${(u)=${1:l}//[^[:IDENT:]]/ }}

```

Try it online!

Fortunately, the `[:IDENT:]` character class is exactly the words we should keep.

```
<<<${#${(u)=${1:l}//[^[:IDENT:]]/ }}
            ${1:l}                    # lowercase string
      ${          //[^[:IDENT:]]/ }   # // replace non-[:IDENT:] with spaces
      ${   =                      }   # = split on $IFS (space/tab/newline
      ${(u)                       }   # keep first occurance of each word
   ${#                             }  # count
<<<                                   # print

```
> 3 votes

# Answer
# Python 3, 34 bytes

```
lambda i:len({*i.lower().split()})

```

Try it online!
> 3 votes

# Answer
# Japt, 14 bytes

Yet another one of those occasions I regret suggesting the removal of `_` from the `\w` RegEx class in Japt!

```
f"[%w_]+" üv l

```

Try it

```
f"[%w_]+" üv l     :Implicit input of string
f                  :Match
 "[%w_]+"          :  RegEx /[a-z0-9_]/gi
          ü        :Group & sort by
           v       :  Lowercase
             l     :Length

```
> 2 votes

# Answer
# Factor, ~~47~~ 46 bytes

```
[ >lower R/ \W/ re-split harvest cardinality ]

```

Try it online!

-1 byte thangs to GammaFunction

* `>lower` convert input to lowercase
* `R/ \W/ re-split` split on non-word characters
* `harvest` remove empty strings
* `cardinality` length without duplicates

Splitting and harvesting is shorter than simply getting a list of matches because the word for that (`all-matching-slices`) is super long. Not sure if there is a way to prevent the empty strings in pure regex, might be shorter.
> 2 votes

# Answer
# PowerShell Core, 49 bytes

```
($args-split'\W'-ne''|%{$_|% *l*r}|sort|gu).Count

```

Try it online!

```
($args-split'\W'-ne''|%{$_|% *l*r}|sort|gu).Count # full function
 $args-split'\W'-ne''                             # Splits the input string on non words character and remove empty entries
                     |%{$_|% *l*r}                # Calls ToLower() on each of the words
                                  |sort|gu        # Get unique words, Get-Unique needs the list to be sorted to remove all duplicates
(                                         ).Count # Return the count

```
> 2 votes

# Answer
# Thunno, \\$ 11 \log\_{256}(96) \approx \\$ 9.05 bytes

```
u"\w+"AfZUL

```

Attempt This Online!

Same approach as basically every other answer.

```
u"\w+"AfZUL  # Implicit input
u            # Uppercase
 "\w+"Af     # Regex findall "\w+"
        ZU   # Uniquify
          L  # Length

```
> 2 votes

# Answer
# Excel, 120 bytes

```
=LET(
    x,MID(UPPER(A1),ROW(A:A),1),
    ROWS(
        UNIQUE(
            TEXTSPLIT(A1,,
                IF((ABS(77.5-CODE(x&"Z"))<13)+1-ISERR(0+x)+(x="_")=0,x),1
            )
        )
    )
)

```
> 2 votes

# Answer
# Vyxal, 7 bytes

```
ɽøWǍUL‹

```

Try it Online!

Explanation:

```
ɽ       - Lowercases Input
 øW     - Groups string by words into a list
   Ǎ    - Removes all non-alphabetical items, leaving empty list spaces
    U   - Removes all non-unique list items
     L  - Gets length of list
      ‹ - Decrements by 1, to account for extra list item for first symbol

```
> 2 votes

# Answer
# Lua, 103 bytes

```
function x(i)r=0m={}for c in i:lower():gmatch("%w+")do if not m[c]then m[c]=1r=r+1 end end return r end

```

Try it online!
> 2 votes

# Answer
# Retina 0.8.2, 15 bytes

```
T`L`l
D`\w+
\w+

```

Try it online! Link includes test cases. Explanation:

```
T`L`l

```

Convert to lower case.

```
D`\w+

```

Deduplicate words.

```
\w+

```

Count the number of remaining words.

13 bytes in Retina 1:

```
D$`\w+
$l
\w+

```

Try it online! Link includes test cases. Explanation:

```
D$`\w+
$l

```

Deduplicate words by lowercased value.

```
\w+

```

Count the number of remaining words.
> 1 votes

# Answer
# Arturo, 35 bytes

```
$=>[match lower&{/\w+}|unique|size]

```

Try it
> 1 votes

# Answer
# , 23 bytes

```
'\w+'#@~.@rxall tolower

```

Uniquify and count word matches in lowercase input.

Attempt This Online!
> 1 votes

# Answer
# Java (JDK), 83 bytes

```
s->java.util.Arrays.stream((" "+s).toLowerCase().split("\\W")).distinct().count()-1

```

Try it online!

Saved 17 bytes thanks to Neil.
> 1 votes

# Answer
# Vyxal, 7 bytes

```
`†`ẎɽUL

```

Try it Online!

```
`†`Ẏ    # find all matches of \w+
    ɽ   # to lowercase
     U  # uniquify
      L # length

```

## With a flag:

# Vyxal `l`, 6 bytes

```
`†`ẎɽU

```

Try it Online!
> 1 votes

# Answer
# APL (Dyalog Extended), 27 bytes

```
f←{⍴∪(⎕A,⎕D,'_')(∊⍨⊆⊢)1⎕C⍵}

```

Try it online!

```
f←{⍴∪(⎕A,⎕D,'_')(∊⍨⊆⊢)1⎕C⍵}
                        1⎕C      to uppercase
     (⎕A,⎕D,'_')                 [A-Z0-9_]
     (⎕A,⎕D,'_')(∊⍨⊆⊢)1⎕C       Partition (⊆) using Membership (∊)
    ∪                             remove duplicates
   ⍴                              count words

```
> 1 votes

# Answer
# 05AB1E, 12 bytes

```
žQžjмS¡õKlÙg

```

Assumes the input will only contain printable ASCII characters.

Try it online or verify all test cases.

**Explanation:**

```
žQ            # Push the constant string with all printable ASCII characters
  žj          # Push the constant string with "a-zA-Z0-9_"
    м         # Remove all those characters
     S        # Convert the string to a list of characters
      ¡       # Split the (implicit) input-string by each of those characters
       õK     # Remove any empty strings from the list
         l    # Convert each word to lowercase
          Ù   # Uniquify the list of lowercase words
           g  # Pop and push the length
              # (which is output implicitly as result)

```
> 1 votes

# Answer
# Ruby `-n`, 32 bytes

```
p$_.upcase.scan(/\w+/).uniq.size

```

Attempt This Online!
> 1 votes

# Answer
# PHP 8.x, 87 bytes

This is a quite long piece of code...

```
fn($z)=>count(array_flip(array_filter(array_map('strtolower',preg_split('/\W+/',$z)))))

```

It's almost self-explanatory.

It's so void of PHP-only tricks that it is so trivial to re-implement it into JavaScript!

```
// PHP-like code
let fn = ($z)=>count(array_flip(array_filter(array_map('strtolower',preg_split('\\W+',$z)))));

// Test boilerplate that has enough functionality
function count(value) {
  return value.length;
}

function strtolower(str) {
  return str.toLowerCase();
}

function preg_split(regex, subject) {
  return subject.split(new RegExp(regex));
}

function array_filter(array) {
  return array.filter(function(value){
    return value !== '';
  });
}

function array_flip(array) {
  return Array.from(new Set(array));
}

function array_map(fn, array) {
  return array.map(typeof fn === 'string' ? window[fn] : fn);
}

// Event handler - does the basic output thing
text.oninput = function(){
  output.innerText = fn(this.value);
};
```

```
<input type="text" id="text"/>

<p>Output: <span id="output">--</span></p>
```

---

## Differences

There aren't a lot of differences between the PHP and JavaScript versions:

* The `fn($z)=>[...]` has to be written without the `fn` bit.
* The regular expression has to be escaped and can't have the slashes.
This means it changes from `/\W+/` to `\\W+`.
* The function `array_flip` only returns a set of all unique values.
The PHP function returns the array with the keys set from the values.
That is, an array like `['a', 'fox', 'a', 'car']` will be returned as `['a' => 2, 'fox' => 1, 'car' => 3]` while JavaScript returns `['a', 'fox', 'car']`.
The end result is the same: an array that has the same number of unique elements.

These differences won't affect the accuracy of the results.
But, it's worth to deal with them to give you an improved testing environment.
> 1 votes

# Answer
# C (gcc), ~~275~~ ~~254~~ ~~250~~ 249 bytes

* -26 bytes thanks to ceilingcat

To split the words, each uppercased word is stored in a list recursively. Duplicates are nulled out, preventing them from being scanned.

```
g(s,t,i)char*s,**t;{char*a[2]={0,t},**v,*u;for(;*s&&!isalnum(*s)&&*s-95;s++);u=*a=strdup(s);if(i=*u){for(;*u=*s&&isalnum(*s)|*s==95;*u++=~32&*s++);i=g(s,a);}else for(v=t;v;v=v[1])if(*v)for(i++,t=v;t=t[1];)*t&&!strcmp(*v,*t)?*t=0:0;s=i;}f(s){g(s,0);}

```

Try it online!

Ungolfed (with a structure instead of an array):

```
struct list { char *data; struct list *prev; };

int g(char *s, struct list *t) {
  int i;
  char *u;
  struct list a={0,t}, *v;

  for(;*s&&!(isalnum(*s)&&*s-'_');s++);
  u=a.data=strdup(s); // skip spaces and duplicate the string locally

  if(i=*u){ // collect the word and uppercase it
    for(;*u=*s&&isalnum(*s)|*s=='_';*u++=~32&*s++);
    i=g(s,&a); // recursively generate list
  }else // end of string: process the words
    for(v=t;v;v=v->prev) // from the end, work backwards
      if(v->data) // if not a duplicate
        for(i++,t=v;t=t->prev;) // scan for duplicates
          t->data&&!strcmp(v->data,t->data)?t->data=0:0; // null out duplicates

  s=i; // return the count
}

int f(char *s) { g(s,0); } // initialize the end of list and (implicitly) return the count

```
> 1 votes

# Answer
# C (GCC), 156 + 48 + 22 = 226 bytes

*-3 bytes thanks to ceilingcat*

Use compiler flags `-DW(a)=for(--s;a!isalnum(*++s)|*s==95;)*s|=32;` and `-DF(a)=for(a=0;a<i;++a)`.

```
char*v[99],*e;i,j,k;f(char*s){e=s+strlen(s);W()for(i=0;s<e;){v[i++]=s;W(!)W((*s=0)|)}F(j)F(k)strcmp(v[j],v[k])|j==k||(*v[j]=0);k=0;F(j)*v[j]&&++k;return k;}

```

Try It Online!

Explanation:

```
char*v[99],*e;
i,j,k;
f(char*s)
{
    // Set e to the end of s
    e=s+strlen(s);
    // Set s to the first character that is alphanumerical or an underscore.
    W()
    // While s hasn't moved past the end of the string ...
    for(i=0;s<e;) {
        // Store s in v[i], then increment i
        v[i++]=s;
        // Set s to the first character that isn't alphanumerical or an
        // underscore.
        W(!)
        // Set all characters between the current word and the next to 0, and
        // set s to the first character in the next word.
        W((*s=0)|)
    }
    // Iterate through the words with j.
    F(j)
        // Iterate through the words with k.
        F(k)
            // If words at index j and k are equal but j and k aren't the same
            // index, set the first character in word j to 0, marking the word
            // as a duplicate.
            strcmp(v[j],v[k])|j==k||(*v[j]=0);
    k=0;
    F(j)
        // For each word that hasn't been marked as a duplicate, increment k.
        *v[j]&&++k;
    // Return the number of words not marked as a duplicate.
    return k;
}

```
> 1 votes

# Answer
## Mathematica (Wolfram Language), 31 bytes

```
Length@*WordCounts@*ToLowerCase

```

The Mathematica built-in WordCounts treats a hyphenated word as a single word. So this program is not going to work correctly on the fourth example, "hello-world2". I discuss this in the comment below.
> 1 votes

# Answer
# Stax, 8 bytes

```
│ÿîIΔ»╝H

```

Run and debug it

This is a packed stax program. When unpacked, it is the following:

```
v"\w+"|Fu%

```

Run and debug it

# Explanation

```
v          # lowercase the input string
      |F   # get all regex pattern matches of regex
 "\w+"     # \w+
        u  # uniquify
         % # length

```
> 1 votes

# Answer
# Go, ~~181~~ 176 bytes

```
import(."regexp";."strings")
func f(s string)int{m:=make(map[string]int)
for _,w:=range MustCompile("\\w+").FindAllString(ToLower(s),-1){if _,o:=m[w];!o{m[w]=1}}
return len(m)}

```

Attempt This Online!

Gets all words matching regex `\w+`, and adds them to a map (acting as a set in this case). Then it returns the number of items in the map (set).

* -5 bytes by @The Thonnu
> 1 votes

# Answer
# Charcoal, 31 bytes

```
≔⦃⦄θＦΦ⪪↧Ｓ⁻⪪γ¹⊞ＯＥ³⁶⍘ιφ_ι§≔θιιＩＬθ

```

Attempt This Online! Link is to verbose version of code. Explanation: Inspired by @KevinCruijssen's 05AB1E answer, so assumes the input only contains printable ASCII.

```
≔⦃⦄θ

```

Start with an empty dictionary.

```
ＦΦ⪪↧Ｓ⁻⪪γ¹⊞ＯＥ³⁶⍘ιφ_ι

```

Split the lowercased input on all printable ASCII except the characters used to encode base 36 and `_`, and...

```
§≔θιι

```

... set each word as a key in the dictionary.

```
ＩＬθ

```

Output the final length of the dictionary.
> 0 votes

# Answer
# Raku, 21 bytes

```
+*.lc.comb(/\w+/).Set

```

Try it online!

This is an anonymous function. The argument (`*`) is converted to lowercase (`.lc`), then the substrings matching one or more word characters are extracted (`.comb(/\w+/)`) and converted to a set (`.Set`), which discards the duplicates. Finally, that set is expressed as a number (`+`), yielding its size.
> 0 votes

# Answer
## q, 101 bytes

```
{(#:)(&:)min each not(^:)(?:){$[not(#:)(&:)x in .Q.an;0N;x]}each cut[(&:)0<>(-':)x in .Q.an;lower x]}

```

More verbose version:

```
{count where min each not null distinct {$[not count where x in .Q.an;" ";x]}each cut[where 0<>deltas x in .Q.an;lower x]}

```
> 0 votes

---
Tags: code-golf, string
---


# Question
Title: Print instructions for typing \` in chat
## Background

As far as we can tell from trying everything (besides cheating with ZWSPs), you can't type ``\` in Stack Exchange chat. However, you can type `\`` by doing ``\\```.

So, if you want to tell someone in chat how to type backslash-backtick, you'd need to type out ``\`\\`\``` to format ``\\``` into a codeblock.

## Challenge

Your challenge will be to take a string of backticks and backslashes and output a string of backticks and backslashes that will format into that (as a code block) when you type it into SE chat. You can test this in the chat sandbox.

One important thing to note is that a backslash prevents the next backtick from starting or ending a code block, but a backslash will not actually make the next backslash *not* escape - basically, three backslashes and a backtick will become two literal backslashes and a literal backtick, the latter of which will not function as a code block delimiter anymore.

Thus, one way to solve this challenge is to take each block of backslashes (including the zero-length ones between consecutive backticks) and add a backslash to each, then surround the string in backticks.

You may assume it is possible; that is, the input will not end with a backslash. You also do not need to handle empty input.

## Input / Output

Input and output will be taken and provided as a string of backticks and backslashes. For this challenge, you must use these characters specifically. You can input or output as a flat list of characters instead, and input and output do not have to use the same format.

## Test Cases

These test cases follow my example solution. I don't actually know if another solution exists, but if you can find an alternative that works in SE chat and isn't just the aforementioned approach, I may offer a bounty.

<pre><code>\`                => `\\``
`\\`\`\\``        => `\`\\\`\\`\\\`\``
`\`\\\`\\`\\\`\`` => `\`\\`\\\\`\\\`\\\\`\\`\``
``````            => `\`\`\`\`\`\``
\\\\\\\\\`        => `\\\\\\\\\\``
`                 => `\``
`\`\`\`\`\`\`\`   => `\`\\`\\`\\`\\`\\`\\`\\``
</code></pre>

Reference Implementation in Python; you can input as many lines as you want and it will print a valid answer to each using my approach.

Standard Loopholes are disallowed as usual.

This is a challenge, so the shortest code in bytes per language wins in its language category. Happy golfing!

# Answer
> 26 votes
# Pip, 6 bytes

```
RP``.q

```

Try it online!

### Explanation

Um... well, this is interesting.

It just so happens that Pip's Pattern type (used for regex) is delimited with backticks. And that backticks can be escaped within a Pattern using backslashes.

... And furthermore, that the code for generating the Pip repr of a Pattern is apparently incorrect, because it should escape the backslashes too, but in fact it only escapes the backticks. Which is exactly the behavior this question asks for.

"It's not a bug, it's a feature"? ¯\\\_(ツ)\_/¯

```
     q  Read a line of stdin
  ``.   Cast it to a Pattern by concatenating an empty Pattern to it
RP      Get the repr

```

---

Okay, I've looked at this again and I think it's **not actually a bug**. The reason why I thought it was a bug was because some of the inputs are not possible to enter as Pattern literals. Since they are "impossible" Patterns, it makes sense that their reprs are not correctly formed representations of Pattern literals.

```
Input  Repr    Comment
`      `\``    Properly formed: backtick is escaped with a backslash
\\`    `\\\``  Properly formed: backslash is also escaped with a backslash
\`     `\\``   Improperly formed: first backtick is not escaped

```

You can't enter a regex for `\`` in Pip because `\`` is not a properly formed regex. (If you want a regex that matches the string `\``, you should use `\\``, which is entered as ``\\\```. Clear as mud? Great.)

In summary, inputs with only even-length runs of backslashes output well-formed reprs, but if there is an odd run of backslashes, all bets are off.

# Answer
> 9 votes
# Python 3, 35 bytes

```
lambda s:'`%s`'%s.replace('`','\`')

```

Try it online!

-1 thanks to dingledooper.

# Answer
> 5 votes
# Jelly, 11 bytes

```
ṣ”`j⁾\`⁾``j

```

Try it online!

Jelly version of Lynn's approach, found independently

## How it works

```
ṣ”`j⁾\`⁾``j - Main link. Takes a string S on the left
ṣ”`         - Split S on backtick
   j⁾\`     - Join with "\`", essentially replacing backticks with "\`"
       ⁾``j - Surround with backticks

```

# Answer
> 4 votes
# JavaScript (Node.js), 32 bytes

```
n=>'`'+n.replace(/`/g,'\\`')+'`'

```

Try it online!

Self-explanatory trivial solution.

# Answer
> 4 votes
# Trilangle, 52 bytes

```
"`oo,.<|...,>~i\"<..._".#.,oo`"<>..+...._#..,@.....^

```

Try it on the online interpreter!

I'm not a huge fan of how un-dense this is (`.` is NOP) but I couldn't make it any smaller. Unfolds to this:

```
         "
        ` o
       o , .
      < | . .
     . , > ~ i
    \ " < . . .
   _ " . # . , o
  o ` " < > . . +
 . . . . _ # . . ,
@ . . . . . ^ . . .

```

On the red path, it prints the opening ```, and gets input. If there's no input left, it follows the green path, which prints the closing ``` and exits. Otherwise, it follows the blue path, which prints `\` and then compares the inputted character against `_` (0x5f). If it's less, it takes the yellow path to close the loop. Otherwise, it takes the magenta path to print ```, waste a lot of time/space, and *then* close the loop.

As I said above, there's so many NOPs I can't help but think I can contract this, but I have yet to find a smaller way to do this.

# Answer
> 3 votes
# Japt, 12 bytes

Look, Ma, no escape characters!

```
"`{r'`_i'\}`

```

Try it

# Answer
> 3 votes
# Vyxal 2.3, 7 bytes

```
\`‛\`Vq

```

Up until recently, q (uneval) simply surrounded the string in backticks. Now it escapes backslashes and backticks, which we don't want.

Also up until recently, strings in the input couldn't be delimited by backticks, but now they can so input is misparsed.

The rest is just replacing backticks with a backtick and a backslash.

So no TIO, but feel free to download the interpreter from the above link and try it out.

# Answer
> 2 votes
# QuadR, 11 bytes

```
^|$
`
`
\\`

```

Try it online!

Simply replaces (i.e. inserts at) the beginning/end with a backtick,

and any backtick with a backslash and a backtick.

Equivalent to the Dyalog APL function `'^|$' '`'⎕R'`' '\`'`

# Answer
> 2 votes
# 05AB1E (legacy), 9 bytes

```
Z„\`.:Z.ø

```

Assumes the input will always contain a backtick.

Try it online or verify all test cases.

**Explanation:**

```
Z          # Get the maximum character of the (implicit) input-string (the backtick `)
    .:     # Replace all backticks in the input
 „\`       # with "\`"
      Z    # Then get the backtick again with the maximum (without popping the string)
       .ø  # Surround the string with this backtick as leading/trailing character
           # (after which the result is output implicitly)

```

Uses the legacy version of 05AB1E, because the newer 05AB1E version's min/max won't work on characters (it will return the first character, instead of the lowest/highest unicode character).

# Answer
> 2 votes
# Nibbles, 9 bytes

```
;"`":<<*$.`%_$:"\\"

```

Attempt This Online!

```
;"`":<<*$.`%_$:"\\"
;                   Output b :=
 "`"                 backtick
    :               Join
     <<              remove last character from
       *              join by
        $              b
         .             for each s in
          `%            split
            _            input
             $           by b
              :         join
               "\\"      backslash
                         s
                     b

```

# Answer
> 1 votes
# PowerShell, 31 bytes

```
'`'+$args.replace('`','\`')+'`'

```

Try it online!

# Answer
> 1 votes
# Perl 5 \+ `-pl140`, 16 bytes

```
$_=$\.s/`/\\`/gr

```

Try it online!

## Explanation

A relatively standard solution, this uses the `-l140` flag to set `$\` to ``` which is automatically output after every call to `print`. Since we're also using the `-p` flag, `$_` will be automatically `print`ed so we set it to `$\` concatenated with the `/r`esult of `s/`ubsitituing ``` with `\`` in the (implicit) input stored in `$_`.

---

# Perl 5 \+ `-p0140l`, 19 bytes

```
$\.="$_\\`"}{$\.=$/

```

Try it online!

## Explanation

Slightly more interesting but longer, this answer uses the `-0140` flag to split input on ``` instead of newlines which means the first part of the code (before the `}{`) will be called for each part of the string (up to, but excluding ```), appending the string itself concatenated with `\\`` to `$\` which is pre-initialised to `$/` (```) via `-l`. Once all the input has been parsed (`}{`), `$/` is appended to `$\` which is implicitly output due to `-p`.

# Answer
> 1 votes
# Vyxal, ~~12~~ 7 bytes

```
q\\d\\V

```

Try it Online!

*-5 thanks to @lyxal*

#### Explanation

```
q\\d\\V  # Implicit input
q        # Repr (Vyxal strings are
         # delimited by backticks)
 \\d     # Double a backslash to get \\
    \\V  # Replace with one backslash
         # Implicit output

```

Old:

```
\`\\\`+V\`ø.  # Implicit input
\`            # Push the character `
  \\          # Push the character \
    \`+       # Add it to ` to get \`
              # This is one byte shorter than
              # using a string literal, `\\\``,
              # since strings in Vyxal are
              # delimited by backticks
       V      # Replace ` with \`
        \`ø.  # Surround with backticks
              # Implicit output

```

# Answer
> 1 votes
# Thunno, \\$ 15 \log\_{256}(96) \approx \\$ 12.35 bytes

```
'`"\`"Ar'`+'`s+

```

Attempt This Online!

Port of Lynn's Python answer

#### Explanation

```
'`"\`"Ar'`+'`s+  # Implicit input
'`               # Push `
  "\`"           # Push \`
      Ar         # Replace ` with \`
        '`+      # Append a backtick
           '`s+  # Prepend a backtick
                 # Implicit output

```

# Answer
> 0 votes
# Red, 42 bytes

```
func[s][rejoin[t:"`"replace/all s t"\`"t]]

```

Try it online!

---
Tags: code-golf, string
---


title: Print a tongue twister!

text:
# Question
Title: Print a tongue twister!
The goal of this challenge is to print the following tongue twister:

```
She sells seashells by the seashore,
The shells she sells are seashells, I'm sure.
So if she sells seashells on the seashore,
Then I'm sure she sells seashore shells.

```

This is more complicated than just calling your language's `print` equivalent. Since there are a lot of repeated words and phrases, you can greatly decrease the size of your code by using other tactics.

**Rules:**

* No querying another website which will respond with the full twister
* You must include all the punctuation and line breaks in the original text.
* You can end with a trailing newline

**This is , so the shortest code wins!**

**Good luck!**

# Answer
# Python 3, ~~166~~ \\$\cdots\\$ ~~142~~ 135 bytes

Saved a whopping ~~13~~ 18 bytes thanks to ovs!!!
Saved 4 bytes thanks to user253751!!!
Saved a byte thanks to branboyer!!!
Saved 7 bytes thanks to dingledooper!!!

Note: There's lots of unprintables in the following code so please avert your eyes if you're sensitive to such things! :D

```
print("Sh by are,.\nSo if onnore.".translate("| seash|ells|ore,\nThe| sh|e s| I'm sure| the".split("|")))

```

Try it online!

Based on Netråm's C# answer.
> 15 votes

# Answer
# Retina 0.8.2, ~~106~~ 103 bytes

```

S230 by41h012 are30,5.¶So if1230 on4n5123ore1h0.
5
 I'm1ure
4
 the3ore,¶The
3
1eash
2
he10
1
 s
0
ells

```

Try it online! Explanation: In Retina, a substitution only makes sense if it's long enough `l` for the number `n` of repetitions. The substitution saves `n(l-1)` bytes in the compressed text but costs `l+3` bytes in the replacement stages. This gives the minimum length required to be useful as follows:

* 2 repetitions: length \> 5
* 3 repetitions: length \> 3
* 4 repetitions: length \> 3
* 5 repetitions: length \> 2
* 6+ repetitions: length \> 1

Edit: As @Arnauld pointed out, you can count repetitions from the substitution entries as well. This means that although there were only 5 repetitions of space+s in my previous encoded text, there are also 3 repetitions in the substitutions, thus allowing me to save 3 bytes overall. (@Arnauld himself had only spotted 2 of the 3 repetitions.)
> 12 votes

# Answer
# JavaScript (ES6),  ~~142~~  141 bytes

*Saved 1 byte thanks to @Neil*

```
_=>`246 / I'm5ure/he56/ the4ore,
The/5eash/ s/ells`.split`/`.reduce((s,p,i)=>s.split(i).join(p),`S0by35h652 are46,1.
So if50on3n1524ore5h6.`)

```

Try it online!

### Compression steps

```
**"ells" -> "6" (9 occurences, saved: 22 bytes)**
She s6 seash6 by the seashore,
The sh6 she s6 are seash6, I'm sure.
So if she s6 seash6 on the seashore,
Then I'm sure she s6 seashore sh6.

**" s" -> "5" (17 occurences, saved: 14 bytes)**
She565eash6 by the5eashore,
The5h65he56 are5eash6, I'm5ure.
So if5he565eash6 on the5eashore,
Then I'm5ure5he565eashore5h6.

**"5eash" -> "4" (6 occurences, saved: 18 bytes)**
She5646 by the4ore,
The5h65he56 are46, I'm5ure.
So if5he5646 on the4ore,
Then I'm5ure5he564ore5h6.

**" the4ore,\nThe" -> "3" (2 occurences, saved: 10 bytes)**
She5646 by35h65he56 are46, I'm5ure.
So if5he5646 on3n I'm5ure5he564ore5h6.

**"he56" -> "2" (4 occurences, saved: 7 bytes)**
S246 by35h652 are46, I'm5ure.
So if5246 on3n I'm5ure524ore5h6.

**" I'm5ure" -> "1" (2 occurences, saved: 5 bytes)**
S246 by35h652 are46,1.
So if5246 on3n1524ore5h6.

**"246 " -> "0" (2 occurences, saved: 1 byte)**
S0by35h652 are46,1.
So if50on3n1524ore5h6.
```
> 11 votes

# Answer
# ///, 115 bytes

Port of Neil's answer + accepting nph's suggestion.

```
/3/ I'm4ure//2/4eash//1/he40//0/ells//4/ s/S120 by the2ore,
The4h041 are20,3.
So if4120 on the2ore,
Then3412ore4h0.

```

Try it online!
> 9 votes

# Answer
# 05AB1E, ~~91~~ 86 bytes

```
“SheÌç1€‹€€0,
The¬•s‚ÎÌç€™1,2.
So€¬‚ÎÌç1€‰€€0,
Then2‚ÎÌç0¬•s.“2Ý…½š¬•s#'í™ì“I'mˆ•“ª1ú:

```

Try it online.

**Explanation:**

```
“SheÌç1€‹€€0,
The¬•s‚ÎÌç€™1,2.
So€¬‚ÎÌç1€‰€€0,
Then2‚ÎÌç0¬•s.“  # Push dictionary string "She sells1 by the0,
                 #                         The shells she sells are1,2.
                 #                         So if she sells1 on the0,
                 #                         Then2 she sells0 shells."
2Ý               # Push list [0,1,2]
…½š¬•s           # Push dictionary string "shore shells"
      #          # Split it on spaces: ["shore","shells"]
       'í™ì     '# Prepend dictionary string "sea" in front of both:
                 #  ["seashore","seashells"]
“I'mˆ•“ª        '# Append dictionary string "I'm sure" to this list:
                 #  ["seashore","seashells","I'm sure"]
1ú               # Pad each string with a leading space:
                 #  [" seashore"," seashells"," I'm sure"]
:                # Replace all [0,1,2] with [" seashore"," seashells"," I'm sure"]
                 # (after which the result is output implicitly)

```

See this 05AB1E tips of mine (section *How to use the dictionary?*) to understand how the dictionary strings work.
> 9 votes

# Answer
# Bubblegum, ~~79~~ 78 bytes

removed trailing newline for -1 byte
The text in the tongue twister has many simple patterns. There are enough of them that even "normal" languages can save bytes. However, the *only* thing DEFLATE does is compressing simple patterns with little overhead...

```
00000000: 0bce 4855 284e cdc9 2906 9289 c519 6056  ..HU(N..).....`V
00000010: 52a5 4209 5018 2c90 5f94 aac3 1502 e441  R.B.P.,._......A
00000020: e58a e1ea 138b 5211 7a74 143c d573 158a  ......R.zt.<.s..
00000030: 4b8b 52f5 b882 f315 32d3 800a 310d cecf  K.R.....2...1...
00000040: c334 380f ae13 a105 a602 66ab 1e00       .48.......f...

```

Try it online!

After "writing" this answer, I finally decided to find a way to view the internal representation details of the string (to be specific, information on what characters are printed literally and what substrings are compressed as repetitions via LZ77). I modified `kunzip` (which already had some useful logging capabilities) to log only the information I want to see. This is the result:

```
output 83 S
output 104 h
output 101 e
output 32
output 115 s
output 101 e
output 108 l
output 108 l
output 115 s
len: 3 dist: 6 ( se)
output 97 a
output 115 s
output 104 h
len: 5 dist: 10 (ells )
output 98 b
output 121 y
output 32
output 116 t
len: 3 dist: 23 (he )
len: 5 dist: 17 (seash)
output 111 o
output 114 r
output 101 e
output 44 ,
output 10
output 84 T
len: 3 dist: 14 (he )
len: 7 dist: 28 (shells )
output 115 s
len: 9 dist: 48 (he sells )
output 97 a
output 114 r
output 101 e
len: 10 dist: 52 ( seashells)
output 44 ,
output 32
output 73 I
output 39 '
output 109 m
output 32
output 115 s
output 117 u
output 114 r
output 101 e
output 46 .
output 10
output 83 S
output 111 o
output 32
output 105 i
output 102 f
len: 3 dist: 41 ( sh)
len: 18 dist: 89 (e sells seashells )
output 111 o
output 110 n
len: 18 dist: 89 ( the seashore,
The)
output 110 n
len: 9 dist: 58 ( I'm sure)
len: 10 dist: 51 ( she sells)
len: 8 dist: 34 ( seashor)
len: 8 dist: 118 (e shells)
output 46 .

```

I think might will be useful for "normal" language answers.
> 7 votes

# Answer
# C# (Visual C# Interactive Compiler), 171 bytes

```
string a=" she sells ",b="shells",c="seashore",d=a+"sea"+b;Write(@$"She{d[4..]} by the {c},
The {b}{a}are sea{b}, I'm sure.
So if{d} on the {c},
Then I'm sure{a}{c} {b}.")

```

Try it online!

The `@` allows for line breaks inside string literals.
> 5 votes

# Answer
# Japt, ~~108~~ ~~105~~ ~~104~~ ~~96~~ ~~93~~ 92 bytes

```
`S230 by41h012 ‡e30,d.
So if1230 4˜123Že1h0.`dd` I'm1¨e`4` e3Že,
T”`3`1Á`2`”10`1" s"0`e¥s

```

Try it online!

Port of the retina answer to Japt.

## Explanation

```
S230 by41h012 ‡e30,d.
So if1230 4˜123Že1h0.
```

Decompress into the string literal:

```
S230 by41h012 are30,d.
So if1230 on4nd123ore1h0.

```

Then we do replacements with:

```
d
 d` I'm1¨e`     // "d" with " I'm1ure"
 4` e3Že,\nT”`  // "4" with " the3ore,\nThe"
 3`1Á`          // "3" with "1eash"
 2`”10`         // "2" with "he10"
 1" s"          // "1" with " s"
 0`e¥s          // "0" with "ells"

```
> 5 votes

# Answer
# Stax, 83 bytes

```
ÇσGª☺Uë\╠╤↑╡V╦⌐∞┐ü9B@♦1ÖFò╫◄«vâ¬♂ƒQn→↨¥p▬♂♥å↓hb½Z╫Éà½♣µ\╩N>.▄┌bæ¼@3▲¡w8╣▐ù☼ve/h{≈ï░

```

**Run and debug it**

### How?

Unpacked:

```
`...`'!/|J
`...`      - compressed string "She sells..." with '!' where newlines should be
     '!    - a '!' character
       /   - split the compressed string at '!' characters
        |J - join with newline characters

```

Maybe making a manual compression using the words will be shorter?
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), 154 bytes

```
Write(@"S{0}sea{1} by the {2},
The {1} s{0}are sea{1}, I'm sure.
So if s{0}sea{1} on the {2},
Then I'm sure s{0}{2} {1}.","he sells ","shells","seashore")

```

Try it online!
> 5 votes

# Answer
# ink, ~~129~~ 130 bytes

```
-(i){|The shells|So if|Then I'm sure} {S|s}he sells {|are |}sea{|||shore }shells{& {on|by} the seashore,|{, I'm sure.|.->END}}
->i

```

Try it online!

* +1 byte: A period was missing from the end of a line

### Explanation

```
// Thanks to all the new whitespace, this ungolfed code doesn't quite work as is
-(i)                              // A label
{|The shells|So if|Then I'm sure} // A sequence - the first time we get here we print nothing,
                                  // the second time we print "The shells",
                                  // the third time we print "So if", etc
{S|s}                             // Sequences keep outputting their last value once it's been reached
he sells                          // Plain text just gets printed
{|are |}
sea{|||shore }shells
{& {on|by} the seashore,|{, I'm sure.|.->END}}
                                  // {& marks a repeating sequence.
                                  // Instead of getting stuck on its last value, this it starts over.
                                  // On the fourth pass we hit ->END and terminate the program
->i                               // On the other passes, we get here and go back to the start

```
> 4 votes

# Answer
# PHP, ~~133~~ 126 bytes

```
<?=strtr("S2 s101 by t203,\nT2414e s1 are01,5.\nSo if4e s101 on t203,\nT2n54e s10341.",[" seash",ells,he,ore," sh"," I'm sure"]);

```

Try it online. Use PHP \< 7.2 to avoid warnings
> 4 votes

# Answer
# PowerShell, 158 bytes

Because if bash counts then why not...

```
$1="seash"
$5="ells"
$4="he s$5 "
$6=" I'm sure"
$2="$1$5"
$3="$1`ore"
"S$4$2 by the $3,`nThe $5 s$4`are $2,$6.`nSo if s$4$2 on the $3,`nThen$6 s$4$3 $5"

```

Try it online!
> 4 votes

# Answer
# PowerShell, ~~134~~ ~~133~~ 132 bytes

-1 byte thanks @Titus

see similar by Nail and Arnauld

```
$d='S0by36h461 are54,2.
So if60on3n2615ore6h4.'
"154 #he64# I'm6ure# the5ore,
The#ells#6eash# s"-split'#'|%{$d=$d-replace$i++,$_}
$d

```

Try it online!
> 4 votes

# Answer
# V (vim), 110 bytes

```
iS230 by41h012 are30,5.
So if1230 on4n5123ore1h0.Í5/ I'm1ure
Í4/ the3ore,\rThe
Í3/1eash
Í2/he10
Í1/ s
Í0/ells

```

Try it online!

Port of @Neil's retina answer to V (vim)
> 4 votes

# Answer
# Python, ~~179~~ 176 bytes

```
print"She sells seashells by the seashore,\nThe shells she sells are seashells, I'm sure.\nSo if she sells seashells on the seashore,\nThen I'm sure she sells seashore shells."

```

Trivial algorithm, but nobody’s done it yet. I’m working on a better answer in a different language, but I don’t know if it should be posted in another answer or in this one. Shortening advice accepted, but I’m perfectly fine with just hard-coding it for now.
> 3 votes

# Answer
# PicoLisp, ~~160 157 146 142~~ 138 bytes

```
(prin(text"S@1 @2 by the @3,
The @5 s@1 are @2,@4.
So if s@1 @2 on the @3,
Then@4 s@1 @3 @5.""he sells"'seashells'seashore" I'm sure"'shells]

```

Using the template:

```
S1 by the 2,
The 5 s1 are 2,4.
So if s1 on the 3,
Then4 s1 3 5.

```

Where 1 is `"he sells"`, 2 is `"seashells"`, 3 is `"seashore"`, and 4 is `" I'm sure"`

Ideone It!

`{<sub><sup><sub> 14 imaginary interweb points for guessing which syntax highlighting I'm using without peeking </sub></sup></sub>}`

### Common Lisp, 160 bytes

```
(format t"S~a~a by the ~a,~%The shells s~3:*~Aare ~a, I'm sure.~%So if s~3:*~A~a on the ~a,~%Then I'm sure s~3:*~a~*~a shells.""he sells ""seashells""seashore")

```

https://ideone.com/n7zVUm
> 3 votes

# Answer
# Java 8, ~~169~~ 160 bytes

```
v->"".format("S%sells by%s shells she sells are seashells, I'm sure.\nSo if s%1$sells on%2$sn I'm sure s%1$sore shells.","he sells seash"," the seashore,\nThe")

```

Port of *@IgbyLargeman*'s C# answer, so make sure to upvote him as well!
-9 bytes thanks to *@branboyer*.

Try it online.

(Simply returning as is would be 174 bytes.)

**Explanation:**

```
v->           // Method with empty unused parameter and String return-type
  "".format(  //  Return the following formatted string:
     "S%sells by%s
      shells she sells are seashells, I'm sure.\n
     So if s%1$sells on%2$s
     n I'm sure s%1$sore shells.",
    "he sells seash",
              //   Where the first `%s` and all `%1$s` are replaced with "he sells seash"
    " the seashore,\nThe")
              //   and the second `%s` and all `%2$s` are replaced with " the seashore,\n
                                                                         The"

```
> 3 votes

# Answer
# JavaScript (V8), 287 bytes

Trying a different way of compressing it, in a different language. Feedback is appreciated!

```
function s(){a="kdg by the dj,/nThe g care dg, I'm sure./nSo if cdg on the dj,/nThen I'm sure cdj g.".replace(/c|k/g,function(match){return(match=="c")?"she sells ":"She sells ";});c=a.replace(/d|g/g,function(match){return(match=="d")?"sea":"shells";});return (c.replace(/j/g,"shore"));}

```

Try it online!
> 3 votes

# Answer
# Husk, 77 bytes

```
ΓJx'p¨½ΞĿ∫Ẏj5pż¦Sβyεḟ?ṡ,ḣŀḢ¦ṠεΞĿ∫äeŻaŀ`◄,İ'm ṡ→.¶ȮSÏf£2₅Φεḟ?ṡ,ḣnİ'm ṡ→⁸ρΘŀḢ¦.

```

Try it online!

Better than Bubblegum!

Husk's string compression is pretty good for this task, a straightforward compressed string would be 82 bytes long. Here, we apply just a single substitution to make it shorter. The compressed string we use here is

```
he sells seashpSpells by the seashore,
The shells she sells are seashells, I'm sure.
So if spells on the seashore,
Then I'm sure spore shells.

```

The structure of the code is:

```
ΓJx'p¨...
     ¨...  The compressed string
  x'p      split on occurrences of the character 'p'
ΓJ         and joined by interleaving the first substring between the rest

```

What this does in practice is replacing the character 'p' with "he sells seash" everywhere in the rest of the string. This substitution was the one that generated the shortest compressed string among the ones I've tried; multiple substitutions are possible but they didn't seem worth the longer payload. The letter 'p' was chosen because it generates words like "spell" and "spore" in the text that can be compressed very well by Husk.
> 3 votes

# Answer
# Deadfish~, ~~1313~~ 1234 bytes

```
iiissiic{ii}icdddc{{d}iii}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dcdddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}ddsddc{ii}iiic{{d}i}ic{dd}dsdddddc{d}ddcdddc{{d}iii}ic{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dc{i}dddciiic{d}dddc{{ii}}dc{ddd}ddddcdsiiic{ii}cdddc{{d}iii}ic{dd}s{ddd}ic{d}dcdddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}dcdddc{{d}iii}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{{iii}ii}ic{ii}dddc{d}dddc{{d}iii}ic{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dcdddc{i}dddcc{i}dddc{{d}iii}dc{d}ddc{iiii}ic{ddd}ddddc{{i}ddd}c{{d}ii}iiic{dd}s{ddd}iciicdddc{d}dddc{{ii}}ic{{ii}ii}cdsiic{iii}ddc{{d}ii}ic{{iii}iii}dcdddc{{d}iii}c{dd}s{ddd}ic{d}dcdddc{{d}iii}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dcdddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}ds{d}cdc{{d}ii}iic{dd}dsdddddc{d}ddcdddc{{d}iii}ic{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dc{i}dddciiic{d}dddc{{ii}}dc{ddd}ddddcdsiiic{ii}cdddc{i}dc{{d}ii}iic{iiii}ic{ddd}ddddc{{i}ddd}c{{d}ii}iiic{dd}s{ddd}iciicdddc{d}dddc{{d}iii}ic{dd}s{ddd}ic{d}dcdddc{{d}iii}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dc{i}dddciiic{d}dddc{{d}iii}ic{dd}s{ddd}ic{d}dcdddc{i}dddcc{i}dddc{{d}iii}ic

```

Try it online!

Deadfish, the ungolfing language.
> 3 votes

# Answer
# Deadfish~, ~~1216~~ 1196 bytes

```
iiissiici{ii}cdddci{iii{d}}ciii{dd{i}}cdddd{d}cddd{i}ccddd{i}c{{d{{i}}}}ciii{dd{i}}cdddd{d}cddddcdd{ii}cd{d}cdddcddd{i}ccddd{i}c{{d{{i}}}}c{d{i{i}}}ciii{ii}ci{i{d}}c{iiii{iii}}cdd{d}cdddci{iii{d}}ciii{dd{i}}cdddd{d}cddddcdd{ii}cd{d}cddd{i}ciiicddd{d}cd{{ii}}c{d{{i}}}cdsiiic{ii}cdddci{iii{d}}ciii{dd{i}}cd{d}cdddcddd{i}ccddd{i}c{{d{{i}}}}ciii{dd{i}}cd{d}cdddci{iii{d}}ciii{dd{i}}cdddd{d}cddd{i}ccddd{i}c{{d{{i}}}}ci{ii{iii}}cddd{ii}cddd{d}ci{iii{d}}ciii{dd{i}}cdddd{d}cddddcdd{ii}cd{d}cdddcddd{i}ccddd{i}cd{iii{d}}cdd{d}ci{iiii}c{d{{i}}}c{ddd{i}}cd{dd{ii}}ciii{dd{i}}ciicdddcddd{d}ci{{ii}}c{ii{ii}}cdsiicdd{iii}ci{ii{d}}ciii{ddd{i}}cdddc{iii{d}}ciii{dd{i}}cd{d}cdddci{iii{d}}ciii{dd{i}}cdddd{d}cddd{i}ccddd{i}c{{d{{i}}}}ciii{dd{i}}cdddd{d}cddddcdd{ii}cd{d}cdddcddd{i}ccddd{i}c{{d{{i}}}}cd{dd{i}}cdcii{ii{d}}c{iiii{iii}}cdd{d}cdddci{iii{d}}ciii{dd{i}}cdddd{d}cddddcdd{ii}cd{d}cddd{i}ciiicddd{d}cd{{ii}}c{d{{i}}}cdsiiic{ii}cdddcd{i}cii{ii{d}}ci{iiii}c{d{{i}}}c{ddd{i}}cd{dd{ii}}ciii{dd{i}}ciicdddcddd{d}ci{iii{d}}ciii{dd{i}}cd{d}cdddci{iii{d}}ciii{dd{i}}cdddd{d}cddd{i}ccddd{i}c{{d{{i}}}}ciii{dd{i}}cdddd{d}cddddcdd{ii}cd{d}cddd{i}ciiicddd{d}ci{iii{d}}ciii{dd{i}}cd{d}cdddcddd{i}ccddd{i}ci{iii{d}}c

```

Try it online!

As long as I didn't mess anything up, this should be the shortest possible without `()` and printing in loops.
> 3 votes

# Answer
# FEU, ~~112~~ 111 bytes

-1 byte thanks to Neil

```
a/S256 by43h632 are56,1.\nSo if3256 on4n1325ore3h6.
m/1/ I'm3ure/2/he36/3/ s/4/ the5ore,\nThe/5/ seash/6/ells/g

```

Try it online!

Port of JavaScript answer.
> 2 votes

# Answer
# Python 2, ~~175~~ 158 bytes

thanks @branboyer for the edit!

```
print"S{0}ells by{1} shells she sells are seashells, I'm sure.\nSo if s{0}ells on{1}n I'm sure s{0}ore shells.".format("he sells seash"," the seashore,\nThe")

```

Try it online!
> 2 votes

# Answer
# Scala, 155 bytes

```
printf("S%2$s by%1$s shells%3$sare seashells, I'm sure.\nSo if s%2$s on%1$sn I'm sure%3$sshells."," the seashore,\nThe","he sells seashells"," she sells ")

```

Try it online!
> 2 votes

# Answer
# Zsh, 128 bytes

```
<<Z
S${4=${2=he s${1=ells}}${3= seash}$1 }by${5= the$3ore,
The} sh$1 s$2 are$3$1,${6= I'm sure}.
So if s$4on$5n$6 s$2$3ore sh$1.

```

Try it online!
> 2 votes

# Answer
# Deadfish~, 1269 bytes

```
iiissiic{ii}icdddc{ddddddd}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dcdddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}ddsddc{ii}iiic{ddddddddd}ic{dd}dsdddddc{d}ddcdddc{ddddddd}ic{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dc{i}dddciiic{d}dddc{{ii}}dc{ddd}ddddcdsiiic{ii}cdddc{ddddddd}ic{dd}s{ddd}ic{d}dcdddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}dcdddc{ddddddd}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{{iii}ii}ic{ii}dddc{d}dddc{ddddddd}ic{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dcdddc{i}dddcc{i}dddc{ddddddd}dc{d}ddc{iiii}ic{ddd}ddddc{iiiiiii}c{dddddddd}iiic{dd}s{ddd}iciicdddc{d}dddc{{ii}}ic{{ii}ii}cdsiic{iii}ddc{dddddddd}ic{{iii}iii}dcdddc{ddddddd}c{dd}s{ddd}ic{d}dcdddc{ddddddd}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dcdddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}ds{d}cdc{dddddddd}iic{dd}dsdddddc{d}ddcdddc{ddddddd}ic{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dc{i}dddciiic{d}dddc{{ii}}dc{ddd}ddddcdsiiic{ii}cdddc{i}dc{dddddddd}iic{iiii}ic{ddd}ddddc{iiiiiii}c{dddddddd}iiic{dd}s{ddd}iciicdddc{d}dddc{ddddddd}ic{dd}s{ddd}ic{d}dcdddc{ddddddd}ic{dd}s{ddd}ic{d}ddddc{i}dddcc{i}dddc{{iiii}iii}dc{dd}s{ddd}ic{d}ddddcddddc{ii}ddc{d}dc{i}dddciiic{d}dddc{ddddddd}ic{dd}s{ddd}ic{d}dcdddc{i}dddcc{i}dddc{ddddddd}ic

```

Try it online!
> 2 votes

# Answer
# Knight, 138 bytes

```
O+S=q+=sS=v" shells"4F" se"=tSvT0"sea"F2"S"+" by"+=p" the seashore,
The"+v+s+" are"+t+=u" I'm sure.
So if"+q+S" onn"3Fp+GuF9+s+Gp 4 9+v"."

```

Try it online!

Fiiiiiiiine, I'll explain it

#### Attempt at explaining it

Sorry, the indentation is a little inconsistent...

```
OUTPUT
 +
  # substitute " s" with "S" for initial capitalization
  SUBSTITUTE(
   = _she_sells_seashells
    + = _she_sells
     # inject " se" into "shells"
     # to get "she sells"
     SUBSTITUTE(
       = _shells " shells"
       4
       0
       " se"
      )
    # inject "sea" to get " seashells"
    = _seashells
       SUBSTITUTE(
        _shells
        1
        0
        "sea"
       )
    )
    0
    2
    "S"
   )
  + " by"
  + = _the_seashore_the " the seashore,\nThe"
  + _shells
  + _she_sells
  + " are"
  + _seashells
  + = _im_sure_so_if "  I'm sure.\nSo if"
  + _she_sells_seashells
  # shorter to inject than concatenate
  # to get " on the seashore,\nThen"
  + SUBSTITUTE(
     " onn"
     3
     0
     _the_seashore_the
    )
  # Extract "I'm sure"
  + GET(
     _im_sure_so_if
     0
     9
    )
  + _she_sells
  # " seashore"
  + GET(
     _the_seashore_the
     4
     9
    )
  + _shells
  : "."

```
> 2 votes

# Answer
# Bash, 156 bytes

```
i=" I'm sure"
h=" she"
k=lls
l=" seashe"$k
s=" seashore"
e=" se"$k
printf "She$e$l by the$s,
The$h$k$h$e are$l,$i.
So if$h$e$l on the$s,
Then$i$h$e$s$h$k."

```

An expert can probably save some more here.
> 1 votes

# Answer
# zlib, 84 bytes

Hex dump:

```
00000000: 78 9c 0b ce 48 55 28 4e cd c9 29 06 92 89 c5 19  x...HU(N..).....
00000010: 60 56 52 a5 42 09 58 18 28 90 5f 94 aa c3 15 02  `VR.B.X.(._.....
00000020: e2 41 e4 8a e1 ea 13 8b 52 11 7a 74 14 3c d5 73  .A......R.zt.<.s
00000030: 15 8a 4b 8b 52 f5 b8 82 f3 15 32 d3 90 14 22 0c  ..K.R.....2...".
00000040: ce cf c3 34 38 0f ae 13 5d 4b 7e 11 cc 56 3d 00  ...48...]K~..V=.
00000050: 3c 70 3a e6                                      <p:.

```

Raw hex:

```
789c0bce4855284ecdc929069289c519605652a54209581828905f94aac31502e241e48ae1ea138b52117a74143cd573158a4b8b52f5b882f31532d39014220ccecfc334380fae135d4b7e11cc563d003c703ae6

```

Or generate this file yourself:

```
openssl zlib < seashells.txt > seashells.zlib

```

You can ~~decompress this file~~ execute this program with:

```
openssl zlib -d < seashells.zlib

```

or, presumably, any of the answers here.
> 1 votes

# Answer
# JavaScript: 195 bytes ...?

```
console.log(`She ${a='sells'} sea${c='shells'} by the sea${e='shore'},
The ${c} she ${a} are sea${c}, ${d="I'm sure"}.
So if she ${a} sea${c} on the sea${e},
Then ${d} she ${a} sea${e} ${c}.`)

```

Simplest JavaScript answer possible. Simply defines commonly used words. Annoyingly, compression made it longer
> 1 votes

# Answer
# Perl 5, 133 bytes

```
say"S5s0 10 by t513,
T5sh02are 10, 4.
So if210 on t513,
Then 4213 sh0."=~s/\d/(ells,seash," she sells ",ore,"I'm sure","he ")[$&]/ger

```

Try it online!
> 1 votes

# Answer
# Splinter, 150 bytes

```
I{ECA}H{\ }G{\r\e}F{H\I\'\mC\uG}E{\h\e}D{H\tEB\oG\,\
\TE}C{H\s}B{C\e\a\s\h}A{\e\l\l\s}\SIBAH\b\yDC\hACIH\aGBA\,F\.\
\S\oH\i\fCIBAH\o\nD\nFCIB\oGC\hA\.

```

Try it online!
> 1 votes

# Answer
# Vyxal 3.0.0beta.1, 77 bytes

```
"dyrΦ<ᶲrᵞjvG#IZᶳ²∵nᶨ₂ᶜ8G6OẠ′zḃṁɠ₉EFḟih←Xᵞᶻ1d²i)`⁰!⌐=x‴¶ᶢ↓•ƓΦ…ᶢɾʀ5ḋỌḄcGᵒıɾᶪ×‴”

```

Try it online!

> This is more complicated than just calling your language's `print` equivalent.

Is it now.

Simply a single compressed string. No string formatting, no substitutions. Just one string.
> 1 votes

---
Tags: code-golf, string, kolmogorov-complexity
---


title: How-many-bonacci-like is this sequence?

text:
# Question
Title: How-many-bonacci-like is this sequence?
Inspired by @emanresu A's *Is it a fibonacci-like sequence?* Make sure to upvote that challenge as well!

We say a sequence is Fibonacci-like, if, starting from the third term (\\$1\\$-indexed), each term is the sum of the previous two terms. For example, \\$3, 4, 7, 11, 18, 29, 47, 76, 123, 199\cdots\\$ is a Fibonacci-like sequence that starts with \\$3, 4\\$.

Similarly, for any positive integer \\$n\\$, we say a sequence is \\$n\\$-bonacci-like, if, starting from the \\$n+1\\$ term (\\$1\\$-indexed), each term is the sum of the previous \\$n\\$ terms. For example, \\$2, 4, 5, 11, 20, 36, 67, 123, 226, 416\cdots\\$ is a \\$3\\$-bonacci-like sequence that starts with \\$2, 4, 5\\$, while \\$1, 2, 4, 7, 8, 22, 43, 84, 164, 321\cdots\\$ is a \\$5\\$-bonacci-like sequence that starts with \\$1, 2, 4, 7, 8\\$.

In particular, constant sequences (sequences where every item are the same) are \\$1\\$-bonacci-like.

## Task

Given a non-empty list of positive integers, output the smallest \\$n\\$ such that it could be part of some \\$n\\$-bonacci-like sequence. You may assume that the input is (non-strictly) increasing.

Note that a list with length \\$n\\$ is always a part of some \\$n\\$-bonacci-like sequence.

This is , so the shortest code in bytes wins.

## Testcases

```
[3] -> 1
[2, 2, 2] -> 1
[1, 2, 2] -> 3
[2, 3, 4, 7] -> 4
[1, 3, 4, 7, 11, 18] -> 2
[1, 1, 1, 1, 1, 1, 6] -> 6
[2, 4, 5, 11, 20, 36, 67, 123, 226, 416] -> 3
[1, 2, 4, 7, 8, 22, 43, 84, 164, 321] -> 5
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] -> 10

```

# Answer
> 8 votes
# , ~~91~~ ~~78~~ 77 bytes

*Edit: -1 byte thanks to Giuseppe*

```
function(x){while(any((rowSums(matrix(c(0,x),sum(x|1),T))-x)[0:-T]))T=T+1;+T}

```

Try it online!

# Answer
> 7 votes
# Vyxal, ~~14~~ ~~12~~ 10 bytes

```
?lṠṪ?nȯ⁼)ṅ

```

Try it Online!

Man this new "lambda to newline" thing is cool.

*-2 thanks to @emanresuA*

## Explained

```
?lṠṪ?nȯ⁼)ṅ
        )ṅ   # Get the first positive integer n where:
  Ṡ          #   the sums of all
?l           #   overlapping windows of the input of length n
   Ṫ         #   with the tail removed
       ⁼     #   exactly equals
    ?nȯ      #   input[n:]

```

# Answer
> 6 votes
# MATL, 25 bytes

```
f"G1@&l2&Y+3L)G@QJh)=A?@.

```

Try it online!

Generalization of the convolution method from my fibonacci-like sequence answer.

---

*Previous*

### MATL, 30 bytes

```
f"Gn@XH-t:"G@@H+&:)J&)s=-]~?@.

```

Try it online!

# Answer
> 5 votes
# Python3, 102 bytes:

```
lambda x,c=0:(v(x,c)and c)or(x and f(x,c+1))
v=lambda x,i:len(x)<=i or(sum(x[:i])==x[i]and v(x[1:],i))

```

Try it online!

# Answer
> 5 votes
# Dyalog APL, ~~15~~ 13 bytes

-2 thanks to @FrownyFrog. (Since the input is non-decreasing,  can be used instead of `⍳∘≢` to save 2 bytes.)

```
⊃∘⍸⍋(⊃↓⍷+/)¨⊂

```

Try it online!

Taking the sequence `1 1 2 3 5` as an example:

```
   ⍋(     )¨⊂  For each n from 1 to the length of the sequence,  1           2        ...
      ↓        is the sequence with the first n terms removed    1 2 3 5     2 3 5    ...
       ⍷       a subsequence of
        +/     the sums of each n-sized window in the sequence   1 1 2 3 5   2 3 5 8  ...
     ⊃         at the first position?                            no          yes      ...
⊃∘⍸            What is the first index where this is true?       2

```

# Answer
> 4 votes
# JavaScript (ES6),  ~~65~~  64 bytes

*Saved 1 byte thanks to @tsh*

```
f=(a,w)=>a.every((v,i)=>s=i<w|s==v&&s+v-~~a[i-w],s=0)?w:f(a,-~w)

```

Try it online!

# Answer
> 4 votes
# Factor \+ `lists.lazy math.unicode`, 68 bytes

```
[ 1 lfrom [ dupd clump [ Σ ] map 1 head* tail? ] with lfilter car ]

```

Try it online!

## Explanation

Find the first positive integer whose sums of clumps of the input, sans the last element, is the tail end of the input.

`1 lfrom [ ... ] with lfilter car` Find the first positive integer where...

```
           ! { 2 4 5 11 20 36 67 123 226 416 } 3      (for example)
dupd       ! { 2 4 5 11 20 36 67 123 226 416 } { 2 4 5 11 20 36 67 123 226 416 } 3
clump      ! { 2 4 5 11 20 36 67 123 226 416 } {
                 { 2 4 5 }
                 { 4 5 11 }
                 { 5 11 20 }
                 { 11 20 36 }
                 { 20 36 67 }
                 { 36 67 123 }
                 { 67 123 226 }
                 { 123 226 416 }
             }
[ Σ ] map  ! { 2 4 5 11 20 36 67 123 226 416 } { 11 20 36 67 123 226 416 765 }
1 head*    ! { 2 4 5 11 20 36 67 123 226 416 } { 11 20 36 67 123 226 416 }
tail?      ! t

```

# Answer
> 4 votes
# Python 3.8 (pre-release), 76 bytes

```
f=lambda n,i=1:i*all(E==sum(n[I:I+i])for I,E in enumerate(n[i:]))or f(n,i+1)

```

Try it online!

This is a recursive function that increments `i` until the conditions are met with that `i`.

# Answer
> 4 votes
# Ruby, ~~59~~ 58 bytes

```
->l{1.step.find{|a|l.each_cons(a+1).all?{|*h,g|g==h.sum}}}

```

Try it online!

### Let's check:

This exploits a couple of ruby-specific shortcuts to achieve the final result.

```
->l{1.step.find{|a|

```

This is easy: starting from 1, repeat until we find the right number.

```
l.each_cons(a+1).all?{|*h,g|

```

Take every possible subarray of length a+1 and check.

```
g==h.sum}}}

```

Is the last element the sum of all other elements?

So, what happens if no match is found?

After the last check, when a+1 is the length of the array, and `each_cons` returns the whole array, we try to get all subarray of length a+2 (length of the whole array plus 1), the list is empty, and that satisfies the `all?` check, so if no answer is found, the answer is the length of the array.

# Answer
> 4 votes
# 05AB1E, 12 bytes

```
ā.Δ„üÿ.VO¨Å¿

```

Straight-forward modification of my 5-bytes inversed approach from the related challenge.

Try it online or verify all test cases.

**Explanation:**

```
ā             # Push a list in the range [1, input-length]
 .Δ           # Pop and find the first which is truthy for:
   „üÿ        #  Push string "üÿ", where the `ÿ` is automatically replaced with
              #  the integer using string interpolation
      .V      #  Execute it as 05AB1E code
              #  (`üN` creates all overlapping lists of size `N`)
        O     #  Sum each inner overlapping list
         ¨    #  Remove the last item
          Å¿  #  Check if the (implicit) input-list ends with this sublist
              # (after which the found result is output implicitly)

```

# Answer
> 4 votes
# Haskell, 58 bytes

```
g n(h:t)l|t==init l=n|1>0=g(n+1)t$zipWith(+)t l
f l=g 1l l

```

Try it online!

# Answer
> 3 votes
# Nibbles, 12.5 bytes

```
/|,~==<*~$.`'.`,$>$_+$>@_

```

Attempt This Online! / All testcases

```
/|,~==<*~$.`'.`,$>$_+$>@_
/|,~                      Find first number n such that
    ==                     equals
      <*~                   take all except the last
         $                   n items of
          .                  for each row of
           `'                 transpose
             .                 for each i in
              `,                range from 0 to (excluding)
                $                n
                 >              drop the first
                  $              i items of
                   _              input
                    +         sum of
                     $         the row
                      >     drop the first
                       @     n items of
                        _     input

```

# Answer
> 3 votes
# Japt, ~~18~~ 16 bytes

```
@ãX mx ¯J eUtX}a

```

Try it

Port of @lyxal's Vyxal answer.

Explanation:

```
@             }a  # find the first positive integer X where:
 ãX               #   all overlapped sections of length X
    mx            #   sum each
       ¯J         #   remove the last item
          e       #   is this list equal to
           UtX    #   the last X elements of the input list?

```

# Answer
> 2 votes
# Charcoal, 23 bytes

```
Ｉ⌕Ｅ⊕Ｌθ⬤θ∨‹μι⁼Σ✂θ⁻μιμ¹λ¹

```

Try it online! Link is to verbose version of code. Explanation:

```
     θ                  Input array
    Ｌ                   Length
   ⊕                    Incremented
  Ｅ                     Map over implicit range
       θ                Input array
      ⬤                 All elements satisfy
          μ             Current index
         ‹              Is less than
           ι            Outer value
        ∨               Logical Or
               θ        Input array
              ✂     ¹   Every element from
                 μ      Current index
                ⁻       Minus
                  ι     Outer value
                   μ    To current index
             Σ          Take the sum
            ⁼           Equals
                     λ  Current element
 ⌕                      Find first index of
                      ¹ Literal integer `1`
Ｉ                       Cast to string
                        Implicitly print

```

In Charcoal, the `Sum` of an empty list is `None`, so the test for a 0-binacci-like sequence always fails.

# Answer
> 2 votes
# Jelly, 13 bytes

```
+⁹\Ṗ;@ḣʋƑⱮJTḢ

```

**Try it online!** Or see the test-suite.

### How?

```
+⁹\Ṗ;@ḣʋƑⱮJTḢ - Link: list of integers, A
          J   - range of length of A -> [1,2,3,...,length(A)]
         Ɱ    - map (for L in [1,2,3,...,length(A)]) with:
        Ƒ     -   is A invariant under?:
       ʋ      -     last four links as a dyad - f(A, L)
 ⁹\           -       L-wise overlapping cumulative reduce A with:
+             -         addition
   Ṗ          -       remove the final value
      ḣ       -       head A to index L
    ;@        -       concatenate -> first L terms of A then summed terms
           T  - truthy (1-indexed) indices
            Ḣ - head

```

# Answer
> 2 votes
# Husk, 13 bytes

```
|L¹V€ṫ¹mhTm∫ṫ

```

Try it online!

```
          m ṫ  # for each of the tails of the input
           ∫   # get the cumulative sums,
         T     # transpose this list-of-lists,
       mh      # and remove the last element of each;
   V€          # now check if this is one of
     ṫ¹        # the tails of the input
               # (and output the index if it is)
|L¹            # otherwise, output the length of the input

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 42 bytes

```
1//.a_/;MovingMap[Tr,#,a]!=2#~Drop~a:>a+1&

```

Try it online!

Uses the check from this answer to the challenge that inspired this one.

# Answer
> 2 votes
# Pyth, 11 bytes

```
fqsM.:PQT>Q

```

Try it online!

### Explanation

```
fqsM.:PQT>QT    # implicitly add T
                # implicitly assign Q = eval(input())
f               # return the first integer which satisfies lambda T
         >QT    # all but the first T elements of Q
 q              # is equal to
  sM            # map to their sums
    .:  T       # all sublists of length T of
      PQ        # all but the last element of Q

```

# Answer
> 1 votes
# Julia 1.0, 56 bytes

```
\(L,l=[0L])=sum(l)!=L&&1+L[2:end]\(l=[l;[L]];pop!.(l);l)

```

Try it online!

recursive function. At step `n`, `l` stores the `n` first sub-lists of length `length(L)-n` and `L` is the last one. We iterate until `sum(l)==L`

# Answer
> 1 votes
# Raku, 53 bytes

```
{first {none .rotor($^n+1=>-$n).map:{[R-] $_}},1..$_}

```

Try it online!

* `first { ... }, 1 .. $_` returns the first number from 1 up to the size of the input list for which the brace-delimited anonymous function returns a true result. Within that function, `$^n`/`$n` is the number being tested. `$_` continues to refer to the input parameter to the outer function.
* `.rotor($^n + 1 => -$n)` produces a moving window of size `$n + 1` across the input list. For example, if the input list is `1, 3, 4, 7, 11, 18` and we're testing whether the list is 2-bonacci-like, the rotor method returns a list of the lists `1, 3, 4`, `3, 4, 7`, `4, 7, 11`, and `7, 11, 18`.
* `.map: { [R-] $_ }` reduces each of those lists with the reversed subtraction operator `R-`. (`a R- b` means `b - a`.) Because the regular subtraction operator `-` is left-associative, the reversed subtraction operator is right-associative, and so to continue the above example, it produces the numbers `4 - 3 - 1`, `7 - 4 - 3`, `11 - 7 - 4`, and `18 - 11 - 7`.
* Finally, `none` returns a truthy result if none of the reduced lists has a truthy value; that is, if all of them are zero.

# Answer
> 1 votes
# C (gcc), 123 bytes

The function takes an array of ints for `a` and its length for `z`.

```
B(a,z,M,b,v,t,L)int*a;{int*c,*p;for(M=b=z;--b;M=v?M:b)for(c=a+z,v=0;c-b-a;v|=t)for(t=*--c,p=c-1,L=b;L--;)t-=*p--;return M;}

```

Try it online!

---
Tags: code-golf, sequence, integer, fibonacci
---


title: How many xor'ed waves?

text:
# Question
Title: How many xor'ed waves?
In this challenge, you're given a list of overlapping waves. Each wave is a finite list with `n` truthy values, then `n` falsy values, then `n` truthy and so on, where `n` is the wavelength (or half the wavelength I guess, but it really doesn't matter in this challenge). The values of a wave may have an offset, so a wave of wavelength 3 could be something like `001110001110001`.

The overlapping waves all have the same length, and the result of an overlap is the exclusive or operator applied to both other waves. Applying the exclusive or operator to more than two booleans returns true if and only if the number of truthy values is odd. Example:

```
1000111000111 +
0101010101010 +
0001111000011 =
1100010101110

```

The values of a list without any waves are all falsy.

Your task is to create a program or function that, given a list of truthy and falsy values, returns the smallest number of waves that can be used to create that list.

## Test cases

```
101010101 =
101010101
-> 1 wave

10100001 =
10011001 +
00111000
-> 2 waves

110101110 =
001100110 +
111000111 +
000001111
-> 3 waves

00100101011011100100 =
10101010101010101010 +
10001110001110001110 +
00000001111111000000
-> 3 waves

1 =
(any wave)
-> 1 wave

0 =
(any or no wave(s))
-> 0 waves

(empty list of booleans) =
(any or no wave(s))
-> 0 waves

```

This is a , so the shortest submission in bytes wins!

# Answer
> 4 votes
# Vyxal, ~~26~~ 22 bytes

```
a:[λ?żD›v+$Ẋvƒḭ↔Ṡ∷?c;Ṅ

```

Try it Online!

Surprisingly it only times out for the longest test case despite using a brute force method.

```
a:[                     # if the input doesn't contain a 1 return 0
   λ                ;Ṅ  # find the first n where the following is truthy:
    ?żD›v+$Ẋvƒḭ         #   get all waves as lists of numbers
                             where odd numbers represent 1 and even 0
    ?ż                  #   range [1, len(input)]
      D                 #   triplicate
       ›                #   increment
        v+              #   addition vectorised over the left operand
          $             #   swap top two items on the stack
           Ẋ            #   cartesian product
            vƒḭ         #   reduce each by integer division

               ↔        #   all combinations with replacement of length n
                Ṡ       #   vectorising sum
                 ∷      #   mod 2
                  ?c    #   does it contain input?

```

# Answer
> 8 votes
# Pyth, ~~41~~ 39 bytes

```
K]QWshK=hZ=KSmxMCd*Ksm.:*lQS*hdU2lQlQ;Z

```

Try it online!

### Explanation

```
                                           # implicitly assign Q = eval(input())
K]Q                                        # assign K to a list containing Q
   WshK                                    # while the first element of K is not all zeros
       =hZ                                 #   increment Z (which is auto-initialized to 0)
          =K                               #   assign K to
                  *K                       #   cartesian product of K and
                    sm.:*lQS*hdU2lQlQ      #   all possible waves
             mxMCd                         #   xor'ed together
            S                              #   sort so the all zeros element will be at the start if present
                                     ;Z    # outside of loop, print Z

```

# Answer
> 7 votes
# Charcoal, ~~40~~ 37 bytes

```
⊞υＳＷΣ⌊υ«≔ΣＥυΣＥκＥ⊗⊕ν⭆κ﹪⁺Ｉρ÷⁻ςξ⊕ν²υ→»Ｉⅈ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
⊞υＳ

```

Start with the input string.

```
ＷΣ⌊υ«

```

Repeat until the input has been cancelled by the waves.

```
≔ΣＥυΣＥκＥ⊗⊕ν⭆κ﹪⁺Ｉρ÷⁻ςξ⊕ν²υ

```

Calculate the effect of at least all possible single waves on all of the waves calculated so far, and collect all of the results. (The code is pathological and generates far too many duplicates but it would cost too many bytes to uniquify them.)

Increment the count of waves, using the X-position to keep track.

```
»Ｉⅈ

```

Output the final count.

# Answer
> 7 votes
# Python 2, 141 bytes

```
lambda s:g([int("0"+s,2)],len(s))
g=lambda l,n:min(l)and-~g([x^(1<<n+j)/-~(1<<i)%(1<<n)for i in range(1,n+1)for j in range(i*2)for x in l],n)

```

Try it online! Link includes test cases. Explanation: Uses bit-twiddling to calculate the effect of at least all possible single waves on the input, recursing until a set of waves that cancels the input wave out is found.

# Answer
> 7 votes
# 05AB1E, ~~38~~ 31 bytes

```
āεÅ1D_«Ig·∍ŒIgù}€`æé.ΔIš.«^O_}g

```

Input as a list.
Brute-force, and extremely slow (times out for test cases of length \\$n\>4\\$).

Try it online or verify most lists of lengths 0 to 4..

**Original 37 bytes answer:**
(which doesn't time out for the test cases..)

```
OĀiāεÅ1D_«Ig·∍ŒIgù}€`[¼D¾ãÅΔ.«^IQ}d#]¾

```

Input as a list.
Brute-force, and also pretty slow (but it's able to complete all test cases at once nonetheless).

Try it online or verify all test cases.

**Explanation:**

```
āεÅ1D_«Ig·∍ŒIgù}€`    # Generate a list of all valid waves of the input-length:
ā                     #  Push a list in the range [1, (implicit) input-length]
 ε                    #  Map over each of those integers
  Å1                  #   Convert the integer to a list of that many 1s
    D_«               #   Merge an inverted copy (that many 0s)
       Ig             #   Push the input-length
         ·            #   Double it
          ∍           #   Extend the list of 1s/0s to that list's length
           Œ          #   Get all sublists of this list
            Igù       #   Only keep all sublists of a length equal to the input-list
               }€`    #  After the map: flatten it one level down
æ                     # Get the powerset of this list of lists
 é                    # Sort it by length
  .Δ                  # Find the first that's truthy for:
    Iš                #  Prepend the input-list to the list of lists
      .«              #  Reduce the list of lists by:
        ^             #   Vectorized bitwise-XOR the values in the lists together
         O            #  Then check if the sum of the resulting list
          _           #  is equal to 0
   }g                 # After the find_first loop: pop and push the length of the found
                      # list of lists
                      # (which is output implicitly as result)

```

```
OĀi                   # If the sum of the (implicit) input-list is NOT 0:
   āεÅ1D_«Ig·∍ŒIgù}€` #  Generate a list of all valid waves same as above
   [                  #  Start an infinite loop:
    ¼                 #   Increase the counter variable `¾` by 1 (0 by default)
    D                 #   Duplicate the current list of lists
     ¾ã               #   Get the `¾` cartesian power, to create all possible `¾`-sized
                      #   tuples of the list of lists
       ÅΔ             #   Pop and get the first index that's truthy for,
                      #   or -1 if none are truthy:
         .«           #    Reduce the current list of lists by:
           ^          #     Vectorized bitwise-XOR the values in the lists together
         IQ           #    Check if this list is equal to the input-list
       }d             #   Check if the found index is non-negative (aka NOT -1)
         #            #   If it is: stop the infinite loop
  ]                   # Close both the infinite loop and if-statement
   ¾                  # Push the counter variable
                      # (which is output implicitly as result)

```

# Answer
> 4 votes
# Haskell, ~~177~~ 161 bytes

*-16 bytes thanks to @Unrelated String*

```
(#)=replicate
f n|l<-length n=until(\x->any((==n).foldl(zipWith$(fromEnum.).(/=))(l#0))$sequence(x#[take l$drop o$(k#)=<<cycle[0,1]|k<-[1..l],o<-[1..2*k]]))(+1)0

```

Attempt This Online!

# Answer
> 4 votes
# Jelly, 23 bytes

...but Golf-SlowTM! :)

```
LḤ+€J:ⱮJẎḂŒPḊ^/⁼¥Ƈ⁸ẈṂ×Ṁ

```

A monadic Link that accepts a, potentially empty, list of zeros and ones and yields the minimal number of waves required.

Don't Try it online! it will time out even at length three!

Modifying a little will allow length four TIO (considers a window of only one greater than the length rather than double the length and also deduplicate the waves prior to getting the powerset).

It would, however, take many more bytes to make this memoised and recursive!

### How

Builds a set of "sea-position" lists that cover having position zero at every index of the input and another that would have zero at one end if extended by one (the code produces more than required). Integer divide the results by each of one through to the length of the list and modulo each result by two to get all possible single waves that could cover the input (with repeats). Take the powerset to get all combinations of waves. Filter these sets to those that become the input when reduced with a vectorising XOR. Get the minimum length of the remaining sets. Handle empty and all-zero input lists by multiplying the result by the maximum value in the input or zero if there are none.

```
LḤ+€J:ⱮJẎḂŒPḊ^/⁼¥Ƈ⁸ẈṂ×Ṁ - Link: list, A
L                       - length (A)
 Ḥ                      - double
    J                   - range of length (A)
   €                    - for each (i in [1..2*length(A)]):
  +                     -   (i) add (range of length (A)) (vectorises)
       J                - range of length (A)
      Ɱ                 - map with:
     :                  -   integer division (vectorises)
        Ẏ               - tighten  -> all waves (with loads of duplicates :p)
         Ḃ              - modulo two (vectorises)
          ŒP            - powerset
            Ḋ           - dequeue -- since we cannot reduce an empty list
                  ⁸     - chain's left argument -> A
                 Ƈ      - filter (the dequeued powerset) keeping those for which:
                ¥       -   last two links as a dyad - f(set of waves, A):
              /         -     reduce (the set of waves) by:
             ^          -       logical XOR (vectorises)
               ⁼        -     equals (A)?
                   Ẉ    - length of each
                    Ṃ   - minimium
                      Ṁ - maximum (A) -- given an empty list Ṁ yields zero
                     ×  - multiply -- this forces the `1` to a `0` when A=[] or is all zeros

```

# Answer
> 3 votes
# JavaScript (ES6), 119 bytes

```
f=(a,n=0)=>(F=(a,k=n)=>a.join``<1||k--&&a.some((_,n)=>(g=o=>o--&&g(o)||F(a.map(v=>v^o++/n&1),k))(++n*2)))(a)?n:f(a,n+1)

```

Try it online!

---
Tags: code-golf, integer, binary
---


title: Is it a valid chemical?

text:
# Question
Title: Is it a valid chemical?
Non-metals typically\* have a fixed number of covalent bonds in every chemical they are part of. Given the number of bonds every element requires, output whether it's possible to construct a *single* molecule from the given chemicals, such that every atom has it's desired number of bonds.

In other words, output if it's possible to construct a connected undirected multigraph without self-loops so that each node has the number of edges equal to the corresponding number listed in the input.

## Test Cases

Falsey:

* `[1]` A single element has nothing to bond with
* `[4]` Atoms can not bond with themselves
* `[1, 1, 1, 1]` Each atom is saturated after single bond, so it's impossible to connect all 4 of them together. It can form 2 pairs but not a single molecule.
* `[0, 0]` Two separate helium "molecules"
* `[1, 3]`
* `[2, 3]`
* `[1, 1, 1, 1, 1, 3]`

Truthy:

* `[1, 1]` (Hydrogen Gas: H-H → `1-1`)
* `[4, 2, 2]` (Carbon Dioxide: O=C=O → `2=4=2`)
* `[3, 3]` (Nitrogen Gas: N≡N → `3≡3`)
* `[2, 2, 2]` (Ozone\*: \\$\newcommand{\tripow}\[3\]{ \_{#1}{\stackrel{#2}{\triangle}}\_{#3}} \tripow{O}{O}{O}\\$\\$\tripow{2}{2}{2}\\$)
* `[0]` (Helium: He → `0`)
* `[3, 2, 1]` (Nitroxyl: O=N-H → `2=3-1`)
* `[3, 3, 3, 3]` (Tetrazete: \\$\begin{array}{ccccccc}N&-&N& &3&-&3\\\ ||& &||& → &||& &||\\\ N&-&N& &3&-&3\end{array}\\$)
* `[4, 1, 1, 1, 1, 2, 2, 2]`
* `[4, 2, 2, 1, 1]`
* `[3, 3, 2, 1, 1]`

Here are the Falsey/Truthy test cases as two lists of lists:

```
[[1], [4], [1, 1, 1, 1], [0, 0], [1, 3], [2, 3], [1, 1, 1, 1, 1, 3]]
[[1, 1], [4, 2, 2], [3, 3], [2, 2, 2], [0], [3, 2, 1], [3, 3, 3, 3], [4, 1, 1, 1, 1, 2, 2, 2], [4, 2, 2, 1, 1], [3, 3, 2, 1, 1]]

```

## Clarifications

* You may assume the input is non-empty and all values are positive or zero.
* You may choose any 2 distinct values for truthy or falsy, or output truthy/falsy using your language's convention (swapping is allowed). See the tag wiki

\*I've been told real chemistry is a lot more complex than this, but you can ignore the complexities in this challenge.

# Answer
# Python 3, ~~61 60 59 58~~ 51 bytes

```
lambda x:len(x)-2<~sum(x)%2*all(x)*sum(x)/2>=max(x)

```

Try it online!

-1 thanks to @Kevin Cruijssen

-7 thanks to @xnor

Uses theorem 2 from this paper.

It says a degree sequence is realizable as a connected multigraph with no self-loops if and only if it is `[0]`, or:

0. All degrees are positive.
1. The sum of the degree sequence is even.
2. The biggest degree is less than or equal to the sum of the rest of the degrees. That is, `sum(x)-max(x)>=max(x)`, or equivalently `sum(x)/2>=max(x)`
3. The number of edges, which is half the sum of degrees, is greater or equal to \\$n-1\\$, where \\$n\\$ is the number of vertices.

`~sum(x)%2*all(x)*sum(x)/2` is equal to `sum(x)/2` is the first two conditions are satisfied, and `0` otherwise.

If it is equal to `0`, it implies `len(x)-2<0>=max(x)`, so `len(x)==1, max(x)==0` and therefore `x==[0]`.

Otherwise, if the first two conditions are satisfied, it tests the third condition with `sum(x)/2>=max(x)`, and the fourth with `len(x)-2<sum(x)/2` (which is equivalent to `len(x)-1<=sum(x)/2` since these are integers according to the second condition).
> 27 votes

# Answer
# Wolfram Language (Mathematica), 134 bytes

Thanks to all for the motivation to immerse in graph theory! It is wonderful that there is a numerical criterion for connected multigraph. But I was wondering how it worked.
So I didn’t make a port of the same theorem, but I found *an algorithm* that allows you to build a multigraph, if it's possible, or give a message that you can’t. Having studied this article.
Here is the full-code version of Theorem 7 from the paper. It takes list of degrees and print out:

* Render of graph and `True`, if it's possible to make connected multigraph
* Graph and `False`, if only non-connected result is possible
* `None`, if list of degrees is non-graphic

```
multiGraphFromDegrees[degrees_List] :=
  Module[{n = Length@degrees, graph = Graph[{}]},
   data = MapThread[{#1, #2} &, {degrees, Range@n}];
   While[n > 1,
    data = ReverseSortBy[data, First];
    data[[1, 1]] -= 1; data[[n, 1]] -= 1;
    graph =
     EdgeAdd[graph, UndirectedEdge[data[[1, 2]], data[[n, 2]]]];
    data = Select[data, #[[1]] > 0 &];
    n = Length@data;
    ];
   If[n > 0, Print["None"],
    Row[{graph, " Connected: ", ConnectedGraphQ@graph}]
    ]];

```

Example `[1, 1, 1, 1, 1, 3]`:

Example `[3, 3, 3, 3]`:

Example `[6, 6, 4]`:

Example `[5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]`:

Note, that algorithm makes *some example* of graph, if it's possible. So for `[3,3,3,3]` we have not Tetrazet, but other valid chemical. Also result *may be non-planar*, but it's OK for chemicals too.

And here is short version, directly answers the question of challenge (`True` or `False`):

```
(d=#;n=Length@#;Catch[While[n>1,d=ReverseSort[d];d[[1]]-=1;d[[n]]-=1;d=Select[d,#>0&];m=Length@d;If[n-m==2,Throw[False],n=m]]];d=={})&

```

If anyone is interested, I’ll describe the algorithm a little more.

Try it online!
> 7 votes

# Answer
# , ~~58~~ ~~51~~ 45 bytes

*Edit: -6 bytes thanks to pajonk*

```
\(x,`+`=sum)max(+x^0-1,x)<=all(x)*+x/2*!+x%%2

```

Attempt This Online!

Based on xnor's comment on Command master's Python answer: upvote that!
> 6 votes

# Answer
# Jelly, 13 bytes

Uses S. L. Hakimi's result as aired by Command Master in their excellent Python answer.

```
ẠȧSH_L’»ṀƲeŻ$

```

A monadic Link that accepts a list of non-negative integers and yields `1` if a molecule may be formed or `0` if not.

**Try it online!**

### How?

```
ẠȧSH_L’»ṀƲeŻ$ - Link: non-empty list of non-negative integers, D
Ạ             - all (D)? -> 0 if any of D are zero
  S           - sum (D)
 ȧ            - (all?) logical AND (sum)
   H          - halve (that) - call this X
         Ʋ    - last four links as a monad - f(D):
     L        -   length (D)
      ’       -   decrement
        Ṁ     -   maximum (D)
       »      -   (length-1) maximum (maximum(D)) - call this Y
    _         - (X) subtract (Y)
            $ - last two links as a monad - f(Q=that)
           Ż  -   zero range (Q) -> list of integers = [0..floor(Q)] (empty if Q < 0)
          e   -   (Q) exists in (that)?

```
> 6 votes

# Answer
# JavaScript (ES6), 67 bytes

Based on the theorem found by @CommandMaster.

Returns `1` for falsy or `0` for truthy.

```
a=>a.some(v=>!(s+=v,k++,m>v?v:m=v)&a>'0',m=k=s=0)|2*k>s+3|s<m*2|s%2

```

Try it online!
> 5 votes

# Answer
# 05AB1E, 16 bytes

```
OÉ›¦IO;IàIg<‚@«P

```

Port of *@CommandMaster*'s Python answer, so make sure to upvote him/her as well!

Try it online or verify all test cases.

**Explanation:**

```
O           # Get the sum of the (implicit) input-list
 É          # Pop and check whether it's odd (0 if even; 1 if odd)
  ›         # Check for each value in the (implicit) input-list whether it's larger
            # (so the sum is even and none are 0)
   ¦        # Remove the very first check (for edge-case input=[0])
IO          # Push the sum of the input-list again
  ;         # Halve it
        ‚   # Pair
   Ià       # the maximum of the input-list
     Ig<    # with the length-1 of the input-list
         @  # Check [sum/2>=max, sum/2>=length-1]
«           # Merge this pair to the earlier list of checks
 P          # Check if all are truthy by taking the product
            # (after which the result is output implicitly)

```
> 4 votes

# Answer
# Thunno `D`, \\$ 21 \log\_{256}(96) \approx \\$ 17.29 bytes

```
XDS2%!>xS2/xMxL1-ZPpP

```

Attempt This Online! or verify all test cases

Based on Command Master's answer. Somehow passes all the test cases.

Outputs \\$0\\$ for falsy and \\$1\\$ for truthy.

#### Explanation

```
XDS2%!>xS2/xMxL1-ZPpP  # Implicit input
XD                     # Store input in x for later
  S2%!                 # Sum is even?
      >                # Is the input greater than this?
       xS2/            # Divide the sum by 2
           xM          # Push the maximum of x
             xL1-      # Get the length and decrement
                 ZP    # Pair together
                   pP  # Sum / 2 greater than or equal to both?
                       # Implicit output

```
> 4 votes

# Answer
# Arturo, 52 bytes

```
$[a][s:∑a(0=s%2)∧(>=s/2max a)∧(-size a 2)<s/2]

```

Thanks to S. L. Hakimi for solving the problem back in 1962 and @CommandMaster for finding the solution and explaining the relevant bits so clearly.
> 4 votes

# Answer
# Nekomata \+ `-e`, 13 bytes

```
∑2¦$ṁ±*$:#←c≥

```

Attempt This Online!

A port of @Command Master's Python answer.

The flag `-e` set the interpreter to `CheckExistence` mode, which prints `True` if the computation has any result, and `False` otherwise.

```
∑2¦$ṁ±*$:#←c≥

∑2¦              Divide the sum of the input by 2. Fail if the remainder is not zero.
   $ṁ±*          Multiply it by the sign of the minimum element of the input.
            ≥    Check if the result is greater than or equal to all items of the following list:
       $:#←c       Prepend the length minus 1 to the input

```

---

# Nekomata \+ `-e`, 18 bytes

```
ʷ{P↕1:Ð-:C0=+?}0U=

```

Attempt This Online!

This is extremely slow and takes up a lot of memory.

The idea is to repeatedly delete one edge at a time, until the result equals to `[0]`.

```
ʷ{P↕1:Ð-:C0=+?}0U=

ʷ{            }       Repeat the following function until it fails:
  P                     Fails unless the result is all positive.
   ↕                    Non-deterministically permute the list.
    1:Ð-                Decrement the first two elements of the list.
        :C0=+?          Drop the first element of the list if it is zero.
               0U=    Check if the result is equal to [0].

```
> 4 votes

# Answer
# Vyxal, 17 bytes

Based on Command Master's answer

```
∑₂?sṫ$∑≤?∑½?L‹≥WA

```

```
∑₂?sṫ$∑≤?∑½?L‹≥WA
∑₂                  Is the sum of the list even?
  ?sṫ$∑≤            Sort list, swap and sum tail-removed part, is lesser than or equal?
        ?∑½?L‹≥     Is length of list - 1 greater than or equal to half of the sum
               WA   Wrap stack, all truthy?

```

Try it Online!
> 3 votes

# Answer
# TI-Basic, 28 bytes

```
max(dim(Ans)-1,max(Ans))≤min(Ans>0).5sum(Ans)not(fPart(.5sum(Ans

```

Takes input in `Ans`. Uses the same method as in Command Master's Python 3 answer.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 67 bytes

```
Length@x-2<BitNot[Tr@x]~Mod~2*If[AllTrue[x,#>0&],1,0]*Tr@x/2>=Max@x

```

Try it online!

A port of @Command Master's answer.

Explicit Mathematica Code is

```
f[x_List] := Module[{len, bitNotSumMod, allPositive, halfSum, maxVal},
    len = Length[x] - 2;
    bitNotSumMod = BitNot[Total[x]] ~Mod~ 2;
    allPositive = If[AllTrue[x, # > 0 &], 1, 0];
    halfSum = Total[x] / 2;
    maxVal = Max[x];

    len < bitNotSumMod * allPositive * halfSum >= maxVal
]

```
> 2 votes

# Answer
# Charcoal, 20 bytes

```
¬∨﹪Σθ²‹∧⌊θΣθ⊗⌈⊞Ｏθ⊖Ｌθ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a valid chemical, nothing if not. Explanation: Based on @CommandMaster's Python answer.

```
    θ                    Input list
   Σ                     Sum
  ﹪                      Modulo
     ²                   Literal integer `2`
 ∨                      Logical Or
         θ              Input list
        ⌊               Minimum
       ∧                Logical And
           θ            Input list
          Σ             Sum
      ‹                 Is less than
                   θ    Input list
                  Ｌ     Length
                 ⊖      Decremented
              ⊞Ｏ        Appended to
                θ       Input list
             ⌈          Maximum
            ⊗           Doubled
¬                       Logical Not
                        Implicitly print

```
* `len(x) - 2 < ~sum(x) % 2 * all(x) * sum(x) / 2 >= max(x)` becomes
* `~sum(x) % 2 * all(x) * sum(x) / 2 >= max(*x, len(x) - 1)` becomes
* `~sum(x) % 2 * all(x) * sum(x) >= 2 * max(*x, len(x) - 1)` becomes
* `not(~sum(x) % 2 * all(x) * sum(x) < 2 * max(*x, len(x) - 1))` becomes
* `not(sum(x) % 2 or all(x) * sum(x) < 2 * max(*x, len(x) - 1))` becomes
* `not(sum(x) % 2 or (min(x) and sum(x)) < 2 * max(*x, len(x) - 1))`.
> 1 votes

---
Tags: code-golf, array, decision-problem, graph-theory, chemistry
---