Forem: Kirk Shillingford

From Script to Scaffold in F#

Kirk Shillingford — Sat, 24 Dec 2022 00:03:29 +0000

Introduction

This year I've been attempting Advent of Code in my favourite programming language, F#. This is a beginner(ish) centered post about making incremental changes from the smallest possible solution to something more robust.

What is F# (F Sharp)

If you've never heard of it before, F# is a functional first programming language in the Microsoft dotnet ecosystem used for general purpose programming, Web development, data analysis, and everything in between. It compiles to the same Common Language Runtime as all other .NET languages, meaning it can interop with any C# package//library and make full use of the .NET ecosystem.

More importantly, (to me), it's a delightfully expressive language, that has just about every semantic pattern I enjoy in a modern programming language, like algebraic data types, powerful pattern matching capabilties, immutability as a default, and a generally terse, lightweight syntax, which both functional and Object Oriented patterns a delight to use.

What is Advent of Code

If you're unfamiliar with it, Advent of Code (or AOC as we'll be referring to it from now on) is a yearly programming challenge that takes place from the first to the 25th of December. Each day a themed coding puzzle is released, in increasing order of difficulty. Programmers from all over the world attempt to solve these puzzles, with varying degrees of competitiveness and rigour. For example, as of writing this in 2022, over two hundred thousand participants.

I have zero interest in the hyper-competitive aspect of AOC; my current life does not afford me the opportunity to do programming challenges in the wee hours of the night. However, this year, after beginning the way I normally do AOC, writing one-off scripts each day, I began feeling frustrated with how much time I spent erecting structures to make solutions possible, vs actually solving problems.

Earlier this year, I wrote about scripting and automation in VSCode using typescript as part of an ongoing project to reduce time consuming repetitive actions in my professional life. So this seemed like a perfect opportunity to do something similar at a more targeted domain space. Additionally, I'd seen a few examples of AOC runners floating around (pre-built libraries and templates that come with hope to help streamline the mechanics of participating in AOC). There are a few solutions in the .NET ecosystem, but they're all in C#!

There's nothing wrong with C# mind you, but I'm here this year, to write F#, not C#. So without any more pre-ample, I'd like to share some of the things I've implemented so far and the trajectory for my AOC runner and solution.

warning: I've used snippets from past and current solutions as examples for the article. It shouldn't be enough to provide meaningful spoilers for anyone, but if your goal is to try the problems, and you're worried about any sort've input, you've been warned.

Step 0 - The current state of things

One of the things I love about F# is its power as a scripting language and with the start of this year's AOC, I took full advantage of this. With access to the F# interactive REPL, my initial pattern was to simply:

create each day as a .fsx file called DayXX.fsx
Each AOC problem is split into two parts, so after completing each portion, I would simply print my solution to console.

let data = """

...

"""

let day10part1solution =
    data
    |> Seq.map (Seq.fold tokenize (List.singleton Empty))
    |> Seq.choose (Seq.tryFindBack isInvalid)
    |> Seq.sumBy invalidValue

...

let day10part2solution =
    data
    |> Seq.map (Seq.fold tokenize (List.singleton Empty))
    |> Seq.filter (Seq.forall (not << isInvalid))
    |> Seq.choose (Seq.tryFindBack isIncomplete)
    |> Seq.map ((Seq.unfold deTokenize >> Seq.map toNum2) >> Seq.fold score 0L)
    |> middle

printfn $"{day03part1solution}, {day03part2solution}"

You might be able to see the obvious problems with this approach over time.

I manually copy and paste all inputs from AOC into the file itself which is clunky and error-prone. It also means more hot swapping of comments when doing tests
Toggling the output I focus on involves modifying an interpolated string
Because the solutions are values and not functions, unless commented out, they're both calculated anyway, which is an issue for solutions involving a heavier amount of calculations.
You can't see it, but because I just make a new script for each day, I'm doing a lot of rewriting of useful patterns. I could make yet another script for those things I want to repeat, but at that point, I may as well just overhaul the entire solution, which is exactly what we're gonna do.
Lastly, .fsx aren't ideal for using official testing frameworks like Xunit, FsUnit, or Unquote, etc.

Step 1 - Switching to solutions

Firstly we can easily use the dotnet command line interface to scaffold a solution with a new project for all our solutions.

dotnet new sln -o AOC
dotnet new console -lang "F#" -o AOC2022
dotnet sln add AOC2022/AOC2022.fsproj

mkdir AOC2022.Tests
cd AOC2022.Tests
dotnet new xunit -lang "F#"
dotnet add reference ../AOC2022/AOC2022.fsproj
cd ..
dotnet sln add AOC2022.Tests/AOC2022.Tests.fsproj

There's a little bit going on but essentially these commands just:

Make a new solution called AOC
Add a project called AOC2022 that contains our code for our actual solutions
Make a project called AOC2022.Tests that'll consume our AOC code and run tests on our solutions.

Now for our .fsx files. First, we'll place them all in our new AOC2022 folder as part of the project and we'll change them to fs files (which is the file type dotnet can parse into a proper solution. Additionally, we'll make a few tweaks.

module Day03

... 

let part1 data =
    data
    |> Seq.map (Seq.fold tokenize (List.singleton Empty))
    |> Seq.choose (Seq.tryFindBack isInvalid)
    |> Seq.sumBy invalidValue

...

let part2 data =
    data
    |> Seq.map (Seq.fold tokenize (List.singleton Empty))
    |> Seq.filter (Seq.forall (not << isInvalid))
    |> Seq.choose (Seq.tryFindBack isIncomplete)
    |> Seq.map ((Seq.unfold deTokenize >> Seq.map toNum2) >> Seq.fold score 0L)
    |> middle

Each file now has a unique module, which is the primary way of organizing code in .NET. Think Solution -> Project -> Namespace (Optional) -> Module -> Value. Instead of the parts being values, they're now functions that accept the data as input and perform the appropriate calculations. We can call them by saying DayXX.part1 input... for example. And that makes it a lot easier to use and test them.

Yay, more structure! There's just one problem! We now have no way of actually running our problem files. Let's fix that with some more CLI work!

Step 2 - Passing Arguments through the Command Line

Now that out code is .fs files, we have no way of calling them directly from the command line. In the entrypoint of our application, Program.fs, we could simply call and return every value in our files


let day1input = ...
let day2input = ...
let day3input = ...
...
// printfn $"{Day01.part1 day1input}, {Day01.part2 day1input}"
// printfn $"{Day02.part1 day2input}, {Day02.part2 day2input}"
printfn $"{Day03.part1 day3input}, {Day03.part2 day3input}"
...

but this still means we're doing control flow with comments. We can do better.

One of the things I've been experimenting with a bit more recently are Computation Expressions which for the purposes of this post we can just treat as ways of safely transforming data in context while keeping a convenient procedural syntax. Using one little CE for the Option type we can put together a crude mechanism to capture user input on the solutions we want to run.

open System.IO

let getInput dayNumber =
        let fileName = $"./data/day{dayNumber}.txt"

        if File.Exists(fileName) then
            Some(File.ReadAllLines)
        else
            None

let getSolution =
    function
    | "1" -> Some(Day01.part1, Day01.part2)
    | "2" -> Some(Day02.part1, Day02.part2)
    | "3" -> Some(Day03.part1, Day03.part2)
    | _ -> None

type MaybeBuilder() =
    member this.Bind(x, f) =
        match x with
        | Some x -> f x
        | _ -> None

    member this.Zero() = None

let maybe = new MaybeBuilder()

[<EntryPoint>]
let main args =
    maybe {
        let! day = Seq.tryHead args
        let! part = Seq.tryItem 1 args
        let! input = getInput day
        let! (part1, part2) = getSolution day

        match part with
        | "1" -> printfn "%A" (part1 input)
        | "2" -> printfn "%A" (part2 input)
        | _ ->
            printfn "%A" (part1 input)
            printfn "%A" (part 2 input)
    }
    |> ignore

    0

Again, let's take a step back and talk about what we're doing here.

We've made a function getInput that accepts a string and tries to find a txt file based on that string. We're going to start keeping our input data in a folder called data, and keep our .fs files containing just our solution code. The function will check if the file exists, and if it does, try and read all the lines into an array of strings
We've also made a getSolution function that attempts to get a solution based on an input string. If we try to call a solution we haven't created yet, it'll just return a value of None instead of crashing.
Our last special value is a MaybeBuilder computation expression. Rather than explain it here, we'll just talk through how it's used below.

In our main function, we put it all together, plus attempting to access two values from the incoming arguments to the program, day and part values representing what code we want to run and what day we want to run it. Those let!s reference any value that would normally be an option and let us use them as if the were just normal values. Our MaybeBuilder is doing the work of chaining the valid values in the background. If any of these actions returns a None, the whole thing gracefully returns None and won't crash. It's not particularly informative, but this is just for me, and all I really want is to not handle crazy error messages every time I mistype a day or part name.

Mind you, a construct like maybe builder is absolutely unnecessary. This was just my small attempt at IO safety. I may switch to a more formal method using async expressions. Or just handling the logic using regular, practical if expressions. Whatever works.

Anyways, we did all of this just so in our terminal we can run our solutions individually.

dotnet run 3 1 

// part 1 results

dotnet run 3 2

// part 2 results

dotnet run 3

// part 1 results
// part 2 results

Great! This is looking way more organized! And most of our earlier hiccups are gone. All we need now are some tests!

Step 3 - All the Tests

We've done a bit of setup so far so we just need a few things to get our tests working

First, we need some test files. We'll mirror the project setup in our AOC2022 folder, one file/module per day, and a data file for test inputs.

module Day03Tests

open Xunit

let input =
    match getInput 3 with
        | Some input -> input
        | _ -> failwith "Input cannot be found" 

[<Fact>]
let ``Part 1`` () = Assert.Equal(157, Day03.part1 input)

[<Fact>]
let ``Part 2`` () = Assert.Equal(70, Day03.part2 input)

I've kept the tests pretty simple for now. We reuse the getInput function from our AOC2022 project but this type we deliberately throw an error if it's missing, since I'm not doing any manual typing with these tests. Then we simply call our module functions in our tests, and compare them to our expected values. We can run these tests from our solution folder just be saying.

dotnet test --filter Day03Tests

Note here the built in functionality to filter tests to one specific module. (And we can of course omit the filter and run all the tests).

The last thing we need is just a little tweak to our AOC2022.Tests.fsproj file so those data files are included in our output.

<ItemGroup>
  <Compile Include="*.fs" />
  <Content Include="data\**"> 

  <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
  </Content>
  </ItemGroup>

This little contant tag in our XML ensures all the data successfully makes to our build directory.

Conclusion and Next Steps

If you've made it here you've seen all I wanted to share in this post. This project is far from over, and I almost didn't share this post because I wanted to add a lot more features first, but I revised that after thinking about how it's rare to see conversations about work in progress. I'm hoping that seeing a project go from nothing to something could provide value for some people. Also, this is a living project and I am using and solving advent of code in it, so my time is split between doing more scaffolding and well, solving problems.

Things coming soon:

Automatic file generation for each day
More formal argument parsing using the Argu library
Automatic input downloads
Benchmarking tools

You can view the live project (and my solves for AOC 2022) here.

Thank you for your time.

Scripting with VSCode Tasks and Typescript

Kirk Shillingford — Wed, 16 Nov 2022 18:01:55 +0000

Cover photo by Markus Winkler on Unsplash

This article will attempt to demonstrate the minimum setup required to run Typescript scripts through Node using VSCode Tasks. We're going to create from scratch a small project that allows someone to:

Write some Typescript
Run that Typescript without converting it to Javascript first
Run the entire process using VSCode tasks to capture user arguments without using the command line.

The article assumes a passing familiarity with Visual Studio Code, Typescript, and Node.js, but I've tried to include links wherever someone might want additional context.

Important Note: This article is meant to be more of a how-to than a why-to, but I felt like it was worth talking about the reason behind scripting in the general, and Typescript in particular. If you'd rather jump straight to the implementation though, you can head straight there.

Why script in Typescript? Why script at all?

Recently, I've been taking a hard look at my work patterns, and making note of opportunities for improvement. What I've discovered are a large amount of repetitive tasks that are made unnecessarily inconsistent and haphazard because I do them from scratch whenever I need them, with little preparation.

I don't think all tasks require automation, and there's a real measure of "value-gained-per-time-lost" that should always be considered, but at least for me personally, it feels like a space where I can make meaningful changes to great benefit.

Scripting can be a great way to reduce cognitive overhead and save time by automating away actions that are:

Repetitive, meaning the same actions take place with sufficient frequency and duration that there's a significant chunk of your time repeating the same actions.
Tediously Mechanical, meaning actions that require specificity and precision, but not analysis (long sequences of commands, file creation and naming, migration of text, etc)

Often we associate scripts with the built-in environments that interface with our operating systems, like bash or Powershell, but we can use any language for scripting provided it has some mechanism (like a runtime environment for executing instructions on a server/OS.

Frequently in my experience, scripts have been described and treated as short, throwaway code, or tedious config work, devoid of the care and rigour we apply to application or operations code.

But if something is important enough to commit to code, it's probably important enough to try to write correctly. The paradigms of readability, testability, and extensibility are just as relevant for short, targeted actions as long-standing operations. Maybe even more so?

Enter Typescript

Anyone who knows me knows I have a deep fondness for Type Driven Development and a particular fascination with Typescript's Type system. Many folks do not see the value in static type systems and I don't see the value in refuting those opinions; I can only attempt to express my own satisfaction through the work I do. I try as much as possible to write code with the support of a strong type system whenever I am able to, and for me, the benefits are real and worthwhile. So this is for anyone who might be interested in the same.

Also, just as a personal note, I love writing scripts. I love writing short, powerful, durable piece of code, that do a thing, well. I like the completeness of small actions, done well. Scripts make me happy.

Manually debugging scripts though, does not make me happy. It does not spark joy. There is a wailing and gnashing of teeth. So I want every possible safeguard to ensure my scripts work as well as they can the first time around. I'm not under the delusion that I can prevent all errors before I run the code. I'd just like to prevent some of them.

Implementing Our Scripts

We're going to split this into two major parts; firstly, how to run typescript code in node without prior compilation to js, and then how to configure that process using a Visual Studio Code Tasks features.

First step is ensuring we have both Node and Visual Studio Code on your machine. I'm going to create a new project folder and open it up in VSCode. We won't need VSCode till we implement tasks though, so working in a File Explorer or Terminal is also fine.

In our project folder, we're going to create our first file, createTemplate.ts that contains the code we want to execute.



import { writeFile } from 'fs'

const [_, __, cwdInput, dateInput] = process.argv

const rawDay = new Date(dateInput)

const day = new Date(rawDay.getTime() + rawDay.getTimezoneOffset()*60000);

const path = `${cwd}/${day.toLocaleDateString('en-CA')}.md`

const template = 
`
${day.toLocaleDateString('en-CA')} - ${day.toLocaleDateString(undefined, { weekday: 'long' })}

# Gratitude
-
-
-

# Frogs
-
-
-

# Wins
-
-
-
`

console.log(path, template)
// writeFile(path, template, console.log)

This script creates a markdown file with some prewritten headers that I tend to use when I write my daily journals. It then sticks that file in the current working directory, with some context of the current date. Currently, we're just opting to log it console first though, while we're getting setup.

As it stands, it currently works fine, but we have two problems.

First, we're getting some rudimentary, and dubious type hints right now. We're being told that the command line arguments cwdInput and dateInput are strings, but there's actually no guarantee that they're there at all. process.env pulls info from the environment the script is run in, and thus is an I/O operation, which is inherently impure. Typescript has the capacity to warn us about this, but isn't currently configured to surface that, so let's give it that capacity.

We can add a tsconfig.json file that informs VSCode's typescript language server of how we want it to compile our code, and what guarantees we'd like.



{
    "compilerOptions": {
        "target": "ES2021",
        "strict": true,
        "noUnusedLocals": true,
        "esModuleInterop": true,
        "module": "CommonJS",
        "moduleResolution": "NodeNext",
        "lib": [
            "ES2021"
        ],
        "noUncheckedIndexedAccess": true,
    }
}

We've got a few things in there, but most important is the strict: true and noUncheckedIndexedAccess: true, configuration. This makes the compiler much less permissive about unsafe operations and our intellisence now correctly sees that our process values are string | undefined.

If you've been following along directly, your project folder should now look like,

But how to run it

The second problem we've got with this script right now is of course, we've got nothing to run it! Because Node can't directly run Typescript!

Note: To be clear, there is currently no popular runtime engine for Typescript. Meaning, there is no application that accepts Typescript natively, turns it to an AST, and executes in an environment, without first, compiling it to javascript. That's what Typescript is really:

An expanded syntax and type system that layers over Javascript syntax, providing an powerful set of additional information, context, and guarantees at compile time
A compiler than converts that to javascript to be consumed by some runtime.
A language itself for expressing complex shapes and a powerful engine for type manipulation

Typically, we would compile our Typescript to Javascript, and run those javascript files with Node. But in this case, we don't need to ever use those javascript files. And this code isn't going to the browser either. So we have the option of finding solutions that don't need those intermediate javascript files.

Ts-Node

The one we're going to use is ts-node. Ts-node has a simple premise; you can pass it typescript files, and it will convert them to JS, and pass them to node for you. It can function also function as a REPL.

To get it, we first add a package.json to our directory. A lot of folks think you need a filled out package.json for npm to function effectively. But really you just need the file.

We can then install the necessary packages using the following:



npm i -D typescript ts-node

That will install ts-node and the Typescript compiler locally, as dev-dependencies. There's an argument for having these as just regular dependencies here, but we're not planning to ship this code anywhere else, so I'm not sure what the best practise is (if anyone reading has opinions, please let me know!)

So we should now see something like this in out package.json.



{
  "devDependencies": {
    "ts-node": "^10.9.1",
    "typescript": "^4.8.4"
  }
}

Check in time for those following along! Now your project folder should look like this

We've added a little addition to our tsconfig to tell ts-node to not run type-checking on our code, because the language intellisense in VSCode is already doing that for us. We've also added some controls to ensure Typescript doesn't attempt to output any javascript files.



{
    "compilerOptions": {
        "target": "ES2021",
        "strict": true,
        "noUnusedLocals": true,
        "noEmit": true,
        "esModuleInterop": true,
        "module": "CommonJS",
        "moduleResolution": "NodeNext",
        "lib": [
            "ES2021"
        ],
        "noUncheckedIndexedAccess": true,
        "allowJs": false
    },
    "ts-node": {
        "transpileOnly": true,
    }
}

And now we can simply tell ts-node to run our typescript using npx



npx ts-node createTemplate.ts /path/to/root/ 2022-11-15

And we get the result we want!

Yay, that worked! And honestly, we could leave it there if you don't mind typing commands in the terminal. We don't need vscode for any of this really, we could let ts-node do our type-checking.

But we don't want to do our own command line instructions now do we? We want to AUTOMATE. And particularly, I want VSCode to do the work for me!

Part 2 - Tasks

To start with, I'm going to pull a line of text straight from the VSCode documentation:

"Tasks in VS Code can be configured to run scripts and start processes so that many of these existing tools can be used from within VS Code without having to enter a command line or write new code."

Great, that looks like exactly what we want.

"Workspace or folder specific tasks are configured from the tasks.json file in the .vscode folder for a workspace."

Say less, fam.

Jokes aside, this is exactly what we're going to do next, making a .vscode folder in our project and adding a tasks.json file.

The tasks API is pretty robust, coming with a suite of built-in variables, integrations for common operations like build-time and run-time actions, and pre-existing hooks and plug-ins, but for our needs we just need a small custom task ourselves.

Here is the json that we will add to out tasks.json file to tell VSCode how to execute our little ts-node script.



{
    "version": "2.0.0",
    "tasks": [
        {
            "type": "shell",
            "label": "CreateDay",
            "command": "npx",
            "args": [
                "ts-node",
                "./createBujoTemplate.ts",
                "${cwd}",
                "${input:date}"
            ]
        }
    ],
    "inputs": [
        {
            "type": "promptString",
            "id": "date",
            "description": "Date for your new template. Preferred format yyyy-mm-dd",
            "default": ""
        }
    ]
}

I'm going to try my best to step through the various parts of this json.

First, we declare the task version we're working with. At the time of writing, 2.0.0 is the default.
Then we make a tasks field; a list of the all the tasks we would like VSCode to use. We currently have the one.
In that task, we specify the task type (shell or process), the tasks unique label (it will yell if you give two tasks the same label), and a way to specify the main command, and any arguments it needs.
Note "${cwd}" as our third argument. CWD (which stands for current working directory) is a built in variable VSCode makes available for use in writing tasks.
Below that, we define another variable "${input:date}", which makes use of VSCode's ability to define custom input variables that need to be provided by the user.
After our task list, we define our list of inputs, where we specify an input we call date.
The type promptString is a VSCode definition that just means the user needs to provide some string of text. There's options for providing a list or dropdown or even other commands. We're just using a string.
Finally, we add a description and a default value for our input.

Putting it all together

And with that all in place, we should be be hit Cmd-Shift-P (or Cntl-Shift-P on Windows Systems) to bring up the Command Palette and find the Run Task command.

That will open up a dropdown showing available tasks where we find our newly added custom task CreateTemplate.

Selecting that takes us to a prompt asking if we need any specific debugging environment while running the script; we can just click continue without scanning output for now.

Finally, we get a prompt asking for that input we defined earlier!

With all that in place, we can watch as the terminal details the running of our code.

And if we check the file system...

We did it!

To Sum Up

So just to recap, we originally had a very manual process, that required us to create and populate a file with the same information every day. And now we've reduced all those to a few keystrokes! I know this doesn't feel like a lot, in terms of the complexity of the code we automated away, but we've barely scratched the surface of what tasks are capable of here. We could've set this task to run whenever we opened our project, or connected it to a cron job or a Github action.

Not everything should be automated, but it's worth considering what could be automated, and if it's your goal to get this kind of behaviour, hopefully this article let you realise it's not as far away as you might think. Give it a try.

Build your own tools sometimes, not because you have to, but because you want to.

Thank you for your time.

Revealing Compound Types in Typescript

Kirk Shillingford — Thu, 10 Nov 2022 16:40:30 +0000

In this post I would like to show a small generic type I use sometimes when writing Typescript to improve intellisense and my developer experience.

The Problem

Frequently when writing Typescript, I run into the following scenario:

I have a set of types that I sometimes use separately or in combination depending on the context. I make heavy use of intellisense in my IDE to get information about the shape of data structures as I write.



// our representative for some application user object
type User = {
  name: string
  age: number
}

type Repository = {
  name: string
  url: string
}

// github data for our app users
type GithubUser = {
  id: number
  repos: Repository[]
}

// a certain set of functions only care about core user data
const fetchUser = (): User => {
  // ...
}

// and others are concerned with finding and revealing github data
const fetchGithubUser = (): GithubUser => {
  // ...
}

We have a User and a GithubUser type that both have different interfaces and their own methods for fetching and processing from their respective APIs. However, there are times in my UI when they need to be combined into a single entity

With both of these separately, intellisense can give us an idea of the shape of the data structure we can expect to see.

However, if we try to make a type that combines the two, using Typescript's (&) intersection syntax, we find that the intellisense now only shows use the type names, and will no longer reveal their shapes to us.



type UnifiedUser = User & GithubUser

// code where I need a unified object containing info from both
const displayUserdata = (data: UnifiedUser) => {
  // ... 
}

By combining multiple types, we've obscured their implementations.

The Solution

The solution here, is to use a small bit of Typescript's very advanced type manipulation abilities to re-expose the shape of our objects. We can do this using a combination of two concepts, mapped types, and Generics

Rather than go headlong into the full explanation of the solution, I'll present it first, and discuss how the pattern works after.



type Spread<Type> = { [Key in keyof Type]: Type[Key] }

type UnifiedUser = Spread<User & GithubUser>

Here, we've made a small generic type which I've called Spread (there may be an better name for this), which we can pass our intersection of User and GithubUser, and we find that we can now see the object representing the combination of the two types.

How it works

Without getting too much into the weeds of the immensely deep, and admittedly, arcane syntax of the Typescript type system, what we've essentially done here is:

The type Spread is parametrized, meaning it itself accepts a type as part of its implementation, similar to how a function accepts a variable to use to figure out its result. It's a type who's value depends on another type!
We've called that type variable that goes into Spread, Type. Sometimes people use T or some other generic name. Like regular variables, you can call type variables anything that isn't an existing type or keyword.
After the equal sign, in the type body we define an object whose fields are the keys of the incoming type variable, and who's values are the values associated with those fields.
The [Key in keyof Type] syntax makes another type variable, Key that represents all the keys (fields) of the type passed in.
And finally, T[Key], passes our key variable into our type variable, to get the value associated with that key! Just like how you would say SomeObject['somefield'] in a real JS object.
This essentially maps the keys and values of the entire intersection into a object containing both.
The intellisense sees this new object now, and not the original types used to make the intersection.

Unions

One nice thing about this pattern is that it works for unions as well.



type Arrows = "Up" | "Down" | "Left" | "Right"

type Buttons = "X" | "Y" | "A" | "B"

type Pressables = Arrows | Buttons

type SpreadPressables = Spread<Arrows | Buttons>

Pressables suffers from the same problem as our object intersection.

But SpreadPressables does not!

Caveats

While this patterns works really well with these two use cases, it can become a little wonky otherwise.

One notable caveat is this solution doesn't work recursively. If a field in the intersection is itself some object, this won't expose that.
Mixing unions and intersections can also sometimes fail to spread out in a way that feels intuitive.

In Conclusion

If the above statements don't immediately click, that's fine! Understanding and Implementing these helper types isn't trivial, which is why Typescript provides a whole suite of Utility types which have useful built-ins for common transformations that people tend to use when working with TS/JS applications.

Also, there are many occasions where we want the implementation details of types to be squashed, especially when designing APIs. Once Typescript does expose type info, it is extremely difficult to keep it hidden if it exists in the same file. There are more advanced Type-level data structures called Opaque types that do just that, but opaque types go far beyond intellisense; they prevent the consumer from even making an implementation of the type.

There may be techniques to expand the utility of this pattern to cover for more use cases, but that's for another time. This post was just to highlight a small scenario that the utility types didn't have an answer for, but the solution turned out to be quite close at hand with some type-level programming!

Here's a link to a typescript playground where you can see all the code written here in it's entirety.

Thanks for reading :)

Semantics, Not Syntax; Developer empowerment using functional-first programming

Kirk Shillingford — Mon, 29 Nov 2021 16:35:42 +0000

"It's not about syntax; it's about semantics." - Richard Feldman

This article is just a collection of my thoughts concerning my favourite languages and why I enjoy them. For the most part, I think software developers operate like artists; our attachment or reluctance to different technologies is heavily influenced by recency, emotional connection, and personal association. We like the things we like, not necessarily the things that are "correct" if there is even some correct to be.

However, in recent times I've seen a few languages spark joy for myself and other developers, and I have spent some time contemplating why that is the case; what makes these (seemingly disparate and unrelated) languages all seem to inspire the same type of zeal and interest in their users.

That seeming disparity is essential. Rust, Elixir, f#, and Go could never be mistaken for each other, yet their advocates' emotional response feels familiar. And in between the various quirks of function definition, platforms, object definitions, etc., there seems to be some more fantastic design ethic that draws people in.

So I'd like to surface some of the ones that I've noticed and maybe explain a bit of why I think they matter to us.

Note: I'll be using examples from a tiny implementation of the Snake Game I wrote in F# here because the language exemplifies pretty much all the things I'll be speaking about today. Also, I like it.

Immutability as Default

If I had to put forth the single most powerful of these language semantics to influence and improve the type of programs we write, it would have to be the decision to make variables not alterable by default after initialisation. The concept of explicit mutation seems so fundamentally baked into what programming means that the idea of working without it seems inconceivable. What does it mean to program with it?

To the computer, not much. Under the hood, languages that leverage immutability are the same variables and spaces in memory that we're used to. But to the developer, it's a big deal to be able to make guarantees that data can only ever be what you defined it to be the first time. And if you want something new, you can use the first thing as a template for the new thing, but they are not the same.

Let's look at an example.


[<StructAttribute>]
type Game = { Food: Food; Snake: Snake; Size: int; Status: Status }

let advance game =
    match game with
    | AlreadyOver -> game
    ...
    | EatsFood ->
      let newSnake = updateSnake game.Snake true
      let newFood = createFood game.Size (newSnake.Head :: newSnake.Tail)

      { game with Snake = newSnake; Food = newFood }

Here we have the core data type for our Snake implementation, the type Game, a record/object with fields Food of a kind Food, Snake of type Snake, Size of type int and Status of type Status. We'll learn what those types are a little later in the article, but what I want to focus on right now is a snippet of the advance() function shown below.

advance() is a function that accepts a game and returns a game. I've trimmed away most of the implementation but kept the portion where advance has determined the snake has eaten a piece of food.

Let's look at the order of operations:

let newSnake = updateSnake game.Snake true is used to create a new snake based on the state of the old one.
let newFood = createFood game.Size (newSnake.Head:: newSnake.Tail) creates a new piece of food by passing in the size of the grid and our new snake.
Finally we return { game with Snake = newSnake; Food = newFood }. Now, this looks very much like a stateful update. It is changing the game fields to these new values. But what it's doing is making a new record, using the values from the old game, but with these new changes.

The old game was unmodified. The game returned is an entirely different value. But the semantics of the language make it cheap, efficient, and sensible to produce new values. So we don't have to worry about actions later accidentally mutating previous values.

It's essential to think about this last part. It's not that we can't program like this in other languages. It's just that their semantics make it less worthwhile. It's harder to track when you're mutating or not. Idiomatic methods and functions in those languages mutate. There could be a performance overhead for making new values too often. These are all semantic barriers to using immutable values and disempowering the developer from this programming style, leading to more precarious code.

In languages like F# and Rust, the mutable keyword is an intentional indicator to the language that you intend to modify a value. In languages like Elm, you cannot do mutation at all. But either way, it makes the programmer much more thoughtful about how they change states in their code. And in the field of software development, thoughtfulness matters*.

No Default Nulls

I won't spend too much time on this one since many, many people have expounded on the dangers of null values.

Suffice to say, it is difficult to trust types, typing, and functions itself in languages that do not or cannot guarantee that the function will return the type you expect, and perhaps more importantly, do not enforce that you write operations that return the types you say they do.

It's OK to have a function that returns Some value or Nothing. That's a semantically correct logical operation. Sometimes things fail. What's not fine is if language inserts a null value because you forgot to return a value at all operation paths in your function. It's hard to write and use code that you cannot trust. It's hard to read and follow docs if every function can not return the value it's supposed to.

  let changeDirection game proposedChange =
    match proposedChange with
    | Perpendicular game.Snake.Direction ->
      { game with Snake = { game.Snake with Direction = proposedChange } }
    | _ -> game

This function, changeDirection, is responsible for changing the way the snake is moving. It has some guard logic for making sure the snake's direction can only change perpendicularly. A snake moving up can either go left or right, but it can't, for example, reverse back into itself.

| _ -> game is the default case for our match (switch) statement where we return the game that came in unchanged. And F# will complain if:

We forget the default (or fail to account for all possible shapes of the input)
We return anything but a game from this function at any point. It won't compile unless we tell it that this function could return a game or something else. But then, everywhere we call this function, we would have to deal with the fact that it might return a game or it might not. All our inputs have to match our outputs.

And that means if I say a function returns an int, the language itself will ensure I'm not lying, and I'd rather not be a liar.

Almost every language I know created in the last decade does not have default nullability on its functions and objects. What was meant as a convenience turned out to be a detriment, and it turns out developers prefer living without it.

Brevity

I have many thoughts on brevity. So many thoughts. I can't write them all because there's something wrong with not being brief about being brief.

So, briefly,

Programming languages and paradigm popularity ebbs and wanes. But nothing truly goes away. In the 90s and aughts, we saw C#, C++, and Java in maybe their heyday as the language du jour of software development. Many times, it has been posited that the rise of dynamic languages like python, ruby, and javascript was a direct response to developers feeling the friction of the overhead of the enterprise languages.

Some people think that this was a resistance to the rigidity of static typing. Developers wanted more freedom and spent less time "type wrangling", opting for performing actions over defining structures.

I think that's part of it, and not all of it. Specifically, I don't believe the types were necessarily the problem, but more like collateral damage from incredibly verbose language syntax.

Curly braces, accessibility modifiers, semicolon, semicolon, semicolon, and always everywhere type definitions made for an intimidating syntax for new developers and seemed to add to laden the burgeoning developer; the better you understood the language, the more code you seemed to have to write to express yourself.

  let private opposite = // Direction -> Direction
    function
    | Up -> Down
    | Down -> Up
    | Left -> Right
    | Right -> Left

Here's a private function in F# that returns the opposite direction. F# does not make explicit return statements in its functions; everything is an expression, so the function's body is a valid return. Indentation handles defining the boundaries of the function body. Newlines define the following case in the switch. Arrows (->) separate cases from results. Mise en place.

Languages like python, F#, and Rust, in contrast to the older iterations of the enterprise languages, do their best to eliminate superfluous syntax, verbose symbols and overly elaborate exposition for every construct. They embrace whitespace as syntax; an idea which arguably does not make that much sense for compilation, but makes a massive difference for human readability. Code people can read and parse is lexically succinct.

By and large, languages are getting briefer and more expressive, relying more on intuitive whitespace for scoping.

And as for the question of verbose type definitions:

Type inference

As a direct continuation of the pattern of brevity discussed above, recently we've seen the emergence of type inference (the ability for a language compiler or runtime to determine and enforce types based on usage).

All the F# code I've shown you so far has been fully/strongly typed. Every function parameter and function return has been deduced and enforced by the type checker.

Some tools, like the VSCode Ionide extension take advantage of this and will display the types for you.

All the type comments you see here are overlaid on to the code. They're not actually being written in the file.

It's hard for me to return to dynamic languages when I know I can get all the benefits of strong types and compile time guarantees without having to explicitly write all the type information.

Safety meets brevity. Admittedly, type inference isn't perfect, and you lose context if you're reading the code outside of an optimized editor experience, but at that point, it's still no worse than if the code was dynamic, and you still have the knowledge that all the logic is type safe and checks out.

I never personally felt the slow down that dynamic programming enthusiasts have mentioned comes with using static types - I think I write working code faster with strong typing - but if you are concerned with speed and expressiveness, type inference seems like an excellent way to mitigate it.

Abstract Data Types

We've reached the final pattern I want to discuss here and I feel like I've saved the best for last; at least for me, it is my personal favourite of all the things we've discussed here and the one that has had the greatest impact on my progression as a developer.

Algebraic Data Types aka Custom Types aka Union and Product Types are a relatively straightforward concept with profound applications.

Ultimately, programming is giving instructions to a machine to perform meaningful work. And modern programming involves making abstractions that produce maintainable code that performs the behaviours we desire. Values, functions, classes, modules and all these other namespaces allow us to define constructs and ideas that map the real domain of our endeavours to a program space of data structures and logic.

Algebraic Data Structures (ADTs) provide a straightforward syntax for expressing the shape of a problem with as little overhead as possible.

Let's see how.

type Game = { Food: Food; Snake: Snake; Size: int; Status: Status }

and Snake = { Head: Head; Tail: Tail; Direction: Direction }

and Head = Position

and Tail = Position list

and Food = Position

and Position = int * int

and Status =
  | Active
  | Won
  | Lost

and Direction =
  | Up
  | Down
  | Left
  | Right

These are the types representing the domain of my Snake game. The concepts, so to speak, that are meaningful to the idea of snake. What is a game of snake?

What is the minimum amount of information necessary to play a game of snake?

There are a few interesting things happening here:

The data structure for the game is composed from smaller structures
We can easily alias types (give them a more semantically meaningful name that's relevant on the context of our application). Like how Food and the snake's Head are both just positions, but we can use their aliases throughout our code for more clarity.
Status and Direction are both Union types. They're similar to enums, but they're not integers or strings under the hood. They're fully qualified Values that we can use in our code, like making our own primitives unique to this application.

You might not find this particularly exciting, saying these are just fancy enums and records, but ADTs are fully unencumbered by shape:

type Message =
  | Restart
  | Dir of Direction
  | Tick

Here we make a Message type that has two simpler values, Restart and Tick that don't rely on any other data, and one parametrized value, Dir that requires a Direction.

let update game msg =
  match msg with
  | Restart -> Game.init 10
  | Dir direction -> Game.changeDirection game direction
  | Tick -> Game.advance game

When we consume this data type we can make decisions and access the associated data with each value, but not mix them up. We can't use the direction in any case except the Dir direction case, because directions only exist on that value.

This allows us to precisely model domains without wastage. It is not a trivial operation to express something like that message type in a language like Java, and requires significantly more code to do so. As a consequence, people rarely do it, opting to use more mutation, and nullable values to handle states where data is lacking, or shouldn't exist.

And that causes more bugs.

We shouldn't write code that squeezes our real-world domain into the primitive types of our programming languages; our programming languages should provide the tools to represent our domain precisely and without wastage. The better the representation, the easier it will be to work with the data.

ADTs are now a first-class feature for me in any language I want to use. The more resistance a language gives me to describing what a thing actually is, the less I find myself wanting to use it.

Final thoughts

If you've made it here, thank you for taking the time to read my little love letter to the patterns I enjoy, and why I think other developers enjoy them as well.

We've gone this whole way without me mentioning functional programming, and that's deliberate. While almost all of these patterns saw their origins and notable iterations in the functional programming space, I've recently found myself moving away from attempting to separate the world into functional or not functional; I'd rather talk about patterns that I like, and tools that implement them.

F# itself has recently done the same with it's updated tagline:

F# empowers everyone to write succinct, robust and performant code

The goal is not to be functional or object oriented. It's not to be the most popular language or the fastest language.

It's to help people write good code.
It's to help developers express their desires.
It's to avoid bugs, and errors.

Languages that execute well on these ideas, seem to be well received. And it's not just the new languages. All the older tools and frameworks are thinking about developer empowerment.

It was never really about semicolons. The things we've just talked about aren't recommendations or suggestions in style guides. They're not buried in tomes like, "Everything you need to know about X". They're baked into the language ecosystems themselves.

Let me know in the comments what you think, and what language patterns bring you delight.

Talking technique: Recognizing context for cleaner design

Kirk Shillingford — Wed, 17 Nov 2021 12:33:17 +0000

A Short Introduction

This is a short post covering a relatively useful pattern for writing functions that I have found very applicable to anyone writing modern software. The pattern itself isn't particularly arcane, and many developers find themselves adopting this style with time.

However, I've found that sometimes, speaking about something explicitly can accelerate learning and understanding faster than trying to intuit things over time. I remember being fairly excited once I noticed the pattern and grateful that once I brought it up, someone more senior than myself took the time to break it down.

So let's see if I can pass it on.

So what's the pattern

Sometimes, I feel like the best way to approach things is to lay an elaborate groundwork of pieces and slowly assemble the puzzle together with the reader. But this time, I think it's best to start with the final statement, so let's just start with defining the pattern itself.

"User-defined functions should try not to consume "container" data structures.

Those data structures should be manipulated at a higher level by built-in features of the language itself."

If the above statement doesn't immediately click, that's okay! That's what this article is for. Since we'll be looking at examples in Javascript, I also have a more specific version of the statement for js development, which goes:

"User-defined functions should try not to consume Arrays, Promises, and Nullables. Those should be manipulated by the built-in methods of their respective libraries.

User-defined functions should try to concern themselves with the values inside the container data structures instead."

Still unclear? That's fine. Let's examine this more in-depth with some examples.

Example one: Manipulating the elements in an array.

Let's take a look at the following code

const radii = [1, 4, 7, 10, 13]

const sphericalVolumes = (radii) => {
  const volumes = []
  radii.forEach(radius => {
    const volume = (4 / 3) * Math.PI * radius ** 3
    volumes.push(volume)
  })
  return volumes
}

console.log(sphericalVolumes(radii))

// [4.1887902047863905, 268.082573106329, 1436.7550402417319, 4188.790204786391, 9202.7720799157]

We've created this function, sphericalVolume(), that accepts a list of "radii" (radiuses? I don't honestly know) and calculates the Volume of the corresponding sphere. This function is fine, but there are a few things we could critique here:

By having the function consume an array, and by using forEach(), we've bound it to always consuming an array-like structure. If we ever decide to use a different container for our radiuses (like a list or a set), this will break.
Consuming a list also makes our tests more complicated. In addition to checking the actual calculation of the spheres, we now have to also ensure this maintains the right behaviour when the list is empty or contains non-numerical values. Neither of which has anything to do with the function's true purpose; calculating a volume from a radius.
Another added complexity of the tests is that the value returned is now an array that must be unpacked to retrieve the value.

Let's compare it to this refactored version:

const radii = [1, 4, 7, 10, 13]

const sphericalVolume = (radius) => (4 / 3) * Math.PI * radius ** 3

console.log(radii.map(sphericalVolume))

// [4.1887902047863905, 268.082573106329, 1436.7550402417319, 4188.790204786391, 9202.7720799157]

Here, we leverage the fact that arrays already have the tools to transform values in that container. We can do away with most of the trimming around that original function with the built-in map() method, and most importantly, our custom function accepts and returns a single value now.

Testing this function is way easier than before because it always gets a number and returns a number. In Javascript, we can't guarantee it will be passed in a number (in Typescript, we can), but if it does get passed in something else, that's not its job to guarantee.

Although this article isn't explicitly about overly defensive coding, this pattern does help you avoid it. As a rule of thumb,

functions should not both validate an incoming input and perform an operation.

It is the caller's job to ensure the values it passes to the function are correct.

Let's see that more clearly in another example.

Example Two: Manipulating a value that may be null or undefined

const samplePerson = {
  id: 25,
  title: "Dr",
  firstName: "Justin",
  lastName: "Belieber"
}

const people = [samplePerson]

const makeGreeting = (person) => {
  if (person) {
    return `Hello ${person.title} ${person.firstName} ${person.lastName},`
  } else {
    return "Hello Valued Customer,"
  }
}

const person1 = people.find(person => person.id === 25)
const person2 = people.find(person => person.id === 77)

console.log(makeGreeting(person1))
console.log(makeGreeting(person2))

// "Hello Dr Justin Belieber,"
// "Hello Valued Customer,"

So here we have a mock of doing some kind of data retrieval from an array. This array is supposed to contain objects with information about people's names and titles, identifiable by a unique id. We use the find() method to get the objects, but find() will return undefined if it fails to find a matching element of the array. Our makeGreeting() function receives this value, checks if it isn't undefined, and returns either a custom, or generic message accordingly.

You can probably already see the problem here, but let's look at a potential alternative.

const samplePerson = {
  id: 25,
  title: "Dr",
  firstName: "Justin",
  lastName: "Belieber"
}

const people = [samplePerson]

const makeGreeting = (person) =>
  `Hello ${person.title} ${person.firstName} ${person.lastName},`

const possible = people.find(person => person.id === 25)
const greeting = possible ? makeGreeting(possible) : "Hello Valued Customer,"

console.log(greeting)

// "Hello Dr Justin Belieber,"

Here again, we've done what we did in the first example. We've moved the validation out of the function and now ensured that it only ever has to deal with real concrete values.

Thanks to things like the ternary and the nullish coalescing operator, we can handle logic concerning whether a value exists using native language features without concerning the custom function.

This gives us similar testing, readability, and refactoring advantages as we did before.

Now you might have noticed, earlier in the article, I referred to these data structures as "container" structures. But container may not be the best term to describe something like a value that may be null. Another way we can describe these are values in context:

the values in the first example have the context of being held inside an array
the values in the second example have the context of maybe not existing

Phrased like that, it might seem a little more obvious why it's so much easier to write and manipulate functions that work with values that exist and are usable, rather than ones that we aren't sure about.

To wrap up, let's look at just one more example.

Example Three: Handling Promises

This last example will be the most lengthy, but I promise it's just a continuation of the same patterns we've seen so far. It just requires a bit more preamble to make sense.

const processResponse = (response) => {
  if (response.ok) {
    const { name, sprites, types } = response.json();
    const sprite = sprites.front_default;
    const types_ = types.map((o) => o.type.name);
    return { name: name, sprite: sprite, types: types_ };
  } else return null;
};

const addChildren = (parent, ...children) => {
  for (let child of children) {
    parent.appendChild(child);
  }
};

const getData1 = async () => {
  const pokeDiv = document.getElementById("pokedex");
  const id = Math.floor(Math.random() * 899);
  const address = `https://pokeapi.co/api/v2/pokemon/${id}`;

  const response = await fetch(address);

  const data = processResponse(response);

  if (data) {
    const { name, sprite, types_ } = data;
    const nameDiv = document.createTextNode(name);
    const spriteDiv = document.createElement("img");
    const typeDivs = types_.map((type) => document.createTextNode(type));
    spriteDiv.src = sprite;
    addChildren(pokeDiv, nameDiv, spriteDiv, ...typeDivs);
  }
};

So what's going on here?

This is a snippet of part of the logic for my Pokedex New Tab Chrome Extension project (really rolls off the tongue right).

We use fetch to request some data from the pokemon api.
We make a function, processResponse() that accepts the results of that fetch, checks whether it was successful, and then extracts the relevant data, and then returns that transformed data, or null
Back in the calling function, we update our html with the relevant poke-info if data returned has a meaningful value.

Once again, with processResponse() we've got a function that's attempting to both make sense of some context, and manipulate the objects inside it.

Also, because it sometimes returns null, we have to validate again in the main function on the data returned. Does null even make sense as a return value here? Should it perhaps be an error? This whole thing feels a little too unwieldy for a simple data fetch.

Can we leverage existing tools in the language to handle some of this?

const processResponse2 = (payload) => {
  const { name, sprites, types } = payload.json();
  const sprite = sprites.front_default;
  const types_ = types.map((o) => o.type.name);
  return { name: name, sprite: sprite, types: types_ };
};

const getData2 = async () => {
  const pokeDiv = document.getElementById("pokedex");
  const id = Math.floor(Math.random() * 899);
  const address = `https://pokeapi.co/api/v2/pokemon/${id}`;

  await fetch(address)
    .then((response) => {
      const { name, sprite, types_ } = processResponse(response);
      const nameDiv = document.createTextNode(name);
      const spriteDiv = document.createElement("img");
      const typeDivs = types_.map((type) => document.createTextNode(type));
      spriteDiv.src = sprite;
      addChildren(pokeDiv, nameDiv, spriteDiv, ...typeDivs);
    })
    .catch((error) => {
      throw Error(error);
    });
};

So what's going on in this version of our logic? Well now, we're leveraging the then() method on our promise object to pass the value that we want, the object from the successful response.

processResponse() therefore no longer has to concern itself with whether the response succeeded; it's a function that is only there for when a success happens. The ambiguity of our logic goes away, and we even get to use the catch() method to handle errors any way we choose.

Cleaner code that easier to reason about, extend, and manipulate.

Final thoughts

I hope this little foray into code design was useful to you. This is a broad and deep space, and I wish I had more time to present a more substantial mapping of the principles behind these tactics, and how to build upon them. Hopefully this article and others like it can spark interest and thought in the craft of good code, and what the goals are when refactoring.

"Values in context" are the type of thing where once you notice them, you start seeing them everywhere, because they are everywhere. Knowing when we need to manipulate an array vs just transforming the values inside seems small, but it's the type of thing that can make the difference between spaghetti logic and functions that are easy to reason about.

As always, please reach out if you have any questions, comments, or feedback.

I hope this was valuable for you. Thank you for your time.

Additional Notes

If you want to approach this from a more academic standpoint, the entire class of "contexts that contain a value" that we've looked at here are referred to as Functors. There's a very precise definition of what functors are and how they work but many people just remember them as contexts that are mappable. map(), then(), and the ternary operator all do the same thing; they allow us to safely work with a value in some context without disturbing the context itself.
A note on dogma: Like everything in software these techniques are suggestions and not absolutes. There are very legitimate reasons for functions to consume arrays and nullables and promises; this was just a way of highlighting that that shouldn't always be the default. For example, a sum function that is actually performing a transformation on an entire array, would need that entire area.
In the first example, you might be tempted to think that the second solution seems better partially because we replaced a more verbose forEach() with the minimal syntax of map(), but the solution of map() in the array consuming version has its own even more subtle flaw.

const sphericalVolumes = (radii) =>
  radii.map(radius => (4 / 3) * Math.PI * radius ** 3)

This code, while having the same issues as its more verbose version, suffers from another potential anti-pattern:

sphericalVolumes() in this case is just a thin abstraction over radii.map(radius => (4 / 3) * Math.PI * radius ** 3). So thin, in fact, that you could argue that unless we use this function in multiple places, the abstraction isn't worth hiding the code behind an interface. In other words, wrapping radii.map(radius => (4 / 3) * Math.PI * radius ** 3) in sphericalVolumes() just hides code away that would've been easy enough to understand anyway. The abstraction doesn't help us make sense of the code; it just makes it harder to discover.

A Most Magic TicTacToe solution with React and TS

Kirk Shillingford — Tue, 02 Nov 2021 12:13:44 +0000

Synopsis

My name is Kirk. I like making small games with code. And today's game is Tic-Tac-Toe. Specifically, this is a post about an alternative algorithm for finding winning combos in Tic-Tac-Toe using a concept called Magic Squares, but also about burnout, productivity, and finding joy in code. The code is all done in React and Typescript, and as always, full links and examples will be provided. If you just want to see the final solution, visit the sandbox here.

1. Starting from the end with sensible solutions.

Now, normally we'd start a post like this at the beginning; we'd talk about the domain of the physical game, and what elements we'd need in our digital solution. But today we're gonna start at the end; we're gonna take an existing solution and look at what if we just changed a small bit in an interesting way. Like Marvel's What-If, but with a smaller animation budget.

So what do we have going on?

My take on Tic-Tac-Toe. Does it work? Yes. A bit plain? Also yes.

This is our basic Tic-Tac-Toe implementation in React. Each turn a user clicks a cell in the grid, and the game checks to see if they've won.

Under the hood, our "grid" is just an object whose fields are the numbers of the cells and who's values are "X"s, "O"s, and nulls (for empty cells).

type Grid = { [key: number]: "X" | "O" | null };

const grid:Grid = {
  1: "X",
  2: null,
  3: null,
  4: "X",
  5: "O",
  6: "O",
  7: null,
  8: "X",
  9: null
}

// this grid would be rendered as the following

 x |   |
 x | o | o
   | x |

For our Tic-Tac-Toe implementation, we need a function that checks whether a player has won after each turn, hasWinner(). That function can accept a grid and determine if there's a winning set of moves in the grid.

The win function looks like this:

const winningCombos = [
  [1,2,3], // top row
  [4,5,6], // middle row
  [7,8,9], // bottom row
  [1,4,7], // left column
  [2,5,8], // middle column
  [3,6,9], // right column
  [1,5,9], // descending diagonal
  [3,5,7] // ascending diagonal
]

const hasWinner = (grid: Grid): boolean => {
  // map the grid values to the combo keys
  const comboValues = winningCombos.map(
    (comboKeys) => comboKeys.map(
      (key) => grid[key]
    )
  )

  // find returns a value or undefined
  const maybeWinner = comboValues
    .find(
      (comboValues) =>
        comboValues.every((v) => v === "X") ||
        comboValues.every((v) => v === "O")
    );

   // convert this value to a boolean
   return !!maybeWinner
}

So what's happening here?

First, we create a list of lists representing all the potential winning sequences of cells, all the rows and columns and the two diagonals.

In the hasWinner() function:

We use map() over our combos to get the grid values for every cell
Then we use find() to look for a group which has all X's or all O's
If we find one, that means there's three of the same value in a row on the board, and we have a winner.

And this works and performs fine. It does the job. But maybe we can do something a bit more fun that does the job. Not with how hasWinner() works, but with how we get those winningCombos.

Here, we basically just wrote them out by hand. And eight wasn't really so bad.

But what if we had a 4x4 board? That's 10 solutions. And a 5x5 board is twelve. It would be nice if there was a way to just know the ways to solve without having to look at the grid and then write them all out.

And luckily, there just so happens to be a way (or this would be the end of this blog post).

And that solution, involves magic squares

2. Answers with no questions.

Now, this is meant to be a technical article, but it's worth taking a bit of time to talk about why this is an article about Tic-Tac-Toe, and why this solution even exists.

I tend to think that Human being like patterns. We're designed to find patterns and solve problems. Sometimes, our brains pattern matching inclinations can get us in trouble; conspiracies are essentially just us finding patterns even when they aren't there. Some patterns we've been picking apart and working on for thousands of years.

One such pattern discovered at least as early as 190 BCE by Chinese mathematicians is the concept of a Magic Square.

Tada? Yes it's just a box.

"But Kirk," you ask, "what's so special about this square?"

Well you see, all magic squares (including this one) have three (3) very interesting properties.

All the digits in the rows of the square add to a particular number.
All the digits in the columns of the square must add to that same number.
And all the digits in the diagonals add to that number too!

Do these rules feel familiar?

Magic Squares care about the same patterns in grids made from squares that Tic-Tac-Toe does!

And the best part is, they have nothing to do with each other! When Tic-Tac-Toe started showing up in Ancient Egypt, it didn't have anything to do with Magic Squares. Humans have just been enjoying patterns of squares in squares forever.

Magic Squares fall into the realm of Recreational Mathematics, which is maths done at least partially for the purposes of entertainment, as opposed to research of practical application. It's also the maths most frequently done by amateur (unpaid mathematicians). Throughout history though, Mathematicians, Philosophers, and even Religious figures have studied and teased apart the nature of magic squares. Beyond 3x3 grids, they've looked at 4x4 and larger magic squares. They've looked at semi-magic squares and pseudo magic squares, and even some things given the brilliant name of Most-Perfect Magic Squares.

Throughout history the patterns of magic squares have been claimed to have use in astronomical calculations, and even occult powers. There's quite a large body of examples, computations, and algorithms based on them. We've taken them apart and put them together over and over in the pursuit of understanding what do these patterns of numbers mean? And that's been terribly fun for everyone involved, but for the most part, generally, they have absolutely no purpose at all.

They're just numbers in squares, with no more meaning than what we give them. Just some silly nonsense that we like to look at. Answers with no questions.

Except for today. Today they're helping us solve Tic-Tac-Toe.

3. Making winning magic combos

So now we know there are magic squares, which care about the same arbitrary patterns that Tic Tac Toe cares about. How does that help us get to a solution.

Well, let's look at the magic square for a 3x3 grid.

While magic squares get more complex in 4x4 grids and higher, with 3x3 grids we can confidently say a few things:

All the rows, columns, and diagonals in a 3x3 magic square add to fifteen (15)
As importantly, any other 3 number combo in a 3x3 magic square Does Not add up to 15.
There's only one (1) way to align the numbers in a 3x3 grid to get a magic square (You can rotate the numbers around the center or flip them on an axis but it's still the same arrangement).

This means if we can programatically get all the 3 digits combos that sum to 15, we can get all the relevant rows, columns, and diagonals in Tic-Tac-Toe.

The implementation of this ends up being far shorter that the lead up.

import { Combination } from "js-combinations"

const keys = [1, 2, 3, 4, 5, 6, 7, 8, 9]

const uniqueTriples = new Combination(keys, 3).toArray()
// [[1, 2, 3], [1, 2, 4], [1, 2, 5] ...

const winningCombos = uniqueTriples.filter(
  (nums) => nums.reduce((acc, num) => acc + num) === 15
);
// [[1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 5, 8]...

This is only a few lines of code but there's a lot going on here so let's break it down step by step.

The first thing we do is import the Combination class from the js-combinatorics package. This package has a ton of useful tools for calculating permutations and combinations of items.

We're using to the Combination class to create all the valid, unique combinations of 3 numbers from the set of numbers from 1 to 9.

The Combination class from this library is a Javascript Iterable.

Each value is the same shape as the ones we saw in one original winning combos; an array of three (3) numbers.

We convert our combination class to an array so we can do the next step; filtering those unique pairs down to just the values that add to 15. Thanks to magic squares we know those values will be the rows, columns, and diagonals of our solution.

To the filter method, we pass a callback inline that uses reduce() to sum all the values in our triple and see if they add to 15.

And our hasWinner() function is none the wiser.

The final part is the arrangement of our cells in the UI. The only way this method works is if on the UI side, our cells are displayed in the right order. There are a few ways to accomplish this but the simplest is just to order our keys in the magic square arrangement so whatever calls the API gets them out in the order they're meant to be displayed.

const keys = [2, 7, 8, 9, 5, 1, 4, 3, 6]

And that's all it takes. No more manually writing out winning combos. And we can scale this for 4x4, 5x5, 6x6 etc...

4. So What's the Takeaway

Honestly, I started this project planning to talk about object-oriented vs functional API design. And I might still do that. I had written the first version of this solution, and it worked really well, and that was going to be it.

But then, at 2:00 a.m. in the morning when I should've been asleep, I was instead thinking about how tic-tac-toes remind me of tiny sudoku tables. And I remembered doing a cool sudoku once that had a Magic Square.

I have always felt like coding is a creative endeavour. I remember being told once, that "creativity is just novel juxtapositions". I could've done this the regular way, but this way, with this weird fact about magic squares, it just seemed a little more fun.

It just felt like something to explore. I am far from the first person to make a Tic-Tac-Toe game. And I'm definitely not the first person to think of Magic Squares.

But maybe I'm the first one to put them together like this. With React. With Typescript. And that was fun for me.

So I hope this post and this code can provide you some measure of joy and insight. And even if you don't care about the squares stuff, I don't think it's a half bad implementation of Tic-Tac-Toe. It's got all the function composition and expression based logic I also enjoy. And I hope it inspires you to do things you enjoy as well. Not everything we do needs to have a direct purpose.

You can just do things, and write code, because it makes you happy. In between all the React fundamentals, and AWS fundamentals, and Docker fundamentals, and practicality and hireability, we should sneak in some time just for us.

And like me and the folks who first thought about Magic squares, maybe 2000 years from now, someone will find the things you did just for fun, and use them to have fun too.

Let me know if you have any questions about the code, the squares, or the strategy, or if there's anything else you'd like me to cover.

Thank you for your time.

*Special thank you to all my friends at Virtual Coffee for encouraging me to do this (and debugging my css!)

Resources

See here for the Github repo for this code.
See here for the editable, runnnable codesandbox where I made this.
The wikipedia article about magic squares has a lot more cool info about their history and properties.

And finally, here's the main code for the solution if you'd just like to see what's going on here.

App.tsx

import "./styles.css";
import Game from "./GameClass";
import { useState } from "react";

const initialGame = () => ({ game: new Game() });

export default function App() {
  const [state, setState] = useState(initialGame());

  // this is where we update the state of our application
  const update = (value: number | "Restart") => {
    if (value !== "Restart") {
      state.game.setCell(value);
      setState({ ...state });
    } else setState(initialGame());
  };

  // our tiny little cell component
  const Cell = (key: number) => (
    <button key={key} id={`cell${key}`} onClick={() => update(key)}>
      {state.game.getCell(key) ?? ""}
    </button>
  );

  // I really dislike curly braces
  const statusMessage = () => {
    if (state.game.winner) return `${state.game.winner} won the game!`;
    else if (state.game.isFull) return "The game is a draw!";
    else return `${state.game.turn}'s turn to play!`;
  };

  // Putting it all together
  return (
    <div className="App">
      <h1>ReacTacToe</h1>
      <div id="gamebox">{state.game.cellNames.map(Cell)}</div>
      <div id="status">{statusMessage()}</div>
      <button onClick={() => update("Restart")}>Restart</button>
    </div>
  );
}

GameClass.ts

import { Combination } from "js-combinatorics";

type Grid = { [key: number]: "X" | "O" | null };

const keys = [2, 7, 6, 9, 5, 1, 4, 3, 8];

// get every unique combination of 3 numbers and only keep the ones that sum to 15
const winningCombos = new Combination(keys, 3).toArray().filter(
  (nums) => nums.reduce((acc, num) => acc + num) === 15
);

const hasWinner = (grid: Grid) =>
  !!winningCombos
    // get the corresponding grid items
    .map((comboNumbers) => comboNumbers.map((key) => grid[key]))
    // if you find at least one with all Xs or all Os, there's a winner!
    .find(
      (comboValues) =>
        comboValues.every((v) => v === "X") ||
        comboValues.every((v) => v === "O")
    );

export default class Game {
  private _grid: Grid;

  constructor() {
    // using reduce to add all our keys to an object with initial values of null;
    this._grid = keys.reduce(
      (grid, key) => Object.assign(grid, { [key]: null }),
      {}
    );
  }

  get turn() {
    // get the grid values
    const counts = Object.values(this._grid)
      // use reduce to make an object that counts all the Xs and Os
      .reduce(
        (acc, value) => {
          if (value === "X") acc.Xs += 1;
          else if (value === "O") acc.Os += 1;
          return acc;
        },
        { Xs: 0, Os: 0 }
      );
    // if there are more Xs on the board, it's O's turn.
    return counts.Xs > counts.Os ? "O" : "X";
  }

  get winner() {
    if (!hasWinner(this._grid)) return null;
    // if there's a winner and it's X's turn, that means O just won. Otherwise, X just won.
    else return this.turn === "X" ? "O" : "X";
  }

  get isFull() {
    // no null values in the grid? board must be full
    return Object.entries(this._grid).every(([_, value]) => !!value);
  }

  getCell = (key: number) => (key in this._grid ? this._grid[key] : null);

  setCell = (key: number) => {
    // no winner yet, a valid name and an empty cell? Set grid cell to whoever's turn this is.
    if (!this.winner && key in this._grid && !this._grid[key])
      this._grid[key] = this.turn;
  };

  get cellNames() {
    return keys;
  }
}

Styles.scss

.App {
  display: flex;
  flex-direction: column;
  align-items: center;
  justify-content: space-around;
}

#gamebox {
  display: grid;
  width: 80vw;
  height: 80vw;
  max-width: 600px;
  max-height: 600px;
  min-width: 150px;
  min-height: 150px;
  grid-template-areas:
    ". . ."
    ". . ."
    ". . .";
}

#status {
  margin: 5px;
}

Reduce in 5 Minutes

Kirk Shillingford — Mon, 11 Oct 2021 16:30:52 +0000

Here's a quick intro to the reduce() method in Javascript/Typescript arrays, which is frequently perplexing when encountered in working code.

The code here is written in Typescript but I've tried to keep it friendly for JS readers, and I'll post a link to the equivalent JS at the end.

What's the point of reduce?

Reduce allows us to take a container of data (like an array) and fold it into another data structure.

The reduce() method involves three parts:

A container of values, like an array, with which we need to update another structure (in sequence)
A function that lets us update a value (typically called the accumulator) based on an element from our array

function updater(accumulator:SomeType, nextValueFromArray): SomeType {
    ... // whatever operations we want
    return updatedAccumulator
}

Frequently this updater is written inline, directly inside the reduce function.

The last thing the reducer needs is an initial value for our accumulator, for the first iteration of the function. Reduce is smart enough to realize that if we don't provide an initial value, it should use the first element of the array as the initial value.

NOTE: Omitting the initial value only works if the accumulator is the same type as elements. An example to show this will be provided below.

So, to recap, any reduce operation can be thought of as

someArrayOfValues.reduce(updater, initialValueOfTheAccumulator)

Examples

Let's look at some examples!

First, let's see how we could do string concatenation using reduce. This involves 'folding' an array of strings into a single string.

// our array of characters to fold
const boSpelling = ['B', 'o', ' ', 'B', 'u', 'r', 'n', 'h', 'a', 'm']


// our initial value for us to reduce into is an empty string 
const initialName = ''

Here you see, we write a function that understands how to add a letter to a value and return a new value. Reduce takes that function, and our new value, and will pass each letter of our array to that function, bringing the result forward to serve as the accumulated value for the next iteration.

const bosName = boSpelling.reduce((nameSoFar, letter) => {
    const updatedName = nameSoFar + letter
    return updatedName
}, initialName)

We could also inline the initial value.

const bosName = boSpelling.reduce((nameSoFar, letter) => {
    const updatedName = nameSoFar + letter
    return updatedName
}, '')

console.log(bosName) // "Bo Burnham"

Just to provide context, here is the for loop version. This does the same as the code above, but here we update a mutable variable and use a for block instead of a function expression.

Some people find this preferable but it does require object mutation, unlike reduce.

const concatenate = (lst:string[]) => {
    let name = ""
    for (let letter of lst) {
        name += letter
    }
    return name
}

const bosName = concatenate(boSpelling)

console.log(bosName) \\ "Bo Burnham"

Now, let's make a custom sum function using reduce. Combining with es6 syntax allows for some very concise expressions.

const numbers = [ 2, 3, 4, 5, 6, 7, 8, 9, 10]

const sum = (lst:number[]) => 
    lst.reduce((count, nextNum) => count + nextNum, 0)

Note that since the accumulator count, and the array elements are both numbers, we can omit the initial value and just let reduce use the first value as the initial.

In situations where they're not the same data type, doing this would cause an error.

const sum = (lst:number[]) => 
    lst.reduce((count, nextNum) => count + nextNum)

console.log(sum(numbers)) // "54"

Advanced Examples

We've hit the end of the main things I wanted to demonstrate with reduce (I told you this would be quick). But we can have a bit more fun and show how powerful and flexible it really is. These next examples are beyond the standard use cases of reduce and if you're still new to the concept, feel free to skip them.

The reduce() method can fold a sequence of values into any data structure you'd like, including another sequences.

This makes it more powerful than its sibling methods, map() and filter(), which can only transform an array into another array. But that doesn't mean it can't do what they do as well.

Here we make map() from reduce. For each item in the original array, we apply the function to it and add to an accumulator, a new array.

const map = <a, b>(func:(arg:a) => b, lst:a[]) => 
    lst.reduce((acc:b[], item) => [...acc, func(item)], [])

and we can use it similarly to the map() method we know

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

const multiplyByThree = (x:number) => x * 3

const mapResults = map(multiplyByThree, numbers)

console.log(mapResults) \\ "3,6,9,12,15,18,21,24,27,30"

The filter function is similar. Here, the function we pass in is a condition, which is a function that accepts a variable of the same type as the ones in the array and returns a boolean).

If the array item satisfies the condition (returns true), we add it to the new array, otherwise we pass along the new array as is.

const filter = <a>(condition:(arg:a) => boolean, lst:a[]) => 
    lst.reduce((newLst:a[], item) =>
        condition(item) ? [...newLst, item] : newLst, [])

// our condition
const isEven = (x:number) => x % 2 === 0 ? true : false

const filterResults = filter(isEven, numbers)

console.log(filterResults) \\ "2,4,6,8,10"

A brief aside on types

Another way we can compare the three methods in in terms of the types they accept, and return. In pseudocode, the types of the three functions can be described as

map : (a -> b), Array a -> Array b
Given a function that takes an a and returns a b, and an array of a, map will return an array of b.

filter : (a -> Bool) -> Array a -> Array a
Given a function that takes an a and returns a boolean, and an array of a, filter returns an array of a

reduce : (b -> a -> b) -> b -> Array a -> b
Given a function that takes a b and an a and returns a b, an initial accumulator value b, and an array of a, reduce returns a b.

Final Thoughts

I hope this provided some clarity and demystified one of the more powerful tools in the JS toolbelt.

Let me know if this helped, or what other methods you want five minutes on!

Resources

See here for the full code in a sandboxed environment, in both TS and JS versions.
See here for some more official docs on the method, it's overloads, etc.
Note there's a small error in the live example where the isOdd function actually checks for evenness, and I am being too lazy to fix it and get a new URL.

Solving the Dominoes problem with Graph Theory and Typescript

Kirk Shillingford — Wed, 07 Apr 2021 13:20:07 +0000

Prelude

This is a very short article which talks about using graph theory to solve my latest code challenge.

Every two weeks my online community group, Virtual Coffee picks a new challenge for us all to work on together.

This fortnight we've been working on the Dominoes problem on https://www.exercism.io.

I tried to solve this previously using F# without having to do any recursion or traversals. That basically worked, but failed at a few edge cases and ultimately wasn't a complete solution.

While looking at other implementations I stumbled upon this solution which proposed that you could solve the problem by modelling the dominoes as a Graph. I liked the approach conceptually, but didn't want to just recreate the answer in F# again so I figured I'd try it with Typescript.

If you just want see the code, feel free to skip to here.

So without further ado, let's dive in.

INTRODUCTION

Problem

Paraphrasing exercism, "Write a function canChain to determine whether a set of dominoes (an array of tuples) can be chained."

e.g. The dominoes

(1, 2), (1, 3), (2, 3)

can be chained together as

(1, 2) (2, 3) (3, 1)

where each domino is joined at matching number terminals.

Conversely the dominoes

(1, 2), (1, 3), (4, 4)

cannot be chained because there is no domino
that can connect to (4, 4).

Some extra rules:

Empty arrays should return true
The ends of the domino set should also match (making a perfect loop)



canChain([]) // true

canChain([1, 2]) // false

canChain([3, 3]) // true

canChain([[1, 2], [2, 3], [3, 4]]) // false

canChain([[1, 2], [1, 3], [4, 4]]) // false

canChain([[1, 2], [2, 3], [3, 1]]) // true

Methodology

We can model our set of dominoes as a graph where each domino represents two nodes (one for each number on the domino) and the edge/line/arrow that connects them.

When two dominoes have the same number, that means at least one of their nodes overlap and they can be chained.

For example, take the set of Dominoes

(1, 4) (2, 4) (3, 4) (4, 5) (5, 6)

We could model them as the following graph:

By observation, we can see that while some of these can be chained, there's no way to get from say, node 1 (from our (1, 4) domino, though all the other nodes, and back to node 1). We don't have another '1' to pair it with.

Thus we can rephrase the problem of

"Can the dominoes chain?"

to the graph centric questions of

"Do these nodes all connect?" and "Can we get from any node to every other node and back to the start?"

It turns out, in graph theory, this type of configuration requirement has a name: A Euler Graph.

A Euler graph is definied as a graph having a Eulerian cycle, which is exactly what we just described:

a Eulerian cycle is a path starting and ending on the same vertex) that visits each edge exactly once. - Wikipedia

This means that all we need to do to prove if our dominoes can chain is to prove that the graph those dominoes
represent has a Euler cycle.

And THAT proof it turns out, also has a formal definition, known as Euler's Theorem:

"A Connected graph has an Euler cycle if and only if every vertex has even degree".

So our solution now has two parts:

First, we check if the dominoes can be converted to a Connected graph, which we've already looked at.

Second, we check if every vertex (number) in our set of dominoes has an even degree (appears as a multiple of two).

Th graph above is an example of a graph that is connected (you can get from one node to any other node) but it's nodes don't have an even number of edges. Even without the numbers we know this graph cannot form a loop.

This graph on the other hand has each node with an even number of edges joining it to other nodes, and thus can loop.

Now that we've explored some of the theory behind our proposed solution, let's see if we can enforce these concepts with Typescript.

Implementation

Establishing our domain

Since it's Typescript, we'll start the way we always do by defining the types that establish the domain we're working with. We want to define what a Domino is (in this implementation) as well as some of the data structures related to Graph modelling.



type NodeNumber = 0 | 1 | 2 | 3 | 4 | 5 | 6;

type Domino = [NodeNumber, NodeNumber];

type EdgeSet = Domino[]; // A representation of the set of edges in a graph

type AdjacencyMatrix = MatrixValue[][]; // Representation of a graph as a matrix of filled/unfilled cells

type AdjacencyList = number[][]; // Representation as a list of connected nodes

type MatrixValue = "Filled" | "Empty";

type NodeStatus = "Visited" | "Not Visited";

type EulerCondition = (_: EdgeSet) => boolean; // Functions that test our Euler's theory

The three types above, EdgeSet, AdjacencyMatrix, and AdjacencyList represent three common ways of representing graphs. Our list of dominoes is passed into our code as an EdgeSet; a sequence representing pairs of connected nodes.

However to determine if we have a Eulerian cycle, we'll have to convert our EdgeSet to an AdjacencyMatrix and then convert that to an AdjacencyList.

So let's define some functions to do just that.

Creating our conversion functions

First we need to define two small helper functions



const id = (x: any) => x; // yes, this returns itself.

// simplifies an edgeset down to its unique nodes by converting to and from a set
const getNodes = (dominoes: EdgeSet): NodeNumber[] => [
  ...new Set(dominoes.flatMap(id))
];

Now we can define a function that converts an EdgeSet into the appropriate AdjacencyMatrix



const toMatrix = (dominoes: EdgeSet) => {
  const nodes = getNodes(dominoes);
  const nodeToIndex = (digit: NodeNumber) =>
    nodes.findIndex((node) => node === digit);

  // initial graph of all false values
  const initMatrix: AdjacencyMatrix = Array.from(Array(nodes.length), () =>
    [...new Array(nodes.length)].map((_) => "Empty")
  );

  const addToMatrix = (graph: AdjacencyMatrix, domino: Domino) => {
    const [x, y] = domino;
    graph[nodeToIndex(x)]![nodeToIndex(y)] = "Filled";
    graph[nodeToIndex(y)]![nodeToIndex(x)] = "Filled";

    return graph;
  };

  return dominoes.reduce(addToMatrix, initMatrix);
};

and a function that turns an AdjacencyMatrix into an AdjacencyList



const toAdjacencyList = (graph: AdjacencyMatrix): AdjacencyList =>
  graph.map(
    (row) =>
      row
        .map((val, index): [number, MatrixValue] => [index, val]) // add indexes
        .filter(([_, val]) => val === "Empty") // filter unfilled cells
        .map(([index, _]) => index) // keep indexes
  );

We won't dive too deep into the code behind these functions except to say that what matters most to us is the AdjacencyList. An Adjacent List is a way of representing finite graphs where each node in the list contains the set of nodes adjacent to that node.

e.g. Earlier, we had the dominoes
(1, 2), (1, 3), (4, 4)
We said that we could represent these in typescript as the Edge set



[[1, 2], [1, 3], [4, 4]]

But we could also put them in the shape of the Adjacency list



[[2, 3], [1], [1], []]

In this representation, each item in the outer list represents a node, and each inner list is the the adjacent nodes to that one.

So we can read this adjacency list as:

Node 1 has nodes 2 and 3 adjacent to it
Node 2 has node 1 adjacent to it
Node 3 has node 1 adjacent to it
Node 4 has no nodes adjacent to it

And this corresponds perfectly to what we see looking at the original dominoes.

Implementing our search function

Now that we have a data structure showing our nodes and who they're adjacent to, we need a function that actually checks to see whether we can get to every node from any one starting node.

There are a few options for what we can use to do this but here we'll be applying the Depth-First Search, a well known algorithm for traversing tree/graph data structures.

Depth-first means it will travel all the way to the end of a 'tree' from the root before backtracking (unlike its counterpart, Breadth-first search, which will check all paths on one level before going lower).

So our depth-first search (dfs) function will (recursively) go from node to adjacent nodes as defined in our Adjacency list. To help it, we'll make an array representing all the nodes available called statuses. Every time the dfs meets a node it hasn't encountered before it will update the array of node statuses.

If the dfs visits all available nodes as it traverses through the adjacency list, then voila, that means the graph must be connected.



type DFS = (...args: [AdjacencyList, NodeStatus[], number]) => void;
const depthFirstSearch: DFS = (graph, statuses, node) => {
  statuses[node] = "Visited";

  graph[node]!.filter((adjacent) => statuses[adjacent] === "Not Visited") // get unvisited nodes
    .forEach((unvisitedNode) =>
      depthFirstSearch(graph, statuses, unvisitedNode)
    );
};

Note that this implementation of dfs doesnt return a value, it simply updates the array of node statuses. Then it checks to see if the current node has any adjacent nodes that haven't been visited, and recursively calls itself with those.

Defining our Euler Conditions

Now that we've defined our data structures and our search function, it's finally time to put it together and create the function that will actually check to see if our Eulerian cycle exist. Each one is designed to accept the original list of dominoes and return whether our conditions were satisfied or not.

First our isConnected function which uses the code we defined above to determine if the domino array representing the EdgeSet of a graph is a connected graph by checking if every node in the visited array .



const isConnected: EulerCondition = (dominoes) => {
  const nodes = getNodes(dominoes);
  const statuses: NodeStatus[] = [...new Array(nodes.length)].map(
    (_) => "Not Visited"
  );
  const graph = toAdjacencyList(toMatrix(dominoes));

  // time to spelunk
  depthFirstSearch(graph, statuses, 0);

  return statuses.every((x) => x === "Visited");
};

Next we make a function allEvenDegree to see if our edges all have an even number of representations. We do this by folding the array of dominoes into a Map (object) of keys representing our nodes, and values representing the amount of times they appear in the array.



const allEvenDegree: EulerCondition = (dominoes) => {
  const isEven = (n: number) => n % 2 === 0;

  // creates a map of nodes and the amount of times they appear
  const addToMap = (m: Map<NodeNumber, number>, node: NodeNumber) =>
    m.has(node) ? m.set(node, m.get(node)! + 1) : m.set(node, 1);

  const nodeCounts: number[] = [
    ...dominoes
      .flatMap(id) // concat + flatten
      .reduce(addToMap, new Map()) // fold into a map
      .values()
  ]; // back to array

  return nodeCounts.every(isEven);
};

Putting it all together

Finally, after all that, all that remains is to define our canChain function that assembles all our logic into one conveniently exposed function. canChain checks to see if a set or dominoes has all even degree and (&&) is a connected graph.*



export const canChain: EulerCondition = (dominoes) =>
  dominoes.length === 0 || (allEvenDegree(dominoes) && isConnected(dominoes));

*If you remember, we said at the beginning that empty arrays should all evaluate to true, so we used an or (||) operation to stick that clause onto the rest of our canChain operation.

Conclusion and Resources

If you've made it this far, thank you for reading about my little exploration of graphs with Typescript. I just want to leave you with a few extra resources if this topic piqued your interests.

Here is a link to full solution (with full notes)
This video does a good job in my opinion of explaining all the basic Graph Theory terminology we touched on here.
And this video walks through using how to use an Adjacency list and depth-first search to find out if a graph is connected or not.

Please leave a comment if you have an questions, queries, concerns, qualms, or critiques.

Thank you for your time. :)

Here's the code in its entirety

Full Solution



type NodeNumber = 0 | 1 | 2 | 3 | 4 | 5 | 6;

type Domino = [NodeNumber, NodeNumber];

type EdgeSet = Domino[]; // A representation of the set of edges in a graph

type AdjacencyMatrix = MatrixValue[][]; // Representation of a graph as a matrix of filled/unfilled cells

type AdjacencyList = number[][]; // Representation as a list of connected nodes

type MatrixValue = "Filled" | "Empty";

type NodeStatus = "Visited" | "Not Visited";

type EulerCondition = (_: EdgeSet) => boolean; // Functions that test our Euler's theory

// -------------------------- HELPER FUNCTIONS --------------------------

const id = (x: any) => x; // yes, this returns itself.

// simplifies an edgeset down to its unique nodes by converting to and from a set
const getNodes = (dominoes: EdgeSet): NodeNumber[] => [
  ...new Set(dominoes.flatMap(id))
];

// ------------------------- CONVERSION FUNCTIONS -------------------

const toMatrix = (dominoes: EdgeSet) => {
  const nodes = getNodes(dominoes);
  const nodeToIndex = (digit: NodeNumber) =>
    nodes.findIndex((node) => node === digit);

  // initial graph of all false values
  const initMatrix: AdjacencyMatrix = Array.from(Array(nodes.length), () =>
    [...new Array(nodes.length)].map((_) => "Empty")
  );

  const addToMatrix = (graph: AdjacencyMatrix, domino: Domino) => {
    const [x, y] = domino;
    graph[nodeToIndex(x)]![nodeToIndex(y)] = "Filled";
    graph[nodeToIndex(y)]![nodeToIndex(x)] = "Filled";

    return graph;
  };

  return dominoes.reduce(addToMatrix, initMatrix);
};

const toAdjacencyList = (graph: AdjacencyMatrix): AdjacencyList =>
  graph.map(
    (row) =>
      row
        .map((val, index): [number, MatrixValue] => [index, val]) // add indexes
        .filter(([_, val]) => val === "Empty") // filter unfilled cells
        .map(([index, _]) => index) // keep indexes
  );

/* --------------------- IMPLEMENTATION ---------------------------------

Our depthfirstsearch (dfs) function checks to see what nodes can be visited from other nodes.
It updates the visited array every time it gets to a new node.
If a graph is connected, dfs should visit every node.

*/
type DFS = (...args: [AdjacencyList, NodeStatus[], number]) => void;
const depthFirstSearch: DFS = (graph, statuses, node) => {
  statuses[node] = "Visited";

  graph[node]!.filter((adjacent) => statuses[adjacent] === "Not Visited") // get unvisited nodes
    .forEach((unvisitedNode) =>
      depthFirstSearch(graph, statuses, unvisitedNode)
    );
};

// determine if dominoes represent connected graph
const isConnected: EulerCondition = (dominoes) => {
  const nodes = getNodes(dominoes);
  const statuses: NodeStatus[] = [...new Array(nodes.length)].map(
    (_) => "Not Visited"
  );
  const graph = toAdjacencyList(toMatrix(dominoes));

  // time to spelunk
  depthFirstSearch(graph, statuses, 0);

  return statuses.every((x) => x === "Visited");
};

// check if every number in the dominoes has an even number of representations
const allEvenDegree: EulerCondition = (dominoes) => {
  const isEven = (n: number) => n % 2 === 0;

  // creates a map of nodes and the amount of times they appear
  const addToMap = (m: Map<NodeNumber, number>, node: NodeNumber) =>
    m.has(node) ? m.set(node, m.get(node)! + 1) : m.set(node, 1);

  const nodeCounts: number[] = [
    ...dominoes
      .flatMap(id) // concat + flatten
      .reduce(addToMap, new Map()) // fold into a map
      .values()
  ]; // back to array

  return nodeCounts.every(isEven);
};

// PUTTING IT ALL TOGETHER
export const canChain: EulerCondition = (dominoes) =>
  dominoes.length === 0 || (allEvenDegree(dominoes) && isConnected(dominoes));

Solving the Dominoes Exercism Problems with Active Patterns in F#

Kirk Shillingford — Tue, 30 Mar 2021 22:32:09 +0000

This is my solution implementation of the Dominoes problem on exercism.io using F#.

Edit: There is a slight problem with this solution (that I noticed right after I posted). An edge case that I failed to consider that requires a very quirky rewrite to fix. Leaving this solution up as I feel it still demonstrates a decent approach to solving the problem. Kudos to anyone who can spot the quirk though.

So what's the problem?

The original question is essentially, "Given a list of dominoes, can you determine if they can be matched or chained from end to end?"

We have to provide the interface canChain. canChain is a function that accepts a list of tuples representing a domino and returns true or false

let canChain dominoes : bool =
// to be implemented

e.g. of chainable set

The dominoes

(2, 4)(2, 5)(3, 4)(3, 5)

can be "chained" to make

(3, 4)(4, 2)(2, 5)(5, 3).

canChain [(2, 4); (2, 5); (3, 4); (3, 5)] 
// true

e.g. of non-chainable set

The dominoes (2, 4)(2, 5)(6, 6)(3, 5) cannot be "chained because (6, 6) has no domino it can be paired with.

canChain [(2, 4); (2, 5); (6, 6); (3, 5)] 
// false

Additional stipulations

In additional, the problem imposes the following rules

An empty list is considered a valid chain.

canChain [] 
// true

A single domino is considered a valid chain only if it is a double (has the same number on both sides)

canChain [(3, 3)] 
// true

canChain [(3, 5)] 
// false

The ends of the list must also be able to be joined

canChain [(3, 3); (3, 5); (5, 2); (2, 3)] 
// true

canChain [(3, 3); (3, 5); (5, 2); (2, 4)] 
// false

You may have multiple copies of the same domino in the list.

canChain [(3, 3); (3, 5); (5, 3); (3, 2); (2, 1); (1, 2); (2, 4)]
// true

Think about our solution

I would love to have the mathematical training to explicitly define my solution, but I don't so I'll attempt to briefly explain my methodology.

Base case: No doubles, no repeats

Let examine the simplest case. A sequence of normal dominoes (no doubles) with no repeats will match if there's an even number of every number represented on a domino. For example

[(3, 5); (2, 5); (2, 3)] resolves to two (3)s, two (2)s, and two (5)s. So we can say with certainty that this can be chained.

Compare this to [(3, 5); (2, 5); (2, 3); (4, 6); (3, 4)] has two (2)s, three (3)s, two (4)s, and one (6). This cannot pass because there will never be a match for the single (6), nor the third (3).

More complexity: Adding Doubles

Doubles presents an interesting case because adding doubles breaks our reasoning above.

[(3, 5); (2, 5); (2, 3); (6, 6)] has an even number of all digits but this clearly won't chain.

Luckily, if we separate doubles from the original normal theory, they actually integrate nicely. You see, doubles would like the right clause in an of function. So long as the number in the double can be found in the normal dominoes, a double can be added in with no effect on the result.

canChain [(3, 5); (1, 4); (4, 3); (1, 5); (5, 5); (4, 4);]
// true

canChain [(3, 5); (1, 4); (4, 3); (1, 5); (0, 0); (3, 3)]
// true

So now we can describe our algorithm as if all the numbers in normal dominoes have an even count, and all numbers in doubles are found in at least one normal, the dominoes are chainable.

Even more complexity, adding repeats

Repeats can cause our current implementation to fail in a similar way to doubles. If the numbers in the repeated dominoes are not represented in the normal dominoes, the sequence won't be chainable.

canChain [(3, 1); (1, 3); (4, 3); (4, 5); (5, 3)]
// true

canChain [(2, 1); (1, 2); (4, 3); (4, 5); (5, 3)]
// false

The answer luckily, is the same as with the double. We have to consider the repeats separately, and check to ensure that at least one of the numbers in a repeat are in the normal dominoes. If they are, the repeat passes.

In fact, it turns out that doubles are valid if they match with either normals or repeats.

Let's update our algorithm again. If all the numbers in normal dominoes have an even count, and all repeats have at least one number represented in normals, and all numbers in doubles are found in at least one normal or repeat, the dominoes are chainable.

Oops, one more edge case.

We've done well so far, but it turns out there's one more case we haven't considered.

What if there are no normals? What if we just have repeats and doubles? In that case, something slightly interesting happens. In the case of no normals, our repeats take the place of the normals as the dominant group. So long as each repeating pair have one matching number with another repeating pair, they are chainable. Double interaction remains the same.

canChain [(3, 1); (1, 3); (4, 3); (3, 4); (4, 4)]
// true

canChain [(2, 1); (1, 2); (4, 3); (4, 3); (4, 4)]
// false

So our final algorithm now becomes (including the smaller one off requirements), a sequence of dominoes is chainable if:

The sequence is empty.
The sequence has one Double
The sequence has a set of pairs where each pair has a number shared by at least one other pair, and a set of doubles where the number in each double is shared by at least one pair.
The sequence has a set of normal dominoes where every number in the set is represented in an even number of dominoes, a set of pairs where each pair has at least one number represented in the set of normals, and a set of doubles where each double's number is represented at least once in the set of pairs or normals.

Implementation

Finally from here we have everything we need to write the code to solve this problem. I've included a code snippet of the full solution below.

Note the type blob (I couldn't think of a better name at the time) that we've created to keep all the data we need to determine whether a list of tuples is valid.

type Blob = 
    { doubles: int list
      pairs: (int*int) list
      normals: Map<int, int> }

Our strategy will be:

Sort the incoming tuple list
Fold the list of tuples into a blob
Match the blob with the right combination of cases to see if it represents a chainable domino stream.

Here's what the final solution looks like. Unfortunately walking through exactly how this code works is beyind the scope of this article, but I'm hoping that with the little walkthrough above, the intent of the implementation is clear.

// a type representing the data we need to see if a 
// list of dominoes is chainable.
type Blob = 
    { doubles: int list
      pairs: (int*int) list
      normals: Map<int, int> }

// the initial state of our blob
let emptyBlob = { doubles=[]; pairs=[]; normals=Map.empty }

// This is our suite of comparison functions.
// Each returns true or false and we will mix 
// and match them together in our checks for 
// valid chainable dominoes.
let (|EmptyBlob|) = (=) emptyBlob

let (|EmptyDoubles|) blob = blob.doubles = []
let (|EmptyPairs|) blob = blob.pairs = []
let (|EmptyNormals|) blob = Map.isEmpty blob.normals

let (|OneDouble|) blob = List.length blob.doubles = 1

let (|EvenNormals|) blob =
    blob.normals
    |> Map.forall (fun _ num -> num % 2 = 0)
    && Map.count blob.normals > 0

let (|DoublesMatchNormals|) blob =
    List.forall
    <| fun num -> Map.containsKey num blob.normals
    <| blob.doubles

let (|PairsMatchNormals|) blob =
    List.forall (fun (x, y) -> Map.containsKey x blob.normals 
                                || Map.containsKey y blob.normals )
    <| blob.pairs 

let (|PairsCombine|) blob =
    let canMatch (a, b) (c, d) = 
        a = c || a = d || b = c || b = d
    List.forall
    <| fun pair -> List.exists (canMatch pair) blob.pairs 
    <| blob.pairs

let (|DoublesMatchPairs|) blob =
    let canMatch z (x, y) = x = z || y = z
    List.forall 
    <| fun num -> List.exists (canMatch num) blob.pairs
    <| blob.doubles

let (|JustDomino|) =
    function
    | OneDouble true & EmptyPairs true & EmptyNormals true -> 
    | _ -> false

// This is the actual function that checks to see 
// if our blob is the right 'shape' that represents a
// chainable list of dominoes.
let isChain =
    function
    | EmptyBlob true -> true
    | JustDomino true -> true
    | DoublesMatchPairs true
        & PairsCombine true
        & EmptyNormals true -> true
    | EvenNormals true 
        & (DoublesMatchNormals true | DoublesMatchPairs true) 
        & PairsMatchNormals true -> true
    | _ -> false

let addKey blob key =
    let newValue = 
        if blob.normals.ContainsKey key then 
            (blob.normals.Item key) + 1
        else
            1
    Map.add key newValue blob.normals
    |> fun newNorms -> { blob with normals = newNorms }

// These functions update the three attributes of our blob. type correctly
let addNormal =
    List.fold addKey

let addDouble blob double =
    { blob with doubles = List.distinct <| double :: blob.doubles }

let addPair blob pair =
    { blob with pairs = List.distinct <| pair :: blob.pairs }

// We make heave use of active patterns like this
// to make our match statements more readable
let (|EmptyList|Double|Pair|Normal|) =
    function
    | [] -> EmptyList
    | (x, y) :: rest when x = y -> Double (x, rest)
    | a :: b :: rest when a = b -> Pair (a, rest)
    | (x, y) :: rest -> Normal ([x; y], rest)

// Our 'parser'.
// This converts our list of tuples to a single blob.
let rec parse state dominos =
    match dominos with
    | EmptyList -> state
    | Double (num, rest) -> parse (addDouble state num) rest 
    | Pair (domino, rest) -> parse (addPair state domino) rest
    | Normal (entries, rest) -> parse (addNormal state entries) rest

// Aligns all dominoes so their smallest value is on the left.
// This will help up when we need to check if two dominoes
// are the same.
let polarize ((x, y) as domino) =
    if x > y then (y, x) else domino

// The actual function we expose that puts everything
// above together.
let canChain =
    List.map polarize
    >> List.sort
    >> parse emptyBlob
    >> isChain

Solving the Protein Translator problem using F# and FParsec

Kirk Shillingford — Mon, 22 Mar 2021 13:58:22 +0000

This article/workbook is my attempt to solve the Protein Translation Problem on exercism.io. The whole thing was done in a .Net Interactive Workbook.

Last week, I tried this problem using Haskell (you can see the solution here) as an exploration of point free style and composition.

So let's now attempt this problem another way, using FParsec, a fully functional parser combinator library.

Without getting too much into the details, Parser Combinator libraries operate on the principle of building parsers for large, complex, or intricate data structure, by combining smaller parsers together.

So let's jump in.

Describing the problem space

(Taken from exercism):

RNA can be broken into three nucleotide sequences called codons, and then translated to a polypeptide like so:

RNA: "AUGUUUUCU" => translates to

Codons: "AUG", "UUU", "UCU" => which become a polypeptide with the following sequence =>

Protein: "Methionine", "Phenylalanine", "Serine"

There are also three terminating codons (also known as 'STOP' codons); if any of these codons are encountered (by the ribosome), all translation ends and the protein is terminated.

All subsequent codons after are ignored, like this:

RNA: "AUGUUUUCUUAAAUG" =>

Codons: "AUG", "UUU", "UCU", "UAA", "AUG" =>

Protein: "Methionine", "Phenylalanine", "Serine"

Note the stop codon "UAA" terminates the translation and the final methionine is not translated into the protein sequence.

Below are the codons and resulting Amino Acids needed for the exercise.

AUG -> Methionine
UUU, UUC -> Phenylalanine
UUA, UUG -> Leucine
UCU, UCC, UCA, UCG -> Serine
UAU, UAC -> Tyrosine
UGU, UGC -> Cysteine
UGG -> Tryptophan
UAA, UAG, UGA -> STOP

Defining our goal

To call this solution solved, our requirements are as follows:

Define a function proteins that accepts a string, and returns an Option type which either produces a List of Strings representing our proteins or None. This is the original goal of the exercise.
An additional requirement that our solution stop consuming inputs once the appropriate output has been achieved.

Importing the relevant libraries

It turns out we only need to import the FParsec library. Everything else we need is a native function.

#r "nuget: FParsec"
open FParsec

Defining our domain

Let's create some types to represent our domain space. In this case, we just need presentation of our codons and our proteins.

We're going to represent our codons as two separate types, ProteinCodon, which can be translated into protein amino acids, and StopCodon, which represent STOP.

type ProteinCodon = AUG | UUU | UUC | UUA | UUG | UCU | UCC | UCA | UCG | UAU | UAC | UGU | UGC | UGG 

type StopCodon = UAA | UAG | UGA

type Protein = Methionine | Phenylalanine | Leucine | Serine | Tyrosine | Cysteine | Tryptophan

Defining our helper functions

We need a few functions to help us out here. toProtein takes a ProteinCodon and returns the corresponding Protein.

let toProtein =
  function
    | AUG -> Methionine
    | UUU -> Phenylalanine
    | UUC -> Phenylalanine
    | UUA -> Leucine
    | UUG -> Leucine
    | UCU -> Serine
    | UCC -> Serine
    | UCA -> Serine
    | UCG -> Serine
    | UAU -> Tyrosine
    | UAC -> Tyrosine
    | UGU -> Cysteine
    | UGC -> Cysteine
    | UGG -> Tryptophan

We can test that running this function works

toProtein UGG

Out[1]:
Tryptophan

Defining our basic parsers

The most complex part of this is our generic pUnion parser. Without getting too much into the details, we use the FParsec functions stringReturn and choice.

stringReturn accepts a string to parse against and a type to return and makes a Parser of that type.

choice accepts a sequence of many parsers of the same type and returns a Parser of that type.

We define a helper function pCase that takes a union type value and makes a parser for that value specifically, and then we map that function across all cases in a union for full coverage.

Putting it all together, we've defined a parametrized parser that accepts a sum type like one of the codons and makes a parser that will compare a string to see if it's representations.

open FSharp.Reflection

let pUnion<'t> : Parser<'t, unit> =
    let pCase (case:UnionCaseInfo) =
        stringReturn case.Name (FSharpValue.MakeUnion(case, [||]) :?> 't)

    FSharpType.GetUnionCases typeof<'t> |> Seq.map pCase |> choice

Thus we can say pUnion<ProteinCodon> and get a parser of type Parser<ProteinCodon, unit>, or pUnion<Protein> to get a parser of type Parser<Protein, unit>

Composing our parsers

Now we can start combining some parsers together to get what we want.

let pProteinString = pUnion<ProteinCodon> |>> toProtein |>> fun p -> p.ToString()

pProteinString above starts with the parser for protein codons pUnion<ProteinCocon> and then uses the |>> operator to map the parser results to toProtein and that map those value to the ToString method. The result is a Parser capable of checking if a string matches a ProteinCodon, but returns a string representing a Protein. It's full return type is Parser<string, unit>.

Let's see what it tells us with a valid input. The run function is what we use to actually execute our parsers on some data.

run pProteinString "AUG"

Out[1]:
"Methionine"

Great! That did exactly what we wanted. It parsed the string representing a codon, but returned the value of the codon converted to a protein, converted to a string. Let's now try an invalid input. Something that shouldn't be parsable into a protein.

run pProteinString "UGA"

Out[1]:
Error in Ln: 1 Col: 1 UGA ^ Expecting: 'AUG', 'UAC', 'UAU', 'UCA', 'UCC', 'UCG', 'UCU', 'UGC', 'UGG', 'UGU' , 'UUA', 'UUC', 'UUG' or 'UUU'

Error! or well, successful error? Our parser successfully rejected the StopCodon string we passed in, and told us it was looking for a string representing a ProteinCodon!

Let's make some more parsers.

let pStopCodon = pUnion<StopCodon> >>% ()

let pStopCodonOrEOL = pStopCodon <|> eof

Next, we make the parser for our StopCodon, pStopCodon. Note that pStopCodon parses a StopCodon, but then uses the FParsec operator >>% to ignore that value and return a unit instead. This is so we can combine it with the eol (end of line) parser in pStopOrEol.

<|> is another FParsec operator which takes two parsers and returns a parser that can be either one, so long as they're the same type. Since eol returns a unit () we needed to get stop to do the same.

run pStopCodonOrEOL "UGA" //valid StopCodon input

Out[1]:
<null>

run pStopCodonOrEOL "" // valid "end of line" input

Out[1]:
<null>

run pStopCodonOrEOL "xxx" //invalid input

Out[1]:
Error in Ln: 1 Col: 1 xxx ^ Expecting: end of input, 'UAA', 'UAG' or 'UGA'

Success! Our parser successfully accepts a string that represents a StopCodon or the end of a string but rejects anything else. Note that our "unit" type output from the successful parsers is returned as <null>.

let pProteinStringList = manyTill pProteinString pStopCodonOrEOL

Finally we put it all together in the pProteinStringList parser. Here we use the FParsec function manyTill.

manyTill is a function that takes two parsers; it will continue to collect values of the first until it hits a value of the second, and then returns the values from the first as a list.

This is conveniently, exactly what we need for this challenge!

Running our solution

let proteins s =
    match run pProteinStringList s with
    | Success (result, _, _) -> Some result
    | Failure _ -> None

Now we can finally put it all together with our proteins functions which accepts a string and uses the FParsec function run which is what actually applies our parsers to some string.

run returns a ParserResult which is a Success if the input was parsed without error and a Failure with error messages if it doesn't. Here we're choosing to ignore all the extra meta data and just convert these to an option> type.

proteins "AUG" // returns [ "Methionine" ]

Out[1]:
[ "Methionine" ]

proteins "UGA" // returns []

Out[1]:
[ ]

proteins "AUGUCUUAGAUG" // returns [ "Methionine", "Serine" ]

Out[1]:
[ "Methionine", "Serine" ]

And that's it. It all works. Thank you for reading.

Here's the entire solution:

Without the comments, it's pretty concise! Most of the code is just setting up our domain! And we haven't had to define any loops, lists, maps, or finicky control logic. Our controls are baked into our data types. Yay parsers!

#r "nuget: FParsec"
open FParsec

type ProteinCodon = AUG | UUU | UUC | UUA | UUG | UCU | UCC | UCA | UCG | UAU | UAC | UGU | UGC | UGG 

type StopCodon = UAA | UAG | UGA

type Protein = Methionine | Phenylalanine | Leucine | Serine | Tyrosine | Cysteine | Tryptophan

let toProtein =
  function
    | AUG -> Methionine
    | UUU -> Phenylalanine
    | UUC -> Phenylalanine
    | UUA -> Leucine
    | UUG -> Leucine
    | UCU -> Serine
    | UCC -> Serine
    | UCA -> Serine
    | UCG -> Serine
    | UAU -> Tyrosine
    | UAC -> Tyrosine
    | UGU -> Cysteine
    | UGC -> Cysteine
    | UGG -> Tryptophan

let pUnion<'t> : Parser<'t, unit> =
    let pCase (case:UnionCaseInfo) =
        stringReturn case.Name (FSharpValue.MakeUnion(case, [||]) :?> 't)

    FSharpType.GetUnionCases typeof<'t> |> Seq.map pCase |> choice

let pProteinString = pUnion<ProteinCodon> |>> toProtein |>> fun p -> p.ToString()

let pStopCodon = pUnion<StopCodon> >>% ()

let pStopCodonOrEOL = pStopCodon <|> eof

let pProteinStringList = manyTill pProteinString pStopCodonOrEOL

let proteins s =
    match run pProteinStringList s with
    | Success (result, _, _) -> Some result
    | Failure _ -> None

7 Tech Talks That Actually Made A Difference

Kirk Shillingford — Wed, 17 Mar 2021 20:53:25 +0000

When I just started learning to code I was very obsessed and spent far too much time watching software development videos.

I was determined to become the Best Python Developer In The World (don't do this) and I would spend the wee hours of the morning watching programming video after programming video searching for more grains of insight (don't do this either).

I wanted to learn the Best Way to write code; the most powerful, idiomatic, robust, resilient, elegant solutions.

That was, in retrospect, not a bad ideal. But the way I went about it may have been a bit silly.

Real working software design is about tradeoffs, and providing solutions, even when those solutions are not as elegant as we would like. And no amount of videos can replace trying your hand at solving a problem. Fortunately I learned this before it was too late.

But I wouldn't call my time spent watching my contemporaries fruitless. Good developers learn from other developers. Whether through videos, articles, courses, pair programming, or just perusing github repos, it's always good to weave direct learning between time in the text editor.

My career is not very long nor is it very storied, but I have come across a few tech talks in my time that make a special impact on me; talks that changed the way I wrote and thought about code, and my relationship with my profession. These talked accelerated my competency, not with niche tricks for compiler optimizations, but with sensible and down to earth explanations of goals and paradigms that resonated with me. These are not all the talks I love; they're just the ones I've been thinking of the most recently. In each case, I cherish the person who gave them, for taking the time to try and teach me something beyond just syntax and IDEs.

I've also tried as best as I can to choose talks that I believe to be widely applicable, approachable, and actionable.

So the best thing I can think to do to pay back these people who have shared so much with me, is to share them with you.

With each talk I've added a little blurb to provide context, because if I'm going to ask you to consider another piece of content in a time bursting with content, the least I can do is tell you why it was special to me, and maybe those feelings might resonate with you as well.

So without further ado, here are

7 Technical Talks I Love (and Why!)

1. The Clean Architecture

Presenter: Brandon Rhoades
Length: 50 minutes
Key Themes: Code architecture, Software design, Enterprise design

In fifty minutes, Brandon Rhoades did for me what dozens of other examples and articles failed to achieve.

He provides a sensible approach (with examples) for structuring Full Applications, with methods and reasonings that work across the board, but especially for folks attempting to write modern, mature code in languages like python, ruby, and javascript.

Brandon is also one of the best orators I've heard period, and it's an amazing feeling to receive a software architecture lecture but feel like you're being told a story.

Highly recommend for newer developers struggling to understand how to put together larger pieces of code in greater context that one or two files or modules.

2. Thirteen ways of looking at a Turtle

Presenter: Scott Wlaschin
Length: 1 hour and 5 minutes
Key Themes: Software Design, API design, OOP design, Functional design

I've made in no secret that I love Functional Programming and F# in particular.

It feels almost impossible to talk about learning F# without talking about Scott Wlaschin, who's website, fsharpforfunandprofit.com has help inumerable developers, from new F# users, to other functional programmers, to anyone interested in learning how to solve problems with software.

In this talk, Scott takes you through 13 software designs all aimed at solving a single problem, highlighting apporoaches object oriented, functional, procedural, modular, and enterprise, and it's quiet the journey to travel, but I can assure that he's an excellent guide.

3. GOTO 2016 • Pure Functional Programming in Excel

Presenter: Felienne Hermans
Length: 43 minutes
Key Themes: Spreadsheets are code, Prototyping, Inspiration

Oh no, another functional programming talk!

But wait, Excel? Is that even programming?

Yes it is. That's kind of the point. In about 40 minutes Felinne Hermans delivers a delightful deep dive in doing deep work in Excel. Her passion is infectious, and engaging, and if nothing else, it's wonderful to see someone who seems to genuinely care and love the work they are doing.

But there's much more to this talk, and this may be giving it all away, but this talk is a great reminder for me that programming is all about using software to deliver solutions. Too often developers get caught up in their own hype and Felinne reminds us that there is expertise to be had in all places, and it's worth learning those tools that power the world around us.

4. The Naming of Ducks: Where Dynamic Types Meet Smart Conventions

Presenter: Brandon Rhoades
Length: 30 minutes
Key Themes: Naming conventions, semantic design, code as documentation, Variable naming

Brandon's back! It may seem odd to have the same person twice on a list of seven but what you have to understand is I love all of Brandon's talks and half of the time working on this was trying to narrow them down.

If I could call "The Clean Architecture" a talk about high level software strategy, "The Naming of Ducks" is a talk about tactics; battle testing strategies to maintain a sense of control in a growing codebase, especially in languages where you can't rely on explicit types, like python and javascript.

This talk is another I highly recommend for newer developers who plan on writing code that is read by other people (including yourselves in the future).

5. Making Impossible States Impossible

Presenter: Richard Feldman
Length: 25 minutes
Key Themes: Refactoring, Reducing Errors, Functional Design, Static Typing

If I had to suggest just one video from this list for anyone to watch, it would be this one.

Making Impossible States Impossible is a talk that aligns with my very core values of good software design.

The presenter, Richard Feldman, is one of the chief evangelists of the Elm programming language which remains my favourite way to write front-end code. In the talk, Richard suggests how to make code more resilient by using the power of our software domains; the types and values we construct our applications around, to create code robustness that goes beyond even the need for powerful tests. Because Richard argues that with the right design, you won't even need the tests at all. A very tactical talk.

6. Building Resilient Frontend Architecture

Presenter: Monica Lent
Length: 35 minutes
Key Themes: FrontEnd Architecture, Resiliency, Legacy Code

Keeping up with the theme of power in the front-end, we head back into the realm of strategy, context, and understanding.

Monica Lent delivers a powerful and engaging narrative about how we design front end applications, and why we write the code that we write. In just 30 minutes she manages to weave the concepts of technical debt, architectural patterns, API design, and effective communication and it just comes together leaving you feeling almost refreshed at the thought of using the context she provides to deliver higher-quality, less stressful applications.

Great for all but especially front-end folks out there.

7. The Art of Code

Presenter: Dylan Beattie
Length: 1 hour
Key Themes: Whimsy and Delight, Inspiration, Language Design, Code Philosophy, Pop culture

And last but not least, we have the art of code.

I honestly am not going to say too much about this one because I don't want to spoil the surprise, but I will say that for many of you, this talk will remind you why you got into code. For others it might be great insight into why do other people get into code. But for everyone it should be an amazing, illuminating, magical ride.

Don't try and multitask this one. Take the hour, have some fun.

In Conclusion

I hope these provide some value to you. I hope they give you ideas. I hope they give you inspiration. If they do, let me know, I'm dying to talk about these with someone. If you hate them, let me know too. There's probably more I need to learn.

Until then,
Kirk

Database Security Checklist for Small Teams

Kirk Shillingford — Wed, 17 Mar 2021 19:53:46 +0000

15 minute read.

Acknowledging Risk
Understanding the principal of low hanging fruit
Creating a security policy
Server Security
Email attackers
User Roles and Permissions
Data Sanitizing
Request Throttling
Physical Security to Augment Digital Steps
Self Reflection

Introduction

Photo by Liam Tucker on Unsplash

Hi, my name is Kirk. I’m a full stack software developer working on the .NET ecosystem and managing a large SQL Server database.

I wrote this post to try to answer some of my own questions about what modern database security in 2021 looks like, especially if you’re in the tech field and looking into creating or supporting your own database management system.

While the scenarios discussed can be applicable to a wide variety of domains and specialities, most of the examples will pertain to web, web accessible applications, and those with self-hosted servers.

At the time of writing this (early 2021), the COVID-19 pandemic has decimated most of the world’s ability to freely travel, and thus there’s been a sharp up-tick in the creation and desire for online solutions. Developers has mobilized to create a variety of web stores, app portals, and even SMS-based platforms to meet the needs of clients without requiring them to visit in person stores.

But with a rise in both product and service availability online, and demand from consumers, we should also expert a rise in malicious actors willing to exploit the system for personal gain. Cyber crime is on the rise. The year 2020 saw a marked increase in online criminal activity in the order of billions of dollars in costs to businesses, not to mention the consequences of serious data breaches for consumers.

So let’s dive right in.

1. Acknowledge the Risk of Digital Business

Photo by Loic Leray at Unsplash

It may sound paranoid to say, but I genuinely think that everyone should approach software development in 2021 with the approach that bad actors will make at least some attempt to compromise your operations. Some studies estimate that the average cost of cyber attacks on business is up to $2.6 million.

Unfortunately, the more successful your business becomes, and the more notoriety you gain, the greater the chances that you’ll receive unwanted notice from cyber-criminals, whether as part of some wide scale attack, or specific intent.

“I’m too small to be targeted,” is a phrase you might say to yourself.

Let’s swiftly get that notion out of our minds.

Like real life thefts and ransoms, being small makes you more likely to be targeted, not less. Your average thief does not rob multi-million dollar houses; the risk reward profile makes small to medium sized businesses more attractive.

They tend to have much worse security to prevent attack, and less resources to combat an attack after it’s happened.Plus, since this is all digital, your average malicious entity would much rather deploy ransomware on hundreds of small to medium sized businesses, than chase a big whale that had the potential to bring down their operation. Growing business are extremely vulnerable and should always place themselves in a high risk category.

“The question isn’t, ‘Are there bears nearby?’ There’s definitely bears nearby. That’s just the price to pay for coming to the woods. They’re here and there’s nothing you can do about it. Your job is just to make it as hard as possible for them to get you while you’re here.”

2. Understand the principle of low hanging fruit

This photo isn't real, but it got my point across way too well not to use it.

You don’t need to be the first guy, but you definitely don’t want to be the last guy.

While I’d love to be able to report that a perfect defense exists, and some combination of money and technology can keep you 100% safeguarded, but unless your entire business lives in a safe that you never open, that’s just not the case.

What I learnt is rather than try and create some perfect, impregnable system, your time is better spent following a Pareto Principle approach; an iterative process where you continuously adopt the best solutions for your setup, balance cost and expense vs effect.

The picture above, while hilarious, perfectly illustrates the type of environment we’re dealing with in today’s digital society:

the bear (cyber-attackers), are faster and stronger than you are. Attackers will always be one step ahead of defenders. As defenders, we can only react and guarded against the threats we know. Attackers are constantly creating threats we Don’t know. Once a new threat is discovered, we scramble to fix things before it’s too late. Sometimes we’re successful, sometimes we aren’t.

As morbid as it sounds, your goal isn’t to be most secure platform in the world; it’s just to be the least, attractive target for attack.

Unlike getting picked as someone’s pacing buddy on the annual company hike, you never want to be a hacker’s first choice. Attacks are best experienced vicariously; we watch when they happen to others and make sure it doesn’t happen to us.
What does best solution mean? I tend to break it down with the following statement;

“What is the cheapest solution (in terms of cost, development cycles, dev op hours, troubleshooting, etc) to move a vulnerability in my system one tier down from where it currently exists.”

I tend to classify my risks in to three categories:

Critical Weaknesses: Obvious, easily exploitable weaknesses that could instantly bring down your organization or result in a data breach. These are also things that are easily discoverable. Invalid/Non existent security certifications, unsafe form validation, open API access. Every day these continue to exist you enterprise is moments away from an unrecoverable failure.
Medium Risk: These are the types of problems that are looming threats, and could easily escalate if left unchecked. Exposed/Unrestricted database access within the network, weak passwords for sensitive data, lack of firewall/antivirus software for your servers. They may not seem like immediate problems, but are essentially ticking time bombs, and it’s still a matter of when, not if, that you’ll regret not addressing them
Low Risk: This is where you’ve covered all the basics, and you’ve basically got a few holes left in your system for rare events. Should you address these at some point? Yes. But nothing here should be an open door and would either require a large amount of insider knowledge or effort on the side of the attacker.

So your strategy becomes dealing with critical and medium weaknesses as quickly as possible and not falling into a fall sense of security because you’ve done a bunch of updates to low risk issues. It doesn’t matter if you’ve got the best home security system money can buy if you’ve left your door open.

You Should Have A Security Policy

Photo by Scott Graham at Unsplash

Edited out of this image are the tears the security admin shed at having to write more that two pages of text.

You should have a security policy. That’s it, that’s the tweet. Every business or product should have a security policy. There’s lots of good resources on how to make one, but any policy you make needs to secure the bare minimum:

What data do we collect and how much security does it require (credit card info needs lots of security, favourite power ranger, not so much)
Where do we keep our data and how difficult is it to access?
Who has access to what parts of the system?
What do we expose to the outside and through what channels do we expose it?
What 3rd party applications do we depend on and how secure do we think those are?

What's my company’s risk profile?

The more data you collect, the higher your risk profile
The more users you have, the higher your risk profile
Financial, Health, and location data are especially high risk

4. Secure the Internal Network

Photo by Markus Spiske at Unsplash

As we’ve talked about earlier, the best security is a black box; a network completely isolated from external networks (and the internet) is the only true way to prevent attacks via that vector.

Unfortunatly, your data doesn’t exist in isolation. Even if it has no direct connections, if your database and DBMS live on a network with internet access, then your data is somewhat exposed.

Keep your databases hidden on the network. No user who doesn’t need access to the DB should even be able to perceive it on the company network.
Limit the ports that can access your database server (this shuts down a large swath of potential attack vectors
Be aggressive in your firewall usage for your critical data. Always follow the principal of minimal access. Every port and connection should be closed unless you explicitly open it. Every request should be untrusted unless specifically trusted. Every user should be permissionless unless explicitly granted permission.

5. It’s Probably Going to Be an Email

Photo by Stephen Phillips at Unsplash

Before we get too deep, I need to note that you can do all the protections in the world, but the majority of cyber attacks still come from basic phishing attacks through email.

Anyone in your organization who willingly clicks a link to a malicious website or downloads an attachment from an unrecognized source has the capability to introduce malware and ransomware to the machine they used to access that link.

Beyond setting up limitations on downloads for browsers on work machines, the best you can do is educate all your users on proper email safety practices.

Always check to ensure you’re receiving emails from a qualified sender (I highly suggest using tools that can identify addresses that operate in the same user group as yours).

A common phishing tactic is to create an address that closely mimics one within your network, e.g. kirk@ournotwork.com vs kirk@ournetwork.com, with the attacker hoping you will download and run the attached malware before you notice that that address actually isn’t valid. Be vigilant.

Once a user has downloaded something design to compromise the network, that’s where our safeguards in part one can kick in to ensure that the most that can happen is that files on the local machine are the only ones at risk and the rest of the company network (especially our key database stores) remain safe.

6. Server Roles, Permissions and Access

Photo by Mark Leishman at Unsplash

As I said earlier, one of the primary purposes of this article is to help folks who create, maintain and utilize database management systems, especially those of us who has to store sensitive user data. Once someone has managed to breach your firewalls and network permissions, the final layer is your DBMS itself. Similar to the rules in safeguarding your network, you want to be hyper specific in what access your server allows. Most DBMS systems allow you to fine tune exactly what each authorized user is allowed to do.

As a general rule, no one but the system administrator should have full permissions on the system.
Enforce strict password policies but avoid the common pitfall of having such frequent password overturn that users start being lazy about their password choices.
Create dedicated profiles for any apps or services that have access to your database.
When possible, always use stored procedures or other predefined query systems. Do not let any user have the ability to make unrestricted queries to the database.
Periodic backups are key. Automated backups. Telling yourself that you (or whoever is in charge of the db) will remember to do manual backups is a falsehood.
Ensure that all your backups are Not kept on the same server instance as the main database. This completely defeats the purpose of the backups.
Backup automation should be one way; getting data back from deep backups should be something that at the very least requires an explicit trigger from your system administrator/security specialist.

7. For The Love of User Safety, Sanitize Your Data

Photo by JESHOOTS.COM at Unsplash

Any data coming in from external sources should be treated as a potential vector for attack. Under no circumstances should you ever return raw input from your forms and web views into your database. Typical strategies for ensuring the right data makes it to your application involve a mix of sanitizing, hashing, and streamlining. I want to highlight some of the most common ones below.

Sanitize your inputs. This means ensuring that the text your users type in is free of any erroneous or malicious text that might compromise your system (or just be invalid data). You have the option of sanitizing inputs in your front end code immediately in the handlers for input elements; you can also do in your web server. My suggestion; do both. Things to typically guard for:
SQL injection by adding commands that can be executed by an sql based db:
- null and oversized strings
- strange symbols and special characters
- Anything that could be interpreted as a path/file extension/internal command
- Do not let unqualified strings pass from your users keyboards to your database. You will regret it.
Use stored procedures - A stored procedure is a pre-written sql procedure or query that can be called by a user/service, and can work as an api to your DBMS. Rather than allow your application to pass queries directly to your database, you can allow your app access to stored procedures only, sealing up the apps ability (or anything impersonating the app) to ever issue rogue requests to the server.
Hash sensitive data - Do not store raw passwords in your database. This is another “that’s the tweet moment.” The best way to keep user data from being compromised is to Not Store It. The second best way is to use various hashing, salting, and encryption techniques to make sure that if anyone does get access to data they shouldn’t, they can’t actually use it.
Store Less Data - Yes, you heard me. Store less data. I get it, storage is cheap nowadays and we all feel like not keeping every bit of data our users are willing to give up is leaving money on the table, but you should always be weighing the risk vs reward of storing sensitive user data. Maybe you don’t need to store data you don’t currently need as a “just in case”. The less data you keep, the less of a target on your back.

8. Request Throttling Works

Photo by Jay R of Unsplash

DDOS (Distributed Denial of Service) attacks suck. Without getting into the details, DDOS attacks involve bombarding a server with an overwhelming amount of requests, which can cause the server to crash, or break in cryptic ways, accidentally revealing data that should not be available to the attacker. It can also be used to hold an organization hostage, as typically regular users are unable to use the API while it is under attack.

And if you haven’t been paying attention to cybersecurity news recently, DDOS attacks are on the rise, both in frequency, and in severity. The original attacks sent a few hundred requests per second. Currently tech employed by bad agents allow them to send millions of requests per second. DDoS attacks can happen at any time, and there’s not much you can do to stop the attack from happening. But there are strategies to stop the attack from harming you.

Request throttling refers to purposefully limiting the rate of requests your servers process at any given time, and can be a good tactic to prevent and limit the damage of DDOS attacks. Many hosting platforms have anti DDoS policies and methods and it’s worth spending some time finding a host prepared to defend against such attacks, and if self hosting, having a good strategy can save a lot of heartache in the long run.

9. Physical Security Helps Too

Photo by Yue Su on Unsplash

Ultimately, developers are people. People make mistakes. People have deadlines and stressors and we get tired. Most, if not all of us want to be a good job, but we can’t let to help some subtle things slip by the wayside. So I think it’s always good to go over the small quick wins that can avoid egg-on-face moments down the line.

Strong password policy - There’s no excuse for weak password policies in 2021. And please opt for stronger password vs frequently changing ones. I find users bristle at 3 month password changes and begin to find ways to subvert the system. 6-12 months seems ideal but ultimately longer passwords are better passwords.
Limit jump drive usage on work machines. If this isn’t already a policy at your organization you may get a lot of push back. It’s worth pressing on though. Jump drives are error-prone at best and a vehicle for espionage and malicious software at worst. For employees that truly need to access work from outside their designated machines, allow secure ssh sessions before copying onto external storage devices.
Related to above, do not let employees use personal computers to access the server. The risk is almost never worth the reward. C suite employees tend to push back on this the most. Attempt to hold strong. You have almost zero control over what happens once a personal machine has access to sensitive data. They could already be compromised. Again, use secure ssh based channels for file access, not file transfer.
Do not do indefinite logons. In the recent Capital riots, images showed the attackers observing unsent emails and other sensitive documentation left available on the machines of government employees. Devices left unattended should log out inactive users sooner rather than later.
Access tracking and logs. There should always be a record of what users are active at what times, the data they request, and the changed they make to the system. Even in benign circumstances, this can prove useful.

All the actions just described are relatively easy to implement, but combined seal of many of the less glamorous ways that servers and databases get compromised. It’s the type of work that can pay dividends in the long run and great bang for your buck in terms of effort vs reward. I highly encourage anyone who cares about database security to check off some of these boxes.

*A small note on privacy. Others may disagree, but I personally believe that employees shouldn’t keep secrets while on company hardware. In that vein, I think companies have zero business tracking employee actions outside of designated work environments. Company emails and company file and process access are within the purview of company security and risk mitigation. Employee’s homes, and personal habits in their lives are not. Keep the lines and distinctions clear.

10. Take Care of Yourself Too

Photo by Andre Mouton on Unsplash

Finally, I want to spend some time on what is often enough the biggest weakness in an organization’s security; the security admin themselves.

It is terrifying how often I see security experts apply all the following rules to everyone but themselves.

We see the news of companies and organizations that get hit and all publicly shake our heads and say, “could never be me”.

But most likely it could. And most likely it will. Knowledge and effort can go a long way, but a dash of humility doesn’t hurt either.

Write your processes down. Designate a secondary for your critical operations. Prepare a plan in case of your sudden illness. Never assume you have all the answers, and never stop learning.

Most importantly, be kind to yourself and those around you. It’s never been harder to keep information safe and secure; we’re all just trying to do our best.

Hopefully this article can give folks a solid starting point to assess themselves and their organizations.

Thank you for your time.