S2T2

Jim Randell 5:03 pm on 26 February 2021 Permalink Reply
Tags: by: Andrew Skidmore ( 85 )   

• 

  Jim Randell 5:22 pm on 26 February 2021 Permalink | Reply

  Here is a constructive solution.

  This Python program runs in 56ms.

  Run: [ @repl.it ]

  from collections import defaultdict
  from enigma import irange, inf, is_square, nsplit, peek, printf
  
  # generate (number-of-trees, total-area, size-of-square, distance-between-trees)
  def generate():
    # consider total number of trees (t = 4n)
    for t in irange(4, inf, step=4):
      # this is the same as the total number of acres
      # calculate the area in square yards
      a = 4840 * t
      # but the area is a square
      # and the side is a whole number of yards
      s = is_square(a)
      if s is None: continue
      # so the distance between trees is...
      (d, r) = divmod(4 * s, t)
      if d < 1: break
      if r == 0:
        printf("[t={t} a={a} s={s} d={d}]")
        yield (t, a, s, d)
  
  # collect candidate solutions by the even digits of the number of trees
  digits = {0, 2, 4, 6, 8}
  r = defaultdict(set)
  for (t, a, s, d) in generate():
    for x in digits.intersection(nsplit(t)):
      r[x].add(d)
  
  # look for digits that give a unique distance
  for (x, ds) in r.items():
    if len(ds) == 1:
      printf("digit {x} -> distance {ds} yards", ds=peek(ds))
  

  Solution: The distance between trees is 4 yards.

  ---

  Manually:

  If there are t = 4n trees around the perimeter, then we can calculate the distance d between them as:

  d = 88 √(5 / 2n)

  So:

  n⋅d² = 19360 = (2^5)(5)(11^2)

  Which gives the following (d, n) values:

  (d=1, n=19360) → t=77440
  (d=2, n=4840) → t=19360
  (d=4, n=1210) → t=4840
  (d=11, n=160) → t=640
  (d=22, n=40) → t=160
  (d=44, n=10) → t=40

  Looking at the t values we see that, of the even digits, only 8 gives a unique solution.

  Here is a Python program that uses the same approach:

  from collections import defaultdict
  from enigma import divisors_pairs, is_square, irange, nsplit, peek, printf
  
  # generate (number-of-trees, distance-between-trees)
  def generate():
    # n.d^2 = 19360
    for (n, d2) in divisors_pairs(19360, every=1):
      d = is_square(d2)
      if d is None: continue
      # return (t, d)
      t = 4 * n
      printf("[d={d} n={n} -> t={t}]")
      yield (t, d)
  
  # group candidate solutions by the even digits of the number of trees
  digits = set(irange(0, 9, step=2))
  r = defaultdict(set)
  for (t, d) in generate():
    for x in digits.intersection(nsplit(t)):
      r[x].add(d)
  
  # look for digits with a single distance
  for (x, ds) in r.items():
    if len(ds) == 1:
      printf("digit {x} -> distance {ds} yards", ds=peek(ds))
  

  LikeLike

  • 

    Tony Brooke-Taylor 12:57 pm on 27 February 2021 Permalink | Reply

    My solution replicates my manual approach. It is an order or magnitude quicker than yours – I think because I am being much more selective about the cases I try. Ironically it took me about ten times as long to code as it took me to solve the problem manually!

    #let the number of trees on a side be n, and the distance between trees be x yards, so the length of a side is n.x 
    
    #we are told that the total number of trees is equal to the area in acres, so
    #4n=((n.x)**2)/4840 
    
    #For integer values of n, valid values of x**2 must be made up of factors of 4*4840
    
    def factors(n):    
        j = 2
        while n > 1:
            for i in range(j, int(n**(1/2)) + 1):
                if n % i == 0:
                    n /= i ; j = i
                    yield i
                    break
            else:
                if n > 1:
                    yield int(n); break
    
    facs=list(factors(4*4840))
    
    #furthermore, if x is an integer, x**2 can only be made up of products of squares, meaning that we can only combine factors in multiples of two
    
    cofac=1
    mults=[]
    for fac in set(facs):
      if facs.count(fac)%2==1: cofac *= fac
      if facs.count(fac)//2>0:mults.append([fac**i for i in range(facs.count(fac)//2+1)])
    
    #mults contains the possible multiples of each valid prime factor; cofac is the product of factors that do not form part of a pair
    
    #use mults to generate all possible values for x
    x_vals=[1]
    for vec in mults:
      x_vals = [(i*j) for i in x_vals for j in vec]
    
    #each value of x generates a possible value for 4n  
    n_vals=list(zip(x_vals,[4*(x**2)*cofac for x in x_vals]))
    
    #we are now looking for the value for 4n which contains a unique instance of a given even number, so let's collect all digits in all our possible 4n's
    
    digits=[]
    for n in n_vals:
      digits=digits+([dig for dig in str(n[1])])
    
    #then find the value of 4n which contains the even digit that appears in only one value of 4n
    for ev in range(2,9,2):
      if digits.count(str(ev)) == 1:
        result_n = [n for n in n_vals if str(ev) in str(n[1])][0]
    
    print("The distance between adjacent trees is",(result_n[0]),"yards.")
    

    LikeLike

    • 

      Jim Randell 4:40 pm on 27 February 2021 Permalink | Reply

      @Tony: I also did some analysis which gives a fairly short manual solution (or a short program). I’ve put the code up on repl.it [link], and I’ll post the analysis later.

      LikeLike

    • 

      Frits 5:26 pm on 27 February 2021 Permalink | Reply

      @Tony,

      I have taken a similar approach like you (number of trees on a side is n) but I reach a different answer.

      At the Notes section of the Enigmatic Code (link in the About section) site Jim has described how you can include Python code so that it is displayed with colors.

      LikeLike

      • 

        Tony Brooke-Taylor 9:48 am on 28 February 2021 Permalink | Reply

        Brian has spotted my error. Thanks for the tip re: posting. Hopefully any posts I make in future will be more legible.

        LikeLike

    • 

      Brian Gladman 9:31 am on 28 February 2021 Permalink | Reply

      Line 38 should be:

      n_vals = list(zip(x_vals, [16 * 4840 // (x ** 2) for x in x_vals]))
      

      LikeLike

      • 

        Tony Brooke-Taylor 9:46 am on 28 February 2021 Permalink | Reply

        So it should, thanks.

        LikeLike

• 

  Frits 4:53 pm on 27 February 2021 Permalink | Reply

  from enigma import divisors_pairs
  from math import isqrt
  
  #          n trees  
  #     x . . . . . . . x
  #  n  .               . n     T = 4 * (n - 1),  total number of trees
  #     .               .             
  #  t  .    Jed's      . t     A = (n - 1)^2 * D^2,  A = area, D = distance
  #  r  .               . r 
  #  e  .    land       . e     no acres A / 4840 = T
  #  e  .               . e   
  #  s  .               . s     so (n - 1) * D^2 = 4 * 4840 = 19360
  #     x . . . . . . . x
  #          n trees  
    
  # make a list of possible <T> and <D> values
  TD = [(4 * b, sa) if sa * sa == a else (4 * a, sb) 
        for (a, b) in divisors_pairs(19360) 
        if (sa := isqrt(a)) ** 2 == a or (sb := isqrt(b)) ** 2 == b]
  
  # check if a certain even digit occurs in only one of the <T> values
  for dgt in '02468':
    if len(q := [x[1] for x in TD if dgt in str(x[0])]) == 1:
      print(f"answer = {q[0]} yards")
  

  LikeLike