DEV Community

loading...

Discussion on: Daily Challenge #176 - Loopover

Collapse
candidateplanet profile image
lusen / they / them 🏳️‍🌈🥑

Cool problem, but fairly unrealistic as an interview question in terms of time expectations for implementation. Could work as a design discussion or homework problem.

class Board(object):
  def __init__(self, layout):
    self.board = [list(r) for r in layout.split('\n')]
    self.init = ["ABCDE","FGHIJ","KLMNO","PQRST","UVWXY"]
    self.size = 5
    self.moves = []

  def print(self):
    for row in self.board:
      print(row)

  # THE CHALLENGE: move the board back to the initial alphabetical
  # state, recording moves as you go
  def reset(self):
    goalr, goalc = 0, 0

    while True:
      letter = self.init[goalr][goalc]
      rdx, cdx = self.find(letter)
      self.move(rdx, cdx, goalr, goalc)
      goalr, goalc = self.increment(goalr, goalc)
      # the last row is always ordered correctly, so once we
      # place the left-most letter in the row we're done
      if goalr == self.size-1 and goalc == 1:
        break

  # increment the goal row and column indexes, wrapping as needed
  def increment(self, goalr, goalc):
    goalc += 1
    if goalc == self.size:
      goalc = 0
      goalr += 1
    return goalr, goalc

  # rotate the provided row index to the left, 
  # returning the new column index for the provided column index (including wrapping)
  def LX(self, rdx, cdx):
    row = self.board[rdx]
    self.board[rdx] = row[1:] + [row[0]]
    self.moves.append('L'+str(rdx))
    cdx -= 1
    if cdx < 0:
      cdx = self.size -  1
    return cdx

  # rotate the provided row index to the right, 
  # returning the new column index for the provided column index (including wrapping)
  def RX(self, rdx, cdx):
    row = self.board[rdx]
    self.board[rdx] = [row[-1]] + row[0:-1]
    self.moves.append('R'+str(rdx))
    cdx += 1
    if cdx == self.size:
      cdx = 0
    return cdx

  # rotate the provided column index up,
  # returning the new row index for the provided row index (including wrapping)
  def UX(self, cdx, rdx):
    last = self.board[0][cdx]
    for r in range(0, self.size)[::-1]:
      tmp = self.board[r][cdx]
      self.board[r][cdx] = last
      last = tmp
    self.moves.append('U'+str(cdx))
    rdx -= 1
    if rdx < 0:
      rdx = self.size - 1
    return rdx

  # rotate the provided column index down,
  # returning the new row index for the provided row index (including wrapping)
  def DX(self, cdx, rdx):
    last = self.board[self.size-1][cdx]
    for r in range(0, self.size):
      tmp = self.board[r][cdx]
      self.board[r][cdx] = last
      last = tmp
    self.moves.append('D'+str(cdx))
    rdx += 1
    if rdx == self.size:
      rdx = 0
    return rdx

  # move the current index location to the goal index location
  # without disturbing prior letters
  # side effects both board and moves
  def move(self, rdx, cdx, goalr, goalc):
    # no change needed
    if rdx == goalr and cdx == goalc:
      return

    # letter just needs to move left to the start of the row
    if rdx == goalr and goalc == 0:
      while cdx > 0:
        cdx = self.LX(rdx, cdx)
      return

    # if letter is on same row as goal row, move it down a row without permanently disturbing previously set letters to left and above
    if rdx == goalr:
      rdx = self.DX(cdx, rdx) # move letter down a row
      origc = cdx
      cdx = self.LX(rdx, cdx) # move letter to left
      self.UX(origc, rdx) # move orig column without letter back up

    # move letter to right of goal column
    if goalc == self.size - 1:
      while cdx > 0:
        cdx = self.LX(rdx, cdx)
    else:
      while cdx <= goalc:
        cdx = self.RX(rdx, cdx)
      while cdx > goalc + 1:
        cdx = self.LX(rdx, cdx)

    # rotate goal column down so goal row is next to current row
    times = 0
    for i in range(goalr, rdx):
      times += 1
      self.DX(goalc, rdx)

    # rotate row left to put letter into column
    cdx = self.LX(rdx, cdx)

    # rotate column back up to original place
    for i in range(0, times):
      rdx = self.UX(cdx, rdx)

  # find the row and col indexes of the letter
  def find(self, letter):
    for rdx in range(0, len(self.board)):
      row = self.board[rdx]
      for cdx in range(0, len(row)):
        if row[cdx] == letter:
          return (rdx, cdx)
    raise Exception("letter not found")

board = Board("ABCDE\nFGHIJ\nKLMNO\nPQRST\nUVWXY")
print("STARTING")
board.print()

board.reset()
print("MOVES:", board.moves)

print("ENDING")
board.print()

print("-"*80)
board = Board("ABWDE\nFGCIJ\nKLHNO\nPQMST\nUVRXY")
print("STARTING")
board.print()

board.reset()
print("MOVES:", board.moves)

print("ENDING")
board.print()

print("-"*80)
board = Board("ACDBE\nFGHIJ\nKLMNO\nPQRST\nUVWXY")
print("STARTING")
board.print()

board.reset()
print("MOVES:", board.moves)

print("ENDING")
board.print()

print("-"*80)
board = Board("ABCDE\nKGHIJ\nPLMNO\nFQRST\nUVWXY")
print("STARTING")
board.print()

board.reset()
print("MOVES:", board.moves)

print("ENDING")
board.print()