|
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. |
On February 18 2017 16:40 Hanh wrote:Show nested quote +On February 18 2017 16:12 Acrofales wrote:
Re Hahn: it's not true that (1) is a weaker or stronger version of (2). They say completely different things about the set. The original statement says there is no minimum element. (1) says there is a minimum element. (2) says nothing about minima, but instead says there is no maximum element. For instance, (1) is true for the set [0, 1,2], but (2) is not (and neither is the original statement). OK, but you misquoted me. I wasn't referring to these statements. Travis: Me: Show nested quote +
Not sure what you mean by that, the 1st statement is stronger than the 2nd. (1) is false but (2) is true.
Do you disagree with me?
Still do. They just mean something completely different.
For all dragons, there exists a fairy (that rides it). This is a true statement in our world, because there are no dragons. And thus all of them are indeed ridden by fairies.
There exists a dragon for which all fairies ride it. This is a false statement in our world, because this requires the existence of a dragon.
However:
For all natural numbers x there exists a natural number y != x such that x < y is false. As above, choose x=0 and you have a counterexample.
There is a natural number x, such that for all natural numbers y != x, x < y is true. The natural number for which this holds is x=0.
It's hard to describe this formally without referring to models, but presumably you can piece the rest together yourself? If not I'll give the proof using models this evening. Now I'm going skiing 
|
Look at the variables.
there exists x, such that for all y
and
for all y, there exists x
They are flipped in the second statement.
For any predicate P(x, y) for which,
If [there is a x for which for all y, P(x, y) is true] then [for all y, there is a x for which P(x, y) is true].
In the first case x cannot depend on y. In the second case it can.
|
On February 18 2017 18:11 Hanh wrote:Look at the variables. They are flipped in the second statement. For any predicate P(x, y) for which, If [there is a x for which for all y, P(x, y) is true] then [for all y, there is a x for which P(x, y) is true]. In the first case x cannot depend on y. In the second case it can.
Just wanted to say that this is correct.
(a) exists x. forall y. P(x, y) => (b) forall y. exists x. P(x, y)
Thus, (a) is stronger than (b). It seems Acrofales didn't notice the flipped order of the variables in the quantifications.
|
|
|
On February 18 2017 14:29 dsyxelic wrote:Show nested quote +On February 18 2017 10:49 Blitzkrieg0 wrote:Which node are you actually deleting is probably where you're running into issues. When you delete the final node in the list your pointer is at position p. p.next is the final node in the list and it's p.next.next value is null. When you set the node at position p's next value to null you're removing the last node in the list as expected and not causing a problem. HEAD -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null So if I need to delete 7, I want to traverse the list until p.next == 7. p will be at 6. Then I set p.next equal to p.next.next. The resulting list: HEAD -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> null Consider the difference between delete(value) and delete(pointer). In the latter you've already done the search which is causing the discrepancy. The delete(value) function runs in O(n) time because you must traverse the list to find the node. However, the function signature looks like you're telling it to delete a pointer after you've traversed the list making it a O(1) deletion time. There is no search in the pseudo code. Same example, but with delete(pointer): function delete(6)
p=position
p.next = p.next.next p.next.next is null. Set p.next equal to null and node 7 is removed in constant time. Hi, thanks for this. So I guess my confusion comes from my 'end' function not really being the true end of the list. For example on my list x: 1 -> 2 -> 3 -> 4
I think it makes more sense to have everything based on the idea that you're returning p, but the value p.next is the actual result you're looking for. As long as all your function calls follow this pattern then the data structure makes sense. However, if you like the way you've set it up then it isn't wrong either. This is where documentation becomes important.
Does your list x look like:
A: HEAD -> [1] -> [2] -> [3] -> [4] -> null
B: [1] -> [2] -> [3] -> [4] -> null
Note in the A case that HEAD is a pointer to an empty node that does not contain any data. You'll still have an edge case at the front when you're making a new list, but you're only going to make the list once. You're always going to have these edge cases when you're implementing the data structure. It's more about implementing them in a way that causes the fewest amount of problems.
When the list is empty HEAD is null. When the list is created you create two nodes, the head node and add head.next as the first node. If you do end() on this you return HEAD and have head.next as the end of the list. If you then delete this pointer as per my previous post it will delete the correct node.
Alternately you can always have a list that is pointed to by HEAD. If HEAD.next is null then your list is empty and you need to insert as a special case.
When you're implementing data structures how the code actually works behind the scenes is irrelevant. You have certain methods exposed that are documented to do what they say they do. It is up to the user to utilize them properly.
|
On February 18 2017 14:29 dsyxelic wrote:
seems fine? though I'm curious how python's default list is so much faster in every way possible
Most python implementations store their lists in a partly full array. Removing an element from the end is as quick as decreasing the 'size' variable, except that if you remove a lot of them it'll copy the remaining list into a smaller array.
|
Anyone want to tell me what they think of this C code? I feel like it's pretty well written. To the point. Normally I end up making these small exercises way more convoluted than they need to be. (inb4 i find out it's shit)
the specifications are to take the prototype and implement the function. the function takes the source string and copies it to the results string with leading and trailing whitespace removed. it then records how many spaces were removed into number_of_spaces. You return -1 if there was nothing to copy over.
code:
+ Show Spoiler +
int remove_spaces(const char *source, char *result, int *num_spaces_removed) {
int i = 0;
int j = strlen(source) - 1;
int k = 0;
int z = 0;
if(source == NULL || j == -1) {
return -1;
}
while(source[i]) {
if(source[i] == ' ') {
i++;
continue;
}
break;
}
while(1) {
if(source[j] == ' ') {
j--;
continue;
}
break;
}
for(k=i; k < (j+1); k++) {
printf("%d %d\n", k, j);
result[z] = source[k];
z++;
}
result[z] = '\0';
*num_spaces_removed = (strlen(source) - strlen(result));
return 0;
}
|
On February 19 2017 03:50 travis wrote:Anyone want to tell me what they think of this C code? I feel like it's pretty well written. To the point. Normally I end up making these small exercises way more convoluted than they need to be. (inb4 i find out it's shit) the specifications are to take the prototype and implement the function. the function takes the source string and copies it to the results string with leading and trailing whitespace removed. it then records how many spaces were removed into number_of_spaces. You return -1 if there was nothing to copy over. code: + Show Spoiler +
int remove_spaces(const char *source, char *result, int *num_spaces_removed) {
int i = 0;
int j = strlen(source) - 1;
int k = 0;
int z = 0;
if(source == NULL || j == -1) {
return -1;
}
while(source[i] {
if(source[i] == ' ') {
i++;
continue;
}
break;
}
while(1) {
if(source[j] == ' ') {
j--;
continue;
}
break;
}
for(k=i; k < (j+1); k++) {
printf("%d %d\n", k, j);
result[z] = source[k];
z++;
}
result[z] = '\0';
*num_spaces_removed = (strlen(source) - strlen(result));
return 0;
}
Whoever gave you that prototype is a C rookie. int *num_spaces_removed Really? That screams for buggy code on all major 64 bit platforms. Why is that you may ask: int j = strlen(source) - 1;
if the source string has lenght 0 (i.e. source = ""), strlen(source) - 1 will wrap around because strlen returns a size_t. So you are basicly asigning SIZE_MAX to j. Please set your compiler warnings higher! The compiler will complain about this line because you are truncating a size_t to an int. Remember: object sizes must be of type size_t!
Other than that I have no clue to what your function is trying to achive. The first two loops are completly unecessary. Just loop once and copy every character from source to dest and skip spaces. You need just two counting variables for both strings.
|
interesting about strlen(source) - 1
As for just looping and copying all non-spaces, that doesn't work because we are not skipping spaces that are inbetween non-space characters. We are only removing trailing and leading whitespace.
|
On February 19 2017 04:22 travis wrote:
interesting about strlen(source) - 1
As for just looping and copying all non-spaces, that doesn't work because we are not skipping spaces that are inbetween non-space characters. We are only removing trailing and leading whitespace.
One loop is still enough. Skip the first spaces until you reach a non space character. Use an index (e.g. size_t end) to remember when you copied the last non space character. Once you are done copying, set source[end] to 0 to cut off the last spaces.
That is part of the reason why that prototype sucks. There is no parameter to specify how large the dest buffer is…
|
On February 18 2017 18:11 Hanh wrote:Look at the variables. They are flipped in the second statement. For any predicate P(x, y) for which, If [there is a x for which for all y, P(x, y) is true] then [for all y, there is a x for which P(x, y) is true]. In the first case x cannot depend on y. In the second case it can.
Okay, I see it now. So for starters, and this is more at travis than at you: quantified variables are quantified variables. For all I cared, you could use "cupcake" as your variable name. If the order of your variables are important, make it explicit.
But either way, the claim is still wrong. For the sake of simplicity, I have written it out here:
(1) \exists x \forall y P(x, y)
is stronger than
(2) \forall x \exists y P(y, x)
This is also not true. All we need to do is find a P and a model m such that m \models (1), but m \not\models (2). Right.
Or if you prefer it in your form of implication (2) \rightarrow (1) is false if (1) is false while (2) ist true (which boils down to essentially the same thing, but is less formal.
Here's a simple counter example:
Let X = {a, b} and Y = {a}
R = {(a, a)}
Now:
\forall x \in X \exists y \in Y such that (y, x) \in R
This is false. Counter example: x=b
However:
\exists x \in X \forall y \in Y such that (x, y) \in R
This is true, because it is true for x=a.
Therefore, unless you also make some requirements of the domains of your variables and probably some properties of P, this is definitely not true.
There is an interesting relationship between the two statements. I'm not sure whether your lemma might be true if we restrict x and y to be from the same set. I didn't immediately see a counterexample (but also haven't looked very hard, or tried to construct a proof).
But the sweeping statement you made is still false even when you clarify the switched variables.
+ Show Spoiler +Thankfully. Would be rather embarrassing for me to be wrong on something like this
|
On February 19 2017 04:30 Biolunar wrote:Show nested quote +On February 19 2017 04:22 travis wrote:
interesting about strlen(source) - 1
As for just looping and copying all non-spaces, that doesn't work because we are not skipping spaces that are inbetween non-space characters. We are only removing trailing and leading whitespace. One loop is still enough. Skip the first spaces until you reach a non space character. Use an index (e.g. size_t end) to remember when you copied the last non space character. Once you are done copying, set source[end] to 0 to cut off the last spaces. That is part of the reason why that prototype sucks. There is no parameter to specify how large the dest buffer is…
I actually thought about this way. I thought mine was better(easier, at least). Maybe it's not.
|
On February 19 2017 00:24 Blitzkrieg0 wrote:Show nested quote +On February 18 2017 14:29 dsyxelic wrote:On February 18 2017 10:49 Blitzkrieg0 wrote:Which node are you actually deleting is probably where you're running into issues. When you delete the final node in the list your pointer is at position p. p.next is the final node in the list and it's p.next.next value is null. When you set the node at position p's next value to null you're removing the last node in the list as expected and not causing a problem. HEAD -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null So if I need to delete 7, I want to traverse the list until p.next == 7. p will be at 6. Then I set p.next equal to p.next.next. The resulting list: HEAD -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> null Consider the difference between delete(value) and delete(pointer). In the latter you've already done the search which is causing the discrepancy. The delete(value) function runs in O(n) time because you must traverse the list to find the node. However, the function signature looks like you're telling it to delete a pointer after you've traversed the list making it a O(1) deletion time. There is no search in the pseudo code. Same example, but with delete(pointer): function delete(6)
p=position
p.next = p.next.next p.next.next is null. Set p.next equal to null and node 7 is removed in constant time. Hi, thanks for this. So I guess my confusion comes from my 'end' function not really being the true end of the list. For example on my list x: 1 -> 2 -> 3 -> 4 I think it makes more sense to have everything based on the idea that you're returning p, but the value p.next is the actual result you're looking for. As long as all your function calls follow this pattern then the data structure makes sense. However, if you like the way you've set it up then it isn't wrong either. This is where documentation becomes important. Does your list x look like: A: HEAD -> [1] -> [2] -> [3] -> [4] -> null B: [1] -> [2] -> [3] -> [4] -> null Note in the A case that HEAD is a pointer to an empty node that does not contain any data. You'll still have an edge case at the front when you're making a new list, but you're only going to make the list once. You're always going to have these edge cases when you're implementing the data structure. It's more about implementing them in a way that causes the fewest amount of problems.When the list is empty HEAD is null. When the list is created you create two nodes, the head node and add head.next as the first node. If you do end() on this you return HEAD and have head.next as the end of the list. If you then delete this pointer as per my previous post it will delete the correct node. Alternately you can always have a list that is pointed to by HEAD. If HEAD.next is null then your list is empty and you need to insert as a special case. When you're implementing data structures how the code actually works behind the scenes is irrelevant. You have certain methods exposed that are documented to do what they say they do. It is up to the user to utilize them properly.
Mine looks like B.
I did not know that (bolded part), that's definitely good to know. I implemented in a way that p gives the actual result besides end(). I guess ideally I would have everything consistent but again, the book we're using did it with p giving the actual result and apparently didn't account for deletion from the back.
Thanks though you were a lot of help.
|
sometimes I read stuff in this thread and I am amazed at just how smart you guys are. how much varied stuff you guys know and how precise you are at it. and I wonder to myself "how are these guys not able to work anywhere they want on the cutting edge with this much ability". but then again, maybe you are?
But anyways I read it and am just constantly reminded of how much effort I will have to put in to actually be exceptional in this field, when this is how high the bar is set.
|
On February 19 2017 05:11 travis wrote:
sometimes I read stuff in this thread and I am amazed at just how smart you guys are. how much varied stuff you guys know and how precise you are at it. and I wonder to myself "how are these guys not able to work anywhere they want on the cutting edge with this much ability". but then again, maybe you are?
But anyways I read it and am just constantly reminded of how much effort I will have to put in to actually be exceptional in this field, when this is how high the bar is set.
You see a dozen or more people showing off their knowledge in their respective fields of expertise. You especially don't see people answering with an unhelpful and slightly embarassing "I don't know". You don't need to be exceptionally smart to be good at a couple of things. With actual job experience you also learn a couple of things in detail, often the hard way. That kind of stuff tends to burn itself into your mind.
But yes, this software as a job is not something where you learn stuff once and then stop putting in effort.
|
Gee why do I keep using quote instead of edit...
|
On February 19 2017 04:57 travis wrote:Show nested quote +On February 19 2017 04:30 Biolunar wrote:On February 19 2017 04:22 travis wrote:
interesting about strlen(source) - 1
As for just looping and copying all non-spaces, that doesn't work because we are not skipping spaces that are inbetween non-space characters. We are only removing trailing and leading whitespace. One loop is still enough. Skip the first spaces until you reach a non space character. Use an index (e.g. size_t end) to remember when you copied the last non space character. Once you are done copying, set source[end] to 0 to cut off the last spaces. That is part of the reason why that prototype sucks. There is no parameter to specify how large the dest buffer is… I actually thought about this way. I thought mine was better(easier, at least). Maybe it's not.
I think with C you need to put a lot of effort into making your code as simple as possible, since the language offers very little help. Fewer moving parts should make the code a lot easier to read. Try to cut as many extra lines of code as long as it also makes the code somewhat more readable. A common pattern in string handling is to simply loop until str[i]==0, instead of using strlen to avoid extra passes. Another common trick is to use a[i++] = b[j++] for copying a string.
With a single pass the code becomes quite a bit shorter:
int i = 0, j = 0, end_pos = 0;
for(i=0;source[i]!=0;i++) {
bool space = source[i]==' ';
if(j || !space ) {
if(!space) end_pos = j+1;
result[j++] = source[i];
}
}
result[end_pos] = 0;
*num_spaces_removed = i-end_pos;
return (i-end_pos) == 0 ? -1 : 0;
You can do two passes in a similar manner:
int j = 0, last_char = -1, len = 0;
for(len=0;source[len]!=0;len++) if(source[len]!=' ') last_char = len;
for(int i=0;i<=last_char;i++) {
if(j || source[i] != ' ') {
result[j++] = source[i];
}
}
result[j] = 0;
*num_spaces_removed = len-j;
return (len-j) == 0 ? -1 : 0;
A lot of this is of course subjective, verbose code might be easier to read for some people. At least after doing a lot of string processing in pure C this style should become easier to read.
|
slmw could you explain
bool space = source[i]==' ';
is "bool" in a certain library in C? I was under the impression C doesn't have a boolean type.
What is the syntax here?
bool name = [ statement ] ?
it's syntax is weird to me
|
C99 has bools.
as for the use, it's
bool name = <something boolean>
could be
bool stopyet = false;
<do stuff>
stopyet = true;
if (stopyet) {
exit(0);
}
or as slmw wrote, some statement that evaluates to true/false. I would put it between brackets,though. I hate depending on non-obvious precedence between operators for my code to work. Does C parser parse that as:
(bool space = source[i]) == ' '; //gibberish
or
bool space = (source[i] == ' '); //what you want: assigns the outcome of the comparison to your newly declared bool.
If assignment were to have a higher precedence than comparison, C parser would give you the former, which at best wouldn't compile (haven't tested). But that's just personal preference for the style, perhaps if I was more familiar with C, I wouldn't be bothered by it.
|
Hyrule19087 Posts
On February 19 2017 05:30 spinesheath wrote:
Gee why do I keep using quote instead of edit...
It gets even more annoying when you can edit any post...
|
|
|
|
|
|
EPT
