#!/usr/bin/env python
# coding: utf-8

# ![alt text](https://github.com/callysto/callysto-sample-notebooks/blob/master/notebooks/images/Callysto_Notebook-Banner_Top_06.06.18.jpg?raw=true)

# # The Frog Jumping Problem
# 
# #### In this Callysto Notebook, we present a lesson that was first taught to Grade 4/5 students at Wishart Elementary School in Colwood, and Grade 7/8 students at Coast Mountain Academy in Squamish.
# 
# #### To use this Notebook, repeatedly click the "Run" button above, until you reach the end.  The teacher manual is embedded in this Notebook, marked in <font color='red'>red</font>.
# 
# ##### Written by Richard Hoshino

# #### <font color='red'>There are two ways to introduce the Frog Jumping Problem.  The first way is to show the following YouTube video, which presents the problem and walks the students through the scenario with 3 red frogs and 3 green frogs.  To play the video, click the triangular "Play" button appearing in the middle of the video's screen.</font>
# 
# #### <font color='red'>If you do show the video, make sure you cut off the video at the 2:30 mark, just after the solution is revealed.</font>
# 
# #### <font color='red'>The second (and better) way to introduce the Frog Jumping Problem is to invite six students to come up to the front of the classroom.  They will sit in a line of seven chairs, with an empty chair in the middle.  The three students on the left will be the red frog team, and the three students on the right will be the green frog team.  If you have access to coloured gym pinnies, have each student put on a red or green pinny corresponding to their team colour.</font>
# 
# #### <font color='red'>Now introduce the rules: the red team can only move to the right, and the green team can only move to the left.  On any move, a student can either <i>Slide</i> into the empty chair, or a <i>Jump</i> over one player from the other team into the empty chair.  The goal is to have the two teams swap positions, where the green team ends up on the left and the red team ends up on the right.</font>
# 
# #### <font color='red'>If the six students are ever stuck, and cannot make a legal move, then they have to start from the beginning.  They are to keep going until the game is solved, where the three green students are on the left and the three red students are on the right.</font>
# 
# #### <font color='red'>Students will need to be reminded that reds can only jump over greens, and vice versa.  Also, in each jump, a player can only jump over one player from the opposite colour.</font>
# 
# #### <font color='red'>Have the six students try to solve the game, either working amongst themselves, or enlisting the help of everyone else in the class.  I highly recommend that the students attempt this without talking.  When I lead this activity, I say this to the students: "you may communicate in any way that you wish, but you can't use words". </font>
# 
# #### <font color='red'>The solution appears in the YouTube video below.  If we denote the team names as Green (G) and Red (R), this sequence of fifteen moves solves the problem: G, R, R, G, G, G, R, R, R, G, G, G, R, R, G</font>
# 
# 

# ## Let's play the Frog Jumping game! 
# ### The YouTube video teaches us the rules of this game.

# In[1]:


#Import Youtube Video
from IPython.display import YouTubeVideo
YouTubeVideo('R8wkhae4Pvg')


# #### <font color='red'>Now have your students pair up, open up a shared computer, load this Notebook, and play the Frog Jumping Game on the computer.  To do so, they need to keep hitting the Run button until they see the game below, with a bunch of smiling red and green frogs on a log.</font>
# 
# #### <font color='red'>Have your students solve all three games: where the total number of red and green frogs is 4, 6, and 8.  To move a frog (either a Slide or a Jump), you just need to click on that frog.</font>
# 
# #### <font color='red'>Have them keep track of the moves they make, so they can list the <i>move sequence</i> that solves the game.  Assuming the green frog moves first, the correct move sequences are:</font>
# 
# #### <font color='red'>For 4 frogs: G, R, R, G, G, R, R, G</font>
# 
# #### <font color='red'>For 6 frogs: G, R, R, G, G, G, R, R, R, G, G, G, R, R, G </font>
# 
# #### <font color='red'>For 8 frogs: G, R, R, G, G, G, R, R, R, R, G, G, G, G, R, R, R, R, G, G, G, R, R, G </font>
# 
# #### <font color='red'>This is not at all obvious, but it turns out that there is only one solution to the problem if the green frog moves first, and only one solution to the problem if the red frog moves first.  In all moves (other than the initial move), whenever there are two possible moves, one of these moves will lead to the team becoming stuck.  This is why the solution is unique.   
# 
# 
# 

# ## Now you play the Frog Jumping game!

# In[2]:


get_ipython().run_cell_magic('html', '', '<link rel="stylesheet" href="style.css">\n    <div class="frogNum">\n        <label for="frogs"><strong>Choose number of frogs: </strong></label>\n        <select name="frogs" id="frogNumberSelector">\n            <option value="2" selected>4 Frogs</option>\n            <option value="3">6 Frogs</option>\n            <option value="4">8 Frogs</option>\n        </select>\n    </div>\n    <div class="mainGrid">\n        <ul id="frogList" class="frogGrid">\n            <li class="btns" onclick="resetFrogs()"><span>Reset</span></li>\n            <li class="btns" onclick="undo()"><span>Undo</span></li>\n            <li class="counter">Your moves: <span id="counter">0</span></li>\n        </ul>\n    </div>\n    \n        <div>\n        <table id="moveTable">\n            <tr>\n                <th>Step Number</th>\n                <th>Current Position</th>\n                <th>Move</th>\n            </tr>\n        </table>\n    </div>\n\n    <script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha256-3edrmyuQ0w65f8gfBsqowzjJe2iM6n0nKciPUp8y+7E="\n        crossorigin="anonymous"></script>\n    <script src="main.js"></script>\n')


# #### <font color='red'>Write down the correct move sequences on the board, and ask students if they notice any patterns.  They might notice that the number of moves required is 8, 15, and 24, respectively.  Perhaps it's not a coincidence that 8=2x4, 15=3x5, and 24=4x6.  They can use this information to predict the number of moves that will be required to solve larger instances of the problem, which they will do momentarily.    
#     
# #### <font color='red'>Another key insight is that the letters G and R in the move sequence occur in <i>blocks</i>.  So what we can do is express the move sequences as a code of numbers, where each number represents how many consecutive moves of that colour we make.  For example, the sequence G, R, R, G, G, R, R, G can be thought of as 1G, 2R, 2G, 2R, 1G, and we can write this as 12-2-21.    
# 
# #### <font color='red'>For 4 frogs: G, R, R, G, G, R, R, G is equal to the code 12-2-21</font>
# 
# #### <font color='red'>For 6 frogs: G, R, R, G, G, G, R, R, R, G, G, G, R, R, G is equal to the code 123-3-321</font>
# 
# #### <font color='red'>For 8 frogs: G, R, R, G, G, G, R, R, R, R, G, G, G, G, R, R, R, R, G, G, G, R, R, G is equal to the code 1234-4-4321</font>
# 
# #### <font color='red'>And now the pattern will be clear to the students.  For 10 frogs, with five of each colour, the correct code is 12345-5-54321, and they can use this code to create the desired move sequence of G's and R's.  Bring 10 volunteers up to the front of the class to illustrate this, to show how the move sequence G-RR-GGG-RRRR-GGGGG-RRRRR-GGGGG-RRRR-GGG-RR-G solves the problem with 5 green frogs and 5 red frogs.</font>
#     
# #### <font color='red'>This is a beautiful illustration of computational thinking and mathematical problem-solving, where we solve smaller simpler problems to find patterns and use these patterns to solve harder problems.</font> 

# ## Below is a Python program that takes YOUR move sequence, and applies it to the starting position.

# In[3]:


def play_game(starting_position, move_sequence):
    
    Rlist=[]
    Glist=[]
    Empty=0
    totalmoves=0
    counter=0
    flag=0

    for i in range(0,len(starting_position)):
        if starting_position[i]=='R':
            counter+=1
            Rlist.append(counter)
        if starting_position[i]=='G':
            counter+=1
            Glist.append(counter)
        if starting_position[i]=='_':
            counter+=1
            Empty=counter

    startRlist=list.copy(Rlist)
    startGlist=list.copy(Glist)
    startEmpty=Empty

    for i in range(0,len(move_sequence)):
        if move_sequence[i]=='R':
            totalmoves+=1
            print("")
            if Empty-1 in Rlist:
                Rlist.remove(Empty-1)
                Rlist.append(Empty)
                Empty=Empty-1
            elif Empty-2 in Rlist and Empty-1 in Glist:
                Rlist.remove(Empty-2)
                Rlist.append(Empty)
                Empty=Empty-2
            else:
                print("")
                print("ERROR: sorry you made a mistake after", totalmoves, "total moves")
                flag=1
                break
        if move_sequence[i]=='G': 
            totalmoves+=1
            print("")
            if Empty+1 in Glist:
                Glist.remove(Empty+1)
                Glist.append(Empty)
                Empty=Empty+1
            elif Empty+2 in Glist and Empty+1 in Rlist:
                Glist.remove(Empty+2)
                Glist.append(Empty)
                Empty=Empty+2
            else:
                print("")
                print("ERROR: sorry you made a mistake after", totalmoves, "total moves")
                flag=1
                break

        if move_sequence[i]=='R' or move_sequence[i]=='G':
            for j in range(0,counter+1):
                if j in Rlist: print("R ", end = " ") 
                elif j in Glist: print("G ", end = " ")
                elif j == Empty: print("_ ", end = " ") 
                else: print("", end = " ")
            print("")
    
    print("")
    
    startRlist.sort()
    startGlist.sort()
    Rlist.sort()
    Glist.sort()
    
    if flag==0:
        if startRlist==Glist and startGlist==Rlist and startEmpty==Empty:
            print("Congratulations! You have solved the problem in", totalmoves, "total moves")
        else:
            print("You have currently made", totalmoves, "total moves.  Keep going!")
        


# #### <font color='red'>Now have your students solve harder problems directly in this Notebook.  To do this, they will need to input their STARTING POSITION, and then input their MOVE SEQUENCE.  If they do this correctly, they will receive a Congratulations message once they run their program.
# 
# #### <font color='red'>Note that the number of red and green frogs must be equal.  For example, with five people on each team, their STARTING POSITION will be RRRRR_GGGGG, where the underscore symbol _ denotes the empty chair. </font>
# 
# #### <font color='red'>Now the students will input the MOVE SEQUENCE that will solve the problem.  For example, with five frogs of each colour, the move sequence G-RR-GGG-RRRR-GGGGG-RRRRR-GGGGG-RRRR-GGG-RR-G will move all the greens to the left and all the reds to the right, as we see from the Python program.</font>
#     
# #### <font color='red'>Have the students try harder cases, such as 6 frogs of each colour, or even 10 frogs of each colour!  What will be the correct move sequences in these scenarios?</font>
# 

# ## Input your STARTING POSITION below, with team names R and G
# ### For example, with four people on each team, write down RRRR _ GGGG

# In[4]:


starting_position = 'RR_GG'


# ## Now input your MOVE SEQUENCE, to try to solve the game
# ### For example, with two people on each team, one solution is G RR GG RR G

# In[5]:


move_sequence = 'G RR GG RR G'


# ## Click the Run button to check your solution!

# In[6]:


play_game(starting_position, move_sequence)


# #### <font color='red'>For more advanced classes (say a Grade 11 or 12 class), the students may wish to investigate the 2-dimensional version of this game, where the game is played on a square board, rather than a single row.  In this variation, the red team can only move right and down, while the green team can only move left and up.  Students can play the game at https://www.cut-the-knot.org/SimpleGames/FrogsAndToads2D.shtml
#     
# #### <font color='red'>For your strongest students, here is one final challenge problem: </font>
# 
# #### <font color='red'>Suppose we begin with R red frogs on the left and G green frogs on the right, where R and G are any positive intgers (that are not necessarily equal!)  Determine the correct sequence of moves to solve this game, so that the G green frogs end up on the left, and the R red frogs end up on the right.</font>
# 
# #### <font color='red'>In your sequence of moves, how many total Jumps take place, and how many total Slides take place?  (Both answers will be a simple formula in terms of R and G.)  Clearly explain why these two formulas make sense.</font>
#    
# #### <font color='red'>I will purposely not post the solution to that challenge problem here.  However, your students are encouraged to write out their solution, scan it as a PDF, and then e-mail it to me (richard.hoshino@gmail.com).  I would be happy to write to the student and provide feedback on their solution.</font>
#     

# ![alt text](https://github.com/callysto/callysto-sample-notebooks/blob/master/notebooks/images/Callysto_Notebook-Banners_Bottom_06.06.18.jpg?raw=true)