swift - 查找根项的递归模式

Question

我正在尝试找出一种方法来查找根项及其相关性。

就我而言，我有一个游戏的“可制裁剪品”列表。

例如:

• 木原木
• 木板
• 木墙

<小时/>

所有这些项目都有所谓的 parent 和 child 。这些是包含 itemID 的简单元组数组(我可以将其转换为实际的 Item 对象和 amount 值。

例如:

typealias ParentTuple = (id: Int, amount: Float)
typealias ChildrenTuple = (id: Int, amount: Float)

var woodLog = Item(id: 1,
                   name: "Wood Log",
                   parents: [],
                   children: [ChildrenTuple(id: 2, amount: 2)]
                   )

var woodPlank = Item(id: 2,
                     name: "Wood Plank",
                     parents: [ParentTuple(id: 1, amount: 0.5)],
                     children: [ChildrenTuple(id: 3, amount: 4)]
                     )

var woodStick = Item(id: 3,
                     name: "Wood Stick",
                     parents: [ParentTuple(id: 2, amount: 0.25)],
                     children: []
                     )

正如您所看到的，一根原木可以制造 2 block 木板，而您需要 0.5 根原木才能制造 1 block 木板。 (当然，稍后我会将每个值向上取整到下一个完整整数)。

因此，按照 1 个木原木的逻辑，您应该能够制作 8 个木棍。

• 1x 原木 ->
• 2x 木板 ->
• 8x 木棍

现在我需要知道的是，如果我想制作 32 根木棍，我需要多少根原木？

我设法递归地返回项目的所有rootItems(没有任何父项的项目)的列表，如下所示:

func rootItems() -> [ParentTuple] {
    guard self.isCraftable else { return [ParentTuple(self.id, amount: 1)] }

    var rootItems = [ParentTuple]()

    for (_, parentTuple) in self.parentIDs.enumerated() {
        guard let parentItem = Item.item(forID: parentTuple.id) else {
            assertionFailure()
            return [ParentTuple(self.id, amount: 1)]
        }
        if parentItem.isRootItem {
            rootItems.append(ParentTuple(id: parentTuple.id, amount: parentTuple.amount))
        } else {
            rootItems.append(contentsOf: parentItem.rootItems())
        }
    }

    return rootItems
}

这很好用。我只是纠结于如何让金额发挥作用。理论上，对于每个递归调用，我只需将当前的 parentTuple.amount 与下一个相乘(在我们的示例中:0.25 * 0.5 = 0.125 --> 1/8 Wood Log for 1 Wood分支)

我的模型可能不适合该任务吗？我错过了什么吗？

Answer 1

我会以不同的方式处理这个问题。这是伪代码来说明

class Item {
    id : int?
    name : String?
    tier : Int?
    material : String?
}

然后，当您定义 WoodLog、WoodPlank 和 WoodStick 时，您可以分配 ID、tier 和 material 然后您就可以从 tier 级别处理计算。添加 Material 还可以让您以最少的工作量获得更多相同 Material 和层的元素，并轻松与其他元素进行比较，以确保可以用它们拆卸或创造。

func calcDismantleEfficiency(_ itemToMake: Item, _ itemToDismantle: Item) -> Int? {
    // array to get result based on tiers
    // the indices of tierArray are the itemToDismantle.tier
    // the subindices are the itemToMake.tier
    let tierArray = [[0,1,2,8,32...],
                     [0,0,1,4,16]...]
    if itemToDismantle.material == itemToMake.material {
         return tierArray[itemToDismantle.tier][itemToMake.tier] as! Int
    } else { return nil }

}

因此，如果您调用 calcDismantleEfficiency(WoodStick,WoodLog) ，它将返回 8。

func calculateCost(_ itemToMake: Item, _ itemToDismantle: Item, _ countToMake: Int ) -> Int? {
    if let efficiency = calcDismantleEfficiency(iteToMake, itemToDismantle) {
        if countToMake % efficiency == 0 {
            return countToMake / efficiency
        } else { return (countToMake / efficiency) + 1
    } else { return nil }
}

因此，如果您计算calculateCost(WoodStick, WoodLog, 64)，它应该返回 8

顺便说一下，我没有编译或测试任何这些。这都是伪代码

编辑:回答有关多个 Material 项目的评论中的问题。

class Item: NSObject {
    var name : String?
    var id : Int?
    var tier : Int?
    var material : String?

    init(_ name : String?,_ id : Int?,_ tier : Int?,_ material : String?) {
        self.name = name
        self.id = id
        self.tier = tier
        self.material = material
    }

}

class Equipment : Item {
    var components : [[Item : Int]]?

    override init(_ name : String?,_ id : Int?,_ tier : Int?,_ material : String?) {
        super.init(name, id, tier, material)
    }

    init(_ name : String?,_ id : Int?,_ tier : Int?,_ material : String?,_ components : [[Item : Int]]?) {
        super.init(name, id, tier, material)
        self.components = components
    }
}

Basic example of how to proceed

   override func viewDidLoad() {
        super.viewDidLoad()

        let item = Item(nil, nil, nil , "wood")
        let item2 = Item(nil,nil,nil,"metal")
        let equipment = Equipment(nil, nil, nil, nil, [[item : 1],[item2 : 5]])

        checkType(object: item2)
        checkType(object: equipment)
    }


    func checkType(object: NSObject) {
        if let obj = object as? Equipment {
            print("Equipment")
            // do work here
        } else if let obj = object as? Item {
            print("Item")
            // do work here
        }
    }