14
\$\begingroup\$

Setup

Take the following 4x4x4 cube along with a 2D view of 3 of its faces, with a common 1x1x1 cube highlighted:

enter image description here

The arrows represent the points of view that generated the V1, V2 and V3 faces drawn underneath the big cube.

Given an arrangement of some 1x1x1 cubes inside the main cube we can try and identify it with only three projections. For example, the arrangement below:

enter image description here

could be represented as follows:

V1
X...
....
....
XXXX

V2
X...
X...
X...
X..X

V3
X...
X...
X...
XXXX

However, if we consider only projections on V1 and V2, most of the time we can't identify uniquely the arrangement being considered.(there are arrangements that can't be uniquely identified, even with the 6 projections)

Task

Given projections on V1 and V2, output the minimum and maximum number of 1x1x1 cubes that an arrangement could have and still produce the projections V1 and V2.

I'll walk you through 2 examples:

Explained example 1

V1
XXXX
....
....
....

V2
X...
X...
X...
X...

These two projections signal some directions along which there must be cubes:

enter image description here

and the output would be 4, 16; This is the case because both V3 below represent valid projections on V3:

V3a
X...
.X..
..X.
...X

This is a "diagonal" pattern of cubes in the back plane, when viewed from V3; ...

V3b
XXXX
XXXX
XXXX
XXXX

and this is a full face in the back plane.

Explained example 2

V1
XXXX
XXXX
XXXX
XXXX

V2
XXXX
....
....
....

These projections represent the top face of the main cube, so in this case we managed to identify the arrangement uniquely. The output in this case would be 16, 16 (or 16, see output rules below).

Input

Your code takes the projections on V1 and V2 as input. There are a variety of reasonable ways for you to take this input. I suggest the following to represent each projection:

  • An array of length 4 with strings of length 4, two different characters to encode "empty" or "filled", like ["X...", ".X..", "..X.", "...X"] for the V3a above.
  • An array/string of length 16, representing the 16 squares of the projection, like "X....X....X....X" for V3a above.
  • An integer where its base 2 expansion encodes the string above; 1 must represent the X above, so V3a above would be 33825 = b1000010000100001.

For any of the alternatives above, or for any other valid alternative we later decide that is helpful for you guys, you can take any face in any orientation you see fit, as long as it is consistent across test cases.

Output

The two non-negative integers representing the minimum and maximum possible number of 1x1x1 cubes in an arrangement that projects onto V1 and V2 like the input specifies. If the minimum and maximum are the same, you can print only one of them, if that helps you in any way.

Test cases

(I didn't really know how to format these... if needed, I can reformat them! Please let me know.)

XXXX
....
....
....,
X...
X...
X...
X... -> 4, 16

XXXX
XXXX
XXXX
XXXX,
XXXX
....
....
.... -> 16, 16

XXXX
XXXX
XXXX
XXXX,
XXXX
....
..X.
.... -> 16, 20

X..X
.XX.
.XX.
X..X,
X.XX
.X..
..X.
XX.X -> 8, 16

XXXX
XXXX
XXXX
XXXX,
XXXX
XXXX
XXXX
XXXX -> 16, 64

X...
....
....
XXXX,
X...
X...
X...
X..X -> 8, 8

X..X
....
....
XXXX,
X...
X...
X...
X..X -> 8, 12

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!

\$\endgroup\$
  • \$\begingroup\$ brute-forcing is gonna take a while... \$\endgroup\$ – Surculose Sputum Mar 24 at 0:17
  • 4
    \$\begingroup\$ Can I take V1 rotated once, so that V1 and V2 are vertically aligned? \$\endgroup\$ – Bubbler Mar 24 at 0:31
  • 1
    \$\begingroup\$ @Bubbler can take any face in any orientation you see fit, as long as it is consistent across test cases \$\endgroup\$ – RGS Mar 24 at 6:40
  • 2
    \$\begingroup\$ @RGS I had this wild brute force idea where each cube was one bit, so V1 and V2 started off as bit arrays, and the way things were set up it would save bytes for V1 to be represented on a by-row basis where each row was a 4-bit number instead of individual bits. It doesn't matter anymore though, it would save even more bytes if I threw my solution out the window and just ported Surculose's Python solution to Ruby instead. \$\endgroup\$ – Value Ink Mar 24 at 17:00
  • 1
    \$\begingroup\$ @ValueInk I also had to throw my brute force solution out the window. \$\endgroup\$ – Neil Mar 24 at 21:34
10
\$\begingroup\$

APL (Dyalog Unicode), 11 bytes

+.(⌈,×)/+⌿¨

Try it online!

Takes V1 and V2 as two binary matrices inside a nested vector, and V1 is rotated so that it vertically lines up with V2. Returns doubly nested vector of (min, max).

How it works

The first column of V1 and the first column of V2 decide the first vertical layer of 4x4 cells. If n cells are shaded in V1's column and m cells in V2's, the minimum number of shaded cells in the corresponding 4x4 layer is max(m,n), and the maximum is m * n.

min          |  max
  | 1 0 1 0  |    | 1 0 1 0
-----------  |  -----------
1 | 1 0 0 0  |  1 | 1 0 1 0
1 | 1 0 0 0  |  1 | 1 0 1 0
0 | 0 0 0 0  |  0 | 0 0 0 0
1 | 0 0 1 0  |  1 | 1 0 1 0

Therefore, it suffices to count ones in each column, and evaluate sums of the pairwise max (for minimum) and pairwise product (for maximum) of the column sums.

+.(⌈,×)/+⌿¨
        +⌿¨  ⍝ In each matrix, evaluate column sums
       /     ⍝ Over the two vectors,
+. ⌈         ⍝ Evaluate the sum of pairwise max
    ,        ⍝ and
+.   ×       ⍝ the sum of pairwise product
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Really lovely answer. \$\endgroup\$ – Jonah Mar 24 at 1:22
10
\$\begingroup\$

Python 3, 74 71 bytes

-3 bytes thanks to @Bubbler!

lambda V:(sum(f(*map(sum,p))for p in zip(*V))for f in[max,int.__mul__])

Try it online!

Input: a list of faces [V1,V2], each face is a 4x4 list of binary digit. The orientation of each face is as follow (V2 is rotated 90 degree clock-wise compare to the challenge's default orientation). Face orientation Output: A tuple of 2 integers, representing the min and max number of blocks.

Approach

Consider each of the 4 slices of the cube: take the max or the product of each slice We can see that for each slice, the min and max number of block in that slice is respectively the max and the product of the top and left strips.

Code explanation:

lambda V:(sum(f(*map(sum,p))for p in zip(*V))for f in[max,int.__mul__])

  • for f in[max,int.__mul__] assigns f first to the function max, then to the integer multiply function.
  • p in zip(*V) pairs each corresponding strips (aka rows) of the 2 faces together.
  • map(sum,p) applies the sum function to each row in the pair. The result is effectively (top, left).
  • f(*map(...)) computes either max(top,left) or top*left.
  • sum(f(...)) sums over all slices.
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Valid 71. \$\endgroup\$ – Bubbler Mar 24 at 1:28
  • \$\begingroup\$ @Bubbler thanks! I also came up with the same thing. Writing my explanation now, will update in a bit. \$\endgroup\$ – Surculose Sputum Mar 24 at 1:30
  • 1
    \$\begingroup\$ Also 71 \$\endgroup\$ – xnor Mar 24 at 2:18
  • 1
    \$\begingroup\$ Another 71 \$\endgroup\$ – xnor Mar 24 at 2:19
  • 1
    \$\begingroup\$ @Jonah MS Paint :) \$\endgroup\$ – Surculose Sputum Mar 24 at 2:56
4
\$\begingroup\$

Jelly, 7 bytes

§µ»/,P§

A monadic Link accepting a list of the two projections each being a list of lists of 1s and 0s, [V1, V2], with V2 rotated a quarter turn clockwise which yields a list of two integers, [min, max]

Try it online!

How?

The same method as Bubbler & Surculose Sputum came up with.

§µ»/,P§ - Link: list of two lists of lists of 1s and 0s
§       - sums
 µ      - start a new monadic chain, call that v
   /    - reduce (v) by:
  »     -   maximum (vectorises)
     P  - product of (v) (vectorises)
    ,   - pair
      § - sums
|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 61 58 22 bytes

≔E⁴EθΣ§λιθI⟦ΣEθ⌈ιΣEθΠι

Try it online! Takes input as a list of lists in a different orientation to the examples. Uses @Bubbler's formula. Explanation:

≔E⁴EθΣ§λιθ

Transpose the input while taking the count of the number of cubes in each row.

I⟦ΣEθ⌈ιΣEθΠι

Calculate the minimum and maximum cubes for each row, and then take the totals for all four rows.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ This one contains so much Greek it's almost readable. \$\endgroup\$ – probably_someone Mar 24 at 15:55

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.