You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Smartdown Notebooks via bl.ocks.org (Draft Tutorial v3)
Smartdown is currently in a beta-testing phase, and the source code is not yet publicly available, although the plan is to make it open source once it stabilizes more.
This tutorial is best experienced in raw mode. Please continue at README
This tutorial describes how to author a simple Smartdown example, extend it, and then make it available for show-and-tell via bl.ocks.org and via the Smartdown Viewer. Thanks for your patience and help in building a better Smartdown experience.
Smartdown is an accessible, yet powerful, way to author and explore ideas, be they technical, philosophical, or artistic. By design, it is an open format building upon other open standards and open source technology. Smartdown notebooks may be published via a variety of existing platforms and tools, including WordPress and GitHub Pages.
Recently, I've begun to use bl.ocks.org as a platform for sharing and publishing Smartdown notebooks and fragments. About Blocks describes the site as:
Bl.ocks (pronounced "Blocks") is a simple viewer for sharing code examples hosted on GitHub Gist.
but in my opinion it is a very powerful tool and the author, Mike Bostock has done a wonderful job in making it practical and fun.
The best way to experience Smartdown and this tutorial is via the Block link, which focuses on the Smartdown content and hides the details of the component files.
Recently, while talking with three mathematicians, I said that I use the following simple question to determine whether a potential software engineer is credible. It's a horrible and biased and possible useless test, but so far it has proven surprising in the amount of fail it generates. My question is roughly:
If $x$ times $x$ is $9$, then what is $x$?
One of the mathematicians, Jake Potter, said that the question was silly and insulting to ask of a mathematician, and I asked him what a better question was for mathematicians. This is the problem he then relayed.
The Battery Problem
Assume that you have $8$ batteries, and that $4$ of them are good, and $4$ of them are bad. You have a battery tester (a light bulb) that requires two good batteries to light up. Anything less than that will not light the bulb at all.
What is the minimum number of pairwise tests required to find at least one pair of good batteries.
Basic Analysis
I am NOT a mathematician, although I do love mathematics and am comfortable with it. But I think my brain is oriented towards something else, and the following discussion follows my imperfect and suboptimal thinking about the problem, rather than a final perfect solution.
If we evaluate all pairs of batteries, then it will take
of these tests will be successful. So the worst case would be if all of the successful tests were last, meaning that $28 - 6 = 22$ tests would be sufficient in that worst case.
The problem with the above solution is that we are determining more information than is demanded by the problem, and that comes at a cost of extra testing. So from an engineering point of view it is suboptimal. From the problem statement of finding the minimum number of tests, it is not a solution.
Determining some information
So let's start out with the basic idea of randomly choosing one battery (call it A), and comparing it with the remaining $7$ batteries (B through H). So we'd expend $7$ tests and if they all failed, we'd know that A was a bad battery, and we'd know nothing about the remaining $7$ batteries. It's the same as if we did the first $7$ tests of our worst-case $28$ tests. So we know that $7$ tests are sufficient to identify one battery's goodness, and that $28$ tests are sufficient to identify all pairs of good batteries.
But we can do better, since we know that there are $4$ good batteries, and the problem doesn't care if we identify all good batteries, it only wants at least one pair.
Being Smarter
Rather than relying upon a predefined set of tests that will be performed and provide us with all of the successful pairs, we can instead using a dynamic programming approach where we use the results of early tests to inform the structure of our test regime.
One of the flaws of testing battery A against batteries B...H ignores the fact that we know that at least$3$ batteries in the latter set must be good (because we know that there are $4$ good batteries). This means that if we test battery A against $4$ other batteries and it fails to light, then we know that either A is a bad battery, or that A is good and we randomly tested against the $4$ bad batteries. So an additional test is necessary to determine which of these is the case. So $5$ tests is required to determine A's badness in the worst case.
So.... $5$ tests can determine that either A is bad OR we will have a successful lighting of A and some other battery, which means that we win.
What if A is bad?
Suppose we exhaust our $5$ tests and have determined that A is bad, because we were unable to light the light in $5% tests. Now we throw away A and look at a new subproblem, which has $7$ batteries, $4$ of which are known to be good, and $3$ bad. Let's call the first element of this new set B, for consistency, and try to apply similar reasoning.
By the same logic as above, in the worse case, B is good, but we won't know that until we test against the $3$ bad batteries and finally light the light on the $4$th test. So we need $4$ additional tests just to determine B's goodness.
So it would appear that in the worst case (A is bad and B is bad), we need $5 + 4 = 9$ tests to determine this, leaving behind $2$ bad batteries and $4$ good ones.
Rinse and Repeat
By the same logic as above, we can use $2$ tests to determine whether C is bad, leaving behind $1$ bad battery and $4$ good ones. And that will require one additional test to determine whether D is bad (meaning any of E through H are good), or D is good, meaning D and any of F through H are good.
Final Answer
$5 + 4 + 3 + 2 = 14$ tests.
But it's wrong!
Just brainstorming an alternate strategy for reducing the problem complexity...
Let's suppose we divide (randomly) the set of $8$ into two sets of $4$, where all that e know is that each set may have from $0...4$ good and $0...4$ bad batteries. Can this help us? Doesn't seem likely.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
