Friday trash
Be careful, the first photo is really a kind of trash. 100 kilometers north of Moscow, kids are playing with a dead snake. If your toys were wooden, you were lucky.
Near Zvenigorod there is a bunch of identical houses. I don't know why, but it still looks funny to me. I heard that there is a business around some legislative procedures: before signing a contract, you place some dummy structures on your plot and pay less for registration, or something like that. The next year, all these houses were removed.
Round-leaved sundew. Near the artificial lake Sima.
Be careful, the first photo is really a kind of trash. 100 kilometers north of Moscow, kids are playing with a dead snake. If your toys were wooden, you were lucky.
Near Zvenigorod there is a bunch of identical houses. I don't know why, but it still looks funny to me. I heard that there is a business around some legislative procedures: before signing a contract, you place some dummy structures on your plot and pay less for registration, or something like that. The next year, all these houses were removed.
Round-leaved sundew. Near the artificial lake Sima.
👀2
Implicit Curriculum aka skill graph
Why should I read all these articles? - I asked myself this week, when I suddenly found this diamond.
To explain why I jumped out of my chair, let me tell you about my previous team. It was Schoolbook. My second assignment after I joined it was to figure out how to build, store and edit a skill graph. It is quite an intuitive idea: in order to solve quadratic equations, you have to understand square roots, summation, multiplication and so on. These simple skills are prerequisites. You can represent these dependencies using a DAG (directed acyclic graph). There were a lot of professional teachers who built mathematics and Russian language graphs in our team. While the idea seems quite straightforward and intuitive, its implementation is the opposite of simple and clear. It took me half a year to understand how it should work and how to implement it in a production environment.
But what about the article? It gives a nice landscape of how skills emerge during model training on unstructured internet data. The described articles give important understanding of how skills emerge in large language models, how to evaluate them, how to detect phase transitions in a model and how to find internal representations of skills inside the model.
For me, these findings are very important because they are very close to the bridge between model training and human education. I believe that our brain is just a very complex classical computer and that insights can be transferred from human education practice to machine learning and back. After reading the article, I feel much more confident that the skill graph is a real thing, not just a figment of our teachers' imagination.
There is quite a well-shaped method of model evaluation. Probably, it can be transferred to the realities of educational platforms and give us metrics for educational efficiency.
Why should I read all these articles? - I asked myself this week, when I suddenly found this diamond.
To explain why I jumped out of my chair, let me tell you about my previous team. It was Schoolbook. My second assignment after I joined it was to figure out how to build, store and edit a skill graph. It is quite an intuitive idea: in order to solve quadratic equations, you have to understand square roots, summation, multiplication and so on. These simple skills are prerequisites. You can represent these dependencies using a DAG (directed acyclic graph). There were a lot of professional teachers who built mathematics and Russian language graphs in our team. While the idea seems quite straightforward and intuitive, its implementation is the opposite of simple and clear. It took me half a year to understand how it should work and how to implement it in a production environment.
But what about the article? It gives a nice landscape of how skills emerge during model training on unstructured internet data. The described articles give important understanding of how skills emerge in large language models, how to evaluate them, how to detect phase transitions in a model and how to find internal representations of skills inside the model.
For me, these findings are very important because they are very close to the bridge between model training and human education. I believe that our brain is just a very complex classical computer and that insights can be transferred from human education practice to machine learning and back. After reading the article, I feel much more confident that the skill graph is a real thing, not just a figment of our teachers' imagination.
There is quite a well-shaped method of model evaluation. Probably, it can be transferred to the realities of educational platforms and give us metrics for educational efficiency.
👍3❤1
This media is not supported in your browser
VIEW IN TELEGRAM
The simplest cacti sort
At the last moment I got a request to write the smallest possible program which sorts cacti in The Farmer Was Replaced game.
Here is my version:
Let's work through this solution:
Here I both set the world size to 8 and introduce a new variable n for the world size.
Let's check an interesting idiom:
I introduce the flag disorder_detected and put this flag up before the loop. This way the loop will be executed at least once. Then, at the beginning of the loop, I put it down. It means that if there are no disorders, the field is ready for harvest. Disorders are: absence of cactus, or cacti in the wrong order.
Navigation is very simple. I have two nested loops. The inner loop moves the drone horizontally from left to right. The outer loop moves it vertically. The map is toroidal, therefore the drone appears on the left after crossing the right boundary; similarly, it appears at the bottom after crossing the upper boundary.
When we start the script, the field is empty. So we plant cactus on empty cell and count it as a disorder. Cactus requires Soil, we ensure it with till().
And finally, the main thing:
If our current cactus is higher than its neighbor to the right or above, we swap them. This way each pass of the drone brings more order into the field, and one day the field becomes sorted. On a sorted field no swaps occur, therefore no disorder is detected and the while loop ends.
The drone stops at the left bottom end of the field, and we can call harvest() function, which picks up all cacti with a big bonus.
At the last moment I got a request to write the smallest possible program which sorts cacti in The Farmer Was Replaced game.
Here is my version:
n = 8
set_world_size(n)
disorder_detected = True
while(disorder_detected):
disorder_detected = False
for y in range(n):
for x in range(n):
if get_entity_type() != Entities.Cactus:
if get_ground_type() != Grounds.Soil:
till()
if plant(Entities.Cactus):
disorder_detected = True
if measure() != None and measure(East) != None and measure() > measure(East):
if swap(East):
disorder_detected = True
if measure() != None and measure(North) != None and measure() > measure(North):
if swap(North):
disorder_detected = True
move(East)
move(North)
harvest()
Let's work through this solution:
n = 8
set_world_size(n)
Here I both set the world size to 8 and introduce a new variable n for the world size.
Let's check an interesting idiom:
disorder_detected = True
while(disorder_detected):
disorder_detected = False
...
if plant(Entities.Cactus):
disorder_detected = True
if swap(East):
disorder_detected = True
I introduce the flag disorder_detected and put this flag up before the loop. This way the loop will be executed at least once. Then, at the beginning of the loop, I put it down. It means that if there are no disorders, the field is ready for harvest. Disorders are: absence of cactus, or cacti in the wrong order.
Navigation is very simple. I have two nested loops. The inner loop moves the drone horizontally from left to right. The outer loop moves it vertically. The map is toroidal, therefore the drone appears on the left after crossing the right boundary; similarly, it appears at the bottom after crossing the upper boundary.
if get_entity_type() != Entities.Cactus:
if get_ground_type() != Grounds.Soil:
till()
if plant(Entities.Cactus):
disorder_detected = True
When we start the script, the field is empty. So we plant cactus on empty cell and count it as a disorder. Cactus requires Soil, we ensure it with till().
And finally, the main thing:
if measure() != None and measure(East) != None and measure() > measure(East):
if swap(East):
disorder_detected = True
if measure() != None and measure(North) != None and measure() > measure(North):
if swap(North):
disorder_detected = True
If our current cactus is higher than its neighbor to the right or above, we swap them. This way each pass of the drone brings more order into the field, and one day the field becomes sorted. On a sorted field no swaps occur, therefore no disorder is detected and the while loop ends.
The drone stops at the left bottom end of the field, and we can call harvest() function, which picks up all cacti with a big bonus.
👍2
5. Longest Palindromic Substring
My friend is solving some LeetCode problems now, and I couldn't help but join him.
I know, I know... LeetCode is dead, all this is trash, and we shouldn't solve it. But for now the standards of interviews in Big Tech are settled, and you can, at least, laugh at us, who spend tons of time performing cargo cult rituals.
First of all, it's like a 20-minute problem. In these 20 minutes you have to:
— 0 min
✒️ read the problem statement
✒️ come up with a few test cases - it helps both to understand the problem better and to have test cases for the later testing session
✒️ figure out a working solution for the problem
✒️ explain your approach to the interviewer, give them T=O(...), M=O(...) estimations
✒️ get approval from the interviewer to go on with this solution
- 5 min
✒️ implement your approach
✒️ test your implementation on your test cases
✒️ fix it, if necessary
✒️ check that your T=O(...), M=O(...) are true
- 18 min
✒️ discuss pros and cons
- 20 min
I'm not a quick thinker, and in order to be able to take part in this competition, I thought a lot and came up with some tricks which I want to share. First of all, how to read the statement and how to approach a solution.
"the longest palindromic substring" - if you, like me, start to think "I read really beautiful algorithms which solve it in linear time, what was that book..." - poof, you have already lost this game. Nice thought. But you have to mention it really quickly and move on. What is the real complexity you want to aim at? Check s.length <= 1000 and think about the naive approach. All substrings - n squared, palindrome check - n => n cubed. Rough estimation for time - 10 secs in Python - doesn't look good.
Here you have to recall at least a glimpse of that wonderful algorithm you read about. There was something... about... middle points of palindromes! Let's check. n middle points, linear check => n squared. 0.01s for n = 1000. Sounds promising.
In the program I want to share a trick: decomposition. Of course, you can try to write a program in one long sheet of text. But if you split it into logical parts, it's better for you. Python gives you a great opportunity - iterators. In the function you can generate candidates and then select the best using just the max function.
In order to use just max, we are to be careful about an empty sequence. It is not a case here, because n >= 1. If an empty sequence is possible, default = ... in the max function is your friend.
For odd-length palindromes, candidate generation is quite boring. We start with the trivial one-letter palindrome and extend it, if it is possible. No problem.
Even-length palindromes have a real chance to be absent at all. One more trick - make a step back and set up variables in the previous position before they form a valid even palindrome. Then we can check whether the variables are still in this weird initial position. If they are, we don't have a candidate.
So, here we are. A few tricks, and the problem is solved.
My friend is solving some LeetCode problems now, and I couldn't help but join him.
I know, I know... LeetCode is dead, all this is trash, and we shouldn't solve it. But for now the standards of interviews in Big Tech are settled, and you can, at least, laugh at us, who spend tons of time performing cargo cult rituals.
First of all, it's like a 20-minute problem. In these 20 minutes you have to:
— 0 min
✒️ read the problem statement
✒️ come up with a few test cases - it helps both to understand the problem better and to have test cases for the later testing session
✒️ figure out a working solution for the problem
✒️ explain your approach to the interviewer, give them T=O(...), M=O(...) estimations
✒️ get approval from the interviewer to go on with this solution
- 5 min
✒️ implement your approach
✒️ test your implementation on your test cases
✒️ fix it, if necessary
✒️ check that your T=O(...), M=O(...) are true
- 18 min
✒️ discuss pros and cons
- 20 min
I'm not a quick thinker, and in order to be able to take part in this competition, I thought a lot and came up with some tricks which I want to share. First of all, how to read the statement and how to approach a solution.
"the longest palindromic substring" - if you, like me, start to think "I read really beautiful algorithms which solve it in linear time, what was that book..." - poof, you have already lost this game. Nice thought. But you have to mention it really quickly and move on. What is the real complexity you want to aim at? Check s.length <= 1000 and think about the naive approach. All substrings - n squared, palindrome check - n => n cubed. Rough estimation for time - 10 secs in Python - doesn't look good.
Here you have to recall at least a glimpse of that wonderful algorithm you read about. There was something... about... middle points of palindromes! Let's check. n middle points, linear check => n squared. 0.01s for n = 1000. Sounds promising.
In the program I want to share a trick: decomposition. Of course, you can try to write a program in one long sheet of text. But if you split it into logical parts, it's better for you. Python gives you a great opportunity - iterators. In the function you can generate candidates and then select the best using just the max function.
In order to use just max, we are to be careful about an empty sequence. It is not a case here, because n >= 1. If an empty sequence is possible, default = ... in the max function is your friend.
For odd-length palindromes, candidate generation is quite boring. We start with the trivial one-letter palindrome and extend it, if it is possible. No problem.
Even-length palindromes have a real chance to be absent at all. One more trick - make a step back and set up variables in the previous position before they form a valid even palindrome. Then we can check whether the variables are still in this weird initial position. If they are, we don't have a candidate.
So, here we are. A few tricks, and the problem is solved.
🗿2
3D-printed Dragon Curve
Once I stumbled upon a big glass box in the middle of the App in the Air office. I asked, "What is it?" Turned out it was a 3D printer. An expensive one. I didn't get a believable answer about what this thing was for, but I got permission to play with it.
One day I'll tell you the story of my first 3D model in life - it's epic. Now the small story is about the Dragon Curve. Unfortunately, I'm not educated enough to write the whole story about this object, but it is certainly worth your time if you are a fan of math. The Dragon Curve can be obtained by folding and unfolding a strip of paper, as a recursive procedure, as powering up complex numbers...
This model I created myself by writing a small Python program which calculates the path for a Dragon Curve - the easy part - and makes a 3D model out of it - the slightly trickier part. The output of this program was an .stl file, then conversion to gcode, and finally printing this thing out.
I really appreciate the chance to play with this machine. Thanks, Sergey, Bayram!
Once I stumbled upon a big glass box in the middle of the App in the Air office. I asked, "What is it?" Turned out it was a 3D printer. An expensive one. I didn't get a believable answer about what this thing was for, but I got permission to play with it.
One day I'll tell you the story of my first 3D model in life - it's epic. Now the small story is about the Dragon Curve. Unfortunately, I'm not educated enough to write the whole story about this object, but it is certainly worth your time if you are a fan of math. The Dragon Curve can be obtained by folding and unfolding a strip of paper, as a recursive procedure, as powering up complex numbers...
This model I created myself by writing a small Python program which calculates the path for a Dragon Curve - the easy part - and makes a 3D model out of it - the slightly trickier part. The output of this program was an .stl file, then conversion to gcode, and finally printing this thing out.
I really appreciate the chance to play with this machine. Thanks, Sergey, Bayram!
🔥4👏1
Agentic Programming - navigation
There are fans and haters of LLMs and agents. I'm neither. I'm just working with these tools, much like I used to work with programming languages and other tools.
Little by little, this channel has gathered some notes about using and creating agents, along with some news from this dynamic world.
Feel free to explore it!
If you want to start quickly
These five posts contain most of the ideas.
131 - Vibe Coding Guide tg / web
133 - To those who want to understand agents properly tg / web
143 - How Codex is built tg / web
145 - RAG is dead, long live agentic retrieval tg / web
216 - Integration: Codex and JupyterLab tg / web
Full list
Setup and first experiments
34 - How to set up openai helper in JupyterLab tg / web
77 - The First Vibe Coding Project tg / web
131 - Vibe Coding Guide tg / web
137 - How to vibecode Chizhik-Pyzchic app tg / web
Agents and Codex
133 - To those who want to understand agents properly tg / web
143 - How Codex is built tg / web
174 - Marionette Codex tg / web
194 - Agent personalities tg / web
Retrieval and RAG
145 - RAG is dead, long live agentic retrieval tg / web
166 - Agentic RAG Legal Challenge tg / web
Courses and notes
197 - School of Data Analysis. Agent intensive tg / web
200 - Shad Intensive. Memory. Guardrails. tg / web
201 - Shad Intensive. Evaluation. tg / web
Tools and side applications
168 - A fleeting moment of joy. Vibe analytics. tg / web
216 - Integration: Codex and JupyterLab tg / web
224 - SCI BOT tg / web
There are fans and haters of LLMs and agents. I'm neither. I'm just working with these tools, much like I used to work with programming languages and other tools.
Little by little, this channel has gathered some notes about using and creating agents, along with some news from this dynamic world.
Feel free to explore it!
If you want to start quickly
These five posts contain most of the ideas.
131 - Vibe Coding Guide tg / web
133 - To those who want to understand agents properly tg / web
143 - How Codex is built tg / web
145 - RAG is dead, long live agentic retrieval tg / web
216 - Integration: Codex and JupyterLab tg / web
Full list
Setup and first experiments
34 - How to set up openai helper in JupyterLab tg / web
77 - The First Vibe Coding Project tg / web
131 - Vibe Coding Guide tg / web
137 - How to vibecode Chizhik-Pyzchic app tg / web
Agents and Codex
133 - To those who want to understand agents properly tg / web
143 - How Codex is built tg / web
174 - Marionette Codex tg / web
194 - Agent personalities tg / web
Retrieval and RAG
145 - RAG is dead, long live agentic retrieval tg / web
166 - Agentic RAG Legal Challenge tg / web
Courses and notes
197 - School of Data Analysis. Agent intensive tg / web
200 - Shad Intensive. Memory. Guardrails. tg / web
201 - Shad Intensive. Evaluation. tg / web
Tools and side applications
168 - A fleeting moment of joy. Vibe analytics. tg / web
216 - Integration: Codex and JupyterLab tg / web
224 - SCI BOT tg / web
👍4❤1
Manacher superpowers
These days you are either getting work done or keeping up with contemporary technologies - rarely both. You know, we are living in a strange time. There is an information bubble around agentic programming, and people do crazy things in there. I'm officially out of this race, and I try to stay somewhere in the middle of the bubble — not to spend tons of time on chasing new technologies, but to give a chance to some of them from time to time.
Today two of my vectors of interest became collinear: algorithms and the superpowers skill. Once in a while I'm refreshing some algorithms, and stringology is one of the themes that always slips out of my mind. In the post we discussed the quadratic algorithm for finding the longest palindrome, then I wanted to recall Manacher, which works in T=O(n). That's the kind of skill that lets you build strong features. I decided to try both and created this page.
My old-school self-education approach was to recall the idea, then play with a piece of paper and a pencil, trying to convert the main idea into code. This time I opened Claude in the console, added the superpowers plugin, described the site, and in a few iterations got it. Here you can check the main purpose of this algorithm — finding the longest palindrome in a string, the complexity estimates of the naive O(n*n) and the Manacher O(n) algorithms, the algorithm description, implementations in several languages, and several approaches to implementation.
I keep thinking about Gödel when writing string algorithms like Knuth-Morris-Pratt or Manacher. Because the main trick in them is the "self-reference" property. In KMP you jump to a substring which is a substring of your current substring. In the Manacher algorithm we use the symmetry of the answer, which is inherited from the input data. Namely, if you have a big palindrome "abaCabaDabaCaba", you keep track of the lengths of palindromic substrings, and once you have filled the left part of this array, you can take the already-calculated values as a good approximation for the current value of your array. Wow. It seems I really started to recall this algorithm, and there is a chance that from here on I can start playing with pen and paper.
I'll try to come up with a nice explanation of this algorithm. Meanwhile, feel free to play with the webpage.
These days you are either getting work done or keeping up with contemporary technologies - rarely both. You know, we are living in a strange time. There is an information bubble around agentic programming, and people do crazy things in there. I'm officially out of this race, and I try to stay somewhere in the middle of the bubble — not to spend tons of time on chasing new technologies, but to give a chance to some of them from time to time.
Today two of my vectors of interest became collinear: algorithms and the superpowers skill. Once in a while I'm refreshing some algorithms, and stringology is one of the themes that always slips out of my mind. In the post we discussed the quadratic algorithm for finding the longest palindrome, then I wanted to recall Manacher, which works in T=O(n). That's the kind of skill that lets you build strong features. I decided to try both and created this page.
My old-school self-education approach was to recall the idea, then play with a piece of paper and a pencil, trying to convert the main idea into code. This time I opened Claude in the console, added the superpowers plugin, described the site, and in a few iterations got it. Here you can check the main purpose of this algorithm — finding the longest palindrome in a string, the complexity estimates of the naive O(n*n) and the Manacher O(n) algorithms, the algorithm description, implementations in several languages, and several approaches to implementation.
I keep thinking about Gödel when writing string algorithms like Knuth-Morris-Pratt or Manacher. Because the main trick in them is the "self-reference" property. In KMP you jump to a substring which is a substring of your current substring. In the Manacher algorithm we use the symmetry of the answer, which is inherited from the input data. Namely, if you have a big palindrome "abaCabaDabaCaba", you keep track of the lengths of palindromic substrings, and once you have filled the left part of this array, you can take the already-calculated values as a good approximation for the current value of your array. Wow. It seems I really started to recall this algorithm, and there is a chance that from here on I can start playing with pen and paper.
I'll try to come up with a nice explanation of this algorithm. Meanwhile, feel free to play with the webpage.
👍1
The Water Tower
Earlier I mentioned my old project: a water tower from an ancient DIY pioneer book, which turns 60 years old this year.
I decided that the pyramids were too simple project and I needed to do something a little bit more interesting, so I started a new project in Blender. The second picture shows my models in PrusaSlicer. Now we are waiting for the tower to be finished, and then the experiment will be conducted.
Meanwhile, I found exactly the book I read half of a lifetime ago. You can compare the neuroslop version of the water tower with the real thing. I totally like these black-and-white schemes.
The text is hilarious. "You can use these tin cans, they are the best. Green pea cans worse, but will do." I don't know why, but it sounds... really, I don't know exactly how. Like a magical chant?
Looking forward to pouring water into the tower.
Earlier I mentioned my old project: a water tower from an ancient DIY pioneer book, which turns 60 years old this year.
I decided that the pyramids were too simple project and I needed to do something a little bit more interesting, so I started a new project in Blender. The second picture shows my models in PrusaSlicer. Now we are waiting for the tower to be finished, and then the experiment will be conducted.
Meanwhile, I found exactly the book I read half of a lifetime ago. You can compare the neuroslop version of the water tower with the real thing. I totally like these black-and-white schemes.
The text is hilarious. "You can use these tin cans, they are the best. Green pea cans worse, but will do." I don't know why, but it sounds... really, I don't know exactly how. Like a magical chant?
Looking forward to pouring water into the tower.