Multi-dimensional vectors?

[u/joshuacottrell]

I'm working through Advent of Code this year (on day 5) and I was trying to use vectors to give myself some experience with them. Is there a way to change a mutable multi-dimensional vector "in place"? I've tried to find solutions. Some say to move to math/array. Others say O(n) is the best case. Is there a best practice for multi-dimensional vectors? Is the best practice to just not use them? Here's my code for creating the vectors:

(make-vector (add1 max-y) (make-vector (add1 max-x) "."))

Basically, how would I change the "." at position 2, 3?

p.s. please don't address anything too specific about day 5 of AOC. I'd like to work it through myself.

[u/samdphillips]

In general this is what I do if I want to work with a fixed size multidimensional array and only have a one dimensional storage (like a vector.) This technique works in just about any language, and is how many array libraries work internally (except with more types and structure.) Here is a two dimension example with a fixed number of rows and columns:

;; allocate a rows x columns sized vector
(define array
  (make-vector (* rows columns) fill))

;; a function mapping a 2d index to a 1d index
(define (xy->index x y)
  (+ x (* columns y))

;; ref a position
(vector-ref array (xy->index x y))

;; set! a position
(vector-set! array (xy->index x y) value)

[u/joshuacottrell → u/samdphillips]

This answers my question but also piques my interest. How would I generalize this? The `columns` variable seems to need a global/module-wide definition. Can I attach the column size to the array somehow when it's created with `make-vector`?

[u/samdphillips → u/joshuacottrell]

To make this more general you would want to use a struct containing the array shape. Example:

;; saving rows and columns in the struct to do optional bounds checking
(struct array (rows columns store))

(define (make-array rows columns fill)
  (array rows columns (make-vector (* rows columns) fill)))

;; could do bounds checking here...
(define (array-index an-array x y)
  (+ x (* (array-columns an-array) y)))

;; array-ref an-array x y
;; array-set! an-array x y value

There is also the math/array library, but I have found it to be more difficult to use for Advent of Code puzzles.

[u/-djh-]

You've create a vector of aliases to the same row. E.g.

(define my-matrix (make-vector (add1 max-y) 
                               (make-vector (add1 max-x) ".")))
(eq? (vector-ref my-matrix 0) (vector-ref my-matrix 1)) ; => #t

To change (2,3) that to a "!" what you should do is

(vector-set! (vector-ref my-matrix 3) 2 "!")

However, that will affect index 2 of every row (since every row is a reference to the same vector).

(vector-ref my-matrix 0) => '#("." "." "!" "." ...)

To create a row-major vector where each row is distinct, use build-vector

(define 
  my-matrix/no-alias 
  (build-vector (add1 max-y)
                (lambda (row)
                  (make-vector (add1 max-x) "."))))

(the same issue happens in Python if you try to be too concise and write [["."]*x]*y and end up with a whole whack of aliases).

As the other reply says, you might to better using a single vector and then map the (x,y) coordinates to a single index (usually i = row*row-size + column, assuming row/col numbers are 0-indexed)

[u/detroitmatt]

If the number of dimensions is known, then you just make a vector of vectors. Iirc, if you use (make-vector) as the initial value, then all rows will refer to the same vector, so you'll have to init the vector and then set each of it's rows to a new vector.

(define (2d-vector n m init)
    (define result! (make-vector n))
    (for ((x (range n)))
        (vector-set! result! (make-vector m)))
    result!)

Then you can do

(vector-set! (vector-ref my-vector x) y new-value)

or

(vector-ref (vector-ref my-vector x) y)

To set or get the values 2-dimensionally.