8
\$\begingroup\$

I solved this programming challenge whose objective is to come up with an OO solution to the problem.

The problem statement is quite verbose and the tl;dr version would be:

Given an enemy army(Falicornia) made up of Horses, Elephants, Armoured Tanks and Sling Guns and our own similar army(Lengaburu). Find out the minimum army required to defeat this based on a few rules as below

Our army(Lengaburu) will have 100 Horses, 50 Elephants, 10 Armoured Tanks and 5 Sling Guns

Rule #1. The Power Rule: Each Lengaburu army unit is 2X more powerful than their Falicornia counterpart.

Example: 1 Lengaburu Horse can counter 2 Falicornia Horses, 1 Lengaburu Elephant can counter 2 Falicornia Elephants and so on.

Rule #2. The Like-to-Like Rule: Falicornia Horses battalion should be countered with Lengaburu horses battalion, Elephants with elephants and so on. Except when the battalion is completely exhausted (see Rule #3).

Example: If Falicornia deploys 2 H, 4 E, 0 AT and 6 SG, Lengaburu should counter with 1 H, 2 E, 0 AT and 3 SG.

Rule #3. The Substitution Rule: When all units of a particular Lengaburu battalion is exhausted, an adjacent battalion can be used. 1 Elephant can replace 2 Horses (and 2 Horses can replace 1 Elephant), 1 Armoured Tank can replace 2 Elephants (and vice versa) and 1 Sling Gun can replace 2 Armoured Tanks (and vice versa). Note that only adjacent battalions can be used for substituting. Horses cannot replace Sling Guns as they are not adjacent.

Example: If Falicornia deploys 204 H, 20 E, 0 AT and 0 SG, Lengaburu should counter with 100 H, 11 E (1 Elephant has substituted 2 Horses which got exhausted at 100)

Rule #4. The Substitution Choice Rule: When there are 2 possibilities of substitution, then always a lower ranked battalion should be used (Horses is lower than Elephants, is lower than Armoured Tanks, is lower than Sling Guns)

Example: If Falicornia deploys 50 H, 104 E, 6 AT and 2 SG, Lengaburu should counter with 29 H, 50 E, 3 AT and 1 SG (4 Horses substituted for 2 Elephants instead of the higher ranked Armoured Tanks)

Sample Input and Output

Sample 1

Input: Falicornia attacks with 100 H, 101 E, 20 AT, 5 SG

Expected Output: Lengaburu deploys 52 H, 50 E, 10 AT, 3 SG and wins

Sample 2

Input: Falicornia attacks with 250 H, 50 E, 20 AT, 15 SG

Expected Output: Lengaburu deploys 100 H, 38 E, 10 AT, 5 SG and loses

I am relatively new to OO Python and Python.

I'm looking for a review on how OO the solution is, how accurate the modelling is for the problem described and how Pythonic my code is coming from someone who mostly writes C#.


The Army class

class Army:
    """Army holds all the battalions along with their strength.
    Army can update, add new battalions and their strength
    """
    def __init__(self, **battalions):
        self.battalion_strength: Dict[BattalionType, int] = {}
        for k, v in battalions.items():
            if BattalionType.is_valid_battalion(k) and isinstance(v, int):
                self.battalion_strength[BattalionType(k)] = v

    def get_battalion_strength(self, battalion_type: BattalionType) -> int:
        """Returns the strength of the battalion in this army
        Arguments:
            battalion_type {BattalionType} -- [type of battalion whose 
            strength needs to be found]

        Raises:
            KeyError: [Raises when battalion_type is not present in the army]

        Returns:
            [int] -- [strength of battalion_type]
        """
        if battalion_type not in self.battalion_strength:
            raise KeyError("{0} not found".format(battalion_type))
        return self.battalion_strength.get(battalion_type)

    def update_battalion_strength(self, battalion_type: BattalionType,
                                  change: int):
        """adds a new battalion_type battalion if not present else 
        updates the strength of the battalion

        Arguments:
            battalion_type {BattalionType} -- [Type of battalion to be added or updated]
            change {int} -- [represents change in the strength of the battalion]
        """
        if battalion_type not in self.battalion_strength:
            self.battalion_strength[battalion_type] = change
        else:
            self.battalion_strength[battalion_type] += change

    def get_battalions(self) -> List[BattalionType]:
        return list(self.battalion_strength.keys())

    def has_battalion(self, battalion_type: BattalionType) -> bool:
        return battalion_type in self.battalion_strength

    def __eq__(self, other): 
        if not isinstance(other, Army):
            return False
        return self.battalion_strength == other.battalion_strength

BattalionProcessor class.

This class hold the multiplier (Rule 1) and I have extended it to also accept the seniority of battalions so that newer battalions can be added or existing ones can have their seniority changed

The substitution order of battalion is modelled as a graph to allow for uni-directional relations (i.e only horse can replace elephants and not vice versa) also to be open to adding additional substitutions (like a horse can replace sling guns)

class BattalionProcessor:
    """[summary]
    Class to hold the battalion seniority and substitution battalions
    """

    def __init__(self, multiplier: int = 2, **battalions):
        self.multiplier = multiplier
        self.battalion_seniority: Dict[BattalionType, int] = {}
        self.substitution_graph: Dict[BattalionType, List[Tuple[BattalionType, float]]] = {}
        for k, v in battalions.items():
            if BattalionType.is_valid_battalion(k) and isinstance(v, int):
                self.battalion_seniority[BattalionType(k)] = v    

    def get_battalion_seniority(self, battalion_type: BattalionType) -> int:
        return self.battalion_seniority.get(battalion_type, 100)

    def add_battalion_substituation(self, from_battalion_type: BattalionType,
                                    to_battalion_type: BattalionType,
                                    multiplier: int,
                                    bidirectional: bool = True) -> None:
        """[summary]

        Arguments:
            from_battalion_type {BattalionType} -- [from battalion_type]
            to_battalion_type {BattalionType} -- [to battalion_type]
            multiplier {int} -- [amount of from_battalion_type required to 
            make 1 to_battalion_type]
            bidirectional {bool} -- [indicates weather the relationship 
            is bidirectional] (default: {True})
        """
        from_sub_btn = self.substitution_graph.get(from_battalion_type, [])
        from_sub_btn.append((to_battalion_type, multiplier))
        self.substitution_graph[from_battalion_type] = from_sub_btn
        if(bidirectional):
            to_sub_btn = self.substitution_graph.get(to_battalion_type, [])
            to_sub_btn.append((from_battalion_type, 1/multiplier))
            self.substitution_graph[to_battalion_type] = to_sub_btn

    def get_substitution_battalion(self, battalion_type: BattalionType) -> List[Tuple[BattalionType, float]]:
        """[summary]
        Returns the list of Tuple of BattalionType and multipler indicating
        how much of that battalion is need to make 1 of the input battalion_type
        Arguments:
            battalion_type {BattalionType} -- [Input battalion whose 
            substitution order needs to be found]

        Returns:
            List[Tuple[BattalionType, float]] -- [substitution order of the 
            input battalion]
        """
        unordered_sub_btn = self.substitution_graph.get(battalion_type, [])
        return sorted(unordered_sub_btn,
                      key=lambda btn: self.get_battalion_seniority(btn))

BattalionType enum

from enum import Enum


class BattalionType(Enum):
    HORSES = "horses"
    ELEPHANTS = "elephants"
    ARMOUREDTANKS = "armoured_tanks"
    SLINGGUNS = "sling_guns"

    @staticmethod
    def is_valid_battalion(battalion_name: str) -> bool:
        btn_names = [bat.value for bat in BattalionType]
        return battalion_name in btn_names

The BattlePlanner class which does the actual computation with the other two as dependencies

class BattlePlanner:

    def __init__(self, battalion_processor: BattalionProcessor, our_army: Army):
        self.battalion_processor: BattalionProcessor = battalion_processor
        self.our_army: Army = our_army
        self.__result_army: Army = Army()

    def update_battalion_stats(self, our_battalion: BattalionType, our_strength: int,
                               enemy_battalion: BattalionType, enemy_strength: int,
                               resolvable: int) -> int:
        enemy_strength -= resolvable
        self.our_army.update_battalion_strength(our_battalion, -our_strength)
        self.__result_army.update_battalion_strength(our_battalion, our_strength)
        return enemy_strength

    def resolve_battalion(self, enemy_battalion: BattalionType,
                          enemy_strength: int) -> bool:

        remaining_strength: int = self.apply_power_rule(enemy_strength)
        if self.our_army.has_battalion(enemy_battalion):
            remaining_strength = self.resolve_with_similar_battalion(enemy_battalion,
                                                                     remaining_strength)

        if remaining_strength > 0:
            remaining_strength = self.resolve_with_substitution_battalion(enemy_battalion,
                                                                          remaining_strength)
        return remaining_strength == 0

    def resolve_with_similar_battalion(self, enemy_battalion: BattalionType,
                                       enemy_strength: int) -> int:
        our_strength = self.our_army.get_battalion_strength(enemy_battalion)
        resolvable_strength = min(our_strength, enemy_strength)
        resolved_strength = self.update_battalion_stats(enemy_battalion, resolvable_strength,
                                                   enemy_battalion, enemy_strength,
                                                   resolvable_strength) 
        return resolved_strength

    def apply_power_rule(self, enemy_strength: int) -> int:
        return int(ceil(enemy_strength / self.battalion_processor.multiplier))

    def resolve_with_substitution_battalion(self, enemy_battalion: BattalionType,
                                            enemy_strength: int) -> int:
        substitution_battalions = self.battalion_processor.get_substitution_battalion(enemy_battalion)
        for substitution_battalion in substitution_battalions:
            if enemy_strength == 0:
                break
            required_strength = ceil(substitution_battalion[1] * enemy_strength)
            actual_strength = self.our_army.get_battalion_strength(substitution_battalion[0])

            resolvable_strength = min(required_strength, actual_strength)
            normalized_resolvable = min(int(ceil(resolvable_strength *
                                        (1 / substitution_battalion[1]))),
                                        enemy_strength)
            enemy_strength = self.update_battalion_stats(substitution_battalion[0],
                                                         resolvable_strength,
                                                         enemy_battalion, enemy_strength,
                                                         normalized_resolvable)

        return enemy_strength

    def get_winning_army(self, enemy_army: Army) -> Army:
        """Returns the minimum required army and a bool 
        indicating the result of the battle with the returned
        army
        True : Returned army will win
        False : Returned army will lose
        Arguments:
            enemy_army {Army} -- [The army to battle against]
        Returns:
            Army -- [Minimum required army to defeat enemy_army]
            battle_result {bool} -- [boolean indicating the result of the battle]
        """
        battle_result: bool = True
        for enemy_battalion in enemy_army.get_battalions():
            enemy_strength = enemy_army.get_battalion_strength(enemy_battalion)
            battle_result &= self.resolve_battalion(enemy_battalion, enemy_strength)
        return battle_result, self.__result_army

The code is in Github to be easier to read

\$\endgroup\$
  • \$\begingroup\$ I don't get the exhaustion rule. Where are the limits defined? \$\endgroup\$ – Mathias Ettinger Jul 9 at 6:58
  • \$\begingroup\$ @MathiasEttinger Sorry, the question was a bit vague. I have edited the question and provided a link to the original question as well. The limit is we start with a pre-defined strength for each battalion \$\endgroup\$ – thebenman Jul 9 at 7:28
  • \$\begingroup\$ I don't quite get Sample 2 above (quoted from geektrust.in Sample III): Why, instead of deploying all elephants or acknowledging inferiority deploy 38 of them? \$\endgroup\$ – greybeard Jul 10 at 4:48
  • \$\begingroup\$ @greybeard Falicornia has 250 which uses all 100 H and still has 50H to resolve. Falicornia has 50E which requires 25E which has to be applied due to the like to like rule. Then for the remaining 50H it applies 13E which brings it to 38H \$\endgroup\$ – thebenman Jul 11 at 14:30
3
\$\begingroup\$

Dict updates

This:

if battalion_type not in self.battalion_strength:
    self.battalion_strength[battalion_type] = change
else:
    self.battalion_strength[battalion_type] += change

can be done more easily in a few different ways. Perhaps the easiest is to make battalion_strength a defaultdict(int). Then, this if goes away and you can "naively" do +=.

Redundant parens

if(bidirectional):

We aren't in Java anymore :)

Cache btn_names

This won't change, so you should probably save it as a class constant rather than a variable within the method is_valid_battalion.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.