In this problem, we wish to implement a function `outputConsecutivePairsLinearTime` that solves the exact same problem as in __Part(A)__ but takes time linear in the size of the input list. To do so, we would like you to use the `::` or Cons operator on a list that appends an element to the __front__ of a list. ~~~ val l1 = List(1, 2, 3) val l2 = 25 :: l1 // place 25 and then the contents of list l1. // list l2 is List(25, 1, 2, 3) ~~~ You may also want to use the list reverse function ~~~ val l = List(1, 2, 5, 6, 7, 8) val r = l.reverse println(r) // r is the reverse of list l, this works in linear time in the size of the list. ~~~ **Restrictions** remain the same as problem 1. But we would like you to focus on ensuring that your solution runs in linear time. // YOUR CODE HERE ??? //BEGIN TEST val lst1 = List((1,1), (-1, 1), (1, -1)) val out1 = outputConsecutivePairsLinearTime(lst1) testWithMessage( out1, List( (1,1)), "test1") val lst2 = List((1, 2), (2, 1), (1,0), (0,1), (1,1)) val out2 = outputConsecutivePairsLinearTime(lst2) testWithMessage( out2, lst2, "test2") val lst3 = List((1,5), (5,1)) val out3 = outputConsecutivePairsLinearTime(lst3) testWithMessage(out3, Nil, "test3") val lst4 = List((2,5), (1,2), (-5, -4), (4,1)) val out4 = outputConsecutivePairsLinearTime(lst4) testWithMessage(out4, List((1,2), (-5,-4)), "test4") passed(5) //END TEST //BEGIN TEST //create a list of milion pairs val longTestList = (1 to 1000000).map ( x => (x, x-1)).toList //run the function you wrote outputConsecutivePairsLinearTime(longTestList) // this better finish in <= 15 seconds //END TEST
(I need help coding for problem B but posted part A because they use some of the same perimeters; an explanation would be appreciated. In Python, please, Thank you.)
### Part (A)
Given a list of pairs of integers, for example
~~~
List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )
~~~
Output a list consisting of just those pairs $(n_1, n_2)$ in the original list wherein $ | n_1 - n_2 | \leq 1 $. Ensure that the order of the elements in the output list is the same as that in the input list.
For the example above, the expected output is:
~~~
List( (15,14), (18,19), (0,0) )
~~~
__Note__
- Your function must be called `outputConsecutivePairs` with just one argument that must be a list of pairs of integers. It must return a list of pairs of integers.
- You can use for-loops and the following operators for concatenating elements to list.
- `::` or cons appends an element to the front of a list.
- `:+` appends an element to the back of a list.
- `++` appends two lists together.
- You can use list API functions: `reverse` and `length`
- You should not use any other list API functions including `filter`, `map`, `foldLeft`, `foldRight` and so on.
- Plenty of time to learn them properly later on.
- Do not try to convert your list to an array or vector so that you can mutate it.
- There are no restrictions on the use of vars.
__Hints__
- In Scala, pairs of integers have the type `(Int, Int)`
- A list containing pairs of integers has the type : `List[ (Int, Int) ]`.
- Here is how one iterates over the elements of a list in Scala
~~~
for (elt <- list) {
// do stuff with elt
}
~~~
- Appending an element to the end of a list (see below).
~~~
result_list = result_list :+ elt // result_list must be declared as a var
~~~
- Appending an element to the front of a list :
~~~
result_list = elt:: result_list // using cons
~~~
- Appending an element to the end of a list
~~~
result_list = result_list ++ List(elt) // use list concatenation
~~~
- Warning: The append at end of a list `:+` (or other operations like list concat `++`) operation takes $O(n)$ time, where $n$ is the size of the list. We will often try to avoid it. But OK to use it for this particular part of problem 1.
### Part (B)
If you followed the hint we provided in part (A), you would have used the :+ or ++ operation to append an element to the end of a list at each step.
for ... { // iterate over a loop ... new_list = new_list :+ new_element // this takes O( size of new_list ) }
Each :+ or ++ operation requires a full list traversal to find the end of the list and append to the end. The overall
To illustrate: cut & paste/run this code in a new test cell. Just remember to delete that cell before you submit. It will take a long time to run.
//create a list of 1,000,000 pairs val longTestList = (1 to 1000000).map ( x => (x, x-1)).toList //run the function you wrote outputConsecutivePairs(longTestList) //This will take a long time to finish.
In this problem, we wish to implement a function `outputConsecutivePairsLinearTime` that solves the exact same problem as in __Part(A)__ but takes time linear in the size of the input list.
To do so, we would like you to use the `::` or Cons operator on a list that appends an element to the __front__ of a list.
~~~
val l1 = List(1, 2, 3)
val l2 = 25 :: l1 // place 25 and then the contents of list l1.
// list l2 is List(25, 1, 2, 3)
~~~
You may also want to use the list reverse function
~~~
val l = List(1, 2, 5, 6, 7, 8)
val r = l.reverse
println(r) // r is the reverse of list l, this works in linear time in the size of the list.
~~~
**Restrictions** remain the same as problem 1. But we would like you to focus on ensuring that your solution runs in linear time.
// YOUR CODE HERE
???
//BEGIN TEST
val lst1 = List((1,1), (-1, 1), (1, -1))
val out1 = outputConsecutivePairsLinearTime(lst1)
testWithMessage( out1, List( (1,1)), "test1")
val lst2 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))
val out2 = outputConsecutivePairsLinearTime(lst2)
testWithMessage( out2, lst2, "test2")
val lst3 = List((1,5), (5,1))
val out3 = outputConsecutivePairsLinearTime(lst3)
testWithMessage(out3, Nil, "test3")
val lst4 = List((2,5), (1,2), (-5, -4), (4,1))
val out4 = outputConsecutivePairsLinearTime(lst4)
testWithMessage(out4, List((1,2), (-5,-4)), "test4")
passed(5)
//END TEST
//BEGIN TEST
//create a list of milion pairs
val longTestList = (1 to 1000000).map ( x => (x, x-1)).toList
//run the function you wrote
outputConsecutivePairsLinearTime(longTestList)
// this better finish in <= 15 seconds
//END TEST
Step by step
Solved in 4 steps
