I’ve been doing the Weekly
Challenges. The
latest
involved prime counting and list selections. (Note that this ends
today.)
Task 1: Count Primes
You are given a positive integer, $n.
Write a script to find the total count of primes less than or equal to the given integer.
It's been a while since we had a prime number problem - I think the
last one was #198 part 2, which in fact is nearly the same challenge.
The languages in my chosen collection that have prime number
generation readily available are Ruby (in core) and Perl (via
Math::Prime::Utils
); for everything else I've written a lightly
optimised sieve of Eratosthenes, which by its nature finds all primes
with a given upper bound.
(Yes, including Raku - which has is-prime
, but running that on every
number is a lot slower.)
Perl:
use Math::Prime::Util qw(primes);
sub countprimes($l) {
return scalar @{primes($l)};
}
Task 2: Box Coins
You are given an array representing box coins, @box
.
Write a script to collect the maximum coins until you took out all boxes. If we pick box[i]
then we collect the coins $box[i-1] * $box[i] * $box[i+1]
. If $box[i+1]
or $box[i-1]
is out of bound then treat it as 1 coin.`
A slightly tricky parse, but it made sense with the examples. In each
loop, pick one entry in the list. Add to the running total the product
of that entry and its two neighbours. Remove that entry (but not the
neighbours).
I found this quite reminiscent of 221 part 2 (a search that involves
dropping each member in turn from the successor list), though this
time I want to be exhaustive, so I use a depth-first search for
simplicity. (Also, 221 was the challenge for which I skipped several
of my usual languages.)
I'm a bit sloppy about defining extra variables here. Also some
languages get Pair and similar types rather than an array with
disparate elements.
JavaScript:
function boxcoins(ints) {
let mx = 0;
let stack = [ [ ints, 0 ] ];
while (stack.length > 0) {
const x = stack.pop();
const t = x[0];
const tot = x[1];
if (tot > mx) {
mx = tot;
}
for (let i = 0; i < t.length; i++) {
let p = t[i];
if (i > 0) {
p *= t[i - 1];
}
if (i < t.length - 1) {
p *= t[i + 1];
}
const stot = tot + p;
let tt = [];
for (let ix = 0; ix < t.length; ix++) {
if (i != ix) {
tt.push(t[ix]);
}
}
stack.push([tt, stot]);
}
}
return mx;
}
if (boxcoins([3, 1, 5, 8]) == 167) {
process.stdout.write("Pass");
} else {
process.stdout.write("FAIL");
}
process.stdout.write(" ");
if (boxcoins([1, 5]) == 10) {
process.stdout.write("Pass");
} else {
process.stdout.write("FAIL");
}
process.stdout.write("\n");
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.