I’ve been doing the Weekly
Challenges. The
latest
involved counting divisors and another joke sort. (Note that this is
open until 19 December 2021.)
Task 1: Calculator
You are given a string, $s
, containing mathematical expression.
Write a script to print the result of the mathematical expression.
To keep it simple, please only accept + - * ()
.
Well, of course, you could use eval
. You could. But that would be
boring.
The correct answer would be "use a parser module". But that would mean
learning one for each language.
So instead I implemented Dijkstra's shunting-yard
algorithm as
modified by Dave
Matuszek.
(And further modified by me to remove the references to variables.)
That's the relatively easy part. The harder part is tokenising the
input; I ended up feeding it to a regular expression which would match
on any token. Here it is in Ruby:
def operate(op,a,b)
if op=="+" then
return b+a
elsif op=="-" then
return b-a
elsif op=="*" then
return b*a
end
end
def exval(expr)
A list of operators, in increasing precedence order.
op=["(",")","+","-","*"]
opp=Hash.new
What a number looks like.
rec=["-?[0-9]+"]
Add to that list, what each operator looks like.
op.each_with_index do |o,i|
opp[o]=i
rec.push('\\' + o)
end
Now we have a single regexp which will match any one token.
ret=Regexp.new("(" + rec.join("|") + ")")
Also one for matching numbers.
ren=Regexp.new("^" + rec[0] + "$")
Initialse the two stacks.
opstack=[]
valstack=[]
Iterate over the matches to get individual tokens.
expr.scan(ret).each do |ta|
token=ta[0]
If it's a number, push it to valstack
.
if token.match(ren) then
valstack.push(token.to_i())
If it's a left paren, push it to opstack
.
elsif token == "(" then
opstack.push(token)
If it's a right paren, evaluate the op and val stacks until we get
down to the matching left paren, which we discard.
elsif token == ")" then
while opstack[-1] != "(" do
valstack.push(operate(opstack.pop(),valstack.pop(),valstack.pop()))
end
opstack.pop()
If it's an operator, then while there's something in the opstack and
the top of the opstack is not lower priority than this, evaluate the
val and op stacks. Then push to opstack
.
elsif opp.has_key?(token) then
while opstack.length>0 && opp[opstack[-1]] >= opp[token] do
valstack.push(operate(opstack.pop(),valstack.pop(),valstack.pop()))
end
opstack.push(token)
else
print("bad token")
end
end
Once we've got to the end of the tokens, unwind the stacks until
there's just one value left.
while opstack.length>0 do
valstack.push(operate(opstack.pop(),valstack.pop(),valstack.pop()))
end
return valstack[0]
end
Rust gets more complicated because that push()
line implies multiple
potentially-simultaneous accesses to the same stack, so that ended up
needing explicit temporary variables. (Really I should have moved the
abstraction up a bit and written operate
to take opstack
and
valstack
as parameters.) And I didn't try this in PostScript at all;
the stacks would be readily doable, but the input parsing would be a
pain since it lacks a regexp engine and I'd have to do "proper"
tokenisation.
No, I am not going to write a regexp engine in PostScript.
Probably.
Task 2: Stealthy Number
You are given a positive number, $n
.
Write a script to find out if the given number is Stealthy Number.
A positive integer N is stealthy, if there exist positive integers a, b, c, d such that a * b = c * d = N and a + b = c + d + 1.
Interestingly, the stealthy numbers are also the
bipronics (of the form x × (x+1) × y ×
(y+1)
). I can almost but not quite see how that's the same thing…
This is much easier than task 1, in part because I can reuse that
factorising code from the last couple of weeks. This time it'll return
a list of sums-of-factors – so for example factorpairs(26)
would
generate (2,13)
and (1,26)
internally, then return [15,27]
.
Raku:
sub factorpairs($n) {
if ($n==1) {
return [2];
}
my @ff;
my $s=floor(sqrt($n));
if ($s*$s == $n) {
push @ff,$s*2;
$s--;
}
for (2..$s) -> $pf {
if ($n % $pf == 0) {
push @ff,$pf+($n div $pf);
}
}
push @ff,1+$n;
return @ff;
}
Then we just look through that list to see if any of the pairs of
numbers in it differ by 1. (I could sort it and use various sexy
pairwise comparison methods like rotor
, window
, etc., but this was
the way that came to mind first and it's probably no slower.)
sub is_stealthy($n) {
my @p=factorpairs($n);
if (@p.elems==1) {
return False;
}
for (0..@p.end-1) -> $ix {
for ($ix+1..@p.end) -> $iy {
if (abs(@p[$ix]-@p[$iy])==1) {
return True;
}
}
}
return False;
}
I've added a new language! Kotlin can be
compiled for the Java runtime engine, not something I've used before;
it's also the preferred language for app development on Android.
The documentation is very keen on you doing everything inside an IDE,
but at least for simple programs like this I could use the
command-line compiler, which does exist though it's buried
deep in the
documentation. (I don't need an IDE, I have emacs.) It looks pretty
similar, really; Array
s are fixed-length so I have to use a
different thing, but basically searching for "kotlin" plus whatever
I'm after seems mostly to produce sensible results, and the web site
documentation isn't bad.
(Though, just as some Rust books are very keen to say "C does it like
this, which is bad, but Rust is better", several Kotlin books are at
pains to point out how it's better than Java. I write neither C nor
Java, so I really don't care.)
fun factorpairs(n: Int): ArrayList<Int> {
if (n == 1) {
return ArrayList(2)
}
var ff=ArrayList<Int>()
var s=Math.sqrt(n.toDouble()).toInt()
if (s*s == n) {
ff.add(s*2)
s--
}
for (pf in 2..s) {
if (n % pf == 0) {
ff.add(pf+n/pf)
}
}
ff.add(n+1)
return ff
}
fun is_stealthy(n: Int): Boolean {
val p=factorpairs(n)
if (p.size == 0) {
return false
}
for (ix in 0..p.size-2) {
for (iy in ix+1..p.size-1) {
if (Math.abs(p[ix]-p[iy])==1) {
return true
}
}
}
return false
}
It doesn't so far seem very different from lots of other languages
with some degree of object orientation.
For this half of the challenge I could do PostScript again.
/factorpairs {
/nn exch def
nn 1 eq {
[ 2 ]
} {
/ff 0 array def
/s nn sqrt cvi def
s s mul nn eq {
/ff ff s 2 mul apush def
/s s 1 sub def
} if
2 1 s {
/pf exch def
nn pf mod 0 eq {
/ff ff pf nn pf idiv add apush def
} if
} for
/ff ff 1 nn add apush def
ff
} ifelse
} bind def
/is_stealthy {
/n exch def
/p n factorpairs def
/stl false def
p length 1 ne {
0 1 p length 2 sub {
/ix exch def
ix 1 add 1 p length 1 sub {
/iy exch def
p ix get p iy get sub abs
1 eq {
/stl true def
exit
} if
} for
stl {
exit
} if
} for
} if
stl
} bind def
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.