Forum: Ruby Maximum Sub-Array (#131)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-07-13 16:35
(Received via mailing list)
The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum.  For
example:

  array:              [-1, 2, 5, -1, 3, -2, 1]
  maximum sub-array:  [2, 5, -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.
F8fbc5df2432deac7557cf5e111439f2?d=identicon&s=25 Matt Greer (Guest)
on 2007-07-13 16:49
(Received via mailing list)
>
> by Harlan
>
> Given an array of integers, find the sub-array with maximum sum.  For
> example:
>
>         array:              [-1, 2, 5, -1, 3, -2, 1]
>         maximum sub-array:  [2, 5, -1, 3]


Just to confirm the problem. Wouldn't the maximum sub array be

[2, 5, 3] ?


Matt
F8fbc5df2432deac7557cf5e111439f2?d=identicon&s=25 Matt Greer (Guest)
on 2007-07-13 16:51
(Received via mailing list)
On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:
>
>
> Just to confirm the problem. Wouldn't the maximum sub array be
>
> [2, 5, 3] ?
>

Duh. Nevermind :) Maximum sub *array*. I get it. Carry on. Don't mind
me...

Matt
4d7bf65b4675b3e9575617929ab123f1?d=identicon&s=25 Paul Novak (Guest)
on 2007-07-13 17:58
(Received via mailing list)
On Jul 13, 10:29 am, Ruby Quiz <ja...@grayproductions.net> wrote:
>
>         array:              [-1, 2, 5, -1, 3, -2, 1]
>         maximum sub-array:  [2, 5, -1, 3]
>
> Extra Credit:
>
> Given a matrix of integers, find the rectangle with maximum sum.

Nice quiz.  One question.

For an array containing all negative integers, is the maximimum sub-
array an empty array or a single-value array containing the highest
value?

For example:

array:              [-1,-2,-3]

maximum sub-array:  []
                    or [-1] ?

Regards,

Paul.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-07-13 18:29
(Received via mailing list)
On Jul 13, 2007, at 10:42 AM, Paul Novak wrote:

>>
>>
>> Given a matrix of integers, find the rectangle with maximum sum.
>
> maximum sub-array:  []
>                     or [-1] ?

Let's say we are looking for a non-empty subarray.

James Edward Gray II
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-07-13 18:46
(Received via mailing list)
On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:
> On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:
> > > by Harlan
> > >
> > > Given an array of integers, find the sub-array with maximum sum.  For
> > > example:
> > >
> > >         array:              [-1, 2, 5, -1, 3, -2, 1]
> > >         maximum sub-array:  [2, 5, -1, 3]

What are the criteria for selecting from multiple possibilities? For
example:

[1,2,3,-7,6]

options:

[1,2,3]
[6]

Does it matter?
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2007-07-15 16:40
(Received via mailing list)
>
> Given a matrix of integers, find the rectangle with maximum sum.
>
>
#
# Here is my solution.
# If there are multiple sub arrays that equal max sum, it prints all of
them.

require 'enumerator'
arr, s = [1,5,3,-9,9], []
(1..arr.length).each{|q| arr.each_cons(q) {|x| s << x}}
big = s.max {|x,y| x.inject(0) {|a,b| a+b} <=> y.inject(0) {|c,d| c+d}}
p s.select {|r| r.inject(0) {|a,b| a+b} == big.inject(0) {|c,d| c+d}}

# Harry
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2007-07-15 16:42
(Received via mailing list)
On Fri, 13 Jul 2007 23:29:03 +0900, Ruby Quiz wrote:

>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps
> everyone on Ruby Talk follow the discussion.  Please reply to the
> original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
>
> by Harlan
>
> Given an array of integers, find the sub-array with maximum sum.  For
> example:
>
>   array:              [-1, 2, 5, -1, 3, -2, 1] maximum sub-array:
[2, 5,
>   -1, 3]
>
> Extra Credit:
>
> Given a matrix of integers, find the rectangle with maximum sum.

#!/usr/bin/env ruby

require 'matrix'

#strangely, none of these methods are in the facets gem.

module Enumerable
   def argmax
      curmax=nil
      curval=nil
      each do |x|
   t=yield x
   if not curmax or (curmax < t)
      curmax=t
      curval=x
   end
      end
      curval
   end

   def sum
      inject{|a,b|a+b}
   end

   def subarrays
      result=[]
      (0...length).each do |start|
   ((start + 1)..length).each do |finish|
      result << self[start...finish]
   end
      end
      result
   end
end

class Matrix
   include Enumerable
   def submatrices
      result=[]
      (0...row_size).each do |srow|
      (srow+1..row_size).each do |erow|
      (0...column_size).each do |scolumn|
      (scolumn+1..column_size).each do |ecolumn|
   result << minor(srow...erow,scolumn...ecolumn)
      end end end end
      result
   end
   def each
      (0...row_size).each do |row|
      (0...column_size).each do |column|
   yield self[row,column]
      end end
   end
end

ARRAY=[-1, 2, 5, -1, 3, -2, 1]
p ARRAY.subarrays.argmax{|x| x.sum}

MATRIX=Matrix[[1,-2,3],[5,2,-4],[5,-5,1]]
p MATRIX.submatrices.argmax{|x| x.sum}
Ca87a9b1fcd13c942dd76311fadcd571?d=identicon&s=25 Henrik Schmidt-Møller (Guest)
on 2007-07-15 16:48
(Received via mailing list)
Ruby Quiz wrote:
>
> Given a matrix of integers, find the rectangle with maximum sum.
>
>
*# The algorithm for max_subarray is a slightly adapted version of
# the linear solution presented in
# "Programming pearls: algorithm design techniques"
# by Jon Bentley, published in Communications of the ACM,
# volume 27, Issue 9 (september 1984). According to the article, it
# was designed by Jay Kadane (in less than a minute) in 1977.
# The algorithm for max_submatrix was inspired by some of the ideas in
the same
# article and large quantities of coffee.

# Running time: O(n)
def max_subarray(arr)

  if (max = arr.max) <= 0
    # if all the numbers in the array are less than or equal to zero,
    # then the maximum subarray is simply the array
    # consisting of the largest value
    max_idx = arr.index(max)
    return max, max_idx, max_idx
  end

  # starting index of the maximum subarray
  x1 = 0

  # ending index of the maximum subarray
  x2 = 0

  # the maximum value found so far
  running_max = 0

  # the maximum value of the array ending on the current
  # value (in the block below) or zero, if the maximum
  # array becomes negative by including the current value
  max_ending_here = 0

  # the start index of a possible maximum subarray
  start_idx = 0

  arr.each_with_index do |i, idx|
    start_idx = idx if max_ending_here == 0
    max_ending_here = [0, max_ending_here + i].max
    if max_ending_here > running_max
      running_max = max_ending_here
      x1 = start_idx
      x2 = idx
    end
  end
  return running_max, x1, x2
end

# Running time: O(m^2 * n)
def max_submatrix(matrix)

  # We already have a nice linear algorithm for solving
  # the problem in one dimension. What we want to do is
  # basically to reduce the problem to an array, and then
  # solve that problem using max_subarray.
  # The problem can be solved this way for any contiguous
  # number of rows by simply adding them together, thereby
  # "collapsing" them into one row, and then going from there.
  # Now, we want to do this efficiently, so we create
  # a cumulative matrix, by adding the elements of the columns
  # together. That way, we only need to look up one value
  # pr. column to get the sums of the columns in any sub matrix.
  c_matrix = matrix.inject([]) do |memo, arr|
    prev_arr = memo.last
    memo << (prev_arr == nil ? arr : Array.new(arr.size) { |i|
prev_arr[i] + arr[i] })
  end

  # the maximum value found so far
  running_max = 0

  # starting index of the horizontal maximum subarray
  x1 = 0

  # ending index of the horizontal maximum subarray
  x2 = 0

  # starting index of the vertical maximum subarray
  y1 = 0

  # ending index of the vertical maximum subarray
  y2 = 0

  c_matrix.each_with_index do |c_arr, vert_iter_end|
    0.upto(vert_iter_end) do |vert_iter_start|
      arr = c_arr
      if vert_iter_start != vert_iter_end
        arr = Array.new(c_arr.size) { |i| c_arr[i] -
c_matrix[vert_iter_start][i] }
      end
      c_max, hz_s, hz_e = max_subarray(arr)
      if c_max > running_max
        running_max = c_max
        x1, x2, y2 = hz_s, hz_e, vert_iter_end
        y1 = vert_iter_start == vert_iter_end ? 0 : vert_iter_start + 1
      end
    end
  end
  return running_max, x1, x2, y1, y2
end

array = [-1, 2, 5, -1, 3, -2, 1]
max, x1, x2 = max_subarray(array)
puts "Maximum subarray for #{array.inspect}:
#{array.values_at(x1..x2).inspect}, sum: #{max}"

matrix =
[
  [ 1,   5, -3,  4],
  [-8,   2,  9, 12],
  [ 6,   1, -2,  2],
  [-3, -15,  7, -6]
]

max, x1, x2, y1, y2 = max_submatrix(matrix)
max_matrix = matrix.values_at(y1..y2).collect { |arr|
arr.values_at(x1..x2) }
puts "Maximum submatrix for #{matrix.inspect}: #{max_matrix.inspect},
sum: #{max}"
*
B09f99b655b96fd4130aafd04531f6f1?d=identicon&s=25 Eric I. (Guest)
on 2007-07-15 16:50
(Received via mailing list)
I went for the all-in-one line solution (not including the method
definition boilerplate), with no consideration for the computational
or memory cost.  Here are two versons, the first does not require the
'enumerator' library, the second does and is slightly shorter as a
result.  Both will favor shorter solutions over longer solutions if
they have the same sum.

In both cases the code generates every possible sub-array and sorts
them by two factors: 1) sum of elements ascending, and 2) size of sub-
array descending.  Finally it chooses the solution at the end of this
sorted list.

In the first solution, it generates every sub-array by using all
possible combinations of starting and ending indices.

def max_sub_array(a)
  (0...a.size).inject([]) { |c, s| c + (s...a.size).map { |e|
a.slice(s..e) } }.sort_by { |b| [b.inject { |s, e| s + e }, -
b.size] }.last
end

In the second solution, it generates every sub-array by sequencing
through all possible sub-array lengths (1..size) and then calling
enum_cons.  If you're not familiar with enum_cons, it takes a size as
a parameter and returns an Enumerable for every sub-array of that size
(e.g., [1, 2, 3, 4].enum_cons(2) would provide an Enumerable that
would encode the sequence [1, 2], [2, 3], and [3, 4]).

def max_sub_array2(a)
  (1..a.size).inject([]) { |l, s| l + a.enum_cons(s).to_a }.sort_by { |
b| [b.inject { |s, e| s + e }, -b.size] }.last
end

Eric

====
Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com
245cfab887781bdf3f53178b794c42dc?d=identicon&s=25 Alexandru E. Ungur (Guest)
on 2007-07-15 17:32
(Received via mailing list)
Hi all,

Here's my solution. It has no other merits than showing me
that I really need to get back to studying algorythms more
in depth :-) as it's quite slow (needs about 2 minutes for
an 1000 elements array).

There are just two optimisations I came up with:
drop sub arrays starting or ending with negative numbers
and breaking out of loop when the sum of the positive numbers
left is smaller than the maximum we already have.

Cheers,
Alex
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2007-07-15 17:34
(Received via mailing list)
On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote:
>
> Extra Credit:
>
> Given a matrix of integers, find the rectangle with maximum sum.
>
>
#
# Here is my matrix solution.
# It does the Matrix extra credit.
# If there are multiple rectangles that equal max sum, it prints all of
them.
#
# Since the quiz did not specify how to input,
# I just hard coded a sample Matrix at the beginning.
#

require 'matrix'
mat =
Matrix[[77,-1,2,3,-4],[-7,8,-22,10,11],[3,15,16,17,-18],[4,22,-23,-24,-25]]
s = []
(0...mat.row_size).each do |a|
  (0...mat.column_size).each do |b|
    (1..mat.row_size).each do |x|
      (1..mat.column_size).each do |y|
      s << mat.minor(a,x,b,y)
      end
    end
  end
end

tot = s.uniq.map {|x| x.to_a}
big = tot.max{|x,y| x.flatten.inject(0) {|a,b| a+b} <=>
y.flatten.inject(0) {|c,d| c+d}}
subs = tot.select {|r| r.flatten.inject(0) {|a,b| a+b} ==
big.flatten.inject(0) {|c,d| c+d}}
puts "Original Matrix"
(0...mat.row_size).each do |x|
print mat.row(x).to_a.map{|m|
m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"
end
puts
puts "Solutions"
subs.each do |x|
puts
  x.each {|y| print y.map{|m|
m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"}
end

# Harry
F3b02532d4cb4855881935c002389213?d=identicon&s=25 Morton Goldberg (Guest)
on 2007-07-15 17:46
(Received via mailing list)
My solution to Quiz 131. It does a straight-forward O(N**2) search. I
did add a constraint: the algorithm should return a sub-array of
minimal length. This is because I strongly prefer [0] to [0, 0, 0, 0,
0, 0, 0].

My submission also shows my preference for code that is readable/
maintainable rather than golfed/obfuscated. (This is not intended as
a shot at those who enjoy code golf -- I'm just saying it's not for me.)

<code>
# Return the non-empty sub-array of minimal length that maximizes the
sum
# of its elements.
def max_sub_array(arry)
    max_sum = arry.inject { |sum, n| sum += n }
    min_length = arry.size
    result = arry
    (1...arry.size).each do |i|
       (i...arry.size).each do |j|
          sub = arry[i..j]
          sum = sub.inject { |sum, n| sum += n }
          next if sum < max_sum
          next if sum == max_sum && sub.size >= min_length
          max_sum, min_length, result = sum, sub.size, sub
       end
    end
    result
end
</code>

Regards, Morton
B63d3390f6285b1af0f1662687911a95?d=identicon&s=25 Jesse Merriman (Guest)
on 2007-07-15 17:47
(Received via mailing list)
I didn't try any golfing, but here are 3 attempts.

The first and second are straightforward approaches, their only
difference is
that the second prefers shorter arrays. Both are (n**2 + n) / 2.

The third is my clever solution. I think it should have lower complexity
(if
still a factor of n**2), despite having much more setup code, but I'm
not sure
what it is exactly. Here's a copy of the main descriptive comment I put
in the
code:

# Try to be clever. First, remove any leading or trailing non-positive
numbers,
# since including them can only lower the sum. Then, split the array up
into
# "islands" of same-sign numbers. Zeros will be including in the group
to their
# left. Map each island to its sum to get an array of alternating
+,-,+,-,...,+
# numbers. This is really the fundamental form of an instance of the
problem.
# It could be run though another max-subarray algorithm, but instead I
tried
# to take advantage of its structure by only looking at even-number
indices.
# Then just find the maximum subarray's indices, and map back to the
originali
# array.

An example in case thats not clear enough:

Start with:    [-1, 0, 2, 4, -1, 5, 0, 6, -2]
Trim ends:     [2, 4, -1, 5, 0, 6]
Sign switches: [0, 2, 3]
Islands:       [[2, 4], [-1], [5, 0, 6]]
new_arr:       [6, -1, 11]
Try each index pair: [0, 0], [0, 2], [2, 2]
Best is:       [0, 2]
Map back:      [2 4 -1 5 0 6]

Only 3 index pairs were tested, as opposed to (9**2 + 9)/ 2 = 45 for the
others.
Aedd89a10aba3a46576ea4f604146c65?d=identicon&s=25 Carl Porth (Guest)
on 2007-07-15 17:55
(Received via mailing list)
#!/usr/bin/env ruby

require "rubygems"
require "facets"
require "enumerable/each_unique_pair"
require "enumerable/sum"

class Array
  # all contiguous subarrays
  def sub_arrays
    [*0..self.size].to_enum(:each_unique_pair).map { |a,b|
self[a..b-1] }
  end
end

array = [-1, 2, 5, -1, 3, -2, 1]

# I find this easy on the eyes
array.sub_arrays.max { |a,b| a.sum <=> b.sum } # => [2, 5, -1, 3]

# but if you didn't want to recompute the sums you could do this
array.sub_arrays.map { |a| [a.sum,a] }.max.last # => [2, 5, -1, 3]
289cf19aa581c445915c072bf45c5e25?d=identicon&s=25 Todd Benson (Guest)
on 2007-07-15 17:57
(Received via mailing list)
Just like many others, I went for brute force with some readability.
Golf solution at the bottom.


class Array
  def sum
    inject {|sum, elem| sum + elem}
  end
  def sub_arrays
    subs = []
    0.upto(size-1) { |i| i.upto(size-1) { |j| subs << self[i..j] } }
    subs
  end
end

foo = Array.new(42) { rand(42) - 21 }  # build array; choice of
numbers here is arbitrary
p foo << "\n"  # show the array
# now show maximum sub-array ...
p foo.sub_arrays.inject([foo.max]) { |max, elem| elem.sum > max.sum ?
elem : max }


Golf solution (3 lines, 120 chars not including array initialization).
 I'm sure it could be shorter, though :(

a = Array.new(42){rand(42)-21}

v=[]
0.upto(b=a.size-1){|i|i.upto(b){|j|v<<a[i..j]}}
p v.inject([a.max]){|z,m|z.inject{|s,i|s+i}>m.inject{|s,i|s+i}?z:m}


Todd
0a5391b2f3c8aea510ebed66b29998f3?d=identicon&s=25 Sammy Larbi (Guest)
on 2007-07-15 19:48
(Received via mailing list)
Morton Goldberg wrote, On 7/15/2007 10:44 AM:
> <code>
>
Doesn't this basically make it order n cubed?
A81805e545b4996b36c7d011a5249b2c?d=identicon&s=25 Justin Ethier (Guest)
on 2007-07-15 23:05
(Received via mailing list)
No extra credit on this one, but my solution handles a regular list of
numbers just fine.
First, I created an object to define a range of numbers:

# Object defining a sub-array of integer values
# The sub-array contains a start and end index
# defining a region of the master array
class SubArray
  def initialize
    @start = 0
    @end = 0
    @sum = 0
  end

  # Set boundaries of the sub-array
  def set_bounds(list_start, list_end)
    @start, @end = list_start, list_end
  end

  # Provide get/set accessors
  attr_reader :start, :end, :sum
  attr_writer :sum
end


Then I created a class to find the sub-array with the maximum sum.
Basically
it performs a single pass of the array, updating the maximum sub-array
each
time the current sum exceeds the current maximum sum:

class MaxSubArray
  # Finds the sub-array with the largest sum
  # Input: a list of integers
  def find(list)
    max = SubArray.new
    cur = SubArray.new

    for i in 0...list.size
      cur.sum = cur.sum + list[i]

      if (cur.sum > max.sum)
        max.sum = cur.sum
        cur.set_bounds(cur.start, i)
        max.set_bounds(cur.start, i)
      elsif (cur.sum < 0)
        # If sum goes negative, this region cannot have the max sum
        cur.sum = 0
        cur.set_bounds(i + 1, i + 1)
      end
    end

    list.slice(max.start, max.end - max.start + 1)
  end
end


And finally, here are some tests:

$:.unshift File.join(File.dirname(__FILE__), "..")
require 'test/unit'
require 'max_sub_array.rb'

class TestMaxSubArray < Test::Unit::TestCase
  def setup
    @ma = MaxSubArray.new
  end

  def test_max_sub_array
    assert_equal([2, 5, -1, 3], @ma.find([-1, 2, 5, -1, 3, -2, 1]))
    assert_equal([10], @ma.find([-1, 2, 5, -1, 3, -2, -12, 10]))
    assert_equal(@ma.find([-25, 81, -14, 43, -23, 86, -65, 48]), [81,
-14,
43, -23, 86])
    assert_equal([9, 11, 23, -5, 15, 18, 6, -18, 21, -4,
                           -17, -19, -10, -9, 19, 17, 24, 10, 21, -23,
-25,
                           21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18,
-22,
                           -6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6,
10,
4,
                           2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23],
                 @ma.find([-16, -8, 9, 11, 23, -5, 15, 18, 6, -18, 21,
-4,
                           -17, -19, -10, -9, 19, 17, 24, 10, 21, -23,
-25,
                           21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18,
-22,
                           -6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6,
10,
4,
                           2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23,
-23,
16,
                           -19, -10, 12, -17, -9, 6, -8, -23, 16, -17,
-10,
24,
                           -1, -6, -24, -5, 16, -11, -7, -8, 12, -21,
-23,
-8,
                           -8, 4, 7, 6, -22, -8, -19, -7, 23, 4, 9, -19,
-19, 0, -15]))
    assert_equal([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9, 30,
31,
16, 44, 20, 10, 55, 28,
                  -18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17,
38,
-5, -28, 45, -38, 4,
                  4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32,
-22, 8, 37, 57, 13, 17,
                  -17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24,
34,
-10, -26, -27, 12, 5, -2,
                  4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56,
10,
-35, -29, 40, -1, 30, 45, 36],
                 @ma.find([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26,
9,
30, 31, 16, 44, 20, 10, 55, 28,
                  -18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17,
38,
-5, -28, 45, -38, 4,
                  4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32,
-22, 8, 37, 57, 13, 17,
                  -17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24,
34,
-10, -26, -27, 12, 5, -2,
                  4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56,
10,
-35, -29, 40, -1, 30, 45, 36, -38, 30, -28]))
  end
end

Thanks,

Justin
Ae82cad40a0caca9c932d45c7a9eb3cd?d=identicon&s=25 Michael Glaesemann (Guest)
on 2007-07-15 23:22
(Received via mailing list)
Here's a solution which iterates over the array just once. Looks like
I came up with a variant of the algorithm presented by Henrik Schmidt-
Møller, though I'm storing the local max sub array rather than just
its delimiting indices. I'm not happy with the calls to slice
(especially as they require calculating the size of the array), but
I'm pleased that I came up with a solution using recursion.

class Array
   def max_sub_array
     self.max_sub_arrayr[0]
   end

   def max_sub_arrayr
     ary = self.clone
     sub_ary = Array.new.push(ary.shift)
     sum = sub_ary[0]
     max_sub_ary = sub_ary.dup
     max_sum = sum
     done = false
     ary.each_with_index do |n,i|
       if sum > 0
         if sum + n > 0
           sum += n
           sub_ary.push(n)
         else
           sub_ary, sum = ary.slice(i+1..(ary.size-1)).max_sub_arrayr
           done = true
         end
       elsif sum <= n
         sub_ary, sum = ary.slice(i..(ary.size-1)).max_sub_arrayr
         done = true
       end
       if sum > max_sum
         max_sum = sum
         max_sub_ary = sub_ary.dup
         break if done
       end
     end
     return max_sub_ary, max_sum
   end
end

Michael Glaesemann
grzm seespotcode net
81d609425e306219d54d793a0ad98bce?d=identicon&s=25 Matthew Moss (Guest)
on 2007-07-16 02:07
(Received via mailing list)
I see I was not the only one to borrow inspiration from Programming
Pearls. This is O(N) code... some few examples included for testing:

def max_subarray_last_index(arr)
   a = b = x = 0
   arr.each_with_index do |e, i|
      b = [b + e, 0].max
      unless a > b
         a, x = b, i
      end
   end
   return x
end

def max_subarray(arr)
   i = arr.size - max_subarray_last_index(arr.reverse) - 1
   j = max_subarray_last_index(arr)
   return arr[i..j]
end


p max_subarray( [-1, 2, 5, -1, 3, -2, 1] )
p max_subarray( [31, -41, 59, 26, -53, 58, 97, -93, -23, 84] )
p max_subarray( [] )
p max_subarray( [-10] )
p max_subarray( [10] )
p max_subarray( [-5, 5] )
p max_subarray( [5, -5] )
F3b02532d4cb4855881935c002389213?d=identicon&s=25 Morton Goldberg (Guest)
on 2007-07-16 03:09
(Received via mailing list)
On Jul 15, 2007, at 1:47 PM, Sammy Larbi wrote:

>>
>>          sub = arry[i..j]
>>    result
>> end
>> </code>

Yes, the inject introduces another factor of N. I missed that.

Regards, Morton
B63d3390f6285b1af0f1662687911a95?d=identicon&s=25 Jesse Merriman (Guest)
on 2007-07-16 03:20
(Received via mailing list)
On Sunday 15 July 2007 17:17, Michael Glaesemann wrote:
> Here's a solution which iterates over the array just once. Looks like
> I came up with a variant of the algorithm presented by Henrik Schmidt-
> Møller, though I'm storing the local max sub array rather than just
> its delimiting indices. I'm not happy with the calls to slice
> (especially as they require calculating the size of the array), but
> I'm pleased that I came up with a solution using recursion.
>
> <snip>

Not to be the downer who points out everyone's problems, but here's a
bug:

irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19,
-36, -6,
                      -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, 37,
39,
                      -22, 11, -44, -40, -37, -26]
irb(main):009:0> arr.max_sub_array
=> [37, 39, 10]

That sequence does not appear in arr.
Ae82cad40a0caca9c932d45c7a9eb3cd?d=identicon&s=25 Michael Glaesemann (Guest)
on 2007-07-16 05:00
(Received via mailing list)
On Jul 15, 2007, at 20:19 , Jesse Merriman wrote:

> Not to be the downer who points out everyone's problems, but here's
> a bug:

No problem at all! Thanks for taking a look at my work :)

> irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9,
> -19, -36, -6,
>                       -20, -4, -23, -25, 48, -22, 22, 5, -21, -33,
> 37, 39,
>                       -22, 11, -44, -40, -37, -26]
> irb(main):009:0> arr.max_sub_array
> => [37, 39, 10]

This should be a bit more pleasing :)

irb(main):002:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19,
-36, -6,
                            -20, -4, -23, -25, 48, -22, 22, 5, -21,
-33, 37, 39,
                            -22, 11, -44, -40, -37, -26]
irb(main):005:0> arr.max_sub_array
=> [46, -8, 43]

Updated code follows below signature:

Michael Glaesemann
grzm seespotcode net

class Array
   def max_sub_array
     return [] if self.empty?
     self.max_sub_arrayr[0]
   end

   def max_sub_arrayr
     ary = self.clone
     sub_ary = Array.new.push(ary.shift)
     sum = sub_ary[0]
     max_sub_ary = sub_ary.dup
     max_sum = sum
     done = false
     ary.each_with_index do |n,i|
       if sum > 0
         if sum + n > 0
           sum += n
           sub_ary.push(n)
         else
           sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr
           done = true
         end
       elsif sum <= n
         sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr
         done = true
       end
       if sum > max_sum
         max_sum = sum
         max_sub_ary = sub_ary.dup
       end
       break if done
     end
     return max_sub_ary, max_sum
   end
end
Ef3aa7f7e577ea8cd620462724ddf73b?d=identicon&s=25 Rob Biedenharn (Guest)
on 2007-07-16 06:27
(Received via mailing list)
This was a nice diversion on Friday morning at the start of my kids'
championship swim meet.  I had to work Saturday and Sunday so the
last two test cases had to wait until now (yes, I should be sleeping!).

-Rob

Rob Biedenharn    http://agileconsultingllc.com
Rob@AgileConsultingLLC.com


class Array
   # Given an Array of numbers, return the contiguous sub-array
having the
   # maximum sum of its elements.  Longer sub-arrays are preferred.
   #
   #--
   # (or members of any Ring having operations '+' (binary,
associative and
   # commutative) and '-' (unary, giving the inverse with respect to
'+'))
   #++
   def sub_max identity=0
     return self if size < 2     # nothing to sum!

     ms = Array.new(size) { Array.new(size) {identity} }
     mx, range = self[0], 0..0
     0.upto(size-1) do |e|
       e.downto(0) do |s|
         current = ms[s][e] = if s == e
                                self[s]
                              else
                                ms[s][e-1] + ms[s+1][e] + (- ms[s+1]
[e-1])
                              end
         if current > mx || current == mx && (e - s + 1) > (range.end
- range.begin + 1)
           mx = current
           range = s..e
         end
       end
     end
     self[range]
   end
end

if __FILE__ == $0
   require 'test/unit'

   class Array
     def put2d
       print '[ '
       each do |row|
         row.put1d
         print ",\n  "
       end
       puts ']'
     end

     def put1d
       print '[ '
       each do |item|
         print("%3d, " % item)
       end
       print ']'
     end
   end

   class SubMaxTest < Test::Unit::TestCase
     def test_quiz_example
       input = [-1, 2, 5, -1, 3, -2, 1]
       expected = [2, 5, -1, 3]

       assert_equal expected, input.sub_max
     end

     def test_empty
       assert_equal [], [].sub_max
     end
     def test_single
       assert_equal [ 0], [ 0].sub_max
       assert_equal [-1], [-1].sub_max
       assert_equal [ 1], [ 1].sub_max
     end
     def test_all_positive
       input = [ 1, 2, 4, 8 ]
       assert_equal input, input.sub_max
     end
     def test_all_non_negative
       input = [ 1, 2, 0, 4 ]
       assert_equal input, input.sub_max
     end
     def test_all_negative
       input = [ -1, -2, -3, -9 ]
       assert_equal [-1], input.sub_max
       input = [ -2, -1, -3, -9 ]
       assert_equal [-1], input.sub_max, 'need to test diagonal'
     end
     def test_prefer_length_earlier
       input = [ -1, 0, 1, -2, -9 ]
       assert_equal [0, 1], input.sub_max, "if actual is [1], need to
add a length test on range"
     end
     def test_prefer_length_later
       input = [ -1, 1, 0, -2, -9 ]
       assert_equal [1, 0], input.sub_max, "if actual is [1], need to
add a length test on range"
     end

     def test_prefer_length_multiple_options
       input = [ 1, 2, 3, -6, 6 ]
       # options
       # [6]
       # [1,2,3]
       expected = [ 1, 2, 3, -6, 6 ]
       assert_equal expected, input.sub_max, "if [6] or [1,2,3] you
can do better"
     end
   end
end
__END__
94cc3e46cfc5bc361e409e2e884ecfa4?d=identicon&s=25 Drew Olson (dfg59)
on 2007-07-16 17:30
Here's my solution to the maximum sub-array problem. I'm sure my
algorithm is not optimal, but it's readable and concise:

# file: max_sub_array.rb
# author: Drew Olson

class Array

  alias :orig_to_s :to_s

  # sum the integer values of array contents
  def int_sum
    self.inject(0){|sum,i| sum+i.to_i}
  end

  # find the maximum sub array in an array
  def max_sub_array
    (0...self.size).inject([self.first]) do |max_sub,i|
      (i...self.size).each do |j|
        if max_sub.int_sum < self[i..j].int_sum
          max_sub = self[i..j]
        end
      end
      max_sub
    end
  end

  # pretty printing for array
  def to_s
    self.inject("[") do |str,i|
      str + "#{i}, "
    end[0...-2] + "]"
  end
end

# test example
if __FILE__ == $0
  my_arr = [-1, 2, 5, -1, 3, -2, 1]
  puts "array: #{my_arr}"
  puts "maximum sub-array: #{my_arr.max_sub_array}"
end
4425958c134c5e70f76d5e1a5b76ce87?d=identicon&s=25 James Koppel (Guest)
on 2007-07-17 01:03
(Received via mailing list)
Solution #1: Array is bound to arr

  sub_arrs = []
arr.each_index{|i| (i...arr.length).each{|i2| sub_arrs << arr[i..i2]}}
p sub_arrs.sort_by{|arr| arr.inject(0){|s,n|s+n}}.last

  Solution #2: Array is bound to a

  p
(b=(0...(l=a.size)).to_a).zip([b]*l).map{|(i,s)|s.map{|j|a[i,j]}}.sort_by{|a|a.map!{|a|[a.inject(0){|s,n|s+n},a]}.sort![-1][0]}[-1][-1][-1]
9dec3df8319c613f6f4f14a27da0fdb4?d=identicon&s=25 Kyle Schmitt (Guest)
on 2007-07-17 16:04
(Received via mailing list)
A late late entry (I was busy yesterday).
Yes it does an exhaustive search, but for even moderate sized sets,
it's feasibly fast enough.


class Array
  def sum()
    s=0
    each{|i| s+=i}
    s
  end
end

array=[-6,-5,-4,-3,-2,-1,0,1,2,3,-5,4,5,6]
maxIndex = array.length-1
sizeByRange = {}
0.upto(maxIndex) do
  |start|
  start.upto(maxIndex) do
    |endI|
    sizeByRange.store(array[start..endI].sum,start..endI)
    #puts "subarray #{start} to #{endI} sums to
#{array[start..endI].sum}"
  end
end

puts "Minimum array is [#{array[sizeByRange.min[1]].join(',')}]"
puts "Maximum array is [#{array[sizeByRange.max[1]].join(',')}]"
81d609425e306219d54d793a0ad98bce?d=identicon&s=25 Matthew Moss (Guest)
on 2007-07-17 18:49
(Received via mailing list)
Just a note on my "solution" I sent in earlier... Well, it's not
entirely correct... I've been shown at least one case that fails.
It's probably not that far off, but unfortunately I don't have time
this week to correct it... Just so no summaries go using it.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-07-17 19:03
(Received via mailing list)
On Jul 17, 2007, at 11:12 AM, Matthew Moss wrote:

> Just a note on my "solution" I sent in earlier... Well, it's not
> entirely correct... I've been shown at least one case that fails.
> It's probably not that far off, but unfortunately I don't have time
> this week to correct it... Just so no summaries go using it.

Next week's quiz:  debug Matthew's solution.  ;)

James Edward Gray II
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2007-07-18 05:22
(Received via mailing list)
On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote:
> Extra Credit:
>
> Given a matrix of integers, find the rectangle with maximum sum.
>
>
#
# This is roughly the same matrix solution I posted before.
# Sorry for the double post. Two lines in the middle of the program were
# too long and got wrapped in the post.
# I made the lines shorter and tried again.
#
# Here is my matrix solution.
# It does the Matrix extra credit.
# If there are multiple rectangles that equal max sum, it prints all of
them.
#
# Since the quiz did not specify how to input,
# I just hard coded a sample Matrix at the beginning.


require 'matrix'
mat=Matrix[[7,-1,2,3,-4],[-7,8,-22,10,11],[3,15,16,17,-18],[4,22,-23,-24,-25]]
s = []
(0...mat.row_size).each do |a|
  (0...mat.column_size).each do |b|
    (1..mat.row_size).each do |x|
      (1..mat.column_size).each do |y|
      s << mat.minor(a,x,b,y)
      end
    end
  end
end

tot = s.uniq.map {|x| x.to_a}
bg=tot.max{|x,y|x.flatten.inject(0){|a,b|a+b}<=>y.flatten.inject(0){|c,d|c+d}}
sb=tot.select{|r|r.flatten.inject(0){|a,b|a+b}==bg.flatten.inject(0){|c,d|c+d}}
puts "Original Matrix"
(0...mat.row_size).each do |x|
print mat.row(x).to_a.map{|m|
m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"
end
puts
puts "Solutions"
sb.each do |x|
puts
  x.each {|y| print y.map{|m|
m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"}
end

# Harry
E60b2dc57668b5662ce3f07781e41710?d=identicon&s=25 Matthew Rudy Jacobs (matthewrudy)
on 2007-07-18 11:06
this is my first entry
(only found this place last week)

so it's late,
but I like it.

I deal with left-subarrays, and right-subarrays
(i decided that intuitively a max sub array is a max left of a max
right,
but have not the time to prove this)
I also assume that the empty array [] is always a member.

also, my max_left_of_right and max_right_of_left methods will return
multiple copies of the empty array if that is indeed the smallest.

I did initially uniq the result,
but decided against it in the end
(who says that the empty array is a unique sub array -- probably me)

class Array

  # solution 1
  def max_subs
    max_found, max_instances = 0, [[]]  # the empty sub array will
always return 0 sum
    self.left_subs.each do |l_sub|
      next if l_sub.last.nil? || l_sub.last < 0   # if
      l_sub.right_subs.each do |sub|
        next if sub.first.nil? || sub.first < 0
        if (sub_sum = sub.sum) > max_found
          max_found, max_instances = sub_sum, [sub]
        elsif sub_sum == max_found
          max_instances << sub
        end
      end
    end
    return max_instances
  end

  # i hypothesise that each max sub array is actually;
  # a max left sub of a max right sub, and the other way round
  # but i dont have time to prove it

  # solutions 2 and 3
  def max_left_of_right
      max_right_subs.inject([]){|rtn, max_r| rtn + max_r.max_left_subs}
  end

  def max_right_of_left
      max_left_subs.inject([]){|rtn, max_l| rtn + max_l.max_right_subs}
  end


  # sub methods

  def left_subs
    if (l_sub = self.dup) && l_sub.pop
      return (l_sub.left_subs << self.dup)
    else
      return [self]
  end
  end

  def right_subs
    if (r_sub = self.dup) && r_sub.shift
      return (r_sub.right_subs << self.dup)
    else
      return [self]
  end
  end

  def sum
    self.inject(0){|sum, element| sum+element}
  end

  def max_left_subs
    max_of_subs(:left_subs)
  end

  def max_right_subs
    max_of_subs(:right_subs)
  end

  def max_of_subs(method)
    max_found, max_instances = 0, [[]] # we expect to have an empty sub
    self.send(method).each do |sub|
      if (sub_sum = sub.sum) > max_found
        max_found, max_instances = sub_sum, [sub]
      elsif sub_sum == max_found
        max_instances << sub
      end
    end
    return max_instances
  end
end
81d609425e306219d54d793a0ad98bce?d=identicon&s=25 Matthew Moss (Guest)
on 2007-07-18 16:19
(Received via mailing list)
Eh.... I got some better quizzes in mind than debugging my lousy
code...  I just have to write them up.  (This thing called "day job"
keeps getting in the way...)
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-07-18 16:30
(Received via mailing list)
On Jul 18, 2007, at 9:17 AM, Matthew Moss wrote:

> Eh.... I got some better quizzes in mind than debugging my lousy
> code...  I just have to write them up.  (This thing called "day job"
> keeps getting in the way...)

I always enjoy your quizzes Matthew.  Looking forward to it.

James Edward Gray II
B1b1d33e0655e841d4fd8467359c58d0?d=identicon&s=25 Yossef Mendelssohn (Guest)
on 2007-07-19 02:13
(Received via mailing list)
Oh, these quizzes.  I need to either find more time to play with them
or stop telling myself I don't have the time.  I did this in Perl for
a job interview a while ago and happened to still have it handy, so
all I did was translate it (somewhat) into Ruby.

-------------------------------------------------------------------------------
class Array
  def largest_sum_sequence
    # initialize with a sequence of the first number
    largest = {
      :sum   => first,
      :start => 0,
      :end   => 0
    }

    (0 .. length-1).each do |start_i|
      sum = 0
      start_num = self[start_i]

      # don't bother with a sequence that starts with a negative number
      # but what if all the numbers are negative?
      next if largest[:sum] > start_num and start_num < 0

      (start_i .. length-1).each do |end_i|
        end_num = self[end_i]
        sum += end_num

        # if this sequence is the largest so far
        if sum > largest[:sum]
          largest[:sum]   = sum
          largest[:start] = start_i
          largest[:end]   = end_i
        end
      end
    end

    puts "Largest sum: #{largest[:sum]}"
    puts "The sequence starts at element #{largest[:start]} and goes to
element #{largest[:end]}"
    puts "The sequence is #{self[largest[:start] ..
largest[:end]].join(' ')}"
  end
end

numbers = ARGV.collect { |arg|  arg.to_i }

numbers.largest_sum_sequence
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-09-25 23:01
(Received via mailing list)
On Jul 13, 2007, at 11:10 AM, Kyle Schmitt wrote:

> Am I missing something, or is this one of the easiest quizzes that's
> been put forward?

It's a pretty easy problem.  I almost rejected it for that reason.

I was just sure I could do it with a one-liner, but when my own
solution didn't make it down to that I accepted the problem.  I'm
sure someone will get it down there, but I didn't so it required a
touch more thought than I expected.

We've had some pretty easy problems.  FizzBuzz was pretty close to
this level.

I'm fine with that thought.  Ruby Quiz is for all levels.

James Edward Gray II
69498abbf47d4967f8640317a58377dd?d=identicon&s=25 Aureliano Calvo (Guest)
on 2007-09-25 23:02
(Received via mailing list)
> Am I missing something, or is this one of the easiest quizzes that's
> been put forward?

Well, you're missing the fizzfuzz quiz.
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2007-09-25 23:03
(Received via mailing list)
On Fri, 13 Jul 2007 19:47:11 +0200, anansi wrote:

>
> but why is  [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum?
> wouldn't be [2,5,3,1] sum=11 the right solution?

Because the subarrays in the quiz problem must be contiguous.

The answer to your proposed version is
ARRAY=[-1, 2, 5, -1, 3, -2, 1]
ARRAY.select{|x| x>=0}

--Ken
0a5391b2f3c8aea510ebed66b29998f3?d=identicon&s=25 Sammy Larbi (Guest)
on 2007-09-25 23:03
(Received via mailing list)
Kyle Schmitt wrote, On 7/13/2007 11:10 AM:
> Am I missing something, or is this one of the easiest quizzes that's
> been put forward?
>
> --Kyle
>
>
>

Well, you could put a maximum time complexity constraint on it and the
solutions aren't as obvious (unless you've seen it before)
1685f91cc5853eb465ca50aa68b91421?d=identicon&s=25 anansi (Guest)
on 2007-09-25 23:04
(Received via mailing list)
could someone explain this please? I really don't understand this quiz?

Given an array of integers, find the sub-array with maximum sum.  For
 > example:
 >
 >         array:              [-1, 2, 5, -1, 3, -2, 1]
 >         maximum sub-array:  [2, 5, -1, 3]

I know what an array is :) I know what integers are :) I know what a sum
is :)

but why is  [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum?
wouldn't be [2,5,3,1] sum=11 the right solution?

--
greets

                     one must still have chaos in oneself to be able to
give birth to a dancing star
F3b02532d4cb4855881935c002389213?d=identicon&s=25 Morton Goldberg (Guest)
on 2007-09-25 23:04
(Received via mailing list)
On Jul 13, 2007, at 2:29 PM, Ari Brown wrote:

> Being a nub at life, liberty, and ruby, what is the best way to
> search it? Would it be to go and sum up the elements in every
> possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because
> that seems like it would get very CPU consuming with larger arrays.

An exhaustive search would have execution time on the order of N**2,
where N is the length of the array. That's not great but its not
horrible either -- that is, not nearly so bad as a search that takes
exponential (e**N) time.

Regards, Morton
F8fbc5df2432deac7557cf5e111439f2?d=identicon&s=25 Matt Greer (Guest)
on 2007-09-25 23:05
(Received via mailing list)
On 7/13/07, anansi <kazaam@oleco.net> wrote:
> is :)
>
> but why is  [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum?
> wouldn't be [2,5,3,1] sum=11 the right solution?


A sub-array is a contiguous list within the overall array.

For [a,b,c], the sub-arrays are

[a], [b], [c], [a,b], [b,c] and of course [a,b,c], but [a,c] is NOT a
sub-array because the elements are not contiguous within the overall
array.

I'm looking forward to tackling this quiz this evening, what a rocking
Friday night it will be! :)

Matt
9dec3df8319c613f6f4f14a27da0fdb4?d=identicon&s=25 Kyle Schmitt (Guest)
on 2007-09-25 23:05
(Received via mailing list)
Humm.  OK well fizbuzz could be done as a one liner.....
a reasonably readable version of this one looks like 10 lines to me.....

yea just tried to shorten it.  My version of this one can only
condense down to 2 lines, and I don't wanna spend the time to do more
on it, considering the whole, at work thing :)

--Kyle
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-09-25 23:06
(Received via mailing list)
On Jul 13, 2007, at 10:56 AM, David Chelimsky wrote:

>
> Does it matter?
I think either selection would be acceptable.  I would probably favor
the shorter one, but I don't think it matters.

James Edward Gray II
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2007-09-25 23:07
(Received via mailing list)
On 7/13/07, Sammy Larbi <sam@powersource.com> wrote:
> solutions aren't as obvious (unless you've seen it before)
Thank you I felt completely stupid in desperately searching for a
O(n*log n) solution...
Robert
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-09-25 23:07
(Received via mailing list)
On Jul 13, 2007, at 1:29 PM, Ari Brown wrote:

> Being a nub at life, liberty, and ruby, what is the best way to
> search it? Would it be to go and sum up the elements in every
> possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because
> that seems like it would get very CPU consuming with larger arrays.

Let's have this discussion after the no-spoiler period, please.

James Edward Gray II
425cab08658a06567879717de154552c?d=identicon&s=25 Ari Brown (Guest)
on 2007-09-25 23:08
(Received via mailing list)
<snip>

Being a nub at life, liberty, and ruby, what is the best way to
search it? Would it be to go and sum up the elements in every
possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because that
seems like it would get very CPU consuming with larger arrays.

aRi
--------------------------------------------|
If you're not living on the edge,
then you're just wasting space.
9dec3df8319c613f6f4f14a27da0fdb4?d=identicon&s=25 Kyle Schmitt (Guest)
on 2007-09-25 23:08
(Received via mailing list)
Am I missing something, or is this one of the easiest quizzes that's
been put forward?

--Kyle
813f535246722b7bf02aacc9ce818de8?d=identicon&s=25 Bob Showalter (Guest)
on 2007-09-25 23:09
(Received via mailing list)
On 7/13/07, Kyle Schmitt <kyleaschmitt@gmail.com> wrote:
> yea just tried to shorten it.  My version of this one can only
> condense down to 2 lines, and I don't wanna spend the time to do more
> on it, considering the whole, at work thing :)

I've golfed mine down to a 108-char method body for an exhaustive
search...
5d38ab152e1e3e219512a9859fcd93af?d=identicon&s=25 David Chelimsky (Guest)
on 2007-09-25 23:10
(Received via mailing list)
On 7/13/07, David Chelimsky <dchelimsky@gmail.com> wrote:
> What are the criteria for selecting from multiple possibilities? For example:
>
> [1,2,3,-7,6]

Or this:

[1,2,3,-6,6]

options

[1,2,3]
[1,2,3,-6,6]
[6]
This topic is locked and can not be replied to.