Split bit!

17

Kami mendefinisikan V(x) sebagai daftar kekuatan 2 yang berbeda yang menjumlahkan x . Misalnya, V(35)=[32,2,1] .

Berdasarkan konvensi, kekuatan diurutkan di sini dari tertinggi ke terendah. Tapi itu tidak mempengaruhi logika tantangan, maupun solusi yang diharapkan.

Tugas

Diberikan semiprime N , ganti setiap istilah dalam V(N) dengan daftar kekuatan lain 2 yang menjumlahkan istilah ini, sedemikian rupa sehingga penyatuan semua sub-daftar yang dihasilkan adalah sampul yang tepat dari matriks M didefinisikan sebagai:

Mi,j=V(P)i×V(Q)j

dimana P dan Q adalah faktor prima dari .N

Ini jauh lebih mudah dipahami dengan beberapa contoh.

Contoh 1

Untuk N=21 , kami memiliki:

  • V(N)=[16,4,1]
  • dan V ( P ) = [ 4 , 2 , 1 ]P=7V(P)=[4,2,1]
  • dan V ( Q ) = [ 2 , 1Q=3V(Q)=[2,1]
  • M=(842421)

Untuk mengubah menjadi penutup M yang tepat , kita dapat membagi 16 menjadi 8 + 4 + 4 dan 4 menjadi 2 + 2 , sementara 1V(N)M168+4+442+21 dibiarkan tidak berubah. Jadi output yang mungkin adalah:

[[8,4,4],[2,2],[1]]

Output lain yang valid adalah:

[[8,4,2,2],[4],[1]]

Contoh # 2

Untuk , kami memiliki:N=851

  • V(N)=[512,256,64,16,2,1]
  • dan V ( P ) = [ 32 , 4 , 1 ]P=37V(P)=[32,4,1]
  • dan V ( Q ) = [ 16 , 4 , 2 , 1 ]Q=23V(Q)=[16,4,2,1]
  • M=(512641612816464823241)

Output yang mungkin adalah:

[[512],[128,64,64],[32,16,16],[8,4,4],[2],[1]]

Aturan

  • Karena faktorisasi bukan bagian utama dari tantangan, Anda dapat mengambil P dan Q sebagai input.NPQ
  • Ketika beberapa solusi yang mungkin ada, Anda dapat mengembalikan salah satu atau semuanya.
  • Anda dapat secara bergantian mengembalikan eksponen dari kekuatan (misalnya alih-alih [ [ 8 , 4 , 4[[3,2,2],[1,1],[0]] ).[[8,4,4],[2,2],[1]]
  • Urutan sub-daftar tidak menjadi masalah, juga urutan persyaratan dalam setiap sub-daftar.
  • Untuk beberapa semiprimes, Anda tidak perlu membagi istilah apa pun karena sudah merupakan sampul sempurna M (lihat A235040 ). Tetapi Anda masih harus mengembalikan daftar (tunggal) daftar seperti [ [ 8 ] , [ 4 ] , [ 2V(N)M untuk N = 15 .[[8],[4],[2],[1]]N=15
  • Ini !

Uji kasus

 Input | Possible output
-------+-----------------------------------------------------------------------------
 9     | [ [ 4, 2, 2 ], [ 1 ] ]
 15    | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 21    | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
 51    | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
 129   | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
 159   | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 161   | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
 201   | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
 403   | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 851   | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 2307  | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]
Arnauld
sumber
dapatkah kita mengambil P dan Q bukannya N?
ngn
@ Ngn Saya akan mengatakan ya, karena memfaktorkan N bukan bagian utama dari tantangan.
Arnauld
1
Bisakah kita mengembalikan hasil rata?
Erik the Outgolfer
@EriktheOutgolfer ... Output diratakan hanya partisi input (1 + 2 + 2 + 4 = 9, misalnya). Saya pikir itu tidak seharusnya diizinkan
Tn. Xcoder
@EriktheOutgolfer Saya tidak berpikir itu bisa jelas seperti ini, karena istilah terakhir dari sub-daftar mungkin sama dengan istilah pertama yang berikutnya.
Arnauld

Jawaban:

4

K (ngn / k) , 66 63 byte

{(&1,-1_~^(+\*|a)?+\b)_b:b@>b:,/*/:/2#a:{|*/'(&|2\x)#'2}'x,*/x}

Cobalah online!

menerima (P; Q) alih-alih N

algoritma:

  • hitung A sebagai jumlah parsial dari V (P * Q)

  • gandakan setiap V (P) dengan masing-masing V (Q), urutkan produk dalam urutan menurun (sebut saja R), dan hitung jumlah parsialnya B

  • menemukan posisi elemen-elemen di B yang juga terjadi di A; potong R tepat setelah posisi itu

ngn
sumber
3

Jelly , 24 byte

BṚT’2*
Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ

Tautan monadik yang menerima daftar dua bilangan bulat [P, Q]yang menghasilkan satu daftar daftar yang mungkin seperti yang dijelaskan dalam pertanyaan.

Cobalah online!(footer mencetak representasi string untuk menampilkan daftar apa adanya)

Atau lihat test-suite (mengambil daftar N dan menyusun ulang hasil menjadi seperti yang ada di pertanyaan)

Bagaimana?

Kami selalu dapat mengiris elemen dari terendah ke atas, dengan rakus (baik ada 1 di M atau kami memiliki input 4 , ketika M = [ [ 4 ] ] ) untuk menemukan solusi.M1M4M=[[4]]

Catatan: kode mengumpulkan semua (satu!) Solusi tersebut dalam daftar dan kemudian mengambil hasil head (only) - yaitu kepala akhir diperlukan karena partisi tidak dari semua kemungkinan pemesanan.

BṚT’2* - Link 1, powers of 2 that sum to N: integer, N    e.g. 105
B      - binary                                                [1,1,0,1,0,0,1]
 Ṛ     - reverse                                               [1,0,0,1,0,1,1]
  T    - truthy indices                                        [1,4,6,7]
   ’   - decrement                                             [0,3,5,6]
    2  - literal two                                           2
     * - exponentiate                                          [1,8,32,64]

Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ - Main Link: list of two integers, [P,Q]
Ç€                - call last Link (1) as a monad for €ach
    /             - reduce with:
   þ              -   table with:
  ×               -     multiplication
     F            - flatten
      Ṣ           - sort
       ŒṖ         - all partitions
              Ƈ   - filter keep if:
             ɗ    -   last three links as a dyad:
         §        -     sum each
            }     -     use right...
               P  -       ...value: product (i.e. P×Q)
           Ç      -       ...do: call last Link (1) as a monad
          ⁼       -     equal? (non-vectorising so "all equal?")
                Ḣ - head
Jonathan Allan
sumber
3

Python 2 , 261 233 232 231 byte

g=lambda n,r=[],i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Cobalah online!

1 byte dari Jo King ; dan 1 byte lagi karena Kevin Cruijssen .

Dibawa sebagai input p,q. Mengejar algoritma serakah.

Chas Brown
sumber
-k-1bisa ~k.
Jonathan Frech
The i,jtugas bisa i,j=[i+1,i,0,j+1][j+1<len(v)::2]untuk -1 byte
Jo Raja
@ Jo King: Hahaha! Itu bengkok!
Chas Brown
while v[j]>-mbisawhile-m<v[j]
Kevin Cruijssen
@Kevin Cruijssen: Ya, tentu saja. Terima kasih!
Chas Brown
2

Jelly , 41 byte

Œṗl2ĊƑ$Ƈ
PÇIP$ƇṪÇ€Œpµ³ÇIP$ƇṪƊ€ŒpZPṢ⁼FṢ$µƇ

Cobalah online!

ÇIP$Ƈ[P,Q]

Tuan Xcoder
sumber
Bukannya itu masalah, tapi tidak terlalu cepat, kan? :)
Arnauld
@Arnauld Menggunakan sekitar 3 fungsi partisi integer dalam sekali jalan :) Tentu saja tidak terlalu cepat
Tn. Xcoder
Sekarang menunggu untuk dikalahkan. Saya pikir itu mungkin di sub-35/30, tapi saya tidak berpikir saya akan dapat melakukan sesuatu yang lebih singkat
Tn. Xcoder
2

Jelly , 34 byte

BṚT’2*
PÇŒṗæḟ2⁼ƊƇ€ŒpẎṢ⁼Ṣ}ʋƇÇ€×þ/ẎƊ

Cobalah online!

Format input: [P, Q](tautan TIO di atas tidak menerima ini, melainkan nomor tunggal, untuk membantu dengan kasus uji).

Format output: Daftar semua solusi (ditampilkan sebagai representasi kisi dari daftar 3D di atas TIO).

Kecepatan: Turtle.

Erik the Outgolfer
sumber
1

Haskell, 281 195 byte

import Data.List
r=reverse.sort
n#0=[]
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=[]
m!x=m!!0:tail m!(x-m!!0)
m%[]=[]
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))
Евгений Новиков
sumber
1
Berikut adalah beberapa tips: Mendefinisikan operator alih-alih fungsi biner lebih murah, mengatur ulang pelindung dan pencocokan pola dapat menyelamatkan Anda (==), menggunakan 1>0alih-alih, Truedan tidak menggunakan where. Juga n'dapat dipersingkat .. Dengan ini Anda dapat menyimpan 72 byte: Cobalah online!
ბიმო
Btw. Anda harus memeriksa bagian tips Haskell jika Anda belum.
ბიმო
Saya melihat situasi penjaga lagi, 13 byte lagi: Coba online!
ბიმო
@ OMᗺ, terima kasih. Saya baru
mengenal haskell
Jangan khawatir :) Jika Anda memiliki pertanyaan, jangan ragu untuk bertanya di Of Monads and Men .
ბიმო