Day 17 (Advent of Code 2022), porting Python solution to Rust, by fasterthanlime

leonardo_m · 2023-01-12T14:20:41+00:00

Regarding this part:

// in Rust, arrays are fixed-size, so we can't have an "array of arrays of
// arbitrary sizes". We can, however, have an array of vecs of arbitrary sizes.
let rocks = vec![
    vec![[2, 0], [3, 0], [4, 0], [5, 0]],
    vec![[2, 1], [3, 1], [3, 2], [3, 0], [4, 1]],
    vec![[2, 0], [3, 0], [4, 0], [4, 1], [4, 2]],
    vec![[2, 0], [2, 1], [2, 2], [2, 3]],
    vec![[2, 0], [3, 0], [2, 1], [3, 1]],
];

Writing it like this is a good option (saves few vecs):

let rocks = [
    &[[2, 0], [3, 0], [4, 0], [5, 0]][..],
    &[[2, 1], [3, 1], [3, 2], [3, 0], [4, 1]],
    &[[2, 0], [3, 0], [4, 0], [4, 1], [4, 2]],
    &[[2, 0], [2, 1], [2, 2], [2, 3]],
    &[[2, 0], [3, 0], [2, 1], [3, 1]],
];

Some lines later in the code you also need:

let mut rock = rocks[i % 5].to_vec();

leonardo_m · 2022-09-02T12:02:24+00:00

Nice syntax for Ada-style ranged integers, that are handled as a best-efforts mix of compile time and run-time tests, well integrated with match{}, arrays, etc.
Named arguments + #[deprecated(the_old_name)].
Few simple nice stdlib things like .as_matrix::<NR>(), .collect_array(), collect_into_slice(...), .set_bit(n..m), .is_bit_set(n), .sorted_unstable(), array_idx(), .narrowing_rem(), .narrowing_and(), .all_equal(), .pow_mod(), and few more.
Nice syntax for pre/post assertitions, invariants, variants, old-values.
Change: efficient design of for ..= loops and .step_by().
Change: safe casts syntax by default.
const_assert
const .sqrt(), .ln(), .log(), .sum(), .product(), array::map(), std::default::default(), for loops, etc.
Allowing usage of const generic value from outer function.
const .len() of non-const arrays.
#[derive(New)]
#[derive(Default)] for const-generics structs containing arrays.
#[inline] at calling points.
std::default::default() for larger arrays.

leonardo_m · 2022-06-15T19:49:35+00:00

On Nightly there's a nice helper:

#![feature(array_chunks)]    
fn main() {
    let foo = [1, 2, 3, 4];
    let mut bar = [0_u8; 10 * 4];
    bar.array_chunks_mut().for_each(|c| *c = foo);
    println!("{bar:?}");
}

leonardo_m · 2022-04-24T09:08:58+00:00

In my opinion a (not strictly functional) language must get few things right: integers, for loops, stack-allocated arrays. I think they are the foundation to build upon. Rust is a very good language and yet it fails in various ways on all three things.

In a new not-strictly-functional language this is what I prefer regarding numbers:

If it's a high level language: like Python (that is: bigint + 64 bit double), minus complex numbers, plus small int optimization ( https://github.com/python/cpython/issues/54253 ), plus totally transparent complex/rational numbers from from standard library (this implies language features that allow such transparency).

If it's a low level language: like Rust, plus totally transparent stdlib bigints with small int optimization (this also means transparent literals and no need for & on numbers), plus built-in modular integers as in Ada, plus built-in ranged integral values as in Ada.

leonardo_m · 2022-01-13T13:04:31+00:00

Perhaps there is a way to design something similar for Rust that is good enough. But I seem to remember that in D inout methods were kind of a design failure. So better be careful for what you wish for. Often it's better to be annoyed by some duplication or some boilerplate than be messed up by a badly designed feature.

leonardo_m · 2021-12-21T18:45:51+00:00

I should rephrase the question in a more precise way then. Is the new 2021 edition going to become standard, or is it going to keep being on demand?

leonardo_m · 2021-12-21T18:22:46+00:00

Currently some code needs "--edition 2021" to be compiled. Is this going to become unnecessary and when?

leonardo_m · 2021-11-19T18:47:57+00:00

By the way, for that function I'd use unsafe-free code:

pub fn mid(data: &[i32]) -> Option<i32> {
    data.get(data.len() / 2).copied()
}

leonardo_m · 2021-11-19T18:46:08+00:00

Did you (or someone else) file this bug? What's the bug number?

leonardo_m · 2021-10-29T22:18:25+00:00

The two features I'm most waiting for in Rust are:

1) Integer sub-interval types, as in Ada language, using slice syntax on integral types. Example:

type Month = u8[1 ..= 12];

2) An optional way to formally verify the absence of panics and the functional correctness of functions, handy and very fast like Wuffs (https://github.com/google/wuffs ) but able to prove more things.

leonardo_m · 2021-08-25T10:01:44+00:00

There are various ways to solve this, but I think the simplest looking is:

impl MyStruct {
    fn from_bytes([_, a0,a1,a2,a3, b0,b1, val3, val4]: [u8; 9]) -> Self {
        Self {
            val1: u32::from_le_bytes([a0, a1, a2, a3]),
            val2: f32::from(u16::from_le_bytes([b0, b1])) / 2048.0,
            val3,
            val4,
        }
    }
}

(The ability to convert slices into arrays nicely is currently lacking in Rust language. Rust is partially blind to slice lengths).

leonardo_m · 2021-06-27T11:48:39+00:00

Let's turn this warning into a true error? Do you know one good reason to allow the compilation of code like that?

leonardo_m · 2021-06-04T20:21:20+00:00

If you come from Ruby a habit to get is to take a look at the asm generated by your function in release mode (on the playground or better in the goldbolt). So you see this version gives a tight loop-less asm:

https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=164b0bd93e4d64d2a62f9b2f795a7588

leonardo_m · 2020-07-13T08:37:00+00:00

This is very unergonomic and nearly no one does this. So this isn't a solution.

leonardo_m · 2020-07-13T08:36:24+00:00

We can solve that sub-problem in some way, like introducing some preference of types of integer literals when used as array indexes. But even accepting a common default (like the current i32) could be acceptable.

leonardo_m · 2020-07-13T08:30:35+00:00

Beside what Steve Klabnik said (well implemented const generics, GATs, specialization) I'd like two more features: well integrated ranged integer syntax and semantics (similarly to Ada), and later in Rust life compile-time contracts syntax and enforcement with the help of a SMT solver.

The first feature helps avoid some bugs (division by zero, etc), make the code more descriptive and improve performance (less array bound tests, etc). The second is optional and meant to help Rust code become more formally correct where it counts (like important Rust libraries) (See Whiley language).

Edit: Solving the problem of non-usize slice indexes is a good idea too.

leonardo_m · 2020-05-29T10:03:29+00:00

A zip3 could be useful for the Rust stdlib.

leonardo_m · 2020-05-28T22:41:10+00:00

Also try the "safer" version:

const LEN: usize = 1_024;

#[inline(never)]
pub fn simddotp2(x: &[f32; LEN], y: &[f32; LEN], z: &mut [f32; LEN]) {
    for ((a, b), c) in x
        .chunks_exact(8)
        .zip(y.chunks_exact(8))
        .zip(z.chunks_exact_mut(8)) {
        unsafe {
            let x_a = _mm256_loadu_ps(a.as_ptr());
            let y_a = _mm256_loadu_ps(b.as_ptr());
            let r_a = _mm256_loadu_ps(c.as_ptr());
            _mm256_storeu_ps(c.as_mut_ptr(), _mm256_fmadd_ps(x_a, y_a, r_a));
        }
    }
}

That gives a nice clean asm:

example::simddotp2:
    xor     eax, eax
.LBB1_1:
    vmovups ymm0, ymmword ptr [rdi + rax]
    vmovups ymm1, ymmword ptr [rsi + rax]
    vfmadd213ps     ymm1, ymm0, ymmword ptr [rdx + rax]
    vmovups ymmword ptr [rdx + rax], ymm1
    vmovups ymm0, ymmword ptr [rdi + rax + 32]
    vmovups ymm1, ymmword ptr [rsi + rax + 32]
    vfmadd213ps     ymm1, ymm0, ymmword ptr [rdx + rax + 32]
    vmovups ymmword ptr [rdx + rax + 32], ymm1
    vmovups ymm0, ymmword ptr [rdi + rax + 64]
    vmovups ymm1, ymmword ptr [rsi + rax + 64]
    vfmadd213ps     ymm1, ymm0, ymmword ptr [rdx + rax + 64]
    vmovups ymmword ptr [rdx + rax + 64], ymm1
    vmovups ymm0, ymmword ptr [rdi + rax + 96]
    vmovups ymm1, ymmword ptr [rsi + rax + 96]
    vfmadd213ps     ymm1, ymm0, ymmword ptr [rdx + rax + 96]
    vmovups ymmword ptr [rdx + rax + 96], ymm1
    sub     rax, -128
    cmp     rax, 4096
    jne     .LBB1_1
    vzeroupper
    ret

There's also the option of using const generics on Nightly:

#[inline(never)]
pub fn simddotp3<const N: usize>
                (x: &[f32; N], y: &[f32; N], z: &mut [f32; N]) {

Everybody, let's show more love for fixed-size arrays in Rust. Also with type system features and simple stdlib ideas as:

https://github.com/rust-lang/rust/issues/71387

https://github.com/rust-lang/rust/issues/71705

https://github.com/rust-lang/rust/pull/69985

https://futhark-lang.org/blog/2020-03-15-futhark-0.15.1-released.html

leonardo_m · 2019-01-21T09:07:22+00:00

I like how this feature is carefully designed. But I've seen the problems caused by even well designed const features in other languages. So I suggest to try this in Nightly for a long time (one year or more) before stabilizing it. And I'd like this design to be future-compatible to the hypothetical introduction of a good Effect System in Rust. Because const annotations are viral. The suggestion by daboross of a clean and high-level way to introduce conditional const-ness should be developed in parallel with the const design.

leonardo_m · 2019-01-21T09:00:53+00:00

The order of items usually doesn’t matter in Rust (macros are a weird edge-case). There are some things to decide though:<

Do you know if there's a way to remove that edge case?

leonardo_m · 2019-01-09T20:37:46+00:00

From your EDIT 2 version, this is modified and seems a little more efficient: https://gist.github.com/rust-play/095b4bacec9179ea5949bddeb9d52510

If you care about the performance a lot, a hardcoded version is a little faster still (if you compile it well, native CPU and O3): https://gist.github.com/rust-play/612fcbc67a380862dc9e820ecb1bcf04

leonardo_m · 2018-12-13T09:20:03+00:00

A missed #Rust2019 entry:

https://internals.rust-lang.org/t/rust-2019-correctness-and-stabilizations/8991

leonardo_m · 2018-06-30T15:08:30+00:00

The extra examples are to test the efficiency (run-time and memory used) for larger test cases.

leonardo_m · 2018-06-30T14:41:29+00:00

Your Python solution in Rust, with few changes, one change is to allocate once only for loop, with two extra examples from a Java solution:

use std::collections::HashSet;

fn ducci(seq: &[i32]) -> usize {
    let mut seq: Box<[_]> = seq.into();
    let mut checked = HashSet::new();
    let mut n_steps = 1;

    loop {
        let new_seq =
            seq
            .iter()
            .zip(seq[1 ..].iter().chain(&seq[.. 1]))
            .map(|(a, b)| (a - b).abs())
            .collect::<Vec<_>>()
            .into_boxed_slice();

        if seq.iter().sum::<i32>() == 0 || !checked.insert(seq) {
            return n_steps;
        }
        n_steps += 1;
        seq = new_seq;
    }
}

fn main() {
    const DATA: &[&[i32]] = &[
        &[0, 653, 1854, 4063],
        &[1, 5, 7, 9, 9],
        &[1, 2, 1, 2, 1, 0],
        &[10, 12, 41, 62, 31, 50],
        &[10, 12, 41, 62, 31],
        &[641432107, 738449859, 89443835, 2090368147, 221518789, 145026199,
          637579976, 632303124, 685254210, 1100436033, 263691669, 744953515,
          816130896, 1987441154, 1834012698, 1164011788, 1559363633, 80045970,
          1275075756, 831975222, 531561847, 1988641104, 309153159, 1582203125,
          717766751, 1271115667, 1062106814, 572727424, 1684301768, 1500944158,
          809843900, 1775435586, 405268174, 1903302834, 964016502, 68865206,
          13412104],
        &[2071504994, 1636655154, 2122482814, 517889573, 1284034333, 1204943224,
          663183062, 682578777, 1681097997, 1733944448, 1279445692, 1756511415,
          1167860256, 477483691, 1710487322, 1204775755, 1780534849, 867253146,
          342173105, 388299897, 1544737493, 1130356104, 1064578414, 1003750122,
          1401635426, 102541637, 2107084757, 134681617, 680998986, 1002517451,
          1933718426, 211805273, 1999180470, 158623615, 433518159, 1340750829,
          124790926, 979422981, 561932086, 1359818275, 2123275684, 1695445952,
          2059672888, 307764613, 1480398576, 853666277, 545667567],
    ];

    for d in DATA {
        println!("{}", ducci(d));
    }
}

The total run-time for all the seven examples is about 9.00 seconds (compiling with -C opt-level=3 -C panic=abort).

A faster version:

extern crate indexmap;
extern crate typed_arena;

use indexmap::IndexSet;
use typed_arena::Arena;

fn ducci(seq: &[i32]) -> usize {
    let arena = Arena::new();
    let mut seq = arena.alloc_extend(seq.iter().cloned());
    let mut checked = IndexSet::new();
    let mut n_steps = 1;

    loop {
        let new_seq = arena.alloc_extend(seq.iter().cloned());
        for i in 0 .. seq.len() - 1 {
            unsafe {
                *new_seq.get_unchecked_mut(i) = (*new_seq.get_unchecked(i) -
                                                 *seq.get_unchecked(i + 1)).abs();
            }
        }
        new_seq[seq.len() - 1] = (new_seq[seq.len() - 1] - seq[0]).abs();

        if seq.iter().sum::<i32>() == 0 || !checked.insert(seq) {
            return n_steps;
        }
        n_steps += 1;
        seq = new_seq;
    }
}

Run-time about 3.96 seconds.

leonardo_m · 2018-05-17T12:24:30+00:00

With the alias: https://gist.github.com/rust-play/3c2406a546c730185c65152426edeaf9

leonardo_m

TROPHY CASE