4
\$\begingroup\$

I have got such 2d jagged array (row is 1st dimension, column is 2nd dimension, bottom to up, left to right)

0   0   b   b   b   c
0   0   h   g   g   c
0   0   h   a   a   c
0   0   f   f   d   d
0   0   i   j   e   e
0   0   i   j   0   0

I would like to get a 2d jagged array summarize the positions of consecutive elements for each row, and ignore all 0 or single elements (assume that things like x x x y x x would not occur, so there won't be 2 blocks of same chars in a row)

the ideal outcome would be

{(b,3,5,2)}  // char, length, rowID, columnID
{(g,2,4,3)}
{(a,2,3,3)}
{(f,2,2,2), (d,2,2,4)}
{(e,2,1,4)}
{}

this is my code, i feel it is not that readable, so I appreciate any suggestion in C# or F# (Linq extension method is welcomed as well)

   Tuple<char, int, int, int>[][] GetHorizontalBricks()
    {
        List<Tuple<char, int, int, int>[]> ret = new List<Tuple<char, int, int, int>[]>();

        for (int rowID = 0; rowID < rowNum; rowID++)
        {
            List<Tuple<char, int, int, int>> rowBricks = new List<Tuple<char, int, int, int>>();
            var row = myBoard[rowID];

            int recentCount = 1;
            int columnID = 0;
            while (columnID < columnNum)
            {
                char recent = row[columnID];
                int next = columnID + 1;
                for (; next < columnNum; next++)
                {
                    if (row[next] == recent)
                    {
                        recentCount++;
                    }
                    else
                    {
                        break;
                    }
                }

                if (recentCount > 1 && recent != '0')
                {
                    rowBricks.Add(Tuple.Create(recent, recentCount, rowID, columnID));

                }
                columnID = next;
                recentCount = 1;
            }

            ret.Add(rowBricks.ToArray());
        }
        return ret.ToArray();
    }
\$\endgroup\$
2
\$\begingroup\$

First of all get rid of these tuples. After one week you will forget what each int represents. Define simple struct/class for your brick.

Second thing, small performance suggestion for big row count - explicit initial list size:

... = new List<Tuple<char, int, int, int>[]>(myBoard.Length);//assuming myBoard is an array

without it, list would be recreated and rewritten every 4 new elements.

Below is mine implementation with linq extensions. Probably it is not faster. I don't know if it is more readable, but at least line count is smaller :)

public struct Brick
{
    public char Symbol { get; set; }
    public int Length { get; set; }
    public int RowID { get; set; }
    public int ColumnID { get; set; }

    public override string ToString()
    {
        return string.Format("{0} {1} {2} {3}", Symbol, Length, RowID, ColumnID);
    }
}

public Brick[][] GetHorizontalBricks(char[][] board)
{
    return
        board
            .Reverse() //bottom up row order
            .Select((row,rowIndex) =>
                row
                    .Select((c,i) => new { c = c, i = i })
                    .GroupBy(symbol => symbol.c) //assumption that we will never see 2 groups of same nonzero character in single row
                    .Where(symbol => symbol.Key != 0 && symbol.Count() > 1)
                    .Select(brick =>
                        new Brick
                        {
                            Symbol = brick.Key,
                            RowID = rowIndex,
                            ColumnID = brick.First().i,
                            Length = brick.Count()
                        })
                    .ToArray()
            )
            .Reverse() //reverse again to show result in form like you provided
            .ToArray();
}

and Console app test:

static void Main(string[] args)
{
    char[][] board = new char[][]
    {
        new char[] { (char)0, (char)0, 'b' ,'b','b','c'},
        new char[] { (char)0, (char)0, 'h' ,'g','g','c'},
        new char[] { (char)0, (char)0, 'h' ,'a','a','c'},
        new char[] { (char)0, (char)0, 'f' ,'f','d','d'},
        new char[] { (char)0, (char)0, 'i' ,'j','e','e'},
        new char[] { (char)0, (char)0, 'i' ,'j',(char)0,(char)0}
    };

    foreach (var row in new Program().GetHorizontalBricks(board))
    {
        Console.WriteLine("Row:");
        foreach (var brick in row)
            Console.WriteLine(brick);
    }

    Console.ReadLine();
}
\$\endgroup\$
  • \$\begingroup\$ thank u, I didn't know that Linq select supports index as well \$\endgroup\$ – colinfang Oct 3 '12 at 20:37
  • \$\begingroup\$ Small warning. Watch out for monster linq queries. It looks nice to do all in one chain but it can be pretty nasty to debug. \$\endgroup\$ – Kuba Oct 3 '12 at 20:40
  • 1
    \$\begingroup\$ If you don't specify size of a List, it's not going to be “recreated every 4 elements”, that would have terrible performance. Instead, every time it gets full, it is recreated to twice the size it was previously. Specifying the size can help you a bit, but probably not noticeably. \$\endgroup\$ – svick Oct 4 '12 at 9:25
  • \$\begingroup\$ My mistake. It starts from 0, then 4, 8, 16, 32 and so on. stackoverflow.com/questions/1762817/default-capacity-of-list \$\endgroup\$ – Kuba Oct 4 '12 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.