Numerical solution:
1038733707Programs:
A naive
T in Python is:from collections import deque
def T(a: int, b: int, N: int) -> int:
total = a
q = deque([a] * (a - 1))
is_a = False
for i in range(N - 1):
cur = q.popleft()
total += cur
q.extend([a if is_a else b] * cur)
is_a = not is_a
return total
assert T(2, 3, 10) == 25
assert T(4, 2, 10**4) == 30004
assert T(5, 8, 10**6) == 649987122332223332233 which has 14 digits.Maybe if
T is optimized enough, then we can just bruteforce over the ~40k possible sum ranges 2 to 223. 1 second would mean 14 hours to do them all, so bruteforce but doable. Otherwise another optimization step may be needed at that level as well: one wonders if multiple sums can be factored out, or if the modularity can of the answer can help in a meaningful way. The first solver was ecnerwala using C/C++ in 1 hour, so there must be another insight missing, unless they have access to a supercomputer.The first idea that comes to mind to try and optimize
T is that this is a dynamic programming, but then the question is what is the recurrence relation.The sequence appears to be a generalization of the Kolakoski sequence but to numbers other than 1 and 2, also known as the Generalized Kolakoski sequence.
maths-people.anu.edu.au/~brent/pd/Kolakoski-ACCMCC.pdf "A fast algorithm for the Kolakoski sequence" might provide the solution, the paper says:and provides exactly a recurrence relation and a dynamic programming approach.
www.reddit.com/r/dailyprogrammer/comments/8df7sm/20180419_challenge_357_intermediate_kolakoski/ might offer some reference implementations. It references a longer slide by Brent: maths-people.anu.edu.au/~brent/pd/Kolakoski-UNSW.pdf
www.reddit.com/r/algorithms/comments/8cv3se/kolakoski_sequence/ asks for an implementation but no one gave anything. Dupe question: math.stackexchange.com/questions/2740997/kolakoski-sequence contains an answer with Python and Rust code but just for the original 1,2 case.
github.com/runbobby/Kolakoski has some C++ code but it is not well documented so it's not immediately easy to understand what it actually does. It does appear to consider the m n case however.
Bibligraphy:
- pubs.sciepub.com/tjant/5/4/4/index.html Some Formulas for the Generalized Kolakoski Sequence Kol(a, b) by Abdallah Hammam. Maybe these identities could be useful.
People who do cool open tech stuff when don't need money anymore are awesome:
- François Chollet, project founder: www.linkedin.com/in/fchollet/ 9 years at Google from 2015 to 2024. He founded ARC while he was still at Google though, so maybe doesn't coun
- Cristiano Calgano from cristianoc/arc-agi-2-abstraction-dataset. Imperial College London researcher who founded a formal verification company and sold it to Facebook where he staid for 7 years
- Benjamin Crouzier from Tufa Labs
Benjamin has a masters in Computer Science and applied ML to quant finance previously, tufalabs.ai/team.html mentions:
From another awesome retired tech bro that does this project for fun.
Cool website tracking the status of varios
Ciro Santilli's fork of ARC-DSL merging all pull requests needed to make tests run again on Ubuntu 25.04.
This interesting repo defines a set of input transformations that can be composed together into programs to generate the solve ARC problems.
It does not appear to have any program synthesis: it only defines the DSL and then provides manual solutions to the problems.
The README is lacking as usual, an overview of the files is:
- dsl.py: defines the transformations as Python functions
- solvers.py: defines solvers for the 400 ARC-AGI-1 training problems
Intended usage to run the solvers seems to be:Unfortunately this blows up on Ubuntu 25.04 on
git clone https://github.com/fchollet/ARC-AGI
cd ARC-AGI
git checkout 399030444e0ab0cc8b4e199870fb20b863846f34
git clone https://github.com/michaelhodel/arc-dsl
cd arc-dsl
git checkout 635de4902a5fb4e376f27333feaa396d3f5dfdcb
python main.pytest_mpapply apparently due to a Python 3.12 issue and the pull request github.com/michaelhodel/arc-dsl/pull/7 has been ignored for more than one year, so the project is largely dead.The rich guy behind Tufa Labs:
- github.com/pinouchon
- pinouchon.github.io
- www.youtube.com/benjamincrouzier He's also a wooden block fanatic. Funnily Ciro Santilli had seen his channel before knowing he was rich. www.youtube.com/watch?v=5HyYyXHSW74 shows probable home and could likely be geolocated.
- tufalabs.ai/team.html describes how he made his money:
Benjamin has a masters in Computer Science and applied ML to quant finance previously.
Unlisted articles are being shown, click here to show only listed articles.