17
\$\begingroup\$

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 and the goal is to minimize the size of your source code as measured in bytes.

Test cases

Truthy

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

Falsy

######
 #
######
 #
 #
######
 ##
####
  #
###
# #
###
####
#  #
#  #
####
######
######
######
######
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Can I take input as a list of coordinates? \$\endgroup\$
    – mousetail
    Dec 11, 2022 at 9:14
  • \$\begingroup\$ New way to fold my net #|##|##/#3#/#3#/##|##|# into a cube: fold |s 180° towards you, making the left and right columns overlap resulting in a standard net, which automatically folds into a cube when you fold the remaining edges 90° towards you. (Still doesn't qualify under your edit #4 though.) \$\endgroup\$
    – Neil
    Dec 22, 2022 at 0:23
  • \$\begingroup\$ @Neil Nice! That's a really bizarre folding pattern. Tough to get your mind around, and physically difficult to execute. \$\endgroup\$
    – Wheat Wizard
    Dec 22, 2022 at 1:22

3 Answers 3

7
\$\begingroup\$

Charcoal, 209 206 bytes

WS⊞υι≔ΣEυ⁺⌕Aι#×I1jκθ≔”)⊟⬤e~±”η≔⪪⁺⮌ηη⁴η≔ΣEηE⁴⁺✂ιλ⁴¦¹…ιλη≔⟦⟧υFθ«≔ΦE⁴XI1jκ№θ⁺ικζ¿⁼¹Lζ⊞υ⟦ι⊟ζ⦃ι0⦄⌊η⟧»Fυ«≔⊟ιδ≔⊟ιε≔Σιζ¿⁼LεLθP⬤⁶№εIκ¿№θζF⁼§δ¹∨§εζ§δ¹⊞υ⟦ζ⊟ι⁺ε⦃ζ§δ¹⦄⁺Φδμ§δ⁰⟧F⁻θEελ«≔ΦE⁴XI1jλ№θ⁺κλζ¿⁼¹LζFη⊞υ⟦κΣζ⁺ε⦃κ§λ⁰⦄λ

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:

WS⊞υιυ≔⌊Φυ№ι#θ≔⟦⁺E⁶ι⟦⌕υθ⌕θ#⟧⟧η≔EυEι⟦⟧θ≔¹ζFη«J⊟ι⊟ι≔§θⅉ§εⅈ«§≔εⅈιF⌕AKV#«M✳⊗⁻¹κ⊞η⁺E§⪪”)⊟Z➙.κ⊗φαμ”⁶κ§ιIλ⟦ⅉⅈ⟧M✳⊗⁻³κ»»¿¬⁼§εⅈι≔⁰ζ»⎚∧ζ¬Φ⁶⬤θ⬤λ⌕νι

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

WS⊞υιυ

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

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

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

≔EυEι⟦⟧θ

Start tracking dice placed at each position.

≔¹ζ

Assume the scrap does not need recycling.

Fη«

Loop over each die as it is placed.

J⊟ι⊟ι

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.

F⌕AKV#«

Loop over potential adjacent spots.

M✳⊗⁻¹κ

Move to that position.

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

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

M✳⊗⁻³κ

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.

\$\endgroup\$
14
  • \$\begingroup\$ @WheatWizard But I can fold that net into a cube... \$\endgroup\$
    – Neil
    Dec 11, 2022 at 14:53
  • \$\begingroup\$ There are a number of shapes which can be folded into a cube if you allow complex folds. For example ####### can also be folded into a cube. The question is limited to simple folds as described. \$\endgroup\$
    – Wheat Wizard
    Dec 11, 2022 at 14:58
  • 1
    \$\begingroup\$ @WheatWizard Sure. First, note that you can roll a 5×4 square horizontally into a tube, overlapping the left and right edges. If you try that with the net with the 3×2 hole, you end up with two tubelets joined by two squares. Rolling them up vertically and tucking one tubelet inside the other forms a cube. \$\endgroup\$
    – Neil
    Dec 11, 2022 at 15:08
  • 1
    \$\begingroup\$ @Jonah See my comment from a few hours ago; I haven't actually updated my answer yet. \$\endgroup\$
    – Neil
    Dec 11, 2022 at 20:33
  • 1
    \$\begingroup\$ @Jonah I finally got around to porting Ajax1234's answer, so I should now get the same results. \$\endgroup\$
    – Neil
    Jan 1, 2023 at 0:57
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Returns false for new, final truthy test case (with loop). \$\endgroup\$
    – Jonah
    Dec 11, 2022 at 20:10
  • \$\begingroup\$ Yea it only works with 90 degree anglees \$\endgroup\$
    – mousetail
    Dec 12, 2022 at 6:21
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Managed to sneak it under 600 bytes \$\endgroup\$
    – jezza_99
    Dec 11, 2022 at 22:39
  • \$\begingroup\$ @jezza_99 Thanks, updated \$\endgroup\$
    – Ajax1234
    Dec 11, 2022 at 22:42
  • \$\begingroup\$ replacing len with l=len saves 2 bytes (4 len replaced), using space for split saves another 3(space is default for split) \$\endgroup\$
    – okie
    Dec 13, 2022 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.