Given an array of integers arr, sort the array by performing a series of pancake flips.
In one pancake flip we do the following steps:

Choose an integer k where 1 <= k <= arr.length.
Reverse the sub-array arr[1...k].

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.
Return the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.
 
Example 1:
Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.
Notice that we return an array of the chosen k values of the pancake flips.

Example 2:
Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

 
Constraints:

1 <= arr.length <= 100
1 <= arr[i] <= arr.length
All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

Difficulty: interview

Starter code:

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        

Solutions:
class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        n = len(A)
        res = []
        
        for x in range(n, 1, -1):
            idx = A.index(x)
            res.extend([idx + 1, x])
            A = A[idx::-1] + A[idx+1:]
            A = A[x-1::-1]
            
        return res


class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        N = len(A)
        res = []
        for x in range(N, 0, -1):
            i = A.index(x)
            res.extend([i + 1, x])
            A = A[:i:-1] + A[:i]
        return res

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ans = []
        for i in range(n, 0, -1):
            for j in range(i-1):
                if arr[j] == i:
                    ans.append(j+1)
                    ans.append(i)
                    print((j, i))
                    arr = list(reversed(arr[:j+1])) + arr[j+1:]
                    print(arr)
                    arr = list(reversed(arr[:i])) + arr[i:]
                    print(arr)
                    break
        return ans
                    


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        res = []
        for x in range(len(arr), 1, -1):
            i = arr.index(x)
            res.extend([i + 1, x])
            arr = arr[:i:-1] + arr[:i]
        return res

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:

        def pancake_flip(to_flip, index):
            print(\"flipping \" + str(to_flip) + \" with index \" + str(index))
            middle = index // 2
            for i in range(middle):
                to_flip[i], to_flip[index - i - 1] = to_flip[index - i - 1], to_flip[i]
            print(\"flipped: \" + str(to_flip))
            return to_flip
        
        is_sorted = True
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                is_sorted = False
                break
        if is_sorted:
            return []
        
        result = []
        print(\"starting with: \" + str(arr))
        current_element = 1
        while current_element < len(arr):
            print(\"current element: \" + str(current_element))
            index = arr.index(current_element) + 1
            print(\"found element \" + str(current_element) + \" at \" + str(index))
            if index != len(arr) - current_element + 1:
                if index != 1:
                    result.append(index)
                    arr = pancake_flip(arr, index)
                index = len(arr) - current_element + 1
                result.append(index)
                arr = pancake_flip(arr, index)
            current_element += 1
        result.append(len(arr))
        return result


class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        def flip(r):
            l = 0
            while l<r:
                A[l], A[r] = A[r], A[l]
                l, r = l+1, r-1     
                
        ans = []
        for x in range(len(A),0,-1):
            i = A.index(x)+1 #x is the current unsorted largest element
            ans.extend([i, x])
            flip(i-1)
            flip(x-1)
        
        return ans


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        # Discussion solution by Lee215
        res = []
        for x in range(len(arr), 1, -1):
            i = arr.index(x)
            res.extend([i + 1, x])
            arr = arr[:i:-1] + arr[:i]
        return res
        
        # First answer: Best run 93.4%[36ms], 5.03%[14.2MB]
        out = []
        for i in range(len(arr),0,-1):  # traverse left-to-right
            if arr[i-1] != i:           # find 1st wrong entry  
                j = arr.index(i)        # search for right entry
                out.extend([j+1,i])
                arr[:j+1] = reversed(arr[:j+1])
                arr[:i]   = reversed(arr[:i])
        return out

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        res = []
        A = arr
        for x in range(len(A), 1, -1):
            i = A.index(x)
            res.extend([i+1, x])
            A = A[x-1:i:-1] + A[:i]
            
        return res


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        
        last = len(arr)
        ans = []
        
        while last > 1:
            #print(f\"last={last} ans={ans} arr={arr}\")
            max_pos = 0
            max_v = -float('inf')
            for i in range(last):
                if arr[i] > max_v:
                    max_v = arr[i]
                    max_pos = i
                    
        
                
            ans.append(max_pos+1)
            ans.append(last)
            arr[:max_pos+1] = arr[:max_pos+1][::-1]
            arr[:last] = arr[:last][::-1]
                
            last -= 1
        return ans
    
    


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        # 1. find max value, flip it to first; 2. flip whole array, let max to the end.
        results = []
        end = len(arr)
        
        while end > 1:
            max_idx = arr.index(max(arr[:end]))
            if max_idx == end - 1:
                end -= 1
            else:
                if max_idx > 0:
                    results.append(max_idx+1)
                    arr[:max_idx+1] = reversed(arr[:max_idx+1])
                results.append(end)
                arr[:end] = reversed(arr[:end])
                end -= 1
        print(arr)
        return results


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ans = []
        def flip(idx):
            arr[:idx+1] = arr[:idx+1][::-1]
        for i in range(len(arr)):
            maxInd = arr[:n].index(max(arr[:n]))
            if maxInd != n:
                ans.append(maxInd+1)
                ans.append(n)
                flip(maxInd)
                flip(n -1)
            n -= 1
        
        return ans


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        def flip(k):
            for i in range(k // 2):
                arr[i], arr[k - i - 1] = arr[k - i - 1], arr[i]
        
        ans = []
        val = len(arr)
        while val > 0:
            i = arr.index(val)
            if 0 < i < val - 1:
                ans.append(i + 1)
                flip(i + 1)
            if i < val - 1:
                ans.append(val)
                flip(val)
            val -= 1
        return ans

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        
        def flip(sublist,k):
            i=0
            while(i<k/2):
                sublist[i],sublist[k-i-1]=sublist[k-i-1],sublist[i]
                i+=1
        
        ans = []
        value_to_sort= len(arr)
        while(value_to_sort>0):
            index = arr.index(value_to_sort)
            if(index!=value_to_sort-1):
                if(index!=0):
                    ans.append(index+1)
                    flip(arr,index+1)
                ans.append(value_to_sort)
                flip(arr,value_to_sort)
            value_to_sort-=1
        return ans


class Solution(object):
    def pancakeSort(self, arr):
        p = arr.copy()
        final = p.copy()
        final.sort()
        print(p)
        k = len(final) - 1
        ret = []
        while k >= 0:
            val = final[k]
            print(\"value = \", val)
            ind = p.index(val)
            print(\"p array = \", p)
            print(\"index for\", val, \"=\", ind)
            if ind != k and ind != 0:
                p = p[:(ind+1)][::-1] + p[(ind+1):]
                p = p[:(k+1)][::-1] + p[(k+1):]
                ret += [ind+1, k+1]
            elif ind == k:
                pass
            elif ind == 0:
                p = p[:(k+1)][::-1] + p[(k+1):]
                ret.append(k+1)
            k -= 1
        return ret