Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / For the sake of this question, we will need to define a new type

For the sake of this question, we will need to define a new type

Computer Science

For the sake of this question, we will need to define a new type. Let us define nested lists of arbitrary depths (nests for short) as follow: (nestof X) = (listof (anyof X (nestof X))). For example, ["a", "b", ["ew", "d", ["r", "j"], "", ["a"]], []] is a nest of strings.

We call siblings nest values contained inside the same list, for example "d", ["r", "j"] and ["a"] are siblings in the example above.

Write function

 

 

nest_sort(N)

that consumes N, a (nestof Int), returns None, and mutates N to be in sorted order in according to the following rules:

  • A nest should come before a sibling nest if the sum of all the integers it contains is smaller than the sum of the integers the other nest contains; for example [2, 5] should come before [9].
  • If the sum of the integers contained in two sibling nests are equal, they keep the order they had.
  • An integer should come before a sibling nest if it is smaller than the sum of all the integers the nest contains; for example 9 should come before [4, 3, 3]
  • If an integer is equal to the sum of the integers contained in a sibling nest, they keep the order they had.
  • If two integers are equal... It does not matter, they are the same anyway.

The function nest_sort must run in O(n log n) where O(n) is the number of individual integers across all nests.

 

Examples:

 

 

nest = [16, 8, 49, [2, 4], 0, 6, 4, [19, [4, 3]]]
nest_sort(nest) => None

and nest is now [0, 4, [2, 4], 6, 8, 16, [[3, 4], 19], 49].

Hints:

  • Consider writing a helper returning the sum of the integers in a nest, or the value of an integer
  • Review the type() command from Module 1 Functions. For example, type([]) == type([2,[3]]) => True
  • Consider starting from the merge sort algorithm, and edit it to sort the outer most nest. At the end, sort its children.
  • For positive integers m,n,r, if m*r<=n, then m*r(log r)< n(log(n)).

Restrictions

Do not import any modules other than math and check. You are always allowed to define your own helper/wrapper functions, as long as they meet the assignment restrictions. Do not use Python constructs from later modules (e.g. dictionaries, commands continue or break, zip, anything with set or enumerator, etc.).

Do not mutate passed parameters unless otherwise told to.

Use only the functions and methods as follows:

  • abs, len, max, min, sum, range and sorted
  • Any method or constant in the math module
  • Any basic arithmetic operation (including +, -, *, /, //, %, **)
  • Any basic logical operators (not, and, or)
  • Typecasting including int(), str(), float(), bool(), list(), and type()
  • if statements
  • String or list slicing and indexing as well as string or list operations using the operators above
  • Any string or list methods, including the in operation
  • input and print as well as the formatting parameter end and method format. Note that all prompts must match exactly in order to obtain marks, so ensure that you do not alter these prompts.
  • Recursion is allowed but inputs will often be larger than recursion can handle so be cautious!
  • Abstract List Functions map and filter and the keyword lambda
  • Single variable loops, specifically for and while loops.

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE