All | 43 Folders | Accessibility | BoingBoing | Books | Computer Related | Family | Films | General | Hacking | Hobbies | Humor | Java | Links | Omni | OpenSolaris | Puzzles and Games

« Four Fours | Main | ScummVM - Beneath a... »
20061204 Monday December 04, 2006

Four Fours in Python

I couldn't leave it alone. I just had to see what the C# code looked like in Python, so I could understand how it worked, and to see how much slower it was in a scripting language.

I've made no attempts to optimize the code. If I had more time to spend on this, I think I would have designed the data structures differently for the Python version.

To my unpracticed eye, it looks more readable as Python code, but I don't want to start a my-language-is-better-than-yours slanging match.

Here's the results. Hopefully identicals to Carl's. 

  % python fourfours.py 
  1 = (4 + 4) / (4 + 4)
  2 = (4 * 4) / (4 + 4)
  3 = ( (4 + 4) + 4) / 4
  4 = ( (4 - 4) * 4) + 4
  5 = ( (4 * 4) + 4) / 4
  6 = ( (4 + 4) / 4) + 4
  7 = (4 + 4) - (4 / 4)
  8 = (4 + 4) + (4 - 4)
  9 = (4 + 4) + (4 / 4)
  10 = (4 + 4) + (4 - sqrt(4))
  11 = ( (4 + 4!) / 4) + 4
  12 = 4 - (4 / 4) * 4
  13 = (4 / 4) + (4! / sqrt(4))
  14 = (4 + 4) + (4 + sqrt(4))
  15 = (4 * 4) - (4 / 4)
  16 = (4 + 4) + (4 + 4)
  17 = (4 * 4) + (4 / 4)
  18 = (4 * 4) + (4 - sqrt(4))
  19 = (4! - 4) - (4 / 4)
  20 = ( (4 / 4) + 4) * 4
  21 = (4 / 4) - (4 - 4!)
  22 = (4 * 4) + (4 + sqrt(4))
  23 = ( (4 * 4!) - 4) / 4
  24 = (4 + 4) + (4 * 4)
  25 = ( (4 / 4) + 4) ^ sqrt(4)
  26 = ( (4 + 4) / 4) + 4!
  27 = (4 + 4!) - (4 / 4)
  28 = ( (4 + 4) * 4) - 4
  29 = (4 / 4) + (4 + 4!)
  30 = ( (4 + 4) * 4) - sqrt(4)
  31 = ( (4 + 4!) / 4) + 4!
  32 = (4 * 4) + (4 * 4)
  33 = (4 + 4!) + (sqrt(4) / .4)
  34 = ( (4 + 4) * 4) + sqrt(4)
  35 = ( (4 * 4) - sqrt(4)) / .4
  36 = ( (4 + 4) * 4) + 4
  37 = (4 + 4!) + (4 / .4bar)
  38 = (4 * 4) - (sqrt(4) - 4!)
  39 = ( (4 * 4) - .4) / .4
  40 = ( (4 * 4) + 4) * sqrt(4)
  41 = ( (4! - 4) / .4bar) - 4
  42 = (4 * 4) + (sqrt(4) + 4!)
  43 = (sqrt(4) * 4!) - (sqrt(4) / .4)
  44 = (4 * 4) + (4 + 4!)
  45 = ( (4 * 4) + 4) / .4bar
  46 = ( (4 * 4!) - 4) / sqrt(4)
  47 = (sqrt(4) * 4!) - (4 / 4)
  48 = ( (4 + 4) + 4) * 4
  49 = (4 / 4) + (sqrt(4) * 4!)
  50 = ( (4 * 4) + 4) / .4
  51 = ( (4! - sqrt(4)) / .4) - 4
  52 = ( (4 - sqrt(4)) * 4!) + 4
  53 = (4! / .4bar) - (4 / 4)
  54 = ( (4 + sqrt(4)) ^ 4) / 4!
  55 = (4 / 4) + (4! / .4bar)
  56 = ( (4 * 4) - sqrt(4)) * 4
  57 = (4 / .4bar) + (sqrt(4) * 4!)
  58 = ( (4 ^ 4) - 4!) / 4
  59 = (4! / .4) - (4 / 4)
  60 = ( (4 * 4) * 4) - 4
  61 = (4 / 4) + (4! / .4)
  62 = ( (4 * 4) * 4) - sqrt(4)
  63 = ( (4 ^ 4) - 4) / 4
  64 = (4 + 4) * (4 + 4)
  65 = ( (4 ^ 4) + 4) / 4
  66 = ( (4 * 4) * 4) + sqrt(4)
  67 = ( (4 + 4!) / .4bar) + 4
  68 = ( (4 * 4) * 4) + 4
  69 = ( (sqrt(4) + 4!) / .4) + 4
  70 = ( (4 ^ 4) + 4!) / 4
  71 = ( (sqrt(4) * 4!) - sqrt(.4bar)) / sqrt(.4bar)
  72 = ( (4 * 4) + sqrt(4)) * 4
  73 = ( (sqrt(4) * 4!) + sqrt(.4bar)) / sqrt(.4bar)
  74 = (4 * 4!) + (sqrt(4) - 4!)
  75 = ( (4 + sqrt(4)) + 4!) / .4
  76 = ( (4! - 4) * 4) - 4
  77 = ( (4 / .4bar) ^ sqrt(4)) - 4
  78 = ( (4! - 4) * 4) - sqrt(4)
  79 = ( (4 / .4bar) ^ sqrt(4)) - sqrt(4)
  80 = ( (4 * 4) + 4) * 4
  81 = ( (4 / 4) - 4) ^ 4
  82 = ( (4! - 4) * 4) + sqrt(4)
  83 = ( (4 / .4bar) ^ sqrt(4)) + sqrt(4)
  84 = ( (4! - 4) * 4) + 4
  85 = ( (4 / .4bar) ^ sqrt(4)) + 4
  86 = ( (4! - sqrt(4)) * 4) - sqrt(4)
  87 = (4 * 4!) - (4 / .4bar)
  88 = (4 * 4!) - (4 + 4)
  89 = ( (sqrt(4) + 4!) / .4) + 4!
  90 = (4 * 4!) - (4 + sqrt(4))
  91 = (4 * 4!) - (sqrt(4) / .4)
  92 = 4! - (4 / 4) * 4
  93 = (4 * 4!) - (sqrt(4) / sqrt(.4bar))
  94 = (4 * 4!) - (4 - sqrt(4))
  95 = (4 * 4!) - (4 / 4)
  96 = (4 * 4) * (4 + sqrt(4))
  97 = (4 / 4) + (4 * 4!)
  98 = (4 - sqrt(4)) + (4 * 4!)
  99 = ( (sqrt(4) * 4!) - 4) / .4bar
  100 = ( (4 + 4) + sqrt(4)) ^ sqrt(4)
  Done. (648000 loop iterations)
  Elapsed time:  8.08476805687  seconds
  %

I ran this on an Acer Ferrari 3400 laptop (which has a Mobile AMD Athlon 64 processor), under Ubuntu Edgy (with Python 2.4.4c1). I don't know what Carl ran his code on.

Assuming they are roughly comparable, the Python version was over 20 times slower. Not bad. Unlike Homer Simpson and his microwaved food, I think I can wait out the 8 seconds with patience.

If somebody has a setup to run both and compare apples with apples that would be great.

I think the itch is scratched now. On to other things.

Update:

I received an email notification of a comment from "Name", but that comment didn't automatically appear with this blog entry. It was marked as spam. I've cleared that. Name said:

"Some of the values are wrong - I noticed 92, but there are probably others. I've created a new version of this, also written in Python. It's very, very slow (30 seconds to run), but is correct. (lets hope posting it works)"

Thanks! I've put the new version here.

Update:

I've also received a Java version of Carl's original C# code from Jeffrey Olson (thanks!), which you can find here

[]

( Dec 04 2006, 07:43:56 AM PST ) [Listen] Permalink Comments [27]

Comments:

On Linux Mono vs Python: Mono: Elapsed time: 563 milliseconds Python: Elapsed time: 7.31023597717 seconds Mono is 1.2.1; Python is 2.4.2 These are only on Linux, someone should test it on Windows, as .NET has a better JITer than we do.

Posted by Miguel de Icaza on December 04, 2006 at 08:00 AM PST #

I think Homer had problems waiting for a flash fry of a Buffalo. Perhaps there's another instance where he indicated impatience w.r.t. microwave oven cooking times, but I can't recall it.

Posted by mike on December 04, 2006 at 08:21 AM PST #

Dell Inspiron 640m (Core Duo 1.6mhz, 1gb ram) running Ubuntu Edgy: Mono: Elapsed time: 745 milliseconds Python: Elapsed time: 8.50408196449 seconds

Posted by Mario Fuentes on December 04, 2006 at 08:34 AM PST #

Thanks Mario! That put's it closer to 10-12X slower than 20x21. With a bit of optimization to the Python code, I suspect it can be reduced even more.

Posted by Rich Burridge on December 04, 2006 at 08:38 AM PST #

Argh. Sorry Miguel. Our mail servers must be a little slow at the moment. I didn't get the notification of your comment so didn't see your comparison there. Thanks!

mike, it's been a while since I saw that Simpsons episode. I don't remember it being Buffalo. I do remember Marge shouting "It's ready kids. Come and get it while it's incredible hot!"

Posted by Rich Burridge on December 04, 2006 at 08:44 AM PST #

On my machine the python version goes from 8 seconds to 1.8 just by using psyco.

Posted by Justin on December 04, 2006 at 08:53 AM PST #

Thanks Justin! That's really interesting. Maybe we should start looking at psyco for Orca...

Posted by Rich Burridge on December 04, 2006 at 09:11 AM PST #

running under winXP (1.7 PentiumM): python2.4.2: Elapsed time: 7.73200005531 seconds under .net 2.0 360 milliseconds almost 21.5 times faster. Must be the better JITer that Miguel alluded to. Perhaps of note, IronPython is not much faster than native python. Elapsed time: 7.52201080322 seconds

Posted by Karl Strauss on December 04, 2006 at 09:12 AM PST #

I consider .4 and .4bar cheating - and I found a solution to 45 without the cheats. Do you want to try it yourself? Or should I post it here?

Posted by 85.197.4.196 on December 04, 2006 at 09:26 AM PST #

Ran these on XP SP2.

VS 2005 Professional using release build:
1 = (4 + 4) / (4 + 4)
2 = (4 * 4) / (4 + 4)
3 = ( (4 + 4) + 4) / 4
4 = ( (4 - 4) * 4) + 4
5 = ( (4 * 4) + 4) / 4
6 = ( (4 + 4) / 4) + 4
7 = (4 + 4) - (4 / 4)
8 = (4 + 4) + (4 - 4)
9 = (4 + 4) + (4 / 4)
10 = (4 + 4) + (4 - sqrt(4))
11 = ( (4 + 4!) / 4) + 4
12 = 4 - (4 / 4) * 4
13 = (4 / 4) + (4! / sqrt(4))
14 = (4 + 4) + (4 + sqrt(4))
15 = (4 * 4) - (4 / 4)
16 = (4 + 4) + (4 + 4)
17 = (4 * 4) + (4 / 4)
18 = (4 * 4) + (4 - sqrt(4))
19 = (4! - 4) - (4 / 4)
20 = ( (4 / 4) + 4) * 4
21 = (4 / 4) - (4 - 4!)
22 = (4 * 4) + (4 + sqrt(4))
23 = ( (4 * 4!) - 4) / 4
24 = (4 + 4) + (4 * 4)
25 = ( (4 / 4) + 4) ^ sqrt(4)
26 = ( (4 + 4) / 4) + 4!
27 = (4 + 4!) - (4 / 4)
28 = ( (4 + 4) * 4) - 4
29 = (4 / 4) + (4 + 4!)
30 = ( (4 + 4) * 4) - sqrt(4)
31 = ( (4 + 4!) / 4) + 4!
32 = (4 * 4) + (4 * 4)
33 = (4 + 4!) + (sqrt(4) / .4)
34 = ( (4 + 4) * 4) + sqrt(4)
35 = ( (4 * 4) - sqrt(4)) / .4
36 = ( (4 + 4) * 4) + 4
37 = (4 + 4!) + (4 / .4bar)
38 = (4 * 4) - (sqrt(4) - 4!)
39 = ( (4 * 4) - .4) / .4
40 = ( (4 * 4) + 4) * sqrt(4)
41 = ( (4 * 4) + .4) / .4
42 = (4 * 4) + (sqrt(4) + 4!)
43 = (sqrt(4) * 4!) - (sqrt(4) / .4)
44 = (4 * 4) + (4 + 4!)
45 = ( (4 * 4) + 4) / .4bar
46 = ( (4 * 4!) - 4) / sqrt(4)
47 = (sqrt(4) * 4!) - (4 / 4)
48 = ( (4 + 4) + 4) * 4
49 = (4 / 4) + (sqrt(4) * 4!)
50 = ( (4 * 4) + 4) / .4
51 = ( (4! - sqrt(4)) / .4) - 4
52 = ( (4 - sqrt(4)) * 4!) + 4
53 = (4! / .4bar) - (4 / 4)
54 = ( (4 + sqrt(4)) ^ 4) / 4!
55 = (4 / 4) + (4! / .4bar)
56 = ( (4 * 4) - sqrt(4)) * 4
57 = (4 / .4bar) + (sqrt(4) * 4!)
58 = ( (4 ^ 4) - 4!) / 4
59 = (4! / .4) - (4 / 4)
60 = ( (4 * 4) * 4) - 4
61 = (4 / 4) + (4! / .4)
62 = ( (4 * 4) * 4) - sqrt(4)
63 = ( (4 ^ 4) - 4) / 4
64 = (4 + 4) * (4 + 4)
65 = ( (4 ^ 4) + 4) / 4
66 = ( (4 * 4) * 4) + sqrt(4)
67 = ( (4 + 4!) / .4bar) + 4
68 = ( (4 * 4) * 4) + 4
69 = ( (sqrt(4) + 4!) / .4) + 4
70 = ( (4 ^ 4) + 4!) / 4
71 = ( (4 + 4!) + .4) / .4
72 = ( (4 * 4) + sqrt(4)) * 4
73 = ( (sqrt(4) * 4!) + sqrt(.4bar)) / sqrt(.4bar)
74 = (4 * 4!) + (sqrt(4) - 4!)
75 = ( (4 + sqrt(4)) + 4!) / .4
76 = ( (4! - 4) * 4) - 4
77 = ( (4 / .4bar) ^ sqrt(4)) - 4
78 = ( (4! - 4) * 4) - sqrt(4)
79 = ( (4 / .4bar) ^ sqrt(4)) - sqrt(4)
80 = ( (4 * 4) + 4) * 4
81 = ( (4 / 4) - 4) ^ 4
82 = ( (4! - 4) * 4) + sqrt(4)
83 = ( (4 / .4bar) ^ sqrt(4)) + sqrt(4)
84 = ( (4! - 4) * 4) + 4
85 = ( (4 / .4bar) ^ sqrt(4)) + 4
86 = ( (4! - sqrt(4)) * 4) - sqrt(4)
87 = (4 * 4!) - (4 / .4bar)
88 = (4 * 4!) - (4 + 4)
89 = ( (sqrt(4) + 4!) / .4) + 4!
90 = (4 * 4!) - (4 + sqrt(4))
91 = (4 * 4!) - (sqrt(4) / .4)
92 = 4! - (4 / 4) * 4
93 = (4 * 4!) - (sqrt(4) / sqrt(.4bar))
94 = (4 * 4!) - (4 - sqrt(4))
95 = (4 * 4!) - (4 / 4)
96 = (4 * 4) * (4 + sqrt(4))
97 = (4 / 4) + (4 * 4!)
98 = (4 - sqrt(4)) + (4 * 4!)
99 = ( (sqrt(4) * 4!) - 4) / .4bar
100 = ( (4 + 4) + sqrt(4)) ^ sqrt(4)
Done. (648000 loop iterations)
Elapsed time: 312 milliseconds

Hacked up the c# file a bit to run in Java5, came up with this:
C:\>java -classpath .; FourFoursSolver
1 = (4 + 4) / (4 + 4)
2 = (4 * 4) / (4 + 4)
3 = ( (4 + 4) + 4) / 4
4 = ( (4 - 4) * 4) + 4
5 = ( (4 * 4) + 4) / 4
6 = ( (4 + 4) / 4) + 4
7 = (4 + 4) - (4 / 4)
8 = (4 + 4) + (4 - 4)
9 = (4 + 4) + (4 / 4)
10 = (4 + 4) + (4 - sqrt(4))
11 = ( (4 + 4!) / 4) + 4
12 = 4 - (4 / 4) * 4
13 = (4 / 4) + (4! / sqrt(4))
14 = (4 + 4) + (4 + sqrt(4))
15 = (4 * 4) - (4 / 4)
16 = (4 + 4) + (4 + 4)
17 = (4 * 4) + (4 / 4)
18 = (4 * 4) + (4 - sqrt(4))
19 = (4! - 4) - (4 / 4)
20 = ( (4 / 4) + 4) * 4
21 = (4 / 4) - (4 - 4!)
22 = (4 * 4) + (4 + sqrt(4))
23 = ( (4 * 4!) - 4) / 4
24 = (4 + 4) + (4 * 4)
25 = ( (4 / 4) + 4) ^ sqrt(4)
26 = ( (4 + 4) / 4) + 4!
27 = (4 + 4!) - (4 / 4)
28 = ( (4 + 4) * 4) - 4
29 = (4 / 4) + (4 + 4!)
30 = ( (4 + 4) * 4) - sqrt(4)
31 = ( (4 + 4!) / 4) + 4!
32 = (4 * 4) + (4 * 4)
33 = (4 + 4!) + (sqrt(4) / .4)
34 = ( (4 + 4) * 4) + sqrt(4)
35 = ( (4 * 4) - sqrt(4)) / .4
36 = ( (4 + 4) * 4) + 4
37 = (4 + 4!) + (4 / .4bar)
38 = (4 * 4) - (sqrt(4) - 4!)
39 = ( (4 * 4) - .4) / .4
40 = ( (4 * 4) + 4) * sqrt(4)
41 = ( (4 * 4) + .4) / .4
42 = (4 * 4) + (sqrt(4) + 4!)
43 = (sqrt(4) * 4!) - (sqrt(4) / .4)
44 = (4 * 4) + (4 + 4!)
45 = ( (4 * 4) + 4) / .4bar
46 = ( (4 * 4!) - 4) / sqrt(4)
47 = (sqrt(4) * 4!) - (4 / 4)
48 = ( (4 + 4) + 4) * 4
49 = (4 / 4) + (sqrt(4) * 4!)
50 = ( (4 * 4) + 4) / .4
51 = ( (4! - sqrt(4)) / .4) - 4
52 = ( (4 - sqrt(4)) * 4!) + 4
53 = (4! / .4bar) - (4 / 4)
54 = ( (4 + sqrt(4)) ^ 4) / 4!
55 = (4 / 4) + (4! / .4bar)
56 = ( (4 * 4) - sqrt(4)) * 4
57 = (4 / .4bar) + (sqrt(4) * 4!)
58 = ( (4 ^ 4) - 4!) / 4
59 = (4! / .4) - (4 / 4)
60 = ( (4 * 4) * 4) - 4
61 = (4 / 4) + (4! / .4)
62 = ( (4 * 4) * 4) - sqrt(4)
63 = ( (4 ^ 4) - 4) / 4
64 = (4 + 4) * (4 + 4)
65 = ( (4 ^ 4) + 4) / 4
66 = ( (4 * 4) * 4) + sqrt(4)
67 = ( (4 + 4!) / .4bar) + 4
68 = ( (4 * 4) * 4) + 4
69 = ( (sqrt(4) + 4!) / .4) + 4
70 = ( (4 ^ 4) + 4!) / 4
71 = ( (4 + 4!) + .4) / .4
72 = ( (4 * 4) + sqrt(4)) * 4
73 = ( (sqrt(4) * 4!) + sqrt(.4bar)) / sqrt(.4bar)
74 = (4 * 4!) + (sqrt(4) - 4!)
75 = ( (4 + sqrt(4)) + 4!) / .4
76 = ( (4! - 4) * 4) - 4
77 = ( (4 / .4bar) ^ sqrt(4)) - 4
78 = ( (4! - 4) * 4) - sqrt(4)
79 = ( (4 / .4bar) ^ sqrt(4)) - sqrt(4)
80 = ( (4 * 4) + 4) * 4
81 = ( (4 / 4) - 4) ^ 4
82 = ( (4! - 4) * 4) + sqrt(4)
83 = ( (4 / .4bar) ^ sqrt(4)) + sqrt(4)
84 = ( (4! - 4) * 4) + 4
85 = ( (4 / .4bar) ^ sqrt(4)) + 4
86 = ( (4! - sqrt(4)) * 4) - sqrt(4)
87 = (4 * 4!) - (4 / .4bar)
88 = (4 * 4!) - (4 + 4)
89 = ( (sqrt(4) + 4!) / .4) + 4!
90 = (4 * 4!) - (4 + sqrt(4))
91 = (4 * 4!) - (sqrt(4) / .4)
92 = 4! - (4 / 4) * 4
93 = (4 * 4!) - (sqrt(4) / sqrt(.4bar))
94 = (4 * 4!) - (4 - sqrt(4))
95 = (4 * 4!) - (4 / 4)
96 = (4 * 4) * (4 + sqrt(4))
97 = (4 / 4) + (4 * 4!)
98 = (4 - sqrt(4)) + (4 * 4!)
99 = ( (sqrt(4) * 4!) - 4) / .4bar
100 = ( (4 + 4) + sqrt(4)) ^ sqrt(4)
Done. (648000 loop iterations)
Elapsed time: 469 milliseconds

Python2.5 Running the file you linked:
C:\>c:\Python25\python.exe fourfours.py
1 = (4 + 4) / (4 + 4)
2 = (4 * 4) / (4 + 4)
3 = ( (4 + 4) + 4) / 4
4 = ( (4 - 4) * 4) + 4
5 = ( (4 * 4) + 4) / 4
6 = ( (4 + 4) / 4) + 4
7 = (4 + 4) - (4 / 4)
8 = (4 + 4) + (4 - 4)
9 = (4 + 4) + (4 / 4)
10 = (4 + 4) + (4 - sqrt(4))
11 = ( (4 + 4!) / 4) + 4
12 = 4 - (4 / 4) * 4
13 = (4 / 4) + (4! / sqrt(4))
14 = (4 + 4) + (4 + sqrt(4))
15 = (4 * 4) - (4 / 4)
16 = (4 + 4) + (4 + 4)
17 = (4 * 4) + (4 / 4)
18 = (4 * 4) + (4 - sqrt(4))
19 = (4! - 4) - (4 / 4)
20 = ( (4 / 4) + 4) * 4
21 = (4 / 4) - (4 - 4!)
22 = (4 * 4) + (4 + sqrt(4))
23 = ( (4 * 4!) - 4) / 4
24 = (4 + 4) + (4 * 4)
25 = ( (4 / 4) + 4) ^ sqrt(4)
26 = ( (4 + 4) / 4) + 4!
27 = (4 + 4!) - (4 / 4)
28 = ( (4 + 4) * 4) - 4
29 = (4 / 4) + (4 + 4!)
30 = ( (4 + 4) * 4) - sqrt(4)
31 = ( (4 + 4!) / 4) + 4!
32 = (4 * 4) + (4 * 4)
33 = (4 + 4!) + (sqrt(4) / .4)
34 = ( (4 + 4) * 4) + sqrt(4)
35 = ( (4 * 4) - sqrt(4)) / .4
36 = ( (4 + 4) * 4) + 4
37 = (4 + 4!) + (4 / .4bar)
38 = (4 * 4) - (sqrt(4) - 4!)
39 = ( (4 * 4) - .4) / .4
40 = ( (4 * 4) + 4) * sqrt(4)
41 = ( (4! - 4) / .4bar) - 4
42 = (4 * 4) + (sqrt(4) + 4!)
43 = (sqrt(4) * 4!) - (sqrt(4) / .4)
44 = (4 * 4) + (4 + 4!)
45 = ( (4 * 4) + 4) / .4bar
46 = ( (4 * 4!) - 4) / sqrt(4)
47 = (sqrt(4) * 4!) - (4 / 4)
48 = ( (4 + 4) + 4) * 4
49 = (4 / 4) + (sqrt(4) * 4!)
50 = ( (4 * 4) + 4) / .4
51 = ( (4! - sqrt(4)) / .4) - 4
52 = ( (4 - sqrt(4)) * 4!) + 4
53 = (4! / .4bar) - (4 / 4)
54 = ( (4 + sqrt(4)) ^ 4) / 4!
55 = (4 / 4) + (4! / .4bar)
56 = ( (4 * 4) - sqrt(4)) * 4
57 = (4 / .4bar) + (sqrt(4) * 4!)
58 = ( (4 ^ 4) - 4!) / 4
59 = (4! / .4) - (4 / 4)
60 = ( (4 * 4) * 4) - 4
61 = (4 / 4) + (4! / .4)
62 = ( (4 * 4) * 4) - sqrt(4)
63 = ( (4 ^ 4) - 4) / 4
64 = (4 + 4) * (4 + 4)
65 = ( (4 ^ 4) + 4) / 4
66 = ( (4 * 4) * 4) + sqrt(4)
67 = ( (4 + 4!) / .4bar) + 4
68 = ( (4 * 4) * 4) + 4
69 = ( (sqrt(4) + 4!) / .4) + 4
70 = ( (4 ^ 4) + 4!) / 4
71 = ( (sqrt(4) * 4!) - sqrt(.4bar)) / sqrt(.4bar)
72 = ( (4 * 4) + sqrt(4)) * 4
73 = ( (sqrt(4) * 4!) + sqrt(.4bar)) / sqrt(.4bar)
74 = (4 * 4!) + (sqrt(4) - 4!)
75 = ( (4 + sqrt(4)) + 4!) / .4
76 = ( (4! - 4) * 4) - 4
77 = ( (4 / .4bar) ^ sqrt(4)) - 4
78 = ( (4! - 4) * 4) - sqrt(4)
79 = ( (4 / .4bar) ^ sqrt(4)) - sqrt(4)
80 = ( (4 * 4) + 4) * 4
81 = ( (4 / 4) - 4) ^ 4
82 = ( (4! - 4) * 4) + sqrt(4)
83 = ( (4 / .4bar) ^ sqrt(4)) + sqrt(4)
84 = ( (4! - 4) * 4) + 4
85 = ( (4 / .4bar) ^ sqrt(4)) + 4
86 = ( (4! - sqrt(4)) * 4) - sqrt(4)
87 = (4 * 4!) - (4 / .4bar)
88 = (4 * 4!) - (4 + 4)
89 = ( (sqrt(4) + 4!) / .4) + 4!
90 = (4 * 4!) - (4 + sqrt(4))
91 = (4 * 4!) - (sqrt(4) / .4)
92 = 4! - (4 / 4) * 4
93 = (4 * 4!) - (sqrt(4) / sqrt(.4bar))
94 = (4 * 4!) - (4 - sqrt(4))
95 = (4 * 4!) - (4 / 4)
96 = (4 * 4) * (4 + sqrt(4))
97 = (4 / 4) + (4 * 4!)
98 = (4 - sqrt(4)) + (4 * 4!)
99 = ( (sqrt(4) * 4!) - 4) / .4bar
100 = ( (4 + 4) + sqrt(4)) ^ sqrt(4)
Done. (648000 loop iterations)
Elapsed time: 8.60899996758 seconds


Thought I'd toss this in too..
C:\>diff pyresults.txt javaresults.txt
41c41
< 41 = ( (4! - 4) / .4bar) - 4
---
> 41 = ( (4 * 4) + .4) / .4
71c71
< 71 = ( (sqrt(4) * 4!) - sqrt(.4bar)) / sqrt(.4bar)
---
> 71 = ( (4 + 4!) + .4) / .4

C:\>diff pyresults.txt csresults.txt
41c41
< 41 = ( (4! - 4) / .4bar) - 4
---
> 41 = ( (4 * 4) + .4) / .4
71c71
< 71 = ( (sqrt(4) * 4!) - sqrt(.4bar)) / sqrt(.4bar)
---
> 71 = ( (4 + 4!) + .4) / .4

C:\>diff javaresults.txt csresults.txt
((Jeff note, nothing different))

So, the Python version had the same difference between the Java & C# version.

The Java version had no difference from the C# version according to diff.


Btw, what is ".4bar"?

Posted by Jeffrey Olson on December 04, 2006 at 09:29 AM PST #

I had no idea that was going to be so popular! Thanks everybody for updated times (and results).

85.197.4.196, please post your new 45 result. I consider .4 and .4bar cheating too.

I'm considering reworking the code to not use those. And there I was thinking I could move on. Silly me.

Jeffrey, .4bar is .4444.. recurring.

Posted by Rich Burridge on December 04, 2006 at 10:41 AM PST #

45 = (4!/4)!/(4*4)

Posted by 85.197.4.196 on December 04, 2006 at 10:53 AM PST #

I Consider .4bar cheating too (I dont even know what it means), but the use of the decimal digit can be considered legal, but not .4, since .4 = 0.4, instead of 4.4.

One thing I noticed, is that no solution uses the number 44, or even 444 or 4444 (but that last one might be rare to use). For instance, 1 = 44/44 and 0 = 44-44 (The 0 was not present at the solutions neither).

So, 45 = 44 + 4/4

http://en.wikipedia.org/wiki/Four_fours

Posted by Ronaldo Maia on December 04, 2006 at 11:50 AM PST #

I had no idea there was a wikipedia entry. Thanks Ronaldo. Now I've got a load of new links to explore.

Posted by Rich Burridge on December 04, 2006 at 12:24 PM PST #

"I had no idea there was a wikipedia entry" I wonder how many times that phrase has been (or will be in the future) uttered. :)

Posted by jon on December 04, 2006 at 12:37 PM PST #

Ah ok, good to know! Any ideas why the python one returns results different from the others? Also, Rich, if yuo want the java one I need an email address and I'll send it to you so you can have it as well to run. I literally hacked up the c# one by changing the few things different (string to String, etc..) to make it work.

Posted by Jeffrey Olson on December 04, 2006 at 01:32 PM PST #

BTW: The code seems to have a bug, look at the entry for 12: It's 4-(4/4)*4 instead of (4-4/4)*4.

Posted by 85.197.4.196 on December 04, 2006 at 02:00 PM PST #

Hi Jeffrey,

I'd be happy to add an update to the post giving a pointer to your Java code. I'm also happy to store it in the resources section of this blog.

My email address is rich period burridge at sun period com

I've no idea why we are getting different results. Floating point arithmetic doesn't come quite as naturally in Python as it does in C#. My guess is that I've introduced a bug or two as I ported it (maybe in the Operate() routine.

Hopefully I'll find time to revisit this code and make it more flexible and bug free.

Thanks.

Posted by Rich Burridge on December 04, 2006 at 02:20 PM PST #

Some of the values are wrong - I noticed 92, but there are probably others. I've created a new version of this, also written in Python. It's very, very slow (30 seconds to run), but is correct. (lets hope posting it works) 
#!/usr/bin/python

import operator
import time
from math import ceil,fabs

def combinations(size, values):
  if size == 1:
    return [[i] for i in values]
  
  half = combinations(size - 1, values)
  result = []
  for value in values:
    for row in half:
      result.append([value] + row)
  return result

def expressions():
  # There are two versions of each term and operation - the pretty version,
  # to be shown to the user, and the version to be evaluated by Python

  all_terms = [
    ('4', 4.0),
    ('sqrt(4)', 2.0),
    ('4!', 24.0),
    ('.4', 0.4),
    ('.4bar', 4.0 / 9.0),
    ('sqrt(.4bar)', 2.0 / 3.0)
  ]

  all_operators = [
    ('+', '+'),
    ('-', '-'),
    ('*', '*'),
    ('/', '/'),
    ('^', '**')
  ]

  expression_combos = [
    '(%s %s %s) %s (%s %s %s)',  # ( A x B ) x ( C x D )
    '( (%s %s %s) %s %s) %s %s', # ( ( A x B ) x C ) x D
    '%s %s (%s %s %s) %s %s',    # A x ( B x C ) x D
    '%s %s (%s %s (%s %s %s))'   # A x ( B x ( C x D ) )
  ]

  for association in expression_combos:

    # Four slots for values
    for terms in combinations(4, all_terms):

      # Three slots for operators
      for operations in combinations(3, all_operators):

        # To be shown to the user
        values = (
          terms[0][0],
          operations[0][0],
          terms[1][0],
          operations[1][0],
          terms[2][0],
          operations[2][0],
          terms[3][0]
        )

        # To be executed by Python
        py_values = (
          terms[0][1],
          operations[0][1],
          terms[1][1],
          operations[1][1],
          terms[2][1],
          operations[2][1],
          terms[3][1]
        )

        yield (association % values, association % py_values)

def main():
  results = [None for i in range (0, 101)]

  start_time = time.time()
  iterations = 0

  for expression, py_expression in expressions():
    iterations = iterations + 1
    try:
      result = eval(py_expression)

      # Check that the result is in the correct range
      if result > 0 and result <= 100:
        int_result = int(ceil(result))

        # Check that the result is an integer
        if fabs(int_result - result) < 0.0000001:

          # Check this value has not already been found
          if results[int_result] == None:
            results[int_result] = expression

    except ZeroDivisionError:
      pass

    # Numerical result out of range
    except OverflowError:
      pass

    # negative number cannot be raised to a fractional power
    except ValueError:
      pass

  for ii, expression in enumerate(results):
    if ii > 0:
      print ii,'=',expression

  print "Done. (%d loop iterations)" % iterations
  print "Elapsed time: ", (time.time() - start_time), " seconds"


if __name__ == "__main__":
    main()

Posted by Name on December 04, 2006 at 04:50 PM PST #

Thanks! I've updated the blog entry directly with a pointer to your new version. As I mention there, I'd like to properly attribute this to you.

Posted by Rich Burridge on December 04, 2006 at 05:08 PM PST #

I posted the earlier code. Consider it in the public domain - it's simple enough that I would feel silly taking credit for it. Especially since all I did was clean up the existing code a bit, and didn't actually create a new algorithm. (by the way, your web log software does not work correctly if Javascript is disabled)

Posted by Anonymous, Internet superhero on December 04, 2006 at 08:03 PM PST #

Okay, fair enough. Thanks! I really like your code. Very clean.

The Javascript problem is known. I suspect it's not going to be changed.

Posted by Rich Burridge on December 04, 2006 at 10:20 PM PST #

File sent to you.

Posted by Jeffrey Olson on December 05, 2006 at 07:05 AM PST #

[Trackback] Sur ce blog un programme �crit en python permet de tous les trouver jusqu'� 100.

Posted by DaBobo'sBlog on December 05, 2006 at 07:29 AM PST #

Has anyone ever tried to solve this using some form of concurrency/parallelism? The more I look at it, it seems like it would be possible, though I'm a beginner in that realm and could be complete mistaken. The one major hitch I can see is figuring out what is the simplist answer as you can, from what I read on wikipedia, come up with a lot of alternate answers so the worthiness part (god, this just screams of a genetic algo...) of it would definatly be interesting to figure out.

Posted by Jeffrey Olson on December 05, 2006 at 08:36 AM PST #

Paolo Molaro profiled Mono, and he increased the array access performance by 40% (we were using a slow path for arrays with multiple dimensions).

So the 563 milliseconds reported earlier turned into 353 milliseconds with Mono from SVN.

Miguel.

Posted by Miguel de Icaza on December 05, 2006 at 09:54 AM PST #

Excellent! I'm so glad we've found a fun test case. 8-) Seriously, this is great news. Thanks for commenting.

Posted by Rich Burridge on December 05, 2006 at 10:06 AM PST #

Post a Comment:

Comments are closed for this entry.