CarlsenBot – Third update

2013-04-25 21.19.04

Since last time, my rig got an upgrade in placement of the y-axis movement racks and z-axis movement racks. It looks pretty sweet, I know. It’s still got some ugly wires, but believe me, it was looking much worse earlier. May have to get some tubing for the remaining wires.

 

2013-04-25 21.19.18

Here’s the rig controller. 4 identical H-bridges control each of the motors. I will probably adjust it so all the wires stay flush against the breadboard.

 

 

2013-04-25 21.19.28

Lastly, here’s the Sparkfun claw affixed to the end of the z-axis. It is the only thing that’s not part of the system, as evident by its leads unconnected. I’m heading back to the lab to fix that as soon as I finish eating. You will also see in the back the distance sensor we plan to use to determine the height of the z-axis. You might wonder why don’t we just use the encoder? Because I had an oversight, and didn’t get enough encoder attachments for the motors.

A simple test revealed that everything moved without fail, which is a huge relief. It means that this rig is ready for a day of programming. Look out for the next update!

CarlsenBot – Second update

Since the last time, the rig’s got one new edition: racks to enable movement in one direction. It looks like this:

2013-04-19 15.02.45

And video of “movement”:

I should have known better than to film vertically… The program runs a simple movement command for a short time, at the end of which I reset the microcontroller and step back to get the shot. Let it be known I do terrible prototype wiring. It will no doubt be cleaned up as we progress.

That being said, it’s awesome to finally see movement, after having so many setbacks. There was going to be another problem though: the motor movements are tracked with an encoder on one of the motors, just one though, so it’s possible the other one will lag. That’s been fixed by changing the other motor to one with an encoder, so this picture actually isn’t the one that’s most recent.

I thought programming was going to be a huge headache. And it was/is. I don’t know a whole lot about controls, and until I know a little bit more, movement is going to be a little naive: move towards desired position at full speed, and ramp down speed as platform approaches.

Here was another thing that was testing me as I was programming. The vex motor encoder is an i2c device, and the mbed microcontroller only has two i2c sda/scl pair of output pins. We are using a minimum of at least 3 encoders, so at least two encoders will be put on the same bus. To distinguish between the encoders on the same bus, you have to change their address (I’ll assume you know the basics of i2c from here). According to the datasheet for the encoder, you can change the address by opening up communication with the default address of 0x60, then writing the value 0x40, which is the address of “change default address” register, followed up by a final write of the desired register address (which should be in the range of 0x20-0x5E). The mbed i2c library is a little strange, because these two should do the same thing…but they don’t:


char changeAddr = 0x4D; // change address register
char newAddr = 0x20; // new address
i2c.write(0x40, &changeAddr, 1); // tell encoder I want to change default address
i2c.write(newAddr); // write new address

// that didn't work, but this did:

char changeAddr[2] = {0x4D, 0x20}; // put values to write in an array
i2c.write(0x40, changeAddr, 2);

the mbed’s i2c API specifies two versions of the write method, write(addr, char*, int) where the first argument is the address of the device, the second is a pointer to the values being written (hence why in the first try, and the third is the number of bytes to write. The other write is just write(byte) which writes a single value on the line. I thought after sending the device the value 0x4D, it knows that I am sending a value of the new address I want. But that can’t be done in a separate write. The “write” method includes the start and stop commands, so that was probably why. That took me way too long to figure out. Not enough experience working with i2c I suppose.

The encoders are also a bit different from other i2c devices in that multiple devices on a bus are actually daisy chained together, as opposed to devices attaching themselves to the bus like the other devices I’ve worked with, and there is a register that tells each device in the chain whether to pass through the clock and data along. If it does not, it is called a terminator. This is set in a register. If you do in fact want an i2c bus, you must disable the terminator register, and the next device can be initialized just as in the above.

Hopefully this phase of the programming will be done soon, and what I learn can be applied to movements in the other axis.

CarlsenBot (working title) – first update

Some time ago I announced my final project for my Embedded Systems class: a voice activated chess-playing robot. Turns out another group did something similar a couple semesters ago, and they called it Kasparobot, clearly named after Gary Kasparov. It played with a chess engine by registering moves through OpenCV. Inspired by the name, I’ve christened our robot CarlsenBot, after Magnus Carlsen. I spent a few days looking at similar projects, namely this one: letsmakerobots.com/node/20833. It’s very well documented, and the various pictures help immensely. I’m very glad I found this, as it will provide a most excellent skeleton for my own project. My team and I spent a few hours digging through the parts in the lab and rigging together this setup:

2013-04-12 14.39.04 2013-04-12 14.39.16 2013-04-12 14.39.29

Zoom in on the first picture. The green thing is a toothed rack, which turns rotary motion from a motor into linear motion with a gear that travels on the rack. We plan to place racks on the two arches to create movement along one axis, and create a movable platform positioned by motors and pinions, that will allow movement in the other two axis. You can see a claw that looks like it came from the same set we found these racks.

* To my annoyance the arches are slightly less than parallel, but I suppose if the racks are position parallel, it doesn’t really matter.

We will have to order a few new parts pronto, and assemble the platform I have in mind.

In parallel, we also have to get a program running to recognize dictated commands. For that, I think we might use this: http://msdn.microsoft.com/en-us/vstudio/cc482921.aspx. We’ve also got another option in EasyVR, which is a voice recognition hardware module: https://www.sparkfun.com/products/10685. It’s got an advantage of having a library already created by some other user on our microcontroller platform, but has the disadvantage of needing to be trained.

Hopefully a rough prototype can be completed this week, and finished next week, with plenty of time to debug before the demo.

New project – Voice controlled chess robot

For the final project in my embedded systems class, I’ve decided to build a voice controlled chess robot. I’ve got three other people working with me now so it should be manageable (or, it turns out to be a really easy project and we coast for the rest of the semester).

Just off the top of my head, here’s what we have to get done:

– find a voice recognition engine. For this we might use a EasyVR module, or Microsoft’s Speech SDK. I think EasyVR has to be trained, and I’d really like it to be independent of speaker, so that anybody can sit down and dictate.

– use the mbed to control motors that move a pick-and-place machine. Luckily mbed’s huge support will make this easy, hopefully. Encoder and motor libraries already exist, so I’ll be taking advantage of that.

– build the chassis for the pick-and-place machine.

Stay updated for progress during the next month!

Projust Euler 55 – Lychrel Numbers

This isn’t too difficult a problem, but it’s made simpler with a few helper functions. Most problems thus far could all be written in main(), but this problem requires a lot of string processing (at least the way I’m going about it). As for the problem description:

First, there are palindromic numbers, which are, as the name implies, numbers that are palindromes (read the same forward and backwards). For example, 7337. Then take 349. If we reverse it, and add the reverse to itself, we may or may not get a palindrome. If we don’t, we simply repeat the process:

349 + 943 = 1292

1292 + 2921 = 4213

4213 + 3124 = 7337

So 349 produces a palindrome in 3 iterations. It is thought that some numbers never produce a palindrome with this process, called Lychrel numbers. Because there still isn’t a method for detecting whether a number is Lychrel or not, we’ll assume that a number is Lychrel if it doesn’t produce a palindrome in 50 iterations. The problem description was also nice enough to provide another piece of information, telling us that 10677 is the first number that requires 50+ iterations to terminate, ending at a number that is 28 digits long, so we know what kind of numbers we may be dealing with. The question is, how many numbers are not Lychrel below 10000?

Since the numbers quickly overflow the basic data types, I thought we’d do most of the problem with strings. First we need a function to convert to string, and a function to reverse such a string.

string toString(int n){
   string out = "";
   stringstream nss;
   nss << n;
   return out=nss.str();
} // I guess this wasn't as necessary, since I just ended up using the sstream library

string reverse(string str){
   string out = "";
   for(int i = str.length()-1 ; i >= 0; i--){
   out+=str[i];
   }
   return out;
}

As mentioned, the process quickly overflows even a long long. So I wrote a function to add strings as numbers, and in the case that overflow would occur, adding is done by taking a number in two parts: the lower 18 digits and the upper digits. Two 19 digit numbers could overflow a long long, so I stopped at 18. By the problem description, the largest number we’re dealing with is around ~28 digits, so this method will safely¬† deal with all numbers we’ll come across in this problem. I should mention this isn’t the most pretty looking thing:

string addAsNum(string a, string b){
   string out = "";
   string templ, tempu;
   stringstream lss, uss;
   int carry = 0;
   unsigned long long au, al, bu, bl;
   if(a.length() > 18){ // is a number is greater than 18 digits, we'll have to split it into lower and upper
      stringstream(a.substr(a.length()-18, 18)) >> al;
      a.erase(a.length()-18, 18);
      stringstream(a) >> au;
   } else {
      stringstream(a) >> al;
      au = 0;
   }
   if(b.length() > 18){
      stringstream(b.substr(b.length()-18, 18)) >> bl;
      b.erase(b.length()-18, 18);
      stringstream(b) >> bu;
   } else {
      stringstream(b) >> bl;
      bu = 0;
   }
   lss << (al+bl); // add the lowers, and if that turns out to be greater than 18 digits, we'll have a carry
   templ = lss.str();
   if(templ.length() > 18){
      carry = 1;
      templ.erase(0,1);
   }
   if(carry) uss << (au+bu+1);
   else uss << (au+bu);

   tempu = uss.str();
   if(tempu == "0") tempu = "";
   return out = tempu+templ; // then simply concatenate the upper and lower
}

The rest is pretty straightforward. A function tests if a number is Lychrel or not by repeating the reverse and add process, stopping either when we get a palindrome, or when we have repeated the process 50 times. The main loop calls this function on all numbers < 10000.

bool isLychrel(int n){
   int iterations = 0;
   string temp = toString(n);
   while(iterations < 50){
      temp = addAsNum(temp, reverse(temp));
      if(isPalindrome(temp)){
         return false;
      }
      iterations++;
   }
   return true;
}

int main() {
   clock_t t1 = clock(), t2;
   int count = 0;
   for(int i = 1; i < 10000; i++){
      if(isLychrel(i)) count++;
   }
   t2 = clock();
   cout << "Ans: " << count << endl;
   cout << ((float)t2 - (float)t1)/CLOCKS_PER_SEC << endl;
   return 0;
}

Final Answer: 249

Project Euler 49 – Prime permutations

As promised, here is part 2 of the results of my vigil. This problem describes very special prime sequences. The sequence 1487, 4817, and 8147, has some special properties. First, it is an arithmetic sequence, which means each term of the sequence can be generated by adding some constant to the previous term. In this case the constant is 3330. Next, each term is prime. Lastly, each term is a permutation of the others. There is exactly one other sequence like this of 4-digit numbers, what is it?

My solution to this has the longest runtime of any of the problems I’ve completed yet: 11.528 seconds. Not terrible, but could be a lot better. Here’s the basic approach:

I preloaded all 4 digit primes into a vector, using a text file I generated from some other problem. I have a nested for loop that will check pairs of numbers in the vector to see if they are permutations (which I wrote a isPerm function for). Suppose that they are, then they could possibly be the first two numbers in the sequence I’m looking for. I know they are the first two since my primes list are sorted. Call these two numbers “x” and “y”. Then I can get the next term by adding to y the difference (y-x), since it is supposed to be an arithmetic sequence, that is, z = y+(y-x). I wouldn’t be done yet though, because there’s no guarantee z is the number that completes the sequence I’m looking for. Therefore, it is necessary to check that 1) it is a permutation of x or y and 2) that it is a prime. So for two candidates to the sequence generated by the nested for loop, I check 1) and 2) for the respective “z”.

Here is the code: http://pastebin.com/LRpcjWq0

This turns out to be very slow, even though the number of primes that have 4 digits is only around ~1000 (so that doubly looping through is about ~1000000 loops). I could probably use a better compare function. For isPerm(a,b) works by turn a and b into strings, sorting them, and then checking to see if they are the same. Moreover, it is also probably not necessary to check ALL pairs of primes in my list, but I don’t know what to rule out. I may come back to this later. Regardless, 11.5 seconds still isn’t too long to wait for the answer: 2969, 6299, 9629. Again, the difference of 3330. Coincidence?

Project Euler 48 – Self Powers

As it was Pi-day yesterday, I celebrated by staying up all night catching up on reading for a class because of the weekly quiz. I also spaced out the monotony with some coding. Moreover, this will be part of a twofer! This is a neat problem that I wouldn’t have been able to do until a few weeks ago, when I learned some of the math in being able to do this problem in my Number Theory class. It’s very simple: what is the last 10 digits of the sum 1^1 + 2^2 + 3^3 + 4^4 + … + 1000^1000. Until I learned more about modular arithmetic in my number theory class, I had no idea how to proceed. I doubt there was a formula for sum(k^k), so there is some brute force approach, but 1000^1000 has over 3000 digits! I had written a big-number library for another problem, but I don’t know how well it would carry over.

But luckily, number theory came to the rescue. Presumably you, the reader, know what modulo n means. First, we only care about the last 10 digits of the result. We can get the last digit of any number by dividing out all multiples of 10, that is, the last digit of n is simply n mod 10. Similarly, we can get the last two digits of any number n by dividing out all multiples of 100, n mod 100 in this case. Our problem then indicates that we just need to take n mod 10^10 of the result. Does that mean we need to keep track of the sum in the meantime? No! And thank God, since we still haven’t dealt with that 3000 digit business, but turns out we don’t need to. To proceed, we’ll need two identities:

1. if a = b mod n, then a^k = b^k mod n for k integer. What this means for us is a handy way to keep track of the term k^k mod 10^10, so that any time, the largest number we really have to keep track of won’t exceed 10^10, which can be stored in a long long in my c++ solution. For example, to calculate 100^100, we start with 100 mod n = 100. We can increase the power by 1 by multiplying by 100 and then taking the modulus of the result according to that identity. We repeat until the power equals 100. *

* We can actually do it faster if we square each result, stopping at the highest power of 2 lower than our desired power. To see why, realize a^k = b^k mod n implies (a^k)^2 = (b^k)^2 mod n, and that ((a^k)^2)^2 = ((b^k)^2)^2 mod n, and so on. But it’s an optimization we won’t miss.

2. if a = b mod n, then a + c = b + c mod n. What this one means for us is that we can keep a running modular sum, carry out k^k mod n by means of the first identity, and add it to our result.

Since the highest base is 1000, the first identity is employed less then 1000*1000 times if we increase power linearly. I’m happy with a O(n^2) algorithm if it’s easier to code :p

The result, by the way is 9110846700, and the code is here: http://pastebin.com/q3wPDmyv

Look out for part 2 later in the day! Back to studying I go.

Project Euler 43

Another quick problem post. It’s still adding variety though – I’m refusing the help of the terminal and doing this one mostly by hand (and with the help of Excel).

The problem is from Project Euler, number 43. The operating term here is pandigital number. A number if pandigital from 0 to N if it contains all the numbers from 0 to N once and only once. For example, 1234567890 is a 0-to-5 pandigital number. If we represent a pandigital 0 to 9 number by the string “abcdefghij”, we are looking for a string with such these properties:

  • 2 divides bcd
  • 3 divides cde
  • 5 divides def
  • 7 divides efg
  • 11 divides fgh
  • 13 divides ghi
  • 17 divides hij

So, starting with the second digit (b), consecutive groups of 3 digits are divisible by consecutive primes. The solution to this problem is the sum to all such 0-to-9 pandigital numbers.

It’s probably not unreasonable to have a program go through permutations of 1234567890, of which there are 10! = 3628000, and perform these tests, but this is definitely doable by hand, which I will attempt. To do this, we will use basic divisibility rules to narrow our search space, and remember that a number can only be used once.

First, if 5 divides “def”, then f can only be a 0 or 5. However, if f = 0, then “fgh” = “0gh” is only divisible by 11 if g = h. To see why, look at the numbers divisible by 11 under 100: 011, 022, 033,… Because they contain repeated digits, 0 is out as an option for f, so f is decidedly 5.

Next, we go back to “def”. There are only a handful of 3-digit numbers divisible by 7 that have the middle digit as 5. I created a multiplication table in Excel and picked out all such numbers: 056, 154, 259, 350, 357, 651, 658, 756, 854, 952. Immediately we see that our search space is already reduced considerably.

We move to the right in our string because there are fewer numbers divisible by 11, 13, and 17 than numbers divisible by 2 and 3. Again, I had to consult a multiplication table, but for 11. For each number in the previous list, we look at two rightmost digits, and see if they appear in the multiplication table for 11 as the first two digits. For example, for 056, “561” appears in the table, so it’s a possible candidate, however, “54g” doesn’t appear in the table for any value of g. Progressing this way, we find possible values for “defg”: 0561, 2954, 3506, 3572, 6517, 6583, 7561.

The values for i and j are found the exact same way. By consulting a multiplication table for 13 and 17, we look at the two rightmost numbers in the previous list, and see if they appear as the first two digits of any number. Our list is considerably shorter by the end of this. Possible candidates for efghij: 357289, 952867.

With that, we are done with the six rightmost digits. To move left, we consider candidates for d. Note that since 6 digits have been decided, d can only take on four values, namely {0, 1, 4, 6} for 357289, and {0, 1, 3, 4} for 952867. We can eliminate a few more options with some observations: “bcd” is divisible by 2, so that bcd is a even number, which means it can only be one of 0, 2, 4, 6, or 8. So in each set of four candidates, we eliminate the odd numbers. Our list is now: 0357289, 4357289, 6357289, 0952867, 4952867.

The logic for choosing “c” will depend on a little-known rule for divisibility by 3: a number is divisible by 3 if the sum of all digits results in a number divisible by 3. Then for each candidate in the previous list, we consider numbers that could be formed by the 3 remaining unused numbers, and look at the first three digits to see if they pass the test. For example, 0357289 leaves {1, 4, 6} unused. Of these, concatenated with 03, only 603 is divisible by 3. So we get 60357289 out of this. Note that some candidates above don’t have any unused number that could be used to pass this test. Our list is now: 60357289, 06357289, 30952867.

Finally, note that each candidate in the previous list unconditionally passes the test for bcd, that is, bcd divisible by 2. To see why, regardless of what b is, “b60”, “b06”, and “b30” will always be divisible by 2. After choosing b, we have used nine of ten possible digits, so a is also decided.

Our final list and the sum is:

1460357289

4160357289

1406357289

4106357289

1430952867

4130952867

_______________

16695334890

 

More posts will probably be more like this and the last for the near future, since I’m getting ready for a programming competition and Microsoft Puzzle Challenge, but I may put up what I’ve been working on for my ECE4180 – Embedded Systems class.

First real post – Project Euler 14 (Longest Collatz sequence)

Let’s kick off this blog with a programming problem. This is number 14 on Project Euler, something I do on and off. The problem deals with the Collatz conjecture, which to my knowledge is still unsolved. It states that given an integer N, let N be the first term in a sequence defined iteratively as:

  1. if N is even, the next term is N/2
  2. if N is odd, the next term is 3N+1

For example, the sequence starting with 9 is 9-28-14-7-22-11-32-16-8-4-2-1. Which produces a chain of 12 number.The conjecture says that all chains end at 1. The actual problem relating to this post is much simpler: what number produces the longest chain starting with a number less than 1 million?

My solution is straightforward: for the integers 1 through 999999, generate chains as per the definition, and stop when the chain reaches 1. For our purposes, presumably all integers below 1000000 produces a chain that ends at 1. All the while, keep track of the longest chain as well as the number causing the chain along the way.

The solution does rely on one optimization. Suppose we’ve determined the chain length belonging to 21. When performing the iteration on 42, it is not necessary to step through until the chain reaches 1, because the next number in the chain is 21, a number we already have the enumeration for. The problem is made simpler by just wanting the chain length, so we can store the chain length produced by a number in an array, and perform a lookup if the iteration produces a number we know the chain for. My solution steps through the numbers 1 to 999999 in order, so it is possible that N/2 produces a link in the chain we have the length for, and can simply add it.

Here is the code that does it (in C++, which is what I’m most familiar with):

edit: ok don’t know any good methods for embedding code. Until then, here’s a pastebin: http://pastebin.com/WqxhwK8j

The above runs almost instantaneously (supposedly all problems on Project Euler can be solved in 2 minutes), and gives the solution 837799.

My background isn’t in programming, so I’m not a stellar programmer by any standards. I welcome any and all critique, especially on future problems I tackle. Enjoy!

Ben