12
\$\begingroup\$

I solved a Risk game question (http://www.pyschools.com/quiz/view_question/s3-q12) in two ways, but as I am currently learning Python, I'm just wondering how to rate my methods of solving this question. Like which one of these ways is really a better, effective, and efficient method to solve this question? Or maybe there is a better approach than what I did?

This is the game instruction: "In the Risk board game, there is the situation where the attacker rolls 3 dice while the defender rolls 2 dice. To determine the outcome, the highest die of each player is compared, followed by the next highest die. For each case, the attacker's die has to be higher than that of the defender to win. The loser will lose 1 army in each case."

This is the sample of the function and the return statement:

    >>> RiskGame([6,2,6], [6, 6])
    'Attacker loses 2 armies.'
    >>> RiskGame([1,4,1], [1, 2])
    'Attacker loses 1 army and defender loses 1 army.' 

Method 1

def RiskGame(attacker, defender):
    a_score = 0
    a_loose = 0
    d_score = 0
    d_loose = 0
    for e in range(len(defender)):
        a= max(attacker)
        d= max(defender)
        
        if a>d:
            a_score +=1
            d_loose +=1
        
        else:
            d_score +=1
            a_loose +=1
        attacker.remove(a)
        defender.remove(d)
    if a_loose == 0:
        return 'Defender Loses %i armies.' %d_loose
    elif d_loose == 0:
        return 'Attacker loses %i armies.' %a_loose
    else:
        return 'Attacker loses %i army and defender loses %i army.' %(a_loose, d_loose)
            
RiskGame([1,2,6], [1, 5])
RiskGame([1,4,1], [1, 2])
RiskGame([6,2,6], [6, 6])

Method 2

def RiskGame(attacker, defender):
    a = sorted(attacker, reverse=True)
    b = sorted(defender, reverse=True)
    
    a_scr =0
    d_scr =0
    pairs = zip(a,b)
    for i,j in pairs:
        if i>j:
            a_scr +=1
        else:
            d_scr +=1
    if d_scr == 0:
        return 'Defender loses %i armies.' %a_scr
    elif a_scr == 0:
        return 'Attacker loses %i armies.' %d_scr
    else:
        return 'Attacker loses %i army and defender loses %i army.' %(a_scr, d_scr)

RiskGame([1,2,6], [1, 5])
RiskGame([1,4,1], [1, 2])
RiskGame([6,2,6], [6, 6])
\$\endgroup\$
13
\$\begingroup\$

Nice implementation for both methods, few suggestions:

  • Camel case or underscores. The function RiskGame uses camel case notation but the variables use underscore notation (a_score). Better to use only one notation. Generally, underscores are preferred in Python.
  • Unused variables: a_score and d_score in Method 1.
  • Variable names can be improved: a_scr can be renamed to attacker_score. This statement a=max(attacker) could be attacker_max_number=max(attacker) or similar. Even if it's longer, makes the code easier to read.
  • Return the result instead of a human-readable string, it's easier to reuse and test. For example instead of:
    def RiskGame(attacker, defender):
        #...
        if d_scr == 0:
            return 'Defender loses %i armies.' %a_scr
        elif a_scr == 0:
            return 'Attacker loses %i armies.' %d_scr
        else:
            return 'Attacker loses %i army and defender loses %i army.' %(a_scr, d_scr)
    
    return the result directly:
    def RiskGame(attacker, defender):
        #...
        return attacker_score, defender_score
    
    attacker_score, defender_score = RiskGame([1,2,6], [1, 5])
    if defender_score == 0:
        print('Defender Loses %i armies.' %attacker_score)
    #...
    

Which method is more efficient?

There are no issues about performances given the requirements of max three elements for the input list. In fact, as @Jasmijn points out in the comments, on the condition that 1 <= len(attacker) <= 3 and 1 <= len(defender) <= 2, the time complexity of both methods is \$O(1)\$.

If the input lists have many elements and the attacker's list is bigger than the defender's list, I would say Method 2 is faster. The time complexity of Method 1 would be \$O(d*a)\$ where \$d\$ is the length of the defender's list and \$a\$ is the length of the attacker's list. Even if the lists shrink at each iteration we can say that for big inputs. Method 2 would be \$O(a*log(a))\$, assuming that the zip() function runs in \$O(d)\$ and sorting the attacker's list takes \$O(a*log(a))\$.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ thank you very much for this thorough and marvelous review and feedback. I really appreciate it, next time, I will use your comments as a guide to improve my codes. \$\endgroup\$
    – teemran
    Sep 12 '20 at 13:04
  • 3
    \$\begingroup\$ Given the rules of Risk, 1 <= len(attacker) <= 3 and 1 <= len(defender) <= 2, both methods are O(1) under those constraints. \$\endgroup\$
    – Jasmijn
    Sep 12 '20 at 18:07
  • \$\begingroup\$ @Jasmijn thanks, I included your feedback in the answer. \$\endgroup\$
    – Marc
    Sep 13 '20 at 3:18
  • 1
    \$\begingroup\$ @teemran thanks, I am glad I could help. Please consider to choose an answer when you are satisfied ;) \$\endgroup\$
    – Marc
    Sep 13 '20 at 3:20
  • \$\begingroup\$ The time complexity of any algorithm with a maximum input size is O(1). Bubble sort on a deck of cards is O(1). It's a rather vacuous statement. \$\endgroup\$ Sep 14 '20 at 3:35
7
\$\begingroup\$

You have some good answers already. Rather than focusing on the details of your code, I'll offer some comments about how to approach the design of a full program. I don't know your exact situation, but when you are learning, command-line programs are a good focal point for various practical reasons, so I'll use that as an illustration.

Functional core and imperative shell. As much as possible, strictly separate your program into two types of functions: (A) those that do nothing but take data and return data (the core); and (B) those that have side-effects (the shell). What counts as a side-effect? Many things, but printing and exceptions are two of the most common. The core idea here is that most of your program (and especially its algorithmic, computational details) should reside in the functional core. The outer shell concerned with printing and interactivity should be as thin and as non-algorithmic as possible. In the example below, main() is the outer shell and it is puny from an algorithmic perspective -- nothing more than a trivial if-else. If you want to learn more about these ideas, the best talk I've seen on this core-shell separation is from Gary Bernhardt.

Break it down. Once you have that fundamental separation in mind, start decomposing the needed computations into reasonably small parts. This effort is part art, part science. How far you should pursue decomposition depends on the context. The example below takes it pretty far. The more complex the program, and the higher the stakes, the more seriously you want to take the decomposition effort. In simpler situations, various shortcuts are fine. But when the program is important, you need to write tests for it, and the demands of testability will often drive you to decompose more (it can be difficult to test functions that do too many things at once, and it's a big headache to test functions that have major side effects).

Notice the simplicity that emerges. The functions end up being small, easy to understand, quick to describe in a comment for the reader. In most situations those benefits outweigh (often significantly) the extra costs of taking the extra time to break things apart.

import sys

def main(args):
    # Command-line usage example: `python risk_game.py 3,4,6 3,5`
    attacker, defender, error = parse_entries(args)
    if error:
        print(error)
        sys.exit(1)
    else:
        message = risk_game(attacker, defender)
        print(message)

def parse_entries(entries):
    # Takes attacker and defender entries. Returns a 3-tuple: (ATTACKER-ROLLS,
    # DEFENDER-ROLLS, ERROR-MESSAGE). There are more featureful and robust ways
    # to handle this; adjust as needed.
    try:
        return (parse_entry(entries[0]), parse_entry(entries[1]), None)
    except Exception as e:
        return (None, None, 'Invalid entry')

def parse_entry(entry):
    # Parses a single entry and returns a list of dice rolls.
    return [int(val) for val in entry.split(',')]

def risk_game(attacker, defender):
    # Takes two lists of dice rolls. Returns a message describing the outcome.
    score = compute_battle_score(attacker, defender)
    return generate_message(attacker, defender, score)

def compute_battle_score(attacker, defender):
    # Takes two lists of dice rolls. Returns a battle score.
    atts = sorted(attacker, reverse = True)
    defs = sorted(defender, reverse = True)
    return sum(1 if a > d else -1 for a, d in zip(atts, defs))

    # Or if you need to know N of victories for each combatant.
    return collections.Counter(a > d for a, d in zip(atts, defs))

def generate_message(attacker, defender, score):
    # Make it as fancy as you want.
    return f'Attacker score: {score}'

if __name__ == '__main__':
    main(sys.argv[1:])
\$\endgroup\$
7
  • 4
    \$\begingroup\$ Very nice explaination of how and why you should structure your source code this way. However, two remarks about your example code: I would not catch exceptions just to convert them to a regular error message. Just let them propagate to the point where the error can really be dealt with. As for compute_battle_score: a battle round of Risk is not a single number, both attacker and defender can lose armies. While a single number might be enough information for 3 attacker armies and 2 defender armies, the actual game of Risk allows different army sizes, so a single number no longer suffices. \$\endgroup\$
    – G. Sliepen
    Sep 12 '20 at 21:09
  • 2
    \$\begingroup\$ @G.Sliepen Good point about Risk: I'll leave that to the OP to enhance based on what is known to be needed. Regarding exception handling strategy, I agree with you in many contexts, but not this one. If parse_entries() raises, the algorithmic burden on the "imperative shell" increases – not necessarily in my trivial demo, but in a real program where one would want the error message to be specific to the mistake. I want the algorithmic complexity of picking the right message to reside outside of main(), so I illustrated it that way to point the OP on that path. \$\endgroup\$
    – FMc
    Sep 12 '20 at 21:25
  • 1
    \$\begingroup\$ Ah, I can see how a ValueErrormight not be so helpful for the end user. But perhaps rethrowing a more specific exception from within parse_entries() might be better? Returning a tuple makes it easy for the caller to forget to check the error condition. \$\endgroup\$
    – G. Sliepen
    Sep 12 '20 at 21:43
  • \$\begingroup\$ I'd be happy to CR this if you post it as a question. There's a number of things I would suggest changing if this came through in a real PR, e.g., using a function to wrap a list comprehension one-liner, using a function to wrap an f-string, throwing a generic exception and then immediately catching it to print a message, completely hiding the error, and so forth. \$\endgroup\$ Sep 13 '20 at 1:13
  • 1
    \$\begingroup\$ @user1717828 Feel free to comment (I'm always willing to learn and am not bothered by a world of differing opinions), but I'm not building a Risk game (the OP is), so my desire to have it code reviewed is quite low. It wasn't written with that intent (see the text discussion). If it were real software, I would change various details myself. But that's not the context. It's a tiny educational demo written with a specific purpose in mind. \$\endgroup\$
    – FMc
    Sep 13 '20 at 1:23
5
\$\begingroup\$

The first one changes the input, which is bad unless it's supposed to. You could fix that by making copies of the given lists and working on them instead.

The string formatting is unnecessary, since the values are always 2, 2 or (1, 1), respectively. Also gives us the opportunity for good writing style, writing the numbers as words, not digits. Yes, I realize digits are required by the problem setter so it's their fault, not yours. Just saying. You could argue that yours are more general, in case more dice were used, but then you should also use singular/plural appropriately, to avoid saying something like "Attacker loses 5 army".

Finally, I'd pick a side. That is, only count one side's statistic. I'll go with the attacker, as that's the "active" party (as opposed to defense being a reaction).

def RiskGame(attacker, defender):
    _, a1, a2 = sorted(attacker)
    d1, d2 = sorted(defender)
    wins = (a2 > d2) + (a1 > d1)
    if wins == 2:
        return 'Defender loses two armies.'
    elif wins == 0:
        return 'Attacker loses two armies.'
    else:
        return 'Attacker loses one army and defender loses one army.'
\$\endgroup\$
5
  • \$\begingroup\$ Hi, thanks for your suggestion. But can you tell me why this underscore _, a1,...? \$\endgroup\$
    – teemran
    Sep 13 '20 at 9:59
  • \$\begingroup\$ And for the string formatting, it is actually the problem of the questions setter, I just acted based on the requirements, just as you said. Lastly, I simply couldn't understand your boolean comparison for the wins parameter, can you help to clear this? thanks \$\endgroup\$
    – teemran
    Sep 13 '20 at 10:06
  • 1
    \$\begingroup\$ The underscore is because I can't assign three values to only two variables. So I use the underscore variable conventionally used for unused values. Booleans True and False act like 1 and 0, so I can just add the two match results to get the total. \$\endgroup\$ Sep 13 '20 at 10:20
  • \$\begingroup\$ Got it now, you are very correct👍 \$\endgroup\$
    – teemran
    Sep 13 '20 at 10:24
  • 1
    \$\begingroup\$ You can do a1, a2 = sorted(attacker)[1:] \$\endgroup\$ Sep 14 '20 at 3:42
2
\$\begingroup\$

If this were a real PR, I would highlight one of the *loose variables and ask Should this read lose?

I really like your second approach. While reading it, I felt like the next line of code was doing exactly what I was anticipating it would do, and I didn't have to use as much mental memory while reading it like I did your first approach, keeping track of all those variables that were set to zero. One way you might consider improving it is to remove the a_scr and d_scr initializations and use a sum() to calculate them, such as:

def RiskGame(attacker, defender):
    a = sorted(attacker, reverse=True)
    b = sorted(defender, reverse=True)
    
    a_scr = sum([i > j for i, j in zip(a,b)])
    d_scr = sum([i < j for i, j in zip(a,b)])

    if d_scr == 0:
        return 'Defender loses %i armies.' %a_scr
    elif a_scr == 0:
        return 'Attacker loses %i armies.' %d_scr
    else:
        return 'Attacker loses %i army and defender loses %i army.' %(a_scr, d_scr)

RiskGame([1,2,6], [1, 5])

I have similar reservations about the Pascal casing of the functions and returning strings instead of values, but these are covered nicely in the other answers.

Edit: Demonstrate how to use tests

This part covers another way of ensuring your example battles run correctly in a systematic way using pytest. It illustrates why some other the other answers' suggestions to get the printing out of the function makes it easier to code.

Step 1.

Have your main function just return a_scr and d_scr, and put the printing logic in the main script:

# riskgame.py
def risk_game(attacker, defender):
    a = sorted(attacker, reverse=True)
    b = sorted(defender, reverse=True)

    a_scr = sum([i > j for i, j in zip(a,b)])
    d_scr = sum([i <= j for i, j in zip(a,b)])

    return a_scr, d_scr

if __name__ == "__main__":
    a_scr, d_scr = risk_game([6,2,6], [6, 6])

    if d_scr == 0:
        print('Defender loses %i armies.' %a_scr)
    elif a_scr == 0:
        print('Attacker loses %i armies.' %d_scr)
    else:
        print('Attacker loses %i army and defender loses %i army.' %(a_scr, d_scr))

When you execute the script, you get the same behavior as before:

$ python riskgame.py 
Attacker loses 2 armies.

Step 2.

In the same directory create test_wins_and_losses.py and create some tests:

# test_wins_and_losses.py
from riskgame import risk_game
  
def test_d_wins():
    a_scr, d_scr = risk_game([1,2,6], [1, 5])
    assert a_scr == 2
    assert d_scr == 0

def test_a_wins():
    a_scr, d_scr = risk_game([6,2,6], [6, 6])
    assert a_scr == 0
    assert d_scr == 2

def test_equal():
    a_scr, d_scr = risk_game([1,4,1], [1, 2])
    assert a_scr == 1
    assert d_scr == 1

Notice I used the same values you put in the original post, but you could have any example games you want in there. Ideally, you would have lots, covering as many use cases as you can.

Step 3.

Install pytest if you haven't already.

$ pip install pytest

Step 4.

Run it!

$ pytest
============================= test session starts ==============================
platform linux -- Python 3.7.4, pytest-6.0.2, py-1.9.0, pluggy-0.13.1
rootdir: /tmp/risk_game
collected 3 items                                                              

test_wins_and_losses.py ...                                              [100%]

============================== 3 passed in 0.02s ===============================

The idea is now you can change your code, and every time you do you can just type pytest at the command line to confirm everything is still functioning the way you expect. For example, if we make the mistake I made earlier and change the line to

d_scr = sum([i < j for i, j in zip(a,b)])

and run the tests, we get:

$ pytest
==================================================================== test session starts =====================================================================
platform linux -- Python 3.7.4, pytest-6.0.2, py-1.9.0, pluggy-0.13.1
rootdir: /tmp/risk_game
collected 3 items                                                                                                                                            

test_wins_and_losses.py .FF                                                                                                                            [100%]

========================================================================== FAILURES ==========================================================================
________________________________________________________________________ test_a_wins _________________________________________________________________________

    def test_a_wins():
        a_scr, d_scr = risk_game([6,2,6], [6, 6])
        assert a_scr == 0
>       assert d_scr == 2
E       assert 0 == 2

test_wins_and_losses.py:11: AssertionError
_________________________________________________________________________ test_equal _________________________________________________________________________

    def test_equal():
        a_scr, d_scr = risk_game([1,4,1], [1, 2])
        assert a_scr == 1
>       assert d_scr == 1
E       assert 0 == 1

test_wins_and_losses.py:16: AssertionError
================================================================== short test summary info ===================================================================
FAILED test_wins_and_losses.py::test_a_wins - assert 0 == 2
FAILED test_wins_and_losses.py::test_equal - assert 0 == 1
================================================================ 2 failed, 1 passed in 0.09s ================================================================

Happy testing!

\$\endgroup\$
7
  • \$\begingroup\$ Yes, I also realized the bad definition of the lose variable. Thanks for this! \$\endgroup\$
    – teemran
    Sep 13 '20 at 10:10
  • \$\begingroup\$ I really like this idea to just sum and calculate the score directly without initialing the variable to 0, this list comprehensions could be one of the faster ways to create a list, this could enhanced the efficiency of my code. \$\endgroup\$
    – teemran
    Sep 13 '20 at 10:15
  • \$\begingroup\$ However, your code suggestion, will not be able to address the issue when both the attacker and the defender have the same elements eg., RiskGame([1,1,1], [1, 1]) in this way neither the defender nor the attacker will lose any armies. Remember the game instructions: For each case, the attacker's die has to be higher than that of the defender to win. So I refined your code by just changing the d_scr condition with i<=j instead of i<j \$\endgroup\$
    – teemran
    Sep 13 '20 at 10:22
  • 1
    \$\begingroup\$ @teemran Nice catch! BTW, do you know how to use pytests? I think that might be out of scope for your requested code review, but this is an excellent motivation to learn. \$\endgroup\$ Sep 13 '20 at 11:30
  • 1
    \$\begingroup\$ @teemran Updated the answer to help you get started with pytest. \$\endgroup\$ Sep 13 '20 at 12:50

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.