title: Reduced Factorization Leader Changes

text:
# Question
Title: Reduced Factorization Leader Changes
tl;dr: Output the values where the reduced prime factorization leader changes.

Every positive integer has a unique prime factorization. Let's call the reduced prime factorization just the list of multiplicity of the prime factors, ordered by the size of the factors. For instance, the reduced prime factorization of `1980` is `[2, 2, 1, 1]`, because `1980 = 2 * 2 * 3 * 3 * 5 * 11`.

Next, let's record how often each reduced prime factorization happens, over integers in `[1, 2, ..., n]`. For instance, in `[1, 2, ..., 10]`, the following reduced prime factorizations occur:

```
[1]: 4 (2, 3, 5, 7)
[2]: 2 (4, 9)
[1, 1]: 2 (6, 10)
[]: 1 (1)
[3]: 1 (8)

```

We'll call the leader up to `n` the reduced prime factorization that occurs the most often over `[1, 2, ..., n]`. Therefore, the reduced prime factorization leader for `n = 10` is `[1]`. Ties will be broken by the size of the largest integer less than or equal to `n` with that reduced prime factorization, with smaller largest integer being better. For instance, up to `n = 60`, the reduced prime factorizations `[1]` and `[1, 1]` occur 17 times each. The maximum integer in that range giving `[1, 1]` is `58`, while the maximum integer giving `[1]` is `59`. Therefore, with `n = 60`, the reduced prime factorization leader is `[1, 1]`.

I'm interested in the values of `n` where the reduced prime factorization leader changes. Those are the values of `n` where the reduced prime factorization leader is different from the reduced prime factorization leader up to `n-1`. As an edge case, we will say that the leadership changes at `n = 1`, because a leader does not exist for `n = 0`.

Your challenge is to output.

An initial sequence of the desired output is:

```
1, 3, 58, 61, 65, 73, 77, 1279789, 1280057, 1280066, 1280073, 1280437, 1280441, 1281155, 1281161, 1281165, 1281179, 1281190, 1281243, 1281247, 1281262, 1281271, 1281313, 1281365

```

Allowed output styles are:

* Infinite output.
* The first `k` leader changes, where `k` is the input.
* The `k`th leader change, where `k` is the input.

`k` may be zero or one indexed.

This is code-golf. If you're not sure about anything, ask in the comments. Good luck!

# Answer
# Husk, 18 bytes

```
m←ġ(←►Lk=mȯmLgpṫ)N

```

Try it online! This prints the infinite list. The link truncates the result to the first 7 values, since the program is quite inefficient and times out after that on TIO.

The parentheses are ugly, but I don't know how to get rid of them.

## Explanation

```
m←ġ(←►Lk=mȯmLgpṫ)N  No input.
                 N  The list of natural numbers [1,2,3,4,..
  ġ(            )   Group into slices according to this function.
                    Each slice corresponds to a run of numbers with equal return values.
    ←►Lk=mȯmLgpṫ    Function: from n, compute the reduced factorization leader in [1..n].
                     As an example, take n = 12.
               ṫ     Reversed range: [12,11,10,9,8,7,6,5,4,3,2,1]
         m           Map over this range:
              p       Prime factorization: [[2,2,3],[11],[2,5],[3,3],[2,2,2],[7],[2,3],[5],[2,2],[3],[2],[]]
             g        Group equal elements: [[[2,2],[3]],[[11]],[[2],[5]],[[3,3]],[[2,2,2]],[[7]],[[2],[3]],[[5]],[[2,2]],[[3]],[[2]],[]]
          ȯmL         Take length of each run: [[2,1],[1],[1,1],[2],[3],[1],[1,1],[1],[2],[1],[1],[]]
       k=            Classify by equality: [[[2,1]],[[1],[1],[1],[1],[1]],[[1,1],[1,1]],[[2],[2]],[[3]],[[]]]
                     The classes are ordered by first occurrence.
     ►L              Take the class of maximal length: [[1],[1],[1],[1],[1]]
                     In case of a tie, ► prefers elements that occur later.
    ←                Take first element, which is the reduced factorization leader: [1]
                    The result of this grouping is [[1,2],[3,4,..,57],[58,59,60],[61,62,63,64],..
m←                  Get the first element of each group: [1,3,58,61,65,73,77,..

```
> 3 votes

# Answer
# JavaScript (ES6), 120 bytes

Returns the N-th leader change, 1-indexed.

```
N=>(F=m=>N?F((F[k=(D=(n,d=2,j)=>d>n?j:n%d?D(n,d+1)+(j?[,j]:[]):D(n/d,d,-~j))(++n)]=-~F[k])>m?F[N-=p!=k,p=k]:m):n)(n=p=0)

```

### Demo

```
let f =

N=>(F=m=>N?F((F[k=(D=(n,d=2,j)=>d>n?j:n%d?D(n,d+1)+(j?[,j]:[]):D(n/d,d,-~j))(++n)]=-~F[k])>m?F[N-=p!=k,p=k]:m):n)(n=p=0)

for(let n = 1; n <= 7; n++) {
  console.log('a(' + n + ') = ' + f(n))
}
```

### Commented

Helper function **D()**, returning the reduced prime factorization of **n** in reverse order:

```
D = (n, d = 2, j) =>             // n = input, d = divisor, j = counter
  d > n ?                        // if d is greater than n:
    j                            //   append j and stop recursion
  :                              // else:
    n % d ?                      //   if d is not a divisor of n:
      D(n, d + 1) + (            //     recursive call with n unchanged and d = d + 1
        j ?                      //     if j is not undefined:
          [,j]                   //       append a comma followed by j
        :                        //     else:
          []                     //       append nothing
      )                          //
    :                            //   else:
      D(n / d, d, -~j)           //     recursive call with n divided by d and j = j + 1

```

Main function:

```
N =>                             // N = target index in the sequence
  (F = m =>                      // m = # of times the leader has been encountered
    N ?                          // if N is not equal to 0:
      F(                         //   do a recursive call to F():
        (F[k = D(++n)] =         //     increment n; k = reduced prime factorization of n
                         -~F[k]) //     increment F[k] = # of times k has been encountered
        > m ?                    //     if the result is greater than m:
          F[N -= p != k,         //       decrement N if p is not equal to k
                         p = k]  //       update p and set m to F[p]
        :                        //     else:
          m                      //       let m unchanged
      )                          //   end of recursive call
    :                            // else:
      n                          //   stop recursion and return n
  )(n = p = 0)                   // initial call to F() with m = n = p = 0

```
> 1 votes

# Answer
# Stax, 24 bytes

```
Ç▓Δk/‼&²Θºk∙♥╜fv╛Pg8╝j♀§

```

This program takes no input and theoretically produces infinite output. I say "theoretically" because the 8th element will take more than a year.

Run and debug it

The corresponding ascii representation of the same program is this.

```
0WYi^{|n0-m|=c:uny=!*{i^Q}Md

```

It keeps the last leader on the stack. Iterating over integers, if there's a distinct mode in the factor representation, and it's different than the last one, output it.

```
0                               push zero for a placeholder factorization
 W                              repeat the rest of the program forever
  Y                             store the last factorization in the y register
   i^                           i+1 where i is the iteration index
     {    m                     using this block, map values [1 .. i+1]
      |n0-                          get the prime exponents, and remove zeroes
           |=                   get all modes
             c:u                copy mode array and test if there's only one
                ny=!            test if mode array is not equal to last leader
                    *           multiply; this is a logical and
                     {   }M     if true, execute this block
                      i^Q       push i+1 and print without popping
                           d    discard the top of stack
                                    if it was a leader change, this pops i+1
                                    otherwise it pops the mode array
                                at this point, the last leader is on top of
                                the stack

```
> 1 votes

# Answer
# Python 2, 145 bytes

```
m=i=0;f=[]
while 1:
 i+=1;a=i;d=[0]*-~i;k=2
 while~-a:x=a%k>0;k+=x;a/=x or k;d[k]+=1-x
 k=filter(abs,d);f+=k,;c=f.count
 if c(k)>c(m):print i;m=k

```

Try it online!

## Ungolfed

```
m=0                    # reduced prime factorizations leader
i=0                    # current number
f=[]                   # list of reduced prime factorizations
while 1:               # Infinite loop:
  i+=1                 #   next number
  a=i                  #   a is used for the prime factorization
  d=[0]*-~i            #   this lists stores the multiplicity
  k=2                  #   current factor
  while~-a:            #   As long as a-1 != 0:
    x=a%k>0            #      x := not (k divides a)
    k+=x               #      If k does not divide a, go to the next factor
    a/=x or k          #      If k does not divide a,
                       #         divide a by 1,
                       #         else divide it by k
    d[k]+=1-x          #      add 1 to the multiplicity of k if k divides a
  k=filter(abs,d)      #   Only keep non-zero multiplicities
                       #     k is now the reduced prime factorization of i
  f+=k,                #   append k to the list of reduced prime factorizations
  c=f.count            #   c(x) := number of occurences of x in f
  if c(k)>c(m):        #   has the current reduced prime factorization
                       #    appeared more often than the leader?
    print i;m=k        #     print the current number, set new leader

```

Try it online!
> 0 votes

# Answer
# Jelly,  ~~35~~  34 bytes

I feel like it's still golfable

```
ÆEḟ0µ€ĠL€M⁸’ß¤¹Ṗ?
®‘©Ç€F0;ITµL<³µ¿

```

A full program taking `k` and outputting a Jelly list representation of the first `k` leader change points.

**Try it online!**
> 0 votes

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


title: Regex for multiples of 9

text:
# Question
Title: Regex for multiples of 9
It is easy to describe a finite state machine that recognizes multiples of 9: keep track of the digit sum (mod 9) and add whatever digit is accepted next. Such a FSM has only 9 states, very simple! By the equivalence between FSM-recognizability and regular languages, there is a regular expression for multiples of 9. However, any such regular expression is likely... very... long. As in, likely on the order of a gigabyte.

There is a worked example at https://www.quaxio.com/triple/ for multiples of 3. At the bottom of the page, the author provides a somewhat "hand-optimized" solution that's a bit shorter than the naive conversion from FSM to regex.

### The challenge:

You must make a regex to detect multiples of 9. Since such a regex is expected to be very long, I ask that you provide a program that can print out your regex. (If you really want to give a whole regex, perhaps host it elsewhere and link it here!)

You must be able to tell us the exact character count of your program's output -- so having a program that simply tries all regexes up to a certain length, until it finds one that works, is not acceptable unless it runs quickly enough that you can run it to completion and give us the resulting regex length!

Points are for having the shortest output regex, not based on program length, of course. Since the regex is the "program" I am asking for, and it's just too long to conveniently transmit here, I'm still tagging this code-golf.

Rules:

* The input will only include characters matching `[0-9]*`.
* Your regex should *match* multiples of 9, but not anything else. Cases that aren't made entirely of the digits 0-9 and are invalid inputs can either match or fail as you wish.
* Given the motivation that it's easily recognized by a DFA, the resulting regex must actually be *regular expression* in the more theoretic terminology, that is, only operators under which regular languages are closed. To be precise, the only things that are allowed:
    + Literals, character ranges (`[ab]`, `[a-f]`, `[^k]`), Kleene star (`*`), anchors (`^` and `$`), grouping via parentheses, alternation (`|`), optional terms (`?`), one-or-more terms (`+`), lookaheads (`(?=)`), negative lookaheads (`(?!)`), lookbehinds (`(?<=)`), negative lookbehinds (`(?<!)`), conditionals (as in https://www.regular-expressions.info/conditional.html -- `(?(?=test)then|else)` ), and backreferences of bounded length (see below).
* Examples of things that are *not* allowed:
    + Backreferences of arbitrary length, forward references, Recursion, subroutines, looping constructs, executable code, any variation of 'eval', or built-in constructs for casting the string to an arithmetic value.
* Backreferences that can be shown to have a bounded-length binding string are acceptable, as they can be stored in finite state and do not alter the regularity of the language. For instance, the regex `(..2.[3-5])4\1.\1` is acceptable, as there is bound length on the capturing group `\1`. This is a regular construction. A construct such as `(2*)0\1` is not acceptable, as the captured group cannot be stored in finite state.
* Your regex is free to accept or reject integers with extraneous leading zeroes as you wish. However, the string `"0"` must be accepted.

# Answer
# Haskell, ~~207,535~~ 202,073 bytes

5,462 bytes saved by using `0|9` instead of `[09]` where possible.

```
digits n
  | x == 0    = "0|9"
  | otherwise = show x
  where x = mod n 9

regex 0 = "[09]*"
regex n = (regex' n (-1) (-1)) ++ "*"

regex' 0 start end = digits (end - start)
regex' n start end = '(':(regex' 0 start end) ++ (concat ['|':(regex' (n-x) (start-x) (-1)) ++ (regex (n-x))
                                                  ++ (regex' (n-x) (-1) (end-x)) | x <- [1..n]]) ++ ")"

main = do
  putStr ("^" ++ (regex 8) ++ "$")

```

Try it online!

Just a quick adaptation of the regex given in the footnotes of the linked article to get things started.

Pastebin of output regex, courtesy of Herman Lauenstein.

While I have not been able to test the full regex, modifying the program to check divisibility by 3 instead gives something exactly equivalent to the regex I based this on. Furthermore, modifying the program to check the digit sum's divisibility by 4 or 5 also seems to work on the numbers I tested it on.
> 3 votes

---
Tags: code-golf, number-theory, regular-expression
---


title: Output the Source, One Bit at a Time

text:
# Question
Title: Output the Source, One Bit at a Time
Write a non-empty program or function that when called outputs a single value, 1 or 0, and when called multiple times, the output numbers produce the binary representation of your program's source code (in the same code page from which your code is compiled/interpreted).

For instance, if your source code was `abc` (in ASCII), the outputs would be:

```
1st call:  0           // ASCII letter 'a'
2nd call:  1
3rd call:  1
4th call:  0
5th call:  0
6th call:  0
7th call:  0
8th call:  1

9th call:  0           // ASCII letter 'b'
10th call: 1
11th call: 1
12th call: 0
13th call: 0
14th call: 0
15th call: 1
16th call: 0

17th call: 0           // ASCII letter 'c'
18th call: 1
19th call: 1
20th call: 0
21st call: 0
22nd call: 0
23rd call: 1
24th call: 1

After the 24th call, the behaviour is undefined.

```

The binary representation of the source must contain at least one 0 bit and one 1 bit.

Instead of 1 and 0, you can output any two distinct, consistent values (such as `true` and `false`).

Self-modifying programs that output the binary representation of the original source are allowed, provided that they don't read the source code to find out what to print next.

This is , so the shortest answer in bytes wins.

# Answer
# Funky, ~~47~~ ~~41~~ 37 bytes

Returns a number representing a bit.

```
f=_=>1&("%b"%("f="+f)[i//8])>>7-i++%8

```

This uses the quine format of `f=_=>"f="+f`. It takes the character at position **⌊i/8⌋**, then, gets the bit by taking the pairity of `n >> 7-i%8` where `n` is the ascii value of the current character.

This is an iterative function that increments `i` with each call, once it's out of source code, it will write the code for `n` forever.

Try it online!
> 8 votes

# Answer
# Bash, 105 bytes

```
trap -- 'trap|xxd -b -c1|cut -d\  -f2|tr -d \\n|cut -c`x=\`cat f||echo 1\`;echo $((x+1))>f;echo $x`' EXIT

```

**NOTE**: Make sure that you don't have an important file called `f` in the directory you're testing this.

---

If you want to test this, you can use the following command:

```
for i in $(seq 848); do bash path/to/script.sh 2> /dev/null; done | tr -d \\n

```

Which should give the same output `xxd -c1 -b path/to/script.sh|cut -d\ -f2|tr -d \\n`.

## Explanation

This is using the `trap` trick - calling `trap` inside the `trap` action simply prints that line. Next that output gets piped to `xxd` which converts it to binary (unfortunately `xxd -bp` doesn't work - thus the workaround with `cut` & `tr`):

```
xxd -c1 -b $0|cut -d\  -f2|tr -d \\n

```

From that we're only interested in one bit (say `N`) which we can select with `cut -cN`.

To find out what `N` we're using (remember that's the part that needs to be incremented after each call), simply try to set `x` to the content of the file `f` and if it doesn't exist set it to 1:

```
x=`cat f||echo 1`

```

Last thing to do, is to update the file `f` \- writing `x+1` to it:

```
echo $((x+1))>f

```
> 9 votes

# Answer
# TI-Basic (TI-83 series), ~~592~~ ~~357~~ 309 bytes

```
"123456789ABCDEF02A3132333435363738394142434445463004AA003FB958833404593FB9588338045A3F3230363FDA582B383F303FCE5A405A6B3232333F5A70BB0FAA002BBB0CAA002B5A2B313FB932BA32F01058713459713511BB0FAA002BBB0CAA002B597031377132722B31→Str1
iPart(X/4→Y
iPart(X/8→Z
206
IS>(X,8
0
If Z and Z<223
Z+inString(Str1,sub(Str1,Z,1
iPart(2fPart(2^(X-4Y-5)inString(Str1,sub(Str1,Y+17-2Ans,1

```

This table is a possible reference for the calculator's binary representation of the source code, though ultimately I just used Virtual TI's debugger.

For comparison and/or historical interest: the first quines written in TI-Basic.

# How it works

`Str1` stores the source code (now in glorious hexadecimal, saving lots of space over the previous binary version), leaving out the bits where the contents of `Str1` itself would be represented.

We're assuming that the program starts out on a calculator whose memory has just been cleared, so `X` is `0`. Every time through the program, we increment `X`.

Usually, we just figure out the half-byte we're trying to extract a bit from, read it out of `Str1`, convert from hexadecimal to binary, and print it. If we're on the part of the source code that's storing `Str1` (which is two-thirds of the total length of the program), then we first move to the corresponding part of the string storing `31`, `32`, and so on.
> 7 votes

# Answer
# Java 8, ~~249~~ ~~241~~ ~~237~~ ~~234~~ 148 bytes

```
int i;v->{String s="int i;v->{String s=%c%s%1$c;return s.format(s,34,s).charAt(-i/8)>>(--i&7)&1;}";return s.format(s,34,s).charAt(-i/8)>>(--i&7)&1;}

```

*Sorry in advance for the long explanations. :)*

* Whopping 89 bytes saved thanks to *@Nevay*.

Try it here.

**Explanation:**

```
int i;                     // Index-integer on class-level
v->{                       // Method with empty unused parameter and integer return-type
  String s="int i;v->{String s=%c%s%1$c;return s.format(s,34,s).charAt(-i/8)>>(--i&7)&1;}";
                           //  String containing the unformatted source code
  return s.format(s,34,s)  //    Quine to get the source code,
      .charAt(-i/8)        //     and get the character at index `-i/8`
     >>                    //    And bitwise right-shift it with:
       (--i&7)             //     `i-1` bitwise-AND 7
                           //     by first decreasing `i` by 1 with `--i`
      &1;                  //   Then bitwise-AND everything above with 1
}                          // End of method

```

Additional explanation:

-part:

* `String s` contains the unformatted source code
* `%s` is used to put this String into itself with `s.format(...)`
* `%c`, `%1$c` and `34` are used to format the double-quotes (`"`)
* `s.format(s,34,s)` puts it all together

Try it here with some parts removed/modified to verify the quine outputs it's own source code.

-part:

---

Old **233 bytes** answer:

```
int i;v->{String s="int i;v->{String s=%c%s%1$c;return Long.toString((s.format(s,34,s).charAt(i/8)&255)+256,2).substring(1).charAt(i++%%8);}";return Long.toString((s.format(s,34,s).charAt(i/8)&255)+256,2).substring(1).charAt(i++%8);}

```

Try it here.

**Explanation:**

```
int i;                           // Index-integer on class-level
v->{                             // Method with empty unused parameter and char return-type
  String s="int i;v->{String s=%c%s%1$c;return Long.toString((s.format(s,34,s).charAt(i/8)&255)+256,2).substring(1).charAt(i++%%8);}";
                                 //  String containing the unformatted source code
  return Long.toString(
          (s.format(s,32,s)      //  Quine-formatting
          .charAt(i/8)           //  Take the current character
           &255)+256,2).substring(1)
                                 //  Convert it to an 8-bit binary-String
         .charAt(i++%8);         //  And return the bit at index `i` modulo-8
                                 //  and increase index `i` by 1 afterwards with `i++`
}                                // End of method

```

Additional explanation:

-part:

Same explanation as above, with the addition of:

* `%%` is the escaped form of the modulo-sign (`%`)

Try it here with some parts removed/modified to verify the quine outputs it's own source code.

-part:

* `i/8` will automatically truncate on integer division, so when `i` is 0-7, it will become `0`; if `i` is 8-15, it will become `1`; etc.
* So `s.charAt(i/8)` takes the current character of the source-code, eight times after each other. Try it here with a modified version.
* `255` is `0xFF` or `11111111` (the max value for an unsigned byte)
* `256` is `0x100` or `100000000`.
* The `&` upcasts the ASCII-character to an integer. At that point, it's anywhere between `0` and `255` (`00000000` to `11111111`).
* `Long.toString(...,2)` converts it to the 9-bit binary String representation
* `+256` and `.substring(1)` will ensure there are leading zeroes, and will convert the 9-bit to an 8-bit.

Try it here with some parts removed/modified to verify the entire bytes.
> 4 votes

# Answer
# Javascript ES6, ~~73~~ ~~58~~ 52 bytes

```
o=_=>`o=${o}`.charCodeAt((o.n=1+o.n|0)/8)>>(7-o.n%8)&1

```

# Explanation

Breakdown of the code:

* `o=_=>`: define a function.
* ``o=${o}``: construct a string; `o` is converted to a string, which in this case is the function's source code.
* `.charCodeAt(`: get a character in the string as its ASCII character code.
* `(o.n=1+o.n|0)/8`: select a character. This is also where the counter is incremented.
* `)>>(7-o.n%8)`: shift the resulting character code so that the desired bit is in the right position.
* `&1`: set all other bits to 0.
> 2 votes

# Answer
# q/kdb+, 45 bytes

**Solution:**

```
a:-1;f:{((,/)0b vs'4h$"a:-1;f:",($).z.s)a+:1}

```

**Example:**

```
q)f[] / call function f with no parameters
0b
q)f[]
1b
q)f[]
1b
q)f[]
0b
q)f[]
0b
q)f[]
0b
q)f[]
0b
q)f[]
1b
q)f[]
q)"c"$0b sv 01100001b / join back to a byte and cast to a character
"a"

```

**Explanation:**

I *think* I understood the brief.

First setup a global variable `a` with starting value of `-1`. Function `f` builds the binary representation of the *string* representation of the function (everything including the `{}`) prepended with the `a:-1;f:` junk, and indexes into this binary list at index a (which gets incremented each call).

```
a:-1;f:{(raze 0b vs'4h$"a:-1;f:",string .z.s)a+:1} / ungolfed solution
a:-1;                                              / stick -1 in variable a
     f:{                                         } / define function f
                                             a+:1  / increment a by 1 (:: is required as a is a global variable), indexes into the left
        (                                   )      / do all this together
                                 string .z.s       / z.s is the function, string converts it to a string
                       "a:-1;f:",                  / prepend "a:-1;f:" to the start
                    4h$                            / cast to bytes
              0b vs'                               / convert each byte to binary
         raze                                      / flatten binary into long list

```
> 2 votes

# Answer
# Python 2, 164 bytes

```
lambda s='lambda s=%r,i=[]:i.append(1)or"{:08b}".format(ord((s%%s)[~-len(i)/8]))[~-len(i)%%8]',i=[]:i.append(1)or"{:08b}".format(ord((s%s)[~-len(i)/8]))[~-len(i)%8]

```

Try it online!

## Explanation

Let's start with a standard Python 2 quine.

```
s = '...'; print s % s

```

Okay, well, this outputs it just like that. We need binary!

```
s = '...'; print "\n".join("\n".join("{:08b}".format(ord(i))) for i in s % s)

```

Right, that just converts everything to binary. But the title says "one bit at a time". We need something to persist through multiple runs. I know, let's make it a function!

```
lambda s = '...': "\n".join("\n".join("{:08b}".format(ord(i))) for i in s % s)

```

Wait, that doesn't help... Hmm, how can we keep track of the index of the bit needed to be output? Ooh, ooh, let's have an integer to keep track.

```
lambda s = '...', i = 0: "{:08b}".format(ord((s % s)[i / 8]))[i % 8]

```

Um... that always outputs the first bit. Oh, we need to increment the tracker! Oh crap, Python doesn't allow integers as default arguments to be modified. And assignments aren't expressions in Python, so you can't do that in a lambda. Welp, this is impossible in Python, case closed.

...Well, not quite. Python *does* allow lists as default arguments to be modified. (And it bites Python programmers all the time.) Let's use its length!

```
lambda s = '...', i = []: "{:08b}".format(ord((s % s)[len(i) / 8]))[len(i) % 8]

```

That still doesn't modify the tracker though... We can append something to it to increase its length... But how? Ah, well, we've got `list.append`. `lst.append(1)` is equivalent to `lst += [1]`. Great!

```
lambda s = '...', i = []: i.append(1) and "{:08b}".format(ord((s % s)[len(i) / 8]))[len(i) % 8]

```

Whoops, this skips the first bit because the length of the tracker is **1** before the bit is outputted. We need to decrement the length where it's used.

```
lambda s = '...', i = []: i.append(1) and "{:08b}".format(ord((s % s)[(len(i) - 1) / 8]))[(len(i) - 1) % 8]

```

There it is, folks! Golf it and you've got my solution!
> 2 votes

# Answer
## Perl 5, 59 bytes

```
sub{$_=q{unpack(B.++$-,"sub{\$_=q{$_};eval}")=~/.$/g};eval}

```

Try it online!
> 2 votes

---
Tags: code-golf, quine, binary
---


# Question
Title: Cops and Robbers: Redacted Primality (Robbers' Thread)
*This is the robbers' thread. The cops' thread is here.*

Your challenge is to take an uncracked submission from the cops' thread and try to find the original unredacted program. Please comment on the cop's submission when you've cracked their code.

# Answer
> 6 votes
# brainfuck, Jo King

```
>>>>>+>,[>++++++[-<-------->]<+>,]<[-[█<█<]++++++++++<]>[-]>>██[>█>>█>]+[<]<<[<]>█<<+>>[>]█>[>]█+[<]<<[<]>-█>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<█]>]>[>]<[[█]<]<<<<<[<]<<██>>[>]<█[->+<]<█>>[>]<[-[[<]<]++++++++++<]>███>[<<]>[[[>]>████[<]<[-[[<]<]++++++++++<]>[-]>[█<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>███████>[[█]>]<]<[[<]<]<[█]>]>>>[[>]<->>]]>[[>]>]<<[[[█]<]<]<<<[█]<<█>>>[>]█[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.
>>>>>+>,[>++++++[-<-------->]<+>,]<[-[[<]<]++++++++++<]>[-]>>[[[>]>>[>]+[<]<<[<]>[<<+>>[>]>>[>]<+[<]<<[<]>-]>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]<]<<<<<[<]<<[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>[[-]+>]>[[>]>]<]<[[<]<]<[<]>]>>>[[>]<->>]]>[[>]>]<<[[[-]<]<]<<<[<]<<]>>>[>]<[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.

```

Try it online!

This implements the sieve of Eratosthenes.

The initial `>>>>>+>,[>++++++[-<-------->]<+>,]` inputs each digit as an character code and subtracts 47 to put it in the range 1-10. This allows a cell value of 0 to denote spacing between numbers. The `+>` near the beginning of this section forces the number to be at least two digits, which will be important soon.

Next, and one of the first things I figured out, is the section `<[-[[<]<]++++++++++<]>[-]>`. This appears several times in the code, each with different patterns of redaction, but it was not hard to guess that all of those instances were probably the same code. This code requires three zeros to the left of the decimal number on the tape, and its effect is to decrement the number. The last iteration of the loop will put the value 10 two cells left of the number, but the `[-]` cleans it up.

If the decimal number was 0, there is no extraneous 10 created, and the cell zeroed by `[-]` is the most significant digit. The tape head is then at the second-most significant digit (which is why at least two digits are necessary). Most instances of this snippet are immediately followed by `[<<]>`, which places the head on a nonzero cell in normal conditions and a zero cell if the original decimal number was zero. It seems that in this program, the decimal representation of `n-1` is used to denote `n`, so that decrementing to `0` is caught instead of decrementing to `-1`.

The next part puts the numbers from n-1 (n) down to 0 (1) on the tape:

```
>[                      until the number reaches zero:
  [                     for each digit:
    [>]>>[>]+[<]<<[<]>  create a placeholder for the next copy
    [                   while the original value of the digit is nonzero:
      <<+               add 1 to copy two cells left (to keep one copy)
      >>[>]>>[>]<+      go to new copy and increment that cell
      [<]<<[<]>-        go back to original digit and decrement
    ]                   (this is effectively the same as [<+>>+<-] but with the cells at variable locations)
  >]                    next digit
  >>[->]                cancel the placeholder 1s that were used for the new copy
  <[-[[<]<]++++++++++<]>[-]>[<<]> decrement
]
>[>]<[[-]<]      clean up the trash 10s on the tape while ending at a known location relative to the last number

```

Now, these numbers are all on the tape with two zero cells separating them. `<<<<<[<]<<` puts us at the final cell of the penultimate number on the tape, which is where we will be in every iteration of the loop. The loop terminates when all numbers except the original have been handled.

At the start of the loop, we move the current number (last one still on the tape) one cell right to have room to decrement, and then go ahead and decrement:

```
[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>

```

If this decrement didn't underflow, we proceed to convert the number to unary:

```
[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]

```

Note that this snipped has an unclosed `[`. As a result, the rest of this loop is skipped if the number was 0 (representing 1). After converting to unary, we clear out the leftover 10s, dragging the unary representation with us to the left:

```
>[>]<[[-]>+[>]<-<[<]<]+

```

I didn't notice until just now writing this, but the `+` at the end of this snippet is separated from the unary representation by a single 0. It is also a part of the unary representation: the sequence `1011...11` will represent 0 mod k. The following `<<<<<[<]>` puts us at the beginning of the number `k+1`, starting a new loop.

The inner loop here "marks" every number on the tape with a 1 on the cell immediately right, and uses the unary representation as a clock to determine which numbers are multiples of `k`.

```
[
  [>]+             mark the current decimal number
  [[>]>]           move to end of decimal part of tape
  >[>]             move to 0 in middle of unary "clock"
  >[-<+>]          move the following 1 to the left if possible
  <[<]<            if a 1 was moved this will bring us back to a zero before the start of this "clock";
                   otherwise the looped move command doesn't move us at all and we are at the final 1
  [                if there was no gap (happens every kth iteration):
    >+[<]>>-       reset to original position
    <<<<<[[<]<]>>  go to number that was just marked
    [[-]+>]        replace digits with 0s (cell value 1)
    >[[>]>]<       go back to where we would be without this conditional
  ]
  <[[<]<]<[<]>     return to first unmarked number
]

```

The `[[-]+>]` in that section was the last part I figured out. Before that, I assumed the program was just doing trial divisions, but I couldn't see where the result was used.

This loop ends two cells left of the far left number, and `>>>[[>]<->>]]` removes the markers placed on the tape and gets us to the end of the tape again. After that `>[[>]>]<<[[[-]<]<]` removes either the unary clock or, if this entire segment was skipped, the leftover 10s. The loop is set to its starting condition with `<<<[<]<<]`.

After this is just reading whether the input number was replaced by 1 at any point:

```
>>>[>]<[-[[<]<]++++++++++<]>>                      do the check
[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]      conditionally print "not "
>[>]+[------->++<]>++.++.---------.++++.--------.  unconditionally print "prime"

```

Fortunately, the actual output was not redacted at all.

# Answer
> 5 votes
# Wolfram Language (Mathematica)

Cracks this answer.

```
f[x_]:=(p=ToString@Boole@PrimeQ@x;StringMatchQ[p&@@Infinity,RegularExpression@"(\
\n{}\b+, )?1"])

```

Try it online!

# Answer
> 5 votes
# Brain-Flak, MegaTom

```
(({████){██[████)█>(({}))<>}<>{}███{}((██({}))█████{}]██)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})██[██()██(()█[()]██{}██}{}<>{})
(({})<>){([[]]{})<>(({}))<>}<>{}{}{{}(([]({}))[({}[{}])])({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})}([][()])((){[()](<{}>)}{}<>{})

```

Try it online!

This program performs trial divisions from n-2 down to 1, then outputs 1 if and only if this terminated with the factor 1.

# Answer
> 4 votes
# 8086 DOS COM by Joshua

`xxd` representation, because of encodings and null bytes and other scary stuffs:

```
00000000: 31c0 b90a 0031 dbbe 8100 ac3c 0d74 3c3c  1....1.....<.t<<
00000010: 2075 f7ac 3c0d 7410 2c30 7c2f 3c09 7f2b   u..<.t.,0|/<..+
00000020: 93f7 e193 01c3 ebeb 83fb 027c 19c6 0653  ...........|...S
00000030: 0159 b902 0039 d974 1289 d831 d2f7 f109  .Y...9.t...1....
00000040: d274 0341 ebef c606 5301 4eb4 09ba 5301  .t.A....S.N...S.
00000050: cd21 c341 0d0a 24                        .!.A..$

```

First disassembled the cop manually, then assembled using yasm. Some bytes have been corrupted by the conerter Joshua used, but I've just treated them like redacted bytes. I'm 99.72% certain about their actual content. It shouldn't take long to fix it if I'm wrong, though. Enjoy:

```
; A COM file is just a 16-bit flat binary
; loaded at 0x100 in some segment by DOS

org 0x100
bits 16

; Unsurprisingly, we start by converting
; the commandline string to a number. During
; the conversion, SI is a pointer to the
; string, CX is the base, and BX holds the
; partial result
parse_input:
; We'll read the input character by character
; into AL, but we need the resulting digit as
; a 16-bit number. Therefore, initialise AX to
; zero.
    xor ax, ax
    mov cx, 10
    xor bx, bx
; When a DOS program is loaded, it's preceded
; in memory by the Program Segment Prefix,
; which holds the commandline arguments at
; offset 0x81, terminated by a carriage return
    mov si, 0x81

.skip_prog_name:
; Load a character and move the pointer
    lodsb
; If we find the terminator here, the program
; was not given any arguments.
    cmp al, 13
    je finish

    cmp al, ' '
    jne .skip_prog_name

.input_loop:
    lodsb
    cmp al, 13
    je got_input

; If the ASCII value of the character is less
; than the one of '0', error out. Adjust the
; value in AL so that it holds the digit
; itself. This exploits the fact that the
; comparison instruction is just a subtraction
; that throws away the actual result.
    sub al, '0'
    jl finish

; If we have a value larger than 9, this
; character wasn't a digit.
    cmp al, 9
    jg finish

; Multiply the intermediate result by 10 and
; add the new digit to it.

    xchg ax, bx
    mul cx
    xchg ax, bx
    add bx, ax
    jmp .input_loop

got_input:
; The loop below would go haywire when given a
; zero or a one, so make them a special case.
    cmp bx, 2
    jl composite

; Patch the output string to say that it's
; prime
    mov byte[outstr], 'Y'

; BX = number being checked
; CX = loop counter, potential divisor of BX
    mov cx, 2

.loop:
; If CX = BX, we looked everywhere and couldn't
; find a divisor, therefore the number is prime
    cmp cx, bx
    je finish

; DIV takes DX:AX as a 32-bit number for the
; dividend. We don't want nor need the extra
; precision, so we set DX to 0.
    mov ax, bx
    xor dx, dx
    div cx

; DX now contains the remainder. To check if
; it's 0, we perform some noop operation, that
; happens to set the flags appropriately. AND
; and OR are commonly used for this purpose.
; Because of what's presumably a bug in the
; encoder used by Joshua, I do not yet know
; which for certain. However, I can make an
; educated guess. All other instances of the
; bug happened with a codepoint below 32.
; Moreover, no other bytes from that range
; occur in the code. Because an AND would be
; encoded as an exclamation mark, while OR -
; - as a tab, I am highly confident that Joshua
; used an OR.
    or dx, dx
    jz composite

; Increment the counter and loop again!
    inc cx
    jmp .loop

composite:
    mov byte[outstr], 'N'

finish:
    mov ah, 9
    mov dx, outstr
    int 0x21
    ret

outstr:
    db 'A', 13, 10, '$'

```

# Answer
> 3 votes
# Jelly

Cracks this answer.

```
25██26█966836897364918299█0█1█65849159233270█02█837903312854349029387313█ị██v

```

```
250126,9668368973649182994001,658491592332700020837903312854349029387313ṖịØJv

```

Try it online!

---

Explanation:

Looking at  and `v`, I think of building a list of numbers, ndex it into some list and evaluate it.

The "trivial" way of checking primality in Jelly is `ÆP`, so (if it can cracks the submission):

* The list to be indexed to must contains `Æ` and `P`.
* The list of indices must be congruent modulo `256` with `[14, 81]`.

So... the list at the start of the program congruent to `[14, 81, 49]` mod 256 (TIO) and  pops the last element.

# Answer
> 3 votes
# sh + coreutils

Cracks this answer.

```
e█ec█s█ █c "██████WyAkKHNoIC1jICJg█WNobyBabUZqZEc5eWZIUnlJQ2█2SnlBblhHNG5m██JoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K█b█se6███d`"

```

```
exec sh -c "`echo WyAkKHNoIC1jICJgZWNobyBabUZqZEc5eWZIUnlJQ2M2SnlBblhHNG5mSFJoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K|base64 -d`"

```

No Try it online! this time because of some issues. However you can use jdoodle.

Returns by exit code. `0` (success) for prime, `1` (error) for composite.

The actual command executed is

```
factor|tr ':' '\n'|tail +2|wc -w

```

### How to crack

1. Look at the code, recognize Base64.
2. Learn how to use `base64` command.
3. Know that `+` is a valid base64 character.
4. Try to decode.
5. Apply the wrapper `sh -c "`echo ...|base64 -d`"` back to the original program.
6. Generate nested base64 from commands.

# Answer
> 3 votes
# Octave, 86 bytes, Stewie Griffin.

```
@(x)eval([(str2num(cell2mat([cellstr(reshape('0█1███1█0█0█00',████))])')█'█')','(x)'])
@(x)eval([(str2num(cell2mat([cellstr(reshape('04141113040800',2,[]))])')+'e')','(x)'])

```

Try it online!

This was a fun one! I struggled with this for a good couple of days.

The first clue was recognizing `eval([...,'(x)'])` as a construction creating a call to the `isprime` function, as concatenation of `ints` and `char` will implicitly convert the array to `char`, so the `...` needed to be either `isprime` or an array that had the ASCII values of `isprime`, `[105, 115, 112, 114, 105, 109, 101]`.

The rest of it was just slogging through documentation to figure out that `reshape` can take one unknown dimension with `[]`, although I suppose I could have done `reshape(...,2, 7)` at the same byte count.

Using `+'e'` (101) instead of `+'d'` (100) was a nice touch that threw me for another few minutes until I noticed the last digits (unobfuscated) were `00` rather than `01`, and with that it was easy.

# Answer
> 2 votes
# JavaScript

```
x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=████;--y-1;(p=x/y%1)████if(██&&(███))break████return(███)}
x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=2-1);--y-1;(p=x/y%1)){;;if(!p&&(1<2))break;;;}return(!!p)}

```

Try it online!

I somehow doubt this is exactly what you had in mind, but it works.

# Answer
> 2 votes
# \>\<\>, Esolanging fruit

```
:1@v>~~:?1n;█$-1<█?=2:}*{█@:$@:

```

to

```
:1@v>~~:?1n;
$-1</?=2:}*{%@:$@:

```

Try it online!

Clever use of redacting a newline confused me for a bit. Doesn't seem to work for 1 or 2 though.

# Answer
> 2 votes
# Java (OpenJDK 8), Magic Octopus Urn

```
class X{public static void main(String[]args){System.out.println(new String(████████[Integer.parseInt(args[0])]).matches("█████████████")?███);}}
class X{public static void main(String[]args){System.out.println(new String(new char[Integer.parseInt(args[0])]).matches(".?|(..+?)\\1+")?0:1);}}

```

Try it online!

The code is taken from RosettaCode and explained on SO.

# Answer
> 2 votes
# Python 3, 44 bytes, osuka\_

```
p=lambda x,i=2:i>=x or(x%i and p(x,i+1))or 0

```

Try it online!

Does not work when x\<2. The `or 0` can be replaced with `>0{2 spaces}` or even 4 spaces

For the x\<2 problem, since `i>=x` must be put at the front (otherwise there will be an infinite loop), and the `i>=x` returns true immediately when x\<2, so I think that's no fix with that.

# Answer
> 2 votes
# M, dylnan

```
ÆPø“;;“»VOḣ2S⁵++3Ọ;”Pv

```

This probably wasn't the intended solution.

Try it online!

### How it works

`ÆP` is the built-in primality test.

`ø` beings a new, niladic chain. Since the previous return value (the result of `ÆP`) goes out of scope, this prints it implicitly.

`“;;“»` evaluates to the list of strings `["< Aalst" ""]`, and `V` tries to eval them. `s` tries to split its argument into chunks of length **0**, which causes the M interpreter to crash, suppressing further output.

# Answer
> 1 votes
# Pyth, Mr. Xcoder

```
q]tQ #aQ{*MyP

```

# Answer
> 1 votes
# Python 3, user71546

```
import random
def f(z):
 if z<4:return z>>1
 d,s,n,e,c=~-z,0,z,0,50
 while not d&1:d//=2;s+=1
 while n>0:n//=2;e+=1
 random.seed()
 while c>0:
  a=0
  while a<2or a>z-1:
   a,b=0,e
   while b>0:a=a*2+random.randint(0,1);b-=1
  x,r=pow(a,d,z),~-s
  if ~-x and x!=~-z:
   while r>0:
    x,r=pow(x,2,z),~-r
    if not ~-x:return 0
    elif x==~-z:break
   else:return 0
  c-=1
 else:return 1

```

Try it online!

---
Tags: code-challenge, primes, cops-and-robbers, obfuscation
---


title: Repeat after me!

text:
# Question
Title: Repeat after me!
Given a string as argument, output the length of the longest(s) non-overlapping repeated substring(s) or zero if there is no such string.

You can assume the input string is not empty.

## Examples

`abcdefabc` : the substring `abc` is repeated at positions 1 and 7, so the program should output **3**

`abcabcabcabcab` : `abcabc` or `bcabca` or `cabcab` are repeated, so the program should output **6**. (the substring `abcabcabcab` is also repeated, but the occurrences overlap, so we don't accept it).

`aaaaaaa` : `aaa` is repeated at positions 1 and 4 for example, so the program should output **3**

`abcda` : `a` is repeated, so the program should output **1**

`xyz` : no repeated string → **0**

`ababcabcabcabcab` : should return **6**

This is , so fewest bytes wins.

# Answer
> 9 votes
## brainfuck, 226 bytes

```
,[<<<,]+[>>->[[[[>>[>>>]<+<-<[<<<]>>+<-]>[<+>-]>[>>>]<<[>[<+>-]]>[[<+>-]>+[<<<]>
>>-[+>[<<<]<[>+>[->]<<[<]>-]>[<+>>+<-]>>>[>>>]]>>]<]>+[,<<<+]->[<<<]>>>>>+[,+>>>
+]-[>>>]->]<[+<<<]+<<<++[->>>]+>>>->]<[,<<<]<[>>>+<<<-]>+>,>>>]<<.

```

Formatted:

```
,[<<<,]
+
[
  for each suffix
  >>->
  [
    for each prefix
    [
      for each suffix
      [
        for each char while no mismatch
        [
          >>[>>>]
          <+<-<[<<<]
          > >+<-
        ]
        >[<+>-]
        >[>>>]
        <<
        [
          mismatch
          >[<+>-]
        ]
        >
        [
          [<+>-]
          >+[<<<]
          >>>-
          [
            match
            +>[<<<]
            <
            [
              >+>[->]
              <<[<]
              >-
            ]
            >[<+> >+<-]
            >>>[>>>]
          ]
          >>
        ]
        <
      ]
      >+[,<<<+]
      ->[<<<]
      >>> >>+[,+>>>+]
      -[>>>]
      ->
    ]
    <[+<<<]
    +<<<++[->>>]
    +>>>->
  ]
  <[,<<<]
  <[>>>+<<<-]
  >+>,>>>
]
<<.

```

Expects input with or without a trailing newline, and outputs the result as a byte value.

Try it online.

This checks each prefix to see whether it occurs later in the string, then chops off the first character and repeats the process until there are no more characters left.

The tape is divided into 3-cell nodes,

`c 0 f`

where `c` is a character of the given string, and `f` is a flag that can be either one, negative one, or zero. Nonzero flags are placed between the two characters currently being compared, and negative ones are reserved for the cells after the end of the current prefix and before the beginning of the current suffix (i.e., before the index of the current potential match).

The result is stored to the left of the string and is updated whenever a match is found.

(The string is actually processed in reverse with a `\x01` appended to it.)

# Answer
> 6 votes
# Jelly, 12 bytes

```
œ-QL€
ŒṖÇ€FṀ

```

Try it online!

### How it works

```
ŒṖÇ€FṀ  Main link. Argument: s (string)

ŒṖ      Generate all partitions of s.
  Ç€    Apply the helper link to each partition.
    F   Flatten the resulting array of lengths.
     Ṁ  Take the maximum.

œ-QL€   Helper link. Argument: P (partition)

  Q     Yield the elements of P, deduplicated.
œ-      Multiset subtraction; remove exactly one occurrence of each string in P.
   L€   Compute the lengths of the remaining strings.

```

# Answer
> 5 votes
# Retina, ~~35~~ ~~32~~ 30 bytes

Pretty cool challenge.

```
M&!`(.*)(?=.*\1)
M%`.
O#^`
G1`

```

**Try it online**

**Explanation:**

```
M&!`(.*)(?=.*\1)    # Prints overlapping greedy substrings occuring more than once
M%`.                # Replace each line with its length
O#^`                # Sort lines by number in reverse
G1`                 # Return the first line

```

# Answer
> 5 votes
# Perl 6, 36 bytes

```
{m:ex/(.*).*$0/.map(*[0].chars).max}

```

Try it

## Expanded:

```
{   # bare block lambda with implicit parameter ｢$_｣

  m           # match ( implicitly against ｢$_｣
  :exhaustive # every possible way
  /
    (.*)      # any number of characters ( stored in ｢$0｣ )
    .*
    $0
  /

  .map(

    *\        # the parameter to Whatever lambda
    [0]\      # the value that was in ｢$0｣ for that match
    .chars    # the number of characters

  ).max

}

```

# Answer
> 4 votes
## JavaScript (ES6), ~~79~~ ~~68~~ 66 bytes

```
f=(s,r,l=s.match(/(.*).*\1/)[1].length)=>s?f(s.slice(1),l<r?r:l):r
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

Edit: Saved ~~11~~ 13 bytes thanks to @Arnauld.

# Answer
> 4 votes
# Haskell, 79 bytes

```
(""%)
(a:b)!(c:d)|a==c=1+b!d
_!_=0
a%c@(e:d)=maximum[a!c,""%d,(a++[e])%d]
_%_=0

```

Try it online!

# Answer
> 3 votes
# Python 3, ~~75~~ 72 bytes

```
f=lambda s,n=0:s[n:]and max(n*(s[:n]in s[n:]),f(s,n+1))or n and f(s[1:])

```

Try it online!

# Answer
> 3 votes
# Husk, 11 bytes

```
L►L§fo↓2`xQ

```

Try it online!

Note: Husk is newer than this challenge.

## Explanation

```
L►L§fo↓2`xQ  Implicit input, say x = "ababc"
          Q  Nonempty substrings: ["a","b","ab",..,"ababc"]
    f        Keep those that satisfy this:
              Take s = "ab" as an example.
   §    `x    Split x along s: ["","","c"]
     o↓2      Drop the first two pieces: ["c"]
              This is truthy (i.e. nonempty).
             Result is ["a","b","ab","a","b","ab"]
 ►L          Take element with maximal length: "ab"
             If the list is empty, "" is used instead.
L            Length: 2

```

# Answer
> 2 votes
# JavaScript, 120

```
function r(a,b,m){return b=-~b,t=a.slice(0,b),n=a.indexOf(t,b),m=b>m&&!~n?m:b,a!=t&&r(a,b,m)||(a?r(a.slice(1),m,m):~-m)}

```

# Answer
> 2 votes
## Perl 5 with `-p`, 40 bytes

```
$_+=(sort map{y///c}/(?=(.+).*\1)/g)[-1]

```

Try it online!

# Answer
> 1 votes
# Mathematica, ~~75~~ 65 bytes

<sup>*10 bytes saved due to @JingHwan Min.*</sup>

```
Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&

```

Anonymous function. Takes a string as input, and returns a number as output.

# Answer
> 1 votes
# Pyth - 16 bytes

I need to golf the converting all the strings to lengths and finding the max.

```
eSlM+ksmft/dTd./

```

Test Suite.

# Answer
> 1 votes
**Clojure, 112 bytes**

```
#(apply max(for[R[(range(count %))]j R i R](let[[b e](split-at i(drop j %))](if((set(partition i 1 e))b)i 0)))))

```

loops twice over numbers `0` to `n - 1` (`n` being length of the string), drops `j` characters and splits the remainder into "beginning" and "end" parts. Creates a set of all substrings at `e` of length `b` and uses it as a function to check if `b` is found from there. Returns the length of `b` if found and 0 otherwise, returns the max of these values.

Would be interesting to see a shorter version.

# Answer
> 1 votes
# Retina, 24 bytes

```
L$v`(.*).*\1
$.1
N`
G-1`

```

Try it online!

A warmup for me to learn the new features of Retina 1.

### Explanation

```
L$v`(.*).*\1
$.1

```

A List stage, this returns all the matches for the regex `(.*).*\1`, wich matches any pattern of the form "ABA", where A and B are two arbitrary substrings (possibly empty). The additional options given to this stage are `v`, which considers overlapping matches, and `$` which applies a substitution to each of the matches before returning it: the substitution is indicated in the second line, and corresponds to the length (`.`) of the first capturing group (which would be the substring "A" in the previous example).

```
N`

```

We now have all the lengths of repeated substrings, this stage simply sorts them in numerical order, from the shortest to the longest.

```
G-1`

```

Finally, this grep stage (`G`) keeps only the last (`-1`) result, which is the length of the longest repeated substring.

# Answer
> 0 votes
## Javascript, 165 bytes

```
function a(s){var l=s.length/2,z=1,f='';while(z<=l){var t=s.substr(0,z),c=0;for(var i=0;i<s.length;i++){if(s.substr(i,z)===t){c++;if(c>1){f=t}}}z++}return f.length}

```

Test Cases

```
console.log(a('abcabcabcabc')) // Output 6
console.log(a('xyz'))          // Output 0
console.log(a('aaaaaaa'));     // Output 3
console.log(a('abcdefabc'));   // Output 3

```

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


# Question
Title: Order a list but respect integer ordering (natural sort order)
Given a list of *n* strings, return a list of that strings in ascending order. However, be aware, that in this case we want integer comparison for all numbers appearing in the strings, meaning that "12" \> "3".

Example cases:

```
{"abc123", "abc6", "abc47", "abd49"} -> {"abc6", "abc47", "abc123", "abd49"}
{"foo0", "bar12", "foobar12", "foo"} -> { "bar12", "foo", "foo0", "foobar12"}
{"Bond007", "Bond07", "Bond7", "Bond12"} -> {"Bond007", "Bond07", "Bond7", "Bond12"}
{"one1", "one11two23", "one1two2", "one1two3", "1"} -> {"1", "one1", "one1two2", "one1two3", "one11two23"}

```

You can expect to only find *\[a-zA-Z0-9\]+* in each string. This is so shortest code in bytes wins. Standard Loopholes are forbidden.

Update:
\- Sorting is case insensitive
\- The ascending order is *integers* \< "abcdefghijklmnopqrstuvwxyz"
\- Every sequence of integers as in the aforementioned order should be interpreted as one integer, meaning "421" represents 421, not 4, 2 and 1 and thus is smaller than "1341", as 421 \< 1341

-Treat numbers with leadings zeroes as though they were decimals meaning "001" -\> "0.01" so "001" \< "01" \< "1"

Thanks for Adám for pointing out, that this is called natural sort order.

# Answer
# 05AB1E, 7 bytes

```
ΣDþïs)}

```

Try it online!

# Explanation

```
ΣDþïs)}  Full Program
Σ     }  Sort by result of key: a
 D       a, a
  þ      digits_only(a), a
   ï     int(digits_only(a)), a
    s    a, int(digits_only(a))
     )   [a, int(digits_only(a))]

```
> 1 votes

# Answer
# Python 2, 68 bytes

```
lambda l:sorted(l,key=lambda x:int(re.sub("\D","",x)or 0))
import re

```

Try it online!

I used something like this to sort PDF files recently!

*my entry originally didn't work but Neil fixed it (thanks!)*
> 2 votes

# Answer
# Perl 6,  ~~32 31~~  30 bytes

```
*.sort(*.comb(/\d+|\D+/)».&val)

```

Test it

```
*.sort(*.comb(/\d+|\D/)».&val)

```

Test it

```
*.sort(*.comb(/\d+|./)».&val)

```

Test it

## Expanded:

```
*\                         # WhateverCode lambda (this is the parameter)

.sort(                     # sort by doing the following to each string

  *.comb( / \d+ | . / )\ # split the string into consecutive digits or a character

  ».&val                   # convert each to a Numeric if possible

)

```

Note:

```
"Bond007".comb(/\d+|\D+/)».&val
# results in
("Bond", IntStr.new(7, "007"))

# and

"Bond007".comb(/\d+|./)».&val
# results in
("B", "o", "n", "d", IntStr.new(7, "007"))

```
> 2 votes

# Answer
# APL (Dyalog Unicode) 17.0 (currently in alpha), 31 bytesSBCS

Anonymous tacit prefix function taking a list of strings as argument.

```
⊂⊃¨⍨∘⍋({0::⍵⋄⍎⍵}¨⊢⊂⍨1,2≠/∊∘⎕D)¨

```

As version 17.0 isn't on TIO yet, here is a test session transcript:

```
      f←⊂⊃¨⍨∘⍋({0::⍵⋄⍎⍵}¨⊢⊂⍨1,2≠/∊∘⎕D)¨
      ⎕JSON f ⎕JSON '["abc123", "abc6", "abc47", "abd49"]'
["abc6","abc47","abc123","abd49"]
      ⎕JSON f ⎕JSON '["foo0", "bar12", "foobar12", "foo"]'
["bar12","foo","foo0","foobar12"]
      ⎕JSON f ⎕JSON '["Bond007", "Bond07", "Bond7", "Bond12"]'
["Bond007","Bond07","Bond7","Bond12"]
      ⎕JSON f ⎕JSON '["one1", "one11two23", "one1two2", "one1two3", "1"]'
["1","one1","one1two2","one1two3","one11two23"]

```

---

from the entire argument…

`⊃¨⍨` pick each of the indices…

that are…

the ascending grade (indices which would place in ascending order) of…

`(` the following tacit function applied to each of the strings:

`∊∘⎕D` Boolean mask for the characters which are members of the set of **D**igits

`2≠/` pairwise inequality of that (i.e. indicate beginnings of letter runs and digit runs)

`1,` prepend 1 to mark the first character as beginning a run

`⊢⊂⍨` use that to partition (beginning partitions at 1s) the string

`{` apply the following anonymous lambda to each partition:

`0::` if any error happens, then:
return the argument as-is

try to:
`⍎⍵` evaluate the argument
> 2 votes

# Answer
# Python 3, 125 bytes

```
lambda a:[y for _,y in sorted([([i%2and int(e)or e for i,e in enumerate(re.findall("(\D+|\d+)",s))],s)for s in a])]
import re

```

Try it online!
> 1 votes

# Answer
# Python 3, 107 106 bytes

```
import re
lambda a:sorted(a,key=lambda x:[n.isdigit()and n.zfill(9)or n for n in re.findall('\d+|\D+',x)])

```

Try it online!

Abused the fact that Python compares two lists lexicographically. Unfortunately `re.split(r'\b',x)` does not work.
> 1 votes

# Answer
# Python 2, 92 bytes

```
lambda q:map(lambda a:a[1],sorted(map(lambda a:[int(re.sub("\D","",a)or 0),a],q)))
import re

```

Try it online!
> 1 votes

# Answer
# PHP 7, 17 bytes

```
<?php natsort()?>

```

natsort*"Sort an array using a 'natural order' algorithm"*
> 1 votes

---
Tags: code-golf
---


title: Create a folder

text:
# Question
Title: Create a folder
## Challenge

Given an input `x`, create a directory (AKA folder) in the file system with the name `x`.

Languages that are not able to create file system directories are excluded from this challenge.

The directory may be created anywhere, as long as the location is writable to the user running the program. Assume that the program is run as a non-privileged user on a modern Linux (or Windows if needed) desktop system.

### Clarifications

* Assume that the current directory is `$HOME`/`%USERPROFILE%`.
* Assume that no file or directory exists with the name given.
* Assume that the filename will only contain the characters `abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`.
* Assume that the filename will always be 8 characters long or shorter.

## Rules

* The directory must actually be created. You can't just say "I made it in /dev/null".
* Standard loopholes apply.
* This is .

# Answer
> 3 votes
# MATLAB/Octave, 6 bytes

```
@mkdir

```

Creates a function handle named `ans` to the built-in function `mkdir` which accepts the folder to be created as a string

```
ans('folder_to_create')
ans('/absolute/path/to/folder/to/create')

```

# Answer
> 2 votes
# Ruby, 11 + 1 = 12 bytes

+1 for `-n`

```
Dir.mkdir$_

```

Try it online!

# Answer
> 2 votes
# Julia 0.5, 5 bytes

```
mkdir

```

Try it online!

# Answer
> 2 votes
## Java, 33 31 bytes

-2 bytes thanks to @Phoenix - removing curly braces around lambda.

```
s->new java.io.File(s).mkdir();

```

In the form of a `Consumer<String>` where `s` is the name of the folder to create.

# Answer
> 1 votes
# Bash, 8 bytes

```
mkdir $1

```

Try it online!

# Answer
> 1 votes
# Python, 18 bytes

```
import os
os.mkdir

```

# Answer
> 1 votes
## Batch, 6 bytes

```
@md %*

```

~~Try it online!~~

# Answer
> 1 votes
# Go, 46 bytes

```
import."os"
func f(n string){Mkdir(n,ModeDir)}

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 14 bytes

```
Run["md "<>#]&

```

Try it online!

---

The trivial approach is longer. Surprise! (demonstrates that Mathematica is very verbose)

Works on Windows only, where `md` is the command to create a directory. See this answer or this answer.

---

Explanation:

```
Run["md "<>#]&   Anonymous function.

    "md "        String literal "md ". (with a trailing space to separate
                   the command and the parameter (directory name)
           #     The input.
         <>      `StringJoin` together.
Run[        ]    Runs as a command.

```

# Answer
> 0 votes
# Mathematica, 15 bytes

```
CreateDirectory

```

# Answer
> 0 votes
# C#, 35 bytes

```
System.IO.Directory.CreateDirectory

```

Does what it says on the tin.

# Answer
> 0 votes
# Batch, 2 bytes

```
md

```

`md` means **m**ake **d**irectory. Here it is in action:

```
C:\tmp>set f=md

C:\tmp>%f% foo

C:\tmp>dir f*.*
 Volume in drive C is OS
 Volume Serial Number is 6CC3-3025

 Directory of C:\tmp

02-Feb-18  09:56    <DIR>          foo
               0 File(s)              0 bytes
               1 Dir(s)  378,122,883,072 bytes free

```

# Answer
> 0 votes
# APL (Dyalog Unicode), 6 bytes

Prefix function.

```
⎕MKDIR

```

Try it online!

# Answer
> -2 votes
# tcl, don't know how to count

My count could be:

* 13, if everything on `file mkdir $x` is accounted.
* 12, if `file mkdir $`as how I have seen in some answers `x` is not taken into account
* 11, because in tcl whenever you use the value of `x` , you type `$x`, so only `file mkdir`  is taken into account
* 10, if is `file mkdir` by removing the trailing space from previous.

Source:

```
file mkdir $x

```

demo — Please reserve it for question asker. Look at files tree at the left where there is only `root` and `main.tcl` . Click the `Execute` button, it will run a script command on the green area; In the top of the files tree there is a `Refresh` button symbolized by an icon, click it and see `folder1` and `folder2` appearing.

---
Tags: code-golf, file-system
---


title: Flatten a Stack Cats program

text:
# Question
Title: Flatten a Stack Cats program
Stack Cats is a reversible, stack-based language. Its reversible nature makes for somewhat weird loops. This challenge is about the conditional loop `(...)`. When these loops are nested in certain ways, it's possible to transform the code to reduce the nesting depth. Here are the rules (where `A` and `B` stand for an arbitrary snippets):

1. When one loop starts with another loop, we can extract the inner loop to the front: `((A)B)` becomes `(A)(B)`.
2. When one loop ends with another loop, we can extract the inner loop to the end: `(B(A))` becomes `(B)(A)`.
3. Empty loops, `()`, can be removed from the program entirely. As a corollary (in conjunction with the other rules), `((A))` is equivalent to `(A)`.

The only nested loops that will remain are of the form `(A(B)C)`, where `A`, `B` and `C` are non-empty.

## The Challenge

You're given a valid Stack Cats program and your task is to reduce the nesting level of loops as much as possible, leaving no empty loops, using the above transformations.

A valid Stack Cats program...

* ... consists only of the characters `()/\<>[]{}!"*+-:=ITX^_|`.
* ... has mirror symmetry (e.g. `\(]{}!{}[)/` is a valid program, but `/|/` isn't).
* ... has correctly matched and nested `()` and `{}` (`[]`, `<>` and `\/` don't necessarily need to be matched as usual, although they'll appear in pairs due to the mirror symmetry requirement).

You can take either a string or a list of characters as input, but output needs to be presented in the same format.

You may write a program or a function and use any of our standard methods of receiving input and providing output. Note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in *bytes* – wins.

## Test Cases

Test cases are two lines each (input and output), separated by empty lines. Note that one output is empty. You also need to support the empty input (which should result in empty output).

```
(((=+|+=)))
(=+|+=)

({(=+|+=)})
({(=+|+=)})

((\)/)I(\(/))
(\)(/)I(\)(/)

(()()(())()())

((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)

```

# Answer
# Retina 0.8.2, ~~113~~ ~~107~~ ~~67~~ 66 bytes

```
+`\(\)|(\()?(\(((\()|(?<-4>\))|[^()])*(?(4)@)\))(?(1)|(\)))
$5$2$1

```

Try it online! Includes ~~3~~ 4 byte saving thanks to @MartinEnder. Explanation:

```
+`

```

Repeatedly apply the substitution until there are no matches.

```
\(\)|

```

Match an empty loop (in which case nothing is captured so the substitution simply deletes it) or:

```
(\()?

```

Optionally match a `(`. This is captured in group 1 if it matched, but not if it didn't.

```
(\(

```

Capture the main body of the match in group 2 and match a `(`.

```
(
 (\()
|
 (<-4>\))
|
 [^()]
)*

```

Repeatedly match either a `(`, capturing it in group 4, or a `)`, removing a capture from group 4 (failing if there isn't one), or something else.

```
(?(4)@)

```

Ensure that there are no spare captures left in group 4.

```
\))

```

End capture group 2 with another `)`.

```
(?(1)|(\)))

```

If capture group 1 was empty, then capture a `)` in capture group 5. (So exactly one of those two groups will have a capture).

```
$5$2$1

```

Move the bracket captured in either group 1 or group 5 to the other side of group 2. This has the effect of moving the inner loop to the front or the end of the outer loop depending on which side it matched.
> 6 votes

# Answer
# Stax v1.0.3+, ~~76~~ ~~65~~ ~~64~~ ~~62~~ 58 bytesCP437

```
îÜ•$o,Γ{í]Üf╒9♦╛üΣóç*\$ñ₧└ΦJ♠¥c╥jóu≥3E.╘ⁿ◄◘W₧<¶┼7úê╟┴zç↨aG

```

70 bytes when unpacked,

```
{{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Md}X!:Rx!:Rc.()z:rgp

```

Run and debug online!

## Explanation

`{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Md` is a block that separates `A((B)C)D` into four parts and convert it to `A(B)(C)D`.

`X!:Rx!:R` executes the block on the input string (step 1), then **reflects** the string (string reflection in Stax refers to reversing the string plus replacing (translating) `(<[{/` with (to) `\}]>)` ) and execute the block on the string obtained, and then reflect it back (step 2). Step 2 is essentially converting `(A(B))` to `(A)(B)`.

`c.()z:r` remove all empty loops (step 3).

`gp` is a generator that finds the fix point of an iteration. In this case the string is iterated with the 3-step process until it no longer changes.

Implicit output.
> 2 votes

# Answer
# Python 3, 226 223 212 206 bytes

Okay, here is an attempt to solve this in a language that doesn't support recursive regex.

```
lambda s:g(g(s,*'()'),*')(').replace('()','')
def g(s,t,u):
 m,*a={},;i=v=0
 for c in s:
  i+=1;a+=[i]*(c==t)
  if c==u:*a,x=a;m[x]=i;v=m.get(x+1)
  if v:return g(s[:x]+s[x+1:v]+t+s[v:],t,u)
 return s[::-1]

```

Try it online!

**Edits:**

* Refactored `[::-1]` to save 6 bytes, thanks to Mr.Xcoder.

The `g` function is the basic building block, which finds an occurrence of `((A)B)`, changes it to `(A)(B)`, then applies itself to the result until no more transformation is possible.

The main steps are:

* Apply `g` to the input normally.
* Apply `g` to the input flipped. This run finds the occurrence of `))A(B(` in the reversed input, which effectively handles `(A(B))`.
* Remove any occurrence of `()`.

The problem is, `g` has so bad control structure that trying to one-line it made it bloat badly, so I don't think major improvement is possible based on this solution.
> 2 votes

---
Tags: code-golf, balanced-string, syntax
---


title: Screenshot Tiler

text:
# Question
Title: Screenshot Tiler
# Introduction

Given a set of text-based "screenshots" consisting of printable ASCII chars merge them so that all of them form one long screenshot so that nobody has to do it themselves when reading it.

# Challenge

Take input as a list of strings (referred to as "screenshots"). Each screenshot consists of several lines of text.

To merge two screenshots:

1. Starting from the first line, check if that line occurs in the second screenshot

* If it does, cut the first screenshot so it ends at this duplicated line and cut the second screenshot so it begins one line after the duplicated line
    * Concatenate these two together with the cuts
2. If they do not have a line of text in common, just append the second screenshot to the first (starting on a new line).

Your output should be a single string merging all of the screenshots together. Screenshot merging is not associative, so you should merge in the following order: merge the first and the second screenshot, then the resulting screenshot with the third, then the result with the fourth screenshot, and so on, until only one screenshot is left.

### Example with explanation

Input:

Screenshot 1:

```
> hi
      hi <
> how are you doing
    good <

```

Screenshot 2:

```
      hi <
> how are you doing
    good <
> good
     yes <

```

Output:

```
> hi
      hi <
> how are you doing
    good <
> good
     yes <

```

Explanation:

Going from top to bottom, find the first line on both the first and second screenshot

```
> how are you doing

```

Take the first half of this screenshot above and including the line

```
> hi
      hi <
> how are you doing
--remove everything below--

```

Find the first line where it is duplicated in the next screenshot and cut one below there

```
--remove everything including and above--
    good <
> good
     yes <

```

Concatenate the two sections

```
> hi
      hi <
> how are you doing
--join them together--
    good <
> good
     yes <

```

# Test Cases

Input:

```
line 1
line 2
line 3

line 2
line 3
line 4

```

Output:

```
line 1
line 2
line 3
line 4

```

Input:

```
line 1
line 2
line 10

line 10
line 2
line 3

```

Output:

```
line 1
line 2
line 3

```

> Note that even though line 10 is duplicated, line 2 is duplicated first and split there.

Input:

```
words
really long repeated words
456

hi
really long repeated words
hmm
really long repeated words
kthxbye

```

Output:

```
words
really long repeated words
hmm
really long repeated words
kthxbye

```

> Note that `really long repeated words` appears twice in the result because the one in the first screenshot and the other in the second screenshot is included

Input:

```
======= 10:42 ========
~~~ p1: hi
            hi :p2 ~~~
~~~ p1: yes
            no :p2 ~~~
v     -----------    v

======= 10:43 ========
            no :p2 ~~~
~~~ p1: why?
       because :p2 ~~~
~~~ p1: ok fine
v     -----------    v

======= 10:44 ========
       because :p2 ~~~
~~~ p1: ok fine
~~~                ~~~
~~~                ~~~
v     -----------    v

```

Output:

```
======= 10:42 ========
~~~ p1: hi
            hi :p2 ~~~
~~~ p1: yes
            no :p2 ~~~
~~~ p1: why?
       because :p2 ~~~
~~~ p1: ok fine
~~~                ~~~
~~~                ~~~
v     -----------    v

```

> Note that the clock increases in time meaning that the clock is not the first duplicated input. Because it is before the first duplicated input, it gets ignored the second and third time.

### Edge Case Input:

```
> hello
   oh hi <

> how are you doing
    good <

```

Output:

```
> hello
   oh hi <
> how are you doing
    good <

```

> Note that nothing is duplicated here so just append them together

As this is , smallest submission in bytes wins.

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

Takes input as a list of lists of lines, outputs a list of lines.

```
s=>s.reduce((a,b)=>(i=a.findIndex(x=>(j=b.indexOf(x))>=0))<0?a.concat(b):a.slice(0,i+1).concat(b.slice(j+1)),[])

```

```
const f =
s=>s.reduce((a,b)=>(i=a.findIndex(x=>(j=b.indexOf(x))>=0))<0?a.concat(b):a.slice(0,i+1).concat(b.slice(j+1)),[])
;
const tests = [
[`line 1
line 2
line 3`,
`line 2
line 3
line 4`],
[`line 1
line 2
line 10`,
`line 2
line 10
line 3`],
[`words
really long repeated words
456`,
`hi
really long repeated words
hmm
really long repeated words
kthxbye`],
[`======= 10:42 ========
~~~ p1: hi
            hi :p2 ~~~
~~~ p1: yes
            no :p2 ~~~
v     -----------    v`,
`======= 10:43 ========
            no :p2 ~~~
~~~ p1: why?
       because :p2 ~~~
~~~ p1: ok fine
v     -----------    v`,
`======= 10:44 ========
       because :p2 ~~~
~~~ p1: ok fine
~~~                ~~~
~~~                ~~~
v     -----------    v`],
[`> hello
   oh hi <`,
`> how are you doing
    good <`]
];

for(let test of tests) {
  console.log('Input:', test=test.map(x=>x.split('\n')));
  console.log('Output:', f(test));
}
```

# Answer
> 2 votes
# Jelly, 29 bytes

```
Ỵ€ð¹Ƥp¹ÐƤ}Ṛ⁼"¥Ḣ¥/ÐfḢṖ;¥/ȯ;µ/Y

```

Try it online!

# Answer
> 2 votes
# Python 2, 124 bytes

```
def f(S):
 x=[]
 for y in S:
	y=y.split('\n');x+=y;i=0
	while(x[i]in y)<1:i+=1
	x=x[:i]+y[y.index(x[i]):]
 print'\n'.join(x)

```

Try it online!

---
Tags: code-golf, ascii-art
---


title: Turn Your Program into a Snake!

text:
# Question
Title: Turn Your Program into a Snake!
...or "snakes but not too long".

Inspired by this challenge and this comment.

## Task

Write a program or a function that takes no input and outputs its own source code formatted as a snake according to the rules below:

1. If your code has any whitespace, it will not be output; it will just be skipped.
2. There will be one character on each column in the output.
3. The first character in the code is placed on the first column of line **x**.
4. The second character is placed on the second column of either line **x**, **x-1**, or **x+1**. More generally, the **n**th character (excluding whitespace) goes to the **n**th column on a line that is one above, one below, or the same as the line on which the previous character went.
5. The character on the highest line will be on the first line in the output; that is, there are no extraneous leading lines. A single, empty trailing line is allowed.

For example, if the code was `from python import snake`, the output should look like:

```
      th
     y  o       s  ke
f  mp    ni po t na
 ro        m  r

```

or

```
                    e
                   k
f                 a
 r               n
  om    o im    s
    p  h n  po t
     yt       r

```

All valid forms of snake should have a nonzero probability of occurring. Your program's source code should contain at least two non-whitespace characters.

This is , so the shortest answer in bytes wins.

# Answer
> 4 votes
# 05AB1E, 47 bytes

```
4"D34çýSDεXD<X>ŸΩU}W-úζ»"D34çýSDεXD<X>ŸΩU}W-úζ»

```

Try it online!

---
Tags: code-golf, ascii-art, random, quine
---


title: #Hashtag_or_not

text:
# Question
Title: #Hashtag_or_not
In this code golf challenge, you will verify hashtags!

# #What\_your\_code\_should\_do

Input is a string. Output a truthy value if it is a valid hashtag, and a falsy value otherwise.

We define a string as a valid Hashtag if ...

* It starts with a hash (`#`).
* It doesn't have a number right after the hashtag (e.g. `#2016USElection` isn't a valid hashtag).
* It doesn't have any "special characters" (i.e. any character that isn't an alphabet, underscore (`_`) or a number).

You can assume that the input only contains ASCII characters. (It would be unfair if we did Unicode too.)

# #Rules

Basic rules apply.

# #Examples

Truthy:

```
#
#e
#_ABC
#thisisanunexpectedlylongstringxoxoxoxo
#USElection2016

```

Falsy:

```
Hello, World!
#12thBday
#not-valid
#alsoNotValid!
#!not_a_hash

```

# Answer
## Retina, 12 bytes

```
^#(?!\d)\w*$

```

Prints `1` for hashtags and `0` otherwise.

Try it online! (The first line enables a linefeed-separated test suite.)

Not much to explain here, this is quite a literal implementation of the definition: `^` and `$` are just anchors ensuring that the match covers the entire string, `#` checks that the string starts with a `#`, `(?!\d)` ensures that the next character *isn't* a digit (without advancing the regex engine's position), `\w*` checks that we can reach the end of the string with zero or more letters, digits or underscores.

By default, Retina counts the number of matches of the given regex, which is why this gives `1` for valid hash tags and `0` otherwise.
> 19 votes

# Answer
## Perl, 22 bytes

**21 bytes code +1 for `-p`**

```
$_=/^#([a-z_]\w*)?$/i

```

Prints 1 if it's a valid hashtag, empty string otherwise.

### Usage

```
perl -pe '$_=/^#([a-z_]\w*)?$/i' <<< '#'
1
perl -pe '$_=/^#([a-z_]\w*)?$/i' <<< '#_test'
1
perl -pe '$_=/^#([a-z_]\w*)?$/i' <<< '#1test'

```

Saved 2 bytes thanks for Martin Ender (and another 4 using his lookaround method)

---

## Perl, 18 bytes

**17 bytes code +1 for `-p`**

Using Martin's lookaround this can be much shorter!

```
$_=/^#(?!\d)\w*$/

```
> 6 votes

# Answer
# JavaScript (ES6), 25 bytes

```
s=>/^#(?!\d)\w*$/.test(s)

```

```
F = s => /^#(?!\d)\w*$/.test(s)
input.oninput = () => result.innerHTML = input.value ? F(input.value) ? '\ud83d\udc8e' : '\ud83d\udca9' : '\ud83d\udcad';
```

```
#input, #result {
  vertical-align: middle;
  display: inline-block;
}
#input {
  line-height: 2em;
}
#result {
    font-size: 2em;
}
```

```
<input id="input" type="text"/> <span id="result">&#x1f4ad</span>
```
> 6 votes

# Answer
# C, 80 bytes

Function `f()` takes the string as an argument and modifies `int *b` to either 1 or 0 to indicate truthy/falsy.

```
f(char*p,int*b){for(*b=(*p==35)&&!isdigit(p[1]);*p;++p)*b&=isalnum(*p)||*p==95;}

```

If the string always has at least one character (i.e. never an empty string), a byte can be shaved off for 79 bytes:

```
f(char*p,int*b){for(*b=(*p==35)&&!isdigit(p[1]);*++p;)*b&=isalnum(*p)||*p==95;}

```
> 5 votes

# Answer
# Python 3, 41 bytes

```
import re
re.compile('#(?!\d)\w*$').match

```
> 5 votes

# Answer
# Brachylog, 55 bytes

```
"#"|h"#",?b@lL'(eE,@A:"1234567890":"_"c'eE),@A:"_"ce~hL

```

This uses no regex.

### Explanation

```
Main predicate, Input (?) is a string

  "#"                           ? = "#"
|                             Or
  h"#",                         First character of ? is "#"
  ?b@lL                         L is the rest of the chars of ? lowercased
  '(                            It is not possible for any char of L that...
    eE,                           Call this char E
    @A:"1234567890":"_"c          Concatenate the lowercase alphabet with the digits and "_"
    'eE                           E is not a member of that concatenated string
   ),
   @A:"_"c                      Concatenate the lowercase alphabet with "_"
   e~hL                         One char of that concatenated string is the first char of L

```
> 4 votes

# Answer
## Python 3, ~~103~~ 93 bytes

```
all((c=='_'or c.isalpha()*i>0)^(i<1and'#'==c)^(c.isdigit()*i>1)for i,c in enumerate(input()))

```

The `#` being `True` killed me here, I had to enumerate the string to avoid an index error on the single character input.
> 4 votes

# Answer
## PowerShell v2+, 25 bytes

```
$args-match'^#(?!\d)\w*$'

```

Using Martin's regex, just wrapped up in PowerShell's `-match` operator coupled with the input `$args`. For truthy/falsey values, this will return the string itself on a match (a truthy value) or nothing on a non-match (a falsey value). This is because when a comparison operator is applied against an array, it returns anything that satisfies that operator.

A couple examples (wrapped in a `[bool]` cast to make the output more clear):

```
PS C:\Tools\Scripts\golfing> [bool](.\hashtag-or-not.ps1 '#2016Election')
False

PS C:\Tools\Scripts\golfing> [bool](.\hashtag-or-not.ps1 'Hello, World!')
False

PS C:\Tools\Scripts\golfing> [bool](.\hashtag-or-not.ps1 '#')
True

PS C:\Tools\Scripts\golfing> [bool](.\hashtag-or-not.ps1 '')
False

PS C:\Tools\Scripts\golfing> [bool](.\hashtag-or-not.ps1 '#USElection2016')
True

```
> 4 votes

# Answer
# Mathematica, ~~52~~ ~~46~~ 43 bytes

Saved ~~6~~ 9 bytes due to @MartinEnder.

```
StringMatchQ@RegularExpression@"#(?!\d)\w*"

```

Function. Takes a string as input, and returns `True` or `False` as output. Pretty simple, just matches against the regex `/#(?!\d)\w*/`.
> 3 votes

# Answer
## Python3 - 156 128 bytes

```
lambda n:n=="#"or(n[0]=="#")*all(any([47<ord(c)<58,64<ord(c)<91,ord(c)==95,96<ord(c)<123])for c in n[1:]+"0")*~(47<ord(n[1])<58)

```

A solution that doesn't use regex. 0 is falsey and every other value is truthy.

Thanks to @LeakyNun for saving bytes!
> 3 votes

# Answer
# Dyalog APL, ~~22~~ 20 bytes

Without RegEx:

```
{0≤⎕NC 1↓⍵,⎕A}∧'#'=⊃

```

-2 thanks to ngn
> 3 votes

# Answer
# Octave, ~~37~~ ~~56~~ ~~54~~ 43 bytes

Thanks to @LuisMendo for removing 8 bytes!

```
@(s)s(1)==35&(isvarname(s(2:end))|nnz(s)<2)

```

Not very golfy, but very built-inny.
Edit: The original code accepted strings with no leading '#'. I guess I should have stuck with regex.

Test suite on ideone.
> 3 votes

# Answer
# Python 2, 79 bytes

```
lambda x:x=='#'or(1>x[1].isdigit())&x[1:].replace('_','').isalnum()&('#'==x[0])

```

First golfing attempt. Ungolfed version:

```
def f(x):
    if x == '#':
        return True
    else:
        return x[0]=='#' and x[1:].replace('_','').isalnum() and not x[1].isdigit()

```
> 3 votes

# Answer
# Lua, ~~59~~ ~~55~~ 54 bytes

## Code

```
s=arg[1]print(load(s:sub(2).."=0")and s:sub(1,1)=="#")

```

## How it works:

1. Check if the rest of the characters can be a valud Lua identifier (identifiers in Lua follow the same rules as hashtags.)
2. Check if the first character is a `#`.

Takes input from the command line. Prints `true` if the string is a valid hashtag, otherwise, it prints `nil`.
> 2 votes

# Answer
# Google Sheets, 30 bytes

An anonymous worksheet function that takes input from the cell `A1` checks it against the RE2 expression and outputs the result to the calling cell.

```
=RegexMatch(A1,"^#([a-z_]\w*)?

```
> 2 votes

# Answer
# 05AB1E, 18 bytes

Code:

```
¬'#Qs¦A«¬d_sDžjKQP

```

Uses the **CP-1252** encoding. Try it online!.
> 1 votes

# Answer
# Standard ML, ~~121~~ ~~118~~ 107 bytes

```
(fn#"#"::a=>(fn x::r=>x> #"@"andalso List.all(fn#"_"=>1=1|c=>Char.isAlphaNum c)a|e=>1=1)a|e=>1=0)o explode;

```

Try it online! Functional solution without using regex. Declares an anonymous function which is bond to the implicit result identifier `it`.

```
> val it = fn : string -> bool
- it "#valid_hash";
> val it = true : bool

```
> 1 votes

# Answer
## Pyke, 19 bytes

```
\#.^It,!It\_D-PRkq|

```

Try it here!

Quick fix for tonight
> 1 votes

# Answer
# Python 3, 97 Bytes 70 Bytes 56 Bytes

```
lambda x:s=x[2:];b=x[1];all(x!="#",[x[0]=="#",any[b.isalpha(),"_"in b],any[s.isalnum(),"_"in s]])

```

(Code changed) Human readable

```
x=input()
if x[0]=="#" and x[1].isalpha() and str(x)[2:].isalnum():
    print(True)
else:
    print(False)

```
> 1 votes

# Answer
# GNU grep, 15 + 2 = 17 bytes

```
grep -Ei '^#([a-z_]\w*)?$'

```

### Test:

```
$ echo '#
#e
#_ABC
#thisisanunexpectedlylongstringxoxoxoxo
#USElection2016
Hello, World!
#12thBday
#not-valid
#alsoNotValid!' | grep -Ei '^#([a-z_][a-z0-9_]*)?$'

```

Output:

```
#
#e
#_ABC
#thisisanunexpectedlylongstringxoxoxoxo
#USElection2016

```
> 1 votes

# Answer
# Sed 19 + 2 = 21 bytes

```
/^#([a-z_]\w*)?$/Ip

```

This filters out all non-hashtags and outputs valid hashtags.

Run as `sed -rn "/^#$|^#[a-z]\w*$/Ip"`. Quit with `Ctrl` \+ `D` (send EOF).
> 1 votes

# Answer
# Ruby, 16 + ~~3~~ 1 (`n` flag) = ~~19~~ 17 bytes

Uses `0` as truthy and `nil` as falsy.

```
p~/^#(?!\d)\w*$/

```

Run it as `ruby -ne 'p~/^#(?!\d)\w*$/'`. Thanks to @manatwork for fixing the bash error when running the program.
> 1 votes

# Answer
# Excel VBA, 54 bytes

Anonymous VBE immediate window function that takes input from cell `[A1]`, checks if the value of the cell matches the `Like` pattern, and outputs as `Boolean` to the VBE immediate window

```
?Not[Left(A1,2)]Like"[#]#"And[A1]Like"[#][_a-zA-z0-9]*

```
> 1 votes

# Answer
# Haskell, 79 bytes

```
import Data.Char
f(a:r)=a=='#'&&r==""||r!!0>'@'&&all(\c->c=='_'||isAlphaNum c)r

```

Try it online!
> 1 votes

# Answer
# Java 8, ~~57~~ ~~54~~ 28 bytes

```
s->s.matches("#(?!\\d)\\w*")

```

Port of Martin Ender's Retina answer to save a few bytes and match added test cases.
Not that `String#matches` always matches the entire String, so no need for `^...$`.

Try it here.
> 0 votes

# Answer
# C#, 92 bytes

```
s=>s[0]=='#'&s.Length>1&&(s[1]<48|s[1]>57)&s.Skip(1).All(x=>char.IsLetterOrDigit(x)|x=='_');

```

C# lambda (`Predicate`) where input is a `string` and output is a `bool`.

Try it online!
> 0 votes

# Answer
## Lua, 39 bytes

```
print(arg[1]:match("^#[%a_][%a_%d]*$"))

```

Straightforward copypasta of match description. Outputs falsy `nil` if not hashtag, outputs truthly hashtag back otherwise.

Can be shortened for one more byte by using `find` if outputing list of two values (which is truthly) doesn't break rules.
> 0 votes

# Answer
## Clojure, ~~130~~ ~~135~~ 132 bytes

* +5 bytes to deal with an NPE that happened when the string consisted of only a hashtag.
* -2 bytes by using `Character/isLetterOrDigit`.

```
(fn[s](let[[h & r]s n(map int r)](and(= h\#)(not(<= 48(or(first n)0)57))(every? #(or(Character/isLetterOrDigit^long %)(= 95 %))n))))

```

Ungolfed:

```
(defn hashtag? [s]
  (let [[h & r] s
        codes (map int r)]
    (and (= h \#)
         (not (<= 48 (or (first codes) 0) 57))
         (every?
           #(or (Character/isLetterOrDigit ^long %)
                (= 95 %))
           codes))))

```
> 0 votes

---
Tags: code-golf, string, decision-problem
---


title: Write a Palindrome-Polyglot-Quine

text:
# Question
Title: Write a Palindrome-Polyglot-Quine
Write a "palipolyquine": a program that is a quine, a polyglot, and a palindrome.

Rules:

* The number of polyglot languages is more preferable than code size.
* The shortest answer (in bytes) wins, in case of a tie.
* Polyglot and Quine rules see here: Write a Polyquine.

My example (I have a repository Freaky-Sources with tests):

## C#/Java (1747 bytes):

```
/**///\u000A\u002F\u002A
using System;//\u002A\u002F
class Program{public static void//\u000A\u002F\u002A
Main//\u002A\u002Fmain
(String[]z){String s="`**?`@#_^using System;?_#^class Program{public static void?@#_^Main?_#main^(String[]z){String s=!$!,t=s;int i;int[]a=new int[]{33,94,38,64,35,95,96,63,36};String[]b=new String[]{!&!!,!&n!,!&&!,!&@!,!&#!,!&_!,!`!,!?!,s};for(i=0;i<9;i++)t=t.?@#_^Replace?_#replace^(!!+(char)a[i],b[i]);t+='*';for(i=872;i>=0;i--)t=t+t?@#_^[i];Console.Write?_#.charAt(i);System.out.printf^(t);}}/",t=s;int i;int[]a=new int[]{33,94,38,64,35,95,96,63,36};String[]b=new String[]{"\"","\n","\\","\\u000A","\\u002F","\\u002A","/","//",s};for(i=0;i<9;i++)t=t.//\u000A\u002F\u002A
Replace//\u002A\u002Freplace
(""+(char)a[i],b[i]);t+='*';for(i=872;i>=0;i--)t=t+t//\u000A\u002F\u002A
[i];Console.Write//\u002A\u002F.charAt(i);System.out.printf
(t);}}/*/}};)t(
ftnirp.tuo.metsyS;)i(tArahc.F200u\A200u\//etirW.elosnoC;]i[
A200u\F200u\A000u\//t+t=t)--i;0=>i;278=i(rof;'*'=+t;)]i[b,]i[a)rahc(+""(
ecalperF200u\A200u\//ecalpeR
A200u\F200u\A000u\//.t=t)++i;9<i;0=i(rof;}s,"//","/","A200u\\","F200u\\","A000u\\","\\","n\",""\"{][gnirtS wen=b][gnirtS;}63,36,69,59,53,46,83,49,33{][tni wen=a][tni;i tni;s=t,"/}};)t(^ftnirp.tuo.metsyS;)i(tArahc.#_?etirW.elosnoC;]i[^_#@?t+t=t)--i;0=>i;278=i(rof;'*'=+t;)]i[b,]i[a)rahc(+!!(^ecalper#_?ecalpeR^_#@?.t=t)++i;9<i;0=i(rof;}s,!?!,!`!,!_&!,!#&!,!@&!,!&&!,!n&!,!!&!{][gnirtS wen=b][gnirtS;}63,36,69,59,53,46,83,49,33{][tni wen=a][tni;i tni;s=t,!$!=s gnirtS{)z][gnirtS(^niam#_?niaM^_#@?diov citats cilbup{margorP ssalc^#_?;metsyS gnisu^_#@`?**`"=s gnirtS{)z][gnirtS(
niamF200u\A200u\//niaM
A200u\F200u\A000u\//diov citats cilbup{margorP ssalc
F200u\A200u\//;metsyS gnisu
A200u\F200u\A000u\///**/

```

Compilation available on ideone.com: C#, Java.

# Answer
> 15 votes
## CJam/GolfScript, 2 languages, 50 bytes

```
{`"0$~e#"+0$-1%"":n}0$~e##e~$0}n:""%1-$0+"#e~$0"`{

```

Try it CJam! Try it in GolfScript!

Huh, this went unanswered surprisingly long.

### Explanation

It's probably easiest to explain this by showing how I turned the basic quine in each language into a palindromic polyglot quine.

So the basic quines in both languages are:

```
{".~"}.~

```

```
{"_~"}_~

```

In GolfScript and CJam, respectively. These are quite similar thanks to the fact that CJam was originally inspired by GolfScript (but has since deviated quite a lot). The first difference we notice is that one uses `.` for duplicating the top of the stack and the other uses `_`. A common trick to avoid this problem is to use `0$`, since both languages have the "copy-nth-item-on-stack" operator `$`. So we get `{"0$~"}0$~`, although that still needs a trailing linefeed in GolfScript. But let's worry about that at the end.

First, we need to make it a palindrome. The obvious solution to this is to append a comment and put the source code there in reverse. This is quite simple, because CJam uses `e#` for comments, and in GolfScript `e` does nothing at all, and `#` is a comment. So if we append `e#...` that works for both languages. Here is what we've got:

```
{"0$~"}0$~e##e~$0}"~$0"{

```

Of course, that doesn't actually *print* the part from `e#` onward. We can reconstruct this quite easily from the source code itself. Both languages can turn the initial block into a string with ``` and append the `"0$~"` part with `+`, so that we get the entire unmirrored source code in a single string. To append a mirrored copy, all we need to do is duplicate the string with `0$` again and then reverse it with `-1%`, which also works in both languages. So now we've got this:

```
{`"0$~e#"+0$-1%}0$~e##e~$0}%1-$0+"#e~$0"`{

```

This is a valid palindromic quine in CJam, and it also works in GolfScript but still prints that pesky trailing linefeed.

The usual way to prevent this is to assign an empty string to `n`, because what GolfScript really does is print the contents of `n` at the end. So what we need is `"":n`. So what about CJam? Thankfully, this does nothing at all. `""` is also an empty string (or empty list, they're the same thing in CJam), and `:` maps the operator `n` (print with linefeed) over the list. But since the list is empty, mapping an operator over it does nothing at all. Hence, we can get rid of the linefeed, without messing with CJam, and end up with the final solution:

```
{`"0$~e#"+0$-1%"":n}0$~e##e~$0}n:""%1-$0+"#e~$0"`{

```

# Answer
> 7 votes
# Perl 5/Ruby/PHP/JavaScript (Browser), 4 languages, 513 bytes

```
$_='$z=0?"$&".next: eval("printf=console.log;atob`JCc`");printf("%s_=%s%s%s;eval(%s_);//#//;)_%s(lave;%s%s%s=_%s",$d=$z[0]||h^L,$q=$z[1]||h^O,$_,$q,$d,$d,$q,"0"?$_.split("").reverse().join(""):~~reverse,$q,$d)';eval($_);//#//;)_$(lave;')d$,q$,esrever~~:)""(nioj.)(esrever.)""(tilps._$?"0",q$,d$,d$,q$,_$,O^h||]1[z$=q$,L^h||]0[z$=d$,"s%_=s%s%s%;eval(s%_);//#//;)_s%(lave;s%s%s%=_s%"(ftnirp;)"`cCJ`bota;gol.elosnoc=ftnirp"(lave :txen."&$"?0=z$'=_$

```

Try the Perl online!
Try it online!
Try the PHP online!
Validate it online!

```
$_='$z=0?"$&".next: eval("printf=console.log;atob`JCc`");printf("%s_=%s%s%s;eval(%s_);//#//;)_%s(lave;%s%s%s=_%s",$d=$z[0]||h^L,$q=$z[1]||h^O,$_,$q,$d,$d,$q,"0"?$_.split("").reverse().join(""):~~reverse,$q,$d)';eval($_);//#//;)_$(lave;')d$,q$,esrever~~:)""(nioj.)(esrever.)""(tilps._$?"0",q$,d$,d$,q$,_$,O^h||]1[z$=q$,L^h||]0[z$=d$,"s%_=s%s%s%;eval(s%_);//#//;)_s%(lave;s%s%s%=_s%"(ftnirp;)"`cCJ`bota;gol.elosnoc=ftnirp"(lave :txen."&$"?0=z$'=_$
```

---
Tags: code-challenge, quine, palindrome, polyglot
---