## Re-approaching the Project Euler Problems: Uh-oh

This all happened one quiet Friday evening.

I was at my laptop happily working away on my new system for tackling the Project Euler problems, and had just got both PHP and JavaScript playing nicely with the Python script (one of many) that I had created, which takes all the data of the language, version, machine specs (OS, memory, that sort of thing). Success! Naturally I had written scripts in each of the 3 languages to tackle – where else to start? Problem 1.

Problem 1 asks you to find the sum of all the multiples of 3 or 5 below 1000, of course for this project I am taking it a bit further and finding the sum of all said multiples below x, but of course it defaults to 1000 if no value of x is provided.

When I hit enter on the JavaScript file for the first successful time my heart leapt with joy as it reported no errors. Then just as quickly that joy turned to suspicion, “that answer looks different to the one Python has been giving me, oh please don’t be”.

This could well mean that all the data I have been collecting thus far is useless. I mean, what good is knowing how long it took a particular script to give you the wrong answer?

And here I was thinking I’d get away without automated testing! *Sigh* yet another bit to add! One of these days I might actually start solving the problems themselves!

The much older and wiser Gavin from 20 minutes in the future: Get away without automated testing? What on earth were you thinking, Gavin? You go ahead and do what you want but I’m going to bed 💤.

## Re-approaching the Project Euler Problems – an Introduction

Avid readers of this blog (of which I’m sure there are many, I mean, there are 14 whole posts on here at the time of writing!) will remember that back in 2019 I started solving the Project Euler Problems, I set myself the task of solving 1 problem a week, writing a bit about it, and posting it every Sunday at 3PM without fail.

Needless to say, I failed. The few posts that did manage to see the light of day are now available under the project euler 2019 tag in all their glory. I started doing the first few in PHP then switched to Python, then wondered why I shouldn’t do them all in both of those languages, then thought about other languages such as JavaScript, C, Rust and C++, then tried to build all sorts of tools to help me manage all of this. Plus how would I store the code to display it? It took me quite a while to settle on Gists which with hindsight really should have been my first port of call. Can I really be sure I’ll be at my desk at 3PM on a Sunday every week for 749 weeks? No, of course I can’t, I’d better automate that part. 749 weeks is just under 14 and a half years. Meaning that if I had kept up with it from the latter half of 2019, it would run to about the end of 2033. My 28-year-old self would then be 42, my newborn infant would be about to start his GCSEs, you see where this is going, it’s a commitment. One way to combat this is to construct some tools around it to help automate it – as well as adding a few supplementary features – such as:

• First of all, I want to make sure my code works, so automatic compilers for the languages that need compilation. These will also need to be tailored to the platform I happen to be running them on, especially given that back in 2019 I only had a clunky old laptop running Ubuntu. I now still have that same laptop, but also a much newer, smaller, Windows laptop, and now a MacBook from my new job. On the plus side this does now give me all 3 of Linux, MacOS and Windows!
• I wonder if there’s a way to get these running on Android/iOS as well! Maybe save that for another day.
• A tool to turn Markdown posts into nicely-formatted blog posts suitable for WordPress.
• A way to automate their publishing for 3PM each Sunday – this is actually the easy part, just write them ahead of time and set their publish dates accordingly. Then again, who’s to say I won’t decide to alter this?
• A tool to upload my code files into Gists (as well as maintaining the whole thing as a Git repo anyway).
• This one is quite troublesome because at the time of writing my way of making sure a Gist for a given problem and language doesn’t already exist is a bit hit-and-miss.
• A WordPress block to pull down all the Gists relating to the problem being viewed.
• This has the same issue, however, as my Gist-uploading tool above. When I was going through the posts to add the project euler 2019 tag, problem 1 believed I’d only written it in C++ and Java!
• A way to manage and maintain all of this, including making updates where necessary.
• Additional feature: It would be nice to include a D3-based scatter plot of how long each language takes to solve each problem given different input values. This in itself is a huge data collection project, meaning I need to store the language, values, results, time taken and machine specs in a CSV for each problem. The latest version of the design for this can be seen on VizHub, and treat yourself to a screenshot below! This may give some insights beyond just “which languages are faster?” such as “does a particular language work better on a certain machine?”, “how do various language cope with higher inputs?” And so on.

So where to even begin with all this? Well, luckily, I’m writing this partway through getting my system built up, so I already have something of an idea of what to do. One thing I have noticed copied across multiple files (most of this automation is being done in Python) is a duplication of the dictionary containing the language names and file extensions. It would be good to get a comprehensive list of the ones I’ll be working on in a separate file wouldn’t it? Luckily I have found this Gist from Peter Pisarczyk (in turned forked from Aymen Mouelhi) which contains what appears to be just about every programming language ever. I haven’t gone through the whole list but I reckon it’s a fairly safe bet that I haven’t even heard of more than half of them!

This then results in the following `languages.json` file – I never knew there were this many file extensions in the known universe!:

At each step I’ll be looking to see what our basic folder structure looks like, so at the moment:

``````project-euler
├get_working_language_extensions.py
└working_language_extensions.json``````

Now as an example, let’s look at what I want each problem folder to look like:

``````project-euler
├problem_x
│├problem_x_timings.csv // To store the info of how long each problem took to solve, also store the input value, language, and machine specs
│├problem_x.c
│├problem_x.cpp
│├problem_x.java
│├problem_x.js
│├problem_x.md // To be converted into the relevant blog post
│├problem_x.php
│├problem_x.py
│├problem_x.rs
│└problem_x.ts
├get_working_language_extensions.py
└working_language_extensions.json``````

And for completeness and to allow me to make my next post in this series but still chronologically after this (albeit not by much), without leaving this one looking a bit short, here is the full file list (for now at least!) Along with a brief explanation, there will of course be full posts explaining these in due course!

``````project-euler
├problem_x
│├problem_x_timings.csv // To store the info of how long each problem took to solve, also store the input value, language, and machine specs
│├problem_x.c
│├problem_x.cpp
│├problem_x.java
│├problem_x.js
│├problem_x.md // To be converted into the relevant blog post
│├problem_x.php
│├problem_x.py
│├problem_x.rs
│└problem_x.ts
├.gitignore // (obviously!)
├c_functions.c // Functions to be imported into C scripts, not sure yet but this may need to be .h, once I dive properly into C I'll find out!
├cpp_functions.cpp // Functions to be imported into C# scripts
├env_info.json // gitignored as it's machine specific
├file_operations.py // All file-related operations
├file_templates.py // Templates for files in each language, hopefully to prepopulate imports, boilerplate, etc. in each folder
├get_env.py // Run this to creat env_info.json above
├github_config.py // Generated tokens for working with my Gists
├github_credentials.json // gitignored as these are the API keys for github_config to use!
├java_functions.java
├js_functions.js
├languages.json // Renamed from working_language_extensions.json in the code block above
├languages.py // Renamed from get_working_language_extensions.py in the code block above
├mkdirs.py // Create all the directories for each problem, may merge this into file_operations.py
├php_functions.php
├problem_descriptions.json // I created this to allow the chart I'm designing to pull down a subtitle, may change how I do this
├publish_to_wordpress.py
├publish.py // A lot of duplicate code between these two, but the idea is that this automates creating the blog posts
├pyfuncs.py
├rust_functions.rs
├ts_functions.ts
├updategists.py // Functions for working with Gists
├wp_config.py // Much like github_config.py but for WordPress
└wp_credentials.json // Again, like github_credentials, gitignored as these are keys``````

## Making a responsive navbar and placing it on a page with a sticky footer.

See it in action on CodePen:

See the Pen Responsive Navbar in page with sticky footer by Gavin Sykes (@gavinsykesuk) on CodePen.

## Starting with the footer positioning

A common issue with placing footers can be a page looking unneat when its content does not reach to the bottom of a user’s viewport. This was not so complicated in earlier times, when the web was still on computers and there were limited different screen sizes.

via GIPHY

Nowadays though, with all sorts of different screen sizes available, and in the mobile age, it is more important than ever to make your content adapt to any screen size.

There are all sorts of ways to do this, mostly involving JavaScript, that have all sorts of dependencies such as fixed-height footers, which considering how dynamic content can be, simply isn’t practical.

Now with recent CSS features though, it is very simple to achieve, in one of 2 ways:

### Flexbox

As the name might suggest, flexbox allows its child items to be displayed in a flexible manner, manipulating their positioning and sizing along an axis, and you as the developer get to decide if this axis is the horizontal or the vertical. To achieve a sticky footer we use flexbox vertically.

Imagine a simple page layout, with a `<header>`, `<nav>` (which we’ll come to sorting later), `<main>` and `<footer>`:

```<header></header>
<nav></nav>
<main></main>
<footer></footer>```

We set our surrounding body tag as a flex container. This in itself doesn’t do anything to its child elements, but it does tell them that they are in a flex container and can use certain properties as a result.

The next important piece of code is telling our `<body>` what to do with its flex children, we want it to arrange them in a column (because we’re stacking everything on top of each other rather than to the side) and not wrap them, we can do this in one line of CSS with` flex-flow: column nowrap;`. I haven’t seen what would happen if it did wrap, and given how we will set up our child elements I doubt it would try to wrap anyway, but if it ever did the results would be bad, so that `nowrap` acts as a safety feature more than anything.

In order to get our header and footer right to the edge of the viewport, it is often useful to set the margins on our `<body>`, and even our `<html>`, to 0, and their minimum heights to 100vh;

One additional thing we can do is set `align-items` to stretch, this stretches all of our elements across its axis, removing the need to set their widths individually.

```html {
margin: 0;
min-height: 100vh;
}

body {
margin: 0;
min-height: 100vh;
display: flex;
flex-flow: column nowrap;
align-items: stretch;
}

footer {
}

}

main {
}

nav {
}```

Now that the container is taken care of, we need to look at the children. The beauty of flex children is that they can stretch and shrink to accommodate any environment, but they can also be set to do the exact opposite of that, which is what we want to do here. We do this by utilising the `flex-grow` and `flex-shrink` properties.

`flex-grow` is set to a number and behaves according to that number in relation to its siblings, if two flex children each have a `flex-grow` value of 1 then they will grow at the same rate, if you change one of them to 2 however then that one will grow at twice the rate of the other one.` flex-shrink` works much the same way only it does the opposite, it shrinks items to fit in the available space rather than growing them to fill the available space.

If you set `flex-grow` to 0 it will not grow at all, and the same applies with shrinking when `flex-shrink` is set to 0.

With this in mind we want our `<header>`, `<nav>` and `<footer>` to keep their height i.e. not grow or shrink, and our `<main>` to take up the rest of the available room.

In order to have our `<main>` take up the rest of the available space, simply set its `flex-grow` to 1, this has the added bonus effect of not needing to set it to 0 on our other elements, as if only 1 element is expanding to take up all available room, no others will.

We should, however, make sure that none of our elements shrink, by setting their `flex-shrink` property to 0. On our `<main>` this can be done by the shorthand property flex, which sets `flex-grow` and `flex-shrink` in a single line, so we can set it to 1 0. It can also set `flex-basis` which you may want to play around with but isn’t really necessary here and defaults to auto.

Strangely, although we don’t need to set `flex-grow` on our other elements to 0, if we use this shorthand property to do it our CSS will end up shorter! Plus it provides a safety mechanism much like setting the `nowrap` on our flex container.

```html {
margin: 0;
min-height: 100vh;
}

body {
margin: 0;
min-height: 100vh;
display: flex;
flex-flow: column nowrap;
align-items: stretch;
}

footer {
flex: 0 0;
}

flex: 0 0;
}

main {
flex: 1 0;
}

nav {
flex: 0 0;
}```

The one (and so far only that I’ve found) drawback to this is that all of your content must be in a line for it to work, you cannot have an `<aside>`, for example, or any other `<div>`s, unless they are directly above or below something else, rather than to the side. This is where grid comes in.

### Grid

Just as the name of Flexbox suggests you can treat its children flexibly, the name of Grid allows you to lay that grid’s children out in a grid fashion.

This now allows us to add additional items to our layout, so rather than just our `<header>`, `<nav>`, `<main>` and `<footer>`, we can now have an `<aside>`.

To get started with our grid we need to set the display of the body to grid, and then define that grid.

```html {
margin: 0;
min-height: 100vh;
}
body {
margin: 0;
min-height: 100vh;
display: grid;
grid-template-columns: 2fr 1fr;
grid-template-rows: auto auto 1fr auto;
grid-template-areas:
"nav nav"
"main main"
"aside aside"
"footer footer";
}```

So what exactly have we done here? Without going too in depth into grid (because grid is insanely powerful and doing that would take us well away from what we’re focussing on here) we have defined 2 columns and 4 rows for a total of 8 cells. The columns have been defined as 2fr wide and 1fr wide, what this means is the left column is 2 portions wide of whatever space is left after any other columns that have rigidly-defined sizes (50px, 30% and so on) and 1fr means 1 portion wide. Essentially our left column in this case takes up 2 thirds and our right column takes up the remaining third.

Looking at our rows, the browser will first look at the rows defined as auto (which means “look at my content and set my height appropriately”) before portioning out the remaining space to the row set to 1fr – in theory as that’s our only fr-defined row, we could have that as any positive number!

Using `grid-template-areas`, in conjunction with the `grid-area` property on our child elements allows us to define where things will go on our page.

```html {
margin: 0;
min-height: 100vh;
}
body {
margin: 0;
min-height: 100vh;
display: grid;
grid-template-columns: 2fr 1fr;
grid-template-rows: auto auto 1fr auto;
grid-template-areas:
"nav nav"
"main main"
"aside aside"
"footer footer";
}
aside {
grid-area: aside;
}
footer {
grid-area: footer;
}
}
main {
grid-area: main;
}
nav {
grid-area: nav;
}```

We have told our `<header>` to fill up all areas where the grid displays header and so on, it is important to note that you cannot set items to be L-shaped or any other shape than a rectangle.

The reason I haven’t just defined one column is because we need our page/application to look good on different screen sizes, so lining all our elements up on top of one another means we can read everything on a small screen then use media queries to rearrange the items on larger screens.

You can define these media queries however you like, but the way I have done it is to go mobile-first (which I always recommend you do as well) and rearrange things as you go up the screen sizes. Borrowing a breakpoint from Bootstrap I have set it to be at 768px wide. If our screen is narrower than that we keep our `<aside>` underneath our `<main>`, and once it hits 768px we move it to the side.

```@media (min-width: 768px) {
body {
grid-template-rows: auto auto 1fr auto;
grid-template-areas:
"nav nav"
"main aside"
"footer footer";
}
}```

Notice how we now only have 4 rows, and that `<main>` and `<aside>` share a row? This is also why the columns earlier were 2fr and 1fr wide, to keep the main content bigger, although you could set this how you want, 3fr and 1fr, 3fr and 2fr, 10fr and 1fr, even 1fr and 1fr!

When doing media queries, if one of them evaluates to true then the browser will overwrite only the rules that are part of that media query, so in our media query we can set only the `grid-template-rows` and `grid-template-areas` property, without having to set `display: grid` or anything else, as it simply keeps the already-defined rule.

By naming our grid areas and setting each element to take up the space defined by those areas, this also means we needn’t do a single thing to our child elements in media queries, simply rearranging the grid layout will move them.

And here we have it! A layout grid that adjusts to your screen size and always keeps the footer at the bottom of the page.

```html {
margin: 0;
min-height: 100vh;
}

body {
margin: 0;
min-height: 100vh;
display: grid;
grid-template-columns: 2fr 1fr;
grid-template-rows: auto auto 1fr auto auto;
grid-template-areas:
"nav nav"
"main main"
"aside aside"
"footer footer";
}

footer {
grid-area: footer;
}

}

main {
grid-area: main;
}

nav {
grid-area: nav;
}

@media (min-width: 768px) {
body {
grid-template-rows: auto auto 1fr auto;
grid-template-areas:
"nav nav"
"main aside"
"footer footer";
}
}```

### TL;DR

#### Flexbox

```html {
margin: 0;
min-height: 100vh;
}

body {
margin: 0;
min-height: 100vh;
display: flex;
flex-flow: column nowrap;
align-items: stretch;
}

footer {
flex: 0 0;
}

flex: 0 0;
}

main {
flex: 1 0;
}

nav {
flex: 0 0;
}```

#### Grid

```html {
margin: 0;
min-height: 100vh;
}

body {
margin: 0;
min-height: 100vh;
display: grid;
grid-template-columns: 2fr 1fr;
grid-template-rows: auto auto 1fr auto auto;
grid-template-areas:
"nav nav"
"main main"
"aside aside"
"footer footer";
}

footer {
grid-area: footer;
}

}

main {
grid-area: main;
}

nav {
grid-area: nav;
}

@media (min-width: 768px) {
body {
grid-template-rows: auto auto 1fr auto;
grid-template-areas:
"nav nav"
"main aside"
"footer footer";
}
}```

## And now the navbar

First of all we need to lay out our navbar’s links inside a `<nav>` tag:

```<nav>
<a class="active" href="#top">Home</a>
<a href="#flex-footer">Flexbox Footer</a>
<a href="#grid-footer">Grid Footer</a>
<a href="#tldr-footer">Footer (TL;DR)</a>
<a href="#navbar">Navbar</a>
<div class="middle"></div>
<a  class="codepen" href="https://codepen.io/gavinsykesuk"  target="_blank"><i class="fab  fa-codepen"></i><span> Codepen</span></a>
<a  class="github" href="https://github.com/gavinsykes"  target="_blank"><i class="fab fa-github"></i><span>  Github</span></a>
<a class="stackoverflow"  href="https://stackoverflow.com/users/8640133/gavin"  target="_blank"><i class="fab  fa-stack-overflow"></i><span> Stack  Overflow</span></a>
<div id="nav-open" class="open-icon">≡</div>
</nav>```

As with our grid, we want to lay it out differently based on the width of the screen we are viewing it on, but also we now want to introduce a bit of JavaScript to prevent the navbar taking up too much space when not needed, and show us all our navigation options when needed. I have used the jQuery library to make our code more concise.

```\$(() => {
\$('#nav-open').click(() => {
\$('nav').toggleClass('open');
});
});```

If you prefer to use raw JavaScript then you can, but all I’ll say is there is a reason I’ve used jQuery!:

```document.addEventListener("DOMContentLoaded",() => {
document.getElementById('nav-open').onclick = (e) => {
document.getElementsByTagName('nav')[0].classList.toggle('open');
}
});```

It looks complicated, but basically what this code does is add a function to an item called nav-open (which we’ll come to later), so that when the user clicks it it either adds or removes the open class as necessary to (or from) the navbar.

Of course there is also the Pandora’s Box of frameworks that would have their own methods of doing this such as React and Vue!

We will use flexbox for our navbar, as it is linear i.e. everything will be in a line rather than some bits being to the side of each other.

```nav {
grid-area: nav;
display: flex;
flex-flow: column nowrap;
align-items: stretch;
position: sticky;
top: 0;
}```

The `position: sticky` and `top: 0` properties tell the navbar that when we scroll away from it on the page, it is to stick to the top of our screen.

As we are mobile-first, we want to set everything inside our navbar to not display, then only pick the items we do want to show.

```nav {
grid-area: nav;
display: flex;
flex-flow: column nowrap;
align-items: stretch;
position: sticky;
top: 0;
}

nav * {
display: none;
text-align: center;
}

nav a.active {
display: block;
}

nav div.open-icon {
display: block;
font-weight: bold;
}```

Depending what you have as your open icon you may not need to set `font-weight: bold`, but in this case I have. What we have done here is set everything within our navbar to not display, and then overridden that in our active link and the opening icon.

Next we need to worry about what our navbar looks like when it is open, meaning that we want to show everything when it has the open class, and hide it when we click the icon again.

`nav { grid-area: nav; display: flex; flex-flow: column nowrap; align-items: stretch; position: sticky; top: 0;}nav * { display: none; text-align: center;}nav a.active { display: block;}nav div.open-icon { display: block; font-weight: bold;}nav.open a { display: block;} `

Now we need to turn to what our navbar looks like on bigger screens, one thing we can do straightaway is set our middle div to `flex-grow: 1 ` to make it push everything to its left all the way to the left, and everything to its right all the way to the right, but as we’re doing it outside the media query we need to also set it to `display: none` so that it doesn’t appear on mobile and take up the whole screen!

`nav { grid-area: nav; display: flex; flex-flow: column nowrap; align-items: stretch; position: sticky; top: 0;}nav * { display: none; text-align: center;}nav a.active { display: block;}nav div.open-icon { display: block; font-weight: bold;}nav.open a { display: block;}nav div.middle { flex-grow: 1; display: none;}@media (min-width: 768px) { nav {  flex-flow: row nowrap; } nav a:not(.active), nav div.middle {  display: block; } nav div.open-icon {  display: none; }}`

So what have we done in our media query? Firstly we have set our navbar to display as a row rather than as a column, set all the links within the navbar to display given that we now don’t need to save any space, and set our middle `div` to display (although it’s empty) to push everything else to the relevant edges as above. Finally as we no longer need our opening button, set it to `display: none`.

## Solving the Project Euler Problems – Problem 2

The main consideration here was how to calculate the Fibonacci sequence without taking up too many resources, a common danger with recursive functions which are often touted as the solution for working out the sequence and other things like factorials. It turns out the Fibonacci sequence as a recursive function is fine up until about the 10th term, but any further than that? Not advisable!

No gists found

The much quicker solution that I’ve found is to do it as an array, which takes simple values for its calculations rather than calling a recursive function again and again and again.

The second performance optimisation is checking whether our Fibonacci number is even, which when doing it a limited number of times, is fine to do just by checking if n modulo 2 is 0, but how many times will we be doing this? Off the top of your head which Fibonacci term is the largest below 4,000,000? The 10th? The 50th? The 1,000th? We don’t know how many until we actually do it. As it happens it’s the 32nd term, 3,524,578. Run that recursive function 32 times!

As division is slow and all we’re using it to do is check if a number is even, is there a better way? Well kind of, we can check if it isn’t odd. This is done by using the bitwise AND operator. This takes the binary representation of a number – 2019’s would be 11111100011 – and it’s that final bit we’re interested in, if it’s 1 then the number is odd and if it’s 0 it’s even. So using the bitwise AND operator to compare any number to 1 checks only 2 bits and avoids division.

## Solving the Project Euler Problems – Problem 1

After stumbling across an article on Medium by Bennett Garner, I discovered the Project Euler problems and that it would be a good idea to showcase my skills in solving them in a variety of ways, as a good starting point to get a code portfolio going, so here goes with – as natural a starting point as any – problem 1!

All of the Project Euler Problems can be found at ProjectEuler.net.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

No gists found

There were 2 ways I considered to tackle this:

• Loop from 1 to 1000 (or as in the code, n) and check each number for dividing by 3 and 5 respectively, adding them to the result if either is true
• Reduce the number of loops by 47% and run our loop $\frac{n}{3}$ + n/5 times (for those interested, 1/3 + 1/5 = 8/15, so this reduction percentage works for any integer), by dividing n by 3, running that loop, adding 3 times each number to the result – which takes division out of the loop as well – then doing the same again, only now having to check (on a smaller loop) if our result was already added as being a multiple of 3.