title: Determine if a relation is transitive

text:
# Question
Title: Determine if a relation is transitive
# Challenge description

Let's start with some definitions:

* a **relation** is a set of ordered pairs of elements (in this challenge, we'll be using integers)

For instance, `[(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]` is a relation.

* a relation is called **transitive** if for any two pairs of elements `(a, b)` and `(b, c)` in this relation, a pair `(a, c)` is also present,
* `[(1, 2), (2, 4), (6, 5), (1, 4)]` is transitive, because it contains `(1, 2)` and `(2, 4)`, but `(1, 4)` as well,
* `[(7, 8), (9, 10), (15, -5)]` is transitive, because there aren't any two pairs `(a, b)`, `(c, d)` present such that `b` = `c`.
* `[(5, 9), (9, 54), (0, 0)]` is not transitive, because it contains `(5, 9)` and `(9, 54)`, but not `(5, 54)`

Given a list of pairs of integers, determine if a relation is transitive or not.

# Input / output

You will be given a list of pairs of integers in any reasonable format. Consider a relation

`[(1, 6), (9, 1), (6, 5), (0, 0)]`

The following formats are equivalent:

```
[(1, 6), (9, 1), (6, 5), (0, 0)] # list of pairs (2-tuples)
[1, 9, 6, 0], [6, 1, 5, 0] # two lists [x1, x2, ..., xn] [y1, y2, ..., yn]
[[1, 6], [9, 1], [6, 5], [0, 0] # two-dimentional int array
[4, 1, 6, 9, 1, 6, 5, 0, 0] # (n, x1, y1, ..., xn, yn)
[1+6i, 9+i, 6+5i, 0+0i] # list of complex numbers

... many others, whatever best suits golfing purposes

```

Output: a truthy value for a transitive relation, falsy otherwise. You may assume that the input will consist of at least one pair, and that the pairs are unique.

# Answer
## Haskell, 42 bytes

```
f x=and[elem(a,d)x|(a,b)<-x,(c,d)<-x,b==c]

```

Usage example: `f [(1,2), (2,4), (6,5), (1,4)]`-\> `True`.

(Outer)loop over all pairs `(a,b)` and (inner)loop over the same pairs, now called `(c,d)` and every time when `b==c` check if `(a,d)`is also an existent pair. Combine the results with logical `and`.
> 8 votes

# Answer
# MATL, ~~27~~ 25 bytes

```
7#u2e!l6MX>thl4$XQttY*g<~

```

Input format is a matrix (using `;` as row separator) where each pair of the relation is a column. For example, test cases

```
[(1, 2), (2, 4), (6, 5), (1, 4)]
[(7, 8), (9, 10), (15, -5)]
[(5, 9), (9, 54), (0, 0)]

```

are respectively input as

```
[1 2 6 1; 2 4 5 4]
[7 9 15; 8 10 -5]
[5 9 0; 9 54 0]

```

Truthy output is a matrix formed by ones. Falsy is a matrix that contains at least one zero.

Try it online!

### Explanation

The code first reduces the input integers to unique, 1-based integer values. From those values it generates the adjacency matrix; matrix-multiplies it by itself; and converts nonzero values in the result matrix to ones. Finally, it checks that no entry in the latter matrix exceeds that in the adjacency matrix.
> 4 votes

# Answer
## Prolog, 66 bytes

```
t(L):-not((member((A,B),L),member((B,C),L),not(member((A,C),L)))).

```

The relation is *not* transitive if we can find (A,B) and (B,C) such that (A,C) doesn't hold.
> 4 votes

# Answer
## JavaScript (ES6), ~~69~~ 67 bytes

```
a=>(g=f=>a.every(f))(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

```

Saved 2 bytes thanks to an idea by @Cyoce. There were four previous 69-byte formulations:

```
a=>a.every(([b,c])=>a.every(([d,e])=>c-d|a.some(([d,c])=>b==d&c==e)))
a=>!a.some(([b,c])=>!a.some(([d,e])=>c==d&a.every(([d,c])=>b-d|c-e)))
a=>a.every(([b,c])=>a.every(([d,e])=>c-d|!a.every(([d,c])=>b-d|c-e)))
(a,g=f=>a.every(f))=>g(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

```
> 3 votes

# Answer
# Pyth, 14 bytes

```
!-eMfqFhTCM*_M

```

Test suite

Input format is expected to be `[[0, 0], [0, 1], ... ]`

```
!-eMfqFhTCM*_M
!-eMfqFhTCM*_MQQQ    Variable introduction
            _MQ      Reverse all of the pairs
           *   Q     Cartesian product with all of the pairs
         CM          Transpose. We now have [[A2, B1], [A1, B2]] for each pair
                     [A1, A2], [B1, B2] in the input.
    f                Filter on
       hT            The first element (the middle two values)
     qF              Being equal
  eM                 Take the end of all remaining elements (other two values)
 -              Q    Remove the pairs that are in the input
!                    Negate. True if no transitive pairs were not in the input

```
> 3 votes

# Answer
# Brachylog, 24 bytes

```
'{psc[A:B:B:C],?'e[A:C]}

```

Try it online!

Explanation:

```
'{psc[A:B:B:C],?'e[A:C]}
'{                     } it is impossible to find
    c                    a flattened
   s                     subset of
  p                      a permutation of the input
     [A:B:B:C]           that has four elements, with the second and third equal
              ,?         and such that the input
                'e       does not contain
                  [A:C]  a list formed of the first and fourth element

```

In other words, if the input contains pairs `[A:B]` and `[B:C]`, we can permute the input to put `[A:B]` and `[B:C]` at the start, delete all other elements, and produce a list `[A:B:B:C]`. Then we return truthy from the inner predicate (falsey from the whole program) if `[A:C]` isn't there.
> 3 votes

# Answer
## CJam (22 bytes)

```
{__Wf%m*{z~~=*}%\-e_!}

```

Online test suite. This is an anonymous block (function) which takes the elements as a two-level array, but the test suite does string manipulation to put the input into a suitable format first.

### Dissection

```
{         e# Begin a block
  _       e#   Duplicate the argument
  _Wf%    e#   Duplicate again and reverse each pair in this copy
  m*      e#   Cartesian product
  {       e#   Map over arrays of the form [[a b][d c]] where [a b] and [c d]
          e#   are in the relation
    z~~=* e#     b==c ? [a d] : []
  }%
  \-      e#   Remove those transitive pairs which were in the original relation
  e_!     e#   Test that we're only left with empty arrays
}

```
> 2 votes

# Answer
## Mathematica, 49 bytes

```
#/.{x=___,{a_,b_},x,{b_,c_},x}/;#~FreeQ~{a,c}:>0&

```

Pure function which takes a list of pairs. If the input list contains `{a,b}` and `{b,c}` but not `{a,c}` for some `a, b, c`, replaces it with `0`. Truthy is the input list, falsy is `0`.
> 2 votes

# Answer
# C++14, 140 bytes

As unnamed lambda returning via reference parameter. Requires its input to be a container of `pair<int,int>`. Taking the boring O(n^3) approach.

```
[](auto m,int&r){r=1;for(auto a:m)for(auto b:m)if (a.second==b.first){int i=0;for(auto c:m)i+=a.first==c.first&&b.second==c.second;r*=i>0;}}

```

Ungolfed and usage:

```
#include<vector>
#include<iostream>

auto f=
[](auto m,int&r){
  r=1;                         //set return flag to true
  for(auto a:m)                //for each element
    for(auto b:m)              //check with second element
      if (a.second==b.first){  //do they chain?
        int i=0;               //flag for local transitivity
        for(auto c:m)          //search for a third element
          i+=a.first==c.first&&b.second==c.second;
        r*=i>0;                //multiply with flag>0, resulting in 0 forever if one was not found
      }
}
;

int main(){
 std::vector<std::pair<int,int>> m={
  {1, 2}, {2, 4}, {6, 5}, {1, 4}
 };

 int r;
 f(m,r);
 std::cout << r << std::endl;

 m.emplace_back(3,6);
 f(m,r);
 std::cout << r << std::endl;

 m.emplace_back(3,5);
 f(m,r);
 std::cout << r << std::endl;

}

```
> 1 votes

# Answer
# Python 2, ~~91~~ ~~67~~ 55 bytes

```
lambda s:all(b-c or(a,d)in s for a,b in s for c,d in s)

```

Try it online!

-24 bytes thanks to Leaky Nun
-12 bytes thanks to Bubbler
> 1 votes

# Answer
# 05AB1E, 14 bytes

```
íâ€øʒθË}€нIKg_

```

Port of *@isaacg*'s Pyth answer, so make sure to upvote him/her as well!
Also takes the input as a list of pairs (e.g. `[[1,2],[3,4],...]`).

Try it online or verify all test cases.

**Explanation:**

```
í           # Reverse each pair of the (implicit) input-list
 â          # Get the cartesian product of this list and the (implicit) input-list,
            # creating pairs of pairs
  €         # Map over each pair of pairs:
   ø        #  Zip/transpose; swapping rows/columns
            # (we now have a list of [[x1,y2],[y1,x2]] of each pair in the input-list,
            # including those where [x1,y1]==[x2,y2])
    ʒ       # Filter this list of 2x2 blocks by:
     θ      #  Get the last row: [y1,x2]
      Ë     #  Check if the values in the pair are the same: y1==x2
    }€      # After the filter: map over each remaining 2x2 block:
      н     #  Leave just the first row: [x1,y2]
       IK   # Remove all input-pairs from this list of remaining pairs
         g  # And then check if the length
          _ # is equal to 0 (1 if the list was empty; 0 if not)
            # (after which the result is output implicitly)

```
> 1 votes

# Answer
**Axiom 103 bytes**

```
c(x)==(for i in x repeat for j in x repeat if i.2=j.1 and ~member?([i.1, j.2],x)then return false;true)

```

ungolfed:

```
c(x)==
  for i in x repeat
    for j in x repeat
       if i.2=j.1 and ~member?([i.1, j.2],x) then return false
  true

                                                                   Type: Void

```

the exercises

```
(2) -> c([[1,2],[2,4],[6,5],[1,4]])
   Compiling function c with type List List PositiveInteger -> Boolean
   (2)  true
                                                                Type: Boolean
(3) -> c([[7,8],[9,10],[15,-5]])
   Compiling function c with type List List Integer -> Boolean
   (3)  true
                                                            Type: Boolean
(4) -> c([[5,9],[9,54],[0,0]])
   Compiling function c with type List List NonNegativeInteger ->
      Boolean
   (4)  false

```
> 0 votes

# Answer
# Pyth - ~~22~~ 21 bytes

```
.Am},hdedQfqFtPTsM^Q2

```

Test Suite.
> 0 votes

# Answer
## Clojure, ~~56~~ 53 bytes

Update: Instead of using `:when` I'll just check that for all pairs of `[a b]` `[c d]` either `b != c` or `[a d]` is found from the input set.

```
#(every? not(for[[a b]%[c d]%](=[b nil][c(%[a d])])))

```

Original:

Wow, Clojure for loops are cool :D This checks that the `for` loop does not generate a falsy value, which occurs if `[a d]` is not found from the input set.

```
#(not(some not(for[[a b]%[c d]% :when(= b c)](%[a d]))))

```

This input has to be a set of two-element vectors:

```
(f (set [[1, 2], [2, 4], [6, 5], [1, 4]]))
(f (set [[7, 8], [9, 10], [15, -5]]))
(f (set [[5, 9], [9, 54], [0, 0]]))

```

If input must be list-like then `(%[a d])` has to be replaced by `((set %)[a d])` for extra 6 bytes.
> 0 votes

# Answer
Both these solutions are unnamed functions taking a list of ordered pairs as input and returning `True` or `False`.

# Mathematica, 65 bytes

```
SubsetQ[#,If[#2==#3,{#,#4},Nothing]&@@@Join@@@#~Permutations~{2}]&

```

`#~Permutations~{2}]` creates the list of all ordered pairs of ordered pairs from the input, and `Join@@@` converts those to ordered quadruples. Those are then operated upon by the function `If[#2==#3,{#,#4},Nothing]&@@@`, which has a cool property: if the middle two elements are equal, it returns the ordered pair consisting of the first and last numbers; otherwise it returns `Nothing`, a special Mathematica token that automatically disappears from lists. So the result is the set of ordered pairs that needs to be in the input for it to be transitive; `SubsetQ[#,...]` detects that property.

# Mathematica, 70 bytes

```
And@@And@@@Table[Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j},{i,#},{j,#}]&

```

`Table[...,{i,#},{j,#}]` creates a 2D array indexed by `i` and `j`, which are taken directly from the input (hence are both ordered pairs). The function of those two indices is `Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}`, which translates to "either the second element of `i` and the first element of `j` don't match, or else the input contains the ordered pair consisting of the first element of `i` and the last element of `j`". This creates a 2D array of booleans, which `And@@And@@@` flattens into a single boolean.
> 0 votes

# Answer
# APL(NARS), 39 chars, 78 bytes

```
{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}

```

test:

```
  f←{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}
  f (1 2) (2 4) (6 5) (1 4)
1
  f (7 8) (9 10) (15 ¯5)
1
  f (5 9) (9 54) (0 0)
0

```

one second 'solution' follow goto ways:

```
r←q w;i;j;t;v
r←1⋄i←0⋄k←↑⍴w⋄→3
r←0⋄→0
→0×⍳k<i+←1⋄t←i⊃w⋄j←0
→3×⍳k<j+←1⋄v←j⊃w⋄→4×⍳t[2]≠v[1]⋄→2×⍳∼(⊂t[1]v[2])∊w

```
> 0 votes

# Answer
## Common Lisp, 121 bytes

```
(lambda(x)(not(loop for(a b)in x thereis(loop for(c d)in x do(if(= b c)(return(not(member`(,a ,d) x :test #'equal))))))))

```

Try it online!
> 0 votes

---
Tags: code-golf, math, graph-theory, decision-problem
---


title: Count all my sheep

text:
# Question
Title: Count all my sheep
Sandbox

Given a boolean matrix representing my grass field, sheep length \\$n\\$ and wool thickness \\$k\\$, you will have to count my sheep.

A sheep is a single independent unbroken line of sheep length \\$n\\$ and thickness \\$k\\$.

```
#|##|# | #
#|  | #|#

```

are all valid sheep for \\$n=2,k=1.\\$

```
##|###|##  |  ##
##|###| ## | ##
##|   |  ##|##

```

are all valid sheep for \\$n=3,k=2.\\$

The diagonal sheep must be composed of horizontal lines of length k.

you are to count occurrences of valid sheep across a given grid.

Sheep will not intersect. You will be guaranteed that \\$n,k≥1\\$ and \\$n ≠ k.\\$

so for \\$n=2,k=1\\$:

```
##
   #
##  #

```

should give 3. Sheep may be right next to each other, and smaller animals may be present in the grid. You should get the max number of sheep that can be recognized from the grid.

Since the grass becomes really short after the sheep graze, your code must be short as well ().

## I/O

You may take the field in any way you like (2D array, string, boolean matrix, so on)

Output must be a single integer ≥ 0.

## Test Cases

`n=3, k=1`

```
#      #
 # ### #
  #
   #
   #
   #

```

`Output: 3`

---

`n=1,k=4`

```
####
     ####

    #
    #
  ####

```

`Output: 3`

---

`n=3, k=1`

```
#  #
 ##
 ###
  #
 #

```

`Output: 2`

---

`n=2, k=5`

```
###
###
###
###
###
###

```

`Output: 1`

# Answer
# Jelly, ~~66~~ 55 bytes

```
ZQ€Ƒȧ)Ẏ+€4ḶB¤fƑƇƊṆ)Ạ
ḶŒp,U;Ä,_@\€ƊƲ+þẎfƑƇŒPŒcÇaẎQƑ$ƲƇẈṀ

```

Try it online!

A pair of links that takes a left argument of `[n,k]` and a right argument of the 1-indexed coordinates of the cells containing the hashes. Returns an integer with the maximal number of sheep that can be found.

The intersecting diagonals as seen in the third example make this quite a bit harder. Removing this requirement saves 26 bytes.

## Explanation (outdated)

### Helper link

Takes a pair of sheep and checks whether they intersect

```
.ịⱮ                   | Last and first list member of each sheep
   Ẏ                  | Tighten (merge outer lists)
    œc3               | Combinations of length 3
               Ʋ€     | For each combination:
       _Ṫ             | - Subtract the last one from each of the first two
           ¥/         | - Reduce using the following:
         U×           |   - Reverse x and y for left hand item and then multiply by right
             >/       | - Reduce using greater than
                 s2   | Split into lists of length 2
                   I  | Increments (vectorises)
                    Ȧ | Any and all

```

## Main link

```
Ḷ                                           | [0..n-1], [0..k-1]
 Œp                                         | Cartesian product of these
             Ʋ                              | Following as a monad f(z)
   ,U                                       | - Pair z with reversed pairs of z
     ;      Ɗ                               | - Concatenate to the following applied to z:
      Ä                                     |   - Cumulative sum of each member of z
       ,_@\€                                |   - Paired with cumulative subtraction of each member of z with reversed arguments
              +þ                            | Outer sum with right hand argument (grid of sheep coordinates)
                Ẏ                           | Tighten -> list of all potential sheep
                 fƑƇ                        | Keep those where all coordinates are in the original list
                     ŒP                     | Power set
                                     ƒ€“”   | Reduce each list starting with an empty list on the left:
                                   ʋ?       | - If:
                             ¥€             |   - For each current sheep in list:
                           ,                |     - Pair with potential new sheep
                            Ç               |     - Call helper link to check if they intersect
                               o            |   - Or:
                                fƇ          |     - Filter any current sheep that contain an overlapping coordinate
                                  Ẹ         |   - Any of the above
                       ¹                    | - Then: identity function (i.e. don’t append new sheep)
                        ṭ@                  | - Else: tag new sheep to end of list
                                         Ẉ  | Lengths of lists of sheep
                                          Ṁ | Max

```
> 7 votes

# Answer
# Python3, 629 bytes:

```
lambda b,n,k:max(map(len,F({r for x,R in E(b)for y,_ in E(R)for r in S(b,x,y,n,k)})))
E=enumerate
def S(b,x,y,n,k):
 q=[(x,y,[],r,w,h)for r,w,h in[(0,n,k),(0,k,n),(1,k,n),(-1,k,n)]]
 while q:
  x,y,C,r,w,h=q.pop(0)
  if h==0:yield tuple(C);continue
  if x<len(b)and 0<=y and y+w<=len(b[0])and all(b[x][y:y+w]):q+=[(x+1,y+r,C+[(x,y+i)for i in range(w)],r,w,h-1)]
O=lambda x,y:any(t[0]==T[0]and t[1]>T[1]for t in x for T in y)and any(t[0]==T[0]and t[1]>T[1]for t in x for T in y)
def F(s,c=[]):
 if[]==(o:=[i for i in s if all({*j}&{*i}==set()for j in c)and 0==any(O(j,i)for j in c)]):yield c
 for i in o:yield from F(s-{i},c+[i])

```

Try it online!
> 2 votes

---
Tags: code-golf, grid, binary-matrix
---


title: Sum of combinations with repetition

text:
# Question
Title: Sum of combinations with repetition
Write the shortest code you can solving the following problem:

**Input:**

An integer X with `2 <= X` and `X <= 100`

**Output:**

Total combinations of 2, 3, and 5 (repetition is allowed, order matters) whose sum is equal to X.

**Examples:**

Input: `8`

Output: `6`, because the valid combinations are:

```
3+5
5+3
2+2+2+2
2+3+3
3+2+3
3+3+2

```

Input: `11`

Output: `16`, because the valid combinations are

```
5+3+3
5+2+2+2
3+5+3
3+3+5
3+3+3+2
3+3+2+3
3+2+3+3
3+2+2+2+2
2+5+2+2
2+3+3+3
2+3+2+2+2
2+2+5+2
2+2+3+2+2
2+2+2+5
2+2+2+3+2
2+2+2+2+3

```

Input: `100`

Output: `1127972743581281`, because the valid combinations are ... many

Input and output can be of any reasonable form. The lowest byte count in each language wins. Standard rules apply.

# Answer
> 10 votes
# Python 2, ~~46~~ 45 bytes

thanks to xnor for -1 byte

```
f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0

```

Try it online!

# Answer
> 7 votes
# Oasis, 9 bytes

```
cd5e++VT1

```

Try it online!

**Explanation**

```
        1    # a(0) = 1
       T     # a(1) = 0, a(2) = 1
      V      # a(3) = 1, a(4) = 1

             # a(n) =
c    +       # a(n-2) +
 d  +        # a(n-3) +
  5e         # a(n-5)

```

# Answer
> 3 votes
# Pyth, 9 bytes

```
/sM{y*P30

```

**Try it here!**

# Pyth, 16 bytes

```
l{s.pMfqT@P30T./

```

**Try it here**

### How?

1. Generates the prime factors of **30**, namely **\[2, 3, 5\]**, gets the powerset of it repeated **N** times, removes duplicate elements, sums each list and counts the occurrences of **N** in that.
2. For each integer parition **p**, it checks whether **p** equals **p ∩ primefac(30)**. It only keeps those that satisfy this condition, and for each remaining partition **k**, it gets the list of **k**'s permutations, flattens the resulting list by 1 level, deduplicates it and retrieves the length.

# Answer
> 3 votes
# Jelly, 11 bytes

```
5ÆRẋHŒPQḅ1ċ

```

Try it online!

## How it works

```
5ÆRẋHŒPQḅ1ċ -> Full program. Argument: N, an integer.
5ÆR         -> Pushes all the primes between 2 and 5, inclusively.
   ẋH       -> Repeat this list N / 2 times.
     ŒP     -> Generate the powerset.
       Q    -> Remove duplicate entries.
        ḅ1  -> Convert each from unary (i.e. sum each list)
          ċ -> Count the occurrences of N into this list.

```

# Answer
> 3 votes
# Perl, 38 bytes

Includes `+1` for `p`

```
perl -pE '$_=1x$_;/^(...?|.{5})+$(?{$\++})\1/}{' <<< 11; echo

```

Interesting enough I have to use `\1` to force backtracking. Usually I use `^` but the regex optimizer seems too smart for that and gives too low results. I'll probably have to start giving perl version numbers when using this trick since the optimizer can change at every version. This was tested on `perl 5.26.1`

This `49` is efficient and can actually handle `X=100` (but overflows on `X=1991`)

```
perl -pe '$\=$F[@F]=$F[-2]+$F[-3]+$F[-5]for($F[5]=1)..$_}{' <<< 100;echo

```

# Answer
> 2 votes
# JavaScript (ES6), 32 bytes

Same algorithm as in ovs' Python answer.

```
f=n=>n>0?f(n-2)+f(n-3)+f(n-5):!n

```

### Test cases

```
f=n=>n>0?f(n-2)+f(n-3)+f(n-5):!n

console.log(f(8))
console.log(f(11))
console.log(f(13))
```

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
30fIиæÙOI¢

```

Try it online!

# Answer
> 2 votes
# C, 41 bytes

```
G(x){return x>0?G(x-2)+G(x-3)+G(x-5):!x;}

```

Try it online!

# Answer
> 2 votes
# , ~~56~~ ~~49~~ 47 bytes

Recursive approach from ovs's answer. Giuseppe shaved off those final two bytes to make it 47.

```
f=pryr::f(+`if`(x<5,x!=1,f(x-2)+f(x-3)+f(x-5)))

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 43 bytes

```
Tr[Multinomial@@@{2,3,5}~FrobeniusSolve~#]&

```

Try it online!

Explanation: `FrobeniusSolve` computes all solutions of the unordered sum `2a + 3b + 5c = n`, then `Multinomial` figures out how many ways we can order those sums.

Or we could just copy everyone else's solution for the same byte count:

```
f@1=0;f[0|2|3|4]=1;f@n_:=Tr[f/@(n-{2,3,5})]

```

# Answer
> 1 votes
# MATL, 15 bytes

```
:"5Zq@Z^!XsG=vs

```

Very inefficient: required memory is exponential.

**Try it online!**

### How it works

```
:"       % For each k in [1 2 ... n], where n is implicit input
  5Zq    %   Push primes up to 5, that is, [2 3 5]
  @      %   Push k
  Z^     %   Cartesian power. Gives a matrix where each row is a Cartesian k-tuple
  !Xs    %   Sum of each row
  G=     %   Compare with input, element-wise
  vs     %   Concatenate all stack contents vertically and sum
         % Implicit end. Implicit display

```

# Answer
> 1 votes
# Pari/GP, 32 bytes

```
n->1/(1-x^2-x^3-x^5)%x^(n+1)\x^n

```

Try it online!

# Answer
> 1 votes
# Ruby, 41 bytes

```
f=->n{n<5?n==1?0:1:[n-5,n-2,n-3].sum(&f)}

```

Try it online!

This is a recursive solution, the recurcive call being: `[n-5,n-2,n-3].sum(&f)`.

# Answer
> 1 votes
# Regex  (ECMAScriptRME / Perl / PCRE / Raku`:P5`), 14 bytes

```
^(xxx?|x{5})*$

```

Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

Try it on replit.com (RegexMathEngine)
Try it online! \- Perl
Try it online! \- PCRE1
Try it online! \- PCRE2
Try it online! \- Raku

Same method as used for Fibonacci function or sequence, directly enumerating the ordered partitions.

```
^          # tail = input number
(
    xxx?   # tail-=2 or tail-=3
|          # or
    x{5}   # tail-=5
)*         # Loop the above as many times as possible, minimum zero
$          # Assert tail == 0

```

# Regex  (Raku), 14 bytes

```
^(xxx?|x**5)*$

```

Try it online!

Raku's plain regex alternation operator is `||`, and `|` does something special – it chooses the alternative making the longest match. But it'll still try every alternative when backtracking, so this makes no difference in the number of matches.

# Perl, 38 bytes (full program)

```
1x<>~~/^(...?|.{5})*$(??{++$i})/;say$i

```

Try it online!

Interestingly, I noticed after making this post that Ton Hospel already used the same basic method (and it predates my Perl Fibonacci answer by 3 years), but did it with Perl `-p` in 37 bytes (which can be reduced to 34 bytes), by exploiting Perl actually using literal `{` `}` to create the `-p` loop. I previously assumed Perl emulated a loop when launched with `-p`, not that it literally string-concatenated the program into a loop.

Using the `$\` trick (setting the `print` record separator), there's an alternative 38 byte flagless full program:

```
1x<>~~/^(...?|.{5})*$(??{++$\})/;print

```

Try it online!

Sadly it's only literally a `print` record separator and doesn't apply to `say`.

# Raku, 27 bytesSBCS (anonymous function)

```
{+m:ex/^(...?|.**5)*$/}o¹x*

```

Try it online!

# Answer
> 1 votes
# Vyxal, 9 bytes

```
⁺¤fẋfṗUṠO

```

Try it Online!

The header in the link halves the input to make things faster. It will return the same result if you remove it, but it may time out.

`⁺¤f` could alternatively be `30ǐ` (prime factors of 30) or `5~æ` (prime numbers up to 5).

```
⁺¤fẋfṗUṠO
⁺¤f       # Push the digits of 235: [2, 3, 5]
   ẋf     # Repeat the list the input times
     ṗ    # Powerset
      U   # Uniquify
       Ṡ  # Sum each
        O # Count the number of times the input appears in this array

```

# Answer
> 1 votes
# Desmos, 101 bytes

```
l=mod(floor(nk/n^{[1,2,3]}),n)
f(n)=∑_{k=1}^{n^3}0^{(n-total([2,3,5]l))^2}l.total!/∏_{a=1}^3l![a]

```

Ugh, no recursion sucks. I literally see all these answers going `f(n-2)+f(n-3)+f(n-5)`, like super golfy, but nope, can't do that in Desmos.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 1 votes
# Prolog (SWI), 50 bytes

```
N+O:-N>0,N-2+A,N-3+B,N-5+C,O is A+B+C;N<0,O=0;O=1.

```

Try it online!

# Answer
> 0 votes
# Jelly, 21 bytes

```
Œṗe€2,3,5$Ạ$ÐfŒ!Q$€ẎL

```

Try it online!

Surely can be golfed

# Answer
> 0 votes
# Pyth, 12 bytes

```
l{fqQsTy*P30

```

This is horrendously inefficient and hits the memory limit for inputs above 5.

Try it online

### Explanation

```
l{fqQsTy*P30
         P30   Get the prime factors of 30 [2, 3, 5].
        *   Q  Repeat them (implicit) input times.
       y       Take the power set...
  fqQsT        ... and filter the ones whose sum is the input.
l{             Count unique lists.

```

# Answer
> 0 votes
# Proton, 32 bytes

```
f=n=>n>0?f(n-2)+f(n-3)+f(n-5):!n

```

Try it online!

Same approach as ovs' answer.

# Answer
> 0 votes
# Haskell, 40 bytes

```
f 0=1
f n|n<0=0|1>0=f(n-2)+f(n-3)+f(n-5)

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 8 bytes

```
1λèƵ†S₆O

```

Port of *@ovs*' Python 2 answer.

Try it online or verify all test cases.

Outputting the infinite sequence would be 6 bytes instead:

```
λƵ†S₆O

```

Try it online.

**Explanation:**

```
 λ        # Start a recursive environment
  è       # to output the (implicit) input'th value
          # (which is output implicitly in the end)
1         # Starting with a(0)=1, and a(-1)=a(-2)=a(-3)=a(-4)=0
          # And where every next a(n) is calculated as:
   Ƶ†     #  Push compressed integer 235
     S    #  Convert it to a list of digits: [2,3,5]
      ₆   #  Calculate a(n-v) for each value v in this list: [a(n-2),a(n-3),a(n-5)]
       O  #  Sum this list together: a(n-2)+a(n-3)+a(n-5)

λ         # Start a recursive environment
          # to output the infinite sequence
          # (which is output implicitly in the end)
          # (implicitly starting with a(0)=1, and a(-1)=a(-2)=a(-3)=a(-4)=0)
          # And where every next a(n) is calculated as:
 Ƶ†S₆O    #  Same as above

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶ†` is `235`.

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


title: Is This an Equivalence Relation?

text:
# Question
Title: Is This an Equivalence Relation?
Given a relation, and a domain, output whether the relation is an equivalence relation.

## Context

For this challenge, a relation is defined as being a set of ordered pairs that is a subset of the cartesian product of a domain with itself. That is, \\$R \subset X \times X\\$.

For a relation \\$R\\$ to be an equivalence relation on domain \\$X\\$, it needs to be: a) reflexive, b) symmetric and c) transitive.

If a relation is reflexive, for all items in the relation's domain, the item paired with itself is in the relation. That is:

$$ \forall a \in X : (a, a) \in R $$

or as one might write in Python:

```
all([(a, a) in R for a in X])

```

If a relation is symmetric, for all pairs of items in the relation, the reverse of the pair is also in the relation. That is:

$$ \forall a, b \in X : (a, b) \in R \implies (b, a) \in R $$

or as one might write in Python:

```
all([(y, x) in R for x in X for y in X if (x, y) in R])

```

If a relation is transitive, for all items a, b and c in the relation's domain, `(a, b)` being in the relation and `(b, c)` being in the relation means that `(a, c)` is in the relation. That is:

$$ \forall a, b, c \in X : (a, b) \in R \land (b, c) \in R \implies (a, c) \in R $$

or as one might write in Python:

```
all([(x, z) in R for x in X for y in X for z in X if (x, y) in R and (y, z) in R])

```

## Worked Example

Let the domain of the relation be \\${1, 2, 3, 4}\\$ and the relation be \\${(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)}\\$

The relation is reflexive, as \\$(1, 1)\\$, \\$(2, 2)\\$, \\$(3, 3)\\$ and \\$(4, 4)\\$ are all in the relation.

The relation is symmetric, as \\$(1, 2)\\$ and \\$(2, 1)\\$ are in the relation, as are \\$(1, 3)\\$ and \\$(3, 1)\\$. As are \\$(2, 3)\\$ and \\$(3, 2)\\$.

The relation is transitive, as \\$(1, 2)\\$, \\$(2, 3)\\$, and \\$(1, 3)\\$ are in the relation.

Therefore, the relation is an equivalence relation.

## Rules

* The domain can be taken as a list of arbitrary objects (e.g. numbers, strings, a mix of numbers and strings) or any similar format. You do not need to take the domain if you take the relation as an adjacency matrix
* The relation can be taken as a list of ordered pairs/tuples, as an adjacency matrix or any other reasonable format. It can not be taken as a function object though.
* The domain will not be empty. That is, it will not be \\$\emptyset\\$ / `{}`
* The relation will not be empty. That is, it will not be \\$\emptyset\\$ / `{}`.
* Default decision-problem output rules apply

## Tests

*Assuming the domain is given as a list of integers and that the relation is given as a list of lists*

```
Domain, Relation => Equivalence?
[1, 2, 3, 4], [[1, 1], [2, 2], [3, 3], [4, 4]] => 1
[1, 2, 3, 4], [[1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]] => 1
[1, 2, 3, 4], [[1, 2], [2, 1], [3, 3]] => 0
[3, 4, 5], [[3, 4], [3, 5], [4, 5]] => 0
[1, 2, 3, 4, 5], [[1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4]] => 0
[1, 2, 3], [[1, 1]] => 0
[1, 2, 3], [[1, 2], [2, 3], [3, 3]] => 0
[1, 2, 3], [[1, 1], [1, 2], [2, 2], [2, 3], [3, 1], [3, 3]] => 0
[1, 2], [[1, 2], [2, 2]] => 0

```

This is code golf, so aim to get your programs as short as possible.

# Answer
# 05AB1E, 3 bytes

```
δQQ

```

Try it online!

Takes input as an adjacency matrix.

## Explanation

```
δ      double vectorized - for each pair of rows in the adjacency matrix
Q      check if they are equal
Q      then check if the matrix produced by that is equal to the original matrix

```

If the input matrix is an equivalence relation, then it's easy to see that two values are equal iff their rows are equal, so the algorithm will return true.

Otherwise, since `δQ` returns an equivalence relation, it's impossible for it to be equal to the input.
> 16 votes

# Answer
# Prolog (SWI), 95 bytes

```
X*Y:-member(X,Y).
X-Y:-forall(X,Y).
D+R:-X*D-[X,X]*R,[X,Y]*R-[Y,X]*R,([X,Y]*R,[Y,Z]*R)-[X,Z]*R.

```

Try it online!

Predicate that succeeds if the relation given is an equivalence relation. Call as `+(Domain, Relation)` or `Domain+Relation`.
> 9 votes

# Answer
# Python NumPy, 33 bytes

```
lambda M:(M^M.T@M<M.any(0)).all()

```

Attempt This Online!

Expects adjacency matrix.

### How?

First note that arithmetic is boolean, so 1+1=1.

The test can only be satisfied if

1. there is no empty column
2. M is symmetric (M=M^T)
3. M is idempotent (M^2=M)

together these imply

4. the diagonal of M is set

4 corresponds to "reflexive", 3 to "transitive" and 2 to "symmetric"
> 8 votes

# Answer
## Python 2, 86 bytes

```
lambda X,R:any(R[a][c]<R[a][b]&R[b][c]|R[c][a]|(a==c)for a in X for b in X for c in X)

```

Try it online!

Takes the relation `R` as a two-level dictionary so we can write `R[a][b]` to query whether \\$(a,b) \in R\\$. Outputs `True/False` inverted.

---

## Python 2, 55 bytes

```
lambda R:all(R[a]=={a}|R[b]for a in R for b in{a}|R[a])

```

Try it online!

Uses a more liberal input format of a dictionary taking each \\$a \in X\\$ to a set of all \\$\\{b:(a,b) \in R\\}\\$. We no longer need to take `X` as input because the keys of the dictionary will do.

---

## Python 2, 54 bytes

```
lambda R:R=={a:{b for b in R if R[a]==R[b]}for a in R}

```

Try it online!

Based on Command Master's solution. I/O as above.

---

## Python 2, 39 bytes

```
lambda M:M==[map(a.__eq__,M)for a in M]

```

Try it online!

A more direct port of Command Master's solution, with input as a adjacency matrix, that is, a list of lists of Booleans. Less golfed:

**41 bytes**

```
lambda M:M==[[a==b for b in M]for a in M]

```

Try it online!
> 5 votes

# Answer
# Factor, 32 bytes

```
[ 3 dupn [ = ] cartesian-map = ]

```

Try it online!

Port of @CommandMaster's 05AB1E answer (and so takes an adjacency matrix as input).
> 4 votes

# Answer
# Charcoal, 9 bytes

```
⁼θＥθＥθ⁼ιλ

```

Try it online! Link is to verbose version of code. Takes input as an adjacency matrix and outputs a Charcoal boolean, i.e. `-` for an equivalence relation, nothing if not. Explanation: Port of @CommandMaster's 05AB1E solution.

```
 θ          Input matrix
⁼           Is equal to
   θ        Input matrix
  Ｅ         Map over rows
     θ      Input matrix
    Ｅ       Map over rows
       ι    Outer row
      ⁼     Is equal to
        λ   Inner row
            Implicitly print

```

14 bytes to take input as an adjacency matrix of bit strings for convenience:

```
ＷＳ⊞υι⁼υＥυ⭆υ⁼ιλ

```

Try it online! Link is to verbose version of code.
> 3 votes

# Answer
# Jelly, 3 bytes

```
⁼þ⁼

```

Try it online!

another port of Command Master's 05AB1E answer, so takes an adjacency matrix as input
> 3 votes

# Answer
# APL (Dyalog Classic), 6 bytes

```
⊢≡∧.=⍨

```

Try it online!

Similar to Command Master's submission, but compares each column to each row, instead of pairs of rows.
> 2 votes

# Answer
# Vyxal `2`, 6 bytes

```
v‡$v⁼⁼

```

Try it Online!

Input as adjacency matrix. Yet another port of Command Master's answer (YAPOCMA).

Using a different flag:

# Vyxal `r`, 6 bytes

```
ƛ?v⁼;⁼

```

Try it Online!
> 1 votes

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


title: Is that number a Two Bit Number™?

text:
# Question
Title: Is that number a Two Bit Number™?
Let's start by defining a Two Bit Number™:

* It is a positive integer
* When expressed as a binary string it has exactly 2 true bits OR
* When expressed as a decimal number, it has exactly 2 of the numeral one, and all other numerals are zero.

Or as a sentence

A Two Bit Number™ is a number which contains exactly 2 of the numeral 1 and no other numerals besides 0, when expressed as a decimal string or a binary number.

So here area all the Two Bit Numbers™ between 0 and 256

```
Dec  Bin       Type
3    00000011  Binary
5    00000101  Binary
6    00000110  Binary
9    00001001  Binary
10   00001010  Binary
11   00001011  Decimal
12   00001100  Binary
17   00010001  Binary
18   00010010  Binary
20   00010100  Binary
24   00011000  Binary
33   00100001  Binary
34   00100010  Binary
36   00100100  Binary
40   00101000  Binary
48   00110000  Binary
65   01000001  Binary
66   01000010  Binary
68   01000100  Binary
72   01001000  Binary
80   01010000  Binary
96   01100000  Binary
101  01100101  Decimal
110  01101110  Decimal
129  10000001  Binary
130  10000010  Binary
132  10000100  Binary
136  10001000  Binary
144  10010000  Binary
160  10100000  Binary
192  11000000  Binary

```

The challenge:

* Write some code which accepts a number and outputs true or false (or some indicator of true or false) if it is a Two Bit Number™.
* Input will always be an integer, but it may not always be positive.
* It can be in any language you like.
* It's code golf, so the fewest bytes wins.
* Please include links to an online interpreter for your code (such as tio.run).

## Test Cases

Binary Two Bit Numbers™:

```
3
9
18
192
288
520
524304

```

Decimal Two Bit Numbers™:

```
11
101
1001
1010
1100
1000001
1100000000
1000000010

```

Non Two Bit Numbers™:

```
0
1
112 (any numerals over 1 prevent it being a Decimal Two Bit Number™)
200
649
-1
-3

```

---

Fun fact: I was not able to find any DecimalBinary Two Bit Numbers™ checking up to about 14 billion, and I have a hypothesis that such a number does not exist, but I have no mathematical proof. I'd be interested to hear if you can think of one.

# Answer
> 20 votes
# Python 3, ~~68~~ ~~62~~ 48 bytes

-6 bytes thanks to xnor!
-14 bytes thanks to Jitse!

```
lambda n:' 11 'in f' {n:b} {n} '.replace('0','')

```

Try it online!

# Answer
> 12 votes
# Haskell, 50 bytes

```
f n=or[b^x+b^y==n|b<-[2,10],x<-[0..n],y<-[x+1..n]]

```

Try it online!

Brute force search.

## Alternative 50 bytes

```
b!0=0
b!x=rem x b^3+b!quot x b
f n=2!n==2||10!n==2

```

`b!x` computes a base-`b` “cubed digit sum” of `x`. For example, `10!123` = \\$1^3+2^3+3^3\\$ = 36.

We check if either of `2!n` or `10!n` equals 2.

`quot` is necessary to support negative input. It rounds toward zero, whereas `div` rounds down, meaning `div (-1) 10 == (-1)`, causing an infinite loop.

# Answer
> 10 votes
# JavaScript (ES6), 38 bytes

Returns **0** for *true*, or a non-zero integer for *false*.

```
n=>(g=n=>!(n&=n-1)|n&n-1)(n)*g('0b'+n)

```

Try it online!

### How?

The helper function **g** removes the two least significant bits set in `n` by computing `n & (n - 1)` twice. If we get **0** the first time, it means that `n` has at most one bit set, which is not enough. If we *don't* get **0** the second time, it means that `n` has more than 2 bits set, which is too much.

For the decimal test, we invoke **g** with `'0b' + n` to parse it as a binary value. If `n` is negative, this gives something such as `'0b-10100'`, which is NaN'ish and fails as expected.

---

# JavaScript (ES6),  ~~40~~  39 bytes

Returns a Boolean value telling whether the input is *not* a Two Bit Number.

```
n=>[n,'0b'+n].every(n=>!(n&=n-1)|n&n-1)

```

Try it online!

# Answer
> 9 votes
# 05AB1E, ~~8~~ 7 bytes

```
b‚€{11å

```

Try it online or verify all test cases.

`€{` could alternatively be  for the same bytecount:
Try it online or verify all test cases.

**Explanation:**

```
b        # Convert the (implicit) input-integer to a binary string
 ‚       # Pair it together with the (implicit) input-integer
  €{     # Sort the digits in each string
    11å  # And check if this pair contains an 11 (which is truthy for "011","0011",etc.)
         # (after which the result is output implicitly)

  0м     # Remove all 0s from both the binary string and input in the pair

```

# Answer
> 8 votes
# APL (Dyalog Extended), 18 bytes

```
2∊+/↑(*3)2 10⊤¨0⌈⎕

```

Try it online!

Jo King's 18 byte solution.

# APL (Dyalog Extended), ~~20 21 20 26~~ 25 bytes

```
{<⍵:2∊+/↑(⊂×⍨⍎¨⍕⍵)⍪⊂⊤⍵⋄0}

```

Try it online!

+1 byte after correcting the answer(ovs).

-1 byte after ovs's suggestion.(yay!)

+7 bytes after properly accepting negative test cases.

-1 byte from Adám.

Inspired from the J solution.

## Explanation

```
{⍵>0:2∊+/↑(⊂2*⍨⍎¨⍕⍵)⍪⊂⊤⍵⋄0}
 ⍵>0:                       If number is positive
                      ⊤⍵    Decode number to binary
            ×⍨⍎¨⍕⍵          square each digit
         ↑ ⊂        ⍪⊂      join into two rows
       +/                   sum each row
     2∊                     is two present in it?
                         ⋄0 otherwise return 0

```

# Answer
> 6 votes
# Brachylog, 9 bytes

```
ℕ{ḃc|}o11

```

Try it online!

Somewhat embarrassed I didn't think to translate other solutions' sort-based approaches earlier...

A more fun solution:

# Brachylog, 10 bytes

```
ℕ{|ẹ~ḃ}ḃ+2

```

Try it online!

```
ℕ             The input is a whole number (necessary to exclude -3 etc.),
 {|   }       which either unchanged or
   ẹ          with its decimal digits
    ~ḃ        interpreted as binary (impossible if any ≥ 2),
       ḃ      has binary digits
        +2    that sum to 2.

```

# Brachylog, ~~12~~ 11 bytes

```
ℕ{ḃ|ẹ}<ᵛ²+2

```

Try it online!

-1 byte thanks to xash

```
ℕ              The input is a whole number,
 { | }         and either
  ḃ            its binary digits
    ẹ          or its decimal digits
      <ᵛ²      are all less than 2
         +2    and sum to 2.

```

# Answer
> 6 votes
# , ~~50~~ ~~49~~ ~~48~~ 46 bytes

*Edit: -1 byte, and then -1 more byte, and then -2 more bytes, thanks to Robin Ryder*

```
gsub(0,'',n<-scan())!=11&sum(n%/%2^(0:n)%%2)-2

```

Try it online!

Tests for decimal 2bit numbers using text manipulation to remove '`0`' digits and check whether the result is *not* '`11`', and then tests for binary 2bit numbers by calculating the binary digits and checking if they *do not* sum to `2`. Returns FALSE for 2bit numbers and TRUE for non-2bit numbers.
It seems a bit clunky to do two different kinds of tests for essentially the same feature, but somehow comes-out quite short...

# Answer
> 6 votes
# Regex (ECMAScript), ~~70~~ ~~68~~ ~~56~~ 52 bytes

*-4 bytes by successfully combining base \\$2\\$ and \\$10\\$ into a single expression, as was already accomplished in the other versions*

```
^((x)|(x))((((\2*)\3*)(\2\7){8}x(?=\6$))*x){2}\2{8}$

```

Try it online!

Takes its input in unary, as a sequence of `x` characters whose length represents the number.

Here are some examples of how this **52 byte** version works:

```
Example input: 1001000
Choose base 10 and subtract 1 from tail
1000999
Iteration 1 of the outer loop:
1000999
100099
10009
1000
tail -= 1
999
Iteration 2 of the outer loop:
999
99
9
tail -= 1
8
Assert tail == 10 - 2

Example input: 11
Choose base 10 and subtract 1 from tail
10
Iteration 1 of the outer loop:
10
tail -= 1
9
Iteration 2 of the outer loop:
9
tail -= 1
8
Assert tail == 10 - 2

```

The regex, pretty-printed and commented:

```
^                # tail = N = input number
# Pick which base to operate in, and tail -= 1
(
    (x)          # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
    (x)          # \3 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=2
)
# Assert tail is the sum of two powers of B
(
    (
        # tail = (tail + 1) / B - 1
        ((\2*)\3*)   # if \2=1, then \6 = \7 = (tail + 1) / 10 - 1;
                     # if \3=1, then \6 =      (tail + 1) /  2 - 1, and \7 = 0
        (\2\7){8}
        x
        (?=\6$)
    )*               # Loop the above zero or more times
    x                # tail -= 1
){2}                 # Loop the above exactly twice
\2{8}$               # Assert tail == B - 2

```

*The following text applies to the earlier 56 byte version:*

This turned out to be very similar to Neil's 58 byte regex. I looked at the byte count, but not at the regex itself, in that answer's heading before working on the problem myself. It took me a while to figure out how to make a non-ECMAScript-specific regex shorter than 70 bytes. The hangup for me was, that I was doing it like this:

```
^((((x+)\4{8}(?=\4$))*x(?=(xx)*$)){2}|(((x+)(?=\8$))*x(?=(xx)*$)){2})$

```

In order to prevent the loop from subtracting the same power of 2 or 10 twice (and matching, for example, 512 and 200) I had to use `(?=(xx)*$)` to assert that tail is even after subtracting 1 (this works for both 2 and 10, as they are both even). Finally I figured out that I could just use two alternatives inside the `(`...`){2}` loop, one that must do at least one division before subtracting 1, and one that can only subtract 1 if it's the first thing done, and this saved 7 bytes per base, giving 70 - 2×7 = 56 bytes:

```
^((((x+)\4{8}(?=\4$))+x|^x){2}|(((x+)(?=\7$))+x|^x){2})$

```

# Regex (ECMAScript / Perl / PCRE / Java / Boost / Python / .NET), 54 bytes

```
^(x?)(^x|\B)((((\1*)\2*)(\1\6){8}x(?=\5$))*x){2}\1{8}$

```

This is a port of the 52 byte ECMAScript version to be NPCG-behavior-independent and compatible with a wide variety of regex engines including ECMAScript (i.e., "generic"). This is done by changing `((x)|(x))` (where `\2` and `\3` are differently 1 or unset) to `(x?)(^x|\B)` (where `\1` and `\2` are differently 1 or 0).

Try it online! \- ECMAScript
Try it online! \- Perl
Try it online! \- PCRE
Try it online! \- Java
Try it online! \- Boost (throws some errors, but this is fixed in later versions than what is on TIO)
Try it online! \- Python
Attempt This Online! \- Python (`import regex`)
Try it online! \- .NET

It exposes a bug in the regex engine used by Ruby. The 56 byte regex works in Ruby: Try it online!
But the 54 byte regex does not: Try it online! Boiling this down, it appears that `^((x*)(){4}(?=\2$))*x$` matches powers of 2 just fine, but `^((x*)(){5}(?=\2$))*x$` does not.

Similarly, while it works with Python's `re` module (see above), it exposed a bug in the the more powerful `regex` module: Try it online! \[This bug has now been fixed!\]

It also exposes a bug in older versions of Boost, as stated above – throwing an error on `480`, `512`, `584`, and many other larger numbers. In older versions of Notepad++ (using the older Boost versions), this is treated as a match.

# Regex (ECMAScript+`(?*)` / PCRE2 v10.35+), ~~54~~ 47 bytes

```
^(?*(x)|(x))((((\1*)\2*)\6{8}(?=\5$))+x|^x){2}$

```

Attempt This Online! \- PCRE2

In this version, the two bases \\$10\\$ and \\$2\\$ are combined, by choosing between them using the initial `(x)|(x)`. Thanks to molecular lookbehind `(?*)`, this can be done without subtracting 1 from the number being tested:

```
^
(?*
    (x)          # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
    (x)          # \3 = 1 - \2; B=2
)
# Assert tail is the sum of two powers of B
(
    # Alternative #1: Divide evenly by B as many times as possible, at least once
    # (meaning tail has to be initially divisible by B), then subtract 1.
    (
        ((\1*)\2*)\6{8}(?=\5$)   # assert tail % B == 0; tail /= B
    )+
    x                            # tail -= 1
|
    # Alternative #2: Don't divide at all, and just subtract 1, but only if this is
    # the first thing we do. If this path is taken, only alternative #1 can next.
    ^x                           # assert tail == N; tail -= 1
){2}             # Loop the above exactly twice
$                # Assert tail == 0

```

When `\1`=1 and `\2`=0, `((\1*)\2*)\6{8}(?=\5$)` behaves like `(x*)\5{8}(?=\5$)`, dividing by \\$10\\$.
When `\1`=0 and `\2`=1, `((\1*)\2*)\6{8}(?=\5$)` behaves like `(x*)(?=\5$)`, dividing by \\$2\\$.

# Regex (ECMAScript 2018 / Python`regex` / .NET), 51 bytes

```
((x)|(x))$(?<=^(x((?<=^\6)\7{8}(\3*(\2*)))+|x$){2})

```

**Try it online! \- ECMAScript 2018 (Node v11.6.0, with bug workaround)
Attempt This Online! \- ECMAScript 2018 (Node v17.3.0+, bug fixed)**
Attempt This Online! \- Python `import regex`
Try it online! \- .NET

This is a port of the ECMAScript+`(?*)` version to variable-length right-to-left-evaluated positive lookbehind `(?<=)`. It starts 1 off from the end, reaches the end by capturing a determination of whether to work in base \\$10\\$ or \\$2\\$, then does the rest of its work going backwards.

It **exposed a bug** present in the ECMAScript 2018 regex engine of both SpiderMonkey (Firefox) and V8 (Chrome / Node). To make this regex work, the **m**ultiline flag must be enabled. It fails to work without the flag. pxeger has reported the bug. It was since then fixed.

```
(
    (x)          # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
    (x)          # \3 = 1 - \2; B=2
)
$                # head = N = input number
# Assert head is the sum of two powers of B
(?<=             # Lookbehind - evaluated right-to-left
    ^            # Assert head == 0
    (
        # Alternative #1: Divide evenly by B as many times as possible, at least once
        # (meaning head has to be initially divisible by B), then subtract 1.
        x                             # head -= 1
        (
            (?<=^\6)\7{8}(\3*(\2*))   # assert head % B == 0; head /= B
        )+
    |
        # Alternative #2: Don't divide at all, and just subtract 1, but only if this is
        # the first thing we do. If this path is taken, only alternative #1 can next.
        x$                            # assert head == N; head -= 1
    ){2}     # Loop the above exactly twice
)

```

# Regex (Perl / PCRE / Boost / Python / Ruby / .NET), ~~51~~ 39 bytes

```
^()?(((x*)(?(1)\4{8})(?=\4$))+x|^x){2}$

```

Try it online! \- Perl
Try it online! \- PCRE
Try it online! \- Boost
Try it online! \- Python
Attempt This Online! \- Python (`import regex`)
Try it online! \- Ruby
Try it online! \- .NET

This version takes advantage of a conditional group `(?(1)\4{8})` to determine whether to work in base \\$10\\$ or \\$2\\$.

```
^
()?              # \1 = choose between B=10 (if set) or B=2 (if unset)
# Assert tail is the sum of two powers of B
(
    # Alternative #1: Divide evenly by B as many times as possible, at least once
    # (meaning tail has to be initially divisible by B), then subtract 1.
    (
        (x*)(?(1)\4{8})(?=\4$)   # assert tail % B == 0; tail /= B
    )+
    x                            # tail -= 1
|
    # Alternative #2: Don't divide at all, and just subtract 1, but only if this is
    # the first thing we do. If this path is taken, only alternative #1 can next.
    ^x                           # assert tail == N; tail -= 1
){2}             # Loop the above exactly twice
$                # Assert tail == 0

```

# Regex (Perl / PCRE / Java / Boost / Python / Ruby / .NET), 44 bytes

```
^()?(((x*)(\1\4{8}|(?!\1))(?=\4$))+x|^x){2}$

```

**Try it online! - Java** / Perl / PCRE / Boost / Python / Ruby / .NET

```
^(()|())(((x*)(\2\6{8}|\3)(?=\6$))+x|^x){2}$

```

**Try it online! - Java** / Perl / PCRE / Boost / Python / Ruby / .NET

These are ports of the 39 byte version, to a regex flavor that has no conditionals. In the first one, the `(?(1)\4{8})` conditional is replaced with `(\1\4{8}|(?!\1))` which behaves equivalently at a cost of 5 extra bytes. In the second the expression `(()|())` instead of `()?` is used to determine the mode (which either sets `\2` or `\3` leaving the other one unset), and the conditional is replaced with `(\2\6{8}|\3)`. The regex is otherwise unchanged (except for shifting the capture group numbering).

# Answer
> 6 votes
# Vyxal, 8 bytes

```
₍fb3eṠ2c

```

Try it Online!
Try it Online! \- test cases only

```
₍    # Parallel Apply Wrap - applies the following two operations to the input,
     # wrapping the two results in a list.
  f  # Flatten (convert decimal string into list of digits)
  b  # Convert to binary (as a list of digits, which will all be negative if the
     # number is negative)
3e   # Cube (applied to each digit)
Ṡ    # Vectorized Sum (apply individually to each list)
2c   # Does the resulting list (of two items) contain the number 2?

```

Alternatively instead of `3e` to cube each digit, `ʀṠ` could be used to triangularize each digit, or `√√` to take the fourth root of each digit.

If not for the fact that the challenge requires that negative numbers be tested (and that they can't be Two Bit Numbers™), this could be 7 bytes, because we could use `²` to square instead of `3e` to cube.

# Vyxal, ~~10~~ 9 bytes

```
∆b"vs⌊11c

```

Try it Online!
Try it Online! \- test cases only

```
∆b   # Convert to binary as a string.
"    # Pair that string and the original number as two items in a list.
vs   # Vectorized Sort - sort each individual item in the list (sorts the digits)
⌊    # Floor - in this context, used to interpret strings as decimal and convert
     # them to integers.
11c  # Does the resulting list (of two items) contain the number 11?

```

This solution was unusable at the time of my original posting, due to  not working on `0`. The bug has since been fixed.

# Answer
> 5 votes
# , 25 bytes

```
0&<*10&#.inv+&(2=1#.*~)#:

```

Try it online!

### How it works

```
0&<*10&#.inv+&(2=1#.*.~)#:
0&<*                       input is a positive number
    10&#.inv               list of digits base 10
                        #: list of digits base 2
            +&(        )   OR the result of both …
                    *.~    square each digit (x>=2 will be larger than 2)
                 1#.       sum
               2=          is equal to two

```

If there is a DecimalBinary number, the `+` as OR could result in 2, thus needing one byte more for `+.`.

# Answer
> 5 votes
# Japt `-!`, ~~9~~ 8 bytes

~~There's gotta be a way to shave at least one more byte off this.~~
I got there eventually!

```
ìÍ-B©a¢ñ

```

Try it or run all test cases

```
ìÍ-B©a¢ñ     :Implicit input of integer U
ì            :Convert to digit array
 Í           :Sort (and implicitly convert back to integer)
  -B         :Subtract 11
    ©        :Logical AND with
     a       :Absolute difference of B and
      ¢      :Convert U to binary string
       ñ     :Sort
             :Implicit output of logical NOT of result

```

# Answer
> 5 votes
# Raku, 25 bytes

```
{$_|.base(2)~~/^10*10*$/}

```

Try it online!

Checks if the input or the base 2 of the input matches the regex `^10*10*$`

# Answer
> 5 votes
# Julia 1.3, ~~61~~ ~~57~~ 50 bytes

using a regex on the binary and decimal representation of the number

```
!x=count(r"^0*10*10*$",x)>0
~x=!"$x"|!bitstring(x)

```

Try it online!

# Answer
> 4 votes
# Factor, ~~79~~ ~~74~~ 70 bytes

-4 bytes thanks to chunes

```
: n ( n -- ? ) dup present swap >bin [ 48 swap remove "11"= ] bi@ or ;

```

Try it online!

# Answer
> 4 votes
# , ~~71~~ 64 bytes

-7 bytes thanks to Dominic van Essen

```
`+`=function(n,k)sum((n%/%k^(0:n)%%k)^2)-2
n=scan();n<0|n+2&n+10

```

Try it online!

Output is reversed: gives `FALSE` if the input is a Two Bit Number, and `TRUE` if it is not.

The helper function `+` converts an integer to a vector of digits in base `k` (we need `k=2` and `k=10`). Then sum the square of these digits. This sum is equal to 2 exactly for a Two Bit Number.

Will fail due to memory limits for large input, in which case you can use `0:log2(n)` instead of `0:n` and `||` instead of `|`: Try it online!.

# Answer
> 4 votes
# Charcoal, ~~21~~ 13 bytes

```
№⟦⁻θ0⁻⍘Ｎ²0⟧11

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a two bit number, nothing if not. Port of @Kaddath's PHP answer. Explanation:

```
   θ            Input as a string
  ⁻ 0           Remove zeros
       Ｎ        Input as a number
      ⍘ ²       Convert to base 2
     ⁻   0      Remove zeros
 ⟦        ⟧     Make into a list
№          11   Count occurances of literal string `11`

```

# Answer
> 4 votes
# Python 3, 67 bytes

```
lambda n:n>2in{g(n,2),g(n,10)}
g=lambda x,b:x and(x%b)**2+g(x//b,b)

```

Try it online!

Port of my Haskell answer. (I took the test harness from ovs's Python answer. Thanks!)

# Answer
> 4 votes
# Perl 5 `-lp`, 35 bytes

```
$_=grep/^10*10*$/,$_,sprintf"%b",$_

```

Try it online!

returns 1 or 2 (if a number can be decimal and binary Two Bit number) for true, 0 for false.

# Answer
> 4 votes
# Ruby 2.7, 44 bytes

```
->n{[2,10].any?{n.to_s(_1).tr(?0,'')=='11'}}

```

**Explanation:**

```
->n{                      # a lambda with one argument
    [2,10].any?{          # Return true if for either of 2 or 10...
      n.to_s(_1)          # input in that base
      .tr(?0,'')          # after removing all 0-s
      =='11'              # is exactly '11'
    }
}

```

## Equivalent in ruby \< 2.7, 46 bytes

```
->n{[2,10].any?{|b|n.to_s(b).tr(?0,'')=='11'}}

```

Try it out

# Answer
> 4 votes
# Retina 0.8.2, 36 bytes

```
^\d+
$*1¶$&
+`^(1+)\1
$+0
m`^10*10*$

```

Try it online! Link includes most test cases (the larger ones cause Retina to run out of memory). Explanation:

```
^\d+
$*1¶$&

```

If the input is non-negative, prefix it with a unary copy.

```
+`^(1+)\1
$+0

```

Begin converting the unary copy to binary. At this point there are too many zeros in the result, but fortunately they are irrelevant.

```
m`^10*10*$

```

Match either number as being a two bit number.

# Answer
> 4 votes
# MUMPS, 55 bytes

```
 i $tr(n,01) f  q:n<1  s %=n#2_%,n=n\2
 w $tr(n_%,0)=11

```

Try it online!

* Each line has a leading space so that the commands aren't interpreted as line labels.
* `$tr` is short for `$translate` which replaces one or more characters in a string with one or more other characters. For example, `$tr("abc","a","c")` evaluates to `"cbc"`. Omitting the third parameter is the same as passing the empty string, in which case the characters in the second parameter are removed. Therefore `$tr(n,01)` is nonempty only if it contains any characters other than 0 or 1, and `$tr(n,0)` removes all zeroes from the string.
* `i` is short for `if`, its condition is the following `$tr(n,01)` expression. The condition is only met if `n` needs to be converted to binary.
* `f` is short for `for` and loops until the `quit` condition (`q:n<0`) becomes true. The loop converts `n` to binary in `%`.
* `w` is short for `write` and prints the expression that follows it.
* If the `for` loop was executed then `n` will be empty or zero, otherwise `%` will be empty. `n_%` concatenates the two so that the result can be evaluated in a single expression.

# Answer
> 3 votes
# K (ngn/k), ~~25~~ 24 bytes

-1 byte thanks to ngn

```
{("11"~($x)^$0)+2=+/2\x}

```

Try it online!

# Answer
> 3 votes
# Jelly, 8 bytes

```
,BṢ€Ḍ11e

```

Try it online!

## Explanation

```
,BṢ€Ḍ11e  Main Link
,         Pair the integer with
 B        Convert the integer to binary
  Ṣ€      Sort Each (sorts the digits of the integer implicitly)
    Ḍ     Convert from decimal to integer
     11e  Is 11 in this list?

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 46 bytes

```
!FreeQ[Tr/@(#~IntegerDigits~{10,2}^2),2]&&#>0&

```

Try it online!

*-1 byte from @att*

# Answer
> 3 votes
# Scala, ~~73~~ ~~63~~ ~~54~~ 52 bytes

```
n=>Seq(n+"",n.toBinaryString)find(_ matches "10*"*2)

```

Try it online!

**Edit:**

* Thanks to @Tomer Shetah for pointing out that lamdbas do not require their type definition (see comments), which reduces the length from 73 to 63 bytes
* Thanks to @user for adding some nice syntax tricks that further reduce the length from 63 to 54 bytes
* Again thanks to @user for the comment on using `find` instead of `exists`, which saves another 2 bytes and is valid for this challenge, since it is stated that a valid solution should *"output true or false (or some indicator of true or false)"*

# Answer
> 3 votes
## PCRE Regex, ~~100~~ 95 bytes

```
^(((?(2)\2\2|.))*.)(?!\1)((?(3)\3\3|.))*.$|^(((?(5)\5{10}|.{9}))*.)(?!\4)((?(6)\6{10}|.{9}))*.$

```

Assume unary input (no support for negative numbers).

Should work in flavors with support for conditional regex and forward-declared back-reference.

The regex consists of 2 similar portions, one check for binary and the other for decimal.

* The code makes use of sum of geometric series to match 2n and 10n.
1 + (1 + 2 + 22 \+ ... + 2n) = 2n+1
1 + 9 * (1 + 10 + 102 \+ ... + 10n) = 10n+1
* Then it try to decompose the number into sum of 2n \+ 2k (or 10n \+ 10k for decimal), and check that 2n != 2k

Update:

* Drops unused capturing group
* Drops `$` in `(?!\1$)` since it's fine if we reject 2n \< 2k

regex101

# Answer
> 3 votes
# Generic regex, ~~58~~ 56 bytes

```
^(((1+)(?=\3$))+1|^1){2}$|^(((1+)\6{8}(?=\6$))+1|^1){2}$

```

Try it online! Link includes test harness written in Retina 0.8.2 although the regex itself should work in most engines. Takes input in signed unary i.e. `^-?1*$`. Explanation: Given `k` and `m` we can write a specific test for a number being the sum of `k` distinct powers of `m` by repeatedly dividing by `m` and subtracting `1` `k` distinct times along the way, before we eventually reach zero:

```
^(((1+)\3{<m-2>}(?=\3$))+1|^1){<k>}$

```

where `<m-2>` and `<k>` represent substitutions for the specific values being tested (subject to trivial reductions such as `\3{0}` being a no-op). This works as follows:

```
   (1+)                                 Find `i` such that
       \4{<m-2>}                        `i+(m-2)i=(m-1)i` is equal to
                (?=\4$)                 `n-i`, therefore `i=n/m`.
  (                    )+               Divide `n` by `m` at least once
                         1              Then decrement
 (                        |^1)          Or on the first loop just decrement
                              {<k>}     Decrement `k` distinct times
^                                  $    Consume entire input

```

The problem then reduces to an alternation of two such tests. Edit: Saved 2 bytes by noticing from @Deadcode's answer that `(((...)+|^)1)` is the same as `((...)+1|^1)`.

# Answer
> 3 votes
# Husk, ~~11~~ 10 bytes

```
#2§¤eṁ^3ḋd

```

Try it online!

### Explanation

```
  §            Apply to input the two functions
         d       Convert to list of digits
        ḋ        And convert to list of binary digits
   ¤e          Then apply to both values
     ṁ^3         Cube each and sum
#2             How many 2s are there in the list?

```

# Answer
> 3 votes
# Perl 5, 45 bytes

```
sub($n){$_=sprintf"=$n=%b=",$n;s/0//g;/=11=/}

```

Try it online!

# Answer
> 3 votes
# Perl 5 `-p`, 35 bytes

```
$_.=sprintf" %b",$_;$_=/\b10*10*\b/

```

Try it online!

# Answer
> 3 votes
# Fig \< 1.0.0, \\$11\log\_{256}(96)\approx\\$ 9.054 bytes

```
Gu=11Oeo0wb

```

See the README to see how to run this

I will not let Vyxal beat me. Even though I ported it. No. Never. That thing that beat me by 0.054 bytes is not Vyxal. It is an impostor. Long live Fig!!!

```
Gu=11Oeo0wb # Takes 1 input
          b # Convert to binary
         w  # Wrap it in a list with the original number
      eo0   # Remove 0s
     O      # Join by nothing
  =11       # Equal to 11?
 u          # Unpack the list into the arguments of...
G           # Max

```

# Answer
> 3 votes
# Chocolate, 8 bytes

```
ċ11€ṛ0;B

```

Try it online!

Link includes `γ` (map) for test cases.

```
ċ11€ṛ0;B
       B ## Binary representation (as a string) of the input
      ;  ## Make a list with that and the input
   €ṛ0   ## For each, remove all zeros
ċ11      ## Does this contain 11? (11 == "11")

```

# Answer
> 3 votes
# PARI/GP, 46 bytes

```
n->(d=digits(n))*d~==2||sumdigits(n,2)==2&&n>0
```

Attempt This Online!

For base 2, checks whether the sum of the digits is \\$2\\$.

For base 10, checks whether the sum of the squares of the digits is \\$2\\$.

# Answer
> 3 votes
# Pip, 12 bytes

```
11N[TBaa]DC0

```

Outputs 1 for two-bit numbers, 0 otherwise. Try It Online! Or, use as a filter to get all two-bit numbers up to 101.

### Explanation

```
   [    ]     Construct a list containing
    TBa         the input converted to binary
       a        and the input unchanged
         DC0  Delete all occurrences of the character 0 from both
11N           Count how many times 11 occurs in the resulting list

```

# Answer
> 2 votes
# Pyth, ~~22~~ 16 bytes

-6 bytes thanks to @FryAmTheEggman

```
}11,v-Q\0v-.BQ\0

```

Try it online!

# Answer
> 2 votes
# PHP, ~~69~~ 67 bytes

```
echo($f=fn($s)=>str_replace(0,'',$s)==11)($argn)|$f(decbin($argn));

```

Try it online!

Pretty straightforward: treats each input as a string, replaces all zeroes by `''` and tests if it (loosely) equals `11`, or if the binary does

EDIT: saved 2 bytes by using `0` instead of `'0'`

# Answer
> 2 votes
# C (gcc), ~~75~~ \\$\cdots\\$ ~~76~~ 80 bytes

Added 6 bytes to fix a bug.

```
d;r;c;f(n){for(c=2,r=__builtin_popcount(n)!=2|n<0;n>0;n/=10)d=n%10,c-=d*d;r*=c;}

```

Try it online!

Returns a falsy value if \\$n\\$ is a Two Bit Number™ or a truthy one otherwise.

# Answer
> 2 votes
# APL (Dyalog Extended), 19 bytes

```
2∊2 10(+.×⍨⊤)¨⊢×0<⊢

```

Try it online!

**Commented:**

```
                0<⊢  ⍝ Is the (right) argument greater than 0
              ⊢×     ⍝ Multiply this with the argument
                     ⍝   results in 0 for negative inputs
  2 10(     )¨       ⍝ Call the next function with each of the bases 2 and 10
                     ⍝   and the non-negative number as a right argument
           ⊤         ⍝ Convert number to base digits
       +.×⍨          ⍝ The sum of squares of the digits
2∊                   ⍝ Does this contain 2?

```

# Answer
> 2 votes
# Japt, ~~17 14~~  12 bytes

```
[¢Us]d_e0 ¥B

```

Try it

```
[¢Us]         - input to string base 2 , 10
     d_       - if any :
          ¥B  - are == 11 after
       e0     - removing 0

```
* Saved 3 stealing from @ovs Python answer, upvote him!

# Answer
> 2 votes
# Java 8, 67 bytes

```
n->(" "+n+" "+n.toString(n,2)+" ").replace("0","").contains(" 11 ")

```

Try it online.

**Explanation:**

```
n->                       // Method with Integer parameter and boolean return-type
  (" "                    //  Have a leading space
   +n                     //  Appended with the input
   +" "                   //  Appended with another space
   +n.toString(n,2)       //  Appended with the input as binary-String
   +" ")                  //  Appended with a trailing space
        .replace("0","")  //  Then remove all "0"s from this string
        .contains(" 11 ") //  Check if what remains contains 11 surrounded with spaces

```

# Answer
> 2 votes
# Python, 79 Bytes

```
lambda n:any(sum((ord(c)-48)**4 for c in f.format(n))==2for f in["{}","{0:b}"])

```

## Explanation

I format the int as both binary and decimal. For each character, I subtract the `'0'` character, then raise it to the power of 4. This maps `'0'` to 0, `'1'` to 1, `'2'` to 16, and other digits and the `'-'` character to numbers greater than 16. Then, I check if the summation equals 2.

# Answer
> 2 votes
# T-SQL, 93 bytes

Returns 1 for true, 0 for false

```
DECLARE @y INT=@,@x INT=9WHILE @>0SELECT
@x+=@%2,@/=2PRINT
IIF(11in(@x,replace(@y,0,'')),1,0)

```

**Try it online**

# Answer
> 2 votes
# Octave, ~~67~~ 64 bytes

```
@(x,p=@(b,z=dec2base(x*(x>0),b)-48)all(z<2)&sum(z)==2)p(2)|p(10)

```

Try it online!

If in doubt, make the code more convoluted. Somehow that tends to save bytes...

```
@(x,                               % Main anonymous function with 'x' as input
    p=                             % Second input 'p' with default value (no second input is given when calling function) which
      @(b,                         % consists of another anonymous function which takes base as input
          z=                       % From which it creates a second input 'z' with default value
            dec2base(       ,b)    % Which runs dec2base (convert from integer to string) using provided base
                     x             % On the input to the main anonymous function
                      *(x>0)       % Multiplied by (x>0) to return false for any negative integer passed in.
                               -48 % And converts from a string to an array of integers (one per digit)
      )
      all(z<2)&                    % Two-bit numbers must only contain 0 or 1, so need all elements in array of digits <2.
               sum(z)==2           % Sum all digits. Two-digit number if sum is 2 (two 1's)
)
p(2))||                            % Run two-bit number check in base 2
       p(10)                       % Run two-bit number check in base 10

```

---

First attempt,

```
@(x,p=@(z)all(z<50)&&sum(z-48)==2)x>0&&p(dec2bin(x))||p(num2str(x))

```

Try it online!

```
@(x,                               % Main anonymous function with 'x' as input
    p=                             % Second input 'p' with default value (no second input is given when calling function)
      @(z)                         % Default value consists of another anonymous function to check if string is two-bit
          all(z<50)&&              % Two-bit numbers must only contain '0' or '1', so need all elements in string <'2'(50).
                     sum(z-48)==2  % Convert all characters from '0'/'1' to 0/1 and sum. Two-digit if sum is 2 (two 1's)
)
x>0&&                              % Short-circuit to return false for any negative integer passed in.
     p(dec2bin(x))||               % Convert to binary string and check if two-digit, or...
                    p(num2str(x))  % Convert to decimal string and check if two-digit

```

# Answer
> 2 votes
# PHP, 157 bytes

```
echo$argn>0&&(2==array_reduce(str_split($argn),fn($c,$i)=>$c+=$i?($i==1?1:9):0)||2==array_reduce(str_split(decbin($argn)),fn($c,$i)=>$c+=$i?($i==1?1:9):0));

```

Try it online!

# Answer
> 2 votes
# Groovy, ~~35~~ 34 bytes

```
f={1.bitCount(it)==2|it==~'10*'*2}

```

Try it online!

Note that this treats negative numbers as 2-bit if its binary representation has exactly two 1 bits, e.g. `Integer.MIN_VALUE+1 == 10000000000000000000000000000001` would be 2-bit.

# Answer
> 2 votes
# Excel, 169 bytes

```
=LET(n,LEN(A1),e,SUBSTITUTE(A1,1,""),d,(n-LEN(e)=2)*(LEN(SUBSTITUTE(e,0,""))=0),b,CONCAT(DEC2BIN(MOD(INT(A1/512^{0,1,2}),512))),t,(LEN(b)-LEN(SUBSTITUTE(b,1,"")))=2,d+t)

```

## Excel (future release), 166 bytes

```
=LET(s,LAMBDA(x,y,SUBSTITUTE(x,y,"")),n,LEN(A1),e,s(A1,1),d,(n-LEN(e)=2)*(LEN(s(e,0))=0),b,CONCAT(DEC2BIN(MOD(INT(A1/512^{0,1,2}),512))),t,(LEN(b)-LEN(s(b,1)))=2,d+t)

```

This uses `LAMBDA` which isn't widely available yet. Not much savings.

# Answer
> 2 votes
# Fig, \\$9\log\_{256}(96)\approx\\$ 7.408 bytes

```
I11eo0wOb

```

See the README to see how to run this

Yeaa I beat Vyxal!. Also took down Chocolate as well.

```
I11eo0wOb # Full program
        b # Convert the number to binary
       O  # Join the list of binary
      w   # Wrap it in a list with the original number
   eo0    # Remove 0s
I11       # Contains 11?

```

# Answer
> 1 votes
# Arn, ~~12~~ ~~9~~ 12 bytes

```
⁼←±Î¡Oû¨¨K²$

```

Try it!

## Old answer:

```
©ou…ö6úË»˜½$

```

# Explained

Unpacked: `[+\;b--:!1#]&2`

```
  [         Begin sequence
            ENTRY ONE
    +\        Fold with sum
        _     Variable initialized to STDIN; implied
      ;b      In binary
            ENTRY TWO
    --        Subtract one from
          _   Implied
        :!    Split on every
          1
      #       Length
  ]         End sequence
&           Contains
  2         Literal two

```

# Answer
> 1 votes
# K (ngn/k), ~~9~~ 32 bytes

```
{({~#($x)^"1 0"} x)|{2=+/2\x} x}

```

Try it online!

Having to add more bytes because I read the challenge wrong. Doesn't work correctly with `0` and `1`. Return `1` for true, and `0` for false.

Explanation:

```
{({~#($x)^"1 0"} x)|{2=+/2\x} x}       Main program. x is input
                    {       }          Execute a function with argument x
                         2\x           Convert to base 2
                       +/              Sum
                     2=                Equals to 2
                   |                   Or
 ({            } x)                    Execute a function with argument x
          "1 0"                        String "1 0"
         ^                             Without (set function)
     ($x)                              Input converted to string
    #                                  Length
   ~                                   Not

```

---
Tags: code-golf, math, binary
---


title: Persistence of a number

text:
# Question
Title: Persistence of a number
The persistence of a number \\$x = d\_1d\_2d\_3...d\_n\\$, with \\$d\_1 \ne 0\\$, under some function \\$f : \mathbb N\_0 \times \mathbb N\_0 \to \mathbb N\_0\\$ is defined as the number of applications of \\$f\\$ to the digits of \\$x\\$ before it reaches a single digit integer. That is, if we have the map

$$I\_f: (x = d\_1d\_2d\_3...d\_n) \mapsto f(f(...f(d\_1, d\_2), d\_3), ...), d\_n),$$

the persistence is defined as

$$P\_f(x) = \begin{cases} 0, & x \in \\{0,1,2,3,4,5,6,7,8,9\\} \\ 1 + P\_f(I\_f(x)), & \text{otherwise} \end{cases}$$

Some examples include:

* Additive persistence: \\$P\_+(2718) = 2\\$, \\$P\_+(5) = 0\\$ and \\$P\_+(2677889) = 3\\$
* Multiplicative persistence: \\$P\_\times(68889) = 7\\$, \\$P\_\times(25) = 2\\$ and \\$P\_\times(8) = 0\\$
* Minimal/maximal digit: \\$P\_{\min}(1734) = 1\\$, \\$P\_{\max}(48203) = 1\\$ and \\$P\_{\min}(5) = 0\\$

---

Given a blackbox function \\$f : \mathbb N\_0 \times \mathbb N\_0 \to \mathbb N\_0\\$ and a positive integer \\$x = d\_1d\_2d\_3...d\_n\\$, where \\$d\_i\\$ are digits with \\$d\_1 \ne 0\\$, output the persistence of \\$x\\$ under \\$f\\$.

You may assume that \\$f\\$ will eventually reach a single digit number when repeatedly applied to \\$x\\$'s digits.

This is a challenge, so shortest code wins.

## Test cases

```
f(x, y), x -> output
x + y, 2677889 -> 3
x × y, 68889 -> 7
x ** y, 29 -> 4
φ(x × y), 736 -> 2                 (φ is the Euler Totient function)
x/2 + (x × y), 1234567 -> 5        (using floor division)
|x - y|, 9 -> 0

```

# Answer
# K (ngn/k), 14 bytes

```
{#1_(x/.'$:)\}

```

Try it online!

Uses `.'$:` instead of `10\` because the latter gives `()` for 0 (and `*/` of `()` is 1), breaking the `(*, 68889)` test case.

```
{#1_(x/.'$:)\}    Curried function, 1st arg: f, 2nd arg: n
    (      )\     repeat and collect starting from n until convergence:
       .'$:         digits
     x/             reduce by x
 #1_              length minus 1

```
> 7 votes

# Answer
# Python, ~~70~~ 71 bytes

```
p=lambda f,n:n>9and-~p(f,(i:=lambda n:f(i(n//10),n%10)if n>9else n)(n))

```

Attempt This Online!

Takes in an anonymous function `f` and an integer `n`.

---

+1 bytes from @xnor for noticing an error when `n=0` in `i`.

# Python, 65 bytes

```
p=lambda f,n:~-len(n)and-~p(f,reduce(f,n))
from functools import*

```

Attempt This Online!

Takes in an anonymous function `f` and a *string* `n` representing an integer.

# Python 2, 42 bytes

```
p=lambda f,n:~-len(n)and-~p(f,reduce(f,n))

```

Attempt This Online!

Same as above. Posted based on the recommendation of @tsh.
> 6 votes

# Answer
# Vyxal, 6 bytes

```
£‡¥RİL

```

Try it Online!

Takes inputs from the stack due to technical limits.

```
£      # Store function to register
 ‡--   # Next two elements as a function...
   R   # Reduce by (implicit digits)...
  ¥    # The function stored in the register
    İ  # Apply that function until the result doesn't change, not including the initial value
     L # Count the number of different values.

```
> 4 votes

# Answer
# PARI/GP, 38 bytes

```
g->p(n)=if(n>9,1+p(fold(g,digits(n))))

```

Attempt This Online!

A curried function that takes input as `(f)(x)`.
> 4 votes

# Answer
# Jelly, 7 bytes

```
Dç/$ƬL’

```

Try it online!

Takes a function from the previous line and a number from an argument.

```
Dç/$       Convert an integer to its decimal digits and reduce by the input function
    Ƭ      Repeat and collect the results until the results are not unique
           (repeats after reaching a single digit number)
     L’    Get its length minus 1

```
> 3 votes

# Answer
# Haskell, ~~47~~ 44 bytes

```
f#n=sum[1+f#foldl1 f[read[x]|x<-show n]|n>9]

```

Try it online!

* saved 3 Bytes thanks to @xnor

`#` is an infix function taking the function to apply as *f* and a integer number as *n*.

Uses the trick shorter conditionals when one outcome is the empty list combined with a recursive approach by @xnor idea.

If *n* \> 9 yeld 1+ result of *#* with number transformed, the result is the sum.
> 3 votes

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

```
ΔÅ»X.V}θ}N

```

Assumes the function is defined as a string in variable `X`.

Try it online or verify all test cases.

**Explanation:**

```
Δ       # Apply until the result no longer changes,
        # using the (implicit) input-integer in the first iteration:
 Å»     #  Reduce the digits of the integer by, keeping all intermediate results:
   X    #   Push function-string `X`
    .V  #   Evaluate and execute it as 05AB1E code
  }θ    #  After the reduce-by: only keep the resulting last value
}N      # After the until-no-more-changes-loop: push the last 0-based index of the loop
        # (which is output implicitly as result)

```

Unfortunately, 05AB1E lacks functions, so we'll have to store the 'black box function' in a string and execute it as 05AB1E code with `.V`.
In addition, 05AB1E's regular reduce-by builtin  only works with single builtins (e.g. `.»*`), so we'll have to use the reduce-by that keeps intermediate results and then just keep the final result, in order to have a larger body with multiple builtins (pushing `X`, and executing as 05AB1E `.V` in this case). (e.g. `Å»*}θ`).
> 3 votes

# Answer
# Japt, 11 bytes

Black-box function is pre-assigned to variable V, although functions that consist of a single basic operation can be passed via input variable V.

```
@=ìrV)¨A}fÄ

```

Try it
> 2 votes

# Answer
# Prolog (SWI), 90 bytes

```
X/Y/Z:-Y<10,Z=0;number_codes(Y,A),maplist(plus(48),[F|B],A),foldl(X,B,F,S),X/S/H,Z is H+1.

```

Try it online!

90 bytes by Steffan.
> 2 votes

# Answer
# Ruby, 47 bytes

```
->g,n{n>9?1+f[g,n.digits.reverse.reduce(&g)]:0}

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 48 bytes

Expects `(F)(n)`, where `n` is passed as a string. Returns *false* for *0*.

```
F=>g=n=>n>9&&g([...n].map(x=>+x).reduce(F)+'')+1

```

Try it online!
> 1 votes

# Answer
# Burlesque, 19 bytes

```
{XXr[}j1ia1jC~qlnfi

```

Try it online!

```
{XX    # As digits
 r[    # Reduce by F
}j1ia  # Insert F before reduce
1jC~   # Evaluate infinitely
qlnfi  # Find first single digit index

```
> 1 votes

# Answer
# BQN, 25 bytes

```
{>9?1+˜´⌽'0'-˜•Fmt;0}

```

Defines a 1-modifier that can be applied to a dyadic function F, turning it into a monadic function that takes a single number and returns its persistence under F. Try it at BQN online!

### Explanation

Here  is the original dyadic function,  is the modified function, and  is the single argument of the modified function.

```
{>9?1+˜´⌽'0'-˜•Fmt;0}
{                        }  Block (which is a 1-modifier due to the presence of  in it)
 >9                         Does the argument have multiple digits?
    ?                        If so (recursive case):
                  •Fmt       Format the argument as a string
             '0'-˜            Subtract '0' from each char, giving a list of digits
           ⌽                  Reverse
          ´                   Right fold on:
        ˜                     with reversed arguments
                             Recurse on that value
     1+                       Add one to the result of the recursive call
                       ;0    Otherwise (base case), return 0

```

Unfortunately, BQN doesn't have a left-fold modifier. Scan works left-to-right, but then it costs two bytes to extract the last value from the result list.
> 1 votes

# Answer
# tinylisp, 66 bytes

```
(load library
(d P(q((F N)(i(l N 10)0(a 1(P F(foldl F(to-base 10 N

```

Defines a function `P` that takes a function `F` and a number `N` and returns the persistence of `N` under `F`. Try it online!

### Explanation

```
(load library

```

The library contains definitions for `foldl` and `to-base`.

```
(d P(q((F N)

```

Define `P` to be a function of two arguments, `F` and `N`.

```
(i(l N 10)0

```

If `N` is less than 10, return 0. Otherwise...

```
(a 1(P F

```

Add 1 to the result of calling `P` recursively on `F` and the result of...

```
(foldl F(to-base 10 N

```

Convert `N` to its base-10 digits and left-fold on `F`.
> 1 votes

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


title: "Defuse" the bombs

text:
# Question
Title: "Defuse" the bombs
You've been hired by a bomb defusing company to perform some "controlled" demolition of un-exploded ordnance. You are given a list of bombs represented by non-negative integers.

```
[3,2,4,0,3,1,2]

```

Every step you can set up and explode a bomb. When a bomb \\$n\\$ explodes, it destroys all bombs within \\$n\\$ places replacing them with zeros

```
         v
[3,2,4,0,3,1,2]
   * * * * * *
[3,0,0,0,0,0,0]

```

Once everything is zeros you are done "defusing".

## Task

Given a starting non-empty list of bombs output the minimum steps required to clear it.

This is so the goal is to minimize the length of your source code as measured in bytes.

## Test cases

```
[0,0,0,0,0] -> 0
[0,0,1,0] -> 1
[3,2,4,1,3,1,2] -> 1
[9,9,10,9] -> 1
[1,4,1,3,1,0,5] -> 1
[1,1,1,1,1] -> 2
[1,1,1,1,1,5,1,1,1,1,4,1,0,0,1] -> 2
[1,1,1,1,1,5,1,6,1,1,4,1,0,0,1] -> 2

```

# Answer
> 6 votes
# Python 3.8, 72 bytes

*-3 bytes thanks to @loopy walt*

Returns `False` instead of `0`.

```
f=lambda a,i=0:any(a)and-~min(f(a[:i][:-x])+f(a[x+(i:=i+1):])for x in a)

```

Try it online!

The idea is to recursively split the array into left and right sections after an explosion.

# Answer
> 4 votes
# BQN, ~~29~~ 26 bytesSBCS

Quite inefficient depth-first search.

```
{(≠⌊´1+˘)⊸×˘/<|-⌜˜↕≠}

```

Run online! or click here for step-by-step results with comments.

# Answer
> 3 votes
# Julia 1.0, ~~65~~ 62 bytes

```
!l=sum(l)>(j=0)&&minimum(i->1+!l[1:(j+=1)-i]+!l[j+i:end],l.+1)

```

Try it online!

# Answer
> 3 votes
# 05AB1E, ~~31~~ 25 bytes

```
[DOß_#¼εāDδα‹øy*øyĀÏ}€`}¾

```

-6 bytes and sped up substantially by porting @ovs' BQN answer.

Input as a wrapped list. If this is not allowed, a leading `¸` can be added.

Try it online or verify all test cases.

**Explanation:**

```
[         # Loop indefinitely:
 D        #  Duplicate the current list of lists
          #  (which will be the implicitly input in the first iteration)
  Oß_     #  Check if there is an inner list of only 0s:
  O       #   Sum each inner list in the duplicate
   ß      #   Pop and push the minimum
    _     #   Check if this is equal to 0
          #  If it's truthy:
     #    #   Stop the infinite loop
  ¼       #  Increase `¾` by 1 (0 by default)
  ε       #  Map over each inner list `y`:
   āDδα   #   Create a matrix of the same length with 0 as main diagonal, and
          #   with each adjacent diagonal 1 higher than the previous:
   ā      #    Push a list in the range [1,length] (without popping `y`)
    D     #    Duplicate it
     δ    #    Apply double-vectorized:
      α   #     Absolute difference
   ‹      #   Check for all values in a row if it's smaller than the value at the
          #   same position in list `y` that's was still on the stack
    øy*ø  #   Multiply each column to the corresponding value in list `y`:
    ø     #    Zip/transpose; swapping rows/columns
     y*   #    Multiply each row by the same positioned value in list `y`
       ø  #    Zip/transpose the row/columns back
    yĀÏ   #   Remove the rows for which the corresponding value in `y` is 0:
    y     #    Push list `y` again
     Ā    #    Check for each value if it's NOT 0
      Ï   #    Only leave the rows at the truthy positions
   }€`    #  After the inner map: flatten one level down
}¾        # After the infinite loop: push the counter variable `¾`
          # (which is output implicitly as result)

```

# Answer
> 2 votes
# Python3, 84 bytes:

```
f=lambda x:any(x)and-~min(f(x[:max(i-a,0)])+f(x[i+a+1:])for i,a in enumerate(x)if a)

```

Try it online!

# Answer
> 2 votes
# Jelly, 17 bytes

```
J_r+ɗ⁸ŒPFḟ@LɗÞTḢL

```

A monadic Link accepting a list of non-negative integers that yields a non-negative integer.

**Try it online!** Or see the test-suite.

### How?

I *think* brute force is tersest for this one, but maybe not...

```
J_r+ɗ⁸ŒPFḟ@LɗÞTḢL - Link: bombs
J                 - range of length of bombs -> I = [1,2,...]
    ɗ⁸            - last three links as a dyad - f(I, bombs)
 _                -   I subtract bombs (vectorises)
   +              -   I add bombs (vectorises)
  r               -   inclusive range -> list of blast zones
                                         (includes out of bounds, but that's OK...)
      ŒP          - powerset
              T   - truthy indices of bombs -> T = indices we need to affect
             Þ    - sort the powerset by:
            ɗ     -   last three links as a dyad - f(set, T)
        F         -     flatten the set
         ḟ@       -     filter those values out of T
           L      -     length
               Ḣ  - head
                L - length

```

# Answer
> 1 votes
# Python, 94 bytes

```
f=lambda a:any(a)and-~min(f([v<abs(i-t)and x for i,x in E(a)])for t,v in E(a)if v)
E=enumerate
```

Attempt This Online!

Simple depth-first search.

---

## Whython, 87 bytes

```
f=lambda a:min(f([v<abs(i-t)and x for i,x in E(a)])for t,v in E(a)if v)+1?0
E=enumerate
```

Attempt This Online!

Base-case is `ValueError: min() arg is an empty sequence`, which indicates the array is all `0`s.

# Answer
> 1 votes
# JavaScript (Node.js), ~~89~~ ~~79~~ 67 bytes

-7 bytes from Arnauld

```
f=x=>0|Math.min(...x.map((v,i)=>v?1+f(x.map(w=>i*i-->v*v&&w)):1/0))

```

Try it online!

Using fact that `(Infinity | 0) == 0`

DFS

BFS answer deprecated

# Answer
> 1 votes
# Perl 5 `List::Util`, 109 bytes

```
sub f{my($b,$r,@i)=@_;@i[$b-min($r,$b)..$b+$r]=()if$r;!sum(@i)?0:1+min map $i[$_]?f($_,$i[$_],@i):inf,0..$#i}

```

Try it online!

# Answer
> 1 votes
# Charcoal, 44 bytes

```
⊞υＡ≔⁰ζＷ⌊Ｅυ⌈κ«≦⊕ζ≔υη≔⟦⟧υＦηＦＥκＥκ∧›↔⁻ξμλν⊞υλ»Ｉζ

```

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

```
⊞υＡ

```

Start with just the input list.

```
≔⁰ζ

```

Start with 0 explosions.

```
Ｗ⌊Ｅυ⌈κ«

```

Repeat until a fully cleared list is found.

```
≦⊕ζ

```

Increment the number of explosions.

```
≔υη≔⟦⟧υ

```

Temporarily save the list of lists.

```
ＦηＦＥκＥκ∧›↔⁻ξμλν⊞υλ

```

Make a new list of lists of the results of exploding each entry in each list (including zero entries, which have no effect on the list).

```
»Ｉζ

```

Output the number of explosions needed.

23 bytes using the newer version of Charcoal on ATO:

```
⊞υＡ≔⁰ζＷ⌊Ｅυ⌈κ«≦⊕ζ≔ΣＥυＥκＥκ∧›↔⁻πνμξυ»Ｉζ

```

Attempt This Online! Link is to verbose version of code.

# Answer
> 1 votes
# Retina, 52 bytes

```
^
!¶
\d+
*_-$%"
^/^[0,-]*$/m}+`\d*,?_(_*-),?\d*
$1
!

```

Try it online!

## Explanation

```
^
!¶

```

Prepend a new line with a single `!` to keep track of number of steps

---

```
\d+
*_-$%"

```

For each nonnegative integer, duplicate the whole line but with the number replaced by that many `_`s followed by a `-`. For example, `3,2,4,1,3,1,2` becomes

```
___-,2,4,1,3,1,2
,__-,4,1,3,1,2
3,,____-,1,3,1,2
3,2,,_-,3,1,2
3,2,4,,___-,1,2
3,2,4,1,,_-,2
3,2,4,1,3,,__-
3,2,4,1,3,1,

```

The `_`s represents a "blast wave" which destroys other bombs.

Some of the numbers next to the "defused" bomb are also deleted along the way. This does not affect the result because

* if the "defused" bomb is positive, that number would have been blown up anyway
* if the "defused" bomb is 0, then it is not the optimal move anyway as long as there are still positive bombs (which is guaranteed by the looping condition)

Also note that the original line (with the last number removed) is kept, effectively giving the option of actually defusing the last bomb (without blowing it up). But since that won't ever be better than just blowing it up, we can just leave it.

---

```
+`\d*,?_(_*-),?\d*
$1

```

Propagate the blast waves repeatedly until it no more propagation is possible

To propagate a blast wave,

1. Delete the adjacent spaces.
2. Reduce the blast wave by 1

This compresses the entire "blast zone" to one space, but it is fine because there is no need to keep track of how large a blast zone was.

A `-` is left behind in that space and it act as a barrier to prevent blast waves from later steps from propagating through an old blast zone. If a blast wave from a later step wants to cross an old blast zone, then either:

* it doesn't have enough power to cross the whole blast zone anyway, so the barrier didn't prevent the new blast wave from destroying any bombs
* it has enough power to cross the whole blast zone, which means the new blast wave covers the entire old blast zone, so "defusing" that new bomb first is a more optimal move anyway

---

```
^/^[,0-]+$/m}

```

Loop all the above until there is a line with only `,`s, `0`s, and/or `-`s (i.e. a finished state)

---

```
!

```

Count the number of `!`s marked. That is the number of steps taken to reach the finished state.

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