Otaku, Cedric's weblog

As one of the people decrying the profligate and inappropriate claim of 'not brute-force', let me state for the record that I wasn't including Bob's solution in my complaint, which was primarily directed at people that seemed to confuse typing time with runtime, and assumed that anything that was fast to type couldn't possibly be brute-force.

I think I've reached the stage in my coding career where I'm officially sick of 'elegance'. Yes, it's cute that you can write an algorithm in 60 characters because your language is so high level that all you're doing is gluing your standard library to itself. No, you can't check it into subversion, because it's impossible to comment, debug, and test.

Programmers tend to vastly overstate the importance of coding time, because that's the time that we spend. We often willfully ignore the fact that time spent writing code is dwarfed by time spent using it, and then reading it and debugging it, and then optimizing it. . by many orders of magnitude. So a syntax or coding style that shaves 50% off of your initial writing time, but adds 10% to your execution time, and 20% to your eventual test and debug time, 100% to the time it takes another developer to understand it (or 1000%, if it's perl) and 50% to any optimization time is enormously expensive over the lifetime of your software, and isn't even worth considering.

A few corrections regarding my OCaml solutions: they are all functional, there
was no imperative version to begin with, and the second version just used a
different functional set representation, making it nearly three times faster
than the initial one (which was as fast as Bob's first attempt). The latest
version is as fast as Bob's fastest one on my machine (Linux x86_64, Java
1.6.0_05-b12, 64-bit OCaml), 40% slower on his (OSX with 32-bit OCaml build?,
unknown JVM).

Here's a summary of the performance race :)
(The times from Bob's Java versions are without JVM startup and system time;
the overhead is over 100ms.)

crazybob.org/BeustSequence.java.html 680ms
eigenclass.org/hiki/ordered_permutations 640ms

crazybob.org/FastBeustSequence.java.html 269ms (doubly linked list)
eigenclass.org/misc/beust.ml 273ms (functional set with 2 lists)

crazybob.org/TestFastBeustSequence.java.html (avoid allocation)
207ms (Linux x86_64, Java 1.6.0_04-b12) / 150ms (OSX, unknown JVM)

eigenclass.org/misc/beust2.ml (expanded pattern matching)
217ms (Linux x86_64) / 237ms (OSX, 32-bit OCaml build)

I'm convinced the problem is a constraint problem with a solution similar to Peter Norvig's stunningly fast Sudoku solver.

But my brain hurts.

Hey Cedric,

could you let us know the story behind the challenge?

regards, David

There are a lot of intermediate complexities between brute force and closed form.

Brute force in this case here would be O(n) [I don't see how you could do worse than O(n) on such a problem] while a closed form would be O(1).

A solution that is not O(1) is not necessarily O(n)... Some people here are smoking some heavy crack.

A serious discussion should involve big-O, not simply "mine is brute force but less brute force than yours".

Ruby - version but it takes longer than 30 sec on my box.

def findDigits( used , value , ndigit , start , listener )
if ( ndigit == 1 )
start.upto(9) { |i| listener.hear( value + i ) unless used[i] }
else
start.upto(9) do |i|
unless( used[i] )
used[i] = true
findDigits(used,(value+i)*10 , ndigit-1, 0, listener);
used[i] = false
end
end
end
end

1.upto(10) do |x|
findDigits( {} , 0, x , 1 , TestListener.new )
end

C version - if I compile with -O3, it is faster than CrazyBob's Java version

#include
#include

void recurseMe( int* used, unsigned long value, int ndigit, int start )
{
int i = 0;
if ( ndigit == 1 )
{
for( i = start; i < 10 ; i++ )
if ( used[i] == 0 )
{
printf( "%lu\n", value + i );
}
}
else
{
for( i = start; i < 10; i++ )
{
if ( used[i] == 0 )
{
used[i] = 1;
recurseMe( used , (value+i) * 10, ndigit - 1, 0 );
used[i] = 0;
}
}
}
}

int main(char* arg)
{
int n = 1;
int used[10];
struct timeval start, end;
double dT = 0.0;

for( n = 0; n < 10; n++ )
used[n] = 0;

gettimeofday(&start, NULL);

for( n = 1; n <= 10; n++ )
recurseMe( used, 0l, n, 1);

gettimeofday(&end, NULL);

dT = ( end.tv_usec - start.tv_usec );

printf("time = %15.9lf miillseconds\n", dT);

return 0;
}

Here is a non-brute-force dynamic programming solution that counts integers that don't contain duplicate elements, in C#:

class UniqueDigits
{
private int[] m_limit;
private int[,,,] m_cache;

public UniqueDigits(long limit)
{
m_limit = new int[10];
for (int i = 0; limit > 0; i++)
{
m_limit[i] = (int)(limit % 10);
limit /= 10;
}

m_cache = new int[1 << 10, 10, 2, 2];
for (int i = 0; i < 1 << 10; i++) for (int j = 0; j < 10; j++)
for (int k = 0; k < 2; k++) for (int m = 0; m < 2; m++)
{
m_cache[i,j,k,m] = -1;
}
}

public int Compute()
{
return Compute(0, 9, true, false);
}

private int Compute(int taken, int pos, bool firstDigit, bool isLess)
{
if (pos < 0) return taken == 0 ? 0 : 1;
if (m_cache[taken, pos, firstDigit ? 1 : 0, isLess ? 1 : 0] >= 0) return m_cache[taken, pos, firstDigit ? 1 : 0, isLess ? 1 : 0];

int ans = 0;
for (int digit = 0; digit <= 9; digit++)
{
if ((taken & (1 << digit)) != 0) continue;
if (!isLess && digit > m_limit[pos]) break;

int newTaken = taken;
bool newFirstDigit = (digit == 0 && firstDigit);
if (!newFirstDigit) newTaken |= (1 << digit);

ans += Compute(newTaken, pos - 1, newFirstDigit, isLess || digit < m_limit[pos]);
}

return m_cache[taken, pos, firstDigit ? 1 : 0, isLess ? 1 : 0] = ans;
}
}
Here is a usage example:

Console.WriteLine(new UniqueDigits(9999999999L).Compute());

This prints "8877690", which I believe is the correct answer.

It runs in 4-7ms on my machine.

I am pretty sure that there is an efficient solution to the second half of the problem - the biggest jump. It seems like a nasty case-enumeration problem. I'll think a bit about it.

It was easy enough to do something faster than Bob's first attempt, but I don't see any way to beat his final solution.

(At least it wouldn't be anything measurable.)

Have fun,

here is my ugly attempt. It is very fast and does not seem to register a time using DataTime.Now as the metric. So sub millisecond or two.

using System;
using System.Collections.Generic;

namespace Challenge {

class Program {
public static List count( List inuse, int curVal, int maxvalue ) {
List ret = new List( );
curVal *= 10;
for( int n=0; n maxvalue ) {
break;
}
ret.Add( tmp );
inuse.Add( n );
ret.AddRange( count( new List( inuse ), tmp, maxvalue ) );
}
}
return ret;
}

public static List count( int maxvalue ) {
List inuse = new List( );
List ret = new List( );
for( int n=0; n maxvalue ) {
break;
}
ret.Add( n );
List newinuse = new List( inuse );
newinuse.Add( n );
ret.AddRange( count( new List( newinuse ), n, maxvalue ) );
}
return ret;
}

public static void Main(string[] args) {
DateTime start = DateTime.Now;
List ret = count( 10000 );
ret.Sort( );
int first = ret[0];
int second = ret[1];
int jumpsize = ret[1] - ret[0];
int tmp;
for( int n=2; n jumpsize ) {
jumpsize = tmp;
first = ret[n-1];
second = ret[n];
}
}
double secs = DateTime.Now.Subtract( start ).TotalMilliseconds;
Console.WriteLine( @"There where {0} items and the biggest jump was from {1}->{2} it was a jump of {3}", ret.Count, first, second, jumpsize );
Console.WriteLine( @"It took {0:F20} milliseconds to complete", secs );
Console.Write( @"Press any key to continue . . . " );
Console.ReadKey( true );
}
}
}

Just a follow up to my previous recursive solution. I let it go to 9876543210, which is obviously the largest number possible. Here are the results. Hopefully I didn't miss something and it is correct. It looks like it.

There where 5120 items and the biggest jump was from 8012345679->9012345678 it was a jump of 999999999
It took 0.00000000000000000000 milliseconds to complete

Darrell, there are a lot more than 5120 items if you let it go to that number, it looks like you are still counting up to 10000 and not 10^10.

Another follow up, it looks like the braces are not supported on the forum the types labeled List are all actually generic List's of type long.

@Darrell

> It took 0.00000000000000000000 milliseconds to complete

My version beat that;) Unfortunately I can't post it here because running the program can tear the very fabric of the universe (I still have a black hole where my CD player used to stand).

Ok, I ported Bob's to Common Lisp. I haven't done any performance metrics or anything yet. It feels slower than the Java version, but it still is probably under a second.

I did make a few performance enhancements to Bob's Java version though. You can find the details at

blog [-dot-] techhead [-dot-] B-I-Z
/2008/07/beust-coding-challenge.html

Sorry for the weird link. It was necessary. My TLD is being screened by the software for some reason.

A straightforward scala port of Bob's code performs about the same and is marginally shorter.

With just one iteration is is a bit slower, due to the extra load time for the scala-library jar. Over 100 iterations it takes 40 seconds to the Java versions 42 seconds.

I would expect that some kind of permutation generator working over an array of ints would be a bit faster than this approach, but it would be a bit excessive.

object BeustSeq {
trait Listener {
def hear(value: Long)
}

class Digit (var previous: Digit, val value: Int) {
var next: Digit = if (value max) return true
listener.hear(newValue)
}
else {
current.use()
val newHead = if (current == head) head.next else head

if (find(newHead, newHead, remaining - 1, newValue * 10, max, listener))
return true

current.yieldDigit()
}
current = current.next
}

return false;
}

def findAll(max: Long, listener: Listener) {
val zero = new Digit(null, 0);
val one = zero.next;

for (length <- 1 to 10) {
if (find(one, zero, length, 0, max, listener)) return;
}
}
}

Oh no, forgot my angle brackets. Hopefully this will work:

object BeustSeq {
trait Listener {
def hear(value: Long)
}

class Digit (var previous: Digit, val value: Int) {
var next: Digit = if (value < 9) new Digit(this, value + 1) else null

/** Removes digit from the set. */
def use() {
if (previous != null) previous.next = next
if (next != null) next.previous = previous
}

/** Puts digit back into the set. */
def yieldDigit() {
if (previous != null) previous.next = this;
if (next != null) next.previous = this;
}
}


def find(start: Digit, head: Digit, remaining: Int,
value: Long, max: Long, listener: Listener) : Boolean = {
var current = start

while (current != null) {
var newValue = value + current.value


if (remaining == 1) {
if (newValue > max) return true
listener.hear(newValue)
}
else {
current.use()
val newHead = if (current == head) head.next else head

if (find(newHead, newHead, remaining - 1, newValue * 10, max, listener))
return true

current.yieldDigit()
}
current = current.next
}

return false;
}
}
def findAll(max: Long, listener: Listener) {
val zero = new Digit(null, 0);
val one = zero.next;

for (length <- 1 to 10) {
if (find(one, zero, length, 0, max, listener)) return;
}
}
}

Bob's solution is indeed pretty elegant.

Came across my old TRS-80 model 100 this weekend. Seriously considering implementing it on that machine in it's old-as-hell basic language.

I don't think it has longs, so I'll probably have to implement integer string operations (addition and comparison) to make it work. Or I could use arrays where each entry represents--hmm, 32767 max IIRC--each array item could be 1-4 digits I guess, then I'd still need custom addition and compare algorithms as well as a display routine.

I expect it would be hideously slow, although Crazy Bob's algorithm should help a lot. I could use recursion I guess--although it should be just as easy to implement as loops.

sigh...

Ok, looks like nobody bothered to type the funny link to read my blog entry, so I'll just sum it up here. I was able to improve the performance of Bob's Java version by using a singly linked list, eliminating a few method calls and additional conditional statements within the loop and by using a Throwable to unwind the stack once the max is found.

The modified version can be found here:

code.google.com/p/blogcode/source/browse/trunk/BeustChallenge0708/src/beust/ModifiedBeustSequence.java

I also ported to Common Lisp which was a fairly easy task considering Lisp's native use of linked lists.

code.google.com/p/blogcode/source/browse/trunk/BeustChallenge0708/beust.lisp

Jonathan Hawkes's version converted to C looks like the faster so far:
codepad.org/6SW1RMQi

This older version of mine seems a bit slower, but it allows to set up the upper value too:
codepad.org/wlz2Vaqn

Last C version (from Jonathan Hawkes's version still):
codepad.org/BTnMQ8mz

A good algorithm is fast even with just Python + Psyco:
codepad.org/V8rzUSo2

I put my solution, which is in the category nor fast not concise, here: thecarefulprogrammer.blogspot.com/2008/07/cdric-beusts.html

I did not aim for performance, although I tried to avoid things I just would be bad like appending at the end of a list.

For me, it was simply an occasion to explore Scala and functional programming.

I'll stake my claim in the Java speed challenge, beating both Bob and Jonathan. Code at tobega.blogspot.com/2008/07/cedrics-coding-challenge.html

It uses a created object and its fields instead of passing a lot of values on the stack. Also uses a singly-linked list with a guard element.

I can knock about 3/4 of the time off of Bob's first version by noting that the largest non-repeating value is 1234567890 which fits in an int. Convert the code to only check up to this number at maximum, and use int everywhere rather than long.

Here's my improvement on Bob's original, which I measure at 14.6s for 100 10^10 executions vs 47.2s for the original. I'm sure this same improvement makes all the other algorithms improve similarly:
private static final long _maxNoRepeat = 1234567890L;
private static int _max;
private static final Listener _listener = new Listener();

public void testBobBeust() {
// findAll((long) 1200);
for (int i = 0; i _max) {
return true;
}
_listener.hear(value);
} else if (find(0, remaining - 1, value * 10, used | mask)) {
return true;
}
}
}
return false;
}

private static class Listener {
public void hear(int value) {
// System.out.println(value);
}
}

Sorry, didn't notice the code to html transformation doesn't work.

private static final long _maxNoRepeat = 1234567890L;

private static int _max;
private static final Listener _listener = new Listener();

public void testBobBeust() {
// findAll((long) 1200);
for (int i = 0; i < 100; i++) {

findAll((long) Math.pow(10, 10));

}
}

/**
* Finds all numbers in sequence up to max.
*
* @param max maximum sequence value
*/
public static void findAll(long max) {

_max = (int) Math.min(max, _maxNoRepeat);

for (int length = 1; length < 11; length++) {

if (find(1, length, 1, 0)) {

return;
}
}
}

/**
* Called recursively for each digit from most to least significant.
*
* @param first digit, 0 or 1
* @param remaining digits
* @param value so far
* @param used digit bitfield
* @return true if we reached max, false otherwise
*/

private static boolean find(int first, int remaining, int value, int used) {

for (int digit = first; digit < 10; digit++, value++) {

int mask = 1 << digit;
if ((used & mask) == 0) {

if (remaining == 1) {
if (value > _max) {

return true;
}
_listener.hear(value);

} else if (find(0, remaining - 1, value * 10, used | mask)) {

return true;
}
}
}
return false;

}

private static class Listener {
public void hear(int value) {

// System.out.println(value);
}
}

Doug, you're on to something good, except 9876543210 is the largest non-repeating value.

Of course I'm wrong. The number is 1023456789, which is lower than 1234567890.

Hi Cedric,

It was interesting trying to come up with a faster solution than the ones already posted. I've blogged about my experiences at www.indiangeek.net/2008/08/29/a-case-study-in-micro-optimization/ if you're interested.

s='0123456789'
all_vals=dict()
all_vals_array=[]
significant=''
incremented=''
total=0
max_val=10**5
while True:
left_over=[i for i in s if i not in significant]
for digit in left_over:
all_vals[incremented]=significant+digit
incremented=significant+digit
all_vals_array.append(incremented)
if incremented=='987654321':
break
if significant!='':
significant=all_vals[significant]
else:
significant='1'
print incremented
print len(all_vals_array)

Returns the 5611771 length array in about 10 seconds

Hopefully I don't make a fool of myself by posting something that is wrong, but here's my longer/faster JavaScript:

document.maximum = 10000000000; // 10^10
var max_bin = "";
var max_str = new String(document.maximum);
var max_len = max_str.length;
document.nums = "1234567890";
document.nums2 = "9876543210";
var nums = new Array();
document.used = new Array();

function clean(results){
  var filtered = new Array();
  filtered.push(0);
  results.sort(function(a,b){ return a-b;});
  for(i=0; i 0){
    bin = '0' + bin;
    morezeros--;
  }
  var newstr='';
  for(var i=0; i 0){
    bin = '0' + bin;
    morezeros--;
  }
  var newstr='';
  for(var i=0; i<=bin.length; i++){
    if(bin.charAt(i) == '1'){
      newstr = newstr + document.nums2.charAt(i);
    }
  }
  return +newstr;
}

var k=0;
while(k<max_len){
  max_bin += "1";
  k++;
}
var start = (new Date()).getTime();
var i = 0;
var ans;
var max_dec = parseInt(max_bin, 2);
var rev;
while(i<=max_dec){
  ans = pick(i.toString(2));
  nums.push(pick(i.toString(2)));
  nums.push(pickrev(i.toString(2)));
  i++;
}
nums = clean(nums);
var end = (new Date()).getTime();
alert((end - start) + " ms\nResults to follow");
document.body.innerHTML = nums.join(", ");

I've got to say, I'm not 100% sure what the requirements for this "challenge" are.

Anyway, here's a straightforward port to C of Bob's java code.

codepad.org/Pf4N5ojK

It runs in ~65ms on my machine.

The Erlang version that was posted looks more verbose (and
"frightening") than it needs to because it needlessly reimplements
some library functions, and intersperses test code (and dead code!)
with the important stuff (and because the indentation was stripped.
Here's a slightly modified version which I
hope is reasonably clear, and also runs more than twice as fast as the
original (because it uses the built-in functions).

-module(buest).
-export([challenge/1]).

unique_list([]) ->
____true;
unique_list([H|T]) ->
____case lists:member(H,T) of
________true ->
____________false;
________false ->
____________unique_list(T)
____end.

count(Upto, Upto, State) ->
____State;
count(From, Upto, State) ->
____case unique_list(integer_to_list(From)) of
________true ->
____________count(From + 1, Upto, finder(State,From));
________false ->
____________count(From + 1, Upto, State)
____end.

finder({RunStart,MaxGap,Counter},Element) when Element - RunStart >= MaxGap ->
____{Element,Element - RunStart,Counter + 1};
finder({_RunStart,MaxGap,Counter},Element) ->
____{Element,MaxGap,Counter + 1}.

challenge(Max) ->
____statistics(wall_clock),
____{_,BiggestJump,CountOfNumbers} = count(1,Max+1,{1,0,0}),
____{_, Elapsed} = statistics(wall_clock),
____io:format("~p ms elapsed to complete count to ~p~n", [Elapsed, Max]),
____{BiggestJump, CountOfNumbers}.

It's still much slower than the crazybob solution, because it's still a naive brute force implementation. Although it could be parallelized without too much trouble, there's not really any point because the algorithmic differences dwarf the small constant factor you might pick up from it.

My last one was completely wrong.
mrdamien.com/beust.html <- this one works.

Generates to 10^10 in 343,808 ms (slow, but much faster than the other JavaScript ones).

Computing the length of the list up to length k digits is trivially fast: for k digits, you can pick the first digits 9 ways (it can't be zero). The number of ways to pick the other digits is the number of permutations of the 9 remaining digits taken k-1 at a time. Call this function "bc".

The number of permutations of n elements taken r at a time is just (n-r+1)*(n-r)*...*n. Write this in Haskell as:

permutations n r = product [r+1 .. n]

Then we can write the bc function:

bc k = 9 * permutations 9 (k-1)

Finally, the total size of the list UP TO k digits is just the sum of the size for 1 digit, 2 digits, etc:

main = print (sum [bc k | k <- [1..4])