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

mightypants · July 30, 2013, 11:28pm

Awesome, three completely different implementations.

Mine’s:

a.inject []{|s,x|(i=s.find_index{|y|y>=x})?s[0…i]+[x]+s[i…-1]:s+[x]}

mightypants · July 31, 2013, 5:02am

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

Honestly its a bit confusing to me. I haven’t thought about it much
because again I am taking a quick detour away from the book and trying
an online detour to see if it might help me. I get the idea of it, I
just have a hard time putting it into ruby code I guess.

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.

mightypants · July 30, 2013, 5:14pm

On Tue, Jul 30, 2013 at 3:42 PM, Harry K. [email protected]
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}}}

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.

mightypants · July 31, 2013, 5:24am

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:

start with a prose description of the actions (in plain language,
like you’re talking to a human)
trim the description down to smaller, more “atomic” or simple actions
repeat #2
repeat #3
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:

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
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.”

designate a second list, called the “sorted list”
take an item from the unsorted list (call the item “X”)
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
if you get to the end of the unsorted list without putting X in, add
X to the end of the unsorted list
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.

mightypants · July 31, 2013, 11:46am

Am 31.07.2013 05:02, schrieb JD JD:

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 P. 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

mightypants · July 31, 2013, 9:08am

On Wed, Jul 31, 2013 at 5:00 AM, JD KF [email protected] wrote:

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.

mightypants · August 1, 2013, 4:52am

Thanks for the input everyone. Matthew, thanks for taking the time to
write this. This is actually something I think I needed to read. It
helps me actually think about how to possibly solve these issues.

Also, Marcus, I will try to keep my code clean. Also, I will try not to
peak at your solution until I go back to the book and try again at it.
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)?

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.

Is there any book that might not take such a massive jump that might be
good to read as well? I really want to learn how to do ruby. It just
seems either things are too “basic” or they take “to big of jumps”.
This book was great until Ch. 9. It provided good learning material and
realistic but good problems. Do you have any ideas or this?

mightypants · August 2, 2013, 4:15am

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?

mightypants · August 1, 2013, 11:24am

Am 01.08.2013 04:52, schrieb JD JD:

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

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

mightypants · August 2, 2013, 10:11pm

On Aug 1, 2013, at 9:15 PM, JD JD [email protected] wrote:

examples are helpful)? Anything?

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

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.

mightypants · August 2, 2013, 6:09am

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

mightypants · August 3, 2013, 4:04pm

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?

Not sure… there might be a gap where it’s difficult to find the
right book. Chris P.'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

mightypants · August 6, 2013, 3:10am

So, I tried to think about this stuff and I really don’t understand it.
Its frusterating because I really want to learn this stuff. I have done
sorting before with Java.

Its just been a while. I am really frusterated though. I start trying
to figure it out and make ZERO progress. Its one thing if I was just
taking a while to solve the problem. I almost feel like I HAVE to look
at solutions. But if I look at solutions I don’t learn this stuff. But
if I just sit here and get no where, I don’t solve it either.

I am just lost and annoyed right now. I was doing great in this book up
until this point and the previous chapter. I’m not happy with this
right now and have no idea what to do.