Working years
and square sums
Weekly challenge 138 — 8 November 2021
Week 138: 8 Nov 2021
You are given a perfect square $square
.
Write a script to figure out if the square root of $square
is same as
sum of 2 or more splits of the given number.
Example 1 Input: $n = 81 Output: 1, since sqrt(81) = 8 + 1 Example 2 Input: $n = 9801 Output: 1, since sqrt(9801) = 98 + 0 + 1 Example 3 Input: $n = 36 Output: 0, since sqrt(36) != 3 + 6
The slightly tricky requirement is to generate all the splits of a multi-digit number (eg 123456).
Consider the number as a string of $n
digits.
Consider also a binary number with $n - 1
digits (eg 01101). If we generate
all such binary numbers, and consider each bit to represent whether the
corresponding digit in the split is followed by ' + ', we can generate
all the splits.
So for example 123456 and 01101 yields 12 + 3 + 45 + 6:
a plus has been inserted after the first, second and fifth digits of $n
because the first, second and fifth bits of the binary number are 1.
Once we have all the splits we can eval
them to get the sum, and compare
it with sqrt($n)
.
There is one slight catch. If $n
contains am embedded 0 (eg 123056) then
we will get splits like 123 + 056. Perl regards 056 as octal 56, so it
is necessary to remove these leading zeroes before the eval
.
#!/usr/bin/perl # Peter Campbell Smith - 2021-11-08 # PWC 138 task 2 use v5.20; use warnings; use strict; my (@squares, $square, $root, $gaps, $plus_map, $position, $result, $sum, $since, $good, $legend0, $legend1, $result2); # test values @squares = (81, 9801, 36 ** 2, 45 ** 2, 55 ** 2, 82 ** 2, 91 ** 2, 92 ** 2, 777 ** 2); # loop over test values for $square (@squares) { # check it really is a sqare $root = sqrt($square); say qq[Input: $square ($root ** 2)]; if ($root != int($root) or $square < 10) { say qq[$square is not an integer square >= 10\n]; next; } # initialisation $gaps = length($square) - 1; # no of gaps where we could insert a + $good = 0; $since = ''; $legend1 = qq[Output: 1\nsince]; $legend0 = qq[Output: 0\nsince]; # loop over binary numbers eg if $gaps == 6, from 000001 to 111111 for $plus_map (1 .. 2 ** $gaps - 1) { # create a string containing pluses in the appropriate places (eg 123 + 456) $result = ''; for $position (0 .. $gaps) { $result .= substr($square, $position, 1); if ($plus_map & (2 ** $position)) { # use bitwise & to isolate the appropriate bit $result .= ' + '; } } # need to avoid constructs like + 012 as perl regards 012 as an octal number $result2 = $result; $result2 =~ s| 0(\d)| $1|g; # evaluate the string $sum = eval($result2); # good result - sums to the root of the original number - show it if ($sum == $root) { say qq[$legend1 $result == $sum]; $good = 1; $legend1 = 'and '; # bad result - it doesn't; keep this in $since in case no good result is found } else { $since .= qq[$legend0 $result == $sum != $root\n]; $legend0 = 'and '; } } # if there were no good results, list the bad ones print $good ? qq[\n] : qq[$since\n]; }
Input: 81 (9 ** 2) Output: 1 since 8 + 1 == 9 Input: 9801 (99 ** 2) Output: 1 since 98 + 01 == 99 and 98 + 0 + 1 == 99 Input: 1296 (36 ** 2) Output: 1 since 1 + 29 + 6 == 36 Input: 2025 (45 ** 2) Output: 1 since 20 + 25 == 45 Input: 3025 (55 ** 2) Output: 1 since 30 + 25 == 55 Input: 6724 (82 ** 2) Output: 1 since 6 + 72 + 4 == 82 Input: 8281 (91 ** 2) Output: 1 since 8 + 2 + 81 == 91 and 82 + 8 + 1 == 91 Input: 8464 (92 ** 2) Output: 0 since 8 + 464 == 472 != 92 and 84 + 64 == 148 != 92 and 8 + 4 + 64 == 76 != 92 and 846 + 4 == 850 != 92 and 8 + 46 + 4 == 58 != 92 and 84 + 6 + 4 == 94 != 92 and 8 + 4 + 6 + 4 == 22 != 92 Input: 603729 (777 ** 2) Output: 0 since 6 + 03729 == 3735 != 777 and 60 + 3729 == 3789 != 777 and 6 + 0 + 3729 == 3735 != 777 and 603 + 729 == 1332 != 777 and 6 + 03 + 729 == 738 != 777 and 60 + 3 + 729 == 792 != 777 and 6 + 0 + 3 + 729 == 738 != 777 and 6037 + 29 == 6066 != 777 and 6 + 037 + 29 == 72 != 777 and 60 + 37 + 29 == 126 != 777 and 6 + 0 + 37 + 29 == 72 != 777 and 603 + 7 + 29 == 639 != 777 and 6 + 03 + 7 + 29 == 45 != 777 and 60 + 3 + 7 + 29 == 99 != 777 and 6 + 0 + 3 + 7 + 29 == 45 != 777 and 60372 + 9 == 60381 != 777 and 6 + 0372 + 9 == 387 != 777 and 60 + 372 + 9 == 441 != 777 and 6 + 0 + 372 + 9 == 387 != 777 and 603 + 72 + 9 == 684 != 777 and 6 + 03 + 72 + 9 == 90 != 777 and 60 + 3 + 72 + 9 == 144 != 777 and 6 + 0 + 3 + 72 + 9 == 90 != 777 and 6037 + 2 + 9 == 6048 != 777 and 6 + 037 + 2 + 9 == 54 != 777 and 60 + 37 + 2 + 9 == 108 != 777 and 6 + 0 + 37 + 2 + 9 == 54 != 777 and 603 + 7 + 2 + 9 == 621 != 777 and 6 + 03 + 7 + 2 + 9 == 27 != 777 and 60 + 3 + 7 + 2 + 9 == 81 != 777 and 6 + 0 + 3 + 7 + 2 + 9 == 27 != 777
Any content of this website which has been created by Peter Campbell Smith is in the public domain