In Python 3

Exercise 4: Cake cutting (Challenging) Source: This exercise is a modified version of one of Google's own coding exams, used to recruit new software developers each year. The setup: Happy Birthday! We brought some cake to celebrate! You take one look at your cake, and see the writing on it is representable as a string, abcabcabcabc. How to make everyone at your party happy cut the cake such that everyone gets (1) the same number of letters, (2) the same sequence of letters as everyone else, and (3) you've cut your cake into the maximum number of pieces possible. So, for this cake, we can obviously split it into four pieces, each containing abc . Note: sequences are not interchangeable, so bca is not the same as abc. Your task: given an arbitrary cake, find the maximum number of pieces we can cut it into, i.e. the number of friends you can share your cake with. Here are the steps. You work out the code. (There are other ways to do this. Feel free to go your own way!) 1. Find the potential ways you can cut the cake. You cannot have fractions of letters. For example. Suppose the cake was 12 letters long cake = 'abccbaabccba'. You could cut it up into 1, 2, 3, 4, 6, or 12 pieces. Notice that you can divide by 12 by each of these numbers and not have a remainder. Store your potential cake-piece lengths in a list named piece_lengths 2. For each potential piece length: A. Cut the first piece from the cake. (Hint: you can slice a string.) Given our example, if piece length = 1, then the first piece would be 'a'. B. Create a string that is made up of the piece you cut repeated until it has the same length as the cake. In our example, we would repeat 'a' 12 times: test_cake = 'aaaaaaaaaaaa'. If we used piece length = 2, we would repeat 'ab' six times and have test_cake='abababababab'. C. Compare your test cake to the cake. If they are the same, then this is a successful cutting strategy, Keep this piece length --- save it to a list. If the cake and test cake are not the same, move on to the next potential piece length. In our example, 6 is the only piece length that works. In general, there may be many piece lengths that work. 3. From your list of acceptable piece lengths, choose the shortest. Report the length of the piece and the number of pieces you can cut the cake into. Test your algorithm with test_1 = 'abccbaabccba' test_2 = 'abcabcabcabc