A short update on GBDTE presentation.

The die is cast. I set the date for my presentation on Gradient Boosted Decision trees. It's Jan 15. I'm aiming for a 45 minutes presentation, so like 30 slides to make. The timeline isn’t actually tight, but there’s no opportunity to do nothing either.

So I decided to stop here, where I am now, and work on the presentation. The current point is:
🌳there is an efficient multithreaded Golang implementation with python bridge
🌳there is a synthetic MSE dataset
🌳there is a synthetic LogLoss dataset

datasets demonstrate that the model is working and can handle hundreds of thousands of records

The crazy picture is about my predecessors:
🌳2017 LinXGBoost: Extension of XGBoost to Generalized Local Linear Models arxiv
🌳2019 Gradient Boosting with Piece-Wise Linear Regression Trees (GBDT-PL) — IJCAI arxiv
🌳2023 Fast Linear Model Trees by PILOT arxiv
🌳2024 PINE / PINEBoost: Efficient Piecewise-Linear Trees for Gradient Boosting arxiv

I started to think about them because there is quite an interesting thing. There are papers in which the authors try to mix extrapolating and interpolating features. My point is that it is not a good idea, because it breaks a fundamental idea behind this method: group objects with one type of feature and capture trends with another.

My inadvertent experiment demonstrated that the performance drops when you do it. And I think I know how to explain why.

the point of no return has been crossed

🔪The Rubicon has been crossed.
🔪We've crossed the point of no return.
🔪There’s no turning back now.
🔪The die is cast.
🔪The bridge behind us has been burned.

So, except "The die is cast" expressions are quite similar to one we use in Russian.

sin(a+b), cos(a+b)

Hello everyone!

Today, while doing my dishes, I suddenly realized that sin and cos of a sum can be derived through the consecutive matrix multiplication. But I definitely remember that in school our teacher derived it through the Pythagorean theorem. Can anyone explain why?

P.S. I honestly think that in school sin(a+b) and cos(a+b) should be axiomatic basis, but if, suddenly, someone wants to derive it, what it the best way to do it?

Всем привет!

Сегодня, перемывая посуду, я внезапно обнаружил что косинус и синус суммы выводятся из последовательного применения операции поворота координат. Но я абсолютно точно помню что в школе эту формулу выводили из теоремы Пифагора. У кого-нибудь есть идеи, почему?

З.Ы. На самом деле я считаю что эти формулы в школе нужно тупо выучить наизусть и выводить из них всю остальную тригонометрию. Но если уж решили выводить, то как лучше?

Heteronym of the day

SOW

🐷 noun: "female pig", sound: /saʊ/
🐷 verb: "to plant seeds", sound: /soʊ/

Sunflower achievement

We have already started to discuss multidrone programming. I applied this technique to get the "Sunflower" achievement. I'm not quite happy with the code yet, but here we are: it works.

code - code to get this achievement
doc - crucial functions

I want to clean up this code and then I'll post a more thorough explanation of how it works.

MapReduce in The Farmer Was Replaced

Code discussion. Part I.

27 years ago Google was born. One of its key ideas was PageRank – a “credibility” score for a web page. (the paper) To compute it quickly, you need a lot of computational power. One option is to build a specialized supercomputer, but Google as a company rejected that path. Instead, they decided to use large arrays of commodity‑class hardware, connected into a network. You have to carefully orchestrate programs that run on such a platform, and back then writing distributed computation was almost like witchcraft.

In 2004 a new era of distributed computation started – the era of MapReduce platforms (see the paper by Dean and Ghemawat). The idea is simple: split your data into pieces, run the same “map” function in parallel on many machines, then combine (“reduce”) the partial results into one final result.

This post is about adapting that approach to the sunflower‑collection challenge in the game “The Farmer Was Replaced”.

The in‑game task has three stages: prepare the soil, plant sunflowers, harvest. We want to use the 5× bonus, so we try to collect sunflowers in order of measure(): from highest to lower. I’m talking about a late part of the game, when I have a 32×32 field and 32 drones, so I can assign one drone to each column or row.

I wanted a tiny “framework” to assign tasks to drones and run them in parallel. Because we take measurements, we also need to collect data from different drones and merge it. The core of this framework is the function drone_map_reduce from the script.

The function drone_map_reduce takes three parameters:

⌖ objects – things to process
⌖ f_map – a function that processes a batch of objects
⌖ f_red – a reducer function that combines results from each batch into one big result

GitHub reference

The drone API we rely on:

⌖ spawn_drone(f) – starts a drone running function f and returns a drone id
⌖ a drone “disappears” when f finishes
⌖ wait_for(drone_id) – waits for the drone to finish and returns its result

First we create slots for drones and distribute tasks between them:

def drone_map_reduce(objects, f_map, f_red):
    drone_jobs = []

    for _ in range(max_drones()):
        drone_jobs.append([])

    ind = 0
    for q in objects:
        drone_jobs[ind % len(drone_jobs)].append(q)
        ind += 1

Now each element in drone_jobs is a batch of work for one drone (or for the main thread).

Then we start the drones and also process some batches in the main thread:

    results = []
    drones = []

    while drone_jobs:
        while drone_jobs and num_drones() < max_drones():
            current = drone_jobs.pop()
            drones.append(spawn_drone(f_map(current)))
        if drone_jobs:
            current = drone_jobs.pop()
            results.append(f_map(current)())

After that we collect all results from the drones:

    for current_drone in drones:
        results.append(wait_for(current_drone))

And finally we combine everything into one result using f_red:

    reduced = None

    for r in results:
        if reduced is None:
            reduced = r
        else:
            reduced = f_red(reduced, r)

    return reduced

A few important details:

⌖ To create a valid drone job, f_map expects a list of the same type of elements that you store in objects.
⌖ We create up to max_drones() batches, so in the inner loop we just spawn drones until num_drones() reaches max_drones().
⌖ The code still works when the number of tasks is less than the number of drones (for example, with set_world_size(3)); some batches just end up empty.
⌖ If your drone function doesn’t return anything (None) and you don’t care about results, you can pass a dummy reducer like no_reduce that ignores its arguments. Or even just None value for reducer function because it will be never called.

Next time: how to build actual game logic on the top of this instrument.

GBDTE presentation. Unstable class.

I’m working now on a presentation for my upcoming public talk. Here’s a picture that illustrates a small but telling idea: an applicant with exactly three unique phone numbers in their applications looked suspicious in 2014, neutral in 2015, and honest in 2016.

Word of the day

I’m in ɔ of this world.
Three letters → one ɔ.

Competitive programming guides.

When somebody asks about best guides for competitive programming, my first reaction is:
* A. Shen: "Programming: theorems and problems"
* Cormen Leiserson Rivest Stein: «Introduction to Algorithms»

Web:
* max algo - static site with a lot of interesting and useful algorithms
* sirius pythonic algo courses
* sirius c++ algo courses

New for me resources:
* competitive programming chectsheet https://usaco.guide/
* demos for algorithms https://t.me/python_ready/1986

MapReduce in The Farmer Was Replaced

Code discussion. Part II.

In the previous post we discussed the code which uses map reduce approach to farm sunflowers. We reviewed the drone_map_reduce(objects, f_map, f_red) function line-by-line and realized that:
👉🏻 objects is an array of tasks descriptions
👉🏻 f_map - a factory function that creates a task from its description
👉🏻 f_red - reducer function, merges results into one big result if necessary

Today we are going to discuss how this framework applies to solving three sunflower tasks: till the entire field, plant sunflowers, harvest sunflowers with x5 bonus.

Till the field

def till_field():
 columns = []

 for x in range(get_world_size()):
  columns.append(x)

 def till_column(columns):
  def g():
   for q in columns:
    for p in range(get_world_size()):
     nav(q, p)
     till_soil()
  return g

 drone_map_reduce(columns, till_column, no_reduce)

Let's check this code. First, we prepare a list of columns to till. Then we prepare the factory function till_column, which takes a list of columns to process and returns... Attention!!! - a function to till all these columns. It uses helper functions: nav for navigation and till_soil for tilling grassland into Soil (it doesn't till it back). We use quite an interesting trick - nested function g inside the function till_column. It captures the columns variable and therefore is self-aware, it can run with no parameters. In "normal" programming it is like "partial" function which binds parameters with values. This function is called inside the spawn_drone function and determines the drone's actions and its lifetime.

Plant sunflowers

def plant_sunflowers():
  drone_jobs = []
  
  for q in range(get_world_size()):
    drone_jobs.append(q)

  def drone_job(columns):
    def g():
      heights = dict()
      for q in columns:
        for p in range(get_world_size()):
          nav(q, p)
          plant(Entities.Sunflower)
          heights[(q, p)] = measure()
      return heights
    return g

  def reduce_hights(h1, h2):
    for k in h2:
      h1[k] = h2[k]
    return h1
  
  return drone_map_reduce(drone_jobs, drone_job, reduce_hights)

The first part is quite familiar - forming a list of columns to process. The drone_job function is again a factory of functions. Again, these functions are quite similar to previous till_column. But now we have an interesting detail. Each sunflower has its own petal count and we are to use these petals to determine which sunflower to collect first. So, after planting a sunflower we call the measure() function and put its result into a dictionary:

heights[(q, p)] = measure()

Keys of this dictionary are tuples of coordinates and the values - the numbers of petals.

And last, but not least detail: reduce_heights function. It takes two dictionaries as parameters, updates the first with the values from the second and returns this first dictionary. Here the logic of the whole affair is a little bit complicated and I intentionally did it. In my first version the code was clearer: every time I created a fresh dictionary and filled it with the content of two parameters. But in this case drone suddenly stopped for a noticeably long time. It turned out that the price of clean code was quadratic complexity of the algorithm. Therefore I changed it and now you see messier, but faster code.

I'm not sure that one post can contain so much code, so let's use links to github. Starting from this line I convert a dictionary from format (x,y) -> h to h -> [(x1, y1), (x2, y2), ...]. For each height of sunflower now we have a list of cells with sunflowers of this height in these cells.

Finally , we use our map_reduce approach to collect all sunflowers in a correct order. "gather_all" is a factory function for this task.

Sunflowers. MapReduce.

P.S. While writing this post, I realized this algorithm can be improved. There’s some unnecessary work: first I build a (x, y) → h dictionary, and then I rebuild it into h → [(xi, yi), …]. We can generate the latter format from the start — that’s the first thing to try.

Second: we can water the tallest sunflowers first to reduce waiting time.

If this post gets 10 🔥 reactions, I’ll write one more article with these improvements. Otherwise — it’s homework 😄

Sine cosine machine

I’m a physicist, and for me sine and cosine are first and foremost laws of motion: the horizontal and vertical shadows of a pin on the edge of a rotating disc, cast on a wall.

Some time ago I decided to create a sine–cosine machine to demonstrate this idea. One evening of work in Blender, and here we are.

The problem was that the mechanism tended to stick. A piece of sandpaper and a bit of silicone oil pretty much solved it. The machine is lost now—though I can probably find the 3D files and print it again.

Word of the day: spendthrift

Spend means “to give away”, thrift — “to keep”.
If you know these words, spendthrift may sound like “keep your money while you can”.

And that would be totally wrong.

Spendthrift means to spend money carelessly.

Qbasic and polar coordinates

I think it's quite a controversial take. Progress gives us far more powerful computers, instruments nobody could imagine 5 years ago. And still qbasic feels like the best way to start writing small programs.

To make the video I used this web page .

Vibe-coding version:
* prompt
* c++ code

Algorithm Flood

In comments you can bring interesting programming tasks and discuss it

De Morgan's rule

One of the subscribers brought me a problem. Roughly, it sounds like this:
“Read standard input and count strings. Stop counting when the user enters конец or КОНЕЦ.”
The question was how to write the loop condition.

It looks trivial, but I think I can easily write a post (or two) around this question.

First, let’s try the straightforward approach with an exit condition:

n = 0
while True:
    s = input()
    if s == "конец" or s == "КОНЕЦ":
        break
    n += 1
print(n)

Here we use the break keyword, which exits the loop and skips the rest of the loop body.
So we know that we reach n += 1 only if s differs from the end-of-input marker.

Personally, I don’t like these break and continue guys — they always look like goto in disguise.

Let’s try to remove the if … break construction and move the condition into the while.

To do this, we need to invert the exit condition and write down the continuation condition instead.

Formally, the exit condition is:

s == "конец" or s == "КОНЕЦ"

So the continuation condition is:

not (s == "конец" or s == "КОНЕЦ")

And here comes De Morgan’s rule.

Let’s look at our comic strip with almost Rescue Rangers trying to find a brilliant. They know that Fat Cat hid it inside one of Nimnul’s robots — the one that is round and green. But finding such a robot in a crowded laboratory is hard.

So Gadget uses her invention and reverses the polarity. Now the diamond is inside all robots except the round and green one.

The team plays it safe and reasons like this:
if a robot is either not green or not round, we grab it.

As you can see, they find the diamond — using De Morgan’s rule.

This is important because when you write programs, you constantly switch between:

👉exit conditions
👉continuation conditions

The practical rule is simple (for basic cases):

To negate a logical expression, negate each term and swap or ↔️ and.

Let’s apply it to our example.

n = 0
s = input()
while s != "конец" and s != "КОНЕЦ":
    n += 1
    s = input()

Everything has its price.
Now we have to write s = input() twice.

But at least we got rid of break.