These are some of the puzzles/tricks I’ve been thinking about these weeks.
Dividing area up
You have a 1x1 unit square area that you want to divide into 3 equal area. What’s the least length of lines needed to do so?
Before we try something, we should have a naive solution. We can simply draw two lines. So our answer should be <= 2.
Next, what if we draw a horizontal line that cuts off 1/3 of the area, and then have another line perpendicular to it to divide the remaining area into two. The result there is 1 + 2/3.
That’s pretty good already. What if we perturb the solution slightly, so that instead of a T shape, we get like a Y shape. If we form a cost equation of decreasing the vertical line but increasing the two diagonal line, we can see that the maximum we can decrease before the costs outweighs the saving is <= 2/15. At that point, the total length used is the same as the T shape, so there is probably a local minimum there. We can use calculus for this to get an exact answer. To test this hypothesis, I plugged in a (= the perturbation) = 1/15 and got ~1.62 which is better than our original 1.66 solution.
Sub problem
We have 4 cities located on the 4 vertices of a 1x1 square. We want to construct a road network to ensure it is possible to get from any cities to the other cities. We would like to minimize the length of the roads built. We do not care about how it takes to travel between cities.
Read: Steiner problem.
Venn diagram for 4 groups
Is it possible to draw a venn diagram that represents all possible subsets of 4 groups? If no, why not? What about squares? Rectangle? Oval?
Source: Concrete mathematics 2 ed
It is fun to try this problem and draw a few circles and quickly realize that it’s not possible.
A circle can finitely intersect another circle maximally at 2 points, and this creates at most 2 new regions. If we have 4 circles to represent the 4 groups, then we have at most 4C2 * 2 = 12 finite intersections. This means we can have at most 14 intersection (2 for free when a circle first enters the space).
This is the same situation for squares. However, for ovals and rectangles, they can finitely intersect at 4 points, so it is possible to generate more regions. In fact, solutions do exist.
Clever datastructure
This is not so much a puzzle but an interesting data structure that caught my attention.
Given an array, implement an API that allows us to query the sum of a subregion effectively.
Read: Fenwick tree
Unix skills
You are given a string of mixed case. How can you convert them all into lowercase quickly?
In order of speed from slowest to fastest: Write a compiled {c++, java, go} program to do it, open up a modern text editor like sublime text.
If you stackoverflow this question, people would suggest either using the unix tool tr which honestly is hard to remember how to use.
Vim users have a quick way of doing this. Open vim, insert mode, paste line, Ctrl + V, u
An equally fast was is to use interpreted/scripting languages like python/javascript.
You are in a directory, and you want to find the real path of a file in that directory.
The solution is in the question: realpath