test_feb_13_2021

saving_marvel.md

Saving Marvel

In a parallel universe called Marvel, an infectious viral disease has been spreading at a very fast rate. Dr. Strange Is trying to create a potion that would prevent people from catching the disease and would also cure the ones already diseased.

He knows that the cure is a potion which is a mixture of N chemicals and is K liters in volume. He does not know the amount of each chemical that must be added and hence is experimenting on the same.

As the assistant of Dr. Strange, you help him in his task and ask him how to prepare the potion, to which he replies:

1. Chemicals must be added in the increasing order of their labels.
2. The amount of chemicals being added must be between 1 and L where L Is the amount of mixture obtained till that step.
3. Exactly 1 liter of the first chemical must be taken

You, along with being a biologist, are a good programmer and mathematician and hence, decide to find the number of potions possible In accordance with Dr. Strange's Instructions using a computer program.

Input Specification:

input1: N, The number of chemicals.
input2: K, the total amount of chemical to be added.

Output Specification:

Your function should return the required value.

Example 1:

input1: 2
input2: 2

Output: 1

Explanation:

Possible ways:

1. chemical 1 - 1L chemical 2 - 1L

Example 2:

input1: 5
input2: 10

Output: 6

Explanation:

Possible ways:

1. chemical 1 - 1L, chemical 2 - 1L, chemical 3 - 2L, chemical 4 - 4L, chemical 5 - 2L
2. chemical 1 - 1L, chemical 2 - 1L, chemical 3 - 2L, chemical 4 - 3L, chemical 5 - 3L
3. chemical 1 - 1L, chemical 2 - 1L, chemical 3 - 2L, chemical 4 - 2L, chemical 5 - 4L
4. chemical 1 - 1L, chemical 2 - 1L, chemical 3 - 1L, chemical 4 - 3L, chemical 5 - 4L
5. chemical 1 - 1L, chemical 2 - 1L, chemical 3 - 1L, chemical 4 - 2L, chemical 5 - 5L
6. chemical 1 - 1L, chemical 2 - 1L, chemical 3 - 1L, chemical 4 - 1L, chemical 5 - 6L

saving_marvel.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
# created_on: 2021-02-13 16:01

"""Test Feb 13 2021."""


__author__ = 'Toran Sahu <toran.sahu@yahoo.com>'
__license__ = 'Distributed under terms of the MIT license'


class UserProblem:
    @classmethod
    def solve(cls, input1, input2):
        cls.N = input1
        cls.K = input2
        cls.W = 0  # possible ways

        if cls.N <= 0 or cls.K <= 0:
            return 0
        elif cls.N > cls.K:
            return 0
        elif cls.N == cls.K:
            return 1
        elif cls.K > 2**(cls.N - 1):
            return 0

        A = Node(1)
        B = Node(1)
        level = 2
        A.add_child(B)
        cls.do(B, level)
        return cls.W

    @classmethod
    def do(cls, node, level):
        if level == cls.N:
            if node.total == cls.K:
                cls.W += 1
            return

        for i in range(1, node.total + 1):
            child = Node(i)
            node.add_child(child)
            cls.do(child, level + 1)


class Node:
    def __init__(self, val):
        self.value = val
        self.children = []
        self.total = self.value

    def add_child(self, node):
        node.total += self.total
        if node.total <= self.total:
            self.children.append(node)


if __name__ == '__main__':
    p = UserProblem()
    print(p.solve(5, 11))