# Mini-challenges

## Fizz Buzz

```{block, type="miniChallenge"}

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
```

```{python echo = FALSE}

class FizzBuzz:
    def fizzBuzz(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        # ans list
        ans = []

        for num in range(1,n+1):

            divisible_by_3 = (num % 3 == 0)
            divisible_by_5 = (num % 5 == 0)

            if divisible_by_3 and divisible_by_5:
                # Divides by both 3 and 5, add FizzBuzz
                ans.append("FizzBuzz")
            elif divisible_by_3:
                # Divides by 3, add Fizz
                ans.append("Fizz")
            elif divisible_by_5:
                # Divides by 5, add Buzz
                ans.append("Buzz")
            else:
                # Not divisible by 3 or 5, add the number
                ans.append(str(num))

        return ans


```

```{python}

foo = FizzBuzz()
foo.fizzBuzz(15)

```

## Fibonacci Extended

```{block, type="miniChallenge"}

The Fibonacci sequence starts with a one or a zero, followed by a one, and proceeds based on the rule that each number is equal to the sum of the preceding two numbers, e.g. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

We can generalize this so that the sum of the preceding n numbers form the next term. e.g. with n=3, 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, ...

Write a function that takes two inputs: n and m, and returns m values from an n-Fibonacci sequence.

```

```{python eval = TRUE, echo = FALSE}

# returns full sequence from the first to m-th term of n-bonacci sequence
def fiboExt(n,m):

	nfib =[] # storage of sequence
	
	if m < n or n == 0:
		nfib = [0]*m # sequence contains only zeros
		
	else:
		# first non-zero term at n-th place
		nfib = [0]*(n-1) + [1] 
		# calculate further terms till m-th
		for i in range(n,m):
			nfib.append(sum(nfib[i-n:i]))
			
	return nfib # return the sequence
			


```

```{python}
n = 3 # depth of sum
m = 8 # Until the mth term
fiboExt(n,m)
```

## Points Distance

```{block, type="miniChallenge"}

A Cartesian plane is defined by two perpendicular number lines: the x-axis, which is horizontal, and the y-axis, which is vertical.
Using these axes, we can describe any point in the plane using an ordered pair of numbers.

Write a function which takes two different points as a list [x1, y2, x2, y2], and returns the distance between these two points.

The distance formula is the Pythagorean Theorem:

```

$$distance = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

```{python eval = TRUE, echo = FALSE}
import math

def get_distance(points):
	return int(math.sqrt((points[0]-points[2])**2 + (points[1]-points[3])**2))
```

```{python}
get_distance([2, 1, 5, 5])
```

## Emirp Numbers

```{block, type="miniChallenge"}

An emirp number is a prime number, that when reversed, is still a prime number, i.e. _emirp_, get it? :)

e.g. 13 is an emirp, since both 13 and 31 are prime numbers.

Write two functions. `is_prime()` checks if a number is prime, `is_emirp()` checks if the reverse is also prime. If both conditions are met then it returns `True`. You can of course check that a number is prime inside `is_emirp()`, but having two functions will help to compartmentalize our code.

e.g.:
Input: 13
Output: true (13 and 31 are prime numbers)

Input: 23
Output: false (23 is a prime number, but 32 is not)

Bonus 1: Exclude palindromic primes since the definition of an emirp is meaningless here.

Bonus 2: return a sentence, dependent on the result of 
```

```{python eval = TRUE, echo = FALSE}

def is_prime(n):
	"""Check for prime number."""
	if n == 2:
		return True
	elif n > 2 and not n % 2:
		return False
	return all(n % i for i in range(3, int(n ** .5 + 1), 2))


def is_emirp(n):
	"""Check for emirp number.
	
	Excludes palindromic primes
	"""
	return is_prime(n) and is_prime(int(str(n)[::-1])) and str(n) != str(n)[::-1]


n = 23

print(f"{n} is{' ' if is_emirp(n) else ' not '}an emirp number.")

```

```{python}
is_emirp(13)
```

## Summations Calculator

```{block, type="miniChallenge"}

Create a function that takes 3 inputs, a lower bound, an upper bound and the expression. Calculate the sum of that range based on the given expression and output the result.


For Example:

Input: ['2', '4', '*2']

Output: 18 (2*2 + 3*2 + 4*2)

Input: w = ['1', '5', '%2']

Output: 3 (1%2 + 2%2 + 3%2 + 4%2 + 5%2)

```

```{python eval = TRUE, echo = FALSE}

def summation(exp):
	return eval("+".join([str(i)+exp[-1][0]+exp[-1][1] for i in range(int(exp[0]),int(exp[1])+1)]))

```

```{python}
summation(['2', '4', '*2'])
summation(['1', '5', '%2'])
```

## Linear versus binary search

```{block, type="miniChallenge"}
Given an array of integers values sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's run-time complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].
```

```{python, eval = FALSE, echo = FALSE}

# Exercise 35:
# three different solutions

import bisect
import time

class FindValue:
# Linear Search
    def linearSearch(self, nums, target):
        if not nums:
            return 0
        
        for i, num in enumerate(nums):
            if num >= target:
                return i
        
        return len(nums)

# Using bisect module
    def bisectModule(self, nums, target):
        return bisect.bisect_left(nums, target)

# Binary Search By Hand
    def binaryManual(self, nums, target):
        low, high = 0, len(nums)
        while low < high:
            mid = (low + high) // 2
            if target > nums[mid]:
                low = mid + 1
            else:
                high = mid
        return low

foo = FindValue()



foo.linearSearch([5,7,7,8,8,10], 8)
foo.bisectModule([5,7,7,8,8,10], 8)
foo.binaryManual([5,7,7,8,8,10], 8)
```

```{python, eval = FALSE, echo = FALSE}
import numpy as np
myVal = np.random.choice(range(8000), size=20000, replace=True, p=None)
myVal = np.ndarray.tolist(myVal)
myVal = myVal + [6400] * 6
myVal.sort()
myVal[:6]
type(myVal)

start = time.time()
foo.linearSearch(myVal, 6400)
end = time.time()
print(end - start)
```

```{python, eval = FALSE, echo = FALSE}
start = time.time()
foo.bisectModule(myVal, 6400)
end = time.time()
print(end - start)

```

```{python, eval = FALSE, echo = FALSE}
start = time.time()
foo.binaryManual(myVal, 6400)
end = time.time()
print(end - start)
```

```{python, eval = FALSE, echo = FALSE}
class Solution:
    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted
    # array `nums` via binary search.
    def extreme_insertion_index(self, nums, target, left):
        lo = 0
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):
                hi = mid
            else:
                lo = mid+1

        return lo


    def searchRange(self, nums, target):
        left_idx = self.extreme_insertion_index(nums, target, True)

        # assert that `left_idx` is within the array bounds and that `target`
        # is actually in `nums`.
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        return [left_idx, self.extreme_insertion_index(nums, target, False)-1]

foo = Solution()
foo.searchRange([5,7,7,8,8,10], 8)
```

```{python, eval = FALSE, echo = FALSE}

# Approach 2: Binary Search
# Intuition
# 
# Because the array is sorted, we can use binary search to locate the left and rightmost indices.
# 
# Algorithm
# 
# The overall algorithm works fairly similarly to the linear scan approach, except for the subroutine used to find the left and rightmost indices themselves. Here, we use a modified binary search to search a sorted array, with a few minor adjustments. First, because we are locating the leftmost (or rightmost) index containing target (rather than returning true iff we find target), the algorithm does not terminate as soon as we find a match. Instead, we continue to search until lo == hi and they contain some index at which target can be found.
# 
# The other change is the introduction of the left parameter, which is a boolean indicating what to do in the event that target == nums[mid]; if left is true, then we "recurse" on the left subarray on ties. Otherwise, we go right. To see why this is correct, consider the situation where we find target at index i. The leftmost target cannot occur at any index greater than i, so we never need to consider the right subarray. The same argument applies to the rightmost index.
# 
# The first animation below shows the process for finding the leftmost index, and the second shows the process for finding the index right of the rightmost index.

# Solution 2: Binary Search
from typing import List
class Solution:
    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted
    # array `nums` via binary search.
    def extreme_insertion_index(self, nums, target, left):
        lo = 0
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):
                hi = mid
            else:
                lo = mid+1

        return lo


    def searchRange(self, nums, target):
        left_idx = self.extreme_insertion_index(nums, target, True)

        # assert that `left_idx` is within the array bounds and that `target`
        # is actually in `nums`.
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        return [left_idx, self.extreme_insertion_index(nums, target, False)-1]

foo.searchRange([5,7,7,8,8,10], 8)

foo.searchRange([5,7,7,8,8,10], 6)



# Problem 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        a = 0
        if len(nums) == 1 and target > nums[0]:
            return 1
        for i in range(0, len(nums)):
            if target == nums[i]:
                print('bbb')
                return i
            if nums[i] > target and i != 0:
                print('aaa')
                a = i
                break
            if nums[i] > target and i == 0:
                return 0
        if nums[-1] <= target and len(nums) != 1:
            return len(nums)
        return a

foo = Solution()
foo.searchInsert([3,5,7,8,9], 6)    
```

