I came across another codechef problem which I am attempting to solve in Scala. The problem statement is as follows:
Stepford Street was a dead end street. The houses on Stepford Street were bought by wealthy millionaires. They had them extensively altered so that as one progressed along the street, the height of the buildings increased rapidly. However, not all millionaires were created equal. Some refused to follow this trend and kept their houses at their original heights. The resulting progression of heights was thus disturbed. A contest to locate the most ordered street was announced by the Beverly Hills Municipal Corporation. The criteria for the most ordered street was set as follows: If there exists a house with a lower height later in the street than the house under consideration, then the pair (current house, later house) counts as 1 point towards the disorderliness index of the street. It is not necessary that the later house be adjacent to the current house. Note: No two houses on a street will be of the same height For example, for the input: 1 2 4 5 3 6 The pairs (4,3), (5,3) form disordered pairs. Thus the disorderliness index of this array is 2. As the criteria for determining the disorderliness is complex, the BHMC has requested your help to automate the process. You need to write an efficient program that calculates the disorderliness index of a street.
A sample input output provided is as follows:
Input: 1 2 4 5 3 6
Output: 2
The output is 2 because of two pairs (4,3) and (5,3)
To solve this problem I thought I should use a variant of MergeSort,incrementing by 1 when the left element is greater than the right element.
My scala code is as follows:
def dysfunctionCalc(input:List[Int]):Int = {
val leftHalf = input.size/2
println("HalfSize:"+leftHalf)
val isOdd = input.size%2
println("Is odd:"+isOdd)
val leftList = input.take(leftHalf+isOdd)
println("LeftList:"+leftList)
val rightList = input.drop(leftHalf+isOdd)
println("RightList:"+rightList)
if ((leftList.size <= 1) && (rightList.size <= 1)){
println("Entering input where both lists are <= 1")
if(leftList.size == 0 || rightList.size == 0){
println("One of the lists is less than 0")
0
}
else if(leftList.head > rightList.head)1 else 0
}
else{
println("Both lists are greater than 1")
dysfunctionCalc(leftList) + dysfunctionCalc(rightList)
}
}
First off, my logic is wrong,it doesn't have a merge stage and I am not sure what would be the best way to percolate the result of the base-case up the stack and compare it with the other values. Also, using recursion to solve this problem may not be the most optimal way to go since for large lists, I maybe blowing up the stack. Also, there might be stylistic issues with my code as well.
I would be great if somebody could point out other flaws and the right way to solve this problem.
Thanks