# The Wiert Corner – irregular stream of stuff

• ## Email Subscription

Join 2,873 other followers

# Archive for the ‘Algorithms’ Category

## Coming Back to Old Problems: How I Finally Wrote a Sudoku Solving Algorithm – DEV Community 👩‍💻👨‍💻

Posted by jpluimers on 2021/09/02

It is always fun to see how Sudoku solving algorithms are created and implemented. This is no exception: [WayBack] Coming Back to Old Problems: How I Finally Wrote a Sudoku Solving Algorithm – DEV Community 👩‍💻👨‍💻

For a visual Sudoku solver, I usually take [WayBack] Sudoku Solver by Andrew Stuart. Shows the logic behind solving Sudoku square by square which is part of [WayBack] SudokuWiki.org – Getting Started having many visual explanations on how to solve these puzzles, for instance:

It’s a kind of sudo ku, but visually and never failed me solve one.

–jeroen

## Two might lead to a pattern

Posted by jpluimers on 2021/08/05

There is a known saying phrased using cardinal, adverbial or ordinal numbers, and several naming for the first:

• One is change, two is coincidence, three is a pattern
• Once Is Chance, Twice is Coincidence, Third Time Is A Pattern
• One is an anomaly, two is a coincidence, three is a pattern
• First time is an incident, second a coincidence, third a pattern

Sometimes the second can lead to a pattern.

## CloudFlare knows how to do public postmortems on outages

Posted by jpluimers on 2021/07/16

Everyone can learn from an outage. CloudFlare shows how to do it right, for instance on the RegEx-going-wild downtime 2 years ago.

So it’s time to link to that one again: [WayBack] Details of the Cloudflare outage on July 2, 2019

More like these at [WayBack] Post Mortem – The Cloudflare Blog.

More on evaluating regular expressions in linear time:

• [WayBack] Regular Expression Search Algorithm KEN THOMPSON Bell Telephone Laboratories, Inc., Murray Hill, New Jersey
• [WayBack] Programming Techniques: Regular expression search algorithm / [WayBack] Programming Techniques: Regular expression search algorithm

A method for locating specific character strings embedded in character text is described and an implementation of this method in the form of a compiler is discussed. The compiler accepts a regular expression as source language and produces an IBM 7094 program as object language. The object program then accepts the text to be searched as input and produces a signal every time an embedded string in the text matches the given regular expression. Examples, problems, and solutions are also presented.

# Programming Techniques: Regular expression search algorithm

 Full Text: PDF
 Author: Ken Thompson Bell Telphone Labs, Inc., Murray Hill
 Published in: · Magazine Communications of the ACM CACM Homepage archive Volume 11 Issue 6, June 1968 Pages 419-422 ACM New York, NY, USA table of contents doi>10.1145/363347.363387
• Thompson’s construction – Wikipedia

is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA)

The algorithm works recursively by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules.[3] More precisely, from a regular expression E, the obtained automaton A with the transition function δ respects the following properties:

• A has exactly one initial state q0, which is not accessible from any other state. That is, for any state q and any letter a{\displaystyle \delta (q,a)} does not contain q0.
• A has exactly one final state qf, which is not co-accessible from any other state. That is, for any letter a{\displaystyle \delta (q_{f},a)=\emptyset }.
• Let c be the number of concatenation of the regular expression E and let s be the number of symbols apart from parentheses — that is, |*a and ε. Then, the number of states of A is 2s − c (linear in the size of E).
• The number of transitions leaving any state is at most two.
• Since an NFA of m states and at most e transitions from each state can match a string of length n in time O(emn), a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.
• [WayBack] A Regular Expression Matcher Code by Rob Pike Exegesis by Brian Kernighan

–jeroen

## c# – Algorithm to check whether a certain hour falls into a given time period – Stack Overflow

Posted by jpluimers on 2021/07/15

For my link archive: [WayBack] c# – Algorithm to check whether a certain hour falls into a given time period – Stack Overflow answered by [WayBack] kennytm:

Assume you only have the time and not the date.

if end_time >= start_time:
return start_time <= current_time <= end_time
else:
return start_time <= current_time or current_time <= end_time

I totally agree with this comment:

This is brilliant! Thanks a lot. – Martin Dimitrov [WayBack]

I love it when algorithms are simple and elegant.

It reminded me of another scheduling related algorithm: [WayBack] Activity Selection Problem | Greedy Algo-1 – GeeksforGeeks

–jeroen

## “Not having done docker, but having developed enough software to have the impression that as soon as things get hierarchical, things eventually end up in a mess. Somewhere down the road something won’t cope with depth/breadth/size and break badly.”

Posted by jpluimers on 2021/06/22

I originally posted this in a docker on docker thread, but I think it holds universally:

This despite the cool gif in the reply:

I found the below video files by searching for zzzz