Spanish Juggling problem
These are some notes to be shared about a specific kind of problem I am thinking about since yesterday.
Problem formulation
You are given a list of persons P, a list of capabilities (or skills) C, and a list of all the capabilities per person. A person can have any number of capabilities. For each capability, there is at least one person who possesses it. Find the smallest set of persons so that they, in total, have all capabilities.
(Optional:) If there are multiple possible smallest sets, find them all.
Changing the maximum upload file size with Nextcloud in a docker-compose setup
The Nextcloud documentation as of today does not mention how to adjust the settings for uploading large files when using Nextcloud in a docker-compose setup (or generally in a Docker container). It does mention, however, that the following PHP settings need to be adjusted:
php_value upload_max_filesize 16G php_value post_max_size 16G
So the issue is reduced to finding out how these values can be changed for the container running the Nextcloud image in the simplest way.
Most of the sites I found while trying to solve this recommend adding or changing an ini file in the container (e.g. setting up a bind mount). But this can actually be solved in a much simpler and potentially less fragile way! Check out this excerpt from an nextcloud.ini file inside the main Nextcloud container:
$ sudo docker exec -it nextcloud_app bash
root@42b3ec8ee31f:/var/www/html# grep -E '(upload_max_filesize|post_max_size)' /usr/local/etc/php/conf.d/nextcloud.ini
upload_max_filesize=${PHP_UPLOAD_LIMIT}
post_max_size=${PHP_UPLOAD_LIMIT}
Shrinking a QNAP Virtualization Station disk image
It’s not possible to shrink a disk image with QNAP’s Virtualization Station (as of version 3). Even growing it might not work through the QNAP UI depending on the details of the disk image. Here’s how to do it manually with qemu-img.
Preparation
- Create a backup of all data and check that it works. Messing with filesystems and disk images is a great way to corrupt your data.
- Check that there are no snapshots of the VM for which you want to manipulate the disk image (in one case I noticed a snapshot was created without me noticing it):
Indexed Priority Queue in C++
Basics
Priority queues are a useful data structure e.g. when you repeatedly need to access the largest or smallest element of a set of values but want more efficiency than keeping an array ordered. The C++ standard library contains std::priority_queue, which works well for basic use cases. It offers insertion of elements as well as access and removal of the minimum (or maximum). It does not, however, offer a method for changing the priority of a value, which is needed for some applications (like Dijkstra’s algorithm to find shortest paths in graphs). Often such a method is called decreaseKey or changeKey. This post offers an implementation using a binary heap which supports this operation in O(log(n)) time.
Efficient Union-Find in C++ – or: Disjoint-set forests with Path Compression and Ranks
tl;dr: https://github.com/nspo/graphs-cpp/blob/master/general/include/DisjointSets.h
Basics
Disjoint-set data structures are useful in cases where you have a (possibly very large) number of elements and want to repeatedly execute two operations: marking two elements as connected, and checking whether two elements are connected. A query of the latter kind does not necessarily mean that the two elements p and q were explicitly connected to each other by the caller – it is possible, e.g., that p was first connected to the element r, and only much later in time q was also connected to r.
The disjoint sets in the data structure are commonly represented by trees, where each node in the tree contains a link to its parent, the parent in turn contains a link to the parent’s parent, and so on. The node at the root of the tree contains contains a link to itself, i.e. it is its own parent. All nodes of a tree are in the same set. It can be easily checked whether two elements are in the same set by evaluating whether they have the same root. The set of trees is called the disjoint-set forest. While this approach is common and can be implemented efficiently, the C++ standard library does not contain an implementation – this post tries to offer one.
Let us assume the data structure is used for N elements, each having an index between 0 and N-1. The links to the parent nodes of all elements can then easily be saved in an array of length N. If parent[p] == q, then q is the parent of p. Whenever two sets containing the elements p and q should be merged, this can be achieved by attaching the root of one element to the root of the other.
NMPC with CasADi and Python – Part 3: State-space equations of a 2-DOF robot with SymPy or MATLAB
CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.
In this post, we will look at determining the system equations of a robot with two degrees of freedom in stace-space form. These state-space equations can be used for simulation and for developing a nonlinear model predictive controller. For some transformation tasks, Python with SymPy will be utilized and an alternative using the MATLAB Symbolic Math Toolbox will be shown.
During the following, we are considering a robot with two links, two masses at the end of the links, and motors applying torque as control input at the joints. A diagram of the robot is shown below.
NMPC with CasADi and Python – Part 2: Simulation of an uncontrolled system
CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.
In this post, we will try to simulate an uncontrolled system with a forward Euler and a 4th order Runge-Kutta integration method. The latter can be the base for future closed-loop simulations.
NMPC with CasADi and Python – Part 1: ODE and steady state
CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.
In this post, a file describing the system equations and a script to determine a steady-state setpoint will be developed. This older post contains similar code for CasADi inside MATLAB.
Linearize nonlinear state space equation in MATLAB at steady state setpoint
This post shows one way to linearize a nonlinear state equation 
function dx = ode(t, x, u)
% example ODE
dx1 = tan(x(4)) * x(2) + 2*u(2) - 1;
dx2 = x(1) - sin(x(2));
dx3 = 13 * x(4) + u(1) + 1;
dx4 = 2*x(1);
dx = [dx1; dx2; dx3; dx4];
end
Calculate Levenshtein distance in MATLAB (words or characters) with Wagner–Fischer algorithm
This is a MATLAB implementation of the Wagner–Fischer algorithm.