site-cache.rkt

((3) 0 () 0 () () (h ! (equal) ((u . "rackle_site//draft/posts/Leetcode-55-In-31-Characters-Of-BQN_2023-10-17.md") c 1699834157 u . "# Leetcode 55 In 31 Characters Of BQN\n\nGood ol' [Leetcode 55](https://leetcode.com/problems/jump-game/), a classic in the interview circuit. At first glance, it's a simple question with a straightforward solution - just simulate the game, jump from the start index to each reachable index and see if we can reach the end. This leads to an O(n^2) solution and inevitably to the follow up question: \"but can you do it in linear time?\".\n\nThis proves deceptively difficult. Deceptive because the linear solution is (like most leetcode problems) simple. But unless you've seen similar problems (or, you already know the \"trick\") you're bound to waste valuable interview time teasing out the solution. But once the answer strikes you (or you look it up), you'll either kick yourself for missing something so obvious or pat yourself on the back for seeing through the interviewer's ruse.\n\nHere's the idea, it's a basic dynamic programming solution:\n\nLet x = array[0] and at each index (i) calculate x = max(x-1, array[i]).\n\nIf x == 0 at or before the end of the array then we know we won't make it and we should return false.\n\nFollowing this recipe will get us an O(N) solution, which is normally ~10 lines of Python, but we can do it in just one line (32 characters!) of [BQN](https://mlochbaum.github.io/BQN/index.html) (presumably, we could also do it in one line in most other array languages, and Python list comprehensions will probably also get you close).\n\n```\nJumpgame ← {a← ⊑𝕩 , (×´ {a ≤ 𝕩 ? a↩𝕩; a↩a-1}¨ 𝕩) ≢ 0}\n\n```\n\nWe can run this block as follows\n\n```\nJumpgame ⟨0,2,1⟩\n->\t\t 0\nJumpgame ⟨ 2, 3, 1, 1, 4 ⟩\n->\t\t 1 \n```\n\nBQN doesn't exactly have the boolean value types True and False, instead they're represented naturally by 1 and 0.\n\nBQN is interepreted from right to left, but I'll walk through the code from right to left.\n\n```\nJumpgame ← {a← ⊑𝕩 , \n```\n\nWe define Jumpgame as a block (which in this case, will behave as a function) that captures the value of the first index as the variable a, then we proceed to the second, inner block using the ',' seperator.\n\n```\n{a ≤ 𝕩 ? a↩𝕩; a↩a-1}¨ 𝕩\n```\n\nThe inner block performs the algorithm discussed above. We use the previously defined variable a, and a variable that will be bound to the argument on the right side of the block, captured by 𝕩. The diaresis (¨) at the end of this block means \"Each\", resulting in the function being performed over each element , i.e., mapped over the given list. This results in a new array with the value max(x-1,array[i]) at each index i.\n\n```\n(×´ {a ≤ 𝕩 ? a↩𝕩; a↩a-1}¨ 𝕩) ≢ 0}\n```\n\nBy product folding this array (x' means fold by multiplying each element the list with the next element) and comparing the result with 0, we get our answer - can we reach the end or not? 0 means that there's a 0 somewhere in the array, so, no we can't. 1 means yes we can reach the end.\n\n\nAdmittedly, you could probably code golf this down quite a bit further. But I think this solution is fine as is, and as a bonus, it's surprisingly readable for an array language!") ((u . "rackle_site//draft/posts/A-Simple-C++-co-yield-Example_2023-10-10.cpp") c 1697671091 u . "// A Simple C++ co-yield Example\n/*\nCoroutines, put succinctly, are functions that can be paused and resumed at user defined suspension points. This post is mostly concered with co_yield's functionality. I won't go into too much detail regarding the implementation and usage of coroutines in C++ in this post. You can check out [cpp_reference](https://en.cppreference.com/w/cpp/language/coroutines) or [lewis_baker's blog](https://lewissbaker.github.io/) for more details on that. co_yield() can be thought of as a light abstraction on co_await's functionality (see references and posts above). Calling co_yield is equivelant to calling co_await promise.yield_value(expr), which as you might suspect, yields a value.\n\nSo how do coroutines help us? In general, they provide a nice interface for functions that might require starting and stopping, with the function's state being maintained in between calls. Think of how a rendering callback might work in a game engine. At every iteration or tick, the rendering callback function is called which returns the necessary data (like object positions, lighting calculations, etc.) for drawing to a screen. With coroutines you could avoid writing the rendering code as callback functions and instead write the code as functions that (potentially) yield values.\n\nIn general the usual use cases for coroutines are asynchronous IO (networks, files, etc.) and generator functions (audio, images, etc.), which we'll be taking a look at soon.\n\nThe following example isn't perfect. It doesn't speed up execution nor does it improve readability very much, but it does show how coroutines (specifically lazy generators via co_yield) can be used. The following Generator struct is part of the compiler magic necessary to use coroutines in C++. Note - the struct's name doesn't necessarily have to be \"Generator\", it can be anything, \"Generator\" just aptly describes the type of function we'll be creating.\n */\n#include <coroutine>\n#include <cstdio>\n#include <cstdint>\n#include <cstring>\n#include <exception>\n#include <iostream>\n#include <unistd.h>\n#include <utility>\n\ntemplate <typename T>\nstruct Generator {\n  struct promise_type;\n  // the handle is for suspending and resuming the coroutine\n  using handle_type = std::coroutine_handle<promise_type>;\n\n  // the promise type handles the returnable information for our coro\n  struct promise_type {\n\tT val_; // value to be yielded or returned from our coro\n\tstd::exception_ptr exception_;\n\n\t// necessary function for the promise type\n\tGenerator get_return_object() {\n\t  return Generator(handle_type::from_promise(*this));\n\t}\n\n\t// these std::suspend_always functions control the behavior of the coro on suspensions\n\tstd::suspend_always initial_suspend() {return {}; }\n\tstd::suspend_always final_suspend() noexcept {return {};}\n\n\t// error handling\n\tvoid unhandled_exception() { exception_ = std::current_exception(); }\n\n\t// yields the value\n\ttemplate<std::convertible_to<T> From>\n\tstd::suspend_always yield_value (From&& from) {\n\t  val_ = std::forward<From>(from);\n\t  return {};\n\t}\n\n\tvoid return_void() {}\n  };\n\n  handle_type h_;\n\n  Generator(handle_type h) : h_(h) {};\n\n  ~Generator() { h_.destroy(); }\n\n  // this what happens when we call our coro function (e.g. f())\n  T operator()() {\n\th_(); // call our promise type. this will run yield_value (I think?)\n\treturn std::move(h_.promise().val_); // return the data\n  }\n};\n/*\nThe following code calculates the donut's current frame. It's lifted directly from [here] (https://www.a1k0n.net/2021/01/13/optimizing-donut.html), with a nice explanation found [here](https://www.a1k0n.net/2011/07/20/donut-math.html) */\n#define R(mul,shift,x,y) \\\n  _=x; \\\n  x -= mul*y>>shift; \\\n  y += mul*_>>shift; \\\n  _ = 3145728-x*x-y*y>>11; \\\n  x = x*_>>10; \\\n  y = y*_>>10;\n\n\n// N.B. Of type Generator<T>\nGenerator<int8_t*>\nget_donut_frame() {\n  int8_t b[1760], z[1760];\n  int sA=1024,cA=0,sB=1024,cB=0,_;\n  for (;;) {\n    memset(b, 32, 1760);  // text buffer\n    memset(z, 127, 1760);   // z buffer\n    int sj=0, cj=1024;\n    for (int j = 0; j < 90; j++) {\n      int si = 0, ci = 1024;  // sine and cosine of angle i\n      for (int i = 0; i < 324; i++) {\n        int R1 = 1, R2 = 2048, K2 = 5120*1024;\n\n        int x0 = R1*cj + R2,\n            x1 = ci*x0 >> 10,\n            x2 = cA*sj >> 10,\n            x3 = si*x0 >> 10,\n            x4 = R1*x2 - (sA*x3 >> 10),\n            x5 = sA*sj >> 10,\n            x6 = K2 + R1*1024*x5 + cA*x3,\n            x7 = cj*si >> 10,\n            x = 40 + 30*(cB*x1 - sB*x4)/x6,\n            y = 12 + 15*(cB*x4 + sB*x1)/x6,\n            N = (-cA*x7 - cB*((-sA*x7>>10) + x2) - ci*(cj*sB >> 10) >> 10) - x5 >> 7;\n\n        int o = x + 80 * y;\n        int8_t zz = (x6-K2)>>15;\n        if (22 > y && y > 0 && x > 0 && 80 > x && zz < z[o]) {\n          z[o] = zz;\n          b[o] = \".,-~:;=!*#$@\"[N > 0 ? N : 0];\n        }\n        R(5, 8, ci, si)  // rotate i\n      }\n      R(9, 7, cj, sj)  // rotate j\n    }\n\tco_yield(b); // suspension point\n    R(5, 7, cA, sA);\n    R(5, 8, cB, sB);\n    usleep(15000);\n    printf(\"\\x1b[23A\");\n  }\n}\n\n/*\nThe co_yield(b) call is the function's suspension point. co_yield suspends the function and returns (yields) the value we pass to it. In this case, we're passing a char array filled with the donut's current frame data. By invoking the generator (calling gen()), we cause the function to execute until the suspension point. Reinvoking the generator will cause the function to continue where it left off. Subsequent calls of gen() will result in the function executing the rest of the code starting at the end of the loop, iterating through the loop again and pausing at the suspension point.\n */\n\nint main() {\n  auto gen = get_donut_frame();\n  for(;;) {\n\tauto b_ = gen();\n\tfor (int k = 0; 1761 > k; k++)\n      putchar(k % 80 ? b_[k] : 10);\n  }\n\n  return 0;\n}\n\n/*\nIn our main function we invoke the generator inside of an infinite for loop. Calling gen() yields our desired buffer which we then print out to the console. Resulting in a rotating donut being drawn on the screen.\n */\n")))