Anda memiliki koin yang menghasilkan 0
atau 1
. Tetapi Anda mencurigai koin itu bias , artinya kemungkinan 0
(atau 1
) tidak harus 1/2.
Sebuah terkenal prosedur untuk "mengubah" koin bias menjadi koin (yaitu untuk mendapatkan hasil yang sama mungkin), seperti yang diusulkan oleh von Neumann, adalah sebagai berikut. Menghasilkan (tidak tumpang tindih) blok dari dua lemparan koin sampai dua nilai blok berbeda; dan output nilai pertama di blok itu (nilai kedua juga akan dilakukan, tetapi untuk tujuan tantangan ini kita memilih yang pertama). Secara intuitif, 1
mungkin lebih mungkin daripada 0
, tetapi 01
dan 10
akan sama mungkin.
Misalnya, input 1110...
akan membuang blok pertama, lalu menghasilkan 1
dari blok kedua, ...
Prosedur ini mahal , karena beberapa lemparan koin dikonsumsi untuk menghasilkan hasil tunggal.
Tantangan
Ambil urutan nol dan satu yang terbatas, mewakili lemparan koin asli, dan hasilkan jumlah hasil maksimum sesuai dengan prosedur di atas, sampai semua input dikonsumsi.
Blok terakhir mungkin tidak lengkap, jika jumlah nilai input ganjil. Misalnya, urutan input tidak 11111
akan menghasilkan hasil (dua blok pertama memiliki nilai yang sama, dan blok ketiga tidak lengkap).
Aturan
Input dapat memiliki jumlah nilai non-negatif, tidak harus positif atau bahkan.
Format input mungkin:
- sejumlah nol dan satu;
- string nol dan yang dengan pemisah opsional.
Format output mungkin:
- serangkaian nol dan satu, dengan atau tanpa pemisah;
- sejumlah nol dan satu;
- string yang mengandung nol tunggal atau satu, dipisahkan oleh baris baru;
- format serupa yang wajar dan sesuai dengan bahasa Anda.
Golf kode. Bytes paling sedikit menang.
Uji kasus
Input dan output di sini diasumsikan sebagai string.
Input --> Output
'1110' --> '1'
'11000110' --> '01'
'1100011' --> '0'
'00' --> ''
'1' --> ''
'' --> ''
'1101001' --> '0'
'1011101010' --> '1111'
Jawaban:
Jelly, 6 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Retina ,
1614 byteCobalah online!
Penjelasan
Ini cukup sederhana. Kode mendefinisikan satu penggantian substitusi tunggal menggantikan semua kecocokan (tidak tumpang tindih)
(.)\1|(.)?.
dengan apa pun yang ditangkap kelompok kedua. Ini menggabungkan tiga kasus berbeda menjadi satu:Jika dua digit berulang sama, kami menghapusnya dari string (karena grup 2 tidak digunakan).
Kalau tidak, jika kita dapat mencocokkan dua karakter, hapus yang kedua, dengan mengganti keduanya dengan yang pertama. Jika bukan itu masalahnya maka
?
akan menghilangkan grup:Ini hanya terjadi jika ada karakter trailing tidak berpasangan, yang juga dihapus.
sumber
Labirin ,
2112 byteContoh langka dari program Labirin kompak yang juga tidak memiliki larangan.Di|
versi sebelumnya sama sekali tidak perlu, dan menghapusnya secara besar-besaran mengurangi ukuran program. Faktanya, Lab mengalahkan Retina!Cobalah online!
Kiri bawah
"
juga bisa menjadi ruang, tetapi memiliki di sana sangat menyederhanakan penjelasan.Penjelasan
Yang ini agak rumit, jadi disertai dengan gambar. Tapi pertama-tama, primer cepat:
Mendirikan
Program dimulai di kiri atas
"
, yang merupakan no-op. Lalu kami melakukan:Ini meninggalkan tumpukan dengan 0 tunggal di atasnya, yang sama baiknya dengan kosong untuk keperluan Labirin.
Masukan dan terminasi bacaan
,
membaca char dari input, menghasilkan 48 atau 49 untuk0
atau1
masing - masing, dan -1 pada EOF. Karena ini bukan nol, bagaimanapun kita berubah menjadi:
, yang menduplikasi bagian atas tumpukan.Jalan
:
buntu, jadi kami berbalik dan mengeksekusi,
sekali lagi. Sekarang jika input terakhir adalah EOF, maka kita berbelok ke kiri dan mengakhiri dengan@
, kalau tidak kita berbelok ke kanan, dengan tumpukan tampak seperti[a a b]
(di manaa
,b
adalah dua karakter).Menafsirkan lemparan koin
Jika kami tidak berhenti, langkah selanjutnya adalah mengeksekusi
$
(bitwise xor) lagi. Ini menghasilkan 0 jika karakter inputnya sama, 1 sebaliknya. Kami kemudian gandakana
dengan hasil ini, memberikan 0 ataua
. Sejak*
berada di persimpangan, nilai tumpukan teratas ini menentukan apa yang terjadi selanjutnya.Dalam 0 case, kita langsung saja menjalankan tiga
"
no-ops, sebelum melakukan(
decrement. Seperti pengaturan, ini membuat kita berbalik dan mengeksekusi"*$
, membuat kita siap untuk membaca lebih banyak karakter.Kalau tidak, dalam
a
kasus ini, kita belok kanan di persimpangan karenaa
positif (48 atau 49)..
output char, membiarkan stack kosong, dan(
mengurangi bagian atas stack, memutar 0 ke -1. Sekali lagi, ini membuat kita berbelok ke kiri, menjalankan"*$
seperti pada pengaturan, juga membuat kita siap untuk membaca lebih banyak input.sumber
(
kemudian.
, menghasilkan char 255 (-1 modulo 256). Jadi sudah salah mulai dari sana, sayangnya: PCJam,
108 byteUji di sini.
Penjelasan
Ini adalah solusi yang sangat sederhana: di setiap pasangan, hapus semua instance dari karakter terakhir. Digit berulang dan digit trailing tidak berpasangan akan dihapus, seperti halnya digit kedua dari setiap pasangan digit yang tidak sama:
Ini hanya menyisakan digit yang kita cari. Inilah cara kode menghitung ini:
Ketika daftar dicetak secara otomatis di akhir program, string kosong dihilangkan.
sumber
Perl,
191817 byteSolusi @Martin Büttner Retina menginspirasi gain 2 byte
Termasuk +1 untuk
-p
Jalankan dengan input pada STDIN, mis
perl -p fair.pl <<< 11000110
fair.pl
:Tidak banyak yang bisa dijelaskan di sini karena ini merupakan terjemahan spesifikasi (tidak langsung):
(.)\1
Jika 2 digit pertama sama, jatuhkan.\K.
Kalau tidak, dua digit pertama berbeda. Simpan (\K
) yang pertama.?\K.
Kecuali bahwa yang pertama.
adalah opsional. Hal ini memungkinkan untuk satu pertandingan di ujung string yang kemudian dibuang karena bagian yang disimpan kosongsumber
Mathematica, 36
38byte-2 setelah mencuri fungsi @ LegionMammal978 untuk menentukan apakah daftar 2-elemen adalah {0,1} atau {1,0}
Argumen diharapkan menjadi daftar bilangan bulat.
sumber
Hexagony ,
2321 byteDibuka:
Ini berakhir dengan kesalahan, tetapi pesan kesalahan pergi ke STDERR.
Cobalah online!
Menilai dari jumlah mirror, mungkin saja cukup untuk memasangnya menjadi side-length 3 tapi sejauh ini saya belum beruntung.
Penjelasan
Berikut diagram yang biasa, dihasilkan dengan HexagonyColorer Timwi :
Program ini hanya menggunakan tiga sisi memori, diberi label A , B , dan C di sini (diagram milik Timwi's EsotericIDE ):
Eksekusi dimulai di jalur biru. The
/
hanya cermin yang mengarahkan pointer instruksi (IP), kode aktual adalah:The
,
akan mengatur tepi untuk-1
bukan kode karakter jika kita telah memukul EOF. Karena kami menambah kedua input yang tidak mengubah apakah mereka sama atau tidak, tetapi mengubah EOF menjadi0
.Kami menggunakan modulo untuk memeriksa persamaan, karena itu
1
atau49
(positif) untuk karakter yang tidak sama dan0
karakter yang sama. Ini juga berfungsi sebagai akhir dari program, karena ketika kita memiliki0
dari EOF, pembagian yang dicoba dengan nol akan menyebabkan kesalahan.Sekarang yang
<
membedakan nol dari hasil positif. Yang sederhana pertama: jika karakternya sama, IP mengambil jalur merah._
adalah cermin,\
juga cermin tetapi diabaikan, dan>
membelokkan IP sedemikian rupa sehingga membungkus tepi dan mulai dari atas lagi. Namun, pada iterasi ini, peran A , B dan C bertukar secara siklis ( C sekarang mengambil peran A dan seterusnya).Jika karakter berbeda, jalur hijau diambil sebagai gantinya. Yang ini agak berantakan. Pertama-tama melompati no-op dengan
$
, kemudian membungkus ke sekitar/
di tepi kiri, kemudian melintasi baris kedua-ke-terakhir dari kanan ke kiri dan akhirnya kembali memasuki bagian yang menarik dari kode sumber di{
. Ada sedikit kode yang pada dasarnya linier, yang akan saya jelaskan sebentar lagi, sebelum$
IP melompati>
untuk menggabungkan dua jalur lagi.Inilah potongan kode linear:
Perhatikan bahwa dalam kasus ini, peran tepi untuk iterasi berikutnya juga ditukar secara siklikal, tetapi dengan B mengambil peran A dan seterusnya.
sumber
Haskell,
714429 byteGolf ekstrim oleh nimi .
sumber
> <> , 11 byte
> <> sangat cocok untuk tantangan membaca-a-char-at-a-time seperti ini :) Coba online!
Ini semua terjadi dalam satu lingkaran karena pointer instruksi membungkus begitu mencapai akhir baris.
sumber
>
atau<
Python, 42 byte
Bersenang-senang dengan rekursi dan bitor xor. Mengambil daftar 1s dan 0s sebagai input.
sumber
JavaScript (ES6), 33 byte
Bagaimana itu bekerja
sumber
Pendahuluan , 12 byte
Ini mengasumsikan seorang juru bahasa yang membaca dan mencetak karakter. Anda dapat mengurutkannya secara online. Tapi juru bahasa itu mencetak bilangan bulat, jadi untuk setiap
0
Anda akan mendapatkan48
dan untuk masing-masing1
Anda akan mendapatkan49
sebaliknya (dan linefeed).Penjelasan
Sangat jarang Anda dapat menulis program non-sepele pada satu baris di Prelude (karena Prelude membutuhkan lebih dari satu baris untuk menyelesaikan Turing).
sumber
Perl,
2721 byteByte ditambahkan untuk
-n
bendera.Uji:
Terima kasih kepada @TonHospel untuk 6 byte!
sumber
say grep$_-chop,/../g
Menuju 93 , 16 byte
Satu liner untuk kekompakan. Diuji menggunakan juru bahasa online ini .
Bagian terakhir memanfaatkan fakta itu muncul dari tumpukan Befunge-93 yang kosong menghasilkan 0 .
Jika
a != b
, kami tampilKalau tidak, jika
a == b
, kami melakukan:sumber
Pyth,
109 byteAlgoritma dicuri tanpa malu-malu dari jawaban Dennis's Jelly .
sumber
Python 2, 48 byte
Cobalah online
Terima kasih untuk Dennis dan vaultah karena menunjukkan hal-hal yang saya lewatkan
sumber
zip(*[iter(n)]*2)
Mathematica,
4139 byteKurang rumit dan lebih pendek dari jawaban lainnya. Kotak adalah karakter transpose.
sumber
JavaScript (ES6), 33 byte
Port yang membosankan dari jawaban Retina.
sumber
sed,
3433 byteUji:
sumber
fold(1)
perintah untuk berpisah. Itu juga keluar di 34!fold -s2|sed 's+01+0+p;s+10+1+p;d'
fold -s2
setara denganfold -2
, membuat 33 byte ... yang merupakan dasar dari solusi sed murni, juga. : Ps/../& /g;s/00\|11\|.\b\| //g
Labirin , 31 byte
Tidak sesingkat dan serapi solusi Sp3000, tapi saya pikir saya tetap akan memposting ini sebagai pendekatan yang berbeda:
Penjelasan
Loop pertama sederhana
yang bertuliskan dua karakter sekaligus (
"
tidak ada op). Setelah EOF,,
akan kembali-1
, tetapi hanya memeriksa EOF di setiap karakter kedua. Itu berarti dalam hal apapun bagian atas tumpukan kemudian akan menjadi-1
dan nilai di bawahnya adalah baik-1
atau beberapa kode karakter yang tidak kita pedulikan, karena itu adalah lemparan koin yang tidak berpasangan.Kemudian
)*
ubah-1
dan nilai di bawah ini menjadi tunggal0
yang kita perlukan a) untuk menyingkirkan kedua nilai tersebut dan b) untuk memasukkan loop berikutnya dengan benar. Lingkaran berikutnya itu sederhanaYang menggeser semua nilai ke tumpukan tambahan. Ini diperlukan karena kami ingin mulai memproses pasangan yang kami baca terlebih dahulu. Sekarang loop terakhir:
The
)
hanya penambahan beberapa nilai dummy untuk memastikan bahwa itu positif dan instruksi pointer bergantian utara.{
menarik digit pertama dari pasangan berikutnya dan:
menduplikatnya. Sekarang ketika kita selesai memproses, ini akan menjadi0
dari dasar tumpukan tambahan. Kalau tidak salah48
atau49
. Dalam hal nol, kita keluar dari loop dan berakhir@
, jika tidak, IP berbelok ke timur.{
menarik digit lain dari pasangan saat ini.$
mengambil XOR di antara mereka. Jika itu 0, yaitu keduanya sama, IP hanya terus bergerak ke selatan,;
membuang nol, dan IP berubah ke barat ke iterasi berikutnya. Jika XOR itu1
, yaitu mereka berbeda, IP berubah menjadi barat, membuang1
dengan;
dan mencetak digit pertama dengan.
.sumber
MATL ,
1198 byteInput dan output adalah angka yang dipisahkan oleh baris baru. Berakhir dengan kesalahan (diizinkan secara default) ketika semua input telah dikonsumsi.
Cobalah online!
Pendekatan lama, 11 byte
Input adalah sebuah string. Output adalah angka yang dipisahkan oleh baris baru.
Cobalah online!
sumber
Ruby, 46 byte
Ini memisahkan
l[0]
,l[1]
danl[2..{end}]
sebagaia
,b
danc
. Kemudian ia menciptakan string dengana
jikaa!=b
atau''
sebaliknya danf[c]
jikac[0]
ada atau''
sebaliknya.Tidak Disatukan:
sumber
brainfuck, 33 byte
Dibandingkan dengan Jawa, ini sangat ringkas, namun, saya takut dengan penjawab brainfuck-pegolf. Dan jangan ragu untuk menyebutkan jika ada bug. Dengan asumsi EOF adalah 0, input tidak mengandung input yang tidak valid, sel awalnya nol, dan rentang nilai sel terbatas dan siklik. Tidak ada asumsi lain.
Penjelasan:
Peta Sel Memori
Petunjuk
sumber
Mathematica, 41 byte
Fungsi anonim yang input dan output daftar nol dan yang.
sumber
#&@@a
lebih pendek 1 byte daria[[1]]
.RuleDelayed
.Transpose
:(Pyth, 10 byte
Suite uji
sumber
!q
dengann
lalu filterfnFT
dengannF#
. (hMnF#cz2
; ini adalah hal yang saya pikirkan ketika saya melihat tantangan, tetapi milik Anda cukup dekat bagi saya untuk tidak mempostingnya secara terpisah)1
C, 66 byte
Asumsi
sizeof(int) == sizeof(char *)
"pintar" solusi -
8481 byteBekerja pada mesin little-endian dengan asumsi
short
2 byte. Masukan diberikan sebagai argumen. Program ini mengulangi pasangan karakter dan mencetak 0 untuk 0x3130 dan 1 untuk 0x3031. Pada big-endian hasilnya akan terbalik (ganti48|c&1
dengan49^c&1
untuk memperbaikinya).sumber
C, 57 byte
Kami sementara menyalin karakter dari input
p
ke hasilr
, tetapi hanya memajukanr
pointer jika berbeda dari karakter berikutnya. Jika tidak, maka kami akan menimpanya di pasangan yang tidak cocok berikutnya, atau denganNUL
di akhir.Program uji:
Hasil tes:
sumber
Befunge-93 , 40 byte
Anda bisa mencobanya di sini . Tempel kode di ruang di bawah tombol "tampilkan", tekan "tampilkan", tentukan input, tekan "jalankan". Kami menggunakan tombol "langkah" untuk melihat cara kerja program.
sumber
DOS / Windows Batch,
201162 byteInput adalah string yang dipisahkan ruang, misalnya
1 0 0 1 1
. Mulai dari cmd, jika tidak layar segera keluarsumber
lilin lebah ,
4535 byteSaya bisa menurunkannya dengan 10 byte — tidak terlalu buruk.
Saya mengambil bacaan penuh dengan pendekatan lemparan koin , yang membuat program ini cukup besar. Hanya dengan membaca bilangan bulat satu per satu akan membuat program lebih kecil — mungkin sekitar 22 byte atau lebih — tetapi juga sangat tidak nyaman untuk digunakan.
Contoh:
Gudang lilin GitHub saya.
Contoh lilin lebah saya di Rosetta Code.
sumber