1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#!/usr/bin/perl
#
# TASK #2 - Split Number
#
# Variation that Tabulates the first N perfect squares and whether or
# not they have a split whose sum is sqrt(that square).
#
# 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
#
# MY NOTES: Sounds pretty easy. The only tricky part is identifying all
# distinct "splits" of the number. Is there a "binary counting" method,
# where bit i being true means: split the number between digit i and i+1?
#
use strict;
use warnings;
use feature 'say';
use Function::Parameters;
use Getopt::Long;
use Data::Dumper;
use List::Util qw(sum);
my $debug = 0;
die "Usage: split-numbers [-d|--debug] MAXN\n"
unless GetOptions( "debug"=>\$debug ) && @ARGV==1;
my $maxsq = shift @ARGV;
#
# my @pieces = BinarySplit( $str, $count );
# Split $str using the binary count $count
# and return the list of split pieces. Each bit of
# the count $count determines whether to split the
# string at the corresponding letter - or
# equivalently, whether to insert a ',' before the letter.
#
fun BinarySplit( $str, $count )
{
$str =~ s/^(.)//; # always add the first letter
my $result = $1;
while( $str =~ s/^(.)// )
{
my $letter = $1;
$result .= ',' if $count&1;
$result .= $letter;
$count >>= 1;
}
return split(/,/,$result);
}
#die Dumper BinarySplit( "hello", 0b100 );
#
# my $issplit = SplitSum( $n, $sum );
# Return 1 iff the digits of $n can be split at
# any position set of positions st the sum of those
# split values is $sum. Return 0 otherwise.
# For example SplitSum(81,9) is true as 9 = 8 + 1
#
fun SplitSum( $n, $sum )
{
my $bits = length($n)-1;
my $twopower = 2**$bits;
say "debug: twopower=$twopower" if $debug;
# ignore i=0, that doesn't split $n at all, and sum($n)==$n
# which is always > $sqrt($n) so can't be an answer
for( my $i=1; $i<$twopower; $i++ )
{
my @pieces = BinarySplit( $n, $i );
my $actualsum = sum(@pieces);
say "debug: i=$i, want sum=$sum, ".join(',',@pieces).
", got sum=$actualsum, want $sum" if $debug;
return 1 if $actualsum == $sum;
}
return 0;
}
foreach my $sq (1..$maxsq)
{
my $n = $sq*$sq;
my $issplit = SplitSum( $n, $sq );
say "$n - $sq" if $issplit;
}
|
