Complete the following tasks with documentation. The documentation$/$commenting must consist of $($but is not limited to$)$:

$$ For each function, high$-$level description of that function. This should be a two or three

sentence explanation of what this function does.

$$ Your main function in the assignment should contain a generalised description of the

approach your solution uses to solve the assignment task.

$$ For each function, specify what the input to the function is$,$ and what output the function

produces or returns $($if appropriate$).$

$$ For each function, the appropriate Big$-$O or Big$-\backslash$Theta time and space complexity of that

function, in terms of the input size. Make sure you specify what the variables involved

in your complexity refer to$.$ Remember that the complexity of a function includes the

complexity of any function calls it makes.

$$ Within functions, comments where appropriate.

You are an adventurer in FITWORLD $$ a magical world where humans and FITMONs live in

harmony. FITMONs are insanely cute creatures $1$ which make everyone around them happy.

Each FITMON has a cuteness$\_$score where a higher score means a cuter FITMON.

Recently, it was discovered that it is possible to fuse FITMONs together. The fusing process

could increase or decrease the cuteness$\_$score of the resulting FITMON. Thus, you set out to

fuse FITMONs together, to create the very cutest FITMON possible, that no FITMON ever

was. In order to do so$,$ you head over to a FITMON Center.

$1\mathrm{.}1$ Input

You have a list of fitmons:

$$ Contains N fitmon in the list $[0...$N $1].$ N is a non$-$zero, positive integer where N $>1.$

$$ Each fitmon is identified by their index in the fitmons list.

$$ Each fitmon in the list is a list of $3$ values

$[$affinity$\_$left, cuteness$\_$score, affinity$\_$right$].$

$$ affinity$\_$left is a positive float in the range of $0\mathrm{.}1..\mathrm{.}0\mathrm{.}9$ inclusive. Only the left$-$most

fitmons$[0]$ will have an affinity$\_$left of $0$ as there is no fitmon on the left for it to

fuse.

$$ affinity$\_$right is a positive float in the range of $0\mathrm{.}1..\mathrm{.}0\mathrm{.}9$ inclusive. Only the right$-$most

fitmons$[$N$-1]$ will have an affinity$\_$right of $0$ as there is no fitmon on the right for

it to fuse.

$$ cuteness$\_$score is a non$-$zero, positive integer.

An example of the input list fitmons is illustrated below:

fitmons $=[$

$[0,29,0\mathrm{.}9],$

$[0\mathrm{.}9,91,0\mathrm{.}8],$

$[0\mathrm{.}8,48,0\mathrm{.}2],$

$[0\mathrm{.}2,322,0]$

$]$

In this input, fitmons$[1]$ has a:

$$ affinity$\_$left of $0\mathrm{.}9.$

$$ cuteness$\_$score of $91.$

$$ affinity$\_$right of $0\mathrm{.}8.$

$1\mathrm{.}2$ Fusing Logic

From the fitmons list, you realize that each fitmon can only fuse with the adjacent fitmon in

the adjacent fitmon. Your goal is to fuse all of the given fitmons into only $1$ fitmon. Thus:

$$ fitmons$[$i$]$ can only fuse with either fitmons$[$i$-1]$ or fitmons$[$i$+1].$

$$ The affinity for the $2$ fusing fitmons are the same as illustrated in the example input. We

see that fitmons$[$i$][0]$ would have the same value as fitmons$[$i$-1][2]$ and similarly

fitmons$[$i$][2]$ would have the same value as fitmons$[$i$+1][0].$

$$ However, fitmons$[0]$ can only fuse with fitmons$[1]$ as there is no fitmon on its left.

$$ Likewise, fitmons$[$N$-1]$ can only fuse with fitmons$[$N$-2]$ as there is no fitmons on its

right.

$$ Once a fitmon is fused, it no longer exist and thus cannot be used for fusing again.

When $2$ fitmons fuse, their cuteness changes based on their cuteness$\_$score and the affinity

of the fuse. Fusing fitmons$[$i$]$ with fitmons$[$i$+1]$ will create a new fitmon with:

$$ The affinity$\_$left will be based on the affinity$\_$left of the left fitmon,

affinity$\_$left $=$ fitmons$[$i$][0]$

$$ The cuteness$\_$score is computed using the affinity$\_$score of the fusing fitmons multiplied with their cuteness$\_$score based on the following equation,

cuteness$\_$score $=$ fitmons$[$i$][1]*$ fitmons$[$i$][2]+$

fitmons$[$i$+1][1]*$ fitmons$[$i$+1][0]$

$$ The affinity$\_$right will be based on the affinity$\_$right of the right fitmon,

affinity$\_$right $=$ fitmons$[$i$+1][2]$

$$ Note: as the cuteness$\_$score is an integer, you can use int$()$ on it after each and every

fuse; before the next fuse $($if any$).$

Using the example input earlier:

$$ Fusing fitmons$[0]$ with fitmons$[1],$ will produce a fitmon with the value of $[0,108,0\mathrm{.}8].$

$$ Fusing fitmons$[1]$ with fitmons$[2],$ will produce a fitmon with the value of $[0\mathrm{.}9,111,0\mathrm{.}2].$

$$ Fusing fitmons$[2]$ with fitmons$[3],$ will produce a fitmon with the value of $[0\mathrm{.}8,74,0].$

Therefore, you implement a function called fuse$($fitmons$)$ which accepts the list fitmons and

this function would fuse all of the fitmon in the list into a single ultimate final fitmon. The

resulting fitmon will have the highest possible cuteness$\_$score from the fusing.

$1\mathrm{.}3$ Output

The fuse$($fitmons$)$ function would return an integer, where it is the cuteness$\_$score of the

highest possible cutenness$\_$score from fusing all of the fitmons $$ if there are N fitmonns

then you would need N $1$ fuses in total.

$1\mathrm{.}4$ Complexity

The function fuse$($fitmons$)$ must run at the worst$-$case, O$($N$3$

$)$ time and O$($N$2$

$)$ space where

N is the number of items the list fitmons. It is possible for your solution to run better than

the complexity stated here.