Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Task

This is quite a simple coding task, all your program has to do is place a point on a canvas (or your alternative in another coding language) and connect it to all the dots already placed. Your program must take in one input, the number of dots that should be placed, and output some sort of display with the dots connected. Example

Requirements

  • I have to be able to run it, which means that it has to have a compiler/tool to run it either online, or publicly available to download.
  • You are allowed to use any library created before this challenge was set, as long as it wasn't designed for the sole purpose of solving this.
  • This is a shortest code task, which means characters. Comments, code that changes colour (for prettiness) and libraries will be ignored.
  • Your answer must be unique, don't steal other peoples code, shorten it a few characters and repost it.
  • It must be able to run in less than 5 minutes, for the values of 5 and 100. It must also use a resolution of at least 200*200 and put each dot in a random location on the canvas using a non-trivial distribution.

Current Leaderboard

Flawr       - Matlab        - 22  - Confirmed
Falko       - Python 2      - 41  - Confirmed
Ssdecontrol - R             - 66  - Confirmed
David       - Mathematica   - 95  - Confirmed
ILoveQBasic - QBasic        - 130 - Confirmed
Adriweb     - TI-Nspire Lua - 145 - Confirmed
Manatwork   - Bash          - 148 - Confirmed
Doorknob    - Python 2      - 158 - Confirmed
Kevin       - TCL           - 161 - Confirmed
Manatwork   - HTML/JS       - 261 - Confirmed - Improved code of Scrblnrd3
Makando     - C#            - 278 - Confirmed
Scrblnrd3   - HTML/JS       - 281 - Confirmed
Geobits     - Java          - 282 - Confirmed
WozzeC      - C# WPF        - 306 - Confirmed

If I've missed you out, I'm very sorry, just add a comment to your work saying so and I'll add it as soon as I see it =)

TL;DR

  • Input - Number of dots (int, can be hard coded)
  • Output - Image of randomly placed dots, all connected to each other (graphic)
  • Winner - Shortest code
share|improve this question
1  
Am I allowed math libraries? What libraries exactly are you trying to avoid with requirement #2? –  Nathan Merrill Aug 22 at 12:51
2  
Is there any limitation for resolution? This is quite easy if you let me output a 1x1 image –  Jan Dvorak Aug 22 at 12:54
3  
When you say no "math" libraries, what about languages where the default PRNG is included in "math"? I don't want to write a generator. –  Geobits Aug 22 at 13:02
1  
Since you disallow library code that directly relates to the task, and that task is essentially to draw a random network graph, isn't use of native graph-drawing functions also disallowed? This restriction is far from well defined. –  comperendinous Aug 22 at 15:52
1  
@PopeyGilbert I must say, I've never seen a new user so responsive to issues with their question and also individually test each answer and maintain a leaderboard. Good work and welcome to PPGC! –  Calvin's Hobbies Aug 23 at 3:03

13 Answers 13

up vote 11 down vote accepted

Matlab (22)

gplot(ones(n),rand(n))

It is assumend that n is the number of points, and it looks like this for n=10: random graph

n=6:

random

Explaination

gplot is a command for plotting graphs. The first argument is a n x n incidence matrix (full of ones, obviously). The second argument should be a n x 2 matrix with the coordinates of the points, but it does not matter if the second dimension is bigger that 2, so I just generate an n x n matrix of random values (which is 2 characters shorter than generating an n x 2 matrix).

Links to documentation

share|improve this answer
    
Never used Matlab, so it will take a moment to test - But from the image it looks okay! Congrats on doing it in 22 characters. EDIT - Turns out I can't test this, however looking at the image it seems correct so I'll allow it. However can someone else test it please? –  Popey Gilbert Aug 22 at 15:31
2  
Thanks=) You can test it here: octave-online.net Since octave is basically the opensource version of MatLab. –  flawr Aug 22 at 15:36

Java : 318 282 265

Because, ya know, Java:

class M{public static void main(String[]a){new Frame(){public void paint(Graphics g){int i=0,j,d=640,n=25,x[]=new int[n],y[]=x.clone();for(setSize(d,d);i<n;i++)for(j=0,x[i]=(int)(random()*d),y[i]=(int)(random()*d);j<i;g.drawLine(x[i],y[i],x[j],y[j++]));}}.show();}}

Its just a simple loop that makes random dots and draws lines between the current dot and all previous ones.

Example with 25 dots:

enter image description here

With line breaks and imports:

import java.awt.*;
import static java.lang.Math.*;

class M{
    public static void main(String[]a){
        new Frame(){
            public void paint(Graphics g){
                int i=0,j,d=640,n=25,x[]=new int[n],y[]=x.clone();
                for(setSize(d,d);i<n;i++)
                    for(j=0,x[i]=(int)(random()*d),y[i]=(int)(random()*d);
                        j<i;
                        g.drawLine(x[i],y[i],x[j],y[j++]));
            }
        }.show();
    }
}

Edit: Since we're not counting imports, I imported a couple more things to save some characters later.

Edit 2: OP added an allowance for hardcoding number of dots. -17 chars :)

share|improve this answer
    
Nice! Congrats on being first one. –  Popey Gilbert Aug 22 at 13:17
2  
First, but I'm sure it won't be the shortest by a long shot. Cause, ya know, Java ;) –  Geobits Aug 22 at 13:19
2  
+1. Cause, ya know, Java. :) –  bitpwner Aug 22 at 13:21
1  
I admire people who always solve the task in Java, even when hopeless, I'd even be too lazy to start eclipse... so +1 =) –  flawr Aug 22 at 15:53
1  
It's not necessary to define main's parameter as final. You can cut off those 6 characters –  Cruncher Aug 22 at 15:53

Python 2 - 41 35

After importing some libraries as allowed for this challenge

from pylab import rand as r
from pylab import plot as p
from itertools import product as x
from itertools import chain as c

we can plot some number of connected points with just one line of code:

X=r(5,2);p(*zip(*c(*list(x(X,X)))))

(The screenshot was generated with 10 points.)

share|improve this answer
    
[Referring to a deleted comment:] I know, but here "libraries will be ignored". If not, I'd definitely implement it differently. Using those libraries does not save enough characters to justify the import statements in a normal code golf challenge. –  Falko Aug 22 at 15:52
    
is pylab part of standard distribution? I would imagine we can't just import anything we like. Under that metric you can implement anything in python with a single import statement. –  Cruncher Aug 22 at 16:02
    
Yes it is. I just did what I thought would be valid. But I'm not sure. And looking into the comments shows a huge discussion going on. As soon as this is clarified I'd be willing to adjust my code. –  Falko Aug 22 at 16:09
    
Although this competitions view on what libraries are allowed seems to change from day to day, PyLab should definitely be allowed. –  Popey Gilbert Aug 23 at 15:31

Python 2, 158

Import statements not included in character count, as noted in question ("libraries will be ignored").

from PIL import Image,ImageDraw
from random import randint

s=[(randint(0,200),randint(0,200))for _ in range(int(input()))]
i=Image.new('RGB',(200,200))
[ImageDraw.Draw(i).line((p,q),255)for p in s for q in s]
i.show()

Sample outputs:

n=2 (...):

n=2

n=10 (looks like fancy 3d thing or something):

n=10

n=100 (looks like someone went BLELEEEAARARGHHH with a red pen):

n=100

n=500, 1000, 10000 (runs in about 1.5 seconds, 5-6 seconds, and 3.5 minutes respectively):

Note: the 10000 points one was run with a slightly optimized version that changed line 3 (not including imports) to this:

d=ImageDraw.Draw
for p in s:
  for q in s:d.line((p,q),255)

Otherwise it would have taken forever. :P

Ungolfed:

from PIL import Image, ImageDraw
from random import randint
point_count = int(input())
image_size = 200
points = [(randint(0, image_size), randint(0, image_size)) for _ in range(point_count)]
image = Image.new('RGB', (200, 200))
draw = ImageDraw.Draw(image)
for start_point in points:
    for end_point in points:
        draw.line((start_point, end_point), 255)
image.show()
share|improve this answer
1  
Congrats on currently being the shortest entrant! Love your comment on n=100. Might be best to put image.new and image_size to 800. Might look less weird =) –  Popey Gilbert Aug 22 at 13:24
    
@PopeyGilbert So I can remove the import statements from mine? I assumed "ignore libraries" meant the library itself wasn't counted (as usual). –  Geobits Aug 22 at 13:26
    
Yeah, because some languages have very few base functions, and have to import all their stuff. If you think this is not fair Geobits, then please say =) I want to try to make this fair. –  Popey Gilbert Aug 22 at 13:27
    
@PopeyGilbert I just asked because it's not the norm and wanted to clear it up before I chopped a few more characters from my code :D –  Geobits Aug 22 at 13:30
1  
Since the resolution only has to be at least 200x200, you could save a few characters (5, I think) by setting x=255 and using it to replace the instances of 200 and 255. –  comperendinous Aug 22 at 13:38

Mathematica 95 87

With some help from belisarius.

CompleteGraph[n, VertexSize -> {2, 2},
VertexCoordinates -> Table[RandomInteger[{0, 199}, 2], {n}]]

n=5

5


n=100

Timing: 2.082654 sec

100

share|improve this answer
    
This is verified, I've gotten it to work! Does Mathematica normally count as a language though? –  Popey Gilbert Aug 22 at 13:36
1  
@PopeyGilbert Sure it does. There are ~750 answers in Mathematica so far. –  Geobits Aug 22 at 13:59
    
Oh, wow, Okay! Fair enough <3 –  Popey Gilbert Aug 22 at 14:01
    
Methinks this is shorter and satisfies the rules CompleteGraph[100, VertexCoordinates -> RandomReal[{0, 199}, {100, 2}]] –  belisarius Aug 24 at 3:24
    
Thanks, You are correct. I figured I couldn't win so I thought I'd make it pretty (VertexSize->{2,2}. I did, however, overlook the fact that 100 was unnecessary to include, and that Input[] was optional. –  David Carraher Aug 24 at 4:06

R, 66

This one is borderline cheating but I still think it's within the rules. Set up by loading the igraph package with library(igraph), which can be downloaded from CRAN with install.packages("igraph"). Then assign the input to variable N. As per the rules, these are not counted in the total.

G=graph.adjacency(matrix(1,N,N),"un")
plot(G,layout=layout.random)

N = 50

enter image description here

Note that this code also draws self-connections. Eliminating them (although there's no rule against them) adds 6 characters:

G=graph.adjacency(matrix(1,N,N),"un",diag=F)
plot(G,layout=layout.random)

R, 141

This is an honest-to-goodness solution in base R:

p=replicate(2,runif(N))
g=as.matrix(expand.grid(1:N,1:N))
plot.new()
apply(g,1,function(i) segments(p[i[1],1],p[i[1],2],p[i[2],1],p[i[2],2]))

although you still have to enter N by hand.

N = 50

enter image description here

I'm wondering if a for loop would be fewer characters than apply but I'm happy with what I've got.

share|improve this answer
    
I'll accept self-connects, technically the question is draw a line to ALL points. I've tested it and confirmed it also. –  Popey Gilbert Aug 23 at 15:44
    
Do you mind arrows connecting the points? That'll save another 5 by eliminating ,"un" at the end of the first line. –  ssdecontrol Aug 23 at 15:51
    
If you don't mind, I think we should keep it so it has to be lines connecting each of the points. That way the answer will appear similar in each of the answers. –  Popey Gilbert Aug 23 at 16:00

[TI-Nspire] Lua - 145 135 130

(Updated fixed version)

Screenshot with n=10

"Importing" math.random as "r", first, as allowed : r=math.random

Actual code :

function on.paint(g)t={}for b=1,2*n-1,2 do t[b]=r(318)t[b+1]=r(212)for c=1,b-1,2 do g:drawLine(t[b],t[b+1],t[c],t[c+1])end end end

Note : This code works on the TI-Nspire calculators (TI added Lua scripting to recent OSes of this platform, with an even-based API allowing users to graph stuff etc. for example.)
It can also be tried online here (just erase the demo script and prepend mine with n=10 for example)

share|improve this answer
    
Time for me to learn Lua! –  Beta Decay Aug 23 at 12:30
1  
This seems to suffer by the same mistake as fuandon's deleted PowerShell answer and Vlo's also deleted R answer: you connect the dots in pair, not every dot with all other dots. (Lua is so rare on this site. Please fix your code instead of deleting it.) –  manatwork Aug 23 at 12:37
    
Oh, my bad - I'll fix that soon ! –  Adriweb Aug 23 at 14:13
    
There we go, thanks for letting me know :) –  Adriweb Aug 23 at 14:49
    
This has been tested and confirmed! Well done on using Lua. –  Popey Gilbert Aug 23 at 15:36

C# Windows forms, 268

static void k(int n,int s){var f=new Form{Height=s+50,Width=s+25};f.Paint+=(u,v)=>{var r=new Random();var p=new Point[n];while(n>0)p[--n]=new Point(r.Next(s),r.Next(s));foreach(var a in p)foreach(var b in p)f.CreateGraphics().DrawLine(Pens.Tan,a,b);};f.ShowDialog();}

N=5

Plot using 5 points

N=50

Plot using N=50

Full code is given below

using System;
using System.Drawing;
using System.Windows.Forms;

namespace WindowsFormsApplication2
{
    static class Program
    {
        static void Main()
        {
            k(50, 200);
        }
        static void k(int n, int s)
        {
            var f = new Form {Height = s + 50, Width = s + 25};
            f.Paint += (u, v) =>
            {
                var r = new Random();
                var p = new Point[n];
                while (n > 0)
                    p[--n] = new Point(r.Next(s), r.Next(s));
                foreach (var a in p)
                    foreach (var b in p)
                        f.CreateGraphics().DrawLine(Pens.Tan, a, b);
            };
            f.ShowDialog();
        }
    }
}
share|improve this answer
    
Tested and confirmed! When I checked the character count, I used the full code and was surprised when it came to <700 characters... >.<. Anyway, congratulations on making a successful entry! –  Popey Gilbert Aug 24 at 10:15
    
Isn't there some shortcut like Pens.Tan instead of new Pen(Color.Tan)? –  CompuChip Aug 24 at 13:40
    
Changed to use Pens.Tan, saving an extra 10 –  makando Aug 25 at 11:15

QBasic or QuickBasic, 130 characters

SCREEN 1:RANDOMIZE:N=10:DIM X(100),Y(100):FOR I=1 TO N:X(I)=RND*320:Y(I)=RND*200:FOR J=1 TO I:LINE(X(I),Y(I))-(X(J),Y(J)):NEXT J,I

Code variations

  • If you do not want to be prompted for a seed, replace RANDOMIZE with RANDOMIZE TIMER.
  • If you want to be prompted for N, replace N=10 with INPUT N or INPUT "N";N.

Sample runs

For N=5, tested with QBasic 1.1 running on DOSBox 0.74:

For N=100, tested with QBasic 1.1 running on DOSBox 0.74:

share|improve this answer
    
Oh, wow, nice image for N=5! Love that it's a pentagram when the seed is 42. Tested and confirmed. –  Popey Gilbert Aug 24 at 14:20

Bash + ImageMagick: 148 characters

c=()
while((i++<$1)); do
p=$[RANDOM%200],$[RANDOM%200]
c+=($p)
for e in ${c[@]};do
d+="line $p $e"
done
done
convert -size 200x200 xc: -draw "$d" x:

Sample run:

bash-4.3$ time ./line.sh 5

real    0m5.256s
user    0m0.137s
sys     0m0.017s

Sample output:

5 connected points

Sample run:

bash-4.3$ time ./line.sh 25

real    0m3.043s
user    0m0.574s
sys     0m0.023s

Sample output:

25 connected points

Sample run:

bash-4.3$ time ./line.sh 100

real    0m5.662s
user    0m11.156s
sys     0m0.076s

Sample output:

100 connected points

share|improve this answer
    
Tested and confirmed. Well done manatwork! –  Popey Gilbert Aug 22 at 18:14
    
I'm very sorry, did I completely forget to add this to the leader boards? I will do that now. –  Popey Gilbert Aug 23 at 18:19

HTML/JS, 210, thanks to manatwork

<canvas id=q /><script>c=q.getContext("2d");r=Math.random;e=prompt(a=[]);for(i=0;i<e;i++){a[i]={x:r()*300,y:r()*150};for(j in a)c.beginPath()+c.moveTo(a[i].x,a[i].y)+c.lineTo(a[j].x,a[j].y)+c.stroke()}</script>

JSFiddle

share|improve this answer
    
This is verified, I've gotten it to work! –  Popey Gilbert Aug 22 at 14:03
    
You can use ~~ instead of m.floor to save 5 bytes –  William Barbosa Aug 22 at 16:20
    
Make the canvas tag self-closing and remove the single quotes around the id value: <canvas id=q />. (Note that you have to leave one space between the last attribute value and the self-closing /.) BTW, in Firefox works fine without m.floor() and ~~. –  manatwork Aug 22 at 17:08
    
Thanks for the help. –  scrblnrd3 Aug 22 at 17:13
    
219 characters: jsfiddle.net/e866azzs/5 –  manatwork Aug 22 at 17:33

C# WPF 306 296

partial class W:Window{public W(){InitializeComponent();int x=5,i=0,j,z=200;int[]f=new int[x],s=new int[x];var r=new Random();var X=new Grid();AddChild(X);for(;i<x;i++){f[i]=r.Next(z);s[i]=r.Next(z);for(j=i;j>=0;)X.Children.Add(newLine(){X1=s[j],Y1=f[j--],X2=s[i],Y2=f[i],Stroke=Brushes.Red});}}}

I would like to say that I could remove Stroke=Brushed.Red. But Sadly that means that I am painting transparent lines, and my Guess is that it wouldn't really count. :P I can also shave of a couple of bytes by just creating a grid in the XAML view. But that seemed unfair, so I stripped the XAML to become a blank canvas. (I don't count the XAML as bytes...)

partial class W:Window
{
    public W()
    {
        InitializeComponent();
        int x=5,i=0,j,z=200;
        int[]f=new int[x],s=new int[x];
        var r = new Random();
        var X = new Grid();
        AddChild(X);
        for (;i<x;i++)
        {
            f[i]=r.Next(z);
            s[i]=r.Next(z);
            for (j=i;j>=0;)
                X.Children.Add(new Line()
                {
                    X1 = s[j],
                    Y1 = f[j--],
                    X2 = s[i],
                    Y2 = f[i],
                    Stroke = Brushes.Red
                });
        }
    }
}

XAML

<Window x:Class="W"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="MainWindow" Height="350" Width="525">
</Window>

5

5

100

100

share|improve this answer
1  
Since it is WPF it will crash at around 3k Points for Out of Memory exception. –  WozzeC Aug 22 at 15:13
    
Tested and confirmed, well done on doing it in C# WPF! –  Popey Gilbert Aug 22 at 15:15
2  
Could be shorted a little by using var when declaring variables. –  MarcinJuraszek Aug 23 at 20:47
    
Yes, indeed. Thanks! I was also able to remove "this" from "this.AddChild". –  WozzeC Aug 28 at 7:43

TCL 161 chars

Clearly not going to win, but beats several others presented here, and I think it makes good use of a highly undervalued language.

for {set i 0} {$i<10} {incr i} {lappend l [expr rand()*291] [expr rand()*204]}
pack [canvas .c]
foreach {x y} $l {foreach {w z} $l {.c create line $x $y $w $z}}

Example

The default canvas size on my system appears to be 291x204. Not sure why, but using it saves 13 characters.

Fairly fast, 400 points in < 5 seconds, 500 in ~10 s. Size and points can be scaled arbitrarily and colors and line styles can be altered, at the cost of characters of course. Un-golfed and using variables to make it clearer and easier to scale and color:

set n 20
set width 500
set height 500
set bg_color black
set line_color white
for {set i 0} {$i < $n} {incr i} {
        lappend points [expr rand() * $width] [expr rand() * $height]
}
canvas .c -width $width -height $height -background $bg_color 
pack .c
foreach {x1 y1} $points {
        foreach {x2 y2} $points {
                .c create line $x1 $y1 $x2 $y2 -fill $line_color
        }
}       
share|improve this answer
    
Image seems fine, unfortunately my computer isn't working so I'll test it later. Congratulations on using such an underappreciated language. –  Popey Gilbert Aug 23 at 18:22
    
Just confirmed it, congratulations on a successful entry! –  Popey Gilbert Aug 24 at 10:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.