Generate the Temple Skyline Sequence

Question

Consider the following process:

Take some non-negative integer N.

e.g. N = 571
Express it in binary with no leading zeroes. (Zero itself is the only exception, becoming 0.)

e.g. 571 = 1000111011 in binary
Break apart consecutive runs of ones and zeroes in this binary representation.

e.g. 1000111011 → 1, 000, 111, 0, 11
Sort the runs from longest to shortest.

e.g. 1, 000, 111, 0, 11 → 000, 111, 11, 1, 0
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, 0 → 111, 000, 11, 0, 1
Concatenate the result to get a new binary number.

e.g. 111, 000, 11, 0, 1 → 1110001101 = 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:

Here are the terms from 0 to 1023.

Sp3000 · Accepted Answer · 2015-10-06 06:41:32Z

14

CJam, 25 23 22 bytes

ri1e>2be`z($W%a\+ze~2b

Just a bit of run-length encoding. -1 thanks to @MartinBüttner.

Try it online / Test suite.

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

edited Oct 6, 2015 at 6:41

answered Oct 6, 2015 at 0:49

Sp3000

61.9k13 gold badges115 silver badges287 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

11

Pyth - 21 20 bytes

Thanks to @sok for saving me one byte!

is.em%hk2hb_Sr.BQ8 2

Try it here online.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 6, 2015 at 0:25

Maltysen

25.8k4 gold badges55 silver badges127 bronze badges

\$\begingroup\$ You can use .BQ instead of jQ2, which means you can lose the space between the 8 and the preceding 2. \$\endgroup\$
– Sok
Commented Oct 6, 2015 at 9:01
\$\begingroup\$ is*R`s=!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. \$\endgroup\$
– FryAmTheEggman
Commented Oct 6, 2015 at 15:17
1

\$\begingroup\$ @FryAmTheEggman Replace `s with ]. Saves one byte. \$\endgroup\$
– Jakube
Commented Oct 11, 2015 at 15:38

Add a comment |

user2033511 · Accepted Answer · 2015-10-06 05:53:05Z

6

Python 2, 121 bytes 125

121: Thanks to Sp3000 for shaving off 4 bytes!

import re;print int("".join(n*`~i%2`for 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)

edited Oct 6, 2015 at 5:53

answered Oct 6, 2015 at 4:18

user2033511

1615 bronze badges

1

\$\begingroup\$ Nice! I believe you can also do n*`~i%2`for instead of "10"[i%2]*n for \$\endgroup\$
– Sp3000
Commented Oct 6, 2015 at 4:22
\$\begingroup\$ 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! \$\endgroup\$
– user2033511
Commented Oct 6, 2015 at 5:38
\$\begingroup\$ 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. \$\endgroup\$
– cole
Commented Oct 7, 2015 at 6:11
\$\begingroup\$ 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! \$\endgroup\$
– user2033511
Commented Oct 7, 2015 at 6:24

Add a comment |

Downgoat · Accepted Answer · 2015-10-06 03:18:36Z

5

JavaScript ES6, 110 bytes 113 116 119 120

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.

edited Oct 6, 2015 at 3:18

answered Oct 6, 2015 at 0:56

Downgoat

29.1k6 gold badges84 silver badges155 bronze badges

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

| Show 2 more comments

Liam · Accepted Answer · 2015-10-06 20:55:48Z

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; — Zereges, Commented Oct 6, 2015 at 19:51
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, Commented Oct 6, 2015 at 20:36
@LiamNoronha You actually did not save what I recommended :) — Zereges, Commented Oct 6, 2015 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 — Zereges, Commented Oct 6, 2015 at 21:05

isaacg · Accepted Answer · 2015-10-11 18:00:24Z

4

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.

edited Oct 11, 2015 at 18:00

answered Oct 7, 2015 at 3:16

isaacg

42.1k5 gold badges73 silver badges213 bronze badges

Add a comment |

Laposhasú Acsa · Accepted Answer · 2015-10-08 09:00:00Z

3

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!

edited Oct 8, 2015 at 9:00

answered Oct 6, 2015 at 16:51

Laposhasú Acsa

1714 bronze badges

\$\begingroup\$ 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. \$\endgroup\$
– simbabque
Commented Oct 7, 2015 at 16:17
\$\begingroup\$ No need for the grep part either. The oct is neat though :) \$\endgroup\$
– simbabque
Commented Oct 7, 2015 at 16:22
\$\begingroup\$ Thank you, I accidentally left those parts from the original code. \$\endgroup\$
– Laposhasú Acsa
Commented Oct 8, 2015 at 9:02

Add a comment |

nimi · Accepted Answer · 2015-10-06 19:44:19Z

Haskell, 132 131 bytes

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

algorithmshark · Accepted Answer · 2015-10-07 04:49:31Z

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

Zach Gates · Accepted Answer · 2015-10-07 15:39:50Z

1

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))

edited Oct 7, 2015 at 15:39

answered Oct 6, 2015 at 2:11

Zach Gates

6,69029 silver badges75 bronze badges

\$\begingroup\$ Rather than map with a lambda, would it be better to do ''.join(... for ... in ...)? \$\endgroup\$
– Sp3000
Commented Oct 6, 2015 at 2:21

Add a comment |

Martin Ender · Accepted Answer · 2015-10-11 14:36:28Z

1

Mathematica, 83 bytes

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

This defines an unnamed function.

answered Oct 11, 2015 at 14:36

Martin Ender

197k67 gold badges447 silver badges975 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Ruby, 107 104 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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 6, 2015 at 22:16

Reinstate Monica -- notmaynard

1,0835 silver badges9 bronze badges

\$\begingroup\$ A few bytes to save: (i+=1)%2 is i=1-i. \$\endgroup\$
– nimi
Commented Oct 6, 2015 at 22:32
\$\begingroup\$ @nimi Ah, thank you. I was trying to figure out how to shorten that. \$\endgroup\$
– Reinstate Monica -- notmaynard
Commented Oct 6, 2015 at 22:38

Add a comment |

Olivier Grégoire · Accepted Answer · 2015-10-07 11:01:04Z

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
};

Razetime · Accepted Answer · 2020-10-13 13:01:40Z

0

Husk, 11 bytes

ḋ`Ṙİ¬↔OmLgḋ

Try it online!

answered Oct 13, 2020 at 13:01

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

Add a comment |

caird coinheringaahin g · Accepted Answer · 2020-10-13 21:16:12Z

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

Shaggy · Accepted Answer · 2020-10-13 21:32:43Z

0

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

edited Oct 13, 2020 at 21:32

answered Oct 13, 2020 at 13:39

Shaggy

43.5k4 gold badges36 silver badges94 bronze badges

Add a comment |

Razetime · Accepted Answer · 2020-10-30 06:09:25Z

APL (Dyalog Extended), ³² 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

Stack Exchange Network

Generate the Temple Skyline Sequence

Challenge

17 Answers 17

CJam, 25 23 22 bytes

Explanation

Pyth - 21 20 bytes

Python 2, 121 bytes 125

JavaScript ES6, 110 bytes 113 116 119 120

C++, 535 527 Bytes

Pyth, 20 19 bytes

Perl 5.10, 121 101

Haskell, 132 131 bytes

J - 30 bytes

Python 3, 146 136 bytes

Mathematica, 83 bytes

Ruby, 107 104 102 bytes

Java 8, 179 176 bytes

Husk, 11 bytes

Jelly, 13 bytes

How it works

Japt, 14 bytes

APL (Dyalog Extended), ³² 30 bytes

Explanation

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
binary
or ask your own question.

Linked

Hot Network Questions

Generate the Temple Skyline Sequence

Challenge

17 Answers 17

CJam, 25 23 22 bytes

Explanation

Pyth - 21 20 bytes

Python 2, 121 bytes 125

JavaScript ES6, 110 bytes 113 116 119 120

C++, 535 527 Bytes

Pyth, 20 19 bytes

Perl 5.10, 121 101

Haskell, 132 131 bytes

J - 30 bytes

Python 3, 146 136 bytes

Mathematica, 83 bytes

Ruby, 107 104 102 bytes

Java 8, 179 176 bytes

Husk, 11 bytes

Jelly, 13 bytes

How it works

Japt, 14 bytes

APL (Dyalog Extended), 32 30 bytes

Explanation

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfsequencebinary or ask your own question.

Linked

Related

Hot Network Questions

APL (Dyalog Extended), ³² 30 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
binary
or ask your own question.