Sunday, November 11, 2018

Cellular Automata Meets Putnam Problem


The What

You have probably heard of the Putnam Competition. If you haven’t, well it’s almost the IMO in the Imperial System. Or maybe the NEERC of ACM ICPC. Michael Jordan of Baseball?
Ok it’s a mathematical competition, and quite a prestigous one, always known for beautiful and hard problems.
This is the story of how my early undergrad years obsession with cellular automata met a problem in the 2000 Putnam Competition that I was doing for fun last week.

The Problem

Let S0 be a finite set of positive integers. An integer a is a member of Sn if and only if exactly one of a and a-1 is in Sn-1. Prove that there are infinitely many N such that SN = S0 ∪ {a + N | a ∈ S0}.
So if S0 = {0, 1, 3}, we’ll have S1 = {0, 2, 3, 4}, S2 = {0, 1, 2, 5}, and so on.
It’s definitely worth tyring, so I suggest you give it a minute or two.

The Connection

I’ll go through a few basic things about cellular automata and you’ll be able to follow along even if this is your first time hearing the term. Also if you try to keep the problem mind while reading along, you’ll be able to tell which way we are going at each step. If you are already familiar with CA then skip right ahead.
I am not trying to be too precise here. If you would like to know more about cellular automata, I suggest you put aside at least 2 hours(!) and start your binge reading at the wiki page.

Cellular Automata

Think of a cellular automata as an initial state, and an update function from all possible states to all possible states. We are going to apply this function to the initial state to get a new state, and do the same thing with the output of the function over and over again: x0, f(x0), f(f(x0)), …
Imagine one of those stadium waves in motion.



source: sciencelearn.org.nz

Now take a snapshot of the system and let that be your initial state (we only care about the spectators, and whether or not they’re standing). Now define the function to update the world in the following way:
  • A spectator will stand up (or stay standing up) if the person immediately to her right is standing up
  • Otherwise she will sit down/remain seated
To “see” your cellular automata in action, apply the above function subsequently to your snapshot every second in 3, 2, and go!
Why you can get away with calling a function and an input a cellular automata though, is: - A discrete nature of the state of the system, which is composed of cells (spectators), while each cell is allowed to be in finitely many states (standing, sitting)
and the update function being: - Local, meaning it is defined in terms of the state of the world around each cell, affecting only the output of that particular cell (you look to your right, and decide your own move) - Universal, meaning the function definition is the same for all of the cells (everybody looks to her right and decides based on one function)
You must now see the difference between the above (usual) strategy of creating waves vs. defining a centralized function in the stadium which has to microdefine the behavior of every single person explicitly for ~260,000 possible states of the system.

Elementary Cellular Automata

Suppose you have a (usually infinite) row of cells each one adjacent to the two neighboring ones, each allowed to be in one of two states: 0 or 1
Let’s decide to call the black ones 1. The above configuration corresponds to:
1 0 1 0 0 1 0 1 1 1 ...
In the elementary cellular atuomata, your function (remember it’s local and universal) is allowed to look at the current cell, the cell to the right, and the cell to the left. Your function should provide answer for all of the possible inputs that it can obtain from the three. In fact your function consists of exactly 8 (input,output) pairs:
The above table represents one of 2(23) possible update functions. That is, the world around you will always look like one of the configurations on the left. Depending on which one it actually represents you would choose your color after we apply the update function. In this case each cell says: - If I am the only one with value of 1, I’m going to stay 1. - If my left neighbor is the only one with a 1, I’m gonna turn to 1. - Otherwise I will stay at/turn to 0.
Everybody (including your neighbors) does this at the same time in each turn to calculate the own values for their next round. In other words, the steps happen atomically.
Let’s apply the above rule to the following initial configuration:

If we apply it once we get:
Now if we apply it again on this last one, we will get:
And again:
As it is the case above, we usually want to look at these states next to each other. Which is why you will usually see these shown like:
Each of the possible 256 functions is known by a number from 0 to 255 (I’m not going to go through why that is a good idea and why it makes sense. Hint: look to the right of the image of the function table, then tilt your head 90 degrees). Here is how each of them looks like. For example here’s rule 99 which is kind of my favorite. (When not specified, it usually means that the initial state consists of one 1 cell)

Back to the problem

Remember the problem? Finite S0, An integer a is a member of Sn if and only if exactly one of a and a-1 is in Sn-1, Prove there are infinitely many SN = S0 ∪ {a + N | a ∈ S0}.
With all this CA context, this should (or probably already has) remind(ed) you of how this is going to connect to CA. Let’s write the above problem in CA language:
With start from an arbitrary initial position.
A cell i turns to/stays at one in a new round t iff exactly one of i and i-1 has been one in the previous ronud t-1.
Prove that there are infinitely many rounds N that look like they are the initial round
Let’s build the function:
As you can see we don’t care about the guy on the right, which makes sense based on the problem statement.
Now let’s see how it runs:


Can you see the proof to one special case of the problem?
This is rule number 60, and hard to forget after you come across it once, not only because of the beautiful Sierpinski-like triangle pattern, but also because of the fact that it is one of only eight so called additive rules. What that means is conveyed by the following ~1000 pictures (from wolfram mathworld) better than ~1 million words:
This shows what happens if you were to start from an initial position with two black states instead of one. This happens when you can write the rule as some formula of your neighbors modulo 2, which is clearly the case in our problem: met = (leftt-1 + met-1) mod 2.
This is a fantastic property which enables the starting points to care less about the existence of each other. This is a great tool for calculating the nth state of a run from any initial state S: We can calculate the nth state of the simple one dot configuration, then for every black square in S, we shift the result equal to the offset, and sum up everything modulo 2.
You can see this formally if we go over an example in algebraic notation:
Initial state with cells i and j being on: S0 (i, j) ≡ xi + xj
Next round based on rule 60: S1 (i, j) ≡ (1 + x) S0 (i, j) ≡ xi + xj + x i + 1 + x j + 1
Rewriting right hand side: ≡ (1 + x) xi + (1 + x) xj ≡ S0 (i) + S0 (j)
Let’s revisit rule 60 now.
Lemma:
Observe that the simple starting position satisfies the condition of SN from the problem statement infinitely many times at 2n cycles. That is in the first row the of the biggest triangle that you so far, where there are exactly two black cells, with the distance of 2n.




It’s easy to prove why this happens with an induction on n: The dot on the left is going to do the same thing in the next 2n ronuds. The dot on the right is also going to that but with everything shifted 2n times. They will therefore create 4 points in the 2n+1th round, but two of those two points conincide (on the 2nth cell) and cancel each other out. What remains is two black cells on 0 and 2n+1.
Here’s how 60 doesn’t mind multiple black cells in its initial position and will happily generate suitable S2n states for us:
And here’s for example how 169 very much minds different starting positions (also note the density of the black cells)

Final blow

We are now only left to prove the above lemma for the general starting position. We claim that for all n such that 2n > max{S0}, we have a correct S2n.
To prove this, let’s look at this round for every black cell i in the starting position one by one.
We know each of them is going to generate the double black cell Sierpinski pattern at round 2n, in cells 0 + i and 2n + i. But who else can influence these two cells?
Candidate 1: cell number 0 + i - 2n, to disturb cell 0: impossible. 2n > max{S0}. There can’t be a black cell there as all elements of S0 are positive.
Candidate 2: cell number 2n, to disturb cell 2n, again impossible for the exact same reason.
Which after a marathon of keypresses concludes a proof which you can see almost instantly, given you know about rule 60.

P.s. I have paid great attention to put only pixel perfect graphs above so you wouldn’t be disturbed by at least one very particular kind of OCD while reading along.
P.p.s. Which pun do you think was the cheesiest?

Friday, August 10, 2018

Dynamically changing Android app icons, for the rest of us (literally)

What

If you’re an android user, you’ve probably noticed how the Google Calendar app icon behaves:

There’s that little blue (#A7C5F8 for the skeptical) circle just sitting there, maybe signaling that there’s been something going on in the calendar app since the last time you have checked. This is not the story of that little blueish dot.

It is, however the story of the pair of digits that you can see in the center of the above image, which happen to mysteriously coincide with today’s date (July 29th).


Why

Google calendar is probably the best calendar app (or service) that you will find out there, because one, it syncs painlessly on all your devices, and two, it’s icon has those friendly little digits on that nice blue (a number of colors are involved including #3764D0) background which correctly shows the day of the month, whenever you take a look at it, and this fancy, mysterious little feature, is what I’m gonna try to figure out. I got sucked into this while trying to implement the exact same feature for Persian Calendar.

How

Alright so let’s get to work. I found a Google Calendar APK on the internet (I’m not putting it here cuz copyright and stuff) and decompiled it.
Next I tried something as simple as:
Please note: Code excerpts are incomplete. I have only copied the relevant parts.
Here’s an important part of the output:
Now here’s an important portion of that file:
Now let’s have a look at res/drawable-v26/logo_calendar_03_adaptive.xml:
Quite self explanatory right? Each of those resources are pngs containing exactly what you’re thinking: The adaptive_base:

And the calendar_date_03_adaptive:

After that, I took a dive into .smali files and also browsed the remains of the actual code after converting the apk to jar using dex2jar (I used jd-gui).
After hours of navigating the code I hadn’t found a single reference to any of these drawables that I mentioned above.
This is why I set the calendar app aside and went diving into pixel launcher’s source code. Here’s what you can find there in a class called DyanmicIconProvider:
And all of a sudden, everything makes sense if you take a glimpse on other parts of this file:
Note the action class paths.
I also found this c.class with barely even readable decompiled function/class names which is probably responsible for updating the face of the clock app (deskclock). Here are some interesting parts:
It is also interesting note the difference between the design decisions in case of the calendar app and the deskclock app adaptive icons. To further understand this, let’s have a look at a part of launcher_clock.xml from deskclock:
And apart from this, there is no other reference to launcher_clock_second in the codebase.
Interestingly enough, we can see two very different solutions for a fairly similar problem: dynamic launcher icons.
Due to the complications of online text rendering, the authors have decided to pre-cook all the required icons in case of the calendar app. In the case of deskclock however, there would just be too many icons if they were to create the drawables beforehand, which has resulted in bringing this seemingly unrelated (as far as a launcher is concerned) logic into the code of the pixel launcher:

So

This is where my search ends. This is bad news for you if you wanted this fancy little feature in your app too. With the launcher handling all the workload here and not even providing an internal APi, we are probably not likely to see this feature be available to public anytime soon.
Let’s go back to widgets.


Update 1: Thank you Ebrahim for finding this piece of code. This is most likely the actual source code of the part that I was investigating, from LIFE-OS, under com.google.android.apps.nexuslauncher;