title: xkcd-Style Page Numbering

text:
# Question
Title: xkcd-Style Page Numbering
Randall Munroe's book "xkcd, volume 0" uses a rather odd number system for the page numbers. The first few page numbers are

```
1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

```

This looks a bit like ternary, but notice that he skips from `20` straight to `100`, from `120` to `200` and from `200` to `1000`. One way to define this sequence is to say that it enumerates all ternary numbers that contain at most one `2` and no `1` after that `2`. You can find this on OEIS in entry A169683. This number system is known as skew binary.

Your task is to find the representation of a given positive integer `N` in this number system.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be a string, a number with a decimal representation equal to the skew binary representation, or a list of digits (as integers or characters/strings). You must not return leading zeroes.

This is code golf, so the shortest answer (in bytes) wins.

**Fun fact:** There is actually some merit to this number system. When incrementing a number, you will always change at most two adjacent digits - you'll never have to carry the change through the entire number. With the right representation that allows incrementing in O(1).

## Test Cases

```
1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001

1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102

```

I will give a bounty to the shortest answer which can solve the last test case (and any other input of similar magnitude, so don't think about hardcoding it) in less than a second.

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

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

```

```
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```

# Answer
> 12 votes
# Pyth, 17 bytes

```
Ljb3ye.f!-P-yZ01Q

```

This is somewhat ridiculously slow - `O(output^log_2(3))`. It's exponential in the length of the input, but not doubly exponential, like some of the answers on the page. Some ideas taken from @Dennis's answer, here.

Demonstration.

It makes use of `.f`, Pyth's "loop until n matches have been found" function.

# Answer
> 33 votes
# CJam, ~~24~~ ~~23~~ ~~22~~ ~~21~~ 19 bytes

```
ri_)2b,,W%{2\#(md}/

```

This is an **O(log n)** approach, where **n** is the input, that completes the last test case instantly. It converts **n** directly to skew binary, using modular division by the values of the digit **1**.

This code finishes with an error that goes to STDERR with the Java interpreter, which is allowed according to the consensus on Meta.

If you try this code in the CJam interpreter, just ignore everything but the last line of output.

The error can be eliminated, at the cost of 2 bytes, by prepending `2>` to `W%`.

*Thanks to @MartinBüttner for golfing off one byte.*

### Background

The skew binary representation **ak...a0** corresponds to the integer **n = (2k+1-1)ak+...+(21-1)a0**.

Since both **(2k-1) + ... + (21-1) = 2k+1 \- (k + 2)** and **(2k-1) + ... + 2(2j-1) = 2k+1 \- (2j+1 \- 2j \+ k + 1)** are less than **2k+1-1**, the values of **ak** to **a0** can be recovered by successive modular division by **2k+1-1**, **2k-1**, etc.

To begin, we have to find the value of **2k+1-1** first. Since **n** is at most **2(2k+1-1)**, the integer **n + 1** must be strictly smaller than **2k+2**.

Thus, taking the integer part of the binary logarithm of **n + 1** yields **k + 1**.

Finally, we observe that the integer **n + 1** has **⌊log2(n + 1)⌋** digits in base 2.

### How it works

```
ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

```

In the last two iterations, we perform modular division by **1** and **0**. The first pushes an unwanted **0** on the stack. The last attempts to execute `0 0 md`, which pops both unwanted **0**s from the stack, exits immediately instead of pushing anything and dumps the stack to STDOUT.

# Answer
> 28 votes
# Python 2, 67 bytes

```
def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

```

Seems to work for the given test cases. If I've got this right, this should be about `O(place values set in output)`, so it does the last case with ease.

Call like `f(100)`. Returns a decimal representation equal to the skew binary.

# Python 3, 65 bytes

```
def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

```

Slightly less efficient but still logarithmic, so the last case is near-instant.

Call like `g(100)`. Returns a list of digits.

# Answer
> 12 votes
# CJam, ~~22~~ ~~21~~ 20 bytes

```
ri_me,3fb{0-W<1-!},=

```

This is an **O(enn)** approach, where **n** is the input. It lists the first **⌊en** non-negative integers in base 3, eliminates those that have **2**s or **1**s after the first **2** (if any) and selects the **n+1**th.

Try it online in the CJam interpreter.

### How it works

```
ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.

```

# Answer
> 9 votes
# Pyth, 20 bytes

```
Jt^2hslhQ#p/=%QJ=/J2

```

Runs in O(log(input())), well under a second for the final test case. Based around a run until error loop. No trailing newline.

Demonstration.

Explanation:

```
Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

```

J is initialized to the value of the smallest skew binary digit position that is larger than the input. Then, each time through the loop, we do the following:

* Remove each digit of value `J` from `Q` with `=%QJ`. For instance, if `Q=10` and `J=7`, `Q` becomes `3`, which corresponds to the skew binary changing from `110` to `10`. This has no effect in the first iteration.
* Change `J` to the next smaller skew binary base value with `=/J2`. This is floored division by 2, changing `J=7` to `J=3`, for instance. Because this happens before the first digit is output, `J` is intialized one digit position higher than needed.
* Find the actual digit value with `/QJ` (effectively).
* Print that value with `p`, instead of Pyth\`s default printing, to avoid the trailing newline.

This loop will repeat until `J` becomes zero, at which point a divide by zero error will be thrown, and the loop will end.

# Answer
> 8 votes
# ES6, 105 bytes

```
f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

```

Usage is: `f(1048576)` =\> \`"10000000000000000001"

Test the last argument at your own peril. I gave up after 5 seconds.

And pretty print with comments!

```
f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3

```

# Answer
> 7 votes
# Retina, 55 bytes

```
^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

```

Takes input in unary.

Each line should go to its own file but you can run the code as one file with the `-s` flag. E.g.:

```
> echo 11111|retina -s skew
12

```

Method: Executes incrementation on a string input number times starting from the string `0`.

We use the following incrementation rules:

* if contains `2`: `^2 -> ^12`; `02 -> 12`; `12 -> 20`
* if doesn't contain `2`: `0$ -> 1$`; `1$ -> 2$`

(There can be at most one `2` in the string; `^` and `$` marks the start and end of the string in the rules.)

More information about Retina.

# Answer
> 7 votes
# Java, ~~154~~ 148

```
n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

```

This answer take the form of a single anonymous function that takes an integer argument and returns the answer as a String. Below is a complete class for testing this solution.

```
import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}

```

# Answer
> 5 votes
# Java, ~~337~~ ~~335~~ ~~253~~ ~~246~~ 244 bytes

A method that takes in the index as a `long` and returns the result as a string

Uses a `long` for the index so can *theoretically* handle the last test case, but I *really* wouldn't suggest it.

```
String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}

```

# Answer
> 5 votes
# Bash + coreutils, 52

```
dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

```

This is a brute-forcer, so its rather slow for larger numbers.

### Output:

```
$ ./xkcdnum.sh 1000
111110120
$

```

# Answer
> 4 votes
# CJam, 24 bytes

```
Q{0\+2a/())+a\+0a*}ri*si

```

This is an **O(n log n)** approach, where **n** is the input. It starts with the skew binary representation of **0** and increments the corresponding integer **n** times.

Try it online in the CJam interpreter.

### Background

Incrementing a number in skew binary can be done by following two easy steps:

1. Replace an eventual **2** by a **0**.
2. If a **2** has been replaced, increment the digit to its left.

Otherwise, increment the last digit.

### How it works

```
Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.

```

# Answer
> 4 votes
# Haskell, ~~73~~ 72

Thanks to @nimi for 1 byte!

This solution won't be winning any bounty, the last couple tests take an inordinate amount of time to run, but, I think I've golfed it fairly well.

```
i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

```

This solution is a rather naïve approach that calculates the skew binary number `n` by incrementing 0 `n` times.

# Answer
> 4 votes
# VBA, ~~209~~ ~~147~~ 142 bytes

```
Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

```

My math is inefficient and my golfing could use work. But it's my first attempt at PoG and thought I'd give this one a try. Sort of a Brute Force way though.

It's just counting by 1 unless the last digit is a 2 then steps back by 2 and jumps forward 10. Plus the trailing 0's.

This stops working at 65534 because VBA insists on giving output in scientific notation, but the logic should work fine for even higher numbers

Looking forward to golfing suggestions, VBA is not very golf-friendly but it's not often represented, and I think it can beat Java for length.

Edit1: Thanks **Manu** for helping shave off 62 bytes

Edit2: Swapped `debug.print` for `msgbox` as output. Saved 5 bytes

# Answer
> 4 votes
# Javascript ES6, ~~99~~ ~~86~~ ~~78~~ ~~76~~ 72 chars

```
f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

```

Test:

```
;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

```

> **Fun fact:** There is actually some merit to this number system. When incrementing a number, you will always change at most two adjacent digits - you'll never have to carry the change through the entire number. With the right representation that allows incrementing in O(1).

Thank you for the fact - it is the base of my solution :)

# Answer
> 3 votes
# Octave, ~~107~~ 101 bytes

Should be **O(log n)** if I'm figuring this right...

```
function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

```

Pretty-print:

```
function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

```

I was somewhat stymied addressing the final challenge, since Octave by default treats everything as floating point numbers and I didn't have the necessary precision to calculate the last one. I got around that by spending precious bytes to force everything to be an unsigned integer. The result of the last one was too big to treat as a number, so the result is a string.

Output (I'm including `1e18 - 1` to show I can do that accurately, and the last set of outputs shows how long it takes to calculate that value):

```
octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.

```

# Answer
> 3 votes
## T-SQL, ~~221~~ ~~189~~ 177 bytes

EDIT: The original versions of this code would produce incorrect output for some numbers, this has been corrected.

With every query here, just add the number to calculate before the first comma.

Everyone know that T-SQL is the best golfing language. Here is a version that will calculate even the last test case. On the machine I tested it on, it ran in under a second, I'd be interested to see how it runs for everyone else.

```
DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

```

And here it is again, but readable:

```
DECLARE
    @ BIGINT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I

    UNION ALL

    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M
ORDER BY I DESC

SELECT @T

```

---

If I only use ints, this can be a bit shorter, coming out at 157 bytes:

```
DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

```

And once more again, more readable:

```
DECLARE
    @ INT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        2I

    UNION ALL

    SELECT
        I * 2
    FROM M
    WHERE I < @
)

SELECT
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M
ORDER BY I DESC

SELECT @T

```

# Answer
> 3 votes
# Turing Machine Code, ~~333~~ 293 bytes

I'm using an encoding as used here.

This machine uses 9 states and 11 colors.

If binary input is permissible, this can be reduced to a mere 4 colors, saving a few tens of bytes in the process.

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

```

If the above link isn't working (sometimes it works for me, other times the page refuses to load) you may also test this using this java implementation.

# Answer
> 2 votes
# Perl, 66 bytes

Number is to be input through STDIN.

```
$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;

```

# Answer
> 2 votes
# Perl, ~~84~~ ~~70~~ 67 bytes

```
$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

```

~~Not very golfy,~~ Getting better but it does work very quickly!

Dennis's suggestion gets it down to 51 (50 bytes + -p switch)

```
$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

```

It *must* be called like `perl -p skew_binary.pl num_list.txt` where `num_list.txt` contains a single line with the number to encode on it.

# Answer
> 2 votes
# Pyth, 19 bytes

```
m/=%Qtydtd^L2_SslhQ

```

Logarithmic complexity. Easily finishes in the necessary amount of time. Output in the form of a list of digits.

Demonstration.

# Answer
> 2 votes
# JavaScript (Node.js), 40 bytes

```
v=>(g=n=>n>v?'':g(n-~n)+(v-(v%=n))/n)(1)

```

Try it online!

This solution does not work on last testcase. It just cause stack overflow on it.

# Answer
> 1 votes
## Mathematica, 65

Should be quite fast enough, although I have to admit I peeked at the other submissions before making this.

```
f = (n = #;
     l = 0;
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

```

Usage:

```
f[1000000000000000000]

```

Output:

```
11011110000010110110101100111010011101100100000000000001102

```

Starts giving MaxExtraPrecision error messages somewhere past 10^228 (for which it calculates the result in .03 seconds on my machine)

After removing the MaxExtraPrecision limit, it will handle numbers up to around 10^8000 in a second.

Input:

```
Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

```

Output:

```
{1.060807, Null}

```

# Answer
> 1 votes
# C, 95 bytes

```
void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

```

This accepts an integer and a buffer in which to return the digits. The results are stored in `b`, terminated with value `3` (which can't occur in the output). We don't have to handle input of `0` (as the question specified only positive integers), so there's no special-casing to avoid empty output.

### Expanded code

```
void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

```

We operate by successive subtraction, starting with the most significant digit. The only complication is that we use the variable `m` to avoid printing leading zeros. A natural extension to `unsigned long long` may be made if desired, at the cost of 10 bytes.

### Test program

Pass numbers to be converted as command arguments. It converts the `int` array buffer to a printable digit string. Runtime is less than one millisecond for input `1000000000000000000`.

```
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

```

### Test results

```
$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012

```

# Answer
> 0 votes
## CoffeeScript, ~~92~~ 69 bytes

Based of Qwertiy's answer and updates:

```
f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s

```

# Answer
> 0 votes
# Japt, 31 bytes

```
_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

```

Try it online!

Almost direct port of this JS solution. No idea if there's better way.

### Unpacked & How it works

```
X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times

```

# Answer
> 0 votes
# Stax, 16 bytes

```
üxëàè£öΦGΩ│Je5█ò

```

Run and debug it

I'm not sure exactly what the formal complexity class is, but it's fast enough to do all the test cases in a tenth of a second on this machine.

Unpacked, ungolfed, and commented, it looks like this. In this program, the x register originally contains the input.

```
z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

```

Run this one

# Answer
> 0 votes
# Husk, 16 bytes

```
!mdfö¬f≠1hfImB3N

```

Try it online! or Verify first 100 values

Same method as Dennis' CJam answer.

---
Tags: code-golf, number, sequence, base-conversion
---


title: Find the nearest biquadratic number

text:
# Question
Title: Find the nearest biquadratic number
A biquadratic number is a number that is the fourth power of another integer, for example: `3^4 = 3*3*3*3 = 81`

Given an integer as input, output the closest biquadratic number.

Here are the first 15 double-squares:

```
1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, 14641, 20736, 28561, 38416, 50625

```

This is so fewest bytes **in each language** wins

This is OEIS A000583

# Answer
# Python 3, 35 bytes

```
lambda n:int((n**.5-.75)**.5+.5)**4

```

Try it online!

### How it works

The value *n* at which the output switches from (*k* − 1)4 to *k*4 satisfies √(√n − 3/4) + 1/2 = *k*, or *n* = ((k − 1/2)2 \+ 3/4)2 = (*k*2*k* \+ 1)2 = ((*k* − 1)4 \+ *k*4 \+ 1)/2, which is exactly the first integer that’s closer to *k*4.

(Works for all *n* ≤ 4504699340341245 = (81924 \+ 81934 − 7)/2 \> 252, after which floating-point roundoff starts to break it, even though it works mathematically for all *n*.)
> 16 votes

# Answer
# Octave, 35 bytes

This challenge needed a convolution-based approach.

```
@(n)sum(n>conv((1:n).^4,[1 1]/2))^4

```

**Try it online!**

### Explanation

The expression `(1:n).^4` produces the row vector `[1 16 81 256 ... n^4]`.

This vector is then convolved with `[1 1]/2`, which is equivalent to computing the sliding average of blocks of size `2`. This implicitly assumes that the vector is left- and right-padded with `0`. So the first value in the result is `0.5` (average of an implicit `0` and `1`), the second is `8.5` (average of `1` and `16`), etc.

As an example, for `n = 9` the result of `conv((1:n).^4,[1 1]/2)` is

```
0.5 8.5 48.5 168.5 440.5 960.5 1848.5 3248.5 5328.5 3280.5

```

The comparison `n>...` then yields

```
1 1 0 0 0 0 0 0 0 0 0

```

and applying `sum(...)` gives `2`. This means that `n` exceeds exactly `2` of the mid-points betwen biquadratic numbers (including the additional mid-point `0.5`). Finally, `^4` raises this to `4` to yield the result, `16`.
> 8 votes

# Answer
# Haskell, ~~51~~ 49 bytes

Function monad ftw!

```
f n=snd.minimum$(abs.(n-)<$>)>>=zip$(^4)<$>[1..n]

```

Try it online!

Explanation:

```
                                (^4)<$>[1..n] -- creates a list of fourth powers
            (abs.(n-)<$>)>>=zip               -- creates a list of |n-(4th powers)| and
                                              -- zips it with the 4th powers list
    minimum                                   -- finds the minimum
                                              -- (only first tuple entry matters)
snd                                           -- exctracts the second entry (the 4th power)

```
> 7 votes

# Answer
# MATL, 6 bytes

```
t:4^Yk

```

**Try it online!**

### Explanation

Consider input `9` as an example.

```
t    % Implicitly input n. Duplicate
     % STACK: 9, 9
:    % Range [1 2 ... n]
     % STACK: 9, [1 2 3 4 5 6 7 8 9]
4^   % Raise to 4, element-wise
     % STACK: 9, [1 16 81 256 625 1296 2401 4096 6561]
Yk   % Closest element. Implicitly display
     % STACK: 16

```
> 6 votes

# Answer
# Neim, 5 bytes

```
4S

```

Explanation:

```
       Inclusive range [1 .. input]
      Raise to the  v  power
 4                   4th
       Select the value closest to
    S   the input

```

Try it online!
> 5 votes

# Answer
# Brachylog, 9 bytes

```
;I≜+.~^₄∧

```

Try it online!

### Explanation

```
;I≜          I = 0 / I = 1 / I = -1 / I = 2 / etc. on backtracking
   +.        Output = Input + I
    .~^₄     Output = Something to the power 4
        ∧

```
> 5 votes

# Answer
## Excel, 25 bytes

```
=INT((A1^.5-3/4)^.5+.5)^4

```

Excel updates this to `=INT((A1^0.5-3/4)^0.5+0.5)^4`
> 5 votes

# Answer
## Mathematica, 21 bytes

```
Nearest[Range@#^4,#]&

```
> 4 votes

# Answer
# 05AB1E, 6 bytes

```
LnnI.x

```

Try it online!

### Explanation

```
LnnI.x
L      # Push [1 .. input]
 nn    # Raise every element to the 4th power
   I   # Push input
    .x # Closest element in the array to input

```
> 3 votes

# Answer
## JavaScript (ES7), 42 bytes

```
x=>(n=x**.25|0,x-(k=n**4)<++n**4-x?k:n**4)

```

### Recursive version, 44 bytes

```
f=(x,k,b)=>(a=k**4)>x?a-x>x-b?b:a:f(x,-~k,a)

```

### Demo

```
let f =

x=>(n=x**.25|0,x-(k=n**4)<++n**4-x?k:n**4)

console.log(f(16))
console.log(f(48))
console.log(f(49))
```
> 3 votes

# Answer
# Octave, 37 bytes

```
@(n)interp1(t=(1:n).^4,t,n,'nearest')

```

Anonymous function that uses nearest-neighbour interpolation.

**Try it online!**
> 3 votes

# Answer
# Jelly, 6 bytes

```
R*4ạÐṂ

```

A monadic link returning a list of one item, or a full program that prints the result (using an inefficient method).

**Try it online!**

### How?

```
R*4ạÐṂ - Link: number, n
R      - range(n) -> [1,2,3,...,n]
 *4    - raise to the fourth power -> [1,16,81,...,n**4]
    ÐṂ - filter keep those (only ever one) minimal:
   ạ   -   absolute difference (with n)
       - if a full program: implicit print (one item lists print their content).

```
> 3 votes

# Answer
# APL, 22 bytes

```
{o/⍨p=⌊/p←|⍵-⍨o←4*⍨⍳⍵}

```

Try it online!

**How?**

`o←4*⍨⍳⍵` \- `o` = range()4 \[vectorize\]

`p←|⍵-⍨o` \- `p` = abs(`o` \- ) \[vectorize\]

`o/⍨` \- take the `o` element at the index where ...

`p=⌊/p` \- the `p` minimum element is
> 2 votes

# Answer
# Husk, ~~10~~ 7 bytes

*Edit: -3 bytes thanks to Razetime*

```
◄≠¹m^4ḣ

```

Try it online!

```
◄≠¹m^4ḣ
◄               # minimum element based on
 ≠¹             # difference to input,
      ḣ         # of series from 1 up to input
   m^4          # to the power of 4

```
> 2 votes

# Answer
# Pyth, 9 bytes

```
.maQb^R4S

```

Try it online!

---

### Pyth, 17 bytes

A full program that uses the same arithemtic approach as in @AndersKaseorg's answer:

```
K.5^s+^-^QK.75KK4

```

Try it online!
> 1 votes

# Answer
# PHP, 33 bytes

```
<?=(($argn**.5-.75)**.5+.5^0)**4;

```

Try it online!

# PHP, 56 bytes

```
<?=2*$argn-($x=($f=$argn**.25^0)**4)>($y=++$f**4)?$y:$x;

```

Try it online!
> 1 votes

# Answer
**C++, 96 bytes**

```
int Q(int N){int i=1;while (pow(i,4)<N){i++;}if (pow(i,4)-N>N-pow(i-1,4)){i--;}return pow(i,4);}

```

Full version:

```
int Q(int N)
{
    int i = 1;

    while (pow(i, 4) < N)
    {
        i++;
    }

    if (pow(i, 4)-N > N-pow(i - 1, 4))
        i--;

    return pow(i,4);
}

```

LINK to try
> 1 votes

# Answer
# Haskell, 35 bytes

```
f n=(floor$(n**0.5-3/4)**0.5+0.5)^4

```

Port of Anders' Python3 answer.
> 1 votes

# Answer
# , ~~47~~ ~~44~~ ~~37~~ 35 bytes

```
n=scan();which.min(((1:n)^4-n)^2)^4

```

Try it online!
> 1 votes

# Answer
# Stax, 10 bytes

```
Ç∞§δo╧╖s►M

```

Run and debug it
> 1 votes

# Answer
# Japt `-g`, ~~20~~ ~~8~~ 7 bytes

~~This feels far too long!~~ I was right!

```
Ç²²ÃñaU

```

Try it

```
Ç²²ÃñaU     :Implicit input of integer U
Ç           :Map the range [0,U)
 ²²         :  Square twice
   Ã        :End map
    ñ       :Sort by
     aU     :  Absolute difference with U
            :Implicit output of first element

```

## Without flag, 8 bytes

```
È¬¬v1}cU

```

Try it

```
È¬¬v1}cU     :Implicit input of integer U
È            :Function taking an integer X as argument
 ¬           :  Square root
  ¬          :  Square root
   v1        :  Divisible by 1?
     }       :End function
      cU     :Return the first X in the sequence [U,U-1,U+1,U-2,U+2,U-3,...] that returns true

```
> 0 votes

# Answer
# QBIC, 38 bytes

```
{p=q^4~p>:|~p-a>a-o|_Xo\_Xp]\o=p┘q=q+1

```

## Explanation

```
{           DO infinitely
p=q^4       Set p to q quad (q starts out as 1)
~p>:|       IF p exceeds the input THEN
~p-a>a-o    check the distance to p and to o (the last quad) and
|_Xo        PRINT o, or
\_Xp        PRINT p accordingly
]           END IF
\o=p        ELSE  ( p <= input) store p in o to keep track of this quad
┘q=q+1      and raise q for the next iteration

```
> 0 votes

# Answer
# Java (OpenJDK 8), 64 bytes

```
n->{int i=0,q,Q=0;while((q=i*i*i*i++)<n)Q=q;return q-n<n-Q?q:Q;}

```

Try it online!
> 0 votes

# Answer
# Ruby, ~~23~~ 34 bytes

I have no idea why `0.75` is such an important number for this, but hey, whatever works.

```
->n{((n**0.5-0.75)**0.5).round**4}

```

Try it online!
> 0 votes

# Answer
# Common Lisp, 50 bytes

```
(lambda(x)(expt(floor(+(sqrt(-(sqrt x).75)).5))4))

```

Try it online!
> 0 votes

# Answer
# C#, 95 bytes

```
namespace System.Linq{n=>new int[940].Select((_,i)=>i*i*i*i).OrderBy(i=>Math.Abs(i-n)).First()}

```

We use 940 as a set value as any larger value will overflow the int.

Full/Formatted Version:

```
namespace System.Linq
{
    class P
    {
        static void Main()
        {
            Func<int, int> f = n => new int[940].Select((_, i) => i * i * i * i).OrderBy(i => Math.Abs(i - n)).First();

            for (int i = 1; i <= Int32.MaxValue; ++i)
                Console.WriteLine($"{i} = {f(i)}");

            Console.ReadLine();
        }
    }
}

```
> 0 votes

---
Tags: code-golf, sequence, number-theory, integer
---


title: The Saltine Challenge

text:
# Question
Title: The Saltine Challenge
Here is an ASCII saltine cracker:

```
 _________________
|  .     .     .  |
|     .     .     |
|  .     .     .  |
|     .     .     |
|  .     .     .  |
|_________________|

```

Here are two crackers stacked:

```
 _________________
|  .     .     .  |
|     . __________|______
|  .   |  .     .     .  |
|     .|     .     .     |
|  .   |  .     .     .  |
|______|     .     .     |
       |  .     .     .  |
       |_________________|

```

Write the shortest program possible that takes a positive integer and draws a stack of that many ASCII saltine crackers.

Input may come from stdin, command line, or you may simply write a function. The input will always be valid. Output must go to stdout or closest alternative.

Each stacked cracker is always shifted 2 characters down and 7 characters right of the cracker below it. There should be no trailing spaces or extraneous newlines.

The shortest program in bytes wins.

# Examples

If the input is `1` the output is

```
 _________________
|  .     .     .  |
|     .     .     |
|  .     .     .  |
|     .     .     |
|  .     .     .  |
|_________________|

```

If the input is `2` the output is

```
 _________________
|  .     .     .  |
|     . __________|______
|  .   |  .     .     .  |
|     .|     .     .     |
|  .   |  .     .     .  |
|______|     .     .     |
       |  .     .     .  |
       |_________________|

```

If the input is `3` the output is

```
 _________________
|  .     .     .  |
|     . __________|______
|  .   |  .     .     .  |
|     .|     . __________|______
|  .   |  .   |  .     .     .  |
|______|     .|     .     .     |
       |  .   |  .     .     .  |
       |______|     .     .     |
              |  .     .     .  |
              |_________________|

```

And so on.

*the real saltine challenge*

# Answer
> 4 votes
# CJam, ~~140~~ ~~125~~ ~~119~~ 116 bytes

```
li__7*C+S*a\2*5+*\{5m>S'|6*+_" ."5*5/{'__@\++}:U%3*0@t{S5*U_}%\a+zsB'|tJ/{\(J>@\+a+}/{7m<}%}*{Cm<0{;)_' =}g+}%N*B'_t

```

Try it online.

### A single saltine

The code snippet

```
S'|6*+_      " Push ' ||||||' twice.                                                      ";
" ."5*5/     " Push [' . . ' '. . .'].                                                    ";
{'__@\++}:U% " Prepend and append an underscore to each string in the previous array.     ";
3*           " Repeat the resulting array thrice.                                         ";
0@t          " Replace its first element with ' ||||||'.                                  ";
{S5*U_}%     " Insert '_     _' after each element of the array.                          ";
\a+          " Append ' ||||||' to the array.                                             ";
z            " Zip; transpose rows with columns.                                          ";
sB'\t        " Flatten the array of strings and replace the 12th element with a '|'.      ";
19/          " Split into chunks of length 19.                                            ";

```

leaves the following on the stack:

```
[
  " __________|______ "
  "|  .     .     .  |"
  "|     .     .     |"
  "|  .     .     .  |"
  "|     .     .     |"
  "|  .     .     .  |"
  "|_________________|"
]

```

### Stacked saltines

Assume the saltine from above is saved in Z.

```
li               " I := int(input())                                                      ";
__7*C+S*a\2*5+*  " R:= [(I * 7 + 12) * ' '] * (I * 2 + 5)                                 ";
\{               " Repeat I times:                                                        ";
  5m>            "   R := R[-5:] + R[:-5]                                                 ";
  Z              "   Push a single saltine, as an array of lines.                         ";
  {              "   For each line L of the saltine:                                      ";
    \(J>@\+a+    "     R := R[1:] + [R[0][19:] +     L]                                   ";
  }/             "                                                                        ";
  {7m<}%         "   R := [ L[7:] + L[:7] : L in R ]                                      ";
}*               "                                                                        ";
{                " R := [                                                                 ";
  Cm<            "   (L[12:] + L[:12])                                                    ";
  0{;)_' =}g+    "                    .rstrip()                                           ";
}%               " : L in R ]                                                             ";
N*               " R := '\n'.join(R)                                                      ";
B'_t             " R[11] := '|'                                                           ";

```

# Answer
> 11 votes
## JavaScript (E6) 249  ~~259 289 304 345~~

~~Not so confident about the string compression.~~  Found a good compression for the strings. ~~The simple 1 cracker case seems difficult to manage. There may be a better way...~~

```
F=n=>{
  for(B=",|4.,|1.2,|1.4.4.1|,|5,|4.4.4|, 9|5, 87 ,|87|".replace(/\d/g,c=>' _'[c>4|0][R='repeat'](-~c)).split(','),
  O=(c,b=0,a=0)=>console.log(' '[R](y)+B[a]+B[b][R](x)+B[c]),
  r=x=y=0,
  O(7);
  O(3,2),
  !(z=++r>2)|x;)
    x+=(v=r<n)-z,O(v+5,1,z*4),y+=z*7;
  O(8)
}

```

**Ungolfed** more or less

That is the basic code, before I started golfing. It's not exactly the same and works only for n \> 2

```
F=n=>{
  O=t=>console.log(t)

  r=0
  x=0
  y=0

  O(' _________________')
  O(' '.repeat(y)+'|  .   '.repeat(x)+'|  .     .     .  |')

  while (++r<n)
  {
    x++;
    if (r>2)
    {
       x--;
       O(' '.repeat(y)+'|______'+'|     .'.repeat(x)+' __________|______')
       y+=7;
       O(' '.repeat(y)+'|  .   '.repeat(x)+'|     .     .     |')
    }
    else
    {
       O(' '.repeat(y)+'|     .'.repeat(x)+' __________|______')
       O(' '.repeat(y)+'|  .   '.repeat(x)+'|  .     .     .  |')
    }

  }
  while(x--)
  {
     O(' '.repeat(y)+'|______'+'|     .'.repeat(x)+'|  .     .     .  |')
     y+=7;
     O(' '.repeat(y)+'|  .   '.repeat(x)+'|     .     .     |')
  }

  O(' '.repeat(y)+'|_________________|')
}

```

**Test** In FireFox/FireBug console

```
F(4)

```

*Output*

```
 _________________
|  .     .     .  |
|     . __________|______
|  .   |  .     .     .  |
|     .|     . __________|______
|  .   |  .   |  .     .     .  |
|______|     .|     . __________|______
       |  .   |  .   |  .     .     .  |
       |______|     .|     .     .     |
              |  .   |  .     .     .  |
              |______|     .     .     |
                     |  .     .     .  |
                     |_________________|

```

# Answer
> 8 votes
# Python, ~~252~~ 241 characters

```
s="eJxTiIeDGgiloBBRo6CgpwACcLIGJKaAKlxDmbp4dFADAL+oIFI=".decode('base64').decode('zip').split('X')
N=input()
R=range
G=map(list,[' '*(7*N+12)]*(2*N+5))
for n in R(N):
 for y in R(7):G[2*n+y][7*n:]=s[y]
G[0][11]='_'
for g in G:print''.join(g)

```

Thanks to FryAmTheEggman and Vincent for snipping off 11 characters.

A preponderance of crackers:

```
$ echo 17 | python saltines.py
 _________________
|  .     .     .  |
|     . __________|______
|  .   |  .     .     .  |
|     .|     . __________|______
|  .   |  .   |  .     .     .  |
|______|     .|     . __________|______
       |  .   |  .   |  .     .     .  |
       |______|     .|     . __________|______
              |  .   |  .   |  .     .     .  |
              |______|     .|     . __________|______
                     |  .   |  .   |  .     .     .  |
                     |______|     .|     . __________|______
                            |  .   |  .   |  .     .     .  |
                            |______|     .|     . __________|______
                                   |  .   |  .   |  .     .     .  |
                                   |______|     .|     . __________|______
                                          |  .   |  .   |  .     .     .  |
                                          |______|     .|     . __________|______
                                                 |  .   |  .   |  .     .     .  |
                                                 |______|     .|     . __________|______
                                                        |  .   |  .   |  .     .     .  |
                                                        |______|     .|     . __________|______
                                                               |  .   |  .   |  .     .     .  |
                                                               |______|     .|     . __________|______
                                                                      |  .   |  .   |  .     .     .  |
                                                                      |______|     .|     . __________|______
                                                                             |  .   |  .   |  .     .     .  |
                                                                             |______|     .|     . __________|______
                                                                                |  .   |  .   |  .     .     .  |
                                                                                |______|     .|     . __________|______
                                                                                |  .   |  .   |  .     .     .  |
                                                                                |______|     .|     . __________|______
                                                                                |  .   |  .   |  .     .     .  |
                                                                                |______|     .|     .     .     |
                                                                                |  .   |  .     .     .  |
                                                                                |______|     .     .     |
                                                                                |  .     .     .  |
                                                                                |_________________|

```

This code seems really inefficient, but other answers will tell. It just copies and pastes the saltine cracker into an array at the right spot, accounts for the bottom-most cracker being 1-character off, then prints it all.

I can get it down to **230 characters** if I use an external file (202 code + 38 file size + 1 file name).

# Answer
> 7 votes
# Perl 189

Stealing some string compression ideas from choroba, I got it down to:

```
echo 4 | perl -E 's/\d/($&<8?$":_)x$&/ge for@l=("|2.5.5.2|"," 98","|5.5.5|","|98|",7)[102020344=~/./g];map{say for@l[0,1];$l[$_]=substr($l[$_+2],0,7).$l[$_]for 0..6;substr$l[0],-7,1,"|"}2..<>;say for@l[0..6]'

```

For easier viewing in your browser:

```
s/\d/($&<8?$":_)x$&/ge for@l=
("|2.5.5.2|"," 98","|5.5.5|","|98|",7)[102020344=~/./g];map{
    say for@l[0,1];
    $l[$_]=substr($l[$_+2],0,7).$l[$_]for 0..6;
    substr$l[0],-7,1,"|"
}2..<>;say for@l[0..6]

```

For context, my best before that:

# Perl 207

```
$u='_'x11;s/:/ .  /g,s/.(.)/$&$1/g,$_.=$/for@l=("|:: . |"," $u","|  :: |","|$u|",$"x5)[102020344=~/./g];map{print@l[0,1];$l[$_]=substr($l[$_+2],0,7).$l[$_]for 0..6;substr$l[0],-8,1,'|'}2..pop;print@l[0..6]

```

Adding newlines and indentation for ease of reading in your browser:

```
$u="_"x11;
s/:/ .  /g,s/.(.)/$&$1/g,$_.=$/for@l=
("|:: . |"," $u","|  :: |","|$u|",$"x5)[102020344=~/./g];
map{
    print@l[0,1];
    $l[$_]=substr($l[$_+2],0,7).$l[$_]for 0..6;
    substr$l[0],-8,1,"|"
}2..pop;
print@l[0..6]

```

You can replace "pop" with "\<\>" to take the count from STDIN instead of as a command-line parameter and get to 206 bytes. Going to STDERR would drop it to 204 bytes.

If I could enable the 'say' feature without a byte penalty, then I could get to 202.

```
$u="_"x11;s/:/ .  /g,s/.(.)/$&$1/g for@l=("|:: . |"," $u","|  :: |","|$u|",$"x5)[102020344=~/./g];map{say for@l[0,1];$l[$_]=substr($l[$_+2],0,7).$l[$_]for 0..6;substr$l[0],-7,1,"|"}2..<>;say for@l[0..6]

```

invoked as:

```
echo 4 | perl -E '$u="_"x11;s/:/ .  /g,s/.(.)/$&$1/g for@l=("|:: . |"," $u","|  :: |","|$u|",$"x5)[102020344=~/./g];map{say for@l[0,1];$l[$_]=substr($l[$_+2],0,7).$l[$_]for 0..6;substr$l[0],-7,1,"|"}2..<>;say for@l[0..6]'

```

# Answer
> 4 votes
# Perl 201

(remove newlines except the first one to get the #)

```
$_=" 46|6
15.5.5|15.5.5|198|";
s/1/|  .5.5.  ||/g;
s/\d/(5^$&?_:$")x$&/ge;
@o=@l=/.{18}.?/g;
map{
$s=$_*7;
substr$o[$_-5],$s,12,$l[$_]for 0..4;
push@o,($"x$s).$l[$_]for 5,6
}1..-1+pop;
$o[$,=$/]=~y/|/_/;
print@o

```

`say` \+ `<>` = 198.

# Answer
> 2 votes
# Haskell, 215 bytes

This one builds up the cracker stack inductively, pulling cracker parts and spacing out of a couple of cyclic lists:

```
(b:u:i)=" _|"
(%)=replicate
z=5%b++'.':z
m!n=i++map(z!!)[m..n]
s=7%b:s
d=3!19++i
e=0!16++i
y=i++6%u
g 1=[e,d,e,d,i++17%u++i]
g k=zipWith(++)(0!5:3!8:0!5:3!8:y:s)$(b:10%u++y):d:g(k-1)
f k=mapM putStrLn$(b:17%u):d:g k

```

The control flow is pretty straightforward; most of the trickery is in reusing as much of the cracker parts as possible.

**Ungolfed:**

```
top     = " _________________"
top'    = " __________|______"
dots3   = "|  .     .     .  |"
dots2   = "|     .     .     |"
bot     = "|_________________|"

halfR   = "|     ."
halfL   = "|  .   "
halfBot = "|______"

spacer  = "       "
spaces = repeat spacer

saltine = above ++ [dots2, dots3, dots2, dots3, bot]
above   = [top, dots3]
left    = [halfR, halfL, halfR, halfL, halfBot] ++ spaces

another (oldTop:oldCracker) = above ++ zipWith (++) left (top' : oldCracker)

crackers 1 = saltine
crackers k = another $ crackers (k - 1)

test = putStr . unlines . crackers

```

# Answer
> 1 votes
# Python, 299

I thought I was being clever but the solution turned out to be overly complicated and longer than any straight forward approach, yet I couldn't resist to post it. The program explicitly calculates which character has to be plotted at the different positions of the output string, without looping over the individual crackers.

```
N=input()
m,n,c,r=12+7*N,5+2*N,3.5,range
print''.join(i>m-2and'\n'or(i%7<(i/c<j<7+i/c)*(i<N*7)or(i+4)%7<(i/c<j+4<2+4*(i>m-3)+i/c)*(i>16))and'|'or j%2<(j*c<i<17+j*c)*(j<n-5)+(j*c<i+22<8+10*(j>n-3)+j*c)*(j>5)and'_'or(i-j*3-min(i/7,~-j/2,N-1)+1)%6<(-3<-~i/7-j/2<3)and'.'or' 'for j in r(n)for i in r(m))

```

And the last line expanded to see what's going on:

```
print ''.join(
              '\n' if i>m-2 else
              '|' if i%7<(i/c<j<7+i/c)*(i<N*7) or (i+4)%7<(i/c<j+4<2+4*(i>m-3)+i/c)*(i>16) else
              '_' if j%2<(j*c<i<17+j*c)*(j<n-5)+(j*c<i+22<8+10*(j>n-3)+j*c)*(j>5) else
              '.' if (i-j*3-min(i/7,~-j/2,N-1)+1)%6<(-3<-~i/7-j/2<3) else
              ' '
              for j in r(n)
              for i in r(m)
             )

```

# Answer
> 1 votes
# C,284

For the function `f` and the `#define`s, excluding unnecessary whitespace and `main`. In accordance with edc65's comment, I have included a 128-bit integer type (which I was going to do anyway) but I miscalculated *again* and I can only do 29 crackers before the tops start going missing.

Complete function and test program below. Will comment it later.

```
#define C b,b,c,b,b
#define S s[i/v*7-i%v
f(n){
  __int128 a=4095,b=a+2,c=6281,d=4641,w=998,v=19,s[998]={a,C,d,C,d,C,a},i=v;
  for(;i<n*v;i++)S+18]|=S+11]*16&-1<<(12+i/v*2-i%v/18)*(i%v>7);
  for(i=(5+n*2)*w;i--;i%w||puts(""))i%w>i/w/2*7-21+i/w%2*6&&s[i%w]&&putchar(" _.|"[(s[i%w]>>i/w*2)&3]);
}

main(){
  int m;
  scanf("%d",&m);f(m);
}

```

There are only four different characters in the output. These are decoded from binary numbers 0-3 by `" _.|"`. The array `s[]` contains an integer for each column of the output, 2 bits per symbol, which is intitialised to contain the rightmost cracker.

The first `for` loop copies the previous cracker, leftshifts it to move it up, deletes the bottom right corner using `&`  and ORs it with the previous cracker, 7 steps to the left.

The second `for` loop decodes the 2-bit representation of each character into the actual character and prints the character. There's a lot of code here just to suppress unnecesary whitespace in the output. I'm disappointed that my score went up instead of down from my previous revision.

**Output**

That's 29 crackers. I replaced the space with a `-` for a different look, and to show that no trailing spaces or extraneous newlines in the output.

```
-_________________
|--.-----.-----.--|
|-----.-__________|______
|--.---|--.-----.-----.--|
|-----.|-----.-__________|______
|--.---|--.---|--.-----.-----.--|
|______|-----.|-----.-__________|______
-------|--.---|--.---|--.-----.-----.--|
-------|______|-----.|-----.-__________|______
--------------|--.---|--.---|--.-----.-----.--|
--------------|______|-----.|-----.-__________|______
---------------------|--.---|--.---|--.-----.-----.--|
---------------------|______|-----.|-----.-__________|______
----------------------------|--.---|--.---|--.-----.-----.--|
----------------------------|______|-----.|-----.-__________|______
-----------------------------------|--.---|--.---|--.-----.-----.--|
-----------------------------------|______|-----.|-----.-__________|______
------------------------------------------|--.---|--.---|--.-----.-----.--|
------------------------------------------|______|-----.|-----.-__________|______
-------------------------------------------------|--.---|--.---|--.-----.-----.--|
-------------------------------------------------|______|-----.|-----.-__________|______
--------------------------------------------------------|--.---|--.---|--.-----.-----.--|
--------------------------------------------------------|______|-----.|-----.-__________|______
---------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
---------------------------------------------------------------|______|-----.|-----.-__________|______
----------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
----------------------------------------------------------------------|______|-----.|-----.-__________|______
-----------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
-----------------------------------------------------------------------------|______|-----.|-----.-__________|______
------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
-------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
-------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
--------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
--------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
---------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
---------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
----------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
----------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
-----------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
-----------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
-------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
-------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
--------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
--------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
---------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
---------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
----------------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
----------------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
-----------------------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
-----------------------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
------------------------------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-__________|______
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.---|--.-----.-----.--|
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.|-----.-----.-----|
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--.---|--.-----.-----.--|
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|______|-----.-----.-----|
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--.-----.-----.--|
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|_________________|

```

# Answer
> 0 votes
# JavaScript (ES6) HTML5 - 233 236 bytes

Probably not a valid answer, but I just couldn't resist posting, sorry :-P

```
F=n=>{d="______";b="\n|  .     .     .  |";a=b+"\n|     .     .     |";for(i=0;i<n;)document.body.innerHTML+="<pre style='background:#fff;position:fixed;top:"+i*28+"px;left:"+i*56+"px'> ____"+d+'|_'[+!i++]+d+a+a+b+"\n|"+d+d+"_____|"}

```

Test in Firefox with `F(1)`, `F(2)`, `F(3)`, etc.

**Example:** http://jsfiddle.net/Lvmg9fe8/7/

# Answer
> 0 votes
# Canvas, 54 bytes

```
Ｈ┐“)4╪xω╷┘IＱ+aｚQ┴¾４＊↔⌐∔v│↶++z2；ｅ＼１ｐ9H+m}`1Ｌ²‟19┤ｎ；８３╋╋

```

Try it here!

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---


title: Collapse Adjacent Duplicates

text:
# Question
Title: Collapse Adjacent Duplicates
# Challenge

Given a list of integers, return the list of these integers after repeatedly removing all pairs of adjacent equal items.

Note that if you have an odd-length run of equal numbers, one of them will remain, not being part of a pair.

### Example:

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

```

First, you should remove `0, 0`, `4, 4`, and `1, 1` to get:

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

```

Now, you should remove `2, 2`:

```
[0, 1, 0]

```

And this is the final result.

# Test Cases

```
[] -> []
[1] -> [1]
[1, 1] -> []
[1, 2] -> [1, 2]
[11, 11, 11] -> [11]
[1, 22, 1] -> [1, 22, 1]
[-31, 46, -31, 46] -> [-31, 46, -31, 46]
[1, 0, 0, 1] -> []
[5, 3, 10, 10, 5] -> [5, 3, 5]
[5, 3, 3, 3, 5] -> [5, 3, 5]
[0, -2, 4, 4, -2, 0] -> []
[0, 2, -14, -14, 2, 0, -1] -> [-1]
[0, 0, 0, 1, 2, 4, 4, 2, 1, 1, 0] -> [0, 1, 0]
[3, 5, 4, 4, 8, 26, 26, 8, 5] -> [3]
[-89, 89, -87, -8, 8, 88] -> [-89, 89, -87, -8, 8, 88]

```

# Scoring

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

# Answer
> 5 votes
# Jelly, 10 bytes

```
Œgœ^/€FµÐL

```

Try it online!

### How it works

```
Œgœ^/€FµÐL  Main link. Argument: A (array)

       µ    Combine all links to the left into a chain.
Œg              Group all adjacent equal items.
    /€          Reduce each group by...
  œ^                symmetric multiset difference.
                In each step, this maps ([], n) to [n] and ([n], n) to [], so the
                group is left with a single item if its length is odd, and no items
                at all if its length if even.
      F         Flatten the resulting array of singleton and empty arrays.
        ÐL  Apply the chain until the results are no longer unique. Return the last
            unique result.

```

# Answer
> 4 votes
# Mathematica 29 bytes

This repeatedly removes pairs of equal adjacent elements, `a_,a_` until there are none left.

```
#//.{b___,a_,a_,c___}:>{b,c}&

```

# Answer
> 4 votes
# Retina, ~~17~~ 15 bytes

```
+m`^(.+)¶\1$¶?

```

Try it online!

Saved 2 bytes thanks to Neil and Martin!

Replaces each pair of numbers with nothing. This process loops until no changes are made.

# Answer
> 3 votes
# Python 2, 57 bytes

```
r=[]
for x in input():r+=x,;r[-2:]*=r[-2:-1]!=[x]
print r

```

Try it online!

Iteratively constructs the output list by appending the next element, then chopping off the end if the appending element equals the one before it. Checking the second-to-last element `r[-2:-1]!=[x]` turns out awkward because it's possible the list has length only 1.

# Answer
> 2 votes
# Jelly, 15 bytes

```
Œr;ṪḂ$$€x/€FµÐL

```

Try it online!

# Explanation

```
Œr;ṪḂ$$€x/€FµÐL  Main Link
Œr               Run-length encode
  ;              Concatenate (?)
       €         For each element
   ṪḂ$$          Is the last element odd?
          €      For each element    // Non-breaking alternative
        x/       Reduce by repeating // for run-length decode
           F     Flatten
            µ    (New monadic link)
             ÐL  Repeat until results are no longer unique

```

-1 byte thanks to miles, and fixed :)

# Answer
> 2 votes
## JavaScript (ES6), ~~54~~ 53 bytes

*Saved 1 byte thanks to @ThePirateBay*

```
f=a=>1/a.find(q=>q==a[++i],i=-2)?f(a,a.splice(i,2)):a

```

Naive recursive solution, may be improvable.

# Answer
> 2 votes
# MATL, 7 bytes

```
t"Y'oY"

```

For some of the test cases where the result is empty the program exits with an error, but in any case it produces the correct (empty) output.

Try it online! Or verify the test cases with non-empty output.

### Explanation

```
t     % Implicit input. Duplicate
"     % For each (i.e. do as many times as input size)
  Y'  %   Run-length encode. Gives array of values and array of run lengths
  o   %   Parity, element-wise. Reduces run-lengths to either 0 or 1
  Y"  %   Run-length decode. Gives array of values appearing 0 or 1 times;
      %   that is, removes pairs of consecutive values
      % Implicit end. Implicit display

```

Consider input

```
0 0 0 1 2 4 4 2 1 1 0

```

Each iteration removes pairs of consecutive pairs. The first iteration reduces the array to

```
0 1 2 2 0

```

The two values `2` that are now adjacent were not adjacent in the initial array. That's why a second iteration is needed, which gives:

```
0 1 0

```

Further iterations will leave this unchanged. The number of required iterations is upper-bounded by the input size.

An empty intermediate result causes the run-length decoding function (`Y"`) to error in the current version of the language; but the ouput is empty as required.

# Answer
> 2 votes
# Python 2, 73 bytes

Since I do not have enough reputation to comment: I just changed @officialaimm 's answer to use r!=\[\] instead of len(r) to save a byte. Very clever solution to you, @officialaimm !

```
r=[]                            # create list that will hold final results. A new list is important because it needs to be removable.
for i in input():
 if r!=[]and r[-1]==i:r.pop()   # Ensure that we have at least 1 char added to the list (r!=[])... or that the last character of our final result isn't the current character being scanned. If that is, well, remove it from the final list because we do not want it anymore
 else:r+=[i]                    # Shorthand for r.append(i). This adds i to the final result
print r

```

Try it online!

It is, again, way too late... why am I even still up?

# Answer
> 2 votes
# Python, ~~60~~ 58 bytes

```
f=lambda a:a and(a[:1]+f(a[1:]))[2*(a[:1]==f(a[1:])[:1]):]

```

Try it online!

# Answer
> 2 votes
# x86 Machine Code (32-bit protected mode), 36 bytes

```
52
8B 12
8D 44 91 FC
8B F9
8D 71 04
3B F0
77 10
A7
75 F9
83 EF 04
4A
4A
A5
3B F8
75 FB
97
EB E7
58
89 10
C3

```

The above bytes of machine code define a function that takes an array as input, collapses adjacent duplicates in-place, and returns to the caller without returning a result. It follows the `__fastcall` calling convention, passing the two parameters in the `ECX` and `EDX` registers, respectively.

The first parameter (`ECX`) is a pointer to the first element in the array of 32-bit integers (if the array is empty, it can point anywhere in memory). The second parameter (`EDX`) is a pointer to a 32-bit integer that contains the length of the array.

The function will modify the elements of the array in-place, if necessary, and also update the length to indicate the new length of the collapsed array. This is a bit of an unusual method for taking input and returning output, but you really have no other choice in assembly language. As in C, arrays are actually represented in the language as a pointer to the first element and a length. The only thing a bit weird here is taking the length *by reference*, but if we didn't do that, there would be no way to shorten the array. The code would work fine, but the output would contain garbage, because the caller wouldn't know where to stop printing elements from the collapsed array.

**Ungolfed assembly mnemonics:**

```
; void __fastcall CollapseAdjacentDuplicates(int * ptrArray, int * ptrLength);
; ECX = ptrArray              ; ECX = fixed ptr to first element
; EDX = ptrLength
   push  edx                  ; save pointer to the length
   mov   edx, [edx]           ; EDX = actual length of the array
   lea   eax, [ecx+edx*4-4]   ; EAX = fixed ptr to last element

FindAdjacentPairs:
   mov   edi, ecx             ; EDI = ptr to element A
   lea   esi, [ecx+4]         ; ESI = ptr to element B
FindNext:
   cmp   esi, eax             ; is ptr to element B at end?
   ja    Finished             ; if we've reached the end, we're finished
   cmpsd                      ; compare DWORDs at ESI and EDI, set flags, and increment both by 4
   jne   FindNext             ; keep looping if this is not a pair

; Found an adjacent pair, so remove it from the array.
   sub   edi, 4               ; undo increment of EDI so it points at element A
   dec   edx                  ; decrease length of the array by 2
   dec   edx                  ;  (two 1-byte DECs are shorter than one 3-byte SUB)
RemoveAdjacentPair:
   movsd                      ; move DWORD at ESI to EDI, and increment both by 4
   cmp   edi, eax             ; have we reached the end?
   jne   RemoveAdjacentPair   ; keep going until we've reached the end
   xchg  eax, edi             ; set new end by updating fixed ptr to last element
   jmp   FindAdjacentPairs    ; restart search for adjacent pairs from beginning

Finished:
   pop   eax                  ; retrieve pointer to the length
   mov   [eax], edx           ; update length for caller
   ret

```

The implementation was inspired by my C++11 answer, but meticulously rewritten in assembly, optimizing for size. Assembly is a much better golfing language. :-)

*Note:* Because this code uses the string instructions, is *does* assume that the direction flag is clear (`DF` == 0). This is a reasonable assumption in most operating environments, as the ABI typically requires that DF is clear. If this cannot be guaranteed, then a 1-byte `CLD` instruction (`0xFC`) needs to be inserted at the top of the code.

It also, as noted, assumes 32-bit protected mode—specifically, a "flat" memory model, where the extra segment (`ES`) is the same as the data segment (`DS`).

# Answer
> 1 votes
# Japt, 34 bytes

```
ó¥ k_l vÃ®ò k_l É}Ãc
ó¥ l ¥Ul ?U:ß

```

Recursively removes pairs of equal numbers until none exist.

Try it online! with the `-Q` flag to format the output array.

Run all test cases using my WIP CodePen.

# Answer
> 1 votes
# Jelly, 12 bytes

```
ŒgṁLḂ$$€ẎµÐL

```

A monadic link taking and returning lists of numbers.

**Try it online!** or see a test suite

### How?

```
ŒgṁLḂ$$€ẎµÐL - Link: list
         µÐL - perform the chain to the left until no changes occur:
Œg           -   group runs (yield a list of lists of non-zero-length equal runs)
      $€     -   last two links as a monad for €ach run:
     $       -     last two links as a monad:
   L         -       length (of the run)
    Ḃ        -       modulo 2 (1 if odd, 0 if even)
  ṁ          -     mould (the run) like (1 or 0) (yields a list of length 1 or 0 lists)
        Ẏ    -   tighten (make the list of lists into a single list)

```

# Answer
> 1 votes
## Batch, 133 bytes

```
@set s=.
:l
@if "%1"=="%2" (shift/1)else set s=%s% %1
@shift/1
@if not "%1"=="" goto l
@if not "%s:~2%"=="%*" %0%s:~1%
@echo(%*

```

I set s to `.` because Batch gets confused if there are only duplicates. I also have to use `shift/1` so that I can use `%0%s:~1%` to set the argument list to the new array and loop.

# Answer
> 1 votes
# Python 2, ~~74 70~~ 66 bytes

* Thanks @SteamyRoot for 4 bytes: `r` instead of `len(r)` is enough to check emptiness of the list/stack.
* Thanks @ovs for 4 bytes: better if condition `[i]==r[-1:]`

# Python 2, 66 bytes

```
r=[]
for i in input():
 if[i]==r[-1:]:r.pop()
 else:r+=[i]
print r

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 15 bytes

```
[γʒgÉ}€нÐγ‚€gË#

```

Try it online!

### Explanation

```
[γʒgÉ}€нÐγ‚€gË#
[               # Start infinite loop
 γ              # Group Array into consecutive equal elements
  ʒgÉ}          # Keep the subarrays with an uneven amount of elements
      €н        # Keep only the first element of each subarray
        Ð       # Triplicate the result on the stack
         γ      # Group the top element into consecutive equal elements
          ‚     # Wrap the top two items of the stack in an array
           €g   # Get the length of each subarray
             Ë# # Break if they are equal
                # Implicit print

```

# Answer
> 1 votes
# 05AB1E, 13 bytes

```
[DγʒgÉ}€нDŠQ#

```

Try it online!

Explanation:

```
[DγʒgÉ}€нDŠQ# Implicit input
[             Start infinite loop
 D            Duplicate
  γ           Split into chunks of equal elements
   ʒ  }       Filter by
    g           Length
     É          Odd? (0=falsy 1=truthy)
       €      Foreach command
        н     Head
         D    Duplicate
          Š   Push c, a, b
           Q  Equal? (0=falsy 1=truthy)
            # Break if true (i.e. equal to 1)

```

# Answer
> 1 votes
# Haskell, 33 bytes

```
a!(b:c)|a==b=c
a!b=a:b
foldr(!)[]

```

Try it online!

# Answer
> 1 votes
# Husk, 9 bytes

```
ωoṁ?I↓2εg

```

Try it online!

A bit shorter than Zgarb's existing answer.

## Explanation

```
ωoṁ?I↓2εg
ωo        apply the following till a fixed point:
        g group adjacent values
   ?   ε  if the group is a singleton list
    I     leave as is
     ↓2   otherwise drop 2 elements
  ṁ       concatenate the results of that

```

# Answer
> 0 votes
## Husk, 10 bytes

```
ωoṁS↑o%2Lg

```

Try it online!

## Explanation

```
ωoṁS↑o%2Lg
ω           Repeat until fixed point
 o          the following two functions:
         g   a) group adjacent elements
  ṁ          b) map over groups and concatenate:
        L     length of group
     o%2      mod 2
   S↑         take that many elements of group

```

# Answer
> 0 votes
## Clojure, 100 bytes

```
#(loop[i % j[]](if(= i j)i(recur(mapcat(fn[p](repeat(mod(count p)2)(last p)))(partition-by + i))i)))

```

Not sure if this is the shortest possible.

# Answer
> 0 votes
## Bash, 82 bytes

```
cat>b
while cat b>a
perl -pe 's/(\d+) \1( |$)//g' a>b
! diff a b>c
do :
done
cat a

```

There's probably a way out of all those `cat`s, but I don't know it.

# Answer
> 0 votes
# PHP, 81 bytes

```
    function f(&$a){for($i=count($a);--$i;)$a[$i]-$a[$i-1]||array_splice($a,$i-1,2);}

```

function, call by reference or try it online.

fails for empty input; insert `$i&&` or `$a&&` before `--$i` to fix.

# Answer
> 0 votes
# , 10 bytes

```
òÍ¨.«©î±î*

```

Try it online!

Compressed Regex: `:%s/\(.\+\)\n\1\n*`. The optional newline is so that it works at the end of the file also. If I assume that there is a newline after the end it would be 8 bytes... but that seems like a stretch

# Answer
> 0 votes
# , ~~57~~ 54 bytes

```
l=rle(scan());while(any(x<-!l$l%%2))l=rle(l$v[!x]);l$v

```

Try it online!

uses a run-length encoding to remove pairs.

# Answer
> 0 votes
# dc, 84 78 bytes

```
[L.ly1-dsy0<A]sA[LtLtS.ly1+sy]sP[dStrdStr!=Pz1<O]sO[0syzdsz1<Oly0<Azlz>M]dsMxf

```

Try it online!

Unpacking it a bit, out of order in some attempt at clarity:

* `[0syzdsz1<Olydsx0<Alx1+lz>M]dsMxf` The main macro `M` resets counter `y` to 0, retrieves the number of items on the stack, stores this in register `z`, then runs macro `O` if there are at least two items on the stack. Once `O` finishes, it loads counter `y` and copies it into register `x` before checking to make sure `y` is nonzero (meaning stack `.` has data). If this is the case, it runs macro `A`. Finally it checks whether the original stack size is larger than the current stack size and reruns itself if so. Once it has finished, it prints the stack with `f`.
* `[dStrdStr!=Pz1<O]sO` Macro `O` temporarily stores the top two items on the stack into stack `t`. It then compares the top two items and runs macro `P` if they are not equal. Finally it checks whether or not there are at least two items on the stack, and runs itself if so.
* `[LtLtS.ly1+sy]sP` Macro `P` takes the two items from stack `t`, pushes the top one back onto the main stack, and pushes the following one onto stack `.`. It then increments counter `y`.
* `[L.ly1-dsy0<A]sA` Macro `A` takes stack `.` and turns it back into the primary stack. It does that, decrementing counter `y` until there's nothing left to push.

Edited for explanation, and to golf off 6 bytes as I was needlessly storing the size of the stack.

# Answer
> 0 votes
# C++11, 161 bytes

```
#include<vector>
#include<algorithm>
using V=std::vector<int>;void f(V&v){V::iterator i;while((i=std::adjacent_find(v.begin(),v.end()))!=v.end())v.erase(i,i+2);}

```

The above code defines a function, `f`, that takes a `std::vector<int>` by reference, modifies it in place to collapse adjacent duplicates according to the specification, and then returns.

**Try it online!**

Before I checked the byte count, I thought this was pretty svelte code. Over 150 bytes is, however, not so good! Either I'm not very good at golfing, or C++ is not a very good golfing language…

**Ungolfed:**

```
#include <vector>
#include <algorithm>

using V = std::vector<int>;

void f(V& v)
{
   V::iterator i;

   // Use std::adjacent_find to search the entire vector for adjacent duplicate elements.
   // If an adjacent pair is found, this returns an iterator to the first element of the
   // pair so that we can erase it. Otherwise, it returns v.end(), and we stop.
   while ((i=std::adjacent_find(v.begin(), v.end())) != v.end())
   {
        v.erase(i, i+2);   // erase this adjacent pair
   }
}

```

# Answer
> 0 votes
# PHP, 74 bytes

```
function c(&$a){foreach($a as$k=>$v)$a[$k+1]===$v&&array_splice($a,$k,2);}

```

Function c calls by reference to reduce array. Try it online.

Interestingly this works in Php5.6 but not 7.

# Answer
> 0 votes
# , 38 bytes

```
;@(<@($~2|#)/.~0+/\@,}.~:}:)^:(0<#)^:_

```

Try it online!

# Answer
> 0 votes
# GNU sed, 19 + 1 = 20 bytes

+1 byte for `-r` flag.

```
:
s/\b(\S+ )\1//g
t

```

Try it online!

# Answer
> 0 votes
# Pyth, 10 bytes

Bit late to the party.

```
ueMf%hT2r8

```

Test Suite.

# Answer
> 0 votes
# Japt `-h`, 11 bytes

```
£=òÎ®ò l1Ãc

```

Try it or run all test cases

```
£=òÎ®ò l1Ãc     :Implicit input of array U
£               :Map
 =              :  Reassign to U
  ò             :  Partition between elements where
   Î            :    The sign of their difference is truthy (not zero)
    ®           :  Map
     ò          :    Partitions of length 2
       l1       :    Filter elements of length 1
         Ã      :  End map
          c     :  Flatten
                :Implicit output of last element

```

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


title: Pascal's Rhombus

text:
# Question
Title: Pascal's Rhombus
Pascal's Rhombus (which is actually a triangle) is obtained by adding in the pattern:

```
  *
 ***
  x

```

instead of

```
* *
 x

```

This means that each cell is the sum of the three cells on the row directly above it and one cell on the row 2 above it. Just like Pascal's triangle the zeroth row has a single `1` on it that generates the triangle.

Here are the first couple of rows of Pascal's Rhombus

```
      1
    1 1 1
  1 2 4 2 1
1 3 8 9 8 3 1

```

## Task

Given a row number (starting from the top) and an column number (starting from the first non-zero item on that row) output the value at that particular cell. Both inputs may be either 1 or 0 indexed (you may mix and match if you desire).

This is so you should aim to make the file size of your source code as a small as possible.

OEIS A059317

# Answer
# Haskell, ~~59~~ 55 bytes

***Pascal's Rhombus? More like Haskell's Rhombus! amiright?***

*4 bytes saved thanks to Ørjan Johansen*

I thought I'd have a go at my own problem and practice my Haskell. Hopefully this will inspire more people to answer this.

```
1!1=1
n!k=sum[(n-2)!(k-2)+sum(map((n-1)!)[k-2..k])|n>1]

```

Try it online!

## Explanation

*This is a bit out of date with the latest golf*

Instead of calculating

```
  *
 ***
  x

```

We calculate

```
*
***
  x

```

This slants our entire triangle to become

```
1
1 1 1
1 2 4 2 1
1 3 8 9 8 3 1

```

This lines up all of our rows making it easier to index the nth item of any column. We then define our base cases.

The zeroth row is all zeros so

```
0!_=0

```

There is a single `1` at position `1,1` so we define that

```
1!1=1

```

And we define the rest of the first row to be zeros as well

```
1!_=0

```

Then we define the general case recursively using the pattern described above:

```
n!k=(n-2)!(k-2)+(sum$map((n-1)!)[k-2..k])

```
> 13 votes

# Answer
# Pascal, 122 bytes

*Well, it's **Pascal's** rhombus.*

<sub>*37 bytes saved thanks to @manatwork*</sub>

```
function f(n,k:integer):integer;begin f:=1-Ord((k<0)or(k>n*2));if n>0then f:=f(n-1,k-2)+f(n-1,k-1)+f(n-1,k)+f(n-2,k-2)end;

```

Try it online!
> 12 votes

# Answer
# PHP, 86 bytes

recursive way only the function row and column 0-Indexed

```
function f($r,$c){return$r|$c?$r<0?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

```

Try it online!

# PHP, 114 bytes

recursive way full program row and column 0-Indexed

```
<?=f(...$_GET);function f($r,$c){return$r|$c?$r<0|$c<0|$c>2*$r?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

```

Try it online!

# PHP, 129 bytes

row and column 0-Indexed

```
for(;$r<=$argv[1];$l=$t[+$r++])for($c=~0;$c++<$r*2;)$t[+$r][$c]=$r|$c?$t[$r-2][$c-2]+$l[$c]+$l[$c-1]+$l[$c-2]:1;echo$l[$argv[2]];

```

Try it online!
> 7 votes

# Answer
# Jelly, ~~22~~ ~~20~~ 19 bytes

```
3ḶṚp@Ḣḣ4
Ḟ_Ð€Çß€ȯ¬S

```

Takes a 0-based index pair as command-line argument.

Try it online!
> 4 votes

# Answer
# Pari/GP, 60 bytes

```
i->j->polcoeff(Vec(1/(1-x*(1+y+y^2+x*y^2))+O(x^i++))[i],j,y)

```

Try it online!
> 3 votes

# Answer
# MATL, ~~22~~ ~~20~~ 19 bytes

```
Ti:"2Y6Y+FT_Y)]!i_)

```

Both inputs are 0-based.

Try it online!

### Explanation

Let `r` and `c` denote the two inputs, specifying 0-based row and column respectively.

Each new row in Pascal's rhombus can be built from the matrix containing the previous two rows by *convolving* with the kernel `[1 1 1; 0 1 0]` and keeping the last two rows of the result swapped. This is done `r` times, starting from matrix `1`.

It turns out to be shorter to use the kernel `[0 1 0; 1 1 1; 0 1 0]`, which is a predefined literal. This produces an extra row, which will be discarded.

Consider for example `r = 3`, so there are `3` iterations.

1. Starting from

```
1

```

convolution with `[0 1 0; 1 1 1; 0 1 0]` gives

```
0 1 0
1 1 1
0 1 0

```

Keeping the last two rows (the whole matrix, in this case) and swapping them gives

```
0 1 0
1 1 1

```
2. Convolution of the above with `[0 1 0; 1 1 1; 0 1 0]` gives

```
0 0 1 0 0
0 1 1 1 0
1 2 4 2 1
0 1 1 1 0

```

The matrix formed by the last two rows swapped is

```
0 1 1 1 0
1 2 4 2 1

```

This contains the new row at the bottom, and the preceding one extended with zeros.
3. Convolving again yields

```
0 0 1 1 1 0 0
0 1 2 3 2 1 0
1 3 8 9 8 3 1
0 1 2 4 2 1 0

```

Taking the last two rows swapped gives

```
0 1 2 4 2 1 0
1 3 8 9 8 3 1

```

After the `r` iterations have been done, the output is contained in the last row of the final matrix. For example, for `c = 2` (0-based) the result would be `8`. Instead of indexing the last row and the desired column, a trick can be used which exploits the *symmetry* of each row: the final matrix is transposed

```
0 1
1 3
2 8
4 9
2 8
1 3
0 1

```

and its `-c`-th element is taken. This uses linear indexing, that is, the matrix is indexed by a *single index* in column-major order. Since indexing is *modular*, the `0`-entry is the lower-right corner (value `1`) and the `-2`-th entry is two steps above (value `8`).

```
T       % Push true
i       % Input row number
:"      % Do the following that many times
  2Y6   %   Push predefined literal [0 1 0; 1 1 1; 0 1 0]
  Y+    %   2D convolution, increasing size
  FT_   %   Push [0 -1]
  Y)    %   Matrix with rows 0 (last) and -1 (second-last), in that order
]       % End
!       % Transpose
i       % Input: colun number
_       % Negate
)       % Entry with that index. Implicitly display

```
> 3 votes

# Answer
## Haskell, 74 bytes

```
0#0=1
n#m|m<=2*n&&m>=0=sum[(n-a)#(m-b)|(a,b)<-zip[2,1,1,1]$2:[0..2]]
n#m=0

```

Try it online!

Call with `n # m`, where `n` is the row and `m` is the column.
> 2 votes

# Answer
# Python 2, ~~70~~ ~~66~~ 65 bytes

```
f=lambda n,k:(k==0)|sum(f(n+~j/3,k-j+j/3)for j in range(4)[:3*n])

```

Try it online!
> 2 votes

# Answer
# Mathematica, 56 bytes

```
If[#<1,Boole[##==0],Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}]]&

```

Pure function taking two integer arguments (row first, column second) and returning an integer. Works for negative integer arguments as well, returning `0`. A pretty straightforward recursive structure: `If[#<1,Boole[##==0],...]` defines the base-case behavior for the 0th row (and above), while `Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}]` implements the recursive definition.
> 2 votes

# Answer
## JavaScript (ES6), 68 bytes

```
f=(y,x)=>x<0|x>y+y?0:x>0&x<y+y?f(--y,x)+f(y,--x)+f(y,--x)+f(--y,x):1

```
> 1 votes

# Answer
# Mathematica, 53 bytes

```
D[1/(1-x(1+y+y^2(1+x))),{x,#},{y,#2}]/#!/#2!/.x|y->0&

```

Using the generating function.
> 1 votes

# Answer
# Python 3, 75 Bytes

This is a recursive lambda that takes column and row as 0-indexed integers.

```
p=lambda r,c:(r<0 or((c==0)|p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

```

Here's a (slightly) more readable version with a printing function:

```
p = lambda r,c:(r<0 or ((c==0) | p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

def pp(r):
    ml = len(str(p(r,r)))+1
    for i in range(0, r):
            a=" "*ml*(r-i)
            for j in range(0,i*2 + 1):
                    a+=str(p(i,j))+(" "*(ml-len(str(p(i,j)))))
            print(a)

```
> 1 votes

# Answer
# Python 3, ~~82~~ 84 bytes

This is a recursive implementation with 1-indexed rows and columns. (Technically needs an `f=` in front, someone let me know if I should change it to 84 bytes. Still new and not 100% sure of the rules.)

This uses the recursive formula found on the OEIS page, but with the `k`'s shifted one to the left to line up properly. Coincidently, `sum(f(n-1,k-i)for i in(0,1,2))` is the same size as `f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)`. The whole function is the Python `and or` trick, where the first condition checks if k is inside the triangle *and* not on the boundary, in which case the recursive formula is used. If is isn't, the part after the `or` is returned, which checks if `k` is in `(1, 2*n-1)`, i.e. on the boundary, returning `True` and `False`. `k+1in(2,2*n)` is one byte shorter than `k in(1,2*n-1)`. Wrapping that in parentheses and putting a `+` in front converts to integer, which is what is needed.

```
f=lambda n,k:2*n-1>k>1and sum(f(n-1,k-i)for i in(0,1,2))+f(n-2,k-2)or+(k+1in(2,2*n))

```

Try it online!
> 0 votes

# Answer
# Java (OpenJDK 8), 87 bytes

```
int f(int r,int c){return c<0|2*r<c?0:0<c&c<2*r?f(--r,c)+f(r,--c)+f(r,--c)+f(--r,c):1;}

```

Try it online!

At first, I was happy with my 160 bytes iterative method... Hmmm... let's just forget about it, OK?
> 0 votes

# Answer
# Husk, 38 bytes

```
!!¡(S+o↔↑2Fz+§,ȯΘΘ←(moΣ↑_3ḣ→)↑_2)eḋ1ḋ7

```

Try it online!

Displays the infinite list, but somehow indexing into the list makes it time out.
> 0 votes

---
Tags: code-golf, math, number, arithmetic, integer
---


title: Lets make a triangle

text:
# Question
Title: Lets make a triangle
Most people are familiar with Pascal's triangle.

```
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

```

Pascal's triangle is an automaton where the value of a cell is the sum of the cells to the upper left and upper right. Now we are going to define a similar triangle. Instead of just taking the cells to the upper left and the upper right we are going to take all the cells along two infinite lines extending to the upper left and upper right. Just like Pascal's triangle we start with a single `1` padded infinitely by zeros and build downwards from there.

For example to calculate the cell denoted with an `x`

```
   1
  1 1
 2 2 2
4 5 5 4
   x

```

We would sum the following cells

```
   .
  . .
 2 . 2
. 5 5 .
   x

```

Making our new cell `14`.

# Task

Given a row number (**n**), and distance from the left (**r**) calculate and output the **r**th non-zero entry from the left on the **n**th row. (the equivalent on Pascal's triangle is **nCr**). You may assume that **r** is less than **n**.

This is , the goal is to minimize the number of bytes in your solution.

# Test cases

```
0,0 -> 1
1,0 -> 1
2,0 -> 2
4,2 -> 14
6,3 -> 106

```

Here's the first couple rows in triangle form:

```
                  1
                1   1
              2   2   2
            4   5   5   4
          8  12  14  12   8
       16  28  37  37  28  16
     32  64  94  106 94  64  32
   64  144 232 289 289 232 144 64
 128 320 560 760 838 760 560 320 128

```

# Answer
> 10 votes
# Jelly, ~~18~~ 17 bytes

```
SṚ0;+Sṭ
1WWÇ⁸¡ṪṙḢ

```

Uses 0-based indexing.

Try it online!

### How it works

```
1WWÇ⁸¡ṪṙḢ  Main link. Arguments: n, r

1          Set the return value to 1.
 W         Wrap; yield [1].
  W        Wrap; yield [[1]].
           This is the triangle with one row.
   Ç⁸¡     Call the helper link n times.
           Each iteration adds one row to the triangle.
      Ṫ    Tail; take the last array, i.e., the row n of the triangle.
       ṙ   Rotate row n r units to the left.
        Ḣ  Head; take the first element, i.e., entry r of row n.

SṚ0;+Sṭ    Helper link. Argument: T (triangle)

S          Take the column-wise sums, i.e., sum the ascending diagonals of the
           centered triangle, left to right.
 Ṛ         Reverse the array of sums. The result is equal to the sums of the
           descending diagonals of the centered triangle, also left to right.
  0;       Prepend a 0. This is required because the first element of the next row
           doesn't have a descending diagonal.
     S     Take the column-wise sum of T.
    +      Add the ascending to the descending diagonals.

```

# Answer
> 5 votes
# Python 3, 72 bytes

1 byte thanks to Kritixi Lithos.

```
f=lambda n,r:n>=r>=0and(0**n or sum(f(i,r)+f(i,r+i-n)for i in range(n)))

```

Try it online!

# Answer
> 3 votes
# ES6, 80 78 bytes

```
p=(n,r,c=0)=>n?(o=>{while(n&&r<n)c+=p(--n,r);while(o*r)c+=p(--o,--r)})(n)||c:1

```

In action!

Two bytes thanks to Arnauld.

# Answer
> 2 votes
# PHP, 94 bytes

recursive way 0-indexed

```
function f($r,$c){for($s=$r|$c?$r<0?0:!$t=1:1;$t&&$r;)$s+=f($r-=1,$c)+f($r,$c-++$i);return$s;}

```

Try it online!

# PHP, 125 bytes

0-indexed

```
for(;$r<=$argv[1];$r++)for($z++,$c=~0;++$c<$z;$v+=$l)$x[$c]+=$t[+$r][$c]=$l=($v=&$y[$r-$c])+$x[$c]?:1;echo$t[$r-1][$argv[2]];

```

Try it online!

## PHP\>=7.1, 159 bytes

0-indexed for rows over 50

```
for([,$m,$n]=$argv;$r<=$m;$r++)for($z++,$c=0;$c<$z;$v=bcadd($v,$l),$x[$c]=bcadd($x[$c],$l),$c++)$t[+$r][$c]=$l=bcadd(($v=&$y[$r-$c]),$x[$c])?:1;echo$t[$m][$n];

```

# Answer
> 1 votes
# Python 3, 61 bytes

```
f=lambda n,r:sum(f(k,r)+f(k,r+k-n)for k in range(n))or~n<-r<1

```

This returns *True* for base case **(0, 0)**, which is allowed by default.

Try it online!

# Answer
> 1 votes
# Husk, 16 bytes

```
!!¡ȯSż+oΘ↔mΣT;;1

```

Try it online!

Same idea as Dennis' answer, but simpler indexing method.

# Answer
> 0 votes
# Pascal, 145 bytes

```
function f(n,k:integer):integer;var i,r:integer;begin r:=1-Ord((k<0)or(k>n));if n>0 then r:=0;for i:=1 to n do r:=r+f(n-i,k-i)+f(n-i,k);f:=r;end;

```

Try it online!

Uses the `T(n, r) = T(n-1, r-1) + T(n-1, r)` recursion.

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