Golf with a bowling ball: hello world with high complexity yet short code

In this challenge, you must write a Hello World program that is both short and complex. We measure complexity by Cyclomatic McCabe complexity, and length by the number of bytes (not characters).

Score = complexity / bytes

For example, if the cyclomatic complexity is 5 and you use 100 bytes, your score is 5/100=0.05. If the cyclomatic complexity is 25 and you use 200 bytes, your score is 25/200=0.125.

The program shall take no input. The program must output exactly the ASCII-encoded string:

Hello, world!

in this exact case. This string may or may not be followed by a single newline (LF, ASCII 10). No other text shall be output.

gerrit

Posted 2014-01-27T12:20:08.907

Reputation: 296

Is this really code bowling? Seems like golf, with an added element. – Iszi – 2014-01-27T21:42:51.333

@Iszi bowling is more appropriate than golf in this case because big score wins. – hildred – 2014-01-27T22:23:57.903

@hildred Highest score wins, but the code has to be fairly short to keep a score high. Though the scoring may not be golf-like, the nature of the challenge most closely matches code golf. – Iszi – 2014-01-28T02:41:18.480

1@Iszi, I'm not sure whether it's really bowling, but it's certainly not golf because the scoring depends on a factor other than the length of the code. – Peter Taylor – 2014-01-28T12:31:17.687

@PeterTaylor I understand there's a factor other than length of code, but length of code is a strong enough factor in this that I think it really does fit. I'm pretty sure we've had other modified code golf challenges like this before, and I can't think of another tag that fits well enough - unless you just want to genericize it to code bowling. – Iszi – 2014-01-28T14:07:48.437

@Iszi: see the tag wiki for [tag:code-golf].

– Peter Taylor – 2014-01-28T14:08:59.217

Ack, I meant "genericize it to code challenge" not bowling. And it looks like the Wiki supports that. – Iszi – 2014-01-28T16:09:52.093

Answers

C# - 1/3

string x = null;
Console.WriteLine(x??x??x??...??x??"Hello, world!");

Score calculation:

lim(x→x/(x*3+53))
x→∞

If you feel the need to wrap this all in a class with a Main method... it doesn't change the score.

Kendall Frey

Posted 2014-01-27T12:20:08.907

Reputation: 2 384

Yes, I thought of doing something similar in GolfScript with {}/. – Peter Taylor – 2014-01-27T14:06:00.663

Since x is always initialized to null, the score here should probably be one (every time the program is executed, one path - and exactly the same path - is taken). – primo – 2014-01-27T16:08:57.833

2@primo The OP didn't specify that each path must be reachable, which would an entirely new challenge, since it would require randomization. – Kendall Frey – 2014-01-27T16:16:20.393

@KendallFrey Or, that your program follow each branch at some point. – primo – 2014-01-27T16:20:05.077

@primo And that requires randomization, unless I'm missing something. – Kendall Frey – 2014-01-27T16:24:28.847

for(i=0;13<i;i++){case 0: ... case 1: ...}. I don't see why randomization of any kind would be necessary. – primo – 2014-01-27T16:31:46.407

"every time the program is executed, one path - and exactly the same path - is taken" seems to apply equally to your program. – Kendall Frey – 2014-01-27T16:36:51.143

Do non-reachable paths contribute to the cyclomatic complexity, formally speaking? – gerrit – 2014-01-27T19:44:45.597

2@gerrit That's a good question. In the strictest theoretical sense, a program that does not take input takes only one possible path, so it's not possible to take multiple paths without input. Therefore the complexity will always be 1 unless you account for paths that are not taken. At least, this is my extrapolation. – Kendall Frey – 2014-01-27T19:55:04.790

@gerrit According to McCabe's original paper in Definition 1: "...it is assumed that each node can be reached by the entry node and each node can reach the exit node." Nodes which cannot be reached are not included in the graph.

– primo – 2014-01-27T20:14:19.470

@primo I think the definition of reachability there is a little more lax than what's being discussed here. It appears to be graph reachability, which doesn't take into account the actual decisions being made. – Kendall Frey – 2014-01-27T20:31:30.533

looks like you could use "var x = null" and thereby save 3 characters, doesn't change the limit as x approaches infinity though. – Xantix – 2014-02-03T05:36:06.393

Perl - score = 29/42 ≈ 0.6905

fork?wait:print for'Hello, world!
'=~/./gs

This will spawn a total of 16384 processes (don't worry though, no more than 15 are ever active at a time), each with a cyclomatic complexity of 3:

E - N + 2P = 8 - 7 + (2·1) = 3

Each time a branch is encountered, both paths are taken; once by the parent, and once by the newly spawned child.

My contention is that because the parent process never stops executing (that is, control is not passed, but rather split in two directions), the child process can not be considered to be running in the same control flow as the parent, but rather in its own. The total complexity diagram would therefore be more accurately depicted as the following:

The nodes from all paths which can never be reached have been removed.

E = 100; N = 73; P = 1 ⇒ CC = 29

Perl - score = 6000000/38 ≈ 157894.74

print eval'0?1:'x6e6."'Hello, world!'"

If you don't like the previous solution, consider this one: 6000000 nested branches, with a code length of 38. It could be argued - in fact I would even argue - that the complexity of this code is exactly 1, as the true condition of each branch can never be met, and therefore should be excluded from the complexity analysis.

In general, I think solutions of this type trivialize the challenge.

primo

Posted 2014-01-27T12:20:08.907

Reputation: 30 891

You generated the diagrams with a program (à la graphviz). What program is it? – Stéphane Gourichon – 2016-03-31T15:37:10.323

@StéphaneGourichon It's been a while, but I'm pretty sure I used draw.io.

– primo – 2016-04-01T07:07:50.387

As a non-Perl hacker, I'm pretty confused by this. Can you explain how it works, and why it has a complexity of more than 4, which I would have calculated it as? – Kendall Frey – 2014-01-27T19:58:36.943

The false branch spawns an entirely new process, essentially creating a whole new code tree. If one were to draw each of these trees on a single canvas, there would be 16384 of them. – primo – 2014-01-27T20:03:36.973

2It's the same program, isn't it? It's just one more decision branch, adding 1 to the complexity. – Kendall Frey – 2014-01-27T20:06:40.460

@KendallFrey Consider a program with two identical functions, both of which are called throughout the program. Do both functions add to the complexity of the system? Consider two processes running identical code in parallel, which are reliant on one another. Do both processes add to the complexity of the system? – primo – 2014-01-28T13:04:50.037

I think the program model pretty much breaks down when you execute things in parallel, because it doesn't allow you to take more than one path at once. – Kendall Frey – 2014-01-28T13:13:20.707

HQ9+, 1/1 = 1

1 byte, 1 path.

Timtech

Posted 2014-01-27T12:20:08.907

Reputation: 12 038

Doesn't output exactly Hello, world!. – Kendall Frey – 2014-01-27T21:24:34.857

1Yeah it does... try the official interpreter. – Timtech – 2014-01-27T21:26:37.030

I didn't know there was an official one. The one I tried didn't. – Kendall Frey – 2014-01-27T21:27:31.370

Ingenious. A bit like cheating though… – Tobia – 2014-01-27T22:04:23.013

VBScript - ?/337 = ?

Set s=WScript.CreateObject("WScript.Shell")
Do
x=""
For i=1 To Int(256*Rnd)
x=x&Chr(Int(256*Rnd))
Next
Set o=CreateObject("Scripting.FileSystemObject")
Set f=o.OpenTextFile("c:\a.exe",2,1)
f.Write x
f.Close
Set e=s.Exec("c:\a.exe")
Do Until e.Status:WScript.Sleep 9:Loop
t=e.StdOut.ReadLine()
Loop While t<>"Hello, world!"
Wscript.Echo t

Not sure exactly how to score this, as it's what I call "Bogo, world!". It generates random bytes and then shells them as executables until one of them successfully outputs "Hello, world!". The complexity for any given run is impossible to determine - eventually it will exit, but the number of code branches that it generates are outside of my abilities to determine statistically.

My original thought was to do something similar with randomly emitted assemblies in C#, but VBScript has a much lower byte count given the error trapping .NET would require...

BTW - have a Task Manager open if you run this (the Exec method doesn't have a way to suppress the command window, and I need the return value so I can't use Run).

Comintern

Posted 2014-01-27T12:20:08.907

Reputation: 3 632