CGAC2022 Day 11: Reduce, Reuse, Regift

Question

Traditionally presents are kept secret in boxes wrapped in paper. Since the ice caps are melting Santa Claus has begun to investigate some ways they might make the whole gift wrapping operation a little more eco-friendly. The first thing they've decided to do is to put all presents in perfectly cubic boxes. This makes things more efficient to process and cuts down on waste. The second thing they are doing is to reuse some of the scrap paper to wrap boxes as opposed to tossing it.

In this challenge you will help Santa make a machine which will identify which pieces of scrap can still be used to wrap gifts. Because of the industrial wrapper cutting machine used scraps will always be connected faces of a square tiling. The squares will also always be the exact size of the faces that make up the boxes Santa uses.

For example you might get the following scrap:

   #
####
 #

This scrap can fold around the cube perfectly with no overlap and no empty space. Some scraps might overlap, for example:

 #
#######
#

Can wrap around the cube perfectly, but since there are more than 6 squares there must be overlap. This is fine and this scrap can be used to wrap.

Some scraps can't wrap a cube without leaving some gaps. For example

######

This has 6 squares, but there's no way to fold them which covers all sides of a cube. So this should be sent to the recycling plant.

Some scraps can wrap the cube but require fancy folding techniques. For example:

####
####
####

This can be folded to wrap around a cube, but it requires folds that aren't along the edges of the squares. The wrapping machine just isn't that fancy, so this should be sent to the recycling plant.

The following can be folded with the only permanent creases being along the edges of the squares:

####
#  #
#  #
####

However it requires making multiple folds at once and bending the paper to make the geometry fit. The machine can't do anything that fancy, it makes one fold at a time along one straight axis, folding every edge that meets that axis.

Task

For this challenge, take a scrap as input in any reasonable method. Output one of two consistent distinct values. One value should only be output if the scrap can be used as gift wrapping, the other should only be output if the scrap should be sent to the recycling plant.

Some folds are almost possible, but require paper to pass through itself to complete the fold. If the a shape requires this to fold you can output either value. That is you can choose to assume that paper can pass through itself or not, whichever is more convenient for you.

In order to be eco-friendly Santa is asking you to minimize the size of your source code as measured in bytes. (You've tried to explain that that's not how things work.) So this is code-golf and the goal is to minimize the size of your source code as measured in bytes.

Test cases

Truthy

  #
####
  #

#
#
#
####

##
####
   #
   #
   #

 ###
 # #
 # #
####
  #

Falsy

######

 #
######

 #
 #
######

 ##
####
  #

###
# #
###

####
#  #
#  #
####

######
######
######
######

Answer 1

Charcoal, 209 206 bytes

ＷＳ⊞υι≔ΣＥυ⁺⌕Ａι#×Ｉ1jκθ≔”)⊟⬤e~±”η≔⪪⁺⮌ηη⁴η≔ΣＥηＥ⁴⁺✂ιλ⁴¦¹…ιλη≔⟦⟧υＦθ«≔ΦＥ⁴ＸＩ1jκ№θ⁺ικζ¿⁼¹Ｌζ⊞υ⟦ι⊟ζ⦃ι0⦄⌊η⟧»Ｆυ«≔⊟ιδ≔⊟ιε≔Σιζ¿⁼ＬεＬθＰ⬤⁶№εＩκ¿№θζＦ⁼§δ¹∨§εζ§δ¹⊞υ⟦ζ⊟ι⁺ε⦃ζ§δ¹⦄⁺Φδμ§δ⁰⟧Ｆ⁻θＥελ«≔ΦＥ⁴ＸＩ1jλ№θ⁺κλζ¿⁼¹ＬζＦη⊞υ⟦κΣζ⁺ε⦃κ§λ⁰⦄λ

Attempt This Online! Link is to verbose version of code. Outputs - for wrapping, nothing for recycling. Port of @Ajax1234's Python answer, except using complex numbers as coordinates as Charcoal has no tuples and lists can't be used as dict keys. No explanation as I don't actually understand how it works. Edit: Saved 3 bytes because the bleeding edge version of Charcoal on ATO will now Cast strings containing complex constants thus avoiding the need to PythonEvaluate.

Previous 138 byte version only handled 90° folds:

ＷＳ⊞υιυ≔⌊Φυ№ι#θ≔⟦⁺Ｅ⁶ι⟦⌕υθ⌕θ#⟧⟧η≔ＥυＥι⟦⟧θ≔¹ζＦη«Ｊ⊟ι⊟ι≔§θⅉ§εⅈ«§≔εⅈιＦ⌕ＡＫＶ#«Ｍ✳⊗⁻¹κ⊞η⁺Ｅ§⪪”)⊟Z➙.κ⊗φαμ”⁶κ§ιＩλ⟦ⅉⅈ⟧Ｍ✳⊗⁻³κ»»¿¬⁼§εⅈι≔⁰ζ»⎚∧ζ¬Φ⁶⬤θ⬤λ⌕νι

Try it online! Link is to verbose version of code. Outputs - for wrapping, nothing for recycling. Explanation:

ＷＳ⊞υιυ

Input the scrap and also print it to the canvas so that it can be peeked later.

≔⌊Φυ№ι#θ≔⟦⁺Ｅ⁶ι⟦⌕υθ⌕θ#⟧⟧η

Find the coordinates of a # and place a die at that spot.

≔ＥυＥι⟦⟧θ

Start tracking dice placed at each position.

≔¹ζ

Assume the scrap does not need recycling.

Ｆη«

Loop over each die as it is placed.

Ｊ⊟ι⊟ι

Jump to its position.

≔§θⅉε

Get the row of the tracking matrix for convenience.

¿¬§εⅈ«

If we haven't seen this spot yet, then:

§≔εⅈι

Place the die at this spot.

Ｆ⌕ＡＫＶ#«

Loop over potential adjacent spots.

Ｍ✳⊗⁻¹κ

Move to that position.

⊞η⁺Ｅ§⪪”)⊟Z➙.κ⊗φαμ”⁶κ§ιＩλ⟦ⅉⅈ⟧

Calculate the die obtained by rolling the current die in this direction and push it to the list of placed dice.

Ｍ✳⊗⁻³κ

Move back to the original position.

»»¿¬⁼§εⅈι

But if there was already a different die placed here, then...

≔⁰ζ

... mark the scrap as for recycling.

»⎚∧ζ¬Φ⁶⬤θ⬤λ⌕νι

Check that each side of the die touched the scrap.

Answer 2

Rust + NAlgebra + arrayvec, 1019 bytes

Needless to say I'm not winning this one. There probably is way way more efficient way to do this.

use nalgebra::*;use arrayvec::*;fn g(a:[[bool; 9];9],b:&mut[Vec<(isize,isize)>;27],c:(isize, isize),d:Quaternion<f32>,)->bool{let m=Matrix4::from(UnitQuaternion::new_normalize(d))*Vector4::new(0.,0.,1.,0.);let n=(((1.+m.x).round()as usize)*9+((1.+m.y).round()as usize)*3+(1.+m.z).round()as usize);c.0<0||c.1<0||c.0>8||c.1>8||!a[c.0 as usize][c.1 as usize]||b[n].contains(&c)||(b.iter().all(|j|!j.contains(&c))&&{b[n].push(c);g(a,b,(c.0-1,c.1),d*Quaternion::new((0.5).sqrt(),0.,(0.5).sqrt(),0.,))&&g(a,b,(c.0+1,c.1),d*Quaternion::new((0.5).sqrt(),0.,-(0.5).sqrt(),0.))&&g(a,b,(c.0,c.1+1),d*Quaternion::new((0.5).sqrt(),(0.5).sqrt(),0.,0.))&& g(a,b,(c.0,c.1-1),d*Quaternion::new((0.5).sqrt(),-(0.5).sqrt(),0.,0.))})}let f=|a:[[bool; 9]; 9]|{let mut c = (0..27).map(|_|Vec::new()).collect::<ArrayVec::<_,27>>().into_inner().unwrap();let f=(0..9).find_map(|j|{a[j].iter().position(|&m| m).and_then(|k|Some((j as isize, k as isize)))}).unwrap();g(a,&mut c,f,Quaternion::identity())&&c.iter().filter(|i|i.len()>0).count()>5};

Playground Link

Explained

Basically, I have a 3x3x3 array that has the coordinates of each normal. If all 6 normals are represented we return true.

To keep track of the rotation of the current face we use quaternions. These are convenient since we can cover the same face from different angles.

    use nalgebra::*; // 0.31.4
    use arrayvec::*; // 0.7.2

    // this function recurses on the sides of a square, and adds it to the collection. Returns false if it's impossible to make a square
    fn g(a: [[bool; 9]; 9],b: &mut [Vec<(isize,isize)>;27],c: (isize, isize),
        d: Quaternion<f32>,
    ) -> bool {
        // The normal vector of this face
        let m = Matrix4::from(UnitQuaternion::new_normalize(d)) * Vector4::new(0., 0., 1., 0.);
        // The index of this face in the map of all normals
        let n =(((1.+m.x).round()as usize)*9+((1.+m.y).round()as usize)*3+(1.+m.z).round()as usize);
        // If we are out of bounds, just return True
        c.0 < 0
            || c.1 < 0
            || c.0 > 8
            || c.1 > 8
        // If this face is not actually present in the wrapping paper, return True
            || !a[c.0 as usize][c.1 as usize]
        // If we already checked this face, return true
            || b[n].contains(&c)
        // If this face already has a different normal, return false. This is the "fancy wrapping" variant
            || (b.iter().all(|j|!j.contains(&c)) && {
                // Set this normal to our coordinates
                b[n].push(c);

                // Recurse in all 4 directions, using a quaternion to represent our rotation.
                       g(a, b, (c.0 - 1, c.1), d * Quaternion::new( (0.5).sqrt(), 0., (0.5).sqrt(), 0.,))
                    && g(a, b, (c.0 + 1, c.1), d * Quaternion::new((0.5).sqrt(),  0., -(0.5).sqrt(), 0.))
                    && g(a, b, (c.0, c.1 + 1), d * Quaternion::new((0.5).sqrt(),  (0.5).sqrt(), 0., 0.))
                    && g(a, b, (c.0, c.1 - 1), d  * Quaternion::new((0.5).sqrt(), -(0.5).sqrt(), 0.,0.))
            })
    };
    // f is the main function
    let f = |a: [[bool; 9]; 9]| {
        // Create a map of empty vectors
        let mut c = (0..27).map(|_|Vec::new()).collect::<ArrayVec::<_,27>>().into_inner().unwrap();
        // find the starting point, the first cell that's true.
        let f = (0..9)
            .find_map(|j| {
                a[j].iter()
                    .position(|&m| m)
                    .and_then(|k| Some((j as isize, k as isize)))
            })
            .unwrap();
        // Execute g on this cell
        g(a, &mut c, f, Quaternion::identity())
            // check if we have at least 6 faces
            && c.iter().filter(|i|i.len()>0)
                .count()
                > 5
    };

Edit: This assumes all folds are 90 degrees inwards, so won't pass the new test cases. This approach fundamentally can't handle 180 degree folds.

Answer 3

Python3, 636 bytes:

E=enumerate
g=lambda e,x,y:[(x,y,X,Y)for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]if(n:=(x+X,y+Y))in e]
def f(b):
 e,C=[(x,y)for x,r in E(b)for y,t in E(r)if'#'==t],['0231','0435','2415']
 C+=[i[::-1]for i in C]
 C=[a[i:]+a[:i]for a in C for i,_ in E(a)]
 q=[(*t[0],{(x,y):k[0]},1,k)for k in C for x,y in e if len(t:=g(e,x,y))==1]
 while q:
  x,y,X,Y,m,I,p=q.pop(0)
  if len(m)==len(e):
   if{*m.values()}=={*'012345'}:return 1
   continue
  if(n:=(x+X,y+Y))in e:
   if n not in m or m[n]==p[I%4]:q+=[(*n,X,Y,{**m,n:p[I%4]},I+1,p)]
  else:
   for x,y in e:
    if(x,y)not in m and len(t:=g(e,x,y))==1:q+=[(*t[0],{**m,(x,y):k[0]},1,k)for k in C]

Try it online!

Does not allow paper folding through itself.