Euler 31 on monoids

[sassa_nf]

https://projecteuler.net/problem=31

I've done it before, but it came up again.
Recurrent relationships can be represented as matrices. Computing the N-th then is a matrix multiplication. The multiplication being associative, and having a unit, it allows certain improvements - faster computation of N-th, parallellism.

Let's represent each coin denomination as a square matrix NxN, C. Then given a vector V of size N representing the number of ways to give change for an amount up to N for some set of coins, you can compute a new vector of size N: V_S+C = V_S x C, representing the number of ways to give change for an amount up to N for a set of coins including a new coin denomination, C.

We know what the vector V is for an empty set of coins: V_∅ = |1 0 0 0 ...| - you have 1 way to give change for amount 0, and 0 ways to give change for any other amount.

Now, for each denomination the matrix is going to look like this:

   coin == 2        coin == 3
 | 1 0 1 0 ... |  | 1 0 0 1 0 0 1 ... |
 | 0 1 0 1 ... |  | 0 1 0 0 1 0 0 ... |
 | 0 0 1 0 ... |  | 0 0 1 0 0 1 0 ... |
 | 0 0 0 1 ... |  | 0 0 0 1 0 0 1 ... |
 | ...         |  | ...               |

where each column tells how the number of ways to give change depends on known ways to split the money. That is, a diagonal (I) tells us - one way to split the money including a new denomination, is to not use the new denomination at all - just use the old denominations. Then a 1 is placed every d spaces above the diagonal - to represent the other cases: use 1 coin of new denomination d, and split the rest using old denominations; use 2 coins of new denomination d, and split the rest using old denominations, etc.

Then a product V_∅ x C₁ x C₂ x C₅ tells us in how many ways we can split any amount using coins of 1, 2 and 5. The problem asks only one amount, so really we are interested only in the rightmost value in the topmost row of every matrix. This, and the fact that the matrices are symmetric, simplifies matrix multiplication - we really need to keep track only of the top row; the rightmost column is always the same as the top row.

                      | 1 0 1 0 1 0 1 ... |
                      | 0 1 0 1 0 1 0 ... |
                      | 0 0 1 0 1 0 1 ... |
| A B C D E F ... | x | 0 0 0 1 0 1 0 ... | = | A' B' C' D' E' F' ... |
                      | 0 0 0 0 1 0 1 ... |
                      | 0 0 0 0 0 1 0 ... |
                      | 0 0 0 0 0 0 1 ... |

 A' = | A B C D E F | * | 1 0 0 0 0 0 ... | = A
 B' = | A B C D E F | * | 0 1 0 0 0 0 ... | = B
 C' = | A B C D E F | * | 1 0 1 0 0 0 ... | = A' + | A B C D E F | * | 0 0 1 0 0 0 ... | = C + A'
 D' = | A B C D E F | * | 0 1 0 1 0 0 ... | = B' + | A B C D E F | * | 0 0 0 1 0 0 ... | = D + B'
 E' = | A B C D E F | * | 1 0 1 0 1 0 ... | = C' + | A B C D E F | * | 0 0 0 0 1 0 ... | = E + C'
 F' = | A B C D E F | * | 0 1 0 1 0 1 ... | = D' + | A B C D E F | * | 0 0 0 0 0 1 ... | = F + D'
 ...

We can compute matrix product separately for various subsets of coins, even in parallel.

use std::slice::Iter;
use std::thread;
use std::time::Instant;

fn change_mx(amount: usize, coins: Iter<u32>) -> Vec<u32> {
   let mut row0 = vec![0; amount+1];
   row0[0] = 1;
   for c in coins {
      let c = *c as usize;
      for i in c..(amount+1) {
         row0[i] += row0[i - c];
      }
   }

   row0
}

fn change(amount: usize, coins: Vec<u32>) -> u32 {
   let now = Instant::now();
   let r = if coins.len() < 2 {
      change_mx(amount, coins.iter())[amount]
   } else {
      let mut half_coins = Vec::new();
      half_coins.extend_from_slice(&coins[0..coins.len() / 2]);
      let mx_l = thread::spawn(move || change_mx(amount, half_coins.iter()));
      let mut mx_r = change_mx(amount, coins[coins.len() / 2..].iter());
      mx_r.reverse();
      mx_l.join().unwrap().iter().zip(mx_r.iter()).map(|v| v.0 * v.1).sum()
   };
   println!("{}", now.elapsed().as_micros());
   r
}

fn main() {
   println!("{}", change(500, vec![3,5,7,8,9,10,11]));
}

But the benefits of parallellism are really didactic :-) Performance-wise spinning up a thread for parallel computation pays off only when you start looking at giving change for the amounts of tens of millions.

Comments

[juan_gandhi]

Wow, pretty cool idea!

[thedeemon]

I assume some types in angle brackets after Iter disappeared here.

[sassa_nf]

Thanks! Fixed.

[dmm]

Wow! Very cool...