एक हत्यारे की पहेली की कल्पना || गणित ∩ प्रोग्रामिंग

Math3ma पर, ताई-डाने ब्रैडली ने निम्नलिखित पहेली साझा की, जिसे उन्होंने एक शानदार (स्पॉइलर-मुक्त) YouTube वीडियो में भी दिखाया। अगर आप ये पहली बार देख रहे हैं तो पहले वीडियो देखें.

xy-तल में एक वर्ग पर विचार करें, और A (एक “हत्यारा”) और T (एक “लक्ष्य”) को वर्ग के भीतर दो मनमाने-लेकिन-निर्धारित बिंदु होने दें। मान लीजिए कि वर्ग एक बिलियर्ड टेबल की तरह व्यवहार करता है, ताकि हत्यारे से कोई भी किरण (उर्फ “शॉट”) वर्ग के किनारों से टकराए, जिसमें घटना का कोण प्रतिबिंब के कोण के बराबर हो।

पहेली: क्या वर्ग में सीमित संख्या में अंक रखकर ए से टी तक किसी भी संभावित शॉट को रोकना संभव है?

यह पहेली मुझे ताई-डाने के वीडियो के माध्यम से, श्रेणी सिद्धांतकार एमिली रिहल के माध्यम से, हाल ही में मृत फील्ड्स मेडलिस्ट मरियम मिर्जाखानी की बातचीत के माध्यम से मिली, जिन्होंने समस्या का अधिक व्यापकता में अध्ययन किया। मैं उसके काम से परिचित नहीं हूं, लेकिन गणितज्ञों को जानते हुए यह संभवतः एक मनमाने जटिल $ n$-मैनिफोल्ड में सेट किया गया है।

प्रमाण के लिए ताई-डाने की पोस्ट देखें, जिसने मुझ पर ऐसी छाप छोड़ी कि मुझे और गहराई में जाना पड़ा। इस पोस्ट में मैं अपने द्वारा किए गए विज़ुअलाइज़ेशन पर चर्चा करूंगा – जिसे अब ताई-डाने के लेख के अंत में पोस्ट किया गया है – साथ ही यहां और नीचे (बिगाड़ने से बचने के लिए)। विज़ुअलाइज़ेशन में, माउस की गति हत्यारे के लिए फायरिंग की दिशा चुनती है, और लक्ष्य हरे रंग में होता है। माउस से लक्ष्य को खींचने से गार्ड की स्थिति अपडेट हो जाती है। स्रोत कोड Github पर है.

रूपरेखा

विज़ुअलाइज़ेशन d3 लाइब्रेरी का उपयोग करता है, जो विज़ुअलाइज़ेशन के लिए बनाया गया था जो डेटा के साथ गतिशील रूप से अपडेट होता है। मैं इसका उपयोग करता हूं क्योंकि यह एसवीजी को वास्तव में अच्छा बना सकता है।

विज़ुअलाइज़ेशन का सार दो ज्यामितीय कार्यों में है।

1. एक किरण को रेखा खंडों की एक श्रृंखला में विघटित करें – इसका पथ जब यह दीवारों से उछलता है – यदि यह विमान में किसी भी बिंदु को काटता है तो रुक जाता है।
2. सीमा वर्ग और हत्यारे तथा लक्ष्य की स्थिति को देखते हुए, गार्ड की इष्टतम स्थिति की गणना करें।

ये दोनों फ़ंक्शन, उनका समर्थन करने वाली सभी ज्यामिति के साथ, ज्यामिति.जेएस में हैं। बाकी डेमो को main.js में परिभाषित किया गया है, जिसमें मैं किसी कार्यशील उत्पाद पर चमत्कारिक ढंग से पहुंचने के लिए d3 सर्वोत्तम प्रथाओं को आसानी से रौंद देता हूं। आलोचकों का स्वागत है 🙂

अधिकांश प्रोग्रामिंग और सॉफ़्टवेयर समस्याओं की तरह, अपनी समझदारी बनाए रखते हुए इन कार्यों को लागू करने की कुंजी इसे प्रबंधनीय टुकड़ों में तोड़ना है। वृद्धिवाद आपका मित्र है.

सदिश, किरणें, आयत और किरण विभाजन

हम मानदंडों और आंतरिक उत्पादों को जोड़ने, स्केल करने और कंप्यूटिंग के लिए सहायक तरीकों के साथ एक वेक्टर वर्ग के साथ नीचे से शुरू करते हैं।

function innerProduct(a, b) {
  return a.x * b.x + a.y * b.y;
}

class Vector {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }

  normalized() { ... }
  norm() { ... }
  add(vector) { ... }
  subtract(vector) { ... }
  scale(length) { ... }
  distance(vector) { ... }
  midpoint(b) { ... }
}

यह किसी को दो बिंदुओं के बीच की दूरी की गणना करने की अनुमति देता है, उदाहरण के लिए, साथ vector.subtract(otherVector).norm().

आगे हम एक किरण के लिए एक वर्ग को परिभाषित करते हैं, जिसे उसके केंद्र (एक वेक्टर) और एक दिशा (एक वेक्टर) द्वारा दर्शाया जाता है।

class Ray {
  constructor(center, direction, length=100000) {
    this.center = center;
    this.length = length;

    if (direction.x == 0 && direction.y == 0) {
      throw "Can't have zero direction";
    }
    this.direction = direction.normalized();
  }

  endpoint() {
    return this.center.add(this.direction.scale(this.length));
  }

  intersects(point) {
    let shiftedPoint = point.subtract(this.center);
    let signedLength = innerProduct(shiftedPoint, this.direction);
    let projectedVector = this.direction.scale(signedLength);
    let differenceVector = shiftedPoint.subtract(projectedVector);

    if (signedLength > 0
        && this.length > signedLength
        && differenceVector.norm() 

हमें इसे खींचने के लिए किरण सीमित होनी चाहिए, लेकिन हमने जो लंबाई चुनी है वह इतनी बड़ी है कि, जैसा कि आप विज़ुअलाइज़ेशन में देख सकते हैं, यह प्रभावी रूप से अनंत है। इसे और भी अधिक समय तक बढ़ाने के लिए स्वतंत्र महसूस करें।

दिलचस्प बात इंटरसेक्शन फ़ंक्शन है। हम गणना करना चाहते हैं कि कोई किरण किसी बिंदु को काटती है या नहीं। ऐसा करने के लिए, हम एक रेखा से एक बिंदु की दूरी की गणना करने के लिए निर्णय नियम के रूप में आंतरिक उत्पाद का उपयोग करते हैं। यदि वह दूरी बहुत छोटी है, तो हम कहते हैं कि वे प्रतिच्छेद करती हैं।

हमारे डेमो पॉइंट्स अतिसूक्ष्म नहीं हैं, बल्कि इनके द्वारा वर्णित एक छोटा दायरा है intersectionRadius. कुछ भी देखने में सक्षम होने के लिए हम इसे 3 पिक्सेल पर सेट करते हैं। यदि यह बहुत छोटा है तो डेमो खराब दिखेगा। किरण तब नहीं रुकेगी जब उसे रुकना चाहिए, और जब नहीं रुकना चाहिए तो वह लक्ष्य से टकराती हुई प्रतीत हो सकती है।

आगे हमारे पास एक आयत के लिए एक कक्षा है, जहाँ जादू होता है। बॉयलरप्लेट और सहायक विधियाँ:

class Rectangle {
  constructor(bottomLeft, topRight) {
    this.bottomLeft = bottomLeft;
    this.topRight = topRight;
  }

  topLeft() { ... }
  center() { ... }
  width() { .. }
  height() { ... }
  contains(vector) { ... }

समारोह rayToPoints जो किरण को उछाल से रेखा खंडों में विभाजित करता है वह तीन सहायक कार्यों पर निर्भर करता है:

1. rayIntersection: आयत के साथ किरण के प्रतिच्छेदन बिंदु की गणना करें।
2. isOnVerticalWall: निर्धारित करें कि क्या कोई बिंदु आयत की ऊर्ध्वाधर या क्षैतिज दीवार पर है, यदि कोई बिंदु नहीं है तो एक त्रुटि उत्पन्न होगी।
3. splitRay: एक किरण को एक रेखा खंड में विभाजित करें और एक छोटी किरण जो आयत की दीवार से “उछाल” जाए।

(2) तुच्छ है, कुछ त्रुटि सहनशीलता तक कुछ x- और y-समन्वय दूरियों की गणना करना। (1) इसमें किरण को पैरामीटराइज़ करना और चार असमानताओं में से एक की जाँच करना शामिल है। यदि आयत के नीचे बाईं ओर $ (x_1, y_1)$ है और शीर्ष दाहिनी ओर $ (x_2, y_2)$ है और किरण को $ \{ (c_1 + t v_1, c_2 + t v_2) \mid t > 0 \}$ के रूप में लिखा गया है, तो – कुछ कोहनी ग्रीस के साथ – निम्नलिखित चार समीकरण ऊर्ध्वाधर या क्षैतिज किरणों के लिए कुछ विशेष मामलों के साथ, सभी संभावनाएं प्रदान करते हैं:

$$\displaystyle \begin{aligned} c_2 + t v_2 &= y_2 & \textup{ and } \hspace{2mm} & x_1 \leq c_1 + t v_1 \leq x_2 & \textup{ (शीर्ष पर प्रतिच्छेद करता है)} \\\ c_2 + t v_2 &= y_1 & \textup{ and } \hspace{2mm} & x_1 \leq c_1 + t v_1 \leq x_2 & \textup{ (नीचे प्रतिच्छेद करता है)} \\\ c_1 + t v_1 &= x_1 & \textup{ और } \hspace{2mm} और y_1 \leq c_2 + t v_2 \leq y_2 और \textup{ (बाएं प्रतिच्छेद करता है)} \\\ c_1 + t v_1 &= x_2 & \textup{ और } \hspace{2mm} और y_1 \leq c_2 + t v_2 \leq y_2 और \textup{ (दाईं ओर प्रतिच्छेद करता है)} \\\ \end{संरेखित}$$

कोड में:

  rayIntersection(ray) {
    let c1 = ray.center.x;
    let c2 = ray.center.y;
    let v1 = ray.direction.x;
    let v2 = ray.direction.y;
    let x1 = this.bottomLeft.x;
    let y1 = this.bottomLeft.y;
    let x2 = this.topRight.x;
    let y2 = this.topRight.y;

    // ray is vertically up or down
    if (epsilon > Math.abs(v1)) {
      return new Vector(c1, (v2 > 0 ? y2 : y1));
    }

    // ray is horizontally left or right
    if (epsilon > Math.abs(v2)) {
      return new Vector((v1 > 0 ? x2 : x1), c2);
    }

    let tTop = (y2 - c2) / v2;
    let tBottom = (y1 - c2) / v2;
    let tLeft = (x1 - c1) / v1;
    let tRight = (x2 - c1) / v1;

    // Exactly one t value should be both positive and result in a point
    // within the rectangle

    let tValues = (tTop, tBottom, tLeft, tRight);
    for (let i = 0; i  epsilon && this.contains(intersection)) {
        return intersection;
      }
    } 

    throw "Unexpected error: ray never intersects rectangle!";
  }

अगला, splitRay आयत के साथ किरण के प्रतिच्छेदन की गणना करके, और “शेष” किरण को आयत की दीवार पर स्थित एक नए केंद्र के साथ दृष्टिकोण की दिशा को प्रतिबिंबित करके, एक किरण को एक एकल रेखा खंड और “शेष” किरण में विभाजित करता है। नई किरण की लंबाई उचित रूप से कम है। यदि हमारी किरण की लंबाई समाप्त हो जाती है, तो हम बस एक खंड को शून्य किरण के साथ लौटा देते हैं।

  splitRay(ray) {
    let segment = (ray.center, this.rayIntersection(ray));
    let segmentLength = segment(0).subtract(segment(1)).norm();
    let remainingLength = ray.length - segmentLength;

    if (remainingLength 

जैसा कि आपने शायद अनुमान लगाया होगा, rayToPoints बस कॉल करता है splitRay बार-बार तब तक जब तक कि किरण किसी इनपुट “स्टॉपिंग पॉइंट” – एक गार्ड, लक्ष्य, या हत्यारे – से नहीं टकराती, अन्यथा हमारी सीमित किरण की लंबाई समाप्त हो गई है। आउटपुट मूल किरण के केंद्र से शुरू होने वाले बिंदुओं की एक सूची है, जिसके लिए आसन्न जोड़े को खींचने के लिए रेखा खंडों के रूप में व्याख्या की जाती है।

  rayToPoints(ray, stoppingPoints) {
    let points = (ray.center);
    let remainingRay = ray;

    while (remainingRay) {
      // check if the ray would hit any guards or the target
      if (stoppingPoints) {
        let hardStops = stoppingPoints.map(p => remainingRay.intersects(p))
          .filter(p => p != null);
        if (hardStops.length > 0) {
          // find first intersection and break
          let closestStop = remainingRay.closestToCenter(hardStops);
          points.push(closestStop);
          break;
        }
      }

      let rayPieces = this.splitRay(remainingRay);
      points.push(rayPieces.segment(1));
      remainingRay = rayPieces.ray;
    } 

    return points;
  }

यह हत्यारे की ओर से निकली गोली को निशाना बनाने के लिए पर्याप्त है। हर बार जब माउस चलता है तो इस विधि को बुलाया जाता है।

इष्टतम रक्षक

गार्ड की इष्टतम स्थिति की गणना करने का कार्य इनपुट के रूप में आयत, हत्यारे और लक्ष्य को लेता है, और आउटपुट के रूप में 16 बिंदुओं की एक सूची तैयार करता है।

/*
 * Compute the 16 optimal guards to prevent the assassin from hitting the
 * target.
 */
function computeOptimalGuards(square, assassin, target) {
...
}

यदि आप ताई-दाने का प्रमाण पढ़ेंगे, तो आपको पता चल जाएगा कि यह निर्माण किस लिए है

1. आयत के ऊपर, दाएँ और ऊपर+दाएँ पर लक्ष्य के दर्पणों की गणना करें। इस परिणामी चीज़ को कॉल करें 4-प्रतिबिंबित-लक्ष्य।
2. 4-मिरर-लक्ष्य आकार की पूरी चौड़ाई से छोड़ी गई तीन प्रतियों का अनुवाद करके, पूरी ऊंचाई से नीचे, और बाएं-और-नीचे दोनों का अनुवाद करके, 4-मिरर-लक्ष्यों को चार बार दोहराएं।
3. अब आपके पास लक्ष्य की 16 प्रतियां और एक हत्यारा है। यह हत्यारे-से-लक्ष्य-प्रतिलिपि तक 16 पंक्ति खंड देता है। इनमें से प्रत्येक रेखाखंड के मध्यबिंदु पर एक गार्ड रखें।
4. अंत में, गार्ड को मूल वर्ग में वापस लाने के लिए रिवर्स ट्रांसलेशन और रिवर्स मिररिंग लागू करें।

वर्डप्रेस एक घटिया ब्लॉगिंग प्लेटफ़ॉर्म होने के कारण मुझे इससे हटना होगा, नीचे दिए गए कोड स्निपेट जादुई रूप से गायब हो रहे हैं। मैंने जीथब लाइनों के लिंक भी शामिल किए हैं।

चरण 1 (सरल सहायक फ़ंक्शन जोड़ने के बाद Rectangle मिररिंग करने के लिए):

  // First compute the target copies in the 4 mirrors
  let target1 = target.copy();
  let target2 = square.mirrorTop(target);
  let target3 = square.mirrorRight(target);
  let target4 = square.mirrorTop(square.mirrorRight(target));
  target1.guardLabel = 1;
  target2.guardLabel = 2;
  target3.guardLabel = 3;
  target4.guardLabel = 4;

चरण दो:

  // for each mirrored target, compute the four two-square-length translates
  let mirroredTargets = (target1, target2, target3, target4);
  let horizontalShift = 2 * square.width();
  let verticalShift = 2 * square.height();
  let translateLeft = new Vector(-horizontalShift, 0);
  let translateRight = new Vector(horizontalShift, 0);
  let translateUp = new Vector(0, verticalShift);
  let translateDown = new Vector(0, -verticalShift);

  let translatedTargets = ();
  for (let i = 0; i 

चरण 3, मध्यबिंदुओं की गणना:

  // compute the midpoints between the assassin and each translate
  let translatedMidpoints = ();
  for (let i = 0; i  t.midpoint(assassin)));
  }

चरण 4, गार्ड को मूल वर्ग में वापस लौटाना, जितना लगता है उससे कहीं अधिक कठिन है, क्योंकि हत्यारे-से-लक्ष्य-प्रतिलिपि खंड का मध्यबिंदु वर्ग की उसी प्रतिलिपि में नहीं हो सकता है जिस पर लक्ष्य-प्रतिलिपि पर गोली चलाई जा रही है। इसका मतलब है कि आपको यह पता लगाना होगा कि कौन सा वर्ग मध्यबिंदु की भूमि की प्रतिलिपि बनाता है, और इसका उपयोग यह निर्धारित करने के लिए करें कि कौन से संचालन को उलटा करने की आवश्यकता है। इसका परिणाम इस विशाल समारोह का अंतिम खंड है।

  // determine which of the four possible translates the midpoint is in
  // and reverse the translation. Since midpoints can end up in completely
  // different copies of the square, we have to check each one for all cases.
  function untranslate(point) {
    if (point.x  square.bottomLeft.y) {
      return point.add(translateRight);
    } else if (point.x >= square.bottomLeft.x && point.y  square.topRight.y) {
      return square.mirrorTop(square.mirrorRight(point));
    } else if (point.x > square.topRight.x && point.y 

और इसमें बस इतना ही है!

यदि मेरे पास समय होता तो सुधार होता

मैं इस पहेली में कुछ सुधार करना चाहता हूं, लेकिन अभी समय नहीं मिला है (आखिरकार मैं एक किताब लिख रहा हूं!)।

1. गार्डों को इधर-उधर खींचने में सक्षम हो।
2. समाधान को “प्रकट” करने के लिए एक बटन के साथ, गार्ड के खाली सेट से नए गार्ड बनाएं।
3. एक टॉगल शामिल करें, जिसे दबाए जाने पर, वर्ग के पूरे क्षेत्र को अंधेरा कर दिया जा सकता है, जिस पर हत्यारा हमला कर सकता है। उदाहरण के लिए, यह आपको यह देखने की अनुमति देगा कि क्या लक्ष्य एकमात्र संभावित सुरक्षित स्थान पर है, या किसी दिए गए कॉन्फ़िगरेशन के लिए कई सुरक्षित स्थान हैं।
4. संभवतः संभावित रास्तों की संख्या के आधार पर, कुछ सीमा तक, संवेदनशील स्थानों को काला कर दिया जाए।
5. सबसे जटिल: एक मनमाना बहुभुज (उत्तल या नहीं!) का सामान्यीकरण, जिसके लिए कोई वैकल्पिक समाधान नहीं हो सकता है। विज़ुअलाइज़ेशन आपको 2-4 का उपयोग करके समाधान खोजने की अनुमति देगा।

यदि आप इनमें से किसी भी सुधार का प्रयास करते हैं तो पुल अनुरोधों का स्वागत है।

अगली बार तक!