rotate updates

I pushed a bunch of commits today yesterday and now rotate has touchscreen support. Like, whoa, literally nobody requested that feature because literally nobody knows about that project anyway. I haven’t committed the solver code yet, and probably won’t for a while since it’s really kinda ugly. (I have five or six similar algorithms to solve rotate4 and there’s a lot of duplicated code because IDA* really needs the code to be heavily optimised to run fast. The loop overhead for looping over four elements is just too much when it has to be done hundreds of millions of times.)

I must say, programming things for touch screens is kinda hard without actually having a touchscreen device to test. I do have one of those “smartphone” thingamajigs that run Android but I don’t really use it a lot, so I had to charge it just to check the touch code was working correctly. Well, it almost was, and you can check the git commit history if you care to know about what I did wrong. Anyhow, I started off by making a generic handler which’d be easy to interface with mouse and touch events, then wrote code for pretending mouse events were touch events, then finally got to writing the touch event handlers.

Touch input didn’t quite work as intuitively as I expected it to, which is unfortunate because I actually spent a fair amount of time thinking “what if I implemented touchscreen support”. The layout’s also somewhat broken in mobile Firefox in a way I cannot reproduce with desktop Firefox. This really makes me wonder how people manage to design mobile websites at all; nothing ever works!

The next feature to land is probably going to be a timed solve function, and maybe macros because solving size-6 or larger puzzles is prohibitively time consuming without them. (Especially if you miss a move mid-sequence and everything just ends up wrong, then you have to redo a huge chunk of the solving. This incidentally was something that happened quite often when I did my gigaminx solve.)

Oh, and I wrote a solver for rotate5 (without orientation). I initially thought of directly adapting my human method of solving it, but came to realise that human methods are good only for humans because we can pull from all our non-domain-specific knowledge to attack problems, which is not so easily done within code. Common sense simply isn’t common when you’re a computer interpreting instructions from a human overlord. The approach of blindly generating and using lookup tables is rather easy to express in code; IDA* is trickier, but it’s not a very complicated algorithm either. There’s still human guidance involved in the sense that I’m telling it what intermediate phases to use, which could, in theory, be done away with entirely. GAP manages to decompose an element in a group into a product of elements from a specified generating set, so there surely has to be a way to automate it completely, though this might not run performantly.

That said, I’m not sure what to do with rotate5 with orientation. It’s very annoyingly nontrivial to just split it into intermediate phases that have coset spaces which are not too large (because we want it to not take 10 days to initialise the solver) and are easily described (because we want it to be easy to code). The difference here compared to rotate4o is that rotate4 has only two possible orientations per piece while rotate5o has four, and given that this grows exponentially with the number of pieces (of which there are also more) and that lookup tables for a phase are proportional in size to the coset space… you get the idea. Another contributing factor to this difference is that rotate4o has an \mathrm S_{16} subgroup with a simple set of generators, but rotate5o doesn’t have a simple set of generators generating \mathrm S_{25}. (But the quotient group would still have 424 elements, which is too large to compute full lookup tables for anyway, so maybe this isn’t as useful as I thought it’d be. There’re no meaningful intermediate subgroups that can be used for solving orientation: either you solve it all at once, or the symmetric subgroup will allow the unsolved parts to leak into the solved parts.)

Relatedly, rotate6 is sort of a deep-cut puzzle, since every pair of moves intersect in a “nontrivial” manner. To twist the definition of “triviality” a bit here, I suppose we can consider rotate5 to not be a deep-cut puzzle because it’s easy to separate pieces and manipulate them individually. rotate5 with the top row and leftmost column fixed, though, does not have individually-manipulable pieces, which is much the same situation as rotate6. This is what makes rotate6 a fundamentally distinct puzzle from rotate4 or rotate5, while any larger size is simply a direct generalisation of rotate6 and can be solved in much the same way.

The Gregory-Leibniz series is a horrible introduction to calculating π

For some reason, when people ask about how π can be calculated (which is, to be fair, a nontrivial question and one worth thinking about), the Gregory-Leibniz series is a very popular response.

Stop doing that.

The Gregory-Leibniz series is itself a simple (but nontrivial) result that requires some basic calculus to establish, and therefore anyone asking about how to calculate π either: knows calculus and therefore also this series (and the more useful arcsine series); or doesn’t know calculus and thus can’t understand the relation to the arctangent. This is why it’s a horrible way to introduce laypeople to calculating π: it doesn’t appeal to any sort of geometric intuition at all.

Oh, and it converges sublinearly, which means that it cannot even be used for calculating π with reasonable speed. There are many tricks for series acceleration, but they generally all seem like black magic to people unfamiliar with them.

There’re ways of calculating π that appeal more closely to geometric intuition. Like, you know, finding the area of a quarter circle via numerical integration: \pi/4=\int_0^1\sqrt{1-x^2}dx. This actually also has not-so-nice convergence properties because of the nondifferentiability at one of the endpoints, unfortunately, but that is not difficult to overcome with some geometry.

Instead of integrating from 0 to 1, we could integrate from 0 to 1/√2. Geometrically, this corresponds to an eighth of a circle plus a triangle with base and height both 1/√2, and since \sqrt{1-x^2} is differentiable within that interval (infinitely differentiable even), the convergence might be expected to be less bad.

\displaystyle\int_0^{1/\sqrt2}\sqrt{1-x^2}dx=\frac\pi8+\frac14

Or, similarly, integrating from 0 to 1/2, which gives a twelfth of a circle and a triangle with base 1/2 and height √3/2:

\displaystyle\int_0^{1/2}\sqrt{1-x^2}dx=\frac\pi{12}+\frac{\sqrt3}8

These both have the expected \Theta(n^{-2}) error when using the midpoint method or trapezoidal technique, in contrast to \Theta(n^{-3/2}) error when integrating over [0,1] using either rule.

Of course, these still have sublinear convergence and suck for actual computation, but they suck less and can actually be derived without any prior knowledge of calculus. (I sorta cheated by knowing that numerical integration has worse performance on nondifferentiable functions, but let’s overlook that—\Theta(n^{-3/2}) error is still better than \Theta(n^{-1}).)

Disregarding all the above, the classical method of finding the areas of inscribing and circumscribing regular polygons with edge doubling does have linear convergence, so in fact Archimedes was way ahead of his time, and it’s telling that it was the method of calculating π for over a millennium. This does involve a square root extraction at every iteration, but that’s a small price to pay for converging at 2 bits per doubling. The trick of using (A+2a)/3 where A,a are respectively the areas of the circumscribing and inscribing polygons doubles the rate of convergence to 4 bits per iteration without increasing complexity, and has much the same motivation as Simpson’s rule. Armed with the knowledge of Taylor series, the faster convergence is easy to prove, but that defeats the purpose of this post!

It’s 2014 and YouTube still sucks

On the vast majority of videos I only get to view them at 360p, despite youtube-dl and other programs informing me that there are, in fact, other options available. I have Flash disabled most of the time (the only times I enable it are to watch/rip things on ニコニコ動画) so I don’t expect to get the H.264 versions, but even so, I don’t get served the 720p/1080p WebM versions even though they exist.

Autoplaying is still a thing on YouTube despite this being an absolutely horrible idea. Unless, well, they’re catering specifically to people who only browse YouTube, because there is literally no other way this could be a good idea. But unfortunately, the YouTube website is not the YouTube app and maybe Google should get that in their heads.

Oh, and for some reason now they’re eating keyboard input they shouldn’t be eating, like Ctrl-W which no longer closes a YouTube tab if the video happens to be focused. Because no one would ever decide to close a video, even after finishing watching it, right?

Speaking of which, playlist autoplaying-by-default is also terribad. Want to check the video description after watching a video? (Not before, because the video has already autoplayed, hurhur.) Nope, you can’t, YouTube’s gotta show you the next video immediately.

These are all such gigantic warts in the YouTube experience and somehow all of them (except the 360p-only thing which seems to be a recent development) have existed for multiple years. Good going there, Google.

A computer puzzle solving observation (left versus right cosets)

One mildly bizarre thing I’ve noticed in the computer puzzling community is that very often right cosets are used instead of left cosets. The solving algorithm is largely the same whether you use left cosets or right cosets, but it seems “obvious” to me that left cosets would be the natural choice.

To quickly draw an analogy, taking the Rubik’s Cube as an example, using left cosets to solve the cube would be like a typical human method (modulo some speedcubing optimisations), where you successively solve larger portions of the cube. On the other hand, using right cosets would be like solving in reverse: you consider the inverse state of the cube, successively solve larger portions of that, then take the inverse of the resulting move sequence as a solution for the original state. For a computer, this presents no problem because performing a move “from the end” isn’t any more expensive than doing it usually (the difference being as simple as whether you use state=compose(state,move) or state=compose(move,state)), but of course this can’t be done with physical puzzles short of peeling off stickers.

One minor exception is with PLL on the Rubik’s Cube, I guess. Cubers new to PLL tend to solve with right cosets of the U-turn subgroup (\mathbb Z_4) of the PLL group (\mathbb Z_2\rtimes\mathrm A_4^2); in other words, you perform U turns until the last layer looks like a known pattern, then apply a memorised algorithm to bring it directly to the solved state.

The lack of connection to physical puzzle solving is what makes the usage of right cosets in computer puzzling rather… puzzling, which is why I’ve used left-coset solving in all my code so far.

My hypothesis is that the mathematical convention is to view a transform (in this case, a move on the puzzle) as a left-multiply, which makes move sequences look like \cdots m_3\,m_2\,m_1\,m_0\,\mathrm{state}, whereas the puzzling convention (if one exists?) is to view a transform as a right-multiply, which gives the more commonsensical \mathrm{state}\,m_0\,m_1\,m_2\,m_3\cdots. The latter would certainly make right-coset solving more intuitive than left-coset solving.

I’ve never looked much at other people’s code, much less code specific to puzzle solving, so the above hypothesis was entirely pulled out from my arse. It does seem plausible, though.

I am angry about software (again)

I uninstalled gdipp after realising that disabling the gdipp services on every reboot was rather inefficient. I also installed MacType again and now it’s working without any text glitches. Hooray nicer font rendering.

The reboots were reboots that shouldn’t have been. There was exactly one reboot that was actually desired because Windows updates needs rebooting. (Lol what is this, the 1990s?) The rest were mostly because of Windows update rebooting on its own (durr) and me rebooting to fix some piece of shit software that doesn’t work after it’s closed the first time.

Like win-sshfs, which I’ve mentioned before. It’s an awful piece of shit. To connect to a server, you need to first save the login credentials. This is, of course, done in plaintext. There’s no option to just always ask for the password on connecting, because that would be too reasonable. And you also have to make sure to never ever disconnect, because then win-sshfs fails to cleanly unmount the virtual drive and it won’t be able to mount anything until the next reboot. Restarting win-sshfs is somehow not enough to fix it. Piece of shit.

Paragon’s ExtFS is also a shit. The only time it actually worked was just after I installed it. Well, apart from it creating every goddamn file with 700 permissions, owned by root. There’s no setting to make it do something less stupid like creating files with 755 permissions. But that doesn’t matter, because it never managed to mount my external hard drive again since the first attempt. Useless.

Dammit, WordPress

So I was adding an addendum to the previous post, and then I tried to publish the update. WordPress gave the very annoying “Are you sure you want to do this” error, which is about as useful as an error message as not having an error message at all. Clicking on the “Please try again” link just brought me back to the post editing page with all my edits gone.

Then I noticed that it said that there was an autosave that was more recent than the post, so I restored that and then hit the update button immediately.

Then in the split second where the page was loading, I noticed that now the editing page said that there was a browser autosave that differed from the server autosave. And of course it was too late to do anything about it. The page loaded, and the earlier edits were live (mostly TeX fixes because I’m bad at TeX), but a whole paragraph at the end got nuked.

Why.

rotate4 solver

rotate being this puzzle thing where you rotate pieces, adapted from some ancient Nokia phone game, and also rather reminiscent of Gripple.

For the sake of reducing confusion, let’s consider rotate4 to be the 4×4 puzzle where the pieces don’t have visible orientation, and rotate4o to be the puzzle where the pieces do. rotate4 can be represented as an isomorphism of \mathrm S_{16} with nine generators, corresponding to the nine possible moves. rotate4o likewise has nine generators, but is isomorphic to some semidirect product \mathbb Z_2^{15}\rtimes\mathrm S_{16}. (The orientation subgroup is not \mathbb Z_4^{15} for parity reasons.) The nine moves may be labelled as m(i,j), as before. Not all nine moves are necessary, though: rotate4’s group can be generated with just five of them, and rotate4o’s group can be generated with six.

I wrote an optimal solver for rotate4 in Python last year, along with two different non-optimal solvers. I briefly mentioned these on the blog, too. To quickly review, the first non-optimal solver used the subgroups <m(i,j)|i\in\{0,1,2\},j\in\{0,2\}> (separating the top eight values from the bottom eight), <m(i,2)|i\in\{0,1,2\}> (solving the top half) and <> (solving the bottom half). While it had three phases, the coset spaces for the second and third phases are isomorphic, so I just termed it a two-phase solver. The other one also had three phases, using the subgroups <m(0,1),m(1,0),m(1,1),m(1,2),m(2,1)> (solving corners), <m(0,1),m(1,0),m(1,1)> (solving left/bottom edges) and <> (solving the rest). This generally produced solutions with much fewer moves than the “two-phase” solver, but the code was a fair bit messier. (These non-optimal solvers solved each phase optimally using lookup tables, which is feasible because each individual phase is quite small.)

The optimal solver tried move sequences of increasing length to simultaneously put a position in <m(i,j)|i\in\{0,1,2\},j\in\{0,2\}> (separating top/bottom) and <m(i,j)|i\in\{0,2\},j\in\{0,1,2\}> (separating left/right), stopping when it encountered a move sequence that produced a solved state. Note that the intersection of these two subgroups is not the trivial group, so it was necessary to keep the state around separately. I never figured out the exact reasons the optimal solver was as slow as it was, though when I ported/rewrote it in JavaScript, I did plenty of algorithmic optimisations that made it run a lot more performantly. I’ll cover this later.

Making these solvers work with orientation was somewhat nontrivial. The two-phase solver does not adapt trivially: taking orientation into account, separating the puzzle into two independent halves is not the same as having the top pieces in the top half and the bottom pieces in the bottom half. The difficulty here is in ensuring that the top half has zero total orientation, so that it can be solved using only moves that affect only the top half, and likewise for the bottom half. It’s not obvious how to index the corresponding coset space. The three-phase solver does trivially, but writing the code for it was a pain in the arse so I gave up; the involved coset spaces were also considerably larger and it took about ten minutes to generate transition tables, which is not nice.

What I noticed was that <m(0,0),m(0,2),m(1,1),m(2,0),m(2,2)> (the same five moves as in Gripple) was isomorphic to \mathrm S_{16}. In other words, it’s impossible to rotate a piece in place using only those five moves, even if you don’t care about the orientation/permutation of the other fifteen pieces. This means that we can choose a reference orientation such that five of the nine moves (specifically, those five generators) don’t affect orientation, while the remaining four moves (m(0,1),m(1,0),m(1,2),m(2,1)) do. The squares of these four moves can be represented with the other five moves, so we can consider \{m(0,0),m(0,2),m(1,1),m(2,0),m(2,2),m(0,1)^2,m(1,0)^2,m(1,2)^2,m(2,1)^2\} as our generators instead.

From this the original two-phase solver for rotate4 can be adapted into a three-phase rotate4o solver: solve orientation (9f*), separate top/bottom pieces (9f*), then solve each half individually (16f* for each half). This produced solutions with mean length about 32.96 moves (in the “face”-turn metric, where half turns are counted as single moves) and a maximum length of 50 moves. The code for this isn’t particularly complicated either, since the first phase is only concerned with the orientation, while the other two phases are only concerned with permutation. The price to pay for this simplicity is that the move counts are quite high.

It is known that Gripple can be solved in 38 moves. We can divide the puzzle into four quadrants, each with a corner piece, two edge pieces and one centre piece. Solving the three non-centre pieces of a quadrant can be done in at most 11 moves (I checked this by hand; I don’t know the optimal value but it’s probably about 9), and doing this for two adjacent quadrants takes at most 22 moves. I did a brute-force search through the 10! permutations for the ten remaining pieces and found that those can be solved within 16 moves. Adding these gives an upper bound of 38 moves, which is somewhat better than the 41 moves obtained from the second/third phases in the previous paragraph.

The next thing I did was to merge the second and third phases. The resulting coset space is isomorphic to \mathrm S_{16}, which is too big to fit in memory, so I wrote an optimal solver for it using IDA*. I didn’t think it’d be feasible at all, seeing how my earlier attempt at an optimal solver for a very similar list of generators was too slow to be useful, but I went ahead anyway. The first attempt was a direct port of the Python code, which worked about as poorly as expected. Then came optimisations.

Just to reiterate, previously, the IDA* search used two heuristics. These corresponded to the coset space \mathrm S_{16}/\mathrm S_8^2, which has 12870 cosets. One way to think of it is to tag eight of the pieces and their solved positions, and seeing how many moves it takes to bring all the tagged pieces to tagged positions (not necessarily the solved position). The two heuristics corresponded to tagging the top half of the puzzle and tagging the left half of the puzzle. The first optimisation was to use two more heuristics of the same type: tagging every other row and tagging every other column. Adding these two heuristics also gave the property that, if all four heuristics report zero distance from the solved state, the state actually is solved, so instead of keeping a copy of the state for every node searched, we only had to store four integers (each denoting the index of the coset in the coset space \mathrm S_{16}/\mathrm S_8^2). The original Python code used separate transition tables for the different heuristics which was unnecessary; using the same transition table led to a somewhat faster initialisation.

The next optimisation was to “canonicalise” move sequences. Many pairs of moves commute, so it doesn’t make sense to search for both A\cdot B and B\cdot A when they’re equal. The moves are indexed from 0 to 8, and a move is forbidden if it has an index not greater than the index of the previous move and it also commutes with the previous move. This does not, strictly speaking, canonicalise the move sequences as there exist move sequences identical under permutation of commuting moves that have multiple such representations, but it’s good enough as an optimisation. Doing a proper canonicalisation would involve looking more than one move into the past, which also means it’d be slower and not worth it. This optimisation reduces the number of visited nodes by about 85%. (Checking whether two moves commute was done with a lookup table, not by explicitly checking that they really do commute.)

The last one was to just use better heuristics. There is inherently some trade-off involved here: choosing a smaller subgroup to reduce to (i.e. having a larger coset space) increases the initialisation time and memory usage, but generally results in more accurate heuristics, which would in turn speed up the actual solving. The new coset space I tried was \mathrm S_{16}/\mathrm S_{12} with 43680 cosets, which corresponds to solving four pieces (and ignoring the remaining 12). Again, I used four heuristics, each one solving the four pieces in each quadrant. This was about eight times as effective at pruning the search tree and also about eight times as fast. However, using the new heuristics in conjunction with the “tagging” heuristics (eight heuristics in total) did not provide much further improvement, pruning only 20% more nodes, which doesn’t make up for having to update twice as many heuristics at every node.

js> S8 = scramble(4)
[[8, 15, 9, 12, 13, 0, 6, 11, 2, 14, 3, 1, 4, 7, 5, 10], [1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1]]
js> prettyprint(S8,print,1) // the numbers below correspond to the orientation: 0 = upright, 1 = rotated right, 2 = upside down, 3 = rotated left
i2  p3  j3  m2
n3  a2  g2  l3
c0  o2  d1  b2
e0  h2  f3  k2
js> solve4a(S8) // three-phase solver
[0, 0, 1, 7, 5, 1, 1, 2, 3, 3, 5, 5, 6, 6, 6, 4, 7, 7, 1, 1, 4, 4, 0, 1, 1, 0, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 0, 0, 0, 6, 6, 8, 7, 7, 8, 6, 6, 7, 7, 8, 7, 7, 6, 6, 6, 7, 7]
js> solve4b(S8) // two-phase solver; the "time taken" is only for the second phase; it does not include initialisation time
L1:  5.844085693359375 / 9
L2a: 4.85003885003885 / 7
L2b: 6.056254856254856 / 9
L3a: 6.149130036630036 / 9
solving phase 1
solving phase 2
0 nodes searched, 0 nodes pruned
starting search at depth 9
107 nodes searched, 1312 nodes pruned
starting search at depth 10
2208 nodes searched, 25303 nodes pruned
starting search at depth 11
37393 nodes searched, 415976 nodes pruned
starting search at depth 12
565538 nodes searched, 6204791 nodes pruned
starting search at depth 13
7946215 nodes searched, 86625498 nodes pruned
starting search at depth 14
solution of length 14 moves found
69370866 nodes searched, 752203551 nodes pruned
time taken: 197.777 s
[0, 0, 1, 7, 5, 4, 4, 2, 7, 7, 4, 4, 2, 2, 4, 4, 4, 3, 3, 1, 1, 8, 8, 4, 4, 4, 6, 6, 3, 3, 8, 8, 4]

So as you can see, it still takes multiple minutes to solve random states. It’s also funny to note how the second/third phases in the three-phase solver took 35 moves when the optimal solution was only 14 moves.

What further improvements can be made here? One thing that stands out in the two-phase solver is that the work done in each phase is rather unbalanced: the first phase has only 32768 positions, while the second phase has 20922789888000 positions. It’d probably be better to have more balanced phases, like, say, using <m(0,2),m(1,1),m(2,0),m(2,2),m(1,2)^2,m(2,1)^2> as the intermediate subgroup (solve orientation, one corner and two edges adjacent to that corner), where the first phase has 110100480 cosets and the second phase has 6227020800 cosets. Calculating lookup tables for the first phase would probably take like half an hour and use 1 GB memory unless I mess with typed arrays, so I guess both phases would have to be done with IDA*.

Addendum: Instead of using the above subgroup, I realised that using the square subgroup (<m(i,j)^2>) produced an almost even split between the two phases. The square subgroup is characterised by every piece-position pair having a unique orientation and if you tag the pieces/positions like on a checkerboard, the tagged pieces are in tagged positions, and the permutation parity of the whole puzzle is even. Taken together, this subgroup has 2^{15}\binom{16}82=843448320 elements, and the coset space has 812851200 elements. IDA* was used for both phases and the resulting solver was not unreasonably slow, generating a solution in 0.19 s on average. What was not so nice was that generating the transition tables for the four heuristics (each of which has about 100000 entries) took about four seconds. I’ll see if using typed arrays speeds this up any.

Another bizarre optimisation I came across when trying to reduce the initialisation time (it was in fact originally around seven seconds) was that these two practically identical functions run at vastly different speeds on Chrome (which was the only environment I used a profiler in; the SpiderMonkey shell doesn’t have a profiler).

function compose_map(a,b)
{
	return a.map(x => b[x]);
}

function compose_loop(a,b)
{
	var c = [];
	for (var i = 0; i < a.length; i++) c[i] = b[a[i]];
	return c;
}

Spoiler: the second one ran over a hundred times faster and shaved off about a second from the initialisation time. Now, Chrome’s profiler is actually sorta buggy and reports impossible times sometimes, but this is still weird. This function is called very often during initialisation (probably around half a million times) and I guess creating the lambda function for the map version at every call only to destroy it later is not very efficient. I also converted a slice/map call to an explicit for-loop in another function, which shaved off another second from initialisation. It’s unfortunate that we have to write uglier code to get better performance.

The haze is back…

… but this post isn’t about the haze because I’ve written enough about it. (Actually, one last thing I want to mention regarding the haze was that my office people were nice enough to give me an N95 mask during last year’s haze season because I had an asthmatic history. I ended up not using the mask because it was rather uncomfortable and I hadn’t had an attack in about a decade, but it was a nice gesture nonetheless.)

The topic of today is smoke. Cigarette smoke.

I generally have a very dim opinion of smokers because most of them are oblivious to the sensibilities of the people around them. During national service I’ve had close contact with a lot of people, a significant portion of whom were smokers. I worked in an air-conditioned office (where smoking is obviously forbidden) and the electronic biodata I had access to never included such “trivial” information like whether someone was a smoker. (But see also footnote.) Given that I never hung out around the smoking area, how did I manage to conclude that the smokers were in fact smokers?

The answer is obvious to anyone who’s been near one of them: the smell of tobacco. It’s an unmistakeable stench that announces to everyone else that you just had a smoke. And for logistical reasons, people tended to look for me during their breaks, which, for the smokers (I presume) included smoke breaks either before or after the consultation. I personally don’t really care if they decide to go smoke after they settle their business with me; what bothers me is when they go have their smoke before.

The worst part is that masking the tobacco stench isn’t even difficult: just get a bunch of mints! I don’t have a particular good sense of smell and the masking provided by typical mints is enough to fool me, so this may very well be selection bias at work, but a lot of people don’t even bother with this basic courtesy. There were some people (I would name names if I remembered them, but alas!) who kept looking for me right after their high sessions—I don’t recall them ever smelling not like tobacco—which irked me plenty. (Of course, there were also people who I didn’t even realise were smokers for quite a while because they were polite enough to do something about their breath.)

Did I say something before about polytechnic graduates and the military? (The answer is “yes”, but I probably nuked the blog post.) Apparently, being a poly grad (versus JC) is also somewhat correlated with having a smoking habit, though I don’t have much data to support this and it’s probably some combination of selection/confirmation bias hard at work in my brain.

Another thing that bugged me last year was that I used to take a bus from camp to AMK Hub then walk the remaining distance (about 2 km) home. Stepping out of AMK Hub was horrible—I’d almost immediately encounter hordes of smokers hanging around and smoking without any care in the world. I don’t know why they congregate just outside an area with high human traffic instead of having their smoke in some nearby HDB flat void deck, which, on the other hand, are practically devoid of smokers. (These observations were made in the early evenings, which might not be entirely representative.)

And speaking of smoking in public areas, a couple of weeks ago I was idly waiting at a bus stop, when a bus (not the one I was waiting for) came by, and some asshole who was smoking just threw her cigarette butt onto the grass before boarding the bus. Yo, what the hell, the ashtray is just a couple of metres away! I had the urge to just shout “hey bitch, pick up that cigarette” but I didn’t have the courage. I should work on that.

For that matter, just looking around at the ground in Singapore reveals a somewhat startling fact: a huge proportion of litter is made of cigarette butts. (And actually this turns out to be true in many other cities, which goes to show how uninformed I am.) The natural solution to this is to simply outlaw cigarettes, except this won’t be done because presumably the government makes boatloads of dosh from the vice tax. (Put another way: when I do get a job (as if), would I be willing to pay extra in taxes to make up for the lack of vice tax? I’m not sure.)

Footnote: Actually, I probably did have access to the paper records for such biodata, but I avoided checking paper records as far as I could for two reasons: first was that I had no business checking their records, and second was that accessing the paper records would’ve required walking a couple of metres.

Memoising recursive functions in JS

Gosh JS is such a horrible programming language. An identifier can, depending on context, refer to different objects in the same scope without being reassigned between references. But I still use JS anyway because I’m too lazy to learn GUI programming for anything else, and the HTML+CSS+JS combo is actually pretty useful because it’s so heavily riced. (Have I mentioned how cool CSS transitions look? Of course I have, and I’ll mention it again: they’re cool.) Anyway. I’ve actually written on memoising JS functions before on the old blog, but let’s pretend that never happened, shall we?

So you have a memoisation function that takes a function, and returns a memoised version of that function. This is rather straightforward, though it didn’t immediately occur to me to use JSON.stringify or [].slice because I learnt JS in a time where neither JSON nor Function.prototype.apply existed.

function memoise(f)
{
	var l = {};
	return function () {
		var argstr = JSON.stringify([].slice.apply(arguments));
		// f could possibly return undefined so don't just do (l[argstr] !== undefined) and instead check for membership
		if (!(argstr in l)) l[argstr] = f.apply(this,arguments);
		return l[argstr];
	};
}

Because we like clichéd examples, suppose we want a function to calculate the nth Fibonacci number for nonnegative n using recursion to implement the recurrence relation and bootstrapping from F_0=0;~F_1=1.

function F(n)
{
	if (n < 2) return n;
	else return F(n-1) + F(n-2);
}

This gives a nonmemoised Fibonacci calculator, which takes \Theta(F_n) time to calculate F_n. (I’m ignoring the fact that it’s not really valid to use big-o notation here because the integers with representable predecessors only go up to 253, so n>2^{53} just leads to the function never halting.) This is terrible, because in the process of calculating F_{n-1} the value of F_{n-2} is needed, which is also used later in the computation, but the calculation has to be redone because the value is not cached.

F = memoise(F);

It’s memoised, right? Of course it is. So now the first invocation of F(n) will still take an exponential amount of time, but all subsequent calls will be fast. Yay!

… Not. This is still terrible, because calling F from outside the original F gives you the “memoised” version, but, for reasons I’m not too sure of, calling F from within the original F gives the original F instead of the memoised one. (I have two hypotheses for the reason, and I’m fairly sure at least one of them is right, but I don’t know which. One is that as the function was defined with a name, the name can only ever refer to itself or a variable within the function. The other is that there’s a distinction between F the variable (which is the memoised function) and F the function (which is the nonmemoised function) and since F is referred to using function call syntax, the function version is used. I’m already confusing myself here, but tl;dr it doesn’t work as expected.) The following is not a fix, and exhibits the same behaviour.

var F1 = memoise(function F1 (n) {if (n < 2) return n; else return F1(n-1) + F1(n-2);});

The reason is that this uses a function expression (as opposed to a function statement, as used for F), so the identifier can only refer to the function itself unless it’s shadowed by a variable with the same identifier within the function. On the other hand, the following does work.

var F2 = memoise(function (n) {if (n < 2) return n; else return F2(n-1) + F2(n-2);});

This gives a \Theta(n) Fibonacci calculator, and the reason this works is that F2 can only possibly refer to the memoised function so there’s nowhere for things to go wrong.

F2 has \Theta(n) time complexity, but also \Theta(n) space complexity because all previous values are cached. (Again, calling attention to the fact that big-o notation is invalid because while real integers use \Omega(\log n) space, JS numerical types have only a finite range and thus can fit in constant space.) In fact, a solution is to just not use recursion at all. Memoisation then becomes optional when you just want one specific Fibonacci number, though the usual benefits of memoisation for nonrecursive functions (more commonly just known as “caching”) apply if you need to call the function multiple times. In practice, you also have to make sure that accessing the cache is not any slower than just recomputing the value.

function F3(n)
{
	if (n < 2) return n;
	var a = 0, b = 1, c;
	while (n --> 1)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return b;
}

Still \Theta(n) time, but only constant space complexity. Can we do better? Of course we can. The powers of \begin{pmatrix}1&1\\1&0\end{pmatrix} have the Fibonacci numbers as entries, so performing exponentiation by repeated squaring gives \Theta(\log n) time, and something similar is used in GMP. This is the best that can be achieved with only integer arithmetic; allowing floating-point arithmetic lets you use Binet’s formula, for a constant-time constant-space algorithm, though you’ll run into accuracy/precision issues.

Anyhow, the above memoisation function is incapable of taking an arbitrary recursive function and making it auto-cache, unless the standard trick of passing the function as one of its own arguments is used. Except that no one does this in JS so memoise can never provide a direct drop-in replacement, in which case you might as well just hard-code the caching in each function.

Python’s functools.lru_cache decorator is a nice example of a memoiser, and it’s somewhat unfortunate that it’s impossible to have this same niceness in JS.

CSS transform interpolation

For rotate I initially used rotate notation to represent a rotation. This came with the caveat that (taking the 4×4 as an example, so there are four orientations) the orientation can’t reduced mod 4 because transitioning from rotate(270deg) to rotate(360deg) is not the same as transitioning to rotate(0deg): the former does a rotation by 90 degrees clockwise (which is desired), the latter by 270 degrees anticlockwise (which is not desired).

CSS transforms do allow arbitrary affine transforms through specifying a matrix, but I was worried that browsers would linearly interpolate between two matrices for the purposes of displaying a transition. Suppose that the initial and end matrices are A and B. Even if both A and B have determinant 1, \alpha A+(1-\alpha)B could have a different determinant. Having the area change mid-rotation is clearly undesirable.

It turns out that the CSS Transforms spec does mention how to interpolate transforms, with another section for the case where direct linear interpolation cannot be used. Both Firefox 34 and Chrome 37 get this right (yay) and IE 11 gets this only partially correct (lol IE). The spec-compliant thing to do, in the case where both the initial and end matrices are rotations, is to simply do a rotation in the direction where the angle is not greater than π. (IE 11 apparently gets the matrix decomposition right, but it doesn’t seem to care about choosing the smaller rotation angle.) There is an obvious discontinuity at handling a rotation by exactly π, but the algorithm in the spec does deterministically choose which direction to rotate so I’m not too bothered by that.

I just want to say that when I was trying to search for information on using transitions with transforms, a whole bunch of not really informative websites came up near the top of the Google results. Among them included the infamous W3Schools, which is a really horrible resource if you want to learn how to do things the right way. (And not just, say, doing things in a way that works currently but could potentially break in the future… except that the WHATWG is too obsessed with being backwards compatible so things probably will never really break, which makes my point moot.)

Update: Apparently I was wrong and Firefox Nightly never handled this correctly, instead doing the same thing as IE 11. I checked ten builds between 2014-05-01 to 2014-09-07 (today’s) and none of them handled the rotation interpolation correctly. I’m not really inclined to releasing something that’d only work on Chrome since that’s not even my main browser.

Even more of that rotation thing

I finally decided to do something useful with my GitHub account, so here: rotate. (I spent a few hours wondering why GitHub Pages wasn’t working for me, only to find out that it required a verified email address and I’d never bothered verifying mine in the two whole years since I made the account.) Note that Firefox has relatively bad performance on this compared to, say, Chrome or (gasp) IE 11. Still playable, but the fancy CSS transitions aren’t as smooth and the font rendering is especially bad on Windows Firefox (though fine on Linux).

This now has multiple sizes available (4×4 and up), and the pieces now actually do rotate instead of just translating. This added orientation aspect also makes it significantly harder to solve.

The orientation may be considered to be an integer modulo 4(\mathrm{size}-3) (and this is pretty much how it’s implemented). Each move moves 4(\mathrm{size}-3) pieces and increases the orientation value of each of the moved pieces by ±1 (depending on the rotation direction), so we have the basic fact that the sum of the orientation of all pieces is an invariant.

The pieces may be divided according to their parity, and the piece positions likewise. A piece in a position of the same parity must have even orientation while a piece in a position of opposite parity must have odd orientation. In other words, a piece has only 2(\mathrm{size}-3) valid orientations for any particular position. (This is very similar to what I described for the 45°-face-turn Rubik’s Cube, where even though I describe the orientation as an integer modulo 12, only six orientations are valid.)

It’s possible and not too difficult to describe the puzzle in such a way that the orientation is modulo 2(\mathrm{size}-3) instead of 4(\mathrm{size}-3), at the cost of slightly complicating the description of a move. This would likely be ideal when implementing a solver, though, since it reduces the amount of information to be stored in a puzzle state.

Speaking of solving, I’ve managed to manually solve the 4×4 with orientation and the 5×5 without orientation, though the 6×6 has me stumped. Caring about orientation makes the 5×5 considerably more annoying to solve (without orientation, it’s actually easier than the 4×4), and while I’ve figured out a commutator to rotate a pair of pieces, said commutator is about a hundred moves and repeatedly applying that is very unfun. Likewise for the 6×6, in theory I have all that’s necessary to solve it (bringing any three pieces to any three positions, a three-piece cycle, and a rotation of two pieces), but actually executing a solve from start to end is way too tedious for me.

Getting back to the 4×4, I’ve covered the non-oriented puzzle before, and came to the conclusion that it’s solvable in at most 35 quarter turns. I briefly mentioned the algorithm I use when solving the non-oriented puzzle manually on the old blog, but since it’s dead now, I’ll just go through it again. I do the top two rows similar to how the 15 puzzle is usually solved (put a and b in, put c in d‘s position and d next to c, then rotate c and d into the correct positions together). Next the left and right columns are solved, leaving j, k, n and o; the possible cases are that it’s solved (1/6 probability), two adjacent pieces are swapped (2/3), or two non-adjacent pieces are swapped (1/6). I used to apply a Rubik’s Cube algorithm at this stage, but I found (or, I wrote a program that found) a five-move sequence to swap any two adjacent pieces which is significantly more efficient.

The orientation is actually not that big of a deal and the steps can be modified slightly to account for the orientation, except that after the final permutation step above, the orientation for the four pieces still needs to be handled. The five-move sequence messed up the orientation of more pieces than I’d’ve liked it to, so I went back to using Niklas for swapping two pieces. Coincidentally, the Sune analogue also functions as an orientation changer here, which results in a fairly simple solution.

I wonder what the diameter of the corresponding group for the 4×4 puzzle with orientation is.

Previously, previously, previously.

I have no idea how to write emails

No, I don’t mean like writing a program that handles emails or even a regexp for checking whether an email address is valid. I certainly don’t know either of those and it wouldn’t be blogworthy to mention something that’s both true for most people and not expected of me.

I literally mean the composition of email messages.

You see, I was stuck in a not-quite-a-job for two years, a fairly large chunk of which I wasn’t working at all, and a fairly large chunk of the remaining actually-working bits was reading emails, and a small chunk of that remainder was writing emails. Which was still a considerable amount of emails compared to the quantity I sent throughout six years of high school (which was probably in the ballpark of 40 to 50 messages).

However, I had pretty much zero respect for the recipients of the messages I was composing. I don’t know how many of my rants regarding this topic survived my purge of embarrassing articles, but if you read my previous posts on the topic, you know what I mean. I’ve straight-out insulted people of vastly higher rank or standing in my messages. For that matter, there were requirements on how email messages were supposed to be formatted, but as far as I can tell there was exactly one (read: 1) office I communicated with which followed the guidelines, and they also happened to be located in HQ MINDEF so I guess it’d be pretty hypocritical if they didn’t follow their own guidelines. I don’t remember the arcane rituals one must follow in order to craft the electronic mail message of greatest dignity but I’m pretty sure I violated them with the very first word of almost every single message I sent because I addressed most people with this two-letter word: “Hi”. I also addressed most officers by their given name instead of surname, which probably also violates a dozen other protocols.

I mostly didn’t give a shit because I didn’t believe in authority. The funny thing about that job was that it was compulsory for almost every male of this country, and generally people let you get away with doing whatever because, firstly, they don’t want to further antagonise someone working in a job they don’t love and secondly, unless you’re really causing a lot of trouble for them with your nonsense, the red tape involved in official punishment is simply not worth it. I figured that that was part of how I managed to avoid punishment with my outright trolling messages.

I don’t have these excuses to fall back on now.

A couple of years ago—I don’t remember whether it was on this blog, the old blog, or Twitter, or wherever the heck I stashed away dumb ideas—I flippantly mentioned that email signatures like “Best regards,\n[my name]” are absolutely worthless if they’re automatically added, because then it just becomes a bunch of meaningless words you send with every message. I did use automatic email signatures during the job stint, except I forwent the “yours sincerely” bullshit and left actually useful information like my name and job scope. Now that I’m a student, I don’t exactly have a job scope so I assume I could just leave my name. Except that email messages have a name field, so I could just omit the signature altogether. Is this a good idea? I don’t know!

All I know is that the style of email writing I’d acquired in the last two years is probably not going to be suitable, and this might be a slight problem.

Orthonormal integer-translate partitions of unity

I was thinking about this for a bit.

What are the finite functions that satisfy the following three criteria?

\displaystyle\sup\,\{x\,|\,f(x)\ne0\}-\inf\,\{x\,|\,f(x)\ne0\}<\infty\quad\text{(finite support)}\\  \forall x\in\mathbb R\quad\sum_{n\in\mathbb Z}f(x+n)=1\quad\text{(partition of unity)}\\  \forall n\in\mathbb Z\quad\int_{\mathbb R}f(x)f(x+n)dx=[n=0]\quad\text{(orthonormality under integer translation)}

For instance, we have the boxcar function x\mapsto[-1/2<x<1/2].

And then I can’t really think of anything else. It seems somewhat nontrivial coming up with such functions with larger support. I’ve seen an example somewhere, so it ought to be possible, but I can’t remember it.

There’s also the uninteresting example of partitioning the unit interval [0,1] into a finite number of smaller intervals A_k,\,k\in\mathbb Z, whence the function x\mapsto[x-\lfloor x\rfloor\in A_{\lfloor x\rfloor}] is constructed. This allows arbitrarily large supports (as defined by the range) but also seems too much like a hack and isn’t quite what I’m looking for.

A “trivial” result is that if we assume that the support is an interval (open or closed doesn’t matter) and that the function is positive throughout said interval, then this interval must have length at most 1 (otherwise \int_{\mathbb R}f(x)f(x+1)dx>0) and therefore has to be the boxcar function or a translated version thereof.

On doge

I am (still) being awfully upset over the doge meme which exploded in popularity around the start of the year. This one internet fad has ruined the words “so”, “much” and “wow” for me.

Thankfully, like most memes, it died out after a while and I haven’t been seeing so much of it lately, though the damage has long since been done.

π/4

So, today is Pi Approximation Day, and unfortunately I have nothing very closely related to π to present today.

Anyway. Let’s have a look at the Rubik’s Cube. There are effectively six moves available, which we may take to be {U,D,L,R,F,B}, as usual. (It is, of course, possible to instead use {U,u,R,r,F,f} or {U,R,F,E,M,S} as a “basis” instead, but using the standard moves fixes the centre facelets.)

It is obvious that with a normal Rubik’s Cube, you’re only allowed to turn the faces in multiples of 90°, for the very simple fact that edge cubies and corner cubies are shaped differently and you can’t just interchange them.

But what if we could? What if we turn the faces by only 45°?

It’s probably not possible to make a good real implementation of this, since, projecting the cubies onto a sphere, edge cubies and corner cubies have different latitudes, so the turns will inevitably have some bumpiness. (The path of motion is also most likely forced to be nondifferentiable.) I presume using magnets would be the most straightforward way of creating this idea IRL, and this has probably already been attempted by puzzle-modding enthusiasts.

There is also the Mixup Cube, where faces are still restricted to 90° turns, but slices can turn by 45°; corners remain corners, but edge and centre cubies are now equals. This is conceptually similar to Mozaika and a few other puzzles, except that edge cubies on the Mixup Cube have orientation. (Depending on stickering, the centre cubies might not have visible orientation, in which case the Mixup Cube’s states don’t form a group.)

Getting back to the idea of a 45°-face-turn cube, centre cubies are still fixed and edge/corners can freely mix. It’s not hard to prove that arbitrary permutations (not just even permutations) can be obtained due to the existence of an eight-cycle. As on the usual Rubik’s Cube, there is an orientation invariant; if we choose an orientation reference as pointing towards the direction of increasing latitude, U/D don’t change the orientation, while any of the other four face turns changes the orientation of four pieces by 30° and the other four pieces by 60°, resulting in zero total orientation change.

The non-centre cubies have six possible orientations. On a normal Rubik’s Cube edge orientation corresponds to a cyclic group of order 2 and corner orientation corresponds to a cyclic group of order 3; since edges can corners can mix here, this means they should have at least six orientations. While it’s mentioned above that a non-horizontal face turn would change the orientation of four cubies by a twelfth of a revolution, it turns out that that’s just an artifact of how we decided to label our reference orientation. Any originally E-slice edge cubie in a non-E-slice position necessarily has orientation an odd multiple of 30°, and likewise for any originally non-E-slice cubie in an E slice position.

The centre cubies have eight orientations. Unlike the non-centre cubies, the total orientation is not an invariant in either the 45°-face-turn cube or the Rubik’s Cube. Instead, the parity of the total orientation equals the permutation parity of the non-centre cubies for the former. This can be seen to be because every turn changes both the permutation parity and the centre orientation parity. Like the Rubik’s Cube and unlike the Mixup Cube, ignoring the centre orientation still results in a group.

The 45°-face-turn cube would have a total of 20!\cdot6^{20}\approx8.9\cdot10^{33} states if centre orientation is entirely ignored, 20!\cdot6^{20}\cdot2^6/2\approx2.8\cdot10^{35} if the parity of the centre orientation is used, and 20!\cdot6^{20}\cdot8^6/2\approx1.2\cdot10^{39} if all eight orientations are distinguishable. That said, it’s not really the number of states which determines a puzzle’s difficulty—the Megaminx has many more states than a Rubik’s Cube but can be solved in pretty much the same way.

For that matter, the availability of a 45° face turn in our described puzzle would probably make it easier to solve than a normal Rubik’s Cube. At least the permutation aspect reduces into an almost-trivial puzzle that can be solved by spamming commutators/conjugates, after which the orientation could be solved with the same technique or the usual Rubik’s Cube algorithms. Using commutators is a particularly easy “first principles” way of solving puzzles that behave sufficiently like groups, but generally interesting puzzles don’t have simple commutators to exploit. Huge parts of my two gigaminx solves were done through conjugated commutator spam, for example, and considering that they both took more than an hour, this also highlights how incredibly inefficient solving with commutators/conjugates can be when they involve more than just a few moves. In this case, taking just two faces of the 45°-face-turn cube and ignoring orientation reduces to a (5,3,5) rotational puzzle, which is easy to solve with simple commutators.

Now, suppose we also add 45° turns to slices, like the Mixup Cube. This monstrosity can mix every cubie together and in all likelihood can never be manufactured. Every piece has 24 possible orientations and every permutation of the 26 cubies is possible. I’m not sure about what the orientation subgroup is like, but I guess there are either three or six orbits since each move changes the total orientation by a multiple of 45°. Assuming that there are three orbits and that the centre cubie orientations are distinguishable, this would have 26!\cdot24^{26}/3\approx1.2\cdot10^{60} positions.

Update: I borked the HTML which caused half the post to vanish when viewed from the front page. Also expanded on some stuff.