DEV Community: Eric Lloyd

ChatGPT is Game Changing! – heapq explained by an AI tool

Eric Lloyd — Sun, 04 Dec 2022 17:51:00 +0000

In the past few days, I have read a lot of twitter posts about ChatGPT and I was impressed by all the example I had seen, so I had to try it myself.
Here is the result of the two following prompts.

Introduction

Write a blog post introduction explaining how this blog post was written by ChatGPT, explaining what ChatGPT is an briefly how it works.

Welcome to this blog post on the python "heapq" library. This post was written by ChatGPT, a natural language processing tool that uses machine learning algorithms to generate human-like text.

ChatGPT is a chatbot that uses a state-of-the-art GPT-3 model to generate responses to user inputs. It has been trained on a vast amount of text data, allowing it to generate coherent and natural-sounding responses to a wide variety of inputs.

To use ChatGPT, you simply enter a prompt or question, and the chatbot will generate a response. You can then continue the conversation by entering additional prompts or questions, and ChatGPT will generate appropriate responses.

In this blog post, we asked ChatGPT to write an introduction to the "heapq" library, explaining what it is and how it works. ChatGPT used its knowledge of programming and natural language processing to generate the text you see here.

We hope you enjoy this blog post and find it helpful. Thank you for reading!

heapq library

Write a blog post explaining how to use the python "heapq" library as a priority queue holding the n maximum elements from a list of integers. Make sure to explain how the priority removes elements added after we have reached the max size. Make sure to include code examples.

The python "heapq" library is a great tool for implementing a priority queue. It allows us to easily store and retrieve elements based on their priority. In this blog post, we will explore how to use "heapq" to create a priority queue that holds the n maximum elements from a list of integers.

To create a priority queue using "heapq", we first need to import the library. We can do this using the following code:

import heapq

Once we have imported the library, we can create a priority queue by initializing an empty list and using the "heapify" method to convert it into a heap data structure. We can do this with the following code:

pq = []
heapq.heapify(pq)

Now that we have our empty priority queue, we can start adding elements to it. To add an element to the queue, we use the heappush method, which takes the queue and the element to be added as arguments. For example, if we want to add the element 5 to our priority queue, we can use the following code:

heapq.heappush(pq, 5)

The heappush method automatically places the element in the appropriate position in the heap based on its priority. For a priority queue holding the n maximum elements from a list of integers, the priority of an element is determined by its value. The maximum element will have the highest priority, and the nth maximum element will have the lowest priority.

To retrieve the maximum element from the priority queue, we use the heappop method, which returns the element with the highest priority. For our priority queue, this will be the maximum element. We can use the "heappop" method with the following code:

max_element = heapq.heappop(pq)

Once we have retrieved the maximum element, we can add new elements to the priority queue as needed. However, we need to make sure that the queue only holds the n maximum elements from the list. To do this, we can set a maximum size for the queue and check the size of the queue each time we add a new element. If the queue is already at its maximum size, we can use the heappushpop method to add the new element and remove the lowest priority element (the nth maximum element) in a single step. We can do this with the following code:

if len(pq) == n:
  heapq.heappushpop(pq, new_element)
else:
  heapq.heappush(pq, new_element)

In this code, n is the maximum size of the queue, and new_element is the element we want to add to the queue.

Using the "heapq" library, we can easily create a priority queue that holds the n maximum elements from a list of integers. The heapify and heappush methods allow us to initialize and add elements to the queue, while the heappop and heappushpop methods allow us to retrieve the maximum element and add new elements while maintaining the maximum size of the queue. With these tools, we can easily implement a priority queue in our Python programs.

Conclusion

Write a blog post conclusion from my perspective saying how mindblown I am about ChatGPT, how I believe it will change the future and potentially replace search engines.

In conclusion, I am absolutely mindblown by ChatGPT and the amazing technology behind it. The ability of this chatbot to generate coherent and natural-sounding responses to a wide variety of inputs is truly impressive, and I believe it has the potential to change the future in many ways.

One area where I think ChatGPT could have a big impact is in the field of search engines. With its ability to understand and respond to user inputs, ChatGPT could potentially replace traditional search engines, providing a more intuitive and natural way to find information online. Imagine being able to simply ask a question and get a personalized, accurate response, rather than sifting through pages of search results. This could revolutionize the way we access information and make the internet a more user-friendly and accessible place.

Overall, I am excited to see what the future holds for ChatGPT and the potential it has to change the world. I can't wait to see what amazing things this technology will be able to do in the coming years.

You want to try it while it's available here.

Python Basics: Functions

Eric Lloyd — Sun, 29 May 2022 17:26:44 +0000

Functions are the building blocks of programming.

A function is block of code which is used to execute a task/action or data transformation.
It can be called multiple times, with different inputs.

We will decipher this definition in the following blog post.
I will explain how to define a function in Python and how it can be called multiple times with different inputs.
Using a function can make your code clearer, more organised and more readable. I will give a few use cases to illustrate this.

Print function

Usually the first thing you learn in Python (or any programming language) is to display the sentence "Hello World!" to the terminal output.
This is how the code would look like:

print("Hello World!")

Here what we are actually doing is calling the built-in print function with a string as argument with the value "Hello World!".

You could simplify and imagine the print function to be defined the following way:

def print(value):
    # do something with the value to 
    # display it on the terminal output.
    # ...
    return None

This imaginary print function has a parameter called value. It then displays the value to the terminal and returns None.
We will explain in more details what is a parameter a and what is a return statement later.

The print function is very valuable because you do not need to know how the value you give it is printed to the terminal, you only care about the result.
It is used a lot of times throughout programs.
The name print clearly states the intent of the function, which is to display or print to the terminal output.

Similarly, when we build our own functions, we will try to:

hide implementation details
give them a meaningful name
make them as reusable as possible

Building your own functions

In Python, you can use many built-in functions, meaning functions that come with the language such as print, len (you can find more details about built-in functions here).
More importantly, you can define your own functions in your programs, this is what we will focus on from now on.

How to define a function

To define your own function, you need to:

start with the keyword def
after that you need parenthesis with, optionally, the parameters of your function
then you need a semicollon to start your function block
finally the block or content of the function (what it does)

The first line when you define a function is called the function signature, it has the keyword (def) the name of the function and optionally some parameters.

Remember that all the code in your function should be indented inside the function block.

Defining a function with no parameters

Here is an example of what is described above for a function with no parameters:

def my_first_function():
    print("Hello inside a function!")

Here the name of the function is my_first_function, it takes no parameters: there is nothing inside the parenthesis.
It then calls the print built-in function.

Defining a function with parameters

Here are two examples of functions with parameters:

def greeting(name):
    print(f"Hello {name}, from inside a function!")

def polite_greeting(title, surname):
    print(f"Dear {title} {surname}, greetings from inside a function!")

Here the name of the first function is greeting, it takes one parameter called name (inside the parenthesis).

The name of the second function is polite_greeting, it takes two parameters called title and surname (inside the parenthesis).

Again, they both call the print built-in function, this time with a f-string.

Once you have defined your functions, if you try to run your program, you will see that nothing happens.
This is expected: for your functions to be executed you will need to call them.

How to call a function

Calling a function is equivalent to executing the code inside your function.
It will be called with the arguments (or values) that you pass to it.

To call your first function, you simply do the following:

my_first_function()

This has to be below your function definition in your program.

You can call it multiple times, it will execute the code inside your functions each time:

my_first_function()
my_first_function()
my_first_function()

To call the greetings functions, which take parameters there are multiple ways.
I will illustrate below 3 different ways:

1. With inline variables

In this method, we directly pass inline values to the function:

greeting("Jane")
polite_greeting("Mrs", "Jackson")

We pass the value "Jane" directly to the greeting function.
When the function is executed, we have name="Jane" inside the function block.
We pass the value "Mrs" and "Jackson" directly to the polite_greeting function.
When the function is executed, we have title="Mrs" surnname="Jackson" inside the function block.

2. With existing variable(s)

In this method, we pass existing variables to the function:

first_name = "John"
greeting(first_name)
title = "Dr"
surname = "Jackson"
polite_greeting(title, surname)

We pass the variable first_name to the greeting function.
When the function is executed, we have name=first_name inside the function block (which is equivalent to name="John").
We pass the variables title and surname to the polite_greeting function.
When the function is executed, we have title=title surnname=surname inside the function block (which is equivalent to title="Dr" surnname="Jackson").

Here it is important to note that the variable we pass the function (called argument) does not have to have the same name as the function parameter.

3. With keyword arguments

In this method, we can pass either inline values or variable using the parameter name explicitly followed by an equal sign:
This method is more verbose, but it is in my opinion is the more intuitive one when learning:

first_name = "John"
greeting(name=first_name)
title = "Dr"
surname = "Jackson"
polite_greeting(title=title, surname=surname)

We are explicitly saying that we want the variable inside our greeting function block name to be first_name when we call it.

Here is an example with inline values:

polite_greeting(title="Mrs", surname="Jackson")

Function return statement in Python

For your functions to be useful in your program, it is common for them to execute some kind of data transformation and return a result.
To do this in Python (and most programming languages), you can use the return statement.
Here is a very simple example:

def add(a, b):
    result = a + b
    return result

The above function takes 2 parameters, a and b, it computes the sum of these variables and saves it into a result variable.
It then returns this result variable.
When you call it, you can assign its return value to a variable like so:

c = add(5, 5)
# here c = 10

d = add(1, 5)
# here d = 6

one = 1
two = 2
f = add(one, two)

g = add(c, d)
# here g = 16

Here you see an example of how a function called add can be used and called multiple times.
It can be called directly with values (example c and d) or with existing variables (example f and g)

In Python, a function always returns a value. If you do not explicitly write a return statement in your function definition, Python will add an implicit return None.
In other words if a function has not explicit return statement, it will return None.

You can check this by assigning the execution of a function with no implicit return to a variable and printing its value:

def does_nothing():
    pass

nothing = does_nothing()
# here nothing = None

Use case 1: average of a list

Imagine we have a list grades for which we want to compute the average.
Here is the code I would use without a function.

grades_1 = [12, 15, 10, 17]

sum  = 0
for grade in grades_1:
    sum += grade
avg = round(sum / len(grades_1), 2)

We are summing all the elements in the list, and then dividing the sum by the length of the list, rounding the result to maximum 2 decimal.

This works, but it is not reusable. If I want to do it again for a different list of grades, for example grades_2 = [18, 15, 11, 13],
I would have to copy and paste my code above and tweak it for it to work with the grades_2 variable.
However, if I create a function called average, I can reuse it easily on the 2 lists. Let's do it:

def average(grades):
    sum  = 0
    for grade in grades:
        sum += grade
    avg = round(sum / len(grades), 2)
    return avg

This is the same code as above, just extracted into a function.

Now that we have the function, we can call it or apply it multiple times:

grades_1 = [12, 15, 10, 17]
grades_2 = [18, 15, 11, 13]
avg_1 = average(grades=grades_1)
# here avg_1 = 13.5
avg_2 = average(grades=grades_2)
# here avg_2 = 14.25

Use case 2: formatting a string

Imagine we are given list of names with different formats, and we want all the names to have the same format.
For this, we will write a function with converts all the names to title case using the title() string method.

def format(names):
    result = []
    for name in names:
        formatted_name = name.title()
        result.append(formatted_name)
    return result


unformatted_names = ["JANE", "john", "Janet"]
formatted_names = format(names=unformatted_names)
# here formatted_names = ['Jane', 'John', 'Janet']

Here if we are ever given more list of unformatted names, we can reuse our function to format them.

Conclusion

This blog post has just introduced functions, why they are useful in programming and how to define them and call them in Python.

Code

All the code from this blog post can be found in this replit.

Python Basics: Looping over common Data Structures

Eric Lloyd — Sun, 22 May 2022 11:38:04 +0000

Python Basics: Looping over common Data Structures

Looping is an essential aspect to programming.
Given a data structure which length may vary, it is common to want to repeat an operation over each elements of it.
Instead of repeating the common operation in your code, you can use looping to iterate over all elements in a data structure.

I will give a few examples of how to loop over the common data structures in Python (string, list, tuple & dictionary).

This will cover for loops and not while loops.
The name of the variable(s) inside the loop is for you to define, but keep it mind that you should try to use variable names which makes sense and make your code readable.

Looping over a string

Simple looping over characters

sentence = "How to loop over a string?"
for character in sentence:
    # here you can do any operation which will be repeated
    # for each character in the sentence.
    print(character)

Looping over characters and positions

We can access the characters of a string in Python using their index or position.

For example if s = "Baz", then s[0] == 'B', s[1] == 'a' and s[2] == 'z'.

You can notice that index starts from 0 for the first element in Python.
This is the same for string, list and tuple.

sentence = "How to loop over a string with the position?"
for position, character in enumerate(sentence):
    # here you can do any operation which will be repeated
    # for each position and character in the sentence 
    # using the "enumerate" function.
    print(position, character)

Looping over a list

Simple looping over elements

grades = [11, 18, 16, 19, 14]
for grade in grades:
    # here you can do any operation which will be repeated
    # for each grade in the grades list.
    print(grade)

Looping over elements and positions

We can access the elements of a list in Python using their index or position.

For example if l = [2, 0, 1], then l[0] == 2, l[1] == 0 and l[2] == 1.

grades = [11, 18, 16, 19, 14]
for position, grade in enumerate(grades):
    # here you can do any operation which will be repeated
    # for each position and grade in the grades list 
    # using the "enumerate" function.
    print(position, grade)

Looping over a tuple

A tuple is an immutable container of elements, which means we can not change/add/remove elements after it is defined.

Looping over a tuple is the same as looping over a list.

Simple looping over elements

names = ("Jane", "John", "Janet")
for name in names:
    # here you can do any operation which will be repeated
    # for each name in the names tuple.
    print(name)

Looping over elements and positions

We can access the elements of a tuple in Python using their index or position.

For example if t = (1, 2), then t[0] == 1 and t[1] == 2.

names = ("Jane", "John", "Janet")
for position, name in enumerate(names):
    # here you can do any operation which will be repeated
    # for each position and name in the names list 
    # using the "enumerate" function.
    print(position, name)

Looping over a dictionary

A dictionary is a container of "key/value" pairs, in other words a mapping of elements.

We can access the elements of a dictionary in Python using the keys.

For example if d = {"foo": 1, "bar": 2}, then d["foo"] == 1 and d["bar"] == 2.

Simple looping over keys

A simple loop over a dictionary iterates over the keys of the dictionary.

ages = {"Jane": 25, "John": 26, "Janet": 24}
for name in ages:
    # here you can do any operation which will be repeated
    # for each name (key) in the ages dictionary.
    # you can access the value with the key:
    age = ages[name]
    print(name, age)

Looping over key/value pairs

The items method of the dictionary will return all the key/value pairs.
This way, you can iterate over key/value pairs directly.

ages = {"Jane": 25, "John": 26, "Janet": 24}
for name, age in ages.items():
    # here you can do any operation which will be repeated
    # for each name (key) and age (value) in the ages dictionary.
    print(name, age)

Looping over values

The values method of the dictionary will return all values in a list.
This way, you can iterate over key/value pairs directly.

ages = {"Jane": 25, "John": 26, "Janet": 24}
for age in ages.values():
    # here you can do any operation which will be repeated
    # for each age (value) in the ages dictionary.
    print(age)

Looping in practice

Use case 1: sum of a list

Given a list of grades, of unknown/varying size, we can compute the sum using looping:

grades = [11, 18, 16, 19, 14]
# initialize sum of grades to 0
sum_of_grades = 0
for grade in grades:
    # add current grade to the total sum
    sum_of_grades = sum_of_grades + grade

# check result is correct:
assert 78 == sum_of_grades

Use case 2: average of a list

This is the same as above, we just need to divide the sum by the length of the list and round to 2 decimal point.

grades = [11, 18, 16, 19, 14]
# initialize sum of grades to 0
sum_of_grades = 0
for grade in grades:
    # add current grade to the total sum
    sum_of_grades = sum_of_grades + grade

avg_of_grades = round(sum_of_grades / len(grades), 2)
# check result is correct:
assert 15.6 == avg_of_grades

Use case 3: dictionary of grades

Given a dictionary with names as key and a list of grades as values of unknown/varying size, we can compute the average for each student using looping:

grades_dict = {"Jane": [14, 16], "John": [11, 12], "Janet": [18, 16]}
# initialize result to an empty dictionary:
avg_of_grades_dict = {}
for name, grades in grades_dict.items():
    # do the same as above inside the loop for each student:
    sum_of_grades = 0
    for grade in grades:
        # add current grade to the total sum
        sum_of_grades = sum_of_grades + grade
    # compute the average for the student:
    avg_of_grades = round(sum_of_grades / len(grades), 2)
    # save the avg in a result dictionary for the student:
    avg_of_grades_dict[name] = avg_of_grades


# check result is correct:
assert {"Jane": 15.0, "John": 11.5, "Janet": 17.0} == avg_of_grades_dict

Use case 4: common letters (in place) in a string

Given two words (of type string), we can find the common letters in the same position using looping:

name = "Jean"
surname = "John"
# initialize result to an empty list:
common_letters_in_place = []
# loop over position and letters in a string with enumerate:
for position, letter in enumerate(name):
    # check if letters in both string are the same at the same position:
    if letter == surname[position]:
        common_letters_in_place.append(letter)


# check result is correct:
assert ['J', 'n'] == common_letters_in_place

Code

All the code from this blog post can be found in this replit.

Advent of Code in Kotlin: Day 5, 2021

Eric Lloyd — Sun, 05 Dec 2021 16:10:11 +0000

Day 5

Alright, today is day 5 of advent of code, we have an interesting challenge involving points and lines (or vectors) in a 2D plane.
Below I will share and explain my proposed solution in Kotlin.

Looking back on Day 3 and Day 4

Before we jump into day 5's puzzle, I would to share links to my previous days' proposed solutions:

Day 3 — a few key concepts used are:
- extensions for example on List<Char> type
- higher-order functions aka a function which takes other functions as parameters
Day 4 — a few key concepts used are:
- data classes for the board, rows and tiles
- chunked method to partition a iterable in groups of a given size n

Day 5 Problem

You can find the description for this puzzle here, I would summarize the problem as the following:

Given a list of lines or vectors, count the number of points which overlap

Solution

In my opinion, today's puzzle could be broken down into 3 challenges:

modelling the input data
converting lines to a list of points
counting the points to find overlapping ones

I will share how I approached each of these challenges by sharing parts of my solution.

Modelling the input

So here we need to convert each line from the input file to two points on a 2D plane.
The line between two points can be called a vector. I chose to simply call it Line.
Here is how I modelled my data:

data class Point(val x: Int, val y: Int)

data class Line(val from: Point, val to: Point) {
    // [...]
}

Then you need to convert the List<String> to a List<Line>. Here is how I did it:

val lines = readInput("day5/Day5") // https://github.com/Eric-Lloyd/advent-of-code-kotlin/blob/main/src/utils/Utils.kt#L8
        .map { lineFrom(it) }

fun lineFrom(line: String) =
    line.split(" -> ")
        .map { subLine ->
            subLine.split(",")
                .map { it.toInt() }
                .let { (x, y) -> Point(x, y) }
        }
        .let { (from, to) -> Line(from, to) }

Once we have modelled the data, we can focus on solving the problem at hand.

Converting a line to a list of points

As stated before, we need to count occurrences of each point to find when two points overlap.
Before we can do this, we need to get all given points on a Line.

In my opinion, this part was the most difficult — especially for diagonal lines.
For horizontal and vertical lines, we can leverage the fact that y or x stay consistent for all points.
For diagonal lines, there are 4 cases:

from.x < to.x and from.y < to.y
from.x < to.x and from.y > to.y
from.x > to.x and from.y < to.y
from.x > to.x and from.y > to.y

In order to traverse the line, we need to either increment or decrement x and y.

if from.x > to.x we should decrement x
if from.x < to.x we should increment x

The same thing can be said for y. Instead of handling these 4 cases, we can abstract out the increment/decrement action in a direction function.
Then, we can update x and y using this direction.
I hope I was clear, if not reading the code may help you understand:

data class Line(val from: Point, val to: Point) {
    val isHorizontal: Boolean = from.y == to.y
    val isVertical: Boolean = from.x == to.x
    val isDiagonal: Boolean = abs(from.x - to.x) == abs(from.y - to.y)

    /*
     * returns all the points along the line.
     */
    fun points(): List<Point> {
        val points = mutableListOf<Point>()
        when {
            isHorizontal -> {
                val min = minOf(from.x, to.x)
                val max = maxOf(from.x, to.x)
                for (i in min until max + 1) {
                    points.add(Point(i, from.y))
                }
                return points
            }
            isVertical -> {
                val min = minOf(from.y, to.y)
                val max = maxOf(from.y, to.y)
                for (i in min until max + 1) {
                    points.add(Point(from.x, i))
                }
                return points
            }
            isDiagonal -> {
                points.add(from)
                val xDirection = direction(from.x, to.x) // whether to increment or decrement x when traversing the line
                val yDirection = direction(from.y, to.y) // whether to increment or decrement y when traversing the line
                var currentX = xDirection(from.x)
                var currentY = yDirection(from.y)
                while (currentX != to.x) {
                    points.add(Point(currentX, currentY))
                    currentX = xDirection(currentX)
                    currentY = yDirection(currentY)
                }
                points.add(to)
                return points
            }
            else -> {
                throw NotImplementedError("We only support horizontal, vertical or diagonal lines.")
            }
        }
    }
}

fun direction(a1: Int, a2: Int): (Int) -> Int {
    if (a1 > a2) return { a -> a - 1 } else return { a -> a + 1 }
}

Once we have points for a given Line, we simply need to count occurences of points for the lines (List<Line>).

Counting the points

Counting the points can be done in a very idiomatic way leveraging some built-in function of the Kotlin List class.
Here is the one function for it:

fun overlappingPoints(lines: List<Line>, threshold: Int) =
    lines.flatMap { it.points() }
        .groupBy { it }
        .count { it.value.size >= threshold }

Let me break it down for you:

flatMap allows getting all the points for all the lines, if we would have simply mapped, we would have had List<List<Point>>, using flatMap allows to flatten the result to a List<Point>.
groupBy allows transforming the List<Point> to a Map<Point, List<Point>> with the list being a list of duplicates of the same point (one for each time when this point is on a given line).
count allows counting how many times a given predicate is true for the key/value pair. Here the predicate is { it.value.size >= threshold } which checks whether the number of duplicates for this point is bigger than the given threshold.

You may have noticed how I did not distinguish my solution between Part 1 and Part 2 so far, this is because the only difference is which points to count.
For both parts you need to add a filter based on the type of line (whether it is horizontal, vertical or diagonal).
Here is how I did it:

fun count(lines: List<Line>, filter: (Line) -> Boolean) =
    overlappingPoints(lines.filter { filter(it) }, 2)

val count1 = count(lines) { line -> line.isVertical || line.isHorizontal }
val count2 = count(lines) { line -> line.isVertical || line.isHorizontal || line.isDiagonal }

Caveat: for today it seems all lines in the input are one of horizontal, vertical or diagonal (there are no lines at 60 degrees for example).
This means if a line is not horizontal nor vertical you could consider it diagonal without explicit check.

Kotlin Concepts

Alright, I hope you liked my proposed solution and learned a few things along the way.
The key Kotlin concepts that we have covered are:

data classes
flatMap
count
higher-order functions to avoid code duplicates

Feel free to share with me any feedback / concerns / questions you may have.

Source code

You can find the source code for my solution here.

Thank you very much for reading!

Advent of Code in Kotlin: Day 2

Eric Lloyd — Thu, 02 Dec 2021 19:25:46 +0000

Day 2

Alright, today is day 2 of advent of code, we have a challenge slightly more difficult than day 1 but still very much accessible and fun (not overwhelming yet 😬).

Looking back on Day 1

Before we jump into day 2's puzzle and my proposed solution in Kotlin, I would like to share something I learned about yesterday:
in Kotlin List API there is a windowed method which allows iterating over a list with "sliding windows".
This method takes a size parameter which is the size of the "sliding window".

To give a concrete example, consider the following code:

listOf(1, 2, 3, 4).windowed(2) // returns [[1, 2], [2, 3], [3, 4]]

Also, it can be called with a "transform" function parameter which will be applied to each "sliding window" or sublist.
For example:

listOf(1, 2, 3, 4).windowed(2) { it.sum() }) // returns [3, 5, 7]

I imagine you could remember how this could have been useful for yesterday's problem 😅

Big thanks to Sebastian Aigner for sharing his solution for Day 1 and teaching me about this!
You can find an interesting blog post he wrote about advanced Kotlin Collection functionality.

Day 2 Problem

You can find the description for this puzzle here, I would summarize the problem as the following:

Given a list of commands, compute some aggregates based on the command's value.

Modeling the input

I have decided to use a data class to model the input, as well as an enum for the command type:

enum class Type {
    FORWARD, UP, DOWN
}

data class Command(val type: Type, val amount: Int)

The input to my functions will be a List<Command>.

Solution

The distinction between Part 1 and Part 2 is how each command affects the aggregate to be calculated.
I have taken two different approach in each part on how to compute these aggregates, which I will share with you below:

Part 1

For this part, there are two aggregates depth and horizontalPosition. To calculate each we need to iterate over the input list. We could either calculate both in the same function and loop, or create a function for each aggregate.
In Part 2 I will be doing the former, in Part 1 I am doing the latter.
Below are the two functions I have used:

fun horizontalPosition(commands: List<Command>) =
    commands
        .filter { it.type == Type.FORWARD }
        .map { it.amount }
        .sum()

fun depth(commands: List<Command>) =
    commands
        .filter { it.type == Type.DOWN || it.type == Type.UP }
        .map { if (it.type == Type.DOWN) it.amount else -it.amount }
        .sum()

These follow the pattern filter-map-reduce. It is the clean functional way of transforming a list into an aggregate.

For the horizontalPosition we simply need to sum the commands of type FORWARD (while ignoring other types of commands).
For the depth, we need to add the amount for DOWN commands and subtract it for UP commands (while ignoring FORWARD commands).

Part 2

For this part, there is an additional aggregate called aim which we need to compute depth.
In other words, the logic for calculating depth changes, so we need to ditch our previous function.
This time, we have to compute the aggregates together as they depend on each other (depth depends on aim).
To do this, we can leverage the fold method on the List API which is a generalized way of doing a reduce as instead of using the first element of the list as a starting point for the calculation, we can specify our own initial element (and its type).

I have again leveraged a data class here for my aggregates:

data class Attributes(val aim: Int, val horizontalPosition: Int, val depth: Int)

I will use this class for my accumulator when using fold:

fun attributes(commands: List<Command>): Attributes {
    return commands
        .fold(
            Attributes(0, 0, 0),
            { acc, command -> operation(acc, command) }
        )
}

private fun operation(attributes: Attributes, command: Command): Attributes {
    val (aim, horizontalPosition, depth) = attributes
    return when (command.type) {
        Type.FORWARD -> Attributes(aim, horizontalPosition + command.amount, depth + (aim * command.amount))
        Type.UP -> Attributes(aim - command.amount, horizontalPosition, depth)
        Type.DOWN -> Attributes(aim + command.amount, horizontalPosition, depth)
    }
}

Here my initial value for the acc variable is Attributes(0, 0, 0).
Then, I loop over the list and for each command, I transform my acc variable by calling the operation method.
The fold can be considered as doing the following:

fun fold(commands: List<Command>) {
    var acc = Attributes(0, 0, 0)
    for (command in commands) {
        acc = operation(acc, command)
    }
    return acc
}

In other words, the operation method is where the computation happens, and if you look more closely you can see I am using the when expression.
This can be considered an improved "switch" and allows partial "pattern matching".

Based on the command type, I create a new Attributes instance using the previous one, and the command amount.
Note here than I do not need an else clause in my when expression. This is because I am using an enum and not a string, hence the Kotlin compilers knows that I have all the cases covered (as my enum has only 3 fields).
This is very nice as it avoids having something like:

when (foo) { 
  // [...] 
  else -> throw Exception("this should never be reached")
}

Also note how data classes allow destructuring of properties:

val (aim, horizontalPosition, depth) = attributes

is equivalent to:

val aim = attributes.aim
val horizontalPosition = attributes.horizontalPosition
val depth = attributes.depth

Kotlin Concepts

Alright, I hope you liked my proposed solution and learned a few things along the way.
The key Kotlin concepts that we have covered are:

filter-map-reduce for computing an aggregate from a list
fold for computing multiple aggregates at once from a list
when expression and enums work nicely hand in hand
data class can easily help to build named tuples of data

Source code

You can find the source code for my solution here.

Thank you very much for reading!

Advent of Code in Kotlin: Day 1

Eric Lloyd — Wed, 01 Dec 2021 16:31:03 +0000

Introduction

It's this time of the year when it gets dark and cold outside (at least in Berlin), people start getting into the Christmas spirit by going to Christmas Markets and drinking Gluhwein (while it's still allowed). It's also the time when you spend more time indoors "cosying" up with a hot beverage.

More specifically, if you are interested in coding, today marks the first day of advent of code. The idea is fairly straightforward: every day a programming puzzle gets released, in order to unlock the puzzle for each day you need to solve the previous day.

This is a great opportunity to learn new things while having fun for people who enjoy coding.
I personally am in the process of learning Kotlin so this is an opportunity for me to practice my skills in this programming language.

Disclaimer: this event can be competitive and as a result stressful for some. I am not planning to complete each and every puzzle every day, because "life"! Nor am I trying to solve puzzles as fast as possible or as concisely as possible.

Instead, my main goal in participating in this event is three-fold:

Practice coding in Kotlin
Have fun
Share my learnings with the community

Luckily for you, in you are also interested in learning Kotlin, JetBrains have shared a blog post on this event, explaining in more details how you can participate. Moreover, they have created a GitHub template which you can use to easily get started.

My plan is to write short blog posts for the days I will have time to solve in which I will share and explain my solution to the daily puzzle.

Let's get started with Day 1!

Day 1

FYI: in the last years, the puzzle increase in difficulty throughout the days — the first few days can be considered as a "ramp up".

Puzzle — Part 1

The puzzle description can be found here — I would summarize it to the following:

Given a list of integers, return the number of times an element in the list is bigger than the previous element.

Solution

Here is my proposed solution, I will walk through it afterwards:

fun countIncrease(input: List<Int>): Int {
    if (input.isEmpty()) return 0

    var count = 0
    var previous = input[0]
    val tail = input.drop(1)
    for (current in tail) {
        if (current > previous) {
            count += 1
        }
        previous = current
    }
    return count
}

This method takes a list of integers as a parameter, and returns an integer.
Before looping over the input, I check whether it is empty (we can return early if it is). Then I extract the first element of the list in a temporary variable called previous, this variable is mutable and will be updated to always contain the element before the current one.
I then loop over the tail of the list .i.e the input list with the first element removed. In the loop body, I simply compare the current element with the previous and if the former is greater than the latter, I increment a count variable. Then I update the previous variable to current.
Finally, once the loop is completed, I return the count variable.

Here the interesting part is the .drop method on the List API, which concisely returns a new 'read only' list instance without the first element.

Puzzle — Part 2

The second part of the puzzle is an extension of the part 1, it can actually be considered the exact same problem, with an additional data transformation before the calculation.
Indeed, we need to group each triple elements and then apply our algorithm on the new transformed list.
For example, if the input list is [4, 1, 4, 1, 7] the transformed list is [9, 6, 12] (computed by 4 + 1 + 4 = 9, 1 + 4 + 1 = 6 and 4 + 1 + 7 = 12 respectively). Once we have the transformed list, we only need to pass it to our function from part 1.

Solution

Here is my proposed solution for the data transformation:

fun buildTriples(input: List<Int>): List<Triple> {
    val lastFirst = input.size - 3
    return input
        .filterIndexed { index, _ -> index <= lastFirst }
        .mapIndexed { index, _ ->
            val first = input[index]
            val second = input[index + 1]
            val third = input[index + 2]
            Triple(first, second, third)
        }
}

data class Triple(val first: Int, val second: Int, val third: Int)

fun Triple.sum(): Int = this.first + this.second + this.third

This method transform each element in the list to a Triple instance, Triple is a simple data class with 3 integer attributes.
The triple contains the current element and the two following elements in the list.

Here the interesting parts used are the .filterIndexed and .mapIndexed method of the List API. As the names imply, they are the equivalent of .filter and .map but they provide a pair of (index, element) instead of simply the current element.

We need to loop over all elements except the last two, however we still need access these elements, so instead of using .dropLast we simply filter elements in using their index value. After that, we want to transform each element in a triple of elements containing the current and the two subsequent ones. To do that, we use .mapIndexed as it will allow us accessing the following elements based on the current index, and create a Triple instance for each element.

Once we have our transformation, we simply need to pass the result to our other function like so:

countIncrease(buildTriples(input).map { it.sum() })

We are also leveraging an extension function to compute the sum of the Triple.

Source code

You can find the source code for my solution here.

Thank you very much for reading!

Refactoring code to Java 8 Stream API

Eric Lloyd — Sun, 16 May 2021 08:55:48 +0000

You may be wondering why a blog post in 2021 is mentioning Java 8, as it came out over 7 years ago.
The reason is that I have come across a lot of Java codebase which are indeed using Java 8 or a later version, however they are not always leveraging the Java 8 API.
I often find code blocks which could be refactored. What I mean here by refactoring is that these code blocks could leverage the Java 8 APIs to become more readable, more concise (i.e. less verbose) and also less outdated.

I have found that doing this kind of very small refactoring is a good way to get familiar with an unknown codebase — which you can do while reading through the code.
Always make sure that there is a good suite of tests for the code you are refactoring, and to regularly run them every time you make changes.

In this blog post, I would like to share some common patterns that I have come across, and how they can be changed — focusing on the usage of Java 8 Stream API.

Examples

Filtering

One very common action in programming is to filter a collection of elements. To do this prior to Java 8, you would do the following:

List<String> longWords(final List<String> words, final int threshold) {
    List<String> longWords = new ArrayList<>();
    for (String word : words) {
        if (word.length() > threshold) {
            longWords.add(word);
        }
    }
    return longWords;
}

The above method could be replaced with the following:

List<String> longWords(final List<String> words, final int threshold) {
    return words.stream()
            .filter(word -> word.length() > threshold)
            .collect(toList());
}

This is more concise, and more readable.

Counting

Instead of filtering, you may simply want to count the long words.
Prior to Java 8 you could do:

List<String> longWords(final List<String> words, final int threshold) {
     List<String> longWords = new ArrayList<>();
     for (String word : words) {
        if (word.length() > threshold) {
            longWords.add(word);
        }
     }
     return longWords;
}

With Java 8 Stream API you can do:

long longWordsCount(final List<String> words, final int threshold) {
    return words.stream()
            .filter(word -> word.length() > threshold)
            .count();
}

Grouping

Another common action is to group elements from a list, based on a specific condition or predicate.
For example, you may want to group words by length. To do this prior to Java 8, you would do the following:

Map<Integer, List<String>> groupByWordLength(final List<String> words) {
    Map<Integer, List<String>> groups = new HashMap<>();
    for (String word : words) {
        int length = word.length();
        if (groups.containsKey(length)) {
            List<String> group = groups.get(length);
            group.add(word);
        } else {
            List<String> group = new ArrayList<>();
            group.add(word);
            groups.put(length, group);
        }
    }
    return groups;
}

This is starting to be already quite verbose for such a common task. Thankfully it becomes a lot simpler leveraging Java 8 Stream:

Map<Integer, List<String>> groupByWordLength(final List<String> words) {
    return words.stream()
            .collect(groupingBy(word -> word.length()));
}

This one liner is also a lot more readable.

Partitioning

One slightly less common but still frequent action is to partition a list, based on a specific condition or predicate. Continuing with our "words" example, we can partition words based on their lengths. To do this prior to Java 8, you would do the following:


List<List<String>> partitionByWordLength(final List<String> words, final int threshold) {
    List<String> shortWords = new ArrayList<>();
    List<String> longWords = new ArrayList<>();
    for (String word : words) {
        if (word.length() > threshold) {
            longWords.add(word);
        } else {
            shortWords.add(word);
        }
    }
    return Arrays.asList(shortWords, longWords);
}

With Java 8 Stream API, you can refactor the method to be:


List<List<String>> partitionByWordLength(final List<String> words, final int threshold) {
    Collection<List<String>> partition = words.stream()
        .collect(partitioningBy(word -> word.length() > threshold))
        .values();
    return new ArrayList<>(partition);
}

Here we need to convert the Collection to an ArrayList because the type returned by partitioningBy collector is a Map.
We could have simply returned the Map of Lists which contains two keys, true and false.

Transforming

Transformation are also very common, a transformation is when you want to apply a function to each element in a list which converts it to something else.
There are a lot of method which use the following patterns:

static List<String> fooTransform(final List<String> words) {
    List<String> fooStuff = new ArrayList<>();
    for (String word : words) {
        String foo1 = word.repeat(3);
        String foo2 = foo1.stripTrailing();
        String foo3 = foo2.toUpperCase();
        fooStuff.add(foo3);
    }
    return fooStuff;
}

Using streams, you can do the following:

List<String> fooTransform(final List<String> words) {
    return words.stream()
        .map(word -> fooThing(word))
        .collect(toList());
}

private String fooThing(final String word) {
    String foo1 = word.repeat(3);
    String foo2 = foo1.stripTrailing();
    return foo2.toUpperCase();
}

Extracting the inner block computation of the for loop in a helper method allows to then have a clean and readable transformation with map.

Concatenation

Another common practice is to fetch data from two or more different place and then merge the elements into a final list.
To do this prior to Java 8, you could do the following:

List<String> concat(final List<String> words1, final List<String> words2) {
    List<String> concat = new ArrayList<>();

    for (String word : words1) {
        concat.add(word);
    }

    for (String word : words2) {
        concat.add(word);
    }

    return concat;
}

This can be transformed to a (fairly long) one liner :

List<String> concat(final List<String> words1, final List<String> words2) {
    return Stream.concat(words1.stream(), words2.stream()).collect(toList());
}

The above snippet is leveraging the concat method for Streams, and then collecting back to a List.
If you want to add a condition in you concatenation, you can easily do it by using the filter method on each word stream.

Summation

Having a raw collection of elements does not always give good insights, and we often need to do computation on the list like calculting the average, the sum etc.
For example, we might want to know the sum of characters in a list of words for words longer than a given threshold.
To do this prior to Java 8, you could do the following:

int characterSum(final List<String> words, final int threshold) {
    int sum = 0;
    for (String word : words) {
        int length = word.length();
        if (length > threshold) {
            sum += length;
        }
    }
    return sum;
}

This can be achieved by leveraging the reduce method of Streams. This method perform what is called a reduction on the elements of the stream. It takes on two parameters, an initial value for the reduction and an accumulator.
The simplest example is a sum:

int characterSum(final List<String> words, final int threshold) {
    return words.stream()
            .map(word -> word.length())
            .filter(length -> length > threshold)
            .reduce(0, (sum, l) -> sum + l);
}

The accumulator function is applied at each iteration with the current temporary sum at that given iteration.
The initial value here is 0.

Performance comparison

From what I have read, using streams does not degrade performance. However, I did not want to simply guess, rather I wanted to test it myself using the above examples.
I have made very simple and approximate (or "quick and dirty") timer tests using System.nanoTime() before and after executing the method on my laptop.

For all the examples, I have generated either 5 hundred thousands or 5 millions random words, and executed the method 100 times.
The results I will share below is the average executing time in milliseconds.

I will also use both the stream() and the parallelStream() method for comparison.
When using the parallelStream() method, it creates multiple substreams which are processed in parallel by different threads. The intermediary results of each substream then gets combined when collecting.
However, note that you have to be careful when using parallelStream():

iteration operation should not depend/interfere on/with each other
iteration operation should not modify a common mutable variable

Filtering

Reusing my filtering example, the results are the following:

Java 7: 23,66 ms
Java 8 sequential stream: 24,01 ms
Java 8 parallel stream: 11,82 ms

Counting

Reusing my counting example, the results are the following:

Java 7: 20,75 ms
Java 8 sequential stream: 20,79 ms
Java 8 parallel stream: 9,11 ms

Grouping

Reusing my grouping example, the results are the following:

Java 7: 17,24 ms
Java 8 sequential stream: 17,98 ms
Java 8 parallel stream: 13,36 ms

Partitioning

Reusing my partitioning example, the results are the following:

Java 7: 8,71 ms
Java 8 sequential stream: 10,40 ms
Java 8 parallel stream: 7,40 ms

Transforming

Reusing my transforming example, the results are the following:

Java 7: 92,78 ms
Java 8 sequential stream: 77,86 ms
Java 8 parallel stream: 67,22 ms

Concatenation

Reusing my concatenation example, the results are the following:

Java 7: 26,72 ms
Java 8 sequential stream: 22,54 ms
Java 8 parallel stream: 26,52 ms

Summation

Reusing my summation example, the results are the following:

Java 7: 22,13 ms
Java 8 sequential stream: 22,52 ms
Java 8 parallel stream: 11,64 ms

Results

Disclaimer that my testing was "quick and dirty" and that execution time depends on a lot of factor, especially in Java, such as startup time, number of threads available, number of resource available for the JVM, etc.
So take the results with as approximations.

Sequential streams

It seems that sequential streams perform slightly worse that for/loop in most cases.
However, from my point of view — unless you are optimizing for performance — the tradeoff between having code that is more readable and concise, meaning more testable and maintainable versus slight worse performance makes using Java 8 Stream completely worth it.

Parallel streams

Parallel streams usually performs a lot better that for/loop.
When the operation does not depend on the order of the iteration, and each iteration does not modify any shared variable — using parallel streams is a good way to increase the performance of your looping logic.

Conlusion

Java 8 Stream API allows to have code that is more readable and more concise. This is very valuable for making code easier to test and maintain.
Refactoring to using Java 8 Stream is a good habit and can allow you to make small improvements to a new codebase while learning how things work.
So I would recommend you start trying to identify classes or methods that are using old looping patterns and replace them with streams when applicable.