StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is yet another way to do it. If there is sufficient interest, I will try to fill out the details tonight, but I can't right now because I have family responsibilities. Here is a stub of an implementation that should explain the algorithm:</p> <pre><code>low = 0 high = 1 bound = 2 answer = -1 while 0 != answer: mid = best_continued_fraction((low + high)/2, bound) while mid == low or mid == high: bound += bound mid = best_continued_fraction((low + high)/2, bound) answer = ask(mid) if -1 == answer: low = mid elif 1 == answer: high = mid else: print_success_message(mid) </code></pre> <p>And here is the explanation. What <code>best_continued_fraction(x, bound)</code> should do is find the last continued fraction approximation to <code>x</code> with the denominator at most <code>bound</code>. This algorithm will take polylog steps to complete and finds very good (though not always the best) approximations. So for each <code>bound</code> we'll get something close to a binary search through all possible fractions of that size. Occasionally we won't find a particular fraction until we increase the bound farther than we should, but we won't be far off.</p> <p>So there you have it. A logarithmic number of questions found with polylog work.</p> <p><strong>Update:</strong> And full working code.</p> <pre><code>#! /usr/bin/python from fractions import Fraction import readline import sys operations = [0] def calculate_continued_fraction(terms): i = len(terms) - 1 result = Fraction(terms[i]) while 0 < i: i -= 1 operations[0] += 1 result = terms[i] + 1/result return result def best_continued_fraction (x, bound): error = x - int(x) terms = [int(x)] last_estimate = estimate = Fraction(0) while 0 != error and estimate.numerator < bound: operations[0] += 1 error = 1/error term = int(error) terms.append(term) error -= term last_estimate = estimate estimate = calculate_continued_fraction(terms) if estimate.numerator < bound: return estimate else: return last_estimate def ask (num): while True: print "Next guess: {0} ({1})".format(num, float(num)) if 1 < len(sys.argv): wanted = Fraction(sys.argv[1]) if wanted < num: print "too high" return 1 elif num < wanted: print "too low" return -1 else: print "correct" return 0 answer = raw_input("Is this (h)igh, (l)ow, or (c)orrect? ") if answer == "h": return 1 elif answer == "l": return -1 elif answer == "c": return 0 else: print "Not understood. Please say one of (l, c, h)" ow = Fraction(0) high = Fraction(1) bound = 2 answer = -1 guesses = 0 while 0 != answer: mid = best_continued_fraction((low + high)/2, bound) guesses += 1 while mid == low or mid == high: bound += bound mid = best_continued_fraction((low + high)/2, bound) answer = ask(mid) if -1 == answer: low = mid elif 1 == answer: high = mid else: print "Thanks for playing!" print "I needed %d guesses and %d operations" % (guesses, operations[0]) </code></pre> <p>It appears slightly more efficient in guesses than the previous solution, and does a lot fewer operations. For 101/1024 it required 19 guesses and 251 operations. For .98765 it needed 27 guesses and 623 operations. For 0.0123456789 it required 66 guesses and 889 operations. And for giggles and grins, for 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (that's 10 copies of the previous one) it required 665 guesses and 23289 operations.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload