Prob­lem

It is well known that if the square root of a nat­ural num­ber is not an inte­ger, then it is irra­tional. The dec­i­mal expan­sion of such square roots is infi­nite with­out any repeat­ing pat­tern at all.

The square root of two is 1.41421356237309504880…, and the dig­i­tal sum of the first one hun­dred dec­i­mal dig­its is 475.

For the first one hun­dred nat­ural num­bers, find the total of the dig­i­tal sums of the first one hun­dred dec­i­mal dig­its for all the irra­tional square roots.

Solu­tion

(see full solu­tion here).

The premise of the prob­lem itself is fairly straight for­ward, the chal­lenge here is down to the way float­ing points are imple­mented on com­put­ers which lacks the pre­ci­sion nec­es­sary to solve this prob­lem. So the bulk of the research went into find­ing a way to gen­er­ate an arbi­trary num­ber of dig­its of a square root.

As usual, Wikipedia has plenty to offer and the eas­i­est solu­tion imple­men­ta­tion wise is this solu­tion by Frazer Jarvis.

image

which trans­lates to:

image

The rest is really straight for­ward, with the only tricky thing being the con­ver­sion from char to int since this returns the inter­nal inte­ger value instead – e.g. int ‘0’ => 48 and int ‘1’ => 49 – hence the need for some hack­ery in the sum func­tion.

Here is the full solution:

image

 

The solu­tion took 95ms to com­plete on my machine.

Share

Prob­lem

Tri­an­gle, square, pen­tag­o­nal, hexag­o­nal, hep­tag­o­nal, and octag­o­nal num­bers are all fig­u­rate (polyg­o­nal) num­bers and are gen­er­ated by the fol­low­ing formulae:

image

The ordered set of three 4-digit num­bers: 8128, 2882, 8281, has three inter­est­ing properties.

  1. The set is cyclic, in that the last two dig­its of each num­ber is the first two dig­its of the next num­ber (includ­ing the last num­ber with the first).
  2. Each polyg­o­nal type: tri­an­gle (P3,127=8128), square (P4,91=8281), and pen­tag­o­nal (P5,44=2882), is rep­re­sented by a dif­fer­ent num­ber in the set.
  3. This is the only set of 4-digit num­bers with this property.

Find the sum of the only ordered set of six cyclic 4-digit num­bers for which each polyg­o­nal type: tri­an­gle, square, pen­tag­o­nal, hexag­o­nal, hep­tag­o­nal, and octag­o­nal, is rep­re­sented by a dif­fer­ent num­ber in the set.

Solu­tion

(see full solu­tion here),

The tricky thing here (at least for me) was to remem­ber that the six 4-digit num­bers have to come from dif­fer­ent sets, but not nec­es­sar­ily in the order of P3, P4, … P8. Once that is cleared up, the rest is fairly straight for­ward. In the solu­tion linked above, I first cre­ated a set of func­tions for gen­er­at­ing tri­an­gle, square, pen­tag­o­nal, … octag­o­nal numbers:

image

Since the ques­tion con­cerns only 4-digit num­bers, so for effi­ciency sake let’s gen­er­ate the desired 4 digit num­bers ahead of time and safe them for later use:

image

The is4digit pred­i­cate func­tion is self-explanatory. nat­u­ral­Num­bers is an infi­nite sequence of inte­gers start­ing from 1, we use this sequence to gen­er­ate the fig­u­rate num­bers we need, but only keep those that are actu­ally 4 digits.

So far so good, we have all the fig­u­rate num­bers in an array where [0] => P3, [1] => P4, and so on.

 

Next, cre­ate per­mu­ta­tions of the fig­u­rate num­bers such that we exhaust all pos­si­ble sequence of fig­u­rate numbers:

P3 => P4 => P5 => P6 => P7 => P8

P3 => P4 => P6 => P7 => P8 => P5

P4 => P3 => P5 => P6 => P7 => P8

image

(P.S. the per­mute func­tion here comes from the Common.fs source file in the solution)

 

To find the answer to the prob­lem, we process each per­mu­ta­tion to find our answer, take a moment to under­stand this code:

image

 

The processPer­mu­ta­tion func­tion processes one per­mu­ta­tion of the fig­u­rate num­bers and the ter­mi­na­tion con­di­tions for the inner loop func­tion are:

1. we have one num­ber from each fig­u­rate num­ber set and that the last 2 dig­its of the last num­ber = first 2 dig­its of first number

Image

2. we have one num­ber from each fig­u­rate num­ber set but last 2 dig­its of last num­ber <> first 2 dig­its of first num­ber (so close!)

image

3. one of the fig­u­rate num­ber set in the sequence doesn’t con­tain a num­ber whose first 2 dig­its = the last 2 dig­its of the num­ber selected from the last fig­u­rate num­ber set (short-circuited)

Image

 

For each num­ber in the cur­rent set of fig­u­rate num­bers we build up a new pred­i­cate func­tion – e.g. if x = 1282 then the pred­i­cate func­tion would find 4-digit num­bers whose first two digit = 82 – and use it to process the next set of fig­u­rate num­bers in the sequence.

The loop func­tion returns int list option where the int list rep­re­sents the cyclic fig­u­rate num­bers we’re look­ing for, so all that’s left is to unpack the option type and then sum the list.

image

 

This solu­tion took 17ms to find the solu­tion on my machine.

Share

Bit Syn­tax in Erlang

One of the often under-appreciated fea­tures of Erlang is its Bit Syn­tax for pars­ing and pat­tern match­ing binary data at a bit level. For instance, to pare TCP seg­ments you can write some­thing along the line of:

image

image

The same capa­bil­ity can be applied to any­thing binary pro­to­cols, such as video encod­ing, imag­ing, or UDP.

 

Imi­tat­ing with F# Com­pu­ta­tion Expressions

image

 

Whilst this capa­bil­ity is not built into F#, or any other lan­guage that I know of for that mat­ter, we do have a very pow­er­ful, and robust fea­ture in F# in Com­pu­ta­tion Expres­sions.

With com­pu­ta­tion expres­sions, I was able to cre­ate a small library that allows you to write and read data to and from a stream at a bit level. With the bitWriter and bitReader work­flows you will be able to write and parse TCP head­ers with code like the following:

 

The library is avail­able via Nuget:

please give it a try, and let me know if you find any bugs here.

 

p.s. there is still much work to be done on the library. For instance, it’s allo­cat­ing a new buffer array for each work­flow rather than using a buffer pool. If you find this library use­ful and in need for greater per­for­mance, please feel free to con­tribute and help improve the per­for­mance of this library.

Share

It’s been a lit­tle while since I last spent time with Elm, and since Elm 0.13 was recently announced so what bet­ter time to get my Elm hat back on and see what’s new.

There’s a new-look online debug­ger which looks pret­tier than before:

image

but more impor­tant than that, is the new Elm Reac­tor com­mand line tool which pow­ers both the online debug­ger. With the Elm Reac­tor you can run your own time-travelling debug­ger locally and as you edit your Elm source files you can watch your appli­ca­tion update in real-time while retain­ing the abil­ity to go back in time by play back pre­vi­ous events.

There’s also a new com­mand line pack­age man­ager – Elm Get – which gives you the abil­ity to eas­ily add com­mu­nity Elm libraries to your project, or to pub­lish your own libraries to the Elm Pub­lic Library. Over­all it works very sim­i­lar to the how Dart-pub works and whilst I haven’t pub­lished any libraries myself it seems a straight for­ward affair.

There are a cou­ple of small break­ing changes in the core lan­guage, and it’s great to see that F#’s func­tional com­po­si­tion oper­a­tors (« and ») have been adopted and released in this version!

 

Now that I’ve caught up on the changes, I put together a sim­ple imple­men­ta­tion of Snake, and to my pleas­ant sur­prise the whole thing came in at less than 100 LOC although admit­tedly not the eas­i­est 100 LOC I’ve ever writ­ten. I had to really think about what I’m doing (which is a good thing), the lack of IDE sup­port occa­sion­ally gets in the way, and I find the error mes­sage hard to read some­times (although it’s much bet­ter for­mat­ted when you work against Elm Reac­tor run­ning locally.

If you’ve got a few min­utes to kill, why not give it a go:

image

and feel free to check out the source code on Github.

 

Links

Elm Reac­tor – Time Travel made Easy

Elm 0.13 – Archi­tec­ture Improvements

Elm startup project

Elm-Snake project page

Share

On appli­ca­tion monitoring

In the Gamesys social team, our view on appli­ca­tion mon­i­tor­ing is such that any­thing that runs in pro­duc­tion needs to be mon­i­tored exten­sively all the time – every ser­vice entry point, IO oper­a­tions or CPU inten­sive tasks. Sure, it comes at the cost of a few CPU cycles which might mean that you have to run a few more servers at scale, but that’s small cost to pay com­pared to:

  • lack of vis­i­bil­ity of how your appli­ca­tion is per­form­ing in pro­duc­tion; or
  • inabil­ity to spot issues occur­ring on indi­vid­ual nodes amongst large num­ber of servers; or
  • longer time to dis­cov­ery on pro­duc­tion issues, which results in
    • longer time to recov­ery (i.e. longer downtime)
    • loss of cus­tomers (imme­di­ate result of downtime)
    • loss of cus­tomer con­fi­dence (longer term impact)

Ser­vices such as Stack­Driver and Ama­zon Cloud­Watch also allow you to set up alarms around your met­rics so that you can be noti­fied or some auto­mated actions can be trig­gered in response to chang­ing con­di­tions in production.

In Michael T. Nygard’s Release It!: Design and Deploy Production-Ready Soft­ware (a great read by the way) he dis­cussed at length how unfavourable con­di­tions in pro­duc­tion can cause cracks to appear in your sys­tem, and through tight cou­pling and other anti-patterns these cracks can accel­er­ate and spread across your entire appli­ca­tion and even­tu­ally bring it crash­ing down to its knees.

 

In apply­ing exten­sive mon­i­tor­ing to our ser­vices we are able to:

  • see cracks appear­ing in pro­duc­tion early; and
  • col­lect exten­sive amount of data for the post-mortem; and
  • use knowl­edge gained dur­ing post-mortems to iden­tify early warn­ing signs and set up alarms accordingly

 

Intro­duc­ing Metricano

With our empha­sis on mon­i­tor­ing, it should come as no sur­prise that we have long sought to make it easy for our devel­op­ers to mon­i­tor dif­fer­ent aspects of their service.

 

Now, we’ve made it easy for you to do the same with Met­ri­cano, an agent–based frame­work for col­lect­ing, aggre­gat­ing and pub­lish­ing met­rics from your appli­ca­tion. From a high-level, the Met­ric­sAgent class col­lects met­rics and aggre­gates them into second-by-second sum­maries. These sum­maries are then pub­lished to all the pub­lish­ers you have configured.

 

Record­ing Metrics

There are a num­ber of options for you to record met­rics with Met­ric­sAgent:

Man­u­ally

You can call the Incre­ment­Count­Met­ric, or Record­Time­Met­ric meth­ods on an instance of IMet­ric­sAgent (you can use MetricsAgent.Default or cre­ate a new instance with MetricsAgent.Create), for example:

 

F# Work­flows

From F#, you can also use the built-in time­Met­ric and count­Met­ric workflows:

 

Post­Sharp Aspects

Lastly, you can also use the Coun­tEx­e­cu­tion and LogEx­e­cu­tion­Time attrib­utes from the Metricano.PostSharpAspects nuget pack­age, which can be applied at method, class and even assem­bly level.

The Coun­tEx­e­cu­tion attribute records a count met­ric with the fully qual­i­fied name of the method, whereas the LogEx­e­cu­tion­Time attribute records exe­cu­tion times into a time met­ric with the fully qual­i­fied name of the method. When applied at class and assem­bly level, the attrib­utes are multi-casted to all encom­passed meth­ods, pri­vate, pub­lic, instance and sta­tic. It’s pos­si­ble to tar­get spe­cific meth­ods, by name or vis­i­bil­ity, etc. please refer to PostSharp’s doc­u­men­ta­tion for detail.

 

Pub­lish­ing Metrics

All the met­rics you record won’t do you much good if they just stay inside the mem­ory of your appli­ca­tion server.

To get met­rics out of your appli­ca­tion server and into a mon­i­tor­ing ser­vice or dash­board, you need to tell Met­ri­cano to pub­lish met­rics with a set of pub­lish­ers. There is a ready made pub­lisher for Ama­zon Cloud­Watch ser­vice in the Metricano.CloudWatch nuget package.

To add a pub­lisher to the pipeline, use the Publish.With sta­tic method, see exam­ple here.

Since the low­est gran­u­lar­ity on Ama­zon Cloud­Watch is 1 minute, so as an opti­miza­tion to cut down on the num­ber of web requests (which also has a cost impact), Cloud­Watch­Pub­lisher will aggre­gate met­rics locally and only pub­lish the aggre­gates on a per minute basis.

If you want to pub­lish your met­ric data to another ser­vice (Stack­Driver or New Relic for instance), you can cre­ate your own pub­lisher by imple­ment­ing the very sim­ple IMet­ric­sPub­lisher inter­face. This sim­ple Con­solePub­lisher for instance, will cal­cu­late the 95 per­centile exe­cu­tion time and print them:

image

In gen­eral I find the 95/97/99 per­centile time met­rics much more infor­ma­tive than sim­ple aver­ages, since aver­ages are so eas­ily biased by even a small num­ber of out­ly­ing data points.

 

Sum­mary

I hope you have enjoyed this post and that you’ll find Met­ri­cano a use­ful addi­tion in your application.

I highly rec­om­mend read­ing Release It!, much of the pat­terns and anti-patterns dis­cussed in the book are becom­ing more and more rel­e­vant in today’s world where we’re build­ing smaller, more gran­u­lar microser­vices. Even the sim­plest of appli­ca­tions have mul­ti­ple inte­gra­tion points – social net­works, cloud ser­vices, etc. – and they are places where cracks are likely to occur before they spread out to the rest of your appli­ca­tion, unless, you have taken the mea­sure to guard against such cas­cad­ing failures.

If you decide to buy the book from ama­zon, please use the link I pro­vide below or add the query string para­me­ter tag=theburningmon-21 to the URL so that I can get a small refer­ral fee and use it towards buy­ing more books and find­ing more inter­est­ing things to write about here Smile

 

Links

Met­ri­cano project page

Release It!: Design and Deploy Production-Ready Software

Met­ri­cano nuget package

Metricano.CloudWatch nuget package

Metricano.PostSharpAspects nuget package

Red-White Push – Con­tin­u­ous Deliv­ery at Gamesys Social

Share