Tag: minimum

Is there a minimum color class cover algorithm for bipartite graphs?

Let $ G$ be a bipartite graph with color classes $ X, Y$ . Is there an algorithm for determining a minimum set $ S \subseteq X$ such that each $ y \in Y$ is a neighbor of some $ s \in S$ ?

Furthermore, are there any theoretical results related to this problem, such as bounds on the size of $ S$ based on degrees of vertices and sizes of vertex neighborhoods?

I feel like this is a really basic problem, but I’m having trouble finding anything related to it. Any help would be appreciated. Thank you.

Docker Minimum viable architecture [on hold]

My company is trying to adopt docker for new Web Services development on ASP dot net core. We use TFS as source control. My job is to come up with the minimum viable architecture for Asp Net core with Dockers. I have been doing POC’s with Windows server 2016.

Here are my thoughts on how we will build our architecture

Regisry

There is an concern in the company about code being saved in Docker hub. We could spin our own registry. But so far only Linux container is being supported. There is a windows 2016 and image [ stefanscherer/registry-windows] . I will have a hard time convincing my architect to use any non standard images. The only option would be installing Install Docker Desktop for Windows using Windows 10 or using Linux as Host OS to use the registry feature.

Is this a fair assessment on registry ?

Is it advised to have dedicated Host for Registry ?

Continuous Integration

I’ve been looking at Team City for CI. My thought is we can live without CI for now since Team City is new to us. I don’t know the how easy/hard it is to use TFS for this

Dedicated Docker Hosts

  • Registry Host on [ Linux or windows 10 ]
  • Development VM – For development of Api and creating and pushing docker images
  • Dev; QA ; PROD – We will manually pull and run images in a container using dotnet core default Kestrel web server.

What’s your thoughts on this ?

How to find the Eulerian circuit with the minimum accumulative angular distance within a Eulerian graph?


Context

For context, this problem is part of my attempt to determine the path of least inertia for a free and open-source laser scanner DAC API I am developing. The following problem arises during the vector image optimisation pass. I convert the 2D vector image into a graph of 2D positions and add blank edges (i.e. transparent lines) to represent the image as a strongly connected, undirected Eulerian graph from which I should be able to determine the optimal Eulerian circuit.

Problem

Given a strongly connected, undirected Eulerian graph (i.e. each vertex has an even degree), I’m trying to determine the Eulerian circuit that results in the minimum possible accumulative angle, where each vertex is a position in 2D space and each edge describes a straight line between the vertices.

My Solution Attempt

My attempt at solving this was to first simplify the problem by looking at each vertex individually. We know that each vertex must have an even degree, and thus for each vertex there must be an optimal set of incoming/outgoing edge pairs (where each edge is used once) that results in a minimum accumulative angular distance. By minimum accumulative angular distance, I’m referring to the sum of the difference between the result of the difference between the angle of each incoming/outgoing edge pair and a straight line. For example, given the following vertex A and its neighbours B, C, D and E:

enter image description here

an example of optimal pairs would be (DA, AB) and (EA, AC) as they are cumulatively the least sharp angles through which A may be traversed (and in turn would induce the least inertia), whereas the pairs (EA, AD) and (BA, AC) would be the least optimal as cumulatively they contain the sharpest angles to be traversed (resulting in the highest inertia).

Once the set of optimal pairs is determined for each vertex, I suspect the Eulerian Circuit can be created by starting at one of the vertices, picking a direction to begin and following the optimal pairs until the beginning is reached again.

My Solution Attempt Issues

Currently however I’m running into two issues.

  1. I don’t know for sure whether or not my assumption holds true for all Euler graphs (where all nodes have an even degree).
  2. I’m unsure of the best approach for determining the set of optimal edge pairs for each vertex. I suspect it may be possible to represent each vertex and its edges as a sub-graph and treat the problem as finding the shortest path (where the “shorter” distances are the paths through the vertex that result in the straightest angles), but I’m struggling to come up with a sub-graph representation that would allow me to do this.

Related Research

In section 3.4 of Accurate and Efficient Drawing Method for Laser Projection the paper describes using Hierholzer’s algorithm for finding an optimal Eulerian circuit with the amendment that during traversal of each vertex you select the unvisited edge along the angle closest to a straight line. One issue that occurs to me with this approach is that it is not clear to me that this always results in the absolute optimal circuit, only one that is probably more optimal than a naive construction without this added amendment.

Questions

  1. Is there an existing solution to the original Problem stated above? If so, is there somewhere I might read further on this?
  2. If not, does my attempted solution sound like a reasonable approach? If so, do you have an idea of how I might represent the sub-graph for determining the set of edge pairs resulting in the minimum accumulative angular distance for each vertex?
  3. If not, can you recommend an approach I might be able to take to make progress on solving the previously mentioned Problem?

Any advice appreciated!

Calculating minimum processing time for many recipes and tools

I originally asked this question on StackOverflow but a comment was made to the effect that my problem pertains to Job Shop Scheduling and that it was more of a comp sci problem than a programming problem.

It’s the first time I’ve come across this topic and I’ve tried researching with a view to solving my problem below, but to no avail – I am not an academic. Can anybody advise how I should be approaching this problem, or which algorithms I should research to help? Is it even possible to build something like this using DB queries alone (possibly with PL/SQL)?

My goal is to develop a capacity model for the manufacturing facility at work.

— text below copied from original source at https://stackoverflow.com/questions/55501683/calculating-minimum-processing-time-with-sql

I have a process monitoring application where I need to determine tool capacity requirements based on a loading forecast. I have a selection of “Equipment” that process the product using “Recipes”.

The key “rules” for the interaction are:

  • A recipe can be run on one or more equipment
  • An equipment can run one or more recipes
  • An equipment can only run one recipe at a time
  • Time taken to run a recipe is specific to the equipment / recipe combination.

So, for a given set of equipment, recipes, tool-to-recipe relationships & processing times, I need to determine what the quickest possible processing time is for a given loading.

The table below shows a possible interaction, where the numbers in the columns are process units (e.g. hours). I’ve assumed processing time is the same for each tool per recipe (despite the fourth point, above).

             |  Eqp#1  |  Eqp#2  |  Eqp#3  |  Eqp#4  |  Eqp#5     -------+---------+---------+---------+---------+-------     Rcp#1  |    5    |         |         |    5    |            Rcp#2  |    6    |         |         |    6    |    6       Rcp#3  |    3    |         |    3    |         |    3       Rcp#4  |         |    4    |    4    |         |            Rcp#5  |    2    |    2    |    2    |    2    |    2

Transposed:

      Equipment  |  Recipe  |  ProcessTime     -----------+----------+-------------     Eqp#1      |  Rcp#1   |     5            Eqp#1      |  Rcp#2   |     6            Eqp#1      |  Rcp#3   |     3            Eqp#1      |  Rcp#5   |     2            Eqp#2      |  Rcp#4   |     4            Eqp#2      |  Rcp#5   |     2            Eqp#3      |  Rcp#3   |     3            Eqp#3      |  Rcp#4   |     4            Eqp#3      |  Rcp#5   |     2            Eqp#4      |  Rcp#1   |     5            Eqp#4      |  Rcp#2   |     6            Eqp#4      |  Rcp#5   |     2            Eqp#5      |  Rcp#2   |     6            Eqp#5      |  Rcp#3   |     3            Eqp#5      |  Rcp#5   |     2

SQL for creating in DB:

      CREATE TABLE ProcessSample (          "Equipment"     VARCHAR2(16),          "Recipe"        VARCHAR2(16),          "ProcessTime"   NUMBER(3) );      INSERT INTO ProcessSample VALUES ( 'Eqp#1', 'Rcp#1', 5 );     INSERT INTO ProcessSample VALUES ( 'Eqp#1', 'Rcp#2', 6 );     INSERT INTO ProcessSample VALUES ( 'Eqp#1', 'Rcp#3', 3 );     INSERT INTO ProcessSample VALUES ( 'Eqp#1', 'Rcp#5', 2 );     INSERT INTO ProcessSample VALUES ( 'Eqp#2', 'Rcp#4', 4 );     INSERT INTO ProcessSample VALUES ( 'Eqp#2', 'Rcp#5', 2 );     INSERT INTO ProcessSample VALUES ( 'Eqp#3', 'Rcp#3', 3 );     INSERT INTO ProcessSample VALUES ( 'Eqp#3', 'Rcp#4', 4 );     INSERT INTO ProcessSample VALUES ( 'Eqp#3', 'Rcp#5', 2 );     INSERT INTO ProcessSample VALUES ( 'Eqp#4', 'Rcp#1', 5 );     INSERT INTO ProcessSample VALUES ( 'Eqp#4', 'Rcp#2', 6 );     INSERT INTO ProcessSample VALUES ( 'Eqp#4', 'Rcp#5', 2 );     INSERT INTO ProcessSample VALUES ( 'Eqp#5', 'Rcp#2', 6 );     INSERT INTO ProcessSample VALUES ( 'Eqp#5', 'Rcp#3', 3 );     INSERT INTO ProcessSample VALUES ( 'Eqp#5', 'Rcp#5', 2 );

Assuming the following recipe quantities, is it possible, with a query / PL/SQL to determine the minimum total processing time for the processes?

      Rcp#1 = 10     Rcp#2 = 8     Rcp#3 = 2     Rcp#4 = 6     Rcp#5 = 8

I can plot this out graphically, and show that stacking Rcp#2 on Eqp#5 six times (and other recipes elsewhere) gives me the minimum process time, but I can’t seem to arrive at this programatically. The table below shows a process matrix showing, per hour, which tool is running which recipe, showing a min process time of 36 hours (I hope it makes sense!)

            |            Equipment                       Hour  |  #1  |  #2  |  #3  |  #4  |  #5       ------+------+------+------+------+------     1     |   1  |   4  |   3  |   1  |   2       2     |   1  |   4  |   3  |   1  |   2       3     |   1  |   4  |   3  |   1  |   2       4     |   1  |   4  |   3  |   1  |   2       5     |   1  |   4  |   3  |   1  |   2       6     |   1  |   4  |   3  |   1  |   2       7     |   1  |   4  |   4  |   1  |   2       8     |   1  |   4  |   4  |   1  |   2       9     |   1  |   4  |   4  |   1  |   2       10    |   1  |   4  |   4  |   1  |   2       11    |   1  |   4  |   4  |   1  |   2       12    |   1  |   4  |   4  |   1  |   2       13    |   1  |   4  |   4  |   1  |   2       14    |   1  |   4  |   4  |   1  |   2       15    |   1  |   4  |   5  |   1  |   2       16    |   1  |   4  |   5  |   1  |   2       17    |   1  |   5  |   5  |   1  |   2       18    |   1  |   5  |   5  |   1  |   2       19    |   1  |   5  |   5  |   1  |   2       20    |   1  |   5  |   5  |   1  |   2       21    |   1  |   5  |   5  |   1  |   2       22    |   1  |   5  |   5  |   1  |   2       23    |   1  |   5  |      |   1  |   2       24    |   1  |   5  |      |   1  |   2       25    |   1  |      |      |   1  |   2       26    |   2  |      |      |   2  |   2       27    |   2  |      |      |   2  |   2       28    |   2  |      |      |   2  |   2       29    |   2  |      |      |   2  |   2       30    |   2  |      |      |   2  |   2       31    |   2  |      |      |   2  |   2       32    |      |      |      |      |   2       33    |      |      |      |      |   2       34    |      |      |      |      |   2       35    |      |      |      |      |   2       36    |      |      |      |      |   2       37    |      |      |      |      |           38    |      |      |      |      |           39    |      |      |      |      |           40    |      |      |      |      |

My real world example is more complex than this, I’ve just (hopefully) supplied enough information to explain what I’m trying to achieve. For example, I have tens of equipments running tens of different recipes.

Thanks for reading and for any advice.

Minimum backlight in Solus for AMD GPU is bright

When I boot into Solus 4.0 with a live USB, the backlight can go extremely low, it even flickers slightly (flickers in backlight intensity, not on/off). I would describe it as 4 times dimmer than the minimum allowed brightness on Windows 10 and Solus 4.0 (partition on hdd; not live USB).

I was very happy that the live USB allowed such a dim backlight, since I used to have to change colour icc profiles on Windows at night to “simulate” dimness (just lowering contrast). “Now I can actually lower the hardware backlight!” I said to myself, this behaviour was also present when using an Ubuntu live USB a few years ago.

After installing Solus, I realized I couldn’t lower the backlight as low as I could compared to the live USB, in fact it is the same minumum as in Windows. I did a lot of research and now know that I am using amdgpu (not pro) and not radeon drivers, my brightness range is from 0-255 (from /sys/class/backlight/amdgpu-bl0/brightness and max_brighness), manually setting brightness file to 0 does not achieve desired backlight intensity from live USB, no decimal or negative numbers are allowed (invalid argument).

I even went back and booted from a Solus live USB and everything was the same as far as I could tell, amdgpu drivers and 0-255 backlight range, however simply setting low integers in the brightness file yielding significantly dimmer backlight. I don’t know how to check if the drivers are the same version or anything else, so based on this info I’m asking if there’s any way to “port” the backlight behaviour of the Solus live USB (or Ubuntu for that matter) into my actual Solus partition.

About:

  • GNOME: 3.28.2
  • Processor: AMD A10-8700P (“Carrizo” APU)
  • Graphics: AMD Radeon R6 Graphics (part of APU; no dedicated graphics)

Code Chef’s Cleaning Tables: find the minimum number of tables to clean

Description:

Haku has been newly hired by Chef to clean tables at his restaurant. So whenever a customer wants a table, Haku must clean it.

But Haku happens to be a lazy boy. So in the morning, when the restaurant is opened, all the tables are dirty from night before.

The customer don’t leave the table unless they are politely requested to do so. And customers can order meal later again. So if they were already having a table, they can be served on the same table [Haku doesn’t have to clean :)]. But if they don’t have a table then they must be given some table [Haku must clean :(]

The restaurant has N tables. When a customer requires a table, he/she can occupy any unoccupied table. However if all tables are occupied, then Haku is free to ask politely any customer to leave his/her table. And the freed table can be given to the waiting customer.

Now Chef has the psychic ability to tell the order of customer meal requests for the entire day. Given this list, help Haku find the minimum number of times he has to clean the tables.

Link

Input:

First line contains integer T, number of test cases. First line of each test case contains 2 integers N, number of tables and M, number of customer orders. Followed by M integers on next line, which is the order in which customers ask for meal. Customers are referenced by integer C.

Output:

For each test case output the minimum number of times Haku must clean the table(s).

Code:

class Main {   public static int solve(int N, int[] orders) {     Map<Integer, LinkedList> positions = new HashMap<>();     for (int i = 0; i < orders.length; i++) {       int order = orders[i];       positions.computeIfAbsent(order, x -> new LinkedList<Integer>()).add(i);     }     Set<Integer> table = new HashSet<>();     //System.out.println(positions);     int count = 0;     for (int i = 0; i < orders.length; i++) {       int order = orders[i];       if (table.contains(order)) {         positions.get(order).removeFirst(); // remove the first entry         continue;       }       count++;       if (table.size() < N) {         positions.get(order).removeFirst(); // remove the first entry         table.add(order);         continue;       } else {         int farthestOrder = findIndex(table, orders, i, positions);         table.remove(farthestOrder);         table.add(order);       }     }     System.out.println("Count: " + count);     return count;   }    private static int findIndex(       Set<Integer> table, int[] orders, int i, Map<Integer, LinkedList> positions) {     // case 1: There is at least one order which is not seen in future     for (int order : orders) {       if (positions.get(order).size() == 0) {         return order;       }     }     // case 2: All the orders can be seen, find farthest     int max = -1;     for (; i < orders.length; i++) {       int order = orders[i];       int position = (int) positions.get(order).getLast();       max = Math.max(position, max);     }     return orders[max];   }    public static void main(String[] args) {     solve(2, new int[]{1, 2, 3, 4});     solve(2, new int[]{4, 1});     solve(3, new int[]{1, 2, 1, 3, 4, 1});     solve(3, new int[]{1, 2, 1, 3, 4});   } }

Question(s):

I assume that the solution is $ O(N^2)$ where $ N$ is the number of orders. Is there any linear time algorithm possible?

Set minimum quantity in product

I’m looking for a way to set a minimum quantity per product in a Drupal Commerce store.

I found this module which claims to do just this, but I can’t get it working and the project seems abandoned:

I found this one which is useful if you need to set a minimum in the order but it doesn’t help to set a minimum in products.

Is there any other way to do this?

Minimum number of parentheses to be removed to make a string of parentheses balanced

The task:

Given a string of parentheses, write a function to compute the minimum number of parentheses to be removed to make the string valid (i.e. each open parenthesis is eventually closed).

For example, given the string “()())()”, you should return 1. Given the string “)(“, you should return 2, since we must remove all of them.

const brackets = "()())()";

My functional solution:

const numberOfUnbalanced = brackets => Object.values(brackets   .split("")   .reduce((brackCounter, b) => {     b === "(" ? brackCounter.openBrackets++ :     brackCounter.openBrackets ? brackCounter.openBrackets-- :     brackCounter.closedBrackets++;      return brackCounter;   }, {openBrackets: 0, closedBrackets: 0})) .reduce((sum, b) => sum + b, 0);  console.log(numberOfUnbalanced(brackets));

My imperative solution:

function numberOfUnbalanced2(brackets) {   let openBrackets = 0, closedBrackets = 0;   for (let i in brackets) {     brackets[i] === "(" ? openBrackets++ :     openBrackets ? openBrackets-- :     closedBrackets++;   }   return openBrackets + closedBrackets; }  console.log(numberOfUnbalanced2(brackets));

Usually the functional approach is shorter and tend to be easier to understand in comparison to imperative approaches. However, in this case it doesn’t have any advantage to the imperative approach. I guess it is due to the nested structure in the functional solution.