#StackBounty: #algorithms #optimization #combinatorics #combinatory-logic What is an efficient algorithm to solve the following combina…

Bounty: 50

I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes:

  1. weight,
  2. shape (denoted by number of faces, $n_{rm block} in [4, 14]$, $n_{rm block}=4$ is a tetrahedron, $n_{rm block}=5$ is a pentahedron etc.),
  3. a rank number printed on the blocks,
  4. color, and
  5. material.

None of these attributes are unique, there might be more than one blocks with the same attributes.

The slots are marked with a number $n_{rm slot}$. Any block can be put in any slot, one slot can hold only one block. A solution must have all the slots filled in. There is a goodness score of a solution. If a block is put into a slot it receives a score $10 – |n_{rm block} – n_{rm slot}|$. After all the slots are filled, extra score is added to each block depending on the neighboring blocks. For each neighboring blocks matching both color and material, a block gets +3 score; for each neighboring blocks with either matching color or material, a block gets +1.5 score; for a non-matching neighbor no point is added. The total goodness score of the solution is the sum of all the blocks’ scores. Now a solution has to satisfy the two following constraints.

  1. a minimum goodness score
  2. a minimum average rank number (average of the rank numbers of all the blocks)

The inputs of the problem are:

  1. The map of the connected slots showing which slots are inter-connected,
  2. A list of available blocks with all of their attributes (5000~15000 blocks)
  3. Minimum goodness score necessary
  4. Minimum average rank necessary

The output of the problem is:

A solution with the lowest total weight of all the blocks.

If finding the lowest-weight-solution is not feasible within 10-15 minutes in Python, a good enough solution with total weight lower than a specified budget can be a plan B.


Get this bounty!!!

#StackBounty: #algorithms #runtime-analysis How does one heuristically determine if an algorithm has an exponential time complexity?

Bounty: 100

How does one easily determine if an algorithm has an exponential time complexity? The Word Break naive solution is known to have a time complexity of O(2n) but most people think its O(n!) because of the decreasing subsets as you go down the stack depth.

Word Break Problem:
Given an input string and a dictionary of words, find out if the input
string can be segmented into a space-separated sequence of dictionary
words.

The brute-force/naive solution to this is:

def wordBreak(self, s, wordDict):
    queue = [0]
    dictionary_set = set(wordDict)
    for left in queue:
        for right in range(left,len(s)):
            if s[left:right+1] in dictionary_set:
                if right == len(s)-1:
                    return True
                queue.append(right+1)
    return False

With the worst case inputs of:

s = 'aab'
wordDict = ['a','aa','aaa']

Results in a O(2n) time complexity of 23 ≈ 7:

example

Let me caveat this question with:

  1. I’m not looking for a performant solution so just ignore why the implementation is the way it is. There is a known O(n2) dynamic programming solution.
  2. I know there are similar questions asked on stackexchange, but none of them gave an easy to understand answer to this problem. I would like a clear answer with examples using preferably the Word Break example.
  3. I can definitely figure the complexity by counting every computation in the code, or using recurrence relation substitution/tree methods but what I’m aiming for in this question is how do you know when you look at this algorithm quickly that it has a O(2n) time complexity? An approximation heuristic similar to looking at nested for loops and knowing that it has a O(n2) time complexity. Is there some mathematical theory/pattern here with decreasing subsets that easily answers this?


Get this bounty!!!

#StackBounty: #algorithms #satisfiability #sat-solvers #constraint-satisfaction #constraint-programming CSP Forward checking with n-ary…

Bounty: 100

I have implemented my own CSP solver using a Backtracking algorithm.
Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that only works with Binary constraints.

The problem I have is that the CSP I try to solve has lots of n-ary constraints, making the FC algorithm mostly redundant.

Is there a way to enhance or replace my FC algorithm, so it works with n-ary constraints.
Or is there a “simple” procedure to convert n-ary constraints to binary constraints?

EDIT:
Added pseudo code (attempt) of the Forward Checking algorithm:

function ForwardChecking(variable, csp) list of variables with new domains, or failure
    for each constraint in connectedConstraints(variable) do
        if connectedVariable is assigned then
            if constraint is not satisfied then
                return failure
        else 
            for each value in connectedVariable.domain do
                connectedVariable.assign(value)
                if constraint is not satisfied do
                    remove value from connectedVariable.domain
                if connectedVariable.domain.count == 0 then
                    return failure
                add connectedVariable to solution
    return solution


Get this bounty!!!

#StackBounty: #algorithms #graphs #graph-theory #optimization Trying to find a human-usable method to figure out optimal round 1 openin…

Bounty: 50

I’m trying to figure out optimal round 1 openings for this game: http://generals.io/.

For the purposes of this question, I’ve simplified some of the rules and mechanics of the game, and I assume that there are no opponents.

Here are the basic rules/mechanics/assumptions:

  • The game is played on a board of size m * n, 16 <= m, n <= 20 (m and n are random).
  • A tile on the board can be one of:
    • City: The player starts the game owning 1 City. The City
      generates 1 Unit every 2 turns (on even-numbered turns). For the purposes of this, assume that there are no other Cities on the board.
    • Land: A Land tile can be occupied by moving at least 1 Unit onto it.
    • Mountain: Impassable tile.
  • Assume that about a third of the tiles are Mountains at random locations, and that all Lands are orthogonally connected to at least one Land or City (and so are all reachable from your City).
  • Every turn, the player can do one of two actions:
    • Idle: Nothing is done on this turn.
    • Move: The player chooses a tile where they have at least 2 Units. They then choose an orthogonally adjacent tile, which cannot be a Mountain, to Move the Units to. All but 1 of the Units will be transferred to this new tile. Only one Move action can be issued on each turn.
  • At the beginning of the game, it is turn 0. The City starts with 1 Unit, and will generate its first Unit on turn 2.
  • Each round consists of 50 turns. At the start of each round, all Lands generate 1 Unit.

Here is an example from Generals.io of a section of the game board on turn 22:
An example from Generals.io of a section of the game board on turn 22, showing a City, unoccupied Lands, occupied Lands and Mountains
In the above image, the player Idled until turn 20, then on turn 21 Moved (with 10 Units) east from the City. On turn 22 they Moved east again (with 9 Units) from the Land they occupied on turn 21.

Since the City generates 1 Unit every 2 turns, by turn 48 it will have generated 24 Units. So the theoretical maximum number of Lands that could be occupied by turn 50 is 24.

And so, the goal is to figure out an approach that can be used to find a set of actions (or whether any even exist) that would allow the player to occupy 24 Lands by turn 50, given a starting configuration of the game board. Ideally this would be an approach that a human could quickly use to calculate what the actions would have to be, since the game is played in semi-realtime (each turn lasts about 1 second, during which you can issue a Move action or not do anything and just Idle).

QUESTION: Can you come up with a method that a human could use (within ~20 seconds) to get 24 Lands on round 1 whenever a board configuration makes it possible?


I was trying to write myself a “cheat-sheet” to achieve the above. Here’s what I have so far.

Basic observations:

  • In order to have 24 Lands by turn 50, we must have spent 24 of the 50 turns Moving Units onto unoccupied Lands.
  • Therefore, we have 26 turns left that we can use to either Idle or Move Units onto occupied Lands.
  • Knowing this, we could generate some “action plans” and see if one of them fits our game board starting configuration.

Here’s the template/strategy that these “action plans” follow:

  • Begin by idling for I turns, I <= 26, I divisble by 2. (I divisible by 2 as the purpose of Idling at the start is to build up a sizeable number of Units in your City before Moving out with them to occupy Lands in a chain.)
  • You will now have floor(I / 2) + 1 Units in your City. Move out with these Units and occupy floor(I / 2) Lands over the next floor(I / 2) turns.
  • Since you’ve Idled for I turns, you now only have 26 - I turns left during which you can Idle or Move over occupied Lands. The rest of the turns must all be used to Move over (and so occupy) unoccupied Lands. The “action plan” lists the permutations in which you could utilize these 26 - I turns, given I.

So here are some explained “action plan” examples of the easiest cases, that seem to allow one to find a solution for quite a few starting board configurations. Once one is familiar with how these work, more concise/readable versions can be utilized as a cheat-sheet.

  • I## = “Idle”. Idle for ## turns.
  • M## = “Move”. Move all (but 1) Units (from your City) over ## occupied Lands, over the next ## turns.
  • O## = “Occupy”. Move all (but 1) Units (from your City or from an occupied Land) over ## unoccupied Lands (thereby occupying them), over the next ## turns.
  • @## = One of the above three actions will prefix this @## notation. Here, ## indicates the turn at which you start executing the prefixed action.

I = 26: You Idle for 26 turns, and thereafter you cannot Idle or Move over occupied Lands.

  • The only set of actions that works after Idling for 26 turns at the start is: I26@0, O13@26, O6@39, O3@45, O2@48.
  • This plan requires your City to be adjacent to 4 separate Land chains, of minimum lengths of 13, 6, 3 and 2.
  • It is easy enough to manually identify whether your starting City location satisfies the above.

I = 24: You Idle for 24 turns, and thereafter you have the following set of options for your last 2 I|M actions:

  • {{2}, {1, 1}}. (Meaning you could either do 2x I1|M1 actions, or 1x I2|M2 action.)
  • I’ve found that in general, one will rarely Idle after the initial long Idling phase. Mostly the above options would be used for M actions.
  • So one possible way of playing out this plan would be: I24@0, O12@24, O6@36, M1@42, O3@43, M1@46, O2@47, O1@49.
  • This plan could be used to get 24 Lands if your City spawns with one orthogonal side blocked by a Mountain, for instance. The other three sides would need to have the following lengths of separate chains of Lands: 13, 6, 1, 3 (connected to the 13 or 6 chain at a distance of 1 from the City), and 2 (connected to the 13 or 6 chain at a distance of 1 from the City).

Here is the concise version of the cheat-sheet that I’ve been using for round 1 openings in Generals.io:

  • I24:
    • {2}
    • {1, 1}
  • I22
    • {4}
    • {3, 1}
    • {2, 2}
    • {2, 1, 1}
    • {1, 1, 1, 1}
  • I20:
    • {6}
    • {5, 1}
    • {4, 2}
    • {4, 1, 1}
    • {3, 3}
    • {3, 2, 1}
    • {3, 1, 1, 1}
    • {2, 2, 2}
    • {2, 2, 1, 1}
    • {2, 1, 1, 1, 1}
    • {1, 1, 1, 1, 1, 1}

Before explaining my approach at using the cheat-sheet, there’s another important observation:

  • In order to have occupied 24 Lands by turn 50, the Unit that is generated by the City on turn 48 must Move to occupy a new Land. It only has 2 turns to do so. I assume that by this point, all 26 non-occupy turns have been used. And so, both of these turns would be used for new Land occupation (using the Units generated on turns 46 and 48).
  • This requires that at turn 48 your City would still have either an adjacent size 2 unoccupied Land chain or two separate adjacent (to the City) unoccupied Lands.
  • This helps narrow down the possibilities I look at in using the cheat-sheet.

So, here is how I use the cheat-sheet (keep in mind that all of the below has to be planned out within ~20 seconds, which is the length of time before the game reaches turn 20):

  • I identify the 2 Lands I will occupy using the Units generated on turns 46 and 48. (As mentioned above, these 2 Land tiles have to either be in a chain adjacent to the City, or be both separately adjacent to the City.)
  • These 2 Land tiles cannot be occupied before turn 46, narrowing down our occupation paths at the start.
  • I then identify the path that the initial (biggest) set of Units will take (after the long initial Idling time). Ideally, I try to choose a path that can scout towards the center of the board, but I prioritize not blocking potential future occupation paths.
  • For the remainder of the occupation paths, I repeat the following:
    1. I note the minimum number of occupied Lands that Units would have to Move through from the City in order to occupy a new Land chain.
    2. Using the above, I plan out a simple path that would obstruct further occupation paths as little as possible.
  • Finally, I check the cheat-sheet for a set of Move counts that satisfy the list of “minimum number of occupied Lands to Move through”.
    • If I find a matching set, then by following its initial Idle time, I should be able to execute the plan I made and get 24 Lands by turn 50.
    • If I don’t find an exactly matching set, I will try to find one that matches the list as much as possible, and go with that one. I go for a set where the numbers are smaller than required. The overall sum difference (between the required and the picked set) equals the number of Lands you miss out on.

I realize that some of the options on the cheat-sheet are fairly useless (such as I20: {1, 1, 1, 1, 1, 1}) and that the list of possible permutations would start to get too large for human use for smaller initial Idle lengths. This is why I am asking this question, in hopes of learning of a better method.


Get this bounty!!!

#StackBounty: #machine-learning #time-series #predictive-models #algorithms How to use predicted features in prediction?

Bounty: 50

I have ratings data.

My ratings data contains some technical features like the Originator (Channel), the exact day & hour of the broadcast, duration of the program etc. and, obviously, the label, which is the rating.
So the data looks like that:

+---------+------------+-----------------+----------------+----------------------------------+---------------+
| Program | Originator |      date       | Duration (min) | some other technical features…   | Actual rating |
+---------+------------+-----------------+----------------+----------------------------------+---------------+
| Empire  | FOX        | 24/5/2016 21:00 |             58 | …                                | 4.6%          |
| Gotham  | FOX        | 24/5/2016 21:58 |             32 | …                                | 3.1%          |
+---------+------------+-----------------+----------------+----------------------------------+---------------+

Based on the historical ratings data, I need to predict the future ratings, when all the parameters of the train are given, except the label of course.

My problem is:

A very strong feature for rating prediction is the carry over, or what was the rating of the previous program.

I want to train my model with the feature of the carry over, but I’m not sure how I should add it?
Should I train the model with the real carry-over? (the actual rating of the previous program)? In the test set the carry-over would be just an approximation to the real carry-over (it will be the prediction, not the actual rating, as oppose to the training data – because I can’t know in advance what would be the rating of the previous program) , so the correlation of the carry over with the real ratings in the test set would be less significant then in the train set…
How should I tackle this problem?


Get this bounty!!!

#StackBounty: #algorithms #linear-algebra #matrices #sparse-matrices Finding the bandwidth of a band matrix

Bounty: 50

I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 times 6000$). In order to improve the efficiency of the algorithm, I am trying to exploit the sparsity of the matrix by finding its bandwidth, but I have to run through the matrix a lot of times to find it, and it is taking too long.

The main idea I am using to find the bandwidth is:

  • for each row, find the start(row) and end(row): these are the intervals in which the elements are different of $0$;

  • to find start(row): iterate from the beginning of the row until the element is not $0$;

  • to find end(row): iterate from the end of the row until the element is not $0$;

The problem is that I am running through many unnecessary $0$’s, but I can not figure out how to avoid this and guarantee a solid result. Thanks.


Get this bounty!!!

#StackBounty: #algorithms #permutations #algorithm-design Counting permutations whose elements are not exactly their index ± M

Bounty: 50

I was recently asked this problem in an algorithmic interview and failed to solve it.

Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) such that the absolute difference between any number in the permutation and its position in the permutation is not equal to M.

Example – If N=3 and M=1 then, 1 2 3 and 3 2 1 are valid permutations but 1 3 2 is invalid as the number 3 is at position 2 and their difference is = M.

I tried NxM Dynamic programming but failed to form a recurrence that doesn’t count repetitions.


Get this bounty!!!

#HackerEarth: #BattleOfBots 9: Taunt

Problem

Taunt is a two player board game which is played on a 10X4 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Orange ( First Player ) or Green ( Second Player ) being conventional. Each player has nine piece in total. The players move their pieces towards to his / her opponent’s area by moving their pieces strategically. Each piece has a different moving feature and is one of the 3 types of pieces.

Piece 1: It can move to horizontally or vertically adjacent cell, if the cell doesn’t contain a piece of same color.

enter image description here

Piece 2: It can move to horizontally adjacent cell or can move two steps forward, if the cell doesn’t contain a piece of same color (except the piece itself).

enter image description here

This type of piece can move to its own position if its in the second last row of the grid and going downward or if its in the second row of the grid and going upward.

enter image description here

Piece 3: It can move two step diagonally in the forward direction, if the cell doesn’t contain a piece of same color (except the piece itself).

enter image description here enter image description here

This type of piece can move to its own position if its in the second last row of the grid and going downward or if its in the second row of the grid and going upward.

enter image description here

Players take turns involving moves of pieces as mentioned above and can captures opponent’s piece by jumping on or over opponent’s pieces.

Note: Forward direction for first player is downward and for second player is upward.

If a piece (except piece 1) is moving downward and touches the last row, its direction will change i.e. now it will move upward. Similarly, once if a piece (except piece 1) is moving upward and touches the first row, its direction will change i.e. now it will move downward.

Rules:

  • Player can only move according to the moves mentioned above.
  • A player may not move an opponent’s piece.
  • A player can captures opponent’s piece by jumping on or over opponent pieces.

The game will end after 100 moves ( 50 moves for each player ) or when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 10X4 grid. The top left of the grid is [0,0] and the bottom right is [9,3].

Input:
The input will be a 10X4 matrix consisting only of 0,1or2. Next line will contain an integer denoting the total number of moves till the current state of the board. Next line contains an integer – 1 or 2 which is your player id.

In the given matrix, top-left is [0,0] and bottom-right is [9,3]. The y-coordinate increases from left to right, and x-coordinate increases from top to bottom.

A cell is represented by 3 integers.

First integer denotes the player id (1 or 2).
Second integer denotes the type of piece (1, 2 or 3).
Third integer denotes the direction of the piece (0 (upward) or 1 (downward)). When the piece is of first type, direction doesn’t matter as the piece is free to move to horizontally or vertically adjacent cell, if the cell doesn’t contain a piece of same color.

Empty cell is represented by 000.

Output:
In the first line print the coordinates of the cell separated by space, the piece you want to move.
In second line print the coordinates of the cell in which the piece will jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if the piece is able to jump to [1,1], but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

131 131 131 121
121 121 111 111
111 000 000 000
000 000 000 000
000 000 000 000
000 000 000 000
000 000 000 000
000 000 000 210
210 210 220 220
220 230 230 230

First Input
This is the input give to the first player at the start of the game.

131 131 131 121
121 121 111 111
111 000 000 000
000 000 000 000
000 000 000 000
000 000 000 000
000 000 000 000
000 000 000 210
210 210 220 220
220 230 230 230
0
1

 

SAMPLE INPUT
000 000 000 000
000 000 000 111
000 000 111 130
000 000 000 000
000 000 000 000
000 220 000 000
131 000 000 000
121 000 210 000
000 210 131 000
000 210 000 000
58
1
SAMPLE OUTPUT
8 2
8 0

Explanation

This is player 1’s turn, and the player will move the piece at [8,2] and will take two steps diagonally in downward direction and will be at [8,0]
After his/her move the state of game becomes:

000 000 000 000
000 000 000 111
000 000 111 130
000 000 000 000
000 000 000 000
000 220 000 000
131 000 000 000
121 000 210 000
130 210 000 000
000 000 000 000
59
2

Note: Direction of the piece is also changed from 1 to 0 as the piece was moving downward and touches the last row. This state will be fed as input to program of player 2.

Here is the code of the default bot.

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

Sample Game

#StackBounty: #algorithms #graphs #graph-theory #weighted-graphs #union-find Disjoint-set on probabilistic graphs

Bounty: 50

We have an undirected weighted Graph G where each edge has a score in (0, 1]. We want to emit a score in [0, 1] for each pair of vertices u and v which is a score of how likely they are in the same disjoint set.

If the only possible weights were discrete 0 and 1 – then this problem reduces to a simple union-find like algorithm. But, I am not sure what literature exists for probabilistic graphs.


Get this bounty!!!

#StackBounty: #algorithms #complexity-theory Class of Algorithms where finding output of algorithm can be aided by output of same algor…

Bounty: 100

Sorry for the confusing title, but I’m trying to find out if a certain algorithm or class of algorithms fits this description. Given an algorithm A, computing A(x) can be computionally easier if A(g) is known, where g is close to x, and it’s easier the closer g gets to x. So also, the amount of computation A has to do grows with respect to the size of the input.

You would also have to be able to calculate the output of A(x) given A(g), x-g, A(x-g). Does A exist for anything other than trivial artithemtic, and if so, is there an entire class of algorithms which A belongs to?


Get this bounty!!!