u/Sad-Structure4167

It's funny that your comment was the only correct one in the entire thread.

search for the haroldbot x86 expression simplifier for ideas on how to do go forward

yes you can, but it is computationally hard to find small equivalent expressions, as an exercise try to do it assuming that the output table is binary, the problem pretty much asks you to find an expression that generates a given truth table. For k-bit outputs, you can repeat the process for each bit independently, and combine the expressions.

there is a reduction from 3sat in the directed subgraph homeomorphism paper by Fortune et al 1971

1. Finding a simple directed path over three vertices (s -> ... -> t -> ... -> u) in a directed graph is NP-complete, but the undirected case is solvable in polynomial time.
2. In perfect graphs, many hard optimization problems have a polynomial time solution.
3. You can partition a graph into edge disjoint cycles in polynomial time.
4. Generating steiner triplet systems is hard, but simple hill climbing solutions are reasonably effective.

E poi ci sono io che compro in base al prezzo/kg, funziona finchè non inizieranno a "riempire" il prodotto per farlo pesare.

Probably because the `while(neighbor.z > -1)` loop adds a non constant factor to the time complexity, you should precompute the neighbour info for all vertices before running A*

advanced SA techniques:
- Tezuka's method is useful when the seach space has unfeasible solutions. Modifying the cost function to penalize unfeasible solutions often doesn't work well because you get stuck in local minima. Tezuka's method consists in accepting unfeasible solutions with a geometrically decreasing probability, and then restarting the search from the last feasible solution.

• To speed up local search algorithms, in particular SA, when the evaluation cost is high, you can use zobrist hashing to avoid re-evaluating the same state multiple times. Zobrist hashing is used because you can compute the hash after a local move efficiently. It is important if you parallelize the SA algorithm to use a shared cache of states and their evaluations, to avoid having multiple threads or machines all evaluating the same states over and over.

My guess is that there is a total order of buttons s.t x < y iff it is always better to press x before y in all optimal upgrade sequences. So you can start with any random order, swap the order of two buttons if the time improves, and if there is no improving move then the solution is optimal. You shouldn't rely on guesses tho.

You can find an elegant algorithm in 'Uniformly Random Generation of Floorplans' by YAMANAKA et al, it generates a floorplan uniformly at random and it is based on an algorithm for enumerating mosaic floorplans.

It can't generate all possible subdivision, but it can generate wheels. It can't generate floorplans with 4-way crossings.

Recursion is a bad idea, use a multi-source shortest path algorithm, study the Bellman-Ford algorithm.

use standard quicksort but when the recursive call is completely contained in a subinterval just stop

I tested it, the problem is that some packings are too good, there can be wheel-shaped configurations that are hard to untangle after setting them up on the shelf, so it might be better to use a different algorithm.

if you want a very good solution, implement the Zhang et al algorithm described in "Approximating the longest paths in grid graphs", it partitions the original graph into disjoint cycles and then merges adjacent cycles repeatedly.

there are multiple approaches for 2d packing problems, you can find them mostly in the VLSI literature. Approaches differ primarly by the choice of the packing representation. Possible choices are polish expressions, skew binary trees, twin trees, o-trees, sequence pairs, constraint graphs. Some algorithms use force-directed approaches or recursive graph partitioning.

My suggestion is to use an algorithm based on the sequence pair representation and simulated annealing.

The algorithm solves the packing problem independently for each bins, so it has to start with a balanced partitionining of the shapes into the bins. This is the subset sum problem, we can use dynamic programming or heuristics to solve it.

Then, it initializes a sequence pair representation for all bins, evaluates it by building the packing and evaluating the occupied area. The evaluation function penalizes packings with an aspect ratio different from the bin shape.

Then the simulated annealing starts, the local moves considered are:

M1: swap two elements in the sequence pair of a random bin.

M2: swap two shapes across bins.

M3: rotate a shape in a random bin.

The evaluation function is reduced over all bins to avoid a solution with some very good packings and some very bad ones. I think you want to minimize the badness of the worst packing.

If you want help coding it you can send me a private message

Check temperatures, maybe the case is too dusty or the fan isn't spinning. You haven't fried anything, the cpu throttles down when overloaded, and if you can boot up the hard drive/ssd isn't damaged.

The nested purple room makes this harder, it's not clear why you subdivided it that way. If the algorithm only works with the binary terrain data, there will be a lot of ambiguous cases, especially involving corridors or nested rooms. But if the map/level/terrain data is more detailed maybe it's possible to have a better solution.

the key is how to do board shifts in the 4 directions. If you use 1 bit per cell and pack them horizontally, you can shift the board up/down by shifting the bitmask left/right by the number of columns. You can shift the board left/right by masking with (0x7f7f7f7f) or (0xfefefefe) and then shifting by 1 left/right, assuming 8x8 boards. The masks correspong do (0b01111111) and (0b11111110) patterns repeated, that select all bits in a row except the one that is shifted out, for each row.

it is not clear what the goal of OP is, but to give some guidance on all the variants proposed here, if the primary goal is to ensure good quality pairings, then use the binary search based solutions, because they give you a lower bound on the quality of the worst pairing. If you want maximize the number of matched peoples, but allow for bad pairings, use the hungarian or blossom algorithm directly.

If the time complexity exponent is too high, you can take a random subgraph instead of considering all pairs. If every person can be paired with at least 4 other random persons, the graph almost surely has a perfect matching.

Alternatively you could try to minimize the number of exchanges, I made some progress with a flow network model but then got stuck, I think it's NP-hard.

The network has a single source and single sink, and 2N intermediate nodes where N is the number of currencies. Add a (source, x) edge for each currency x with capacity equal to the remaining balance of that currency after paying the debt of the same currency. Add a (y, sink) edge for each currency y with capacity equal to the remaining debt of that currency. Then add all pairs of intermediate edges with capacity infinity. The maximum flow either saturates all sink edges or there is no solution. If there is no solution, remove the sink edges of less important currencies until all sink edges are saturated. If there is one currency left at the end, use the remaining balance to repay part of its debt.

The number of exchanges is the number of intermediate edges with non zero flow, which is hard to minimize.

fair, iirc all-pairs reachability and path related problems are hard for big DAGs, i.e we don't know if we can do better than O(N^2), but for 10k nodes it's fair game

OP wants to know for each internal node of the DAG and each sink node how many paths starting from that internal node reach that sink node, so you need as many variables as sink nodes, for each internal node, if I understand correctly OP's requirements and your algorithm.

saving the dp state in memory for each DAG sink vertex is going to be costly.

the second case sounds like bin packing, without knowing the input constraints it's hard to tell if a hard problem was intended. It's easy if you are only allowed to delete presentations, just guess the solution and the starting point and delete all necessary presentations, then take the best valid solution. If the input constraints are realistic (presentations are at least 10-15min long without microsecond precision), then it should be doable with backtracking.

there is nothing "fractal" in these works, if you zoom in the details are not self-similar to the whole. They are only "fractal" as in they have a "fractured" style.