I came across the FourFours problem recently. Stated succinctly, it asks: what are the ways to calculate each of the integers from 1 to 100 with formulas which use the digit four exactly four times? (No digits other than four can be used at all.)
People have solved it in C# (138 lines, 380ms), Python (119 lines, 20s), Haskell (73 lines, 900ms), and Perl (one (really long) line, 45s). I thought it would be interesting to try it in Common Lisp, so I did.
For one thing, I found that my code was slower than the C# and Haskell solutions; I consistently get about 2.5 seconds for my solution. That seems mostly to be a result of both the dynamic nature of Lisp and the particularly-dynamic approach I took (more on that in a bit). I also took more lines (148 significant lines; excludes comments, doc strings, empty lines, and a couple of ancillary definitions).
In my defense, I did things somewhat more generally than the others; I don’t like hardcoded data, so my code generates a lot of stuff on the fly. One notable example is the ordering of operations on the four values: the other solutions I’ve seen all hardcode the orderings, but my code generates the code structure (just a binary tree) at runtime based on the number of elements. I then use the code/data duality of Lisp to generate both functions and the printed representation of the operations from those trees. Likewise, my code will figure out the possible values to use in the calculations from a supplied digit.
All that flexibility let me play around a lot more with the structure of the problem. Although everyone else used five operations (addition, subtraction, multiplication, division, and exponentiation), I found that only four were necessary (addition, subtraction, multiplication, and division). (I checked smaller numbers of operations, too. I considered all of the functions in Common Lisp that would return ratios or integers when given a pair of ratios or integers as parameters. I was unable to get all the way from 1 to 100 with fewer than four distinct functions.)
With the given parameters (four fours, with 4, 4!, sqrt(4), .4, .4bar, and sqrt(.4bar)) and operators (+, -, *, /), you can actually go all the way up to 102. (Adding exponentiation does not allow you to go any further.)
I can calculate the consecutive chains for arbitrary base digits:
1: 1
1: 2 / 2
1: 3! / (3 + 3)
2: (3 + 3) / 3
3: (3 + 3) - 3
4: 3 + (3 / 3)
5: (3! / 3) + 3
6: (3 * 3) - 3
7: 3! + (3 / 3)
8: 3! + (3! / 3)
9: 3 + (3 + 3)
10: (3! - 3) / .3
11: (.3 + 3) / .3
12: 3 + (3 * 3)
13: (3 / .3) + 3
14: (3! / .3) - 3!
15: 3! + (3 * 3)
16: (3 / .3) + 3!
17: (3! / .3) - 3
18: 3 * (3 + 3)
19: (3! - .3) / .3
20: (3 + 3) / .3
21: (3! * 3) + 3
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)) / 4
11: ((4! + 4) / 4) + 4
12: 4 * (4 - (4 / 4))
13: (4! + (4! + 4)) / 4
14: (4! / 4) + (4 + 4)
15: (4 * 4) - (4 / 4)
16: 4 + (4 + (4 + 4))
17: (4 / 4) + (4 * 4)
18: ((4! * 4) - 4!) / 4
19: 4! - (4 + (4 / 4))
20: 4 * (4 + (4 / 4))
21: (4 / 4) + (4! - 4)
22: 4! - ((4 + 4) / 4)
23: ((4! * 4) - 4) / 4
24: (4 * 4) + (4 + 4)
25: ((4! * 4) + 4) / 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)) / 4
31: 4! + ((4! + 4) / 4)
32: (4 * 4) + (4 * 4)
33: ((4 - .4) / .4) + 4!
34: (4! / 4) + (4! + 4)
35: ((4 / .4) + 4) / .4
36: 4 + (4 * (4 + 4))
37: ((.4 + 4!) / .4) - 4!
38: (4 / .4) + (4! + 4)
39: 4! + (4! / (.4 * 4))
40: (4 * (4 * 4)) - 4!
41: (.4 + (4 * 4)) / .4
42: (4! + 4!) - (4! / 4)
43: (4! + 4!) - (sqrt(4) / .4)
44: (4 * 4) + (4! + 4)
45: (4! - (4! / 4)) / .4
46: ((4! - 4) / .4) - 4
47: (4! + 4!) - (4 / 4)
48: 4 * (4 + (4 + 4))
49: (4 / 4) + (4! + 4!)
50: (4 + (4 * 4)) / .4
51: ((.4 + 4!) - 4) / .4
52: (4! / .4) - (4 + 4)
53: (sqrt(4) / .4) + (4! + 4!)
54: (4! / 4) + (4! + 4!)
55: ((4! - .4) / .4) - 4
56: 4! + (4 * (4 + 4))
57: ((.4 + 4!) / .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) - 4
67: ((4! + 4) / .4bar) + 4
68: 4 + (4 * (4 * 4))
69: ((4! + 4) - .4) / .4
70: (4! / .4) + (4 / .4)
71: (.4 + (4! + 4)) / .4
72: 4! * (4 - (4 / 4))
73: (sqrt(.4bar) + (4! + 4!)) / sqrt(.4bar)
74: ((4! + 4) / .4) + 4
75: (4! + (4! / 4)) / .4
76: ((4! - 4) * 4) - 4
77: ((4! - .4bar) / .4bar) + 4!
78: ((4! - 4) * 4) - sqrt(4)
79: ((4! - sqrt(4)) / .4) + 4!
80: 4 * (4 + (4 * 4))
81: ((4! / .4) - 4!) / .4bar
82: sqrt(4) + ((4! - 4) * 4)
83: ((4! - .4) / .4) + 4!
84: ((4! - 4) * 4) + 4
85: ((4 / .4) + 4!) / .4
86: (4! * 4) - (4 / .4)
87: (4! * 4) - (4 / .4bar)
88: (4! * 4) - (4 + 4)
89: ((sqrt(4) + 4!) / .4) + 4!
90: (4! * 4) - (4! / 4)
91: (4! * 4) - (sqrt(4) / .4)
92: (4! - (4 / 4)) * 4
93: (4! * 4) - (sqrt(4) / sqrt(.4bar))
94: ((4! + 4) / .4) + 4!
95: (4! * 4) - (4 / 4)
96: 4! * ((4 + 4) - 4)
97: (4 / 4) + (4! * 4)
98: .4 + ((.4 + 4!) * 4)
99: ((4! + 4!) - 4) / .4bar
100: (4! + (4 / 4)) * 4
101: (sqrt(4) / .4) + (4! * 4)
102: (4! / 4) + (4! * 4)
1: 5 / (5 + (5 * (5 - 5)))
2: ((5 + (5 + 5)) - 5) / 5
3: (5 + (5 * 5)) / (5 + 5)
4: (5 + (5 + (5 + 5))) / 5
5: (5 + (5 + 5)) - (5 + 5)
⋮
154: (5! / 5) + (5! + (5 + 5))
155: 5 + (5 * (5 + (5 * 5)))
156: (5! + (5! * (.5 + 5))) / 5
157: (5 / (.5bar * (.5bar - .5))) - 5
158: (((5! / 5) - 5) / .5) + 5!
1: (6 + (6 + 6)) / (6 + (6 + 6))
2: (6 + (6 + (6 + 6))) / (6 + 6)
3: ((6 + (6 + (6 + 6))) - 6) / 6
4: (6 * (6 + 6)) / (6 + (6 + 6))
5: (6 + (6 + (6 + (6 + 6)))) / 6
6: 6 + (6 * ((6 + 6) - (6 + 6)))
⋮
881: 6! + (((.6bar * (6! + 6!)) + 6) / 6)
882: ((6! / 6) + 6) * (6 + (6 / 6))
883: ((.6bar + (6! / (.6bar + 6))) / .6bar) + 6!
884: (6! / (.6 * 6)) + (6! - (6 * 6))
885: (.6 * ((6 * 6) + (6! + 6!))) - .6
886: ((6! / (6 - .6)) * (.6 + 6)) + 6
I’ll probably experiment with solutions that involve concatenation of digits next. That’ll involve some fairly significant code changes, though. And I’ll probably just end up duplicating the work of the definitive Four Fours answer key.