Divida os bits!

17

Definimos como a lista de potências distintas de que somam . Por exemplo, .2 x V ( 35 ) = [ 32 , 2 , 1 ]V(x)2xV(35)=[32,2,1]

Por convenção, os poderes são classificados aqui do mais alto para o mais baixo. Mas isso não afeta a lógica do desafio, nem as soluções esperadas.

Tarefa

Dado um semiprime , substitua cada termo em por outra lista de potências de que somarem a esse termo, de modo que a união de todas as sub-listas resultantes seja uma cobertura exata da matriz definida como:V ( N ) 2 MNV(N)2M

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

onde e são os factores primários de .QPQN

Isso é muito mais fácil de entender com alguns exemplos.

Exemplo 1

Para , temos:N=21

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

Para transformar em uma cobertura exata de , podemos dividir em e em , enquanto permanece inalterado. Portanto, uma saída possível é:M 16 8 + 4 + 4 4 2 + 2 1V(N)M168+4+442+21

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

Outra saída válida é:

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

Exemplo 2

Para , temos:N=851

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

Uma saída possível é:

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

Regras

  • Como fatorar não é a parte principal do desafio, você pode considerar e como entrada.P QNPQ
  • Quando existem várias soluções possíveis, você pode retornar apenas uma delas ou todas elas.
  • Você pode retornar alternadamente os expoentes dos poderes (por exemplo, vez de ).[ [ 8 , 4 , 4 ] , [ 2 , 2 ] , [ 1 ] ][[3,2,2],[1,1],[0]][[8,4,4],[2,2],[1]]
  • A ordem das sub-listas não importa, nem a ordem dos termos em cada sub-lista.
  • Para alguns semiprimes, você não precisará dividir nenhum termo porque já é uma cobertura perfeita de (consulte A235040 ). Mas você ainda precisa retornar uma lista de listas (singleton) como para .M [ [ 8 ] , [ 4 ] , [ 2 ] , [ 1 ] ] N = 15V(N)M[[8],[4],[2],[1]]N=15
  • Isso é !

Casos de teste

 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
fonte
podemos tomar P e Q em vez de N?
NGN
@ngn Vou dizer que sim, porque fatorar N não é a parte principal do desafio.
Arnauld
1
Podemos retornar a saída achatada?
Erik the Outgolfer
@EriktheOutgolfer ... A saída achatada é apenas uma partição da entrada (1 + 2 + 2 + 4 = 9, por exemplo). Eu não acho que deveria ser permitido
Mr. Xcoder
@EriktheOutgolfer Eu não acho que possa ser inequívoco dessa maneira, pois o último termo de uma sub-lista pode ser o mesmo que o primeiro termo do próximo.
Arnauld

Respostas:

4

K (ngn / k) , 66 63 bytes

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

Experimente online!

aceita (P; Q) em vez de N

algoritmo:

  • calcular A como as somas parciais de V (P * Q)

  • multiplique cada V (P) por cada V (Q), classifique os produtos em ordem decrescente (vamos chamá-lo de R) e calcule suas somas parciais B

  • encontre as posições desses elementos em B que também ocorrem em A; corte R logo após essas posições

ngn
fonte
3

Gelatina , 24 bytes

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

Um link monádico que aceita uma lista de dois números inteiros [P, Q]que gera uma lista possível de listas, conforme descrito na pergunta.

Experimente online! (rodapé imprime uma representação de string para mostrar a lista como ela realmente é)

Ou veja a suíte de testes (tomando uma lista de N e reordenando os resultados para serem como os da pergunta)

Quão?

M1M4M=[[4]]

Nota: o código coleta todas (uma!) Dessas soluções em uma lista e, em seguida, obtém o resultado do cabeçalho (somente) - ou seja, o cabeçalho final é necessário, pois as partições não possuem todos os pedidos possíveis.

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
fonte
3

Python 2 , 261 233 232 231 bytes

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

Experimente online!

1 byte de Jo King ; e outro byte devido a Kevin Cruijssen .

Toma como entrada p,q. Persegue o algoritmo ganancioso.

Chas Brown
fonte
-k-1pode ser ~k.
Jonathan Frech
A i,jatribuição pode ser i,j=[i+1,i,0,j+1][j+1<len(v)::2]de -1 byte
Jo King
@Jo King: Hahaha! Isso é distorcido!
Chas Brown
while v[j]>-mpode serwhile-m<v[j]
Kevin Cruijssen
@ Kevin Cruijssen: Sim, de fato. Valeu!
Chas Brown
2

Geléia , 41 bytes

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

Experimente online!

ÇIP$Ƈ[P,Q]

Mr. Xcoder
fonte
Não que seja um problema, mas não é exatamente rápido, é? :)
Arnauld
@Arnauld Ele usa cerca de 3 funções de partição inteiro em uma única corrida :) Claro que não é muito rápido
Mr. Xcoder
Agora esperando para ser derrotado. Eu acho que é possível em sub-35/30, mas eu não acho que eu vou ser capaz de fazer qualquer coisa muito mais curto
Mr. Xcoder
2

Geléia , 34 bytes

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

Experimente online!

Formato de entrada: [P, Q](o link TIO acima não aceita isso, mas apenas um número, para ajudar nos casos de teste).

Formato de saída: lista de todas as soluções (mostradas como representação em grade da lista 3D em TIO).

Velocidade: Tartaruga.

Erik, o Outgolfer
fonte
1

Haskell, 281 195 bytes

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))
Евгений Новиков
fonte
1
Aqui estão algumas dicas: Definir operadores em vez de funções binárias é mais barato, reorganizar as proteções e a correspondência de padrões podem salvá-lo (==), use em 1>0vez de Truee não use where. Também n'pode ser reduzido. Com isso, você pode economizar 72 bytes: Experimente online!
ბიმო
Btw. você deve verificar a seção de dicas Haskell , se não tiver.
ბიმო
Observei novamente a situação da guarda, com mais 13 bytes de distância: Experimente online!
ბიმო
@ OMᗺ, obrigado. Eu sou novo para Haskell, então isso parece para mim como truques de mágica
Евгений Новиков
Não se preocupe :) Em caso de dúvidas, não hesite em perguntar em Of Monads and Men .
ბიმო