Intersection of O(n) expanding circles with line from the origin

I am interested resolving a programming challenge problem, but I’m struggling obtaining an efficient solution.

Consider yourself as a point located on the origin $ (0,0)$ of an infinite two-dimensional flat world. There are $ n$ sea waves surrounding you, each one modeled as a circle with center $ (x_i, y_i)$ , initial radius $ r_i$ , and propagation speed $ s_i$ , so that the radius of wave $ i$ as a function of the time $ t ≥ 0$ is $ r_i + s_i \cdot t$ . You choose any fixed direction and run “forever” at speed $ p$ . Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

  • $ 1 ≤ p ≤ 1000$
  • $ 3 ≤ n ≤ 10^4$ [the number of circles $ c_i$ ]
  • $ −1000 ≤ x_i,\;y_i ≤ 1000$
  • $ 1 ≤ r_i ≤ 1000$
  • $ 0 ≤ s_i < p$
  • Except for $ n$ , all numbers are real, with at most three digits after the decimal point.
  • Initially, you are strictly outside all the waves.
  • There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

  • Each “fixed direction” to run forever is solely determined by the angle of that line with the X axis, namely $ 0 \leq \theta < 2 \pi$ .
  • For each $ \theta \in [0, 0.001, 0.002, \dots, 2\pi)$ :
    • Recall that the map is within the square $ [-1000, -1000]$ to $ [1000, 1000]$ , and the furthest distance between $ (0,0)$ and any point in the map has distance $ 1000\sqrt{2}$ . We advance at $ p$ speed, so at most we will compute $ 1000\sqrt{2}/p \approx 1414/p$ iterations.
    • For each $ t \in [0, 0.001, 0.002, \dots, 1414/p]$ :
      • My position at time $ t$ in line $ \theta$ is $ pos_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$ .
      • Check whether $ pos_t$ is inside any sea wave at moment $ t$ . Basically, check if the distance between $ pos_t$ and the center of each circle is less than that circle’s radius at moment $ t$ , namely $ r_i + s_i \cdot t$ . If so, bad luck; we’re done with this $ \theta$ and we continue the search.
      • If not, try with next $ t$ .
    • If no intersection is found after iterating all $ t$ s, then you will be able to scape (through line with angle $ \theta$ ).
  • If all $ \theta$ s got some intersections, then we are not able to scape.

This solution has cost $ \Theta(6000 \times 1400 \times n)$ , which is impractical for $ n \leq 10^4$ . Informally, and without being precise, the multiplicative term may be $ O(n^3)$ if $ n \leq 10^4$ is considered. Plus, it may not be correct, as I am assuming that $ \Delta t = 0.001$ is fine; same for the angle.


I have thought about another idea, which is reducing systematically $ \theta$ . For instance, let’s imagine that we’ve got a circle at $ C = (5, 5)$ (in the line of $ \theta = \pi/2$ ) with some small radius. From the beginning, we know that angles $ \theta = \pi/2 \pm \alpha$ will never be an option, being $ \alpha$ determined by tangent lines from $ (0, 0)$ to $ C$ and $ t$ ; the more time passes, the higher $ \alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $ t$ we have a set of ranges of possible $ \theta$ s, and that range is reduced as long as $ t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $ \Delta t$ and $ \Delta \theta$ .


I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $ O(k n)$ or $ O(k \cdot n \log n)$ with $ k$ being reasonably small.

Which creatures count as “entities from the shadowfell” for the purpose of a Shadow Magic Sorcerer’s origin?

The description of the sorcerer subclass “Shadow Magic” (XGtE, p. 50) starts off with the following paragraph (emphasis mine):

You are a creature of shadow, for your innate magic comes from the Shadowfell itself. You might trace your lineage to an entity from that place, or perhaps you were exposed to its fell energy and transformed by it.

Off the top of my head, I can only think of Shadar-Kai (MToF, p. 62). Other than that, I can’t think of suitable creatures – Darkmantles or Skull Lords among those not even humanoid, and it’s hard to imagine Meazels (MToF, p. 214) or Skulks (MToF, p. 227) having any offspring.

Are there any entities in the Shadowfell known from 5e or previous versions, aside from the Shadar-Kai, that are known to reproduce with other humanoids?
Or does “entity” include an immaculate conception from the Raven Queen? 😀

Who or what exactly does the “Same Origin Policy” aim to protect

As I understand the “Same Origin Policy” is a browser security feature that aims to protect the user. It prevents scripts to load data from another webserver (typicall with ajax).

So esentially there are 3 actors:

  • The User in the Browser
  • The Original Website
  • The “other origin” Web Resource

Does it protect the user ? No: With CORS I can just allow any Origin on a malicious “Other origin” Web Resource

Does it protect the original Website? No: With CORS I can just allow any Origin on a malicious “Other origin” Web Resource

Does it protect the “other origin” Web Resource? No: A browser with Same Origin Policy disabled or a crafted request can be used to get the request trough anyway

I cannot get my head around that. What is the situation where the SOP help and which of these 3 actors does it protect in this situation.

Fireball spell origin with Still Spell

The description for Fireball says

“You point your finger and determine the range (distance and height) at which the fireball is to burst. A glowing, pea-sized bead streaks from the pointing digit”

If you use the Still Spell metamagic feat, which removes the somatic components to a spell, do you still have to aim with your finger?

K Closest Points to Origin C# solution deemed too slow by Leetcode.com

LeetCode challenge

I know I could simply use the built in .Sort or .Order by to solve this question in 1 line. However, for interviews I would need to show the whole workings of my solution.

I am using a min-heap to calculate and store the distances from the origin. Then I simply return the K number of distances.

My code fails due to the “Time limit exceeded” error, indicating my code is too slow. However, it does return the correct answer.

Is there a more efficient way of using a min-heap? Or should my code be using a completely different algorithm and data structure?

public class Solution {     public int[][] KClosest(int[][] points, int K)     {         var lists = new int[K][];          Heap head = new Heap();          for (int i = 0; i < points.Length; i++)         {             int a = points[i][0];             int b = points[i][1];             var testMin = a * a + b * b;             var newNode = new Node             {                 val = testMin,                 index = points[i]             };             head.Add(newNode);         }          for (int i = 0; i < K; i++)         {             lists[i] = head.Pop().index;         }          return lists;     } }  class Heap {     public Node head;     public Node tail;      public void Add(Node newNode)     {         if (head == null)         {             head = newNode;             tail = newNode;         }         else         {             newNode.parent = tail;             tail.next = newNode;             tail = tail.next;         }         HeapifyUp();     }      void HeapifyUp()     {         Node curr = tail;         while (curr.parent != null)         {             if (curr.val < curr.parent.val)             {                 var tVal = curr.val;                 var tIndex = curr.index;                  curr.val = curr.parent.val;                 curr.index = curr.parent.index;                  curr.parent.val = tVal;                 curr.parent.index = tIndex;             }             curr = curr.parent;         }     }      public Node Pop()     {         var tempHead = new Node         {             index = head.index,             val = head.val         };          // Set head value to tail value         head.index = tail.index;         head.val = tail.val;          // Deference tail         if (tail.parent != null)         {             tail.parent.next = null;             tail = tail.parent;         }         else         {             tail = null;             head = null;         }          HeapifyDown();          return tempHead;     }      void HeapifyDown()     {         Node curr = head;         while (curr != null && curr.next != null)         {             if (curr.val > curr.next.val)             {                 var tVal = curr.val;                 var tIndex = curr.index;                  curr.val = curr.next.val;                 curr.index = curr.next.index;                  curr.next.val = tVal;                 curr.next.index = tIndex;             }             curr = curr.next;         }     } }  class Node {     public int[] index;     public int val;     public Node next;     public Node parent; } 

Compute manhattan distance from origin given a set of left-right-step directions

I am solving the problems for Advent of Code 2016 to learn Rust programming. The prompt for the first problem can be summarized:

I start at position 0,0 on a regular grid. I am given a set of directions to get to a location. I can only travel in “steps” on this grid, and I am only given directions in the form (e.g.):

“R5, L2, L1, R1, R3, R3, L3, R3, R4, L2, R4, L4, R4”

Where the first character is the direction to turn right or left and the following number is the number of steps to take. I need to compute the Manhattan distance between my starting point and the ending point.

The instructions are saved in a text file called “2016-1.txt”.

use std::fs;  struct Pos {     facing: char,     x: i32,     y: i32, }  fn split_dir(dir_str: &str) -> Vec<&str> {     dir_str.split(", ").collect() }  fn update_facing(rel_dir: &char, face_char: &char) -> char {     if *rel_dir == 'L' {         match face_char {             'N' => 'W',             'S' => 'E',             'E' => 'N',             'W' => 'S',             _ => 'I', // Is there a better way to handle the catch-all?         }     } else {         match face_char {             'N' => 'E',             'S' => 'W',             'E' => 'S',             'W' => 'N',             _ => 'I',         }     } }  fn update_x(pos_x: i32, face_char: char, move_num: i32) -> i32 {     match face_char {         'E' => pos_x + move_num,         'W' => pos_x - move_num,         _   => pos_x     } }  fn update_y(pos_y: i32, face_char: char, move_num: &i32) -> i32 {     match face_char {         'N' => pos_y + move_num,         'S' => pos_y - move_num,         _   => pos_y     } }  fn get_manhattan_dist(pos_x: i32, pos_y: i32, origin_x: i32, origin_y: i32) -> i32 {     (pos_x - origin_x).abs() + (pos_y - origin_y).abs() }  fn main() {     let s = fs::read_to_string("2016-1.txt")         .expect("Failed to read file.");      let split: Vec<&str> = split_dir(&s);      let mut pos: Pos = Pos {x: 0, y: 0, facing: 'N'};      for inst in split {         // Update direction         let rel_dir = inst.chars().nth(0).unwrap(); // Get first character of the instruction         pos.facing = update_facing(&rel_dir, &pos.facing);          // Update position         let move_num = &inst[1..].parse::<i32>().unwrap();         pos.x = update_x(pos.x, pos.facing, *move_num);         pos.y = update_y(pos.y, pos.facing, &move_num);     }      let dist = get_manhattan_dist(pos.x, pos.y, 0, 0);     println!("{}", dist); } 

I am particularly interested in error handling. Particularly in the “update_facing” function. This is my first Rust program, so all advice is warranted as well.

Origin of the convolution theorem

I am chemist, with some interest in signal processing. Sometimes, we occasionally use the deconvolution process to remove the instruments response from the desired signals. I am looking for the earliest reference which proposed the convolution theorem which is often utilized in signal processing (i.e., convolution becomes a multiplication in the Fourier domain).

The Earliest Known Uses of the Word of Mathematics websites gives lot of details on the word convolution, but who was the first person to specifically show the above mentioned property- the connection of Fourier transforms with convolution?

Here is the history of Convolution Operation: https://pulse.embs.org/january-2015/history-convolution-operation/

However, a mathematician privately disagreed with that historical account given in this article.

Thanks.

What is causing 403 during attempt to push local repository to remote origin on my git server?

I am building a git server to allow my app users to remotely host their projects (similar to Github).

When a user posts a repository, the following function is ran after it’s saved to my database:

@receiver(post_save, sender=Repository) def init_repository(sender, instance, created, **kwargs):     profile = Profile.objects.get(user=instance.user)     folder = f"{profile.folder}/{instance.name}.git"     os.system(f"sudo mkdir -p {folder} && cd {folder} && sudo git --bare init && sudo git update-server-info")     os.system(f"sudo chown -R www-data:www-data . && sudo chmod -R 755 .")  

My intention here is to give www-data full access to the repository. Below is my nginx config:

location ~ /git(/.*)(/.*) {         autoindex on;         alias /var/www/html/git;         fastcgi_pass unix:/var/run/fcgiwrap.socket;         auth_basic "Git Login";         auth_basic_user_file /var/www/html/git/$  1/.htpasswd;         include fastcgi_params;         fastcgi_param REQUEST_METHOD $  request_method;         fastcgi_param SCRIPT_FILENAME $  2;         fastcgi_param GIT_HTTP_EXPORT_ALL "";         fastcgi_param GIT_PROJECT_ROOT /var/www/html/git/$  1;         fastcgi_param PATH_INFO /var/www/html/git/$  1/$  2; } 

I created the above config to allow users to have access to their posted repositories from the cmd line via git smart protocols. Below is where I get stuck:

$   git remote add origin http://xx.xxx.xxx.xxx/git/test_user/test_repo.git $   git push origin master  Username for 'http://xx.xxx.xxx.xxx': test_user Password for 'http://test_user@xx.xxx.xxx.xxx': fatal: unable to access 'http://xx.xxx.xxx.xxx/git/test_user/test_repo.git/': The requested URL returned error: 403 

So authentication is working, but I am unable to access the repository. To get around this, I’ve tried making all files & folders inside /var/www/html/git rwxrwxrwx. I also restarted Nginx and reloaded supervisor. Still get the same error.