MindCipher

May 10, 2013

According to their masthead, the MindCipher website is “a social repository of the world’s greatest brain teasers, logic puzzles and mental challenges.” Some of the problems lend themselves to brute force computation, others are better solved with pencil-and-paper or solely with mental effort. We look at three MindCipher exercises today.

1: Coin Flip: On Monday, you flip a coin all day. You start flipping it until you see the pattern Head, Tail, Head. You record the number of flips required to reach this pattern, and start flipping again (and counting up from 1 again) until you see that pattern again, you record the second number, and start again. At the end of the day you average all of the numbers you’ve recorded. On Tuesday you do the EXACT same thing except you flip until you see the pattern Head, Tail, Tail.

Will Monday’s number be higher than Tuesday’s, equal to Tuesday’s, or lower than Tuesday’s?

2: 1978: The year 1978 is such that the sum of the first two digits and the latter two digits is equal to the middle two digits, i.e. 19 + 78 = 97. What is the next year (after 1978) for which this is true?

3: Sum of Two Prime Numbers: If p, q > 2 are consecutive in set of primes. Since p,q can only be odd number, (p+q) is an even number.

Can (p+q)/2 be prime?

Your task is to solve the three problems given above; write a computer program to help you if you wish. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

20 Responses to “MindCipher”

  1. […] today’s Programming Praxis exercise, our goal is to solve two exercises from the MindCipher website […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/10/programming-praxis-mindcipher/ for a version with comments):

    import Control.Monad
    import Data.List
    import System.Random
    
    flipUntil :: [Bool] -> IO Int
    flipUntil pattern = fmap (length . takeWhile (not . isPrefixOf pattern) .
                        tails . randomRs (False, True)) newStdGen
    
    day :: [Bool] -> IO Double
    day pattern = fmap (\cs -> fromIntegral (sum cs) / fromIntegral (length cs)) .
                  replicateM 10000 $ flipUntil pattern
    
    sumDay :: Maybe Integer
    sumDay = find (\d -> div d 100 + mod d 100 == div (mod d 1000) 10) [1979..]
    
    main :: IO ()
    main = do print =<< liftM2 compare (day [False, True, False])
                                       (day [False, True, True])
              print sumDay
    
  3. eupraxia said
    # if p and q are consecutive prime numbers then, since p<q,
    # p < (p+q)/2 < q => (p+q)/2 cannot be prime.
    
  4. OptimusPrime said

    Ans 2) 2307
    n = 1979
    while n<9999:
    if (n/100) + (n%100) == (n/10)%100:
    print n
    break

    n=n+1

  5. namako said

    1.’s most accurate answer is probably ‘there is no way to know’ (in fact, since one can only do something a finite number of times in a day, there’s a (tiny) nonzero chance you didn’t see the sequences at all on either day). However, we can get the average time until one sees any particular 3-element code using a Markov chain with 9 states.
    Source
    Mean time to hit TTT = 14
    Mean time to hit TTH = 8
    Mean time to hit THT = 10
    Mean time to hit THH = 8
    Mean time to hit HTT = 8
    Mean time to hit HTH = 10
    Mean time to hit HHT = 8
    Mean time to hit HHH = 14
    E(HTH) > E(HTT), so one would probably see Monday’s average as longer than Tuesday’s.

  6. wolvesatthedoor said

    here’s my solution to 1978 in python:

    for a in xrange(10):
      for b in xrange(10):
    	for c in xrange(10):
    	  for d in xrange(10):
    		if ((10*a) - (9*b) + (9*c) + d)== 0:
    		  y = int(str(a)+str(b)+str(c)+str(d))
    		  if y > 1978:
    			print y
    			exit(1)
    
  7. eupraxia said
    from random import choice
    from itertools import repeat
    from func_utils import repeatedly, partition
    
    def number_tosses(pattern):
        heads_tails = repeatedly(lambda: choice(['H', 'T']))
        triples = partition(heads_tails, 3, 1)
        indexed = enumerate(triples, 1)
        return next(i for (i, (t, t1, t2)) in indexed if (t, t1, t2)==pattern)
    
    patterns = [('T', 'T', 'T'), ('T', 'T', 'H'), ('T', 'H', 'T'),
                      ('T', 'H', 'H'), ('H', 'T', 'T'), ('H', 'T', 'H'),
                      ('H', 'H', 'T'), ('H', 'H', 'H')]
    
    for p in patterns:
        print p, sum(map(number_tosses, repeat(p, 1000000)))/1000000
    
    # ('T', 'T', 'T')  12.01629   ~= 12
    # ('T', 'T', 'H')  6.006479   ~=  6
    # ('T', 'H', 'T')  8.003555   ~=  8
    # ('T', 'H', 'H')  5.999449   ~=  6
    # ('H', 'T', 'T')  5.999335   ~=  6
    # ('H', 'T', 'H')  7.993025   ~=  8
    # ('H', 'H', 'T')  5.99461     ~=  6
    # ('H', 'H', 'H')  12.000927 ~= 12
    
    # This gives the same ordering as Namako ie.
    # TTH==THH==HTT==HHT < THT==HTH < TTT==HHH
    # but different ratios.
    
  8. namako said

    @eupraxia
    I’m not sure (not familiar with the language) but if you’re only counting triples, you’re missing the first two tosses. (It takes 3 to get a triple in the first place, which will be the first you test).

  9. eupraxia said

    @namako. Many thanks. You’re absolutely right, I should have started the count at three, not one.

    from random import choice
    from itertools import repeat
    from func_utils import repeatedly, partition
     
    def number_tosses(pattern):
        heads_tails = repeatedly(lambda: choice(['H', 'T']))
        triples = partition(heads_tails, 3, 1)
        # changed from: indexed = enumerate(triples, 1)
        indexed = enumerate(triples, 3)
        return next(i for (i, (t, t1, t2)) in indexed if (t, t1, t2)==pattern)
    
    for p in patterns:
         print p, sum(map(number_tosses, repeat(p, 1000000)))/1000000
    
    #('T', 'T', 'T') 14.018673
    #('T', 'T', 'H') 8.010297
    #('T', 'H', 'T') 10.008117
    #('T', 'H', 'H') 8.001807
    #('H', 'T', 'T') 8.006271
    #('H', 'T', 'H') 10.001372
    #('H', 'H', 'T') 8.006121
    #('H', 'H', 'H') 13.995327
    
    
    from random import choice
    from itertools import repeat
    
    def number_tosses(pattern):
        toss = lambda:choice(['H', 'T'])
        a, b, c = toss(), toss(), toss()
        # n = number of tosses so far
        n = 3
        while True:
            if (a, b, c)==pattern:
                return n
            a, b, c = b, c, toss()
            n+=1
    
    patterns = [('T', 'T', 'T'), ('T', 'T', 'H'), ('T', 'H', 'T'),
                ('T', 'H', 'H'), ('H', 'T', 'T'), ('H', 'T', 'H'),
                ('H', 'H', 'T'), ('H', 'H', 'H')]
    
    for p in patterns:
        print p, sum(map(number_tosses, repeat(p, 1000000)))/1000000
    
    #('T', 'T', 'T') 14.004905
    #('T', 'T', 'H') 7.999236
    #('T', 'H', 'T') 10.001018
    #('T', 'H', 'H') 8.006784
    #('H', 'T', 'T') 8.004825
    #('H', 'T', 'H') 10.002537
    #('H', 'H', 'T') 7.995162
    #('H', 'H', 'H') 13.99838
    
  10. aks said

    The coin tossing problem comparing the statistics on two different
    targets “HTH” versus “HTT” can be resolved with some logical
    analysis:

    Both targets are a specific permutation of three flips of a
    coin.

    Coin flipping continues until the target permutation occurs.

    After each coin flip that fails to create a matching
    permutation, one or none previous flips can be used as part
    of the permutation that includes the next flip.

    For the HTH target:

    A failing sequence of “HTT” requires at least three more
    tosses; none of the previous tosses can be used for a
    successfully matched permutation. e.g.: HTT{HTH}

    A failing sequence of “HH” requires two more tosses, because
    the second toss can be part of succesful matching sequence:
    H{HTH}.

    For the HTT target:

    A failing sequence of “HTH” can be successfully matched with
    two more tosses: “HT{HTT}”.

    A failing sequence of “HH” can be successfully matched with
    just two more tosses: “H{HTT}”.

    So, the number of tosses needed for a succesful match, including
    a random number of failing tosses is smaller for the “HTT”
    target than for the “HTH” target.

    I wrote a Ruby program to demonstrate the problem:

    https://gist.github.com/aks/5562771

    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #!/usr/bin/env ruby
    # coins.rb
    # count average flips until HTH is reached
    #
     
    def flip ; rand(2) == 1 ? 'H' : 'T' ; end
     
    # 'HTH'.count_flips
     
    class String
      def count_flips
        target = self.to_s
        src = ''
        count = 0
        while (target != src)   # loop until we match the target
          src += flip           # append new toss
          count += 1            # count flips
          src.slice!(0,1) if src.size > target.size
        end
        count                   # return flip count
      end
    end
     
    # Enumerable didn't include this -- why?
    class Array
      def sum 
        self.reduce(:+)
      end
      def average
        Float(self.sum) / self.nitems
      end
    end
     
    # average_flips
    # 
    # count coin flips until a target is reached
    # do this repeated for a day, then average those counts.
    # 
    # Simulate human-speed coin flips by estimating time for each flip, and
    # assuming constant flipping for 24 hours, without a break.
     
    $flip_time = 4    # 4 seconds per flip
    $max_flips_per_day = 24 * 60 * 60 / $flip_time
     
    class String
      def flip_stats
        target = self
     
        counts = []
        (1..$max_flips_per_day).each{|i| counts += [target.count_flips]}
        min_count, max_count = counts.minmax
        average_count = counts.average
        [min_count, max_count, average_count]
      end
    end
     
    ['HTH', 'HTT'].each {|target|
      puts "Computing #{target} stats.." if $DEBUG
      (min, max, avg) = target.flip_stats
      printf "Target: %s  Coin flip stats: min: %4.1f  max: %5.1f  avg: %5.1f\n", target, min, max, avg
    }
    exit
    
  11. aks said
    #!/usr/bin/env ruby
    # year-digits-sum.rb
    #
    # 1978: The year 1978 is such that the sum of the first two digits
    # and the latter two digits is equal to the middle two digits, i.e.
    # 19 + 78 = 97. What is the next year (after 1978) for which this is
    # true?
    # 
    #    a b c d
    #    1 9 7 8
    # 
    # Formula:
    # 
    #   [F1] a*10 + b + c*10 + d = b*10 + c
    # 
    #   [F2] a*10 - b*9 + c*9 + d = 0   ( Simplified )
    # 
    # Problem:
    # 
    #  Find Min(Year) such that [F2] is true.
    
    class Fixnum
      def find_next_year
        year = self.to_i
        while true do
          year += 1
          a, b, c, d = year.to_s.split(//).map{|c| c.to_i}
          if a*10 - b*9 + c*9 + d == 0
            return year
          end
        end
      end
    end
    
    puts "After 1978, the next year for which (ab) + (cd) = (bc) is.."
    puts 1978.find_next_year
    exit
    

    Here’s the run output:

    $ ./year-digits-sum.rb 
    After 1978, the next year for which (ab) + (cd) = (bc) is..
    2307
    
  12. aks said

    For the primes problem (#3), here is a J program to show that there are no primes in the set of (p+q)/2 where p,q are consecutive primes in the first million prime numbers.

    https://gist.github.com/aks/5563008

       i. 20
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
     
       NB. generate the first 20 primes
       p: i. 20
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
     
       NB. box up consecutive pairs of those primes
       (2 <\ ]) p: i. 20
    ┌───┬───┬───┬────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
    │2 3│3 5│5 7│7 11│11 13│13 17│17 19│19 23│23 29│29 31│31 37│37 41│41 43│43 47│47 53│53 59│59 61│61 67│67 71│
    └───┴───┴───┴────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
     
       NB. sum up each pair of primes
       +/ each (2 <\ ])p: i. 20
    ┌─┬─┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬───┬───┬───┬───┬───┐
    │5│8│12│18│24│30│36│42│52│60│68│78│84│90│100│112│120│128│138│
    └─┴─┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴───┴───┴───┴───┴───┘
     
       NB. divide each sum by 2
       2 %~ each +/ each (2 <\ ])p: i. 20                                                                                                                          
    ┌───┬─┬─┬─┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
    │2.5│4│6│9│12│15│18│21│26│30│34│39│42│45│50│56│60│64│69│
    └───┴─┴─┴─┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
     
       NB. now, test each of those results for being prime.  1 p: y -- tests y for being prime
     
       1&p: each 2 %~ each +/ each (2 <\ ])p: i. 20                                                                                                                
    ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
    │0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│
    └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
     
       NB. open the boxed results, so we can add them up
       >1&p: each 2 %~ each +/ each (2 <\ ])p: i. 20
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     
       NB. sum/reduce the vector of booleans.  If there's a prime, the sum will be > 0
       +/>1&p: each 2 %~ each +/ each (2 <\ ])p: i. 20
    0
     
       NB. ok. No primes.  Let's keep checking for larger groups
     
       +/>1&p: each 2 %~ each +/ each (2 <\ ])p: i. 1000
    0
       +/>1&p: each 2 %~ each +/ each (2 <\ ])p: i. 10000
    0
       +/>1&p: each 2 %~ each +/ each (2 <\ ])p: i. 100000
    0
     
       NB. the previous output took a few seconds.  The next will take a few minutes
     
       +/>1&p: each 2 %~ each +/ each (2 <\ ])p: i. 1000000
    0
    
  13. Mike said

    For number 3:

    p and q are consecutive primes.
    p and q are positive integers
    let m = (p + q)/2
    m is the mean of p
    p < m < q
    therefore, m cannot be prime, because p and q are consecutive primes

  14. Mike said

    For number 2:

    Let the digits be labelled a,b,c,d.  So for 1978, a=1, b=9, c=7, d=8.
    
    observation 1 : a + c = b, therefor a <= b and c <= b.  
                    Moreover, a < b, because if a == b, then c = 0, and there is
                    no d such that bb + 0d == b0.
                    So, only need to consider centuries in which a < b.
    
    observation 2: c = b - a if b + d = 10.  So for any given century, there
                   are only two possible decades.
    
    observation 3: for any give decade there is only 1 possible year such
                   that (b+d)%10 == c
    
    So:
      19cd: c can be 7 or 8
            197d: (9 + d)%10 == 7 => d = 8, and 19 + 78 = 97 **** 1978 is a winner
            198d: (9 + d)%10 == 8 => d = 9, but 19 + 89 != 98
    
      20cd: can't work because a >= b
      21cd:            "
      22cd:            "
    
      23cd: c can be 0 or 1
            230d:  (3 + d)%10 == 0  => d = 7, and 23 + 07 = 30 **** 2307 is a winner
            231d:  (3 + d)%10 == 1  => d = 8, but 23 + 18 != 31
    
      24cd: c can be 1 or 2:
            241d: d = 7, and 24 + 17 == 41 **** 2417 is a winner
    
    
    Based on observation 1, there are at most 8 possibilities for 1bcd, 7 for 2bcd, etc. for a total of (8*(8+1))/2 = 36 possible solutions between the years 1000 and 9999.
    
  15. Mike said

    The end of my previous comment should have said: Based on observation 1, there are at most 8 possibilities for 1bcd, 7 for 2bcd, etc. for a total of (8*(8+1))/2 = 36 possible solutions between the years 1000 and 9999

    aks said a,b,c,d must satisfy the formula: a*10 - b*9 + c*9 + d = 0.
    
    if you have (a, b, c, d) that satisfy the formula, these also satisfy
    the formula:
    
    observation 4 : (   a   , b +/- k, c +/- k,    d   )
    
    observation 5 : (a +/- k, b +/- k,    c   , d -/+ k)
    
    observation 6 : (a +/- k,    b   , c -/+ k, d -/+ k)
    
    where k is limited so that the new a,b,c,d are all single digits
    
    So:
      from 1978, apply observation 6, with k=1, to get a solution 2967.  Then
      apply observation 4, with k=6, to get the solution 2307
    
    by repeatedly applying observations 4 and 6, all solutions between 1000 and 9999 are easily found:
    
    1208, 1318, 1428, 1538, 1648, 1758, 1868, 1978
          2307, 2417, 2527, 2637, 2747, 2857, 2967
                3406, 3516, 3626, 3736, 3846, 3956
                      4505, 4615, 4725, 4835, 4945
                            5604, 5714, 5824, 5934
                                  6703, 6813, 6923
                                        7802, 7912
                                              8901
    
    Observation 4 moves along a row, observation 6 moves up or down a column.
    
  16. Vignesh M said

    // solution to 1978 prob. using Java

    public class Year1978Problem {

    /**
    * @param args
    */
    public static final int REF_YEAR = 1978;
    public static final int DEFAULT_VAL = 0;
    private int findNextYear(){
    boolean yearFound = false;
    int i = REF_YEAR; // (1978)
    int nextYear;
    do{
    i++; // starting the test with 1979
    int a = i/100; // to get (19)
    int b = i%100; // to get (79)
    int c = a%10; // to get (9)
    int d = b/10; // to get (7)
    int e = Integer.parseInt((Integer.toString(c)+d)); // to get (97)
    if((a+b) == e){ // checking whether 1979 is OK
    yearFound = true;
    return i; // return if yes,
    }

    }while(!yearFound); // continue till finding the year
    return DEFAULT_VAL;
    }
    public static void main(String[] args) {
    Year1978Problem obj = new Year1978Problem();
    int nextYear = obj.findNextYear();
    System.out.println(“Next year satisfying given condition : “+nextYear);
    }

    }

    # Next year satisfying given condition : 2307

  17. Alcriss said

    bool check = false;
    int _refYear = 1978;

    while (check == false)
    {
    _refYear += 1;
    check = CheckUp(_refYear);
    }

    Console.Write(“\n Next to 1978 is ” + _refYear + “.”);
    Console.ReadLine();
    Environment.Exit(0);

    }
    //METHODS

    public static bool CheckUp(int entry)
    {
    string _year = string.Empty;
    _year = Convert.ToString(entry);
    int _num1 = Convert.ToInt32(_year[0].ToString() + _year[1].ToString());
    int _num2 = Convert.ToInt32(_year[2].ToString() + _year[3].ToString());
    int _sum = _num1 + _num2;
    string _new = _year[1].ToString() + _year[2].ToString();
    if (_new == Convert.ToString(_sum))
    {
    return true;
    }
    return false;
    }

  18. Tyler said

    I have to learn Coldfusion for my job, so I’ve been using different examples from your site to help me learn. Most solutions I’ve seen to 1978 solve it by splitting it up into a,b,c,d. I chose a different route because I felt the individual digits didn’t mean as much as the two digits together. Is there anything wrong with me solving it this way?

    Year Program

    Find the next year after 1978 in which the middle digits is equals to the sum of the first two digits and the last two digits

    #NumberFormat(a, mask)# + #NumberFormat(c, mask)# = #NumberFormat(b, mask)#

  19. tylerchilds said

    Sorry, last one I placed inside instead of

    , my bad.
    
    
    
    	Year Program
    	
    	
    	
    	Find the next year after 1978 in which the middle digits is equals to the sum of the first two digits and the last two digits
    	
    		
    		
    		
    		
    			
    				#NumberFormat(a, mask)# + #NumberFormat(c, mask)# = #NumberFormat(b, mask)#
    			
    			
    		
    		
    	
    
    

  20. For #2:

    #!/usr/bin/ruby
    r=[];1978.upto(9999) {|y|y=y.to_s;((“#{y[0]}#{y[1]}”.to_i+”#{y[2]}#{y[3]}”.
    to_i)==(“#{y[1]}#{y[2]}”.to_i))?r.push(y):”; };puts r.to_s

    That will give you all the solutions that are in a 4 digit year. You can easily quit after the first by just printing (instead of pushing to an array and exiting):

    #!/usr/bin/ruby
    1978.upto(9999) {|y|y=y.to_s;((“#{y[0]}#{y[1]}”.to_i+”#{y[2]}#{y[3]}”.
    to_i)==(“#{y[1]}#{y[2]}”.to_i))?puts y;exit:”; }

Leave a Reply

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

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: