Each of the six faces on a cube has a different digit (0 to 9) written on it; th

Question

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

Explanation / Answer

import java.util.*;

public class CubePair {
   
    private final static int[] DIGITS = new int[] {0,1,2,3,4,5,6,7,8,9};
   
    public Set<Integer> first;
    public Set<Integer> second;
   
    /*
    * A CubePair represents a pair of sets of digits
    * There need not be six digits in each set
    * i.e. it could be an "incomplete" cube pair where all the sides haven't been filled in yet)
    *
    * We're using Set<Integer> to represent a cube
    */
    public CubePair(Set<Integer> first, Set<Integer> second) {
        this.first = first;
        this.second = second;
    }
   
    public static CubePair emptyCubePair() {
        return new CubePair(new HashSet<Integer>(),new HashSet<Integer>());
    }
   
    /*
    * If A and B are two cubes,
    * we're counting (A,B) and (B,A) as distinct pairs.
    */
    public boolean equals(CubePair o) {
        return first.equals(o.first) && second.equals(o.second);
        // Use this code if you want to count (A,B) the same as (B,A)
        // return (first.equals(o.first) && second.equals(o.second)) || (first.equals(o.second) && second.equals(o.first));
    }
   
   
    // Return the set of supercubes of a cube
    // A supercube of a cube is a complete cube (all six sides filled in)
    // that contains all the numbers on the original cube.
    // If the cube already has six sides filled in, just return the set containing that cube only.
    public static Set<Set<Integer>> superCubes(Set<Integer> cube) {
        Set<Set<Integer>> result = new HashSet<Set<Integer>>();
        if (cube.size() > 6) {
            return result;
        }
        if (cube.size() == 6) {
            result.add(cube);
            return result;
        }
        for (int x : DIGITS) {
            if (!cube.contains(x)) {
                Set<Integer> newCube = new HashSet<Integer>(cube);
                newCube.add(x);
                result.addAll(superCubes(newCube));
            }
        }
        return result;
    }
   
   
    // Given a cube pair (A,B)
    // return a set of all cube pairs consisting of supercubes of A paired with supercubes of B
    public Set<CubePair> superCubePairs() {
        Set<CubePair> results = new HashSet<CubePair>();
        for (Set<Integer> cube1 : superCubes(first)) {
            for (Set<Integer> cube2 : superCubes(second)) {
                results.add(new CubePair(cube1,cube2));
            }
        }
                   
        return results;
    }
   
    // If a cube has a 6, return a cube with a 9 substituted for the 6.
    public static Set<Integer> flip(Set<Integer> cube) {
        Set<Integer> result = new HashSet<Integer>(cube);
        if (cube.contains(6)) {
            result.remove(6);
            result.add(9);
        }
        return result;
    }
   
   
   
    public String toString() {
        return cubeString(first) + ", "+cubeString(second);
    }
   
    // Return a String representation of a cube
    public static String cubeString(Set<Integer> cube) {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (Integer x : cube) sb.append(x+",");
        sb.append("}");
        return sb.toString();
    }
   
    /*Recursive method to generate sets of cube pairs that can produce the square numbers up to and including index lastDie
    * so for instance if lastDie == 2 then generateCombos will generate sets of cube pairs that can produce the first three squares
    * The cube pairs will contain incomplete cubes.
    * What we do is take each square and assign the first digit to one cube and the second to the other.
    * We find all possible ways of assigning the digits of the squares to the cubes.
    * At this point we are not concerned with filling in the remaining sides of the cubes that haven't been assigned digits.
    */
    public static Set<CubePair> generateCombos(int[][] squares, int lastDie) {
        Set<CubePair> result = new HashSet<CubePair>();
        // Base case
        if (lastDie < 0) {
            result.add(emptyCubePair());
            return result;
        }
       
        for (CubePair pair : generateCombos(squares, lastDie-1)) {
            Set<Integer> newFirst1 = new HashSet<Integer>(pair.first);
            Set<Integer> newSecond1 = new HashSet<Integer>(pair.second);
            Set<Integer> newFirst2 = new HashSet<Integer>(pair.first);
            Set<Integer> newSecond2 = new HashSet<Integer>(pair.second);
            newFirst1.add(squares[lastDie][0]);
            newSecond1.add(squares[lastDie][1]);
            newFirst2.add(squares[lastDie][1]);
            newSecond2.add(squares[lastDie][0]);
            result.add(new CubePair(newFirst1,newSecond1));
            result.add(new CubePair(newFirst2,newSecond2));
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] squares = new int[][] {
                {0,1},
                {0,4},
                {0,6},
                {1,6},
                {2,5},
                {3,6},
                {4,6},
                {8,1}
        };
        Set<CubePair> temp = generateCombos(squares,squares.length-1);
        Set<CubePair> temp2 = new HashSet<CubePair>();
       
        // Add in cubes with 9's used instead of 6's
        for (CubePair pair : temp) {
            temp2.add(pair);
            temp2.add(new CubePair(flip(pair.first),flip(pair.second)));
            temp2.add(new CubePair(flip(pair.first),pair.second));
            temp2.add(new CubePair(pair.first,flip(pair.second)));
        }
       
        // Fill in the sides of the cubes that haven't yet been assigned digits
        Set<CubePair> result = new HashSet<CubePair>();
        for (CubePair pair : temp2) {
            result.addAll(pair.superCubePairs());
        }
       
        for (CubePair pair : result) {
            System.out.println(pair);
        }
        System.out.println("Grand total: "+result.size());
    }

}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.