import java.util.Scanner;
import java.util.HashSet;
import java.util.Vector;
public class e79 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Vector<HashSet<Integer>> preceding = Vector<HashSet<Integer>>();
HashSet<Integer> used = new HashSet<Integer>();
for (int i = 0; i < 10; ++i) {
preceding.add(new HashSet<Integer>());
}
while (scan.hasNextInt()) {
int entry = scan.nextInt();
Integer d1 = entry / 100;
Integer d2 = (entry / 10) % 10;
Integer d3 = entry % 10;
preceding.get(d2).add(d1);
preceding.get(d3).add(d1);
preceding.get(d3).add(d2);
used.add(d1);
used.add(d2);
used.add(d3);
}
String ans = "";
int i = 0;
while (i < 10) {
if (preceding.get(i).isEmpty() && used.contains(i)) {
ans += i;
used.remove(i);
for (HashSet<Integer> hs : preceding) {
hs.remove(i);
}
i = 0;
} else {
++i;
}
}
System.out.println(ans);
}
}
Sunday, March 30, 2014
Problem 79 - Java, aka fun with HashSets
So, as it was free, I solved problem 79 in Java. Things weren't that bad, and my aversion to Java for the past year and a half or so made me actually pleasantly surprised to find that it wasn't too bad to work with the language, even though I will admit that Vector<HashSet<Integer>> is a lot of boilerplate, but nonetheless, having sets available was good for this problem. Nothing too special, runs in .134 seconds on my machine. Also, notably, my solution depends on the fact that there are no duplicate numbers in the answer, things would be a bit harder if those were allowed.
Friday, March 28, 2014
A single letter and bringing back an old friend - Problem 20 in E
There are a lot of languages with single letter names. To name just the ones used so far in this language challenge, C,D,J,K,R are all languages, and F# deserves an honorable mention. Even the letters that are not associated with languages too many people care about are associated with languages though, as I learned today with E. The hardest part of E was figuring out how to do anything without very much documentation to rely on, but once I figured out how to do things, there wasn't too much issue. The last time I solved problem 20 was way back in the 24-hour 20-problem hackathon that began all of this, and as it was towards the end of the hackathon, I threw a capable language at it, despite it being an easy problem. However, that capable language was Java, which, though I took a semester-long class taught in it, is not exactly my favorite language. However, using it in problem 20 simply because it had the BigInteger class was a bit silly. So, I have now recovered problem 20, and I did so without relying on anything like a BigInteger, instead explicitly storing the big number as an array of digits and doing some work by hand. So, problem 20 is solved, E is used, and Java is free. Solution runs in about 4.8 seconds on my machine, but the E interpreter has such a slow start up time that Hello World runs in about 4.1 seconds, so timing is pretty unreliable.
var d := [1]
def digits := d.diverge()
for x in 2..100 {
var carry := 0
for i in 0..(digits.size()-1) {
var prod := (digits[i] * x) + carry
digits[i] := prod % 10
carry := prod // 10
}
while (carry > 0) {
digits.push( carry % 10)
carry := carry // 10
}
}
var digisum := 0
for d in digits {
digisum += d
}
println(digisum)
Thursday, March 27, 2014
Problem 78 - R
So, after solving problem 45 in Rexx, I had R open and free for use. Problem 78 was a bit annoying for me. Problem 76, I decided to solve using dynamic programming as it was pretty easy to do so, and that solution generalized really well to problem 77. There was another way to solve problem 76, and that was by directly calculating the partition function called p(n) in this problem. I realized that this was what I had to do, but mathworld and wikipedia are not the best place to learn this things (and my copy of TAOPC is up at college, far from my hands), and they were not very clear what conventions were being used or what bounds were reasonable for the sum that must be calculated. My first solution took 67 minutes in Python, and then after the change to the loop bounds, in took 9 seconds. After I ported my solution to R, it took about 4 minutes to calculate the answer, but I am okay with that, according to the first estimate I looked at, about 20x slowdowns are expected moving to R from Python, and Python is already about 20x slower than C, so 4 minutes in a language like R feels like it is fair to consider it within Project Euler's one minute rule. Anyway, here is my solution, which took a while to debug off-by-one errors resulting from arrays starting with index 1.
N = 100000
p <- array(0, dim=c(N))
p[1] <- 1
p[2] <- 1
for (n in 2:N) {
n1 <- 1
n2 <- 1
k <- 1
while (n1 > 0 || n2 > 0) {
n1 <- n - (k*(3*k-1)) %/% 2
n2 <- n - (k*(3*k+1)) %/% 2
c <- 0
if (n1 >= 0) {
c <- p[n1+1]
}
if (n2 >= 0) {
c <- c + p[n2+1]
}
if (k %% 2 == 0) {
c <- c * -1
}
p[n+1] <- (p[n+1] + c) %% 1000000
k <- k + 1
}
if (p[n+1] == 0) {
print(n)
break
}
}
Wednesday, March 26, 2014
Rexx to get R (45)
I want to move on to solve problem 78, but it is another dynamic programming problem, and therefore I would really like a language in which arrays are pretty easy to use. Admittedly, I haven't actually looked much at R, but it feels like a language that should have pretty good support for arrays, seeing as people use it for processing large data sets and stuff. So, the language I used for problem 45 is a language called Rexx (note: do not make the mistake I made and append an extra x to the end of the name while searching for it!) According to http://langpop.com/, it is so popular that it just barely edges out brainfuck. Anyway, here is my wonderful solution, it is little more than a transcription of my old R code to Rexx, but it notably includes yet another implementation of the babylonian method for sqrt: maybe after the 20th time I will finally stop needing to consult wikipedia to remember how to do that.
Solution runs in 1.7s on my computer:
numeric digits 20 i = 144 do forever h = hex(i) if isPent(h) then do say h leave end i = i + 1 end isPent: parse arg p a = sqrt(24*p+1) return (a*a = 24*p+1) & ((a+1) // 6 = 0) hex: parse arg n return n*(2*n-1) sqrt: parse arg N x1 = N % 2 x2 = N do while (x2 - x1) > 1 x2 = x1 x1 = (x1 + (N % x1) ) % 2 end return x2
Hack 77 - I didn't lie
I solved problem 77 in a language called Hack (hacklang.org), which, in the trend of languages that attempt to be "language X but with change Y", is an attempt at making a better version of PHP where it is harder to shoot yourself in the foot. It has type annotations, so it might succeed at that, though I didn't have enough time to see if those annotations actually lead to good static type checking. Anyway, Problem 77 is the type of problem that, if I didn't have to switch languages all the time, would have taken very little effort, but it still didn't take that much effort because it was pretty easy to create my solution to this problem from the last. Still dynamic programming, still similar probably of counting the ways to write a number as a sum. Because I had a pretty crazily high upper bound on my search (1000), this runs in .4s on my machine, searching only up to 100 gives a 4x speedup. Even though I haven't used PHP much, didn't have too many problems with Hack: main problems were a) it took something like 5 hours to install, b) Forget semicolons as I was moving from Python and Forth, and c) Of course I dropped some $'s, I personally think that if I were to make a "better PHP", the $'s would have been one of the first things I would have cut, it seems pretty clear from all the non-Perl, non-PHP languages out there that people generally don't want/need special characters to denote variables. (Also, no, that is not a typo, hack files begin with <?hh but have no closing >).
<?hh
function isPrime(int $x): int {
if ($x < 2) {
return false;
} else if ($x % 2 == 0) {
return $x == 2;
}
for ($i = 3; $i*$i <= $x; $i+=2) {
if ($x % $i == 0) {
return false;
}
}
return true;
}
$count = Vector<Vector<int>>{ } ;
$BOUND = 1000;
for ($i = 0; $i < $BOUND; $i++) {
$count[] = Vector<int>{};
for ($j = 0; $j < $BOUND; $j++) {
$count[$i][] = 0;
}
}
for ($i = 0; $i < $BOUND; $i++) {
for ($j = 0; $j < $BOUND; $j++) {
if ($i == 2 or ($j == 2 and $i % 2 == 0)) {
$count[$i][$j] = 1;
} else if ($i < 2 or $j < 2) {
$count[$i][$j] = 0;
} else if ($j >= $i) {
$count[$i][$j] = $count[$i][$i-1];
if (isPrime($i)) {
$count[$i][$j] += 1;
}
} else if (isPrime($j)) {
$count[$i][$j] = $count[$i - $j][$j] + $count[$i][$j - 1];
if ($count[$i][$j] > 5000) {
echo $i . "\n";
$i = $BOUND;
$j = $BOUND;
}
} else {
$count[$i][$j] = $count[$i][$j - 1];
}
}
}
Tuesday, March 25, 2014
Progress
Below is the table of my progress. It includes all of the languages that I have solved problems in, as well as which problem I solved in that language. Statements of the problems can be found at projecteuler.net, and all of the solutions are linked to from the table, in addition to being directly in posts on this blog.
| BrainFuck | 1* |
| Haskell | 2*,37 |
| J | 3*,24*,35* |
| J | 69*,72 |
| Ruby | 4*,40*,56 |
| Whenever | 2,5* |
| Ook! | 6* |
| Racket | 7*,26*,57 |
| K | 8*,30 |
| Javascript | 9*,31*,60 |
| sML | 10*,42 |
| PHP | 11 |
| Go | 12*,32 |
| cLisp | 13*,62 |
| C | 48*,50 |
| Fortran95 | 3,15* |
| Python | 16*,24*,39* |
| Python | 65*,66 |
| ELM | 17*,48 |
| Scala | 18*,44 |
| Perl | 19*,70 |
| Java | 20*,79 |
| FALSE | 4 |
| Squirrel | 21*,52*,55 |
| D | 22 |
| Ceylon | 23 |
| Postscript | 7 |
| Befunge | 27 |
Spring Break - Problem 76 in Forth
Yet again, a problem solved after a long hiatus: hopefully the distance between this solution and the next will be less than the distance between it and the previous, as I am now on a two-week long Spring Break, a perfect time to solve some Project Euler problems. Today, I used Forth, which I hadn't used since problem 9, and there I really only used it as a glorified postscript. This time around, I used some of the more interesting features of the language, like actually using data structures, in this case a big "two dimensional" (that was two hard, so its just a one dimensional and I convert indices between 1 and 2 dimensions) array which I use to solve the problem: We just covered Dynamic Programming in my Algorithms class, and Project Euler 76 happens to be a wonderful problem for Dynamic Programming. Now, the combination of the fact that the solution was found through dynamic programming and the fact that it is written in Forth may make the solution unintelligible to most looking at it, but oh well, and I will admit I had to work through the solution in Python before converting it over to Forth. Here is my solution, runs in about 80ms on my machine.
create count 101 101 * cells allot
: splitIndex { x } x 101 mod x 101 / ;
: makeIndex { i j } 101 j * i + ;
: test1 { i j } i 1 = j 1 = or ;
: test0 { i j } i 0 = j 0 = or ;
: testbig { i j } j i >= ;
: setArray { index value } value count index cells + ! ;
: getArray { index } count index cells + @ ;
: computeAns { i j } i j - j makeIndex getArray i j 1 -
makeIndex getArray + ;
: main 0 begin
dup splitIndex test1 if dup 1 setArray else
dup splitIndex test0 if dup 0 setArray else
dup splitIndex testbig if dup dup splitIndex drop dup 1 -
makeIndex getArray 1 + setArray else
dup dup splitIndex computeAns setArray then then then
1 + dup 101 101 * = until
100 99 makeIndex getArray CR . CR bye ;
main
Thursday, March 6, 2014
Long break due to school, but here is some Arnold
A friend of mine showed me a language called ArnoldC (https://github.com/lhartikk/ArnoldC). This wonderful language requires commands to be written in the language of Arnold Schwarzenegger quotes. Though it was a very fun language to work with, I have a slight confession regarding this problem, the program doesn't quite print out the answer. The problem asks for you to find a pythagorean triple (a,b,c) and the answer is then the product abc. The product abc is too large to store in ArnoldC's 16bit integers, so I just print the triple from this program and multiply on a calculator. I normal dislike intermediary answers, but this feels entirely sufficient - for what it's worth, it's less effort converting the answer this way than it was extracting the decimal answer from the brainF unary output I had a while ago. Despite needing to put up with Arnold, this solution is relatively fast - runs in .110s on my machine.
LISTEN TO ME VERY CAREFULLY sqrt I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE x GIVE THESE PEOPLE AIR HEY CHRISTMAS TREE prev YOU SET US UP 0 GET TO THE CHOPPER prev HERE IS MY INVITATION x HE HAD TO SPLIT 2 ENOUGH TALK HEY CHRISTMAS TREE current YOU SET US UP prev HEY CHRISTMAS TREE continue YOU SET US UP 1 HEY CHRISTMAS TREE result YOU SET US UP 1 HEY CHRISTMAS TREE diff YOU SET US UP 1 STICK AROUND continue GET TO THE CHOPPER prev HERE IS MY INVITATION current ENOUGH TALK GET TO THE CHOPPER current HERE IS MY INVITATION x HE HAD TO SPLIT current GET UP prev HE HAD TO SPLIT 2 ENOUGH TALK GET TO THE CHOPPER diff HERE IS MY INVITATION current GET DOWN prev ENOUGH TALK GET TO THE CHOPPER result HERE IS MY INVITATION diff YOU ARE NOT YOU YOU ARE ME 0 ENOUGH TALK BECAUSE I'M GOING TO SAY PLEASE result GET TO THE CHOPPER continue HERE IS MY INVITATION 0 ENOUGH TALK YOU HAVE NO RESPECT FOR LOGIC GET TO THE CHOPPER result HERE IS MY INVITATION diff YOU ARE NOT YOU YOU ARE ME 1 ENOUGH TALK BECAUSE I'M GOING TO SAY PLEASE result GET TO THE CHOPPER continue HERE IS MY INVITATION 0 ENOUGH TALK YOU HAVE NO RESPECT FOR LOGIC CHILL I'LL BE BACK current HASTA LA VISTA, BABY IT'S SHOWTIME HEY CHRISTMAS TREE a YOU SET US UP 2 HEY CHRISTMAS TREE b YOU SET US UP 7 HEY CHRISTMAS TREE a2 YOU SET US UP 0 HEY CHRISTMAS TREE b2 YOU SET US UP 0 HEY CHRISTMAS TREE c2 YOU SET US UP 0 HEY CHRISTMAS TREE c YOU SET US UP 0 HEY CHRISTMAS TREE t1 YOU SET US UP 0 HEY CHRISTMAS TREE t2 YOU SET US UP 0 HEY CHRISTMAS TREE result YOU SET US UP 1 HEY CHRISTMAS TREE always YOU SET US UP 1 STICK AROUND always STICK AROUND result GET TO THE CHOPPER a2 HERE IS MY INVITATION a YOU'RE FIRED a ENOUGH TALK GET TO THE CHOPPER b2 HERE IS MY INVITATION b YOU'RE FIRED b ENOUGH TALK GET TO THE CHOPPER c2 HERE IS MY INVITATION a2 GET UP b2 ENOUGH TALK GET YOUR ASS TO MARS c DO IT NOW sqrt c2 GET TO THE CHOPPER result HERE IS MY INVITATION c YOU'RE FIRED c YOU ARE NOT YOU YOU ARE ME c2 ENOUGH TALK BECAUSE I'M GOING TO SAY PLEASE result GET TO THE CHOPPER result HERE IS MY INVITATION a GET UP b GET UP c YOU ARE NOT YOU YOU ARE ME 1000 ENOUGH TALK BECAUSE I'M GOING TO SAY PLEASE result TALK TO THE HAND a TALK TO THE HAND b TALK TO THE HAND c GET TO THE CHOPPER always HERE IS MY INVITATION 0 ENOUGH TALK GET TO THE CHOPPER a HERE IS MY INVITATION 499 ENOUGH TALK YOU HAVE NO RESPECT FOR LOGIC YOU HAVE NO RESPECT FOR LOGIC GET TO THE CHOPPER a HERE IS MY INVITATION a GET UP 1 ENOUGH TALK GET TO THE CHOPPER result HERE IS MY INVITATION 500 LET OFF SOME STEAM BENNET a ENOUGH TALK CHILL GET TO THE CHOPPER a HERE IS MY INVITATION 1 ENOUGH TALK GET TO THE CHOPPER b HERE IS MY INVITATION b GET UP 1 ENOUGH TALK GET TO THE CHOPPER result HERE IS MY INVITATION 1 ENOUGH TALK CHILL YOU HAVE BEEN TERMINATED
Subscribe to:
Posts (Atom)