Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5607

Re: Detecting four sided figures

Show all headers | View raw

Chad <cdalten@gmail.com> writes:

> A description of the problem can be found here...
>
> http://www.reddit.com/r/dailyprogrammer/comments/3e5b0o/20150722_challenge_224_intermediate_detecting/

Fun problem.

> Ihe question is what is a possible approach I would take to solve this
> problem.  Counting the number of pluses doesn't work and I can't seem
> to establish a relationship between the lines and stars that form a
> box. I also looked at the solutions and I have zero clue on the
> algorithm or algorithms they used to solve this problem. Ideas?

The brute-force method would simply to be search for them all.  Read the
data into an array of characters and, as you do that, record the (x, y)
index of every +.  Then:

  for each such (x1, y1)
     for each (x2, y2)
        if     x2 > x1
           and y2 > y1
           and there is a + at (x2, y1) and at (x1, y2)
           and the lines from (x1, y1) to (x2, y1)
                              (x1, y2) to (x2, y2)
                              (x1, y1) to (x1, y2)
                              (x2, y1) to (x2, y2) all have no spaces
              add one to the count

You should probably sort the corners from top to bottom and from from
left to right to make the loops more efficient.  You could also note
which +s have lines between them as the data are read in.  That may only
pay off for large diagrams.

-- 
Ben.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Detecting four sided figures Chad <cdalten@gmail.com> - 2015-08-07 14:37 -0700
  Re: Detecting four sided figures Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-08 01:25 +0100
  Re: Detecting four sided figures Kaz Kylheku <kaz@kylheku.com> - 2015-08-08 01:05 +0000

csiph-web