Coding challenge (on Ruby Garden)

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

As with 0001, this challenge comes with unit tests and an
unimplemented method. The basic idea of this challenge is: write a
method which takes two arguments: an array of items, and an
array-of-arrays of items, and determines whether or not a one-to-one
correspondence can be established, so that every item in the first
array can be found in one of the arrays in the array-of-arrays:

This would return true:

[1,2,3]
[ [1,11,111], [0,3,2], [2,4,6] ]

This would return false:

[1,2,3]
[ [1,11,111], [0,3,2], [4,6,8] ]

(because 2 and 3 aren’t allowed to correspond to the same array).

More details on the site – enjoy.

David

···


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

what about this

[1,2]
[ [1,2], [1,2] ]

does that comply?

···

On Mon, 2002-08-05 at 18:58, David Alan Black wrote:

This would return true:

[1,2,3]
[ [1,11,111], [0,3,2], [2,4,6] ]

This would return false:

[1,2,3]
[ [1,11,111], [0,3,2], [4,6,8] ]

(because 2 and 3 aren’t allowed to correspond to the same array).


~transami

Hi –

A unit test has been added, in case you haven’t downloaded it in the
past 5 minutes:

def test_true_3
items = [ 1,2 ]
rows = [ [2,1], [3,1] ]
assert(one_in_each(items,rows))
end

(This tests something fairly important, so I wanted to mention it
here.)

David

···


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Half the tests are successful without implementing the method! Do I get
part marks? :wink:

If you wanted to tighten this, there should be methods assert_true and
assert_false at your disposal.

Gavin

···

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

[…]

David Alan Black dblack@candle.superlink.net wrote in message news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution are:

bytes: 139
lines: 3
expressions: 1
assignments: 0

:wink:
Avi

“David Alan Black” dblack@candle.superlink.net wrote in message
news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

This would return true:

[1,2,3]
[ [1,11,111], [0,3,2], [2,4,6] ]

This is actually a special case of the assignment problem of operational
analysis.

You have M machines and M jobs. Each machine needs to be assigned a job. In
this case there is no preference to the quality of assignments, in the
classical case you assign a cost for each job on a given machine. In this
case the cost is either infinite of the machine cannot handle the job, or 0
if it can.

You can view the numbers in the first array as Job Id’s and the second array
as the ability of a machine to handle a given job.

You can represent a M x M matrix of the problem for the above example where
each row is a Job Id and each column is a machine.

For the given example:

[1,2,3]
[ [1,11,111], [0,3,2], [2,4,6] ]

you get

[[ 0, inf, inf], (Job 1 on each machine)
[ inf, 0, 0], (Job 2 on each machine)
[ inf, 0, inf]] (Job 3 on each machine)

Mikkel

David Alan Black dblack@candle.superlink.net writes:

As with 0001, this challenge comes with unit tests and an
unimplemented method. The basic idea of this challenge is: write a
method which takes two arguments: an array of items, and an
array-of-arrays of items, and determines whether or not a one-to-one
correspondence can be established, so that every item in the first
array can be found in one of the arrays in the array-of-arrays:

This would return true:

[1,2,3]
[ [1,11,111], [0,3,2], [2,4,6] ]

This would return false:

[1,2,3]
[ [1,11,111], [0,3,2], [4,6,8] ]

(because 2 and 3 aren’t allowed to correspond to the same array).

I just got here, but isn’t this just the bipartite matching problem?
The two partitions are the two arrays, and an edge AB from partition 1
to partition 2 exists iff A is an element of B.

Dan

···


http://www.dfan.org

Hi –

···

On Tue, 6 Aug 2002, Tom Sawyer wrote:

On Mon, 2002-08-05 at 18:58, David Alan Black wrote:

This would return true:

[1,2,3]
[ [1,11,111], [0,3,2], [2,4,6] ]

This would return false:

[1,2,3]
[ [1,11,111], [0,3,2], [4,6,8] ]

(because 2 and 3 aren’t allowed to correspond to the same array).

what about this

[1,2]
[ [1,2], [1,2] ]

does that comply?

Yes. As long as you can draw one line, so to speak, from each item
to an array, and as long as one and only one line touches each item
and each array, it’s OK.

David


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Hi,

def test_true_3
items = [ 1,2 ]
rows = [ [2,1], [3,1] ]
assert(one_in_each(items,rows))
end

(This tests something fairly important, so I wanted to mention it
here.)

Hmm, what about

items = [ 2,2 ]
rows = [ [1,2], [2,3] ]

?

Thanks,

Bill

very nice use of recursion! very very nice.

···

On Tue, 2002-08-06 at 01:20, Avi Bryant wrote:

David Alan Black dblack@candle.superlink.net wrote in message news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution are:

bytes: 139
lines: 3
expressions: 1
assignments: 0

:wink:
Avi


~transami

did you calculate those yourself or is there a way to get a readout of
these factors?

while we’re at it i decided to run a simple speed compare just to see
how they match up. they are all pretty close. these are the fastest
reported times i got for each solution after running each one many many
times:

Transami AviBryant BillKelly DavidNaseby DavidBlack
.005810 .005827 .005831 .006141 .009374

by the way, david’s is picking up a failure on:

def test_true_3
items = [ 1,2 ]
rows = [ [2,1], [3,1] ]
assert(one_in_each(items,rows))
end

but considering it was the first one and this test came later and it was
his idea! (i think), that’s okay :wink:

personally i don’t see why mine came out slightly ahead as it is pretty
brute force, calculating all possible mappings and checking for valid
ones. but hey! that’s cool :slight_smile:

~transami

···

On Tue, 2002-08-06 at 01:20, Avi Bryant wrote:

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution are:

bytes: 139
lines: 3
expressions: 1
assignments: 0


~transami

Hi –

···

On Tue, 6 Aug 2002, Gavin Sinclair wrote:

Half the tests are successful without implementing the method! Do I get
part marks? :wink:

If you wanted to tighten this, there should be methods assert_true and
assert_false at your disposal.

I guess the tests could be changed to “assert_equal(true, …)” etc.
But notice that you’re asked to code until “the tests pass and the
requirements are met” :slight_smile:

David


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Hi –

···

On Tue, 6 Aug 2002, Avi Bryant wrote:

David Alan Black dblack@candle.superlink.net wrote in message news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution are:

bytes: 139
lines: 3
expressions: 1
assignments: 0

The criteria are passing the tests, and the mysterious “meeting the
requirements” (which is a way of saying I doubt that the tests are
comprehensive enough). I think you get the honorary golf trophy,
though :slight_smile:

David


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Hi –

···

On Tue, 6 Aug 2002, Bill Kelly wrote:

Hi,

def test_true_3
items = [ 1,2 ]
rows = [ [2,1], [3,1] ]
assert(one_in_each(items,rows))
end

(This tests something fairly important, so I wanted to mention it
here.)

Hmm, what about

items = [ 2,2 ]
rows = [ [1,2], [2,3] ]

I’m not sure whether you mean as a unit test, or just whether it
should work. Well, to cover both: it should work, and you can add
it as a test to the wiki if you want.

David


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Is it legal to assume that the first array contains no duplicate items?

  • Brian D. Baker

David Alan Black wrote:

···

Yes. As long as you can draw one line, so to speak, from each item
to an array, and as long as one and only one line touches each item
and each array, it’s OK.

David

Hi –

···

On Tue, 6 Aug 2002, Tom Sawyer wrote:

On Tue, 2002-08-06 at 01:20, Avi Bryant wrote:

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution are:

bytes: 139
lines: 3
expressions: 1
assignments: 0

did you calculate those yourself or is there a way to get a readout of
these factors?

while we’re at it i decided to run a simple speed compare just to see
how they match up. they are all pretty close. these are the fastest
reported times i got for each solution after running each one many many
times:

Transami AviBryant BillKelly DavidNaseby DavidBlack
.005810 .005827 .005831 .006141 .009374

by the way, david’s is picking up a failure on:

def test_true_3
items = [ 1,2 ]
rows = [ [2,1], [3,1] ]
assert(one_in_each(items,rows))
end

but considering it was the first one and this test came later and it was
his idea! (i think), that’s okay :wink:

I respectfully decline the verdict of okay-ness :slight_smile: There’s definitely
something wrong with my algorithm… leaving aside the fact that the
whole thing is a lot longer than 139 bytes :slight_smile:

David


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Very impressive indeed. Avi, as you said it isn’t golf, but you could
combine the select and detect into a single detect combining the
conditions with &&, making your solution even shorter (both in
code size and - maybe not noticeable - execution speed).

Regards,
Pit

···

On 6 Aug 2002, at 16:41, Tom Sawyer wrote:

On Tue, 2002-08-06 at 01:20, Avi Bryant wrote:

David Alan Black dblack@candle.superlink.net wrote in message
news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution
are:

bytes: 139
lines: 3
expressions: 1
assignments: 0

:wink:
Avi

very nice use of recursion! very very nice.

David Alan Black wrote:

Hi –

David Alan Black dblack@candle.superlink.net wrote in message
news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net

Hello –

Coding Challenge 0002 (my numbering scheme :slight_smile: has been posted to
http://www.rubygarden.org/ruby?CodingChallenge0002.

So, what are the criteria for the challenge, apart from passing the
tests? This obviously isn’t golf, but the stats for my solution are:

bytes: 139
lines: 3
expressions: 1
assignments: 0

The criteria are passing the tests, and the mysterious “meeting the
requirements” (which is a way of saying I doubt that the tests are
comprehensive enough). I think you get the honorary golf trophy,
though :slight_smile:

David

I think Avi’s doesn’t quite meet the requirements. This should be true,
shouldn’t it?:

one_in_each([1,2,3],[[1,2],[1,2],[1,3]])

I have a 118 char solution (including the “def…end”!) which I think meets
all requirements. Anyone care to shorten it?

http://www.rubygarden.org/ruby?G00002

···

On Tue, 6 Aug 2002, Avi Bryant wrote:

Hi,

while we’re at it i decided to run a simple speed compare just to see
how they match up. they are all pretty close. these are the fastest
reported times i got for each solution after running each one many many
times:

Transami AviBryant BillKelly DavidNaseby DavidBlack
.005810 .005827 .005831 .006141 .009374

I thought it might be interesting to try some timing with a
larger dataset…

The solutions, surprisingly to me, polarized into two groups,
one of which was two orders of magnitude faster than the other group.
(However two solutions in the “fast” group failed to produce the
correct answer.)

(ruby 1.6.6 (2001-12-26) [i586-mswin32])

dblack (1000 iterations) 19.188 (0.019188 per iter) [failed test]

transami (1000 iterations) 20.469 (0.020469 per iter) [failed test]

dnaseby (1000 iterations) 61.609 (0.061609 per iter)

george (10 iterations) 40.638 (4.0638 per iter)

avi (10 iterations) 68.238 (6.8238 per iter)

bwk (10 iterations) 78.503 (7.8503 per iter)

I’m surprised at the polarity, and disparity between the fast
and slow groups here… but haven’t tried to understand it yet.

For what it’s worth, here’s the code used to generate the
dataset, and test. (I removed the “assert” when generating
the times above, and changed ‘niter’ manually for the two
groups…)

class Array # from http://www.rubygarden.org/ruby?OneLiners
def shuffle!
each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i], self[j]}
end
end

require 'test/unit’
class TestMe < Test::Unit::TestCase
def test_big
puts "\n------------------"
srand 314159
nitems = 60 # if increased to just 70, the slow solutions take “forever” !
big_items = [*1…nitems]
big_items.shuffle!
big_rows = []
big_items.each_with_index do |elm,idx|
big_rows[idx] = []
5.times {|i| big_rows[idx] << rand(1000) }
big_rows[idx] << elm
5.times {|i| big_rows[idx] << rand(1000) }
end
big_items.shuffle!

niter = 10
auths = %w(dblack dnaseby transami avi bwk george)
auths.each do |auth|
  eval <<-EOE
    print " #{auth} "
    t1 = Time.now
    niter.times { assert( #{auth}_one_in_each(big_items, big_rows) ) }
    t2 = Time.now
    
    puts "(\#{niter} iterations) \#{(t2-t1)} (\#{(t2-t1)/niter.to_f} per iter)"
  EOE
end

end
end

So, for instance, on my system, the code consistently generates
a big_items of:
[27, 54, 31, 3, 26, 24, 15, 53, 39, 37, 6, 43, 1, 13, 18, 30,
40, 14, 32, 22, 57, 17, 8, 48, 46, 36, 25, 34, 5, 7, 12, 38,
42, 2, 11, 10, 50, 28, 49, 47, 51, 44, 35, 19, 59, 23, 55, 60,
33, 52, 21, 56, 45, 9, 20, 58, 41, 16, 29, 4]

And a big_rows of:
[[727, 441, 342, 179, 535, 19, 888, 996, 397, 843, 573],
[626, 899, 823, 204, 951, 14, 498, 617, 104, 22 4, 260],
[51, 228, 818, 872, 165, 8, 657, 354, 370, 637, 492],
[653, 420, 583, 541, 292, 4, 773, 809, 721, 42, 72],
[13, 555, 976, 661, 984, 57, 703, 518, 551, 332, 910],
. . .
]

. . . Anyway, I’d be interested in anyone’s thoughts on what’s
going on here… (Hope I didn’t botch the tests somehow -
but I don’t think so!)

Thanks & Regards,

Bill

···

From: “Tom Sawyer” transami@transami.net

Hi –

Hmm, what about

items = [ 2,2 ]
rows = [ [1,2], [2,3] ]

I’m not sure whether you mean as a unit test, or just whether it
should work. Well, to cover both: it should work, and you can add
it as a test to the wiki if you want.

Ah, OK thanks. I’d noticed no existing unit tests had had duplicate
numbers/objects in the ‘items’ list… and an implementation I was
considering, I realized relied on that… :slight_smile:

… BTW also I’m noticing the objects in the unit tests are all
Enumerable. Can we depend on the objects in the arrays being
"sortable", or just testable for equality?

Thanks,

Bill

···

From: “David Alan Black” dblack@candle.superlink.net

On Tue, 6 Aug 2002, Bill Kelly wrote: