tag:blogger.com,1999:blog-33811661062770109952023-11-15T22:21:38.724-08:00Level Up! ProgrammingJasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.comBlogger49125tag:blogger.com,1999:blog-3381166106277010995.post-59267658599596884542010-01-15T15:38:00.000-08:002010-01-15T15:44:16.358-08:00Employement ContinuationIt has been a little over 5 months since I started working here at MokaFive. I would say that the amount of knowledge I have gained over this time is comparable to my college career of 5 years. I would say college was much breadth while working at MokaFive has been some serious depth. I have had some lengthy development time now with GUI (Qt), Windows Vista/7 login screen (Credential Providers), NSIS and WiX installers, and now I am working on expanding our product to have a 64-bit version. Those are just the larger areas of focus as I have done a great deal of smaller tasks as well. In any case, onto the true purpose of this post.<br /><br />That is that this great experience is going to continue! Earlier this week my boss told me that they are planning to make me an offer within the next few weeks that will make me a full time employee. I will no longer be a contractor after nearly 6 months of working here. I am definitely excited about this; however, there is a part of me that does feels some remorse. This is not a game company, which is where I want to be, but it is the place I would want to be if I wasn't in the game industry. Fortunately I have my game project to hold me over for the time being. Speaking of which, I plan to make some posts about pretty soon!Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com2tag:blogger.com,1999:blog-3381166106277010995.post-29045246882056740352009-10-10T08:58:00.000-07:002009-10-10T10:40:22.627-07:00Setup for SuccesAfter nearly a decade of attempting to develop games, I have learned a few valuable lessons. Some of them are extremely basic, yet crucial, for anyone wanting to develop a video game, while some are more technical and for the more serious developer. Today I want to go over one a more technical lesson I have learned fairly recently.<br /><br />From the very beginning, I was always a part of some game group project. Communication was hardly ever a problem; however, collaboration was almost always a problem. There was a continuous mess of making sure that everyone had the up-to-date map file, scripts ...ect. The problem grew exponentially with the size of the group. Anyone who has done a project in a group like this will know exactly what I am talking about. There is a solution to this though!<br /><a href="http://en.wikipedia.org/wiki/Revision_control"><br /><span style="font-weight: bold;">Source Control</span></a> (<a href="http://subversion.tigris.org/">Subversion</a>)<br />Source control is the key. I am sure that many developers have heard of this, but I imagine the more casual developer has not. I highly recommend this for anyone working on a project in a group. Subversion, aka SVN, is the most popular source control and is extremely useful. With it you can not only have a history of your revisions, but also be able to keep everything in one place, on the server, so that way it is easy for everyone to keep their project up-to-date.<br /><br />I would write a tutorial on how to get this setup; however, there are lots of great tutorials out there that you can easily find via a google search. I know setting up a SVN server on Windows can be a little tricky if you don't know what you're doing. Ask if you have any questions and if enough people ask then I can write another post with some details.<br /><br /><a href="http://trac.edgewall.org/"><span style="font-weight: bold;">Trac</span></a><br />Source control is a giant leap in setting up your project for success; however, it is only the start. Next on the list is something that will cover a gambit of potential hurdles. "Trac <span style="text-decoration: underline;"></span>is an enhanced wiki and issue tracking system for software development projects." I am sure everyone has heard of a wiki before. They are immensely useful for documenting anything, even games that are being developed. I know I have seen several game projects that use a forum for keeping track of all of the game's details: storyline, characters, monsters, skills ...ect. With a wiki it is very simple to keep all of this data very organized and easily accessible by anyone on the team.<br /><br />As mentioned, along with the wiki is an "issue tracking system" basically this system allows you to create "tickets" which can represent anything you want. Most commonly this is used for features and bugs. With a ticket created, lets say for a bug, you can assign it to someone and on that ticket have a discussion as well as keep track of the progress. When that bug is closed you can close the ticket. This goes along with Milestones you can create and attach tickets to. Tickets are very nice.<br /><br />Trac can do much more than just this. It can be attached to a subversion repository and you can easily view the history of the changes as well as browse the source. You can easily add in new features and customize your Trac however you want. <a href="http://trac-hacks.org/">Trac Hacks</a> is the best place to quickly to this. It is also easy to create your own since Trac is developed with Python.<br /><br />Setting up Trac is easy thanks to the documentation. Here is a link to the different <a href="http://trac.edgewall.org/wiki/TracInstallPlatforms">platforms</a> and one directly to the <a href="http://trac.edgewall.org/wiki/TracOnWindows">windows</a> since I'm sure most of you are on that.<br /><br /><span style="font-weight: bold;">Conclusion</span><br />I know that this is a lot to take in. I was there not too long ago. Getting Subversion and Trac setup will cost some overhead, especially if you have some difficulties like I did, but the time spent is nothing compared to what you gain.<br /><br />The valuable lesson to take away from this is that having an environment that enables collaboration is not only going to make your life easier but may very well be the deciding factor in the completion of your project.Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com1tag:blogger.com,1999:blog-3381166106277010995.post-27653913396837512302009-10-08T15:11:00.000-07:002009-10-08T17:55:19.970-07:00DaB Gameplay<p>Following up my previous post, I wanted to give readers the general concept behind the gameplay for DaB. Here is an excerpt from the design document.<br /></p><p style="font-style: italic;">The main gameplay is playing a match. This is a 1v1 game of cards. Each player has 4 character cards, collectively known as a party, and a deck of other card types; Aer, Ability, and Item cards. An Aer card is played on a character (this is known as channeling), which enables the character to perform certain abilities. Such as the Aer of Health would give a character the ability to cast healing magic. Item cards are agnostic and consequently can be performed by any character at any time, but are generally weaker than their ability card counterparts. The objective of the game is to KO the opposing player's party.<br /></p> <p style="font-style: italic;"> DaB will follow the "always connected" methodology and require the player to always be connected to the online service that will be provided. Think of this online service as a mini battle.net. Through this service the player can match up on the ladder, with friends or take it solo in either practice (PvE) or story mode. </p> <ul style="font-style: italic;"><li>The story mode would consist of dialog scenes (2D backgrounds with character portraits). No actual character movement, everything is menu driven. </li><li>The online mode is where the major focus lies. With a matchmaking system in place the player is put in a match against another player with similar experience for competitive play. Players will be ranked but there are also unranked matches for playing with friends. </li></ul>Hope you found this interesting. I will continue to provide more information about this project as development goes on.Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-22182111989099562352009-10-07T14:00:00.000-07:002009-10-07T19:26:35.310-07:00The beginningsIt all began nearly 10 years ago. I was all so eager to begin making video games. With the trusty RPG Maker 2k (rm2k) program at my side I felt like I could take on the world! and I could... I just had to set up the scene...<br /><br />Before too long I decided I was going to make an epic RPG. I planned to pull all of the stops with my game. The game was going to have an original mythology with at least a decent amount of history. To go along with the game's story, I designed several original gameplay systems (which I still think would be fun to play). Somewhere along the way I decided that I needed a card game inside my game. I figured why not, FF8 and FF9 were doing it. Also, subconsciously, I had to make sure I overwhelmed myself with as much work as possible - guaranteeing my game's demise.<br /><br />I never completely fleshed out the card game concept, but I had a pretty rough idea of how it was going to work. Basically the player would have some sort of creature card they would have out in play. Then the player could use a card that would represent one of the Gods from the game's mythology. When played, this God card would modify the abilities of the creature. This is all I can really remember from it. I probably came up with more but in my old age I have a hard time remembering the days of my youth.<br /><br />In May 2008 I decided I was going to develop a game. After some long and hard debating (that's what she said), I decided to revive my card game - at least what I could remember of it. In about a month and a half I came up with a good game design and even a very basic <a href="http://www.deusadbellum.com/">website</a>. Things were going great and then came the avalanche of distractions; my wedding, FFXI and final year of college. FFXI was definitely the biggest one of them all. FFXI is to time as a Vampire is to blood. Needless to say, this project was put on the back burner.<br /><br />Earlier this year I resumed game development, but on another game, <a href="http://punipunikingdom.blogspot.com/">Puni Puni Kingdom</a>. After working on the game design for a few months we decided we needed a project that was more scalable. Puni Puni Kingdom required more overhead than we wanted for our first game. We wanted something we could get a basic build out before too long and build on top of it. That's when DaB(the card game) came back into the picture. Consequently we immediately switched projects and began working on DaB. This was all just a little over a month ago.<br /><br />Stay tuned for followups!<br /><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com1tag:blogger.com,1999:blog-3381166106277010995.post-87183169101219680732009-10-01T23:25:00.001-07:002009-10-01T23:38:21.350-07:00Belated updateWell, well, well, it looks like it has been awhile since I posted here. Two months to be precise. Much greatness has happened during this time. I have some catching up to do on here; however, I will take things one step at a time. For now I am going to just go over a few things that have been going on with my internship.<br /><br />As I mentioned in my last post, I have been working at MokaFive for the last two months as an intern on the client team. During this time I have helped implement a few new features as well as help squash some little bugs - oh how they scurried. I have mostly been working with C++ and recently lots of WIN32 API, which I had managed to avoid all of these years. I have worked with so many different things it is not funny: drivers, services, GINA, credential providers, network stuff, cross-platform development, and the list goes on. I have also worked with some great tools like Boost, Doxygen (unfortunately minimal), Win32 (already mentioned...and maybe not so great) ...ect.<br /><br />So far it has been a great experience at MokaFive. I have one month left, November 6th, there as an intern and then we'll see if I want to stay and if they will keep me. I think I know how things will go down but I wont say anything quite yet. Regardless, I am happy that I have been able to work with everyone there thus far.Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-1022249528069932202009-07-29T14:13:00.000-07:002009-08-09T22:47:34.633-07:00Obtained: Job (Internship)As most NPCs know by now, I recently began a new chapter in the story; my story. This chapter focuses on my recently obtained internship at <a href="http://www.mokafive.com/">MokaFive</a>. To be completely honest when I first heard about MokaFive from a good friend that works there I was highly hesitant. My primary concern was that it was not a video game company. Sad news.<br /><br />However, my interest in the position grew as I learned more about the company and the technologies I would be working with. As the interview process proceded I found myself more and more hopeful of being offered the job. This was all weeks ago.<br /><br />Now, a week into the job, I am very pleased to say that it is a great place to work and for several reasons. The people are really friendly and are exceptionally intellegent with a large portion having a masters (or Ph.D.) from Stanford. One of the founders is even a CS professor from Stanford. The overall environment is relaxed and fairly casual but at the same time there is always something that needs to be done and it's seemingly crunch time often.<br /><br />I am not clear on exactly all of the cool technologies that I am going to work with but to give you an idea. Last week I played around with a MSI file using Orca.exe and learned a great deal about the MokaFive product. This next week I am going to learn Python and SCons to help work on the build tools and I am also going to implement a Windows service into the product which is going to undoubted require me to use about five different things that I have never used before. Exciting!<br /><br />The only downside to this internship is that I consequently have much less time. Project Euler problems are going to probably be fairly infrequent for now as well as my blog posts. I do want to continue to write about what I am doing at work as well as a juicy side project that I have yet to mention in this blog. Stay tuned!<br /><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com3tag:blogger.com,1999:blog-3381166106277010995.post-46264852039679062062009-07-29T13:43:00.000-07:002009-07-29T14:12:24.813-07:00Grind Report 30<a href="http://projecteuler.net/index.php?section=problems&id=30">Problem 30</a><br /> <span style="font-style: italic;"><br />Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:</span><div style="font-style: italic;" class="problem_content"> <blockquote>1634 = 1<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 6<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 3<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 4<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /><br />8208 = 8<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 2<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 0<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 8<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /><br />9474 = 9<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 4<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 7<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> + 4<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /></blockquote> <p class="info">As 1 = 1<img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=30" style="display: none;" alt=")" /> is not a sum it is not included.</p> <p>The sum of these numbers is 1634 + 8208 + 9474 = 19316.</p> <p>Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.</p> </div><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />This was a fairly simple problem. My approach was extreme brute force using some recursion. I first consider every possible number with one digit, then two digits and so on. Every number I consider I check to see if the number matches the criteria for being a special number.<br /><br />As I look back at my solution I think that recursion was probably not the best method but I'll let it stay as it is.<br /><br />One important thing to do in this problem is precalculate the digits to the 5th power and store them in an array. This is somewhat obvious but still helps cut down the cost.<br /><pre><br />#include <iostream><br />#include <vector><br />#include <math.h><br /><br />using std::vector;<br />using std::cout;<br /><br />const double N = 5;<br />const int MAXDIGITS = 6;<br /><br />vector<int> nthpow;<br />int solution;<br /><br />void CheckDigitCombinations(int digitCount, int digitTotal, int num, int sumOfDigits);<br /><br />int main()<br />{<br /> //precalculate the nth power of all single digits [0-9]<br /> for (double i = 0; i < 10; ++i)<br /> nthpow.push_back((int)pow(i, N));<br /><br /> for (int digitCount = 1; digitCount <= MAXDIGITS; ++digitCount)<br /> CheckDigitCombinations(digitCount, digitCount, 0, 0);<br /><br /> cout << solution;<br />}<br /><br />void CheckDigitCombinations(int digitCount, int digitTotal, int num, int sumOfDigits)<br />{<br /> <br /> for (int digit = 0; digit < 10; ++digit)<br /> {<br /> int number = num;<br /> int sum = sumOfDigits;<br /> if (digitCount == digitTotal && !digit)<br /> continue;<br /> //add on the extra digit (doesn't change anything for digit #1)<br /> number *= 10;<br /> number += digit;<br /> sum += nthpow[digit];<br /> if (digitCount > 1)<br /> CheckDigitCombinations(digitCount - 1, digitTotal, number, sum);<br /> if (sum == number && sum != 1 && digitCount == 1)<br /> solution += number;<br /> }<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com1tag:blogger.com,1999:blog-3381166106277010995.post-64700873391547854262009-07-29T12:37:00.001-07:002009-07-29T13:15:41.997-07:00Grind Report 29<a href="http://projecteuler.net/index.php?section=problems&id=29">Problem 29</a><br /><span style="font-style: italic;"><br /></span>Consider all integer combinations of a<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>b</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" /> for 2 <= a <= 5 and 2 <= b <= 5:<div style="font-style: italic;" class="problem_content"> <blockquote>2<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>2</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=4, 2<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>3</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=8, 2<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=16, 2<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>5</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=32<br />3<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>2</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=9, 3<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>3</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=27, 3<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=81, 3<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>5</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=243<br />4<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>2</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=16, 4<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>3</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=64, 4<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=256, 4<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>5</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=1024<br />5<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>2</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=25, 5<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>3</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=125, 5<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>4</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=625, 5<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>5</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" />=3125<br /></blockquote> <p>If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:</p> <p style="text-align: center;">4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125</p> <p>How many distinct terms are in the sequence generated by a<img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt="^(" /><sup>b</sup><img src="http://projecteuler.net/index.php?section=problems&id=29" style="display: none;" alt=")" /> for 2 <= a <= 100 and 2 <= b <= 100?</p> </div><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />While attempting this problem I came up with two solutions - but only one actually completely worked... As usual, using C++ runs into some problems here because of the limitation on integer size.<br /><br />My first solution (the semifunctional one) placed the focus on the repeated terms. I used the fact that an exponent can be broken up such as<br /><br />2^32 = (2^4)^8 = 16^8<br /><br />With this it is possible to find which terms are repeated without ever actually calculating the value of a^b. So with this it is easy to simply keep a boolean collection of the different combinations and if one has been encountered before. Such as in the example above when 2^32 (a = 2, b = 32) is run it will see that this is equal to 4^16 and 16^8. Consequently [4][16] and [16][8] both need to be marked as repeats. At the end it is as easy as counting the repeats and subtracting them from the max number of possible terms (99x99).<br /><br />Here is the code but keep in mind that this code does not return the correct answer. While attempting to debug the solution I came across another, much simplier, solution. That I'll discuss after this.<br /><pre><br />#include <iostream><br />#include <vector><br /><br />using std::vector;<br />using std::cout;<br /><br />int PowerWithinMAX(int a, int b);<br /><br />int main()<br />{<br />vector<vector<bool>> encountered;<br /> //create the list of encountered combinations - vector<vector<bool>><br /> for (int i = 0; i < MAX + 1; ++i)<br /> encountered.push_back(vector<bool>(MAX + 1, false));<br /> <br /> int repeatCount = 0;<br /> for (int a = MIN; a <= MAX; ++a)<br /> {<br /> for (int b = MIN; b <= MAX; ++b)<br /> {<br /> //if a^b has previously been encountered before<br /> //then increment repeat count and continue<br /> if (encountered[a][b])<br /> {<br /> ++repeatCount;<br /> continue;<br /> }<br /> //check to see if b can be broken up into pieces<br /> //ie. 2^32 = (2^4)^8 = 16^8<br /> //if so then mark that as being encountered ([16][8])<br /> for (int i = 2; i < b / 2; ++i)<br /> {<br /> //if i is a divisor of b<br /> if (b % i == 0)<br /> {<br /> //check to see if the power is within the max<br /> int c = PowerWithinMAX(a, i);<br /> if (c)<br /> encountered[c][b / i] = true;<br /> }<br /> }<br /> }<br /> }<br /> int ans = 0;<br /> for (int i = 0; i <= MAX; ++i)<br /> for (int j = 0; j <= MAX; ++j)<br /> if (encountered[i][j])<br /> ++ans;<br /> <br /> int answer = (MAX - MIN + 1) * (MAX - MIN + 1) - ans;<br /> cout << answer;<br />}<br /><br />int PowerWithinMAX(int a, int b)<br />{<br /> int solution = 1;<br /> //calculates a^b until solution is > 100<br /> while (solution <= MAX && b > 0)<br /> {<br /> solution *= a;<br /> b--;<br /> }<br /> //if b > 0 (true) then the solution is greater than MAX<br /> if (solution > MAX)<br /> return 0;<br /> else<br /> return solution;<br />}<br /></pre><br />The working method using some more standard library goodness to take care of mostly everything. Every possible combination of a^b is calculated using pow(a, b) and then stored into a set. Once done the set.size() is the unique number of terms. The reason why this works is that when using double it is true that it is not precise enough to give the correct term, but it is precise enough that all terms are unique unless they are actually a repeated term.<br /><br />Because this is so simple the code is pretty small.<br /><pre><br />#include <iostream><br />#include <set><br />#include <math.h><br /><br />using std::set;<br />using std::cout;<br /><br />const int MIN = 2;<br />const int MAX = 100;<br /><br />int main()<br />{<br /> set<double> answer;<br /> for (double a = MIN; a <= MAX; ++a)<br /> for (double b = MIN; b <= MAX; ++b)<br /> answer.insert(pow(a, b));<br /> cout << answer.size();<br />}<br /></pre><br />I will probably go back and fix up the first solution and get it working eventually. I am curious what the problem with the algorithm is. In the meantime I'll continue to move onward.<br /><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-64504654440640220562009-07-27T17:21:00.000-07:002009-07-27T18:28:13.609-07:00Grind Report 28<a href="http://projecteuler.net/index.php?section=problems&id=28">Problem 28</a><br /><br /> Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:<div style="font-style: italic;" class="problem_content"> <p style="text-align: center; font-family: courier new;"><span style="color: rgb(255, 0, 0); font-family: courier new;">21</span> 22 23 24 <span style="color: rgb(255, 0, 0); font-family: courier new;">25</span><br />20 <span style="color: rgb(255, 0, 0); font-family: courier new;">7</span> 8 <span style="color: rgb(255, 0, 0); font-family: courier new;">9</span> 10<br />19 6 <span style="color: rgb(255, 0, 0); font-family: courier new;">1</span> 2 11<br />18 <span style="color: rgb(255, 0, 0); font-family: courier new;">5</span> 4 <span style="color: rgb(255, 0, 0); font-family: courier new;">3</span> 12<br /><span style="color: rgb(255, 0, 0); font-family: courier new;">17</span> 16 15 14 <span style="color: rgb(255, 0, 0); font-family: courier new;">13</span></p> <p>It can be verified that the sum of both diagonals is 101.</p> <p>What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />This is by far my most compact solution so far and like any compact algorithm, there was a decent amount of thought that went into it. So here is my attempt to explain everything...<br /><br />One of the first things I did was write out the corners by themselves as well as expand the grid to be 9x9 so I could get a better view of what exactly was going on. After drawing them out and staring at them I saw that the way to get the corners is to just add multiples of two to the previous number...<br /><br /><br />3 5 7 9 13 17 21 25... //corner value<br />2 2 2 2 4 4 4 4 6 6 6 6 8 8 8 8 //amount to add to the previous corner<br /><br />That's not exactly a beautiful example but I think it will suffice. With just this it would be very easy to write a program to do this; however, I took it a step further. Instead of considering each corner, I figured why not just consider the average of the corners and multiply that by 4. It makes sense if you think about it, but it actually turns out that the average of the corners is all of the numbers directly to the left of 1 (and including 1). In the example you can see 3 averages: 1, 6, 19. As I just said, to get the answer we just need to sum of the averages and multiply by 4.<br /><br />One way to get to each average is to follow the bottom left diagonal and move <span style="font-style: italic;">n</span> numbers up, where <span style="font-style: italic;">n</span> is the number of spirals moved over from the center. And now the question shifts to how to find the corners in the bottom left diagonal. Using the previously gathered information I derived that at any given spiral <span style="font-style: italic;">n</span> the value of the bottom left corner is<span style="font-style: italic;"><br /><br />n</span> * 4 + ((8 * (<span style="font-style: italic;">n</span> - 1) * <span style="font-style: italic;">n</span>) / 2) + 1<br /><br /><span style="font-style: italic;">n</span> * 2 * 2 //is that for the given spiral we need to find the 2nd corner<br />((8 * (<span style="font-style: italic;">n</span> - 1) * <span style="font-style: italic;">n</span>) / 2) //this sums up all of the previous corners<br />1 //because we start with the center 1<br /><br />This is a little complex and I could go into it more but I doubt it is of that much interest. Here is my code solution.<br /><pre><br />#include <iostream><br /><br />using std::cout;<br /><br />const int SPIRALSIZE = 1001;<br /><br />int main()<br />{<br /> long long average = 1;<br /> for (int i = 1; i * 2 + 1 >= 1001; ++i)<br /> average += (i * 4 + ((8 * (i - 1) * i) / 2) + i + 1);<br /> cout << average * 4;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-9905107659330829312009-07-26T19:43:00.000-07:002009-07-26T21:34:44.859-07:00Grind Report 27<a href="http://projecteuler.net/index.php?section=problems&id=27">Problem 27</a><br /><span style="font-style: italic;"><br /></span>Euler published the remarkable quadratic formula:<div style="font-style: italic;" class="problem_content"> <p style="text-align: center;">n² + n + 41</p> <p>It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40<img src="http://projecteuler.net/index.php?section=problems&id=27" style="display: none;" alt="^(" /><sup>2</sup><img src="http://projecteuler.net/index.php?section=problems&id=27" style="display: none;" alt=")" /> + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.</p> <p>Using computers, the incredible formula n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.</p> <p>Considering quadratics of the form:</p> <blockquote> n² + an + b, where |a| < 1000 and |b| < 1000<br /><br /><div class="info" style="text-align: right;">where |n| is the modulus/absolute value of n<br />e.g. |11| = 11 and |-4| = 4</div> </blockquote> <p>Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />After reading the question a few times through to make sure I understood it completely I caught onto a subtle hint. In both examples a and b are prime numbers. After thinking about it a little it became obvious that this is necessary to produce a string of prime numbers with n. Such as if b is not prime then n=0 automatically fails. This also concludes that b must be positive.<br /><br />With this and reusing my prime code I went ahead and solve this problem. I did run into one problem that once I figured it out I realized it was right there in my face the whole time. This was that I am considering all a and b that index the prime numbers up to 1000.<br /><br /><span style="font-style: italic;">for (int a = 0; primes[a] < 1000; ++a)</span><br /><br />I thought that this was clever when I wrote it. But apparently it was too clever for me because later on I completely forgot I was using a and b as an index to the prime numbers. Consequently I wrote the quadratic equation like this...<br /><br /><span style="font-style: italic;">n * n + a * n + b</span><br /><br />instead of indexing the primes array like I was suppose to.<br /><br /><span style="font-style: italic;">n * n + primes[a] * n + primes[b]</span><br /><br />I learned my lesson here. Not to mention that this mistake was a little humbling, I have not made one of these for awhile and so this was much needed. Here is the code. (the IsPrime function is not optimal)<br /><pre><br />#include <iostream><br />using std::cout;<br /><br />const int MAX = 1000;<br />const int PRIMECOUNT = 200;<br />int primes[PRIMECOUNT];<br /><br />bool IsPrime(long number);<br />void populatePrimes();<br /><br />int main()<br />{<br /> populatePrimes();<br /><br /> int answer = 0;<br /> int highest = 0;<br /> //consider all prime numbers up to 1000 for a<br /> for (int a = 0; primes[a] < MAX; ++a)<br /> {<br /> //also consider the negative version<br /> for (int i = -1; i <= 1; i += 2)<br /> {<br /> int primeA = primes[a] * i;<br /> //consider all prime numbers up to b<br /> for (int b = 3; primes[b] < MAX; ++b)<br /> {<br /> int quadratic;<br /> int n = 0;<br /> //continue calculating the quadratic and checking to see if it is prime<br /> //until it is no longer prime<br /> do<br /> {<br /> quadratic = n * n + primeA * n + primes[b];<br /> ++n;<br /> } while (IsPrime(quadratic));<br /> //check to see if the highest n has been reached<br /> if (n > highest)<br /> {<br /> highest = n;<br /> answer = primeA * primes[b];<br /> }<br /> }<br /> }<br /> }<br /> cout << answer;<br />}<br /><br />bool IsPrime(long number)<br />{<br /> for (int i = 0; i < PRIMECOUNT; ++i)<br /> {<br /> if (primes[i] == number)<br /> return true;<br /> if (primes[i] > number)<br /> return false;<br /> }<br /> return false;<br />}<br /><br />void populatePrimes()<br />{<br /> primes[0] = 2;<br /> primes[PRIMECOUNT - 1] = -1;<br /> int number = 3;<br /> int foundCount = 1;<br /> bool isPrime = false;<br /> while (primes[PRIMECOUNT - 1] == -1)<br /> {<br /> //assume a number is prime until proven guilty<br /> isPrime = true;<br /> for (int i = 0; i < foundCount; ++i)<br /> {<br /> //break if the number is divisible by an already found prime number (guilty)<br /> if (number % primes[i] == 0)<br /> {<br /> isPrime = false;<br /> break;<br /> }<br /> //check to see if the current prime number squred is greater than or equal to the provided number<br /> //if so then break. This means the number is a prime.<br /> if (primes[i] * primes[i] >= number)<br /> break;<br /> }<br /> //add the prime number<br /> if (isPrime)<br /> primes[foundCount++] = number;<br /> //increment the number by 2 (to stay odd)<br /> number += 2;<br /> }<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-11480877913574374572009-07-26T02:34:00.000-07:002009-07-26T13:19:07.029-07:00Grind Report 26<a href="http://projecteuler.net/index.php?section=problems&id=26">Problem 26</a><br /><br /><span style="font-style: italic;">A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:</span><div style="font-style: italic;" class="problem_content"> <blockquote> <table> <tbody><tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>2</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.5</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>3</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.(3)</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>4</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.25</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>5</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.2</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>6</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.1(6)</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>7</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.(142857)</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>8</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.125</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>9</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.(1)</td> </tr> <tr> <td><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>10</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /></td><td>= </td><td>0.1</td> </tr> </tbody></table> </blockquote> <p>Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that <img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(" /><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>7</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /> has a 6-digit recurring cycle.</p> <p>Find the value of d < src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^("><sup>1</sup><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" />/<img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="_(" /><sub>d</sub><img src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt=")" /> contains the longest recurring cycle in its decimal fraction part.</p> </div><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />Ready to revisit 4th grade? This problem is a little tricky because of one thing - floating point precession. The precision required is far beyond our float or double we have available in C++ and so something more is required.<br /><p><br />This "more" is actually from 4th grade. Do you remember long hand division? If not you can refresh your memory at the <a href="http://en.wikipedia.org/wiki/Long_division">Long Division Wikipedia page</a> - don't worry I wont tell anyone ;).<br /><br />This is a very basic example; however, it shows something very important. That is if the remainder is the same as a previous encountered remainder then the number has a recurring cycle. Also, something not shown here, is the fact that if the remainder is 0 then the number does not have a recurring cycle. By just using these two pieces of knowledge this problem becomes fairly simple. All that is needed is to implement long division and check for if 0 or a previous remainder is encountered (this method requires storing the previous remainders).<br /><br />Here is an implementation that solves the problem very quickly.<br /></p><pre><br />#include <iostream><br /><br />using std::cout;<br /><br />const int MAX = 1000;<br /><br />int main()<br />{<br /> int answer;<br /> int highest = 0;<br /> for (int i = 1; i < MAX; ++i)<br /> {<br /> int count = 0;<br /> int remainder = 1;<br /> bool remainders[MAX] = {false};<br /> while (remainder != 0)<br /> {<br /> //keep dropping 0s to the remainder until i can divide into it at least once<br /> while (!(int)(remainder / i))<br /> remainder *= 10;<br /> //get the new remainder<br /> remainder %= i;<br /><br /> //found a cycle<br /> if (remainders[remainder])<br /> break;<br /> //store the remainder<br /> remainders[remainder] = true;<br /> count++;<br /> }<br /> //if there was a cycle and the count is greater than the previous highest<br /> //then set the count as the new highest<br /> if (remainder && count > highest)<br /> {<br /> highest = count;<br /> answer = i;<br /> }<br /> }<br /> cout << answer << ": " << highest;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-18493541066588140472009-07-25T01:06:00.000-07:002009-07-25T01:34:11.166-07:00Grind Report 25<a href="http://projecteuler.net/index.php?section=problems&id=25">Problem 25</a><br /><span style="font-style: italic;"><br /></span>The Fibonacci sequence is defined by the recurrence relation:<div style="font-style: italic;" class="problem_content"> <blockquote>F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>n</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>n-1</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> + F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>n-2</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" />, where F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>1</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 1 and F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>2</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 1.</blockquote> <p>Hence the first 12 terms will be:</p> <blockquote>F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>1</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 1<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>2</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 1<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>3</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 2<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>4</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 3<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>5</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 5<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>6</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 8<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>7</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 13<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>8</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 21<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>9</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 34<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>10</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 55<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>11</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 89<br />F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>12</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" /> = 144</blockquote> <p>The 12th term, F<img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt="_(" /><sub>12</sub><img src="http://projecteuler.net/index.php?section=problems&id=25" style="display: none;" alt=")" />, is the first term to contain three digits.</p> <p>What is the first term in the Fibonacci sequence to contain 1000 digits?</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />1000 digits, eh? That's a lot of digits. And once again there are two ways to solve this. Brute force or some method paved with gold. Amazingly I went with brute force this time since it was the one that required programming, but I'll go over the gold way as well.<br /><br />My brute force method is kind of cheating but it is smart cheating? This raises the moral issue of whether cheating is acceptable as long as it is done in an intelligent manner. Anyways, the way I cheated is that while calculating Fibonacci numbers to find the first one with 1000 digits, instead of keeping all of the digits, which would be impossible with built in types, I just would cut off the less significant digits when the number got to a certain size and keep count of how many digits I cut off. This method worked like a charm and the algorithm is very fast! :)<br /><br />The golden method is real gold! If you ever took calculus with Mr. Penner at Red Bluff High School, then you would know what the golden ratio is - (1 + sqrt(5)) / 2. You would also know that F<sub>n</sub>/F<sub>n-1</sub> converges to this golden ratio, which is known as phi. Taking this golden ratio and using it with the fact that if you take the ceil(log<sub>10</sub>(n)) then you will actually the number of digits that number contains, we can solve this problem by hand (preferably with a calculator in it). This looks something like...<br /><br />ceil(((999 + log<sub>10</sub>(sqrt(5)))/log<sub>10</sub>((1 + sqrt(5))/2))<br /><br />Yay! Math!<br /><br />Oh, yeah. Here is my brute force goodness.<br /><pre><br />#include <iostream><br />#include <math.h><br /><br />int main()<br />{<br /> long long f = 1;<br /> long long fn = 1;<br /> int count = 0;<br /> int i = 2;<br /> while (count + (int)ceil(log10((long double)fn)) < 1000)<br /> {<br /> long long temp = fn;<br /> fn += f;<br /> f = temp;<br /> if (fn > 1000000000000)<br /> {<br /> fn /= 10;<br /> f /= 10;<br /> ++count;<br /> }<br /> ++i;<br /> }<br /> std::cout << i;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-74700115977241878772009-07-24T00:03:00.001-07:002009-07-24T00:29:22.767-07:00Project Euler Level up!Even though I only have 24 reports, I actually have done another problem which sets me at 25 problems completed. This is great! When I completed the problem I was presented with this message.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhyZA-pa6_Fewqx65qpjHuk9Ha2mTABT9XN46x5KyorSzoIIU4Wl6TVtCJGuatlSFpROeoAQiz000kq9fW1WrjAy11FJzJR3PE-PUB1NCoP_i_wsnPCBgN5Na1ZJ1Rs8PBWhyMnyQGimkU/s1600-h/euler-levelup1.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 400px; height: 101px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhyZA-pa6_Fewqx65qpjHuk9Ha2mTABT9XN46x5KyorSzoIIU4Wl6TVtCJGuatlSFpROeoAQiz000kq9fW1WrjAy11FJzJR3PE-PUB1NCoP_i_wsnPCBgN5Na1ZJ1Rs8PBWhyMnyQGimkU/s400/euler-levelup1.png" alt="" id="BLOGGER_PHOTO_ID_5361920849634022002" border="0" /></a><br />I was very excited to see this. I'm above 79.4% - that's pretty awesome. When I went to look at my profile I was very happy to be presented with this.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5tAiNAA9ntiwNWhASQKBEVGECq66Y83FhFjBeAH77kmxJM9xtL4zDkae_FMjwZCnjn137ZuJN0zDIPxcWnNs94FuWNYKTLMNwXdoJDNscXbzS5NgCPi2ClTXWFyDVnDvbfKsIxzTdpSIo/s1600-h/euler-level1.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 400px; height: 89px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5tAiNAA9ntiwNWhASQKBEVGECq66Y83FhFjBeAH77kmxJM9xtL4zDkae_FMjwZCnjn137ZuJN0zDIPxcWnNs94FuWNYKTLMNwXdoJDNscXbzS5NgCPi2ClTXWFyDVnDvbfKsIxzTdpSIo/s400/euler-level1.png" alt="" id="BLOGGER_PHOTO_ID_5361921245780919090" border="0" /></a>Yeah, I bet you didn't know they were handing out TRIANGLES! but they aren't just handing them out to anyone. One day I hope to become <a href="http://projecteuler.net/index.php?section=scores">spherical</a> - this is my dream; my goal in life.<br /><br />Anyways, I thought I'd take a moment and reflect back on the past 25 problems and see how this project Euler is treating me and everything.<br /><br />My original primary reason to do these problems was that I wanted to become a better C++ programmer. After the first 10 problems I realized that was an unreasonable goal given the means. These problems are really more intellectually challenging and are working my mind several times harder than it is working my C++ skills. However, I do not want to discredit what I have learned. I have become more familiar with the standard library and more comfortable with the syntax.<br /><br />One thing these problems are not requiring is work with classes. But, I am considering putting together a namespace and classes (where applicable) of the methods that I find myself commonly using in these problems.<br /><br />Overall I am enjoying working on these problems. I have always found interest in any intellectual challenge and these are a good way to work that. One thing I am unhappy about is that with all of these reports this blog has become much more serious and intellectual than I originally wanted. If anyone has any suggestions on how to mix things up then let me know! I don't want to lose all 7 of my readers!<br /><br />Level Up!<br />Jasson grows to <span style="font-weight: bold;">Level 10</span> Programmer.<br />Jasson's STR (in fingers) increases by 3.<br />Jasson's INT increases by 99.<br />Jasson learns skill "Basic C++".<br /><br />Alright!<br /><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-43901258295749750832009-07-23T23:53:00.000-07:002009-07-24T00:02:40.774-07:00Grind Report 24Problem 24<br /><span style="font-style: italic;"><br /></span>A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:<div class="problem_content"> <p style="text-align: center; font-style: italic;">012 021 102 120 201 210</p> <p style="font-style: italic;">What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?</p><p></p></div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />As usual, this could be solved using a brute force method that would calculate each permutation until the targeted permutation was reached. But since the target is 1 million, that would be a very sad method. Thus, once again, I set out to come up with an algorithm that could calculate any target permutation.<br /><br />The first and most important thing to know about permutations is that given a set of n characters there are exactly n! (factorial) possible combination. Such as in the example in the question, there are 3 characters and there are 3! = 3 * 2 * 1 = 6 combinations. Since 3 characters can only represent 6 different combinations then if a target permutation such as 10 is requested you know that 4 characters are required, 4! = 24 possible permutations, and consequently you also know that the first digit has to be changed to be able to represent this target permutation.<br /><br />The 10<sup>th</sup> permutation of 0, 1, 2, and 3 is 1230. As you might have noticed by now, the most significant character that needs to be changed is the first one (moving right to left) that has n! / Target >= 1. In our example we have...<br /><br />1! / 10 = .1<br />2! / 10 = .2<br />3! / 10 = .6<br />4! / 10 = 2.4<br /><br />So we can see that there are at least 4 characters required to represent this target permutation. Furthermore, using a similar method we can even know which number belongs in the place of the most significant place. This is done by taking the Target / (n – 1)!. Once again in our example we have...<br /><br />10 / (4 – 1)! = 10 / 6 = 1 r 4<br /><br />This actually tells us two things. The first thing is that we need to swap the first and second most significant numbers. This is the most significant number and 1 place to the right, which would give us 1023 given that we start with 0123. If this number is larger than 1 it is important to continue to swap the numbers so that besides the place being changed, n, the other numbers need to stay in the lowest lexicographical order possible. Such as if 2 was the number we'd want 2013 and 3 we would want 3012.<br /><br />The other thing we can pull from this is if we look at the remainder. If we take this remainder, set it as the new target permutation and then decrement n by 1 we can repeat this and once you're done you'll have the original target permutation. Pretty cool huh?<br /><br />It took me awhile to figure this out but once I understood how the algorithm would work it didn't take long to implement it. Here is my solution. I added comments to help with reading it. :)<br /><pre><br />#include <iostream><br /><br />using std::cout;<br /><br />const int TARGET = 1000000;<br />const int CHARCOUNT = 10;<br /><br />void swap(char &a, char &b);<br />long factorial(int number);<br /><br />int main()<br />{<br /> //setup array to include 0, 1, 2, 3, 4, 5, 6, 7, 8, 9<br /> char permutation[CHARCOUNT + 1];<br /> for (int i = 0; i < CHARCOUNT; ++i)<br /> permutation[i + 1] = '0' + i;<br /><br /> //find out how many characters are required to represent the target<br /> //and store that place so we know where to start<br /> int place;<br /> for (place = 1; place < CHARCOUNT + 1; ++place)<br /> {<br /> if ((int)(factorial(place) / TARGET))<br /> break;<br /> }<br /> //flip the place around to work with the array indexing<br /> place = CHARCOUNT - place + 1;<br /> //set the current target to the original target<br /> int current = TARGET;<br /> //this is the main algorithm<br /> for (;place < CHARCOUNT; ++place)<br /> {<br /> //calculate the factorial<br /> long fact = factorial(CHARCOUNT - place);<br /> //determine how many places to the right this needs to go<br /> int index = (current - 1) / fact;<br /> //store it for later use<br /> int count = index;<br /> //this goes over index number of places and continues to swap the numbers<br /> //until it gets to the current place<br /> while (index > 0)<br /> {<br /> swap(permutation[place + index], permutation[place + index - 1]);<br /> --index;<br /> }<br /> //set the new target for the next iteration of the algorithm<br /> current -= fact * count;<br /> }<br /> //output solution<br /> for (int i = 1; i <= CHARCOUNT; ++i)<br /> cout << permutation[i];<br />}<br /><br />//swaps two char<br />void swap(char &a, char &b)<br />{<br /> char temp = a;<br /> a = b;<br /> b = temp;<br />}<br /><br />//returns the factorial of the number (recursive)<br />inline long factorial(int number)<br />{<br /> return (number == 1 ? 1 : number * factorial(number - 1));<br />}<br /></pre><br />Oh yeah, I almost forgot to mention. This is fast. Much faster than calculating the 999,999 permutations before it. Also <span style="font-style: italic;">I believe</span> this can calculate any permutation target with any characters, not just numbers - only the top bit of the code needs to be changed. ^^<br /><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-63247165185286678402009-07-21T23:21:00.000-07:002009-07-22T00:15:38.886-07:00Grind Report 23<a href="http://projecteuler.net/index.php?section=problems&id=23">Problem 23</a><br /><br /><div style="font-style: italic;" class="problem_content"> <p>A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.</p> <p>A number <var>n</var> is called deficient if the sum of its proper divisors is less than <var>n</var> and it is called abundant if this sum exceeds <var>n</var>.</p> <!-- <p>A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.</p> --> <p>As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.</p> <p>Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />When I first came to this problem I was not sure what approach I was going to use to solve it. I knew that I could use the sumofproperdivisors method from my <a href="http://levelupprogramming.blogspot.com/2009/07/grind-report-21.html">problem 21 solution</a> to check to see if a number is abundant or not. The real question was how would I know if a number could (and not) be expressed as the sum of two abundant numbers?<br /><br />There are two ways to go about solving this problem.<br /><ol><li>Check every number and see if it can be written as the sum of two abundant numbers. (obvious approach).</li><li>For every abundant number, go though all abundant numbers and mark the sum of the two as a number that can be written as the sum of two abundant numbers.</li></ol>My first attempt was the first way. I quickly realized that this was a huge waste of time because the abundant numbers would have to be checked several times for each number instead of only once per number. Needless to say, I moved to the second approach immediately after this discovery.<br /><br />In addition to a list of abundant numbers, the second approach requires a list of all of the considered numbers. Once I to this point things became much clearer.<br /><br />One issue I ran into while doing this problem is that my solution was kind of slow. It took about 20-30 seconds to find the answer, which is much longer than any of my previous solutions. After some analysis I realized that my implementation was somewhat flawed. My collection of abundant numbers was a map, which when I started made some sense, but my final solution it was completely unnecessary. When I changed it from a map to a vector it went down to about 4-5 seconds to find the answer. Much better :)<br /><br />Here is my solution. I changed the sumofproperdivisors method a little and so it should be slightly faster now.<br /><pre><br />#include <iostream><br />#include <vector><br /><br />using std::vector;<br />using std::cout;<br /><br />const int MAX = 28123;<br /><br />int sumofproperdivisors(int n);<br /><br />int main()<br />{<br /> bool numbers[MAX + 1];<br /> vector<int> abundants;<br /> for (int i = 1; i <= MAX; ++i)<br /> {<br /> //check to see if the number is abundant<br /> if (sumofproperdivisors(i) > i)<br /> {<br /> //add to the list of abundant numbers<br /> abundants.push_back(i);<br /> //go through all abundant numbers and mark off the sum of the two<br /> for (int j = 0; j < abundants.size(); ++j)<br /> {<br /> //break if the sum of the abundant numbers is larger than the MAX<br /> if (i + abundants[j] > MAX)<br /> break;<br /> numbers[i + abundants[j]] = false;<br /> }<br /> }<br /> }<br /><br /> //go through all of the numbers and add up the ones that<br /> //cannot be expressed as the sum of two abundant numbers<br /> long answer = 0;<br /> for (int i = 1; i <= MAX; ++i)<br /> if (numbers[i])<br /> answer += i;<br /> cout << answer;<br />}<br /><br />int sumofproperdivisors(int n)<br />{<br /> int sum = 0;<br /> //determine how much to increment by each<br /> int increment = n % 2 + 1;<br /> //iterate through all numbers that are less than the sqrt(n)<br /> //since i * i is the largest the smallest of the two can be<br /> for (int i = 1; i * i <= n; i += increment)<br /> {<br /> //if n is evenly divisible then add i and the other number (n / i)<br /> //so that i * (n / i) = n<br /> if (!(n % i))<br /> {<br /> sum += i;<br /> //add the larger divisor unless i is the square of n (avoid duplication)<br /> if (i * i != n)<br /> sum += n / i;<br /> }<br /> }<br /> //remove n since it was added when i == 1<br /> sum -= n;<br /> return sum;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-66543192845621923012009-07-20T23:50:00.000-07:002009-07-22T00:16:07.960-07:00Grind Report 22<a href="http://projecteuler.net/index.php?section=problems&id=22">Problem 22</a><br /><span style="font-style: italic;"><br /></span>Using <a href="http://projecteuler.net/project/names.txt">names.txt</a> (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.<div style="font-style: italic;" class="problem_content"> <p>For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 x 53 = 49714.</p> <p>What is the total of all the name scores in the file?</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />This was a somewhat longer problem. It was for me at least. Starting off, it is obvious that the names need to be extracted from the .txt file, sorted and then calculate the name scores.<br /><br /><span style="font-weight: bold;">Extraction:</span><br />I decided I would use a regex, even though it was kind of overkill for this problem. I considered using Boost regex but I ended up going with the extension of the standard library, which is known as tr1. Which this I was able to define a regex ("[A-Z]+") and then search through the names for all matches, which took the names out of the quotes and commas.<br /><br /><span style="font-weight: bold;">Sorting:</span><br />I wanted to have a fast algorithm since 5000+ elements is kind of a lot. Having something like O(n^2) would be horrible and so I decided to go with the popular Quicksort algorithm which can be at best O(log(n)). So I went ahead and implemented that with some help from the wikipedia page for the <a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort algorithm</a>.<br /><br /><span style="font-weight: bold;">Scoring:</span><br />This part was actually the easiest. It was really straight forward and quick to implement.<br /><br />The real time sucker was getting regex to work. First I had to download and install the extension to Visual Studio 2008 known as VS2008 Feature Pack. Then I had to work with the very limited documentation to figure out how to actually search through a string with a regular expression and retrieve the matched values. Because this has several components to it, I think this is my longest solution thus far. Here it is.<br /><pre><br />#include <iostream><br />#include <fstream><br />#include <string><br />#include <vector><br />#include <regex><br /><br />using std::tr1::smatch;<br />using std::tr1::regex;<br />using std::string;<br />using std::vector;<br />using std::ifstream;<br />using std::cout;<br /><br />void Swap(string& a, string& b);<br />void QuickSort(vector<tring>& list, int startIndex, int endIndex);<br />int Partition(vector<string>& list, int startIndex, int endIndex, int pivotIndex);<br />int CalcNameScore(string name, int index);<br /><br />int main()<br />{<br />//obtains the string of names<br />string line;<br />ifstream file ("names.txt");<br />if (file.is_open())<br /> std::getline(file, line);<br /><br />//setup the regex<br />smatch match;<br />const regex ex("[A-Z]+");<br /><br />//extract the names from the string<br />string::const_iterator first = line.begin();<br />string::const_iterator last = line.end();<br />vector<string> list;<br />while (std::tr1::regex_search(first, last, match, ex))<br />{<br /> list.push_back(match[0]);<br /> first += match.position() + match.length();<br />}<br /><br />//sort the list using Quick Sort<br />QuickSort(list, 0, list.size() - 1);<br /><br />//calculate the total name score<br />int totalNameScore = 0;<br />for (int i = 0; i < list.size(); ++i)<br /> totalNameScore += CalcNameScore(list[i], i);<br />cout << totalNameScore;<br />}<br /><br />//simply swaps two values<br />inline void swap(string& a, string& b)<br />{<br />string temp = a;<br />a = b;<br />b = temp;<br />}<br /><br />void QuickSort(vector<string>& list, int startIndex, int endIndex)<br />{<br />if (startIndex < endIndex)<br />{<br /> int pivotIndex = startIndex;<br /> pivotIndex = Partition(list, startIndex, endIndex, pivotIndex);<br /> QuickSort(list, startIndex, pivotIndex - 1);<br /> QuickSort(list, pivotIndex + 1, endIndex);<br />}<br />}<br /><br />int Partition(vector<string>& list, int startIndex, int endIndex, int pivotIndex)<br />{<br />string pivotValue = list[pivotIndex];<br />swap(list[pivotIndex], list[endIndex]);<br />int storeIndex = startIndex;<br />for (int i = startIndex; i < endIndex; ++i)<br />{<br /> if (pivotValue.compare(list[i]) > 0)<br /> swap(list[i], list[storeIndex++]);<br />}<br />swap(list[storeIndex], list[endIndex]);<br />return storeIndex;<br />}<br /><br /><br />int CalcNameScore(string name, int index)<br />{<br />int score = 0;<br />//add up the value from each character in the name<br />for (int i = 0; i < name.length(); ++i)<br /> score += name[i] - 'A' + 1;<br />//returns the score of the name<br />//index is 0 based so it is necessary to increase by one<br />return score * (index + 1);<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-13475926590092138012009-07-18T14:23:00.000-07:002009-07-18T14:39:01.129-07:00Grind Report 21<a href="http://projecteuler.net/index.php?section=problems&id=21">Problem 21</a><br /><span style="font-style: italic;"><br /></span>Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).<br /><div style="font-style: italic;" class="problem_content"><p> If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.</p> <p>For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.</p> <p>Evaluate the sum of all the amicable numbers under 10000.</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*<br /><br /></span>By now I am pretty comfortable working with divisors and prime numbers. The proper divisors are just the divisors minus the number itself. So basically all we had to do was find and add up all of the divisors and then subtract the number to get the proper divisors. Easy enough!<br /><br />There are two way to speed up this algorithm of obtaining the sum of the proper divisors. One we already have encountered a few times, which is that the highest value we need to look at is the square of the number. This is because all divisors numbers greater than the square of the number can be determined using the lower divisors, which is simply the number divided by the lower divisor.<br /><br />The other trick is that if the number is odd then all divisors must be odd, therefor only odd numbers need to be considered. This little trick actually cuts off 1/4 of the algorithm and is really easy to implement. This was a quick and simple solution.<br /><pre><br />#include <iostream><br />#include <math.h><br /><br />using std::cout;<br /><br />const int TARGET = 10000;<br /><br />int sumofproperdivisors(int n)<br />{<br /> int sum = 0;<br /> //calculate the square of n<br /> int square = sqrt((float)n);<br /> //determine how much to increment by each<br /> int increment = n % 2 + 1;<br /> //iterate through all numbers that are less than the sqrt(n)<br /> //since n * n is the largest the smallest of the two can be<br /> for (int i = 1; i <= square; i += increment)<br /> {<br /> //if n is evenly divisible then add i and the other number (n / i)<br /> //so that i * (n / i) = n<br /> if (!(n % i))<br /> {<br /> sum += i;<br /> //add the larger divisor unless the i == n / i (which would mean i == square)<br /> if (i != square)<br /> sum += n / i;<br /> }<br /> }<br /> //remove n since it was added when i == 1<br /> sum -= n;<br /> return sum;<br />}<br /><br />int main()<br />{<br /> int amicablesum = 0;<br /> for (int i = 4; i < TARGET; ++i)<br /> {<br /> int b = sumofproperdivisors(i);<br /> //determine if it is a new amicable pair<br /> //standard check plus since i != b this means that every pair<br /> //will be encountered twice so simply only accept one of them (aka i > b)<br /> if (sumofproperdivisors(b) == i && i != b && i > b)<br /> amicablesum += i + b; //add the pair to the total sum<br /> }<br /> cout << amicablesum;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-43952936752289108542009-07-18T01:01:00.000-07:002009-07-18T01:12:23.184-07:00Grind Report 20<a href="http://projecteuler.net/index.php?section=problems&id=20">Problem 20</a><br /><br /><div style="font-style: italic;" class="problem_content"> <p>n! means n x (n - 1) x ... x 3 x 2 x 1</p> <p>Find the sum of the digits in the number 100!</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />This problem was giving me some issues for awhile. I think this is because my planned solution was similar to <a href="http://levelupprogramming.blogspot.com/2009/07/grind-report-16.html">my solution for Problem 16</a>. However, there are some changes that needed to be made to accommodate multiplication of larger numbers. I was going about this the long hand way and then stumbled upon <a href="http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Example">this</a>.<br /><br />The example on that page is fairly similar to my approach to problem 16. This example hinted to me the fact that I could allow my carry to be greater than 10. With this hint I was able to quickly implement it into my solution and get the correct answer. Here is the code, which is for the most part the same as problem 16.<br /><pre><br />#include <iostream><br /><br />using std::cout;<br />using std::endl;<br /><br />const int FACTORIAL = 100;<br /><br />int main()<br />{<br /> int number[200];<br /><br /> number[0] = 1;<br /> int size = 1;<br /> int remainder = 0;<br /><br /> for (int i = 1; i <= FACTORIAL; ++i)<br /> {<br /> int carry = 0;<br /> //go through all of the digits<br /> for (int j = 0; j < size; ++j)<br /> {<br /> //the new value of this digit<br /> int digit = number[j] * i + carry;<br /> //calculate the new remainder<br /> carry = digit / 10;<br /> number[j] = digit % 10;<br /> }<br /> //continue to add the carry<br /> while (carry)<br /> {<br /> number[size] = carry % 10;<br /> carry /= 10;<br /> ++size;<br /> }<br /> }<br /><br /> int sum = 0;<br /> //sum of the digits of the number<br /> for (int i = 0; i < size; ++i)<br /> sum += number[i];<br /><br /> cout << sum << endl;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-89677077067269475182009-07-16T13:14:00.000-07:002009-07-16T13:32:26.049-07:00Grind Report 19<div style="text-align: left;"><div style="text-align: left;"><a href="http://projecteuler.net/index.php?section=problems&id=19">Problem 19<br /></a></div><br /><div style="font-style: italic;" class="problem_content"> <p>You are given the following information, but you may prefer to do some research for yourself.</p> <ul><li>1 Jan 1900 was a Monday.</li><li>Thirty days has September,<br />April, June and November.<br />All the rest have thirty-one,<br />Saving February alone,<br />Which has twenty-eight, rain or shine.<br />And on leap years, twenty-nine.</li><li>A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.</li></ul> <p>How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />I completely misread this problem when I first started. I think I got too excited and got carried away planning how to solve this before I actually understood what they were asking for. For some reason I was thinking Monday, not Sunday, and also instead of the first of the month I was thinking the first month of the year (January). I eventually realized that I must have read the question wrong and carefully reread it. But I learned a very important life lesson that hopefully I wont have to relearn for a few days at least - know what they are asking before giving an answer.<br /><br />Moving on, I came up with this interesting solution. Essentially the algorithm only checks every first Sunday of the month and sees if it is the 1st and if so increments the count and moves on. This is pretty basic and I suppose the only cool thing about it is the way I calculate the first Sunday of the month.<br /><pre><br />#include <iostream><br />#include <vector><br /><br />using std::cout;<br />using std::endl;<br />using std::cin;<br />using std::vector;<br /><br />const int NUMBEROFDAYSINWEEK = 7;<br /><br />int main()<br />{<br />//store the number of days in each month<br />vector<int> months;<br />months.push_back(31); //January<br />months.push_back(28); //Feburary<br />months.push_back(31); //March<br />months.push_back(30); //April<br />months.push_back(31); //May<br />months.push_back(30); //June<br />months.push_back(31); //July<br />months.push_back(31); //August<br />months.push_back(30); //Septemeber<br />months.push_back(31); //October<br />months.push_back(30); //November<br />months.push_back(31); //December<br /><br />//start date: January 6, 1901 (Sunday)<br />int year = 1901;<br />int month = 0;<br />int firstsunday = 6;<br /><br />int sundays = 0;<br />//go month by month checking to see if the first sunday is on the first<br />while (year < 2001)<br />{<br /> //if you reached the end of the year then restart to January.<br /> if (month == 12)<br /> {<br /> ++year;<br /> month = 0;<br /> }<br /> //check to see if the current first sunday of the month is on the first<br /> if (firstsunday == 1)<br /> ++sundays;<br /> //get the number of days in the month (account for possible leap years)<br /> int daysinmonth = months[month] + (month == 1 && year % 4 == 0 && (year % 100 != 0 || year % 400 == 0));<br /> //calculate the first sunday of the next month<br /> firstsunday = NUMBEROFDAYSINWEEK - ((daysinmonth - firstsunday) % NUMBEROFDAYSINWEEK);<br /> ++month;<br />}<br />cout << sundays << endl;<br />}<br /></pre><br />*saved game*<br /></div>Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-37289468146705569432009-07-16T01:42:00.000-07:002009-07-16T02:05:22.469-07:00Grind Report 18Alright! I am now officially above the average for the number of problems completed on Project Euler. The current average is 17.3. You can see the statistics <a href="http://projecteuler.net/index.php?section=statistics">here</a>.<br /><br /><a href="http://projecteuler.net/index.php?section=problems&id=18">Problem 18</a><br /><br /><p style="font-style: italic;">By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.</p> <p style="text-align: center; font-style: italic;font-family:courier new;font-size:12pt;"><span style="color: rgb(255, 0, 0);">3</span><br /><span style="color: rgb(255, 0, 0);">7</span> 5<br />2 <span style="color: rgb(255, 0, 0);">4</span> 6<br />8 5 <span style="color: rgb(255, 0, 0);">9</span> 3</p> <p style="font-style: italic;">That is, 3 + 7 + 4 + 9 = 23.</p> <p style="font-style: italic;">Find the maximum total from top to bottom of the triangle below:</p><p style="text-align: left;"><span style="font-style: italic;"> [number triangle]</span><br /></p><b style="font-style: italic;">NOTE:</b><span style="font-style: italic;"> As there are only 16384 routes, it is possible to solve this problem by trying every route. However, </span><a style="font-style: italic;" href="http://projecteuler.net/index.php?section=problems&id=67">Problem 67</a><span style="font-style: italic;">, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)</span><br /><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />As soon as I read "clever method" my heart jumped for joy for it knows what a challenge looks like. I immediately began seeking to discover this oh so clever method.<br /><br />My initial thought was that I could possibly use some type of algorithm like A* (A-star) and find the best path using that. In order for A* to work I would need each point, every number, to know what its value is to reach the bottom - or at least this is what I was thinking. When I did look at the bottom and see if I could actually come up with this value for each number, I saw that I could get this if I started with the second to last row and considered each number. For each number I would take the largest out of the two choices that number had below it and add it to the number. Like so...<br /><br />//consider the first number<br /><span style="font-weight: bold; font-style: italic;">63</span> 66<br /><span style="font-weight: bold;">04</span><span style="font-weight: bold; font-style: italic;"> </span><span style="font-weight: bold;">62</span> 98<br /><br />//add 62 to 63<br /><span style="font-weight: bold;">125</span> 66<br />04 62 98<br /><br />//consider the secon number<br />125 <span style="font-weight: bold;">66</span><br />04 <span style="font-weight: bold;">62 98</span><br /><br />//add 98 to 66<br />63 <span style="font-weight: bold;">164</span><br />04 62 98<br /><br />...and so on. Move up the rows as you complete them to get the best value so we can perform the A*... wait. When we get to the top it is going to have the largest number we can get right? Isn't that we are going for?<br /><br />Yes!<br /><br />And this is how I stumbled upon the "clever method". It was around this point that I concluded that A* is not the algorithm you'd want to use for this type of problem. It was worth a shot though and amazing it did lead to the correct answer.<br /><br />Here is my implementation of the method explained above.<br /><pre><br />#include <iostream><br />#include <vector><br />#include <fstream><br />#include <string><br /><br />using std::string;<br />using std::ifstream;<br />using std::vector;<br /><br />//changes a string to an int<br />int stoi(string str)<br />{<br />int val;<br />val = 0;<br />for (int i = 0; i < str.length(); ++i)<br />val = 10 * val + (str[i] - '0');<br />return val;<br />}<br /><br />int main()<br />{<br />vector<vector<int>> triangle;<br /><br />//read in the triangle from file<br />string line;<br />int lineCount = 0;<br />ifstream file ("triangle.txt");<br />if (file.is_open())<br />{<br />while (!file.eof())<br />{<br /> std::getline(file, line);<br /> triangle.push_back(vector<int>());<br /> for (int i = 0; i * 3 + 1 < line.length(); ++i)<br /> {<br /> int number = stoi(line.substr(i * 3, 2));<br /> triangle[lineCount].push_back(number);<br /> }<br /> ++lineCount;<br />}<br />//take back the extra line<br />--lineCount;<br />}<br /><br />//go through every row, starting from the second to the bottom,<br />//and calculate the row's optimal values based off of the row below<br />for (int i = lineCount - 1; i >= 0; --i)<br />//go through every number<br />for (int j = 0; j < triangle[i].size(); ++j)<br /> //add the best possible value to the current index<br /> triangle[i][j] += triangle[i + 1][j] > triangle[i + 1][j + 1] ? triangle[i + 1][j] : triangle[i + 1][j + 1];<br />//the top will house the maximum value at the end of the algorithm<br />std::cout << triangle[0][0] << std::endl;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-57360036721939182042009-07-14T17:05:00.000-07:002009-07-14T17:18:36.004-07:00Grind Report 17<a href="http://projecteuler.net/index.php?section=problems&id=17">Problem 17</a><br /><br /><div style="font-style: italic;" class="problem_content"> <p>If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.</p> <p>If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used? </p> <b>NOTE:</b> Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage. </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />There are many approaches to this. I think that this is a pretty simply problem overall. My approach to this problem was fairly straightfoward. Basically I made a map that consisted of keys that represented the number and the values were the number of letters the number was made up of. Such as 7 mapped to 5 (seven). 20 -> 6 (twenty).<br /><br />I did not have to include all of the numbers because there is so much overlap and I could split up the number into its different components. An example of this would be 192 one comes from 1 -> 3. 100 -> 7. 90 -> 6. 2 -> 3 and then since the number is greater than 100 and not evenly divisible by 100 we need to include the 'and' so add 3. 192 = 22<br /><br />I used recursion for this since I like recursion so much :)<br /><pre><br />#include <string><br />#include <iostream><br />#include <map><br /><br />using std::map;<br />using std::string;<br />using std::cout;<br /><br />map<int, int> dictionary;<br />const int MAX = 1000;<br /><br />int CountLetters(int number)<br />{<br /> if (!number)<br /> return 0;<br /> if (number < 20)<br /> return dictionary[number];<br /> if (number / 1000)<br /> return CountLetters(number / 1000) + dictionary[1000] + CountLetters(number % 1000);<br /> if (number / 100)<br /> {<br /> int temp = CountLetters(number / 100);<br /> temp += dictionary[100];<br /> temp += CountLetters(number % 100);<br /> return temp;<br /> }<br /> if (number / 10)<br /> {<br /> int temp = dictionary[(number / 10) * 10];<br /> temp += CountLetters(number % 10);<br /> return temp;<br /> }<br />}<br /><br />int main()<br />{<br /> dictionary[0] = 3; //and<br /> dictionary[1] = 3; //one<br /> dictionary[2] = 3; //two<br /> dictionary[3] = 5; //three<br /> dictionary[4] = 4; //four<br /> dictionary[5] = 4; //five<br /> dictionary[6] = 3; //six<br /> dictionary[7] = 5; //seven<br /> dictionary[8] = 5; //eight<br /> dictionary[9] = 4; //nine<br /> dictionary[10] = 3; //ten<br /> dictionary[11] = 6; //eleven<br /> dictionary[12] = 6; //twelve<br /> dictionary[13] = 8; //thirteen<br /> dictionary[14] = 8; //fourteen<br /> dictionary[15] = 7; //fifteen<br /> dictionary[16] = 7; //sixteen<br /> dictionary[17] = 9; //seventeen<br /> dictionary[18] = 8; //eighteen<br /> dictionary[19] = 8; //nineteen<br /> dictionary[20] = 6; //twenty<br /> dictionary[30] = 6; //thirty<br /> dictionary[40] = 5; //forty<br /> dictionary[50] = 5; //fifty<br /> dictionary[60] = 5; //sixty<br /> dictionary[70] = 7; //seventy<br /> dictionary[80] = 6; //eighty<br /> dictionary[90] = 6; //ninety<br /> dictionary[100] = 7; //hundred<br /> dictionary[1000] = 8; //thousand<br /><br /><br /> int temp = CountLetters(201);<br /><br /><br /> int letterCount = 0;<br /> for (int i = 1; i <= MAX; ++i)<br /> {<br /> letterCount += CountLetters(i);<br /> if (i > 100 && i % 100 != 0)<br /> letterCount += dictionary[0];<br /> }<br /><br /> cout << letterCount << std::endl;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-68631367506911705472009-07-13T08:22:00.000-07:002009-07-13T08:39:44.081-07:00Grind Report 16<a href="http://projecteuler.net/index.php?section=problems&id=16">Problem 16</a><br /><br /><div style="font-style: italic;" class="problem_content"> <p>2<img src="http://projecteuler.net/index.php?section=problems&id=16" style="display: none;" alt="^(" /><sup>15</sup><img src="http://projecteuler.net/index.php?section=problems&id=16" style="display: none;" alt=")" /> = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.</p> <p>What is the sum of the digits of the number 2<img src="http://projecteuler.net/index.php?section=problems&id=16" style="display: none;" alt="^(" /><sup>1000</sup><img src="http://projecteuler.net/index.php?section=problems&id=16" style="display: none;" alt=")" />?</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the Solution!*</span><br /><br />What is your first thought when looking at this problem? Mine was that the largest number that C++ can represent is 2^64 (long long). So obviously we cannot just calculate this by any traditional means.<br /><br />What I decided to do is go back to grade school and implement some basic arithmetic to solve the problem. I did this by creating a large array that would house the solution. The array was initialized with 1 in the first index and I then preceded to continuously multiply the contents of the array by the base value, 2 in this case. Carrying was of course necessary.<br /><br />I feel like this was a pretty basic and fairly obvious approach to solving this problem. I know that some of the scripting languages such as Ruby or Python were able to solve this problem in one line - good for them. Here is my code.<br /><pre><br />#include <iostream><br /><br />using std::cout;<br />using std::endl;<br /><br />//2^1000 (This solution works for BASE 1-10 & POWER 0+)<br />const int BASE = 2;<br />const int POWER = 1000;<br /><br />int main()<br />{<br /> //this array size needs to be adjusted according to the BASE and POWER<br /> int number[310];<br /> //BASE^0<br /> number[0] = 1;<br /> int size = 1;<br /> int remainder = 0;<br /> //for each power...<br /> for (int i = 1; i <= POWER; ++i)<br /> {<br /> //raise each value by the base, keep the remainder and use the previous remainder<br /> for (int j = 0; j < size; ++j)<br /> {<br /> //calculate the new remainder<br /> int newRemainder = BASE * number[j] / 10;<br /> //the new value of this digit<br /> number[j] = ((BASE * number[j]) % 10) + remainder;<br /><br /> //check to see if the remainder caused overflow<br /> if (number[j] / 10)<br /> {<br /> newRemainder += number[j] / 10;<br /> number[j] = number[j] % 10;<br /> }<br /> //set the remainder<br /> remainder = newRemainder;<br /> }<br /> //if there is a remainder left then add it and increase the size<br /> if (remainder)<br /> {<br /> number[size] = remainder;<br /> ++size;<br /> }<br /> remainder = 0;<br /> }<br /><br /> int sum = 0;<br /> //sum of the digits of the number<br /> for (int i = 0; i < size; ++i)<br /> sum += number[i];<br /><br /> cout << sum << endl;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-15134345039796941542009-07-12T23:20:00.000-07:002009-07-12T23:59:31.085-07:00Grind Report 15<a href="http://projecteuler.net/index.php?section=problems&id=15">Problem 15</a><br /><br /><div style="font-style: italic;" class="problem_content"> <p>Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.</p> <div style="text-align: center;"> [2x2 grid routes]<br /></div> <p>How many routes are there through a 20x20 grid?</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />This was an interesting and challenging problem! That is if you don't have any background with this type of problem. To be completely honest, this was the first problem thus far that actually had me stumped. I enjoyed it!<br /><br />My initial intuition was that there must be some type of equation that represents the answer. The grounding for this thought was based on the fact that the number of routes grows with the size of the grid. But how? This question daunted me for nearly an hour before I came to the conclusion that I would not be able to derive this algorithm and there must be another way. Before I move on though, I would like to share some of my attempts.<br /><br />For some reason, along with my initial intuition came the factorial sign (!) and so I played around with that some. I saw that for the 2x2 grid 3! = 6 which is (2 + 1)!. I needed more samples to work with so I figured out that 1x1 = 2 and 3x3 = 20. (1 + 1)! = 2. I was really onto something! (3 + 1)! = 24 ...or not >.<.<br /><br />My next attempt was nxn = (2n)! / 2n. 2x2 = 4! / 4 = 6. Good... 6! / 6 = 120...not quite. I played around with some other numbers but soon moved onto my next method.<br /><br />This other method consisted of me staring at all the possible 3x3 routes and trying to come up with some sort of elegant way to calculate the number of paths for any nxn grid. I tried many things like sorting the routes by the number of turns they took, breaking the 3x3 into a 2x2 and seeing if I could build off of the previous nxn grid...ect. Some of these ideas where definitely better than others, but in the end I had come up with nothing. I was for once actually stumped.<br /><br />So I turned to my good friend, Google, and asked him what he knew about this problem. I was looking for some type of hint - a push towards the solution. Well, he told me exactly what I was asking for...and way more. Unfortunately, while I was attempting to find a hint, I found a HUGE hint that led to the solution in about...3 seconds...<br /><br />What I found was that this problem is strongly connected with <a href="http://en.wikipedia.org/wiki/Pascal%27s_triangle">pascal's triangle</a> and by drawing the triangle inside the grid (with the outside 1's on the outside of the grid) you can actual find the number of possible routes every time by looking at the largest number (it will be in the corner). If you do this starting from the bottom corner of the grid up to the start corner each number inside of the grid represents the possible number of routes from that corner. You have no idea how close I was to figuring this out. I went ahead and programmed something along these lines to get the solution. <pre><br />#include <string><br />#include <iostream><br /><br />using namespace std;<br /><br />const int diminsion = 20;<br /><br />int main()<br />{<br />int total;<br />//this grid will be a pascals triangle<br />long long grid[diminsion + 1][diminsion + 1];<br />//fill in the sides with 1<br />for (int i = 0; i < diminsion + 1; ++i)<br />{<br /> grid[0][i] = 1;<br /> grid[i][0] = 1;<br />}<br />//fill in the middle<br />for (int i = 1; i < diminsion + 1; ++i)<br />{<br /> for (int j = 1; j < diminsion + 1; ++j)<br /> {<br /> grid[i][j] = grid[i - 1][j] + grid[i][j - 1];<br /> }<br />}<br />cout << grid[20][20];<br />}<br /></pre><br />After getting the solution I was able to read the forums for this question and see what the different solutions people had come up with. Apparently there is another way to solve this problem. This other method deals with combinatorics, which I almost took last semester but didn't because I wanted to take Linear Programming. I don't know all of the details that go into finding this solution but I do know what the solution looks like.<br /><br />(40!) / (20! * 20!)<br />((2n)!) / (n! * n!)<br /><br />...seriously!? >.>;<br /><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-35537784053263139022009-07-11T19:59:00.000-07:002009-07-11T20:30:45.460-07:00Grind Report 14<a href="http://projecteuler.net/index.php?section=problems&id=14">Problem 14</a><br /><br /><div style="font-style: italic;" class="problem_content"> <p>The following iterative sequence is defined for the set of positive integers:</p> <p style="margin-left: 50px;"><var>n</var> -><var> n</var>/2 (<var>n</var> is even)<br /><var>n</var> -> 3<var>n</var> + 1 (<var>n</var> is odd)</p> <p>Using the rule above and starting with 13, we generate the following sequence:</p> <div style="text-align: center;">13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1</div> <p>It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.</p> <p>Which starting number, under one million, produces the longest chain?</p> <p class="info"><b>NOTE:</b> Once the chain starts the terms are allowed to go above one million.</p> </div><br /><span style="font-weight: bold;">*WARNING: This contains the solution!*</span><br /><br />As you can guess this could be a lot of calculations. But all of the numbers eventually cross at some point (4 -> 2 -> 1). So my first thought was to use <a href="http://en.wikipedia.org/wiki/Memoization">memoization</a> but before I did this I implemented a fairly straightforward method (for the most part brute force). I got this to work almost immediately so I decided to attempt the memoization.<br /><br />Along side the memoization, I used a recursive method. Basically I had a map that stored the number as a key and the value was the number of terms in the chain the key would produce. Overall I think this was a good direction to come from; however, there was two things I did not take into consideration.<br /><br />One thing is that the overhead for each function call in the recursion added up thus slowing the program. The other problem is that mapping each value to a key took a toll on the speed as well. I ended up scrapping this attempt because the brute force method was pretty fast (1.5~ seconds to solve this problem). In retrospec, I think I could have fixed up this memoization method and gotten it to be faster than 1.5~ seconds.<br /><br />First, if I inlined the function *I think* that would take out some? most? of the overhead for calling the function. The other thing I could have done is been smarter with mapping the numbers. Such as only mapping the more common numbers; however, I am not sure how to distinguish the common numbers from the other numbers. Even numbers would be a guess of mine, but that is something I'd have to consider more for a good answer.<br /><br />So I reverted back to my first attempt. Two things I used to make this attempt more effecient were: only consider odd numbers, only consider numbers 500,000-999,999. The reason for the first one is somewhat obvious. Odd numbers make it become larger; even numbers make it become smaller. The reason for the second one is because all numbers 1-499,999 can be multiplied by 2 and be found within the range I was considering - therefore adding an extra number to the chain. :)<br /><br />Here is my brute force method.<br /><pre><br />#include <string><br />#include <iostream><br /><br />using std::string;<br />using std::cout;<br /><br />const int MAX = 999999;<br /><br />int main()<br />{<br />int answer = 0;<br />int highestCount = 0;<br />for (int i = (MAX + 1) / 2; i < MAX; i += 2)<br />{<br /> long long number = i;<br /> int count = 1;<br /> while (number != 1)<br /> {<br /> if (number % 2 == 0)<br /> number /= 2;<br /> else<br /> number = number * 3 + 1;<br /> ++count;<br /> }<br /> if (count > highestCount)<br /> {<br /> highestCount = count;<br /> answer = i;<br /> }<br />}<br />cout << "Highest Number is " << highestNumber << std::endl;<br />cout << answer << " with count of " << highestCount << std::endl;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0tag:blogger.com,1999:blog-3381166106277010995.post-29546088661558812192009-07-10T09:19:00.000-07:002009-07-10T09:36:21.994-07:00Grind Report 13After a two day hiatus, I am back and ready for action.<br /><br /><a href="http://projecteuler.net/index.php?section=problems&id=13">Problem 13</a><br /><br /><span style="font-style: italic;">Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.</span><br /><br /><span style="font-style: italic;">[list of 100 50-digit numbers]</span><br /><br />With one of the earlier problems I had to deal with some large numbers and know that the largest integer type provided by C++ is unsigned long long, which ranges from 0 to 18446744073709551615. That is not 50-digits long. So having a long long array of the 100 numbers is out of the question.<br /><br />One of the keys to solving this is that only the first 10 digits of the sum needs to be found. So my first thought was that I only needed to sum up around the first 15~ digits of each number. This gives plenty of room for the number to be correct and also fit inside of a long long.<br /><br />Another thought I had was to just simply read from a file one line at a time. Each line has a number so I take the substring of the first 15 digits and then convert it into a long long and add it to the total. Once the file reaches its end all that needs to be done is return the answer.<br /><br />This is very straight forward, took about 15 minutes to solve completely, and returned the correct answer my first run. :)<br /><pre><br />#include <iostream><br />#include <fstream><br />#include <string><br /><br />using std::string;<br />using std::ifstream;<br /><br /><br />long long atoll(string str)<br />{<br /> long long val;<br /> val = 0;<br /> //goes through each digit and adds it to the value<br /> for (int i = 0; i < str.length(); ++i)<br /> val = 10 * val + (str[i] - '0');<br /> return val;<br />}<br /><br />int main()<br />{<br /> long long answer = 0;<br /> string line;<br /> ifstream file ("numbers.txt");<br /> if (file.is_open())<br /> {<br /> while (!file.eof())<br /> {<br /> std::getline(file, line);<br /> line = line.substr(0, 15);<br /> answer += atoll(line);<br /> }<br /> }<br /> std::cout << answer << std::endl;<br />}<br /></pre><br />*saved game*Jasson McMorrishttp://www.blogger.com/profile/17374944413887501335noreply@blogger.com0