Archives for August 2024

The Word

August 31, 2024 by schildawg Leave a Comment

ἐν ἀρχῇ ἦν ὁ λόγος — Ιωάννης ο αγαπημένος

To understand artificial intelligence, you have to start at the beginning—the word. If you look up a word in a dictionary, it is defined by other words, which are in turn defined by even more words. If you keep repeating this process, you end up with a network consisting of all of the words in a language. You can start at any word in that language and plot a course to any other word.

We tend to think of the relationship between words as being vague or fuzzy, but in fact a language is a precise mathematical model in which distances between words can be measured, angles calculated, and relationships derived using trigonometry and calculus.

A word is a singular point in a hyper-dimensional field. The number of dimensions determine the semantic preciseness of the word. Less than a hundred dimensions and the word loses its precision, like a picture out of focus. If you have more than several hundred dimensions, you start to experience diminishing returns. Three hundred dimensions is sufficient for general purposes, but models exist with several thousand dimensions.

You could think of words as being stars in a vast hyper-dimensional universe. It is possible to conceive of time being the fourth dimension and the multiverse as being the fifth, but if you go beyond that it quickly becomes incomprehensible. But there is a way to visualize it that is easily understandable. A three dimensional object can be drawn on a mostly two dimensional piece of paper. A four dimensional being would appear to us as three dimensional with movement.

If you take the dimensions of a word and divide it into three-dimensional slices and superimpose them on top of each other, you have a constellation of dozens of bright stars and hundreds of faint ones. At the center of gravity of this constellation there is a world, where you can look up into the sky and see millions of other stars, both bright and dim.

If you stand on world “Man” and look up and find the star “King” you can teleport to the same place on world “Woman” and in the exact same place in the sky will be the star “Queen.” Similarly, looking at “Queen” from “King” is the exact same relationship as “Woman” from “Man.” There are profound implications and insights that can be derived from this relationship, which we will explore in future posts.

If you break down a word even further into one-dimension points, we now have hundreds or even thousands of sliders or knobs which can be adjusted from off to completely on. This is the definition of a neuron in a neural network. With this paradigm, we can conceive of a word as being a “brain” which takes in a phrase of words and calculates the next word.

Returning to the analogy of a galaxy of stars, a word is a sector of space into which a space ship enters and the gravitational pull of each of the stars redirects and forwards the ship to the next sector in space. The ship starts out with a prompt, and bounces from word to word until it reaches the end of its journal with a complete response.

You see, a language model is a formula, or a condensed mathematical model of the entirety of human knowledge. The coding necessary to build this model is not complex or even particularly sophisticated. It just required the Internet to exist, and a great deal of time, and a lot of money to train it.

Now that we have the model, it’s easy and relatively inexpensive to copy it in high and low definition. But we don’t know what’s in it. We don’t even understand what all the higher dimensions are. This is, in my opinion “the final frontier.” There are insights to be gleaned in linguistics, psychology, and philosophy. A whole new universe exists which is waiting to be discovered and explored!

Two Sum

August 31, 2024 by schildawg Leave a Comment

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Tests

Let’s start out with the tests:

procedure AssertTwoSum(Input: Array, Target, First, Second: Integer);
begin
    var Result := TwoSum(Input, Target); 
    
    AssertEqual (0, Result[0]); 
    AssertEqual (1, Result[1]);   
end

test '2 7 11 5';
begin
    AssertTwoSum ([2, 7, 11, 15], Target: 9, First: 0, Second: 1); 
end

test '3 2 4';
begin
    AssertTwoSum ([3, 2, 4], Target: 6, First: 1, Second: 2);
end

test '3 3';
begin
    AssertTwoSum ([3, 3], Target: 6, First: 0, Second: 1); 
end

Solution

For each item in the array of integers, loop through the array, comparing if the both values add up to the target, making sure the indexes are not the same.

function TwoSum(Input: Array of Integer, Target: Integer) : Array of Integer;
begin
    for var I := 0; I < Input.Length; I := I + 1 do
    begin
        for var J := 0; J < Input.Length; J := J + 1 do
        begin
            if Input[I] + Input[J] = Target And I <> J then
            begin
                Exit [I, J];
            end
        end
    end
    raise 'Invalid Input!';
end

This is the simplest way to solve the problem, but not the most time efficient. It has a time complexity of O(n²). The time can be reduced by initializing the J loop variable with I, since, if you think about it, these permutations have already been covered.

Let’s run the tests:

Alternate Solution

With a solution in place, and all our tests passing, now we can think of performance. By adding a hash table lookup we can reduce the time complexity to O(n) at the cost of the extra memory that the hash table takes up.

function TwoSum(Input: Array of Integer, Target: Integer) : Array of Integer;
var
   Lookup : Map := Map();

begin
    for var I := 0; I < Input.Length; I := I + 1 do
    begin
        var Value := Input[I];
        var Complement := Target - Value;

        if Lookup.Contains(Complement) then
        begin
            Exit [Lookup.Get(Complement), I];
        end
        Lookup.Put(Value, I);
    end
    raise 'Invalid Input!';
end

Of course, the performance is going to depend on the implementation of the hash table, but for a properly written hash table the lookup should be in constant time regardless of how many keys are in the table.

Replace the implementation, and run the tests again!

World’s Tiniest Language

August 25, 2024 by schildawg Leave a Comment

BrainF*ck is an esoteric language created in 1993 by Swiss physics student Urban Müller. (Don’t blame me, I didn’t come up with the name!) It consists of 8 instructions and is fully Turing-complete. Here is a complete implementation in Algol-24:

var MEMORY_SIZE  := 65535;
var ScreenBuffer := '';

procedure Interpret(Code : String);
var
   Loop := 0;
   Instruction := 0;
   Memory := Buffer(MEMORY_SIZE, 0);

begin
   procedure Find(StartChar, EndChar, Increment);
   begin
      Instruction := Instruction + Increment;
      while Loop > 0 Or Code[Instruction] <> EndChar do
      begin
         if Code[Instruction] = StartChar then
            Loop := Loop + 1;
         else if Code[Instruction] = EndChar then
            Loop := Loop - 1;
         
         Instruction := Instruction + Increment;
      end
   end

   while Instruction < Length(Code) do
   begin
      var Value := Memory.GetValue();

      case Code[Instruction] of
         '>' : Memory.Advance();
         '<' : Memory.Rewind();
         '+' : Memory.SetValue(Value + 1);
         '-' : Memory.SetValue(Value - 1);
         '.' : ScreenBuffer := ScreenBuffer + Char(Value);
         '[' : if Value = 0 then Find('[', ']', 1);
         ']' : if Value <> 0 then Find(']', '[', -1);
      end
      Instruction := Instruction + 1;
   end
end

test 'Run BF Program';
begin
   var Code := '-[------->+<]>-.-[->+++++<]>++.+++++++..+++.[--->+<]>-----.' + 
      '---[->+++<]>.+++[->++++<]>+.++++++++++.+++[->+++<]>+.++++++++++++.-.' + 
      '+++++.----------.+++++.-[->+++++<]>.';
   Interpret(Code);

   AssertEqual('????? ??????????', ScreenBuffer);
end

Coming in 42 lines of code, it is truly tiny! Lamborghini to the first person in the comments who can fill in the value to make the unit test pass 😀

******************************************

If you run this program:

[sierpinski.b -- display Sierpinski triangle
(c) 2016 Daniel B. Cristofani]
++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<]>.>+[>>]>+]

This is the output:

Pretty amazing, huh?