Path: csiph.com!au2pb.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: Detecting four sided figures
Date: Sat, 08 Aug 2015 01:25:38 +0100
Organization: A noiseless patient Spider
Lines: 36
Message-ID: <871tfe62yl.fsf@bsb.me.uk>
References: <42f10925-3179-4468-9c6e-765ed0b3fc06@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="23872"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/DmzpX/xfdSc093wbS/bCwSaLn5hC4IBc="
Cancel-Lock: sha1:AVkmuZwPIacHrmGQPE5k0PMTqgI= sha1:Y/NFGS5Bl3Zs8XzHlhi+N+DPn4s=
X-BSB-Auth: 1.2bd0b5e8a2f7f00608a3.20150808012538BST.871tfe62yl.fsf@bsb.me.uk
Xref: csiph.com comp.programming: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.