Rock Paper Scissors

To solve this problem recursively, think of the game as a tree and you want to traverse all possible solutions depth-first.  That means going all the way down one branch first before moving back up to evaluate the previous level(s).

Screen Shot 2017-12-10 at 6.19.47 PM

Recursive Solution:

var rockPaperScissors = function(n) {
  var output = [];
  var choices = ['rock', 'paper', 'scissors'];
  n = n || 3;

  var makeCombo = function(movesPlayed, roundsLeft) {
    if (roundsLeft === 0){
      output.push(movesPlayed);
    } else {
       for (var i = 0; i < choices.length; i++) {
         makeCombo(movesPlayed.concat(choices[i]), roundsLeft - 1);
       }
    }
  }
  makeCombo([], n);
  return output;
};

 

Order of execution: 

1. makeCombo([], 3)
2. makeCombo([‘rock’], 2);
3. makeCombo([‘rock rock’], 1);
4. makeCombo([‘rock paper’], 1);
5. makeCombo([‘rock scissors’], 1);
6. makeCombo([‘rock rock rock’], 0);
7. push [‘rock rock rock’] to output
8. makeCombo([‘rock rock paper’], 0);
9. push [‘rock rock paper’] to output
10. makeCombo([‘rock rock scissors’], 0);
11. push [‘rock rock scissors’] to output

12. makeCombo([‘paper’], 2);

..

…. makeCombo([‘scissors’], 2);

 

 

 

Advertisements
Rock Paper Scissors

Hackerrank Day 22: Binary Search Trees

screen-shot-2016-12-29-at-3-06-56-pmscreen-shot-2016-12-29-at-3-07-05-pm

My Solution in Ruby: 

The Hacker Rank’s Tutorial was actually helpful in solving this.   It gave me the formula that’s essentially the solution to this challenge.

screen-shot-2016-12-29-at-3-09-04-pm

Basically, to find the height of a binary tree (the maximum distance from root node to leaf node):

  1. Find the height of the left child/subtree and right child/subtree
  2. Return the maximum between the two subtrees.
  3. Add 1 to it (because 1 is the height of the current parent node)
  4. Do this recursively as each node may have children.

screen-shot-2016-12-29-at-3-06-30-pm

Hackerrank Day 22: Binary Search Trees

Hackerrank Day 9: Recursion

Objective
Today, we’re learning and practicing an algorithmic concept called Recursion. Check out the Tutorial tab for learning materials and an instructional video!

Recursive Method for Calculating Factorial

screen-shot-2016-12-17-at-12-44-52-am

Task
Write a factorial function that takes a positive integer, as a parameter and prints the result of ( factorial).

Input Format

A single integer, (the argument to pass to factorial).

Output Format

Print a single integer denoting N!.

Sample Input

3

Sample Output

6

Explanation: 

  1. factorial(3) = 3 x factorial(2)
  2. factorial(2) = 2 x factorial(1)
  3. factorial(1) = 1

My solution:

Recursion is basically defining a base case and applying that base case to the function again to find results for other cases.

This example was easy because the explanation basically tells you how to code it, but once again, I struggled with reading and printing input in Hacker Rank..

Don’t forget to explicitly tell the code to print out the result of the function at the end!

screen-shot-2016-12-17-at-12-39-03-am

Hackerrank Day 9: Recursion

Wonky Coins

Catsylvanian money is a strange thing: they have a coin for every denomination (including zero!). A wonky change machine in Catsylvania takes any coin of value N and returns 3 new coins, valued at N/2, N/3 and N/4 (rounding down).

Write a method `wonky_coins(n)` that returns the number of coins you are left with if you take all non-zero coins and keep feeding them back into the machine until you are left with only zero-value coins.

Test Cases:

puts wonky_coins(1).should == 3
puts wonky_coins(5).should ==  11
# => [2, 1, 1]
# => [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
# => [[[0, 0, 0], 0, 0], [0, 0, 0], [0, 0, 0]]
puts wonky_coins(6).should == 15
puts wonky_coins(0).should == 1

My solution (w/ arrays and recursion): 

screen-shot-2016-11-28-at-10-25-19-pm

Jimmy’s solution (w/o recursion): 

The idea is you draw a coin from a pouch (array).  If the coin is 0, count it.  If it’s not, redraw another coin until the pouch is empty.

screen-shot-2016-11-28-at-10-25-36-pm

Provided solution (w/ recursion):

screen-shot-2016-11-28-at-10-25-46-pm

Wonky Coins