title: Is it an OVSF code?

text:
# Question
Title: Is it an OVSF code?
Given a list of `1`s and `-1`s, determine whether or not it is a valid OVSF code (by outputting a truthy or falsey value).

OVSF codes are defined as follows:

* `[1]` is an OVSF code.
* If `X` is an OVSF code, then `X ++ X` and `X ++ -X` are both OVSF codes.

Here `++` is list concatenation, and `-` negates every element in the list.
* No other lists are valid OVSF codes.

You may assume the input list contains only `-1` and `1`, but you must handle the empty list correctly, as well as lists whose length is not a power of 2.

Shortest code (in bytes) wins.

# Test cases

```
[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[-1, 1] -> False
[-1, -1] -> False
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True

```

# Answer
# Jelly, ~~18~~ ~~16~~ ~~14~~ 11 bytes

```
^2/Eam2µḊ¿Ṭ

```

Outputs `[1]` (truthy) for OVSF codes, `[]` (falsy) otherwise.

Try it online!

### Background

Like @LuisMendo's MATL answer and @xnor's Python answer, this submission verifies the input array "from the inside out".

Every (non-overlapping) pair of elements of a OVSF code of length two or higher is essentially a copy of the the first pair, either with the same signs or with both signs swapped. Likewise, every (non-overlapping) 4-tuple of elements of a OVSF code of length four or higher is essentially a copy of the the first 4-tuple, either with the same signs or with both signs swapped. The same is true for 8-tuples, 16-tuples, etc., up to the length of the OVFS code.

One way to verify this is to check all pairs for equality modulo the sign first, then remove the second element of each pair (which is now redundant information). If we repeat this process once more, we're essentially checking all 4-tuples. In the next iteration, we're comparing 8-tuples, etc.

Finally, if all the required 2k-tuples were equal modulo the sign and the array has been reduced to a singleton, it is sufficient to check if the remaining element is a **1**.

### How it works

```
^2/Eam2µḊ¿Ṭ  Main link. Argument: A (array of 1's and -1's)

       µḊ¿   While dequeuing A (removing its first element) yields a non-empty
             array, execute the monadic chain to the left, updating A with the
             return value after each iteration.
^2/            Compute the bitwise XOR of each non-overlapping pair of elements of
               A. Note that 1 ^ 1 = 0 = -1 ^ -1 and 1 ^ -1 = -2 = -1 ^ 1.
               For an array of even length that consists of the same pairs modulo
               the sign, this returns either an array of 0's or an array of -2's.
               If the length is odd, it will also contain the last element, which
               is either a 1 or a -1.
   E           Test the elements of the result for equality. This yields 1 if the
               array consists solely of 0's or solely of -2's, 0 otherwise.
    a          Take the logical AND of the previous result and every element of A.
               This returns A if it passed the previous test, but replaces all of
               its elements with 0's otherwise.
     m2        Modulo 2; select every second element of A, starting with the first.
             At this point, the last return value can be:
               • [  ] if the input was empty
               • [ 1] if the input was a valid OVSF code
               • [-1] if the input was the negative of a valid OVSF code.
               • [ 0] in all other cases.
           Ṭ  Untruth; yield an array with 1's at the specified indices.
              Indexing is 1-based in Jelly, so [1] returns [1], the array with a 1
              at index 1. Since the indices -1 and 0 are non-canonical, the arrays
              [-1] and [0] are mapped to []. The empty array remains empty.

```
> 8 votes

# Answer
## Mathematica, ~~52~~ ~~47~~ 45 bytes

Byte count assumes CP-1252 encoding and `$CharacterEncoding` set to `WindowsANSI` (the default on Windows installations).

```
±___=!(±1=1>0)
a__±b__/;a!==b!||{a}==-{b}:=±a

```

This defines a variadic function `PlusMinus`, which takes the input list as a flat list of arguments and returns a boolean, e.g. `PlusMinus[1, -1, -1, 1]` gives `True`. It's theoretically also usable as an operator `±`, but that operator is only syntactically valid in unary and binary contexts, so the calling convention would get weird: `±##&[1,-1,-1,1]`. It will throw a bunch of warnings that can be ignored.

This will also throw a few warnings which can be ignored.

There *might* be away to shorten the somewhat annoying `a!==b!||{a}==-{b}` part, but I'm not finding anything right now. Keywords like `SubsetQ` and `MatrixRank` are simply too long. :/

### Explanation

The solution basically defers all the tricky things to Mathematica's pattern matcher and is therefore very declarative in style. Apart from some golfitude on the first line, this really just adds three different definitions for the operator `±`:

```
±___=False;
±1=True;
a__±b__/;a!==b!||{a}==-{b}:=±a

```

The first two rows were shortened by nesting the definitions and expressing `True` as `1>0`.

We should deconstruct this further to show how this actually defines a variadci function `PlusMinus` by only using unary and binary operator notation. The catch is that all operators are simply syntactic sugar for full expressions. In our case `±` corresponds to `PlusMinus`. The following code is 100% equivalent:

```
PlusMinus[___]=False;
PlusMinus[1]=True;
PlusMinus[a__,b__]/;a!==b!||{a}==-{b}:=PlusMinus[a]

```

By using sequences (sort of like splats in other languages) as the operands to `±` we can cover an arbitrary number of arguments to `PlusMinus`, even though `±` isn't usable with more than two arguments. The fundamental reason is that syntactic sugar is resolved first, before any of these sequences are expanded.

On to the definitions:

The first definition is simply a fallback (`___` matches an arbitrary list of arguments). Anything that isn't matched by the more specific definitions below will give `False`.

The second definition is the base case for the OVSF, the list containing only `1`. We define this to be `True`.

Finally, the third definition applies *only* to lists that can be decomposed into `X ++ X` or `X ++ -X`, and recursively uses the result for `X`. The definition is limited to these lists by ensuring they can be split into subsequences `a` and `b` with `a__±b__` and then attaching the condition (`/;`) that either `{a}=={b}` or `{a}==-{b}`. Defining `PlusMinus` as a variadic function in this weird way via an operator saves a whopping **5** bytes over defining a unary operator `±` on lists.

But wait, there's more. We're using `a!==b!` instead of `{a}=={b}`. Clearly, we're doing this because it's two bytes shorter, but the interesting question is why does it work. As I've explained above, all operators are just syntactic sugar for some expression with a head. `{a}` is `List[a]`. But `a` is a *sequence* (like I said, sort of like a splat in other languages) so if `a` is `1,-1,1` then we get `List[1,-1,1]`. Now postfix `!` is `Factorial`. So here, we'd get `Factorial[1,-1,1]`. But `Factorial` doesn't know what to do when it has a different number of arguments than one, so this simply remains unevaluated. `==` doesn't really care if the thing on both sides are lists, it just compares the expressions, and if they are equal it gives `True` (in this case, it won't actually give `False` if they aren't, but patterns don't match if the condition returns anything other than `True`). So that means, the equality check still works if there are at least two elements in the lists. What if there's only one? If `a` is `1` then `a!` is still `1`. If `a` is `-1` then `a!` gives `ComplexInfinity`. Now, comparing `1` to itself still works fine of course. But `ComplexInfinity == ComplexInfinity` remains unevaluated, and *doesn't* give true even though `a == -1 == b`. Luckily, this doesn't matter, because the only situation this shows up in is `PlusMinus[-1, -1]` which isn't a valid OVSF anyway! (If the condition did return `True`, the recursive call would report `False` after all, so it doesn't matter that the check doesn't work out.) We can't use the same trick for `{a}==-{b}` because the `-` wouldn't thread over `Factorial`, it only threads over `List`.

The pattern matcher will take care of the rest and simply find the correct definition to apply.
> 15 votes

# Answer
## Haskell, 57 bytes

```
q=length
f l=l==until((>=q l).q)(\s->s++map(*l!!q s)s)[1]

```

Given input list `l`, grows a OVSF code `s` by starting from `[1]` and repeatedly concatenating either `s` or `-s`, whichever makes the first element match that of `l`. Then, checks that the result is `l` at the end. This is checked once `s` has length at least that of `l`.

Some alternatives recursive structures also happened to give 57:

```
(s%i)l|length l<=i=s==l|j<-2*i=(s++map(*l!!i)s)%j$l
[1]%1

q=length
s%l|q s>=q l=s==l|r<-s++map(*l!!q s)s=r%l
([1]%)

q=length
g s l|q s<q l=g(s++map(*l!!q s)s)l|1>0=s==l
g[1]

```
> 9 votes

# Answer
# MATLAB/Octave, 94 bytes

```
function a=f(r);n=nnz(r);m=log2(n);a=0;if fix(m)-m==0;for c=hadamard(n);a=a+all(r==c');end;end

```

This is using a new approach: The allowed OVSF codes of length `N` appear in the `log2(N)`-th Walsh-matrix, as they are basically defined by the same recursion:

Walsh matrices are special cases of the Hadamard-matrices of size `N x N` if `N` is a power of two. (There are also Hadamard matrices of other sizes.) MATLAB and Octave have a variety of built in functions that generate test matrices to test properties of numerical algorithms, among them is `hadamard()`. Fortunately for powers of two MATLAB's `hadamard()` usex exactly the construction of the Welsh-matrices.

So this function first checks whether the inputs length is a power of two, and if it is, it checks whether it is a row of the corresponding size Welsh-matrix.

Try it online!
> 6 votes

# Answer
## Python, 64 bytes

```
f=lambda l:[]<l[1::2]==[x*l[1]for x in l[::2]]*f(l[::2])or[1]==l

```

Splits the list into even-indexed elements and odd-indexed elements via slices. Checks if the result vectors are either equals or negatives by multiplying one by the sign forced by its first element. Then, does the same recursive check on the even-indexed elements.

For the base case, if the check fails, rejects unless the list is `[1]`. The empty list is also specifically rejected to avoid an infinite loop.

A different strategy like my Haskell answer gives 66 bytes:

```
f=lambda l,i=1,s=[1]:l[i:]and f(l,i*2,s+[x*l[i]for x in s])or s==l

```
> 6 votes

# Answer
# \>\<\> (Fish), ~~431~~ 385 bytes

* -46 bytes by creating a new stack with l-2 elements so I can remove the `2-` from many places.

```
l[bb01.
>rl2=?vl3=?vl2%?vl2-2,[r0501.
      0v=1:<    0
< <  < <<       /
  1  0
   ?!^  v|.!]@{r/
 v&,2-2l<
 >&:?!v1-&l2-[l2,[{]rl2,[}]rl2,1+[{$:@$:@=?!v}]]
 l2-, ~v&,2-2lr                 .c1r8+eer]]}<
^    1<>&:?!v1-&l2-[l2,[{]rl2,[}]rl2,1+[{$:@$:@0$-=?!v}]]79.
^         1~<.a10r                       .c1ra+eer]]}<
n;
>&1+&v
     >&:?!v1-&l4-2,[}]l4-[r]l4-2,[{]l4-[r]
       .r~<

```

Try it

This took me wayyyy to long. Checking if 2 lists are equal is a pain in \>\<\>

This code loops to check if 2 lists are equal:

```
l2-[l2,[{]rl2,[}]rl2,1+[{$:@$:@=?!v}]]

```

Basically, what we do is:

* `l` gets the length of the stack
* `l-2` is the total length of both lists. So you see `l2-` all over.
* `(l-2)/2` is the length of one list, so you see `l2-2,` all over too.
* `l2-2,[{]` moves the top list to a new stack, shifts it left, then pushes it back to the old list. This means a new value is the top one.
* To shift the other list, it's a bit more complex. Since there is no command to push the bottom of the stack to a new list. We use `l2-[3]l2-2,[}]l2-[r]`. Reverse both lists, then shift the top half right, then reverse both lists together again.
* Now we need to check if the top of both lists are equal. We now take `(l-2)/2+1` elements, so the entire top list but 1 of the bottom list. Then we shift left to 1 item from the bottom list to the top. Now we use the `$:@$:@` trick to compare them. In either case we need to shift the list back.

this is copied twice. There is also this:

```
>&1+&v
     >&:?!v1-&l4-2,[{]l4-[r]l4-2,[{]l4-[r]
       .r~<

```

Which resets the list after the checking process, only needed if the process was aborted halfway though (they where not equal)
> 5 votes

# Answer
## JavaScript (ES6), ~~85~~ 61 bytes

```
a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>e==a[j=i&-i]*a[i-j])

```

Previous version which checked elements to ensure that they were `1` or `-1`:

```
a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>i?(j=i&-i)<i?e==a[j]*a[i-j]:e==1|e==-1:e==1)

```

Explanation:

* The length cannot be zero
* The length must be a power of 2
* The first element must be 1
* Elements in positions that are a power of 2 must be either 1 or -1
* Elements in other positions are the product of all the elements in the positions corresponding to the bitmask, e.g. `a[22] == a[2] * a[4] * a[16]`. Since `a[20] == a[4] * a[16]` has already been checked, only `a[22] == a[2] * a[20]` needs to be checked.
* The above check gives degenerate results for `i` not having at least two bits set. In the case of zero bits set, it checks that `a[0] == a[0] * a[0]`, which is false for `a[0] == -1`, while in the case of one bit set, it checks that `a[i] == a[0] * a[i]`.
> 3 votes

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

Translation of Jonah's solution.

```
{~^*((#1_2\#x){(x,x),'x,-x}/,1)?x}

```

Try it online!
> 3 votes

# Answer
# Haskell, ~~106 91 87~~ 86 bytes

```
g n|n<1=[[1]]|m<-g(n-1)=foldl(\a b->[b++map(0-)b,b++b]++a)[]m++m
f l=elem l$g$length l

```

The function `g` generates the `n` iteration of lists (relatively inefficiently, since `length $ g n == 3^n`, however if we'd delete the duplicates, we'd get `2^n`), `f` checks if our list is in any one of them. Thanks to @Zgrab for a few hints!

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), ~~130~~ ~~93~~ ~~87~~ ~~85~~ 83 bytes

```
f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b))

```

## Demo

```
f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b)),[[],[1],[-1],[1,1],[1,-1],[1,1,1,1],[1,1,1,1,1],[1,-1,-1,1,-1,1,1,-1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,-1,-1,-1,-1]].map(a=>console.log(`[${a}] -> ${!!f(a)}`))
```
> 2 votes

# Answer
# APL, 46 bytes

```
{0::0⋄⍵≡,1:1⋄⍬≡⍵:0⋄(∇Z↑⍵)∧(∇Y)∨∇-Y←⍵↓⍨Z←.5×⍴⍵}

```

Fairly straightforward:

* Base cases:
    + `0::0`: if an error occurs, return 0
    + `⍵≡,1:1`: if the input is exactly `[1]`, return 1
    + `⍬≡⍵:0`: if the input is the empty list, return 0
* Recursive case:
    + `Z←.5×⍴⍵`: `Z` is half the length of the input
    + `Y←⍵↓⍨Z`: `Y` is the last half of the input (this fails if `⍴⍵` is uneven, triggering the exception handler)
    + `(∇Y)∨∇-Y`: either the last half of the list, or the negation of the last half of the list, must be an OVSF code
    + `(∇Z↑⍵)∧`: and the first half of the list must be an OVSF code.
> 2 votes

# Answer
# MATL, ~~21~~ 20 bytes

```
`2eZ}yy=&=tn1>hh]1X=

```

Try it online! Or verify all test cases.

### How it works

The code splits the array into two equal-length pieces: the first with the odd-indexed entries, the second with the even-indexed entries. The two pieces are forced to have equal length, with a padding zero in the second if needed. Then the code checks that

1. The corresponding entries of the two pieces are either all equal or all different;
2. No entry in the second piece is zero;
3. The length of the pieces exceeds 1.

If these three conditions are met, the process is applied again on the first piece. If the loop is exited because the length was already 1, the input is an OFSV code. Else it is not.

Condition 1 iterated is an equivalent version of the defining property of OVSF codes. For an array of say length 8, the straightforward approach would be to check that entries 1,2,3,4 are all equal or all different to entries 5,6,7,8 respectively (this is the defining property). But we can equivalently check that entries 1,3,5,7 are all equal or all different to entries 2,4,6,8 respectively; and this turns out to use fewer bytes.

Condition 2 makes sure that the input length is a power of 2: if it's not, a padding zero will be introduced at some stage.

```
`        % Do...while loop
  2e     %   Reshape as a two-row matrix, with a padding zero if needed
         %   Row 1 contains the original odd-indexed entries, row 2 the
         %   even-indexed
  Z}     %   Split matrix into two vectors, one corresponding to each row
  yy     %   Duplicate those two vectors
  =      %   Check if corresponding entries are equal or not
  &=     %   Matrix of all pairwise comparisons. This will give a matrix
         %   filled with ones if and only if the previous check gave all
         %   true or all false (condition 1)
  tn1>   %   Duplicate and push true if size exceeds 1, or false otherwise
         %   (condition 3)
  hh     %   Concatenate condition 1, condition 3, and the original copy of
         %   the second piece (condition 2). The resulting vector is truthy
         %   if and only if it doesn't contain any zero
]        % End
1X=      % True if top of the stack is a single 1, false otherwise

```
> 2 votes

# Answer
# Haskell, 66 bytes

Yay, infinite lists!

```
o=[1]:(o>>= \x->[x++map(0-)x,x++x])
f l=l`elem`take(2*2^length l)o

```

Alternative versions:

```
o=[1]:(o<**>map(>>=flip(++))[map(0-),id])
f=Data.List.Ordered.hasBy(comparing length)o

```
> 2 votes

# Answer
# , 31 bytes

```
e.,.@1(],.~,],.-)^:[~0>.2<.@^.#

```

Try it online!

We build everything and check if the input is a member.

* `0>.2<.@^.#` Tells us how many iterations to build: Base 2 log of the length of the list. This will be the exact number of iterations for truthy cases. To handle non-power-of-2 lengths, we take the floor. To handle empty lists, we take the max with 0.
* `,.@1` Seed the iterations with a table containing just 1.
* `(],.~,],.-)` Build the next iteration per the definition: Input zipped with itself `,.~` catted with `,` the input zipped with its negative `],.-`.
* `e.` Is the input a member of that list?
> 2 votes

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

```
f:{$[2>#x;x~,1;{f[x]&|/x~/:-:\y}.2 0N#x]}

```

Try it online!
> 2 votes

# Answer
## Haskell, ~~69~~ 68 bytes

```
g x=any(elem x)$scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]]x

```

Usage example: `g [-1,1]` -\> `False`.

Even more inefficient than @flawr's answer. It takes too much time and memory for 4 element lists. To see that the list of OVSF codes (with a lot of duplicates) is actually created, try:

```
take 10 $ c $ scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]] [1..4]

```

which returns

```
[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1]]

```

i.e. the list starts with all 16 element lists (4 times concatenated, because of `[1..4]`), continues with all 8 element lists and so on until it ends with `[1]`.

Edit: @xnor saved a byte. Thanks!
> 1 votes

# Answer
# Python 2, ~~78~~ 75 bytes

```
def f(x):l=len(x)/2;return[n*x[l]*f(x[:l])for n in x[l:]]==x[:l]>[]or[1]==x

```

Try it online!
> 1 votes

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

```
{$[x~,1;1;(1=#?x*|x)&c=2*(d:-2!c:#x);o(d#x);0]}

```

Try it online!
> 1 votes

# Answer
# Vyxal, 11 bytes

```
⁽y↔≬y*≈MA=h

```

Try it online! or Test suite. Returns 1 for truthy and 0 for falsy.

## Explanation

Essentially compares the odd indices to even indices, then applying it again with even indices, until arriving with an empty list.

```
⁽y          # a lambda that returns the even indices only
  ↔         # apply to the input until empty, returning a new list containing
            #  the values each time it was applied. Includes the input
   ≬        # a lambda that:
    y       #  uninterleaves (pushes odd indices then even indices)
     *      #  multiplies (vectorises)
            #  - in the case that the length of the input is not a power of two,
            #    it pads a 0 to the shorter list
      ≈     #  then checks if all are equal
       M    # map to each element
        A   # check if all are truthy
         =  # is the number equal to the input? (vectorises)
            # - -1 is always 0
            # - 0 never appears in the input
            # - 1 is 1 if it satisfies OVSF code, otherwise 0
            # - an input of [] returns []
          h # get first element
            # - [] outputs 0
            # - [-1,...] outputs 0
            # - [1,...] outputs 1 if it is valid

```
> 1 votes

# Answer
# JavaScript (ES6), 80

```
f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

```

Recursively builds and check each list up to the length of the input list, starting with `[1]`.

Return value is JS truthy or falsey, specifically `1` or `true` if valid, `0` or `false` or `undefined` if not valid.

**Test**

```
f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

test=`[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True`
.split('\n')

test.forEach(r=>{
  input = r.match(/-?1/g)||[]
  check = r.slice(-4) == 'True'
  result = f(input)
  console.log(result, check, '['+input+']')
})
```
> 0 votes

# Answer
## Clojure, 118 bytes

```
(defn f[C](or(=(count C)1)(let[l(/(count C)2)[a b](split-at l C)](and(> l 0)(=(count b)l)(apply =(map * a b))(f a)))))

```

Splits input `c` into two halves `a` and `b` and checks if their element-wise products are all identical. If so, checks that the first half is valid sequence.

This one is 142 bytes but I found it more interesting:

```
#((set(nth(iterate(fn[I](mapcat(fn[i][(concat i i)(concat i(map - i))])I))[[1][-1]])(loop[l(count %)i 0](if(< l 2)i(recur(/ l 2)(inc i))))))%)

```

`loop` calculates `log_2` of input's length, `iterate` generates sequences of that many iterations based on the definition. This returns the input argument if it is a valid sequence and `nil` otherwise.
> 0 votes

# Answer
# Rust, 150 bytes

```
|m|f(m,1);fn f(k:&[i8],u:i8)->bool{let m=k.len()/2;k!=&[]&&(k==&[u]||f(&k[..m],u)&&(&k[..m]==&k[m..]||(f(&k[m..],-u)&&(0..m).all(|i|k[i]==-k[i+m]))))}

```

Attempt This Online!
> 0 votes

# Answer
# Prolog (SWI), ~~96~~ 75 bytes

```
+[1].
+L:-append(A,B,L),A\=[],(A=B;A-B),+A.
[]-[].
[A|B]-[C|D]:-C is-A,B-D.

```

Try it online!

*-15 bytes thanks to Steffan!*
> 0 votes

# Answer
# Haskell, ~~85~~ 82 bytes

*-3 bytes thanks to @Laikoni*

```
f[x]=x<0
f x|n<-length x`div`2,y<-take n x,z<-drop n x=n<1||y/=z&&y/=map(0-)z||f y

```

Try it online!

Not too short but efficient.
> 0 votes

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


title: Intermediate Boolean Algebra Calculator

text:
# Question
Title: Intermediate Boolean Algebra Calculator
## Background

With the success of Simple Boolean Algebra Calculator, I present a more difficult problem.

Boolean Algebra concerns representing values with letters and simplifying expressions. The following is a chart for the standard notation used:

Above is what actual boolean algebra looks like. For the purposes of this code golf, this is not the exact syntax that will be used.

## Your Task

Given a short boolean expression, return the solution to the expression.

There will be at most two values and one function involved in the calculator. The values may be any of 0, 1, or a capital letter(s). The functions may be /, +, or .

Any of the following may be an input: (values are demonstrated with X and Y in these examples.)

**One function, One value**

* There is only one possibility for this, which is /X. Return NOT X. If X is a variable, return /X, otherwise compute and output. This is the only scenario where /, the backslash, will be used.

**Two values**

* There is only one possibility for this, which is XY. Return X AND Y. If X and Y are different variables, return XY, otherwise compute and output. This is the only scenario where two values are next to each other.

**One value, One function, Another value**

* If you've done Simple Boolean Algebra Calculator, this is exactly the same except that it now must be able to output two variable calculations.
* Return the value for X (function) Y. If X and Y are different variables, output X (function) Y.
* (function), the second character in this scenario, will be either "+" or ".". If "+", treat as OR. If ".", treat as AND.

*Input: Either two characters or three characters.*

*Output: Either one character, two characters, or three characters.*

## Explained Examples

```
Input => Output
/0 => 1
/1 => 0
/P => /P

```

These expressions output the NOT value for the input. /P outputs /P because it cannot be simplified further.

```
Input => Output
0Q => 0

```

0Q evaluates to 0 because 0 AND Q will always be 0, regardless of what value Q takes.

```
Input => Output
Z1 => Z

```

Z1 evaluates to Z because the output for Z AND 1 depends entirely on the value of Z.

```
Input => Output
AH => AH (or A.H)

```

AH evaluates to AH because it cannot be simplified further. A.H is also a valid output.

```
Input => Output
A+1 => 1

```

A+1 evaluates to 1 because the OR statement is overridden by 1. That is, no matter what value A takes, the presence of 1 means that the statement will always evaluate to 1.

```
Input => Output
B+B => B

```

B+B evaluates to B because the OR statement is dependent on either Bs being true. If both Bs are false, then the output would also be false. So, the statement returns B since whatever value B takes, the output would return that.

```
Input => Output
W+L => W+L

```

W+L evaluates to W+L because it cannot be simplified further.

```
Input => Output
0.H => 0

```

0.H evaluates to 0 because the AND statement is overridden by 0. That is, no matter what value H takes, the presence of 0 means that the statement will always evaluate to 0.

```
Input => Output
1.1 => 1

```

1.1 evaluates 1 because the AND statement requires both inputs to be 1, and since they are both 1, 1 is returned.

```
Input => Output
G.L => G.L

```

G.L evaluates to G.L because it cannot be simplified further.

## Examples/Test cases

```
Input => Output

/0 => 1
/1 => 0
/P => /P

00 => 0
11 => 1
0Q => 0
Z1 => Z
NN => N
AH => AH (or A.H)

A+1 => 1
B+B => B
R+0 => R
1+1 => 1
0+0 => 0
A+B => A+B
Y+Z => Y+Z

0.0 => 0
Q.Q => Q
0.A => 0
1.C => C
1.1 => 1
R.S => R.S
N.W => N.W

```

This is , so shortest answer wins. Good luck.

# Answer
# JavaScript (ES6), 75 bytes

```
s=>([x,o,y]=s,y||(y=o,o=-1),x<'0')?1/y?y^1:s:x+1|y+1|x==y?~x&y!=0^o+1?x:y:s

```

Try it online!
> 1 votes

# Answer
# Retina 0.8.2, 62 bytes

```
0\+|\+0

/0|1\+.|.\+1
1
/1|.*0.*
0
1\.?(.)|(.)(\.?1|.?\2)
$1$2

```

Try it online! Link includes test cases. Explanation:

```
0\+|\+0

```

`0+X` and `X+0` become `X`.

```
/0|1\+.|.\+1
1

```

`/0`, `1+X` and `X+1` become `1`.

```
/1|.*0.*
0

```

`/1`, `0X`, `0.X`, `X0` and `X.0` become `0`. (This is tested after `/0` so that it doesn't erroneously match the `X0` rule and after `0+X` and `X+0` so that a simpler regex can be used that would otherwise erroneously match them.)

```
1\.?(.)|(.)(\.?1|.?\2)
$1$2

```

`1X`, `1.X`, `X1`, `X.1`, `XX`, `X.X` and `X+X` become `X`. (This is tested after `/1` so that it doesn't erroneously match the `X1` rule.)
> 0 votes

# Answer
# Charcoal, 36 bytes

```
¿№θ/¿‹⌈θAＩ¬Σθθ¿⁼²ＬΦα№θιθＦＩ№θ+¿№θιι⌈θ

```

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

```
¿№θ/

```

If the input contains a `/`, then:

```
¿‹⌈θA

```

If the input does not contain a letter, then...

```
Ｉ¬Σθ

```

... output the complement of the digit that it contains, otherwise...

```
θ

```

... output the input.

```
¿⁼²ＬΦα№θι

```

Otherwise, if the input contains two letters, then...

```
θ

```

... output the input, otherwise...

```
ＦＩ№θ+¿№θιι⌈θ

```

... solve the problem using the method from Simple Boolean Algebra Calculator.
> 0 votes

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


# Question
Title: Interstellar Cabbages, Wolves, and Sheep
The Cabbage, Wolf, Goat riddle with a twist!

### Backstory:

There’s an intergalactic river than needs to be crossed! Being a space-ferryman you’ve offered some aliens on your small space ferry that can only carry two entities: you and a passenger. However, you know that because politics, some of these aliens will instantly zap some other aliens if they are left at on a planet unsupervised. Supervision means **you** are watching them. (Once they go to the other side, they are no longer affiliated with you and you can just let them sort it out amongst themselves). Being an uneducated earthling, you have no way of knowing who will zap who until you meet them, and therefore you can’t plan who will ride your ship when. So, you decide to write a program that will instantly plan your route.

### Input:

Input can be taken in any way that makes sense. It will be a list of strings. The first character of the string will be a length 1 name of the alien. The second character of the string will be who the alien will zap. If there is no second character, the alien is at peace with everybody (unless it has been previously declared that somebody hates that alien).

Examples:

* `["WG", "GC"]` \- the original riddle.
* `["YB", "BU", "UJ", "YJ"]` \- the Yipiyuks zap the Bobles, the Bobles zap the Umpalumps, the Umpalumps zap the Jogos, and the Yipiyuks zap the Jogos.
* `["YB", "U"]` \- the Yipiyuks zap the Bobles, and the Umpalumps are just sitting there chilling.
* `["YB", "B"]` \- the Yipiyuks zap the Bobles, and even though the Bobles want to chill, they can’t.

### Output:

Output the solution to the puzzle. The first element of the list will be who goes on the first trip to the destination. The second element of the list (if necessary) is who will come back from the the destination. The third will be who goes to the destination on the second round, and so on. Redundant trips must be avoided (ie. the Yipiyuks go and then come back again.) If there is no solution, output something that is distinguishable from a solution. If there is more than one solution, output any solution as long as it is correct.

Examples:

* `["G", "", "W", "G", "C", "", "G"]` \- Solution to the original Cabbage Wolf Goat riddle. The Goat goes, and nobody goes back. The Wolf goes, and the Goat goes back. The Cabbage goes, and nobody goes back. And finally, the Goat is brought to the other side.
* `["Y"]` The Yipiyuks go to the other side, and nothing else happens.

### Test Cases

```
["WG", "GC"]       ->  ["G", "", "W", "G", "C", "", "G"]
["YB", "U"]        ->  ["Y", "", "U", "", "B"]
["YB", "B"]        ->  ["Y", "", "B"]
["YB", "BU", "YU"] ->  No Solution

```

This is , so shortest answer in bytes wins!

# Answer
# Python 3, 180 bytes

```
def f(l):
 X={''}.union(*l);B=X-X;n=1;q=S=L=[]
 while n or B:
  while~-len(B)and B in map(set,l)or(n,B)in S:n,B,L,*q=q
  for i in X-B:q=*q,1-n,X-B-{'',i},L+[i];S=*S,(n,B)
 return L

```

Try it online!

Raises an exception to indicate no solution.
> 4 votes

# Answer
# JavaScript (ES7), 187 bytes

Returns a string, where `,` means that there's no alien in the ship. Throws an error if there's no solution.

```
f=(a,N=0,s=new Set(','+a),M=2**s.size-1,g=(o,m)=>m^M?[...s].some((v,i,b)=>!o[N]&a.every(s=>~(m^m%2*M)&(h=n=>1<<b.indexOf(s[n]))(0)+h(1))&(m>>i^~m)&&g(o+v,m^1<<i^!!i)):O=o)=>g``?O:f(a,N+2)

```

Try it online!

## Commented

### Wrapper

```
f = (                   // f is a recursive function taking:
  a,                    //   a[] = input array
  N = 0,                //   N   = maximum number of rides - 1
  s = new Set(',' + a), //   s   = set of alien characters
                        //         + a leading comma for the pilot
  M = 2 ** s.size - 1,  //   M   = bit mask of passengers (pilot + aliens)
  g = ...               //   g   = main search function (detailed below)
) => g`` ? O            // if g() does not succeed,
         : f(a, N + 2)  // increase N until it does

```

### Search function

```
g = (                   // g is the main recursive search function taking:
  o,                    //   o = output string
  m                     //   m = bit mask of transferred passengers
) =>                    //       bit #0 is the pilot
m ^ M ?                 // if m is not equal to M:
  [...s]                //   turn s into an array
  .some((v, i, b) =>    //   for each character v at position i in b[]:
    !o[N] &             //     abort if we've reached the max. number of rides
    a.every(s =>        //     for each string s in a[]:
      ~(m ^ m % 2 * M)  //       take the 1's complement of either m or m XOR M
      &                 //       depending on the side of arrival
      ( h = n =>        //       h is a helper function that turns the 1st or
        1 <<            //       2nd character of s into a bit mask according
        b.indexOf(s[n]) //       to its position in b[] (2**31 if not found)
      )(0) + h(1)       //       if both antagonists are there, we have a *ZAP*
                        //       situation
    ) &                 //     end of every()
    (m >> i ^ ~m)       //     make sure the passenger is on the departure side
    &&                  //     if successful:
      g(                //       do a recursive call to g:
        o + v,          //         append v to the output string
        m ^ 1 << i      //         mark the passenger as transferred
        ^ !!i           //         unless the passenger is the pilot himself,
                        //         mark the pilot as transferred as well
      )                 //     end of recursive call
  )                     //   end of some
:                       // else:
  O = o                 //   success: save the solution in O

```
> 4 votes

---
Tags: code-golf, puzzle-solver
---


title: LS, Part 1: Ana Gram

text:
# Question
Title: LS, Part 1: Ana Gram
**Warning**: Wouldn't you rather answer a challenge about ponies?1

---

If you have read *The Hostile Hospital*, you would know that the Baudelaire orphans, from one of the scraps of paper recovered from the Quagmire's notebooks, they discover a name, "Ana Gram". Later on, they realize that means the word "anagram", not a name. And that information helps them in finding out who Count Olaf disguised Violet Baudelaire as (Laura V. Bleediotie). They have to search through the entire hospital list, but trace the correct person down. However, what if they lived in a time where YOU helped them? Not personally, but with a program?
So your task today is simple. Given a string `a` and an array, return a smaller array that contains all the possible anagrams of `a`.

## Rules:

* This is , so shortest answer wins
* Make sure to lowercase everything in the array and the string
* Two strings that are the same are not anagrams after normalizing
* Make sure to watch out for initials! You should also remove them
* There may be multiple possible anagrams. Output them all

## Test cases:

```
String, Array
-> Array

"Violet", ["Veilo","Efh", "Telvio","veliot"]
-> ["Telvio","veliot"]

"Krotasmon", ["Krotas Mon","Krota","Monsakrot", "Trokasmont","KROTASMON"]
-> ["Monsakrot"]

"Laura V. Bleediotie", ["Violet Baudelaire", "Violet. Baudelaire", "VIOLeT BAUDELAIRE", "BUADELIAR VIOLETM", "Laura V. Bleediotie"]
-> ["Violet Baudelaire", "Violet. Baudelaire", "VIOLeT BAUDELAIRE"]

```

1: Inspired by the "all rights reserved" page of LS: The Unauthorized Autobiography

# Answer
# Nibbles, 12 bytes (24 nibbles)

```
|@~`^+%;~$.|$\$a`($$_@;$

```

```
|                           # filter
 @                          # the second argment (=array of possible anagrams)
  ~                         # returning elements that are falsy for:
       ;~$                  #   apply and save the following function to each element:
           |$               #     filter each element
             \$a            #       to keep only alphabetic characters
          .                 #     and then map over each character
                `($         #       converting to lowercase
                   $_       #   apply the saved function to the first argument
      %                     #   split each normalized element
                            #     by the normalized first argment
     +                      #     and flatten
                            #     (this removes normalized identities)
   `^                       #   and then get the element-wise xor
                     @;$    #     with the normalized first argument
                            #     (so anagrams give empty list,
                            #     identities/non-anagrams give lists of all/different characters)

```

See the other test cases here
> 0 votes

# Answer
# Python, 106 bytes

*-12 by mousetail, Kevin Cruijssen*
*-5 by Jitse*

```
lambda w,l,S=sorted:[x for x in l if S(g(x))==S(g(w))!=g(w)!=g(x)]
g=lambda s:s.lower().translate(['']*96)

```

Attempt This Online!
> 5 votes

# Answer
# 05AB1E, 14 bytes

```
šl€áD€{ćQsćÊ*Ï

```

Inputs in the order `String, Array`.

Try it online or verify all test cases.

**Explanation:**

```
š         # Prepend the first (implicit) input to the second (implicit) input-list
 l        # Convert everything in the list to lowercase
  €á      # Only keep the letters of each string in the list
    D     # Duplicate this list
     €{   # Sort the characters of each string in the list
       ć  # Extract head; push the modified list and modified first input separated to
          # the stack
        Q # Check which modified strings in the list are equal to this modified input
    s     # Swap so the duplicated list is at the top again
     ć    # Extract its head as well
      Ê   # Check which partially-modified strings in the list are NOT equal to this
          # partially-modified input
    *     # Combine the checks at the same positions (vectorized multiply that acts as a
          # vectorized logical AND)
     Ï    # Only keep the strings from the second (implicit) input-list at the truthy
          # positions
          # (after which the filtered list is output implicitly as result)

```
> 2 votes

# Answer
# Charcoal, 37 bytes

```
≔Φ↧Ｓ№βιθＷＳ«≔Φ↧ι№βκη¿‹⁼ηθ⬤⁺ηθ⁼№ηκ№θκ⟦ι

```

Try it online! Link is to verbose version of code. Takes the array as a list of newline-terminated strings. Explanation:

```
≔Φ↧Ｓ№βιθ

```

Lower case the target anagram and only keep letters.

```
ＷＳ«

```

Loop through the array.

```
≔Φ↧ι№βκη

```

Lower case the current element and only keep letters.

¿‹⁼ηθ⬤⁺ηθ⁼№ηκ№θκ

If the strings do not equal and both strings contain equal counts of all the letters in both strings:

```
⟦ι

```

Output the current element on its own line.
> 1 votes

# Answer
# Jelly, 18 bytes

```
ŒlfØa,Ṣ$
Ç⁼"Ç}</ðƇ

```

A dyadic Link that accepts the list of potentials on the left and the identity on the right and yields the filtered list.

**Try it online!**

### How?

```
ŒlfØa,Ṣ$ - Helper Link: list of characters, Name
Œl       - lower case (Name)
   Øa    - "a-z"
  f      - (lowered Name) filter keep ("a-z")
       $ - last two links as a monad - f(X=that):
      Ṣ  -   sort (X)
     ,   -   (X) pair with (that)

Ç⁼"Ç}</ðƇ - Main Link: Potentials; Identity
        Ƈ - keep Potentials, P, for which:
       ð  -   dyadic chain - f(P, Identity):
Ç         -     call Helper with Name=P
   Ç}     -     call Helper with Name=Identity
  "       -     zip with:
 ⁼        -       equal?
      /   -     reduce by:
     <    -       less than?
                i.e. alphas(lowered(P)) == alphas(lowered(Identity))
                     less than?
                     sorted(alphas(lowered(P))) == sorted(alphas(lowered(Identity)))

```
> 1 votes

# Answer
# C (clang), ~~163~~ ~~155~~ ~~151~~ ~~134~~ ~~218~~ ~~193~~ ~~186~~ 169 bytes

-3 bytes thanks to ceilingcat!!

+84 bytes thanks to c--

-24 bytes thanks to c--

```
u[256];v[256];*w;q(*h,*j){bzero(h,512);for(w=h+128;*j;j++)*j>64&&h[*w++=32|*j]++;}f(**o,i){for(q(u,i);*o;o++)q(v,*o),bcmp(u,v,w-v<<2)*!bcmp(u,v,512)&&printf("%ls,",*o);}

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES10*), 105 bytes

** Not a strict requirement, but starting with ECMAScript 2019 (aka ES10), the .sort() method is guaranteed to be stable. This used to be left to the implementation.*

Expects `(string)(array)`.

```
s=>a=>a.filter(w=>(g=c=>(h=s=>[...s.toLowerCase().replace(/[^a-z]/g,'')].sort(c)+0)(w)==h(s))()&!g(_=>1))

```

Try it online!

### Commented

For each test, the helper function `g` is called twice: once to check that the normalized strings are equal when the letters are sorted, and once to check that they're different when no sort is applied.

```
s =>                    // s   = reference string
a =>                    // a[] = array of strings
a.filter(w =>           // for each string w in a[]:
  ( g = c =>            //   g is a helper function taking a callback c
    ( h = s =>          //     h is a helper function taking a string s
      [...              //       split into an array of characters:
        s.toLowerCase() //         convert s to lower case
        .replace(       //         remove ...
          /[^a-z]/g, '' //         ... all non-letter characters
        )               //
      ].sort(c)         //       sort the resulting array using the callback c
      + 0               //       add a final 0 to coerce to a string
    )(w) == h(s)        //     is the normalization of w equal to that of s?
  )()                   //   we first call g() with an undefined callback
  &                     //   so that the default lexicographical sort is used
  !g(_ => 1)            //   we then call g() with a callback that leaves the
                        //   arrays unchanged
)                       // end of filter()

```
> 0 votes

# Answer
# Ruby, 80 bytes

```
->s,a{g=->s{s.upcase.gsub(/[^A-Z]/,"").chars.sort}
a.select{s!=_1&&g[s]==g[_1]}}

```

Attempt This Online!
> 0 votes

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


title: Shortest Addition Chain

text:
# Question
Title: Shortest Addition Chain
An addition chain is a sequence of integers starting with 1, where every integer other than the initial 1 is a sum of two previous integers.

For instance, here's an addition chain:

```
[1, 2, 3, 4, 7, 8, 16, 32, 39, 71]

```

Here are the sums that make it an addition chain:

```
1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
3 + 4 = 7
1 + 7 = 8
8 + 8 = 16
16 + 16 = 32
7 + 32 = 39
32 + 39 = 71

```

In this challenge, you will be given a positive integer `n`, and you must output one of the shortest addition chains which ends in `n`.

Examples - note that there are many possible outputs, all that you are required to find is an addition chain that's just as short:

```
1: [1]
2: [1, 2]
3: [1, 2, 3]
4: [1, 2, 4]
5: [1, 2, 3, 5]
6: [1, 2, 3, 6]
7: [1, 2, 3, 4, 7]
11: [1, 2, 3, 4, 7, 11]
15: [1, 2, 3, 5, 10, 15]
19: [1, 2, 3, 4, 8, 11, 19]
29: [1, 2, 3, 4, 7, 11, 18, 29]
47: [1, 2, 3, 4, 7, 10, 20, 27, 47]
71: [1, 2, 3, 4, 7, 8, 16, 32, 39, 71]

```

Standard I/O rules, etc. Standard Loopholes banned. Code golf: Fewest bytes wins.

# Answer
# Pyth, 13 bytes

```
h-DsM^N2/#QyS

```

Test suite

Gives the lexicographically first shortest chain. It's fairly slow, but not that bad - `19` completes in about 30 seconds using pypy.

Some ideas from @Dennis's solution.

I really like this one - there are a ton of neat tricks involved.

**Explanation:**

```
h-DsM^N2/#QyS
h-DsM^N2/#QySQ    Implicit variable introduction
            SQ    Inclusive range, 1 to input.
           y      Subsets - all subsets of the input, sorted by length then lexicographically
                  Only sorted subsets will be generated.
                  Our addition chain will be one of these.
        /#Q       Filter for presence of the input.
  D               Order by
 -                What's left after we remove
     ^N2          All pairs of numbers in the input
   sM             Summed
h                 Output the list that got sorted to the front.

```

This is still a bit hard to understand, but let me try to explain in a bit more detail.

We start with `ySQ`, which gives all possible ordered subsets of `[1, 2, ... Q]`, in increasing order of size. The shortest addition chain is definitely one of these, but we need to find it.

The first thing we'll do is filter the list to only keep lists that contain a `Q`. We do this with `/#Q`.

Next, we order the list by what's left after we remove the result of a certain function. `-D` orders by the remainder after removing something.

The thing we remove is `sM^N2`, where `N` is the list we're removing things from. `^N2` gives the cartesian product of `N` with itself, all possible pairs of two elements in `N`. `sM` then sums each of the pairs.

What's the smallest possible result, after we do this removal? Well, the smallest element in the input list definitely will remain, because all the numbers are positive, so any sum of two numbers will be greater than the smallest number. And there will be at least one number, because we checked that the input was present in the list. Therefore, the smallest possible result will be when every number except the smallest number is the sum of two other numbers in the list, and the smallest number in the list is 1. In this case, the sorting key will be `[1]`. These requirements mean that the list must be an addition chain.

So, we sort the addition chains to the front. Remember that `y` gives its subsets in increasing order of size, so the list which is sorted to the front must be one of the shortest addition chains. `h` selects that list.
> 1 votes

# Answer
## Haskell, 57 bytes

```
c=[1]:[x++[a+b]|x<-c,a<-x,b<-x]
f n=[x|x<-c,last x==n]!!0

```

A brute force solution. Try it online!

## Explanation

The infinite list `c` contains all addition chains, ordered by length. It is defined inductively in terms of itself, by taking a list `x` from `c` and two elements from `x`, and appending their sum to `x`. The function `f` finds the first list in `c` that ends with the desired number.

```
c=            -- c is the list of lists
 [1]:         -- containing [1] and
 [x           -- each list x
  ++[a+b]     -- extended with a+b
 |x<-c,       -- where x is drawn from c,
  a<-x,       -- a is drawn from x and
  b<-x]       -- b is drawn from x.
f n=          -- f on input n is:
 [x           -- take list of those lists x
 |x<-c,       -- where x is drawn from c and
  last x==n]  -- x ends with n,
 !!0          -- return its first element.

```
> 7 votes

# Answer
# Brachylog, 14 bytes

```
∧≜;1{j⊇Ċ+}ᵃ⁽?∋

```

Try it online!

A brute-force submission that builds all possible addition chains using iterative deepening, stopping when a chain containing its right argument is found. Unlike most Brachylog submissions, this is a function submission that inputs via its right argument (conventionally called the Output) and outputs via its left argument (conventionally called the Input); doing this is somewhat controversial, but the highest-voted meta answer on the subject says it's legal (and doing so is consistent with our normal I/O defaults for functions). If we used the input and output in a more conventional way, this would be 16 bytes (`∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧`), because the right-hand side of the program would not be able to make use of the implicit constraint (thus would need that disabled, and a new explicit constraint given, at a cost of 2 bytes).

## Explanation

```
∧≜;1{j⊇Ċ+}ᵃ⁽?∋
∧               Disable implicit constraint to read the left argument
 ≜;        ⁽    Evaluation order hint: minimize number of iterations
    {    }ᵃ     Repeatedly run the following:
   1      ᵃ       From {1 on the first iteration, results seen so far otherwise}
     j            Make {two} copies of each list element
      ⊇           Find a subset of the elements
       Ċ          which has size 2
        +         and which sums to {the new result for the next iteration}
             ∋    If the list of results seen so far contains {the right argument}
            ?     Output it via the left argument {then terminate}

```

An interesting subtlety here is what happens on the first iteration, where the input is a number rather than a list like on the other iterations; we start with the number 1, make two copies of every digit (making the number 11), then find a 2-digit subsequence of it (also the number 11). Then we take its digit sum, which is 2, and as such the sequence starts `[1,2]` like we want. On future iterations, we're starting with a list like `[1,2]`, doubling it to `[1,2,1,2]`, then taking a two-element subsequence (`[1,1]`, `[1,2]`, `[2,1]`, or `[2,2]`); clearly, the sums of each of these will be valid next elements of the addition chain.

It's a little frustrating here that the evaluation order hint is needed here, especially the  component (it appears that  takes its evaluation order hint from *inside* rather than outside by default, thus the rather crude use of  in order to force the issue).
> 5 votes

# Answer
# Jelly, 17 bytes

```
’ŒP;€µ+þ;1Fḟ@µÐḟḢ

```

Outputs the lexicographically first solution in exponential time.

Try it online!

### How it works

```
’ŒP;€µ+þ;1Fḟ@µÐḟḢ  Main link. Argument: n (integer)

’                  Decrement; n-1.
 ŒP                Powerset; generate all subarrays of [1, ..., n-1], sorted first
                   by length, then lexicographically.
   ;€              Append n to all generate subarrays.
     µ       µÐḟ   Filterfalse; keep only subarrays for which the chain between the
                   two chain separators (µ) returns a falsy value.
     µ             Monadic chain. Argument: A (array of integers)
      +þ               Add table; compute the sums of all pairs of elements in x,
                       grouping the results by the right addend.
        ;1             Append 1 to the resulting 2D array.
          F            Flatten the result.
           ḟ@          Filterfalse swapped; remove all elements of A that appear in
                       the result. This yields an empty list for addition chains.
                Ḣ  Head; select the first result.

```
> 3 votes

# Answer
# PHP, 195 Bytes

```
function p($a){global$argn,$r;if(!$r||$a<$r)if(end($a)==$argn)$r=$a;else foreach($a as$x)foreach($a as$y)in_array($w=$x+$y,$a)||$w>$argn||$w<=max($a)?:p(array_merge($a,[$w]));}p([1]);print_r($r);

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), ~~83~~ 86 bytes

*Edit: fixed to output the list in non-reverse order*

```
n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

```

### Demo

```
let f =

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

for(n = 1; n <= 15; n++) {
  console.log(n, '-->', JSON.stringify(f(n)));
}
```
> 2 votes

# Answer
# Mathematica, 140 bytes

```
t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

```

.

produces a different shortest addition chain everytime you run it

Try it online
paste the code with ctrl+v, place input i.e \[71\] at the end of the code and press shift+enter
> 1 votes

# Answer
# Python 3, 102 bytes

```
f=lambda n,s={(1,)}:next((p for p in s if n in p),0)or f(n,{p+(i+j,)for p in s for i in p for j in p})

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence, arithmetic
---


title: How many pages have I torn out?

text:
# Question
Title: How many pages have I torn out?
Last month I borrowed a plenty of books from the library. They all were good books, packed with emotions and plot-twists. Unfortunately, at some points I got very angry/sad/disappointed, so I tore some pages out.

Now the library wants to know how many pages I have torn out for each book.

Your goal is to write a program, which takes a sorted, comma-delimited list of numbers as input and prints the minimum and maximum possible page count I could have torn out. Each line represents a book, each number represents a missing page from the book.

Example input:

```
7,8,100,101,222,223
2,3,88,89,90,103,177
2,3,6,7,10,11
1
1,2

```

Example output:

```
4/5
5/6
3/6
1/1
1/2

```

`4/5` means, that I may have torn out either 4 or 5 pages, depending on which side the book's page numbering starts. One could have torn out page 6/7, page 8/9, page 100/101, and page 222/223 (4 pages). Alternatively, one could have torn out page 7/8, page 99/100, page 101/102, page 221/222, and page 223/224 (5 pages).

Remember that a book page always has a front and a back side. Also the page numbering differs from book to book. Some books have even page numbers on the left page; some on the right page. All books are read from left to right.

Shortest code in bytes win. Strict I/O format is **not** required. Your programs must be able to take one or more books as input. Have fun.

# Answer
# 05AB1E, 13 bytes

```
εD>)ÅÈε€θγg}{

```

Try it online!

Thanks to Emigna for the heads-up on spec changes.

### Explanation

```
εD>)ÅÈε€θγg}{ – Full program.
ε             – For each book...
 D            – Push two copies of it.
  >           – Increment all the elements of the second copy.
   )          – Wrap the whole stack into a list.
    ÅÈ        – Produces the lists of even natural numbers lower or equal to each element.
      ε       – For each (the modified copies of the book):
       €θ     – Get the last item of each.
         γg   – And split into chunks of equal adjacent elements.
           }  – Close the loop.
            { – Sort the resulting list.

```
> 6 votes

# Answer
# Python 2, ~~72~~ ~~56~~ ~~68~~ 67 bytes

```
lambda b:[map(len,map(set,zip(*[[p/2,-p/2]for p in t])))for t in b]

```

Try it online!
> 4 votes

# Answer
# JavaScript, ~~104~~ ~~93~~ ~~92~~ ~~85~~ ~~80~~ ~~79~~ 74 bytes

Would be 57 bytes if not for the unnecessary (in my opinion) requirement that each pair of numbers in the output be consistently sorted, or 47 bytes if we only needed to take one book as input.

Input and output are both an array of arrays.

```
a=>a.map(x=>[0,1].map(n=>new Set(x.map(y=>y+n>>1)).size).sort((x,y)=>x-y))

```
* Initially inspired by Olivier's Java solution and my own (currently deleted) Japt solution.
* 2 bytes saved thanks to Arnauld (plus another 3 we both spotted at the same time) and 10 bytes *added* thanks to him spotting the broken sorting I'd hoped nobody would notice while that requirement was still under discussion!

---

## Test cases

Test cases are split into individual books for better readability with the last case (which includes the `[1,2]` edge case) serving to illustrate that this solution supports multiple books in the input.

```
f=
a=>a.map(x=>[0,1].map(n=>new Set(x.map(y=>y+n>>1)).size).sort((x,y)=>x-y))
o.innerText=` Input                         | Output\n${`-`.repeat(31)}|${`-`.repeat(21)}\n`+[[[7,8,100,101,222,223]],[[2,3,88,89,90,103,177]],[[2,3,6,7,10,11]],[[1,3,5,7,9,11,13,15,17,18]],[[1],[1,2],[8,10]]].map(b=>` `+JSON.stringify(b).padEnd(30)+"| "+JSON.stringify(f(b))).join`\n`
```

```
<pre id=o></pre>
```

---

## History

```
//104
a=>a.map(x=>x.map(y=>b.add(y/2|0)&c.add(++y/2|0),b=new Set,c=new Set)&&[b.size,c.size].sort((x,y)=>x-y)))
// 93
a=>a.map(x=>[new Set(x.map(y=>y/2|0)).size,new Set(x.map(y=>++y/2|0)).size].sort((x,y)=>x-y)))
// 92
a=>a.map(x=>[(g=z=>new Set(z).size)(x.map(y=>y/2|0)),g(x.map(y=>++y/2|0))].sort((x,y)=>x-y))
// 85
a=>a.map(x=>[(g=h=>new Set(x.map(h)).size)(y=>y/2|0),g(y=>++y/2|0)].sort((x,y)=>x-y))
// 80
a=>a.map(x=>[(g=n=>new Set(x.map(y=>(y+n)/2|0)).size)(0),g(1)].sort((x,y)=>x-y))
// 79
a=>a.map(x=>[(g=n=>new Set(x.map(y=>y/2+n|0)).size)(0),g(.5)].sort((x,y)=>x-y))
// 76
a=>a.map(x=>[0,.5].map(n=>new Set(x.map(y=>y/2+n|0)).size).sort((x,y)=>x-y))
```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 37 bytes

Thanks @MartinEnder for 8 bytes!

```
Sort[Length@*Split/@{#,#+1}~Floor~2]&

```

Try it online!

### Explanation

In: `{3, 4, 5}`

```
{#,#+1}

```

Take (input) and (input + 1). `{{3, 4, 5}, {4, 5, 6}}`

```
... ~Floor~2

```

For each number from above, take the largest even number less it. `{{2, 4, 4}, {4, 4, 6}}`

```
Length@*Split/@

```

For each list from above, split the list by same elements `{{{2}, {4, 4}}, {{4, 4}, {6}}}`

and take the length of each: `{2, 2}`

```
Sort[ ... ]

```

Sort the output.
> 2 votes

# Answer
# Perl 5, 95 + 1 (`-a`) = 96 bytes

```
@0=@1=0;map{$i=-1;$F[$i]+1==$F[$i+1]&&$F[$i]%2==$_&&$i++while++$i<@F&&++@{$_}[0]}0,1;say"@0/@1"

```

Try it online!
> 2 votes

# Answer
# Retina 0.8.2, 60 bytes

```
\d+
$*
.+
$&,/$&,
,(?=.*/)
1,
((11)+,)1\1|1+,
1
%O`1+
1+
$.&

```

Try it online! Explanation:

```
\d+
$*

```

Convert the page numbers to unary.

```
.+
$&,/$&,

```

Duplicate the list, interposing a `/`.

```
,(?=.*/)
1,

```

Increment the page numbers in one copy of the list.

```
((11)+,)1\1|1+,
1

```

Count the number of pages, but consecutive even and odd numbers only counts as one page.

```
%O`1+

```

Sort the counts into order.

```
1+
$.&

```

Convert the counts back to decimal.
> 2 votes

# Answer
# Haskell, 62 bytes

```
import Data.List
p t=sort[length$nub[div(p+o)2|p<-t]|o<-[0,1]]

```

Try it online!
> 2 votes

# Answer
# Java (OpenJDK 9), 163 bytes

```
import java.util.*;
n->{for(int i=n.length;i-->0;){Set s=new HashSet(),t=new HashSet();for(int p:n[i]){s.add(p/2);t.add(++p/2);}n[i]=new int[]{s.size(),t.size()};}}

```

Try it online!

## Explanations

```
n->{                                   // Input-output of int[][]
 for(int i=n.length;i-->0;){           // Iterate on books
  Set s=new HashSet(),t=new HashSet(); // Create two hashsets
  for (int p:n[i]) {                   // Iterate over each page
   s.add(p/2);                         // Add the sheet-of-page of books [ even | odd ] to one set.
   t.add(++p/2);                       // Add the sheet-of-page of books [ odd | even ] to the other set.
  }
  n[i]=new int[] {                     // change the input to the number of sheets used.
   s.size(),
   t.size()
  };
 }
}

```

Note: since there is no requirement about it, the min and max numbers of pages aren't ordered.
> 2 votes

# Answer
# APL (Dyalog Unicode), 37 bytes

```
{(≢⍵)≤2:⌽≢∘∪¨⌊⍵(1+⍵)÷2⋄≢∘∪¨⌊⍵(1+⍵)÷2}

```

Try it online!

This can be done for less than half the byte count if the output order of pages doesn't matter:

```
{≢∘∪¨⌊⍵(1+⍵)÷2}

```

### How?

```
{(≢⍵)≤2:⌽≢∘∪¨⌊⍵(1+⍵)÷2⋄≢∘∪¨⌊⍵(1+⍵)÷2}⍝ Prefix dfn
{(≢⍵)≤2:                               ⍝ If argument length ≤2
                    ÷2                 ⍝ Divide by 2
              ⍵(1+⍵)                   ⍝ Both the argument and 1+argument
             ⌊                         ⍝ Round down to the nearest integer
           ∪¨                          ⍝ Get the unique values of each
          ∘                            ⍝ And then
         ≢                             ⍝ Get the tally of elements of each
        ⌽                              ⍝ And reverse the result
                      ⋄                ⍝ Else
                       ≢∘∪¨⌊⍵(1+⍵)÷2} ⍝ Same as above, without reverting the result.

```
> 2 votes

# Answer
# Clean, ~~222~~ ~~210~~ ~~204~~ 196 bytes

```
import StdEnv,ArgEnv,Data.Maybe,qualified GenLib as G
Start=tl[let(Just l)='G'.parseString i;?s=sum[1\\n<-[s,s+2..last(sort l)]|isAnyMember[n,n+1]l]in zip2(sort[?0,?1])['/\n']\\i<-:getCommandLine]

```

Try it online!

Full-program requirements absolutely murder Clean's ability to compete.

For those who have been paying attention to my answers in Clean, you'll notice `import qualified`, which is an ugly hack to get around using modules that shouldn't be used together, together - which is only needed here because of another ugly hack to do with `GenLib` depending on `Data.Maybe` instead of `StdMaybe`, which is the result of *yet another* ugly hack in the libraries translated from Haskell's `Data` to get functionality before Clean's own libraries are equally complete.

Takes input via command-line arguments.
> 1 votes

# Answer
# Vyxal, 9 bytes

```
½₍⌈⌊vUvLs

```

Try it Online!

Append a `\/j` for strict I/O compliance (12 bytes)

```
½         # Halve each
 ₍⌈⌊      # Floor and ceiling of each, paired
    vUvL  # Count unique items in each
        s # Sort

```
> 1 votes

# Answer
# Perl, 40 bytes

Inludes `+1` for `a`

```
perl -aE 'say/$/*grep${$.}{$_*$`|1}^=1,@F for-1,1' <<< "7 8 100 101 222 223"

```

Output is not ordered.

Assumes positive page numbers (especially no page `0`). Assumes missing pages are only mentioned once. Doesn't care if the input is ordered or not.

Processing only one book per run saves `3` bytes for `37`:

```
perl -aE 'say/$/*grep$z{$_*$`|1}^=1,@F for-1,1' <<< "7 8 100 101 222 223"

```
> 0 votes

---
Tags: code-golf
---


title: Making Squared Words

text:
# Question
Title: Making Squared Words
**The Challenge**

Your task is to create a program that takes any given string input, and outputs the input in a squared format. Empty strings should return an empty string.

**Examples**

Given the input:

```
golf

```

Your program should output:

```
golf
o  l
l  o
flog

```

Input:

```
123

```

Output:

```
123
2 2
321

```

Input:

```
a

```

Output:

```
a

```

Input:

```
Hello, world!

```

Output (notice the space between the , and w - the gap is not just a newline):

```
Hello, world!
e           d
l           l
l           r
o           o
,           w

w           ,
o           o
r           l
l           l
d           e
!dlrow ,olleH

```

**Scoring**

This is , so the shortest answer in each language wins.

# Answer
> 20 votes
# Charcoal, ~~7~~ 5 bytes

```
θ‖Ｏ↙↘

```

Try it online! Link is to verbose version of code. Edit: Saved 2 bytes thanks to @CarlosAlejo. Explanation:

```
θ       Print the input string, making the top row
 ‖Ｏ     Reflect with overlap...
   ↙    ... down and left, to create the left side
    ↘   ... down and right, to create the bottom and right sides

```

(Multiple directions to the Reflect command run consecutively rather than simultaneously.)

# Answer
> 11 votes
# MATL, ~~20~~ ~~16~~ 11 bytes

```
otYTO6Lt&(c

```

Try it at **MATL online!**

*EDIT: The code works in release 20.2.1, which predates the challenge. The link uses that release. (In 20.2.2 the code would be shorter, but it postdates the challenge).*

### Explanation

```
o     % Implicitly input a string. Convert chars to ASCII codes
t     % Duplicate
YT    % 2-input Toeplitz matrix
O     % Push 0
6L    % Push predefined literal [2, -1+1j]. When used as an index, this is
      % interpreted as 2:end-1 (indexing is 1-based)
t     % Duplicate
&(    % 4-input assignment indexing. This writes 0 at the square formed by
      % rows 2:end-1 and columns 2:end-1
c     % Convert to char. Char 0 is shown as space. Implicitly display

```

# Answer
> 6 votes
# Jelly,  ~~29 22~~  17 bytes

*Charcoal ~~will~~ trounce+d this score...*

```
J⁶ẋa0,1¦"ṚṚ;$ṖŒḌY

```

A monadic link taking and returning a lists of characters; or a full program printing the result.

**Try it online!**

### How?

```
J⁶ẋa0,1¦"ṚṚ;$ṖŒḌY - Link: list of characters, w     e.g. "whole"
 ⁶                - literal space character              ' '
J                 - range(length(w))                     [1,2,3,4,5]
  ẋ               - repeat                               [" ","  ","   ","    ","     "]
         Ṛ        - reverse w                            "elohw"
        "         - zip with:
       ¦          -   sparse application of:
   a              -     and (vectorises)
    0,1           -     to indexes: [0,1] (last and 1st) ["e","ll","o o","h  h","w   w"]
            $     - last two links as a monad:
          Ṛ       -   reverse                            ["w   w","h  h","o o","ll","e"]
           ;      -   concatenate                        ["w   w","h  h","o o","ll","e","e","ll","o o","h  h","w   w"]
             Ṗ    - pop (remove last entry)              ["w   w","h  h","o o","ll","e","e","ll","o o","h  h"]
              ŒḌ  - reconstruct matrix from diagonals    ["whole","h   l","o   o","l   h","elohw"]
                Y - join with newlines                   "whole\nh   l\no   o\nl   h\nelohw"
                  - if running as a full program implicit print

```

# Answer
> 3 votes
# Haskell, ~~84~~ 78 bytes

```
f s@(_:x)|_:y<-r x=s:[a:(y>>" ")++[b]|(a,b)<-zip x y]++[r s];f s=[s]
r=reverse

```

Try it online! Usage: `f "test"`. Returns a list of lines.

**Edit:** -6 bytes thanks to dianne!

# Answer
> 3 votes
## C, 109 bytes

```
i,j;f(char*s){for(i=j=printf("%s\n",s)-2;1[++s];)printf("%c%*c\n",*s,i,s[j-=2]);for(;*s*~i--;)putchar(*s--);}

```

Try it online!

Noteworthy tricks:

* Instead of wasting bytes on `strlen`, we simply grab the length of the string while simultaneously printing the first line:

```
i=j=printf("%s\n",s)-2

```

This works because `printf` returns the number of bytes written.
* For the middle lines, we need to loop over the string but exclude both the first and last character. This is achieved with the condition

```
1[++s]

```

(which is shorter than `(++s)[1]`), which skips the first character due to the `++`'s being in the condition and skips the last one by stopping when the character past the current character is `'\0'` (rather than stopping *at* `'\0'`).
* In the body of the first loop,

```
printf("%c%*c\n",*s,i,s[j-=2])

```

we print the current character, then the appropriate "mirrored" character (keeping track with `j`, which does go into the negatives, resulting in the odd situation of indexing into a string with a negative number) padded to a length of `i` with spaces (where `i` is conveniently `strlen(s) - 1`).
* The reversed printing on the last line is pretty straightforward; the only trick is the `*s*~i--`, which is the shortest way to get `i+2` iterations of the loop body (which doesn't depend on `i`; all `i` is used for is to count). The funky `*s*` part makes sure the loop doesn't run if `*s` is `'\0'`, which happens on length-1 input.

# Answer
> 3 votes
# Octave, 40 bytes

```
@(s,t=toeplitz(s),u=t(x=2:end-1,x)=32)t;

```

Try it online!

It is my answer but posted after @Luis MATL answer

# Answer
> 2 votes
# Python 2, ~~89~~ ~~81~~ ~~88~~ 86 bytes

```
i=input();n=k=len(i)-2
print i
exec'print i[~k]+" "*n+i[k];k-=1;'*n
if~k:print i[::-1]

```

Try it online!

# Answer
> 2 votes
# , 113 bytes

```
function(s){n=length(s<-strsplit(s,'')[[1]])
m=matrix(' ',n,n)
m[n,n:1]=m[,1]=m[1,]=m[n:1,n]=s
write(m,'',n,,'')}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~17~~ ~~16~~ ~~15~~ 19 bytes

```
ÂDÂø¦¨Dgú€Ás)˜»Igi¨

```

Try it online!

**Explanation**

Example with `input = golf`

```
ÂDÂ                  # bifurcate, duplicate, bifurcate
                     # STACK: 'golf', 'flog', 'flog', 'golf'
   ø                 # zip the top 2 items
                     # STACK: 'golf', 'flog', ['fg', 'lo', 'ol', 'gf']
    ¦¨               # remove the first and last element
                     # STACK: 'golf', 'flog', ['lo', 'ol']
      Dg             # get the length of the list
                     # STACK: 'golf', 'flog', ['lo', 'ol'], 2
        ú            # prepend that many spaces to each element
                     # STACK: 'golf', 'flog', ['  lo', '  ol']
         €Á          # rotate each right
                     # STACK: 'golf', 'flog', ['o  l', 'l  o']
           s         # swap the top 2 items
                     # STACK: 'golf', ['o  l', 'l  o'], 'flog'
            )˜       # wrap in a flattened list
                     # STACK: ['golf', 'o  l', 'l  o', 'flog']
              »      # join on newline
               Igi¨  # if input is length 1, remove last char

```

The fix for 1-letter input was quite expensive.
I feel like a different approach might be better now.

# Answer
> 2 votes
# Python 3, 88 bytes

```
w=input();p=print;l=len(w)-2
[p(w[n+1]+' '*l+w[l-n])for n in range(l)]
l+1and p(w[::-1])

```

# Answer
> 1 votes
# Python 2, ~~99~~ 88 bytes

*-4 bytes thanks to musicman523.*

```
lambda s:s[1:]and[s]+[s[i]+' '*(len(s)-2)+s[~i]for i in range(1,len(s)-1)]+[s[::-1]]or s

```

Try it online!

Returns a list of strings.

# Answer
> 1 votes
# Swift 3, ~~215~~ 199 bytes

```
let s=readLine()!,c=s.characters,r:[Character]=c.reversed(),b=c.count
print(s)
if b>1{for i in 0..<b-2{print("\(r.reversed()[i+1])\(String.init(repeating:" ",count:b-2))\(r[i+1])")};print(String(r))}

```

Try it online

# Answer
> 1 votes
# APL, 58 bytes

```
{(' ',⍵)[x+(x←∘.{((c-1)=⍺⌈⍵)∨0=⍺⌊⍵}⍨r)×o⌊⌽⊖o←∘.⌈⍨r←⍳c←≢⍵]}

```

With `⎕IO←0`.

Try it online!

**How?**

`c←≢⍵` \- length of the string

`r←⍳` \- range

`o←∘.⌈⍨` \- outer product with minimum

```
123
223
333

```

`o⌊⌽⊖` \- minimalize with itself turned 180o

```
123  ⌊  333  =  123
223  ⌊  322  =  222
333  ⌊  321  =  321

```

`×` \- multiply with

`x←∘....⍨r` \- outer product of the range with

`((c-1)=⍺⌈⍵)∨0=⍺⌊⍵` \- the frame of the matrix

```
111  ×  123  =  123
101  ×  222  =  202
111  ×  321  =  321

```

`x+` \- add the frame

```
111  +  123  =  234
101  +  202  =  303
111  +  321  =  432

```

`(' ',⍵)[...]` \- get by index from the string concatenated to space

# Answer
> 1 votes
# Mathematica, 128 bytes

```
(c=Column;g=Length[x=Characters@#]-1;If[g==0,#,c@{#,c@Table[""<>{x[[i]],""<>Table[" ",g-1],x[[-i]]},{i,2,g}],StringReverse@#}])&

```

# Answer
> 1 votes
# C, 96 bytes

```
i,l;f(char*s){for(i=l=puts(s)-2;--i;)printf("%c%*c\n",s[l-i],l,s[i]);for(;l+1;)putchar(s[l--]);}

```

Bonus version (122 bytes):

```
x,y,i,l;f(char*s){for(i=l=puts(s)-1;++i<l*-~l;putchar(x==l?10:x%~-l*(y%~-l)?32:s[(x*y?l+l-2-x-y:x+y)%l]))x=i%-~l,y=i/-~l;}

```

# Answer
> 1 votes
# JavaScript (ES8), ~~108~~ 112 bytes

```
let f =

s=>(n=s.length)<2?s:(r=[...s].reverse()).slice(1,-1).reduce((a,v,i)=>a+`
`+s[i+1].padEnd(n-1)+v,s)+`
`+r.join``

o.innerHTML = f("hello folks!")
```

```
<pre id="o"></pre>
```

**Less golphed**

```
s=>
   (n=s.length) < 2 ?    // record and check length
   s :                   // s has 0 or 1 char, else
   (r=[...s].reverse())  // reverse characters,
   .slice(1,-1)          // exclude 1st and last
   .reduce((a,v,i)=>     // append inner lines
      a +'\n' +s[i+1].padEnd(n-1) + v
    ,s)                  // to first line
    + '\n' +r.join("")   // append characters reversed

```

Thanks to Justin Mariner for saving lots of bytes, which then all got used up adding the zero or single character check needed to comply with the challenge. You get that :-(

# Answer
> 1 votes
# PHP, 118 bytes

```
echo $s=$argv[1];$l=strlen($r=strrev($s))-1;for($i=$l-1;$l&&$i;)echo "\n".str_pad($r[$i],$l).$s[$i].(--$i?"":"\n$r");

```

Try it online!

```
echo $s = $argv[1];
$l = strlen($r = strrev($s)) - 1;

for ($i = $l - 1; $l && $i;)
    echo "\n" . str_pad($r[$i], $l) . $s[$i] . (--$i ? "" : "\n$r");

```

# Answer
> 1 votes
# Vyxal, ~~16~~ 10 bytes

```
∞∞?L2460ø∧

```

Try it Online!

-6 bytes by porting 05AB1E thanks to emanresu

# Answer
> 1 votes
# Japt `-R`, ~~14~~ 10 bytes

*Knew* there had to be a shorter way!

```
¬hU ÆÔÃÕÆÔ

```

Try it

```
¬hU ÆÔÃÕÆÔ     :Implicit input of string U
¬              :Split
 hU            :Replace first element with U
    Æ          :Modify last element
     Ô         :  U reversed
      Ã        :End modify
       Õ       :Transpose
        ÆÔ     :As above
               :Implicit output joined with newlines

```

# Answer
> 1 votes
# Python 3, 122 bytes

```
i=input();l=len(i)
if l!=1:
    print(i)
    for I in range(1,l-1): print(i[I]+" "*(l-2)+i[l-I-1])
    print(i[::-1])
else:print(i)

```

Attempt This Online!

# Answer
> 1 votes
# , 28 23 bytes

```
|._1}]0}|.,.~<:@#{."1,.

```

Try it online!

* `,.` Columnize the input:

```
g
o
l
f

```
* `<:@#{."1` Take "input length - 1" elements from each row, with space fills. I'll show the spaces filled with `.` for clarity:

```
g..
o..
l..
f..

```
* `|.,.~` Zip with the reverse:

```
g..f
o..l
l..o
f..g

```
* `]0}` Replace first row with input:

```
golf
o..l
l..o
f..g

```
* `|._1}` Replace last row with input reversed:

```
golf
o..l
l..o
flog

```

# Answer
> 1 votes
# 05AB1E, 8 bytes

```
gIûûŽ9¦Λ

```

Try it online or verify all test cases.

**Explanation:**

```
g    # Push the length of the (implicit) input
I    # Push the input itself
 û   # Palindromize it
  û  # And palindromize that again
Ž9¦  # Push compressed integer 2460
Λ    # Use the Canvas builtin with those three options
     # (after which the result is output immediately implicitly)

```

See this 05AB1E tip of mine (section How to compress large integers?) to understand why `Ž9¦` is `2460`.

As for some additional information about the Canvas builtin `Λ`:
It takes 3 arguments to draw an ASCII shape:

1. Length of the lines we want to draw
2. Character/string to draw
3. The direction to draw in, where each digit represents a certain direction:

```
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

```

`gIûûŽ9¦` creates the following Canvas arguments:

* Length: the length of the input (e.g. `4` for input `"abcd"`)
* Characters: the double palindromized input (e.g. `"abcdcbabcdcba"` for input `"abcd"`)
* Directions: `[2,4,6,0]`, which translates to \\$\[→,↓,←,↑\]\\$

Because we only have a single length, the directions are leading here.

Step 1: Draw 4 characters (`"abcd"`) in direction `2` (\\$→\\$):

```
abcd

```

Step 2: Draw 4-1 characters (`"cba"`) in direction `4` (\\$↓\\$):

```
abcd
   c
   b
   a

```

Step 3: Draw 4-1 characters (`"bcd"`) in direction `6` (\\$←\\$):

```
abcd
   c
   b
dcba

```

Step 4: Draw 4-1 characters (`"cba"`) in direction `0` (\\$↑\\$):

```
abcd
b  c
c  b
dcba

```

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.

# Answer
> 0 votes
# Lua, 104 bytes

```
print(s);for a=2,#s-1 do print(s:sub(a,a)..(" "):rep(#s-2)..s:sub(#s-a+1,#s-a+1)) end;print(s:reverse())

```

Try it online!

# Answer
> 0 votes
# JavaScript (ES2017), 87 bytes

```
s=>[...s].reverse(l=s.length-1).map((c,i,z)=>i?l-i?s[i].padEnd(l)+c:z.join``:s).join`
`

```

ES6 version: 93 bytes

```
s=>[...s].reverse(l=s.length-1).map((c,i,z)=>i?l-i?s[i]+' '.repeat(l-1)+c:z.join``:s).join`
`

```

*Less golfed*

```
s => (
  l = s.length-1,
  [...s].reverse().map( // scan string backwards
     (c, i, z) =>
     i != 0 // check if top row
     ? l-i != 0 // check if bottom row
       ? s[i].padEnd(l) + c // any middle row
       : z.join`` // bottom row: string reversed
     :s // top row: original string
  ).join`\n`
)

```

```
F=
s=>[...s].reverse(l=s.length-1).map((c,i,z)=>i?l-i?s[i].padEnd(l)+c:z.join``:s).join`
`

function update() {
  O.textContent = F(I.value)
}

update()
```

```
<input id=I value='Hello, world!' oninput='update()'>
<pre id=O></pre>
```

# Answer
> 0 votes
# C# (.NET Core), ~~179~~ 161 bytes

*-18 bytes thanks to TheLethalCoder*

```
using System.Linq;
s=>{int l=s.Length-1,i=1;var d=s.Reverse().ToArray();while(i<l)s+="\n"+s[i]+new string(' ',l-1)+d[i++];if(l>1)s+="\n"+new string(d);return s;};

```

Try it online!

~~I'm not sure about the rules, if this is needed to byte count or not:~~

~~```
using System.Linq;

```~~

~~Someone please correct me about this.~~

Ungolfed:

```
s =>
{
    int l = s.Length - 1, i = 1;
    var d = s.Reverse().ToArray();
    while (i < l)
        s += "\n" + s[i] + new string(' ', l - 1) + d[i++];
    if (l > 1)
        s += "\n" + new string(d);
    return s;
};

```

# Answer
> 0 votes
# Java, 191 bytes

```
(s)->{PrintStream o=System.out;int l=s.lenght();o.println(s);for(int i=0;i<l;i++){o.printf("%"+"s%"+(l-1)+"s%n",s.charAt(i),s.charAt(l-1-i));for(int i=0;i<l;i++){o.print(s.charAt(l-1-i));}}};

```

# Answer
> 0 votes
# Python 3, 85 bytes

Using the input for the top row :)

```
a=input()
b=len(a)
for i in range(b-2):print(a[1+i]+" "*(b-2)+a[-2-i])
print(a[::-1])

```

# Answer
> 0 votes
# Retina, 106 bytes

```
..+
$&¶$&
O$^`.(?=.*$)

\G.
$&$%'¶
r`.\G
¶$%`$&
+`(.+)¶¶((.*¶)*).(.*)
¶¶$1$4$2
T`p` `(?<=.¶.).*(?=.¶.)
G`.

```

Try it online! Explanation:

```
..+
$&¶$&

```

If there are at least two characters, duplicate the input.

```
O$^`.(?=.*$)

```

Reverse the duplicate.

```
\G.
$&$%'¶
r`.\G
¶$%`$&

```

Turn the strings into triangles. The top triangle starts with the input and removes the first character each time, while the bottom triangle starts with the first letter of the reversed input and adds a character each time.

```
+`(.+)¶¶((.*¶)*).(.*)
¶¶$1$4$2

```

Join the triangles together, overlapping so that the last character forms the `/` diagonal.

```
T`p` `(?<=.¶.).*(?=.¶.)

```

Change all the characters to spaces, if they are at least one character away from the end on every side.

```
G`.

```

Delete any left-over blank lines.

# Answer
> 0 votes
# Python 3, 106 bytes

A functional version...

```
w=input();p=print;l=len(w)-2
def f(k):p(w[k]+' '*l+w[-k-1]);l-k>0and f(k+1)
l<0 or f(1)or l<1or p(w[::-1])

```

# Answer
> 0 votes
# Python 2, 100 bytes

```
lambda a:'\n'.join([a]+(len(a)>1)*([a[i]+(len(a)-2)*' '+a[~i]for i in range(1,len(a)-1)]+[a[::-1]]))

```

Try it online!

# Answer
> 0 votes
# Mathematica, ~~138~~ 91 bytes

```
(b=Outer[" "&,#,#];Do[l={{1,k},{k,1}};b=ReplacePart[b,Join[l,-l]->#[[k]]],{k,Length@#}];b)&

```

You can try it online with by pasting the following at the Wolfram Cloud Sandbox and clicking "evaluate cell" or hitting Shift+Enter or Numpad Enter:

```
(b=Outer[" "&,#,#];Do[l={{1,k},{k,1}};b=ReplacePart[b,Join[l,-l]->#[[k]]],{k,Length@#}];b)&@{"g","o","l","f","y"}//MatrixForm

```

# Answer
> 0 votes
# \>\<\> (Fish) \- 153 bytes

```
l:>:?v;l$-[r:or].
-$/-$>$: ?vao~1-l1
  ^1vv?(2:<
 1^\:>$:&05&60. >$:&04&60.
o 1^\l3-=?v$:2(?^:l3-=?v$' '
 $^/$-3l:$<   /1-$-3l:$<
   \-1+&05&60.\+&04&60.

```

Try it

Make sure the initial stack setting is set to "chars", occasinally it bugs out and switches itself to numbers.

## Summary

The blue bar at the top `l$-[r:or]` prints the n-th letter. The rest of the code is mostly branches leading to `&04&60.` that jump to the nth letter printer.

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


title: Draw a descendant pyramid (addition)

text:
# Question
Title: Draw a descendant pyramid (addition)
**Challenge**

Given a sequence of non-negative integers, create a function that output a descendant pyramid where the children are the sum of both parent numbers.

The result is outputted as an string using tab `\t`.

*Note: trailing tabs on each line are not required*

```
1\t\t2\t\t3\n\t3\t\t5\t\n\t\t8\t\t results in
1       2       3
    3       5
        8

```

Optionally result can be outputted as an array using an empty position as space.

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

```

**Example:**

Given `4,5,7,3,4,2` Output:

```
4       5       7       3       4       2
    9       12      10      7       6
        21      22      17      13
            43      39      30
                82      69
                    151

```

**Rules**

* Standard rules apply
* Input can be a string using any separator or an array
* Leading/trailing newlines and tabs are permitted (but not required as long as the output is an inverted pyramid)

**Test Cases**

```
Input: 1,3,5

1       3       5
    4       8
        12

Input: 9,8,7,6,5

9       8       7       6       5
    17      15      13      11
        32      28      24
            60      52
                112

Input: 5,5,2,5

[[5,,5,,2,,5],
[,10,,7,,7,],
[,,17,,14,,],
[,,,31,,,]]

Input: 3,3,3

[[3,,3,,3],
[,6,,6,],
[,,12,,]]

```

Winning criteria is

---

***Note:*** *This challenge is very close to Generate Pascal's triangle. The difference is the custom starting sequence (pascal goes from 1 and in ascendant mode, this from an input and in descendant mode).*

**Sandbox post**

# Answer
> 4 votes
# 05AB1E, ~~15~~ 14 bytes

-1 bytes thanks to Kevin Cruijssen

```
vD„		ý'	N×ì,ü+

```

Try it online!

# Answer
> 4 votes
# Jelly,  ~~14~~  13 bytes

14 -\> 13 assumes trailing spaces-only entry is allowed in the list format output; if not I shall revert to the 14 (asked)

```
+ƝƬK€z⁶Zṙ"JC$

```

A monadic link. Output is a list of lists using space characters as the spaces (includes a single trailing spaces-only entry).

**Try it online!** (includes a footer to show the list structure since running the monadic link as a full program will print smashed output implicitly.)

# Answer
> 4 votes
# APL (Dyalog Unicode), ~~31~~ 28 bytesSBCS

Tacit prefix function. Uses a single space as empty slot marker. Returns list of lists of numbers/spaces.

```
⍳∘≢{∊(⍺⍴''),,∘' '¨2+/⍣⍺⊢⍵}¨⊂

```

Try it online!

`⍳∘≢{``}¨⊂` apply the below function for each of
the **ɩ**ndices  of  the tally with
the entire argument:

`⊢⍵` yield the right argument (the original input)

`2+/⍣⍺` apply pairwise sum as many times as indicated by the left argument

`,∘' '¨` append a space to each number

`(``),` append that to the following:

`⍺⍴''` left-argument elements of the empty string (padded with spaces)

**ϵ**nlist (flatten)

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

```
ArrayPad[Riffle[#,],k++,]&/@NestList[k=0;BlockMap[Tr,#,2,1]&,#,Tr[1^#]-1]&

```

Try it online!

# Answer
> 3 votes
# Husk, 22 bytes

```
zoΣ~+R"	"oJ"		"msNU¡Ẋ+

```

Try it online!

### Explanation

```
z(Σ~+R" "(J"  "ms))NU¡Ẋ+  -- example input: [1,2,3]
                     ¡    -- infinitely do and collect in list
                      Ẋ+  -- | sum adjacent
                          -- : [[1,2,3],[3,5],[8],[],[],...
                    U     -- keep up until first repetition: [[1,2,3],[3,5],[8],[]]
z(                )N      -- zip with natural numbers under (example on 1 [1,2,3])
   ~+    (       )        -- | join arguments modified by
     R" "                 -- | | replicate tab: " "
               ms         -- | | show each: ["1","2","3"]
          J"  "           -- | | join with 2 tabs: ["1","  ","2","  ","3"]
                          -- | : [" ","1","  ","2","  ","3"]
  Σ                       -- | concatenate: " 1  2  3"
                          -- : [" 1  2  3","  3  5","   8"]

```

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

Weird source code ... Anyway, that's !

Includes leading and trailing whitespace.

```
f=(a,p=`
`)=>p+a.join`		`+(1/(y=a.shift())?f(a.map(x=>y+(y=x)),p+`	`):'')

```

Try it online!

# Answer
> 2 votes
# Python 3, ~~101~~ ~~93~~ 80 bytes

Saved 7 bytes (`map(str,x)` instead of `for in` and init y as `''`) and got rid of the trailing newlines (`x and[` instead of `print(`), thanks to *Jo King*.

Saved 13 bytes (`[*map(sum,zip(x,x[1:]))]` instead of `[x[j]+x[j+1]for j in range(len(x)-1)]`) thanks to *ovs*.

```
f=lambda x,y='':x and[y+'		'.join(map(str,x))]+f([*map(sum,zip(x,x[1:]))],y+'	')

```

Try it online!

# Answer
> 2 votes
# Perl 5 `-a`, 62 bytes

```
$,="\t\t";do{say"\t"x$i++,@F;map$_+=$F[++$q[@F]],@F}while$#F--

```

Try it online!

# Answer
> 1 votes
# Retina, 35 bytes

```
+¶<`\d+ *(?=(\d+)?)
    $#1*$.(*_$1*)

```

Try it online! Explanation:

```
+

```

Repeat until the buffer stops changing,

```
¶<`

```

Print the contents of the buffer before the substitution, with a trailing newline, and

```
\d+ *(?=(\d+)?)
    $#1*$.(*_$1*)

```

Substitute a single number with a pair of tabs, but a number followed by another number with a tab, the sum, and another tab.

# Answer
> 1 votes
# Perl 6, ~~50~~ 48 bytes

```
{$_,{say "	"x$++~.join("		");$_[1..*]Z+@$_}...0}

```

Try it online!

Anonymous code block that takes a list of integers and prints the inverted pyramid.

# Answer
> 1 votes
# C (clang), ~~112~~ 109 bytes

* -3 from @ceilingcat

```
j,k;f(*i,c){for(j=c;j;j-=puts("")){for(k=c-j;k--;)putchar(9);for(;++k<j;i[k]+=i[k+1])printf("%d\t\t",i[k]);}}

```

Try it online!

# Answer
> 1 votes
# Red, 151 bytes

```
func[b][m: length? b repeat n m[loop n - 1[prin"^-"]print replace/all
form b" ""^-^-"c: copy[]repeat i -1 + length? b[append c b/(i) + b/(i + 1)]b: c]]

```

Try it online!

## More readable:

```
f: func [ b ] [
    m: length? b
    repeat n m [
        loop n - 1 [ prin tab ]
        print replace/all form b " " rejoin [ tab tab ]
        c: copy []
        repeat i (length? b) - 1 [
            append c b/(i) + b/(i + 1)
        ]
        b: c
    ]
]

```

# Answer
> 1 votes
# C# (Visual C# Compiler), 163 bytes

```
b=>{var s="";var c=b.Length;for(int i=0;i<c;i++){for(int z=0;z<i;z++)s+="\t";for(int x=0;x<c-i;x++){s+=b[x]+"\t\t";b[x]=x==c-i-1?0:b[x]+b[x+1];}s+="\n";}return s;}

```

Try it online!

Readable:

```
b =>    {
            var s = "";
            var c = b.Length;
            for (int i = 0; i < c; i++)
            {
                for (int z = 0; z < i; z++)
                    s += "\t";
                for (int x = 0; x < c - i; x++)
                {
                    s += b[x] + "\t\t";
                    b[x] = x == c - i - 1 ? 0 : b[x] + b[x + 1];
                }
                s += "\n";
            }
            return s;
        }

```

# Answer
> 1 votes
# Japt `-Rx`, ~~20~~ 18 bytes

The second line includes a trailing tab.

```
Nc¡=ä+
Ëq' ² iEç'

```

Try it

---

## Explanation

```
                  :Implicit input of array U
N                 :The array of inputs (NOT the input array)
 c                :Concatenate
  ¡               :  Map U
    ä+            :    Consecutive sums of U
   =              :    Reassign to U for next iteration
\n                :Reassign the resulting 2D-array to U
Ë                 :Map each array at index E
 q                :  Join with
  '\t             :   Tab
     ²            :   Repeated twice
       i          :  Prepend
          '\t     :   Tab
         ç        :   Repeated
        E         :   E times
                  :Implicitly join with newlines, trim (not strictly necessary) and output.

```

# Answer
> 1 votes
# Vyxal, 18 bytes

```
2lṠ)↔ðdvj:ẏ$꘍⁋ð9CV

```

Try it Online!

I *think* this works? Output format is annoying.

```
   )↔              # Repeat until no change, collecting values
  Ṡ                # Sums of
2l                 # Consecutive pairs
       vj          # Join each by...
     ðd            # Double spaces
           $꘍      # Pad left with spaces by
         :ẏ        # range(0, len(list)
             ⁋     # Join by newlines
                 V # Replace
              ð    # Spaces
               9C  # With tabs

```

# Answer
> 1 votes
# Python 3, ~~79~~ ~~75~~ 70 bytes

Has leading tabs. Prints the required output then prints trailing tabs and newlines forever.

```
def f(x,y='\n'):print(y,*x,sep='        ');f([*map(sum,zip(x,x[1:]))],y+'   ')

```

Try it online!

# Answer
> 0 votes
# Ruby, 67 bytes

A straightforward recursive solution.

```
F=->a,n=0{puts ?\t*n+a*"		"
a[0]&&F[a.each_cons(2).map(&:sum),n+1]}

```

Attempt This Online!

---
Tags: code-golf
---