# Number of Pi in file – Perl weekly challenge, week 4

A new challenge appears!

## How much π in your script?

At first glance, part 1 of this challenge is pretty simple:

Of course, I had to create the file using echo to avoid have a newline at the end. Look close and there’s a problem though.

That’s **almost** but not *quite* 16 significant digits of pi. I’m keeping this
as a first solution though, because IMHO it *should* be the answer.

Okay, time to break out the cynicallest solution for perl6:

15 significant digits of π for 15 characters, including the line break 🤪.

Now let’s get serious. Number sequences were actually one of my favourite parts of Mathematics, and when the world presents me with an opportunity to strike a Calculating π shaped nail, I’m going to hit it with my convergent sequence hammer.

### Isn’t that a bit far away from the original question?

Yeah, I doubt this was the challenge’s intention; I’m doing it anyway.

Interestingly enough, revisiting *last* week’s challenge brought up something
about calculating π using Pascal’s Triangle; apparently since I was last doing
things with Blaise Pascal’s work in high school, one Jonas Castillo Toloza
discovered another place it exposed
π – in the
triangular numbers.

I implemented this in Perl6; it went something like this:

Which is functional, and if you try out a couple of different sizes of $lim you
can see it converging; keeping in mind that Perl6’s `pi`

is apparently accurate
to the 15 digits it **has**:

```
> pi
3.141592653589793
> 2 + [+] $Ts[^2000]
3.1415921540896665
> 2 + [+] $Ts[^80000] # Jump of 40x, 3 digits closer
3.1415926532772707
> 2 + [+] $Ts[^160000] # 2x, one more digit
3.1415926535116068
> 2 + [+] $Ts[^320000] # 2x, closer but 11th digit is still wrong
3.141592653570272
> 2 + [+] $Ts[^640000] # 2x again, there we go
3.1415926535849534
> 2 + [+] $Ts[^2**20] # 1048576; many iterations
3.1415926535880487
> pi
3.141592653589793
```

… that’s a whole megasequence to still be accurate accurate to only 12 digits. That speed of convergence is effectively nonfunctional.

I’ve used a much faster algorithm in the past; The Euler Convergence Transformation, which is:

(Where *k!!* is the odd-only factorial of *k*)

Now, we **could** implement the sequence discretely according to probably the
second summation (this *k!!* seems a bit of a pain to implement), but if you
squint a bit at the right hand sequence, it looks a bit like:

Which saves us some calculation as during a gather / take we already know what
*n _{k-1}* is. Throw it together, sum the results, multiply by two, and
Bob’s yer uncle.

While we’re at it, we’ll use FatRats to be away with those pesky IEE754 floats and their imprecision.

Through some analysis I found that 608 iterations was enough to give me 177 correct significant digits, which is the final size of the script; that’s quite a lot better than 1M iterations to get 12…

### Algorithmic Script Size

‘Enough tedious maths!’ you say, ‘tell us something about programming!’

Cool feature of Perl 6 – you can find the size of the current script using
`$?FILE.IO.s`

. To round out the script I used that (+ 1 for the decimal point)
as the end of the substring of my calculated π.

See my solution at https://github.com/fjwhittle/perlweeklychallenge-club/blob/master/challenge-004/fjwhittle/perl6/ch-1.p6

## Letters in words in list in … ?

Part 2 of the week 4 challenge starts with “You are given a file containing a list of words (case insensitive 1 word per line) and a list of letters” however doesn’t provide any such data. I have to admit I’m not a big fan of challenges with undefined data sets, although I can also certainly appreciate that providing data for testing is potentially not something challenge authors have time for. The challenge itself is fairly similar to an anagram generator I had a go at making for my own fun some time back (around the release of 6.c).

### Finding data.

Hmm. Where would I find a list of words lying around waiting to be used?

```
$ time perl6 -e 'put + "/usr/share/dict/british-english".IO.lines.unique'
101921
real 0m0.593s
user 0m0.671s
sys 0m0.065s
```

Seems reasonable. Next step is to get a list of letters… Oh, let’s just use command line arguments.

One of my favourite things about Perl 6 is how easy it is to get arguments from
the command line. I normally make my main script file `unit sub MAIN();`

, which
lets me treat it otherwise like a script. I can then use Pod to document the
options as well.

We’ll approach the problem using Bags and the subsets thereof. We use Bags instead of Sets to count duplicate letters.

We’ll comb through each of the gobbled arguments for letters, which will allow the user to enter words on the command line, so map the @letters array to lower-case, comb each argument for letters, flatten, and convert to a bag..

`.hyper`

makes the `.map`

happen in parallel. Maybe not a huge deal for this
step, however when now building a list of word bags out of a 102000 line file it
makes the 30 second process take 10 (on my system – an old Athlon II. It
doesn’t even have SSEv4, but it **does** have 4 cores).

Use of a pair here allows us to map a word bag to the unmodified word
preserving order, punctuation, and case.
It’s now a pretty simple task to find our words; we just grep the `@words`

list
for a key that’s a subset of or equal to the `$letter-bag`

using the `⊆`

operator, and print out the corresponding values.

```
$ perl6 ch-2.p6 /usr/share/dict/british-english hello dolly
Dell, Doe, Dole, Dolly, Dooley, Doyle, Eloy, Hell, Holley, Holly, Hood, Hoyle,
Hyde, Leo, Lloyd, Loyd, Lyell, Lyle, Odell, doll, dye, ell, he'd, he'll, held,
hello, hey, hod, hoe, hoed, hold, hole, holed, holy, hooey, led, lode, loll,
lolled, lye, ode, oho, old, oleo, yell, yodel
```

Looks good to me 😊. See the full solution at https://github.com/fjwhittle/perlweeklychallenge-club/blob/master/challenge-004/fjwhittle/perl6/ch-2.p6

For information on your privacy including GDPR details, see Github's privacy statement.