#include <iostream>
#include <string>
#include "recLL.cpp"
using namespace std;

//return sum of 1+2+....+3*n
int sumThree(int n)
{
	if (n == 0) //base case
		return 0;
	else //recursive case
		return 3 * n + 3 * n - 1 + 3*n - 2 + sumThree(n - 1);
}

int binarySearch(double* nums, int start, int end, double key)
{
	if (start > end) //base: no items
	{
		return -1;
	}
	else //recursive case
	{
		int mid = (start + end) / 2;

		if (key == nums[mid])
			return mid;
		else if (key < nums[mid])
			return binarySearch(nums, start, mid - 1, key);
		else // key > mid
			return binarySearch(nums, mid + 1, end, key);
	}
}

//Move top n discs from poleA to poleC, using poleB
//as a buffer.
void hanoi(int n, string poleA, string poleB, string poleC)
{
	if(n==0) //base case
	{//do nothing, no discs!
	}
	else
	{
		//step 1: hanoi top n-1 discs to poleB
		hanoi(n - 1, poleA, poleC, poleB);

		//step 2: move top disc from A to C
		cout << "Move top disc from: " << poleA << " to " << poleC << endl;

		//step 3: hanoi top n-1 discs from B to C
		hanoi(n - 1, poleB, poleA, poleC);
	}
}

int main()
{
	//Quiz #1:
	cout << sumThree(5) << endl;  //returns 1+2+...+15 = 120

	//Challenge #2: Print a singly linked list backwards
	linkedList L;
	L.addFront(13);
	L.addFront(11);
	L.addFront(7);
	L.addFront(5);
	L.addFront(3);
	L.addFront(2);

	L.printForwards();
	cout << endl;
	L.printBackwards();

	//Challenge #2: Binary search
	//Search a sorted array in O(log n) time - no loops
	double nums[] = { -123, -24, -5, 1.3, 2.4, 3, 5, 8.8, 9, 11.5, 12, 15, 23, 24, 29, 65, 82, 91, 93, 94, 97.8 };

	cout << binarySearch(nums, 0, 20, 1.3) << endl;		//  3
	cout << binarySearch(nums, 0, 20, 93) << endl;		//	18
	cout << binarySearch(nums, 0, 20, 14.3) << endl;	//  -1

	//Challenge #3: Towers of Hanoi
	hanoi(63, "A", "B", "C");

	return 0;
}