Fwd: Diagram of Eric's solution for ex. 3

[Nagappan Alagappan]

FYI

---------- Forwarded message ----------
From: Hieronymus <knowwhere...@yahoo.com>
Date: Sun, Sep 30, 2012 at 5:39 PM
Subject: Diagram of Eric's solution for ex. 3
To: er...@ebiester.com
Cc: Anthony Schexnaildre <apsc...@gmail.com>, Azad Bolour <azadb...@bolour.com>, naga...@gmail.com, David Vydra <da...@vydra.net>, David Sprowls <da...@sprowls.org>, all...@oceanpark.com, Michael Reardon <michael...@incept5.com>, Jeff Miller <jeffrey...@gmail.com>


Tip o' the hat to Eric for providing such a simple and elegant solution to ex 3. I started to have an "Ah ha, of course" moment the minute I saw it. But it actually helped me to draw the actual tree to see just how it's performing its magic. So Eric's function splits the recursion into a head reduction series and a tail reduction series that are summed back together at every return going back to the top. No tallys need be made on actual coins or monitory amounts; The split assures that every combination of coins is travered, and those that end up in either empty money (0) or empty coins prove a viable factoring branch.

Once again, glad to be in the group.
Cheers, Richard

--
Linux Desktop (GUI Application) Testing Project - http://ldtp.freedesktop.org
Cobra - Windows GUI Automation tool - https://github.com/ldtp/cobra
http://nagappanal.blogspot.com

[Nagappan Alagappan]

---------- Forwarded message ----------
From: Dennis G Allard <all...@oceanpark.com>
Date: Tue, Oct 2, 2012 at 9:51 AM
Subject: My "submission" for Scala Week 1 Assignment (including verbose countChange output)
To: Anthony Schexnaildre <apsc...@gmail.com>, Azad Bolour <azadb...@bolour.com>, "naga...@gmail.com" <naga...@gmail.com>, David Vydra <da...@vydra.net>, Hieronymus <knowwhere...@yahoo.com>, "er...@ebiester.com" <er...@ebiester.com>, Michael Reardon <michael...@incept5.com>
Cc: David Sprowls <da...@sprowls.org>, "all...@oceanpark.com" <all...@oceanpark.com>

I really wanted to catch up and not "peek" at other's solutions
for Week 1.

I solved countChange last night (on paper) but did not code it
until this morning.

I have to admit that was work.  I did nail it.

But...

Too late to submit!!  (deadline was midnight).

Worse, I had coded the other two exercises a few days ago and
never did a preliminary submit.  So my score so far in this course
is zero!

In the interest of team collaboration, I hereby "submit" my
solutions to the team.

Note - I include a "Verbose" version of countChange and show
that output below.

As you all know, the most interesting exercise was countChange.

Since I recall Eric's solution (Jeff's?) was very elegant (but
I did not pay enough attention to it to "cheat") - I still had
to struggle with the algorithm on paper.  I suspect that mine
can be reduced by code substitution, perhaps eliminating one of
the auxiliary functions (see my Exercise 3 solution, below).

I didn't have time this morning to simplify, but I was happy
to have coded an algorithm that mirrors the tree of all possible
denomination sequences that make change for the input money.


  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int =
    if (c == 0 || c == r) 1
    else pascal(c-1,r-1) + pascal(c,r-1)

 
  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
      def bal(parity: Int, chars: List[Char]): Boolean =
        if (chars.isEmpty) parity == 0
        else if (chars.head == '(') bal(parity+1, chars.tail)
        else if (chars.head == ')') bal(parity-1, chars.tail)
        else bal(parity, chars.tail)
      bal(0,chars)
    }

  /**
   * Exercise 3 - [ I suspect I can reduce my code via substitution ]
   */
  def countChange(money: Int, denoms: List[Int]): Int = {
    def countAux(money: Int, denoms: List[Int]): Int =
      if (denoms.head == money) 1
      else if (denoms.head > money) 0
      else traverse(money - denoms.head, denoms)
    def traverse(money: Int, denoms: List[Int]): Int =
      if (denoms.isEmpty) 0
      else countAux(money, denoms) + traverse(money, denoms.tail)
    traverse(money, denoms)
  }

  def countChangeVerbose(money: Int, denoms: List[Int]): Int = {
    def countAux(money: Int, denoms: List[Int], change: List[Int]): Int =
      if (denoms.head == money) {
        println(change); 1
      }
      else if (denoms.head > money) 0
      else traverse(money - denoms.head, denoms, change)
    def traverse(money: Int, denoms: List[Int], change: List[Int]): Int = {
      if (denoms.isEmpty) 0
      else countAux(money, denoms, denoms.head::change) + traverse(money, denoms.tail, change)
      }
    println
    println("Change for : "+ money + " using denominations: " + denoms + " ...")
    traverse(money, denoms, List())
  } 

}


Example outputs:

Pascal's Triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1


Balance examples...
(this is (a) test) = true
(this is a) test) = false
(this is (a test) = false


Count change examples...

Change for : 25 using denominations: List(5, 10) ...
List(5, 5, 5, 5, 5)
List(10, 5, 5, 5)
List(10, 10, 5)
3

Change for : 7 using denominations: List(1, 5, 10) ...
List(1, 1, 1, 1, 1, 1, 1)
List(5, 1, 1)
2

Change for : 35 using denominations: List(5, 10, 25) ...
List(5, 5, 5, 5, 5, 5, 5)
List(10, 5, 5, 5, 5, 5)
List(10, 10, 5, 5, 5)
List(25, 5, 5)
List(10, 10, 10, 5)
List(25, 10)
6

[Nagappan Alagappan]

Hello,

I just checked this email, my bad.

Thanks

Nagappan

---------- Forwarded message ----------
From: Hieronymus <KnowWhere...@yahoo.com>
Date: Sat, Sep 29, 2012 at 12:45 PM
Subject: Re: Scala FP post first assignment: thoughts? topics?
To: David Vydra <da...@vydra.net>
Cc: Azad Bolour <azadb...@bolour.com>, Jeff Miller <jeffrey...@gmail.com>, "er...@ebiester.com" <er...@ebiester.com>, "michael...@incept5.com" <michael...@incept5.com>, "naga...@gmail.com" <naga...@gmail.com>, "apsc...@gmail.com" <apsc...@gmail.com>, "all...@oceanpark.com" <all...@oceanpark.com>, David Sprowls <da...@sprowls.org>

Does everyone know that Martin Odersky is going to be speaking (presenting Scala 2.10) in San Francisco on Monday? Check out this MeetUp link:

http://www.meetup.com/SF-Scala/events/83514372/?a=co1_grp&rv=co1

--Richard

Intel hosts Dr. Martin Odersky presenting Scala 2.10

• Monday, October 1, 2012

  6:30 PM to 9:00 PM

• Lettermen Digital Arts Center (Building A- Dining Commons)

  1 Letterman Drive, , San Francisco, CA (edit map)

• Register at: http://www.eventbrite.com/event/4339491536

  
  

On Sep 29, 2012, at 11:16 AM, Hieronymus wrote:

I'm looking forward to joining the group tomorrow (my first session) as David was nice enough to invite me after I stuck my nose under the tent. I did ok on the warm up and first two exercises for week 1--the the third one I've not been able to complete successfully. I thought I knew the basics of recursion, but the constraint of having to factor all combinations of coins (as opposed to a straight factorial, has added a level of complication which I haven't been able to suss out. Maybe some of the more enlightened minds in the group can help me with some tips (is it ok, to use a for loop inside of the recursion to handle the permutations of repeating coins? Or should that also be recursive?

Azad, I hope you are on the mend! The good thing about Coursera is that there is literally no high price to pay for missing a deadline! We'll help you catch up!

Richard

On Sep 29, 2012, at 10:05 AM, David Vydra wrote:

Azad,

I am sure I am speaking for everyone in our group in wishing you a

speedy recovery!

Coursera and Udacity have just started and they have a long way to go

to figure out the UX in such a way that benefits different styles of

learning. About 20 years ago, I took a course in educational software

design at Northwestern and the team there was working on tools to

train military logistics officers that included outlines, text and a

jukebox of video disks each the size of an LP record. From what I

recall, in some ways it was better than where Coursera is right now.

I like video from brilliant, engaging presenters that is appropriately

split into small segments and driven from an outline. I predict that

in time we will see a trend that the best presenters are not

necessarily the 'famous' research professors.

I'll search for other video content on functional programming.

I am sure tomorrow we will finally  spend more time looking at code. :)

-d

On Sat, Sep 29, 2012 at 3:26 AM, Azad Bolour <azadb...@bolour.com> wrote:

Hello Fellow Students,

You may have heard from David that I was hospitalized for the last 10 days,

and had to miss the session last Sunday. I'll try to make it to tomorrow's

session, but will likely be far behind you guys.

As I watched the first 5 video lectures, I had similar feelings as expressed

by Jeff. The lectures seemed to follow the material in the Structure and

Interpretation book fairly closely. The major added benefit was seeing the

incarnation of the concepts in Scala. But I felt that the concepts

themselves were glossed over somewhat lightly. For example, I would have

liked to see a deeper discussion of substitution semantics. Maybe this is

just backgound material that is expected to be known, and is just being

reviewed, and when we get into the meat of the course, the expositions will

be deeper.

I am also somewhat disappointed in the fact that there are deadlines for

submitting assignments, for obvious reasons due to my current circumstance.

It seems that one of the major benefits of online learning is independence

from arbitrary time constraints. At least that was my expectation going into

the course and not reading the fine print.

Azad

On 9/28/2012 11:55 PM, Jeff Miller wrote:

Dear Study Group,

I'm interested to know if anyone has had any particular impressions or

thoughts regarding the beginning of the course.

So far the first assignment (as well as the warmup) seemed like a fairly

gentle introduction to recursive methods.

I'm a bit behind on the video lectures. Internet video is not my favorite

medium; I like to be able to scan an outline, pause, and follow at my own

pace, as hyperlinked written content has trained me.  Anyone have any

thoughts on whether the videos are doing a good job conveying the course

content?

My thoughts on the warm-up ("example") exercise calculating sum and max of a

list:

Calculating the sum of a large list (10000 integers, provided by range()),

provokes a stack overflow.  I think if I change the logic so that the

recursion is pure tail recursion rather than an arithmetic expression

containing a tail-recursive call, the compiler may perform better.  Result:

confirmed.  The revised sum(List[Int]) method calculates much bigger lists.

Unfortunately large sum operations silently lose a great deal of arithmetic

precision.

How are people doing on the lectures and homework?

-- Jeff Miller

--

http://www.testdriven.com

http://twitter.com/vydra

Confidentiality Notice:This e-mail message, including any attachments,

is for the sole use of intended recipient(s) and may contain

confidential and protected information. Any unauthorized review, use,

disclosure or distribution is prohibited. If you are not the intended

recipient, please contact the sender by reply e-mail and destroy all

copies of the original message.

In the absence of an expressed statement to the contrary, nothing in

this e-mail constitutes an electronic signature.

[Sharmin Choksey]

Hi Folks,

I am seriously running late on my second assignment and haven't had a chance to review week 3 lectures.

Not sure if I'll get time between now and Thurs evening to review them.  I will try to make it some how this Thurs, hopefully no more surprises at work.

At this point, I'm more inclined to do reference reading before attempting the assignments, wasted about an hour or so figuring out why the "type" alias wouldn't work in the worksheet.

So far, I've been really amazed at how powerful the FP one liners are.

=Sharmin

--
You received this message because you are subscribed to the Google Groups "Scala discussion based on Coursera" group.
To unsubscribe from this group, send email to scala-courser...@googlegroups.com.
Visit this group at http://groups.google.com/group/scala-coursera?hl=en.
 
 

[Robert Kohlenberger]

Spoke briefly to Martin before his talk.  But he wouldn't give up any of the homework answers!

;+)

[Pankaj Gupta]

Hey Guyz,

I have to meet some friends who are in town and can't make it to the study group today. Hope you guyz have a great discussion. Will catch up next week.

Pankaj

[Nagappan Alagappan]

Hi Pankaj,

We will meet only tomorrow :-)

Thanks

Nagappan

Pankaj

--
You received this message because you are subscribed to the Google Groups "Scala discussion based on Coursera" group.
To unsubscribe from this group, send email to scala-courser...@googlegroups.com.
Visit this group at http://groups.google.com/group/scala-coursera?hl=en.

[Robert Kohlenberger]

Had the same problem with "type" alias in the worksheet.  Ended up just not using a Set type, and replaced alias "Set" with its signature everywhere in the worksheet.  Even Martin had trouble with the worksheet on Monday night.

Reviewing my 2nd homework submission, it's really true that everything except "forall" is a 1-liner, and the exact structure of forall is given.  Look at what each method returns, and write a conditional with the same input, output signature. "exists" can use "forall" and "map" can use "exists".  Best thing to do is carefully read the assignment instructions and the comments in FunSets.scala.

In FunSetSuite.scala, I defined a couple of small sets in TestSets that partially overlap (-2..2 and 1..3) and use these in combination in several of the tests.  Again, reading the source comments really helps!

If you're running late near a deadline, go ahead and submit a partial assignment.  You can aways resubmit later with no penalty to improve your score.

Good luck!  - Bob

[Pankaj Gupta]

lol. Totally forgot it is Wednesday today (or was until an hour ago). Just finished the third assignment. Meet you guyz tomorrow.

Pankaj