/
ch-2.raku
87 lines (83 loc) · 2.15 KB
/
ch-2.raku
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
use v6 ;
sub is_arithmetic ( @array ) {
my $len = @array.elems ;
my $start = @array[1] - @array[0] ;
for (1..$len - 2) -> $i {
if ( @array[ $i + 1 ] - @array[ $i ] != $start ) {
return False ;
}
}
return True ;
}
#count the number of 1's in the binary string
sub count_ones( $bin_str ) {
my $ones = 0 ;
for ( 0..$bin_str.chars( ) ) -> $i {
if $bin_str.substr( $i , 1 ) eq '1' {
$ones++ ;
}
}
return $ones ;
}
#convert a binary string into a subset of an array
sub find_subset( $binary_str , @array ) {
my $len = @array.elems ;
my @subset ;
for (0..$len - 1 ) -> $i {
if ( $binary_str.substr($i , 1 ) eq '1' ) {
@subset.push( @array[ $i ] ) ;
}
}
return @subset ;
}
#prefix as many 0's as necessary
sub pad_zeroes( $binstr , $desired_len ) {
my $len = $binstr.chars( ) ;
my $padded ;
if ( $len < $desired_len ) {
$padded = '0' x ( $desired_len - $len ) ;
$padded ~= $binstr ;
}
else {
$padded = $binstr ;
}
return $padded ;
}
#there are as many subsets in the set of integers that were input as
#given by (2 to the power of length of input) - 1
#so we create the binary numbers of all integers from 0 to this upper
#limit that is denoted by the power of 2
#we can then extract elements of the number array that correspond to
#the ones in the binary numbers
say "Enter some integers, separated by blanks!" ;
my $line = $*IN.get ;
my @numbers = $line.words.map( {.Int} ) ;
if ( is_arithmetic( @numbers ) ) {
say @numbers.elems ;
}
else {
my $len = @numbers.elems ;
my $subset_number = 2 ** $len - 1 ;
my $max_len = 0 ;
for (0..$subset_number ) -> $num {
my $binstr = $num.base( 2 ) ;
my $ones = count_ones( $binstr ) ;
my $padded_bin ;
if ( $ones > 1 ) {
if ( $binstr.chars( ) < $len ) {
$padded_bin = pad_zeroes( $binstr , $len ) ;
}
else {
$padded_bin = $binstr ;
}
my @selection = find_subset( $padded_bin , @numbers ) ;
if ( is_arithmetic( @selection )) {
my $sublen = @selection.elems ;
if ( $sublen > $max_len ) {
$max_len = $sublen ;
}
}
}
}
say $max_len ;
}