Jul 27
Playing with Problems II
I think playing with problems is such an important concept that I'm going to devote another short blog post to it. This time let's look at another fun problem: opening doors!
doors.png
There are n closed doors in a long corridor, numbered 1 to n. A person walks through and opens each door. Another person walks through and closes every alternate door. This continues with the i-th person toggling the state of every i-th door. How many doors are left open after the nth person is done?
(People have strange hobbies I guess! :-D) The problem itself is easy enough to understand. Let's whip out our editors and dash off a solution in no time!
but-wait.png
This is a terrible mistake!
Rushing to a Solution If we rush to a solution we will implement it something like this:
#include <iostream> #include <algorithm> #include <cmath> #include <assert.h> int doors_open(int n) { int doors[n]; long num = 0; std::fill(doors, doors+n, 0); for(int i = 1;i <= n;i++) { int p = i; while (p <= n) { doors[p-1] = !doors[p-1]; p += i; num++; } } return std::count(doors, doors+n, 1); }
Then we’ll spend time trying to optimize it (let’s use a bitset!) and use all the technical wizardry and deep knowledge we are so good at. However, our solution will remain O(nlog(n)) and become harder and harder to maintain.
Playing with the Problem If, instead, we play around with the problem for a bit we will begin to notice a pattern: Num Doors Doors Open 1 1 2 1 3 1 4 1, 4 5 1, 4 6 1, 4 7 1, 4 8 1, 4 9 1, 4, 9 10 1, 4, 9 Now we can clearly see a pattern.
But why does this happen? Well, stop here for a few minutes, play with the problem and I guarantee you'll figure it out! And, once we understand it the pattern, the solution becomes so much simpler!
wow.png
int doors_open(int n) { return std::sqrt(n); /* neat huh? */ }
The Explanation If you’ve played with the problem and still can’t figure it out – I’ll explain it for you. But before you read ahead, do promise you’ve tried it out yourself. Ok so if we think about it, door 1 will be touched only by person 1, door 2 will be touched by person 1 and 2, door 3 will be touched by person 1 and 3, and so on. In general door `i` will be touched by all the divisors of `i`. Door 6 Door 9 | | 1 2 3 6 1 3 9 (touched by) (touched by) Also if `a` touches a door then b = i / a also touches the same door! (If this seem complicated - please play with the problem and it'll all make sense!) So that means that for every `a` that touches the door there will be another `b` that simply undo's whatever `a` did! The only time this will not happen is when b == a. In other words - when i = a*a which only happens for perfect squares. If we want the count, all we need to know is how many perfect squares are there in the line of doors - which is sqrt(n)
As with my last post, I am hoping to show you how important (and fun) it can be to play with the problems given to you before trying to find a solution. This is a hard but excellent habit to cultivate and will stand you in good stead through your career.
int main(int argc, char* argv[]) { int num_doors_test[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 97, 128, 198, 234, 500, 700, 1243, 4000 }; int len = sizeof(num_doors_test)/sizeof(num_doors_test[0]); for(int i = 0;i < len;i++) { int num_doors = num_doors_test[i]; int num_open = doors_open_improved(num_doors); /* check */ assert(doors_open(num_doors) == num_open); std::cout << "For " << num_doors << " doors: " << num_open << " open\n"; } }
. . . . . . . . . .
Notify me on new blog posts
. . . . . . . . . .