39
\$\begingroup\$

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:

Temple Skyline plot to 1024

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

Temple Skyline

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.

\$\endgroup\$

14 Answers 14

4
\$\begingroup\$

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.

\$\endgroup\$
14
\$\begingroup\$

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
\$\endgroup\$
11
\$\begingroup\$

Pyth - 21 20 bytes

Thanks to @sok for saving me one byte!

is.em%hk2hb_Sr.BQ8 2

Try it here online.

\$\endgroup\$
  • \$\begingroup\$ You can use .BQ instead of jQ2, which means you can lose the space between the 8 and the preceding 2. \$\endgroup\$ – Sok Oct 6 '15 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 Oct 6 '15 at 15:17
  • 1
    \$\begingroup\$ @FryAmTheEggman Replace `s with ]. Saves one byte. \$\endgroup\$ – Jakube Oct 11 '15 at 15:38
6
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice! I believe you can also do n*`~i%2`for instead of "10"[i%2]*n for \$\endgroup\$ – Sp3000 Oct 6 '15 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\$ – enpenax Oct 6 '15 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 Oct 7 '15 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\$ – enpenax Oct 7 '15 at 6:24
5
\$\begingroup\$

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.

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

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

\$\endgroup\$
  • \$\begingroup\$ 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; \$\endgroup\$ – Zereges Oct 6 '15 at 19:51
  • \$\begingroup\$ Saved some bytes thanks \$\endgroup\$ – Liam Oct 6 '15 at 20:13
  • \$\begingroup\$ Shift your first for loop by 1, i.e. for(int i=D;i;i--) and use pow(2,i-1) inside the loop. \$\endgroup\$ – nimi Oct 6 '15 at 20:36
  • \$\begingroup\$ @LiamNoronha You actually did not save what I recommended :) \$\endgroup\$ – Zereges Oct 6 '15 at 20:53
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Zereges Oct 6 '15 at 21:05
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

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

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))
\$\endgroup\$
  • \$\begingroup\$ Rather than map with a lambda, would it be better to do ''.join(... for ... in ...)? \$\endgroup\$ – Sp3000 Oct 6 '15 at 2:21
1
\$\begingroup\$

Mathematica, 83 bytes

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

This defines an unnamed function.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ A few bytes to save: (i+=1)%2 is i=1-i. \$\endgroup\$ – nimi Oct 6 '15 at 22:32
  • \$\begingroup\$ @nimi Ah, thank you. I was trying to figure out how to shorten that. \$\endgroup\$ – Reinstate Monica iamnotmaynard Oct 6 '15 at 22:38
0
\$\begingroup\$

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
};
\$\endgroup\$
-1
\$\begingroup\$

Python 2, 170 bytes

def t(n):
  from itertools import groupby;lst=sorted([''.join(g) for n,g in groupby(bin(n)[2:])],key=len)[::-1];s=''
  for i in lst:s+=str(i)
  return int(s,2)
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to PPCG! Unfortunately I think this gives the wrong values for some numbers, e.g. t(0) = 0 when 1 is expected and t(4) = 1 when 6 is expected \$\endgroup\$ – Sp3000 Oct 6 '15 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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