Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

narbsy: Jun 2, 2007

Appa Time!: did you take out the even numbers in your test? That can help a large amount. I.e. test 2, then skip by 2s from 3 on. Makes it go quicker-er. I did it in javascript and it finished pretty quickly, if I recall correctly.

Yeah, just tested now. It took about 30 seconds for 600851475143, the new number for problem 3.

narbsy fucked around with this message at 23:04 on Feb 26, 2008

# ¿ Feb 26, 2008 22:52

Adbot: ADBOT LOVES YOU

# ¿ May 7, 2024 01:02

narbsy: Jun 2, 2007

Appa Time! Yeah, I build a list of primes first to test against. Here's my code if you'd like; it's pretty simple. I'm not very complex.

code:

function findPrimes(howfar)
{
	var primes = new Array();
	
	for(var i = 3; i < howfar; i += 2)
	{
		if(isPrime(i, primes)){primes.push(i);}
	}
	primes.unshift(2*1);
	return primes;
}
function isPrime(number, primes)
{
	var root = Math.sqrt(number*1);
	if(primes.length == 0){return true);
	
	for(var i = 0; i < primes.length; i++)
	{
		if(primes[i]*1 > root){return true;}
		if(number*1 % primes[i]*1 == 0){return false;}
	}
	return true;
}
function getPrimeFactors(number)
{
	number = number*1;
	var primes = findPrimes(Math.sqrt(number));
	var factors = new Array();
	
	for(i = 0; i < primes.length; i++)
	{
		if(number % primes[i] == 0)
		{
			factors.push(primes[i]);
		}
	}
	return factors;
}

# ¿ Feb 27, 2008 05:37

narbsy: Jun 2, 2007

No problem Appa Time!! My pleasure.

Triangulum: There is a site devoted to TI programming, here. There's a ton of stuff, and if all else fails you can download an example program that does what you want to learn from.

# ¿ Feb 27, 2008 22:04

narbsy: Jun 2, 2007

You can also get an emulator for the TI-83 and open it up in there. I think there were a few listed on the website.

# ¿ Feb 28, 2008 03:33

narbsy: Jun 2, 2007

I'm not entirely sure, and would have to program out an example to be completely sure (but not in Pascal), that the point of the 6k+/-1 optimization is that you can skip 6 each time, with the exception of your base cases (2 and 3).

I.e. start at 6; check 5 and 7, go to 12. check 11 and 13, go to 18, much like the += 2 to check odds only.

e: The code looked like it was checking every number for being of the form 6k+/-1, and then going from there, but I could be wrong. Not that great at reading Pascal.

narbsy fucked around with this message at 15:49 on May 25, 2008

# ¿ May 25, 2008 08:32

narbsy: Jun 2, 2007

rjmccall posted:

I don't know the Excel API well enough to know if you're doing something obviously wrong there, but if you're using this function as, well, a function, you'll want
code:
Return State
at the end.

I believe in Excel VBA it's the old style, so <FunctionName> = State.

If return doesn't work, try that.

Also, it might be faster if you told it to process a specific range of the column and iterated over each cell, and populated a cell in another column.

# ¿ Sep 15, 2008 04:46

narbsy: Jun 2, 2007

floWenoL posted:

Oh, right. Actually, it suffices to exchange the changed element with its parent while necessary. That's log(n) and preserves the heap property. I guess you'd also have to store per-node info as to where it is in the heap (and update it). Hmm.

The remove/add thing does work; Java code below. However .. O(n) solution is more awesome.

code:

		while( ! pq.isEmpty() ) {
			Pair<V> curr = pq.poll();
			int temp;
			
			Collection<E> edges = g.outgoingEdges(curr.vertex);
			for ( E e : edges ){
				temp = cost.get(e.src()) + e.weight();
				if ( temp < cost.get(e.dest())) {// e requires attention, relax e
						cost.put(e.dest(), temp);
						previous.put(e.dest(), e.src());
						Pair<V> p = new Pair<V>(temp, e.dest());
						pq.remove(p);
						pq.offer(p);			//pq fix
				}
			}
		}

# ¿ Nov 25, 2008 19:11

narbsy: Jun 2, 2007

Bonus posted:

Cool, I just implemented the trie by using a field which increases and decreases in size but I have to traverse when seeing which edge to follow. It performs alright for inserting, looking up and then deleting 1.5M words, but not as well as the AVL tree and hash table. I'll try doing some branching to see how fast it is if I switch to a hash table for storing edges or a field that I can index in O(1) time.

I've done an analysis of the input files and I've found that they contain 78 different ASCII characters, so that shouldn't be a problem.

Later I'll have to add the ability to find the n nearest words for any word by Levenshtein distance and I have a feeling tries will give good performance there. AVL trees will probably be alright for that too but I have no idea if it's even possible to implement that efficiently if I'm storing the words in a hash table.

That's pretty cool. There's another self-balancing tree that's faster than AVL called the DSW algorithm. It's different in the sense that it doesn't balance on each insert, delete but rather waits and then turns the tree into a "vine" (a linked list), and then re-forms the tree by unrolling the "vine". It is superb.

I always meant to implement a trie but never did

# ¿ Dec 8, 2008 13:53

narbsy: Jun 2, 2007

Sleeper354 posted:

I have a question related to threading. I'm taking a class where its a pretty big chunk. I want to know the difference between the following:

Condition Variable
Lock
Semaphore

From my understanding (my most recent one from observing) is that a condition variable is just that a variable, a Lock is a condition variable, and a Semaphore is a combination of the previous two. However, this definition has changed several times. I understand how they work, but I'm having trouble distinguishing them.

A condition variable is more than just a variable. There are two methods defined for these guys - wait, and notify (sometimes notifyAll). When something is wait()ing for a condition variable, it's thread is blocked and it will wait() until the end of time, or it is notify()ed that the resource the condition variable is protecting is available.

By a Lock, I'll guess you mean a mutex. A mutex allows one and only one thing to access a resource at a time. If a thread asks the mutex to lock for it, the mutex waits until it has been unlocked first, and then resumes execution for the thread.

A semaphore is similar to a mutex, but can model more than one resource. A good example for this is like a bathroom with multiple stalls; a semaphore models this excellently. It keeps a queue of those who have locked it with P(), and a count of how many resources are available currently. A resource is released with V(), and another thread given access (as P() blocks).

I'm not the most coherent, so let me know if this doesn't make sense.

# ¿ Dec 14, 2008 21:24

narbsy: Jun 2, 2007

Emo.fm posted:

If you can't get mySQL set up, use SQLite; if you're using PHP's PDO, you can write essentially the same SQL for mySQL as SQLite, with only small differences. It only requires a file per db. For smallish things it's reasonably speedy. Not to mention, it is far, far, far better than XML to store data.

# ¿ Dec 21, 2008 01:40

narbsy: Jun 2, 2007

GT_Onizuka posted:

You might want to check out the CS:APP shell lab for this. It's what we used in my systems class and was a pretty fun lab.

Seconding this, it is a fun lab, and pretty informative. The book is a really good resource for the lab.

# ¿ Feb 6, 2009 03:24

narbsy: Jun 2, 2007

outlier posted:

An oddly specific question - being used to editing code on the Mac with TextMate, I'm happy using E (a TextMate look-a-like) on the PC. But on Ubuntu? Every editor is giving me the creeps.

I don't want an editor that requires I set up a "project". I don't want something I have to choose and open every file I need. What I like about TextMate is being able to open a folder as a project, and have the folder structure there in a sidebar as I edit the code in multiple tabs. Is there anything like this for Linux?

You can get creative and set gedit up to do the file structure thing. I may be hallucinating, but I think I've also seen gedit do code suggestion for CSS. Unsure if it can do that for anything else.

# ¿ Feb 11, 2009 22:07

narbsy: Jun 2, 2007

royallthefourth posted:

If you're doing CS, your professors are going to make you do lots of simple things the hard way. You'll probably take an assembler class later, which will see you doing things like implementing your own floating point numbers or divisions algorithms.

Complex operations like renaming files in a language like PHP or Python is trivial. In PHP, issues like pointers, memory management, and even data types are no longer an issue. You can't forget about the altogether, but it's much easier to deal with.

Of all languages you could mention for scripting, why PHP?

Perl, Python, Ruby are all recent choices; bash is an older one.

PHP!??!?

# ¿ Feb 19, 2009 03:38

Adbot: ADBOT LOVES YOU

# ¿ May 7, 2024 01:02

narbsy: Jun 2, 2007

fletcher posted:

I want to parse a human readable string of time spans, not really sure how to approach this to make it clean. I'm sure I could come up with something that works, but I have a feeling it will be a sloppy mess of poo poo if I don't go in with a plan of attack. I'll be using Java for this.

The basic format is:
1:00pm to 2:00pm and 3:00pm to 4:00pm

It can come in other variations:
1:15-2
1-2 3-4
1-2 and 3-4
1 to 2 and 3-4
1300-1400

I also want to handle overlap:
1-2 and 2-3 turns into 1-3

Can anybody give me a nudge in the right direction?

Check out the Ruby gem Chronic, which does natural date/time parsing. Might make life easier if it works with the format you've got.

# ¿ Mar 19, 2009 00:24

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread