title: When is Hannukah?

text:
# Question
Title: When is Hannukah?
# Input

The input will be a year between 1583 and 2239. We just want to know when Hannukah was or will be in that year. This is information used by millions of people every year and put in calendars across the world. What could be easier?

# Output

The Gregorian date of the first **evening** of Hannukah that year. That is the day before the first full day of Hannukah. Your code should output the month and day of the month in any easy to understand human readable form of your choice.

# Examples

```
1583    December 9
2013    November 27
2014    December 16
2015    December 6
2016    December 24
2017    December 12
2018    December 2
2019    December 22
2020    December 10
2021    November 28
2022    December 18
2023    December 7
2024    December 25
2025    December 14
2026    December 4
2027    December 24
2028    December 12
2029    December 1
2030    December 20
2031    December 9
2032    November 27
2033    December 16
2239    December 21

```

It could hardly be simpler. We start with a couple of definitions:

We define a new inline notation for the division remainder of \\$x\\$ when divided by \\$y\\$: $$(x|y)=x \bmod y$$

For any year Gregorian year \\$y\\$, the *Golden Number*, $$G(y) = (y|19) + 1$$ For example, \\$G(1996)=2\\$ because \\$(1996|19)=1\\$.

To find \\$H(y)\\$, the first evening of Hannukah in the year \\$y\\$, we need to find \\$R(y)\\$ and \\$R(y+1)\\$, the day of September where *Rosh Hashanah* falls in \\$y\\$ and in \\$y+1\\$. Note that September \\$n\\$ where \\$n≥31\\$ is actually October \\$n-30\\$.

$$R(y)=⌊N(y)⌋ + P(y)$$ where \\$⌊x⌋\\$ denotes \\$x-(x|1)\\$, the integer part of \\$x\\$, and

$$N(y)= \Bigl \lfloor \frac{y}{100} \Bigr \rfloor - \Bigl \lfloor \frac{y}{400} \Bigr \rfloor - 2 + \frac{765433}{492480}\big(12G(y)|19\big) + \frac{(y|4)}4 - \frac{313y+89081}{98496}$$

We define \\$D\_y(n)\\$ as the day of the week (with Sunday being \\$0\\$) that September \\$n\\$ falls on in the year \\$y\\$. Further, Rosh Hashanah has to be postponed by a number of days which is

$$P(y)=\begin{cases} 1, & \text{if } D\_y\big(\lfloor N(y)\rfloor \big)\in\\{0,3,5\\} & (1)\\ 1, & \text{if } D\_y\big(\lfloor N(y)\rfloor\big)=1 \text{ and } (N(y)|1)≥\frac{23269}{25920} \text{ and } \big(12G(y)|19\big)\>11 & (2)\\ 2, & \text{if } D\_y\big(\lfloor N(y)\rfloor \big)=2 \text{ and } (N(y)|1)≥\frac{1367}{2160} \text{ and } (12G(y)|19)\>6 & (3)\\ 0, & \text{otherwise} & (4) \end{cases}$$

For example, in \\$y=1996\\$, \\$G(y)=2\\$, so the \\$N(y)\approx13.5239\\$. However, since September 13 in 1996 was a Friday, by Rule \\$(1)\\$, we must postpone by \\$P(y)=1\\$ day, so Rosh Hashanah falls on Saturday, September 14.

Let \\$L(y)\\$ be the number of days between September \\$R(y)\\$ in the year \\$y\\$ and September \\$R(y+1)\\$ in year \\$y+1\\$.

The first evening of Hannukah is:

$$ H(y)=\begin{cases} 83\text{ days after }R(y) & \text{if } L(y)\in\\{355,385\\}\\ 82\text{ days after }R(y) & \text{otherwise} \end{cases} $$

# Notes and thanks

Your code may not access the Internet to get the answer using e.g. an online Hebrew calendar calculator.

Thank you to @Adám for pointing me to the rules and for a great deal of help. To keep things simple, this challenge assumes the location to be Jerusalem.

For those now intrigued by the math of the Hebrew calendar, see https://docs.microsoft.com/en-us/dotnet/api/system.globalization.hebrewcalendar?view=netframework-4.8 .

# Answer
> 8 votes
# JavaScript (ES6),  ~~188 ... 168~~  160 bytes

*Assumes that the system is set up to UTC time (as the TIO servers are)*

Returns a Date instance.

```
y=>(D=d=>new Date(y,8,n+=d))(((g=y=>D((n=80,d=D((3*-~(y/100)>>2)+1.554*(x=12*-~y%19)+y%4/4-y/314.6-.9).getDay())%2+2*(n%!d>.63&x>6))/864e5)(++y)-g(--y)+5)%30<1)

```

Try it online!

Or test it against a more literal implementation

### How?

The approximations described below are guaranteed to work for \\$665\le y\le 5510\\$, which is a significantly larger interval than the requested one.

* Instead of computing:

$$k=\left\lfloor\frac{y}{100}\right\rfloor-\left\lfloor\frac{y}{400}\right\rfloor-2$$

we compute \\$k+2\\$ with:

```
3 * -~(y / 100) >> 2

```

This off-by-two error is left uncorrected. We just need to adjust the final offset accordingly, as well as the tests about the day of the week. It has no impact on \\$L(y)\\$.
* An offset of \\$80\\$ days is added right away to all date calculations, which introduces an additional shift of \\$3\\$ more days (\\$80\bmod7\\$) in the days of the week.

Therefore, the index \\$d\\$ for the day of the week is \\$5\\$ for Sunday, \\$6\\$ for Monday, \\$0\\$ for Tuesday, \\$1\\$ for Wednesday, \\$2\\$ for Thursday, \\$3\\$ for Friday, or \\$4\\$ for Saturday.

Very conveniently, it leads to the following properties:

+ rule \\$(1)\\$ for \\$P(y)\\$: the day is either Sunday, Wednesday or Friday iff \\$d\\$ is odd
    + rule \\$(3)\\$ for \\$P(y)\\$: the day is Tuesday iff \\$d=0\\$
* We use \\$1.554\\$ as an approximation of \\$\dfrac{765433}{492480}\\$.
* We use \\$\dfrac{y}{314.6}+0.9\\$ as an approximation of \\$\dfrac{313y+89081}{98496}\\$.
* The test about \\$D\_y(\lfloor N(y)\rfloor)\\$ being equal to \\$1\\$ is ignored entirely, as the result cancels out with the other criteria.
* We use \\$0.63\\$ as an approximation of \\$\dfrac{1367}{2160}\\$.
* Instead of testing \\$L(y)\in\\{355,385\\}\\$, we test \\$\big(L(Y)+5\big)\bmod30=0\\$.

# Answer
> 3 votes
# C# (Visual C# Interactive Compiler), 108 bytes

An alternate version suggested by @Adám, with a distinct output format for the edge case 2239.

```
using System.Globalization;string f(int y)=>y<2239?new DateTime(y+3761,3,24,new HebrewCalendar())+"":"1221";

```

Try it online!

---

# C# (Visual C# Interactive Compiler),  ~~134 130 122~~  121 bytes

*Saved 8 bytes thanks to @Hedi*
*Saved 1 byte thanks to @Adám*

My first C# program either... \o/

Returns a DateTime instance.

```
using System.Globalization;dynamic f(int y)=>y<2239?new DateTime(y+3761,3,24,new HebrewCalendar()):new DateTime(y,12,21);

```

Try it online!

# Answer
> 2 votes
# Perl 5, ~~313~~ 278 bytes

```
sub f{sub t{timegm_nocheck(0,0,0,pop,8,pop)}$Y=pop;eval'(R,N,Q)=map{X=12*(_%19+1)%19;N=1.554*X-2.9-_/314.4+_%4/4+_/100%99-_/400%9;I=intN;D=t(_,I)/86400%7;M=N-I;P=D=~/[361]/||D==4&&M>1?1:D==5&&M>=.63&&X>6?2:0;t(_,I+P),I+P}Y,Y+1;t(Y,N+82+((Q-R)/432e3)=~/1|7$/)'=~s/[A-Z_]/\$$&/gr}

```

Try it online!

Based on @Arnauld's javascript answer.

Slightly ungolfed:

```
sub f{
  sub t{timegm_nocheck(0,0,0,pop,8,pop)}            #xth sep y => secs after jan 1 1970
  $Y=pop;                                           #input year
  eval'                                             #eval code string to use code without $
    (R,N,Q) = map {                                 #R,N=rosh for curr Y. Q for Y+1
      X=12*(_%19+1)%19;
      N=1.554*X-2.9-_/314.4+_%4/4+_/100%99-_/400%9; #%99 cuts decimals, int() for small nums
      I=intN;
      D=t(_,I)/86400%7;                             #D=weekday - 4, 3=sun 6=wed 8=1=fri ...
      M=N-I;                                        #M=N%1 (perl dont support
      P=D=~/[361]/||D==4&&M>1?1:D==5&&M>=.63&&X>6?2:0;
      t(_,I+P),I+P
    }
    Y, Y+1;
    t(Y,N+82+((Q-R)/432e3)=~/1|7$/)
  ' =~ s/[A-Z_]/\$$&/gr                             #inserts $ before every uppercase A-Z and _
}

```

# Answer
> 2 votes
# APL (Dyalog Unicode), ~~86~~ 85 bytesSBCS

Now that Arnauld has posted his C# solution, I can reveal my equivalent anonymous tacit prefix function.

```
⎕NEW{⎕USING←'System'⋄0::1221⋄⍺⍺DateTime((3761+⍵)3 24,⍺⍺Globalization.HebrewCalendar)}

```

Can't try it online as this only works under Windows. (.NET Core support is planned for this year!)

`⎕NEW{``}` function derived from monadic operator with `⎕NEW` (create new instance of object) as operand:

`⎕USING←'System'` make the members of .NET's root namespace's immediately available

`⋄0::1221` upon any error, return this number

Try:

`⍺⍺DateTime(``)` create a new DateTime object with the following constructor arguments:

`⍺⍺Globalization.HebrewCalendar` create a new HebrewCalendar object

`(``)3 4,` prepend the list ending with `[``,3,4]` where the first element is:

`3761+⍵` the argument adjusted for the difference between the civil and Hebrew calendars' years

---
Tags: code-golf, date
---


title: Convert Character Substrings to Numeric

text:
# Question
Title: Convert Character Substrings to Numeric
I often have to take character data and categorize it numerically at work. A common thing I do is to take character type variables and convert them to numeric type characters, keeping same categories according to the level of work I'm doing. (The longer the substring, the more in depth and specific, shorter substrings for broad level). Enough backstory...

The challenge: **In as few bytes as possible,** convert the input part A, *a vector/list of unique strings*, into the output, a *vector/list of numbers*, keeping unique categories within the length of substrings the same length, which is input part B. Feel free to ask questions for clarification.

**Input:**

1. w, Vector/list of unique strings of equal character length. `n <= 10`

* These strings may be any combination of uppercase letters and numbers. Sorry if it seems my examples follow a pattern, I just created them after a similar pattern I see in the data I work with.
    * Some random examples of what input could look like: "A1", "7LJ1", "J426SIR", "4AYE28TLSR", or any other random combination of uppercase letters up to 10 characters. To repeat: Each element in the vector/list will be the same length.
    * Input may already be ordered by group, or non-contiguous, meaning elements lying within one group may be separated by elements of a different group. (See example 2)
2. s, where `1 <= s <= n`

**Output:**

Output should have the indexes of the sorted, de-duplicated, trimmed values. See example 2. (I've included comments in my output to clarify, this is not required) This can be 0-based or 1-based index, as per your language uses.

**Example Input 1:**

```
#Input already alphabetized, but this input is not always guaranteed

s = 3, w =
[ABC01,
 ABC11,
 ABC21,
 ABD01,
 ABE01,
 ABE02,
 ACA10,
 ACA11,
 ACB20,
 ACB21]

```

**Example Output 1:**

```
[1, #ABC
 1,
 1,
 2, #ABD
 3, #ABE
 3,
 4, #ACA
 4,
 5, #ACB
 5]

```

**Example Input 2:** s = 4, w =

```
[X1Z123,
 X1Z134,
 X1Y123,
 X1Y134,
 X1Y145,
 X1Y156,
 X1X123,
 X1X124,
 X1X234,
 X2Z123,
 X2Z134,
 X1X255,
 X1Y124,
 X2Z222,
 X2Z223,
 X2Z224]

```

**Example 2 Output:**

```
#Categorize by order of appearance
[1, #X1Z1
 1,
 2, #X1Y1
 2,
 2,
 2,
 3, #X1X1
 3,
 4, #X1X2
 5, #X2Z1
 5,
 4, #X1X2 again (to show input can be non-contiguous)
 2, #X1Y1 again
 6, #X2Z2
 6,
 6]

OR

#Input not alphabetized, but indexes still match original input indexes.
[4, #X1Z1
 4,
 3, #X1Y1
 3,
 3,
 3,
 1, #X1X1
 1,
 2, #X1X2
 5, #X2Z1
 5,
 2, #X1X2 again (to show input can be non-contiguous)
 3, #X1Y1 again
 6, #X2Z2
 6,
 6]

```

# Answer
> 3 votes
# APL (Dyalog Extended), ~~8~~ ~~7~~ 6 bytesSBCS

Anonymous infix function. Takes `s` as left argument and `w` as a list of strings as right argument.

```
∪⍛⍳⍨↑¨

```

Try it online!

take the first `s` characters from…
`¨` each string in `w`

`∪⍛` in the list of the nique strings in that…
find the **ɩ**ndex of the first occurrence of each string

# Answer
> 2 votes
# Japt, 9 bytes

```
®¯V
m!bUâ

```

Try it

# Answer
> 2 votes
## bash, 44 bytes

```
cut -c-$1|awk '{print(x=a[$0])?x:a[$0]=++b}'

```

Try it online!

`cut` takes the first *s* characters, then `awk` remembers strings it's seen before and assigns them to `++b` otherwise.

# Answer
> 2 votes
# Jelly, 6 bytes

```
ḣ€µQiⱮ

```

A dyadic Link accepting a list on the left and an integer on the right which yields a list of integers.

**Try it online!**

# Answer
> 2 votes
# Ruby, ~~47~~ 46 bytes

Uses 0-indexing in the order of appearance.

```
->s,w{w.map!{|e|e[0,s]}.map{|e|(w&w).index e}}

```

Try it online!

```
->s,w{w.map!{|e|e[0,s]}.map{|e|(w&w).index e}}
->s,w{                                       }  # Proc that takes 2 arguments
      w.map!{|e|e[0,s]}                         # Replace each element of w with its prefix
                       .map{|e|             }   # For each element in the modified w
                               (w&w)            #  Deduplicated copy of the modified w
                                    .index e    #  Get the element's index in the dedup copy

```

# Answer
> 1 votes
# , ~~18~~ ~~14~~ 13 bytes

```
[:(~.i.]){."1

```

Try it online!

* `{."1` Extract first `s` of each item
* `(~.i.])` Within the uniq of that list `~.` find the index of `i.` every item `]`

# Answer
> 1 votes
# Python 2, ~~94~~ 65 bytes

```
def f(w,A):A=[a[:w]for a in A];return map(sorted(set(A)).index,A)

```

Try it online!

A whopping 29 bytes thx to Value Ink.

Uses 0-indexing; returns the index of the sorted list of possibilities (as per Example 2, alternate output).

# Answer
> 0 votes
# Charcoal, 17 bytes

```
≧…θηＩＥη⌕Φη¬№…ημλι

```

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

```
≧…θη

```

Truncate each string to the given length.

```
ＩＥη⌕Φη¬№…ημλι

```

Map over each string, finding its position in the filtered list given by the first occurrence of each string in the list, and cast the results to string for implicit print.

# Answer
> 0 votes
# JavaScript (V8), 68 bytes

```
(z,L)=>(L=L.map(x=>x.slice(0,z))).map(x=>[...new Set(L)].indexOf(x))

```

Try it online!

0-indexed in order of appearance

```
(z,L)=>                      input : z= number of characters, L=list
(L=L.map(x=>x.slice(0,z)))   cut L saving it.
.map(x=>[... ].indexOf(x))   maps the result indexing in :
        [...new Set(L)]      builds an iterable object out of the Set of L

```

# Answer
> 0 votes
# 05AB1E, 6 bytes

```
€£DÙsk

```

String-list \\$w\\$ as first input, and integer \\$s\\$ as second input.
Output is categorized by order of appearance, and uses 0-based indexing.

Try it online or verify all test cases.

Output could also be categorized by alphabetical order for **6 bytes** as well, by changing the `Ù` to `ê`.

Try it online or verify all test cases.

**Explanation:**

```
€       # For each string in the (implicit) input-list:
 £      #  Only leave the first (implicit) input-integer amount of characters
  D     # Then duplicate this list of strings
   Ù    # Uniquify the list
   ê    # (Alternative: Uniquify AND sort the list)
    s   # Swap to get the duplicated list again
     k  # And get the (0-based) index of each in the unified list
        # (after which the result is output implicitly)

```

# Answer
> 0 votes
# , 40 bytes

```
function(w,s)c(factor(substring(w,1,s)))

```

Try it online!

`c()` has the odd behavior of coercing its arguments into the lowest possible one in the following hierarchy:

```
NULL < raw < logical < integer < real < complex < character < list < expression

```

`factors` are internally held as `integers`, so this coerces to an integer list.

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


# Question
Title: Dissect a word and arrange all its letters in alphabetical order
**Question**

Write a program to accept one string on the console only and print back its letters arranged in alphabetical order. The string must only have the following characters:

> 0123456789abcdefghijklmnopqrstuvwxyz

**Rules**

The ascending alphabetical order is defined in the given string.

All repeated characters must be printed.

If the string contains characters other than the ones mentioned above, it must display "Invalid input".

This is code-golf, so shortest answer in bytes wins.

Standard loopholes are forbidden.

A null string "" will output "Invalid input".

Your program must be executable and not a function or snippet.

Boilerplate is not required.

**Examples**

```
"dragon"--> adgnor
"skoda3ferrari"--> 3aadefikorrrs
"ferret"--> eefrrt
"werewolf92"--> 29eeflorww
"@hog"--> Invalid input
"gTa5"--> Invalid input
"  l "--> Invalid input
""--> Invalid input

```

Edit: The double quotes are given for clarification.

May the force be with you. Good luck!

# Answer
# 05AB1E, ~~16~~ 15 bytes

*-1 byte thanks to Kevin Cruijssen*

```
žKlsSåßi{ë”Í¼î®

```

Try it online!
> 6 votes

# Answer
# Python 3.8 (pre-release), ~~77~~ ~~75~~ ~~74~~ 88 bytes

```
import re
print(*re.match('[0-9a-z]+$',i:=input())and sorted(i)or'Invalid input',sep='')

```

Try it online!
> 4 votes

# Answer
# APL (Dyalog Extended), 37 bytesSBCS

```
{0∊(≢⍵),⍵∊⎕D,⌊⎕A:'Invalid input'⋄∧⍵}⍞

```

Try it online!

prompt for text input from the console

`{``}` apply the following anonymous lambda to that:

`⎕A` the uppercase **A**lphabet

**L**owercase that

`⎕D,` prepend the digits

`⍵∊` for each character of the argument, indicate if it is a member thereof

`(``),` prepend the following:

`≢⍵` the tally of characters in the argument

`0∊``:` if zero is a member thereof:

`'Invalid input'` return (and implicitly print) this message

else:

`∧⍵` sort the argument ascending
> 4 votes

# Answer
# Burlesque, 37 bytes

```
><JJann!/^zz!=||{vv"Invalid Input"}if

```

Try it online!

```
><                    # Sort input string
JJ                    # Duplicate twice
ann!                  # Not alphanumeric
/^                    # Swap and duplicate (sorted string)
zz!=                  # Lowercased not equal to original (i.e. contains uppercase)
||                    # Or
{vv"Invalid Input"}if # If not alphanumeric or lowercase drop sorted list
                        and output invalid input

```
> 4 votes

# Answer
# x86-16 machine code, IBM PC-DOS, ~~81~~ 80 bytes

**Binary:**

```
00000000: b40a ba4f 01cd 218b f2ad 8bd6 8acc 8be9  ...O..!.........
00000010: 938b f28b fe51 ad3c 307c 0c3c 397e 0e3c  .....Q.<0|.<9~.<
00000020: 617c 043c 7a7e 06ba 4201 59eb 103a c47c  a|.<z~..B.Y..:.|
00000030: 0286 c4ab 4e4f e2de 59e2 d688 1bb4 09cd  ....NO..Y.......
00000040: 21c3 496e 7661 6c69 6420 696e 7075 7424  !.Invalid input$

```

Build and test `DISSECT.COM` using `xxd -r`

**Unassembled listing:**

```
B4 0A           MOV  AH, 0AH            ; DOS read buffered input from STDIN
BA 014F R       MOV  DX, OFFSET BUF     ; load buffer pointer
CD 21           INT  21H                ; get STDIN input
8B F2           MOV  SI, DX             ; buffer pointer into SI
AD              LODSW                   ; load char count into AH
8B D6           MOV  DX, SI             ; save start of string
8A CC           MOV  CL, AH             ; string length into CX
8B E9           MOV  BP, CX             ; save string length for later display
            OUTER_LOOP:
8B F2           MOV  SI, DX             ; reset SI to beginning of buffer
8B FE           MOV  DI, SI             ; reset DI to beginning of buffer
51              PUSH CX                 ; save outer loop counter
            INNER_LOOP:
AD              LODSW                   ; load next two chars into AH/AL
3C 30           CMP  AL, '0'            ; is char < '0' ?
7C 0C           JL   INVALID            ; if so, not valid
3C 39           CMP  AL, '9'            ; is char <= '9'?
7E 0E           JLE  VALID              ; if so, valid
3C 61           CMP  AL, 'a'            ; is char < 'a'?
7C 04           JL   INVALID            ; if so, not valid
3C 7A           CMP  AL, 'z'            ; is char <= 'z'?
7E 06           JLE  VALID              ; if so, valid
            INVALID:
BA 0142 R       MOV  DX, OFFSET INV     ; load address of "invalid" string
59              POP  CX                 ; discard saved counter
EB 11           JMP  OUTPUT             ; display "invalid" string
            VALID:
3A C4           CMP  AL, AH             ; compare chars
7C 02           JL   NO_SWAP            ; if AL < AH, do not swap
86 C4           XCHG AL, AH             ; otherwise, swap chars
            NO_SWAP:
AB              STOSW                   ; store chars back to buffer
4E              DEC  SI                 ; adjust SI to previous char
4F              DEC  DI                 ; adjust DI to previous char
E2 DE           LOOP INNER_LOOP         ; loop inner iterations
59              POP  CX                 ; restore outer loop counter
E2 D6           LOOP OUTER_LOOP         ; loop outer
C6 03 24        MOV  BYTE PTR[BP+DI],'$'; add string terminator
            OUTPUT:
B4 09           MOV  AH, 09H            ; DOS display string function
CD 21           INT  21H                ; write output to console
C3              RET                     ; exit to DOS

INV DB "Invalid input"                  ; "invalid" message string
BUF DB '$'                               ; buffer size is 36 bytes, also string terminator

```

Standalone PC DOS executable. Implements a simple bubble sort algorithm.

Input via console/`STDIN`, output to console/`STDOUT`.
> 4 votes

# Answer
# GolfScript, 37 bytes

```
.$\58,48>123,97>+-!*"Invalid input"or

```

Try it online!

## Explanation

Whoa. Maybe I shouldn't have done this..

.                                     # Make 2 copies of the input,
 $                                    # One is the sorted copy of the input,
  \58,48>123,97>+-!                   # Another is whether all of input is in the
                                      # lowercase alphanumeric range
                   *                  # Multiply them:
                                      #     If the input contains invalid characters,
                                      #     e.g. @hog, this multiplies the sorted copy by 0.
                                      # ----If the input is a null string,
                                      #     The input multiplies 0 by the null string,
                                      #     which is still the null string.
                                      # ----If the input is a valid string,
                                      #     e.g. dragon, the input multiplies the
                                      #     sorted copy by 1 (because everything is
                                      #     inside the range)
                    "Invalid input"or # Do a "logical magic":
                                      #     If the input is 0 or the null string,
                                      #         returns "Invalid input"
                                      #     Otherwise, this returns the
                                      #         sorted copy of the input.

# Further explanation of the code snippet
# \                 # Swap the stack so that an unused copy of the input emerges
#  58,              # Generate a range and drop the last: 0 to ASCII ':'
                    # (The previous character is '9')
#     48>           # Select everything that is larger than 48 (ASCII '0')
#        123,97>    # Same thing with generating 'a' to 'z'
#               +   # Join the inputs together
#                -  # Set subtraction: subtract this string from the fresh unused input
#                   # This results in everything that isn't alphanumeric
#                 ! # Negate the string. If the string has something,
#                   # it turns to 0. Otherwise it turns to 1.
```
</code></pre>
> 3 votes

# Answer
# Keg, 35 bytes

```
₳0a&᠀:(⑴|⑻-)⒃᠀⒃¬+[Invalid input|¿÷⑭

```

Nice to see Keg still "up to par" with Golfscript! *No regrets about the bad pun*
> 3 votes

# Answer
# Red, 86 bytes

```
func[s][a: charset[#"0"-#"9"#"a"-#"z"]either parse sort s[some a][s]["Invalid input"]]

```

Try it online!
> 3 votes

# Answer
# Jelly, 18 bytes

```
ɠfƑØBŒl¤ȧṢȯ“4{ẉṄi»

```

Try it online!

A full program that reads its input from STDIN and outputs to STDOUT.

If the input validation and requirement to use STDIN were removed, this would be a single byte:
> 3 votes

# Answer
# Perl 5 `-pF//`, 45 bytes

```
$_=/^[a-z\d]+$/?join"",sort@F:"Invalid Input"

```

Try it online!
> 3 votes

# Answer
# C++ (clang), <sup>~~223~~ \\$\cdots\\$ ~~182~~</sup> 170 bytes

Saved ~~8~~ a whopping 20 bytes thanks to ceilingcat!!!

```
#import<bits/stdc++.h>
int main(){std::string s,i="Invalid input";getline(std::cin,s);sort(begin(s),end(s));for(int c:s)s=c<48|c>122|c>57&c<97?i:s;std::cout<<(s[0]?s:i);}

```

Try it online!

A program that reads a single string from `stdin` (handling all invalid cases) and outputs to `stdout`.
> 2 votes

# Answer
# PHP, 92 bytes

```
$a=str_split($s=$argn);sort($a);echo preg_match('/^[a-z\d]+$/',$s)?join($a):'Invalid input';

```

Try it online!
> 2 votes

# Answer
# Charcoal, 37 bytes

```
≔⁺⭆χιβη¿∨¬θ⊙θ¬№ηιInvalid inputＦηＦ№θιι

```

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

```
≔⁺⭆χιβη

```

Concatenate the digits with the lowercase letters.

```
¿∨¬θ⊙θ¬№ηι

```

If the input is empty or contains a character not in the digit letter string, ...

```
Invalid input

```

... then output the required error message, ...

```
Ｆη

```

... else for each digit and lowercase letter...

```
Ｆ№θιι

```

... output each time it appears in the input.
> 2 votes

---
Tags: code-golf, alphabet, word-puzzle
---


# Question
Title: Caddyshack or: How to compress already-golfed code
In golf, a knowledgable caddie helps an already good golfer to be even better. In this challenge, you build a "caddie" to help you code golf. In particular, your caddie will compress golfed code in such a way that another program can uncompress and then run the code. A good caddie will compress golfed code to be much smaller than the original golfed code. In fact, in caddie-assisted Python (say), you might be able to golf on par with a Jelly golfer!

Formally, a **caddie** for a language L is a pair (E,D) of programs. The program E takes as input any code c in L and outputs a string s. The program D takes s as input along with any input x of c and returns the output of c(x). We do not require E and D to be written in L. You could say that E is a transpiler that converts c into a version s that runs in the language D. We are interested in transpilers E for which E(c) tends to be smaller than c, even when c is already golfed.

Write a caddie (E,D) for any language L of your choosing. When you first post a caddie here, its score is infinity. Use the following method to update your score:

* Let C denote the challenge in with at least 10 points that was posted first after your submission.
* Let c denote the shortest posted solution to C that is written in L.
* Your score is infinity unless C and c both exist, at which point your score is size(E(c))/size(c).

Recompute your score whenever either C or c changes. Lowest score wins.

# Answer
# Python 3 Caddy, interprets BrainF\***

# Score: \\$\frac{38}{224}\approx0.17\\$ (with newlines removed)

## Program E

```
from textwrap import wrap

x = input('Code: ')
i = ['<', '>', '+', '-', '[', ']', '.', ',']
o = ''
for c in x:
    if c in i:
        o += str(i.index(c) + 1)
if o:
    d = wrap(o, 6)
    d = [int(x) for x in d]
    o = ''
    for c in d:
        o += chr(int(c) + 128)
print('Compressed: ', o)

```

The way this works is by converting every instruction in the input to a digit, then concatenating those digits to a number. Then it splits that number into 6-digit groups and converts each to a Unicode character. (A number higher than 6 could be used, by that would cause errors for large programs). Then it outputs it.

## Program D

```
x = input('Compressed: ')
p = input('Input: ')
p = list(p)
d = ''
for c in x:
    c = ord(c) - 128
    d += str(c)
d = d.replace('-', '')
i = ['<', '>', '+', '-', '[', ']', '.', ',']
o = ''
for n in d:
    n = int(n) - 1
    o += i[n]
tape = [0] * 30000
head = 0
m = {}
m2 = {}
stack = []
for i in range(len(o)):
    char = o[i]
    if char == '[':
        stack.append(i)
    elif char == ']':
        begin = stack.pop()
        m[begin] = i + 1
        m2[i] = begin
i = 0
while i < len(o):
    char = o[i]
    if char == '<':
        head -= 1
        i += 1
    elif char == '>':
        head += 1
        i += 1
    elif char == '+':
        tape[head] += 1
        i += 1
    elif char == '-':
        tape[head] -= 1
        i += 1
    elif char == '[':
        if tape[head] == 0:
            i = m[i]
        else:
            i += 1
    elif char == ']':
        if tape[head] != 0:
            i = m2[i]
        else:
            i += 1
    elif char == '.':
        print(chr(tape[head]), end='')
        i += 1
    elif char == ',':
        try:
            tape[head] = ord(p.pop(0))
        except:
            tape[head] = 0
        i += 1

```

This is pretty simple, it just reverses the compression algorithm and evaluates the result.
> 2 votes

---
Tags: code-challenge, compression
---


title: Build a "BizzFuzz" program

text:
# Question
Title: Build a "BizzFuzz" program
In traditional FizzBuzz, you are asked to print the numbers from 1 to 100, but replacing every multiple of 3 with "Fizz", every multiple of 5 with "Buzz", and every multiple of both 3 and 5 (i.e. 15) with "FizzBuzz".

However, as an evil interviewer, I've invented my own twisted version of FizzBuzz, which I've decided to name BizzFuzz and give to you in a coding interview.

The rules of the game are:

* Print each number from 1 to 100, except if the number meets one of the conditions below.

+ If the number is divisible by 4, print "Fizz".
    + If the number is divisible by 5, print "Buzz".
    + If the number is divisible by 4, but the number immediately *after* it is divisible by 5, print "FizzBuzz" instead of "Fizz", and print the next number regularly.
    + If the number is divisible by 5, but the number immediately *after* it is divisible by 4, print "BuzzFizz" instead of "Buzz", and print the next number regularly.
    + If the number is immediately *before* a number divisible by both 4 and 5, print "Bizz".
    + If the number is immediately *after* a number divisible by both 4 and 5, print "Fuzz".
    + If the number is divisible by both 4 and 5, print "BizzFuzz".

The shortest code to implement all these rules in any language wins.

# Answer
> 4 votes
## GolfScript (83 80 chars)

(NB Howard's suggestion in the comments allows to reduce to 78 chars, but with trailing spaces on some lines).

This uses the character `\0`, so here it is in xxd format:

```
0000000: 3130 302c 7b29 2e32 3025 2742 6946 750a  100,{).20%'BiFu.
0000010: 0046 750a 0000 0046 6942 750a 0000 0000  .Fu....FiBu.....
0000020: 4669 0a00 0042 750a 0000 4669 0a00 0000  Fi...Bu...Fi....
0000030: 4275 4669 0a00 0000 0042 690a 2731 2c2f  BuFi.....Bi.'1,/
0000040: 3d32 2f27 7a7a 272a 5c6e 2b6f 727d 2f0a  =2/'zz'*\n+or}/.

```

and base64:

```
MTAwLHspLjIwJSdCaUZ1CgBGdQoAAABGaUJ1CgAAAABGaQoAAEJ1CgAARmkKAAAAQnVGaQoAAAAA
QmkKJzEsLz0yLyd6eicqXG4rb3J9Lwo=

```

Using **^** as a stand-in for `\0`, it's

```
100,{).20%'BiFu
**^**Fu
**^****^****^**FiBu
**^****^****^****^**Fi
**^****^**Bu
**^****^**Fi
**^****^****^**BuFi
**^****^****^****^**Bi
'1,/=2/'zz'*\n+or}/
```

Still not a particularly interesting problem.

---

An explanation was requested:

For values `0` to `99` inclusive:

```
100,{
...
}/

```

Increment the value (we want `1` to `100`) and also find out what the incremented value is `mod 20`:

```
).20%

```

Split the magic string around `\0` characters:

```
MAGIC_STRING 1,/

```

Take the (`x mod 20`)th element of that array, split it into 2-character chunks, and glue them back together with `zz`. Note: the string is either empty (in which case there are no chunks, so we end up with the empty string) or is a sequence of `[BF][iu]` prefixes followed by a newline.

```
=2/'zz'*

```

Take the other copy of the incremented number which we kept on the stack, and append a newline. Now whichever string we keep will end with a newline.

```
\n+

```

Apply a fallback operation. (This is similar to `||` in JavaScript or `COALESCE` in SQL).

```
or

```

# Answer
> 18 votes
## Python, 114

```
a='Fizz'
b='Buzz'
c='Bizz'
d='Fuzz'
e=c+d
f=a+b
g=b+a
i=1
exec"print eval('ediifiiiaibiaiigiiic'[i%20]);i+=1;"*100

```

Original solution (**131**):

```
f='Fizz'
for i in range(1,101):x=i%20;print('Bizz'*(x%19<1)+'Fuzz'*(x<2)or(i%4<1)*f+'Buzz'*(i%5<1or x==4)+f*(x==15)or i,i)[x%11==5]

```

# Answer
> 3 votes
### Python 2, 131

```
F,B,Z,I='Fizz','Buzz','Fuzz','Bizz'
for i in range(1,101):print{5:Z,19:I,i%4:B,i%5*4:F,3:B+F,16:F+B,0:I+Z,1:i,4:i}.get(i%4+i%5*4,i)

```

# Answer
> 1 votes
An ungolfed reference implementation in Python that implements every rule literally (420 chars):

```
n = 1
while(n <= 100):
    if(n % 20 == 0):
        print "BizzFuzz"
    elif((n - 1) % 20 == 0):
        print "Fuzz"
    elif((n + 1) % 20 == 0):
        print "Bizz"
    elif(n % 5 == 0 and (n + 1) % 4 == 0):
        print "BuzzFizz"
        print n + 1
        n += 1
    elif(n % 4 == 0 and (n + 1) % 5 == 0):
        print "FizzBuzz"
        print n + 1
        n += 1
    elif(n % 4 == 0):
        print "Fizz"
    elif(n % 5 == 0):
        print "Buzz"
    else:
        print n
    n += 1

```

# Answer
> 1 votes
# Python, 150

This is derivative of minitechs (earlier) answer, but I've squeezed enough out of it to make my own:

```
F,B,Z,I='Fizz','Buzz','Fuzz','Bizz'
for i in range(1,101):a,b=i%4,i%5*4;print i if a+b in [1,4] else {5:Z,19:I,a:B,b:F,3:B+F,16:F+B,0:I+Z}.get(a+b,i)

```

The degolfed version isn't much more readable, but the `r` that minitech was using is only triggered if on the next iteration the sum if `a,b` was either `1,0` or `0,4`, which is equivalent to `i%4 or i%5 == 0`so it was only going to appear in those circumstance. So it was possible to remove the assignment and calculation of `r` and derive it from the current value of `i` using `a` and `b`:

```
F,B,Z,I='Fizz','Buzz','Fuzz','Bizz'
for i in range(1,101):
 a,b=i%4,i%5*4;
 print i if a+b in [1,4] else {5:Z,19:I,a:B,b:F,3:B+F,16:F+B,0:I+Z}.get(a+b,i)

```

It also includes @WolframH's suggestions.

# Answer
> 1 votes
## R: 170 characters

```
a=b=1:100
o=!a%%4
i=!a%%5
w=o&i
a[o]="Fizz"
a[i]="Buzz"
a[c(i,F)&c(F,o)]="FizzBuzz"
a[c(F,i)&c(o,F)]="BuzzFizz"
a[w[-1]]="Bizz"
a[c(F,w)]="Fuzz"
a[w]="BizzFuzz"
cat(a[b])

```

# Answer
> 1 votes
## Javascript 127 bytes

```
f='Fizz';b='Buzz';F='Fuzz';B='Bizz';z=n=>(n?z(n-1):0,console.log([f,b,B,F,B+F,f+b,b+f,n]["43775777071707767772"[n%20]]));z(100)

```

## Explanation

```
f = 'Fizz';
b = 'Buzz';
F = 'Fuzz';
B = 'Bizz';

z = n => (
    n?z(n-1):0,  // If n is greater than 0, we keep going downwards, this happens before printing.
    console.log(
        // These are the values that we a want to print, it is
        // very important that it is written inline inside the
        // function, otherwise, we couldn't have 'n' in it
        [f,b,B,F,B+F,f+b,b+f,n][
          // The game cycles every 20 steps, so we can build a
          // look up table that we'll use to index into the other
          // table. We take advantage of implicit string -> Number
          // conversion inside the index operator, and use a
          // string instead of an array, saving 1 byte per entry
          "43775777071707767772"[n%20]])
);

z(100);

```

# Answer
> 0 votes
## Tcl, 185 chars

```
while {[incr i]<101} {puts [expr {$i%4?$i%5?($i-1)%4|($i-1)%5?($i+1)%4|($i+1)%5?$i:"Fuzz":"Bizz":($i-1)%4?($i+1)%4?"Buzz":"BuzzFizz":$i:($i-1)%5?($i+1)%5?$i%5?"Fizz":"FizzBuzz":$i:$i}]}

```

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


title: Interpreting the Wolfram Code

text:
# Question
Title: Interpreting the Wolfram Code
# Introduction

An elementary cellular automaton is a cellular automaton that is 1-dimensional and has 2 states, 1 and 0. These cellular automata are categorized based on a simple code: the Wolfram code, invented by Stephen Wolfram (yes, the Wolfram | Alpha guy). It works like this:

* First, you the set of all possible states for a cell and its 2 neighbors; this gives you 8 (2^3) states. You then arrange them in order (in this case) from left to right, so you have 000, 001, 010, 011, 100, 101, 110, and 111.
* Then, for each state, you take the resulting state of the center cell, either a 0 or 1. Then, you are left with 8 bits.
* You can guess what you do next: you combine the 8 bits into a single 1-byte number. This gives you 255 possible cellular automatons.

# Challenge

Given the Wolfram code number of a cellular automaton and a 3-bit state, you must write a program that will output the state of the center cell for that state.

* The two integers may be taken from any input method that is convenient (ie. variable, stdin, command line arguments, function arguments) Input can be taken as any type, as long as that type is capable of representing integers. For example, you could take input as an array of digits, a string, or an integer. Input can be in any base you want.
* The output may also be in any convenient method (ie. variable, stdout, exit code, return value) The only restriction is that the use must be able to see the output (no outputting to /dev/null). Output can be given as any type as well.

# Example I/O

> Number: `255`, State: `101`
> States: `1, 1, 1, 1, 1, 1, 1, 1`
> Output: `1`

---

> Number: `129`, State: `110`
> States: `1, 0, 0, 0, 0, 0, 0, 1`
> Output: `0`

---

> Number: `170`, State: `001`
> States: `1, 0, 1, 0, 1, 0, 1, 0`
> Output: `0`

# Rules

This is , so shortest answer in bytes wins!

# Answer
# Haskell, 4 bytes

The *number* is taken as a binary string and the *state* is taken as a (decimal) integer. This let us use the *state* as an index to the *number*, which immediately results in the desired output. So this answer just consists of an indexing function `!!`.

```
(!!)

```

Try it online!
> 7 votes

# Answer
# 05AB1E, 1 byte

Based on @flawr's previous MATL answer. Remember to give them an upvote! (Note: this takes input in a reversed order.)

```
è

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog Classic), 8 bytes

I don't know how to set this to a callable function or turn it into a full program. (Based on @flawr's Haskell answer, remember to upvote them!)

Format: `'state' {⍺[⍵+1]} number`

```
{⍺[⍵+1]}

```

Try it online!
> 1 votes

# Answer
# Keg, 5 SBCS bytes

-2 bytes from Jono 2906 via the `-hr` flag

```
?(¿|_

```

Try it online!
> 1 votes

# Answer
# GolfScript, 2 bytes

```
~=

```

Try it online!

## Explanation

```
~  # Dump the input onto the stack
 = # Index

```
> 1 votes

# Answer
# Wren, 17 bytes

Based on @flawr's previous JavaScript answer. Remember to give them an upvote!

```
Fn.new{|a,b|a[b]}

```

Try it online!
> 0 votes

# Answer
# JavaScript (Node.js), 34 bytes

```
(n)=>(s)=>n.toString(2)[+('0b'+s)]

```

Try it online!

Pretty sure the `toString(2)` call can be golfed better.
> 0 votes

---
Tags: code-golf, math, bitwise, cellular-automata
---


# Question
Title: Can you calculate the average Levenshtein distance exactly?
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one.

The challenge is to compute the average Levenshtein distance between two independent and uniformly random chosen binary strings of length `n` each. Your output must be exact but can be given in any easy to understand human readable form.

# Examples:

These are the answer for `n` up to `24`.

```
1 1/2
2 1
3 47/32
4 243/128
5 1179/512
6 2755/1024
7 12561/4096
8 56261/16384
9 124329/32768
10 2175407/524288
11 589839/131072
12 40664257/8388608
13 174219279/33554432
14 742795299/134217728
15 1576845897/268435456
16 13340661075/2147483648
17 14062798725/2147483648
18 59125997473/8589934592
19 123976260203/17179869184
20 259354089603/34359738368
21 8662782598909/1099511627776
22 72199426617073/8796093022208
23 150173613383989/17592186044416
24 1247439983177201/140737488355328

```

# Score

Your score is the highest value of you can reach. Where humanly possible, I will run your code on my Linux machine for 10 minutes and then kill the job to get the score.

# Notes

As always this should be a competition *per* language. I will maintain a leaderboard that shows the best score for each language used in an answer. ~~I will also give a bounty of 50 points for the first answer to get to `n = 20`.~~

My CPU is an Intel(R) Xeon(R) CPU X5460.

# Leaderboard

* `n = 18` in **Python+numba** by Shamis (timing pending...).
* `n = 19` in **Java** by Bob Genom (278 seconds).
* `n = 19` in **C** by ngn (257 seconds).
* `n = 21` in **Rust** by Anders Kaseorg (297 seconds). 150 point bonus awarded.

# Answer
> 10 votes
# Rust, score ≈ 22

This uses a dynamic programming approach (I’ve added an explanation here) whose running time seems to scale as approximately \\$\tilde O(2^{1.5n})\\$, rather than the \\$\tilde O(2^{2n})\\$ of a brute-force search. On my Ryzen 7 1800X (8 cores/16 threads), it gets through \\$1 \le n \le 21\\$ in 1.7 minutes, \\$1 \le n \le 22\\$ in 5.1 minutes.

Now using SIMD for the inner loop.

### `src/main.rs`

```
use fxhash::FxBuildHasher;
use itertools::izip;
use rayon::prelude::*;
use std::arch::x86_64::*;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::mem;
use typed_arena::Arena;

#[global_allocator]
static ALLOC: mimallocator::Mimalloc = mimallocator::Mimalloc;

type Distance = i8;
type Count = u32;
type Total = u64;

#[derive(Debug)]
struct Distances(__m128i);

impl PartialEq for Distances {
    fn eq(&self, other: &Distances) -> bool {
        unsafe {
            let x = _mm_xor_si128(self.0, other.0);
            _mm_testz_si128(x, x) != 0
        }
    }
}

impl Eq for Distances {}

impl Hash for Distances {
    fn hash<H: Hasher>(&self, state: &mut H) {
        unsafe {
            _mm_extract_epi64(self.0, 0).hash(state);
            _mm_extract_epi64(self.0, 1).hash(state);
        }
    }
}

fn main() {
    let splat0 = unsafe { _mm_set1_epi8(0) };
    let splat1 = unsafe { _mm_set1_epi8(1) };
    let splatff = unsafe { _mm_set1_epi8(!0) };
    let splat7f = unsafe { _mm_set1_epi8(0x7f) };
    let seq = unsafe { _mm_set_epi8(15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0) };
    let grow0 = unsafe {
        _mm_set_epi8(
            -0x80, 0, 0x20, 0, 0x8, 0, 0x2, 0, 0, 0x40, 0, 0x10, 0, 0x4, 0, 0x1,
        )
    };
    let grow1 = unsafe {
        _mm_set_epi8(
            0, 0x40, 0, 0x10, 0, 0x4, 0, 0x1, -0x80, 0, 0x20, 0, 0x8, 0, 0x2, 0,
        )
    };

    for n in 1 as Distance.. {
        if n > 31
            || (n as Count).leading_zeros() < n as u32
            || (n as Total).leading_zeros() < 2 * n as u32
        {
            break;
        }

        let total: Total = (0u32..1 << (n - 1))
            .into_par_iter()
            .map(|a| {
                let mut a_sym = a.reverse_bits();
                a_sym ^= (a_sym >> 31).wrapping_neg();
                a_sym >>= 32 - n as usize;
                if a_sym < a {
                    return 0;
                }

                let arena = Arena::<Distances>::new();
                let stride = (n as usize + 16) / 16 * 16;
                let idx = |i: Distance, j: Distance| i as usize + stride * j as usize;
                let both = |[x, y]: [Distance; 2]| x.max(y);
                let mut worst = vec![[stride as Distance; 2]; idx(0, n + 1)];
                for j in 0..=n {
                    worst[idx(n, j)] = [n - j; 2];
                }
                for i in (0..n).rev() {
                    worst[idx(i, n)] = [n - i; 2];
                    let good = (a >> i & 1) as usize;
                    let bad = good ^ 1;
                    for j in (0..n).rev() {
                        worst[idx(i, j)][good] = both(worst[idx(i + 1, j + 1)]);
                        worst[idx(i, j)][bad] = 1 + worst[idx(i + 1, j)][bad]
                            .min(both(worst[idx(i, j + 1)]))
                            .min(both(worst[idx(i + 1, j + 1)]));
                    }
                }
                let worst: &[Distances] = arena.alloc_extend(
                    worst
                        .into_iter()
                        .map(both)
                        .collect::<Box<[Distance]>>()
                        .chunks(16)
                        .map(|chunk| {
                            Distances(unsafe {
                                _mm_loadu_si128(chunk as *const [i8] as *const __m128i)
                            })
                        }),
                );

                let mut states: HashMap<&[Distances], Count, FxBuildHasher> = HashMap::default();
                let mut new_states = HashMap::default();

                states.insert(
                    arena.alloc_extend(
                        (0..n + 1)
                            .step_by(16)
                            .map(|i| Distances(unsafe { _mm_add_epi8(_mm_set1_epi8(i), seq) })),
                    ),
                    1,
                );

                let bvs: Vec<_> = [a, !a]
                    .iter()
                    .map(|b| {
                        arena.alloc_extend((0..n + 1).step_by(16).map(|i| unsafe {
                            let x = _mm_set1_epi16(((b << 1) >> i) as i16);
                            Distances(_mm_xor_si128(
                                _mm_cmpeq_epi8(
                                    _mm_or_si128(
                                        _mm_and_si128(x, grow0),
                                        _mm_and_si128(_mm_alignr_epi8(x, x, 1), grow1),
                                    ),
                                    splat0,
                                ),
                                splatff,
                            ))
                        }))
                    })
                    .collect();

                for j in 1..=n {
                    new_states.reserve(2 * states.len());
                    let worst_slice = &worst[idx(0, j) / 16..idx(0, j + 1) / 16];
                    for (state, count) in states.drain() {
                        for bv in &bvs {
                            let mut x = j;
                            let mut y = n.into();
                            let mut bound = n;

                            let new_state: &mut [Distances] =
                                arena.alloc_extend(izip!(&**bv, state, worst_slice).map(
                                    |(&Distances(bc), &Distances(yc), &Distances(wc))| unsafe {
                                        let o = _mm_min_epi8(
                                            _mm_add_epi8(yc, splat1),
                                            _mm_sub_epi8(
                                                _mm_insert_epi8(_mm_slli_si128(yc, 1), y, 0),
                                                bc,
                                            ),
                                        );
                                        y = _mm_extract_epi8(yc, 15);
                                        let o = _mm_sub_epi8(o, seq);
                                        let o = _mm_min_epi8(o, _mm_set1_epi8(x));
                                        let o = _mm_sub_epi8(splat7f, o);
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 1));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 2));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 4));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 8));
                                        let o = _mm_sub_epi8(splat7f, o);
                                        x = _mm_extract_epi8(o, 15) as i8 + 16;
                                        let o = _mm_add_epi8(o, seq);
                                        let z = _mm_add_epi8(o, wc);
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 1));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 2));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 4));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 8));
                                        bound = bound.min(_mm_extract_epi8(z, 0) as i8);
                                        Distances(o)
                                    },
                                ));

                            let bound = unsafe { _mm_set1_epi8(bound) };
                            for (i, Distances(x)) in (0..).step_by(16).zip(&mut *new_state) {
                                *x = unsafe {
                                    _mm_min_epi8(
                                        *x,
                                        _mm_sub_epi8(
                                            bound,
                                            _mm_abs_epi8(_mm_add_epi8(_mm_set1_epi8(i - j), seq)),
                                        ),
                                    )
                                };
                            }

                            *new_states.entry(&*new_state).or_insert(0) += count;
                        }
                    }
                    mem::swap(&mut states, &mut new_states);
                }

                let control = unsafe { _mm_insert_epi8(splatff, (n % 16).into(), 0) };
                Total::from(
                    states
                        .into_iter()
                        .map(|(state, count)| unsafe {
                            count
                                * _mm_extract_epi8(
                                    _mm_shuffle_epi8(state[n as usize / 16].0, control),
                                    0,
                                ) as Count
                        })
                        .sum::<Count>(),
                ) * if a_sym == a { 1 } else { 2 }
            })
            .sum();

        let shift = total.trailing_zeros();
        println!(
            "{} {}/{}",
            n,
            total >> shift,
            (1 as Total) << (2 * n as u32 - 1 - shift),
        );
    }
}

```

### `Cargo.toml`

```
[package]
name = "levenshtein"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[profile.release]
lto = true
codegen-units = 1

[dependencies]
fxhash = "0.2.1"
itertools = "0.8.2"
mimallocator = "0.1.3"
rayon = "1.3.0"
typed-arena = "2.0.0"

```

### Running

```
RUSTFLAGS='-C target-cpu=native' cargo build --release
target/release/levenshtein

```

### Output

(With cumulative timing data prepended by `ts -s %.s`.)

```
0.000008 1 1/2
0.000150 2 1/1
0.000219 3 47/32
0.000282 4 243/128
0.000344 5 1179/512
0.000413 6 2755/1024
0.000476 7 12561/4096
0.000538 8 56261/16384
0.000598 9 124329/32768
0.000660 10 2175407/524288
0.000721 11 589839/131072
0.000782 12 40664257/8388608
0.000843 13 174219279/33554432
0.006964 14 742795299/134217728
0.068070 15 1576845897/268435456
0.310136 16 13340661075/2147483648
1.062122 17 14062798725/2147483648
3.586745 18 59125997473/8589934592
11.265840 19 123976260203/17179869184
33.691822 20 259354089603/34359738368
101.514674 21 8662782598909/1099511627776
307.427106 22 72199426617073/8796093022208
956.299101 23 150173613383989/17592186044416
3077.477731 24 1247439983177201/140737488355328
10276.205241 25 5173410986415247/562949953421312
34550.754308 26 5356540527479769/562949953421312

```

Static `core2` build for Anush

# Answer
> 5 votes
# Java, score ≈ 19

My solution is a recursive approach. It is still \\$\tilde O(2^{2n})\\$ of a brute-force search. In other words: if n increase by 1 runtime increase by a factor of 4 (even when using multi-threading).

Which is obviously not enough to compare with Anders Kaseorg's code.

I observed and used some symmetries to squeeze out some (linear) factors.

```
import java.util.stream.IntStream;
// version 5.1
public class AvgLD51_MT {

    public static void main(String[] argv) {
        long t0=System.currentTimeMillis();
        for (int n=1; ;n++) {
            int VP = (1 << n) - 1; // 1m;
            int VN = 0; // 0m;
            int max=1<<(n-1);
            final int N=n;
            long sum=IntStream.range(0, max).mapToLong(p-> {
                int rp = Integer.reverse(p)>>>(32-N);
                int np = VP & ~rp;
                if (p <= rp && p <= np) {
                    if (p == rp || p == np) {
                        return 2*buildX(N, p, 0, 1, VP, VN);
                    } else {
                        return 4*buildX(N, p, 0, 1, VP, VN);
                    }
                }
                return 0;
            }).parallel().sum();
            long gcd=gcd(sum, (1L<<(2*n)));
            System.out.printf("%f   %d  %d  %d/%d\n", (double)(System.currentTimeMillis()-t0)/(1000), n, sum, sum/gcd, (1L<<(2*n))/gcd);
            sum*=2;
        }
    }

    /**
     * Myers (, Hyyrö) injected into my recursive buildX function (see version 4).
     * Pattern p is fixed. Text t is generated by recursion.
     *
     * Myers (, Hyyrö) bit-parallel LevenshteinDistance
     * taken and inferred (for gulfing e.g. m==n) from:
     * https://www.win.tue.nl/~jfg/educ/bit.mat.pdf
     * http://www.mi.fu-berlin.de/wiki/pub/ABI/RnaSeqP4/myers-bitvector-verification.pdf
     * https://www.sciencedirect.com/science/article/pii/S157086670400053X
     * https://www.researchgate.net/publication/266657812_Thread-cooperative_bit-parallel_computation_of_Levenshtein_distance_on_GPU
     */
    static long buildX(int n, int p, int t, int j, int VP, int VN){
        final int HMASK = 1 << (n - 1); // 10^(m-1)
        final int VMASK = (1<<n)-1;
        long score=0;
        int Bj, D0, HP, HN, VP1, VN1, X;

        // assume a 0 at Tj
        Bj= ~p;
        // compute diagonal delta vector
        D0 = ((VP + (Bj & VP)) ^ VP) | Bj | VN;

        // update horizontal delta values
        HN = VP & D0;
        HP = VN | ~(VP | D0);
        // Scoring and output
        // carry = rev(n, j)*(Integer.bitCount(HP & HMASK) - Integer.bitCount(HN & HMASK));
        X = (HP << 1) | 1;
        VN1 = (HN << 1) | ~(X | D0);
        VP1 = X & D0;
        if (j!=HMASK) {
            // update vertical delta values
            score = buildX(n, p, t, 2*j, VN1, VP1);
        } else {
            score = n + Integer.bitCount(VMASK & VN1) - Integer.bitCount(VMASK & VP1);
        }

        // assume a 1 at Tj
        Bj= p;
        // compute diagonal delta vector
        D0 = ((VP + (Bj & VP)) ^ VP) | Bj | VN;

        // update horizontal delta values
        HN = VP & D0;
        HP = VN | ~(VP | D0);
        // Scoring and output
        // carry += rev(n, j)*(Integer.bitCount(HP & HMASK) - Integer.bitCount(HN & HMASK));
        X = (HP << 1) | 1;
        VN1 = (HN << 1) | ~(X | D0);
        VP1 = X & D0;
        if (j!=HMASK) {
            // update vertical delta values
            return score + buildX(n, p, t, 2*j, VN1, VP1);
        } else {
            return n + score + Integer.bitCount(VMASK & VN1) - Integer.bitCount(VMASK & VP1);
        }
    }

    static long gcd(long numerator, long denominator) {
        long gcd = denominator;
        while (numerator != 0) {
            long tmp=numerator; numerator=gcd % numerator; gcd=tmp;
        }
        return gcd;
    }
}

```

## Version 5.1

Like version 5 but is multi-threaded by using streams.

```
0.000000    1   2   1/2
...
0.748000    15  6307383588  1576845897/268435456
2.359000    16  26681322150 13340661075/2147483648
10.062000   17  112502389800    14062798725/2147483648
35.387000   18  473007979784    59125997473/8589934592
156.396000  19  1983620163248   123976260203/17179869184
572.525000  20  8299330867296   259354089603/34359738368

```

## Version 5

Myers code directly injected into my recursive buildX function. As a consequence no extra call of LevenshteinDistance is needed any more.

```
0.000000    1   2   1/2
...
2.134000    15  6307383588  1576845897/268435456
7.571000    16  26681322150 13340661075/2147483648
32.705000   17  112502389800    14062798725/2147483648
119.952000  18  473007979784    59125997473/8589934592
523.186000  19  1983620163248   123976260203/17179869184

```

## Version 4.1

Like version 4 but is multi-threaded by using streams.

```
0.000000    1   2   1/2
...
0.764000    13  348438558   174219279/33554432
1.525000    14  1485590598  742795299/134217728
4.417000    15  6307383588  1576845897/268435456
15.445000   16  26681322150 13340661075/2147483648
63.199000   17  112502389800    14062798725/2147483648
259.179000  18  473007979784    59125997473/8589934592

```

## Version 4

Uses Myers, Hyyrö bit-parallel LevenshteinDistance.

```
0.000000    1   2   1/2
...
8.203000    15  6307383588  1576845897/268435456
35.326000   16  26681322150 13340661075/2147483648
148.577000  17  112502389800    14062798725/2147483648
629.084000  18  473007979784    59125997473/8589934592
2615.031000 19  1983620163248   123976260203/17179869184

```

## Version 3

Copied and uses getLevenshteinDistance(..) from apache StringUtils. BTW: Using the threshold variant made no difference for me. (Used threshold=bitCount(s^t))

```
0.000000    1   2   1/2
...
60.190000   15  6307383588  1576845897/268435456
271.020000  16  26681322150 13340661075/2147483648
1219.544000 17  112502389800    14062798725/2147483648

```

## Version 2

Found more symmetries on recursion.

```
0.000000    1   2   1/2
...
105.389000  15  6307383588  1576845897/268435456
447.617000  16  26681322150 13340661075/2147483648
2105.316000 17  112502389800    14062798725/2147483648

```

## Version 1

```
0.000000    1   2   1/2
0.068000    2   16  1/1
0.070000    3   94  47/32
0.071000    4   486 243/128
0.073000    5   2358    1179/512
0.074000    6   11020   2755/1024
0.076000    7   50244   12561/4096
0.086000    8   225044  56261/16384
0.111000    9   994632  124329/32768
0.223000    10  4350814 2175407/524288
0.640000    11  18874848    589839/131072
1.842000    12  81328514    40664257/8388608
7.387000    13  348438558   174219279/33554432
29.998000   14  1485590598  742795299/134217728
139.217000  15  6307383588  1576845897/268435456
581.465000  16  26681322150 13340661075/2147483648

```

# Answer
> 4 votes
# C

```
// gcc -O3 -pthread -march=native a.c && ./a.out
#define _GNU_SOURCE
#include<stdio.h>
#include<unistd.h>
#include<pthread.h>
#define _(a...){return({a;});}
#define $(x,a...)if(x){a;}
#define P(x,a...)if(x)_(a)
#define W(x,a...)while(x){a;}
#define F(i,n,a...)for(I i=0,n_=(n);i<n_;i++){a;}
#define S static
typedef void V;typedef int I;typedef long long L;typedef struct{I x,r;pthread_barrier_t*b;}A;
S I n,x1,msk,nt;S L f1(I,I,I,I);
S L gcd(L x,L y)_(W(x,L z=x;x=y%x;y=z)y)S I rev(I x)_(I r=0;F(i,n,r+=(x>>i&1)<<(n-1-i))r)
S L f0(I x,I j,I vp_,I vn_,I pm)_(I d0=(((pm&vp_)+vp_)^vp_)|pm|vn_,hp=vn_|~(d0|vp_),hp1=hp<<1|1,vp=(d0&vp_)<<1|~(d0|hp1),vn=d0&hp1;f1(x,j,vp,vn))
S L f1(I x,I j,I vp_,I vn_)_(P(!--j,__builtin_popcount(msk&vp_)-__builtin_popcount(msk&vn_))f0(x,j,vp_,vn_,x)+f0(x,j,vp_,vn_,~x))
S V*f2(A*a)_(I x=a->x;L s[3]={};W(x<x1,I rx=rev(x),nx=msk&~rx;$(x<=rx&&x<=nx,s[(x!=rx)+(x!=nx)]+=f1(x,n+1,msk,0))x+=nt)
 a->r=s[0]+2*s[1]+4*s[2];pthread_barrier_wait(a->b);NULL)
S L f3()_(L r=(L)n<<2*n;pthread_barrier_t b;pthread_barrier_init(&b,0,nt);A a[nt];pthread_t t[nt];
 F(i,nt,cpu_set_t c;CPU_ZERO(&c);CPU_SET(i,&c);pthread_attr_t h;pthread_attr_init(&h);pthread_attr_setaffinity_np(&h,sizeof(cpu_set_t),&c);
  a[i].x=i;a[i].r=0;a[i].b=&b;pthread_create(t+i,0,(V*(*)(V*))f2,a+i))
 F(i,nt,pthread_join(t[i],0);r+=a[i].r)pthread_barrier_destroy(&b);r)
I main()_(nt=2*sysconf(_SC_NPROCESSORS_CONF);
 W(1,n++;x1=1<<(n-1);msk=(1<<n)-1;L p=f3(),q=1ll<<2*n,d=gcd(p,q);printf("%d %lld/%lld\n",n,p/d,q/d);fflush(stdout))0)

```

# Answer
> 3 votes
Python ~ ~~15, 17, 18~~ Requiem for a Dream.

So far for my attempt to decipher the algorithm. Just one simple symmetry as a result. Upside is that I managed to get up to 19. Downside is obviously a shattered hope XD. To add an insult to an injury, I think that Bob Genom already has it. (Noticed after I dismantled my previous horror of a solution to something readable-ish.) It also might be that what I considered annoying edge cases might actually be a result of me overcomplicating things. Dear oh dear. Still I think that some way of caching the Levenstein computation might be the way to go. Just not the one I tried last time.

```
7.215967655181885 16 13340661075 / 2147483648
24.544007539749146 17 14062798725 / 2147483648
93.72401142120361 18 59125997473 / 8589934592
379.6802065372467 19 123976260203 / 17179869184

```

---

Added Multiprocessing. The most expensive thing at the time are locks. And I have yet to figure a way to bypass the need for them. My manual attempts are slower than the Pool.Starmap which makes me slightly sad.

Tried a block processing approach with an attempt to gain another linear factor, however for some reason this slowed down the code by a lot. Overoptimization seems to backfire.

```
1.640207052230835 13 174219279 / 33554432
1.9370124340057373 14 742795299 / 134217728
3.1867198944091797 15 1576845897 / 268435456
9.054970979690552 16 13340661075 / 2147483648
37.539693117141724 17 14062798725 / 2147483648
158.5456690788269 18 59125997473 / 8589934592

```

Thanks to Bob Genom's answer and using his latest distance algorithm I managed to up the speed. Also I noted that one of the attempts at a linear symmetry backfired - the code runs faster after I removed it. Probably something to do with ranges?

```
...............
0.6873703002929688 13 174219279 / 33554432
2.0464255809783936 14 742795299 / 134217728
7.808838605880737 15 1576845897 / 268435456
33.9985032081604 16 13340661075 / 2147483648
145.6884548664093 17 14062798725 / 2147483648

```

Took me quite a while and I have run into quite the Python limitations. My attempt to parallelize was ground to a halt by the GIL. Figuring out how to make processes talk to each other will take a while. I have few more ideas to try, however my brain is starting to melt. I spent last two hours by juggling indices - my current approach is to embed symmetries directly into the loops. Recursion was much slower and Numba doesn't like to interact with Python objects. For some reason it sees nothing to parallelize in this code and I have no clue whether the parallel part does anything since the CPU is only at 20% capacity.

This approach is still bruteforcing, however with the embedded symmetries it takes the computation down a notch - many of the combinations are not even considered.

I took the liberty to start from 2nd floor. I do not consider that as a cheating since it is negligible time-wise. And it introduces a swath of very vexing edge cases.

If I have time, I will try to do these: Rewrite the code in something faster, probably C. Try to figure out a decent way to use parallelization, maybe in C. And a bit of a caching. That one will be tricky, especially in combination with the embedding.

```
0.0 2 1 / 1
0.483562707901001 3 47 / 32
0.483562707901001 4 243 / 128
0.483562707901001 5 1179 / 512
0.483562707901001 6 2755 / 1024
0.483562707901001 7 12561 / 4096
0.5001938343048096 8 56261 / 16384
0.5334563255310059 9 124329 / 32768
0.6999850273132324 10 2175407 / 524288
1.3333814144134521 11 589839 / 131072
3.7170190811157227 12 40664257 / 8388608
15.165801048278809 13 174219279 / 33554432
62.91589903831482 14 742795299 / 134217728
266.3912649154663 15 1576845897 / 268435456

```

I would love to try and give a GPU a go for this task. However I failed miserably for nowXD.

```
from numba import jit, cuda, prange
import time
import multiprocessing as mp

@jit(nopython=True, fastmath=True, nogil=True)#, parallel=True)
def LevenshteinDistance(n, p, t):
        np=~p
        HMASK = (1 << (n - 1))
        VP = (1 << n) - 1
        VN = 0
        score = n
        for j in range(0,n):
            if (t & (1<<j)) != 0:
                Bj = p
            else:
                Bj = np
            D0 = ((VP + (Bj & VP)) ^ VP) | Bj | VN
            HN = VP & D0
            HP = VN | ~(VP | D0)

            if ((HP & HMASK) != 0):
             score += 1;
            elif ((HN & HMASK) != 0):
             score -= 1;
            X = (HP << 1) | 1
            VN = X & D0
            VP = (HN << 1) | ~(X | D0)
        return score

@jit(nopython=True, fastmath=True)#, parallel=True)
def dispatchLev(i, level):
    halfSize = 1 << (level - 1) - 1
    iRange = halfSize
    levelSize = 1 << (level - 1)
    mask = levelSize - 1
    halfSize = levelSize >> 1
    rangeUpper = iRange - i
    indexI = i + halfSize
    baseI = indexI << 1
    sum = 0
    for indexJ in range(0, rangeUpper):
        baseJ = indexJ << 1
        if (mask ^ indexJ) == indexI:
            a = LevenshteinDistance(level, baseI + 1, baseJ)
            b = LevenshteinDistance(level, baseI, baseJ + 1)
            sum += a + b
        else:
            a = LevenshteinDistance(level, baseI + 1, baseJ)
            b = LevenshteinDistance(level, baseI, baseJ + 1)
            sum += 2 * (a + b)

    return sum

def computeSum(level):
    levelSize = 1 << (level - 1)
    halfSize = levelSize >> 1
    curSum = 0
    iRange = halfSize
    test = [(x, level) for x in range(0, iRange)]
    if len(test) > 1:
        a = myPool.starmap(dispatchLev, test)
        curSum += sum(a)
        #for x, level in test:
        #    curSum += dispatchLev(x,level)

    else:
        a = dispatchLev(0, level)
        curSum += a
    return curSum

def gcd(num, den):
    gcdRet = den
    tmp = 0
    while num != 0:
        tmp = num
        num = gcdRet % num
        gcdRet = tmp

    return gcdRet

if __name__ == '__main__':
    t1 = time.time()
    print("beginning")
    prevSum = 16
    bruteForceCarry = 6
    levelMask = 0
    target = 20
    curSum = 0
    bruteForce = 0
    myPool = mp.Pool(mp.cpu_count())
    processArray = []
    resultArray = []

    for level in range(3, target):
        levelSize = 1 << level
        halfSize = levelSize >> 1
        bruteForce = computeSum(level)
        diagonal = computeDiagonal(level)
        bruteForceCarry = 2 * bruteForceCarry + bruteForce
        curSum = prevSum + bruteForceCarry
        curSum = curSum * 2
        t2 = time.time()
        wholeSize = levelSize * levelSize
        divisor = gcd(curSum, wholeSize)
        a = int(curSum / divisor)
        b = int(wholeSize / divisor)
        print(t2 - t1, level, a, "/", b)
        prevSum = curSum

```

---
Tags: string, math, combinatorics, fastest-code
---


title: Tips for Regex Golf

text:
# Question
Title: Tips for Regex Golf
Similar to our threads for language-specific golfing tips: what are general tricks to shorten regular expressions?

I can see three uses of regex when it comes to golfing: classic regex golf ("here is a list that should match, and here is a list that should fail"), using regex to solve computational problems and regular expressions used as parts of larger golfed code. Feel free to post tips addressing any or all of these. If your tip is limited to one or more flavours, please state these flavours at the top.

As usual, please stick to one tip (or family of very closely related tips) per answer, so that the most useful tips can rise to the top via voting.

# Answer
> 26 votes
# When not to escape

These rules apply to most flavours, if not all:

* `]` doesn't need escaping when unmatched.
* `{` and `}` don't need escaping when they are not part of a repetition, e.g. `{a}` matches `{a}` literally. Even if you want to match something like `{2}`, you only need to escape one of them, e.g. `{2\}`.

In character classes:

* `]` doesn't need escaping when it's the first character in a character set, e.g. `[]abc]` matches one of `]abc`, or when it's the second character after a `^`, e.g. `[^]]` matches anything but `]`. (Notable exception: ECMAScript flavour!)
* `[` doesn't need escaping at all. Together with the above tip, this means you can match both brackets with the horribly counter-intuitive character class `[][]`.
* `^` doesn't need escaping when it's *not* the first character in a character set, e.g. `[ab^c]`.
* `-` doesn't need escaping when it's either the first (second after a `^`) or last character in a character set, e.g. `[-abc]`, `[^-abc]` or `[abc-]`.
* No other characters need escaping inside a character class, even if they are meta characters outside of character classes (except for backslash `\` itself).

Also, in some flavours `^` and `$` are matched literally when they are not at the start or end of the regex respectively.

(Thanks to @MartinBüttner for filling in a few details)

# Answer
> 22 votes
A simple regular expression to match all printable characters in the **ASCII** table.

```
[ -~]

```

# Answer
> 18 votes
# Know your regex flavours

There are a surprising amount of people who think that regular expressions are essentially language agnostic. However, there are actually quite substantial differences between flavours, and especially for code golf it's good to know a few of them, and their interesting features, so you can pick the best for each task. Here is an overview over several important flavours and what sets them apart from others. (This list can't really be complete, but let me know if I missed something really glaring.)

## Perl and PCRE

I'm throwing these into a single pot, as I'm not too familiar with the Perl flavour and they're *mostly* equivalent (PCRE is for Perl-Compatible Regular Expressions after all). The main advantage of the Perl flavour is that you can actually call Perl code from inside the regex and substitution.

* Recursion/subroutines. Probably the most important feature for golfing (which only exists in a couple of flavours).
* Conditional patterns `(?(group)yes|no)`.
* Supports change of case in the replacement string with `\l`, `\u`, `\L` and `\U`.
* PCRE allows alternation in lookbehinds, where each alternative can have a different (but fixed) length. (Most flavours, including Perl require lookbehinds to have an overall fixed length.)
* `\G` to anchor a match to the end of the previous match.
* `\K` to reset the beginning of the match
* PCRE supports both Unicode character properties and scripts.
* `\Q...\E` to escape longer runs of characters. Useful when you're trying to match a string that contains many meta-characters.

## .NET

This is probably the most powerful flavour, with only very few shortcomings.

One important shortcoming in terms of golfing is that it doesn't support possessive quantifiers like some other flavours. Instead of `.?+` you'll have to write `(?>.?)`.

## Java

* Due to a bug (see Appendix) Java supports a limited type of variable-length lookbehind: you can lookbehind all the way to the beginning of the string with `.*` from where you can now start a lookahead, like `(?<=(?=lookahead).*)`.
* Supports union and intersection of character classes.
* Has the most extensive support for Unicode, with character classes for "Unicode scripts, blocks, categories and binary properties".
* `\Q...\E` as in Perl/PCRE.

## Ruby

In recent versions, this flavour is similarly powerful as PCRE, including the support for subroutine calls. Like Java, it also supports union and intersection of character classes. One special feature is the built-in character class for hex digits: `\h` (and the negated `\H`).

The most useful feature for golfing though is how Ruby handles quantifiers. Most notably, it's possible to nest quantifiers without parentheses. `.{5,7}+` works and so does `.{3}?`. Also, as opposed to most other flavours, if the lower bound on a quantifier is `0` it can be omitted, e.g. `.{,5}` is equivalent to `.{0,5}`.

As for subroutines, the major difference between PCRE's subroutines and Ruby's subroutines, is that Ruby's syntax is a byte longer `(?n)` vs `\g<n>`, but Ruby's subroutines can be used for capturing, whereas PCRE resets captures after a subroutine finishes.

Finally, Ruby has different semantics for line-related modifiers than most other flavours. The modifier that's usually called `m` in other flavours is *always* on in Ruby. So `^` and `$` always match the beginning and end of a *line* not just the beginning and end of the string. This can save you a byte if you need this behaviour, but it will cost you extra bytes if you don't, because you'll have to replace `^` and `$` with `\A` and `\z`, respectively. In addition to that, the modifier that is usually called `s` (which makes `.` match linefeeds) is called `m` in Ruby instead. This doesn't affect byte counts, but should be kept in mind to avoid confusion.

## Python

Python has a solid flavour, but I'm not aware of any particularly useful features that you wouldn't find anywhere else.

**However**, there is the **regex** module, which is intended to replace the `re` module at some point, and which contains a lot of interesting features. In addition to adding support for recursion, variable-length lookbehinds and character class combination operators, it also has the unique feature of **fuzzy matching**. In essence you can specify a number of errors (insertions, deletions, substitutions) which are allowed, and the engine will also give you approximate matches.

## ECMAScript

The ECMAScript flavour is very limited, and hence rarely very useful for golfing. The only thing it's got going for it is the negated empty character class `[^]` to match any character as well as the unconditionally failing empty character class `[]` (as opposed to the usual `(?!)`). Unfortunately, the flavour does not have any features which makes the latter useful for normal problems.

## Lua

Lua has its own fairly unique flavour, which is quite limited (e.g. you can't even quantify groups) but does come with a handful of useful and interesting features.

* It's got a large number of shorthands for built-in character classes, including punctuation, upper/lower case characters and hex digits.
* With `%b` it supports a very compact syntax to match balanced strings. E.g. `%b()` matches a `(` and then everything up to a matching `)` (correctly skipping inner matched pairs). `(` and `)` can be any two characters here.

## Boost

Boost's regex flavour is essentially Perl's. However, it has some nice new features for regex substitution, including case changes and **conditionals**. The latter is unique to Boost as far as I'm aware.

# Answer
> 13 votes
# Know your character classes

Most regex flavours have predefined character classes. For example, `\d` matches a decimal digit, which is three bytes shorter than `[0-9]`. Yes, they might be slightly different as `\d` may also match Unicode digits as well in some flavours, but for most challenges this won't make a difference.

Here are some character classes found in most regex flavours:

```
\d      Match a decimal digit character
\s      Match a whitespace character
\w      Match a word character (typically [a-zA-Z0-9_])

```

In addition, we also have:

```
\D \S \W

```

which are negated versions of the above.

Be sure to check your flavour for any additional escape codes it might have. For example, PCRE has **`\R`** for newlines and Lua even has classes such as lowercase and uppercase characters.

(Thanks to @HamZa and @MartinBüttner for pointing these out)

# Answer
> 12 votes
# Don't bother with non-capturing groups (unless...)

This tip applies to (at least) all popular Perl-inspired flavours.

This may be obvious, but (when not golfing) it's good practice to use non-capturing groups `(?:...)` whenever possible. These two extra characters `?:` are wasteful when golfing though, so just use capturing groups, even if you're not going to backreference them.

There's one (rare) exception though: if you happen to backreference group `10` at least 3 times, you can actually save bytes by turning an earlier group into a non-capturing group, such that all those `\10`s become `\9`s. (Similar tricks apply, if you use group `11` at least 5 times and so on.)

# Answer
> 11 votes
# Recursion for pattern reuse

A handful of flavours support recursion (to my knowledge, Perl, PCRE and Ruby). Even when you're not trying to solve recursive problems, this feature can save a *lot* of bytes in more complicated patterns. There is no need to make the call to another (named or numbered) group inside that group itself. If you have a certain pattern that appears several times in your regex, just group it and refer to it outside that group. This is no different from a subroutine call in normal programming languages. So instead of

```
...someComplexPatternHere...someComplexPatternHere...someComplexPatternHere...

```

in Perl/PCRE you could do:

```
...(someComplexPatternHere)...(?1)...(?1)...

```

or in Ruby:

```
...(someComplexPatternHere)...\g<1>...\g<1>...

```

provided that is the first group (of course, you can use any number in the recursive call).

Note that this is *not* the same as a backreference (`\1`). Backreferences match the exact same string that the group matched last time. These subroutine calls actually evaluate the pattern again. As an example for `someComplexPatternHere` take a lengthy character class:

```
a[0_B!$]b[0_B!$]c[0_B!$]d

```

This would match something like

```
aBb0c!d

```

Note that you cannot use backreferences here while preserving the behaviour. A backreference would fail on the above string, because `B` and `0` and `!` are not the same. However, with subroutine calls, the pattern is actually reevaluated. The above pattern is completely equivalent to

```
a([0_B!$])b(?1)c(?1)d

```

### Capturing in subroutine calls

One note of caution for Perl and PCRE: if group `1` in the above examples contains further groups, then the subroutine calls will not remember their captures. Consider this example:

```
(\w(\d):)\2 (?1)\2 (?1)\2

```

This will *not* match

```
x1:1 y2:2 z3:3

```

because after the subroutine calls return, the new capture of group `2` is discarded. Instead, this pattern would match this string:

```
x1:1 y2:1 z3:1

```

This is different from Ruby, where subroutine calls *do* retain their captures, so the equivalent Ruby regex `(\w(\d):)\2 \g<1>\2 \g<1>\2` would match the first of the examples above.

# Answer
> 10 votes
# Causing a match to fail

When using regex to solve computational problems or match highly non-regular languages, it is sometimes necessary to make a branch of the pattern fail regardless of where you are in the string. The naive approach is to use an empty negative lookahead:

```
(?!)

```

The contents (the empty pattern) always matches, so the negative lookahead always fails. But more often than not, there is a much simpler option: just use a character you know will never appear in the input. E.g. if you know your input will always consist only of digits, you can simply use

```
!

```

or any other non-digit, non-meta character to cause failure.

Even if your input could potentially contain any substrings whatsoever, there are shorter ways than `(?!)`. Any flavour which allows anchors to appear within a pattern as opposed to the end, could use either of the following 2-character solutions:

```
a^
$a

```

Note however that some flavours will treat `^` and `$` as literal characters in these positions, because they obviously don't actually make sense as anchors.

In the ECMAScript flavour there is also the rather elegant 2-character solution

```
[]

```

This is an empty character class, which tries to make sure that the next characters is one of those in the class - but there are no characters in the class, so this always fails. Note that this won't work in any other flavour, because character classes can't usually be empty.

# Answer
> 9 votes
# Optimize you OR's

Whenever you have 3 or more alternatives in your RegEx:

```
/aliceblue|antiquewhite|aquamarine|azure/

```

Check to see if there's a common start:

```
/a(liceblue|ntiquewhite|quamarine|zure)/

```

And maybe even a common ending?

```
/a(liceblu|ntiquewhit|quamarin|zur)e/

```

*Note: 3 is just the start and would account for the same length, 4+ would make a difference*

---

But what if not all of them have a common prefix? <sub>(whitespace only added for clarity)</sub>

```
/aliceblue|antiquewhite|aqua|aquamarine|azure
|beige|bisque|black|blanchedalmond|blue|blueviolet|brown|burlywood
|cadetblue|chartreuse|chocolate|coral|cornflowerblue|cornsilk|crimson|cyan/

```

Group them, as long as the 3+ rule makes sense:

```
/a(liceblue|ntiquewhite|qua|quamarine|zure)
|b(eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood)
|c(adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/

```

Or even *generalise* if the entropy satisfies your usecase:

```
/\w(liceblue|ntiquewhite|qua|quamarine|zure
|eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood
|adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/

```

<sup>^ in this case we're sure we don't get any `clue` or `crown` `slack` `Ryan` </sup>

This *"according to some tests"* also improves performance, as it provides an *anchor* to start at.

# Answer
> 7 votes
This one is fairly simple, but worth stating:

If you find yourself repeating the character class `[a-zA-Z]` you can probably just use `[a-z]` and append the `i` (case-**i**nsensitive modifier) to your regex.

For example, in Ruby, the following two regexes are equivalent:

`/[a-zA-Z]+\d{3}[a-zA-Z]+/`
`/[a-z]+\d{3}[a-z]/i` \- 7 bytes shorter

For that matter, the other modifiers can shorten your total length as well. Instead of doing this:

`/(.|\n)/`

which matches ANY character (because dot doesn't match newline), use the **s**ingle-line modifier `s`, which makes dot match newlines.

`/./s` \- 3 bytes shorter

---

In Ruby, there are a ton of built-in Character Classes for regex. See this page and search for "Character Properties".
A great example is the "Currency Symbol". According to Wikipedia there are a ton of possible currency symbols, and to put them in a character class would be very expensive (`[$฿¢₡Ð₫€.....`\]) whereas you can match any of them in 6 bytes: `\p{Sc}`

# Answer
> 7 votes
# `\K` instead of positive lookbehind

PCRE and Perl support the escape sequence `\K`, which resets the beginning of the match. That is `ab\Kcd` will require your input string to contain `abcd` but the reported match will only be `cd`.

If you are using a positive lookbehind at the start of your pattern (which is probably the most likely place), then in most cases, you can use `\K` instead and save 3 bytes:

```
(?<=abc)def
abc\Kdef

```

This is equivalent for *most* purposes, but not entirely. The differences bring both advantages and disadvantages with them:

* Upside: PCRE and Perl don't support arbitrary-length lookbehinds (only .NET does). That is, you can't do something like `(?<=ab*)`. But with `\K` you can put any sort of pattern in front of it! So `ab*\K` works. This actually makes this technique vastly more powerful in the cases where it's applicable.
* Upside: Lookarounds don't backtrack. This is relevant if you want to capture something in the lookbehind to backreference later, but there are several possible captures which all lead to valid matches. In this case, the regex engine would only ever try one of those possibilities. When using `\K` that part of the regex is being backtracked like everything else.
* Downside: As you probably know, several matches of a regex cannot overlap. Often, lookarounds are used to partially work around this limitation, since the lookahead can validate a portion of the string that was already consumed by an earlier match. So if you wanted to match all the characters that *followed* `ab` you might use `(?<=ab).`. Given the input

```
ababc

```

this would match the second `a` and the `c`. This *cannot* be reproduced with `\K`. If you used `ab\K.`, you would only get the first match, because now the `ab` is not in a lookaround.

# Answer
> 6 votes
# A simple language parser

You can build a very simple parser with an RE like `\d+|\w+|".*?"|\n|\S`. The tokens you need to match are separated with the RE 'or' character.

Each time the RE engine tries to match at the current position in the text, it will try the first pattern, then the second, etc. If it fails (on a space character here for example), it moves on and tries the matches again. Order is important. If we placed the `\S` term before the `\d+` term, the `\S` would match first on any non-space character which would break our parser.

The `".*?"` string matcher uses a non-greedy modifier so we only match one string at a time. If your RE doesn't have non-greedy functions, you can use `"[^"]*"` which is equivalent.

### Python Example:

```
text = 'd="dogfinder"\nx=sum(ord(c)*872 for c in "fish"+d[3:])'
pat = r'\d+|\w+|".*?"|\n|\S'
print re.findall(pat, text)

['d', '=', '"dogfinder"', '\n', 'x', '=', 'sum', '(', 'ord', '(', 'c', ')',
    '*', '872', 'for', 'c', 'in', '"fish"', '+', 'd', '[', '3', ':', ']', ')']

```

### Golfed Python Example:

```
# assume we have language text in A, and a token processing function P
map(P,findall(r'\d+|\w+|".*?"|\n|\S',A))

```

You can adjust the patterns and their order for the language you need to match. This technique works well for JSON, basic HTML, and numeric expressions. It has been used successfully many times with Python 2, but should be general enough to work in other environments.

# Answer
> 6 votes
# Capturing groups hold the last value matched

`(REGEX)*` will hold in capturing group 1 the last match of `REGEX`. `(REGEX)` can be combined with any such repeaters.

For getting the last character of a string, there is the straightforward 5-byter

```
.*(.)

```

which captures the last character in capturing group 1. Another byte can be saved by noting the point in the title of this post, giving the 4-byter

```
(.)*

```

Another example, getting the penultimate character

```
.*(.).        # 6 bytes
(.)*.         # 5 bytes

```

# Answer
> 5 votes
# Matching any character

**Update**: Since the ECMAScript 2018 specification, the flavor has the classic dotAll flag that matches all characters, so the following quoted part is now only true if your browser or system uses a very old version that predates this 2018 update, which would be unusual:

> The ECMAScript flavour is lacking the `s` modifiers which makes `.` match any character (including newlines). This means there is no single-character solution to matching completely arbitrary characters.

The following is the unedited rest of this older answer:

The standard solution in other flavours (when one doesn't want to use `s` for some reason) is `[\s\S]`. However, ECMAScript is the only flavour (to my knowledge) which supports empty character classes, and hence has a much shorter alternative: `[^]`. This is a negated empty character class - that is, it matches any character whatsoever.

Even for other flavours, we can learn from this technique: if we don't want to use `s` (e.g. because we still need to usual meaning of `.` in other places), there can still be a shorter way to match both newline and printable characters, provided there is some character we know doesn't appear in the input. Say, we're processing numbers delimited by newlines. Then we can match any character with `[^!]`, since we know that `!` won't ever be part of the string. This saves two bytes over the naive `[\s\S]` or `[\d\n]`.

# Answer
> 5 votes
## Optional expressions

It is sometimes useful to remember that

```
(abc)?

```

is *mostly* the same as

```
(abc|)

```

There is a small difference though: in the first case, the group either captures `abc` or doesn't capture at all. The latter case would make a backreference fail unconditionally. In the second expression, the group will either capture `abc` or an empty string, where the latter case would make a backreference *match* unconditionally. To emulate the latter behaviour with `?` you'd need to surround everything in another group which would cost two bytes:

```
((abc)?)

```

The version using `|` is also useful when you want to wrap the expression in some other form of group anyway and don't care about the capturing:

```
(?=(abc)?)
(?=abc|)

(?>(abc)?)
(?>abc|)

```

Finally, this trick can also be applied to ungreedy `?` where it saves a byte even in its raw form (and consequently 3 bytes when combined with other forms of groups):

```
(abc)??
(|abc)

```

# Answer
> 4 votes
# Use atomic groups and possessive quantifiers

I found atomic groups (`(?>...)`) and possessive quantifiers (`?+`, `*+`, `++`, `{m,n}+`) sometimes very useful for golfing. It matches a string and disallows backtracking later. So it will only match the first matchable string which is found by the regex engine.

For example: To match a string with odd number of `a`'s at the beginning, which is not followed by more `a`'s, you can use:

```
^(aa)*+a
^(?>(aa)*)a

```

This allows you to use things like `.*` freely, and if there is an obvious match, there won't be another possibility matching too many or too few characters, which may break your pattern.

In .NET regex (which doesn't have possessive quantifiers), you can use this to pop group 1 the greatest multiple of 3 (with maximum 30) times (not golfed very well):

```
(?>((?<-1>){3}|){10})

```

In flavors that have neither of the two features, such as ECMAScript, you could usually use lookahead for this, but may not worth it unless you already need lookahead anyway:

```
(?=(atomic group))\1

```

# Answer
> 4 votes
# Forget a captured group after a subexpression (PCRE)

For this regex:

```
^((a)(?=\2))(?!\2)

```

If you want to clear the \2 after group 1, you can use recursion:

```
^((a)(?=\2)){0}(?1)(?!\2)

```

It will match `aa` while the previous one won't. Sometimes you can also use `??` or even `?` in place of `{0}`.

This might be useful if you used recursions a lot, and some of the backreferences or conditional groups appeared in different places in your regex.

Also note that atomic groups are assumed for recursions in PCRE. So this won't match a single letter `a`:

```
^(a?){0}(?1)a

```

I didn't try it in other flavors yet.

For lookaheads, you can also use double negatives for this purpose:

```
^(?!(?!(a)(?=\1))).(?!\1)

```

# Answer
> 1 votes
# Multiple lookaheads that always match (.NET)

If you have 3 or more lookahead constructs that always match (to capture subexpressions), or there is a quantifier on a lookahead followed by something else, so they should be in a not necessarily captured group:

```
(?=a)(?=b)(?=c)
((?=a)b){...}

```

These are shorter:

```
(?(?(?(a)b)c))
(?(a)b){...}

```

where `a` should not be the name of a captured group. You can't use `|` to mean the usual thing in `b` and `c` without adding another pair of parentheses.

Unfortunately, balancing groups in the conditionals seemed buggy, making it useless in many cases.

---
Tags: code-golf, tips, regular-expression
---


# Question
Title: Partitioning Digits into Distinct Integers
Given a sequence of base-10 digits, output the longest list of integers that contains all the digits exactly once, in the order in which they appeared in the input, without repeating any integers.

# Examples

```
Input: 12345
Output: [1, 2, 3, 4, 5]

Input: 12123
Output: [1, 2, 12, 3]

Input: 10010
Output: [100, 1, 0]

Input: 35353
Output: [35, 3, 53] or [3, 5, 353]

Input: 988382
Output: [9, 88, 3, 8, 2]

```

# Rules

* Use any convenient formats for input and output
* You must support input sequences of up to 10,000 digits long.
* You must support integers of 18 decimal digits or more (This will fit in 64-bit integers, though you may want work with strings anyway)
* You may assume that the input given can be made into a sequences where the 18-digit number requirement is possible.
* If there is more than one possible longest sequence, you may output any one of them.
* Numbers in the output sequence may not be zero-padded.
* Zero is a valid element, but it can, of course, only be used once in the output.
* There is no time or complexity requirement.
* Shortest code wins.

# Answer
# Jelly, 14 bytes

```
ŒṖḌD$ƑƇḌQƑƇLÞṪ

```

Try it online!

A monadic link taking a list of base-10 digits and returning a list of integers.

Added a byte (and switched to numbers) because of the zero padding issue.

Added 5 bytes to fix a further issue with zeros pointed out by @KevinCruijssen - thanks!

## Explanation

```
ŒṖ             | Partitions of list
  ḌD$ƑƇ        | Keep only those invariant when converted to integers and back to lists of digits
       Ḍ       | Convert from lists of lists of lists of decimal digits to lists of lists of integers
        QƑƇ    | Keep only those invariant when uniquified
           LÞ  | Sort by ascending length
             Ṫ | Tail

```
> 4 votes

# Answer
# Perl 6, 49 bytes

```
{m:ex/(0|<![0]>.+)+<!{$0>set ~<<$0}>/.max(+*[0])}

```

Try it online!

Outputs a regex match with a list of submatches as the integers.

### Explanation:

```
{                                               }  # Anonymous code block
 m:ex/                              /    # Match all
      (          )+                        # Series of
       0|                                  # Zero or
         <![0]>.+                          # Numbers not starting with zero
                   <!{$0          }>     # Where the series is not
                        >set ~<<$0       # Larger than the set of itself
                                     .max(+*[0])   # Return the maximum by length of series

```
> 2 votes

# Answer
# 05AB1E, 10 bytes

```
.œʒÙïJQ}éθ

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~115~~ ~~112~~ 114 bytes

Takes input as a string. A recursive function that takes a string and a list of previously-used numbers; it gets all substrings that start with the first character, and for each gets the result of the recursive call on the rest of the string. It then decides what the longest string that still matches is.

```
f=->s,*e{(1..l=s.size).map{|i|*q=x=s[0,i];q-e==[]||x=~/^0./?[]:q+f[s[i,l],*q+e]}.max_by{|i|s==i*''?i.size: 0}||[]}

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 100 bytes

Takes input as a string.

```
f=([v,...a],p=o=[],c='')=>(v&&f(a,p,c+v),c?p.includes(c)|[+c]!=c||f(a,[...p,c],v):p[o.length]?o=p:o)

```

Try it online!

### Commented

```
f = (                    // f is a recursive function taking:
  [v,                    //   v   = next digit
     ...a],              //   a[] = array of remaining digits
  p = o = [],            //   p[] = current list, o[] = best list
  c = ''                 //   c   = current pattern
) => (                   //
  v &&                   // if v is defined:
    f(a, p, c + v),      //   do a recursive call with c + v
  c ?                    // if c is not empty:
    p.includes(c) |      //   unless p[] already includes c
    [+c] != c ||         //   or c has leading zeros:
      f(a, [...p, c], v) //     do a recursive call with c appended to p[]
  :                      // else:
    p[o.length] ? o = p  //   update o[] to p[] if p[] is longer than o[]
                : o      //   or just return o[] unchanged otherwise
)                        //

```
> 1 votes

# Answer
# Perl 5, 119 bytes

```
sub f{($s=$_=shift)=~/\b(\d+)\b.*\b\1\b/?push@_,grep!/\b0\d/,map$s=~s/^((.*?,){$_}.*?),/$1/r,0..y/,//:return$s while@_}

```

Try it online!

```
sub f {
  ($s=$_=shift)                               #get next trial
    =~ /\b(\d+)\b.*\b\1\b/                    #duplicate exist in trial?
    ? push @_,                                #if so, add trials
           grep !/\b0\d/,                     #without zero-leading
           map $s=~s/^((.*?,){$_}.*?),/$1/r,  #remove nth comma
           0 .. y/,//                         #that many trials (-1)
    : return $s                               #answer = 1st w.o. duplicate
        while @_                              #while trials left
}

```

Passes:

```
12345     → 1,2,3,4,5
12123     → 12,1,2,3
10010     → 100,1,0
35353     → 353,5,3
988382    → 9,88,3,8,2
1001000   → 10,0,1000
100100010 → 100,1000,1,0

```
> 1 votes

# Answer
# Burlesque, 24 bytes

```
PppPsu5cb{++pP==}f[:U_[~

```

Try it online!

Not necessarily the best method, think I could probably save on some loading.

```
Pp    #Save number (as str) for later use
pP    #Load number
su    #Find all substrings of number
5cb   #Find all combinations of substrings of length 5 (as list of list of str)
{
 ++   #Concatenate all strings
 pP   #Load number
 ==   #Is equal
}f[   #Filter for all substring combinations where
       the concatenation is the same as original number
:U_   #Filter for all elements unique
[~    #Take the last one

```
> 1 votes

# Answer
# Charcoal, 55 bytes

```
⊞υ⟦ωＳ⟧Ｆυ«≔⊟ιθＦＬθＦ∧Ｉ§θκ¬№ι…θκ⊞υ⁺ι⟦…θκ✂θκ⟧⊞ιθ»⊟Φυ⁼Ｌι⌈ＥυＬλ

```

Try it online! Link is to verbose version of code. Outputs each integer preceded by a newline. Explanation:

```
⊞υ⟦ωＳ⟧Ｆυ«

```

Perform a breadth-first search starting from the input and having only seen the empty string before.

```
≔⊟ιθ

```

Temporarily separate the current suffix from the list of previously seen integers.

```
ＦＬθ

```

Loop over the potential new suffixes. (The next integer is then the current suffix with the new suffix removed.)

```
Ｆ∧Ｉ§θκ¬№ι…θκ

```

Check that the new suffix does not begin with zero and the next integer has not already been seen.

```
⊞υ⁺ι⟦…θκ✂θκ⟧

```

If so then create a new entry including the next integer and the new suffix.

```
⊞ιθ»

```

Restore the suffix for the entry in case no suffixes were valid.

```
⊟Φυ⁼Ｌι⌈ＥυＬλ

```

Print the last entry of those with the longest length.
> 0 votes

# Answer
# PHP, ~~380~~ ~~338~~ ~~287~~ 279 bytes

```
<?php $s=array_fill(0,$n=strlen($u=$argv[1]),0);$m=[];g:if(array_sum($s)==$n){$b=[];$p=0;$k=1;foreach($s as$c){$c&&($b[]=substr($u,$p,$c))[0]==0&&$c>1&&$k=0;$p+=$c;}if($k&&array_unique($b)==$b&&$b>$m)$m=$b;}for($i=0;;){if(++$s[$i]<=$n)goto g;$s[$i++]=0;$i==$n&&die(print_r($m));}

```

Try it online!

## Ungolfed

```
<?php
$input= $argv[1];

$len=strlen($input);
$counts=array_fill(0,$len,0); // enumerator - basically a counter to base input-length, where each digit represents substring length
$max=0;
$max_sub=[];
do {
    // add up size of all substring lengths
    $size=0;
    for($i=0;$i<$len;$i++) {
        $size+=$counts[$i];
    }

    // size matches string length
    if ($size==$len){
        $subs=[];
        $pos=0;

        // get the substrings and ensure constraints
        $ok=true;
        for ($i=0;$i<$len;$i++) {
            //exclude zero length substrings
            if ($counts[$i]>0) {
                $sub = $subs[] = substr($input, $pos, $counts[$i]);
                if ($sub[0]=='0' && $counts[$i]>1) {
                    $ok=false;
                    break;
                }
                $pos+=$counts[$i];
            }
        }

        // makes sure no repeated substrings
        for($i=0;$i<count($subs);$i++){
            for($j=0;$j<$i;$j++){
                if($subs[$i]==$subs[$j]) {
                    $ok=false;
                    break(2);
                }
            }
        }

        // if all ok, then check this has maximal number of substrings
        if ($ok) {
            if (count($subs)>$max) {
                $max=count($subs);
                $max_sub=$subs;
            }
        }
    }

    // increment counter
    for($i=0;$i<$len;$i++) {
        $counts[$i]++;
        if ($counts[$i]<=$len) {
            break;
        }
        $counts[$i]=0;
    }

// counter hasn't reached the end
} while ($i<$len);

echo json_encode($max_sub);

```
> 0 votes

---
Tags: code-golf, number, sequence
---