C#•16mo ago

❔ 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•16mo 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•16mo ago

73 Or 45

Spekulant•16mo ago

again?

Angius•16mo ago

Idk, could be 37 It's not easy to provide an answer without a question

Spekulant•16mo ago

oh my bad would it be passivle to go VC?

Angius•16mo ago

Not right now, no

Spekulant•16mo ago

after? ok so

Angius•16mo ago

In the unspecified future, maybe

Spekulant•16mo 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•16mo ago

Have you implemented a pathfinder for this? A* is quite simple to implement and essentially solves this problem

Spekulant•16mo ago

you mean DFS or BFS i havent used A* in my life so nope

Doombox•16mo 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•16mo ago

bruteforce it with A* you mean

Doombox•16mo ago

yep but even with multithreading, it's going to get quite expensive quite fast when size/string length increase

Spekulant•16mo ago

where can i paste my whole code

Doombox•16mo ago

$paste

MODiX•16mo 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•16mo ago

https://paste.mod.gg/uonabmvvdhnc/0

BlazeBin - uonabmvvdhnc

A tool for sharing your source code with the world!

Doombox•16mo 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•16mo ago

so its working for 2 test cases but other 4 its

Spekulant•16mo ago

crashing because of execution time

Doombox•16mo 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•16mo ago

well dont know

Doombox•16mo ago

implementing a solution myself as we speak, curious

Spekulant•16mo ago

with A* you mean

Doombox•16mo ago

nah no need for it in this case, manhattan distance is fine

Spekulant•16mo ago

so how would you do it will you show me then

Doombox•16mo 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•16mo ago

@Task.WhenAll wait if the letter is not in the grid we just omit it

Doombox•16mo 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•16mo ago

wait if i want to test it i need to make it general

Doombox•16mo ago

there just modified it slightly to skip letters that aren't in the array

Spekulant•16mo 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•16mo 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•16mo 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•16mo ago

what .NET version are you on?

Spekulant•16mo ago

dont know where to check

Spekulant•16mo ago

Doombox•16mo ago

oh, that's my bad you should make CalculateMinDistance static didn't think about that

Spekulant•16mo ago

even tho 3 is not the right ans

Doombox•16mo ago

is it not? B -> E is 2 steps, E -> E is 0 steps, E -> F is 1 step 3 steps

Spekulant•16mo 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

Doombox•16mo ago

ah, fair enough, I can adjust that slightly

Spekulant•16mo ago

okey we can jsut do result +=1 if letter in grid

Doombox•16mo ago

https://sharplab.io/#v2:C4LgTgrgdgNAJiA1AHwAICYCMBYAUKgBgAJVMA6AGQEsoBHAbj0JMwBZHcmBmE9IgESoBnYAEMoAYwCmABTAB7AEYAbKQFsAyvOUA3KWDwBvPEVO90Js8dxnbRHaLBEoRALxEuHO2YdO1bjy9ve0ciGgAHCGAAgCIAQQAhAGEEgDEAUST+VJiyABV5OLAwUQBPAAoASiDvXyIAd3kwOFiE9PScmrs6uGFo9yTRZQkIZVFgKQBZGkERcWlyiKiYZxW1Fcbm6stvUgBOct6RbZszAF88HaJwsCoHCZYANjCoaMHh0fGpmb75qXKJAALRwAbQAui9IsAVjRovUqHBgICYa8iICpFQAOaA6EsYibOCVK7WYJhABmRHKBLIcSgFQAHm4AHyQqI05TKcqlZlERkAQncpUqwpIAHYiABaTD0IgAellDSaLTg8ikQigAHJolJ6X0XkQkVIiI4SqUyFdbNQRAAeAHApyqYATMAo6I0OA6yostSicIBJbAMgaKSqCTAcrlekwyo8yPRyr5eRW8MnUl1MBq0b9IgELq2OojYoASSgHsZ7lzFrMZKalLqVACubCRGtiualCkUExSJlVEQiCJp28JNJPlCjudAQJIKoYLzwXrpZ1AULYBLZfntVC7p1aoCPvCZAA6uiM5GefSyBP9G53NewIPR8EgyGpGHz64WXGiJNxoCaYoQiLEujIKvCiKApKvJkDuoENAiSIxogP5/gBQGwUQACkaIYti0QStBGHYeiWI4sKj5PnYZDTFACQMheZBFhMajoKmlGruuy7uLBapkJesGbnYGZCFmRCINxIG8Ux6h8Mh0pygqohwC08hQEaNZOIaRAxJ2zoxKywBVqYFxDnYqDisJWZdCZZxAA== man I hate sharplab pepetense

yeah there it is running with 8 as the result

Spekulant•16mo 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•16mo 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•16mo ago

yep same problem occured as i was having

Doombox•16mo ago

even that isn't fast enough? pepetense

even multithread this because each operation is reliant on the previous one

Spekulant•16mo 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•16mo 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•16mo ago

ye but the grid will be max 256 char

Doombox•16mo ago

bruteforcing it with breadthfirst is going to be quite slow for big grids

Spekulant•16mo ago

probably will have to implement the BFS

Doombox•16mo 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•16mo 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•16mo ago

https://paste.mod.gg/isvmvwzmvalv/0

BlazeBin - isvmvwzmvalv

A tool for sharing your source code with the world!

Doombox•16mo 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•16mo ago

well i tried implementing it but failed not the tests but i failed at implementation

Spekulant•16mo ago

https://paste.mod.gg/ojucgnoasydo/0

BlazeBin - ojucgnoasydo

A tool for sharing your source code with the world!

Spekulant•16mo ago

@Task.WhenAll just checking if you found somehting beucase i didnt come up with anything

Accord•16mo 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

❔ forloops upon forloops