Finden Sie ein Teilbarkeitsmuster
Hintergrund
Wenn ich ein Programm spiele, wird manchmal die folgende Situation angezeigt: Ich habe einen ganzzahligen Wert \$x\$in einem festen Intervall \$[a, b]\$, und ich möchte testen, ob es sich um eine feste Teilmenge handelt \$S \subset [a, b]\$mit so wenig Bytes wie möglich. Ein Trick, der manchmal in einer Sprache funktioniert, in der Ganzzahlen ungleich Null wahr sind, ist das Finden kleiner Ganzzahlen \$n\$und \$k\$so dass \$x \in S\$gilt genau dann, wenn \$x + k\$teilt nicht \$n\$, denn dann kann mein Test gerecht sein n%(x+k). Bei dieser Herausforderung besteht Ihre Aufgabe darin, das Minimum \ zu berechnen$n\$und \$k\$ aus den festen Daten.
Die Aufgabe
Ihre Eingaben sind eine Zahl \$b\$und eine Menge \$S\$von ganzen Zahlen zwischen \$1\$und \$b\$inklusive (wir nehmen an \$a = 1\$der Einfachheit halber) in jedem vernünftigen Format. Sie können die Ergänzung von \ nehmen$S\$falls Sie es wollen. Wenn Sie \ nehmen$S\$Als Liste können Sie davon ausgehen, dass sie sortiert und duplikationsfrei ist. Sie können auch \ annehmen$b\$ist höchstens die Anzahl der Bits in einer ganzen Zahl und nehmen \$S\$ als Bitmaske, wenn Sie wollen.
Ihre Ausgabe ist das lexikografisch kleinste Paar von Ganzzahlen \$(n,k)\$mit \$n \geq 1\$und \$k \geq 0\$so dass für jeden \$1 \leq x \leq b\$, \$k+x\$teilt \$n\$genau dann, wenn \$x\$ist kein Element von \$S\$. Dies bedeutet, dass \$n\$sollte minimal sein und dann \$k\$sollte dafür minimal sein \$n\$. Das Ausgabeformat ist ebenfalls flexibel.
Beachten Sie, dass Sie nur \ berücksichtigen müssen$k \leq n\$, weil nein \$k+x\$kann teilen \$n\$wenn \$k \geq n\$.
Die niedrigste Byteanzahl in jeder Sprache gewinnt.
Beispiel
Angenommen, die Eingaben sind \$b = 4\$und \$S = [1,2,4]\$. Versuchen wir es mit \$n = 5\$ (unter der Annahme, dass alle niedrigeren Werte ausgeschlossen wurden).
- Die Wahl \$k=0\$funktioniert nicht, weil \$k+1 = 1\$teilt \$5\$aber \.$1 \in S\$.
- Die Wahl \$k=1\$funktioniert nicht, weil \$k+3 = 4\$teilt nicht \$5\$aber \.$3 \notin S\$.
- Die Wahl \$k=2\$funktioniert: \$k+1 = 3\$, \$k+2 = 4\$und \$k+4 = 6\$teile nicht \$5\$und \$k+3 = 5\$teilt \$5\$.
Testfälle
b S -> n k
1 [] -> 1 0
1 [1] -> 1 1
2 [] -> 2 0
2 [1] -> 3 1
2 [2] -> 1 0
2 [1,2] -> 1 1
4 [1,2,4] -> 5 2
4 [1,3,4] -> 3 1
5 [1,5] -> 168 4
5 [2,5] -> 20 1
5 [3,4] -> 6 1
5 [2,3,4,5] -> 1 0
6 [1] -> 3960 6
8 [2,3,6,7] -> 616 3
8 [1,3,5,7,8] -> 105 1
8 [1,2,3,4,5] -> 5814 11
9 [2,3,5,7] -> 420 6
14 [3,4,6,7,8,9,10,12,13,14] -> 72 7
Antworten
05AB1E , 21 20 19 18 Bytes
Vielen Dank an Kevin Cruijssen für -1 Byte!
-1 Byte inspiriert XASH ‚s Brachylog Antwort !
[¼¾ƒ²L¾ÑN-K¹Qi¾N‚q
Probieren Sie es online aus!
oder
Probieren Sie die meisten Testfälle aus! (basierend auf der Testsuite von FryAmTheEggman für diese Antwort .)
# see below for the remainder of the code
²L # push [1 .. b]
¾Ñ # push the divisors of n
N- # subtract k from each
# this is now a list of all x in [-k+1 .. n-k] with n%(x+k)==0
K # remove this from [1 .. b]
¹Q # is this equal to S?
05AB1E , 24 23 Bytes
Die erste Eingabezeile ist die Menge \$S\$, zweiter \$b\$.
[¼¾ƒ¾¹²L‚N+Ö_O¹gªËi¾N‚q
Probieren Sie es online aus!
Dies durchläuft alle möglichen Paare in lexikografischer Reihenfolge und prüft für jedes Paar:
\begin{align*} \left|S\right| &=\left|\left\{ x \in [1 .. b] \mid x \;\text{does not divide}\; n \right\}\right| \\&= \left|\left\{ x \in S \mid x \;\text{does not divide}\; n \right\}\right| \end{align*}
Kommentiert :
[ # infinite loop
¼¾ # increment and push the counter (n)
ƒ # for N(=k) in [0 .. n]:
¾ # push n
¹ # push the first input (S)
²L # push [1 .. second input (b)]
‚ # pair these two lists up
N+ # add current k to both lists
Ö_ # do they not divide n (vectorizes)
O # sum both lists
¹g # push the length of S
ª # append this to the list
Ë # are all equal?
i # if this is true:
¾ # push n
N # push k
‚ # pair n and k
q # quit the program (implicit output)
Haskell , 63 Bytes
b!s=[(n,k)|n<-[1..],k<-[0..n],[x|x<-[1..b],mod n(k+x)>0]==s]!!0
Probieren Sie es online aus!
Python 3 , 110 91 89 Bytes
Dank Jitse wurden satte 19 21 Bytes gespeichert !!!
Sprengt TIO wegen wahnsinniger Rekursionstiefen in die Luft! :(
f=lambda b,S,n=1,k=0:S==[x+1for x in range(b)if n%(k-~x)]and(n,k)or f(b,S,n+k//n,-~k%-~n)
Probieren Sie es online aus!
R , 92 86 85 83 82 Bytes
Bearbeiten: -2 Bytes dank Giuseppe, dann -1 weitere Bytes dank Robin Ryder
function(b,S)repeat for(k in 0:(F=F+1))if(all(1:b%in%S-!F%%(1:b+k)))return(c(F,k))
Probieren Sie es online aus!
Testet zunehmende Geschwindigkeiten von n (tatsächlich wie Fhier definiert , um seinen Standardanfangswert von Null auszunutzen) und durchläuft für jeden alle Schleifen kund gibt zurück, F,kwenn sie !F%%(x+k) != x %in% Sfür alle xin erfüllen 1:b.
Jetzt 6 Byte kürzer als meine vorherige rekursive Version , und es können tatsächlich alle Testfälle abgeschlossen werden, ohne dass das R- Rekursionslimit und die zugewiesene Stapelgröße erhöht werden müssen .
JavaScript (ES6), 85 83 82 Byte
Erwartet (b)(s), wo sist ein Set. Rückgabe [n, k].
b=>s=>{for(n=k=0;(g=x=>x&&n%(x+k)>0^s.has(x)|g(x-1))(b,k=k?k-1:++n););return[n,k]}
Probieren Sie es online aus!
Kommentiert
b => s => { // b = upper bound; s = set of integers
for( // main loop:
n = k = 0; // start with n = k = 0
( //
g = x => // g is a recursive function taking x:
x && // stop if x = 0
n % (x + k) > 0 // otherwise yield 1 if x + k does not divide n
^ s.has(x) // XOR with 1 if x belongs to the set
| g(x - 1) // recursive call with x - 1
)( // initial call to g:
b, // start with x = b
k = // update k:
k ? k - 1 // decrement k if it's not equal to 0
: ++n // otherwise, increment n and set k to n
); // end of call to g; break if it's falsy
); // end of loop
return [n, k] // return the result
} //
Gelee , 19 Bytes
Ż⁴+þ⁸%T€i©
1ç1#‘,®’
Ein vollständiges Programm, das den Satz akzeptiert, \$S\$und die Obergrenze, \$b\$, der die Variablen als Liste druckt, \$[n,k]\$.
Probieren Sie es online aus!
Oder sehen Sie sich die Testsuite an (ohne die beiden am längsten laufenden Eingaben).
Mit freundlicher Genehmigung von FryAmTheEggman .
Wie?
1ç1#‘,®’ - Main Link: S, b
1 - set left to 1
1# - count up starting at x=left finding the first x which is truthy under:
ç - call the helper Link as a dyad - f(x, S)
‘ - increment -> n+1
® - recall the value from the register -> k+1
, - pair -> [n+1, k+1]
’ - decrement -> [n, k]
- implicit print
Ż⁴+þ⁸%T€i© - Link 1: potential_n, S
Ż - zero-range -> [0..potential_n] (the potential k values)
⁴ - program's 4th argument, b
þ - table of (implicitly uses [1..b]):
+ - addition
⁸ - chain's left argument -> potential_n
% - modulo (vectorises)
T€ - truthy 1-based indexes of each
i - first index of (S); 0 if not found
© - copy that to the register and yield it
C (gcc) , 129 \$\cdots\$ 111 109 Bytes
x;s;n;k;f(b,S){for(s=n=1;s;++n)for(k=0;k++<=n&&s;)for(x=b,s=S;x--;)s-=!(n%(x+k))<<x;printf("%d %d",n-1,k-2);}
Probieren Sie es online aus!
Nimmt \$S\$als invertierte Bitmaske der Länge \$b\$und Ausgänge \$n\$und \$k\$zu stdout.
Erläuterung
f(b,S){ // function f takes b as an int and S as a
// inverted bitmask - the least significant
// b-bits of S are unset only if that bit position
// corresponds to a member of the original set S
for(s=n=1; // loop starting with n=1 and s temporarily
// set to 1 just to pass the first two loop tests
s; // loop until s is 0
++n) // bumping n up by +1 each time
for(k=0; // inner loop trying values of k starting at 0
k++ // k is bumped up by +1 before use to offset b
// which will be 1 less than needed
<=n // loop until k is +1 greater than n
&&s;) // or until we've hit our target
for(x=b, // another nested for loop of x starting at b-1
s=S; // first real init of s to input bitmask
x--;) // loop from b-1 down to 0
// which corresponds to b down to 1
// since x is offset by -1
s-=!(n%(x+k))<<x; // subtract off from s bits corresponding to values
// for which n%(x+k) is false - because it's the
// inverted bitmask
// s will be 0 at the end of this most inner loop
// iff n and k are our minimal targets
printf("%d %d", // once we've discovered the smallest n and k
n-1, // we need to compensated for loop increments
k-2); // and k being offset by +1
}
Holzkohle , 32 29 Bytes
Ｗ¬№ωθ≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κωＩ⟦Ｌυ⌕ωθ
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Nimmt \$ S \$als invertierte Bitmaske der Länge \$ b \$und Ausgänge \$ n \$und \$ k \$in getrennten Zeilen. Erläuterung:
Ｗ¬№ωθ
Wiederholen Sie diesen Vorgang, bis die gewünschte Bitmaske in der aktuellen Bitmaske gefunden wurde.
≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κω
Inkrement \$ n \$und berechnen Sie die vollständige Bitmaske für \$ 1 \leq k + x \leq n + b \$.
Ｉ⟦Ｌυ⌕ωθ
Ausgabe \$ n \$und der Index \$ k \$der Eingabebitmaske \$ S \$ in der vollen Bitmaske.
Brachylog , 27 Bytes
∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧
Probieren Sie es online aus!
Wie es funktioniert
∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧
. The output is
Ċ [N, K], where …
ℕᵐ N ≥ 0 and K ≥ 0, and …
≥₁ N ≥ K.
fʰ Factors of N
z zipped with
gᵗ K:
≜-ᵐ label and take K from every factor.
F Save the result as F.
&h⟦₁ [1, …, b]
;Fx without the elements in F
~t? is S.
∧ Return output.
K (oK) , 70 bis 68 Bytes
f:{n,e@n:{y+1-#x@y}[e:{*&&/'=[~x in y]'0=![;z]''+[x]'!1+z}[1+!x;y]]/1}
Probieren Sie es online aus!
TiO kann die Beispiele mit Ausnahme von 6 [1] -> 3960 6und 8 [1,2,3,4,5] -> 5814 11nach Ablauf der Zeit ausführen.
k4, 102 71 69 Bytes
{n,e@n:{y+^x@y}[e:{*&&/'=[~x in y]'0=.q.mod[z;+[x]'!1+z]}[1+!x;y]]/1}
Genannt als {...}[b;S]. Verwendet die Converge - Version /weiterhin erhöht wird, den Wert nzu testen , bis ein gültiger xund kidentifiziert werden. Innerhalb e:, xist b, yist S, und zist n.
Schale , 38 33 28 22 24 Bytes
Änderungen: -5 Bytes dank Razetime, dann -6 Bytes dank Zgarb, dann +2 Bytes, um einen Fehler zu beheben, bei dem keine Lösungen gefunden wurden, für die kNull ist
§,o←ḟVImλVö=²`Wḣ⁴`%¹+ŀ)N
Probieren Sie es online aus!
Argumente sind Ganzzahl bund Liste S; gibt ein Paar von ganzen Zahlen aus (k,n).
Meine zweite Husk Antwort, und es hat mich Alter es an die Arbeit überhaupt zu bekommen, so ich es vermute , noch golfed-down werden kann viel ganz erheblich golfed-down von Razetime & Zgarb ...
Überprüft steigende Werte von nund berechnet den niedrigsten Wert , der kerfüllt werden kann S == (n%(b+k)>0). Ruft dann diesen Wert, und sein Index, wie kund n, respectively.
Bearbeiten: In seiner ursprünglichen Form fehlten diese Lösungen kgleich Null, da dies das gleiche Ergebnis ist, als würde keine gültige gefunden k. Also jetzt bearbeitet, um zu berechnen k+1, und dann 1 abziehen, nachdem der Wert abgerufen wurde.
Wie?
mλVö=²`Wḣ⁴`%¹+ḣ)N # part 1: calculate first value of k+1 for each possible n
m # map function to each element of list
N # N = infinite list of natural numbers
λVö=²`Wḣ⁴`%¹+ḣ) # lambda function taking 1 argument:
V ŀ # find the first 1-based index of k in 0..n with a truthy result of
ö=²`Wḣ⁴`%¹+ # function to check if true indices of n%(k+b) are equal to S
ö # composition of 4 functions
+ # add b
`%¹ # mod n
`Wḣ⁴ # get set of truthy indices of 1..b
=² # is this equal to S?
# (note that because we take the 1-based index
# of a range from 0..n, this part calculates k+1,
# or zero if there is no valid k)
§,o←ḟVI # part 2: return the first k, n
§ # fork: apply func1 to the results of func2 & func3
, # func1 = join as pair
o←ḟ # func2 (takes 2 args, 2-part fucntion combined using o):
# increment the first truthy element of arg1 (a function) applied to arg2 (a list)
V # func3 (takes 2 args): first truthy index of arg1 (a function) applied to arg2 (a list)
I # arg1 for both func2 & func1 = identity function
# arg2 for both func2 & func1 is part1 above: the first k for each n (if any)
Perl 5 -p , 70 Bytes
/,/;++$k>$n?$k=0*++$n:0until"@{[grep$n%($k+$_),1..$`]}"eq$';$_="$n $k"
Probieren Sie es online aus!
oder weniger verständlich und kniffliger 68 Bytes
-lp68 Bytes
/,/;++$\>$,?$\=0*++$,:0until"@{[grep$,%($\+$_),1..$`]}"eq$';$_="$, "
Probieren Sie es online aus!