aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-117/polettix/blog.txt1
-rw-r--r--challenge-117/polettix/blog1.txt1
-rw-r--r--challenge-117/polettix/ch-1.input14
-rw-r--r--challenge-117/polettix/perl/ch-1.pl14
-rw-r--r--challenge-117/polettix/perl/ch-2.pl148
-rw-r--r--challenge-117/polettix/raku/ch-1.raku9
-rw-r--r--challenge-117/polettix/raku/ch-2.raku22
7 files changed, 209 insertions, 0 deletions
diff --git a/challenge-117/polettix/blog.txt b/challenge-117/polettix/blog.txt
new file mode 100644
index 0000000000..d03567fdb7
--- /dev/null
+++ b/challenge-117/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/06/16/pwc117-missing-row/
diff --git a/challenge-117/polettix/blog1.txt b/challenge-117/polettix/blog1.txt
new file mode 100644
index 0000000000..c0643136c8
--- /dev/null
+++ b/challenge-117/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/06/17/pwc117-find-possible-paths/
diff --git a/challenge-117/polettix/ch-1.input b/challenge-117/polettix/ch-1.input
new file mode 100644
index 0000000000..5b9d9ab1ce
--- /dev/null
+++ b/challenge-117/polettix/ch-1.input
@@ -0,0 +1,14 @@
+11, Line Eleven
+1, Line one
+9, Line Nine
+13, Line Thirteen
+2, Line two
+6, Line Six
+8, Line Eight
+10, Line Ten
+7, Line Seven
+4, Line Four
+14, Line Fourteen
+3, Line three
+15, Line Fifteen
+5, Line Five
diff --git a/challenge-117/polettix/perl/ch-1.pl b/challenge-117/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..63b264889c
--- /dev/null
+++ b/challenge-117/polettix/perl/ch-1.pl
@@ -0,0 +1,14 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+
+sub missing_row ($file) {
+ open my $fh, '<', $file or die "open('$file'): $!\n";
+ my %all = map {$_ => 1} 1 .. 15;
+ delete $all{s{\A (\d+) .*}{$1}rmxs} while <$fh>;
+ return keys %all;
+}
+
+say missing_row($ARGV[0]);
diff --git a/challenge-117/polettix/perl/ch-2.pl b/challenge-117/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..972a812b5f
--- /dev/null
+++ b/challenge-117/polettix/perl/ch-2.pl
@@ -0,0 +1,148 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+
+use constant THRESHOLD => 10;
+
+sub find_possible_paths ($N) {
+ my @solution = (['']);
+ for my $i (1 .. $N) {
+ my @new_iteration = [];
+ for my $j (0 .. $#solution) {
+ my $previous = $solution[$j];
+ my $left = $new_iteration[$j];
+ my $right = $new_iteration[$j + 1] = [];
+ for my $p ($previous->@*) {
+ push $left->@*, $p . 'L';
+ push $right->@*, $p . 'R';
+ }
+ for my $p ($left->@*) {
+ push $right->@*, $p . 'H';
+ }
+ }
+ @solution = @new_iteration;
+ }
+ return $solution[-1]->@*;
+}
+
+sub combinations_iterator ($k, @items) {
+ my @indexes = (0 .. ($k - 1));
+ my $n = @items;
+ return sub {
+ return unless @indexes;
+ my (@combination, @remaining);
+ my $j = 0;
+ for my $i (0 .. ($n - 1)) {
+ if ($j < $k && $i == $indexes[$j]) {
+ push @combination, $items[$i];
+ ++$j;
+ }
+ else {
+ push @remaining, $items[$i];
+ }
+ }
+ for my $incc (reverse(-1, 0 .. ($k - 1))) {
+ if ($incc < 0) {
+ @indexes = (); # finished!
+ }
+ elsif ((my $v = $indexes[$incc]) < $incc - $k + $n) {
+ $indexes[$_] = ++$v for $incc .. ($k - 1);
+ last;
+ }
+ }
+ return \@combination;
+ }
+}
+
+sub basic_case_iterator_longer ($N) {
+ my $N2 = 2 * $N;
+ my $cs;
+ return sub {
+ $cs //= combinations_iterator($N, 0 .. $N2 - 1);
+ CANDIDATE:
+ while (my $Ls = $cs->()) {
+ my @sequence = ('H') x $N2;
+ @sequence[$Ls->@*] = ('L') x $N;
+ my $count = 0;
+ for my $item (@sequence) {
+ $count += $item eq 'L' ? 1 : -1;
+ next CANDIDATE if $count < 0;
+ }
+ return join '', @sequence;
+ }
+ return;
+ };
+}
+
+sub basic_case_iterator ($N) {
+ --$N;
+ my $N2 = 2 * $N;
+ my $cs;
+ return sub {
+ $cs //= combinations_iterator($N, 0 .. $N2 - 1);
+ CANDIDATE:
+ while (my $Ls = $cs->()) {
+ my @sequence = ('H') x $N2;
+ @sequence[$Ls->@*] = ('L') x $N;
+ my $count = 1; # we will force starting with an L
+ for my $item (@sequence) {
+ $count += $item eq 'L' ? 1 : -1;
+ next CANDIDATE if $count < 0;
+ }
+ return join '', 'L', @sequence, 'H';
+ }
+ return;
+ };
+}
+
+sub expand_with_Rs_iterator ($sequence) {
+ my $indexes;
+ my @parts;
+ my ($i, $n, $max);
+ return sub {
+ if (! $indexes) { # initialize
+ @parts = grep {length} split m{(LH)}mxs, $sequence;
+ $indexes = [grep {$parts[$_] eq 'LH'} 0 .. $#parts];
+ $n = $indexes->@*;
+ $max = 0;
+ $max = ($max << 1) | 1 for 1 .. $n;
+ $i = 0;
+ return $sequence;
+ }
+ return if $i >= $max;
+ ++$i;
+ my @Rs = split m{}mxs, sprintf "%0${n}b", $i;
+ my @copy = @parts;
+ for my $j (0 .. $#Rs) {
+ next unless $Rs[$j];
+ $copy[$indexes->[$j]] = 'R';
+ }
+ return join '', @copy;
+ };
+}
+
+sub find_possible_paths_iterator ($N) {
+ my ($basic_it, $fit);
+ return sub {
+ $basic_it //= basic_case_iterator($N);
+ while ('necessary') {
+ $fit //= expand_with_Rs_iterator($basic_it->() // return);
+ if (my $item = $fit->()) { return $item }
+ $fit = undef;
+ }
+ };
+}
+
+my $n = shift // 2;
+my $use_iterator = $ENV{USE_ITERATOR} ? 1
+ : defined($ENV{USE_ITERATOR}) ? 0
+ : $n > THRESHOLD;
+if ($use_iterator) {
+ my $it = find_possible_paths_iterator($n);
+ while (my $c = $it->()) { say $c }
+}
+else {
+ say for find_possible_paths($n);
+}
diff --git a/challenge-117/polettix/raku/ch-1.raku b/challenge-117/polettix/raku/ch-1.raku
new file mode 100644
index 0000000000..e9e1bbeeb6
--- /dev/null
+++ b/challenge-117/polettix/raku/ch-1.raku
@@ -0,0 +1,9 @@
+#!/usr/bin/env raku
+use v6;
+
+sub missing-row ($file) {
+ constant All = set(1 .. 15);
+ (All (-) set($file.IO.lines.map({+ S/^ (\d+) .*/$0/}))).keys;
+}
+
+put missing-row(@*ARGS[0]);
diff --git a/challenge-117/polettix/raku/ch-2.raku b/challenge-117/polettix/raku/ch-2.raku
new file mode 100644
index 0000000000..d6e08edc65
--- /dev/null
+++ b/challenge-117/polettix/raku/ch-2.raku
@@ -0,0 +1,22 @@
+#!/usr/bin/env raku
+use v6;
+
+sub find-possible-paths ($N) {
+ my @solution = [''],;
+ for 1 .. $N -> $i {
+ my @new_iteration = [],;
+ for 0 ..^ @solution.elems -> $j {
+ my $previous = @solution[$j];
+ my $left = @new_iteration[$j];
+ my $right = @new_iteration[$j + 1] = [];
+ $left.push: (@solution[$j].flat X~ 'L').Slip;
+ $right.push: (@solution[$j].flat X~ 'R').Slip;
+ $right.push: (@new_iteration[$j].flat X~ 'H').Slip;
+ }
+ @solution = @new_iteration;
+ $i.note;
+ }
+ return @solution[*-1].flat;
+}
+
+sub MAIN ($N = 2) { find-possible-paths($N).join(', ').put; }
generated by cgit (git 2.34.1) at 2026-07-04 21:35:03 +0000