C#•2y ago

❔ Dynamic programming

Hello, I have a task, where I need to find the least keystrokes required to print a word. I have a table sized X*Y filled with letters that can repeat and I have a string s that can contain letters which are not in the table and should be skipped. We cannot move diagonally in the table. We always start at the left top corner. How do I solve this using dynamic programming? I have created a Dict where each letter gets List of positions it is in the table. But then I don't know how to look ahead. Let's say we have table:

ABC  
BFE  
CDF

ABC  
BFE  
CDF

and string = ABCDEFA Then when choosing F from E, how do I choose the middle one because it is closer to the next character (A) and not the right lower F

6 Replies

Connor•2y ago

First of all, nothing about this requires you to use a dynamic object if that’s what your asking I don’t like you’re use of a Dict, it’s should really be a List<Row> or youre own table class, but anyways, I’ll write some example code.

var rows = new List<string>() { “ABC”, “BFE”, “CDF” };

char e = rows[1][2];
char f = rows[1][1];

// The first indexer gets the string in the row number, the second indexer gets the char in the column number

var rows = new List<string>() { “ABC”, “BFE”, “CDF” };

char e = rows[1][2];
char f = rows[1][1];

// The first indexer gets the string in the row number, the second indexer gets the char in the column number

Cattywampus•2y ago

proly try to reword it better it's a bit confusing imho

popcornOP•2y ago

No I am not talking about dynamic object. I am talking about dynamic programming (https://en.wikipedia.org/wiki/Dynamic_programming) I have a matrix that is x*y (we can represent that as char[,]) and a string text. Now I have to find the least keystrokes that are required to visit each letter in the text. You can imagine a TV remote when you are filling some text. You can also move through the grid. We start in the left upper corner. So I need some function

static int FindLeastKeyStrokes(char[,] grid, string text) {}

static int FindLeastKeyStrokes(char[,] grid, string text) {}

It should be similar to Travelling Salesman problem, that is why the dynamic programming. In the example above it would be:

ABC  
BFE  
CDF

string text = ABCDEFA

enter
down
enter
down
enter
right
enter
up
right
enter
left
enter
up
left
enter

= 15 keystrokes

ABC  
BFE  
CDF

string text = ABCDEFA

enter
down
enter
down
enter
right
enter
up
right
enter
left
enter
up
left
enter

= 15 keystrokes

I only need the result (15) I don't need the actual path.

canton7•2y ago

So. I think your only decision points are when you need to visit a letter which appears multiple times in the grid (there's no significant decision about how to get to a particular point on the grid some another, as the optimal path is easy to find). And your only state is where you are on the grid, and where you are in the string. Pondering it a bit, if you just base everything on letters and not coordinates, I'm not sure this problem follows the principle of optimality, and therefore I'm not sure that dynamic programming can solve it? E.g. with THE (1D) grid: BACDBE The optimal path from A to B has cost 1, but the optimal path from A to B to E requires taking a non-optimal route from A to B. So we can't do recursion or memoization based just on the letters That said I'm struggling to think how you could sensibly do this with dynamic programming at all... As in, what the subproblems look like. The only subproblem definition I can think of is "from coordinates x to coordinates y via letters [...]"

i love cat(mull-rom splines)•2y ago

not sure how dp can be used too it's just distance to the next letter for all letters since you have to print them in a sequence

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ Dynamic programming