Posted By

cb9 on 06/26/11


Tagged


Versions (?)

Find "Square" of 1s in a 2D Array of 1s and 0s.


 / Published in: C#
 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace C9Test
  7. {
  8. class Program
  9. {
  10. static void Main(string[] args)
  11. {
  12. int width = 6, length = 5;
  13. int[][] arr = new int[length][];
  14.  
  15. arr[0] = new int[] { 1, 1, 1, 0, 1, 1 };
  16. arr[1] = new int[] { 1, 1, 1, 1, 1, 1 };
  17. arr[2] = new int[] { 1, 1, 1, 1, 1, 1 };
  18. arr[3] = new int[] { 0, 0, 1, 1, 1, 1 };
  19. arr[4] = new int[] { 0, 0, 1, 1, 1, 1 };
  20.  
  21. /*
  22.   //After run 1
  23.   { 1, 1, 0, 0, 1, 0 }
  24.   { 1, 1, 1, 1, 1, 0 }
  25.   { 0, 0, 1, 1, 1, 0 }
  26.   { 0, 0, 1, 1, 1, 0 }
  27.   { 0, 0, 0, 0, 0, 0 }
  28.  
  29.   //After run 2
  30.   { 1, 0, 0, 0, 0, 0 }
  31.   { 0, 0, 1, 1, 0, 0 }
  32.   { 0, 0, 1, 1, 0, 0 }
  33.   { 0, 0, 0, 0, 0, 0 }
  34.   { 0, 0, 0, 0, 0, 0 }
  35.  
  36.   //After run 3
  37.   { 0, 0, 0, 0, 0, 0 }
  38.   { 0, 0, 1, 0, 0, 0 }
  39.   { 0, 0, 0, 0, 0, 0 }
  40.   { 0, 0, 0, 0, 0, 0 }
  41.   { 0, 0, 0, 0, 0, 0 }
  42.  
  43.   //After run 4
  44.   { 0, 0, 0, 0, 0, 0 }
  45.   { 0, 0, 0, 0, 0, 0 }
  46.   { 0, 0, 0, 0, 0, 0 }
  47.   { 0, 0, 0, 0, 0, 0 }
  48.   { 0, 0, 0, 0, 0, 0 }
  49.  
  50.   */
  51.  
  52. int size = 1;
  53. do
  54. {
  55. var newarr = SetMask(arr, width, size);
  56. var hasone = newarr.Count(y => y.Any(x => x == 1));
  57. if (hasone == 0)
  58. {
  59. break;
  60. }
  61. else
  62. {
  63. size++;
  64. arr = newarr;
  65. }
  66. }
  67. while (true);
  68.  
  69. if (size > 1)
  70. {
  71. var rowhasones = arr.Select((r, i) => new { Index = i, RowData = r })
  72. .Where(y => y.RowData.Any(x => x == 1))
  73. .Select(r => r.Index);
  74.  
  75. foreach (var rowindex in rowhasones)
  76. {
  77. for (int i = 0; i < width; i++)
  78. {
  79. if (arr[rowindex][i] == 1)
  80. {
  81. Console.WriteLine("{0:d}x{0:d} square @ ({1:d},{2:d})", size, rowindex, i);
  82. }
  83. }
  84. }
  85.  
  86. }
  87. }
  88.  
  89. static int[][] SetMask(int[][] arrSrc, int width, int offset)
  90. {
  91. var length = arrSrc.Length;
  92. var maxlencheck = length - offset;
  93. var arrRet = new int[length][];
  94. for (int i = 0; i < length; i++)
  95. {
  96. arrRet[i] = new int[width]; //default to zeroes
  97. }
  98.  
  99. //Project to anonymous type to get array index
  100. var rowhasones = arrSrc.Select((r, i) => new { Index = i, RowData = r })
  101. .Where((r, i) => i < maxlencheck && r.RowData.Any(x => x == 1))
  102. .Select(r => r.Index)
  103. .OrderBy(i => i);
  104.  
  105. foreach (var rowindex in rowhasones)
  106. {
  107. if (rowindex == maxlencheck)
  108. {
  109. //last row is all zeroes
  110. continue;
  111. }
  112.  
  113. var currow = arrSrc[rowindex];
  114. var nextrow = arrSrc[rowindex + 1];
  115. var maxcolcheck = width - offset;
  116.  
  117. for (int i = 0; i < maxcolcheck; i++)
  118. {
  119. if (currow[i] == 1 && currow[i + 1] == 1 && nextrow[i] == 1 && nextrow[i + 1] == 1)
  120. {
  121. arrRet[rowindex][i] = 1;
  122. }
  123. }
  124. }
  125. return arrRet;
  126. }
  127. }
  128. }

Report this snippet  

You need to login to post a comment.