fork download
copy 
  1. # ========================================================================== #
  2. # These globals should be part of some library, hidden from the user
  3. # The only exposed functions are: get_position, get_world_dimensions,
  4. # move, measure, swap, and the directions (which should ideally be an enum)
  5. _grid = [[4, 5, 2, 2],
  6.          [1, 3, 6, 4]]
  7. _height = len(_grid)
  8. _length = len(_grid[0])
  9. def get_world_dimensions():
  10.     return (_length, _height)
  11. _x = 0
  12. _y = 0
  13. def get_position():
  14.     return (_x, _y)
  15.  
  16. North = "N"
  17. South = "S"
  18. East = "E"
  19. West = "W"
  20.  
  21. # Return the value of the current cell, or the one directly in the specified direction
  22. def measure(direction=None):
  23.     if direction is None:
  24.         return _grid[_y][_x]
  25.     # Hacky solution to get the value in that direction
  26.     # (probably not how it would actually be implemented)
  27.     x, y = get_position()
  28.     move(direction)
  29.     val = measure()
  30.     move_to(x, y)
  31.     return val
  32.  
  33. # Move one cell in the specified direction
  34. def move(direction):
  35.     global _x, _y
  36.     if direction == North:
  37.         _y = (_y + 1) % _height
  38.     elif direction == South:
  39.         _y = (_y - 1) % _height
  40.     elif direction == East:
  41.         _x = (_x + 1) % _length
  42.     elif direction == West:
  43.         _x = (_x - 1) % _length
  44.     else:
  45.         raise ValueError(f"{direction} is not a valid direction to move in")
  46.  
  47. # Move the values of the current cell and the one in the specified direction
  48. # But not wrapping around the edges
  49. def swap(direction):
  50.     # also kinda hacky, but this is not the point
  51.     if direction == North and _y + 1 < _height:
  52.         _grid[_y][_x], _grid[_y + 1][_x] = _grid[_y + 1][_x], _grid[_y][_x]
  53.     elif direction == South and _y > 0:
  54.         _grid[_y][_x], _grid[_y - 1][_x] = _grid[_y - 1][_x], _grid[_y][_x]
  55.     elif direction == East and _x + 1 < _length:
  56.         _grid[_y][_x], _grid[_y][_x + 1] = _grid[_y][_x + 1], _grid[_y][_x]
  57.     elif direction == West and _x > 0:
  58.         _grid[_y][_x], _grid[_y][_x - 1] = _grid[_y][_x - 1], _grid[_y][_x]
  59.     else:
  60.         raise ValueError(f"{direction} is not a valid direction to swap in from position {(_x, _y)}")
  61.  
  62.  
  63.  
  64. # ========================================================================== #
  65.  
  66. # Not a part of the API, but convenient for me here
  67. # The user could make something with the same effect, through get_position() and move()
  68. def move_to(x, y):
  69.     global _x, _y
  70.     _x = x
  71.     _y = y
  72.  
  73. # ========================================================================== #
  74. # My solution
  75.  
  76. # Assumes everything below and everything at this height to the left, 
  77. # is sorted in increasing order of going along the first row first, then the second and so on
  78. # Inserts the current cell, and returns the pointer to this cell
  79. def insert():
  80.     x, y = get_position()
  81.     val = measure()
  82.     if y > 0:
  83.         # Takes the shortcut of pulling it down if it should be there
  84.         # Then ensures it is in place, and continues with whatever was pulled up
  85.         if measure(South) > val:
  86.             swap(South)
  87.             move(South)
  88.             insert()
  89.             move(North)
  90.             val = measure()
  91.         if x == 0:
  92.             move(West)
  93.             if measure(South) <= val:
  94.                 move(East)
  95.                 return
  96.             # In this situation, we should move this all the way to the right and down once
  97.             # This is the best I could come up with for that
  98.             m, n = get_world_dimensions()
  99.             swap(South)
  100.             swap(West)
  101.             for i in range(2, m):
  102.                 move(West)
  103.                 swap(West)
  104.             for i in range(2, m):
  105.                 swap(East)
  106.                 move(East)
  107.             swap(South)
  108.             move(South)
  109.             insert()
  110.             move(North)
  111.             move(East)
  112.     if x > 0 and measure(West) > val:
  113.         swap(West)
  114.         move(West)
  115.         insert()
  116.         move(East)
  117.  
  118.  
  119.  
  120. # Goal: move the values around such that ever row and every column are individually sorted
  121. # Idea: "Standard" insertion sort, as if the grid was just one long array
  122. # where the first `m` elements are the ones in row 0, then comes row 1 and so on
  123. # This is already an O((nm)^2) algorithm in the ideal sense of being able to swap elements in constant time,
  124. # and even worse here, having to deal with the edges of the grid.
  125. def insertion_sort():
  126.     move_to(0, 0)
  127.     m, n = get_world_dimensions()
  128.     for i in range(n):
  129.         for j in range(m):
  130.             insert()
  131.             move(East)
  132.         move(North)
  133.  
  134.  
  135. print("Before")
  136. print(_grid)
  137.  
  138. insertion_sort()
  139.  
  140. print("After")
  141. print(_grid)
Success #stdin #stdout 0.04s 9440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Before
[[4, 5, 2, 2], [1, 3, 6, 4]]
After
[[1, 2, 2, 3], [4, 4, 5, 6]]
https://ideone.com/C42tF5
language:
Python 3 (python  3.12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!