Prime Factorization, Water, BQN

This is the easy bit. Specifically, we can think of the sub-problems:

1. What are the factors of a number?
2. What is the list of the first n prime numbers? Or given any number is it a prime?

Surprisingly, the questions are interlinked, since a number is prime, if it only has two factors.

Here is some sample Common Lisp solution to this, included for fun:

(defun factors (n)
  (remove-if-not (lambda (x) (eq (mod n x) 0)) (range 2 n 1)))

(defun is-prime? (n)
  (eq 0 (length (factors n))))

(defun prime-factors (n)
  (remove-if-not #'is-prime? (factors n)))

This is how I put it together in BQN, with tacitness not being an immediate aim:

P ← {((2=(+´0=(1+↕)⊸|))¨v)/v←↕⊸(⊣/˜0=|) 𝕩}

You can get some of this solution out of BQNCrate too.

As per the original question, there is more to do. We need the full prime factorization: the number of occurences of each prime that will make the original number.

The logic for this is clear, but at first glance, it seemed to be hard to do in APL. What I mean is, I don't want to use conditionals like "if" and loops like "while". Just pure array programming.

Given this difficulty, I wanted to get the simple functional version clear in my mind first. Functional, in the terms of Lisp and StandardML is different from Functional as understood in the APL family. Nevertheless, for clarity, I implemented it in Common Lisp.

(defun -pf (n pfs acc)
  (if (or (eq n 1) (endp pfs))
     acc
    (if (eq (mod n (car pfs)) 0)
        (-pf (/ n (car pfs)) pfs (push (car pfs) acc))
        (-pf n (cdr pfs) acc))))

(defun pf (n)
  (-pf n (prime-factors n) '()))

Aside: by the way, if you want to make that look more "functional", this is a good way. Of course, Emacs has you covered for that.

But, see, the more I look at that, the more I was convinced that it was going to be impossible to do it in pure APL style. To be clear, BQN does offer imperative control flow, but if I wanted to use while and if, I would have been programming in Python!

Then it clicked, and here it is, again in non-optimized (non tacit) form:

{+´«(⌊⊸=¨((𝕩×⍟(↕⌊𝕩⋆⁼120) 1)÷˜120))}¨ (P 120)

It is not made into a proper function, but that is beside the point here, focus on the logic.

How does this work?

1. Apply the function on the left, to all prime factors of 120.
2. The repeat ⍟ function is used with a list of numbers 0, 1, 2, … log_p(n). We are basically repeating the original function, which is 120/p, a number of times, in an array, so that all results are saved.
3. Then we look at the corresponding numbers and see which of them are integers, that is remain the same when floor'ed. These integers are powers of the prime p which divide n cleanly.
4. Now, we simply count the number of entries, adjusting by 1 for the first entry. This « could have been avoided by simply using 1+↕ instead of simple range.

Now, per the terms of the original problem, we need to join these two lists with a simple (×´⋆).

This was a completely new concept to me! The problem pretty much asks you to make an histogram and then pour water all over it. How about that!

Once I understood what was going on here, I wanted to visualize it. I took this as an opportunity to explore Manim, the awesome animation library created by the famous math YouTuber 3Blue1Brown. His videos are really good at explaining Math and I would highly recommend you to check it out.

Anyway, after a bunch of fiddling around, I got it to work. Word of advice, the easiest option is to go with the Docker image option and the Jupyter notebook so that can preview videos inline directly.

Here is the final video:

And, for completeness, here is the corresponding code for Manim:

class WaterHist(Scene):
  def construct(self):

      text = MarkupText("<i>Pouring water on a histogram</i>")
      self.play(Write(text))

      text.generate_target()
      text.target.shift(3*UP + 1.5*LEFT)
      self.play(MoveToTarget(text))

      bars = []
      start = 5*LEFT + DOWN
      rect1 = Rectangle(width=1.0, height=5).move_to(start)
      bars.append(rect1)
      self.play(Create(rect1))

      nums = [4, 3, 2, 3, 6, 3, 4, 2, 4, 7]
      for idx, i in enumerate(nums):
          rect = Rectangle(width=1.0, height=i).move_to(start + (idx+1)*RIGHT).align_to(rect1, DOWN)
          bars.append(rect)
          self.play(Create(rect))

      self.wait(2)

      points1 = [[0, 0, 0], [0, -1, 0], [1, -1, 0], [1, -2, 0], [2, -2, 0], [2, -3, 0], [3, -3, 0], [3, -2, 0], [4, -2, 0], [4, 0, 0]]
      water1 = Polygon(*points1, stroke_width=4).move_to(start+UP+2.5*RIGHT)
      water1.set_fill(BLUE, opacity=0.5)

      points2 = [[0, 0, 0], [0, -3, 0], [1, -3, 0], [1, -2, 0], [2, -2, 0], [2, -4, 0], [3, -4, 0], [3, -2, 0], [4, -2, 0], [4, -2, 0], [4, 0, 0]]
      water2 = Polygon(*points2, stroke_width=4).move_to(0.5*UP+2.5*RIGHT)
      water2.set_fill(BLUE, opacity=0.5)
      self.play(DrawBorderThenFill(water1), DrawBorderThenFill(water2))

      self.wait(2)

There is some heavy hardcoding going on in here. Generalizing this to work for any given array of integers is left as an exercise to the reader!

Animations aside, how do we calculate the exact amount of water in the histogram? The algorithm, it turns out is quite simple. You can look at the other answers in the original Stack Exchange question.

At this juncture, I would recommend looking at this video: https://www.youtube.com/watch?v=ftcIcn8AmSY which is a talk given by Guy Steele on 4 different ways to solve this same problem. The talk goes into a broader topic of programming abstraction giving you the freedom to express solutions without thinking about explicitly parallelizing it while also enabling the compiler to freely parallelize.

From the talk, for example, Guy Steele is quite opposed to the normal for loop. Why? Because the moment you gave a state accumulator, the moment you have written down the infamous i of the for loop, you have locked your solution into a single-threaded one. His point is that the tools of the last 70 years have evolved to the hardware of that time. Now, today, in a world of multi-processing, it makes no sense to continue with those abstractions, yet we do it!

His point is very relevant for APL like programming, since the APL abstraction does exactly what he prescribes. Funnily enough, APL was originally invented in 1960s (in IBM Research, too)!

With this context, the most straightforward solution in BQN is Guy Steele's 4th presented option. The option that he advocates for, the option with least amount of structural lock in, the option with the greatest amount of flexibility, is the one that naturally falls out of APL!

And in 11 characters, ladies and gentlemen!

(⌈`⌊⌈`∘⌽)-⊢

This has to be simply the most elegant solution to any problem I have seen. Ken Iverson said Notation as a Tool of Thought, and I see the light now. If I had time, I would present a video animated using manim explaining this solution. For now though, I have already spent enought time, so you will have to understand this on your own!

There is still some effort needed to convert the components I have presented into tacit form and put them togther to get the final solution. But, I leave that as an exercise to the diligent reader. My heart is full and I am contended today.