Tantangan ini sebagian merupakan tantangan algoritma, sebagian tantangan optimasi dan sebagian hanya tantangan kode tercepat.
Matriks AT sepenuhnya ditentukan oleh baris r
pertama dan kolom pertama c
. Setiap elemen yang tersisa dari matriks hanyalah salinan dari elemen yang diagonal ke atas dan ke kiri. Yaitu M[i,j] = M[i-1,j-1]
. Kami akan memungkinkan matriks T yang tidak persegi. Namun kami selalu menganggap bahwa jumlah baris tidak lebih dari jumlah kolom. Sebagai contoh, perhatikan 3 oleh 5 T matriks berikut.
10111
11011
11101
Kami mengatakan sebuah matriks memiliki properti X jika berisi dua set kolom yang tidak kosong dengan indeks tidak identik yang memiliki jumlah (vektor) yang sama. Jumlah vektor satu atau lebih kolom hanyalah penjumlahan elemen dari kolomnya. Itu adalah jumlah dari dua atau lebih kolom yang mengandung x
elemen masing-masing adalah kolom lain yang mengandung x
elemen. Jumlah dari satu kolom adalah sepele dari kolom itu sendiri.
Matriks di atas sepele memiliki properti X karena kolom pertama dan terakhir adalah sama. Matriks identitas tidak pernah memiliki properti X.
Jika kita hanya menghapus kolom terakhir dari matriks di atas maka kita mendapatkan contoh yang tidak memiliki properti X dan akan memberikan skor 4/3.
1011
1101
1110
Tugas
Tugasnya adalah menulis kode untuk menemukan matriks T skor tertinggi dengan entri biner dan yang tidak memiliki properti X. Untuk kejelasan, sebuah matriks dengan entri biner memiliki properti yang masing-masing entrinya adalah 0 atau 1.
Skor
Skor Anda akan menjadi kolom jumlah dibagi dengan jumlah baris dalam matriks skor terbaik Anda.
Tie Breaker
Jika dua jawaban memiliki skor yang sama, jawaban yang pertama menang.
Dalam hal (sangat) tidak mungkin bahwa seseorang menemukan metode untuk mendapatkan skor tanpa batas, bukti valid pertama dari solusi semacam itu akan diterima. Dalam acara yang bahkan lebih tidak mungkin bahwa Anda dapat menemukan bukti optimalitas dari matriks yang terbatas saya tentu saja akan memberikan penghargaan juga.
Petunjuk
Semua jawaban di Temukan matriks skor tertinggi tanpa properti X valid di sini tetapi tidak optimal. Ada T matriks tanpa properti X yang tidak siklik.
Sebagai contoh, ada 7 oleh 12 T matriks tanpa properti X tetapi tidak ada matriks siklik tersebut.
21/11 akan mengalahkan semua jawaban saat ini dari tantangan ini dan sebelumnya.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga tersedia secara bebas untuk Linux.
Bonus Jawaban pertama dengan skor lebih besar dari 2 mendapat hadiah langsung 200 poin . Ton Hospel sekarang telah mencapai ini!
Papan pemimpin saat ini
- C ++ . Skor 31/15 oleh Ton Hospel
- Jawa . Skor 36/19 oleh Peter Taylor
- Haskell . Skor 14/8 oleh alexander-brett
sumber
Jawaban:
C ++, Skor
23/1225/1327/1428/1431/15Akhirnya hasil dengan rasio> 2:
Saya benar-benar menjelajahi 1 hingga 14 baris. 15 akan terlalu lama untuk dijelajahi sepenuhnya. Hasilnya adalah:
Kode yang diberikan di bawah ini adalah versi program yang lebih lama. Versi terbaru ada di https://github.com/thospel/personal-propertyX .
sumber
Haskell 14/8 = 1.75
Sebelumnya 9/6 = 1,5
Saya menulis ini, kemudian melihat jawaban untuk pertanyaan lain dan ... berkecil hati.
sumber
main
, bilangan (dalam hal ini8
) adalah ketinggian dari matriks, dan program iterasi melalui lebar[1..]
. Untuk setiap kombinasi tinggi / lebar, ia mencetak array kolom dari matriks yang valid.C
Inilah jawaban yang berfungsi dan secara signifikan lebih efisien-memori daripada Haskell. Sayangnya, komputer saya masih terlalu lambat untuk mencapai yang lebih baik dari 14/8 dalam jangka waktu yang wajar.
Coba kompilasi dengan
gcc -std=c99 -O2 -fopenmp -o matrices.exe matrices.c
dan jalankan denganmatrices.exe width height
atau serupa. Outputnya adalah integer, bit-bit yang membentuk dasar untuk matriks yang dimaksud, misalnya:Kemudian, karena
1650223 = 0b110010010111000101111
, matriks yang dimaksud adalah:Jika seseorang dengan 8 core dan waktu ingin menjalankan ini untuk sementara waktu, saya pikir beberapa hal baik dapat terjadi :)
sumber
valid i: 7481
. Dalam python bin (7481) adalah 0b1110100111001 yang tidak cukup panjang. Adakah yang tahu apa yang sedang terjadi?