9 Posts

The following presents my solution for the Longest Chain of Character Removals problem.

Problem Statement

You are given a library with n words (w[0], w[1], ...,w[n-1]). You choose a word from it, and in each step, remove one letter from this word only if doing so yields another word in the library. What is the longest possible chain of these removal steps?

Constraints:

  • 1 <= n <= 50000
  • 1 <= the length of each string in w <= 50
  • Each string is composed of lowercase ascii letters only

The function should take in an array of strings w as its argument and should return a single integer representing the length of the longest chain of character removals possible.

Example input/output

a
b
ba
bca
bda
bdca

Calling the function on the input above should output 4. The longest possible chain is "bdca" -> "bca" -> "ba" -> "a".

Solution

I solved this problem using dynamic programming (DP):

1. Sort the input dictionary by size, from shortest to longest
2. Create a dynamic programming table, which I call chainLength of size n. Define chainLength[i] to be the length of the longest chain of character removals that can be formed starting with w[i] in the sorted input dictionary.
3. Use an unordered_map (hash table) to keep track of words in the input dictionary that have already been processed by the DP algorithm. The key value is the word from the input dictionary and the mapped value is the longest possible chain starting with that word (same value as stored in the DP table)
4. Iterate through every word in the sorted input dictionary and find the longest possible chain up to that word. In other words, fill up from DP table going from index 0 to n-1.
5. To calculate chainLength[i] in the dynamic programming table, iterate through each letter of w[i] and check if removing that letter would yield another word in the dictionary. This can be done in constant time using the hash table. If removing a letter from w[i] yields w[j], then it is possible to create a chain with length 1 + chainLength[j]. (Note that in this scenario j will always be less than i because the input is sorted by length and so the DP algorithm will process the shorter words first) By doing this for every letter, we can find the longest possible chain starting with w[i].
5. The result is the maximum value in the dynamic programming table chainLength

Code

I recently solved an interesting programming challenge, called Friend Circles, and wanted to share my solution, which was implemented in C++.

Problem statement

There are N students in a class. Some of them are friends, while some of them are not. Their friendship is transitive in nature, i.e., if A is a friend of B and B is a friend of C, then A is also a friend of C. A friend circle is a group of students who are directly or indirectly friends.

You have to complete a function int friendCircles(vector<std::string> friends) which returns the number of friend circles in the class. Its argument, friends, is an array of strings. However, for the sake of this problem, friends should be viewed as a 2-dimensional array of characters (the input has N strings and each string has N characters). Therefore, friends is a NxN matrix which consists of characters 'Y' or 'N'. If friends[i][j] = 'Y', then students i and j are friends which each other, otherwise not. You have to return the total number of friend circles in the class.

Constraints:

  • 1 <= N <= 300
  • Each element of matrix friends will be either'Y' or 'N'
  • Number of row and columns in friends will be equal
  • friends[i][i] = 'Y', where 0 <= i < N
  • friends[i][j] = friends[j][i]

Example inputs/return values

Example 1

YYNN
YYYN
NYYN
NNNY

should output 2. There are two pairs of friends (0, 1) and (1, 2). So (0, 2) is also a pair of friends by transitivity. So the first friend circle contains (0, 1, 2) and the second friend circle contains only student 3.

Example 2

YNNNN
NYNNN
NNYNN
NNNYN
NNNNY

should output 5 because no student is friends with any other. So each student forms its own friend circle, for a total of 5.

Solution (C++)

Note that, since friends is an NxN matrix where friends[i][j] = friends[j][i], the input can be thought of as an undirected graph. Each student represents a node in the graph and there is an edge between two nodes if the corresponding students are friends. If there is a path in the graph from student A to student B, then, by transitivity, students A and B must be in the same friend circle. Therefore, we can use a DFS/BFS to find each student in a friend circle. The general algorithm for this problem can be represented as follows:

1. Create an array to keep track of whether a student has been visited by the DFS/BFS. This can also be thought of to represent whether or not that student has already been placed in a friend circle.
2. Starting with the first student, use a DFS to find each student in the same friend circle. Mark each student as being "visited".
3. Increment the number of friend circles.
4. Repeat steps 2 and 3, starting with the next student that is not already part of a friend circle.

(For those more familiar with graph theory, note that each friend circle would constitute a connected component on the graph. Therefore, this problem can be abstracted out to be the same as "How to find the number of connected components in an undirected graph". )

In my time working with Linux, there have been a number of very useful "obscure" commands that I've discovered. These are commands that I'll use pretty frequently. However, the problem is that they can be difficult to memorize. As a result, whenever I need to use the command again, I end up google searching to find out exactly what the syntax for it is.

I'm creating this post mostly for personal use. I wanted to consolidate all of these commands into a single location so that I don't have to search the internet each time I need to use one. I hope others find it useful. Feel free to comment with your own if you want to share!

Really clear the terminal in PuTTY

When working in PuTTY, the clear command doesn't truly clear the terminal, it just shifts all of the text up. One alternative is the reset command, but it completely re-initializes the terminal which isn't what I want. What does work is:

I don't know why it works, but it does. I've only ever used it on PuTTY, but I hear it works on many other terminals, including OSX and most *nix terminals.

Replace a string in multiple files in a directory

Replace oldString with the string you want to replace, and set newString to be whatever you want to replace it with. Set directory to specify which directory this command will act on (it works recursively).

This command will search through every file in directory and replace all occurrences of oldString with newString.

Kill all processes that contain a string in the name

There are two methods for this.

Replace string with the text you are searching for in the processes. Either of these commands will then kill all processes that have string in their name.

Remove extra carriage return from DOS (if you don't have dos2unix)

DOS such as Windows append an extra carriage return for a newline, whereas Linux does not. This can be an issue. dos2unix is a useful that can convert DOS/MAC text to Linux text, but it's not available on every machine. This function will do the trick as well:

This takes the file infile, removes all of the extra carriage returns ('\r'), and outputs it to a new text file outfile. Warning: This will remove all of the carriage returns in the file, not just the ones from newline. This command is nice because it keeps the original in case you ever need it again.

Find all files that contain specified text

This command searches the specified directory (recursively) and outputs all of the files that contain the specified text. To clarify, this command searches the contents of the files themselves for the specified search text. It does not just search for the file names.

Count the number of processes containing specified string in process name

This command will output the number of processes that contain searchstring in the process name:

A short explanation: ps aux prints all currently running processes. The grep command filters out all processes that don't have the word searchstring in them. The [] brackets remove command itself so that it is not counted as a running process. The -c flag specifies the count command.

Display date and time in terminal

Outputs the date and time in the top right corner of the terminal.

This article discusses programming a GPIO Driver on a Raspberry Pi 2 using C. If you haven't already, check out the introductory post. You will also need the Broadcom BCM2835 datasheet. The Raspberry Pi 2 uses a BCM2836 chip, but at the time of writing this post the datasheet for the BCM2836 has not been released. However, the BCM2835 and BCM2836 have the same underlying architecture. For the scope of this article, the only difference between the two is that the addresses of the registers are different.

The full source code for the GPIO Driver can be found near the bottom of this post, or by clicking here

Accessing the Pi's memory

As I mentioned in the introductory post, we need to write to the Pi's registers. So the first thing we need to do is access the memory of the BCM2836 chip. To do this, we first need to know the physical address at which the peripheral registers start (AKA the base peripheral address) for the Pi 2. This address is different than it is for the Pi 1, so looking through the BCM2835 (the chip in Pi 1) datasheet won't be much help. Luckily, the helpful Pi community on the internet told me that it could be found at 0x3F000000. We'll define this using a macro in the code.

Note that this value 0x3F000000 is just the address at which all of the peripheral registers start. There are many different peripherals, and so we need to find the one specifically for GPIO. If you don't care about how to find this value, I'll just let you know its 0x3F200000 and you can skip the next paragraph.

The GPIO registers are located at some offset of the base peripheral address. To find this offset, we consult the BCM2835 datasheet. First, we must find the virtual base peripheral address. This is because the datasheet lists information using virtual addresses rather than physical ones. Page 6 of the datasheet tells us that the virtual base peripheral address is 0x7E000000. Page 90 of the datasheet then tells us that the virtual address of the GPIO peripheral is 0x7E200000. This means that the offset from the peripheral base address to the GPIO peripheral address is 0x00200000. This offset is the same for both the physical and the virtual addresses. We'll define the address for the GPIO peripheral base with a macro as well:

Finally, to access the BCM2836's memory, we must access /dev/mem. /dev/mem is a pseudo-driver which provides access to the system's physical memory. Then, we can map /dev/mem into the virtual address space of our program using the mmap() command.

Assuming that mmap() is successful, the gpio variable is now a pointer to the RPi 2's GPIO peripheral registers.

Working with GPIO Registers

Information about the RPi 2's GPIO peripheral can be found starting at page 89 of the datasheet. On page 90, the datasheet has a layout of all of the GPIO registers (Section 6.1 - Register View). Note that there is a typo on this layout. The first register, GPFSEL0, is listed twice. We'll define some macros to make the code easy to read and provide easy access to these registers. (Remember that the gpio variable points to the start of the GPIO registers)

Setting the function of a GPIO pin

Before we can use a GPIO pin, we must set its functionality in the GPIO Function Select (GPFSEL) Registers. Information about these can be found on pages 91-94 of the datasheet. The GPFSEL registers are used to define the operation of a GPIO pin. There are six GPFSEL registers in total, named GPFSEL0 through GPFSEL5. The layout of the first one GPFSEL0 is shown below. All of the GPFSEL registers have pretty much the same layout.

Layout and functionality of the GPIO GPFSEL registers from the BCM2835 datasheet.

Layout and functionality of the GPFSEL registers from the BCM2835 datasheet.

Each GPIO pin has three corresponding bits in one of the GPSEL registers. Writing a value to these bits will configure that GPIO pin to function in a certain way, as specified in the datasheet (000 for input, 001 for output, etc). Let's define some macros for these different functionalities:

Then, we can write a function that sets the operation mode of a GPIO pin, as shown below. Here, pin is the GPIO pin number and function should be one of the macros defined above that defines the pin's operation mode.

How exactly does this work? First, we need to find the three bits that will configure the GPIO pin. Note that the registers are 32-bit. This means that each one of the GPFSEL registers contains the function select bits for 10 GPIO pins (each GPFSEL register has 2 bits left over that are not used for anything). The bits go in order, so GPFSEL0 has the bits for GPIO pins 0 through 9, GPFSEL1 has the bits for GPIO pins 10 through 19, and so on. So, if we simply divide the pin number by 10, we get the GPFSEL register number that we need to write to. This is what the code offset = pin / 10 is doing.

Then, we can access the correct GPFSEL register using the macro we defined before: GPFSEL[offset] (Remember that we defined GPFSEL to be a pointer to the GPFSEL0 register using a macro)

shift = (pin % 10) * 3 gives the offset of the three selection bits inside the GPFSEL register.

Then, the selection bits for the GPIO Pin are cleared and afterwards set accordingly using bit manipulation.

Reading and Writing to a GPIO pin

Reading and writing to a GPIO pin is probably the simplest part of the code. Setting a GPIO Pin high is done through the GPIO Pin output Set (GPSET) registers. Clearing a GPIO Pin (AKA setting it low) is done through the GPIO Pin Output Clear (GPCLR) registers. The info on these registers can be found on page 95-96 of the datasheet. Essentially, each GPIO pin has a corresponding bit in one of these registers. Writing a 1 to that bit will set or clear the GPIO pin.

Similarly, the GPIO Pin Level (GPLEV) registers can be read to see the actual value of a pin. Page 96 on the datasheet has the info for these registers.

Full Source Code

gpio_driver.h
gpio_driver.c

A lot of the work being done on the Raspberry Pi involves high-level programming using languages such as Python. However, the Raspberry Pi is also well-equipped for lower-level "embedded-style" programming (like programming a microcontroller). In this article I'll be going through how to create drivers that implement GPIO and I2C functionality on a Raspberry Pi. These drivers will be written in C, a lower-level programming language. The description and source code of these drivers are on their own pages. The links to these can be found at the bottom of this article.

Why would you want to program the Raspberry Pi like a microcontroller? To learn, mainly. After all, the Pi was originally developed for educational purposes. Another advantage is that programs written in C are capable of running much faster than programs written in high-level languages such as Python. There are many articles online which compare the speed of different languages on a Raspberry Pi. Here is one example that shows how much faster the C language can be.

To follow the code, you should be familiar with C, have a decent understanding of pointers/pointer arithmetic, and understand how bit manipulation works.

Introduction

Low-level programming of microcontrollers is different because it involves writing to registers. A register is a memory location that is frequently used by the CPU. The size of a register can vary and is usually measured in the number of bits (e.g 16-bit register). Writing certain values to these registers allows us to program the CPU.

But how do we know what we need to write to the registers? The datasheets will tell us. The Raspberry Pi Model A, B, B+, and Zero use the Broadcom BCM2835 chip. The Raspberry Pi 2 uses the Broadcom BCM2836 chip. At the time of writing this, the datasheet for the BCM2836 has not been released. However, the underlying architectures of the BCM2835 and BCM2836 are the same. For the scope of this article, the only difference between the two is that the addresses of the registers are different.

Implementing the Drivers!

The implementation and source code of the drivers are in separate articles. The links can be found below.

GPIO Driver
I2C Driver

This article discusses how to create a clock divider in VHDL using the counter method. A clock divider is also known as a frequency divider. I also provide the source code for a simple and configurable clock divider implementation.

A clock divider takes an input clock with a given frequency and produces an output clock with some lower, divided frequency.

Scaling factor

The first thing that needs to be determined is the scaling factor. The scaling factor is simply the ratio of the input clock frequency and the desired output clock frequency. For this article, the scaling factor will be abbreviated as the variable N.

\frac{Input Clk}{Output Clk} = Scaling Factor (N)

N represents the number of input clock cycles needed for one output clock cycle. In other words, for every N cycles on the input clock, one cycle on the output clock is generated. Remember that a clock signal is a square wave with a 50% duty cycle. This means that, in one cycle, half of the time is spent high (active) and half of the time is spent low (inactive). Therefore, for a scaling factor of N, the output clock will be set high for N/2 input clock cycles and set low for N/2 input clock cycles.

A clock divider implementation therefore involves using a counter to count to N/2 cycles on the input clock. Once it hits N/2, it toggles the output clock and resets the counter. Note that N must be an even integer in order to have a precise clock divider. If N is not an even integer, you can truncate it to the nearest one and in many cases this will still provide a fairly accurate output.

Clock Divider Source Code

This post discusses the design for a FPGA I2C Slave implementation in VHDL. The final source code for this design can be found in this post here. This I2C Slave implementation provides basic read, write, and addressing functionality. The address of the slave is configurable through a generic. The implementation supports repeated START conditions, but it does not support other "advanced" features such as clock stretching and 10-bit addressing.

The final implementation has been tested on an Altera Cyclone IV FPGA, using a Raspberry Pi 2 as the I2C master.

Learning I2C

This post requires a basic knowledge of the I2C bus. I will not be teaching about or providing a tutorial for I2C here, as there are already many great resources on the internet for learning about it.

The ultimate authority for I2C will always be the specification and user manual. However, this document might be too detailed for those who are only looking for a basic overview. Personally, I recommend any of the following three resources for learning I2C.

  • Sparkfun I2C Tutorial.
  • ESAcademy I2C Bus Overview.
  • Columbia Lecture Presentation.
  • I2C Slave VHDL Interface

    The VHDL implementation will provide the following interface for usage:

    The naming of the signals here may be a little confusing. I2C transactions take place from the master's perspective. Therefore, a READ command means that the master is reading data from the slave (i.e the slave is sending data to the master). A WRITE command means that the master is writing data to the slave (i.e the slave is receiving data from the master). In the interface defined above, however, the naming is done from the perspective of the slave. By convention, TX refers to transmitting data and RX refers to receiving data. The signals that begin with "tx_" are used when the slave is transmitting data to the master (during a READ command). The signals that begin with "rx_" are used when the slave is receiving data from the master (during a WRITE command).

    tx_done is an indicator signal that goes high when the I2C Slave module has finished transmitting data to the master. The data to be sent to the master must be set in tx_byte.

    rx_data_rdy is an indicator signal that goes high when data is received from the master. The received data can be found in rx_byte.

    clk is the clock signal for the I2C Slave module itself. This should not be confused with SCL, which is the I2C-bus clock line. This will be explained more in the next section. For best performance, clk should be significantly faster than SCL.

    in_progress is an output indicator signal I decided to add, as it may be useful in some applications. It goes high whenever there is activity on the bus that is addressed to the slave.

    I2C Slave FSM Design

    This I2C Slave implementation uses a fast clock to oversample the SDA and SCL signals. This is more reliable than using the SCL line itself as the FPGA's clock signal. There are four particular events that need to be captured. The first two are the rising and falling edges of the SCL clock. These edges trigger transitions between states in the FSM. The next two are the START and STOP conditions. These occur when the SCL line is high, so they must be captured separately. Four strobe signals are used to capture these events. These strobe signals go high to indicate that the event has occurred.

    Using these four strobe signals, it is easy to implement a state machine for the I2C Slave. The FSM uses eight states. The states and their general functions are listed below.

  • IDLE - No bus activity that is addressed toward the slave. The slave is waiting for a START condition in this state.
  • READ_ADDRESS - Reads the 7 bit address and the R/W bit from the master. Also determines whether the address is a match
  • SEND_ACK - Sends an ACK bit by holding SDA low through one SCL cycle.
  • WRITE_CMD - Reads one byte of data from master by polling SDA line.
  • READ_CMD - Writes one byte of data to master by setting SDA line.
  • WAIT_ACK_1 - Waits for ACK bit from master. This requires two states.
  • WAIT_ACK_2
  • WAIT_STOP - A NACK was received during a READ command. Therefore, the I2C shouldn't do anything and should just wait for a STOP bit.
  • Below is a diagram of the FSM. Note that this FSM diagram does not show all the transitions that occur because of START and STOP conditions. When a START condition is received, the FSM immediately transitions to the READ_ADDRESS state to begin a new transaction. This allows Repeated Start Conditions to work. When a STOP condition is received, the FSM immediately goes into the IDLE state. These transitions due to START and STOP conditions can occur at any point and in any state of the FSM. They are not shown in the FSM diagram because it would be too messy.

    microps_i2c_fsm

    Note that the FSM diagram contains some internal strobes and logic signals for its transitions. scl_falling and scl_rising are the two strobe signals for the rising and falling edges of the SCL line, as previously discussed. rw is a signal that holds the value of the R/W bit. It is set during the READ_ADDRESS state. bit_count is a counter. Every transaction involves a single byte that is clocked in or out one bit at a time. The counter keeps track of the number of bits received or sent and transitions between states after a full byte. continue_read is a signal that goes high when the I2C slave should continue reading from the master during a WRITE command. This depends on whether a ACK or a NACK was received after reading a byte.

    Finally, because the I2C bus lines are open-drain, a tri-state buffer must be used to manage when the I2C slave pulls the SDA line low. An enable signal, sda_out_en is high when the slave has control of the SDA line. sda_out_en is high only when the slave is sending data during the SEND_ACK and READ_CMD states. The tri-state buffer is simple to implement:

    For the full source code, click here.

    Below I provide the entire source code for a FPGA I2C Slave implementation in VHDL. To learn more about the implementation's design and FSM, see this post here.

    This I2C Slave implementation provides basic read, write, and addressing functionality. It also supports repeated start conditions. The address of the slave is configurable through a generic. Note that this implementation does not currently support "advanced" features such as clock stretching. It also does not support 10-bit addressing, although I'd imagine it wouldn't be too hard to implement this.

    This implementation has been tested on an Altera Cyclone IV FPGA. A Raspberry Pi 2 was used as the I2C master.

    How to use

    The I2C Slave FSM provides the following interface:

    tx_done goes high when the I2C Slave module has finished transmitting data to the master. In other words, it signals the completion of a READ command (master reads from slave). The data to be sent to the master must be set in tx_byte.

    rx_data_rdy goes high when data is received from the master. In other words, it indicates the completion of a WRITE command (master writes to slave). The received data can be found in rx_byte.

    clk is the clock signal for the I2C Slave module itself. This should not be confused with SCL, which is the I2C-bus clock line. For best performance, clk should be significantly faster than SCL.

    Source Code

    This article discusses how to convert between the common VHDL types. The most common VHDL types are std_logic_vector, signed, unsigned, and integer. The std_logic and std_logic_vector types are defined in the standard logic 1164 package of the IEEE library. This package can be imported as follows:

    library IEEE;
    use IEEE.STD_LOGIC_1664.ALL

    The signed and unsigned types can be found in the numeric_std package. This package can be imported using the code below. The signed type is represented in two's complement form. The source file for the numeric_std package can be found here. For more information on two's complement, check the Wikipedia page.

    use ieee.numeric_std.all

    VHDL is a strongly-typed language, and does not have automatic type conversion. As a result, converting between different types is often necessary. The libraries above provide type casts and conversion functions between the common VHDL types. These are depicted by the image below.

    How to convert between the most common VHDL types

     

    It is important to note that casting between a std_logic_vector and a signed/unsigned type requires that both signals have the same bit width. Integers do not have a set bit width. Therefore, in the to_signed and to_unsigned conversion functions, note that the first argument is the integer that is being converted and the second argument specifies the bit width of the resulting signed/unsigned type.

    It is important to realize that there is no direct conversion between signed and unsigned types. There is also no direct conversion between the std_logic_vector and integer types.

    Using these conversions and casts is straightforward. Below is example code illustrating their usage:

    library ieee;
    use ieee.std_logic_1164.all;
    use ieee.std_logic_unsigned.all;
    use ieee.numeric_std.all;

    signal stdlvec : std_logic_vector(31 downto 0);
    signal unsgn : unsigned(31 downto 0);
    signal sgn : signed(31 downto 0);
    signal int : integer;


    --Conversion from std_logic_vector to signed and unsigned types
    unsgn <= unsigned(stdlvec);
    sgn <= signed(stdlvec);


    --Conversion from signed/unsigned types back to std_logic_vector
    stdlvec <= std_logic_vector(unsgn);
    stdlvec <= std_logic_vector(sgn);


    --Conversion from signed/unsigned types to integer
    int <= to_integer(sgn);
    int <= to_integer(unsgn);


    --Conversion from integer back to 32-bit signed/unsigned types
    unsgn <= to_unsigned(int, 32);
    sgn <= to_signed(int, 32);