Walidacja modułu

12

Biorąc pod uwagę listę wyrażeń matematycznych, które są prawdziwe i składają się z obliczeń reszty modulo z dwiema liczbami i wynikiem, Twoim zadaniem jest uzyskanie pierwszych nliczb, które są prawdziwe dla wszystkich instrukcji na liście.

Na przykład:

[m % 3 = 0, m % 4 = 1, m % 5 = 3], gdzie% jest operatorem modulo.

Dla n= 3 pierwsze 3 liczby (licząc od 0), które pasują do sekwencji, są 33, 93, 153więc wynikiem (format do ciebie).

Zasady / IO

  1. Bierzesz liczbę dodatnią ni listę prawd. Oczywiście, potrzebne są tylko RHS operacji modulo i wynik.
  2. na liczby na liście prawd zawsze będą w zakresie 1 -> 2 ^ 31-1 , podobnie jak wyniki.
  3. Bierzesz dane w dowolnej dogodnej formie i dane wyjściowe w dowolnej dogodnej formie. Na przykład, wejście: 3 [3 0, 4 1, 5 3]i wyjście: 33 93 153.
  4. Gwarantuje to, że rozwiązanie jest matematycznie możliwe.
  5. Źródło danych wejściowych może pochodzić z pliku, parametrów funkcji, standardowego wejścia itd. To samo dotyczy danych wyjściowych.
  6. Bez luk.
  7. To jest golf golfowy, więc wygrywa najmniejsza liczba bajtów.

Przypadki testowe

# Input in the form <n>, <(d r), (d2 r2), ...>
# where <d> = RHS of the modulo expression and <r> the result of the expression. Output in the next line.

5, (3 2), (4 1), (5 3)
53 113 173 233 293

3, (8, 0), (13, 3), (14, 8)
120 848 1576

Implementacja referencji w pseudokodzie

n = (an integer from stdin)
truths = (value pairs from stdin)
counter = 0

while n != 0 {
    if matches_criterias(counter, truths) {
        print counter
        n -= 1
    }

    counter += 1
}
Yytsi
źródło
@flawr EDIT: Drugie pytanie wydaje się blokować wiele rzeczy i drukuje tylko jeden termin. Nie jestem pewien, czy jest to już duplikat ....
Yytsi
1
@flawr To wyzwanie ma ograniczenia czasowe. Istnieją bardziej golfistyczne sposoby rozwiązania tego problemu, które nie opierają się na chińskim twierdzeniu o pozostałej części.
Dennis
Tak, jestem tego świadomy, dlatego właśnie go połączyłem.
flawr
Czy 0prawidłowy wynik?
Neil

Odpowiedzi:

6

Galaretka , 7 bajtów

%⁼⁴
0ç#

To jest pełny program. Argumentami są dzielniki, moduły docelowe i liczba rozwiązań w tej kolejności.

Wypróbuj online!

Jak to działa

0ç#  Main link.
     Left argument: D (array of divisors)
     Right argument: M (array of target moduli)
     Third argument: n (number of solutions)

0ç#  Execute the helper link with k = 0, 1, 2, ... as left argument and D as the
     right one until n of them return 1. Yield the array of matches.


%⁼⁴  Helper link. Left argument: k. Right argument: D

%    Compute k % d for each d in D.
 ⁼⁴  Compare the result with M.
Dennis
źródło
4

Perl 6 , 33 bajtów

{grep((*X%@^b)eqv@^c,0..*)[^$^a]}

Spróbuj

Dane wejściowe to ( number-of-values, list-of-divisors, list-of-remainders )

Rozszerzony:

{   # bare block lambda with placeholder parameters 「$a」 「@b」 「@c」

  grep(

    # WhateverCode lambda:
    (

      *        # the value being tested

      X%       # cross modulus

      @^b      # with the divisors ( second parameter )

    )

    eqv        # is that list equivalent with

    @^c        # the expected remainders ( third parameter )

    # end of WhateverCode lambda

    ,

    0 .. *     # Range of all Integers starting with 0

  )[ ^$^a ]    # grab up-to 「$a」 values ( first parameter )
               # ( 「^$a」 is the same as 「0 ..^ $a」 )
}
Brad Gilbert b2gills
źródło
4

JavaScript (ES6), 71 68 bajtów

a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]

Prosta funkcja rekurencyjna. Użyj, curry w tablicy pierwszy i ndrugi, tak:

g=a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]
g([[3, 2], [4, 1], [5, 3]])(5)
ETHprodukcje
źródło
4

JavaScript (ES6), 74 70 69 bajtów

Staje wejście liczbą całkowitą noraz szereg az [modulo, remainder]tablic z currying składni (n)(a).

n=>a=>eval('for(i=r=[];a.some(([b,c])=>i%b-c)||--n*r.push(i);i++);r')

Przypadki testowe

Arnauld
źródło
3

Haskell, 47 bajtów

n#l=take n[i|i<-[0..],all(\(d,r)->mod i d==r)l]

Przykład użycia: 3 # [(8,0),(13,3),(14,8)]-> [120,848,1576].

nimi
źródło
3

Python, 67 bajtów

lambda n,r:[k for k in range(2**32)if all(k%d==m for d,m in r)][:n]
orlp
źródło
Potrzebujesz tylko range(2**31). Również bardzo miło. Wymyśliłem tę odpowiedź niezależnie.
mbomb007
3

JavaScript (ES6), 72 70 bajtów

a=>g=(n,i,r=[],m=a.some(e=>i%e[0]^e[1]))=>n?g(n-!m,-~i,m?r:[...r,i]):r

Zwinięte w pierwszej kolejności tablica warunków i druga liczba wyników. Edycja: Zapisano 2 bajty, nie obsługując wielkości zerowej.

Neil
źródło
2

Mathematica, 42 bajty

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&

Funkcja bez nazwy, zwracająca listę dodatnich liczb całkowitych i przyjmująca trzy dane wejściowe: listę modułów, listę reszt i liczbę nliczb całkowitych do zwrócenia. Na przykład drugi przypadek testowy jest wywoływany przez

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&[{8,13,14},{0,3,8},3]

i wraca {120, 848, 1576}.

Wbudowane #2~ChineseRemainder~#daje najmniejsze nieujemne rozwiązanie; aby uzyskać wszystkie pożądane rozwiązania, dodajemy tę liczbę Range[0,#3-1]LCM@@#, która jest pierwszą nnieujemną wielokrotnością najmniejszej wspólnej wielokrotności wszystkich modułów.

O ile mi wiadomo, Mathematica nie ma leniwie ocenianych nieskończonych list, więc ta implementacja była krótsza niż cokolwiek, co znalazłem, które testowało nieujemne liczby całkowite jeden po drugim - nawet przy długości nazwy funkcji ChineseRemainder, i mimo że test taki Mod[k,{8,13,14}]=={0,3,8}działa idealnie dobrze.

Greg Martin
źródło
2

PHP, 97 bajtów

najdłuższa jak dotąd odpowiedź. Ale cieszę się, że udało mi się uzyskać go poniżej 100.

for($a=$argv;++$k;)for($i=$v=2;$m=$a[$i++];$v>$argc/2&&$a[1]-->0?print$k._:0)$v+=$k%$m==$a[$i++];

pobiera dane wejściowe z oddzielnych argumentów wiersza poleceń,
drukuje dopasowania oddzielone i poprzedzone znakami podkreślenia.
Pętla nigdy nie pęka; ledwo odpowiedni dla testerów online.

Biegnij jak php -r 'code' <n> <modulo1> <result1> <modulo2> <result2> ....

awaria

for($a=$argv;++$k;)         // loop $k up from 1
    for($i=$v=2;                // $i = argument index, $v=2+ number of satisfied equations
        $m=$a[$i++];            // loop through modulo/result pairs
        $v>$argc/2                  // 2. if $v>argument-count/2
        &&$a[1]-->0                 // and match count not exhausted
            ?print$k._                  // print match
            :0                          // else do nothing
        )
            $v+=$k%$m==$a[$i++];    // 1. if $k%modulo==result, increment $v

notatki

$argc==count($argv). Dla trzech par istnieje 8 argumentów: nazwa pliku $argv[0], n= $argv[1]i pary modulo/ resultpowyżej. $v=2inkrementowane 3 razy daje 5> $argc/2.

Dodaj jeden bajt na czystą wyjścia: Wymień &&$a[1]-->0?print$k._się ?$a[1]--?print$k._:die.

Tytus
źródło
1

SmileBASIC, 102 bajty

DEF V N,M
FOR K=1TO N@L
T=T+1F=0FOR J=1TO LEN(M)F=F||T MOD M[J-1]-M[J]J=J+1NEXT
ON!F GOTO @L?T
NEXT
END

To pierwszy raz, kiedy używałem ONw SB. Powodem, dla którego użyłem go tutaj, IF F GOTO@Lbyło umieszczenie ?Tgo w tym samym wierszu, oszczędzając 1 bajt.

12Me21
źródło
1

Python, 59 bajtów

lambda n,m:[i for i in range(2**31)if all(map(eval,m))][:n]

m jest listą wyrażeń w postaci łańcucha, takich jak ["i % 4 == 1", ...]

Wypróbuj online (z mniejszym zasięgiem, więc faktycznie się skończy)

mbomb007
źródło
0

PHP, 91 bajtów

Weź listę jako tablicę asocjacyjną

<?for($t=1;$r<$_GET[1];$i+=$t=!$t?:print+$i._.!++$r)foreach($_GET[0]as$k=>$v)$t*=$i%$k==$v;

Wypróbuj online!

Jörg Hülsermann
źródło