หารูปแบบการหาร
พื้นหลัง
บางครั้งเมื่อฉันตีกอล์ฟโปรแกรมฉันจะพบกับสถานการณ์ต่อไปนี้: ฉันมีค่าจำนวนเต็ม\$x\$ในบางช่วงเวลาคงที่\$[a, b]\$และฉันต้องการทดสอบว่ามันอยู่ในชุดย่อยคงที่\$S \subset [a, b]\$โดยมีจำนวนไบต์น้อยที่สุด เคล็ดลับหนึ่งที่บางครั้งทำงานในภาษาที่ไม่ใช่ศูนย์จำนวนเต็มมี truthy คือการหาจำนวนเต็มขนาดเล็ก\$n\$และ\$k\$เช่นนั้น\$x \in S\$ถือได้อย่างแม่นยำเมื่อ\$x + k\$ไม่แบ่ง\$n\$เพราะงั้นการทดสอบของฉันก็เป็นn%(x+k)ได้ ในความท้าทายนี้งานของคุณคือคำนวณ\$n\$และ\$k\$ จากข้อมูลคงที่
งาน
อินพุตของคุณเป็นตัวเลข\$b\$และชุด\$S\$จำนวนเต็มระหว่าง\$1\$และ\$b\$รวม (เราถือว่า\$a = 1\$เพื่อความเรียบง่าย) ในรูปแบบที่สมเหตุสมผล คุณอาจใช้ส่วนเสริมของ\$S\$ถ้าคุณต้องการ. ถ้าคุณใช้\$S\$ในฐานะรายการคุณสามารถสมมติว่ามีการจัดเรียงและไม่ซ้ำกัน คุณยังสามารถสมมติว่า\$b\$เป็นจำนวนบิตมากที่สุดในจำนวนเต็มและรับ\$S\$ เป็น bitmask ถ้าคุณต้องการ
ผลลัพธ์ของคุณคือคู่ของจำนวนเต็มที่เล็กที่สุดในพจนานุกรม\$(n,k)\$ด้วย\$n \geq 1\$และ\$k \geq 0\$เช่นนั้นสำหรับแต่ละ\$1 \leq x \leq b\$, \$k+x\$หาร\$n\$ถ้าและเฉพาะในกรณีที่\$x\$คือไม่ได้องค์ประกอบของ\$S\$. ซึ่งหมายความว่า\$n\$ควรน้อยที่สุดแล้ว\$k\$ควรน้อยที่สุดสำหรับสิ่งนั้น\$n\$. รูปแบบผลลัพธ์ยังมีความยืดหยุ่น
โปรดทราบว่าคุณต้องพิจารณาเฉพาะ\$k \leq n\$เพราะไม่\$k+x\$สามารถแบ่ง\$n\$เมื่อ\$k \geq n\$.
จำนวนไบต์ต่ำสุดในแต่ละภาษาจะชนะ
ตัวอย่าง
สมมติว่าอินพุตเป็น\$b = 4\$และ\$S = [1,2,4]\$. ลองกันเถอะ\$n = 5\$ (สมมติว่าค่าที่ต่ำกว่าทั้งหมดถูกตัดออก)
- ทางเลือก\$k=0\$ไม่ทำงานเนื่องจาก\$k+1 = 1\$หาร\$5\$แต่\$1 \in S\$.
- ทางเลือก\$k=1\$ไม่ทำงานเนื่องจาก\$k+3 = 4\$ไม่แบ่ง\$5\$แต่\$3 \notin S\$.
- ทางเลือก\$k=2\$ผลงาน: \$k+1 = 3\$, \$k+2 = 4\$และ\$k+4 = 6\$อย่าแบ่ง\$5\$และ\$k+3 = 5\$หาร\$5\$.
กรณีทดสอบ
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
คำตอบ
05AB1E , 21 20 19 18 ไบต์
ขอบคุณKevin Cruijssenสำหรับ -1 ไบต์!
-1 ไบต์แรงบันดาลใจจากxash 's คำตอบ Brachylog !
[¼¾ƒ²L¾ÑN-K¹Qi¾N‚q
ลองออนไลน์!
หรือ
ลองใช้กรณีทดสอบส่วนใหญ่! (อ้างอิงจากชุดทดสอบโดยFryAmTheEggmanสำหรับคำตอบนี้)
# 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 ไบต์
บรรทัดแรกของอินพุตคือชุด\$S\$, อันที่สอง\$b\$.
[¼¾ƒ¾¹²L‚N+Ö_O¹gªËi¾N‚q
ลองออนไลน์!
สิ่งนี้จะวนซ้ำผ่านคู่ที่เป็นไปได้ทั้งหมดตามลำดับศัพท์และตรวจสอบแต่ละคู่:
\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*}
แสดงความคิดเห็น :
[ # 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 ไบต์
b!s=[(n,k)|n<-[1..],k<-[0..n],[x|x<-[1..b],mod n(k+x)>0]==s]!!0
ลองออนไลน์!
Python 3 , 110 91 89 ไบต์
บันทึกมหันต์19 21 ไบต์ขอบคุณJitse !!!
ระเบิด TIO เพราะความลึกของการเรียกซ้ำบ้า! :(
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)
ลองออนไลน์!
R , 92 86 85 83 82 ไบต์
แก้ไข: -2 ไบต์ขอบคุณ Giuseppe จากนั้นเพิ่มอีก -1 ไบต์ขอบคุณ 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))
ลองออนไลน์!
การทดสอบการเพิ่ม velues ของ n (ตามที่กำหนดเป็นจริงFที่นี่จะใช้ประโยชน์จากค่าเริ่มต้นค่าเริ่มต้นของการเป็นศูนย์) และสำหรับแต่ละลูปผ่านทั้งหมดkและผลตอบแทนF,kถ้าพวกเขาตอบสนอง!F%%(x+k) != x %in% Sทั้งหมดในx1:b
ตอนนี้ 6 ไบต์สั้นกว่าฉันก่อนหน้ารุ่น recursive , และมันจริงสามารถดำเนินการทุกกรณีการทดสอบโดยไม่จำเป็นต้องเพิ่มRวงเงิน recursion และขนาดสแต็จัดสรร
JavaScript (ES6), 85 83 82 ไบต์
คาดว่า(b)(s)ที่sเป็นชุด [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]}
ลองออนไลน์!
แสดงความคิดเห็น
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
} //
เยลลี่ 19 ไบต์
Ż⁴+þ⁸%T€i©
1ç1#‘,®’
โปรแกรมเต็มรูปแบบรับชุด\$S\$และขอบเขตบน\$b\$ซึ่งพิมพ์ตัวแปรเป็นรายการ\$[n,k]\$.
ลองออนไลน์!
หรือดูชุดทดสอบ (ไม่มีอินพุตที่ทำงานนานที่สุดสองอินพุต)
ให้ความกรุณาโดยFryAmTheEggman
อย่างไร?
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\$ 111109ไบต์
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);}
ลองออนไลน์!
ใช้เวลา\$S\$เป็นบิตมาสก์ที่มีความยาวกลับด้าน\$b\$และเอาต์พุต\$n\$และ\$k\$ถึง stdout.
คำอธิบาย
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
}
ถ่าน , 32 29 ไบต์
Ｗ¬№ωθ≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κωＩ⟦Ｌυ⌕ωθ
ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด ใช้เวลา\$ S \$เป็นบิตมาสก์ที่มีความยาวกลับด้าน\$ b \$และเอาต์พุต\$ n \$และ\$ k \$ในบรรทัดแยกกัน คำอธิบาย:
Ｗ¬№ωθ
ทำซ้ำจนกว่าจะพบ bitmask ที่ต้องการใน bitmask ปัจจุบัน
≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κω
เพิ่มขึ้น\$ n \$และคำนวณ bitmask แบบเต็มสำหรับ\$ 1 \leq k + x \leq n + b \$.
Ｉ⟦Ｌυ⌕ωθ
เอาท์พุท\$ n \$และดัชนี\$ k \$ของ bitmask อินพุต\$ S \$ ใน bitmask เต็มรูปแบบ
Brachylog 27 ไบต์
∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧
ลองออนไลน์!
มันทำงานอย่างไร
∧.Ċℕᵐ≥₁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 68 ไบต์
f:{n,e@n:{y+1-#x@y}[e:{*&&/'=[~x in y]'0=![;z]''+[x]'!1+z}[1+!x;y]]/1}
ลองออนไลน์!
TiO สามารถเรียกใช้ตัวอย่างยกเว้น6 [1] -> 3960 6และ8 [1,2,3,4,5] -> 5814 11เมื่อหมดเวลา
k4, 102 71 69 ไบต์
{n,e@n:{y+^x@y}[e:{*&&/'=[~x in y]'0=.q.mod[z;+[x]'!1+z]}[1+!x;y]]/1}
เรียกว่าเป็น{...}[b;S]. ใช้เวอร์ชันคอนเวอร์จ/เพื่อเพิ่มค่าของnการทดสอบต่อไปจนกว่าจะถูกต้องxและkระบุได้ ภายในe:, xถูกb, yเป็นSและเป็นzn
Husk , 38 33 28 22 24 ไบต์
การแก้ไข: -5 ไบต์ขอบคุณ Razetime จากนั้น -6 ไบต์ขอบคุณ Zgarb จากนั้น +2 ไบต์เพื่อแก้ไขข้อบกพร่องที่ไม่สามารถค้นหาโซลูชันที่kเป็นศูนย์
§,o←ḟVImλVö=²`Wḣ⁴`%¹+ŀ)N
ลองออนไลน์!
อาร์กิวเมนต์เป็นจำนวนเต็มbและรายชื่อS; (k,n)คู่ผลของจำนวนเต็ม
คำตอบHuskที่สองของฉันและฉันต้องใช้เวลานานกว่าจะทำงานได้ดังนั้นฉันจึงสงสัยว่ามันยังสามารถตีกอล์ฟได้ค่อนข้างมากโดย Razetime & Zgarb ...
ตรวจสอบค่าที่เพิ่มขึ้นnและคำนวณค่าต่ำสุดkที่สามารถตอบสนองS == (n%(b+k)>0)ได้ จากนั้นดึงค่านี้และดัชนีเป็นkและnตามลำดับ
แก้ไข:ในรูปแบบเดิมนี้พลาดการแก้ปัญหาที่มีค่าเท่ากับศูนย์ตั้งแต่นี้เป็นผลเช่นเดียวกับความล้มเหลวที่จะหาที่ถูกต้องk kตอนนี้แก้ไขเพื่อคำนวณk+1แล้วลบ 1 หลังจากดึงค่า
อย่างไร?
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 ไบต์
/,/;++$k>$n?$k=0*++$n:0until"@{[grep$n%($k+$_),1..$`]}"eq$';$_="$n $k"
ลองออนไลน์!
หรือเข้าใจน้อยกว่า 68 ไบต์
-lp, 68 ไบต์
/,/;++$\>$,?$\=0*++$,:0until"@{[grep$,%($\+$_),1..$`]}"eq$';$_="$, "
ลองออนไลน์!