dev.to staff

Posted on

# 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 yo+challenge@dev.to with your suggestions!

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)

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