Enigmatic Code

Programming Enigma Puzzles

Enigma 1669: Coloured bricks

From New Scientist #2835, 22nd October 2011 [link]

My daughter has 10 equal-sized coloured bricks. Each is cubic, and has opposite faces of the same colour. The three pairs of opposite faces on each are as follows:

Brick 1: yellow, green, red

Brick 2: blue, green, green

Brick 3: yellow, green, white

Brick 4: blue, yellow, white

Brick 5: green, red, white

Brick 6: yellow, yellow, green

Brick 7: yellow, red, white

Brick 8: blue, green, white

Brick 9: blue, yellow, green

Brick 10: blue, blue, yellow

My daughter arranged nine of the bricks in a tight 3×3 square on the carpet and hid the 10th. The visible face of the centre brick was red, no white faces were visible, and the number of visible blue faces, yellow faces and green faces was the same. By studying the visible faces, but without moving the arrangement, I could deduce which was the hidden brick.

Which brick was hidden?

[enigma1669]

Advertisements

15 responses to “Enigma 1669: Coloured bricks

  1. Jim Randell 2 December 2011 at 4:53 pm

    This was a fun challenge.

    The following Python program runs in 36ms.

    # there are 6B, 8Y, 8G, 3R, 5W
    # the only combination of visible faces is: 6B, 6Y, 6G, 3R, 0W
    # so all B and R faces are visible
    # so the only possibilities for the missing cube are: YGW or YYG
    
    from collections import defaultdict
    
    cubes = set(('YRG', 'BGG', 'YGW', 'BYW', 'GRW', 'YYG', 'YRW', 'BGW', 'BYG', 'BBY'))
    
    soln = defaultdict(set)
    
    def solve(missing, cubes):
      # partition the cubes into corners (4), edges (4), centre (1)
      # so we have: 6B 6Y 6G 3R 0W
    
      # centre square is red
      for centre in cubes:
        if not 'R' in centre: continue
        cubes2 = cubes.difference([centre])
        # all whites must be hidden (so must be on edges)
        edges = [(x.strip('W'), x) for x in cubes2 if 'W' in x]
        if len(edges) > 4: continue
        solve2(missing, cubes2.difference([x[1] for x in edges]), ('R', centre), edges)
    
    
    def solve2(missing, cubes, centre, edges):
      if len(edges) == 4:
        # the remaining cubes are corners
        corners = [(x, x) for x in cubes]
        used = [centre] + edges + corners
        visible = '/'.join(sorted((''.join(sorted(x[0])) for x in used), key=lambda x: (len(x), x)))
        if [visible.count(x) for x in 'BYGRW'] != [6, 6, 6, 3, 0]: return
        soln[visible].add(missing)
    
      elif len(edges) < 4:
        # we need more edges
        for x in cubes:
          for e in set((x[0:2], x[0:3:2], x[1:3])):
            solve2(missing, cubes.difference([x]), centre, edges + [(e, x)])
    
    for missing in cubes:
      solve(missing, cubes.difference([missing]))
    
    for k in sorted(soln.keys()):
      print("{} => {}".format(k, soln[k]))
    

    Solution: The missing brick is #3 (yellow, green, white).

  2. saracogluahmet 24 June 2013 at 9:02 am
    #There are some constraints given in the enigma
    
    #1- There are 21 visible faces, and one of them is given as red
    
    #2- The count of visible faces of yellow,green,blue squares are same,
    #so, there must be 3 visible red faces to satisfy the number 2.
    
    #This means that the hidden cube can not be 1,5,7 cubes as they have red faces.
    
    #No visible white faces, this does mean, since the cubes at the corners of the
    
    #square each have 3 faces visible, then they can not be cubes which have white faces.
    
    #That is: 3,4,5,7,8 cubes can not be at the corners.
    
    # 4 of (1,2,6,9,10) cubes must be at the corners as there are 4 corners in the square.
    
    # Red=1,Green=2,Blue=3,White=4,Yellow=5
         #R #G #B #W #Y  
    #First 1-5 columns show the count of colours and the other 4 columns do the cubes
    #[0, 2, 2, 1, 4, 3, 3, 4, 5, 7]---->Here, 3,4,5,7 numbered cubes are used...
    #[0, 1, 3, 2, 4, 2, 3, 4, 5, 8]
    #[0, 1, 2, 2, 4, 3, 3, 4, 7, 8]
    #[0, 2, 3, 1, 4, 2, 3, 5, 7, 8]
    #[0, 2, 2, 2, 4, 2, 4, 5, 7, 8]
    
    import time
    print(time.time())
    import itertools
    
    # cube 1, [5,1,2] this means, The cube has visible faces (Yellow,Red,Green)
    cubes=[[0,0,0],[5,1,2],[3,2,2],[5,2,4],[3,5,4],[2,1,4],[5,5,2],[5,1,4],[3,2,4],[3,5,2],[3,3,5]]
    
    CCubes=list(itertools.combinations([1,2,6,9,10],4))
    ICubes=list(itertools.combinations([3,4,5,7,8],4))
    
    
    def Solve(C):
        counter=[[0]*10 for i in range(5)]
        for i in range(len(C)):
            items=C[i]
            for j in range(4):
                index=items[j]
                counter[i][j+6]=index
                for k in range(3):
                    counter[i][cubes[index][k]]+=1
                    
        return counter
            
            
    def FindHidden():
        CornerCubes=Solve(CCubes)
        InnerCubes=Solve(ICubes)
        
        count=0
    
        
        Sums=[[0]*6 for i in range(25)]
    
        for i in range(5):
            for j in range(5):
                for k in range(1,6):
                    Sums[count][k]=CornerCubes[i][k]+InnerCubes[j][k]
                if Sums[count][1]==2 and Sums[count][2]==6 and Sums[count][3]==6 and Sums[count][5]==6:
                    if (5) in InnerCubes[j]:
                        print(CornerCubes[i]) #[0, 0, 4, 4, 0, 4, 2, 6, 9, 10] #The middle square has number 1 cube and it has only one visible face and that is red.
                        print(InnerCubes[j])  #[0, 2, 2, 2, 4, 2, 4, 5, 7, 8] # numbered 3cube is hidden as not seen on this array
                        print(Sums[count])    #[0, 2, 6, 6, 4, 6] There must be 3 on the red face entry and that is 1 numbered face, and the others satisfy the constraint
                        return
                count+=1
                
    FindHidden()
    #The answer is 3.
    print(time.time())
    
  3. saracogluahmet 24 June 2013 at 10:33 am

    Hi Jim, You did classify this one in the notable enigmas, but I guess there are more notable ones in the ordinary ones, to my humble. I guess this one is really easy to code, however that is an enjoyable one.

    • Jim Randell 6 August 2013 at 10:52 am

      I marked this puzzle as a fun programming challenge because I found it required some thought before you start programming also it requires you construct a non-trivial program to find the possible arrangements of the cubes and then deduce the answer. Of course (as with most Enigmas) you can do a fully analytic solution on a piece of paper, so there’s a balance between how much you work out yourself and how much you let the computer work out.

      I’m sorry if you didn’t find it an interesting challenge, but I’ve looked through your code and I’m not sure you’ve fully grasped the problem. For instance it seems that your program only finds one way of arranging the cubes, and declares that as the answer, and also requires that brick 5 is placed in an edge position, which I don’t see explained and also isn’t actually true. Just a couple of hints if you want to look at it again.

      • saracogluahmet 6 August 2013 at 10:59 am

        Ohhh Jim hi,
        I did write it on the 24th June, and today is 6th August. I really do not remember the puzzle and how to construct the algorithm.

        But my code finds the result satisfying the condition given in the puzzle, and I did not say that the puzzle had not been interesting, how did you derive that? I just had said that it had been easy, furthermore this is my opinion.

        You may think different.. 🙂

        if you wish, you can delete my code, you know.

        • Jim Randell 6 August 2013 at 11:11 am

          Yes, sorry it took a while to get around to looking at your code – I had to get back into the problem myself (I put it up in 2011), and it took some time to work out what your code was doing. But I thought it was polite to try and understand your code as you’d gone to the trouble of putting it on the site.

          I mark the puzzles I’ve found to be a fun programming challenge in the Notable Enigmas list, and this was one that I remember finding fun at the time (I did it before I created this site, although only a few weeks before). And as your program doesn’t really solve the problem I think it is probably more challenging than you originally thought too.

          If you want me to remove your program I will.

          • saracogluahmet 6 August 2013 at 11:18 am

            Ok, I have to remember the problem and I can have a look at one more in my free time, I have so much time nowadays, I wish you had said your opinion when I had uploaded it on your site, as I said time has passed, and I have to remember and sure if some thing has to be changed, I will change and if that does not require any changes, I will explain my algorithm and/or approach.

  4. saracogluahmet 6 August 2013 at 11:02 am

    “Which brick was hidden?”

    The question is above. 🙂

  5. saracogluahmet 6 August 2013 at 11:28 am

    what is the lack of the code? what did I miss? would you explain it clearly?

    • saracogluahmet 6 August 2013 at 11:56 am

      I have read one more, I guess You did say this, there was more paper work than what the code was supposed to do, almost it was solved on the paper,.

      Then, I will code it from the scratch and you need not to delete the previous one.

      • Jim Randell 7 August 2013 at 9:23 am

        If you need a hint, read on…

        The first part of the problem describes the arrangement of the cubes, but the key phrase in the question is: “By studying the visible faces, but without moving the arrangement, I could deduce which was the hidden brick”. This implies that there are multiple ways of arranging the cubes to satisfy the first part of the problem, with different cubes missing from the arrangement. So finding an arrangement that satisfies the first part of the problem is only part of the solution. We need to find all possible arrangements and then eliminate those where we can’t tell which cube is missing from the arrangement by inspecting the visible faces. If the puzzle is well set this will leave us with a single possibility for the missing cube.

        Although I did solve the puzzle manually, the program I present above doesn’t use any additional analysis. (Although the runtime of the program would be shorter if I only considered the two possible missing cubes). It constructs the possible arrangements that satisfy the conditions of the square and shows which arrangements have which missing cube. One of the arrangements cannot occur, because we can’t tell which cube is missing from it, but all the other arrangements have the same cube missing from them. So, although we don’t know which arrangement was made, we can say what the missing cube is.

  6. saracogluahmet 19 February 2015 at 9:05 am

    I remember that I should correct the code for all possible combinations, almost a year has passed, anyway;

    
    
    import itertools as C
    
    PossibleCorners,PossibleInnerCorners=[0,1,5,8,9],range(10)
    
    CornersSpace,InnerCornersSpace=list(C.combinations(PossibleCorners,4)),list(C.combinations(PossibleInnerCorners,4))
    
    #0=Yellow,1=Green,2=Red,3=Blue,4=White
    bricks,colors=[[0,1,2],[3,1,1],[0,1,4],[3,0,4],[1,2,4],[0,0,1],[0,2,4],[3,1,4],[3,0,1],[3,3,0]],[[] for i in range(10)] 
    
    setcenter={0,4,6}
    
    def AddColor(ls,cols,rng):
        for i in range(len(ls)):
            for j in range(rng):
                color=bricks[ls[i]][j]
                cols[color]+=1
            
    def PossibleConfiguration():
        for Corners in CornersSpace:
            corners=set(Corners)
            for Edges in InnerCornersSpace:
                edges=set(Edges)
                if len(set.intersection(corners,edges))==0:
                    ucornersedges=set.union(corners,edges);center=set.intersection(ucornersedges,setcenter)
                    if len(center)!=3:
                     colors=[0]*4
                     AddColor(list(corners),colors,3),AddColor(list(edges),colors,2)
                     colorset={colors[0],colors[1],colors[3]}
                     if len(colorset)==1 and 6 in colorset:
                         centerbrick=setcenter.difference(center)
                         print("Colors=",colors,"Corners=",corners,"Edges=",edges,"Center=",centerbrick,"Hidden=",set(PossibleInnerCorners).difference(set.union(centerbrick,ucornersedges)))
                         # For example, one of the possible output,
                         # Colors= [6, 6, 2, 6] Corners= {0, 1, 5, 8} Edges= {9, 3, 6, 7} Center= {4} Hidden= {2}
                         # 0 denotes the first brick.
                         
                     
    PossibleConfiguration()
    
    • Jim Randell 19 February 2015 at 3:54 pm

      If your program is looking for possible assignments of the bricks for the centre, edge and corner positions, then it should find 10 possible arrangements, not 6.

      Using the brick numbers to indicate the arrangements as “(<missing>) <centre> + <edges> + <corners>” and the colours to show the visible faces, they are as follows:

      A1: (3) 5 + 10,8,4,7 + 2,9,1,6 = R + BB,BG, BY,RY + BGG,BGY,GRY,GYY [V1]
      A2: (3) 5 + 8,9,4,7 + 10,2,1,6 = R + BG,BG,BY,RY + BBY,BGG,GRY,GYY [V3]
      A3: (6) 5 + 8,4,3,7 + 10,2,9,1 = R + BG,BY,GY,RY + BBY,BGG,BGY,GRY [V7]
      A4: (3) 5 + 8,4,1,7 + 10,2,9,6 = R + BG,BY,GR,RY + BBY,BGG,BGY,GYY [V5]
      A5: (3) 5 + 8,4,7,6 + 10,2,9,1 = R + BG,BY,GY,RY + BBY,BGG,BGY,GRY [V7]
      A6: (3) 1 + 8,4,5,7 + 10,2,9,6 = R + BG,BY,GR,RY + BBY,BGG,BGY,GYY [V5]
      A7: (3) 7 + 2,8,4,5 + 10,9,1,6 = R + BG,BG,BY,RY + BBY,BGY,GRY,GYY [V2]
      A8: (3) 7 + 8,9,4,5 + 10,2,1,6 = R + BG,BY,BY,GR + BBY,BGG, GRY,GYY [V4]
      A9: (3) 7 + 8,4,5,1 + 10,2,9,6 = R + BG,BY,GR,RY + BBY,BGG,BGY,GYY [V5]
      A10: (3) 7 + 8,4,5,6 + 10,2,9,1 = R + BG,BY,GR,YY + BBY,BGG,BGY,GRY [V6]

      Your program seems to be missing A2, A4, A5 and A9. Which stops you being able to find a solution.

      Once you find the full set of arrangements you can see that if any of the visible patterns V1, V2, V3, V4 or V6 occur, then we can immediately identify which arrangement is being used (as the visible patterns are unique), and they all correspond to brick 3 being missing (only A3 corresponds to a brick other than 3 being missing).

      The remaining visible patterns, which correspond to more than one arrangement are V5 and V7.

      V5 corresponds to arrangements A4, A6 and A9, each of these arrangements has brick 3 missing, so if we were to see the visible pattern V5 we would also know that brick 3 was missing.

      Which leaves us with V7. This corresponds to the arrangements A3 and A5. But A3 is missing brick 6 and A5 is missing brick 3. So if we were to see V7 we would not know which brick is missing.

      However the puzzle tells us that from the visible pattern we can tell which brick is missing. So we cannot be confronted with V7.

      We could, however, be confronted with any of the other visible patterns (V1, V2, V3, V4, V5, V6), but all the arrangements that correspond to these patterns have brick 3 missing. So the answer to the puzzle is that brick 3 must be missing. But we don’t know what the visible pattern is (it could be any of the 6 patterns V1, V2, V3, V4, V5, V6, but not V7), and we don’t know what the corresponding arrangement of bricks is (it could be any of the 8 arrangements A1, A2, A4, A6, A7, A8, A9, A10, but not A3 or A5).

      • Brian Gladman 19 February 2015 at 10:23 pm

        My version gives the same answer as Jim’s above:

        from itertools import combinations
        from collections import defaultdict
        
        cubes = set(( 
              ('Yellow', 'Green', 'Red'),   ('Blue', 'Green', 'Green'), 
              ('Yellow', 'Green', 'White'), ('Blue', 'Yellow', 'White'), 
              ('Green', 'Red', 'White'),    ('Yellow', 'Yellow', 'Green'),
              ('Yellow', 'Red', 'White'),   ('Blue', 'Green', 'White'), 
              ('Blue', 'Yellow', 'Green'),  ('Blue', 'Blue', 'Yellow') ))
        
        whites = set(x for x in cubes if 'White' in x)
        
        # for collecting missing cubes indexed on visible faces
        d = defaultdict(set)
        
        # pick four corner cubes (which cannot include white faces)
        r0 = set(x for x in cubes if 'White' not in x)
        for corners in combinations(r0, 4):
          
          # find the single cube without a white face that has not been used
          extra, = set(x for x in r0 if x not in corners)
          
          # choose its non-visible face and put it last
          for i, hidden in enumerate(extra):
            faces = tuple(x for j, x in enumerate(extra) if j != i) + (hidden,) 
            
            # pick four edge cubes
            for edges in combinations(whites.union([faces]), 4):
              
              # collect all visible faces on the corner and edge cubes
              visible = corners + tuple((a, b) for a, b, c in edges)
              # count the numbers of blue, green and yellow faces
              colours = tuple(y for x in visible for y in x)
              cnt = tuple(colours.count(c) for c in ('Blue', 'Green', 'Yellow'))
              # which must all be the same
              if cnt[0] == cnt[1] == cnt[2]:
                
                # now find the cubes that have not been used        
                edge_cubes = set(edges)
                if faces in edge_cubes: 
                  edge_cubes = edge_cubes.difference([faces]).union([extra])  
                r = tuple(cubes.difference(corners).difference(edge_cubes))
                
                # one must contain a red face and the other is the hidden cube
                for red, hidden in (x for x in (r, r[::-1]) if 'Red' in x[0]):
                  d[tuple(sorted(visible))].update([hidden])
        
        # find a set of visible faces that uniquely identifies the hidden cube
        for hidden in set(min(h) for h in d.values() if len(h) == 1):
          print('The hidden cube is', hidden)
        
        • saracogluahmet 20 February 2015 at 1:48 pm

          I agree with You.

          
          
          import itertools as C
          
          PossibleCorners,PossibleInnerCorners=[0,1,5,8,9],range(10)
          
          CornersSpace,InnerCornersSpace=list(C.combinations(PossibleCorners,4)),list(C.combinations(PossibleInnerCorners,4))
          
          #0=Yellow,1=Green,2=Red,3=Blue,4=White
          bricks=[[0,1,2],[3,1,1],[0,1,4],[3,0,4],[1,2,4],[0,0,1],[0,2,4],[3,1,4],[3,0,1],[3,3,0]]
          
          setcenter={0,4,6}
          
          def AddColorCorner(ls,cols):
              for brick in ls:
                  
                  for j in [0,1,2]:
                      color=bricks[brick][j]
                      cols[color]+=1
          
          def AddColorEdge(ls,cols,items,pat):
              
              
              for brick in ls:
                  if brick not in [0,1,5,8,9]:
                      rng=[0,1]
                  else:
                      rng=items
          
                  t=[]
                  for j in rng:
                      color=bricks[brick][j]
                      cols[color]+=1
                      
                      t.append(color)
                  
                  pat.append(tuple(t))
                      
              
                      
          def AddCornersPattern(Crns,pat):
              
              for brick in Crns:
                  t=[]
                  for color in bricks[brick]:
                      t.append(color)
                  pat.append(tuple(t))
                  
          
          
          
          def PossibleConfiguration():
              
              config,patterns,Index=[],[],0
              twos=list(C.combinations([0,1,2],2))
              
              for Corners in CornersSpace:
                  corners=set(Corners)
                  for Edges in InnerCornersSpace:
                      edges=set(Edges)
                      if len(set.intersection(corners,edges))==0:
                          ucornersedges=set.union(corners,edges);center=set.intersection(ucornersedges,setcenter)
                          if len(center)!=3:
                             
                              colors=[0]*4
                              AddColorCorner(list(corners),colors)
                              
                              for items in twos:
                                  
                                  tempcolors,pattern=[0]*4,[]
                                  AddColorEdge(list(edges),tempcolors,items,pattern)
                                  colorset={colors[0]+tempcolors[0],colors[1]+tempcolors[1],colors[3]+tempcolors[3]}
                                  
                                  if len(colorset)==1 and 6 in colorset:
                                      centerbrick=setcenter.difference(center)
                                      lcenter,hidden=list(centerbrick),set(PossibleInnerCorners).difference(set.union(centerbrick,ucornersedges))
                                      set1=[corners,edges,centerbrick,hidden]
          
                                      if set1 not in config:
                                          config.append(set1)
                                          #print("Colors=",colors+tempcolors,"Corners=",corners,"Edges=",edges,"Center=",centerbrick,"Hidden=",set(PossibleInnerCorners).difference(set.union(centerbrick,ucornersedges)))
                                          AddCornersPattern(Corners,pattern)
                                          print("Index=",Index,"Patterns=",pattern,"Corners=",Corners,"Edges=",Edges,"Center=",lcenter,"Hidden=",hidden)
                                          patterns.append(pattern)
                                          Index+=1
              
          
              
          
              for i in range(len(config)-1):
                  hidden,setpattern1=config[i][3],set(patterns[i])
                  for j in range(i+1,len(config)):
                      hidden1=config[j][3]
                      if hidden!=hidden1:
                          if len(set.intersection(setpattern1,set(patterns[j])))==len(setpattern1):
                              print("Impossible Configuration with Index=",i,"Then Hidden Brick=",hidden1.pop()+1)
                          
                      
                          
                      
                      
                                                  
                  
          PossibleConfiguration()
                      
            

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: