DZone shortest code to print first 30 fibonacci numbers without using numbers

There's interesting challenge on Dzone website. The task is to print Fibonacci sequence for first 30 numbers in the format "order: fib number". Once constraint is that you can't use any numbers in the code. Shortest answer wins.
My take on that problem in Ruby is here (85characters):

Code snippet - 30 fibonacci number without using numbers in ruby on Snipplr

[edit] During morning run I've realised that using array is just PITA and by getting rid of indexes for last and previous elements I can save some space (64 characters):

Code snippet - 30 fibonacci numbers without using numbers in Ruby on Snipplr

[edit] Since there was groovy solution with 64 characters I've shaved off another two getting down to 62.

Code snippet - 30 Fibonacci Numbers Without Using Numbers In Ruby(62) on Snipplr

Later when I read discussion they have dropped requirement to use : in the output so I decided to update solution and found another nifty trick to get rid of another two characters ending up at 58(60) chars which can be easily reduced to 57 by removing whitespace after p.

Code snippet - 30 Fibonacci Numbers Without Using Numbers In Ruby(58) on Snipplr

Java puzzler - Letter went missing

Recently I've implemented function that takes String and populates long so that it contains character values from the back of the string. However my unit test is failing because one Letter is missing. Are you able to put it to the right place so that unit tests will not fail without debugging the code?

import static org.junit.Assert.*;
import org.junit.Test;

public class StringToolsTest {

	static final char [] data = {0xca, 0xfe, 0xeb, 0xab, 0xee};
	static final String string5 = String.valueOf(data);
	static final String string0 = "";
	static final String string1 = "a";
	static final String string9 = "987654321";
	
	@Test
	public void testFillBackwards() {
		long l = 0;
		assertEquals(0xcafeebabeeL, StringTools.fillBackwards(string5, l));
		assertEquals(0L, StringTools.fillBackwards(string0, l));
		assertEquals(0x61L, StringTools.fillBackwards(string1, l));
		assertEquals(0x3837363534333231L, StringTools.fillBackwards(string9, l));
	}
}

public class StringTools {
	public static long fillBackwards(String s, long d)
	{
		long result = 0L;
		byte[] bytes = s.getBytes();
		for (int i=0; i<Math.min(8,bytes.length); i++){
			result |= ((bytes[bytes.length-i-1] & 0xff) << (8*i));
		}
		return result;
	}
}

Solution bellow (highlight to show):

The problem is on the line 29 in "& 0xFF". I should be doing &0xFFL instead. Why ? bytes[x]&0xff is by default int (both operands are widened to int), but then << is applied, result of which is type of left operand (java spec) and this is |= to long result. Solution is to make & operator to work on long values by adding L to 0xFF.

Puzzler on snipplr.

Question Interview

One of my friends got this question on his interview: "Given is an arbitrary long string, revert order of words in the string". If the input is "Hello World!", function should modify string to: "World! Hello". Function must have this interface: "void revert(char * string)". It must work in linear time O(n) and have no special memory requirements M(1).

My solution (spoiler alert)

Java puzzler - How many integers are in the box ?

This is most basis Java Puzzler. Question is, how will the output look like ?

• Will it print out powers of 10 starting from 1 ending at 10000000.
• Or will it print just 1.
• Or will it print any other number.
• Or will it loop forever.
• Or anything else.

package sk.adino.puzzlers;

import static org.junit.Assert.*;
import org.junit.Test;

public class AutoboxingTest {

	@Test
	public void test() {
		int i=1;
		while(i<10000000) {
			System.out.println("value:" + i);
			Integer j=i;
			Integer k=i;
			if (j==k){
				i=i*10;
			}else break;
		}
		assertEquals(i,1000);
	}
}

Puzzler @ Snipplr

Puzzler for C developer role

Today, I've created puzzler for C developer at company I work for. This is one of rare cases where we can publish the code, and it's few lines anyhow, so here I give it a shot. You can try to solve the puzzler, as described in comments. It's very easy and you should have no problem solving it without Solaris. All you need is a C compiler.

Bonus question: why did I choose (R) and (C) instead of R and C ?

Bellow is the code which you can find also on snipplr:

1. /** This program should be compiled using following command:
3.  $ cc -g -o test_hr_test test_hr_test.c
5.  Original developer Malvin left company to pursue his dream and went
6.  to live with wild ligers. No-one ever heard any word about him since
7.  he left. We've managed to recover source code from his source repo.,
8.  but program seems to be broken. Strangely Malvin used iso-8859-1 as
9.  his console encoding.
11.  Hints:
12.  - program does not compile
13.  - we were not able to recover whole function permutateBlockRev()
14.  - program crashes on our X86 solaris 10 matchine (not on linux)
16.  Are you the one which can help us recover the password ?
17.  Send it to: rpc-hr@ri-rpc.sk
18.  */
20. #include <stdio.h>
21. #include <string.h>
23. /** bit manipulation macros */
24. #define CLRBIT( STR, IDX ) ( (STR)[(IDX)/8] &= ~(0x01 << (7 - ((IDX)%8))) )
25. #define SETBIT( STR, IDX ) ( (STR)[(IDX)/8] |= (0x01 << (7 - ((IDX)%8))) )
26. #define GETBIT( STR, IDX ) (( ((STR)[(IDX)/8]) >> (7 - ((IDX)%8)) ) & 0x01)
28. /** permutation works on unsigned char blocks of size 8 */
29. #define BLOCK_SIZE 8
30. typedef unsigned char[BLOCK_SIZE] block;
32. /** Function does reverse permutation to DES initial block permutation as described at
33.  http://en.wikipedia.org/wiki/DES_supplementary_material
34.  @param b - block which will be permutated in-place
35.  @note indexes start from 0 contrary to wikipedia initialization vector - C like index
36.  */
37. void permutateBlockRev(block b)
38. {
39. int i;
40. static const int initialPermuteMap[64] =
41. {
42. 57, 49, 41, 33, 25, 17, 9, 1,
43. 59, 51, 43, 35, 27, 19, 11, 3,
44. 61, 53, 45, 37, 29, 21, 13, 5,
45. 63, 55, 47, 39, 31, 23, 15, 7,
46. 56, 48, 40, 32, 24, 16, 8, 0,
47. 58, 50, 42, 34, 26, 18, 10, 2,
48. 60, 52, 44, 36, 28, 20, 12, 4,
49. 62, 54, 46, 38, 30, 22, 14, 6
50. };
52. /* There are few lines of code missing */
53. }
55. int main (void)
56. {
57. unsigned char str[BLOCK_SIZE + 1] = "DummyStr";
58. block permutated = { 0x7a, 0xd2, 0x21, 0x3c, 0x05, 0x85, 0x8d, 0x71 };
60. permutateBlockRev(permutated);
61. strcpy(str, permutated);
62. printf("Password is: %s\n", str);
63. }

C/C++ puzzler #2 - Is it typo ?

Ok, here is next C/C++ specific puzzler. Puzzler here is to guess, what will be result of program ?

1. It won't compile


2. It will compile, but it will segfault when we try to run it


3. It will run and print 4 times 30


4. Anything else you can think of

Highlight text bellow code to find out correct answer.

/* compile with cc -g -o test_typedef_sizeof test_typedef_sizeof.c */
#include <stdio.h>
#include <string.h>

typedef char name_t[30];

void fn(name_t value)
{
    printf("%d\n", sizeof(name_t));
    printf("%d\n", sizeof(value));
}

int main (void)
{
    name_t aa;

    printf("%d\n", sizeof(name_t));
    printf("%d\n", sizeof(aa));

    fn(aa);
    return 0;
}

I'll just show you program output:

30
30
30
4

Is it not, what you have expected ? Fine, let's walk the program together. On entry to main() program prints sizeof(user defined type name_t), which has length of 30 chars. Next it'll print sizeof(instance of name_t) which again is 30 chars long. Then it calls function fn(instance of name_t), In fn() it prints sizeof(user defined type name_t) which is again 30 bytes. But when it tries to print sizeof(value) it prints 4, because arrays are passed as reference to first element in C/C++. And the sizeof(pointer) is 4 respectively 8 for 64 bit system.

C/C++ puzzler #1 - Where do you want to go today ?

First puzzler is in C/C++ and it is based on puzzler found in book Java Puzzlers by Neal Gafter and Joshua Bloch.
Problem:
We have following C program:

/* compile with: cc -g -o test_xxx test_xxx.c */
#include <stdio.h>
#include <stdlib.h>

int main (void)
{
printf("firefox.exe");
http://www.google.com;
printf(":new\n");
exit(0);
}

Options:
What will the program do:
a) print firefox.exe
b) run firefox.exe open http://www.google.com in new tab
c) fail to compile
d) other


Solution: (highlight to see)

First look at source, and you probably think that this couldn't compile. In fact it does. Real puzzler is, why does it compile. Problem seems to be in line http://www.google.com; But let's take a closer look. Is it problem ? It compile because of long forgotten feature of C, which is labels. (Except for kernel source, you'll find plenty of labels there ;) What compiler see is label http: followed by comment //www.google.com;

Puzzlers series

I guess everyone have been in situation when he/she has written code, which didn't behave as it should. Most of these times, problem was of PEBKAC (problem exists between keyboard and chair) type. Computers (nearly) always do, what they're told to do. Under influence of Java Puzzlers book by Neal Gafter and Joshua Bloch, I've decided to start series of posts to this blog, which would cover situations when program doesn't do what we think it should. At first posts will be mostly in C/C++, but i think more languages will be covered in the future. Posts will be formated, so that you'll see only problem with possible answers. Solution will have font color set to background color, or some close color, so you'd have to highlight block in order to see it. You're more than welcome to add your own puzzlers. Just contact me.