Tristan Brindle

Very fortunate to have the one and only Herb Sutter as a guest speaker at C++ London this evening

The Road to Flux 1.0 · tcbrindle flux · Discussion #242 Flux has been around for a couple of years now, and the feedback I get is mostly that people seem to think it's pretty good. I think it's pretty good too! But I'm also aware that the current design...

I've just posted a long old update about my plans for the Flux library, focusing on ease of use, performance and a potential future standardisation effort.

I'm keen to get feedback at this stage so please head on over to Github and leave a comment if you so choose...

github.com/tcbrindle/fl...

This is ChatGPT 4-o, which has been trained on tens of millions of books and articles on every subject under the sun at eye-watering cost. Yet apparently it can't even correctly analyse a few hundred words of english text. And this is supposed to be the future?

Only after I asked it to tell me the specific line numbers on which the alleged misspellings occurred did it "apologise for the earlier error"

I'm a bit of an AI skeptic, but I thought I'd give Copilot a go in VSCode since it's now free. After writing some documentation in Markdown format, I asked it to check for any spelling or grammar mistakes. It insisted, repeatedly, that I had misspelled words *that didn't even appear in the document*

But the 5th of April was last month?

Hey Matt, any truth to the rumour/legend that Jez San demo’d an early version (starring Yoshi) for Nintendo during Starfox 2 development, which then inspired Miyamoto to create Mario 64?

📢 Episode 225 is out! 📢 In this episode, @elbeno.com and I chat with @tristanbrindle.com about plans for @cppnorth.bsky.social, future Flux plans, the slow death of Twitter and more! adspthepodcast.com/2025/03/14/E...

Guessing: no empty structs in C (unlike C++) so 1 is not allowed, but 2 contains a “declaration” so is okay

📢 Episode 224 is out! 📢 In this episode, @elbeno.com and I chat with @tristanbrindle.com about updates in Flux, internal iteration vs external iteration and more! adspthepodcast.com/2025/03/07/E...

📢 Episode 223 is out! 📢 In this episode, @elbeno.com and I chat with @tristanbrindle.com about the recent C++ London meetup, the status of safety in C++ and the future of C++ and whether it is dying ☠️ adspthepodcast.com/2025/02/28/E...

📢 Episode 222 is out! 📢 In this episode, @elbeno.com and I chat with @tristanbrindle.com about graph algorithms resources 📊, tropical semirings 🌴, Stepanov stories 📖, FM2GP 📓, EOP 📙, TV shows & movies 📺 and more! adspthepodcast.com/2025/02/21/E...

Phil Nash, Michael Wong, Lisa Lippincott, Mungo Gill, Timur Doumler, John Lakos, Gašper Ažman and Joshua Berne

An all-star lineup discussing contracts for #cplusplus at C++ London

template <int Size> struct grid_t { std::bitset<Size * Size> data; static constexpr position target{Size - 1, Size - 1}; constexpr auto operator[](this auto& self, position const& pos) { return self.data[pos.y * Size + pos.x]; } }; template <int Size, std::size_t N> auto part1(std::span<position const> bytes) -> int { grid_t<Size> grid{}; flux::for_each(bytes.first<N>(), [&](position const& pos) { grid[pos] = true; }); return dijkstra(graph_t{grid}, {0, 0}).at(grid.target); } template <int Size, std::size_t Skip> auto part2(std::span<position const> bytes) -> position { auto idx = *std::ranges::partition_point( std::views::iota(Skip, bytes.size()), [&](std::size_t n) { grid_t<Size> grid{}; flux::for_each(bytes.first(n + 1), [&](position const& pos) { grid[pos] = true; }); return dijkstra(graph_t{grid}, {0, 0}).contains(grid.target); }); return bytes[idx]; }

I've found the last few days pretty tricky, so #AdventOfCode day 18 was a nice change of pace. Dijkstra's algorithm came up a couple of days ago so I had an implementation ready to go, and then std::partition_point() does all the hard work for part 2. I like this one!

struct robot { vec2 pos; vec2 vel; }; auto const parse_input = [](std::string_view input) -> std::vector<robot> { constexpr auto& regex = R"(p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)\n?)"; return flux::map(ctre::tokenize<regex>(input), [](auto result) { auto [_, px, py, vx, vy] = result; return robot{.pos = {px.to_number(), py.to_number()}, .vel = {vx.to_number(), vy.to_number()}}; }) .to<std::vector>(); }; template <vec2 Bounds> auto const part1 = [](std::vector<robot> robots) -> int64_t { // Move robots for (auto& [pos, vel] : robots) { pos += 100 * (vel + Bounds); pos.x %= Bounds.x; pos.y %= Bounds.y; } // Calculate safety factor std::array<int64_t, 4> quadrants{}; for (auto const& [pos, _] : robots) { if (pos.x < Bounds.x / 2) { if (pos.y < Bounds.y / 2) { ++quadrants[0]; } else if (pos.y > Bounds.y / 2) { ++quadrants[1]; } } else if (pos.x > Bounds.x / 2) { if (pos.y < Bounds.y / 2) { ++quadrants[2]; } else if (pos.y > Bounds.y / 2) { ++quadrants[3]; } } } return flux::product(quadrants); };

A frustratingly vague #AdventOfCode day 14, where we're asked to "find a picture of a Christmas tree" with no absolutely no further details. I solved it by the ingenious method of dumping 10,000 ASCII "pictures" to a text file and searching for "*********". I'm not proud!

At least part 1 was easy.

struct game_info { vec2 a; vec2 b; vec2 prize; }; auto solve(game_info const& game) -> std::optional<i64> { auto [a, b, prize] = game; i64 i = b.y * prize.x - b.x * prize.y; i64 j = -a.y * prize.x + a.x * prize.y; i64 det = (a.x * b.y) - (a.y * b.x); if (det == 0 || i % det != 0 || j % det != 0) { return std::nullopt; } else { return 3 * i / det + j / det; } } auto part1(std::vector<game_info> const& games) -> i64 { return flux::ref(games).map(solve).filter_deref().sum(); } auto part2(std::vector<game_info> const& games) -> i64 { return flux::ref(games) .map([](game_info g) { g.prize += vec2{10000000000000, 10000000000000}; return solve(g); }) .filter_deref() .sum(); }

Ah, #AdventOfCode day 13, in which I fail to spot that we're solving a system of two simultaneous equations despite allegedly holding multiple degrees in mathematics AND WRITING THE EQUATIONS DOWN IN FRONT OF ME 🤦‍♂️. I got there in the end though.

github.com/tcbrindle/ad...

GitHub - martinus/unordered_dense: A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion - martinus/unordered_dense

As noted, mine is about 10x slower with libc++'s std::unordered_map, so your approach might be faster? This is the hash table I'm using, it's a drop-in single header if you want to try it github.com/martinus/uno...

With the fast hash map it's about 3.5ms for part 2 on my laptop

// From https://github.com/martinus/unordered_dense // 10x faster than std::unordered_map for this problem! using stones_map = ankerl::unordered_dense::map<u64, u64>; template <int N> auto blink = [](stones_map stones) -> u64 { stones_map next; for (auto _ : flux::ints(0, N)) { for (auto [val, count] : stones) { if (val == 0) { next[1] += count; } else if (auto opt = split_digits(val)) { next[opt->first] += count; next[opt->second] += count; } else { next[val * 2024] += count; } } std::swap(stones, next); next.clear(); } return flux::sum(stones | std::views::values); }; auto const part1 = blink<25>; auto const part2 = blink<75>;

Exponential growth was the enemy in #AdventOfCode today!

A simple vector was good enough for part 1, but more iterations in part 2 required a different approach. I went for storing the data in a (value, count) hash map, which worked very well. A nice puzzle!

github.com/tcbrindle/ad...

This is very nice! Clearly recursive lambdas were the way to go today

struct trail_info { int score; int rating; }; auto walk_trail(grid2d const& grid, position start) -> trail_info { std::vector<position> goals; [&](this auto const& self, position here) -> void { char value = grid[here]; if (value == '9') { goals.push_back(here); } else { get_neighbours(here) .filter([&](position p) { return grid.is_in_bounds(p) && (grid[p] == value + 1); }) .for_each(self); } }(start); flux::sort(goals); int score = flux::ref(goals).dedup().count(); return {.score = score, .rating = int(goals.size())}; }; auto walk_all(std::string_view input) -> trail_info { auto grid = parse_input(input); return grid.positions() .filter([&](auto pos) { return grid[pos] == '0'; }) .map(std::bind_front(walk_trail, grid)) .fold([](auto sum, auto info) { sum.score += info.score; sum.rating += info.rating; return sum; }, trail_info{}); };

A strange #AdventOfCode problem today where you had to solve part 2 in order to get part 1! I'm pretty happy with my solution to this one, runs in ~100µs on my laptop and has my first use of a C++23 recursive lambda.

Github: github.com/tcbrindle/ad...

I used exactly this approach to get the stars, but my solution took a couple of seconds to run. Rewrote it as a boring DFS and it ran in 10ms. Not sure what I did wrong the first time but it made me a bit sad!

No #AdventOfCode screenshots today as my code is super messy and not worth showing off. But it was very satisfying taking the initial 5 minute(!) runtime for part 2 down to ~70ms on my laptop.

github.com/tcbrindle/ad...

FYI the "144 pages" link in that article points to your C drive

That `tl::split<T, N>` looks super interesting, is it available somewhere to have a look at?

Thanks! If you fancy giving it a try sometime I’d love to get some feedback from ranges experts about how I can improve it.

Oh, that's really nice! 😍

using rules_t = ankerl::unordered_dense::set<std::pair<int, int>>; using update_t = std::vector<int>; auto part1(rules_t const& rules, std::vector<update_t> const& updates) -> int { auto cmp = [&](int l, int r) { return rules.contains(l, r); }; return flux::ref(updates) .filter([&](update_t const& u) { return std::ranges::is_sorted(u, cmp); }) .map([](update_t const& u) { return u.at(u.size() / 2); }) .sum(); }; auto part2(rules_t const& rules, std::vector<update_t> const& updates) -> int { auto cmp = [&](int l, int r) { return rules.contains({l, r}); }; return flux::ref(updates) .filter([&](update_t const& u) { return !std::ranges::is_sorted(u, cmp); }) .map([&](update_t u) { std::ranges::sort(u, cmp); return u.at(u.size() / 2); }) .sum(); };

Day 5 of #AdventOfCode felt kinda like cheating once I realised that the rules give us an ordering that we can use as a comparator with sort()/is_sorted().

Using a hash set gives about a 10x speedup versus a sorted vector + binary search, but the latter is plenty fast enough for the problem size

One super helpful trick I discovered from AoCs past is to use a grid type whose operator[] returns an invalid character (e.g. '.') when given an out-of-bounds position -- it saves tons of messy bounds checking elsewhere.

// helper function which returns a sequence that lazily generates // the 8 length-3 strings originating at [x, y] auto neighbours = [](grid2d const& grid, i64 x, i64 y) { return flux::cartesian_power<2>(flux::ints(-1, 2)) .filter(flux::unpack([](i64 i, i64 j) { return !(i == 0 && j == 0); })) .map(flux::unpack([&grid, x, y](i64 i, i64 j) { return std::string{grid[x + i, y + j], grid[x + 2 * i, y + 2 * j], grid[x + 3 * i, y + 3 * j]}; })); }; // for each grid position, if it contains an 'X' then find the 8 strings // surrounding it and count how many of those match 'MAS' auto part1 = [](grid2d const& grid) -> i64 { return flux::cartesian_product(flux::ints(0, grid.height), flux::ints(0, grid.width)) .filter(flux::unpack([&](i64 x, i64 y) { return grid[x, y] == 'X'; })) .map(flux::unpack([&](i64 x, i64 y) { return neighbours(grid, x, y); })) .flatten() .count_if(flux::pred::eq("MAS"sv)); }; // for each grid position, look at a 3x3 window and check whether // the leading and back diagonals both match either 'MAS' or 'SAM' auto part2 = [](grid2d const& grid) -> i64 { return flux::cartesian_product(flux::ints(0, grid.height - 2), flux::ints(0, grid.width - 2)) .count_if(flux::unpack([&grid](i64 x, i64 y) { std::string lead{grid[x, y], grid[x+1, y+1], grid[x+2, y+2]}; std::string back{grid[x+2, y], grid[x+1, y+1], grid[x, y+2]}; return (lead == "MAS" || lead == "SAM") && (back == "MAS" || back == "SAM"); })); };

Day 4 of #AdventOfCode and we're solving word searches!

Part 1 had me scratching my head for a little while, because I didn't account for the fact that an 'X' can be the root of more than one 'XMAS'. Fortunately part 2 was less tricky.

Code: github.com/tcbrindle/ad...