# Question
Title: All your bijective base are belong to us
### Background

A bijective base **b** numeration, where **b** is a positive integer, is a bijective positional notation that makes use of **b** symbols with associated values of **1** to **b**.

Unlike its non-bijective counterpart, no symbol has a value of **0**. This way, each non-negative integer **n** has a *unique* representation in bijective base **b**.

Popular bijective numerations include unary, bijective base 2 (used in bzip2's run-length encoding) and bijective base 26 (used to number columns in spreadsheets).

### Definition

In this challenge, we define the set **M** of symbols as

```
123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz<=>

```

and a function **i** from **M** to the natural number such that **i('1') = 1, …, i('\>') = 64**.

Given a base **b** between **1** and **64** (both inclusive), we define that each non-negative integer **n** corresponds to the string **ak…a0**, consisting of symbols of **M**, such that **n = bki(ak)+…+b0i(a0)**.

This correspondence is well-defined and bijective. Since an empty sum is defined as **0**, the integer **0** can be encoded as an empty string.

### Task

Accept three strings as input:

* An input base **b** between **1** and **64**, encoded as a bijective base **64** string.
* A non-negative integer **n**, encoded as a bijective base **b** string.
* An output base **B** between **1** and **64**, encoded as a bijective base **64** string.

Given these three inputs, encode **n** as a bijective base **B** string.

### Test cases

All test cases specify the input in the order **b**, **n**, **B**.

```
Input:  "4" "" "8"
Output: ""

Input:  "A" "16" "2"
Output: "1112"

Input:  "2" "122" "A"
Output: "A"

Input:  "3" "31" "1"
Output: "1111111111"

Input:  ">" "Fe" "a"
Output: "RS"

```

### Rules

* You may read the three strings in any convenient order, as such, an array of strings, a string representation thereof, concatenated or separated by single-character delimiters of your choice.
* If you choose to print the output to STDOUT, you may only print the symbols and (optionally) a trailing newline.
* Base conversion built-ins of all kinds are allowed.
* Standard rules apply.

# Answer
# CJam, 43

```
qA,s"?[a{A<":,:^+:Mf#):B;(bLa{(Bmd)M=\j\+}j

```

3 bytes eradicated with help from Dennis :) Try it online

**Explanation:**

The input is taken as `bnB`, concatenated into a single string.

```
q           read the input
A,s         make an array of numbers from 0 to 9 and convert to string
"?[a{A<"    push this string, which contains the ends of 3 character ranges:
             uppercase letters: ['A'…'[')
             lowercase letters: ['a'…'{')
             "<=>": ['<'…'?')
             they're in a special order for the symmetric difference below
:,          for each character, make a range of all characters smaller than it
:^          fold/reduce these 6 ranges using symmetric difference
+           concatenate with the digits before
:M          save in M; this is like the M from the statement,
             except it starts with a zero (for matching indexes)
f#          find the indexes in M of all characters from the input string
)           take out the last value from the array
:B;         save it in B and pop it
(           take out the first value
b           use it as a base and convert the remaining array to a number
             this works even if some of the digits are not in the "normal" range
La{…}j      calculate with memoized recursion, using an empty string for value 0
  (         decrement the number
  Bmd       divide by B and get the quotient and remainder
  )         increment the remainder (this is the last digit in bijective base B)
  M=        get the corresponding character from M
  \j        swap with the quotient, and convert the quotient recursively
  \+        swap again and concatenate

```
> 6 votes

# Answer
# Pip, ~~84~~ ~~80~~ 78 bytes

```
m:J[,tAZLCAZ"<=>"]p:$+(m@?^b)*(m@?a)**RV,#bs:m@?cWn:px:(mn-(p:n//s-!n%s)*s).xx

```

GitHub repository for Pip

Algorithms adapted from the Wikipedia article. Here's the explanation for a slightly ungolfed earlier version:

```
                 Implicit: initialize a,b,c from cmdline args; t=10;
                 AZ=uppercase alphabet; x=""
m:               Build lookup table m:
 (J,t)             0123456789 (i.e. join(range(10)))...
 .AZ               plus A-Z...
 .LCAZ             plus lowercase a-z...
 ."<=>"            plus <=>
f:{              Define f(a,b) to convert a from bijective base b to decimal:
 $+                Sum of...
  (m@?^a)            list of index of each character of a in m
  *                  multiplied item-wise by
  b**RV,#a           b to the power of each number in reverse(range(len(a)))
}
t:{              Define t(a,b) to convert a from decimal to bijective base b:
 x:""              Reset x to empty string (not needed if only calling the function once)
 Wa{               While a is not zero:
  p:a//b-!a%b        p = ceil(a/b) - 1 (= a//b if a%b!=0, a//b-1 otherwise)
  x:m@(a-p*b).x      Calculate digit a-p*b, look up the corresponding character in m, and
                     prepend to x
  a:p                p becomes the new a
 }
 x                 Return x
}
(t               Return result of calling t with these arguments:
 (f                Result of calling f with these arguments:
  b                  2nd cmdline arg
  m@?a)              1st cmdline arg's decimal value
 m@?c              3rd cmdline arg's decimal value
)
                 Print (implicit)

```

Sample run:

```
dlosc@dlosc:~/golf$ python pip.py bijectivebase.pip ">" "Fe" "a"
RS

```
> 5 votes

# Answer
# Octave, 166 bytes

```
function z=b(o,x,n)
M=['1':'9','A':'Z','a':'z','<=>'];N(M)=1:64;n=N(n);x=polyval(N(x),N(o));z='';while x>0 r=mod(x,n);t=n;if r t=r;end;z=[M(t),z];x=fix(x/n)-(r<1);end

```

Multi-line version:

```
function z=b(o,x,n)
   M=['1':'9','A':'Z','a':'z','<=>'];
   N(M)=1:64;
   n=N(n);
   x=polyval(N(x),N(o));
   z='';
   while x>0
      r=mod(x,n);
      t=n;if r t=r;end;
      z=[M(t),z];
      x=fix(x/n)-(r<1);
   end
%end // implicit - not included above

```

Rather than create a map to convert a character to an index value, I just created the inverse lookup table `N` for ascii values `1..'z'` and populated it with the indices at the appropriate values.

`polyval` evaluates the equation

> c1xk \+ c2xk-1 \+ ... + ckx0

using the decimal-converted input value as the vector of coefficients `c` and the original base as `x`. (Unfortunately, Octave's `base2dec()` rejects symbols out of the normal range.)

Once we have the input value in base 10, calculation of the value in the new base is straightforward.

Test driver:

```
% script bijecttest.m
a=b('4','','8');
disp(a);
a=b('A','16','2');
disp(a);
a=b('2','122','A');
disp(a);
a=b('3','31','1');
disp(a);
a=b('>','Fe','a');
disp(a);

```

Results:

```
>> bijecttest

1112
A
1111111111
RS
>>

```
> 4 votes

# Answer
# Perl, ~~261~~ ~~248~~ 229 bytes

```
sub t{$b=0;$b*=$_[1],$b+=ord($1=~y/0-9A-Za-z<=>/\0-A/r)while$_[0]=~/(.)/g;return$b}sub r{$n=$_[0];$n-=$m=($n-1)%$_[1]+1,$d=(chr$m)=~y/\0-A/0-9A-Za-z<=>/r.$d,$n/=$_[1]while$n;print$d}@a=split/,/,<>;r(t(@a[1],t@a[0],64),t@a[2],64)

```

multi-line, while loops ungolfed:

```
sub t{ # convert bijective base string to number
    $b=0;
    while($_[0]=~/(.)/g)
        {$b*=$_[1];$b+=ord($1=~y/0-9A-Za-z<=>/\0-A/r)}
    return$b}
sub r{ # convert number to bijective base string
    $n=$_[0];
    while($n)
        {$n-=$m=($n-1)%$_[1]+1;$d=(chr$m)=~y/\0-A/0-9A-Za-z<=>/r.$d;$n/=$_[1]}
    print$d}
@a=split/,/,<>; # parse input
r(t(@a[1],t@a[0],64),t@a[2],64)

```

`t` is a function to parse a number from a bijective-base string of a given base. `r` is a function to generate a bijective-base string of a given base from a number. The 3 comma-separated parameters are parsed from stdin and the functions are called as needed.

Converting a positive number to a bijective base string is similar to a normal base. However where you would do something like this for a normal base:

```
string s = ""
while(n)
{
    c = (n % base)
    s = (c + '0') + s
    n -= c // not necessary because the division will take care of it
    n /= base
}

```

you adjust the mod to give a range from 1 to base instead of 0 to base - 1:

```
string s = ""
while(n)
{
    c = (((n-1) % base)+1)
    s = (c + '0') + s
    n -= c  // necessary in the case c = base
    n /= base
}

```
> 2 votes

# Answer
# CJam, ~~73~~ ~~70~~ ~~69~~ ~~55~~ ~~51~~ 48 bytes

Latest version uses the CJam base conversion operator for the conversion from the source base, which I hadn't thought of until I saw @aditsu's solution. It also applies a recent tip by @Dennis for constructing the "digit" string (https://codegolf.stackexchange.com/a/54348/32852), as well as some other ideas shared on chat.

```
lA,s'[,_el^+"<=>"+:Lf#Ll#bLl#:K;{(Kmd)L=\}hs-]W%

```

Input format is the value, followed by the source and destination base, with each of them on a separate line. For the empty string, leave the first line empty. Example input:

```
122
2
A

```

Try it online

Explanation:

```
l       Get and interpret value from input.
A,s     Build the list of 64 "digits". Start with [0..9]
'[,     Build character sequence from \0 to Z.
_el     Lower case copy of the same sequence.
^       Symmetric set difference gives only letters from both sequences.
+       Concatenate with sequence of decimal digits, creating [0..9A..Za..z].
"<=>"   Remaining 4 characters.
+       Concatenate, resulting in full 64 character "digit" string.
:L      ... and store it in variable L for repeated use.
f#      Look up input characters in digit list.
Ll#     Get source base from input, and look up value in digit list.
b       Base conversion. This produces the input value.
Ll#     Get destination base from input, and look up value in digit list.
:K;     Store it in variable K for use in loop, and pop it off stack.
{       Loop for generating output digits.
  (       Decrement to get ceiling minus 1 after division.
  Kmd     Calculate divmod of current value with destination base.
  )       Increment mod to get 1-based value for digit.
  L=      Look up digit character for digit value.
  \       Swap. Digit stays on stack for output, remaining value is processed
          in next loop iteration until it is 0.
}h      End of loop for generating output digits.
s       Final value is 0. Covert it to a string.
-       And subtract it from second but last value. This eliminates the 0,
        as well as the second but last value if it was a \0 character.
]       Wrap digits in array.
W%      Reverse array, to get result from MSB to LSB.

```
> 2 votes

# Answer
# Python 2, ... ~~317~~ ~~307~~ ~~298~~ 311 bytes

Definitely golfable. I really hate how strings have no item assignment and lists have no `find`. I'll look into a better way than my fast fix that I have now.

My method is to convert the input to a decimal number, then to the output base, then convert that to the bijective base.

**Edit**: Found that my program didn't work when converting to Unary. It cost 13 bytes to fix with `e=F(o)<2`, etc.

**Try it here**

```
R=range;M="".join(map(chr,R(48,58)+R(65,91)+R(97,123)))+"<=>"
b,s,o=input()
F=M.find
e=F(o)<2
B=lambda n:n and B(n/F(o)-e)+M[n%F(o)+e]or""
n=B(sum(F(s[~j])*F(b)**j for j in R(len(s))))
i=n.find('0')
n=list(n)
while-~i:n=n[:i-1]+[M[F(n[i-1])-1]]+[o]+n[i+1:];n=n["0"==n[0]:];i="".join(n).find('0')
print"".join(n)

```
> 2 votes

# Answer
# Python 2, 167 Bytes

No special tricks in here really, except for the `[2::5]` slicing to get the charset at a lower byte count.

```
x=range;A=`map(chr,x(49,58)+x(65,91)+x(97,123))`[2::5]+'<=>'
r=A.find
b,n,B=input()
B=r(B)+1
d=0;s=''
for c in n:d=d*-~r(b)+r(c)+1
while d:d-=1;s=A[d%B]+s;d/=B
print s

```

Tests:

```
"4","","8"     >>> (empty string)
">","Fe","a"   >>> RS
"3","31","1"   >>> 1111111111
"A","16","2"   >>> 1112
"2","122","A"  >>> A

```
> 2 votes

# Answer
# Jelly, 22 bytes

```
ØBḊ;“<=>”
i@€€¢ḅḃ2ƭ/ị¢

```

Try it online!
> 0 votes

---
Tags: code-golf, math, base-conversion
---


title: How can I shorten this python code?

text:
# Question
Title: How can I shorten this python code?
Here is the code which I want to shorten.

```
n=input()
while n:
 s=raw_input()
 x,r,g,b=(int(x) for x in s.split())
 a=x/r%2
 c=x/g%2
 d=x/b%2
 r=((a*10+c)*10)+d
 if r==0:e="black"
 elif r==100:e="red"
 elif r==1:e="blue"
 elif r==10:e="green"
 elif r==101:e="magenta"
 elif r==11:e="cyan"
 elif r==110:e="yellow"
 else:e="white"
 print(e)
 n-=1

```

Input: 3

```
4643 5913 4827 9752
5583 5357 5120 9400
2025 5475 4339 8392

```

Output:

```
black
yellow
black

```

# Answer
> 18 votes
Instead of `((a*10+c)*10)+d` we can use `((a*2+c)*2)+d` to distinguish the colors.

```
 r=((a*2+c)*2)+d
 if r==0:e="black"
 elif r==4:e="red"
 elif r==1:e="blue"
 elif r==2:e="green"
 elif r==5:e="magenta"
 elif r==3:e="cyan"
 elif r==6:e="yellow"
 else:e="white"

```

Ah, but now we're just distinguishing between values from `0` to `7`, so we can index into an array instead!

```
 r=a*4+c*2+d
 e=["black","blue","green","cyan","red","magenta","yellow","white"][r]
 # or even shorter:
 e="black blue green cyan red magenta yellow white".split()[r]

```

Combining with Uriel's changes we get down to 136 bytes **(164 bytes saved)**.

```
exec'x,r,g,b=map(int,raw_input().split());print"black blue green cyan red magenta yellow white".split()[x/r%2*4+x/g%2*2+x/b%2];'*input()

```

Try it online!

# Answer
> 5 votes
For the repetition use an `exec` statement,

`map(int,` for the conversion of string input into numerals,

shorten calculating `r` with `r=a*100+c*10+d`, then put the calculations of each variable (`a`, `c`, `d`) instead of the variable,

and for the conditions use a dictionary with a `get` query.

Finally, mash everything into one line.

Final result (updating):

```
exec'x,r,g,b=map(int,raw_input().split());print({0:"black",100:"red",1:"blue",10:"green",101:"magenta",11:"cyan",110:"yellow"}.get((x/r%2)*100+(x/g%2)*10+x/b%2,"white"));'*input()

```

Bytes saved: **121**.

---
Tags: code-golf, tips, python
---


title: Average Out Two Lists

text:
# Question
Title: Average Out Two Lists
# Average out two lists

### Challenge

Given two lists of positive integers, determine whether it is possible to rearrange the elements into two new lists such that the new lists have the same arithmetic mean (average).

### Input

The input can be taken through STDIN or as function arguments. Input can be taken as a list, or if your language doesn't support lists (or anything similar such as arrays/dictionaries) then the input can be taken as a comma- or space-delimited string. That is,

```
"1 4 8 2 5,3 1 5 2 5"

```

is the same as:

```
[ [1,4,8,2,5], [3,1,5,2,5] ]

```

All *input* lists will be the *same* length.

### Output

If you can create two new lists with the same average, your program/function should print or return the mean. If you can't, your program should output a sad face `:(`.

Note that the rearranged lists with equal means, if they exist, need not has the same length. Any number of swaps can be made to create the new lists.

### Examples

```
1 4 8 2 5,3 1 5 2 5 -> 1 4 8 2 3,5 1 5 2 5 (swapped 3 and 5) -> 3.6
1 3 6 2,16 19 19 14 -> [[1,6,19,14],[3,2,16,19]] -> 10
2 6 2,6 3 5 -> 2 6,2 6 3 5 (moved 2) -> 4
90 80 20 1,40 60 28 18 -> :(

```

---

This is so shortest code in bytes wins. As always, standard loopholes are disallowed.

# Answer
> 13 votes
# Pyth, 24 bytes

```
?}KcsJsQlJmcsdldtPyJK":(

```

Try it online: Demonstration

Thanks to Dennis for noticing an error and golfing one byte.

### Explanation:

```
?}KcsJsQlJmcsdldtPyJK":(   implicit: Q = evaluated input
      sQ                   all numbers of Q
     J                     save them in J
  KcsJ  lJ                 average of J (sum(J) / len(J))
                           store in K
          m     tPyJ       map each nonempty subset d of J to:
           csdld             average of d
?}                         if K in ^:
                    K        print K
                     ":(   else print sad-face

```

# Answer
> 6 votes
# SWI-Prolog, 159 bytes

```
a(A,B):-append([A,B],R),permutation(R,S),append([Y,Z],S),sum_list(Y,I),sum_list(Z,J),length(Y,L),length(Z,M),L\=0,M\=0,I/L=:=J/M,W is J/M,write(W);write(':(').

```

Called as `a([1,4,8,2,5],[3,1,5,2,5]).`

# Answer
> 5 votes
# Julia, 101 bytes

```
f(a,b)=(m=mean;p=filter(i->m(i[1])==m(i[2]),partitions([a,b],2));isempty(p)?":(":m(collect(p)[1][1]))

```

This creates a function that accepts two arrays and returns a string or a float accordingly.

Ungolfed + explanation:

```
function f(a,b)
    # Get the set of all 2-way partitions of the array [a,b]
    l = partitions([a,b], 2)

    # Filter the set of partitions to those where the two
    # contained arrays have equal means
    p = filter(i -> mean(i[1]) == mean(i[2]), l)

    # Return a frown if p is empty, otherwise return a mean
    isempty(p) ? ":(" : mean(collect(p)[1][1])
end

```

# Answer
> 2 votes
# R, 94 Bytes

Basically the same as Jakubes I think. If the mean of both lists matches the mean of any combination of the values in lists up to but not including the combined length of the list, output the mean otherwise the sad face.

```
if(mean(l<-scan())%in%unlist(sapply(2:length(l)-1,function(x)combn(l,x,mean))))mean(l)else':('

```

Test run

```
> if(mean(l<-scan())%in%unlist(sapply(2:length(l)-1,function(x)combn(l,x,mean))))mean(l)else':('
1: 1 4 8 2 5
6: 3 1 5 2 5
11:
Read 10 items
[1] 3.6
> if(mean(l<-scan())%in%unlist(sapply(2:length(l)-1,function(x)combn(l,x,mean))))mean(l)else':('
1: 90 80 20 1
5: 40 60 28 18
9:
Read 8 items
[1] ":("

```

# Answer
> 0 votes
# Jelly, 23 bytes

```
FŒ!ŒṖL=2ƊƇÆmEƇƲ€ṀṀṀȯ⁾:(

```

Try it online!

Wildly inefficient, times out when the lengths of the input lists are \\$\ge4\\$

## How it works

```
FŒ!ŒṖL=2ƊƇÆmEƇƲ€ṀṀṀȯ⁾:( - Main link. Takes a list of lists, l = [a,b]
F                       - Flatten
 Œ!                     - Yield all permutations
              Ʋ€        - Over each permutation, p:
   ŒṖ                   -   Yield all partitions of p
     L=2ƊƇ              -   Only keep those of length 2
          Æm            -   Take the mean of each
            EƇ          -   Only keep those where the means are equal
                ṀṀṀ     - Take the maximum three times. This yields 0 for impossible inputs and the mean for possible ones
                    ⁾:( - Yield the string ":("
                   ȯ    - Replace 0 with this string, or do nothing if not 0

```

---
Tags: code-golf, array
---


title: Fold up a matrix!

text:
# Question
Title: Fold up a matrix!
Given a matrix, sum its values up/down or left/right to form an X, fold it up, and return the list. I describe the algorithm here:

# Algorithm

Your input will be a odd-sized square matrix of integers within your language's reasonable numerical capacity.

Let's take the following matrix as an example:

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

```

First, add every number to the closest number that is on the main diagonal or antidiagonal. That is, divide the matrix into four sections along the main diagonal and antidiagonal, and then sum all of the numbers in each section towards the center, like so:

```
1   2   3   2   1
    ↓   ↓   ↓
0 → 3   2   3 ← 0
        ↓
4 → 2 → 5 ← 6 ← 3
        ↑
7 → 4   7   9 ← 4
    ↑   ↑   ↑
0   6   7   2   5

```

This step gives the following result:

```
1        1
  5    5
    39
  17  15
0        5

```

Then, we fold it by flattening the X and interweaving the elements with the top-left first and the bottom left last. This gives the following result:

```
1, 0, 5, 17, 39, 5, 15, 1, 5

```

You can imagine this as stretching the main diagonal and rotating it counterclockwise.

This is the final result.

# Challenge

Implement this algorithm. Standard loopholes apply. All reasonable I/O formats acceptable.

# Test Cases

```
Input
Output

1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5

1, 0, 5, 17, 39, 5, 15, 1, 5

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

1, 6, 11, 16, 47, 7, 22, 5, 0

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

1, 8, 15, 11, 23, 20, 62, 32, 25, 13, 18, 3, 9

```

# Answer
> 7 votes
# JavaScript, 113 bytes

```
s=>(l=s.length-1,a=[],s.map((v,y)=>v.map((n,x)=>a[q=2*[x,y,l-y].sort((u,v)=>u-v)[1]+(y>l/2),q-=q>l]=~~a[q]+n)),a)

```

```
f=

s=>(l=s.length-1,a=[],s.map((v,y)=>v.map((n,x)=>a[q=2*[x,y,l-y].sort((u,v)=>u-v)[1]+(y>l/2),q-=q>l]=~~a[q]+n)),a)
```

```
<p><textarea id="i" style="width: 400px; height: 120px">1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5</textarea></p>
<p><button onclick="o.value=f(i.value.trim().split`\n`.map(l=>l.trim().split(/\s+/).map(v => parseInt(v,10)))).join` `">Run</button></p>
<p><output id="o"></output></p>
```

# Answer
> 5 votes
# Python, 159 158 bytes

```
def f(m):l=len(m)-1;r=range(1,l);return m[0][::l]+f([[sum(m[x][1%y*y:(y>l-2)-~y])+m[0][y]*(x<2)+m[l][y]*(x>l-2)for y in r]for x in r])+m[l][::l]if l else m[0]

```

Try it online!

# Answer
> 5 votes
# Jelly, ~~25~~ ~~23~~ 21 bytes

```
AṂ×ṠṚ
LHŒRṗ2Ç€ḅLĠịFS€

```

Try it online!

### Alternate version, 19 bytes

```
AṂ×ṠṚ
LHŒRṗ2Ç€ĠịFS€

```

This didn't use to work because `Ġ` behaved improperly for nested arrays. The only difference is that the pairs **\[q, p\]** mentioned in *How it works* are sorted lexicographically instead of mapping them to **p + nq** before sorting.

Try it online!

### Background

We start by replacing its elements with coordinates, increasing leftwards and downwards and placing **(0, 0)** in the center of the matrix.

For a 7x7 matrix **M**, we get the following coordinates.

```
(-3,-3) (-3,-2) (-3,-1) (-3, 0) (-3, 1) (-3, 2) (-3, 3)
(-2,-3) (-2,-2) (-2,-1) (-2, 0) (-2, 1) (-2, 2) (-2, 3)
(-1,-3) (-1,-2) (-1,-1) (-1, 0) (-1, 1) (-1, 2) (-1, 3)
( 0,-3) ( 0,-2) ( 0,-1) ( 0, 0) ( 0, 1) ( 0, 2) ( 0, 3)
( 1,-3) ( 1,-2) ( 1,-1) ( 1, 0) ( 1, 1) ( 1, 2) ( 1, 3)
( 2,-3) ( 2,-2) ( 2,-1) ( 2, 0) ( 2, 1) ( 2, 2) ( 2, 3)
( 3,-3) ( 3,-2) ( 3,-1) ( 3, 0) ( 3, 1) ( 3, 2) ( 3, 3)

```

We now compute the minimum absolute value of each coordinate pair and multiply the signs of both coordinate by it, mapping **(i, j)** to **(sign(i)m, sign(j)m)**, where **m = min(|i|, |j|)**.

```
(-3,-3) (-2,-2) (-1,-1) ( 0, 0) (-1, 1) (-2, 2) (-3, 3)
(-2,-2) (-2,-2) (-1,-1) ( 0, 0) (-1, 1) (-2, 2) (-2, 2)
(-1,-1) (-1,-1) (-1,-1) ( 0, 0) (-1, 1) (-1, 1) (-1, 1)
( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0)
( 1,-1) ( 1,-1) ( 1,-1) ( 0, 0) ( 1, 1) ( 1, 1) ( 1, 1)
( 2,-2) ( 2,-2) ( 1,-1) ( 0, 0) ( 1, 1) ( 2, 2) ( 2, 2)
( 3,-3) ( 2,-2) ( 1,-1) ( 0, 0) ( 1, 1) ( 2, 2) ( 3, 3)

```

Matrix elements that correspond to the same pair have to be summed. To determine the order of the sums, we map each pair **(p, q)** to **p + nq**, where **n** is the number of rows/columns of **M**.

```
-24 -16  -8   0   6  12  18
-16 -16  -8   0   6  12  12
 -8  -8  -8   0   6   6   6
  0   0   0   0   0   0   0
 -6  -6  -6   0   8   8   8
-12 -12  -6   0   8  16  16
-18 -12  -6   0   8  16  24

```

The order of sums corresponds to the order of integers the correspond to its summands.

### How it works

```
LHŒRṗ2Ç€ḅLĠịFS€  Main link. Argument: M (matrix)

L                Compute n, the length (number of rows) of M.
 H               Halve it.
  ŒR             Symmetric range; map t to [-int(t), ..., 0, int(t)].
    ṗ2           Compute the second Cartesian power, yielding all pairs [i, j]
                 with -t ≤ i, j ≤ t.
      Ç€         Map the helper link over the resulting array of pairs.
         L       Yield n.
        ḅ        Unbase; map each pair [q, p] to (p + nq).
          Ġ      Group the indices of the resulting array of n² integers by their
                 corresponding values, ordering the groups by the values.
            F    Flatten M.
           ị     Index into the serialized matrix.
             S€  Compute the sum of each group.

AṂ×ṠṚ            Helper link. Argument: [i, j] (index pair)

A                Absolute value; yield [|i|, |j|].
 Ṃ               Minimum; yield m := min(|i|, |j|).
   Ṡ             Sign; yield [sign(i), sign(j)].
  ×              Multiply; yield [p, q] := [sign(i)m, sign(j)m].
    Ṛ            Reverse; yield [q, p].

```

# Answer
> 3 votes
# Dyalog APL, ~~101~~ ~~99~~ ~~64~~ ~~62~~ 59 bytes

<sub>*3 bytes saved by @Adám*</sub>

```
{+/∘,¨⍵∘×¨d∘=¨k[⍋k←↑∪/,d←∘.((+/1x×××⌊/∘|),)⍨(⍳x)-⌈.5×x←≢⍵]}

```

Try it online!

Using Dennis' awesome algorithm.

# Answer
> 2 votes
# APL (Dyalog), 60 bytes\*

In collaboration with my colleague Marshall.

Anonymous prefix lambda. Takes matrix as argument and returns vector. Assumes `⎕IO` (**I**ndex **O**rigin) to be zero, which is default on many systems.

```
{(,⍉{+/,(s×-×⍺)↓⍵×i∊¨⍨s←⌊⊃r÷2}⌺r⊢⍵)/⍨,(⊢∨⌽)=/¨i←⍳r←⍴⍵}

```

Try it online!

`{``}` anonymous lambda;  is right argument (as rightmost letter of the Greek alphabet):

`⍴⍵` shape of the argument (list of two identical elements)

`r←` store as `r` (as in **r**ho)

all **ɩ**ndices of an array of that size, i.e. `(0 0)`,`(0 1)`

`i←` store in `i` (as in **i**ota)

`=/¨` Boolean where the coordinates are equal (i.e. the diagonal)

`(``)` apply this anonymous tacit prefix function:

reverse the argument

`⊢∨` OR that with the unmodified argument

`,` ravel (straighten into simple list)

We now have a Boolean mask for the diagonals.

`(``)/⍨` use that to filter the following:

`⊢⍵` yield (to separate from `r`) the argument

`{``}⌺r` call the following anonymous infix lambda on each element, with the `r`-neighbourhood (padded with zeros as needed) as right argument (), and a two element list of number padded rows,columns (negative for bottom/right, zero for none) as left argument ():

`r÷2` divide `r` with two

pick the first element (they are identical)

floor it

`s←` store as `s` (for **s**hape)

`i∊⍨¨` for each element of `i`, Boolean if `s` is a member thereof

`⍵×` multiply the neighbourhood therewith

`(``)↓` drop the following number of rows and columns (negative for bottom/right):

`×⍺` signum of the left argument (i.e. the direction of paddings)

`-` negate

multiply `s` therewith

`,` ravel (straighten into list)

`+/` sum (plus reduction)

Now we have full matrix of sums, but we need to filter all the values read columnwise.

transpose

`,` ravel (straighten into simple list)

---

* By counting  as `⎕U233A` . Try it online!

---
Tags: code-golf, matrix
---


title: Two-Coloring Overlapping Circles

text:
# Question
Title: Two-Coloring Overlapping Circles
Write a program or function that takes in the following input in a reasonable format of your choice:

* Two positive integers W and H that define the width and height of the image you'll be generating.
* Two RGB colors C1 and C2 that will be used to color the image.
* A list of 3-tuples of the form `(r, x, y)` that define circles with radius `r` and center `x, y` in the plane of the image. `r` is a positive integer and `x` and `y` are any integers. The top left pixel of the image is `0, 0` and the x-axis increases to the right and the y-axis increases downward.

Output an image with dimensions W by H that is colored with C1 and C2 **such that no two neighboring regions defined by all the overlapping circles are the same color.**

> **For example:** If the input is
>
> ```
> W = 300
> H = 200
> C1 = (255, 200, 0)
> C2 = (128, 0, 255)
> Circles = (25, 50, 80), (40, 80, 120), (300, -100, 6), (17, 253, 162)
>
> ```
>
> then the circle boundaries look like this:
>
> There are six distinct, contiguous regions in the image created by the circles. Each region must be colored with C1 (yellow) or C2 (purple) such that no two neighboring regions are the same color.
>
> There are two ways to do this, their only difference being that the colors are swapped:
>
> Thus, either of these two images would be valid output for the example input.
>
> Something like this would be invalid output since two yellow regions neighbor each other.

Your output images should follow these guidelines:

* Besides C1 and C2, a third, neutral color such as black or white may be used for circle boundaries as long as they are no more than 5 pixels thick. (Black, 1-pixel thick boundaries are present in the example above.)
* Circles boundaries are not required, however. The regions may neighbor each other directly:

Both of these is another valid output to the example above.
* Circles should be as accurate as reasonably possible, using circle drawing algorithms or whatever your graphics library provides.
* In general, pixel-perfection is not required, but if the input parameters are scaled equally larger and larger, the resulting image should become more and more accurate.
* Anti-aliasing is allowed but not required.
* Gridlines or axis labels etc. in the background are not allowed.

**The shortest code in bytes wins.**

# More Examples

All using these inputs with different sets of circles:

```
W = 100
H = 60
C1 = (255, 0, 0)
C2 = (0, 0, 255)

```

In any example the colors can be swapped and remain valid.

```
Circles =
A. empty list
B. (13, 16, 20)
C. (30, 16, 20)
D. (200, 16, 20)
E. (42, 50, 20)
F. (42, 50, 20), (17, 40, 30)
G. (42, 50, 20), (17, 20, 30)
H. (42, 50, 20), (17, 10, 30), (10, 50, 30)
I. (42, 50, 20), (17, 10, 30), (35, 50, 20)
J. (18, 36, 40), (18, 63, 40), (18, 50, 20)
K. (100, -10, -20), (60, 50, -10)
L. (18, 36, 40), (18, 63, 40), (18, 50, 20), (14, 50, 20), (5, 50, 18), (20, 0, 0), (70, 22, 0), (10000, -9970, 0), (135, 100, -80)

```

`A.`  `B.`  `C.`  `D.`
`E.`  `F.`  `G.`  `H.`
`I.`  `J.`  `K.`  `L.`

Make sure your output behaves similar to all these examples.

# Answer
> 14 votes
# Mathematica, 165 bytes

```
ContourPlot[Cos@Tr[Boole[Norm[{x,y}-#2]<#]Pi&@@@#4],{x,0,#},{y,0,#2},PlotPoints->5!,AspectRatio->Automatic,Frame->False,ContourShading->RGBColor@@@#3,Contours->{0}]&

```

Pure function taking four arguments: the width, the height (both integers), an ordered pair of triples of numbers between 0 and 1 (representing the two RGB colors), and a list of items of the form `{r, {x, y}}` to record the radii and centers of the circles. For example, the first example in the OP would be called with the arguments `[300, 200, {{1, 0.784, 0}, {0.5, 0, 1}}, {{25, {50, 80}}, {40, {80, 120}}, {300, {-100, 6}}, {17, {253, 162}}}]`. The positive y-axis points upwards in Mathematica.

`Norm[{x,y}-#2]<#` detects whether a point is inside a given circle; `Boole[...]Pi` converts that `True` or `False` to `π` or `0`. After computing those πs/0s over all the input circles, `Tr` adds them up and `Cos` converts even multiples of π to 1, odd multiples of π to –1. `ContourPlot[...,Contours->{0}]` then colors the appropriate region of the plane in two colors depending on whether the value is greater or less than `0`. `AspectRatio->Automatic` makes circles look like circles; `PlotPoints->5!` gives a decent accuracy (boost it to `9!` if you really want an amazing picture, far in the future!); `Frame->False` gets rid of the axes; and `ContourShading->RGBColor@@@#3` uses the input colors for the contours.

Sample output, with the first pair of colors (since they're nice) but the last set of circles:

# Answer
> 11 votes
## JavaScript/SVG/HTML5, 219 bytes

```
f=// for demo
(w,h,b,f,a)=>`<svg width=${w} height=${h}><rect width=${w} height=${h} fill=rgb(${b}) /><path fill=rgb(${f}) fill-rule=evenodd d=${a.map(([r,x,y])=>[`M`+x,y-r+`a`+r,r,0,0,0,0,r+r+`a`+r,r,0,0,0,0,-r-r]).join``} /></svg>`
;//demo
[[`A`, []],
 [`B`, [[13, 16, 20]]],
 [`C`, [[30, 16, 20]]],
 [`D`, [[200, 16, 20]]],
 [`E`, [[42, 50, 20]]],
 [`F`, [[42, 50, 20], [17, 40, 30]]],
 [`G`, [[42, 50, 20], [17, 20, 30]]],
 [`H`, [[42, 50, 20], [17, 10, 30], [10, 50, 30]]],
 [`I`, [[42, 50, 20], [17, 10, 30], [35, 50, 20]]],
 [`J`, [[18, 36, 40], [18, 63, 40], [18, 50, 20]]],
 [`K`, [[100, -10, -20], [60, 50, -10]]],
 [`L`, [[18, 36, 40], [18, 63, 40], [18, 50, 20], [14, 50, 20], [5, 50, 18], [20, 0, 0], [70, 22, 0], [10000, -9970, 0], [135, 100, -80]]]
 ].forEach(([c, a])=>document.write(`<nobr><tt> ${c}. </tt>${f(100, 60, [255, 0, 0], [0, 0, 255], a)}</nobr><wbr>`));
```

# Answer
> 10 votes
# BBC Basic, ~~120~~ 117 bytes

Download interpreter at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

```
I.w,h,R,G,B,r,g,b:V.22,4,19;16,r,g,b,275;16,R EORr,G EORg,B EORb,24,0;0;w;h;16
5I.r,x,y:V.25,4,x;h-y;25,154,r;0;:G.5

```

BBC Basic has a range of colour modes allowing you to plot raster graphics according to basic logic operations: OR, AND, XOR etc.

It also supports pallete reprogramming, meaning that for example here a 2 colour image can have its colours reprogrammed to any of 4096 colours. The implementation used here has some (undocumented) differences from the original BBC implementation, in which the EOR operators would not be necessary.

**Ungolfed**

```
  INPUTw,h,R,G,B,r,g,b:                           :REM Input size and colours
  VDU22,4                                         :REM Change to MODE 4 (2 colours) as the default mode gives odd behaviour
  VDU19,0,16,r,g,b,19,1,16,R EORr,G EORg,B EORb   :REM Reprogram the colours to R,G,B and R^r,G^g,B^b
  VDU24,0;0;w;h;16                                :REM Setup a graphics viewport of the right size, and "clear" it to change background colour
5 INPUTr,x,y                                      :REM take input coordinates
  VDU25,4,x;h-y;                                  :REM move to x,y (h-y required as BBC BASIC y axis increases upward, reverse of spec)
  VDU25,154,r;0;                                  :REM draw circle in "logical inverse colour" of existing pixels (this implementation seems however to XOR with colour 1 instead)
  GOTO5                                           :REM repeat infinitely until user presses escape

```

**Typical output screen**

Example image scaled up by a factor of 10 in units / factor of 5 in pixels (BBC basic uses 1 pixel = 2 units.)

# Answer
> 10 votes
# MATL, ~~30~~ ~~29~~ 25 bytes

```
2ZG:i:!J*+2&!-|i<so2&!1YG

```

Input format:

* Colormap as a matrix of values between 0 and 255, where each row defines a color
* *W*
* *H*
* Column vector of 1-based center coordinates as complex values (*x* is the real part, *y* is the imaginary part)
* Column vector of radii.

Try at MATL Online! Or verify the last test case. (The interpreter is still experimental. You may need to refresh the page and try again if it doesn't work).

### Explanation

The code uses complex numbers to define the grid of points and to compute distances, and makes heavy use of array operations with broadcasting.

```
2ZG    % Implicitly input matrix of colors. Set as colormap
:      % Implicitly input W. Push [1 2 ... W]
i:     % Input H. Push [1 2 ... H]
!J*    % Transpose, multiply by 1i
+      % Add element-wise with broadcast. Gives H×W grid of points as
       % complex numbers, 1-based
2&!    % Permute first dimension with the third. Gives a 1×W×H array
-|     % Implicitly input center coordinates. Subtract grid from them,
       % element-wise with broadcast. Gives a C×H×W array, where C is the
       % number of circles
i      % Input column vector of circle radii
<      % Less than, element-wise with broadcast
so     % Sum along first dimension, modulo 2. Gives a 1×W×H array
2&!    % Permute first dimension with the third. Gives a a H×W array
1YG    % Display as scaled image

```

# Answer
> 6 votes
# Python using pypng, ~~140~~ 138 bytes

```
import png
f=lambda W,H,c,d,C:png.from_array([[[c,d][sum(abs(x-X+1j*(y-Y))<r for r,x,y in C)%2]for X in range(W)]for Y in range(H)],'RGB')

```

Example usage:

```
W = 100
H = 60
C1 = (255, 0, 0)
C2 = (0, 0, 255)
Circles = (18, 36, 40), (18, 63, 40), (18, 50, 20), (14, 50, 20), (5, 50, 18), (20, 0, 0), (70, 22, 0), (10000, -9970, 0), (135, 100, -80)
f(W, H, C1, C2, Circles).save('test.png')

```

Thanks to xnor for saving 2 bytes.

# Answer
> 3 votes
# Math (non-competiting)

(idk how to do LaTeX in PPCG, so I used a LaTeX to png tool)

## Explanation

The product of multiple circle equations (`(x-a)^2+(y-b)^2-r^2`) \>= 0 will make a graph which this question needs. In the equation, `n` is the size of the array, and `(x, y or r)_k` is the `k`th `(x, y, or r)` element.

## Example

`(0,0,2),(2,2,2)`

(Inequality plot by WolframAlpha)

# Get/Run equation for WolframAlpha

> Getting script : Complete

```
<input id="in" placeholder="input, with () changed to []">
<br>
<input type="color" id="c1" value="#ff0000">
<input type="color" id="c2" value="#00ff00">
<br>
<input id="w" placeholder="width">
<input id="h" placeholder="height">
<br>

<button onclick="change()">
Convert!
</button>
<br>
<input id="res" placeholder="result">
<script>
  function change() {
    var a = document.getElementById("in").value;
    document.getElementById("res").value = "";
    var arr = JSON.parse("[" + a + "]");
    document.getElementById("res").value += "plot ";
    for (var i = 0; i < arr.length; i++) {
      document.getElementById("res").value += "((x-("
      document.getElementById("res").value += arr[i][1];
      document.getElementById("res").value += "))^2+(y-(";
      document.getElementById("res").value += arr[i][2];
      document.getElementById("res").value += "))^2-(";
      document.getElementById("res").value += arr[i][0];
      document.getElementById("res").value += ")^2)";
    }
    document.getElementById("res").value += ">=0";
    document.getElementById("res").value += " from x=0 to x=";
    document.getElementById("res").value += document.getElementById("w").value;
    document.getElementById("res").value += " and y=0 to y=";
    document.getElementById("res").value += document.getElementById("h").value/2;
    document.getElementById("res").value += "> color ";
    document.getElementById("res").value += document.getElementById("c1").value;
    document.getElementById("res").value += " background color ";
    document.getElementById("res").value += document.getElementById("c2").value;
  }
</script>
```

> Running script : Not done yet

Now make it work with Mathematica...

# Answer
> 1 votes
# Common Lisp + Quicklisp + ZPNG 260 + 20 = 280 chars

This is some of the widest code I've ever written in CL, and if I weren't doing a code golf I would've restructured this to make it much easier to read...

Prelude (20 chars)

```
(ql:quickload 'zpng)

```

Golfed (260 chars)

```
(lambda(w h g b c)(make-instance'zpng:png :image-data(coerce(loop :for j :below h :nconc(loop :for i :below w :append(if(evenp(count t(mapcar(lambda(c)(<(abs(complex(-(cadr c)i)(-(caddr c)j)))(car c)))c)))g b)))'(array(unsigned-byte 8)(*))):width w :height h))

```

Ungolfed:

(Uses defun to allow testing and longer variable names for readability)

```
(defun mk-png (width height color1 color2 circles)
  (make-instance 'zpng:png
                 :image-data (coerce (loop :for j :below height
                                           :nconc (loop :for i :below width
                                                        :append (if (evenp (count t (mapcar (lambda (circ)
                                                                                (< (abs (complex (- (cadr circ) i) (- (caddr circ) j)))
                                                                                (car circ)))
                                                                                circles)))
                                                                    color1 color2)))
                                     '(array (unsigned-byte 8) (*)))
                 :width width
                 :height height))

```

Example Usage:

```
(let ((png (mk-png 300 200 '(255 200 0) '(128 0 255) '((25 50 80) (40 80 120) (300 -100 6) (17 253 162)))))
  (zpng:write-png png #p"path/to/file.png"))

```

### Explaination

```
(lambda (circ)
   (< (abs (complex (- (cadr circ) i) (- (caddr circ) j)))
      (car circ)))

```

Returns true if the point (i, j) falls within the given circle circ. Euclidean distance is calculated by taking the absolute value of the complex number which represents the vector from (i, j) to the center of circ.

```
(evenp (count t (mapcar ___
                         circles)))

```

Map that function across the circles list and check if the given point (i, j) falls within an even number of circles.

```
(if ____
     color1 color2)

```

Select color based on that test.

```
(loop :for j :below height
       :nconc (loop :for i :below width
                    :append ____))

```

Collect together a flat list of all the rgb bytes by looping over each (i, j) in the image and appending the resulting lists together.

```
(coerce ____
         '(array (unsigned-byte 8) (*)))

```

Convert that list of bytes into a proper array of bytes, so zpng can ingest it properly.

```
(make-instance 'zpng:png
                :image-data ____
                :width width
                :height height)

```

Create the png object.

```
(defun mk-png (width height color1 color2 circles)
   ___)

```

Create the function to take the width, height, two colors, and list of circles and return the created png object.

# Answer
> 1 votes
# Python 2.x, ~~166~~ 158

```
import re;def f(W,H,c,d,C):print'P3',W,H,255,re.sub('[^0-9]',' ',repr([[d,c][sum([abs(x-X+1j*(y-Y))<r for r,x,y in C])%2]for Y in range(H)for X in range(W)]))

```

The function generates a PPM file on the standard output.

# example:

```
W = 300
H = 200
C1 = (255, 200, 0)
C2 = (128, 0, 255)
Circles = [(25, 50, 80), (40, 80, 120), (300, -100, 6), (17, 253, 162)]

f(W, H, C1, C2, Circles)

```

# Answer
> 0 votes
# JavaScript (ES6), 224 bytes

I saw the JS + SVG solution, but I just had to create a canvas-based solution ;-) This is a function which returns a canvas element. If an existing canvas element can be provided, remove 40 bytes.

Call like `f(width, height, [[r1, g1, b1], [r2, g2, b2]], [[r1, x1, y1], [r2, x2, y2], ...])`

```
let f =
(w,h,a,c,O=document.createElement`canvas`)=>{O.width=w;O.height=h;C=O.getContext`2d`;for(y=0;y<h;y++)for(x=0;x<w;x++)C.fillStyle=`rgb(${a[c.filter(([R,X,Y])=>(X-x)**2+(Y-y)**2<R**2).length%2]})`,C.fillRect(x,y,1,1);return O}

let tests = A.innerHTML.match(/.+/g);
A.innerHTML = "";
for (let i of tests) {
  let p = document.createElement("span");
  p.innerHTML = "<br>" + i.slice(0, 3);
  p.style["font-family"] = "monospace";
  A.append(p);
  A.append(f(100, 60, [[255,0,0], [0,0,255]],
    eval(`[${ i.slice(3).replace(/\(/g, "[").replace(/\)/g, "]") }]`)
  ));
}
```

```
<div id=A>
A.
B. (13, 16, 20)
C. (30, 16, 20)
D. (200, 16, 20)
E. (42, 50, 20)
F. (42, 50, 20), (17, 40, 30)
G. (42, 50, 20), (17, 20, 30)
H. (42, 50, 20), (17, 10, 30), (10, 50, 30)
I. (42, 50, 20), (17, 10, 30), (35, 50, 20)
J. (18, 36, 40), (18, 63, 40), (18, 50, 20)
K. (100, -10, -20), (60, 50, -10)
L. (18, 36, 40), (18, 63, 40), (18, 50, 20), (14, 50, 20), (5, 50, 18), (20, 0, 0), (70, 22, 0), (10000, -9970, 0), (135, 100, -80)
</div>
```

Example output:

# Answer
> 0 votes
# Löve2D, 353 Bytes.

```
o=love.graphics
a=arg
w,h,r,g,b,R,G,B=...c={}for i=9,#a,3 do
c[#c+1]={a[i],a[i+1],a[i+2]}end
C=o.newCanvas(w,h)o.setCanvas(C)o.clear(R,G,B)for k,v in pairs(c)do
o.stencil(function()o.circle("fill",v[2],v[3],v[1],9^3)end,"invert",1,true)end
o.setStencilTest("greater",0)o.setColor(r,g,b)o.rectangle("fill",0,0,w,h)local
C:newImageData():encode("png","c")

```

---
Tags: code-golf, graphical-output, geometry, graph-theory, color
---


title: Parse nested digit-lead strings

text:
# Question
Title: Parse nested digit-lead strings
## The task

A string `S` is constructed with the following process:

1. Start with `S` being the empty string.
2. Insert at some position of `S` a string of the form `ds`, where `d` is a nonzero digit and `s` is a string of `d` lowercase ASCII letters. We say `ds` is a *constituent* of `S`.
3. Go to step 2 or stop.

Your task is to take such a string as input, and output its constituents concatenated into a single string, in the order of appearance of their leading digits. The output must be a single string, and there can't be any delimiters (including newlines) between the constituents. You can choose whether the input and output strings have quotes. Note that the input and output will never be empty.

## Example

Let's construct a string with the above process. The structure of the constituents is highlighted in the final result.

```
S = ""              // Insert "3abc"
S = "3abc"          // Insert "2gh" after 'a'
S = "3a2ghbc"       // Insert "1x" before '3'
S = "1x3a2ghbc"     // Insert "3tty" after '3'
S = "1x33ttya2ghbc" // Final result
     └┘│└┴┴┘│└┴┘││
       └────┴───┴┘

```

The output is obtained by concatenating the constituents in the order of their digits. In this case, the correct output is

```
"1x3abc3tty2gh"

```

## Rules and scoring

You can write a full program or a function. the lowest byte count wins, and standard loopholes are disallowed.

## Test cases

```
1k -> 1k
4asdf -> 4asdf
111xyz -> 1z1y1x
8whatever3yes -> 8whatever3yes
8what3yesever -> 8whatever3yes
1x33ttya2ghbc -> 1x3abc3tty2gh
63252supernestedstrings2ok -> 6trings3eds2st5perne2su2ok
9long3yes4lo2ngwords11here -> 9longrdsre3yes4lowo2ng1e1h
9abc8de7fg6hi5jk4lm3o2pq1rstuvwxyzabcdefghijklmnopqrst -> 9abcopqrst8deijklmn7fgdefgh6hizabc5jkwxy4lmuv3ost2pq1r

```

# Answer
# JavaScript (ES6), 68 bytes

```
f=s=>s&&f(s.replace(/\d\D+$/,m=>(s=m.slice(0,i=++m[0]),m.slice(i))))+s

```

## Explanation

Based on a simple concept:

* Match the last digit `n` followed by `n` letters in the input string
* Remove it from the input string and add it to the start of the output string
* Repeat until the input string is empty

Recursion was the shortest way to do this in JavaScript.

```
f=s=>
  s&&                        // if the input string is empty, return the empty string
  f(                         // prepend the constituent before it
    s.replace(/\d\D+$/,m=>(  // match the last digit followed by every remaining letter
      s=m.slice(0,n=++m[0]), // set s to the constituent (n followed by n letters)
                             // (we must use s because it is our only local variable)
      m.slice(n)             // replace the match with only the letters after it
    ))
  )+s                        // append the constituent
```

```
<input type="text" id="input" value="9long3yes4lo2ngwords11here" />
<button onclick="result.textContent=f(input.value)">Go</button>
<pre id="result"></pre>
```
> 2 votes

# Answer
# Haskell, 89 bytes

```
fst.p
p(d:s)|(h,(g,r))<-p<$>span('9'<)s,(a,b)<-splitAt(read[d])$h++r=(d:a++g,b)
p e=(e,e)

```

Try it online! Example usage: `fst.p $ "1x33ttya2ghbc"` yields `"1x3abc3tty2gh"`.
> 0 votes

# Answer
# Python 3, ~~173~~ 159 bytes

```
k='123456789';y='';i=0
for t in x:
 i+=1
 if t in k:
  y+=t;n=int(t);m=0
  for z in x[i:]:
   if n:
    if z in k:m+=int(z)+1
    if m<1:y+=z;n-=1
    m-=m>0

```

Try it online!

Probably not the golfiest Python implementation.

The logic is almost straightforward: it scans the string. When it finds a digit it starts adding the characters that follow, as many as required (i.e. until the count corresponds to the digit). If it encounters digits before completing the task, it adds them to a counter corresponding to the number of characters to skip. When the counter reaches zero, it goes back to adding characters (i.e. until the count corresponds to the initial digit).

Note: Saved 14 bytes thanks to Wheat Wizard and HyperNeutrino
> 0 votes

# Answer
# Java 8, 152 bytes

```
s->{String t=s,r="";for(char c;!s.isEmpty();c=t.charAt(0),s=s.replace(t=c+(t.substring(1,c-47)),""),r=t+r)t=s.replaceAll(".*(\\d\\D+$)","$1");return r;}

```

**Explanation:**

Try it here.

```
s->{                        // Method with String as both parameter and return-type
  String t=s,               //  Temp-String, starting at the input-String
         r="";              //  Result-String, starting empty
  for(char c;!s.isEmpty();  //  Loop as long as the input-String `s` is not empty
                            //    After every iteration:
      c=t.charAt(0),        //     Get the leading digit from `t` as character
      s=s.replace(t=c+(t.substring(1,c-47))
                            //     Set `t` to the last substring (digit + `c` letters),
                  ,""),     //     and remove that sub-string from String `s`
      r=t+r)                //     And add the substring at the start of result-String `r`
    t=s.replaceAll(".*(\\d\\D+$)","$1");
                            //   Get the last digit + everything after it,
                            //   and set this substring to `t`
                            //  End of loop (implicit / single-line body)
  return r;                 //  Return result-String
}                           // End of method

```
> 0 votes

# Answer
# Python 2, ~~151~~ ~~147~~ 135 bytes

```
d,D=[],[]
for c in input():
 if'/'<c<':':x=[[c]];d=x+d;D+=x
 else:y=d[0];y+=c;d=d[len(y)>int(y[0]):]
print''.join(''.join(w)for w in D)

```

Try it online!

**Explanation:**

The code keeps two lists of constituent groups, `d and D`.

Each character of the string is then scanned:

* If it is a digit, a new group is added to both lists
* Otherwise, the character is added to the latest group in `d`

When a group has the same length as its digit, the group is removed from `d`.

At the end, the `D` is concatenated, as the groups in `D` are in the original order.

**Example:**

```
Input = '1121xwyzv'
d = [], D = []
Loop each character in the input

c='1'
    d=[[1]], D=[[1]]
c='1'
    d=[[1], [1]], D=[[1], [1]]
c='2'
    d=[[2], [1], [1]], D=[[1], [1], [2]]
c='1'
    d=[[1], [2], [1], [1]], D=[[1], [1], [2], [1]]
c='x'
    d=[[1x], [2], [1], [1]], D=[[1], [1], [2], [1x]]
latest group in d is full:
    d=[[2], [1], [1]], D=[[1], [1], [2], [1x]]
c='w'
    d=[[2w], [1], [1]], D=[[1], [1], [2w], [1x]]
c='y'
    d=[[2wy], [1], [1]], D=[[1], [1], [2wy], [1x]]
latest group in d is full:
    d=[[1]], D=[[1], [1], [2wy], [1x]]
c='z'
    d=[[1z], [1]], D=[[1], [1z], [2wy], [1x]]
latest group in d is full:
    d=[[1]], D=[[1], [1z], [2wy], [1x]]
c='v'
    d=[[1v]], D=[[1v], [1z], [2wy], [1x]]
latest group in d is full:
    d=[], D=[[1v], [1z], [2wy], [1x]]
print D in order:
    '1v1z2wy1x'

```
> 0 votes

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


title: Is my password secure?

text:
# Question
Title: Is my password secure?
# Task:

Take a string as input and if it meets the requirements, accept the password.

**Input**: a string, e.g. `someString`, `asjk23t89h`, `123456789abcdef`.

**Output**: two distinct values representing "secure" and "insecure", e.g. `0`/`1`, `true`/`false`, `secure`/`insecure`.

# Password requirements:

In order for a password to be determined as secure, it must:

* Be at least 8 characters in length.
* Contain at least one character each from the four groups `a-z`, `A-Z`, `0-9` and `!"£$%^&*()_+-={}[]:@~;'#<>?,./`

# Examples:

* `password` -\> insecure
* `password123` -\> insecure
* `L0h~[/1s7C` -\> secure
* `h&fn3*#` -\> insecure
* `C#de g07F` -\> secure

# Winning:

This is code golf, the shortest answer wins.

# Answer
# Java 8, ~~93~~ ~~62~~ ~~65~~ 60 bytes

```
s->s.matches("([a-z]()|[A-Z]()|\\d()|.()){8,}+\\2\\3\\4\\5")

```

+3 bytes due to a bugfix, pointed out by *@MartinEnder♦*.
-5 bytes thanks to *@jaytea* by using capture groups instead of lookaheads, since the matches are not overlapping.

Old answer with (redundant) dictionary (**~~93~~ 96 bytes**):

```
d->s->!d.contains(s.toLowerCase())&s.matches("(?=.*[a-z])(?=.*[A-Z])(?=.*\\d)(?=.*[\\W_]).{8,}")

```

~~Because I can't think of a single word in the dictionary that contains at least one uppercase, lowercase, digit and other ASCII character.. So the dictionary-check is kinda redundant in that case.~~

**Explanation:**

Try it here.

```
s->                    // Method with String parameter and boolean return-type
  s.matches("([a-z]()  //  Checks if the String contains at least one lowercase letter
             |[A-Z]()  //  and at least one uppercase letter
             |\\d()    //  and at least one digit
             .()       //  and at least one other ASCII character
             ){8,}+\\2\\3\\4\\5")
                       //  And has a length of at least 8
                       // End of method (implicit / single-line return-statement)

```
> 3 votes

# Answer
# Python 2, ~~112~~ ~~107~~ ~~83~~ 86 bytes

```
lambda s:re.match(r'(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[\W_]).{8,}',s)!=None
import re

```

Try it online!
> 2 votes

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


title: All Possible Matching Lists

text:
# Question
Title: All Possible Matching Lists
Implement a function that takes a list that consists of 0, 1 or 2, the list is called "pattern". Your job is to return all possible lists that match the pattern.

* 0 matches 0
* 1 matches 1
* 2 matches 0 and 1

Examples:

```
f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]

```

Order does not matter, you can use a {set} data structure instead.

You cannot use regular expressions or other **string** pattern matching mechanisms. You cannot use a brute-force search.

Shortest solution wins.

# Answer
> 8 votes
## Haskell, 49 characters

```
f[]=[[]]
f(2:r)=f(0:r)++f(1:r)
f(x:r)=map(x:)$f r

```

Interestingly this is exactly what I'd write even if this wasn't golf - except for removing spaces and calling the list's tail `r` rather than `xs`.

# Answer
> 5 votes
## Haskell, ~~34~~ 26 characters

Saved 8 characters thanks to Zgarb.

```
r 2=[0,1]
r n=[n]
f=mapM r

```

# Answer
> 5 votes
# Prolog, 62 characters

```
f([],[]). f([H|T],[A|B]):-((H=2,(A=0;A=1));(H<2,A=H)),f(T,B).

```

Example:

```
?- f([0,2,0,2],X).
X = [0, 0, 0, 0] ;
X = [0, 0, 0, 1] ;
X = [0, 1, 0, 0] ;
X = [0, 1, 0, 1] ;

```

# Answer
> 3 votes
# Mathematica, 30 chars

```
f=Tuples[{#}&/@#/.{2}->{0,1}]&

```

Examples:

```
f[{0, 1, 1}]

```

> {{0, 1, 1}}

```
f[{0, 2, 0, 2}]

```

> {{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}}

```
f[{2, 1, 0}]

```

> {{0, 1, 0}, {1, 1, 0}}

# Answer
> 1 votes
## Ruby - 76 characters

```
def f l;l==l-[2]?[l]:((j=l.dup)[k=l.index(2)]=0;(i=l.dup)[k]=1;f(j)+f(i))end

```

### Testing script:

```
require_relative 'golf-lists'

[
  [0, 1, 1],
  [0, 2, 0, 2],
  [2, 1, 0]
].each do |list|
  puts "f([#{list.join(', ')}]) == #{f(list)}"
end

```

Result:

```
f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 1, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]

```

# Answer
> 0 votes
## Scheme (149) (148)

```
(define(f l)(if(null? l)'(())(let((t(f(cdr l)))(n(car l)))(if(< n 2)(map(lambda(m)`(,n,@m))t)`(,@(map(lambda(m)`(0,@m))t),@(map(lambda(m)`(1,@m))t]

```

With whitespace (the closing square brace closes all open parentheses on certain Scheme implementations; 154 chars without it):

```
(define (f l)
  (if (null? l)
      '(())
      (let ((t (f (cdr l)))(n(car l)))
        (if (< n 2)
            (map (lambda (m) `(,n ,@m)) t)
            `(,@(map (lambda (m) `(0 ,@m)) t)
              ,@(map (lambda (m) `(1 ,@m)) t]

```

# Answer
> 0 votes
# CJam, 18 bytes

CJam is much younger than this challenge, so this is answer is not eligible for being accepted.

```
]]l~{2b\f{\f+~}}/p

```

Reads input from STDIN as a CJam style array.

Test it here.

## Explanation

```
]]l~{2b\f{\f+~}}/p
]]                 "Push a nested empty array [[]] onto the stack. This is the base case.";
  l~               "Read and eval the input.";
    {          }/  "For each integer in the input.";
     2b            "Convert to base 2. This turns 0 into [0], 1 into [1] and 2 into [1 0].";
       \f{    }    "Swap with the current result and map this block onto the base-2 representation
                    copying in the current list of lists on each iteration.";
          \f+      "Swap the list of lists with the 0 or 1 and add the number to each list.";
             ~     "Unwrap the list of lists. They'll be regrouped by the surrounding f{...}.";
                 p "Pretty-print the result.";

```

# Answer
> 0 votes
# Python 2, 156 bytes

```
def f(l):R,L=range(len(l)),[];exec"\n".join(" "*j+"for v%d in[[l[%d]],[0,1]][l[%d]>1]:"%(j,j,j)for j in R)+"L+=["+"".join("v%d,"%j for j in R)+"],";return L

```

Try it online!

# Answer
> 0 votes
# J, 19 bytes

```
[:>@,[:{{&(0;1;0 1)

```

Try it online!

I had originally created a much longer version using amend and binary numbers, but user b\_jonas suggested the above approach in IRC to me.

It essentially converts 0 and 1 to themselves, and 2 to the list `0 1`, and the just cross products everything using catalog `{`. Since catalog requires boxed data, and returns structured data, everything is (un)raveled and unboxed at the end: `>@,`.

---
Tags: code-golf, array
---


title: The Binary Square Diagonal Sequence

text:
# Question
Title: The Binary Square Diagonal Sequence
The *binary-square-diagonal-sequence* is constructed as follows:

1. Take the sequence of positive natural numbers:
```
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
```
2. Convert each number to binary:

```
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, ...
```
3. Concatenate them:

```
11011100101110111100010011010101111001101111011111000010001 ...
```
4. Starting with `n=1`, generate squares with increasing side-length `n` which are filled left-to-right, top-to-bottom with the elements of the above sequence:

```
1
```

```
1 0
1 1
```

```
1 0 0
1 0 1
1 1 0
```

```
1 1 1 1
0 0 0 1
0 0 1 1
0 1 0 1
```

```
0 1 1 1 1
0 0 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 1
```

```
...
```
5. Take the diagonal (top left to bottom right) of each square:

```
1, 11, 100, 1011, 00111, ...
```
6. Convert to decimal (ignoring leading zeros):

```
1, 3, 4, 11, 7, ...
```

# Task

Write a program or function which outputs the sequence in one of the following ways:

* Return or print the sequence infinitely.
* Given input `i`, return or print the first `i` elements of the sequence.
* Given input `i`, return or print the `i`th element of the sequence (either 0 or 1 indexed).

Please state in your answer which output format you choose.

This is , the shortest answer in each language wins.

# Test cases

Here are the first 50 elements of the sequence:

`1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845,17129,55518,134717,151988,998642,1478099,391518,7798320,8530050,21809025,61485963,66846232,54326455,221064493,256373253,547755170,4294967295,1875876391,2618012644,24710258456,6922045286,132952028155,217801183183,476428761596,51990767390,687373028085,1216614609441,7677215985062,15384530216172,22714614479340,15976997237789,0,256145539974868,532024704777005,601357273478135`

# Answer
## Husk, ~~15~~ 14 bytes

```
zȯḋm←CtNCİ□ṁḋN

```

Try it online!

Continually prints the results as an infinite list.

### Explanation

I wonder whether there's a better way to get every **n**th element from a list than splitting the list into chunks of length **n** and retrieving the head of each chunk.

```
      tN          Get a list of all natural numbers except 1. (A)

             N    Get a list of all natural numbers.
           ṁḋ     Convert each to its binary representation and join them
                  all into a single list.
         İ□       Get a list of squares of all natural numbers.
        C         Cut the list of bits into chunks of corresponding sizes. (B)

zȯ                Zip (A) and (B) together with the following function.
     C            Split the bit list (from B) into chunks of the given length
                  (from A).
   m←             Get the head of each chunk. This is the diagonal of the
                  bit list arranged as a square.
  ḋ               Interpret the resulting bits as binary digits and return
                  the result.

```

To be clear, we extract the diagonal of an **n x n** square by splitting its linear form into chunks of length **n + 1** and retrieving the first element of each chunk:

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

```
> 11 votes

# Answer
# Python 2, ~~137~~ 85 bytes

```
lambda n:int(''.join(bin(x+1)[2:]for x in range(n**3))[n*~-n*(2*n-1)/6:][:n*n:n+1],2)

```

Try it online!
> 6 votes

# Answer
# Python 3, ~~96~~ 94 bytes

```
lambda i:int(''.join(bin(x+1)[2:]for x in range(i**3))[sum(x*x for x in range(i))::i+1][:i],2)

```

Try it online!
> 5 votes

# Answer
# 05AB1E, ~~19~~ ~~17~~ 16 bytes

```
°LbJsLn£θs>ô€нJC

```

`°` is replaced by `3m` in the links as `°` tends to get very slow.

Try it online! or as a Test Suite

**Explanation**

```
°L                 # push the range [1 ... 10^input]
  bJ               # convert each to binary and join to string
    sLn            # push the range [1 ... input]^2
       £θ          # split the binary string into pieces of these sizes and take the last
         s>ô       # split this string into chunks of size (input+1)
            €н     # get the first digit in each chunk
              JC   # join to string and convert to int

```
> 5 votes

# Answer
# Java (OpenJDK 8), ~~215~~ ~~212~~ ~~206~~ ~~202~~ 197 bytes

```
i->{String b="",t;int s=0,x=++i,j;for(;--x>0;s+=x*x);while(b.length()<s)b+=i.toString(++x,2);for(j=1,s=0;j<i;System.out.println(i.valueOf(t,2)),s+=j*j++)for(t="",x=s;x<s+j*j;x+=j+1)t+=b.charAt(x);}

```

Try it online!
> 4 votes

# Answer
# Husk, 15 bytes

This takes a somewhat different approach to Martin's answer

```
moḋz!NCNCṘNNṁḋN

```

Try it online!

### Explanation:

```
              N   List of all natural numbers
            ṁḋ    Convert each to it's binary representation and flatten
         ṘNN      Repeat the list of natural numbers according the natural numbers:
                  [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5...]
        C         Cut the list of bits into lists of lengths corresponding to the above
      CN          Cut that list into lists of lengths corresponding to the natural numbers
moḋz!N            For each in the list, get the diagonals and convert from binary.
m                   For each list in the list
   z!N              Zip it with natural numbers, indexing.
 oḋ                 Convert to binary

```

### In action

`ṁḋN` : `[1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1...]`

`ṘNN` : `[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8...]`

`C` : `[[1],[1,0],[1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1,1],[0,0,0,1]...]`

`CN` : `[[[1]],[[1,0],[1,1]],[[1,0,0],[1,0,1],[1,1,0]]...]`

`m z!N` : `[[1],[1,1],[1,0,0],[1,0,1,1],[0,0,1,1,1],[0,1,1,1,0,1]...]`

`oḋ` : `[1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845...]`
> 4 votes

# Answer
# Python 2, 91 bytes

```
i=n=1;s=''
while 1:
 s+=bin(i)[2:];i+=1
 if s[n*n:]:print int(s[:n*n:n+1],2);s=s[n*n:];n+=1

```

Try it online!

prints the sequence infinitely
> 3 votes

# Answer
# Jelly, 16 bytes

```
RBFṁ
R²SÇṫ²C$m‘Ḅ

```

Try it online!

## Explanation

```
RBFṁ  Helper link. Input: integer k
R     Range, [1, 2, ..., k]
 B    Convert each to a list of its binary digits
  F   Flatten
   ṁ  Mold to length k

R²SÇṫ²C$m‘Ḅ  Main link. Input: integer n
R            Range, [1, 2, ..., n]
 ²           Square each
  S          Sum
   Ç         Call helper link on the sum of the first n squares
       $     Monadic chain
     ²         Square n
      C        Complement, 1-n^2
    ṫ        Tail, take the last n^2 elements
        m    Modular indexing, take each
         ‘   (n+1)th element
          Ḅ  Convert from list of binary digits to decimal

```
> 3 votes

# Answer
# Mathematica, 96 bytes

**Outputs** the `i`th element of the sequence (1-indexed)

```
Diagonal@Partition[TakeList[Flatten@IntegerDigits[Range[#^3],2],Range@#^2][[#]],#]~FromDigits~2&

```

Try it online!
> 2 votes

# Answer
# Jelly, 18 bytes

Completely different approach compared to Erik's solution.

```
Ḷ²S‘ɓ*3B€Fṫ
Çm‘ḣµḄ

```

Try it online!

## How it works

```
Ḷ²S‘ɓ*3B€Fṫ  - Helper link (monadic).

Ḷ            - Lowered range, generates [0, N).
 ²           - Vectorized square (square each).
  S          - Sum.
   ‘         - Increment, to account for the 1-indexing of Jelly.
     ɓ       - Starts a separate dyadic chain.
     *3      - The input to the power of 3.
       B€    - Convert each to binary.
         F   - Flatten.
          ṫ  - Tail. Return x[y - 1:] (1-indexed).

Çm‘ḣµḄ  - Main link (monadic).

Ç       - Last link as a monad.
 m‘     - Modular input + 1. Get each "input + 1"th element of the list.
   ḣ    - Head. Return the above with elements at index higher than the input cropped.
    µḄ  - Convert from binary to integer.

```

Saved 1 byte thanks to Jonathan Allan!
> 2 votes

# Answer
# Jelly, 22 bytes

```
²Rµ²Ṭ€Ẏ0;œṗBẎ$³ịs³ŒDḢḄ

```

Try it online!
> 1 votes

# Answer
# Pyth,  ~~27~~  20 bytes

```
i<%hQ>s.BS^Q3s^R2QQ2

```

**Verify the first few test cases.**

Gets the **I**th term of the sequence, 1 indexed.

## How it works?

```
i<%hQ>s.BS^Q3s^R2QQ2   - Full program. Q represents the input.

         S^Q3          - Generate the (inclusive) range [1, Q ^ 3].
       .B              - Convert each to binary.
      s                - Join into a single string.
     >                 - Trim all the elements at indexes smaller than:
               ^R2Q      - The elements of the range [0, Q) squared.
              s          - And summed.
  %hQ                  - Get each Q + 1 element of the list above.
 <                     - Trim all the elements at indexes higher than:
                   Q   - The input.
i                   2  - Convert from binary to integer.

```
> 1 votes

# Answer
# Perl 5, 92 + 1 (`-p`) = 93 bytes

```
$s.=sprintf'%b',++$"for 1..$_**3;map{say oct"0b".(substr$s,0,$_*$_,'')=~s/.\K.{$_}//gr}1..$_

```

Try it online!
> 1 votes

---
Tags: code-golf, sequence, binary, base-conversion, binary-matrix
---


title: Did you hear about alphametics?

text:
# Question
Title: Did you hear about alphametics?
## Task

The letters spell out actual words, but if you replace each letter with a digit from 0–9, it also “spells” an arithmetic equation. The trick is to figure out which letter maps to each digit. All the occurrences of each letter must map to the same digit, no digit can be repeated, and no “word” can start with the digit 0.

# Input

```
HAWAII + IDAHO + IOWA + OHIO = STATES

```

# Output

```
510199 + 98153 + 9301 + 3593 = 621246

```

# Input

```
I + LOVE + YOU = DORA

```

# Output

```
1 + 2784 + 975 = 3760

```

# Input

```
SEND + MORE = MONEY

```

# Output

```
9567 + 1085 = 10652

```

# Rules

* Standard loopholes apply.
* shortest code wins.
* addition only

# Appendix

for other Inputs you gotta keep in mind you can only have 10 different characters(to assign values 0-9)

# Answer
> 2 votes
# JavaScript (ES7), 104 bytes

```
f=(s,o,c=s.match(/[A-Z]/))=>c?[...2**29+'4'].some(i=>o&1<<i?0:f(r=s.split(c).join(i),o|1<<i))&&r:eval(s)

```

### Demo

```
f=(s,o,c=s.match(/[A-Z]/))=>c?[...2**29+'4'].some(i=>o&1<<i?0:f(r=s.split(c).join(i),o|1<<i))&&r:eval(s)

console.log(f('I + LOVE + YOU == DORA'))
```

### Formatted and commented

```
f = (                               // f = recursive function taking:
  s,                                //   s = input string
  o,                                //   o = bitmask of used digits
  c = s.match(/[A-Z]/)              //   c = next alphabetical character in s
) =>                                //       (either null or a single-element array)
  c ?                               // if c is not null:
    [...2**29 + '4'].some(i =>      //   for each character i of '5368709124'
      o & 1 << i ?                  //     if this digit was already used:
        0                           //       ignore this iteration
      :                             //     else:
        f(                          //       do a recursive call to f() with:
          r = s.split(c).join(i),   //         all characters c replaced with i
          o | 1 << i                //         the updated bitmask
        )                           //       end of recursive call
    ) && r                          //   end of some(): if successful, return r
  :                                 // else:
    eval(s)                         //   evaluate this fully numerical expression

```

---
Tags: code-golf, math, number, alphabet
---


title: It's a double+ header!

text:
# Question
Title: It's a double+ header!
*Related*

# Exposition

After winning the SO raffle, you could have been on top the world, and you were! The raffle had been going on for a year, now, and you were one of a hundred programmers who were selected to enter into the SO stronghold. And finally, the wait is over. Today is the day you go to--\[obfuscated text proceeds\].

Whoops. Sorry, not supposed to tell.

Anyhow, you finally have arrived to meet a stoic-faced man in a black suit with the tiny SO emblem on it. He frowns at you. "The others are already inside," he said, noting that you had been identified at the gate. "Quickly."

You rush inside, a tad scared. *What on earth had gone on? What was wrong at SO?* Inside, you observe the other 99 programmers are staring intently at their screens, typing. You take the remaining seat, and are greeted with the following message:

> Hello, programmer! It seems that we have encountered a problem; SO has been penetrated, by whom we don't know. (Personally, I suspect it was a Pyth or CJam programmer, but hey.) However, all that has been harmed is the Markdown editor. Well, actually, that's quite a lot, but that's where you come in.
> I want you to create a program (or function, we're not picky) that will interpret a markdown file and convert it to our new "SO Beautifier-Arity-Decomposer" (a.k.a. "SOBAD") format. You must do this in the shortest amount of bytes--we are running on lowdown until we resolve this hacking issue. Thanks for your time, and best of luck!
> Sincerely,
> The Maker of Stack Overflow

---

**Objective** Given a valid markdown file as input to your submission, perform and output the following transformations on the input:

(When I use the `+` symbol, I mean the RegExp "one or more instances of previous character" operator, not a literal plus sign.)

* Transform all Level 1 headers (`# ...` or `...\n=+`) to `{ ... }`, with `...` becoming ALL CAPS.
* Transform all Level 2 headers (`## ...` or `...\n-+`) to `{{ ... }}`, with every word capitalized
* Transform all Level 3 headers (`### ...`) to small caps; that is, all letters (case insensitive) are mapped to `ᴀʙᴄᴅᴇғɢʜɪᴊᴋʟᴍɴᴏᴘǫʀsᴛᴜᴠᴡxʏᴢ` in a respective fashion.
* Transform all bold instances (`**...**`) to `...`, with `...` becoming ALL CAPS.
* Transform all italic instances (`_..._`) to `. . .`, where a space has been inserted between each pair of characters.
* Transform all code instances (``...``) to `< ... >`.
* Transform all strikethrough instances (`---...---`) to `-.-.-.-`, where a `-` has been inserted between each pair of characters.
* Transform all numbered list instances (`N. {a}\nN. {b} ...` where `N` matches the regex `[0-9]+`) to (`1. {a}\n 2. {b}...`)
* Transform all unordered list instances (`* ...\n* ...`...) to (`o ...\n o ...`...)

## More details

* Headers and list instances will only be found at the beginning of lines, however, they may be surrounded by an amount of whitespace.
* There will be no linked instances, e.g., `*a_*a_` is not valid for our standards, nor will anything like `__a__`, `*_a_*`, or `_*a*_` appear in an input.
* A multiline header is valid if and only if the `-` or `=`s directly follows a line of text.
* No headers will contain other markdown entities. E.g., `# `code` snippet` is not a valid input for our purposes
* You do not have to account for Level 4+ headers
* You do not have to preserve excess spaces (i.e. `> 1` spaces) within the file, so it is O.K. to have `**hello there**` to become `**hello there**` but not `**hellothere**`. Similarly, trailing and leading spaces found on a line does not have to be preserved
* No tabulators will be found in the input.
* **THERE WILL BE NO NESTED INSTANCES.** For example, `***...***` would never occur.
* A space will always follow an unordered bullet point (E.g., `* ...` not `*...`)
* List items in ordered and unordered lists will always consist of a single line.
* Unmatched pairs of characters should be ignored. E.g., `** cool` and ``java::def` should remain the same.

---

## Input methods

The input must be one of the following:

1. An array/tuple/list/etc. of strings.
2. OR a string containing newlines to separate lines.

Use your language's closest equivalent to the aforementioned data types if your language does not support them. (E.g., TI-BASIC doesn't support (1.)… not that TI-BASIC can compete, anyhow :P).

## Test cases

A `}` signifies input, and the next line signifies output. Multiple `}`s signify newline-separated lines of text.

```
} Hello!
Hello!

} That _2 + 2 = 5_ challenge sure was **intense!**
That  2  +  2  =  5  challenge sure was INTENSE!
    // note that there are spaces also padding it

} It's `s/a/e/g` **not** `sudo g/a/e/s`, stupid.
It's < s/a/e/g > NOT < sudo g/a/e/s >

} **WHAT!** He did _WHAT?!_
WHAT! He did W H A T ? !

} _WHAT_ is undefined, here!
 W H A T  is undefined, here!

} OI)(EJDSFIJK L:JP #@*REF&WDS F*(D+S +&(SDFWEF )DSF _DSF_F #R#
OI)(EJDSFIJK L:JP #@*REF&WDS F*(D+S +&(SDFWEF )DSF  D S F F #R#

} # So, you wanna be a programmer, eh?
} ## Step 1: learn recursion
} ### Learning recursion requires learning recursion
} **Programming** is a futile task. _Leave w h i l e you still can!_
{SO YOU WANNA BE A PROGRAMMER, EH?}
{{Step 1: Learn Recursion}}
ʟᴇᴀʀɴɪɴɢ ʀᴇᴄᴜʀsɪᴏɴ ʀᴇǫᴜɪʀᴇs ʟᴇᴀʀɴɪɴɢ ʀᴇᴄᴜʀsɪᴏɴ
PROGRAMMING is a futile task.  L e a v e   w   h   i   l   e   y o u   s t i l l   c a n !  // trailing space not required

} Haha, you're a _Java_ golfer? You'd be better of with brainf***.
Haha, you're a  J a v a  golfer? You'd be better of with brainf***. // less than four asterisks, do nothing

} # Reasons why NOT to use C--:
} 1. It doesn't exist.
} 2. I don't care.
{REASONS WHY NOT TO USE C--:}
 1. It doesn't exist.
 2. I don't care.

} 1. This is a test!
} 1. <-- And this actually works in Markdown.
 1. This is a test!
 2. <-- And this actually works in Markdown. // less than three -s, ignore

} * no.
} * NOOO.
} * fine.
 o no.
 o NOOO.
 o fine.

} Python, ---34--- 3 bytes.
Python, -3-4- 3 bytes.

} ---Long line of crossed text.---
-L-o-n-g- -l-i-n-e- -o-f- -c-r-o-s-s-e-d- -t-e-x-t-.-

} ** cool!
** cool! // is not a bullet point, because a space doesn't follow the *; Isn't bold, because there is no matching **

 -- end of test cases --

```

# Bonus

1. -19 bytes if you support the escaping of characters (so that they are treated as "normal"); you may choose any escape character, but I'd suggest `\` or `^`. Note that the escaping system on SO sites is different from what I am suggesting (and more complicated), so don't do it! SO would treat ``\`` as `\`, but I would want you to treat the second ``` as then a regular character, and instead match the *next* ``` character.

# Answer
# Python 3, ~~652~~ 640 bytes

```
import re
def N(o):c,t,_=o.groups();x=' -'[c<'_'];return['< %s >'%t,t.upper()][c<'`']if c in'**`'else x+x.join(t)+x
def f(s):
 S=[];i=0
 while s:
  l=s.pop(0);n=set(*s[:1])
  if n<={*'=-'}and n:s=s[1:];l='#'*('-'in n)+'# '+l
  if'# '==l[:2]:l='{%s}'%l[2:].upper()
  if'## '==l[:3]:l='{{%s}}'%l[3:].title()
  if'### '==l[:4]:l=''.join('ᴀʙᴄᴅᴇғɢʜɪᴊᴋʟᴍɴᴏᴘǫʀsᴛᴜᴠᴡxʏᴢ'[ord(c)-65]if'@'<c<'['else c for c in l[4:].upper())
  l=re.sub(('(\*\*|_|---|`)(.*?)'*2)[:-5],N,re.sub(r'^\s*[*] (.*)',r' o \1',l))
  if re.match(r'\s*\d+\. ',l):i+=1;l=re.sub(r'\s*\d+\.(.*)',' %d.'%i+r'\1',l)
  else:i=0
  S+=[l]
 return S

```

Try it online!
> 1 votes

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


title: Sum the means of the two integers

text:
# Question
Title: Sum the means of the two integers
There are quite a few means in mathematics, such as the arithmetic mean, the geometric mean, and many others...

## Definitions and Task

Note that these are the definitions for *two positive integers*\*:

* The **root mean square** is the square root of the sum of their squares halved ().
* The **arithmetic mean** is their sum, halved ().
* The **geometric mean** is the square root of their product ().
* The **harmonic mean** is **2** divided by the sum of their inverses ( = ).

Given two integers **a** and **b** such that **a, b ∈ \[1, +∞)**, sum the means mentioned above of **a** and **b**. Your answers must be accurate to at least 3 decimal places, but you do not have to worry about rounding or floating-point precision errors.

# Test Cases

```
a, b -> Output

7, 6 -> 25.961481565148972
10, 10 -> 40
23, 1 -> 34.99131878607909
2, 4 -> 11.657371451581236
345, 192 -> 1051.7606599443843

```

You can see the correct results for more test cases using **this program**. This is , so the shortest valid submissions that follows the standard rules wins.

<sub> * There are many other means, but for the purposes of this challenge we'll use the ones mentioned in the "Definitions" section. </sub>

# Answer
> 13 votes
# Haskell, 48 bytes

```
a%b=sum[((a**p+b**p)/2)**(1/p)|p<-[2,1,-1,1e-9]]

```

Try it online!

This uses the fact that the root-square, arithmetic, harmonic, and geometric means are all special cases of the generalized mean `((a**p+b**p)/2)**(1/p)` for `p=2,1,-1,0`. The geometric mean uses the limit `p->0+`, approximated as `p=1e-9` which suffices for precision.

# Answer
> 9 votes
# Mathematica, 37 bytes

*-2 bytes thanks to Martin Ender. -6 bytes thanks to Jenny\_mathy and function reusability thanks to JungHwan Min.*

```
(t=1##)^.5+(2(s=+##/2)^2-t)^.5+s+t/s&

```

Try it online!

# Mathematica, 55 bytes

```
RootMeanSquare@#+Mean@#+GeometricMean@#+HarmonicMean@#&

```

Try it online!

¯\\\_(ツ)\_/¯

# Answer
> 5 votes
# Python 3, 57 bytes

```
lambda a,b:(a+b+(a*a+b*b<<1)**.5)/2+(a*b)**.5+2*a*b/(a+b)

```

Try it online!

# Answer
> 4 votes
# , 52 bytes

```
function(a,b,m=(a+b)/2,p=a*b)m+p^.5+(m^2*2-p)^.5+p/m

```

Try it online!

# Answer
> 3 votes
# Octave, ~~44~~ ~~42~~ 41 bytes

```
@(n)(q=mean(n))+rms(n)+(z=prod(n))^.5+z/q

```

Try it online!

Note that TIO does not have the signal package installed, so I defined `rms()` in the header. On Octave Online, you can try it if you `pkg load nan`. I'm not sure if there are any online interpreters that load it by default, but most systems would have this package loaded by default.

Thanks to Tom Carpenter for spotting a small mistake of 2 bytes.

This defines an anonymous function, taking the input as a vector `n=[a,b]`. We then use inline assignment to reduce the calculation of the HM to just `z/q`.

# Answer
> 3 votes
# Haskell, 48 bytes

```
a?b|s<-a+b,p<-a*b=s/2+sqrt(s^2/2-p)+sqrt p+2*p/s

```

Try it online!

### Explanation:

`s/2 = (a+b)/2`: The arithmetic mean.

`sqrt(s^2/2-p) = sqrt((a^2+2*a*b+b^2)/2-a*b) = sqrt((a^2+b^2)/2)`: The root mean square.

`sqrt p = sqrt(a*b)`. The geometric mean.

`2*p/s = 2*a*b/(a+b)`. The harmonic mean.

# Answer
> 2 votes
# Jelly, 17 bytes

```
²Æm,P½S
PḤ÷S+Ç+Æm

```

Try it online!

# Answer
> 2 votes
# MATL, ~~21~~ ~~18~~ 17 bytes

```
UYmGphX^GYmGpy/vs

```

Try it online!

-3 bytes thanks to Luis Mendo.

### Explanation

```
UYm               % Mean of squares,
                  % Stack: { (a^2+b^2)/2 }
   Gp             % Product of input, a*b
                  % Stack: { (a^2+b^2)/2, a*b }
     hX^          % Concatenate into array, take square root of each element.
                  % Stack: { [RMS, HM] }
        GYm       % Arithmetic mean of input.
                  % Stack: { [RMS,GM], AM }
           Gpy    % Product of input, duplicate AM from below.
                  % Stack: { [RMS,GM], AM, a*b, AM
              /   % Divide to get HM
                  % Stack { [RMS,GM], AM, HM}
               vs % Concatenate all to get [RMS,GM,AM,HM], sum.

```

# Answer
> 2 votes
# 05AB1E, ~~18~~ 16 bytes

-2 bytes thanks to Erik the Outgolfer

```
nO;t¹O;¹Pt2¹zO/O

```

Explanation:

```
nO;t                Root mean square
n                    Raise [a, b] to [a ** 2, b ** 2]
 O                   Sum
  ;                  Half
   t                 Square root
    ¹O;             Arithmetic mean
    ¹                Retrieve stored [a, b]
     O               Sum
      ;              Half
       ¹Pt          Geometric mean
       ¹             Retrieve stored [a, b]
        P            Product
         t           Square root
          2¹zO/     Harmonic mean
           ¹         Retrieved stored [a, b]
            z        Vectorised inverse to [1 / a, 1 / b]
             O       Sum
          2   /      Get 2 divided by the sum
               O    Sum of all elements in stack

```

Try it online!

# Answer
> 2 votes
# Husk, 19 bytes

```
ṁëȯ√½ṁ□o½Σo√Π§/ΣoDΠ

```

Try it online!

-1 thanks to H.PWiz.

# Answer
> 2 votes
# Ohm v2, 16 bytes

```
²Σ½¬³Π¬³Σ½D³Πs/Σ

```

Try it online!

## Explanation

```
square sum halve sqrt input product sqrt input sum halve dupe input product swap div sum

```

...if Ohm had a verbose mode of sorts. :P

```
²Σ½¬³Π¬³Σ½D³Πs/Σ

                  implicit input       [[7, 6]]
²Σ½¬              root mean square
²                  square              [[49, 36]]
 Σ                 sum                 [85]
  ½                halve               [42.5]
   ¬               square root         [6.519]
    ³Π¬           geometric mean
    ³              push first input    [6.519, [7, 6]]
     Π             product             [6.519, 42]
      ¬            square root         [6.519, 6.481]
       ³Σ½        arithmetic mean
       ³           push first input    [6.519, 6.481, [7, 6]]
        Σ          sum                 [6.519, 6.481, 13]
         ½         halve               [6.519, 6.481, 6.500]
          D³Πs/   harmonic mean
          D        duplicate           [6.519, 6.481, 6.500, 6.500]
           ³       push first input    [6.519, 6.481, 6.500, 6.500, [7, 6]]
            Π      product             [6.519, 6.481, 6.500, 6.500, 42]
             s     swap                [6.519, 6.481, 6.500, 42, 6.500]
              /    divide              [6.519, 6.481, 6.500, 6.461]
               Σ  sum                  [25.961]
                  implicit output      [25.961]

```

# Answer
> 2 votes
# TI-Basic (TI-84 Plus CE), ~~27~~ 25 bytes

```
√(sum(Ans<sup>2</sup>)/2)+mean(Ans)+2prod(Ans)/sum(Ans)+√(prod(Ans

```

-2 bytes from Scrooble

Takes a list of two numbers in `Ans`, and implicitly returns the sum of the four means; e.g. run with `{7,6}:prgmNAME` to get `25.96148157`.

Explanation:

`√(sum(Ans<sup>2</sup>)/2)`: 8 bytes: root mean square

`mean(Ans)`: ~~5~~ 3 bytes: arithmetic mean (old: `sum(Ans)/2`)

`2prod(Ans)/sum(Ans)`: 8 bytes: harmonic mean

`√(prod(Ans`: 3 bytes: geometric mean

+3 bytes for 3 `+`es

# Answer
> 1 votes
# SOGL V0.12, 22 bytes

```
+:A½.².²+½√..*:√;«a/¹∑

```

Try it Here!

# Answer
> 1 votes
# Dyalog APL, 44 bytes

```
{+/(2×o÷k),(.5×k←⍺+⍵),.5*⍨(o←⍺×⍵),.5×+/⍺⍵*2}

```

Try it online!

Dyadic dfns with `a` on the left and `b` on the right.

# Answer
> 1 votes
# C# (.NET Core), 76 bytes

+13 bytes for `using System;`

```
a=>b=>Math.Sqrt((a*a+b*b)/2)+(a+b)/2+Math.Sqrt(a*b)+2/(1/a+1/b)

```

Try it online!

# Answer
> 1 votes
# Julia, ~~49~~ 47 bytes

```
a$b=(x=a+b)/2+((a^2+b^2)/2)^.5+(y=a*b)^.5+2*y/x

```

Try it online!

# Answer
> 1 votes
# JavaScript, 47 bytes

```
a=>b=>(c=a+b)/2+(c*c/2-(d=a*b))**.5+d**.5+2*d/c

```

quite trivial

```
f =

a=>b=>(c=a+b)/2+(c*c/2-(d=a*b))**.5+d**.5+2*d/c
```

```
<div oninput="r.value = f(+a.value)(+b.value)">
<p><label>a = <input id="a" type="number" step="any" value="1" /></label></p>
<p><label>b = <input id="b" type="number" step="any" value="1" /></label></p>
</div>
<p>result = <output id="r">4</output></label></p>
```

# Answer
> 1 votes
# ARBLE, ~~49~~ 45 bytes

*-4 bytes thanks to Mr. Xcoder*

```
((a^2+b^2)/2)^.5+(a+b)/2+(a*b)^.5+2*a*b/(a+b)

```

Try it online!

# Answer
> 1 votes
# Java 8, 63 bytes

```
a->b->Math.sqrt((a*a+b*b)/2)+(a+b)/2+Math.sqrt(a*b)+2/(1/a+1/b)

```

Takes both parameters as `Double` and outputs as `Double`.
Try it here.

Or (also **63 bytes**):

```
a->b->(a+b+Math.sqrt(a*a+b*b<<1))/2+Math.sqrt(a*b)+2d*a*b/(a+b)

```

Takes both parameters as `Integer` and outputs as `Double`.
Try it here.

# Answer
> 1 votes
# Python 2, 58 bytes

```
lambda a,b:((a*a+b*b)/2)**.5+(a+b)/2+(a*b)**.5+2*a*b/(a+b)

```

Try it online!

Takes input as floats

# Answer
> 1 votes
# Actually, 15 bytes

```
æßπ√+ßΣßπτ/+ßµ+

```

Try it online!

Yay Actually has a built-in for Root Square Mean!

```
æßπ√+ßΣßπτ/+ßµ+  ~ Full program.

æ                ~ Arithmetic mean.
 ßπ√             ~ Product, Square root (computes geometric mean).
    +            ~ Addition.
     ßΣ          ~ Push the sum of the input.
       ßπτ       ~ Push the product of the input doubled.
          /      ~ Divide.
           +     ~ Addition.
            ßµ   ~ Push Root Square Mean.
              +  ~ Addition.

```

# Answer
> 1 votes
## Groovy, 54 bytes

```
{a,b->c=a+b;((a*a+b*b)/2)**0.5+c/2+(a*b)**0.5+2*a*b/c}

```

-2 thanks to Mr. Xcoder for an edit that made me feel dumb.

# Answer
> 0 votes
# Jq 1.5, 76 bytes

```
[pow((map(pow(.;2))|add)/2;.5),add/2,pow(.[0]*.[1];.5),2/(map(1/.)|add)]|add

```

Expanded

```
[
  pow((map(pow(.;2))|add)/2;.5)  # root mean square
, add/2                          # arithmetic mean
, pow(.[0]*.[1];.5)              # geometric mean
, 2/(map(1/.)|add)               # harmonic mean
]
| add                            # that just about sums it up for mean

```

Try it online!

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


# Question
Title: Number of distinct non-empty subsequences of binary expansion
A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of `100` are `0`, `1`, `00`, `10`, `100`. The distinct non-empty subsequences of `1010` are `0`, `1`, `00`, `01`, `10`, `11`, `010`, `100`, `101`, `110`, `1010`.

Write a program or function that given a positive integer *n* returns the number of distinct non-empty subsequences of the binary expansion of *n*.

Example: since `4` is `100` in binary, and we saw that it had five distinct non-empty subsequences above, so `f(4) = 5`. Starting from *n = 1*, the sequence begins:

```
1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12

```

However, your program must work for any *n \< 250* in under a second on any modern machine. Some large examples:

```
f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674

```

# Answer
> 10 votes
# Python 3, ~~95 bytes~~ 83 bytes

\[-12 bytes thanks to Mr.XCoder :)\]

```
def f(x):
 v=[2,1];c=1
 for i in bin(x)[3:]:k=int(i);c+=v[k];v[1-k]+=v[k]
 return c

```

Try it online!

A note on the algorithm. The algorithm computes the increment in unique subsequences given by the bit at a given position t. The increment for the first bit is always 1. The algorithm then runs over the sequence of bits s(t) and adds the increment v\[s(t)\]. At each step, the increment for the complement of s(t), v\[1 - s(t)\] is updated to v\[1\]+v\[0\]. The final number is the sum of all increments.

It should run in O(log2(n)), where n is the input number.

# Answer
> 8 votes
# JavaScript (ES6), ~~53~~ 51 bytes

```
f=(n,r=~(a=[]))=>n<1?~r:f(n/2,r*2-~~a[n&=1],a[n]=r)

```

### Test cases

```
f=(n,r=~(a=[]))=>n<1?~r:f(n/2,r*2-~~a[n&=1],a[n]=r)

console.log(f(1099511627775))   // 40
console.log(f(1099511627776))   // 81
console.log(f(911188917558917)) // 728765543
console.log(f(109260951837875)) // 447464738
console.log(f(43765644099))     // 5941674
```

### Formatted and commented

```
f = (                      // f is a recursive function taking:
  n,                       //   n = integer
  r = ~(                   //   r = last result, initially set to -1
    a = []                 //   and using a[] = last results for 0 and 1,
  )                        //   implicitly initialized to [0, 0]
) =>                       //
  n < 1 ?                  // if n is less than 1:
    ~r                     //   we're done: return -(r + 1)
  :                        // else:
    f(                     //   do a recursive call with:
      n / 2,               //     n / 2
      r * 2 - ~~a[n &= 1], //     updated result = r * 2 - last result for this binary digit
      a[n] = r             //     update last result for this binary digit
    )                      //   end of recursive call

```

# Non-recursive version, 63 bytes

*Saved 3 bytes thanks to @ThePirateBay*

```
s=>[...s.toString(2)].map(l=c=>l[p=r,r=r*2-~~l[c],c]=p,r=1)|r-1

```

### Test cases

```
let f =

s=>[...s.toString(2)].map(l=c=>l[p=r,r=r*2-~~l[c],c]=p,r=1)|r-1

console.log(f(1099511627775))   // 40
console.log(f(1099511627776))   // 81
console.log(f(911188917558917)) // 728765543
console.log(f(109260951837875)) // 447464738
console.log(f(43765644099))     // 5941674
```

# Answer
> 7 votes
# Python 2, 56 bytes

```
f=lambda x,a=1,b=1:x and f(x/2,a+~x%2*b,x%2*a+b)or a+b-2

```

Try it online!

Taking the method from NofP.

**59 bytes iteratively:**

```
x=input()
v=[1,1]
while x:v[x%2]=sum(v);x/=2
print sum(v)-2

```

Try it online!

# Answer
> 6 votes
# Jelly, 10 bytes

```
B3;BSṛ¦/’S

```

This uses @xnor's improvement on @NofP's algorithm.

Try it online!

### Background

Let **(a1, ..., an)** be a finite binary sequence. For each non-negative integer **k ≤ n**, define **ok** as the number of unique subsequences of **(a1, ..., ak)** that are either empty or end in **1**, **zk** as the number of unique subsequences that are either empty or end in **0**.

Clearly, **o0 = z0 = 1**, as the only subsequence of the empty sequence is the empty sequence.

For each index **k**, the total number of subsequences of **(a1, ..., ak)** is **ok \+ zk \- 1** (subtracting **1** accounts for the fact that both **ok** and **zk** count the empty sequence). The total number of *non-empty* subsequences is therefore **ok \+ zk \- 2**. The challenge asks to compute **on \+ zn \- 2**.

Whenever **k \> 0**, we can compute **ok** and **zk** recursively. There are two cases:

* ### ak = 1

**zk = zk-1**, since **(a1, ..., ak-1)** and **(a1, ..., ak-1, 1)** have the same subsequences that end in **0**.

For each of the **ok \- 1** non-empty subsequences of **(a1, ..., ak)** that end in **1**, we can remove the trailing **1** to obtain one of the **ok-1 \+ zk-1 \- 1** subsequences **(a1, ..., ak-1)**. Conversely, appending a **1** to each of the latter **ok-1 \+ zk-1 \- 1** sequences results in one of the **ok \- 1** former sequences. Thus, **ok \- 1 = ok-1 \+ zk-1 \- 1** and **ok = ok-1 \+ zk-1**.
* ### ak = 0

Similarly to the previous case, we obtain the recursive formulae **ok = ok-1** and **zk = zk-1 \+ ok-1**.

### How it works

```
B3;BSṛ¦/’S  Main link. Argument: n (positive integer)

B           Binary; convert n to base 2.
 3;         Prepend a 3.
   B        Binary; convert all integers in the resulting array to base 2, mapping
            0 to [0], 1 to [1], and the prepended 3 to [1, 1].
       /    Reduce the resulting array by the quicklink to the left, which will be
            called with left argument [x, y] (integer pair) and right argument [j]
            (either [0] or [1]).
      ¦     Sparse application.
    S           Compute the sum (x + y) and...
     ṛ          for each index in the right argument (i.e., for j)...
            replace the element of [x, y] at that index with (x + y).
       ’    Decrement both integers in the resulting pair.
        S   Take the sum.

```

# Answer
> 4 votes
# 05AB1E, 12 bytes

```
0¸sbvDO>yǝ}O

```

Try it online! Explanation: As pointed out by the other answers, the number of subsequences for a binary string `a..y0` that end in a 1 is the same as the number for the binary string `a..y`, while the number that end in a `0` is the total number of subsequences for the binary string `a..y` (which each gain a `0` suffix) plus one for `0` itself. Unlike the other answers I don't include the empty subsequence as this saves a byte constructing the initial state.

```
0¸s             Push [0] under the input
   b            Convert the input to binary
    v     }     Loop over the digits
     D          Duplicate the array
      O         Take the sum
       >        Increment
        yǝ      Replace the index corresponding to the binary digit
           O    Take the sum of the final array

```

# Answer
> 1 votes
# Java 8, 97 bytes

```
n->f(n,1,1)long f(long n,long a,long b){return n>0?f(n/2,a+Math.floorMod(~n,2)*b,n%2*a+b):a+b-2;}

```

Port of *@xnor*'s Python 2 answer, which in turn is an improvement of *@NofP*'s Python 3 answer.

Try it here.

---

Maybe it's a good thing the -tag was present, because I initially had the following to bruteforce all subsequences:

```
import java.util.*;n->p(n.toString(n,2)).size()-1;Set p(String s){Set r=new HashSet();r.add("");if(s.isEmpty())return r;Set q=p(s.substring(1));r.addAll(q);for(Object o:q)r.add(""+s.charAt(0)+o);return r;}

```

Try it here.

Which also worked, but took way too long for the last three test cases. Not to mention it's way longer (**~~208~~ 204 bytes**).

# Answer
> 1 votes
# 6502 machine code (C64), 321 bytes

```
00 C0 20 FD AE A2 00 9D 4F C1 E8 20 73 00 90 F7 9D 4F C1 A0 FF C8 B9 4F C1 D0
FA A2 15 CA 88 30 0A B9 4F C1 29 0F 9D 4F C1 10 F2 A9 00 9D 4F C1 CA 10 F8 A9
00 A0 07 99 64 C1 88 10 FA A0 40 A2 6C 18 BD E4 C0 90 02 09 10 4A 9D E4 C0 E8
10 F2 A2 07 7E 64 C1 CA 10 FA 88 F0 13 A2 13 BD 50 C1 C9 08 30 05 E9 03 9D 50
C1 CA 10 F1 30 D1 A2 0F A9 00 9D 3F C1 CA D0 FA A9 01 8D 3F C1 8D 47 C1 A2 08
CA BD 64 C1 F0 FA A0 09 1E 64 C1 88 90 FA B0 0A CA 30 28 A0 08 1E 64 C1 90 04
A9 47 B0 02 A9 4F 8D AF C0 86 FE A2 F8 18 BD 47 C0 7D 4F C0 9D 47 C0 E8 D0 F4
A6 FE 88 D0 DC F0 D5 A2 F8 BD 47 C0 7D 4F C0 9D 6C C0 E8 D0 F4 AD 64 C1 E9 01
8D 64 C1 A2 F9 BD 6C C0 E9 00 9D 6C C0 E8 D0 F5 A0 15 A9 00 99 4E C1 88 D0 FA
A0 40 A2 13 BD 50 C1 C9 05 30 05 69 02 9D 50 C1 CA 10 F1 0E 64 C1 A2 F9 3E 6C
C0 E8 D0 FA A2 13 BD 50 C1 2A C9 10 29 0F 9D 50 C1 CA 10 F2 88 D0 D1 E0 14 F0
06 E8 BD 4F C1 F0 F6 09 30 99 4F C1 C8 E8 E0 15 F0 05 BD 4F C1 90 F0 A9 00 99
4F C1 A9 4F A0 C1 4C 1E AB

```

**Online demo**

**Online demo with error checking** (346 bytes)

**Usage:** `sys49152,[n]`, e.g. `sys49152,911188917558917`.

The time restriction and the test-cases require solutions to calculate in 64bit numbers, so time to prove the C64 qualifies as "**modern machine**" ;)

Of course, this needs quite a bit of code, the OS doesn't provide **anything** for integers wider than 16bit. The lame part here: it's *yet another implementation* (slightly modified) of NofP's algorithm resp. xnor's improved variant. Thanks for the idea ;)

---

### Explanation

Here's a commented disassembly listing of the relevant part doing the algorithm:

```
.C:c06c  A2 0F       LDX #$0F           ; 15 bytes to clear
.C:c06e  A9 00       LDA #$00
.C:c070   .clearloop:
.C:c070  9D 3F C1    STA .num_a,X
.C:c073  CA          DEX
.C:c074  D0 FA       BNE .clearloop
.C:c076  A9 01       LDA #$01           ; initialize num_a and num_b
.C:c078  8D 3F C1    STA .num_a         ; to 1
.C:c07b  8D 47 C1    STA .num_b
.C:c07e  A2 08       LDX #$08           ; 8 bytes of input to check,
.C:c080   .findmsb:                     ; start at most significant
.C:c080  CA          DEX
.C:c081  BD 64 C1    LDA .nc_num,X
.C:c084  F0 FA       BEQ .findmsb       ; repeat until non-0 byte found
.C:c086  A0 09       LDY #$09           ; 8 bits to check (+1 for pre dec)
.C:c088   .findbit:
.C:c088  1E 64 C1    ASL .nc_num,X      ; shift left, highest bit to carry
.C:c08b  88          DEY
.C:c08c  90 FA       BCC .findbit       ; bit was zero -> repeat
.C:c08e  B0 0A       BCS .loopentry     ; jump into calculation loop
.C:c090   .mainloop:
.C:c090  CA          DEX                ; next byte
.C:c091  30 28       BMI .done          ; index -1? -> done calculating
.C:c093  A0 08       LDY #$08           ; 8 bits to check
.C:c095   .bitloop:
.C:c095  1E 64 C1    ASL .nc_num,X      ; shift left, highest bit to carry
.C:c098  90 04       BCC .tgt_b         ; if 0, store addition result in num_b
.C:c09a   .loopentry:
.C:c09a  A9 47       LDA #$47
.C:c09c  B0 02       BCS .tgt_a         ; ... else store in num_a ...
.C:c09e   .tgt_b:
.C:c09e  A9 4F       LDA #$4F
.C:c0a0   .tgt_a:
.C:c0a0  8D AF C0    STA $C0AF          ; ... using self-modification.
.C:c0a3  86 FE       STX $FE            ; save byte index
.C:c0a5  A2 F8       LDX #$F8           ; index for adding
.C:c0a7  18          CLC
.C:c0a8   .addloop:
.C:c0a8  BD 47 C0    LDA $C047,X        ; load byte from num_a
.C:c0ab  7D 4F C0    ADC $C04F,X        ; add byte from num_b
.C:c0ae  9D 47 C0    STA $C047,X        ; store to num_a or num_b
.C:c0b1  E8          INX                ; next index
.C:c0b2  D0 F4       BNE .addloop       ; done if index overflown
.C:c0b4  A6 FE       LDX $FE            ; restore byte index
.C:c0b6  88          DEY                ; decrement bit index
.C:c0b7  D0 DC       BNE .bitloop       ; bits left in current byte -> repeat
.C:c0b9  F0 D5       BEQ .mainloop      ; else repeat main loop
.C:c0bb   .done:
.C:c0bb  A2 F8       LDX #$F8           ; index for adding
.C:c0bd   .addloop2:
.C:c0bd  BD 47 C0    LDA $C047,X        ; load byte from num_a
.C:c0c0  7D 4F C0    ADC $C04F,X        ; add byte from num_b
.C:c0c3  9D 6C C0    STA $C06C,X        ; store to nc_num (result)
.C:c0c6  E8          INX                ; next index
.C:c0c7  D0 F4       BNE .addloop2      ; done if index overflown
.C:c0c9  AD 64 C1    LDA .nc_num        ; load least significant result byte
.C:c0cc  E9 01       SBC #$01           ; subtract 2 (1 + negated carry)
.C:c0ce  8D 64 C1    STA .nc_num        ; store least significant result byte
.C:c0d1  A2 F9       LDX #$F9           ; index for subtract
.C:c0d3   .subloop:
.C:c0d3  BD 6C C0    LDA $C06C,X        ; subtract 0 from all other bytes
.C:c0d6  E9 00       SBC #$00           ; for handling carry if necessary
.C:c0d8  9D 6C C0    STA $C06C,X
.C:c0db  E8          INX
.C:c0dc  D0 F5       BNE .subloop

```

The rest is input/output and converting between string and 64bit unsigned integer (little-endian) using some double-dabble algorithm. In case you're interested, here's the whole assembly source for the version with error-checking -- the "golfed" version is in the branch "golf".

---
Tags: code-golf, combinatorics, binary, subsequence, restricted-time
---