Maths Puzzle

[tribbles]

Alex said:

OK, we know the answer. Let's change this to a coding challenge!

I propose the following categories:

• Most elegant
• Shortest
• Fastest
• Daftest

You can use any language. I'll have a go myself.

No doubt some LISP expert will come along with a single line solution...

Damn - maybe I shouldn't have posted my answer then

We used to do this kind of thing at school: set a programming challenge and see who can do the best job. Although we only looked at fastest and shortest.

[tribbles]

Okay - here it is with some extra optimisations (I spotted that the 4th and 8th digits could be improved).

DateTime start = DateTime.Now;
int count = 0;

for (int a = 1; a < 10; a++)
{
for (int b = 0; b < 10; b += 2)
{
if (a == b)
continue;

for (int c = 0; c < 10; c++)
{
if ((c == a) || (c == b))
continue;
if (((a + b + c) % 3) != 0)
continue;

for (int d = (c & 1) << 1; d < 10; d += 4)
{
if ((d == a) || (d == b) || (d == c))
continue;

for (int e = 0; e < 10; e += 5)
{
if ((e == a) || (e == b) || (e == c) || (e == d))
continue;

for (int f = 0; f < 10; f += 2)
{
if ((f == a) || (f == b) || (f == c) || (f == d) || (f == e))
continue;

if (((a + b + c + d + e + f) % 3) != 0)
continue;

for (int g = 0; g < 10; g++)
{
if ((g == a) || (g == b) || (g == c) || (g == d) || (g == e) || (g == f))
continue;
if (((a * 1000000 + b * 100000 + c * 10000 + d * 1000 + e * 100 + f * 10 + g) % 7) != 0)
continue;

for (int h = 10 - (((g & 3) + 1) << 1); h >= 0; h -= 8)
{
if ((h == a) || (h == b) || (h == c) || (h == d) || (h == e) || (h == f) || (h == g))
continue;

for (int i = 0; i < 10; i++)
{
if ((i == a) || (i == b) || (i == c) || (i == d) || (i == e) || (i == f) || (i == g) || (i == h))
continue;
if (((a + b + c + d + e + f + g + h + i) % 9) != 0)
continue;

Console.WriteLine(string.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}", a, b, c, d, e, f, g, h, i));
count++;
}
}
}
}
}
}
}
}
}

TimeSpan duration = DateTime.Now.Subtract(start);
Console.WriteLine(string.Format("Count: {0}", count));
Console.WriteLine(string.Format("Duration: {0} ", duration.Milliseconds));

I've also changed it to report the time in milliseconds:

C:\stprojects\tmp\NumberCrunch\NumberCrunch\bin\Debug>NumberCrunch.exe
381654720
381654729
783204165
801654723
Count: 4
Duration: 0

So it's pretty fast...

[tribbles]

Final version: This one uses the digits /1/ to 9, not 0 to 9 like before.

DateTime start = DateTime.Now;
int count = 0;

for (int a = 1; a < 10; a++)
{
if (a == 5)
continue;
for (int b = 2; b < 10; b += 2)
{
if (b == a)
continue;

for (int c = 1; c < 10; c++)
{
if ((c == 5) || (c == a) || (c == b))
continue;
if (((a + b + c) % 3) != 0)
continue;

for (int d = (c & 1) << 1; d < 10; d += 4)
{
if ((d == a) || (d == b) || (d == c))
continue;

for (int f = 0; f < 10; f += 2)
{
if ((f == a) || (f == b) || (f == c) || (f == d))
continue;

if (((a + b + c + d + 5 + f) % 3) != 0)
continue;

for (int g = 1; g < 10; g++)
{
if ((g == a) || (g == b) || (g == c) || (g == d) || (g == 5) || (g == f))
continue;
if (((a * 1000000 + b * 100000 + c * 10000 + d * 1000 + 500 + f * 10 + g) % 7) != 0)
continue;

for (int h = 10 - (((g & 3) + 1) << 1); h >= 0; h -= 8)
{
if ((h == a) || (h == b) || (h == c) || (h == d) || (h == f) || (h == g))
continue;

for (int i = 1; i < 10; i++)
{
if ((i == a) || (i == b) || (i == c) || (i == d) || (i == 5) || (i == f) || (i == g) || (i == h))
continue;
if (((a + b + c + d + 5 + f + g + h + i) % 9) != 0)
continue;

Console.WriteLine(string.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}", a, b, c, d, 5, f, g, h, i));
count++;
}
}
}
}
}
}
}
}

TimeSpan duration = DateTime.Now.Subtract(start);
Console.WriteLine(string.Format("Count: {0}", count));
Console.WriteLine(string.Format("Duration: {0} ", duration.Milliseconds));



C:\stprojects\tmp\NumberCrunch\NumberCrunch\bin\Debug>NumberCrunch.exe
381654729
Count: 1
Duration: 0

ETA: Just spotted a bugette - although it still produces the correct answer.

Edited by tribbles on Tuesday 22 February 20:20

[bishbash]

zippy3x said:

I'll have a go at Most Elegant, Shortest and Fastest

Console.WriteLine("381654729");

anyone do better?

I can do shorter with php

echo 381654729;

or even shorter with old school asp
=381654729

Both of them are probably slower though

Edited because I fked up the PHP, even though that's what I do all day most days, serves me right for slipping into c# to play with a programming puzzle

Edited by bishbash on Tuesday 22 February 16:58

[Alex]

Worth a special prize, I think. Smartiest Arse, perhaps?

Actually, there is an elegant way to work out the number on paper, without any coding.

[130R]

Elegant:

private static Set<String> permutations = new HashSet<String>();

public static void main(String... args) {
char[] digits = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
permute(digits, digits.length);
int count = 0;
for (String s : permutations) {
int div = digits.length;
int temp = Integer.valueOf(s);
do {
if (temp % div == 0) {
div--;
temp = (temp / 10);
} else break;
} while (div > 1);
if (div == 1) {
System.out.println("match found: " + s);
count++;
}
}
System.out.println("total match count: " + count);
}

private static void permute(char[] a, int n) {
if (n == 1) {
permutations.add(String.valueOf(a));
} else {
for (int i = 0; i < n; i++) {
int j = n - 1;
swap(a, i, j);
permute(a, j);
swap(a, i, j);
}
}
}

private static void swap(char[] a, int i, int j) {
char c = a[i];
a[i] = a[j];
a[j] = c;
}

[Prak]

tribbles said:

Console.WriteLine(string.Format("Duration: {0} ", duration.Milliseconds));

Duration.totalmilliseconds, no?

Got caught by that last week.

[tribbles]

Prak said:

tribbles said:

Console.WriteLine(string.Format("Duration: {0} ", duration.Milliseconds));

Duration.totalmilliseconds, no?

Got caught by that last week.

It depends: If it's less than 1 second, then it's fine; otherwise you'd need to use totalmilliseconds. Since I know my code executes in less than 1s, I chose to do less typing (or rather, less intellisense-skipping)

Or maybe I forgot...

[aspender]

130R said:

Elegant Java Solution

Elegant yes, but Java's imperative style doesn't suit this kind of problem. I love Java, but I'm starting to love Scala even more:


import scala.collection.mutable.Set

object ProblemScala extends Application {

implicit def charArray2Int(c: Array[Char]): Int = java.lang.String.valueOf(c).toInt

val digits = Array('1', '2', '3', '4', '5', '6', '7', '8', '9')
val permutations = Set[Int]()

def permute(digits: Array[Char], n: Int): Unit = n match {
case 1 => permutations += digits
case _ => {
for(val i <- 0 until n) {
val j = n - 1
swap(digits, i, j)
permute(digits, j)
swap(digits, i, j)
}
}
}

def swap(digits: Array[Char], i: Int, j: Int): Unit = {
val c = digits(i)
digits(i) = digits(j)
digits(j) = c
}

def divisible(n: Int, divisor: Int): Boolean = divisor match {
case 1 => true
case _ => n % divisor == 0 && divisible(n / 10, divisor - 1)
}

permute(digits, digits length)
val result = permutations filter (n => divisible(n, 9))

result.foreach(i => println("match found: " + i))
println("total match count: " + result.size)
}


There is still room for improvement in there, particularly around the calculation of all permutations which is not very functional, but I'm still learning...

Edited by aspender on Wednesday 23 February 10:32

[130R]

aspender said:

Scala

Python:

import itertools

digits = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
permutations = list(itertools.permutations(digits))
count = 0
for i in permutations:
div = len(digits)
num = int(''.join(i))
while div > 1:
if num % div == 0:
div += -1
num = (num / 10)
else:
break
if div == 1:
print 'match found: ', ''.join(i)
count += 1

print 'total match count: ', count

http://pastebin.com/FDfqt3u8

Edited by 130R on Wednesday 23 February 16:27

[bishbash]

Lua - http://pastebin.com/FeQCZ1WB

local permute = require 'pl.permute'
t = (permute.table{1,2,3,4,5,6,7,8,9})
for i, value in pairs(t) do
local x,m,skip = "",0,0
for j, v in pairs(value) do
if skip == 0 then
x = x..v
m = m+1
if (x%m) == 0 then
if tonumber(x) > 99999999 then
print(x)
end
else
skip,m = 1,0
end
end
end
end


It takes a couple of seconds to run.

Edited to take a couple of lines out, original in the pastebin, 18 lines is currently the shortest, I think

Edited by bishbash on Wednesday 23 February 15:42

[bishbash]

Nice cheeky edit 130r

Here it is in 15 lines

for i, value in pairs(require 'pl.permute'.table{1,2,3,4,5,6,7,8,9}) do
local x,m,skip = "",0,0
for j, v in pairs(value) do
if skip == 0 then
x, m = x..v, m+1
if x%m == 0 then
if string.len(x) ==9 then
print(x)
end
else
skip,m = 1,0
end
end
end
end

[zippy3x]

Another way....

static void Main(string[] args)
{
Stopwatch timer = new Stopwatch();
timer.Start();

int answer = Calculate(0, 1);

TimeSpan duration = timer.Elapsed;

Console.WriteLine("Answer - " + answer.ToString());
Console.WriteLine("Duration - " + duration.ToString());
Console.ReadLine();
}

static int Calculate(int n, int depth)
{
for (int i = 1; i <= 9; i++)
{
int number = n * 10 + i;
if (number % depth == 0 && n.ToString().IndexOf(i.ToString()) == -1)
{
if (depth != 9)
{
int answer;
if ((answer = Calculate(number, depth + 1)) != 0)
return answer;
}
else
return number;
}
}
return 0;
}


I put a loop round the Calculate call in Main and ran it 100 times
The duration was 00:00:00.0114242
Which means it ran once in 00:00:00.000114242

Fastest?


I could make it smaller by formatting, but I've left it a bit more readable.

To Tribbles - the timer code you used of mine will only have a 500ms resolution. If you use the timer code in this example you'll get a truer measurement (you'll need to add a reference to system.diagnostics)

[130R]

bishbash said:

Here it is in 15 lines

Those end statements will be the end of you I fear 8 lines:

import itertools
permutations = list(itertools.permutations(['1', '2', '3', '4', '5', '6', '7', '8', '9']))
for i in permutations:
div = 9; num = int(''.join(i))
while div > 1:
if num % div == 0: div += -1; num = (num / 10)
else: break
if div == 1: print 'match found: ', ''.join(i)

http://pastebin.com/M9ZtLHAr

This is not quite as nice as the previous example though because that allowed you to remove digits from the end of the list meaning it worked for "find an x-digit integer that is exactly divisible by x (etc, etc), where the digits from 1 to x can only appear once each in the number." where x is any number from 2 to 9 (so for 6, for example, you would set the list to ['1', '2', '3', '4', '5', '6']).

Technically in Java or C# I could write it all in one (very, very long) line though.

This thread now reminds me of the Social Network:

Eduardo Saverin: So when will it be finished?
Mark Zuckerberg: It won't be finished. That's the point. The way fashion's never finished.

[bishbash]

Your right about those ends, so i've combined them
In lua you can run it all on one line but here it is in 7

for i, value in pairs(require 'pl.permute'.table{1,2,3,4,5,6,7,8,9}) do
local x,m,skip = "",0,0
for j, v in pairs(value) do
if skip == 0 then x, m = x..v, m+1
if x%m == 0 then
if string.len(x) ==9 then print(x) end
else skip,m = 1,0 end end end end

I've only been playing with lua for a week, so would like to see what someone who really knows the language could do, but I love the fact that in lua you can do
x, y = "something", 999
Giving x a value of something and y a value of 999 saves lots of space for this kind of thing, allthough not amazingly practical in the real world.

The thing thats bugging me though is that I'm having to do

if x%m == 0 then
if string.len(x) == 9

I've tried variations of

if (x%m == 0) and (string.len(x) ==9) then

but it doesn't work and I can't get my head round why

[aspender]

Scala version 2. This is using the latest nightly snapshot of Scala 2.9.0:


object ProblemScala2 extends App {

def divisible(n: Int, divisor: Int): Boolean = divisor match {
case 1 => true
case _ => n % divisor == 0 && divisible(n / 10, divisor - 1)
}

"123456789".permutations filter (n => divisible(n.toInt, 9)) foreach(n => println("match found: " + n))

}


This is it running via SBT (Simple Build Tool):

Edited by aspender on Wednesday 23 February 19:48

[Alex]

That's very good.