diff options
| -rwxr-xr-x | challenge-076/alexander-pankoff/perl/ch-1.pl | 82 | ||||
| -rwxr-xr-x | challenge-076/alexander-pankoff/perl/ch-2.pl | 99 | ||||
| -rw-r--r-- | challenge-076/alexander-pankoff/perl/dict.txt | 56 | ||||
| -rw-r--r-- | challenge-076/alexander-pankoff/perl/grid.txt | 19 |
4 files changed, 256 insertions, 0 deletions
diff --git a/challenge-076/alexander-pankoff/perl/ch-1.pl b/challenge-076/alexander-pankoff/perl/ch-1.pl new file mode 100755 index 0000000000..f191517b4e --- /dev/null +++ b/challenge-076/alexander-pankoff/perl/ch-1.pl @@ -0,0 +1,82 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use feature qw(signatures say state); +no warnings qw(experimental::signatures); + +use Scalar::Util qw(looks_like_number); +use List::Util qw(any first); +use Memoize; + +memoize( 'is_prime' ); + +my ( $N ) = @ARGV; + +if ( $N =~ m/\D/ ) { + usage(); + exit 1; +} + +my ( $number_of_primes_used, $primes_used ) = minimum_primes( $N ); + +say $number_of_primes_used; +say 'Primes used: ' . join( ', ', @$primes_used ) if $ENV{DEBUG}; + +sub minimum_primes ( $N ) { + if ( $N < 2 ) { + die "cannot construct numbers smaller than 2 from a sum of primes"; + } + + if ( is_prime( $N ) ) { + return ( 1, [$N] ) if is_prime( $N ); + } + elsif ( $N % 2 == 0 ) { + my $prime_gen = new_prime_gen( $N ); + while ( 1 ) { + my $prime = $prime_gen->(); + if ( is_prime( $N - $prime ) ) { + return ( 2, [ $N - $prime, $prime ] ); + } + } + } + elsif ( is_prime( $N - 2 ) ) { + return ( 2, [ 2, $N - 2 ] ); + } + else { + my $is_even = $N - 3; + my ( $count, $primes_used ) = minimum_primes( $is_even ); + return ( $count + 1, [ 3, @$primes_used ] ); + } +} + +sub new_prime_gen($max) { + return sub { + state $last = 0; + $last = first { is_prime( $_ ) } ( $last + 1 ) .. $max; + return $last; + } +} + +sub is_prime ( $n ) { + + return 0 if $n <= 1; + return 1 if $n <= 3; + return 0 if any { $n % $_ == 0 } ( 2, 3 ); + + my $i = 5; + while ( $i * $i <= $n ) { + return 0 if $n % $i == 0; + $i = $i + 2; + } + + return 1; +} + +sub usage() { + say <<"END"; +$0 <N> + + Calculate the minimum number of prime numbers required, whose summation gives N + <N> a positive integer >= 2 +END +} diff --git a/challenge-076/alexander-pankoff/perl/ch-2.pl b/challenge-076/alexander-pankoff/perl/ch-2.pl new file mode 100755 index 0000000000..cb6b515851 --- /dev/null +++ b/challenge-076/alexander-pankoff/perl/ch-2.pl @@ -0,0 +1,99 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use autodie; +use feature qw(signatures say); +no warnings qw(experimental::signatures); + +use FindBin; +use List::Util qw(any none); + +my ( $gridfile, $dictfile ) = @ARGV; + +$gridfile //= $FindBin::RealBin . '/grid.txt'; +$dictfile //= $FindBin::RealBin . '/dict.txt'; + +my $dict = read_dict( $dictfile ); +my $grid = read_grid( $gridfile ); + +my %checks = ( + positive_diagonals => [ diagonals( 'positive' ) ], + negative_diagonals => [ diagonals() ], + horizontal => $grid, + vertical => [ + map { + my $index = $_; + [ map { $_->[$index] } @$grid ] + } 0 .. $#{ $grid->[0] } + ] +); + +my @out; +for my $check ( keys %checks ) { + for my $pos ( 0 .. $#{ $checks{$check} } ) { + my $line_chars = $checks{$check}->[$pos]; + my $forwards_line = join( '', @$line_chars ); + my $backwards_line = join( '', reverse @$line_chars ); + my %lines = ( forwards => $forwards_line, backwards => $backwards_line ); + for my $line ( keys %lines ) { + my @res = check_line( $lines{$line}, $dict ); + push @out, @res; + say "found " . join( ", ", @res ) . " $line in $check $pos" if $ENV{DEBUG} && @res; + } + } +} + +say join( "\n", @out ); +say 'Found ' . @out . ' entries'; + +sub diagonals { + my ( $positive ) = @_; + + my $height = $#{$grid}; + my $width = $#{ $grid->[0] }; + + my @start_points = map { [ $_, $positive ? 0 : $width ] } 0 .. $height - 1; + push @start_points, map { [ $height, $_ ] } $positive ? 0 .. $width : reverse 0 .. $width; + + my @diags; + for my $point ( @start_points ) { + my @diag; + my ( $row, $col ) = @$point; + while ( $row >= 0 && ( $positive ? $col <= $width : $col >= 0 ) ) { + push @diag, $grid->[$row][$col]; + $row--; + $positive ? $col++ : $col--; + } + push @diags, \@diag; + } + + return @diags; +} + +sub check_line ( $line, $dict ) { + grep { $line =~ m/$_/i } @$dict; +} + +sub read_dict($filename) { + open( my $fh, '<', $filename ); + chomp( my @out = <$fh> ); + return \@out; +} + +sub read_grid($filename) { + open( my $fh, '<', $filename ); + chomp( my @lines = <$fh> ); + return [ map { [ split( ' ', $_ ) ] } @lines ]; +} + +sub usage() { + say <<"END"; +$0 [GRIDFILE] [DICTFILE] + + This programm takes two file names. A GRIDFILE containing a grid of + characters and a DICTFILE that contains a list of words. + It will print out all words from DICTFILE that can be found in the grid by + looking both orthogonally and diagonally, backwards as well as forwards. + +END +} diff --git a/challenge-076/alexander-pankoff/perl/dict.txt b/challenge-076/alexander-pankoff/perl/dict.txt new file mode 100644 index 0000000000..6ecc2f6a73 --- /dev/null +++ b/challenge-076/alexander-pankoff/perl/dict.txt @@ -0,0 +1,56 @@ +argos +constitution +margo +patna +traci +tracie +aimed +align +antes +arose +ashed +blunt +blunts +broad +buries +clove +cloven +constitution +constitutions +croon +depart +departed +enter +filch +garlic +goats +grieve +grieves +hazard +liens +malign +malignant +malls +midst +ought +ovary +parted +pudgiest +quash +quashed +raped +ruses +shrine +shrines +social +socializing +spasm +spasmodic +succor +succors +theorem +theorems +virus +viruses +wigged +foobarbaz diff --git a/challenge-076/alexander-pankoff/perl/grid.txt b/challenge-076/alexander-pankoff/perl/grid.txt new file mode 100644 index 0000000000..31cf2e0fd8 --- /dev/null +++ b/challenge-076/alexander-pankoff/perl/grid.txt @@ -0,0 +1,19 @@ +B I D E M I A T S U C C O R S T +L D E G G I W Q H O D E E H D P +U S E I R U B U T E A S L A G U +N G N I Z I L A I C O S C N U D +T G M I D S T S A R A R E I F G +S R E N M D C H A S I V E E L I +S C S H A E U E B R O A D M T E +H W O V L P E D D L A I U L S S +R Y O N L A S F C S T A O G O T +I G U S S R R U G O V A R Y O C +N R G P A T N A N G I L A M O O +E I H A C E I V I R U S E S E D +S E T S U D T T G A R L I C N H +H V R M X L W I U M S N S O T B +A E A O F I L C H T O D C A E U +Z S C D F E C A A I I R L N R F +A R I I A N Y U T O O O U T P F +R S E C I S N A B O S C N E R A +D R S M P C U U N E L T E S I L |