|
|
11-01-2009, 04:50 PM
|
#11 |
|
CEO
Join Date: Dec 2007
Age: 15
Posts: 1,017
|
I've known about this for a while, and currently have 24 problems completed. I just coded a solution for #220 in Java and it's computing right now.
http://projecteuler.net/index.php?se...roblems&id=220 Code:
public class Heighway_Dragon {
static int a,b,x,y;
public static void main(String[] args) {
position(1000000000000l,construct(50));
}
public static String construct(int i){
String current = "Fa";
String next;
for(int generation=1;generation<=i;generation++){
next = "";
for(int x=0;x<current.length();x++){
switch(current.charAt(x)){
case 'a': next+="aRbFR"; break;
case 'b': next+="LFaLb"; break;
case 'F': next+="F"; break;
case 'R': next+="R"; break;
case 'L': next+="L"; break;
}
}
current=next;
}
return current;
}
public static void position(long pos, String dragon){
dragon=dragon.replaceAll("a","");
dragon=dragon.replaceAll("b","");
int direction=1;
while(b<pos){
a++;
if(dragon.charAt(a)=='F'){
if(direction==1)
y++;
if(direction==2)
x++;
if(direction==3)
y-=1;
if(direction==4)
x-=1;
b++;
} else if(dragon.charAt(a)=='L') {
direction-=1;
if(direction==0)
direction=4;
} else if(dragon.charAt(a)=='R') {
direction+=1;
if(direction==5)
direction=1;
}
}
System.out.println(x);
System.out.println(y);
}
}
__________________
|
|
|
|
11-01-2009, 06:56 PM
|
#12 |
|
Brotroid
Join Date: Jul 2003
Location: Chillin' with the Brozo
Age: 22
Posts: 13,097
|
This is pretty cool. If I wasn't supposed to be doing a test right now and not being online, I'd try some of these today.
For now I'll just bookmark it and start tomorrow.
__________________
   
|
|
|
|
|
11-03-2009, 06:22 PM
|
#13 |
|
you % me = you, bro
Join Date: Oct 2004
Location: Texas
Posts: 11,918
|
Found out that the site isn't blocked on my school's websense. That means I'll actually have something to do in my compsci class, after I finish the entire week's worth of work in 15 minutes...
__________________
|
|
|
|
|
12-16-2009, 08:28 PM
|
#15 |
|
you % me = you, bro
Join Date: Oct 2004
Location: Texas
Posts: 11,918
|
__________________
|
|
|
|
|
12-16-2009, 08:33 PM
|
#16 | |
|
CEO
Join Date: Dec 2007
Age: 15
Posts: 1,017
|
Quote:
I assume it means a 6-input binary truth table.
__________________
|
|
|
|
|
|
12-16-2009, 08:37 PM
|
#17 |
|
you % me = you, bro
Join Date: Oct 2004
Location: Texas
Posts: 11,918
|
Er, didn't see that part ,τ, part. Thanks.
On a side note, I just did problem 11 with nothing but ctrl+F and 2 minutes =P
__________________
Last edited by game-bot; 12-16-2009 at 10:12 PM. |
|
|
|
|
12-18-2009, 05:40 PM
|
#18 |
|
you % me = you, bro
Join Date: Oct 2004
Location: Texas
Posts: 11,918
|
Am I the only one doing these?
Just finished problem 54. Not too much programming insight required, but it was worth it in the fact that I now have an efficient playing card algorithm. Although if I were to make a poker game (of course, it'd be Texas Holdem), it'd need a number of tweaks, mostly for the case of ties, which this problem did not make you confront. The whole program takes an average of ~55 ms to get the answer. That #220 one looks interesting Serisium. You ever get it? I'm gonna do that next. Yeah, this is a tough one. I'm down to the optimization point now. Determining D(50) takes too long with an unoptimized method. So far I've only been able to speed it up a small bit by noticing that 'b' always has at least 4 characters after it, so instead of moving the index up 5 (the length of both of the strings we're adding), it can be moved up 9. 'a' is stuck at 5. That's all I've got. Although I've noticed the following patterns:
EDIT Found the pattern. I'll put it up in a bit =P Here. Would spoiler tag it, but it'd make it hard to read. To determine the ending posistion of D(X) without simulating the draw method or making the string, follow the pseudocode. If X is odd, If X is even, Now we can easily get the x,y position of D(X). We'd use this to speed up the calculation of D(50)'s x,y after 10^12 steps by finding the biggest X with < 10^12 steps (which is 2^X), and using that as our starting position. Now to calculate the rest... I have no idea. Is it possible? gah. By the way, the above approach is 230x faster than the brute force.
__________________
Last edited by game-bot; 12-18-2009 at 09:14 PM. |
|
|
|
|
12-19-2009, 01:37 AM
|
#19 |
|
Person
Join Date: Oct 2004
Location: Quel'Dorei
Age: 19
Posts: 12,443
|
Just started problem 98
http://projecteuler.net/index.php?se...problems&id=98 I'll finish it later. Already know what to do. But I'm going to bed now |
|
|
|
|
12-19-2009, 02:44 PM
|
#20 |
|
you % me = you, bro
Join Date: Oct 2004
Location: Texas
Posts: 11,918
|
I don't like the word ones ='(
I'm on solving 209 now. I don't know if it's that I'm not understanding the problem, or what, but I'm not getting the correct answer. Code:
package projecteuler;
public class p209 {
public static int solve() {
return findHowManySatisfy();
}
private static int findHowManySatisfy() {
int count = 0;
boolean[] bool = new boolean[6];
for (int b1 = 0; b1 < 2; b1++) {
bool[0] = !bool[0];
for (int b2 = 0; b2 < 2; b2++) {
bool[1] = !bool[1];
for (int b3 = 0; b3 < 2; b3++) {
bool[2] = !bool[2];
for (int b4 = 0; b4 < 2; b4++) {
bool[3] = !bool[3];
for (int b5 = 0; b5 < 2; b5++) {
bool[4] = !bool[4];
for (int b6 = 0; b6 < 2; b6++) {
bool[5] = !bool[5];
if (satisfiesTT(bool)) {
count++;
}
}
}
}
}
}
}
return count;
}
private static boolean satisfiesTT(boolean[] b) {
//τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0
boolean p2[] = new boolean[6];
p2[0] = b[1];
p2[1] = b[2];
p2[2] = b[3];
p2[3] = b[4];
p2[4] = b[5];
p2[5] = b[0] ^ (b[1] & b[2]);
for (int i = 0; i < 6; i++) {
if (p2[i] & b[i]) {
return false;
}
}
return true;
}
}
__________________
|
|
|
|
 |
| Thread Tools | |
|
|
