Magic Squares

According to Wolfram Math World, a magic square is "a square array of numbers consisting of the distinct positive integers 1, 2, ..., arranged such that the sum of the numbers in any horizontal, vertical, or main diagonal line is always the same number ".

From the same source, another interesting property of a magic square is that "if every number in a magic square is subtracted from , another magic square is obtained called the complementary magic square."

This time, though, we would like to present our own "magic square". This magic square does not comply with the requirements to strictly be called magic square, but as it was very entertaining to create, we decided that it could be another type of magic square.

Can you tell from the following code how our magic square looks like?
MagicSquares.java

 1 public class MagicSquares
 2 {
 3     private static int nElementsPerLine;
 4     private static int startConstant;
 5     private static int endConstant;
 6     private static int element;
 7 
 8     public static void print(int n){
 9         element = n;
10         nElementsPerLine = 2 * element - 1;
11         startConstant = 0;
12         endConstant = 0;
13 
14         for(int line = 0; line < nElementsPerLine; line++)
15         {
16             if(line < element)
17             {
18                 startConstant = line;
19                 endConstant = nElementsPerLine - line;
20             }
21             else
22             {
23                 startConstant = nElementsPerLine - line - 1;
24                 endConstant = line + 1;
25             }
26 
27             for(int index = 0; index < nElementsPerLine; index++)
28             {
29                 if(index < startConstant)
30                 {
31                     System.out.printf("%3d", element);
32                     element--;
33                 }
34                 else if(index < endConstant)
35                 {
36                     System.out.printf("%3d", element);
37                 }
38                 else
39                 {
40                     element++;
41                     System.out.printf("%3d", element);
42                 }
43             }
44             System.out.println();
45         }
46     }
47 
48     public static void main(String[] args){
49         MagicSquares.print(3);
50     }
51 }
52 
53 

Hint:
Look for patterns of symmetry that are controlled by the variables startConstant and endConstant and the way they affect the output on each line.

Solution:
In this example, our magic square looks like this:

3 3 3 3 3 

3 2 2 2 3 

3 2 1 2 3 

3 2 2 2 3 

3 3 3 3 3

Variable elements is initialized with the value of 3 (line 49), then variable nElementsPerLine is initialized using the value of the variable elements: 2 * 3 - 1 = 5 (line 10). The first for cycle controls the number of lines and the nested for controls the appearance of the line, thus dictating the order in which the numbers are printed to build concentric squares given a value. To accomplish this, we have to look at how startConstant and endConstant change values throughout the main for cycle:
1. Whenever the number of the line we want to print is smaller than the element (line 16), the value of the variable startConstant will be equal to that line, the variable endConstant will be equal to the number of elements in that line minus the number of line, and from this, in the second cycle when the variable startConstant is zero (meaning that we are printing the first line)(line 29), the flow of the program jumps to the second condition. In ths condition (line 34), the element will be printed repeatedly the number of times that a line is allowed to grow (in this case 5).
2. When the variable startConstant is greater than zero and the variable endConstant begins to get smaller, the flow can enter the first condition on the second cycle. In this condition, the element will be printed once, decremented by one and continue like this until the condition becomes false (lines 29-32).
3. Once the first and second conditions on the nested cycle become false, the program will jump to the third condition (line 38), then it will increase by one the value of the element and print that value until it reaches the original value of the variable element.
4. From here, the process will start backwards and it will end when just the third condition of the second cycle is true.
5. In the last line of the magic square, only the third condition of the nested cycle will be true, therefore, the original element will be printed repeatedly again.

You can try with different values to test this code and tell us what you think in the comments.

Project Euler Problem 26

This week's puzzle comes from project euler, see the description of the puzzle here:
http://projecteuler.net/index.php?section=problems&id=26

Analysis

How do we find when a cycle occurs in the decimal representation of a unit fraction? The expansion of 1 divided by 14 is 0.0(714285), Let's see step by step what happens while expanding 1 divided by 14:

Note: dividend = previous remainder * 10

dividend	divisor	result	remainder
10	14	0	10
100	14	7	2
20	14	1	6
60	14	4	4
40	14	2	12
120	14	8	8
80	14	5	10
100	14	7	2
20	14	1	6
60	14	4	4
40	14	2	12
...	...	...	...

Note that the cycle re-started when the same remainder appeared (see numbers in red). I recommend you to try 1/17 = 0.(0588235294117647) to double check this behavior.

Here are a some additional facts that can help to find the solution:

1. If the remainder at some point is 0, the decimal representation of the unit fraction is finite.
2. For a unit fraction 1/d, the length of the cycle must be smaller than d, since there are at most d-1 possible remainders. As soon as we find a repeater remainder, we find the cycle.
3. Because the problem just requires d smaller than 1000, we can start verifying values of d in decreasing order. If at some point we find a cycle of length x, we know we do not need to check values of d smaller than or equal to x, because those values of d cannot create a larger cycle.

With all this in mind, here is the code I came up with.

 1 package cspuzzles;
 2 
 3 public class ProjectEuler26 {
 4     // We use this array to map from remainder to the first position where the
 5     // remainder was found. For example, for 1/14 = 0.0(714285)
 6     // indexOfRemainder[10] = 0;
 7     // indexOfRemainder[2] = 1;
 8     // indexOfRemainder[6] = 2;
 9     // indexOfRemainder[4] = 3;
10     // indexOfRemainder[12] = 4;
11     // indexOfRemainder[8] = 5;
12     // In this problem, we just need up to 1000 entries.
13     private int[] indexOfRemainder = new int[1000];
14 
15     private void solve(){
16         int d = 999; // we inspect values of d in decreasing order
17         int longestCycle = 1; // minimum value of d to inspect
18         int solution = -1;
19         int index = 0;
20         int remainder = 0;
21 
22         // This loop is to check possible values of d.
23         // When d is smaller than the longestCycle, there is no need
24         // to continue checking
25         while(d > longestCycle){
26             cleanMap();
27             // the initial numerator is 1, and this is also the
28             // initial remainder because we are working with unit fractions
29             remainder = 1;
30             index = 0;
31             // This loop is to find the cycle for a given value of d
32             while(remainder != 0) {
33                 // compute new remainder
34                 remainder = (remainder * 10) % d;
35                 // check if we have found a cylce
36                 if(remainder == 0){
37                     // there is no cycle
38                 }
39                 else if(indexOfRemainder[remainder] == -1){
40                     // first time we find this remainder
41                     indexOfRemainder[remainder] = index;
42                 }
43                 else {
44                     // THE CYCLE!!!
45                     // the length of the cycle is the current index minus
46                     // the index where the current remainder was previouly found
47                     longestCycle = index - indexOfRemainder[remainder];
48                     solution = d;
49                     remainder = 0; // break the while
50                 }
51                 index++;
52             }
53             d--;
54         }
55         System.out.println("Solution: " + solution);
56         System.out.println("Cycle length: " + longestCycle);
57     }
58 
59     private void cleanMap(){
60         for(int i = 0; i < indexOfRemainder.length; i++)
61             indexOfRemainder[i] = -1;
62     }
63 
64     public static void main(String[] args){
65         new ProjectEuler26().solve();
66     }
67 }

Do you like this kind of puzzles? Share your opinion in the comments.

Java Overloaded

Hey! For this puzzle, I need to use a class hierarchy. Instead of coding a small hierarchy inside the example; I will use the hierarchy of primitive wrapper classes like Interger, Short, Long, Byte. These classes inherit from class Number, which in turn inherits from Object. Given said that, here is the puzzle, what does the following code print? Do you think it even compiles?

 1 package cspuzzles;
 2 
 3 public class Post004 {
 4     private void overloadedMethod(Object o){
 5         System.out.println("Object o");
 6     }
 7 
 8     private void overloadedMethod(Number n){
 9         System.out.println("Number n");
10     }
11 
12     private void overloadedMethod(Integer i){
13         System.out.println("Integer i");
14     }
15 
16     public static void main(String[] args){
17         Post004 p = new Post004();
18         p.overloadedMethod(10);
19         p.overloadedMethod(10.0);
20         p.overloadedMethod("Hello");
21         p.overloadedMethod(new Integer(10));
22         p.overloadedMethod(new Byte("1"));
23         p.overloadedMethod(new Post004());
24     }
25 }

Hint

When Java does not find a direct match for a method, it applies widening and/or autoboxing to the parameters trying to find the more specific matching method.

With autoboxing, the compiler automatically wraps primitive values in an object. For example, a literal integer is wrapped in an Integer object.

In the case of widening, the compiler tries to find a wider type than the original type. For example: an int can be widened to a long and a String can be widened to a Object.

Answer

Yes, it compiles and it prints:

Integer i
Number n
Object o
Integer i
Number n
Object o

Explanation

Let's explain what happens for each of the calls:

1. overloadedMethod(10): 10 is an integer literal and is boxed to an Integer.
2. overloadedMethod(10.0): 10.0 is a floating-point literal. The compiler first applies boxing (i.e. from double to Double). Then, it widens Double to Number.
3. overloadedMethod("Hello"): in this case, we are passing a String object which is widened to Object.
4. overloadedMethod(new Integer(10)): this is a direct method match.
5. overloadedMethod(new Byte("1")): Byte is widened to Number.
6. overloadedMethod(new Post004()): after all an object Post004 inherits from Object, that explains the last line printed.

Huh! Sometimes overloading can be trickier than it seems. Did you get all of them correct? Would you like another puzzle about overloading? Let's hear your opinions in the comments.

See you next puzzle!

Passing Parameters in Java

After playing a bit with constructors and initialization blocks, now let's start experimenting with methods. What does the following code print?

 1 package cspuzzles;
 2 
 3 class MyInt{
 4     int anInt;
 5 }
 6 
 7 public class Post003 {
 8     void Method01(int x){
 9         x = 10;
10     }
11 
12     void Method02(MyInt m){
13         m.anInt = 15;
14     }
15 
16     void Method03(MyInt m){
17         m = new MyInt();
18         m.anInt = 20;
19     }
20 
21     public static void main(String[] args){
22         Post003 p = new Post003();
23         MyInt m = new MyInt();
24         m.anInt = 5;
25         System.out.println(m.anInt);
26         p.Method01(m.anInt);
27         System.out.println(m.anInt);
28         p.Method02(m);
29         System.out.println(m.anInt);
30         p.Method03(m);
31         System.out.println(m.anInt);
32     }
33 }

The key is understanding passing primitive values vs. object references.

The code prints:
5
5
15
15

In line 26, a copy of the value of m.anInt is passed. Therefore, line 9 is modifying just a copy of the original value and when the control returns to line 28, the original value has not changed (i.e., the value of m.anInt is still 5).

In line 28, we are passing a copy of the object reference. In other words, variable m in main and variable m in Method02 are different variables, but both refer to the same object. Given said that, line 13 modifies the object created in main and line 29 prints, as expected, the new value of m.anInt.

Now for the bonus part. In line 16, variable m refers to the same object as the variable m in main. But after executing line 17, variable m in Method03 refers to a new object, that's why line 18 is not modifying the original object in main.

What do you think about Java mechanisms to pass parameters? Let's hear your opinion in the comments.

Java Initialization Blocks

Let's have more fun with Java. If you miss our previous post about constructors, take a look at it, here. Here is the new puzzle, what does the following code prints?

 1 package cspuzzles;
 2 
 3 class SuperClass2 {
 4     protected int x = 5;
 5 
 6     { x++;}
 7 
 8     public SuperClass2(){
 9         this(2);
10         x++;
11     }
12 
13     public SuperClass2(int i){
14         x *= i;
15     }
16 
17     { x *= 2; }
18 }
19 
20 public class Post002 extends SuperClass2{
21 
22     { x ++; }
23 
24     public Post002(){
25         x++;
26     }
27 
28     public Post002(int i){
29         super(i);
30         x *= i;
31     }
32 
33     public static void main(String[] args) {
34         Post002 p = new Post002();
35         System.out.println(p.x);
36         p = new Post002(2);
37         System.out.println(p.x);
38     }
39 } 

The tricky parts here are initialization blocks. Lines 6, 17, 22 are initialization blocks. An initialization block runs after the super constructors have run. If there is more than one initialization block, they are run in the same order as they appear in the class. Usually, initialization blocks are placed at the beginning of classes, but nothing stop us from writing one at the end of classes or in between methods.

The code prints:
27
50

The following table shows the lines executed for each of the objects created:

new Post()	new Post(2)
Line 4: x = 5	Line 4: x = 5
Line 6: x = 6	Line 6: x = 6
Line 17: x = 12	Line 17: x = 12
Line 14: x = 24	Line 14: x = 24
Line 10: x = 25
Line 22: x = 26	Line 22: x = 25
Line 25: x = 27
	Line 30: x = 50

Do you think initialization blocks are useful? How have you used them? Share your thoughts in the comments.