RogerBW's Blog

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.