2 people like it.

Find largest mass in 2D array

This is a modification of the flood fill algorithm to find the largest contiguous block of items in a 2D array. Also includes a simple flood fill finder given a canvas and the target point

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 
165: 
166: 
167: 
168: 
169: 
170: 
171: 
172: 
173: 
174: 
175: 
176: 
177: 
178: 
179: 
180: 
181: 
182: 
183: 
184: 
185: 
186: 
187: 
188: 
189: 
190: 
191: 
192: 
193: 
194: 
195: 
196: 
197: 
198: 
199: 
200: 
201: 
202: 
203: 
204: 
205: 
206: 
207: 
208: 
209: 
210: 
211: 
212: 
213: 
214: 
215: 
216: 
217: 
218: 
219: 
220: 
221: 
222: 
223: 
224: 
225: 
226: 
227: 
228: 
229: 
230: 
231: 
232: 
233: 
234: 
235: 
236: 
237: 
238: 
239: 
240: 
241: 
242: 
243: 
244: 
open System

type Board<'T> = 'T[,]

type X = int

type Y = int

type Position = X * Y

type PositionList = Position list 

type ProcessedPositions = PositionList

type ContiguousPoints = PositionList

type MassFinder = ContiguousPoints * ProcessedPositions

type Earth = 
    | Land
    | Water

let ViewType e = 
    match e with
        | Land -> "L"
        | Water -> "W"

let board = array2D [[Land;  Land;  Land;  Land;];
                     [Water; Land;  Land;  Water;];
                     [Land;  Water; Water; Water;];
                     [Water; Land;  Land;  Water;]]

let boardInt = array2D [[0;  0;  0;  1;];
                        [1; 0;  0;  1;];
                        [0;  1; 1; 1;];
                        [1; 0;  0;  1;]]
(* 
    Helper methods to move the position around
*)
                                          
let moveRight position = 
    let (x,y) = position
    (x + 1, y)

let moveLeft position = 
    let (x,y) = position
    (x - 1, y)

let moveUp position = 
    let (x,y) = position
    (x, y + 1)

let moveDown position = 
    let (x,y) = position
    (x, y - 1)

(*
    Size helpers
*)

let xSize board = Array2D.length1 board

let ySize board = Array2D.length2 board

let offBoard position board = 
    let (x,y) = position
    x < 0 || y < 0 || x >= (xSize board) || y >= (ySize board)

(*
    Alias to push elements onto a list
*)

let markPosition position previousSpots = position::previousSpots

(*
    Determines if the position on the board equals the target
*)

let positionOnTarget position board target = 
    if offBoard position board then 
        false
    else
        let (x, y) = position
        (Array2D.get board x y) = target

(*
    Alias to find if we already processed a position
*)

let positionExists position list = 
    List.exists(fun pos -> pos = position) list

(* 
   Iterate over each element in a 2d array, passing the x and y
   coordinate and the board, to the supplied function
   which can return an item. The items are all cons together
   and the function returns a new list
*)

let forEachElement (applier:(X -> Y -> Board<'a> -> 'b)) (twoDimArray:Board<'a>) =
    let mutable items = [] 
    for x in 0..(xSize board)-1 do
        for y in 0..(ySize board)-1 do            
            items <- (applier x y twoDimArray)::items
    items

let elemAt board (x, y) = Array2D.get board x y

(*
    Looks for a specified contigoius block
    and keeps track of processed positions using a 
    reference cell of a list of positions (supplied by the caller)
*)

         

let findMassStartingAt (position:Position) (board:Board<'A>) (target:'A) (positionSeed:ProcessedPositions) : MassFinder = 
    let rec findMassStartingAt' position (currentMass:ContiguousPoints, processedList:ProcessedPositions) cont = 
            // if you move off the board return
        if offBoard position board then
            cont (currentMass, processedList)

        // if you already processed this position then don't do anything
        else if positionExists position processedList then
            cont (currentMass, processedList)
        else  
            
            // branch out left, up, right, and down and see what you can find
            let up = moveUp position
            let down = moveDown position
            let left = moveLeft position
            let right = moveRight position
            
            let found = positionOnTarget position board target

            let updatedProcess = position::processedList

            match found with 
                | true ->                    
                           let massState = (position::currentMass, updatedProcess)

                           findMassStartingAt' up  massState (fun foundMassUp -> 
                           findMassStartingAt' down foundMassUp (fun foundMassDown ->
                           findMassStartingAt' left foundMassDown (fun foundMassLeft ->
                           findMassStartingAt' right foundMassLeft cont))) 

                | false -> 
                    // if you didn't find anything return the masses that you 
                    // found prevoiusly
                    cont((currentMass, updatedProcess))

    findMassStartingAt' position ([], positionSeed) id

(*
    Finds all items of list2 that are not in list1
*)

let except list1 list2 = 
    let listContainsElement item = List.exists (fun i -> i = item) list1
    List.filter(fun item -> not (listContainsElement item)) list2

(*
    Find first non processed position
*)

let firstNonProcessedPosition processedList xCount yCount = 
    match processedList with
        | [] -> 
            Some((0, 0))
        | _ ->
            if List.length processedList = (xCount * yCount) then
                None 
            else

                // get an array representing (x, y) tuples of the entire board
                let totalPositions = [0..xCount] |> List.collect (fun x -> [0..yCount] |> List.map (fun y -> (x, y)))

                // set intersections from the total positions array and the entire board
                let intersections = Set.intersect (Set.ofList totalPositions) (Set.ofList processedList)
                                        |> List.ofSeq

                // exclude the intersections from the total list
                let excludes = except intersections totalPositions

                match excludes with 
                    | [] -> None
                    | _ -> Some(List.head excludes)

                        

(*
    Finds all contiguous blocks of the specified type
    and returns a list of lists (each list is the points for a specific
    block)
*)
    
let getContiguousBlocks board target = 
    
    let xCount = (xSize board) - 1
    let yCount = (ySize board) - 1

    let rec findBlocks' (blocks, processed:PositionList) = 
        
        let findMass x y board = findMassStartingAt (x, y) board target processed

        // find the first non processed block 
        // and try and find its contigoius area
        // if it isn't a valid area the block it returns will be
        // empty and we can exclude it
        match firstNonProcessedPosition processed xCount yCount with 
            | None -> blocks
            | Some (x, y) -> 
                let (block, processed) = findMass x y board


                findBlocks' ((match block with 
                                | [] -> blocks
                                | _ -> block::blocks), processed)
        
    findBlocks' ([],[])

(*
    Returns a list of points representing a contigious block 
    of the type that the point was at. 
*)

let floodFillArea (point:Position) (canvas:Board<'T>) =
    let (x, y) = point
    let itemAtPoint = Array2D.get canvas x y
    
    findMassStartingAt point canvas itemAtPoint [] |> fst


(* 
    Test functions to run it
*)


let masses = getContiguousBlocks board Land

let largestList = List.maxBy(List.length) masses


System.Console.WriteLine("Largest mass is " + (List.length largestList).ToString());
namespace System
type Board<'T> = 'T [,]

Full name: Script.Board<_>
type X = int

Full name: Script.X
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type Y = int

Full name: Script.Y
type Position = X * Y

Full name: Script.Position
type PositionList = Position list

Full name: Script.PositionList
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
type ProcessedPositions = PositionList

Full name: Script.ProcessedPositions
type ContiguousPoints = PositionList

Full name: Script.ContiguousPoints
type MassFinder = ContiguousPoints * ProcessedPositions

Full name: Script.MassFinder
type Earth =
  | Land
  | Water

Full name: Script.Earth
union case Earth.Land: Earth
union case Earth.Water: Earth
val ViewType : e:Earth -> string

Full name: Script.ViewType
val e : Earth
val board : Earth [,]

Full name: Script.board
val array2D : rows:seq<#seq<'T>> -> 'T [,]

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.array2D
val boardInt : int [,]

Full name: Script.boardInt
val moveRight : int * 'a -> int * 'a

Full name: Script.moveRight
val position : int * 'a
val x : int
val y : 'a
val moveLeft : int * 'a -> int * 'a

Full name: Script.moveLeft
val moveUp : 'a * int -> 'a * int

Full name: Script.moveUp
val position : 'a * int
val x : 'a
val y : int
val moveDown : 'a * int -> 'a * int

Full name: Script.moveDown
val xSize : board:'a [,] -> int

Full name: Script.xSize
val board : 'a [,]
module Array2D

from Microsoft.FSharp.Collections
val length1 : array:'T [,] -> int

Full name: Microsoft.FSharp.Collections.Array2D.length1
val ySize : board:'a [,] -> int

Full name: Script.ySize
val length2 : array:'T [,] -> int

Full name: Microsoft.FSharp.Collections.Array2D.length2
val offBoard : int * int -> board:'a [,] -> bool

Full name: Script.offBoard
val position : int * int
val markPosition : position:'a -> previousSpots:'a list -> 'a list

Full name: Script.markPosition
val position : 'a
val previousSpots : 'a list
val positionOnTarget : int * int -> board:'a [,] -> target:'a -> bool (requires equality)

Full name: Script.positionOnTarget
val board : 'a [,] (requires equality)
val target : 'a (requires equality)
val get : array:'T [,] -> index1:int -> index2:int -> 'T

Full name: Microsoft.FSharp.Collections.Array2D.get
val positionExists : position:'a -> list:'a list -> bool (requires equality)

Full name: Script.positionExists
val position : 'a (requires equality)
Multiple items
val list : 'a list (requires equality)

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val exists : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.exists
val pos : 'a (requires equality)
val forEachElement : applier:(X -> Y -> Board<'a> -> 'b) -> twoDimArray:Board<'a> -> 'b list

Full name: Script.forEachElement
val applier : (X -> Y -> Board<'a> -> 'b)
val twoDimArray : Board<'a>
val mutable items : 'b list
val x : int32
val y : int32
val elemAt : board:'a [,] -> x:int * y:int -> 'a

Full name: Script.elemAt
val findMassStartingAt : X * Y -> board:Board<'A> -> target:'A -> positionSeed:ProcessedPositions -> MassFinder (requires equality)

Full name: Script.findMassStartingAt
val position : Position
val board : Board<'A> (requires equality)
val target : 'A (requires equality)
val positionSeed : ProcessedPositions
val findMassStartingAt' : (int * int -> ContiguousPoints * ProcessedPositions -> (ContiguousPoints * ProcessedPositions -> 'a) -> 'a)
val currentMass : ContiguousPoints
val processedList : ProcessedPositions
val cont : (ContiguousPoints * ProcessedPositions -> 'a)
val up : int * int
val down : int * int
val left : int * int
val right : int * int
val found : bool
val updatedProcess : (int * int) list
val massState : (int * int) list * (int * int) list
val foundMassUp : ContiguousPoints * ProcessedPositions
val foundMassDown : ContiguousPoints * ProcessedPositions
val foundMassLeft : ContiguousPoints * ProcessedPositions
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
val except : list1:'a list -> list2:'a list -> 'a list (requires equality)

Full name: Script.except
val list1 : 'a list (requires equality)
val list2 : 'a list (requires equality)
val listContainsElement : ('a -> bool) (requires equality)
val item : 'a (requires equality)
val i : 'a (requires equality)
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val firstNonProcessedPosition : processedList:(int * int) list -> xCount:int -> yCount:int -> (int * int) option

Full name: Script.firstNonProcessedPosition
val processedList : (int * int) list
val xCount : int
val yCount : int
union case Option.Some: Value: 'T -> Option<'T>
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
union case Option.None: Option<'T>
val totalPositions : (int * int) list
val collect : mapping:('T -> 'U list) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.collect
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val intersections : (int * int) list
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool
  ...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
val intersect : set1:Set<'T> -> set2:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.intersect
val ofList : elements:'T list -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofList
val ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
val excludes : (int * int) list
val head : list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.head
val getContiguousBlocks : board:'a [,] -> target:'a -> ContiguousPoints list (requires equality)

Full name: Script.getContiguousBlocks
val findBlocks' : (ContiguousPoints list * PositionList -> ContiguousPoints list)
val blocks : ContiguousPoints list
val processed : PositionList
val findMass : (X -> Y -> Board<'a> -> MassFinder) (requires equality)
val x : X
val y : Y
val board : Board<'a> (requires equality)
val block : ContiguousPoints
val processed : ProcessedPositions
val floodFillArea : X * Y -> canvas:Board<'T> -> ContiguousPoints (requires equality)

Full name: Script.floodFillArea
val point : Position
val canvas : Board<'T> (requires equality)
val itemAtPoint : 'T (requires equality)
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val masses : ContiguousPoints list

Full name: Script.masses
val largestList : Position list

Full name: Script.largestList
val maxBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.maxBy
type Console =
  static member BackgroundColor : ConsoleColor with get, set
  static member Beep : unit -> unit + 1 overload
  static member BufferHeight : int with get, set
  static member BufferWidth : int with get, set
  static member CapsLock : bool
  static member Clear : unit -> unit
  static member CursorLeft : int with get, set
  static member CursorSize : int with get, set
  static member CursorTop : int with get, set
  static member CursorVisible : bool with get, set
  ...

Full name: System.Console
Console.WriteLine() : unit
   (+0 other overloads)
Console.WriteLine(value: string) : unit
   (+0 other overloads)
Console.WriteLine(value: obj) : unit
   (+0 other overloads)
Console.WriteLine(value: uint64) : unit
   (+0 other overloads)
Console.WriteLine(value: int64) : unit
   (+0 other overloads)
Console.WriteLine(value: uint32) : unit
   (+0 other overloads)
Console.WriteLine(value: int) : unit
   (+0 other overloads)
Console.WriteLine(value: float32) : unit
   (+0 other overloads)
Console.WriteLine(value: float) : unit
   (+0 other overloads)
Console.WriteLine(value: decimal) : unit
   (+0 other overloads)

More information

Link:http://fssnip.net/ik
Posted:11 years ago
Author:devshorts
Tags: flood fill , algorithms