C
C#•2y ago
Spekulant

❔ forloops upon forloops

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int m = int.Parse(Console.ReadLine());
        List<char> gridContents = Console.ReadLine().Take(n*m).ToList();
        List<char> word = Console.ReadLine().ToList();
        List<Tuple<int, int>> coordList = new List<Tuple<int, int>>();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                coordList.Add(new Tuple<int, int>(i,j));
            }
        }
        findMinKeyStrokes(gridContents,coordList,word);
        
    }
    
    static void findMinKeyStrokes(List<char> gridContents,List<Tuple<int,int>> coordList,List<char> word)
    { 
        List<int> indexPointers = new List<int>() {0};
        int numberKeystrokes = 0;

        foreach (char letter in word)
        {
            if (gridContents.Contains(letter))
            {
                numberKeystrokes += 1;
                int minimalDis = int.MaxValue;
                List<int> indexes = gridContents.Select((c, i) => letter == gridContents[i] ? i : -1)
                    .Where(i => i >= 0)
                    .ToList();

                foreach (int indexPointer in indexPointers)
                {
                    foreach (int index in indexes)
                    {
                        //calculating distance
                        int dist = Math.Abs(coordList[index].Item1 - coordList[indexPointer].Item1) +
                                   Math.Abs(coordList[index].Item2 - coordList[indexPointer].Item2);
                        if (dist < minimalDis)
                        {
                            indexPointers.Clear();
                            minimalDis = dist;
                            indexPointers.Add(index);
                        }
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int m = int.Parse(Console.ReadLine());
        List<char> gridContents = Console.ReadLine().Take(n*m).ToList();
        List<char> word = Console.ReadLine().ToList();
        List<Tuple<int, int>> coordList = new List<Tuple<int, int>>();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                coordList.Add(new Tuple<int, int>(i,j));
            }
        }
        findMinKeyStrokes(gridContents,coordList,word);
        
    }
    
    static void findMinKeyStrokes(List<char> gridContents,List<Tuple<int,int>> coordList,List<char> word)
    { 
        List<int> indexPointers = new List<int>() {0};
        int numberKeystrokes = 0;

        foreach (char letter in word)
        {
            if (gridContents.Contains(letter))
            {
                numberKeystrokes += 1;
                int minimalDis = int.MaxValue;
                List<int> indexes = gridContents.Select((c, i) => letter == gridContents[i] ? i : -1)
                    .Where(i => i >= 0)
                    .ToList();

                foreach (int indexPointer in indexPointers)
                {
                    foreach (int index in indexes)
                    {
                        //calculating distance
                        int dist = Math.Abs(coordList[index].Item1 - coordList[indexPointer].Item1) +
                                   Math.Abs(coordList[index].Item2 - coordList[indexPointer].Item2);
                        if (dist < minimalDis)
                        {
                            indexPointers.Clear();
                            minimalDis = dist;
                            indexPointers.Add(index);
                        }
62 Replies
Spekulant
SpekulantOP•2y ago
                        if (dist == minimalDis)
                        {
                            indexPointers.Add(index);
                        }
                    }

                    numberKeystrokes += minimalDis;
                }
            }
            else
            {
                continue;
            }
        }
        Console.Write(numberKeystrokes);
    }
}
                        if (dist == minimalDis)
                        {
                            indexPointers.Add(index);
                        }
                    }

                    numberKeystrokes += minimalDis;
                }
            }
            else
            {
                continue;
            }
        }
        Console.Write(numberKeystrokes);
    }
}
Angius
Angius•2y ago
73 Or 45
Spekulant
SpekulantOP•2y ago
again?
Angius
Angius•2y ago
Idk, could be 37 It's not easy to provide an answer without a question
Spekulant
SpekulantOP•2y ago
oh my bad would it be passivle to go VC?
Angius
Angius•2y ago
Not right now, no
Spekulant
SpekulantOP•2y ago
after? ok so
Angius
Angius•2y ago
In the unspecified future, maybe
Spekulant
SpekulantOP•2y ago
you are given width and height and a table of letters
example:
3
3
ABCBFECDF  
ABCDEFA

so we should process it as we are given a table that looks like this

ABC
BFE
CDF

after that we just want to calculate how many key strokes do we have to use to for example write BEEF.
you are given width and height and a table of letters
example:
3
3
ABCBFECDF  
ABCDEFA

so we should process it as we are given a table that looks like this

ABC
BFE
CDF

after that we just want to calculate how many key strokes do we have to use to for example write BEEF.
im trying to find the minimum of key strokes when you can only use left right up down and enter i had it working but 
ABC
BFE
CDF

if you have this table and you want to type ABCDEFA as you can see in my code the distance from A to B is the same 1 but one route is better then the other so im trying to fix that so the code goes both ways and finds the better one
ABC
BFE
CDF

if you have this table and you want to type ABCDEFA as you can see in my code the distance from A to B is the same 1 but one route is better then the other so im trying to fix that so the code goes both ways and finds the better one
is the problem clear?
Doombox
Doombox•2y ago
Have you implemented a pathfinder for this? A* is quite simple to implement and essentially solves this problem
Spekulant
SpekulantOP•2y ago
you mean DFS or BFS i havent used A* in my life so nope
Doombox
Doombox•2y ago
It's basically like Dijkstra's but with a heuristic it's actually quite simple to implement, and there are tons of implementations available online if you want something to reference then you can just ask it to generate paths for you from wherever you are to every index of whatever letter you're looking for, and pick the shortest one obviously if you wanted to minimise the total number of keystrokes for the entire operation you're approaching a travelling salesman problem but with something this small you could bruteforce it
Spekulant
SpekulantOP•2y ago
bruteforce it with A* you mean
Doombox
Doombox•2y ago
yep but even with multithreading, it's going to get quite expensive quite fast when size/string length increase
Spekulant
SpekulantOP•2y ago
where can i paste my whole code
Doombox
Doombox•2y ago
$paste
MODiX
MODiX•2y ago
If your code is too long, you can post to https://paste.mod.gg/ and copy the link into chat for others to see your shared code!
Spekulant
SpekulantOP•2y ago
https://paste.mod.gg/uonabmvvdhnc/0
BlazeBin - uonabmvvdhnc
A tool for sharing your source code with the world!
Doombox
Doombox•2y ago
my entire A* implementation for my unity project I'm working on at the moment, including a bunch of debug garbage and tons of helpers is ~300 lines the actual code for building and solving the graph is ~100 max
Spekulant
SpekulantOP•2y ago
so its working for 2 test cases but other 4 its
Spekulant
SpekulantOP•2y ago
crashing because of execution time
Doombox
Doombox•2y ago
you could almost certainly use an array here to hold the information also you don't need Tuple<int,int> you can just do (int, int) no need for new Tuple... then, just (1, 10) those won't help your execution time though ah you're just calculating manhattan distance, that's entirely reasonable as a solution for this shouldn't really be that slow then...
Spekulant
SpekulantOP•2y ago
well dont know
Doombox
Doombox•2y ago
implementing a solution myself as we speak, curious
Spekulant
SpekulantOP•2y ago
with A* you mean
Doombox
Doombox•2y ago
nah no need for it in this case, manhattan distance is fine
Spekulant
SpekulantOP•2y ago
so how would you do it will you show me then
Doombox
Doombox•2y ago
private static void Main()
{
    var n = 3;
    var m = 3;
    var input = "ABCBFECDF".ToArray();
    var word = "BEEF";
    var dist = CalculateMinDistance(input, n, m, word);
    Console.WriteLine(dist);
}

private int CalculateMinDistance(char[] input, int width, int height, string word)
{
    List<(char letter, int index)> map = input.Select((x, i) => (x, i)).ToList(); // map the letters to their index in the array
    var result = 0; // total keystrokes
    var currIndex = Array.IndexOf(input, word[0]); // set the index to the first letter
    for (var i = 1; i < word.Length; i++) // loop through the word
    {
        var letter = word[i]; // the letter in the word we're looking for
        if (!input.Any(x => x == letter)) continue; // letter isn't in the array so just continue to the next one
        var index = currIndex; // local variable capturing
        var indexes = map.Where(x => x.letter == letter) // All letter/index pairings where the letter is what we're looking for
            // This is the secret sauce...
            // Transform the collection to pair the letter/index combo with their manhattan distance 
            // from the index of the letter we're currently on (division/modulo gives us their location in 2d space)
            .Select(x => (x, Math.Abs(index / width - x.index / width) + Math.Abs(index % height - x.index % height)))
            // Pick the first element with the lowest manhattan distance
            .MinBy(x => x.Item2);
        currIndex = indexes.x.index; // set the current position in the array
        result += indexes.Item2; // add the manhattan distance keystrokes
    }
    return result;
}
private static void Main()
{
    var n = 3;
    var m = 3;
    var input = "ABCBFECDF".ToArray();
    var word = "BEEF";
    var dist = CalculateMinDistance(input, n, m, word);
    Console.WriteLine(dist);
}

private int CalculateMinDistance(char[] input, int width, int height, string word)
{
    List<(char letter, int index)> map = input.Select((x, i) => (x, i)).ToList(); // map the letters to their index in the array
    var result = 0; // total keystrokes
    var currIndex = Array.IndexOf(input, word[0]); // set the index to the first letter
    for (var i = 1; i < word.Length; i++) // loop through the word
    {
        var letter = word[i]; // the letter in the word we're looking for
        if (!input.Any(x => x == letter)) continue; // letter isn't in the array so just continue to the next one
        var index = currIndex; // local variable capturing
        var indexes = map.Where(x => x.letter == letter) // All letter/index pairings where the letter is what we're looking for
            // This is the secret sauce...
            // Transform the collection to pair the letter/index combo with their manhattan distance 
            // from the index of the letter we're currently on (division/modulo gives us their location in 2d space)
            .Select(x => (x, Math.Abs(index / width - x.index / width) + Math.Abs(index % height - x.index % height)))
            // Pick the first element with the lowest manhattan distance
            .MinBy(x => x.Item2);
        currIndex = indexes.x.index; // set the current position in the array
        result += indexes.Item2; // add the manhattan distance keystrokes
    }
    return result;
}
I think I'm in the right area should really add some comments pepelaff
Spekulant
SpekulantOP•2y ago
@Task.WhenAll wait if the letter is not in the grid we just omit it
Doombox
Doombox•2y ago
oh, well then you can just add a continue; clause in the for loop in that case I'll add it now actually
Spekulant
SpekulantOP•2y ago
wait if i want to test it i need to make it general
Doombox
Doombox•2y ago
there just modified it slightly to skip letters that aren't in the array
Spekulant
SpekulantOP•2y ago
i mean i need to make it general for the n m word we finding and the grid will look at it give me a sec
Doombox
Doombox•2y ago
no worries, was a fun little problem to solve, a good distraction from what I'm actually working on shame I have no test cases locally to try it out
Spekulant
SpekulantOP•2y ago
i will rewrite your code and test it but need to make it general so it can take input @Task.WhenAll im sorry but how is your program working when i paste it into my ide its not working
Doombox
Doombox•2y ago
what .NET version are you on?
Spekulant
SpekulantOP•2y ago
dont know where to check
Spekulant
SpekulantOP•2y ago
Doombox
Doombox•2y ago
oh, that's my bad you should make CalculateMinDistance static didn't think about that
Spekulant
SpekulantOP•2y ago
even tho 3 is not the right ans
Doombox
Doombox•2y ago
is it not? B -> E is 2 steps, E -> E is 0 steps, E -> F is 1 step 3 steps
Spekulant
SpekulantOP•2y ago
ABC
BFE
CDF

after that we just want to calculate how many key strokes do we have to use to for example write BEEF.

we start at A
so we go
right
enter
down
right
enter
enter
down
enter
ABC
BFE
CDF

after that we just want to calculate how many key strokes do we have to use to for example write BEEF.

we start at A
so we go
right
enter
down
right
enter
enter
down
enter
8
Doombox
Doombox•2y ago
ah, fair enough, I can adjust that slightly
Spekulant
SpekulantOP•2y ago
okey we can jsut do result +=1 if letter in grid
Doombox
Doombox•2y ago
https://sharplab.io/#v2:C4LgTgrgdgNAJiA1AHwAICYCMBYAUKgBgAJVMA6AGQEsoBHAbj0JMwBZHcmBmE9IgESoBnYAEMoAYwCmABTAB7AEYAbKQFsAyvOUA3KWDwBvPEVO90Js8dxnbRHaLBEoRALxEuHO2YdO1bjy9ve0ciGgAHCGAAgCIAQQAhAGEEgDEAUST+VJiyABV5OLAwUQBPAAoASiDvXyIAd3kwOFiE9PScmrs6uGFo9yTRZQkIZVFgKQBZGkERcWlyiKiYZxW1Fcbm6stvUgBOct6RbZszAF88HaJwsCoHCZYANjCoaMHh0fGpmb75qXKJAALRwAbQAui9IsAVjRovUqHBgICYa8iICpFQAOaA6EsYibOCVK7WYJhABmRHKBLIcSgFQAHm4AHyQqI05TKcqlZlERkAQncpUqwpIAHYiABaTD0IgAellDSaLTg8ikQigAHJolJ6X0XkQkVIiI4SqUyFdbNQRAAeAHApyqYATMAo6I0OA6yostSicIBJbAMgaKSqCTAcrlekwyo8yPRyr5eRW8MnUl1MBq0b9IgELq2OojYoASSgHsZ7lzFrMZKalLqVACubCRGtiualCkUExSJlVEQiCJp28JNJPlCjudAQJIKoYLzwXrpZ1AULYBLZfntVC7p1aoCPvCZAA6uiM5GefSyBP9G53NewIPR8EgyGpGHz64WXGiJNxoCaYoQiLEujIKvCiKApKvJkDuoENAiSIxogP5/gBQGwUQACkaIYti0QStBGHYeiWI4sKj5PnYZDTFACQMheZBFhMajoKmlGruuy7uLBapkJesGbnYGZCFmRCINxIG8Ux6h8Mh0pygqohwC08hQEaNZOIaRAxJ2zoxKywBVqYFxDnYqDisJWZdCZZxAA== man I hate sharplab pepetense yeah there it is running with 8 as the result
Spekulant
SpekulantOP•2y ago
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{

    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var m = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Take(n * m).ToArray();
        var word = Console.ReadLine();
        var dist = CalculateMinDistance(input, n, m, word);
        Console.WriteLine(dist);
    }

    private static int CalculateMinDistance(char[] input, int width, int height, string word)
    {
        List<(char letter, int index)> map = input.Select((x, i) => (x, i)).ToList(); // map the letters to their index in the array
        var result = 0; // total keystrokes
        var currIndex = Array.IndexOf(input, word[0]); // set the index to the first letter
        for (var i = 1; i < word.Length; i++) // loop through the word
        {
            var letter = word[i]; // the letter in the word we're looking for
            if (!input.Any(x => x == letter)) continue; // letter isn't in the array so just continue to the next one
            var index = currIndex; // local variable capturing
            var indexes = map.Where(x => x.letter == letter) // All letter/index pairings where the letter is what we're looking for
                // This is the secret sauce...
                // Transform the collection to pair the letter/index combo with their manhattan distance 
                // from the index of the letter we're currently on (division/modulo gives us their location in 2d space)
                .Select(x => (x, Math.Abs(index / width - x.index / width) + Math.Abs(index % height - x.index % height)))
                // Pick the first element with the lowest manhattan distance
                .MinBy(x => x.Item2);
            currIndex = indexes.x.index; // set the current position in the array
            result += indexes.Item2; // add the manhattan distance keystrokes
        }
        return result;
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{

    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var m = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Take(n * m).ToArray();
        var word = Console.ReadLine();
        var dist = CalculateMinDistance(input, n, m, word);
        Console.WriteLine(dist);
    }

    private static int CalculateMinDistance(char[] input, int width, int height, string word)
    {
        List<(char letter, int index)> map = input.Select((x, i) => (x, i)).ToList(); // map the letters to their index in the array
        var result = 0; // total keystrokes
        var currIndex = Array.IndexOf(input, word[0]); // set the index to the first letter
        for (var i = 1; i < word.Length; i++) // loop through the word
        {
            var letter = word[i]; // the letter in the word we're looking for
            if (!input.Any(x => x == letter)) continue; // letter isn't in the array so just continue to the next one
            var index = currIndex; // local variable capturing
            var indexes = map.Where(x => x.letter == letter) // All letter/index pairings where the letter is what we're looking for
                // This is the secret sauce...
                // Transform the collection to pair the letter/index combo with their manhattan distance 
                // from the index of the letter we're currently on (division/modulo gives us their location in 2d space)
                .Select(x => (x, Math.Abs(index / width - x.index / width) + Math.Abs(index % height - x.index % height)))
                // Pick the first element with the lowest manhattan distance
                .MinBy(x => x.Item2);
            currIndex = indexes.x.index; // set the current position in the array
            result += indexes.Item2; // add the manhattan distance keystrokes
        }
        return result;
    }
}
so its general for different inputs
Doombox
Doombox•2y ago
yeah, all you have to change is var currIndex = 0; so it starts at a in the top left and result += indexes.Item2 + 1; add one extra keystroke for the enter keystroke input that's about it oh and for(var i = 0; so it actually starts at the start of the word now instead of skipping ahead to the 2nd letter
Spekulant
SpekulantOP•2y ago
yep same problem occured as i was having
Doombox
Doombox•2y ago
even that isn't fast enough? pepetense even multithread this because each operation is reliant on the previous one
Spekulant
SpekulantOP•2y ago
look 
ABC
BFE
CDF

if you have this grid and want to write ABCDEFA
you can do it in 15 but the program does it in 17 because there are 2 routes
ABC
BFE
CDF

if you have this grid and want to write ABCDEFA
you can do it in 15 but the program does it in 17 because there are 2 routes
if it goes to the right its 17 if it goes downwards its 15 thats why i had list of pointers in my code so it checks different routs
Doombox
Doombox•2y ago
ah in that case you'll need to implement A* for the heuristics, in A* you calculate manhattan distance as part of each decision you make though even still that isn't guaranteed to work, this is nearly a travelling salesman problem because you need the shortest path overall, not just the shortest path to each letter
Spekulant
SpekulantOP•2y ago
ye but the grid will be max 256 char
Doombox
Doombox•2y ago
bruteforcing it with breadthfirst is going to be quite slow for big grids
Spekulant
SpekulantOP•2y ago
probably will have to implement the BFS
Doombox
Doombox•2y ago
BFS might be overly slow for big grids with big words though starting from the top left every time does limit the problem but the shortest route could theoretically be to go all the way to the bottom right first, there's no actual way to know without brute forcing every path, which is a bit crappy
Spekulant
SpekulantOP•2y ago
If i wanted that how would i do that even with the going up so i have pointer bottom @Task.WhenAll i found a code that does it
Spekulant
SpekulantOP•2y ago
https://paste.mod.gg/isvmvwzmvalv/0
BlazeBin - isvmvwzmvalv
A tool for sharing your source code with the world!
Doombox
Doombox•2y ago
interesting, not sure how that even works, currently adapting my pathfinder from my other project to see if I can get it to work with that curious thinking about it, probably not, it relies on manhattan distance as the heuristic and only looks at the next node, I'd have to implement another heuristic for the distance of the next node from the eventual goal too breadth first is a solid solution as long as it's fast enough for you
Spekulant
SpekulantOP•2y ago
well i tried implementing it but failed not the tests but i failed at implementation
Spekulant
SpekulantOP•2y ago
https://paste.mod.gg/ojucgnoasydo/0
BlazeBin - ojucgnoasydo
A tool for sharing your source code with the world!
Spekulant
SpekulantOP•2y ago
@Task.WhenAll just checking if you found somehting beucase i didnt come up with anything
Accord
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.
Want results from more Discord servers?
Add your server