Ascensão, sequência, ascensão

19

Temos uma sequência estritamente crescente de números inteiros não negativos, como:

12 11 10

Esperar! Essa sequência não está aumentando estritamente, é? Bem, os números são escritos em diferentes bases. A base menos possível é 2, a maior é 10.

A tarefa é adivinhar as bases de cada número, para que:

  • a sequência está aumentando estritamente,
  • a soma das bases é maximizada.

Por exemplo, a solução para a amostra será:

6 8 10

porque nessas bases a sequência se torna 8 9 10decimal - uma sequência estritamente crescente, e não somos capazes de encontrar bases para as quais a sequência permanece estritamente crescente e cuja soma é maior que 6+8+10.

Devido à segunda limitação, uma solução 3 5 7não é satisfatória: apesar de a sequência ficar 5 6 7sob essas bases - precisamos maximizar a soma das bases, e 3+5+7 < 6+8+10.

Se sob nenhuma base 2<=b<=10é possível que a série aumente estritamente, por exemplo:

102 10000 10

solteiro

0

deve ser produzido.

A sequência de entrada pode ser passada da maneira que for mais conveniente para sua solução (parâmetros de entrada / linha de comando padrão / argumentos de função ...).

pawel.boczarski
fonte
11
É 1 3 5uma sequência crescente? Que tal 1 7 22? (na base 10)
Maçaneta da porta
Sim, 1 3 5e 1 7 22ambos estão subindo na base 10. Portanto, a solução para ambos os casos é 10 10 10porque precisamos maximizar a soma de bases, assegurando que a sequência esteja subindo quando o n-ésimo número for interpretado como sendo escrito na base igual a n -ésimo termo da solução.
precisa saber é o seguinte
2
@ Dennis Sim, quero dizer estritamente aumentando seqüência. 1 1 1ou 3 3 4não estão subindo.
pawel.boczarski
3
Se os comentários indicarem que a pergunta está aberta a erros de interpretação, não basta responder nos comentários. Edite a pergunta para que outras pessoas não percam tempo escrevendo respostas que a interpretam de maneira diferente para você.
22413 Peter Peter Taylor
3
E sobre o assunto das ambiguidades, um dos comentários sobre minha resposta afirma que devemos assumir que os números são escritos de forma canônica na base fornecida. Se assim for, corrija a frase " A base menos possível é 2 " para algo como " A base menos possível é uma maior que o maior valor do dígito ".
Peter Taylor

Respostas:

13

Pitão, 31 30 29 bytes

e+0f.x!sgM.:iVczdT2ZosN^STlcz

1 byte graças a @Jakube.

Demonstração. Equipamento de teste.

A entrada é fornecida no STDIN, com espaço separado. Se a entrada separada por nova linha for permitida, eu posso reduzir o programa em 2 bytes.

Explicação:

e+0f.x!sgM.:iVczdT2ZosN^STlcz
                                  Implicit: z = input(), T = 10, Z = 0, d = ' '
                        ST        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                          lcz     len(z.split())
                       ^          All combinations w/replacement of that length.
                    osN           Order by increasing sum.
   f                              Filter on
              czd                 z.split(' ')
            iV   T                Vectorize the "Convert to base" operation over 
                                  the integers as strings and the base sequence.
          .:      2               Take length 2 subsequences.
        gM                        Map the >= operation over them.
      !s                          Sum and logically negate.
    .x             Z              If that throws an error, returns 0 (e.g. reject)
 +0                               Prepend a 0, in case no sequences are found.
e                                 Take the end of the list.

Incluir 1na lista de possíveis bases é seguro porque i, que usa o intbuilt-in do Python , não permite 1como base e, portanto, sempre gera um erro, que é capturado e filtrado.

isaacg
fonte
9

CJam, 43 bytes

0B,2>ea,m*{:+~}${ea::~_2$.b__Q|$=*@.b=}=p];

Lê argumentos da linha de comando e imprime uma matriz.

Experimente on-line no intérprete CJam .

Exemplos

$ cjam rise.cjam 12 11 10
[6 8 10]
$ cjam rise.cjam 19 18 17
0

Como funciona

0       e# Push a 0 (default return value).
B,2>    e# Push [0 ... 10] and remove the first two elements.
ea,     e# Push the number of command-line arguments (n).
m*      e# Cartesian power. Pushes all vectors of {2 ... 10}^n.
{:+~}$  e# Sort by the negated sums.
{       e# Find; for each vector V in {2 ... 10}^n:
  ea::~ e#   Evaluate each character of each command-line argument.
  _2$   e#   Copy the results and V.
  .b    e#   Vectorized base conversion (list to integer).
  __    e#   Push two copies.
  Q|$   e#   Deduplicate and sort the last copy.
  =     e#   Compare it to the first. Pushes 1/0 if equal/unequal.
  *     e#   Repeat the original result of .b that many times.
  @.b   e#   Vectorized base conversion (integer to list).
  =     e#   Compare the result to the modified command-line arguments.
        e#   Equality makes sure that the base was greater than all digits.
}=      e# If pushed 1, push V and break.
p       e# Print. Either prints the last V or 0 if none matched.
];      e# Clear the stack to avoid implicitly printing the 0 (if still present).
Dennis
fonte
6

Julia, 176 156 145 118 109 99 97 bytes

A->try p=NaN;flipud(map(i->(k=11;t=p;while t<=(p=parseint("$i",k-=1))end;k),flipud(A)))catch;0end

Ungolfed:

function anonfunc(i)
  # Start with k=11 so that it evaluates to 10 on first while iteration
  k=11
  # set t to the previous value of p
  # Note: p here gets held over between iterations within the map
  t=p
  # Iterate through, dropping k by 1 and evaluating the integer in
  # base k and stopping if the value drops below t
  # Note: "p=" expression inside conditional to ensure k-=1 is evaluated
  # at least once (to make NaN work as desired)
  while t<=(p=parseint("$i",k-=1))
  end
  # if it dropped below t, return the base, k to be the corresponding
  # element in the map
  return k
end

function f(A)
  # Using try/catch to return 0 if no acceptable base found
  try
    # This is a trick to make sure the comparison in the while loop
    # evaluates to false on the first use of it (last value in A)
    p=NaN
    # Apply anonfunc to each element of A, starting with the last element
    # and store the result in S
    S=map(anonfunc,flipud(A))
    # S is backwards, so flip it and return it
    return flipud(S)
  catch
    # Will throw to here if parseint fails with the base due to having
    # a digit not acceptable in the base
    return 0
  end
end

Usado com uma entrada de matriz 1d. Se a função estiver atribuída c, você chamaria c([12,11,10])e sairia [6,8,10].

Nota: Eu tinha usado dec(i)dentro do comando parseint, mas como ié um nome de variável de um caractere e não preciso acessar um componente, costumava "$i"obter o mesmo resultado.

Glen O
fonte
Você tem alguns bons truques aqui. Bom trabalho.
Alex A.
Esse código parece verificar as bases quanto à sequência estritamente decrescente na ordem de leitura usual da esquerda para a direita.
pawel.boczarski
@ pawel.boczarski - Não sei ao certo o que você quer dizer, mas se você quiser, posso fornecer alguns exemplos do que ele gera para determinadas entradas. Por exemplo, se você atribuir o nome à função c, as c([12,11,10])saídas [6,8,10]serão as bases necessárias.
Glen O
@GlenO Oh, entendo. Eu usei vetor de linha em [12 11 10]vez de [12,11,10]e isso deu o efeito indesejado.
pawel.boczarski
@ pawel.boczarski - ah, entendo. Sim, se você quiser que ele funcione com vetores de linha, será necessário substituir "flipud" por "fliplr"; nesse caso, ele retornará um vetor de linha das bases.
Glen O
5

Julia, 259 204 183 bytes

Guardou um monte com a ajuda de Glen O.

A->(M(x)=maxabs(digits(x))+1:10;S=[];X={};for i=M(A[1]),j=M(A[2]),k=M(A[3]) s=map(parseint,map(dec,A),[i,j,k]);all(diff(s).>0)&&(S=[S,sum(s)];X=[X,{[i,j,k]}])end;X==[]?0:X[indmax(S)])

Ungolfed + explicação:

function f(A)
    # Define a function to obtain the smallest possible base range
    M(x) = (maxabs(digits(x)) + 1):10

    # Define container arrays for the sums and bases
    S = []
    X = {}

    # Loop over all possible bases for each of the elements
    for i = M(A[1]), j = M(A[2]), k = M(A[3])
        # Parse each element of the input as a string
        # in the given base
        s = map(parseint, map(dec, A), [i,j,k])

        # Push the sum and bases if s is rising
        if all(diff(s) .> 0)
            S = [S, sum(s)]
            X = [X, {[i,j,k]}]
        end
    end

    # If X is empty, return 0, otherwise return the bases
    isempty(X) ? 0 : X[indmax(S)]
end
Alex A.
fonte
OK, um pouco de golfe a ser feito ... use "repr" em vez de "string" no comando map, eles funcionarão da mesma maneira neste contexto e salvarão dois bytes. E podemos economizar um pouco mais usando um operador infix para análise, escrevendo "\ = parseint" e, em seguida, usando x [1] \ i em vez de p (x [1], i) - mais um byte no "\" parte e, em seguida, salvando três para cada uso de p para uma economia líquida de 8 bytes. Outro byte economizado substituindo "maximum (digits (x)) por max (digits (x) ...)"
Glen O
Para uma economia maior, mescle os loops for - use for i=M(A[1]):10,j=M(A[2]):10,k=M(A[3]):10 <code here>end;, economizando oito para os dois se eliminados end;e oito para substituir `por` por ,.
Glen O
Na verdade, podemos melhorar ainda mais a parte da análise. Abandone completamente a renomeação da análise e use s=map(parseint,x,[i,j,k]), economizando 18 bytes em relação à sua solução original e 10 em comparação com a melhoria sugerida anteriormente. E, em vez disso s==sort(unique(s)), use all(diff(s).>0)para salvar outros 3 bytes.
Glen O
Certamente há mais a ser feito, mas deixarei para você e tentarei criar minha própria abordagem.
Glen O
Correção menor - sugeri usar max (...) em vez de máximo ... mas, embora economize um byte, falha nos valores de entrada de um dígito, portanto, você deve usar o máximo.
Glen O
4

CJam (39 bytes)

{Afb:X,9,2f+m*{X\.b__$_&=*},{:+}$0\+W=}

Essa é uma função anônima que recebe a entrada como uma matriz de números inteiros decimais na pilha e deixa a saída como uma matriz ou o número inteiro 0na pilha. Demonstração online .

Peter Taylor
fonte
Além disso, isso parece ordenar pela soma dos números inteiros resultantes, em vez das bases, e tem o mesmo problema que minha revisão anterior tinha ( 19não pode ser um número base 9).
Dennis
11
Hmm. A questão parece precisar de alguma melhoria.
Peter Taylor
@PeterTaylor Pah, desculuses;)
Decay Beta
2

Python 2 (147 bytes)

def x(s):
 q=int;c=10;o=q(s[-1])+1;l=[]
 for i in map(str,s)[::-1]:
    n=q(i,c)
    while o<=n:
        c-=1;n=q(i,c)
        if 3>c:return 0
    l=[c]+l;o=n
 return l

Chame a função xcom uma lista das entradas.

Exemplo:

print x([12,11,10])

impressões

[6, 8, 10]
Azul
fonte