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.
classBoard(object):def__init__(self,layout):self.board=[list(r)forrinlayout.split('\n')]self.init=["ABCDE","FGHIJ","KLMNO","PQRST","UVWXY"]self.size=5self.moves=[]defprint(self):forrowinself.board:print(row)# THE CHALLENGE: move the board back to the initial alphabetical
# state, recording moves as you go
defreset(self):goalr,goalc=0,0whileTrue: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
ifgoalr==self.size-1andgoalc==1:break# increment the goal row and column indexes, wrapping as needed
defincrement(self,goalr,goalc):goalc+=1ifgoalc==self.size:goalc=0goalr+=1returngoalr,goalc# rotate the provided row index to the left,
# returning the new column index for the provided column index (including wrapping)
defLX(self,rdx,cdx):row=self.board[rdx]self.board[rdx]=row[1:]+[row[0]]self.moves.append('L'+str(rdx))cdx-=1ifcdx<0:cdx=self.size-1returncdx# rotate the provided row index to the right,
# returning the new column index for the provided column index (including wrapping)
defRX(self,rdx,cdx):row=self.board[rdx]self.board[rdx]=[row[-1]]+row[0:-1]self.moves.append('R'+str(rdx))cdx+=1ifcdx==self.size:cdx=0returncdx# rotate the provided column index up,
# returning the new row index for the provided row index (including wrapping)
defUX(self,cdx,rdx):last=self.board[0][cdx]forrinrange(0,self.size)[::-1]:tmp=self.board[r][cdx]self.board[r][cdx]=lastlast=tmpself.moves.append('U'+str(cdx))rdx-=1ifrdx<0:rdx=self.size-1returnrdx# rotate the provided column index down,
# returning the new row index for the provided row index (including wrapping)
defDX(self,cdx,rdx):last=self.board[self.size-1][cdx]forrinrange(0,self.size):tmp=self.board[r][cdx]self.board[r][cdx]=lastlast=tmpself.moves.append('D'+str(cdx))rdx+=1ifrdx==self.size:rdx=0returnrdx# move the current index location to the goal index location
# without disturbing prior letters
# side effects both board and moves
defmove(self,rdx,cdx,goalr,goalc):# no change needed
ifrdx==goalrandcdx==goalc:return# letter just needs to move left to the start of the row
ifrdx==goalrandgoalc==0:whilecdx>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
ifrdx==goalr:rdx=self.DX(cdx,rdx)# move letter down a row
origc=cdxcdx=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
ifgoalc==self.size-1:whilecdx>0:cdx=self.LX(rdx,cdx)else:whilecdx<=goalc:cdx=self.RX(rdx,cdx)whilecdx>goalc+1:cdx=self.LX(rdx,cdx)# rotate goal column down so goal row is next to current row
times=0foriinrange(goalr,rdx):times+=1self.DX(goalc,rdx)# rotate row left to put letter into column
cdx=self.LX(rdx,cdx)# rotate column back up to original place
foriinrange(0,times):rdx=self.UX(cdx,rdx)# find the row and col indexes of the letter
deffind(self,letter):forrdxinrange(0,len(self.board)):row=self.board[rdx]forcdxinrange(0,len(row)):ifrow[cdx]==letter:return(rdx,cdx)raiseException("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()
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.