title: Is it a valid list?

text:
# Question
Title: Is it a valid list?
Given a string like `[[[],[[]]],[]]`, made of only commas and square brackets, your challenge is to determine whether it represents a list.

A list is either:

* `[]`, the empty list
* At least one list, joined with commas and wrapped in square brackets.

You may use any three characters instead of `[,]`.

You may output as:

* Any two consistent values representing truthy and falsy
* One consistent value representing either truthy or falsy, and anything else as the other.

Output by erroring/not erroring *is* allowed, although `eval`-like solutions may be trickier than you think. Sometimes erroring and sometimes returning is *not*.

This is , shortest wins!

### Truthy

```
[[]]
[[],[]]
[[[[]],[[],[[]]],[]],[]]
[[[[]]]]
[]

```

### Falsy

```
]
[[][]]
[,]
,
[],[]
[[[]][[]]]
[[],]
,[]
[[]
[,[]]
[][]
[[],

```

# Answer
> 14 votes
# JavaScript, 10 bytes

```
JSON.parse

```

Outputs via the presence or absence of an error.

Try it online!

# Answer
> 8 votes
# Python3, 70 bytes:

```
def f(s):
 try:return s==str(eval(s)).replace(' ','')
 except:return 0

```

Try it online!

# Answer
> 8 votes
# PARI/GP, 0 bytes

Takes input from `stdin`, returns truthy iff `stderr` is empty.

PARI/GP automatically parses and evals everything from the `stdin`.

Attempt This Online!

# Answer
> 7 votes
# APL (Dyalog Unicode), 5 bytes

Anonymous tacit prefix function taking input as `[,]` with output by erroring/not erroring.

```
⎕JSON

```

Try it online! (wrapped in error trapping code to give 0 when erroring and 1 when not erroring)

Attempts to convert from JSON.

# Answer
> 7 votes
# Haskell + hgl, 26 bytes

```
f=opn*>isP f ʃ_*>cls

```

```
x1 f

```

Uses the characters `()_`.

Creates a parser object and uses `x1` to determine if some input matches the parser.

# 25 bytes

```
f('(':')':>x)=mF f$' '|\x

```

Uses the characters `()` .

Returns `True` on valid inputs and errors on invalid ones.

This version is 1 byte shorter but I'm not sure if it's allowed by the rules. If you call the function expecting a bool, e.g.

```
f x::Bool

```

It will work. However by default ghci infers `()` as the type, which does not meet the output specifications of the challenge. So you need to call it either with a type signature or in a context in which ghc can infer it's type to be `Bool`.

# Relfections

* hgl has a `unwords` function. It could be made a pattern like in the curry answer:
```
f('(':')':>Uw x)=mF f x

```
* It's rather annoying that `wR`, the `words` function trims leading spaces. There is a 23 byte answer which would work if `wR` didn't do this.
```
f('(':')':>x)=mF f$wR x

```
* `mF` should have an infix.
* `isP` should have an infix.
* `isP` should have a flip.

# Answer
> 6 votes
# Stax, ~~22~~ 23 bytes

```
Ç╥╫ÜΦªt┌¢♣☺¢+╬ï▼6◘-6¡Zq

```

Run and debug it

### Approach

* Repeatedly
    + Replace `"[[]]"` with `"[]"`
    + ~~Replace `",[]]"` with `"]"`~~
    + Replace `"[[],["` with `"[["`
* Is result equal to `"[]"`?

# Answer
> 6 votes
# Python, 19 bytes (@dingledooper)

```
eval("set"+input())
```

Attempt This Online!

### Old Python, 22 bytes

```
def f(s):eval("set"+s)
```

Attempt This Online!

This takes a string composed of the characters "(+)" and signals by erroring/not erroring.

#### How?

Why can't we just use `eval`?

1. trailing commas
2. missing outer brackets

Both will be tolerated by `eval`.

To address 1 we replace `,` with `+`.

To address 2 we switch from `[]` to `()` and prepend `set`.

### Old Python, 28 bytes

```
def f(s):eval(s+","+s[1:-1])
```

Attempt This Online!

This takes a string composed of the characters "\[+\]" (note that we have cheekily but legally replaced "," with "+") and signals by erroring/not erroring.

I'm not 100% sure this is correct but it works on all test cases.

# Answer
> 5 votes
# Curry (PAKCS), 29 bytes

```
f('[':unwords a++"]")=all f a

```

Try it online!

Uses a space  instead of `,`. Returns `True` for truth, and nothing otherwise.

---

# Curry (PAKCS), 53 bytes

```
f('[':a++"]")=g a
f"[]"=1
g(a++',':b)=f a*g b
g a=f a

```

Try it online!

Returns `1` for truth, and nothing otherwise.

# Answer
> 4 votes
# Whython, 36 bytes

```
lambda s:eval(s)>=[]!=",]"not in s?0

```

Returns `True` for valid lists, `False` or `0` for invalid lists. Attempt This Online!

### Explanation

```
lambda s:eval(s)>=[]!=",]"not in s?0
lambda s:                             # Anonymous function that takes s, a string
         eval(s)                      # Python eval
                >=[]                  # True if the result is a list, error if tuple
                    !=                # Keep the comparison chain going
                      ",]"not in s    # Check that there are no extra commas
                                  ?0  # If anything raised an error, return 0

```

# Answer
> 4 votes
# Regex (Perl / PCRE), 21 bytes

```
^(<(((?1),)*(?1))?>)$

```

Uses the characters `<>,`. (Avoids `[]` as they would require being `\`-escaped.)

Try it online! \- Perl
Try it on regex101 \- PCRE1
Try it online! \- PCRE2 v10.33
Attempt This Online! \- PCRE2 v10.39+

Like the regex in the Raku answer, this uses recursion. Unlike Raku, standard regex has no concept of "separator" characters, so there's no concise way of implementing a comma-separated list, and the recursive call `(?1)` needs to be in two places.

There are many alternatives of the same length:

### Regex (Perl / PCRE), 21 bytes

```
^(<((?1)(,(?2))?)?>)$

```

Also uses the characters `<>,`.

Try it online! \- Perl
Try it online! \- PCRE

Uses `(?2)` recursion instead of `*` repetition for the comma-separated list.

### Regex (Perl / PCRE), 21 bytes

```
^(a((?1),)*(?1)?\Bz)$

```

Uses the characters `az,` in order to take advantage of the `\B` non-word-boundary assertion.

Try it online! \- Perl
Try it online! \- PCRE

Without the use of `\B`, there would be nothing stopping a comma-separated list ending in a comma from being accepted, as the `(?1)?` is optional independently of whether or not `((?1),)*` matched anything.

The `\B` prevents this; if any list ended with a comma, the sequence `,z` would be part of it, so all we need to do is prohibit this sequence. `\Bz` accomplishes this, as `a` and `z` are word-characters but `,` is not, thus there is no word boundary in the middle of `az` or `zz` but there is one in `,z`.

### Regex (Perl / PCRE), 21 bytes

```
^(a\B(?1)?(,(?1))*z)$

```

Also uses the characters `az,`. Mirror version of the above.

Try it online! \- Perl
Try it online! \- PCRE

### Regex (Perl / PCRE), 21 bytes

```
^(<(\B(?1)|\b,\B)*z)$

```

Try it online! \- Perl
Try it online! \- PCRE

Uses the characters `<z,` in order to take advantage of the `\b` and `\B` word- and non-word-boundary assertions.

### Regex (Perl / PCRE), 21 bytes

```
^(a((?1)\B|\B,\b)*>)$

```

Uses the characters `a>,`. Mirror version of the above.

Try it online! \- Perl
Try it online! \- PCRE

# Regex (.NET), ~~35~~ ~~33~~ 29 bytes

```
^((a)+(?<-2>z)+(?(2),\b|$))+$

```

Uses the characters `az,` in order to take advantage of the `\b` word-boundary assertion.

Try it online!

Based on the old **35 byte** one-liner in Neil's Retina answer.

*-1 byte by using the characters `<>,` instead of `[],`, because `[` needed to be `\`-escaped*
*-1 byte by using an illegal character, instead of `$.`, as the impossible condition to assert Group 2 being empty at the end*
*-4 bytes by using the characters `az,` instead of `<>,`, obviating the need for explicitly asserting Group 2 is empty at the end*

```
^                # Assert that we're at the beginning of the string.
(
    (a)+         # Capture at least one "a" on the Group 2 stack.
    (?<-2>z)+    # Match at least one "z", popping an entry from the Group 2
                 # stack for each one we match.
    (?(2),\b|$)  # If the Group 2 stack is non-empty, match a "," followed by a
                 # word boundary (since "," is a non-word character, this means
                 # it must be followed by a word character, i.e. [0-9A-Za-z_]),
                 # else assert that we're at the end of the string.
)+               # Loop the above at least 1 time.
$                # Assert that we're at the end of the string. The Group 2
                 # conditional at the end of the above loop guarantees that the
                 # only way to end the loop at the end of the string is for
                 # Group 2 to be empty, due to the "\b" in its non-empty
                 # clause. So there's no need to explicitly assert here
                 # something like "(?(2)$.)" (which would assert something
                 # impossible in the case that Group 2 is non-empty).

```

Note that if the `<>,` characters are still used, it can be **32 bytes**:

```
^((<)+(?<-2>>)+(?(2),(?!$)|$))+$

```

Try it online!

### \\$\large\textit{Anonymous functions}\\$

# Perl, 33 bytes

```
sub{pop=~/^(<(((?1),)*(?1))?>)$/}

```

Try it online!

# , ~~49~~ ~~48~~ ~~44~~ 39 bytes

```
\(L)grepl('^(<(((?1),)*(?1))?>)$',L,,1)

```

Attempt This Online!

*-1 byte thanks to Giuseppe*
*-4 bytes by using `grepl()` instead of `sum(grep())` or `any(grep())`*
*-5 bytes by using a new anonymous function syntax introduced in R v4.1.0*

# PowerShell, ~~46~~ 42 bytes

```
$args-match'^((a)+(?<-2>z)+(?(2),\b|$))+$'

```

Try it online!

# Answer
> 4 votes
# Yacc, 22 bytes

```
s:'['b']'b:l|l:s|s','l

```

Try it online! (note: Yacc is installed on TIO, but doesn't have a TIO wrapper, so I had to write one myself; I also wrapped the function into a full program. The wrapper outputs by exit code.)

Function submission. (I originally forgot PPCG allowed functions to be sumbitted, so the first version of this was a full program with a lot of boilerplate. Submitting it as a function obviously makes more sense.)

This is a function/parser named `s` that reads input from `yacc`'s usual input source. It does the `yacc` equivalent of throwing an exception if the input is not a list, or returns normally if the input is a list. (It doesn't explicitly return a value – Yacc uses "implicit int" like in C, so these parsers are technically returning integers, but we don't set the return value to anything in particular.)

This function uses `[`, `]`, `,` as suggested by the question, but could easily be adapted to use any three characters (although some choices would make the program longer due to needing to be escaped).

## Explanation

Yacc is a language for writing parsers; you provide a description of syntactically legal input and it generates a parser for you. This program contains three parsers, `s`, `b` and `l`:

```
s:'['b']'b:l|l:s|s','l
s:                       An "s" is
  '['                      an opening square bracket
     b                     then a "b"
      ']'                  then a closing square bracket;
         b:              A "b" is
           l|              either an "l", or {an empty string};
             l:          An "l" is
                |          either
               s             an "s"
                |          or
                 s           an "s"
                  ','        followed by a comma
                     l       followed by another "l"

```

A direct translation of the question to Yacc would be `s:'['']'|'['l']'l:s|s','l`, but factoring out the brackets from the two branches of `s` into a separate rule `b` allows the program to be a byte shorter.

Yacc programs don't normally look this condensed; they're normally written with more whitespace, and semicolons between rules. However, the semicolons are optional, and whitespace is optional except between two identifiers (and I arranged this program so that it never had two identifiers in a row, allowing all the whitespace to be golfed off). A weird side effect of this flexibility is that Yacc's syntax is very hard to parse due to false positives (e.g. `b:l|l` is a valid rule, but `b:l|l:` has to be parsed as `b:l|; l:` despite that), and in fact, it isn't sufficiently powerful to write a parser for its own syntax (it's powerful, but its syntax is weird enough that it needs even more power to parse). It's helpful in golfing, though!

# Answer
> 3 votes
# Retina 0.8.2, ~~39~~ ~~35~~ 23 bytes

```
<<>>
<>
}`<<>,<
<<
^<>$

```

Try it online! Takes `<,>` characters but link is to test suite that converts from `[]` for convenience. Explanation: Port of @recursive's Stax solution.

```
<<>>
<>

```

Remove an empty list that's the only element of a list.

```
<<>,<
<<

```

Remove an empty list that's the first element of a list.

```
}`

```

Repeat until there are no more elements to remove.

```
^<>$

```

Check that we finished with an empty list.

Escaping means that it takes 29 bytes to use `[,]` characters:

```
\[\[]]
[]
}`\[\[],\[
[[
^\[]$

```

Try it online! Link includes test cases.

Previous 35-byte one-liner:

```
^((\[)+(?<-2>])+(?(2),|$))+(?(2)$.)

```

Try it online! Link includes test cases. Explanation:

```
^(

```

Start matching at the beginning of the string.

```
(\[)+

```

Count the number of `[`s.

```
(?<-2>])+

```

Count some `]`s, but no more than the number of `[`s so far.

```
(?(2),|$)

```

After each run of `[`s and `]`s, if there are still unbalanced `]`s, then there must be a `,` next, otherwise we must be at the end of the string.

```
)+

```

Repeat as many times as necessary.

```
(?(2)$.)

```

Check that there weren't more `[`s than `]`s.

# Answer
> 3 votes
# Vyxal `P`, 8 bytes

```
øBEÞfSȧ=

```

Try it Online!

Still shorter than JavaScript! The link is a test suite, hence the additional flags - those are just to wrap all inputs into a list (`a`) and to treat all inputs as strings (`S with updot` \- it's the equivalent of wrapping every input in quotation marks).

## Explained

```
øBEÞfSȧ=
øBE      # wrap the input in square brackets and try to evaluate it as a python literal
   Þf    # attempt to flatten the list by a level - if the input was listlike (that is, valid for this challenge or valid as a python tuple), this will undo the `øB`. Otherwise it leaves the string as is
     S   # convert the result of the above to string. The P flag makes it so that square brackets and commas are used for lists instead of the angular brackets and pipes Vyxal uses.
      ȧ= # remove any whitespace and test to see if this new string is equal to the original input.

```

# Answer
> 3 votes
# , 101 bytes

```
\(x,y='',s=\(p,b,x)sub(p,b,x,,,T)){while(y!=(y=x)){x=s('[[],[]','[[]',y);x=s('[[]]','[]',x)};y=='[]'}
```

Attempt This Online!

Text replacement solution, '\[\[\],\[\]' -\> '\[\[\]' '\[\[\]\]' -\> '\[\]'

Earlier attempts at this were using far too many `\\` to escape `[`/`]`.

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

```
{Times=N}~Block~ToExpression@#&

```

Try it online!

Uses `{,}`. Returns by presence/absence of an error.

Missing arguments are interpreted as `Null`, but will raise an error message.

Juxtaposition is a valid operation (`Times`), so we use `Block` to turn it into `N`. Since `N` only handles one or two arguments, it errors when passed three or more arguments. When `N` has exactly two arguments, the second argument must be of the form `precision` or `{precision,accuracy}`, where `precision` and `accuracy` are numbers. Input is guaranteed to never have numbers, so the 2-argument form is also guaranteed to error.

# Answer
> 3 votes
# Rust (compile-time), 43 bytes

```
macro_rules!v{([$($a:tt),*])=>($(v!{$a})*)}

```

Try it online!

This is a Rust macro (the compile-time equivalent of a function) named `v!`. Use as `v!{…}`, where  is the string you want to check (without delimiters – string literals are opaque to the usual sort of Rust macro). I used `[`, `,`, `]` as in the question, although this could easily be adapted to use almost any Rust token in place of `,` and/or `()` rather than `[]`.

Outputs via error/non-error: an invalid list causes a compile time error, a valid list causes no error (and the macro expands to an empty declaration).

## Explanation

```
macro_rules!v{([$($a:tt),*])=>($(v!{$a})*)}
macro_rules!v{                            }   Macro declaration
              ([          ])                  Match something surrounded by []
                $(     ) *                      which consists of 0 or more
                  $a:tt                         balanced token trees $a
                        ,                       separated by commas
                            =>(          )    and replace it with,
                               $(   $a )*       for each $a,
                                 v!{$a}         a recursive call to v!{$a}

```

We verify the structure of the outermost list, then recurse into the inner lists to make sure that those are also correct. Rust macros have a `:tt` builtin that matches brackets, which makes it easy to use the strategy of parsing out the elements first and recursing over them afterwards. The base case of the recursion is that when we match a zero-length list, the replacement expands into zero macro calls, because the loop in the replacement runs for zero iterations.

Note that Rust normally allows a trailing comma on lists, so we do actually have to write our own verification macro rather than using something that Rust has predefined.

# Answer
> 2 votes
# Haskell (GHCi), 0 bytes

Takes input from `stdin`, returns truthy iff `stderr` is empty.

# Answer
> 2 votes
# Factor \+ `json.reader`, 5 bytes

```
json>

```

Try it online!

Outputs by the presence of an error.

# Answer
> 2 votes
# Rust, 406 bytes

```
fn a(d:&str)->bool{let c=d.chars().collect::<Vec<_>>();let c=c.as_slice();let b=c.iter().fold((0,0),|mut a,&i|{if i=='['{a.0+=1}else if i==']'{a.1+=1}a});let m=c.windows(2).any(|a|a[0]==']'&&a[1]=='[');let mut j=false;c.iter().fold(0,|a,&i|{if i=='['{a+1}else if i==']'{a-1}else if i==','&&a==0{j=true;a}else{a}});let o=c.windows(3).find(|a|a[1]==','&&(a[0]!=']'||a[2]!='['));b.0==b.1&&!m&&!j&&o.is_none()}

```

Try it online!

Not a golfing language by any means, but it's worth giving it a try. It can be golfed down a lot as it's currently using a really naïve approach.

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
„,]å≠i.E}˜

```

No error as truthy; error (`** (Protocol.UndefinedError) protocol Enumerable not implemented for ...`) as falsey.

Try it online or verify all test cases. (Wrap the single TIO input in `"""` quotes to get the input as string, instead of implicitly as (possibly faulty) list.)

**Explanation:**

```
     i  }   # If
            # the (implicit) input-string
    ≠       # does NOT
   å        # contain the substring
„,]         # ",]":
      .E    #  Evaluate the (implicit) input-string as Elixir
            # (implicit else)
            #  (implicitly use the input-string)
         ˜  # Flatten (results in [] for lists; or an error for strings)

```

The if-statement is for edge-case `[[],]`, which unfortunately is a valid Elixir/Python list that evaluates to `[[]]`. If it wasn't for this test cases, `.E˜` would have been enough in the new version of 05AB1E: verify all test cases.
And it could even have been 1 byte in the legacy version of 05AB1E using the `-e`/`--eval` flag: verify all test cases.

# Answer
> 2 votes
# Raku, 31 bytes

```
{($^a~~/"["<~~>*%",""]"/)~~$^a}

```

This is a function which takes the string as input and produces typical Raku Booleans (`True` or `False`).

Let's break it down. First, better spacing

```
{ ($^a ~~ /"[" <~~> * % "," "]"/) ~~ $^a}

```

First, `$^a` is a sort of special syntax for declaring lambdas without explicitly mentioning their arguments, so this is equivalent to the single-argument function

```
-> $a { ($a ~~ /"[" <~~> * % "," "]"/) ~~ $a}

```

Now, `~~` is a terribly clever thing in Raku called the smart-match operator. At a high-level, it's going to evaluate its right-hand side and then call the `.ACCEPTS` method on the right-hand side with the left-hand side as argument. We use it twice here: The leftmost application is on a regex object and will do a regular expression match. The rightmost application is on the input string and will perform ordinary string equality.

We're going to do a regex match against that regular expression enclosed in `/`. That match will return either a special regex `Match` object, or `Nil` if the match fails. We then compare that for string equality. A `Match` object stringifies as the substring it matched, so we're simply checking whether the match that was found is in fact the *whole* string. `Nil`, on the other hand, stringifies to `""`, and as per the comments the empty string is not valid input, so `$^a` will never compare equal to that.

Now let's look at the regex itself.

```
/"[" <~~> * % "," "]"/

```

If you haven't seen Raku regexes before, it may be best to forget everything you know about regular expressions, because the syntax is only superficially similar. Anything enclosed is quotes is matched literally, so `"["`, `","`, and `"]"` are matched literally. `*` works like it does in most regex languages: It's the Kleene star and matches zero or more. `%` is a modifier on `*` which delimits multiple matches by the thing on its right (in our case, a comma). Finally, `<~~>` is the recursive matcher, which matches the entire regular expression again. So, in summary

```
/                      # Start of regex
 "["                   # Match an opening bracket
          *            # Then match zero or more...
            % ","      # delimited by commas...
     <~~>              # of the current regular expression recursively
                  "]"  # Finally, match a closing bracket
                     / # End of regex

```

# Answer
> 2 votes
# SNOBOL4 (CSNOBOL4), 84 bytes

```
	L ='[]' | ('[' *L ARBNO(',' *L) ']')
	INPUT POS(0) L RPOS(0)	:F(END)
	OUTPUT =1
END

```

Try it online!

Prints 1 for truthy and nothing for falsey.

Recursive pattern matching is pretty slick.

Verify all test cases.

# Answer
> 2 votes
# Javascript, ~~79~~ ~~78~~ 77 bytes

```
f=s=>eval("r=/(<(<>,)+<>>)|(<<>>)/;r.test(s)&&f(s.replace(r,'<>'))||s=='<>'")

```

uses the characters `<,>` and returns `true`/`false`

saved 1 byte thanks to @RadvylfPrograms
saved 1 byte by using recursion and joining expressions

Try it online!

# Answer
> 1 votes
# Charcoal, 29 bytes

```
Ｆθ≔⪫⪪⪫⪪θ[[]]¦[]¦[[],[¦[[θ⁼θ[]

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for valid, nothing for invalid. Explanation: Boring port of @recursive's Stax answer.

```
Ｆθ

```

Repeat more than enough times...

```
≔⪫⪪⪫⪪θ[[]]¦[]¦[[],[¦[[θ

```

... remove the first or only element of a list if it's an empty list.

```
⁼θ[]

```

Check that we're left with an empty list.

Less boring 34 byte solution:

```
›⬤⁺,θ№,[[]],⁺ι§⁺θ,κ⊙θ∧κ⁼№…θκ[№…θκ]

```

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

```
   ,                                Literal string `,`
  ⁺                                 Concatenated with
    θ                               Input string
 ⬤                                  All characters satisfy
      ,[[]],                        Literal string `,[[]],`
     №                              Contains
             ι                      Current character
            ⁺                       Concatenated with
                θ                   Input string
               ⁺                    Concatenated with
                 ,                  Literal string `,`
              §                     Indexed by
                  κ                 Current index
›                                   And not
                    θ               Input string
                   ⊙                All characters satisfy
                      κ             Current index
                     ∧              Logical And
                        №           Count of
                            [       Literal string `[`
                         …θκ        In current prefix
                       ⁼            Equals
                             №      Count of
                                 ]  Literal string `]`
                              …θκ   In current prefix
                                    Implicitly print

```

Note that by default Charcoal tries to parse an input in a JSON-like format so to defeat that you need to wrap the input in JSON i.e. prepend `["` and append `"]`.

# Answer
> 1 votes
# C, 178 bytes

```
int v(char *s){int d=1;for(s++;*s!='\0';s++){if(d==0)return 0;if(*s=='{')d++;if(*s=='}'){d--;if(*(s+1)=='{')return 0;}if(*s==','&&!(*(s-1)=='}'&&*(s+1)=='{'))return 0;}return!d;}

```

---
Tags: code-golf, decision-problem, parsing, balanced-string, ragged-list
---


title: Gray coded Gray code convertor

text:
# Question
Title: Gray coded Gray code convertor
To increase data safety at our company, we are planning to start using Gray code numbers (where successive values differ by only one bit) instead of classical binary ones.

Please help us to make a program that converts numbers to Gray code (single number to single number), but the program needs to be safe as well. This means that each successive byte of the program can differ at most by one bit.

Here is a code from Wikipedia for conversion (ungolfed and "unsafe"):

```
uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

```

This code does following: Input number is bit shifted to the right by one bit and then there is performed exclusive or with original number. Example with input 123:

Binary representation of 123 is 1111011b, after shift right the number is 0111101b. After performing exclusive or between those two numbers the result is 1000110b, which is 70 in decimal.

Example inputs, outputs:

```
0, 0
1, 1
123, 70
255, 128
11, 14

```

Example of safe programs:

```
a

bcbcbc
!!!
h()
bcg

```

Example of unsafe programs:

```
abc
OP

```

# Answer
# Incident, 100 bytes

```
@``aaqscbjnNFNLllnjnnfdlLDDdeEDLHJJBBbfd`bcCK[SCGGEGFFB@@HIIKCAIMM]UQAEMmikKJHXxzz{{kcCAackjzZ[[{sqq

```

Try it online!

I/O is done by character (actually byte) code, because Incident is a horrible low-level tarpit with no numeric I/O routines. The program can handle numbers greater than 255 by using multiple characters (enter the number you want in little-endian base 256).

## Explanation

In Incident, the tokens are not fixed by the language but rather defined by the program – any substring of the program that appears exactly 3 times is a token, unless it's contained within another token or overlaps another token. Additionally, the actual bytes that make up a token don't matter – just how the copies of the tokens are arranged relative to the other tokens.

In this program, I picked single-byte tokens to implement the program, choosing the bytes that represent them in order to get an approximate "only one bit changes from one byte to the next" property, and added extra bytes (that appear more or fewer than 3 times) as comments in order to make the property perfect. Thus, every occurrence of a byte in `]eimQSUxXZ` `fNs` `cCn` is a comment, because it appears 1, 2, or 4 times respectively. (I had to double one of the `n`s to "detokenise" `n`; other padding characters added to maintain the one-bit-at-a-time property naturally ended up being used 1, 2 or 4 times.) The actual choice of bytes to represent the tokens, and positions of the padding bytes, was mostly done via a computer search (and the algorithm wasn't optimal, so this is probably golfable, but I haven't found anything better so far).

Removing the comments gives us the following 72-byte program, whose token arrangement was chosen by hand:

```
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq

```

Incident programs are generally very hard to explain, so I'm going to attempt to explain this one by highlighting subsets of characters and explaining what they do. I think I've covered the whole program here, but in a program as unreadable as this one (and which was partially computer-generated, so I didn't entirely write it myself), it's quite possible that I've missed something.

### Starting the program, and the first two bits of input

```
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
@     b               HJJBBb  b         @@H          k  Hzz{{k  k

```

Incident reads standard input a bit at a time (which is the only reason why writing this program is remotely viable in Incident – it's normally a horrible language for just about anything). If the three uses of a token are split as a lone token and a touching pair (e.g. `@``@@`), that represents a jump from the single token to the double token, so the program starts by jumping from the `@` at the start to `@@`.

To do input (the usual way, at least), the program must run into the middle of the three occurrences of a token, without ever hitting the first or last use. `H` here therefore reads the first bit (the least significant bit of the input number), and jumps to the first or last `H` accordingly.

In either case, we then cross over a couple of jump labels (`JJBB` or `zz{{`). For a *backwards* jump (which all of `JBz{` are), it's safe to do this; control just moves past the jump label, like you'd expect for a jump label. (This is not safe for a *forwards* jump – you're encountering the middle of three uses without ever hitting the first or last, which is interpreted as an attempt to read input rather than an attempt to move past a jump label.)

This part of the program finishes by reading the second bit of input, using `b` or `k` based on whether the first bit read was a 0 or a 1 bit. Control flow is thus sent to one of four locations, based on the two most recent bits read.

### Output subroutines

```
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
      bj                      bK                     kK         kj
       j  lljdl                                                  j
                               K           IIKAI      K
             d  DDdED       d                 A MMAEM         A
         L     L   E L           GGEG              E

```

The outer uses (first and last) of any given token are basically subroutine calls, with the middle use being the entry and exit point from the subroutine (i.e. running the first or last token will jump to the middle, and then returning to the middle will return to just after the token you called it from).

We want to output 0 if we read two 0s or two 1s. We want to output 1 if we read 01 or 10. Output in Incident is done by calling a subroutine using the token that's the centremost token in the entire program (which for this program is `E`; the `L` token is dead code, with none of its uses ever reached, and it exists only to push the centre of the program over an `E`); its left call point outputs a `0` bit as a side effect, and its right call point outputs a `1` bit as a side effect. So we have a `d` subroutine that outputs 0 bits, and an `A` subroutine that outputs 1 bits, both via calling `E`. Because subroutines have their entry and exit points in the same place, we wrap each of them in a backwards jump to allow control flow to return to the point from which they were called.

Each Incident subroutine must be called from exactly 2 points in the program, but we have three locations that want to output `0` bits (and three locations that want to output `1` bits). The usual way to fix this is with helper/wrapper subroutines that contain nothing but a call to another subroutine, here `j` and `K`; `j` outputs `0` bits by calling `d`, and `K` outputs `1` bits by calling `A`. These wrapper subroutines use up one of the call points of the subroutine they're calling, but provide two (an increase of one call point), so this technique makes it possible to call `d` and `A` from three points each.

In order to convert regular little-endian binary to Gray code, we basically need to output, for each bit, the XOR of that bit with the previous bit. The program has jumped to one of four locations based on whether the two bits we just read are `00`, `01`, `10`, or `11`; and each of these locations immediately calls an output subroutine to output `0`, `1`, `1`, or `0` respectively.

### Moving from one bit to the next

```
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
       jF                BBb         FFB
                               K[                          {{k     [[{
                       JJ  b                          KJ
                                                         zz  k   jz

```

After we've produced our output, we need to move onto the next bit. The output of the binary-to-Gray conversion only ever depends on the most recent two bits, so we effectively just need to jump to the same location that the `H` which reads the first bit does – after producing output after a `0` bit, we need to jump to the `b` that handled input after a `0` bit is read, and after producing output after a `1` bit, we need to jump to the `k` that handled input after a `1` bit is read.

This is almost very straightforward, just using jumps to return to the relevant part of the program. After reading `10` or `11`, we can do exactly that (using `J` and `z` respectively as the jump labels) – those are backward jumps, so control flow can safely pass over their jump labels. After reading `00` or `01`, though, we would need to jump forward in the program rather than backward jumps, and control flow can't pass over a forward jump label safely. So instead, we need to jump forwards to an arbitrary point in the code, and then backwards to the point we actually need, allowing the two control flows to merge safely. This is done with `F` then `B` after reading `00`, and `[` then `{` after reading `01`.

This handles most of the program – the situation we're in after reading, say, `1110` is identical to the situation we're in after reading `10`, except that we've output two bits already (but there's no need to remember which two bits they were, because those never become relevant later).

### Ending the program

```
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
 ``                        bd`
   aa                                                        kAa
     q                                                                qq

```

Eventually, we reach the end of the input, causing an end-of-file condition. Incident handles end of file by not jumping at all – it just falls through from the input instruction to the next instruction. To convert binary to Gray codes, we need to handle this by outputting a copy of the most recently input bit (because the most significant bit of the input is output directly in addition to being XORed with the bit below), then quitting the program.

If the most recently read bit was a `0` bit, so we're using `b` to read input, then we fall through to `d` (which outputs `0` bits), then use ``` to jump back to the start of the program. Likewise, if we read a `1` bit and thus used `k` to read input, we fall through to `A` to output a `1` bit and `a` to jump back to the start of the program. In either case, `q` jumps to the end of the program and exits.

This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). You could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate `q` – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. I'm not sure whether the program could be shortened like this, because a lot of it would have to be redone (e.g. the centre of the program would move so you'd need to place the output routine in a different place, and that means moving the padding elsewhere in the program).
> 16 votes

# Answer
# 05AB1E, 11 bytes

```
;3ss{Ƶ}]\\^

```

Try it online or verify all test cases.

The core program without the would have been 2 bytes:

```
;^

```

Try it online or verify all test cases.

**Explanation:**

*Explanation of the core program:*

```
;    # Halve the (implicit) input
 ^   # Implicitly truncate it to an integer, and bitwise-XOR it with the
     # (implicit) input
     # (after which the result is output implicitly)

```

The idea is to add no-ops between them without changing the functionality. I started by creating a generator to get all 05AB1E character-pairs that differ by a single bit. Before the `^`, only `\` and `V` seemed reasonable candidates (`\` discards the top of the stack; and `V` pops the top of the stack and saves it in variable `Y`). From there it was kinda trial-and-error to see what characters I could use. Because the `;` and `^` differ by 4 bits, at least that many no-op bytes in between are necessary. Although I have the feeling the byte-count can still be improved perhaps, 9 no-op bytes to toggle 4 specific bits isn't too bad I guess.

*Explanation of the new program:*

```
;           # Halve the (implicit) input-integer
            # No-ops:
 3          #  Push 3
  s         #  Swap the two values on the stack
   s        #  Swap them back
    {       #  Sort the digit(s) of 3
     Ƶ}     #  Push compressed integer 226
       ]    #  Close all open if-statements and loops
        \   #  Discard the top of the stack (the 226)
         \  #  Discard the top again (the 3)
          ^ # Implicitly truncate the halved input to an integer, and bitwise-XOR
            # it with the (implicit) input
            # (after which the result is output implicitly)

```

(See this 05AB1E tip (section *How to compress large integers?*) to understand why `Ƶ}` is `226`.)

*The bytes in 05AB1E's codepage of `;3ss{Ƶ}]\\^` are:*

```
;  00111011
       v
3  00110011
    v
s  01110011
s  01110011
       v
{  01111011
        v
Ƶ  01111111
         v
}  01111101
     v
]  01011101
          v
\  01011100
\  01011100
         v
^  01011110

```
> 10 votes

# Answer
# Jelly, 4 bytes

```
HL\^

```

A monadic Link that accepts an integer and yields a list of one integer. ...Or a full program that accepts an integer and prints the result.

The code's bytes only change by one bit each time, as required:

| Byte | Hex | Binary |
| --- | --- | --- |
| `H` | **48** | **01001000** |
| `L` | **4C** | **01001100** |
| `\` | **5C** | **01011100** |
| `^` | **5E** | **01011110** |

**Try it online!**

### How?

The shortest code that starts with `H` (halve) and ends with `^` (XOR the input) for which the code in between has no adverse effect while fulfilling the source-code restriction of only changing by at most one bit from byte to byte.

```
HL\^ - Link: integer, N
H    - halve N                    -> N/2
  \  - cumulative reduce with:
 L   -   length                   -> [N/2]
   ^ - (floor to integer) XOR (N) -> [floor(N/2) XOR N]

```

---

###### Note

`:2` (integer divide by two) seems like a reasonable start as the bytes already only differ by one bit, but the next available bytes (`Ø"036:rḶ`) don't really help us advance.
> 7 votes

# Answer
# Brainfuck, ~~425~~ 421 bytes

*-4 bytes thanks to @Jiří*

```
,()9;{[YIMm-/?>?;+*:>?;+*(8<<=}]_^~>?;{[YIMm-/?>>?;+*(8<<=?;{[YIMm-/?>>?=-/?>?;+*(8<=}]_^~>>?;{[YIMm-/?>>>>?;+*(8<<=}]}|<<<<=}]_^~>>>?;{[YIMm-=<<<=?;+*:>>>?=}]}|>>>?;{[YIMm-=}]}|<<<<<<<=-/?;{[[Z^~>>>>>>?;{[Z^~>>>?=}]_OKk++;{[YIMm-=<<<=}]}|<<<=-=}]_^~>?=}]_^~>>>?;{[ZXx|<=}]_^~>?;{[[Z^~>?;{[Z^~>?=-=<=-=}]_^~>?;{[ZXx|<<<<<<=?;+*:>>>>>>?;{[YIMm-=}]]_^~>?=}]_OKk+;{[ZXx|<=?;{[ZXx|<<<=?;++*:>>>?=-=}]}|<<=}]_^~>>?=}]}|<<<=?/.
```

Attempt This Online!

Thanks to this answer for the XOR algorithm and to this answer for the division by 2.

Expanded code:

```
,

duplicate the input in two cells
[->+>+<<]

>

divide n by two
    [ 0
        -
        >>+ set marker 2
        << 0
        [->>->+<] dec marker inc n/2
        >> 2 or 4
        [->>>>+<<]
        <<<<
    ]
    >>>
    [-<<<+>>>]

set temp cell to zero
>>>[-]

<<<<<<<

xor
-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>-<-]>[<<<<<<+>>>>>>[-]]>]+[<[<<<++>>>-]<<]>>]

<<<.

```

The code has been made safe with this program. **I invite anyone who's better at golfing in Brainkfuck than me to use it to make shorter solutions!**
> 6 votes

---
Tags: code-golf, restricted-source, source-layout
---


# Question
Title: Implement the slowest possible sorting algorithm that retains a fast best case
I have recently been on a quest to create really really slow sorting algorithms that make Bogosort seem like it is the best.

The task is simple: **Sort an array of integers in as long average time as possible, with the average Bachmann–Landau notation begin as high as possible, while keeping the best case performance fast**

# The rules:

* Everything happening has to be productive in some sense. Using a slow function to generate numbers is not counted as productive (unless that is one of the faster ways to get those exact numbers, and your algorithm depends on them for some reason).
* Best case\* time performace has to be \\$o(2^n)\\$ (i.e. faster than \\$2^n\\$).

\*The fast best case is not allowed to be on already sorted data.

# You need:

* Specify language
* The code / pseudocode
* An explanation + big O-notation for best and average case.

# Scoring:

Scoring will be based in order of this list:

* Highest average big O-notation
* Being deterministic
* Fastest best case
* Working on sets that are not strictly totally ordered
* Earliest submission

For example, if two submissions have the same average runtime, but only one of them is deterministic, that one will win. If they are both either deterministic or non-deterministic, they are judged based on the fastest best case, and so on.

## Example:

fastSort works by giving every item a randomly generated number, putting the lowest one first, then recursively sorting the rest based on those new values. If the resulting array is not sorted, then it loops until it is.

The random marking of card numbers have a \\$\frac{1}{n!}\\$ chance of being correct, so it will on average take \\$n!\\$ attempts to select the right numbers, and for each of these attempts, the method calls itself with 1 lower length. Thus the average time complexity becomes:

$$ \begin{align} T(n) &= n! \cdot T(n-1) \\ &= n! \cdot (n-1)! \cdot T(n-2) \\ &= n! \cdot (n-1)! \cdot (n-2)! \cdot ... \cdot 2! \cdot 1! \cdot T(0) \\ &= T(0) \cdot \prod\_{k=1}^n n! := T(0) \cdot sf(n)) = \underline{O(sf(n))} \end{align} $$ \\$\big\[sf(x)\\$ is the superfactorial\\$\big\]\\$

The best case, excluding the case of already sorted data, is if the initial labeling is correct on every level down. This will cause the algorithm to go as many steps down as it takes to come to a part where the rest of the elements are already sorted, and then go back up again. The best of these cases is if only two elements have been swapped, in which case, it only goes 1 level down, and thus has a best case runtime of \\$O(n)\\$.

Looking at space efficiency: Every step down needs to store n-(#steps) numbers, so the maximum amount of numbers needed at any given time is: $$ \sum\_{k=1}^n k = \frac{n^2+n}{2} = O(n^2) $$

Since the only time we compare the actual inputs, is in checking whether the array is sorted, means that it will work on any partially ordered set.

I have chosen to call it fastSort for obvious reasons. Here is a possible pseudocode-implementation (nothing language specific):

```
class Card<T>
{
    T value
    stack<int> cards
}

function fastSortHelper(cardArr: array<Card<T>>, offset: int)
{
    if (offset >= cardArr.length) then return

    while (cardArr is not sorted based on their top card)
    {
        push 1 random number to every cards stack
        find the element with the smallest top card, and swap it with the first.
        fastSortHelper(cardArr, offset + 1)
        pop the top number from every cards stack
    }
}

function fastSort (arr: array<T>, start: int, end: int)
{
    int length := end - start
    array<Card<T>> cardArr[length]
    initialize cardArr with the values from arr in [start, end), and an empty stack

    while (cardArr is not sorted based on their values)
    {
        push 1 random number to every cards stack
        find the element with the smallest top card, and swap it with the first.
        fastSortHelper(cardArr, 1)
        pop the top number from every cards stack
    }

    move the values from cardArr back into arr, in the correct range
}

```

# Answer
> 2 votes
# Python 3, \\$O\left(n^2\left(max\left(a\right)-min\left(a\right)+1\right)^{n-1}\right)\\$

```
import itertools

def sort(a):
    m, n, l = min(a), max(a), len(a)
    for possible in itertools.product(range(m, n + 1), repeat=l):
        if (
            all(possible.count(i) == a.count(i) for i in possible) and
            all(i <= j for i, j in zip(possible, possible[1:]))
        ):
            return list(possible)

```

Try it online!

When input only contains \\$k\\$ and \\$k+1\\$ each \\$\frac{n}{2}\\$ times. Its complexity is \\$O\left(2^{\frac{n}{2}}\cdot n^2\right)\\$.

---
Tags: code-challenge, sorting, restricted-complexity
---


# Question
Title: Find the number of leading zeroes in a 64-bit integer
**Problem:**

Find the number of leading zeroes in a 64-bit signed integer

**Rules:**

* The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm
* The output should be validated against the 64-bit signed integer representation of the number, regardless of language
* Default code golf rules apply
* Shortest code in bytes wins

**Test cases:**

These tests assume two's complement signed integers. If your language/solution lacks or uses a different representation of signed integers, please call that out and provide additional test cases that may be relevant. I've included some test cases that address double precision, but please feel free to suggest any others that should be listed.

```
input                output   64-bit binary representation of input (2's complement)
-1                   0        1111111111111111111111111111111111111111111111111111111111111111
-9223372036854775808 0        1000000000000000000000000000000000000000000000000000000000000000
9223372036854775807  1        0111111111111111111111111111111111111111111111111111111111111111
4611686018427387903  2        0011111111111111111111111111111111111111111111111111111111111111
1224979098644774911  3        0001000011111111111111111111111111111111111111111111111111111111
9007199254740992     10       0000000000100000000000000000000000000000000000000000000000000000
4503599627370496     11       0000000000010000000000000000000000000000000000000000000000000000
4503599627370495     12       0000000000001111111111111111111111111111111111111111111111111111
2147483648           32       0000000000000000000000000000000010000000000000000000000000000000
2147483647           33       0000000000000000000000000000000001111111111111111111111111111111
2                    62       0000000000000000000000000000000000000000000000000000000000000010
1                    63       0000000000000000000000000000000000000000000000000000000000000001
0                    64       0000000000000000000000000000000000000000000000000000000000000000

```

# Answer
# x86\_64 machine language on Linux, 6 bytes

```
0:       f3 48 0f bd c7          lzcnt  %rdi,%rax
5:       c3                      ret

```

Requires Haswell or K10 or higher processor with `lzcnt` instruction.

Try it online!
> 42 votes

# Answer
# Hexagony, ~~78~~ 70 bytes

```
2"1"\.}/{}A=<\?>(<$\*}[_(A\".{}."&.'\&=/.."!=\2'%<..(@.>._.\=\{}:"<><$

```

Try it online!

Isn't this challenge too trivial for a practical language? ;)

side length 6. I can't fit it in a side length 5 hexagon.

### Explanation
> 25 votes

# Answer
# Python, 31 bytes

```
lambda n:67-len(bin(-n))&~n>>64

```

Try it online!

The expresson is the bitwise `&` of two parts:

```
67-len(bin(-n)) & ~n>>64

```

The `67-len(bin(-n))` gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the `-0b` prefix. The negation is a trick to adjust for `n==0` using that negating it doesn't produce a `-` sign in front.

The `& ~n>>64` makes the answer instead be `0` for negative `n`. When `n<0`, `~n>>64` equals 0 (on 64-bit integers), so and-ing with it gives `0`. When `n>=0`, the `~n>>64` evaluates to `-1`, and doing `&-1` has no effect.

---

**Python 2, 36 bytes**

```
f=lambda n:n>0and~-f(n/2)or(n==0)*64

```

Try it online!

Arithmetical alternative.
> 12 votes

# Answer
# C (gcc), 14 bytes

```
__builtin_clzl

```

Works fine on tio

# C (gcc), ~~35~~ 29 bytes

```
f(long n){n=n<0?0:f(n-~n)+1;}

```

Try it online!

Than Dennis for 6 bytes

# C (gcc) compiler flags, 29 bytes by David Foerster

```
-Df(n)=n?__builtin_clzl(n):64
```

Try it online!
> 11 votes

# Answer
# Java 8, ~~32~~ 26 bytes.

`Long::numberOfLeadingZeros`

Builtins FTW.

-6 bytes thanks to Kevin Cruijssen

Try it online!
> 9 votes

# Answer
# JavaScript (Node.js), 25 bytes

Takes input as a BigInt literal.

```
f=x=>x<0?0:x?f(x/2n)-1:64

```

Try it online!

Or **24 bytes** by returning *false* instead of \\$0\\$.
> 6 votes

# Answer
# Python 3, 34 bytes

```
f=lambda n:-1<n<2**63and-~f(2*n|1)

```

Try it online!
> 5 votes

# Answer
# , 18 bytes

```
0{[:I.1,~(64$2)#:]

```

Try it online!

# , 19 bytes

```
1#.[:*/\0=(64$2)#:]

```

Try it online!

## Explanation:

```
                #:  - convert
                  ] - the input to
          (64$2)    - 64 binary digits
         =          - check if each digit equals
        0           - zero
   [:*/\            - find the running product
1#.                 - sum

```
> 5 votes

# Answer
# Perl 6, 18 bytes

*-2 bytes thanks to Jo King*

```
64-(*%2**64*2).msb

```

Try it online!
> 5 votes

# Answer
# Ruby, 22 bytes

```
->n{/[^0]/=~"%064b"%n}

```

Try it online!
> 5 votes

# Answer
# Haskell, 56 bytes

Thanks xnor for spotting a mistake!

```
f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n

```

Might allocate quite a lot of memory, try it online!

Maybe you want to test it with a smaller constant: Try 8-bit!

## Explanation

Instead of using `mapM(pure[0,1])[1..64]` to convert the input to binary, we'll use `mapM(pure[1,0])[1..64]` which essentially generates the inverted strings \\$\lbrace0,1\rbrace^{64}\\$ in lexicographic order. So we can just sum the \\$1\\$s-prefix by using `sum.fst.span(>0)`.
> 4 votes

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

```
·bg65αsd*

```

I/O are both integers

Try it online or verify all test cases.

**Explanation:**

```
·         # Double the (implicit) input
          #  i.e. -1 → -2
          #  i.e. 4503599627370496 → 9007199254740992
 b        # Convert it to binary
          #  i.e. -2 → "ÿ0"
          #  i.e. 9007199254740992 → 100000000000000000000000000000000000000000000000000000
  g       # Take its length
          #  i.e. "ÿ0" → 2
          #  i.e. 100000000000000000000000000000000000000000000000000000 → 54
   65α    # Take the absolute different with 65
          #  i.e. 65 and 2 → 63
          #  i.e. 65 and 54 → 11
      s   # Swap to take the (implicit) input again
       d  # Check if it's non-negative (>= 0): 0 if negative; 1 if 0 or positive
          #  i.e. -1 → 0
          #  i.e. 4503599627370496 → 1
        * # Multiply them (and output implicitly)
          #  i.e. 63 and 0 → 0
          #  i.e. 11 and 1 → 11

```
> 4 votes

# Answer
# Jelly,  ~~10~~  9 bytes

-1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply )

```
ḤBL65_×AƑ

```

A monadic Link accepting an integer (within range) which yields an integer.

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

---

The 10 was `ḤBL65_ɓ>-×`

Here is another 10 byte solution, which I like since it says it is "BOSS"...

```
BoṠS»-~%65

```

Test-suite here

...`BoṠS63r0¤i`, `BoṠS63ŻṚ¤i`, or `BoṠS64ḶṚ¤i` would also work.

---

Another 10 byter (from Dennis) is `æ»64ḶṚ¤Äċ0` (again `æ»63r0¤Äċ0` and `æ»63ŻṚ¤Äċ0` will also work)
> 3 votes

# Answer
# Powershell, 51 bytes

```
param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1

```

Test script:

```
$f = {

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1

}

@(
    ,(-1                   ,0 )
    ,(-9223372036854775808 ,0 )
    ,(9223372036854775807  ,1 )
    ,(4611686018427387903  ,2 )
    ,(1224979098644774911  ,3 )
    ,(9007199254740992     ,10)
    ,(4503599627370496     ,11)
    ,(4503599627370495     ,12)
    ,(2147483648           ,32)
    ,(2147483647           ,33)
    ,(2                    ,62)
    ,(1                    ,63)
    ,(0                    ,64)
) | % {
    $n,$expected = $_
    $result = &$f $n
    "$($result-eq$expected): $result"
}

```

Output:

```
True: 0
True: 0
True: 1
True: 2
True: 3
True: 10
True: 11
True: 12
True: 32
True: 33
True: 62
True: 63
True: 64

```
> 3 votes

# Answer
# Java 8, 38 bytes

```
int f(long n){return n<0?0:f(n-~n)+1;}

```

Input as `long` (64-bit integer), output as `int` (32-bit integer).

Port of *@l4m2*'s C (gcc) answer.

Try it online.

**Explanation:**

```
 int f(long n){       // Recursive method with long parameter and integer return-type
   return n<0?        //  If the input is negative:
           0          //   Return 0
          :           //  Else:
           f(n-~n)    //   Do a recursive call with n+n+1
                  +1  //   And add 1

```

---

EDIT: Can be **26 bytes** by using the builtin `Long::numberOfLeadingZeros` as displayed in *@lukeg*'s Java 8 answer.
> 3 votes

# Answer
# APL+WIN, 34 bytes

```
+/×\0=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕

```

Explanation:

```
n←⎕ Prompts for input of number as integer

((2*63)××n) If n is negative add 2 to power 63

(63⍴2)⊤ Convert to 63 bit binary

(0>n), Concatinate 1 to front of binary vector if n negative, 0 if positive

+/×\0= Identify zeros, isolate first contiguous group and sum if first element is zero

```
> 3 votes

# Answer
# C# (Visual C# Interactive Compiler), 42 bytes

```
x=>x!=0?64-Convert.ToString(x,2).Length:64

```

Try it online!

# C# (Visual C# Interactive Compiler), 31 bytes

```
int c(long x)=>x<0?0:c(x-~x)+1;

```

Even shorter, based off of @l4m2's C (gcc) answer. Never knew that you could declare functions like that, thanks @Dana!

Try it online!
> 3 votes

# Answer
# Swift (on a 64-bit platform), 41 bytes

Declares a closure called `f` which accepts and returns an `Int`. This solution only works correctly 64-bit platforms, where `Int` is `typealias`ed to `Int64`. (On a 32-bit platform, `Int64` can be used explicitly for the closure’s parameter type, adding 2 bytes.)

```
let f:(Int)->Int={$0.leadingZeroBitCount}

```

In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means `Int` can have methods and properties, such as `leadingZeroBitCount` (which is required on all types conforming to the standard library’s `FixedWidthInteger` protocol).
> 2 votes

# Answer
# Perl 5, 37 bytes

```
sub{sprintf("%064b",@_)=~/^0*/;$+[0]}

```

Try it online!

Or this 46 bytes if the "stringification" is not allowed: sub z

```
sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}

```
> 2 votes

# Answer
# Haskell, 24 bytes

```
f n|n<0=0
f n=1+f(2*n+1)

```

Try it online!

This is basically the same as Kevin Cruijssen's Java solution, but I found it independently.

The argument should have type `Int` for a 64-bit build, or `Int64` for anything.

## Explanation

If the argument is negative, the result is immediately 0. Otherwise, we shift left, *filling in with ones*, until we reach a negative number. That filling lets us avoid a special case for 0.

Just for reference, here's the obvious/efficient way:

# 34 bytes

```
import Data.Bits
countLeadingZeros

```
> 2 votes

# Answer
# Clean, 103 bytes

Uses the same *"builtin"* as ceilingcat's answer.

```
f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}

```

Try it online!

# Clean, 58 bytes

```
import StdEnv
$0=64
$i=until(\e=(2^63>>e)bitand i<>0)inc 0

```

Try it online!
> 1 votes

# Answer
# Stax, 10 bytes

```
în»╧3(∞┼⌠g

```

Run and debug it

It's a port of Kevin's 05AB1E solution.
> 1 votes

# Answer
# Wolfram Language (Mathematica), 41 bytes

The formula for positive numbers is just `63-Floor@Log2@#&`. Replacement rules are used for the special cases of zero and negative input.

The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.

```
63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&

```

Try it online!

@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "`BitLength[n]` is effectively an efficient version of `Floor[Log[2,n]]+1`. " It automatically handles the case of zero correctly reporting `0` rather than `-∞`.

# Wolfram Language (Mathematica), 28 bytes

```
Boole[#>=0](64-BitLength@#)&

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-p`, 42 bytes

```
1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a

```

Try it online!

Longer than a bitstring based solution, but a decent math based solution.
> 1 votes

# Answer
# APL(NARS), 15 chars, 30 bytes

```
{¯1+1⍳⍨⍵⊤⍨64⍴2}

```

test for few numbers for see how to use:

```
  f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
  f ¯9223372036854775808
0
  f 9223372036854775807
1

```
> 1 votes

# Answer
# Rust, 18 bytes

```
i64::leading_zeros

```

Try it online!
> 1 votes

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

```
+/&\~(64#2)\

```

Try it online!

`(64#2)\` encode the argument as 64 bits

`~` bitwise not

`&\` cumulative boolean and

`+/` sum
> 1 votes

# Answer
# PHP, ~~50~~ 46 bytes

```
for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;

```

Run as pipe with `-R` or try it online,

`<?=$argn<0?0:0|64-log($argn+1,2);` has rounding issues; so I took the long way.
> 1 votes

# Answer
bitNumber - math.ceil (math.log(number) / math.log(2))

e.g 64 bit NUMBER : 9223372036854775807 math.ceil (math.log(9223372036854775807) / math.log(2)) ANS: 63
> 1 votes

# Answer
# Charcoal, 15 bytes

```
Ｉ⁻⁶⁴Ｌ↨﹪ＮＸ²¦⁶⁴¦²

```

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

```
    Ｌ           Length of
       Ｎ        Input as a number
      ﹪         Modulo
         ²      Literal 2
        Ｘ       To the power
           ⁶⁴   Literal 64
     ↨          Converted to base
              ² Literal 2
 ⁻              Subtracted from
  ⁶⁴            Literal 64
Ｉ               Cast to string
                Implicitly print

```

The `¦`s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts `0` into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.
> 0 votes

# Answer
# Java 8, 49 bytes (broken)

I misread the problem, check back later for a new solution

```
n->{int i=0;while(n%10==0){n/=10;i++;}return i;};

```

Try it online!
I opted for a loop-based solution instead of recursion or built-ins.
> 0 votes

# Answer
# MMIX, 36 bytes (9 instructions)

Hexdump (jelly code page):

```
00000000: e3ff4080 e6ff1020 e5ff0408 e4ff0102  ẉ”@⁰ȧ”Ñ ẓ”¥®ỵ”¢£
00000010: dc0000ff dc00ff00 27ff0001 da00ff00  ṇ¡¡”ṇ¡”¡'”¡¢ḷ¡”¡
00000020: f8010000                             ẏ¢¡¡

```

Disassembled:

```
clz SETL  $255,#4080
    INCML $255,#1020
    INCMH $255,#0408
    INCH  $255,#0102
    MOR   $0,$0,$255    // reverse byte order of input
    MOR   $0,$255,$0    // reverse bit order of input within bytes
    SUBU  $255,$0,1     // y = x - 1
    SADD  $0,$255,$0    // x = popcnt(y & ~x)
    POP   1,0           // return x

```

\`\`\`
> 0 votes

---
Tags: code-golf, math, restricted-source, binary, bitwise
---


title: String Zip and Sort

text:
# Question
Title: String Zip and Sort
Given a list of strings, output a single string formed by taking a character from each string at each position, sorting them by ASCII ordinal, and appending them in order to the output string. In other words, for `n` input strings, the first `n` characters of the output will be the first characters of each of the inputs sorted by ordinal, the second `n` characters of the output will be the second characters of each of the inputs sorted by ordinal, and so on. You may assume that the strings are all of equal length, and that there will be at least one string. All strings will be composed of only ASCII printable characters (ordinals 32-127).

Reference implementation in Python (try it online):

```
def stringshuffle(strings):
  res = ''
  for i in range(len(strings[0])):
    res += ''.join(sorted([s[i] for s in strings],key=ord))
  return res

```

Examples:

```
"abc","cba" -> "acbbac"
"HELLO","world","!!!!!" -> "!Hw!Eo!Lr!Ll!Od"

```

### Rules

* Standard loopholes are forbidden
* This is , so shortest answer in bytes wins

# Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 64526; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
```

# Answer
> 10 votes
# GS2, 4 bytes

```
*Ü■/

```

This reads the strings from STDIN, separated by linefeeds.

The source code uses the CP437 encoding. Try it online!

### Test run

```
$ xxd -r -ps <<< '2a 9a fe 2f' > zip-sort.gs2
$ echo -e 'HELLO\nworld\n!!!!!' | gs2 zip-sort.gs2
!Hw!Eo!Lr!Ll!Od

```

### How it works

```
*       Split the input into the array of its lines.
 Ü      Zip the resulting array.
  ■     Map the rest of the program over the resulting array.
   /        Sort.

```

# Answer
> 7 votes
## Haskell, ~~39~~ 36 bytes

```
import Data.List
(>>=sort).transpose

```

Usage example: `((>>=sort).transpose) ["HELLO","world","!!!!!"]` -\> `"!Hw!Eo!Lr!Ll!Od"`.

Transpose the list of strings, map `sort` over it and concatenate the resulting list of strings (`>>=` in list context is `concatMap`).

# Answer
> 4 votes
# Pyth, 5 bytes

Zips(`C`) the input(`Q`), `M`aps `S`ort, then `s`ums.

```
sSMCQ

```

Try it online.

# Answer
> 4 votes
# TeaScript, 9 bytes

```
_t¡ßlp¡)µ

```

TeaScript has all the right built-ins implemented in all the wrong ways.

Try it online

## Ungolfed

```
_t()m(#lp())j``

```

## Explanation

```
_t()        // Transposes input array
    m(#     // Loops through inputs
       lp() // Sorts characters by char code
     )
j``         // Joins back into string

```

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

```
a=>a[0].replace(/./g,(c,i)=>a.map(w=>w[i]).sort().join``)

```

# Answer
> 3 votes
# CJam, 5 bytes

```
q~z:$

```

Try it here.

# Answer
> 3 votes
# Python, ~~50~~ 48 bytes

```
lambda x,y=''.join:y(map(y,map(sorted,zip(*x))))

```

*Thanks to @xnor for -2 bytes!*

# Answer
> 3 votes
# Vyxal `d`, 3 bytes

```
∩vs

```

Try it Online!

# Answer
> 2 votes
# Octave, 15 bytes

```
@(a)sort(a)(:)'

```

**Example:**

```
octave:1> (@(a)sort(a)(:)')(["abc";"cba"])
ans = acbbac
octave:2> (@(a)sort(a)(:)')(["HELLO";"world";"!!!!!"])
ans = !Hw!Eo!Lr!Ll!Od

```

# Answer
> 2 votes
# K, 10 bytes

```
,/{x@<x}'+

```

Join (`,/`) the sort of (`{x@<x}`) each (`'`) of the transpose (`+`) of a list of strings.

In action:

```
  ,/{x@<x}'+("HELLO";"world";"!!!!!")
"!Hw!Eo!Lr!Ll!Od"

```

Simple, but K is hurt a bit here by not having a single-character sort function and instead dividing the operation into a scatter-gather index operator `@` and a primitive which yields the permutation vector which would sort a list `<`.

# Answer
> 2 votes
# Stax, 5 bytes

```
LMFop

```

So close to LMNOP :(

Run and debug it at staxlang.xyz!

Put all inputs into one list of strings (`L`), and transpose this list (`M`). For each resulting string (`F`), sort (`o`) and print (`p`) it.

# Answer
> 2 votes
# Pip, 5 bytes

```
SS*Zg
```

Attempt This Online!

# Answer
> 1 votes
# Japt, 12 bytes ~~20~~

```
Ny m_q n q)q

```

Try it online!

## Explanation

```
Ny       // Transpose inputs
  m_     // Maps through each new string
    q    // Split string
    n    // Sort string
    q    // Join
)q       // Join again

```

# Answer
> 1 votes
# Julia, 46 bytes

```
x->(j=join)(map(i->j(sort([i...])),zip(x...)))

```

This creates an unnamed function that accepts an array of strings and returns a string. To call it, give it a name, e.g. `f=x->...`.

Ungolfed:

```
function zipsort{T<:AbstractString}(x::Array{T,1})
    # Splat the input array and zip into an iterable
    z = zip(x...)

    # For each tuple consisting of corresponding characters
    # in the input array's elements, splat into an array,
    # sort the array, and join it into a string
    m = map(i -> join(sort([i...])), z)

    # Take the resulting string array and join it
    return join(m)
end

```

# Answer
> 1 votes
# , 15 chars / 30 bytes

```
Ѩťªï)ć⇀ѨŌ$ø⬯)ø⬯

```

`Try it here (Firefox only).`

Just realized that Lodash's sortBy function works on strings, too.

# Answer
> 1 votes
# C++14, 152 bytes

```
#include<iostream>
#include<regex>
[](auto s){for(int i=0;i<s[0].size();++i){auto r=""s;for(auto k:s)r+=k[i];std::sort(begin(r),end(r));std::cout<<r;}};

```

Not using any advantage of map+zip (guess why)

Ungolfed + usage

```
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main()
{
    auto lambda = [](auto s)
    {
        for (int i = 0; i < s[0].size(); ++i)
        {
            auto r = ""s;
            for (auto k : s)
                r += k[i];
            std::sort(begin(r), end(r));
            std::cout << r;
        }
    };

    std::vector<std::string> data = { "HELLO", "world", "!!!!!" };
    lambda(data);
}

```

# Answer
> 1 votes
# Mathematica, 51 bytes

```
""<>SortBy@ToCharacterCode/@Transpose@Characters@#&

```

String manipulation in Mathematica is expensive...

# Answer
> 1 votes
## Perl 6, 33 bytes

```
{[~] flat ([Z] @_».comb)».sort}

```

Example usage:

```
say {[~] flat ([Z] @_».comb)».sort}(< abc cba >) # acbbca

my &code = my $code = {[~] flat ([Z] @_».comb)».sort}

say code "HELLO","world","!!!!!"; # !Hw!Eo!Lr!Ll!Od

say ((<cba abc>),(<testing gnitset gttseni>)).map($code);
# (acbbac ggtentiststteisenngit)

```

# Answer
> 1 votes
# Jelly, 3 bytes

```
ZṢ€

```

Try it online!

Only valid if considered as a full program: the resulting value is a list of strings, but when it's printed Jelly implicitly flattens it.

```
  €    Map
 Ṣ     sort
Z      over the columns of the input.

```

# Answer
> 1 votes
# PHP, ~~92~~ 91 bytes

```
for($argv[0]='';$a=array_column(array_map(str_split,$argv),$i++|0);print join($a))sort($a);

```

Try it online!

I'm confident this could be done shorter by not trying to use PHP's built-in array functions, but had to try!

### Or 85 bytes

@Night2's swing, done shorter by not trying to use PHP's built-in array functions:

```
for(;''<$argv[1][$i++];print join($a))for($a=[];''<$a[]=$argv[++$$i][$i-1];sort($a));

```

Try it online!

# Answer
> 1 votes
# Japt `-P`, 3 bytes

```
Õmñ

```

Try it here

# Answer
> 1 votes
# PowerShell Core, ~~56~~ 50 bytes

```
-join(($a=$args)[0]|% t*y|%{$a|% c*rs($i++)|sort})

```

*-6 bytes thanks to mazzy*

Try it online!

# Answer
> 1 votes
# Factor, 34 bytes

```
[ flip [ natural-sort ] map-flat ]

```

Attempt This Online!

# Answer
> 1 votes
# rSNBATWPL, 39 bytes

```
x~strfor{flip$x}{y~y sort>}crush-with""

```

Try It Online!

# Answer
> 0 votes
# GolfScript, 8 bytes

```
~zip{$}%

```

Try it online on Web GolfScript.

### How it works

```
~         # Evaluate the input.
 zip      # Zip it.
    {$}%  # Map sort ($) over the resulting array.

```

# Answer
> 0 votes
## Minkolang 0.13, 46 bytes

```
$od0Z2:$zIz:$xd0G2-[i1+z[di0c*+c$r]xz$(sr$Ok].

```

Try it here. Expects input like `"HELLO""world""!!!!!"` (so no commas).

### Explanation

```
$o     Read in whole input as characters
d      Duplicate top of stack (the ")
0Z     Count how often this appears in the stack
2:     Divide by two
$z     Store this in the register (z)
Iz:    Length of stack divided by z (k)
$x     Dump one element from the front/bottom of stack
d      Duplicate top of stack (which is k)
0G     Insert it at the front/bottom of stack
2-     k-2

  [                              Open for loop that repeats k-2 times
   i1+                           Loop counter + 1 (i)
      z[                         Open for loop that repeats z times
        d                        Duplicate top of stack (which is i)
         i                       Loop counter (j)
          0c                     Copy k from front of stack
            *                    Multiply (j*k)
             +                   Add (j*k + i)
              c                  Copy character at position j*k+i to the top
               $r                Swap top two elements of stack (so i is on top)
                 ]               Close for loop
                  x              Dump the top of stack (dump i)
                   z$(           Start a new loop with the top z elements
                      s          Sort
                       r$O       Reverse and output the whole (loop) stack as characters
                          k      Break - exits while loop
                           ].    Close for loop and stop

```

# Answer
> 0 votes
# Clojure/ClojureScript, 43 bytes

```
#(apply str(mapcat sort(apply map list %)))

```

Creates an anonymous function. Written in a ClojueScript REPL, should also be valid Clojure.

Enter it here, then call via `(*1 ["HELLO" "world" "!!!!!"])`. Or do `(def f *1)` and then use `(f ["abc" "cba"])`.

# Answer
> 0 votes
## Ceylon, 166

`String z(String+l)=>String(expand(t(l).map(sort)));[T+]n<T>(T?+i)=>[for(e in i)e else nothing];{[X+]*}t<X>([{X*}+]l)=>l[0].empty then{}else{n(*l*.first),*t(l*.rest)};`

While Ceylon has a `zip` function, it takes only two iterables instead of an iterable of them. `unzip`, on the other hand, takes an iterable of tuples, and I don't want to convert my strings into tuples. So I implemented my own transpose function, inspired by a Haskell implementation which Google found for me somewhere.

```
// zip-sort
//
// Question:  http://codegolf.stackexchange.com/q/64526/2338
// My answer: ...

// Takes a list of strings (same length), and produces
// a string made by concatenating the results of sorting
// the characters at each position.
String z(String+ l) =>
        String(expand(t(l).map(sort)));

// Narrow an iterable of potential optionals to their non-optional values,
// throwing an AssertionError if a null is in there.
[T+] n<T>(T?+ i) =>
        [for (e in i) e else nothing];

// Transpose a nonempty sequence of iterables, producing an iterable of
// sequences.
// If the iterables don't have the same size, either too long ones are
// cut off or too short ones cause an AssertionError while iterating.
{[X+]*} t<X>([{X*}+] l) =>
        l[0].empty
        then {}
        else { n(*l*.first), *t(l*.rest) };

```

The types of `n` and `t` could be defined much more general, but this is Codegolf ;-) (`n` is a special case of what I proposed as `assertNarrow` two weeks ago).

# Answer
> 0 votes
# Red, 85 bytes

```
func[b][repeat c length? b/1[foreach a sort collect[foreach m b[keep m/:c]][prin a]]]

```

Try it online!

# Answer
> 0 votes
## Brev, ~~53~~ 41 bytes

```
(as-list flatten(over(sort args char<?)))

```

Example:

```
((as-list flatten (over (sort args char<?))) "HELLO" "world" "!!!!!")

```

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