Skip to content

Latest commit

 

History

History
91 lines (61 loc) · 2.76 KB

introduction.md

File metadata and controls

91 lines (61 loc) · 2.76 KB

Introduction

There are various idiomatic approaches to solve Grains. You can use bit shifting to calculate the number on grains on a square. Or you can use exponentiation. Another approach is to use pow.

General guidance

The key to solving Grains is to focus on each square having double the number of grains as the square before it. This means that the number of grains grows exponentially. The first square has one grain, which is 2 to the power of 0. The second square has two grains, which is 2 to the power of 1. The third square has four grains, which is 2 to the power of 2. You can see that the exponent, or power, that 2 is raised by is always one less than the square number.

Square Power Value
1 0 2 to the power of 0 = 1
2 1 2 to the power of 1 = 2
3 2 2 to the power of 2 = 4
4 3 2 to the power of 3 = 8

Approach: Bit-shifting

def square(number):
    if number < 1 or number > 64:
        raise ValueError('square must be between 1 and 64')

    return 1 << number - 1


def total():
    return (1 << 64) - 1

For more information, check the bit-shifting approach.

Approach: Exponentiation

def square(number):
    if number < 1 or number > 64:
        raise ValueError('square must be between 1 and 64')

    return 2 ** (number - 1)


def total():
    return 2 ** 64 - 1

For more information, check the exponentiation approach.

Approach: pow

def square(number):
    if number < 1 or number > 64:
        raise ValueError('square must be between 1 and 64')

    return pow(2, number - 1)


def total():
    return pow(2, 64) - 1

For more information, check the pow approach.

Which approach to use?

  • Bit shifting is the fastest for square.
  • Bit shifting and exponentiation are about the same for total.
  • Exponentiation and pow are about the same for square.
  • pow is significantly the slowest for total.

For more information, check the Performance article.