1

edit: This is getting down voted but it's not been made clear what data structure I should be using instead of a list of coordinates. Unfortunately my data comes as a flat list and it needs to be distributed with in an outwards clockwise spiral. Then run a BFS on that to work out islands. I used coordinates which is what the C++ code tutorial seem to do (I have zero C++ experience though) but seems that was a bad route to take in Haskell

I'm trying to accumulate a list of touching land cells grouped by islands. Looking at the image bellow I'd expect 5 islands and each with the cells on that island. [[Cell]].

enter image description here

My input is currently a flat list of cells ordered in a clockwise spiral (red dotted line) and a number of the population of the cell. 0 making it sea and any >= 1 is the population.


data Cell = Cell
  { cellLoc :: (Int, Int)
  , cellpop :: Int -- 0 sea, >= 1 population of land
  }

startingCellList :: [Cell]
startingCellList = 
  [(Cell (1,0) 0)
  ,(Cell (1,-1) 0)
  ,(Cell (0,-1) 0)
  ,(Cell (-1,-1) 4)
  ]

The cellLoc gives me coordinates of cell in an X Y plane with (0,0) being at the centre of the grid. Am I right in thinking I can use the those coordinates to run my BSF?

Or do I need to rethink the use of coordinates to achieving my grid?

I've also found this great example but I'm not grasping it's use of vertexes and how or if I can relate it to using coordinates.

cmdv
  • 1,693
  • 3
  • 15
  • 23
  • I think you are looking for `group` function in `Data.List` – lsmor Aug 21 '19 at 11:00
  • A list of cells doesn't look like a suitable representation of a graph. – n. m. could be an AI Aug 21 '19 at 11:30
  • I do not really understand why you need the location here. It looks more like a grid is `[[CellType]]`, or better, a `Matrix CellType`. – Willem Van Onsem Aug 21 '19 at 11:33
  • Well this is a last part of a problem, I start with a long string which I convert into a spiral grid giving each cell a `(x,y)` coordinate https://stackoverflow.com/questions/57569623/coordinates-for-clockwise-outwards-spiral and now I have that list. Am I better converting it into a matrix first? – cmdv Aug 21 '19 at 11:39
  • @cmdv: well this in essence just a *flood fill task*: https://en.wikipedia.org/wiki/Flood_fill – Willem Van Onsem Aug 21 '19 at 11:51
  • @cmdv give a look to `ComonadSheet` library. Probably it fits your problem. https://github.com/kwf/ComonadSheet – lsmor Aug 21 '19 at 12:12
  • updated question with image and representation of incoming data as to why it's a list with coordinates. – cmdv Aug 21 '19 at 12:20
  • @cmdv just because your input is a list of coordinates that doesn't mean you have to represent it like that while working on it – Cubic Aug 21 '19 at 13:41
  • @Cubic I'm currently trying to convert it into a matrix to simplify it some what – cmdv Aug 21 '19 at 14:49

1 Answers1

0

You can convert the list [(Int,Int)] into a Data.Set (Int,Int). Then you can quickly compute adjacency for your graph in the following way. Using this you can build your graph algorithm that finds components (in the complement of the graph, whatever).

import Data.Set

-- compute all possible neighbours as difference vectors
let adjDiff = [(dx,dy) | dx <- [-1..1], dy <- [-1..1], (dx,dy) /= (0,0)]

-- given a cell, compute all potential neighbouring cells
let adjFull (x,y) = [(x',y') | (dx,dy) <- adjDiff, let x'=x+dx, let y'=y+dy]

-- given a set of valid cells and a cell, compute all valid neighbours of this cell
let adj validCells cell = [n | n <- adjFull cell, member ValidCells n]
ziggystar
  • 28,410
  • 9
  • 72
  • 124
  • Ah great thank you, I'll look into `Set` for sure :) What would be a reasonable way to keep additional data in a Set or did I miss understand the logic? as I'm trying to add up all members of an island to work out population of each island. (this is a pre determined number which is part of cell data) `Cell (-1,-1) 4 Land` the 4 being that cells population. :) – cmdv Aug 22 '19 at 10:23
  • actually I could just make it `Cell (-1,-1) 0` for sea and `Cell (-1,-1) 4` for land. Think that should simplify carrying around a type? – cmdv Aug 22 '19 at 10:25
  • @cmdv If you want to store different types of cells, I would advice using `Data.Map (Int,Int) Int`. – ziggystar Aug 22 '19 at 13:14
  • thanks that's great now just need to work out how to do a BFS to this structure :) – cmdv Aug 22 '19 at 17:09
  • My second to most upvoted answer contains some explanation and pseudo code for graph searches. You can plug the adj function in after some adjustments. – ziggystar Aug 22 '19 at 17:47