Hitung kebenaran yang tertinggal

59

Terinspirasi oleh, dan untuk mengenang, teman dan kolega saya yang terkasih,

Dan Baronet

Dan Baronet , 1956 - 2016. RIP

Dia menemukan solusi APL sesingkat mungkin untuk tugas ini:

Tugas

Diberikan daftar Boolean, hitung jumlah nilai kebenaran yang tertinggal.

Contoh kasus

{}0

{0}0

{1}1

{0, 1, 1, 0, 0}0

{1, 1, 1, 0, 1}1

{1, 1, 0, 1, 1}2

{0, 0, 1, 1, 1}3

{1, 1, 1, 1, 1, 1}6

Adám
sumber
Bisakah kita mengambil daftar sebagai string nol dan satu? misalnya 01100?
Adnan
@Adnan hanya jika itu adalah cara paling normal untuk bahasa Anda mewakili daftar boolean.
Adám
71
Maaf atas kehilanganmu.
Martin Ender
6
@ MartinEnder Terima kasih. Akan sulit untuk maju. Dan mengajari saya semua yang perlu saya ketahui untuk bekerja di Dyalog.
Adám
5
Perpisahan dengan Dan. RIP ...
Erik the Outgolfer

Jawaban:

36

Dyalog APL, 6 2 byte

⊥⍨

Uji di TryAPL .

Bagaimana itu bekerja

(uptack, dyadic: decode) melakukan konversi basis. Jika operan kiri adalah vektor, ia melakukan konversi basis campuran , yang sempurna untuk tugas ini.

Untuk vektor basis b = b n , ⋯, b 0 dan vektor digit a = a n , ⋯, a 0 , b ⊥ a mengonversi a ke basis campuran b , yaitu, menghitung b 0 ⋯ b n-1 a n + ⋯ + b 0 b 1 a 2 + b 0 a 1 + a 0 .

Sekarang, (tilde dieresis , commute ) memodifikasi operator ke kiri sebagai berikut. Dalam konteks monadik, operator memanggil operator dengan argumen kiri dan kanan yang sama.

Misalnya, ⊥⍨ sebuah didefinisikan sebagai suatu ⊥ sebuah , yang menghitung sebuah 0 ⋯ sebuah n + ⋯ + a 0 a 1 a 2 + a 0 a 1 + a 0 , jumlah semua produk kumulatif dari kanan ke kiri .

Untuk k trailing, produk k paling kanan adalah 1 dan yang lainnya 0 , jadi jumlah mereka sama dengan k .

Dennis
sumber
14
Petunjuk: Dan melakukannya hanya dalam dua byte.
Adám
3
Konversi basis campuran! Itu pintar.
Dennis
1
Oh Konversi basis campuran, bagaimana ia menyerang kembali.
Conor O'Brien
Bravo! Faktanya, karena Dan, kami secara khusus membuat b⊥bdan ⊥⍨bmenyerah untuk mempercepat yang tak terbatas.
Adám
19

JavaScript (ES6), 21 byte

f=l=>l.pop()?f(l)+1:0

Uji kasus

Arnauld
sumber
Bagaimana cara kerjanya? Bagaimana cara f(l)+1mengembalikan nilai > 2?
Oliver
@ Oliver Ini adalah proses rekursif, dievaluasi sebagai l.pop()?(l.pop()?(l.pop()?(...etc...)+1:0)+1:0)+1:0.
Arnauld
Saya melihat. Terima kasih untuk penjelasannya.
Oliver
11

Jelly , 4 byte

ŒrṪP

Cobalah online! atau Verifikasi semua kasus uji.

Untuk kasus di mana daftar kosong, ada beberapa pengamatan yang aneh. Pertama, run-length encoding daftar kosong []mengembalikan daftar kosong lain []. Kemudian retreiving elemen terakhir dari yang menggunakan ekor kembali 0bukan pasangan [value, count]yang merupakan elemen reguler dari array yang dikodekan run-length. Kemudian produk Pkembali 0ketika dipanggil 0yang merupakan hasil yang diharapkan.

Penjelasan

ŒrṪP  Main link. Input: list M
Œr    Run-length encode
  Ṫ   Tail, get the last value
   P  Product, multiply the values together
mil
sumber
Atau, ŒgṪSbekerja juga!
Lynn
Ini memberikan output yang tepat untuk daftar kosong sebagai input, tapi saya terkejut diberi pembedahan. Maukah Anda berjalan melalui kasing khusus itu?
Peter Taylor
@ PeterTaylor Saya terkejut juga bahwa itu berhasil. Juga, saya baru saja memperhatikan bahwa tautan pertama memiliki kode yang salah.
mil
@PeterTaylor di Jelly diimplementasikan sebagai: lambda z: iterable(z).pop() if iterable(z) else 0. iterableketika dipanggil pada daftar hanya mengembalikan daftar, dan daftar kosong ini tentu saja palsu.
FryAmTheEggman
10

Brachylog , 7 6 5 byte

@]#=+

Cobalah online!

Penjelasan

@]        A suffix of the Input...
  #=      ...whose elements are all equal
    +     Sum its elements

Sejak @] - Suffixmulai dari sufiks terbesar hingga yang terkecil, ia akan menemukan jangka waktu terpanjang pertama.

Fatalisasi
sumber
10

CJam (8 byte)

{W%0+0#}

Test suite online

Pembedahan

{    e# begin a block
  W%  e# reverse the array
  0+  e# append 0 so there's something to find
  0#  e# find index of first 0, which is number of nonzeros before it
}
Peter Taylor
sumber
10

Haskell, 26 25 byte

a%b|b=1+a|0<3=0
foldl(%)0

Pemakaian:

Prelude> foldl(%)0 [True,False,True,True]
2

Versi pointfree (26 byte):

length.fst.span id.reverse

Menggunakan daftar integer alih-alih daftar bool (21 byte, terima kasih kepada Christian Sievers):

a%b=b*(a+1)
foldl(%)0

Pemakaian:

Prelude> foldl(%)0 [1,0,1,1]
2

Versi pointfree (25 byte)

sum.fst.span(==1).reverse
Laikoni
sumber
Untuk daftar bilangan bulat foldlide tersebut bekerja dengana%b=b*(a+1)
Christian Sievers
9

Retina , 7 5 byte

r`1\G

Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)

Menentukan format input untuk Retina tidak sepenuhnya ambigu. Karena Retina tidak memiliki konsep jenis apa pun kecuali string (dan juga tidak ada nilai yang dapat digunakan untuk definisi biasa kita tentang kebenaran dan kepalsuan), saya biasanya menggunakan 0dan 1(atau sesuatu yang positif secara umum) untuk berhubungan dengan kebenaran dan kepalsuan, karena mereka mewakili nol atau beberapa pertandingan, masing-masing.

Dengan representasi karakter tunggal, kita juga tidak memerlukan pemisah untuk daftar (yang sedikit banyak, lebih banyak representasi daftar alami untuk bahasa yang hanya memiliki string). Adm mengkonfirmasi bahwa ini adalah format input yang dapat diterima.

Adapun regex itu sendiri, itu cocok dari right ke kiri dan \Gjangkar setiap pertandingan ke yang sebelumnya. Oleh karena itu, ini menghitung berapa banyak yang 1dapat kita cocokkan dari akhir string.

Martin Ender
sumber
"Ya, untuk Retina, karena ia hanya menangani string, saya pikir string" 01 "atau" FT "sudah beres.
Adám
9

05AB1E , 12 10 6 5 byte

Disimpan 1 byte berkat carusocomputing .

Î0¡¤g

Cobalah online!

Penjelasan

Î      # push 0 and input
 0¡    # split on 0
   ¤   # take last item in list
    g  # get length
Emigna
sumber
0¡¤gadalah empat byte.
Magic Gurita Guci
@carusocomputing: Bagus! Itu belum diklarifikasi apakah input string baik-baik saja ketika saya menulis ini, tapi sekarang saya mengerti bahwa itu :)
Emigna
J0¡¤gjuga masih lebih pendek;).
Magic Gurita Guci
@carusocomputing: Sayangnya kami perlu Îmenangani input yang kosong, tetapi masih byte yang disimpan, terima kasih :)
Emigna
8

Python, 31 byte

lambda a:(a[::-1]+[0]).index(0)
Mitch Schwartz
sumber
7

Jelly , 4 byte

ṣ0ṪL

TryItOnline! , atau semua tes

Bagaimana?

ṣ0ṪL - Main link: booleanList
ṣ0   - split on occurrences of 0 ([] -> [[]]; [0] -> [[],[]]; [1] -> [[1]]; ...)
  Ṫ  - tail (rightmost entry)
   L - length
Jonathan Allan
sumber
7

Mathematica, 25 24 byte

Fold[If[#2,#+1,0]&,0,#]&
alephalpha
sumber
3
Hanya merekam port dari solusi base-base Dan yang keren: FromDigits[b=Boole@#,MixedRadix@b]&(35 byte).
Greg Martin
5

Pyth, 6 byte

x_+0Q0

Coba di sini!

Menambahkan 0, membalikkan dan menemukan indeks 0 pertama

Biru
sumber
@ Jakube diperbaiki sekarang - algoritma berbeda
Biru
5

C90 (gcc), 46 byte

r;main(c,v)int**v;{while(0<--c&*v[c])r++;c=r;}

Input melalui argumen baris perintah (satu integer per argumen), output melalui kode keluar .

Cobalah online!

Bagaimana itu bekerja

r adalah variabel global. Jenisnya default ke int dan, karena bersifat global, nilainya default ke 0 .

Argumen fungsi c juga default untuk int . Ini akan menyimpan integer n +1 untuk array n Boolean; argumen pertama dari utama adalah selalu path dari executable.

Argumen fungsi v dinyatakan sebagai int**. Jenis sebenarnya dari v adalah char**, tetapi karena kita hanya akan memeriksa bit paling tidak signifikan dari setiap argumen untuk memberi tahu karakter 0 (titik kode 48 ) dan 1 (titik kode 49 ), ini tidak akan berpengaruh pada little-endian mesin.

Loop sementara menurunkan c dan membandingkannya dengan 0 . Setelah c mencapai 0 , kami akan keluar dari loop. Ini diperlukan hanya jika array mengandung no 0 's.

Selama 0<--cpengembalian 1 , kita mengambil c th argumen baris perintah ( v[c]) dan ekstrak karakter pertama dengan oleh dereferencing pointer ( *). Kami mengambil bitwise AND dari Boolean 0<--cdan titik kode karakter (dan tiga byte sampah yang mengikutinya), sehingga kondisinya akan mengembalikan 0 sekali 0 ditemui, keluar dari loop.

Dalam kasus yang tersisa, sedangkan argumen baris perintah adalah 1 , r++bertambah r dengan 1 , sehingga menghitung jumlah trailing 1 's.

Akhirnya, c=rsimpan nilai yang dihitung dari r in c . Dengan pengaturan default, kompiler mengoptimalkan dan menghapus tugas; sebenarnya menghasilkan movl %eax, -4(%rbp)instruksi. Karena retmengembalikan nilai register EAX, ini menghasilkan output yang diinginkan.

Perhatikan bahwa kode ini tidak berfungsi dengan C99, yang mengembalikan 0 dari main jika akhir main tercapai.

Dennis
sumber
Bukankah argcsetidaknya 1( argv[0]berisi nama file)? Anda dapat menyimpan satu byte dengan --c&&alih - alih 0<--c&. kode keluar gcc diambil dari argc? Rapi.
Titus
@Titus Itu tidak akan berhasil. *v[c]adalah titik kode 1 atau 0 , jadi 49 atau 48 dan karenanya selalu benar.
Dennis
Dengan C89 dan C90, gcc mengembalikan apa pun yang ada di RAX pada saat itu. C99 selalu mengembalikan 0 dari utama jika akhir tercapai.
Dennis
4

k, 6 byte

+/&\|:

Komposisi fungsi ini diterjemahkan ke sum mins reversedalam q, saudara lebih mudah dibaca bahasa, di mana menit adalah minimum bergulir.

skeevey
sumber
Bisakah: dijatuhkan?
streetster
4

J, 9 3 byte

#.~

Ini adalah konversi basis campuran refleksif. Karena ini sama dengan konversi basis campuran. Lagi.

Uji kasus

   v =: #.~
   ]t =: '';0;1;0 1 1 0 0;1 1 1 0 1;1 1 0 1 1;0 0 1 1 1;1 1 1 1 1 1
++-+-+---------+---------+---------+---------+-----------+
||0|1|0 1 1 0 0|1 1 1 0 1|1 1 0 1 1|0 0 1 1 1|1 1 1 1 1 1|
++-+-+---------+---------+---------+---------+-----------+
   v&.> t
+-+-+-+-+-+-+-+-+
|0|0|1|0|1|2|3|6|
+-+-+-+-+-+-+-+-+
   (,. v&.>) t
+-----------+-+
|           |0|
+-----------+-+
|0          |0|
+-----------+-+
|1          |1|
+-----------+-+
|0 1 1 0 0  |0|
+-----------+-+
|1 1 1 0 1  |1|
+-----------+-+
|1 1 0 1 1  |2|
+-----------+-+
|0 0 1 1 1  |3|
+-----------+-+
|1 1 1 1 1 1|6|
+-----------+-+
Conor O'Brien
sumber
2
Petunjuk: Ini dapat dilakukan hanya dalam 3 byte, menggunakan terjemahan J dari solusi Dan.
Adám
1
@ Adám saya mencoba mencari solusi. Tidak memikirkan konversi basis. Dia benar-benar pintar!
Conor O'Brien
1
Iya. Itu Dan. :-(
Adám
4

R, 40 39 25 byte

Solusi yang sepenuhnya dikerjakan ulang berkat @Dason

sum(cumprod(rev(scan())))

Baca input dari stdin, balikkan vektor dan jika elemen pertama adalah !=0output, panjang pertama dari run-length encoding ( rle), yang lain 0.

Billywob
sumber
1
Anda dapat menyimpan byte dengan mengubah baris kedua menjadi ifelse(r$v,r$l,0)[1]. (Vektor jika, dan kemudian ambil elemen pertama.)
rturnbull
1
tidak perlu untuk iflelse - cukup kalikan r $ v dan r $ l.
Dason
Tetapi rute sum (cumprod (rev (.))) Harus menyimpan banyak byte
Dason
3

Haskell, 24 byte

foldl(\a b->sum[a+1|b])0

Iterate atas daftar, tambahkan satu untuk setiap elemen, ulang ke 0setelah itu hits a False.

16 byte dengan 0/1 input:

foldl((*).(+1))0

Jika daftar dijamin tidak kosong, kami bisa mendapatkan 14 byte:

sum.scanr1(*)1

Ini menghitung produk kumulatif dari belakang, lalu menjumlahkannya. Produk kumulatif tetap 1 hingga 0 terkena, dan kemudian menjadi 0. Jadi, 1 sesuai dengan tertinggal 1.

Tidak
sumber
3

C # 6, 103 72 byte

using System.Linq;
int a(bool[] l)=>l.Reverse().TakeWhile(x=>x).Count();

Menggunakan daftar non-generik, ketuk daftar generik sebanyak 1 byte lol

-31 byte terima kasih kepada Scott

Tautan Ng
sumber
Jika Anda menggunakan array ints, Anda dapat menggunakanint a(int[] l)=>l.Reverse().TakeWhile(i=>i>0).Sum();
Scott
@Scott Tentu saja apa yang saya pikirkan ... Saya akan tetap dengan bool sekalipun. Pertanyaan menentukan daftar boolean dan itu bukan C.
Tautan Ng
Kompilasi ke Func<bool[], int>57 byte yaituusing System.Linq;l=>l.Reverse().TakeWhile(x=>x).Count();
TheLethalCoder
2

Python, 37 byte

f=lambda l:len(l)and-~f(l[:-1])*l[-1]
orlp
sumber
2

DASH , 16 byte

@len mstr"1+$"#0

Ini bukan solusi DASH terpendek yang mungkin, tetapi solusi DASH terpendek yang mungkin mengganggu saya. Saya memposting pendekatan novel ini sebagai gantinya.

Pemakaian:

(@len mstr"1+$"#0)"100111"

Penjelasan

@(                 #. Lambda
  len (            #. Get the length of the array after...
    mstr "1+$" #0  #. ... matching the argument with regex /1+$/
  )                #. * mstr returns an empty array for no matches
)
Mama Fun Roll
sumber
2

Scala, 25 byte

l=>l.reverse:+0 indexOf 0

Tidak Disatukan:

l=>(l.reverse :+ 0).indexOf(0)

Membalik daftar, menambahkan 0 dan menemukan indeks pertama 0, yang merupakan jumlah elemen sebelum 0 pertama

corvus_192
sumber
2

Batch, 57 byte

@set n=0
@for %%n in (%*)do @set/an=n*%%n+%%n
@echo %n%

Mengambil input sebagai parameter baris perintah. Bekerja dengan mengalikan akumulator dengan nilai saat ini sebelum menambahkannya, sehingga nol di baris perintah mereset hitungan. Perhatikan bahwa %%ntidak sama dengan variabel natau %n%.

Neil
sumber
2

GolfSharp, 14 byte

n=>n.V().O(F);
downrep_nation
sumber
2

Java 7, 62 byte

int c(boolean[]a){int r=0;for(boolean b:a)r=b?r+1:0;return r;}

Tidak digabungkan & kode uji:

Coba di sini.

class M{
  static int c(boolean[] a){
    int r = 0;
    for (boolean b : a){
      r = b ? r+1 : 0;
    }
    return r;
  }

  public static void main(String[] a){
    System.out.print(c(new boolean[]{}) + ", ");
    System.out.print(c(new boolean[]{ false }) + ", ");
    System.out.print(c(new boolean[]{ true }) + ", ");
    System.out.print(c(new boolean[]{ false, true, true, false, false }) + ", ");
    System.out.print(c(new boolean[]{ true, true, true, false, true }) + ", ");
    System.out.print(c(new boolean[]{ true, true, false, true, true }) + ", ");
    System.out.print(c(new boolean[]{ false, false, true, true, true }) + ", ");
    System.out.print(c(new boolean[]{ true, true, true, true, true, true }));
  }
}

Keluaran:

0, 0, 1, 0, 1, 2, 3, 6
Kevin Cruijssen
sumber
2

Perl 5.10, 22 byte

21 byte + 1 byte untuk -aflag. Sejak ekspresi berbasis regex dilakukan ...: hal

Nilai input untuk array harus dipisahkan oleh spasi.

$n++while pop@F;say$n

Cobalah online!

Paul Picard
sumber
1
Sedikit lebih pendek jika Anda mengambil argumen melalui baris perintah: perl -E '$_++while pop;say' 0 1 1 0 1 1 1tapi ini tidak menghasilkan apa pun untuk 0(meskipun tidak yakin apakah itu masalah!)
Dom Hastings
2

Perl, 22 byte

21 byte kode + 1 byte untuk -pflag.

s/.(?=.*0)//g;$_=y;1;

Untuk menjalankannya:

perl -pE 's/.(?=.*0)//g;$_=y;1;' <<< "0 1 1 0 1 1 1"

(Sebenarnya, format input tidak peduli banyak: 0110111, 0 1 1 0 1 1 1, [0,1,1,0,1,1,1]dll akan semua pekerjaan)


Versi 18 bytes dari @Dom Hastings tetapi harus memasok input sebagai string 0 dan 1, yang tidak diizinkan:

perl -pE '/1*$/;$_=length$&' <<< '0110111'
Dada
sumber
Suka ;trik itu :) Jika format adalah satu string berkelanjutan: perl -pE '/1*$/;$_=length$&' <<< '0110111'untuk 18, tidak yakin apakah itu membengkokkan aturan atau tidak ...
Dom Hastings
@Hastings ya, aku juga! (Terima kasih, Ton karena telah menunjukkan itu kepada saya!) Komentar pertama dan kedua dari pertanyaan tersebut agaknya tidak mengizinkan format input yang Anda butuhkan untuk solusi Anda ... Tapi saya akan mengedit posting saya untuk menyarankan versi Anda jika format input lebih Gratis.
Dada
2

PHP, 50 byte

<?=strlen(preg_filter('/.*[^1]/','',join($argv)));

Anehnya percobaan pertama saya dengan regex ternyata lebih pendek daripada percobaan saya dengan array ...
Gunakan seperti:

php tt.php 1 1 0 1 1
pengguna59178
sumber
2

Ruby 37 32 byte

->n{n.size-1-(n.rindex(!0)||-1)}

Membuat fungsi anonim yang menemukan instance paling kanan dari nilai palsu, dan menghitung ukuran subarray mulai dari nilai itu.

Ini digunakan !0sebagai salah, karena 0 adalah nilai kebenaran di Ruby. rindexmenemukan indeks terakhir dari nilai dalam array.

Penggunaan :

boolean_list = [true, false, false, true]
->n{n.size-1-(n.rindex(!0)||-1)}[boolean_list]

Pengembalian 1


Jika saya diizinkan untuk melewatkan string 0s dan 1s sebagai parameter baris perintah (yang bukan bagaimana ruby ​​mewakili daftar booleans), saya bisa menurunkannya menjadi 24:

$*[0]=~/(1*)\z/;p$1.size

Ini menggunakan ekspresi reguler dan mencetak panjang string yang dikembalikan oleh ekspresi reguler /(1*)\z/, di mana \zujung string. $*[0]adalah argumen pertama yang diloloskan dan merupakan string 0s dan 1s.

Pemakaian:

trailing_truths.rb 011101

Pengembalian 1.

IMP1
sumber
1
Setelah Anda memiliki indeks dari nilai false terakhir, mengapa Anda perlu mengambil elemen dari array lagi?
Lee W
Anda benar, saya tidak. Terima kasih. Off 5 byte!
IMP1