Balancing Readability, Testability, and Structure: Refactoring a small type with John Carmack’s Email in mind

mandag den 28. oktober 2024

This is an article about refactoring the characteristics and behaviors of a type, based on some interesting arguments written in an email by programmer John Carmack in 2007.

The email.

He introduces an interesting idea that makes me reflect on when and why it might be necessary to disregard conventional wisdom surrounding the downsizing and decomposition of methods/functions, often aimed at improving readability, code navigation, and mental cognition. While I definitely believe that smaller pieces of code can enhance readability, there is also a cost associated with it, particularly around maintaining the same navigational context and minimizing context switching.

It's a worthwhile question whether breaking down methods/functions into smaller ones is the right approach from the outset.

John's email from 2007, at least as I interpret it, suggests something contrary to what I have been taught over the years—that is, not to lump everything into one method or function. Larger methods, of course, can blur readability, become brittle in testing, and violate the Single Responsibility Principle (SRP). The exercise of "3 strikes, then add the first abstraction" comes to mind. I no longer apply this upfront because my sense of when to decompose a method is somewhat ingrained in how I approach programming in the first place. So, I could say that I decompose right away, but that wouldn't be entirely accurate because I frequently revisit and refactor, either following the Boy Scout Rule or based on my cognitive state at that particular time. I write a method, decompose it when it becomes too long, and continuously refine it without giving it much thought. I do, however, approach decomposition with more consideration when it involves a public API.

I mention "first-time abstraction" because I don't believe the initial abstraction attempt is always correct, even after reviewing something three times and determining it should be abstracted. I might need the abstraction, but does that mean it will be perfect the first time? In my experience, no.

This has become part of my own practice: applying a hypothesis around a potential abstraction but also keeping it as narrow as possible due to the likelihood of revisiting the same piece of code in the future. This isn't universally applicable—magic numbers and strings, for example, are clear candidates for abstraction early on.

Anyway, as I reflect on this while writing and reviewing some code, I see no reason to split up this function or module/class as a means of improving readability. Readability is a crucial aspect of programming, but I also worry about applying too much abstraction since it can extend beyond readability concerns. And honestly, I'm not sure I entirely believe that.

When I navigate through code—going to references, implementations, scrolling up and down—I often lose context. But maybe if the decomposition isn't scattered across different types and files, it could be effective. This is how I've programmed for years.

It has been a long time since I've used a different approach in any object-oriented programming language, though earlier I wrote a lot of interpreted code. Robert C. Martin's advice, “Gather together the things that change for the same reasons,” still resonates. It's solid guidance.

John Carmack's perspective adds another layer, one that I believe significantly impacts a programmer's cognitive load when navigating and reading source code: “Step into every function to try and walk through the complete code coverage.” Next time you're working in a codebase, try following all the paths your code takes during execution and debugging.

We can debate readability and composition all year. I'm not here to impose any dogma or dictate the best approach—you can decide that for yourself. I'm simply experimenting with styles. Some, as John suggests, might be less prone to introducing defects.

In his email, John outlines three types of compositions for a function, or a module if you prefer to extend the concept.

------- style A:
 
void MinorFunction1( void ) {
}
 
void MinorFunction2( void ) {
}
 
void MinorFunction3( void ) {
}
 
void MajorFunction( void ) {
        MinorFunction1();
        MinorFunction2();
        MinorFunction3();
}
 
--------- style B:
 
void MajorFunction( void ) {
        MinorFunction1();
        MinorFunction2();
        MinorFunction3();
}
 
void MinorFunction1( void ) {
}
 
void MinorFunction2( void ) {
}
 
void MinorFunction3( void ) {
}
 
 
---------- style C:
 
void MajorFunction( void ) {
        // MinorFunction1
 
        // MinorFunction2
 
        // MinorFunction3 
}

He concludes with these thoughts:

“Inlining code quickly runs into conflict with modularity and object-oriented programming (OOP) protections, and good judgment must be applied. The whole point of modularity is to hide details, while I advocate for increased awareness of those details. Practical factors like increased multiple checkouts of source files and including more local data in the master precompiled header, forcing more full rebuilds, must also be weighed. Currently, I lean towards using heavyweight objects as the reasonable breakpoint for combining code and reducing the use of medium-sized helper objects while keeping any very lightweight objects purely functional if they must exist at all.”

The key points I take away are:

Finally, John gives this advice:

“If a function is only called from a single place, consider inlining it.”

I don't intend to diminish John's insights—he's a far more experienced programmer than I am—but I find his thoughts and arguments compelling enough to explore further. Since it's a style I haven't used in a while, I'm curious to give it a try.

The first thing that comes to mind when I read, “If a function is only called from a single place, consider inlining it,” is that every function starts by being called from just one place. If not, you might already be ahead of yourself.

I'll begin with an inlined version of an originally non-inlined method and present the full type. One could write a type like this with significant inlining involved.

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
	private readonly string[] ValidFileExtensions = [".md", ".markdown"];
	private readonly List<DownloadMarkdownExecption> downloadExceptions = [];
	private readonly List<MarkdownFile> markdownDownloads = [];
	private readonly DownloadMarkdownFileServiceResult downloadAsyncResult = new();

	private readonly HttpClient httpClient;

	public DownloadMarkdownFileService(HttpClient httpClient)
	{
		this.httpClient = httpClient;
	}

	public async Task<DownloadMarkdownFileServiceResult> DownloadAsync
		(IEnumerable<Uri> uris, CancellationToken cancellationToken = default)
	{
		foreach (var uri in uris)
		{
			if (uri == null) continue;

			var fileName = Path.GetFileName(uri.AbsoluteUri);
			var extension = fileName.Contains('.') ? Path.GetExtension(fileName) : string.Empty;

			if (!ValidFileExtensions.Contains(extension)) continue;

			var markdownFile = new MarkdownFile(uri);

			try
			{
				var result = await httpClient.GetAsync
					(markdownFile.Path, cancellationToken);

				if (!result.IsSuccessStatusCode)
				{
					throw new HttpRequestException
						($"Could not download file at {markdownFile.Path}", 
						null, 
						result.StatusCode);
				}

				markdownFile.Contents =
					await result.Content.ReadAsStringAsync();

				markdownDownloads.Add(markdownFile);
			}
			catch (HttpRequestException hre)
			{
				downloadExceptions.Add
					(new DownloadMarkdownExecption($"{hre.Message}", hre));
			}
			catch (Exception e)
			{
				downloadExceptions.Add
					(new DownloadMarkdownExecption($"{e.Message}", e));
			}
		}

		downloadAsyncResult.DownloadExceptions = downloadExceptions;
		downloadAsyncResult.MarkdownFiles = markdownDownloads;

		return downloadAsyncResult;
	}
}

Anyone can program in their own preferred style; I'm not here to critique but rather to experiment with different approaches and explore their potential.

When I look at this code, I feel a bit mixed. It accomplishes its purpose, and its structure and length are reasonable.

However, I find it difficult to fully accept this method because it goes against some principles I consider important, and I suspect it may pose challenges when testing. Although readability isn't particularly problematic here, I feel the method does more than is ideal for a single function to handle.

The inlined elements within this method could also be seen as problematic. For instance, the method performs multiple tasks, limits extension options, and might even conflict with the Dependency Inversion Principle, as it returns a concrete type rather than an interface.

Here's what the method currently does:

While I don't find the method's readability poor—it narrates a clear story, has some error-handling decisions, and a logical structure—testing it could be challenging. This is mainly due to the intertwined implementation details. For instance, the URI extension validation mechanism is tightly integrated within the method, making it less flexible and more difficult to modify or test independently. This isn't about rigid adherence to any single approach; rather, it's just an observation. Our goal here is to explore if and when inlining code in this way is effective for certain parts of our codebase.

In a more structured OOP environment, the URI extension might make an excellent candidate for a pure function. And this aligns with what I understand John is suggesting in his email, where he states: "If a function is only called from a single place, consider inlining it." He also notes, "If the work is close to purely functional...try to make it completely functional."

Since this function is called only once, inlining seems appropriate. So, let's look for other potential candidates where this might also apply.

One could write a pure function as shown below and encapsulate it in a lightweight type. While this approach might counter the purpose of inlining, it's worth noting. So far, I've identified one candidate for inlining, but there could be more.

public string UriPathExtension(Uri uri) =>
	uri is null ? string.Empty : Path.GetExtension(uri.AbsoluteUri);

The next point John makes in his list is: "If a function is called from multiple places, see if it is possible to arrange for the work to be done in a single place, perhaps with flags, and inline that."

This is an interesting suggestion. Suppose I have two types of tasks I need to carry out. I want to download markdown files, but I also need to download image files, like JPGs and PNGs. I might initially have two distinct services, each calling the pure function I outlined in UriPathExtension. John's advice here is to consolidate that work in a single place and then inline the function again.

Since my original method returns a DownloadMarkdownFileServiceResult, I would likely need to refactor it to a more general DownloadFileServiceResult. From there, the adjustments could start to cascade. With this type, I could handle both tasks while keeping potential extractions inlined. (Please note, I haven't fully implemented this code, so it's not build-ready due to the incomplete refactoring.)

In this experiment, I'm focusing on readability, testability, and the shifts in mindset required when programming in an OOP context.

public class DownloadMarkdownFileService : IDownloadFiles
{
	private readonly string[] ValidMarkdownFileExtensions = [".md", ".markdown"];
	private readonly string[] ValidPictureFileExtensions = [".jpg", ".png"];

	private readonly List<DownloadMarkdownExecption> downloadExceptions = [];
	private readonly List<DownloadableFile> downloadedFiles = [];
	private readonly DownloadMarkdownFileServiceResult downloadAsyncResult = new();

	private readonly HttpClient httpClient;

	public DownloadMarkdownFileService(HttpClient httpClient)
	{
		this.httpClient = httpClient;
	}

	public async Task<DownloadMarkdownFileServiceResult> DownloadAsync
		(IEnumerable<Uri> uris, CancellationToken cancellationToken = default)
	{
		foreach (var uri in uris)
		{
			if (uri == null) continue;

			var fileName = Path.GetFileName(uri.AbsoluteUri);
			var extension = fileName.Contains('.') ? Path.GetExtension(fileName) : string.Empty;

			if (!ValidMarkdownFileExtensions.Contains(extension)) continue;
			if (!ValidPictureFileExtensions.Contains(extension)) continue;

			try
			{
				var result = await httpClient.GetAsync
					(file.Path, cancellationToken);

				if (!result.IsSuccessStatusCode)
				{
					throw new HttpRequestException
						($"Could not download file at {file.Path}", 
						null, 
						result.StatusCode);
				}

				//Markdown
				if (ValidMarkdownFileExtensions.Contains(extension))
				{
					//markdown 
					file.Contents =
						await result.Content.ReadAsStringAsync();
				}

				//Pictures
				if (ValidPictureFileExtensions.Contains(extension))
				{
					//markdown 
					file.FileStream =
						await result.Content.ReadAsStreamAsync();
				}

				downloadedFiles.Add(file);
			}
			catch (HttpRequestException hre)
			{
				downloadExceptions.Add
					(new DownloadResultExecption($"{hre.Message}", hre));
			}
			catch (Exception e)
			{
				downloadExceptions.Add
					(new DownloadResultdownExecption($"{e.Message}", e));
			}
		}

		downloadAsyncResult.DownloadExceptions = downloadExceptions;
		downloadAsyncResult.DownloadableFiles = downloadedFiles;

		return downloadAsyncResult;
	}
}

How does it read? How does it test? I could reiterate what I mentioned with the first method described earlier: the more varied tasks I incorporate around the same domain concept, the more this method seems to expand.

I realize I'm bringing up testing considerations here, and perhaps I shouldn't, but each time I add more inlined code, I have an instinctive hesitation. This latest method won't necessarily become easier to test or to use. One small challenge among many is that now I need to assess the file type in the result as well. But having all the code in one place certainly has its benefits. The trade-offs, however, are evident.

"good judgment must be applied" - John Carmack

For readability, this setup isn't quite working for me. While I appreciate the reduced cognitive load from having all the code in one place, the trade-offs seem too significant. One might argue that this type is too small to be a meaningful experiment, which is fair — but is any type truly too small? Either way, the bottom line is that I don't find this approach appealing, so I'll go back, keeping in mind that "good judgment must be applied," and refactor the first method posted to explore a few alternative styles I might actually use.

My initial refactoring approach still leans towards the principles outlined in Carmack's Email which is perfectly fine. I'll decompose the type as I proceed.

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
    private readonly HttpClient httpClient;
    private readonly string[] validFileExtensions = { ".md", ".markdown" };

    public DownloadMarkdownFileService(HttpClient httpClient)
    {
        this.httpClient = httpClient;
    }

    public async Task<DownloadMarkdownFileServiceResult> DownloadAsync(IEnumerable<Uri> uris, CancellationToken cancellationToken = default)
    {
        var downloadExceptions = new List<DownloadMarkdownExecption>();
        var markdownFiles = new List<MarkdownFile>();

        foreach (var uri in uris)
        {
            if (uri == null) continue;

            var fileName = Path.GetFileName(uri.AbsoluteUri);
            var extension = fileName.Contains('.') ? Path.GetExtension(fileName) : string.Empty;

            if (!validFileExtensions.Contains(extension)) continue;

            try
            {
                var response = await httpClient.GetAsync(uri, cancellationToken);

                if (!response.IsSuccessStatusCode)
                {
                    throw new HttpRequestException($"Could not download file at {uri}", null, response.StatusCode);
                }

                var contents = await response.Content.ReadAsStringAsync();
                markdownFiles.Add(new MarkdownFile(uri) { Contents = contents });
            }
            catch (HttpRequestException hre)
            {
                downloadExceptions.Add(new DownloadMarkdownExecption(hre.Message, hre));
            }
            catch (Exception e)
            {
                downloadExceptions.Add(new DownloadMarkdownExecption(e.Message, e));
            }
        }

        return new DownloadMarkdownFileServiceResult
        {
            DownloadExceptions = downloadExceptions,
            MarkdownFiles = markdownFiles
        };
    }
}

The second approach is leaning a little more into something around SOLID, not much though, since I have only really extracted a new interface in IFileValidator.

public interface IFileValidator
{
    bool IsValid(string fileName);
}

public class FileValidator : IFileValidator
{
    private readonly string[] _validFileExtensions = { ".md", ".markdown" };

    public bool IsValid(string fileName)
    {
        var extension = Path.GetExtension(fileName);
        return !string.IsNullOrEmpty(extension) && _validFileExtensions.Contains(extension);
    }
}

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
    private readonly IFileValidator fileValidator;
    private readonly HttpClient httpClient;

	public DownloadMarkdownFileService(IFileValidator fileValidator, HttpClient httpClient)
	{
		this.httpClient = httpClient;
		this.fileValidator = fileValidator;
	}

    public async Task<DownloadMarkdownFileServiceResult> DownloadAsync(IEnumerable<Uri> uris, CancellationToken cancellationToken = default)
    {
        var downloadExceptions = new List<DownloadMarkdownException>();
        var markdownDownloads = new List<MarkdownFile>();

        foreach (var uri in uris)
        {
            if (uri == null) continue;

            var fileName = Path.GetFileName(uri.AbsoluteUri);
            if (!fileValidator.IsValid(fileName)) continue;

            var markdownFile = new MarkdownFile(uri);

            try
            {
                var result = await httpClient.GetAsync(markdownFile.Path, cancellationToken);

                if (!result.IsSuccessStatusCode)
                {
                    throw new HttpRequestException($"Could not download file at {markdownFile.Path}", null, result.StatusCode);
                }

                markdownFile.Contents = await result.Content.ReadAsStringAsync();
                markdownDownloads.Add(markdownFile);
            }
            catch (HttpRequestException hre)
            {
                downloadExceptions.Add(new DownloadMarkdownException(hre.Message, hre));
            }
            catch (Exception e)
            {
                downloadExceptions.Add(new DownloadMarkdownException(e.Message, e));
            }
        }

        return new DownloadMarkdownFileServiceResult
        {
            DownloadExceptions = downloadExceptions,
            MarkdownFiles = markdownDownloads
        };
    }
}

As I go along, please remember that I am still looking for readability and secondly, testability.

The next refactoring I present is towards even more SOLID, and even more decomposing. Does it read well ? Does it test well ?

public interface IFileValidator
{
	bool IsValid(string fileName);
}

public class FileValidator : IFileValidator
{
	private readonly string[] _validFileExtensions = { ".md", ".markdown" };

	public bool IsValid(string fileName)
	{
		var extension = Path.GetExtension(fileName);
		return !string.IsNullOrEmpty(extension) && _validFileExtensions.Contains(extension);
	}
}

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
	private readonly IFileValidator fileValidator;
	private readonly HttpClient httpClient;

	public DownloadMarkdownFileService(IFileValidator fileValidator, HttpClient httpClient)
	{
		this.httpClient = httpClient;
		this.fileValidator = fileValidator;
	}

	public async Task<DownloadMarkdownFileServiceResult> DownloadAsync(
		IEnumerable<Uri> uris, 
		CancellationToken cancellationToken = default)
	{
		var downloadExceptions = new List<DownloadMarkdownException>();
		var markdownFiles = new List<MarkdownFile>();

		foreach (var uri in uris)
		{
			if (uri == null) continue;

			var (success, markdownFile, exception) = await TryDownloadFileAsync(uri, cancellationToken);

			if (success && markdownFile != null)
			{
				markdownFiles.Add(markdownFile);
			}
			
			if (exception != null)
			{
				downloadExceptions.Add(exception);
			}
		}

		return CreateResult(markdownFiles, downloadExceptions);
	}

	private async Task<(bool Success, MarkdownFile? MarkdownFile, DownloadMarkdownException? Exception)> 
		TryDownloadFileAsync(Uri uri, CancellationToken cancellationToken)
	{
		if (!IsValidFile(uri))
		{
			return (false, null, null);
		}

		var markdownFile = new MarkdownFile(uri);

		try
		{
			var content = await DownloadFileContentAsync(markdownFile, cancellationToken);
			markdownFile.Contents = content;
			return (true, markdownFile, null);
		}
		catch (HttpRequestException hre)
		{
			return (false, null, new DownloadMarkdownException(hre.Message, hre));
		}
		catch (Exception e)
		{
			return (false, null, new DownloadMarkdownException(e.Message, e));
		}
	}

	private bool IsValidFile(Uri uri)
	{
		var fileName = Path.GetFileName(uri.AbsoluteUri);
		return fileValidator.IsValid(fileName);
	}

	private async Task<string> DownloadFileContentAsync(
		MarkdownFile markdownFile, 
		CancellationToken cancellationToken)
	{
		var response = await httpClient.GetAsync(markdownFile.Path, cancellationToken);

		if (!response.IsSuccessStatusCode)
		{
			throw new HttpRequestException($"Could not download file at " +
				$"{markdownFile.Path}", null, response.StatusCode);
		}

		return await response.Content.ReadAsStringAsync();
	}

	private DownloadMarkdownFileServiceResult CreateResult(
		IEnumerable<MarkdownFile> markdownFiles, 
		IEnumerable<DownloadMarkdownException> exceptions)
	{
		return new DownloadMarkdownFileServiceResult
		{
			MarkdownFiles = markdownFiles.ToList(),
			DownloadExceptions = exceptions.ToList()
		};
	}
}

Now I'm approaching something that's highly decomposed compared to the first type I presented above. For me, it's not as readable, though that may be personal preference.

The key point here is that the benefits from this decomposition are less about readability and more about testability. How code reads is often more a matter of context. We could agree that, in isolation, each of these smaller methods is easier to read than the earlier types, but without the context around them, they only convey a single aspect of the process.

When methods do only one thing, they're either meant to be used by other types or are perhaps too small and should be consolidated into the types where they naturally fit. I believe that's in line with what Carmack mentioned. So, in a way, we're back to square one: writing code that balances readability, testability, and structure is challenging.

I could continue with a few more examples of what this type might look like. One example, and a language feature I rarely see used, is the use of local functions. I find them particularly appealing when working with functions needed only within a single type. This will be the last refactoring I present. It's been enjoyable to explore and demonstrate John Carmack's ideas, and exercises like this are always insightful.

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
	private readonly string[] validFileExtensions = { ".md", ".markdown" };
	private readonly List<DownloadMarkdownExecption> downloadExceptions = new();
	private readonly List<MarkdownFile> markdownDownloads = new();
	private readonly DownloadMarkdownFileServiceResult downloadAsyncResult = new();

	private readonly HttpClient httpClient;

	public DownloadMarkdownFileService(HttpClient httpClient)
	{
		this.httpClient = httpClient;
	}

	public async Task<DownloadMarkdownFileServiceResult> DownloadAsync(
		IEnumerable<Uri> uris, CancellationToken cancellationToken = default)
	{
		foreach (var uri in uris)
		{
			if (uri == null) continue;

			var fileName = Path.GetFileName(uri.AbsoluteUri);
			var extension = GetFileExtension(fileName);

			if (!IsValidExtension(extension)) continue;

			var markdownFile = new MarkdownFile(uri);

			try
			{
				await DownloadFileAsync(markdownFile, cancellationToken);
				markdownDownloads.Add(markdownFile);
			}
			catch (HttpRequestException hre)
			{
				downloadExceptions.Add(new DownloadMarkdownExecption($"{hre.Message}", hre));
			}
			catch (Exception e)
			{
				downloadExceptions.Add(new DownloadMarkdownExecption($"{e.Message}", e));
			}
		}

		return BuildDownloadResult();

		string GetFileExtension(string fileName) =>
			fileName.Contains('.') ? Path.GetExtension(fileName) : string.Empty;

		bool IsValidExtension(string extension) =>
			validFileExtensions.Contains(extension);

		async Task DownloadFileAsync(MarkdownFile markdownFile, CancellationToken cancellationToken)
		{
			var response = await httpClient.GetAsync(markdownFile.Path, cancellationToken);

			if (!response.IsSuccessStatusCode)
			{
				throw new HttpRequestException(
					$"Could not download file at {markdownFile.Path}", null, response.StatusCode);
			}

			markdownFile.Contents = await response.Content.ReadAsStringAsync();
		}

		DownloadMarkdownFileServiceResult BuildDownloadResult()
		{
			downloadAsyncResult.DownloadExceptions = downloadExceptions;
			downloadAsyncResult.MarkdownFiles = markdownDownloads;
			return downloadAsyncResult;
		}
	}
}

Refactoring the Mental Bin: An Extension in the way

mandag den 7. oktober 2024

This is an article that is a little bit obnoxius really. I draw up some opionions here that I don't initially, when writing code, always comply with. But I would like to comply with at all times. But I guess that's another story.

I was listening to Jazzmatazz Vol. 1 and reading some really simple code.

I remembered a talk by a former professional friend who had made a statement about arrays and performance. Another professional friend had once said, "stupid code is fast code." I was left pondering these two statements while reading the code.

Code readability is subjective. How someone else perceives code is different from how I do, and therefore, it's of course very important that, when working on a team, such things are handled by using some kind of tooling.

You should, of course, not be "allowed" to use one style of code while your colleague uses a different one; that will most likely lead to confusion and frustration. Program correctness, on the other hand, is something you can objectively measure — "if your specifications are contradictory, life is very easy, for then you know that no program will satisfy them, so, make "no program"; if your specifications are ambiguous, the greater the ambiguity, the easier the specifications are to satisfy (if the specifications are absolutely ambiguous, every program will satisfy them!).".

Having consistent, readable code alone should lower the cognitive load while reading that code. It's about context switching, they say. We all know how it feels when we enter a module with neatly organized methods, naming conventions, sizing, and documentation—and then switch to a different module that doesn’t fit into the mental model you were just in. You then need to switch gears and figure out what's going on.

Think about this. Imagine having three programmers. One writes abstract classes more often than the second programmer, who writes more interfaces. And the last programmer writes and uses concrete types. Will this be, or is it even, a readability issue?

How programmers use a language will most likely evolve over time. It will most likely evolve as they learn more things. So a codebase will likely also change over time due to that evolution. How should that be controlled?

Reading code is more difficult than writing it. That’s the same reason programmers should be very much aware of how they present their code to others in written form. If you're working on a team, at least have tooling set up around structural semantics. Personally, I like code that reads into the lowest common denominator; call it naive, stupid, or the opposite of clever. I really don't care about how clever you are, I also need to understand it.

Reading code should be like drinking a good glass of wine while eating a good pasta dish and listening to some jazz tunes — something a little less hip-hop-ish than Guru’s Jazzmatazz. It should be comfortable and make you feel safe and welcomed.

So, I was reading some code, and this might seem like a bland example, but it should be easy for someone to read and understand.

Return this result:

Go ahead and write a program that does that.

Such a type or method could easily be a utility type/method. Some might even call it a helper. An extension is another name for a higher communicated candidate. There is nothing wrong with any of them, but personally I sometimes forget to think whether such a type is too easy to implement in terms of missing out on responsibility and better encapsulation.

So I can have a difficult time with these sort of types since they tend to grow in the number of files, the number of methods, and the number of things that are just considered an extension, helper or utility.

I often fall into my own traps. This code is part of my site generator Rubin.Static, and I have done exactly what I just said I didn’t like to do. I have more extensions in there than I like.

But I can also explain why, since I am quite aware of how my mental juggling works with this. An Extension/Utility/Helper directory, or even (worse) a project of such kind, is such a great mental bin to offload into whenever something does not fit right into the directory you're standing in.

And it underlines and shows to me how I go about programming. It is in iterations, and sometimes I'm simply not good enough to capture or being aware of everything. Then, luckily, I can get back and iterate again.

At the time of writing, I have five files in the Extensions directory. It’s the directory in that small project that holds the most files. It sort of left me with a "there is something off" feeling, but it also tells the story of not believing in my own standards for everything I do or don’t do. Heck, I could have left it alone and just pumped more extensions in there over time. But no.

I can’t remember why I wrote the initial method like I did, but as I just stated, "Extensions/Helper/Utilities" is such a great bin to put things into, right?

I have experienced this many times in my career, in many codebases, and I have come to believe that it can stem from not fully collecting or gathering the code where it belongs. The responsibilty and encapsulation of these types should be thought of, I think.

Take these methods as they are, which is part of the namespace Rubin.Markdown.Extensions.

public static class UriExtensions
{
    public static IEnumerable<Uri> ByValidFileExtensions(this IEnumerable<Uri> uris, string[] validExtensions)
    {
        foreach (var uri in uris)
        {
            for (var i = 0; i < validExtensions.Length; i++)
            {
                if (validExtensions[i] == uri.GetFileExtension())
                {
                    yield return uri;
                    break;
                }
            }
        }
    }

    public static string GetFileExtension(this Uri uri)
    {
        if (uri == null)
        {
            return string.Empty;
        }
        
        string path = uri.AbsoluteUri;
        string fileName = Path.GetFileName(path);
        
        if (fileName.Contains('.'))
        {
            return Path.GetExtension(fileName);
        }
        
        return string.Empty;
    }
}

It works, and there’s nothing particularly wrong with it. We can always argue about the nested loops, but for such a short method, it’s not really an issue. The GetFileExtension method can also be narrowed down somewhat, sure.

[Fact]
public void When_Uris_Should_Be_Markdown_Return_Only_Markdown_Uris()
{
    var uris = new List<Uri>
    {
        new Uri("https://some.dk/domain/file.md"),
        new Uri("https://some.dk/domain/file.markdown"),
        new Uri("https://some.dk/domain/file1.markdown"),
        new Uri("https://some.dk/domain/file"),
        new Uri("https://some.dk/domain/file.jpg")
    };
    
    var validUris = uris.ByValidFileExtensions(ValidMarkdownFileExtensions.ValidFileExtensions);
    
    Assert.True(validUris.Count() == 3);
}

Just as a testament, the test asserts true.

Let me restate the opening, rather loose, program specification again:

In the original implementation, I used an extension method, which is arguably a fine way to extend functionality to a type. I am not sure I fully agree. The particular extension methods here add functionality to .NET’s Uri type along with IEnumerable<Uri>, and I guess that’s a working approach. But that wasn’t my concern.

My main concern is that when I program these extensions (utility or helpers) without having given any explicit thought about whether those are the right fit or if the actual belonging is correct. This relates to what I wrote earlier about using extensions as a mental bin, an offload of functionality that might actually be more closely related to something else. So I need to ask myself why I made extensions rather than something else that might be more closely connected to the code that actually uses those extensions.

Now, if I were to refactor this and decrease the number of extensions in the directory I just mentioned, how could I do that?

I will start by looking at where this extension code belongs. As an experiment, I will conclude for now that the particular extensions do not belong as an extension, helper, or utility, but something else.

I'm backtracking the references from the extension file in Visual Studio, and I see that I have a reference inside the file DownloadMarkdownFileService.

foreach (var uri in uris.UrisWithValidFileExtensions(ValidMarkdownFileExtensions.ValidFileExtensions))

DownloadMarkdownFileService contains business rules; its purpose is to only download markdown files and convert their contents into a known type called MarkdownFile. So DownloadMarkdownFileService is really a fine candidate for the extension rather than my original approach.

The first thing to note is that DownloadMarkdownFileService is at the lowest level of abstraction. It's deepest in any call chain I have written myself; there are no calls to other types I have programmed myself. So I can also say that it’s a lower type, a fundamental type. I could also argue that having extensions so low down the chain can be bad since any user of the code could simply alter the extension, e.g., changing the valid file extensions, and then everything else would fail. Not good.

A second thing to consider is that someone else could later alter the extension method, perhaps causing a breaking change at runtime, which could also affect the DownloadMarkdownFileService.

I understand that one could mitigate these issues with tests, and one should. But it doesn’t solve the issue around responsibility, I think. The code not only belongs in a closer relationship with the DownloadMarkdownFileService, but it also makes that type "stronger" and more solid.

That has resulted in adding some code to the DownloadMarkdownFileService and its test pendant, but also deleting three files: two files in the extensions folder and one file in the test project.

The previous foreach loop, which looked like this:

foreach (var uri in uris.UrisWithValidFileExtensions(ValidMarkdownFileExtensions.ValidFileExtensions))

I changed to look like this:

foreach (var markdownFile in ValidMarkdownUris(uris))

Instead of working on the basis of Uri, I made a few changes around the DownloadMarkdownFileService type, such as adding a new Path property to the MarkdownFile type.

Instead of working more than absolutely needed on a Uri, I now work on the MarkdownFile type. Perhaps this is even more positive encapsulation.

This is what the DownloadMarkdownFileService type looked like before I refactored it toward better encapsulation and responsibiliy. I have left out unimportant code for now.

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
    ...
    ...

    public async Task<List<MardownFile>> DownloadAsync(IEnumerable<Uri> uris)
    {
        var markdownDownloads = new List<MardownFile>();

        foreach (var uri in uris.ByValidFileExtensions(ValidMarkdownFileExtensions.ValidFileExtensions))
        {
            ...
        }

        return markdownDownloads;
    }

    private async Task<MardownFile> DownloadAsync(Uri uri)
    {
        var result = await httpClient.GetAsync(uri);

        ...

        MardownFile

 markdownFile = new();
        markdownFile.Contents = await result.Content.ReadAsStringAsync();

        return markdownFile;
    }
}

Now it looks like this:

public class DownloadMarkdownFileService : IDownloadMarkdownFile
{
    private readonly string[] ValidFileExtensions = { ".md", ".markdown" };

    ...
    ...

    public async Task<List<MarkdownFile>> DownloadAsync(IEnumerable<Uri> uris)
    {
        var markdownDownloads = new List<MarkdownFile>();

        foreach (var markdownFile in ValidMarkdownUris(uris))
        {
            ...
        }

        return markdownDownloads;
    }

    private async Task<MarkdownFile> DownloadAsync(MarkdownFile markdownFile)
    {
        var result = await httpClient.GetAsync(markdownFile.Path);
        
        ...

        markdownFile.Contents = await result.Content.ReadAsStringAsync();

        return markdownFile;
    }

    private IEnumerable<MarkdownFile> ValidMarkdownUris(IEnumerable<Uri> uris)
    {
        foreach (var uri in uris)
        {
            if (ValidFileExtensions.Contains(UriPathExtension(uri)))
            {
                yield return new MarkdownFile(uri);
            }
        }
    }

    private string UriPathExtension(Uri uri)
    {
        if (uri == null) return string.Empty;

        var fileName = Path.GetFileName(uri.AbsoluteUri);

        if (fileName.Contains('.'))
        {
            return Path.GetExtension(fileName);
        }

        return string.Empty;
    }
}

I am happy with the result. I didn’t sacrifice much but I like the approach better than the original. The point is not the code per se, but that I should always apply thought to what is an extensible type (or helper and utilities) and what is supposed to be closer to the actual type I am working on. In this cas it was the Uri but made better sense to also adjust the surrounding types.

You can find the whole commit and changes here.

Write. Push. Publish. Separating the concerns.

tirsdag den 17. september 2024

For the local-first, feature-less, and admittedly boring static site generator that runs this blog, I have had a few thoughts around a different model for materializing response output. You can always read about the initial design thoughts for Rubin.Static, I still do sometimes.

Today, when I write an article or post, I type the text in my favorite text editor as Markdown. When I’m finished writing, I push that Markdown file to a repository on GitHub.

Now, I have a file persisted in what I call my content repository. You could also call it my write store.

That write-push workflow is completely independent from publishing and updating the actual site, and that was an initial design decision. I wanted to keep writing content and pushing it to whatever write store I chose, independent of whoever or whatever wanted to utilize that content later on.

Write. Push. Publish?

This article you are reading is not being materialized from data upon your request. It was put together before the request, hence the "static" part. It is a file on disk — a static HTML file.

When I want to update this site, I run a program locally on my machine called Rubin.Static. I execute a console program by running .\run.ps1, and from there I wait until the program completes its task.

This is where my fraudulent programming mind starts playing tricks on me. I start thinking about parallelism for HTTP requests, wasted clock cycles when generating files whose content hasn’t even been touched and why even download files that haven’t changed ? And so on. Overengineering is the root of...and all that jazz. But I fallen for the traps before so these days I do not have to let the "creative department on the top floor" take over completely.

This approach around "write -> push" leaves the actual site eventually consistent. Even though I may have content in the write store, which is set as published, the site will not reflect that until the static files are generated and the site is updated. We could choose to call this a manual event, but it was no accident, I designed it this way on purpose.

How is a post or article generated?

For every Markdown file downloaded, Rubin.Static parses it into a strongly typed model and generates a static HTML page from that model.

It does this via the Razor templating engine, with some Razor views and a Layout view. But it’s all within a console application, without a web server being fired up. There are some bounded dependencies.

At the end of an execution, I can navigate to Rubin.Static's output directory and find the site ready to run in a browser. It’s just HTML, CSS, and a little external JavaScript for code highlighting.

Where data is written to has nothing to should not matter. Hence the "reading" of data is almost entirely ignorant of where it was written to. That results in not using the same store for writes and reads. Write store is a github repository. Read store is a directory of web associated files.

This is an example of separation of concerns. I like this approach, and every time I use it, I smile. The whole notion of writing anything should be totally separated from any other concerns. And it is.

Today, when I execute Rubin.Static and add a new Markdown file (post/article), the Index page must be updated to reflect that. The Index page lists the contents of N new posts/articles.

There are also category pages generated if a post or article has a category "attached" to it.

So, with the Index page and Category pages, multiple static HTML pages are generated whenever a new post or article is committed to the repository (or removed, renamed, updated, etc.). However, today Rubin.Static cannot generate Category or Index pages without scanning every single Markdown file.

If I were to take this to an extreme and let my "creative department" go wild, I would experiment with event-driven file generation.

If I were to event-drive this, it would require a completely different page generation mechanism. I would most likely need to persist some interim data between receiving an event (such as a new Markdown file or a deleted one) and generating the static pages.

How do you materialize views from data?

To make it crystal clear, the following Rubin.Static-supported Markdown file would generate a static HTML file called this-is-the-slug-for-some-post.html and also contribute to generating software.html, code.html, and index.html:

[//]: # "title: Some post"
[//]: # "slug: this-is-the-slug-for-some-post"
[//]: # "pubDate: 14/6/2024 12:01"
[//]: # "lastModified: 17/6/2024 10:20"
[//]: # "excerpt: Whatever you want!"
[//]: # "categories: software, code"
[//]: # "isPublished: true" \

Content goes here!

I would bet the most common way online applications materialize their views is based on collecting data "just in time." With the data at hand, we can then materialize and render it for the user.

I have no issues with this approach. At all. The power of querying a relational datastore is incredibly useful. But since I’m already heading down the event-driven path in my mind, I imagine a different approach. This wouldn’t necessarily be the preferred option, but event-driven design could allow my read model to be eventually consistent based on events already received.

In theory, this sounds good, but in practice, I find that designs and architectures around eventual consistency often being evanglized into a too too simple yet too broad approach. But who am I to judge without any context.

How might events be applied in Rubin.Static?

Now, the tricky part—because we don’t have all the data like we used to.

The same process would apply for deleting or updating a Markdown file. Broad strokes, okay.

And suddenly, I’ve come up with an event-based update mechanism for the read model. It’s completely over-engineered and far too complex for where these designs apply correctly. But that's just me. I might try it as an experiment, but it will not end up in the main branch — it’s just too much.

With Rubin.Static, there is no relational data. I initially decided to forego that complexity, opting for Markdown as a low-common-denominator format. I wanted to write software without the need for a database.

So, there are only Markdown files to parse, and my own format parser to apply during the process. It’s all rather sequential. This has resulted in parsing and generating HTML pages, but I’ve already explained that part.

When Technology Overshadows the Social in Software Development

mandag den 9. september 2024

A piece of thought with little to back it up.

In the world around the individualism of software enginnering and programming one sometimes need what cyclists calls "an exercise adjustment". It often results in ones own arrogance being taken down a notch.

Technology often takes center stage. Socalled new frameworks, never-ending disussions around paradigms, and tools that promise to optimize, streamline, and solve complex problems. I get a bit disappointed in the field at times, hoping for higher standards, and I would also be happy for a bit more pressure on the social well being in a professional setting. I am not talking about perks or office hours, I am talking power and social dynamics.

Lately I have watched four real human beings, working together for weeks, to develop an algorithm. Sitting in the same room. Churning. Talking. Discussing. Sharing knowledge. Using social skills. Increasing cognitive safety for domain understanding. In my book, that is team work. Funny enough, others around this group has expressed their interest, wanting in the future to be part of such a tightly knit setting.

In our pursuit of technical solutions, we often overlook the social aspects that are crucial to building successful teams and organizations. Why do you think this happens ? And what are the consequences for the humans alongside you ?

As a programmer, I frequently find myself wondering why the social aspects of our field are so hard to come by — even though practiced they are seldom practiced for lengths at a time, and in my experience, they are often replaced by an individualistic approach to power and decision-making. I've seen plenty of times, teams operate on unvalidated information, following a single person's "good idea", often driven by some sort of "HIPO", seniority or status. This dynamic is compounded by the way many companies organize themselves, creating an environment that does not support healthy social activities for teamwork, collaboration, and feedback.

The Allure of Technology

It's common for both programmers and managers to attempt to solve organizational issues by implementing new technologies. Look at how loose the saying from Conway has been become, like it's a technological issue to fix how communication flows through an organisation.

There might be tendency to believe that technology can drive and can resolve deeper, more fundamental collaboration problems. But this reinforces a theory I’ve long held: we misunderstand the role that technology plays within our organizations.

A well-intentioned but purely technological approach can easily overlook the social structures needed to foster healthy teams. We become trapped in a mindset that assumes technological design will naturally create the right conditions for better collaboration and outcomes. This is a short-sighted solution that focuses only on the tools and not on how people actually work together.

Who Holds the Power?

Power dynamics in an organization play a crucial role in how decisions are made and which solutions are chosen. I recently encountered a manager in a ten-person team who believed that there was no time for code reviews. This might seem as both an easy fix and a shit for brains stance, but in real life you encounter organisations and people that hold power they will not democratize. Being afraid of loosing that power grip is a real thing in some humans.

This is also a good example of how one person’s decision can shape an entire team's working processes. Code reviews are not just a technical step toward better code quality; they are also an opportunity for learning, feedback, and collaboration. When social mechanisms like these are removed from the process, you lose the relational dynamics that can strengthen a team.

If we up the ante and instead add a deeper rooted decision, that could have a more profound effect on a team, then we simply complicate matters even further.

I have no negative opinions towards e.g. DDD or Event-sourcing, but imagine the power dynamics of making such a choice without understanding the underlying organisational conflicts that coulda also add. The higher the complexity the more social stability within your organisation is probably needed.

This is where we often see a conflict between technology and social structures. Many of us in the tech world are influenced by a bias that leads us to believe technical solutions are always the answer. Jeff Hodges’ article, Notes on Distributed Systems for Young Bloods, encapsulates this well: “Our background, education, and experience bias us towards a technical solution even when a social solution would be more efficient, and more pleasing. Let’s try to correct for that.”

Technology and Social Dynamics: Two Sides of the Same Coin

I believe the biggest challenge in modern software development is not about choosing technologies or paradigms. It lies in creating the right conditions for teams to thrive both socially and technologically. That's different from the technological direction. We can’t ignore the social dynamics that arise within teams, organizations, and leadership. Technology is not a replacement for relationships, communication, and trust. And it shouldn't be neither the bearer of it nor a parameter for successful team work.

When organizations attempt to improve their outcomes by implementing new technologies without considering how those technologies will be socially integrated, they risk creating more chaos than clarity. The social architecture of an organization is just as important as its technical architecture. Ignoring this leads us to listen to those who talk the loudest and the most, rather than establishing best insights through information, measurements and team work.

Personally I would much rather be part of a reflective and social organization than a technology-driven one. This is where I have experienced teams build the most sustainable, resilient and quality work and at same time been the best place to be as a human.

Three Page Path Challenge - fifth iteration

mandag den 2. september 2024

This is the sixth article in a series about a man with a three-page path challenge, an interview question that can come up for programmers.

Make sure to read the problem scope in the first article in this series.

Also, read about the first iteration, the second iteration, the third iteration, and the fourth iteration.

I had to question myself around the matter of explicitness and defensiveness in the code I had written. Arguments should be clear, but I had found some of what I had written to be too implicit. This is in relation to correctness but also somewhat about the future and how we can prepare for it. I used to say I am not concerned with the future when writing code because it has an impossibility that is self-explanatory. Live requirements are most often a sign to be read as "stop."

If we guess about exact needs, the correctness could turn into incorrectness. It's a guess. I still fall into the trap, guessing my own ability, sometimes taking it for something higher than it really is. That will be a strain on any human mind—guessing, hoping to be right, but not with a high possibility of certainty.

Anyways, to boil it all the way down, it should be as obvious as possible to a programmer how an API works when one uses it. So when you allow your fellow programmer to pass in a type as an argument which is not explicitly telling, you are not making it obvious. And you might be guessing, even though it might be unconscious.

Here, I am training my abilities

For a constructor to accept an IEnumerable<T> but then change that type inside the constructor, e.g., to an IImmutableList<T>, closes off the possible updating of an exact type. It will hide the fact—e.g., if the exact type of the IEnumerable<T> is a List<T>—that one could manipulate that collection after initializing. That would not be possible in the same capacity with an IImmutableList<T>.

Think about it for a bit. Should my LogEntry collection be left open for manipulation later in the execution chain? Why not? Why yes? Am I the one to determine that? Is it a business rule? Do I know the future? Which type is more open than the other? Will your code be easier to close or to open?

If I did this public PathPatternsAnalyzer(IEnumerable<LogEntry> logEntries, int partitionSize) and wrote a test like this, it would fail.

[Fact]
public void Constructor_Parameter_Can_Update_During_Execution()
{
    //Arrange
    var listOfLogEntries = Log_Entries_No_Common_Paths().ToList();
    var count = listOfLogEntries.Count;
    var sut = new PathPatternsAnalyzer(listOfLogEntries, 3);

    //Act
    // will add to the collection and affect the sut
    listOfLogEntries.Add(new LogEntry(1, "path", 100));
    
    //Assert
    Assert.True(count == sut.logEntries.Count());
}

Yet, changing the constructor argument to an IImmutableList<T> closes off that possibility to change the collection during execution. What is expected, and how do I decide?

public PathPatternsAnalyzer(IImmutableList<LogEntry> logEntries, int partitionSize)

While this test would then succeed:

[Fact]
public void Constructor_Parameter_Cannot_Update_During_Execution()
{
    //Arrange
    var listOfLogEntries = Log_Entries_No_Common_Paths().ToList();
    var count = listOfLogEntries.Count;
    var sut = new PathPatternsAnalyzer(listOfLogEntries.ToImmutableList(), 3);
    
    //Act
    // collection in sut will not be affected
    listOfLogEntries.Add(new LogEntry(1, "path", 100));
    
    //Assert
    Assert.True(count == sut.logEntries.Count());
}

I know it sounds trite, and you might read this and think, "why is this idiot not just using whatever type? Why all this?" That's a valid point, but you might be forgetting that this is a challenge in programming, and asking yourself these questions is exactly how you become a better programmer. The reflections made can be useful. The exploration of types, patterns, and options.

I want to be explicit now, and therefore I will accept only IImmutableList<T> because it first and foremost signals to the programmer what to expect: that this constructor argument is immutable. I also believe that it's easier to understand since it is more predictable.

Bear in mind that it was never the goal that I wanted to create something immutable. It happened during the challenge, and it happened because I could take liberty to try it out while also finding it more correct at that moment.

You can find the code for this fifth iteration here, and I have made a small Runner program where you can follow the execution chain from.

Three Page Path Challenge - fourth iteration

mandag den 26. august 2024

This is the fifth article in a series about a man with a three-page path challenge, an interview question that can come up for programmers.

Make sure to read the problem scope in the first article in this series.

Also, read about the first iteration, the second iteration, and the third iteration.

There is always more, right? The balance between solving something at a satisfactory level and wanting to twist and turn something for answers that you started to ask yourself questions to. Programmers are usually creative beings, often questioning in silence and navigating mazes that can change patterns as they go. One needs to exercise one's mind, not questioning everything to a level of obscurity. Just as often, programmers are filled with honor by their craft, which in turn comes from their mind and hopefully thousands of hours of training. Question it, and you question their intelligence. Question a human's intelligence, and chances are that the human will react. Unless that human being is cool, calm, and knows everything is going to be okay.

We do it again and again, with a hopefulness of getting into that state of complete joy of floating. What a feeling. Crystal clear right there and then.

In this fifth article, I have turned my mind into asking it questions around defensiveness, immutability, and perhaps a little performance.

Visual Studio has a profiler I like. It's easy to use. For example, it lets you look at percentages of where CPU is used in your program, and it gave me some insights. But before I went there, I had some thoughts about how I could "tighten" the types of my program. Defensive code has grown a bit on me, and that has led me to pursue immutability and sealed types.

Both Eric Lippert and Jon Skeet have great comments about sealed types, and I have come to a conclusion for part of this iteration, at least, that sealed types should be the default. It resonates with me that opening something is easier than closing something that was open from the get-go. And in programming, this should really resonate with you quite easily.

So I sealed almost everything off. No problem, no tests failed, nothing couldn't compile. Pure win. The next thing I wanted to try was to turn some of my types into immutables since it makes sense that data cannot be edited during execution. Reading logs is a read-only mechanism, and it shouldn't be possible to add or change data during those measurements. That's one thing, even though I probably cannot guarantee anything. The other thing is that it's more defensive and leaves fewer surprises.

With an IEnumerable<T> you can edit it during execution. I wanted to seal that option off because of obvious reasons when talking immutability, so I settled with IImmutableList<T> instead. You can edit that type as well, but it will return a copy/new instance if you do.

Looking at the code for this iteration, it is obvious to me that I have not followed this all the way through since there are IEnumerables still in the code. I have let myself side-track because of the interest in what possible performance—if any at all—this has left on the solution. The code I have been timing and benchmarking has turned out to be faster in iteration three. So that was a side-track that didn't do me any good in that capacity, and I even looked into the profiler for things that took up most time.

But did it leave the code in a more readable state then? I fell into a different trap. I didn't do one thing at a time. Don't optimize code for the sake of refactoring. And don't refactor solely for optimization unless you are absolutely clear about why. Measure, measure, measure. Even though I fell right into it—the joy of floating, right?—I would be very wary of doing optimizations on code without being absolutely specific, and as it often turns out, side effects of performance optimization can creep into the surrounding types of your software. I think I have done that in this iteration. I wanted to be too clever perhaps, and now I will have to go back and clean up with only one thing in mind.

So the code is left in a state now where it is not as readable, I think, as in iteration three. I will have to address that. I am back at it. You can follow the path from this unfinished test and go about it as you wish.

Three Page Path Challenge - third iteration

tirsdag den 20. august 2024

This is the fourth article in a series about a man with a three-page path challenge, an interview question that can come up for programmers.

Make sure to read the problem scope in the first article in this series.

Also read about the first iteration and the second iteration.

In this article, I believe I have refined myself into a solution I am satisfied with, and I have shown to myself how I have gone back and forth in my iterations for refining my mind and solution for how I can answer all the challenge questions. Can I consider the code finished? No! I believe this code can be optimized and nurtured even further, but the point has also been to positively iterate into a more quality solution, centered around code readability, maintainability, tests, and composition.

Before writing this article I came to think about a few different quotes on data and code.

Linus Torvalds once said "Bad programmers worry about the code. Good programmers worry about data structures and their relationships."

Fred Brooks says something a little less provocative in his Mythical Man-Month:

Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious.

What I am getting at is an internal thought about if I could have either made a data structure from my initial data (LogEntry) or used different data structures for solving this challenge.

I have to pretend that it is needed, the optimization, otherwise it would be an optimization I hardly could justify. But when I run this third iteration on a million log entries and ask for the answer for the first question "What is the most common three-page pattern for all users?" it takes 13 seconds.

Jon Skeet said something along the lines, in his C# in Depth, "often performance optimizations hurt code readability." In the case of this iteration, a call to All on an IEnumerable takes around 10 seconds, and I could have left it out, but didn't.

That challenge, specifically, is "how do you determine if a property on an entry in a collection has the same value as all other entries in the same collection." There is a logical answer to this, but it exists only because I already have an ordered collection. I can take the first and the last entry, check the value on both. I have not changed the call to All, you can try to do that. And it won't really hurt readability.

In the end of the second iteration, I concluded I was going into a corner and the composition was getting skewed. For many years I have been very aware of when I can actually program and when I need to leave it alone. Some days I am simply too tired to do actual quality work and if I do, I know I have to come back and change it. So I have to step back, relax, read, and focus on something else. You can get invested in something where you try to outsmart yourself. I think some of that happened in the second iteration. In the first iteration, I had also just returned from a 7-week vacation where I had not touched a keyboard or a codebase. These things can play with you. Be aware of that context.

Another note is while the number of iterations go up so does the value of my output. I have used a lot less energy in this iteration and that might be because it has been close to the second iteration but just as much because I have made a note of what was to happen. I knew what was wrong. I could go back and change that. In the first iteration coming into the second iteration I still had to thing about a lot more.

In this iteration, I ended up with refactoring the type PathPatternsAnalyzer where one cannot cheat with the partitioning sizes, because the constructor parameter no longer is an IOrderedEnumerable<PathPattern>. Now the full type looks like this.

public class PathPatternsAnalyzer
{
    private readonly IEnumerable<LogEntry> logEntries;
    private readonly int partitionSize;

    private IOrderedEnumerable<PathPattern> orderedPathPatterns = Enumerable.Empty<PathPattern>().OrderBy(p => 0);
    private IEnumerable<UserPathPartition> userPathPartitions = new List<UserPathPartition>();

    public PathPatternsAnalyzer(IEnumerable<LogEntry> logEntries, int partitionSize)
    {
        this.partitionSize = partitionSize;
        this.logEntries = logEntries ?? [];

        if (this.partitionSize == 0)
        {
            throw new ArgumentException($"{partitionSize} cannot be zero");
        }

        if (partitionSize > this.logEntries.Count())
        {
            throw new ArgumentException($"{partitionSize} is larger than the total " +
                $"entries in {logEntries} - {this.logEntries.Count()}");
        }

        PartitionUserPaths();
        OrderPathPatterns();
    }

    public PathPattern MostCommonPathPattern()
    {
        // no common paths, extremely slow!
        if (orderedPathPatterns.All(p => p.OccurrenceCount == orderedPathPatterns.First().OccurrenceCount))
        {
            return new PathPattern(0, new List<UserPathPartition>());
        }

        return orderedPathPatterns.First();
    }

    public IOrderedEnumerable<PathPattern> AllPathPatterns()
    {
        return orderedPathPatterns;
    }

    public UserPathPartition? FastestCommonPathPattern()
    {
        var mostCommon = MostCommonPathPattern();

        var fastest = mostCommon.PathPatterns.OrderBy(s => s.TotalLoadTime);

        return fastest.FirstOrDefault();
    }

    public UserPathPartition SlowestPathPattern()
    {
        var slowest = orderedPathPatterns
            .SelectMany(p => p.PathPatterns)
            .OrderByDescending(o => o.TotalLoadTime)
            .First();

        return slowest;
    }

    private void PartitionUserPaths()
    {
        var pathPartitions = new UserPathPartitions(this.logEntries);
        userPathPartitions = pathPartitions.PartitionedByUserId(this.partitionSize);
    }

    private void OrderPathPatterns()
    {
        var pathPatterns = new PathPatterns(this.userPathPartitions);
        orderedPathPatterns = pathPatterns.OrderByOccurrenceDescending();
    }
}

See how this type is rather small. It has small methods, it uses the types I made earlier in a simple manner and it answers questions around the data in a few lines. I like it, except for the O(n) time complexity with All in MostCommonPathPattern.

The tests for this type are quite straightforward as well, due to the separated types which of course are tested separately.

Here are the tests for the PathPatternsAnalyzer which is also the answering sheet for the questions the challenge put forward.

public class PathPatternsAnalyzerTests
{

    [Fact]
    public void What_Is_The_Single_Most_Common_Page_Pattern()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_For_4_Users(), 3);

        //Act
        var actual = sut.MostCommonPathPattern();

        //Arrange
        Assert.True(actual.PathPatterns.All(a => a.FlattenedPaths == "/home/profile/results"));
    }

    [Fact]
    public void What_Is_The_Frequency_Of_The_Most_Common_Pattern_For_All_Users()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_For_4_Users(), 3);

        //Act
        var actual = sut.MostCommonPathPattern();

        //Arrange
        Assert.True(actual.OccurrenceCount == 2);
    }

    [Fact]
    public void How_Many_Different_Patterns_Exist()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_For_4_Users(), 3);

        //Act
        var actual = sut.AllPathPatterns();

        //Arrange
        Assert.True(actual.Count() == 8);
    }

    [Fact]
    public void Fastest_Most_Common_Path_Pattern()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_For_4_Users(), 3);

        //Act
        var actual = sut.FastestCommonPathPattern();

        //Arrange
        Assert.True(actual!.TotalLoadTime == 620);
    }

    [Fact]
    public void Slowest_Of_All_Path_Patterns()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_For_4_Users(), 3);

        //Act
        var actual = sut.SlowestPathPattern();

        //Arrange
        Assert.True(actual.TotalLoadTime == 900);
    }

    [Fact]
    public void Constructor_Throws_Due_To_Partition_Size_Is_Larger_Than_Collection_Count()
    {
        //Arrange Act Assert
        Assert.Throws<ArgumentException>(() => new PathPatternsAnalyzer(Empty_Log_Entries(), 3));
    }

    [Fact]
    public void Constructor_Throws_Due_To_Partition_Size_Is_0()
    {
        //Arrange Act Assert
        Assert.Throws<ArgumentException>(() => new PathPatternsAnalyzer(Log_Entries_For_4_Users(), 0));
    }

    [Fact]
    public void What_Is_The_Single_Most_Common_Page_Pattern_No_Common_Paths_Exist()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_No_Common_Paths(), 3);

        //Act
        var actual = sut.MostCommonPathPattern();

        //Arrange
        Assert.Equal(0, actual.OccurrenceCount);
        Assert.Empty(actual.PathPatterns);
    }

    [Fact]
    public void Fastest_Most_Common_Path_Pattern_No_Common_Paths_Exist()
    {
        //Arrange
        var sut = new PathPatternsAnalyzer(Log_Entries_No_Common_Paths(), 3);

        //Act
        var actual = sut.FastestCommonPathPattern();

        //Arrange
        Assert.Null(actual);
    }

    private IEnumerable<LogEntry> Log_Entries_No_Common_Paths()
    {
        var partitions = new List<LogEntry>
        {
            new LogEntry(1, "/login", 300),
            new LogEntry(1, "/home", 120),
            new LogEntry(1, "/profile", 200),
            new LogEntry(1, "/results", 300),
            new LogEntry(2, "/people", 300),
            new LogEntry(2, "/hello", 120),
            new LogEntry(2, "/contact", 200),
            new LogEntry(2, "/jobs", 300),
        };

        return partitions;
    }

    private IEnumerable<LogEntry> Log_Entries_For_4_Users()
    {
        var partitions = new List<LogEntry>
        {
            new LogEntry(1, "/login", 300),
            new LogEntry(1, "/home", 120),
            new LogEntry(1, "/profile", 200),
            new LogEntry(1, "/results", 300),
            new LogEntry(2, "/home", 300),
            new LogEntry(2, "/profile", 300),
            new LogEntry(2, "/results", 300),
            new LogEntry(3, "/home", 100),
            new LogEntry(3, "/login", 250),
            new LogEntry(3, "/dashboard", 250),
            new LogEntry(3, "/settings", 400),
            new LogEntry(4, "/login", 80),
            new LogEntry(4, "/home", 200),
            new LogEntry(4, "/dashboard", 200),
            new LogEntry(4, "/setting", 200),
            new LogEntry(4, "/search", 200),
            new LogEntry(4, "/people", 200)
        };

        return partitions;
    }

    private IEnumerable<LogEntry> Empty_Log_Entries()
    {
        var partitions = new List<LogEntry>();
        return partitions;
    }
}

I might return to this challenge in time, perhaps sooner than later, but for now I consider it at a satisfying state.

You can find all the code for the iterations here.

Three Page Path Challenge - second iteration

mandag den 19. august 2024

This is the third article in a series about a man with a three-page path challenge, an interview question that can come up for programmers.

In this article, I will refine and iterate further into the challenge and try answering all the challenge questions.

Make sure to read the problem scope in the first article in this series.

You should also read the article on the first iteration of the problem scope of the first question.

I left off at the first iteration with a few thoughts:

"So before I conclude this iteration, I will say that there is some programming left to do, especially around composition and naming. There might be some low-hanging fruits for performance gains, but I need to measure it, and I will not focus on them thoroughly just yet."

So, composition and naming were something I made a mental note of last time around, and it struck me while writing the last article that at least my naming was off. Composition is a different undertaking since it most likely will evolve in future iterations.

In the first iteration, I had used a single type for my implementation, which I had called CommonPathDeterminator. The name has already left my mind since I have not only renamed it but also moved implementation details around to different types.

The name itself, CommonPathDeterminator, was probably something I came up with while thinking, "this type can be used to determine common paths." A few days later, the name gives little sense. I find it too loose, I find the noun Determinator to be too vague, and really, the composition of the type is off.

But it was a fine start; it served its purpose for where I was at the time.

Let me outline the type CommonPathDeterminator from the first iteration before I reveal what I have done in this iteration.

Simply looking at the naming of the methods makes one wonder what is going on inside CommonPathDeterminator, which makes the type name even more meaningless when we read the code inside the type.

This makes it all sound like the second iteration is a blessing and everything will be right this time around. Not at all. But it will be more right in some ways, and having given myself the feedback from the first iteration, around naming and composition, I knew where I wanted to focus my attention.

The implementation details and my idea of how to reach a result still stand. As an example of that, the partitioning of log entries is still in play.

I didn't show that piece of code in the first article, but it has changed little since, except I have extracted it out from the then-known CommonPathDeterminator and put it into its own type called PathPartition.

public class PathPartition
{
    private readonly IEnumerable<LogEntry> logEntries;

    public PathPartition(IEnumerable<LogEntry> logEntries)
    {
        this.logEntries = logEntries ?? new List<LogEntry>();
    }

    public IEnumerable<UserPathPartition> PathPartitionsByUserId(int partitionSize)
    {
        var groupedLogEntriesByUser = logEntries
            .GroupBy(x => x.UserId)
            .Select(s => s.ToList());

        List<UserPathPartition> userPathPartitions = new();

        foreach (var userLogEntries in groupedLogEntriesByUser)
        {
            logEntryPartitions.Clear();
            var sizedLogPartitions = CreatePathPartitions(partitionSize, userLogEntries);

            foreach (var logPartition in sizedLogPartitions)
            {
                userPathPartitions.Add(
                    new UserPathPartition(logPartition)
                );
            }
        }

        return userPathPartitions;
    }


    private List<IEnumerable<LogEntry>> logEntryPartitions 
        = new List<IEnumerable<LogEntry>>();

    private List<IEnumerable<LogEntry>> CreatePathPartitions(
        int partitionSize, IEnumerable<LogEntry> logEntries, int skip = 0)
    {
        // no reason to continue if our log entries hold too little data
        if (logEntries.Count() < partitionSize)
        {
            return logEntryPartitions;
        }

        // skip and take because we are in recursion and must diminish the log entry size
        var skippedLogEntries = logEntries.Skip(skip);
        var logEntriesPartition = skippedLogEntries.Take(partitionSize);

        // partition entry must match wished size of partition
        if (logEntriesPartition.Count() == partitionSize)
        {
            logEntryPartitions.Add(logEntriesPartition);

            return CreatePathPartitions(partitionSize, logEntries, ++skip);
        }

        return logEntryPartitions;
    }
}

This takes a collection of log entries, partitions them grouped by a user's ID, and converts them into a collection of UserPathPartition.

This still leaves us with a result that looks like the one I had in the first iteration. But the holding type I have changed somewhat.

userPathPartitions[0]
 TotalLoadTime = 60
 FlattenedPaths = 1.html2.html3.html
 Paths = Count(3)
  [0] = 1.html
  [1] = 2.html
  [2] = 3.html
 UserId = 1
userPathPartitions[1]
 LoadTime = 60
 FlattenedPaths = 2.html3.html7.html
 Paths = Count(3)
  [0] = 2.html
  [1] = 3.html
  [2] = 7.html
 UserId = 1

The Count is not part of the type; it's merely to visualize the number of entries in the Paths collection.

public class UserPathPartition
{
    public int UserId { get; }
    public int TotalLoadTime { get => this.Paths.Sum(x => x.LoadTime); }
    public IEnumerable<LogEntry> Paths { get; }
    public string FlattenedPaths { get => Flatten(); }

    public UserPathPartition(IEnumerable<LogEntry> paths)
    {
        this.Paths = paths ?? new List<LogEntry>();
        this.UserId = this.Paths.Select(u => u.UserId).FirstOrDefault();
    }

    public string Flatten()
    {
        string flattenedPaths = string.Empty;
        foreach (var logEntry in Paths)
        {
            flattenedPaths = flattenedPaths + logEntry.Path;
        }

        return flattenedPaths;
    }
}

The flatten method is the only outlier here, and it resides here because I had a small spike during this iteration regarding a small performance optimization when handling larger data sets, and believe I found that when iterating with a foreach instead of doing return string.Join(string.Empty, Paths.Select(logEntry => logEntry.Path)); it came to the foreach's favor.

You can call it a premature optimization, but I like having these small spikes during the iterations, simply for gaining the most out of what I am trying to do. Why not have the two methods from PathPartition be part of UserPathPartition? I'm iterating gradually, and I am getting there slowly.

The type from the first iteration, CommonPathDeterminator, has been renamed to PathPatterns and now looks like this.

public class PathPatterns
{
    private readonly IEnumerable<UserPathPartition> userPathPartitions;
    private readonly Dictionary<string, PathPattern> pathPatternOccurrences;

    public PathPatterns(IEnumerable<UserPathPartition> userPathPartitions)
    {
        this.userPathPartitions = userPathPartitions ?? new List<UserPathPartition>();
        this.pathPatternOccurrences = new Dictionary<string, PathPattern>();
    }

    public IOrderedEnumerable<PathPattern> OrderByOccurrenceDescending()
    {
        pathPatternOccurrences.Clear();

        foreach (var pathPartition in userPathPartitions)
        {
            var flattenedPaths = pathPartition.FlattenedPaths;

            ExistingPathPattern(flattenedPaths, pathPartition);
            NonExistingPathPattern(flattenedPaths, pathPartition);
        }

        var orderedPatternOccurrences = pathPatternOccurrences.Values
            .OrderByDescending(p => p.OccurrenceCount);

        return orderedPatternOccurrences;
    }

    private void NonExistingPathPattern(string flattenedPaths, UserPathPartition userPathPartition)
    {
        if (!pathPatternOccurrences.ContainsKey(flattenedPaths))
        {
            var occurrence = new PathPattern(1,
                new List<UserPathPartition>() {
                    new UserPathPartition(userPathPartition.Paths)
                }
            );

            pathPatternOccurrences.Add(flattenedPaths, occurrence);
        }
    }

    private void ExistingPathPattern(string flattenedPaths, UserPathPartition userPathPartition)
    {
        if (pathPatternOccurrences.ContainsKey(flattenedPaths))
        {
            var patternOccurrence = pathPatternOccurrences[flattenedPaths];
            var count = patternOccurrence.OccurrenceCount;

            patternOccurrence.PathPatterns.Add(
                new UserPathPartition(userPathPartition.Paths)
            );

            var occurrence = new PathPattern(++count, patternOccurrence.PathPatterns);

            pathPatternOccurrences.Remove(flattenedPaths);
            pathPatternOccurrences.Add(flattenedPaths, occurrence);
        }
    }
}

So to recap, this leaves me with two types instead of the initial bastard type CommonPathDeterminator. Now I have PathPatterns and PathPartition. I am not saying this will be the final result, but I like it better than the first iteration.

This is how the PathPattern type looks:

public class PathPattern
{
    public List<UserPathPartition> PathPatterns { get; }
    public int OccurrenceCount { get; }

    public PathPattern(int occurrenceCount, List<UserPathPartition> pathPatterns)
    {         
        this.PathPatterns = pathPatterns ?? new List<UserPathPartition>();
        this.OccurrenceCount = occurrenceCount;
    }
}

All along this iteration, my tests have, of course, also transformed a bit. Like I stated in the first article, they serve as great regression guards, but I must also admit that they have changed drastically because the code they exercise has changed drastically too.

To actually answer the questions for the challenge, I have decided in this iteration to write a type called PathPatternsAnalyzer.

While writing the tests for the type PathPatternsAnalyzer, I had made a constructor for the type, looking like this: public PathPatternsAnalyzer(IOrderedEnumerable<PathPattern> orderedPathPatterns). I soon realized I had cornered myself, and it would mean my composition would be poor.

I have no good way to check the actual partition size of the argument being passed to the constructor. Remember that PathPattern has no mechanism for this and is simply a holder for data. If using this type as a constructor parameter as I had done, I could easily cheat and put any number of arbitrarily sized partitions into it. We don't want that because the goal is to look for path patterns that are sized into a specific number of partitions.

We would not be able to answer the first question, "What is the most common three-page pattern for all users?" if one partition is of size 6 and another is of size 4. They have to be sized as 3.

That means I have to add some defensiveness to my PathPatternAnalyzer type. I will take a look at that in iteration 3.

You can find the code for this iteration here.

Three Page Path Challenge - Thoughts and first iteration

tirsdag den 6. august 2024

Make sure to read the problem scope in first article in this series.

Thought processing and showing my not so good hand

In this article I will try to get my head around the first question of the challenge; What is the most common three page pattern for all users ?

When looking at a programming challenge, I usually spend some time processing and mentally mapping some of the issues at hand. I doubt this is a unique trait for me, but perhaps I spend more time than others thinking before writing any code. I like to come prepared, and I don't really like surprises. I am not a particularly fast programmer, but when I come prepared, it usually helps. I put pressure elsewhere in the beginning. But I still iterate during my implementation.

Looking at this challenge, I thought the most interesting part of the program would be how to partition the log entries into some kind of pattern which could be used later.

If the log entries look like this and our first task is to resolve the question, "What is the most common three-page pattern for all users?" my first thought was to somehow group the log entries by each user. But since the question I need to programmatically answer states "what is the most common 3-page pattern..." I also thought that I needed to partition the paths in groups of 3.

Right off, I started to think about how to make this perform decently with a million rows, which irritated me because that thought would lay there in the back of my mind while I wrote code, and I needed to put that aside.

public struct LogEntry
{
    public LogEntry(int userId, string path, int loadTime)
    {
        this.UserId = userId;
        this.LoadTime = loadTime;
        this.Path = path;
    }

    public int UserId { get; }
    public int LoadTime { get; }
    public string Path { get; }
}

I start by writing a test, of course, and TDD will help me design the code for the better as I go along and later, hopefully, guard me from regressions, which is what tests, to me, are all about.

private IEnumerable<LogEntry> FakeEntries_For_Three_Users()
{
    var entries = new List<LogEntry>
    {
        new LogEntry(1, "1.html", 20),
        new LogEntry(1, "2.html", 10),
        new LogEntry(1, "3.html", 30),
        new LogEntry(1, "7.html", 20),
        new LogEntry(1, "5.html", 10),
        new LogEntry(1, "8.html", 30),
        new LogEntry(2, "1.html", 20),
        new LogEntry(2, "2.html", 10),
        new LogEntry(2, "3.html", 40),
        new LogEntry(2, "9.html", 20),
        new LogEntry(2, "12.html", 10),
        new LogEntry(2, "36.html", 30),
        new LogEntry(3, "6.html", 20),
        new LogEntry(3, "3.html", 10),
        new LogEntry(3, "4.html", 30),
        new LogEntry(3, "1.html", 20),
        new LogEntry(3, "2.html", 22),
        new LogEntry(3, "3.html", 30)
    };
    return entries;
}

This should be easy to comprehend mentally because the log entry list at hand is short and will make my code execute faster and it will be easier for me to debug because I can calculate results by hand.

There are 6 entries with the userId=1. If I want to pair six entries into groups of 3, I should have 4 pairs:

1.html
2.html
3.html

2.html
3.html
7.html

3.html
7.html
5.html

7.html
5.html
8.html

I thought about this for a short while, while writing a bit of code, and circled around some different approaches I could take to overcome this.

Since this is the first iteration, I didn't think about returning one collection only, which I actually haven't tried, but I have made a note that it would be worthwhile pursuing.

I want to make a note of how I perceive quality in code, which is not something I believe you can ever obtain in a first iteration. So I am not so concerned with naming, structure, and to some extent design. I am always trying my best at the moment I am trying it, knowing all too well as I go on I will become wiser and simply forget why I did something. When you program for money, the time factor from external pressure for pace is never in favor.

I went back to my tests and wanted to assert my pairing of the user's paths; test, refactor, test, refactor, etc.

[Fact]
public void Common_Path_Partitions_For_User_Is_Partitioned_Correctly()
{
    //Arrange
    var sut = new CommonPathDeterminator(FakeEntries_For_Three_Users());
    
    //Act
    var partitions = sut.CommonPathPartitionsByUserId();
    var user1PartitionSize = partitions.Where(p => p.UserId == 1).Select(x => x.Paths).Count();
    var user2PartitionSize = partitions.Where(p => p.UserId == 2).Select(x => x.Paths).Count();
    var user3PartitionSize = partitions.Where(p => p.UserId == 3).Select(x => x.Paths).Count();
    
    //Assert
    Assert.True(user1PartitionSize == 4);
    Assert.True(user2PartitionSize == 4);
    Assert.True(user3PartitionSize == 4);
}

I exercise the CommonPathPartitionsByUserId as you might have spotted. I have a few more tests that exercise the same method, with different input, but I saw no reason to add them here.

public IEnumerable<CommonPath> CommonPathPartitionsByUserId()
{
    var groupByUser = logEntries
        .GroupBy(x => x.UserId)
        .Select(s => s.ToList());
        
    List<CommonPath> commonPaths = new();

    foreach (var entry in groupByUser)
    {
        logPartitions.Clear();

        var partitioned = CreateLogPartitions(3, entry);

        foreach (var partition in partitioned)
        {
            var paths = partition.Select(p => p.Path);
            var loadTimeSum = partition.Sum(s => s.LoadTime);
            var userId = partition.Select(u => u.UserId).FirstOrDefault();
            commonPaths.Add(
                new CommonPath(loadTimeSum, userId, paths)
            );
        }
    }
    return commonPaths;
}

Looking at this code while I write this, I have a thought about the nested loop. I cannot make an exact point to what I am trying to infer, I need to think and look at it more thoroughly. That's how my programming mind also works.

In the inner loop, I call CreateLogPartitions(3, entry); where entry is the list of log entries for a user.

The responsibility of the method CreateLogPartitions is to pair the paths for each user. During a TDD "iteration", I ended up creating a new type; CommonPath, which I use for holding the log entry pairs and a summed-up load time for each pair.

public class CommonPath
{
    public int UserId { get; }
    public int LoadTimeSum { get; }
    public IEnumerable<string> Paths { get; } = new List<string>();
    public CommonPath(int loadTimeSum, int userId, IEnumerable<string> paths)
    {
        this.LoadTimeSum = loadTimeSum;
        this.UserId = userId;
        this.Paths = paths;
    }
}

You might wonder what the method CreateLogPartitions looks like, but I am not going to show it to you just yet. Think about how you would do it yourself.

I made the return value of the method a List<IEnumerable<LogEntry>> and I made the method recursive. It didn't take me long to note this as something I might want to address in the near future. Not that I do not find recursion useful, but I am not sure it helps the reader of the code in this case, as it might be too much for what is needed. I believe a simpler loop could do the same, and I might want to try it in another iteration. I might not. The signature of the method looks like this, see if you can implement a recursive method with the same signature List<IEnumerable<LogEntry>> CreateLogPartitions(int partitionSize, IEnumerable<LogEntry> logEntries, int skip = 0)

What I am left with, which is also exposed by looking at the test above, is a collection IEnumerable<CommonPath>.

The first two entries in the collection:

commonPaths[0]
 LoadTime = 60
 Paths = Count(3)
  [0] = 1.html
  [1] = 2.html
  [2] = 3.html
 UserId = 1
commonPaths[1]
 LoadTime = 60
 Paths = Count(3)
  [0] = 2.html
  [1] = 3.html
  [2] = 7.html
 UserId = 1

So now I have a collection with all the possible 3-pair path patterns for each user. I have a few tests and I am at a point where I need to think about how I will count the occurrences of each pattern.

At this point, I thought the "worst part" was over and I could start laying the groundwork for somehow counting the occurrences in the IEnumerable<CommonPath>. For that, I believed I needed a faster collection than a List and I also wanted to compose a different type than the CommonPath for holding the result.

Back to the tests. As I started writing a test, I composed a new type, which I circled around for exposing the result as a collection. It manifested into an mutable type like this. If I could get a collection of this type as a result, I would be grateful.

public class CommonPathOccurrence
{
    public List<CommonPath> CommonPaths { get; } = new List<CommonPath>();
    public int OccurrenceCount { get; }
    public CommonPathOccurrence(int occurrenceCount, List<CommonPath> commonPaths)
    {         
        this.CommonPaths = commonPaths;
        this.OccurrenceCount = occurrenceCount;
    }
}

I know there are a few things that stick out here, but it's the first iteration, and as previously stated, I will re-iterate.

But I still needed to do some internal juggling for adding and increasing to this type, specifically since the type I made mutable, I would have to do a little more than if it were immutable.

[Fact]
public void Find_Most_Common_Three_Page_Path_Pattern_For_Three_Users()
{
    //Arrange
    var sut = new CommonPathDeterminator(FakeEntries_For_Three_Users());
    
    //Act
    var pattern = sut.ThreePagePattern(sut.CommonPathPartitionsByUserId());
    
    //Assert
    var commonPaths = pattern
        .Where(w => w.OccurrenceCount == 3)
        .SelectMany(s => s.CommonPaths);
    
    var allPathsEqual = commonPaths
        .All(a => a.Paths.SequenceEqual(commonPaths.First().Paths));
    
    Assert.True(allPathsEqual);
}

Remember the list of entries I am testing against. It has some users that each share the same path pattern of 1.html, 2.html, 3.html. That is the most common pattern; hence, it should occur 3 times in the collection variable "pattern".

public IEnumerable<CommonPathOccurrence> ThreePagePattern(IEnumerable<CommonPath> commonPaths)
{
    foreach (var commonPath in commonPaths)
    {
        var flatPaths = string.Join(string.Empty, commonPath.Paths);

        ExistingCommonPathOccurrence(flatPaths, commonPath);
        NonExistingCommonPathOccurrence(flatPaths, commonPath);
    }

    var orderedMostCommonThreePagePattern = commonPathOccurrences
        .OrderBy(o => o.Key)
        .Select(o => o.Value)
        .ToList();

    return orderedMostCommonThreePagePattern;
}

The two methods ExistingCommonPathOccurrence and NonExistingCommonPathOccurrence are private and make use of the commonPathOccurrences, which is a Dictionary<string, CommonPathOccurrence>.

Here are those two methods:

private Dictionary<string, CommonPathOccurrence> commonPathOccurrences = new();

private void NonExistingCommonPathOccurrence(string flatPaths, CommonPath commonPath)
{
    if (!commonPathOccurrences.ContainsKey(flatPaths))
    {
        var occurrence = new CommonPathOccurrence(1,
            new List<CommonPath>() {
                new CommonPath(commonPath.LoadTimeSum, 0, commonPath.Paths)
            }
        );
        commonPathOccurrences.Add(flatPaths, occurrence);
    }
}

private void ExistingCommonPathOccurrence(string flatPaths, CommonPath commonPath)
{
    if (commonPathOccurrences.ContainsKey(flatPaths))
    {
        var existing = commonPathOccurrences[flatPaths];
        var newCount = existing.OccurrenceCount;

        var newCommonPaths = new List<CommonPath>(existing.CommonPaths)
        {
            new CommonPath(commonPath.LoadTimeSum, 0, commonPath.Paths)
        };

        var occurrence = new CommonPathOccurrence(++newCount, newCommonPaths);
        
        commonPathOccurrences.Remove(flatPaths);
        commonPathOccurrences.Add(flatPaths, occurrence);
    }
}

I chose to flatten the paths and use that as my dictionary key.

I use the CommonPath as a collection type within CommonPathOccurrence acting as a container, but looking at the composition and especially how I use that specific collection with the ExistingCommonPathOccurrence and NonExistingCommonPathOccurrence I think I can do a better design. This is still the first iteration, though, so I will come to it.

Let's look at the calling method again. I call the "internal workings", which hand me back a Dictionary<string, CommonPathOccurrence>, and then I order it by its key and convert it into a List. This seems expensive, so I will have to address that too.

public IEnumerable<CommonPathOccurrence> ThreePagePattern(IEnumerable<CommonPath> commonPaths)
{
    foreach (var commonPath in commonPaths)
    {
        var flatPaths = string.Join(string.Empty, commonPath.Paths);

        ExistingCommonPathOccurrence(flatPaths, commonPath);
        NonExistingCommonPathOccurrence(flatPaths, commonPath);
    }

    var orderedMostCommonThreePagePattern = commonPathOccurrences
        .OrderBy(o => o.Key)
        .Select(o => o.Value)
        .ToList();

    return orderedMostCommonThreePagePattern;
}

This leaves me with a result which the test above Find_Most_Common_Three_Page_Path_Pattern_For_Three_Users asserts to true. It's not ordered by the OccurrenceCount but my method ThreePagePattern is not yet named as such that it infers that it should come in some kind of order. Next iteration.

I am well aware that I have not answered all the questions for the challenge, but I are getting there.

So before I conclude this iteration, I will say that there are some programming left to do, especially around composition and naming. There might be some low-hanging fruits for performance gains, but I need to measure it, and I will not focus on them thouroughly just yet.

When I run the code with a million rows, it times right now to around 7 seconds, which I believe is way too long. I will hopefully iterate my way through to better performance too.

The code for the first iteration you may find here.

A Man with a Three Page Path Challenge

torsdag den 1. august 2024

During a stay on a small island in Kattegat, one night I was thirsty for company and crept offboard and into the sunsetting night of imagination and warm air around me. The waves licking shore into true randomness of sparkling diamonds from the low sun and the sandy banks still covering the desert while people calmly sipping on colored drinks and wine in their cockpits.

I found a small bar in the northwestern end of the harbor, a wooden shack with an older lady as barkeep. Twenty years ago, this place was nothing but fishing boats and an anchorage bay. She looked like she couldn't do her job much longer, but she still looked nothing like other people's integrity. I didn't blame her. We are all for sale, I thought. I ordered two drinks for myself, which is an old habit, one for a thirsty palate and the delightful possibility of not drinking just one thing.

Then I sat down, leaning my back on the wooden shack and watched the sea with no land in sight. Hazy colors of yellow and light brown are easy on the eyes, and it's the only time in the summer I am not wearing sunglasses. Next to me sat a few people that looked like they were about to leave. They greeted me, and I returned a handwave. The mind wanders when you are off the load for a longer period. A short man with round glasses and a beard approached the shack, came up to me, and sat right across. Nothing stopped him as he started talking to me. I looked around to see if he was conversing with someone unknown to me. I realized he was talking to me, and he was letting that tongue go about his trip and soon his long-awaited vacation from his work.

As Dire Straits' "Wild West End" played softly in the background, we chatted a bit. A lot of people love talking about their jobs; sometimes, it seems to me it is their sole adventure for success. Work are most people's lives, I suppose. So there we went. Luckily for me, it turned out he was very much into programming, as was I, how the wondrous alleys of playful thoughts and creativity can be enjoyable at first, but get a tunnel vision and try to auction it off, will fool you, and when money is involved, your chance of getting out in time is low. You can't succeed trading your passion. Yet he seemed tense and wanted to let me know that what he did was very special. Often people really believe their jobs are special. As the subtle talk went on, it came to my knowledge that, at this given time, he was looking for candidates for a job in some industry I had soon forgot.

He had found it difficult to interview programmer candidates; either they were too stubborn or too con-man-like. Down my alley, I thought. If you cannot lie, you have no chance - look at the industry I thought, perhaps it looks like Klondike - but most people seem to forget that they are silently applauding the ones who are cheating them from their own success. And it always ends up in the same dead end, claiming "it's just a job." And nobody really seems to mind - the circus is full of light, the man on the stool takes your money and in the morning we do it all over again. We talked about his candidate interview practices, and as he had calmed down a bit, I found him to be a decent man. Since I am absolutely not a finalist in the act of job interviews, I could lean into it without coming across as someone with potential. I have always had a quite extinguished dislike for the human across from me who wants so badly to make me answer questions in time or show how I perform with the hourglass turned. Looking for the truth without ever questioning their our own answers.

I needed to refill my two drinks and went back to the barkeep, who had become angry. Cheer up, I said, summer is almost over. She smiled, but it was hardly genuine, which is almost like being turned down for a job - with an almost genuine smile. She would be a brilliant interviewer, I thought. A vodka with sparkling water and a rum and chocolate milk. Thank you.

I came back to my new acquaintance, who had lit a cigarette and had become quiet. The quiet didn't last very long. As we sat there talking about the recent programming books we had read, I had to remind myself not to mix business with sailing (or any other pleasure), as it's often a given that when I start answering questions, I either do not understand why the questions are relevant or why we are so obsessed with finding a quick answer. It's a contradictory world. What nature and the sea offers you is slow and takes its time, compared to the world of technology, it is incomparable. Yet we tell ourselves over and over, trying to convince, that things on a screen can be beautiful. People either do not spend much time outside or need larger glasses. You can't save them all. More want's more, while time flies, being the only true currency I measure things in.

The drinks help me to swallow it all. Somehow, I fumbled and asked what my new friend's challenges were during interviews with programming candidates. Now I had done it, I had walked right into it, I thought, and I regretted it instantly. But somewhere in the back of my skull, emptied from being on the sea, I knew I had to know why this was so difficult.

An hour went by, both of us loosened up in regards to our stance towards the challenge thar these programming candidates were given during an interview. The night soon turned dark and hollow. Most of the harbor asleep, and the sizzling water had calmed down, not so diamond sparkly any longer. I found my way back to the boat, stepped aboard, and slowly turned into my woman's warm body. I lay there in the stern cabin and thought about the challenge this human I had had a friendly encounter with. As a programmer with an issue at hand, you start thinking about a solution. This time was certainly no different.

The Three Page Pattern Challenge for the Programming Interview.

You have a log file which is from a website. It has 3 columns. There are a million rows in the log file.

The columns in the file is "UserId", "Path", "LoadTime". It's a given that its ordered by a timestamp which is not present.

A few rows could look like this. Here I have taken the authors executive and ordered the list for you but in the log file users are not ordered.

1, default.html, 87
2, default.html, 37
3, default.html, 57
1, jobs.html, 22
2, drinks.html, 34
3, jobs.html, 58
1, about.html, 11
2, food.html, 89
3, about.html, 43
1, food.html, 36
2, jobs.html, 78
3, order.html, 66

So can we imagine an interviewer would ask us ? Horrible question to get under pressure. What programming was ever done with quality under pressure ?

Try to see if you can make sense of these questions ?

Since this is not a question in an hour long interview I actually have a chance as well. I would not be able to make a programming solution for this challenge with dignity or certainty within a short time. I am not a fast programmer and I do not have faith or trust in the code that I write before I have iterated over it for some time.

From here on I will try to make an iterative solution for this challenge, write about my thoughts and solutions, and I might be wrong and fail, but at least I get to excersise my programming skills.

I have made a log file for the challenge which you can download here if you want to give it a try.