This Sandbox has been retired in favor of the newer model.

This question replaces the earlier Sandboxes Mk. III, Mk. II, and Mk. I which were getting too crowded.

Just to keep the scrolling to a reasonable level. Please feel free to continue to work or vote on question in older sandboxes.

Use this as a sandbox for new questions.

Upvote when you think a question is ready.

share
add comment

22 Answers 22

Email validation

Rationale

http://codegolf.stackexchange.com/questions/6535/program-in-python was a bad question, but the underlying challenge of validating an e-mail address is actually quite interesting and has quite a bit of potential for golf. I would expect the winning answer to use a mixture of regex and network libraries.

Posted

share
    
Is this code golf? Or something else? –  minitech Jul 11 '12 at 4:08
    
@minitech, yes. Sorry, I thought that was clear enough from the rationale. –  Peter Taylor Jul 11 '12 at 7:01
add comment

Encode Images into Tweets (Extreme Image Compression Edition)

Posted

share
    
It might be simpler to describe the permitted characters as code points 32 to 126 inclusive. Also, the "140 bytes" is a bit misleading, because only about 6.5 bits per byte are available to use. –  Peter Taylor Sep 26 '12 at 22:57
    
@PeterTaylor Okay, I'll improve my description of the permitted characters. I'll also try to calculate how many bytes of storage are actually available. –  PhiNotPi Sep 26 '12 at 23:13
    
It's just short of 115 * 8 bits. –  Peter Taylor Sep 27 '12 at 11:38
    
I would love to see this challenge. My try at Mona Lisa. (original image) And I really don't think it's a problem that a similar one was posted somwhere outside CG. –  randomra Mar 21 '13 at 17:30
add comment

Lego Gear Train

Inspired by the Lego gear ratios problem by Keith Randall, although it is a completely different problem.

I, too, plan on building a giant lego robot that will eventually be able to destroy the other robots in the never-before-mentioned competition. In the process of constructing the robot, I will be using a lot of gear trains to connect different parts of the robot. I want you to write me the shortest program that will help me construct the complex gear trains that are required for such a complex task. I will, of course, only be using gears with 8, 16, 24, and 40 teeth.

Each gear in the gear train has a specific integer coordinate on a 2D grid. The first gear is located at (0,0) and the final gear will be located at non-negative coordinates. The location and size of the first and last gears will be provided as input, your program must tell what gears go where to fill in the gaps. Theoretically, all of the gears must connect perfectly and function correctly if the train actually built.

In addition, your program must use the minimum possible number of gears in the gear train. Fewer gears / train = more trains = bigger and better robot of destruction.

Here is a list of the radii of the gears:

8-tooth  - 1
16-tooth - 2
24-tooth - 3
40-tooth - 5

Input will consist of two lines:

X,Y
B:A

X and Y are the coordinates of the final gear. (the first gear is at (0,0)). B is the size of the second gear (in teeth). A is the size of the first gear in teeth. To add some difficulty, you need to make sure that the output gear rotates the right direction. If B is a positive number, then the output gear needs to rotate in the same direction (an odd number of gears used). If it is negative, then an even number of gears need to be used.

Output should be a list of the X location, Y location, and size (teeth) of each additional gear, one gear per line. If there are multiple minimal-gear solutions, print only one of your choice.

Examples (more coming soon):

4,0
8:8

2,0,8

.

7,7
16:16

4,3,24

.

0,26
-40:40

6,8,40
0,16,40

.

2,2
8:8

2,0,8

As far as I know, no problem is impossible unless the two input gears overlap or directly connect. You won't have to deal with this.

This is code golf, shortest answer wins.

share
    
How literal is "All of the gears must connect perfectly and function correctly if the train actually built"? Chains of gears do tend to lock up due to friction... Also, is 2,2 1:1 possible? –  Peter Taylor Sep 3 '12 at 20:19
    
@PeterTaylor I didn't intend for it to be taken that literally. Also, I'm going to try and find a solution to 2,2 8:8 (I should specify that the two numbers are the number of teeth, not the radii). –  PhiNotPi Sep 3 '12 at 20:51
add comment

Find real roots of a polynomial

Posted

share
    
Doesn't x^2+2=0 have only imaginary solutions? –  tomsmeding Apr 6 '13 at 12:07
    
@tomsmeding, corrected. Thank you. –  Peter Taylor Apr 6 '13 at 16:25
add comment

Render the Utah Teapot

[Hasty first posting.] [Revised and Posted]

The Utah Teapot, originally created by Martin Newell, is a convenient object for testing 3D graphics programs. Using the dataset available here (direct link, just the teapot), render a 3D view of the teapot (a perspective projection to 2D) with a simple lighting model (single light-source).

"Beige"

Requirements

  1. Output an image (to screen or to file). It should look like "the teapot". Minimum resolution, say 320x200, 8-bit grays (but you can do more if you want).
    Don't make a big black square and say, "The lights are off."

  2. Read the object data from an external file. Ideally this would be in the original format: 32 Bezier surface patches, indexed into a list of vertices. But there are alternate formulations, notably the one in Jim Blinn's A Trip Down the Graphics Pipeline. Use any convenient format or formulation, but specify what it is. The data comes for free.

    The idea here is that the program becomes a source-code application, where you can change the data, modify the program, and produce images of 3D scenes of arbitrary objects different datasets. So, sorry, no glutSolidTeapot: too opaque.

  3. Isolate the camera, lighting, and viewing parameters, and exclude them from the count.

    So the parameters are easy to modify, in support of the application idea. The light can be as simple as the dot product of a light direction vector and the surface normal as shown in the example here or it can be a point-light if your scheme uses that. Shadows are not necessary, but they are pretty.

  4. Implement an algorithm for Hidden Surface Removal. This may be raytracing, raycasting, z-buffer, space partitioning (BSP tree, Octree, k-d tree), other?

    From my experiments, simple backface-culling isn't sufficient, but can be helpful.

This is . Shortest (by byte count) code that performs a 3D rendering of the teapot from an external dataset, excluding viewing & lighting parameters (which should not be golfed), wins.

Edit: Maybe it should be . I don't know. Question: Can it be both? I'd like to see submissions in lots of languages even if they're not golfed.

Resources.

Questions asked about implementing my example program: How do Bezier Patches work in the Utah Teapot?, For BSP generation, How to intersect or locate a triangle with a plane defined by another triangle?, How to do a space-partitioning of the Utah Teapot?.

Very brief wikipedia page on Bezier surfaces. I found this nice page about working with Bi-cubic Bezier surfaces.Slides covering Bezier curves and surfaces. This page describes a slightly different Bi-quadratic patch. General spline material. deCastlejau algorithm nicely illustrated on page 16 of this pdf from Bill Casselman's Mathematical Illustrations.

Un-golfed Example in Postscript. This includes a spinning camera which is not necessary.

%!
% this portion sets up camera and viewing parameters and is not counted
%%BoundingBox: 149 202 529 483
%-149 -202 translate
%%BoundingBox: 0 0 380 281

/setuppage {
    %-10 -10 translate
    300 250 translate    % location of the origin on the page
    1 20 dup dup scale div setlinewidth   % scale up, but keep linewidth the same
    1 setlinejoin                         % use straight joins, no miters
} def

/params {
    /R 10 def
    /H 5 def
    /ang 50 def
    /I3 3 ident def
    /Eye [ 0 0 40 ] def     % Eye vector from camera
    /light [ 10 10 5 ] def   % light vector
    setCam
    /preview? true def
} def

/setCam {
    /Cam [  % Camera position
            ang sin R mul  % x
            H              % y
            ang cos R mul  % z
    ] def
    /Theta [  % Camera orientation
            ang 180 add %ang 180 sub   % pan
            H R atan %neg %0 %H R atan neg %60 add   % tilt
            90 %-60 %10    % twist
    ] def
    /Rot makerot def
} def

% count begins here:

/main {
    setuppage
    params

    /f (teapot) (r) file def % read teapot data
    /patch [ f readlist ] def  %    =  patch data
    /vert [ f readlist ] def   %    + vertex data

    /th 90 rotx def
    /vert [ vert { th matmul 0 get } forall ] def

    %lookup vertices, construct new 'flattened' patch list
    /patch [ patch { [ exch { 1 sub
            vert exch get } forall ] } forall ] def

    preview? { patch { drawpatch } forall } if
    4{ /patch[ patch{ splitcols }forall ]def
            preview? { patch { drawpatch } forall } if
    }repeat
    4{ /patch[ patch{ splitrows }forall ]def
            preview? { patch { drawpatch } forall } if
    }repeat

    (patches divided, building bsp)= flush
    patch makebsp /bsp exch def
    preview? { patch { drawpatch } forall } if

    0 { bsp splitbsp } repeat  % split patches in the bsp

    (bsp built, begining loop)=
    {
            bsp drawbsp
            showpage setuppage
            /ang ang 10 add def
            setCam
            %exit
    } loop
} def

(mat.ps) run
/elem { 3 1 roll get exch get } bind def % M i j  .  M_i_j
/div { dup 0 eq { pop pop 100000 }{ div } ifelse } bind def

/planelist [  % list of planes defining the space partition
    .1 .05 4 { /x exch def   % planes at distances [.1 .. 4] step .05
            [ 1 0 0 x ]      % yz planes
            [ 1 0 0 x neg ]
            [ 0 1 0 x ]      % xz planes
            [ 0 1 0 x neg ]
            [ 0 0 1 x ]      % xy planes
            [ 0 0 1 x neg ]
    } for
] def

/tok { token pop exch pop } bind def
/s { (,) { search { tok 3 1 roll }{ tok exit } ifelse } loop } bind def
/readlist{ token pop {[ f 100 string readline pop s ]} repeat } bind def

/makerot {
    Theta 0 get roty %pan
    Theta 1 get rotx %tilt
    Theta 2 get rotz %twist
    matmul matmul
} def

/proj {
    %Model matmul 0 get                        % perform model->world transform
    Cam {sub} vop                  % translate to camera coords
    Rot matmul                     % perform camera rotation
    0 get                          % extract vector from 1x3 matrix
    aload pop Eye aload pop  % extract dot x,y,z and eye xyz
    4 3 roll div exch neg          % perform perspective projection
    4 3 roll add 1 index mul
    4 1 roll 3 1 roll sub mul exch % (ez/dz)(dx-ex) (ez/dz)(dy-ey)
    exch
    %pstack
} bind def

/median { % [x0 y0 z0] [x1 y1 z1]
    {add 2 div} vop % [ (x0+x1)/2 (y0+y1)/2 (z0+z1)/2 ]
} bind def

/decasteljau { % [P0] P1 P2 P3  .  P0 P1' P2' P3'  P3' P4' P5' P3
    {p3 p2 p1 p0}{exch def}forall
    /p01 p0 p1 median def
    /p12 p1 p2 median def
    /p23 p2 p3 median def
    /p012 p01 p12 median def
    /p123 p12 p23 median def
    /p0123 p012 p123 median def
    p0 p01 p012 p0123
    p0123 p123 p23 p3
} def

/splitrows { % [b0 .. b15]  .  [c0 .. c15] [d0 .. d15]
    aload pop % b0 .. b15
    4 {
            16 12 roll decasteljau
            8 4 roll
            20 4 roll
    } repeat
    16 array astore
    17 1 roll 16 array astore
} bind def

/xpose {
    aload pop % 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    15 12 roll % 0 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3
    14 11 roll % 0 4 8 9 10 11 12 13 14 15 1 2 3 5 6 7
    13 10 roll % 0 4 8 12 13 14 15 1 2 3 5 6 7 9 10 11

    12 9 roll % 0 4 8 12 1 2 3 5 6 7 9 10 11 13 14 15
    11 9 roll % 0 4 8 12 1 5 6 7 9 10 11 13 14 15 2 3
    10 8 roll % 0 4 8 12 1 5 9 10 11 13 14 15 2 3 6 7
    9 7 roll % 0 4 8 12 1 5 9 13 14 15 2 3 6 7 10 11

    8 6 roll % 0 4 8 12 1 5 9 13 2 3 6 7 10 11 14 15
    7 6 roll % 0 4 8 12 1 5 9 13 2 6 7 10 11 14 15 3
    6 5 roll % 0 4 8 12 1 5 9 13 2 6 10 11 14 15 3 7
    5 4 roll % 0 4 8 12 1 5 9 13 2 6 10 14 15 3 7 11
    4 3 roll % 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15
    16 array astore
} bind def
/splitcols { xpose splitrows xpose exch xpose } def

/unshift { % [ e1 .. eN ] e0  .  [ e0 e1 .. eN ]
    exch dup length 1 add array % e A B
    dup 0 4 3 roll % e B B 0 A
    putinterval % a B
    dup dup length 1 sub 4 3 roll % B B Bn-1 a
    put
} bind def

/shift { % [ e0 e1 .. eN ]  .  [ e1 .. eN ] e0
    dup 0 get exch dup length 1 sub 1 exch getinterval exch
} bind def

/patch2tri {
    dup [ exch dup 0 get exch dup 3 get exch 12 get ] exch
    [ exch dup 3 get exch dup 12 get exch 15 get 3 2 roll exch ]
} bind def

/color {
    .1 .7
    normal mag 0 lt { /normal normal [-1 -1 -1] {mul} vop def } if
    normal light dot 1 add 2 div %1.10 mul
    sethsbcolor
} def

/calcnormal {
    dup aload pop 1 index % tri p0 p1 p2 p1
    {sub} vop 3 1 roll % tri v12 p0 p1
    {sub} vop cross /normal exch def
} def

/vistri {
    dup 1 get
    Cam {sub} vop
    normal dot 0 lt
    %pop true
} def

/drawtri {
    calcnormal
    vistri {
            {proj} forall
            %2 copy exch =only( )print =
            moveto lineto lineto closepath
            color
            gsave stroke grestore
            fill
            flushpage
    }{ pop } ifelse
} bind def

/drawpatch { patch2tri drawtri drawtri } def

/makebsp { % patchlist  .  bsptree
<< /P [] /PM [] /plane [] /front [] /behind [] /F <<>> /B <<>> >> begin

    dup length 1 le { dup length 0 eq { pop }{
            aload pop
            /P exch def 
            preview? { P drawpatch } def
    }ifelse}{ % length>1
            shift
            /P exch def 
            preview? { P drawpatch } def

            count 1 sub planelist exch
            2 copy exch length 1 sub gt { % patches planes c-1 %no more planes
                    pop pop
                    dup length =only ($)print
                    /front exch def %save patches in node
            }{ % patches planes c-1
                    get /plane exch def

                    { %forall  [ p0 .. p15 ]
                            /T exch def
                            T patch2tri pop transpose
                            { aload pop add add }forall %(x0+x3+x12) (y0+y3+y12) (z0+z3+z12)

                            plane 2 get mul 3 1 roll
                            plane 1 get mul 3 1 roll
                            plane 0 get mul
                            plane 3 get add add add

                            0 lt { /front front
                                    (^)print
                            }{ /behind behind
                            (_)print
                            } ifelse
                            T unshift def
                    } forall
                    ()=

                    (b)print
                    behind currentdict end exch
                    makebsp exch begin /B exch def

                    (f)print
                    front currentdict end exch
                    makebsp exch begin /F exch def

                    /front [] def
                    /behind [] def
            } ifelse %enough planes
    } ifelse %enough patches
currentdict end
} bind def

/drawbsp { % bsptree . -
    begin
    front length 0 ne {
            (F)print
            front{drawpatch}forall
    } if
    plane length 0 eq {
            P length 0 ne { P drawpatch } if
            end
    }{
            Cam aload pop
            plane 2 get mul 3 1 roll
            plane 1 get mul 3 1 roll
            plane 0 get mul
            plane 3 get add add add

            0 lt {
                    B currentdict end exch drawbsp begin
                    P drawpatch
                    F end drawbsp
            }{
                    F currentdict end exch drawbsp begin
                    P drawpatch
                    B end drawbsp
            } ifelse
    } ifelse
} def

/split {
    splitcols
    splitrows
    3 2 roll
    splitrows
} def

/splitbsp { % bsptree . -
    dup length 0 gt {
    begin
    front length 0 ne {
            /front [ front { split } forall ] def
    } if
    P length 0 ne {
            P split /P exch def
            front exch unshift exch unshift exch unshift /front exch def
    } if
    B F end splitbsp splitbsp
    } if
} def

/det { % 2x2 or 3x3 determinant
    dup length 1 index 0 get length ne { /det cvx /typecheck signalerror } if
    1 dict begin /M exch def
            M length 2 eq {
                    M 0 0 elem
                    M 1 1 elem mul
                    M 0 1 elem
                    M 1 0 elem mul sub
            }{
                    M length 3 eq {
                            M aload pop cross dot
                    }{ /det cvx /rangecheck signalerror } ifelse
            } ifelse
    end
} bind def

main

%eof
share
    
I haven't even figured out what the data means. 16 vertices means a 4x4 patch, right? I've looked at Wikipedia and the math formulation is way beyond me. Somewhere I found something like (m-1)(n-1) which I thought might mean it should be considered 3x3 with the outer elements dealt with separately; but I couldn't find the page again after that intuitive (unconfirmed) leap. Do Bezier patches have to be raytraced, or would I be able to get acceptable results with my projected rectangles? (my previous 3d work) –  luser droog Jan 28 '13 at 6:34
    
Most of my previous questions still apply: What makes it a 3D view rather than a 2D one? (The easiest way to solve that one is to require that it take input for camera parameters, but the details require some thought. You need to exclude solutions like rendering a single pixel). What are the minimum requirements of the lighting model (or can I render a black square and claim that my lighting model is the simplest possible)? Can I use the glutSolidTeapot function? –  Peter Taylor Jan 28 '13 at 14:11
1  
Bézier patches can be polygonised with the bounding box property and the de Casteljau algorithm. –  Peter Taylor Jan 28 '13 at 14:12
    
@PeterTaylor Yes, 'camera parameters' is good.... Not sure about the black square yet.... Yes, I think glutSolidTeapot is fine. The boilerplate to use it should be interesting to see. –  luser droog Jan 29 '13 at 7:29
    
Another interpretation of 3D might be to represent an additional dimension beyond the 2 available on the canvas. 2 options: motion (either movie output or the ability to adjust camera parameters for varied views; or stereograms. –  luser droog Jan 29 '13 at 10:13
    
My idea with the camera parameters is that it easily prevents approaches based around hard-coding a compressed image and just unpacking it. Stereograms don't prevent that. –  Peter Taylor Jan 29 '13 at 12:02
    
@PeterTaylor Agreed. I suppose I can just mention motion and stereograms, and some might be inspired to add those. –  luser droog Jan 30 '13 at 0:38
    
@PeterTaylor Perhaps the same solution can apply for the lighting: require it to accept parameters for a light vector, and a quality/resolution parameter. For my polygon example, quality could control the number of subdivisions. A raytracer could use it to determine resolution. –  luser droog Jan 30 '13 at 11:56
    
Augh! Maybe just a side view to avoid occlusions altogether! ... But then there'd be no shadow either. –  luser droog Feb 9 '13 at 4:53
    
Hm. There's an alternate formulation in Jim Blinn's A Trip Down the Graphics Pipeline. I'm inclined to allow it, but I don't feel like typing it in. –  luser droog Feb 9 '13 at 6:27
    
Thinking about how I would implement this in GolfScript is behind my suggestion of a codegolf on polynomial root finding. I think that I can probably ray-trace it in under 1kB of GolfScript... –  Peter Taylor Feb 22 '13 at 14:23
    
Wow. My prototype isn't golfed at all, but it's 1551 words. I've bought and stopped reading so many books on raytracers, I think I've got some kind of mental block preventing my understanding of it. So I look forward to seeing your solution (& explanation?). I'm hoping to clean-up the spec and reopen pretty soon. I just need to calculate planes cutting the intersections at the handle and spout for my example. –  luser droog Feb 23 '13 at 6:14
    
Re your latest edit: scan-line rasterisation isn't hidden surface removal. Did you mean z-buffer? (FWIW you can often get away with doing scan-line rasterisation without z-buffer provided you order your triangles appropriately, but this will sometimes cause glitches). –  Peter Taylor Feb 25 '13 at 12:55
    
Also, when you say "arbitrary objects", do you really mean "arbitrary objects constructed from cubic Bézier patches" or something similar? Personally I was thinking of doing the teapot using rational B-splines in homogeneous coordinates to get a true surface of revolution, but it's certainly slightly simpler to skip the homogeneous coordinates because you can ray-trace by pure subdivision rather than having to solve 18th degree polynomials. –  Peter Taylor Feb 25 '13 at 12:58
    
Thanks. s/scan.*tion/z-buffer/. ... You can use a different construction, just say what it is. –  luser droog Feb 25 '13 at 18:18
add comment

Blockly FizzBuzz Golf!

Put together a FizzBuzz with Blockly, with the goal being least amount of blocks.

Answers given as a screenshot or the generated javascript code?

share
    
Something like this? Links are also a good idea :) –  tomsmeding Apr 6 '13 at 12:42
add comment

GSLint

This is not yet a fully fledged question, but specifying it will be time-consuming, so I want opinions on whether it has potential.

The task would be a lint tool for (a subset of) GolfScript. It would essentially require typing a GS program and then warning of places where it can't be typed. E.g. is that = an equality test or an array lookup? If the latter, warn that it could leave nothing on the stack.

It wouldn't require implementing an interpreter, but it would probably require learning enough GS to write it badly. It would probably have to be a code challenge rather than a code-golf, because it would be a chunky problem per se. Winning criterion probably related to the number of test cases it can handle without giving up on typing them, with a competitive element of allowing implementers to propose test cases.

share
add comment

The One with Two Parts

The aim of this challenge is to create a pair of functions which scramble and unscramble any given piece of text.

Part 1

In part one you post your scrambling function, along with the length in characters and language of your unscrambling function (but NOT its code). The length of the scrambler does not affect your score so you needn't golf it unless you want to. The two functions may be written in different languages if you wish.

Input/Output

The scrambling function should take one argument only - a string containing the input text - and return a string containing the scrambled text. The unscrambling function should also take only one argument - the scrambled text - and return the original text. The input text will be limited to characters in the ASCII set range from 0 to 127.

Part 2

In part two you try to beat your opponents' scores for their unscrambling functions. You MUST use the language they specify for their unscrambler in part one. Please give just one answer to this question containing all your unscrambling functions making it clear which question in part one each function unscrambles (maybe each answer in part one should give its scrambler a name for identification?).

Once the closing date (TBA) has passed all participants should post their unscrambling functions in their answer to part one to prove the length, language and functionality of their function.

Scoring The participants score will be calculated as follows: (unscrambler length from part one) - (shortest unscrambler length from part two). The participant with the lowest score wins and will have their answers accepted on both parts of the challenge. To be eligible to win a participant must have taken part in both parts of the question.

Example

In part 1:

  • Bob posts a Python answer and says his unscrambler is a 165 character Python function.
  • Fred posts a GolfScript answer and says his unscrambler is a 59 character GolfScript function.
  • Joe posts a JavaScript answer and says his unscrambler is a 180 character PHP function.
  • Jim posts a Ruby answer and says his unscrambler is 163 character Ruby function.

In part 2:

  • Bob posts an 82 character GolfScript function to unscramble Fred's scrambled text. He also posts a 175 character PHP function to unscramble Joe's scrambled text.
  • Fred posts a 181 character PHP function to unscramble Joe's scrambled text.
  • Joe posts a 150 character Python function to unscramble Bob's scrambled text.
  • Jim posts a 156 character Python function to unscramble Bob's scrambled text. He also posts a 91 character GolfScript function to unscramble Fred's scrambled text.

The scores:

  • Bob scores 165 - 150 = 15
  • Fred scores 59 - 82 = -23
  • Joe scores 180 - 175 = 5
  • Jim scores 163 - 0 = 163

so Fred wins.

Miscellaneous

I suggest that the closing date be two weeks after the challenge begins, and that unscramblers be posted to part one within 48 hours of closing date in order to be eligible.

share
    
Are there any rules regarding scrambling? i.e. is "Stockholm"->"Stockhoml" a valid scramble? (it may not matter, but I'm curious. And to be clear, the scoring is the difference between your opponent's unscrambler length and your own for the same language? –  Gaffi Jul 16 '12 at 16:39
    
@Gaffi No, you scramble however you want. If you want to just output the text as given that's ok, but you probably won't win with that strategy. The aim is to do it in a way that is easy for you to unscramble but difficult for all the others. That way your score will be smaller. Yes, the score is the difference between your score and the score of the best of your opponents' attempts. I'll add an example to make that bit clearer I think. –  Gareth Jul 16 '12 at 21:27
    
I think this gives an advantage to people who use (relatively) obscure languages. If the scrambler is written in J and the descrambler in GolfScript then only people who know both can realistically attempt a descrambler. (NB the rules don't say how the score works if no-one attempts a particular unscrambler). –  Peter Taylor Jul 17 '12 at 6:59
    
I did consider saying that programs that had no attempts at beating them were not eligible to win, but then I thought that if they were scored as though the shortest attempt to beat them was 0 then they wouldn't have much of an advantage. I'll add that into the example scoring. What do you think? I want to encourage answers that are clever or well obfuscated rather than written in Malbolge or something like that. –  Gareth Jul 17 '12 at 7:28
1  
Does it mean that since no one attempts to solve Jim's Ruby challenge his chances are minimal that he'll win? That would discourage complicated scramblers or difficult languages. –  Howard Jul 17 '12 at 17:12
    
@Howard As it stands, yes that's how it would work. The alternative, as Peter Taylor points out, is that people using obscure languages have an advantage. I'm not sure how else I might score unscramblers that no-one has attempted to beat. Maybe give them a score of 0? Please, if you or anyone else has any suggestions for making the challenge as inclusive as possible, let me know. –  Gareth Jul 17 '12 at 17:51
add comment

Lightbox Generator (Posted)

share
1  
I recommend paring the challenge down to its barest essentials, meaning, design a lightbox that does the following things. All exporting and HTML is better left for another challenge or two. –  David Carraher Sep 5 '12 at 3:48
add comment

Take 5! / 6 Nimmt!

6 Nimmt! is a pretty nice (imho) card game we often play with friends. Takes almost zero time to set up and is quick to play as well. The rules are outlined in the Wikipedia article for those who do not know them.

Apart from a little luck there is also strategy involved in playing it, namely how to choose cards you want to add to a stack and a few other decisions.

I would propose a contest for creating a strategy for that game, similar to the Iterated Prisoner's Dilemma we had once. Given that there are different complexities involved there could be also a few different tiers of strategies:

  1. Simple strategies which just take the cards currently visible into account.
  2. Complex strategies which have knowledge of all cards already played in the game. Those can obviously know what cards are still available and act accordingly. They can also keep track of how many penalty points each player has and try making others lose.
  3. Variation 2 from the Wikipedia article which involves picking cards for the own hand instead of being dealt them randomly. This could probably be separate from the main competition because picking a good hand is different from playing a good game with a given hand. So maybe the picked cards from such a strategy could be run through games with the best strategies from 1. and 2. to determine which is the best.

I'm not entirely sure whether it'd be a good contest but given the nature of the game it could be very interesting. The card to choose for a round does not necessarily depend on only those cards in stacks on the table but instead also on the cards the others are likely to play in the same situation and using that to your advantage. When playing with humans it is certainly helpful to know them and how they play. Strategies from 2. could also try figuring out the competing strategies and target them directly.

If it comes to it, I'd write a thorough task description as well as figure out a usable API for the player programs and a tool that runs contests. Skeleton programs in various languages would be provided to allow for quick tinkering with strategies without first spending half an hour writing parsing code (this was one of my main problems with the Prisoner's Dilemma contest).

share
    
Difficult to judge fairly if there are too many entrants to just throw them all in together. Do you take each possible subset of 10 entrants and play 100 games? –  Peter Taylor Dec 29 '12 at 18:54
    
Also, you should explicitly permit or forbid the submission of multiple entries with a view to cooperating to give one of them a boost at the cost of the other. –  Peter Taylor Dec 29 '12 at 18:54
    
I'm not sure it's that easy to specifically target other players directly. There can be some cases where you can cause one of them to take penalty points but I think it's rare that you can choose voluntarily between all your enemies. So I guess any element that specifically targets other strategies (either beneficially or not) is very likely quite rare. This is different from the IPD where you can influence the other player's score (and your own) very directly. Most penalty points are usually taken because of a lack of other cards to choose from. –  Joey Dec 30 '12 at 0:30
    
As for the contest ... the game works with up to 10 players, so I guess, depending on the number of strategies, one could either go through all subsets or just play games with varying numbers of players so that each strategy played the same number of games. Also, due to the randomness element, there need to be a few games for each set of players, I guess. –  Joey Dec 30 '12 at 0:35
add comment

Take out the Trash!

Your task is to garbage collect a small heap, input as a multi-line block of hexadecimal(ASCII)-encoded bytes.

The heap contains "index" chunks, the first at location zero. An index chunk consists of a 4-byte location of the next index in the chain (the final index chunk points back to location zero), followed by 10 4-byte locations of the heads of trees. The final chunk may not be completely filled, but you may stop at the first reference to location zero.

The first 4-byte location in the first index chunk is the head of the free list. All locations in the index chunks except for the head of the free list comprise the root set. The root set comprises all the tree heads which we wish to traverse.

TODO. Specify the tree node.

Output is the same multi-line block of hexadecimal with all non-reachable locations linked into the free-list, in ascending order.


Questions.

Ditch the free-list and zero-fill the garbage? DEADBEEF?

Do base-36 and have the test-cases reveal a secret message? or ASCII-ART?

Bonus for compacting the heap/compacting the index chunks?

This question is inspired by this personal challenge logged in comp.lang.postscript which, in retrospect, I wish I had cross-posted to comp.lang.c.

share
add comment

Write a compiler/interpreter for ...

Inspired by the lisp challenge here.
It is a series of puzzles.

I don't like to see a simple eval solution, so:

  • interpreting the language is fine
  • translating the language to a different language is fine.

I think this is specific for each language.

Only the syntax and the basic commands.
Also specific.

Winning criteria should not be code golf.
The goal should be that you can "learn" an other language by looking at the code.

Languages that might be good candidates:

  • Lisp
  • APL
  • J
  • Brainfuck (already posted)
  • Whitespace
  • Forth
share
    
This only works for languages which are small and well defined. BF fits those criteria. Whitespace does too. The others may not. Lisp and Forth have so many dialects that you would have to specify exactly which dialect to support; Lisp, Forth, APL and J might have too many built-ins to fit in an answer: there are character limits. –  Peter Taylor May 12 '13 at 15:16
    
You don't have to provide all the built-ins, but that is why it is here. –  Johannes Kuhn May 12 '13 at 15:38
add comment

Countability of Sets of Finite Sets

The aim of this challenge is to code-golf a program which returns an iterator that will iterate over all possible non-empty finite sets of positive integers.

So if running long enough, this iterator should eventually touch on {1}, {2, 5}, {3, 6, 112} (ie none of these should occur "at infinity")

You may choose the order in which you iterate over these sets, but the order must satisfy the following requirement:

Under a particular ordering, if S is the i'th set to be returned by the iterator, then we shall call i the index of set S.

Let a restriction (k,T) be an assertion about a set S that says S has size k and T is a subset of S.

For a given restriction (k,T) and iterator IT, let the restricted iterator be the iterator which takes sets returned by IT and filters out sets that don't satisfy the assertion, iterating only over the ones that do. In other words, if IT iterates over the sequence of all sets, the restricted iterator iterates over the subsequence satisfying (k,T). Now if S is the n'th set returned by the restricted iterator, then we'll call n the restricted index of S with respect to (k,T)

Your ordering must satisfy the property that for any restriction there exists a polynomial P(x) such that for any set satisfying the restriction (with index i and restricted index n), i < P(n)

Note that the following ordering is not acceptable:

{1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} {4} {1, 4} {2, 4}...

This is the sequence that comes from counting 1, 2, 3, 4, 5, 6... and listing the set bits in the binary representation of each number.

This is because the restriction (1, {}) satisfies only the sets {1}, {2}, {3}, {4}... whose index i as a function of their restricted index is i=2^(n-1) which is not bounded by any polynomial


Sandbox Questions

The reason for the strange requirement at the end is to disqualify any variants on the most natural ordering which simply counts upwards from 1 and enumerates the set bits in each number. In this ordering, the n'th set of length-one occurs at index 2^n which is non-polynomial.

I posted this problem originally, but didn't think of the obvious solution and so I left out the final restriction. I'd like to re-post it with the extra restriction. But first I'd like to know what people think. Is there a better way I can word that restriction or a more natural restriction I could impose instead?

share
    
I don't understand the extra restriction, so I can't suggest a rewording, but I can say that it needs one. (In particular: what is k? And what function does T serve? Is it really a parameter of the property?) –  Peter Taylor Jun 18 '12 at 8:25
    
I don't understand it either. Maybe a sample of an ordering, satisfying the requirement, and another one, violating it, would help. –  user unknown Jun 18 '12 at 15:31
    
I understand the restriction now, although I haven't worked through the full implications. Does allowing T to be non-empty make a significant difference at all? –  Peter Taylor Jun 19 '12 at 6:52
    
I don't know. It may not. I guess the size part is the important part. I was just thinking that the ordering should be such that you run into all kinds of sets frequently. –  dspyz Jun 20 '12 at 7:17
add comment

Bad Voice Recognition Calculator

Overview:

Let's say you've decided to operate your computer using voice recognition software, but unfortunately you did a horrible job researching the various products out there and chose a package that does not recognize numbers as numerals, only words. (i.e. "one" (spoken) == "one" (typed), not "1".) Rather than spend more money to get another option, you decide to make do. Now you want to use the computer's calculator, but this poses a problem, since your machine doesn't know how to add "one plus one".

Objective:

Implement a basic calculator that will read in a string of the written-out equation, perform the correct calculations, then return the result in its text form. Your code should be as short as possible; this is code golf.

Rules/Constraints:

  • Input/output will be using your preferred method (STDIN, ARGV, etc.).
  • Your calculator must be able to handle input and output within the billions (non-inclusive) -1,000,000,000 < i < 1,000,000,000, but you may expand to more if you wish.
  • Decimal values and/or parts must be accepted (0 < i < 1) up to 3 places/digits.
    • When calculating answers, proper rounding must be used, so "three point one four one five nine two six" must be returned as "three point one four two".
  • Basic calculator functions required:
    • "Add"/"Plus"/"Sum"/"And" (+)
    • "Subtract"/"Minus"/"Remove" (-)
    • "Multiply"/"Times" (*)
    • "Divide"/"Divided"/"Divide by"/"Divided by" (/)
    • "Raise"/"Exponent"/"Power"/"To the power of" (^)
    • "<Base>Root"/"<Base>Radical" (√)
    • "Point"/"Decimal" (.)
    • "Pi" (π)
  • All strings in the list above must be accounted for in your code, capitalization does not matter.
  • Numbers may be presented as their full value ("one thousand") or by digit (one zero zero zero).
  • Negative numbers may be assigned using "Minus" or "Negative".
    • The string "Minus" bust be accounted for as an operator and identifier. (see example)
  • "And" is only acceptable as an operator, not as part of a named number.
    • "one hundred and one"
    • "one hundred one"
  • "a" or the absence of a number does not equate to any number; all numbers will be explicitly accounted for in the program input.
    • "a hundred" does not equate to "one hundred" and is not a valid input.
  • No more than 2 terms will be used.
    • "one plus one minus one" will not be implemented.
  • If an invalid input is supplied, your function/program should handle the error and exit gracefully with an error description.

Example I/O:

  • "one add one" --> "two"
  • "five thousand thirty four subtract ten thousand six hundred" --> "negative five thousand five hundred sixty six"
    • Alternatively: "five zero three four subtract one zero six zero zero"
  • "three root twenty seven" --> "three"
  • "ten minus minus ten" --> "twenty"
    • Alternatively: "ten subtract negative ten"

Sandbox Questions:

  1. Is this too basic/complicated? (I'm assuming some languages will handle this much more simply than the method I have in my head...)
  2. Does the title fit?
  3. Are there any constraints that should be added/lifted?
  4. Are any more examples needed for clarification?

Thanks for your input, guys!

share
    
Not everyone says numbers the same way. Does the parser have to treat the following as equivalent? "negative one hundred five", "minus one hundred five", "negative one hundred and five", "minus one hundred and five", "negative a hundred five", "negative a hundred and five", ...? –  Peter Taylor Jun 15 '12 at 15:12
    
@PeterTaylor I had had a similar thought re: operators. ("plus" versus "add", etc.) I think it would be more interesting to account for all, but given the wide variety of possible inputs, it may generally be better to limit the options to a specifically defined set (which I have yet to define). –  Gaffi Jun 15 '12 at 15:18
    
@PeterTaylor I've added some of these details. Please let me know if there's anything unclear about them. –  Gaffi Jun 15 '12 at 16:10
    
I don't spot any ambiguities in the parser. There is still an ambiguity relating to decimals, though. What precision should be used? Also, I notice now that there's no winning condition. Is this intended to be code-golf? (Ugh - tons of strings which will have to be hard-coded in most languages. I expect Perl has a suitable parser already in CPAN, though...) –  Peter Taylor Jun 19 '12 at 9:03
    
@PeterTaylor I don't know where I went... I've updated the spec. re: decimal places and objective. –  Gaffi Jun 29 '12 at 13:24
add comment

Huffman Decoding

Write a programm which takes two strings as input and prints a text.


The first argument is a Huffman Tree, serialized in the following format:

  • every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
  • <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
      d e

where a would have the key 00, b 01, c 10, d 110 and e the key 111.


The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

  • the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
  • the bitstring is broken up into 6-bit chunks and mapped to this characters
  • if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
  • - : the last chunk was five bits long
  • = : the last chunk was four bits long
  • =- : the last chunk was three bits long
  • == : the last chunk was two bits long
  • ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-

Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

share
    
It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. –  Peter Taylor Oct 8 '12 at 16:23
add comment

Embracing Greenspun's 10th Law

Your challenge is to implement an embeddable (single-file library) LISP interpreter for your favorite language. While this is not code-golf, brevity is encouraged for easier reading (and scrolling).

The interface with the host language shall be a function which receives a string containing a LISP expression and returns a string containing the result. If the language is C, the prototype shall be

char *lispeval(char *);

or its equivalent.

TBD. Syntax (Special Forms or no? Stick with Micro Manual 1.5 (link via related SO Q)?), supported techniques (currying, tail-recursion, GC?). Host-function callbacks?

And Winning Criteria. Is it possible to do it this way:

1 The language "most foreign" to lisp. As in: between two languages, one may offer a list abstraction and the other may require you implement a linked-list and manage the nodes, the latter ranks higher.

2 Ties by crit. 1 broken by "clarity of expression", a reverse obfuscation test. Measured by syntactic deviation (how many tree-ops) from a cited example in the language's defining document.

Or is that totally bonkers?


I like writing (and reading about) small interpreters, so I'd like to see more [interpreter] questions. These are some ideas that build upon each other (like the Minsky Register Machine questions, and the Crossword Puzzle questions):

  • Implement a simplified HDL
  • Implement a simplified FPGA simulator or Macro-cell Array using the output from the HDL one.

Cover bases 1 and 2 with Tofu, a relay network HDL and simulator. The Reference version is Bona Fide obfuscated: http://www.ioccc.org/years.html#2006_birken !

  • Implement a simplified ALU for the FPGA Better yet, output an ALU design in Tofu satisfying a specification file (register size (how about 4 or 8 bit), more?).

  • Implement a simplified Instruction Decoder for the FPGA

  • Implement a simplified CPU using the ALU and Decoder, tying them to some sort of memory.

  • Implement a simplified Command-Line OS for the CPU

  • simple Assembler
  • simple Compiler (FALSE language? or is it short enough already?)
  • more involved OS using the Compiler

I don't really know enough about any of these areas to pose the problems properly yet (golf or just puzzle?), but these are the kinds of things I'd like to see. So please steal from me if you can flesh it out faster. Put together, they form a tracer bullet through the heart of computer science, from the abstract manipulation of symbols down to their physical manifestation as a dynamic path of electric current.

share
    
LISP: the parser may be simple, but if you're asking for a lot of libraries that could be unfun. Winning criterion is tricky - the current one isn't as objective as it could be. –  Peter Taylor Oct 23 '12 at 8:46
    
I think just a barebones setup would suffice, but with reasonably-sized identifiers, and a shorthand for QUOTE would be nice. ... Agreed. I'm not thrilled with it; the goal is something like "does the job with the least resources (for those who need it most) in the most pedagogically elegant manner. I know it lacks precision, but I want it to be noble, somehow. :) –  luser droog Oct 23 '12 at 9:06
    
I tried writing a lisp interpreter but I had trouble figuring out how to read and write. –  luser droog Jan 24 at 7:52
    
add comment

Good Polish/Bad Hungarian

Got nothing, but isn't that a great title?

Suggestions welcome.

share
add comment

Compile BF to TM

Your task is to write a compiler accepting a Brainfuck program (previous challenge: Interpret Brainfuck, wikipedia: Brainfuck) as input and outputting a Turing Machine which produces identical output when supplied with the same (correct) input.

You may select the output format from among the various formats accepted by the answers to Turing Machine Simulator.

The following links may also be useful.
An introduction to programming in BF
BF is Turing-complete
Programming a Turing Machine
Programming Praxis: Turing Machine Simulator

Equivalently, you may write a Brainfuck interpreter in TM, or any partial compilation/interpretation which results in a TM program as described above.

If we consider squares of the TM tape to represent bits (blank=0, mark=1) of the BF memory, then eight squares represent a cell. Each BF instruction translates to a minimum of 8 states of the Turing Machine.

'>' "advance" (++ptr) could be implemented by eight states (sixteen transitions):

adv8 _ adv7 R _
adv8 1 adv7 R 1
adv7 _ adv6 R _
adv7 1 adv6 R 1
adv6 _ adv5 R _
adv6 1 adv5 R 1
adv5 _ adv4 R _
adv5 1 adv4 R 1
adv4 _ adv3 R _
adv4 1 adv3 R 1
adv3 _ adv2 R _
adv3 1 adv2 R 1
adv2 _ adv1 R _
adv2 1 adv1 R 1
adv1 _ link R _
adv1 1 link R 1

where 'link' represents the first state of the following instruction.

'<' "rewind" (--ptr) can be implemented similarly by making leftward movements and rewriting the same symbol just read.

'+' "increment" (++*ptr) can be implemented by a ripple-carry from the Least Significant Bit to the Most Significant Bit, borrowing "rewind" states to back-up to normal position. If the LSB is on the left, it would look something like this:

inc8 _ link N 1
inc8 1 inc7 R _
inc7 _ rew1 N 1
inc7 1 inc6 R _
inc6 _ rew2 N 1
inc6 1 inc5 R _
inc5 _ rew3 N 1
inc5 1 inc4 R _
inc4 _ rew4 N 1
inc4 1 inc3 R _
inc3 _ rew5 N 1
inc3 1 inc2 R _
inc2 _ rew6 N 1
inc2 1 inc1 R _
inc1 _ rew7 N 1
inc1 1 overflow N 1

where overflow is a HALT state.

For I/O, the simplest way I can think is to place all input on the tape after the memory area, and expand the alphabet to include a symbol indicating the dividing line between the memory portion and the input portion of the tape. In fact, by expanding the cell size to nine squares, this symbol can serve as an input pointer, advancing as the input is consumed. (So "advance" and "rewind" now need 9 states each.) And another new symbol is written in front of the current memory cell to serve as the memory pointer. Inputting a byte therefore consists of schleping each bit over the entire space between the two tape positions with something like this:

input _ set-memptr L _
input 1 set-memptr L 1
set-memptr _ find-inptr R *
find-inptr _ find-inptr R _
find-inptr 1 find-inptr R 1
find-inptr $ schlep-bit R $
schlep-bit _ schlep-blank L _
schlep-bit 1 schlep-one L 1
schlep-blank $ schlep-blank L $
schlep-blank _ schlep-blank L _
schlep-blank 1 schlep-blank L 1
schlep-blank * deposit-blank R *
schlep-one $ schlep-one L $
schlep-one _ schlep-one L _
schlep-one 1 schlep-one L 1
schlep-one * deposit-one R *
deposit-blank _ etc R _
deposit-blank 1 etc R _
deposit-one _ etc R 1
deposit-one 1 etc R 1

where "etc" represents going to get the next bit in similar fashion.

To perform a loop (all BF loops are "while" loops, so the exit control is at the beginning and the end has a simple goto back to the beginning), we need first to check is the current cell is zero,

zero8 _ zero7 R _
zero8 1 body R 1
zero7 _ zero6 R _
zero7 1 left1 L 1
zero6 _ zero5 R _
zero6 1 left2 L 1
zero5 _ zero4 R _
zero5 1 left3 L 1
zero4 _ zero3 R _
zero4 1 left4 L 1
zero3 _ zero2 R _
zero3 1 left5 L 1
zero2 _ zero1 R _
zero2 1 left6 L 1
zero1 _ exit-loop R _
zero1 1 left7 L 1
left7 _ left6 L _
left7 1 left6 L 1
left6 _ left5 L _
left6 1 left5 L 1
left5 _ left4 L _
left5 1 left4 L 1
left4 _ left3 L _
left4 1 left3 L 1
left4 _ left3 L _
left4 1 left3 L 1
left3 _ left2 L _
left3 1 left2 L 1
left2 _ left1 L _
left2 1 left1 L 1
left2 _ loop-body L _
left2 1 loop-body L 1
...
loop-body-final _ zero8 N _
loop-body-final 1 zero8 N 1

So assuming the machine starts at tape-location 0, and the input is on the tape starting at 0 and going to the right, the "startup code" for this arrangement would be

startup _ place$ L _
startup 1 place$ L 1
place$ _ left270000 L $
left270000 _ left269999 L _
...

Jeez! The output is going to be HUGE! It might be better to treat the BF memory as negative-indexed and reverse all the _L_s and _R_s in 'advance', 'rewind', 'increment', and 'decrement'.


Questions:

Bonuses for optimizations? If I can implement this myself and provide a complete example output, The bonus could be "subtract the difference between your program's output for the example input with the example output". So eliminating states would be far more valuable than shrinking the code. One could possibly achieve a negative score!


Edit: Actually I think this is unreasonable unless the Turing Machine is augmented with non-reading (movement-only or epsilon) transitions. Duplicating every letter of the alphabet just to move over one square is just ridiculously painful. That means this challenge won't link-up nicely with the other one. :(

What about, instead of implementing the compiler, just devise a translation scheme (as above) that leads to a smaller output for a trivial sample program (based on calculating, rather than coding)? "Back of the envelope" compiler.

share
    
"How much detail on BF do I need to supply? Can I simply reference the BF question?" A link to almost any site that describes the language will do. –  dmckee Nov 5 '12 at 16:52
    
Winning condition? –  Peter Taylor Nov 6 '12 at 13:43
    
"Longest prefix containing syntactically-correct Malbolge!" :) ... I'd say have none at all. Perhaps the questioner should be required to accept their own example answer? –  luser droog Nov 6 '12 at 18:08
    
@PeterTaylor Apologies for my last comment. I thought we were on my other answer about the [fun] tag. . . . This one would be a golf: shortest code by character count. But I think a clever system of bonuses could make it interesting. –  luser droog Nov 7 '12 at 10:06
    
The "Equivalently, you may write a Brainfuck interpreter in TM" option doesn't play very well with being a code golf - how are you going to count the length of the TM? –  Peter Taylor Nov 7 '12 at 11:15
    
@PeterTaylor Since the TM question specified 5-tuples, I think it's sufficient to count the tuples (== transitions). You can reduce states by increasing the alphabet (or vice versa), but the transitions would remain constant, I think. –  luser droog Nov 8 '12 at 5:25
add comment

Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

Tree of Life after Kirtcher

Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

Eg. http://code.google.com/p/xpost/downloads/detail?name=ve6a.ps
//lotsoflines n = 1 ..12

Mandalas 1 - 12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

Draw the I-Ching Hexagrams in King Wen Sequence.

I suppose I need to implement this first to avoid copyright issues! :)

share
    
The I-Ching one would have to be in standard order to be remotely interesting, and then becomes as much about kolmogorov-complexity as graphical-output –  Peter Taylor Nov 22 '12 at 21:24
    
For the others: images, please! –  Peter Taylor Nov 22 '12 at 21:25
    
I've emailed the owner of the Alchemy pages asking for permission to use his copyrighted images. Awaiting response. –  luser droog Jan 28 '13 at 8:25
add comment

Polygon prefixes

Polygons are named after the number of sides that they have. A pentagon has 5 sides, an octagon has 8 sides. But how are they named? What's the name for a 248-sided polygon?

All polygons are suffixed with -gon. There are specific prefixes for each polygon depending on the number of sides. Here are the prefixes for the lower numbers:

3 - tri
4 - tetra
5 - penta
6 - hexa
7 - hepta
8 - octa
9 - nona
10 - deca
11 - undeca
12 - dodeca
13 - triskaideca
14 - tetradeca
15 - pentadeca
16 - hexadeca
17 - heptadeca
18 - octadeca
19 - nonadeca
20 - icosa

Polygons with 21 to 99 sides have a different system. Take the prefix for the tens digit (found on the left column), the ones digit (right column below), and then stick a "kai" between them to get (tens)(ones)gon.

20 - icosi       | 1 - hena
30 - triaconta   | 2 - di
40 - tetraconta  | 3 - tri
50 - pentaconta  | 4 - tetra
60 - hexaconta   | 5 - penta
70 - heptaconta  | 6 - hexa
80 - octaconta   | 7 - hepta
90 - nonaconta   | 8 - octa
                 | 9 - nona

The 3-digit sided polygons are named in a similar fashion. A 100-sided polygon is called a hectogon. Take the hundreds digit, find it on the column for ones digits, then stick a "hecta" to its right. Now number off the tens and ones like above: (hundreds)hecta(tens)(ones)gon. If the hundreds place digit is a 1, don't put the prefix behind "hecta".

So, given an integer (3 <= n <= 999), return the name of an n-sided polygon. n-gon is not a valid answer :P

As with all code golf, shortest code wins.


Is the description good? Would it be harder if I instead asked for the number of sides, given a name?

share
    
What is a 101-sided figure called? "hectahenagon"? Is "hena" from the column for ones digits you mention? If so, then what is a 111-sided figure called? I'd say "hectaundecagon", but then that comes from a column where "hena" is not present. –  Gaffi Feb 11 '13 at 11:15
    
@Gaffi: Yep, it's hectahenagon, from what Google says. –  beary605 Feb 11 '13 at 16:03
add comment

Self-Golfing Code?

I don't know if I just didn't search hard enough, but I couldn't find any challenge regarding self-golfing code, or rather, any code that can deterministically reduce another set of text code to a much smaller program, yet still compile/run.

For example, take this:

int main() {
std::cout<<"Hello world 1!"<<std::endl;
std::cout<<"Hello world 2!"<<std::endl;
std::cout<<"Hello world 3!"<<std::endl;
std::cout<<"Hello world 4!"<<std::endl;
std::cout<<"Hello world 5!"<<std::endl;
}

And output this (as one possible solution):

#define A std::cout<<"Hello world 
#define B !"<<std::endl;
#define C B A
int main() {
A 1 C 2 C 3 C 4 C 5 B
}

Alternative:

Sub MySub()
Dim aNumber As Integer
Dim someString As String
aNumber = 123
someString = "abc"
MsgBox aNumber
MsgBox someString
End Sub

into (again, as one possible solution)

Sub m()
Dim a As Integer
Dim s As String
a = 123
s = "abc"
MsgBox a
MsgBox s
End Sub

Do we have a challenge for this?

If not, here are some rules I envision:

  • Golfing code need not be in the same language as code to be golfed.
  • Since compilers/running of code varies, newly golfed code must still run under same environment.
  • Possible challenge scoring (multiple options -- thinking code golf):
    • 1: Shortest golfing code wins (not my favorite, since you can minimally shorten the base code, yet still write the shortest program).
    • 2: Shortest output of a set of pre-defined code (potentially limiting if participants are unfamiliar with the options available)
    • 3: Combination of length of golfing code and the output result of the same as input. (Ratio, summation, etc.) -- This I think is my preferred option.
    • 4: Multi-player Ratio of golfed size of other participants' own code versus their original submission. (Similar limitations to that of point #2.)
share
    
Sounds more like an auto-golfer than obfuscation. Seems like it would be very hard to make it a fair contest unless you pick a language to golf, and even then it had better be a simple language (no platform dependency issues or compiler options). –  Peter Taylor Feb 13 '13 at 15:15
    
@PeterTaylor My examples are golfing, but either would work. Perhaps golfing would be simpler, then? I agree that the options for usable languages makes this a bit messy... Would one challenge per language be acceptable? (i.e. aligned with most challenges that are language-agnostic) –  Gaffi Feb 13 '13 at 17:36
1  
Language-agnostic to mean means that you can write a program to do it in any language. Since the language to be golfed can be different from the submitted program, I don't see any incompatibility between making the problem "Write a program to golf Piet" and being language-agnostic. –  Peter Taylor Feb 15 '13 at 0:18
    
@PeterTaylor So then you see no problem with one question per language on which to operate? Are there any proposed scoring algorithms you particularly like/dislike? –  Gaffi Feb 15 '13 at 12:02
    
That depends on what you mean. If you're planning to post 10 questions at once, yes, that would be a problem. But I don't see a problem with posting a well-defined "Auto-golf Piet" and following it up two months later with "Auto-golf Perl 5". –  Peter Taylor Feb 16 '13 at 10:19
    
Scoring is an issue. The halting problem means that it's impossible to write an optimal solution, so the scoring must take into account how good the solution is. I think option 3 is the best, and you'll want a big test set (maybe a few kB taken from a real-world open source project) with coverage of the language features. –  Peter Taylor Feb 16 '13 at 10:22
add comment

DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>


I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

share
add comment

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .