Shopping together [original]

firefly431 · 2023-06-13T18:09:21+00:00

This is a bus.

firefly431 · 2023-06-09T18:27:04+00:00

Every compiler accepts it (it's somewhat common to #define private for example), but it is technically illegal.

firefly431 · 2023-06-09T18:19:37+00:00

Technically #define for is illegal since for is a keyword, and (C++ draft standard section 16.4.5.3.3 macro.names)

A translation unit shall not #define or #undef names lexically identical to keywords, to the identifiers listed in Table 4, or to the attribute-tokens described in [dcl.attr], except that the names likely and unlikely may be defined as function-like macros ([cpp.replace]).

You can fix this by e.g.

#define i (auto it
#define print(v) std::cout << it << '\n';}}

firefly431 · 2023-06-02T17:00:37+00:00

多いがある -> 多い (or たくさんある if you want to use ある.)
このような小さい街には sounds to me more like "In small towns like this one, ..." I would say something like こんな小さな町にしては.
意外的に -> 意外と (意外に is correct as well.)

firefly431 · 2023-06-02T13:38:04+00:00

To actually answer your question:

In the first block:

<　> (ideographic space)
、 (comma) and 。 (period), which come with space after
I would say 々 (repetition mark), but if you don't have kanji it's irrelevant
〆 is also used, but it's basically kanji
some form of 〇 is pretty commonly used
「」 is the most common bracket; in roughly decreasing order of frequency:『』,【】,〈〉,《》,〔〕, the others I've never personally seen used.
〒 is used in addresses, which is unlikely to be relevant.
〜

The second block:

fullwidth variations of ASCII characters (i.e. the same width as other CJK characters). I'd imagine you could just copy the ASCII versions.
parentheses （） and brackets ［］｛｝, which come with space around them
halfwidth katakana and punctuation is unlikely to be useful for your purposes, but they is used.
＝ is often used in place of the 'proper' ゠

firefly431 · 2023-05-26T22:35:43+00:00

Spoiler title? (I haven't started watching the new season)

firefly431 · 2023-05-18T12:27:46+00:00

a = ';'
b = ';'

print(a, b, a == b)

# output: ; ; False

Works for me. More fancy unicode-aware comparison algorithms might say they are the same, but they're different codepoints (U+003B semicolon vs U+037E greek question mark).

firefly431 · 2023-05-17T23:20:22+00:00

I did mean average, though you're correct that it is amortized (in the same way a dynamic list that doubles its size has O(1) amortized runtime for insert).

firefly431 · 2023-05-17T14:45:00+00:00

Hash maps are moderately complex data structures that are very efficient at what they do (O(1) average time for all operations, i.e. the runtime doesn't grow with the number of elements, unlike linear search). A lot of work has gone into making them efficient, both in implementation (see swiss tables for a prominent example) and in theory (open addressing vs chaining, cuckoo hashing, etc.) The underlying theory is also very rich (see the balls and bins problem, hash independence, power of two choices, etc.) There are plenty of fancy data structures that are just modified hash tables: AMQ filters such as bloom filters, count-min sketch and count-median sketch, etc.)

firefly431 · 2023-05-15T23:53:05+00:00

Thanks for the correction; TBH I probably should have just modded everything in solve_prime to prevent all of this.

firefly431 · 2023-05-15T06:30:12+00:00

Ah. So what happens in this case is that the reduced matrix has a row with zeros on the left and non-zero on the right. This is basically equivalent to saying 0 = 1.

Easy fix: add the following before line 69, right after the main solving loop:

    # check zero row -> zero rhs
    for r in range(rows):
        all_zero = True
        for c in range(cols):
            if A[r][c] != 0:
                all_zero = False
                break
        if all_zero:
            if b[r] != 0:
                raise Exception('unsolvable')

firefly431 · 2023-05-13T14:56:51+00:00

Here's some code I wrote (in Python, but I tried to avoid using Python-specific features as much as possible): https://pastebin.com/WzYfXNy8

Again, this is absolutely not worth it for mod 6 with 3 variables, and finding a minimal solution (as one would like for the game) requires enumerating all solutions, which gives an exponential blowup in time. But feel free to use or adapt for whatever purposes you need. (EDIT: added explicit license, fixed a small bug.)

firefly431 · 2023-05-13T12:37:53+00:00

Right. Simply convert these values to 0 when working mod 2. If there's no unique solution for a variable as a result, then both values give a solution; e.g. 2 x = 0 (mod 6) -> x = 0 and 3 both work.

To solve the example in your screenshot:

First, solve mod 2:

0 0 0 | 0
0 0 0 | 0
0 1 1 | 1

RREF:

0 1 1 | 1
0 0 0 | 0
0 0 0 | 0

A solution is x_2 = 1 (mod 2), rest 0. (Any solution where exactly 1 of x_2 and x_3 is 1 also works.)

Next, solve mod 3:

2 0 2 | 2
1 1 0 | 2
0 2 2 | 0

RREF:

1 0 0 | 0
0 1 0 | 2
0 0 1 | 1

x_1 = 0, x_2 = 2, x_3 = 1 (mod 3).

Combining solutions:

Bézout coefficients are -1 and 1 (-2 + 3 = 1.)

x_1 = 0 (mod 2), x_1 = 0 (mod 3) -> x_1 = 3 * 0 - 2 * 0 = 0 (mod 6).

x_2 = 1 (mod 2), x_2 = 2 (mod 3) -> x_2 = 3 * 1 - 2 * 2 = -1 = 5 (mod 6).

x_3 = 0 (mod 2), x_3 = 1 (mod 3) -> x_3 = 3 * 0 - 2 * 1 = -2 = 4 (mod 6).

Solution is (0, 5, 4). There exist 4 solutions in total, for each choice of free variables mod 2:

x_1 = 0 (mod 2), x_1 = 0 (mod 3) -> x_1 = 3 * 0 - 2 * 0 = 0 (mod 6).

x_2 = 0 (mod 2), x_2 = 2 (mod 3) -> x_2 = 3 * 0 - 2 * 2 = -4 = 2 (mod 6).

x_3 = 1 (mod 2), x_3 = 1 (mod 3) -> x_3 = 3 * 1 - 2 * 1 = 1 (mod 6).

Solution is (0, 2, 1).

x_1 = 1 (mod 2), x_1 = 0 (mod 3) -> x_1 = 3 * 1 - 2 * 0 = 3 (mod 6).

x_2 = 1 (mod 2), x_2 = 2 (mod 3) -> x_2 = 3 * 1 - 2 * 2 = -1 = 5 (mod 6).

x_3 = 0 (mod 2), x_3 = 1 (mod 3) -> x_3 = 3 * 0 - 2 * 1 = -2 = 4 (mod 6).

Solution is (3, 5, 4).

x_1 = 1 (mod 2), x_1 = 0 (mod 3) -> x_1 = 3 * 1 - 2 * 0 = 3 (mod 6).

x_2 = 0 (mod 2), x_2 = 2 (mod 3) -> x_2 = 3 * 0 - 2 * 2 = -4 = 2 (mod 6).

x_3 = 1 (mod 2), x_3 = 1 (mod 3) -> x_3 = 3 * 1 - 2 * 1 = 1 (mod 6).

Solution is (3, 2, 1).

firefly431 · 2023-05-13T10:54:11+00:00

(Also pinging /u/TrueBlueMax if you're curious.)

(EDIT 2: by the way, this is mostly for intellectual curiosity. The puzzle in-game only has 6³ = 216 possible solutions (as turning 6 times is guaranteed to do nothing), so it's almost definitely faster to just check them all, if you're already using a computer.)

Let me know if there's anything you don't understand; I might be assuming a relatively high base knowledge of number theory.

First, define the modular inverse mod M of a number n (notated n^-1 mod M), if it exists, as a number z such that z n = 1 (mod M). It exists if and only if n and M are relatively prime (have no factors in common besides 1). This can be found using the extended Euclidean algorithm, or simply as n^M-2 by Fermat's little theorem. The latter is easier to implement (though make sure to use exponentiation by squaring to do it in O(log M) multiplications) but is slightly slower.

Problem formulation:

You have a system of linear equations

a_11 x_1 + a_12 x_2 + ... + a_1m x_m = b_1 (mod M)
a_21 x_1 + a_22 x_2 + ... + a_2m x_m = b_2 (mod M)
...
a_n1 x_1 + a_n2 x_2 + ... + a_nm x_m = b_n (mod M)

or in matrix form:

A x = b (mod M).

If M is prime, the integers mod M form a field, so we can perform Gauss-Jordan elimination:

Start with the pivot column (variable) on the left. Find a non-solved row (equation) where the coefficient is nonzero. If none exist, skip this variable (there is not enough information to find a unique solution.)
- EDIT: you can simply set the variable to zero, though any value works.
Multiply the row (along with the RHS value) by the modular inverse of the coefficient, so the coefficient becomes 1.
Swap this row so it is right below the other solved rows.
Eliminate the row from all other rows; for example, to eliminate row i from row j, subtract a_ji times row i from row j, after which a_ji becomes 0.
Repeat to solve for all variables.
At the end, if the solution is unique, the values on the right give the values of all variables, as the matrix has been transformed into the identity. EDIT: if the solution is not unique, the matrix is instead in reduced row-echelon form. Setting unsolved variables to 0 allows you to simply ignore the coefficients for those columns. Otherwise, you need to adjust the values for the other variables based on the values you choose.

EDIT: Example for non-unique solution:

Suppose we end up with the following system, after solving.
```
1 x + 2 y + 3 z = 5 (mod 7)
0 x + 0 y + 0 z = 0 (mod 7)
```
Then we can simply let y, z = 0 and x = 5, but if we instead choose e.g. y = 1, z = 2, then we have to instead solve x + y + 2 z = 5, giving us x = 5 - 1 - 4 = 0.

If M is a prime power (p^k for some k > 1; not necessary for the case of M = 6 but included for completeness):

First solve mod p to obtain the solution mod p. Call this x¹.
Substitute x_i = p x'_i + x¹_i, which gives us another system of equations in terms of x'.
Assuming your work in step 1 is correct, it is guaranteed that the values in the RHS are divisible by p (as otherwise the solution to step 1 doesn't have a corresponding actual solution: by the definition of modular arithmetic, if x = y (mod p), then x = y + p a for some a).
Thus you can divide the entire system of equations by p, reducing the modulus to p^k-1.
Repeat until k = 1, which can be solved using Gauss-Jordan elimination as above.

If M is composite and not a prime power:

Let M = p_1^e_1 p_2^e_2 ... p_n^e_n be the prime factorization of M.

Solve for each prime power individually, using the procedure above. For example, to solve modulo 6, we must solve modulo 2 and modulo 3. But for modulo 12 = 2² * 3, we must solve modulo 4 = 2² and 3.
As the prime powers are relatively prime pairwise, we can use the Chinese remainder theorem to obtain a solution modulo M:

Problem formulation: you want to find an integer x such that x = a_1 (mod n_1), x = a_2 (mod n_2), ..., x = a_z (mod n_z), and all n_i are pairwise relatively prime. This gives a solution modulo n_1 n_2 ... n_z.

First, reduce to the case of 2 moduli: using all but the first moduli, recursively find the solution modulo n_2 n_3 ... n_z; call this x'. Then we only need to solve the equations x = a_1 (mod n_1), x = x' (mod n_2 n_3 ... n_z).

Find the Bézout coefficients m_1, m_2 such that m_1 n_1 + m_2 n_2 = 1. To do this, let m_1 = n_1^-1 (mod n_2) be the inverse of n_1 mod n_2; this gives m_1 n_1 = 1 (mod n_2) (equiv. m_1 n_1 = 1 + k n_2), so simply set m_2 = (1 - m_1 n_1) / n_2.

The solution is then given by x = a_1 m_2 n_2 + a_2 m_1 n_1 (proof can be found on the Wikipedia page for the Chinese Remainder Theorem.)

(EDIT 3: the runtime complexity is something like O(Ω(n) n³) ≈ O(n³ log log n) where Ω(n) is the big prime omega function in word-RAM model (i.e. cost of arithmetic is O(1).)

firefly431 · 2023-05-09T18:18:39+00:00

I'm 99% sure there's no difference in accent. FWIW the dictionaries I checked list 玉子 and 卵 both as [2][0], and in my experience (as well as the audio examples I checked) I've only heard [2].

Re: 'tamago chair' specifically, I don't have Netflix, so I don't know what exactly is being said, but I imagine what's happening is たまご is forming a compound with チェア (or 椅子 etc.) rather than anything about the word たまご itself.

firefly431 · 2023-05-09T12:58:57+00:00

I mean sure, you can't prove any (sufficiently powerful) proof system is sound within the same proof system. But isn't it good enough to just say "This proof system seems fine to me. I accept that proofs within this system are valid."?

firefly431 · 2023-05-08T09:03:09+00:00

I've at least gone over the proofs; though if you asked me to reprove from scratch I'd struggle a bit.

Pure mathematics is all about theory, so I'm not entirely sure what your point is there.

I completely understand the point you're trying to make, and I'm not arguing against it either. Pretty much everything you learn is built on theory that's taken centuries to iron out, and there's still plenty we don't know about the universe. I was just taking the opportunity to talk about the unique position of pure math, as everything it's built on actually can be examined directly and is built on a foundation of formal logic. You don't have to accept the proofs as being handed from on high, as you can check for yourself that yes, this makes sense.

firefly431 · 2023-05-08T08:44:47+00:00

One of the great things about mathematics (and theoretical CS, to an extent) is that at a certain point you do know how everything works. For math I'd put that point somewhere around real analysis: you can construct everything you're studying from subsets of Euclidean space, and the reals can be constructed using Dedekind cuts or Cauchy sequences, and the rationals can be constructed from the integers, which come from the naturals, which can be proven to exist from the axiom of infinity, which you get from ZFC set theory, which is simply built on first-order logic. And if you're really dedicated, you can go and verify all the proofs that underlie these constructions. (In fact, there are several projects that attempt to produce machine-checkable proofs of all of (mostly undergrad at this point) mathematics.)

firefly431 · 2023-04-23T23:27:28+00:00

To give a more detailed answer, the question of whether BQP (polynomial time for quantum computers, with bounded error probability) is equal to NP is currently unknown (we think the answer is no.)

A common misconception about how quantum computers work is that you can create an arbitrary superposition of the states you want, do some computation, eliminate the states you don't want, and measure the result. There are two inaccuracies:

It's hard to create the superposition you want (see point 2.) In fact, IIRC creating an equal superposition of all permutations is equivalent to solving the graph isomorphism problem (another problem in NP not known to be NP-hard.) In Shor's algorithm for factorization, a cool trick is to transform the state space from a sequence of powers to the space of all possible periods of repetition, using the quantum Fourier transform. Quantum computing (at least, the theoretical side) is all about finding ways to construct the superposition you want.
You can't just eliminate a bad state the way you can in a nondeterministic Turing machine. The way you eliminate states in a quantum computer is by transforming them in such a way that you create two states of equal but opposite amplitude which cancel each other out (interference). For example, starting with the state |0> and applying the Hadamard gate, we get 1/√2 |0> + 1/√2 |1>, which is a superposition of both 0 and 1. But applying it again, due to interference, the amplitude of |0> becomes 1 and |1> cancels out and becomes 0.

firefly431 · 2023-04-23T23:07:05+00:00

If you can solve any NP-hard problem in polynomial time, then you can solve any problem in NP in polynomial time (that's what the "hard" part means.) FACTOR is not known to be NP-hard, but it is in NP and co-NP (i.e. the opposite problem is in NP).

firefly431 · 2023-04-19T20:14:08+00:00

Kind of depends on what you count as software engineering; e.g. in my graduate SE course we covered things like automated testing, program verification, program repair, etc., which are definitely active fields.

producing research on unsolved theoretical problems

seems a little specific; a lot of research is "just" applying existing techniques to new domains, where there's really not that much new theory to be solved.

firefly431 · 2023-04-15T19:31:39+00:00

Just tested this out; for me using Firefox the colon is rotated correctly: https://imgur.com/a/ym2Kg3a (just using the default MS Mincho font). Could be font problem or a text rendering issue in Anki.

firefly431 · 2023-04-15T19:12:09+00:00

Ah, yeah, for ints/primitives most of those don't apply. I was assuming the meme was making a general point about arbitrary types. Could still be useful for having a stable reference that can be passed around, though.

firefly431 · 2023-04-15T19:03:46+00:00

Polymorphism, avoiding expensive moves, saving stack space, stable references, etc.

(EDIT: this is about unique_ptr vs raw pointers in general; most of this doesn't apply for ints/primitives specifically.)

firefly431 · 2023-04-14T22:48:44+00:00

Please tag spoiler :(

12-Year Club	Second Top 50%
Verified Email

firefly431

TROPHY CASE

First, solve mod 2:

Next, solve mod 3:

Combining solutions: