Anda adalah geek pemrograman muda yang tinggal bersama 2 teman terbaik Anda. Setiap minggu, salah satu dari Anda harus melakukan semua pekerjaan rumah dan Anda memutuskan giliran siapa dengan mengambil tongkat. Orang yang mengambil tongkat terpendek akan kalah dan mengerjakan semua tugas.
Karena Anda semua adalah programmer dan suka membuat puzzle, Anda telah memodifikasi "Pilih tongkat terpendek" menjadi puzzle komputer.
Inilah aturan teka-teki.
- Anda akan diberikan matriks 2D, di mana setiap kolom mewakili tongkat.
- Di setiap kolom, 1 mewakili sebagian dari tongkat dan 0 adalah ruang kosong
- Ketika pergi dari atas ke bawah di setiap kolom, awalnya Anda miliki
0
dan segera setelah Anda menekan1
, tongkat sudah mulai dan sisa kolom akan diisi1
hanya dengan - Anda dapat menulis program Anda untuk memilih satu kolom. Ukuran tongkat di kolom itu menentukan pemenang / pecundang. Ukuran tongkat == jumlah 1s di kolom itu.
- Namun, program itu hanya dapat memiliki kompleksitas waktu terburuk linier.
Karena Anda semua adalah pemrogram, Anda akan tahu jika program orang lain merekam batas kompleksitas waktu.
Tugas Anda adalah:
- Tulis program atau fungsi yang menerima input baik dalam format 2D atau array string.
- Input dapat diambil dari STDIN / prompt / console atau argumen fungsi.
- Jika Anda membaca input dari STDIN / prompt maka Anda dapat mengasumsikan bahwa membaca input dan mengubahnya menjadi array membutuhkan waktu 0 (walaupun kode untuk melakukannya harus ada di jawaban Anda)
- Tentukan kolom dengan tongkat terpanjang di dalamnya.
- Output dapat berupa nilai pengembalian fungsi atau ke STDOUT / konsol / peringatan.
- Program / fungsi harus memiliki kompleksitas linear waktu terburuk, di
O(m+n)
manam
adalah jumlah baris dann
jumlah kolom.
Input dapat berupa salah satu dari format berikut:
Array 2D:
[ [0, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 1, 1] ]
Array of Strings:
[ "0000", "1000", "1101", "1111" ]
Input akan memiliki properti berikut:
- Ukuran array tidak diketahui, asumsikan persegi panjang dengan ukuran berapa pun
- Di kolom mana pun, datang dari atas ke bawah, jika Anda melihat angka 1, maka semua yang di bawah ini adalah satu
- Kosong-kolom (yaitu 0-panjang) tongkat yang diperbolehkan.
Ini adalah kode-golf sehingga kode terpendek menang ! *
Tolong jelaskan kode Anda, atau berikan versi yang tidak disatukan (untuk memverifikasi kompleksitas waktu) bersama dengan dua format input yang Anda harapkan.
UPDATE Kompleksitas waktu linear di sini berarti O (n + m) di mana n adalah ukuran kolom dan m adalah ukuran baris. (Bagi mereka yang tidak jelas)
UPDATE 2 Ini pasti bisa dilakukan dalam waktu linier. Dan jika Anda memposting jawaban, jangan ragu untuk menunda pengiriman logika / algoritma beberapa hari untuk pertarungan yang adil :)
UPDATE 3 Saya akan membahas semua jawaban dalam beberapa jam untuk memvalidasi kompleksitas waktu dan program :)
sumber
1
dalam input adalah sel terakhir lalu perlu membaca seluruh input. Bahkan jika perpustakaan standar bahasa memalsukan akses acak ke stdin, di bawah layar itu buffering dan jadi waktu yang diambil adalah Omega (n * m).Jawaban:
GolfScript, 45 karakter
Mengambil input sebagai larik string, mengembalikan indeks kolom tertinggi (berbasis 0). Ini berjalan dalam iterasi O ( baris + kolom ), dan setiap iterasi harus mengambil waktu yang pada dasarnya konstan (setidaknya dengan asumsi aritmatika waktu konstan). Satu-satunya operasi array / string yang dilakukan dalam loop adalah pencarian elemen (
=
) dan mengambil panjang string (,
), yang keduanya membutuhkan waktu konstan dalam GolfScript.Cobalah online.
Penjelasan:
Seperti kebanyakan solusi di sini, kode ini bekerja dengan mulai dari sudut kiri bawah matriks, berjalan ke atas atau ke kanan tergantung pada apakah elemen saat ini dari matriks adalah 1 atau 0, dan melacak kolom di mana terakhir dipindahkan ke atas .
Pada awal program, saya menetapkan array input ke variabel
^
, panjangnya (yaitu jumlah baris)y
, dan 0 untukx
. Nilai 0 juga tersisa di tumpukan; selama loop berikutnya, itu akan digantikan oleh indeks kolom tertinggi.Di dalam loop utama,
^y(=x=
ekstrakx
karakter -th dariy-1
baris -th di^
. Ini sebenarnya mengembalikan kode ASCII dari karakter, sehingga2%
diperlukan untuk menghapus semua kecuali bagian terakhir. Sebagai kasus khusus, jikay
sama dengan 0 (yang dapat terjadi jika kolom tertinggi yang ditemukan sejauh ini mencapai semua jalan ke baris atas), bit yang dicari akan benar-benar datang dari baris terakhir dalam matriks (indeks -1), tetapi berikut iniy*
memaksa ke nol, sehingga secara efektif membuat virtual all-zero row di bagian atas matriks.Berikut ini
if
akan menjalankan salah satu dari dua blok kode yang mendahuluinya, tergantung pada apakah bit yang dicari adalah non-nol (benar) atau nol (salah). Jika bukan nol,y
dikurangi dengan satu, dan nilai saat inix
menggantikan indeks kolom tertinggi pada tumpukan (dengan nilai lama dibiarkan sementara di atasnya). Jika nol,x
ditambahkan secara bertahap oleh satu (dan sementara dibiarkan di tumpukan, di atas indeks kolom tertinggi).Akhirnya,
^0=
ekstrak baris pertama dari matriks,,
kembalikan panjangnya, dan<
bandingkan dengan indeks kolom yang ditinggalkan sementara di tumpukan (yang akan samax
jika hanya bertambah). Jika indeks kurang dari panjang baris, loop mengulangi.Ps. Berdasarkan pengujian saya, seharusnya dimungkinkan untuk mempersingkat program ini dengan satu karakter dengan mengganti tes panjang string
,<
pada akhir loop dengan>
, yang memotong string pada indeks yang diberikan dan mengembalikan bagian akhir (yang akan kosong, dan jadi salah, di akhir loop). Namun, ketika memotong string seperti itu tampaknya diimplementasikan sebagai operasi waktu-konstan di GolfScript (atau, lebih tepatnya, di Ruby, yang mana GolfScript berjalan di atas), saya belum menemukan dokumentasi resmi yang mengatakan demikian. Agar aman, saya telah memilih untuk menampilkan versi yang sedikit lebih lama, tapi pasti O (1), di atas.sumber
Ruby,
8375686663 byteMenentukan fungsi
f
yang mengambil bentuk array 2D sebagai input.sumber
Python 2 -
71, 69, 73, 7581sumber
i
akan keluar batas jika tongkat memakan seluruh kolom?j
untuk menghitung dari0
memecah kondisi loopi*j
.C, 64 byte
Sunting: Saya mengetahui bahwa pertanyaannya menanyakan lokasi kolom terpanjang dan bukan panjangnya.
Baris pertama adalah kode golf dan sisanya adalah pemanggilan sampel.
sumber
int
tanda tangan dalam fungsi secara kebetulan atau tidak berhasil karena petunjuk di sana?C #: 236 Chars
ungolfed:
sumber
PHP 5.4 - 108 byte
(113 jika Anda memasukkan
<?php
)Format input: Array akan dibaca sebagai string JSON.
Spasi ditambahkan untuk keterbacaan - semua baris baru dan ruang utama dapat dihapus.
Versi yang diperkecil:
Semacam mencuri algoritme dari Martin di sini, tapi senang bermain-main dengan bahasa yang jarang terlihat di sini XD
sumber
$s=json_decode($argv[1]);$t=count($s)-1;
dengan$t=count($s=json_decode($argv[1]))-1;
(-3 byte).$t--
hanya akan terjadi jika kondisi terpenuhi.Cobra - 98
sumber
C ++ :: 78
Berbeda dengan solusi C lainnya, ini adalah keseluruhan program. (tidak perlu doa, tidak perlu memberi tahu fungsi ukuran array). Sayangnya ini berarti lebih lama daripada
main
harus digunakan alih-alih nama fungsi karakter tunggal, saya harus menginterpretasikan input dan kemudian mengeluarkan jawabannya, di mana solusi lain menangani itu "di tempat lain". Juga golf kode pertama saya.dikompilasi dengan
g++ file.cpp -include iostream
, dijalankan dengan./a 000 010 110 111
(misalnya) == array string (saya yakin ini diperbolehkan dalam spec pertanyaan)Versi di atas menampilkan yang terbaik saat ini ditemukan sejauh ini pada setiap iterasi. Digit hasil akhir adalah jawabannya. Beralih dari pemrosesan dari kiri bawah, bukan kanan bawah dan
0
pengindeksan mengurangi solusi ini dengan 10 (!) Karakter.beralih ke c ++ menjatuhkan pengajuan oleh satu karakter lagi karena
std::cout<<
lebih pendek dariputchar(-48)
dan itu juga harus secara eksplisit mendukung lebih dari 9 tongkat dengan output yang tepat (meskipun mungkin lebih sulit untuk membedakan setiap output)Menghapus bidang jawaban dan mengeluarkannya langsung memotong 6 karakter lain. Sekarang hanya menampilkan yang terbaik saat ini ketika bergerak ke atas yang memotong setidaknya beberapa keluaran.
Seluruh file sekarang hanya berukuran 78 byte - mendekati solusi fungsi saja yang lain
C
penggunaan pengiriman. (dengan banyak kode tambahan untuk mendukung fungsi tersebut).Seperti uraian di bawah sudah kedaluwarsa:
Bisakah saya bermain golf ini lebih jauh?
Kode tidak digabungkan (dengan output ekstra):
sumber
OCaml - 144 karakter
Mengambil
int array array
input sebagai, dan mulai dari kiri bawah, bergerak ke atas atau ke kanan jika melihat a1
atau a0
. Hitungan kolom dimulai pada0
.Pemakaian
Tidak disatukan
sumber
T-SQL -
7164Mengambil tabel A sebagai input
Dan pertanyaannya adalah
SQLFiddle
Ini mengembalikan baris pertama dari tabel a diurutkan oleh r di mana ada 1 dalam string a.
TOP(1)
membatasi hasil ke baris pertama yang dikembalikan.CHARINDEX('1',A)
mengembalikan posisi 1 pertama dalam string atau nol jika tidak ditemukan.WHERE A LIKE'%1%'
filter ke baris di mana A berisi 1ORDER BY R
memastikan tabel dibaca dari atas ke bawahsumber
Delphi 122 karakter
Huh ... itu bahasa yang sangat banyak.
Pembaruan: harus menambahkan 6 karakter dalam fungsi berubah jenis kembali dari I ke integer. Fungsi masih dikompilasi sebagai program uji memiliki "tipe I = integer;" pernyataan yang tersisa dari versi program sebelumnya.
sumber
"0000", "0010", "1111"
:, kedua, jawaban Anda tidak memenuhi persyaratan kompleksitas waktu linierskema - 236 karakter
Bahkan lebih lama daripada versi delphi ... mungkin ada cara untuk melakukan ini jauh lebih efisien dengan skema. Dan lebih buruk lagi - saya hanya memperhatikan bahwa ini adalah pesanan m * n.
l adalah daftar formulir '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))). Saya pikir itu adalah representasi adil dari input array 2D untuk skema.
(sl) menjumlahkan elemen ke-n dari masing-masing sub-daftar dari daftar daftar orang-orang yang berselisih, jadi (s '((0 0 0 0) (1 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) akan kembali (3 2 1 2).
(ul) mengembalikan 'indeks' dari entri terbesar dari daftar angka (menggunakan fungsi pembantu t), jadi (u '(3 2 1 2)) akan mengembalikan 1 (sebagai elemen terbesar' 3 dalam daftar ' (3 2 1 2) ada di posisi 1).
sumber
Racket 70
Golf:
Asumsikan input adalah array dua dimensi, yang dalam Racket akan menjadi daftar daftar:
Tidak Disatukan:
Mengembalikan indeks kolom dengan tongkat terpanjang.
sumber
1
?1
dalam matriks, atau hanya di baris bawah).JavaScript, ES6, 76 karakter
Mengambil input array array.
sumber
JavaScript ES6, 65 byte
Mengambil kedua format input
Dijelaskan:
Iterasi dari bawah ke atas. Menggunakan
String.prototype.indexOf()
atauArray.prototype.indexOf()
bergantung pada input pada setiap nilai. Menemukan indeks pertama dari setiap baris dengan 1 dari offset sebelumnya, jika tidak menemukan satu pun maka ia menetapkant
variabel ke offset terakhir dan tidak melakukanindexOf
panggilan lagi .sumber
indexOf
berfungsi dalam salah satuO(log n)
atauO(n)
, sehingga algoritme keseluruhan tidak akan pernah adaO(m + n)
O(m+n)