Daily Challenge #14 - Square into Squares

function squaresTotaling(max, goal) {
  if (max ** 2 === goal) return [max];
  if (goal <= 0 || max <= 0) return null;
  const subProblem = squaresTotaling(max - 1, goal - max ** 2);
  if (subProblem) return [...subProblem, max];
  return squaresTotaling(max - 1, goal);
}

function decompose(val) {
  return squaresTotaling(val - 1, val ** 2);
}

const decompose = number => {
  let components = [];
  let modifier = 1;
  do {
    // initialize the values before the loop
    components = [];
    let remaining = number ** 2;

    // from number - 1 until 1 check if the square of the number is less than the remaining
    for (let number = Math.floor(Math.sqrt(remaining)) - modifier; remaining > 0 && number > 0; number--) {
      if (number**2 <= remaining) {
        components.push(number);
        remaining -= number**2;
        // if a squared component is found, continue from the square root of the remaining
        number = Math.floor(Math.sqrt(remaining)) + 1;
      }
    }
    // the modifier is used to check for the next set of
    modifier++;
  // do this while there are duplicates (duplicates mean that one number -in particular 1- was repeated)
  // this code is a variation of https://stackoverflow.com/a/34192063/3695983
  } while (components.length !== new Set(components).size);
  return components.reverse();
}

#!/usr/bin/perl
use warnings;
use strict;

sub _decompose {
    my ($n, $target, $decomposition, $sum) = @_;

    return $decomposition if $target == $sum;

    my $smaller = int sqrt $n - 1;
    while ($smaller) {
        my $small_square = $smaller ** 2;
        if ($sum + $small_square <= $target) {
            my $d = _decompose(
                $smaller ** 2, $target,
                [ $smaller, @$decomposition ], $sum + $smaller ** 2
            );
            return $d if @$d;
        }
        --$smaller;
    }
    return []
}

sub decompose {
    my ($n) = @_;
    my $square = $n ** 2;
    return _decompose($square, $square, [], 0)
}

use Test::More tests => 2;
is_deeply decompose(11), [1, 2, 4, 10], 'eleven';
is_deeply decompose(12), [1, 2, 3, 7, 9], 'twelve';

fn decompose_recursive(goal: u32, i: u32, curr: Vec<u32>) -> Option<Vec<u32>> {
    macro_rules! try_recusing {
        ( $goal:expr, $i:expr, $next:expr ) => {{
            let attempt = decompose_recursive($goal, $i, $next);

            if attempt.is_some() {
                return attempt;
            }
        }};
    }

    if goal == 0 {
        return Some(curr);
    }

    if i <= 0 {
        return None;
    }

    if goal >= i.pow(2) {
        let mut next = curr.clone();
        next.push(i);

        try_recusing!(goal - i.pow(2), i - 1, next);
    }

    try_recusing!(goal, i - 1, curr);

    None
}

pub fn decompose(n: u32) -> Option<Vec<u32>> {
    let reverse_vec = decompose_recursive(n.pow(2), n - 1, vec![])?;
    let vec = reverse_vec.iter().rev().cloned().collect();
    Some(vec)
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn it_works_for_a_nonexistant_example() {
        assert_eq!(decompose(4), None);
    }

    #[test]
    fn it_works_for_the_dev_to_example() {
        assert_eq!(decompose(11), Some(vec![1, 2, 4, 10]));
    }

    #[test]
    fn it_works_for_50() {
        assert_eq!(decompose(50), Some(vec![1, 3, 5, 8, 49]));
    }
}