algorithms – Solving quadratic assignment problem with two metrics using MIP solver

The problem is the following following:

N = {1,...,m} - servers;
Q = {q{1},...,q{m}} - the required amount of resources for tasks, where qi is the required amount of resources for task i;
T = {1, ..., k} - tasks;
V = {v{1}, ..., v{k}} - the amount of resources on servers, where vi is the amount of resources on server i;
DA - the matrix with the amount of data transferred between tasks. DA{i,j} is the amount of data transferred between task i and task j;
NC - the matrix with the network speeds between servers. NC{i,j} is the network speed between server i and server j;
IC - the matrix with a penalty for assigning two tasks on the same server. IC{i,j} is the penalty for assigning task i and task j on the same server;
x{i,j} = 0 if task i is assigned on server j and x{i, j} = 1 if task i is not assigned on server j

I want to minimize the total communication time and minimize the total penalty in two steps. The first step is to minimize the total penalty and the second step is to minimize the total communication time with the penalty constraint.

Total communication time:
enter image description here

Total penalty:
enter image description here

Constraints:
each task is assigned to exactly on server:
enter image description here

the total required amount of resources for tasks on servers does not exceed the available amount of resources on the servers:
enter image description here

and:
enter image description here

Hence the optimization problem is:
enter image description here

To make the objective function linear, I add constraints z{t1,t2,n1,n2} >= x{t1,n1}+x{t2,n2}-1, z{t1,t2,n1,n2} <= x{t1,n1}, z{t1,t2,n1,n2} <= x{t2,n2}, 0 <= z{t1,t2,n1,n2} <= 1

First step:
enter image description here

Let min_penalty be the result of the first step, then the second step:
enter image description here

Is everything correct?

P.S. Sorry for the grammar mistakes and formatting.

recursion – probability based variable assignment

What does assign x = o with probability 0.25 and x = 1 with probability 0.75 mean in any piece of code?
For example if we have some function like below

test(n)
if x = 1
  return test(n)
else 
   return test(n+2)

So that means that the probability of assigning 1 to x is high hence the “test(n)” will run more than “test(n + 2)”.
Is my understanding correct?

python – Rock paper scissors coding assignment

I had a coding assignment to write a Rock Paper Scissors game. The main task is not to show a solution but rather to test the coding style. The rules are such:

Problem:

rock is “O”, paper is “()”, scissors is “8<“. George and John play RPC(rock, paper and scissors) a couple of times. I receive 2 input strings containing their actions. it is guaranteed that both strings contain the same number of actions and the actions will be in {‘O’, ‘()’, ‘8<‘}. Each game gets scored. If a player wins, he gets 2 points, if the game is draw, both get 1 point. the program has to calculate which player has how many points and what is the most common match up and how many times it occured.

Example:

input:

OOOOOO()()8<

()()8<8<8<O()O()

output:

George 12 John 6 O8< 3

explanation:

George plays O John plays O the game outcome is O()
George points: 0


George plays O John plays O the game outcome is O()
George points: 0


George plays O John plays O the game outcome is O8<
George points: 0


George plays O John plays O the game outcome is O8<
George points: 2


George plays O John plays O the game outcome is O8<
George points: 4


George plays O John plays O the game outcome is OO
George points: 6


George plays () John plays () the game outcome is ()()
George points: 7


George plays () John plays () the game outcome is ()O
George points: 8


George plays 8< John plays 8< the game outcome is 8<()
George points: 10


most common match up is rock vs scissors and it happened 3 times. Final output:

George 12 John 6 O8< 3

My thoughts and code:

Thoughts:

Initially I made the solution in plain functions. After that I thought that I should wrap the code into classes, because it would be good to have variables like george’s points available between different functions. I did not add any validators for the input data. I am not sure if that was correct or not. In the statement it was clearly explained that the input data will be passed correctly. I did not thought on edge cases like having empty inputs. The code that calculates who won the game maybe looks hardcoded as it again relies on correct input.

Code:

SCISSORS = "8<"
PAPER = "()"
ROCK = "O"
GEORGE_LOSES = ("8<0", "O()", "()8<")

class Player:
    def __init__(self, hands="") -> None:
        self.hands = hands
        self.index = 0
        self.hand_len = len(self.hands)
        self.points = 0
        self.current_hand = ""

    def has_hands(self):
        return self.index < self.hand_len

class RPS_solver:
    def __init__(self, george=Player(), john=Player()) -> None:
        self.george = george
        self.john = john
        self.george_result = ""
        self.john_result = ""
        self.matchup_outcome = ""
        self.matchup_dict = {"default": 0}
        self.most_common_matchup = "default"

    def next_item(self, player):
        if(player.hands(player.index) == "O"):
            player.index += 1
            return ROCK 
        if(player.hands(player.index) == "8"):
            player.index += 2
            return SCISSORS 
        else:
            player.index += 2
            return PAPER

    def count_match_points(self):
        if self.george.current_hand == self.john.current_hand:
            self.george.points += 1
            self.john.points += 1

        elif self.matchup_outcome in GEORGE_LOSES:
             self.john.points += 2

        # assuming all input data is correct
        else:
             self.george.points += 2

    def get_most_common_matchup(self):
        if self.matchup_outcome in self.matchup_dict:
            self.matchup_dict(self.matchup_outcome) += 1
        else:
            self.matchup_dict(self.matchup_outcome) = 1
        if(self.matchup_dict(self.matchup_outcome) > self.matchup_dict(self.most_common_matchup)):
            self.most_common_matchup = self.matchup_outcome


def solution(george: str, john: str)  -> str:
    # refactoring ca be added to assert correction of data
    # 
    #The input of your function consists of two strings - 
    # the symbols that George showed in the order he showed
    #  them and a second string with the
    #  set of symbols that John showed in the order he showed them.

    george_player = Player(george)
    john_player = Player(john)

    solver = RPS_solver(george_player, john_player)
    while(solver.george.has_hands()  and solver.john.has_hands()):
        solver.george.current_hand = solver.next_item(solver.george)
        solver.john.current_hand = solver.next_item(solver.john)

        #match outcome
        solver.matchup_outcome = solver.george.current_hand + solver.john.current_hand

        # count match points:
        solver.count_match_points()

        # determine current most common matchup:
        solver.get_most_common_matchup()

    result_str = f"George {solver.george.points} John {solver.john.points} {solver.most_common_matchup} {solver.matchup_dict(solver.most_common_matchup)}"
    return result_str

print(solution("OOOOOO()()8<", "()()8<8<8<O()O()"))

Question:

How can I improve this code for style (maybe even performance). Should I add validators if input is being guaranteed? Should I add comments ?

group policy – Configuring User Rights Assignment policies via GPO

I’m configuring a GPO to add a local group to a user right policy, however, when configuring through GPO, all existing members of the right are removed on GPO application. You can obviously add all the users to the GPO to make sure these are retained but when the user is only local to the remote server e.g. NT SERVICESQLSERVERAGENT, this can’t be added to the GPO from the DC which simply doesn’t recognise it.

Am I right in assuming it’s a case of using GPO when the user right should only contain domain accounts/groups, built-in users/groups but if additional user types need to be added then manual addition should be used instead?

Shame if it’s the latter. Could do with being able to configure this via GPP like you can with local users/groups and having the option to retain the existing members which would address this initial observation

Cheers
Jamie

c# – Why usage of assignment operator or loops discouraged in functional programming?

What is it in functional programming that makes a difference?

Functional programming is by principle declarative. You say what your result is instead of how to compute it.

Let’s take a look at really functional implementation of your snippet. In Haskell it would be:

predsum pred numbers = sum (filter pred numbers)

Is it clear what the result is? Quite so, it is sum of the numbers meeting the predicate. How is it computed? I don’t care, ask the compiler.

You could possibly say that using sum and filter is a trick and it doesn’t count. Let implement it without these helpers then (though the best way would be to implement them first).

The “Functional Programming 101” solution that doesn’t use sum is with recursion:

sum pred list = 
    case list of
        () -> 0
        h:t -> if pred h then h + sum pred t
                         else sum pred t

It is still pretty clear what is the result in terms of single function call. It is either 0, or recursive call + h or 0, depending on pred h. Still pretty straighforward, even if the end result is not immediately obvious (though with a little bit of practice this really reads just like a for loop).

Compare that to your version:

public int Sum(Func<int,bool> predicate, IEnumerable<int> numbers){
    int result = 0;
    foreach(var item in numbers)
        if (predicate(item)) result += item;
    return result;
}

What is the result? Oh, I see: single return statement, no surprises here: return result.

But what is result? int result = 0? Doesn’t seem right. You do something later with that 0. Ok, you add items to it. And so on.

Of course, for most programmers this is pretty obvious what happens in a simple funciton like this, but add some extra return statement or so and it suddenly gets harder to track. All the code is about how, and what is left for the reader to figure out – this is clearly a very imperative style.

So, are variables and loops wrong?

No.

There are many things that are much easier explained by them, and many algorithms that require mutable state to be fast. But variables are inherently imperative, explaining how instead of what, and giving little prediction of what their value may be a few lines later or after a few loop iterations. Loops generally require state to make sense, and so they are inherently imperative as well.

Variables and loops are simply not functional programming.

Summary

Contemporarily funcitonal programming is a bit more of style and a useful way of thinking than a paradigm. Strong preference for the pure functions is in this mindset, but it’s just a small part actually.

Most widespread languages allow you to use some functional constructs. For example in Python you can choose between:

result = 0
for num in numbers:
    if pred(num):
        result += num
return result

or

return sum(filter(pred, numbers))

or

return sum(n for n in numbers if pred(n))

These functional expressions fit nicely for that kind problems and simply makes code shorter (and shorter is good). You shouldn’t thoughtlessly replace imperative code with them, but when they fit, they are almost always a better choice.

algorithms – my dsa teacher gave a assignment which is really confusing (i asked my teacher about it but she said just google it and find it out yourself)

Write best case, worst case and average case time complexity of following categories of
algorithm–

a. Constant time

b. Linear time

c. Logarithmic time

d. Polynomial time

e. Exponential time

(this question which is where I am mostly confused as like if she had asked best case, worst case and average case of like a linear search thats easy but what this question is trying to ask is the question for me and yes i did as my teacher as said in the title)

(sorry my knowledge in dsa is quite low rn as i keep on getting 5 to 6 assignments per week and have very little time for self study)

Codility Assignment php – Code Review Stack Exchange

I had my Microsoft codility round and got 2 questions in PHP, mentioned below, I would like to know your thoughts on the questions.

A company has N factories, each producing some pollution every month. The company has decided to reduce its total fume emissions by equipping some of the factories with one or more filters. Every such filter reduces the pollution of a factory by half. When a second (or subsequent) filter is applied, it again reduces by half the remaining pollution emitted after fitting the existing filter(s). For example, a factory that initially produces 6 units of pollution will generate 3 units with one filter, 1.5 units with two filters and 0.75 units with three filters. You are given an array of N integers describing the amount of pollution produced by the factories. Your task is to find the minimum number of filters needed to decrease the total sum of pollution by at least half.

class Solution { public int solution(int() A); }
which, given an array of integers A of length N, returns the minimum number of filters needed to reduce the total pollution by at least half.

Example: 1. Given A = (5, 19, 8, 1), your function should return 3. The initial total pollution is 5 + 19 + 8 + 1 = 33. We install two filters at the factory producing 19 units and one filter at the factory producing 8 units. Then the total pollution will be 5 + ((19 / 2)/ 2) + (8 / 2) + 1 = 5 + 4.75 + 4 + 1 = 14.75 which is less than 33 / 2 = 16.5, so we have achieved our goal.

Example: 2. Given A = (10, 10), your function should return 2, because we may install one filter at each factory.

Write an efficient algorithm.

c++ – Class using resource pointer- Resource class with copy constructor and copy assignment operator

I have created two simple classes: resource and container. below is the full code. actually container keeps resources. and in the beganing it will get all the resources and store them in datalist of resources. The other function is simply prints out all the resources in container. Please review my code and see if its ok just review it and let me know what are the wrongs and rights in the code, thanks

////
// Created by noone on 18/8/21.
//
#include <iostream>
#include <cstring>
#define Max 10
class resource{
private:
public:
    int id;
    char name(10);

    resource(int id,char name1(10)):id(id)
    {

        std::memcpy(name,name1,Max);
    }
    resource& operator= (const resource& arr2){
        if (this == &arr2){ return *this; } //make sure you aren't self-assigning
        //same as copy constructor from here
        id=arr2.id;
        std::memcpy(name,arr2.name,Max);
        return *this;
    }


};
class container
{
public:
    container(resource *new_resource,int i)
    {
            size=0;
            size=i;
            datalist=(resource *)malloc(sizeof(resource)*i);
            for(int x=0;x<i;x++)
            {
                datalist(x).id=new_resource(x).id;
                std::memcpy(datalist(x).name,new_resource(x).name,std::strlen(new_resource(x).name));

            }


    }
    void print_all_resources()
    {
        std::cout<< "total "<<size<<" resources found"<<std::endl;
        for(int i=0;i<size;i++)
        {
            std::cout<<"Printintg first resource"<<i+1<<std::endl;
            std::cout<<datalist(i).name << " | "<< datalist(i).id<<std::endl;
        }
    }

private:
    resource *datalist;
    int size;
};

int main()
{
    resource resource1(10,"abc");
    resource resource2(20,"xyz");
    resource r()={resource2,resource1};

    container c(r,2);
    c.print_all_resources();

}

java – Hungarian algorithm for optimal assignment

The assignment problem is about assigning tasks to workers, where each pair (worker, task) has a cost. The Hungarian algorithm builds an optimal solution for this problem. It has two variants, depending on the representation of the cost relationships: one with bipartite graphs, and one with cost matrices. I have implemented the latter form as described here because I had trouble making Wikipedia’s step 3 example into an algorithm. The goal is to produce a library that I can use in another project in which I intend to assign mentors to students based on their likelihood of getting along.

In short, the algorithm modifies the cost matrix to make zeroes appear and selects some of them to build an optimal solution. It uses two types of marks, stars (for zeroes belonging to the candidate solution) and primes (for zeroes that could replace starred zeroes in the solution). It moves between 6 steps:

  1. The matrix is preprocessed (validity checks, optional rotation to have at least as many columns than rows, subtraction of the minimum value of each row to all values of the same row and then the same for columns)
  2. Greedily prepare a candidate solution by starring zeroes
  3. Check if the candidate solution is complete; if yes, return it; else, go to the next step
  4. Try to find a zero that could replace a starred one in the candidate solution; if one is found, go to the next step; else, go to step 6
  5. Follow an alternating path of primed and starred zeroes to modify the candidate solution, and go back to step 3
  6. Modify some values in the matrix to make more zeroes appear, and go back to step 4.

For example, take the following cost matrix.

0 1 2 3
0 1 2 25 13
1 5 7 25 15
2 10 13 16 13
3 17 21 11 18
4 15 15 15 14

The algorithm must output the following solution, with a total cost of 2 + 5 + 13 + 11 = 31 (and the last row is not assigned any task because the worker is too expensive).

0 1 2 3
0 X
1 X
2 X
3 X
4

My code in Java 11 works as intended on several hand-made examples and standard edge cases (null input, non-square cost matrix, worst-case matrix for this algorithm). If you find any case that is poorly handled, I would be happy to know but that is not my main concern here.

I used junit5 to write unit tests and I feel that the test framework I wrote might be needlessly complex. I wanted to get a separate test result for each run of a test method on each of its input, and several test methods will have the same input.
I wrote the TestFrameWork and TestArguments interfaces as a way to use junit5’s streams of tests, and each test class must implement the TestFrameWork interface with a utility class implementing the TestArguments interface. Then, most tests only need writing a simple lambda function performing only the actual verification. I wonder if that is a good idea or a terrible one.

Additionally, I made three methods package-private rather than private because I wanted to test them specifically, which smells fishy as well: the constructor, reduceInitialMatrix and getState (which only exist to test reduceInitialMatrix, and that seems even worse). I have a bit of trouble setting the balance between encapsulation and testing, I’ll gladly take any advice on this point too.

All the original code base can be found on my github. For this question, I have edited it a bit: instead of making HungarianSolver extend the abstract Solver and inherit the javadoc, I made the HungarianSolver stand-alone and put the javadoc directly in it. I built and ran the tests on the modified version to make sure that I didn’t break anything.

HungarianSolver.java

package AssignmentProblem;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Implementation of the HungarianAlgorithm.
 */
class HungarianSolver {

    final private int()() costMatrix;
    final private int()() assignments;
    final private int() rowAssignments;
    final private int() colAssignments;
    final private int nRows;
    final private int nCols;
    final private boolean() coveredRows;
    final private boolean() coveredCols;
    final private int() starredRows;
    final private int() starredCols;
    final private int() primedRows;
    final private int() primedCols;
    private int numberCoveredCols;
    final private boolean transposed;

    /**
     * Instantiates a new solver on the given cost matrix. The proper way to get
     * the solution of the assignment problem with a {@link HungarianSolver} is
     * to call {@link #initialise(int()())} rather than directly the constructor.
     *
     * @param costMatrix
     */
    HungarianSolver(int()() costMatrix) {
        Solver.checkMatrixValidity(costMatrix);
        if (costMatrix.length > costMatrix(0).length){
            //flip matrix to have more columns than rows
            transposed = true;
            nRows = costMatrix(0).length;
            nCols = costMatrix.length;
            this.costMatrix = new int(nRows)(nCols);
            for (int i = 0; i < nRows; i++) {
                for (int j = 0; j < nCols; j++) {
                    this.costMatrix(i)(j) = costMatrix(j)(i);
                }
            }
        } else {
            this.costMatrix = costMatrix;
            nRows = costMatrix.length;
            nCols = costMatrix(0).length;
            transposed = false;
        }
        assignments = new int(nRows)(2);
        rowAssignments = new int(transposed ? nCols : nRows);
        colAssignments = new int(transposed ? nRows : nCols);
        coveredRows = new boolean(nRows);
        coveredCols = new boolean(nCols);
        starredRows = new int(nRows);
        starredCols = new int(nCols);
        primedRows = new int(nRows);
        primedCols = new int(nCols);
        Arrays.fill(starredRows, -1);
        Arrays.fill(starredCols, -1);
        Arrays.fill(primedRows, -1);
        Arrays.fill(primedCols, -1);
        Arrays.fill(rowAssignments, -1);
        Arrays.fill(colAssignments, -1);
        for (int() assignment : assignments) {
            Arrays.fill(assignment, -1);
        }
    }

    protected static HungarianSolver initialise(int()() costMatrix) {
        HungarianSolver result = new HungarianSolver(costMatrix);
        result.reduceInitialMatrix();
        result.solveReducedMatrix();
        return result;
    }

    /**
     * Returns the column index assigned to each row.
     * @return The result of the assignment problem from the row perspective.
     * The i-th element of the output is the index of the column assigned to the
     * i-th row, or -1 if the row has not been assigned.
     */
    public int() getRowAssignments() {
        return this.rowAssignments;
    }

    public int() getColumnAssignemnts() {
        return this.colAssignments;
    }

    /**
     * Returns the pairs of row and column indices of the assignments.
     * @return The result of the assignment problem as pairs. Each element of 
     * the output is an assigned pair whose first element is the index of the 
     * row and the second element is the index of the column. Unassigned rows
     * and columns are not included.
     */
    public int()() getAssignments() {
        return this.assignments;
    }

    /**
     * Reduces the values of the matrix to make zeroes appear. This
     * corresponds to the first step of the Hungarian Algorithm.
     */
    void reduceInitialMatrix() {
        //first part: reduce all rows
        for (int() row : costMatrix) {
            int min = row(0);
            for (int val : row) {
                if (val < min) {
                    min = val;
                }
            }
            for (int j = 0; j < row.length; j++) {
                row(j) -= min;
            }
        }
        //second part: reduce all columns
        for (int j = 0; j < nCols; j++) {
            int min = costMatrix(0)(j);
            for (int() row : costMatrix) {
                if (row(j) < min) {
                    min = row(j);
                }
            }
            for (int() row : costMatrix) {
                row(j) -= min;
            }
        }
    }

    /**
     * Performs the main loop of the Hungarian algorithm.
     */
    private void solveReducedMatrix() {
        //Steps 0 and 1 have been preprocessed
        //Step 2 : initial zero starring
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (costMatrix(i)(j) == 0 && starredCols(j) == -1) {
                    coveredCols(j) = true;
                    numberCoveredCols++;
                    starredRows(i) = j;
                    starredCols(j) = i;
                    break;
                }
            }
        }
        while (numberCoveredCols < nRows) {
            int() position = primeZero();
            while (position == null){
                //Perform step 6
                //Get minimal unmarked value
                int min = Integer.MAX_VALUE;
                for (int i = 0; i < nRows; i++) {
                    if (coveredRows(i)) {
                        continue;
                    }
                    for (int j = 0; j < nCols; j++) {
                        if (coveredCols(j)) {
                            continue;
                        }
                        if (costMatrix(i)(j) < min) {
                            min = costMatrix(i)(j);
                            if (min == 1){
                                break;
                            }
                        }
                        if (min == 1){
                            break;
                        }
                    }
                }
                //modify the matrix
                for (int i = 0; i < nRows; i++) {
                    for (int j = 0; j < nCols; j++) {
                        if (!coveredRows(i)) {
                            /* If the row is uncovered and the column is covered, 
                        then it's a no-op: add and subtract the same value.
                             */
                            if (!coveredCols(j)) {
                                costMatrix(i)(j) -= min;
                            }
                        } else if (coveredCols(j)) {
                            costMatrix(i)(j) += min;
                        }
                    }
                }
                //go back to step 4
                position = primeZero();
            }
            //perform step 5
            invertPrimedAndStarred(position);
        }
        //format the result
        int assignmentIndex = 0;
        if (transposed){
            for (int i = 0; i < nCols; i++){
                rowAssignments(i) = starredCols(i);
                if (starredCols(i) != -1){
                    assignments(assignmentIndex)(0) = starredCols(i);
                    assignments(assignmentIndex)(1) = i;
                    assignmentIndex++;
                }
            }
            System.arraycopy(starredRows, 0, colAssignments, 0, nRows);
        } else {
        for (int i = 0; i < nRows; i++){
                rowAssignments(i) = starredRows(i);
                if (starredRows(i) != -1) {
                    assignments(assignmentIndex)(0) = i;
                    assignments(assignmentIndex)(1) = starredRows(i);
                    assignmentIndex++;
                }
            }
            System.arraycopy(starredCols, 0, colAssignments, 0, nCols);
        }
    }

    /**
     * Primes uncovered zeroes in the cost matrix.
     * Performs the fourth step of the Hungarian Algorithm.
     * @return the (rowIndex,colIndex) coordinates of the primed zero to star 
     * that has been found, or null if no such zero has been found.
     */
    private int() primeZero() {
        Queue<Integer> uncoveredColumnQueue = new LinkedList<>();
        for (int i = 0; i < nRows; i++) {
            if (coveredRows(i)) {
                continue;
            }
            for (int j = 0; j < nCols; j++) {
                if (coveredCols(j) || costMatrix(i)(j) > 0) {
                    continue;
                }
                //Found a non-covered zero
                primedRows(i) = j;
                primedCols(j) = i;
                if (starredRows(i) == -1) {
                    return new int(){i,j};
                } else {
                    coveredRows(i) = true;
                    coveredCols(starredRows(i)) = false;
                    numberCoveredCols -= 1;
                    //ignore the rest of the row but handle the uncovered column
                    uncoveredColumnQueue.add(starredRows(i));
                    break;
                }
            }
        }
        while (!uncoveredColumnQueue.isEmpty()){
            int j = uncoveredColumnQueue.remove();
            for (int i = 0; i < nRows; i++){
                if(coveredRows(i) || costMatrix(i)(j) > 0) {
                    continue;
                }
                primedRows(i) = j;
                primedCols(j) = i;
                if (starredRows(i) == -1){
                    return new int(){i,j};
                } else {
                    coveredRows(i) = true;
                    coveredCols(starredRows(i)) = false;
                    numberCoveredCols -= 1;
                    uncoveredColumnQueue.add(starredRows(i));
                }
            }
        }
        return null;
    }
    
    /**
     * Stars selected primed zeroes to increase the line coverage of the matrix.
     * Performs the fifth step of the Hungarian Algorithm.
     * @param position array of size 2 containing the row and column indices of 
     * the first primed zero in the alternating series to modify.
     */
    private void invertPrimedAndStarred(int() position){
        int currentRow = position(0);
        int currentCol = position(1);
        int tmp;
        starredRows(currentRow) = currentCol;
        while (starredCols(currentCol) != -1){
            //Move star to its new row in the column of the primed zero
            tmp = starredCols(currentCol);
            starredCols(currentCol) = currentRow;
            currentRow = tmp;
            //Move star to its new column in the column of the previously 
            //starred zero
            tmp = primedRows(currentRow);
            starredRows(currentRow) = tmp;
            currentCol = tmp;
        }
        //set starredCols of last changed zero and reset primes and lines covering
        starredCols(currentCol) = currentRow;
        for (int i = 0; i < coveredRows.length; i++){
            coveredRows(i) = false;
            primedRows(i) = -1;
        }
        //in next step, all columns containing a starred zero will be marked
        //--> do it right away
        for (int j = 0; j < nCols; j++){
            if(!coveredCols(j) && starredCols(j) != -1){
                numberCoveredCols++;
                coveredCols(j) = true;
            }
            //if a column contained a prime zero, it will still contain one
            //after the inversion, so the case where a column needs to be 
            //uncovered does not arise
            primedCols(j) = -1;
        }
    }

    /**
     * @return The internal state of the cost matrix.
     */
    int()() getState() {
        return this.costMatrix;
    }

    /**
     * Checks the validity of the input cost matrix.
     * @param costMatrix the matrix to solve.
     * @throws IllegalArgumentException if {@code costMatrix } is not 
     * rectangular (e.g. rows do not all have the same length).
     */
    static void checkMatrixValidity(int()() costMatrix)
            throws IllegalArgumentException{
        if (costMatrix == null){
            throw new IllegalArgumentException("input matrix was null");
        }
        if (costMatrix.length == 0){
            throw new IllegalArgumentException("input matrix was of length 0");
        }
        for (int() row : costMatrix){
            if (row.length != costMatrix(0).length){
                throw new IllegalArgumentException("input matrix was not rectangular");
            }
        }
    }
}

TestArguments.java

package test.tools;

/**
 * Interface defining the general contract that inner classes should implement
 * to ease the unit testing.
 * 
 * Concrete classes implementing it should provide a unique constructor similar
 * to the main one of the class parameter, and override the toString object 
 * method.
 *
 * @param <T>   class under test: the arguments will be used to generate 
 * instances of that class.
 */
public interface TestArguments<T> {
    /**
     * Initialises an object to use in a test.
     * @return
     */
    T convert();
}

TestFrameWork.java

package test.tools;

import static org.junit.jupiter.api.DynamicContainer.dynamicContainer;
import static org.junit.jupiter.api.DynamicTest.dynamicTest;

import java.util.Map;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Stream;

import org.junit.jupiter.api.DynamicNode;
import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.function.Executable;

public interface TestFrameWork<T, S extends TestArguments<T>> {
    /**
     * @return a {@link Stream} of arguments to initialise an object to test.
     */
    Stream<S> argumentsSupplier();
    
    default String testName(String methodName, S args){
        return String.format("%s.%s on %s", 
                this.getClass().getCanonicalName(), methodName, args);
    }
    /**
     * Forges a {@link DynamicTest} to run the input test for each element 
     * returned by the implementation of 
     * {@link TestFrameWork#argumentsSupplier()}.
     * @param methodName    to set as the test name.
     * @param tester        to run as the test.
     * @return  a stream of nodes running the test.
     */
    default Stream<DynamicTest> test(String methodName, Consumer<S> tester){
        return test(argumentsSupplier(), methodName, tester);
    }

    /**
     * Forges a {@link Stream} of {@link DynamicNode} that runs in independent
     * {@link DynamicTest} instances each {@link Executable} returned by the 
     * input {@link Function} on each element returned by the implementation of
     * {@link TestFrameWork#argumentsSupplier()}.
     * @param methodName    to set as the test container's name.
     * @param testerStream  to generate the {@link Stream} of test using for 
     * each element the {@link String} as a suffix in the test name and the
     * {@link Executable} as the test to run.
     * @return  a stream of nodes running the tests.
     */
    default Stream<DynamicNode> testContainer(String methodName, 
            Function<S, Stream<Map.Entry<String, Executable>>> testerStream){
        return testContainer(argumentsSupplier(), methodName, testerStream);
    }
    /**
     * Forges a {@link DynamicTest} to run the input test for each element 
     * of a {@link Stream} of arguments.
     * @param stream        of arguments, the tests will be run on each 
     * element.
     * @param methodName    to set as the test name.
     * @param tester        to run as the test.
     * @return  a stream of nodes running the tests.
     */
    default Stream<DynamicTest> test(Stream<S> stream, String methodName, Consumer<S> tester){
        return stream.map(args
                -> dynamicTest(testName(methodName, args), () -> tester.accept(args)));
    }
    /**
     * Forges a {@link Stream} of {@link DynamicNode} that runs in independent
     * {@link DynamicTest} instances each {@link Executable} returned by the 
     * input {@link Function} on each element of the input {@link Stream}.
     * @param stream        of arguments, the tests will be run on each 
     * element.
     * @param methodName    to set as the test container's name.
     * @param testerStream  to generate the {@link Stream} of test using for 
     * each element the {@link String} as a suffix in the test name and the
     * {@link Executable} as the test to run.
     * @return  a stream of nodes running the tests.
     */
    default Stream<DynamicNode> testContainer(Stream<S> stream, String methodName, 
            Function<S, Stream<Map.Entry<String, Executable>>> testerStream){
        return stream.map(args
                -> {
                    String message = testName(methodName, args);
                    return dynamicContainer(message, 
                            testerStream.apply(args).map(entry 
                                    -> dynamicTest(message + entry.getKey(), entry.getValue())));
                });
    }
}

HungarianSolverTest.java

package AssignmentProblem;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Stream;
import org.junit.jupiter.api.Assertions;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.TestFactory;
import test.tools.TestArguments;
import test.tools.TestFrameWork;

public class HungarianSolverTest implements TestFrameWork<HungarianSolver, HungarianArgument> {

    @TestFactory
    public Stream<DynamicTest> testInitialiseValidInput() {
        //Check that initialise does not crash on valid input.
        //Correctness of the result is checked in tests linked to the methods getting the results.
        return test("initialise (valid input)", v -> v.convert());
    }
    
    @TestFactory
    public Stream<DynamicTest> testInitialiseInvalidInput(){
        Stream<HungarianArgument> cases = Stream.of(
                new HungarianArgument(null, null, null, null, "null cost matrix"),
                new HungarianArgument(new int(0)(0), null, null, null, "size 0 cost matrix"),
                new HungarianArgument(new int()(){{0}, {0,1}, {0,1,2},{0,1},{0}}, null, null, null, "non-rectangular cost matrix"));
        return test(cases, 
                "initialise (invalid input)", 
                v -> Assertions.assertThrows(IllegalArgumentException.class, 
                        () -> v.convert()));
    }

    @TestFactory
    public Stream<DynamicTest> testGetRowAssignments() {
        return test("getRowAssignments", v -> assertArrayEquals(v.expectedRowAssignment, v.convert().getRowAssignments()));
    }

    @TestFactory
    public Stream<DynamicTest> testGetColumnAssignemnts() {
        return test("getColumnAssignments", v -> assertArrayEquals(v.expectedColAssignment, v.convert().getColumnAssignemnts()));
    }

    @TestFactory
    public Stream<DynamicTest> testGetAssignments() {
        Comparator<int()> comparator = (first, second) ->
            Integer.compare(first(0), second(0)) == 0 ? Integer.compare(first(1), second(1)) : Integer.compare(first(0), second(0));
        return test("getAssignments", v-> {
            /*
            There is no contract on the ordering of the result values.
            */
            int()() assignments = v.convert().getAssignments();
            Arrays.sort(assignments, comparator);
            Arrays.sort(v.expectedMatrixResult, comparator);
            assertArrayEquals(v.expectedMatrixResult, assignments);
        });
    }

    @TestFactory
    public Stream<DynamicTest> testReduceInitialMatrix() {
        Stream<HungarianArgument> cases = Stream.of(
                new HungarianArgument(new int()(){{25, 40, 35}, {40, 60, 35}, {20, 40, 25}}, 
                        new int()(){{0, 0, 10}, {5, 10, 0}, {0, 5, 5}}, 
                        null, null, "square 3*3 matrix"),
                new HungarianArgument(new int()(){{150, 400, 450},{200, 600, 350}, {200, 400, 250}},
                        new int()(){{0, 50, 250}, {0, 200, 100}, {0, 0, 0}},
                        null, null, "second square 3*3 matrix"),
                new HungarianArgument(new int()(){{70, 40, 20, 55},{65, 60, 45, 90},{30, 45, 50, 75},{25,0,55,40}},
                        new int()(){{50, 20, 0, 0},{20, 15, 0, 10},{0, 15, 20, 10},{25, 0, 55, 5}},
                        null, null, "square 4*4 with initial zeroes matrix"),
                new HungarianArgument(new int()(){{1,2,25,13},{5,7,25,15},{10,13,16,13},{17,21,11,18},{15,15,15,14}},
                        new int()(){{0,2,9,16,13},{0,3,11,19,12},{14,12,5,0,3},{0,0,0,5,0}}, 
                        null, null, "5*4 matrix without initial zeroes")
        );
        return test(cases, 
                "reduceInitialMatrix", 
                v -> {
                    HungarianSolver solver = v.convertWithConstructor();
                    solver.reduceInitialMatrix();
                    assertArrayEquals(v.expectedMatrixResult, solver.getState());
                });
    }

    @Override
    public Stream<HungarianArgument> argumentsSupplier() {
        int worstCaseSize = 200;
        int()() worstCaseMatrix = new int(worstCaseSize)(worstCaseSize);
        for (int i = 0; i < worstCaseMatrix.length; i++) {
            for (int j = 0; j < worstCaseMatrix(i).length; j++){
                worstCaseMatrix(i)(j) = (i+1)*(j+1);
            }
        }
        int() worstCaseLinearExpectation = new int(worstCaseSize);
        Arrays.setAll(worstCaseLinearExpectation, i -> worstCaseSize-i-1);
        int()() worstCaseExpectedAssignments = new int(worstCaseSize)(2);
        for (int i = 0; i < worstCaseSize; i++){
            worstCaseExpectedAssignments(i)(0) = i;
            worstCaseExpectedAssignments(i)(1) = worstCaseSize-i-1;
        }
        return Stream.of(new HungarianArgument(new int()(){{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}},
                new int()(){{0,1},{1,2},{2,0}}, new int(){1,2,0}, new int(){2,0,1}, "simple 3*3 matrix"),
                new HungarianArgument(new int()(){{2000,6000,3500},{1500, 4000, 4500},{2000,4000,2500}},
                new int()(){{0,0},{1,1},{2,2}}, new int(){0,1,2}, new int(){0,1,2}, "mildly complex 3*3 matrix"),
                new HungarianArgument(new int()(){{1,2,3,4},{5,6,7,8},{9,10,11,12}},
                new int()(){{0,0},{1,1},{2,2}}, new int(){0,1,2}, new int(){0,1,2,-1}, "complex 4*3 matrix with equality case"),
                new HungarianArgument(new int()(){{1,2,25,13},{5,7,25,15},{10,13,16,13},{17,21,11,18},{15,15,15,14}},
                new int()(){{0,1},{1,0},{2,3},{3,2}}, new int(){1,0,3,2,-1}, new int(){1,0,3,2}, "first complex 5*4 matrix without equality case"),
                new HungarianArgument(new int()(){{1,2,25,13},{5,7,25,15},{10,13,16,14},{17,21,11,18},{15,15,15,13}},
                new int()(){{0,1},{1,0},{2,3},{3,2}}, new int(){1,0,3,2,-1}, new int(){1,0,3,2}, "second complex 5*4 matrix without equality case"),
                new HungarianArgument(worstCaseMatrix, worstCaseExpectedAssignments,
                worstCaseLinearExpectation, worstCaseLinearExpectation, "worst case " + worstCaseSize + "*" + worstCaseSize + " matrix")
        );
    }
    
}

class HungarianArgument implements TestArguments<HungarianSolver>{
    final int()() costMatrix;
    final int()() expectedMatrixResult;
    final int() expectedRowAssignment;
    final int() expectedColAssignment;
    private final String name;
    HungarianArgument(int()() costMatrix, int()() expectedMatrixResult, 
            int() expectedRowAssignment, int() expectedColAssignment,
            String name){
        this.costMatrix = costMatrix;
        this.expectedMatrixResult = expectedMatrixResult;
        this.expectedRowAssignment = expectedRowAssignment;
        this.expectedColAssignment = expectedColAssignment;
        this.name = name;
    }
    @Override
    public HungarianSolver convert() {
        return HungarianSolver.initialise(costMatrix);
    }
    public HungarianSolver convertWithConstructor(){
        return new HungarianSolver(costMatrix);
    }
    
    @Override
    public String toString(){
        return this.name;
    }
}

macos – Why does Zsh complain of my variable assignment as “command not found”?

When I try to write a Zsh script on macOS Big Sur, Version 11.5.1, I noticed that it keeps failing to recognize my variables as variables.

Instead, Zsh treats them as UNIX-like commands.

Screenshot of the problem on the Terminal Application – variable assignment problem for Zsh shell scripts

In the screenshot linked above, I did the following on the Terminal application.

  • Showed the contents of the simple Zsh shell script.
  • Used the “ls -l” UNIX-like command to indicate its file permissions, and show that it is an executable Zsh shell script.
  • Executed the Zsh shell script, which shows that the Zsh script interpreter complains of how my variable name is a “command not found”.

The source code for my Zsh shell script is provided as follows:

#!/bin/zsh

unix_cmd = "ls -al"

Can you please kindly let me know what am I missing, and what did I do wrong?

I just want to assign values to variables in my Zsh shell scripts.

Thank you so much, and have a great day! Ciao!