दो घंटे के चश्मे हैं: एक पूरी तरह से \(4\) मिनट में चलता है, दूसरा \(7\) मिनट में चलता है। आप बिल्कुल \(9\) मिनट कैसे मापते हैं जब माप पहली बार घड़ियाँ शुरू होने पर शुरू होता है? दूसरी घड़ी, सेकंड गिनने और अनुमान लगाने की अनुमति नहीं है। आपको बस इतना करना है कि घंटे के चश्मे को पलट दें और देखें कि ऊपरी कक्ष कब खाली है। घूमने में कोई समय नहीं लगना चाहिए। हम जिस चीज़ की तलाश कर रहे हैं वह एक ऐसी प्रक्रिया है जिसमें वांछित समयावधि के अंत को केवल घंटे के चश्मे से पहचाना जा सकता है।
हम \(4\) मिनट वाली घड़ी को \(A\) और \(7\) मिनट वाली घड़ी को \(B\) कहते हैं। प्रारंभ में सारी रेत नीचे होती है। हम दोनों घड़ियों को एक ही समय पर पलट कर शुरू करते हैं; इस क्षण से खोजे गए \(9\) मिनट गिने जाते हैं। उसके बाद, आप हमेशा व्यापार कर सकते हैं जब शीर्ष पर एक घड़ी खाली हो जाती है। आप एक, एक या दोनों घड़ियों को नहीं पलट सकते, यहाँ तक कि एक को भी नहीं जो अभी भी चल रही हो। आप अगली बार इसके ख़त्म होने तक प्रतीक्षा करें। रोकने और निशान लगाने की अनुमति नहीं है; एक खाली घड़ी खड़ी रह सकती है. समाधान इस प्रकार दिखता है:
- मिनट पर \(0\) \(A\) और \(B\) शुरू हो जाते हैं।
- मिनट पर \(4\) \(A\) खाली है और फ़्लिप किया गया है। \(B\) अपरिवर्तित चलता रहता है।
- मिनट पर \(7\) \(B\) खाली है और फ़्लिप किया गया है। \(A\) में अभी भी \(1\) मिनट बाकी है।
- मिनट पर \(8\) \(A\) खाली है। \(B\) में ठीक \(1\) मिनट तक रेत नीचे बहती रही; इसलिए \(B\) को तुरंत फिर से पलट दिया जाता है।
- मिनट पर \(9\) \(B\) खाली है। जिस समय की आप तलाश कर रहे थे वह समय आ गया है।
\(8\) मिनट पर हम घड़ी \(B\) जो अभी भी चल रही है। \(7\) मिनट पर उनके पुनः आरंभ होने के बाद से, उतनी ही रेत नीचे बह गई है जितनी \(1\) मिनट में बाधा के माध्यम से समा जाएगी। पलटने के बाद यह छोटी सी रकम ही ऊपर रह जाती है। अब इसे फिर से नीचे टपकने में \(1\) मिनट का समय लगता है। इसलिए घड़ी मिनट \(9\) पर खाली हो जाती है, एक और पूर्ण चलने के बाद नहीं। इसलिए हम आखिरी मिनट को उस रेत से मापते हैं जो पहले ही गुजर चुकी है। एनीमेशन इस चाल को दिखाता है:
सामान्य समाधान के लिए चालू घंटे के चश्मे को पलटना भी उपयोगी है। शेष समय से हमारा तात्पर्य उस समय से है जब रेत को ऊपरी कक्ष में प्रवाहित होने की अभी भी आवश्यकता है। यदि पूरी घड़ी का चलने का समय \(c\) है और इसका शेष चलने का समय \(r\) है, तो नीचे रेत की मात्रा अवधि \(cr\) से मेल खाती है। जब आप इसे पलटते हैं, तो यह सटीक राशि शीर्ष पर आ जाती है। यदि ऊपरी कक्ष पहले से भरा हुआ है, तो यह बाद में खाली हो जाएगा और इसके विपरीत। आंशिक रूप से चलने वाली घड़ी के लिए, नया शेष चलने का समय \(r'\):
$$r'=c-r.$$
पहले, माप पहली बारी से शुरू होता था। इसका मतलब है "बिना लीड टाइम के": शुरुआत के बाद से हर मिनट मायने रखता है। दूसरी ओर, "अग्रिम के साथ" का अर्थ है कि आप घड़ियाँ पहले तैयार कर सकते हैं और वांछित समय अवधि बाद में शुरू होती है। उदाहरण के लिए, हम दोनों घड़ियाँ शुरू करते हैं और \(A\) मिनट पर \(4\) घुमाते हैं। यदि \(B\) मिनट \(7\) पर खाली हो जाता है, तो हमारा माप शुरू हो जाता है। यदि \(A\) मिनट \(8\) पर खाली हो जाता है, तो यह समाप्त हो जाता है। हमने \(1\) मिनट मापा; पिछले \(7\) मिनटों की गिनती नहीं होती।
अब हम सकारात्मक पूर्णांक रनिंग टाइम \(a\) और \(b\) के साथ मनमाना घंटे के चश्मे पर विचार करते हैं। हम वांछित अवधि को \(T\) कहते हैं। यदि तैयारी की अनुमति हो तो इससे कौन से समय को मापा जा सकता है? यहां भी, शुरुआत और अंत को खाली जगह से पहचाना जाना चाहिए। इसलिए आपको अपनी भावना के आधार पर किसी बिंदु पर माप शुरू नहीं करना चाहिए। हैंडल वास्तविक पहेली के समान ही रहते हैं। पहले हम दिखाते हैं कि कौन से समय को बाहर रखा गया है; फिर हम आपको दिखाएंगे कि वास्तव में बाकी सब कैसे मापें।
आइए सबसे पहले \(6\) और \(10\) मिनट वाली घड़ियाँ लें। दोनों चलने का समय \(2\) से विभाज्य है। इसलिए रेत को मानसिक रूप से भागों में विभाजित किया जा सकता है, जिनमें से प्रत्येक को पूरा करने में \(2\) मिनट लगते हैं। जब आप इसे पलट देते हैं या अगली बार इसके खाली होने तक प्रतीक्षा करते हैं, तो केवल पूरे हिस्से ही दोबारा बनते हैं। इसलिए सभी अवलोकन योग्य खाली समय मिनटों की एक समान संख्या में होते हैं। आप इसका उपयोग \(3\) मिनट की अवधि मापने के लिए नहीं कर सकते, भले ही आप पहले से अपनी इच्छानुसार घड़ियाँ तैयार कर लें।
सामान्य तौर पर, मान लीजिए कि \(g=\gcd(a,b)\) चालू समय का सबसे बड़ा सामान्य भाजक है। प्रारंभ में शेष दोनों पद \(g\) के गुणज हैं। घुमाए जाने पर \(r\) या तो \(ar\) या \(br\) बन जाता है; दोनों \(g\) से विभाज्य रहते हैं। प्रतीक्षा करते समय, सबसे छोटा सकारात्मक शेष समय बीत जाता है, जो कि \(g\) का गुणज भी है। इसका मतलब यह है कि सभी खाली समय और उनकी दूरियां \(g\) के गुणक बनी रहती हैं। इसलिए एक मापने योग्य अवधि को \(g\mid T\) संतुष्ट करना चाहिए: \(T\) \(g\) से विभाज्य होना चाहिए। यह देखना अभी बाकी है कि क्या यह पर्याप्त है।
ऐसा करने के लिए, हम दोनों घड़ियों को बार-बार पूरी तरह से चलने देते हैं और जैसे ही यह खाली हो जाती है, प्रत्येक को पलट देते हैं। पहला \(a,2a,3a,\ldots\) समय इकाइयों के बाद खाली हो जाता है, दूसरा \(b,2b,3b,\ldots\) के बाद खाली हो जाता है। हम दूसरी घड़ी का समय \(mb\) और पहली घड़ी का बाद का समय \(na\) ढूंढ रहे हैं, जिसके ठीक बीच में \(T\) है। यदि \(T\) \(g\) का एक धनात्मक गुणज है, तो बेज़आउट का लेम्मा पूर्णांक \(n,m\) मिलान की गारंटी देता है। आप जिस रिश्ते की तलाश कर रहे हैं वह है::
$$na-mb=T.$$
बेज़ाउट द्वारा प्रदान की गई संख्याएँ \(n,m\) प्रारंभ में नकारात्मक हो सकती हैं। नकारात्मक रन नहीं चलाए जा सकते. हालाँकि, कोई समय अंतराल को बदले बिना दोनों संख्याओं को बढ़ा सकता है: हम उन्हें \(n+kb/g\) और \(m+ka/g\) से प्रतिस्थापित करते हैं, जहां \(k\) एक पर्याप्त बड़ा सकारात्मक पूर्णांक है। इसलिए दोनों समयों को समान राशि \(kab/g\) से स्थानांतरित किया जाता है; उनका अंतर \(T\) रहता है। तो दोनों संख्याएँ सकारात्मक हो जाती हैं और आवश्यक समय वास्तव में घड़ियाँ शुरू होने के बाद होता है।
अब आप प्रत्येक घड़ी का पूरा चक्र गिनें। जब \(m\) घड़ी खाली हो जाती है तो माप शुरू हो जाता है; यह तब समाप्त होता है जब पहली घड़ी \(n\) -वीं बार खाली हो जाती है। बीच में बिल्कुल \(T\) समय इकाइयाँ हैं। तैयारी में काफी समय लग सकता है. प्रमाण किसी विशेष छोटी प्रक्रिया का वादा नहीं करता है। \(T=0\) के लिए शुरुआत और अंत मेल खाते हैं। यह सभी गैर-नकारात्मक पूर्णांक उद्देश्यों के लिए साबित होता है: तैयारी के साथ, एक अवधि को मापा जा सकता है यदि और केवल तभी जब सबसे बड़ा सामान्य भाजक इसे विभाजित करता है:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
यह नियम जरूरी नहीं कि पहली शुरुआत में ही माप शुरू करने पर लागू हो। उदाहरण के लिए, \(4\) और \(7\) मिनट \(g=1\) के साथ, लेकिन \(1\) मिनट के बाद कोई घड़ी खाली नहीं है। इसलिए आप इस मिनट का अंत नहीं देख सकते। ऊपर वर्णित मिनट \(7\) से \(8\) तक का माप केवल इसलिए काम करता है क्योंकि तैयारी की गिनती नहीं होती है। इस प्रकार प्रमाण इस प्रश्न का उत्तर देता है कि तैयारी के बाद क्या संभव है। यदि आप तैयारी के साथ या बिना तैयारी के किसी अनुमत प्रक्रिया की तलाश में हैं, तो निम्नलिखित व्यवस्थित खोज से मदद मिलेगी।
PHP स्क्रिप्ट शेष चलने के समय और माप की शुरुआत के बाद से बीते समय दोनों को याद रखती है। ऐसी हर स्थिति के लिए, यह सब आज़माएँ \(4\) संभावनाएँ: कोई घड़ी नहीं, केवल पहली, केवल दूसरी या दोनों को पलट दें। इसके बाद यह अगली बार खाली होने तक प्रतीक्षा करता है। मूल्य \(-1\) तैयारी का संकेत देता है; प्रविष्टि start माप का समय निर्धारित करता है \(0\). ज्ञात स्थितियों की दोबारा जांच नहीं की जाएगी. पाया गया अनुक्रम इसके पूर्ववर्तियों के माध्यम से प्राप्त किया गया है। wait केवल अगले खाली होने की दूरी को संदर्भित करता है, अतिरिक्त समय माप को नहीं:
<?php
declare(strict_types=1);
function hourglass(int $a, int $b, int $target, bool $prepare = false): ?array
{
if ($a <= 0 || $b <= 0 || $target < 0) {
throw new InvalidArgumentException('Positive capacities, nonnegative target required.');
}
$root = [0, 0, $prepare ? -1 : 0];
$key = static fn(array $s): string => implode(',', $s);
$queue = new SplQueue();
$queue->enqueue($root);
$previous = [$key($root) => null];
$enqueue = static function (array $next, array $from, array $action)
use ($queue, &$previous, $key): void {
$k = $key($next);
if (!array_key_exists($k, $previous)) {
$previous[$k] = [$key($from), $action];
$queue->enqueue($next);
}
};
while (!$queue->isEmpty()) {
$state = $queue->dequeue();
[$x, $y, $elapsed] = $state;
if ($elapsed === $target) {
$path = [];
for ($k = $key($state); $previous[$k] !== null;) {
[$k, $action] = $previous[$k];
$path[] = $action;
}
return array_reverse($path);
}
if ($elapsed === -1) {
$enqueue([$x, $y, 0], $state, ['start' => true]);
}
for ($mask = 0; $mask < 4; ++$mask) {
$u = ($mask & 1) ? $a - $x : $x;
$v = ($mask & 2) ? $b - $y : $y;
if ($u === 0 && $v === 0) {
continue;
}
$wait = $u === 0 ? $v : ($v === 0 ? $u : min($u, $v));
$nextTime = $elapsed < 0 ? -1 : $elapsed + $wait;
if ($nextTime > $target) {
continue;
}
$enqueue(
[max(0, $u - $wait), max(0, $v - $wait), $nextTime],
$state,
['flip' => $mask, 'wait' => $wait]
);
}
}
return null;
}
foreach ([[4, 7, 9, false], [4, 7, 1, false], [4, 7, 1, true],
[6, 10, 3, true], [5, 5, 10, false], [4, 7, 0, false]] as $case) {
echo json_encode($case), ': ', json_encode(hourglass(...$case)), PHP_EOL;
}
खोज एक अनुमत प्रक्रिया ढूंढती है या लौटाती है null, यदि कोई मौजूद नहीं है. इसमें सभी अनुमत निरंतरताएं शामिल हैं और इसके लिए अधिकतम तैयारी की आवश्यकता होती है \((a+1)(b+1)(T+2)\) राज्य. इसलिए बड़े इनपुट के लिए बहुत अधिक मेमोरी की आवश्यकता होती है। खोज ट्रांज़िशन की संख्या कम की गई है, तैयारी का समय नहीं। तर्कसंगत संचालन और लक्ष्य समय को एक सामान्य विभाजक का उपयोग करके पूर्ण संख्याओं में परिवर्तित किया जाता है। उदाहरण के लिए, सामान्य समय इकाई के बिना रनटाइम के लिए \(1\) तथा \(\sqrt{2}\), यह परिमित पूर्णांक खोज उपयुक्त नहीं है.