Witness My Challenge (Tetris Puzzle)

3

1

Introduction

In the game The Witness (possible spoilers ahead) there is a group of puzzles that involve drawing a Tetris piece with your line while making sure that the symbol for the Tetris piece your currently drawing stays contained within the shape you've drawn.

witness tetris puzzle

For the image above the drawing works because the L-shaped and upside down L-shaped Tetris pieces, occupying the positions (1,2)(2,2)(3,2)(3,3) and (1,1)(1,0)(2,0)(3,0) respectively, and the icons, located at (3,0) and (3,3), are contained within the white line.

Challenge

Your goal is to draw the solution line such that it contains all Tetris pieces as well as their respective symbols. The solution line may not contain anymore squares than that which is required (i.e. you must contain the sum of the number of squares making up each Tetris piece). Each solution will begin in the bottom left and end in the top right. Lastly, this is code-golf, so the shortest solution (in bytes) wins.

Representation

Each of these puzzles use a HxW grid of squares to construct your Tetris pieces and have some space for you to draw lines in between them. The representation is best understood by example. For the above image the representation would be

===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

and the solution would be 

===========
|*********|
|*X X X X |
|*******  |
| X X X*X |
|  *** *  |
| X*X*X*X |
|  * * ***|
| X*X*X X*|
|*** *****|
===========

where each square is represented by an X and the solution is drawn using a line of *s. The number of lines for each puzzle is 2*H+3 and the number of characters for each line is 2*W+3.

Input

The first n lines will give you the Tetris piece followed by the location of the corresponding symbol for that Tetris piece. The format is as follows:

(i1,j1)(i2,j2)...(ik,jk)->(p,q)

where (ik,jk) is the kth coordinate pair of the Tetris piece (the left coordinate increases as you move down, the right coordinate increases as you move right) and (p,q) is the location of the corresponding symbol. The origin of each Tetris piece is the top left square (i.e. the top left square is (0,0)).

Example 1:

X
X
XX

would be

(0,0)(1,0)(2,0)(2,1)

Example 2:

XX
X
X

would be

(0,0)(1,0)(2,0)(0,1)

Example 3:

X  X
X  X

would be

(0,0)(1,0)(0,3)(1,3)

The next 2*H+3 lines will consist of the puzzle's grid.

Output

Output the puzzle grid with the solution line drawn in.

Examples

Example Input 1

(0,0)(0,1)->(2,1)
(0,0)(0,1)->(0,1)
(0,0)->(0,2)
=========
|       |
| X X X |
|       |
| X X X |
|       |
| X X X |
|       |
=========

Example Output 1

=========
|*******|
|*X X X |
|*******|
| X X X*|
|***** *|
|*X X*X*|
|*   ***|
=========

Example Input 2

(0,0)(0,1)(0,2)(1,2)(2,2)->(0,0)
(0,0)(1,0)(0,3)(1,3)->(2,1)
(0,0)(1,0)(2,0)->(1,3)
===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

Example Output 2

===========
|      ***|
| X X X*X |
|      ***|
| X X X X*|
|        *|
| X X X X*|
|*** *****|
|*X*X*X X |
|* ***    |
===========

Example Input 3

(0,0)(1,0)(2,0)->(1,0)
(0,0)(1,0)(2,0)->(1,6)
(0,0)(0,1)(0,2)->(1,3)
=================
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
=================

Example Output 3

=================
|***         ***|
|*X*X X X X X*X |
|* *******   *  |
|*X X X X*X X*X |
|* *******   *  |
|*X*X X X X X*X |
|* ***********  |
=================

Clarifications

  • It is assumed that for any given input there is a solution.
  • If there are multiple solutions just print one.

Bobas_Pett

Posted 2016-11-28T10:02:20.977

Reputation: 965

Can we assume there is always a solution? Can we assume the solution is always unique? – Martin Ender – 2016-11-28T10:42:24.417

Since the challenge is modeled off of the game there is always a solution for every puzzle and there may be more than 1 solution. – Bobas_Pett – 2016-11-28T10:44:26.143

In that case, do we print any one solution or all of them? – Martin Ender – 2016-11-28T10:50:16.543

Yeah, any valid solution. – Bobas_Pett – 2016-11-28T10:57:36.047

The introduction makes very little sense to me. What's the coordinate system? In what sense is there a "Tetris piece your currently drawing"? – Peter Taylor – 2016-11-28T22:30:36.190

@Peter Taylor -- The coordinates I use in the introduction are referring to the 4x4 grid in the picture, where the top left green square is at (0,0) and the bottom right green square is at (3,3) , the left coordinate is up-down and the right coordinate is left-right. The Tetris pieces are defined by the symbols, so in the picture they have an L shaped one located at the bottom left and a upside down (reflected) L shaped one located at the bottom right. These Tetris pieces in the image fully occupy a section in the grid (defined by the white line and the grid border). – Bobas_Pett – 2016-11-28T23:41:18.807

Answers

2

Python, 992

Takes input from stdin and prints the solution. Note that SE has turned my tab characters into four spaces - anything indented beyond one space should be a tab.

It shouldn't be too hard to beat this, but I thought I'd post it since no one else had posted a solution.

L=len
R=range
j=[(-1,0),(1,0),(0,-1),(0,1)]
P=lambda y,x,q:(y,x)==(0,w)and[q+[(y,x)]]or sum([P(y+e,x+d,q+[(y,x)])for e,d in j if not(y+e,x+d)in q and 0<=x+d<=w and 0<=y+e<=h],[])
def C(q,y,x,v):
 if(y,x)in v:return
 v.add((y,x))
 for e,d in j:
    Y,X=y+e,x+d;a,b=[(y+(e+s*d+1)/2,x+(d+s*e+1)/2)for s in[-1,1]]
    if 0<=X<w and 0<=Y<h and not(a in q and b in q and abs(q.index(a)-q.index(b))==1):C(q,Y,X,v)
def G(s,c):
 if not s:return not c
 for y,x in r:
    p=set((Y+y,X+x)for Y,X in s[0])
    if c&p==p and G(s[1:],c-p):return 1
def B(q):
 for y,x in r:
    c=set();C(q,y,x,c);s=[h for(w,h)in p if w in c]
    if s and not G(s,c):return 1
h,p,g=0,[],[]
try:
 while 1:
    s=raw_input()
    if'('in s:l,o=s.split('->');p.append(map(eval,[o,'('+l.replace(')','),')+')']))
    else:g.append(list(s))
except:h=L(g)/2-1;w=L(g[0])/2-1
r=[(x/w,x%w)for x in R(w*h)]
for s in P(h,0,[]):
 if not B(s):break
for(a,b),(c,d)in zip(s,s[1:]):g[1+2*a][1+2*b]=g[1+a+c][1+b+d]=g[1+2*c][1+2*d]='*'
print'\n'.join(''.join(r)for r in g)

Quick rundown of how it works:

P finds all possible paths.

C finds all the squares that are connected to a given square.

G determines whether or not a set of shapes fit exactly in a set of squares.

B determines whether or not a path is bad by checking each connected set of squares and checking if their shapes fit.

Examples

input:

(0,0)(0,1)->(2,1)
(0,0)(0,1)->(0,1)
(0,0)->(0,2)
=========
|       |
| X X X |
|       |
| X X X |
|       |
| X X X |
|       |
=========

output (all tetris pieces are grouped into the top-right):

=========
|***   *|
|*X*X X*|
|* *   *|
|*X*X X*|
|* * ***|
|*X*X*X |
|* ***  |
=========

input:

(0,0)(0,1)(0,2)(1,2)(2,2)->(0,0)
(0,0)(1,0)(0,3)(1,3)->(2,1)
(0,0)(1,0)(2,0)->(1,3)
===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

output (this is the only one that's the same as the example solution):

===========
|      ***|
| X X X*X |
|      ***|
| X X X X*|
|        *|
| X X X X*|
|*** *****|
|*X*X*X X |
|* ***    |
===========

input:

(0,0)(1,0)(2,0)->(1,0)
(0,0)(1,0)(2,0)->(1,6)
(0,0)(0,1)(0,2)->(1,3)
=================
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
=================

output (rightmost 2 pieces are grouped together):

=================
|*** *** *******|
|*X*X*X*X*X X X |
|* * * * *******|
|*X*X*X*X X X X*|
|* * * * *******|
|*X*X*X*X*X X X |
|* *** ***      |
=================

cardboard_box

Posted 2016-11-28T10:02:20.977

Reputation: 5 150

Asked: 2016-11-28T10:02:20.977

Viewed: 676 times

Active: 2016-11-30T01:23:06.680