आयत में चलने से बचें
एक आयत, एक आरंभ बिंदु और एक अंतिम बिंदु को देखते हुए, आरंभ से अंत तक कोई भी रास्ता ढूंढें जो आयत से बचा जाए।
उदाहरण
मान लीजिए आप \ _ पर थे$(1.5, -1.5)\$और आपको \ _ की जरूरत है$(2, 4)\$। हालांकि, वहाँ ऊपरी बाएँ कोने के साथ एक आयत है \$(1, 3)\$और निचले दाएं कोने \$(4, 1)\$आपके रस्ते मैं। यह इस तरह दिखेगा:
वहाँ (हरे) शुरू से (लाल) अंत तक जाने के लिए बहुत सारे रास्ते हो सकते हैं:
- आप \ _ के माध्यम से जा सकते हैं$(-3, 3)\$।
- आप \ _ जा सकते हैं$(-1.5, -0.5)\$और उसके बाद करने के लिए \$(-1, 4)\$।
- चूंकि आप असीम रूप से पतले हैं (अपनी दिनचर्या को पूरा करने के बाद), आप \ _ के माध्यम से जा सकते हैं$(4, 1)\$और \$(4, 3)\$।
- कई अन्य के बीच।
यहाँ उन तीन विकल्पों की तरह क्या है (पूर्ण आकार के लिए क्लिक करें):
चुनौती
एक प्रारंभिक बिंदु को देखते हुए \$S\$एक अंत बिंदु \$E\$, और ऊपरी छोड़ दिया और नीचे एक आयत का सही कोनों के लिए निर्देशांक (किसी भी प्रारूप में अपनी भाषा के लिए उचित, यदि आप चाहें तो जटिल नंबर सहित) अंक की एक श्रृंखला, उत्पादन \$A_1, A_2, \ldots, A_n\$किसी भी लम्बाई का ऐसा भाग जो रेखीय रैखिक पथ \ _$S \rightarrow A_1 \rightarrow A_2 \rightarrow \ldots \rightarrow A_n \rightarrow E\$आयत के आंतरिक भाग को नहीं काटता है। ध्यान दें कि:
- प्रारंभ बिंदु और अंत बिंदु आयत के अंदर नहीं होगा, न ही आयत के किनारे या कोने पर।
- आपका मार्ग आयत के कोनों और किनारों को छू सकता है, लेकिन आयत के अंदरूनी हिस्से को नहीं काटना चाहिए।
- आप उत्पादन कुछ भी नहीं, एक खाली सूची या इसी तरह अगर आप पार करने के लिए इच्छा हो सकती है \$S \rightarrow E\$ सीधे तौर पर।
- आप मान सकते हैं कि आयत में एक सख्ती से सकारात्मक चौड़ाई और ऊंचाई है।
- आपके दृष्टिकोण को सभी टेस्टकेस के लिए समान अंकों का उपयोग करने की आवश्यकता नहीं है।
- पथ में डुप्लिकेट बिंदु हो सकते हैं, और यदि आप चाहें, तो स्वयं को भी प्रतिच्छेद कर सकते हैं।
परीक्षण के मामलों
यहां, (sx,sy)प्रारंभ बिंदु है, (ex,ey)अंतिम बिंदु है, (tlx,tly)आयत का शीर्ष बाएं कोने (brx,bry)है और निचला दायां कोना है। ध्यान दें कि कल्पना से हमारे पास हमेशा होगा tlx < brxऔर tly > bry।
Input -> Sample output (one of infinite valid answers)
(sx,sy), (ex,ey), (tlx,tly), (brx,bry) -> ...
(1.5,-1.5), (2,4), (1,3), (4,1) -> (-3,3)
or (-1.5,0.5),(-1,4)
or (4,1),(4,3)
(-5,0), (5,0), (-1,1), (2,-2) -> (0,5)
or (-5,1),(5,1)
(0.5,-2), (0.5,1), (2,2), (4,-3) -> []
or (0.5,-0.5)
or (-1,-0.5)
स्कोरिंग
बाइट्स में सबसे छोटा कोड जीतता है।
जवाब
जावास्क्रिप्ट (ईएस 6), 66 57 बाइट्स
की उम्मीद है (Sx,Sy,Ex,Ey,[Tx,Ty],[Bx,By])। 3 अंक लौटाता है।
(S,s,E,e,T,B,[x,y]=T)=>[S>x&s<y?B:T,[B[0],y],E>x&e<y?B:T]
इसे ऑनलाइन आज़माएं!
तरीका
पहला बिंदु है \$(Bx,By)\$यदि प्रारंभ बिंदु ग्रे क्षेत्र या \ में है$(Tx,Ty)\$ अन्यथा।
दूसरा बिंदु हमेशा \ _ होता है।$(Bx,Ty)\$।
तीसरा बिंदु है \$(Bx,By)\$अगर अंत बिंदु ग्रे क्षेत्र या \ में है$(Tx,Ty)\$ अन्यथा।
पायथन 2 , 49 बाइट्स
lambda S,E,T,B:[(T*(L<B)+L+T)[::3]for L in S,T,E]
इसे ऑनलाइन आज़माएं!
53 बाइट्स
def f(S,E,T,B):
for L in S,T,E:L[L>B]=T[L>B];print L
इसे ऑनलाइन आज़माएं!
हम केवल क्षैतिज या ऊर्ध्वाधर खंडों से बाहर का रास्ता बनाते हैं, जिसका अर्थ है कि प्रत्येक चरण एक समन्वयित शब्द-सीढ़ी- शैली को बदलता है ।
हमारा रास्ता S->Eहमेशा आयत के ऊपरी बाएँ शीर्ष से होकर जाता है T।
S
?
T
?
E
हम से जाना Sकरने के लिए Tएक पिट स्टॉप उन दोनों के बीच एक संकर है कि के माध्यम से, या तो की समन्वय पहली या दूसरी बदलते Sकी है कि T:
S0, S1 S0, S1
S0, T1 or T0, S1
T0, T1 T0, T1
है यही कारण है कि, हम से जाना Sकरने के लिए Tखड़ी-से-क्षैतिज या क्षैतिज तो खड़ी कदम से।
हम उनमें से एक को आयत के इंटीरियर को पार करने से बचने के लिए चुनते हैं, हालांकि कई मामलों में या तो काम करेगा। पहला समन्वय बदलना तभी विफल हो सकता है जब हम सीधे आयत के सीधे हों, और दूसरा बदलने से केवल तभी विफल हो सकते हैं जब हम सीधे इसके ऊपर हों। हम उन दो मामलों को अलग करके देख सकते हैं कि हम बाएं या दाएं हैं B।
हम इसी तरह Eइसे जोड़ने के लिए अंत बिंदु को संकरण करते हैं T।
कोड में, तीन बिंदुओं में से प्रत्येक S, T, E को T और हाइब्रिड किया गया है। टी के लिए, संकरण इसे अपरिवर्तित छोड़ देता है। कोड का 53-बाइट संस्करण सूची उत्परिवर्तन का उपयोग करता है, जो एक गैर- lambdaफ़ंक्शन की आवश्यकता है । ऊपर 49-बाइट संस्करण यह सूची-कताई चाल के साथ करता है (T*(L<B)+L+T)[::3], के बराबर है [L+T,T+L][L<B][::3]।
49 बाइट्स
def f(B,*R):
for L in R:L[L>B]=R[1][L>B];print L
इसे ऑनलाइन आज़माएं!
B,S,T,Eदो-तत्व सूचियों के रूप में इनपुट लेता है ।
आर , 86 82 94 81 79 बाइट्स
संपादन: -4 बाइट्स स्टार्ट एंड एंड पॉइंट्स को आउटपुट नहीं करके, और फिर +12 -1 बाइट को बग को ठीक करने के लिए (नीचे देखें)
function(p,q,r,s=.5:-1)list(r[1+all(p*s>(z=r[1,]*s)),],r[2:3],r[1+all(q*s>z),])
इसे ऑनलाइन आज़माएं!
बिंदु से शुरू होने वाले निर्दिष्ट आयत कोनों में से एक पर सीधे जाता है *। फिर किसी भी गैर-निर्दिष्ट कोनों (आयत के किनारे) के पास जाता है, और वहां से एक निर्दिष्ट कोने तक (यह बैकट्रैक नहीं हो सकता है), जहां से यह सीधे अंतिम बिंदु तक जा सकता है।
यदि 90 बाइट्स के लिए आयत वास्तव में इस तरह से नहीं है, तो कार्यक्रम का थोड़ा संशोधित संस्करण किसी भी तरह के विस्फोट से बच सकता है ।
(* बग फिक्स: मैंने शुरू में माना था कि निकटतम निर्दिष्ट कोने हमेशा उपलब्ध थे, लेकिन यह जरूरी नहीं है कि आयत बहुत चौड़ी और सपाट हो, और शुरुआती बिंदु इसके नीचे हो लेकिन बाएं हाथ के करीब हो अंत, उदाहरण के लिए)।
C 125 बाइट्स
z(a,b){printf("%d:%d|",a,b);}d(m,n,p,q,r,s,u,v){(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}
इसे ऑनलाइन आज़माएं
कोड स्पष्टीकरण
z(a,b){printf("%d:%d|",a,b);} // print routine
d(m,n,p,q,r,s,u,v) // function take x0 y0 xa ya x1 y1 xb yb
// x0 y0 - top left corner of rectangle
// xa ya - start point a
// x1 y1 - bottom right corner of rectangle
// xa ya - end point b
{(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);
// 1st cross product to decide P1 (see below)
(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}
// 2nd cross product to decide P2 (see below)
तरीका
अगर हम से जाना एक करने के लिए ख नीचे तो हम पहले आयत कि निश्चित रूप से देखने के लिए जो विकर्ण की ओर देख कर पार करने के बिना एक साथ कनेक्ट करेगा पर एक बिंदु चुन सकते हैं एक नीचे हम चुनते हैं - पर है P1 । इसी तरह, अन्य विकर्ण के साथ b की स्थिति की तुलना करके हम एक दूसरा बिंदु P2 चुन सकते हैं जो आयत को पार किए बिना b से जुड़ जाएगा - जैसा कि आरेख में दर्शाया गया है। अब P1 और P2 हमेशा आयत को पार किए बिना कनेक्ट होंगे और हम कर रहे हैं। सूची है
P1
पी 2
(ध्यान दें कि हम कौन से विकर्ण हैं हम क्रॉस उत्पाद का उपयोग कर सकते हैं - यदि सकारात्मक एक पक्ष - यदि नकारात्मक दूसरे पक्ष।)
चारकोल , 19 बाइट्स
ＩＥ⟦θζη⟧Ｅι⎇⁼μ›ιε§ζμλ
इसे ऑनलाइन आज़माएं! लिंक कोड के वर्बोज़ संस्करण के लिए है। मैं इसका उपयोग अधिकांश दो बिंदुओं पर करना चाहता था, लेकिन मैं यह तय करने का एक आसान तरीका नहीं ले सका कि किस दिशा में कूदना है। मैंने तब एक तीसरे बिंदु को जोड़ने की कोशिश की, लेकिन यह जल्दी ही @ xnor के एल्गोरिथ्म के एक बंदरगाह में सरल हो गया। 4 ट्यूपल्स के रूप में इनपुट लेता है। स्पष्टीकरण:
⟦θζη⟧ List of points S, T, E
Ｅ Map over list
ι Current point
Ｅ Map over coordinates
›ιε Is the current point to the right of B
⁼μ If this is the appropriate coordinate
§ζμ Take the relevant coordinate from T
λ Otherwise keep the coordinate
Ｉ Cast to string
Implicitly print