7
\$\begingroup\$

Challenge

Make the shortest program to determine if the figures in the input will fit into the space in the input.

Requirements

The input will be in the format of this example: Input:

+----+      -- +--+
|    +----+    |  |
|         |    +--+
|         |
+---------+

Output:

+----+
|+--++----+
||  |--   |
|+--+     |
+---------+

First, starting in the upper left corner, is the space that the program will try to fit the figures into. Then there is a space. Then there is a figure, in this case two dashes. Then there is a space, then a second figure. The output is the figures fitted inside of the space.

Rules about figures and input:

  • The upper left corner of a shape will always be on the first row.
  • After a figure, there is one space, as shown in the example.
  • There is no limit on the size of the figures.
  • The first figure will always be the space that the program will determine if the figures fit into.
  • There is no limit on the number of figures, but there will only be one space to fit them into.
  • All figures will be made of | and - for the sides and + for the corners. These are the only characters used besides spaces and newlines.
  • Figures cannot be rotated.
  • Borders cannot overlap.
  • You may fit one figure inside of another.
  • The figures do not have to be closed.
  • The space will always be closed.
  • The space does not have to be completely filled.
  • You may not split up shapes.

Rules about output:

  • If the figures fit into the space, the program should output the figures inside of the space, as shown above. It does not matter how they are arranged, as long as no borders overlap, all figures are correct, and no shapes are split up.
  • If the figures do not fit, output "no".

Examples

Input:

+--+ |
+--+

Output:

no

Input:

+---+  -+
|   |   |
|   |
+---+

Output:

+---+
|-+ |
| | |
+---+

This is also valid:

+---+
| -+|
|  ||
+---+

Input:

+----------+ +-----+ -+
|          | |     |  |
|          | |     |  
|          | +-----+
|          |
+----------+

Output:

+----------+
|+-----+   |
||-+   |   |
|| |   |   |
|+-----+   |
+----------+

This is a code golf, so the shortest answer wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ You say make the shortest program at the top, but answer with most votes wins at the bottom. Note that this will get closed as a popularity contest. \$\endgroup\$ – Dennis Feb 22 '17 at 14:53
  • 1
    \$\begingroup\$ This isn't a programming puzzle either. That has a fairly specific meaning; check the tag wiki for more information. \$\endgroup\$ – user62131 Feb 22 '17 at 14:54
  • \$\begingroup\$ I fixed this. It is now a code golf challenge \$\endgroup\$ – Dave Jones Feb 22 '17 at 14:56
  • 1
    \$\begingroup\$ Consider editing out the specific "no" output, and either (1) only having to handle valid input (any behaviour); or (2) allowing standard falsey outputs and errors. \$\endgroup\$ – Jonathan Allan Feb 22 '17 at 15:07
  • \$\begingroup\$ It looks like the two -- are misplaced in one of the first two images [Requirements]. \$\endgroup\$ – Jonathan Allan Feb 22 '17 at 15:09
5
\$\begingroup\$

Python 2, 529 692 683 681 bytes

L=len
R=range
def g(s):S=s.split('\n');S=[l.ljust(L(S[0]))for l in S];Z=zip(*S);I=[-1]+[i for i in R(L(Z))if{' '}==set(Z[i])]+[None];return[[list(x)for x in zip(*Z[I[i]+1:I[i+1]])if set(x)!={' '}]for i in R(L(I)-1)]
def f(s):
 S=g(s);G(S[0],1,1)
 for l in F(*S)or['no']:print''.join(l).replace('~',' ')
def G(a,i,j):
 if len(a)>i>-1<j<len(a[0])and'!'>a[i][j]:
	for x,y in(0,1),(0,-1),(1,0),(-1,0):G(a,i+x,j+y);a[i][j]='~'
def F(a,*s):
 if not s:return a
 c=s[0];h,w=L(c),L(c[0])
 for i in R(1,L(a)-h):
	for j in R(1,L(a[0])-w):
	 T=1;A=[l[:]for l in a]
	 for y in R(h):
		for x in R(w):
		 C=c[y][x]
		 if' '<C:T&=A[y+i][x+j]>'}';A[y+i][x+j]=C
	 r=T and F(A,*s[1:])
	 if r:return r

Try it online!

Gained a lot of bytes by adding a flood fill to the first shape.

This is to fix fix cases where a figure can be outside the shape, but inside its bounding box.

eg. The shape fits inside the bounding box, but outside the shape:

Input:        Wrong:      Correct:
+-+    --     +-+         +-+
| |           | |--       | |
| +--+        | +--+      | +--+
|    |        |    |      |--  |
+----+        +----+      +----+

Explanation

f takes input as a single string with newlines.

+----+      -- +--+
|    +----+    |  |
|         |    +--+
|         |
+---------+

The shapes are split up with g(s) and mapped to lists of lists

[[['+', '-', '-', '-', '-', '+', ' ', ' ', ' ', ' ', ' '], ['|', ' ', ' ', ' ', ' ', '+', '-', '-', '-', '-', '+'], ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'], ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'], ['+', '-', '-', '-', '-', '-', '-', '-', '-', '-', '+']],
[['-', '-']],
[['+', '-', '-', '+'], ['|', ' ', ' ', '|'], ['+', '-', '-', '+']]]

The first shape is flood filled with ~ (G(S[0])), so we know the allowed area:

+----+     
|~~~~+----+
|~~~~~~~~~|
|~~~~~~~~~|
+---------+

For each other shape we recursively fit them into the first F(a,*s), returning when all of them fit, or at the end, if no configuration does.

+----+        +----+        +----+        +----+        +----+     
|--~~+----+   |~--~+----+   |~~--+----+   |~~~~+----+   |~~~~+----+
|~~~~~~~~~|   |~~~~~~~~~|   |~~~~~~~~~|   |--~~~~~~~|   |~--~~~~~~|
|~~~~~~~~~|   |~~~~~~~~~|   |~~~~~~~~~|   |~~~~~~~~~|   |~~~~~~~~~|
+---------+   +---------+   +---------+   +---------+   +---------+
     |             |             |             |             |
     V             V             V             V             V
  No room        No room      No room       No room     +----+     
  for next       for next     for next      for next    |+--++----+
  shape          shape        shape         shape       ||--|~~~~~|
                                                        |+--+~~~~~|
                                                        +---------+

                                                           Done!

Lastly we print the combined shapes, without ~.

+----+     
|+--++----+
||--|     |
|+--+     |
+---------+
\$\endgroup\$
  • \$\begingroup\$ +1 for being fast enough to be runnable. I think (disclaimer: I don't know Python) C>' ' can be replaced with C>32. \$\endgroup\$ – user202729 Nov 1 '17 at 10:01
  • \$\begingroup\$ Great answer. Will accept it if there are no new answers for a while. \$\endgroup\$ – Dave Jones Nov 1 '17 at 11:31
  • \$\begingroup\$ @user202729 Python's object comparison does allow for comparing strings with integers, though int("...")<"..." will always be true; Python's 'chars' are really strings of length one, which always come after an integer. One thing one could do to save a byte, though, would be to replace if C>' ' with if' '<C. \$\endgroup\$ – Jonathan Frech Nov 2 '17 at 6:31
2
\$\begingroup\$

Wolfram Language (Mathematica), 811 bytes

(M=MorphologicalComponents;L=Length;A=Thread;T=Last;B=Table;P=Position;W=Prepend;g=AnyTrue[#,#!=" "&]&;h[n_]:=If[DuplicateFreeQ[Join@@B[(#-{1,1}+W[n,{1,1}][[i]]&)/@P[t[[i]],1],{i,L[y]}]],n,Nothing];R[z_]:=PadRight[#,Max[L/@z]," "]&/@z;s=Characters/@StringSplit[#,"\n"];s=R@s;r=Map[#/.{Longest[" "...],n___," "...}->{n}&,DeleteCases[A/@Split[A@s,g],_?(!g@#&),2],2];r[[1]]=R@#&@@r;t=r/.{"|"|"+"|"-"->1," "->0};y=M[#,Method->"ConvexHull"]&/@t;o=y-M/@t;u=T[h/@T@T@Reap[Outer@@Append[W[B[{NoneTrue[Flatten@B[#[[q+1,w+1]]==1&&o[[1]][[i+q,j+w]]==0,{w,0,L@#&@@#-1},{q,0,L@#-1}],TrueQ],i,j},{i,1,1+L@#&@@y-L@#},{j,1,1+L@y[[1,1]]-L@#&@@#}]&/@y[[2;;]],If[And@@(First/@{##}),Sow[#[[2;;]]&/@{##}]]&],2]]];If[u=={},"no",Grid@ReplacePart[r[[1]],Join@@B[(#-{1,1}+u[[i-1]])->Part[r[[i]],Sequence@@#]&/@P[t[[i]],1],{i,2,L@y}]]])&

enter image description here

It needs a frontend to display grid (which is not supported on tio.run).

The code does the following things:

  1. Get inside points of 1st shape
  2. Iterate over all starting point combinations
  3. Pick a combination where all other (2, 3, ...) shapes' points lie in waht we get in Step 1, and without any overlapped points
  4. Output (by ReplacePart)

If the input format can be more flexible, the code can be shortened to ~680 bytes. Besides that, there is still a lot of golfing space, though.

Try it online!

Expanded:

(M = MorphologicalComponents; L = Length; A = Thread; T = Last; 
  B = Table; P = Position; W = Prepend; g = AnyTrue[#, # != " " &] &; 
  h[n_] := If[
    DuplicateFreeQ[
     Join @@ B[(# - {1, 1} + W[n, {1, 1}][[i]] &) /@ P[t[[i]], 1], {i,
         L[y]}]], n, Nothing]; 
  R[z_] := PadRight[#, Max[L /@ z], " "] & /@ z; 
  s = Characters /@ StringSplit[#, "\n"]; s = R@s; 
  r = Map[# /. {Longest[" " ...], n___, " " ...} -> {n} &, 
    DeleteCases[A /@ Split[A@s, g], _?(! g@# &), 2], 2]; 
  r[[1]] = R@# & @@ r; t = r /. {"|" | "+" | "-" -> 1, " " -> 0}; 
  y = M[#, Method -> "ConvexHull"] & /@ t; o = y - M /@ t; 
  u = T[h /@ 
     T@T@Reap[
        Outer @@ 
         Append[W[
           B[{NoneTrue[
                Flatten@
                 B[#[[q + 1, w + 1]] == 1 && 
                   o[[1]][[i + q, j + w]] == 0, {w, 0, 
                   L@# & @@ # - 1}, {q, 0, L@# - 1}], TrueQ], i, 
               j}, {i, 1, 1 + L@# & @@ y - L@#}, {j, 1, 
               1 + L@y[[1, 1]] - L@# & @@ #}] & /@ y[[2 ;;]], 
           If[And @@ (First /@ {##}), Sow[#[[2 ;;]] & /@ {##}]] &], 
          2]]]; If[u == {}, "no", 
   Grid@ReplacePart[r[[1]], 
     Join @@ B[(# - {1, 1} + u[[i - 1]]) -> 
          Part[r[[i]], Sequence @@ #] & /@ P[t[[i]], 1], {i, 2, 
        L@y}]]]) &
\$\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.