combination sums of several arrays

D

David Vincelli

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

This demonstrates some of the code I wrote:

pl =3D Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree, creating
unique branches that would add up to the results when I applied some
recursive algorithm to it. But I'm curious to know how other people
might do this? (I'm especially curious to see if anyone has some
solution that does not require building a tree and recursing..).

Thanks,
 
S

swille

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

This demonstrates some of the code I wrote:

pl =3D Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree, creating
unique branches that would add up to the results when I applied some
recursive algorithm to it. But I'm curious to know how other people
might do this? (I'm especially curious to see if anyone has some
solution that does not require building a tree and recursing..).

Thanks,

Maybe I'm not understanding what exactly you want, but I think I'd
dump the [1, 10] thing and just count it as [1]. Then maybe something
like:

sum =3D pl.hand.inject { |sum, n| sum + n }
if pl.hand.include?(1)
if sum + 10 <=3D 21
sum +=3D 10
end
end

Or did I miss something?
 
M

Mike Wilson

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

This demonstrates some of the code I wrote:

pl =3D Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree, creating
unique branches that would add up to the results when I applied some
recursive algorithm to it. But I'm curious to know how other people
might do this? (I'm especially curious to see if anyone has some
solution that does not require building a tree and recursing..).

Thanks,

Maybe I'm not understanding what exactly you want, but I think I'd
dump the [1, 10] thing and just count it as [1]. Then maybe something
like:

sum =3D pl.hand.inject { |sum, n| sum + n }
if pl.hand.include?(1)
if sum + 10 <=3D 21
sum +=3D 10
end
end

Or did I miss something?

Oh, yes, I did. Multiple Aces...
 
S

swille

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

This demonstrates some of the code I wrote:

pl =3D Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree, creating
unique branches that would add up to the results when I applied some
recursive algorithm to it. But I'm curious to know how other people
might do this? (I'm especially curious to see if anyone has some
solution that does not require building a tree and recursing..).

Thanks,

Actually, wouldn't you need to evaluate at each hand? So, you'd start
with 2 cards, at which point Aces are always 11. After that it's
something like:

if pl.card.value =3D=3D 1
if sum + 11 <=3D 21
pl.card.value =3D 11
end
end

sum +=3D pl.card.value
 
J

James Edward Gray II

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

Actually, you can do it a little easier. Just count them all as 11
and if you're over 21, subtract 10 until you're out of aces, or you
are under. Here's some sample code from my own version:

class Card
# ...

def soften?
if @face == "A" and @value == 11
@value = 1
true
else
false
end
end

# ...
end

# ...

class Player
# ...

def total
count = @cards.inject(0) { |sum, card| sum + card.value }

while count > 21 and @cards.any? { |card| card.soften? }
count -= 10
end

count
end

# ...
end

# ...

__END__

Hope that helps.

James Edward Gray II
 
B

Bob Hutchison

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

This demonstrates some of the code I wrote:

pl = Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree, creating
unique branches that would add up to the results when I applied some
recursive algorithm to it. But I'm curious to know how other people
might do this? (I'm especially curious to see if anyone has some
solution that does not require building a tree and recursing..).

Well, two aces counting as 11 total to 22 which is bigger than 21 and
so you can never have more than one ace count as 11. I'd just keep an
extra bit of information: do we have an ace? If we do then we may add
10 (just once) to the total when the total <= 11 (and where the total
counts each ace as 1). This won't give you *all* totals just the best
legal one.
 
D

David Vincelli

Actually, you can do it a little easier. Just count them all as 11
and if you're over 21, subtract 10 until you're out of aces, or you
are under. Here's some sample code from my own version:

Your code is very interesting, thanks :)
 
D

David Vincelli

Well, two aces counting as 11 total to 22 which is bigger than 21 and
so you can never have more than one ace count as 11. I'd just keep an
extra bit of information: do we have an ace? If we do then we may add
10 (just once) to the total when the total <=3D 11 (and where the total
counts each ace as 1). This won't give you *all* totals just the best
legal one.

This would work too, thanks. I did have similar ideas but for some
reason I thought it might be incorrect. Sometimes hearing it from
someone else just settles it.
 
D

Dominik Bathon

I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer to
21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to determine
all combinations of the players cards).

This demonstrates some of the code I wrote:

pl =3D Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree, creating
unique branches that would add up to the results when I applied some
recursive algorithm to it. But I'm curious to know how other people
might do this? (I'm especially curious to see if anyone has some
solution that does not require building a tree and recursing..).

You probably won't need this because of the other replies, but here is a =
=20
solution to the combination sums problem (without building a tree ;-):

def combination_sums(arr)
arr.inject([0]) { |sums, cur|
cur.map { |a|
sums.map { |b| b+a }
}.flatten
}.uniq
end

p combination_sums([[1,11],[5],[10]])
p combination_sums([[1,3,5],[2,3,6]])

output:
[16, 26]
[3, 5, 7, 4, 6, 8, 9, 11]

Dominik
 
R

Ryan Leavengood

You probably won't need this because of the other replies, but here is a
solution to the combination sums problem (without building a tree ;-):

I don't know about the OP, but I'm glad you wrote this because I was
having trouble figuring out how to do it myself.

Ryan
 
C

C Erler

------=_Part_16959_21837113.1130069424888
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here's an efficient solution (plus it handles hands of two and three aces
properly) no one has mentioned: keep a running sum of all card values
(counting aces as ones) and a running sum of the number of aces. Then, use =
:

def sum cur_sum, ace_count
if cur_sum > 12 or ace_count =3D=3D 0
cur_sum
elsif cur_sum > 3 or ace_count =3D=3D 1
cur_sum + 9
else
cur_sum + 18
end
end

------=_Part_16959_21837113.1130069424888--
 
C

C Erler

------=_Part_16971_1176681.1130069779152
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Somehow my first rendition of all code posted to ruby-talk has bugs that I
notice right after I post. Here is the correct version (the idea appeared
already, I now see) :

def sum cur_sum, ace_count
if cur_sum > 11 or ace_count =3D=3D 0
cur_sum
else
cur_sum + 10
end
end

------=_Part_16971_1176681.1130069779152--
 
R

Robert Klemme

Dominik Bathon said:
I'm writing a little BlackJack program for fun and I'm at the point
where I have to decide which point value to assign to a hand. As you
know, an Ace may be worth 1 or 11 in this game - whatever is closer
to 21 without going over.

Considering this, I know I have to come up with an algorithm that
first determines what the different point values may be (the extreme
case may be that a player got all four aces, now I'd have to
determine all combinations of the players cards).

This demonstrates some of the code I wrote:

pl = Player.new
pl.hand.each { |card| p pl.card.value }

might produce this output:
[1, 11]
[5]
[10]

For the above example, so what I'm looking for is a method that will
calculate all possible point totals. For this example I'd get the
results [16, 26]

I'm thinking I might do this by first building a binary tree,
creating unique branches that would add up to the results when I
applied some recursive algorithm to it. But I'm curious to know how
other people might do this? (I'm especially curious to see if anyone
has some solution that does not require building a tree and
recursing..).

You probably won't need this because of the other replies, but here
is a solution to the combination sums problem (without building a
tree ;-):

def combination_sums(arr)
arr.inject([0]) { |sums, cur|
cur.map { |a|
sums.map { |b| b+a }
}.flatten
}.uniq
end

p combination_sums([[1,11],[5],[10]])
p combination_sums([[1,3,5],[2,3,6]])

output:
[16, 26]
[3, 5, 7, 4, 6, 8, 9, 11]

Dominik

Here's a variant that reduces the number of created arrays:

sums = values.inject([0]) do |sums,values|
values.inject([]) do |su,v|
sums.inject(su) {|su,s| su << (s+v)}
end
end
sums.uniq!
values = [[1,11],[2],[3,4]] => [[1, 11], [2], [3, 4]]
sums = values.inject([0]) do |sums,values|
?> values.inject([]) do |su,v|
?> sums.inject(su) {|su,s| su << (s+v)}
end
end => [6, 16, 7, 17]
sums.uniq!
=> nil

Kind regards

robert
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,905
Latest member
Kristy_Poole

Latest Threads

Top