9
\$\begingroup\$

This is an additional challenge to the generate Loopy puzzles challenge. You might want to solve this challenge before attempting the harder challenge in the previous link.

The goal of this challenge is to validate the solution to a loopy puzzle. Please take all documentation on what a loopy puzzle is from the previous link. A solved loopy puzzle is formatted in a very similar way to the output of a valid submission to the “generate loopy puzzles” challenge and may look like this:

+-+-+ +-+ +-+ +
|   | | |2|3|  
+-+ + + + + +-+
 2| | | |2|  3|
+ + +-+ + + +-+
 2|  2 1|3| |  
+-+ +-+ +-+ +-+
|2  | |    1 2|
+ +-+ +-+ +-+ +
| |2 1 2|3|3| |
+ + +-+ +-+ +-+
| | |3|2   1   
+ +-+ +-+-+-+-+
|        2 2  |
+-+-+-+-+-+-+-+

The path that makes up the solution is marked with | and - characters between the + characters.

Input specification

Your program shall receive a loopy puzzle with a solution formatted like the example above as input. Your program shall infer the size of the puzzle from the input. You may make the following assumptions about the input:

  • The puzzle has no less than 2 and no more than 99 cells in either direction
  • Thus, each line has a maximum length of 199 characters not including the newline character(s)
  • Thus, the input contains a maximum of 99 lines
  • each line may end after the last printable character or may be padded with whitespace characters so it has a length of up to 2·y + 1 characters where y is the number of cells in horizontal direction
  • each position with both x and y coordinates even contains a + character
  • positions horizontally or vertically adjacent to positions containing + characters contain either a whitespace character, are behind the end of line or contain a - character if horizontally adjacent or a | character if vertically adjacent
  • all other positions are either behind the end of line or contain one of the characters , 0, 1, 2, or 3
  • all lines are terminated with your platforms default newline character(s)
  • there is exactly one trailing newline

Input shall be received in one of the following ways:

  • From standard input
  • As the value of a parameter named p in an HTTP POST request
  • As the content of an HTML form
  • As the content of a file named p in an implementation-defined directory
  • In an implementation defined way at runtime if the former four are not available
  • Hard coded if your language provides no mean of receiving input

Output specification

Your program shall terminate for all inputs matching the input specification and shall compute whether the solution to the puzzle is correct. Your program shall output the result of the computation as a boolean value in one of the following ways:

  • As an exit status of either zero (solution is valid) or non-zero (solution is invalid)
  • As the character y (solution is valid) or n (solution is invalid) followed by zero or more arbitrary characters output in an implementation defined way

The behaviour of your program is unspecified when encountering input not formatted according to the input specification.

Scoring

The score of your program is the number of characters in its source except for omittable whitespace characters and omittable comments. You are encouraged to indent your submission so it's easier to read for the others and to comment your solution so its easier to follow.

Submissions that fail to follow the input or output specification or generate incorrect results are invalid.

\$\endgroup\$
  • \$\begingroup\$ How is input to be handled? Read from a file? STDIN? Can I write a function? \$\endgroup\$ – Martin Ender Aug 17 '14 at 15:20
  • \$\begingroup\$ @MartinBüttner "your program shall receive ...". Not sure why'd you like to read from a file. \$\endgroup\$ – John Dvorak Aug 17 '14 at 15:26
  • \$\begingroup\$ @MartinBüttner You have to write a complete program. I think the language "your program", "shall terminate", "exit status" is pretty clear. \$\endgroup\$ – FUZxxl Aug 17 '14 at 15:28
  • 1
    \$\begingroup\$ Also note that in most puzzles 0 is also a valid number for a cell. \$\endgroup\$ – Howard Aug 17 '14 at 15:30
  • \$\begingroup\$ @Howard Sorry, missed that. \$\endgroup\$ – FUZxxl Aug 17 '14 at 15:35
2
\$\begingroup\$

GolfScript, 133 characters

'|':^4,{48+.(}%+^*1>.^/'-'*+2/:F;4{{~@@/*}2F//n%zip-1%n*}:X*.'+-'?.3+@/(-2<' 9'+\+'9-+  99|+  9'3/:F;.,4*{X}*.9`?@=\' +09
'-!&'ny'1/=

Expects the input from STDIN and prints y for a valid solution and n for an invalid one. Performs the task by using mostly string-replace on the grid or with rotated versions of the grid.

Annotated code:

# construct the string "|0|/|1|0|2|1|3|2-0-/-1-0-2-1-3-2"
# split into pieces of two and save to variable F
'|':^4,{48+.(}%+^*1>.^/'-'*+
2/:F;

# run the code block X 4 times
# with X: string-replace 1st item in F with 2nd, 3rd with 4th, ...
# i.e. '|0' with '|/', '|1' with '|0'
# and then rotate grid by 90 degrees
4{{~@@/*}2F//n%zip-1%n*}:X*

# for a valid grid all digits are now reduced to exactly '0'
# (i.e. no '1' or '2' or '3' or '/')

# now follow the loop along and remove it
# start: find the first occurence of '+-+' and replace with '+ 9'
# note: '9' is the marker for the current position
.'+-'?
.3+@/(-2<' 9'+\+

# string-replace '9-+' or '9|+' by '  9' (i.e. go one step along the loop)
# using block X enough times
'9-+  99|+  9'3/:F;
.,4*{X}*

# look for the marker '9' in the result and check if it is at the original
# position again
.9`?
@=

# the remaining grid must not contain any digits besides 0 and 9
# esp. no '|' or '-' may remain
\' +09
'-!

# check if both conditions are fulfilled and output corresponding character
&'ny'1/=
\$\endgroup\$
2
\$\begingroup\$

C# 803 579bytes

Complete program, reads from STDIN, should cope with any common new-line scheme as long as it has line feeds. Thanks to HackerCow for pointing out that I don't have to append a new line in a different question, prompting me to remove it here and save 4 bytes

Golfed code:

using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","").Split('\n');int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;var B=new int[w,h];var S=new int[w*h*9];for(;i++<w-2;)for(j=0;j<h-2;B[i,j]=c)if((c=(D[j++][i-1]-8)%10)>5){c=5;T++;S[0]=i+j*w;}for(i=0;++i<w-1;)for(j=0;++j<h-1;)R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R;for(o=h=0;o<O;B[i,j]=0)if(B[i=(c=S[o++])%w,j=c/w]>4){h++;S[O++]=(S[O++]=c-w-1)+2;S[O++]=(S[O++]=c+w-1)+2;z=j%2<1?w*2:2;S[O++]=c-z;S[O++]=c+z;}C.Write(h-R<T?"n":"y");}}

The code performs 3 checks, first checking the number of lines around each number and that each junction has 0 or 2 lines leading from it, then that all the lines are joined together.

Formatted code:

using C=System.Console;

class P
{
    static void Main()
    {
        var D=C.In.ReadToEnd().Replace("\r","").Split('\n');
        int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;
        var B=new int[w,h]; // this is the grid
        var S=new int[w*h*9]; // this is a list of joined up lines (stored as x+y*w)

        for(;i++<w-2;)
            for(j=0;j<h-2;B[i,j]=c)
                if((c=(D[j++][i-1]-8)%10)>5)
                { // we are a line
                    c=5;
                    T++; // increment line counter
                    S[0]=i+j*w; // set start of loop
                }

        for(i=0;++i<w-1;) // this loop checks the numbers and that every + has 0 or 2 lines leading from it
            for(j=0;++j<h-1;)
                R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R; // set R to 7 (no significance) if check fails

        for(o=h=0;o<O;B[i,j]=0) // this loops through the list of joined lines adding more until the whole loop has been seen
            if(B[i=(c=S[o++])%w,j=c/w]>4)
            {
                h++; // increment "seen" counter
                S[O++]=(S[O++]=c-w-1)+2;
                S[O++]=(S[O++]=c+w-1)+2;
                z=j%2<1?w*2:2; // special for | and -
                S[O++]=c-z;
                S[O++]=c+z;
            }

        C.Write(h-R<T?"n":"y"); // check if R is greater than 0 or h is less than T and output appropriately
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks @edc65, no idea how I missed that! \$\endgroup\$ – VisualMelon Aug 17 '14 at 22:38
1
\$\begingroup\$

Cobra - 514

class P
    def main
        t,m,g=[[1]][:0],nil,File.readAllLines('p')
        u,i=g[0].length,1
        for l in g.length,for c in u,if g[l][c]in'0123'
            n=0
            for j in-1:2:2,for r in[g[l+j][c],g[l][c+j]],if r in'-|',n+=1
            if'[n]'<>g[l][c],m?='n'
        else if g[l][c]in'-|',x,y,t,d=c,l,t+[[c,l]],g[l][c]
        while i
            i=z=6
            for f,b in[[-1,1],[1,1],[0,2],[-1,-1],[+1,-1],[0,-2]]
                if'-'==d,f,b=b,f
                for w in t.count,if z and t[w]==[x+f,y+b],t,x,y,d,z=t[:w]+t[w+1:],x+=f,y+=b,g[y][x],0
                i-=z//6
        print if(t.count,'n',m?'y')

Checks if every number has the right number of lines next to it, and then walks a path around the lines and checks if it missed any.

\$\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.