Write pseudocode below, that, given a rand7() generator, generates rand5(). Now do the reverse, writing pseudocode that generates rand7(), given rand5().
I was once given the above as an interview question. I was able to solve it, but in a method that allowed for the possibility of endless calls to rand7(). I wondered to myself if there was a way to code rand5() without allowing for an infinite number of calls to rand7(). This is my proof that such a program is not possible. Comments welcome, and any pseudocode answers below will be upvoted!
This will be a proof by contradiction. Suppose such a program exists: a program that given a finite number of calls to rand7() outputs, with even distribution, the values 0-4 (a.k.a. functions as rand5()). Given that no matter the sequence of this program, it calls rand7() a finite number of times, find the path that requires the maximum number of calls to rand7(), which we will call n. From your original program, generate another program that always calls rand7() n times; it identical to your original program, but pads rand7() calls with no meaningful output if rand7() is to be called fewer than n times. This second program has 7^n possible paths, and outputs each of 0-4 an equal number of times. Given that 7^n/5 is not an integer (as 5 does not divide 7^n), this is a contradiction, and the original program can not exist.
Congratulations @cardsox425! You have received a personal award!
Click on the badge to view your own Board of Honor on SteemitBoard.
For more information about this award, click here
Congratulations @cardsox425! You received a personal award!
You can view your badges on your Steem Board and compare to others on the Steem Ranking
Vote for @Steemitboard as a witness to get one more award and increased upvotes!