Random Problem Generation
12 January 2023
This week I tackle the randomly selected first problem from the final chapter of the book and take a first stab at binary arithmetic!
Mon 1/9/23
Hesitantly, I reach for the padlock icon and give it a nervous click. Doing so will randomly select a new problem for me to solve and I kid you not it spits out 17.1. That’s right, on week 2 of my challenge I am now going to attack the first of the ‘Additional Hard Problems’. So it goes when you entrust your fate to the whims of random number generation.
Wed 1/11/23
Having thought about this on-and-off throughout the week, my instinct is to do binary representation of the two numbers and then mash them together with some binary-addition logic that is built without using arithmetic operators. I could build this using these functions:
- a function that converts a number to a binary representation.
- a function that converts binary representation to a number.
- a function that sums two binary representation of numbers.
This is not something I’ve spent a whole lot of time learning about, and so the third function might be as simple as a function that increments a binary number however many times.
As an aside, I came up with a solution that totally ignores the spirit of the question:
Anyway, I learned from reading about The Absolute Essentials for Bit Manipulation in JavaScript that javascript supports quickly converting between numbers and binary:
This deals with string representations of binary which isn’t ideal, but it’ll do for now. Reading the section about summing two binary numbers working just like summing two base-10 numbers makes a lot of sense. I need to deal with the mashing of two binary digits and being able to decide whether I am carrying a value from one column to the next.
Let’s own the string representation of binary numbers for now, so our function’s signature will look like:
Hm, I wanted to kick things off by ensuring the strings were the same length but I’m actually not show how I would do that without using some form of arithmetic.
Between the two binary numbers, whichever is longer will dictate how many times I need to iterate and decide what the output is for that column. I’m going to use a forEach here because a normal for loop in javascript uses ++
which isn’t allowed under the terms of the problem so I’m going to turn these strings into character arrays and plan to work with an output character array that I’ll translate when I’m done building it. Because addition is commutative, I don’t need to care about the order of the input numbers, just which one is larger:
Next up I will iterate over arrayLonger
and then consult arrayShorter
to determine which value gets appended to arrayResult
(remembering that the output is going to be backwards, so I need to reverse it before returning). This is what I came up with first:
It is a little clunky to be sure, but the logic is all there (I’m taking advantage of the similarity between the two cases where one value is 1
and the other is 0
by making them the default ‘fall-through’ case to cut down on code). At least I thought it was until I saw that the output was incorrect. This is because I overlooked two things: One is that arrayShorter
can be smaller than arrayLonger
and so sometimes reading a value from the former will come out as undefined
when I want it to be 0
. Two is that after all’s said and done, I may end up needing an additional column beyond what was originally slated by the forEach loop so after the loop I consult the carry
variable and if it is true I add a 1
into the final column. Due to the nature of binary numbers, this can happen at most once while processing a sum.
I also noticed that I had an additional bug where I neglected to add carry = false
in the double-0 while carry is true section of the if statements.
Here’s today’s final product: