CODEWITHSUNDEEP
c#algorithmlinq
j.castillo
j.castillo

Reputation: 88

Smallest Sum Algorithm

I feel like I may not have been clear enough about the requirements so let me try to make things more clear.

You are provided a dictionary that contains keys that are either single letters or multiple letters. Each key has an associated value. Given an input, you must find the keys that contain the input letters. Return the lowest key values that satisfy this requirement.

Here are a few examples:

Input Dictionary

Key -> Value

a -> 4

b -> 6

e -> 5

abc -> 8

Input: 'a' Output: 4

Input: 'c' Output: 8

Input: 'ab' Output: 8

Input: 'ac' Output: 8

Input: 'ce' Output: 13

Input: 'd' Output: null

Note on the third example, the input is ab. So here, we can either get the letter 'a' from the key 'a' or the key 'abc'. We can either get the letter 'b' from the key 'b' or the key 'abc'. In order to get both keys with the lowest total value, 'abc' with a value of 8 is the correct output.

Note on the fifth example, the input is ce. The letter 'c' is only available in the key 'abc'. The letter 'e' is only available in the key 'e'. The correct output in this situation is 13.

UPDATE: I was able to solve this recursively by starting off with the first letter in the input sequence, finding all keys that contain that letter, and for each key, building a list of all the possible combinations. I was able to track the lowest sum by recursively moving through one letter of the input sequence at a time.

Upvotes: 0

Views: 244

Answers (4)

Sotiris
Sotiris

Reputation: 52

i don't know if i get it right

private static Dictionary<string, int>  dic=new Dictionary<string, int>()  ;
public static void MinSum()
{

    // here create statements where the key is a single letter
    dic.Add("a", 4);
    dic.Add("b", 6);
    dic.Add("c", 3);
    dic.Add("d", 4);
    dic.Add("e", 5);
    // here add the combination
    dic.Add("abcde", 8);
    dic.Add("abce", 10);
    dic.Add("ae", 2);

    var minSum= GetMinSum( "ae".ToCharArray());
    var minSum2 = GetMinSum("abc".ToCharArray());
    var minSum4 = GetMinSum("a".ToCharArray());

}

public static int GetMinSum(char[] letters)
{
    //If the input is a single letter, then I simply return the value associated with that key
    if (letters.Count() == 1)
        return dic[letters[0].ToString()];

    // sumUp all the single Key elements
    var sumOfSingleKeyElements = dic.Where(x => x.Key.Length == 1 && letters.Contains(x.Key[0])).Sum(v => v.Value);
    // get the min value Key elements that combine the letters above
    //  the " !letters.Except(x.Key.ToCharArray()).Any()" defines if the set letters is a subset of the key
    var minOfCompositeKeyElements = dic.Where(x => x.Key.Length > 1 
                        && !letters.Except(x.Key.ToCharArray()).Any()
                        ).Min(v => v.Value);

    return sumOfSingleKeyElements < minOfCompositeKeyElements ? sumOfSingleKeyElements : minOfCompositeKeyElements;
}
  • The minimum sum for the letter combination "a","e" is 2
  • The minimum sum for the letter combination "a","b","c" is 8
  • The minimum sum for the letter "a" is 4

Upvotes: 0

Swati
Swati

Reputation: 67

  #!/usr/bin/python3                                                                                                       
  import operator

    def smallest_sum(dic):
        a_dic = {}
        b_dic = {}
        # get a list of all keys containing a and b
        for key in dic:
            if "a" in key:
                a_dic[key] = dic[key]
            elif "b" in key:
                b_dic[key] = dic[key]

        a_dic = sorted(a_dic.items(), key=operator.itemgetter(1))
        b_dic = sorted(b_dic.items(), key=operator.itemgetter(1))

        if "ab" in a_dic[0]:
            return a_dic[0][1]
        else:
            a_sum_b = a_dic[0][1] + b_dic[0][1]
            return a_sum_b

    if __name__ == "__main__":
        dic = {"a":2, "b":3, "abc":10, "ab": 15, "bcd": 2}
        sum = smallest_sum(dic)
        print(sum)

Upvotes: 0

Prashant Negi
Prashant Negi

Reputation: 348

What I am suggesting here is a bit long method but this is what i can think of to help you right now Take a max count variable Now if the input is multiple letters check for all the strings who have the required alphabets. Also look for "sum of alphabets" separately.

Keep on updating the max_count variable accordingly.

Upvotes: 0

Zizy Archer
Zizy Archer

Reputation: 1390

You can and probably should do recursion. Always grab the next letter of the string you are searching for, and continue building all the possibilities. For each branch, keep just the smallest value and the string it is associated to.

Starting with letter a, you have 2 options - either [4, a] or [8, abc]. Now you continue to the next letter, for a you now have [6, b] or [8, abc]. As this is the end of the list, and b is smaller than abc, you end up with [10, ab] here. Now the other, abc branch, can skip b - it already has it. So, you compare [8, abc] vs [10, ab] and abc is smaller, so it gets returned. And is the final solution already.

Upvotes: 1

Related Questions