Reconhecer dobras mod

18

Tarefa

Defina uma dobra de modificação em função da forma f (x) = x% a 1  % a 2  %…% a k , onde a a i são números inteiros positivos e k ≥ 0 . (Aqui, % é o operador do módulo associativo à esquerda.)

Dada uma lista de n números inteiros y 0 ,…, y n − 1 , determine se existe uma dobra mod f para que cada y i  = f (i) .

Você pode escolher e fixar quaisquer duas saídas Y e N para sua função / programa. Se existir um f , você sempre deve retornar / imprimir exatamente Y ; se não, você deve sempre retornar / imprimir exatamente N . (Estes podem ser true/ false, ou 1/ 0, ou false/ true, etc.) Mencione-os na sua resposta.

O menor envio em bytes vence.

Exemplo

Defina f (x) = x% 7% 3 . Seus valores começam:

|   x  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
| f(x) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | ...

Assim, dada 0 1 2 0 1 2 0 0 1 2como entrada para a solução, que iria imprimir Y , como esta f gera essa sequência. No entanto, 0 1 0 1 2como entrada, imprimiríamos N , pois nenhum f gera essa sequência.

Casos de teste

As fórmulas fornecidas quando a saída é Y são apenas para referência; você não deve imprimi-los em nenhum momento.

0 1 2 3 4 5              Y    (x)
1                        N
0 0 0                    Y    (x%1)
0 1 2 0 1 2 0 0 1 2      Y    (x%7%3)
0 0 1                    N
0 1 2 3 4 5 6 0 0 1 2    Y    (x%8%7)
0 1 2 0 1 2 0 1 2 3      N
0 2 1 0 2 1 0 2 1        N
0 1 0 0 0 1 0 0 0 0 1    Y    (x%9%4%3%2)
Lynn
fonte
Existem limites de tempo ou memória?
Dennis
2
Posso emitir valores reais e valores falsey?
Leaky Nun
2
@Leaky Eu prefiro que você não. Eu não sou um grande fã de truth-falsey; Estou tentando explicitamente isso como uma alternativa mais objetiva que ainda lhe dá liberdade.
Lynn
@ Lynn é só comigo ou você ainda não o corrigiu?
Freira vazada
Com relação às restrições de memória / tempo: acho que não adicionarei nenhuma ao desafio em si, mas posso oferecer uma recompensa pela resposta mais curta em bytes que possa responder a cada um dos meus casos de teste em um período de tempo razoável.
Lynn

Respostas:

7

Pitão, 14 bytes

}Qm%M+RdUQy_Sl

Retorna True/False. Experimente on-line: Demonstration or Test Suite

Explicação:

}Qm%M+RdUQy_SlQ   implicit Q (=input) at the end
             lQ   length of input list
            S     create the list [1, 2, ..., len]
           _      reverse => [len, ..., 2, 1]
          y       generate all subsets (these are all possible mod-folds)
  m               map each subset d to:
        UQ           take the range [0, 1, ..., len-1]
     +Rd             transform each number into a list by prepending it to d
                     e.g. if mod-fold = [7,3], than it creates:
                        [[0,7,3], [1,7,3], [2,7,3], [3,7,3], ...]
   %M                fold each list by the modulo operator
                  this gives all possible truthy sequences of length len
}Q                so checking if Q appears in the list returns True or False

Pitão, 11 bytes

q%M.e+k_tx0

Com base na idéia de @ ferrsum . Na verdade, pensei em usar os índices zero para a geração de subconjuntos, mas não percebi que todos os índices zero já deveriam ser a solução.

Jakube
fonte
4

Python 3, 239 218 bytes

from itertools import*
lambda z:z in[[eval(''.join([str(l)]+['%'+str(i[::-1][k])for k in range(len(i))]))for l in range(len(z))]for i in(i for j in(combinations(range(1,len(z)+1),i+1)for i in range(len(z)))for i in j)]

Uma função anônima que recebe entrada de uma lista ze retorna Trueou Falsepara Ye N.

Isso usa um método semelhante à resposta de @Jakube e, embora seja essencialmente uma força bruta, é executado muito rapidamente.

from itertools import*               Import everything from the Python module for
                                     iterable generation
lambda z                             Anonymous function with input list z
combinations(range(1,len(z)+1),i+1)  Yield all sorted i+1 length subsets of the range
                                     [1,len(z)]...
...for i in range(len(z))            ...for all possible subset lengths
(i for j in(...)for i in j)          Flatten, yielding an iterator containing all possible
                                     mod-fold values as separate lists
...for i in...                       For all possible mod-fold values...
...for k in range(len(i))            ...for all mod-fold values indices k...
...for l in range(len(z))            ...for all function domain values in [0,len(z)-1]...
[str(l)]+['%'+str(i[::-1][k])...]    ...create a list containing each character of the
                                     expression representing the function defined by the
                                     mod-fold values (reversed such that the divisors
                                     decrease in magnitude) applied to the domain value...
 eval(''.join(...))                  ...concatenate to string and evaluate...
 [...]                               ...and pack all the values for that particular
                                     function as a list
 [...]                               Pack all lists representing all functions into a list
 ...:z in...                         If z is in this list, it must be a valid mod-fold, so
                                     return True. Else, return False

Experimente no Ideone

TheBikingViking
fonte
4

Python 2, 69 bytes

f=lambda a,i=0:i/len(a)or a[i]in[a[i-1]+1,i,0][i<=max(a)::2]*f(a,i+1)

Usa True/ False.

A resposta para o que caracteriza uma série dobrável em mod acaba sendo menos interessante do que parece à primeira vista. É uma série do formato 0, 1, ..., M - 1, 0, 1, ... x 1 , 0, 1, ..., x 2 , ... tal que para todos i, 0 <= x i <M. Essa sequência pode ser produzida pela cadeia mod de todos os índices (com base em 0) dos zeros na matriz, excluindo o primeiro.

feersum
fonte
3

Geléia , 19 15 14 bytes

LṗLUZ’1¦%/sLe@

Retorna 1 para verdade, 0 para falsidade. Experimente online!

O algoritmo é O (n n ) , em que n é o comprimento da lista, tornando-o muito lento e com muita memória para a maioria dos casos de teste.

Uma versão modificada - que substitui a segunda Lpor a 5- pode ser usada para verificar todos os casos de teste . Observe que esta versão modificada não funcionará para listas arbitrariamente longas.

Como funciona

LṗLUZ’1¦%/sLe@  Main link. Argument: A (array of integers)

L L             Yield the length l of A.
 ṗ              Take the l-th Cartesian power of [1, ..., l], i.e., construct
                all arrays of length l that consist of elements of [1, ..., l].
   U            Upend/reverse each array. This way, the first l arrays start
                with [1, ..., l], as do the next l arrays, etc.
    Z           Zip/transpose the array of arrays.
     ’1¦        Decrement the first array to map [1, ..., l] to [0, ..., l - 1].
        %/      Reduce the array's columns by modulus/residue.
          sL    Split the result into chunks of length l.
            e@  Verify if A belongs to the resulting array.
Dennis
fonte
Você pode adicionar uma explicação? Como alguém que ainda não usou o Jelly, não faço ideia de como ele funciona.
Steven H.
Vou adicionar um assim que terminar de jogar golfe. Ainda quero tentar algumas coisas primeiro.
Dennis
Eu (desisti e) adicionei uma explicação.
Dennis
3

JavaScript (ES6), 98 bytes

a=>a.every((n,i)=>n?n<(l+=p==i)&&n==p++:p=1,l=p=1)

Economizou 48 bytes mudando para a descoberta de @ Feersum. Qualquer valor especificado nna matriz é zero, nesse caso a próxima previsão pé 1 ou é igual à próxima previsão, e nesse caso pé incrementado. Também medimos o comprimento lda sequência inicial comparando pcom i, como nsempre deve ser menor do que lem todos os momentos.

Neil
fonte
2

Python 2, 103 99 bytes

f=lambda l,r:r==x or l and f(l-1,[t%l for t in r])|f(l-1,r)
x=input();l=len(x);print+f(l,range(l))

Imprime 1 para verdade e 0 para falsidade. Teste em Ideone .

Dennis
fonte