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.

Friday, January 23, 2015

Project Euler memo: Problem 497

Problem 497: Drunken Tower of Hanoi. Relatively easy. 24 minutes in Python.

Monday, January 12, 2015

Project Euler memo: Problem 435

Problem 435: Fibonacci coefficient  polynomials. Straightforward computation of Fibonacci numbers with a little trick on modulo inverse. Less than 0.1 seconds in Python.

Sunday, January 11, 2015

Project Euler memo: Problem 430

Problem 430: Flipping discs. A kind of brute force on N. 10 minutes in Golang. I need to learn in the forum later.