• Some users have recently had their accounts hijacked. It seems that the now defunct EVGA forums might have compromised your password there and seems many are using the same PW here. We would suggest you UPDATE YOUR PASSWORD and TURN ON 2FA for your account here to further secure it. None of the compromised accounts had 2FA turned on.
    Once you have enabled 2FA, your account will be updated soon to show a badge, letting other members know that you use 2FA to protect your account. This should be beneficial for everyone that uses FSFT.

Two puzzles.

S

serpretetsky

2[H]4U
2FA
Joined
Dec 24, 2008
Messages
2,211
I enjoyed this thread started by eLiu: http://forums.anandtech.com/showthread.php?t=2277519
and decided to start one here. Can't say mine are as fun, but oh well :p


1) Alicia always climbs steps 1, 2, or 4 at a time. For example, she climbs 4 steps by
1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2, or 4. In how many ways can she climb 10 steps?

2) Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

EDIT: almost forgot, if you already know the solutions, please don't post them. Give others a chance to try to discuss, work out, and post solutions.
 
Last edited:
It's also not from the movie originally. It's a famous problem called the Monty Hall problem, which has quite a bit of history if you want to read the wiki page about it.
 
My answer to #1 is 169.

Code: 
#!/usr/bin/perl
use strict;

sub next_node {
    my $current = shift;
    my $step = shift;
    my @prev = @{shift()};
    if($step != 0) {
        $current += $step;
        push(@prev, $step);
    }

    if($current == 10) {
        print join(',', @prev) . "\n";
    } elsif($current <= 10) {
        next_node($current, 1, \@prev);
        next_node($current, 2, \@prev);
        next_node($current, 4, \@prev);
    }
}
my @start = ();
next_node(0,0, \@start);
 
I made a Python test for the Monty Hall problem because I just started a few edX classes and have zero programming experience.

http://codepad.org/KVEBZgiR

Looks like it works! It assumes you pick door 1 every time and then if door 2 is a goat you switch to door 3, if door 2 is not a goat, then door 3 must be, so you switch to door 2.

This code trials it 100000 times.

Originally I tried to do it recursively, but I couldn't find a way to keep track of wins and total trials in the local function. :(
 
@Raekwon,
Just started as in, you've been through the 5 weeks of edx 6.00x and maybe a few weeks of cs50x?
 
ShoeLace said:
@Raekwon,
Just started as in, you've been through the 5 weeks of edx 6.00x and maybe a few weeks of cs50x?
Click to expand...

Yes, I'm through the first 5 weeks of 6.00x and I've watched the week 0 and week 1 lectures of cs50x, but haven't started the first weeks assignment yet. :cool:
 
jimmyb said:
My answer to #1 is 169.

Code: 
#!/usr/bin/perl
use strict;

sub next_node {
    my $current = shift;
    my $step = shift;
    my @prev = @{shift()};
    if($step != 0) {
        $current += $step;
        push(@prev, $step);
    }

    if($current == 10) {
        print join(',', @prev) . "\n";
    } elsif($current <= 10) {
        next_node($current, 1, \@prev);
        next_node($current, 2, \@prev);
        next_node($current, 4, \@prev);
    }
}
my @start = ();
next_node(0,0, \@start);
Click to expand...
you brute forcing maniac! i like it. Like you say, there is a more elegant solution, but i didn't even get this far.

It's interesting, the output of your program organizes the combinations in a way i was trying to achieve in my head (which correct me if im wrong, wasn't really your intention), a sort of pseudo-base-number organization. But because the length of the combination changes as you use 2 or 4 step sections, it kept getting me confused.

Example:
binary counting:
000 //increment the last digit by one
001 //carry over to next digit
010
011
100

Step counting:
1111111111 //increment the last digit by one
111111112 <--ughh, the number got shorter! weird!, oh well, increment again
1111114 <-- uggh, still weird! carry over to the next digit.
111111121 <-- kind of back on track?
11111122

your program doesn't quite output like that, but it's something similar.
 
Raekwon said:
I made a Python test for the Monty Hall problem because I just started a few edX classes and have zero programming experience.

http://codepad.org/KVEBZgiR

Looks like it works! It assumes you pick door 1 every time and then if door 2 is a goat you switch to door 3, if door 2 is not a goat, then door 3 must be, so you switch to door 2.

This code trials it 100000 times.

Originally I tried to do it recursively, but I couldn't find a way to keep track of wins and total trials in the local function. :(
Click to expand...
nice
out of 100,000 trials how many wins did you get by switching every time?
 
serpretetsky said:
you brute forcing maniac! [...]
Click to expand...

My program constructs a tree of all possible step sequences. When a node has a step count of 10 I halt construction and print out each step decision from trunk to leaf. I used a recursive implementation because it was quick to write.

The order that the sequences get printed out will be a variation on a depth-first search traversal (where only the leaf nodes get printed).
 
jimmy, inspired by the structure of your program i drew a tree, but didn't keep the branches separated for every combination.

stairs_problem-1.png


i guess thats one way to do it. BLEH.

the number in the diamond represents the step number. I decided i needed to separate them into 4 different rows. I then started from the right and put in the total number of combinations the step had to get to 10. 9 can get to 10 i only one way. 8 can get to 10 directly or using all the combinations of 9. 7 can get to 10 via 8's combinations or 9's combinations, etc.

I still don't like this solution
 
Last edited:
For problem one, brute forcing is certainly a way to do it, but what if you generalized to k steps and n different step denominations?

A very elegant solution that runs in polynomial time (unlike brute forcing which will be exponential with respect to n) would be to use dynamic programming.
 
mpoon2489 said:
For problem one, brute forcing is certainly a way to do it, but what if you generalized to k steps and n different step denominations?

A very elegant solution that runs in polynomial time (unlike brute forcing which will be exponential with respect to n) would be to use dynamic programming.
Click to expand...

I think this solution runs in O(kn) time.

Code: 
#!/usr/bin/perl
use strict;

my @paths = (1);
for my $i (1..10) {
    foreach my $delta (1,2,4) {
        $paths[$i] += $paths[$i - $delta] if($i >= $delta);
    }
}
print $paths[10] . "\n";
 
jimmyb said:
I think this solution runs in O(kn) time.

Code: 
#!/usr/bin/perl
use strict;

my @paths = (1);
for my $i (1..10) {
    foreach my $delta (1,2,4) {
        $paths[$i] += $paths[$i - $delta] if($i >= $delta);
    }
}
print $paths[10] . "\n";
Click to expand...

A very nice and concise way of using dynamic programming. :D

Now what if you wanted to return all the possible combinations instead of just how many?
 
I *think* if you want to actually report the paths explicitly then you can't do better than O(n^k), since the total number of paths is on that order. I'm open to counter-arguments however.
 
You must log in or register to reply here.
Back
Top