## Bogosort

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?

### Implementation

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);
}
shuffle(numbers);
numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Success!`);
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
src/bogosort.ts:1
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
src/bogosort.ts:2
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
src/bogosort.ts:2
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
src/bogosort.ts:2
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
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
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.

## 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.

### Implementation

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")
}
)
}
);
System.Console.WriteLine(initialProgram.interpret(context));
}
}
``````

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 ->
run
{
expression = printExpression,
context = input.context
}
Set key value ->
let variables = Dict.insert key value input.context.variables in
{
output="OK",
context = { variables = variables }
}
get key ->
{
output = Maybe.withDefault("No value for key: " ++ key)(Dict.get key input.context.variables),
context = input.context
}
``````

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
state
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)])
}
else
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
Perform(
parseLeafs {
tokensQueue = tokensQueueTail,
result = []
}
).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)
else
Constant popped
``````

## RGB Image to Grayscale

In this article I will describe algorithm of converting RGB image buffer to Grayscale
And this is done quite simply, each pixel of the color channel of the buffer is converted according to a certain formula, and the output is a gray image.
Average method:

``````const average = (red + green + blue) / 3;
red = average;
green = average;
blue = average;``````

Add the 3 color channels and divide by 3.

However, there is another method – the weighted average method, it takes into account the human color perception:

``````const luminance = 0.2126 * red + 0.7152 * green + 0.0722 * blue;
red = luminance;
green = luminance;
blue = luminance;``````

What is the best method to use? Choose one that suits you better for a particular task. Next, a comparison of methods using a test color grid:

Example JavaScript + HTML 5

``````function rgb2grayscale(
image,
canvas,
weightedAverage
) {
const context = canvas.getContext('2d');

const imageWeight = image.width;
const imageHeight = image.height;

canvas.width = imageWeight;
canvas.height = imageHeight;

context.drawImage(image, 0, 0);

let pixels = context
.getImageData(
0,
0,
imageWeight,
imageHeight
);

for (let y = 0; y & lt; pixels.height; y++) {
for (let x = 0; x & lt; pixels.width; x++) {
const i = (y * 4) * pixels.width + x * 4;

let red = pixels.data[i];
let green = pixels.data[i + 1];
let blue = pixels.data[i + 2]

const average = (red + green + blue) / 3;
const luminance = 0.2126 * red +
0.7152 * green +
0.0722 * blue;

red = weightedAverage ? luminance : average;
green = weightedAverage ? luminance : average;
blue = weightedAverage ? luminance : average;

pixels.data[i] = red;
pixels.data[i + 1] = green;
pixels.data[i + 2] = blue;
}
}
context
.putImageData(
pixels,
0,
0,
0,
0,
pixels.width,
pixels.height
);
}``````

### References

http://papugi.demensdeum.repl.co/

### Thanks

Thanks to Aleksei Matiushkin (https://twitter.com/mudasobwa) for showing Rosetta Code

## How to run CSGO on Macbook M1

If you get error SDL_GetDesktopDisplayMode_REAL on Macbook M1 CSGO launch, then next instructions is for you.
1. Add launch options in Steam for CSGO:
`-w 1440 -h 900 -fullscreen`
2. Launch CSGO via Steam
3. Press Ignore or Always Ignore on SDL_GetDesktopDisplayMode_REAL error window
4. Enjoy!

## Turing Bombe

In 1936, the scientist Alan Turing in his publication “On Computable Numbers, With An Application to Entscheidungsproblem”describes the use of a universal computing machine that could put an end to the problem of decidability in mathematics. As a result, he comes to the conclusion that such a machine would be nothing could solve correctly, if the result of her work would be inverted and looped on itself.It turns out that * ideal * antivirus cannot be created, * ideal * tile layer too, a program that suggests ideal phrases for your crash, etc. Paradox, sir!

However, this universal computing machine can be used to implement any algorithm, which was used by British intelligence, hiring Turing and allowing to create a “Bombe” machine for decrypting German messages during the Second World War.

The following is an example of OOP modeling a single-tape calculator in Dart, based on the original document.

The Turing machine consists of a tape divided into sections, each section contains a symbol, symbols can be read or written. Film class example:

``````class MapInfiniteTape implements InfiniteTape {
final _map = Map<int, String>();

return _map[at] ?? "";
}

void write({required String symbol, required int at}) {
_map[at] = symbol;
}
}
``````

There is also a “scanning square”, it can move along the film, read or write information, in modern language – a magnetic head. Magnetic head class example:

``````class TapeHead {
int _index = 0;
InfiniteTape _infiniteTape;

String next() {
_index += 1;
move(to: _index);
return output;
}

String previous() {
_index -= 1;
move(to: _index);
return output;
}

void move({required int to}) {
this._index = to;
}

}

void write(String symbol) {
_infiniteTape.write(symbol: symbol, at: this._index);
}

int index() {
return _index;
}
}
``````

The machine contains “m-configurations” by which it can decide what to do next. In modern parlance, states and state handlers. State handler example:

``````class FiniteStateControl {
FiniteStateControlDelegate? delegate = null;

void handle({required String symbol}) {
if (symbol == OPCODE_PRINT) {
final argument = delegate?.nextSymbol();
print(argument);
}
else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) {
final to = int.tryParse(delegate!.nextSymbol())!;
final value = new Random().nextInt(to);
delegate!.nextSymbol();
delegate!.write(value.toString());
}
else if (symbol == OPCODE_INPUT_TO_NEXT) {
delegate?.nextSymbol();
delegate?.write(input);
}
else if (symbol == OPCODE_COPY_FROM_TO) {
final currentIndex = delegate!.index();

и т.д.
``````

After that, you need to create “configurations”, in modern language these are operation codes (opcodes), their handlers. Example opcodes:

``````const OPCODE_STOP = "stop";
const OPCODE_PRINT = "print";
const OPCODE_INCREMENT_NEXT = "increment next";
const OPCODE_DECREMENT_NEXT = "decrement next";
const OPCODE_IF_PREVIOUS_NOT_EQUAL = "if previous not equal";
const OPCODE_MOVE_TO_INDEX = "move to index";
const OPCODE_COPY_FROM_TO = "copy from index to index";
const OPCODE_INPUT_TO_NEXT = "input to next";
const OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = "generate random number from zero to next and write after";
``````

Don’t forget to create an opcode and a breakpoint handler, otherwise you won’t be able to prove or not prove (sic!) The resolution problem.

Now, using the “mediator” pattern, we connect all the classes in the Turing Machine class, create an instance of the class, record the programs through the tape recorder, load the cassette and you can use it!

For me personally, the question remained interesting, what was primary – the creation of a universal calculator or the proof of the “Entscheidungsproblem” as a result of which, as a by-product, a calculator appeared.

### Cassettes

For the sake of entertainment, I recorded several cassette programs for my version of the car.

Hello World

``````print
hello world
stop``````

Считаем до 16-ти

``````increment next
0
if previous not equal
16
copy from index to index
1
8
print
?
move to index
0
else
copy from index to index
1
16
print
?
print
Finished!
stop``````

The most interesting challenge was writing Quine a program that prints its source code for a single tape machine. For the first 8 hours it seemed to me that this problem could not be solved with such a small number of opcodes, but after only 16 hours it turned out that I was wrong.

Implementation and examples of cassettes, sources below.

https://gitlab.com/demensdeum/turing-machine

## Writing stuff in Assembly for Sega Genesis #5

In this post I will describe the process of reading the joystick, changing the position of the sprite, horizontal flip, the Sega Genesis emulator and potentially the console itself.

Reading of clicks, processing of “events” of the shogi joystick is carried out according to the following scheme:

1. Request a combination of bits of pressed buttons
2. Reading the bits of pressed buttons
3. Processing at the level of game logic

To move the skeleton sprite, we need to store the variables of the current position.

### RAM

The variables of the game logic are stored in RAM, so far people have not come up with anything better. Let’s declare the addresses of the variables, change the rendering code:

``````skeletonXpos = \$FF0000
skeletonYpos = \$FF0002
frameCounter = \$FF0004
skeletonHorizontalFlip = \$FF0006

move.w #\$0100,skeletonXpos
move.w #\$0100,skeletonYpos
move.w #\$0001,skeletonHorizontalFlip

FillSpriteTable:
move.l #\$70000003,vdp_control_port
move.w skeletonYpos,vdp_data_port
move.w #\$0F00,vdp_data_port
move.w skeletonHorizontalFlip,vdp_data_port
move.w skeletonXpos,vdp_data_port
``````

As you can see, the address available for work starts with 0xFF0000, and ends at 0xFFFFFF, in total we have 64 KB of memory available. Skeleton positions are declared at skeletonXpos, skeletonYpos, horizontal flip at skeletonHorizontalFlip.

By analogy with VDP, work with joypads occurs through two ports separately – the control port and the data port, for the first it is 0xA10009 and 0xA10003 so-but. When working with a joypad, there is one interesting feature – first you need to request a combination of buttons for polling, and then, after waiting for the update via the bus, read the necessary clicks. For the C / B buttons and the cross, this is 0x40, an example is below:

``````ReadJoypad:
nop ; bus sync
nop ; bus sync
rts
``````

In register d2, the state of the buttons pressed, or not pressed, in general, what was requested through the date port, will remain. After that, go to the Motorola 68000 register viewer of your favorite emulator, see what the d2 register is, depending on the keystrokes. In a smart way, you can find out in the manual, but we do not believe a word. Further processing of pressed buttons in register d2

``````HandleJoypad:
cmp #\$FFFFFF7B,d2; handle left
beq MoveLeft
cmp #\$FFFFFF77,d2; handle right
beq MoveRight
cmp #\$FFFFFF7E,d2; handle up
beq MoveUp
cmp #\$FFFFFF7D,d2; handle down
beq MoveDown
rts``````

Of course, you need to check individual bits, not whole words, but for now it will do. Now the simplest thing is left – to write handlers for all events of movement in 4 directions. To do this, we change the variables in RAM, and start the repainting procedure.

Example for moving left + changing horizontal flip:

``````MoveLeft:
move.w skeletonXpos,d0
sub.w #1,d0
move.w d0,skeletonXpos
move.w #\$0801,skeletonHorizontalFlip
jmp FillSpriteTable``````

After adding all the handlers and assemblies, you will see how the skeleton moves and rotates around the screen, but too fast, faster than Sonic the hedgehog itself.

### Not so fast!

To slow down the speed of the game loop, there are several techniques, I chose the simplest and not affecting work with external ports – counting a digit through a register until it becomes zero.

An example of a slowing loop and a game loop:

``````StartWaitFrame:
move.w #512,frameCounter
WaitFrame:
move.w frameCounter,d0
sub.w #1,d0
move.w d0,frameCounter
dbra d0,WaitFrame
GameLoop:
jmp GameLoop
``````

After that, the skeleton runs slower, which is required. As far as I know, the most common variant of “slowing down” is counting the vertical sync flag, you can count how many times the screen has been rendered, thus binding to a specific fps.

## Writing stuff in Assembly for Sega Genesis #4

In this post I will describe how to draw sprites using the Sega Genesis VDP emulator.
The process for rendering sprites is very similar to rendering tiles:

2. Upload parts of 8×8 sprites to VRAM
3. Filling the Sprite Table in VRAM

For example, let’s take a skeleton sprite with a sword 32×32 pixels

### CRAM

Let’s use ImaGenesis to convert it to CRAM colors and VRAM patterns for assembler. After that we get two files in asm format, then we rewrite the colors to the word size, and the tiles must be put in the correct order for rendering.
Interesting information: you can switch the VDP auto-increment through register 0xF to word size, this will remove the address increment from the CRAM color fill code.

### VRAM

The shogi manula has the correct tile order for large sprites, but we’re smarter, so we’ll take the indexes from the blog ChibiAkumas , let’s start counting from index 0:

0 4 8 12

1 5 9 13

2 6 10 14

3 7 11 15

Why is everyone upside down? And what do you want, because the prefix is ​​Japanese! It could have been from right to left!
Let’s manually change the order in the sprite asm file:

``````Sprite:
dc.l	\$11111111	; Tile #0
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111	; Tile #4
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111	; Tile #8
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111111
dc.l	\$11111122
dc.l	\$11111122
dc.l	\$11111166
dc.l	\$11111166	; Tile #12
dc.l	\$11111166
dc.l	\$11111166
и т.д.
``````

Load the sprite like regular tiles / patterns:

``````SpriteVRAM:
lea Sprite,a0
move.l #\$40200000,vdp_control_port; write to VRAM command
move.w #128,d0 ; (16*8 rows of sprite) counter
SpriteVRAMLoop:
move.l (a0)+,vdp_data_port;
dbra d0,SpriteVRAMLoop
``````

To draw the sprite, it remains to fill the Sprite Table

### Sprite Table

The sprite table is filled in VRAM, the address of its location is put in the VDP register 0x05, the address is again tricky, you can see it in the manual, an example for the F000 address:

``````dc.b \$78 ; 0x05:  Sprite table at VRAM 0xF000 (bits 0-6 = bits 9-15)
``````

Ok, now let’s write our sprite to the table. To do this, you need to fill in the data “structure” consisting of four words. You can find a binary description of the structure in the manual. Personally, I made it easier, the sprite sheet can be edited manually in the Exodus emulator.

The structure parameters are obvious from the name, for example XPos, YPos – coordinates, Tiles – starting tile number for drawing, HSize, VSize – sprite sizes by adding 8×8 parts, HFlip, VFlip – hardware horizontal and vertical sprite rotations.

It is very important to remember that sprites can be off-screen, this is the correct behavior. unloading off-screen sprites from memory is quite a resource-intensive task.
After filling in the data in the emulator, they need to be copied from VRAM at 0xF000, Exodus also supports this feature.
By analogy with drawing tiles, first we turn to the VDP control port to start recording at 0xF000, then write the structure to the data port.
Let me remind you that the description of VRAM addressing can be read in the manual, or in the blog Nameless Algorithm .

In short, VDP addressing works like this:
[..DC BA98 7654 3210 …. …. …. ..FE]
Where hex is the position of the bit in the desired address. The first two bits are the type of the requested command, for example 01 – write to VRAM. Then for the address 0XF000 it turns out:
0111 0000 0000 0000 0000 0000 0000 0011 (70000003)

As a result, we get the code:

``````SpriteTable:
move.l #\$70000003,vdp_control_port
move.w #\$0100,vdp_data_port
move.w #\$0F00,vdp_data_port
move.w #\$0001,vdp_data_port
move.w #\$0100,vdp_data_port
``````

After that, the skeleton sprite will be displayed at coordinates 256, 256. Cool yes?