53
\$\begingroup\$

The video game Minecraft is all about placing and removing different types of blocks in the 3D integer lattice that makes up the virtual world. Each lattice point can contain exactly one block or be empty (an "air" block officially). In this challenge, we will only be concerned with one vertical 2D plane of the 3D world, and one type of block: obsidian.

When obsidian forms the outline of an empty rectangle in a vertical plane, a nether portal can be created. The empty rectangle may be any size from 2 units wide by 3 units high to 22 units wide by 22 units high. The corners of the rectangle do not need to be bordered in obsidian, just the sides.

For example, suppose X is obsidian and . is emptiness: (The numbers are just for identification purposes and are also empty.)

...................................
..XXXX....XXXX....XXXXXXXXX........
..X..X...X....X..X.........X..XXXX.
..X.1X...X.2..X..X...3...X.X..X....
..X..X...X....XXXX.........X..X.6X.
..XXXX....XXXX...XXXXXXXXXXX..X..X.
.............X.4.X....X.5.X...XXXX.
.............X...X....X...X........
..............XXX......XXX.........
...................................

This grid contains 3 valid portals:

  • Portal 1 is 2 by 3 units, totally empty, and bordered in obsidian. Therefore it's valid.
  • Portal 2 is 4 by 3, totally empty, and bordered in obsidian. Therefore it's valid.
  • Portal 3 isn't totally empty. Therefore it's invalid.
  • Portal 4 is 3 by 3, totally empty, and bordered in obsidian. Therefore it's valid.
  • Portal 5 is 3 by 2 units, which is too small. Therefore it's invalid.
  • Portal 6 is missing a part of the border. Therefore it's invalid.

Challenge

Write a program or function that takes in these string representations of grids of obsidian and emptiness, and prints or returns the number of valid nether portals present.

  • Input can be from stdin or file or function argument.
  • You may assume the input is always well formed - i.e. a perfectly rectangular grid of text, at least 1 character wide and tall, only containing X and .. You may optionally assume there is a trailing newline after the last row.

  • If desired, you may use any two distinct printable ASCII characters in place of X and ..

  • Obsidian may be on the borders of the grid. Anything beyond the borders is considered empty.

Example input - the output should be 4:

................................................................
...................................XXXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX....XXXXXXXXX........X.......................X....
..X..X...X....X..X.........X..XXXX.X.......................X....
..X..X...X....X..X.......X.X..X....X.......................X....
..X..X...X....XXXX.........X..X..X..XXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX...XXXXXXXXXXX..X..X.X......................X..XXX
.............X...X....X...X...XXXX.X......................X..X..
.............X...X....X...X........X......................X..X..
..............XXX......XXX........XXXXXXXXXXXXXXXXXXXXXXXX...X..
..................................XX.........................XXX

Scoring

The submission with the fewest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can I use another ASCII character in place of the newlines? \$\endgroup\$ – Zgarb Feb 8 '15 at 12:49
  • \$\begingroup\$ @Zgarb No, I still want the input to look like a grid. \$\endgroup\$ – Calvin's Hobbies Feb 8 '15 at 12:53
  • 4
    \$\begingroup\$ When did nether portals' size change from static 2x3 to the optional larger sizes? \$\endgroup\$ – Sparr Feb 8 '15 at 17:12
  • 5
    \$\begingroup\$ @Sparr SInce 1.7.2 (see the update history). I'm not sure if they can do this in the console editions. \$\endgroup\$ – Calvin's Hobbies Feb 8 '15 at 17:16
  • 4
    \$\begingroup\$ Definitely +1 because Minecraft. \$\endgroup\$ – Alex A. Feb 9 '15 at 18:10
24
\$\begingroup\$

Perl, 81 86

Using more than one regexp.

#!perl -p0
$_=map{/.
/;$n="@-"-++$.;/(?=X{$.}..{$n}(X\.{$.}X.{$n}){3,22}.X{$.})/gs}($_)x21

The regexp for a specific width of a portal is much simpler than a generic one: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m} where m is the width of the portal and n is total width - 1 - m. The regexp must be put in a zero width forward assertion (?=...) because the matches may overlap. Then I iterate 21 times over this regexp setting $n and $.. "@-" evaluates to start position of the last match (/.\n/) which happen to be total width - 1. $. is used as the other variable as it is initialized to 1 when used with -p0.

\$\endgroup\$
  • 2
    \$\begingroup\$ You can save a byte if you use a different character than . for empty cells (so you don't have to escape it). \$\endgroup\$ – Martin Ender Feb 9 '15 at 20:24
62
\$\begingroup\$

Regex (.NET flavour), 182 181 145 132 126 114 104 100 98 97 96 bytes

2D ASCII art pattern recognition? Sounds like a job for regex! (It doesn't.)

I know this is going to kick loose endless discussions again about whether regex submissions are valid programs or not, but I doubt this will beat APL or CJam anyway, so I don't see any harm. (That being said, they do pass our die-hard test for "What is a programming language?".)

This takes input as the string to be matched, and the result is the number of matches found. It uses _ in place of ., because I'd have to escape the latter. It also requires a trailing newline.

(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)

You can test it live at RegexHero or RegexStorm). The matches will be the top obsidian rows of the portals. If you can find a test case where it fails, please let me know!

What is this sorcery?

The following explanation assumes a basic understanding of .NET's balancing groups. The gist is that captures are stacks in .NET regex - every new capture for the same name is pushes onto the stack, but there's also syntax to pop captures from those stacks again, as well as syntax to pop captures from one stack and push captures onto another at the same time. For a more complete picture, you can have a look at my answer on Stack Overflow which should cover all the details.

The basic idea is to match a pattern like:

 X{n}..{m}
X_{n}X.{m} |
X_{n}X.{m} |  3 to 22 times
X_{n}X.{m} |
 X{n}..{m} 

Where n is between 2 and 22 (inclusive). The tricky thing is getting all the ns and all the ms to be the same. Since the actual characters won't be the same, we can't just use a backreference.

Note that the regex has to embedded newlines, which I'll write as \n in the following.

(                     # Open capturing group 1. This will contain the top of a portal, which
                      # I can reuse later to match the bottom (being of the same length).
  X                   # Match a single X.
  (X){1,21}           # Match 1 to 21 X's, and push each separately on the <2> stack. Let's
                      # Call the number of X's captured N-1 (so N is the inner width of the
                      # portal).
)                     # End of group 1. This now contains N X's.
(?=                   # Start a lookahead. The purpose of this lookahead is to capture a 
                      # string of N underscores in group 2, so I can easily use this to match 
                      # the inside rows of the portal later on. I can be sure that such a 
                      # string can always be found for a valid portal (since it cannot have 0 
                      # inner height).
  \D+                 # Skip past a bunch of non-digits - i.e. *any* of the vaild characters
                      # of the input (_, X, \n). This to make sure I search for my N 
                      # underscores anywhere in the remainder of the input.
  (                   # Open capturing group 3. This will contain a portal row.
    (?>               # This is an atomic group. Once the engine hass successfully matched the
                      # contents of this group, it will not go back into the group and try to
                      # backtrack other possible matches for the subpattern.
      (?<-2>_)+       # Match underscores while popping from the <2> stack. This will match as
                      # many underscores as possible (but not more than N-1).
    )                 # End of the atomic group. There are two possible reasons for the
                      # subpattern stopping to match: either the <2> stack is empty, and we've
                      # matched N-1 underscores; or we've run out of underscores, in which 
                      # case we don't know how many underscores we matched (which is not 
                      # good).
    _                 # We simply try to match one more underscore. This ensures that we 
                      # stopped because the <2> stack was empty and that group 3 will contain
                      # exactly N underscores.
  )                   # End of group 3.
)                     # End of the lookahead. We've got what we want in group 2 now, but the
                      # regex engine's "cursor" is still at the end of the portal's top.
(?=                   # Start another lookahead. This ensures that there's actually a valid
                      # portal beneath the top. In theory, this doesn't need to be a 
                      # lookahead - I could just match the entire portal (including the lines
                      # it covers). But matches cannot overlap, so if there were multiple
                      # portals next to each other, this wouldn't return all of them. By 
                      # putting the remainder of the check in a lookahead the actual matches
                      # won't overlap (because the top cannot be shared by two portals).
  .                   # Match either _ or X. This is the character above the portal side.

  (                   # This group (4) is where the real magic happens. It's purpose is to to
                      # count the length of the rest of the current line. Then find a portal
                      # row in the next line, and ensure that it's the same distance from the
                      # end of the line. Rinse and repeat. The tricky thing is that this is a
                      # single loop which matches both inner portal rows, as well as the 
                      # bottom, while making sure that the bottom pattern comes last.

    (?!\7)            # We didn't have a group 7 yet... group 7 is further down the pattern.
                      # It will capture an empty string once the bottom row has been matched.
                      # While the bottom row has not been matched, and nothing has been
                      # captured, the backreference will fail, so the negative lookahead will
                      # pass. But once we have found the bottom row, the backreference will
                      # always match (since it's just an empty string) and so the lookahead
                      # will fail. This means, we cannot repeat group 4 any more after the
                      # bottom has been matched.
    (.)*              # Match all characters until the end of the line, and push each onto
                      # stack <5>.
    \n                # Match a newline to go to the next line.
    .*                # Match as many characters as necessary to search for the next portal
                      # row. This conditions afterwards will ensure that this backtracks to
                      # the right position (if one exists).
    (                 # This group (6) will match either an inner portal row, or the bottom
                      # of the portal.
      X\3X            # Match X, then N underscores, then X - a valid inner portal row.
    |                 # OR
      ()              # Capture an empty string into group 7 to prevent matching further rows.
      \1.             # Use the captured top to match the bottom and another character.
    )
    (?=               # This lookahead makes sure that the row was found at the same 
                      # horizontal position as the top, by checking that the remaining line
                      # is the same length.
      (?<-5>.)*       # Match characters while popping from the <5> stack.
      (?(5)!)\n       # Make sure we've hit end of the line, *and* the <5> stack is empty.
    )
  ){4,23}             # Repeat this 4 to 23 times, to ensure an admissible portal height.
                      # Note that this is one more than the allowed inner height, to account
                      # for the bottom row.
  \7                  # Now in the above repetition there is nothing requiring that we have
                      # actually matched any bottom row - it just ensured we didn't continue
                      # if we had found one. This backreference takes care of that. If no
                      # bottom row was found, nothing was captured into group 7 and this
                      # backreference fails. Otherwise, this backreference contains an empty
                      # string which always matches.
)

C#, 185 bytes

Here is a full C# function, just to make this a valid entry. It's time I wrote a command-line "interpreter" for .NET regular expressions...

static int f(string p){return System.Text.RegularExpressions.Regex.Matches(p,@"(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)").Count;}
\$\endgroup\$
  • 5
    \$\begingroup\$ Hmm, not sure how I feel about a pure regex answer. Matching the tops isn't the same as printing the number. It would of course be fine to use regex in a program and print the number of matches. Still, as you say, it will probably be beaten, so I'm too concerned either. \$\endgroup\$ – Calvin's Hobbies Feb 8 '15 at 2:18
  • 1
    \$\begingroup\$ You can use ^ (or any unused character) for (?!). \$\endgroup\$ – jimmy23013 Feb 8 '15 at 11:02
  • \$\begingroup\$ @user23013 Oh, good point, thank you. \$\endgroup\$ – Martin Ender Feb 8 '15 at 11:05
  • \$\begingroup\$ 118 bytes. \$\endgroup\$ – jimmy23013 Feb 8 '15 at 12:11
  • \$\begingroup\$ @user23013 I got 114 with just using unnamed group, but not combining the line checks into one. \$\endgroup\$ – Martin Ender Feb 8 '15 at 13:01
11
\$\begingroup\$

Python, 219 bytes

def f(s):s=s.split();L=len;R=range;return L([r for r in R(L(s))for a in R(L(s[0]))for w in R(2,23)for h in R(3,min(L(s)+~r,23))if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

Better than Java, but boy the quintuple nested loops hurt. The for/in might be slightly compressible using %s substitution, but it wouldn't save much.

Expanded:

def f(s):
  s=s.split()
  L=len
  R=range
  return L([r for r in R(L(s))
              for a in R(L(s[0]))
              for w in R(2,23)
              for h in R(3,min(L(s)+~r,23))
              if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")* 
                 all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])
\$\endgroup\$
  • 1
    \$\begingroup\$ My instinct is to try the itertools nested loop generation sorcery. \$\endgroup\$ – imallett Feb 10 '15 at 6:17
7
\$\begingroup\$

Java, 304 bytes

This is a lot longer than a regular expression. It simply iterates over every possible square in the input. If it is a valid portal, it increments a counter by 1. It then returns the counter. This can probably be golfed much further. Any suggestions are welcome.

int a(String...a){a=a[0].split("\n");int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();for(;c<j;c++)for(d=0;d<i;d++)for(e=c+2;++e<j&e<c+24;)a:for(f=d+3;++f<i&f<d+24;){for(g=c;g<=e;g++)for(h=d;h<=f;h++){if(g==c|g==e&&h==d|h==f)continue;if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)continue a;}b++;}return b;}

Indented:

int a(String...a){
    a=a[0].split("\n");
    int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
    for(;c<j;c++)
        for(d=0;d<i;d++)
            for(e=c+2;++e<j&e<c+24;)
                a:for(f=d+3;++f<i&f<d+24;){
                    for(g=c;g<=e;g++)
                        for(h=d;h<=f;h++){
                            if(g==c|g==e&&h==d|h==f)
                                continue;
                            if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                continue a;
                        }
                    b++;
                }
    return b;
}

Full program:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;

public class B {

    public static void main(String[] args) throws FileNotFoundException {
        String blocks = new BufferedReader(new FileReader(args[0])).lines().reduce((a,b)->a+"\n"+b).get();
        System.out.println(new B().a(blocks));
    }

    int a(String...a){
        a=a[0].split("\n");
        int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
        for(;c<j;c++)
            for(d=0;d<i;d++)
                for(e=c+2;++e<j&e<c+24;)
                    a:for(f=d+3;++f<i&f<d+24;){
                        for(g=c;g<=e;g++)
                            for(h=d;h<=f;h++){
                                if(g==c|g==e&&h==d|h==f)
                                    continue;
                                if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                    continue a;
                            }
                        b++;
                    }
        return b;
    }

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.