fretzine

[fretzine]

Cracking Wordle (kinda) with Monte Carlo Simulations: A Statistical Approach to Predicting the Best Guesses

Wordle, the viral word puzzle game, has captivated millions worldwide with its simple yet challenging gameplay. The thrill of uncovering the five-letter mystery word within six attempts has led to a surge in interest in word strategies and algorithms. In this blog post, we delve into the application of the Monte Carlo method—a powerful statistical technique—to predict the most likely words in Wordle. We will explore what the Monte Carlo method entails, its real-world applications, and a step-by-step explanation of a Python script that harnesses this method to identify the best guesses using a comprehensive list of acceptable Wordle words from GitHub.

Understanding the Monte Carlo Method

What is the Monte Carlo Method?

The Monte Carlo method is a statistical technique that employs random sampling and statistical modeling to solve complex problems and make predictions. Named after the famous Monte Carlo Casino in Monaco, this method relies on repeated random sampling to obtain numerical results, often used when deterministic solutions are difficult or impossible to calculate.

How Does It Work?

At its core, the Monte Carlo method involves running simulations with random variables to approximate the probability of various outcomes. The process typically involves:

Defining a Model: Establishing the mathematical or logical framework of the problem.

Generating Random Inputs: Using random sampling to create multiple scenarios.

Running Simulations: Executing the model with the random inputs to observe outcomes.

Analyzing Results: Aggregating and analyzing the simulation outcomes to draw conclusions or make predictions.

Real-World Applications

The Monte Carlo method is widely used in various fields, including:

Finance: To evaluate risk and uncertainty in stock prices, investment portfolios, and financial derivatives.

Engineering: For reliability analysis, quality control, and optimization of complex systems.

Physics: In particle simulations, quantum mechanics, and statistical mechanics.

Medicine: For modeling the spread of diseases, treatment outcomes, and medical decision-making.

Climate Science: To predict weather patterns, climate change impacts, and environmental risks.

Applying Monte Carlo to Wordle

Objective

In the context of Wordle, our objective is to use the Monte Carlo method to predict the most likely five-letter words that can be the solution to the puzzle. We will simulate multiple guessing scenarios and evaluate the success rates of different words.

Python Code Explanation

Let's walk through the Python script that accomplishes this task.

1. Loading the Word List

First, we need a comprehensive list of acceptable five-letter words used in Wordle. We can obtain the list of all 2315 words that will become the official wordle at some point. The script reads the words from a line-delimited text file and filters them to ensure they are valid.

2. Generating Feedback

To simulate Wordle guesses, we need a function to generate feedback based on the game's rules. This function compares the guessed word to the answer and provides feedback on the correctness of each letter.

3. Simulating Wordle Games

The simulate_wordle function performs the Monte Carlo simulations. For each word in the list, it simulates multiple guessing rounds, keeping track of successful guesses within six attempts.

4. Aggregating Results

The monte_carlo_wordle function aggregates the results from all simulations to determine the most likely words. It also includes progress updates to monitor the percentage of words completed.

5. Running the Simulation

Finally, we load the word list from the text file and run the Monte Carlo simulations. The script prints the top 10 most likely words based on the simulation results.

The Top 50 Words (Based on this approach)

For this article I amended the code so that each simulation runs 1000 times instead of 100 to increase accuracy. I have also amended the script to return the top 50 words. Without further ado, here is the list of words most likely to succeed based on this Monte Carlo method:

trope: 10 successes

dopey: 9 successes

azure: 9 successes

theme: 9 successes

beast: 8 successes

prism: 8 successes

quest: 8 successes

brook: 8 successes

chick: 8 successes

batch: 7 successes

twist: 7 successes

twang: 7 successes

tweet: 7 successes

cover: 7 successes

decry: 7 successes

tatty: 7 successes

glass: 7 successes

gamer: 7 successes

rouge: 7 successes

jumpy: 7 successes

moldy: 7 successes

novel: 7 successes

debar: 7 successes

stave: 7 successes

annex: 7 successes

unify: 7 successes

email: 7 successes

kiosk: 7 successes

tense: 7 successes

trend: 7 successes

stein: 6 successes

islet: 6 successes

queen: 6 successes

fjord: 6 successes

sloth: 6 successes

ripen: 6 successes

hutch: 6 successes

waver: 6 successes

geese: 6 successes

crept: 6 successes

bring: 6 successes

ascot: 6 successes

lumpy: 6 successes

amply: 6 successes

eerie: 6 successes

young: 6 successes

glyph: 6 successes

curio: 6 successes

merry: 6 successes

atone: 6 successes

Edit: I ran the same code again, this time running each simulation 10,000 times for each word. You can find the results below:

bluer: 44 successes

grown: 41 successes

motel: 41 successes

stole: 41 successes

abbot: 40 successes

lager: 40 successes

scout: 40 successes

smear: 40 successes

cobra: 40 successes

realm: 40 successes

queer: 39 successes

plaza: 39 successes

naval: 39 successes

tulle: 39 successes

stiff: 39 successes

hussy: 39 successes

ghoul: 39 successes

lumen: 38 successes

inter: 38 successes

party: 38 successes

purer: 38 successes

ethos: 38 successes

abort: 38 successes

drone: 38 successes

eject: 38 successes

wrath: 38 successes

chaos: 38 successes

posse: 38 successes

pudgy: 38 successes

widow: 38 successes

email: 38 successes

dimly: 38 successes

rebel: 37 successes

melee: 37 successes

pizza: 37 successes

heist: 37 successes

avail: 37 successes

nomad: 37 successes

sperm: 37 successes

raise: 37 successes

cruel: 37 successes

prude: 37 successes

latch: 37 successes

ninja: 37 successes

truth: 37 successes

pithy: 37 successes

spiky: 37 successes

tarot: 36 successes

ashen: 36 successes

trail: 36 successes

Conclusion

The Monte Carlo method provides a powerful and flexible approach to solving complex problems, making it an ideal tool for predicting the best Wordle guesses. By simulating multiple guessing scenarios and analyzing the outcomes, we can identify the words with the highest likelihood of being the solution. The Python script presented here leverages the comprehensive list of acceptable Wordle words from GitHub, demonstrating how statistical techniques can enhance our strategies in the game.

Of course, by looking at the list itself it very rarely would allow a player to input the top 6 words in this list and get it right. It's probalistic nature means that although it is more probable that these words are correct, it is not learning as it goes along and therefore would be considered "dumb".

Benefits of the Monte Carlo Approach

Data-Driven Predictions: The Monte Carlo method leverages extensive data to make informed predictions. By simulating numerous scenarios, it identifies patterns and trends that may not be apparent through simple observation or random guessing.

Handling Uncertainty: Wordle involves a significant degree of uncertainty, as the correct word is unknown and guesses are constrained by limited attempts. The Monte Carlo approach effectively manages this uncertainty by exploring a wide range of possibilities.

Scalability: The method can handle large datasets, such as the full list of acceptable Wordle words from GitHub. This scalability ensures that the predictions are based on a comprehensive dataset, enhancing their accuracy.

Optimization: By identifying the top 50 words with the highest success rates, the Monte Carlo method provides a focused list of guesses, optimizing the strategy for solving Wordle puzzles.

Practical Implications

The application of the Monte Carlo approach to Wordle demonstrates its practical value in real-world scenarios. The method can be implemented using Python, with scripts that read word lists, simulate guessing scenarios, and aggregate results. This practical implementation highlights several key aspects:

Efficiency: The Monte Carlo method streamlines the guessing process by focusing on the most promising words, reducing the number of attempts needed to solve the puzzle.

User-Friendly: The approach can be easily adapted to provide real-time feedback and progress updates, making it accessible and user-friendly for Wordle enthusiasts.

Versatility: While this essay focuses on Wordle, the Monte Carlo method’s principles can be applied to other word games and puzzles, showcasing its versatility.

Specific Weaknesses in the Context of Wordle

Non-Deterministic Nature: The Monte Carlo method provides probabilistic predictions rather than deterministic solutions. This means that it cannot guarantee the correct Wordle word but rather offers statistically informed guesses. There is always an element of uncertainty.

2. Dependence on Word List Quality: The accuracy of predictions depends on the comprehensiveness and accuracy of the word list used. If the word list is incomplete or contains errors, the predictions will be less reliable.

3. Time Consumption: Running simulations for a large word list (e.g., thousands of words) can be time-consuming, especially on average computing hardware. This can limit its practicality for users who need quick results.

4. Simplified Feedback Model: The method uses a simplified model to simulate Wordle feedback, which may not capture all nuances of human guessing strategies or advanced linguistic patterns. This can affect the accuracy of the predictions.

The House always wins with Monte Carlo! Is there a better way?

There are several alternative approaches and techniques to improve the Wordle guessing strategy beyond the Monte Carlo method. Each has its own strengths and can be tailored to provide effective results. Here are a few that might offer better or complementary strategies:

1. Machine Learning Models

Using machine learning models can provide a sophisticated approach to predicting Wordle answers:

Neural Networks: Train a neural network on past Wordle answers and feedback. This approach can learn complex patterns and relationships in the data, potentially providing highly accurate predictions.

Support Vector Machines (SVMs): Use SVMs for classification tasks based on features extracted from previous answers. This method can effectively distinguish between likely and unlikely words.

2. Heuristic Algorithms

Heuristic approaches can provide quick and effective solutions:

Greedy Algorithm: This method chooses the best option at each step based on a heuristic, such as maximizing the number of correct letters or minimizing uncertainty. It's simple and fast but may not always find the optimal solution.

Simulated Annealing: This probabilistic technique searches for a global optimum by exploring different solutions and occasionally accepting worse solutions to escape local optima. It can be more effective than a greedy algorithm in finding better solutions.

3. Bayesian Inference

Bayesian inference provides a probabilistic approach to updating beliefs based on new information:

Bayesian Models: Use Bayes’ theorem to update the probability of each word being correct based on feedback from previous guesses. This approach combines prior knowledge with new evidence to make informed guesses.

Hidden Markov Models (HMMs): HMMs can model sequences and dependencies in data, useful for predicting the next word based on previous feedback.

4. Rule-Based Systems

Using a set of predefined rules and constraints can systematically narrow down the list of possible words:

Constraint Satisfaction: This approach systematically applies rules based on Wordle feedback (correct letter and position, correct letter but wrong position, incorrect letter) to filter out unlikely words.

Decision Trees: Construct a decision tree based on the feedback received to explore different guessing strategies. Each node represents a guess, and branches represent the feedback received.

5. Information Theory

Using concepts from information theory can help to reduce uncertainty and optimize guesses:

Entropy-Based Methods: Measure the uncertainty of a system using information entropy and make guesses that maximize the information gained. By choosing words that provide the most informative feedback, these methods can quickly narrow down the possibilities.

Whether you're a Wordle enthusiast or a data science aficionado, the Monte Carlo method offers a fascinating glimpse into the intersection of statistics and gaming. Happy Wordle solving!

[fretzine]

AI, Codewards and more react!

The past week has seen a flurry of new projects come across my desk that I've thoroughly enjoyed building. It's been one of those "give it a try" weeks where I found myself a bit bored and wanting to code as much as possible.

But what to build? Which tech stack do I try? Python? Javascript? Even... rust?

Coding Cup and Kata Challenges

There's the obvious task of learning how to use authentication in Next JS apps which would be very beneficial in work and so I can build some larger scale projects (such as my dog collar finder app - more on that soon!). But, it doesn't really excite me.

So I started to look online and came across this pretty cool idea that University of Sussex have started. It's a coding competition called HackSussex Coding Challenge.

I enjoyed watching other students try and find solutions to coding challenges in only 12 minutes! There were some that I found easy and was able to beat at home, others were a little trickier and it dawned on me that I do NOT know my data structures like the back of my hand. (does anyone?)

I realised that I needed to brush up on those skills, I want to keep on top of it - it would be a shame to forget those important interview skills. A quick google led me to a leetcode alternatice Codewars.

This kata based learning tool is great for me to flex what I know and build on what I don't. I've managed to get through 15 of the easier challenges and aim to do a few a week.

Forekast - The weather app

When browsing the internet for "easy beginner development projects" I realised that I had never built a weather app... And with my improved react skills and the use of some fancy frameworks (lol) I decided that would be a good pursuit.

Let me introduce you all to my weather app, Forekast:

It uses the OpenWeather Free API to pull through weather information based on either the GPS from the mobile device (activated at the top with the location pin) or with a simple postcode search. It works a treat! I ended up ditching the fancy frameworks and went with bootstrap, and yknow what - I actually like how it turned out. I'm no UX designer - don't shoot me!

Using AI to build an image editor

I was scrolling through Twitter when I happened across a rather scary and intriguing video of a man who built an image editing app and deployed it to Vercel within 30 minutes. The AI technology he was using is V0 or v0. This amazing tool, released by Vercel allows users to generate web apps from text prompts - it creates react components and deploys using Next JS and vercel.

I had to give this a go, so decided to do exactly what he did (because I am an original thinker). I used v0 to generate the app below, and I mean it when I say it took less than 5 minutes.

Everything you see above was generated with a number of basic text prompts. You can visit the v0 website here:

v0 by Vercel

A step in the AI direction

It seems everyone has jumped on the AI bandwagon and every dev project has some AI capabilities nowadays. I had yet to delve into this as it seemed daunting, but after a few watches on YouTube of some clever demos and tutorials I decided to give it a go.

I decided to use Chat GPT's Turbo 3.5 AI model and build a pirate AI chat bot that responds as though he is blackbeard the pirate. I thought this was playful and wanted to harness the idea of talking to someone who may be dead or did not exist. I saw a 9 year old girl do this with Harry Potter and it was really good!

It was actually pretty simple to send and retrieve messages from Chat GPT - I thought it was going to be so much harder! This was all done with Vite build React JS.

It's been a busy week, I hope to continue like this and get a few more apps done. I'm hoping to start building more in Next JS over the next few weeks and get that auth figured out.

The plan is to build full stack app that allows users to register their dogs with a profile, some contact information and these profiles will be attached to a QR code. If someone finds their dog they can scan the QR code and they'll be taken to the dog's profile, where they can either send their location via text or give them a call.

I'm hoping this will make a good final year project in University. Not long to go now, only 2 years part time. And I've already done 3 - it's gone so quick!

Happy coding, if you read this thanks - keep up to date by following the blog and get in touch!

[fretzine]

My heads up in the cloud...

Hey there! 🌐 As I wrap up my journey through the Open University’s Web, Mobile and Cloud Technologies (TM352) module, I thought it would be of benefit to myself and to some readers to provide an overview of the module.

It was a good module that saw us build Single Page Applications (SPA) with React.js and use backend services like Node.js and Express to create API's and connect them to databases like MongoDb.

The second half of the module was focused on cloud computing and we found ourselves building OpenStack virtual cloud environments on our own hardware! (This was very fun!)

Introduction to Cloud Computing

Cloud computing is like having a supercomputer at your fingertips without actually owning one. It’s all about accessing computing resources (like storage and processing power) over the internet, on-demand. This means you can scale up or down based on your needs, and you only pay for what you use. Before cloud computing, setting up servers and managing infrastructure was a huge hassle. Now, it’s as easy as clicking a few buttons!

The Main Providers of Cloud Computing

When it comes to cloud computing, a few big names dominate the scene:

Amazon Web Services (AWS): The giant in the cloud world, offering a vast array of services.

Microsoft Azure: A strong contender, especially popular with enterprises.

Google Cloud Platform (GCP): Known for its data analytics and machine learning capabilities.

IBM Cloud: Focuses on hybrid cloud solutions.

Alibaba Cloud: The leading cloud provider in China.

Each provider has its strengths, so the choice often depends on your specific needs and preferences.

Different types of cloud computing

Infrastructure as a Service (IaaS)

IaaS provides the basic building blocks for cloud IT. It offers virtualized computing resources over the internet, including servers, storage, and networking. This model gives you the highest level of flexibility and control over your IT resources, similar to traditional on-premises infrastructure. Think of it as renting a virtual data center where you can run your applications and store your data.

Platform as a Service (PaaS)

PaaS delivers a platform allowing customers to develop, run, and manage applications without dealing with the underlying infrastructure. This service includes operating systems, development tools, database management systems, and more. It simplifies the development process, enabling developers to focus on writing code. Imagine having a ready-to-use development environment where you can build and deploy your apps effortlessly.

Software as a Service (SaaS)

SaaS provides software applications over the internet, on a subscription basis. These applications are managed by the service provider, so you don’t need to worry about installation, maintenance, or updates. Common examples include productivity tools like Google Workspace and Microsoft Office 365. It’s like having your favorite software available anytime, anywhere, without the hassle of managing it yourself.

Serverless Computing

Serverless computing allows you to run code without provisioning or managing servers. The cloud provider handles the infrastructure, scaling, and maintenance. You only pay for the compute time you consume. This model is ideal for event-driven applications and microservices. Think of it as writing code and letting someone else worry about running it efficiently.

Everything as a Service (XaaS)

XaaS is an umbrella term that encompasses various services delivered over the internet. It includes IaaS, PaaS, SaaS, and other services like Network as a Service (NaaS) and Function as a Service (FaaS). This model offers a comprehensive range of services to meet diverse business needs. It’s like having a buffet of cloud services where you can pick and choose what you need.

AI and Machine Learning Cloud Services

These services provide tools and frameworks for building, training, and deploying machine learning models. They offer pre-built models, data processing capabilities, and integration with other cloud services. Examples include platforms that help you create intelligent applications with ease. It’s like having a personal AI lab at your disposal.

Blockchain Cloud Services

Blockchain cloud services offer platforms for building and managing blockchain networks. They provide the infrastructure and tools needed to develop decentralized applications (dApps) and smart contracts. This is perfect for those looking to leverage blockchain technology without the complexity of setting up the infrastructure themselves.

Internet of Things (IoT) Cloud Services

IoT cloud services enable the connection and management of IoT devices. They offer data collection, processing, and analysis tools to help businesses leverage IoT data. Imagine connecting all your smart devices and managing them from a single platform, making your life easier and more connected.

Open Source vs. Closed Source Cloud Computing

This is a classic debate in the tech world. Open source cloud computing means the source code is available for anyone to inspect, modify, and enhance. It’s all about community and collaboration. Examples include OpenStack and Kubernetes. On the other hand, closed source cloud computing keeps the source code under wraps, controlled by the company that developed it. Think of AWS or Microsoft Azure. Open source offers flexibility and transparency, while closed source often provides more polished, user-friendly solutions.

Introduction to OpenStack Cloud Computing

OpenStack is an open-source cloud computing platform that lets you build and manage both public and private clouds. It was born from a collaboration between Rackspace Hosting and NASA. OpenStack is made up of various components (called projects) that handle different aspects of cloud computing, like compute, storage, and networking. It’s highly customizable and can be tailored to fit specific needs, making it a favorite among organizations looking for flexibility.

Common components of OpenStack Cloud

Designing an OpenStack cloud involves several key components:

Compute (Nova): Manages virtual machines.

Networking (Neutron): Handles network connectivity.

Storage (Swift and Cinder): Swift for object storage and Cinder for block storage.

Identity (Keystone): Manages authentication and authorization.

Dashboard (Horizon): Provides a web-based interface for managing OpenStack services.

These components work together to create a robust and scalable cloud environment.

Benefits and Risks of Cloud Computing

Cloud computing offers numerous benefits, such as:

Scalability: Easily scale resources up or down.

Cost Efficiency: Pay only for what you use.

Accessibility: Access resources from anywhere with an internet connection.

Flexibility: Choose from a wide range of services and configurations.

However, there are also risks to consider:

Security: Storing data off-site can raise security concerns.

Downtime: Service outages can impact availability.

Compliance: Ensuring compliance with regulations can be challenging.

Vendor Lock-In: Switching providers can be difficult and costly.

Legal and Moral Considerations of the Cloud

When using cloud services, it’s important to consider both legal and moral implications. Legally, you need to ensure compliance with data protection regulations like GDPR. This includes understanding where your data is stored and how it’s protected. Morally, consider the environmental impact of data centers and the ethical use of data. Transparency, accountability, and sustainability should be at the forefront of cloud computing practices.

And there you have it! A whirlwind tour of some of the key topics we’ve covered in the TM352 module. Whether you’re a seasoned developer or just starting out, staying updated with these trends and technologies will help you build better, more innovative applications. Happy coding! 🚀

Reflecting on this module, it’s clear that the knowledge and skills we’ve gained are invaluable. From understanding the foundational technologies to exploring the latest trends, TM352 has equipped us with the tools to thrive in the ever-evolving tech landscape. Here’s to many more coding adventures ahead! 🎉

[fretzine]

Reflecting on TM352: Web, Mobile, and Cloud Technologies

Hey there, fellow students and tech enthusiasts! 🌐 As I wrap up my journey through the Open University’s TM352 module, I thought it would be great to share some insights and reflections on what we’ve covered.

So, grab your favorite beverage, and let’s dive into the fascinating world of web, mobile, and cloud technologies!Foundations of the WebOur journey began with the Foundations of the Web.

We explored how Tim Berners-Lee’s vision in 1989 led to the creation of HTML, URI, and HTTP. These technologies are the backbone of the web, enabling us to create and access websites seamlessly. Understanding these basics was crucial as it set the stage for everything else we learned.

Architectures of the Web

Next, we delved into Web Architectures. This part of the module was like learning the blueprint for building a house. We covered:Monolithic Architecture: Building everything as a single, unified application.

Microservices Architecture: Breaking down applications into smaller, independent services.

Serverless Architecture: Writing code without worrying about the underlying infrastructure, thanks to cloud providers.

Each architecture has its pros and cons, and we learned how to choose the right one based on the project’s needs.

Frontend Frameworks

One of the highlights was exploring Frontend Frameworks. These tools make our websites look and feel amazing. We got hands-on experience with some of the most popular frameworks:React: Known for its component-based architecture and virtual DOM.

Angular: Great for building large-scale applications with TypeScript.

Vue.js: A progressive framework that’s easy to integrate.

Svelte: Compiles components into highly efficient vanilla JavaScript at build time.

These frameworks have revolutionized web development, making it faster and more enjoyable.

Microservices

Microservices Architecture was another exciting topic. Instead of building a massive, monolithic application, we learned to create small, independent services that can be developed, deployed, and scaled independently. This approach offers improved scalability, flexibility, and easier maintenance, though it also comes with challenges like managing inter-service communication.

Current Mobile App Development Trends

We also explored the latest Mobile App Development Trends. Here are some of the hottest trends for 2024:AI and ML Integration: Apps are getting smarter with artificial intelligence and machine learning.

5G Technology: Enabling faster, more reliable mobile connections.

AR and VR: Providing immersive experiences in gaming, shopping, and more.

Wearable Tech: Apps for smartwatches and other wearable devices are on the rise.

Blockchain: Secure, decentralized apps are gaining traction, especially in finance and supply chain management.

Mobile App Frameworks

Just like web development, mobile app development has its own set of frameworks. We got to work with some of the top ones:

React Native: Build mobile apps using JavaScript and React, with native performance.

Flutter: Google’s UI toolkit for building natively compiled applications from a single codebase.

Swift: Apple’s powerful programming language for iOS development.

Kotlin: A modern language that makes Android development more enjoyable.

These frameworks help developers create high-quality mobile apps that run smoothly on various devices.

Mobile Web Development Trends

Finally, we looked at Mobile Web Development Trends. Here are a few key trends:Progressive Web Apps (PWAs): Web applications that offer a native app-like experience.

Responsive Design: Ensuring websites look great on all devices.

Voice Search Optimization: Optimizing websites for voice search is becoming crucial.

Accelerated Mobile Pages (AMP): Lightweight pages designed to load quickly on mobile devices.

And there you have it! A whirlwind tour of the TM352 module and some of the most important topics in web and mobile development today. Whether you’re a seasoned developer or just starting out, staying updated with these trends and technologies will help you build better, more innovative applications. Happy coding! 🚀

Reflecting on this module, it’s clear that the knowledge and skills we’ve gained are invaluable. From understanding the foundational technologies to exploring the latest trends, TM352 has equipped us with the tools to thrive in the ever-evolving tech landscape. Here’s to many more coding adventures ahead! 🎉

[fretzine]

Space, Time and Good Code

It's been some time since I last posted to the blog. I've completed my third year studying BsC Computing and IT (Software Engineering)🎉.

In my last post I discussed the Data Structures and Algorithms module (M269) which, as predicted, was a beast. It would be a shame not to cover this module that is so integral to computer science and is genuinely quite interesting (i think so).

What makes some code better than others?

Over the years of trawling through forums and stack overflow I'd heard the term "bad code" and "good code" but it seemed like a subjective distinction that only the minds of the fashionistas of the programming world could make. What makes my code good? Is it the way it looks, how difficult it is to understand? Perhaps I'm using arrays and their using sets, what about string interpolation isntead of concatenation? As it turns out there is a very robust method of measuring the quality of code and it comes in the form of Complexity Analysis.

Complexity analysis is a method used in computer science to evaluate the efficiency of algorithms. It helps determine how the performance of an algorithm scales with the size of the input. By analyzing time and space complexity, we can predict how long an algorithm will take to run and how much memory it will use. This ensures that algorithms are optimized for different hardware and software environments, making them more efficient and practical for real-world applications.

Big O and Theta

Complexity analysis has its roots in the early days of computer science, evolving from the need to evaluate algorithm efficiency. In the 1960s and 1970s, pioneers like Donald Knuth and Robert Tarjan formalized methods to analyze algorithm performance, focusing on time and space complexity. This period saw the development of Big O notation, which became a standard for describing algorithm efficiency. Complexity theory further expanded with the introduction of classes like P and NP, exploring the boundaries of computational feasibility.

Big O notation describes the worst-case scenario for an algorithm, showing the maximum time it could take to complete. Think of it as the upper limit of how slow an algorithm can be. For example, if an algorithm is O(n), its time to complete grows linearly with the input size.

Big Theta notation, on the other hand, gives a more precise measure. It describes both the upper and lower bounds, meaning it shows the average or typical case. If an algorithm is Θ(n), its time to complete grows linearly with the input size, both in the best and worst case.

In complexity analysis, there are several types of complexity to consider:

Time Complexity: This measures how the runtime of an algorithm changes with the size of the input. It’s often expressed using Big O notation (e.g., O(n), O(log n)).

Space Complexity: This evaluates the amount of memory an algorithm uses relative to the input size. Like time complexity, it’s also expressed using Big O notation.

Worst-Case Complexity: This describes the maximum time or space an algorithm will require, providing an upper bound on its performance.

Best-Case Complexity: This indicates the minimum time or space an algorithm will need, representing the most optimistic scenario.

Average-Case Complexity: This gives an expected time or space requirement, averaging over all possible inputs.

There are also several different complexities.

Here are some common types of Big O complexities:

O(1) - Constant Time: The algorithm’s runtime does not change with the input size. Example: Accessing an element in an array.

O(n) - Linear Time: The runtime grows linearly with the input size. Example: Iterating through an array.

O(log n) - Logarithmic Time: The runtime grows logarithmically with the input size. Example: Binary search.

O(n log n) - Linearithmic Time: The runtime grows in proportion to ( n \log n ). Example: Merge sort.

O(n^2) - Quadratic Time: The runtime grows quadratically with the input size. Example: Bubble sort.

O(2^n) - Exponential Time: The runtime doubles with each additional input element. Example: Solving the traveling salesman problem using brute force.

O(n!) - Factorial Time: The runtime grows factorially with the input size.

Here's a diagram that shows the change in runtime for the different complexities:

Data Structures to improve complexity

Throughout the M269 module you are introduced to a variety of data structures that help improve efficiency in several, very clever ways.

For example, suppose you have an array of numbers and you want to find a specific number. You would start at the beginning of the array and check each element one by one until you find the number or reach the end of the array. This process involves checking each element, so if the array has ( n ) elements, you might need to check up to ( n ) elements in the worst case.

Therefore, in its worse case scenario an array of 15 items will take 15 steps before realising that the value is not present in the array.

Here’s a simple code example in Python:

def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1

You need to check each item in an array sequentially because the values at each index aren’t visible from the outside. Essentially, you have to look inside each “box” to see its value, which means manually opening each one in turn.

However, with a hash set, which creates key-value pairs for each element, the process becomes much more efficient!

A hash set is a data structure that stores unique elements using a mechanism called hashing. Each element is mapped to a unique hash code, which determines its position in the set. This allows for constant time complexity, O(1), for basic operations like add, remove, and contains, assuming a good hash function. This efficiency is because the hash code directly points to the location of the element, eliminating the need for a linear search. As a result, hash sets significantly improve search performance compared to arrays or lists, especially with large datasets.

This is just one of the many data structures that we learned can help improve complexity. Some others we look at are:

Stacks

Queues

Linked List

Trees

Graphs

Better Algorithms!

Yes, data structures can dramatically improve the efficiency of your algorithms but algorithm design is the other tool in your arsenal.

Algorithm design is crucial in improving efficiency because it directly impacts the performance and scalability of software systems. Well-designed algorithms ensure that tasks are completed in the shortest possible time and with minimal resource usage.

An example of algorithm design that dramatically improves efficiency is Binary Search.

Binary search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty.

Here’s how it works:

Start with the entire array: Identify the middle element.

Compare the middle element: If it matches the target value, the search is complete.

Adjust the search interval: If the target is smaller than the middle element, focus on the left half of the array. If it’s larger, focus on the right half.

Repeat: Continue this process until the target is found or the interval is empty.

Example: Suppose you have a sorted array ([2, 5, 8, 12, 16, 23, 38, 56, 72, 91]) and you want to find the number 23. Start by comparing 23 with the middle element (23). Since they match, the search ends successfully.

Here is an image of a Binary Search algorithm being applied to a Rooted Tree (a graph with a root node):

Complexity Improvement: Binary search significantly improves search efficiency compared to linear search. While linear search has a time complexity of O(n), binary search has a time complexity of O(log n). This logarithmic growth means that even for large datasets, the number of comparisons needed is relatively small. For example, in an array of 1,000,000 elements, binary search would require at most about 20 comparisons, whereas linear search might need up to 1,000,000 comparisons.

What on earth am i going on about?

Like I said, last year I wouldn't have been able to discern good code from bad code. Now I can analyse the complexity of a piece of code and determine its efficiency, especially as its input grows. I can also see if the programmer has used efficient data structures in their code, rather than bog standard arrays (arrays are amazing btw, no hate).

Ultimately, I feel like this module has definitely made me a better programmer.

[fretzine]

Data Structures and Algorithms

It has been a few months since I completed the second year of my Software Development degree with Open University and I have had the chance to relax, hang with friends and family and not think about coursework for a while.

That being said, in work we are full swing into a full website re-development project which will see us move our CMS into the cloud and re-build the front end using React and Tailwind. This has required a significant amount of time spent ensuring my Javascript is solid and beginning to learn React via online courses. Very much out of the fire and into the pan.

As I look forward to the year ahead I have two modules to focus on: 1. Data Structures and Algorithms 2. Web Technology and Architectures

In preparation for the DSA module (which I know is going to be pretty tough, judging by comments from past students) I have started to read this fantastic book:

I wanted to read this book prior to starting the module as the module can at times be heavy in the mathematics of Algorithms (and maths is not my strong point). If this book allows me to understand the higher level data structures and complexity issues then I can put more effort into understanding the math behind each one.

I'm hoping this will pay off, so far I breezed through the book and have implemented my own recursive binary search, stack, queue and bubble sort.

The images above show my use of recursion when writing new functions, I have started to practice top down thinking which requires imagining that the function itself has already been created, find the base case and sum the result of the first iteration to the function (which in turn recursively calls itself).

I've also been following Primeagen's free Frontend Masters course below: https://frontendmasters.com/courses/algorithms/

I'm hoping that the module will go well, I will try and update you with some further interesting reading and learning.

[fretzine]

Uncle Bob, Alan Turing and Razors.

It's been some time since I've updated the blog with my software development news. It's been a busy two months filled with Java exams, web building, work project deliverables and milestones and a sense of impending doom at the THREE 4 hour exams that I have to sit this week.

That being said, I still like to take the time to discuss some of the interesting things that I've been reading and watching lately. So in this article I will quickly discuss and link to videos across the interwebs that share some very cool ideas that I have encountered during my studies and work.

Uncle Bob's Clean Code

If you haven't heard of Uncle Bob then you need to watch his videos on Clean Code that can be found for free on YouTube. Robert Martin is a highly influential software programmer who was one of the original authors of the Agile manifesto (when it was designed for programmers before the project managers took over). He is known for promoting many different software programming principles, including the well known SOLID principle.

His lectures are fun but more importantly very important to learn.

The Halting Problem

With the development of such powerful computers you'd imagine that the pool of tasks that couldn't be completed by a program would either be small or shrinking. Well, it turns out that it has stayed relatively the same size (at least for the last 20 years). There are some algorithms, some procedures and predicates that cannot be solved by any computer, even supercomputers. One of the many problems that cannot be solved was proven so by Alan Turning. It is called the Halting Problem and it's quite interesting. The video below is a very brief introduction but sums it up nicely and skips all of the logic for those who just want the high level summary.

Razor Pages ( .Net)

I have been working as a web developer for 6 months now and during this time I've been so busy catching up with the current major project which requires very little code that we have yet to delve into any real web design. I've been dealing with small amounts of javascript here and there and designed the odd banner or two in CSS but I have mainly been working on service design and continual service improvement.

This month will see me start diving into the world of .Net from Microsoft. I've been beginning my scouring of their documentation and support sites (Microsoft actually provides good documentation that explains key concepts with very little fuss.) Below is a playlist of introductory lessons from Microsoft and a great starting place for anyone who wants to get into ASP.NET or .NET web developing.

I'm hoping that someone somwhere is interested in any of these videos, if you are let me know on twitter @alexheywood and I will get in touch and we can share resources!

Desperately trying to remind myself that its summer outside and that I should not spend all of my time coding / watching videos on coding.

Speak soon!

[fretzine]

Requirements: Engineering (the software contract)

'Requirements engineering is the branch of software engineering concerned with the real-world goals for, functions of, and constraints on software systems. It is also concerned with the relationship of these factors to precise specifications of software behaviour, and to their evolution over time and across software families.' - (Zave, 1997)

When building a software system it is necessary to define the real world goals that motivate the development of the system. It is important to precisely analyse the system requirements and to validate that those requirements do what customers want, to define what the designers have to build, and to verify that the designers have done it in a correct way. It is also important to note that requirements can change over time and most often develop iteratively throughout the building process.

The important of collecting the requirements, functions and constraints of a proposed system cannot be overstated. It is considered the most important stage of the development process. There has been many examples over the years of projects that have catastrophically failed due to a lack of planning, one example is the London Ambulance Service's 1992 Dispatch System Failure which cost the lives of 42 people.

In the example above there were a number of project killing issues that could have been prevented if the requirements, functions and constraints had been properly examined. Here is a small list of some of the issues that caused the system to fail:

A company was used that did not have experience in large, real-time, safety-critical command and control systems.

The results of an audit were not considered in the selection process of the companies to develop the project.

Requirements were specified by a team of people who did not have a good understanding of the application field.

Requirements were very detailed, focusing on ‘how’ the system should work instead of on ‘what’ the system should do.

Some other important tasks during software development were not executed, such as quality assurance, configuration management, tracking of agreed changes and written evidence of test plans.

Identifying and Defining Problems

It is vital that when developing a software system that the problem it hopes to solve is identified and defined. This can be a challenging but van Lamsweerde (2009) has developed a framework which makes this task easier. It asks that we consider the three dimensions of requirements: why, what and who?

Why?

The why is concerned with the objectives of the software system. In this dimension we precisely define objectives, the consequences of not achieving these objectives and describing the interactions between objectives in the system.

What?

The what is concerned with the functional services (functions) the system provides to the user in order to achieve the objectives stated above. The functional services rely on the 'operations' of the system. They need to meet the constraints of performance, security, usability, interoperability and costs.

Who?

The who dimension is concerned with the assignment of responsibilities to achieve the objectives, functionality and constraints among the components of the system. These include humans, devices and software.

Requirements

Requirements of a system are attributes that satisfy the physical (type of machine, operating system, etc) or functional needs (user details to be recorded, encryption over network etc). Requirements usually describe the characteristics of a system, the properties of a system and the tasks they will execute, the action taken to carry out its tasks and any limitations to the system.

There are several characteristics associated with a set of requirements:

Correct – a requirement should conform to the understanding of the person who defined the requirement.

Necessary – a requirement should have a purpose.

Traceable – a requirement should be associated with its origins.

Non-ambiguous – a requirement should be clear and have a unique interpretation.

Feasible – a requirement should be possible to be developed in the system.

Consistent – requirements of a system should not contradict each other.

Complete – a requirement should represent a behaviour and output for all possible inputs in all states under all constraints.

Testable – a requirement should be able to be checked when implemented in a system.

The identification of a set of requirements is a difficult process and usually requires multiple iterations of the process in order to find all the requirements. Requirements are normally classified as one of two main types: functional requirements or non-functional requirements. 

Functional Requirements

Functional requirements are concerned with the activities and tasks the system must carry out (the what of the system).

Non-Functional Requirements

The non-functional requirements are concerned with how the system achieves its tasks or the ways in which the system should be developed. There are different types of non-functional requirements, we can further categorise them into three groups:

Quality Requirements

These requirements are concerned with the quality properties that the system must have. Some quality properties that a system must have are below:

Safety, Security, Integrity, Availability, Reliability, Accuracy, Performance, Interface.

Compliance Requirements

There are also quality requirements that must adhere to laws, regulations, social norms, cultural and political aspects and standards.

Development Requirements

These requirements describe the way in which the system must be built. It could describe the requirements of the cost, delivery timescales, maintainability, reusability and portability.

Stakeholders

There are several groups of people involved in the development process and use of a system. A stakeholder is a term to describe a person or group of people who are directly or indirectly affected by the system to be built. Stakeholders may influence the way the system is developed or who has responsibility for the acceptance of the system.

Some list of stakeholders are below:

users of the system

the person or people who are paying for the system

people buying the software after release

familiar with the problem domain (area experts)

market researchers who conduct surveys to determine trends and needs

lawyers and auditors who are familiar with the legal and government requirements

the people involved in the development of the system (analysists, developers, testers, technical experts, engineers, designers)

Sometimes a stakeholder can fill all of the roles above or they can be distributed amongst a variety of different groups internal and external.

Requirements Document

The purpose of identifying and defining the requirements of a system is so that we can create a 'requirements document' which acts as a contract between the contractor and the developers. It describes the requirements of the system in an unambiguous and clear way so that the client and developers are clear on the needs, functions and limitations of the system prior to building.

There are two different types of requirements definition documents:

Requirements definition document

Requirement specification document

The specification document is aimted at a technical audience such as the designers, developers, testers and project managers whereas the definition document is aimed at the clients, customers and users of the system.

The definition document provides the basis for the system before you proceed to the build. It also serves as a legal contract between the client and the developer, it should clearly define what the client has agreeed and what the developer is to produce.

They are usually written in natural, non-technical language to avoid confusion.

The requirements definition document should include the basics:

a brief description of the part of the business within which the new software system will operate – the system domain

a description of the functional requirements that the system must meet (in the form of a series of use cases)

a description of the acceptance tests that will be performed to assure the client that all the agreed behaviour is provided by the completed system

a description of the constraints in the system, when such constraints exist.

System Domain?

The system domain is a brief description of the real world context that the system will find itself operating in. It should only contain information that is within the scope of the system and it usually does not contain a lot of detail about the system behaviour.

Use Cases

The developer has to analyse the information gathered about the requirements of the system and define a set of functional requirements. The set of requirements often define what the system does and are usually presented in real life case scenarios which describe the systems functions and goals.

Acceptance Tests

Acceptance testing is an activity that aims to demonstrate to the client that the system works as specified in the requirements document. If the system fails any of the acceptance tests it has failed to meet these requirements and the clients may not accept the software until further work is completed.

Constraints

Constraints are defined as limitations of the new system that is being developed that must be met. Some examples of constraints are:

GUI (Graphical User Interface) must stay the same as the old version

You can only use a certain development software or language

The system must perform to a specific speed and reliability

It must be able to handle multiple concurrent users

Constraints can also occur due to external circumstances, for example laws and societal norms or regulations. You may be required to develop a system that adheres to data protection regulations, the security of data transferred over a network or accessibility concerns for the disabled.

The life cycle of requirements engineering

There are a number of phases that you will go through in the lifecycle of requirement engineering.

The first is "Domain Understanding". In this phase you are required to acquire knowledge of the context of the system (the real world scenario it will live in) and interact with stakeholders to develop a report that identifies the organisation, the domain, any identified problems and ways of addressing those problems. This will then be used in developing the requirements definition document.

The next phase is "Requirements elicitation" which is executed alongside the domain understanding activity. This activity is concerned with the identification and recording of the requirements of the system through data gathering excersises, questionnaires, surveys, teamwork based focus groups, prototyping, model-driven techniques.

The next stage is "Requirements evaluation and negotiation". In this activity, identified requirements are analysed in terms of conflicts, risks, alternative options, priorities, completeness and ambiguity. It may be necessary to hold negotiations with the clients and come to a consensus which results in sections of the requirements definition document.

In the next stage "Requirements specification and documentation" we develop the requirements definition document in the form of a template using a variety of inputs such as general objectives, system requirements, software requirements, environmental assumptions etc.

The final stage is "Quality Assurance". In this stage we check that the system is meeting the requirements as set out in the requirements definition document and if they comply with any necessary laws and regulations. It is at this stage that the developers will check that the right product is being built (validation) and that the product is being built correctly (verification). It is the hope that by the end of this stage you will have produced a product has detected all errors and all the problems are fixed.

[fretzine]

API Development

This week I have been developing my knowledge of using APIs within my web app using the javascript Fetch API. In the small app below I have used the dictionary API (which is free, link below):

Free Dictionary API

This very basic API returns a JSON with a meaning of the world and audio snippet of how to pronounce the word. I followed along to a very good tutorial on YouTube to help build this app which is here:

(43) JavaScript Project in 5 min - English Dictionary Project #HTML, #CSS and #JavaScript - YouTube

You can see the finished product below:

As you can see this is a very good example of working with a very basic API. It basically returns a JSON object which we then turn into an iterable JS object with the .json() method. You can see a snippet of the script below:

Once we have generated an object we can point to the data within its arrays and assign it to the innerText or 'src' (audio) of the website's elements.

Some further learning required to understand exactly how this works is:

Promises

Async functions

Await

Although this is basic I plan to go to Rapid API and look through the various free APIs available and build a bigger application that requires API keys, options which are included within the API calls header.

More to follow.

[fretzine]

Website re-design

I recently came across this lightweight CSS framework that uses semantic HTML (so it's more accessible) and it is .classless (although not really as you do need to create custom stylesheets yourself). But I really enjoyed that it had dark theme enabled from the get go so I didn't have to create my own and you can switch between them at the click of a button!

I have now re-designed the website using this framework to build almost 98% of the website, the only part of the website that is strictly copied from the old is the slideshow as I believed it still looked good, was responsive on mobile devices and (tbh) I struggled to get the boostrap framework to run with Pico at the same time.

Here's what the website looks like now:

As you can see the framework has created a very cool looking website with minimal coding, it's a great tool when trying to build very quick projects that can be shown to customers in the moment (or at least very soon).

I am also still developing my bootstrap skills, this week I have been building a Task Management web app in bootstrap that I will then combine with PHP and MariaDB to create an app that will allow me to add and delete tasks and have them show me their percentage of completion.

The website is not finished but currently looks like this:

It's a bit plain, but I love that bootstrap allows so much creation in so little time. This took three to four hours for me to build (which is quite fast, for me).

I'm hoping that in the next 6 months I'll move away from Bootstrap and on to Tailwind CSS as it looks much more flexible and gets rid of that typical 'bootstrap look' everyone goes on about.

[fretzine]

Introduction to JSON

In the following weeks I will be learning the basics of Javascript, PHP. MySQL and JSON. I will also be looking at creating APIs in work in order for our website to communicate with other systems using JSON.

Therefore, as an introductory challenge I decided to create a small web app that pulls data from a JSON file and populates the data into a table using Javascript.

Below you can see the project that I worked on this evening:

I am happy that I have developed a basic understanding of JSON although I can see improvements that I could have made in this script.

Firstly, I did not parse the JSON into javascript which meant that I could not interact with the code recursively which would have allowed me to create objects for each user with their respective fields.

This would have then allowed me to format the "skills" array into a more presentable format with spaces instead of commas - although I could have done it with replace() dealing with JS objects allows for more control overall.

I hope to work on this over the next couple of months as we are beginning to prepare for a large project where a whole website will be re-designed using a new CMS and many APIs will need to be re-created.

[fretzine]

Java #1

I am beginning to learn Java as part of my university course, I have been asked to read my module's textbook 'Objects First with Java'. This textbook walks you through various BlueJ activities which place an emphasis on learning objects first through iterative learning (small and often).

I have found the basic concepts of Object Orientated Programming (OOP) to be quite easy to understand and you can see the benefits of writing programs in this way straight from the go.

Java OOP

Class - a Class is a container for a variety of similar objects. A class creates objects with pre-determined fields (attributes) and methods (operations). In the image below you can see that there is a public class called Vehicle.

Fields - Fields are specific data types which hold values or attributes of the objects that the class will construct. For example, in the image below you can see that there are three fields: doors, speed and color. These fields have the data types int and String.

3. Objects - Classes can use constructors to create objects with the various attributes and methods that are pre-written in the class. For example, in the image below the class is creating two student objects called s1 and s2:

You can see in the image above that the class is creating a string s1 of type Student and assigning its value to that of a new Student.

After the creation of an object we can determine how we interact with the object by looking at its method's signatures. The signature is right at the top of the method code and tells us if it is private or global, if it has a return type of data (int, String), the name of its method and any parameters that it might accept.

[fretzine]

Personal Development Plan

My new employer has asked that I provide a learning plan for the next two years that I believe I will either study in University, teach myself or learn in work. I provide an overview of my first two years in University which can be seen below:

Over the next year I believe that I will slowly teach myself frameworks such as:

Bootstrap

React.js

Tailwind

I believe that React will be the most important for me to learn as I have a pretty good grasp of CSS and Boostrap (which is what we use in my employment).

It might be more beneficial for me to focus on Agile development techniques as during my day I have at least 3 meetings with various teams in our development team. Some are responsible for process mapping, others for process developing and others for future projects.

[fretzine]

I started my new job as a web developer for my local council this week. My first major project is to move an old website the council built within an old, out of date CMS to a static bootstrap template that I have been tasked with making.

I have never used Bootstrap before therefore I am busy going through guides and its documentation to figure out how it works. I've got to say, I can see why so many people use it - it's brilliant! This is a website that I whipped up today using the documentation and example snippets, with a bit of React.js this could be a lovely little website.

I have no specific time limit to complete this website, I hope that over the next two weeks I develop even greater Bootstrap skills and I can start putting them to use at work.

[fretzine]

Portfolio Website

Over the past two weeks I have been slowly building my first portfolio website to showcase some of my projects that I have and will work on in the future. I wanted the website to feature skills that I have developed over the last two weeks since I have completed a HTML, CSS and Javascript course in full.

You can view the website below (or click here):

Although this is relatively simple code I believe that we shouldn't have to rely on frameworks such as Bootcamp and React in order to produce simple, accessible and responsive websites. I decided to design this website as a single page - each link takes you to a different section of the one page.

To make this one page seem bigger than what it is I decided to have each section's height equal to that of the viewport. Therefore each section will feel like its own page with a slightly different background colour and headers. This works very effectively when viewing on a mobile site:

All of the website has been made with vanilla HTML, CSS and Javascript. There are some improvements that I am still looking to make - for example, I believe the content is too large when viewed on a desktop. I also do not like the main typed text on the home screen when viewed on a mobile.

I am starting my new job as a Technical Web Developer for my local council in two weeks. One of the challenges and responsibilities of developing for the council is the requirement that our websites are as accessible as they can be for a varied public. Therefore, I have decided that I should try and build my portfolio adhering to the WCAG guidelines.

My website scored 83/100 which I am happy with.

[fretzine]

Today I have been learning about one of the main data structures in programming - the dictionary. It’s a container that holds keys which each have a value. In the script above we were tasked with creating an ‘interactive loop’ (as it uses user input) that will randomly show a word and its definition.

This has a few things that are interesting for those who may be learning:

It has used the ‘from random import *’ to be able to use the choice() function.

It has used input() to interact with the user and save the input to a variable.

It has used nested conditional loops such as While and For

[fretzine]

Javascript Project: Stopwatch

I have made a stopwatch with HTML, CSS and Javascript. This was a good example of using iteration to change the values of the HTML each second. I created an original version that looked very clunky and wasn’t very inviting therefore I re-formatted the HTML with new CSS that uses circles and lighter colours. You can try it for yourself here: 

http://www.excellent-tinted-babcat.glitch.me