Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, in some sense. However, is this an interesting question worth worrying about? Are there practical situations, where there is some benefit in reducing a more complicated language to a context free language?

# Tag: given

## Given two Quadratic Congruence find the prime

Given:

`x^2 - a = 0 (mod p) y^2 - b = 0 (mod p) `

x, y, a and b are given. Find prime p efficiently.

x, y, a, b, p are of order 10^9

## Choosing the best fit from given plots

I have some data:

`x={1,2,3,4,5,6,7,8,9,10} y={3.05,21.05,69.05,162.05,315.05,543.05,861.05,1284.05,1827.05,2505.05} `

That I plot with `ListPlot`

. I have two functions that I would like to check which one of them best fits my data. The functions are:

`f1[x_]:=0.5 x + (4/2) x^3 f2[x_]:=0.5 x + (5/2) x^3 + 80 `

and I plot them along with data points that I have I get a plot:

Function `f2`

is plotted red, and function `f1`

is plotted blue. Function `f2`

is seems to be the best fit to data points, but is there a way in which I can in Mathematica check this, not by using something like `FindFit`

or `NonlinearModelFit`

, but instead calculating say distances between points and plots and see which function gets data points closer to it. Is this a correct way of thinking about fitting? Is there a code that allows checking how close are data points to some model function, or two of them or even more?

## Finding Largest word in a given text file

So I am working on this problem involving finding the largest word in a given text file using python. I already Wrote a Code But want to find if there is a more efficient way to go by this problem. Help is appreciated!!

I’ve already achieved the goal i just want to find a more efficient way to do this.

Here’s my code:

def largestWord(filename): length = {} maxValue = 0 with open(filename, ‘r’) as infile: for line in infile.readlines(): listOfWords = line.split() for word in listOfWords: length[word] = len(word) //makes a dictionary where the key is the word and the value is the length of the word. for value in length.values(): //Iterating through the values of the if value > maxValue: maxValue = value dictionary to find the highest value and then comparing with values form the keys to return the word

` for k in length.keys(): if length[k] == maxValue: print(k) `

largestWord(filename)

Want a shorter piece of code.

## 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.

## Given N integers in a round fashion, how to choose them in pairs to minimise newly added number sum?

N integers A_{1},A_{2},….A_{N} are arranged on circle such that A_{i} is adjacent to A_{i+1} .Also A_{N} is adjacent to A_{1}. We can choose two adjacent integers (say A_{j},A_{j+1}) and keep integer with value A_{j}+A_{j+1} in between them on the circle .Then we can remove A_{j},A_{j+1} from the circle. We can keep doing this until one integer is left on circle i.e total N-1 times.We need to minimise sum of numbers that were added on the circle by us. Example – 20,10,3 (in sequence) are arranged on circle.Then first we can choose 10,3 .Now sequence becomes 20,13.Then we choose 20,13 and final sequence becomes 33. Hence sum of numbers that we added on circle is 13 + 33 = 46. This is the minimum sum possible. What will be the general procedure to solve this problem ?

## Is is possible to determine if a given number is xor combination of some numbers?

I have been given a number Y which is ($ a$ **xor** $ b$ **xor** $ c$ **xor** $ d$ **xor** $ e$ ) of some numbers ($ a$ ,$ b$ ,$ c$ ,$ d$ ,$ e$ ) and another no X. Now i have to determine if X is a xor combination of ($ a$ ,$ b$ ,$ c$ ,$ d$ ,$ e$ )

e.g – ($ a$ **xor** $ d$ ) , ($ b$ **xor** $ c$ **xor** $ e$ ) , ( $ a$ **xor** $ e$ )

What i know clearly is that lets say X= ($ b$ **xor** $ d$ ) , Now if I xor X and Y i get ($ a$ **xor** $ c$ **xor** $ e$ ), as ( $ b$ **xor** $ b$ =0 ) and if it was some number not a xor combination (say $ p$ ) then i would have got ($ a$ **xor** $ b$ **xor** $ c$ **xor** $ d$ **xor** $ e$ **xor** $ p$ )

How should i approach this question?

## Permute an array in O(n) time with O(1) extra space with a given ordering function?

This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0).

Given a sorted (ascending order) array $ A$ of $ N$ numbers, re-arrange the elements of A to be this order: [A[n-1], A[0], A[n-2], A[1], A[n-3], A[2], …]. While the problem does not actually call for this specific index permutation, that’s the approach I took (it will yield the correct answer). If there is a solution that does not involve this approach, I’m interested to see it, but this question specifically is about whether or not it is possible to perform this specific data value re-arrangement without regards to the values stored in the array.

In other words, alternately interleave the maximum, minimum, 2nd-maximum, 2nd-minimum, etc. The algorithm should run in $ O(n)$ time and consume only $ O(1)$ extra space. It should work regardless of the data values in the array, including scenarios with duplicate values.

Solutions for $ O(n^2)$ time with $ O(1)$ space and $ O(n)$ time with $ O(n)$ space are straightforward.

There is a simple function that given a source index in the initial sorted array, determines its destination index in the re-arranged array. I have a partial solution that works by starting at some index and moving through the cycles of source $ =>$ destination element moving. But I couldn’t find a way to compute the locations of all the separate index-moving cycles. Instead, after completing a cycle, I search the partially re-arranged array for pairs of values that haven’t been moved yet (that hold the original, not new, ordering), and use those indices to start a new cycle (this probably means my solution is not $ O(n)$ time because of this search). But this doesn’t work in general if the elements of the initial array contain duplicate values.

I have an intuition that there must must be an algorithmic move/swap index ordering dependent only on N, but I haven’t been able to find one.

## Algorithm for answering queries of the type “largest interval contained in the given interval”

I have been wondering over the following problem:

Given a set $ S$ of intervals on the number line. We can do two operations on them:

- Add a new interval $ [l,r]$ to $ S$
- Given an interval $ [ql, qr]$ , which is possibly not in $ S$ , find the longest interval from $ S$ which is contained entirely in $ [ql, qr]$

If I didn’t have operation $ 1$ I have found a solution using a persistent segment tree.

For the full version, there is the trivial solution which runs in $ O(QN)$ . I also found that using interval tree, I can directly find which intervals intersect the query interval and then I can check them manually. However, is there an even better solution? Maybe $ O(NlogN)$ or $ O(Nlog^2N)$

## Finding the next total Solar Eclipse over a given latitude and longitude?

What is a reasonable way to code the title question in Mathematica? Trying the following gave Polygons over GeoPositions over Lists of pairs, but just digging into these seemed inelegant. Besides, there may be a more general way than what I’ve guessed below.

Also, is there a better way of searching for Solar Eclipses over a given time frame than what I’ve ventured below? Many thanks.

`SolarEclipse[{DateObject[{2010, 1, 1, 0, 0}], DateObject[{2030, 1, 1, 0, 0}], All}, "TotalPhasePolygon", EclipseType -> "Total"] `