Project Euler 154 - Exploring Pascal's pyramid

A triangular pyramid is constructed using spherical balls so that each ball rests on exactly three balls of the next lower level.

Then, we calculate the number of paths leading from the apex to each position:
A path starts at the apex and progresses downwards to any of the three spheres directly below the current position.
Consequently, the number of paths to reach a certain position is the sum of the numbers immediately above it (depending on the position, there are up to three numbers above it).
The result is Pascal's pyramid and the numbers at each level n are the coefficients of the trinomial expansion (x + y + z)ⁿ.
How many coefficients in the expansion of (x + y + z)²⁰⁰⁰⁰⁰ are multiples of 10¹²?

Solution

I have spent a week to solve this problem.

First step is observe the pattern

Now we can see the for any given level l, any row m (starting 0), any column n (starting 0), the value is C_l^m * C_mⁿ

Due to the symmetry, there is no need to go through the entire a triangle. Only going through the red ones is sufficient.


To illustrate the idea, considering peeling an onion, we take off the outermost layer of the triangle, what is left is:


Then again take off the outermost layer, what is left is:


The complexity of the algorithm is O(n^2), which runs 19 minutes on my iMac. I struggle to make it run any faster. 

Project Euler 152 - Writing 1/2 as a sum of inverse squares

There are several ways to write the number 1/2 as a sum of inverse squares using distinct integers.
For instance, the numbers {2,3,4,5,7,12,15,20,28,35} can be used:

12=122+132+142+152+172+1122+1152+1202+1282+1352

In fact, only using integers between 2 and 45 inclusive, there are exactly three ways to do it, the remaining two being: {2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45}.
How many ways are there to write the number 1/2 as a sum of inverse squares using distinct integers between 2 and 80 inclusive?

---

Solution

Wow, this one is tough. I spent more than 6 hours to solve it.

Upon observing the outcome of a very naive (and hence very slow) algorithm, it can be found that only a portion of numbers in the range of [2, 80] can be candidates that form the solution, namely

CANDIDATES = [2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 18, 20, 21, 24, 28, 30, 35, 36, 39, 40, 42, 45, 52, 56, 60, 63, 70, 72]

I don't know how to prove it, so I just hope it's the correct set of candidates.

My algorithm is very intuitive and requires no advanced mathematics knowledge.

First define S([a1, a2, a3, ..., ak]) = sum(1 / a1 ^ 2 + 1 / a2 ^ 2 + 1 / a ^ 3 + .... + 1 / ak ^ 2)

We start with the candidate array [2], search for the next smallest candidate (sc) so that S([2]) + S([sc]) <= 0.5. Obviously, in this case, the next smallest candidate is 3, so we append 3 to the candidate array and the array becomes [2, 3].

The candidate array keeps expanding until such smallest candidate cannot be found, then we update the last element of the candidate array to its 'next greater element' (we will refer to it as 'sibling' in the rest of the article) in the CANDIDATES list.

For example, the candidates array is [2, 3, 4, 5, 6, 12, 28, 52], so no such smallest candidate can be found so that S([2, 3, 4, 5, 6, 12, 28, 52]) + S([sc]) <= 0.5. Therefore the last element 52 is updated to its 'sibling ' 56, the candidate array becomes [2, 3, 4, 5, 6, 12, 28, 56].

if S(candidate_array) + S([sc]) happens to be 0.5, a solution is found.

The algorithm so far will find all the solutions although it's still quite slow. Consider this scenario:

candidate_array = [2, 4], the next smallest candidate that meets the criteria is 5, but even if we 'add up' the rest of all candidates, i.e. S([5, 6, 7, ...., 72]), the sum of S([2, 4]) and S([5, 6, 7, ...., 72]) is less than 0.5. We can see there is no solution for candidate array starting with [2, 4]. Similarly, there won't be a solution when it starts with [2, 5] and so on so forth. So we simply take off the last item off the list, and update the second last item (now it has become the last one) to its 'sibling' 3. When candidate_array = [3], there is also no solution. We take it off the list and end up with an empty array. And this is the terminating condition in the while loop.

It is worth mentioning that there is another condition that needs to be met to trigger the above scenario. That is, the next smallest candidate must equate the last element's 'sibling' in the CANDIDATES list, because the greatest candidate 72, happens to always meet this criteria, and therefore this particular case must be excluded. In the example above, 5 is 4's 'sibling', so the condition is met. On the other hand, the next smallest candidate for [2, 3, 4, 5, 9, 10, 13, 18, 24, 30, 35, 45, 52, 56] is 72, which is not 56's 'sibling'. Therefore the condition is not met and the scenario is not applied. 

The algorithm runs 4 seconds. I consider it not a half bad result.


 

Project Euler 151 - Paper sheets of standard sizes: an expected-value problem

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random.
If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .

Solution 

After round 1, we have
(A2, A3, A4, A5), 1. 1 denotes the probability of this combination.

After round 2, we have
(A2, A3, A4), 1/4
(2*A3, 2*A4, 2*A5), 1/4
(A2, 2*A4, 2*A5), 1/4
(A2, A3, 2*A5), 1/4

After round 3, we have
(2*A3, 2*A4, A5), 1/12
(A2, 2*A4, A5), 1/12
(A2, A3, A5), 1/12
(A3, 3*A4, 3*A5), 1/12
(2*A3, A4, 3*A5), 1/12
(2*A3, 2*A4, A5), 1/12
(A3, 3*A4, 3*A5), 1/20
(A2, A4, 3*A5), 1/10
(A2, 2*A4, A5), 1/10
(2*A3, A4, 3*A5), 1/16
(A2, A4, 3*A5), 1/16
(A2, A3, A5), 1/8

Then we add the probability for the same combination

(2*A3, 2*A4, A5), 1/12 + 1/12
(A2, 2*A4, A5), 1/12 + 1/10
(A2, A3, A5), 1/12 + 1/8
(A3, 3*A4, 3*A5), 1/12 + 1/20
(2*A3, A4, 3*A5), 1/12 + 1/16
(A2, A4, 3*A5), 1/10 + 1/16

Repeat the process for 14 rounds, then look for the combination that has one sheet of paper.

Project Euler 148 - Exploring Pascal's triangle

We can easily verify that none of the entries in the first seven rows of Pascal's triangle are divisible by 7:

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1

However, if we check the first one hundred rows, we will find that only 2361 of the 5050 entries are not divisible by 7.
Find the number of entries which are not divisible by 7 in the first one billion (10⁹) rows of Pascal's triangle.

Solution

Rewrite the number N in the format of:

N = q₁ * 7^p₁ + q₂ * 7^p₂ + q₃ * 7^p₃ .... + q_k-1 * 7 + q_k

For example:

1934 = 343 * 5 + 49 * 4 + 7 * 3 + 2

Define PA(N) as the function to find the number of entries which are not divisible by 7 in the first N rows of Pascal's triangle.

PA(q₁ * 7^p₁) = 28^p₁ * (q₁ + 1) * q₁ / 2

For example:

PA(5 * 7³) = 28³ * 6 * 5 / 2 = 329280

The final formula

PA(q₁ * 7^p₁ + q₂ * 7^p₂ + q₃ * 7^p₃ .... + q_k-1 * 7 + q_k) = PA(q₁ * 7^p₁) + (p₁ + 1) * PA(q₂ * 7^p₂) + (p₁ + 1)*(p₂ + 1)*PA(q₃ * 7^p₃) + .....

For example:

PA(1934) = PA(343 * 5 + 49 * 4 + 7 * 3 + 2) = PA(345 * 5) + (5+1) * PA(49 * 4) + (5+1)*(4+1)*PA(7*3) + (5+1)*(4+1)*(3+1)*PA(2)=381720

I don't know how to prove it.

Project Euler 147 - Rectangles in cross-hatched grids

Rectangles in cross-hatched grids

Problem 147

In a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.

There are 5 grids smaller than 3x2, vertical and horizontal dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

1x1	1
2x1	4
3x1	8
1x2	4
2x2	18

Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.
How many different rectangles could be situated within 47x43 and smaller grids?

Solution

The normal rectangles that are parallel to the borders are easy to count. For the 'diagonal rectangles', it is relatively straight forward to figure out the pattern for square ones (1*1, 2*2). It's the counting of the non-square 'diagonal rectangles' that is the trickiest.

The first step is given the width (m) and height (n) of the box, work out a list of 'max length' of 'diagonal rectangles' with a width of 1 block, starting from top left corner to bottom right corner.

For example, for m = 7, n = 5, we have the list as [2, 4, 6, 8, 9, 9, 8, 6, 4, 2]

Assume m >= n, the general pattern is [2, 4, ... 2(n-1), 2n - 1, ..., 2n - 1,  2(n-1), ..., 4, 2]. There are (m - n) of the (2n - 1) item in the middle. Apparently, when m=n, there is no (2n - 1) item.

The key of this problem is how to calculate the max length of any consecutive blocks that can form a rectangle. Let's define it as M(consecutive_blocks)

For example, for M([2, 4]) = 2. For M([6, 8, 9, 9]) = 6.

By taking advantage of symmetry, there is no need to work out all the cases. Assuming the width of the block is always less than the M(consecutive_blocks), we don't need to consider [4, 6, 8, 8, 6] because the width of [4, 6, 8, 8, 6] = 5, which is greater than M([4, 6, 8, 8, 6]) = 4. Also M([8, 9, 9, 8, 6]) is the same as M([6, 8, 9, 9, 8]).

Start with 'max length' being the first item of the list, iterate over the list, how far can it go before the 'max length' starts to decrease?

In this example, we can see that M([6]) = 6, M([6, 8]) = 6, M([6, 8, 9]) = 6, M([6, 8, 9, 9]) = 6, but the next one, M([6, 8, 9, 9, 8]) = 5. Since m >= n, the length of the 'L' shape is fixed, which is 2n - 1. So the max length can go (2n - 1 - first_item) steps before it starts to decease.

Next question is deceasing by 1 or 2? It can be proved that as long as the first item is less than or equal to the last item, it's always decreasing by 1.

Once we know the value of M(consecutive_blocks), we can easily calculate the number of full-width non-square rectangles (only consider length > width) that can be situated in the blocks.

For example, if M(cb) = 6 and width(cb) = 3, we just calculate the number of 4*3, 5*3, 6*3 rectangles, which is 3+2+1=6. 

Multiply this number by 2 (due to symmetry), we can get the total number of non-square 'diagonal rectangles

Finally, let's prove 'as long as the first item is less than or equal to the last item, it's always decreasing by 1.'

Suppose m >= n, then b >= a, we move the line P toward bottom right, when the lower end hits point X, the 'max length' will start to decease, but until it coincides line R, it deceases by 1 unit. After that, it decreases by 2 units. Line Q which is of the same length of line P, sits between line P and Line R. So between line P and line Q, the 'max length' can decrease by 1 unit at most.

https://github.com/sunmingtao/sample-code/blob/master/python/projecteuler/p147.py

Get rid of boilerplate code (setters and getters) - Lombok

Maven dependency

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok</artifactId>
    <version>1.18.8</version>
</dependency>

Code template

@Getter @Setter @RequiredArgsConstructor @ToString
public class User {
    private final String name;
    private int age;
}

Install Lombok in eclipse

Go to the directory where lombok.jar sits. (e.g. /Users/msun/.m2/repository/org/projectlombok/lombok/1.18.8/)

java -jar lombok-1.18.8.jar

Test callback logic

Suppose we need to write unit tests for the Service class. The Dao class interacts with database, so it needs to be mocked.

class Service{
    
    Dao dao;
    
    Service(Dao dao){
        this.dao = dao;
    }
    
    public void doStuff(String s) {
        Callback<String> callback = i -> {
            System.out.println("Hello "+i);  
        };
        dao.doStuff(s, callback);
    }
    
}

class Dao{
    public void doStuff(String s, Callback<String> callback) {
        callback.apply(s);
        //Some DB operation
    }
    
}

interface Callback<T>{
    void apply(T t);
}

The question is how to test the callback logic (the System.out.println() line). If we simply write test case as below, it doesn't print out 'Hello John'.

@ExtendWith(MockitoExtension.class)
@RunWith(JUnitPlatform.class)
public class CallbackTest {

    @Mock Dao dao;
    
    @Test
    void test() {
        Service service = new Service(dao);
        service.doStuff("John");
    }

}

Well, we can mock dao.doStuff() by using doAnswer() method. It allows us to define the method body. What we do here is only invoking callback.apply(s) while skipping the database operations.

@Test
void test() {
    Service service = new Service(dao);
    doAnswer(i -> {
        Callback<String> callback = i.getArgument(1);
        callback.apply(i.getArgument(0));
        return null;
    }).when(dao).doStuff(anyString(), any());
    service.doStuff("John");
}