Saturday, June 03, 2017

Project euler memo: Problem 516

Problem 516: A kind of easy, but some problems with the new language: Haskell. 40 seconds in Haskell. I was able to access with my original ID.

 26 seconds with -O2 option for ghc.

Monday, February 27, 2017

Project euler memo: redoing with new ID

Just a week ago, I was able to sing in to Project Euler and I solved one. Then I went there again, and I  cannot sign in again. My browser caches my password, that's not because I am typing wrong password.

Anyway, I set up a new ID and started redoing the problems with it. This time, I am using Haskell from the beginning. I have finished first 10 problems. My new sticker is the one below.

Friday, February 17, 2017

Project euler memo: Problem 587

Problem 587: Yesterday I got a comment from pipilu in this blog that I have been away from Project euler for a long time. I was thinking that my account was locked, but I was able to sign in today. It seems it is about one year and half since last time I solved one and they added about 70 problems.

Anyway I chose one that looks easiest from the latest problems. It is easy.

Tuesday, July 05, 2016

bubble sort and its animation

When somebody was talking about bubble sort, I needed to check wikipedia to see what that is :-) and I understood the algorithm.

The algorithm move a value from the left to the right until it finds a proper position, then it goes back to the next value to repeat the same thing.

The algorithm is pretty procedural, how should I write a functional code for this algorithm? My solution in Python is the following.

Knowing that the right most value is fixed after each scan() and scan() does the inner loop in the first code. So bubble() does bubble() for smaller subset in it.

I rewrote the Python code in Haskell.

This is not a algorithmic interest but something impressed me very much was the animation in the wikipedia article.


I wanted to do this myself, so I used matplotlib to that by googling everywhere.
The algorithm for bubble sort is in gen_points() which is a procedural one.

There are 100 random values. X-axis indicates their positions and Y-axis indicates their values.

I uploaded the animation to youtube, which is the first video I published.

Sunday, September 06, 2015

Project euler memo: Problem 510

Problem 510: Easy. 1.5 min in Golang.

Friday, August 14, 2015

Memory size with Golang

In the previous post, I complained on the slowness of Golang. It seems that it is because that I requested more memory than the machine has. In the following snippet, by default, 's' is zero-initialized and the program should print only the size of memory, in this case:

memory size is 4000000000

But if the length of array is 500*10^6, the program finds lots of non-zero elements. If the length is one tenth, i.e. 50*10^6, there is no problem. Since my machine is a Macbook air with 4GB DRAM, now I am thinking that Golang has some problem with memory size, but not very sure.

(Update 8/17/2015) This happens the array size is over 2GB.  There is a discussion here.

package main

import (

var s [500000000] int

func main () {
  mx := 500000000

  fmt.Println("memory size is", unsafe.Sizeof(s))
  for i:=0; i< mx; i+=1 {
    if s[i] != 0 {

Project euler memo: Problem 512

Problem 512: Counting the sum of Euler's totient. Basically I did brute-force. At first I tried to do it in  Golang, but it took forever to initialize a prime sieve. Then I did the same thing in C++ and it just takes 40 seconds. Up until 1/10 of the size, Golang does it fast enough.


Congratulations, the answer you gave to problem 512 is correct.
You are the 503rd person to have solved this problem.

Sunday, August 09, 2015

Project euler memo: problem 504

Problem 504:  Counting the number of lattice points in rectangles. It's been 7 months since last time I solved a problem. I chose the easiest problem by difficulty rate. Simple brute force in Python. 5 minutes.
(update 8/12)
I re-wrote it in Golang, including the suggestions in the forum. Now it runs in 1.2 seconds.

Saturday, April 25, 2015

Binary search on an array

I read a conference paper lately that has a pseudo code. In the code, there was a binary search and I noticed that the algorithm does not stop. That part in the paper is not very important but I myself confused at first, so I make it clear. 

I took a look at Knuth's TAOCP and I translated the description into Python:

# search key between [l,u]
# returns -1 on failure
def search1(key, arr):
  l = 0
  u = len(arr)-1

  while l<=u:
    m = (l+u)/2
    if arr[m] == key:
      return m
    elif arr[m] > key:
      u = m-1
      l = m+1
  return -1

This is simple and it has the case for failure.

What happens if the upper limit is an open end? I re-wrote it in this way.

# search key between [l,u)
# you need to be sure that you have an answer in arr
def search2(key,arr):
  l = 0
  u = len(arr)

  while l+1<u:
    m = (l+u)/2
    if arr[m] > key:
      u = m
      l = m
  return l

It does not have the case for failure so you need to be careful when you call it. There is a trick to compare l and u this case.

The algorithm in the paper is a mix of these and it does not stop. 

Sunday, January 25, 2015

Project Euler memo: Problem 443

Problem 443: GCD sequence. It's interesting and hard. I don't like it. One minute in Python.