Friday, March 16, 2018

Old Phone/Tablet as an Info Board Part 2: Direct API queries

In the previous post, we discussed using iframe for an information widget on our info board, noting that it would be too heavy on your browser if your target web page is feature-rich. This means you can forget anything like a Google maps snippet.

However, precisely with this in mind, many large websites have developed APIs that other websites (read: we) can use. Google does a great job providing its maps API, so incorporating local traffic can be done as simple as

 
<div id="map" class="basic" style="border: none; position: absolute; right: 10px; top: 10px; width: 415px; height: 350px;">
</div>

<script async defer
    src="https://maps.googleapis.com/maps/api/js?key=(get_your_own_key)&callback=initMap">
</script>
 
 <script>
  function initMap() {
     map = new google.maps.Map(document.getElementById('map'), {
       zoom: 13,
        center: {lat: 44.444, lng: -77.777} // Change these parameters to your location
        });

        var trafficLayer = new google.maps.TrafficLayer();
        trafficLayer.setMap(map);
      }
</script>


Obviously to make this work, you will need to get you own Google API key, and change the map location (ans possibly, zoom) to where you would like your map to display. The easiest way to find it would be to open your Google Maps view and then look at the URL to find the values for latitude and longitude.

Now let us take a step further and provide a widget to monitor the duration in traffic of a given trip in real time. For added flavor, we will compute both the travel time in both directions, where the outbound trip is to start now and the return trip would start in the future.

For this, we define the interface

 
<div id="travel" class="basic info" style="position: absolute; left: 150px; bottom: 190px; width: 415px; height: 60px; background:rgb(255,255,225);">
<span id="log1" style="font-size: 10px; color:rgb(200,200,200); position: relative; top: 0px;">Not loading</span><br/>
<span id="log2" style="font-size: 10px; color:rgb(200,200,200); position: relative; top: 2px;">Not loading</span><br/>
<span id="results" style="position: relative; top: 10px;"><span id="result1" style="font-weight: bold;">. . .</span> / <span id="result2" style="font-weight: bold;">. . .</span> <span id="resultkm">...</span></span>
</div>


and poll the Directions API like this:

 
function navigate(){
 $("#log1").text("load...");$("#log2").text("load...");
 var origin = "44.44444, -77.77777";
 var destination = "43.33333,-78.88888";
 //Change these to your origin and destination

 var directionsService = new google.maps.DirectionsService();
 // var directionsDisplay = new google.maps.DirectionsRenderer();
 // directionsDisplay.setMap(map)
    var request1 = {
 origin: origin, destination: destination, 
 travelMode: google.maps.DirectionsTravelMode.DRIVING,
 drivingOptions: { departureTime: new Date(Date.now()+0), trafficModel: 'bestguess'}
 };
    var request2 = {
 origin: destination, destination: origin, // return trip
 travelMode: google.maps.DirectionsTravelMode.DRIVING,
 drivingOptions: { departureTime: new Date(Date.now()+1000*60*30), trafficModel: 'bestguess'}
        // trip stars 30 minutes in the future
 };
   var fAlert = "rgb(200, 0, 200)";
   var fWarn = "rgb(255, 0, 0)";
   var bOK = "rgb(225,255,225)";
   var bAlert = "rgb(255,255,200)";
   var bWarn = "rgb(255,180,180)";
     
   directionsService.route( request1, function( response, status ) {
    if ( status === 'OK' ) {
        // directionsDisplay.setDirections(response);
        var point = response.routes[ 0 ].legs[ 0 ];
 var d=new Date();
 $( '#log1' ).html(d.toString());
        $( '#result1' ).html(point.duration_in_traffic.text);
    $( '#resultkm' ).html(' (' + point.distance.text + ')' );
 if (point.duration_in_traffic.value > 16*60) {$("#result1").css("color",fAlert);};
 if (point.duration_in_traffic.value > 25*60) {$("#result1").css("color",fWarn);};
 $("#travel").css("background-color",bOK);
 if ($("#result1").css("color")==fAlert) {$("#travel").css("background-color",bAlert);};
 if ($("#result1").css("color")==fWarn || $("#result2").css("color")==fWarn ) {$("#travel").css("background-color",bWarn);};
    }
} ); 
   directionsService.route( request2, function( response, status ) {
    if ( status === 'OK' ) {
        var point = response.routes[ 0 ].legs[ 0 ];
 var d=new Date();
 $( '#log2' ).html(d.toString());
        $( '#result2' ).html(point.duration_in_traffic.text);
 if (point.duration_in_traffic.value > 16*60) {$("#result2").css("color",fAlert);};
 if (point.duration_in_traffic.value > 25*60) {$("#result2").css("color",fWarn);};
    }
} ); 
}
Note that as per Google's use policies, you will need to display the directions and route on a map if you use this function on a website that other people can see - just uncomment the corresponding DirectionsRenderer code lines. For your own use, and at your own risk, I believe you can forego this for the sake of readability if you know what you are doing. There is a caveat, though, in that you won't know the exact route that the time was calculated for.

Here are the examples, showing three possible traffic situations:
As usual, your mileage may vary:
  • You can implement more sophisticated logic of coloring and alerts - an obvious candidate would be analyzing the difference between .duration and .duration_in_traffic
  • You can analyze the suggested best route and alert if it happens to be different from the default route (which you can determine by making a request when there is as little traffic as possible, i.e. in the middle of the night) - this will indicate a major congestion.
  • You can compare travel time along a predetermined route (by setting many waypoints in the most congested portion) and the chosen preferred route;
  • You can even log / graph the travel time gathering your own statistics and storing it in an SQL database on the DiskStation. This way, should Google's API become unavailable, you will have a fallback method to determine travel times based on historical values. 
As far as the billing goes... Even if we poll the server every minute round the clock (which is totally overkill), we still won't exceed Google free usage quotas. And even if we did, once debugged and calibrated, this is such a useful service that you may seriously consider paying for it.

Thursday, January 18, 2018

Old Phone/Tablet as an Info Board Part 1: IFRAME's and their limitations

This continues our series on making an info screen. Last time, we created a skeleton layout, so let us begin filling it with contents.

As an example, let us try to display current and hourly weather using this webpage:
https://www.theweathernetwork.com/ca/hourly-weather-forecast/ontario/mississauga

Highlighted are regions I'd like to put on the info board.

The most straightforward way of putting something from the third-party website into your own would be an IFRAME tag, of this global format:
<IFRAME scrolling="no" src="..." style="..."></IFRAME>

Now usually you would only need some portion of the website displayed on your screen. Unfortunately, if the contents of your IFRAME is from the third-party website, you cannot interact with its content (with a very few exceptions) due to the commonly accepted same-origin policy. (Annoying as it is in our case, this limitation is what prevents a fair amount of malicious attacks.)

However, the desired portion of the website can be extracted via re-positioning the iframe using this negative margin trick:

style="margin-left: -(XXX)px; margin-top: -(YYY)px;"

To zoom in or out on the corresponding website, the only way is to use CSS transform property, like so:

<div id="weather1" class="basic" style="position: relative; left: 5px; top: 10px; width: 500px; height: 180px;">
<iframe scrolling="no" src="https://www.theweathernetwork.com/ca/hourly-weather-forecast/ontario/mississauga" 
style=" -webkit-transform: scale(0.72);  -webkit-transform-origin: 0 0;
 transform: scale(0.72);  transform-origin: 0 0; 
        margin-left: -20px; margin-top: -200px; 
 border: 0px none; height: 8120px; width: 750px;"> 
</iframe></div>

<div id="weather2" class="basic" style="position: relative; left: 5px; top: 20px; width: 500px; height: 200px;">
<iframe scrolling="no" src="https://www.theweathernetwork.com/ca/hourly-weather-forecast/ontario/mississauga" 
style=" -webkit-transform: scale(0.72);  -webkit-transform-origin: 0 0;
 transform: scale(0.72);  transform-origin: 0 0; 
        margin-left: -30px; margin-top: -690px; 
 border: 0px none; height: 8120px; width: 750px;"> 
</iframe></div>
(The -webkit- prefix is needed for browsers like the PlayBook's (or Safari); some other browsers may need other prefixes.)
This gives us something like:


As you can see, this method is very easy to code and there is no need (and no possibility for that matter) to do any rearrangement of the displayed information. The target website takes care of that for you.


Two major pitfalls (besides the above mentioned inability to interact with the iframe contents) are:
  1. Manual adjustment of the margin is very unreliable. Granted, other methods are prone to failing once the target web site undergoes a redesign, but here even a minor change of the layout would screw the placement of your desired content and require re-adjustment. What is worse, this may happen even without a website redesign proper, due to some external content (e.g. ads) affecting the elements' location and sizing. So your screen can intermittently show the wrong content, and may need frequent readjustments.
  2. Even though most of the iframe's target website will be hidden, it will still be loaded and processed (all its scripts, embedded videos, plugins, and ads included), which makes it very heavy on the client browser (especially on older hardware such as the PlayBook). Using transformation makes matters much worse (I guess it may even force the browser to have to "invisibly" render the entire page - how else would the browser know how to scale it?). In my testing, the above example rendered my PlayBook rather unresponsive. 
So, this method would be prohibitively slow for many practically relevant cases. Still, it is a simple and viable method so long as the target URL is rather lightweight and not too loaded with dynamic HTML or embedded media. A good candidate is a mobile webpage or a page specially designed to be embedded, like this: 

<div id="weather1" class="basic" style="position: relative; left: 10px; top: 10px; width: 300; height: 185px; background: white;">
<iframe scrolling="no" src="http://weather.gc.ca/wxlink/wxlink.html?cityCode=on-24&lang=e" allowtransparency="true" 
 style="border: 0px none; height: 185px; width: 300px;"></iframe>
</div>



Friday, January 12, 2018

Old Phone/Tablet as an Info Board Intro: Backstory and Basics

Some time in the past, my loving wife gave me a Blackberry PlayBook for my birthday. As I don't use it much these days (my smartphone has become more versatile and powerful), and would loathe to part with it (it is barely worn and beautiful, and has sentimental value), I would like to give it a second life. 

So in a series of posts I am going to log how I turn the Playbook into an info board: an always-on, always up to date information screen next to the front door, showing some information such as the status of my commute and today's weather. 

Why an information screen in favor of other alternatives? For the same reasons they use departure boards at airports and transit stations: it is the fastest and the least disruptive way to get the important information. You can use it with your hands full (unlike your phone), and you don't have to stand there listening for a robotic voice (unlike Hey Google / Alexa / Siri).

Like so: (and yes, this is a sneak peek into the beta version of the end result):



The DiskStation server I have at home.
Rather than getting the SDK and writing an app (long!!!), I decided to make a web page and host it on my DiskStation (a network attached storage which has a web server function). This approach is much more versatile since it is not limited to the PlayBook or Blackberry. In fact, there will be very few PlayBook-specific points here (mostly limitations: PlayBook uses a rather old implementation of Webkit, and its processor is, by the modern web standards, not the fastest).

On the contrary, the procedures given here should be helpful for many other devices - old iPads, old Android tables, old smartphones (even though a smartphone has a smaller screen and there will be less info that it can meaningfully display) and perhaps something even more exotic like old monitors hooked to something like a Raspberry Pi.

In fact, when the screen is ready, anyone at home can access it from their desktop or phone if they need the info but don't feel like physically going downstairs.


So, to get the job done, we will be combining server-side programming (PHP) and client-side programming (JavaScript / jQuery).

Let's get started by designing an interface:

<html>
<head>
    <title>Info Screen</title>
  <style>
   div.background {background: black; fallback: linear-gradient(180deg, rgb(0,0,0), rgb(25,25,25)); position: absolute; left:0; top:0; height: 560px; width: 1024px; }
   div.basic { background-color: white; border: 1px solid rgb(255,255,255); border-radius: 15px; overflow: hidden; padding: 5px;}
   div.saver {filter:invert(100%);-webkit-filter:invert(100%);}
   div.info { text-align: center; vertical-align: middle;  font-family: "Arial", Helvetica, Sans-Serif; font-size:22px}
  .element {font-size: 12px; text-align: center;}
  .large{background-color: #ffffee;width:650px;height:400px;float:left;}
  </style>
</head>

<body> <div class="background">
<div id="status" class="basic info" style="position: absolute; left: 10px; top: 10px; width: 120px; height: 90px; background: #EEFFF8; color: gray; font-size: 12px;"></div>

<div id="weather" class="basic" style="position: absolute; left: 10px; bottom: 190px; width: 120px; height: 240px; background: #EEEEFF;"></div>
<div id="hourly" class="basic info" style="position: absolute; left: 10px; bottom: 10px; width: 990px; height: 160px; background: white;"></div>

<div id="map" class="basic" style="border: none; position: absolute; right: 10px; top: 10px; width: 415px; height: 350px;"></div>
<div id="travel" class="basic info" style="position: absolute; left: 150px; bottom: 190px; width: 415px; height: 60px; background:rgb(255,255,225);"> </div>

<div id="bus" class="basic info" style="position: absolute; left: 150px; bottom: 270px; width: 415px; height: 50px; background:rgb(255,235,235);"> </div>
<div id="train1" class="basic" style="position: absolute; left: 150px; top: 10px; width: 200px; height: 195px; "></div>
<div id="train2" class="basic" style="position: absolute; left: 365px; top: 10px; width: 200px; height: 195px; "></div>

</div>
</body> </html>

Note that the code above describes only the layout of the elements. In the upcoming posts (there will be 3-4 of them) I am going to discuss in detail how to actually fill the interface with contents, as well as how to script its automatic updates.

(On a side note, it looks like we've lived through a shift of paradigm about what good stuff is.

For centuries - and indeed, persisting all the way into the end of the 20th century - the basic idea of all goods was "the good stuff is the stuff that lasts".

Indeed, in a world where changes are slow and manufacturing is scarce, or expensive, or both, this made total sense. Having to replace anything (from your tools of the trade to the pair of shoes you wear) was an extra burden to be avoided if at all possible; ideally, good stuff would last a lifetime and sometimes even outlast its owners.

But nowadays - at least the "modernized countries" world - this has changed. And the biggest change has been the change of pace. Stuff improves much faster than it wears out. Not only that, but also - with the digital stuff in particular - your device is only as good as the software it works with, and if that software outruns your hardware, bad luck.

To summarize this in a metaphor, we became kids again - the digital kids who outgrow their digital clothes before they have any chance of wearing out. We may happen to have the best smartphone in the world today. But in a few years it will be bugged with so many "apps-that-won't update" and "sites-that-take-forever-to-load" and "services-that-no-longer-work" that using this once-perfect gadget would feel like dressing your five-year-old in clothes that were her favorite when she was three.

Thursday, November 2, 2017

Debugging without a debugger

Another retro post, from even earlier times than the last one.

This happened during my high school years when some of my friends already owned a computer but I had none. So we used to get together after school and binge play some video games -- starting with Lord of the Rings text adventures and Laser Squad hot-seats...

...and then, rummaging through then-abundant "bootleg software shops" (a post-USSR version of Game Stop, selling bunches of floppy disks with copied games or other software and with labels hand-printed on a 9-pin dot matrix printer) I discovered Eric the Unready (which you can actually play in an online emulator here).

I loved it at first sight. A wonderful piece of interactive fiction with hilarious jokes and puns, challenging puzzles and, myself an avid English learner at that time, an invaluable learning resource.

Unfortunately, right after playing through the first chapter, we ran into something annoying: copy protection feature. One of the "Prince of Persia"-type where you would be asked a few questions and would need the original printed game manual to answer these correctly and play on.



And needless to say we didn't have the manual -- and of course, neither did the shop we bought the game from.

Well, as a disclaimer... I do understand that software piracy is, in the big picture, bad bad BAD, but hey, we were 15 years old and had no idea of the big picture - nor any clue about copyrights and licensing. To us at that time, the fact that we had software on our computer meant that we could do as we pleased with it, especially given that we did buy it at a shop (sic!).

And even if someone were to lecture us on the proper course of action... At that time in that part of the world, an equivalent of $30 would be a decent monthly salary (yes, monthly, not daily, not hourly), and there was absolutely no way an ordinary person could possibly make a payment anywhere to a foreign country, or for that matter, to pay in any tender other than cash - no credit cards, no wire transfers, no bank accounts...

...so yes, I admit we were stealing apples from somebody else's garden, but quite unknowingly, almost unavoidably, and without causing anyone any real harm.



But all these sentiments aside, we were already hooked, and needed a way to play on.

Surely we had no Internet to look up the correct answers (there was no Google, no Chrome and even hardly any Internet Explorer yet!), we had no one to ask (the game was so out of mainstream, and the level of English command needed to play it was so untypical that we might well have been the only players in years). We also had nothing to tinker with the game with -- no hiew, no disassembler, no debugger proper.

We did have Game Wizard, a utility that you would normally use to save and reload in Tetris or make yourself infinite lives in Pacman. The way you do it would be to search the memory for "3" when you have 3 lives, then for "2" when you have 2 lives, and so on; with some luck you would find the address in memory that holds the lives variable for the game. You can then set it to 99 or freeze at 3 to get infinite lives.

And we gave it a try, for lack of anything better to do for the rest of the evening. We began by alternating memory searches in the state before vs. after the first question is answered -- hoping to reveal its correct answer by noticing different variable values depending on whether we chanced to answer correctly. Instead, we got:

XXXX:YYYY 01 02 01 02 01 02


As a wild guess I just set it to 4 instead...

...and got right through. (Apparently I inadvertently found the counter of the questions loop and moved right past it.)
All it took after that was to save the game (and the evening), granting us with endless hours of fun time.


The power of one-liners

In modern software engineering where most software is written by large groups of people most of whom seem to dislike reading each other's code. As a result, most organizations have some style guidelines for their code: proper indentation, naming conventions, commenting, you name it.

And most developers will have strong opinions about how code should (and even more so, shouldn't) look like. And they will defend (and, their position permitting, enforce) their opinions with near-religious fervor. Most often, they will yell at you for writing this:

for (i=0;i<n;i++) for (j=i;j<n;j++) if (a[i]>a[j]) {double t=a[i];a[i]=a[j];a[j]=t;} // bubble sort A


and instead insist on something like this:

// Bubble sort array A

for (counter_rows = 0; counter_rows < n; counter_rows++) 
  {
    for (counter_columns = counter_rows; counter_columns < n; counter_columns++) 
      {
        if (a[counter_rows] > a[counter_columns])
          { 
            double temp_variable t = a[counter_rows];
            a[counter_rows] = a[counter_columns];
            a[counter_columns] = temp_variable;
          }
      }
  }


Yes, it looks neat and tidy. But is it really all that readable?

No, not really.

It is very hard to honestly defend a standpoint that a piece of code is easier to read if have to scroll through three screens to read it, as opposed to fitting it on one screen. "But this way it is more organized", comes the objection. Very true, but how is it organized?

It is organized by instructions.

But what for? By instruction is how the compiler looks at the code, but the compiler does not give the slightest damn about your code style. Humans are much more interested in what the code does than in how the code does it (assuming that you, a fellow developer, already have some knowledge of the "how" once you know the "what").

From this standpoint it makes much more sense to organize the code by logically distinct blocks -- important steps of your algorithm that you would put on your flowchart or pseudocode (pseudocode, after all, was invented specifically for this purpose: convey the meaning of complicated code in a simpler, readable, understandable form).

And this means that simple, elegant one-liners -- once (and if) they are self-evident in what they do -- are much more preferable than expanding them on two screens. See for yourselves:

//simple operations, e.g. sumproduct or matrix multiplication
double S=0; for (int i=0;i<N;i++) S+=a[i]*b[i];

for (int i=0;i<N;i++) for (int j=0;j<N;j++) for (int k=0;k<N;k++) c[i][j]+=a[i][k]*b[k][j];

// one-liner error checking, prep or boilerplate
if (failed || !solution_good) return false;

double param; if (!genericParam.Has_Double) throw Error; param = genericParam.Get_Double();

customVector<double> vec(vec1); int vec_n=vec.Count(); double* vec_ptr=vec.Data(); 

//getter/setter methods
double someClass::getSomeProperty() {return someProperty;}

void someClass::setSomeProperty(double arg) {someProperty=arg;}

//etc...


UPDATE: Following some discussion, I feel I need to clear up a confusion here. Any code, prettified, is more readable than the same code, minified. The idea of one-liners isn't about improving the readability of the one-liner code itself! It is about the exact opposite: the one-liner code is assumed to be trivial and therefore not worth going into any great detail about, so the idea is to minify the one-liner code so that it does not get in the way of what's really important and interesting in your code. In other words, it is about improving the readability of the code surrounding your one-liners.


As for naming conventions, they definitely make sense for anything that would be (re)used in several places through the code. If something is set up in one place and is used elsewhere, by all means make the name of the variable (class, object, ...) speak for itself.

That said, still try to keep it short. Calculations in the code are formulas, and formulas read much easier with shorter variables than with long, verbose ones; that's why they introduced variables in textbook formulas in the first place, and they do write E = mgh instead of "Potential_energy = mass * specific_gravity * distance" anywhere beyond grade two at school.

For intermediate variables such as loop counters, simply don't bother. Mathematical names such as a, x, y, i, j, k will perfectly do and they will make your calculations so much easier.

There are exceptions -- sometimes, when naming is especially prone to confusion, do add some mnemonics, such as i_row and i_col rather than i and j, lest you mess up your array indices. But in most cases, formulas in the code need not look any more verbose than they do on your scrap paper.  Sometimes, it is even advisable to assign "long" mnemonic variables to short ones, do the math, and then assign the result back to the long variables.


So -- no, I'm not saying your code should look like Toledo Picochess (see below). But  do write in your IDE as you would write on the blackboard, and do write code as you would write pseudocode.

After all, making code readable is all about making it readable for a human.


P.S. Toledo Picochess looks like this: (now THAT's truly unreadable code!)
#define F (getchar()&15)
#define v main(0,0,0,0,
#define Z while(
#define P return y=~y,
#define _ ;if(
char*l="dbcefcbddabcddcba~WAB+  +BAW~              +-48HLSU?A6J57IKJT576,";B,y,
b,I[149];main(w,c,h,e,S,s){int t,o,L,E,d,O=*l,N=-1e9,p,*m=I,q,r,x=10 _*I){y=~y;
Z--O>20){o=I[p=O]_ q=o^y,q>0){q+=(q<2)*y,t=q["51#/+++"],E=q["95+3/33"];do{r=I[p
+=t[l]-64]_!w|p==w&&q>1|t+2<E|!r){d=abs(O-p)_!r&(q>1|d%x<1)|(r^y)<-1){_(r^y)<-6
)P 1e5-443*h;O[I]=0,p[I]=q<2&(89<p|30>p)?5^y:o;L=(q>1?6-q?l[p/x-1]-l[O/x-1]-q+2
:0:(p[I]-o?846:d/8))+l[r+15]*9-288+l[p%x]-h-l[O%x];L-=s>h||s==h&L>49&1<s?main(s
>h?0:p,L,h+1,e,N,s):0 _!(B-O|h|p-b|S|L<-1e4))return 0;O[I]=o,p[I]=r _ S|h&&(L>N
||!h&L==N&&1&rand())){N=L _!h&&s)B=O,b=p _ h&&c-L<S)P N;}}}t+=q<2&t+3>E&((y?O<
80:39<O)||r);}Z!r&q>2&q<6||(p=O,++t<E));}}P N+1e9?N:0;}Z I[B]=-(21>B|98<B|2>(B+
1)%x),++B<120);Z++m<9+I)30[m]=1,90[m]=~(20[m]=*l++&7),80[m]=-2;Z p=19){Z++p<O)
putchar(p%x-9?"KQRBNP .pnbrqk"[7+p[I]]:x)_ x-(B=F)){B+=O-F*x;b=F;b+=O-F*x;Z x-F
);}else v 1,3+w);v 0,1);}}

Friday, October 6, 2017

Card tricks brute forced

(Now going from lowest-level to highest-level coding)


When I was in middle school, we used a standard 36-card playing deck (from 6 onwards) to play a bunch of games. We also used this deck to do some "loves me, loves me not" type fortune telling where "loves me" was indicated by, essentially, an occurrence of two aces in a row somewhere in the deck.

Much later on I got curious about how likely that outcome was. A short back of the envelope calculation gives
P = [P(A1)*P(A2|A1)]*N 
where 
P(A1) = probability of "there is an ace at position 1 in the deck", 1/9
P(A2|A1) = probability of "there is an ace  at position 2 n the deck if there already is an ace at position 1", 3/35 (3 aces left, out of 35 cards possible)
N = 35 -- number of different positions in the deck where two consecutive aces can occur.

Hence

P = [(1/9)*(3/35)]*35 = 1/3


This looks too high, at first sight. 
So let's write a simple brute-force proof in Wolfram Language (ex-Mathematica):
cards = "6789TJQKA";
adeck = Characters[cards<>cards<>cards<>cards];
testdeck[deck_List] := Length[StringPosition[StringJoin@@ToString/@deck,"AA"]]>0;
(*Monte-Carlo*)
n=100000;For[c=0;i=0,i<n,i++,(thedeck=RandomSample[adeck];If[testdeck[thedeck],c++])]
approx=N[c/n]

It is more or less obvious what the code does: it just tests a large number n of permutations on a deck (using RandomSample[])and then testing whether the resulting deck has at least two aces in a row (searching for "AA" in a deck converted to a string) and counting the number of decks in which this is found.

You can run the code in Wolfram Cloud and make sure the answer is indeed quite close to 0.3
(In hindsight, is it so strange, really? A "loves me, loves me not" trick will only survive among kids if it has a significantly non-negligible chance of a favorable outcome. And I do believe this is how most fortune telling works.)


Naturally you can modify the code very simply to include other card tricks.
For example, you can set cards="23456789TJQKA" for a standard 52-card deck; additionally you can append <>"XX" to cards<>cards<>cards<>cards to include jokers (or <>"AA" if you want them to be wild and count as aces).
Or you can change the testing function to test for any card sequence (like "AK" or "6789"), or indeed modify the criterion to any degree of complexity.

Finally, if you want to differentiate the suits of cards, we will need a slightly more complicated code:

cards = "6789TJQKA"; suits = "SHDC";
adeck = Outer[StringJoin, cards//Characters, suits//Characters]//Flatten;
testdeck[deck_List] := Length[StringPosition[StringJoin@@(First[Characters[#]]&)/@deck,"AA"]]>0;
Isn't it just beautiful how you can combine Map (/@) and Apply (@@) along with Mathematica's pure functions to create tests on lists without unnecessary boilerplate like loops? (And we can verify that making all aces distinct does not change the probability of two of them following each other.)

Finally, I initially planned to do a rigorous (rather than Monte-Carlo) test using Permutations[adesk], but it turns out that Mathematica won't have lists with "more than machine integer" elements. Sad but would probably work (and chances are, will be much faster than Monte-Carlo) with shorter decks.

Monday, October 2, 2017

Text pattern matching, revisited

This is more of a retro post to reflect on one of my very first code experiences.

1. Backstory

Back then, I was a student in an Eastern European city in the middle of a social paradigm change, and as a consequence, with parents struggling to make ends meet. So, even though I did receive a PC (or rather, $500 needed to assemble one) as my prom gift, that PC (with its AMD 5x86-133 processor) was very quickly out-specced by almost everyone in the class...

Long story short, when the city's telephone directory database was leaked and immediately became a very popular piece of software, I was annoyed to find out that it was slow as a snail on a system like mine. It was even more annoying to see that the database, of around 7MB in size, was quite enough to fit entirely in memory, so, given the right shell, we could potentially try to make it faster.

So I was approached by another guy with an older PC and we decided to write such a "fast shell". The first step was to reverse engineer the database, which was quite simple. Each record was 16 bytes, like so:

TT TT TT  NN NN NN  I1 I2  SS SS  SN SN SB SL AP AP 
telephone surname   inits  street  str.#/l    apt.#  

TT -- telephone number 
NN -- last name (integer key)
I1, I2 -- given name initials
SS -- street name (integer key)
SN -- street number
SB -- numeric street number suffix (for numbers like 23/1, pretty common in ex-USSR)
SL -- literal street number suffix (for numbers like 23A, less common but present)
AP -- apartment number

Note that SB and SL could be combined, resulting in a shorter 15-byte record; however the benefit was deemed small compared with having an aligned 16-byte record length, allowing the database file to be very easily browsable in a hex viewer.

The database had some 500-600k entries and was sorted by telephone number (allowing instant look-ups by phone number via binary search). The look-ups by by a specific name or street were very fast as well -- once the integer key for the name was found (again by binary searching, very fast), matching an integer through the entire database took about 1 second.

2. Problem 

What turned out a bit problematic was to look up by an approximate or patterned street name or last name, such as "find everyone whose name matches J?nes and who lives on West* street". On a platform that we had (some protected mode 32-bit Pascal or even standard Borland DPMI -- cannot remember now -- possibly with the use of Turbo Vision), even a simple string comparison for all entries in the database would run for ~30 seconds. Any conceivable pattern matching routine would take up minutes, which was prohibitively long.

To remedy this, we reverted to the assembly language and wrote this: (we assume, for simplicity, that both the pattern and the test string are null-terminated and that the length of the pattern is known in advance):


...
; preparation

mov ecx, __length     ;must be pattern length w/o trailing zero!
mov esi, __pattern    ;pattern string
mov edi, __test       ;test string
mov bh, 0x2A          ;*
mov bl, 0x3F          ;?
...

; main function

_resume:
repe cmpsb
je _pass
mov ah, [esi-1]
mov al, [edi-1]
cmp ah, bh            ;* encountered 
je _pass
cmp al, 0x00          ;test string too short
je _fail
cmp ah, bl            ;? encountered, skip char
jne _fail             ;otherwise -- failed
cmp cx, 0              
je _pass
jmp _resume
...


This routine (at the heart of which was a low-level repe cmpsb which is extremely fast) could handle "?" and the trailing "*" in the pattern (much like in MS-DOS wildcards), going through the entire DB in about 5-6 seconds. What it could not do was to handle "*" in the middle of the string, so as to be able to search for something like Wood*ck. And I wanted this functionality quite badly.

3. Solution

So the idea would be to extend the handling of "*" with the basic idea of  look what's behind "*" in the pattern; keep skipping characters in the test string until it matches or until the string runs out. Finally I came up with this: 


...
_resume:
repe cmpsb
je _pass
mov ah, [esi-1]
mov al, [edi-1]
cmp ah, bh ; * encountered
jne _cont

 inc esi
 dec cx ; skip *
 mov ah, [esi-1] ;look behind *
 cmp ah, 0x00 
 je _pass ;pass if * trailing
_keep:
 inc edi
 mov al, [edi-1]
 cmp al, 0x00 ; out of chars
 je _fail
 cmp al, ah ; next char found
 je _resume ; resume loop; keep cx intact!
 jmp _keep
  
_cont:
cmp al, 0x00 ; test runs out
je _fail
cmp ah, bl ; ? encountered
jne _fail
cmp cx, 0 ; pattern runs out
je _pass
jmp _resume


This allowed full pattern matching in less than 10 seconds, and without using any stack operations - everything is done entirely with registers and minimized memory access.
The only limitation was to disallow constructions such as "*?" (but you could use "?*" instead) and "**" (but you should use a single "*"). (Or on the flipside, this allows to search for literal "*" and "?" in the test string even though it was never practically relevant.)
You can test it out in an emulator by adding some housekeeping code for I/O (just borrowed this from their "Hello, World" example, this will be heavily platform-specific):
  _pass: ;output - pattern matched
     mov edx, 7    ;message length
     mov ecx, __pass    ;message to write
     mov ebx, 1     ;file descriptor (stdout)
     mov eax, 4     ;system call number (sys_write)
     int 0x80        ;call kernel
     mov eax, 1     ;system call number (sys_exit)
     int 0x80        ;call kernel
    
  _fail: ;output - pattern not matched
     mov edx, 11    ;message length
     mov ecx, __fail    ;message to write
     mov ebx, 1     ;file descriptor (stdout)
     mov eax, 4     ;system call number (sys_write)
     int 0x80        ;call kernel
     mov eax, 1     ;system call number (sys_exit)
     int 0x80        ;call kernel

  section .data ;input
     __pattern db 'testi*e',0,0xa 
     __test db 'testicle',0,0xa 
     __pass        db  'Matched',0xa
     __fail        db  'Not matched',0xa
     __length equ 8 ;length of pattern


One may wonder if it made any sense at all to do string matching on every DB entry, rather than generate a list of all key values for matching names or streets and then checking if the key of each entry matches that list. I would agree that the second approach would make sense under most circumstances, and even in those rare occasions where the list would have thousands of entries (like, if we only know the first letter of the name) matching can be made faster using binary search (our names list is sorted, remember?). I was, however, too lazy to write and debug such a matching routine, though.