Pergi! No-1 di Sini!

16

Saya bermain-main dengan beberapa angka dan menemukan urutan yang, tentu saja, ada di OEIS. Ini adalah A005823 : Angka-angka yang ekspansi ternernya mengandung angka 1 . Kelanjutannya:

a (2n) = 3 * a (n) +2

a (2n + 1) = 3 * a (n + 1)

a (1) = 0

a = 0,2,6,8,18,20,24,26,54 ....

Saya menulis program CJam yang menghasilkan n pertama dari angka-angka ini dengan mengubah indeks menjadi biner, mengganti angka 1 dengan angka 2, dan mengkonversi dari ternary ke desimal.

Saya juga memperhatikan bahwa angka genap dapat diperoleh dengan mengambil jumlah dua angka dalam urutan (kadang-kadang angka itu sendiri).

Tantangan:

Dengan diberi nomor genap non-negatif sebagai input, output indeks dari dua angka dalam urutan yang menjumlahkannya. (Perhatikan bahwa terkadang beberapa pasangan dimungkinkan.)

Aturan:

  • Tentukan apakah Anda menggunakan pengindeksan 0 atau 1.
  • Jika Anda menghasilkan sebagai string, letakkan pembatas di antara kedua indeks.
  • Anda diizinkan untuk menghasilkan angka yang kompleks.
  • Jika Anda menginginkannya, Anda dapat menampilkan setiap pasangan yang valid.
  • Golf Kode: jawaban terpendek menang

Uji Kasus

Saya menggunakan pengindeksan 0. Di sini saya daftar setiap kemungkinan output untuk setiap input, tetapi Anda hanya perlu output satu.

0:       [0 0]
 2:       [1 0]
 4:       [1 1]
 6:       [2 0]
 8:       [2 1] [3 0]
 10:      [3 1]
 12:      [2 2]
 14:      [3 2]
 16:      [3 3]
 18:      [4 0]
 30:      [6 2]
 32:      [6 3] [7 2]
 46:      [7 5]
 50:      [7 6]
 120:     [10 10]
 338:     [19 18]
 428:     [30 23] [31 22]
 712:     [33 27] [35 25] [41 19] [43 11] [51 9] [57 3] [59 1]
 1016:    [38 37] [39 36]
Terima kasih kepada @Luis Mendo untuk bantuan uji kasus.

Terkait: Apakah itu dalam set Cantor?

geokavel
sumber
Bisakah kita menampilkan angka kompleks dari kedua nilai? Bisakah kita menyediakan dua fungsi, satu memberikan nilai masing-masing?
xnor
2
Bisakah kita mengeluarkan semua nilai yang mungkin, atau apakah itu melampaui tantangan?
cole
@ole Ya, tidak apa-apa.
geokavel
Tampaknya Tuan Sloane sangat menyukai urutan nomornya. "Ada urutan untuk itu" (TM)
Pharap
1
Karena ada beberapa solusi untuk beberapa input, alangkah baiknya untuk memasukkan semua solusi dalam test case. Program ini menunjukkan semua pasangan solusi untuk setiap test case, dalam format yang sama seperti pada teks tantangan (berbasis 0, masing-masing pasangan semakin disortir)
Luis Mendo

Jawaban:

10

Sekam , 21 14 13 byte

-7 byte, terima kasih untuk jawaban JS @ Neil

-1 byte terinspirasi oleh jawaban Parradoc betaveros

Menggunakan pengindeksan 0

mḋTmMo±>ḋ2B3½

Cobalah online!

Penjelasan

            ½    Half the input
          B3     Convert to Base 3
   m             Map over the list
    Mo±>ḋ2       Function such that: 0 -> [0,0], 1 -> [0,1], 2 -> [1,1]
        ḋ2       Binary 2, [1,0]
    M            For each in that list
     o±>         check if the argument is greater than it
  T              Transpose
mḋ               Convert each from binary

Solusi 21 byte sebelumnya

Pertama kali saya melihat ada gunanya ».

mḋT»o%2+ȯ?´eḋε%3`-0B3

Cobalah online!

Lebih lama, karena saya berurusan dengan membawa

H.Piz
sumber
8

JavaScript (ES6), 75 71 byte

f=
n=>[1,0].map(i=>parseInt((n/2).toString(3).replace(/./g,c=>+c+i>>1),2))
<input type=number min=0 step=2 oninput=o.textContent=this.value%2?``:f(this.value)><pre id=o>

Penjelasan: Membagi input dan elemen-elemen A005823 dengan 2 tidak mengubah masalah, namun itu membuat solusi lebih sederhana karena representasi ternary sekarang hanya menggunakan 0s dan 1s dan oleh karena itu tidak ada carry untuk dipertimbangkan. Ia juga menyimpan langkah ketika mengkonversi dari elemen ke indeksnya (setiap terner elemen adalah dua kali biner dari indeksnya). Contoh:

                 A005823
                  halved
            n in  values A005823
   n n/2  base 3  base 3 indices
   0   0       0   0   0   0   0  
   2   1       1   1   0   1   0
   4   2       2   1   1   1   1
   6   3      10  10   0   2   0
   8   4      11  11   0   3   0
  10   5      12  11   1   3   1
  12   6      20  10  10   2   2
  14   7      21  11  10   3   2
  16   8      22  11  11   3   3
  18   9     100 100   0   4   0
  30  15     120 110  10   6   2
  32  16     121 111  10   7   2
  46  23     212 111 101   7   5
  50  25     221 111 110   7   6
Neil
sumber
6

Jelly , 26, 22 , 21 byte

ḶBḤḅ3
ÇŒcS=¥Ðf⁸ḢiЀÇT

Cobalah online!

Satu byte disimpan berkat @JonathanAllan!

Penjelasan:

                # Helper link: A005823 to *N* terms
Ḷ               # Lowered range(N)
 B              # Converted to binary
  Ḥ             # Double each digit
   ḅ3           # Converted from base 3 to decimal
                # Main link
Ç               # Last link
 Œc             # All combinations of 2 items (with replacement)
      Ðf        # Remove every combination where this isn't true:
   S=¥          #   The sum of the two items is equal to N
        ⁸Ḣ      # Take the first combination left
          i     # Index of
           Ѐ   # Each element of the combination
             Ç  # In the sequence
              T # Return the truthy indices
DJMcMayhem
sumber
1
@ Jonathan Allan Oh, senang tahu tentang Œc. Dan ya, Dennis menjelaskan masalahnya S=¥kepada saya.
DJMcMayhem
Sepertinya Anda perlu menambahkan case-edge handling dengan nol :(
Jonathan Allan
Sepertinya ini berbasis 1; mungkin ada baiknya menyatakannya dalam jawaban
Luis Mendo
20 byte
dylnan
3

Python 2 , 51 byte

f=lambda n:[n and(n/2%3>r)+2*f(n/3)[r]for r in 0,1]

Cobalah online!

Tugas dapat dilakukan seperti ini:

  1. Membagi dua input
  2. Konversikan ke daftar ternary
  3. Membaginya menjadi dua daftar biner yang menjumlahkan elemen untuknya
  4. Ubah daftar itu dari biner

Kita dapat melakukan pemisahan dalam (3) dengan mengonversi 0->0,1->1,2->1untuk satu daftar dan 0->0,1->0,2->1untuk yang lainnya. Artinya, dengan memeriksa apakah nilainya di atas ambang 0 atau 1.

Dua nilai dapat ditemukan oleh fungsi rekursif masing-masing:

p=lambda n:n and(n/2%3>0)+2*p(n/3)
q=lambda n:n and(n/2%3>1)+2*q(n/3)

Fungsinya f menggabungkan keduanya dalam daftar pemahaman. Ini membuatnya tidak efisien karena percabangan eksponensial.

Jika bilangan kompleks bisa menjadi keluaran, kita bisa menghemat 10 byte dengan:

f=lambda n:n and(n%6>1)+n%6/4*1j+2*f(n/3)
Tidak
sumber
Saya kira bilangan kompleks itu ok.
geokavel
3

J, 35 32 byte

($#:I.@,)@(=[:+/~3#.+:@#:@i.@>:)

Cobalah online!

Diindeks 0 dan input diberikan secara monadik. Mengembalikan semua penjumlahan yang mungkin ke nilai (itu memperlakukan a bdan b asebagai penjumlahan yang mungkin berbeda).

Mengubah dari matriks boolean ke indeks membutuhkan banyak kode ...

Saya juga ingin menghapus garpu di sebelah kiri jadi saya tidak harus menggunakan banyak tanda kurung dan @-ats, tapi saya tidak tahu cara yang baik untuk melakukannya (pendekatan alternatif saya tidak menyimpan byte apa pun ).

Penjelasan

Untuk tujuan menjelaskan dan ungolfing, pertimbangkan komponen fungsi utama berikut

valid_nums      =. = [: +/~ 3 #. +:@#:@i.@>:
indices_of_ones =. $ #: I.@,

valid_nums menghasilkan matriks boolean di mana indeks adalah indeks dari nilai urutan yang dijumlahkan. Jika ada satu di indeks itu, itu berarti bahwa kedua angka dijumlahkan ke nilai input.

indices_of_ones adalah idiom J untuk memberikan koordinat koordinat dalam matriks boolean rank sewenang-wenang

Fungsi utama terdiri cukup sederhana

indices_of_ones@valid_nums

valid_nums

= [: +/~ 3 #. +:@#:@i.@>:  Input is n
                 #:@i.@>:  Binary numbers in range [0,n]
              +:           Doubled
         3 #.              Interpreted as ternary
     +/~                   Addition table with self (sum all possible pairs)
=                          Equate to n

indexes_of_ones

$ #: I.@,
        ,  Ravel matrix into a single list
     I.    Find the indices of ones in that list
  #:       Convert to the base given by
$          The shape of the matrix

,-perjalanan bekerja dalam hal ini dengan bergabung setiap baris ke yang berikutnya.

   i.3 3
0 1 2
3 4 5
6 7 8
   , i.3 3
0 1 2 3 4 5 6 7 8

Kita dapat melihat bahwa jika ini adalah matriks boolean, koordinat yang dapat ditemukan dengan menginterpretasikan indeks matriks yang di-raveled sebagai angka-angka di dasar bentuk matriks itu menggunakan sebanyak mungkin frasa preposisional untuk membingungkan para pembaca miskin. .

cole
sumber
1
output berlebihan Anda ok.
geokavel
3

MATL , 22 21 19 17 byte

tQ:qBEI_ZA&+=R&fh

Output berbasis 1. Program ini menghasilkan semua pasangan solusi. Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

t      % Implicit input: n. Duplicate
Q:q    % Range [0 1 ... n]
B      % Convert to binary. Gives a matrix where each row corresponds to a number
E      % Multiply each entry by 2
I_ZA   % Convert each row from ternary to a number
&+     % Matrix of all pair-wise additions
=      % Does each entry equal n?
R      % Upper triangular matrix
&f     % Push row and column indices of nonzero entries
h      % Concatenate horizontally. Implicit didsplay
Luis Mendo
sumber
OP mengatakan bahwa memproduksi semua solusi adalah OK dalam komentar
H.PWiz
@ H.PWiz Terima kasih! Saya belum melihat itu
Luis Mendo
2

Pyth , 37 byte

Diindeks 0

Tentu saja tidak bermain golf sebaik mungkin.

KUQJmi:.Bd\1\23KhfqQ+@JeT@JhTsmm,dkKK

Cobalah online!

Cowabunghole
sumber
1
34 byte: hfqQ+@Jmi:.Bd\1\23QeT@JhTsmm,dkUQU. Pasti bisa
bermain golf
1
33 byte:hfqQ+@Jmi:.Bd\1\23QeT@JhTsmm,dkUQ
Mr. Xcoder
2

Pyth , 29 byte

Yang ini mengembalikan semua pasangan indeks yang memungkinkan.

fqQ+@Kmi:.Bd\1\[email protected]

Coba di sini.

Pyth , 30 byte

hfqQ+@Kmi:.Bd\1\[email protected]

Coba di sini.

Ini mengembalikan pasangan indeks sebagai [LowerIndex, HigherIndex].


Bagaimana cara kerjanya?

hfqQ+@Kmi:.Bd\1\[email protected]   Full Program. Q means input throughout the whole explanation.

       m          Q               Map over the range [0, Q) with a variable d.
          .Bd                     Convert to binary.
         :   \1\2                 Replace 1 with 2.
        i        3                Convert it from base 3 to integer.
      K                           Assign the mapped range to a variable K.
                         .cUQ2    All possible two-element combinations of the range [0...Q).
    +@             hT@KeT         Sum of the integers on positions in K of the two-element
                                  combination.
 fqQ                              Filter those that equal the input.
h                                 Optional: Head. Take the first element.
                                  Print the result, implicitly. 
Tuan Xcoder
sumber
2

Paradoc (v0.2.10), 11 byte (CP-1252)

½3B2>_B™2Bv

Cobalah online!

Secara algoritma ini sangat mirip dengan jawaban ES6 Neil . Pada tingkat yang lebih rendah, juga sangat mirip dengan jawaban Husk H.PWiz . Saya senang bahwa kami harus menggunakan ketiga kelebihan B.

Mengambil bilangan bulat di tumpukan, meninggalkan daftar dua bilangan bulat di tumpukan.

Penjelasan:

½           .. Halve input
 3B         .. Convert to ternary
   2        .. 2, which will get implicitly coerced to [0,1]
    >_      .. Greater than, as a block
      B     .. "Bimap": take the block and map it over the Cartesian
            .. product of the last two lists to get a matrix
       ™    .. Transpose
        2Bv .. Convert each row from binary
betaveros
sumber
1

Python 3 , 122 120 byte

-2 byte terima kasih kepada Tn. Xcoder!

Diindeks 0

def f(a):r=range(a);s=[int(bin(x)[2:].replace(*'12'),3)for x in r];return[(i,j)for i in r for j in r if s[i]+s[j]==a][0]

Tidak Terkumpul:

def f(a):
    r=range(a)
    s=[int(bin(x)[2:].replace(*'12'),3)for x in r]
    return[(i,j)for i in r for j in r if s[i]+s[j]==a][0]

Cobalah online!

Cowabunghole
sumber
1
Semoga kau tidak keberatan. Saya menambahkan tautan TiO.
Tn. Xcoder
1

Mathematica, 94 byte

(w=#;Position[s,#]&/@#&@@(k=Select)[Tuples[s=k[Range@w,DigitCount[#,3,1]==0&],{2}],Tr@#==w&])& 


1-diindeks

J42161217
sumber
1

JavaScript, 120 101 byte

n=>[(A=[...Array(n+1)].map(Z=(a,b=a)=>b&&3*Z(b/2|0)+b%2*2))[F='findIndex'](a=>z=~A[F](b=>a+b==n)),~z]

Cobalah online!

Diindeks 0.
Ini mengembalikan pasangan indeks di mana satu indeks adalah yang terkecil yang mungkin (misalnya dalam kasus 428itu kembali 22,31).


sumber
1

Brain-Flak , 220 166 byte

-54 byte dengan mencari fungsi modulo pada wiki, memungkinkan beberapa perubahan struktural

({()<({}[()()])>}{}){({}(<>))<>(()()())({()<(({})){({}[()])<>}{}>}{}<><([{}()]{})>[()])}([]){{}<>(({}){})<>(({}){}{()<({}[()]){<>({}())<>(<{}>)}>}{})([][()])}({}{}<>)

Cobalah online!

Diindeks 0.

Penjelasan

Seperti banyak solusi lain, ini menghitung ekspansi ternary dari n/2 dan mengubahnya menjadi dua angka biner.

Langkah 1: Bagi input dengan 2

({()<({}[()()])>}{})

 {              }     until number becomes zero:
     ({}[()()])       subtract two
( ()<          > {})  push number of iterations

Langkah 2: hitung ekspansi terner

{({}(<>))<>(()()())({()<(({})){({}[()])<>}{}>}{}<><([{}()]{})>[()])}

 ({}(<>))<>         {   (({})){({}[()])<>}{} }{}<> ([{}()]{})         modulo (from wiki)
           (()()())                                                   use 3 as base
                     ()<                    >                         evaluate as 1 every time the 3 rolls over
                   (                              <          >[()])   push number of rollovers (function is now division with remainder)
{                                                                  }  repeat until quotient is zero, leaving all remainders on stack

Langkah 3: Konversi ke solusi

([]){{}<>(({}){})<>(({}){}{()<({}[()]){<>({}())<>(<{}>)}>}{})([][()])}({}{}<>)

([]){{}                                                      ([][()])}           repeat while stack height > 1:
                                                                                 (loop happens once when initial stack height is 1, but that's fine)
       <>(({}){})                                                                double smaller output number
                 <>(({}){}                                  )                    double larger output number
                          {                              }{}                     if digit in ternary expansion is nonzero:
                           ()<                          >                        add 1 to larger output number
                              ({}[()]){                }                         if digit is 2:
                                       <>({}())<>(<{}>)                          add 1 to smaller output number
Nitrodon
sumber
0

JavaScript (ES6), 70 72 byte

n=>[6,4].map(x=>parseInt((n/2).toString(3).replace(/./g,d=>x>>d&1),2)) // thanks @Neil
n=>[0,1].map(x=>parseInt((n/2).toString(3).replace(/1|2/g,d=>~-d||x),2))

(0-diindeks, dan tampaknya solusi yang hampir sama dengan @Neil bahkan jika saya belum melihat jawabannya)

Saya mulai dengan mendapatkan kembali indeks dari angka menggunakan proses kebalikan: stringify dengan basis 3, ganti setiap 2dengan 1, parsing dengan basis 2.

Untuk mendapatkan dua angka, dan itu untuk setiap angka satu, kita hanya setengah dari input - tetapi sekarang, juga 1digit dapat terjadi. Jadi kami menggantinya dengan 0dalam satu nomor dan 2dalam nomor lainnya, yang tidak mengubah jumlah keduanya, sebelum langkah ganti dan parsing. Inilah yang saya buat (melakukan dua penggantian, 1-> 0-atau-2 dan 2-> 1dalam satu langkah):

n=>["001","011"].map(x=>parseInt((n/2).toString(3).replace(/./g,d=>x[d]),2))

Tentu saja dua peta pengganti (string) hanya berbeda dalam satu indeks, jadi kita harus dapat mempersingkat array literal dengan hanya mengganti 1 dan 2dengand == 2 ? 1 : x . Ataud-1 || x . Dimana-1 melakukan hal yang sama dengan dua operator unary - tetapi mereka terlihat lebih menakutkan :-)

Mencoba menghindari array literal dan tanda kurung di sekitar n/2 saya juga muncul

n=>Array.from(parseInt,(h=n/2,i)=>parseInt(h.toString(3).replace(/1|2/g,d=>~-d||i),2))

tapi hasilnya tidak membuahkan hasil.

Bergi
sumber
Saya mulai dengan ["001","011"]versinya juga (nah nama variabel saya berbeda)
Neil
Saya pikir .replace(/./g,d=>d>>1|x)menghemat 2 byte.
Neil
@Neil Sayangnya itu tidak berhasil d="0"dan x=1- digitnya harus tetap0
Bergi
Ya, saya baru saja menyelesaikannya setelah mencoba beberapa kasus uji lagi. (Dan saya sudah menemukan varian lain, tapi saya kira itu jawabannya.)
Neil
1
Oh sangat bagus, dan saya pikir saya pintar untuk mengalahkan versi Anda sebelumnya ...
Neil
0

Pyth, 22 byte

J.m}1jb3hQxLJhfqsTQ^J2

Cobalah online: Demonstrasi

Penjelasan:

J.m}1jb3hQxLJhfqsTQ^J2
        hQ                input + 1 
 .m                       find all values of [0, 1, 2, ..., input], where
     jb3                     value converted to base 3
   }1                        check if it contains the digit 1
                          this boolean ^ is false
J                         store this list in variable J

                   ^J2    every pair of J
              f           filter for pairs with
                sT           sum of pair
               q             equal
                  Q          the input
             h            take the first of these pairs
          xLJ             and find the corresponding indices of J
Jakube
sumber