knapsack.swift

import Foundation
import UIKit

let CHAR_LIMIT = 75

extension String {
    func replace(string:String, replacement:String) -> String {
        return self.stringByReplacingOccurrencesOfString(string, withString: replacement, options: NSStringCompareOptions.LiteralSearch, range: nil)
    }
    
    func removeWhitespace() -> String {
        return self.replace(" ", replacement: "")
    }
}

var words = ["water canteen", "dried food", "first aid", "cell phone", "flashlight", "pocket knife", "thermos", "shovel", "flares", "ham radio", "salt", "sewing kit", "whistle"]

words = words.map { $0.removeWhitespace() }
words.joinWithSeparator("").characters.count
struct WordCell {
    var value = 0
    var words = ""
}

func + (left: WordCell, right: WordCell) -> WordCell {
    return WordCell(value: left.value + right.value, words: left.words + right.words)
}

var array: [[WordCell]] = [[WordCell]](count: words.count, repeatedValue:[WordCell](count: CHAR_LIMIT, repeatedValue:WordCell()));

for row in 0..<words.count {
    for column in 0..<CHAR_LIMIT {
        
        var current = WordCell(value: words.count - row, words: words[row])
        var currentWordSpace = current.words.characters.count
        
        var previousMax : WordCell = WordCell(value: 0, words: "")
        var currentPlusRemainingSpaceValue : WordCell = WordCell(value: 0, words: "")

        
        if row == 0 {
            if currentWordSpace < column {
                array[row][column] = WordCell(value: current.value, words: current.words)
            }
        } else { // if a subsequent row
            previousMax = array[row-1][column]
            if let fittingWordIndex = Optional.Some(column - currentWordSpace) where fittingWordIndex >= 0 {
                if let newValue = Optional.Some(array[row-1][fittingWordIndex] + current) where newValue.words.characters.count <= column {
                    currentPlusRemainingSpaceValue = newValue
                }
            }
            if previousMax.value > currentPlusRemainingSpaceValue.value {
                array[row][column] = previousMax
            } else {
                array[row][column] = currentPlusRemainingSpaceValue
            }
            
        }
        
    }
}



array[words.count - 1][CHAR_LIMIT - 1].value
array[words.count - 1][CHAR_LIMIT - 1].words
array[words.count - 1][CHAR_LIMIT - 1].words.characters.count