How could I calculate the distance between the parent and neighbors node when there is a line of sight between two points?

I have completed my Astar algorithm in Python and now I need to convert it to a Theta star algorithm, I have built my line of sight algorithm below, but when I come to my Theta star algorithm I face some problems when there is a line of sight by calculating the distance and how could I make it jump the points that have line of sight. After running my code, I see there is no any effect, I see it’s working as Astar algorithm. Any assistance, please?

The snippet that I have a problem with it:

sight = lineOfsight(grid, y, x, y2, x2) if sight == True:          g2 = g + delta[i][2] + math.sqrt((x2 - x)**2 + (y2 - y)**2)           h2 = math.sqrt((x2 - goal[0])**2 + (y2 - goal[1])**2)           f2 = g2 + h2   else:           g2 = g + delta[i][2]                       h2 = math.sqrt((x2 - goal[0])**2 + (y2 - goal[1])**2)           f2 = g2 + h2   open.append([f2,g2,h2,x2,y2]) 

My line of sight code:

def lineOfsight(grid, y1, x1, y2, x2):     y_size = len(grid)     x_size = len(grid)      #Distance     dy=y2-y1     dx=x2-x1      if dy < 0:         dy = -dy         sy = -1     else:         sy = 1      if dx < 0:         dx = -dx         sx = -1     else:         sx = 1      f = 0      if dx >= dy:         while x1 != x2:             f = f + dy             if f >= dx and 0 < y1+(sy-1)/2 and y1+(sy-1)/2 < y_size and 0 < x1+(sx-1)/2 and x1+(sx-1)/2 < x_size:                 if grid[x1+int((sx-1)/2)][y1+int((sy-1)/2)]:                      return False                 y1 = y1 + sy                 f  = f  - dx              elif 0 < y1+(sy-1)/2 and y1+(sy-1)/2 < y_size and 0 < x1+(sx-1)/2 and x1+(sx-1)/2 < x_size:                 if f != 0 and grid[x1+(sx-1)/2][y1+(sy-1)/2]:                      return False              elif 1<y1 and y1<y_size and 0 < x1+(sx-1)/2 and x1+(sx-1)/2 < x_size:                 if dy==0 and grid[x1+int((sx-1)/2)][y1] and grid[x1+int((sx-1)/2)][y1-1] :                      return False             x1 = x1 + sx      else:          while y1 != y2:             f = f + dx             if f >= dy and 0 < y1+(sy-1)/2 and y1+(sy-1)/2 < y_size and 0< x1+(sx-1)/2 and x1+(sx-1)/2 < x_size:                 if grid[x1+int((sx-1)/2)][y1+int((sy-1)/2)]:                      return False                 x1 = x1 + sx                 f = f - dy             elif 0 < y1+(sy-1)/2 and y1+(sy-1)/2 < y_size and 0 < x1+(sx-1)/2 and x1+(sx-1)/2 < x_size:                 if f !=0 and grid[x1+int((sx-1)/2)][y1+int((sy-1)/2)]:                      return False              elif 0 < y1+(sy-1)/2 and y1+(sy-1)/2 < y_size and 1 < x1 and x1 < x_size:                        if dx == 0 and grid[x1][y1+ int((sy-1)/2)] and grid[x1-1][y1+int((sy-1)/2)]:                      return False              y1=y1+sy      return True 

My theta star code:

import matplotlib.pyplot as plt from lineofsightss import * #grid format # 0 = navigable space # 1 = occupied space  import random import math  grid = [[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],         [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],         [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],         [0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0],         [0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0],         [0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0],         [0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0],         [0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0],         [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],         [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]]    init = [0,0]                            #Start location is (5,5) which we put it in open list. goal = [len(grid)-1,len(grid[0])-1]       heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))] for i in range(len(grid)):         for j in range(len(grid[0])):                     heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])  plt.plot(0,10) plt.plot(0,-len(grid)-10) plt.grid(True) plt.axis("equal")  plt.plot([-1, len(grid[0])],[[-x/2 for x in range(-1,len(grid)*2+1)], [-y/2 for y in range(-1,len(grid)*2+1)]], ".k") plt.plot([[x/2 for x in range(-2,len(grid[0])*2+1)],[x/2 for x in range(-2,len(grid[-1])*2+1)]],[1, -len(grid)],".k")  plt.plot(init[1],-init[0],"og") plt.plot(goal[1],-goal[0],"ob")   #Below the four potential actions to the single field   delta =      [[1, 0, 1],               [0, 1, 1],               [-1, 0, 1],               [0, -1, 1],               [-1, -1, math.sqrt(2)],               [-1, 1, math.sqrt(2)],               [1, -1, math.sqrt(2)],               [1, 1, math.sqrt(2)]]    delta_name = ['V','>','<','^','//','\','\','//']   def search():      pltx,plty=[],[]     #open list elements are of the type [g,x,y]      closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]     action = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]     #We initialize the starting location as checked     closed[init[0]][init[1]] = 1     expand=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]      # we assigned the cordinates and g value     x = init[0]     y = init[1]     g = 0      h = math.sqrt((x - goal[0])**2 + (y - goal[1])**2)      f = g + h      #our open list will contain our initial value     open = [[f, g, h, x, y]]       found  = False   #flag that is set when search complete     resign = False   #Flag set if we can't find expand     count = 0      #print('initial open list:')     #for i in range(len(open)):             #print('  ', open[i])     #print('----')      while found is False and resign is False:          #Check if we still have elements in the open list         if len(open) == 0:    #If our open list is empty, there is nothing to expand.             resign = True             print('Fail')             print('############# Search terminated without success')             print()         else:             #if there is still elements on our list             #remove node from list             open.sort()             #sort elements in an increasing order from the smallest g value up             open.reverse()          #reverse the list             next = open.pop()       #remove the element with the smallest g value from the list             #print('list item')             #print('next')              #Then we assign the three values to x,y and g. Which is our expantion.             x = next[3]             y = next[4]             g = next[1]             #elvation[x][y] = np.random.randint(100, size=(5,6))             expand[x][y] = count             count+=1              #Check if we are done             if x == goal[0] and y == goal[1]:                 found = True                 print(next) #The three elements above this "if".                 print('############## Search is success')                 print()              else:                 #expand winning element and add to new open list                 for i in range(len(delta)):       #going through all our actions the four actions                     #We apply the actions to x and y with additional delta to construct x2 and y2                     x2 = x + delta[i][0]                     y2 = y + delta[i][1]                       #if x2 and y2 falls into the grid                     if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 <= len(grid[0])-1:                          #if x2 and y2 not checked yet and there is not obstacles                         if closed[x2][y2] == 0 and grid[x2][y2]==0:                              sight = lineOfsight(grid, y, x, y2, x2)                             if sight == True:                                  g2 = g + delta[i][2] + math.sqrt((x2 - x)**2 + (y2 - y)**2)                                  h2 = math.sqrt((x2 - goal[0])**2 + (y2 - goal[1])**2)                                  f2 = g2 + h2                             else:                                  g2 = g + delta[i][2]                                              h2 = math.sqrt((x2 - goal[0])**2 + (y2 - goal[1])**2)                                  f2 = g2 + h2                              open.append([f2,g2,h2,x2,y2])                             #we add them to our open list                             pltx.append(y2)                             plty.append(-x2)                             #print('append list item')                             #print([g2,x2,y2])                             #Then we check them to never expand again                             closed[x2][y2] = 1                             action[x2][y2] = i      for i in range(len(expand)):         print(expand[i])     print()     policy=[[' ' for row in range(len(grid[0]))] for col in range(len(grid))]     x=goal[0]     y=goal[1]     policy[x][y]='*'     visx = [y]     visy = [-x]     while x !=init[0] or y !=init[1]:         x2=x-delta[action[x][y]][0]         y2=y-delta[action[x][y]][1]         policy[x2][y2]= delta_name[action[x][y]]         x=x2         y=y2         visx.append(y)         visy.append(-x)     for i in range(len(policy)):         print(policy[i])     print()          plt.plot(visx,visy, "-r")      plt.show()  search() 

Here is below my output:

output

how to remove line break ‘%0D’ from file name

I want to download some data using wget command from list of files, I used foll. code:

    foreach file(`cat Model_list1.txt`)       echo $  file      wget https://jeodpp.jrc.ec.europa.eu/ftp/jrc-opendata/LISCOAST/10011/LATEST/EURO-CORDEX/EUR-11/SMHI-RCA4/"$  file"/BC/historical/prAdjust_EUR-11_"$  file"_historical_r1i1p1_SMHI-RCA4_v1-JRC-SBC-EOBS10-1981-2010_day_19810101-20101231.nc.gz end 

However, for every file name I am getting %0D at the end of the file name. I tried sed as follow to change the name of the file located in the file Model_list but still I am getting the same error. Kindly help me out. Thanks

sed 's/%0D//g' Model_list.txt > Model_list1.txt 

How to stop systemd.tmfiles-clean service command line

The daily job to clean temp files is causing a crash (hard reboot necessary), how can I disable it? Which file do I need to modify and add “Disabled” in the configuration?

The exact message in the logs is: systemd-udevd[483]: seq 7491 ‘/kernel/slab//:A-0000256/cgroup/filp(1880:systemd-tmpfiles-clean.service)’ is taking a long time

systemd-udevd[483]: seq 7492 ‘/kernel/slab//:aA-000192/cgroup/dentry(1880:systemd-tmpfiles-clean.service)’ is taking a long time

After that 2nd message, the system was unresponsive and required a switch off/on.

The graphical interface is xfce with minimal tools installed and pretty unstable too, so I’d rather do command lines/edit files manually.

Thanks for your help!

Greg

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.

No command line access after running maldel

I am using Ubuntu 18 LTS with Unity desktop. I installed, and ran, maldet (Linux Malware Detect (LMD)) on the whole disk. When I came back to check the results, the terminal window was blank. I tried all the settings, including making the background white and the text black, but it is still blank and still does not respond to the keyboard. Sometimes the window does not even open. It flashes and disappears. When it does open, it is always blank with no keyboard response.

I installed MATE term. It also just flashes and goes away. xterm and uterm did not even open. I installed, and launched, TMX, but it returned

bash: /usr/bin/sudo: Permission denied 

every time I tried a command with sudo in it. (It did not ask for my password.)

When I tried ctrl-alt-F3, I got a terminal but, as soon as I entered my user-name and password, it flashed and went back to asking for my username again.

I had the best luck with PowerShell. It allowed me to enter

 sudo apt-get install --reinstall gnome-terminal 

I get

Reading package lists... Done Building dependency tree        Reading state information... Done The following package was automatically installed and is no longer required:   libllvm7 Use 'sudo apt autoremove' to remove it. 0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 32 not     upgraded. Need to get 160 kB of archives. After this operation, 0 B of additional disk space will be used. Get:1 http://us.archive.ubuntu.com/ubuntu bionic-updates/main amd64     gnome-terminal amd64 3.28.2-1ubuntu1~18.04.1 [160 kB] Fetched 160 kB in 0s (1,242 kB/s)       (Reading database ... 231629 files and directories currently     installed.) Preparing to unpack .../gnome-terminal_3.28.2-    1ubuntu1~18.04.1_amd64.deb ... Unpacking gnome-terminal (3.28.2-1ubuntu1~18.04.1) over (3.28.2-    1ubuntu1~18.04.1) ... Processing triggers for mime-support (3.60ubuntu1) ... Processing triggers for desktop-file-utils (0.23-1ubuntu3.18.04.2) ... Processing triggers for libglib2.0-0:amd64 (2.56.4-0ubuntu0.18.04.4)     ... Setting up gnome-terminal (3.28.2-1ubuntu1~18.04.1) ... Processing triggers for man-db (2.8.3-2ubuntu0.1) ... Processing triggers for gnome-menus (3.13.3-11ubuntu1.1) ... 

I cannot get the computer to go to the command/restore mode when I reboot. I try holding down the shift key but it goes straight to desktop.

Everything else appear to work fine. It is just anything to do with a terminal where I have problems. I could just use PowerShell but it seems that something is seriously wrong with my terminal functions as a result of using maldet. Also, when I click on the terminal icon, I get the non-functional gnome terminal instead of PowerShell although PowerShell shows the terminal icons in favorites. I was hoping there would be a way to fix it.

I got maldet (LMD) from http://wwwrfxncom

using

wget http://www.rfxn.com/downloads/maldetect-current.tar.gz 

how to install nvidia drivers by command line?

I have a laptop with a Nvidia gtx 1050 running in parrot os. The problem is that it looks like the system does not detect the Nvidia hardware as a graphic card, i’ve tried to install the drivers by the official site of Nvidia but the system got bugged or else and i cant see anything but the command line(there’s not graphic enviroment).

I saw that in the repositories there are a lot of content about Nvidia, and I would like to install them (drivers) by command line, because looks like the programs of the system does not work nice with programs with property code, so thats why I want to get em from the repositories.

This is the result of “lspci | grep VGA” :

00:02.0 VGA compatible controller: Intel Corporation UHD Graphics 630 (Mobile) 

As you can see it does not recognice the Nvidia hardware…But if i execute this command alone

lspci  00:00.0 Host bridge: Intel Corporation 8th Gen Core Processor Host Bridge/DRAM Registers (rev 07) 00:01.0 PCI bridge: Intel Corporation Skylake PCIe Controller (x16) (rev 07) 00:02.0 VGA compatible controller: Intel Corporation UHD Graphics 630 (Mobile) 00:12.0 Signal processing controller: Intel Corporation Cannon Lake PCH Thermal Controller (rev 10) 00:14.0 USB controller: Intel Corporation Cannon Lake PCH USB 3.1 xHCI Host Controller (rev 10) 00:14.2 RAM memory: Intel Corporation Cannon Lake PCH Shared SRAM (rev 10) 00:14.3 Network controller: Intel Corporation Wireless-AC 9560 [Jefferson Peak] (rev 10) 00:16.0 Communication controller: Intel Corporation Cannon Lake PCH HECI Controller (rev 10) 00:17.0 SATA controller: Intel Corporation Cannon Lake Mobile PCH SATA AHCI Controller (rev 10) 00:1b.0 PCI bridge: Intel Corporation Cannon Lake PCH PCI Express Root Port (rev f0) 00:1d.0 PCI bridge: Intel Corporation Cannon Lake PCH PCI Express Root Port (rev f0) 00:1e.0 Communication controller: Intel Corporation Device a328 (rev 10) 00:1f.0 ISA bridge: Intel Corporation Device a30d (rev 10) 00:1f.3 Audio device: Intel Corporation Cannon Lake PCH cAVS (rev 10) 00:1f.4 SMBus: Intel Corporation Cannon Lake PCH SMBus Controller (rev 10) 00:1f.5 Serial bus controller [0c80]: Intel Corporation Cannon Lake PCH SPI Controller (rev 10) 01:00.0 3D controller: NVIDIA Corporation GP107M [GeForce GTX 1050 Mobile] (rev a1) 02:00.0 Ethernet controller: Qualcomm Atheros QCA8171 Gigabit Ethernet (rev 10) 03:00.0 Non-Volatile memory controller: Kingston Technologies Device 5008 (rev 01) 

Here in the line :

01:00.0 3D controller: NVIDIA Corporation GP107M [GeForce GTX 1050 Mobile] (rev a1) 

detect the grafic card but not as a graphic hardware WTF!!! ;_;

How to get to command line

Some well-meaning person installed Ubuntu on my wife’s formerly Windows laptop. She hadn’t used it for years before I married her. I haven’t used Ubuntu since fifteen or twenty years ago myself, so of course the GUI is completely different. (Actually, I had Kubuntu back then.)

It has auto-login to her admin account but she doesn’t know the password. The search function in the GUI cannot locate any *.jpg in /home although I know there are hundreds of them in one folder on the desktop.

So, I want to open a shell window to use find

There are a lot of icons in the launcher/task bar/dock/whatever it’s called but none of them are a terminal emulator.

The “software center” shows several terminal emulators installed, but I can’t launch any of them, and the “more info” buttons do nothing.

I want to find all of her pictures to put them on a newer machine and retire this one. I can pull the disk and hook it up directly to another laptop (where I have root access) but it would be more pleasant to just type commands. 🙂