title: Blind binary adder

text:
# Question
Title: Blind binary adder
Imagine you have two boxes `B(x)` and `B(y)`, each containing an unknown bit - 0 or 1, and a machine `F` that can X-ray them and produce a third box for `B(x^y)` (*xor*). `F` can also compute `B(x*y)` (*and*). In fact, those are just special cases of the the single operation the machine can perform - *inner product each*, denoted with `F()` below.

For two same-length arrays

```
[B(x[0]), B(x[1]), ..., B(x[n-1])]
[B(y[0]), B(y[1]), ..., B(y[n-1])]

```

*inner product* is defined as

```
B(x[0]*y[0] ^ x[1]*y[1] ^ ... ^ x[n-1]*y[n-1])

```

"*Each*" means `F()` can process multiple pairs of `x[]`, `y[]` in one go. The `x[]` and `y[]` from one pair must be of the same length; `x[]`-s and `y[]`-s from different pairs don't necessarily need to.

Boxes are represented by unique integer ids.

An implementation of *inner product each* in JavaScript might look like

```
var H=[0,1];          // hidden values, indexed by boxId
function B(x) {       // seal x in a new box and return the box id
  return H.push(x)-1;
}
function F(pairs) {   // "inner product each"
  return pairs.map(function (pair) {
    var r = 0, x = pair[0], y = pair[1];
    for (var i = 0; i < x.length; i++) r ^= H[x[i]] * H[y[i]];
    return B(r);
  })
}

```

(Please translate the above to your language of choice.)

Given access to an `F()` implementation as appropriate for your language (but no access to `H` or `B()`) and given two arrays of box ids constituting the 16-bit binary representations of two integers `a` and `b`, your task is to produce box ids for the 16-bit binary representation of `a+b` (discarding overflow) with the minimum number of `F()` calls.

The solution that calls `F()` the fewest times wins. Ties will be broken by counting the total number of `x[],y[]` pairs `F()` was called with - fewer is better. If still tied, the size of your code (excluding the implementation of `F()` and its helpers) determines the winner in the traditional code golf way. Please use a title like "MyLang, 123 calls, 456 pairs, 789 bytes" for your answer.

Write a function or a complete program. Input/output/arguments/result is int arrays in any reasonable format. Binary representation may be little- or big-endian - choose one.

---

Appendix 1: To make the challenge slightly easier, you can assume that boxes with ids 0 and 1 contain the values 0 and 1. This gives you constants, useful e.g. for negation (`x^1` is "not"). There were ways around the lack of constants, of course, but the rest of the challenge is hard enough anyway, so let's eliminate this distraction.

---

Appendix 2: To win the bounty, you must do one of the following:

* post your score (calls,pairs,bytes) and your code before the deadline
* post your score and a sha256 hash of your code before the deadline; then post the actual code within 23 hours after the deadline

# Answer
> 6 votes
# Python 3, 5 calls, 92 pairs, 922 bytes

## ~~Python 3, 5 calls, 134 pairs, 3120 bytes~~

## ~~Python 3, 6 calls, 106 pairs, 2405 bytes~~

## ~~\[JavaScript (Node.js)\], 9 calls, 91 pairs, 1405 bytes~~

## ~~JavaScript (Node.js), 16 calls, 31 pairs, 378 bytes~~

```
def add(F,a,b):r=[];p=lambda x:(x,x);q=lambda u,v,t:([u,v]+t[0],[u,v]+t[1]);s=lambda c,k,n:([e[j][n]for j in range(k,-1,-1)]+[f[n]],[c]+f[n-k:n+1]);t=lambda c,k,n:q(a[n],b[n],s(c,k,n-1));z=F([p([a[i],b[i]])for i in range(16)]+[([a[i]],[b[i]])for i in range(16)]);e=[z[0:16]];f=z[16:32];r+=[e[0][0]];c=f[0];z=F([p([a[1],b[1],c]),([e[0][1],f[1]],[c,f[1]])]+[([e[0][i]],[e[0][i-1]])for i in range(3,16)]);r+=[z[0]];c=z[1];e+=[[0]*3+z[2:15]];z=F([p([a[2],b[2],c]),t(c,0,3),s(c,1,3)]+[([e[j][i]],[e[1][i-j-1]])for j in range(2)for i in range(6+j,16)]);r+=z[0:2];c=z[2];e+=u(2,4,z[3:]);z=F([p([a[4],b[4],c])]+[t(c,i,i+5)for i in range(0,3)]+[s(c,3,7)]+[([e[j][i]],[e[3][i-j-1]])for j in range(4)for i in range(12+j,16)]);r+=z[0:4];c=z[4];e+=u(4,8,z[5:]);z=F([p([a[8],b[8],c])]+[t(c,i,i+9) for i in range(0,7)]);return r+z
def u(b,e,z):
	j=0;w=[0]*(e-b)
	for i in range(b,e):w[i-b]=[0]*(i+e)+z[j:j+16-(i+e)];j+=16-(i+e)
	return w

```

Try it online!

**FIRST VERSION** Okay that's not golfed. It's just an adaptation of @ngn's code.

The only idea here is that you don't need to compute the last carry since you discard overflow. Also, the calls of `F` are grouped by two. Maybe they may be grouped in another way, but I doubt you can reduce significantly the number of pairs, due to the nature of the basic addition algorithm.

**EDIT**: Still not golfed. The number of pairs could certainly be reduced, and probably the number of calls too. See https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 for a "proof" with sympy.

**EDIT 2** Switched to Python because it's more readable for me. Now I have got the general formula, I think I may reach the limit of 5 (maybe 4) calls.

**EDIT 3** Here are the basic bricks:

```
alpha[i] = a[i] ^ b[i]
beta[i] = a[i] * b[i]
c[0] = beta[0]
r[0] = alpha[0]

```

The general formula is:

```
c[i] = alpha[i]*c[i-1] ^ beta[i]
r[i] = a[i] ^ b[i] ^ c[i-1]

```

The expanded version is:

```
c[0] = beta[0]
c[1] = alpha[1]*beta[0] ^ beta[1]
c[2] = alpha[2]*alpha[1]*beta[0] ^ alpha[2]*beta[1] ^ beta[2]
c[3] = alpha[3]*alpha[2]*alpha[1]*beta[0] ^ alpha[3]*alpha[2]*beta[1] ^ alpha[3]*beta[2] ^ beta[3]
...
c[i] = alpha[i]*...*alpha[1]*beta[0] ^ alpha[i]*...*alpha[2]*beta[1] ^ .... ^ alpha[i]*beta[i-1] ^ beta[i]

```

5 calls seems the limit for me. Now I have a little work to remove pairs and golf it!

**EDIT 4** I golfed this one.

Ungolfed version:

```
def add(F, a, b):
    r=[]
    # p is a convenient way to express x1^x2^...x^n
    p = lambda x:(x,x)
    # q is a convenient way to express a[i]^b[i]^carry[i-1]
    q = lambda u,v,t:([u,v]+t[0],[u,v]+t[1])

    # step1: the basic bricks
    z=F([p([a[i],b[i]]) for i in range(16)]+[([a[i]],[b[i]]) for i in range(16)])
    alpha=z[0:16];beta=z[16:32]
    r.append(alpha[0])
    c = beta[0]

    # step 2
    z=F([
        p([a[1],b[1],c]),
        ([alpha[1],beta[1]],[c,beta[1]])
        ]+[([alpha[i]],[alpha[i-1]]) for i in range(3,16)])
    r.append(z[0])
    c = z[1] # c[1]
    alpha2=[0]*3+z[2:15]
    assert len(z)==15, len(z)

    # step 3
    t0=([alpha[2],beta[2]],[c,beta[2]])
    t1=([alpha2[3],alpha[3],beta[3]],[c,beta[2],beta[3]])
    z=F([
        p([a[2],b[2],c]),
        q(a[3],b[3],t0),
        t1]+
        [([alpha[i]],[alpha2[i-1]]) for i in range(6,16)]+
        [([alpha2[i]],[alpha2[i-2]]) for i in range(7,16)])
    r.extend(z[0:2])
    c = z[2] # c[3]
    alpha3=[0]*6+z[3:13]
    alpha4=[0]*7+z[13:22]
    assert len(z)==22, len(z)

    # step 4
    t0=([alpha[4],beta[4]],[c,beta[4]])
    t1=([alpha2[5],alpha[5],beta[5]],[c,beta[4],beta[5]])
    t2=([alpha3[6],alpha2[6],alpha[6],beta[6]],[c,beta[4],beta[5],beta[6]])
    t3=([alpha4[7],alpha3[7],alpha2[7],alpha[7],beta[7]],[c,beta[4],beta[5],beta[6],beta[7]])
    z=F([
        p([a[4],b[4],c]),
        q(a[5],b[5],t0),
        q(a[6],b[6],t1),
        q(a[7],b[7],t2),
        t3]+
        [([alpha[i]],[alpha4[i-1]]) for i in range(12,16)]+
        [([alpha2[i]],[alpha4[i-2]]) for i in range(13,16)]+
        [([alpha3[i]],[alpha4[i-3]]) for i in range(14,16)]+
        [([alpha4[i]],[alpha4[i-4]]) for i in range(15,16)])
    r.extend(z[0:4])
    c = z[4] # c[7]
    alpha5 = [0]*12+z[5:9]
    alpha6 = [0]*13+z[9:12]
    alpha7 = [0]*14+z[12:14]
    alpha8 = [0]*15+z[14:15]
    assert len(z) == 15, len(z)

    # step 5
    t0=([alpha[8],beta[8]],[c,beta[8]])
    t1=([alpha2[9],alpha[9],beta[9]],[c,beta[8],beta[9]])
    t2=([alpha3[10],alpha2[10],alpha[10],beta[10]],[c,beta[8],beta[9],beta[10]])
    t3=([alpha4[11],alpha3[11],alpha2[11],alpha[11],beta[11]],[c,beta[8],beta[9],beta[10],beta[11]])
    t4=([alpha5[12],alpha4[12],alpha3[12],alpha2[12],alpha[12],beta[12]],[c,beta[8],beta[9],beta[10],beta[11],beta[12]])
    t5=([alpha6[13],alpha5[13],alpha4[13],alpha3[13],alpha2[13],alpha[13],beta[13]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13]])
    t6=([alpha7[14],alpha6[14],alpha5[14],alpha4[14],alpha3[14],alpha2[14],alpha[14],beta[14]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13],beta[14]])
    t7=([alpha8[15],alpha7[15],alpha6[15],alpha5[15],alpha4[15],alpha3[15],alpha2[15],alpha[15],beta[15]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13],beta[14],beta[15]])

    z=F([
        p([a[8],b[8],c]),
        q(a[9],b[9],t0),
        q(a[10],b[10],t1),
        q(a[11],b[11],t2),
        q(a[12],b[12],t3),
        q(a[13],b[13],t4),
        q(a[14],b[14],t5),
        q(a[15],b[15],t6)
    ])
    r.extend(z)
    return r

```

Try it online!

# Answer
> 2 votes
# Haskell, 1 call (cheating???), 32 pairs (could be improved), 283 bytes (same)

Please don't be angry with me, I don't want to win with this, but I was encouraged in the remarks to the challenge to explain what I was talking about.

I tried to use the state monad to handle adding boxes and counting calls and pairs, and that worked, but I didn't manage to make my solution working in that setting. So I did what was also suggested in the comments: just hide the data behind a data constructor and don't peek. (The clean way would be to use a seperate module and not export the constructor.) This version has the advantage of being much simpler.

Since we are talking about boxes of bits, I put `Bool` values into them. I define `zero` as the given box with the zero bit - a `one` is not needed.

```
import Debug.Trace

data B = B { unB :: Bool }

zero :: B
zero = B False

f :: [([B],[B])] -> [B]
f pairs =  trace ("f was called with " ++ show (length pairs) ++ " pairs") $
           let (B i) &&& (B j) = i && j
           in map (\(x,y) ->  B ( foldl1 (/=) (zipWith (&&&) x y))) pairs

```

We're using the debugging function `trace` to see how often `f` was called, and with how many pairs. `&&&` looks into the boxes by pattern matching, the inequality `/=` used on `Bool` values is `xor`.

```
bits :: Int -> [Bool]
bits n = bitsh n 16
  where bitsh _ 0 = []
        bitsh n k = odd n : bitsh (n `div` 2) (k-1)

test :: ( [B] -> [B] -> [B] ) -> Int -> Int -> Bool
test bba n m = let x = map B (bits n)
                   y = map B (bits m)
                   r = bba x y
                   res = map unB r
               in res==bits(n+m)

```

The `test` function takes a blind binary adder as first argument, and then two numbers for which addition is tested. It returns a `Bool` indicating whether the test was successful. First the input boxes are created, then the adder is called, the result unboxed (with `unB`) and compared with the expected result.

I implemented two adders, the sample solution `simple`, so that we can see that the debug output works correctly, and my solution using value recursion `valrec`.

```
simple a b = let [r0] = f [([a!!0,b!!0],[a!!0,b!!0])]
                 [c]  = f [([a!!0],[b!!0])]
             in loop 1 [r0] c
             where loop 16 rs _ = rs
                   loop i  rs c = let [ri] = f [([a!!i,b!!i,c],[a!!i,b!!i,c])]
                                      [c'] = f [([a!!i,b!!i,c],[b!!i,c,a!!i])]
                                  in loop (i+1) (rs++[ri]) c'

valrec a b =
    let res = f (pairs res a b)
    in [ res!!i | i<-[0,2..30] ]
  where pairs res a b =
           let ts = zipWith3 (\x y z -> [x,y,z])
                             a b (zero : [ res!!i | i<-[1,3..29] ]) in
           [ p | t@(h:r) <- ts, p <- [ (t,t), (t,r++[h]) ] ]

```

See how I'm defining `res` in terms of itself? That is also known as *tying the knot*.

Now we can see how `f` is only called once:

```
*Main> test valrec 123 456
f was called with 32 pairs
True

```

Or replace `valrec` by `simple` to see `f` being called 32 times.

Try it online! (the tracing output appears under "Debug")

# Answer
> 0 votes
# JavaScript, 32 calls, 32 pairs, 388 bytes

# Dyalog APL, 32 calls, 32 pairs, 270 bytes

This is a naïve sample solution that can serve as a template.

Note that the byte count must include only the section surrounded with "BEGIN/END SOLUTION".

Explanation:

I chose little-endian bit order (`x[0]` is the least significant bit).

Observe that single-bit addition mod 2 can be realised as `F([[[x,y],[x,y]]])` (that is: `x*x ^ y*y` \- multiplication mod 2 is idempotent) and binary multiplication as `F([[[x],[y]]])`.

We traverse the bits from least significant to most significant and at each step compute a result bit and a carry.

```
#!/usr/bin/env node
'use strict'
let H=[0,1]
,B=x=>H.push(x)-1
,nCalls=0
,nPairs=0
,F=pairs=>{
  nCalls++;nPairs+=pairs.length
  return pairs.map(([x,y])=>{let s=0;for(let i=0;i<x.length;i++)s^=H[x[i]]*H[y[i]];return B(s)})
}

// -----BEGIN SOLUTION-----
var f=(a,b)=>{
  var r=[], c // r:result bits (as box ids), c:carry (as a box id)
  r[0]=F([[[a[0],b[0]],[a[0],b[0]]]])          // r0 = a0 ^ b0
  c=F([[[a[0]],[b[0]]]])                       // c = a0*b0
  for(var i=1;i<16;i++){
    r.push(F([[[a[i],b[i],c],[a[i],b[i],c]]])) // ri = ai ^ bi ^ c
    c=F([[[a[i],b[i],c],[b[i],c,a[i]]]])       // c = ai*bi ^ bi*c ^ c*ai
  }
  return r
}
// -----END SOLUTION-----

// tests
let bits=x=>{let r=[];for(let i=0;i<16;i++){r.push(x&1);x>>=1}return r}
,test=(a,b)=>{
  console.info(bits(a))
  console.info(bits(b))
  nCalls=nPairs=0
  let r=f(bits(a).map(B),bits(b).map(B))
  console.info(r.map(x=>H[x]))
  console.info('calls:'+nCalls+',pairs:'+nPairs)
  console.assert(bits(a+b).every((x,i)=>x===H[r[i]]))
}

test(12345,6789)
test(12,3)
test(35342,36789)

```

The same in Dyalog APL (but using randomised box ids):

```
⎕io←0⋄K←(V←⍳2),2+?⍨1e6⋄B←{(V,←⍵)⊢K[≢V]}⋄S←0⋄F←{S+←1,≢⍵⋄B¨2|+/×/V[K⍳↑⍉∘↑¨⍵]}
⍝ -----BEGIN SOLUTION-----
f←{
  r←F,⊂2⍴⊂⊃¨⍺⍵        ⍝ r0 = a0 ^ b0
  c←⊃F,⊂,¨⊃¨⍺⍵        ⍝ c = a0*b0
  r,⊃{
    ri←⊃F,⊂2⍴⊂⍺⍵c     ⍝ ri = ai ^ bi ^ c
    c⊢←⊃F,⊂(⍺⍵c)(⍵c⍺) ⍝ c = ai*bi ^ bi*c ^ c*ai
    ri
  }¨/1↓¨⍺⍵
}
⍝ -----END SOLUTION-----
bits←{⌽(16⍴2)⊤⍵}
test←{S⊢←0⋄r←⊃f/B¨¨bits¨⍺⍵
      ⎕←(↑bits¨⍺⍵)⍪V[K⍳r]⋄⎕←'calls:' 'pairs:',¨S
      (bits⍺+⍵)≢V[K⍳r]:⎕←'wrong!'}
test/¨(12345 6789)(12 3)(35342 36789)

```

---
Tags: arithmetic, binary, atomic-code-golf
---


title: Stretch an array

text:
# Question
Title: Stretch an array
Earlier I defined the process of crushing an array

> In a crush we read the array left to right. If at a point we encounter two of the same element in a row we remove the first one and double the second one.

For example here is the process of crushing the following array

```
[5,2,2,4]
 ^
[5,2,2,4]
   ^
[5,2,2,4]
     ^
[5,4,4]
   ^
[5,4,4]
     ^
[5,8]
   ^

```

Note that the same element can be collapsed multiple times. In the example `2,2,4` was collapsed into `8` in a single pass.

Now crushing arrays is easy, whats hard is uncrushing them. Your task is to take an array of positive integers as input and output the largest array that can form the input when crushed repeatedly. For example the array `[4]` is formed by crushing `[2,2]` which is in turn formed by crushing `[1,1,1,1]`. Since we can't have non integer values `[1,1,1,1]` cannot be uncrushed any further and thus is our answer.

You will never receive a `0` in your input array because such arrays can be expanded indefinitely. You will also never receive a case with two of the same odd number next to each other, such cases cannot be the result of a crushing.

This is so answers will be scored with the size of their source measured in bytes with less bytes being better.

Before you start making your answer I just want to say that this challenge is significantly more difficult than it seems. Check your intuition as you go along and make sure your answer passes all the test cases.

## Test Cases

```
[] -> []
[5] -> [5]
[6] -> [3,3]
[8] -> [1,1,1,1,1,1,1,1]
[4,8] -> [1,1,1,1,1,1,1,1,1,1,2]
[2,8] -> [1, 1, 1, 1, 2, 1, 1, 1, 1]
[4,4] -> [1,1,1,1,1,1,1,1]

```

# Answer
# JavaScript (Node.js), ~~237~~ ~~221~~ ~~213~~ 186 bytes

```
f=a=>a.map(b=>{for(i=1;~b%2;b/=2)i*=2;return Array(i).fill(b)}).reduce((t,c,i,s)=>{b=c.slice();if(i)r=2*s[--i].length,b.length>=r&&b[0]==s[i][0]?b[r-2]+=b.pop():b;return t.concat(b)},[])

```

Try it online!

This algorithm computes optimal stretched arrays, by stretching each number to the max, and then, if necessary, it crushes back a pair of number at the right place, effectively creating a "crush blocker", interrupting the crush sequence of the preceding number.

For instance:

`[1, 1, 1, 1, 1, 1]` gives `[4,2]` once crushed, but `[1, 1, 1, 1, 2]` results in `[2, 4]`

The challenge is to determine where exactly a crush blocker should be placed so that crushing the resulting array gives the right result:

* A crush blocker needs to be placed only if the previous stretched number is equal to the current one, and if the current stretched sequence is greather than the previous one. For instance, `[2, 4]` requires a crush blocker (the stretched number is `1`, repeated, and `[1, 1]` is shorter than `[1,1,1,1]`), but `[4, 2]` and `[2, 6]` do not require one
* if we call `n` the previous stretched sequence, and if the condition above is verified, then the current sequence is a repetition of the `n` sequence. To interrupt the crush sequence of the previous number, we need to place the crush blocker at the end of the second `n` sequence of the current number to stretch. Example: `[2, 8] => [(1, 1)=n, (1, 1) + (2) + (1, 1) + ...]`, or `[4, 8] => [(1, 1, 1, 1)=n, (1, 1, 1, 1) + (1, 1, 2) + ...]`
> 2 votes

# Answer
# Jelly, 42 bytes

```
ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿċ³
ṗÐ€⁸ẎS⁼¥Ðfµ€ŒpẎ€ÇÐfṪ

```

Try it online!

Full program. Extremely inefficient, but works.
> 1 votes

# Answer
# Python 2, 230 228 226 bytes

Works by iterating all possible lists with the same sum as the input one. Removing those that do not equal to the input array in some crushed state, selecting the longest one.

**Edit:** -2 bytes by removing the `if` in the main function

**Edit:** -2 bytes by removing two unnecessary square brackets

```
lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]
def c(x,y):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return x==y or~-e and c(x,y)
b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]

```

Try it online!

# Explanation

Main function, responsible for finding all possible solutions and selecting the longest one

```
lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]

```

Crush function, that checks if y is equal to one of the crushes.

```
def c(x,y):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return x==y or~-e and c(x,y)
```

Generate all possible permutations with the given sum

```
b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]

```
> 1 votes

# Answer
# 05AB1E, ~~41~~ 37 bytes

```
vy[DÉ#2÷]DYQX©NoDU‹&sDV¸X∍sić·®·Íǝ}»,

```

Try it online!

Port of my Javascript solution.

Explanations:

```
vy                   for each member of the list
[DÉ#2÷]              divide by 2 until odd: stack = stretched value, N = iterations
DYQ                  stetched value equal to the previous one?
X©NoDU‹              previous size < current one? (+store the new size in X)
&                    AND on the 2 previous tests
sDV¸X∍s              build a list of the new stretched value repeated X times
                      (+store the new stetched value in Y)
ić·®·Íǝ}             if the previous tests are true:
                       reduce the result list size by 1
                       multiply by 2 the number at the crush block position
»,                   join by newline + print the list

```
> 0 votes

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


title: Make a ;#*:) interpreter

text:
# Question
Title: Make a ;#*:) interpreter
A few month back, I made a language called `;#` (Semicolon Hash) and it started a little bit of a craze (it even got its own tag, as you can see). But, as with everything, the craze died down, and questions related to it stopped being posted.

However, a few people were annoyed at the lack of capability of `;#` and this lead to someone creating a Turing complete version. Eventually, I decided to create `;#` 2.0 with an extended set of commands:

```
; - Increment the accumulator
# - Modulo the accumulator by 127, output as ASCII character and reset the accumulator to 0
: - Open a while loop
) - Close a while loop. You can assume that all loops will be closed.
* - Take a byte of input, and add it to the accumulator. Input is recycled, so if the end of the input is reached, it wraps around to the start.

```

FYI: `;#*:)` still isn't Turing complete

For example, a cat program would be

```
*:#*)

*     - Take a byte of input
 :  ) - While the input character is not a null byte...
  #   -   Print as character
   *  -   Take a byte of input

```

For this, the input must be terminated with a null byte, otherwise the program will repeat the input until the heat death of the universe.

and to add two numbers (input and output as char codes):

```
**#

*   - Take input (e.g. \x02); A=2
 *  - Take input (e.g. \x03); A=5
  # - Output A as character (\x05)

```

Your task is to interpret `;#*:)`. Your program/function will be given 2 inputs, the program and the program's input, and you have to interpret the given program.

A few rules:

1) Your program may not halt termination due to an error unless 2) happens. Output to STDERR is allowed, just so long as it doesn't affect the program's execution.

2) If the second input is empty (a `;#*:)` program with no input) and `*` occurs in the code, you don't have to handle the error and can cause any kind of behaviour you want; summon Cthulhu, make Dennis lose his rep, anything you want.

3) All characters that aren't `;#*:)` are ignored and have no effect on anything.

Nested loops **can** happen, and all loops will be closed, so `;:*:#*);)` is valid code

**This is a code golf, so shortest code wins.**

Some tests to check your program against:

```
program, input (as ASCII characters; \xxx is a byte literal) => output

*#*:#*), "1" => 11111111...
**#, "12" => c
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;#, "abc" => Hello, World!
*#, "" => undefined
Hello, World!, "" => (nothing)
*:#*):;#*)*#, "Hello,\x00World!" => Hello,W
*:#*), "Testing\x00" => Testing
*:#*), "Testing" => TestingTestingTestingTesting...
;:*:#*);*), "123\x00" => 223d3d3d...

```

And, to help you even more, this is an ungolfed reference implementation in Python. In this version, I have decided to make the `*` on empty input be ignored.

Good luck!

# Answer
# Ruby, ~~147~~ 144 bytes

Saved 3 bytes thanks to m-chrzan!

```
z=STDIN.read
eval ARGV[i=a=0].gsub(/./){|e|"#{{?;=>"a+=1",?#=>"putc(a%127);a=0",?:=>"while a>0",?)=>"end",?*=>"a+=z[i%=z.size].ord;i+=1"}[e]};"}

```

Try it online!

Program is taken from first command line argument.
> 4 votes

# Answer
# Python 3, ~~261~~ 253 bytes

*-8 bytes thanks to @Mr.Xcoder*

```
p,i=eval(input());a=k=c=z=0;j=[];m={}
for y in p:
 if':'==y:j+=[z]
 if')'==y:b=j.pop();m[b]=z;m[z]=b
 z+=1
while p[c:]:
 y=p[c];a+=';'==y
 if'*'==y:a+=ord(i[k%len(i)]);k+=1
 if'#'==y:print(end=chr(a%127));a=0
 if y in':)':c=[c,m[c]][(a>0)>(')'<y)]
 c+=1

```

Try it online!

# Python 3, 253 bytes

Same length using `exec`

```
p,i=eval(input());a=k=c=z=0;j=[];m={}
for y in p:
 if':'==y:j+=[z]
 if')'==y:b=j.pop();m[b]=z;m[z]=b
 z+=1
while p[c:]:y=p[c];exec('a+=1 print(end=chr(a%127));a=0 a+=ord(i[k%len(i)]);k+=1 c=[c,m[c]][a<1] c=[c,m[c]][a>0] 1'.split()[';#*:)'.find(y)]);c+=1

```

Try it online!
> 1 votes

---
Tags: code-golf, interpreter
---


title: Code-Golf Assembly Line

text:
# Question
Title: Code-Golf Assembly Line
*Note: This challenge has nothing to do with actual assembly language.*

---

As the head of **Code-Golf Factory Inc.**, you must create an assembly line to generate a specific piece of code. Today, the foreman has asked you to produce quines.

# Specification:

In this challenge, the goal is to write a quine such that a proper subsection of it is also a quine.

This is code-golf, so the fewest bytes (of the main program) win. Standard loopholes are forbidden, and both the main program and the subsection must be true quines.

The subsection must be at least 2 characters shorter than the main program, meaning that the minimum score is 3 bytes.

You only need 1 subsection of your choice to work.

# Answer
> 6 votes
# JavaScript (ES6), 14 bytes

```
f=_=>"f="+f+""

```

Try it online!

This subsection is also a quine:

```
f=_=>"f="+f

```

Try it online!

# Answer
> 4 votes
# Jelly, 5 bytes

```
”ṘṘ10

```

Try it online!

The subsection `”ṘṘ` is also a quine. Try it online!

# Answer
> 3 votes
# CJam, 10 bytes

```
11"`_~"`_~

```

Try it online!

This is also a quine:

```
"`_~"`_~

```

Try it online!

# Answer
> 2 votes
# , 13 bytes

```
ñÉÑ~"qpx:2i2i

```

Try it online!

The subsection `2i2i` is also a quine.

# Answer
> 2 votes
# Alice, 13 bytes

```
"!&d<@o&dh.##

```

Try it online!

This is also a quine:

```
"!&d<@o&dh.

```

Try it online!

This modifies the standard quine by clearing the stack before the relevant string is pushed, and using the stack height to determine how many bytes to output. This allows any no-op to be added at the end.

# Answer
> 0 votes
# Python 2, 60 bytes

This is a really simple answer, so there's probably a shorter one. This is just the standard Python quine twice. The trailing newline is required.

```
_='_=%r;print _%%_';print _%_
_='_=%r;print _%%_';print _%_

```

**Try it online**

# Answer
> 0 votes
# Fission, 35 bytes

```
O abcdefghijklmnopqrstuvwxyz '#_OR"

```

Try it online!

An atom starts at `R` travelling right. The `"` toggles print mode, so it wraps around and prints everything until it encounters `"` again. This stops printing and sets the mass of the atom to the number of characters printed (34). It wraps around again, and `O` destroys the atom and prints the ASCII character represented by its mass, which is `"`.

This contains the simple Fission quine,

```
'#_OR"

```

Try it online!

Here, `'#` sets the mass of the atom to the ASCII value of `#` (35), and `_` decrements it so that the `O` prints a quotation mark.

# Fission, 8 bytes

```
'#_O  R"

```

Since the simple quine above starts at `R` and ends at `O`, any length quine can trivially be created by adding characters between the two.

---
Tags: code-golf, string, quine, source-layout, subsequence
---


title: Plus Primes vs Minus Primes

text:
# Question
Title: Plus Primes vs Minus Primes
# Most of us know...

that all primes `p>3` are of the form

But, how many are the **Plus Primes** (`6n+1`) and how many are the **Minus Primes** (`6n-1`) in a certain range?

# The Challenge

Given an integer `k>5` , count how many `primes<=k` are **PlusPrimes** and how many are **MinusPrimes**.

# Examples

for `k=100` we have
`[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89]` **12 MinusPrimes**
and
`[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]` **11 PlusPrimes**

for `k=149` we have
`[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149]`
**18 MinusPrimes**
and
`[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139]`
**15 PlusPrimes**

# Rules

Your code must output **2 integers**: one for the **MinusPrimes** and one for the **PlusPrimes** in any order you like (please specify which is which).
This is : shortest answer in bytes wins!

# Test Cases

> **Input** -\> **Output** \[**MinusPrimes**,**PlusPrimes**\]

```
6->[1,0]
7->[1,1]
86->[11,10]
986->[86,78]
5252->[351,344]
100000->[4806,4784]
4000000->[141696, 141448]

```

# Answer
> 10 votes
# 05AB1E, ~~10~~ 9 bytes

Saved 1 byte thanks to *Erik the Outgolfer*

Outputs as `[PlusPrimes, MinusPrimes]`

```
LDpÏ6%5Ñ¢

```

Try it online! or as a Test Suite

**Explanation**

```
L             # push range [1 ... input]
 DpÏ          # keep only primes
    6%        # mod each by 6
      5Ñ      # divisors of 5 [1, 5]
        ¢     # count

```

# Answer
> 6 votes
# Python 2, 77 bytes

-2 bytes thanks to Neil

```
lambda x:[sum(all(n%j for j in range(2,n))for n in range(i,x,6))for i in 7,5]

```

Try it online!

### Previous solution, ~~83~~ ~~81~~ 79 bytes

-1 byte thanks to Mr. Xcoder
-2 bytes thanks to Halvard Hummel

```
lambda x:map([all(n%i for i in range(2,n))*n%6for n in range(4,x)].count,[5,1])

```

Try it online!
Both output as \[MinusPrimes,PlusPrimes\]

# Answer
> 6 votes
# MATL, 10 bytes

```
Zq6\!5lh=s

```

Try it online! Or verify all test cases.

### Explanation

```
Zq     % Implicitly input k. Push row vector of primes up to k
6\     % Modulo 6, element-wise
!      % Transpose into a column vector
5lh    % Push row vector [5, 1]
=      % Is equal?, element-wise with broadcast
s      % Sum of each column. Implicitly display

```

# Answer
> 5 votes
# Japt, ~~15~~ ~~13~~ 11 bytes

Output order is `[+,-]`.

```
õj ò6 yx ë4

```

Test it

* Took some inspiration from Dennis' Jelly solution but, after golfing, it's closer to being a port.
* 2 bytes saved thank to Oliver bringing the previously-unknown-to-me `ë` method for arrays to my attention.

---

## Explanation

Implicit input of integer `U`.

```
õj

```

Generate an array of integers (`õ`) from 1 to `U` and check if each is a prime (`j`), giving an array of booleans.

```
ò6

```

Partition the array into sub-arrays of length 6.

```
yx

```

Transpose (`y`) and sum the columns.

```
ë4

```

Get every 4th element of the array and implicitly output them.

---

## Original, ~~19~~ ~~17~~ ~~16~~ 15 bytes

```
õ fj
5â £è_%6¥X

```

Test it

* 1 byte thanks to an inspired suggestion from Oliver to use the divisors of 5 after I'd rested on my laurels splitting 15 to an array.

# Answer
> 5 votes
# Mathematica, 51 bytes

```
(s=#;Mod[Prime~Array~PrimePi@s,6]~Count~#&/@{5,1})&

```

Try it online!

@ngenisis golfed it down, saving 4 bytes

# Mathematica, 47 bytes

```
sPrime~Array~PrimePi@s~Mod~6~Count~#&/@{5,1}

```

# Answer
> 5 votes
# Jelly, 7 bytes

```
s6ÆPSm4

```

Plus, then minus.

Try it online!

### How it works

```
s6ÆPSm4  Main link. Argument: n

s6       Split [1, ..., n] into chunks of length 6.
  ÆP     Test all integers for primality.
    S    Sum across columns.
         This counts the primes of the form 6k + c for c = 1, ..., 6.
     m4  Take every 4th element, leaving the counts for 6k + 1 and 6k + 5.

```

# Answer
> 3 votes
# , 23 bytes

```
1#.5 1=/6|_1 p:@i.@p:>:

```

Try it online!

```
1#.5 1=/6|_1 p:@i.@p:>:   input: y
          _1       p:     number of primes
                     >:   less than y + 1
             p:@i.        prime range from 0 to that number
        6|                get residues modulo 6
   5 1=/                  table of values equal to 5 or 1
1#.                       sum of each (antibase 1)

```

# Answer
> 3 votes
# Retina, ~~53~~ 51 bytes

```
.+
$*
1
$`1¶
G`1111
A`^(11+)\1+$
1{6}

*M`111
\b1\b

```

Try it online! Explanation:

```
.+
$*

```

Convert to unary.

```
1
$`1¶

```

Count from 1 up to `n`.

```
G`1111

```

Delete numbers less than 4.

```
A`^(11+)\1+$

```

Delete composite numbers.

```
1{6}

```

Take the remainder modulo 6.

```
*M`111

```

Print the number of numbers with a remainder between 3 and 5.

```
\b1\b

```

Print the number of numbers with a remainder of 1.

# Answer
> 3 votes
# Ruby, ~~61~~ 60 bytes

## (52 bytes + 8 for the `-rprimes` flag)

```
->n{[1,5].map{|x|(4..n).count{|i|i.prime?&&i%6==x}}}

```

Returns an array of the form \[plus primes, minus primes\].

Saved 1 byte thanks to G B!

Try it online.

# Answer
> 3 votes
# Perl 6, 42 bytes

*Saved 1 byte by removing a useless space...*

*Saved 2 bytes by reorganizing the* `map` *call — thanks to @Joshua.*

*Saved 3 bytes because* `.round` *equals* `.round: 1`.

*Actually the complex exponential is cool but very expensive characterwise. Saved 10 bytes just by ditching it...*

```
{[+] map {.is-prime*($_%6-1??i!!1)},5..$_}

```

Try it online!

This was the version with the complex exponential. (I like it too much to delete it.) The new version works exactly in the same way, just the complex exponential is replaced by the much shorter ternary operator.

```
{[+] map {.is-prime*exp(π*($_%6-1)i/8).round},5..$_}

```

Try it online!

The output is a complex number `(PlusPrimes) + (MinusPrimes)i`. I hope it's not too much against the rules.

---

Explanation: It's a function that takes one integer argument. We iterate over all integers from 5 to the argument (`(5..$_)`). For each of these, we evaluate `.is-prime` (this is called on `$_`, the argument of the mapped block), multiply it (if numified, `True == 1, False == 0`) with a complex exponential that's made to be either `exp(0) = 1` (for `$_%6 = 1`) or `exp(iπ/2) = i` (for `$_%6 = 5`), and finally round it to the nearest integer. Summing them up with `[+]` gives the result.

Finally: it's really efficient, so I'm not sure if TIO won't time out before you get your output for higher numbers (for 1e5, it takes 26 sec on my machine, and TIO tends to be somewhat slower).

# Answer
> 2 votes
# Actually, 21 bytes

```
u5x`p░⌠6@%1=;`╖*ƒ⌡Ml╜

```

Try it online!

Outputs the PlusPrimes first, followed by the MinusPrimes

Explanation:

```
u5x`p░⌠6@%1=;`╖*ƒ⌡Ml╜
u5x                    range(5, n+1)
   `p░                 primes in range
      ⌠6@%1=;`╖*ƒ⌡M    for each prime:
       6@%               mod 6
          1=             equal to 1
            ;`╖*ƒ        execute ╖ if p%6==1 (add 1 to register 0, consuming p)
                   l   length of resulting list (MinusPrimes)
                    ╜  push value in register 0 (PlusPrimes)

```

# Answer
> 2 votes
# Stacked, 37 bytes

```
[~>$primeYES 6%5 1,$=table tr$summap]

```

Try it online!

Rather slow, tests for primality for each **K** \< **N**. Works similar to my J answer.

# Answer
> 2 votes
# C#, ~~202~~ ~~179~~ 174 Bytes

*-23 Bytes thanks to Mr. Xcoder*

*-5 Bytes thanks to Cyoce*

Function that returns an array of length 2, `[MinusPrimes, PlusPrimes]` Execute by calling `a(n)`.

```
int[]a(int n){int[]r={0,0};for(int i=5;i<=n;i++)if(i%2*b(i)>0)if(i%6<5)r[1]++;else++r[0];return r;}int b(int n){for(int i=3;i-2<Math.Sqrt(n);i+=2)if(n%i<1)return 0;return 1;}

```

Properly formatted code on Try It Online: Here

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

*-2 bytes thanks to @Oliver*

```
õ_j ©Z%6
5â £è¥X

```

Try it online!

Outputs in the format `[PlusPrimes, MinusPrimes]`.

# Answer
> 2 votes
# Haskell, ~~81~~ 69 bytes

```
f n=(\r->sum[1|i<-[2..n],all((>0).rem i)[2..i-1],rem i 6==r])<$>[5,1]

```

Try it online!

First solution was:

```
r!l=sum[1|i<-l,rem i 6==r]
f n|l<-[i|i<-[2..n],all((>0).rem i)[2..i-1]]=(5!l,1!l)

```

But I read w0lf's answer in Ruby...

# Answer
> 2 votes
# MATLAB 2017a, 29 Bytes

```
sum(mod(primes(k),6)'==[5,1])

```

Explanation: `primes(k)` gets all primes up to and including k. `mod(primes(k),6)'` takes the modulus 6 of all primes and transposes it so the sum runs along the correct dimension. `==[5,1]` sets all fives (minusPrimes) to 1 in the first column and all ones (plusPrimes) to 1 in the second column. `sum()` sums each column.

This outputs `[minusPrime, plusPrime]`

# Answer
> 1 votes
# Pyth, 15 bytes

```
/K%R6fP_TSQ5/K1

```

**Test Suite.**

# Pyth, 16 bytes

```
m/%R6fP_TSQd,1 5

```

**Test Suite.**

---

# How?

### Explanation #1

```
/K%R6fP_TSQ5/K1 - Full program.

     fP_TSQ     - Filter the primes in the range [1...input].
  %R6           - Mod 6 on each.
 K              - Assign them to a variable K.
/          5    - Count the occurrences of 5 in K.
            /K1 - Count the occurrences of 1 in K.
                - Implicitly output the result.

```

### Explanation #2

```
m/%R6fP_TSQd,1 5 - Full program.

     fP_TSQ      - Filter the primes in the range [1...input]
  %R6            - Mod 6 on each.
            ,1 5 - Push the list [1, 5]
m/         d     - Count how many of each there are.
                 - Implicitly output the result.

```

Alternatives:

```
/K%R6fP_TSQ5/KhZ    (16 bytes)
K%R6fP_TSQ/K5/K1    (16 bytes)
m/%R6fP_TSQdj15T    (16 bytes)
m/%R6fP_TSQd[1 5    (16 bytes)
m/%R6fP_TSQdsM`15   (17 bytes)
m/%R6.MP_ZSQd,1 5   (17 bytes)
m/%R6.MP_ZSQdj15T   (17 bytes)
m/%R6.MP_ZSQd[1 5   (17 bytes)

```

# Answer
> 1 votes
# Jelly,  ~~12 11~~  10 bytes

Thanks to @cairdcoinheringaahing for some tips in chat. Thanks to @Dennis for saving one byte in chat.

```
ÆR%6ċÐ€1,5

```

Try it online!

# Jelly, 11 bytes

```
ÆR%6µ1,5=þS

```

Try it online!

# Jelly, 11 bytes

```
ÆR%6µċ5,ċ1$

```

Try it online!

---

# How does this work?

### Explanation #1

```
ÆR%6ċÐ€1,5   As usual, full program.

ÆR           Get all the primes in the range [2...input].
  %6         Modulo each by 6.
       1,5   The two-element list [1, 5].
    ċÐ€      Count the occurrences of each of ^ in the prime range.

```

### Explanation #2

```
ÆR%6µ1,5=þS   As usual, full program.

ÆR            Get all the primes in the range [2...input].
  %6          Modulo each by 6.
    µ         Chain separator.
     1,5      The two-element list [1, 5].
        =     Equals?
         þ    Outer product.
          S   Sum.

```

### Explanation #3

```
ÆR%6µċ5,ċ1$   As usual, full program.

ÆR            All the primes in the range [2...input].
  %6          Modulo each by 6.
    µ     $   Some helpers for the chains.
       ,      Two element list.
     ċ5       The number of 5s.
        ċ1    The number of 1s.

```

# Answer
> 1 votes
# Java 8, ~~141~~ ~~140~~ ~~138~~ ~~106~~ ~~101~~ ~~100~~ ~~96~~ ~~94~~ 81 bytes

```
n->{int r[]={0,0},c;for(;n-->4;r[n%6/4]+=c)for(c=n;c>1;c=c-1&~n%c>>-1);return r;}

```

Returns an integer-array with two values, in reversed order compared to the challenge description:
`[plusPrime, minusPrime]`.

Port of *@Xynos*' C# answer, after I golfed ~~39~~ ~~40~~ 42 bytes.
Huge help from *@Nevay* for another whopping -55 bytes.

**Explanation:**

Try it here. (Final test case of `4000000` is exceeding the 60 sec time limit slightly.)

```
n->{                   // Method with integer parameter and integer-array return-type
  int r[]={0,0},       //  Return integer-array, starting at [0,0]
      c;               //  Temp integer
  for(;n-->4;          //  Loop (1) as long as the input is larger than 4
                       //  and decrease `n` by 1 before every iteration
      r[n%6/4]+=c)     //    After every iteration, increase the plus or minus prime by `c`
                       //    (where `c` is either 0 or 1)
    for(c=n;           //   Reset `c` to `n`
        c>1;           //   And inner loop (2) as long as `c` is larger than 1
      c=               //    Change `c` to:
        c-1&~n%c>>-1;  //     inverting the bits of `n`,                    [~n]
                       //     modulo-`c` that result,                       [%c]
                       //     then bit-shift right that by -1,              [>>-1]
                       //     and then bitwise-AND that result with `c-1`   [c-1&]
    );                 //   End of inner loop (2)
                       //  End of loop (1) (implicit / single-line body)
  return r;            //  Return result integer-array
}                      // End of method

```

# Answer
> 1 votes
# JavaScript (ES6), ~~83~~ ~~82~~ ~~80~~ ~~68~~ 66 bytes

Turned out a fully recursive solution was *much* shorter than mapping an array!

Output order is `[-,+]`. Craps out with an overflow error somewhere around 3490.

```
f=(n,a=[0,0])=>n>4?f(n-1,a,(g=y=>n%--y?g(y):y<2)(n)&&++a[n%6%5]):a

```

---

## Try it

```
o.innerText=(

f=(n,a=[0,0])=>n>4?f(n-1,a,(g=y=>n%--y?g(y):y<2)(n)&&++a[n%6%5]):a

)(i.value=6);oninput=_=>o.innerText=i.value>5?f(+i.value):[0,0]
```

```
<input id=i min=6 type=number><pre id=o>
```

# Answer
> 0 votes
# \+ numbers, ~~66~~ ~~60~~ ~~58~~ 40 bytes

*-16 bytes thanks to Jarko Dubbeldam!* I subsequently golfed another two bytes off.

```
cat(table(numbers::Primes(4,scan())%%6))

```

Prints `PlusPrimes MinusPrimes` to stdout; reads from stdin.

`table` tabulates the count of each occurrence of the values in its input vector, in ascending order of value. Hence, since there are only two values, namely `1` and `5` (mod 6), this is exactly the function we need, along with `numbers::Primes`, which returns all primes between `4` and the input.

Try it online!

# Base , ~~97~~ ~~91~~ ~~89~~ ~~86~~ 65 bytes

*a bunch of bytes saved by Jarko here, too*

```
function(n)table((5:n)[sapply(5:n,function(x)all(x%%2:x^.5))]%%6)

```

This is nearly identical to the above, except it calculates all the primes in base R rather than using a package, and it returns by function output rather than printing it out. You can see in the output that it returns a table with names `1` and `5`, with the counts below.

Try it online!

# Answer
> 0 votes
# CJam, 19 bytes

```
ri){mp},6f%_5e=p1e=

```

Program that takes the input from STDIN, and outputs the two numbers separated by newline through STDOUT.

**Try it online!**

### Explanation

```
ri){mp},6f%_5e=p1e=

ri                        Read integer k
  )                       Add 1
       ,                  Filter the (implicit) array [0 1 ... k] ...
   {mp}                   ... on the function "is prime"
         f                Map over the resulting array...
          %               ... the function "modulus" ...
        6                 ... with extra parameter 6
           _              Duplicate the resulting array
             e=           Count occurrences ...
            5             ... of number 5
               p          Print with newline
                 e=       Count occurrences ...
                1         ... of number 1. Implicitly display

```

# Answer
> 0 votes
# JavaScript (SpiderMonkey), ~~151~~, ~~140~~, 131 bytes

```
n=>[...Array(n+1).keys()].splice(5).filter(a=>!/^1?$|^(11+?)\1+$/.test("1".repeat(a))).reduce((r,a)=>(a%6<2?r[1]++:r[0]++,r),[0,0])

```

Try it online!

Thanks to shaggy for helping with a bug fix and golfing.

Explanation:

```
n=>                                                   // Create a lambda, taking n
    [...Array(n+1).keys()]                            // Create a list from 0 to n+1
        .splice(5)                                    // remove first five elements
        .filter(a=>                                   // filter the list to get primes
             !/^1?$|^(11+?)\1+$/.test("1".repeat(a))) // using the famous regex here: https://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex
        .reduce((r,a)=>                               // reduce the list
           (a%6<2?r[1]++:r[0]++,r),                   // by counting plus primes
           [0,0])                                     // and minus primes

```

# Answer
> 0 votes
# Pari/GP, 41 bytes

```
n->vecsum([[i>3,i<3]|i<-primes([4,n])%6])

```

Try it online!

---
Tags: code-golf, primes, counting
---


title: Count the Palindromes

text:
# Question
Title: Count the Palindromes
Given a number `n`, calculate the amount of bases in the range of `[2, n)` in which `b(n)` is a Palindrome.

## Example

`n = 8` has the base conversions:

```
2 = 1000
3 = 22
4 = 20
5 = 13
6 = 12
7 = 11

```

Of which 2 of them, `3 = 22` and `7 = 11` are palindromes. So return `2`.

## Clarifications

* For the sake of convenience, Your answer only needs to be correct for inputs 3 - 36 inclusive, as few languages can handle base conversion of \>36.
* A single digit number is considered a palindrome.
* This is sequence A135551 on OEIS

## Test Cases

```
3   -> 1
4   -> 1
5   -> 2
6   -> 1
7   -> 2
8   -> 2
9   -> 2
10  -> 3
11  -> 1
12  -> 2
13  -> 2
14  -> 2
15  -> 3
16  -> 3
17  -> 3
18  -> 3
19  -> 1
20  -> 3
21  -> 4
22  -> 2
23  -> 2
24  -> 4
25  -> 2
26  -> 4
27  -> 3
28  -> 4
29  -> 2
30  -> 3
31  -> 3
32  -> 3
33  -> 3
34  -> 3
35  -> 2
36  -> 5

```

## Finally

# Answer
# Jelly, 6 bytes

```
bḊŒḂ€S

```

A monadic link taking and returning numbers

**Try it online!**

### How?

```
bḊŒḂ€S - Link: number, n
 Ḋ     - dequeue (with implicit range(n) as input) -> [2,3,4,...,n]
b      - convert to base  -> [nb2, nb3, nb4, ..., nbn] (note: nbn is [1,0])
  ŒḂ€  - isPalindrome? for €ach  -> list of 1s and 0s
     S - sum -> number that are palindomes

```
> 2 votes

# Answer
# 05AB1E,  ~~10~~  8 bytes

-2 bytes thanks to Emigna (use "bifurcation" instruction `Â` to replace duplicate and reverse `DR` & increment the loop to avoid needing to close it.)

```
G¹N>вÂQO

```

**Try it online!**

### How?

```
G¹N>вÂQO
G        - for N in range(1, input()+1):
 ¹       -   1st input
  N      -   N (the loop variable)
   >     -   increment
    в    -   base conversion
     Â   -   push reverse
      Q  -   equal?
       O -   sum
         - print top of stack

```
> 3 votes

# Answer
# J, 30 bytes

```
[:+/i.&.(-&2)(-:|.)@(#.inv)"0]

```

Try it online!

Straightforward solution featuring a lot of parentheses.

# Explanation

```
[: +/ i.&.(-&2) (-:|.)@(#.inv)"0 ]
                                 ]  Right argument, n
      i.&.(-&2)                     Range [2,n)
           -&2                        Subtract 2
      i.                              Create range from n-2
        &.                            Undo subtraction (add 2)
                              "0    For each value in the range
                       (#.inv)      Convert to that base *
                (-:|.)              Palindrome check
                   |.                 Reversed
                 -:                   Matches self (= is rank 0)
   +/                               Sum (i.e. count palindromes)

```

*`#.inv` is used since `#:` expects you to specify the number of digits in the base (it doesn't treat a single argument the way you might expect).
> 2 votes

# Answer
# Python 2, 90 bytes

```
lambda n:sum(h(n,i)==h(n,i)[::-1]for i in range(2,n))
h=lambda v,b:v and[v%b]+h(v/b,b)or[]

```

An unnamed function taking `n` that counts the palindromes, which utilises the helper function `h` which performs the base conversions.

**Try it online!**
> 2 votes

# Answer
# Mathematica, 57 bytes

```
Tr@Boole@Table[PalindromeQ@IntegerDigits[#,i],{i,2,#-1}]&

```
> 1 votes

# Answer
# Ruby, 47 bytes

```
->n{(2...n).count{|i|(s=n.to_s(i))==s.reverse}}

```

Try it online!
> 1 votes

# Answer
# Pyth,  ~~10~~  9 bytes

Port of irtosiast's submission to "All your base palindromic belong to us".

-1 byte thanks to FryAmTheEggman - use the filter alias `#` to replace `f` and do away with the `T` (which seems also to have been available back then too).

```
lt_I#jLQS

```

**Try it online!**
> 1 votes

# Answer
# Pyth, 9 bytes

```
lf_IjQTtS

```

**Test it here!**

# Pyth, 9 bytes

```
sm_IjQdtS

```

**Try it here!**

---

# How?

* `sm_IjQdtS` \- Full program with implicit input (`Q` at the end)
* `tS` \- All the integers from 2 to the input (inclusive). I chose inclusive because it is golfier and any number `n` converted to base `n` is `10`.
* `m` \- Map over the above with a variable `d`.
* `jQd` \- Convert the input to base `d` (the current number in the range) as a list.
* `_I` \- The best part of this program: Is invariant under reverse? – This checks if the list is palindromic.
* `s` \- Sum, which acts like "count the number of truthy results" in this case.
> 1 votes

# Answer
# Pyke, 10 bytes

```
tFOAbD_q)s

```

Try it here!

```
t          -   input - 1
 FOAbD_q)  -  for i in ^:
  O        -   ^ + 2
   Ab      -    base(input, ^)
     D_q   -     ^ == reversed(^)
         s - sum(^)

```
> 1 votes

# Answer
# RProgN 2, 18 bytes

```
x=x1-2R³x\Br³]ier+

```

This is essentially what I used as a reference implementaiton.

## Explained

```
x=x1-2R³x\Br³]ier+
x=                  # Associate 'x' with the implicit input.
  x1-               # Get x - 1
     2R             # Get all numbers in the range 2 through x - 1
           r        # Replace each element by the function...
       ³x\B         # Convert x to base i.
                r   # Replace each element by another function...
            ³]ie    # Duplicate, Inverse, Equals. Checks if it's a palindrome.
                 +  # The sum of. Which counts how many are palindromes.

```

Try it online!
> 0 votes

# Answer
# Python 2, 187 bytes

```
def P(n):
 p=0
 for b in range(2,n):
	M=0
	while n>=b**M:M+=1
	N,I,B=n,M-1,[]
	while N:
	 for f in range(b)[::-1]:
		if f*b**I<=N:N-=f*b**I;B+=[f];I-=1;break
	p+=0>(B[::-1]==B)*I
 print p

```

Try it online!

A bit on the lengthy side, as there is no built-in used for changing base.
> 0 votes

# Answer
# Haskell, 67 bytes

```
0#b=[]
x#b=mod x b:div x b#b
f n=sum[1|b<-[2..n],n#b==reverse(n#b)]

```

Try it online! Use by calling `f`. Works with arbitrary high bases.
> 0 votes

# Answer
# JavaScript (ES6), ~~77~~ ~~71~~ ~~70~~ ~~68~~ 67 bytes

```
n=>(g=b=>b<n&&([...s=n.toString(b)].reverse().join``==s)+g(++b))(2)

```

<sup>(Golfed from 77 down to 68 while waiting for the challenge to be reopened)</sup>

---

## Test it

```
f=
n=>(g=b=>b<n&&([...s=n.toString(b)].reverse().join``==s)+g(++b))(2)
o.innerText=[...Array(34)].map(_=>(""+x).padStart(2)+": "+f(x++),x=3).join`\n`
```

```
<pre id=o>
```
> 0 votes

# Answer
# Japt `-x`, ~~9~~ 8 bytes

```
ò2@sX êS

```

\[Test it\]https://ethproductions.github.io/japt/?v=1.4.5&code=8jJAc1gg6lM=&input=MzYKLXg=)

---

## Explanation

```
             :Implicit input of integer U.
ò2           :Range [2,U]
  @          :Map each X
   sX        :  Convert U to a base-X string
      êS     :  Is it a palindrome?
             :Implicitly reduce by addition and output

```
> 0 votes

---
Tags: code-golf, integer, base-conversion, palindrome
---


title: Fun with strings and string lengths

text:
# Question
Title: Fun with strings and string lengths
# Introduction

Inspired by Dyalog Ltd.'s 2016 student competition. The challenge there is to write *good* APL code, but this is a and it is open to all languages. Derived from this closed challenge.

The real challenge here is to combine the various (quite trivial) parts of the problem in a byte-efficient way by reusing values and/or algorithms.

If you find this challenge interesting and you use Dyalog APL (free download here), you may also want to participate in the original competition, but note that the objective there is to submit *quality code* – not necessarily *short code*. If you are a student, you can win USD 100 for Phase I. Phase II (not related to this code golf challenge) can win you up to USD 2000 and a free trip to Scotland!

# Task

Take two strings (of any 7-bit ASCII characters) by any means and order (but please include input format in your answer). You may take them as separate arguments/inputs or as a single list of strings. One string contains the delimiters in the other. E.g. given `',;/'` and `'hello,hello;there;my/yes/my/dear,blue,world'`, the sub-strings are `['hello', 'hello', 'there', 'my', 'yes', 'my', 'dear', 'blue', and 'world']`.

You will do some statistics and ordering based on the lengths of those sub-strings that are not duplicated in the input. (You may chose to consider casing or not.) In the example given, those are `['there', 'yes', 'dear', 'blue', 'world']`.

Give (by any means) a list of four elements in the overall structure `[Number_1, Number_2, [List_3], [[List_4_1], [List_4_2]]]`:

1. The mean of the lengths of the non-duplicated strings. In our example, that is `4.2`
2. The median of the lengths of the non-duplicated strings. In our example, that is `4`.
3. The mode(s) of the lengths of the non-duplicated strings. In our example, that is `[4, 5]`.
4. The original sub-strings (including duplicates), divided into two lists; the first are those that are not one of the above mode lengths, and the second are those that are. In our example: `[['my', 'my', 'yes'], ['dear', 'blue', 'hello', 'hello', 'there', 'world']]`

The combined final answer of our example case is: `[4.2, 4, [4, 5], [['my', 'my', 'yes'], ['dear', 'blue', 'hello', 'hello', 'there', 'world']]]`

# Considerations

1. Don't forget to reuse code and values. E.g. the median is the average of the 1 or 2 middle elements, and you'll need the mode(s) to reorder the original list.
2. Watch out for division by zero; an empty input means one string with length zero, so the mean length is zero. If there are no non-unique sub-strings, return zero for both mean and median, an empty list for modes, and put all original sub-strings onto the non-mode list.
3. The list of modes, and the sub-lists of non-mode-length strings, and mode-length strings, do not need to be sorted in any way.
4. If all non-duplicated sub-strings have different lengths, then all the lengths are considered modes.
5. Wherever the term *list* is used, you may use any collection of multiple data pieces that your language supports, e.g. tuples, arrays, dictionaries, etc.
6. The numeric values only need to be within 1% of the actual value.

# Example cases

### Example A

`',;/'` `'hello,hello;there;my/yes/my/dear,blue,world'`
gives
`[4.2, 4, [4, 5], [['my', 'my', 'yes'], ['dear', 'blue', 'hello', 'hello', 'there', 'world']]`

### Example B

`'+|'` `''`
gives
`[0, 0, [0], [[], ['']]]`

**Note:** while there are two delimiter characters, none of them occur in the data string, so this is just one empty string. Mean, median, and mode are therefore zero There are no strings in the non-mode list and just the single empty string in the mode list.

### Example C

`''` `'ppcg.se.com'`
gives
`[11, 11, [11], [[], ['ppcg.se.com']]]`

**Note:** no delimiters, so the entire input is one string.

### Example D

`',;'` `',math,,math;'`
gives
`[0, 0, [], [['', 'math', '', 'math', ''], []]]`

**Note:** there are three empty sub-strings, and since all sub-strings have at least one duplicate, the mean and median default to zero, as per *Considerations*, above.

### Example E

`',;'` `'new,math,math;!;'`
gives
`[1.333, 1, [0,1,3], [['math', 'math'], ['new', '!', '']]]`

**Note:** there is only one of each length among the non-duplicated sub-strings, so all three lengths are modes.

---

You can verify my explicit permission to post this challenge here by contacting the author of the original competition.

# Answer
> 4 votes
## PowerShell v4+, ~~453~~ ~~455~~ ~~435~~ ~~427~~ 417 bytes

```
param([char[]]$a,$b)if(!$b){0;0;0;'','';exit}$a|%{$b=$b-split$_};$c=@{};if($z=($b|group|?{$_.count-eq1}).Name){$z|%{$m+=$c[$_]=$_.length}}if($l=$c.count){$c=$c.GetEnumerator()|sort v}else{$l=2}$m/$l;if($l%2){$c[[math]::Floor($l/2)].Value}else{($c[$l/2].value+$c[$l/2-1].value)/2}if($x=($c|group value|sort c -des)|%{if($_.count-ge$i){$i=$_.count;$_.name}}){$m=$b|?{$_.length-in$x}}else{$m=@()}$x;($b|?{$_-notin$m}),$m

```

*(Saved 7 bytes by eliminating `$d` and reusing `$c` instead. Saved ~~13~~ ~~21~~ 31 bytes thanks to @Joey)*

What a mess. Below is a slightly more readable version, broken down into sections. I also included `-join` on the two potentially-array outputs to make the output more clear visually, as well as surrounding the last one in distinct delimiters `#->` and `<-#` to indicate the sub-arrays. I did this since PowerShell's `Write-Output` for multiple array return values can get a little confusing when just looking at them on the console.

```
param([char[]]$a,$b)if(!$b){0;0;0;'','';exit}$a|%{$b=$b-split$_}
$c=@{}
if($z=($b|group|?{$_.count-eq1}).Name){$z|%{$m+=$c[$_]=$_.length}}
if($l=$c.count){$c=$c.GetEnumerator()|sort v}else{$l=2}
$m/$l
if($l%2){$c[[math]::Floor($l/2)].Value}else{($c[$l/2].value+$c[$l/2-1].value)/2}
if($x=($c|group value|sort c -des)|%{if($_.count-ge$i){$i=$_.count;$_.name}}){$m=$b|?{$_.length-in$x}}else{$m=@()}
$x-join','
"#->" + ((($b|?{$_-notin$m})-join','),($m-join',')-join'<-# #->') + "<-#"

```

Takes input `$a` and `$b` (separators and string), and explicitly casts `$a` right away as a char-array. The `if(!$b)` clause handles the special case where `$b` is an empty string - it dumps zeros and empty strings onto the pipeline and `exit`s. Otherwise we loop through `$a` with `$a|%{...}`, each loop `-split`ting `$b` by the current character and re-saving into `$b`.

The next line sets `$c` as an empty hashtable. This is used as the temporary storage location for the non-duplicated values in `$b` and their corresponding lengths.

That's the next line. We take `$b`, pump it through `Group-Object` to put like words together, pipe that to `Where-Object` to select only those where the `.count` is `-eq`ual to 1. We then take the `.Name` of those (here's where the v4+ requirement comes into play), and store those `.Name`s (i.e., the words) into `$z`. We then take the `.count` of that, and that number forms our `if` clause -- so long as it's non-zero (i.e., we have at least one unique word), we pump those words through a loop. Each iteration we accumulate `$m` by, and also store into `$c`, the corresponding word's `.length`.

Next line sorts `$c` on lengths (that's the `|sort v`alue in the middle) and stores that back to `$c`, but we need to have some logic to account for cases where `$z` was empty (i.e., every word is a duplicate). If that's the situation, `$c` is already an empty hashtable, but we set `$l` equal to `2` to handle the mean calculation later.

Now, we're to our outputs. The first `$m/$l` just calculates the average length. The next line calculates the median based on either taking the exact middle value of `$c`, or taking the two above and below the middle and splitting the difference.

The next line is very complicated, and was where the longest troubleshooting was. It's calculating the mode. We start by `Group`ing `$c` based on `value` (i.e., the word lengths), then `Sort-Object` them by their `c`ount in `-des`cending order (i.e., the most-common lengths will be first). That list is fed into a loop. Each iteration, if the current item's `$_.count` is greater-than-or-equal-to `$i` (which initializes to `$null` or `0`, here), meaning that we've got a length that's the most-common, set `$i` equal to how many of that length there are, and add the length (`$_.name`) to the pipeline. That resulting array of most-common lengths is stored into `$x`.

Provided that we have at least one most-common length, the `if` triggers and we pipe `$b` through another `Where-Object`. This time, we're selecting all of the words where the `.length` is `-in` `$x` (i.e., all of the words that have a length that's in the mode), and store them into `$m` (yes, I reused a variable name). `Else`, we don't have a most-common length, so the strings of the mode is empty.

The next line `$x-join','` outputs the lengths of the mode. Then, the words in `$b` that aren't in `$m` and the words in `$m`, as two sub-arrays.

---

### Test suite

```
PS C:\Tools\Scripts\golfing> @(@(',;/','hello,hello;there;my/yes/my/dear,blue,world'),@('+|',''),@('','ppcg.se.com'),@(',;',',math,,math;'),@(',;','new,math,math;!;'))|%{"Testing: '"+$_[0]+"' '"+$_[1]+"'";.\fun-with-strings.ps1 $_[0] $_[1];"---------------------------------------------------------------------------------------"}
Testing: ',;/' 'hello,hello;there;my/yes/my/dear,blue,world'
4.2
5
4,5
#->my,yes,my<-# #->hello,hello,there,dear,blue,world<-#
---------------------------------------------------------------------------------------
Testing: '+|' ''
0
0
0

---------------------------------------------------------------------------------------
Testing: '' 'ppcg.se.com'
11
11
11
#-><-# #->ppcg.se.com<-#
---------------------------------------------------------------------------------------
Testing: ',;' ',math,,math;'
0
0

#->,math,,math,<-# #-><-#
---------------------------------------------------------------------------------------
Testing: ',;' 'new,math,math;!;'
1.33333333333333
1
3,1,0
#->math,math<-# #->new,!,<-#
---------------------------------------------------------------------------------------

```

# Answer
> 3 votes
# Pyth, 63 bytes

```
Ju.ncRHGQ]E.OKlMfq1/JTJ.O<.<S*2KtlK2=N
S{.x.M/KZKY=Y
f}lTNJ.-JY

```

Test suite.

# Answer
> 1 votes
# Python 3, 341 chars, 343 bytes

```
from statistics import*
def f(d,s,l=len):
 w=sorted(''.join(x if not x in d else'ÿ'for x in s).split('ÿ'),key=l)
 L=[l(x)for x in w if w.count(x)<2]
 if L==[]:return 0,0,L,[s,L]
 a,q=mean(L),median(L)
 D={x:L.count(x)for x in L}
 m=[x for x in D if D[x]==max(D.values())]
 i=[l(x)for x in w].index(m[0])
 return a,q,m,[w[:i],w[i:]]

```

As built-ins are not forbidden, using the `statistics` module is fine for mean and median, but its mode does not allow multiples.

* Edit1: check for non-uniqueness
* Edit2: shorter list comprehension on `m`
* Edit3: `l=len` and `L==[]`
* Edit4: for the empty `L` case, use it instead of `[]`
* Edit5: figured empty strings were not handled well, introduced non-7-bit-ASCII sentinel **ÿ**

# Answer
> 1 votes
## JavaScript (ES2017), 346 bytes

```
f=(p,q,a=p?q.split(p[0]):[q])=>p[1]?f(p.slice(1),a.join(p[1])):(s=a.filter(e=>a.indexOf(e)==a.lastIndexOf(e)).map(e=>e.length).sort((a,b)=>a-b),t=l=0,r=[],s.map(e=>r[t+=e,l++,e]=-~r[e]),[l&&t/l,l&&(s[l>>1]+s[l-1>>1])/2,[...m=new Set(s.filter(e=>r[e]==Math.max(...Object.values(r))))],[a.filter(e=>!m.has(e.length)),a.filter(e=>m.has(e.length))]])

```

For ES6 replace `Object.values(r)` with `Object.keys(r).map(k=>r[k])` at a cost of 11 bytes. Explanation:

```
f=(p,q,a=p?q.split(p[0]):[q])=>         split on first seprator
 p[1]?f(p.slice(1),a.join(p[1])):       recurse for each separator
  (s=a.filter(e=>                       search through list for
     a.indexOf(e)==a.lastIndexOf(e))    unique strings only
    .map(e=>e.length)                   get lengths of each string
    .sort((a,b)=>a-b),                  sort lengths into order
   t=l=0,                               total and length
   r=[],                                frequency table
   s.map(e=>r[t+=e,l++,e]=-~r[e]),      build frequency table and total
   [l&&t/l                              mean = total / length
   ,l&&(s[l>>1]+s[l-1>>1])/2            median = mean of middle elements
   ,[...m=new Set(s.filter(e=>r[e]==    unique elements matching
    Math.max(...Object.values(r))))]    maximum length frequency
   ,[a.filter(e=>!m.has(e.length))      filter on non-modal length
    ,a.filter(e=>m.has(e.length))]])    filter on modal length

```

# Answer
> 0 votes
# q/kdb+, 134 bytes

**Solution:**

```
{(avg;med;{:M::(&)m=max m:(#:)@/:(=)x};{(y(&)(~)C;y(&)C:((#:)@/:y)in M)}[;a])@\:(#:)@/:(&)1=(#:)@/:(=)a:"\000"vs?[any y=/:x;"\000";y]}

```

**Examples:**

```
q)/assign function to 'f' to make this tidier
q)f:{(avg;med;{:M::(&)m=max m:(#:)@/:(=)x};{(y(&)(~)C;y(&)C:((#:)@/:y)in M)}[;a])@\:(#:)@/:(&)1=(#:)@/:(=)a:"\000"vs?[any y=/:x;"\000";y]}
q)f[",;/";"hello,hello;there;my/yes/my/dear,blue,world"]
4.2
4f
5 4
(("my";"yes";"my");("hello";"hello";"there";"dear";"blue";"world"))
q)f["+|";""]
0f
0f
,0
(();,"")
q)f["";"ppcg.se.com"]
11f
11f
,11
(();,"ppcg.se.com")
q)f[",;";",math,,math;"]
()
()
()
(("";"math";"";"math";"");())
q)f[",;";"new,math,math;!;"]
1.333333
1f
3 1 0
(("math";"math");("new";,"!";""))

```

**Explanation:**

Ungolfed version. Can likely be golfed down a fair bit more.

```
f:{(avg;                                           / built-in average
    med;                                           / built-in median
    {:M::where m=max m:count each group x};        / get max counts for group, save to global M
    {
     (y where not C;                               / y is original list,
      y where C:(count each y) in M)               / so these are ones that match the modes (M)
    }[;a]                                          / pass parameter a to the function
    )
    @\:                                            / apply each-left with items on the right
    count each                                     / get the lengths of each string
    where 1=count each group                       / remove the duplicates
    a:"\000" vs                                    / split on NUL and save in a
    ?[any y=/:x;"\000";y]}                         / replace any occurance of delimiter with NUL

```

---
Tags: code-golf, string, sorting, statistics
---


title: Boolean Rectangles

text:
# Question
Title: Boolean Rectangles
*Inspired by Braille graphics*

Given a Boolean matrix (i.e., consisting of only `1`s and `0`s), output an ASCII-art-style Unicode representation of the closed-polygon shape created by the `1`s in the matrix, using the Unicode drawing characters `┌ ─ ┐ │ └ ┘` (code points `0x250c, 0x2500, 0x2510, 0x2502, 0x2514,` and `0x2518,` respectively, separated by spaces). Replace the `0`s with spaces, so you're left with just the line drawing. Output or return that drawing.

You won't have to handle invalid or ambiguous input - there will be only one unambiguous path of `1`s through the matrix. In other words, every `1` has exactly two cardinal neighbors that are `1`s, and two that are `0`s or out of bounds. Additionally, since the shape is a closed-polygon, this guarantees that the path is cyclical.

Examples:

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

┌─┐
│ │
└─┘

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

 ┌──┐
┌┘  └┐
│    │
└────┘

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

┌─┐
│ └─┐
│   │
└┐ ┌┘
 └─┘

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

┌─┐
│ └┐
└┐ │
 └─┘

```
* Leading or trailing newlines or whitespace are all optional, so long as the characters themselves line up correctly.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# Javascript (ES6), 125 bytes

```
a=>a.map((r,i)=>r.map((c,j)=>c&&"─ ┌└  ┐┘ |"[!(a[i-1]||0)[j]+!(a[i+1]||0)[j]*2+!r[j-1]*4+!r[j+1]*8-3]||" ").join``).join`
`

```

Example code snippet:

```
f=
a=>a.map((r,i)=>r.map((c,j)=>c&&"─ ┌└  ┐┘ |"[!(a[i-1]||0)[j]+!(a[i+1]||0)[j]*2+!r[j-1]*4+!r[j+1]*8-3]||" ").join``).join`
`
o.innerText=f([[1,1,1,0,0],
[1,0,1,1,1],
[1,0,0,0,1],
[1,1,0,1,1],
[0,1,1,1,0]])
```

```
<pre id=o>
```
> 0 votes

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


title: Self-summed numbers

text:
# Question
Title: Self-summed numbers
# Convert a number to a sum of digits

**Not any sum:** we need the **shortest** sum
**Not any digits:** you can use only **digits of the number**

***Example***
You will be given as **input** an integer `n>0`

Let's say `n=27`. You have to express `27` as a **sum**, using **only the digits** `[2,7]`, in the **shortest** way possible. **You don't have to use all the digits of the given number!**

So `27=2+2+2+7+7+7`. We then **take those digits and count them**: `[2,2,2,7,7,7]`.
Final answer for `n=27` is `6`

One more example for `n=195` in order to get the **shortest sum** we have to use the following digits:
`[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]` and the **answer** is `23`

# The challenge

Given an integer `n>0`, output the **minimum number of digits** (contained in the number) that **sum up to this number**

# Test Cases

`Input->Output`

```
1->1
2->1
10->10
58->8
874->110
1259->142
12347->1765
123456->20576
3456789->384088

```

This is .Shortest answer in bytes wins!

# Answer
> 4 votes
# Husk, 12 bytes

```
Lḟo=⁰ΣṁΠḣ∞d⁰

```

Handles two-digit numbers pretty fast. Try it online!

## Explanation

```
Lḟo=⁰ΣṁΠḣ∞d⁰  Input is n, say n = 13.
          d⁰  Digits of n: [1,3]
         ∞    Repeat infinitely: [[1,3],[1,3],[1,3],[1,3]...
        ḣ     Prefixes: [[],[[1,3]],[[1,3],[1,3]],[[1,3],[1,3],[1,3]],...
      ṁ       Map and concatenate
       Π      Cartesian product: [[],[1],[3],[1,1],[3,1],[1,3],[3,3],[1,1,1],[3,1,1],...
 ḟo           Find the first element
     Σ        whose sum
   =⁰         equals n: [3,3,3,3,1]
L             Return its length: 5

```

# Answer
> 2 votes
# Python 2, ~~168~~ ~~155~~ 144 bytes

It isn't the *shortest* it could be, but it's best-first and not *real* bad, runtime wise.

```
n=input()
g=sorted(set(n)-{0})[::-1]
def h(k):
 if k<0:return
 if`k`in g:return 1
 for d in g:
  f=h(k-int(d))
  if f:return 1+f
print h(int(n))

```

~~The `filter(None...` is to remove 0 as a digit, which I learned I could do while making this.~~

The biggest problem is python stack frames, which realistically don't allow me to run this on the largest inputs. So, it is not a valid solution, really, I played around with increasing the recursion limit which just led to seg-faults. This has to either be done with a loop and a stack or with a lot more cleverness to work in python.

edit: Thanks to caird and Chas Brown for 13 bytes!

# Answer
> 2 votes
# Pyth, 12 bytes

```
lef!-TsM`Q./

```

Try it online!

Unfortunately it memory errors on inputs as large as `58`.

### Explanation

```
lef!-TsM`Q./
          ./    All lists of integers that sum to [the input]
  f             Filter for:
    -TsM`Q           Remove all occurrences of the digits in the input
   !                 Check if falsey (i.e. an empty list)
le              Length of the last occurrence, which is the shortest because all the
                filtered partitions share the same digit pool

```

# Answer
> 2 votes
# Mathematica, 78 bytes

```
(t=1;While[(s=IntegerPartitions[x=#,t,IntegerDigits@x])=={},t++];Tr[1^#&@@s])&

```

finds last test case in 5 sec

# Answer
> 2 votes
# , 78 bytes

```
function(n){while(all(F-n)){F=outer(F,n%/%10^(0:nchar(n))%%10,"+")
T=T+1}
T-1}

```

Try it online! (golfed version)

Pure brute force algorithm, so it doesn't actually solve all the test cases, and I think it tried to allocate 40,000 GB for the last test case...

`T` in R defaults to `1` so we get an off-by-one error which we correct at the return step, but we also get `F` which defaults to `0` which pays off.

ungolfed explanation:

```
function(n){
 d <- n%/%10^(0:nchar(n))%%10   # digit list with a 0 appended at end
 d <- unique(d[d>0])            # filter zeros (not technically necessary)
                                # and get unique digits
 x <- 0                         # storage for sums
 i <- 0                         # counter for number of sums done
 while(!any(x==n)){             # until we find a combination
  x <- outer(x,d,"+")           # take all sums of x and d, store as x
  i <- i + 1}                   # increment counter
i}                              # return counter

```

Try it online! (less golfy version)

# Answer
> 0 votes
# Husk, 13 bytes

Pretty inefficient

```
VVo=⁰ΣMṖNṘ⁰d⁰

```

Try it online!

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

```
f=(n,l=0,a=n,[c,...b]=a)=>n?1/c?Math.min(!+c|+c>n?1/0:f(n-c,l+1,a),f(n,l,b)):1/0:l
```

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

Takes input as a string.

# Answer
> 0 votes
# Ruby, 70 bytes

```
->n{w,s=n.digits,0;s+=1while !w.product(*[w]*s).find{|x|x.sum==n};s+1}

```

Very slow, try all the possible combinations increasing the size until we get to a solution.

Thanks Dennis for Ruby 2.4 on TIO.

Try it online!

# Answer
> 0 votes
# Jelly, 23 bytes

```
D;0ṗµḟ€0
ÇS€=µT
Çị1ĿL€Ṃ

```

Try it online!

This is so inefficient, that it does not run for the test cases after the third one on TIO due to a time limit \>\_\<

Any golfing tips are welcome!

# Answer
> 0 votes
# Haskell, 91 bytes

```
f n=[read[c]|c<-show n,c>'0']#n!!0
s#n|n>0,x:m<-(s#).(n-)=<<s=[1+minimum(x:m)]|1<3=[0|n==0]

```

Try it online! Example usage: `f 58` yields `8`. Quick for two-digit numbers, horrendously slow for larger inputs.

The function `f` converts the input number `n` into a list of digits while filtering out zeros. Then this list and `n` itself are handed to the `(#)` function, which returns a singleton list. `!!0` returns the element of this singleton list.

`(#)` uses singleton and empty lists as option type. Given an input of `n=58` and `s=[5,8]`, the idea is to subtract all digits in `s` from `n`, then recursively apply `(#)` and check which digit resulted in the minimum number of steps and return one plus this minimum as result. The first part is computed by `(s#).(n-)=<<s`, which is the same as `concat(map(s#)(map(n-)s))`. So in our example first `[58-5,58-8]` is computed, followed by `[[5,8]#53,[5,8]#50]` which results in `[[7],[7]]` or `[7,7]` after `concat`. The result is matched on the pattern `x:m` to make sure the list has at least one element (`minimum` fails otherwise), then the singleton list of 1 plus the minimum of the result is retuned. If `n` was smaller zero or the recursive call returned an empty list, we are in a failing branch of the search and an empty list is returned. If `n==0` the branch was succeeding and `[0]` is returned.

---

# Haskell, 101 bytes

```
f n=[d|d<-[9,8..1],show d!!0`elem`show n]#n!!0
s@(d:r)#n|n>=d,[x]<-s#(n-d)=[x+1]|1<3=r#n
s#n=[0|n==0]

```

Try it online! A way more efficient approach, checks all test cases in under one second.

This time, the list of digits of the input is computed to be in descending order, which allows `(#)` to try to use the largest digit as often as possible, then the second largest, and so until a solution is found. The first solution found this way is also guaranteed to be the smallest one.

# Answer
> 0 votes
# Python 2, ~~183~~ ~~176~~ ~~172~~ ~~166~~ 161 bytes

```
def f(n,D=0,p=0,b=0):
	D=D or set(map(int,`n`))-{0}
	d=min(D);c=0;D=D-{d}
	q=[p+n/d,b][n%d>0]
	while c<min(D or{0}):q=b=f(n-c*d,D,p+c,b);c+=1
	return[q,b][q>b>0]

```

Try it online!

Longer than the other Python answer, but performs all test cases combined plus `987654321` in under a second on TIO.

Takes advantage of the fact that if `d1<d2` are digits, then there need be at most `d2-1` `d1`'s in the sum (since `d2` instances of `d1` can be replaced with `d1` instances of `d2` for a shorter sum). Thus, sorting the digits in ascending order, there are "only" at most `9! = 362880` possible sums to consider; and a maximum recursion depth of `9` (regardless of the value of `n`).

---
Tags: code-golf, integer-partitions
---


title: The Binary Binary Expansion

text:
# Question
Title: The Binary Binary Expansion
> Normally, we decompose a number into binary digits by assigning it with powers of 2, with a coefficient of `0` or `1` for each term:
>
> `25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1`
>
> The choice of `0` and `1` is... not very binary. We shall perform the *true* binary expansion by expanding with powers of 2, but with a coefficient of `1` or `-1` instead:
>
> `25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1`
>
> Now *this* looks binary.
>
> Given any positive number, it should be trivial to see that:
>
> * Every odd number has infinitely many true binary expansions
> * Every even number has no true binary expansions
>
> Hence, for a true binary expansion to be well-defined, we require the expansion to be the *least*, i.e with the shortest length.

---

Given any positive, odd integer `n`, return its true binary expansion, from the most significant digit to the least significant digit (or in reversed order).

### Rules:

* As this is , you should aim to do this in the **shortest byte count possible.** Builtins are allowed.
* Any output that can represent and list the coefficients is acceptable: an array, a string of coefficients with separators, etc...
* Standard golfing loopholes apply.
* Your program should work for values within your language's standard integer size.

---

### Test Cases

```
25 -> [1,1,1,-1,-1]
47 -> [1,1,-1,1,1,1]
1 -> [1]
3 -> [1,1]
1234567 -> [1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1]

```

# Answer
> 7 votes
# Japt, 6 bytes

```
¤é r0J

```

Try it online!

## Explanation:

```
¤é r0J  // Test input:                  25
¤       // Binary the input:            11001
 é      // Rotate 1 chars to the right: 11100
   r0J  // Replace 0s with -1:          111-1-1

```

# Answer
> 3 votes
## JavaScript (ES6), ~~35~~ 34 bytes

```
f=n=>n?[...f(n>>=1),!n|n%2||-1]:[]

```

### Test snippet

```
let f=n=>n?[...f(n>>=1),!n|n%2||-1]:[];

[25, 47, 1, 3, 1234567].map(x => console.log(x + ":", JSON.stringify(f(x))))
```

# Answer
> 3 votes
# Pyth,  ~~12~~  11 bytes

```
|R_1.>jQ2 1

```

**Try it here!**

---

# How?

```
|R_1.>jQ2 1   Full program.

      jQ2      Convert input to a binary list.
     .>   1    Cyclically rotate the list above by 1 place to the right.
|R_1           Substitute 0 with -1.
               Implicitly output.

```

First off, we notice that the task is just "substitute the `0`s in the binary writing with `-1`s and shift to the right by 1 place." — That's exactly what we should do! The binary conversion gives us a list of `0`s and `1`s. All we should do here is to find a golfy way to convert `0` to `-1`. The bitwise operator `|` (bitwise OR) is our friend. The map over the binary representation shifted with `|` and `-1`. If the current number is `0`, it gets converted to `-1`.

# Answer
> 3 votes
# Perl 6

String version, 31 bytes

```
1~(*+>1).base(2).subst(0,-1,:g)

```

Try it online!

List version, 36 bytes

```
{map * *2-1,1,|($_+>1).base(2).comb}

```

Try it online!

# Answer
> 2 votes
# Perl 6, 72 bytes

There is surely a better way, but this is what I have...

```
->$a {grep {$a==[+] @^a.reverse Z+< ^∞},[X] (1,-1)xx $a.base(2).chars}

```

Try it online!

**Explanation**: It's a function that takes one argument (`->$a`). We first get the number of coefficients needed (`$a.base(2).chars` = number of characters in base 2 representation), then make a Cartesian product (`X`) of that many pairs `(1,-1)`. (The `[X]` means: reduce the following list with `X`.) So we get a list of all possible combinations of 1s and -1s. Then we filter (`grep`) only the lists which encode the given number `$a`. There is only one, so we get a list of one list with the coefficients.

The grep block does this: takes its argument as a list (`@^a`), reverses it and zips it with an infinite list `0,1,2,...` using the "left bit shift" operator `+<`. Zipping stops as soon as the shorter list is depleted (good for us!) We then sum all the results and compare it with the given number. We had to use `.reverse` because the OP demands that the coefficients be in the order from most significant to least significant.

# Answer
> 1 votes
# , ~~90~~ ~~88~~ 46 bytes

```
function(n)c((n%/%2^(0:log2(n))%%2)[-1],1)*2-1

```

Try it online!

Implements Oliver's algorithm, but returns the digits in reverse order. Since we are guaranteed that `n` is never even, the least significant bit (the first) is always `1`, so we remove it and append a `1` to the end to simulate rotation in R. Thanks to Shaggy for getting me to fix my math.

Simply putting `rev( )` around the function calls in the footer should return the values in the same order.

## original answer, 88 bytes:

```
function(n,b=2^(0:log2(n)))(m=t(t(expand.grid(rep(list(c(-1,1)),sum(b|1))))))[m%*%b==n,]

```

Anonymous function; returns the values in **reverse order** with column names attached.

Try it online!

Explanation:

```
function(n){
 b <- 2^(0:log2(n))         # powers of 2 less than n
 m <- expand.grid(rep(list(c(-1,1)),sum(b|1))) # all combinations of -1,1 at each position in b, as data frame
 m <- t(t(m))               # convert to matrix
 idx <- m%*%b==n            # rows where the matrix product is `n`
 m[idx,]                    # return those rows
}

```

# Answer
> 1 votes
# 05AB1E, ~~6~~ 5 bytes

```
bÁ0®:

```

Try it online!

# Answer
> 1 votes
# Jelly, 5 bytes

```
Bṙ-o-

```

Try it online!

# Answer
> 1 votes
# J, 11 bytes

```
1-~2*_1|.#:

```

Try it online!

Thanks to @JosiahWinslow for the algorithm.

Any thoughts on making the conversion shorter? My thoughts are to using `!.`-fit (nvm, it just changes the tolerance of the conversion).

Using `{`-take is longer by 1 character.

```
_1 1{~_1|.#:

```

# Answer
> 1 votes
# Perl 5, 30 bytes

29 bytes code, 1 byte for `-p` switch.

```
$_=sprintf'1%b',$_/2;s/0/-1/g

```

Try it online!

# Answer
> 1 votes
# Java 8, 101 bytes

```
n->{String s=n.toString(n,2);return(s.charAt(s.length()-1)+s.replaceAll(".$","")).replace("0","-1");}

```

Port of *@Oliver*'s Japt answer, with *a few* more bytes.. ;)

Can definitely be golfed by using an mathematical approach instead of this String approach.

**Explanation:**

Try it here.

```
n->{                             // Method with Integer parameter and String return-type
  String s=n.toString(n,2);      //  Convert the Integer to a binary String
  return(s.charAt(s.length()-1)  //  Get the last character of the binary String
    +s.replaceAll(".$","")       //   + everything except the last character
   ).replace("0","-1");          //  Then replace all zeroes with -1, and return the result
}                                // End of method

```

# Answer
> 1 votes
# Ruby, ~~44 37 33~~ 32 bytes

```
->n{("1%b"%n).chop.gsub ?0,"-1"}

```

Try it online!

# Answer
> 0 votes
# Golfscript, ~~14~~ ~~13~~ 14 bytes

*-1 byte because I forgot `%` existed.* *+1 byte because I also forgot input is a string.*

```
~2base{.+(}%)\

```

# Answer
> 0 votes
# CJam, 12 bytes

A port of my Golfscript answer.

```
qi2b{_+(}%)\

```

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


title: Unicode rectangles

text:
# Question
Title: Unicode rectangles
Given

* a matrix `a` of characters from `u=" ╶╺╵└┕╹┖┗╴─╼┘┴┶┚┸┺╸╾━┙┵┷┛┹┻╷┌┍│├┝╿┞┡┐┬┮┤┼┾┦╀╄┑┭┯┥┽┿┩╃╇╻┎┏╽┟┢┃┠┣┒┰┲┧╁╆┨╂╊┓┱┳┪╅╈┫╉╋"`
* the coordinates of a submatrix as `x`,`y`,`w`,`h` (left, top, width\>1, height\>1)
* a thickness `t` of 1 (as in ) or 2 (as in )

render an inner border for the submatrix with the specified thickness, taking into account existing lines.

```
x=4;y=1;w=2;h=3;t=2;
a=[' ┌───┐',
   '┌┼┐  │',
   '│└┼──┘',
   '└─┘   ']

// output
r=[' ┌───┐',
   '┌┼┐ ┏┪',
   '│└┼─╂┨',
   '└─┘ ┗┛']

```

When overwriting a line fragment, the new thickness should be the greater of the old thickness and `t`.

This isn't about input parsing or finding the Kolmogorov complexity of Unicode, so you may assume `a`,`u`,`x`,`y`,`w`,`h`,`t` are available to you as variables. Also, you may put the result in a variable `r` instead of returning or outputting it, as long as `r` is of the same type as `a`.

If your language forces you to put code in functions (C, Java, Haskell, etc) and your solution consists of a single function, you can omit the function header and footer.

Larger test:

```
x=4;y=1;w=24;h=4;t=1;
a=['┏┱─────┐         ┌┐     ┎──┲━┓',
   '┠╂─────┘         ││     ┃  ┗━┛',
   '┃┃               ││     ┃     ',
   '┠╂──┲━━┓  ┏━━━━┓ ││    ┌╂┰┐   ',
   '┃┃  ┗━━┩  ┃    ┃ └╆━┓  └╂┸┘   ',
   '┃┃     │  ┃    ┃  ┃ ┃   ┃     ',
   '┗┹─────┘  ┗━━━━┛  ┗━┛   ╹     ']

// output
r=['┏┱─────┐         ┌┐     ┎──┲━┓',
   '┠╂──┬──┴─────────┼┼─────╂──╄━┛',
   '┃┃  │            ││     ┃  │  ',
   '┠╂──╆━━┓  ┏━━━━┓ ││    ┌╂┰┐│  ',
   '┃┃  ┗━━╃──╂────╂─┴╆━┱──┴╂┸┴┘  ',
   '┃┃     │  ┃    ┃  ┃ ┃   ┃     ',
   '┗┹─────┘  ┗━━━━┛  ┗━┛   ╹     ']

```

# Answer
> 2 votes
# JavaScript, 218 bytes

```
(a,x,y,w,h,t,u)=>a.map((l,j)=>l.map((c,i)=>u[(g=(a,b)=>a?g(a/3|0,b/3|0)*3+Math.max(a%3,b%3):b)(u.indexOf(c),t*((j==y||j==y+h-1)*((i>x&&i<x+w)*9+(i>=x&&i<x+w-1))+(i==x||i==x+w-1)*((j>y&&j<y+h)*3+(j>=y&&j<y+h-1)*27)))]))

```

`a` should be taken as array of array of char.

```
f =

(a,x,y,w,h,t,u)=>a.map((l,j)=>l.map((c,i)=>u[(g=(a,b)=>a?g(a/3|0,b/3|0)*3+Math.max(a%3,b%3):b)(u.indexOf(c),t*((j==y||j==y+h-1)*((i>x&&i<x+w)*9+(i>=x&&i<x+w-1))+(i==x||i==x+w-1)*((j>y&&j<y+h)*3+(j>=y&&j<y+h-1)*27)))]))

x=4;y=1;w=24;h=4;t=1;
a=['┏┱─────┐         ┌┐     ┎──┲━┓',
   '┠╂─────┘         ││     ┃  ┗━┛',
   '┃┃               ││     ┃     ',
   '┠╂──┲━━┓  ┏━━━━┓ ││    ┌╂┰┐   ',
   '┃┃  ┗━━┩  ┃    ┃ └╆━┓  └╂┸┘   ',
   '┃┃     │  ┃    ┃  ┃ ┃   ┃     ',
   '┗┹─────┘  ┗━━━━┛  ┗━┛   ╹     '].map(x => [...x])
u=" ╶╺╵└┕╹┖┗╴─╼┘┴┶┚┸┺╸╾━┙┵┷┛┹┻╷┌┍│├┝╿┞┡┐┬┮┤┼┾┦╀╄┑┭┯┥┽┿┩╃╇╻┎┏╽┟┢┃┠┣┒┰┲┧╁╆┨╂╊┓┱┳┪╅╈┫╉╋";

output = f(a,x,y,w,h,t,u).map(x => x.join('')).join('\n');
document.write(`<pre lang="en" style="font-family: Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,sans-serif;">${output}</pre>`)
```

# Answer
> 2 votes
# Python 3, ~~226~~ ~~201~~ 197 bytes

```
n,m=x+w-1,y+h-1
r=[*map(list,a)]
R=range
for i in R(x,x+w):
 for j in R(y,y+h):A,B=j in(y,m),i in(x,n);r[j][i]=u[sum(3**o*max((i<n*A,y<j*B,x<i*A,j<m*B)[o]*t,u.index(a[j][i])//3**o%3)for o in R(4))]

```

Try it online!

Ungolfed:

```
n,m=x+w-1,y+h-1
r=[*map(list,a)]
for i in range(x,x+w):
 for j in range(y,y+h):
  p=u.index(a[j][i])
  c=(p%3,p%9//3,p%27//9,p//27)
  A,B=j in(y,m),i in(x,n)
  P=(i<n*A,y<j*B,x<i*A,j<m*B)
  l=sum(max(P[o]*t,c[o])*3**o for o in range(4))
  r[j][i]=u[l]

```

# Answer
> 1 votes
## JavaScript (ES6), 174 bytes

```
r=a.map((l,j)=>l.map((c,i)=>u[c=u.indexOf(c),g=n=>c/n%3<t&&g(n,c+=n),j==y|j==h&&(i>=x&i<w&&g(1),i>x&i<=w&&g(9)),i==x|i==w&&(j>=y&j<h&&g(27),j>y&j<=h&&g(3)),c]),w+=x-1,h+=y-1)

```

```
a=`
┏┱─────┐         ┌┐     ┎──┲━┓
┠╂─────┘         ││     ┃  ┗━┛
┃┃               ││     ┃
┠╂──┲━━┓  ┏━━━━┓ ││    ┌╂┰┐
┃┃  ┗━━┩  ┃    ┃ └╆━┓  └╂┸┘
┃┃     │  ┃    ┃  ┃ ┃   ┃
┗┹─────┘  ┗━━━━┛  ┗━┛   ╹
`.match(/.+/g).map(s=>[...s]);
x=4;
y=1;
w=24;
h=4;
t=1;
u=" ╶╺╵└┕╹┖┗╴─╼┘┴┶┚┸┺╸╾━┙┵┷┛┹┻╷┌┍│├┝╿┞┡┐┬┮┤┼┾┦╀╄┑┭┯┥┽┿┩╃╇╻┎┏╽┟┢┃┠┣┒┰┲┧╁╆┨╂╊┓┱┳┪╅╈┫╉╋";
r=a.map((l,j)=>l.map((c,i)=>u[c=u.indexOf(c),g=n=>c/n%3<t&&g(n,c+=n),j==y|j==h&&(i>=x&i<w&&g(1),i>x&i<=w&&g(9)),i==x|i==w&&(j>=y&j<h&&g(27),j>y&j<=h&&g(3)),c]),w+=x-1,h+=y-1)
;document.write(`<pre style="font-family:Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,sans-serif">${r.map(s=>s.join``).join`\n`}</pre>`);
```

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


# Question
Title: Perfect, Germain, Vampire, Mersenne! (Don't forget narcissistic)
> Six is a number perfect in itself, and not because God created all things in six days; rather, the converse is true. God created all things in six days because the number six is perfect.

I am fascinated by numbers. As were Sophie Germain and Marin Mersenne. To be more specific, these two were fascinated by *primes*: a number with only two integer divisors: itself and `1`. In fact, they were so fascinated by primes that classes of primes were named after them:

A Mersenne prime is a prime number which can be generated by the formula 2p \- 1 where `p` is a prime. For example, `7 = 2^3 - 1` therefore `7` is a Mersenne prime.

A Germain prime is similar. It is a prime number that when plugged into the formula `2p + 1` it also produces a prime. E.g. 11 is Germain as `2*11 + 1 = 23` which is prime.

But now let's move on to the next three numbers: perfect, vampire and narcissistic numbers.

A perfect number is very easy to understand. It can be easily defined as

> A number where all its divisors except itself sum to itself. For example, 6 is a perfect number as the divisors of 6 (not including 6) are 1,2,3 which sum to make 6.

A vampire number may be the most difficult to code. A vampire number is a number whose digits can be split into two numbers, of equal length, made from *all* those digits, that when multiplied, produce the original number. Leading 0s aren't allowed in either of the numbers E.g. `136,948 = 146 x 938`

Finally a narcissistic number, probably the hardest to understand. A narcissistic number is a number in which the individual digits, raised to the power of the total number of digits sum to make the original number. A single digit number **has to be** narcissistic.

For example, 8,208 is narcissistic:

84 \+ 24 \+ 04 \+ 84 = 4,096 + 16 + 0 + 4,096 = 8,208

Your task is to create a program that will take an integer and return what category it fits into. The categories are `Mersenne`, `Germain`, `Perfect`, `Vampire`, `Narcissistic` and `False`. Every number that doesn't fit into the first five categories is `False`. `False` doesn't have to necessarily be a falsy value.

If a value fits in more than one category, e.g. `3`, you may output **any** correct result.

Output can be in any form, for example, 6 different numbers, as long as you say what it is in your answer.

Even if it is shorter, you aren't allowed to hard code each number as that ruins maths.

This is a so shortest code wins!

## Examples

```
Input -> Output

10 -> False
7 -> Mersenne
8208 -> Narcissistic
28 -> Perfect
153 -> Narcissistic
2 -> Germain
17 -> False
16,758,243,290,880 -> Vampire
31 -> Mersenne
33,550,336 -> Perfect
173 -> Germain
136,948 -> Vampire

```

# Answer
> 4 votes
# 05AB1E, ~~43~~ ~~40~~ 39 bytes

```
Lo<¹å¹p&¹·>p¹p&¹Ñ¨OQ¹œε2ä}P¹å¹S¹gmOQ)Xk

```

`-1` for False, `0` for Mersenne, `1` for Germain, `3` for Perfect, `4` for Vampire, and `5` for Narcissistic.

Try it online!

# Answer
> 4 votes
# Pyth, 71 bytes

```
x[.EmqQ*shdsed.cs.pM.cK`Q/lK2 2qsP{*MyPQQ&P_hyQP_Q<.&QhQP_QqQsm^sdlKK)1

```

**Try it here! or Verify the test cases.**

Alternative solution, **71 bytes:**

```
x[.EmqQ*shdsed.cs.pM.cK`Q/lK2 2qsP{*MyPQQ&P_hyQP_Q&.AjQ2P_QqQsm^sdlKK)1

```

**Try it here! or Verify the test cases.**

This returns **-1** for *False*, **0** for Vampire, **1** for *Perfect*, **2** for *Sophie Germain*, **3** for *Mersenne* and **4** for *Narcissistic*. In case more are truthy, this picks the one with the lowest index. Unfortunately, this memory errors for the following test cases: `33550336, 16758243290880`.

---

# Explanation

## Vampire (29 bytes)

```
.EmqQ*shdsed.cs.pM.cK`Q/lK2 2

                  .c `Q/lK2      Get all combinations of the input's digits of half its length.
                .pM              Get all possible permutations of each.
             .cs            2    Get all possible two-number combinations, flattened.
.EmqQ*shdsed                     Check if any has the product equal to the input.

```

Let's go through an example. Let's assume our input is **1260**.

* First of all, we get the all the possible combinations of 2 digits (number\_of\_digits / 2). We get `['12', '16', '10', '26', '20', '60']`.
* Then, we get the possible permutations of each, `[['12', '21'], ['16', '61'], ['10', '01'], ['26', '62'], ['20', '02'], ['60', '06']]`.
* We flatten that (`['12', '21', '16', '61', '10', '01', '26', '62', '20', '02', '60', '06']`) and get all the possible 2-element combinations. This list is quite long:

```
[['12', '21'], ['12', '16'], ['12', '61'], ['12', '10'], ['12', '01'], ['12', '26'], ['12', '62'], ['12', '20'], ['12', '02'], ['12', '60'], ['12', '06'], ['21', '16'], ['21', '61'], ['21', '10'], ['21', '01'], ['21', '26'], ['21', '62'], ['21', '20'], ['21', '02'], ['21', '60'], ['21', '06'], ['16', '61'], ['16', '10'], ['16', '01'], ['16', '26'], ['16', '62'], ['16', '20'], ['16', '02'], ['16', '60'], ['16', '06'], ['61', '10'], ['61', '01'], ['61', '26'], ['61', '62'], ['61', '20'], ['61', '02'], ['61', '60'], ['61', '06'], ['10', '01'], ['10', '26'], ['10', '62'], ['10', '20'], ['10', '02'], ['10', '60'], ['10', '06'], ['01', '26'], ['01', '62'], ['01', '20'], ['01', '02'], ['01', '60'], ['01', '06'], ['26', '62'], ['26', '20'], ['26', '02'], ['26', '60'], ['26', '06'], ['62', '20'], ['62', '02'], ['62', '60'], ['62', '06'], ['20', '02'], ['20', '60'], ['20', '06'], ['02', '60'], ['02', '06'], ['60', '06']]

```
* The next step is getting the product of each pair:

```
[252, 192, 732, 120, 12, 312, 744, 240, 24, 720, 72, 336, 1281, 210, 21, 546, 1302, 420, 42, 1260, 126, 976, 160, 16, 416, 992, 320, 32, 960, 96, 610, 61, 1586, 3782, 1220, 122, 3660, 366, 10, 260, 620, 200, 20, 600, 60, 26, 62, 20, 2, 60, 6, 1612, 520, 52, 1560, 156, 1240, 124, 3720, 372, 40, 1200, 120, 120, 12, 360]

```
* And then compare to the input:

```
[False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False]

```
* Finally, the last step is checking if any value is truthy. And there is one (at index `19` into the list). Hence, this returns a truthy value for **1260**, thanks to the pair **\[21, 60\]**.

## Perfect (10 bytes)

```
qsP{*MyPQQ

q        Q   Is equal to the input?
 s           Sum.
   {*MyPQ    Its divisors.
  P          Popped (since we want the proper divisors).

```

## Sophie Germain (9 bytes)

```
&P_hyQP_Q

      P_Q    Is the input prime?
 P_hy        Is the input doubled + 1 prime?
&            Logical AND.

```

## Mersenne (9 bytes)

```
<.&QhQP_Q

<             Is smaller?
 .&             Bitwise AND between:
   Q              The input
    hQ             And the input + 1
              than:
      P_Q       Is the input prime?

```

This tests if the **input + 1** is a power of two (i.e. if it is a Mersenne number), and then performs the primality test. In Python, `bool` is a subclass of `int`, so truthy is treated as **1** and falsy is treated as **0**. To avoid checking explicitly that one is **0** and the other is **1**, we compare their values using `<` (since we only have 1 such case).

In the alternative approach, this part is changed to `&.AjQ2P_Q`. This works as follows:

```
&.AjQ2P_Q

   jQ2      The input in binary as a list of digits.
 .A         Are all truthy (i.e equal to 1)?
&     P_Q   ... And is prime?

```

This uses the fact that any number of the form **2n \- 1** only consists of **1** when written in binary, and also checks if it is prime.

## Narcissistic (10 bytes)

```
qQsm^sdlKK

q            Is equal?
 Q           The Input
   m     K   Map over the string representation of the input.
    ^sdlK    Raise each digit to the power of the number of digits the input has.
  s          Summed.

```

---

When it comes to the rest of the code, `[...)` builds a list of bool values and `x[...)1` gets the index of the first truthy element.

# Answer
> 2 votes
# Jelly, 53 bytes

```
“+1l2Ḟ⁼¡Ḟ$ÆPȧÆP“_1HÆPȧÆP“ÆḌS⁼“DŒ!œs€2ḌP€ċ“D*L$S⁼”v€TX

```

Try it online!

Returns `1` for Mersenne, `2` for Germain, `3` for Perfect, `4` for Vampire, `5` for Narcissistic and `0` for False. Returns random in case many are true.

# Answer
> 2 votes
# 05AB1E, 51 bytes

```
"p¹p* "D">2.nDîpsïÿ<;ÿÑ¨OQ œε2ä}P¹å s¹gmOQ"#ε.V}ā*à

```

Try it online!

Returns `1` for Mersenne, `2` for Germain, `3` for Perfect, `4` for Vampire, `5` for Narcissistic and `0` for False. Returns max in case many are true.

# Answer
> 1 votes
# Python 2, ~~292~~ ~~286~~ 274 bytes

*-2 bytes thanks to @Okx*
*-4 bytes thanks to @Mr.Xcoder*

```
lambda n:[n&-~n<a(n),a(n)&a(2*n+1),sum(k*(n%k<1)for k in range(1,n))==n,any(len(c)%2<1<n==int(j(c[::2]))*int(j(c[1::2]))for c in permutations(`n`)),sum(int(d)**len(`n`)for d in`n`)==n,1].index(1)
a=lambda n:all(n%k for k in range(2,n))*~-n>0
j=''.join
from itertools import*

```

Try it online!

Output is `0` for mersenne, `1` for germaine, `2` for perfect, `3` for vampire, `4` for narcissistic and `5` for false.

---

## Ungolfed

```
from itertools import*
f=lambda n:
  [
    n&-~n == 0 and a(n),                               # Is n a Mersenne prime?
    a(n) and a(2*n+1),                                 # Is n a Germain prime?
    sum(k for k in range(1,n) if n%k<1)==n,            # Is n a perfect number?
    any(len(c)%2<1<                                    # Is n a vampire number?
      n==int(''.join(c[:len(c)/2]))*int(''.join(c[len(c)/2:]))
      for c in permutations(`n`)),
    sum(int(d)**len(str(n)) for d in str(n))==n,       # Is n a narcissistic number?
    1
  ].index(1)                                           # Get the first position
                                                       # of a 1 (or True) in the list
a=lambda n:False if n<2 else all(n%k for k in range(2,n)) # primality check

```

# Answer
> 0 votes
# Mathematica, 275 bytes

```
If[!FreeQ[(S=Select)[2^Range@#-1,PrimeQ],#],1,If[!FreeQ[S[Prime@Range@#,PrimeQ[2#+1]&],#],2,If[PerfectNumberQ@#,3,If[!FreeQ[Times@@FromDigits/@#&/@S[Subsets[Tuples[v=(j=IntegerDigits)@#,{(k=IntegerLength)@#/2}],{2}],ContainsAll[Flatten@#,v]&],#],4,If[Tr[j@#^k@#]==#,5,6]]]]]&

```

thanx to @Mr. Xcoder for letting me know that I don't have to use the string-names!

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