James Gray
7/15/2007 5:58:00 PM
Begin forwarded message:
> From: Florian Gross <flgr@ccan.de>
> Date: July 13, 2007 7:35:13 PM CDT
> To: james@grayproductions.net
> Subject: Re: Ruby quiz solution
> Oh, and the current Ruby Quiz looks great! I'm looking forward to
> the solutions already. The simplest ones always have the broadest
> range of solutions which makes them especially interesting.
>
> Just so I don't forget to submit my solution in time, here it is:
>
>
> class Array
> def each_cont_sub_array()
> return enum_for(__method__) unless block_given?
>
> 0.upto(size - 1) do |start|
> 1.upto(size - start) do |length|
> yield self[start, length]
> end
> end
> end
> end
>
> [-1, 2, 5, -1, 3, -2, 1].each_cont_sub_array.max_by { |ary|
> ary.inject(&:+) } # => [2, 5, -1, 3]
>
>
> I decided to make it depend on 1.9, because I was too lazy to
> include max_by and Symbol#to_proc.
> Once that dependency was there I could shamelessly start to use
> more features of 1.9.
> (I think that the first line of each_contiguous_sub_array might
> eventually become an idiom. :))
>
> Other than that, it is pretty boring and straightforward.
>
> Oh, and the whole thing gets more interesting when you start
> replacing :+ with :* and max_by with min_by... :)
>
> [-1, 2, 5, -1, 3, -2, 1].each_cont_sub_array.min_by { |ary|
> ary.inject(&:+) } # => [-2]
> [-1, 2, 5, -1, 3, -2, 1].each_cont_sub_array.max_by { |ary|
> ary.inject(&:*) } # => [2, 5, -1, 3, -2]
> [-1, 2, 5, -1, 3, -2, 1].each_cont_sub_array.min_by { |ary|
> ary.inject(&:*) } # => [-1, 2, 5, -1, 3, -2]
>
> We can also make it find the shortest solution by changing the
> max_by to max_by { |ary| [ary.inject(&:+), -ary.size] } and the
> longest solution by changing it to max_by { |ary| [ary.inject(&:+),
> +ary.size] }.
>
>
> Here's my extension for matrix support:
>
>
> class Array
> def transpose_zip(&block)
> first, rest = self[0], self[1 .. -1]
> first.zip(*rest, &block)
> end
> end
>
> require 'matrix'
>
> class Matrix
> def each_cont_sub_matrix(&block)
> return enum_for(__method__) unless block_given?
>
> to_a.each_cont_sub_array do |rows|
> rows.map { |row| row.each_cont_sub_array }.transpose_zip(&block)
> end
> end
> end
>
> Matrix[
> [-1, +2, +5],
> [-4, +5, -2],
> [+8, +4, -3]
> ].each_cont_sub_matrix.max_by { |ary| ary.flatten.inject(&:+) } #
> => [[-1, 2], [-4, 5], [8, 4]]
>
>
> Notes:
>
> A straight-forward solution without any clever algorithms. Just
> building on top of the code we already have for Array.
>
> I define a custom transpose_zip() for two reasons:
> a) transpose() can't yield its values (always constructs an array).
> b) transpose() won't work when the inner elements are enumerators.
> The code can be made shorter, but more inefficient, by using the
> built-in transpose.
>
> Matrix#each_cont_sub_matrix yields nested arrays. Could be fixed to
> yield Matrix objects, but then we need a to_a call before the flatten.
>
> Matrix#each_cont_sub_matrix needs to call to_a. This would be nicer
> if there was a RandomAccess mix-in where we could centrally define
> each_cont_sub_array() for both Array and Matrix.
>
> The method names are a bit long. The '_cont' could probably be
> dropped.
>
> Kind regards,
> Florian Gross