Gerar uma função monotônica

12

Visão geral

Nesse desafio, sua tarefa é gerar aleatoriamente uma função matemática monotônica entre dois conjuntos.

Entrada

Suas entradas são dois números inteiros positivos se n.

Depois de obter essas entradas, seu programa deve gerar uma função matemática aleatóriaf do conjunto para . Em outras palavras, é uma "regra" que recebe um número múltiplo de números inteiros entre e e retorna um número inteiro. Além disso, deve ser monotônico no seguinte sentido. Se e são dois -tuples, tal que vale para todas as coordenadas , então .{0,1,...,s-1}n{0,1,...,s-1}fn0s-1fABnA[i] ≥ B[i]if(A) ≥ f(B)

A distribuição exata das funções monotônicas fnão importa, desde que cada uma dessas funções tenha uma probabilidade positiva de ser gerada (assumindo um RNG perfeito).

Resultado

Sua saída deve ser uma enumeração das entradas e saídas de f. Deve conter todos os n-tuplos de números inteiros entre 0e s-1em alguma ordem, cada um sendo seguido pela saída correspondente de f. O formato exato da saída é flexível (dentro do motivo).

Exemplos

As entradas s = 3e n = 2podem produzir a saída

(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2

Ele contém todos os pares sobre o conjunto {0, 1, 2}exatamente uma vez e cada um é seguido pelo seu fvalor. A condição de monotonicidade também é satisfeita. As tuplas são fornecidas aqui em ordem lexicográfica, mas isso não é necessário.

Como outro exemplo, s = 2e n = 4pode produzir

(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1

A seguir, são apresentadas todas as saídas possíveis para s = 2e n = 2(até a reordenação das tuplas); seu programa deve gerar aleatoriamente um deles:

(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1

Regras e Pontuação

Você pode escrever um programa completo ou uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas. Código com explicação é o preferido.

Não há restrições à complexidade do tempo, mas darei um bônus de -15% se a sua solução sempre garantir a conclusão em um determinado período de tempo (dependendo das entradas e assumindo um RNG perfeito que funcione em tempo constante) .

Zgarb
fonte
Pode ser útil se você enumerar completamente todas as funções possíveis para um caso minúsculo, como s = 2 n = 2. Eu tive que ler a descrição algumas vezes para entender como a aleatoriedade entraria em jogo.
Sparr
@Sparr Boa ideia; editado.
Zgarb 23/09/2015
o tempo de execução limitado é um requisito? Estou pensando em uma solução que produz funções aleatórias até encontrar uma solução monotônica.
Sparr
@ Parr Acho que vou adicionar um bônus por tempo de execução limitado, para que essa solução não seja desqualificada.
Zgarb 23/09/15
@ Zgarb - talvez você deva fazer um grande bônus por soluções limitadas e com probabilidade de terminar em uma hora.
Glen O

Respostas:

4

Pitão, 35 bytes (38 - 15% = 31,45 mais abaixo)

#I!sm><FhMds<MCeMd^JC,mOQK^UQvzK2JB

Demonstração

A entrada está no formato:

n
s

A saída está no formato:

[[value, tuple], [value, tuple], ...]

Simplesmente gera possibilidades aleatórias e as testa.


Versão alternativa de 37 bytes, que acredito qualificar para o bônus:

Of!sm><FhMds<MCeMd^T2mC,d^UQvz^UQ^Qvz

Demonstração

Isso começa gerando todas as funções monotônicas possíveis e gera uma aleatoriamente. É muito mais lento e termina em 2,2.

isaacg
fonte
Bom exemplo com entrada 3, 2. Infelizmente, nem recebi uma resposta 3, 3no executor pyth online. Existe um loop infinito para essa combinação ?!
bobbel
@bobbel O executor on-line tem um tempo limite, eu acho. Eu tento localmente.
Isaacg 23/09
@bobbel Não é tanto um loop infinito que é muito lento. Também funciona para 2, 4, mas não muito mais.
Isaacg
Bobb @ eu adicionei algo ainda mais lento.
Isaacg
1

CJam, 40 bytes - 15% = 34 bytes

q~1$\m*\1$,m*{W$\.+2m*{:.<2b}%1&!},mR]zp

Essa abordagem gera todas as funções válidas e, em seguida, seleciona aleatoriamente. O tempo de execução é pelo menos O (s 2s n ) , mas constante para uma determinada entrada.

Duvido que seja isso que o OP tinha em mente, mas é garantido que terminará em um determinado período de tempo (dependendo das entradas) [...] e, portanto, qualifique-se para o bônus.

Experimente on-line no intérprete CJam .

Dennis
fonte
1

Julia, 64 bytes (-15% = 54,4)

g(s,n)=(K=rand(0:s-1,ntuple(n,i->s));for i=1:n K=sort(K,i)end;K)

Ungolfed:

function g(s,n)
  # Generates a random n-dimensional array with s per dimension
  # and all values being integers between 0 and s-1
  K=rand(0:s-1,ntuple(n,i->s))
  # Loop over the various dimensions
  for i=1:n
    # Sort in the current dimension
    K=sort(K,i)
  end
  return K
end

Isso será executado rapidamente, com o único problema possível com a memória para se suficientemente grande n (g (10,10) tiver que produzir uma matriz 10 ^ 10, portanto, obviamente, ficará sem memória - mesmo que cada número seja um byte, são 10 gigabytes de dados).

A saída é indexação com base em 1; portanto, para determinar o resultado de uma determinada entrada, você precisa adicionar uma a cada valor de entrada. Por exemplo, para encontrar f (1,2,6,0,3), você precisa examinar K[2,3,7,1,4].

Glen O
fonte