Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - harold

Pages: 1 2 [3] 4 5 ... 16
Computer Programming / Re: Free C textbook.
« on: November 24, 2014, 03:34:46 am »
I had a look and it makes the same mistake as almost everyone does when discussing Huffman decoding, it only mentions tree-walking.
Tree-walking is a great way to intuitively show that decoding is possible at all, but it's a bad way to actually do it, and actually the code for table-based decoding is shorted and simpler (once you understand the idea).
Can we send in suggestions?

nice book overall.

Math and Science / Re: Graph coloring mini challenge
« on: November 06, 2014, 03:00:24 pm »
Any progress, xeda?

Other people: come on guys, it's great fun to try it :)

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: October 31, 2014, 12:05:02 pm »
After some discussion on an other forum, I've decided that this issue will actually not be resolved.
Only the "normal" behaviour (the usual descriptions of how redstone elements work) will be replicated, not this sort of thing that doesn't follow any clear set of rules.

edit: I've worked on it again, so despite appearances it may not be entirely dead. Simulation still has severe bugs though, so it may not go anywhere.

Community Contests / Re: Code Golf Contest #12: Befunge Numbers
« on: October 07, 2014, 02:32:00 pm »
With the fancy trick, the loop that checks the products is the slowest part (benchmarking shows that part to take about 10 times as long as the loop that checks the sums), though I can't prove this bound, I would theorize that makes it O(n1.5) (obviously without the trick, checking the sums takes much longer since there are far more of them). I'll look into how (if at all) that could be improved.

Community Contests / Re: Code Golf Contest #12: Befunge Numbers
« on: October 07, 2014, 01:42:21 pm »
I don't know, actually I think my algorithm also runs in O(n2), but might have a lower constant factor I guess?
Basically I make all the minimal expressions up to and including the one that's necessary, and generating any one of them inspects O(n) things (products and sums). I did the higher ones with more trickery (costs more code so that's not the version I submitted) to avoid testing most sums.

Community Contests / Re: Code Golf Contest #12: Befunge Numbers
« on: October 06, 2014, 04:49:38 am »
Probably undecidable in general, if in "any" is included the control flow operators and so on, there would be a huge class of programs that might output the number you want but you don't know if they even halt.

By the way here are a couple of test cases (you probably won't get the same answer of course)
1337 = 7379**2+* (9 characters)
9001 = 55589****1+ (11 characters)
12345 = 364888***9+*+ (13 characters)
987654 = 8885688***9+***6+ (17 characters)
9876532 = 2258885688***9+***5+**+ (23 characters)
9876543 = 789**4+56899****2+*7+ (21 characters)
53887677 = 365688**7+7899**7+*9+**9+*+ (27 characters) (lowest number that requires 27 characters)
98765432 = 489*2+6927779****5+**1+** (25 characters)

Community Contests / Re: Code Golf Contest #12: Befunge Numbers
« on: October 05, 2014, 03:04:42 pm »
Note that optimal solutions are usually not unique (you can obviously switch the first and second operands of every operator, and that's not even all).

Math and Science / Graph coloring mini challenge
« on: October 05, 2014, 11:56:58 am »
You've probably heard that a map (with some restrictions: no enclaves, no "bridges", countries meeting at a point are not considered adjacent) can be colored using only four colors.

Graph coloring is a bit more general: given a bunch of "nodes" with "edges" between them, color the nodes such that no two adjacent (ie, have an edge between them) nodes have the same color. A trivial way to do that would be giving every node its own color. A bit better would be to start at the first node, give it color 0, then the second node can have color 0 or 1 (depending on whether it's connected to the first) and so on, and there are tricks you can play here with the order in which you visit the nodes (it matters a lot, and in fact there is an order such that you get an optimal coloring this way, there are many interesting things you can do there).

The challenge is usually to find such a coloring with the fewest possible number of colors, but you could also ask: given a certain number of colors you're allowed to use, can you color the graph? (this is an example of an NP-complete problem)

Anyway for this mini challenge, there are two graphs (I could make more, if necessary), a small one with 50 nodes and 350 edges, and a big one with 500 nodes and 62423 edges. The second one is particularly nasty not so much because it has 500 nodes, but mainly because it has about half as many edges as it could maximally have, which is about the worst case (more edges and it becomes so constrained that there are not many solutions to try, less edges and you won't need as many colours so again there are few solution). But whatever, the point is, there's an easy one and a hard one. The east one is still big enough that you can't blindly try everything though, you have to be at least slightly clever.

50 graph: gc50.txt
500 graph: gc500.txt
Format: first line is [number of nodes] [number of edges]
Other lines are the edges, a pair of nodes that has a link between them.
The last line is empty (so that every line you read can end in \r\n to simplify parsing or whatever), and there are exactly as many edges as advertised (so you can read them in a for loop and not care about end of file).

Challenges (easy):
  • Find an optimal coloring for gc50.
  • Find a coloring with at most 80 colors for gc500.
  • Prove that you need at least 11 colors to color gc500.

Challenges (medium):
  • Find a coloring with at most 60 colors for gc500.

Challenges (hard):
  • Find a coloring with at most 52 (protip: that's not optimal) colors for gc500.

Challenges (impossible):
  • Find an optimal coloring for gc500. (I don't even know how many colors it will have, so don't ask)

Challenges (other):
  • Find a non-trivial lower bound on the number of colors necessary for gc500 (deliver proof/explanation of why it's a lower bound).

PM answers to me (don't post colorings please, feel free to post lower bounds), discuss everything (as long as it doesn't violate "don't post colorings"), pretty much anything goes with respect to how you solve this but it will be more interesting for you if you play with the problems yourself instead of just dumping them into open source solvers.

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 27, 2014, 04:08:36 pm »
Eiyeron, it does this thing in all directions. In the "2 repeaters, one locks the other, both receive power at the same time" case, the locker always win.

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 09:38:36 pm »
Is it the orientation though? In my test, also moving the level made a difference. Perhaps it's the relative position of the level with repeaters?

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 07:28:05 pm »
Ah yes, that shows the problem pretty well.
I do most of my experiments in 1.6.2, I haven't found any differences between that and 1.7.10 though. Doesn't mean there aren't any, but from what I've heard, this area of redstone hasn't seen much change after 1.5

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 06:29:17 pm »
A repeater is itself a block, so it adds a delay of 1 tick minimum.
That can't be the whole story though. Both repeaters have a delay of 1 tick, so both would turn on at the same moment (1 tick after the signal turns on). However, in the case with just the 2 repeaters, the one that locks the other (let's call it A, and the one that is locked B) consistently turns on first.
Then if you add a third repeater C that can be locked by repeater B, and then power is supplied to all three simultaneously, obviously A always turns on since nothing prevents it from doing that, so it locks B, but then B either locks C or doesn't lock C, depending on whether or not B was locked in its ON state (which one wins depends on where power flows from). So now the entire situation is changed, even though all that happened is that we gave repeater B the chance to lock something.

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 05:28:53 pm »
You need a repeater from the side there of course, and if you add that .. it still locks in OFF state.

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 05:14:54 pm »
Oh, I thought it was your implementation... The reason could be that minecraft does it the way I mentioned: Random ticks per chunk, but it has to tick every block in a chunk first before it ticks a block the second time (I'm not sure how to explain it better). What happens if you connect two not gates to the repeater inputs (input & lock) instead of a repeater? Does the behaviour change if you change orientation, location etc.?
Could you draw the circuit?

With statefulness my old Minecraft clone (years ago, lwjgl) achieved a 2-calls-per-chunk renderer :P (IIRC. It was an experiment how to get most performance out of LWJGL with a lot of cubes and big worlds)
Well how? glBindVertexArray, glDrawElements .. nothing left to change state. I'd have 2 calls if it wasn't for the uniform buffer.

Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 04:56:57 pm »
Debugging this should be easy. Do a breakpoint at the repeater's tick function, in the block to lock it and look at the redstone state of the inputs.
I don't see any differences of the two pictures though. (Uh, this sentence sounds and looks weird. Where's my mistake?)
How do I debug minecraft? To clarify, those pictures are of how it should be, not of how it currently is in my clone.

A BIT wasteful? That's a massive understatement.. The normal is unnecessary (the GPU calculates it faster in a shader every frame), as is the redstone dust stuff. I would also replace the texture array index by something stateful. I don't know whether glBindTexture(id, GL_TEXTURE_2D) still exists.
I'd have to add a geometry shader stage for the normals. And do some pretty wonky stuff in it. It's possible, but not worth it especially since the reason would be to make things worse. After all, this isn't about turning 1GB into 500MB, it's about turning 8MB or so into 500MB, that doesn't make any sense. The biggest problem would remain anyway: it just plain takes too much to generate all that geometry data. It would still do so without normals and crap.
And statefulness would break my nice 3-calls-per-chunk renderer.

Pages: 1 2 [3] 4 5 ... 16