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; Arrays 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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 2300ad 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech bayern 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 essen 2024 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