Generieren Sie die Temple Skyline-Sequenz

39

Betrachten Sie den folgenden Prozess:

  1. Nehmen Sie eine nicht negative ganze Zahl N.

    zB N = 571

  2. Drücken Sie es binär ohne führende Nullen aus. (Null selbst ist die einzige Ausnahme, immer 0.)

    zB 571= 1000111011in binär

  3. Teilen Sie aufeinanderfolgende Reihen von Einsen und Nullen in dieser binären Darstellung auf.

    zB 10001110111, 000, 111, 0,11

  4. Sortieren Sie die Läufe von der längsten zur kürzesten.

    zB 1, 000, 111, 0, 11000, 111, 11, 1,0

  5. Überschreiben Sie alle Ziffern in jedem Lauf mit abwechselnden 1und 0, immer beginnend mit 1.

    zB 000, 111, 11, 1, 0111, 000, 11, 0,1

  6. Verketten Sie das Ergebnis, um eine neue Binärzahl zu erhalten.

    zB 111, 000, 11, 0, 11110001101= 909in dezimal

Wenn Sie die Werte zeichnen, die durch diesen Prozess erzeugt werden, erhalten Sie ein hübsches Diagramm:

Temple Skyline Grundstück bis 1024

Und es ist hoffentlich klar, warum ich die resultierende Sequenz als Temple Skyline-Sequenz bezeichne :

Tempel-Skyline

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine nicht negative Ganzzahl N aufnimmt und die entsprechende Temple Skyline-Sequenznummer ausgibt oder zurückgibt. Ihre Eingabe und Ausgabe sollten beide dezimal sein.

zB wenn der eingang 571der ausgang sein soll 909.

Der kürzeste Code in Bytes gewinnt.

Als Referenz sind hier die Ausdrücke in der Reihenfolge von N = 0 bis 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

Hier sind die Begriffe von 0 bis 1023.

Calvins Hobbys
quelle

Antworten:

4

Pyth, 20 bis 19 Bytes

ACr.BQ8|is*V_SGH2 1

1 Byte von Jakube gespeichert

Test Suite

Verwendet die Tatsache, dass nach der Lauflängencodierung die Läufe die gewünschten Läufe in der Ausgabe sind.

3 Byte Sondergehäuse 0 verloren.

isaacg
quelle
14

CJam, 25 23 22 Bytes

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

Nur ein bisschen Lauflängencodierung. -1 Danke an @ MartinBüttner.

Probieren Sie es online / Test-Suite .

Erläuterung

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
Sp3000
quelle
11

Pyth - 21 20 Bytes

Danke an @sok, dass du mir ein Byte gespart hast!

is.em%hk2hb_Sr.BQ8 2

Probieren Sie es hier online .

Maltysen
quelle
Sie können .BQanstelle von verwenden jQ2, was bedeutet, dass Sie den Abstand zwischen dem 8und dem vorhergehenden verlieren können 2.
Sok
is*R`s=!Z_ShMr.BQ8 2ist eine interessante Lösung gleicher Länge. Meistens, weil ich nicht wirklich damit gerechnet habe, dass die Zuweisung in einem Kartenargument funktioniert.
FryAmTheEggman
1
@FryAmTheEggman Ersetzen `sdurch ]. Speichert ein Byte.
Jakube
6

Python 2, 121 Bytes 125

121: Danke an Sp3000 für das Abschneiden von 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)
enpenax
quelle
1
Nett! Ich glaube, Sie können auch n*`~i%2`foranstelle von"10"[i%2]*n for
Sp3000
Danke für die Bearbeitung! Ich musste schnell los, wollte mich aber einreichen, weil ich dachte, dass dies eine schöne Herausforderung und eine gute für eine erste Einreichung war. Ich werde Ihre Einreichung in Kürze überprüfen!
Enpenax
Ich denke, dass Sie einige Bytes einsparen können, indem Sie sorted(...,key=len)anstelle von verwenden, map(len,...aber ich verstehe Ihr Programm derzeit nicht vollständig, sodass ich nicht sicher bin, dass Sie davon profitieren würden.
Cole
Hey @Cole, ich ordne zu, lenweil dies die einzige Information ist, die ich brauche, um die Menge von 1 und 0 zu replizieren. Ich habe Ihren Vorschlag ausprobiert und er fügt 2 Bytes hinzu, da ich ihn lendann zweimal verwenden muss, aber danke für den Vorschlag!
Enpenax
5

JavaScript ES6, 110 Bytes 113 116 119 120

3 Bytes gespart dank @intrepidcoder

3 Bytes dank @NinjaBearMonkey gespeichert

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

Unkomplizierter Ansatz. Die Länge der Sortierfunktion gefällt mir nicht, aber ich kann mir keine Möglichkeit zum Golfen vorstellen.

Downgoat
quelle
Ich denke, Sie können eine +anstelle von verwenden eval.
intrepidcoder
@intrepidcoder Danke, das hat 3 Bytes gespart!
Downgoat
Ich kann das nicht testen, split(/(0+)/g)sollte es aber ersetzen können match(/(.)\1*/g).
NinjaBearMonkey
@ NinjaBearMonkey danke, dass 3 Bytes gespart!
Downgoat
Speichern eines Bytes: +(s=0, ... .map(l=>l.replace(/./g,s^=1))...)
Hoffe, ich kann helfen
5

C ++, 535 527 Bytes

(Danke, Zereges, für das Abschneiden einiger Bytes.)

Nachdem wir diese Bytes entfernt haben, ist das Programm nun konkurrenzfähig;)

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

Ich bin neu im Golfen, also gib mir bitte einige Tipps in den Kommentaren .

Dinge wie "Du brauchst diese Klammern nicht" oder "benutze printf" sind alle hilfreich, aber ich schätze auch Ratschläge zur Logik. Danke im Voraus!

Zur Erleichterung des Lesens präsentiere ich die 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;
}

Die EDIT Golf Version hat ein paar Bytes verloren, die ungolfed Version ist unverändert

Liam
quelle
Sie können stattdessen int a; int b;verwenden int a,b;. Auch Variablen im globalen Bereich werden mit initialisiert 0. Außerdem müssen Sie keine geschweiften Klammern verwenden, wenn nur ein Befehl ausgeführt werden muss. Auch ones=!ones;kann vereinfacht werdenones ^= 1;
Zereges
Einige Bytes gespeichert danke
Liam
Verschieben Sie Ihre erste forSchleife um 1, dh for(int i=D;i;i--)und verwenden Sie pow(2,i-1)innerhalb der Schleife.
nimi
@ LiamNoronha Sie haben tatsächlich nicht gespeichert, was ich empfohlen habe :)
Zereges
1
@LiamNoronha Schauen Sie sich das an . Es gibt noch viel Raum für Verbesserungen. ZB Wiederverwenden von Variablen (Speichern von Definitionen) oneskann auch sein int. Vielleicht Makro int(pow(i))in P(i). Ich würde Ihnen empfehlen, die Diskussion hier zu
lesen
2

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

Anwendungsbeispiel:

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

Wie es funktioniert:

                 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
nimi
quelle
2

J - 30 Bytes

Funktion, die rechts eine Ganzzahl annimmt. Behandelt 0 richtig.

(\:~#2|#\)@(#;.1~1,2~:/\])&.#:
  • #: - Nehmen Sie die binäre Darstellung.
  • 1,2~:/\]- Geben Sie zwischen den einzelnen Ziffern True an, wenn sie unterschiedlich sind. Stellen Sie ein True voran, damit die Liste zu Beginn jedes "Laufs" True enthält .
  • (#;.1~...) - Verwenden Sie den obigen booleschen Vektor, um die Länge jedes Laufs zu bestimmen.
  • \:~ - Sortieren Sie diese Längen von der längsten zur kürzesten.
  • 2|#\- Nehmen Sie eine Liste von abwechselnden 1 0 1 0 ...so lange wie die Liste der Längen.
  • (...#...) - Nehmen Sie für jede Zahl auf der linken Seite (sortierte Längen) so viele der entsprechenden Positionen auf der rechten Seite (abwechselnd Einsen und Nullen).
  • &. - Konvertieren Sie diese neue Binärdarstellung zurück in eine Zahl.

Beispiele:

   (\:~#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
algorithmshark
quelle
2

Perl 5.10, 121 101

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

Ich denke, der Sortierteil kann kürzer sein.

Edit: -20 Bytes dank Symbabque!

Laposhasú Acsa
quelle
Sie können das entfernen \n, und das mist für den Abgleich mit regulären Ausdrücken nicht erforderlich. Verwenden Sie in Ihrer Ersetzung einfach .anstelle der Zeichengruppe.
Simbabque
Auch das grepTeil ist nicht erforderlich . Das octist aber ordentlich :)
simbabque
Vielen Dank, ich habe diese Teile versehentlich aus dem Originalcode entfernt.
Laposhasú Acsa
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))
Zach Gates
quelle
Wäre es besser, als mapmit einem lambdazu tun ''.join(... for ... in ...)?
Sp3000,
1

Mathematica, 83 Bytes

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

Dies definiert eine unbenannte Funktion.

Martin Ender
quelle
0

Ruby, 107 104 102 Bytes

(3 Bytes gespart dank nimi )

Ich werde nicht die Gleichen von CJam schlagen, aber ich habe es ziemlich klein für eine vernünftige Sprache.

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
Setzen Sie Monica iamnotmaynard wieder ein
quelle
Ein paar Bytes zu speichern: (i+=1)%2ist i=1-i.
Nimi
@ Nimi Ah, danke. Ich habe versucht herauszufinden, wie ich das verkürzen kann.
Setzen Sie Monica iamnotmaynard
0

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

Ich habe zwei statische Importe verwendet: java.util.Integer.highestOneBitund java.util.Arrays.sort.

Zur besseren Lesbarkeit ist hier der 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
};
Olivier Grégoire
quelle
-1

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)
Tristan Batchler
quelle
4
Willkommen bei PPCG! Leider denke ich, dass dies für einige Zahlen die falschen Werte ergibt, z. B. t(0) = 0wann 1erwartet wird und t(4) = 1wann 6 erwartet wird
Sp3000