Hasilkan Urutan Skyline Kuil

39

Pertimbangkan proses berikut:

  1. Ambil beberapa bilangan bulat non-negatif N.

    misal N = 571

  2. Ekspresikan dalam biner tanpa nol terkemuka. (Nol itu sendiri adalah satu-satunya pengecualian, menjadi 0.)

    misalnya 571= 1000111011dalam biner

  3. Pecah berturut-turut satu dan nol dalam representasi biner ini.

    misalnya 10001110111, 000, 111, 0,11

  4. Sortir proses dari yang terpanjang hingga terpendek.

    misalnya 1, 000, 111, 0, 11000, 111, 11, 1,0

  5. Timpa semua digit di setiap jalankan dengan 1's dan 0' s, selalu dimulai dengan 1's.

    misalnya 000, 111, 11, 1, 0111, 000, 11, 0,1

  6. Menggabungkan hasilnya untuk mendapatkan nomor biner baru.

    misalnya 111, 000, 11, 0, 11110001101= 909dalam desimal

Saat Anda memplot nilai yang dihasilkan oleh proses ini, Anda mendapatkan grafik yang cukup rapi:

Temple Skyline plot to 1024

Dan semoga jelas mengapa saya memanggil urutan yang dihasilkan urutan Temple Skyline :

Temple Skyline

Tantangan

Tulis program atau fungsi yang mengambil bilangan bulat non-negatif N dan mencetak atau mengembalikan nomor urut Temple Skyline yang sesuai. Input dan output Anda harus dalam desimal.

mis. Jika input adalah 571output seharusnya 909.

Kode terpendek dalam byte menang.

Untuk referensi, berikut adalah istilah dalam urutan dari N = 0 hingga 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

Berikut adalah persyaratan dari 0 hingga 1023.

Hobi Calvin
sumber

Jawaban:

4

Pyth, 20 19 byte

ACr.BQ8|is*V_SGH2 1

1 byte disimpan oleh Jakube

Test Suite

Menggunakan fakta bahwa setelah pengodean run-length, proses adalah proses yang diinginkan dalam output.

Casing khusus 3 byte hilang 0.

isaacg
sumber
14

CJam, 25 23 22 byte

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

Hanya sedikit pengkodean run-length. -1 terima kasih kepada @ MartinBüttner.

Cobalah secara online / Test suite .

Penjelasan

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
sumber
11

Pyth - 21 20 byte

Terima kasih kepada @sok karena telah menyelamatkan saya satu byte!

is.em%hk2hb_Sr.BQ8 2

Coba di sini online .

Maltysen
sumber
Anda bisa menggunakan .BQalih-alih jQ2, yang berarti Anda bisa kehilangan ruang antara 8dan sebelumnya 2.
Sok
is*R`s=!Z_ShMr.BQ8 2adalah solusi sama panjang yang menarik. Sebagian besar memposting karena saya tidak benar-benar berharap penetapan dalam argumen peta berfungsi.
FryAmTheEggman
1
@FryAmTheEggman Ganti `sdengan ]. Menghemat satu byte.
Jakube
6

Python 2, 121 byte 125

121: Terima kasih kepada Sp3000 karena telah memangkas 4 byte!

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
sumber
1
Bagus! Saya yakin Anda juga bisa melakukannya n*`~i%2`fordaripada"10"[i%2]*n for
Sp3000
Terima kasih sudah mengedit! Saya harus buru-buru pergi tetapi ingin menyerah karena saya pikir ini adalah tantangan yang indah dan bagus untuk pengiriman pertama. Saya akan memeriksa kiriman Anda segera!
enpenax
Saya pikir Anda dapat menyimpan beberapa byte dengan menggunakan sorted(...,key=len)daripada menggunakan map(len,...tetapi saya tidak sepenuhnya memahami program Anda sekarang jadi saya tidak positif yang akan menguntungkan Anda.
cole
Hai @Cole Saya memetakan lenkarena hanya itu informasi yang saya butuhkan untuk mereplikasi jumlah 1 dan 0. Saya mencoba saran Anda dan menambahkan 2 byte, karena saya harus menggunakan lendua kali, tetapi terima kasih atas sarannya!
enpenax
5

JavaScript ES6, 110 byte 113 116 119 120

Disimpan 3 byte berkat @intrepidcoder

Disimpan 3 byte berkat @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``)

Pendekatan lurus ke depan. Tidak suka panjang fungsi sortir, tapi saya tidak bisa memikirkan cara untuk golf itu.

Downgoat
sumber
Saya pikir Anda bisa menggunakan +bukan eval.
intrepidcoder
@intrepidcoder terima kasih, yang menyelamatkan 3 byte!
Downgoat
Saya tidak dapat menguji ini, tetapi split(/(0+)/g)harus dapat menggantikan match(/(.)\1*/g).
NinjaBearMonkey
@NinjaBearMonkey terima kasih, itu menyelamatkan 3 byte!
Downgoat
Menyimpan satu byte: +(s=0, ... .map(l=>l.replace(/./g,s^=1))...)
Semoga Saya Dapat Membantu
5

C ++, 535 527 Bytes

(Terima kasih nol untuk mencukur beberapa byte.)

Sekarang setelah kita menghapus byte-byte itu, programnya sekarang kompetitif;)

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

Saya baru bermain golf, jadi tolong beri saya beberapa tips di komentar .

Hal-hal seperti "Anda tidak membutuhkan tanda kurung itu" atau "gunakan printf" semuanya membantu, tetapi saya juga menghargai saran tentang logika. Terima kasih sebelumnya!

Untuk memudahkan membaca, saya sajikan versi yang tidak disolf:

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

Versi golf EDIT menurunkan beberapa byte, versi tidak diubah tidak berubah

Liam
sumber
Anda bisa bukannya int a; int b;menggunakan int a,b;. Juga variabel dalam lingkup global diinisialisasi dengan 0. Anda juga tidak harus menggunakan kurung keriting ketika hanya ada satu perintah yang harus dieksekusi. Juga ones=!ones;dapat disederhanakan sebagaiones ^= 1;
Zereges
Menyimpan beberapa byte, terima kasih
Liam,
Geser forloop pertama Anda dengan 1, yaitu for(int i=D;i;i--)dan gunakan pow(2,i-1)di dalam loop.
nimi
@LiamNoronha Anda sebenarnya tidak menyimpan apa yang saya rekomendasikan :)
Zereges
1
@LiamNoronha Lihat ini . Masih ada banyak ruang untuk perbaikan. Misalnya menggunakan kembali variabel (menyimpan definisi),ones bisa juga int. Mungkin macroing int(pow(i))ke P(i). Saya sarankan Anda membaca diskusi di sini
Zereges
2

Haskell, 132 131 byte

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

Contoh penggunaan:

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

Bagaimana itu bekerja:

                 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
sumber
2

J - 30 byte

Fungsi mengambil integer di sebelah kanan. Menangani dengan benar 0.

(\:~#2|#\)@(#;.1~1,2~:/\])&.#:
  • #: - Ambil representasi biner.
  • 1,2~:/\] - Di antara setiap digit, laporkan Benar jika mereka berbeda. Prepend a True sehingga daftar memiliki True di awal setiap "run".
  • (#;.1~...) - Menggunakan vektor boolean di atas, ambil panjang masing-masing proses.
  • \:~ - Urutkan panjang ini dari terpanjang ke terpendek.
  • 2|#\- Ambil daftar bolak-balik 1 0 1 0 ...sepanjang daftar panjang.
  • (...#...) - Untuk setiap angka di sebelah kiri (panjang yang diurutkan), ambil sebanyak mungkin item yang sesuai di sebelah kanan (bergantian angka 1 dan 0)
  • &. - Konversi representasi biner baru ini kembali ke angka.

Contoh:

   (\:~#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
algoritme hiu
sumber
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

Saya pikir bagian semacam itu bisa lebih pendek.

Sunting: -20 byte, terima kasih untuk symbabque!

Laposhasú Acsa
sumber
Anda dapat menyingkirkan \n, dan mtidak diperlukan untuk pencocokan ekspresi reguler. Dalam subtitusi Anda, cukup gunakan .sebagai ganti grup char.
simbabque
Tidak perlu grepbagian itu juga. Ini octrapi meskipun :)
simbabque
Terima kasih, saya tidak sengaja meninggalkan bagian-bagian itu dari kode aslinya.
Laposhasú Acsa
1

Python 3, 146 136 byte

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
sumber
Daripada mapdengan lambda, apakah lebih baik dilakukan ''.join(... for ... in ...)?
Sp3000
1

Mathematica, 83 byte

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

Ini mendefinisikan fungsi yang tidak disebutkan namanya.

Martin Ender
sumber
0

Ruby, 107 104 102 byte

(disimpan 3 byte berkat nimi )

Tidak akan mengalahkan orang-orang seperti CJam, tapi saya mendapatkannya cukup kecil untuk bahasa yang waras.

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
Pasang kembali Monica iamnotmaynard
sumber
Beberapa byte untuk disimpan: (i+=1)%2adalah i=1-i.
nimi
@nimi Ah, terima kasih. Saya mencoba mencari cara untuk mempersingkat itu.
Pasang kembali Monica iamnotmaynard
0

Java 8, 179 176 byte

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

Saya menggunakan dua impor statis: java.util.Integer.highestOneBitdanjava.util.Arrays.sort .

Agar mudah dibaca, berikut adalah kode yang tidak ditandai:

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
sumber
-1

Python 2, 170 byte

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
sumber
4
Selamat datang di PPCG! Sayangnya saya pikir ini memberikan nilai yang salah untuk beberapa angka, misalnya t(0) = 0kapan 1diharapkan dan t(4) = 1kapan 6 diharapkan
Sp3000