# Generate the Temple Skyline Sequence

Consider the following process:

1. Take some non-negative integer N.

e.g. N = 571

2. Express it in binary with no leading zeroes. (Zero itself is the only exception, becoming 0.)

e.g. 571 = 1000111011 in binary

3. Break apart consecutive runs of ones and zeroes in this binary representation.

e.g. 10001110111, 000, 111, 0, 11

4. Sort the runs from longest to shortest.

e.g. 1, 000, 111, 0, 11000, 111, 11, 1, 0

5. Overwrite all the digits in each run with alternating 1's and 0's, always starting with 1's.

e.g. 000, 111, 11, 1, 0111, 000, 11, 0, 1

6. Concatenate the result to get a new binary number.

e.g. 111, 000, 11, 0, 11110001101 = 909 in decimal

When you plot the values produced by this process you get a pretty neat graph:

And it's hopefully apparent why I'm calling the resulting sequence the Temple Skyline sequence:

# Challenge

Write a program or function that takes in a non-negative integer N and prints or returns the corresponding Temple Skyline sequence number. Your input and output should both be in decimal.

e.g. If the input is 571 the output should be 909.

The shortest code in bytes wins.

For reference, here are the terms in the sequence from N = 0 to 20:

0   1
1   1
2   2
3   3
4   6
5   5
6   6
7   7
8   14
9   13
10  10
11  13
12  12
13  13
14  14
15  15
16  30
17  29
18  26
19  25
20  26


Here are the terms from 0 to 1023.

# CJam, 2523 22 bytes

ri1e>2bez($W%a\+ze~2b  Just a bit of run-length encoding. -1 thanks to @MartinBüttner. ### Explanation ri Read n from input as int 1e> Take max with 1 (special case for n = 0) 2b Convert n to binary e Run length encode z Zip, giving a pair [<counts> <10101.. array>] ($W%      Drop the counts array and sort decending
a\+z      Add it back to the 10101.. array and re-zip
e~        Run length decode
2b        Convert from binary


# Pyth - 21 20 bytes

Thanks to @sok for saving me one byte!

is.em%hk2hb_Sr.BQ8 2

• You can use .BQ instead of jQ2, which means you can lose the space between the 8 and the preceding 2.
– Sok
Oct 6 '15 at 9:01
• is*Rs=!Z_ShMr.BQ8 2 is an interesting same-length solution. Mostly posting because I didn't really expect the assign in a map argument to work. Oct 6 '15 at 15:17
• @FryAmTheEggman Replace s with ]. Saves one byte. Oct 11 '15 at 15:38

# Python 2, 121 bytes 125

121: Thanks to Sp3000 for shaving off 4 bytes!

import re;print int("".join(n*~i%2for i,n in enumerate(sorted(map(len,re.split('(1*|0+)',bin(input())[2:])))[::-1])),2)


125

import re;print int("".join("10"[i%2]*n for i,n in enumerate(sorted(map(len,re.split('(1*|0+)',bin(input())[2:])))[::-1])),2)

• Nice! I believe you can also do n*~i%2for instead of "10"[i%2]*n for Oct 6 '15 at 4:22
• Thanks for editing! I had to rush off quickly but wanted to submit because I thought this was a beautiful challenge and a good one for a first submission. I will check out your submission shortly! Oct 6 '15 at 5:38
• I think that you can save some bytes by using sorted(...,key=len) instead of using map(len,... but I don't fully comprehend your program right now so I'm not positive that would benefit you.
– cole
Oct 7 '15 at 6:11
• Hey @Cole I am mapping len because that is the only information I need to replicate the amount of 1 and 0. I tried your suggestion and it adds 2 bytes, as I will have to use len twice then, but thanks for the suggestion! Oct 7 '15 at 6:24

# JavaScript ES6, 110 bytes 113116119120

Saved 3 bytes thanks to @intrepidcoder

Saved 3 bytes thanks to @NinjaBearMonkey

n=>+('0b'+n.toString(2).split(/(0+)/).sort((b,a)=>a.length-b.length).map((l,i)=>l.replace(/./g,i-1&1)).join)


Straight forward approach. Don't like the length of the sort function but I can't think of a way to golf it.

• I think you can use a + instead of eval. Oct 6 '15 at 2:09
• @intrepidcoder thanks, that saved 3 bytes! Oct 6 '15 at 2:43
• I can't test this, but split(/(0+)/g) should be able to replace match(/(.)\1*/g). Oct 6 '15 at 3:14
• @NinjaBearMonkey thanks, that saved 3 bytes! Oct 6 '15 at 3:19
• Saving one byte: +(s=0, ... .map(l=>l.replace(/./g,s^=1))...) Oct 6 '15 at 7:25

# C++, 535 527 Bytes

(thanks zereges for shaving off some bytes.)

Now that we got rid of those bytes the program is now competetive ;)

#include<iostream>
#include<cmath>
int main(){int I,D;std::cin>>I;while(I>int(pow(2,D))){D++;}int L[99];int X=0;int Z=0;int O=0;for(int i=D-1;i>=0;i--){if( int(pow(2,i))&I){if(Z>0){L[X]=Z;Z=0; X++;}O++;}else{if(O>0){L[X] = O;O=0;X++;}Z++;}}if(Z>0){L[X]=Z;Z=0;X++;}if(O>0){L[X]=O;O=0;X++;}int P=0;bool B = true;int W = D-1;for(int j=0;j<X;j++){int K=0;int mX=0;for(int i=0;i<X;i++){if(L[i]>K){K=L[i];mX=i;}}L[mX]=0;if(B){for(int k=0;k<K;k++){P+=int(pow(2,W));W--;}}else{for(int k=0;k<K;k++){W--;}}B^=1;}std::cout<<P;return 0;}


I'm new to golfing, so please give me some tips in the comments.

Things like "you don't need those brackets" or "use printf" are all helpful, but I also appreciate advice on the logic. Thanks in advance!

For ease of reading, I present the ungolfed version:

#include<iostream>
#include<cmath>
int main()
{
int input,digits;

std::cin>>input;
while(input > int(pow(2,digits))){digits++;}

int list[99];
int index=0;
int zCounter=0;
int oCounter=0;

for(int i=digits;i>0;i--)
{
if( int(pow(2,i-1))&input)
{
if(zCounter>0)
{
list[index] = zCounter;
zCounter=0;
index++;
}
oCounter++;
}
else
{
if(oCounter>0)
{
list[index] = oCounter;
oCounter=0;
index++;
}
zCounter++;
}
}
if(zCounter>0)
{
list[index] = zCounter;
zCounter=0;
index++;
}
if(oCounter>0)
{
list[index] = oCounter;
oCounter=0;
index++;
}

int output = 0;
bool ones = true;
int power = digits-1;
for(int j=0;j<index;j++)
{
int max=0;
int mIndex=0;
for(int i=0;i<index;i++)
{
if(list[i]>max){max=list[i];mIndex=i;}
}
list[mIndex]=0;

if(ones)
{
for(int k=0;k<max;k++)
{
output+=int(pow(2,power));
power--;
}
}
else
{
for(int k=0;k<max;k++)
{
power--;
}
}
ones^=1;

}
std::cout<<output;
return 0;
}


EDIT golfed version brought down a couple bytes, ungolfed version unchanged

• You can instead of int a; int b; use int a,b;. Also variables in in global scope are initialized with 0. Also you don't have to use curly brackets when there is only one command to be executed. Also ones=!ones; can be simplified as ones ^= 1; Oct 6 '15 at 19:51
• Saved some bytes thanks
– Liam
Oct 6 '15 at 20:13
• Shift your first for loop by 1, i.e. for(int i=D;i;i--) and use pow(2,i-1) inside the loop.
– nimi
Oct 6 '15 at 20:36
• @LiamNoronha You actually did not save what I recommended :) Oct 6 '15 at 20:53
• @LiamNoronha Check this out. There is still a lot of space for improvement. E.g. reusing variables (saves definition), ones can also be int. Maybe macroing int(pow(i)) into P(i). I would recommend you reading the discussion here Oct 6 '15 at 21:05

# Pyth, 20 19 bytes

ACr.BQ8|is*V_SGH2 1


1 byte saved by Jakube

Test Suite

Uses the fact that after run-length-encoding, the runs are the desired runs in the output.

Lost 3 bytes special casing 0.

# Perl 5.10, 121 101

say oct"0b".join'',map{$|=1-$|;$_=~s/./$|/gr}sort{length$b<=>length$a}(sprintf"%b",shift)=~/(0*|1*)/g


I think the sort part can be shorter.

Edit: -20 bytes, thanks to symbabque!

• You can get rid of the \n, and the m is not required for regular expression matching. In your substitution, just use . instead of the char group. Oct 7 '15 at 16:17
• No need for the grep part either. The oct is neat though :) Oct 7 '15 at 16:22
• Thank you, I accidentally left those parts from the original code. Oct 8 '15 at 9:02

import Data.List
g 0=[]
g n=mod n 2:g(div n 2)
q=[1]:[0]:q
f=foldl((+).(2*))0.concat.zipWith(<*)q.sortOn((-)0.length).group.g.max 1


Usage example:

> map f [0..20]
[1,1,2,3,6,5,6,7,14,13,10,13,12,13,14,15,30,29,26,25,26]


How it works:

                 max 1         -- fix n=0: f(0) is the same as f(1)
g               -- turn into binary, i.e. list of 0s and 1s
group              -- group sequences of equal elements
sortOn((-)0.length)   -- sort groups on negative length
zipWith(<*)q             -- map each element in a group to constant 1 or 0 by turns
concat                      -- flatten all groups into a single list
foldl((+).(2*))0               -- convert back to decimal


# J - 30 bytes

Function taking integer on right. Correctly handles 0.

(\:~#2|#\)@(#;.1~1,2~:/\])&.#:

• #: - Take the binary representation.
• 1,2~:/\] - Between each digit, report True if they are different. Prepend a True so that the list has True at the start of each "run".
• (#;.1~...) - Using the boolean vector above, take the length of each run.
• \:~ - Sort these lengths from longest to shortest.
• 2|#\ - Take a list of alternating 1 0 1 0 ... as long as the list of lengths.
• (...#...) - For each number on the left (sorted lengths), take as many of the corresponding item on the right (alternating 1's and 0's)
• &. - Convert this new binary representation back to a number.

Examples:

   (\:~#2|#\)@(#;.1~1,2~:/\])&.#: 571
909
i.21   NB. zero to twenty
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(\:~#2|#\)@(#;.1~1,2~:/\])&.#: every i.21   NB. apply separately to every number
1 1 2 3 6 5 6 7 14 13 10 13 12 13 14 15 30 29 26 25 26


# Python 3, 146 136 bytes

import re;print(int(''.join(len(j)*'01'[i%2<1]for i,j in enumerate(sorted(re.findall('1+|0+',bin(int(input()))[2:]),key=len)[::-1])),2))

• Rather than map with a lambda, would it be better to do ''.join(... for ... in ...)? Oct 6 '15 at 2:21

# Mathematica, 83 bytes

Flatten[0#+(d=1-d)&/@SortBy[d=0;Split[#~IntegerDigits~2],-Length@#&]]~FromDigits~2&


This defines an unnamed function.

# Ruby, 107104 102 bytes

(saved 3 bytes thanks to nimi)

Not going to beat the likes of CJam, but I got it pretty small for a sane language.

p gets.to_i.to_s(2).scan(/((.)\2*)/).map{|e|e[i=0].size}.sort.reverse.map{|e|"#{i=1-i}"*e}.join.to_i 2

• A few bytes to save: (i+=1)%2 is i=1-i.
– nimi
Oct 6 '15 at 22:32
• @nimi Ah, thank you. I was trying to figure out how to shorten that. Oct 6 '15 at 22:38

## Java 8, 179 176 bytes

(x)->{int g[]=new int[32],h=0,i=highestOneBit(x);g[0]=1;while(i>1)g[((x&i)>0)^((x&(i>>=1))>0)?++h:h]++;sort(g);for(i=32,h=0;g[--i]>0;)while(g[i]-->0)h=h<<1|i%2;return x<1?1:h;}


I used two static imports: java.util.Integer.highestOneBit and java.util.Arrays.sort.

For readability, here's the code ungolfed:

java.util.function.ToIntFunction<Integer> f = (x) -> {
int g[] = new int[32], h = 0, i = java.util.Integer.highestOneBit(x);
g[0] = 1;
while (i > 1) {
g[((x & i) > 0) ^ ((x & (i >>= 1)) > 0) ? ++h : h]++;
}
java.util.Arrays.sort(g);
for (i = 32, h = 0; g[--i] > 0;) {
while (g[i]-- > 0) {
h = h << 1 | i % 2;
}
}
return x < 1 ? 1 : h; // handle zero
};


# Husk, 11 bytes

ḋṘİ¬↔OmLgḋ


Try it online!

# Jelly, 13 bytes

BŒgLÞṚJḂṁ"ƊFḄ


Try it online!

## How it works

BŒgLÞṚJḂṁ"ƊFḄ - Main link. Takes n on the left
B             - Convert to binary
Œg           - Group adjacent equal elements; Call this l
Þ         - Sort by...
L          -   length
Ṛ        - Reverse, to put the longest first
Ɗ   - Run the previous 3 commands over the sortedt list
J       - Yield [1, 2, ..., len(l)]
Ḃ      - Bit;  [1, 0, 1, 0, ..., len(l)%2]
"    - Zip with l and do the following over each pair
ṁ     -   Mould 1 or 0 to each element of l
F  - Flatten
Ḅ - Convert from binary


# Japt, 14 bytes

¤ò¦ ñÊÔËîEvÃ¬Í


Try it

¤ò¦ ñÊÔËîEvÃ¬Í     :Implicit input of integer
¤                  :To binary string
ò                 :Partition on
¦                :Inequality
ñ              :Sort by
Ê             :Length
Ô            :Reverse
Ë           :Map each D at 0-based index E
î          :  Fill D with
Ev        :  Parity of E
Ã       :End map
¬      :Join
Í     :To decimal


# APL (Dyalog Extended), 32 30 bytes

⊥{⍵/(≢⍵)⍴⊤2}⊃¨∨{⍴¨⍵⊂⍨1,2≠/⍵}⊤⎕


Try it online!

-2 bytes for full program.

## Explanation

⊥{⍵/(≢⍵)⍴⊤2}⊃¨∨{⍴¨⍵⊂⍨1,2≠/⍵}⊤⎕
⊤⎕ convert input to binary
2≠/⍵    inequality of overlapping pairs
1,        prepend 1
⍵⊂⍨          partition bits on that
⍴¨             get length of each part
∨                sort in descending order
⊃¨                 unenclose each
⊤2                   array [1,0]
(≢⍵)⍴                      reshape to ⍵'s length
⍵/                           filter ⍵ by that(every other element)
⊥                              convert that back to binary
`