"""
functions to run TOAH tours.
"""


# Copyright 2013, 2014, 2017 Gary Baumgartner, Danny Heap, Dustin Wehr,
# Bogdan Simion, Jacqueline Smith, Dan Zingaro
# Distributed under the terms- of the GNU General Public License.
#
# This file is part of Assignment 1, CSC148, Winter 2018.
#
# This is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This file is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this file.  If not, see <http://www.gnu.org/licenses/>.
# Copyright 2013, 2014 Gary Baumgartner, Danny Heap, Dustin Wehr


# you may want to use time.sleep(delay_between_moves) in your
# solution for 'if __name__ == "__main__":'

import time
from toah_model import TOAHModel


def tour_of_four_stools(model, delay_btw_moves=0.5, animate=False):
    """Move a tower of cheeses from the first stool in model to the fourth.

    @type model: TOAHModel
        TOAHModel with tower of cheese on first stool and three empty
        stools
    @type delay_btw_moves: float
        time delay between moves if console_animate is True
    @type animate: bool
        animate the tour or not
    @rtype: None
    """
    cheeses = model.get_number_of_cheeses()
    i = (min(A(cheeses)))[1]
    reves_puzzle(model, cheeses, 0, 1, 2, 3)



#helper functions

def A(n):
    lst = []
    m= n - 1
    if n == 0:
        return (0, 0)
    if n == 1:
        return (1, 1)
    else:
        for i in range(1, n):
            a = 2 * P(n - i) + 2 ** i - 1
            lst.append((a,i))
    return lst

def P(n):
    lst = []
    if n == 1:
        return 1
    else:
        for i in range(1, n):
            a = recursive_func(n, i)
            lst.append(a)
    return min(lst)

def recursive_func(n, i):
    if n < 1:
        return 0
    if n == 1:
        return 1
    if n >= 2:
        return 2 * P(n-i) + 2 ** i - 1

#reves_puzzle: solves problem for 4 stools, uses functio-n hanoi
def reves_puzzle(toahmodel, n, start, aux1, aux2, target):
    #base case matches hanoi
    t = min(A(n))
    print (t)
    if n == 1:
        hanoi(toahmodel, n, start, aux1, target)
    else:
        #algorithm from assignment page
        reves_puzzle(toahmodel, n-i, start, aux1, target, aux2)
        hanoi(toahmodel, i, start, aux1, target)
        reves_puzzle(toahmodel, n-i, aux2, start, aux1, target)



#animation version
def reves_A(toahmodel, delay, n, start, aux1, aux2, target):
    sq = round((2*n+1)**(1/2.0))
    k = n - sq + 1
    #base case matches hanoi
    if n == 1:
        hanoi(toahmodel, n, start, aux1, target)



#hanoi: solves problem for 3 stools
def hanoi(toahmodel, n, start, aux1, target):
    #algorithm and base case found on wikipedia: tower of hanoi
    if n == 1: #base case
        toahmodel.move(start, target)
    else:
        hanoi(toahmodel, n-1, start, target, aux1)
        toahmodel.move(start, target)
        hanoi(toahmodel, n-1, aux1, start, target)


if __name__ == '__main__':
    num_cheeses = 6
    delay_between_moves = 0.5
    console_animate = False

    # DO NOT MODIFY THE CODE BELOW.
    four_stools = TOAHModel(4)
    four_stools.fill_first_stool(number_of_cheeses=num_cheeses)

    tour_of_four_stools(four_stools,
                        animate=console_animate,
                        delay_btw_moves=delay_between_moves)

    print(four_stools.number_of_moves())