…And Primus for All

In this note I will describe the launch of Steam games on the Linux distribution Arch Linux in the configuration of an Intel + Nvidia laptop

Counter-Strike: Global Offensive

The only configuration that worked for me is Primus-vk + Vulkan.

Install the required packages:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Next, add launch options for Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Should work!

Sid Meier’s Civilization VI

Works in conjunction – Primus + OpenGL + LD_PRELOAD.

Install the Primus package:
pacman -S primus

Next, add launch options for Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

LD_PRELOAD pushes the Freetype compression and font libraries.

Dota 2

Works in conjunction – Primus + OpenGL + removal of locks at startup.

Install the Primus package:
pacman -S primus

Next, add launch options for Dota 2:
primusrun %command% -gl -console

If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file
rm /tmp/source_engine_2808995433.lock
Usually the lock file is left over from the last game session unless the game was closed naturally.

How to check?

The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:

For games on the Source engine, you can check through the game console using the mat_info command:



Sleep Sort

Sleep Sort – sleep sorting, another representative of deterministic strange sorting algorithms.

Works like this:

  1. Iterates through a list of elements
  2. Run a separate thread for each loop
  3. The thread sleeps (sleep) the thread for a while – the value of the element and output the value after sleep
  4. At the end of the loop, wait until the end of the thread’s longest sleep, display a sorted list

An example code for the sleep sort algorithm in C:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

typedef struct {
    int number;
} ThreadPayload;

void *sortNumber(void *args) {
    ThreadPayload *payload = (ThreadPayload*) args;
    const int number = payload->number;
    usleep(number * 1000);
    printf("%d", number);
    return NULL;

int main(int argc, char *argv[]) {
    const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
    const int length = sizeof(numbers) / sizeof(int);

    int maximal = 0;
    pthread_t maximalThreadID;

    printf("Sorting: ");
    for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
        pthread_create(&threadID, NULL, sortNumber, (void *) payload);
        if (maximum < number) {
            maximal = number;
            maximalThreadID = threadID;
    printf("Sorted: ");
    pthread_join(maximalThreadID, NULL);
    return 0;

In this implementation, I used the usleep function on microseconds with the value multiplied by 1000, i.e. in milliseconds.
The time complexity of the algorithm is O(v. long)


https://gitlab.com/demensdeum/algorithms/ -/tree/master/sortAlgorithms/sleepSort


https://codoholicconfessions.wordpress.com/2017 /05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang= en
https:// stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

Stalin Sort

Stalin Sort – sorting right through, one of the sorting algorithms with data loss.
The algorithm is very efficient and efficient, O(n) time complexity.

It works like this:

  1. Loop through the array, comparing the current element with the next
  2. If the next element is less than the current one, then delete it
  3. As a result, we get a sorted array in O(n)

An example of the output of the algorithm:

Numbers: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]

Python 3 code:

numbers = [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
    element = numbers[i]
    if maximal > element:
        print(f"Element {element} sent to Gulag")
        gulag append(element)
        del numbers[i]
        maximal = element
        i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")

Of the disadvantages, data loss can be noted, but if you move to a utopian, ideal, sorted list in O(n), how else?


https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/stalinSort


https://www.youtube.com/shorts/juRL-Xn- E00

Selection Sort

Selection Sort – selection sort algorithm. Choice of what? But the minimum number!!!
The time complexity of the algorithm is O(n2)

The algorithm works as follows:

  1. We loop through the array from left to right, remember the current starting index and the number by index, let’s call the number A
  2. Inside the loop, we run another one to pass from left to right, looking for less than A
  3. When we find a smaller one, remember the index, now the smaller one becomes the number A
  4. When the inner loop ends, swap the number at the start index and the number A
  5. After a full pass of the upper loop, we get a sorted array

Algorithm execution example:

Round 1
(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)

Not finding an Objective-C implementation at Rosetta Code, wrote his self:

#include "SelectionSort.h"
#include <Foundation/Foundation.h>

@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
   NSLog(@"%@", numbers);   
   for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
      int minimalNumberIndex = startIndex;
      for (int i = startIndex + 1; i < numbers.count; i++) {
         id lhs = [numbers objectAtIndex: minimalNumberIndex];
         id rhs = [numbers objectAtIndex: i];
         if ([lhs isGreaterThan: rhs]) {
            minimalNumberIndex = i;
      id temporary = [numbers objectAtIndex: minimalNumberIndex];
      [numbers setObject: [numbers objectAtIndex: startIndex] 
               atIndexedSubscript: minimalNumberIndex];
      [numbers setObject: temporary
               atIndexedSubscript: startIndex];
   NSLog(@"%@", numbers);


You can build and run either on MacOS/Xcode, or on any operating system that supports GNUstep, for example, I'm building Clang on Arch Linux.
Assembly script:

clang SelectionSort.m \
        -lobjc \
        `gnustep-config --objc-flags` \
        `gnustep-config --objc-libs` \
        -I /usr/include/GNUstepBase\
        -I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
        -lgnustep-base \
        -o SelectionSort \


https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/selectionSort



Counting Sort

Counting sort – counting sort algorithm. What? Yes! Just like that!

The algorithm involves at least two arrays, the first is a list of integers to be sorted, the second is an array of size = (maximum number – minimum number) + 1, initially containing only zeros. Next, the numbers from the first array are sorted out, the index in the second array is obtained by the element-number, which is incremented by one. After going through the entire list, we will get a completely filled second array with the number of repetitions of numbers from the first. The algorithm has a serious overhead – the second array also contains zeros for numbers that are not in the first list, the so-called. memory overhead.

After getting the second array, iterate over it and write the sorted version of the number by index, decrementing the counter to zero. Initially, the zero counter is ignored.

An unoptimized example of how the counting sort algorithm works:

  1. Input array 1,9,1,4,6,4,4
  2. Then the array to count will be 0,1,2,3,4,5,6,7,8,9 (minimum number 0, maximum 9)
  3. With total counters 0,2,0,0,3,0,1,0,0,1
  4. Total sorted array 1,1,4,4,4,6,9

Algorithm code in Python 3:

print("Counting Sort")

numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(f"Minimal number: {minimal}")
print(f"Maximum number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1


Due to the use of two arrays, the time complexity of the algorithm is O(n + k)






Pseudo sort or swamp sort, one of the most useless sorting algorithms.

It works like this:
1. Input is an array of numbers
2. An array of numbers is shuffled randomly (shuffle)
3. Checking if the array is sorted
4. If not sorted, then the array is shuffled again
5. All this action is repeated until the array is sorted randomly.

As you can see, the performance of this algorithm is terrible, smart people think that even O(n * n!) there is a chance to get stuck throwing dice for the glory of the god of chaos for many years, the array will not be sorted, or maybe sorted?


For the TypeScript implementation, I needed to implement the following functions:
1. Shuffling an array of objects
2. Comparing arrays
3. Generating a random number between zero and a number (sic!)
4. Seal of progress, as the sorting seems to run indefinitely

Below is the TypeScript implementation code:

const printoutProcess = (numbers: number[], sortedNumbers: number[], numberOfRuns: number) => console.log(`Still trying to sort: ${numbers}, current shuffle ${sortedNumbers}, try number: ${numberOfRuns}`);
const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
    for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); vartemp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();

let numberOfRuns = 1;

do {
    if (numberOfRuns % 1000 == 0) {
        printoutProcess(originalNumbers, numbers, numberOfRuns);
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);

You can use VSCode and kakumei’s TypeScript Debugger plugin for debugging.

How long

Output of the algorithm:

Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 2,9,7,8,0,7,4,5,2 ,5, try number: 144000
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
Run number: 148798
Original numbers: 5,4,8,7,5,0,2,9,7,2
Current numbers: 5,4,8,7,5,0,2,9,7,2
Sorted numbers: 0,2,2,4,5,5,7,7,8,9

For an array of 10 numbers, Bogosort shuffled the original array 148798 times, too much right?
The algorithm can be used as a training one, to understand the capabilities of the language with which to work on the market. Personally, I was surprised to learn that vanilla JS and TS still do not have their own algorithm for shuffling arrays, generating an integer in a range, accessing object hashes for quick comparison.


https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/bogosort
https://marketplace.visualstudio.com/items?itemName= kakumei.ts-debug



GoF Patterns

List of most important OOP patterns in computer programming aka Gang of Four Design Patterns.

Creational patterns

Structural patterns

Behavioral patterns

Interpreter Pattern

What’s included

The Interpreter Pattern is a Behavioral Design Pattern. This pattern allows you to implement your own programming language by working with an AST tree, the vertices of which are terminal and non-terminal expressions that implement the Interpret method, which provides the functionality of the language.

  • Terminal expression – e.g. string constant – “Hello World”
  • Non-terminal expression – e.g. Print(“Hello World”), contains Print and an argument from the Terminal expression “Hello World”

What’s the difference? The difference is that the interpretation on terminal expressions ends, and for non-terminal expressions it continues deep into all incoming nodes/arguments. If the AST tree consisted only of non-terminal expressions, then the application would never complete, because some end of any process is required, this end is what terminal expressions are, they usually contain data, for example, strings.

An example of an AST tree is below:

Dcoetzee, CC0, via Wikimedia Commons

As you can see, terminal expressions are constant and variable, non-terminal expressions are the rest.

What is not included

The implementation of the Interpreter does not parse the string input of the language into the AST tree. It is enough to implement classes of terminal, non-terminal expressions, Interpret methods with the Context argument at the input, form an AST tree from expressions, run the Interpret method at the root expression. The context can be used to store the state of the application at runtime.


Participants in the pattern:

  • Client – returns AST tree and runs Interpret(context) on root node (Client)
  • Context – contains the state of the application, passed to expressions when interpreted (Context)
  • Abstract expression – an abstract class containing the method Interpret(context) (Expression)
  • Terminal expression is a final expression, a descendant of an abstract expression (TerminalExpression)
  • A non-terminal expression is not a final expression, contains pointers to nodes deep into the AST tree, subordinate nodes usually affect the result of interpreting a non-terminal expression (NonTerminalExpression)

C# Client Example

class Application {
        static void Main(string[] args)
            var context = new Context();
            var initialProgram = new PerformExpression(
                new IExpression[] {
                    new SetExpression("alpha", "1"),
                    new GetExpression("alpha"),
                    new PrintExpression(
                        new IExpression[] {
                            new ConstantExpression("Hello Interpreter Pattern")

Example of an Abstract Expression in C#

interface IExpression
    String interpret(Context context);

C# Terminal Expression Example (String Constant)

class ConstantExpression : TerminalExpression
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;

    override public String interpret(Context context) {
        return constant;

Example of a Non-Terminal Expression in C# (Launching and concatenating the results of subordinate nodes, using the delimiter “;”

class PerformExpression : NonTerminalExpression
    public PerformExpression(IExpression[] leaves) : base(leafs) {
        this.leafs = leaves;
    override public String interpret(Context context) {
        var output = "";
        foreach (var leaf in leaves) {
            output += leaf.interpret(context) + ";";
        return output;

Functionally, can you?

As you know, all Turing-complete languages ​​are equivalent. Can the Object-Oriented pattern be transferred to a Functional Programming language?

You can, for the experiment, let’s take the FP language for the web called Elm. There are no classes in Elm, but there are Records and Types, so the following records and types are involved in the implementation:

  • Expression – enumeration of all possible language expressions (Expression)
  • Subordinate expression – an expression that is subordinate to a non-terminal expression (ExpressionLeaf)
  • Context – a record that stores the state of the application (Context)
  • Functions that implement the Interpret(context) methods – all the necessary functions that implement the functionality of Terminal, Non-Terminal expressions
  • Auxiliary records of the Interpreter state – necessary for the correct operation of the Interpreter, store the state of the Interpreter, the context

For example function that implements the interpretation for the entire set of possible expressions on Elm:

run input =
  case input.expression of
    Constant text ->
        output = text
        context = input.context
    Perform leafs ->
      let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
        let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
          let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
              output = (runExpressionLeaf outputExpressionInput).output,
              context = input.context
    Print printExpression ->
        expression = printExpression,
        context = input.context
    Set key value ->
      let variables = Dict.insert key value input.context.variables in
        context = { variables = variables }
    get key ->
        output = Maybe.withDefault("No value for key: " ++ key)(Dict.get key input.context.variables),
        context = input.context

What about parsing?

Parsing source code into an AST tree is not part of the Interpreter pattern, there are several approaches to parsing source code, but more on that some other time.
In the implementation of the Interpreter for Elm, I wrote the simplest parser into the AST tree, consisting of two functions – parsing a vertex, parsing subordinate vertices.

parseLeafs: ParseLeafsState -> ParseLeafsState
parseLeafs state =
    let tokensQueue = state.tokensQueue in
        let popped = pop state.tokensQueue in
            let tokensQueueTail = tail state.tokensQueue in
                if popped == "Nothing" then
                else if popped == "Perform(" then
                        tokensQueue = tokensQueue,
                        result = (state.result++[Node(parse tokensQueue)])
                else if popped == ")" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = state.result
                else if popped == "Set" then
                    let key = pop tokensQueueTail in
                        let value = pop(tail tokensQueueTail) in
                            parseLeafs {
                                tokensQueue = tail(tail tokensQueueTail),
                                result = (state.result++[Node(Set key value)])
                else if popped == "Get" then
                    let key = pop tokensQueueTail in
                        parseLeafs {
                            tokensQueue = tail tokensQueueTail,
                            result = (state.result++[Node(Get key)])
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = (state.result++[Node(Constant popped)])

parse tokensQueue =
    let popped = pop tokensQueue in
        let tokensQueueTail = tail tokensQueue in
            if popped == "Perform(" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = []
            else if popped == "Set" then
                let key = pop tokensQueueTail in
                    let value = pop(tail tokensQueueTail) in
                        set key value
            else if popped == "Print" then
                Print(parse tokensQueueTail)
                Constant popped


https://gitlab.com/demensdeum /patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/ -/tree/master/interpreter/csharp


https://docs.microsoft.com/en-us/dotnet /csharp/