Średnie bity: średnie wyzwanie

30

Biorąc pod uwagę liczbę całkowitą N> = 1, wypisz średnią liczbę bitów w liczbie całkowitej od 0 do N - 1

Specyfikacja

  • Dane wyjściowe można obliczyć jako sumę liczby bitów w reprezentacji binarnej każdej liczby całkowitej od 0 do N-1, podzieloną przez N.
  • Binarna reprezentacja liczby całkowitej nie ma w tym kontekście zer wiodących, z wyjątkiem zera, który jest reprezentowany jako 0 w postaci binarnej.
  • Wynik powinien być dokładny co najmniej 7 cyfr znaczących.

Przykład

N = 6

0: 0   : 1 bit
1: 1   : 1 bit
2: 10  : 2 bits
3: 11  : 2 bits
4: 100 : 3 bits
5: 101 : 3 bits

Średnia liczba bitów = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

Przypadki testowe

Wejście => wyjście

1 => 1
2 => 1
3 => 1.3333333
4 => 1.5
5 => 1.8
6 => 2
7 => 2.1428571

Fragment tabeli wyników

( stąd )

Pokaż fragment kodu

Zauważ, że suma (przed podzieleniem w celu znalezienia średniej) jest sekwencją w OEIS .

code-golf math binary bitwise statistics trichopaks
źródło
6
Ładne imię, bardzo punny .
Rɪᴋᴇʀ
3
Dla każdego, kto nie wie, chętniej głosuję za rozwiązaniem z wyjaśnieniem
trichoplax
4
Za mało kalamburów, potrzebujesz trochę więcej, aby to było idealne.
clismique
1
Zakładam, że przez „każdą liczbę” rozumiesz „każdą liczbę całkowitą ”?
Cyoce
@Cyoce tak, dziękuję za zwrócenie na to uwagi - edytowałem je w celu wyjaśnienia.
trichoplax

Odpowiedzi:

13

Pyth, 6 bajtów

.Oml.B

Wypróbuj online tutaj .

.Oml.BdUQ              Filling in implict vars

.O                     Average of list
 m   UQ                Map over [0..input)
  l                    Length of
   .B                  Binary string representation of int
    d                  Lambda var
Maltysen
źródło
Wspólne pierwsze miejsce, ale nie pojawiłeś się na tablicy wyników - wprowadziłem niewielką zmianę w nagłówku, aby to naprawić.
trichoplax
9

Galaretka, 6 bajtów

R’BFL÷

Wypróbuj online!

R’BFL÷  Main monadic chain. Argument: n

R       yield [1, 2, ..., n]
 ’      decrement; yield [0, 1, ..., n-1]
  B     convert to binary; yield [[0], [1], [1,0], [1,1], ...]
   F    flatten list; yield [0, 1, 1, 0, 1, 1, ...]
    L   length of list
     ÷  divide [by n]
Leaky Nun
źródło
7

Oktawa, 29 bajtów

@(n)1+sum(fix(log2(1:n-1)))/n

Wyjaśnienie

              log2(1:n-1)       % log2 of numbers in range [1..n-1]
                                % why no 0? because log2(0) = -Inf  :/
          fix(           )      % floor (more or less, for positive numbers)
      sum(                )     % sum... wait, didn't we miss a +1 somewhere?
                                % and what about that missing 0?
                           /n   % divide by n for the mean
    1+                          % and add (1/n) for each of the n bit lengths 
                                % (including 0!)

Próbka uruchomiona na ideone .

zlewka
źródło
6

Python 3, 43 bajty

def f(n):x=len(bin(n))-2;return(2-2**x)/n+x

Wykorzystuje formułę na stronie OEIS . Zaskakujące jest, że nazwana funkcja jest tutaj nieco tańsza ze względu na przypisanie do x.

Alternatywne podejście dla 46 bajtów:

lambda n:-~sum(map(int.bit_length,range(n)))/n

Niestety, -~ponieważ (0).bit_length()jest to konieczne 0, ale nawet wtedy byłby to bajt za długi.

Sp3000
źródło
6

Julia, 27 bajtów

n->endof(prod(bin,0:n-1))/n

Wypróbuj online!

Jak to działa

Ponieważ *w Julii jest konkatenacja ciągów, prodmoże być używana do konkatenacji tablicy ciągów. Opcjonalnie przyjmuje funkcję jako pierwszy argument, który odwzorowuje na drugi przed pobraniem rzeczywistego „produktu”, podobnie prod(bin,0:n-1)jak ciąg binarnej reprezentacji wszystkich liczb całkowitych w żądanym zakresie. Biorąc długość endofzi dzieląc przez n daje średnią.

Dennis
źródło
5

Julia, 28 bajtów

n->mean(ceil(log2([2;2:n])))

Ponieważ binnie mapuje automatycznie tablic, używamy ceil(log2(n))do uzyskania liczby bitów n-1. Działa to dobrze, ponieważ a:bnotacja Julii obejmuje oba końce, podobnie 2:njak zakres od 2 do n, ale tak naprawdę obliczamy liczbę bitów dla liczb z tego zakresu 1:n-1. Niestety musimy jednak zastosować dodatkowe, 2aby uwzględnić 0.

Wypróbuj online!

Sp3000
źródło
5

MATL, 9 bajtów

q:ZlksG/Q

Wypróbuj online!

Zmodyfikowana wersja ze wszystkimi przypadkami testowymi

Wyjaśnienie

    % Implicitly grab input (N)
q:  % Create array from 1:N-1
Zl  % Compute log2 for each element of the array
k   % Round down to the nearest integer
s   % Sum all values in the array
G   % Explicitly grab input again
/   % Divide by the input
Q   % Add 1 to account for 0 in [0, ... N - 1]
    % Implicitly display the result
Suever
źródło
Kłapnięcie!! (wypełniacz)
David
@David W rzeczywistości twój miał rację. Powielanie danych wejściowych na początku nie działa dla innych wartości ... potrzebujesz G/Qna końcu.
zlewka
5

MATL, 9 bajtów

:qBYszQG/

Wypróbuj online!

Wyjaśnienie

:qBYszQG/
:               % take vector [1..n]
 q              % decrement by 1 to get [0..n-1]
  B             % convert from decimal to binary
   Ys           % cumulative sum (fills in 0's after first 1)
     z          % number of nonzero elements
      Q         % increment by 1 to account for zero
       G        % paste original input (n)
        /       % divide for the mean
zlewka
źródło
5

Galaretka, 8 bajtów

Nie krótszy, ale interesujący algorytm i moje pierwsze zgłoszenie galaretki:

Rl2Ċ»1S÷

R         1 to n
 l2       log2
   Ċ      ceiling
    »1    max of 1 and...
      S   sum
       ÷  divided by n
Adám
źródło
4

Galaretka, 10 bajtów

BL©2*2_÷+®

Z sugestii Sp3000.

Wypróbuj tutaj.

Galaretka, 11 bajtów

æḟ2’Ḥ÷_BL$N

Niezbyt krótki, ale potrzebuję kilku wskazówek.

Wypróbuj tutaj.

Przy użyciu tej samej formuły, co w odpowiedzi Sp3000 . (Nie jest bardzo trudno zdobyć go sam, różnicując postęp geometryczny).

jimmy23013
źródło
Spójrz na moją odpowiedź galaretki w celach informacyjnych.
Leaky Nun
@LeakyNun Wykorzystuje inne podejście, które nie wydaje mi się, że byłoby krótsze niż twoje. Ale _BL$Nwydawało się dość długie ...
jimmy23013
Zasadniczo twój kod to „od podłogi do najbliższej potęgi 2, minus 1, podwójne, podziel przez dane wejściowe, minus binarna długość danych wejściowych, ujemne”?
Leaky Nun
@LeakyNun Tak ..
jimmy23013
3
Tylko nieznacznie lepiej:BL©2*2_÷+®
Sp3000,
4

Java, 135 95 90 bajtów

float a(int n){int i=0,t=0;for(;i<n;)t+=Integer.toString(i++,2).length();return t/(n+0f);}
Shaun Wild
źródło
Myślę, że możesz pozbyć się interfejsu i po prostu utworzyć funkcję lub lambda. Możesz także zwrócić wartość zamiast drukować ją na standardowe wyjście
Frozn
Okej, wdrożę te zasady.
Shaun Wild,
Myślę, że należy na to pozwolić. Ponieważ PO nic nie określił myślę standardowe zasady I / O zastosowania.
Frozn
Tak, funkcja jest w porządku - nie potrzebujesz kompletnego programu. Pamiętaj, że tabela liderów podnosi wynik w pierwszej linii, więc twój wynik obecnie pokazuje się jako 135 zamiast 95.
trichoplax
@trichoplax Nadal ostatnie miejsce. Osobiście obwiniam Javę ...
Shaun Wild
3

Python 3, 46 bajtów

lambda x:sum(len(bin(i))-2for i in range(x))/x

Nazwij to jak

f = lambda x: sum(len(bin(i))-2for i in range(x))/x
print(f(6))
# 2.0

Musiałem cofnąć wersję mapy, ponieważ nie udało się wprowadzić 5

Keatinge
źródło
3

05AB1E, 9 7 bajtów

Kod:

L<bJg¹/

Wyjaśnienie:

L<         # range from 0..input-1
  b        # convert numbers to binary
   J       # join list of binary numbers into a string
    g      # get length of string (number of bits)
     ¹/    # divide by input

Wypróbuj online

Edycja: zapisane 2 bajty dzięki @Adnan

Emigna
źródło
@Adnan: Dzięki! Zapomniałem o J.
Emigna
3

C #, 87 bajtów

double f(int n){return Enumerable.Range(0,n).Average(i=>Convert.ToString(i,2).Length);}

Napisałem odpowiedź w języku C #, ponieważ jej nie widziałem. To mój pierwszy post na jednym z nich, więc daj mi znać, jeśli zrobię coś źle.

raive
źródło
Witamy w Programowaniu zagadek i Code Golf. To świetna pierwsza odpowiedź +1. Czy możesz zmienić doublena, floataby zapisać jeden bajt, czy potrzebujesz precyzji?
wizzwizz4
2
@ wizzwizz4 Thanks! Miałem tę samą myśl, ale średnia () zwraca wartość podwójną. Jeśli zmienię typ zwracany na zmiennoprzecinkowy, muszę jawnie rzucić podwójny i uzyskać na nim 7 bajtów.
raive
2

JavaScript (ES7), 38 32 bajtów

n=>(l=-~Math.log2(n))-(2**l-2)/n

Korzystanie z formuły @ sp3000 (poprzednia wersja była rozwiązaniem rekurencyjnym). Wersja ES6 dla 34 bajtów:

n=>(l=-~Math.log2(n))-((1<<l)-2)/n

Wyjaśnienie wzoru: Rozważ przypadek N = 55. Jeśli piszemy liczby binarne (pionowo, aby zaoszczędzić miejsce), otrzymujemy:

                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010

Rozmiar tego prostokąta wynosi nl, więc średnia wynosi tylko l, ale musimy wykluczyć puste miejsca. Każdy rząd pustych miejsc jest dwa razy dłuższy niż poprzedni, więc suma wynosi 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2 l - 2.

Neil
źródło
2

J, 21 17 15 bajtów

Od 17 bajtów do 15 bajtów dzięki @Dennis.

+/@:%~#@#:"0@i.

Czy ktoś może mi pomóc w golfa? ...

Wersja bez golfa

range        =: i.
length       =: #
binary       =: #:
sum          =: +/
divide       =: %
itself       =: ~
of           =: @
ofall        =: @:
binarylength =: length of binary "0
average      =: sum ofall divide itself
f            =: average binarylength of range
Leaky Nun
źródło
Próbowałem alternatywnego podejścia, przez stringifying listę liczb binarnych, a wyszedł z 25 bajtów: %~>:@#@([:":10#.[:#:i.)-]. Twoje rozwiązanie wygląda raczej optymalnie.
Conor O'Brien,
2

Perl 6 ,  34  32 bajty

{$_ R/[+] map *.base(2).chars,^$_}

{$_ R/[+] map {(.msb||0)+1},^$_}

Wyjaśnienie:

{ 
  $_  # the input
  R/  # divides ( ｢$a R/ $b｣ is the same as ｢$b / $a｣ )
  [+] # the sum of:
  map
    {
      (
       .msb # the most significant digit (0 based)
       || 0 # which returns Nil for ｢0.msb｣ so use 0 instead
            # should be ｢(.msb//0)｣ but the highlighting gets it wrong
            # it still works because it has the same end result 
      ) 
      + 1   # make it 1 based
    },
    ^$_ # ｢0 ..^ $_｣ all the numbers up to the input, excluding the input
}

Test:

use v6.c;

# give it a name
my &mean-bits = {$_ R/[+] map {(.msb||0)+1},^$_}

for 1..7 {
  say .&mean-bits
}

say '';

say mean-bits(7).perl;
say mean-bits(7).base-repeating(10);
1
1
1.333333
1.5
1.8
2
2.142857

<15/7>
(2. 142857)
Brad Gilbert b2gills
źródło
2

Dyalog APL , 14 bajtów

(+/1⌈(⌈2⍟⍳))÷⊢

range ← ⍳
log   ← ⍟
log2  ← 2 log range
ceil  ← ⌈
bits  ← ceil log2
max   ← ⌈
fix0  ← 1 max bits
sum   ← +/
total ← sum fix0
self  ← ⊢
div   ← ÷
mean  ← sum div self
Adám
źródło
2

Clojure, 71 64 63 bajtów

Wygląda na to, że stosunki są prawidłowe w zależności od tego, które formaty liczb są dopuszczalne w danych wyjściowych?

(fn[n](/(inc(apply +(map #(.bitLength(bigint %))(range n))))n))

  • n = 1 => 1
  • n = 7 => 15/7

bez golfa (i nieco przepisany dla ułatwienia wyjaśnienia)

(fn [n]
 (->
  (->>
   (range n)                      ;;Get numbers from 0 to N
   (map #(.bitLength (bigint %))) ;;Cast numbers to BigInt so bitLength can be used
   (apply +)                      ;;Sum the results of the mapping
   (inc))                         ;;Increment by 1 since bitLength of 0 is 0
  (/ n)))                         ;;Divide the sum by N

stara odpowiedź, która była używana (liczba zmiennoprzecinkowa):

(fn[n](float(/(inc(apply +(map #(..(bigint %)bitLength)(range n))))n)))

wyjście jest jak:

  • n = 1 => 1,0
  • n = 7 => 2,142857
znak
źródło
Pytanie, czy ułamki czy proporcje są dopuszczalne, nie było wcześniej podnoszone. W przypadku tego wyzwania zaakceptuję osiągnięty konsensus co do domyślnej wartości .
trichoplax
1

Minkolang 0,15 , 23 bajty

n$z1z[i1+2l$M$Y+]kz$:N.

Wypróbuj tutaj!

Wyjaśnienie

n$z                       Take number from input and store it in register (n)
   1                      Push 1 onto the stack
    z[                    For loop that repeats n times
      i1+                 Loop counter + 1
         2l$M             log_2
             $Y           Ceiling
               +          Add top two elements of stack
                ]         Close for loop
                 z$:      Float divide by n
                    N.    Output as number and stop.

Dość prosta implementacja.

El'endia Starman
źródło
1

JavaScript ES5, 55 bajtów

n=>eval(`for(o=0,p=n;n--;o+=n.toString(2).length/p);o`)

Wyjaśnienie

n =>   // anonymous function w/ arg `n`
  for( // loop
      o=0,  // initalize bit counter to zero
      p=n   // copy the input
    ;n-- // will decrease input every iteration, will decrease until it's zero
    ;o+=    // add to the bitcounter
        n.toString(2)  // the binary representation of the current itearations's
                     .length // length
        /p   // divided by input copy (to avergage)
   );o       // return o variable
Downgoat
źródło
1

Hoon , 71 bajtów

|=
r/@
(^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq

... Jestem prawie pewien, że tak naprawdę po raz pierwszy użyłem rdzeni zmiennoprzecinkowych Hoon. W rzeczywistości jest to implementacja napisana w języku Hoon, która wypływa na SoftFloat, ponieważ jedynymi typami danych w Hoon są atomy i komórki.

Utworzyć funkcję, która pobiera atomu r. Utwórz listę z [0 .. (r - 1)], zamapuj listę na liście, przyjmując logarytm binarny liczby, a następnie złóż tę listę za pomocą ++add. Konwersja zarówno produkcję zagięcia i rdo @rq(quad precyzji liczb zmiennoprzecinkowych) z ++sun:rq, a następnie dzieli jeden po drugim.

Najdziwniejsze w tym fragmencie jest :.^rqkoniec. a:bin Hoon oznacza „oceń a w kontekście b”. ++rqjest rdzeniem zawierającym całą implementację poczwórnej precyzji, jak biblioteka. Więc bieganie (sun 5):rqto to samo, co robienie (sun:rq 5).

Na szczęście rdzenie w Hoon są jak gniazdujące lalki; gdy oceniasz ramię, ++rqaby uzyskać rdzeń, dodaje do niego cały stdlib, dzięki czemu możesz dalej toczyć się, obracać, przepełniać i wszystkie te fajne rzeczy, zamiast utknąć tylko z ramionami zdefiniowanymi w ++rq. Niestety, rq zmienia definicję ++addna dodawanie zmiennoprzecinkowe, a także nie ma rw swoim kontekście. .(cały aktualny kontekst) tak.

Podczas oceny wyrażenia w kontekście kompilator szuka najpierw głębokości kończyny. W naszym przypadku a:[. rq]wyglądałoby to w całym bieżącym kontekście aprzed przejściem do zaglądania rq. Sprawdzimy więc addfunkcję, która działa na atomy zamiast liczb zmiennoprzecinkowych ... ale tak też będzie div. Hoon ma również funkcję, w której użycie ^nameignoruje pierwsze znalezione odniesienie i szuka drugiego.

Stamtąd używa po prostu cukru syntaktycznego a^bbycia równym do [a b]oceny naszego fragmentu zarówno w naszym obecnym kontekście, jak i bibliotece float o poczwórnej precyzji, ignorując podział atomowy na korzyść ++div:rq.

> %.  7
  |=
  r/@
  (^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq
.~~~2.1428571428571428571428571428571428
RenderSettings
źródło
1

W rzeczywistości 7 bajtów:

;r♂├Σl/

Wypróbuj online!

Wyjaśnienie:

;r♂├Σl/
;        duplicate input
 r       push range(0, n) ([0, n-1])
  ♂├     map binary representation
    Σ    sum (concatenate strings)
     l/  divide length of string (total # of bits) by n

Gdyby nie błąd, który właśnie odkryłem, to rozwiązanie działałoby dla 6 bajtów:

r♂├♂læ

æ to wbudowane polecenie średnie.

Mego
źródło
Czy to nie 10 bajtów? Sprawdziłem na bytesizematters.com.
m654
1
@ m654 Właściwie nie używa UTF-8, używa CP437 (lub czegoś takiego).
Alex A.,
@AlexA. Nie wiedziałem o tym.
m654
1
@ m654 Bytesizematters używa całkowicie skompilowanego kodowania, które nie istnieje (i nie może ) w praktyce. W przypadku UTF-8 użyj mothereff.in/byte-counter .
Dennis
@Dennis Dzięki za informację, będę o tym pamiętać.
m654
1

Vitsy, 26 bajtów

To jest pierwsza próba, bardziej w golfa i dodam wyjaśnienie później.

0vVV1HV1-\[2L_1+v+v]v1+V/N

Wypróbuj online!

Addison Crump
źródło
1

PowerShell v2 +, 64 bajty

param($n)0..($n-1)|%{$o+=[convert]::ToString($_,2).Length};$o/$n

Bardzo prosta implementacja specyfikacji. Pętle od 0do $n-1z |%{...}. Każdej iteracji podajemy [convert]nasz numer wejściowy $_do podstawy ciągu znaków 2i bierzemy go length. Gromadzimy to w $o. Po pętlach po prostu dzielimy $o/$n, pozostawiając to w potoku, a dane wyjściowe są niejawne.

Tak długo, jak to jest, jest tak naprawdę krótszy niż formuła, której używają Sp i inni, [math]::Ceiling()i [math]::Log()są absurdalnie trudne. Podstawowa konwersja w PowerShell jest pechowa.

AdmBorkBork
źródło
1

Perl 5.10, 54 bajty

for(1..<>){$u+=length sprintf"%b",$_;$n++}$u/=$n;say$u

Prawie proste. sprintf"%b"to fajny sposób na wyprowadzenie liczby binarnej w Perlu bez użycia dodatkowych bibliotek.

Wypróbuj online!

Paul Picard
źródło
1

CJam, 13 12 11 bajtów

Jeden bajt zapisany dzięki @ Sp3000, a drugi dzięki @ jimmy23013

rd_,2fbs,\/

Wypróbuj online!

Wyjaśnienie

Bezpośredni. Stosuje definicję.

rd      e# read input and convert to double 
_       e# duplicate 
,       e# range from 0 to input minus 1
2fb     e# convert each element of the array to binary 
s       e# convert to string. This flattens the array
,       e# length of array 
\       e# swap 
/       e# divide
Luis Mendo
źródło
1

Jolf, 10 bajtów

/uΜr0xdlBH

Wypróbuj tutaj!

Wyjaśnienie

/uΜr0xdlBH
  Μr0x      map range 0..x
      dlBH  over lengths of binary elements
/u          divide sum of this
            by implicit input (x)
Conor O'Brien
źródło
1

Szybki, 72 bajty

func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
John McDowall
źródło
2
Nie musisz wywoływać funkcji, pozostawienie jej jako zdefiniowanej funkcji jest w porządku. Niezły pierwszy post.
Rɪᴋᴇʀ
1

J, 15 bajtów

%~[:+/#@#:"0@i.

Jest to czasownik monadyczny, używany w następujący sposób:

   f =: %~[:+/#@#:"0@i.
   f 7
2.14286

Wypróbuj tutaj!

Wyjaśnienie

Zaimplementowałem specyfikację wyzwania dosłownie. Istnieją inne podejścia, ale wszystkie okazały się dłuższe.

%~[:+/#@#:"0@i.  Input is y
             i.  Range from 0 to y-1.
          "0@    For each number in this range:
      #@           Compute the length of
        #:         its base-2 representation.
  [:+/           Take the sum of the lengths, and
%~               divide by y.
Zgarb
źródło