September 2024, coding trails

“We don’t need no education” — The Wall

In The Word we see that the words in a language models can be visualized as constellations with precise mathematical relations between each other. And each constellation can also be thought of as a “thinking” entity which takes in other “context” words and redirects to the next word. (Adding itself to the context)

The code to navigate the model and generate content is pretty straightforward, and is not very difficult to develop or run, but the model itself is nothing short of amazing! It is something that a thousand programmers could not have programmed in a thousand years. We haven’t even begun to scratch the surface of understanding what is contained in it. So how did we manage to make these language models?

If you have a clear idea of the result you want, but have no training data, you can use “evolution” to teach neural networks. This is the method used for creating bots to beat Super Mario Brothers. The screen is the input, and controller actions are the output. The “hidden” layer is treated as DNA. The DNA is mutated, bred together, and divided into species. Over many generations, only the fittest DNA is kept, and the rest go extinct. The same principle can be used for evolving computer programs. I plan on using my BrainF*ck interpreter to create a laboratory to play around with this concept in PRISM, and I will write about it in depth.

Fortunately, with many zetabytes of content on the Internet, there is no shortage of content to train our model. Where do we start? First you create an hyper-dimensional void, and add all your words. At this point we don’t have the faintest clue where the words should go, however. And we don’t want to place them all at the origin, because that will introduce a bias towards the origin point. So we “explode” the words out, selecting a random hyper-dimensional point for each word.

Next we start working our way through the entire Internet! For every book ever written, every blog post, and every angry rant posted on a forum, we run it through our model nudging the stars to their correct place in the universe. This is where the hard part comes into play. You provide the inputs and the outputs, and use “backpropogation” to turn the knobs in the hidden layer of the neural network. This involves complex coding and advanced mathematics to pull off—people have written thesis papers on the topic, so I won’t be writing about it 😀

So, 64 ZB and a billion dollars later, you get ChatGPT-5. I said we don’t know what’s in it, but we actually do. It is the synthesis of the entirety of human knowledge, organized into a nice, compact mathematical formula.

With this massive undertaking accomplished, the doors are now open to a new form of training. There is no need to start back from the beginning. AI can be tasked with training other AI, which can in turn train other AI… and on and on. What took years to accomplish can now be done in a matter of hours.

Solutions such as OpenAI have thousands of dimensions, vastly exceeding the point of diminishing returns. Reducing dimensions down to several hundred can be 90% as effective, allowing it to run on inexpensive hardware. Stanford’s Alpaca can be trained in an hour and a half and run on a $300 computer! Llama 7B has even been successfully installed and run on a Raspberry Pi!

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Setup

In LeetCode, the linked list is provided for you. We’ll have to add that ourselves. To make the test cases more readable, we will also add a ToString to print it out, and a factory to easily create it from an array of integers.

class ListNode;
begin
    constructor Init(Value : Integer, Next : ListNode := Nil);
    begin
       this.Value := Value;
       this.Next  := Next;
    end

    function ToString() : String;
    begin
        var ToString := Str('[') + Value;
        
        var Current := Next;
        while Current <> Nil do
        begin
           ToString := ToString + ', ' + Current.Value;
           Current := Current.Next;
        end
        ToString := ToString + ']';

        Exit ToString;
    end
end

function LinkedList(Values : Array of Integer) : ListNode;
var 
   Head, Current : ListNode;

begin
    if Values.Length = 0 then raise 'Must contain at least one node!'; 

    Head := ListNode(0);
    Current := Head;

    for var I := Iterator(Values); I.HasNext() do
    begin
        Current.Next := ListNode(I.Next());
        Current := Current.Next;
    end
    Exit Head.Next;
end

Tests

With that taken care of, we can add the 3 example scenarios as test cases:

test 'Case #1';
begin
    var Sum := AddTwoNumbers([2, 4, 3], [5, 6, 4]);

    AssertEqual('[7, 0, 8]', Sum.ToString());
end

test 'Case #2';
begin
    var Sum := AddTwoNumbers([0], [0]);

    AssertEqual('[0]', Sum.ToString());
end

test 'Case #3';
begin
    var Sum := AddTwoNumbers([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]);

    AssertEqual('[8, 9, 9, 9, 0, 0, 0, 1]', Sum.ToString());
end

Solution

To get a O(n) solution, you just loop through the two linked lists at the same time, and add the two together. If the first or second node is Nil you set that value to 0.

Probably the hardest part of this problem is carrying to 10’s place. You can use division to get the value, and the mod operator to get the carry. The tricky part comes in modifying the while loop to make sure you continue till carry value is gone, even if it goes beyond both linked lists.

Note: it makes the solution easier by creating a dummy head, and just returning the Next property.

function AddTwoNumbers(List1, List2: ListNode) : ListNode;
var 
   Head, Current : ListNode;
   
   First, Second : Integer;
   Sum, Carry    : Integer := 0;

begin
    Head := ListNode(0, Nil);
    Current := Head;

    while List1 <> Nil Or List2 <> Nil Or Carry <> 0 do
    begin
       First  := List1 = Nil ? 0 : List1.Value;
       Second := List2 = Nil ? 0 : List2.Value;

       Sum := First + Second + Carry;
       Carry := Sum / 10;

       Current.Next := ListNode(Sum % 10);
       Current := Current.Next;

       List1 := List1?.Next;
       List2 := List2?.Next;
    end
    Exit Head.Next;
end

**********

Bonus

Using operator overloading the code becomes more readable:

operator + (Other : ListNode) : ListNode;
begin
   Exit AddTwoNumbers (this, Other);
end

Now the code looks like LinkedList([1, 2, 3]) + LinkedList([4, 5, 6]).

Bonus #2

In an interview the other day I had the good old “reverse a linked list” coding question, in Java of course, but here is the equivalent in Algol-24 😀

/// Add to ListNode class.
///
function Reverse() : ListNode;
var
    Current, Previous, Next : LinkedNode := Nil;

begin
    Current := this;

    while Current <> Nil do
    begin
        Next := Current.Next;
        Current.Next := Previous;
            
        Previous := Current;
        Current := Next;
    end
    Exit Previous;
end 

test 'Reverse a linked list';
begin
    var TheList := LinkedList([2, 4, 3]);

    var Sum := TheList.Reverse();
    AssertEqual('[3, 4, 2]', Sum.ToString());
end

The Big Bang

Add Two Numbers

Setup

Tests

Solution

Bonus

Bonus #2

Archives for September 2024

Setup

Tests

Solution

Bonus

Bonus #2