Mathematical vs. Computational approach - combinatorial

Here's the question. You are given rods of lengths 2 and 3. You are to line them up so that the total length is 20. How many different ways are there to make length of 20? You have sufficient quantity of both types of rods. Not meant to be a non-sense / tricky question. There are at least two major distinct types of approaches.

[1] Algebraic / Mathematical

Let x and y represent the number of rods of lengths 2 and 3, respectively. Then the governing equation is 2x + 3y = 20 with x and y being non-negative integers. For each (x, y) combination, there are f(x,y) = (x+y)!/(x!y!) different ways of arranging them. So for each combination,

(x, y) = (10, 0) gives f(10, 0) = 1

(x, y) = (7, 2) gives f(7, 2) = 36

(x, y) = (4, 4) gives f(4, 4) = 70

(x, y) = (1, 6) gives f(7, 6) = 7

and the answer is 1 + 36 + 70 + 7 = 114.

[2] Computational

We can incrementally increase the length of the rod, using rod of lengths shorter by 2 or 3. For L = 7 for example, you can add L=2 rod to the right end of each configuration for L=7-2=5, or add L=3 to right end of configuration for L=7-3=4. So the governing equation here is g(7) = g(4) + g(5), or in general g(L) = g(L-3) + g(L-2), with g(0) = 0, g(1) = 0, g(2) = 1, g(3) = 1. We can 'climb the ladder' one by one, or increase L by one until L=20. To list a few intermediate cases,

g(4) = 1

g(5) = 1

g(6) = 2

g(7) = 3

g(10) = 7

g(12) = 12

g(15) = 28

g(20) = 114

[1] requires systematic understanding of underlying principle. You can write a general solution, but you would need to compute each cases from scratch. If you need to figure out an answer for only one final length, this might be a better option.

[2], on the other hand, does not require (or require far less) understanding of logical structure. You only need to find recurrence relation from simpler / smaller cases. And you reuse answers for shorter lengths, so [2] could be your choice if you need to repeat this computations a lot of times.

I have been a type [1] person for a long time. I would have been upset at [2] since it does not conform to 'solving' a problem. It could only be called finding the answer.

But there are classes of problem you can solve only with [2]. Or type [1] approach is far less efficient. What if you have more than two types of rod, like 5 types of rods? Thus I have been making a gradual transition to (or adoption of) type [2] thinking.

Which of the two came up to you first?

PS - approach [2] is called Dynamic Programming in computer science, in that one can think of the original problem being made up of smaller problems of the same logic. In mathematics it belongs to sequence (described by recurrence relation), so you may call both approaches mathematical. Taxonomy is not the main point of this article.

[R] selecting m highest values in each row and their column indices from data frame

A simple microtask : you are given a data frame of numerical data. You want to find maximum values of each row with corresponding column names, and add them at the right end of the original data frame. Here is my solution using user-defined functions that invokes sort(). May not be an efficient or R-native code though. Leave a comment please for a better solution.

maxval1 = function(x) {

  q <- sort(x)

  return(q[length(x)])

}

maxcol1 = function(x) {

  q <- sort(x)

  return(names(q)[length(x)])

}

df <- cbind(df, val1 = apply(df, 1, maxval1), col1 = apply(df, 1, maxcol1))

df <- data.frame(df)

The above code appends maximum value of each row and matching column names at the end of existing data frame df. You only need to replace length(x) by length(x) - k for (k+1)th highest value / index. Or you can replace it with 0, 1, ..., k for lowest value / index.

Project Euler #110 - 41 days spent on a problem

Project Euler Problem #110 is an extended version of #108. The latter can be solved with simple brute force code pretty quickly, but the former obviously defies such simple-minded approach. One should generalize #108 in order to solve #110.

I solved #108 in Jun 10 by brute force. I immediately started finding the general rule. It took me, however, about 40 (four zero) days in the end. Even though I haven't been on this problem 24/7 for the last 41 days, I must have attempted over 50 times in total.

I am proud of myself not having searched for any solution or hint in the mean time. There are other problems for which I spent 2~3 weeks to solve, but 41 days on #110 is definitely my personal record.

* Most of the 50 attempts were purely speculative (even without pen and paper). Not much progress with the brain-only attempts, so I decided to revise #108 code to rearrange and extend the result. That helped in the end; even with it I still had to spend another 2~3 days until finally figuring out the rule.

Unexpected behavior of Python in integer division

There turns out to be a number of cases where Python give you results different from your expectation, or from your implicit assumption from years of math experience. Described here are the two representative cases that gave me quite a bit of headache to figure out while trying Project Euler problems #91 and #160. In both lessons, my codes had to work since they had nothing complicated, but they didn't. Then I need to suspect every single bit of logical steps involved, double checking whether they work exactly as I expect them to.

The first case was about the division operation between integers, particularly when you have a number which is an integer multiple of another: 15 * 26 / 13 gives you 30.0 but 15 / 13 * 26 gives 29.999999999999996. The latter is probably satisfactorily close to, BUT LOWER THAN the expected value of 30. It may not be an issue if this is your final output, but it can make a big difference if you use it as intermediate result subsequently fed to a case statement executing completely different codes depending on whether it is greater or less than 30. The reason is obvious: because division operation is always executed as floating point numbers, even when both arguments are integers.

Implicit conversion to floating point numbers can cause a different type of trouble in integer division: lost significant digit / precision. Python is famous for allowing unlimited number of significant digits to represent integer, but not floating point number. You might expect that Division of A = 265252859812191058636308480000000 by B = 10 removes a zero at the end, retaining all other significant digits. But you will lost many digits by going through floating point number.

How can we avoid this pitfall? Make sure to use true inter-integer operators such as // or %. Unlike A/B, A//B gives the correct and expected answer.

C seems to be free from this issue. Both 15 * 26 / 13 and 15 / 13 * 26 gives 0.000000.

-------------------------------------------------------

Two opposite sides of programming: it can easily drive you nuts, but at the same time you can crack it all the way down to binary digit (0 vs. 1) level as long as you are willing to and are persistent.

iPad mount for rear-facing baby

Showing movie clips to babies is definitely a great way for them to ease the trouble of being on board for distance. The problem was that whoever sits next to the baby had to hold the iPad throughout in a quite inconvenient and awkward angle of upper body and wrist. For which time the baby sitter could have done something else like web surfing, had they have an iPad mount for rear-facing infant. Unfortunately most of the available products are for forward-facing kids, or for a car where the rear seat headrest can be pulled up to expose the shaft underneath that can be used to wrap velcro around. As my car has fixed rear headrests, the only option for me was a suction cup iPad mount. Unfortunately again, those products were designed for front windshield mount, meaning arms are typically short. So my solution was, to buy a long arm one and test mount it on the rear windshield with fingers crossed. Voila! It works quite nice. I'm so happy with the beyond-prescription tweak.

* FBA_CH-3B model manufactured by DHYSTAR.

vtech baby phone repair

Life is full of stuffs to fix / repair. Today I had a little cute thing: a vtech baby phone. After ~half a year of infrequent use, the unit started turning off by itself a few seconds after being turned on. Battery should have been okay, since the light turns on and speaker volume (turn-on melody) was moderate for the first few seconds. I suspected lead solder for power switch cable was loose. But everything looked great when I opened the back cover. A bit of Google search says low battery can cause a number of unwelcomed behaviors. So I replaced battery just in case, and voila! It works. Probably its electric circuit has some protection against low input voltage.

Reassembly took some time since I took it apart way too much, but I am happy that the unit is back in service.

Project Euler #94 : Almost equilateral triangles

Here is the problem description:

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units. We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit. Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

* update on 2019/1/6:
I dropped the original contents in compliance with Project Euler policy, discouraging posting solution or hint on public space. Message me if you would need help. I believe you should know Heron's formula.