kenyan programmer

mostly about programming


String searching

[orgmode source] Table of Contents 1. String Search 1.1. Naive string search 1.1.1. Complexity 1.2. Boyer-Moore-Horspool Search Algorithm 1.2.1. Complexity 1. String Search We define a function that takes in a pattern to search for and the string to search and returns a list of all found matches. Each match is in the form of a tuple of the index in the string at which the pattern was found, and the length of the substring matching the pattern.

Read more...

Binary Tree Basics

[orgmode source] Table of Contents 1. Basics of Binary Search Trees 1.1. Building a BST 1.2. In order Traversal 1.2.1. Recursive 1.2.2. Iterative 1.3. Pre-Order Traversal 1.3.1. Recursive 1.3.2. Iterative 1.4. Post-Order Traversal 1.4.1. Recursive 1.4.2. Iterative 1.5. Breadth first search 1.6. Deleting a node in a BST 1. Basics of Binary Search Trees Each node has a maximum of two children. The value of the left child is less than the node's value.

Read more...

Cycle Detection

[orgmode source] Table of Contents 1. Detect cycle in a linked list 1.1. First approach: Using a visited set 1.1.1. Analysis 1.2. Second approach: Floyd's Tortoise and Hare 1.2.1. Analysis 1.3. References 1. Detect cycle in a linked list Given the head of a linked list, return a boolean indicating whether it has a cycle or not. A node can be represented as a class with value and a pointer to the next node.

Read more...

Pharo Smalltalk is like English

I’m currently on week 2 of the pharo mooc, and it’s fun and eye opening so far. Smalltalk the language was designed by Alan Kay to be easy enough for a child to use in his dynabook project, and that is why it has such a small syntax. In the mooc, an example I see of this is when it comes to your typical method call in C-like languages.

Read more...

Entities vs Value Objects in Domain Driven Design

One of the common concepts that one comes across in Domain Driven Design is that of entities vs value objects. For example, a person could be represented as an entity, whereas their name is a value object. Or in a financial transaction, the transaction is represented as an entity and is stored in perpetuity, whereas the amount involved is a value object composed of an number and a currency unit.

Read more...

Pharo Smalltalk syntax fits on a postcard

Of late, I’ve been playing with the language Pharo, which is inspired by SmallTalk. One interesting thing that I appreciate, and Pharo people boast about is how small its syntax is. So small that it can fit on a postcard. From this small base, an amazingly hackable system has been put together. From these slides. I made an imperfect attempt to translate it to python, with some ugly workarounds just to make it run, since there are no obvious python equivalents for some things.

Read more...

Farewell Dave Mills, inventor of the Network Time Protocol

News has broken out today that Dave Mills, inventor of the Network Time Protocol and author of the reference implementation has passed on. The protocol and its implementation, now referred to as NTP classic, is near ubiquitous on the Internet keeping all sorts of connected servers in sync. However, this has for a long time (decades) been happening with very little funding, with Dave Mills and his successors doing it as mostly a labour of love.

Read more...

Help! My client code isn't being type checked by mypy

That was the issue I had this morning. I had written some piece of code with type annotations but obviously wrong type assignments in unit tests, but mypy was reporting that everything was OK. I had code like this: # lib.py from dataclasses import dataclass @dataclass class Question: text: str options: list['Option'] | None = None @dataclass class Option: text: str correct: bool = False And a test like this:

Read more...
1 of 2 Next Page