MindCipher
May 10, 2013
For the first problem we perform a simple simulation:
(define (flips rev)
(define (flip) (if (< (rand) 1/2) 'H 'T))
(let loop ((k 3) (fs (list (flip) (flip) (flip))))
(if (equal? fs rev) k
(loop (+ k 1) (take 3 (cons (flip) fs))))))
Here rev is a list of coin flips in reverse order, since the coin flips are added to the front of the list. One call to flips computes the average number of flips to find the desired sequence. The two functions below compute the average over n trials:
(define (monday n)
(let loop ((i 0) (k 0))
(if (= i n) (/ k n 1.0)
(loop (+ i 1) (+ k (flips '(H T H)))))))
(define (tuesday n)
(let loop ((i 0) (k 0))
(if (= i n) (/ k n 1.0)
(loop (+ i 1) (+ k (flips '(T T H)))))))
Here are our results:
> (monday 1000)
9.996
> (tuesday 1000)
8.058
Thus Monday is likely to be higher than Tuesday. That makes sense because on Monday the new pattern starts fresh after a two-shot miss, while on Tuesday the new pattern has a head start of one flip after a two-shot miss. That is, if you flip heads-then-tails on Monday, then flip a tail to miss the pattern, you have to wait for the next heads-then-tails for the next possible hit. But on Tuesday, if you flip heads-then-tails, then flip a head to miss the pattern, you already have the first flip of the next heads-then-tails pattern.
The second problem is easily solved by splitting the number into pieces and checking each year after 1978 in order until the answer is found:
> (let loop ((n 1979))
(let ((front (quotient n 100))
(middle (modulo (quotient n 10) 100))
(back (modulo n 100)))
(if (= (+ front back) middle) n
(loop (+ n 1)))))
2307
If you don’t like the brute force solution, you can represent a year as 1000a + 100b + 10c + d, employ a little bit of algebra to form a diophantine equation, then solve.
The third problem is a trick: (p + q) / 2 is between p and q, and by definition there are no primes between p and q, so the answer is no, with no programming required.
We used take and rand from the Standard Prelude. You can run the programs at http://programmingpraxis.codepad.org/fpSuFV7A. Be sure to take a look at MindCipher; some of the problems there will turn your brain inside-out.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to solve two exercises from the MindCipher website […]
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 sumDayAns 2) 2307
n = 1979
while n<9999:
if (n/100) + (n%100) == (n/10)%100:
print n
break
n=n+1
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.
here’s my solution to 1978 in python:
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.@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).
@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.99838The 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
coins.rb
hosted with ❤ by GitHub
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#!/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 exitHere’s the run output:
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Test-prime-pair-sums.ijs
hosted with ❤ by GitHub
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
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.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.// 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
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;
}
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)#
Sorry, last one I placed inside
instead ofFor #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:”; }
Namako is basically right about problem 1. The two cases both amount to finding the expected hitting time for a Markov chain with FOUR states (counting the number of matched coins), from which a simple calculation — inv(I-Q)U where I is the identity matrix, Q is the transition matrix excluding the fourth state, and U is an all-ones column vector, then take the first element — gives the *exact result 10 for HTH and 8 for HTT.
What’s not obvious from that is what the standard deviations are.
A simulation can give that quite simply.
Monday => (count: 1000000 min: 3 max: 112 mean: 9.996582000000235 sd: 7.614711570447746 skew: 2.029387841503218)
Tuesday => (count: 1000000 min: 3 max: 71 mean: 7.994588000000178 sd: 4.892717307278136 skew: 1.833047061117329)
I tackled problem 2 by brute force.
(1000 to: 3000) select: [:year | (year // 100) + (year \ 100) = (year // 10 \ 100)]