python - 适应性挑战

Question

我正在努力完成 codility 挑战，以提高我的编程技能，或者更确切地说是缺乏编程技能。挑战的详细信息在这里。

In a room there are N ropes and N weights. Each rope is connected to exactly one weight (at just one end), and each rope has a particular durability − the maximum weight that it can suspend. There is also a hook, attached to the ceiling. The ropes can be attached to the hook by tying the end without the weight. The ropes can also be attached to other weights; that is, the ropes and weights can be attached to one another in a chain. A rope will break if the sum of weights connected to it, directly or indirectly, is greater than its durability.

We know the order in which we want to attach N ropes. More precisely, we know the parameters of the rope (durability and weight) and the position of each attachment. Durabilities, weights and positions are given in three zero-indexed arrays A, B, C of lengths N. For each I (0 ≤ I < N): A[I] is the durability of the I-th rope, B[I] is the weight connected to the I-th rope, C[I] (such that C[I] < I) is the position to which we attach the I-th rope; if C[I] equals −1 we attach to the hook, otherwise we attach to the weight connected to the C[I]-th rope. The goal is to find the maximum number of ropes that can be attached in the specified order without breaking any of the ropes. Write a function: def solution(A, B, C) that, given three zero-indexed arrays A, B, C of N integers, returns the maximum number of ropes that can be attached in a given order. For example, Given the following arrays:

A= [4,3,1]
B = [2,2,1]
C = [-1,0,1]

the function should return 2, as if we attach a third rope then one rope will break, because the sum of weights is greater than its durability (2 + 2 + 1 = 5 and 5 > 4).

下面是我尝试的解决方案。我有一个名为 add_weights 的辅助函数，如果添加最新的绳索不会导致任何其他绳索断裂，则返回 True，否则返回 false。

def add_weights(A, ancestors, weights, weight, rope):
    #add weight(int) to rope and ancestors
    if (rope == -1):
        return (True)
    else:
        weights[rope] += weight
        if (A[rope] < weights[rope]):
            print "Rope that breaks", rope
            return False
        ancestor = ancestors[rope]
        print ancestor
        add_weights(A, ancestors, weights, weight, ancestor)




def solution(A, B, C):
    # write your code in Python 2.7
    weights = {}
    ancestors = {}
    for i in range(len(B)):
        weights[i] = B[i]
    for i in range(len(C)):
        #attaching rope i to rope x
        x = C[i]
        ancestors[i] = x
        broke = add_weights(A, ancestors, weights, B[i], x)
        if (not broke):
            return i
    return len(C)

问题是在函数解决方案中 for 循环的第二次迭代期间(当我尝试添加绳索 1 时)，变量 break 以某种方式计算为 None，此时我可以清楚地看到 add_weights 返回 True。我也用调试器测试过它，所以我不完全确定发生了什么。欢迎任何帮助。

Answer 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Exercise5_DurablityofRopes
{
    class Program
    {
           static int[] A_Durability = new int[] { 15, 6, 2,3,1 };
           static int[] B_Weight = new int[] { 2, 1, 2,3,1 };
           static int[] C_Position = new int[] { -1, 0, 1 ,2,3};
           static int no_of_ropes_attached = 0;
           static int maxropeattached = 0;
           static void Main(string[] args)
        {
           // first position cannot necessarily be -1 hence Checking for each position How many maximum ropes can be attached
            for (int i = 0; i <= C_Position.Length - 1; i++)
            {
                int[] Copy_Durability = new int[A_Durability.Length];
                for (int l = 0; l <= C_Position.Length - 1; l++)
                {
                    Copy_Durability[l] = A_Durability[l];
                }
                AddNextRope(i, B_Weight[i], Copy_Durability);          
                Console.WriteLine("Total Number of ropes can be attached to " + C_Position[i] + " ropes are" + no_of_ropes_attached);
                if (no_of_ropes_attached>=maxropeattached)
                {
                    maxropeattached = no_of_ropes_attached;
                }
                no_of_ropes_attached = 0;
            }

            Console.WriteLine("Total Number of ropes can be attached is  " + maxropeattached);
            Console.ReadKey();
        }

        private static void AddNextRope(int currentRopePosition,int newWeight,int[] Durability)
        {
            if (currentRopePosition == C_Position.Length - 1) return;
            // decrease same amount of weight from all ansestors from their durability and check if any of them breaks (durability <0) with new weight added
            for (int k = currentRopePosition; k != 0; k--)
            {
                Durability[k] = Durability[k] - newWeight;
                if(Durability[k]<0)
                {
                    return;
                }
            }
            no_of_ropes_attached = no_of_ropes_attached + 1; 

            for (int i = 0; i <= C_Position.Length - 1; i++)
                {
                    if (C_Position[i] == C_Position[currentRopePosition] + 1)
                    {
                        if (A_Durability[i] > B_Weight[i])
                        {
                            AddNextRope(i, B_Weight[i], Durability);
                        }
                        else
                        {
                            return;
                        }
                    }
                }
        }
    }
}