5
\$\begingroup\$

I need to find the number of five-digit octal numbers in which all digits are different and no two odd or even digits are adjacent.

My code below gives the correct answer, but I'm not satisfied. Can you help me improve it or how would you solve this task?

from itertools import product

c = 0
for args in product((0, 1, 2, 3, 4, 5, 6, 7), repeat=5):
    n1, n2, n3, n4, n5 = args
    
    # no zero start
    if n1 == 0: continue
    if (n1 + n2) == 0: continue
    if (n1 + n2 + n3) == 0: continue
    if (n1 + n2 + n3 + n4) == 0: continue
    if (n1 + n2 + n3 + n4 + n5) == 0: continue

    # different digits
    if (args.count(0) > 1 or args.count(1) > 1 or args.count(2) > 1
    or args.count(3) > 1 or args.count(4) > 1 or args.count(5) > 1 or
    args.count(6) > 1 or args.count(7) > 1): continue

    # even odd even odd even    or    odd even odd even odd
    if ((n1 % 2 == 0 and n2 % 2 != 0 and n3 % 2 == 0 and n4 % 2 != 0 and n5 % 2 == 0) or
        (n1 % 2 != 0 and n2 % 2 == 0 and n3 % 2 != 0 and n4 % 2 == 0 and n5 % 2 != 0)):
        c+=1

print(c) # 504 (correct)
\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

As Toby noted, it's not too difficult to calculate the answer. The more you can offload the computer work to insights from your brain, the better your approach will be. But we'll proceed with reviewing your code.

  • As noted, c is not a good variable name. I'll call it validNumbers.

  • I would recommend to always put continue on the next line. Leaving it on the same line can lead to overlooking what you're doing.

  • I don't see how n1+n2==0 could happen if n1!=0.

  • (0,1,2,3,4,5,6,7) is better written as range(8).

  • itertools also has permutations, which guarantees no repeated elements. (Otherwise, I would say that you should have len(args)==len(set(args)).)

  • Python allows you to chain comparisons. This means that "even odd even odd even" could be n1 % 2 == n3 % 2 == n5 % 2 == 0 and n2 % 2 == n4 % 2 != 0. Even better would be to combine the two tests into one: n1 % 2 == n3 % 2 == n5 % 2 != n2 % 2 == n4 % 2.

  • Instead of the first line assigning everything from args, it would be better to have for n1, n2, n3, n4, n5 in permutations(range(8), r=5): and skip args. But even better would be to have everything in terms of args. This makes the parity checks a bit harder, but not too bad: args[::2] gets the items with even indices (n1, n3, and n5), while args[1::2] gets the odd indices. Then we can use a comprehension and put those items into a set to make sure they're all the same. (This removes needing the previous paragraph.)

from itertools import permutations

validNumbers = 0
for args in permutations(range(8), r=5):
    # no zero start
    if args[0] == 0:
        continue

    evens = set(n%2 for n in args[::2])
    odds  = set(n%2 for n in args[1::2])
    if ( len(evens)==len(odds)==1 and evens != odds ):
        validNumbers+=1

print(validNumbers) # 504 (correct)

The big advantage of this approach is that we can now easily adjust the base or the length by simply changing the 8 or 5 in line 4, and the rest of the code remains the same.

If 8 or 5 were much bigger, then this could start slowing down. In that case, you could create your number one digit at a time, and only proceed if the number is correct so far. Or grab the evens separately from the odds, with something like:

for evens,odds in product(permutations(range(0,8,2),r=3),permutations(range(1,8,2),r=3)):
\$\endgroup\$
0
5
\$\begingroup\$

The code is reasonably clear. It obviously iterates over all possible 5-digit octal numbers, and tests each one to determine if it satisfies the required property. I would suggest renaming the variable c to something clearer, such as count.

An alternative that you might want to consider, which will execute faster, is to construct all the numbers which satisfy the property. Or rather, count how many we could construct.

We have 7 choices for our first digit: 1, 2, ..., 7. If we pick an odd number, then the second digit must be even, and if we pick an even number it must be odd. Either way, we have a choice of 4 different digits.

For the third digit, it must have the same oddness as the first, but not be the same - that leaves 3 possibilities, and the same for the fourth. The fifth and final digit is chosen from just two possibilities.

That makes the program very simple (apart from adding the above explanation as a comment):

print(7 * 4 * 3 * 3 * 2)

As this is now so simple, you could consider generalising: How many numbers of n digits in base b have this property? You'll find it a little more difficult when b is odd, so solve for the even-numbered bases first.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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