API tools faq
paste
piRSquared

AoC Day3

piRSquared
Dec 5th, 2017
219
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 8.18 KB | None | 0 0
raw download clone embed print report
  1. # Setup
  2. import pandas as pd
  3. import numpy as np
  4. pd.set_option('display.notebook_repr_html', False, 'expand_frame_repr', False, 'display.max_colwidth', 50)
  5.  
  6. # This gives me the largest odd number whose
  7. # square is less than or equal to n
  8. last_odd_root   = lambda n: int((n - 1) ** .5 + 1) // 2 * 2 - 1
  9.  
  10. # This takes the custom tuple returned by
  11. # spiral_num and returns the Manhatten Distance
  12. spiral_distance = lambda t: t[0] + abs(t[1][1])
  13.  
  14. def spiral_num(n):
  15.     """This returns a custom tuple that describes the
  16.    position of n in terms of a radius and angle"""
  17.     a    = last_odd_root(n)
  18.     head = a ** 2             # gives the end point of last layer
  19.     tail = n - head           # how many since last layer
  20.     size = a + 1              # length of a side of current layer
  21.      
  22.     radius = size // 2        # distance of current layer from origin
  23.     theta  = (                # two values, the first enumerates
  24.         tail // size % 4,     # which of the four sections we're in
  25.         tail % size - radius  # and where along section we're in  
  26.     )
  27.    
  28.     return radius, theta
  29.  
  30. def cartesian_coords(p):
  31.     """Convert custom tuples to Cartesian coordinates relative to (0, 0)"""
  32.     radius, (leg, loc) = p
  33.     signs = [0, -1, 0, 1]
  34.     _sign = signs[leg]
  35.     sign  = signs[(leg - 1) % 4]
  36.     sign_ = signs[(leg - 2) % 4]
  37.    
  38.     x = loc * _sign + radius * sign
  39.     y = loc * sign  + radius * sign_
  40.    
  41.     return x, y
  42.  
  43. def cartesian_to_indices(origin, x, y):
  44.     """Convert Cartesion coordinates to array indices"""
  45.     return origin - y, origin + x
  46.  
  47. def convolve(p, tracker):
  48.     """Sum all neighbors"""
  49.     result = 0
  50.     for i in [-1, 0, 1]:
  51.         for j in [-1, 0, 1]:
  52.             result += tracker.get((p[0] + i, p[1] + j), 0)
  53.     return result
  54.  
  55. ##########################################################################################
  56. # Solve Problem
  57. ##########################################################################################
  58.  
  59. # My input
  60. x = 277678
  61.  
  62. tracker = {(0, 0): 1}
  63. for n in range(2, x + 1):
  64.     p = cartesian_coords(spiral_num(n))
  65.     tracker[p] = convolve(p, tracker)
  66.     if tracker[p] > x:
  67.         print(n, x, tracker[p])
  68.         break
  69.  
  70. # 59 277678 279138
  71.  
  72. ##########################################################################################
  73. # Look at results
  74. ##########################################################################################
  75.  
  76. pd.Series(tracker).unstack(fill_value=0).iloc[:, ::-1].T
  77.  
  78. #        -3     -2     -1      0      1       2       3       4
  79. #  4      0      0      0      0      0  279138  266330  130654
  80. #  3   6591   6444   6155   5733   5336    5022    2450  128204
  81. #  2  13486    147    142    133    122      59    2391  123363
  82. #  1  14267    304      5      4      2      57    2275  116247
  83. #  0  15252    330     10      1      1      54    2105  109476
  84. # -1  16295    351     11     23     25      26    1968  103128
  85. # -2  17008    362    747    806    880     931     957   98098
  86. # -3  17370  35487  37402  39835  42452   45220   47108   48065
  87.  
  88. ##########################################################################################
  89. # More fun!
  90. ##########################################################################################
  91.  
  92. def create_spiral(n, show_tup=False):
  93.     k = last_odd_root(n + 1)
  94.     df = pd.DataFrame('', index=range(k), columns=range(k))
  95.    
  96.     for i_ in range(2, k ** 2 + 1):
  97.         tup = spiral_num(i_)
  98.         i, j = cartesian_to_indices(k // 2, *cartesian_coords(tup))
  99.         df.iat[i, j] = tup if show_tup else i_
  100.  
  101.     return df
  102.  
  103. print(create_spiral(400), create_spiral(169, 1), sep='\n' * 2)
  104.  
  105. #      0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16   17   18
  106. # 0   325  324  323  322  321  320  319  318  317  316  315  314  313  312  311  310  309  308  307
  107. # 1   326  257  256  255  254  253  252  251  250  249  248  247  246  245  244  243  242  241  306
  108. # 2   327  258  197  196  195  194  193  192  191  190  189  188  187  186  185  184  183  240  305
  109. # 3   328  259  198  145  144  143  142  141  140  139  138  137  136  135  134  133  182  239  304
  110. # 4   329  260  199  146  101  100   99   98   97   96   95   94   93   92   91  132  181  238  303
  111. # 5   330  261  200  147  102   65   64   63   62   61   60   59   58   57   90  131  180  237  302
  112. # 6   331  262  201  148  103   66   37   36   35   34   33   32   31   56   89  130  179  236  301
  113. # 7   332  263  202  149  104   67   38   17   16   15   14   13   30   55   88  129  178  235  300
  114. # 8   333  264  203  150  105   68   39   18    5    4    3   12   29   54   87  128  177  234  299
  115. # 9   334  265  204  151  106   69   40   19    6         2   11   28   53   86  127  176  233  298
  116. # 10  335  266  205  152  107   70   41   20    7    8    9   10   27   52   85  126  175  232  297
  117. # 11  336  267  206  153  108   71   42   21   22   23   24   25   26   51   84  125  174  231  296
  118. # 12  337  268  207  154  109   72   43   44   45   46   47   48   49   50   83  124  173  230  295
  119. # 13  338  269  208  155  110   73   74   75   76   77   78   79   80   81   82  123  172  229  294
  120. # 14  339  270  209  156  111  112  113  114  115  116  117  118  119  120  121  122  171  228  293
  121. # 15  340  271  210  157  158  159  160  161  162  163  164  165  166  167  168  169  170  227  292
  122. # 16  341  272  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  291
  123. # 17  342  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287  288  289  290
  124. # 18  343  344  345  346  347  348  349  350  351  352  353  354  355  356  357  358  359  360  361
  125.  
  126. #               0             1             2             3             4             5            6             7             8             9             10            11            12
  127. # 0   (6, (2, -6))   (6, (1, 5))   (6, (1, 4))   (6, (1, 3))   (6, (1, 2))   (6, (1, 1))  (6, (1, 0))  (6, (1, -1))  (6, (1, -2))  (6, (1, -3))  (6, (1, -4))  (6, (1, -5))  (6, (1, -6))
  128. # 1   (6, (2, -5))  (5, (2, -5))   (5, (1, 4))   (5, (1, 3))   (5, (1, 2))   (5, (1, 1))  (5, (1, 0))  (5, (1, -1))  (5, (1, -2))  (5, (1, -3))  (5, (1, -4))  (5, (1, -5))   (6, (0, 5))
  129. # 2   (6, (2, -4))  (5, (2, -4))  (4, (2, -4))   (4, (1, 3))   (4, (1, 2))   (4, (1, 1))  (4, (1, 0))  (4, (1, -1))  (4, (1, -2))  (4, (1, -3))  (4, (1, -4))   (5, (0, 4))   (6, (0, 4))
  130. # 3   (6, (2, -3))  (5, (2, -3))  (4, (2, -3))  (3, (2, -3))   (3, (1, 2))   (3, (1, 1))  (3, (1, 0))  (3, (1, -1))  (3, (1, -2))  (3, (1, -3))   (4, (0, 3))   (5, (0, 3))   (6, (0, 3))
  131. # 4   (6, (2, -2))  (5, (2, -2))  (4, (2, -2))  (3, (2, -2))  (2, (2, -2))   (2, (1, 1))  (2, (1, 0))  (2, (1, -1))  (2, (1, -2))   (3, (0, 2))   (4, (0, 2))   (5, (0, 2))   (6, (0, 2))
  132. # 5   (6, (2, -1))  (5, (2, -1))  (4, (2, -1))  (3, (2, -1))  (2, (2, -1))  (1, (2, -1))  (1, (1, 0))  (1, (1, -1))   (2, (0, 1))   (3, (0, 1))   (4, (0, 1))   (5, (0, 1))   (6, (0, 1))
  133. # 6    (6, (2, 0))   (5, (2, 0))   (4, (2, 0))   (3, (2, 0))   (2, (2, 0))   (1, (2, 0))                (1, (0, 0))   (2, (0, 0))   (3, (0, 0))   (4, (0, 0))   (5, (0, 0))   (6, (0, 0))
  134. # 7    (6, (2, 1))   (5, (2, 1))   (4, (2, 1))   (3, (2, 1))   (2, (2, 1))  (1, (3, -1))  (1, (3, 0))  (1, (0, -1))  (2, (0, -1))  (3, (0, -1))  (4, (0, -1))  (5, (0, -1))  (6, (0, -1))
  135. # 8    (6, (2, 2))   (5, (2, 2))   (4, (2, 2))   (3, (2, 2))  (2, (3, -2))  (2, (3, -1))  (2, (3, 0))   (2, (3, 1))  (2, (0, -2))  (3, (0, -2))  (4, (0, -2))  (5, (0, -2))  (6, (0, -2))
  136. # 9    (6, (2, 3))   (5, (2, 3))   (4, (2, 3))  (3, (3, -3))  (3, (3, -2))  (3, (3, -1))  (3, (3, 0))   (3, (3, 1))   (3, (3, 2))  (3, (0, -3))  (4, (0, -3))  (5, (0, -3))  (6, (0, -3))
  137. # 10   (6, (2, 4))   (5, (2, 4))  (4, (3, -4))  (4, (3, -3))  (4, (3, -2))  (4, (3, -1))  (4, (3, 0))   (4, (3, 1))   (4, (3, 2))   (4, (3, 3))  (4, (0, -4))  (5, (0, -4))  (6, (0, -4))
  138. # 11   (6, (2, 5))  (5, (3, -5))  (5, (3, -4))  (5, (3, -3))  (5, (3, -2))  (5, (3, -1))  (5, (3, 0))   (5, (3, 1))   (5, (3, 2))   (5, (3, 3))   (5, (3, 4))  (5, (0, -5))  (6, (0, -5))
  139. # 12  (6, (3, -6))  (6, (3, -5))  (6, (3, -4))  (6, (3, -3))  (6, (3, -2))  (6, (3, -1))  (6, (3, 0))   (6, (3, 1))   (6, (3, 2))   (6, (3, 3))   (6, (3, 4))   (6, (3, 5))  (6, (0, -6))
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!