title: Binary to decimal converter

text:
# Question
Title: Binary to decimal converter
# Binary to decimal converter

As far as I can see, we don't have a simple binary to decimal conversion challenge.

---

Write a program or function that takes a positive binary integer and outputs its decimal value.

You are not allowed to use any builtin base conversion functions. Integer-to-decimal functions (e.g., a function that turns `101010` into `[1, 0, 1, 0, 1, 0]` or `"101010"`) are exempt from this rule and thus allowed.

Rules:

* The code must support binary numbers up to the highest numeric value your language supports (by default)
* You may choose to have leading zeros in the binary representation
* The decimal output may not have leading zeros.
* Input and output formats are optional, but there can't be any separators between digits. `(1,0,1,0,1,0,1,0)` is not a valid input format, but both `10101010` and `(["10101010"])` are.
    + You must take the input in the "normal" direction. `1110` is `14` not `7`.

Test cases:

```
1
1

10
2

101010
42

1101111111010101100101110111001110001000110100110011100000111
2016120520371234567

```

This challenge is related to a few other challenges, for instance this, this and this.

# Answer
# Jelly, 5 bytes

```
DḤ+¥/

```

Try it online!

## Explanation

### The cast

* `D` is a monad (single argument function): digits, turning `1234` into `[1, 2, 3, 4]`.
* is a monad that doubles its single argument.
* `+` is a dyad (two argument function) that adds its left and right arguments.

From there, it gets a little tricky.

### Here’s what happens at parse time

* `D`, , and `+` are read. The chain looks like `[D, Ḥ, +]`.
* The next two characters are **quicks**, which act like parse-time postfix operators on the links (functions) we've read so far.
* When `¥` is read, the last two links get popped and replaced by a link that acts like the dyad formed by composing them. So now the chain looks like `[D, dyad(Ḥ+)]`.
* When `/` is read, the last link (which ought to be a dyad) gets popped and replaced by a monad that folds using this dyad (intuitively: `f/` takes a list, replaces the commas in it with `f`, and evaluates the result.)
* The final chain looks like `[D, fold(dyad(Ḥ+))]`, two monads.

### Here's what happens at run time

* Input (a number) is implicitly read into the working value (say, `101010`).
* `D` is executed, replacing the working value with its digits (`[1,0,1,0,1,0]`).
* `fold(dyad(Ḥ+))` is executed, replacing the working value with `1∗0∗1∗0∗1∗0`, where  is the dyad `Ḥ+`.

### So what does `x∗y` evaluate to?

* In a dyadic definition, the working value is initially the **left** argument, `x`.
* , the **double** monad, doubles this value. The working value is now `2x`.
* `+`, the **plus** dyad, lacks a right argument, so this is a **hook**: a special syntactical pattern where the right argument of this dyad gets injected into `+`. This yields `2x + y` as the final working value, which is returned.

### So the whole expression evaluates to:

```
1∗0∗1∗0∗1∗0 = 2×(2×(2×(2×(2×1+0)+1)+0)+1)+0
            = 32×1 + 16×0 + 8×1 + 4×0 + 2×1 + 1×0
            = 42

```
> 63 votes

# Answer
# Python 2, ~~49~~ ~~37~~ ~~31~~ 30 Bytes

Now this will take a binary number in a decimal representation, since Python can handle arbitrarily large integers.

```
b=lambda n:n and n%2+2*b(n/10)

```

*thanks to xnor for saving a byte :)*

The easiest way to see how this works is by seeing a basic formula for converting binary to decimal:

```
= 101010
= 1*(2^5) + 0*(2^4) + 1*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)
= 1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 0*1
= 42

```

This is a 'standard' way of converting. You can expand the third line like so:

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

```

And this is essentially what the recursive method I've made is doing.

Alternate solutions I had:

```
b=lambda n:n and n%10+2*b(n/10)
b=lambda n:n%10+2*(n and b(n/10))
b=lambda n:0if n<1else n%10+2*b(n/10)
b=lambda n:0**(n/10)or n%10+2*b(n/10)
b=lambda n,o=0:o*(n<'0')or b(n[1:],2*o+int(n[0]))
lambda j:sum(int(b)*2**a for a,b in enumerate(j,1))

```
> 22 votes

# Answer
# 05AB1E, 6 bytes

Code:

```
$¦v·y+

```

For the explantion, let's take the example **101010**. We start with the number **1** (which is represented by the first digit). After that, we have two cases:

* If the digit is a **0**, multiply the number by 2.
* If the digit is a **1**, multiply the number by 2 and add 1.

So for the **101010** case, the following is calculated:

* **1**01010, start with the number **1**.
* 1**0**1010, multiply by two, resulting into **2**.
* 10**1**010, multiply by two and add one, resulting into **5**.
* 101**0**10, multiply by two, resulting into **10**.
* 1010**1**0, multiply by two and add one, resulting into **21**.
* 10101**0**, multiply by two, resulting into **42**, which is the desired result.

Code explanation:

```
$         # Push 1 and input
 ¦        # Remove the first character
  v       # For each character (starting with the first)
   ·      #   Multiply the carry number by two
    y+    #   Add the current character (converted automatically to a number)

```

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

# Answer
# Turing Machine Code, 232 bytes

(Using, as usual, the morphett.info rule table syntax)

While only 40 bytes shorter than the existing solution, that solution uses 12 states whereas this one only uses 4:

```
0 1 0 l 0
0 0 . r 0
0 . 1 l 0
0 _ I r 1
0 I 2 r 0
0 2 3 r 0
0 3 4 r 0
0 4 5 r 0
0 5 6 r 0
0 6 7 r 0
0 7 8 r 0
0 8 9 r 0
0 9 X l 0
0 X O r 0
0 O I r 0
1 _ _ l 2
1 * * * 0
2 * _ l 3
3 O 0 l 3
3 I 1 l 3
3 . _ l 3
3 _ * * halt
3 * * l 3

```

### Try it online!

The interesting computation (ie. base-conversion) actually just takes place in state 0. This state decrements the binary number one-by-one, each time incrementing a decimal counter.

Due to naming clashes of the number-bases' alphabets, I make use of `O` and `I` during the conversion. State *1,2,3* only take care of cleaning the tape, converting the symbols `O → 0` and `I → 1` and finally halting the machine.
> 11 votes

# Answer
## Haskell, ~~16~~ 111 + 57 = 168 bytes

```
import Data.String
instance IsString[Int]where fromString=map((-48+).fromEnum)
f::[Int]->Int
f=foldl1((+).(2*))

```

+57 bytes for the compile flags `-XOverloadedStrings`, `-XOverlappingInstances` and `-XFlexibleInstances`.

The challenge has some cumbersome IO format, because it heavily depends on how data types are expressed in the source code. My first version (16 bytes), namely

```
foldl1((+).(2*))

```

takes a list of integers, e.g. `[1,0,1,0,1,0]` and was declared invalid because literal Haskell lists happen to have `,` between the elements. Lists per se are not forbidden. In my new version I use the very same function, now named `f`, but I overload "Quote enclosed character sequences". The function still takes a list of integers as you can see in the type annotation `[Int] -> Int`, but lists with single digit integers can now be written like `"1234"`, e.g.

```
f "101010"

```

which evaluates to `42`. Unlucky Haskell, because the native list format doesn't fit the challenge rules. Btw, `f [1,0,1,0,1,0]` still works.
> 10 votes

# Answer
## JavaScript (ES6), ~~33~~ 31 bytes

```
s=>[...s].map(c=>r+=+c+r,r=0)|r

```

Edit: Shorter but less sweet: 2 bytes saved thanks to @ETHproductions.
> 8 votes

# Answer
# Labyrinth, 17 15 bytes

```
-+:
8 +
4_,`)/!

```

Try it online!

Labyrinth is a two-dimensional, stack-based language. In labyrinth, code execution follows the path of the code like a maze with spaces acting as walls and beginning at the top-left-most non-space character. The code flow is determined by the sign of the top of the stack. Since the stack has implicit zeroes at the bottom, the first four instructions (`-+:+`) have no effect.

## Loop starting at the `,`

* `,` Push the ascii code value of the next input character to the stop of the stack, or push -1 if EOF.
* `_48` pushes 48 to the top of the stack
* `-` Pop y, pop x, push `x-y`. The previous instructions have the effect of subtracting 48 from the input yielding 0 for "0" and 1 for "1".
* `+` Pop y, pop x, push `x+y`.
* `:` Duplicate the top of the stack
* `+` This and the previous instruction have the effect of multiplying the current value by 2

So the circular part of the code, in effect, multiples the current number by 2 and adds either a 1 or a 0 depending on if the character 1 or 0 was input.

## Tail

If the top of the stack is negative (meaning EOF was found), the code will turn left at the junction (going towards the semicolon).

* \`\`\` Negate the top of the stack to get 1
* `)` Icrement the top of the stack to get 2
* `/` Pop y, pop x, push x/y (integer division). This has the effect of undoing the last `*2` from the loop.
* `!` Output the integer representation of the top of the stack. At this point the program turns around because it hit a dead end and then exits with an error because it tries to divide by zero.

Thanks to @Martin Ender for saving me 2 bytes (and teaching me how to better think in Labyrinth).
> 8 votes

# Answer
# Retina, 15 bytes

Converts from binary to unary, then unary to decimal.

```
1
01
+`10
011
1

```

**Try it online**
> 7 votes

# Answer
# PHP, 44 bytes

```
for(;""<$c=$argv[1][$i++];)$n+=$n+$c;echo$n;

```

I could have sworn that I´ve seen that question before. But well.

Reads the number from left to right, shifts left and adds the current bit.
> 7 votes

# Answer
# Brain-Flak, ~~46~~, 28 bytes

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

```

Try it online!

*Many many bytes saved thanks to @Riley!*

Since brain-flak can't take binary input, input is a list of '0's and '1's.

Explanation:

```
#Push the height of the stack
([])

#While true:
{

 #Pop the height of the stack
 {}

 #Push this top number to (the other stack * 2)
 ({}<>({}){})

 #Toggle back on to the main stack
 <>

 #Push the new height of the stack
 ([])

#endwhile
}

#Toggle back to the other stack, implicitly display.
<>

```
> 6 votes

# Answer
# Java, ~~84~~ ~~79~~ ~~46~~ 48 bytes

* Version 3.1

Changed to `long`/**48** bytes:

```
s->{long x=0;for(char c:s)x=c-48l+x*2;return x;}

```
* Version 3.0

Did some golfing/**46** bytes:

```
s->{int x=0;for(char c:s)x=c-48+x*2;return x;}

```
* Version 2.0

Thanks to @Geobits!/**79** bytes:

```
s->{int i=Math.pow(2,s.length-1),j=0;for(char c:s){j+=c>48?i:0;i/=2;}return j;}

```
* Version 1.0

**84** bytes:

```
s->{for(int i=-1,j=0;++i<s.length;)if(s[i]>48)j+=Math.pow(2,s.length-i+1);return j;}

```
> 6 votes

# Answer
# C# 6, ~~85~~ ~~37~~ 36 bytes

```
long b(long n)=>n>0?n%2+2*b(n/10):0;

```
* Thanks to Kade for saving 41 bytes!
* Changing to C# 6 saved another 7 bytes.
> 5 votes

# Answer
# Befunge-98, 12 bytes

```
2j@.~2%\2*+

```

Try it online!

Reads one char at a time from input, converts it to 0 or 1 by taking its value modulo 2 (0 is char(48), 1 is char(49)), then uses the usual algorithm of doubling the current value and adding the new digit each time.

**Bonus:** This works with any kind of input string, I've been trying for a while now to find any funny input-\>output combination, but I wasn't able to produce anything (sadly, "answer"=46). Can you?
> 5 votes

# Answer
## Javascript (ES7) ~~41~~ ~~40~~ 36 bytes

```
f=([c,...b])=>c?c*2**b.length+f(b):0

```

takes a string as input

Shaved a byte thanks to ETHproductions

```
f=([c,...b])=>c?c*2**b.length+f(b):0
document.write([
    f('101010'),
    f('11010'),
    f('10111111110'),
    f('1011110010110'),
].join("<br>"))
```
> 4 votes

# Answer
## Perl, 25 bytes

*-3 bytes thanks to @Dom Hastings.*

24 bytes of code + 1 byte for `-p` flag.

```
$\|=$&<<$v++while s/.$//

```

To run it:

```
perl -pe '$\|=$&<<$v++while s/.$//' <<< 101010

```

**Explanations:**

```
$\|=$&<<$v++  # Note that: we use $\ to store the result
              # at first $v=0, and each time it's incremented by one
              # $& contains the current bit (matched with the regex, see bellow)
              # So this operation sets a $v-th bit of $\ to the value of the $v-th bit of the input
while         # keep doing this while...
s/.$//        #  ... there is a character at the end of the string, which we remove.
         # $\ is implicitly printed thanks to -p flag

```
> 4 votes

# Answer
# Vyxal `s`, 31 bitsv2,  ~~9~~   ~~7~~  3.875 bytes

```
fṘTE

```

Try it Online!

```
fṘTE

```

Try it Online!

* -2 thanks to Steffan
* -3 chars thanks to lyxal

**Explanation:**

```
fṘTE  # Implicit input
f     # Flatten into a list of digits
 Ṙ    # Reverse the list
  T   # Truthy indices
   E  # Two power
      # Implicit output of sum

```

Old:

```
ṘėRvƒ↲∑    # Implicit input
Ṙė         # Reverse and enumerate
  R        # Reverse each
   vƒ      # Vecorised reduce over:
     ↲     # Left bit-shift
      ∑    # Sum
           # Implicit output

```
> 4 votes

# Answer
# 05AB1E, 7 bytes

```
RvNoy*O

```

Try it online!

**Explanation**

```
R         # reverse input
 v     O  # sum of
  No      # 2^index
     *    # times
    y     # digit

```
> 3 votes

# Answer
# Bash + GNU utilities, 29 bytes

```
sed 's/./2*&+/g;s/.*/K&p/'|dc

```

I/O via stdin/stdout.

The `sed` expression splits the binary up into each digit and builds a RPN expression for `dc` to evaluate.
> 3 votes

# Answer
# C, 53

```
v(char*s){int v=0,c;while(c=*s++)v+=v+c-48;return v;}

```

Same as my javascript answer

Test Ideone
> 3 votes

# Answer
## Retina, 12 bytes

Byte count assumes ISO 8859-1 encoding.

```
+%`\B
¶$`:
1

```

Try it online!

Alternative solution:

```
+1`\B
:$`:
1

```

### Explanation

This will probably be easier to explain based on my old, less golfed, version and then showing how I shortened it. I used to convert binary to decimal like this:

```
^
,
+`,(.)
$`$1,
1

```

The only sensible way to construct a decimal number in Retina is by counting things (because Retina has a couple of features that let it print a decimal number representing an amount). So really the only possible approach is to convert the binary to unary, and then to count the number of unary digits. The last line does the counting, so the first four convert binary to unary.

How do we do that? In general, to convert from a list of bits to an integer, we initialise the result to `0` and then go through the bits from most to least significant, double the value we already have and add the current bit. E.g. if the binary number is `1011`, we'd really compute:

```
(((0 * 2 + 1) * 2 + 0) * 2 + 1) * 2 + 1 = 11
           ^        ^        ^        ^

```

Where I've marked the individual bits for clarity.

The trick to doing this in unary is a) that doubling simply means repeating the number and b) since we're counting the `1`s at the end, we don't even need to distinguish between `0`s and `1`s in the process. This will become clearer in a second.

What the program does is that it first adds a comma to the beginning as marker for how much of the input we've already processed:

```
^
,

```

Left of the marker, we'll have the value we're accumulating (which is correctly initialised to the unary representation of zero), and right of the value will be the next bit to process. Now we apply the following substitution in a loop:

```
,(.)
$`$1,

```

Just looking at `,(.)` and `$1,`, this moves the marker one bit to the right each time. But we also insert `$``, which is everything in front of the marker, i.e. the current value, which we're doubling. Here are the individual steps when processing input `1011`, where I've marked the result of inserting `$`` above each line (it's empty for the first step):

```
,1011

1,011
 _
110,11
   ___
1101101,1
       _______
110110111011011,

```

You'll see that we've retained and doubled the zero along with everything else, but since we're disregarding them at the end, it doesn't matter how often we've doubled them, as long as the number of `1`s is correct. If you count them, there are `11` of them, just what we need.

So that leaves the question of how to golf this down to 12 bytes. The most expensive part of the 18-byte version is having to use the marker. The goal is to get rid of that. We really want to double the prefix of every bit, so a first idea might be this:

```
.
$`$&

```

The problem is that these substitutions happen simultaneously, so first bit doesn't get *doubled* for each bit, but it just gets copied once each time. For input `1011` we'd get (marking the inserted `$``):

```
 _ __ ___
1101011011

```

We do still need to process the input recursively so that the doubled first prefix is doubled again by the second and so on. One idea is to insert markers everywhere and repeatedly replace them with the prefix:

```
\B
,
+%`,
¶$`

```

After replacing each marker with the prefix for the first time, we need to remember where the beginning of the input was, so we insert linefeeds as well and use the `%` option to make sure that the next `$`` only picks up things up the closest linefeed.

This does work, but it's still too long (16 bytes when counting `1`s at the end). How about we turn things around? The places where we want to insert markers are identified by `\B` (a position between two digits). Why don't we simply insert prefixes into those positions? This almost works, but the difference is that in the previous solution, we actually removed one marker in each substitution, and that's important to make the process terminate. However, the `\B` aren't character but just positions, so nothing gets removed. We *can* however stop the `\B` from matching by instead inserting a non-digit character into this place. That turns the non-word boundary into a word boundary, which is the equivalent of removing the marker character earlier. And that's what the 12-byte solution does:

```
+%`\B
¶$`:

```

Just for completeness, here are the individual steps of processing `1011`, with an empty line after each step:

```
1
1:0
10:1
101:1

1
1:0
1
1:0:1
1
1:0
10:1:1

1
1:0
1
1:0:1
1
1:0
1
1:0:1:1

```

Again, you'll find that the last result contains exactly 11 `1`s.

As an exercise for the reader, can you see how this generalises quite easily to other bases (for a few additional bytes per increment in the base)?
> 3 votes

# Answer
# Pushy, 10 bytes

Takes input as a list of 0/1 on the command line: `$ pushy binary.pshy 1,0,1,0,1,0`.

```
L:vK2*;OS#

```

The algorithm really shows the beauty of having a second stack:

```
            \ Implicit: Input on stack
L:    ;     \ len(input) times do:
  v         \   Push last number to auxiliary stack
   K2*      \   Double all items
       OS#  \ Output sum of auxiliary stack

```

This method works because the stack will be doubled `stack length - n` times before reaching number `n`, which is then dumped into the second stack for later. Here's what the process looks like for input `101010`:

```
1: [1,0,1,0,1,0]
2: []

1: [2,0,2,0,2]
2: [0]

1: [4,0,4,0]
2: [2]

1: [8,0,8]
2: [2,0]

1: [16,0]
2: [2,0,8]

1: [32]
2: [2,0,8,0]

1: []
2: [2,0,8,0,32]

2 + 8 + 32 -> 42

```
> 3 votes

# Answer
# Mathematica, ~~27~~ ~~13~~ 11 bytes

```
Fold[#+##&]

```

Accepts a `List` of bits as input (e.g. `{1, 0, 1, 1, 0}` -- *Mathematica*'s binary representation of the number `22`)
> 3 votes

# Answer
## R (32-bit), 64 Bytes

Input for the function should be given as character. The base functions of R support 32-bit integers.

Input:

```
# 32-bit version (base)
f=function(x)sum(as.double(el(strsplit(x,"")))*2^(nchar(x):1-1))
f("1")
f("10")
f("101010")
f("1101111111010101100101110111001110001000110100110011100000111")

```

Output:

```
> f("1")
[1] 1
> f("10")
[1] 2
> f("101010")
[1] 42
> f("1101111111010101100101110111001110001000110100110011100000111")
[1] 2.016121e+18

```

## R (64-bit), 74 Bytes

Input for the function should be given as character. The package `bit64` has to be used for 64-bit integers.

Input:

```
# 64-bit version (bit64)
g=function(x)sum(bit64::as.integer64(el(strsplit(x,"")))*2^(nchar(x):1-1))
g("1")
g("10")
g("101010")
g("1101111111010101100101110111001110001000110100110011100000111")

```

Output:

```
> g("1")
integer64
[1] 1
> g("10")
integer64
[1] 2
> g("101010")
integer64
[1] 42
> g("1101111111010101100101110111001110001000110100110011100000111")
integer64
[1] 2016120520371234567

```
> 3 votes

# Answer
# Matlab, 30 Bytes

```
@(x)sum(2.^find(flip(x)-48)/2)

```

The last test case has rounding errors (because of `double`), so if you need full precision:

```
@(x)sum(2.^uint64(find(flip(x)-48))/2,'native')

```

with 47 Bytes.
> 3 votes

# Answer
# Elm, ~~60~~ 41 bytes

```
String.foldl(\b a->2*a+Char.toCode b-48)0

```

-19 bytes thanks to Wheat Wizard and alephalpha

You can try it here. Here's a full test snippet:

```
import Html exposing (text)

f : String -> Int
f=String.foldl(\b a->2*a+Char.toCode b-48)0

main = text (String.fromInt (f "101010"))

```
> 3 votes

# Answer
## PowerShell v2+, 55 bytes

```
param($n)$j=1;$n[$n.length..0]|%{$i+=+"$_"*$j;$j*=2};$i

```

~~Feels too long ...~~ Can't seem to golf it down any -- tips appreciated.

### Explanation

```
param($n)$j=1;$n[$n.length..0]|%{$i+=+"$_"*$j;$j*=2};$i
param($n)$j=1;                                          # Take input $n as string, set $j=1
              $n[$n.length..0]                          # Reverses, also converts to char-array
                              |%{                  };   # Loop over that array
                                 $i+=+"$_"*$j;          # Increment by current value of $j times current digit
                                              $j*=2     # Increase $j for next loop iteration
                                                     $i # Leave $i on pipeline
                                                        # Implicit output

```
> 2 votes

# Answer
## T-SQL, 202 Bytes

```
DECLARE @b varchar(max)='1',@ int=1 declare @l int=LEN(@b)declare @o bigint=CAST(SUBSTRING(@b,@l,1)AS bigint)WHILE @<@l BEGIN SET @o=@o+POWER(CAST(SUBSTRING(@b,@l-@,1)*2AS bigint),@)SET @=@+1 END PRINT @o

```
> 2 votes

# Answer
# PHP, 64 bytes

```
foreach(str_split(strrev($argv[1]))as$k=>$v)$t+=$v*2**$k;echo$t;

```

We reverse our binary number, split it into its component digits, and sum them based on position.
> 2 votes

# Answer
# Clojure, ~~114~~ ~~105~~ ~~63~~ 41 bytes

## V4: 41 bytes

-22 bytes thanks to @cliffroot. Since `digit` is a character, it can be converted to it's code via `int`, then have 48 subtracted from it to get the actual number. The map was also factored out. I don't know why it seemed necessary.

```
#(reduce(fn[a d](+(* a 2)(-(int d)48)))%)

```

## V3: 63 bytes

```
(fn[s](reduce #(+(* %1 2)%2)(map #(Integer/parseInt(str %))s)))

```

-42 bytes (!) by peeking at other answers. My "zipping" was evidently very naïve. Instead of raising 2 to the current place's power, then multiplying it by the current digit and adding the result to the accumulator, it just multiplies the accumulator by 2, adds on the current digit, then adds it to the accumulator. Also converted the reducing function to a macro to shave off a bit.

Thanks to @nimi, and @Adnan!

Ungolfed:

```
(defn to-dec [binary-str]
  (reduce (fn [acc digit]
            (+ (* acc 2) digit))
          (map #(Integer/parseInt (str %)) binary-str)))

```

## V2: 105 bytes

```
#(reduce(fn[a[p d]](+ a(*(Integer/parseInt(str d))(long(Math/pow 2 p)))))0(map vector(range)(reverse %)))

```

-9 bytes by reversing the string so I don't need to create an awkward descending range.

## V1: 114 bytes

Well, I'm certainly not winning! In my defense, this is the first program I've ever written that converts between bases, so I had to learn how to do it. It also doesn't help that `Math/pow` returns a double that requires converting from, and `Integer/parseInt` doesn't accept a character, so the digit needs to be wrapped prior to passing.

```
#(reduce(fn[a[p d]](+ a(*(Integer/parseInt(str d))(long(Math/pow 2 p)))))0(map vector(range(dec(count %))-1 -1)%))

```

Zips the string with a descending index representing the place number. Reduces over the resulting list.

Ungolfed:

```
(defn to-dec [binary-str]
  (reduce (fn [acc [place digit]]
            (let [parsed-digit (Integer/parseInt (str digit))
                  place-value (long (Math/pow 2 place))]
              (+ acc (* parsed-digit place-value))))
          0
          (map vector (range (dec (count binary-str)) -1 -1) binary-str)))

```
> 2 votes

# Answer
# MATL, 7 bytes

```
PoofqWs

```

Try it online!

```
P   % Implicitly input string. Reverse
o   % Convert to array of ASCII codes
o   % Modulo 2: '1' becomes 1, '0' becomes 0
f   % Find: push array of 1-based indices of nonzeros
q   % Subtract 1 from each entry
W   % 2 raised to each entry
s   % Sum of array. Implicitly display

```
> 2 votes

# Answer
# JavaScript (ES6), 32 bytes

```
f=([...n])=>n+n&&+n.pop()+2*f(n)

```

Recursion saves the day again! Though the parameterization seems a little long...
> 2 votes

# Answer
# Perl, ~~21~~ ~~19~~ 16 + 4 = 20 bytes

-4 bytes thanks to @Dada

Run with `-F -p` (including the extra space after the `F`). Pipe values to the function using `echo -n`

```
$\+=$_+$\for@F}{

```

Run as `echo -n "101010" | perl -F -pE '$\+=$_+$\for@F}{'`

I feel this is sufficiently different from @Dada's answer that it merits its own entry.

Explanation:

```
-F                              #Splits the input character by character into the @F array
-p                              #Wraps the entire program in while(<>){ ... print} turning it into
while(<>){$\+=$_+$\for@F}{print}
                   for@F        #Loops through the @F array in order ($_ as alias), and...
          $\+=$_+$\             #...doubles $\, and then adds $_ to it (0 or 1)...
while(<>){              }       #...as long as there is input.
                         {print}#Prints the contents of $_ (empty outside of its scope), followed by the output record separator $\

```

This uses my personal algorithm of choice for binary-to-decimal conversion. Given a binary number, start your accumulator at 0, and go through its bits one by one. Double the accumulator each bit, then add the bit itself to your accumulator, and you end up with the decimal value. It works because each bit ends up being doubled the appropriate number of times for its position based on how many more bits are left in the original binary number.
> 2 votes

# Answer
# Dyalog APL, 12 bytes

```
(++⊢)/⌽⍎¨⍞

```

get string input

`⍎¨` convert each character to number

reverse

`(`...`)/` insert the following function between the numbers

`++⊢` the sum of the arguments plus the right argument

---

ngn shaved 2 bytes.
> 2 votes

# Answer
# Haskell, 31 bytes

```
f=foldl(\a b->2*a+(read$b:[]))0

```

Takes input in string format (e.g. `"1111"`). Produces output in integer format (e.g. `15`).

`:[]` Converts from an element to an array -- in this chase from `Char` to `[Char]` (`String`). `read` Converts from string to whatever context it's in (in this case the context is addition, so converts to `Num`)

so `(read$b:[])` converts `b` from `Char` to `Num`. `a` is the accumulator, so multiply that by two and add the `Num` version of `b`.

If input in the format `[1,1,1,1]` was allowed, the 18 byte

```
f=foldl((+).(2*))0

```

would work, but since it's not, it doesn't.
> 2 votes

# Answer
# x86-16 machine code, 10 bytes

**Binary:**

```
00000000: 31d2 acd0 e811 d2e2 f9c3                 1.........

```

**Listing:**

```
31 D2       XOR  DX, DX         ; clear output value
        CHRLOOP:
AC          LODSB               ; load next char into AL
D0 E8       SHR  AL, 1          ; CF = LSb of ASCII char
11 D2       ADC  DX, DX         ; shift CF left into result
E2 F9       LOOP CHRLOOP        ; loop until end of string
C3          RET                 ; return to caller

```

Callable function, input string in `[SI]` length in `CX`. Result in `DX`.

**Example test program I/O:**
> 2 votes

# Answer
# , 25 bytes (65 characters)

```
07717134200446170134271600446170001755630036117700136161177546635

```

Try it online!

## Explanation

```
0**77**                             Initialize counter to 0 (an empty section)
   17134200..77546635           Push the main loop onto the frame

```

Once the original code has finished executing, the frame is

```
||**6**||**7**13420044**7**013427160044**7**000175563003**77**7001361**77**7546**35**
```

The last section of this is the main loop, which will run repeatedly until it gets deleted. All of it except the last two commands is data and section separators, which push commands onto the frame to leave it as:

```
||**6**|| (main loop) |**73426644**|**67342**1**6644**|**6667**55**3663**||0013**7**||54

```

**`3`** outputs the last section (`54`) and discards the last two bars. On the first iteration, `5` is interpreted as a switch to output format 5 ("US-TTY"), which converts each pair of commands to a character. The `4` following it does not form a group, so it is ignored. On future iterations, we are already in output format 5, so `54` is interpreted as a group meaning "input character". To do this, the character from STDIN is converted into its character code (or, on EOF, `-1`), and 1 is added. Then, the last section (which is now the `00137`) is repeated that many times. In summary:

* If the character is `0`, `00137` is repeated 49 times.
* If the character is `1`, `00137` is repeated 50 times.
* If there are no more characters, `00137` is repeated 0 times (i.e. deleted).
* If this was the first iteration, `00137` is left alone (i.e. repeated 1 time).

**`5`** removes the last section (`00137` repeated some number of times) from the frame and executes it, resulting in this many sections containing **`6673`**.

The main loop has now finished executing, so the last section (which is **`6673`** unless we reached EOF) runs. **`66`** concatenates the last three sections into one (and has some other effects that don't affect the number of sections), which **`73`** deletes. Thus, the last three sections are deleted, and this repeats until the last section is no longer **`6673`**.

* If we reached EOF, nothing happens.
* If this is the first iteration or the character was `0`, after removing the last three sections 0 or 16 times, there is just one copy left on the frame. This copy deletes itself and the two sections before it, leaving everything up to the main loop and the section after it.
* If the character was `1`, after removing the last three sections 17 times, all 50 copies and the third section after the main loop (the EOF handler) have been deleted.

Now, the last section left on the frame runs. This could, depending on the inputted character, be any of the three sections after the main loop.

If this is the first iteration or the character was `0`, the section just after the main loop, **`73426644`**, runs. **`73`** deletes this section, and **`4`** swaps the main loop with the counter behind it. This counter keeps track of the number we want to output, stored as the number of `7`s and `1`s minus the number of `6`s and `0`s. This metric has the property that it is not changed by pacification (which changes some `6`s into `0`s, some `7`s into `1`s, and sometimes inserts `7...6` around code). **`2`** duplicates the counter and **`6`** concatenates the two copies (after pacifying the second, which, as we saw, does not change the value it represents), so the value is doubled. If this was the first iteration, the counter was previously empty, and doubling it still results in an empty section. Then, **`6`** gets rid of the empty section inserted by **`4`** (and pacifies the counter again, leaving the value unchanged), and **`44`** swaps the counter back to its original position. This leaves two empty sections on the end of the frame, which are removed automatically, and the main loop runs again.

If the character was `1`, the second section after the main loop (`**67342**1**6644**`) runs. This is just like the section before it (explained in the last paragraph), except for two extra commands: a **`6`** at the start, which joins the section with the previous one before **`73`** deletes it, and a `1` in the middle, which adds a `7` to the counter (increasing its value by 1) after it gets doubled.

If we reached EOF, the third section after the main loop (`**6667**55**3663**`) runs. **`666`** joins the last four sections (everything after the counter) into one section, to be deleted by **`3`**. `**7**55**3**` exits output format 5 by outputting `55` and deletes the section before it, leaving only `||**6**| (counter)` on the frame. **`66`** pacifies the two sections and combines them, turning the **`6`** back into a `0` (and not changing the value of the counter). Finally, the last **`3`** outputs everything. The `0` at the start enters output format 0 ("Numerical output"), and the rest of the section (i.e. the counter) is converted to a number by taking the number of `7`s and `1`s minus the number of `6`s and `0`s. This value, which is the input converted from binary, is output in decimal and the program terminates.
> 2 votes

# Answer
# Excel, ~~74 70~~ 55

Trailing parens already discounted. Tested in Excel Online.

## Formulae:

* `A1`: Input
* `B1`: `=LEN(A1)` (7)

### Main Code (48):

A pretty simple "add all the powers of 2" formula:

```
=SUM(MID(A1,1+B1-SEQUENCE(B1),1)/2*2^SEQUENCE(B1))

```

Verify with:

```
=DECIMAL(A1,2)

```
> 2 votes

# Answer
# , ~~48~~ 37 bytes

*-11 bytes thanks to Dominic van Essen*

```
sum(utf8ToInt(scan(,""))%%2*2^(31:0))

```

Takes input as a string, left-padded with 0s to 32 bits. Try it online!

I copied some good ideas from djhurio's much earlier R answer, so go give that an upvote too. As with the first solution there, this solution won't work for the last test case because it's too large to fit into R's default size of integer.

### Explanation

To get a vector of the bits as integers 0 and 1, we use `uft8ToInt` to convert to a vector of character codes. This gives us a list of 48s and 49s, which we take mod 2 to get 0s and 1s.

Then, to get the appropriate powers of 2 in descending order, we construct a range from 31 down to 0. Then we convert each of those numbers to the corresponding power of two (`2^`).

Finally, we multiply the two vectors together and return their `sum`.
> 2 votes

# Answer
# K (ngn/k), ~~11~~ 10 bytes

```
(+/2 1*,)/

```

Try it online!
> 2 votes

# Answer
## C, 48 bytes

```
i;f(char *s){for(i=0;*++s;i+=i+*s-48);return i;}

```

Heavily inspired by @edc45 's answer but I made some significant changes. I made 'i' a global variable to save having to typecast. I also used a for loop to save a few bytes. It does now require a single leading 0 in the binary representation.

**More readable version**

```
f(char *s){
  int i = 0; // Total decimal counter
  for(;;*++s;i+=i+*s-48); // Shift left and add 0 or 1 depending on charecter
  return i;
}

```
> 2 votes

# Answer
# k, 8 bytes

Same method as the Haskell answer above.

```
{y+2*x}/

```

Example:

```
{y+2*x}/1101111111010101100101110111001110001000110100110011100000111b
2016120520371234567

```
> 1 votes

# Answer
# Java 7, 87 bytes

```
long c(String b){int a=b.length()-1;return a<0?0:b.charAt(a)-48+2*c(b.substring(0,a));}

```

For some reason I always go straight to recursion. Looks like an iterative solution works a bit nicer in this case...
> 1 votes

# Answer
# JavaScript (ES7), ~~56~~ 47 bytes

Reverses a binary string, then adds each digit's value to the sum.

```
n=>[...n].reverse().reduce((s,d,i)=>s+d*2**i,0)

```

**Demo**

```
f=n=>[...n].reverse().reduce((s,d,i)=>s+d*2**i,0)
document.write( f('101010') ) // 42
```
> 1 votes

# Answer
# MATL, ~~8~~, 7 bytes

```
"@oovsE

```

Try it online!

One byte saved thanks to @LuisMendo!

Alternate approach: (9 bytes)

```
ootn:PW*s

```
> 1 votes

# Answer
## JavaScript, ~~18~~ 83 bytes

~~`f=n=>parseInt(n,2)`~~

`f=n=>n.split('').reverse().reduce(function(x,y,i){return(+y)?x+Math.pow(2,i):x;},0)`

**Demo**

```
f=n=>n.split('').reverse().reduce(function(x,y,i){return(+y)?x+Math.pow(2,i):x;},0)
document.write(f('1011')) // 11
```
> 1 votes

# Answer
# JavaScript (ES6), 38

Simple is better

```
s=>eval("for(i=v=0;c=s[i++];)v+=+c+v")

```

**Test**

```
f=s=>eval("for(i=v=0;c=s[i++];)v+=+c+v")

console.log("Test 0 to 99999")
for(e=n=0;n<100000;n++)
{
  b=n.toString(2)
  r=f(b)
  if(r!=n)console.log(++e,n,b,r)
}
console.log(e+" errors")

```
> 1 votes

# Answer
# Turing Machine Code, 272 bytes

(Using, as usual, the morphett.info rule table syntax)

```
0 * * l B
B * * l C
C * 0 r D
D * * r E
E * * r A
A _ * l 1
A * * r *
1 0 1 l 1
1 1 0 l 2
1 _ * r Y
Y * * * X
X * _ r X
X _ _ * halt
2 * * l 2
2 _ _ l 3
3 * 1 r 4
3 1 2 r 4
3 2 3 r 4
3 3 4 r 4
3 4 5 r 4
3 5 6 r 4
3 6 7 r 4
3 7 8 r 4
3 8 9 r 4
3 9 0 l 3
4 * * r 4
4 _ _ r A

```

AKA "Yet another trivial modification of my earlier base converter programs."

Try it online, or you can also use test it using this java implementation.
> 1 votes

# Answer
# Befunge, ~~20~~ 18 bytes

Input must be terminated with EOF rather than EOL (this lets us save a couple of bytes)

```
>+~:0`v
^*2\%2_$.@

```

Try it online!

**Explanation**

```
>             The stack is initially empty, the equivalent of all zeros.
 +            So the first pass add just leaves zero as the current total.
  ~           Read a character from stdin to the top of the stack.
   :0`        Test if greater than 0 (i.e. not EOF)
      _       If true (i.e > 0) go left.
    %2        Modulo 2 is a shortcut for converting the character to a numeric value.
   \          Swap to bring the current total to the top of the stack.
 *2           Multiply the total by 2.
^             Return to the beginning of the loop,
 +            This time around add the new digit to the total.

                ...on EOF we go right...
       $      Drop the EOF character from the stack.
        .     Output the calculated total.
         @    Exit.

```
> 1 votes

# Answer
# Ruby, 37 bytes

```
ruby -e 'o=0;gets.each_byte{|i|o+=o+i%2};p o/2'
         1234567890123456789012345678901234567

```

This depends on the terminating `\n` (ASCII decimal 10) being zero modulo 2 (and on ASCII 0 and 1 being 0 and 1 mod two, respectively, which thankfully they are).
> 1 votes

# Answer
# 아희(Aheui), 40 bytes

```
아빟뱐썩러숙
뎌반뗘희멍파퍄

```

Accepts a string composed of 1s and 0s.

**To try online**

Since the online Aheui interpreter does not allow arbitrary-length strings as inputs, this alternative code must be used (identical code with slight modifications):

Add the character  at the end of the first line (after ) length(n)-times.

```
어우
우어
뱐썩러숙
번댜펴퍼망희땨

```

If the input is `10110`, the first line would be `어우벟벟벟벟벟`.

When prompted for an input, do NOT type quotation marks. (i.e. type `10110`, not `"10110"`)

Try it here! (copy and paste the code)
> 1 votes

# Answer
# ClojureScript, 36 bytes

```
(fn[x](reduce #(+(* 2 %)(int %2))x))

```

or

```
#(reduce(fn[a n](+(* 2 a)(int n)))%)

```

The straightforward reduction. Takes a string as input.
> 1 votes

# Answer
# Minkolang v0.15, ~~23~~ 19 bytes

```
n6ZrI[2%2i;*1R]$+N.

```

Try it online!

### Explanation

```
n                             gets input in the form of a number
 6Z                           converts to string (so that it is split into an array)
   r                          reverses it
    I                         gets the stack length
     [        ]               for loop with the stack's length as the number of iterations
      2%                       gets the modulo of the ascii value
                               1 =(string conversion)> 49 =(after modulo)> 1
                               0 =(string conversion)> 48 =(after modulo)> 0
        2i;                    raises 2 to the power of the loop counter
           *                   multiplies it by the modulo
            1R                 rotates stack 1 time
              $+              sums everything
                N.            outputs as number and exit

```
> 1 votes

# Answer
# Common Lisp, ~~99~~ ~~88~~ 72 bytes

Takes a string as input

```
(defun f(s)(reduce(lambda(a d)(+ d(* a 2)))(map'list #'digit-char-p s)))

```

Ungolfed:

```
(defun bin-to-dec (bin-str)
  (reduce (lambda (acc digit) (+ digit (* acc 2)))
          (map 'list #'digit-char-p bin-str)))

```
> 1 votes

# Answer
# \>\<\> (Fish) ~~36~~ 28 bytes

```
/i:1+?!v$2*$2%+!| !
/0| ;n~<

```

Edit 1: Forgot to put the output in the original. Added output and used MOD 2 instead of minus 48 to convert ascii to decimal to save the extra bytes lost. (no change in bytes)

Edit 2: Changed the algorithm completely. Each loop now does this; times current value by 2, then add the mod of the input. (saving of 8 bytes)

Online version

Try it Online! \- This works with bigger numbers than the above link.
> 1 votes

# Answer
# **C, 44 bytes**

```
d(s,v)char*s;{return*s?d(s,v+=v+*s++-48):v;}

```

Use as follows :

```
int main(){
  printf("%i\n", d("101010",0));
}

```

Remove two bytes and an unused parameter thanks to Steadybox
> 1 votes

# Answer
# C, ~~41~~ 37 bytes

```
i;b(char*s){i+=i+*s++%2;i=*s?b(s):i;}

```

Wandbox
> 1 votes

# Answer
# **MATLAB, 49 bytes**

```
@(a)dot(int2str(a)-'0',2.^(floor(log10(a)):-1:0))

```

Anonymous function that splits the input into an array with `int2str(a)-'0'`, then does a dot product with powers of 2. Has rounding error for the last test case, will update the solution when I figure out a fix.
> 1 votes

# Answer
# Forth (gforth 0.7.3), 47 bytes

```
: x 2 base ! bl parse s>number drop decimal . ;

```

`: x` \- define new word with name 'x'
`2 base !` \- set base to binary
`bl parse` \- read line until a space (bl) or EOL
`s>number` \- try to convert the string to number
`drop` \- we only want the converted number and not the success flag
`decimal` \- set base to decimal
`.` \- print value on top of stack
`;` \- end of definition

Test cases:

```
x 1 1  ok
x 10 2  ok
x 101010 42  ok
x 1101111111010101100101110111001110001000110100110011100000111 2016120520371234567  ok

```
> 1 votes

# Answer
# SmileBASIC, ~~47~~ 44 bytes

```
INPUT B$WHILE""<B$N=N*2+VAL(SHIFT(B$))WEND?N

```

Another program of the same size:

```
INPUT B$WHILE""<B$N=N*2OR"0"<SHIFT(B$)WEND?N

```
> 1 votes

# Answer
# APL(NARS), 26 chars, 52 bytes

```
{+/a×⌽1,2x*⍳¯1+≢a←1-⍨⎕D⍳⍵}

```

test:

```
  f←{+/a×⌽1,2x*⍳¯1+≢a←1-⍨⎕D⍳⍵}
  ⎕fmt f"0"
0
~
  f"1"
1
  ⎕fmt f"101010"
42
~~
  f"10"
2
  (≢,f)"11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
152 4995366924470859583704000893073232977339613183

```

152 bits... It should be limited from memory for store string and numbers.
> 1 votes

# Answer
# Pip, ~~17~~ 14 bytes

```
$+(**_*BMERVa)

```

Doesn't work on TIO because unary \** is only in the latest Pip version.

Try it online!
> 1 votes

# Answer
# Perl 5, 18 + 1 (`-p`) = 19 bytes

Combines techniques from the other Perl entries. Scored using the rules at the time of posting.

```
s/./$\+=$\+$&/ge}{

```

Try it online!
> 1 votes

# Answer
# JavaScript (V8), ~~28~~ 26 bytes

-2 bytes thank to l4m2!

```
f=n=>n%2|(n<2?0:2*f(n/10))

```

Try it online!

Takes input as a Number, outputs a Number.
> 1 votes

# Answer
# ARM Thumb-2 machine code, 16 bytes

```
2100 f810 2b01 b112 0852 4149 e7f9 4770

```

Commented assembly:

```
        .syntax unified
        .arch armv6t2
        .thumb
        .globl bin2int
        .thumb_func
        // Input: null terminated string in r0
        // Output: integer in r1
bin2int:
        // Set initial result to zero
        movs    r1, #0
.Lloop:
        // Load char from r0 into r2, increment
        ldrb    r2, [r0], #1
        // Was it '\0'? If so, bail.
        cbz     r2, .Lend
        // Shift the lowest bit into the carry flag
        // ASCII '0' has the lowest bit clear, ASCII '1'
        // does not.
        lsrs    r2, r2, #1
        // Multiply the result by 2 (by adding to itself),
        // and add the carry flag to that result
        adcs    r1, r1
        // Jump back to .Lloop (our loop condition is cbz)
        b       .Lloop
.Lend:
        // Return
        bx      lr

```

The input is a null terminated string in `r0` and the output is in `r1`.

I came up with the same idea as 640KB (`SHR/ADC`, or in my case, `lsrs/adcs`) without even seeing their solution.

Great minds think alike, I guess.
> 1 votes

# Answer
# Husk, 5 bytes

```
Fo+Dd

```

Try it online!

```
F        # Fold from left
         # (apply binary function to each element,
         # together with the value of the previous result)
    d    # over all the digits of the input,
         # with this function:
 o       # o = combination of 2 functions
  +      # add second argument (each new digit, from left) to
   D     # double the first argument (previous result)

```
> 1 votes

# Answer
# FunStack alpha, 31 bytes

```
Plus Double compose foldl1 Odd?

```

Takes a string consisting of `0`s and `1`s, outputs an integer. Try it at Replit: pass the input string as a command-line argument (formatted like `\"1101\"`) and enter the program on stdin.

### Explanation

Same idea as Steffan's Elm answer, Dominic van Essen's Husk answer, etc.

```
Plus Double compose

```

Push the functions `Plus` (dyadic, adds its arguments) and `Double` (monadic, doubles its argument. Compose them, resulting in a dyadic function that doubles its first argument and adds the result to its second argument.

```
foldl1

```

Perform a left fold over a list using that function, with the first element of the list serving as the initial accumulator value. This errors if the list is empty, but we don't have to worry about that since the input represents a positive integer.

```
Odd?

```

The list that we want to fold over is the program argument (a string, aka list of characters) with the character `'0'` turned into the number `0` and similarly for `'1'` and `1`. The obvious way to do this is `Minus '0'`, but since we only have to deal with `0` and `1`, we can use `Odd?` instead. This function returns `1` if its argument is odd and `0` if it is even; when applied to characters, it considers whether the charcode is odd or even.

---

Another 31-byte answer is possible using a different approach:

```
Sum Times Pow 2 #N Reverse Odd?

```

This generates an infinite list of powers of 2, multiplies it by the input digits reversed, and sums the result.
> 1 votes

# Answer
# Go, 70 bytes

```
func(s string)(o uint64){for _,r:=range s{o=2*o+uint64(r-'0')}
return}

```

Attempt This Online!

Takes in a string of binary digits (`01`). For each digit, convert it to it's corresponding number, and add it to twice the total.
> 1 votes

# Answer
# Arturo, 31 bytes

```
f:$[n][(n>0)?[+2*f n/10n%2]->0]

```

Try it
> 1 votes

# Answer
# Excel, ~~51~~ 48 bytes

```
=NPV(-0.5,MID(n,SORT(SEQUENCE(LEN(n)),,-1),1)/2)

```

*Input **n***
> 1 votes

# Answer
# Desmos, 51 bytes

```
f(n)=∑_{i=0}^{log(n+0^n)}2^imod(floor(n/10^i),10)

```

Try It On Desmos!

Try It On Desmos! - Prettified

Without the ban on binary list input, this could be **33 bytes**:

```
f(l)=total(2^{[l.length-1...0]}l)

```

Try It On Desmos!

Try It On Desmos! - Prettified
> 1 votes

# Answer
# Thunno 2 `S`, 4 bytes

```
drVO

```

Attempt This Online!

#### Explanation

```
drVO  # Implicit input  -> 101010
d     # Cast to digits  -> [1, 0, 1, 0, 1, 0]
 r    # Reverse         -> [0, 1, 0, 1, 0, 1]
  V   # Truthy indices  -> [1, 3, 5]
   O  # Two power       -> [2, 8, 32]
      # S flag sums     -> 42
      # Implicit output

```

Old:

```
dŻrO×  # Implicit input  -> 101010
d      # Cast to digits  -> [1, 0, 1, 0, 1, 0]
 Ż     # Length range    -> [1, 0, 1, 0, 1, 0]  [0, 1, 2, 3, 4, 5]
  r    # Reverse         -> [1, 0, 1, 0, 1, 0]  [5, 4, 3, 2, 1, 0]
   O   # Two power       -> [1, 0, 1, 0, 1, 0]  [32, 16, 8, 4, 2, 1]
    ×  # Multiply        -> [32, 0, 8, 0, 2, 0]
       # S flag sums     -> 42
       # Implicit output

```
> 1 votes

# Answer
# Commodore C64 BASIC, 84 BASIC Bytes

```
0inputa$:b=len(a$):ifb=.thenend
1t=.:c=t:forx=bto1step-1:c=c+1:t=t+val(mid$(a$,c,1))*2^(x-1):next:?t

```

## How it works

Firstly, the `inputa$` is expecting the user to enter a string, though the only sanity check is that there is something is entered. We then initialise three variables, `b` to the string length, `t` to zero (in the Commodore BASIC interpreter, parsing `.` is slightly quicker than parsing `0`), and `c` also to zero. As we enter the loop, we read each position from right to left.

For each position, the value in `c` is incremented by 1, and `t` adds the value of each position multiplied by 2 the power of the current bit position minus 1, and it continues until each position is calculated. The result is then printed.
> 1 votes

# Answer
## Pyke, ~~10~~ 9 bytes

```
1QY_%0m@s

```

Try it here!

```
 QY_      -    reverse digits input
1   %     -   get indecies with a value of 1
     0m@  -  map(set_nth_bit(0, i), ^)
        s - sum(^)

```

Also 9 bytes

```
Y_'XltV}+

```

Try it here!

```
Y_        - reverse digits
  'Xlt    - splat(^), len(^)-1
      V   - repeat length times:
       }+ -  double and add to stack

```
> 0 votes

# Answer
## Jelly, 10 bytes

```
DLḶ2*U,DPS

```

You know your Jelly code is still golfable when it's above 7 bytes...

```
It basically consists of two parts
   2*       generate a list of the powers of two
 LḶ         for all the powers of 2 from 0 to the length of the binary input
D           Convert the binary string into a list to get its length with L
     U      Then upend that list (for '101010', we now have a list of [32, 16, 8, 4, 2, 1]
      ,     Combine this list
       D    with the individual digits of the input
        P   multiply them with eah other [32*1, 16*0, 8*1, 4*0, 2*1, 1*0]
         S  And sum the result      42 =   32 +  0  +  8 +  0 +  2 +  0

```

Try it online!
> 0 votes

# Answer
# Mathematica, 44 bytes

```
2^Range[Length[d=IntegerDigits@#]-1,0,-1].d&

```

Unnamed function taking an integer argument (interpreted as a base-10 integer, but will only have the digits 0 and 1) and returning an integer. `d` is set equal to the set of digits, and then the dot product of d with the appropriate sequence of powers of 2 generates the value.
> 0 votes

# Answer
# JavaScript, 35 bytes

```
f=([c,...b],n=0)=>c<2?f(b,+c+n+n):n

```

For `c='1'` and `c='0'`, `c<2` returns true.
If `b` is empty, `c` will be undefined in the next recursion and `c<2` will be `false`.
> 0 votes

# Answer
# Julia 0.5, 22 bytes

```
!n=n>0&&2*!(n÷10)|n&1

```

Try it online!
> 0 votes

# Answer
# Keg, `-rr`, ~~14~~ 12 bytes

```
0&÷^⑷2⑻Ë*⑹⑸⅀

```

Try it online!

## Explained

```
0&              # Place 0 into the register. This will serve as the power to which 2 will be raised
  ÷^            # Take the input as a number and split it into it's individual numbers. It is then reversed.
    ⑷           # Start a map applying the following to each item in the input:
      2⑻Ë*      #   Exponate 2 to the power of the register and multiply the number by that value
          ⑹     #   Increment the register
           ⑸⅀  # Close the map and sum the stack, printing that sum implicitly

```
> 0 votes

# Answer
# Japt `-x`, 6 bytes

```
Ô¬ËÑpE

```

Try it
> 0 votes

# Answer
# Stax, 4 bytes

```
╖~♫p

```

Run and debug it

same reducing idea as Jelly.
> 0 votes

# Answer
# Raku, 33 bytes

```
{.flip.comb.kv.map(2*** * *).sum}

```

(If builtins were allowed, this would just be `.parse-base(2)`.)

Explanation:

`.flip` reverses the string, `.comb` converts it into a list of chars, `.kv` inserts the index of each char in front of it. The `map` block consumes two elements at a time, computing the product of 2 to the power of the first argument (the index) all multiplied by the second argument (the 0 or 1), and the resulting list of products is totaled by `.sum`.

The asterisks in the `map` call are doing triple duty: the first two are the exponentiation operator, while the third is a `Whatever` standing for the first argument to the block (and is the reason the expression becomes a block without curlies). Likewise, the fourth is the standard ASCII multiplication operator, while the fifth is another `Whatever` representing the second argument. So this ungolfed version does the same thing:

```
… .map( { 2**$^k × $^v } ) …

```

Try it online!
> 0 votes

# Answer
# shell with `dc`, ~~16~~ ~~13~~ 10 bytes

There's already a `bash` \+ GNU utils, but this solution is POSIX compliant and shorter.

```
dc -e "10o2i$1p"

```

It's also a bit quicker (we use internal functioning instead of extra computation, plus there's only one process call instead of two.) But, quoting and extra spaces aren't mandatory

```
dc -e10o2i$1p

```

Now, explanation of the expression (`-e` argument)

1. `10 o` ask to set Output base to decimal.
2. `2 i` ask to set Input base to binary.
Note that the order matters here. If we issue first `2i`, `10o` would be read as request to set to binary…
3. `$1 p` ask to Print out the entry…
Read then as binary and expressed in decimal form.

Better, on standard installations with no `DC_ENV_ARGS` or others (depending your implementation) variable set, default base is decimal. So, finally

```
dc -e2i$1p

```

Note : `dc` is a big bases-converter where `i` tells how to parse inputs (kinda `scanf()`) and `o` tells how to display it (kinda `printf()`). Values are always stored and manipulated using DCB representation.
> 0 votes

# Answer
# TI-Basic, 29 bytes

```
sum(seq(sub(Ans,length(Ans)-I,1)2^I,I,0,length(Ans)-1

```

Takes input as a string in `Ans`.
> 0 votes

# Answer
# Java 8, 54 bytes

Solution using Streams only :

```
s->s.chars().mapToLong(e->e).reduce(0,(a,b)->2*a+b-48)

```

Try it online!

---

If the question didn't require a long, the answer could have been shorter and more elegant (**38 bytes**) :

```
s->s.chars().reduce(0,(a,b)->2*a+b-48)

```
> 0 votes

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


title: Invert a boolean array

text:
# Question
Title: Invert a boolean array
A nice simple one

# Input

Given a boolean array (Or an acceptable alternative), you can assume the array will never be more than 32 elements long.

```
[false, false, true, false, false]

```

# Output

Invert every element of the array and output it.

```
[true, true, false, true, true]

```

# Rules

* You can write a full program or just a function
* Standard loopholes apply
* Shortest code in bytes, per language, wins!

# Test cases

```
Input:
[true, false]
Output:
[false, true]

Input: //Example of acceptable alternative
[0,1,1]
Output:
[1,0,0]

```

# Answer
> 30 votes
# 05AB1E, 1 byte

Code:

```
_

```

Explanation:

```
_     # Logical not

```

Try it online!

# Answer
> 15 votes
# Javascript ES6, 15 bytes

```
a=>a.map(b=>!b)

```

Not much explanation needed I guess

```
f=
a=>a.map(b=>!b)

a.innerHTML = `[true, false, 1, 0] => ${ f([true, false, 1, 0]) }`
```

```
<pre id=a>
```

# Answer
> 15 votes
# Jelly, 1 byte

```
¬

```

Try it online!

`¬` is logical NOT (1 if false-y, else 0). `C` (“complement”, **1−z**) also works.

# Answer
> 14 votes
# Matlab,  ~~4~~  1 byte

This should be self explanatory.

```
~

```

Matlab has the one-byte negation operator `~`, if you want a function you can use `@not`.

# Answer
> 11 votes
# Haskell, 7 bytes

```
map not

```

Example:

```
Prelude> (map not) [False, True, True]
[True,False,False]

```

# Answer
> 11 votes
# R, 1 byte

```
!

```

Example:

```
> !c(TRUE, FALSE)
[1] FALSE  TRUE

```

It also works with numerical input:

```
> !c(1, 0)
[1] FALSE  TRUE

```

We're not restricted to one-dimensional arrays, either. Let's make a matrix, and randomly populate it with 0s and 1s:

```
> mat = matrix(rbinom(16, 1, .5), ncol=4)
> mat
     [,1] [,2] [,3] [,4]
[1,]    0    1    1    1
[2,]    0    1    0    0
[3,]    0    0    0    0
[4,]    1    1    1    0

```

We can invert this just as easily:

```
> !mat
      [,1]  [,2]  [,3]  [,4]
[1,]  TRUE FALSE FALSE FALSE
[2,]  TRUE FALSE  TRUE  TRUE
[3,]  TRUE  TRUE  TRUE  TRUE
[4,] FALSE FALSE FALSE  TRUE

```

We can continue to do this for arbitrary numbers of dimensions. Here's an example on a four-dimensional array:

```
> bigarray = array(rbinom(32, 1, 0.5), dim=c(2,2,2,2))
> bigarray
, , 1, 1

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

, , 2, 1

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

, , 1, 2

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

, , 2, 2

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

> !bigarray
, , 1, 1

     [,1] [,2]
[1,] TRUE TRUE
[2,] TRUE TRUE

, , 2, 1

      [,1] [,2]
[1,] FALSE TRUE
[2,]  TRUE TRUE

, , 1, 2

     [,1]  [,2]
[1,] TRUE FALSE
[2,] TRUE FALSE

, , 2, 2

      [,1]  [,2]
[1,] FALSE  TRUE
[2,] FALSE FALSE

```

Doesn't work for characters, I'm afraid.

```
> !"Hello world"
Error in !"Hello world" : Invalid argument type.

```

# Answer
> 11 votes
# C, 46 Bytes recursive version

```
f(char*s){*s?putchar(*s&72?*s:*s^1),f(++s):0;}

```

# C, 47 Bytes iterative version

```
f(char*s){for(;*s;putchar(*s&72?*s:*s^1),s++);}

```

Run using this main function

```
main(c,v)char**v;
{
    f(v[1]);
}

```

and input like this

```
a.exe [1,0,1,1,0]
[0,1,0,0,1]

```

# Answer
> 10 votes
# MATL, 1 byte

```
~

```

Try it online!

`~` is the logical *not* and as many functions, it can also be applied to arrays/matrices.

# Answer
> 8 votes
# Perl 6, 4 bytes

"French"/Unicode version:

```
!«*

```

"Texas"/ASCII version:

```
!<<*

```

Input is a single value which can be treated as a list.

This is a a Whatever lambda (`*`) with the logical not prefix operator (`!`) combined using prefix hyper operator (`«`).

Effectively this is the same as:

```
-> $_ { $_.values.hyper.map: &prefix:<!> }
# ( currently the Rakudo implementation doesn't actually do the ｢.hyper｣ call,
#   but prefix ｢«｣ is specifically designated for doing things in parallel )

```

## Usage:

```
# pretend it's a method
say (True,False,True,True).&( !«* );
# (False True False False)

say ( !«* )( (False,False,True,False,False) );
# (True True False True True)

# give it a lexical name
my &list-invert = !«*;

#              v¯¯ a space is necessary here
say list-invert (True,False);
# (False True)

say (False,True).&list-invert;
# (True False)

```

# Answer
> 7 votes
# Labyrinth, 9 bytes

```
,$:)%#$.,

```

Try it online! Assumes newline-separated input with a trailing newline. Thanks to @MartinEnder for help with golfing.

This program's a bit weird for a Labyrinth program - it doesn't make use of the 2D nature of the language, and it actually bounces back and forth. On the first forward trip, we have:

```
[Moving rightward]
,            Read char c of input
 $           XOR c with implicit 0 at bottom of stack
  :)%        Calculate c % (c+1), erroring out if c == -1 from EOF, otherwise returns c
     #$      XOR with (length of stack == 1)
       .     Output (c^1) as char
        ,    Read newline

[Moving leftward]
       .     Output newline
      $      XOR two implicit 0s, stack [0]
    %#       Mod with (length of stack == 1), giving stack [0]
 $:)         Increment, duplicate then XOR, stack still [0]
,            Read char c of input

```

The next occurence of `$` then XORs the existing 0 on the stack with `c`, as opposed to an implicit 0 at the bottom of the stack like in the first run. Both situations leave the stack as `[c]`, and the program repeats thereafter.

Alternative 9-bytes:

```
,:):/$.:,
,::)/)$.,
,:):%)$.,

```

# Answer
> 6 votes
## Mathematica, 7 bytes

```
Not/@#&

```

or without letters:

```
!#&/@#&

```

As for the syntactic sugar: `&` marks the right end of an unnamed function and has very low precedence. `#` refers to the first argument of the nearest and enclosing `&`. `!` is the operator for `Not`. So `!#&` is just an unnamed function that negates its argument, in other words its identical to the built-in `Not`. `/@` is the operator for `Map`. So the code would also be equivalent to the somewhat more readable `Map[Not, #]&`.

# Answer
> 6 votes
# Python, ~~27~~ ~~25~~ 24 bytes

Thanks to Lynn for golfing off two bytes, and xnor and Mego for golfing off another.

```
lambda a:[b^1for b in a]

```

# Answer
> 6 votes
# J, 2 bytes

```
-.

```

This is the negation verb.

## Test case

```
   -. 0 1 0 0 1
1 0 1 1 0

```

# Answer
> 6 votes
# C#, 19 bytes

as an annonymous function, takes a bool\[\] and returns an IEnumerable

```
b=>b.Select(x=>!x);

```

or in 36 bytes with

```
dynamic f(bool[]b)=>b.Select(x=>!x);

```

# Answer
> 6 votes
# Swift 3 (7 bytes)

```
.map(!)

```

e.g.

```
[true, false].map(!)

```

## Explanation

Seems pretty obvious. Calls `map` on the array `[true, false]`. The one "gotcha" is that, in Swift, operators are just functions and can be passed around as arguments. This means `map(!)` is passing the "not" function `!` into `map`.

# Answer
> 6 votes
# Shakespeare Programming Language, 240 bytes

```
.
Ajax,.
Puck,.
Act I:.
Scene I:.
[Enter Ajax and Puck]
Puck:
Open your mind.Is hog as big as you?If so, let us return to scene II.You be sum of difference of zero and you and cat.Open thy heart!Let us return to scene I.
Scene II:.
[Exeunt]

```

Takes input as a string of `\0` and `\1` control characters. Outputs as a string of `0` or `1`. If the input must be the same as the output, replace `Open thy heart` with `Speak thy mind` for no change in bytecount. If `\0` and `\1` can't be used, do the above, but also replace `Open your mind` with `Listen to thy heart` for a 5-byte penalty.

Ungolfed:

```
The Invertion of Veronan Arrays.

Romeo, who stores the element.
Juliet, who lectures him.

Act I: In which an array is inverted.

Scene I: A silent entrance.

[Enter Romeo and Juliet]

Scene II: In which Juliet pours out her heart to Romeo.

Juliet:
  Open your mind. Is nothing better than thee? If so, let us proceed to scene III.
  Thou art as good as the sum of the difference between nothing and thee and my
  cat. Open your heart! Let us return to scene II.

Scene III: Finale.

[Exeunt]

```

This roughly translates to the following C pseudocode:

```
int romeo;

Scene1:
romeo = getchar();
if (0 > romeo) goto Scene2;
romeo = 0 - romeo + 1;
printf("%d", romeo);
goto Scene1;

Scene2:;

```

I'm using this interpreter. Sample run:

```
$ python splc.py invert.spl > invert.c
$ gcc invert.c -o invert.exe
$ echo -ne "\x00\x01\x00" | ./invert
101

```

# Answer
> 5 votes
# IBM/Lotus Notes Formula, 2 bytes

```
!a

```

Usage:

Create a Notes form with two fields named a and b.

a (input) = editable, number, multi-value, comma separated

b (output) = computed, number, multi-value, comma separated

Paste the above formula into b and give a a default value of 0.

Create a new document with the form, enter a binary list in a and press F9 to update the output.

Examples:

Works because given a list as input, Notes formula will apply whatever specified action to every element in the list.

# Answer
> 4 votes
# JAISBaL, 1 byte

```
!

```

Like all the other 1-byte answers, this is the negation operator, which can operate over an array if needed. This leaves the output on the stack, which is printed at the end of the program.

For two bytes, the array can be explicitly printed:

Input is in JAISBaL's incredibly odd array format (which I did invent, but I don't like it...).

Test Cases (Output from the Java interpreter, 3.0.5):

```
Enter a value > [true][false]

--------------------
Stack: [[false, true]]
Locals: {}
----------------------------------------
Enter a value > [false][false][true][false][false]

--------------------
Stack: [[true, true, false, true, true]]
Locals: {}

```

# Answer
> 4 votes
## PowerShell, 15 bytes

```
$args[0]|%{!$_}

```

I *think* this may even work in v1, hence I left the version number off the title. Loops through the input `$args` and negates each item in turn. That resulting array is left on the pipeline.

The neat thing, however, is because PowerShell is so loose on its casting requirements, you can do a completely mixed input and get an appropriate Boolean output. For example, here are the literal Boolean values `$false`/`$true`, the numbers `0` `1` and `123456789` as integers, an empty string, a non-empty string, an empty array, and a non-empty array --

```
PS C:\Tools\Scripts\golfing> .\invert-a-boolean-array.ps1 @($false,$true,0,1,123456789,'','foo',@(),@(1,1))
True
False
True
False
False
True
False
True
False

```

# Answer
> 4 votes
# Perl, 7 bytes

Includes +2 for `-lp`

Give each boolean value as 0 or 1 on its own line

```
invert.pl
1
1
0
^D

```

`invert.pl`:

```
#!/us/bin/perl -lp
$_^=1

```

# Answer
> 3 votes
# Logicode, ~~9~~ 8 bytes

```
out!binp

```

Simple, really.

Takes input as a binary string, as Logicode doesn't have support for lists (so `[true, false]` would be `10`).

The `out` outputs the line's result.

The `!` command calculates the NOT of every bit in the string, so something like `!111` would be `000`.

The `binp` is binary input.

1 byte saved thanks to @daHugLenny

# Answer
> 3 votes
# Brachylog, 7 bytes

```
:{-$_}a

```

Try it online!

### Explanation

```
:{   }a   Apply this predicate to each element of the Input
  -         Decrement
   $_       Negate

```

# Answer
> 3 votes
# Java, 58 bytes

```
void f(boolean[]a){for(boolean i:a)System.out.print(!i);}

```

# Answer
> 3 votes
# Cheddar, 10 bytes

```
@.map((!))

```

I hope I counted right as I'm writing from phone

# Answer
> 3 votes
# brainfuck (58 Bytes)

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

```

Try it here

Ungolfed

```
-[>+<-----]>---     Number 48 (stands for 0)
>,                  Read in first point
[
    <[->->+<<]      Subtract 1 from 48 flag, subtract 1 from read data, add 1 for new flag
    >
    [--<]           If sitting on 1 (true) subtract 2 and move left)
        >[>]<       Move to 48 flag
        [-<+<+>>]   Add 48 to data point
        <+.[-]<     Add 1 move print, zero cell, move to new 48 cell
        >,          Read in next point
]                   Loop if input remaining

```

Takes an input of undivided 1s or 0s (11001).

# Answer
> 3 votes
# Java, 15 bytes

```
s->s.map(b->!b)

```

Note: `s` is a `java.util.stream.Stream<Boolean>` and the import is not necessary, proof below.

## Testing and ungolfed

**LookMaNoImports.java**

```
class LookMaNoImports {
  static Main.F f = s -> // transform a Stream<Boolean>
    s.map(               // by applying its map method
      b ->               // which in turns transforms a boolean
        !b               // by applying its negation.
    );
}

```

**Main.java**

```
    import java.util.Arrays;
    import java.util.List;
    import java.util.stream.Collectors;
    import java.util.stream.Stream;

    public class Main {

        interface F {
            Stream<Boolean> f(Stream<Boolean> s);
        }

        public static void main(String[] args) {
            F f=LookMaNoImports.f;

            test(f, new Boolean[]{true}, new Boolean[]{false});
            test(f, new Boolean[]{false}, new Boolean[]{true});
            test(f, new Boolean[]{true, false}, new Boolean[]{false, true});
            test(f, new Boolean[]{true, true}, new Boolean[]{false, false});
        }

        static void test(F f, Boolean[] param, Boolean[] expected) {
            List<Boolean> result = f.f(Arrays.stream(param)).collect(Collectors.toList());
            if (result.equals(Arrays.asList(expected))) {
                System.out.printf("%s: OK%n", Arrays.toString(param));
            } else {
                System.out.printf("%s: NOT OK, expected %s%n", Arrays.toString(param), Arrays.toString(expected));
            }
        }
    }

```

# Answer
> 3 votes
# Binary Lambda Calculus, 64 bits = 8 bytes

```
0001011000000000010111001011111000001000001100101111011010000010

```

Try it online!

*Note: This is a function and its list format is slightly different from the list format used by default in BLC’s I/O, so the TIO link doesn’t really do anything.*

## Explanation

If you don’t know what lambda calculus is, please read this Wikipedia page about it, since Wikipedia explains it better than I can.

My function takes a list of Church booleans as input. The list encoding that it uses is the one where a list is encoded as its right fold function. i.e. The encoding of `list` is `foldr list` (in pseudo-Haskell). An example of this kind of list is `\c n. c (T (c F n))`, where `T` and `F` are the Church booleans for true and false, respectively. This example represents the list `[true, false]`.

Here is the lambda calculus (pseudo-?)code that I used to get my BLC code:

```
\l. l (\a b. \c n. c (a (\x y. y) (\x y. x)) (b c n)) (\c n. n)

```

(`\` is abstraction, `\a b. ...` means `\a. \b. ...`, abstraction extends as far as it can, and application is left-associative.)

I then represented it using De Bruijin indices:

```
\1 (\\\\2 (4 (\\1) (\\2)) (321)) (\\1)

```

Note that `321` means `((3)2)1`, not literally a De Bruijin index using the number 321.

Then I used `@` to represent application (i.e. `@mn` means `m(n)`).

```
\@@1\\\\@@2@@4\\1\\2@@321\\1

```

<sub>(Note that I transcribed this “by hand,” so if my answer doesn’t work, then it’s probably a problem with this.)</sub>

I then used this to get the BLC code. (See here for information about how the encoding works and more information about BLC.)

## The actual explanation is here

So I’m going to explain using a condensed version of the lambda calculus notation.

Note that my vocabulary, specifically “the accumulator’ and “the new element”, is probably wrong. I’m basically trying to paint the image of a for loop initializing the “accumulator” at a value and changing it each time it passes through a “new element” of the list.

```
\l.l(\abcn.c(a(\xy.y)(\xy.x))(bcn))(\cn.n)

\l.l(                             )(     )  Right fold of l.
                                    \cn.n   Start the accumulator as the empty list.
     \a                                     a is the new element.
       b                                    b is the accumulator.
        cn.c(                               Prepend...
             a(\xy.y)(\xy.x)                  the logical negation of a
                            )(bcn)            to the accumulator.

```

(This is a high-level overview and it’s probably possible to explain some of these concepts a better way.)

# Answer
> 2 votes
# CJam, 4 bytes

```
{:!}

```

Input is a list of `0`s and `1`s.

Try it online!

# Answer
> 2 votes
# Japt, 3 bytes

```
¡!X

```

Japt doesn't have boolean input, so input is an array of 0s and 1s. Test it online!

### How it works

```
¡    // Map each item X in the input to
 !X  //  the boolean NOT of X.
     // Implicit output

```

# Answer
> 2 votes
# Retina, 3 bytes

```
%`0

```

Try it online!

For each line (`%`), count the number of `0`s.

# Answer
> 2 votes
# Python 2, 24 bytes (non-competing)

```
lambda a:[i-1for i in a]

```

Logic is similar to Steven's, but I tried to use this comment's idea, but different, because it still takes `0`/`1` arrays, not `0`/`-1`. There is no byte shaving for using `0`/`-1`, so let's be sane. Note that this is non-competing, until Steven or Lynn allows me to use the idea. If so, I *might* remove the non-competing mark. Note that this code cannot be shamelessly stolen, it's still here. Only Steven can use it for his answer.

# Answer
> 2 votes
# Ruby, 14 bytes

Anonymous function:

```
->a{a.map &:!}

```

Test it:

```
->a{a.map &:!}.call([true, true, false, true, false, true, true])
# => [false, false, true, false, true, false, false]

```

# Answer
> 2 votes
# Julia (1 Byte - Thanks to Dennis \[See Comments\])

```
!

```

Map the logical not to all elements of collection y, works due to automatic vectorization (as Dennis explained). My previous answer was basically using \`f(n)=map(!,n)' to map the logical not, but Julia does this on it's own. Jeez, what a cool language. Second time using it, still trying to learn here!

Try it here

# Answer
> 2 votes
## Perl 6, 9 bytes

```
*.map: !*

```

Usage:

```
say (*.map: !*)((0, 1, 1)) # (True False False)

```

# Answer
> 2 votes
## Actually, 2 bytes

```
♂Y

```

Try it online!

Map () Boolean negate (`Y`)

# Answer
> 2 votes
## Clojure, 12 bytes

```
#(map not %)

```

Basically the same as the Haskell answer. Unfortunately, Clojure doesn't have implicit partial application; thus the function macro.

# Answer
> 2 votes
# APL (Dyalog Unicode), 1 byte

```
~

```

Try it online!

# Answer
> 2 votes
# Factor, 4 bytes

```
vnot

```

Try it online!

# Answer
> 1 votes
# Pyth, 2 bytes

```
!M

```

Explanation: (M)ap boolean not (!) over input.

Try it online!

# Answer
> 1 votes
## Hoon, 24 bytes

```
|*
*
(turn +< |=(? !+<))

```

Creates a generic gate, map over the contents of the list, negate all loobeans in it.

This uses the normal Hoon tricks, namely using a generic ("wet"/`|*`) gate to avoid having to specify the sample type, along with having unnamed samples (`*` or `?`) and using tree navigation syntax (`+<`) to fetch them.

```
> a
~[%.y %.n %.n %.y %.n %.y]
> =f |*
  *
  (turn +< |=(? !+<))
> (f a)
~[%.n %.y %.y %.n %.y %.n]

```

# Answer
> 1 votes
# braingasm, 9 bytes

```
,[48-z:,]

```

Assumes that input from stdin is a string of only `"0"`s and `"1"`s, i.e. bytes containing the value `48` or `49`. Prints the negated values to stdout.

**How it works**: Read one byte from stdin (`,`), and loop (`[]`) until the end of the input. For each byte, subtract 48 (`48-`) and print `1` if the result is 0 and vice versa (`z` is the zero-flag, `:` prints the given integer value), then get another byte from stdin (`,`)

Run it like e.g. `$ echo -n 001011 | braingasm invert.bg` and get `110100`

# Answer
> 1 votes
# Groovy (19 Bytes)

```
{x->x.collect{!it}}

```

Simple mapping function in a closure.

# Answer
> 1 votes
# Clojure, 12 bytes

```
(map not x)

```

as in:

```
(map not [true false true])

```

=\> (false true false)

Updating due to the objection that this is not a function or program:

```
#(map not %)

```

Returns a function that `not`s anything passed to it.

# Answer
> 1 votes
## Stata, 20 bytes

```
recode x (0=1) (1=0)

```

x is the input, and the rest is self-explanatory

# Answer
> 1 votes
# Scala, 27 bytes

```
def f(a:Boolean*)=a map(!_)

```

Takes a bool array as varargs and maps each element to its inverse.

# Answer
> 1 votes
# Kotlin, 13 bytes

```
{it.map{!it}}

```

This is a lambda of `(List<Boolean>)->List<Boolean>` type (or `(BooleanArray)->List<Boolean>`, as `map` function on arrays returns lists instead of arrays).

`{it.map{!it}.toBooleanArray()}` would return the result as an actual array.

# Answer
> 1 votes
# sed 8

```
y,01,10,

```

Takes input as 1s and 0s.

# Answer
> 1 votes
# Scala, ~~36~~ ~~35~~ 34 bytes

`def f(a:Array[Boolean])=a.map(!_)`

Discovered I could remove the second space. Discovered I could remove brackets.

# Answer
> 1 votes
# Gogh, 4 bytes

```
{!}m

```

Usage:

```
$ ./gogh -noa '{!}m' "1 0 1 0 0 0 1"
[0 1 0 1 1 1 0]

```

# Answer
> 1 votes
# Racket, 15 bytes

```
(curry map not)

```

Basically the Haskell answer.

# Answer
> 1 votes
## Pyke, 2 bytes

```
m!

```

Try it here!

```
map(not, input)

```

# Answer
> 1 votes
## Golang, 40 bytes

```
func(a[]bool){for i,b:=range a{a[i]=!b}}

```

### usage

```
package main
import "fmt"
func main() {
    a:=[]bool{true, true, false}
    func(a []bool){for i,b:=range a{a[i]=!b}}(a)
    fmt.Print(a) // => [false false true]
}

```

# Answer
> 1 votes
# Brainfuck, ~~72~~ ~~69~~ 61 bytes

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

```

Closest i managed to get as BF dosent have Array support

Formatting is stupid, i will fix it when i get a pc... Somehow it wont let me post it as a snippet

# Answer
> 1 votes
# Brainfuck, 24 bytes

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

```

Try it online!

The same as my answer to a similar question.

Relies on 8-bit wrapping cells, the cell size might not matter (untested) but wrapping definitely is. The main part the program is the `>++[->++[<]>-]>-` does some rather convoluted things to flip the last bit of the number.

A shorter solution of 19 bytes is

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

```

but this requires the `<` to noop if the data index is 0, instead of the more typical implementation of going into negative indeces.

# Answer
> 1 votes
# PHP, 30 bytes

```
foreach($argv[1] as$i)echo!$i;

```

Testing code:

```
$argv[1] = [true,true,false,true,false,false,true,false];
foreach($argv[1] as$i)echo!$i;

```

Test online

# Answer
> 1 votes
# C++11, 30 bytes

As unnamed lambda:

```
[](auto&v){for(auto&x:v)x=!x;}

```

Accepts any standard container like `vector<int>` (but not `vector<bool>`) or `int[]` or `bool[]`.

# Answer
> 1 votes
# 6502 Machine Language - 14 Bytes

```
AE 00 01 CA B5 00 49 01 95 00 8A D0 F6 00

```

Array of bytes is in zero page. Length of array is in $0100.

Flipped array is in zero page.

Assembler code:

```
AE 00 01 - ldx $0100
CA       - dex
B5 00    - lda $00, X
49 01    - eor #$01
95 00    - sta $00, X
8A       - txa
D0 F6    - BNE (-10)
00       - BRK

```

(My first golf answer - sorry if format is off.)

# Answer
> 1 votes
# Vyxal `a`, ~~2~~ 1 byte

*-1 thanks to lyxal*

Try it Online!

# Answer
> 1 votes
# Python 3, 26 bytes

```
lambda s:[~x+2 for x in s]

```

Try it online!

# Answer
> 1 votes
# Lexurgy, 12 bytes

Input is a string of `a`s for truthy and `b`s for falsy. These can be replaced with any two distinct characters, as a "proper" falsy value in Lexury *would* be an empty string, however since empty string is empty string, and infinite number of empty strings can be anywhere within a string, so two distinct characters are required.

```
a:
a=>b
b=>a

```

If you want numbers (16 bytes):

```
a:
\1=>\0
\0=>\1

```

# Answer
> 1 votes
# Arturo, 15 bytes

```
$=>[map&=>not?]

```

Try it

# Answer
> 1 votes
# Thunno 2, 1 byte

```
~

```

Attempt This Online!

Built-in for vectorised logical NOT.

# Answer
> 1 votes
# Japt `-m`, 2 bytes

```
^1

```

Try it here

# Answer
> 1 votes
## C, 37 bytes

```
f(a,l)int *a;{for(;l--;*a++=*a?0:1);}

```

a being the array (pointer) and l being the length of the array.

**Readable version**

```
f(t,i)int *t;{ // K&R to save bytes
  for(;i--; // Run i times
  *t++=*t?0:1); // Flip the value of array element and increment
}

```

# Answer
> 0 votes
# PHP , 45 Bytes

```
<?foreach($_GET[a]as$v)$a[]=1-$v;print_r($a);

```

# Answer
> 0 votes
# Java, 51 bytes

```
l.stream().map(b->!b).collect(Collectors.toList());

```

l = a Collection of Booleans I feel like this could be shorter, then again golfing in java ^^

# Answer
> 0 votes
## Common Lisp, 7

```
bit-not

```

Negate bits on a bit array.

## Example

```
(bit-not #*00101010010100101001010010101)
=> #*11010101101011010110101101010

```

# Answer
> 0 votes
# Ruby, 30 bytes

```
gets.split(?,).map{|e|!eval e}

```

`"true,false"` outputs `false,true`.

# Answer
> 0 votes
# Swift(2.2) 44 bytes

I am using x as the input variable here. For example,

```
let x = [true,false]

```

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

### Golfed

```
let y = {let b = $0.map({!$0});print(b);}(x)

```

### unGolfed

```
let y = {
   let b = $0.map({!$0})
   print(b);
}(x)

```

# Answer
> 0 votes
# PHP (231 Bytes)

```
function flip_bool_array($array) {
  $newarray = array();
  foreach ($array as $bool) {

   if ($bool === true) {
    $bool = false;
   } else {
    $bool = true;
   }

  $newarray[] = $bool;

}

return $newarray;

}

```

## Explanation

The function accepts an array and loops over it testing each value for a true value and setting it to false, if the value is not true then it is set to true. Each boolean is added to a new array and returned.

# Answer
> 0 votes
# dc, 44 bytes

Append this to a line of space-delimited input and echo it into `dc`. Output is delimited with newlines and punctuated with error messages (due to the blatant abuse of `k`). If you quote the stuff, it'll give you even more errors. (When we re-vamp `dc` in the next version, we should probably do something about that.) I suggest pairing with a `2>nul` or other system-specific hack for suppressing whiny programs.

```
0sz[1r-SAlz1+szz0<a]dsax[lzd1-szLApk0<a]dsax

```

Explained:

```
              # "ToS" := "top of stack"
0sz           # Initialise register `z' with 0: this will hold the length of our input
[             # Open macro definition
 1r-          #  Replace ToS with !(ToS): 1-1==0, 1-0==1
 SA           #  Store this result on the top of stack `A'
 lz1+sz       #  Increment z, our length counter
 z0<a         #  If the stack depth is positive, repeat (we still have input to negate)
]dsax         # Store a copy of macro in register `a' and execute it
              # At this point, our input has been negated and stored in A,
              #  first-in-first-out orientation
[             # Open macro definition
 lzd1-sz      #  Decrement z and keep a copy of it for later
 LA           #  Push ToS(A) onto stack; pop from A
 p            #  Peek at ToS
 k            #  `k' is for KILL THE TOP OF STACK BWAHAHAHA
 0<a          #  The value from register `z' is now on top: if positive, we still have
              #   values to print, so repeat macro
]dsax         # I'm in a chaotic mood, so let's just re-use `a'

```

# Answer
> 0 votes
## dc, 47 bytes

```
?zsN0sI[z:az0<A]dsAx[lI1+ddsI;a1r-n32PlN>R]dsRx

```

The actual code to invert a boolean (0 or 1) is `1r-`. The rest is for reading the list and printing it in the same order, which is quite hard because of the (LIFO) stack that dc uses to store the input.

**Explanation:**

```
?zsN0sI         # read input, LIFO, initialize N = nr_elements and I = 0 (iterator)
[z:az0<A]dsAx   # loop A: move the stack content into array 'a' (I add a[n] first,
                #then a[n-1], ..., then a[1] and a[0] is not used)
[lI1+ddsI;a     # loop R: increment iterator and push a[I] to stack (input order)
   1r-n32P         #invert value and print it with a space separator
lN>R]dsRx       #repeat (R)

```

**Run:**

```
dc -f invert_boolean.dc <<< "1 0 1 1"

```

**Output:** there is a trailing separator (space) at the end, but I hope that's ok

```
0 1 0 0

```

**Note:** my answer is similar in concept to that of @Joe's, but there are differences in terms of I/O handling, stack manipulation (I use arrays) and lack of warnings. Do check his answer as well.

# Answer
> 0 votes
# Emacs Lisp, 25 bytes

```
(lambda(x)(mapcar'not x))

```

Not very creative.

# Answer
> 0 votes
## Racket 11 bytes

```
(map not l)

```

Testing:

```
(define l '(#t #f #t)) ; define a list of booleans

(map not l)

```

Output:

```
'(#f #t #f)

```

# Answer
> 0 votes
# \>\<\> Fish \- 9 (16?) Bytes

My second golf and my first in \>\<\> Fish!

```
l?!;r0=nr

```

I'm not sure how to count bytes when flags are considered, but this solution works when running the python interpreter with the -v flag and then space-separated 1's and 0's. If this doesn't match spec, I can remove the answer.

## Example

Input/Run:

```
python fish.py --code "l?!;r0=nr" -v 0 1 0 1 1

```

Output:

```
10100

```

If I'm not allowed to use flags, and instead need to take the input from the input stack (such as on https://fishlanguage.com/playground), the code becomes longer as I must read from the input stack (either 1 or 0 without any separation) until there are no more values, and then convert the char value of the input (1 becomes 49 and 0 becomes 48) to their decimal values before my comparison. I'm not sure how to count bytes for \>\<\> but I believe this would be **16 bytes**.

```
i:1+?!;f3*3+-0=n

```

# Answer
> 0 votes
# dimwit 8 bytes (non-competing)

```
R1,0}0,1

```

Replaces all 0's with 1's, and vice versa.

Takes input through a string of 0's and 1's, and outputs similarly. Hopefully that's acceptable ;)

### Try it here!

# Answer
> 0 votes
# SmileBASIC, 25 bytes

```
DEF l l
ARYOP 1,l,1,l
END

```

### Explanation:

```
DEF 'create a function
    l 'named "L"
      l 'with 0 outputs and 1 input named "L"
ARYOP 'array operation
      1 'mode 1 (subtract)
       ,l 'set each element in L to...
         ,1 '1 minus...
           ,l 'the corresponding element in L
END 'end function definition

```

# Answer
> 0 votes
# FALSE, 13 bytes

```
[49^$0>][-.]#

```

Input is a list of `0` and `1` characters.

# Answer
> 0 votes
# Tcl, 31 bytes

```
proc N L {lmap b $L {expr !$b}}

```

Try it online!

# Answer
> 0 votes
# Zsh, 14 bytes

Assumes input is given as arguments. Try it Online!

```
for z;<<<$[!z]

```

Or without bending the rules so much, this uses array I/0 (26B):

```
for z ($A)B+=($[!z])
<<<$B

```

# Answer
> 0 votes
# MMIX, 24 bytes (6 instrs)

```
00000000: 25010101 82ff0001 73ffff01 a2ff0001  %¢¢¢²”¡¢s””¢ɱ”¡¢
00000010: 5901fffc f8000000                    Y¢”‘ẏ¡¡¡

```

Requires at least one element. Pass array as first argument, length as second.

```
invarr  SUB  $1,$1,1        // loop: i--
        LDBU $255,$0,$1
        ZSZ  $255,$255,1
        STBU $255,$0,$1     // a[i] = !a[i]
        PBNN $1,invarr      // if(i >= 0) goto loop
        POP  0,0

```

# Answer
> 0 votes
# Erlang, ~~43~~ 38 bytes

`n(Z)->lists:map(fun(X)->not X end,Z).`

Many thanks to @Redwolf Programs for saving 5 bytes.

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


title: Maybe fractal sequence?

text:
# Question
Title: Maybe fractal sequence?
## Background

A **fractal sequence** (Wikipedia; MathWorld) is an infinite sequence of positive integers meeting the following conditions:

1. Each positive integer appears infinitely many times in the sequence.
2. Before the first occurrence of a number \\$i \> 1\\$, every number smaller than \\$i\\$ appears at least once.
3. Between consecutive occurrences of \\$i \> 1\\$, each number smaller than \\$i\\$ appears exactly once.

More formal definitions can be found on the Wikipedia and MathWorld pages linked above.

Fractal sequences are named as such because deleting the first occurrence of each number (upper-trimmed subsequence) yields the original sequence unchanged.

A few notable properties:

* Decreasing all terms by one and removing all zeros (lower-trimmed subsequence) gives another fractal sequence, which may or may not be identical to the original sequence.
* The signature sequence of an irrational number \\$x\\$ is a fractal sequence, and it is also identical to its lower-trimmed subsequence. The signature sequence of \\$x\\$ is defined as: sort the numbers \\$i + jx\\$ in ascending order where \\$i, j \in \mathbb{N}\\$, and extract the corresponding values of \\$i\\$.

A few notable fractal sequences:

* A002260 and A004736: Count each number upwards and downwards, respectively. These are also ordinal transforms of each other.

```
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ...
1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1, ...

```
* A054073: Triangle where the \\$n\\$th row consists of \\$1 \cdots n\\$ sorted in the order of fractional parts of each number multiplied by \\$\sqrt2\\$.

```
1,
1, 2,
3, 1, 2,
3, 1, 4, 2,
5, 3, 1, 4, 2,
5, 3, 1, 6, 4, 2,
5, 3, 1, 6, 4, 2, 7, ...

```
* A122196 and A122197: Count each number down by steps of 2, and count each number upwards twice, respectively. These are also ordinal transforms of each other.

```
1, 2, 3, 1, 4, 2, 5, 3, 1, 6, 4, 2, 7, 5, 3, 1, 8, 6, 4, 2, ...
1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, ...

```

## Challenge

Given a nonempty finite sequence \\$s\\$ of positive integers, determine if it is a prefix of some infinite fractal sequence. In other words, determine if \\$s\\$ satisfies the following:

1. (from condition 2 above) for each number \\$n\\$ appearing in \\$s\\$, every number \\$i \< n\\$ appears before the first appearance of \\$n\\$, and
2. (from condition 3 above) for each number \\$n\\$ in \\$s\\$, every number \\$i \< n\\$ appears exactly once between every consecutive appearance of \\$n\\$ AND at most once after the last appearance of \\$n\\$.

For output, you can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

### Truthy

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

```

### Falsy

```
[999]
[1, 3]
[1, 2, 1, 3, 2, 1, 4, 1]
[1, 3, 1, 5, 3, 1, 7, 5]

```

# Answer
> 5 votes
# BQN, 22 19 17 bytes

*-3 thanks to Bubbler*

*-2 by further rearrangement*

```
×∘⊒⊸(/≡∨⊸/)∧⊢≡1+⊐

```

Try it here.

Explanation:

```
×∘⊒⊸(/≡∨⊸/)∧⊢≡1+⊐ #
×∘⊒⊸(     )       # Between the sign of the running occurrence count and the input:
     /            # filter (removing first occurrences)
      ≡           # and match against
       ∨⊸/        # the equal length prefix of the input (sorts down the boolean mask, bringing 1's to front)
           ∧      # and
            ⊢≡    # does the input match
              1+⊐ # its classification + 1

```

Why it works:

Classify () assigns each unique element a number (starting from 0) according to the order of first appearance. That means that if the input matches its classification (+ 1 since starting from 0), every number less than n appears before n, thus satisfying condition 2.

For condition 3, we can use the useful property of fractal sequences that if the first occurrence of each element is removed the result remains the same. Since this is not an infinite sequence we simply check if the remaining sequence is a prefix of the input.

# Answer
> 4 votes
# JavaScript (ES6), 52 bytes

Returns *false* for valid or *true* for invalid.

```
a=>a.some(v=>v^=a[~v]^=a[~v]?v-a[j++]&&-1:++i,i=j=0)

```

Try it online!

### Commented

```
a =>               // a[] = input array, re-used as an object to store
                   //       a 1-indexed ID for each unique value in a[]
a.some(v =>        // for each value v in a[]:
  v ^=             //   test whether v is different from:
    a[~v] ^=       //     the updated value of a[~v]:
      a[~v] ?      //       if this is not the first occurrence of v:
        v - a[j++] //         leave a[~v] unchanged if a[j++] == v
        && -1      //         otherwise: XOR it with -1, which forces
                   //         the comparison with v to fail
      :            //       else:
        ++i,       //         increment i and set a[~v] to i
  i = j = 0        //   start with i = 0 (ID of unique values)
                   //          and j = 0 (pointer in a[])
)                  // end of some()

```

# Answer
> 4 votes
# Python 3, ~~91~~ 65 bytes

```
f=lambda s:s and{*s[-max(s):]}=={*range(1,max(s)+1)}and f(s[:-1])

```

Try it online!

uses the empty list `[]` as truthy value and `False` for falsey

## How it works :

* `s and` : if the list is empty, return it (truthy value)
* `{*s[:-max(s)]}=={*range(1,max(s)+1)}` verify that all numbers are present once in the last chunk of the list;
* `and f(s[:-1])` if the above is `True` (the last item doesn't contradict the sequence), it tests the list truncated to the last item.

By recursivity, it check that all items are correct

# Answer
> 2 votes
# Jelly, 12 bytes

```
ṀRḟṣṪṪƊƲƤ⁼W€

```

A monadic Link that accepts a list of positive integers and yields `1` if a prefix of some infinite fractal sequence, or `0` if not.

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

### How?

Checks that every non-empty prefix contains all integers up to and including its maximum *after* the penultimate\* occurrence of its ultimate value.
* If a prefix only has one occurrence of its ultimate value then the whole prefix is used.

```
ṀRḟṣṪṪƊƲƤ⁼W€ - Link: list, L
        Ƥ    - for each non-empty prefix, P, of L:
       Ʋ     -   last four links as a monad, f(P):
Ṁ            -     maximum -> M
 R           -     range -> [1,2,3,...,M] = X
      Ɗ      -     last three links as a monad, f(P):
    Ṫ        -       tail -> ultimate value = U
   ṣ         -       P split at occurrences of U
     Ṫ       -       tail -> values after "penultimate" U =  T
  ḟ          -     filter discard -> X without any of T
          W€ - wrap each of L in a list
         ⁼   - equal?

```

# Answer
> 2 votes
# 05AB1E, 18 bytes

```
Ù0.;0KÅ?IηεÙZLQ}P*

```

Try it online!

-5 thanks to @ovs

# Answer
> 1 votes
# Charcoal, 45 bytes

```
⬤θ⬤…¹ι∧№…θκλ›⁼№…θκλ⁺№…θ⌕θιλ№…θκι›№θλ⁺№…θκλ№θι

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a fractal sequence, nothing if not. Explanation:

```
 θ                                              Input array `q`
⬤                                               All values `i` match
   …¹ι                                          Range from `1` to `i`
  ⬤                                             All values `l` match
        …θκ                                     Prefix of `q`
       №   λ                                    Contains `l`
      ∧                                         Logical And
              №…θκλ                             Count of `l` in prefix
             ⁼                                  Equals
                    №…θ   λ                     Count of `l` before
                       ⌕θι                      First `i` occurrence
                   ⁺                            Plus
                           №…θκι                Count of `i` in prefix
            ›                                   And Not
                                 №θλ            Count of `l` in `q`
                                ›               Is greater than
                                     №…θκλ      Count of `l` in prefix
                                    ⁺           Plus
                                          №θι   Count of `i` in `q`
                                                Implicitly print

```

For a given positive integer `i` appearing in the input sequence `q`, each positive integer `l<i` must pass the following tests:

* `l` must appear before the given occurrence of `i`
* The number of times `l` appears before the given occurrence of `i` equals the number of times `l` appears before the first occurrence of `i` plus the number of previous occurrences of `i`
* The number of times `l` appears in total must not exceed the number of times `l` appears before the given occurrence of `i` plus the number of occurrences of `i`

Note that the first and third tests are only useful for the first occurrence of `i`, but it's golfier to uselessly test them for each occurrence.

# Answer
> 1 votes
# Haskell, 65 bytes

Based on wasif's 05AB1E answer.

```
import Data.List
f x=isPrefixOf(x\\nub x)x&&[1..maximum x]==nub x

```

Try it online!

# Answer
> 0 votes
# Scala, 125 bytes

Golfed version. Try it online!

```
def f(s:Seq[Int]):Boolean=s match{case Nil=>true case _=>s.takeRight(s.max).toSet==(1 to s.max).toSet&&f(s.dropRight(s.max))}

```

Ungolfed version. Try it online!

```
object Main {
  def f(s: List[Int]): Boolean = s match {
    case Nil => true
    case _ =>
      val max = s.max
      val range = (1 to max).toSet
      s.takeRight(max).toSet == range && f(s.dropRight(max))
  }

  def main(args: Array[String]): Unit = {
    val testsTrue = List(
      List(1),
      List(1, 1, 1),
      List(1, 2, 3),
      List(1, 2, 1),
      List(1, 2, 1, 3, 2, 1, 4, 3),
      List(1, 1, 2, 3, 1, 2, 3, 1, 4, 2, 5, 3, 1)
    )

    val testsFalse = List(
      List(999),
      List(1, 3),
      List(1, 2, 1, 3, 2, 1, 4, 1),
      List(1, 3, 1, 5, 3, 1, 7, 5)
    )

    for (t <- testsTrue) {
      println(s"${t} => ${f(t)}")
    }

    println("-" * 20)

    for (t <- testsFalse) {
      println(s"${t} => ${f(t)}")
    }
  }
}

```

# Answer
> 0 votes
# Wolfram Language (Mathematica), 113 bytes

```
(a=Union@#;f=1>0;Do[f=f∧First@(s=Split[#,#=!=e&])⋂(l=Range@(e-1))==l;(f=f∧l⋂#==l)&/@s[[2;;-2]],{e,a}];f)&

```

Try it online!

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