Happy Pi Day!
It's 2020, this year's Pi Day, it's today
and I would like to do, it's not really today because I'm recording this a couple days early.
But I would like you to see this on Pi Day a coding challenge themed around the number pi
and thank you to FantinBibas
Who suggested this one: Pi Day, find a sequence in pi issue number one four six four
I wonder if those numbers are where they are in pi, we'll find out by the end of this video!
How to look at how one might search for any given sequence of numbers in pi.
Now, I'm in this suggestion, this particular website angio.net/pi is mentioned
it has a bunch of different resources
A resource of where you can download all the digits of pi a place to search for pi
This all reminded me of a wonderful project from Fathom information design.
So if you don't know about Fathom they're an information design firm
founded by Ben Fry who was one of the creators of Processing itself , you can find out more at Fathom.info
But they created this project Peek inside PI, which you can play with at pi.fathom.info
There's also an app version a lot of the versions. I'll link to all those things in the video's description
So the idea here is that I can type or I could tap. Can I tap?
Where is it?
[Tapping]
No it's not working, my touchscreen doesn't work!
The point is for any given sequence like one four one five nine and there it is
It's found at the first digit of pi. So now let's pick another sequence. Like what's a wonderful sequence?
It is today's date is March 14 2020
and that is not in the first 1 million digits of pi. Ah, if only we had more digits. I must have more digits.
[music playing]
Coding train: breaking news!
I'm told that I should search for the number nine nine nine nine nine nine
Which is the 762nd digit of pi
So let's remember that and make sure when I write my own version of this that I find the same digit
I'm gonna do this with p5.js JavaScript in the browser
I'm it's not gonna be as nicely designed with a beautiful interface like this
But I'm first going to recreate this exact thing and then what I'm gonna do
is I'm gonna go from one million digits and go to 1 billion digits
And see if I could still search for a digit in pi
and probably I'm gonna fail because we're gonna need some kind of like Optimization
it's gonna only run too slow
Everything's gonna come crashing down, but I'm gonna try it nonetheless
and we'll see where we get to by the end of this video
I'm starting with a simple p5 sketch and two text files
one with one million digits of pi which is just a Megabyte and one with 1 billion digits of pi which is a Gigabyte
that's a much bigger file. So let's start with the 1 megabyte file
[music playing]
I've uploaded that file to the p5 web editor and I can load all the text from that file right now using preload
[audible typing]
I'm going to just take away animation here. I'm going to get rid of the draw loop and I'm gonna say no canvas
and then the file itself has all of the digits of pi in one line
But loadStrings loads text files into an array with each element of the array being a different line of the text file
so what I'm going to do here is create a variable called digits and just say it is
the first element in that raw data array
Let's console.log digits and just see what happens
Ok, so all of the digits of pi are down here in the console.
Now what I want to do is search for a given digit. Let's make an interface a very very crude simple interface for searching.
[music playing]
Now I have this tiny tiny search box up here. Can I make that bigger?
I also just increased the font size for any input element on the page
So it's a little easier for you to see.
The interaction that I'm looking for is any time anyone types anything into that search box?
I want to look for that string that that those digits in PI itself
[music playing]
And p5.js has a special event function called input
Which you can call on the search box and pass another function that will be executed
Any time a change has been made
So let me write that search it up function because that's when I was looking for something. I say search it up
[music playing]
I'm gonna be a little silly and make these global variables
[music playing]
Then let me get what I'm searching for
[music playing]
From the search box and console.log that
[music playing]
So now whenever I type anything into that search box, I should see what I type here in the console
[audible typing]
And that's working
This is gonna actually be a really easy project to do
You know why? Because I could just use the indexOf function in JavaScript to tell, let me do that real quick
Just please please can I do that real quick? I'm gonna do that real quick.
[music playing]
Digits indexOf search
This is saying look inside the long string digits and give me the index of wherever this string search
Happens to appear. If it doesn't appear. I'll take a negative one, please.
Let's make another element on the page
[music playing]
So now when I get that index back
I can say index P
Dot HTML that index which will put the actual index where it's found in the paragraph text there on the webpage
So for example, if I say 1 4
1 5 9 hmm. Why does it take two so really when counting the digits of pi?
What seems to be the convention is the first digit is the first digit after the period so it's three point
The first digit is one so I should really say
Index minus one and now one four one five nine. I got one and then
what if I say nine nine nine nine nine nine we got it! 999999 appears at the
762nd digit in pi
so if it's a three, I don't want it to find that zero digit so i'm gonna start searching from index two
The chat is also rightfully pointing out that I could just chop off
The first two digits of the string would be much too easy. I'm gonna do it this way
so i'm going to start from looking at digit two
and I'm going to say
as Long as index is greater than zero
Set that, otherwise say...
[music playing]
Otherwise I'll put a message about it not being found
Okay, so let's try one four one five nine nine nine nine nine nine nine not found so I now have
essentially without the care and thought
Into the interaction design, the visual design, the layout of the page all of those elements
Recreated my my own version of this peek inside pi
This video is not over though. I got two more things I want to do.
Number one is I want to just investigate: what does it mean for me to actually perform this search myself?
To write my own indexOf function because maybe if I do
that might unlock some other creative possibilities and also I might learn something about programming
And then let me increase things to one billion digits and see what happens
what breaks down once I have a one gigabyte file that I'm loading all the digits of pi in
as opposed to a one megabyte file. All right, so let's first write our own index of function
so I'm just going to change them to comic this out and I'm going to say
let index equals index of
search in this string for this search string
So search in the string digits, for the string search
[music playing]
And so the function looks like this it's name is indexOf
It needs to receive a block of text and the substring that you're searching for in that text
Let's start with what's the first character in the search string?
[music playing]
Then I want to iterate over the entire string of text
[music playing]
And say hey does this character in the entire string of text
match the first character of the search string
[music playing]
If so, I need another loop
Then I need to loop through all of
the characters of that search string
[music playing]
This is supposed to say four
so I don't need to start at zero because I've already checked to make sure that's zero and I want to check
is text charAt I plus J the same as search charAt J
Again, I'm, I'm not worrying about running this optimally or elegantly. I just want to get the core idea out
[music playing]
So let's say this is my text and what I'm looking for is:
I want to find out where is four one five in that particular string? This is my search
What I have going on here is I know the first character of what I'm searching for is four
So I, the index I is starting here and looking is that four as that four? Is that four?
Is that four AHA this is four!
Now let's, let's save our, let's save this spot and then based on this length three
Which, let's iterate over this length with J
zero one two
And let's add j to i zero one two and see if all those digits continue to match
so ultimately really what I'm looking for here is
any of those digits that aren't the same. So I really want to look for first
I'm going to be very strict about this and use the triple equals and then I'm going to say not equals
I'm going to make a guess that I found it
[music playing]
As soon as I find the first character be the same, aha, I found it and then anytime I find anything to be different
I can now say found equals false. So the question becomes
Right here, if found is true
then I can break out of things
And once one is not true. I don't need to check the rest so I can break out
and then if
found
Return what?
So I'm gonna say let found index equals negative one. I'll give a default value of negative one
and then actually if I've found it
Right here
Found index should equal what
I, wherever we started with I
and then if I've gone through every
Possibility and I haven't found it. Then I'm gonna get to the end and I'm still just going to return
Negative one but found index will have negative one
So if I found it somewhere I'm gonna set it equal to that first index get out of the loop
I don't need to check anymore because I just looking for the first instance and then return what I found
Let's run and see if this works
No, found is not defined sketch line 22
This if statement has got to be inside here
This is where I'm looking at every single character in the large string on searching through
as soon as one of those characters is equal to the start
check every, check all the subsequent characters and then if I found it break out of that larger loop
and keep going so that this should be right now. I'm sure there's other mistakes, but that will be fixed
All right, one four one five nine at digit number one
The chat is giving me a nice suggestion where I could simplify this code where I don't actually need this found index
Because I could just return I
which will automatically break out of the loop. And then if I get to the end I could just return negative one great
So this works
Let's try the 999 thing
[audible typing]
There we go, so this really wraps up a small piece of this coding challenge I have made my own
version of fathom informations peek inside pi. I even wrote my own string search function.
There's so much more that you could do with this to be creative
I mentioned at the top that you could think about what if what you weren't looking for were just
Numbers, but you were looking for some other piece of data that's encoded into numbers
So we could you find secret messages in pi or pieces of music in pi
are there other kinds of algorithms that you could explore
that you could optimize this particular search algorithm with
And I'll list some of those in the video's description
That's a little challenge out to you to research some of those and tell me about your favorite substring search algorithm in the comments
but those are going to be needed for when I take the next step and
Attempt to get this working with a billion digits of pi and for that. I'm also going to need a node server
so at the very least I could be like, okay, let's run this exact same code, but now let's take a
Text file that has a billion digits of pi. So I'm gonna go back to add file here. And I'm gonna go back to my
File system. I'm gonna come over here. I'm gonna find my billion digit PI file
Drag that into the browser here and
mmm, the web editor will not let you upload a file that big and even if it could am I really gonna expect my
Client-side code to load. Well a one gigabyte file with a billion characters in it. Now there's plenty ways probably that file could be compressed
Encoded a different way. I probably get down to like 600 megabytes or something
But whether it's 600 megabytes or a gigabyte, I've still really got the same problem. I have this like huge file
So rather than try to work with it client-side in any type of clever way
I'm just going to use a node application
by the way
I could probably do this in processing because a desktop piece of desktop processing is not gonna have any problem loading a really large file
But I want to stay into JavaScript
I'm going to create a node server that can load all the digits, store them into memory
and then my client-side JavaScript code could query that node server
now if you've never used node before I do have a few basic beginner tutorials about
installing node and getting set up with node and I'll refer you to those but I'm gonna start from the point where I have
a directory with a blank JavaScript file
A package dot JSON file to describe my project that I'm building and both a million digit and
Billion digit file of Pi so I'm going to start by working in index.js
to write some code to load that file. So first I need to require the filesystem module
[music playing]
And one thing that I could just do is just with the million digits of pi. Let's just read file sync
Let's just read the whole file in.
[music playing]
Interesting, so the file has been read in but look how it's being displayed. It's giving me the binary information into the console
so I want to tell it that I want to read it as a string and I'll use
Utf-8 so that's a second argument to read file sync and now here we go
And there's all those digits of pi all those 1 million digits
Now let's just change it to, why not change it to a billion. What could possibly go wrong?
Interesting, it did something but it didn't print anything out. So I know this is just basically a bad idea
I don't know whether something crashed or memory ran out but read file sync for a gigabyte file is not a good idea
and I Think what I want to investigate here is createStream createReadStream
So let me just look for that on the node documentation page createReadStream
So createReadStream is a function
I can call to open up a stream for reading the file so I can read it bit by bit
I can kind of track how long it's gonna take
and get what I want and piece it together, it just gives me a lot of options. So let me do that by saying
Stream equals FS.createReadStream and let's go back to the million
[music playing]
And then once I have a stream I believe that I can
Basically handle different events. So for example, I can say stream on data. That's when anything is actually coming in
I can then have a callback function and just
console.log the data
So now if I run this hopefully I'm gonna see all those digits streaming out
I'm still just gonna use the million, the million digit file
Okay, oh I'm getting I'm getting the binary data so probably I can say just data to string
Great so that's the million digits of pi, you're in, I'm sort of curious to do
Console.log like how big are the chunks that it's reading this in?
Yeah, you can see these are the chunks that it's reading the data and they're pretty large
Because I put some line breaks in between each
Chunk of the stream. In fact, I think a lot of examples use the word sort of like a chunk here
So now let's try
1 billion digits of pi
Yeah, okay
[music playing]
Boy this is taking a while.
There we go all 1 billion digits could I possibly just put them all into one string
[music playing]
And then uh-huh, if I have stream on I believe it's end I think there's an end and a close
[music playing]
And by the way, if this arrow syntax isn't familiar to you. It's a nice way of writing
Callback and anonymous functions and there's a lot more to it than that and I have a whole video about arrow fucntions you could watch
[music playing]
Let's just do digits dot length and see if we get 1 billion digits
Digits is not defined
Data!
digits
And look at that, it's 1 billion in 2 because the 3 and the 1 don't actually count
Okay. Now let's just search for a digit. Let's grab my
index of function that I wrote previously
and bring it into the node code
and then let's look for
I'm just going to hard code this, lets search
what was I looking for 9 9 now let's look for 999 and then
IndexOf digits search and then
Console.log index
763 old minus one minus one minus one minus one
Okay, so that works now. Here's the thing
that didn't take very long because that is actually found at 762
does anybody know of a
Sequence of digits that's very very far into the sequence of a billion digits
That would be helpful to know while you're thinking about that. For those of you who will happen to be watching this live
Not in the recorded video that you right now. I'm not you watching this live, but you watching this later or watching
Let's just quickly add in a web server so I can make a call to ask for the location of a given digit
so in this video
I'm not going to go through all of
The pieces of adding a web server and how HTTP requests work and get requests and response and all that stuff
But guess what! If you're interested in a much lengthier series about all of the details that I'm going to add quickly right now
You can find that in the working with data and API's in JavaScript, a learning playlist that I have on this channel
But for now, I'm gonna go and copy paste, I'm gonna copy paste from the code that I have for those examples right here
I want to create an express app
So I'm gonna add an Express app. I want I don't need this database stuff. So I just need to create an app Express
I want to listen at port 3000 and then I need just a get request
So I'm gonna grab this I just want to handle one route
I'm gonna say get whenever I do I'm gonna just call this route search. Actually, I'm gonna call this pi
and then I'm going to use one of those things called resti and routes something like that to
Look for some sequence of digits
Let's call it search. Let's keep it with search some sequence of digits
[music playing]
Request params digits
So basically
I have a simple get request when if ever I run this server any time somebody navigates to search slash some sequence of digits
I'm gonna pull out those digits and just send them back. I'm gonna get rid of just this on end stuff right now
I don't need this. Actually. I'm just gonna write console.log
Billion digits loaded
And let me run the server
Mmm error, oh, I've got to install Express. So Express is a Nice framework for making web servers in node.
Let me run it again
So I'm listening at port 3000 the bindle billion digits are loaded
I'm gonna go to localhost 3000. There's nothing there. But now if I go to
slash search slash 1 like 4 3 3 2 5 4
See it I got it and I sent it back. Guess what I can do now
Really exciting. So if I take this code where I was searching before?
And I bring it up here and I can say search equals
request params digits
Search for it within the digits and then send that response back
But ultimately, I want to turn, make this JSON so I'm gonna say index
I'm gonna make this a nice little JSON object and I'll also send back. What was the search string as well?
So let's try this one more time, and let's switch to a million digits.
So I'm going to just change this to a million digits
Go back to the browser, hit refresh
I've got to restart the server
Go back to the browser and there we go. This particular sequence of digits was found at that index
Let's double check this with Fathoms. Pecan pie. The digits were 4 3 3 2
It's found at the 35572nd digit of pi
Is that what I got. Yes, that's what I got. So my search is working and now
Let's change it. Well, let's get it working from our interface first, then we'll try it with a billion digits
So now I don't want to just do this by hard coding this into the browser
I want to go back to my p5 code
And in my p5 code I'm not going to load the data file there. I don't even need to do the search there
So index of can go to way go away
But whenever I want to search it up
Instead of actually running the search. I'm going to make a get request. So I'm gonna say load JSON
The URL is localhost:3000/search
And then add in the actual search value
This is a string literal which is an incredibly convenient way to put a variable into a string. I'm gonna
I'm gonna call load JSON, got results and then when I get the results
The result comes back in index
And that is where I'm going to put it in the paragraph
[music playing]
And get rid of these things I don't need.
So basically, this is just the interface and the interface whenever a
Interface goes and asks the server to look in the digits
with a server being the one that can handle holding on to those billion digits
But
I need to host this webpage
and the way that I'm going to do that it's use Express the same Express server that is serving up the digits of pi
The index value into the digits of pi to serve up these web pages and that I can do with
Adding like Express static something-or-other. Let me go look back to my older tutorials about this
It's right here app use Express static public
I want to host everything that's in a directory called public which happens to be what I just called it back into the server
There we go
You can see the p5 sketch that I've been working with is in the directory public
We don't need this million digits of pi anymore
There, it's not part of the clients at all. Just part of the server
Let me restart the server
Let me go to localhost
3000
Mmm
Uncaught error: raw is not defined. So I've got some errors in my p5 code. Oh, I don't need
The digits no longer belongs here. There we go. Okay now!
Okay, it's searching, it's always finding negative 2
Because it's searching for this like colon what what where'd that colon come from? Where did I put that in by accident?
Oh! Look at that.
It's just an extra colon that I had actually in the string that goes away, bye, go away colon
It works it's searching in PI, but the searching is happening on the server. So now it's time.
[drumroll]
This is the grand finale of today's Coding Train Pi Day Challenge.
[train whistle]
We are going to search in 1 billion digits of pi to find any given sequence of digits, it is time.
I'm going to do it, let me go back to my server code.
That was anticlimactic, I'm gonna change it to loading the billion digits of pi. I'm gonna restart the server.
Got to wait, it loaded the billion digits. It's now waiting for me, going back to the webpage.
Let me just refresh this web page and I don't know, let's try.
Searching
Question is has it found it. No, it didn't find that
So, somebody needs to fact checks this for me
Is that sequence not in the first billion digits of pi David suggested a string.
Two zero, seven seven five, five one zero. Let's see if that works.
Two zero, seven seven five, five one zero.
This is at digit number 176866377.
That's pretty good. Well, I have an idea
Let's look at what's in that text file the last few digits
[music playing]
Digits dot length minus ten.
I could use like substring or something, but I'm just like afraid
[music playing]
So, let me print out the last ten digits, oh no, no
digits.charAt()
Fun okay. Does it really have to be like this?
I'm doing this in the weirdest most nonsensical way
So with a little detective work
I have determined that these are the last ten digits in the first billion digits of pi
So just to see how slow is the searching I'm gonna refresh this page
and I'm going to paste those last 10 digits in here and we're gonna see how long it takes
[clock ticking]
[congratulatory music plays]
There we go, it found it!
That's not so terrible
So we can even with my crude brute-force algorithm
Find any
Sequence of digits in the first 1 billion digits of pi by having both a server and client talk to each other
So many possibilities here. How could you optimize the search algorithm?
How could you make the API do all sorts of more fun creative things to give you more information about what's in pi?
Could you put this on to glitch? So we could maybe, we could make this.
Glitch is like a hosting website that allows you to deploy different kind of creative web applications
So maybe I could make a version of this that runs on glitch that people could remix
I will include a link to that if I can get it to work in this video's description and
You could just be much more creative about the interface and once again, what are you actually really searching for?
Could you search for secret messages in Pi by thinking about encoding text into digits music in Pi by encoding?
Musical notes and melodies and rhythms into digits, colors into digits. What data could you search for in pi?
And what wonderful things could you discover that way?
And maybe you could find a text file with more than a billion digits!
and make your own version that searches into even larger number of digits of pi
I hope you enjoyed this Coding Train coding challenge for Pi Day
thanks to Fathom information design for the inspiration with peeking inside pi and thanks also to FantinBibas
and all of you watching this liven during the live stream with all of the
Suggestions and help that you offered. I'll see you soon next time on The Coding Train
Have a great day, ride, all aboard, all that nonsense , that catchphrase. It's coming one day. Oh, this is my catchphrase
It's not a phrase. It's a sound, it's a train whistle sound. That's my catchphrase
[train whistle sound]
[outro music]