title: Compute the Carmichael function

text:
# Question
Title: Compute the Carmichael function
## Task description

In number theory, the Carmichael function ***λ*** takes a positive integer **n** and returns the least positive integer **k** so that the **k**-th power of each integer coprime to **n** equals 1 modulo **n**.

Given a positive integer **n**, your solution must compute ***λ*(n)**. The shortest code in bytes wins.

Your program should theoretically work for arbitrarily large inputs, but doesn’t need to be efficient.

## Tips

The sequence of all ***λ*(n)** is OEIS A002322.

An ungolfed Python implementation would look like

```
from fractions import gcd

def carmichael(n):
    coprimes = [x for x in range(1, n) if gcd(x, n) == 1]
    k = 1
    while not all(pow(x, k, n) == 1 for x in coprimes):
        k += 1
    return k

```

(In Python, `pow(A, B, C)` efficiently computes `pow(A, B) % C`.)

## Test cases

```
Input    Output
1        1
2        1
3        2
10       4
35       12
101      100
530      52
3010     84
6511     3056
10000    500

```

# Answer
## Mathematica, 16 bytes

```
CarmichaelLambda

```

Well...
> 49 votes

# Answer
# Python, ~~76~~ ~~73~~ 67 bytes

```
f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)

```

Try it online!

A further byte could be saved by returning *True* instead of **1**.

### Alternative implementation

Using the same approach, there is also the following implementation by @feersum which doesn't use list comprehensions.

```
f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<1)*f(n,k,a+1)or-~f(n,k+1)

```

Note that this implementation requires **O(nλ(n))** time. Efficiency could be improved dramatically while actually *decreasing* score to **66 bytes**, but the function would return *True* for input **2**.

```
f=lambda n,k=1,a=1:a/n or~-a**k*a**-~k%n<1==f(n,k,a+1)or-~f(n,k+1)

```

## Background

### Definitions and notation

All employed variables will denote integers; **n**, **k**, and **α** will denote *positive* integers; and **p** will denote a positive *prime*.

**a | b** if **b** is divisible by **a**, i.e., if there is **q** such that **b = qa**.

**a ≡ b (*mod* m)** if **a** and **b** have the same residue modulo **m**, i.e., if **m | a - b**.

**λ(n)** is the smallest **k** such that **ak ≡ 1 (*mod* n)** – i.e., such that **n | ak \- 1** – for all **a** that are coprime to **n**.

**f(n)** is the smallest **k** such that **a2k+1 ≡ ak+1 (*mod* n)** – i.e., such that **n | ak+1(ak \- 1)** – for all **a**.

### λ(n) ≤ f(n)

Fix **n** and let **a** be coprime to **n**.

By the definition of **f**, **n | af(n)+1(af(n) \- 1)**. Since **a** and **n** do not have a common prime factor, neither do **af(n)+1** and **n**, which implies that **n | af(n) \- 1**.

Since **λ(n)** is the smallest integer **k** such that **n | ak \- 1** for all integers **a** that are coprime to **n**, it follows that **λ(n) ≤ f(n)**.

### λ(n) = f(n)

Since we've already established the inequality **λ(n) ≤ f(n)**, it is sufficient to verify that **k = λ(n)** satisfies the condition that defines **f**, i.e., that **n | aλ(n)+1(aλ(n) \- 1)** for all **a**. For this purpose, we'll establish that **pα | aλ(n)+1(aλ(n) \- 1)** whenever **pα | n**.

**λ(k) | λ(n)** whenever **k | n** (source), so **(aλ(k) \- 1)(aλ(n)-λ(k) \+ aλ(n)-2λ(k) \+ ⋯ + aλ(k) \+ 1) = aλ(n) \- 1** and, therefore, **aλ(k) \- 1 | aλ(n) \- 1 | aλ(n)+1(aλ(n) \- 1)**.

If **a** and **pα** are coprime, by the definition of **λ** and the above, **pα | aλ(pα) \- 1 | aλ(n)+1(aλ(n) \- 1)** follows, as desired.

If **a = 0**, then **aλ(n)+1(aλ(n) \- 1) = 0**, which is divisible by all integers.

Finally, we must consider the case where **a** and **pα** have a common prime factor. Since **p** is prime, this implies that **p | a**. Carmichael's theorem establishes that **λ(pα) = (p - 1)pα - 1** if **p \> 2** or **α \< 3** and that **λ(pα) = pα - 2** otherwise. In all cases, **λ(pα) ≥ pα - 2 ≥ 2α - 2 \> α - 2**.

Therefore, **λ(n) + 1 ≥ λ(pα) + 1 \> α - 1**, so **λ(n) + 1 ≥ α** and **pα | pλ(n)+1 | aλ(n)+1 | aλ(n)+1(aλ(n) \- 1)**. This completes the proof.

## How it works

While the definitions of **f(n)** and **λ(n)** consider all possible values of **a**, it is sufficient to test those that lie in **\[0, ..., n - 1\]**.

When **f(n, k)** is called, it computes **ak+1(ak \- 1) % n** for all values of **a** in that range, which is **0** if and only if **n | ak+1(ak \- 1)**.

If all computed residues are zero, **k = λ(n)** and `any` returns *False*, so **f(n, k)** returns **1**.

On the other hand, while **k \< λ(n)**, `1-any(...)` will return **0**, so **f** is called recursively with an incremented value of **k**. The leading `-~` increments the return value of **f(n, k + 1)**, so we add **1** to **f(n, λ(n)) = 1** once for every integer in **\[1, ..., λ(n) - 1\]**. The final result is thus **λ(n)**.
> 28 votes

# Answer
# Mathematica without built-in, ~~58~~ 57 bytes

*Thanks to Martin Ender for finding an error, then saving me the bytes it took to fix it!*

*Thanks to miles for saving 1 byte! (which seemed like 2 to me)*

Built-ins are totally fine ... but for those who want to implement it without using brute force, here's a formula for the Carmichael function:

```
LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&

```

If p is a prime, the Carmichael function λ(p^r) equals φ(p^r) = (p-1)\*p^(r-1)—*except* when p=2 and r≥3, in which case it's half that, namely 2^(r-2).

And if the prime-power factorization of n equals p1^r1 * p2^r2 * ..., then λ(n) equals the least common multiple of { λ(p1^r1), λ(p2^r2), ...}.

Runtime is one instant more than factoring the integer in the first place.
> 14 votes

# Answer
# Templates Considered Harmful, 246 bytes

```
Fun<Ap<Fun<If<Eq<A<2>,T>,A<1>,And<Eq<Ap<Fun<If<A<1>,Ap<A<0>,Rem<A<2>,A<1>>,A<1>>,A<2>>>,A<1,1>,A<2>>,T>,Sub<Ap<Fun<Rem<If<A<1>,Mul<A<2,1>,Ap<A<0>,Sub<A<1>,T>>>,T>,A<1,2>>>,A<1>>,T>>,Ap<A<0>,Add<A<1>,T>,A<1,1>>,Ap<A<0>,A<1>,Sub<A<2>,T>>>>,T,A<1>>>

```

An unnamed function (not that there are named functions).

This is a forgotten esolang of mine which is interpreted by a C++ compiler instantiating templates. With the default max template depth of `g++`, it can do λ(35), but it can't do λ(101) (the lazy evaluation makes things worse).
> 12 votes

# Answer
# Haskell, ~~57~~ 56 bytes

```
f n=[k|k<-[1..],and[mod(m^k)n<2|m<-[1..n],gcd m n<2]]!!0

```
> 10 votes

# Answer
# Jelly, 2 bytes

```
Æc

```

Thank you for the builtin, @Lynn
> 9 votes

# Answer
# Pyth - ~~19~~ ~~18~~ 17 bytes

*One byte saved thanks to @TheBikingViking.*

Straight up brute force.

```
f!sm*t.^dTQq1iQdQ

```

Try it online here.
> 6 votes

# Answer
# Ruby, ~~59~~ 56 bytes

```
->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}

```
> 6 votes

# Answer
# J, ~~28~~ 27 bytes

```
[:*./@(5&p:%2^0=8&|)2^/@p:]

```

The Carmichael function is λ(*n*) and the totient function is φ(*n*).

Uses the definition where λ(*p**k*) = φ(*p**k*)/2 if *p* = 2 and *k* \> 2 else φ(*p**k*). Then, for general *n* = *p*1*k*1 *p*2*k*2*p**i**k**i*, λ(*n*) = LCM\[ λ(*p*1*k*1) λ(*p*2*k*2) ⋯ λ(*p**i**k**i*) \].

## Usage

Extra commands used to format multiple input/output.

```
   f =: [:*./@(5&p:%2^0=8&|)2^/@p:]
   f 530
52
   (,.f"0) 1 2 3 10 35 101 530 3010 6511 10000
    1    1
    2    1
    3    2
   10    4
   35   12
  101  100
  530   52
 3010   84
 6511 3056
10000  500

```

## Explanation

```
[:*./@(5&p:%2^0=8&|)2^/@p:]  Input: integer n
                          ]  Identity function, get n
                    2   p:   Get a table of prime/exponent values for n
                     ^/@     Raise each prime to its exponent to get the prime powers of n
[:    (            )         Operate on the prime powers
                8&|            Take each modulo 8
              0=               Test if its equal to 0, 1 if true else 0
            2^                 Raise 2 to the power of each
       5&p:                    Apply the totient function to each prime power
           %                   Divide it by the powers of 2
  *./@                       Reduce using LCM and return

```
> 5 votes

# Answer
## JavaScript (ES6), ~~143~~ 135 bytes

*Edit: saved 8 bytes thanks to Neil*

An implementation using functional programming.

```
n=>(A=[...Array(n).keys()]).find(k=>k&&!c.some(c=>A.slice(0,k).reduce(y=>y*c%n,1)-1),c=A.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1

```

### Ungolfed and commented

```
n =>                                          // Given a positive integer n:
  (A = [...Array(n).keys()])                  // Build A = [0 ... n-1].
  .find(k =>                                  // Try to find k in [1 ... n-1] such as
    k && !c.some(c =>                         // for each coprime c: c^k ≡ 1 (mod n).
      A.slice(0, k).reduce(y =>               // We use reduce() to compute
        y * c % n, 1                          // c^k mod n.
      ) - 1                                   // Compare it with 1.
    ),                                        // The list of coprimes is precomputed
    c = A.filter(x =>                         // before the find() loop is executed:
      (                                       // for each x in [0 ... n-1], keep
        g = (x, y) => x ? g(y % x, x) : y     // only integers that verify:
      )(x, n) == 1                            // gcd(x, n) = 1
    )                                         // (computed recursively)
  ) || 1                                      // Default result is 1 (for n = 1)

```

### Demo

Although it does work for `6511` and `10000`, I won't include them here as it tends to be a bit slow.

```
let f =
n=>(A=[...Array(n).keys()]).find(k=>k&&!c.some(c=>A.slice(0,k).reduce(y=>y*c%n,1)-1),c=A.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1

console.log(f(1));     // 1
console.log(f(2));     // 1
console.log(f(3));     // 2
console.log(f(10));    // 4
console.log(f(35));    // 12
console.log(f(101));   // 100
console.log(f(530));   // 52
console.log(f(3010));  // 84
```
> 4 votes

# Answer
# Actually, ~~30~~ ~~28~~ ~~25~~ ~~19~~ 26 bytes

The Carmichael function, `λ(n)` where `n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a`, is defined as the least common multiple (LCM) of `λ(p_i**k_i)` for the maximal prime powers `p_i**k_i` that divide into `n`. Given that for every prime power except where the prime is `2`, the Carmichael function is equivalent to the Euler totient function, `λ(n) == φ(n)`, we use `φ(n)` instead. For the special case of `2**k` where `k ≥ 3`, we just check if `2**3 = 8` divides into `n` at the beginning of the program, and divide by 2 if it does.

Unfortunately, Actually doesn't currently have an LCM builtin, so I made a brute-force LCM. Golfing suggestions welcome. Try it online!

```
;7&Yu@\w`iⁿ▒`M╗2`╜@♀%ΣY`╓N

```

**Ungolfing**

```
         Implicit input n.
;        Duplicate n.
7&       n&7 == n%8.
Yu       Logical NOT and increment. If n%8 == 0, return 2. Else, return 1.
@\       Integer divide n by 2 if n%8==0, by 1 otherwise.
          Thus, we have dealt with the special case where p_i == 2 and e_i >= 3.
w        Full prime factorization of n as a list of [prime, exponent] lists.
`...`M   Map the following function over the prime factorization.
  i        Flatten the array, pushing exponent, then prime to the stack.
  ⁿ▒       totient(pow(prime, exponent)).
╗        Save that list of totients in register 0.
2`...`╓  Get the first two values of n where the following function f(n) is truthy.
         Those two numbers will be 0 and our LCM.
  ╜@       Push the list in register 0 and swap with our n.
  ♀%       Get n mod (every number in the list)
  Σ        Sum the modulos. This sum will be 0, if and only if this number is 0 or LCM.
  Y        Logical NOT, so that we only get a truthy if the sum of modulos is 0.
N        Grab the second number, our LCM. Implicit return.

```
> 4 votes

# Answer
# Ruby, ~~101~~ ~~86~~ ~~91~~ 90 bytes

A Ruby port of my Actually answer. Golfing suggestions welcome.

**Edit:** -4 bytes from removing `a` but +9 bytes from fixing a bug where `1` returned `nil`. -1 byte thanks to Cyoce.

```
require'prime'
->n{((n%8<1?n/2:n).prime_division<<[2,1]).map{|x,y|x**~-y*~-x}.reduce :lcm}

```

**Ungolfing**

```
require 'prime'
def carmichael(n)
  if n%8 < 1
    n /= 2
  end
  a = []
  n.prime_division.do each |x,y|
    a << x**(y-1)*(x-1)
  end
  return a.reduce :lcm
end

```
> 2 votes

# Answer
# JavaScript (ES 2016) 149

Python reference implementation ported to JS. Some fancy Pyhton builtin is missing in js, like `gcd` and `pow`, and the array comprehension is not standard in ES 6. This works in Firefox.

```
n=>eval('for(g=(a,b)=>b?g(b,a%b):a,p=(a,b,c)=>eval("for(r=1;b--;)r=r*a%c"),c=[for(_ of Array(i=n))if(g(i--,n)<2)i+1],k=1;c.some(x=>p(x,k,n)-1);)++k')

```

*Less golfed*

```
n=>{
  g=(a,b)=>b?g(b,a%b):a
  p=(a,b,c)=>{
    for(r=1;b--;)
      r=r*a%c
    return r
  }
  c=[for(_ of Array(i=n)) if(g(i--,n)<2) i+1]
  for(k=1;c.some(x=>p(x,k,n)-1);)
    ++k
  return k
}

```
> 1 votes

# Answer
# Java8 ~~38~~ 19 + ~~287~~ ~~295~~ ~~253~~ ~~248~~ 241 = ~~325~~ ~~333~~ ~~272~~ ~~267~~ 260 bytes

```
BigInteger B(int i){return new BigInteger(""+i);}int c(int...k){int n=k[0];for(k[0]=1;n>1&!java.util.stream.IntStream.range(0,n).filter(i->B(n).gcd(B(i)).equals(B(1))).allMatch(x->B(x).modPow(B(k[0]),B(n)).equals(B(1)));k[0]++);return k[0];}

```

**Imports, 19 bytes**

```
import java.math.*;

```

**Explanation**

It is a straight forward implementation. The co-primes are calculated in the `Set p` and every one's kth power is used to check if it equals 1 modulo n.

I had to use `BigInteger` because of precision issues.

**Usage**

```
public static void main(String[] args) {
    Carmichael c = new Carmichael();
    System.out.println(c.c(3)); // prints 2
}

```

**Ungolfed**

```
// returns the BigInteger representation of the given interger
BigInteger B(int i) {
    return new BigInteger(""+i);
}
// for a given integer it returns the result of the carmichael function again as interger
// so the return value cannot be larger
int c(int... k) {
    int n = k[0];
    // iterate k[0] until for all co-primes this is true: (x^n) mod n == 1, if n==1 skip the loop
    for (k[0]=1;n > 1 && !java.util.stream.IntStream.range(0, n)
                .filter(i -> B(n).gcd(B(i)).equals(B(1)))
                .allMatch(x -> B((int) x).modPow(B(k[0]), B(n)).equals(B(1)));k[0]++);
    return k[0];
}

```

Any suggestions to golf it more are welcome :-)

**Update**

* No elements outside the functions that keep the state
* Followed Olivier Grégoire's advice and saved 1 byte from `B()`
* Removed the `k()` method and `p` (co-primes) Set.
* Removed not required casting to int.
* Added varags and use for instead of while.
> 1 votes

# Answer
# Java, ~~209~~ ~~207~~ ~~202~~ ~~194~~ 192 bytes

Code (96 bytes):

```
n->{for(int x,k=1,a;;k++){for(a=1,x=0;++x<=n&&a<2;)a=g(x,n)<2?p(x,k,n):1;if(a<2||n<2)return k;}}

```

extra functions (96 bytes):

```
int g(int a,int b){return b<1?a:g(b,a%b);}int p(int n,int p,int m){return p<2?n:n*p(n,p-1,m)%m;}

```

## Testing & ungolfed

```
import java.util.Arrays;
import java.util.function.IntUnaryOperator;

public class Main2 {

  static int g(int a,int b) { // recursive gcd
    return b < 1
        ? a
        : g(b,a%b);
  }

  static int p(int n, int p, int m) { // recursive modpow
    return p < 2
      ? n
      : n * p(n, p - 1, m) % m;
  }

  public static void main(String[] args) {

    IntUnaryOperator f = n -> {
      for(int x,k=1,a;;k++) { // for each k
        for(a=1,x=0;++x<=n&&a<2;) // for each x
          a=g(x,n)<2?p(x,k,n):1; // compute modpow(x,k,n) if g(x,n)
        if(a<2||n<2) // if all modpow(x,k,n)=1. Also check for weird result for n=1.
          return k;
      }
    };

    Arrays.stream(new int[]{1, 2, 3, 10, 35, 101, 530, 3010, 6511, 10000})
        .map(f)
        .forEach(System.out::println);
  }
}

```

## Notes

* the use of `a` being an `int` is shorter than if I had to use a `boolean` to perform my tests.
* Yes, it's shorter to `valueOf` all new `BigInteger` than create a separate function (there are 5, plus the `ONE` constant is a freebie).
* Algorithm is different than @Master\_ex' algorithm, so it's not just a golfed repost. Also, this algorithm is much less efficient as `gcd` is computed again and again for the same values.

## Shaves

1. 209 -\> 207 bytes:
    * `if(...)a=...;` -\> `a=...?...:1;`
    * `a==1` -\> `a<2`
2. 207 -\> 202 bytes
    * Got rid of `BigInteger` by golfing `gcd` and `modPow` for `int`.
3. 202 -\> 194 bytes
    * looping `modPow` -\> recursive
4. 194 -\> 192 bytes
    * `==1` -\> `<2` (seems to work for all the test cases, don't know for other numbers.)
> 1 votes

# Answer
# C++, ~~208 200 149 144 140~~ 134 bytes

```
[](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;};

```

A port of my C implementation.

Try it on Ideone
> 1 votes

# Answer
# Java, ~~165 163 158 152~~ 143 bytes

```
int l(int n){int k=1,x,a,b,t,d=1;for(;d>0;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;b>0;b=a%b,a=t)t=b;for(t=b=1;b++<=k;t=t*x%n);}return k;}

```

Another port of my C implementation.

Try it on Ideone
> 1 votes

# Answer
# C, ~~278 276 272 265 256 243 140 134~~ 125 bytes

```
k,x,a,b,t,d;l(n){for(k=d=1;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;}

```

This uses a slow modular exponentiation algorithm, computes the GCD too often and no longer leaks memory!

Ungolfed:

```
int gcd( int a, int b ) {
  int t;
  while( b ) {
    t = b;
    b = a%b;
    a = t;
  }
  return a;
}
int pw(int a,int b,int c){
  int t=1;
  for( int e=0; e<b; e++ ) {
    t=(t*a)%c;
  }
  return t;
}
int carmichael(int n) {
  int k = 1;
  for( ;; ) {
    int done = 1;
    for( int x=1; x<n; x++ ) {
      if( gcd(x,n)==1 && pw(x,k,n) != 1 ) {
        done = 0;
        k++;
      }
    }
    if( done ) break;
  }
  return k;
}

```

Try it on Ideone
> 0 votes

# Answer
## Racket 218 bytes

```
(λ(n)(let((fl #f)(cl(for/list((i n) #:when(coprime? n i))i)))(for/sum((k(range 1 n))#:break fl)(set! fl #t)
(for((i(length cl))#:break(not fl))(when(not(= 1(modulo(expt(list-ref cl i)k)n)))(set! fl #f)))(if fl k 0))))

```

Ungolfed version:

```
(require math)
(define f
  (λ(n)
    (let ((fl #f)
          (cl (for/list ((i n) #:when (coprime? n i))
                i)))
             (for/sum ((k (range 1 n)) #:break fl)
               (set! fl #t)
               (for ((i (length cl)) #:break (not fl))
                 (when (not (= 1 (modulo (expt (list-ref cl i) k) n)))
                   (set! fl #f)))
               (if fl k 0)))))

```

Testing:

```
(f 2)
(f 3)
(f 10)
(f 35)
(f 101)
(f 530)
(f 3010)
(f 6511)
(f 10000)

```

Output:

```
1
2
4
12
100
52
84
3056
500

```
> 0 votes

# Answer
**Axiom 129 bytes**

```
c(n)==(r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1);repeat(for a in r repeat(v:=powmod(a,k,n);v~=1=>break);v<=1=>break;k:=k+1);k)

```

less golfed

```
cml(n)==
 r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1)
 repeat
   for a in r repeat(v:=powmod(a,k,n);v~=1=>break)
   v<=1=>break
   k:=k+1
 k

```

results

```
(3) -> [i,c(i)] for i in [1,2,3,10,35,101,530,3010,6511,10000]
   Compiling function c with type PositiveInteger -> PositiveInteger

   (3)
   [[1,1], [2,1], [3,2], [10,4], [35,12], [101,100], [530,52], [3010,84],
    [6511,3056], [10000,500]]
                                             Type: Tuple List PositiveInteger

```
> 0 votes

---
Tags: code-golf, math, number, number-theory, primes
---


title: Handling errors

text:
# Question
Title: Handling errors
What's great about golfing is not having to deal with errors. Except this time you won't get off so lightly! I need to do some arithmetic with certain limitations, and I wan't to know what goes wrong if anything.

# Challenge

Given a list of signed integer values `[n1..n11]`, give the following result *or* the first error that occurred.

```
(((((((((n1+n2)-n3)^n4)/n5)*n6)+n7)-n8)^n9)/n10)*n11

```

The same in reverse polish notation:

```
n1 n2 + n3 - n4 ^ n5 / n6 * n7 + n8 - n9 ^ n10 / n11 *

```

The operators have the following limitations:

* `0^0` → error `0^0 is undefined`
* `0^a` when `a<0` → error `Negative exponent`
* `a/0` → error `Division by zero`
* `a/b` when `mod a b != 0` → error `Uneven division`
* for any operator: `result < 0` → error `Integer underflow`
* for any operator: `result > 99` → error `Integer overflow`
* for any operator: either input value or result == 13 → error `13 is bad luck!`

Errors occur left to right, so `13/0` = error `13 is bad luck!`.

## Scoring

The shortest code in bytes wins. To encourage readability string literals used for errors won't count towards the score.

The output format isn't strict but all seven errors plus a correct value must be distinguishable. Your program/function must retain control flow until the end, so e.g. any exceptions must be caught.

Standard loopholes are disallowed.

# Examples

```
[6,7,14,2,0,1,2,3,4,0,6]   → error `13 is bad luck!`
[6,6,14,2,0,1,2,3,4,0,6]   → error `Integer underflow`
[6,6,12,0,0,1,2,3,4,0,6]   → error `0^0 is undefined`
[6,6,12,2,0,1,2,3,4,0,6]   → error `Division by zero`
[6,6,10,6,12,1,2,3,4,0,6]  → error `Uneven division`
[6,6,10,6,8,17,2,13,4,0,6] → error `Integer overflow`
[6,6,10,6,8,7,99,13,4,0,6] → error `Integer overflow`
[6,6,10,6,8,7,9,99,4,0,6]  → error `Integer underflow`
[6,6,10,6,8,7,9,55,-2,0,0] → error `Negative exponent`
[6,6,10,6,8,7,9,56,2,0,8]  → error `Division by zero`
[6,6,10,6,8,7,9,56,2,9,12] → error `Integer overflow`
[6,6,10,6,8,7,9,56,2,9,11] → 99

```

# Answer
## Haskell, ~~190~~ ~~186~~ 185 bytes

311 bytes total, 185 bytes without the string literals.

```
e=Left
0#0=e"0^0 is undefined"
b#_|b<0=e"Negative exponent"
b#a=t$a^b
0!a=e"Division by zero"
b!a|mod a b>0=e"Uneven division"
b!a=t$div a b
t 13=e"13 is bad luck!"
t x|x<0=e"Integer underflow"|x>99=e"Integer overflow"|1<2=Right x
f(x:y)=foldl(>>=)(t x)$zipWith id(cycle[q(+),q(-),(#),(!),q(*)])y
q=((t.).).flip

```

This wraps the error handling in the `Either e` monad, i.e. the result is either `Left <ErrorMsg>` or `Right <Number>`, for example:

```
*Main> f [6,6,10,6,8,7,9,56,2,9,11]
Right 99
*Main> f [6,6,10,6,8,7,9,56,2,0,8]
Left "Division by zero"

```

How it works: define custom versions for operators with individual error handling, i.e. `#` for `^` and `!` for `/` (resp. `div` as it is called in Haskell) and lift the others (`+`, `-`, `*`) via `q` into the monad. The main function `f` creates a list of unary function form the numbers (without the first one) and the list of the operators in order, e.g. `[+6, -10, #6, !8, ...]` and reduces this list by feeding the first number into a chain of `>>=`.

Edit: @Angs found a bug. Fixing it saved 4 bytes.
> 4 votes

---
Tags: code-golf, math, arithmetic
---


title: Write a Semiquine

text:
# Question
Title: Write a Semiquine
Suppose you have 2 languages, `A` and `B`. A string `s` is a semiquine in `A` and `B` if it satisfies the following conditions:

1. `s` is a quine in language `A`.
2. `s` is a polyglot in `A` and `B`.
3. The output of running `s` as a `B` program is a different string `s'`, which is a quine in `B`.

The goal of this challenge is to write a semiquine in two distinct languages. This is , so shortest code wins, with earliest answer used as a tiebreaker.

### Rules for Quines

Only *true* quines are accepted. That is, you need to print the entire source code verbatim to STDOUT, **without**:

* reading your source code, directly or indirectly.
* relying on a REPL environment which just simply evaluates and prints every expression you feed it.
* relying on language features which just print out the source in certain cases.
* using error messages or STDERR to write all or part of the quine. (You may write things to STDERR or produce warnings/non-fatal errors as long as STDOUT is a valid quine and the error messages are not part of it.)

Furthermore, your source code must not consist purely of literals (whether they be string literals, numeric literals, etc.) and/or NOPs. For example, ``12` is a polyglot in Jelly and Pyth, but in Jelly it is a NOP and a numeric literal, so it is not valid.

Any non-suppressible output (such as copyright notices, startup/shutdown messages, or a trailing line feed) may be ignored in the output for the sake of the validity of the quine.

### Rules for Polyglots

The two languages used must be distinctly different. In particular:

* They must not be different versions of the same language (e.g. Python 2 vs. Python 3).
* They must not be different dialects of the same language (e.g. Pascal vs. Delphi).
* One language may not be a subset of the other one (e.g. C vs. C++1).
* One language may not be a trivial derivative of the other (e.g. Matlab vs. Octave2, brainfuck vs boolfuck vs TinyBF vs ShadyAsFuck vs all the other trivial brainfuck derivatives).

### Miscellaneous Rules

* You may not accept input from STDIN (or any other source). If your chosen language *must* take input, then either the input must be empty (empty string, piped from `/dev/null`, etc.), or the output of the program must not depend on the input.
* For this challenge, you must write a complete program. Requiring additional code to run the solution is not allowed (such as assigning and calling a lambda function defined in the solution).

1: Yes I know that C is not really a subset of C++. It's close enough to be considered one for the purpose of polyglots, though, so I'm counting it for this challenge.

2: Like point 1 above, though Octave is technically not 100% compatible with Matlab, it was designed to be compatible, and is close enough that allowing a Matlab/Octave polyglot would trivialize the challenge.

# Answer
> 5 votes
## GolfScript + Fission, ~~19~~ 18 bytes

```
{".~
'!+OR"
2<}.~

```

The trailing linefeed is necessary.

This is a true quine in GolfScript. Try it online!

In Fission it prints

```
'!+OR"

```

which is a true quine in Fission. Try it online!

### Explanation

In GolfScript, anything of the form

```
{...}.~

```

is a quine as long as `...` leaves a string with `".~"` on the stack. The `.` duplicates the block, such that there's one copy that gets printed at the end, and the `~` executes it, so we can use its contents to print the `.~` itself. In this case, the block pushes the string

```
".~
'!+OR"

```

and then truncates it to the first two characters with `2<`.

The Fission program really works exactly the same as the quine itself, since the first and third line are entirely ignored by the program.

# Answer
> 4 votes
# Ruby + (JavaScript *or* Python 3), 76 bytes

This is another challenge that can be solved using my new favourite language, the almost-common subset of Ruby, JavaScript, and Python 3; and given that we don't have any answers in exoteric languages yet, and many people like to see non-golfing-language solutions, I thought I'd contribute one. Even better, the same answer solves the challenge in a variety of ways at the same time.

Here's `s`:

```
s="'";d='"';n='print("s="+d+s+d+";d="+s+d+s+";n="+s+n+s+";eval(n)")';eval(n)

```

This is a quine in Ruby. It isn't a quine in JavaScript or Python 3; if you run it in either of those languages, its output `s'` has a trailing newline, and thus is different:

```
s="'";d='"';n='print("s="+d+s+d+";d="+s+d+s+";n="+s+n+s+";eval(n)")';eval(n)

```

However, `s'` is a polyglot quine in JavaScript and Python 3! (As usual for me, I'm using the Rhino implementation of JavaScript, both for convenience (as it runs from the command line rather than needing a browser), and because it has a weird standard library in which `print` writes to standard output.) Both languages produce `s'` as a result of running either program.

As a bonus, this program also solves the problem in reverse. If you decide to run `s'` in Ruby, it'll print the original program `s` again. As such, `s'` is a valid (but slightly longer, at 77 bytes) answer to the question.

At this point, I'm almost starting to think "differences in whether or not the output ends with a newline being sufficient to count two programs as different" should be considered a standard loophole, given that this seems to be a second set of languages (beyond the well known GolfScript/CJam) in which it's possible to pull the trick off.

# Answer
> 2 votes
# Vitsy (safe mode) and Y, 9 bytes, noncompeting.

```
' Ugrd3*Z

```

In Vitsy, this is a quine. In Y, this prints `Ugrd3*Z'`; when run, this prints `Ugrd3*Z'`, which is a quine in Y. Y postdates the question, however.

What Vitsy sees:

```
 ' Ugrd3*Z
 '         Heyyyy a string! Let's do this!
  ........ Capturing a string! Oh, not done? Hm, let's go back to the start.
 '         There we go.
           (space) ...
   U       (no op)
    g      use count, disabled in safe mode
     r     reverse stack
      d3*  push a '
         Z print it all!

```

What Y sees:

```
' Ugrd3*Z
'         Push a space.
  U       Wrap around and capture.
   g      Print that. (Nothing else is printed.)

```

# Answer
> 1 votes
# CJam + GolfScript, 9 bytes

```
"0$p"
0$p

```

This is a quine in CJam. In GolfScript, it outputs itself with a trailing newline, which is a quine in GolfScript.

I'm not sure whether CJam should be considered a trivial derivative of GolfScript. But I think they are quite different and at least not trivial.

---
Tags: code-golf, quine, code-generation, polyglot
---


title: Prove 2+2=2*2 (and similar)

text:
# Question
Title: Prove 2+2=2*2 (and similar)
Output a full formal poof of such statements such as `1+2=3`, `2+2=2*(1+1)` etc.

# Introuction

If you know Peano Arithmetic you can probably skip this section.

Here's how we define the Natural Numbers:

```
(Axiom 1) 0 is a number
(Axiom 2) If `x` is a number, the `S(x)`, the successor of `x`, is a number.

```

Hence, for example `S(S(S(0)))` is a number.

You can use any equivalent representation in your code. For example, all of these are valid:

```
0    ""    0           ()       !
1    "#"   S(0)        (())     !'
2    "##"  S(S(0))     ((()))   !''
3    "###" S(S(S(0)))  (((()))) !'''
...
etc

```

We can extend the rules to define addition as follows.

```
(Rule 1) X+0 = X
(Rule 2) X+S(Y)=S(X)+Y

```

With this we can prove 2+2=4 as follows

```
         S(S(0)) + S(S(0)) = 2 + 2
[Rule 2 with X=S(S(0)), Y=S(0)]
         S(S(S(0))) + S(0) = 3 + 1
[Rule 2 with X=S(S(S(0))), Y=0]
         S(S(S(S(0)))) + 0 = 4 + 0
[Rule 1 with X=S(S(S(S(0))))
         S(S(S(S(0))))     = 4

```

We can extend these rules to define multiplication as follows

```
(Rule 3) X*0 = 0
(Rule 4) X*S(Y) = (X*Y) + X

```

Although to allow this we need to define the structural role of parentheses.

```
(Axiom 3) If X is a number, (X) is the same number.

```

Addition and multiplication operators are strictly binary and parentheses must always be explicit. `A+B+C` is not well-defined, but `(A+B)+C` and `A+(B+C)` are.

# Example

Now we have enough to prove a theorem about multiplication: 2+2=2\*2

```
2 + 2
(2) + 2
(0 + 2) + 2
((0*2) + 2) + 2
(1*2) + 2
2*2

```

# Requirements

A *proof that `A=B`* is a list expressions such that:

* the first is `A`,
* the last is `B`, and
* each expression in the list apart from the first can obtained from the previous by transforming it under one of the rules.

Your program will take **two valid expressions as input**, each expression contains numbers, addition, multiplication, and parentheses as defined above.

Your program will output a proof, a list as defined above, that the two expressions are equal, if such a proof exists.

If the two expressions are not equal, your program will output nothing.

Proving or disproving is always possible in a finite number of steps, because each expression can be reduced to a single number and these numbers can be trivially tested for equality.

If the input expressions are not valid (e.g. unbalanced parentheses, contains non-numbers, or non-binary operators) then your program should exit with error, throw an exception, print an error, or otherwise produce some observable behaviour *which is distinct from the case in which the inputs are valid but non-equal*.

In summary, the normal output for admissible inputs is a list of equal numbers, including the inputs, which is produced by the following rules.

```
(Axiom 1) 0 is a number
(Axiom 2) If `x` is a number, the `S(x)`, the successor of `x`, is a number.
(Axiom 3) If X is a number, (X) is the same number

(Rule 1) X+0 = X
(Rule 2) X+S(Y)=S(X)+Y
(Rule 3) X*0 = 0
(Rule 4) X*S(Y) = (X*Y) + X
(Rule 5) X = (X)              (Axiom 3 expressed as a transformation rule.)

```

Any suitable representation of the numbers in the input and output is allowed, e.g. `0=""=()`, `3="###"=(((())))`, etc. Whitespace is irrelevant.

Rules can, of course, be applied in either direction. Your program does not have to output which rule is used, just the expression produced by its action on the previous expression.

Shortest code wins.

# Answer
> 5 votes
# Perl, 166 + 1 bytes

Run with `-p` (1 byte penalty).

```
$r='\((S*)';(@b,@a)=@a;push@a,$_ while+s/\+S/S+/||s/$r\+\)/$1/||s/$r\*\)//||s/$r\*S(S*)/(($1*$2)+$1/||s/$r\)/$1/;$\.=/[^S]./s;$_=$b[-1]eq$a[-1]?join'',@b,reverse@a:""

```

More readable:

```
                           # implicit: read a line of input into $_
                           # we leave the newline on
$r = '\((S*)';             # we use this regex fragment a lot, factor it out
(@b, @a) = @a;             # set @b to @a, @a to empty
push @a, $_ while          # each time round the loop, append $_ to @a
+s/\+S/S+/||               # rule 2: change "+S" to "S+"
s/$r\+\)/$1/||             # rule 1: change "(X+0)" to "X"
s/$r\*\)//||               # rule 3: change "(X*0)" to ""
s/$r\*S(S*)/(($1*$2)+$1/|| # rule 4: change "(X*Y" to "((X*Y)+X"
s/$r\)/$1/;                # rule 5: change "(X) to "X"
$\.=/[^S]./s;              # append a 1 to the newline character if we
                           # see any non-S followed by anything
$_=$b[-1]eq$a[-1]?         # if @b and @a end the same way
  join'',@b,reverse@a      # then $_ becomes @b followed by (@a backwards)
  :""                      # otherwise empty $_
                           # implicit: output $_

```

The input format expresses numbers in unary as strings of `S`, and requires the two inputs on separate lines (each followed by a newline, and an EOF after both are seen). I interpreted the question as requiring that parentheses should be literally `(` `)` and addition/multiplication should be literally `+` `*`; I can save a few bytes through less escaping if I'm allowed to make different choices.

The algorithm actually compares the first line of input with an empty line, the second with the first, the third with the second, and so on. This fulfils the requirements of the question. Here's an example run:

My input:

```
(SS+SS)
(SS*SS)

```

Program output:

```
(SSS+S)
(SSSS+)
SSSS
SSSS
(SSSS+)
((SS+)SS+)
(((SS*)SS+)SS+)
(((SS*)S+S)SS+)
(((SS*)+SS)SS+)
((SS*S)SS+)
((SS*S)S+S)
((SS*S)+SS)

```

The duplicated `SSSS` in the middle is annoying but I decided it didn't violate the specification, and it's fewer bytes to leave it in.

On invalid input, I append `1` to the newline character, so you get stray `1`s sprinkled in at the end of the output.

---
Tags: code-golf, math, arithmetic, syntax, repeated-transformation
---


title: I want to watch you die of thirst

text:
# Question
Title: I want to watch you die of thirst
You are a traveller crossing the desert between two towns. You cannot carry enough water to get across without stopping. This is a variation of a classic puzzle.

# The Rules

A desert looks like this: a WxH grid of mostly empty space. The space marked `S` is where you start, `E` is where you want to end, and a square marked with the number N holds N units of water. Squares marked with a `.` hold zero water.

```
.....................................
........S............................
.....................................
.........7...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................

```

You start at S with 5 units of water.

You can carry at most 5 units of water.

Each turn you

1. move one square Up, Down, Left, or Right,
2. consume 1 unit of water that you are carrying,
3. pick up **or drop** some number of units of water.

A turn is notated thus: `(direction)(+|-)(units of water)`, `+` indicates you are picking up water, `-` that you are dropping it.

Example turns:

```
D+0        Move Down
R+0        Move Right
D+2        Move Down, pick up two units of water.
U-1        Move Up, drop one unit of water.

```

If you perform these moves starting at S in the example above, the desert looks like this afterwards.

```
.....................................
........S............................
.........1...........................
.........5...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................

```

You can pick up no more water than is already on your square. When you pick up the water, deduct that number of units from the tile's count.

You can only pick up water to hold a maximum of 5 units.

No tile can hold more than 9 units, except S which holds infinity units.

You can only drop as much water as you are currently holding.

Water on the ground remains unchanged until you pick it up again.

If you return to S you can pick up any quantity of water without depleting it.

If you reach E then **you win**. You still win if you consume your last unit of water on E.

If, after your turn, you have zero water and you are not on E, **you die**.

# Input and Output

Your program will receive a starting map of arbitrary size on `STDIN` as ASCII art in the format above. You can assume it is rectangular i.e. all lines the same length, that there is exactly one `S` and one `E` square, all lines are terminated with `\n`, and the whole of STDIN will conform to this regex: `/^[SE1-9\.\n]+$/`

Your program will write the following output to STDOUT:

1. the list of moves,
2. the final state of the map.

You may output the list of moves in any convenient format.

The final state of the map will be printed in the same format as the input **except that it will additionally show the route you took through the desert** by marking all visited tiles with `#`, if that tile contains no water and is not S or E (i.e. it is `.`).

**EXAMPLE** input:

```
.....S.
.......
.......
E......
....8..

```

**EXAMPLE** winning output:

```
D+0
D+0
D+0
D+0
L+5
L+0
L+0
L+0
L+0
U+0
.....S.
.....#.
.....#.
E....#.
####3#.

```

# Nontriviality

When you post your code, post a sample map input which your code finds a solution for which satisfies the following non-triviality conditions:

* S and E are at least 10 moves apart.
* Any square which initially contains N units of water must be surrounded by a N-width border in which all squares are `.` (no water, not S or E)

**EXAMPLE**

```
........2.
..........
..........
S.1..2....
..........
..........
........1.
..3.......
.........E

```

If you increase the amount of water on any tile, the above becomes trivial.

# Requirements

Presumably your program will encounter a number of failed attempts before it finds a solution, if any.

1. Your program must eventually solve any solvable input.
2. **I want to watch you die** -- your program will output the moves and final map of the route to death for *each and every* failed attempt to find a solution.
3. If you encounter a winning solution, print the full output for that and terminate.
4. Run until a solution is found, but *do not attempt the same solution twice* -- all deaths should be by distinct routes.
5. Use this a test input:

(it requires at least one move to drop a water cache at some midpoint).

```
 S........
 .........
 .........
 ........E

```

Shortest code *which is posted with a non-trivial demonstration input which it solves* wins.

# Answer
> 12 votes
# Perl, ~~299 + 1 = 300~~ 254 + 1 = 255 bytes

This will almost certainly be beaten by one of the golfing languages when people see my algorithm :-)

Run with `-n` (1 byte penalty).

The previous version didn't quite comply with the spec because it left extra water on the map and didn't show it in the final version of the map; while changing the algorithm to deal with that situation, I managed to golf it a bit smaller in the process.

```
push@a,[split//];($s,$t)=(length$`,$.)if/S/;($e,$f)=(length$`,$.)if/E/}{$_.=$s<$e?($s++,R):$s>$e?($s--,L):$t<$f?($t++,D):($t--,U);$\=reverse$";$".=y/LRUD/RLDU/r.Y.reverse.($"=~y/Y/X/r);$a[$t-1][$s]=~y/./#/;$\.=$s-$e||$t-$f?redo:$_;print map{join'',@$_}@a

```

Example (I've added line-breaks to the output to avoid the need to scroll and to show the structure):

```
E.....
#.....
#.....
#.....
#####S
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUXDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUUYDDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUYDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUYDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLYRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLYRRRR
 LXR LLXRR LXR LLLYRRR LXR LLYRR LYR LLLLLUUUU
```

In the notation used by the program, movement is represented via `L`, `R`, `U`, and `D` for left, up, right, down respectively. By default, you pick up 1 unit of water after every move, but this can be modified by appending a character:

* `X`: drop 2 units of water, rather than picking 1 up
* `Y`: drop 1 unit of water, rather than picking 1 up
* (i.e. space): completely refill on water (only output after a move to `S`; the program is also output with a leading space, which makes sense because you start full on water)

As you can see, it's possible to cross this (rather barren) map using no extra pools at all. In fact, it's possible to get any distance under these rules, on *any* map, without the help of any preplaced water. As such, this algorithm just ignores any preplaced water, meaning I don't have to waste bytes trying to handle it. This also means that you're not going to see the bot die, sorry. It never moves beyond the range in which it knows it's guaranteed to survive.

The reason we need both `X` and `Y` (and a bit of extra code to ensure we have `X` throughout most of the strategy but the occasional `Y` at the end) is that the spec requires the final version of the map to be output. The easiest way to implement this is to leave the map entirely untouched (apart from our path through initially empty squares), especially as a square which started with `9` water would end up with `10` (breaking the ASCII art) if it happened to be on the path and we only used `X`, and thus we need to find some solution that avoids dropping extra water on the map. The algorithm here would "naturally" drop 1 extra unit of water on each square on the route; as such, the penultimate time we visit each square, we reduce the amount of water dropped by 1 via the use of Y rather than X, so that on our final visit, we drain the square back to its original quantity of water, rather than leaving it slightly wetter than when we started.

I'd recommend against running this on a large map, because it has O(2^n) performance (although the bot never dies of thirst, it's plausible to think it would die of hunger using a strategy like this.)

Readable version:

```
# implicit with -n: read a line of input into $_
push @a, [split //]; #/ split $_ into characters, store at the end of @a
($s,$t) = (length$`,$.) if /S/; # if we see S, store its coordinates
($e,$f) = (length$`,$.) if /E/  # if we see E, store its coordinates
}{ # Due to -n, loop back to start if there are more lines.

# From here onwards, $" stores the partial solution this iteration;
#                    $\ stores the partial solution last iteration;
#                    $_ stores the path from ($s,$t) to S.
# At the start of the program, $" is a space, $\ and $_ are empty.

$_ .=  # Work out the next step on the path:
  $s < $e ? ($s++,R) # if too far left, move right, record that in $_;
: $s > $e ? ($s--,L) # if too far right, move left, record that in $_;
: $t < $f ? ($t++,D) # if too far up,    move down, record that in $_;
: ($t--,U);          # in other cases we must be too far down.
$\ = reverse $";     # Store last iteration; $" is constructed backwards.
$" .=                # Extend $" by appending
  y/LRUD/RLDU/r .    # the path from ($s, $t) back to S;
  Y .                # a literal 'Y';
  reverse .          # $/ backwards (i.e. the path from S to ($s, $t);
  ($"=~y/Y/X/r);     # a copy of $" with all 'Y' changed to 'X'.
$a[$t-1][$s] =~      # At the current path coordinate,
  y/./#/;            # replace any '.' with '#'.
$\ .=                # Start appending to $\;
  $s-$e||$t-$f?redo  # if we're not at E, abort that and jump back to {{,
: $_;                # otherwise append $_ (the path from S to E).
print map            # For each element of some array
  {join'',@$_}       # output its concatenated elements
  @a                 # specifying that array as @a.
# Implicitly: print $\ (which specifies the sort of newline print uses).

```

---
Tags: code-golf, game, search
---


title: Armistice Day Challenge

text:
# Question
Title: Armistice Day Challenge
Today, November 11th, is known as Remembrance Day, Armistice Day, or Veterans Day (depending upon the country), and is a day of reflection and gratitude for members of the military and their service, specifically started to reflect the end of European hostilities in the first World War. Let us reflect on that with a simple ASCII-art output of `11/11`.

Given an input `n`, output an ASCII-art rendition of `11/11` that is `n` units tall. Specifically, each `1` is composed of vertical pipes `||`, the slash is composed of slashes `//`, and each character is two spaces apart. Note that this means varying output widths -- for example, for `n=3` below, see how the "bottom" of the slash is two spaces from the `1` to its left, but is four spaces from the `1` on its right, so that the top of the slash lines up appropriately and is two spaces from the `1` on its right.

```
n = 1
||  ||  //  ||  ||

n = 2
||  ||   //  ||  ||
||  ||  //   ||  ||

n = 3
||  ||    //  ||  ||
||  ||   //   ||  ||
||  ||  //    ||  ||

n = 4
||  ||     //  ||  ||
||  ||    //   ||  ||
||  ||   //    ||  ||
||  ||  //     ||  ||

n = 5
||  ||      //  ||  ||
||  ||     //   ||  ||
||  ||    //    ||  ||
||  ||   //     ||  ||
||  ||  //      ||  ||

```

and so on.

### Input

A single positive integer in any convenient format, `n > 0`.

### Output

An ASCII-art representation of `11/11`, following the above rules and examples. Leading/trailing newlines or other whitespace are optional, provided that the characters line up appropriately.

### Rules

* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# Jelly, 24 bytes

```
⁾| Ḥẋ2µ,Ṛðj
⁶ẋṖ;⁾//ṙḶÇ€Y

```

**TryItOnline!**

### How?

```
⁾| Ḥẋ2µ,Ṛðj - Link 1, join two "11"s with: middle
⁾|          - string literal: "| "
   Ḥ        - double          "||  "
    ẋ2      - repeat twice    "||  ||  "
      µ     - monadic chain separation
       ,    - pair with
        Ṛ   - reversed       ["||  ||  ","  ||  ||"]
         ð  - dyadic chain separation
          j - join with input "||  ||  middle  ||  ||"

⁶ẋṖ;⁾//ṙḶÇ€Y - Main link: n       e.g. 5
⁶            - literal ' '        ' '
 ẋ           - repeat n times     "     "
  Ṗ          - remove last entry  "    "
   ;         - concatenate with
    ⁾//      - literal "//"       "    //"
        Ḷ    - lowered range(n)   [0,1,2,3,4]
       ṙ     - rotate left        ["    //","   // ","  //  "," //   ","//    "]
         Ç€  - call last link (1) as a monad for €ach
           Y - join with line feeds

```
> 4 votes

# Answer
## JavaScript (ES6), 57 bytes

```
n=>" ".repeat(n).replace(/./g,"||  ||  $'//$`  ||  ||\n")

```
> 21 votes

# Answer
# 05AB1E, 24 bytes

```
<ð×„//J¹FD"  ||"2×ÂŠ««,À

```

Try it online!

**Explanation**

```
                          # implicit input n
<ð×                       # push n-1 spaces
   „//J                   # join with "//"
       ¹F                 # input times do:
         D                # duplicate top of stack
          "  ||"2×        # push "  ||  ||"
                  Â       # push "||  ||  "
                   Š      # move the top of the stack down 2 places on the stack
                    ««    # concatenate the top 3 elements of the stack
                      ,   # print with newline
                       À  # rotate top of stack left

```

**Previous 26 byte version**

```
F"||  "2×©ð¹N-<×„//ðN×®RJ,

```

Try it online!
> 7 votes

# Answer
## Perl, 45 bytes

*-9 bytes thanks to @Gabriel Benamy*

47 bytes of code + 1 byte for `-n` flag.

```
say$@="||  "x2,$"x$_,"//",$"x++$.,$@while$_--

```

Run with `-nE` flags :

```
perl -nE 'say$@="||  "x2,$"x$_,"//",$"x++$.,$@while$_--' <<< 5

```
> 6 votes

# Answer
# JavaScript (ES6), ~~88~~ 77 bytes

```
f=(n,i=n)=>i--?`||  ||  ${" ".repeat(i)}//${" ".repeat(n+~i)}  ||  ||
`+f(n,i):""

```

The recursive approach ~~may not be~~ could not possibly be the shortest.

---

`.map` version (88 bytes):

```
n=>[...Array(n)].map((_,i)=>`||  ||  ${" ".repeat(n+~i)}//${" ".repeat(i)}  ||  ||`).join`
`

```

Array comprehension (86 bytes):

```
n=>[for(_ of Array(i=n))`||  ||  ${" ".repeat(--i)}//${" ".repeat(n+~i)}  ||  ||`].join`
`

```

`for` loop version (89 bytes):

```
n=>{for(a="",i=n;i--;a+=s+" ".repeat(i+2)+`//${" ".repeat(n-i+1)+s}
`)s="||  ||";return a}

```

`.replace` version (85 bytes):

```
n=>`||  ||  q  ||  ||
`[r="repeat"](n).replace(/q/g,_=>" "[r](--i)+"//"+" "[r](n+~i),i=n)

```
> 5 votes

# Answer
## Retina, 29 bytes

```
.+
$*
.
xx$'//$`  xx¶
x
||

```

Port of my JavaScript solution. Note the space after `$*` and two spaces after `||`.
> 4 votes

# Answer
# , 30 bytes

```
4i||  2Bi//  Àé XÀ«ñÄf/é Elx

```

Try it online!

As usual, here is a hexdump:

```
0000000: 3469 7c7c 2020 1b32 4269 2f2f 2020 1bc0  4i||  .2Bi//  ..
0000010: e920 58c0 abf1 c466 2fe9 2045 6c78       . X....f/. Elx

```
> 3 votes

# Answer
# Python 2, ~~76~~ ~~75~~ 71 Bytes

Still working on a shorter version, not too bad though.

```
n=input()
k='||  ||'
for i in range(n):print k,(n-i)*' '+'//'+' '*-~i,k

```

<sup>*thanks mbomb007 for catching an error!*</sup>
> 3 votes

# Answer
## Batch, 130 bytes

```
@set s=xx//  xx
@set l=@for /l %%i in (2,1,%1)do @call
%l% set s=%%s://= //%%
%l%:l
:l
@echo %s:x=^|^|  %
@set s=%s: //=// %

```

Not a port of my JavaScript solution. Since `|`s are hard to manipulate in Batch, I use `x`s as placeholders and replace them on output, this conveniently also reduces my code size. Starts by setting `s` to the desired output for `n=1` (`n` is passed on the command line), then inserts spaces as necessary to obtain the first line for the actual value of `n`, then loops through printing the string and shifting the slash left by one character each time.
> 3 votes

# Answer
# **BaCon, 71 bytes**

A complete BASIC program in one line.

```
INPUT n:FOR x=1 TO n:?"||  ||",SPC$(n-x+2),"//",SPC$(x+1),"||  ||":NEXT

```
> 3 votes

# Answer
# Common Lisp, 216 bytes

I'm going to state right off the bat that this is an awful solution to the challenge. Nevertheless, it works, and I'm tired.

```
(defun arm (n) (format t "~{||  || ~v,,,vA//~v,,,vA ||  ||~%~}" (butlast (butlast (butlast (butlast (butlast (butlast (loop for i from 1 to (+ n 1) append `(,(- (+ n 1) i) #\Space #\Space ,i #\Space #\Space))))))))))

```

Usage:

```
* (arm 4)
||  ||     //  ||  ||
||  ||    //   ||  ||
||  ||   //    ||  ||
||  ||  //     ||  ||

```

For some reason, instead of doing anything sane, I decided to approach this with a loop inside a `format` call. This loop iterates through the contents returned by the *other* actual loop construct at the very end, with the last six elements removed (thus the repeated `butlast`s). The contents of the value returned by this loop construct consist of a padding count for the front of the slashes, the padding characters (spaces), the padding count for the back of the slashes, and finally the same padding characters.

I'm rather new to Lisp, and I understand that there is definitely a lot of room for improvement here.
> 3 votes

# Answer
## R, 86 bytes

Just a simple `for` loop approach:

```
x="||  ||";n=scan();for(i in 1:n)cat(x,rep(" ",2+n-i),"//",rep(" ",1+i),x,"\n",sep="")

```
> 2 votes

# Answer
## Retina, 40 bytes

```
.+
x $&$* //  x
;{:`x
||  ||
   //
  //

```

Try it online!

### Explanation

```
.+
x $&$* //  x

```

This turns the input `N` into

```
x S//  x

```

Where `S` corresponds to `N` spaces.

```
;{:`x
||  ||

```

There are two things happening here. `;{:` indicates that this stage and the last one should be run in a loop until they fail to change the string. `:` indicates that the result of this stage should be printed after each iteration and `;` indicates that the final result of the loop (and therefore of the entire program) should *not* be printed. The stage itself just replaces the `x`s with `|| ||` on the first iteration (and does nothing afterwards), so that we now have the first line of the required output (and print it).

```
   //
  //

```

Finally, this shifts the `//` one character to the left, provided there are still at least three spaces left of the `//`. Afterwards we return to the previous stage (which now only prints the current line, since there are no more `x`s) and then repeat.
> 2 votes

# Answer
# Ruby, 60 bytes

```
->n{n.times{|i|puts (a='||  || ')+' '*(n-i)+'//  '+' '*i+a}}

```
> 2 votes

# Answer
# C, ~~116 94~~ 89 bytes

```
c,d;f(a){for(d=a;a--;puts("  ||  ||"))for(c=-1;c<d;)printf(a-c++?c?" ":"||  ||  ":"//");}

```

Try it out on Ideone
> 2 votes

# Answer
# Ruby, ~~76~~ ~~74~~ 73 bytes

```
x="||  ||";n=gets.to_i;puts (1..n).map{|i|x+" "*(n-i+2)+"//"+" "*(i+1)+x}

```

As a function it takes ~~73~~ 72 bytes, counting the definition:

```
def f n,x="||  ||";(1..n).map{|i|x+" "*(n-i+2)+"//"+" "*(i+1)+x}*?\n;end

```
> 1 votes

# Answer
# Powershell, 66 bytes

```
$a=read-host;1..$a|%{$s="||  ";$s*2+" "*($a-$_)+"// "+" "*$_+$s*2}

```
> 1 votes

# Answer
# C#, 150 Bytes

Golfed:

```
string A(int n){string a="",b= "||  ||";for(int i=0;i<n;i++)a+=b+"  //  ".PadLeft(5+n-i,'\0')+string.Concat(Enumerable.Repeat(" ",i))+b+"\n";return a;

```

Ungolfed:

```
public string A(int n)
{
  string a = "", b = "||  ||";
  for (int i = 0; i < n; i++)
    a += b + "  //  ".PadLeft(5 + n - i, '\0') + string.Concat(Enumerable.Repeat(" ", i)) + b + "\n";
  return a;
}

```

Testing:

```
Console.WriteLine(new ArmisticeDayChallenge().A(11));

```

Output:

```
||  ||            //  ||  ||
||  ||           //   ||  ||
||  ||          //    ||  ||
||  ||         //     ||  ||
||  ||        //      ||  ||
||  ||       //       ||  ||
||  ||      //        ||  ||
||  ||     //         ||  ||
||  ||    //          ||  ||
||  ||   //           ||  ||
||  ||  //            ||  ||

```
> 1 votes

# Answer
# Groovy, 63 chars/bytes

Here's my attempt with Groovy, using an anonymous closure and simple loops to print the ASCII art to standard output:

`{n->n.times{println'|| '*2+' '*(n-it-1)+'//'+' '*it+' ||'*2}}`

You can try it online here. Just click "Edit in console" and then "Execute script".

Trying to do the same and returning a string instead of printing, I couldn't get below 71 bytes:

`{n->a='';n.times{a+='|| '*2+' '*(n-it-1)+'//'+' '*it+' ||'*2+'\n'};a}`
> 1 votes

# Answer
# Python 3, 78 bytes

```
a="||  ||"
def m(n):
    for e in range(n):print(a," "*(n-e),"//"," "*(e+1),a)

```

Still trying to shorten...
> 0 votes

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


# Question
Title: Probability of All Combinations of Given Events
Given a sequences of events with probabilities between 0.0 and 1.0, generate and derive the probability of each combination occurring. You may presume that a sequence of numbers is provided in whatever construct your chosen language provides.

Here's an example; you may presume that the length of the sequence's combinations fit into memory:

```
{ 0.55, 0.67, 0.13 }

```

The program shall print each combination and the associated probability of that sequence occurring. A 1 shall denote that the event in that index of the input sequence occurred and a 0 shall denote that that event did not occur. The desired output is below (I don't care about printing the work, that's just for informational purposes of the algorithm):

```
[0,0,0] = (1 - 0.55) * (1-0.67) * (1-0.13) = 0.129195
[0,0,1] = (1 - 0.55) * (1-0.67) * (0.13)   = 0.019305
[0,1,0] = (1 - 0.55) * (0.67)   * (1-0.13) = 0.262305
[0,1,1] = (1 - 0.55) * (0.67)   * (0.13)   = 0.039195
[1,0,0] = (0.55)     * (1-0.67) * (1-0.13) = 0.157905
[1,0,1] = (0.55)     * (1-0.67) * (0.13)   = 0.023595
[1,1,0] = (0.55)     * (0.67)   * (1-0.13) = 0.320595
[1,1,1] = (0.55)     * (0.67)   * (0.13)   = 0.047905

```

This problem is tangentially related to calculating a "Cartesian product".

Remember, this is code-golf, so the code with the fewest number of bytes wins.

# Answer
> 8 votes
## Haskell, 86 bytes

```
unlines.map(\p->show(fst<$>p)++" = "++show(product$snd<$>p)).mapM(\x->[(0,1-x),(1,x)])

```

Usage example:

```
Prelude> putStrLn $ unlines.map(\p->show(fst<$>p)++" = "++show(product$snd<$>p)).mapM(\x->[(0,1-x),(1,x)]) $ [0.55, 0.67, 0.13]
[0,0,0] = 0.12919499999999998
[0,0,1] = 1.9304999999999996e-2
[0,1,0] = 0.262305
[0,1,1] = 3.9195e-2
[1,0,0] = 0.157905
[1,0,1] = 2.3595e-2
[1,1,0] = 0.320595
[1,1,1] = 4.790500000000001e-2

```

Most of the bytes are spent for output formatting. If you are only interested in the probability vector it's only 29 bytes:

```
map product.mapM(\x->[1-x,x])

```

How it works:

```
                    mapM(\x->[(0,1-x),(1,x)])   -- for each number x in the input
                                                -- list make either the pair (0,1-x)
                                                -- or (1,x). Build a list with
                                                -- all combinations

    map(\p->                    )               -- for each such combination p
          show(fst<$>p)                         -- print the first elements
          ++" = "++                             -- then the string " = "
          show(product$snd<$>p)                 -- then the product of the second
                                                -- elements

unlines                                         -- joins with newlines

```

# Answer
> 5 votes
# Mathematica, ~~46~~ 45 bytes

```
(s=#;1##&@@Abs[#-s]&/@{1,0}~Tuples~Length@s)&

```

Takes a list. Even works for the empty list `{}`, for which the output is `{1}`.

## Test case:

```
%[{0.55, 0.67, 0.13}]
{0.129195, 0.019305, 0.262305, 0.039195, 0.157905, 0.023595, 0.320595, 0.047905}

```

## Explanation

Given a list of probabilities `s` and a list of bits `b` with `0` denoting "did not occur" and `1` denoting "did occur", the list of probabilities to be multiplied is given by

```
1 - b - s

```

up to sign. If instead `0` denotes "did occur" and `1` "did not occur", then this simplifies to

```
b - s

```

so we:

```
                      {1,0}~Tuples~Length@s   (* Generate all possible bit combinations *)
              (#-s)&/@{1,0}~Tuples~Length@s   (* Generate probabilities to be multiplied
                                                  up to sign *)
     1##&@@Abs[#-s]&/@{1,0}~Tuples~Length@s   (* Correct sign and multiply;
                                                 1##& is short for Times *)
(s=#;1##&@@Abs[#-s]&/@{1,0}~Tuples~Length@s)& (* Assign s to first argument of function,
                                                 done separately to avoid clash
                                                 with inner function *)

```

# Answer
> 4 votes
# MATL, ~~12~~ 11 bytes

```
TF-|Z}&Z*!p

```

Input is a column vector, with the format `[0.55; 0.67; 0.13]`

Try it online!

```
TF    % Push [1, 0]
-     % Subtract from implicit input (column array), with broadcast. Gives a 2-col
      % matrix where the first column is the input minus 1 and the second is the input
|     % Absolute value
Z}    % Split the matrix into its rows
&Z*   % Cartesian product of all resulting. This gives a matrix as result, with each
      % "combination" on a different row
!p    % Product of each row. Implicitly display

```

# Answer
> 4 votes
# Perl, ~~42~~ 40 bytes

Includes +1 for `-a`

Give numbers on STDIN:

```
perl -M5.010 combi.pl <<< "0.55 0.67 0.13"

```

outputs

```
0.129195
0.019305
0.262305
0.039195
0.157905
0.023595
0.320595
0.047905

```

`combi.pl`:

```
#!/usr/bin/perl -a
$"=")\\*({1-,}";say eval for<({1-,}@F)>

```

# Answer
> 3 votes
# Perl, 116 bytes

```
for(glob"{0,1}"x(@a=split/ /,<>)){@c=split//;$d=1;$d*=@c[$_]?$a[$_]:1-$a[$_]for 0..$#a;say"[".join(",",@c)."] = $d"}

```

Readable:

```
for(glob"{0,1}"x(@a=split/ /,<>)){
    @c=split//;
    $d=1;$d*=@c[$_]?$a[$_]:1-$a[$_]for 0..$#a;
    say"[".join(",",@c)."] = $d"
}

```

Creates a list of all possible combinations of 0s and 1s of length equal to the number of input parameters (e.g., for the example above, it would be of length 3), then calculates each probability.

Thanks to @Dada for showing me what the `glob` function *can* do, even though I'm not 100% sure I understand *how* it does that.

Sample output:

```
[0,0,0] = 0.129195
[0,0,1] = 0.019305
[0,1,0] = 0.262305
[0,1,1] = 0.039195
[1,0,0] = 0.157905
[1,0,1] = 0.023595
[1,1,0] = 0.320595
[1,1,1] = 0.047905

```

# Answer
> 3 votes
# R, 72 69 bytes

Takes input from stdin and returns an R-vector of probabilities.

```
apply(abs(t(expand.grid(rep(list(1:0),length(x<-scan())))-x)),1,prod)

```

Edit: Removed one unnecessary transpose, the permutation matrix is now the transposed version of the one below and the probabilities are calculated as the column-wise product rather than row-wise. **Example output:**

```
[1] 0.129195 0.157905 0.262305 0.320595 0.019305 0.023595 0.039195 0.047905

```

Note that the probabilities are in a different order due to the fact that the permutation-matrix generated by `expand.grid` produces the following (generation of this matrix can probably be golfed using external packages):

```
1    1    1    1
2    0    1    1
3    1    0    1
4    0    0    1
5    1    1    0
6    0    1    0
7    1    0    0
8    0    0    0

```

The first probability corresponds to the inverted outcome of the first row in the above matrix and the second to the inverted second row etc. Formatting output to see this even more clearly makes the program longer (164 bytes):

```
m=expand.grid(rep(list(1:0),length(x<-scan())))
cat(paste0("[",apply(abs(m-1),1,function(x)paste0(x,collapse=",")),"] = ",apply(abs(t(t(m)-x)),1,prod),"\n"),sep="")

```

which instead produces:

```
[0,0,0] = 0.129195
[1,0,0] = 0.157905
[0,1,0] = 0.262305
[1,1,0] = 0.320595
[0,0,1] = 0.019305
[1,0,1] = 0.023595
[0,1,1] = 0.039195
[1,1,1] = 0.047905

```

# Answer
> 2 votes
# J, 14 bytes

```
-.([:,*/)/@,.]

```

## Usage

```
   f =: -.([:,*/)/@,.]
   f 0.55 0.67 0.13
0.129195 0.019305 0.262305 0.039195 0.157905 0.023595 0.320595 0.047905

```

## Explanation

```
-.([:,*/)/@,.]  Input: array P
-.              Complement (1-x) for each x in P
             ]  Identity, get P
           ,.   Interleave to make pairs [(1-x), x]
  (     )/@     Reduce from right-to-left by
      */          Forming the multiplication table
   [:,            Flattening the result

```

# Answer
> 2 votes
# Jelly, 9 bytes

```
ż@C×þF¥@/

```

Try it online!

# Answer
> 2 votes
# Pyth, 10 bytes

```
*MaVLQ^U2l

```

Try it online: Demonstration

### Explanation:

```
*MaVLQ^U2lQ   implicit Q at the end (Q = input list)
      ^U2lQ   repeated Cartesian product of [0, 1] with itself length(Q)-times
              this gives all combinations of 0s and 1s
  aVLQ        absolute difference between these 0-1-vectors with Q
*M            fold the vectors by multiplication

```

# Answer
> 1 votes
## JavaScript (Firefox 30-57), 57 bytes

```
f=([p,...a])=>1/p?[for(q of[1-p,p])for(b of f(a))q*b]:[1]

```

Returns an array of all the probabilities. If you want the array of events too, then for 86 bytes:

```
f=([p,...a])=>1/p?[for(e of'01')for(b of f(a))[[+e,...b[0]],(+e?p:1-p)*b[1]]]:[[[],1]]

```

If you're allowed the events as a string, then it's only 80 bytes:

```
f=([p,...a])=>1/p?[for(e of'01')for(b of f(a))[e+b[0],(+e?p:1-p)*b[1]]]:[['',1]]

```

Subtract two bytes for `1/` for each solution if the probability is never going to be zero.

# Answer
> 1 votes
# C, 110 bytes

```
i,k;f(float* a,int n){for(k=0;k<1<<n;++k){float p=1;for(i=0;i<n;++i)p*=k&(1<<i)?a[i]:1-a[i];printf("%f,",p);}}

```

Ungolfed:

```
i,k;f(float* a,int n){
 for(k=0; k<1<<n; ++k){
  float p=1;
  for (i=0; i<n; ++i)
   p*=k&(1<<i)?a[i]:1-a[i];
  printf("%f,",p);
 }
}

```

Works up to 32 items, +5+1 bytes for 64 items (declare `long k;` and add `L` in the first loop so that `k<1L<<N`).

# Answer
> 1 votes
# 05AB1E, 8 bytes

```
<Äæ¹æR+P

```

Try it online!

```
 <Äæ¹æR+P  # Main link (Input is [.1,.2])
 ###########
 <Ä        # Invert input, take the abs value.
           # Stack is [.9,.8]
   æ¹æ     # Powerset of both inverted and original arrays.
           # Stack is [[],[.1],[.2],[.1,.2]],[[],[.9],[.8],[.9,.8]]
      R+   # Reverse original array, add arrays together.
           # Stack is [.9,.8],[.1,.8],[.2,.9],[.1,.2]
        P  # For each sub array, push product.
           # Final Result: [0.02, 0.18, 0.08, 0.72]
           # E.G.          [  11,   10,   01,   00]

```

# Answer
> 0 votes
# PHP, ~~105~~ ~~97~~ ~~94 93~~ 87 bytes

```
for(;$i<2**$c=count($a=$argv)-$p=1;$i+=print-abs($p))for(;$c;)$p*=$a[$c--]-!($i>>$c&1);

```

Run like this:

```
php -r 'for(;$i<2**$c=count($a=$argv)-$p=1;$i+=print-abs($p))for(;$c;)$p*=$a[$c--]-!($i>>$c&1);' -- .55 .67 .13 2>/dev/null;echo
> -0.129195-0.157905-0.262305-0.320595-0.019305-0.023595-0.039195-0.047905

```

Note that the output is little endian:

```
[0,0,0]
[1,0,0]
[0,1,0]
[1,1,0]
[0,0,1]
[1,0,1]
[0,1,1]
[1,1,1]

```

# Explanation

```
for(
  ;
  $i<2**$c=                 # Iterate over possible combinations: 2^c,
    count($a=$argv)-$p=1;   #   where c is input length -p (set p to 1)
  $i+=print-abs($p)         # Increment i and print product after each
)                           #   iteration, dash separated
  for(
     ;
     $c;                    # Iterate over input ($c..0)
  )
    $p*=                    # Multiply the product by difference between:
      $a[$c--]-             # - The $c-th item of the input.
      !($i>>$c&1);          # - The $c-th bit of `$i`, negated (1 or 0)

```

# Tweaks

* Saved 8 bytes by using binary logic to get bit instead of converting to string
* Saved a byte by combining the resetting of `$p` to 1 with computation of `$c`
* Saved a byte by adding the result of print (1) to `$i` instead of incrementing
* Saved a byte by using underscore as output delimiter
* Saved a byte by using minus sign as delimiter (there are no negative chances).
* Saved 6 bytes by using `$c` instead of `$$i`

# Answer
> 0 votes
# Perl 6, ~~24~~ 19 bytes of Latin-1

```
{[*] 1 «-»@_ «|»@_}

```

Older code:

```
{[*] map {1-$^a|$^a},@_}

```

This is a function. Use it like this:

```
{[*] 1 «-»@_ «|»@_}(0.55, 0.67, 0.13)

```

to get:

```
any(any(any(0.129195, 0.019305), any(0.262305, 0.039195)), any(any(0.157905, 0.023595), any(0.320595, 0.047905)))

```

Explanation of the older code:

```
[*]          multiply together all array elements
map          but first transform each element via
{1-$^a|$^a}  considering both 1 minus the value and the value
,@_          of the function input

```

The newer code is basically the same, just using terser syntax:

```
[*]          multiply together all array elements
1 «-»@_      of the array formed by subtracting the argument from 1
«|»@_        pointwise considering both that and the original array

```

The map generates an array full of `any` constructs, which multiply into larger `any` constructs, neatly solving the problem without even needing a loop.

Not the shortest language for the program, but it's a very direct translation of the problem.

# Answer
> 0 votes
# C++17, ~~137~~ ~~131~~ 129 bytes

Saving 6 bytes by declaring `#define A auto`, first time that such a short macro saves anything. -2 bytes for using `#import` and deleting the space before `<`

```
#import<iostream>
#define A auto
A g(A r){std::cout<<r<<",";}A g(A r,A x,A...p){g(x*r,p...);g(r-x*r,p...);}A f(A...p){g(1,p...);}

```

Spawns all possible combinations.

Ungolfed:

```
//base case to print the result
int g(auto r){std::cout << r << ",";}

//extract item from parameter pack
int g(auto r, auto x, auto... p) {
 g(x*r,p...);    //multiply with temp result and call with tail
 g(r-x*r,p...);  //same as above for (1-x)
}

//start of recursion, setting temp result to 1
int f(auto...p){g(1,p...);}

```

Usage:

```
f(0.55, 0.67, 0.13);

```

# Answer
> 0 votes
# Dyalog APL, 10 bytes

## New Solution

Index origin independent. Anonymous function. Takes probabilities list as argument.

```
∘.×/⊢,¨1-⊢

```

`∘.×/` The Cartesian product reduction over

the argument values

each paired up with

`1-⊢` the complement argument values (lit. one minus the argument values)

TryAPL online!

---

## Old Solution

Requires `⎕IO←0` which is default on many systems. Prompts for probabilities' list.

```
|⎕∘.×.-⊂⍳2

```

### Explanation

`|` absolute value of

the input, ***ɑ*** = \[***ɑ***₁ ***ɑ***₂ ***ɑ***₃\]

`∘.×.-` modified inner tensor multiplied, (***ɑ***₁ – ***b***₁) ⊗ (***ɑ***₂ – ***b***₂) ⊗ (***ɑ***₃ – ***b***₃), with

`⊂⍳2` the enclosed list ***b*** = \[\[0 1\]\]

### Mathematical definition

As ***b*** is enclosed, it is scalar, and therefore extended to the length of ***ɑ***, namely 3, so the entire expression is
**A** = │(***ɑ***₁ – ***b***) ⊗ (***ɑ***₂ – ***b***) ⊗ (***ɑ***₃ – ***b***)│ =
│(***ɑ***₁ – \[0,1\]) ⊗ (***ɑ***₂ – \[0,1\]) ⊗ (***ɑ***₃ – \[0,1\])│ =
│\[***ɑ***₁,***ɑ***₁ – 1\] ⊗ \[***ɑ***₂, ***ɑ***₂ – 1\] ⊗ \[***ɑ***₃,***ɑ***₃ – 1\]│ =
⎢ ⎡ ⎡ ***ɑ******ɑ******ɑ***₃ ⎤ ⎡ ***ɑ******ɑ***₂(***ɑ***₃-1) ⎤ ⎤ ⎥
⎢ ⎢ ⎣ ***ɑ***₁(***ɑ***₂-1)***ɑ***₃ ⎦ ⎣ ***ɑ***₁(***ɑ***₂-1)(***ɑ***₃-1) ⎦ ⎥ ⎥
⎢ ⎢ ⎡ (***ɑ***₁-1)***ɑ******ɑ***₃ ⎤ ⎡ (***ɑ***₁-1)***ɑ***₂(***ɑ***₃-1) ⎤ ⎥ ⎥
⎢ ⎣ ⎣(***ɑ***₁-1)(***ɑ***₂-1)***ɑ***₃⎦ ⎣(***ɑ***₁-1)(***ɑ***₂-1)(***ɑ***₃-1)⎦ ⎦ ⎥

TryAPL online!

## Notes (applies to both old and new solution)

The program and formula works for any number (*n*) of variables, and returns an *n*-dimensional array of length 2 in every dimension. With three variables, the probability of a specific outcome
*P*(*p*,*q*,*r*) = **A**<sub>*p*,*q*,*r*</sub>
which can conveniently be selected from the array with `(⊃A)[p;q;r]` extracted with `p q r⌷⊃A`

E.g. `1 1 0⌷⊃|0.55 0.67 0.13∘.×.-⊂⍳2` gives *P*(55%, 67%, ¬13%) = 1.9305%

---
Tags: code-golf, probability-theory
---


title: A simple number system

text:
# Question
Title: A simple number system
Let me tell you about a simple number system. (which I made up just for this challenge)

This system contains the functions `()`, `[]`, `{}`, and `<>`.

## 1. `()`

When `()` is given no arguments, it evaluates to `0`.

When `()` is given one or more arguments, it evaluates to the sum of the arguments.

## 2. `[]`

When `[]` is given no arguments, it evaluates to `-1`.

When `[]` is given one or more arguments, it evaluates to the first argument minus the sum of the other arguments.

# 3. `{}`

When `{}` is given no arguments, it evaluates to `1`.

When `{}` is given one or more arguments, it evaluates to the product of those arguments.

# 4. `<>`

When `<>` is given no arguments, it evaluates to `1`.

When `<>` is given one or more arguments, it evaluates to the first argument integer divided by the product of the other arguments.

## Your task

Given a string that contains a valid number (that means brackets are balanced, no division by 0s, etc.) in this simple number system, print its value.

## Test cases

```
() -> 0
(()()) -> 0
([][]) -> -2
({}<>) -> 2
({}[]) -> 0
[] -> -1
[[][]] -> 0
[()<>] -> -1
{()} -> 0
{([]<>)} -> 0

```

Remember, this is , so the code with the fewest bytes wins.

# Answer
> 2 votes
# Dyalog APL, 94 bytes

`o←{(⊂(1⊃⍵),⍺⍺⊃⍵),2↓⍵}⋄u←{(⊃⍵,⍺⍺1)⍺⍺⍵⍵/1↓⍵}⋄⍎⍕'+/o' '-u+o' '×/o' '÷u×o' '(⊂⍬),'[')]}>'⍳⌽⍞],'⊂⍬'`

uses `⎕IO←0`

replaces `)]}>` with a function call that takes a stack, applies an operation on its top frame, deletes it, and appends the result to its next frame (monadic operator `o` is used for that; dyadic operator `u` handles the more complicated cases of `-` and `÷`)

replaces `([{<` with code that adds a frame to the stack (`(⊂⍬),`)

executes the resulting expression (reversed, to match APL's order of execution) with an initial stack of one empty frame (`⊂⍬`)

# Answer
> 5 votes
# Haskell, ~~357~~ ~~306~~ ~~277~~ ~~251~~ ~~228~~ ~~224~~ ~~188~~ ~~185~~ 180 bytes

A token-based parser with an explicit stack. `(%)` takes a token stack and a character and either pushes (opcode,defaultnumber) or (0,number) for `({[<`, or pops topmost numbers and one opcode and pushes the answer for `)}]>`. Opcodes are encoded by a ascii enumeration hack.

Kudos to @ChristianSievers for his great answer that I borrowed some ideas from.

One-liner!

```
s%c|elem c"([<{",g<-div(fromEnum c)25=(g,[0,0,1,-1,1]!!g):s|(a,(o,n):b)<-span((==0).fst)s=(0,[foldr1(flip$[(+),quot,(-),(*)]!!(o-1))$snd<$>a,n]!!(0^length a)):b
snd.head.foldl(%)[]

```

Now with less error-handling! Usage:

```
*Main> map (snd.head.foldl(%)[]) ["()","(()())","([][])","({}<>)","({}[])","[]","[[][]]","[()<>]","{()}","{([]<>)}"]
[0,0,-2,2,0,-1,0,-1,0,0]

```

Thanks @ChristianSievers for saving 14+3 bytes!

Thanks @Zgarb for saving some+4 bytes!

# Answer
> 3 votes
# PEG.js (ES6), 132 bytes

```
x=a:[([{<]b:x*[)\]}>]{var x='([<'.indexOf(a)
b.length^1||b.push(0)
return~~eval(b.length?b.join(('+-/'[x]||'*')+' '):~-('10'[x]||2))}

```

Should be fixed now.

# Explanation

More readable:

```
x=a:[([{<]
  b:x*
  [)\]}>]
{
  var x='([<'.indexOf(a)
  b.length^1||b.push(0)
  return ~~eval(
    b.length?
      b.join(('+-/'[x]||'*')+' ')
    :~-('10'[x]||2))
  )
}

```

PEG.js is an extended version of Javascript specifically made for parsing. It's VERY strict, which is why I had to use `var`. In addition, there seems to be a bug with brackets inside strings, which bloated the code significantly.

To start, we define a rule `x` that matches any bracket `a` that may or may not contain multiple expressions that matches rule `x`.

For each match to rule `x`, we push a 0 to the array of the inner match `b` if `b`'s length is 1.

If `b`'s length \> 0, then we find the index of `a` in `([<` and get a character from `+-/` using that index. If the result is undefined (meaning that `a` was `{`), then we turn the result into `*`. Finally, we tack on a space and join `b` with the result.

If `b`'s length = 0, then we find the index of `a` in `([<` and get a character from `10` using that index. If the result is undefined (meaning that `a` was `{` or `<`), then we turn the result into 2. Finally, we simply decrement.

At the end, we can just evaluate the expression and floor the result.

# Answer
> 3 votes
# Python 2, ~~292~~ ~~265~~ ~~248~~ ~~235~~ ~~223~~ ~~206~~ 204 bytes

```
r=reduce
s=input()
for n in')]}>':s=s.replace(n,'),')
for a in'(*x:sum(x)','[a=-1,*x:a-sum(x)','{*x:r(int.__mul__,x,1)','<a=1,*x:r(int.__div__,x,a)':s=s.replace(a[0],'(lambda %s)('%a[1:])
print eval(s)[0]

```

Replaces all brackets with a lambda that does what the bracket does, then evaluates the resulting Python code. Requires its input surrounded by quotes, like `'[<><>([]{})]'`.

This program stores the type of bracket as the first character in each string in the `for`, and everything after the keyword `lambda` as the rest. It then uses the first character to substitute; the rest of it is combined into a lambda like `(lambda*x:sum(x))()`.

Try it on Ideone!

# Answer
> 3 votes
# Perl, 113 + 2 = 115 bytes

Run with `-lp` (2 byte penalty).

```
/\W/,eval"sub $`\{\$#_?(shift)$&&$'1}"for qw'a+a:1- b-a:- c*c: d/c:';y/([{</a-d/;s/\W/0),/g;s/\pL\K/(/g;$_=eval

```

More readable (note: this "more readable version" won't actually run, because I put comments in places they aren't syntactically allowed):

```
              # -p option: read a line of input into $_ at program start
              # -l option: remove the final newline whenever reading
do {          # for each element of a list, given later:
  /\W/;       # place an initial identifier in $`, the next character in
              # $&, and the rest of the element in $'
  eval qq{    # then evaluate the following template, with substitutions:
    sub $` {  # define a subroutine named $`, that does this:
      \$#_ ?  # if there is more than one argument
      (shift) # then return the first argument $&-ed with
      $& &$'  # the result of a recursive call with the tail of the arguments
              # else (the "else" is a colon taken from $', not the template)
      1       # return (the remainder of $' applied to) 1
    }
  }
} for qw'     # specify the list by splitting the following on whitespace:
  a+a:1-      # a(head,tail) = len(tail>1) ? head+a(tail) : 1-1
  b-a:-       # b(head,tail) = len(tail>1) ? head-a(tail) : -1
  c*c:        # c(head,tail) = len(tail>1) ? head*c(tail) : 1
  d/c:        # d(head,tail) = len(tail>1) ? head/c(tail) : 1
';
y/([{</a-d/;  # replace ( [ { < with a b c d in $_
s/\W/0),/g;   # replace whitespace, punctuation in $_ with the string "0),"
s/\pL\K/(/g;  # place a ( after (\K) each letter (\pL) in $_
$_=eval       # evaluate $_ as a Perl program, storing the result back in $_
              # -p option: print $_ to the user at program end
              # -l option: output a newline whenever printing

```

The basic idea is that we're converting an input like `[()<>]` to the Perl program `b(a(0),d(0),0),` via text processing; Perl's just fine with the trailing comma. Earlier, we defined the functions `a`, `b`, `c`, `d` to have the same effect as the `()`, `[]`, `{}`, `<>` constructs from the language we're implementing; they each disregard their last argument (the 0 at the end), which is included to ensure that all input parses correctly, and work using the implementation commonly seen in functional programming where the head and tail are processed separately. Because `b(e,f,g,0)` means `e-f-g`, i.e. treats its first argument specially, whereas `a` treats its arguments symmetrically (`a(e,f,g,0)` means `e+f+g`), we implement `a` recursively and `b` via calling `a`. `c` and `d` have a similar relationship. All four of these functions are very similar, so we generate them at runtime rather than implementing them separately; we store a template that applies to all four functions in a string, then generate the functions by substituting characters into the template.

Because Perl `/` does floating-point division, the implemented `{}` does too. I'm assuming that either this is not a problem in its own right, or `-Minteger` (selecting a language variant where all arithmetic operations are integer operations) is free, because otherwise I'd have to spend extra bytes writing an integer division in Perl, which doesn't seem to be what the problem is fundamentally about. (I think you'd have to spend four bytes changing `(shift)` to `int+(shift)`; I haven't tested this.)

# Answer
> 2 votes
# Octave, ~~215~~ ~~206~~ 198 bytes

```
S='sum(x(:))-sum(x(2:end))';Y='(@(x)isempty(x)';c=']) ';[~,~,u]=unique(['()<>[]{}',input('')]);eval([{'sum([',c,[Y,'+fix((',S,')/prod(x(2:end))))(['],c,[Y,'*-1+',S,'*2)(['],c,'prod([',c}{u(9:end)}])

```

try it online

# Answer
> 2 votes
# PHP, ~~315~~ ~~300~~ ~~285~~ ~~258~~ ~~250~~ 244 bytes

```
for($s=$argv[1];$r=!$r;)foreach(["(+)1","[-]0","{*}2","</>2]as$p)if(preg_match("#$e$p[0]([-_\d]*)$e$p[2]#",$s,$m)){if(""==$v=strtok($m[1],_))$v=$p[3]-1;while(""<$n=strtok(_))eval("\$v$p[1]=$n;");$s=strtr($s,[$m[$r=0]=>_.$v]);}echo substr($s,1);

```

replaces sub-expressions with underscore+value; loop breaks when iteration made no replacement.

19 years since I first met C, 17 years working with PHP;
this is the first time that `strtok` makes sense ... helping to save 24 bytes!

**breakdown**

```
for($s=$argv[1];    // take input from argument
    $r=!$r;)        // toggle $r; loop until no replacement has taken place
    foreach(["(+)1","[-]0","{*}2","</>2]as$p) // loop through operations
        if(preg_match("#$e$p[0]([-_\d]*)$e$p[2]#",$s,$m))   // find a match
        {
            if(""==$v=strtok($m[1],_))  // init $v with first token from sub-match
                $v=$p[3]-1;             // if no token, init with default value
            while(""<$n=strtok(_))      // loop through tokens
                eval("\$v$p[1]=$n;");       // operate
            $s=strtr($s,[$m[$r=0]=>_.$v]);  // reset $r; replace match with underscore+value
        }
echo substr($s,1);  // print result

```

# Answer
> 2 votes
# ES6 (Javascript), ~~250~~, ~~171~~, ~~154~~, ~~149~~, 147 bytes

A pure Javascript version.

"Metaprogramming" (like most other answers here), converts input program text into a corresponding Javascript program, by applying a number of direct text substitutions to it (i.e. keeping the program structure as is).

Can probably be golfed further.

*UPDATE (v2.1)*

* Minus two bytes (removed parenthesis in the ternary expression)
* Golfed 5 more bytes off, by using variable for result extraction, and getting rid of extra "\[\]"

*UPDATE (v2)*

Just realised that pending commas in ES arrays are totally valid, so the whole comma normalization code could be removed. Also followed an excellent advice by @Titus, on optimizing the alphabet lookup.

*UPDATE (v1)*

Removed duplicate "replace" alias.

*UPDATE (v1)*

* Use a better alphabet: ()=\>1+ \[\]=\>0 {}=\>2\* \<\>=\>2/ (each char can be directly re-used as a value or operator)
* Replaced reduce() with replace() (alphabet mapping)
* Merged constant inlining, open and closing bracket processing into one step

**Golfed (v2.1)**

```
s=>eval("o="+s.replace(/./g,r=>"2+1-3*3/"["()[]{}<>".indexOf(r)]).replace(/\d\D?|\D/g,r=>r[1]?r[0]-2+",":r*1?'([':`].reduce((r,a)=>r${r}a)),`)+"o

```

**Golfed (v1)**

```
(s,A="(2)+[1]-{3}*<3>/")=>eval(s[R="replace"](/./g,r=>A[A.indexOf(r)+1])[R](/\d\D?|\D/g,r=>r[1]?r[0]-2+",":(r[0]*1?'([':`].reduce((r,a)=>r${r}a)),`))[R](/,(\])|,$/g,"$1"))

```

**Golfed (v0)**

```
([...s],A="(a)b[c]d{e}f<g>h",R="replace")=>eval(s.reduce((r,c)=>r+=A[A.indexOf(c)+1],'')[R](/ab|cd|ef|gh/g,r=>({d:-1,b:'0'}[r[1]]||1) + ',')[R](/[aceg]/g,"([")[R](/[bdfh]/g,r=>`].reduce((r,a)=>r${"+*-/"["bfdh".indexOf(r)]}a)),`)[R](/,(\])|,$/g,"$1"))

```

**Explained (v0)**

```
//BEGIN

//s - input text, A - alphabet, R - "String.replace()" alias
E=([...s],A="(a)b[c]d{e}f<g>h",R="replace")=>eval(

//Replace input alphabet by a more friendly one, to avoid too much escaping and quoting
// () - ab, [] -cd, {} - ef, <> - gh
s.reduce((r,c)=>r+=A[A.indexOf(c)+1],'')

//Replace no-arg invocations with a corresponding constant value
// () => 0, [] => -1, {} => 1, <> => 1
[R](/ab|cd|ef|gh/g,r=>({d:-1,b:'0'}[r[1]]||1) + ',')

//Replace opening brackets with "(["
[R](/[aceg]/g,"([")

//Replace closing brackets with "].reduce(...)),"
//An arithmetic operation to apply (+-*/) is chosen based on the bracket type
//and is substituted into the template
[R](/[bdfh]/g,r=>`].reduce((r,a)=>r${"+*-/"["bfdh".indexOf(r)]}a)),`)

//Strip excessive commas
[R](/,(\])|,$/g,"$1")
);

//END: eval() the result

Example:
E("{([]<>()<>{})(<><>)}")
=> eval("([([-1,1,0,1,1].reduce((r,a)=>r+a)),([1,1].reduce((r,a)=>r+a))].reduce((r,a)=>r*a))")
=> 4

```

**Test**

```
E=([...s],A="(a)b[c]d{e}f<g>h",R="replace")=>eval(s.reduce((r,c)=>r+=A[A.indexOf(c)+1],'')[R](/ab|cd|ef|gh/g,r=>({d:-1,b:'0'}[r[1]]||1) + ',')[R](/[aceg]/g,"([")[R](/[bdfh]/g,r=>`].reduce((r,a)=>r${"+*-/"["bfdh".indexOf(r)]}a)),`)[R](/,(\])|,$/g,"$1"))

T=(s,a)=>{
    console.log(s,r=E(s),r==a?"OK":"NOT OK");
}

T("()",0)
T("(()())",0)
T("([][])",-2)
T("({}<>)",2)
T("({}[])",0)
T("[]",-1)
T("[[][]]",0)
T("[()<>]",-1)
T("{()}",0)
T("{([]<>)}",0)

```

**Test Output**

```
() 0 OK
(()()) 0 OK
([][]) -2 OK
({}<>) 2 OK
({}[]) 0 OK
[] -1 OK
[[][]] 0 OK
[()<>] -1 OK
{()} 0 OK
{([]<>)} 0 OK

```

# Answer
> 2 votes
## Haskell, ~~184 179 172 161 160 159 151 148~~ 145 bytes

```
s%(c:i)|elem c")}]>"=([1?(*),sum,1?quot,(-1)?(-)]!!mod(fromEnum c)5$s,i)|(r,j)<-[]%i=(s++[r])%j
[v]%e=(v,e)
(v?_)[]=v
(_?o)s=foldl1 o s
fst.([]%)

```

Recursive descent, threading the input because Haskell. As usual, the last line is not a definition, but states the function that solves the problem. So to test, put the lines except the last one in a file, load it and do something like this:

```
*Main> fst.([]%) $ "{([][][])([][])}"
6

```

Thanks to @Zgarb for inspiration and a lot of detailed hints, and to @Angs for inspiration from his solution and further hints.

It wasn't specified how division should behave with negative integers. Anyway, repeatedly using `div` seems wrong, as it is not the same as using `div` once with the product of the remaining values. Now using `quot`, I get the same results for `<{}([][])[]>`and `<{}{([][])[]}>`.

For nice, almost readable code look at the first version. The intermediate versions contain all kinds of nice and intimidating code and help understand this version.

# Answer
> 1 votes
## JavaScript (ES6), no `eval`, 156 bytes

```
f=s=>s==(s=s.replace(/(.) ?([- \d]*)[\]})>]/,(_,c,s)=>` `+(s?s.split` `.reduce((l,r)=>c<`<`?l- -r:c<`[`?l/r|0:c<`{`?l-r:l*r):c==`[`?-1:c==`(`?0:1)))?+s:f(s)

```

Explanation: The regexp finds the first unprocessed closing bracket, and matches the (presumably) corresponding opening bracket and any arguments in between. The arguments are split and reduced according to the operation (sadly '(' and '\[' are not the optimal pair for `+` and `-`), or if there are no arguments then the appropriate value is calculated (again the matching of characters to values is suboptimal from my point of view). The result is then substituted in with a leading space so as to separate it from other results. The function then calls itself recursively until there are no more changes to make, in which case it returns the resulting value. Example:

```
[()<>]
[ 0<>]
[ 0 1]
 -1

```

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