Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 298 299 [300] 301 302 ... 796

Author Topic: if self.isCoder(): post() #Programming Thread  (Read 902558 times)

Vector

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4485 on: June 12, 2013, 09:42:41 pm »

Hahahaha, I see you know my unannounced direction of choice ;)

Okay, I'll try that.
Logged
"The question of the usefulness of poetry arises only in periods of its decline, while in periods of its flowering, no one doubts its total uselessness." - Boris Pasternak

nonbinary/genderfluid/genderqueer renegade mathematician and mafia subforum limpet. please avoid quoting me.

pronouns: prefer neutral ones, others are fine. height: 5'3".

Mego

  • Bay Watcher
  • [PREFSTRING:MADNESS]
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4486 on: June 12, 2013, 09:45:02 pm »

Lucky guess :P

Vector

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4487 on: June 12, 2013, 09:59:01 pm »

Well, to be honest...

What I really want is a job.  Because I'm making $12/hour right now, when I'm employed, which is infrequent.
Logged
"The question of the usefulness of poetry arises only in periods of its decline, while in periods of its flowering, no one doubts its total uselessness." - Boris Pasternak

nonbinary/genderfluid/genderqueer renegade mathematician and mafia subforum limpet. please avoid quoting me.

pronouns: prefer neutral ones, others are fine. height: 5'3".

Stargrasper

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4488 on: June 12, 2013, 10:17:19 pm »

If you're doing Java, get used to using objects.  They're required, and proper use of objects and inheritance makes life much easier.  Also learn to intelligently split things between packages.

With C++, creative use of multiple inheritance can be helpful for game programming.  And learn to recognize when objects are overkill and something simpler would work.

Also, reinventing the wheel if good for learning but not so much for actual development.  Even games like Minecraft use LWJGL, a game programming library for Java.

Skills like these lend themselves well to game programming, but may or may not lend themselves well to programming anything else.  If you want a job and don't want to spend the next two years writing a game that's good enough many people would pay money for it, you'll want to polish other programming skills as well.
Logged

alway

  • Bay Watcher
  • 🏳️‍⚧️
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4489 on: June 12, 2013, 10:49:22 pm »

A suggestion if the end goal is a good job: don't do games. Game development is more competitive, has worse hours and gets lower pay than you would get doing more general software development. From what I've seen, it may even be a better fit for the pre-existing skills of someone with a math major.

On the other hand, game developers have more creative freedom, particularly at smaller studios. If you are going to do games, make sure you really want to do games, because there will be a price to pay for it. Additionally, if you are a good game programmer, the skills should translate well enough to get a decent non-game related job.

Some other areas:

A particular combination I've seen work well is math undergrad, followed up by AI. Modern probabilistic AI can be fairly rigorous in terms of the math involved, and people like Google and Microsoft really want people who are good at it. And by that I mean I know someone who had an undergrad math major, followed by a game dev masters focusing on AI who got a starting offer from Google for 6 figures.

There's also networking. Those who can write good networking code are uncommon; those who can do so while also enjoying it are very rare. As such, that's another high-pay direction.

Another big one is highly parallel systems. From what I've seen currently, there's a fairly good demand for people who can take an algorithm, parallelize it, then put it on a highly parallel system (like a GPU, or even a supercomputer full of GPUs) using things like OpenCL or CUDA. There's quite a lot of image processing jobs there; medical imaging analysis is a big one I've seen a few times.

So make sure you look around a bit before deciding on any particular direction. A math major will be really helpful for some, and utterly useless for others.
Logged

Skyrunner

  • Bay Watcher
  • ?!?!
    • View Profile
    • Portfolio
Re: if self.isCoder(): post() #Programming Thread
« Reply #4490 on: June 12, 2013, 10:54:03 pm »

It's Vector o_O
Logged

bay12 lower boards IRC:irc.darkmyst.org @ #bay12lb
"Oh, they never lie. They dissemble, evade, prevaricate, confoud, confuse, distract, obscure, subtly misrepresent and willfully misunderstand with what often appears to be a positively gleeful relish ... but they never lie" -- Look To Windward

Vector

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4491 on: June 12, 2013, 10:54:47 pm »

. . . Yes?  You rang?
Logged
"The question of the usefulness of poetry arises only in periods of its decline, while in periods of its flowering, no one doubts its total uselessness." - Boris Pasternak

nonbinary/genderfluid/genderqueer renegade mathematician and mafia subforum limpet. please avoid quoting me.

pronouns: prefer neutral ones, others are fine. height: 5'3".

Skyrunner

  • Bay Watcher
  • ?!?!
    • View Profile
    • Portfolio
Re: if self.isCoder(): post() #Programming Thread
« Reply #4492 on: June 12, 2013, 11:01:19 pm »

What's rang? >_>

Anyhow, my true purpose for posting here is because I recieved orders to learn greedy programming, dynamic programming, and backtracking programming to enter the Seoul (regional) Informatics Olympiad. <__< I can't understand the little book that introduces them. :/ I'm pretty sure I'm going to fail at it, but I apparently /must/ participate. What to do? :S

((Clearly algorithms aren't my forte, because the best way to tag coasts in a map for my game I found had a worst-case of 8n (naive method), while someone else helped my and drew up a 5n algorithm right off the bat. Also I think I took a long time to understand A*.))

Wait, if algorithms are important in CS, does that mean I'm not fit for it? D: nuuu.
Logged

bay12 lower boards IRC:irc.darkmyst.org @ #bay12lb
"Oh, they never lie. They dissemble, evade, prevaricate, confoud, confuse, distract, obscure, subtly misrepresent and willfully misunderstand with what often appears to be a positively gleeful relish ... but they never lie" -- Look To Windward

Mego

  • Bay Watcher
  • [PREFSTRING:MADNESS]
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4493 on: June 12, 2013, 11:23:42 pm »

I can explain the concept of a greedy algorithm pretty easily for you. At every option, the greedy algorithm picks the optimal choice, even if it does not lead to the most optimal end result. Consider this weighted graph:

Code: [Select]
     @
    / \
   4   6
    \ / \
     4   1
      \ /
       G

The shortest distance from @ to G is 7 (by way of the 6 and the 1). However, a greedy algorithm would pick the 4 at the first fork, because it was the optimal choice for that decision, leading to a distance of 8. Greedy algorithms also never look back; once a choice is made, it sticks with it.

An example of a problem that a greedy algorithm is the best solution for is making change. If you needed to give someone 63 cents, the first thing you would do is use quarters until the number went under 25 cents, and then so on. The optimal solution is 6 coins (2 quarters, a dime, and 3 pennies), which the greedy algorithm would find.

MadocComadrin

  • Bay Watcher
  • A mysterious laboratory goblin!
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4494 on: June 12, 2013, 11:30:40 pm »

The difference of 8n and 5n aren't really that big unless you don't have the luxury of high processing power (eg. an embedded system where half your code ends up being assembly). Being bad at algorithm design would be making an average case O(N^2) where there exists a worst case O(N). :P

Anyway, what do you need to know about the algorithm design paradigms and what are you having trouble understanding. Or, what might you be expected to do in the Olympiad with the knowledge?
Logged

Skyrunner

  • Bay Watcher
  • ?!?!
    • View Profile
    • Portfolio
Re: if self.isCoder(): post() #Programming Thread
« Reply #4495 on: June 13, 2013, 12:15:02 am »

Well... Apparently, dynamic programming is like optimally testing all combinations, while backtracking probably uses nodes each time it makes a choice until it finds an optimal solution? >_>


Blehh. It's hard to say what I need when I don't even know what I need. The olympiad is similar to the international informatics olympiad, just easier.
Logged

bay12 lower boards IRC:irc.darkmyst.org @ #bay12lb
"Oh, they never lie. They dissemble, evade, prevaricate, confoud, confuse, distract, obscure, subtly misrepresent and willfully misunderstand with what often appears to be a positively gleeful relish ... but they never lie" -- Look To Windward

Mephisto

  • Bay Watcher
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4496 on: June 13, 2013, 08:00:54 am »

The canonical example for backtracking is the eight queens puzzle.

Dynamic programming is where you break a problem down into smaller, more easily-solvable problems. Possibly the most easily understood example is the fibonacci sequence. I don't know fib(10), but I can find fib(9) and fib(8). I don't know fib(9), but I can find... and so on until it's all adding 1s and 0s. Bonus points for also implementing some form of memoization.
Logged

Siquo

  • Bay Watcher
  • Procedurally generated
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4497 on: June 13, 2013, 08:17:59 am »

Wait, if algorithms are important in CS, does that mean I'm not fit for it? D: nuuu.
Yes, they're important in CS. No, you will probably not use any in a real job. Yes, you will still need to know the basics of them in a real job otherwise when you do need them you'll look like a chump.
Logged

This one thread is mine. MIIIIINE!!! And it will remain a happy, friendly, encouraging place, whether you lot like it or not. 
will rena,eme sique to sique sxds-- siquo if sucessufil
(cant spel siqou a. every speling looks wroing (hate this))

MadocComadrin

  • Bay Watcher
  • A mysterious laboratory goblin!
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4498 on: June 13, 2013, 11:55:11 pm »

I'll describe all three (plus divide and conquer) the way I was taught them and see them.

Greedy Algorithms:
Greedy algorithms make locally optimal choices, hoping that it leads to an optimal overall solution or a close enough approximation. For some problems, a well-designed greedy algorithm will find the most optimal solution. Other times, it's simply a trade-off, gaining speed in exchange for accuracy.

Consider this extremely simple shortest path algorithm: at every node, choose the neighbor with the shortest distance. It sounds sensible upfront, but upon further examination, it's easy to see where it could give a solution that really isn't the shortest path: for example, say the algorithm give a path with the following distances 2, 7, 3, 8--20 overall. However, there could be a path like this too 3, 1, 2, 4--10 overall--yet the algorithm would miss it as the first 2 is shorter than the 3.

Dynamic Programming:
I find it hard to define dynamic programming as what it is. Instead, I'm going to define it in terms of what you should use it for. Some people (and Wikipedia) will tell you that dynamic programming is useful for problems that exhibit Optimal Substructure and Overlapping Subproblems, and often makes use of memoization. That tells you pretty much everything and nothing at the same time.

What is Optimal Substructure?
Optimal substructure involves being able break a problem into smaller, concise subproblems. If you can solve these subproblems optimally and combine their solutions to get the optimal solution to the overall problem, you have optimal substructure. (NOTE: this is different than simply making the optimal local choice--the local choice is unaware, and often simply a step rather than an entire subproblem).

Example -- Shortest paths exhibit optimal substructure too. For example, if you know the shortest path to Rome from Vienna passes through Ravenna, then you can find that path by finding the shortest path from Vienna to Ravenna, and the shortest path from Ravenna to Rome and combine them. Likewise, many recursive problems exhibit optimal substructure. For example, Mephisto brought up Fibonacci numbers: Calculating Fib(5) requires calculating Fib(4) and Fib(3), if you calculate these optimally and add them, you will have calculated Fib(5) optimally.

What are Overlapping Subproblems?
Overlapping subproblems occur when a subproblem is encountered/depended upon multiple times when solving the overall problem. Fibbonacci numbers are pretty much the clearest example of this: calculating Fib(5) requires calculating Fib(4) and Fib(3), and calculating Fib(4) requires calculating Fib(3) and Fib(2), and so on. You can easily see that a subproblem, Fib(3) (as well as Fib(2) and Fib(1), are used more than once.

What is Memoization?
There's a natural observation you can make from optimal subproblems: if you encounter a subproblem more than once, why shouldn't you just save the answer to that subproblem for later? This is in essence memoization. Instead of spending time calculating a sub-problem every time, you exchange that cost for memory space by saving the answer.

Approaches to dynamic programming:
There are generally two approaches to dynamic programming: top-down and bottom-up. Conceptually, top-down starts from the overall problem and works its way through the subproblems; whereas bottom-up starts from the subproblems and builds up to the overall problem. More practically, top-down works from the start of the overall problem and saves the solutions to subproblems once they're encountered; whereas bottom-up calculates the subproblems first then fits them together to solve the overall problem.

Let's go back to the Fibonacci* example. The top down approach to solving Fib(5) will attempt to solve Fib(4) and Fib(3), which will both encounter Fib(1) and Fib(2). So, to get Fib(3), you use the two base cases Fib(1) and Fib(2). You then save Fib(3). For solving Fib(4), you need Fib(3), which you already solved and stored, and a base-case Fib(2).
The bottom-up approach to this would be to start from Fib(1) and calculate upward until you reach Fib(5).

Divide and Conquer:
I'm mentioning divide and conquer because it's easy to understand in and of itself and is often included in many algorithm design classes. Divide and Conquer splits a problem into smaller subproblems repeatedly until it can solve one directly and recombine the solutions. Like Dynamic Programming, D&C problems exhibit optimal substructure; however, unlike Dynamic Programming, they may or may not have overlapping subproblems (they often don't). Often, subproblems themselves exhibit optimal substructure and are often extremely similar. Identifying a D&C algorithm is generally easy, but designing an efficient D&C algorithm can take years worth of skill.

I'm not going to type out an example of a D&C algorithm; rather, just watch the animated visualization for Mergesort and Bubblesort. You should be able to see why Mergesort is D&C given the stark differences between the two.

Backtracking:
Backtracking builds up to a solution by discarding partial candidates until there's zero* or more candidates that are correct. A partial candidate solves part of the problem, however, continuing with this candidate may or may not be valid for the rest of the problem. For example, say you've solved 1 face of a Rubik's cube--this is a partial candidate for solving the whole cube. You might be able to solve the rest of the faces from this point, or the order of turns you made to solve that face might be wrong rendering you unable to solve the cube without undoing (aka backtracking) from the current partial candidate. I like to think of backtracking as an organized guess-and-check, but that somewhat oversimplifies it. Also, backtracking can only be used on problems that can have partial candidates. That is, if you look at the steps to solve a problem, and they branch out at different decisions which may or may not lead to the right answer, you probably have partial candidates.

*Sometimes it's useful or intended to find 0 solutions.

As Mephisto said, 8 Queens is one of the most cited examples of backtracking. Other examples are Sudoku or crossword solving algorithms, solving (not necessarily the most efficiently) the knapsack problem, and more. It's also used to form the internals of some Logic Programming Languages such as Proglog. It may actually be a good idea to play around with some Prolog examples to get the feel for it's backtracking. After a quick look, I like these: http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/search.html
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: if self.isCoder(): post() #Programming Thread
« Reply #4499 on: June 14, 2013, 04:28:53 am »

Actually, the Fibonacci series can be calculated in various other, more efficient ways. If you can use VPA, you can calculate Fib(n) in O(1) operations with the explicit formula, and if you have variable-size integers, you can calculate F(n) := [[Fib(n-1),Fib(n)],[Fib(n),Fib(n+1)]] = F(1)^n in O(log n) operations. Due to the size of those numbers you are operating on these would have a runtime of O(n) (which is the lower bound because F(n) has O(n) digits), but that is still better than O(nē), which is the runtime of the memoized direct recursion.
Logged
Pages: 1 ... 298 299 [300] 301 302 ... 796