Problem 28

//package javaapplication1; /** Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows: 21 22 23 24 25 20  7  8  9 10 19  6  1  2 11 18  5  4  3 12 17 16 15 14 13 It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way? */ /**  * this is what one can write with poor tools  */ /**  * Timing: 1:01 am to 1:54 am  * @author umang  */ public class Problem28 {     /**      * @param args the command line arguments      */     public static void main(String[] args) {         int max = 1001;         int arr[][] = new int[max][max];         int x = max / 2;         int y = max / 2;         int count = 0;         int increment = 2;         // initialize first square         arr[x][y] = count++;         arr[x][y++] = count++;         arr[x++][y] = count++;         arr[x][y--] = count++;         arr[x][y--] = count++;         arr[x--][y] = count++;         arr[x--][y] = count++;         arr[x][y++] = count++;         //arr[x][y++] = count++;         //arr[x][y++] = count++;         //   y++;         //System.out.println(x + " " + y + " " + count + " " + increment);         while (x != 0 && y != 1) {             increment++;             //  System.out.println("start " + x + " " + y + " " + count + " " + increment);             for (int i = 0; i < increment; i++) {                 arr[x][y++] = count++;                 //y++;             }             y--;             x++;             //System.out.println(x + " " + y + " " + count + " " + increment);             for (int i = 0; i < increment; i++) {                 arr[x++][y] = count++;                 //    System.out.println(x + " " + y + " " + count + " " + increment);             }             x--;             y--;             increment++;             //System.out.println(x + " " + y + " " + count + " " + increment);             for (int i = 0; i < increment; i++) {                 arr[x][y--] = count++;             }             x--;             y++;             ///System.out.println(x + " " + y + " " + count + " " + increment);             for (int i = 0; i < increment; i++) {                 arr[x--][y] = count++;             }             x++;             y++;             //System.out.println("end" + x + " " + y + " " + count + " " + increment);         }         for (int i = 0; i < increment; i++) {             arr[x][y++] = count++;         }      /*   for (int i = 0; i < arr.length; i++) {             for (int j = 0; j < arr[i].length; j++) {                 System.out.printf("%2d ", arr[i][j]);             }             System.out.println("");         }*/         int sum = 0;         for (int i = 0; i < arr.length; i++) {             //   System.out.println(arr[i][i] + " ");             sum += arr[i][i];         }         int row = 0;         for (int i = arr.length - 1; i >= 0 && row < arr.length; i--, row++) {             if (row != i) {                 sum += arr[row][i];             }         }         System.out.println("sum is " + sum);     } }

Refactoring code-1 - breaking complex if...else to simple structure

In order to show how I broke down nested if...else structure into smaller, more manageable pieces, I have to show it with an example. The example might be technology specific but person with a little experience will be able to figure out what I did-and how the very same thing could be done with his/her programming language.

I was working on a web based application on PHP and CodeIgniter framework. Application was simple in the beginning. Admin could do certain things. Obviously the user should be allowed only after logging in through the admin login. If the login was successful the we set certain things in the session. All the admin pages should be accessible only after logging in to the system. I thought of some solution that was like "Aspect Oriented Programming" (or AOP) that i was used to do with Java(Spring AOP / AspjecctJ). The very same thing could be achieved in the CodeIgniter framework through what they call hooks.

We would be seeing the same hook that my team mate wrote and later I refactored for better maintainability (we will take it as an example in order to understand the technique).

We created a controller "login_check" and a method named "checkLogin". The checkLogin function from "login_check" class was invoked before any controller(the entry needed to be made in the hooks.php in application/config in php-CodeIgniter project). By doing this we saved ourselves from writing if/else on all the pages in the admin part.

(This method is executed before any controller - controller method execution)

The class looked something like shown in the snippet-1:
It is a normal CodeIgniter controller with a constructor. The line 11 (in code snippet-1) checks if the class(controller in this case) is 'authenticate' (the method check_login is executed before doing anything in the actual controller.) If the class is the authenticate (the one that renders the form) then we should not be redirecting him/her to the login (through appropriate route) (otherwise it would send us in a redirection loop that does not end). If the user has requested login page or anything that has anything to do with authenticate then we are not redirecting the user(eg if the button click on login page invokes a method from authenticate controller indirectly).

On the line 12 in the snippet-1 we get the CodeIgniter instance that is required in order to access the session.

And on the line 13 we check if the session is set and if not set then we redirect the visitor the the login page.

All the pages for admin were with URI "admin/".

Things we good enough so far. Then we started implementing the Student part. Now we were required to write the pages for Student as well. Student also could see pages only after he/she is authenticated. The student can not see pages for admin that is the student can not see the pages for which he/she is not authorized.

Now we had to write the code that would check if the user is logged in or not also we also had to make sure that the user is accessing the intended pages only(that is admin is accessing pages of admin and the student is accessing the pages of student only). If the student tried to see the pages of admin then he was to be redirected to his home page (that is URI "/student").

Also if the user had requested any URI starting with student/* as was not authenticated then we had redirect the user to user's login page of student. Same way if the user tries to access anything with URI matching :admin/*" then we had to redirect the user to admin's login page.

The code looked as shown in Snippet-2.



To understand what is happening here we need to first know the method _get_root_directory_requested() (that I have written in snippet-2). This method returns the top level directory name from the requested URI (if if user has requested '/admin/students/edit/1' then the method would return 'admin'). That method helped in keeping the "checkLogin" function smaller.

The line 24 in snippet-2 does the same thing discussed earlier.
Then on the line 26 we get the requested directory(eg admin,student).
On line 27 we check if the user is logged in as admin and he has requested for /. In this case we redirect him to admin/dashboard.
On line 42 we redirect the user to student/dashboard if the student has logged in and trying to access / URI.

On line 38 we redirect the user to appropriate login page depending on the top level directory he has requested. And on the 45 onward we redirect the student to student/dashboard and admin to admin/dashboard if he/she is trying to access un-authorized pages.

This also worked fine so far. After this we were asked to write the Super-Admin feature. In super admin we had to create a user who could manage the administrators. This introduced the third User-Type. We had to check the very same things discussed above(that is user should be given access to pages for which he/she is authenticated and authorized).

Because of the third user being added I though of adding some more if...else to make the things work. But if I had done it, it would make the function even bigger^[1] and difficult to read and in-turn difficult to maintain. Also the function will not be visible on the screen once on normal displays.

So i applied some refactoring to it. After doing it the code looked as it is shown in scnippet-3.



The method '_get_root_directory_requested' stays as it was in the previous snippet and does the same thing.
checkLogin is the method which would be invoked and it would invoke other methods in order to perform its task.

We would now see what changes I did in order to make things easier to read and maintain.

The line 36 checks if the controller before which the method is invoked is not one of authentication controller. We have replaced a complex condition with a method call. We placed the complex condition inside a method call that is easier to read as well as easier to maintain^[1].  The complex condition with two 'and' was encapsulated inside a method named '_is_authentication_controller'. This can also be seen as an abstraction we built. It prevents us from getting to the actual detail of names of the controllers. We can just use the method. We are not required to go into the details. In future if new controller for authentication is added (in case of new user being added) then we would be easily able to make the changes.

At line 39 we call a method that checks for login in the session. It returns true if user is logged in and false if the user is not logged in. On the line 40 we get the user type that is logged in. On the line 41 we call method "_authorize_for_url_with" with argument of user type that we have got from previous line.

The method "_authorize_for_url_with" redirects the user to appropriate path if the user is not authorized for the URI and the method does nothing if user is trying to access intended pages.

In the Else part at line 45 we call the method "_redirect_to_appropriate_login" which redirects the user to the login page. The user is redirected to the URI "student/" if the user has requested for "/" URI. This method uses the "Direct Access Tables^[2]"(the array- or the data-structure that holds the details is constructed in the constructor at line 20)(although the data-structure would vary according to the language but the concept would remain the same. You could also put that in a method if you wish.). This method relies on the values in the associative array. The key is top directory requested or user-type(ed admin,student,etc) and the value is the page to which the user needs to be redirected in order to login.

Here in this case the length of method was reduced be introducing some methods. In this structure if a new user type is added then we just need to add its entry in the constructor and add its controller class name to method "_is_authentication_controller". No other changes needs to be done on other part. This makes the class more flexible and ready to adopt new user types.

Although I have made some assumption while writing which you can read in the comments written at the top of the class in snippet-3.

This is the first time i have tried writing something. I have started noticing some problems already; but however I am publishing this post. ;) I hope it is entertaining.

References:
[1] Clean Code: A Handbook of Agile Software Craftsmanship by Robert C. Martin (ISBN: 0132350882 )
[2] Code Complete: A Practical Handbook of Software Construction, Second Edition By Steve McConnell (ISBN: 0735619670 )

Amicable Number

import java.util.ArrayList; /**  * @author Umang  */ /**  * Let d(n) be defined as the sum of proper divisors of n   * (numbers less than n which divide evenly into n).  *   * If d(a) = b and d(b) = a, where a  b, then a and b are an amicable pair   * and each of a and b are called amicable numbers.  *   * For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44,   * 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4,   * 71 and 142; so d(284) = 220.  *   * Evaluate the sum of all the amicable numbers under 10000.  */ public class Problem21 {     private static boolean isAmicable(int no)     {         long sum = sum(getEvenDivisors(no));         long no2 = sum(getEvenDivisors(sum));         return no == no2 && sum != no;     }     private static long sum(ArrayList<Long> numbers)     {         long ans = 0;         for (Long number : numbers)         {             ans += number;         }         return ans;     }     private static ArrayList<Long> getEvenDivisors(long n)     {         long root = Math.round(Math.sqrt(n)) + 1;         ArrayList<Long> test = new ArrayList<Long>();         test.add(1L);         for (long i = 2; i <= root; i++)         {             if (n % i == 0)             {                 test.add(i);                 test.add(n / i);             }         }         return test;     }     public static void main(String[] args)     {         long sum = 0;         for (int i = 0; i < 10000; i++)         {             if (isAmicable(i))             {                 sum = sum + i;             }         }         System.out.println("Sum = " + sum);     } }

Circular Primes

package javaapplication3; import java.util.ArrayList; /**  * The number, 197, is called a circular prime because all rotations of the  * digits: 197, 971, and 719, are themselves prime.  *  * There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71,  * 73, 79, and 97.  *  * How many circular primes are there below one million?  */ /**  * @author Umang  */ public class Problem35 {     public static ArrayList<Long> getDigits(long no)     {         ArrayList<Long> numbers = new ArrayList<Long>();         long temp = no;         while (temp > 0)         {             numbers.add(temp % 10);             temp /= 10;         }         return numbers;     }     private static int getCount(long no)     {         ArrayList<Long> numbers = getDigits(no);         return numbers.size();     }     public static long sumOfFactorialOfEach(ArrayList<Integer> numbers)     {         long sum = 0;         for (int no : numbers)         {             sum += factorial(no);         }         return sum;     }     static boolean isPrime(long n)     {         //check if n is a multiple of 2         if (n % 2 == 0)         {             return false;         }         //check the odds         for (long i = 3; i * i <= n; i += 2)         {             if (n % i == 0)             {                 return false;             }         }         return true;     }     static String rotate(String number)     {         return number.subSequence(1, number.length()) + "" + number.charAt(0);     }     private static long factorial(long no)     {         return no == 1 ? 1 : no * factorial(no - 1);     }     static boolean checkRotationsAndPrime(long no)     {         boolean allPrimes = true;         String strNo = new Long(no).toString();         int rotations = getCount(no);         for (int i = 0; i < rotations; i++)         {             if (!isPrime(new Long(strNo)))             {                 allPrimes = false;             }             strNo = rotate(strNo);         }         return allPrimes;     }     public static void main(String[] args)     {         long count = 0;         for (int i = 1; i <= 1000000; i++)         {             if (checkRotationsAndPrime(i))             {                 count++;             }         }         System.out.println("\nCount is " + count);     } }

Problem 18

package javaapplication3; import java.io.File; import java.io.FileNotFoundException; import java.util.LinkedList; import java.util.Scanner; import java.util.StringTokenizer; /**  * By starting at the top of the triangle below and moving to adjacent numbers  * on the row below, the maximum total from top to bottom is 23.  *  *    3  *   7 4  *  2 4 6  * 8 5 9 3  *  * That is, 3 + 7 + 4 + 9 = 23.  *  * Find the maximum total from top to bottom of the triangle below:  *  *                        75  *                      95 64  *                     17 47 82  *                   18 35 87 10  *                 20 04 82 47 65  *               19 01 23 75 03 34  *              88 02 77 73 07 63 67  *             99 65 04 28 06 16 70 92  *           41 41 26 56 83 40 80 70 33  *         41 48 72 33 47 32 37 16 94 29  *        53 71 44 65 25 43 91 52 97 51 14  *      70 11 33 28 77 73 17 78 39 68 17 57  *    91 71 52 38 17 14 91 43 58 50 27 29 48  *  63 66 04 68 89 53 67 30 73 16 69 87 40 31  * 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23  *  * NOTE: As there are only 16384 routes, it is possible to solve this problem by  * trying every route. However, Problem 67, is the same challenge with a  * triangle containing one-hundred rows; it cannot be solved by brute force, and  * requires a clever method! ;o)  */ /**  *  * @author Umang  */ public class Problem18 {     /**      * get the file content from given location      * @return file content in string format      */     private static String getFileContent()     {         StringBuilder content = new StringBuilder("");         File aFile = new File("D:/input.txt");         Scanner aScanner = null;         try         {             aScanner = new Scanner(aFile);         }          catch (FileNotFoundException ex)         {             System.out.println("File could not be readed");             ex.printStackTrace();;             System.exit(0);         }         while (aScanner.hasNextLine())         {             content = content.append(aScanner.nextLine() + "\n");         }         return content.toString();     }     /**      * gets the numbers in format of  LinkedList<LinkedList<Integer>>      * @return  LinkedList<LinkedList<Integer>> from the ifile      */     private static LinkedList<LinkedList<Integer>> getList()     {         LinkedList<LinkedList<Integer>> result = new LinkedList< LinkedList< Integer>>();         String content = getFileContent();         StringTokenizer lineTokenizer = new StringTokenizer(content, "\n\r");         while (lineTokenizer.hasMoreTokens())         {             LinkedList<Integer> row = new LinkedList<Integer>();             StringTokenizer numberTokenizer = new StringTokenizer(lineTokenizer.nextToken(), " ");             while (numberTokenizer.hasMoreTokens())             {                 Integer no = new Integer(numberTokenizer.nextToken());                 row.add(no);             }             result.add(row);         }         return result;     }     /**      *       * @param rows is the LinkedList<LinkedList<Integer>> where everything is stored      * @param row_no is the row number      * @param col_no is the column number      * @return the actual number at given row and column from LinkedList<LinkedList<Integer>>      * @throws Exception if no number is found in the list (assuming that the       * number is never 0 in the list)      */     public static int get_item_at(LinkedList<LinkedList<Integer>> rows, int row_no, int col_no) throws Exception     {         int no = 0;         int row_count = 0;         int col_count = 0;         for (LinkedList<Integer> row : rows)         {             col_count = 0;             for (Integer number : row)             {                 if (row_no == row_count && col_count == col_no)                 {                     no = number;                     break;                 }                 col_count++;             }             row_count++;         }         if (no == 0)         {             throw new Exception("No such item");         }         return no;     }     public static void main(String[] args) throws Exception     {         LinkedList<LinkedList<Integer>> numbers = getList();         System.out.println("Ans is " + getHighestSumFromList(numbers, 0, 0));     }     private static int getHighestSumFromList(LinkedList<LinkedList<Integer>> rows, int row, int col) throws Exception     {         int currunt_no = get_item_at(rows, row, col);         int mul_left = 0;         int mul_right = 0;         try         {             mul_left = getHighestSumFromList(rows, row + 1, col)  + currunt_no;             mul_right = getHighestSumFromList(rows, row + 1, col + 1)  + currunt_no;         }          catch (Exception e)         {             // if at the end of the list then return the currunt value              return get_item_at(rows, row, col);         }         int bigger_number =  mul_left > mul_right ? mul_left : mul_right;         return bigger_number;     } }