Refactoring approach story

I have a feeling that everyone is omitting the shit. Or maybe they just not shout when they found it . Every time we find shit we need to shout - it makes others pay attention to it and stare at it for a while. It may happen that is was actually not a shit, but a similar looking pile painted in brown for some very important reason. Then maybe someone who made it can explain his/her intentions. Otherwise it should be cleaned as a regular shit.

Points are not given by stepping over the shit, only by cleaning it and being sure that some other shit was not dependent on it. If you think its faster to just run and jumping over all the piles than I asure you that you will find yourself in the air with a scary face expression, anticipating the fall into so cold 'deep shit' or 'big browny'. Jumping is allowed only when shit is not ours, or we cannot clean it. 'Cannot' refers only to a situation when the shit is not ours.

If you can't recognize the shit by how it looks, you need to smell it. If you are not sure of the smell you can ask others and then we will smell it together. It's always better than omitting it. To make yourself able to distinguish the shit from a not shit you need to be sometimes in the shit-free places. And learn how it is not to smell it. Otherwise you can just get used to it.

filet gem just released!

We finally found some time to finish the work on the gem for acceptance testing - filet. It's available via our employer github account: https://github.com/xing/filet

filet is a dsl for acceptance testing on top of Test::Unit.

Hope you'll find it useful!

How to re-implement a cartesian product algorithm

Yes. So did I waste my time, or not? Of course not. I just got a big slap in my programming face. Un pollazo. I over-implemented a cartesian product, without even noticing it. But it's fantastic, I can learn every day :)
I was even showing it around to my friends at work. They didn't notice too! Maybe this algorithm could be used for something else. But I have no fucking clue where :D
Of course I learned a lot, but still, feel a bit stupid. Do not overdo and read more - that is the lesson of today!

	def cartprod(*args)
	result = [[]]
	while [] != args
	t, result = result, []
	b, *args = args
	t.each do |a|
	b.each do |n|
	result << a + [n]
	end
	end
	end
	result
	end
	# Posted here http://www.ruby-forum.com/topic/95519

view raw fast_cartesian_product.rb hosted with ❤ by GitHub

Ou programming... my dear...

Fast! iterative algorithm for generating permutations from sets' single elements

I like it. I like this one. Last algorithm for this problem (here) was O(n^3). Now it's O(n). It may mean two things: first one was very shitty, or that the second one is really good. Probably both are true.

I came back home, without a laptop. With one hand holding the Algorithms book (I really recommend that one) and with notebook and a pen in the other. I choose notebook and pen. It did the trick.

I know I masturbate on that issue, but it's fun. After some furious paper programming I got here:


I asked myself 3 questions at the beginning:

1. How many times "1" will be first?
2. How many times "4" will be in the result?
3. How many times "5" will be in the result?"

I wanted to answer that questions without the use of any offset indexes kept in memory in other array. Keep it simple: what do I know about my input data?
So my answers were like that:

1. If I take all the sizes of following tables and multiply them, I'll get 12.
2. Always, cause it's a single element array, so 36 (total possible permutations.
3. The same as answer number one. 6 times in cycle of 3, 18.

The main conclusion was that I can fill the results array column by column instead of row by row. All permutations will be fully calculated at once, at the very end. No gathering the permutation by permutation and then pushing it to the results. No no no, that needs indexes and traveling across the array many times. This idea dropped the complexity from O(n^3) to O(n).

Cycles, subcycles, offsets. The most important thing was to calculate a proper index in the result table and stick the current argument element exactly there (IBID). No more talk, code is below and benchmark is on the gist comment.

	def permute(*args)
	# filter the arguments
	args.reject! {|x| !x.is_a?(Array) || x.empty?}
	# get the number of all combinations
	total = args.inject(1) {|total, array| total * array.size}
	# prepare the small_cycles array to know how many times
	# one element should be repeated in a loop
	small_cycle = total
	small_cycles = []
	# small cycle depends on the size of arrays are after the current array
	args.each do |array|
	small_cycle = small_cycle/array.size
	# if the array has only one element it should be everywhere
	if array.size == 1
	small_cycles << total
	else
	small_cycles << small_cycle
	end
	end
	# prepare the results table
	result = []
	(args.size).times do |i|
	array_size = args[i].size
	repeat_counter = if (i==0) || (array_size==1) then
	1
	else
	total/(small_cycles[i]*array_size)
	end
	(repeat_counter).times do |j|
	args[i].each_with_index do |element, index|
	(small_cycles[i]).times do |k|
	# calculate an index in the result array
	rindex = (j*small_cycles[i]*array_size)+(index*small_cycles[i])+k
	result[rindex] ||= []
	result[rindex] << element
	end
	end
	end
	end
	result
	end
	# output for: permute([1,2,3], ['X'], [4,5])
	# [[1, "X", 4], [1, "X", 5], [2, "X", 4], [2, "X", 5], [3, "X", 4], [3, "X", 5]]

view raw fast_permute_sets.rb hosted with ❤ by GitHub

Iterative algorithm for generating permutations from sets' single elements

My friend asked on facebook for a iterative algorihm that would generate all possible strings from given sets in a way that for ex. given {a,b,c}, {d,e}, {f} should produce {adf, aef, bdf, bef, cdf, cef}.

	def permute(*args)
	# initialize the register for each array
	# with [array itself, offset, its size]
	memory = []
	perm_count = 1
	args.each do |array|
	size = array.size
	memory << [array, 0, size-1]
	# get the number of all combinations
	perm_count *= size
	end
	# remember the memory size
	msize = memory.size
	result = []
	# for every possible permutation
	perm_count.times do |i|
	# prepare empty array and bumped flag
	permutation = []
	bumped = false
	# iterate over subsets
	msize.times do |j|
	# get element with a registered offset
	permutation.push(memory[j][0][memory[j][1]])
	# if no offset was bumped yet, bump one
	unless bumped
	# the current one
	if memory[j][1] < memory[j][2]
	memory[j][1] += 1
	bumped = true
	else
	# or any next possible one that will not overflow yet
	# and set the current offset to 0
	memory[j][1] = 0
	bump_next(memory, j)
	bumped = true
	end
	end
	end
	# save the permutation to the results array
	result << permutation.join
	end
	result
	end
	# finiding the one that can be bumped
	def bump_next(memory, j)
	n = j+1
	unless memory[n].nil?
	unless full?(memory[n])
	memory[n][1] += 1
	else
	memory[n][1] = 0
	bump_next(memory, n)
	end
	end
	end
	# check if the offset doesn't overflow
	def full?(array)
	array[1]==array[2]
	end

view raw permset.rb hosted with ❤ by GitHub

There is still a recursive call moved to bump_next method. I'm trying to get rid of that one and make it fully iterative.
That was much fun doing it, as it has some tricky parts. Probably faster algorithm for that already exists, but I couldn't find any. Lots of fun.