Support NeoGAF

[Koren]

I don't think you should be scared of js, more than any other thing you run on your computer

Well, you see, most of the things I run on my computer are coming from trusted sources and signed, or recompiled...

Even on website I trust, there's plently of unresponsive scripts that bothers me. And I don't speak about redirections on my phone, where I'm not able to limit JS...

Because of that, I try to avoid JS on my own websites, while keeping as many features as I can...

I'm probably overly cautious, but I've never had a virus on a computer, and I don't run an antivirus... I want to go on this way

 

[Kieli]

I'm having a little bit of trouble with C code. Given the following:

          int a[10] = {0,1,2,3,4,5,6,7,8,9};
          int i = *( &a[3] + 2 + *(a+1) );

What exactly does &a[3] mean? Does it mean *(a+3)? I thought & was the address of a[3].

Also, &a[5] - &a[3] = 2 apparently. I don't get why (I mean, I understand 2 represents how many indices the two are apart). But again, & tells us the address. So &a[5] - &a[3] would be:
(base + 5 * word size) - (base + 3 * word size) = 2 * word size.

So it's not 2, but rather twice the word size, by my logic.

Finally, if someone is familiar with Huffman encoding, then can you shed some light on this question?

We want some input to Huffman algorithm such that the prefix tree generated will have all leafs at the same level or one level higher.

The solution states to have an alphabet where every element has the same frequency. Then it uses proof by contradiction to tell us it's impossible to have a prefix tree for such an input NOT satisfy the property requested. We assume, to the contrary, that there is some element that is 2 or more levels higher than the greatest depth of the tree. Swapping the locations of this item with 2 siblings at the lowest level will produce a tree with shorter average bits/length encoding, which contradicts the fact that we shouldn't be able to optimize our tree further.

???

 

[Somnid]

I'm having a little bit of trouble with C code. Given the following:

          int a[10] = {0,1,2,3,4,5,6,7,8,9};
          int i = *( &a[3] + 2 + *(a+1) );

What exactly does &a[3] mean? Does it mean *(a+3)? I thought & was the address of a[3].

Also, &a[5] - &a[3] = 2 apparently. I don't get why (I mean, I understand 2 represents how many indices the two are apart). But again, & tells us the address. So &a[5] - &a[3] would be:
(base + 5 * word size) - (base + 3 * word size) = 2 * word size.

So it's not 2, but rather twice the word size, by my logic.

Finally, if someone is familiar with Huffman encoding, then can you shed some light on this question?

We want some input to Huffman algorithm such that the prefix tree generated will have all leafs at the same level or one level higher.

The solution states to have an alphabet where every element has the same frequency. Then it uses proof by contradiction to tell us it's impossible to have a prefix tree for such an input NOT satisfy the property requested. We assume, to the contrary, that there is some element that is 2 or more levels higher than the greatest depth of the tree. Swapping the locations of this item with 2 siblings at the lowest level will produce a tree with shorter average bits/length encoding, which contradicts the fact that we shouldn't be able to optimize our tree further.

???

I'd have to think a bit more about the huffman encoding but a[3] is the value of the third element in a, so &a[3] should be the address of the 3rd element in a. So if a[3] = *(a+3) then &a[3] would be (a+3). &a[5] - &a[3] = 2 because (a+5) - (a+3) would be 2.

 

[Kieli]

I'd have to think a bit more about the huffman encoding but a[3] is the value of the third element in a, so &a[3] should be the address of the 3rd element in a. So if a[3] = *(a+3) then &a[3] would be (a+3). &a[5] - &a[3] = 2 because (a+5) - (a+3) would be 2.

The solution key agrees with you, but I'm not sure what it means to be (a + 3). Is that an address? Like maybe 0x2004 somewhere in the heap?

 

[Somnid]

The solution key agrees with you, but I'm not sure what it means to be (a + 3). Is that an address? Like maybe 0x2004 somewhere in the heap?

Yeah, so "a" with nothing else is really an address of the 0th element in memory. Maybe it's 0x2000, a+3 is 0x200B because an int32 is 4 bytes so it's 3*4 bytes offset from a.

 

[Ahnez]

Finally, if someone is familiar with Huffman encoding, then can you shed some light on this question?

We want some input to Huffman algorithm such that the prefix tree generated will have all leafs at the same level or one level higher.

The solution states to have an alphabet where every element has the same frequency. Then it uses proof by contradiction to tell us it's impossible to have a prefix tree for such an input NOT satisfy the property requested. We assume, to the contrary, that there is some element that is 2 or more levels higher than the greatest depth of the tree. Swapping the locations of this item with 2 siblings at the lowest level will produce a tree with shorter average bits/length encoding, which contradicts the fact that we shouldn't be able to optimize our tree further.

???

I think I got it

First, all elements of the alphabet have the same frequency.

Due to how the algorithm builds the tree, every non-leaf node always have exactly two children. This means there are at least two characters stored on the highest height of the tree (lets say the height is K).

Assume there is a character stored in a leaf in the K-2 level

Switch the places of the subtree that holds the two characters at the highest height (The node that connects them, and the two leafs) with the one stored in the (K-2) height.

Before the switch:

Two characters had a code of length K
One characters had a code of length K-2

After the switch:

The two characters now have a code of length K-1 (Because the sum node takes the K-2 place)
And the one character also have a code of length K-1 (Because its a single node, and its replacing a subtree with three nodes)

And every character have the same frequency, lets say, N.

So, before, we had
2*K*N + (K-2)*N =
= 2KN + KN - 2N =
= 3KN - 2N

And after:
3*(K-1)*N =
3KN - 3N

As you can see, the number of acesses decreased, because 3N is bigger than 2N.
And since this change don't do anything to the other nodes of the tree, the average code length decreased.

But thats a contradiction, because the algorithm creates the optimal tree, and we found a way to optimize it further

 

[Koren]

nm

 

[Koren]

I have read comprehension this morning... :/

 

[Ambitious]

Just received the response from the company. While I'm personally rather disappointed and actually somewhat embarrassed about my results, they seem to be satisfied. They invited me to an interview with one of their team leaders tomorrow. That's great news. (Well, maybe they invite everyone independent of their test results..)

Koren, JeTmAn81 and CornBurrito: I'm really busy right now, but I'm gonna reply with some details later. I've already started writing the post.

 

[Koren]

Koren, JeTmAn81 and CornBurrito: I'm really busy right now, but I'm gonna reply with some details later. I've already started writing the post.

Take all the time you need, you've more important matters at hand. I wish you the best for your interview.

(and I'm pretty sure you shouldn't worry too much about your results, I'd say. Most probably, most candidates have done far worse. Think about what you would have done differently, given more time and a less stressful environment, should they discuss the matter with you)

 

[cpp_is_king]

Holy eff...

looking at solutions to nonograms. Idk if my school has really prepared me to tackle these sorts of problems.

Is that those picture puzzles? If you know how to solve them by hand, seems like a straightforward matter to extend that to an algorithm

 

[Ahnez]

Holy eff...

looking at solutions to nonograms. Idk if my school has really prepared me to tackle these sorts of problems.

Nonogram solving is a NP-Complete problem

There's not much to do outside of brute-forcing it

 

[Koren]

Is that those picture puzzles? If you know how to solve them by hand, seems like a straightforward matter to extend that to an algorithm

The trick is that it's not obvious by hand... By scanning each line/columns, you can find black and white cells, and found cells gives helps you for other columns/rows.

But for some puzzles, you won't solve them that way. You'll have to make guesses, build on those guesses, and revert if you're wrong.

Also, an efficient way to choose the columns/rows checks, and a clever way to represent data so that you avoid computing several times the same thing aren't obvious, even if you spent hundreds of hours on the puzzle.

I'm wondering also if there's special rules in his problem (the 7 parts is intriguing)

 

[Koren]

Nonogram solving is a NP-Complete problem

Funilly enough, I had read some articles about that, and completely forgot them. I fact, I've even written a couple attempts at solvers several years ago (I'm fond of the game).

http://debut.cis.nctu.edu.tw/Publications/pdfs/J54.pdf

There's not much to do outside of brute-forcing it

There's plently of ways to use probabilistic approches and efficient ways to do computations, though. That won't change the worst-case complexity, but that can still be night and day in practical cases.

 

[cpp_is_king]

The trick is that it's not obvious by hand... By scanning each line/columns, you can find black and white cells, and found cells gives helps you for other columns/rows.

But for some puzzles, you won't solve them that way. You'll have to make guesses, build on those guesses, and revert if you're wrong.

Also, an efficient way to choose the columns/rows checks, and a clever way to represent data so that you avoid computing several times the same thing aren't obvious, even if you spent hundreds of hours on the puzzle.

I'm wondering also if there's special rules in his problem (the 7 parts is intriguing)

But the thing is that it's very easy to make guesses.

Each cell has 3 states: 0 = unknown, 1 = definitely colored, -1 = definitely uncolored.

Each row/column has a number which is the number of cells with value 1 in that row/column. The number of cells with value -1 can be trivially computed. You can compute the number of possibilities for each row/column by (N ; P), where N is the length of the row/column, and P is the number of cells colored in that row/column and (N; P) is a binomial coefficient.

So, compute this value for each row/column and then sort the entire list of rows / columns by this number in ascending order. The row/column with the lowest number of possibilities is where you start guessing.

For each possibility:
    Activate the possibility by coloring the entire row/column with 1s and -1s
    For each cell that got colored 1 in the possibility, decrement the number of remaining colored cell in the converse row/column, and similarly for -1.
    If any rows/columns can be solved immediately (# of cells known to be 1 == # of total # of cells with 1 in them), solve them by marking them all with a 1.
    If any rows/columns are illegal (# of cells with 0 is less than # of remaining 1s), the original possibility is and is now known to be -1.
    Repeat this recursively until no more rows can be solved immediately.
    After no more rows can be solved immediately, back up to the beginning and recompute all possibility counts for each row/column.

At each step of the algorithm, you are doing all guesswork on a secondary copy of the grid. So, the result of a single run of this loop is a single cell getting updated with a -1 in the master copy of the grid. After that cell gets updated with a -1, you recompute the possibilities for that row and that column, then run the loop again.

This is just a starting point, you could add optimizations from here but this should guarantee a solution.

 

[Koren]

I may have misunderstood your algorithm, but I'd say you're working with the wrong rules... discrete tomography instead of nonograms?

I'll read carefully what you suggest later, but it's ofter exploding quite quickly in terms of possibilities... That being said, the general idea (find sure 1/-1, then find the highest 1 or -1 probability, clone the state, and recurse (and go back if you end in an impossibility) will definitively gives you a solution, since it'll check the whole tree till it find a solution.

But with time constraints for solving the problem, you'll enter more interesting issues (one of the reasons there's several research articles on the subject with different approaches)

Implementing a working solver, even slow, is probably a good start for this kind of test, though...

 

[cpp_is_king]

I may have misunderstood your algorithm, but I'd say you're working with the wrong rules... discrete tomography instead of nonograms?

I'll read carefully what you suggest later, but it's ofter exploding quite quickly in terms of possibilities... That being said, the general idea (find sure 1/-1, then find the highest 1 or -1 probability, clone the state, and recurse (and go back if you end in an impossibility) will definitively gives you a solution, since it'll check the whole tree till it find a solution.

But with time constraints for solving the problem, you'll enter more interesting issues (one of the reasons there's several research articles on the subject with different approaches)

Implementing a working solver, even slow, is probably a good start for this kind of test, though...

It's easily parallelizable though, so it doesn't really need to be all that efficient. You could check the first 32-64 columns all at once independently of one another, and knock out a good chunk of the grid on each pass.

Also, maybe we're talking about slightly different problems. The ones I did weren't called nonograms, so maybe it was slightly different. But basically you started with a rectangular grid, and each row and column in the grid were labelled with numbers telling how many colored squares were in that row / column. There was a unique solution, usually resulting in a picture or something.

Do you mean time constraints for coding up a solution (like on a programming test), or time constraints for the solver's execution time?

 

[Koren]

It's easily parallelizable though

That's still a huge tree to explore, and since there's more efficient solutions...

Also, maybe we're talking about slightly different problems. The ones I did weren't called nonograms, so maybe it was slightly different. But basically you started with a rectangular grid, and each row and column in the grid were labelled with numbers telling how many colored squares were in that row / column. There was a unique solution, usually resulting in a picture or something.

Yes, that's discrete tomography.

Nonograms (or Picross) are slighly differents, with more information: you're given the RLE encoding of 1 in each lines/columns.

For example

OXXXO
XOOOX
XOXOX
XOOOX
OXXXO

whould have
3
1 1
1 1 1
1 1
3

for each lines/columns.

It's easier, because on a line of length 5
> 3 means that the center cell is 1
> 2 1 means that the second cell is 1
etc.

That makes the tree exploration shorter (you have more data) but also more interesting...

Edit: still, that's not a good example, since

XXXOO
XOOXO
XOXOX
OXOOX
OOXXX

(and the symmetrical shape) are also solutions... and usually, the solution is unique.

Do you mean time constraints for coding up a solution (like on a programming test), or time constraints for the solver's execution time?

The latter... (which is also often used in those tests...)

 

[Ambitious]

A picross solver? That's interesting... I'd be curious to hear about the details. Are they public?


Unfortunately, I'm 99% sure it won't. You really have to find the handle and release it. :/

I'm interested in this too. Probably a lot of dynamic programming and base case and build stuff.

What sort of algorithm did you use?

The test was split into seven stages with increasing difficulty. In level 1, for instance, there was just a single row with a single block to solve. In level 2, multiple blocks were allowed. Level 3 introduced multiple colors for the blocks, and in level 4 a hint with some pre-filled cells was provided together with the input data. Level 5 did not include any new requirements and just tested some edge cases. Level 6, which is where I failed, was about expanding the solver from a single row to a full Picross puzzle with an arbitrary number of rows and columns. I don't know about level 7, as the level descriptions are only unlocked after finished the previous one. But I assume it simply contains more sophisticated puzzles, analogous to level 5.

There are zero implementation requirements. You're free to use any programming language and solve the tasks however you want. The input data was provided in the form of text files (one puzzle per row), and the solution had to be entered on their website, which simply tells you whether the solution is correct or incorrect. This goes for all of their tests, by the way.

Example Input: 10 2 1 5 2 3 ?????????2
Ten columns with two blocks. The first block has length 5 and color 1, the second one has length 3 and color 2. The last argument is the hint, which states that the very last cell has the color 2.

Expected Output: ??111??222
I suppose the meaning is obvious: A number means that the cell in its position is guaranteed to have that color, while questions marks indicate that the cells' colors are ambiguous.

As for my solution:
It's actually pretty simple. For the first block, I calculate the range which the block could potentially occupy. That's simply the length of the row minus the sum of the lengths of the subsequent blocks minus one separator for each pair of blocks (only if they have the same color). Then, I calculate all potential positions for the block within this range. Finally, the same function is called recursively for the rest of the blocks (just for the rest of the row, of course). The potential positions for the first block are combined with all results from the recursive call, which in turn consist of all potential positions for the second block combined with all possible positions for the third block and so on.

Finally, all that's left to do is to evaluate the resulting list of solutions and combine them into the string format described above. For each index: If all solutions have the same value in this position, append that value to the string. Otherwise, append a question mark.

As mentioned above, the next step would have been to solve entire Picross puzzles instead of just single rows. The test's over, but I'm nonetheless gonna finish the level just for fun. My plan is to 1) call my function for each row, 2) transpose the field so the columns are now rows, and 3) simply use my function again for each of them. Level 4 already required adding support for a hint, so I can simply use the existing values in the field as the hint in order to further restrict the solutions. Then, I will just have to repeat this three step process until the result is stable.

---------

Some of the tests are publicly availably (though you need to create an account), but this Picross test is not. However, I could send you the level descriptions and the test data for the first six levels via PM.

 

[Koren]

Many thanks for taking the time to type all this...

That's an interesting variation on the problem... I'm pretty there's an Euler problem on this, with colored blocks...

As mentioned above, the next step would have been to solve entire Picross puzzles instead of just single rows. The test's over, but I'm nonetheless gonna finish the level just for fun. My plan is to 1) call my function for each row, 2) transpose the field so the columns are now rows, and 3) simply use my function again for each of them. Level 4 already required adding support for a hint, so I can simply use the existing values in the field as the hint in order to further restrict the solutions. Then, I will just have to repeat this three step process until the result is stable.

That's at the very least a good start...

You'll get a sub-optimal result, though (far more ? than needed).

It would be interesting to change the ? into something like [0, 1, 3], id est "it can be empty, color 1, color 3 but not color 2", a kind of partial hint (you can still use your line solver, though, by calling it several times).

That being said, you'll get the optimal answer ony by exploring the full tree, doing guess on each "?" cells to see whether a given color is possible, but the computation time will explode :/

 

[cpp_is_king]

Many thanks for taking the time to type all this...

That's an interesting variation on the problem... I'm pretty there's an Euler problem on this, with colored blocks...


That's at the very least a good start...

You'll get a sub-optimal result, though (far more ? than needed).

It would be interesting to change the ? into something like [0, 1, 3], id est "it can be empty, color 1, color 3 but not color 2", a kind of partial hint (you can still use your line solver, though, by calling it several times).

That being said, you'll get the optimal answer ony by exploring the full tree, doing guess on each "?" cells to see whether a given color is possible, but the computation time will explode :/

Unless you're given a really contrived example, I honestly don't think the complexity will be all that bad if you start with lowest # of possibilities first. In my experience solving these by hand, figuring out just 1 cell successfully can have a large trickle down effect that knocks out large swaths of the puzzle all at once. Multiple colors does make it tricky, though.

 

[Koren]

Unless you're given a really contrived example, I honestly don't think the complexity will be all that bad if you start with lowest # of possibilities first.

Well, it's an interesting problem to code (or so I think). It can quickly take hours even on simple problems of reasonable size, though, if you're not efficient...

Multiple colors does make it tricky, though.

Beside the representation problem (and the possibility of a "null-length" separator), I think it works both ways (you'll have less immediate results on a single row/column, but the constraints between rows and columns are higher, so you may be able to reduce the number of possibilites quicker*).

That's a problem I'll probably try to tackle in the coming weeks, seems interesting.

* for example, if one color is rare than the other, you can try to solve the problem for this color only, and that gives you stronger clues for the rest.

 

[PetriP-TNT]

Jonathan Blow is doing series of blog posts where he refactors and cleans up BRAID:

http://number-none.com/blow/blog/programming/2016/07/16/braid_code_cleanup_1.html

 

[Pinewood]

Can anyone give pointers with the syntax stuff?

E: so I somewhat got the worksheet thing sorted but I cant figure out how I can compare/look up strings for a function.
For example i need to check cells if they have a certain string in them and then give me a true/false result.

Function datamine(i As Integer)
i = 1
While Worksheets("Data").Cells(2, i).String <> "Total Actual Cost"
i = i + 1
Wend
End function

Here the while clause gives me a syntax error, I know I need to find this specific string but not sure how the proper syntax is.

 

[Ambitious]

Take all the time you need, you've more important matters at hand. I wish you the best for your interview.

(and I'm pretty sure you shouldn't worry too much about your results, I'd say. Most probably, most candidates have done far worse. Think about what you would have done differently, given more time and a less stressful environment, should they discuss the matter with you)

Some more details about my result:
The mentioned that 188 applicants have successfully completed level 1. I'm rank 31. The ranking is determined by first by the number of completed levels, then by the total time needed.

In an earlier email, they mentioned that from experience they know that applicants who're in the first quarter of the ranking usually do really well in the company. While I'm not 100% sure, I can only assume they were referring to the first quarter of these 188 applicants, which would be the ranks 1-47.

Yeah.. I think I should be good. 90 minutes until the interview.

 

[Koren]

Some more details about my result:
The mentioned that 188 applicants have successfully completed level 1. I'm rank 31.

Told you so

That probably mean that at least one applicant missed the level 2 ^_^

Yeah.. I think I should be good. 90 minutes until the interview.

I wish you the best. Gambatte!

 

[CornBurrito]

Solved.

 

[Ambitious]

Told you so

That probably mean that at least one applicant missed the level 2 ^_^


I wish you the best. Gambatte!

Thanks.
So.. I just need to provide my personal information, then they will send me the contract. Yeah, it worked out. I've got the job.

The guy I talked to basically went through all the technologies they use and asked me to describe my experience with them, if any. He was satisfied with my level of experience and considered me a good fit for the company, so he would recommend to hire me. Barely five minutes later, the offer arrived.
He also said that my test result was "respectable".

The only bummer is the pay. For the first month, they're gonna hire me as an intern with a really low salary. If I do well, they're gonna hire me as a regular employee, but the salary range sounds like I'm gonna get less than at the other companies I applied at. Well, it's a shame, but I can only reiterate how amazing both the company and the job are. I will not pass up an opportunity like this.

 

[Koren]

Congratulations!

I'd say one month is nothing... You'll see what you get later, and you'll always be able to change your job if the salary is too low or ont interesting enough to compensate... Changing a job seems to be easier than finding one...

 

[PetriP-TNT]

Thanks.
So.. I just need to provide my personal information, then they will send me the contract. Yeah, it worked out. I've got the job.

The guy I talked to basically went through all the technologies they use and asked me to describe my experience with them, if any. He was satisfied with my level of experience and considered me a good fit for the company, so he would recommend to hire me. Barely five minutes later, the offer arrived.
He also said that my test result was "respectable".

The only bummer is the pay. For the first month, they're gonna hire me as an intern with a really low salary. If I do well, they're gonna hire me as a regular employee, but the salary range sounds like I'm gonna get less than at the other companies I applied at. Well, it's a shame, but I can only reiterate how amazing both the company and the job are. I will not pass up an opportunity like this.

Gongrats! The intern part kinda sucks but one month is a really short time by any measure, and money is not always everything.

 

[JeTmAn81]

Jonathan Blow is doing series of blog posts where he refactors and cleans up BRAID:

http://number-none.com/blow/blog/programming/2016/07/16/braid_code_cleanup_1.html

He's been making a lot of cool posts/videos on programming lately. There's one on there from a while back where he posted something from John Carmack talking about inlining code. Here's a section from that post:

On the subject of code duplication, I tracked all the bugs (problems that surfaced after I thought everything was working correctly) I fixed for a while, and I was quite surprised at how often copy-paste-modify operations resulted in subtle bugs that weren’t immediately obvious. For small vector operations on three or four things, I would often just past and modify a few characters like this:

v[0] = HF_MANTISSA(*(halfFloat_t *)((byte *)data + i*bytePitch+j*8+0));
v[1] = HF_MANTISSA(*(halfFloat_t *)((byte *)data + i*bytePitch+j*8+1));
v[2] = HF_MANTISSA(*(halfFloat_t *)((byte *)data + i*bytePitch+j*8+2));
v[3] = HF_MANTISSA(*(halfFloat_t *)((byte *)data + i*bytePitch+j*8+3));

Anybody know exactly what this code does? I start parsing it and get confused at the halfFloat_t casting part. He's casting data as a byte pointer and then accessing an offset, but after that I don't know what's really happening. I also don't know what HF_MANTISSA does. Obviously something floating point related.

 

[cpp_is_king]

He's been making a lot of cool posts/videos on programming lately. There's one on there from a while back where he posted something from John Carmack talking about inlining code. Here's a section from that post:



Anybody know exactly what this code does? I start parsing it and get confused at the halfFloat_t casting part. He's casting data as a byte pointer and then accessing an offset, but after that I don't know what's really happening. I also don't know what HF_MANTISSA does. Obviously something floating point related.

In C and C++, float is also called "single precision floating point" (32 bits) and double is called "double precision floating point" (64 bits).

Half precision floating point, as you might expect, is a 16-bit floating representation.

All floating point numbers according to IEEE 754 have 1 bit reserved for the sign, and then some number of bits allocated to the exponent, and the rest of the bits allocated to the "mantissa". In the case of half precision, it is 1 bit for sign, 5 bits for exponent, 10 bits for mantissa.

So, HF_MANTISSA(x) is probably equal to "x & 0x3FF".

So you'd think that whatever is at ((byte *)data + i*bytePitch+j*8 is a half-precision floating point number. But that appears to be not quite right, because it wouldn't make sense to be extracting the mantissa from 4 consecutive bytes in a row, since the mantissa is only in the last 10 bits.

Before that though he mentions that there would be subtle bugs, so I'm guessing this is one of those bugs. Most likely he had 4 half precision floating point numbers in a row, and he wanted to get all 4 mantissas out. It looks like a simple error in parentheses location, as if he moved the parentheses over like this:

v[0] = HF_MANTISSA(*((halfFloat_t *)((byte *)data + i*bytePitch+j*8)+0));
v[1] = HF_MANTISSA(*((halfFloat_t *)((byte *)data + i*bytePitch+j*8)+1));
v[2] = HF_MANTISSA(*((halfFloat_t *)((byte *)data + i*bytePitch+j*8)+2));
v[3] = HF_MANTISSA(*((halfFloat_t *)((byte *)data + i*bytePitch+j*8)+3));

it would probably work as expected. It would have been a lot more readable if he had done this:

halfFloat_t *floatArray = (halfFloat_t *)((byte *)data + i*bytePitch+j*8;
v[0] = HF_MANTISSA(floatArray[0]);
v[1] = HF_MANTISSA(floatArray[1]);
v[2] = HF_MANTISSA(floatArray[2]);
v[3] = HF_MANTISSA(floatArray[3]);

This code is still kind of dumb in my opinion, because compilers are pretty good at auto-vectorizing for you, so this is an unnecessary optimization that turned out to introduce a bug as well. My "cleaner" version makes it obvious that you'd be silly not to use a loop here, there's no point writing all this out.

 

[Koren]

This code is still kind of dumb in my opinion, because compilers are pretty good at auto-vectorizing for you, so this is an unnecessary optimization that turned out to introduce a bug as well. My "cleaner" version makes it obvious that you'd be silly not to use a loop here, there's no point writing all this out.

How would you write it?

Edit: damn, you edited just before I quoted, so my question is moot...


Also, isn't this a case where it would be sane to unroll a loop? Sometimes, I wish there was a way to say "I don't want a loop, but I write a loop so that I avoid copy-pasting errors, and improve readability.

A kind of "preprocessor loop". But a portable bone (not an __attribute__((optimize("unroll-loops"))) )

 

[cpp_is_king]

How would you write it?

Edit: damn, you edited just before I quoted, so my question is moot...


Also, isn't this a case where it would be sane to unroll a loop? Sometimes, I wish there was a way to say "I don't want a loop, but I write a loop so that I avoid copy-pasting errors, and improve readability.

A kind of "preprocessor loop". But a portable bone (not an __attribute__((optimize("unroll-loops"))) )

If you don't trust the compiler to do it for you, I guess you could unroll it yourself. But if you really don't trust it, just inspect the generated code first before you go make this kind of optimization. I would put loop unrolling and auto-vectorization into the "advanced" and "intermediate" categories respectively, with regards to how good the compiler technology is. And in the above example, I would classify it as "utterly trivial". So yea, the compiler will do it for you. Or at least, you should assume that it will unless you have specific evidence to the contrary (and a benchmark shows that it actually matters).

 

[Koren]

If you don't trust the compiler to do it for you, I guess you could unroll it yourself. But if you really don't trust it, just inspect the generated code first before you go make this kind of optimization.

Well, I usually trust it, but I won't be able to check whether it's done when someone else compile my source.

That's more a philosophical question... You can say "inline" for a function, which the compiler will take as a clue that you'd prefer it inlined (even if you let it decide what's the best). I would welcome a "unroll for" that do the same for loops. Would probably be useless in 99.99% of the situations, though. But since "inline" exists...

 

[cpp_is_king]

Well, I usually trust it, but I won't be able to check whether it's done when someone else compile my source.

That's more a philosophical question... You can say "inline" for a function, which the compiler will take as a clue that you'd prefer it inlined (even if you let it decide what's the best). I would welcome a "unroll for" that do the same for loops. Would probably be useless in 99.99% of the situations, though. But since "inline" exists...

clang has #pragma unroll, but MSVC doens't have anything and I don't know about GCC.

 

[Koren]

clang has #pragma unroll, but MSVC doens't have anything and I don't know about GCC.

gcc has __attribute__((optimize("unroll-loops")))

it works, but that's not great and definitively not portable.

Usually, it doesn't matter, but when I'm doing embedded, I'm often short of both cycles AND memory... The problem with letting the compiler decide is that it doesn't have a profiler to know where it matters to win a couple cycles at the expense of bytes and where it should go for shorter binary. Since C is used a lot in embedded, I'd say a portable way to give hints to the compiler would be welcome. Well...

 

[cpp_is_king]

gcc has __attribute__((optimize("unroll-loops")))

it works, but that's not great and definitively not portable.

Usually, it doesn't matter, but when I'm doing embedded, I'm often short of both cycles AND memory... The problem with letting the compiler decide is that it doesn't have a profiler to know where it matters to win a couple cycles at the expense of bytes and where it should go for shorter binary. Since C is used a lot in embedded, I'd say a portable way to give hints to the compiler would be welcome. Well...

clang, gcc, and msvc all support profile guided optimization. Have you tried it out? I'd be curious if it works well for the things you're trying to do.

 

[Koren]

clang, gcc, and msvc all support profile guided optimization. Have you tried it out?

No, I've somehow missed this feature... I'll look into it, thanks! That make so much sense that I wonder why I've never looked after such an option.

Although I'm profiling "by hand" because I can't run any realy profiler on the hardware, so it may be difficult to use.

 

[Kieli]

You have two sorted sets. Find the k'th smallest element in the union of the set in less than O(k) time. You may use binary search or divide-and-conquer.

I have no clue how to do this.... I'll keep cracking at it and report back to you guys tomorrow.

 

[Koren]

Is it a call for help?

Clue:

Spoiler

How would you reconstruct a single sorted set with two sorted sets in O?

Answer to clue:

Spoiler

Look into merge step from merge sorting...

A bit more precise:

Spoiler

Assuming both sets are empty, consider the first of both sets, and remove the smallest of the two. You have two ordered sets, and one is 1 element smaller. You were looking the the h-th, which one are you looking in the two new sets?

Beware, I guess the union of two sets don't allow for duplicates (?) so there's different cases whether the two elements are equal or not...

Solution in pseudo-code:

[spoiler]
    i1 = 0
    i2 = 0

    // "remove" the k-1 smallest elements
    while k>0 and i1<len(set1) and i2<len(set2):
        if set1[i1] == set2[i2] :
            i++
        else :
            k--
            if set1[i1] < set2[i2] :
                i1++
            else :
                i2++

    if i1 == len(set1) :
        return set2[i2+k]
    elif i2 == len(set2) :
        return set1[i1+k]
    else :
        return min(set1[i1], set2[i2]) 
[/spoiler]

By the way, you can find the k-th element even if the two sets are not sorted in O, I find this more surprising at first...

 

[cpp_is_king]

It says to do it in LESS than linear time

 

[Koren]

It says to do it in LESS than linear time

Yes, the solution I give is O(k) and not O.

(which isn't really "less than linear time", I'd say... at least, not without hypothesis on k)


But I found more surprising that you could find the k-th element in a unsorted list in* O than the k-th in sorted lists in O(k). I just took the chance to talk about QuickSelect which is, I think, a really interesting algorithm based on D&C.


* average complexity, not worst-case... O(n ln) in worst case if I'm not mistaken.

(well, you COULD use radix sort to have the k-th in, sort of, O in worst case, but that's not without hypothesis)

 

[cpp_is_king]

Yes, the solution I give is O(k) and not O.

Err... Maybe I'm missing something, but OP asks for a solution that is less than O(k)

 

[Ambitious]

Congratulations!

I'd say one month is nothing... You'll see what you get later, and you'll always be able to change your job if the salary is too low or ont interesting enough to compensate... Changing a job seems to be easier than finding one...

Gongrats! The intern part kinda sucks but one month is a really short time by any measure, and money is not always everything.

Thanks.
Yeah, money isn't everything. I wasn't looking for a job that would make me rich, but a job which 1) I would really like and 2) pays my bills. Which is the case for this one.

 

[Koren]

Err... Maybe I'm missing something, but OP asks for a solution that is less than O(k)

I think it's "O(k) or less"... But that need clarification, indeed.

If it's indeed a set union (so when you merge both, you'll have to remove duplicates), I can't see how you would be able to do less than k comparisons.

If that's not a set but a list of values (or sets without cross-duplicates), there's a O(log(k)) algorithm, if I'm not mistaken...

Something like

Spoiler

finding the i for which set1 < set2[k-i] < set1[i+1] using a dichotomic approach for i.

I'll try to clean the idea...

 

[Koren]

Something the code below is O(ln(k)), assuming you don't have to remove duplicates from the union set.

There's at least a bug (see comment), maybe more (I've yet to check how it works with duplicates, there may be < instead of <=). But I have to leave, so in the meantime...

Edit: yes, definitively a bug in case of duplicates, for example when k=0 and l1[0] = l2[0]. Will correct this later...

[spoiler]
def K2(l1, l2, k) :
    # Check whether there's not a complete list smaller than the result
    if k > len(l1) and l1[-1] < l2[k-len(l1)] :
        return l2[k-len(l1)]
    if k > len(l2) and l2[-1] < l1[k-len(l2)] :
        return l1[k-len(l2)]

    # check whether there's not a complete list greater than the result
    if k < len(l1) and l2[0] > l1[k] :
        return l1[k]
    if k < len(l2) and l1[0] > l2[k] :
        return l2[k]

    # OK, now the result have values greater and smaller in both lists, dichotomy!

    a, n = 0, k-1  # <- Beware, not correct: you have to ensure that 1 <= i < len(l1)
                   # and 0 < k-i < len(l2)
                   # that's not the good starting values...
    
    while n > 1 :
        n = (n+1)//2
        i = a+n
        if l2[k-i-1] > l1[i] :
            a += n
        elif not (l1[i-1] > l2[k-i]) :
            break

    i = a+n

    # The k numbers in l1[0..i-1] and l2[0..k-i-1] are smaller than
    # l1[i] and l2[k-i]
    # So the answer is either l1[i-1] or l2[k-i-1], the largest one
    return max(l1[i-1], l2[k-i-1])
[/spoiler]

 

[cpp_is_king]

If the two lists can contain duplicates I don't think it's possible to do it in strictly less than O(k). Imagine in the worst case the two lists each contain exactly the same k elements. For example:

set A: 1, 3, 5, 7, 9, 11, 13, 15
set B: 1, 3, 5, 7, 9, 11, 13, 15

k = 8

You know that if A &#8746; B has more than k elements, it's not as simple as just choosing set A or B outright.

But there is no way to know without checking all k items in set A whether A &#8746; B would have k elements or more than k elements.

If we can assume that A &#8745; B = Ø then yes, we can do it in strictly less than O(k)

 

[Koren]

If the two lists can contain duplicates I don't think it's possible to do it in strictly less than O(k).

Yes, that was the feeling I had when I said we should need at least O(k) comparison because of the union. Your proof is short and convincing.

If we can assume that A &#8745; B = Ø then yes, we can do it in strictly less than O(k)

Indeed, you can have O(ln(k)).

Also, you can have O(ln(k)) if A and B are just ordered lists (even if A or B have duplicates). The code above could work, but it's a mess, because there's so many side-cases. I have thought of a nicer solution in the bus... (edit: or rather, it's exactly the same idea, but written differently, which makes things easier to understand and the code easier to write correctly)

First, you can find in O( ln(k) ) the k lowest elements of a decreasing-increasing list by using dichotomy, provided you know where the minimum value is (+/-1 doesn't matter).

Then, you can trivially transform the two increasing lists in a decreasing-increasing list by manipulating the indexes.

Then, the k-th value (0-indexed) is simply the largest of the k+1 smallest values of the increasing-decreasing list.

Commented solution in Python (that I hope is correct, 50000 random tests haven't found an error, I don't have time to check the perfect coverage of those tests, though)

[spoiler]
# Function to transform two increasing lists into a decreasing-increasing one
def DIMerge(l1, l2, i) :
    if i<len(l1) :
        return l1[len(l1)-1-i]
    return l2[i-len(l1)]

# Function that research the h-th element
def K(l1, l2, kth) :
    # Total length of both lists
    length = len(l1) + len(l2)

    # Ensure there's enough values
    if kth >= length :
        return None

    # Ensure lists are not empty
    if len(l1) == 0 :
        return l2[kth]
    if len(l2) == 0 :
        return l1[kth]
    
    # Is the wanted value the largest?
    if kth == length-1 :
        return max(l1[-1], l2[-1])

    # Now there's at least a larger value, useful later
    
    # Want to find the k = kth+1 smallest values
    k = kth+1

    # Check (signed integer) whether we're in the decreasing or
    # the increasing part of the decreasing-increasing list
    def dir(i) :
        return DIMerge(l1, l2, i+k) - DIMerge(l1, l2, i)

    # Dichotomy!
    a = max(0, len(l1)-k)
    
    if dir(a) > 0 :
        b = a
    else :
        b = min(length-k, len(l1))

        while b > a+1 :
            m = (a+b)//2
            if dir(m) > 0 :
                b = m
            else :
                a = m

    # The kth value is at either index b or b+k-1 of
    # the increasing-decreasing list
    return max(DIMerge(l1, l2, b), DIMerge(l1, l2, b+k-1))
[/spoiler]

 

[Gurrry]

Speaking of python, I could use some help on this project for my class. Its a pokemon project where we are practicing creating classes and functions.

However, I have no idea how to get this program to print out what I need.

Basically, the user is going to enter in a pokemon name and an ability for as many pokemon as they want.

Then at the end, it has to print out in this fashion:

Pokemon #1: Charmander
Pokemon #1 Ability: Growl

Pokemon #2: Squirtle
Pokemon #2 Ability: Water Gun

etc.

Right now in the code in the display_pokemon(pokemon_list) function, I cant get it to print out anything. Anytime I try, it gives me this weird hexadecimal print statement.

[<__main__.Pokemon object at 0x00E9E970>]

I cant figure out how to get this list to print anywhere i put it.

Any ideas?

http://pastebin.com/RtMH6gXx

note: right now i just put pass into that function because ive tried a for loop, regular print statements, etc and all of them keep giving me that weird "[<__main__.Pokemon object at 0x00E9E970>]" thing.