Daily Challenge #176 - Loopover

Setup

Loopover puzzles are 2D sliding puzzles that work more like flat rubik's cubes. Instead of having one open slot for pieces to slide into, the entire grid is filled with pieces tha wrap back around when you slide a row or column.

You can try it out at this sketch here: https://www.openprocessing.org/sketch/576328

To complete this challenge, implement a function to return a list of moves that will transform an unsolved grid into a solved one.

Consider the grid:

ABCDE
FGHIJ
KLMNO
PQRST
UVWXY

If we make the move R0 (move the 0th row right) then we get:

EABCD
FGHIJ
KLMNO
PQRST
UVWXY

Likewise, if we do L0 (move the 0th row left), we get:

ABCDE
FGHIJ
KLMNO
PQRST
UVWXY

Back to normal.

Say we make the move U2 (move the 2nd column up):

ABHDE
FGMIJ
KLRNO
PQWST
UVCXY

D2 (2nd column down) would then return us to the original grid. With all of this in mind, our tests will give you the scrambled grid as input. Please return an array of the moves taken to unscramble the grid.

For example:

SCRAMBLED GRID:

DEABC
FGHIJ
KLMNO
PQRST
UVWXY

SOLVED GRID:

ABCDE
FGHIJ
KLMNO
PQRST
UVWXY

One possible solution would be ["L0", "L0"] as moving the top row left twice would result in the original, solved grid. Another would be ["R0", "R0", "R0"] etc. etc.

Tests

"ACDBE\nFGHIJ\nKLMNO\nPQRST\nUVWXY"
"ABCDE\nKGHIJ\nPLMNO\nFQRST\nUVWXY"

Some of these can be kind of tricky. Good luck!

---

This challenge comes from jaybruce1998 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[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()