StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I don't know if this is a "more Ruby way". At least at is a more "higher-order" way, FWIW.</p> <pre><code># first line is number of inputs (Don't need it), thus drop the first line # read inputs as ints h = ARGF.drop(1).reduce(Hash.new(0)) {|h, n| h.tap {|h| h[n.to_i] += 1 }} </code></pre> <p>Not much to say here. Instead of simply looping over <code>ARGF</code> and setting the hash keys, we use <code>reduce</code> to let it do the work for us. And we use a hash with a default value of <code>0</code> instead of manually checking the keys for existence.</p> <p>We use <code>Enumerable#drop</code> to simply drop the first line.</p> <p><code>ARGF</code> is a really cool feature stolen (like most of the scripting features) from Perl: if you simply call the script as <code>script.rb</code> without arguments, then <code>ARGF</code> is the standard input. If, however, you call your script like <code>script.rb a.txt b.txt</code>, then Ruby will interpret all the arguments as filenames, open all the files for reading and <code>ARGF</code> will be the concatenation of their contents. This allows you to very quickly write scripts that can take their input either via standard input or a file.</p> <pre><code># find smallest mode modes = h.group_by(&:last).sort.last.last.map(&:first).sort puts "Mode is: #{modes.first}" </code></pre> <p>Ruby doesn't have an explicit key-value-pair type, instead most looping operations on hashes use two-element arrays. This allows us to refer to the key and the value with <code>Array#first</code> and <code>Array#last</code>.</p> <p>In this particular case, we are using <code>Enumerable#group_by</code> to group the hash into different buckets, and the grouping criterion we use is the <code>last</code> method, i.e. the value which in our hash is the frequency. In other words, we group by frequency.</p> <p>If we now sort the resulting hash, the very last element is the one with the highest frequency (i.e. the mode). We take the last element (the value of the key-value-pair) of that, and then the last element of that, which is an array of key-value-pairs (<code>number => frequency</code>) of which we extract the keys (the numbers) and sort them.</p> <p>[Note: simply print out the results at every intermediate stage and it's much easier to understand. Just replace the <code>modes = ...</code> line above with something like this:</p> <pre><code>p modes = h.tap(&method(:p)). group_by(&:last).tap(&method(:p)). sort.tap(&method(:p)). last.tap(&method(:p)). last.tap(&method(:p)). map(&:first).tap(&method(:p)). sort </code></pre> <p>]</p> <p><code>modes</code> is now a sorted array with all the numbers which have that particular frequency. If we take the first element, we have the smallest mode.</p> <pre><code># mode unique? puts "Mode is #{unless modes.size == 1 then '*not* ' end}unique." </code></pre> <p>And if the size of the array is not <code>1</code>, then the mode was not unique.</p> <pre><code># print number of singleton odds, # odd elems repeated odd number times in desc order # even singletons in desc order odds, evens = h.select {|_,f|f==1}.map(&:first).sort.reverse.partition(&:odd?) </code></pre> <p>It looks like there is a lot going on here, but it's actually straightforward. You start reading after the equals sign and simply read left to right.</p> <ol> <li>we select all items in the hash whose value (i.e. frequency) is <code>1</code>. IOW, we select all the singletons.</li> <li>we map all the resulting key-value-pairs just to their first element, i.e. the number – IOW we throw away the frequency.</li> <li>we sort the list</li> <li>and then reverse it (for larger lists we should sort in reverse to begin with, since this is quite a waste of CPU cycles and memory)</li> <li>lastly, we partition the array into two arrays, one containing all the odd numbers and the other all the even numbers</li> <li><p>now we finally look to the left side of the equals sign: <code>Enumerable#partition</code> returns a two-element array containing the two arrays with the partitioned elements and we use Ruby's destructuring assignment to assign the two arrays to two variables</p> <p>puts "Number of elements with an odd value that appear only once: #{odds.size}"</p></li> </ol> <p>Now that we have a list of odd singletons, their number is simply the size of the list.</p> <pre><code>puts "Elements repeated an odd number of times: #{ h.select {|_, f| f.odd?}.map(&:first).sort.reverse.join(', ') }" </code></pre> <p>This is very similar to the above: select all numbers with an odd frequency, map out the keys (i.e. numbers), sort, reverse and then convert them to a string by joining them together with a comma and space in between.</p> <pre><code>puts "Elements with an even value that appear exactly once: #{evens.join(', ')}" </code></pre> <p>Again, now that we have a list of even singletons, printing them is just a matter of joining the list elements with commas.</p> <pre><code># print fib numbers in the hash </code></pre> <p>I didn't feel like refactoring this algorithm to be more efficient and specifically to memoize. I just made some small adjustments.</p> <pre><code>class Integer </code></pre> <p>There was nothing in the algorithm that depended on the number being a certain size, so I pulled the method up into the <code>Integer</code> class.</p> <pre><code> def fib? </code></pre> <p>And I dropped the <code>is_</code> prefix. The fact that this is a boolean method is already explicit in the question mark.</p> <pre><code> l, h = 0, 1 while h <= self return true if h == self l, h = h, l+h end end end puts "Fibonacci numbers: #{h.keys.sort.select(&:fib?).join(', ')}" </code></pre> <p>This probably doesn't need much explanation: take the keys, sort them, select all Fibonacci numbers and join them together with commas.</p> <p>Here is an idea for how to refactor this algorithm. There is <a href="http://Neeraj.Name/2008/05/10/how-hash-works-with-block-in-ruby.html" rel="nofollow noreferrer">a very interesting implementation of Fibonacci</a> using a <code>Hash</code> with default values for memoizing:</p> <pre><code>fibs = {0 => 0, 1 => 1}.tap do |fibs| fibs.default_proc = ->(fibs, n) { fibs[n] = fibs[n-1] + fibs[n-2] } end </code></pre> <p>It would look a little like this:</p> <pre><code>class Integer @@fibs = {0 => 0, 1 => 1}.tap do |fibs| fibs.default_proc = ->(fibs, n) { fibs[n] = fibs[n-1] + fibs[n-2] } end def fib? i = 0 until @@fibs[i += 1] > self break true if @@fibs[i] == self end end end puts "Fibonacci numbers: #{h.keys.sort.select(&:fib?).join(', ')}" </code></pre> <p>If anyone can think of an elegant way to get rid of the <code>i = 0</code>, <code>i += 1</code> and the whole <code>until</code> loop, I'd appreciate it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload