In this challenge, you will do some simple graphics using Pygame. Later challenges will allow you to actually build full games using Pygame.

For this challenge, you need to show a ball moving across the screen, and when it hits a wall it bounces and continues moving in the new direction.

1. Download PyGame and install it. To check if it has installed properly, open a python command line (or the IDLE interface) and type

   import pygame

   If this gives you an error, your installation has not worked. If you don't see any error on screen, then the installation has been successful.

2. Read and understand the Pygame Introduction. Make sure you understand what is going on. Otherwise you will not be able to complete this challenge.

3. Try to create and run the 'bouncing ball animation' given in the Pygame introduction. You will need to do the following:

   • Create a file called bounce.py. Copy-n-paste the code from the Pygame introduction into bounce.py and save it
   • Download the image of the ball and save it in the same directory as 'bounce.py'.

   • Now when you try to run the program, it will probably give you an error like this:

     pygame.error: Couldn't open ball.bmp

   • Change the name of the image file in bounce.py to make this error go away

   • Now, the program will probably run, but the ball whizzes past the screen too fast. To slow down the game you'll need to use the 'tick' method of pygame.time.Clock. Basically, you'll need to insert this line at the beginning of your program:

     clock = pygame.time.Clock()

     and then you'll need to insert this line as the first line of code inside the while loop:

     clock.tick(60)

     this ensures that the game does not go faster than 60 frames per second.

Bonus challenge #1: Replace the 'ball' in this animation with the head of someone you dislike, taken from a photo. So, when this program is run, instead of a ball bouncing, you see someone's head bouncing

Bonus challenge #2: Modify this animation so that when the mouse is clicked on the ball (or photo from challenge #1), the animation ends (and the program exits). Check the documentation for pygame.event to see how you can do this. (Hint: you'll need to use the MOUSEDOWN event).

Challenge: Find the largest prime factor of the number 60085146 (the
answer is 193)

The prime factorization of 15 is 3 x 5. The largest prime factor of 15 is 5.
The prime factorization of 50 is 2 x 5 x 5. So the largest prime factor is 5.
The prime factorization of 100 is 2 x 2 x 5 x 5. So the largest prime
factor is 5.
The prime factorization of 42 is 2 x 3 x 7. So the largest prime factor is 7.

You have to find the prime factorization of the given number, and then
figure out which one is the largest.

To do this, we will use recursive functions. First revise your
concepts of function by reading Chapter 7 of the textbook
(http://www.ibiblio.org/swaroopch/byteofpython/read/functions.html).
After that get an idea of what a "recursive" function is by reading
this: http://www.greenteapress.com/thinkpython/html/book006.html#toc58
... to understand recursion you should also look at the first few
examples given here:
http://www.ibm.com/developerworks/linux/library/l-recurs.html

We'll do some exercises before we get to the main problem.

1. Finding the smallest factor of a number
Complete this function:

def smallest_factor(n):  '''This function returns the smallest number (greater than 2) that divides 'n'.  If n is a prime number, then, obviously the smallest number that divides  'n' will be 'n' itself. Hence in case of prime numbers, this function will   return n.'''  # write your code here

2. Finding a prime number
Complete this function:

def is_prime(n):  '''This function returns True if n is prime. Otherwise it returns False'''  # define your function here. Use the 'smallest_factor' function in your code.

3. Getting the prime factors of a number

def prime_factorization(n):  '''This function returns a list containing all the prime factors of n  If p1 is a prime number that divides n,   then we can write n = p1 x c1 (where c1 is simply n/p1, and it might  or might not be a prime number). In that case, we can say that the  prime factors of n = list consisting of p1 + prime factors of c1. This  idea is implemented in the code below. Make sure you understand the  code. If you don't, future python challenges will be difficult for you  to solve'''  p1 = smallest_factor(n)  if p1 == n:    return [n]  else:    return [p1] + prime_factorization(n/p1)

4. Getting the largest prime factor:

def largest_prime_factor(n):  '''returns the largest prime factor of n'''  # your code here

Now use this function to find the largest prime factor of 60085146.
(Note: the answer is 193)

Bonus quesiton #1: If a number 'n' is a prime_number, then the
smallest_factor function will check each value from 2 uptil n to see
which of them divides n. And will finally return n. However, please
note the following, if n is not divisible by any number less than
sqrt(n) (i.e. the square root of n), then n is guaranteed to be prime.
Hence, modify the smallest_factor function so that it only check from
2 until sqrt(n) and then stops. This functions will be much, much more
faster. Use google to figure out how to get the "sqrt" function in
python

Bonus question #2: Solve this challenge without using recursion. i.e.
in exercise #3, the prime_factorization method works by calling
itself. Sometimes, this might not be the most efficient way of
implementing a function. Can you do it without using recursion. i.e.
rewrite the function so that it does not call itself. (Hint: you'll
need to use a while loop or a for loop for this purpose. You might
have to use a list.)

Challenge: Find the largest palindromic number which is a product of two three digit numbers. (The answer is 906609)

A palindromic number is one that is the same if you reverse its digits. For example, 12321 is a palindrome. But 12345 is not a palindrome (because it's reverse 54321 is not the same as 12345.)

Note that 1001 is a palindrome and it can be written as the product of 2 two-digit numbers: 91*11. What is the largest such number? The answer is: 9009 = 91*99.

For this challenge you have to find the largest number which is a palindrome and can be written as a product of two three digit numbers.

Please note that this is problem 4 of Project Euler: http://projecteuler.net/index.php?section=problems&id=4

For this, you will be using python 'functions'. These are covered in Chapter 7 of the text: http://www.ibiblio.org/swaroopch/byteofpython/read/functions.html. Please read and understand this chapter before trying this challenge.

First we'll define a few helper functions that you will need later. Don't worry too much about how they work. Just understand what they do, so that you'll know how to use them in your own code.

The first helper function is:

def int_to_string(i):    '''This function converts the number i to a string of characters    Thus if you pass in the number 23, it will return the string "23"    The difference between the two is this: you can do mathematical    operations (like * / + - ** etc) on numbers and you cannot do them    on strings. Conversely, you can do string operations (like reverse,     join (i.e. concatenate)), which cannot be done on numbers    Examples:    >>> int_to_string(23)    '23'    >>> x = int_to_string(1234)    >>> x    '1234'    >>> x[0]    '1'    >>> x[1]    '2'    The last two examples show that its easy to extract the digits    of a number by first converting it to a string.     Don't worry if you don't understand what str(i) below means.    str(i) is an in-built python method.    '''    return str(i)

The second helper function is:

def reverse_string(s):    '''Takes a string and returns a reverse of that string    Examples:    >>> reverse_string('abcde')    'edcba'    >>> s1='nitin'    >>> s2=reverse_string(s1)    >>> s2    'nitin'    >>> s1==s2    True    >>> p1=int_to_string(34)    >>> p2=reverse_string(p1)    >>> p2    '43'    Don't worry if you don't understand what s[::-1] really means    and how it works. It is an advanced topic in lists.    '''    return s[::-1]

And the third helper function is:

def is_palindrome(str1):    '''Return True if str1 is a palindrome, and False if it is not    You should understand this code, and how/why it works.'''    return str1 == reverse_string(str1)

The next helper function is also your first exercise. I've left this function incomplete. You have to complete it so that it does what it claims to do.

def is_number_a_palindrome(num):    '''This function should return true if num is a palindromic number, False otherwise    This is similar to the is_palindrome function above, but is_palindrome    expects a string, and num is a number.    You have to complete the code for the function.    You can (actually, you should) use the 'is_palindrome' function    '''    ## Your code goes here

Now comes your main challenge. Today is your lucky day. I've written most of the code for this challenge. I've just missed out a little bit - you just have to complete that, and your challenge is done.

def find_largest_palindromic_product():    '''You have to complete this function    This function is intentionally not commented'''    max = 0    for i in range(100, 999):        for j in range(100, 999):            p = i*j            ### your code goes here    return max

Bonus question #1: Rewrite the find_largest_palindromic_product function so that it does not use any of the helper functions. Which means that the code that is contained in the helper functions will now have to be directly written in the find_largest_palindromic_product function. Can you do it?

Bonus question #2: Figure out how many times does your program compute a product of two 3-digit numbers? Re-write the function so that this figure becomes half (or less). i.e. the number of times your new program computes a product of two 3-digit numbers should be less than half of the corresponding number for your old program.

You get 0.5 points: If you manage to write a python program that gets the correct answer for the basic challenge, but your program is badly written (i.e. it is difficult to understand, or it is unnecessarily confusing, or something else is particularly bad about the program).
You get 1 points: if you write a program that is correct, as well as easy to understand. This is important. Writing good programs, that others can understand easily, is as important as writing correct programs.
Each challenge has two bonus questions.
You get a additional 1 point for solving bonus question #1.
You get an additional 2 points for solving bonus question #2.

Challenge: Find the sum of all the even numbers in the fibonacci sequence that do not exceed 4 million. (This is problem #2 of Project Euler: http://projecteuler.net/index.php?section=problems&id=2). The correct answer is 4613732.

Remember the fibonacci sequence (http://en.wikipedia.org/wiki/Fibonacci_number) is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Here, each subsequent number of the sequence is generated by adding up the previous two numbers.
You have to find the sum of all the even numbers in this sequence that are less than 4 million:
i.e. 2+8+34+144+.....

The challenge for this time is based on understanding lists. It is covered, briefly, in http://www.ibiblio.org/swaroopch/byteofpython/read/list.html

However, that is not enough. So, here are preliminary exercises to teach you some basics of lists (and to lead you towards the solution)

1.

x = [1,2,3,4,5]
print x

Here [1,2,3,4,5] represents a list containing the first five numbers. Once you say x=[1,2,3,4,5], then after this point, you can use x to represent the entire list. 'print x' simply prints that list.

2.

 x = [1,2,3,4,5]
 for y in x:
    print y

What will this print?
3.

 x = range(1,6)
 for y in x:
     print y
 

How is this different from #2?

Actually it is no different. "range(a,b)" represents the list [a, a+1, a+2, ..., b-1]. Note: the range ends at b-1, not at b. But otherwise you can use it anywhere you use a list. In challenge #2 (http://pythonchallenges.posterous.com/python-beginners-challenge-2-control-flow-if) you've already used this feature.

4.

x = range(15,21)
print x[0]
print x[1]
print x[5]
print x[-1]
print x[-2]

Try out this code and try to guess what is going on. Note, x represents the list [15, 16, 17, 18, 19, 20]. So x[0] is 15. Because x[0] represents the first element of list x. x[1] represents the second element (16) and so on. Hence x[5] represents the 6th element (20).

In addition, python also allows you to count backwards in the list. So x[-1] represents the last element (20). x[-2] represents the second-from-last element (i.e. 19).

5.

x = range(15,21)
x.append(22)
print x
x.append(100)
print x
x.append(1729)
print x

Have you figured out what x.append(y) does?

6.

x=[0,1]        # this represents a list with two items, 0 and 1
while x[-1]<100:
  next_number = x[-1] + x[-2]
  x.append(next_number)

After you execute this code, what does x contain? 'print x' at this point should show you something very familiar. And if you've understood exercises #1 to #5 properly, (and if you've understood the 'while loop' (from http://www.ibiblio.org/swaroopch/byteofpython/read/while-statement.html)) then you should not have any trouble understanding what this code is doing.

Now, it should be easy for you to create a fibonacci sequence of all fibonacci numbers less than 4000000. And solving the challenge should be easy. By the way, the answer is: 4613732, so if you're getting something else, you're doing something wrong.

Bonus question #1: Compute the sum of all odd fibonacci numbers less than 4000000. If you get 10316619, you've made a mistake in your program. (If this happens, try inserting some print statements in your code to figure out what went wrong. For example, after you've constructed the fibonacci sequence, print it out to see if it is what you had expected it to be. Or, if you have a loop for adding numbers from your sequence, then do a print of that number at that point. You can then check to see if your program is adding the correct numbers.) The answer for this is also 4613732.

Bonus question #2: Write a single python mathematical expression that gives the n_th fibonacci number - without using a loop. Hint 1: Wikipedia is your friend. Hint 2: x**0.5 gives you the square root of x.

Note 1: I've intentionally used meaningless variable names of 'x' and 'y' etc. in my example code, because I don't want to make the exercises too easy for you. But in real python code, you should use meaningful variable names (or list names). For example fib=[0,1]... etc

Note 2: If you've done challenge #2 correctly, you should now be able to figure out how to decide whether a number is even or odd... If you haven't done challenge, then go back to doing that...

For this exercise, you're expected to have read Chapter 6 of our textbook (http://www.ibiblio.org/swaroopch/byteofpython/read/control-flow.html). Make sure you've understood the if statement and the for loop.

The challenge: What is the sum of all the multiples of 17 that are less than 1729. (Example: All the multiple of 3 that are less than 10 are 3, 6, and 9. Their sum is 18.) Note: The answer is 87567. So if you're getting a different answer, then your program is incorrect.

For that, here are some preliminary hints/exercises that will help you to write the python code to compute the answer.

At the python prompt, type the following expressions/code to see what it prints:

1.

range(1,11)

What will happen if you use range(1,1729)?

2.

i=25
if i%5 == 0:
  print 'divisible by 5'
else:
  print 'not divisible by 5'

What does this print? What happens if you change the 25 in the first line to 26? (Note: if you don't know what i%5 means then it is time to revise Chapter 5: Operators and Expressions: http://www.ibiblio.org/swaroopch/byteofpython/read/operators-expressions.html

3.

sum=0
for i in range(1,11):
    sum += i

--------

Now, based on the examples in code snippets #1, #2, and #3, you should know enough to be able to write python code that will compute the sum of all numbers less than 1729 that are divisible by 17.

Bonus question #1: Change your python program to compute the sum of all numbers less than 1729 that are divisible by 11 or 17. Note #1: this problem is equivalent to problem #1 of Project Euler: http://projecteuler.net/index.php?section=problems&id=1  Note #2: The correct answer is 215585. If you get 224000, you are making a mistake in the logic of your program. (If you cannot understand why 224000 i wrong, try this simpler problem first - Sum of all the numbers less than or equal to 10 which are divisible either by 2 or by 3 is how much? Answer: 42. If you get 48, you're making a mistake...)

Bonus question #2: Can you compute the answer without using a for loop? i.e. by simply writing a single arithmetic expression that gives the correct answer? Hint 1: Google for 'triangular numbers'. Hint 2: What does the expression n*(n+1)/2 represent?

For all these challenges, you're expected to submit the python code that you used to do the computation.

This is the first in a series of challenges that are intended to be interesting to someone who doesn't know python and is learning. Existing tutorials and exercises on the net assume that just because you don't know python, you're an idiot. Here, we assume that you are smart, and would love an interesting challenge while you learn python. This blog is inspired by http://codeblog.dhananjaynene.com/ and http://projecteuler.net/ but those require you to be already good at python.

After you complete each challenge, you get the next one. Each subsequent challenge requires you to learn a little more about python. These challenges don't teach you anything about python. That you have to do on your own, mainly by reading (http://www.ibiblio.org/swaroopch/byteofpython/read/) but you're free to use google and read whatever tutorials/resources on python you can find to be able to do this.

This assumes that you already have a python interpreter installed and can run it. We also assume that you've read up to Chapter 5 of website/textbook given above. Specifically, the most useful you'll find is this page: http://www.ibiblio.org/swaroopch/byteofpython/read/operators.html

Challenge 1.
See this python interpreter session:
    >>> 4+4-4-4
    0
Basically, I typed the expression '4+4-4-4' and got an answer of 0.

Your challenge is to similarly use four 4s to get each of the numbers from 1 to 10.
i.e. Basically write an expression with four 4s whose value is 1, another whose value is 2, and so on.
You are allowed to use standard mathematical operators, parantheses, and the dot ('.').

For additional bonus, try to get the following numbers: 10000000000, 1024.

Note 1: Most of the material you need for doing this challenge is in Chapter 5 of the book/webpage referenced above
Note 2: For the purposes of this challenge, 1024.0 is the same as 1024.
Note 3: If you get stuck and are not able to get the number 10, email me for a hint.

Note 4: Yes, you can use exponentiation. But even the expression in the exponent can contain only 4s. And those 4s also count towards your limit of four 4s.

Note 5: Don't forget the '.'  - it can come in very useful!

Bonus question: What's the most interesteing/bizarre/difficult number you can get using just four 4s