Working through Ch.10 for learning to program 2.0 (Chris Pine)

ruby-talk
21

JD JD wrote in post #1117223:

My guess is it would involve a while loop that does a swap something
like this:

if a>b
X++
Y++
elsif a==b
check next letter and compare
else
swap a and b

Here's a bit of advice, with which I think everyone will agree: this is
confusing, and because it's confusing, it's the wrong thing to do. What
you're writing is a description of an algorithm, however the way you're
writing it is a little bit "bottom-up" -- that is, you're starting by
writing something that looks like "computer language", and trying to
squeeze that into your mental model for sorting.

The way to write an algorithm is:
1. start with a prose description of the actions (in plain language,
like you're talking to a human)
2. trim the description down to smaller, more "atomic" or simple actions
3. repeat #2
4. repeat #3
5. when the actions are all very small and simple, add some syntax (like
semicolons or braces or dollar signs)

After step 5, you have your algorithm, implemented in the programming
language of your choice.

Here are a couple of descriptions of sorting algorithms, written at one
step below prose:

1. look at each item in the list, comparing it to the next item:
1.1. if the next item is less than the current item, swap them
2. when you reach the end of the list, if you did any swaps, go back to
step 1 and start over

That's called "bubble sort."

1. designate a second list, called the "sorted list"
2. take an item from the unsorted list (call the item "X")
3. look at each item in the sorted list:
3.1. if X is less than the unsorted item, put X into the sorted list
immediately before the unsorted item that's bigger than it
4. if you get to the end of the unsorted list without putting X in, add
X to the end of the unsorted list
5. if any items remain in the unsorted list, go back to step 2 and
repeat

That's called "insertion sort."

There are lots of others, but I'm given to understand that these are the
easiest to describe and understand.

Personally I find bubble sort easier to implement recursively, but
they're both quite simple once you get the operations small enough, and
add in some syntax.

···

--
Posted via http://www.ruby-forum.com/\.

22

So, I am just taking a detour away from the book for a bit and trying
something else and will go back to it. I glanced at the solution for
one you all wrote out. The book didn't really go over a lot of what you
all are doing.

When I go back to the book, I'm going to attempt to do it without
recursion and then with recursion. However, I am really curious if
someone could give me a semi hint on how to do it without recursion
based off my card swap example.

My guess is it would involve a while loop that does a swap something
like this:

if a>b
X++
Y++
elsif a==b
check next letter and compare
else
swap a and b

Let me explain a little bit what I did, expanding the one liner. I
started with your description of the select sort algorithm:

So, here is how to do it with cards. Basically, you look at the first
card and compare it with the second. If its smaller, you compare it to
the next one, etc. etc. until you either find a smaller card or you
don't. If you do find a smaller card, you swap the cards. If you
don't, you leave them.
Then you move on to the second card and do the same thing. You do this
until you get to the last card (which should be the biggest at this
point).

So, there's a loop from the first to the last. In each step of the
loop I look for the smaller value from the remaining. I do it with
min, but in your explanation you do it comparing each two elements. If
the smallest is smaller than the value you are looking at, you swap
them. Then you continue with the loop:

p a.each_with_index {|e,i| (x = a[i..-1].find_index(a[i..-1].min)) &&
((a[i],a[i+x]=a[i+x],a[i]) if a[i+x] <= e) }

Expanding it:

a.each_with_index do |current, i|
  # find the min from the rest of the array
  min = a[1..-1].min # this could be replaced by another loop over
a[1..-1] with a temporary variable holding the smallest seen, and
another with the index where that is
  min_index = a[1..-1].find_index(min) # the index relative to the
rest of the array

  # if min is smaller than the one we are looking at (i) we swap them
  if min < e
    a[i],a[i+x]=a[i+x],a[i]
  end
end
# print it
p a

Hope this helps,

Jesus.

···

On Wed, Jul 31, 2013 at 5:00 AM, JD KF <lists@ruby-forum.com> wrote:

23

So, I am just taking a detour away from the book for a bit and trying
something else and will go back to it. I glanced at the solution for
one you all wrote out. The book didn't really go over a lot of what you
all are doing.

Please do not take these one-liners as examples on how you should
write your code. I consider them more as riddles or katas than
as good solutions for a beginning programmer (or maybe even for
an expert programmer). They are cryptic and not too easy to
understand, and good "real" code should be neither.

Considering your pseudo code (I do not know how your real code looks
like, but just to make sure): beware of using one letter variable
names! The additional time for typing is only spent once, but
cryptic code causes extra time spent every time you need to re-read
through it when searching for bugs, etc.

Marcus, it sounds like you read the same book. Could you maybe give me
a hint based off what I should know from the book? It looks like many
people here are using things that weren't taught in the book. Not
saying they are wrong, but it not something I probably know from what I
read in the book. I might be wrong though. I'm still learning either
way.

Matthew gave very good advice. Think in small steps, write them down,
break them up even more. I would like to add that IMO the selection
sort algorithm I described earlier is even a bit simpler than
insertion sort (of course, it's partially a matter of taste).
The biggest subtask there is to find the smallest element of the
array and its index.

I'll give an example implementation below, you can ignore it for
the time being, or have a peak and then try on your own, whatever.
It uses only the most basic array operations (like accessing,
pushing or deleting elements).
There is another versions that uses Array#min (which could be
considered cheating, but it's an exercise and you make the rules).
It might help further in understanding how the algorithm works.

BTW. Don't be discouraged by chapter 10. Not without reason
Chris Pine calls it a "rite of passage". And: you know that
the appendix has suggestions for possible solutions, often
more than one?

Regards,
Marcus

Without Array#min (the biggest block is only for finding
of the smallest value):

  unsorted = [8, 4, 0, 9, 2, 6, 5, 9, 2, 7]
  sorted =

  while unsorted.size > 0 do # more rubyish: until unsorted.empty? do
    smallest = unsorted[0]
    index_of_smallest = 0

    1.upto(unsorted.size - 1) do |index| # more rubyish: each_with_index
      if unsorted[index] < smallest
        smallest = unsorted[index]
        index_of_smallest = index
      end
    end

    sorted << smallest
    unsorted.delete_at(index_of_smallest)
  end

  p sorted # => [0, 2, 2, 4, 5, 6, 7, 8, 9, 9]

The same using Array#min:

  unsorted = [8, 4, 0, 9, 2, 6, 5, 9, 2, 7]
  sorted =

  while unsorted.size > 0 do
    smallest = unsorted.min
    index_of_smallest = unsorted.index(smallest)

    sorted << smallest
    unsorted.delete_at(index_of_smallest)
  end

  p sorted

···

Am 31.07.2013 05:02, schrieb JD JD:

--
GitHub: stomar (Marcus Stollsteimer) · GitHub
PGP: 0x6B3A101A

24

Just curious, is that solution a selection sort solution or insertion
sort? Also, the one described in the book, is that selection or
insertion (the one he writes out in plain words)?

That shouldn't be too difficult to figure out, also I already told you
in a previous post :slight_smile:

I guess my issue with the book is it took a massive jump after Ch. 8.
Ch. 9 I had to look in the back of the book and type out was written.
Reading the code afterwords, I can understand what is going on. It may
just be the Roman numerals, but it took a massive jump in Ch. 9 and this
one.

Studying given examples and afterwards re-implementing it by yourself,
maybe a little different, is a good way to practice, too.

Regards,
Marcus

···

Am 01.08.2013 04:52, schrieb JD JD:

--
GitHub: stomar (Marcus Stollsteimer) · GitHub
PGP: 0x6B3A101A

25

its not Ruby specific (i believe it uses python) but
http://software-carpentry.org/ aims to teach basic programming to scientist
So assumes a fairly intelligent student but not necessarily very computer
savvy

···

On Thu, Aug 1, 2013 at 10:15 PM, JD JD <lists@ruby-forum.com> wrote:

Sorry, I didn't realize that. I read that, but didn't know if that was
what the code was below that writing (mainly because I didn't look at
the code yet for reason obvious).

Marcus, do you have any good website/book/etc. that would be helpful
from going from complete "novice" to "pretty good"? I know everyone
says this book is good, but I think it jumps too fast after ch. 9.

Is there one that is really good at that doesn't jump so fast without
giving plenty of examples beforehand (not answers of course, but
examples are helpful)? Anything?

--
Posted via http://www.ruby-forum.com/\.

26

I want to pass along this offer from O'Reilly which offers a couple of books on the computational aspects of programming, rather than the language specific concepts.

I'm not affiliated with O'Reilly in any way, just a customer.

I'm going to snap these up and go through them and I'll write up a review on them at some point, but not likely before the sale ends.

···

On Aug 1, 2013, at 9:15 PM, JD JD <lists@ruby-forum.com> wrote:

Sorry, I didn't realize that. I read that, but didn't know if that was
what the code was below that writing (mainly because I didn't look at
the code yet for reason obvious).

Marcus, do you have any good website/book/etc. that would be helpful
from going from complete "novice" to "pretty good"? I know everyone
says this book is good, but I think it jumps too fast after ch. 9.

Is there one that is really good at that doesn't jump so fast without
giving plenty of examples beforehand (not answers of course, but
examples are helpful)? Anything?

--
Posted via http://www.ruby-forum.com/\.

27

Not sure... there might be a gap where it's difficult to find *the*
right book. Chris Pine's book is for complete beginners and covers
only the very basics, whereas many other recommended books are
targeted at programmers with at least *some* experience.

In general, there are plenty of resources out there: there are
certainly many recommendations in the ruby-talk archives,
there are also some links on ruby-lang.org, and many tutorials,
examples, etc. that can be found in the internet.

Consider also a different (but less guided) approach:

Start writing small programs that do things you need to get done,
or that interest you, and then search the internet or ask for
advice on this list when you get stuck.

Gather some experience and then have a look at books about
object-oriented design, more idiomatic Ruby, whatever.

Regards,
Marcus

···

Am 02.08.2013 04:15, schrieb JD JD:

Marcus, do you have any good website/book/etc. that would be helpful
from going from complete "novice" to "pretty good"? I know everyone
says this book is good, but I think it jumps too fast after ch. 9.

Is there one that is really good at that doesn't jump so fast without
giving plenty of examples beforehand (not answers of course, but
examples are helpful)? Anything?

--
GitHub: stomar (Marcus Stollsteimer) · GitHub
PGP: 0x6B3A101A

28

[...]

Just out of curiosity, do you mean this page:

http://pine.fm/LearnToProgram/?Chapter=10

? Because in this page, the words 'sorting' and 'sorted' can't be
found. I was surprised that a tutorial would ask you to write a
sorting algorithm, without describing the algorith you should use.

Could be different in the new version… the online one is v1.

Indeed, chapter 10 in the printed book is different.
And the sorting algorithm is described there, see my earlier reply.

Regards,
Marcus

···

Am 28.07.2013 15:45, schrieb Tamara Temple:

On Jul 28, 2013, at 5:26 AM, "Carlo E. Prelz" <fluido@fluido.as> wrote:

--
GitHub: https://github.com/stomar/
PGP: 0x6B3A101A

29

I'd like to see it too. Also RE: Sto.Mar's post

···

On Mon, Jul 29, 2013 at 10:34 AM, <sto.mar@web.de> wrote:

Am 29.07.2013 16:43, schrieb Harry Kakueki:
> I tried this and came up with a one-liner that seems to do it. It sorts
> the array and prints the result.

Just to make sure: you do not use Array#sort?

Regards,
Marcus

--
GitHub: https://github.com/stomar/
PGP: 0x6B3A101A

--
*Richard Wilson*
Sechelt Innovations
Cell - (604) 842 5318
Skype - r.crawfordwilson
Email - r.crawfordwilson@gmail.com

“*This email may contain confidential and/or privileged information. If you
are not the intended recipient or have received this email in error, please
notify the sender immediately and destroy this email. Any unauthorized
copying, disclosure or distribution of the information contained on this
email is prohibited”.*

30

Nooooooo :slight_smile: That would be cheating. Also, no semicolons :slight_smile:

Harry

···

On Tue, Jul 30, 2013 at 2:34 AM, <sto.mar@web.de> wrote:

Am 29.07.2013 16:43, schrieb Harry Kakueki:
> I tried this and came up with a one-liner that seems to do it. It sorts
> the array and prints the result.

Just to make sure: you do not use Array#sort?

Regards,
Marcus

--
GitHub: https://github.com/stomar/
PGP: 0x6B3A101A

31

This is my one liner:

p a.each_with_index {|e,i| (x = a[i..-1].find_index(a[i..-1].min)) &&
((a[i],a[i+x]=a[i+x],a[i]) if a[i+x] <= e) }

It uses min which feels a bit like cheating, but there it is.

Jesus.

···

On Tue, Jul 30, 2013 at 3:42 PM, Harry Kakueki <list.push@gmail.com> wrote:

I have not heard from the OP for almost 24 hours, so I will post an idea.

a = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]

#one-line version
p .tap{|b| (0...a.size).each{|c| a.each{|d| b << d if a.select{|e|
e<d}.size==c}}}

32

Harry Kakueki wrote in post #1117089:

Nooooooo :slight_smile: That would be cheating. Also, no semicolons :slight_smile:

Harry

Yeah, semicolons are for noobs. These are single-SLOC snippets.

Matty

···

--

--
Posted via http://www.ruby-forum.com/\.

33

Ohhhh, a quiz, a quiz !!! I want in... When can we post our solutions?

Jesus.

···

On Tue, Jul 30, 2013 at 4:20 AM, Matthew Kerwin <lists@ruby-forum.com> wrote:

Harry Kakueki wrote in post #1117089:

Nooooooo :slight_smile: That would be cheating. Also, no semicolons :slight_smile:

Harry

Yeah, semicolons are for noobs. These are single-SLOC snippets.