S2T2

Jim Randell 4:56 pm on 8 January 2021 Permalink Reply
Tags: by: Colin Vout ( 2 )   

• 

  Jim Randell 5:14 pm on 8 January 2021 Permalink | Reply

  By choosing the excluded pitches we ensure that the scales are generated in the required order, so we only need to find the first scale that satisfies the specified condition.

  This Python program runs in 45ms.

  Run: [ @repl.it ]

  from enigma import subsets, irange, join, printf
  
  # count notes with an interval of k
  interval = lambda ps, k: sum((p + k) % 12 in ps for p in ps)
  
  # choose six notes to exclude
  for xs in subsets(irange(1, 11), size=6):
    ps = tuple(p for p in irange(0, 11) if p not in xs)
  
    # count notes with an interval of 1 and 5
    if not(interval(ps, 1) == 2 and interval(ps, 5) == 1): continue
  
    # the solution is the first value we find
    printf("{s}", s=join("01"[i in ps] for i in irange(0, 11)))
    break
  

  Solution: Skaredahora’s favourite scale is 100010101110.

  We can consider this as a binary representation of the number 2222.

  There are 12 possible scales starting with 1 that have exactly 2 notes with another note 1 above, and exactly one having another note 5 above.

  There are also 12 possible scales starting with 0.

  LikeLike

  • 

    Jim Randell 11:04 am on 9 January 2021 Permalink | Reply

    Here is another solution that treats the scales as numbers represented in binary.

    We can use the [[ bit_permutations() ]] function from the enigma.py library (described here [link]) to generate patterns with 6 bits set in lexicographic order.

    It runs in 45ms overall, and has an internal runtime of 55µs.

    Run: [ @repl.it ]

    from enigma import bit_permutations, dsum2, printf
    
    # count notes with and interval of k
    def interval(n, k):
      m = n << (12 - k) # notes shifted up an interval of k
      v = n | (n << 12) # wrapped values
      return dsum2(v & m) # count the set bits
      
    # choose a bit pattern with 6 of the 12 digits set
    for n in bit_permutations(0b100000011111, 0b111111111111):
      # count notes with an interval of 1 and 5
      if interval(n, 1) == 2 and interval(n, 5) == 1:
        printf("{n} -> {n:012b}")
        # we only need the first value
        break
    

    And here is an “unrolled” version that has an internal runtime of only 24µs [ link ].

    LikeLike

    • 

      Tony Brooke-Taylor 12:54 pm on 9 January 2021 Permalink | Reply

      I tried the binary approach first and was annoyed that this took more than twice as long as your first solution Jim. Having swapped other bits of my algorithm for yours I think the biggest time difference comes from this: your first approach generates trials with only the 6 notes in; my binary approach generates trials with all 12 positions included, and then I have to use an if statement or similar to test only the 6.

      LikeLike

• 

  Brian Gladman 10:24 am on 9 January 2021 Permalink | Reply

  You get the speed record this week Jim. And you can gain a few percent more by using a set for in place of a tuple. Maybe I am being stupid but it was not immediately obvious to me why lexically sorted zero digit positions produced numerically sorted values.

  LikeLike

  • 

    Jim Randell 11:02 am on 9 January 2021 Permalink | Reply

    @Brian: The lowest number will have the largest leftmost grouping of 0’s. And fortunately combinations are generated in lexicographic order, so that gives us what we want.

    LikeLike

• 

  Frits 12:22 pm on 9 January 2021 Permalink | Reply

  As the puzzle is not yet fully clear to me I publish a solution which does the same as Jim’s code.
  I tried to use different and probably less efficient code.

  check1 = lambda s: sum(y == (x + 1) % 12 \
                         for (x, y) in list(zip(s, s[1:] + s[:1])))
  
  check5 = lambda s: sum(y - x == 5 or 12 + x - y == 5 
                         for x in s for y in s if y > x)    
  
  # loop backwards as first found solution will have maximal value
  # and thus the 2nd 1 bit will be as far to the right as possible
  for A in range(7, 0, -1):
    for B in range(8, A, -1):
      for C in range(9, B, -1):
        for D in range(10, C, -1):
           for E in range(11, D, -1):
             if check1([0, A, B, C, D, E]) != 2: continue
             if check5([0, A, B, C, D, E]) != 1: continue
             
             # print solution
             for k in range(12):
               print("1", end="") if k in {0, A, B, C, D, E} \
                                  else print("0", end="")
             print()  
             exit()
  

  LikeLike

  • 

    Frits 1:00 pm on 9 January 2021 Permalink | Reply

    check5 can also be written as:

    check5 = lambda s: sum(y - x in {5, 7} for x in s for y in s if y > x)
    

    LikeLike

• 

  Hugh Casement 1:24 pm on 17 January 2021 Permalink | Reply

  Using Basic (oh horror!) I found the same solution as Jim.
  Five other scales can be found by transposing the scale up or down by appropriate numbers of semitones, always with 1 in first position. Each can be reversed to give the other six.

  I think the solution corresponds to C E F# G# A A#.
  Some of those sharps may be better designated as flats of the note above
  (though in an equitempered scale it makes no difference).

  Five semitones apart is the interval known as a fourth; that leaves seven semitones, known as a fifth, to the octave note. Those are generally considered the most harmonious intervals, so a person with normal hearing would want as many as possible in the scale. I bet S’s so-called music sounds even worse than the stuff they play in the supermarket so that we don’t linger over our shopping a moment longer than necessary. But then I’ve always said that the only good composer is a dead composer — preferably one who’s been dead for a couple of centuries.

  LikeLike