Enigmatic Code

Programming Enigma Puzzles

Enigma 1696: Leftovers

From New Scientist #2863, 5th May 2012 [link]

A set of snooker balls contains six coloured and 15 red balls. From such a set Harry took some coloured balls and a larger number of reds and put them in his bag. From the remainder Tom took some coloured balls and some reds (more of each than Harry took) and put them into his bag.

Each of them calculated that if he drew two balls at random out of his own bag simultaneously there was a 1 in X chance that they would both be coloured, X representing the same number for each person.

How many coloured balls and how many red balls from the set were not taken by either of them?

This is probably the same Harry and Tom from Enigma 1551.

[enigma1696]

Advertisements

10 responses to “Enigma 1696: Leftovers

  1. Jim Randell 2 May 2012 at 8:12 pm

    The following Python program runs in 40ms. You can write the same program without using objects, but I thought this would be a bit more readable. (Or I could have used the Python namedtuple library).

    from collections import defaultdict
    from itertools import permutations
    from enigma import irange, printf, sprintf
    
    # a (<colour>, <red>) pair count
    class Pair(object):
      def __init__(self, c, r):
        (self.c, self.r) = (c, r)
      def __str__(self):
        return sprintf("{self.c}c{self.r}r")
    
    # collect (<colour>, <red>) pairs with a 1/x chance of drawing 2 coloured
    xs = defaultdict(list)
    for c in irange(2, 6):
      for r in irange(3, 15):
        n = c * (c - 1)
        d = (r + c) * (r + c - 1)
        (x, y) = divmod(d, n)
        if y > 0: continue
        xs[x].append(Pair(c, r))
    
    # find two different pairs with the same x
    for (k, v) in xs.items():
      if len(v) < 2: continue
      for (H, T) in permutations(v, 2):
        # check the conditions on the pairs
        if not(H.c < T.c and H.c < H.r < T.r): continue
        # and how many balls are remaining?
        R = Pair(6 - (H.c + T.c), 15 - (H.r + T.r))
        if R.c < 0 or R.r < 0: continue
        printf("R={R} [X={k} H={H} T={T}]")
    

    Solution: 1 coloured ball and 4 red balls were not taken.

  2. arthurvause 2 May 2012 at 11:05 pm
    for ch in range(2,4):
      for rh in range(ch+1,8):
          for ct in range(ch+1,7-ch):
              for rt in range(rh+1,16-rh):
                  if ch*(ch-1)*(ct+rt)*(ct+rt-1) == ct*(ct-1)*(ch+rh)*(ch+rh-1):
                      print ch,rh,ct,rt
    

    30ms run time

    • arthurvause 2 May 2012 at 11:30 pm

      Of course, it’s easy to deduce that ch (the number of coloured balls taken be Harry) is 2 : it has to be more than 1 to allow the selection of 2 coloured balls, and less than 3 as Tom takes more coloured balls than Harry, so

      ch=2
      for rh in range(ch+1,8):
          for ct in range(ch+1,7-ch):
              for rt in range(rh+1,16-rh):
                  if ch*(ch-1)*(ct+rt)*(ct+rt-1) == ct*(ct-1)*(ch+rh)*(ch+rh-1):
                      print ch,rh,ct,rt
      

      25ms run time

      • Jim Randell 3 May 2012 at 9:26 am

        This is very similar to (but more compact than) the solution I originally came up with. Although I also tested X to check it was an integer value (which I feel was subtly implied in the puzzle, rather than explicitly stated), although as it turns out there are no non-integer solutions for X anyway.

        from enigma import irange, printf
        
        # compute a 1/X chance of drawing 2 coloured balls from r reds and c coloureds
        def X(r, c):
          n = c * (c - 1)
          d = (r + c) * (r + c - 1)
          # we need X to be an integer value
          (x, y) = divmod(d, n)
          return (x if y == 0 else None)
        
        for Hc in irange(2, 2):
          for Hr in irange(Hc + 1, 7):
            Hx = X(Hr, Hc)
            if Hx is None: continue
        
            for Tc in irange(Hc + 1, 6 - Hc):
              for Tr in irange(Hr + 1, 15 - Hr):
                Tx = X(Tr, Tc)
                if Tx is None or Tx != Hx: continue
                
                printf("R={Rc}c{Rr}r [H={Hc}c{Hr}r X={Hx} / T={Tc}c{Tr}r X={Tx}]", Rc=6 - (Hc + Tc), Rr=15 - (Hr + Tr))
        
  3. Brian Gladman 3 May 2012 at 8:38 am

    An issue that often arises in providing programs to solve teasers is that of deciding how much prior analysis should be exploited in the programmed solution.

    In this case, for example, it is easy to see that Harry can only pick two of the ‘coloured’ balls, a constraint that gives a large speed gain in a program when compared with an unconstrained search.

    Going a bit further with the analysis also provides a complete solution which then reduces to a few lines of Python.

    • Jim Randell 3 May 2012 at 9:35 am

      Indeed. The Enigma Puzzle this week is not a great programming challenge.

      But in cases like this where the search space is sufficiently small I feel most satisfied by a fully exhaustive search. I tried to come up with a more interesting programmed solution in my first post by approaching the puzzle from a slightly different angle (finding possible pairs for X and then applying the constraints, rather than starting with the constraints), and also playing around with objects to make the printing of the solution easier.

      • arthurvause 3 May 2012 at 11:06 am

        Agreed. The coding of the first line caused me a dilemma, as knowing that Harry takes at least 2 coloured balls,and less than half the coloured balls could be coded as
        for ch in range(2,3):, which might as well be replaced by ch=2

        Anyway, here is an alternative coding in SQL, run on an SQlite database in 2.7ms. (The table “numbers” contains the set of natural numbers > 0 )

        select Ch.n, Rh.n, Ct.n, Rt.n
        from 
        (select * from numbers where n<3) Ch
        ,(select * from numbers where n<8) Rh
        ,(select * from numbers where n<=6) Ct
        ,(select * from numbers where n<=15) Rt
        where
         Ch.n < Rh.n
         and Ch.n < Ct.n
         and Rh.n < Rt.n
         and Ch.n*(Ch.n-1)*(Ct.n+Rt.n)*(Ct.n+Rt.n-1) = Ct.n*(Ct.n-1)*(Ch.n+Rh.n)*(Ch.n+Rh.n-1)
         ;
        
        • Jim Randell 9 May 2012 at 8:31 am

          That’s neat. I’ve had some exposure to SQL in the past, and it wouldn’t leap out as the first language I’d chose to implement Enigma puzzles!

          Here’s my solution in BBC Basic (running under the BeebEm3 emulator):

          > LIST
             10 start% = TIME
             20 FOR Hc% = 2 TO 2
             30   FOR Hr% = Hc% + 1 TO 7
             40     Hx% = FNx(Hr%, Hc%)
             50     IF Hx% = 0 THEN GOTO 140
             60     FOR Tc% = Hc% + 1 TO 6 - Hc%
             70       FOR Tr% = Hr% + 1 TO 15 - Hr%
             80         Tx% = FNx(Tr%, Tc%)
             90         IF Tx% = 0 THEN GOTO 120
            100         IF Tx% <> Hx% THEN GOTO 120
            110         PRINT "R=";6 - Hc% - Tc%;"c";15 - Hr% - Tr%;"r (H=";Hc%;"c";Hr%;"r X=";Hx%;" / T=";Tc%;"c";Tr%;"r X=";Tx%;")"
            120       NEXT Tr%
            130     NEXT Tc%
            140   NEXT Hr%
            150 NEXT Hc%
            160 PRINT "Time = ";(TIME - start%) / 100;"s"
            170 END
            180 DEF FNx(r%, c%)
            185   LOCAL n%, d%
            190   n% = c% * (c% - 1)
            200   d% = (r% + c%) * (r% + c% - 1)
            210   IF d% MOD n% = 0 THEN =d% DIV n% ELSE =0
          
          >RUN
          R=1c4r (H=2c4r X=15 / T=3c7r X=15)
          Time = 0.93s
          
          • Hugh Casement 11 April 2016 at 3:01 pm

            Having been potty-trained on Fortran, I usually start my Basic programs with
            defint i – n
            Then if you choose your variable names accordingly you can do without those % symbols that don’t exactly improve the readability of a program.  Turbo Basic also allows long integers of 32 bits.
            And it does away with line numbers.  A label can be any name starting with a letter(presumably not a reserved word or a name in use as a variable) followed by a colon and on a line by itself.  That’s neater than numbering every line: those early dialects of Basic were basically horrid!
            I’m not intending to publish any of my programs here, as I’m not particularly proud of them.  They’re much longer than the Python equivalent, and I’m sure take longer to run.  This old dog is not going to learn new tricks, but he usually gets there in the end.

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: