S2T2

Jim Randell 11:50 am on 27 February 2020 Permalink Reply
Tags: by: Harold Reiter ( 4 )   

• 

  Jim Randell 11:51 am on 27 February 2020 Permalink | Reply

  (See also: Puzzle #32).

  We can measure the “disorderedness” of a list by going through it and looking how each element compares to the next element. If it is less than the next element, then it is “ordered”. If it is greater than the next element, then it is “disordered”.

  Looking at the initial list we have:

  [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

  which gives the following pairs:

  (11, 10) (10, 9) (9, 8) (8, 7) (7, 6) (6, 5) (5, 4) (4, 3) (3, 2) (2, 1)

  all of which are disordered, giving the initial list a score of 10.

  The target list is:

  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

  which gives the following pairs:

  (1, 2) (2, 3) (3, 4) (4, 5) (5, 6) (6, 7) (7, 8) (8, 9) (9, 10) (10, 11)

  all of which are ordered, give the target list a score of 0.

  Suppose the list is:

  [? … a] [b … c] [d … e] [f … ?]

  And we move the [b … c] section to between e and f.

  Then we end up with

  [? … a] [d … e] [b … c] [f … ?]

  In the process we lose the adjacent pairs (a, b) (c, d) (e, f) and we gain the adjacent pairs (a, d) (e, b) (c, f).

  So the best improvement we could hope for is if the first three pairs are disordered, and the second three pairs are ordered, then we has reduced the disorderedness score by 3.

  For this to happen we need:

  a > b
  c > d
  e > f

  and:

  a < d
  e < b
  c < f

  We can write all six inequalities as the following chain:

  a < d < c < f < e < b < a

  So it is not possible for all the inequalities to hold simultaneously. So the best we can hope for in a move is to reduce the disorderedness score by 2.

  A similar argument holds if a block is moved to the left.

  Furthermore, if we consider the first move, we know the values a, b, c, d, e, f are in descending order. So the pairs (a, b), (c, d), (e, f) are disordered, and of the pairs (a, d) (e, b) (c, f) only (e, b) is ordered, so we can only reduce the disorderedness by 1 on the first move.

  Similarly, on the final move the list ends up correctly ordered, and a similar argument shows that we can only reduce the disorderedness by 1 on the final move.

  So, for a sequence of length 11, we start with a disorderedness score of 10, and to reduce this to a disorderedness score of 0 will require at least 6 moves (the score being reduced by 1+2+2+2+2+1 = 10). In general reversing a sequence of length n > 2 will require at least 1 + [n / 2] moves (where [x] denotes the integer part of x).

  But can we achieve a reversal in 6 moves?

  I wrote a program to try.

  The following program can be used to examine the behaviour of sequences up to length 9 in less than 7s (and length 10 takes 23 minutes). All of these were achievable with the expected minimum number of moves. Unfortunately we want to know about sequences of length 11 (which takes 93m).

  However, in my experiments with smaller sequences, I found that the minimal sequence found always had as an initial move, removing the two leftmost elements, and then re-inserting them at position (m – 1) // 2 (where m is the length of the original sequence).

  Using this as the first move reduces the run time for a length 10 sequence to 6s, and produces a solution of 6 moves for a length 11 sequence in just 29s.

  Run: [ @repl.it ]

  from enigma import irange, inf, subsets, first, arg, printf
  
  # start with a [1..m] list, reversed
  m = arg(9, 0, int)
  f = arg(1, 1, int)
  printf("[m={m}, f={f}]")
  
  # collect possible different moves
  move = dict()
  s = list(irange(0, m - 1))
  for (i, j) in subsets(irange(0, m - 1), size=2):
    for k in irange(1, m - j + i - 1):
      if k == i: continue
      r = s[i:j + 1]
      t = s[:i] + s[j + 1:]
      r = t[:k] + r + t[k:]
      if r not in move.values():
        move[(i, j, k)] = r
  
  # disorderedness score
  def score(s):
    r = 0
    a = None
    for b in s:
      if a is not None: r += (a > b)
      a = b
    return r
  
  # sort s in n (or fewer moves)
  def solve(s, n, d, ms=[]):
    # are we done?
    if d == 0:
      yield ms
    elif n > 0:
      # choose a move
      (diff1, diff2) = (list(), 0)
      for (m, v) in move.items():
        s1 = list(s[x] for x in v)
        d1 = score(s1)
        diff = d - d1
        if diff == 2:
          # try diff 2
          for z in solve(s1, n - 1, d1, ms + [m]): yield z
          diff2 += 1
        elif diff == 1:
          # save up diff 1
          diff1.append((s1, d1, m))
      # try any diff 1 moves
      if not diff2:
        for (s1, d1, m) in diff1:
          for z in solve(s1, n - 1, d1, ms + [m]): yield z
  
  s0 = list(irange(m, 1, step=-1))
  for n in irange(1 + m // 2, inf):
  
    # make an initial move...
    if f:
      m1 = (0, 1, (m - 1) // 2)
      s1 = list(s0[x] for x in move[m1])
      (s, n, ms) = (s1, n - 1, [m1])
    else:
      (s, ms) = (s0, [])
  
    ss = first(solve(s, n, score(s), ms), 1)
    for ms in ss:
      # output solution
      printf("n={n}: {ms}", n=len(ms))
      s = s0
      for (i, j, k) in ms:
        t = list(s[x] for x in move[(i, j, k)])
        printf("  [{i}, {j}] @ {k}: {s} -> {t} ({ss} -> {st})", ss=score(s), st=score(t))
        s = t
      printf()
    if ss: break
  

  Solution: The minimum number of moves required is 6.

  Here is one set of 6 moves that achieves the reversal:

  

  (Adjacent pairs that are ordered are linked with a hyphen).

  LikeLike

• 

  Jim Randell 11:19 am on 1 March 2020 Permalink | Reply

  John Crabtree has come up with the following procedure to reverse a sequence using a minimal number of moves.

  The first move partitions the sequence into an ordered sequence (to the left) and a subsequence from which ordered pairs can be removed and inserted into the ordered sequence (to the right). The total number of moves required is 1 + [n / 2].

  Here is the procedure used to reverse a length 11 sequence in 6 moves:

  

  And here is the procedure encapsulated in a Python program:

  Run: [ @repl.it ]

  from enigma import irange, tuples, arg, printf
  
  # generate the moves to reverse a sequence of length n
  def reverse(n):
    if n < 3:
      if n == 2: yield (1, 1, 0)
      return
    (h, r) = divmod(n, 2)
    # 1st move
    yield (h + r, n - 1, r)
    # then move successive pairs into position
    for k in irange(0, h - 1):
      i = k + h + r - 1
      j = i + 1
      yield (i, j, k)
      
  
  # disorderedness score
  score = lambda s: sum(a > b for (a, b) in tuples(s, 2))
  
  # make a block move
  def move(s, i, j, k):
    r = s[i:j + 1]
    t = s[:i] + s[j + 1:]
    return t[:k] + r + t[k:]
  
  n = arg(11, 0, int)
  
  # collect the moves
  ms = list(reverse(n))
  printf("[n={n}, {m} moves]", m=len(ms))
  s = list(irange(n, 1, step=-1))
  for (i, j, k) in ms:
    t = move(s, i, j, k)
    printf("  [{i}, {j}] @ {k}: {s} -> {t} ({ss} -> {st})", ss=score(s), st=score(t))
    s = t
  printf()
  

  LikeLike