Navigation

    ask avan logo
    • Register
    • Login
    • Search
    • Categories
    • Unsolved
    • Solved

    Need Help with Python Assignment Involving Lists, Finding Minimum Value, Insert and Delete

    Python
    2
    7
    60
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • V
      vvv003 last edited by avan

      Hi Everyone,

      I was wondering if somebody could guide me in the right direction for the following assignment.
      I am lost and any help would be greatly appreciated! Thank you in advanced.

      Magic List is a special type of list L in which the elements are arranged according to the following
      properties :

      1. The first element of the list is always 0 (L[0] = 0).
      2. For each index i (>= 1), L[i] <= L[2i] and L[i] <= L[2i+1].
      3. For each index i (>= 1), L[i/2] is called the parent of L[i], and L[2i], L[2i+1] are called the children of
        L[i].
      4. L[1] has no parent.
        In this list, all the elements besides the first one are called magic elements. The size of Magic List is
        the number of magic elements in the list. Observe that L[1] will be the smallest magic element in list
        (Due to point 2. above).
        A class called MagicList has been given to you (inside MagicList.py). You have to complete the
        following functions inside the file :
      5. findMin
        Complete the findMin function and return the smallest magic element in the Magic List. If there are
        no magic elements (i.e. size of Magic List is zero), then return None.
      6. insert
        Complete the insert function and return the modified list. To insert an element in the Magic List, first
        append the element to the end of the list. Start at last element and keep comparing with parent
        L[i/2]. If parent is larger, swap the parent and the element. Keep doing this till parent is smaller, or
        the element has no parent.
      7. deleteMin
        Complete the deleteMin function, delete the smallest magic element in the Magic List, and return
        the modified list. To delete the minimum element, swap the minimum element (E1) with the last
        element (E2) and remove the last element. Keep comparing E2 with children L[2i] and L[2i+1] and
        swap with the smaller child. Keep doing this till both children are greater than E2 or E2 has no more
        children.
      Reply Quote 0
        1 Reply Last reply

      • avan
        avan last edited by

        OK. I saw a couple of things slightly off such as looping starting at 0 instead of 1. There were was at least one other mistake I have notices but it would take too long to dissect it all.

        Here is the code that I got but like I said I am not 100% confident it would pass more advanced tests.

        class MagicList:
          def __init__(self):
            self.data = [0]
        	
          def findMin(self):
            M = self.data
            ''' you need to find and return the smallest
              element in MagicList M.
              Write your code after this comment.
            '''
            # Make sure there is at least one element
            if(len(M) < 1):
              return None
            # Initialize i to 1
            # Temporarily set the min to the first value e.g. M[i]
            i = 1
            min = M[i]
            # Iterate over the list M
            while (i < len(M)):
              # check if the current element in the iteration is smaller than min
              if (M[i] < min):
                # New min found, update min
                min = M[i]
              # update i by adding 1
              i += 1
            return min
        	
          def insert(self, E):
            M = self.data
            ''' you need to insert E in MagicList M, so that
              properties of the MagicList are satisfied. 
              Return M after inserting E into M.
              Write your code after this comment.
              
              # Algorithm  
              1) first append the element to the end of the list. 
              2) Start at last element and keep comparing with parent L[i/2]. 
              3) If parent is larger, swap the parent and the element. 
              4) Keep doing this till parent is smaller, or
                # the element has no parent.
            '''
            # Step 1 
            # Add element to end of the list using append
            M.append(E)
            # Step 2
            # Initialize size to the length of M e.g. size = len(M) 
            size = len(M)
            # Subtract one from i
            i = size - 1
            # Initialize parent_i to i / 2
            parent_i = int(i / 2)
            # while i is greater than 0
            while(i > 0):
              # set parent_element to M[parent_i]
              parent_element = M[parent_i]
              # Step 3
              # if E is less than parent_element 
              if (E < parent_element):
                # Swap with parent (M[parent_i] --> E and M[i] --> parent_element)
                M[parent_i] = E
                M[i] = parent_element
                # update i and parent_i, i --> parent_i and parent_i --> parent_i / 2
                i = parent_i
                parent_i = int(parent_i/2)
              else:
                # Stop here. Break from while loop and return list and 
                break
            # Return List at the End of While Loop
            return M  
        
          def deleteMin(self):
            M = self.data
            ''' you need to delete the minimum element in
              MagicList M, so that properties of the MagicList
              are satisfied. Return M after deleting the 
              minimum element.
              Write your code after this comment.
            
            # Algorithm
            To delete the minimum element, 
            1) swap the minimum element (E1) with the last
            element (E2) and remove the last element. 
            2) Keep comparing E2 with children L[2i] and L[2i+1] and swap with the smaller child. Keep doing this till both children are greater than E2 or E2 has no more children.
            '''
            # Step 1 Set min to self.findMin()
            min = self.findMin()
            # Set i to 0
            i = 0
            # Iterate over M until i >= len(M)
            while(i < len(M)):
              # Check if M[i] is min
              if(M[i] == min):
                # Found minimum, now set location of min to the last element (hint: use M[-1])
                # No swap per se.  
                # Set M[i] to last element
                M[i] = M[-1]
                # Set E2 to M[i]
                E2 = M[i]
                # Delete last element (use pop())
                M.pop()
                # Another while loop this time run while i is less than len(M)
                # and 2*1 is less than len(M) and 2*1+1 is less than len(M)
                while(i < len(M) and (2*i < len(M)) and (2*i+1 < len(M))):
                  # Step 2
                  # Check if E2 is less than its child M[2*1]
                  if(E2 < M[2*i]):
                    # Complete swap with this child
                    child = M[i*2]
                    M[i*2] = E2
                    M[i] = child
                  # Else Check if E2 is less than its other child M[2*1+1]
                  elif(E2 < M[2*i+1]):
                    # Complete swap with this child
                    child = M[i*2+1]
                    M[i*2+1] = E2
                    M[i] = child
                  # Increase by a factor of 2 so i *= 2
                  i *= 2    
                # Stop the outer loop  
                break   
              # Increase i by 1
              i += 1
            return M    
        
        
        M = MagicList()
        M.insert(4)
        M.insert(3)
        M.insert(5)
        x = M.findMin()
        if x == 3 :
        	print("testcase 1 : Passed")
        else :
        	print("testcase 1 : Failed")
        	
        '''deleteMin and findMin'''
        M.deleteMin()
        x = M.findMin()
        if x == 4 :
        	print("testcase 2 : Passed")
        else :
        	print("testcase 2 : Failed")
        
        Reply Quote 0
          1 Reply Last reply

        • avan
          avan last edited by

          Hi @vvv003 Can we see MagicList.py?

          Reply Quote 0
            1 Reply Last reply

          • V
            vvv003 last edited by avan

            @avan this is magiclist.py please help!!

            class MagicList :
            	def __init__(self):
            		self.data = [0]
            	
            	def findMin(self):
            		M = self.data
            		''' you need to find and return the smallest
            			element in MagicList M.
            			Write your code after this comment.
            		'''
            	
            	def insert(self, E):
            		M = self.data
            		''' you need to insert E in MagicList M, so that
            			properties of the MagicList are satisfied. 
            			Return M after inserting E into M.
            			Write your code after this comment.
            		'''
            	
            	def deleteMin(self):
            		M = self.data
            		''' you need to delete the minimum element in
            			MagicList M, so that properties of the MagicList
            			are satisfied. Return M after deleting the 
            			minimum element.
            			Write your code after this comment.
            		'''
            
            

            if name == "main" :
            '''Here are a few test cases'''

            '''insert and findMin'''
            M = MagicList()
            M.insert(4)
            M.insert(3)
            M.insert(5)
            x = M.findMin()
            if x == 3 :
            	print("testcase 1 : Passed")
            else :
            	print("testcase 1 : Failed")
            	
            '''deleteMin and findMin'''
            M.deleteMin()
            x = M.findMin()
            if x == 4 :
            	print("testcase 2 : Passed")
            else :
            	print("testcase 2 : Failed")
            Reply Quote 0
              1 Reply Last reply

            • avan
              avan last edited by

              I think I got it! Test cases are on the light side so I don't know if it is a correct solution for sure.

              However before I give you the complete code I would like to try this psudo code version first. Let me know what you struggle with or what parts are still unclear.

              I really want to help you but I need a little bit of engagement from you before I give you the code. I hope you understand.

              class MagicList:
                def __init__(self):
                  self.data = [0]
              	
                def findMin(self):
                  M = self.data
                  ''' you need to find and return the smallest
                    element in MagicList M.
                    Write your code after this comment.
                  '''
                  # Make sure there is at least one element
                  if(...):
                    return None
                  # Initialize i to 1
                  # Temporarily set the min to the first value e.g. M[i]
                  i ..
                  min...
                  # Iterate over the list M
                  while...:
                    # check if the current element in the iteration is smaller than min
                    if ...:
                      # New min found, update min
                      min...
                    # update i by adding 1
                    i ...
                  #return min
                  return ...
              	
                def insert(self, E):
                  M = self.data
                  ''' you need to insert E in MagicList M, so that
                    properties of the MagicList are satisfied. 
                    Return M after inserting E into M.
                    Write your code after this comment.
                    
                    # Algorithm  
                    1) first append the element to the end of the list. 
                    2) Start at last element and keep comparing with parent L[i/2]. 
                    3) If parent is larger, swap the parent and the element. 
                    4) Keep doing this till parent is smaller, or
                      # the element has no parent.
                  '''
                  # Step 1 
                  # Add element to end of the list using append
                  M...
                  # Step 2
                  # Initialize size to the length of M e.g. size = len(M) 
                  size...
                  # Subtract one from i
                  i...
                  # Initialize parent_i to i / 2
                  parent_i...
                  # while i is greater than 0
                  while...
                    # set parent_element to M[parent_i]
                    parent_element....
                    # Step 3
                    # if E is less than parent_element 
                    if ...:
                      # Swap with parent (M[parent_i] --> E and M[i] --> parent_element)
                      M...
                      M[i]...
                      # update i and parent_i, i --> parent_i and parent_i --> parent_i / 2
                      i ...
                      parent_i...
                    else:
                      # Stop here. Break from while loop and return list and 
                      break
                  # Return List at the End of While Loop
                  return M  
              
                def deleteMin(self):
                  M = self.data
                  ''' you need to delete the minimum element in
                    MagicList M, so that properties of the MagicList
                    are satisfied. Return M after deleting the 
                    minimum element.
                    Write your code after this comment.
                  
                  # Algorithm
                  To delete the minimum element, 
                  1) swap the minimum element (E1) with the last
                  element (E2) and remove the last element. 
                  2) Keep comparing E2 with children L[2i] and L[2i+1] and swap with the smaller child. Keep doing this till both children are greater than E2 or E2 has no more children.
                  '''
                  # Step 1 Set min to self.findMin()
                  min ...
                  # Set i to 0
                  i ...
                  # Iterate over M until i >= len(M)
                  while....
                    # Check if M[i] is min
                    if...
                      # Found minimum, now set location of min to the last element (hint: use M[-1])
                      # No swap per se.  
                      # Set M[i] to last element
                      M[i]....
                      # Set E2 to M[i]
                      E2...
                      # Delete last element (use pop())
                      M...
                      # Another while loop this time run while i is less than len(M)
                      # and 2*1 is less than len(M) and 2*1+1 is less than len(M)
                      while...
                        # Step 2
                        # Check if E2 is less than its child M[2*1]
                        if....
                          # Complete swap with this child
                          child....
                          M[i*2]...
                          M[i]...
                        # Else Check if E2 is less than its other child M[2*1+1]
                        elif....
                          # Complete swap with this child
                          child....
                          M[i*2+1]...
                          M[i]....
                        # Increase by a factor of 2 so i *= 2
                        i *=...
                      # Stop the outer loop  
                      break   
                    # Increase i by 1
                    i ...
                  return M    
              
              
              Reply Quote 0
                1 Reply Last reply

              • V
                vvv003 last edited by avan

                @avan testcase : failed
                what should i do?

                Here is my code:

                class MagicList:
                  def __init__(self):
                    self.data = [0]
                	
                  def findMin(self):
                    M = self.data
                    ''' you need to find and return the smallest
                      element in MagicList M.
                      Write your code after this comment.
                    '''
                    if len(self.data) == 1:
                      return None
                    # Initialize i to 1
                    # Temporarily set the min to the first value e.g. M[i]
                    i = 1
                    min = M[i]
                    # Iterate over the list M
                    length = len(M)
                    for i in range(length):
                      # check if the current element in the iteration is smaller than min
                      if M[i] < min:
                        # New min found, update min
                        min = M[i] + 1
                      # update i by adding 1
                    #return min
                    return min
                
                  def insert(self, E):
                    M = self.data
                    ''' you need to insert E in MagicList M, so that
                      properties of the MagicList are satisfied. 
                      Return M after inserting E into M.
                      Write your code after this comment.
                      
                      # Algorithm  
                      1) first append the element to the end of the list. 
                      2) Start at last element and keep comparing with parent L[i/2]. 
                      3) If parent is larger, swap the parent and the element. 
                      4) Keep doing this till parent is smaller, or
                        # the element has no parent.
                    '''
                    # Step 1 
                    # Add element to end of the list using append
                    M.append(E)
                    # Step 2
                    # Initialize size to the length of M e.g. size = len(M) 
                    size = len(M)
                    # Subtract one from i
                    i = len(M) - 1
                    # Initialize parent_i to i / 2
                    parent_i = i/2
                    # while i is greater than 0
                    while i>0:
                      # set parent_element to M[parent_i]
                      parent_element = M[int(parent_i)]
                      # Step 3
                      # if E is less than parent_element 
                      if E < parent_element:
                        # Swap with parent (M[parent_i] --> E and M[i] --> parent_element)
                        M[int(parent_i)] = E
                        M[i] = parent_element
                        # update i and parent_i, i --> parent_i and parent_i --> parent_i / 2
                        i = parent_i
                        parent_i = parent_i / 2
                      else:
                        # Stop here. Break from while loop and return list and 
                        break
                    # Return List at the End of While Loop
                    return M  
                
                  def deleteMin(self):
                    M = self.data
                    ''' you need to delete the minimum element in
                      MagicList M, so that properties of the MagicList
                      are satisfied. Return M after deleting the 
                      minimum element.
                      Write your code after this comment.
                    
                    # Algorithm
                    To delete the minimum element, 
                    1) swap the minimum element (E1) with the last
                    element (E2) and remove the last element. 
                    2) Keep comparing E2 with children L[2i] and L[2i+1] and swap with the smaller child. Keep doing this till both children are greater than E2 or E2 has no more children.
                    '''
                    # Step 1 Set min to self.findMin()
                    min = self.findMin()
                    # Set i to 0
                    i = 0
                    # Iterate over M until i >= len(M)
                    length = len(M)
                    for i in range(i >= len(M)):
                      # Check if M[i] is min
                      if M[i] == min:
                        # Found minimum, now set location of min to the last element (hint: use M[-1])
                        # No swap per se.  
                        # Set M[i] to last element
                        M[i] = M[-1]
                        # Set E2 to M[i]
                        E2 = M[i]
                        # Delete last element (use pop())
                        M.pop()
                        # Another while loop this time run while i is less than len(M)
                        # and 2*1 is less than len(M) and 2*1+1 is less than len(M)
                        while i < len(M) and 2*1 < len(M) and 2*1+1 < len(M):
                          # Step 2
                          # Check if E2 is less than its child M[2*1]
                          if E2 < M[2*1]:
                            # Complete swap with this child
                            child = M[i*2]
                            M[i*2] = M[i]
                            M[i] = child
                          # Else Check if E2 is less than its other child M[2*1+1]
                          elif E2 < M[2*1+1]:
                            # Complete swap with this child
                            child = M[i*2+1]
                            M[i*2+1] = M[i]
                            M[i] = child
                          # Increase by a factor of 2 so i *= 2
                          i *= 2
                        # Stop the outer loop  
                        break   
                      # Increase i by 1
                      i = i + 1
                    return M    
                
                

                if name == "main" :
                '''Here are a few test cases'''

                  '''insert and findMin'''
                  M = MagicList()
                  M.insert(4)
                  M.insert(3)
                  M.insert(5)
                  x = M.findMin()
                  if x == 3 :
                    print("testcase 1 : Passed")
                  else :
                    print("testcase 1 : Failed")
                
                  M.deleteMin()
                  x = M.findMin()
                  if x == 4 :
                    print("testcase 2 : Passed")
                  else :
                    print("testcase 2 : Failed")
                
                Reply Quote 0
                  1 Reply Last reply

                • avan
                  avan last edited by

                  OK. I saw a couple of things slightly off such as looping starting at 0 instead of 1. There were was at least one other mistake I have notices but it would take too long to dissect it all.

                  Here is the code that I got but like I said I am not 100% confident it would pass more advanced tests.

                  class MagicList:
                    def __init__(self):
                      self.data = [0]
                  	
                    def findMin(self):
                      M = self.data
                      ''' you need to find and return the smallest
                        element in MagicList M.
                        Write your code after this comment.
                      '''
                      # Make sure there is at least one element
                      if(len(M) < 1):
                        return None
                      # Initialize i to 1
                      # Temporarily set the min to the first value e.g. M[i]
                      i = 1
                      min = M[i]
                      # Iterate over the list M
                      while (i < len(M)):
                        # check if the current element in the iteration is smaller than min
                        if (M[i] < min):
                          # New min found, update min
                          min = M[i]
                        # update i by adding 1
                        i += 1
                      return min
                  	
                    def insert(self, E):
                      M = self.data
                      ''' you need to insert E in MagicList M, so that
                        properties of the MagicList are satisfied. 
                        Return M after inserting E into M.
                        Write your code after this comment.
                        
                        # Algorithm  
                        1) first append the element to the end of the list. 
                        2) Start at last element and keep comparing with parent L[i/2]. 
                        3) If parent is larger, swap the parent and the element. 
                        4) Keep doing this till parent is smaller, or
                          # the element has no parent.
                      '''
                      # Step 1 
                      # Add element to end of the list using append
                      M.append(E)
                      # Step 2
                      # Initialize size to the length of M e.g. size = len(M) 
                      size = len(M)
                      # Subtract one from i
                      i = size - 1
                      # Initialize parent_i to i / 2
                      parent_i = int(i / 2)
                      # while i is greater than 0
                      while(i > 0):
                        # set parent_element to M[parent_i]
                        parent_element = M[parent_i]
                        # Step 3
                        # if E is less than parent_element 
                        if (E < parent_element):
                          # Swap with parent (M[parent_i] --> E and M[i] --> parent_element)
                          M[parent_i] = E
                          M[i] = parent_element
                          # update i and parent_i, i --> parent_i and parent_i --> parent_i / 2
                          i = parent_i
                          parent_i = int(parent_i/2)
                        else:
                          # Stop here. Break from while loop and return list and 
                          break
                      # Return List at the End of While Loop
                      return M  
                  
                    def deleteMin(self):
                      M = self.data
                      ''' you need to delete the minimum element in
                        MagicList M, so that properties of the MagicList
                        are satisfied. Return M after deleting the 
                        minimum element.
                        Write your code after this comment.
                      
                      # Algorithm
                      To delete the minimum element, 
                      1) swap the minimum element (E1) with the last
                      element (E2) and remove the last element. 
                      2) Keep comparing E2 with children L[2i] and L[2i+1] and swap with the smaller child. Keep doing this till both children are greater than E2 or E2 has no more children.
                      '''
                      # Step 1 Set min to self.findMin()
                      min = self.findMin()
                      # Set i to 0
                      i = 0
                      # Iterate over M until i >= len(M)
                      while(i < len(M)):
                        # Check if M[i] is min
                        if(M[i] == min):
                          # Found minimum, now set location of min to the last element (hint: use M[-1])
                          # No swap per se.  
                          # Set M[i] to last element
                          M[i] = M[-1]
                          # Set E2 to M[i]
                          E2 = M[i]
                          # Delete last element (use pop())
                          M.pop()
                          # Another while loop this time run while i is less than len(M)
                          # and 2*1 is less than len(M) and 2*1+1 is less than len(M)
                          while(i < len(M) and (2*i < len(M)) and (2*i+1 < len(M))):
                            # Step 2
                            # Check if E2 is less than its child M[2*1]
                            if(E2 < M[2*i]):
                              # Complete swap with this child
                              child = M[i*2]
                              M[i*2] = E2
                              M[i] = child
                            # Else Check if E2 is less than its other child M[2*1+1]
                            elif(E2 < M[2*i+1]):
                              # Complete swap with this child
                              child = M[i*2+1]
                              M[i*2+1] = E2
                              M[i] = child
                            # Increase by a factor of 2 so i *= 2
                            i *= 2    
                          # Stop the outer loop  
                          break   
                        # Increase i by 1
                        i += 1
                      return M    
                  
                  
                  M = MagicList()
                  M.insert(4)
                  M.insert(3)
                  M.insert(5)
                  x = M.findMin()
                  if x == 3 :
                  	print("testcase 1 : Passed")
                  else :
                  	print("testcase 1 : Failed")
                  	
                  '''deleteMin and findMin'''
                  M.deleteMin()
                  x = M.findMin()
                  if x == 4 :
                  	print("testcase 2 : Passed")
                  else :
                  	print("testcase 2 : Failed")
                  
                  Reply Quote 0
                    1 Reply Last reply

                  • avan
                    avan last edited by

                    @vvv003 Do you mind selecting my last answer as the correct one if it worked for you? Thank you!

                    Reply Quote 0
                      1 Reply Last reply

                    • First post
                      Last post