PBK and edgeoftheatlas,
PBK is right, although moving the pseudo-code into Swift will be challenging until you get the right point of view about how recursion works. additionally, PBK's phrase "loop through each card in the hand" can be absorbed directly in the recursion.
i'd describe the recursion this way: for a hand of cards that is represented as say x = [3,2,53,4,53], with real cards being 1...52 and a joker as 53, it helps to think of finding the value of score or the value of the hand by breaking it out is "prefix" and "suffix" terms:
the value of [3,2,53,4,53]
is the value of [] and [3,2,53,4,53] joined
is the value of [3] and [2,53,4,53] joined
is the value of [3,2] and [53,4,53] joined
is the maximum value of [3,2,x] and [4,53] joined, for each possible x
is the value of [3,2,x,4] and [53] joined
is the maximum value of [3,2,x,4,y] and [] joined, for each possible y
is the "no jokers" value of [3,2,x,4,y]
when you look at it like this, i suggest a simple recursion, but it requires a little subtlety to get things started
-- a function that i call "noJokersValue" that returns the value of any hand that has NO jokers.
-- a function that i call "value" that returns the value of any hand (jokers or not, as many jokers as you like, for a hand of any length) by kicking off a recursive call to a function that figures out the value of a hand with prefix [] and suffix [3,2,53,4,53]
-- this recursive function when called then looks at the suffix.
(1) if the suffix is empty, evaluate the "no jokers" value of the prefix (it has no jokers)
(2) if the suffix is not empty, identify and remove the first card in the suffix
(2a) if the card is not a joker, add it to the prefix and recurse with the remaining suffix
(2b) if the card is a joker, loop over all possible substitutions for the card, adding each to the prefix and recursing with the remaining suffix. pick the biggest of all 52 of these.
so i have the following code for your consideration. it evaluates every hand to have a value of "1," but prints the hand so that you can see you're getting all possible combinations. the code also does not depend on the length of the array.
import Foundation
// assume cards are numbered 1...52 as you suggested
// use 53 to represent a Joker
let kJoker = 53
// this first function assigns a value to every hand that has no jokers.
// for this demonstration, we assume that the value of any hand will
// be non-negative.
func noJokersValue(hand: ArraySlice<Int>) -> Int {
print(hand)
return 1
}
// the value function assigns a value for any hand of cards. it's AN ENTRY POINT that
// calls a more general, recursive helper function to figure out the value of a
// hand that has been separated into a prefix and a suffix, e.g., separating [2,3,4,53,8]
// into prefix = [2,3,4] and suffix = [53,8], where the prefix has NO jokers, and the
// suffix MAY HAVE jokers. to get the process started, separate the hand into
// an empty prefix and suffix = the given hand, i.e., [] and [2,3,4,53,8].
func value(hand: [Int]) -> Int {
return value(prefix: [], suffix: hand[0...(hand.count)-1])
}
// this function does the real recursion work. when called, we know that the prefix has no jokers in it.
func value(prefix: ArraySlice<Int>, suffix: ArraySlice<Int>) -> Int {
// if there are no cards left to move from the suffix to the prefix, just return
// the ordinary value of the prefix, since it was the original hand and has no jokers
if suffix.isEmpty {
return noJokersValue(hand: prefix)
}
// otherwise, identify and remove the first card from the suffix
let nextCard = suffix.first!
let newSuffix = suffix.dropFirst()
// if the first card in the suffix IS NOT a joker, make a direct recursive call by
// removing the first card of the suffix and adding it to the prefix.
if nextCard != kJoker {
return value(prefix: prefix + [nextCard], suffix: newSuffix)
}
// but if this first card IS a joker, we recursively look through all
// possible substitutions of the joker with a legitimate card, adding
// each possible substitution to the prefix. we get the value
// after each substitution is made, and if it's bigger than what we
// had seen before, remember it
var maxValue = 0 // assumes all values will be non-negative
for card in 1...52 {
let nextValue = value(prefix: prefix + [card], suffix: newSuffix)
if nextValue > maxValue {
maxValue = nextValue
}
}
// return the largest value seen
return maxValue
}
let x = [3,2,kJoker,4,kJoker]
print(value(hand: x))
one syntactic point: some arguments are typed as ArraySlice<Int>. you can certainly pass such a function a real Array of Int, but when you start using .suffix(), you get an ArraySlice, which is a fancy way of saying: "it's not a real array, but a reference you can use" that works perfectly well later when using (some) functions like .isEmpty() or additional .suffix() calls. it removes the burden of, at every level, creating a new Array in memory and it will run faster with ArraySlice.
hope that helps,
DMG
