I am looking for some new ideas on a project in C++, nothing large, just 300-500 lines of code, can be more.
Short introduction: I'm in my second semester of C++ and finally learning to program. My first semester was basically all syntax and small procedural programming problems, but now I’m learning to write code for people and all that snazz.
The class threw around a couple ideas:
-An evil hangman, where basically the computer changes the word you’re supposed to guess as you get closer to solving it. This is the one I’m leaning towards.
-A basic calculator that does addition, subtraction, multiplication, and division of positive and negative numbers. Kinda a lame one here and not really unique.
-A text based adventure/game. While really cool, just feels like a lot of menial work, especially if I want to include ASCII art to show pictures or something like that.
Does anyone else have a unique idea to work on? I’d like to hear them even if I just decide to work on the evil hangman. It'd be fun to discuss how we’d go about writing some of the ideas.
Hmm, I don't know how to go about that. To give you a perspective of where I'm at, our last class covered some of the library alogrithms c++ provides. The most complex problem we've tackled was storing inputs of strings split into characters in a vector and then manipulating them to rotate/rearrange order and give a framing of asteriks that changed based on length of longest string.
All I can think of is having a function "encrypt" a string by scrambling the letters and then "decrypt" it by unscrambling it.
That is a good idea, the 6502 has enoguht resources, and it is quite simple. As for encrypting, you can implement cesars code, and you could add a function that would additionally scramble the caracters.
well, i can give you a fun project that involves both code, and learning a lot about hardware!
look up a 'full adder'... its what exists inside of a cpu to add and subtract numbers (its one of the main components of the arithmatic logic unit). in c++ you run into limitations with the size of variables. now, the way a full adder works, is if you want to add a 4 bit number, you need 4 "segments"/ an 8 bit number, you need 8 "segments" and so on. so, by virtualizing a full adder into code, you can make an infinite percision library (so you can add and subtract numbers longer than an unsigned long long).
like i said, it will involve research, lots of low level coding (bitwise and, or, posibly bitshifting). i will be happy to help out if you get stumped, but i wont give you answers. this sort of goes along with the "virtual cpu" as well. as if you were to make a virtualized cpu, you would need to make some full adders.
however i will warn you, a virtualized cpu will be beond your scope of programming knowledge right now.
===========
also, with the encryption thing, the simplist form would be an xor encryption.
for(int i = 0; i < file.length(); i++){
output[i] = file[i]^key[i%key.length()];
}
to decrypt, you just run it again with the same key.
I like ztrains adder circuit. I once had a go at that, I got adding, subtracting, and multiplication working (division is harder). Tip: If you need to store large numbers, a vector array works best, or a bitset array.
if you choose to do this, these will help. the picture above is a single "segment" of a full added. A is your first input, B is your second input (they take binary numbers, as in a 1 or 0). for the first segment, ignore cin, its not used... now on the other side, S is the output, and cout is your carry output. it becomes more apparent when you start connecting multiple.
the cout from one goes into the cin on the other. so say we have two numbers, [01] and [10] the first segment will have an input A0:1 and B0:0. the second segment would have an input A1:0 B1:1. if you want to add a 4 bit number, you would need 4 of them, ect.
Implement a tool that uses compression/decompression algorithm for a text file. The best choice is Huffman coding.It is reasonably simple, yet lets your learn about lots of coding constructs that will be necessary for come complex projects.
This project will involve:
1. Basic input/output from/to a file
2. Basic parsing string into character values.
3. Identifying repeating patterns.
4. Creating and working with data structures (at least linked list and a binary tree).
5. Reasonable degree of performance optimization: how fast your code can compress/decompress comparing to benchmark software.
My digital logic class just covered adding and subtracting in binary(or a Radix r) and implementing circuits based on it. Wouldn't this basicaly be a binary calculator? Or rather a way to calculate a set amount of bits with adding, subtracting, etc?
Say I go with two bits, A and B. My output S, if adding, could be: 00, 01, 10, 11. In this case I wouldn't have a carry over?
These are all very unique ideas compared to what my classmates were saying they were going to do, though may be a bit above my head in terms of the programming level I'm at. I'm going to try and fool around with the Full Adder and see what I can come up with.
I wiki'd the Huffman coding. Help me understand the process:
Take a sentence say "the cat runs fast" and break it into individual characters. By identifying repeating patterns are you saying that it should sort based on say alphanumeric order or some other way of ordering? Let's say I had a list of characters from the above sentence. Would I make each character be represented by a number? At that point I guess you'd then split the numbers into a binary tree, but I'm not sure where to go from there.
Ok, yes and no. Essentially you would be making a binary calculator, but by doing so you could add numbers much much larger than a standard int or long.
Further more, to clarify. If you add 01 and 01... The first addition would be 1+1 or '2' so the first S would be 0 and the Cout bit would be 1. Then the next segment would add 1(from the carry) +0+0. So the output for the second S would be 1.
The core idea behind Huffman coding is to assign shortest possible unique binary patter to each unique character in a text. As an example let's take the sentence you have proposes "the cat runs fast". The sentence contains following unique characters: "t h e c a r u n s f space".
Now you assign a unique binary pattern to each character and create a reference table below:
t - 0000, h - 0001, e - 0010, c - 0100, a - 0011, r - 0111, u - 1000, n - 1100, s - 1001, f - 0101, space - 1111
Then you replace every character in the sentence with binary pattern and you will end up with a binary sequence which is in size smaller than the original string of text. It is smaller because you replaced 8 bit ASCII character with 4 bit pattern.
The challenge is how to find the shortest possible unique binary patters to assign to each character. Huffman proposes algorithm that uses character frequencies to calculate binary patterns. So essential steps are:
1. Identify unique characters.
2. Count frequency for each character.
3. Create a binary tree based on frequency information (lower frequency character is a child node of a higher frequency character).
4. Create a reference table by traversing the tree from left-to-right depth first. Assign 0 to left node and 1 to right node.
I found those slides to be a good introduction to Huffman coding: www.cs.nyu.edu/~melamed/courses/102/lectures/huffman.ppt
