Python Practice

#Escribe una función que invierta una cadena sin usar [::-1].
import math
def reverse_string(string):
    gnirts=''
    for letter in string:
        gnirts=letter+gnirts
    
    return gnirts

#Crea una función que determine si un número es primo.
def prime_tester(number):
   for element in range(2,math.floor(math.sqrt(number))+1):
    if number%element == 0:
        return False

    return True

#Escribe una función que cuente la frecuencia de cada carácter en una cadena.

def letter_counter(string):
    count_dict={}
    for letter in string:
        if letter in count_dict.keys():
            count_dict[letter]+=1
        else:
        	count_dict[letter]=1
    return count_dict
        

#Escribe una función que ordene una lista de números sin usar sorted() o .sort().

def ultimate_sorter(list_to_sort):
    if len(list_to_sort) <=1:
        return list_to_sort
    elif  len(list_to_sort) ==2:
        if list_to_sort[0]<=list_to_sort[1]:
            return list_to_sort
        else:
            return [list_to_sort[1],list_to_sort[0]]
    else:
        list1=ultimate_sorter(list_to_sort[0:int(len(list_to_sort)/2)])
        list2=ultimate_sorter(list_to_sort[int(len(list_to_sort)/2):len(list_to_sort)])
        merged_list=[]
        while (list1 and list2):
            if list1[0] <= list2[0]:
                merged_list.append(list1.pop(0))
            else:
                merged_list.append(list2.pop(0))
        if list1:
            merged_list += list1
        else:
            merged_list += list2
        return merged_list

def maxProfit(prices):
        down=False
        up=False
        minim=10001
        profit=0
        for i in range(len(prices)-1):
            if prices[i]>prices[i+1] and not down:
                down=True
                up=False
                if prices[i]-minim>profit:
                    profit=prices[i]-minim
                    print(profit,' with pricing ', prices[i], ' and index ', i, ' and minimum ',minim)
                
            elif prices[i]<prices[i+1] and not up:
                down=False
                up=True
                if minim>prices[i]: minim=prices[i]
        if up:
            if prices[-1]-minim>profit: profit=prices[-1]-minim
        return profit

    def canJump(nums):
        arrivedLast=False
        reachedIndex=[0]
        for element in reachedIndex:
            if element==len(nums)-1:
                arrivedLast=True
                return arrivedLast
            for j in range(nums[element]):
                if element+j+1 not in reachedIndex and element+j+1<=len(nums)-1:
                    reachedIndex.append(element+j+1)
        return arrivedLast

def canJumpIter(nums):
    arrivedLast=False
    for j in reversed(range(nums[0])):
        if j+1==len(nums)-1:
            arrivedLast=True
            return arrivedLast
        else:
            arrivedLast= canJumpIter(nums[j:])
    return arrivedLast

def canJumpIter2(nums):
    print('ITER', nums)
    arrivedLast=False
    if len(nums)==True:
        return 1
    for jumps in reversed(range(nums[0])):
        arrivedLast=canJumpIter2(nums[jumps+1:])
        if arrivedLast: return True
    return arrivedLast

def canJump2(nums):
    i=len(nums)-1
    if not i:
        return True
    while i>=0:
        print(i)
        if not nums[i]:
            jumpable=False
            j=1
            while not jumpable:
                if i-j<0:
                    return False
                if nums[i-j]>j or nums[i-j]+i-j==len(nums)-1:
                    jumpable=True
                    i-=j
                j+=1
        i-=1
    return True
            

def jumpIter(nums, count=10001):
    memo = {}

    def helper(nums, count):
        if len(nums) == 1:
            return 0
        if tuple(nums) in memo:
            return memo[tuple(nums)]
        
        for tryJump in reversed(range(1, nums[0] + 1)):
            if tryJump >= len(nums) - 1:
                memo[tuple(nums)] = 1
                return 1
            else:
                tempcount = helper(nums[tryJump:], count)
                if count > tempcount:
                    count = tempcount + 1
        
        memo[tuple(nums)] = count
        return count

    return helper(nums, count)

def jumpIter(nums):
    n = len(nums)
    if n == 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= n - 1:
                break
    
    return jumps

# Improvements:
# 1. Removed the recursive approach and replaced it with an iterative greedy approach.
# 2. The new approach uses a single pass through the list, making it O(n) in time complexity.
# 3. The variables `current_end` and `farthest` help track the range of the current jump and the farthest point that can be reached.
# 4. This reduces the overhead of recursive calls and improves performance significantly.

def jumpIter(nums,count=10001):
    if len(nums)==1:
        return 0
    for tryJump in reversed(range(nums[0])):

        if tryJump+1 >=len(nums):
            return 1
        else:
            tempcount=jumpIter(nums[tryJump+1:],count)
            if count>tempcount:
                count=tempcount+1
    return count

def hIndex(citations):
    scoreCount=[]
    for paper in citations:
        for cit in range(paper+1):
            if len(scoreCount)>cit:
                scoreCount[cit]+=1
            else:
                scoreCount.append(1)
    for i, count in enumerate(scoreCount):
        if i==count: return i
        elif i>count: return i-1
    return len(scoreCount)-1
        
        

def hIndex2(citations):
    citations.sort(reverse=True)
    for i in range(len(citations)):
        print(i,' ',citations[i])
        if i+1==citations[i]: return i+1
        elif i+1>citations[i]: return i
    return len(citations)

def helper(nums):
    length=len(nums)
    if length==2:
        return [nums[1],nums[0]]
    appended=False    
    if length%2:
        nums.append(1)
        appended=True
    numsNew=[]
    for i in range(0,length,2):
        a,b=nums[i],nums[i+1]
        nums[i+1],nums[i]=a,b
        numsNew.append(a*b)
    numsNew=helper(numsNew)
    k=0
    for j in range(length):
        nums[j]=nums[j]*numsNew[k]
        if j%2: k+=1
    if appended: nums.pop()
    return nums