# Scala Coursera - Week 4

Joe Harry
Ranch Hand
Posts: 10124
3
Joe Harry wrote:decodedSecret was the easiest of all.

Just wanted to check with you guys as to what you got for the following test case when you print out the method calls?

Do you guys also get what I got above?

Any results guys?

Joe Harry
Ranch Hand
Posts: 10124
3
I have a test failure as I submitted my assignment. It is as below:

I guess the problem is with the combine method. What I do in my combine method is simple. I check if the CodeTree passed is less than 2 elements, if yes return doing nothing, else I take the first two Leaf from the List and sum them up and return. For this I use the makeCodeTree method that we already have:

Joe Harry
Ranch Hand
Posts: 10124
3
Sorting my combine function helped me get rid of the error above. I'm still in the gameā¦ Hope to survive till Week 7.

Matthew Brown
Bartender
Posts: 4568
9
combine is supposed to take the first two elements, combine them, and then insert them back into the list. So the structure should still contain all the Leaf elements that it did before.

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34973
379
chris webster wrote:I suppose they want us to practice recursion up and down trees and merging lists/trees, but I'm getting a wee bit tired of all this academic CS101 stuff that I doubt I'll ever need to know again in whatever remains of my career.

I've been trying to avoid this thread until I finish the assignment myself lest I accidentally see something that would influence me. I agree they want us to practice recursion. Under the goal of getting more comfortable with patterns. I don't mind. The goal isn't to finish as fast as possible. I certainly wouldn't have thought of this approach to divide the work on my own though!

decodedSecret confused me for a minute until I realized they weren't actually asking to write a function even though the scaladoc said that.

Wen Tong Lin wrote:HI everyone,
I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.

I originally wrote it with recursion. Pattern matching didn't show up in that function. I then replaced it with a one liner where I got to explore the Scala docs and learn a few new things. I was inspired to do this based on the forums. I did after the recursion way though so I got to practice both ways.

Joe Harry wrote:
Any results guys?

I get the following. However, I am getting
[test failure log] test name: 'createCodeTree(someText)' gives an optimal encoding, the number of bits when encoding 'someText' is minimal
java.util.concurrent.ExecutionException: org.scalatest.exceptions.TestFailedException: 2048 did not equal 1919

so need to look at combine too.

After I got 10/10, the output of your example gave me:
List(Fork(Leaf(e,1),Leaf(t,2),List(e, t),3), Leaf(x,4))
List(Fork(Fork(Leaf(e,1),Leaf(t,2),List(e, t),3),Leaf(x,4),List(e, t, x),7))

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34973
379
chris webster wrote: There are some useful methods on the Scala List class API that will help you do this.

Oh cool! I like that method.

Wen Tong Lin
Greenhorn
Posts: 24
Hi Everyone, thanks for the help with my previous question. Now, I can't seem to figure out the combine() method. I know that if there's only 2 element in the input list, i should return the list. This is a hint that combine() has to be recursive. I just need to create a Fork() with the first 2 element, and then add it in the list.tail and recursively call combine. I was able to get the first element using list.head, but i don't know how to get the second. (I think list.tail.head is a bad idea). Is my approach going in the right direction? Any hint will be greatly appreciated. I already watch the videos twice, and didn't help. Thanks

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:Hi Everyone, thanks for the help with my previous question. Now, I can't seem to figure out the combine() method. I know that if there's only 2 element in the input list, i should return the list. This is a hint that combine() has to be recursive. I just need to create a Fork() with the first 2 element, and then add it in the list.tail and recursively call combine. I was able to get the first element using list.head, but i don't know how to get the second. (I think list.tail.head is a bad idea). Is my approach going in the right direction? Any hint will be greatly appreciated. I already watch the videos twice, and didn't help. Thanks

Why would you want the combine method to be recursive? You just have to get the first two elements in the List and for this a single case statement matching a codeTree would do.

Hope you could figure out the meaning of the sample hint above.

Wen Tong Lin
Greenhorn
Posts: 24
Thanks for the response Joe. I still don't get it. But thanks for the hint. If its not recursive, then that's good to know. I just have to find the first two elements and make use of the pattern matching.

Wen Tong Lin
Greenhorn
Posts: 24
I think I am getting warmer, I was able to extract the second element using this pattern maching

However, the result is wrong, because the trees.tail still contain 2 elements. There's gotta be a recursive call in here.

Wen Tong Lin
Greenhorn
Posts: 24
I got the answer correctly. It passed the unit test. Although I am not sure if this is the right one. Thanks for all the tips Joe.

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:I got the answer correctly. It passed the unit test. Although I am not sure if this is the right one. Thanks for all the tips Joe.

Which method implementation are you referring to? From my experience working on these assignments, combine method was a bit trickier. Everything else is just case match. Once you get that idea implemented for any one of those functions using case match, then the others just follow.

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:I got the answer correctly. It passed the unit test. Although I am not sure if this is the right one. Thanks for all the tips Joe.

Take a look at Week5 video lectures. You have lot of examples and discussions on Pattern matching in Lists. The first 2 videos for Week5 would be really helpful for solving Week4 assignments.

Matthew Brown
Bartender
Posts: 4568
9
More on week 5 at https://www.coderanch.com/t/595326/Scala/Scala-Coursera-Week ...

Wen Tong Lin
Greenhorn
Posts: 24
Thanks Joe. I was referring to the combine method. I used pattern matching, having 2 cases. first if there are only 2 elements, then return the list, second case is, get the first two elements and create a Fork then put the fork in a list and append the tail minus the second. It passed the unit test, but I think the pattern matching that I have created will not work, if there are a lot of data in the input list. That's why I thought it has to be recursive Anyways, thanks for the help. I have submitted the solution and got 4/10. I'll watch week 5 and see if I can find a solution and resubmit.

Matthew Brown
Bartender
Posts: 4568
9
One thing to realise is that a recursive method is needed to process the entire tree. But the combine method isn't doing that - it's only carrying out one step. The until method is where you have to process the whole tree.

Wen Tong Lin
Greenhorn
Posts: 24
Thank you Mathew. So if you have a list with 5 (1,2,3,4,5) elements, and you call combine(), it will return a list of 4 elements = ((1,2), 3,4,5 ) ? because it will only combine element 1, and 2 and append the tail (3,4,5) ? My implementation is doing that. Is that correct? or should it combine ((1,2),(3,4), 5).

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:Thank you Mathew. So if you have a list with 5 (1,2,3,4,5) elements, and you call combine(), it will return a list of 4 elements = ((1,2), 3,4,5 ) ? because it will only combine element 1, and 2 and append the tail (3,4,5) ? My implementation is doing that. Is that correct? or should it combine ((1,2),(3,4), 5).

In that case the combine should actually return (1,2,3,3,4,5).... something of that sort. As you can see from the Scaladoc comments that the combine function just combines the first two elements in the List and adds it at the appropriate position.

Getting combine to work correctly is vital for until and createCodeTree.

Hope you have used pattern matching. Just think of the case where you have the first two elements and the rest of the elements as a case statement:

Like I said before, watching videos 1 and 2 of Week5 will definitely help here!

Wen Tong Lin
Greenhorn
Posts: 24
Thanks Joe. I was able to implement it. The videos really helped! Now I have to do encode() and decode().

Wen Tong Lin
Greenhorn
Posts: 24
Another question. Does createCodeTree(chars: List[Char]):CodeTree, transform the input parameter chars to a tree like structure? I can't visualize the output. again, any help will be greatly appreciated.

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:Another question. Does createCodeTree(chars: List[Char]):CodeTree, transform the input parameter chars to a tree like structure? I can't visualize the output. again, any help will be greatly appreciated.

It will return a CodeTree like Fork(Fork(CodeTree, CodeTree, Weight, Chars)).... For Visualizing the CodeTree, refer to the discussion forums in Coursera. There was a post that describes this.

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:Thanks Joe. I was able to implement it. The videos really helped! Now I have to do encode() and decode().

The idea behind decode is that you have to check for 0 or 1 and the idea behind encode is that you have to check if the characters match. This should help you get started.

Joe Harry
Ranch Hand
Posts: 10124
3

Wen Tong Lin
Greenhorn
Posts: 24
Hi Joe. Thanks for the help. I was able to solve until(). that visualizeTree() method was really helpful. I didn't realize that my implementation of times and combine (which are needed in until) were wrong. Now that I have until() working fine, I have to solve encode(). I know the idea behind encode, which is to walk the tree and count the 0's and 1's.

Wen Tong Lin
Greenhorn
Posts: 24
Actually, I need some hints.

Joe Harry
Ranch Hand
Posts: 10124
3
Wen Tong Lin wrote:Actually, I need some hints.

Take a look at this thread. There are a couple of hints that might help you solve encode.