title: Find the "unwrapped size" of a list

text:
# Question
Title: Find the "unwrapped size" of a list
Let's define the "unwrapped size" function `u` of a nested list `l` (containing only lists) by the following rules:

* If `l` is empty, then `u(l)` is 1.
* If `l` is non-empty, `u(l)` is equal to the sum of the unwrapped sizes of every element in `l`, plus one.

Your task is to write a program (or function) that takes a list as input and outputs (or returns) the unwrapped size of the list.

## Test Cases:

```
[]                                           ->  1
[[[]],[]]                                    ->  4
[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]] -> 19
[[[[]]]]                                     ->  4

```

This is , so the shortest program (in bytes) wins.

# Answer
> 23 votes
# Retina, 1 byte

```
]

```

Try it online! (The first line enables a linefeed-separated test suite.)

By default, Retina counts the number of matches of the given regex in the input. The unwrapped size is simply equal to the number of `[]` pairs in the input and therefore to the number of `]`.

# Answer
> 11 votes
## Mathematica, 9 bytes

```
LeafCount

```

Turns out there's a built-in for that...

Note that this wouldn't work if the lists actually contained non-list elements. What `LeafCount` really does is count the number of atomic subexpressions. For input `{{}, {{}}}`, the expression actually reads:

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

```

Here the atomic subexpressions are actually the *heads* `List`.

# Answer
> 7 votes
## Brainfuck, ~~71~~ ~~61~~ 59 bytes

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

```

Takes input from STDIN in the format given in the question, and outputs the character whose ASCII code is the list's "unwrapped size."

I'm still a complete amateur at Brainfuck, so there are most likely many optimizations that can still be made.

Try it online!

Ungolfed:

```
read input to tape
>>+[>,]<
current tape: (0 0 1 a b *c)
where abc represents input and * is IP

now we loop over each character (from the end)
this loops assumes we are starting on the (current) last char
and it zeroes the entire string by the time it finishes
[

  subtract 91 from this character
  technically we only subtract 85 here and correct the answer
  with the 6 minus signs below
  >-[<->---]
  current tape: (0 0 1 a b cminus91 *0)

  invert the result and put that in the next cell
  +<------[->[-]<]>
  current tape: (0 0 1 a b 0 *c==91)

  move that result back to the original cell
  [-<+>]<
  current tape: (0 0 1 a b *c==91)

  if the result is true we found a brace
  increment the very first cell if so
  [-<[<]<+>>[>]]<
  current tape: (count 0 1 a *b)

]
current tape: (count *0)

<.

```

# Answer
> 5 votes
# JavaScript (ES6), ~~29~~ 27 bytes

```
f=([x,...a])=>x?f(x)+f(a):1

```

i love it when a recursion turns out this cleanly. This is basically a depth-first search of the input, adding 1 whenever the end of an array is reached.

If an empty array were falsy in JS, this could be 24 bytes:

```
f=a=>a?f(a.pop())+f(a):1

```

But alas, it's not. Other attempts:

```
f=a=>a.reduce((n,x)=>n+f(x),1) // Works, but 3 bytes longer
f=a=>a.map(x=>n+=f(x),n=1)&&n  // Works, but 2 bytes longer
f=a=>(x=a.pop())?f(x)+f(a):1   // Works, but 1 byte longer
f=a=>a[0]?f(a.pop())+f(a):1    // Works, but same byte count
f=a=>a+a?f(a.pop())+f(a):1     // Doesn't work on any array containing 1 sub-array
f=a=>a-1?f(a.pop())+f(a):1     // Same

```

# Answer
> 4 votes
# Perl, ~~9~~ ~~8~~ 7 + 1 = 8 bytes

Requires the `-p` flag

```
$_=y;[;

```

Thanks to @Dada for two byte saves (I'm loving this semicolon exploit btw)

# Answer
> 4 votes
# CJam, ~~7~~ 5 bytes

*Thanks to Peter Taylor for removing 2 bytes! (`e=` instead of `f=:+`)*

```
r'[e=

```

Try it online!

```
r         e# Read input
 '[       e# Push open bracket char
   e=     e# Count occurrences. Implicit display

```

# Answer
> 3 votes
## Python ~~3~~ 2, ~~36~~ 23 bytes

```
lambda x:`x`.count("[")

```

I noticed that `u(l)` is equal to the number of `[` in the string representation of `l`, so this program tries to do that. It could probably be golfed further by finding another way to do this, though...

# Answer
> 3 votes
# 05AB1E, 4 bytes

```
I'[¢

I    Get input as a string
 '[¢ Count the opening square brackets and implicitly print them

```

Try it online!

I think it can be golfed more but that 'I' is mandatory, otherwise the input is considered an actual array instead of a string

# Answer
> 3 votes
# Ruby, 13 (+1) bytes

```
p $_.count ?[

```

Called with `-n` argument:

```
ruby -ne 'p $_.count ?['

```

EDIT: Changed to actually print out the answer

# Answer
> 3 votes
## Labyrinth, 8 bytes

```
&-
#,(/!

```

Try it online!

### Explanation

This counts the opening brackets via a bit of bitwise magic. If we consider the results of the character codes of the bitwise AND of `[`, `,` and `]` with `2`, we get:

```
[ , ]
2 0 0

```

So if we just sum up the result of this operation for each character, we get twice the value we want.

As for the code itself, the 2x2 block at the beginning is a small loop. On the first iteration `&-` don't really do anything except that they put an explicit zero on top of the implicit ones at the bottom of the stack. This will be the running total (and it will actually be negative to save a byte later). Then the loop goes as follows:

```
,   Read character. At EOF this gives -1 which causes the instruction pointer to
    leave the loop. Otherwise, the loop continues.
#   Push the stack depth, 2.
&   Bitwise AND.
-   Subtract from running total.

```

Once we leave the loop, the following linear bit is executed:

```
(   Decrement to turn the -1 into a -2.
/   Divide negative running total by -2 to get desired result.
!   Print.

```

The IP then hits a dead and turns around. When it tries to executed `/` again, the program terminates due to the attempted division by zero.

# Answer
> 2 votes
# Python, 26 bytes

```
f=lambda a:sum(map(f,a))+1

```

Simple recursive formula.

# Answer
> 2 votes
# Brain-Flak, ~~63~~, 61 bytes

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

```

Try it online! 58 bytes of code, and +3 for the `-a` flag enabling ASCII input.

Readable version/explanation:

```
#While non-empty:
{

    #subtract
    ({}[

    #91
    (((()()()){}){}()){({}[()])}{}

    ])

    #if non-zero
    {

        # Remove the difference
        {}

        #Increment the counter on the other stack
        (<>{}())

        #Push a zero onto the main stack
        (<>)
    }

    #pop the left-over zero
    {}

#endwhile
}

#Move back to the stack with the counter, implicitly display
<>

```

# Answer
> 2 votes
# Jelly, 4 bytes

```
ß€S‘

```

Doesn't use string manipulation. Try it online! or verify all test cases.

### How it works

```
ß€S‘  Main link. Argument: A (array)

ß€    Map the main link over A.
  S   Sum. For empty arrays, this yields zero.
   ‘  Increment.

```

# Answer
> 2 votes
# C#, 46 41 bytes

```
int u(string l){return l.Count(c=>c=='[');}

```

l is the string of nested list. Test it here.

# Answer
> 2 votes
# Befunge, ~~22~~ ~~18~~ 16 bytes

```
~:0#@`#.!#$_3%!+

```

TryItOnline!

Edit: Thanks to Martin Ender for shaving off 4 bytes!

Edit2: Credit to David Holderness for optimizing out two more

# Answer
> 2 votes
# Regex, 1 byte

```
]

```

Try it online!

# Answer
> 1 votes
# ///, 13 bytes

```
/[/0//]///,//

```

Output in unary.

Try it online!

**Explanation:**

```
/[/0/          Replace every [ with 0
     /]///,//  Remove every ] and ,

```

# Answer
> 1 votes
# PHP, 35 bytes

```
<?=preg_match_all('/\[/',$argv[1]);

```

`preg_match_all` finds all of the matching instances of the regular expression and returns a number, which is why the short echo tags are needed.

Like most answers, it counts the number of `[` in the input and outputs that number

# Answer
> 1 votes
## Racket 82 bytes

```
(define n 0)(let p((l l))(if(null? l)(set! n(+ 1 n))(begin(p(car l))(p(cdr l)))))n

```

Ungolfed:

```
(define (f l)
  (define n 0)
  (let loop ((l l))
    (if (null? l)
        (set! n (add1 n))
        (begin (loop (first l))
               (loop (rest l)))))
  n)

```

Testing:

```
(f '[])
(f '[[[]] []])
(f '[[[]] [[[[]] []]] [[[]] [[[[]] [[] [[]]]]]]])
(f '[[[[]]]])

```

Output:

```
1
4
19
4

```

# Answer
> 1 votes
# C, ~~48~~ 46 Bytes

Saved two bytes thanks to kirbyfan64sos

```
i;f(char*v){for(i=0;*v;i+=*v++==91);return i;}

i;f(char*v){for(i=0;*v;*v++^91?0:i++);return i;}

```

Test code

```
main()
{
    printf("%d\n", f("[]"));
    printf("%d\n", f("[[[]] []]"));
    printf("%d\n", f("[[[]] [[[[]] []]] [[[]] [[[[]] [[] [[]]]]]]]"));
}

```

Test cases

```
a.exe
1
4
19

```

# Answer
> 1 votes
# , 10 bytes

```
ÓÛ
ÒC0@"

```

Try it online!

This contains some unprintable characters, here is the readable version:

```
ÓÛ
Ò<C-a>C0<esc>@"

```

`<C-a>` represents "ctrl-a" (ASCII `0x01`) and `<esc>` represents the escape key (ASCII `0x1b`).

```
ÓÛ              " Remove all '['s
                "
Ò<C-a>          " Replace what's left with '<C-a>' (the increment command)
      C         " Delete this line
       0<esc>   " And replace it with a '0'
             @" " Run what we just deleted as V code (A bunch of increment commands

```

More fun, less golfy version:

```
o0kòf]m`jòd

```

Try it online!

```
o0<esc>                     " Put a '0' on the line below us
       k                    " Move back up a line
        ò               ò   " Recursively:
         f]                 "   Move to a right-bracket
           m`               "   Add this location to our jumplist
             j              "   Move down a line
              <C-a>         "   Increment this number
                   <C-o>    "   Move to the previous location
                         d  " Delete the bracket line
                            " Implicitly display

```

# Answer
> 1 votes
## Brainfuck, 28 bytes

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

```

Try it online.

This counts the number of input characters divisible by 3, i.e. the number of `]` characters.

Alternate 34-byte solution counting `[` characters directly and relying on 8-bit cells:

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

```

# Answer
> 1 votes
# Scala, 15 bytes

```
s=>s.count(92<)

```

Ungolfed:

```
s=>s.count(c=>92<c)

```

`count` counts how many elements satisfy a predicate, in this case `92<`, which is the method `<` of `92`.

# Answer
> 1 votes
# \>\<\>, ~~21~~ ~~20~~ 18 bytes

```
0i:0(90.;n?|3%0=+!

```

Edit: score 1 for goto statements!

Edit 2: Apparently \>\<\> differs from Befunge in that it allows non-zero IP offset after wrapping (in other words, by using a trampoline instruction, I can wrap to (1, 0) instead of (0, 0)). Interesting.

TryItOnline!

# Answer
> 1 votes
# Haskell, ~~20 19~~ 17 bytes

```
f s=sum[1|']'<-s]

```

Try it online!

Takes the list as string and puts a `1` in a list for each `]`, then sums up all the `1`s.

---

**Pointfree version:** (19 bytes)

```
length.filter(>'[')

```

Assumes `, [ ]` are the only chars in the string. Filters the list to get all chars greater than `[`, which are all `]` and returns the length.

Usage:

```
Prelude> length.filter(=='[')$"[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]]"
19

```

# Answer
> 1 votes
# Befunge-98, ~~12~~ ~~11~~ ~~10~~ 9 bytes

```
~3%!+2j@.

```

TryItOnline!

Edit: Thanks to Martin Ender for shaving off a byte

# Answer
> 1 votes
# , 15 bytes

```
i~{1\{nJ+}d}J;J

```

Try it here!

In the input, any commas must be either removed or replaced by spaces.

## Explanation

```
i~{1\{nJ+}d}J;J
i                Read a line of input.
 ~               Evaluate it.
  {        }J;   Define a function and save it into the `J` variable.
                 Currently, the input array is at the top of the stack.
   1\            Push 1 and swap it with the input array.
     {   }d      For each element in the array...
                 Because the array was popped by `d`, 1 is at the TOS.
      nJ+        Recurse and add the result to 1.
              J  Initiate the function call.
                 The result is printed implicitly.

```

## If we're allowed to take work on a string: 10 bytes

```
ie\']-e@-p

```

# Answer
> 1 votes
## tinylisp repl, 39 bytes

```
(d u(q((L)(i L(s(u(h L))(s 0(u(t L))))1

```

Defines a function `u` that can be called like `(u (q ((())()) ))` (for the second test case). Doing it in the repl saves 4 bytes due to auto-closed parentheses.

### Explanation

```
(d u                                      )  Define u as
    (q                                   )    the following, unevaluated
      (                                 )     list (which acts as a function in tinylisp):
       (L)                                   Given arglist of one element, L, return:
          (i L                         )     If L (is nonempty):
              (s(u(h L))             )        Call u on head of L and subtract
                        (s 0        )          0 minus
                            (u(t L))           call u on tail of L
                                      1      Else, 1

```

The `x-(0-y)` construct is necessary because tinylisp doesn't have a built-in addition function, only subtraction.

# Answer
> 0 votes
# Bash + coreutils, 29 bytes

```
f()(echo $1|tr -d -c [|wc -c)

```

# Answer
> 0 votes
# DASH, 14 bytes

```
(ss[len;!> ="]

```

Simply counts `]`'s. Usage:

```
(ss[len;!> ="]"])"[[]]"

```

# Bonus solution, 15 bytes

```
a\@+1sum ->#a#0

```

This one recursively counts from a real list. Usage:

```
(f\@+1sum ->#f#0)[[]]

```

# Answer
> 0 votes
# Java 7, 48 bytes

```
int c(String l){return l.split("\\[").length-1;}

```

If we aren't allowed to use a String as input, then we have the following instead (**60 bytes** \- Try it here):

```
int c(java.util.List l){return(l+"").split("\\[").length-1;}

```

**Ungolfed & test cases:**

Try it here.

```
class M{
    static int c(String l){
        return l.split("\\[").length - 1;
    }

    public static void main(String[]a){
        System.out.println(c("[]"));
        System.out.println(c("[[[]],[]]"));
        System.out.println(c("[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]]"));
        System.out.println(c("[[[[]]]]"));
    }
}

```

**Output:**

```
1
4
19
4

```

# Answer
> 0 votes
## Prolog (SWI), 43 bytes

```
u(L,N):-L=[H|T],u(H,A),u(T,B),N is A+B;N=1.

```

Defines a predicate `u` that takes a list as its first argument and unifies its second argument with the unwrapped size of that list. Verify all test cases on Ideone.

### Explanation

First, `L=[H|T]` tries to unify `L` with a list of the structure "one item `H`, followed by the rest of the list `T`."

* If the list is nonempty, the unification succeeds. We then run `u` recursively on `H` and `T`, getting the results in `A` and `B`. Finally, we add these two and assign the result to `N`.
* If the unification fails, we have an empty list, in which case we need only unify `N` with `1`.

# Answer
> 0 votes
**Clojure, 42 bytes**

Does not leave much room for tweaking as the syntax is so limited. Basically just follows the definition.

```
(fn[i](if(empty? i)1(apply + 1(map f i))))

```

---
Tags: code-golf, string, array, counting
---


title: Find the sortable years

text:
# Question
Title: Find the sortable years
The year 2013 had an interesting property: the digits are consecutive when sorted (0123). Let's call this type of number a *sortable number:* a non-negative integer whose base-10 digits are consecutive after sorting. Unfortunately, this won't happen again until 2031, and after that, not until 2103. Your challenge is to write a program or function that, when given a non-negative integer through any standard method, outputs or returns the next sortable number.

## Rules

* Input and output must be in base 10.
* Output may be in any reasonable format (number literal, string literal, single-item array, ...).
* Your code must produce the proper output within 1 minute for all inputs up to 98764.

## Test cases

```
    0 -> 1
    1 -> 2
    9 -> 10
   10 -> 12
   11 -> 12
   99 -> 102
  233 -> 234
  234 -> 243
  243 -> 312
 2016 -> 2031
 2031 -> 2103
 2103 -> 2130
 2130 -> 2134
 2134 -> 2143
 9876 -> 10234
98764 -> 98765

```

The sortable numbers form A215014. A list of all entries up to 98765 can be found here.

## Scoring

This is , so **the shortest code in bytes wins.**

# Answer
# Python 2, 61 bytes

```
f=lambda n:-~n*(`sorted(`n+1`)`[2::5]in'0123456789')or f(n+1)

```

Try it online!
> 9 votes

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

```
⁵ḶwṢ
‘Ç1#

```

Returns a singleton array. Try it online!

### How it works

```
‘Ç1#  Main link. Argument: n

‘     Increment; yield n+1.
 Ç1#  Apply the helper link to k = n+1, n+2, n+3, ... until one of them maps to a
      truthy value. Yield a singleton array containing that value of k.

⁵ḶwṢ  Helper link. Argument: k

⁵     Set the return value to 10.
 Ḷ    Unlength; yield [0, ..., 9].
   Ṣ  Sort; yield the sorted array of k's decimal digits.
  w   Window-index; yield the 1-based index(truthy) of the digit array in
      [0, ..., 9], 0 (falsy) if not found.

```
> 7 votes

# Answer
# MATL, 8 bytes

```
`QtVSdqa

```

Try it online! Or verify all test cases.

### Explanation

```
`     % Do...while
  Q   %   Add 1. Takes input (implicit) in the first iteration
  t   %   Duplicate
  V   %   Convert to string. This gives an array of chars (same as a string)
      %   representing the digits
  S   %   Sort
  d   %   Consecutive differences between the chars (automatically converted
      %   to ASCII codes)
  q   %   Subtract 1. This gives an array where consecutive differences equal
      %   to 1 are converted to 0, and the rest give a nonzero result
  a   %   True if any value is nonzero. This is the loop condition: if true
      %   (which means at least one consecutive difference was not 1), go on
      %   with the next iteration. Else exit loop
      % End do...while (implicit)
      % Display (implicit)

```
> 6 votes

# Answer
## JavaScript (ES6), ~~64~~ 54 bytes

*Saved a massive 10 bytes, thanks to Neil*

```
f=n=>[...++n+''].sort().some((v,i,a)=>v-i-a[0])?f(n):n

```

### Test cases

```
f=n=>[...++n+''].sort().some((v,i,a)=>v-i-a[0])?f(n):n

console.log(f(0));      // -> 1
console.log(f(1));      // -> 2
console.log(f(9));      // -> 10
console.log(f(10));     // -> 12
console.log(f(11));     // -> 12
console.log(f(99));     // -> 102
console.log(f(233));    // -> 234
console.log(f(234));    // -> 243
console.log(f(243));    // -> 312
console.log(f(2016));   // -> 2031
console.log(f(2031));   // -> 2103
console.log(f(2103));   // -> 2130
console.log(f(2130));   // -> 2134
console.log(f(2134));   // -> 2143
console.log(f(9876));   // -> 10234
console.log(f(98764));  // -> 98765
```
> 5 votes

# Answer
# Pyth - ~~11~~ 10 bytes

```
f}S`TjkU;h

```

Test Suite
> 4 votes

# Answer
## PowerShell v2+, ~~71~~ ~~68~~ 67 bytes

```
param($n)do{$n++}until(-join(0..9)-match-join([char[]]"$n"|sort))$n

```

Try it online!

An iterative solution that runs pretty much instantaneously on my machine.

```
PS C:\Tools\Scripts\golfing> measure-command {.\find-the-sortable-years.ps1 98764} | fl totalseconds

TotalSeconds : 0.0487127

```

Yes, that's a `do`/`until` loop in a code-golf. Sorry, not sorry. Basically we loop upwards from our input `$n` until `$n|sort`ed regex `-match`es against `0123456789`. Then we place `$n` on the pipeline, and output is implicit.

Saved a byte by realizing that `-join(0..9)` is one byte shorter than the literal string `0123456789`.
> 4 votes

# Answer
## Mathematica, 63 bytes

```
#+1//.x_/;!Differences@Sort@IntegerDigits@x~MatchQ~{1...}:>x+1&

```

Replaces `#+1` with the next value as long as `Differences@Sort@IntegerDigits@x~MatchQ~{1...}` is false, which is the condition that the current value is sortable.

Here's another fun idea, that unfortunately ended up being way too long:

```
FirstCase[FromDigits/@Union@@Permutations/@Join@@Array[Range,{9,10},0],x_/;x>#]&

```

In this one, I'm generating all the sortable years first and then I select the first one that is greater than the input.

Some more ideas that didn't turn out to be shorter than the first attempt:

```
#+1//.x_/;Array[Range,{9,10},0]~FreeQ~Sort@IntegerDigits@x:>x+1&
#+1//.x_/;Subsequences@Range[0,9]~FreeQ~Sort@IntegerDigits@x:>x+1&
#+1//.x_/;0~Range~9~FreeQ~{___,##&@@Sort@IntegerDigits@x,___}:>x+1&

```
> 3 votes

# Answer
# PHP, ~~105~~ ~~103~~ 89 bytes

New 89 bytes version thanks to Titus:

```
for(;!$p;){$t=str_split($n=++$argv[1]);sort($t);$p=strstr('0123456789',join($t));}echo$n;

```

Usage:

```
php -r "for(;!$p;){$t=str_split($n=++$argv[1]);sort($t);$p=strstr('0123456789',join($t));}echo$n;" 9000

```

Previous 103 bytes version thanks to Xanderhall:

```
<?for($p=0;!$p;){$t=str_split($n=++$_GET[n]);sort($t);$p=strstr('0123456789',implode($t));}echo "$n\n";

```

Previous 105 bytes version:

```
<?for($n=$_GET[n]+1;;$n++){$t=str_split($n);sort($t);if(strstr('0123456789',implode($t))){echo$n;exit;}}

```

Usage: `sortable-years.php?n=9000` outputs `9678`.

Ungolfed version with test cases:

```
$test = array(0,1,9,10,11,99,233,234,243,2016,2031,2103,2130,2134,9876,98764);

foreach ($test as $argv[1]) {
    for(;!$p;){
        $t=str_split($n=++$argv[1]);
        sort($t);
        $p=strstr('0123456789',join($t));
    }
    echo "$n\n"; // add newline for testing
    $p=false; // reset $p for testing
}

Output:
1
2
10
12
12
102
234
243
312
2031
2103
2130
2134
2143
10234
98765

```

Test online! (New 89 bytes version)

Test online! (Previous 103 bytes version)

Test online! (Previous 105 bytes version)

Execution time maybe \<= 1 second for all the test cases.
> 3 votes

# Answer
# C#, ~~153~~ ~~130~~ 101 bytes (~~122~~ ~~99~~ 83 excluding namespace declarations)

```
using System.Linq;n=>{while(!"0123456789".Contains(string.Concat((++n+"").OrderBy(x=>x))));return n;}

```

**-23 bytes thanks to pinkfloydx33**

**another -29 thanks to Link Ng (I really should have known I don't need to convert it into an array)**

Damn conversions.

(Added bonus this is surprisingly fast)
> 2 votes

# Answer
# Perl 6, 49 bytes

```
{first {$/eqv($/=.comb.sort).minmax.list},$_^..*}

```

## Explanation

```
{

  first

  {

    $/             # sorted list from later

    eqv            # is it equivalent

    (

      $/           # store in match variable ( doesn't need to be declared )
      =
      .comb.sort   # sorted list of digits from currently tested value

    ).minmax       # the Range of digits
            .list  # flattened to a list
  },

  $_  ^..  *       # Range starting just after input

}

```

## Test:

```
# give it a lexical name for clarity
my &code = {first {$/eqv($/=.comb.sort).minmax.list},$_^..*}

my @all = +«'sortable.txt'.IO.lines;

my @gen = code(-1), &code ... ( * >= 98765 );

say @all eqv @gen; # True

say now - INIT now; # 16.3602371

```
> 2 votes

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

-1 thanks to Emigna.

```
[>D{žhså#

```

Try it online!

New description coming when I have time.
> 1 votes

# Answer
# Befunge, 117 bytes

```
&>1+0v
9`#v_>:9+0\4p1+:
1:$<v
0g1+>00p:55+%9+1\4p55+/:!#v_0
v+*g09:<".........." 9p09 <
>:00g-v^<
-9:p09_v|
$v@._<$<>

```

Try it online!

The way we test if a year is sorted is by creating an "array" (written into the string literal on line five) and for every digit in the year, we set that index into the array to 1. Once all the digits have been processed, we count how many 1s there are in sequence, and if that count equals the year length we can assume the year is sorted.

**Detailed Explanation**

```
&>1+                              Read the year and increment it.

    0v                            The "array" is initialized with zeros prior
9`#v_>:9+0\4p1+:                     to processing each year.

1:$<v                             For every digit, set the corresponding array index
0g1+>00p:55+%9+1\4p55+/:!#v_0       to one, and increment the year length counter.

                      p09 <       Initialise the sequence counter to zero.
                     9            Push a marker onto the stack.
        ".........."              Push the values from the array onto the stack.

v+*g09:<                          Increment the sequence counter for every 1 in the
>:00g-v^<                           array and reset it on every 0. Break if it equals
-9:p09_v|                           the year length or we encounter the end marker.

  @._<$<                          If we have a match, clear the stack and output the year.
$v      >                         If we've reached the marker, drop it try the next year.

```
> 1 votes

# Answer
# Python 2, ~~118 117 114~~ 108 Bytes

```
x,s=input()+1,sorted
while[j for i,j in enumerate(s(str(x))[1:])if int(s(str(x))[i])+1!=int(j)]:x+=1
print x

```

EDIT:

-1 Byte thanks to @Gábor Fekete

-6 Bytes thanks to @Zachary T
> 1 votes

# Answer
# Ruby, 51 bytes

```
->n{n+=1 until'0123456789'[n.to_s.chars.sort*''];n}

```
> 1 votes

# Answer
# Python 2, 68 bytes

```
n=input()+1
while''.join(sorted(`n`))not in'0123456789':n+=1
print n

```

Well beaten by @Dennis but just posted as an alternative method anyway.
> 1 votes

# Answer
## C#, 127 bytes

```
using System.Linq;n=>{char[]s;while((s=(++n+"").OrderBy(x=>x).ToArray()).Select((x,i)=>i>0&&x-s[i-1]!=1).Any(x=>x));return n;};

```

~~Beat the current C# submission by 3 bytes :p~~ Beaten back already
I know this answer will be beaten back easily...
repl.it demo

Ungolfed

```
n=>
{
    char[] s;
    while((
        // Store char array in variable to be referenced in Select()
        // Increment n and cast to string
        s=(++n+"")
            // Sort ascending, to array
            .OrderBy(x=>x)
            .ToArray())
        // Convert char to true if it's not at position 0,
        // and it is not 1 greater than the previous char
        .Select((x,i)=>i>0&&x-s[i-1]!=1)
        // All false: n is sortable
        // Any true: n is not sortable
        .Any(x=>x))
    // while loop body is empty
    ;
    return n;
};

```
> 1 votes

# Answer
# PHP, ~~90~~ ~~89~~ 88 bytes

a completely different approach:

```
while(array_unique($a=str_split($n=++$argv[1]))!=$a|max($a)-min($a)-count($a)+1);echo$n;

```

Run with `-r`.

**breakdown**

```
while(
    array_unique(           // 3. unique values
        $a=str_split(       // 2. split to digits
            $n=++$argv[1]   // 1. increase number
        )
    )
    !=$a                    // 4. repeat while unique digits differ from original digits
    |                       // or
        max($a)-min($a)     // digit range
        -count($a)+1        // differs from count-1
    );
echo$n;                 // print result

```
> 1 votes

# Answer
**Clojure, ~~104~~ ~~96~~ 91 bytes**

Long method names don't make this that short... At least `map-indexed` and `-` get main calculations done in a neat way.

*Edit 1*: Neat, I forgot also `=` can take multiple arguments so I don't need to check if count of distinct values is 1.

*Edit 2*: No need to run `(sort(seq(str %)))`, `(sort(str %))` works equally well.

```
(fn[i](first(filter #(apply =(map-indexed -(map int(sort(str %)))))(rest(iterate inc i)))))

```

Ungolfed:

```
(defn f [i]
  (let [is-sorted? #(= 1 (->> % str sort (map int) (map-indexed -) set count))]
    (->> i (iterate inc) rest (filter is-sorted?) first)))

```
> 0 votes

# Answer
## R, 87 bytes

```
f=function(x)`if`(all(diff(sort(as.double(el(strsplit(c(x+1,""),"")))))==1),x+1,f(x+1))

```

As usual when it comes to splitting numbers into digits, R does not have a native way of doing this. Consequently we have to coerce the input into a character, split into a character vector and subsequently convert back to any numeric type.

Try it online
> 0 votes

---
Tags: code-golf, number, sequence, restricted-time
---


title: Alternating sign matrix verification

text:
# Question
Title: Alternating sign matrix verification
An alternating sign matrix is an `n` by `n` matrix consisting of the numbers -1, 0, 1, such that:

* The sum of each row and column is 1
* The nonzero entries in each row and column alternate in sign

These matrices generalise permutation matrices, and the number of such matrices for a given `n` was of interest for some time. They occur naturally during the Dodgson condensation method of computing matrix determinants (named after Charles Dodgson, better known as Lewis Carroll).

Here are some examples of 4 by 4 alternating sign matrices:

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

```

And here are some examples of 4 by 4 matrices which aren't alternating sign matrices:

```
 0  1  0  0
 0  0  0  1
 1  0  0  0
 0  0  1 -1    (last row and last column don't add to 1)

 0  0  0  1
 1  0  0  0
-1  1  1  0
 1  0  0  0    (third row does not alternate correctly)

```

Your program or function will be given an `n` by `n` matrix (`n >= 1`) of -1s, 0s and 1s — output a truthy value if the given matrix is an alternating sign matrix, otherwise output a falsy value.

This is , so the goal is to minimise the number of bytes used.

## Test cases

The following test cases are given in a Python-like 2D list format.

**Truthy:**

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

```

**Falsy:**

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

```

# Answer
# Jelly, 15 bytes

```
;Zḟ€0;€-;@€-IFP

```

Try it online!

```
;Zḟ€0;€-;@€-IFP   Main monadic chain. Argument: z

;Z                Concatenate with its transpose.
  ḟ€0             Remove zeros from each sub-list. At this point,
                  one expects lists of the form [1, -1, 1, -1, ..., 1] for truthy,
                  and any other arrays containing purely 1 and -1 for falsey.
     ;€-          Append -1 to each sub-list.
        ;€@-      Prepend -1 to each sub-list.
            I     Compute the difference between each term. At this point,
                  for truthy, one expects arrays filled with 2, and arrays
                  containing 0 otherwise.
             FP   Product of every item. This checks if any item is equal to zero.

```
> 3 votes

# Answer
## Retina, ~~62~~ ~~58~~ ~~56~~ 53 bytes

Byte count assumes ISO 8859-1 encoding, and the `\t` should be replaced with actual tabs (0x09 which would be turned into spaces by SE otherwise).

```
$
\t$`¶
O$#`...(?<=^[^\t]*(.+))
$.1
T` 0
^(1(-11)*\s)+$

```

Input format is a matrix where each column uses three right-aligned characters, e.g.:

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

```

Output is either `0` (falsy) or `1` (truthy).

Test suite. (The first few lines transform the input format and let Retina run several test cases at once.)

### Explanation

Thankfully, the input is a square matrix: transposing squares is just about doable in Retina, whereas transposing rectangles is a massive pain.

```
$
\t$`¶

```

We start by appending a tab, the entire input again (using the prefix `$``) and then a linefeed at the end (using Retina's alias ). We're using a tab to separate the two copies so that we can distinguish between them when we're transposing one of them, and by using a whitespace character we can save a couple of bytes later on.

```
O$#`...(?<=^[^\t]*(.+))
$.1

```

This is the trickiest bit: transposing the first copy of the matrix. The idea is to match cells in the first copy and then sorting them (stably) by the horizontal position. We match the cells with `...` (since they're always three characters wide) and then measure the horizontal position with `(.+)` inside the lookbehind. Then, to make sure that we only transpose the first copy, we check that we can reach the beginning of the string without moving past a tab.

You might notice that this will also match some three-byte strings (that don't even align with the cells) in the first row of the second copy, because the `.+` can pass through the tab. However, this is not an issue because the horizontal position of these matches is strictly greater than any inside the first copy, so these matches remain in their position.

The rest is fairly simple:

```
T` 0

```

We remove spaces and zeros from the input.

```
^(1(-11)*\s)+$

```

And finally we check that the entire input consists of whitespace-terminated rows of the form `1(-11)*`, i.e. an alternating sequence of `1` and `-1` that begins and ends with `1` (because otherwise it doesn't sum to `1`).
> 3 votes

# Answer
# Pyth, 16 bytes

```
!sm-sM._+d_1U2+C

```

Try it online: Demonstration or Test Suite

# Explanation:

```
!sm-sM._+d_1U2+CQQ   two implicit Qs (=input matrix) at the end
              +CQQ   zip Q and connect it with Q (=list of columns and rows)
  m                  map each column/row d to:
        +d_1            append -1 to d
      ._                compute all prefixes of ^
    sM                  compute the sums of the prefixes
   -        U2          remove zeros and ones
                        a column/row is correct, if this gives an empty list
 s                   connect up all resulting lists
!                    check, if this result is empty

```
> 3 votes

# Answer
# Jelly, 11 bytes

```
;Zj-+\ṚQḄ=2

```

Returns **1** for alternating sign matrices, **0** otherwise. Try it online! or verify all test cases.

### Background

Disregarding zeroes, each row and column has to consist of the pattern **(1, -1)\* 1**, i.e., alternating occurrences of **1** and **-1**, starting and ending with a **1** (so the sum is **1**).

To verify this is the case, we take the array of all rows and columns, and join them using **-1** as separator. Since all endpoints are **1**'s, the resulting flat array satisfies the pattern **(1, -1)\* 1** if and only if the rows and columns do.

For the actual test, we compute the cumulative sum of the array. For an alternating sign matrix, the result will be an array of **0**'s and **1**'s that ends with a **1**.

We reverse the cumulative sum and deduplicate it, keeping the order of the initial occurrences of all unique elements. For a truthy input, the result will be the list **\[1, 0\]**.

To output the corresponding Boolean, we convert the duplicated cumulative sums from binary to integer and test if the result is **2**.

### How it works

```
;Zj-+\ṚQḄ=2  Main link. Argument: M (matrix / 2D array)

 Z           Zip; transpose M's rows and columns.
;            Concatenate M and zipped M.
  j-         Join, separating by -1.
    +\       Take the cumulative sum of the result.
      Ṛ      Reverse the array of partial sums.
       Q     Unique; deduplicate the partial sums.
        Ḅ    Unbinary; convert from base 2 to integer.
         =2  Test for equality with 2.

```
> 3 votes

# Answer
# MATL, ~~18~~ ~~16~~ ~~15~~ 13 bytes

*3 bytes saved thanks to @Luis*

```
t!h"@s1=@Xzdv

```

This solution accepts a 2D array as input and will output a truthy or falsey array. It is important to note that in MATL, a truthy array is composed of all non-zero elements while a falsey result has at least one zero element. Here is another demonstration of truthy/falsey arrays.

**Try it Online**

Modified version to show all test cases

**Explanation**

```
        % Implicitly grab input matrix
t!      % Duplicate and transpose input
h       % Horizontally concatenate input with transpose. This allows us to
        % process only columns since now the columns *also* contain the rows.
"       % For each column (of our column/row combined matrix)
  @s1=  % Compute the sum and ensure it is equal to 1
  @Xz   % Get the non-zeros
  d     % Compute the element-to-element difference. The 1 and -1 alternate only if
        % all these differences are non-zero
  v     % Vertically concatenate everything on the stack
        % Implicit end of loop and implicitly display truthy/falsey value

```
> 2 votes

# Answer
# Julia, 36 bytes

```
!x=[x^0 x^0;-x -x'][:]|>cumsum⊆0:1

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), ~~112~~ 100 bytes

```
a=>!/(^|,)(?!0*10*(-10*10*)*(,|$))/.test(a.map(b=>b.join``)+','+a.map((_,i)=>a.map(b=>b[i]).join``))

```

Flattens the array and its transpose into strings, then (ignoring `0`s) checks for the pattern `1-11...1-11` in each string.

Edit: Saved 12 bytes thanks to @PeterTaylor.
> 1 votes

# Answer
# Python 2, ~~63~~ 60 bytes

```
s=0;x=input()
for r in x+zip(*x):
 for n in(-1,)+r:s+=[n][s]

```

Input is a list of tuples.

This terminates with exit code **0** for alternating sign matrices and exit code **1** otherwise. This is what true and false do, and – as shown in the verification section – it can indeed be used as a condition in, e.g., a Bash script.

### Verification

**test-cases.txt**

```
[(1,)]
[(1, 0), (0, 1)]
[(0, 1), (1, 0)]
[(0, 1, 0), (0, 0, 1), (1, 0, 0)]
[(0, 1, 0), (1, -1, 1), (0, 1, 0)]
[(0, 1, 0, 0), (0, 0, 1, 0), (1, 0, 0, 0), (0, 0, 0, 1)]
[(1, 0, 0, 0), (0, 0, 1, 0), (0, 1, -1, 1), (0, 0, 1, 0)]
[(0, 0, 1, 0), (0, 1, -1, 1), (1, -1, 1, 0), (0, 1, 0, 0)]
[(0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0), (0, 0, 1, 0)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 0, -1, 1), (0, 0, 0, 1, 0)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, -1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]
[(0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, -1, 1, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0), (1, 0, 0, -1, 1, -1, 1, 0), (0, 1, -1, 1, -1, 1, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 1)]
[(0,)]
[(-1,)]
[(1, 0), (0, 0)]
[(0, 0), (0, 1)]
[(-1, 1), (1, 0)]
[(0, 1), (1, -1)]
[(0, 0, 0), (0, 0, 0), (0, 0, 0)]
[(0, 1, 0), (1, 0, 1), (0, 1, 0)]
[(-1, 1, 1), (1, -1, 1), (1, 1, -1)]
[(0, 0, 1), (1, 0, 0), (0, 1, -1)]
[(0, 1, 0, 0), (0, 0, 0, 1), (1, 0, 0, 0), (0, 0, 1, -1)]
[(0, 0, 1, 0), (0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0)]
[(0, 0, 0, 1), (1, 0, 0, 0), (-1, 1, 1, 0), (1, 0, 0, 0)]
[(1, 0, 1, 0, -1), (0, 1, 0, 0, 0), (0, 0, 0, 0, 1), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 1, -1, 0), (0, 0, -1, 1, 1)]
[(0, -1, 0, 1, 1), (1, -1, 1, -1, 1), (0, 1, 1, 0, -1), (1, 1, -1, 1, -1), (-1, 1, 0, 0, 1)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]

```

**test-suite.sh**

```
while read; do
        if python2 asmv.py <<< "$REPLY"; then
                echo "true"
        else
                echo "false"
        fi
done < test-cases.txt 2>&- | uniq -c

```

**Output**

```
$ bash test-suite.sh
     12 true
     17 false

```

### How it works

Disregarding zeroes, each row and column has to consist of the pattern **(1, -1)\* 1**, i.e., alternating occurrences of **1** and **-1**, starting and ending with a **1** (so the sum is **1**).

To verify this is the case, we zip/transpose the input matrix **M**, append the result to **M** (now consisting of a list of rows and columns), and prepend a **-1** to each row/column.

For example, if **M** is one of the following matrices (valid, invalid)

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

```

the results are

```
-1 | 0  1  0    -1 | 0  0  0
-1 | 0  0  1    -1 | 1  0  0
-1 | 1  0  0    -1 | 0  1 -1
------------    ------------
-1 | 0  0  1    -1 | 0  1  0
-1 | 1  0  0    -1 | 0  0  1
-1 | 0  1  0    -1 | 0  0 -1

```

Reading the generated matrix row-wise must result in a flat sequence with pattern **(-1, 1)\***. To verify this is the case, we take the cumulative sum of all entries, beginning with the top row.

For the example matrices, this results in

```
-1 -1  0  0 -1 -1 -1  0 -1  0  0  0 -1 -1 -1  0 -1  0  0  0 -1 -1  0  0
-1 -1 -1 -1 -2 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -2 -3 -3 -3 -2 -3 -3 -3 -4

```

For a valid alternating sign matrix, the output will consist of **-1**'s and **0**'s and – since every **-1** cancels out the previous **1** and vice versa – no other numbers.

At first glance, this may appear to fail checking if the last column ends with a **1**. However, for an **n × n** matrix containing **k** zeroes, valid rows will contain **n + k** ones. If all columns except the last were valid as well, there would be **n + k - 1** ones in the columns, which is impossible.

To test that there are no other numbers, we store the partial sums in a variable **s** and update them for each entry of with generated matrix with `s+=[n][s]`.

If **s = 0** or **s = -1**, this is equivalent to `s+=n`. However, for all other values of **s**, it causes an *IndexError*, so Python immediately terminates with exit code **1**. If this doesn't happen at any point, the program finishes cleanly with exit code **0**.
> 1 votes

# Answer
# R, 54 bytes

Anonymous function, uses the same logic as Dennis's Python 2, Jelly, and Julia answers.

```
function(x)all(abs(cumsum(rbind(-1,cbind(t(x),x))))<2)

```
> 0 votes

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


title: Make a ASCII Hexagon Ring Tiling

text:
# Question
Title: Make a ASCII Hexagon Ring Tiling
Using ASCII print a section of a hexagon ring tiling.

Here's a small section:

```
       /\__/\
      /_/  \_\
 /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/
 /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/
      \ \__/ /
       \/__\/

```

Here's a larger section:

```
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/

```

# Challenge

Given 2 integers `h` and `w`, where `h` is the height and `w` is the width, output a `hxw` section of a hexagon ring tiling.

# Examples

## Input 1

`4x4`

## Output 1

```
 /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\

```

## Input 2

`3x3`

## Output 2

```
 /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/
 /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/
 /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/

```

## Input 3

`1x3`

## Output 3

```
 /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/

```

## Input 4

```
3x6

```

## Output 4

```
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\

```

# Clarifications

* My question is similar to this one: Me Want Honeycomb.
* The input will be on a single line in the form `hxw`.
* Output to stdout (or something similar).
* This is code-golf so shortest answer in bytes wins.

# Answer
> 2 votes
# Befunge, 137 bytes

I seem to have created some kind of scifi hand gun.

```
&>4*>~>$&>\>1-:4%3v
>00gg,\1-:v^_@#:\<>+00p\::6*\00g2/+2%+1+66+:
^%+66<:+1\_$$55+,^
_\/__\/_/  \
\ \__/ /\__/\
/_/  \_\/__\/
 /\__/\ \__/

```

Try it online!

**Explanation**

```
&>4*>                    Read the height and multiply by 4.
     ~>$                 Drop the 'x' separator.
        &>\              Read the width and swap below the height

>                        Start of the outer loop.
 1-                      Decrement the height.
   :4%3+00p              Calculate the pattern y offset: height%4+3
           \             Swap the width back to the top.

::6*\00g2/+2%+1+         Calculate the line length: w*6+(w+y/2)%2+1
                66+:     Initialise the pattern x offset to 12, and duplicate it.

>                        Start of the inner loop.
 00gg                    Get a pattern char using the x on the stack and the saved y.
     ,                   Output the char.
      \1-                Swap the line length to the top of the stack and decrement it.
         :v              Check if it's zero, and if so...
          _                 ...break out of the loop to the right.
       +1\               Otherwise swap the x offset back to the top and increment it.
 %+66<:                  Mod it with 12 to make sure it's in range.
^                        Then return to the beginning of the inner loop.

$$                       Drop the x offset and line length.
  55+,                   Output a newline.
     \<                  Swap the height back to the top of the stack.
 _@#:                    Check if it's zero, and exit if that's the case.
^                        Otherwise return to the start of the outer loop.

```

# Answer
> 3 votes
# Lua, 174 176 156 bytes

*The code would print height-amount of lines, not height-amount of hexagons. Added `*4`, that fixed it, but added 2 extra bytes.* *Saved some bytes by changing the counter from if to modulo, and by putting two `io.read()`s into one.*

Uses `io.read()` as input.

```
a,w,h,n,d={[[ /\__/\ \__/]],[[/_/  \_\/__\\]],[[\ \__/ /\__/]],[[_\/__\/_/  \\]]},io.read(,),"",0 for i=h*4,0,-1 do d=d+1 d=5%d end n=a[d]print(n:rep(w))end

```

Replicates the strings width-amount of times via `string:rep(width)`, then iterates height-amount of times with a for-loop. Needed `[[]]` (literal strings) because the backslashes really screwed stuff up.

*Old Version:*

```
a,w,h,n,d={[[ /\__/\ \__/]],[[/_/  \_\/__\\]],[[\ \__/ /\__/]],[[_\/__\/_/  \\]]},io.read(),io.read(),"",0 for i=h*4,0,-1 do d=d+1 d=5%d end n=a[d]print(n:rep(w))end

```

# Answer
> 1 votes
## Python 2, 180 bytes

```
a,b,c,d=' /\__/\ \__/','/_/  \_\/__\\','\ \__/ /\__/','_\/__\/_/  \\'
h,w=input()
x=w/2
e,E=[(2,1),(7,8)][w%2]
print'\n'.join([a*x+a[:e],b*x+b[:E],c*x+c[:E],' '+(d*x+d[:e])[1:]]*h)

```

Takes input as two integers

Input: `2,7`

Output:

```
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/
 /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\
/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\
\ \__/ /\__/\ \__/ /\__/\ \__/ /\__/\ \__/ /
 \/__\/_/  \_\/__\/_/  \_\/__\/_/  \_\/__\/

```

# Answer
> 1 votes
## Batch, 266 bytes

```
@echo off
for /l %%i in (1,1,%1)do call:l %2 " \" /__\/ "_/  \_\" " \__/ /" \__/\
exit/b
:l
call:c %1 " /" %6 %5
call:c %1 / %4 %3
call:c %1 \ %5 %6
:c
set s=%~2
for /l %%j in (2,2,%1)do call set s=%%s%%%~3%~4
set/ao=%1^&1
if %o%==1 set s=%s%%~3
echo %s%

```

The `:c` subroutine does all the legwork of concatenating the pieces together for a single line; it is called by `:l` 4 times (one by fall though by arranging for `:l`'s arguments to be a superset of `:c`'s) to generate the 4 lines for each row of rings. There was also the possibility of falling through for the last row of rings instead but it turned out to be 5 bytes longer.

---
Tags: code-golf, ascii-art, kolmogorov-complexity, hexagonal-grid, tiling
---


title: Are we then yet?

text:
# Question
Title: Are we then yet?
I'm a time traveler, and I'm obsessed with the passage of time. I particularly love the moments when the clock hands pass 12, or when I get to flip to the next page of my calendar, or when everyone yells "Happy New Year!"

Please write for me a program to show me how far I am from the last such moment to the next, in the form of a progress bar. For example, if I tell it the time is 09:12, it should print this:

```
09:00 ####---------------- 10:00

```

If I tell it the month is May, 1982, it should print this:

```
1982-01 #######------------- 1983-01

```

Did I mention I'm a time traveler? I travel to anywhere from the first millisecond of 0 A.D. to the last millisecond of 9999 A.D., so the program needs to handle any date and time in that range.

# Input

* Input will be in one of the following formats:

+ `YYYY-MM-DDThh:mm:ss.sss`
    + `YYYY-MM-DDThh:mm:ss`
    + `YYYY-MM-DDThh:mm`
    + `YYYY-MM-DDThh`
    + `YYYY-MM-DD`
    + `YYYY-MM`

These are the only formats that need be handled. Each part will have exactly the number of digits shown, which means fractional seconds may have trailing zeroes (e.g. `.120`, never `.12`). The `T` is a literal letter "T" delimiting the date from the time. Hours are on a 24-hour clock.
* Months and days are 1-based (more on this below).
* Invalid and out-of-range inputs need not be handled.
* At the programmer's discretion, input may have a single trailing newline.

# Progress bar math

The program is concerned with the least- and second-least-significant units in the given input. For example, if the input has day-level precision (e.g. `2016-12-14`), the progress bar will indicate what proportion of the days in the input month have elapsed versus what remains.

The progress bar will have 20 units (characters) and the proportion represented will be rounded to the nearest increment of 120. For example, given `2016-12-14T12:28`, the progress bar will show **Round(2860 × 20) = 9** of 20 units "filled."

### 1-based months and days

Although the day of December 1 (for example) is `01` in `2016-12-01`, for the purpose of calculation it is the 0th day of the month, because the truncated units imply the 0th millisecond of the 0th minute of the 0th hour of the day. In other words, `2016-12-01` is 031 of the way through December and `2016-12-02` is 131, and so on.

Likewise, `2016-01` is the 0th millisecond of the 0th day of January, so in calculations it is 012, which means `2016-12` is 1112.

Yes, that means months and days will never completely fill the progress bar.

### Differing month durations and leap years

Different months have different numbers of days and the output must reflect this—including leap years. The progress bar for February 6, 2017 will be different from the progress bar for February 6, 2016 (or January 6 of both years).

### Miscellaneous

* Time travelers use the proleptic Gregorian calendar. TL;DR: No special cases like missing days in 1752. Input will include dates in the year 0 A.D.
* Time travelers ignore daylight savings.
* The program is not required to account for leap seconds, but it may.

# Output

The program (or function) must print (or return as a string) a horizontally-oriented 20-character progress bar that is "filled in" for time that has elapsed and "open" for time that remains. It must "fill in" from left to right.

The progress bar must have a label to its left showing the beginning of the period being counted and another to its right showing the beginning of the next period, in the same format as the input (but showing only two units of precision). For our example `2016-12-14` valid output would be:

```
12-01 #########----------- 01-01

```

Here are the valid label formats for each of the possible periods:

* Months: `YYYY-MM`
* Days: `MM-DD`
* Hours: `DDThh`
* Minutes: `hh:mm`
* Seconds: `mm:ss`
* Milliseconds: `ss.sss`

No additional units may be included in the labels, and none may be omitted.

### Output notes

* The progress bar's "filled in" units will be represented by a `#` character. "Open" units will be represented by `-`.
* There must be exactly one space between the progress bar and each label.
* Leading or trailing spaces and/or a single trailing newline are allowed.

# Winning

This is . Shortest code in bytes wins. Standard rules apply. Standard loopholes forbidden.

# Examples

```
Input                      Output
-----------------------    -------------------------------------
2016-12-12T12:17           12:00 ######-------------- 13:00
2016-12-12                 12-01 #######------------- 01-01
0000-01-01T00:00:00.000    00.000 -------------------- 01.000
0000-01-01T00:00           00:00 -------------------- 01:00
1899-12-31T23              31T00 ###################- 01T00
1899-12-31                 12-01 ###################- 01-01
1899-12                    1899-01 ##################-- 1900-01
1982-05-15T17:15           17:00 #####--------------- 18:00
1982-05-15T17              15T00 ##############------ 16T00
1982-05                    1982-01 #######------------- 1983-01
9999-12-31T23:59:59.999    59.000 #################### 00.000
9999-12                    9999-01 ##################-- 10000-01
2000-01-06                 01-01 ###----------------- 02-01
2000-02-06                 02-01 ###----------------- 03-01
2001-02-06                 02-01 ####---------------- 03-01
1742-09-10                 09-01 ######-------------- 10-01

```

# Answer
# JavaScript, 282 bytes

```
(x,v=x.split(/\D/g),l=v.length-2,[a,b,c,d]=("10e5,01,-,12,01,-,"+new Date(v[0],v[1],0).getDate()+",00,T,24,00,:,60,00,:,60,000,.,1000").split`,`.slice(l*3,l*3+4),t=(v[l+1]-b)/d*20+.5|0,n=v[l],o=((n|0)+1)%a,r=l?('0'+o).slice(-2):o)=>n+c+b+' '+'#'.repeat(t)+'-'.repeat(20-t)+' '+r+c+b

```

Passes all the tests

```
(
x,
v=x.split(/\D/g),
l=v.length-2,
[a,b,c,d]=("10e5,01,-,12,01,-,"+new Date(v[0],v[1],0).getDate()+",00,T,24,00,:,60,00,:,60,000,.,1000").split`,`.slice(l*3,l*3+4),
t=(v[l+1]-b)/d*20+.5|0,
n=v[l],
o=((n|0)+1)%a,
r=l?('0'+o).slice(-2):o
) =>n+c+b+' '+'#'.repeat(t)+'-'.repeat(20-t)+' '+r+c+b

```

Test function prints nothing for pass, values for fail.

```
function test(value,expected){
    if (f(value)!=expected)
    {
        console.log(value);
        console.log(f(value));
        console.log(expected);
     }
}

```

The test cases:

```
test('2016-12-12T12:17','12:00 ######-------------- 13:00')                 ;
test('2016-12-12','12-01 #######------------- 01-01')                       ;
test('0000-01-01T00:00:00.000','00.000 -------------------- 01.000')        ;
test('0000-01-01T00:00','00:00 -------------------- 01:00')                 ;
test('1899-12-31T23','31T00 ###################- 01T00')                    ;
test('1899-12-31','12-01 ###################- 01-01')                       ;
test('1899-12','1899-01 ##################-- 1900-01')                      ;
test('1982-05-15T17:15','17:00 #####--------------- 18:00')                 ;
test('1982-05-15T17','15T00 ##############------ 16T00')                    ;
test('1982-05','1982-01 #######------------- 1983-01')                      ;
test('9999-12-31T23:59:59.999','59.000 #################### 00.000')        ;
test('9999-12','9999-01 ##################-- 10000-01')                     ;
test('2000-01-06','01-01 ###----------------- 02-01')                       ;
test('2000-02-06','02-01 ###----------------- 03-01')                       ;
test('2001-02-06','02-01 ####---------------- 03-01')                       ;
test('1742-09-10','09-01 ######-------------- 10-01')                       ;

```
> 4 votes

# Answer
# Pyth, 213 bytes

My first code in pyth! Behold:

```
+%h=N:[d"%.4d"\-=Z"%.2d"\-Z\TZ\:Z\:Z\."%.3d")-*2lKr:w"[-T:.]"d7 3*2lKJ@K_2+@N1+%eN=b<lK4+d+*\#=Gs+*20c-eKb@=H[0^9T12?q2=k@K1+28+q0%=YhK4-q0%Y400q0%Y100+30%+k/k8 2 24 60 60 999)lK.5+*\--20G+d+%hN%+J1@H-lK1+@N1%eNb

```

My pyth code is closely based off of my previous python answer. Here is the ungolfed version with comments:

```
"K is the input, as a list of numbers"
Kr:w"[-T:.]"d7
"Y=year"
=YhK
"k=month"
=k@K1
"H = a list of denominators"
=H[0 ^9T 12 ?q2k+28+q0%Y4-q0%Y400q0%Y100 +30%+k/k8 2 24 60 60 999)
"J is the second-to-last number of the input"
J@K_2
"b is the +1 starting point for months and days"
=b<lK4
"G is the number of hashtags in the statusbar"
=Gs+*20c-eKb@HlK.5
"N is the formatted string"
=N:[d"%.4d"\-=Z"%.2d"\-Z\TZ\:Z\:Z\."%.3d")-*2lK3 *2lK
+%hNJ+@N1+%eNb+d+*\#G+*\--20G+d+%hN%+J1@H-lK1+@N1%eNb

```

Testing multiple values is easily accomplished by making the code loop, and adding a newline print to the end:

```
Wp+%h=N:[d"%.4d"\-=Z"%.2d"\-Z\TZ\:Z\:Z\."%.3d")-*2lKr:w"[-T:.]"d7 3*2lKJ@K_2+@N1+%eN=b<lK4+d+*\#=Gs+*20c-eKb@=H[0^9T12?q2=k@K1+28+q0%=YhK4-q0%Y400q0%Y100+30%+k/k8 2 24 60 60 999)lK.5+*\--20G+d+%hN%+J1@H-lK1+@N1+%eNb"\n"

```

Then I ran `cat testinput | pyth code.pyth > output` and `diff output testoutput` Or try it online.
> 3 votes

# Answer
# Python 2, 371 bytes

This challenge was surprisingly difficult! It seemed like I was going to be just under 300 until I worked out the output string formatting.

The kind of cool part is that my answer does not use any date package:

```
import re
s=raw_input()
S=[int(i)for i in re.sub('[-T:.]',' ',s).split()]
l=len(S)
y,m=S[:2]
d=[0,20<<9,12,28+(y%4==0!=y%100)+(y%400==0)if m==2else 30+(m+m/8)%2,24,60,60,999]
a,n=S[-2:]
b=1-(1if l>3else 0)
h=int(20.*(n-b)/d[l]+.5)
x,y,z='- %.4d - %.2d - %.2d T %.2d : %.2d : %.2d . %.3d'.split()[l*2-3:l*2]
print x%a+y+z%b+' '+'#'*h+'-'*(20-h)+' '+x%((a+1)%d[l-1])+y+z%b

```
> 2 votes

---
Tags: code-golf, date
---


title: Un-de-duplicating strings

text:
# Question
Title: Un-de-duplicating strings
### Introduction

Let's observe the following string:

```
AABBCCDDEFFGG

```

You can see that every letter has been *duplicated*, except for the letter `E`. That means that the letter `E` has been *de-duplicated*. So, the only thing we need to do here is to reverse that process, which gives us the following **un-de-duplicated** string:

```
AABBCCDDEEFFGG

```

---

Let's take a harder example:

```
AAAABBBCCCCDD

```

You can see that there is an uneven number of consecutive `B`'s, so that means that one of the `BB` was de-duplicated from the original string. We only need to un-de-duplicate this letter, which gives us:

```
AAAABBBBCCCCDD

```

### The challenge

Given a non-empty **de-duplicated** string, consisting of *only alphabetic characters* (either only uppercase or only lowercase), return the **un-de-duplicated** string. You can assume that there will always be at least one de-duplicated character in the string.

### Test cases

```
AAABBBCCCCDDDD    -->    AAAABBBBCCCCDDDD
HEY               -->    HHEEYY
AAAAAAA           -->    AAAAAAAA
N                 -->    NN
OOQQO             -->    OOQQOO
ABBB              -->    AABBBB
ABBA              -->    AABBAA

```

This is , so the shortest valid submission in bytes wins!

# Answer
# MATL, 7 bytes

```
Y'to+Y"

```

Try it online! Or verify all test cases.

Let's take `'ABBA'` as example input.

```
Y'   % Implicit input. Run-length decoding
     % STACK: 'ABA', [1 2 1]
t    % Duplicate top of the stack
     % STACK: 'ABA', [1 2 1], [1 2 1]
o    % Modulo 2
     % STACK: 'ABA', [1 2 1], [1 0 1]
+    % Add, element-wise
     % STACK: 'ABA', [2 2 2]
Y"   % Run-length encoding. Implicit display
     % STACK: 'AABBAA'

```
> 20 votes

# Answer
# Retina, 11 bytes

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

```

**Try it online** \- *contains all test cases*
> 11 votes

# Answer
## Haskell, 36 bytes

```
u(a:b:c)=a:a:u([b|a/=b]++c)
u x=x++x

```

Usage example: `u "OOQQO"` -\> `"OOQQOO"`.

If the string has at least 2 elements, take two copies of the first and append a recursive call with

* the second element an the rest if the first two elements differ or
* just the rest

If there are less than two elements (one or zero), take two copies of the list.
> 8 votes

# Answer
## Perl, 16 bytes

15 bytes of code + `-p` flag.

```
s/(.)\1?/$1$1/g

```

To run it:

```
perl -pe 's/(.)\1?/$1$1/g' <<< 'HEY'

```
> 8 votes

# Answer
# Brachylog, 17 bytes

```
@b:{~b#=.l#e,|}ac

```

Try it online!

### Explanation

```
Example input: "ABBB"

@b                  Blocks: Split into ["A", "BBB"]
  :{          }a    Apply the predicate below to each element of the list: ["AA", "BBBB"]
                c   Concatenate: "AABBBB"

    ~b#=.             Output is the input with an additional element at the beginning, and
                        all elements of the output are the same (e.g. append a leading "B")
        .l#e,         The length of the Output is an even number
             |        Or: Input = Output (i.e. do nothing)

```
> 6 votes

# Answer
## JavaScript (ES6), ~~37~~ 30 bytes

*Saved 7 bytes by using the much more efficient '$1$1' like \[other\] \[answers\] did*

```
s=>s.replace(/(.)\1?/g,'$1$1')

```

### Test cases

```
let f =

s=>s.replace(/(.)\1?/g,'$1$1')

console.log(f("AAABBBCCCCDDDD"));   //  -->  AAAABBBBCCCCDDDD
console.log(f("HEY"));              //  -->  HHEEYY
console.log(f("AAAAAAA"));          //  -->  AAAAAAAA
console.log(f("N"));                //  -->  NN
console.log(f("OOQQO"));            //  -->  OOQQOO
console.log(f("ABBB"));             //  -->  AABBBB
console.log(f("ABBA"));             //  -->  AABBAA
```
> 4 votes

# Answer
# Ruby, 21 bytes

20 bytes plus the `-p` flag.

```
gsub(/(.)\1?/){$1*2}

```
> 4 votes

# Answer
# Mathematica, 41 bytes

```
s=StringReplace;s[s[#,a_~~a_->a],b_->b~~b]&

```

Unnamed function that inputs a string and outputs a string. Completely deduplicate then completely undeduplicate. Not real short, but I couldn't do better for now.
> 4 votes

# Answer
# Befunge 98, 24 bytes

```
#@~#;:::#@,~-:!j;$,;-\,;

```

Try it Online!

`$` can be easily replaced with `-`, and the 2nd `@` with `;`.

I think this can be golfed further due to the `-` at the beginning of both `-,` (or `$,` above) and `-\,`.

**How?**

```
Stack notation:  bottom [A, B, C, D] top

#@~     Pushes the first character onto the stack (C henceforth) and ends if EOF
#;      No-op to be used later
:::     Now stack is [C, C, C, C]

#@,~    Prints C, and if EOF is next (odd consecutive Cs), prints again and ends
        Lets call the next character D

-       Now stack is [C, C, C-D]
:!j;    If C == D, go to "$," Else, go to "-\,"

===(C == D)===

$,      C == D (i.e. a pair of Cs) so we discard top and print C (Stack is now [C])
;-\,;   Skipped, IP wraps, and loop starts again

===(C != D)===

-       Stack is [C, C-(C-D)]  By expanding: [C, C - C + D] or just [C, D]
\,      Prints C (Stack is now [D])

;#@~#;  This is skipped, because we already read the first character of a set of Ds,
        and this algorithm works by checking the odd character in a set of
        consecutive similar characters. We already read D, so we don't
        need to read another character.

```
> 4 votes

# Answer
# Java 7, 58 bytes

```
String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

```

**Ungolfed:**

```
String c(String s){
  return s.replaceAll("(.)\\1?", "$1$1");
}

```

**Test code:**

Try it here.

```
class M{
  static String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

  public static void main(String[] a){
    System.out.println(c("AABBCCDDEFFGG"));
    System.out.println(c("AAAABBBCCCCDD"));
    System.out.println(c("AAABBBCCCCDDDD"));
    System.out.println(c("HEY"));
    System.out.println(c("AAAAAAA"));
    System.out.println(c("N"));
    System.out.println(c("OOQQO"));
    System.out.println(c("ABBB"));
    System.out.println(c("ABBA"));
  }
}

```

**Output:**

```
AABBCCDDEEFFGG
AAAABBBBCCCCDD
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA

```
> 3 votes

# Answer
# PHP, 65 bytes, no regex

```
while(""<$c=($s=$argv[1])[$i])if($c!=$s[++$i]||!$k=!$k)echo$c.$c;

```

takes input from command line argument. Run with `-r`.

**regex?** In PHP, the regex used by most answers duplicates every character. would be 44 bytes:

```
<?=preg_replace("#(.)\1?#","$1$1",$argv[1]);

```
> 2 votes

# Answer
# Brain-Flak 69 Bytes

Includes +3 for `-c`

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

```

Try it Online!

**Explanation:**

```
Part 1:
{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>

{                                                  }   # loop through all letters
 (   {}     [ {} ]<(())>){((<{}{}>))}{}                # equals from the wiki
                                                       # but first:
  ((  <>))<>                                           # push the top letter on the other
                                                       # stack twice
             (  )                                      # push the second letter back on
                                       {        }      # if they were equal:
                                        (<    >)       # push a 0 to exit this loop
                                          {}{}         # after popping the 1 from the
                                                       # comparison and the next letter
                                                       # (the duplicate)
                                                 {}    # pop the extra 0
                                                    <> # switch stacks

Part 2 (at this point, everything is duplicated in reverse order):
{({}<>)<>}<>

{        }   # for every letter:
 ({}<>)      # move the top letter to the other stack
       <>    # and switch back
          <> # Finally switch stacks and implicitly print

```
> 2 votes

# Answer
## brainfuck, 22 bytes

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

```

Try it online.

Prints the current character twice, unless it's equal to a character that was just printed twice.
> 2 votes

# Answer
# Jelly, 9 bytes

```
Œgs€2ṁ€€2

```

Try it online!
> 1 votes

# Answer
## Racket 261 bytes

```
(let((l(string->list s))(r reverse)(c cons)(e even?)(t rest)(i first))(let p((l(t l))(ol(c(i l)'())))
(cond[(empty? l)(list->string(if(e(length ol))(r ol)(r(c(i ol)ol))))][(or(equal?(i ol)(i l))(e(length ol)))
(p(t l)(c(i l)ol))][(p(t l)(c(i l)(c(i ol)ol)))])))

```

Ungolfed:

```
(define (f s)
  (let ((l (string->list s)))
    (let loop ((l (rest l))
               (ol (cons (first l) '())))
      (cond
        [(empty? l)
         (list->string(if (even? (length ol))
                          (reverse ol)
                          (reverse (cons (first ol) ol))))]
        [(or (equal? (first ol) (first l))
             (even? (length ol)))
         (loop (rest l) (cons (first l) ol))]
        [else
         (loop (rest l) (cons (first l) (cons (first ol) ol)))] ))))

```

Testing:

```
(f "ABBBCDDEFFGGG")

```

Output:

```
"AABBBBCCDDEEFFGGGG"

```
> 1 votes

# Answer
# 10 bytes

```
Í¨.©±½/±±

```

TryItOnline

Just a find and replace regex like all of the rest in the thread. The only difference is that I can replace anything that would require a `\` in front of it with the character with the same ascii value, but the high bit set. (So `(`, 00101000 becomes `¨`, 10101000)
> 1 votes

# Answer
# Perl 6, 17 bytes

```
s:g/(.)$0?/$0$0/

```

with -p command-line switch

## Example:

```
$ perl6 -pe 's:g/(.)$0?/$0$0/' <<< 'AAABBBCCCCDDDD
> HEY
> AAAAAAA
> N
> OOQQO
> ABBB
> ABBA'
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA

```
> 1 votes

# Answer
# Python3, ~~102~~ 94 bytes

```
from collections import*
lambda s:"".join(c*(s.count(c)+1&-2)for c in OrderedDict.fromkeys(s))

```

Thanks to xnor for saving 8 bytes! -\> bithack.
> 1 votes

# Answer
# 05AB1E, 10 bytes

```
.¡vy¬ygÉ×J

```

Try it online!

**Explanation**

```
.¡           # split string into groups of the same char
  v          # for each group
   y         # push the group
    ¬        # push the char the group consists of
     yg      # push the length of the group
       É     # check if the length of the group is odd
        ×    # repeat the char is-odd times (0 or 1)
         J   # join to string

```
> 1 votes

# Answer
## R, 81 bytes

```
r=rle(el(strsplit(scan(,""),"")));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

```

Reads a string from stdin, splin into vector of characters and perform run-length encoding (rle). Subsequently repeat the each values from the rle, the sum of the lengths and the lengths mod `2`.

If we can read input separated by space (implicitly as a vector/array of characters) then we can skip the splitting part and the program reduces to 64 bytes:

```
r=rle(scan(,""));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

```
> 1 votes

# Answer
# \>\<\> (Fish) 39 bytes

```
0v ;oo:~/:@@:@=?!voo
 >i:1+?!\|o !:  !<

```

Pretty sure this can be golfed a lot using a different technique.

It takes an input and compares against the current stack item, if it's different it'll print the first stack item twice, if the same it prints them both.

The stack when empty gets supplied with a 0 which prints nothing so can be appended on whenever.
> 1 votes

# Answer
# Pyth, 15 bytes

```
Vrz8p*+hN%hN2eN

```

Verify all test cases here.

Thanks to Luis Mendo for the methodology.

### Explanation

```
Vrz8p*+hN%hN2eN    z autoinitializes to the input
 rz8               run-length encode the input, returned as list of tuples (A -> [[1,"A"]])
V                  for every element N in this list
      +hN          add the head element of N (the number in the tuple)
         %hN2      to the head element of N mod 2
     *       eN    repeat the tail element of N that many times (the letter in the tuple)
    p              print repeated character without trailing newline

```

As is often the case, I feel like this could be shorter. I think there should be a better way to extract elements from the list than what I am using here.
> 1 votes

# Answer
# PowerShell, 28 bytes

```
$args-replace'(.)\1?','$1$1'

```

Try it online! (includes all test cases)

Port of the Retina answer. The only points of note are we've got `$args` instead of the usual `$args[0]` (since the `-replace` will iterate over each item in the input array, we can golf off the index), and the `'$1$1'` needs to be single quotes so they're replaced with the regex variables rather than being treated as PowerShell variables (which would happen if they were double-quote).
> 1 votes

# Answer
# C, 67 bytes

```
i;f(char*s,char*d){i=*s++;*d++=i;*d++=i;*s?f(i-*s?s:++s,d):(*d=0);}

```

Call with:

```
int main()
{
    char *in="AAABBBCCCCDDDD";
    char out[128];
    f(in,out);
    puts(out);
}

```
> 1 votes

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


# Question
Title: position of the only 1 in a number in binary format
Every number of the form 2i (where `i` is a non-negative integer) has a single 1 in its binary representation. Given such a number, output the 1-based position of the 1.

Examples:

```
DECIMAL   BINARY    POSITION
--------------------------
1            0001      1
2            0010      2
4            0100      3
8            1000      4

N         0...1...0     ?

```

# Answer
Stolen wholesale from Bit twiddling hacks:

```
uint8_t f(uint32_t v)
{
    static const uint8_t MultiplyDeBruijnBitPosition2[32] = {
          0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
            31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };
    return MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
}

```
> 16 votes

# Answer
# R, 14 or 22 characters

```
p=function(x)log2(x)+1

```

It remains fully vectorized, so not only can you do it for one number you can do it for any vector of numbers:

```
> n <- 2^seq(0,10)
> n
 [1]    1    2    4    8   16   32   64  128  256  512 1024
> p(n)
 [1]    1    2    3    4    5    6    7    8    9   10   11

```

Doesn't seem terribly slow either:

```
Unit: microseconds
   expr   min    lq median    uq    max
1 p(16) 4.749 4.749   4.75 5.029 33.524

```

As an expression, it can be cut down to 14 characters: `log2(scan())+1`

```
> log2(scan())+1
1: 1
2: 2
3: 4
4: 8
5: 16
6:
Read 5 items
[1] 1 2 3 4 5

```
> 6 votes

# Answer
**GNU C, POSIX C, or MSVC: usually 2 instructions with low latency (see below for perf)**

You can do the same thing even more portably with Rust, where `foo.trailing_zeros()` is a language built-in for all integer primitive types.

Performance varies a lot with hardware, but this inlines to whatever the hardware is capable of. This works on any architecture that has a GNU or POSIX compiler.

Most CPU architectures can count leading zeros or trailing zeros in one instruction. (See Wikipedia's Find First Set article). We can use either, since there's only one set bit. Knowing that our input is always non-zero also simplifies things. (Especially for x86 where BSF and BSR leave their output undefined when the input is zero).

The trick is to write something that will compile to that for the target architecture. Since pure C unfortunately doesn't provide a portable way to express this, we use macros to detect language extensions.

```
#define _GNU_SOURCE  // request that string.h define ffsl
#include <stdint.h>
#include <stdlib.h>

#ifdef __unix__
// https://stackoverflow.com/questions/11350878/how-can-i-determine-if-the-operating-system-is-posix-in-c
#include <unistd.h>  // for _POSIX_VERSION
#endif

#ifdef _POSIX_VERSION
#include <strings.h>
#include <string.h>  // for GNU-extension ffsl in case we want that
int bit_position_posix(uint32_t v) {
#ifdef __GNUC__
  // tell the compiler about the assumption that v!=0
  // unfortunately doesn't help gcc or clang make better ffs() code :(  And ICC makes worse code
  if (v == 0)
    __builtin_unreachable();
#endif

  return ffs(v);
}
#endif

#ifdef __GNUC__
int bit_position_gnu(uint32_t v) {
  // v is guaranteed to be non-zero, so we can use a function that's undefined in that case

  // we can count from the front or back, since there's only one bit set
  // but the compiler doesn't know this so we use macros to select a method that doesn't e.g. require an RBIT instruction on ARM

  // TODO: tweak this for more architectures
#if (defined(__i386__) || defined(__x86_64__))
  return __builtin_ctz(v) + 1;
#else
  return 32 - __builtin_clz(v) + 1;
#endif
}
#endif

#ifdef _MSC_VER
// https://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx
#include <intrin.h>
int bit_position_msvc(uint32_t v) {
  unsigned long idx;
  int nonzero = _BitScanForward(&idx, v);
  return idx + 1;
}
#endif

static inline
  int bit_position(uint32_t v)
{
#ifdef __GNUC__
  return bit_position_gnu(v);
#elif defined(_MSC_VER)
  return bit_position_msvc(v);
#elif defined(_POSIX_VERSION)
  return bit_position_posix(v);
#else
  #error no good bitscan detected for this platform
#endif
}

```

sample asm output **from the Godbolt compiler explorer**:

```
# gcc6.2 for x86-64 -O3
bit_position_gnu:
    xor     eax, eax    # break BSF/TZCNT's false dependency on destination
    rep bsf eax, edi    # 3 cycle latency   # runs as BSF on CPUs that don't support TZCNT
    add     eax, 1      # 1 cycle latency
    ret

#MSVC: same thing but without the xor-zeroing
# yes, beta Godbolt has cl.exe installed
bit_position_msvc PROC
    bsf      eax, ecx
    inc      eax
    ret      0
bit_position_msvc ENDP

```

Using count leading vs. count trailing zeros shouldn't hurt the code on x86, but it does. With count-leading, gcc doesn't fold the `33-...` part into the `32-bsr()` that it does as part of implementing the builtin (since BSR produces the bit-index of the high bit, rather than counting leading zeros). See comments on this question and my answer there for more discussion about using `reg_width - __builtin_clzl` vs. using `__builtin_ctz` on power-of-2 integer.

---

**Perf analysis**: (see Agner Fog's instruction tables and microarch pdf, and the SO x86 tag wiki).

ADD is always 1c latency on all x86 CPUs worth mentioning. On Intel Core2, BSF is 2c latency with one per clock throughput. On Nehalem and later (up to Skylake at least), it's 3 cycle latency.

BSF is slow on Atom (16c) and Silvermont (10c), and on P4 Prescott (16c). Some of the pure-C sequences may be faster on those CPUs, since gcc still uses BSF even with `-march=atom` (which implies `-mtune=atom`).

BSF is fairly slow on all AMD CPUs, but TZCNT is fast (2c latency). This is why gcc uses `rep bsf` (which will decode as TZCNT on CPUs which support it, but as just plain BSF on CPUs which don't, ignoring prefixes which don't apply). So on AMD Piledriver and later, this sequence has 3c total latency. But on AMD Bulldozer (which only has LZCNT, not TZCNT), we should have used `32 - lzcnt(v) + 1` (but BSR vs. LZCNT produce different results even for non-zero inputs, so that binary would only be usable on CPUs that support LZCNT).

This is not limited to x86, either:

```
bit_position_gnu:  # ARM gcc5.4 -O3 -mcpu=cortex-a53
    clz     r0, r0
    rsb     r0, r0, #33
    bx      lr

bit_position_gnu:  # ARM64 gcc5.4 -O3
    mov     w1, 33
    clz     w0, w0
    sub     w0, w1, w0
    ret

```

Performance: 2 cycle total latency from `clz` and `sub`. This implies CLZ is always single-cycle on CPUs that support it (ARMv5T and later). I also found info for ARM9E-S specifically that `clz` is single cycle, in my first google hit for `arm clz cycles`.

Reverse-subtract with an immediate, and regular sub with a register, are both almost certainly single-cycle latency. (The mov of the constant in AArch64 is off the critical path, but for in-order CPUs is farther from being free.)

---

When an architecture doesn't have a bit-scan instruction that gcc knows how to use, it emits a call to a library function. e.g.

```
# gcc5.4 for MIPS el with -O3.  Maybe there's an option to enable using clz if it's not baseline?
bit_position_gnu:
    lui     $28,%hi(__gnu_local_gp)
    addiu   $sp,$sp,-32
    addiu   $28,$28,%lo(__gnu_local_gp)
    sw      $31,28($sp)

    lw      $25,%call16(__clzsi2)($28)   ## function address of __clzsi2
    jalr        $25
    nop

    li      $3,33                 # 0x21
    lw      $31,28($sp)
    addiu   $sp,$sp,32
    j       $31
    subu    $2,$3,$2

```

---

I don't have any compilers that support POSIX but not GNU, so I was only able to see if / how the `ffs()` version compiled by making it non-inline. It basically sucks because it accounts for the input=0 case even though we know that can't happen.

---

Related: an SO C++ question, but that doesn't have the simplifying factor that only a single bit is set.
> 2 votes

# Answer
# J - 4 characters

```
2&^.

```

Test:

```
i=: 2^ i. 10
2&^. i
    0 1 2 3 4 5 6 7 8 9

```
> 1 votes

# Answer
## Haskell 65 characters

```
import List
main=n<-readLn;print$findIndices(>n)[2^n|n<-[0..]]!!0

```
> 0 votes

# Answer
If you like to make performance tests, I guess you need really big values for 2^i, so I use BigInt:

```
@annotation.tailrec
def binexp (n: BigInt, sofar: Int = 0): BigInt =
  if (n < 2) 1 + sofar else binexp (n/2, sofar + 1)

```

The annotation is only to check, whether the compiler can perform a tailcall optimization.

I'm curios how you measure this challenge.
> 0 votes

# Answer
**Python, 38 bytes**

```
import math
print int(math.log(input(),2)+1)

```
> 0 votes

# Answer
# Ruby 20

No input or output is necessary because N is given and the question asks for "code":

```
Math::log2(N).to_i+1

```
> 0 votes

# Answer
# K, 8

```
1+&|0b\:

```

.

```
k)(1+&|0b\:)'(2*)\[10;1]
1
2
3
4
5
6
7
8
9
10
11

```
> 0 votes

# Answer
# Mathematica

I was surprised to find that Method #2 is much faster than Method #1.

**Some data**

```
 t = Table[2^k, {k, 0, 10^5}];

```

**Method #1 Log base 2**

```
 Log[2, t]; // AbsoluteTiming

```

> {0.203758, Null}

---

**Method 2: where is the 1 bit?**

```
 Length[IntegerDigits[#, 2]] & t; // AbsoluteTiming

```

Break up the base 2 representation of the number into bits.

Find how many bits there are. (The 1 will always be farthest left.)

> {0.100730, Null}
> 0 votes

# Answer
## Python, 39 chars

```
f=lambda n:len(bin(n))-bin(n).find('1')

```
> 0 votes

# Answer
# JavaScript (ES6), 19 17 bytes

```
a=>Math.log2(a)+1
```
> 0 votes

# Answer
```
n = n - 1; //n is the input no.
count = 0; //count of set bits
while(n = (n & (n-1)))
  count++;
return count + 1;

```
> -1 votes

---
Tags: number, fastest-code, binary, integer
---