Menjelajahi xorspace

14

The xorspace dari himpunan bilangan bulat adalah himpunan semua bilangan bulat yang bisa diperoleh dengan menggabungkan bilangan bulat dimulai dengan operator bitwise XOR biasa ( ^). Sebagai contoh, xorspace dari (8, 4)adalah (0, 4, 8, 12): 0 adalah 4 ^ 4, 12 adalah 4 ^ 8, dan tidak ada nomor lain yang dapat dihubungi. Perhatikan bahwa angka awal selalu dimasukkan, dengan definisi ini (misalnya, 4 adalah 4 ^ 4 ^ 4).

Tujuan Anda adalah menulis program terpendek yang mengambil daftar bilangan bulat non-negatif sebagai input, dan menampilkan jumlah elemen di xorspace mereka.

  • Celah standar dilarang.
  • Input dan output dapat dalam format yang biasa . Masukan dijamin valid, tidak kosong, dan tanpa duplikat.
  • Kode Anda harus dapat memproses semua kasus uji dalam waktu kurang dari sehari .

Uji kasus

Input: 0
Output: 1

Input: 6
Output: 2

Input: 8 4
Ouput: 4

Input: 0 256
Output: 2

Input: 256 259 3
Output: 4

Input: 60 62 94 101 115
Output: 32

Input: 60 62 94 101 115 40 91
Output: 32

Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Output: 64

Input: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Output: 32768
Grimmy
sumber

Jawaban:

2

Pyth, 8 byte

lu{+xM*Q

Suite uji

Penjelasan:

Untuk menghasilkan xorspace, kami menemukan fixpoint mengambil xor dari setiap pasangan angka, menambahkan setiap angka, dan menduplikasi. Kemudian, kami mengambil hasil yang panjang. Ini berjalan dalam 20 detik (hanya offline) pada test case akhir.

lu{+xM*Q
lu{+xM*QGGQ    Implicit variable introduction
 u        Q    Find the fixed point of the following, starting with the input,
               where the current value is G.
      *QG      Form the Cartesian product of Q (input) and G (current)
    xM         Take the xor of every pair
   +           Add the current values
  {            Deduplicate
l              Output the length of the result.

Dikemas Pyth , 7 byte

Hexdump:

0000000: d9d7 dabf 1355 51                        .....UQ

Sama seperti di atas, dengan pengkodean ASCII 7-bit.

Masukkan di atas dalam file dengan xxd -r, dan jalankan sebagai berikut:

py packed-pyth.py xorspace.ppyth '[256, 259, 3]'
isaacg
sumber
Saya pikir Anda bisa melakukannya l{mxFdy.
xnor
@ xnor yang yditerapkan pada kasus uji 1 hingga 63 terlalu lambat. Saya tidak memiliki memori 2 ^ 63.
isaacg
10

MATL , 11 byte

t"G!Z~Ghu]n

Cobalah online!

Kasing uji terakhir tidak berjalan pada juru bahasa online karena keterbatasan memori, tetapi beroperasi offline dalam waktu kurang dari 2 detik pada komputer modern.

Penjelasan

Untuk input ukuran n, ini melakukan hal berikut:

  1. Inisialisasi hasil untuk input.
  2. Ulangi nkali:
    1. Terapkan bitor XOR ke semua pasangan entri dari hasil dan input saat ini.
    2. Lampirkan nilai input ke hasilnya.
    3. Deduplicate.
  3. Outputnya adalah jumlah elemen dari hasil akhir.

Kode yang dikomentari.

t      % Implicit input: row vector. Duplicate
"      % For each (i.e. do as many times as the input size)
  G!   %   Push input as a column vector
  Z~   %   Bitwise XOR with broadcast, i.e. for all pairs of entries of the
       %   two arguments. The first argument is the accumulated result
       %   from the previous iteration, the second is the input vector
  G    %   Push input again
  h    %   Postpend
  u    %   Unique values. Gives a row vector
]      % End
n      % Number of entries. Implicitly display

Contoh

Hasil antara (langkah 2.1 dan 2.3) untuk input [256 259 3]adalah:

Iterasi pertama: [256 259 3]dengan [256 259 3]: menghitung semua pasangan bitwise-XOR menghasilkan matriks

  0   3 259
  3   0 256
259 256   0

Melampirkan [256 259 3]dan mendeduplikasi

0 3 259 256

Iterasi kedua: hasil saat ini [0 3 259 256]dengan [256 259 3]. Setelah deduplicating ini memberi lagi

0 3 259 256

Iterasi ketiga: lagi

0 3 259 256

Jadi outputnya adalah 4(jumlah entri hasil).

Luis Mendo
sumber
Penjelasannya tolong? Anda tidak dapat menggunakan O (2 ^ n).
Erik the Outgolfer
Saya tidak tahu cara kerjanya, tapi jelas bukan O (2 ^ n). Ini benar-benar memecahkan kasus uji (1 2 3 ... 63) cukup cepat, meskipun itu adalah kasus terburuk untuk metode brute-force.
Grimmy
2
Bagaimana ini begitu cepat? Saya sudah mencoba melakukan hal yang sama di Jelly, tetapi upaya pertama terbunuh setelah 19 menit ... (Sekarang mencoba dengan lebih banyak RAM.)
Dennis
2
Saya percaya ini adalah kasus terburuk O (2ⁿ); hanya saja dalam tes yang melatihnya, n hanya 15, sehingga program masih berjalan cukup cepat.
2
@ ais523 Nomor-nomor antara yang diperoleh dari bitwise-XOR tidak akan pernah bisa lebih besar dari angka maksimum dalam input, sebut saja M. Jadi ukuran vektor hasil antara tidak pernah melebihi M, dan kompleksitasnya adalah O ( M*M). OP telah mengatakan bahwa definisi yang tepat dari ntidak masalah, jadi jika saya mendefinisikan nsebagai Msaya dapat mengklaim ini sebagai O ( n*n).
Luis Mendo
8

Haskell , 64 byte

f mengambil daftar bilangan bulat dan mengembalikan bilangan bulat.

import Data.Bits
f l|m<-maximum l,m>0=2*f(min<*>xor m<$>l)|0<1=1

Cobalah online!

Ini tidak menangani daftar kosong, untuk itu Anda bisa tetapi $0:bukan ruang setelah maximum.

Bagaimana itu bekerja

  • Jika maksimal m daftar adalah nol, mengembalikan 1.
  • Sebaliknya, atasi setiap elemen dengan maksimal.
    • Jika hasilnya lebih kecil dari elemen, elemen digantikan olehnya.
    • Ini tentu nol bit paling signifikan yang ditetapkan di mana saja dalam daftar.
    • Kemudian berulang pada daftar yang dihasilkan, menggandakan hasil rekursi.
  • Proses ini pada dasarnya melakukan eliminasi Gaussian (walaupun membuang baris terakhir dengan mengaturnya ke 0) modulo 2, pada matriks yang barisnya merupakan representasi bit dari daftar angka. Himpunan representasi bit dari "xorspace" adalah ruang vektor modulo 2 yang direntang oleh baris-baris matriks ini, dan yang jumlah elemennya 2 pangkat pangkat baris matriks.
  • Algoritma ini adalah waktu polinomial, jadi pasti lebih baik daripada O (2 ^ n).
Ørjan Johansen
sumber
Ini pada dasarnya adalah algoritma yang saya pikirkan (untuk mengalahkan batas kompleksitas), meskipun ini adalah cara yang sangat elegan untuk mewakilinya. Sangat menyenangkan melihatnya dalam jawaban golf yang benar.
4

Mathematica, 52 byte

2^MatrixRank[PadLeft@IntegerDigits[#,2],Modulus->2]&
alephalpha
sumber
Mengapa Anda menghapus jawaban Pari / GP Anda? Tampaknya berfungsi dengan baik. EDIT: tidak apa-apa, sebenarnya gagal beberapa kasus uji.
Grimmy
@ Grimy Mengapa Anda menerima jawaban saya? Ini adalah kode-golf, kode terpendek menang.
alephalpha
Maaf, saya mengubah jawaban yang diterima menjadi 7 byte yang dikemas Pyth one.
Grimmy
3

05AB1E , 8 byte

vDy^ìÙ}g

Cobalah online!

Semua uji kasus selesai dalam waktu kurang dari 1 menit pada TIO.

Emigna
sumber
Ini gagal kriteria terakhir: «Kode Anda harus dapat memproses semua kasus uji dalam waktu kurang dari sehari (tanpa O (2 ** n) hal). »
Grimmy
@ Grimy: Tidak membaca 2^nbagian: /
Emigna
@ Grimy: Sekarang diperbarui untuk menyelesaikan semua kasus uji dalam waktu kurang dari 1 menit (dan dengan lebih sedikit byte digunakan)
Emigna
Berpikir âü^Ùgsampai aku melihatmu bisa lebih dari sekali, solusi yang bagus.
Magic Gurita Guci
@carusocomputing: Itu menghemat satu byte, tapi saya tidak yakin tentang kerumitannya.
Emigna
3

Python 2 , 55 byte

r={0}
for n in input():r|={x^n for x in r}
print len(r)

Cobalah online!

Mematikan fungsi:

f=lambda l,r={0}:l and f(l[1:],r|{x^l[0]for x in r})or len(r)
f=lambda l:len(reduce(lambda r,n:r|{x^n for x in r},l,{0}))

Metode penghapusan baris indah Ørjan Johansen adalah satu byte lebih pendek.

Python 2 , 54 byte

f=lambda l:1-any(l)or 2*f([min(x,x^max(l))for x in l])

Cobalah online!

Tidak
sumber
2

Jelly , 9 8 byte

0œ|⁺^¥/L

Selesaikan semua kasus uji dalam waktu kurang dari 8 detik pada TIO, dengan persyaratan memori yang dapat diabaikan.

Cobalah online!

Bagaimana itu bekerja

0œ|⁺^¥/L  Main link. Argument: A (array)

0œ|       Perform multiset union with 0, prepending 0 if A doesn't contain it.
      /   Reduce A by the link to the left.
     ¥      Combine the previous two links into a dyadic chain.
            Left argument: V (array). Right argument: n (integer)
    ^           Bitwise XOR each element in V with n.
   ⁺            This quick refers to the previous link, making it a shorthand for
                the link 'œ|'. Thus, it performs multiset union on V and the array
                of bitwise XORs.
       L  Compute the length of the result.
Dennis
sumber
1

Python, 113 byte

def f(x):
 u,s=[0],{0}
 while u:
	a=u.pop()
	for b in x:
	 c=a^b
	 if c not in s:u+=[c]
	 s.add(c)
 return len(s)
pengguna1502040
sumber
Ini bekerja, tapi saya menghitung 113 byte; apakah saya melewatkan sesuatu?
Grimmy
@ sebenarnya manusia itu mungkin karena Anda menghitung tabulasi sebagai 8 byte, bukan satu byte.
Grimmy
Jika lekukan pertama adalah spasi, yang berikutnya adalah tab, dan yang terakhir adalah tab + spasi (atau 2 tab), maka itu 113 byte
daniero
@ Grimy Sebenarnya setiap tab adalah 4 spasi bukan 8.
Erik the Outgolfer
Program lengkap akan lebih pendek, karena menghemat sedikit lekukan. Juga, loop untuk dapat diringkas menjadi satu baris, seperti u+=[c][c in s:]yang setara dengan ifpernyataan Anda .
Dennis