|
Sorry, I'm not familiar with the rules of this forum.
I don't know if you are interested in following my research on the resolution of my problem.
I plan to
* study in which case my problem can be reduced to a fractional knapsack problem;
* test different algorithms (greedy, branch and bound, genetics) and their relevance depending on the case.
Personally, when I help someone, I like him to tell me later the taken steps.
What about you? Do you want me to come back in a few weeks to tell you what steps I have taken?
So if you want to know, I'll come back to tell you about it. Otherwise, I keep it for myself.
Thanks again 
|
|
|
|
|
Thanks.
-- modified 2-May-19 10:18am.
|
|
|
|
|
Hi Everyone!!
I am working on logic for a Microcontroller that dynamically updates a screen via UART. The screen only accepts vector based commands to fill a coordinate with a square and a filled color. The command looks like so
fill x,y,h,w,<color>The PHP code I wrote so far takes the image and converts each pixel to the following format, However, there are tons of room for optimization. An idea I had was to take the image and find the most common color then set the whole screen to this color. Then find all pixel's within a given shade and make it the same color than that beings the fill command to a single command because it can then cover two squares by using the command x,y,2,1,<color>.
The goal is to generate the picture with lossy compression but without extremely affecting the image and as few FILL commands as possible.
It can be your own or someone else's algorithm.. just make it possible to redraw with least amount of commands
Examples of algorithms are like this.
Cycle through each pixel and neighboring pixels and if they are similar shade make them the same. Then find the most common color and set the background image to that color. then cycle through each pixel if it's not that background color fill in that color.
The least amount of times you have to cast the fill command to drop a pixel the better the algorithm!
A sample image that will be used is here
https://www.faichi.com/sites/default/fi ... %202_0.png[^]
In this case, the large portion of the map is gray, so its best to make that shade one distinct RGB565 color then set the image of the full background to that color using a single fill command.
Then cycle through each pixel and combine additional like colors to make the least amount of permutations to cast a fill command to fill a pixel or a subset of pixels.
When doing this without any compression you would have to cast nearly one fill command for each pixel and would take over 5 minutes to draw a screen which is not a doable solution however there should be a simple way to go upon this.
Sample PHP code.
<?php
$img = imagecreatefromjpeg("Path to Image that is 480x272");
$width = ImageSX($img);
$height = ImageSY($img);
for ($y = 0; $y < $height; $y++) {
for ($x = 0; $x < $width; $x++) {
$c = imageColorAt($img, $x, $y);
$r = ($c >> 16) & 0xFF;
$g = ($c >> 8) & 0xFF;
$b = $c & 0xFF;
$r = $r >> 3;
$g = $g >> 2;
$b = $b >> 3;
$oc = ($r << 11) | ($g << 5) | $b;
echo ("fill $x,$y,1,1,$oc<br>");
}
}
?>
If anyone has any Keyterms I may use to research this issue I'd be more then open to review them and any pointers in the right direction would be greatly appreciated!
Thanks everyone for your consideration!
modified 24-Apr-19 14:18pm.
|
|
|
|
|
|
Creating the output of the pixel's isn't exactly the part I am looking for guidance on but this is a useful read anyhow to keep on my radar. I think maybe I am looking for "image vectoring" perhaps? Im not sure if that the correct term.
|
|
|
|
|
There is 4x4 matrix type of bool (can be 0 or 1)
It looks like this e.g.:
(1)(1)(0)(0)
(1)(0)(0)(1)
(1)(0)(0)(1)
(1)(1)(0)(0)
That is input...
And output is list(array) of pairs of positions and that pair represents one area
for example
In first column there are four 1s, so it should return (0,0)&(0,3) (1x4)
After that step then it becomes:
[1](1)(0)(0)
[1](0)(0)(1)
[1](0)(0)(1)
[1](1)(0)(0)
that means that 1s are used
After that you can do (0,3)&(1,0) (it's 2x2)
And that means that group can pass over like it's folded paper(when iterating use i%4)
Also that means 1s that are used can be used again
[1][1](0)(0)
[1](0)(0)(1)
[1](0)(0)(1)
[1][1](0)(0)
And do that over and over until all 1s are used
There are rules:
- All 1s must be used
- Same 1s can be used more than once
- Width and height must be power of 2 (1,2,4)
that means groups can be (1x1,2x1,1x2,2x2,4x2,2x4,4x1,1x4,4x4) - Group can cross over border to get to the other side
(like folded paper; 0 can be connected with 3 and vice versa) - Logically number of areas should be minimum possible
- Area is defined by it's top left corner and it's bottom right corner
(In form of point) - Optional:
The times one [1] is used more than once must be maximum possible
Output for this example:
(0,3)&(1,0)
(3,1)&(0,2)
Also output can be done with more areas but this is only using two and it's wanted solution
There is example of one interesting matrix:
(1)(0)(1)(1)
(1)(0)(1)(0)
(1)(0)(1)(0)
(1)(0)(1)(1)
Output:
(3,3)&(0,0)(that means that all 4 corners are included in one area)
(0,0)&(0,3)
(2,0)&(2,3)
Another:
(0)(1)(1)(1)
(0)(1)(0)(1)
(1)(1)(0)(1)
(0)(0)(0)(0)
Output:
(0,2)&(1,2)
(1,1)&(1,2)
(1,0)&(2,0)
(3,0)&(3,1)
(3,1)&(3,2)
Preferable languange is any C type (C C++ C#)
|
|
|
|
|
Very interesting, but what is your question? If you are expecting someone here to write your homework assignment, then I am afraid you will be disappointed.
|
|
|
|
|
My question is:
Is there any idea I can start from I tried finding every group for each [one] left...
but it takes 16 ifs...
Also this is not my homework I'm just trying to implement algorithm of
"minimization of switching function" for digital circuits with visualising it so I need that output
|
|
|
|
|
Sorry, no idea. What algorithm is it supposed to follow?
|
|
|
|
|
|
I would try a "classifier".
Flatten it out to a 16 column "record".
4x4 is manageable; you should be able to construct your own "training data" with all combinations.
You then run your "sample" against the training data and have it "classify" your (flattened) matrix by comparing columns.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I would start by writing classifiers for all sub-sizes:
1x1 (trivial)
2x2
3x3
4x4
The previous level may be placed inside the next level in one of 4 positions, possibly allowing the creation of additional output lines. IOW, use recursion!
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
I work for a milk company and I have to deliver Milk to stores. I also have to pick up expired milk when there is some. Is there an algorithm or process that can track the sales and expired product to predict future sales and minimize the amount of expired product picked up?
|
|
|
|
|
I was wondering a problem from algorithm - Proving that a particular matrix exists - Stack Overflow[^] Somebody said that there is a solution found by a computer, but I was unable to find a proof.
Prove that there is a matrix with 117 elements containing the digits such that one can read the squares of the numbers 1, 2, ..., 100.
Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.
But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.
I found that if there is such a matrix mxn, we may assume without loss of generality that m<=n. Therefore, the matrix must be of the type 1x117, 3x39 or 9x13. But what kind of algorithm will find the matrix?
I have managed to do the program that checks if numbers to be added can be put on the board. But how can I implemented the searching algorithm?
|
|
|
|
|
Hi all,
I want to calculate the number of labels available on a roll.
Please help me to found the exact formula.
Thanks
|
|
|
|
|
|
I'm working on formulating an optimization problem to find the minimum weighted tree between a set of terminals (aka Steiner tree). The literature on Steiner tree formulations consider the set of terminals as input, and provides the minimum weighted tree connecting them (possibly also including non-terminal transit nodes). However, the structure of my problem requires these set of terminals to be decided "in conjunction with" the minimum Steiner tree between them. Hence, existing Steiner tree formulations based on cut-sets, multi-commodity flows, etc., are not applicable in my case, given lack of prior knowledge about the set of terminals.
Any suggestions on how to design a linear program for Steiner tree where the set of terminals is not provided as an input, and at best can be denoted by a set of decision variables?
|
|
|
|
|
The problem is the following:
Given N containers with different sizes between 1 and N (2 <= N <= 10^5), each of them placed in a line, determine how many places can be freed if one container can be placed in another only if its size is less that the others size and they don't have any other containers between them. Multiple placings can be made, so if there are containers placed in each other, they can be placed in another container (if the bottom container size is less than the others size), a container can be placed in another group of container (if its size is less than the top container size), and a group of containers can be placed in another group of containers with similar rules.
Example: if N = 8 and the containers are placed in the following order: 1 8 2 4 3 6 7 5, then 7 places can be freed; we place 3 in 4, then 2 in 3, 6 in 7, 5 in 6, 4 in 5, 7 in 8, and 1 in 2. This way all the containers can be packed in a single group.
My idea of solving this problem is the following: calculate the minimum difference between all the neighbour containers sizes, then find the first pair where this minimum appears and make a placement. Then repeat the whole process again until no placements can be made. Then calculate the freed places.
This can be done trivially in quadratic time, but that is too slow. The other thing that bothers me that this method may not lead to the optimal solution.
Note: I have to implement the algorithm in C++, and my program has to finish in 200ms. This is why a quadratic solution has no chance. Also, I don't want to have my job done by others, I posted this because I got stuck solving the problem, and needed some help to know if my approach is correct or how can I make optimizations.
modified 24-Apr-22 21:01pm.
|
|
|
|
|
You set no limit on N, so there is no solution that will always "finish in 200 ms" ... (which is a long time) ... unless you add a timer; if it runs too fast.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Hello,
First and foremost thank you very much to anyone who may be able to help. I am looking for anyone to help me understand the steps that need to be taken in order to predict the output of the following code:
var msg = 'hellohello'
for(x = 2; x < msg.length - 2; x++)
{
if(msg.length == 1)
{
for(var i = 0; i < 6; i++)
{
console.log(i);
}
}
else
{
for(var i = msg.length; i > (msg.length - 1); i--)
{
console.log(i);
}
}
}
|
|
|
|
|
One option would be to step through it with a debugger.
Another option (which will teach you more) is to "play computer". You read through the code, following the instruction at each line. For example:
var msg = 'hellohello'
(Create a label 'msg', and give it the value 'hellohello')
for(x = 2; x < msg.length - 2; x++)
(Create a label 'x', and give it the value 2. If x < msg.length - 2, execute the loop)
…
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
You should be the computer. Start at the beginning, keep a written note of the current values of x, i and the length of the message, and proceed to the next statement. It might seem tedious, but it will help you develop a skill that has will serve you well (as it has served me well in my 40+ years as a programmer).
|
|
|
|
|
Problem Statement :
Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints :
Flow on an edge doesn’t exceed the given capacity of the edge.
Incoming flow is equal to outgoing flow for every vertex except s and t.Dinic’s algorithm for Maximum Flow - Code Companion[^]
|
|
|
|
|
And you have a question ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hello to all! I need to solve the problem. An approximate representation and partial solution is already there. This controversial mathematical question can push you away, since I do not go into some important points. I just want to state the very idea. I hope someone has enough time and will interest you. In programming, we are all accustomed to using only the numerical number system. However, theoretically, there is a vector system. Why not try to implement it in such a way that the distances between the cells of information are also carriers of information? Due to this, the counting rate will be completely predetermined, and, accordingly, it will be possible to solve much more complex tasks. Below I have laid out my presentation, as an example of the simplest implementation can be represented through the creation of an emulator.
Can apply c/c++
// designation in area. Position Form.
arr1 =
Vector1 = Vector3 + Vector2, Vector4 + (-Vector5), Vector10 + (-Vector12), Vector16 + (-Vector17) = 1;
Vector2 = (-Vector3) + Vector1, Vector6 + (-Vector5), Vector15 + (-Vector13), Vector18 + (-Vector17) = 1;
Vector3 = Vector1 + (-Vector2), Vector4 + (-Vector6), Vector7 + (-Vector9), Vector16 + (-Vector18) = 1;
Vector4 = Vector1 + Vector5, Vector3 + Vector6, Vector10 + (-Vector11), Vector7 + (-Vector8) = 1;
Vector5 = (-Vector1) + Vector4, (-Vector2) + Vector6, Vector12 + (-Vector11), Vector13 + (-Vector14) = 1;
Vector6 = (-Vector5) + (-Vector2), (-Vector3) + Vector4, Vector15 + (-Vector14), Vector9 + (-Vector8) = 1;
Vector7 = Vector4 + Vector8, Vector3 + Vector9 = 1;
Vector8 = (-Vector6) + Vector9, (-Vector4) + Vector7 = 1;
Vector9 = Vector6 + Vector8, (-Vector3) + Vector7 = 1;
Vector10 = Vector4 + Vector11, Vector1 + Vector12 = 1;
Vector11 = (-Vector5) + Vector12, (-Vector4) + Vector10 = 1;
Vector12 = Vector5 + Vector11, (-Vector1) + Vector10 = 1;
Vector13 = Vector5 + Vector14, (-Vector2) + Vector15 = 1;
Vector14 = (-Vector6) + Vector15, (-Vector5) + Vector13 = 1;
Vector15 = Vector6 + Vector14, Vector2 + Vector13 = 1;
Vector16 = Vector1 + Vector17, Vector3 + Vector18 = 1;
Vector17 = (-Vector1) + Vector16, (-Vector2) + Vector18 = 1;
Vector18 = Vector2 + Vector17, (-Vector3) + Vector16 = 1;
// arr is an array containing the shape of the initial tetrahedron for defining the reference system in space.
// 4 conditions(directions) of expansion
Vector1 * 2, Vector4 * 2, Vector3 * 2, Vector10 * 2, Vector7 * 2, Vector16 * 2;
// if not, then
Vector1 * x^(x + 1), Vector4 * x^(x + 1), Vector3 * x^(x + 1), Vector10 * x^(x + 1), Vector7 * x^(x + 1), Vector16 * x^(x + 1);
Vector3 * (-2), Vector6 * 2, Vector2 * 2, Vector9 * 2, Vector15 * 2, Vector18 * 2;
// if not, then
Vector3 * (-x^(x + 1)), Vector6 * x^(x + 1), Vector2 * x^(x + 1), Vector9 * x^(x + 1), Vector15 * x^(x + 1), Vector18 * x^(x + 1);
Vector1 * (-2), Vector2 * (-2), Vector5 * 2, Vector12 * 2, Vector13 * 2, Vector17 * 2;
// if not, then
Vector1 * (-x^(x + 1)), Vector2 * (-x^(x + 1)), Vector5 * x^(x + 1), Vector12 * x^(x + 1), Vector13 * x^(x + 1), Vector17 * x^(x + 1);
Vector4 * (-2), Vector5 * (-2), Vector6 * (-2), Vector8 * 2, Vector11 * 2, Vector14 * 2;
// if not, then
Vector4 * (-x^(x + 1)), Vector5 * (-x^(x + 1)), Vector6 * (-x^(x + 1)), Vector8 * x^(x + 1), Vector11 * x^(x + 1), Vector14 * x^(x + 1);
x = 2^n
n = 1++
int r1 = sum(arr1; sum[arr1; g]);
// the sum of all vectors, in an arbitrary order g, in the range from 1 to 18
arr1 = sum(Vector1; Vector18);
arr2 = sum(Vector18; Vector36);
arrn = sum(18*n; n+18);
// reverse motion system.
// points of position with points in the center and continuous connection of vectors at points of separation are indicated
arr1_=
Line14 = Vector1(0; 0.5); Vector4(0; 0.5);
Line15 = Vector1(0.5; 1); Vector5(0; 0.5);
Line13 = Vector1(0; 0.5); Vector3(0; 0.5);
Line34 = Vector3(0; 0.5); Vector4(0; 0.5);
Line117 = Vector1(0.5; 1); Vector17(0; 0.5);
Line12 = Vector1(0.5; 1); Vector2(0.5; 1);
Line217 = Vector2(0.5; 1); Vector17(0; 0.5);
Line25 = Vector2(0.5; 1); Vector5(0; 0.5);
Line212 = Vector2(0.5; 1); Vector12(0; 0.5);
Line213 = Vector2(0.5; 1); Vector13(0; 0.5);
Line112 = Vector1(0.5; 1); Vector12(0; 0.5);
Line37 = Vector3(0; 0.5); Vector7(0; 0.5);
Line316 = Vector3(0; 0.5); Vector16(0; 0.5);
Line310 = Vector3(0; 0.5); Vector10(0; 0.5);
Line410 = Vector4(0; 0.5); Vector10(0; 0.5);
Line416 = Vector4(0; 0.5); Vector16(0; 0.5);
Line47 = Vector4(0; 0.5); Vector7(0; 0.5);
Line512 = Vector5(0; 0.5); Vector12(0; 0.5);
Line513 = Vector5(0; 0.5); Vector13(0; 0.5);
Line517 = Vector5(0; 0.5); Vector17(0; 0.5);
Line62 = Vector6(0; 0.5); Vector2(0; 0.5);
Line63 = Vector6(0; 0.5); Vector3(0.5; 1);
Line618 = Vector6(0; 0.5); Vector18(0; 0.5);
Line69 = Vector6(0; 0.5); Vector9(0; 0.5);
Line615 = Vector6(0; 0.5); Vector15(0; 0.5);
Line79 = Vector7(0.5; 1); Vector9(0.5; 1);
Line78 = Vector7(0.5; 1); Vector8(0.5; 1);
Line89 = Vector8(0.5; 1); Vector9(0.5; 1);
Line1012 = Vector10(0.5; 1); Vector12(0.5; 1);
Line1011 = Vector10(0.5; 1); Vector11(0.5; 1);
Line1112 = Vector11(0.5; 1); Vector12(0.5; 1);
Line1315 = Vector13(0.5; 1); Vector15(0.5; 1);
Line1314 = Vector13(0.5; 1); Vector14(0.5; 1);
Line1415 = Vector14(0.5; 1); Vector15(0.5; 1);
Line1617 = Vector16(0.5; 1); Vector17(0.5; 1);
Line1618 = Vector16(0.5; 1); Vector18(0.5; 1);
Line1718 = Vector17(0.5; 1); Vector18(0.5; 1);
Line64 = Vector6(0.5; 1); Vector4(0.5; 1);
Line65 = Vector6(0.5; 1); Vector5(0.5; 1);
Line611 = Vector6(0.5; 1); Vector11(0; 0.5);
Line614 = Vector6(0.5; 1); Vector14(0; 0.5);
Line68 = Vector6(0.5; 1); Vector8(0; 0.5);
// Expansion of the reverse system
// Superimposed on top in the same position with additional conditions.
Vector1 * 2, Vector4 * 2, Vector3 * 2, Vector10 * 2, Vector7 * 2, Vector16 * 2;
// if not, then
Vector1 * x ^ (x + 1), Vector4 * x ^ (x + 1), Vector3 * x ^ (x + 1), Vector10 * x ^ (x + 1), Vector7 * x ^ (x + 1), Vector16 * x ^ (x + 1);
Vector3 * (-2), Vector6 * 2, Vector2 * 2, Vector9 * 2, Vector15 * 2, Vector18 * 2;
// if not, then
Vector3 * (-x ^ (x + 1)), Vector6 * x ^ (x + 1), Vector2 * x ^ (x + 1), Vector9 * x ^ (x + 1), Vector15 * x ^ (x + 1), Vector18 * x ^ (x + 1);
Vector1 * (-2), Vector2 * (-2), Vector5 * 2, Vector12 * 2, Vector13 * 2, Vector17 * 2;
// if not, then
Vector1 * (-x ^ (x + 1)), Vector2 * (-x ^ (x + 1)), Vector5 * x ^ (x + 1), Vector12 * x ^ (x + 1), Vector13 * x ^ (x + 1), Vector17 * x ^ (x + 1);
Vector4 * (-2), Vector5 * (-2), Vector6 * (-2), Vector8 * 2, Vector11 * 2, Vector14 * 2;
// if not, then
Vector4 * (-x ^ (x + 1)), Vector5 * (-x ^ (x + 1)), Vector6 * (-x ^ (x + 1)), Vector8 * x ^ (x + 1), Vector11 * x ^ (x + 1), Vector14 * x ^ (x + 1);
x = 2^n
n = 1++
int r1 = sum(arr1_; sum[arr1_; G]);
G = Line g
// the sum of all vectors, in an arbitrary order g, in the range from 1 to 18
arr1_ = sum(0.5*Vector1 + 0.5*VectorN; 0.5*Vector18 + 0.5*VectorN);
0.5*Vector1 + 0.5*VectorN = 1 or 0.5
arr2 = sum(Vector18; Vector36);
arrn = sum(18*n; n+18);
// number of combinations and setting of numerical conditions
K(arr1) = 2 ^ x - 1
// if not, then
K(arr1_) = 2 ^ x - 1
// number of algorithms max movement on a diverging row
:Vectorn
(arr1 - 1) ^ 2 = 17 ^ 2 = 289
(arr_1 - 1) ^ 2 = 17 ^ 2 = 289
(arrn - 1) ^ 2
(arr_1 - 1) ^ 2
// max movement arr1
:K_maxr
= sum[1; (Vectorn-2)] + (Vectorn + Vectorn+1) or
= sum(Vector1; Vector16) + (Vector n + Vector n+1);
// min movement arr1
:K_minr
= Vectorn +(arrn-Vector g)
// max movement arr1_
: K_maxr
= sum[1; (Line n - 2)] + (Line n + Line n + 1)
// min movement arr_1
: K_minr
= Vectorn + (arr_n - Line g)
// the numerical designation must be replaced on vector combinations from maximum
// to minimum in the system arr1 and vice versa in the system arr1_
I'm not so good at writing code. Moreover, it is necessary to take into account all the subtleties of the low-level environment. It is difficult to explain, but if short, it is necessary to create an artificial vector environment inside the existing numerical (point). When compliance with several specific conditions, will be folded into a figurative array. Which, in turn, is the composition of the new elements (geometric) composite units appearing in space. If you are interested, I can tell you in more detail. I do not scream with pride about the prospects and uniqueness. But I am sure that this method of calculation has never been applied before. This is just an idea. And if it seems stupid to you, that's your opinion.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
