matching – Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7)

I’m working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

Some of your friends are working for CluNet, a builder of large
communication networks, and they are looking at algorithms for
switching in a particular type of input/output crossbar. Here is the
setup. There are n input wires and n output wires, each directed from
a source to a terminus. Each input wire meets each output wire in
exactly one distinct point, at a special piece of hardware called a
junction box. Points on the wire are naturally ordered in the
direction from source to terminus; for two distinct points x and y on
the same wire, we say that x is upstream from y if x is closer to the
source than y, and otherwise we say x is downstream from y. The order
in which one input wire meets the output wires is not necessarily the
same as the order in which another input wire meets the output wires.
(And similarly for the orders in which output wires meet input wires.)
Figure 1.8 gives an example of such a collection of input and output
wires. Now, here’s the switching component of this situation. Each
input wire is carrying a distinct data stream, and this data stream
must be switched onto one of the output wires. If the stream of Input
i is switched onto Output j, at junction box B, then this stream
passes through all junction boxes upstream from B on Input i, then
through B, then through all junction boxes downstream from B on Output
j. It does not matter which input data stream gets switched onto which
output wire, but each input data stream must be switched onto a
different output wire. Furthermore—and this is the tricky
constraint—no two data streams can pass through the same junction box
following the switching operation. Finally, here’s the problem. Show
that for any specified pattern in which the input wires and output
wires meet each other (each pair meeting exactly once), a valid
switching of the data streams can always be found—one in which each
input data stream is switched onto a different output, and no two of
the resulting streams pass through the same junction box.
Additionally, give an algorithm to find such a valid switching.

figure 1.8

This is the algorithm I’ve came up with so far:

  1. Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
  2. Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
  3. Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
  4. Return the set M of input-to-output wire matchings

I’m having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven’t made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions – then no instability can exist.

On chapter 25 of Growing Object Oriented Software. Which books should I read to understand it?

I am reading Growing Object Oriented Software by Steve Freemen and Nat Pryse.
I leaned about TDD cycle and the Hexagonal Pattern or Ports and adapters pattern.
Authors describe application(if it’s the correct term) as a web of objects interacting via messages.
Now, on chapter 25 I stopped as I do know about persistence or anything written beyond this point.
I need advise/suggestions on which book to read to get these concepts.
Also I want to know what is DDD, Event Sourcing, what is application layer, service layer and other concepts.
A list of books if in order will be much more helpful.
I have read Principles Patterns & Practices by Robert C. Martin and Test-Driven Development by Kent Beck before.

TL;DR- I am beginner read PPP by Robert C. Martin then TDD by Kent Beck before. Currently on chapter 25 of GOOS, Unable to understand, which book should I read to get the concepts.

smooth manifolds – do Carmo Differential forms and application Chapter 2 Exercise 6

Line integrals are quite useful in the study of complex functions $f:Bbb Cto Bbb C$. Here the complex plane $Bbb C$ is identified with $Bbb R^2$ by setting $z=x+iy$, $zinBbb C$, $(x,y)inBbb R^2$. It is convenient to introduce the complex differential form $dz = dx+idy$ and to write
$$ f(z) =u(x,y)+iv(x,y) = u+iv.$$
Then the complex form
$$f(z)dz = (u+iv)(dx+idy) = (udx-vdy)+i(udy+vdx)$$
has $udx-vdy$ as its real part and $udy+vdx$ as its imaginary part. Define
$$int_c f(z) dz = int_c(udx-vdy)+iint_c(udy+vdx)$$
Assume that $u,vin C^1$. Recall that $f$ is holomorphic if and only if $u_x = v_y, u_y = -v_x$

Question. If $f$ is holomorphic, the function $f'(z)$ (the derivative of $f$ in $z$) given by the equation $df:=du+idv = f'(z)dz$ is well defined and $f'(z) = u_x-iu_y$.

In the question I what should I check for well definedness?

javascript – Show contents in a book chapter and sections in a highly normalized repository

I want to present books that has chapters and sections, and contents in each book, chapter and section.

This is my schema:

type BookId = string
type ChapterId = string
type SectionId = string
type ContentId = string


export type SourceId =
| ChapterId
| SectionId
| BookId


type Book = {
  id: BookId,
  name: string,
}

type Chapter = {
  id: ChapterId,
  bookId: BookId,
  name: string
}
type Section = {
  id: SectionId,
  chapterId: ChapterId,
  name: string
}

type Content = {
  id: ContentId,
  sourceId: SourceId,
  name: string,
  content: string
}

This is how I query all the books, chapters and sections:

 list() {
    return this.bookRepo.all().then(books =>
      Promise.all(books.map(book =>
        Promise.all((
          this.bookRepo.contents(book.id),
          this.bookRepo.chapters(book.id)
        )).then(((contents, chapters)) =>
          Promise.all(chapters.map(chapter =>
            Promise.all((
              this.bookRepo.contents(chapter.id),
              this.bookRepo.sections(chapter.id)
            )).then(((contents, sections)) =>
              Promise.all(sections.map(section =>
                this.bookRepo.contents(section.id).then(contents => (
                  section, contents
                ))))
                .then(sections => (chapter, contents, sections)))))
            .then(chapters => (book, contents, chapters))))));
  }

I just render as json at the moment, but the query code seems hard to maintain.

Chapter numbering is different in desktop word and when opened within browser

I have a document (stored on a sharepoint site) with different heading levels, e.g: 1, 1.1, 1.2, 1.2.1
This looks fine in desktop word application. But if I open the same document within a browser then the chapter numbering looks like: 1, 2, 3, 4
Desktop
Browser
What might be the reason for this and how can I fix it?

real analysis – Baby Rudin : Chapter 2 : Basic Topology, page number : 28, 2.10(b)

I’m reading the “Baby Rudin” book and one particular example (which is very trivial, I guess but) I couldn’t understand properly. I’m stating the problem and the answer here.

I want the visual and logical undertsnading of this problem.

(Chapter 2 : Basic Topology, page number : 28, 2.10(b)) :

Let $A$ be the set of real numbers such that $0 < x leq 1$. Fro every
$x in A$, let $E_{x}$ be the set pf real numbers $y$ such that $0 <y
> <x$
. Then

(i) $E_{x} subset E_{z}$ if and only if $ 0 <x leq z leq 1$;

(ii) $bigcup_{x in A} E_{x} = E_{1}$;

(iii) $bigcap_{x in A} E_{x}$ is empty;

(i) and (ii) are clear. To prove (iii), we note that for every $y>0$,
$y notin E_{x}$ if $x<y$. Hence $y notin bigcap_{x in A} E_{x}$.

My (worng?) undertsanding :

(i) From the concept of equality it’s obvious. Am I right? What’s the proper explanation of this?

(ii) How it’s $bigcup_{x in A} E_{x} = E_{1}$? Didn’t unfderstand.

(iii) For this one with th egiven hint, I tried to think as points in the ral line $x$, but I can’t convince myself enough with imagination and logics.

P.s : There are already some answers on this same topic (but not on all 3 points) , but I need the answers in more details in all 3 points, like visually with some sketches in real line, I hope this question will not get duplicated.

beginner – Company database REPL program in Rust for Chapter 8 of The Book

I implemented a solution for the third exercise of Chapter 8 of The Book. I’m still trying to build my intuition for what makes a good Rust program and so would really appreciate some pointers to help me improve. Here’s my current solution:

// Using a hash map and vectors, create a text interface to allow a user to
// add employee names to a department in a company. For example, “Add
// Sally to Engineering” or “Add Amir to Sales.” Then let the user retrieve
// a list of all people in a department or all people in the company by
// department, sorted alphabetically.

// @todo Add functions to remove people, departments and companies. Add a clear function.

use std::collections::HashMap;
use std::collections::HashSet;
use std::io;
use std::io::Write;

#(derive(Debug, PartialEq, Eq, Hash, Clone, PartialOrd, Ord))
struct Employee(String);
#(derive(Debug))
struct Department(HashSet<Employee>);
#(derive(Debug))
struct Company(HashMap<String, Department>);

fn make_company() -> Company {
    Company(HashMap::new())
}

#(derive(Debug))
struct ExistingDepartment(String);

// This assumes all department names are unique.
fn add_department(company: &mut Company, department: &str) -> Result<(), ExistingDepartment> {
    let department_name = String::from(department);
    match company.0.contains_key(&department_name) {
        true => Err(ExistingDepartment(department_name)),
        false => {
            company
                .0
                .insert(department_name, Department(HashSet::<Employee>::new()));
            Ok(())
        }
    }
}

#(derive(Debug))
enum AddEmployeeError {
    NonexistentDepartment(String),
    ExistingEmployee(Employee),
}

// This assumes that all employee names in a department are unique.
fn add_employee(
    company: &mut Company,
    department_name: &str,
    employee: Employee,
) -> Result<(), AddEmployeeError> {
    match company.0.get_mut(department_name) {
        None => Err(AddEmployeeError::NonexistentDepartment(String::from(
            department_name,
        ))),
        Some(department) => match department.0.insert(employee.clone()) {
            true => Ok(()),
            false => Err(AddEmployeeError::ExistingEmployee(employee)),
        },
    }
}

#(derive(Debug))
struct NonexistentDepartment(String);

fn get_employees_department(
    company: &Company,
    department_name: &str,
) -> Result<Vec<Employee>, NonexistentDepartment> {
    match company.0.get(department_name) {
        None => Err(NonexistentDepartment(String::from(department_name))),
        Some(department) => {
            let mut result: Vec<Employee> = department.0.iter().cloned().collect();
            result.sort_unstable();
            Ok(result)
        }
    }
}

fn get_employees_company(company: &Company) -> Vec<Employee> {
    let mut result = company
        .0
        .keys()
        .map(|department| get_employees_department(company, department).unwrap())
        .collect::<Vec<Vec<Employee>>>()
        .concat();
    result.sort_unstable();
    result
}

fn format_slice(slice: &(Employee)) -> Option<String> {
    match slice.len() {
        0 => None,
        _ => Some(
            slice
                .iter()
                .map(|employee| employee.0.to_string())
                .collect::<Vec<String>>()
                .join("n"),
        ),
    }
}

#(derive(PartialEq))
enum GetInput {
    Print,
    Read,
    Parse,
}

#(derive(PartialEq))
enum Mode {
    Greet,
    GetInput(GetInput),
    Quit,
}

struct State {
    mode: Mode,
    company: Company,
    input: String,
}

fn make_state() -> State {
    State {
        company: make_company(),
        mode: Mode::Greet,
        input: String::new(),
    }
}

fn print_flush(input: &str) -> Result<(), std::io::Error> {
    print!("{}", input);
    io::stdout().flush()
}

fn read_line(string: &mut String) -> Result<usize, std::io::Error> {
    string.clear();
    io::stdin().read_line(string)
}

// This assumes that department and employee names don't have whitespace.
fn process_input(state: &mut State) {
    let company = &mut state.company;
    match state.input.len() {
        0 => {
            state.mode = Mode::GetInput(GetInput::Print);
        }
        _ => {
            let tokens: Vec<&str> = state.input.split_whitespace().collect();
            match tokens.get(0) {
                None => {
                    state.mode = Mode::GetInput(GetInput::Print);
                }
                Some(token) => match *token {
                    "quit" => {
                        println!("Bye for now!");
                        state.mode = Mode::Quit;
                    }
                    command => {
                        match command {
                            "add-department" => match tokens(1..).len() {
                                0 => println!("Command "{}" requires at least 1 argument.", command),
                                _ => tokens(1..).iter().for_each(|element| match add_department(company, element) {
                                    Ok(_) => (),
                                    Err(error) => println!("Error: {:?}", error)
                                })
                            },
                            "add-employee" => match tokens(1..).len() {
                                0 ..= 1 => println!("Command "{}" requires at least 2 arguments.", command),
                                _ => match company.0.contains_key(tokens(1)) {
                                    true => tokens(2..).iter().for_each(|employee| match add_employee(company, tokens(1), Employee(employee.to_string())) {
                                        Ok(_) => (),
                                        Err(error) => println!("Error: {:?}", error)
                                    }),
                                    false => println!("Department "{}" doesn't exist.", tokens(1))
                                }
                            },
                            "get-employees" => match tokens(1..).len() {
                                0 => println!("Command "{}" requires at least 1 argument.", command),
                                _ => tokens(1..).iter().for_each(|department| match company.0.contains_key(*department) {
                                    true => match format_slice(&get_employees_department(company, department).unwrap()) {
                                        None => println!("Department "{}" has no employees.", department),
                                        Some(employees) => println!(
                                            "Employees in "{}":
{}", department, employees)
                                    },
                                    false => println!("Department "{}" doesn't exist.", department)
                                })
                            },
                            "get-employees-all" => match format_slice(&get_employees_company(company)) {
                                None => println!("Company has no employees."),
                                Some(employees) => println!(
                                    "Employees:
{}", employees)
                            },
                            "help" => println!(
                                "Commands:

add-department <department_name (department_name ...)>
  Add one or more departments to the company.

add-employee <department_name> <employee_name (employee_name ...)>
  Add one or more employees to a department.

get-employees <department_name (department_name ...)>
  Print a list of employees from one or more departments.

get-employees-all
  Print a list of all employees in the company.

help
  Print this message.

quit
  Quit."
                            ),
                            command => {
                                println!("Invalid command "{}".", command);
                            }
                        }
                        state.mode = Mode::GetInput(GetInput::Print);
                    }
                },
            }
        }
    }
}

fn state_machine(state: &mut State) {
    match &state.mode {
        Mode::Greet => {
            println!(
                "Database program.
Enter "help" for a list of commands."
            );
            state.mode = Mode::GetInput(GetInput::Print);
        }
        Mode::GetInput(get_input_step) => match get_input_step {
            GetInput::Print => {
                println!("Company: {:?}", state.company);
                match print_flush("> ") {
                    Ok(_) => {
                        state.mode = Mode::GetInput(GetInput::Read);
                    }
                    Err(error) => println!("Error {:?}", error),
                }
            }
            GetInput::Read => match read_line(&mut state.input) {
                Ok(_) => {
                    state.mode = Mode::GetInput(GetInput::Parse);
                }
                Err(error) => println!("Error: {:?}", error),
            },
            GetInput::Parse => process_input(state),
        },
        Mode::Quit => (),
    }
}

fn repl(function: fn(&mut State), state: &mut State) {
    while state.mode != Mode::Quit {
        function(state)
    }
}

fn main() {
    repl(state_machine, &mut make_state())
}

I previously tried to refactor the process_input function to try to decrease nesting by moving parts of it to different functions, but I ran across borrowing issues so I stopped trying. I also couldn’t figure out a nice way to implement it such that it accepts inputs that use the same format as the example (i.e., “Add Amir to Sales”), so I did it a little differently.

I’m also not sure if I’m using the Result type nicely and if the tuple structs and enum I made to pass to them are a good way to do error handling.

I also feel like some of the cloning I did is probably unecessary, but I’m not sure how I could refactor them away, so it would be nice to know if that is indeed the case and how I might refactor. In fact, I think it would be helpful to know how I might determine when it is appropriate to clone or when to borrow, as I think I’m a little iffy about that topic.

On a related note, how should I go about writing functions? Is it generally better to initially write functions such that they clone their arguments, then try to refactor the cloning away later on, or to try to borrow everything up front then try to fix any borrow-checker issues that crop up and only clone if I can’t fix them?

In any case, I’d really appreciate any constructive criticisms and advice.

epsilon delta – Spivak Calculus Chapter 5 Problem 10 (b)

I am unsure about how to solve this problem and unfortunately I do not understand the given solution. The problem goes as follows (Spivak, Calculus, 3rd edition, pg. 107, Problem 10-(b)):

Prove that $limlimits_{x to 0} f(x)=limlimits_{x to a} f(x-a)$.

My attempt:

  1. $Rightarrow$“: Let $limlimits_{x to 0} f(x)=m$. Then for every $varepsilon>0$ there is a $delta>0$ such that, for all $x$, if $0<lvert x-0rvert<delta$, then $lvert f(x)-mrvert<varepsilon$. Now let $0<lvert (x-a)-0rvert<delta$ (which can als be written $0<lvert x-arvert<delta$), then $lvert f(x-a)-mrvert<varepsilon$. Thus $limlimits_{x to a} f(x-a)=m$.
  2. $Leftarrow$“: Let $limlimits_{x to a} f(x-a)=m$. Then for every $varepsilon>0$ there is a $delta>0$ such that, for all $x$, if $0<lvert x-arvert<delta$, then $lvert f(x-a)-mrvert<varepsilon$. Now let $0<lvert yrvert<delta$. ($0<lvert y-0rvert<delta$.) This inequality can be written $0<lvert (y+a)-arvert<delta$. It follows that $lvert f((y+a)-a)-mrvert<varepsilon$, which is $lvert f(y)-mrvert<varepsilon$. Thus $limlimits_{y to 0} f(y)=m$ (which is equivalent to $limlimits_{x to 0} f(x)=m$).

Spivak’s solution:

Suppose that $limlimits_{x to a} f(x)=l$, and let $g(x)=f(x-a)$. Then for all $varepsilon>0$ there is a $delta>0$ such that, for all $x$, if $0<lvert x-arvert<delta$, then $lvert f(x)-lrvert<varepsilon$. Now, if $0<lvert yrvert<delta$, then $0<lvert (y+a)-arvert<delta$, so $lvert f(y+a)-lrvert<varepsilon$. But this last inequality can be written $lvert g(y)-lrvert<varepsilon$. So $limlimits_{y to 0} g(x)=l$. The argument in the reverse direction is similar.

My troubles:
Why does he start with $limlimits_{x to a} f(x)=l$? Why can $lvert f(y+a)-lrvert<varepsilon$ be written $lvert g(y)-lrvert<varepsilon$? (If $g(x)=f(x-a)$, then shouldn’t $f(y+a)=g(y+2a)$?) It looks like he is trying to prove $limlimits_{x to a} f(x)=limlimits_{x to 0} f(x-a)$, which is very weird…

python – Automate the Boring Stuff Chapter 8 Sandwich Maker

I am currently learning Python by working my way through Automate the Boring Stuff with Python. This project is from Chapter 8 which is focused on validating input by using the PyInputPlus module. Whenever I finish, I like to look the problem up and compare to other’s solutions to see what I could have done better. However, I can only find a couple of links to this problem. Here is the problem:

Sandwich Maker

Write a program that asks users for their sandwich preferences. The program should use PyInputPlus to ensure that they enter valid input, such as:

  • Using inputMenu() for a bread type: wheat, white, or sourdough.
  • Using inputMenu() for a protein type: chicken, turkey, ham, or tofu.
  • Using inputYesNo() to ask if they want cheese. If so, using inputMenu() to ask for a cheese type: cheddar, Swiss, or mozzarella.
  • Using inputYesNo() to ask if they want mayo, mustard, lettuce, or tomato.
  • Using inputInt() to ask how many sandwiches they want. Make sure this number is 1 or more.

Come up with prices for each of these options, and have your program display a total cost after the user enters their selection.

That being said, I’d like to hear what I can do better and how I can improve this code:

   import pyinputplus as pyip

# store a dictionary of ingredients and their respective prices
optionPrices = {'white' : 2.00,
                'wheat' : 2.50,
                'sour dough' : 3.00,
                'chicken' : 2.50,
                'turkey' : 2.25,
                'ham' : 1.75,
                'tofu' : 4.00,
                'cheddar' : 1.00,
                'swiss' : 1.25,
                'mozzarella' : 2.00,
                'mayo' : 0.25,
                'mustard' : 0.25,
                'lettuce' : 0.30,
                'tomato' : 0.50
                }

customerOrder = () # a list to store the current order
extras = ('mayo', 'mustard', 'lettuce', 'tomato')
sandwichTotal = 0.0

# ask the user for bread choice and append to order list
breadChoice = pyip.inputMenu(('white', 'wheat', 'sour dough'), 'Please choose your bread:n', lettered=True)
customerOrder.append(breadChoice)

# ask the user for protein choice and append to order list
proteinChoice = pyip.inputMenu(('chicken', 'turkey', 'ham', 'tofu'), 'Please choose your protein:n', lettered=True)
customerOrder.append(proteinChoice)

# ask if the user wants cheese, and if so, record cheese choice
cheeseResponse = pyip.inputYesNo('Would you like cheese?n')
if cheeseResponse == 'yes':
    cheeseChoice = pyip.inputMenu(('cheddar', 'swiss', 'mozzarella'), 'Please choose your cheese:n', lettered=True)
    customerOrder.append(cheeseChoice)
else:
    cheeseChoice = ''

# loop through 'extras' and ask if customer wants each one. If so, append it the order
choice = ''
for i in extras:
    choice = pyip.inputYesNo('Would you like ' + i +'?n')
    if choice == 'yes':
        customerOrder.append(i)
    else:
        choice = ''

# get the number of sandwiches from the customer
numSandwiches = pyip.inputInt('How many sandwiches would you like?n', min=1)

print('nYour order: ')
# check if the item exists in the options, and get the price for each sandwich
for item in customerOrder:
    if item in optionPrices.keys():
        sandwichTotal += optionPrices.get(item)
        print('t' + item + ' - $' + str(optionPrices.get(item)))

print('Total for your sandwich: $' + str('{:0.2f}'.format(sandwichTotal))) # per sandwhich total
print('Total for your order: (' + str(numSandwiches) + ' sandwiches @ $' + 
      str('{:0.2f}'.format(sandwichTotal)) + ' each): ')
print('$' + str('{:0.2f}'.format(sandwichTotal * numSandwiches))) # give the total price of sandwiches

I know that there are likely a lot of things I could do better to optimize or make the code easier to read, but there are some things I just haven’t learned yet. I realize this probably isn’t the most efficient way to solve this problem and that is why I’d like to get some feedback.

number theory – Why does the proof of Theorem 3.10 in Apostol (1976) use generalized convolutions from previous chapter when there could be a simpler proof?

The proof of Theorem 3.10 in Introduction to Analytic Number Theory by Apostol goes like this:

Theorem 3.10 If $ h = f * g $, let
$$
H(x) = sum_{n le x} h(n),
F(x) = sum_{n le x} f(n), text{ and }
G(x) = sum_{n le x} g(n). $$

Then we have
$$
H(x)
= sum_{n le x} f(n) G left( frac{x}{n} right)
= sum_{n le x} g(n) F left( frac{x}{n} right). $$

PROOF. We make use of the associative law (Theorem 2.21) which relates the operations $ circ $ and $ * $. Let
$$
U(x) = begin{cases} 0 & text{ if } 0 < x < 1, \
1 & text{ if } x ge 1. end{cases}
$$

Then $ F = f circ U $, $ G = g circ U $, and we have
$$ f circ G = f circ (g circ U) = (f * g) circ U = H, $$
$$ g circ F = g circ (f circ U) = (g * f) circ U = H. $$
This completes the proof.

I am curious to understand why use generalized convolution and Dirichlet multiplication here at all.

Since section 3.5, the book has been relying on the following reordering of summation at various places,
$$
sum_{n le x} sum_{d | n} f(d)
= sum_{substack{q, d \ qd le x}} f(d)
= sum_{d le x} sum_{q le frac{x}{d}} f(q).
$$

Can we not arrive at a simpler proof with a similar reordering of summation like this:
begin{align*}
H(x)
& = sum_{n le x} h(n)
= sum_{n le x} (f * g)(n)
= sum_{n le x} sum_{d | n} f(d) gleft(frac{n}{d}right)
= sum_{substack{q, d \ qd le x}} f(d) gleft(qright) \
& = sum_{d le x} sum_{q le frac{x}{d}} f(d) g(q)
= sum_{d le x} f(d) sum_{q le frac{x}{d}} g(q)
= sum_{n le x} f(n) sum_{q le frac{x}{n}} g(q)
= sum_{n le x} f(n) Gleft(frac{x}{n}right).
end{align*}

I am trying to understand if a simpler proof using basic arithmetic and reordering of summations is correct or if I am missing something and there is a specific reason why Apostol went for a proof using generalized convolution and Dirichlet multiplication.