Tsuchiya Yoshihiro Blog

Project euler memo: Problem 324

2012-01-20T21:11:00.000+09:00

Problem 324: Filling a very high tower (3x3x10^10000) with blocks (1x1x2). I first tried with something similar to problem 161. I found the correct, but it took too long to finish 10^1000: 4 hours with C++. I need to read the forum.
-----
(update) With a minor change, it takes 2 hours now.

Project euler memo: Problem 258

2012-01-09T17:36:00.000+09:00

Problem 258: Lagged Fibonacci sequence. I heard that it is used to generate random number sequences. It is also written that it has a long cycle, but I am not sure how long for the parameter of this problem. I had been trying to solve this problem in several wrong ways, but finally I got closer yesterday, but my implementation was very slow. From very early morning today, I had run my code four or five times in 3 hour interval, and got wrong answers. Finally I found a way with 30 minutes in C++ and a correct answer.

Project euler memo: Problem 365

2012-01-03T00:13:00.000+09:00

Problem 365: 'A huge binomial coefficient". I am glad that I finished this problem. Four and half minutes in Python. Also I am 100th person for this problem. Nice number for the new year. The message from Euler:

-----

Congratulations, the answer you gave to problem 365 is correct.

You are the 100th person to have solved this problem.

Nice work, tsuchiya.yoshihiro, you've just advanced to Level 13.
133 members (0.07%) have made it this far.

You have earned 1 new award:

High Flyer: Progress to the maximum level

Project euler memo: Problem 363

2011-12-23T00:59:00.001+09:00

Problem 363: Bézier curve. An easy problem. One and half minutes in Python.

Project euler memo: Problem 362

2011-12-18T11:24:00.001+09:00

Problem 362: Counting the number of square free factorization. I am the 50th person who solved this problem and this is the first time for me to get in to a fast solver list. It has been about a week since after the problem was published. Two minutes in C++.

Project euler memo: Problem 181

2011-11-24T18:59:00.001+09:00

Problem 181: Creating groups in Black and White objects. I took a simple method, however there was a bug to produce a dictionary ordered sequence. Thee minutes in Python.

Project euler memo: Problem 359

2011-11-21T23:02:00.001+09:00

Problem 359: Hilbert's infinite hotel. I do not like this non-natural way of introduction of the problem. First, I wrote a brute force. I do not quite understand why, but looking at the numbers, I found something and wrote a program in Python. 0.04 sec in Python.

Project euler memo: Problem 358

2011-11-19T13:27:00.001+09:00

Problem 358: After coming back from Munich, I finally recovered from jet lag. The problem is on the cyclic number. This is not very hard, but interesting. 14 minutes in Python. Is there any way to speed that up?

Project euler memo: Problem 357

2011-11-06T11:35:00.000+09:00

Problem 357: For a divisor d of n, check if d+d/n is prime or not. Very easy and I brute forced it. It was about 30 minutes in Python. I am at the Narita airport, and I am heading to Munich.

Project euler memo: Problem 161

2011-11-01T20:18:00.001+09:00

Problem 161: Tetris kind of annoying picture. Tiling with triominos. I wanted solve this problem but I could not. I ended up with the dynamic programming. 1.3 minutes with C++.

Project euler memo: Problem 198

2011-10-25T21:02:00.002+09:00

Problem 198: A difficult problem. It was difficult to understand what this problem was asking. I read the forum (http://forum.projecteuler.net) and I learned that I was not the only one. It took 16 minutes in Python. It was necessary to avoid recursion.

Project euler. My friend key

2011-10-23T22:58:00.001+09:00

My friend key:
2684377928646_d1bcc4e5535f98ee658c519b54cfe3a9

Project euler memo: Problem 353

2011-10-11T20:56:00.000+09:00

Problem 353: Finding a min-cost path on a sphere. The first problem was to find the points on the sphere and the second one was to find the path. The second one was hard for me before I found a trick to make it easy. Nine minutes with Python.

FizzBuzz

2011-10-08T10:52:00.000+09:00

FizzBuzz is a problem for programmers. "Print out numbers from 1 to 100. If a number is divisible by 15, print 'FizzBuzz' instead. If a number is divisible by 5, print 'Buzz'. If divisible by 3, print 'Fizz'." Sounds easy, and I would write:

def fizzbuzz():
for x in xrange(1,101):
if x%15 == 0: print "FizzBuzz"
elif x%5 == 0: print "Buzz"
elif x%3 == 0: print "Fizz"
else: print x

It's in Python and it's style is procedural. Some people interpret this problem to write very short and tricky code. I searched some on the internet, and honestly I need to say some of them are not understandable for me. The most impressive one is the following.

def fizzbuzz_short():
for i in range(1,101):print"Fizz"*(i%3<1)+"Buzz"*(i%5<1)or i

The original is here. Enjoy to see what it does.

I also found Lisp version of answer. With Lisp, you can program just like I did in a procedural way. However you may have a different idea. Think about a list of numbers (1,...,100). You modify the values depending on its value. Since I am not a Lisp programmer, I wrote it in Python.

def fizzbuzz_map():
for k in map(lambda x: x%15 == 0 and "FizzBuzz" or \
x%5 == 0 and "Buzz" or \
x%3 == 0 and "Fizz" or \
x, range(1,101)):
print k

I used map() function to modify the list. This is functional rather than procedural. Isn't it interesting? Just wanted to share these ideas.

How to cancel a purchase from Kindle book store

2011-10-07T22:22:00.001+09:00

I bought a Kindle book and later I noticed that it is a wrong book. The title of the two books are very similar and they are written by the same author. The only difference is that the one I want has two more characters: "++" in its title. I sent a message to Amazon from 'Your account > Manage your Kindle > Kindle Help (there is an button at the right) > Contact us > Contact Kindle support > Kindle customer service". Shortly, they wrote me back that they had canceled the order and they would refund the money. I was impressed by this service. The following is what they said:

You can request a refund for items purchased from the Kindle Store within seven days of purchase.

You can also cancel accidental purchases yourself for a short time after the order is placed.

Simply select the "Purchased by Accident? Cancel this Order" option on the order confirmation

page displayed on your Kindle.

Project euler memo: problem 314

2011-09-27T20:06:00.002+09:00

Problem 314: The mouse on the moon. Maximizing the area/perimeter ratio. Very hard one. I first thought that the shape should be a circle. Actually it is not.

It seems that the anecdote of this problem is based on the story of Dido of Carthage. Also its title 'The mouse on the moon' came from a movie; I do not know why they took it. Probably I should see the movie.

About 30 seconds in Python.

Project euler: new interface

2011-09-25T13:33:00.000+09:00

Project euler memo: Problem 351

2011-09-18T23:03:00.001+09:00

Problem 351: The number of unseen points from O in a hexagon. Very easy problem even after two bottles of beer and a half bottle of wine. 12 seconds in C.

Project euler memo

2011-09-10T17:12:00.000+09:00

I finished the bunch of easy problems, the ones after the summer break. So now, I have finished 313 problems and I have 36 problems to go.

161,163,181,194,198,236,237,241,248,254,258,269,270,275,280,282,289,292,298,300,305,311,314,316,319,322,324,325,328,330,331,334,337,338,339,344

Project euler memo: Problem 349

2011-09-10T16:55:00.000+09:00

Problem 349: Langton's ant. If you look at the wikipedia article on this ant, this is very easy.

Project euler memo: Problem 345

2011-09-06T20:33:00.000+09:00

Problem 345: The largest sum of numbers in a matrix. One of the recent five easy problems. 0.5 sec in Python and 0.02 sec in C++.

Project euler memo: Problem 346, 347, 348

2011-09-04T17:44:00.001+09:00

Celebrating beginning of the new season, they gave us five problems at once, 345-349.

Problem 346: Repunit. Five seconds in Python.
Problem 347: Numbers only divisible by two prime numbers. Three and half minutes in Python.
Problem 348: Palindrome numbers that can be expressed as a sum of a square and a cube in exactly four ways. One minute in Python. But first I put the answer in the box, it was a wrong answer, then I tried to find a bug in my code, but I could not. Four hours later, now, I put the same answer again in the box, it said that it was collect! What was wrong ?

Project euler memo: Problem 262

2011-08-06T00:07:00.003+09:00

Problem 262: A fly flies around a mountain. I do not feel like I have solved this problem. I divided the area like mesh, and when I change the size of the mesh, the precision, it would give slightly different answer. Five minutes with python.

This is the first problem I solved after I bought a new Macbook Air(core i7) . I tried some problems, I recently solved, to check its speed, but I could not see a big difference with the three year old Macbook(core 2 duo). The Macbook Air looks very fast with its flash based disk and graphics, but it is nothing to do with the speed of the CPUs. So I do not have to care about the difference of my machines in terms of Project Euler.

-----
(update 8/6/2011)
I changed the mesh value much bigger, and now it returns a nice value, though it takes much longer. 20 minutes. But I feel much better.

Project euler memo: Problem 279

2011-07-25T19:18:00.002+09:00

Problem 279: Triangles with integer sides with at least one integer angle. First, I tried to use cos and sin to find out angles and lengths. I noticed that I could not do that because of numerical error. Then I chose a different approach. One minute with C++.

Project euler memo: Problem 341

2011-07-21T22:36:00.002+09:00

Problem 341: Golomb's self-describing sequence. It's not very hard and very interesting. One minute with Python. "Concrete Mathematics" helped me, actually.

I didn't know that Solomon W. Golomb invented pentominoes.