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

Groups > comp.programming > #5605 > unrolled thread

Detecting four sided figures

Back to article view | Back to comp.programming

Contents

  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

#5605 — Detecting four sided figures

A description of the problem can be found here...

http://www.reddit.com/r/dailyprogrammer/comments/3e5b0o/20150722_challenge_224_intermediate_detecting/

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?

[toc] | [next] | [standalone]

#5607

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.

[toc] | [prev] | [next] | [standalone]

#5608

On 2015-08-07, Chad <cdalten@gmail.com> wrote:
> A description of the problem can be found here...
>
> http://www.reddit.com/r/dailyprogrammer/comments/3e5b0o/20150722_challenge_224_intermediate_detecting/
>
> 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?

A four-sided figure occurs when an angle configuration like the following ABC:

  A              B
  +--------+-----+
  |
  |
  +
  |
  +
  | C
  +

Has a completing corner, such as this D:

  A              B
  +--------+-----+
  |              |
  |              |
  +              |
  |              +
  +              |
  | C            |
  +--------------+ D

For every + character in the diagram, enumerate all the possible angle figures which
have that character as their upper-left corner. Test which of these angle figures
have a completing corner: each of those is a four-sided figure. Count these.

For instance, the above A has 2x3 possible angle figures, since it is flanked by
a horizontal edge with two + characters, and a vertical edge with three + characters.

Connectivity testing can be performed by simple walks: start a given character
and march horizontally or vertically while you see only dashes, pipes and
pluses.

If the coordinates of C are (cx, cy) and those of B are (bx, by), then those of
D are necessarily (bx, cy).  The job is to test whether C connects
horizontally to D (unbroken path of dashes and pluses from (cx, cy) to (bx,
cy)) and similarly for C to D.

Once you know that C connects to D, or verify that it doesn't, you can cache
this knowledge so as not to repeat these scans. An initial scan thorugh the
figure could find all horizontal and vertical lines, and associate together the
vertices which they connect.  Then the subsequent computation reduces to a
graph problem.

For every vertex, we can have a is singly linked list of vertices which lie on
the same horizontal segment to the right, and another list of vertices which
lie on the same vertical below. Every diagram reduces to a DAG and the right
kind of combinatorial traversal of this DAG finds the four-sided figures.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web