# RogerBW's Blog

 The Weekly Challenge 143: Stealthy Calculator 15 December 2021 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 { if (n == 1) { return ArrayList(2) } var ff=ArrayList() 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. Search 10 per page 20 per page 50 per page 100 per page Archive Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult Special All book reviews, All film reviews
Produced by aikakirja v0.1