Project Euler – Problem 64 Solution

Prob­lem

All square roots are peri­odic when writ­ten as con­tin­ued frac­tions and can be writ­ten in the form:

image

For exam­ple, let us con­sider ?23:

image

If we con­tinue we would get the fol­low­ing expansion:

image

The process can be sum­marised as follows:

image

It can be seen that the sequence is repeat­ing. For con­cise­ness, we use the nota­tion ?23 = [4;(1,3,1,8)], to indi­cate that the block (1,3,1,8) repeats indefinitely.

The first ten con­tin­ued frac­tion rep­re­sen­ta­tions of (irra­tional) square roots are:

?2=[1;(2)], period=1

?3=[1;(1,2)], period=2

?5=[2;(4)], period=1

?6=[2;(2,4)], period=2

?7=[2;(1,1,1,4)], period=4

?8=[2;(1,4)], period=2

?10=[3;(6)], period=1

?11=[3;(3,6)], period=2

?12= [3;(2,6)], period=2

?13=[3;(1,1,1,1,6)], period=5

Exactly four con­tin­ued frac­tions, for N <= 13, have an odd period.

How many con­tin­ued frac­tions for N <= 10000 have an odd period?

Solu­tion

(see full solu­tion here).

 

Based on the algo­rithm on con­tin­ued frac­tions from Wikipedia, we can imple­ment the expan­sion algo­rithm as:

image

From the Wikipedia page:

The algo­rithm can also ter­mi­nate on ai when ai = 2 a0, which is eas­ier to implement.

which cor­re­sponds to the ter­mi­na­tion con­di­tion we have in the Repeat active pat­tern (which also checks if the accu­mu­la­tor is empty):

image

Also, this algo­rithm doesn’t work on num­bers that are per­fect squares, i.e. 4, 9, 16, … hence we need to exclude them when search­ing for our answer.

Here’s the solu­tion in full:

image

 

This solu­tion took 92ms to exe­cute on my machine.

Project Euler – Problem 80 Solution

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.

Project Euler – Problem 61 Solution

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.

F# – Imitating Erlang’s bit syntax for easier binary protocol implementation

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.

Elm – building a version of Snake in under 100 lines of code

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