Rust via Advent of Code

This repo explores Rust idioms, data-structure tradeoffs, and optimization via some Advent of Code problems. The problems typically have initial cold attempts, then some solutions influenced by community write-ups and video, and often deeper dives. The focus is on the algorithm or Rust differences, not solving all the puzzles.

For building, layout, and conventions, see the rust/README.md.

Warning

Spoilers. Crate and module docs describe each day's task and approach.

Topics explored

Each bullet links to the most applicable source file.

• SIMD and intrinsics
  • Portable std::simd: a working vectorized parse. 2024 day 1: v0_simd_port
  • Auto/generic intrinsics: hard to beat the normal optimized compile, as expected generic SIMD gained little over plain code.
  • Arch-specific intrinsics: initial hand-coded experiments, incomplete. 2024 day 1: v1_simd_intrins
• Byte-level parsing and micro-optimization
  • Simple: idiomatic &str parsing with iterators.
  • Involved: byte parsing with chunks_exact and ASCII masking. A heap Vec buffer ran 4–8% faster than a fixed-size array, and masking beat subtracting '0'. 2024 day 1: v3_bytes
• Parser combinators
  • nom: match number-words, skip non-reusable prefixes, and fold to the first and last digit. 2023 day 1: v1_nom
• Enum modeling
  • Mod-3 discriminant arithmetic, FromStr, and outcome-to-shape mapping for scoring. 2022 day 2: ver_1
  • Enum parsing vs string matching, measured: the enum version was ~10% slower than plain string matching, likely from matching twice. 2021 day 2: v1_enum
• Membership data structures
  • HashSet vs an ASCII-indexed bool array for O(1) lookup, space-versus-speed tradeoff. 2022 day 3: v1
• Iterators and parallelism
  • Functional passes with map and itertools batching. 2022 day 1: v2_itertools
  • A rayon parallel variant. 2022 day 1: v_par
• Proc macros (historical)
  • A derive-style macro pulling the day number from the crate's folder name. Present in the tree, but no longer used. proc-fn

Goals

• Learning and playing with Rust. Some solutions are simple, others are heavily but unevenly engineered.
• Efficient algorithms.
• Problem-solving targeting a rapid-prototyping pace, though the above come first.

Non-goals

• Deep documentation or rich error handling.
• Fully optimized algorithms, or exhaustive low-level choices such as raw bytes vs. enum FromStr, or i32 vs. u8. Though parts of that get played with.
• Speed coding.

Python

There is one Python solution. See python/.

See also

• Fasterthanlime's AoC 2022 blog series, is a great discussion of Rust fundamentals applied to each day and a good chance to learn Rust ideas by applying them to code you just wrote.
• The Advent of Code site.
• TJ DeVries did several AoC 2021 days in Rust.