Number of `m` length walks from a vertice with steps in [1, s]

The problem is stated as the following:

We are given a grid graph $ G$ of $ N \times N$ , represented by a series of strings that describe vertices s.t.

  • $ L$ is the vertice we’re interested in
  • $ P$ are vertices that are unavailable
  • $ .$ are vertices that are available

e.g.:

....  ...L  ..P.  P... 

Would mean a graph that looks like this

   0    1    2    3  +-------------------+ 0|    |    |    |    |  |    |    |    |    |  +-------------------+ 1|    |    |    |    |  |    |    |    |    |  +-------------------+ 2|    |    |XXXX|    |  |    |    |XXXX|    |  +-------------------+ 3|XXXX|    |    |    |  |XXXX|    |    |    |  +-------------------+ 

Where $ v_{2,3}$ and $ v_{0,3}$ are unavailable and we’re interested in $ v_{3,1}$ .

From each vertice we’re only allowed to move on the axis (we can’t move on the diagonal) and a move is valid from $ v_{x,y}$ to $ v_{q,p}$ if

  • $ |x-q| + |y-p| \leq s$ and $ v_{q,p}$ is available.
  • Staying in the same spot is also a valid move

Given $ m$ – maximal number of moves and $ s$ what is the number of ways we can make $ m$ moves from vertice designated by $ L$ .

My attempt was to

  • First compute the neighbors reachable from each node. Create a look s.t. $ \forall v N[v]$ is the list of reachable nodes from $ v$
  • Then build a starting record $ M_0$ s.t. if node is reachable $ M[i][j] = 1$ and $ 0$ otherwise.
  • Then for each step calculate for $ \forall i,j \in N$ (all the grid) $ M_{i}[i][j] = \sum_{v\in N[v]} M_{i-1}[v_i][v_j]$ (where $ v_i, v_j$ are the coordinates of $ v$ on the grid) and store in a matrix $ M_i$

We iterate until $ i==m$ .

  1. for each $ v_{i,j}$ : 1. for each neighbor $ n$ of $ v_{i,j}$ : 1. $ M[i][j] += M'[n_i][n_j]$

Unfortunately this doesn’t work (tried to do it with a pen and paper as well to make sure) and I get fewer results then the expected answer, apparently there should be 385 ways but I only get to 187.

Here are the intermediate states for the above mentioned board:

----------------------------    5   6   5   5     5   7   6   6     4   6   0   5     0   5   4   5   ----------------------------   25  34  27  27    27  41  33  34    20  33   0  27     0  27  20  25   ----------------------------  133 187 146 149   146 229 182 187   105 182   0 146     0 146 105 133   ---------------------------- 

This did work for e.g. m=2 and s=1 for the following board:

   0   1   2  +---+---+---+ 0|   |   |   |  |   |   |   |  +-----------+ 1|   |   |   |  |   |   |   |  +-----------+ 2|   |   |   |  |   |   |   |  +---+---+---+ 

Here’s my reference code (findWalks is the main function)

using namespace std; using Cord = std::pair<size_t, size_t>;  auto hash_pair = [](const Cord& c) {     return std::hash<size_t>{}(c.first) ^ (std::hash<size_t>{}(c.second) << 1); };  using NeighborsMap = unordered_map<Cord, vector<Cord>, decltype(hash_pair)>;   inline vector<vector<int>> initBoard(size_t n) {     return vector<vector<int>>(n, vector<int>(n, 0)); }   Cord findPOI(vector<string>& board) {     for (size_t i=0; i < board.size(); i++) {         for (size_t j=0; j < board.size(); j++) {             if (board[i][j] == 'L')             {                 return make_pair(i, j);             }         }     }     return make_pair(-1, -1); }   NeighborsMap BuildNeighbors(const vector<string>& board, size_t s) {     NeighborsMap neighbors(board.size() * board.size(), hash_pair);      for (size_t i = 0; i < board.size(); i++)     {         for (size_t j = 0; j < board.size(); j++)         {             size_t min_i = i > s ? i - s : 0;             size_t max_i = i + s > board.size() - 1 ? board.size() - 1 : i + s;             size_t min_j = j > s ? j - s : 0;             size_t max_j = j + s > board.size() - 1 ? board.size() - 1 : j + s;              auto key = make_pair(i, j);               if (board[i][j] != 'P')             {                 for (size_t x = min_i; x <= max_i; x++)                 {                     if (board[x][j] != 'P' && x != i)                     {                         neighbors[key].push_back(make_pair(x, j));                     }                 }                  for (size_t y = min_j; y <= max_j; y++)                 {                     if (board[i][y] != 'P' && y != j)                     {                         neighbors[key].push_back(make_pair(i, y));                     }                 }                 neighbors[key].push_back(key);             }             else             {                 neighbors[key].clear();             }         }     }      return neighbors; }  int GetNeighboursWalks(const Cord& cord, NeighborsMap& neighbors, const vector<vector<int>>& prevBoard) {     int sum{ 0 };     const auto& currentNeighbors = neighbors[cord];     for (const auto& neighbor : currentNeighbors)     {         sum += prevBoard[neighbor.first][neighbor.second];     }     return sum; }   int findWalks(int m, int s, vector<string> board) {     vector<vector<int>> currentBoard = initBoard(board.size());     vector<vector<int>> prevBoard = initBoard(board.size());     std::unordered_map<int, std::vector<Cord>> progress;      auto poi = findPOI(board);     NeighborsMap neighbors = BuildNeighbors(board, s);     for (const auto& item : neighbors)     {         const auto& key = item.first;         const auto& value = item.second;         prevBoard[key.first][key.second] = value.size();     }      for (size_t k = 1; k <= static_cast<size_t>(m); k++)     {         for (size_t i = 0; i < board.size(); i++)         {             for (size_t j = 0; j < board.size(); j++)             {                 auto currentKey = make_pair(i, j);                 currentBoard[i][j] = board[i][j] != 'P' ? GetNeighboursWalks(currentKey, neighbors, prevBoard) : 0;             }         }          std::swap(currentBoard, prevBoard);     }     return prevBoard[poi.first][poi.second]; } 

CFG to CNF, but stuck on the last few steps

I recently learned about the conversion, but I seem to be stuck.

I need to convert the following CFG to CNF:

$ S → XY$

$ X → abb|aXb|e$

$ Y → c|cY$

  1. There is no S on the right side, so I did not need to add another
  2. I removed the null productions $ X → e$

$ S→XY|Y$

$ X→abb|aXb|ab|$

$ Y→c|cY|$

  1. I removed unit production $ S→Y$ $ Y→c$ with $ S→c$

  2. There are no production rules which have more than 2 variables

  3. Here, I struggle. I am not allowed to have a terminal symbol and a variable together, but I am not sure how to get rid of these.

New grammar after step 4:

$ S→XY|c$

$ X→abb|aXb|ab$

$ Y→ZY$

$ Z→c$

I managed to replace the symbol c with Z, and added the new rule, so that seems fixed. However, I am unsure what do do with $ aXb$ .

Is this okay so far? if yes, what step should i take next?

Thank you in advance!

Setting different steps for Y-Axes of ListPlot

I am trying to set the scaling interval of my Y-Axes different than Mathematica automatically does. So in steps of 1000 instead of 2000 (see picture)

At the moment I determined following PlotRange:

PlotRange -> {{1, 10}, {0, 8000}} 

enter image description here

Is there a simple option?

To get an overview over the command:

ListPlot [   MapThread[    If[Or[#1[[1]] === 3., #1[[1]] === 8.],       Callout[Tooltip[#1, #2], #2], Tooltip[#1, #2]] &, Annotated2],    FrameLabel -> {"Happiness Score",      "Education Expenditure (per capita)"}, Frame -> True,    GridLines -> Automatic, LabelStyle -> {GrayLevel[0]},    PlotRange -> {{1, 10}, {0, 8000}}] // Framed 

Design for grouping undo steps when editing text

Some undo for text editor editors handle text input differently.

  • Every key press is a single undo step.
    Typing in a word N characters long, requires N undo steps.
  • Undo steps use word boundaries
    Undoing will undo each word entered.
  • Undo steps use timer-based boundaries
    If you stop typing N milliseconds – this adds an undo step.
  • Undo steps add boundaries every N characters entered.

Given these different ways of handling undo for text input, are there strong reasons to pick one of these over another?

What are the exact steps to establish a HTTPS/SSL connection?

Before asking this question I got through a lot of posts for finding a simple explanation about:

  • How an HTTPS/SSL connection establishes?

but I could not find a good one, in addition here, i can ask more question until it becomes clear for me, it may also be helpful for many others. And also there is another question Related to this topic:

  • How the client generates the privet key?

Auto-skipping steps on progress trackers

We are implementing a progress tracker for a 3 step task. However, step 2 (‘review step 1’) is not always applicable; it’s only applicable if one validation check after the submission of step 1 fails. If the check PASSES, should we jump straight to step 3 and skip step 2? Or should we always go to step 2?

The steps are visible on the UI, so I’m concerned users may see they’ve gone from step 1 to 3 without understanding why. However, taking them to step 2 is a bit pointless, as the only action they’ll have to do is ‘go to step 3’. In essence, we’d be saving them a click.

Thanks

Minimum steps involved for an effective and efficient website redesign process?

I just started working for a web development agency, we work mainly with government so we want to align ourselves within that market with a professional, creative and functional website. We have a great blog and want to highlight our content and whitepapers, plus who we are, our vision and services.

We just started the Discovery phase of the project, and are in the process of doing personas and user journey mapping. I work there in project support and partly as a junior UX designer, alongside the contract designer, who is more of a UI designer than a UX designer, so it’s a bit of a learn as we go process. BUT we have a pretty strict deadline of Christmas where we’d like to have the final designs signed off, so we can start developing the site in January.

Our current plan/timeline is: – initial planning including pain points and wants for our existing website (done) – persona planning (done) – user journey mapping and doing value journey canvas for our 4 personas (in process) – content analysis – IA card sorting, treejacking, review and iteration – component mapping and content architecture – sketching session of new components – wireframing all vanilla pages – wireframing custom pages – prototyping key user journeys for customer testing – customer testing script – audience testing – prepare customer insights deck to present – presentation of customer insights – refine prototypes/wireframes – UI: Theme and Brand – UI Review

Which is quite a lot and definitely won’t get done by Christmas this year. So my question, is what is the absolute minimum process required for doing a website redesign?

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is:

Is there a word $ w$ on which a TM M $ M$ halts after a maximum of $ |w|$ (word length) steps?

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn’t a proof and I have to proofe this question (without the Rice’s theorem).

My idea was to use the subroutine technique to “convert” the problem into the halt-problem, the $ \epsilon$ -halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one – could you help me here please?

Port Scanning: Question about next steps after Zenmap port scan

I am very new to offensive security

I have done a nmap scan on a public IP, its showing 4 ports open and the OS is undetectable, I have no idea how to proceed further, I appreciate any next steps further in this case. Below is a snippet from nmap output:

Not shown: 995 closed ports PORT     STATE    SERVICE      VERSION 25/tcp   filtered smtp 135/tcp  filtered msrpc 139/tcp  filtered netbios-ssn 445/tcp  filtered microsoft-ds 6009/tcp filtered X11:9  Warning: OSScan results may be unreliable because we could not find at least 1 open and 1 closed port Aggressive OS guesses: ISS Proventia GX3002 firewall (Linux 2.4.18) (97%), Linux 2.6.22 (Debian 4.0) (97%), CMI Genus NEMA terminal (95%), D-Link DGS-1210 switch (95%), D-Link DI-604 wireless broadband router (95%), Efficient Networks SpeedStream 4100 ADSL router (95%), FreeBSD 6.1-RELEASE (95%), IBM i 6.1 (95%), Cobalt Qube 2700WG (Linux 2.0.34) (95%), Linux 2.4.20 (95%) No exact OS matches for host (test conditions non-ideal). 

Real time filtering or Wizard steps

At this moment, I’m working on a product finder tool. By answering different questions, you get advice that suggests a product of your interest. So, the answers to questions could lead to different follow-up questions. This process isn’t linear.

I notice while designing that there are different ways to approach this. – A Wizard gives clear steps that help to create focus and guides through finding the right product. – At the same time, we want to create something which provides the user with the possibility to realtime change things and play around with the settings to get a different result very fast. But I noticed that accordions are getting though and not the flexibility that we want.

I put some quick wireframes to give a better understanding of the context. Any suggestions on this case? Examples are appreciated! enter image description here enter image description here enter image description here