Leetcode 51: N-Queens

The n-queens problem is about arranging n queens on an n x n chessboard such that no queen attacks another queen.

It turns out that this is quite a common example for using a backtracking algorithm. However my initial solution involved going through permutations of the column positions for each queen. Here are my whiteboard notes and source code for this solution and then my implementation of a more traditional backtracking solution further down:

And here is my explanation and implementation of backtracking solution (iterative):

Posted in programming | Tagged , , | Leave a comment

Structured bindings in C++17

Structured bindings are a useful new feature in c++17. They are particularly handy where you have multiple return values. Here are some examples showing how things have evolved over different versions of c++:

Posted in programming | Tagged | Leave a comment

Logic gates

Here are some basic logic gates and how we can combine them to get an XOR:

In order to perform addition of arbitrary length binary numbers we first start with creating a Half Adder, which can add two single binary bits to result in a single two bit binary number. We can then create a Full Adder, which allows us to add three binary bits that results in a single two bit binary number. We need to add three bits as that allows to add two bits of two numbers and a carry bit. Next we chain together a sequence of full adders to add two binary numbers with any number of bits. We can optimise this to use bitwise operators to do ANDs, XORs and bitshifts to do the addition and carry operations on a sequence of bits. We can multiply numbers by doing repeated shift and add operations. Here are my whiteboard notes for all of these:

Posted in programming | Tagged , | Leave a comment

C++ Lambda Expressions

Here are some whiteboard notes I created on c++ lambda expressions. I should create a digital/html version of this reference.

Posted in programming | Tagged , | Leave a comment

Leetcode 50: Pow(x, n)

A few fiddly cases of exponentiation to deal with in this problem. A simple O(n) solution is fairly straightforward but that will not pass some of the leetcode test cases. An implementation that uses binary exponentiation will work in O(log n) time and will pass the leetcode tests. One other fiddly edge case was the test case that used INT_MIN as the exponent, which does not allow us to *= -1 for negative exponents, so I had to use long int to expand the range of the exponent. My original binary exponentiation implementation was messy, so the elegant solution below took inspiration from https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/

Here are my whiteboard notes:

And here is the c++ source code:

Posted in programming | Tagged , , | Leave a comment

SudokuSolverX Android app

I’ve created a Sudoku puzzle solving app. See details here:

Posted in programming | Tagged | Leave a comment

Leetcode 49: Group Anagrams

The most efficient way I could think of to solve this problem was to use an unordered_multimap to store sorted strings as keys and the original strings as values. This will then automatically provide the groupings we need. Here are my whiteboard notes:

And the C++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 48: Rotate Image

The idea with my solution is that you work your way through layers of the box, starting with the outside layer and then moving inwards. For each layer we step through four points at a time, starting at the corners and then working our way around. In the solution below I store those four points in an array and then I call std::rotate() to shift the numbers. I felt this was logically slightly simpler. An optimisation on this would be to use a single temporary variable to store one of the points and copy the other points to each other.

Here are my whiteboard notes:

And here is the c++ source code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 46: Permutations

The obvious way to solve this is to repeatedly call next_permutation() from the standard library. Another way to solve it is to implement what next_permutation() does and I have done that in a previous solution:

I thought I would have a go at solving this by using the nature of recursive calls to go through combinations. The following is a logically simple but not very efficient way of doing it:

And here is the source code:

A more efficient solution is https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ although this does not generate outputs in lexicographical order.

Posted in programming | Tagged , , | Leave a comment

Origins of the C++ name

In Stroustrup’s “A Tour of C++”, it says that C++ takes its name from:

  • The increment operator (++) combined with C programming language name.
  • George Orwell’s novel “1984”.

The first was obvious and expected but the second was surprising, so I did some digging around to find more details.

In the novel “1984”, “Newspeak” was the language of English socialism. Newspeak had three vocabularies. The A vocabulary was for everyday use, the B vocabulary was for political usage and:

“The C vocabulary was supplementary to the others and consisted entirely of scientific and technical terms” – 1984 – George Orwell, p.322

The 1984 novel also describes the meaning of “doubleplus”:

“any word … could be strengthened by the affix plus-, or, for still greater emphasis, doubleplus-.” – 1984 – George Orwell, p.315

Posted in programming | Tagged , | Leave a comment