EPTThe Big Programming Thread - Page 860
| Forum Index > General Forum |
Thread Rules 1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution. 2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20) 3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible. 4. Use [code] tags to format code blocks. | ||
|
Nesserev
Belgium2760 Posts
| ||
|
Blisse
Canada3710 Posts
In hindsight I think it's a good question: it has a lot of pretty straightforward coding sections like palindrome, lends itself well to breaking down into parts, has lots of areas for optimizations, and then the short time limit adds a nice intensity given I think most people could find an okay solution in 30 minutes. This takes me 4 minutes to code, but I have the advantage of knowing the question and my previous attempt :p mfw trying to read slmw's O(n) solution... lol + Show Spoiler +
| ||
|
Fwmeh
1286 Posts
Best I could do, certainly more than 5 minutes. https://ideone.com/M4tVmS. O(n^2), but reasonably good constants. | ||
|
meatpudding
Australia520 Posts
| ||
|
slmw
Finland233 Posts
If you try every substring (N^2) in a string and check if it is a palindrome you get an O(N^3) algorithm. That is what Fwmeh's and many others' solution is doing. If you try every midpoint and expand until it is no longer a palindrome, you get an O(N^2) algorithm. This is what travis's solution was doing for odd palindromes. | ||
|
Manit0u
Poland17187 Posts
I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:
After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help... + Show Spoiler [sample] +
One of my favorites:
| ||
|
BluzMan
Russian Federation4235 Posts
On March 13 2017 23:08 Manit0u wrote: Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses? I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:
After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help... + Show Spoiler [sample] +
One of my favorites:
Looks like regular production code to me, also pretty well-formed. At least this doesn't have 20 global declarations at the start of each function like our code did. Based on the sample you provided I would definitely try to reuse it, deep control structure nesting does not necessarily imply redundancy, it might just be that the field is actually that difficult. In that was the case, rewriting it from scratch would be a pretty stupid thing to do. Maybe start with writing tests for the parts you understand and slowly increase the coverage as your understanding grows? Could also refactor obvious subroutines into functions, etc. Throwing working code away and rewriting from scratch is almost never a good idea. One of my favorites:
That is a pretty creative way to do a swap one-liner  Can you implement cpp-style swap with references in php? Don't remember the exact way they work. | ||
|
Deleted User 3420
24492 Posts
Prove: If a, b, c and d are consecutive integers, 4 | abcd. *please note that this is under the heading "formal proofs" So my answer is: + Show Spoiler + Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd. Here is what the answer key says: + Show Spoiler + Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd. So I guess my question is, does my answer suffice for a "formal" proof? Also this question is dumb. | ||
|
Acrofales
Spain17842 Posts
| ||
tofucake
Hyrule18969 Posts
| ||
|
Deleted User 3420
24492 Posts
| ||
|
Biolunar
Germany224 Posts
Same goes of following example: ℕ = { n ∈ ℤ | n ≥ 0 } is not more “mathematically” than ℕ = { n ∈ ℤ | n is greater or equal to zero }, although the former is more formal. | ||
|
Manit0u
Poland17187 Posts
On March 14 2017 00:54 BluzMan wrote: Looks like regular production code to me, also pretty well-formed. At least this doesn't have 20 global declarations at the start of each function like our code did. Based on the sample you provided I would definitely try to reuse it, deep control structure nesting does not necessarily imply redundancy, it might just be that the field is actually that difficult. In that was the case, rewriting it from scratch would be a pretty stupid thing to do. Maybe start with writing tests for the parts you understand and slowly increase the coverage as your understanding grows? Could also refactor obvious subroutines into functions, etc. Throwing working code away and rewriting from scratch is almost never a good idea. That is a pretty creative way to do a swap one-liner Can you implement cpp-style swap with references in php? Don't remember the exact way they work.It doesn't have 20 global declarations at each function. It has 60 at the top of the file though. Swap one-liner is clever, but it comes out of the blue and is buried deep in other logic (also with functions that span several hundred lines it's easy to miss). I have to pretty much rewrite it anyway since I have to do it in another language. I've started with various utility functions around the code, but it's hard to implement some of the larger methods since no documentation or anything and magic numbers are bad (also, pi with 5 digit precision jumped at me out of nowhere, no explanation why 5 digits or how important it is...). I've been reading some books from 1895 on imposition, also some Rockwell patents I found on Google. It's damn complicated stuff  | ||
|
Liebig
France738 Posts
On March 14 2017 02:26 travis wrote: I am studying for my discrete math midterm. Here is a question that an old exam asks: Prove: If a, b, c and d are consecutive integers, 4 | abcd. *please note that this is under the heading "formal proofs" So my answer is: + Show Spoiler + Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd. Here is what the answer key says: + Show Spoiler + Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd. So I guess my question is, does my answer suffice for a "formal" proof? Also this question is dumb. I think it's fine, but I would play it safe if it was in the first few questions of the exam and just answer like that We can assume without loss of generality that b=a+1, c=a+2, d=a+3. If a=0[4] then a*b*c*d is clearly a multiple of 4 If a=1[4] then d=0[4] and etc | ||
|
Atreides
United States2393 Posts
On March 14 2017 02:26 travis wrote: I am studying for my discrete math midterm. Here is a question that an old exam asks: Prove: If a, b, c and d are consecutive integers, 4 | abcd. *please note that this is under the heading "formal proofs" So my answer is: + Show Spoiler + Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd. Here is what the answer key says: + Show Spoiler + Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd. So I guess my question is, does my answer suffice for a "formal" proof? Also this question is dumb. Every math professor in the world here is just looking for you to say there is two even numbers bla bla bla. It's ez to formalize. Jumping straight to divisible by four is obviously doable but slightly harder to formalize. For a question like that the entire thing is formalizing something intuitively obvious so I can't imagine any prof giving full credit for your answer. | ||
|
Hanh
146 Posts
On March 14 2017 03:05 travis wrote: So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with? You can only use theorems and axioms that were given to you during your class, so I wouldn't call your answer a formal proof. Edit: 1. Use the canonical injection to go from N to Z/4Z. 2. By definition, you get 4 different equivalent classes of Z/4Z. 3. Z/4Z has cardinality 4. Therefore one of the classes must be 0. 4. the product is 0 5. Therefore the product is a multiple of 4. | ||
|
Prillan
Sweden350 Posts
On March 14 2017 03:05 travis wrote: So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with? You need to state why the things you do are true. Ask "why?" until you reach an already proved result. To get you started: Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Why? | ||
|
Blisse
Canada3710 Posts
Now to go over your answer. Correct me if I am wrong, but "multiple" and "factor" are not words in the theorems you've been taught. They are obvious mathematical definitions and results of the theorems, and maybe part of some related, unpresented corollary due to those definitions, but they essentially aren't part of your set of premises. The goal of these exercises is to have you conceptualize how to infer the result, given the premises. Using these "unrelated" concepts and jumping from result to result is what is I meant by not being rigorous. > Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. (1) Is this true? It looks like it's true, but how do I prove that? Is it so trivially true that it's unnecessary to show (1*n = n)? Is this the result of some theorem that I know (n|a-b => a === b mod n)? This result is intuitive, in that it's easy enough to convince yourself that this must be true, but how do you show that in writing? > Therefore 4 can be factored from a*b*c*d. (2) What did factored come from and what factored mean? Are you saying that "multiple of n" implies "factor out by n"? > Therefore 4|abcd. (3) Are you saying that "factor n from x" implies "n | x"? I think you'd have to enumerate all the cases in (1) to show a proof of it. Suppose a,b,c,d are consecutive numbers. Any 4 consecutive numbers (a,b,c,d) must contain 1 number which is a multiple of 4. <show that this is true> Without loss of generality, suppose a is divisible by 4. Therefore there exists n such that a = 4n. (2) Therefore there exists n such that abcd = 4nbcd. If x == nbcd, then abcd = 4x. From definitions, a | b iff a*n = b. Therefore 4 | abcd. (3) | ||
|
netherh
United Kingdom333 Posts
On March 15 2017 07:49 Blisse wrote: Suppose a,b,c,d are consecutive numbers. Any 4 consecutive numbers (a,b,c,d) must contain 1 number which is a multiple of 4. <show that this is true> Without loss of generality, suppose a is divisible by 4. Therefore there exists n such that a = 4n. (2) Therefore there exists n such that abcd = 4nbcd. If x == nbcd, then abcd = 4x. From definitions, a | b iff a*n = b. Therefore 4 | abcd. (3) Probably dumb questions: What does the line in 4 | abcd mean? What does "without loss of generality" mean, and why do you use it there? | ||
|
tofucake
Hyrule18969 Posts
| ||
| ||
;
