Note: Extra one-liners for discussion
Some students wanted one-liners they could discuss. Here you go. I’m not going to comment on them; have fun.
Here are a few one-liners we didn’t use for various reasons:
1. This one is easy and a classic: A solution is probably given in the Pickaxe:
Given an array of Strings named ‘a’, return an integer representing the length of the longest string.
Example input: %w[fee fi foo fum i smell the blood of an english man]
Expected result: 7
2. This one is less interesting, because there is new syntax in Ruby 1.9.1 to allow for constructing Hashes in a manner similar to the problem:
A developer is tired of the syntax for initializing Hashes. He is so lazy that the
following two strategies represent too much typing:
h = Hash["a" => "1", "b" => "2"]
h = Hash["a", "1", "b", "2"]
He would like to write
h = Hash["a:1 b:2"]
This would define a Hash with keys being the Strings “a” and “b” with corresponding
values being the Strings “1″ and “2″.
Example input: “a:1 b:2″
Expected result: {”a”=>”1″, “b”=>”2″}
3. You are given an Array of Strings named a representing the first names of people going to a party. Return an Array with two elements; the first element is a new Array with the party-goers whose names begin with a letter between “A” and “M” inclusive; the second element is a new Array with the party-goers whose names begin with a letter between “N” and “Z” inclusive.
Example input: ["John", "Amy", "Jim", "Naomi", "Aaron", "Zack"]
Expected result: [["John", "Amy", "Jim", "Aaron"], ["Naomi", "Zack"]]
4. This one is annoying to test, given our data-driven model for expected results, so we don’t use it anymore:
Given a String a that is a sequence of characters, e.g.,
“abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789″
(which you can generate with:
a = ((’a’..’z').collect + (’A’..’Z').collect + (’0′..’9′).collect).join
), provide a one-liner that will create a password of a random sequence of characters, selected from a, of a given length n.
Example input: ‘abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789′
A suitable result: ‘j4mUndZuFO’
5. Here’s one we don’t use because there are too many implementations on the web:
Write a ROT13 translator — see http://en.wikipedia.org/wiki/Rot13
Hint: A “brute-force” approach using a translation table is acceptable.
Sample input:
a = “How can you tell an extrovert from an introvert at NSA? Va gur ryringbef, gur rkgebireg ybbxf ng gur BGURE thl’f fubrf.”
Generates:
“Ubj pna lbh gryy na rkgebireg sebz na vagebireg ng AFN? In the elevators, the extrovert looks at the OTHER guy’s shoes.”
6. (9) Inspired by http://acm.uva.es/problemset/v4/457.html
You have a row of Petri dishes. For example, say there are 5 of them. The Petri dishes are numbered from 0. Each Petri dish has a number of organisms, between 0 and 3. We are going to follow the growth of the population of the organisms over time. The population of the next generation is looked up in a special Array called dna. For example, dna might be the following:
dna = [ 0, 1, 2, 0, 1, 3, 3, 2, 3, 0 ]
After each unit of time, we calculate the sum k of the population of each dish and its neighbors. For example, say the row looks like this:
Dishes at time 0: 0 3 2 0 0
In this example, Petri dish 1 has population 3. At the end of the first unit of time, we would calculate k for dish 1 as the sum of the population of dish 0 (=0), dish 1 (=3), and dish 2 (=2), or 0 + 3 + 2, or 5. We do this for each dishes. If the dish is on either end, then the neighbor on that end is considered to have population 0. So the values of k at the end of the first unit of time would be:
k (time 0): 3 5 5 2 0
Now with these values of k, we look up the next population in our dna Array. So the result after one unit of time is:
Dishes at time 1: 0 0 2 0 0
Now we do it again:
k (time 1): 0 2 2 2 0
Dishes at time 1: 0 2 2 2 0
*** NOTE: To show the user each generation, you may print out the Array for that generation. I.e., just use “p” — in other words, you don’t have to create a big Array of Arrays (if for some reason you find it easier to implement by creating an Array of Arrays, go ahead.)
Here are your inputs:
dishes is an Array where each element gives the population for that dish.
dna is an array where each element represents the growth rule for k.
n is the number of generations to show data (including time = 0).
Example:
dishes = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
dna = [0, 1, 2, 0, 1, 3, 3, 2, 3, 0]
n = 10
Output:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 3, 3, 1, 2, 0, 2, 1, 3, 3, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 2, 3, 0, 1, 0, 3, 2, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Hints:
(a) To make this easier, you may define a method sum on the Array class that will provide the sum of all elements for any given Array. E.g.,
class Array; def sum; inject( nil ) { |sum,x| sum ? sum+x : x }; end; end
(b) You may find it useful to learn about Array#slice (especially in conjunction with the first hint)
(c) To make this easier, you may create a new array based on dishes with a 0 at the start and at the end. E.g.,
dishes = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Also, you might learn what negative indices do with Arrays.
(d) To create output that looks like the web page cited above, you can take a dishes array and do something like this:
.join.tr(’0123′,’ .xW’)
E.g.,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].join.tr(’0123′,’ .xW’)
Which if applied to the Arrays above produces:
" . " " ... " " .x x. " " . . . " " ......... " " .x x. " " . x x . " " ...xxx xxx... " " .x .WW.x x.WW. x. " " . .xxW . Wxx. . "
(e) If you like, you may require ‘enumerator’ and use .enum_cons
Enjoy!
For problem 1:
# Takes the highest value of length stored and returned from result
def prob(a)
a.inject {|result, e| result = e.length > result.to_i ? e.length : result }
end
I have gotten really comfortable with inject because one of the issues I ran across often was the ability to create a container of the type I want returned. I would like to see ways for removing inject in instances like this. I guess another way to do it is,
# Changes array to lengths then takes the highest
def prob(a)
a.map { |e| e.length }.max
end
Which I dreamt of while trying to think of discussion points. We can see that the second way is much shorter and produces the same result.
lesson_to_self: Compete with self and to push the status quo and see how SHORT you can make these one-liners.
Referece: Ruby Docs
For problem 2, a little more interesting. I would like to find the library reference mentioned above. Here it goes,
a.split(" ").inject({}) {|result, e| result.merge(e.split(":")[0] => e.split(":")[1])}
@Jeff Ancel
Folks -- You might *discuss* one-liner solutions here, but I don't think it's advisable to post completely working solutions.
@john
Oops. Sorry.
@Jeff Ancel
Well, since you did post a solution... let's take a look at it. For this one:
a.inject {|result, e| result = e.length > result.to_i ? e.length : result }
the value of the block is automatically assigned to the accumulator parameter 'result' each time the block is executed. So you can rewrite it as:
a.inject { |result, e| e.length > result.to_i ? e.length : result }
That would be more idiomatic. I think it would be even more idiomatic to provide a starting value for inject, and to remove the to_i coercion on result:
a.inject(0) { |result, e| e.length > result ? e.length : result }
@Jeff: if by 'library reference' you mean documentation of the new Ruby 1.9 syntax for hash literals, see page 43 of Programming Ruby (PDF version). If you don't have the PDF, this is the 'Symbols' section of Chapter 2.
Also, pages 70-71 of the PDF, which is the 'Hashes' section of Chapter 4.
@Ron Newman
I was talking about the class library for Ruby on the web.
@Keith
I actually like the inject(0) to rid the .to_i reference. When I was trying that I ran into issues with this feature, once I get back to it, I will try to find out what my problem was. It seemed to evaluate result as a string.
@Jeff: I don't understand what you mean by "class library for Ruby on the web" .
I posted a comment with a link, however, I don't see that comment appearing here. Not sure if that is a caching feature or what, but it won't let me repost per it's "identical" to other post. The docs I am referring to are the ones on ruby-doc.org. Sorry if the lingo is off. I am a Java guy (and I believe it is the same in Ruby). I am used to calling docs/library Class Library or API. Maybe I am wrong but I hope this explanation helps a little.
@Jeff Ancel
You mean like these: http://ruby-doc.org/core-1.9/index.html
Those are the "RDocs" for the Core Ruby APIs. (RDoc was largely modeled on JavaDoc.)
@john
That's the link it wouldn't allow me to post.
Thanks.
(1) Another way to solve this is to first sort the array (Enumerable#sort_by or #sort) and then just return the length of the first or last element depending on your sort.
But I do like Jeff's map+max solution as I think it is really easy to comprehend. I timed each of these 4 methods using Time.now over a range and I saw:
So I guess Map+Max wins for ease and efficiency!
@Donnie Demuth
The best way to do some basic analysis of how long different approaches will take is to use the Benchmark class in the standard library:
http://www.ruby-doc.org/stdlib/libdoc/benchmark/rdoc/index.html
It is extraordinarily easy to use.
#5 is considerably more challenging, but still possible, if you add this rule: You may not use the String#tr method.
@Keith
Thanks! That actually helps out a lot and will be invaluable to a number of us. I'm certain there will be others who will like to learn about it (Benchmark) as the topic of "efficiency" came up time and time again during the sections. Get well soon.
Oops, I got confused with names when I commented on this yesterday (I wish there was an edit button)... So I played around with the Benchmark class today and got similar but much more cleaner results. You can even use ri and type "ri Benchmark" to find out more about it. Basically, you just pass in a block/function that you want to evaluate and it handles everything for you.
Problem 2 may use split, inject, and merge functions.
I have a solution to #2 which uses split, inject, lambda, and the splat (*) operator.