========================================================================================= ______ _ _____ _ _ | ____| | | | __ \ | | | | | |__ __ _| |_ _ __ __ _ | |__) | __ ___ | |__ | | ___ _ __ ___ ___ | __| \ \/ / __| '__/ _` | | ___/ '__/ _ \| '_ \| |/ _ \ '_ ` _ \/ __| | |____ > <| |_| | | (_| | | | | | | (_) | |_) | | __/ | | | | \__ \ |______/_/\_\\__|_| \__,_| |_| |_| \___/|_.__/|_|\___|_| |_| |_|___/ ========================================================================================= Here are some more challenging algorithmic problems that are great for practice towards final examinations and final projects. You are encouraged to try as many as possible of them in order to learn how to program - this is the only way to gain programming experteise !!! The solutions of these are currently not available, but we may provide solutions to some of them at the end of the semester. ----------------------------- PROBLEM A1 ----------------------------- Download the following two text files (famous English books) http://www.samyzaf.com/braude/PYTHON/projects/jude.txt http://www.samyzaf.com/braude/PYTHON/projects/oliver_twist.txt Write a Python function letter_frequency(file) for counting English letters frequency in a text file. Your program output should look like: oliver_twist.txt frequency: a: 0.076604 b: 0.014013 c: 0.023012 d: 0.045420 e: 0.124753 f: 0.019366 g: 0.020698 h: 0.065341 i: 0.062343 j: 0.000870 .... z: 0.000423 A: 0.002227 B: 0.001085 C: 0.000751 D: 0.000504 E: 0.000583 F: 0.000451 G: 0.000499 .... Z: 0.000002 The frequency of a letter is defined as the ratio between the number of its occurrences and the total number of letters in the text (make sure to ignore characters that are not English letters!). (a) Print the frequency tables for the two books. (b) Do you notice any similarities between the two tables? Hints: - Import the string module and look at string.lowercase and string.uppercase fields of the string module. - Use a dictionary to hold a mapping between a letter and its number of occurrences. ----------------------------- PROBLEM A2 ----------------------------- Explain what exactly happens in the following code? def random_cipher(): letters = string.lowercase + string.uppercase L = list(letters) random.shuffle(L) cipher = dict() for letter in letters: cipher[letter] = L.pop() return cipher (a) Use a cipher object for encrypting a simple text file. Here is a start of your Python function: def file_encrypt(file, outfile, cipher): letters = string.lowercase + string.uppercase f1 = open(file, 'r') f2 = open(outfile, 'w') ... The file_encrypt function takes a soure file, a target file, and a cipher dictionary. It translates each letter in the source file to its corresponding cipher[letter]. (b) Download the encrypted file: http://www.samyzaf.com/braude/PYTHON/projects/decrypt_me.txt This file was generated by applying the function file_encrypt on a very famous English book by a secret cipher object. Can you use the ideas in problem A1 in order to decrypt this book and its secret cipher? Hints: Start with a utility: find_closest(x, list_of_floats) which finds the closest value in list_of_floats to x. ----------------------------- PROBLEM E1 ----------------------------- Project Euler: http://projecteuler.net Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms ----------------------------- PROBLEM E2 ----------------------------- Project Euler: http://projecteuler.net A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99. Find the largest palindrome made from the product of two 3-digit numbers. ----------------------------- PROBLEM E3 ----------------------------- Project Euler: http://projecteuler.net A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a**2 + b**2 = c**2 For example: 3**2 + 4**2 = 9 + 16 = 25 = 5**2 There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product a*b*c. ----------------------------- PROBLEM E4 ----------------------------- Project Euler: http://projecteuler.net 2**15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 2**1000? ----------------------------- PROBLEM E5 ----------------------------- Project Euler: http://projecteuler.net The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? ----------------------------- PROBLEM E6 ----------------------------- Project Euler: http://projecteuler.net In the 20x20 grid below, four numbers along a diagonal line have been enclosed in brackets: [26], [63], [78], [14]. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 [26] 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 [63] 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 [78] 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 [14] 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 The product of these numbers is 26 * 63 * 78 * 14 = 1788696. What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in this grid? ----------------------------- PROBLEM E7 ----------------------------- Project Euler: http://projecteuler.net The following problem is a potential candidate for a midterm or final project. At its current level, it is still a reasonable problem for practice. In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way: * High Card: Highest value card * One Pair: Two cards of the same value * Two Pairs: Two different pairs * Three of a Kind: Three cards of the same value * Straight: All cards are consecutive values * Flush: All cards of the same suit * Full House: Three of a kind and a pair * Four of a Kind: Four cards of the same value * Straight Flush: All cards are consecutive values of same suit * Royal Flush: Ten, Jack, Queen, King, Ace, in same suit The cards are valued in the order: 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king, ace (in some Poker versions the rank of suites is also counted. The rank of suites from lower to higher is: S=Spades, H=Hearts, D=Diamonds, C=Clubs) * If two players have the same ranked hands then the rank made up of the highest value wins. For example: a pair of eights beats a pair of fives (see example 1 below). * But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below) * If the highest cards tie then the next highest cards are compared, and so on. * Consider the following five hands dealt to two players: +------+-------------------+---------------------+----------+ | Hand | Player 1 | Player 2 | Winners | +------+-------------------+---------------------+----------+ | 1 | 5H 5C 6S 7S KD | 2C 3S 8S 8D TD | Player 2 | +------+-------------------+---------------------+----------+ | | Pair of Fives | Pair of Eights | | +------+-------------------+---------------------+----------+ +------+-------------------+---------------------+----------+ | 2 | 5D 8C 9S JS AC | 2C 5C 7D 8S QH | Player 1 | +------+-------------------+---------------------+----------+ | | Highest card Ace | Highest card Queen | | +------+-------------------+---------------------+----------+ +------+-------------------+---------------------+----------+ | 3 | 2D 9C AS AH AC | 3D 6D 7D TD QD | Player2 | +------+-------------------+---------------------+----------+ | | Three Aces | Flush with Diamonds | | +------+-------------------+---------------------+----------+ +------+-------------------+---------------------+----------+ | 4 | 4D 6S 9H QH QC | 3D 6D 7H QD QS | Player1 | +------+-------------------+---------------------+----------+ | | Pair of Queens | Pair of Queens | | +------+-------------------+---------------------+----------+ | | Highest card Nine | Highest card Seven | | +------+-------------------+---------------------+----------+ +------+-------------------+---------------------+----------+ | 5 | 2H 2D 4C 4D 4S | 3C 3D 3S 9S 9D | Player1 | +------+-------------------+---------------------+----------+ | | Full House | Full House | | +------+-------------------+---------------------+----------+ | | With Three Fours | with Three Threes | | +------+-------------------+---------------------+----------+ The file: http://www.samyzaf.com/braude/PYTHON/projects/poker.txt contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that - all hands are valid (no invalid characters or repeated cards) - each player's hand is in no specific order - in each hand there is a clear winner How many hands does Player 1 win? ----------------------------- PROBLEM E8 ----------------------------- Project Euler: http://projecteuler.net The following problem is also a potential basis for a midterm or final project. SuDoku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of SuDoku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid. SUDOKU PUZZLE SOLUTION +-------+-------+-------+ +-------+-------+-------+ | 0 0 3 | 0 2 0 | 6 0 0 | | 4 8 3 | 9 2 1 | 6 5 7 | | 9 0 0 | 3 0 5 | 0 0 1 | | 9 6 7 | 3 4 5 | 8 2 1 | | 0 0 1 | 8 0 6 | 4 0 0 | | 2 5 1 | 8 7 6 | 4 9 3 | +-------+-------+-------- --------+-------+-------+ | 0 0 8 | 1 0 2 | 9 0 0 | | 5 4 8 | 1 3 2 | 9 7 6 | | 7 0 0 | 0 0 0 | 0 0 8 | | 7 2 9 | 5 6 4 | 1 3 8 | | 0 0 6 | 7 0 8 | 2 0 0 | | 1 3 6 | 7 9 8 | 2 4 5 | +-------+-------+-------- ----------------+-------+ | 0 0 2 | 6 0 9 | 5 0 0 | | 3 7 2 | 6 8 9 | 5 1 4 | | 8 0 0 | 2 0 3 | 0 0 9 | | 8 1 4 | 2 5 3 | 7 6 9 | | 0 0 5 | 0 1 0 | 3 0 0 | | 6 9 5 | 4 1 7 | 3 8 2 | +-------+-------+-------+ +-------+-------+-------+ A well constructed SuDoku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction. The 6K text file: http://www.samyzaf.com/braude/PYTHON/projects/sudoku.txt contains fifty different SuDoku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above). By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above. ----------------------------- PROBLEM E9 ----------------------------- Project Euler: http://projecteuler.net Some positive integers n have the property that the sum n + reverse(n) consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n). There are 120 reversible numbers below one-thousand. How many reversible numbers are there below one-billion (109)? ----------------------------- PROBLEM E10 ----------------------------- Project Euler: http://projecteuler.net A Hamming number is a positive integer which has no prime factor larger than 5. So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. There are 1105 Hamming numbers not exceeding 10**8. We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n. Hence the Hamming numbers are the generalised Hamming numbers of type 5. How many generalised Hamming numbers of type 100 are there which don't exceed 10**9?