dev.to staff

Posted on Jul 12, 2019

Daily Challenge #14 - Square into Squares

#challenge

Good morning, all.

This challenge finishes our second week of the Daily Challenge series. It'll be our most difficult challenge yet!

We are grateful to user g964, who posted this challenge and many others on CodeWars.

Given a positive integer n, return a strictly increasing sequence of numbers so that the sum of the squares is equal to n².

If there are multiple solutions, return the result with the largest possible value:

For example: decompose(11) must return [1,2,4,10].

Note: there are actually two ways to decompose 11², 11² = 121 = 1 + 4 + 16 + 100 = 1² + 2² + 4² + 10² but you shouldn't return [2,6,9], since 9 is smaller than 10.

Hint: Very often will xk be n-1.

Good luck and happy coding!

Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Top comments (9)

Andy O'Neill • Jul 12 '19

I think this works for JavaScript:

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);
}

Alvaro Montoro • Jul 14 '19

JavaScript

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();
}

And a live demo on CodePen.

Alvaro Montoro • Jul 14 '19

Not really inspired lately, my code is getting bigger and messier... and I'm running behind on these challenges :-/

Corey Alexander • Jul 14 '19

I feel ya! Me tooooo

I got this one started but ran into a tougher example that I haven't worked through yet! Definitely want to get it wrapped up but I'm definitely not doing 1 a day anymore

E. Choroba • Jul 16 '19 • Edited

Perl solution, using recursion:

#!/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';

I added 12 as a test, too, because for 12, 11 is not part of its decomposition.

Corey Alexander • Jul 16 '19

Here is my Rust version!

I started with an iterative solution, but I was working off a simplifying assumption that turned out to be false once I starting testing larger examples.

After I realized my simplification wasn't going to work I went for a recursive solution. I think it turned out pretty well! I also got to try out my first Macro in Rust so that was cool!

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]));
    }
}

Mat-R-Such • Jan 17 '20

Python solution:

def decompose(n):
    if n == 0:
        return -1
    elif n == 1:
        return [1]

    array_power=[pow(i,2) for i in range(1,n)]          #array with powers [1^2,2^2,3^2...,(n-1)^2]
    array_power=array_power[::-1]
    array_help,power,i,j=[],pow(n,2),0,n-1              # power= n^2, i=element(array), j= base of the power

    while power > 0:
        if power >= array_power[i]:
            power-=array_power[i]
            array_help.append(j)
        i+=1
        j-=1
        if i == n-1 and power > 0:
            return [n]
    return array_help[::-1]


print(decompose(1))

YAGNESH RAJA • Mar 18 '21

Once try for 50 You should get[1,3,5,8,49],

meave9786 • Apr 3 '20

This is the use full blog here most people have to seen it and save the batter update of euchre free online really thanks for the share me it is the amazing.

DEV Community

Daily Challenge #14 - Square into Squares

Top comments (9)

Read next

5 Best Note-Taking Apps 📝

Next.js containerization using Docker

Lendo e gravando arquivos usando fluxos de bytes

Test dates-related and time features using date-fns and Jest