title: Compute the Hausdorff Distance

text:
# Question
Title: Compute the Hausdorff Distance
# Introduction

The Hausdorff distance measures the difference between two subsets of a metric space. Intuitively, a metric space is just some set with a built-in distance function; in this challenge, we will use natural numbers with the ordinary distance `d(a, b) := abs(a - b)`. The Hausdorff distance between two non-empty finite sets `A` and `B` is given by

```
max(max(min(d(a, b) for b in B) for a in A),
    max(min(d(a, b) for a in A) for b in B))

```

in Python-like notation. The Hausdorff distance can be computed by finding the element of `A` for which the distance to the nearest element of `B` is maximal, and the element of `B` for which the distance to the nearest element of `A` is maximal, and then taking the maximum of these distances. In other words, if the Hausdorff distance is `d`, then every element of `A` is within distance `d` of some element of `B`, and vice versa.

# Input

Your input is a single list of integers. It only contains the elements `0,1,2,3`, which signify whether the given index of the list is an element of neither `A` nor `B`, only `A`, only `B`, or both `A` and `B`. For example, the input `[0,1,1,0,2,3]` means that `A = {1,2,5}` and `B = {4,5}`, if we use 0-based indexing (which makes no difference, as our metrics are translation invariant).

# Output

Your output is the Hausdorff distance between `A` and `B`; in the above example, it is `3`. If either set is empty, then the distance is not defined, and you shall return `-1`.

# Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
[] -> -1
[0] -> -1
[0,1,0] -> -1
[2,0,0,2] -> -1
[0,1,2,3] -> 1
[0,3,3,0,0,0,0,3] -> 0
[1,0,0,1,0,0,1,3,1] -> 7
[1,0,0,0,0,3,0,0,0,0,2] -> 5
[0,1,1,3,1,3,2,1,1,3,0,3] -> 2
[2,2,2,1,2,0,3,1,3,1,0,3] -> 3
[1,3,0,2,0,2,2,1,0,3,2,1,1,2,2] -> 2
[1,0,1,1,2,0,1,2,3,1,0,0,0,1,2,0] -> 4

```

# Answer
> 7 votes
# CJam, ~~53~~ ~~52~~ ~~46~~ ~~38~~ 37 bytes

```
3,q~f{f&:L,{L=},}$~ff{-z}_z+::e<W+:e>

```

Takes input on STDIN as a CJam style array:

```
[0 1 2 3]

```

Here is a test harness which converts all the test cases to this format and runs the code on them. Although the results are in the input field, they are not used by the code (remove them if you don't trust me :)).

## Explanation

First, we parse the input to get the two sets A and B:

```
3,q~f{f&:L,{L=},}$~
3,                  "Push [0 1 2]. 1 is for A, 2 is for B, and 0 we can luckily ignore
                     as we'll see later.";
  q~                "Read and evaluate the input.";
    f{          }   "Map this block onto the [0 1 2] array, copying in the input for
                     each iteration.";
      f&:L          "Take the bitwise AND with each element of the input and store the
                     result in L.";
          ,{  },    "Get the length N, and filter the range [0 .. N-1] by evaluating
                     the block for each element.";
            L=      "Check if the bitwise AND at that index yielded something non-zero.
                     This gives an empty array for 0, A for 1 and B for 2.";
                 $  "Sort the three arrays. This has two important effects: a) it moves
                     the empty array resulting from 0 to the front, and b) if only one
                     of A and B is empty, it moves the non-empty one to the end.";
                  ~ "Unwrap the array, dumping all three sets on the stack.";

```

And now we find the absolute differences and select the max of the mins:

```
ff{-z}_z+::e<W+:e>
ff{-z}             "Turn A and B into a matrix of absolute differences.";
      _z           "Duplicate and transpose.";
        +          "Add the two together, so I've got one row of distances for
                    each element in either A or B.";
         ::e<      "Find the minimum of each row.";
             W+    "Add a -1 in case one set was empty.";
               :e> "Get the overall maximum.";

```

Note that we've kept the empty array resulting from the initial `0` at the bottom of the stack all the time, but empty arrays don't contribute anything to the output.

# Answer
> 5 votes
# CJam, ~~57 56~~ 52 bytes

I think this can be golfed a bit, but here goes:

```
q~ee_{W=2%},\{W=1>},]0ff=_W%]{~ff-{:z$1<~}%W+$W=}/e>

```

Input goes in like a CJam styled list, eg.

```
[1 0 0 0 0 3 0 0 0 0 2]

```

> 5

**How it works**:

The code is split in two parts:

Parsing the input into the lists `A` and `B`:

```
q~ee_{W=2%},\{W=1>},]0ff=_W%]
q~                               "Eval the input array";
  ee                             "Enumerate and prepend index with each element. For ex:
                                  [5 3 6]ee gives [[0 5] [1 3] [2 6]]";
    _{W=2%},                     "Make a copy and filter out elements with value 1 or 3";
            \{W=1>},             "On the original, filter elements with value 2 or 3";
                    ]            "Wrap stack in an array. Stack right now contains
                                  enumerated A and B in an array";
                     0ff=        "Get the index of the enumerated arrays. Stack is [A B]";
                         _W%     "Make a copy and swap order. Stack is now [A B] [B A]";
                            ]    "Wrap this in an array";

```

Performing the required actions on the two pairs of `A` and `B`:

```
{~ff-{:z$1<~}%W+$W=}/e>
{                  }/            "Run this loop for both the pairs, [A B] and [B A]"
 ~ff-                            "Unwrap [A B] and take difference of every pair";
     {      }%                   "For each row in the matrix difference";
      :z$                        "abs each term and then sort";
         1<~                     "Take only the first element of the array";
              W+                 "Add -1 to compensate for an empty array";
                $W=              "Take max";
                     e>          "Take max of the two maximums";

```

Try it online here

# Answer
> 5 votes
# Lua, 235 bytes

Definitely not a winner, but at least a fun challenge.

```
A={}B={}c={}d={}m=math p=m.min q=m.max u=unpack for k=1,#arg do for h=0,1 do if
arg[k]/2^h%2>=1 then A[#A+1]=k for i=1,#B do l=m.abs(B[i]-k)d[i]=p(d[i]or
l,l)c[#A]=p(c[#A]or l,l)end end A,B=B,A c,d=d,c end end
print(q(q(-1,u(c)),u(d)))

```

Input works like so:

```
lua hausdorff.lua <space-separated-sequence>

```

...and here's a test script:

```
local testcase = arg[1] or 'hausdorff.lua'
print('testing '..testcase)
local function run(args)
    return function(expected)
        local result = tonumber(
            io.popen('lua.exe '..testcase..' '..args):read'*a':match'%S+')
        print(args..' -> '..expected..' :: '..result)
        assert(result == expected,
            ("for input %q expected %s but got %s"):format(
                args, expected, result))
    end
end
run''(-1)
run'0'(-1)
run'0 1 0'(-1)
run'2 0 0 2'(-1)
run'0 1 2 3'(1)
run'0 3 3 0 0 0 0 3'(0)
run'1 0 0 1 0 0 1 3 1'(7)
run'1 0 0 0 0 3 0 0 0 0 2'(5)
run'0 1 1 3 1 3 2 1 1 3 0 3'(2)
run'2 2 2 1 2 0 3 1 3 1 0 3'(3)
run'1 3 0 2 0 2 2 1 0 3 2 1 1 2 2'(2)
run'1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0'(4)

```

...produces...

```
testing hausdorff.lua
 -> -1 :: -1
0 -> -1 :: -1
0 1 0 -> -1 :: -1
2 0 0 2 -> -1 :: -1
0 1 2 3 -> 1 :: 1
0 3 3 0 0 0 0 3 -> 0 :: 0
1 0 0 1 0 0 1 3 1 -> 7 :: 7
1 0 0 0 0 3 0 0 0 0 2 -> 5 :: 5
0 1 1 3 1 3 2 1 1 3 0 3 -> 2 :: 2
2 2 2 1 2 0 3 1 3 1 0 3 -> 3 :: 3
1 3 0 2 0 2 2 1 0 3 2 1 1 2 2 -> 2 :: 2
1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0 -> 4 :: 4

```

# Answer
> 4 votes
# Pyth, ~~43~~ ~~40~~ ~~39~~ 38 bytes

```
J+m0yQQLq3.|Fb?eS.e&Yfy:J-kT+hkT0JyJ_1

```

My algorithm operates directly on the input string and never converts these number. It only calculate once a maximum and never a minimum.

Thanks to @isaacg for saving one byte.

Try it online: Pyth Compiler/Executor

## Explanations:

First I'll insert a lot of zeros in front of the input.

```
          implicit: Q = input()
    yQ    powerset(Q)
  m0yQ    map each element of the powerset to 0 (creates 2^Q zeros, I said lots)
 +    Q   zeros + Q
J         assign to J

```

Then I define a helper function `y`, which tells if the indices of a list (like the input one) appear in both sets A and B. E.g. `y([0, 1, 0, 0, 1, 1]) = False`, but `y([0, 1, 0, 2]) = y([3]) = True`.

```
Lq3.|Fb
L          define a function y(b), which returns _
   .|Fb       fold b by bitwise or
 q3            == 3

```

Afterwards I first check if the result is `-1`.

```
?...yJ_1   print ... if numbers appear in both sets (`yJ`) else -1

```

Now to the interesting stuff:

```
  .e              J    map each pair k,Y in enumerate(J) to:
    &Y                   Y and ... (acts as 0 if Y == 0 else ...)
      f          0       find the first number T >= 0, where:
       y                    indices appear in both sets in the substring
        :J-kT+hkT           J[k-T:k+T+1]
eS                     sort and take last element (maximum)

```

Notice, that I will always find a number `T`, since I already know that indices appear in both sets in the list J. The number is maximal `length(Q)`. This is also the reason for inserting the zeros. If there are at least `length(Q)` zeros inserted, `k-T` is always `>= 0`, which is necessary for the list slicing. So why do I insert `2^length(Q)` zeros instead of `length(Q)` zeros? In the test-case `[]` I need at least 1 zero, otherwise `yJ` will return an error.

# Answer
> 3 votes
# Mathematica, 88 bytes

```
Max[Min/@#,Min/@Thread@#,-1]/.∞->-1&@Outer[Abs[#-#2]&,p=Position;p[#,1|3],p[#,2|3],1]&

```

# Answer
> 3 votes
# Haskell, ~~145~~ ~~126~~ 124 bytes

```
s t x=[e|(e,i)<-zip[0..]x,t i]
d#e=maximum[minimum[abs$i-j|j<-e]|i<-d]
[]%_= -1
_%[]= -1
d%e=max(d#e)$e#d
f x=s(>1)x%s odd x

```

Test run:

```
*Main> map f [[], [0], [0,1,0], [2,0,0,2], [0,1,2,3],
              [0,3,3,0,0,0,0,3], [1,0,0,1,0,0,1,3,1],
              [1,0,0,0,0,3,0,0,0,0,2], [0,1,1,3,1,3,2,1,1,3,0,3],
              [2,2,2,1,2,0,3,1,3,1,0,3],
              [1,3,0,2,0,2,2,1,0,3,2,1,1,2,2],
              [1,0,1,1,2,0,1,2,3,1,0,0,0,1,2,0]]

[-1,-1,-1,-1,1,0,7,5,2,3,2,4]

```

`s` filters the natural numbers according to a predicate `t` and the input list `x`. `#` calculates the maximum distance of it's parameters `d` and `e`. `%` catches empty sets A or B or takes the final maximum of `d#e` and `e#d`. `f` is the main function which calls `%` with set A and B.

Edit: @Zgarb found lots of bytes to save; @ali0sha another 2. Thanks!

# Answer
> 3 votes
# Perl, ~~56~~ 55

Added +2 for `-lp`.

The input list should be given on stdin without spaces, e.g.:

```
echo 1011201231000120 | perl -lp hausdorf.pl

```

`hausdorf.pl`:

```
s%%$z=$_&=$p|=$'|P.$p;$q+=!!y/12/3/%eg;$_=$z=~3?$q:-1

```

To support spaces between the elements of the input list just divide the final `$q` by 2 for a cost of 2 strokes

# Answer
> 2 votes
# Python 2, 124

This definitely feels suboptimal. Oh well.

```
lambda a,E=enumerate:-min([1]+[~l*(n<3)for i,n in E(a)for l,_ in E(a)if{0}|set(n*a+n/3*[5])>{0,n}>=set(a[max(i-l,0):i-~l])])

```

# Answer
> 1 votes
# APL (49)

```
{(⊂⍬)∊∆←(↓2 2⊤⍵)/¨⊂⍳⍴⍵:¯1⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆}

```

Testcases:

```
      ({(⊂⍬)∊∆←(↓2 2⊤⍵)/¨⊂⍳⍴⍵:¯1⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆} ¨ testcases) ,⍨ '→',⍨ ↑ ⍕¨testcases
                               → ¯1
0                              → ¯1
0 1 0                          → ¯1
2 0 0 2                        → ¯1
0 1 2 3                        →  1
0 3 3 0 0 0 0 3                →  0
1 0 0 1 0 0 1 3 1              →  7
1 0 0 0 0 3 0 0 0 0 2          →  5
0 1 1 3 1 3 2 1 1 3 0 3        →  2
2 2 2 1 2 0 3 1 3 1 0 3        →  3
1 3 0 2 0 2 2 1 0 3 2 1 1 2 2  →  2
1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0→  4

```

Explanation:

* `⍳⍴⍵`: get a list of numbers from 1 to the length of the input list
* `↓2 2⊤⍵`: for each value in the input list, get the first byte and the second byte
* `∆←(`...`)/⊂⍳⍴⍵`: for both lists of bytes, select the corresponding values from `⍳⍴⍵`. Store these in .
* `(⊂⍬)∊∆`...`:¯1`: if this list contains the empty list, return `-1`. Otherwise:
* `|∘.-/∆`: get the absolute difference between every pair of values, giving a matrix
* `(+,⍉¨)`: get a rotated and a non-rotated copy of that matrix
* `{⌈/⌊/⍵}`: for both matrices, get the maximum of the minimums of the rows
* `⌈/`: then get the maximum of that

# Answer
> 1 votes
# Perl, ~~189~~ ~~176~~ 157B

Now with 500% more state.

```
use List::Util qw'max min';@I=<>;sub f{$n=($n%2)+1;map{$I[$_]&$n?$_:()}0..$#I}sub i{@t=f;max map{$b=$_;min map{abs$_-$b}@t}f}$r=max i,i;print defined$r?$r:-1

```

Legible:

```
use List::Util qw'max min';
@I=<>;
sub f {
    $n = ($n%2) + 1;
    map { $I[$_] & $n ? $_ : () } 0..$#I
}
sub i {
    @t = f;
    max map {
        $b = $_;
        min map { abs $_ - $b } @t
    } f
}
$r = max i,i;
print defined $r ? $r : -1

```

Example usage:

input

```
0
1
2
3

```

`perl golf.pl < input`

# Answer
> 0 votes
## Clojure, 167 bytes

```
#(let[P apply F(fn[I](filter(fn[i](I(% i)))(range(count %))))A(F #{1 3})B(F #{2 3})d(fn[X Y](P min(for[x X](P max(for[y Y](P -(sort[x y])))))))](-(min(d A B)(d B A))))

```

There should be a shorter way... Is there?

---
Tags: code-golf, number, array
---


title: Find the inside of a Loop

text:
# Question
Title: Find the inside of a Loop
# Task

Given a ASCII diagram of a loop

*e.g.*

```
....................
......@@@@@.........
......@...@.........
.....@@...@@@@@.....
....@@........@.....
....@........@@.....
....@@@@@@@@@@......
....................
....................

```

And a location on the loop

*e.g.*

```
(7,1)

```

You must find the inside and outside of the loop

*e.g.*

```
00000000000000000000
00000011111000000000
00000011111000000000
00000111111111100000
00001111111111100000
00001111111111100000
00001111111111000000
00000000000000000000
00000000000000000000

```

# Specifications

* You may take input for the diagram as a string separated by newlines or obvious equivalent
* You will receive a coordinate on the loop (0 or 1 indexed) as part of your input. You may place your origin at any place you wish. You may take this coordinate in `(<row>, <column>)`, `(<column>, <row>)` or as the linear position on the string. You may receive these data in any reasonable method. All characters on the loop will be the same as the character at that index.
* Preferred output is a 2 dimensional array of truthy and falsy values, however strings of `1` and `0` separated by newlines or any obvious equivalent of the later two are accepted. The inside and outside must have different truth values but it does not matter which is which.
* A loop is defined as a group of characters such that they are all the same character (*e.g. `@`*) and so that every character in the loop has a path to the original character (The character at the coordinate of input) that only passes through that same character (Taxicab geometry *No diagonals*).
* The inside is all the loop itself and the places that cannot reach the edge of the diagram without crossing the loop.
* The outside is everywhere else
* This is

# Test Cases

PasteBin

# Answer
> 6 votes
# MATLAB, ~~163 159 146~~ 78 bytes

```
function m=f(m,y,x);[~,i]=bwfill(m~=m(y,x),x,y,8);m=m*0;m(i)=1;m=bwfill(m,'h')

```

Thanks @rahnema1 for -66 bytes!!!

Now it does work on Try it online! BUT a few adjustments were needed, as MATLAB and Octave are not entirely compatible.

### Explanation

First we make a binary image that just masks all the characters that are equal to the initial character. Then we determine the connected component the initial character is in.

```
% determine the connected component that is contains initial character

[~,i]=bwfill(m~=m(y,x),x,y,8);     % i contains the indices of the connected component
m=m*0;m(i)=1;                      % create an image of the connected component

```

After that we create an image of that connected component and apply fill all the "holes" in the image.

```
m=bwfill(m,'h')

```

# Answer
> 5 votes
## MATLAB: 67 bytes

```
function A=f(A,r,c),A=bwlabel(A==A(r,c),4);A=imfill(A==A(r,c),'h');

```

A couple caveats:

* `A` is assumed to be a character array.
* Indices in MATLAB are 1-based, with rows indexed first. It is assumed these changes would be made to the function input (i.e. the question example would be called as `output = f(A,2,8)`).
* `bwlabel` and `imfill` are part of the Image Processing Toolbox.

---
Tags: code-golf, ascii-art, grid
---


title: Contiguous Block Count

text:
# Question
Title: Contiguous Block Count
Count the number of contiguous blocks within a given 3D input.

## Input

The input will consist of one or more rectangles of characters separated by blank lines. Each rectangle represents a cross section of the 3D space. The characters used will be `0`, representing empty space, and `1` representing a solid block.

**Example**

```
00000
01110
01110
01110

00000
01110
01110
01110

00000
01110
01110
01110

```

In the above example we have a 3x3 cube - the bottom layer first, then the middle and then the top.

## Output

The output should be a single integer giving the number of contiguous blocks within the input.

## What's considered contiguous?

If any two `1`s are adjacent to each other to the front, back, left, right, top or bottom, they are considered to be part of the same contiguous block. If they are not adjacent or they are only adjacent diagonally, they are not considered to be part of the same block.

**Examples**

```
00
11

```

Contiguous.

```
10
10

```

Contiguous.

```
10
01

```

Not contiguous.

```
01
00

01
00

```

Contiguous.

```
01
00

00
01

```

Not contiguous.

```
01
00

00
10

```

Not contiguous.

```
01
00

10
00

```

Not contiguous.

## Test inputs

```
11101110111
10000011100

00111000000
00000000000

Result: 1

111
111
111

000
010
000

111
111
111

Result: 1

111
111
111

100
000
000

101
011
111

Result: 2

11011011011
00100100100

11011011011
00100100100

00100100100
11011011011

00100100100
11011011011

Result: 14

11011011011
01100100110

11011011011
00100100100

00100100100
11011011011

00100100100
11011011011

Result: 12

11011011011
00100100100

11011011011
01100100110

00100100100
11011011011

00100100100
11011011011

Result: 10

11111
10001
10001
10001
11111

Result: 1

11111
10001
10101
10001
11111

Result: 2

11111
11111
11111
11111
11111

11111
10001
10001
10001
11111

11111
10001
10001
10001
11111

11111
10001
10001
10001
11111

11111
11111
11111
11111
11111

Result: 1

11111
11111
11111
11111
11111

11111
10001
10001
10001
11111

11111
10001
10101
10001
11111

11111
10001
10001
10001
11111

11111
11111
11111
11111
11111

Result: 2

11111
11111
11111
11111
11111

11111
10001
10001
10001
11111

11111
10001
10101
10001
11111

11111
10001
10101
10001
11111

11111
11111
11111
11111
11111

Result: 1

```

## Input format

I'm happy to be slightly flexible on the input format, so if you want to take a list of strings as input instead of one continuous string that's okay, and if you want to take a list of lists of characters (or integers if that helps) that's okay too.

Your answer can be a full program reading input or a function taking the input as a parameter. If your anonymous function needs a name in order for me to call it, then the characters for assigning the function to a name need to be counted too.

This is code golf so shortest code in bytes will win the big green tick, but any answer that meets the spec, passes the tests and has obviously been golfed will get my upvote.

# Answer
> 3 votes
# Octave, 30 bytes

`bwlabeln(...,6)` determines the 6-connected components of an n-dimensional array and outputs the number of components found as a second argument.

```
@(m){[~,N]=bwlabeln(m,6),N}{2}

```

Try it online!

# Answer
> 4 votes
# APL, 83 bytes

```
{0=⍴o←(,G)/Z←,⍳⍴G←⍵:0⋄1+∇G⊣{G[⊂⍵]←0⋄0=⍴A←G[A]/A←(A∊Z)/A←⍵∘+¨(+,-)↓∘.=⍨⍳3:⍬⋄∇¨A}⊃o}

```

Unlike some other languages, APL does not have a built-in for this (that I know of).

This function takes a 3-dimensional array of bits. It uses a 3-dimensional flood fill to remove blocks one by one, and counts how many blocks it can remove before the input is empty.

Non-golfed version with comments here.

# Answer
> 3 votes
# Mathematica, 53 bytes

```
Max@MorphologicalComponents[#,CornerNeighbors->False]&

```

Unnamed function taking a 3D-array of integers. `MorphologicalComponents` is the builtin being exploited here: treating `0` as empty space, it separates the other integers into contiguous blocks, and assigns each block a number (starting from `1`, `2`, ...) and replaces all of its component entries by that number. So the number of blocks is just the maximum of all entries thus produced. Unfortunately, by default `MorphologicalComponents` counts diagonal neighbors as connected, so we need to add the option `CornerNeighbors->False` to fit the spec. (Side note: `MorphologicalComponents` is really built to operate on 2D and 3D images; but it handles arrays of integers as a side benefit.)

---
Tags: code-golf, geometry, 3d
---


title: Hello World! generator

text:
# Question
Title: Hello World! generator
Often I need a simple Hello World! program to show some basic concepts of a programming language on my travels. As I usually travel only with light luggage I can't to carry a Hello World! program for each language. So a program that generates Hello World! programs in as many languages as possible would be a great help.

# Task

Write a program or function that accepts a language as an input and outputs or returns the source code for program or function that accepts no input and outputs (not returns) *Hello World!*.

# Input

The input defines in which language the Hello World! program should be generated. The input can be a number, a string, or whatever is the easiest for you. The input must only be used to select the language. You are not allowed to use the input as part of the output.

Please specify the valid inputs in your answer.

# Output

The output can the return value, or be written to a file or STDOUT (or equivalent). It must full program of function in the language defined by the input. The resulting program/function must write Hello World! to STDOUT (or equivalent for the language). The output doesn't need to be exactly "Hello World!". Everything reasonably recognizable as *Hello World!* is acceptable. Eg. *"HeLLo w0rlD1"* would be an acceptable output. Also the resulting *Hello World!* string can be different for different languages. See bonus points section for more details.

# Scoring

The program should work for as many languages as possible, and be as short as possible. Therefore the score is calculated by number of bytes / (number of supported languages - 1). Eg. an answer with 15 bytes and 3 supported languages would have a score of 7.5.

As usual with code-golf challenges lower scores are better.

# Bonus points

* You can subtract 10 percent from your score if the resulting *Hello World!* output for all supported languages is the same.
* You can subtract and additional 10 percent from your score if the output for all supported languages is exactly *Hello World!*

# Answer
# PHP, 13 bytes, 9 languages, Score: 1.625\*0.9^2 = 1.31625

```
Hello, World!

```

**Explanation:**

`Hello, World!` outputs `Hello, World!`. This can be used as input, and produce the same output in at least 9 languages.

Here's a list of languages this works for:

1. Chaîne
2. ///
3. Lines
4. if(j)invert()if(l)change()if(q)input()if(t)output(x);
5. Carrot
6. MicroSoft Windows HTA
7. PHP
8. pl
9. Dogless
10. Swap

---

This would give a fairly low score too, in Octave:

```
disp('print("Hello, World!")')

```

It prints `print("Hello, World!")` and should work in Perl, R, Ruby, Julia, Python 2, Python 3, Qbasic, Zsh/ksh, Cheddar among others.

Thanks to Dada for noticing I had capital instead of lower case `P`.
> 4 votes

---
Tags: code-golf, hello-world
---


title: Tips for golfing in Haxe

text:
# Question
Title: Tips for golfing in Haxe
What general tips do you have for golfing in Haxe? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to Haxe (e.g. "remove comments" is not an answer).

Please post one tip per answer.

Haxe can be run online here!

# Answer
# String interpolation

Haxe supports string interpolation on single-quote strings. Like template strings in JavaScript ES6, you can include an expression in a string with `${...}`:

```
trace('2 + 2 = ${2 + 2}');

```

Unlike ES6, however, you can omit the curly brackets when the expression is a single variable:

```
var x = 2 + 2;
trace('2 + 2 = $x');

```

Both of these examples print `2 + 2 = 4`.
> 8 votes

# Answer
# Array comprehensions

Haxe supports array comprehensions:

```
trace([for (i in 0...5) i]); // Prints 0,1,2,3,4

```

Unlike many other languages, you can also use `while` in comprehensions:

```
var i = 5;
trace([while (i > 0) i--]); // Prints 5,4,3,2,1

```

This can be very useful when you don't know how long of an array you need.

You can also chain `for`, `while`, and `if` statements:

```
trace([for (x in ['A','B','C','D'])
       for (y in ['x','y'])
       if (x + y != "Cx")
       x + y
]); // Prints Ax,Ay,Bx,By,Cy,Dx,Dy

```
> 7 votes

# Answer
# Range operator

Haxe has a range operator `...` which can be used to create ranges of integers. For example, instead of this:

```
var i = 0;
while (i < 10) trace(i++);

```

You can do this:

```
for (i in 0...10) trace(i++);

```

Specifics for `x...y`:

* `x` and `y` must both be Ints.
* `x` cannot be larger than `y`.
* This returns an IntIterator object, which can be used in the same places as any Iterable.
> 6 votes

# Answer
# Omit function brackets

Unlike most languages, everything in Haxe is an expression, including `{blocks}`. Thus, curly brackets *anywhere* in a Haxe program (with the exception of `switch` expressions) can be left off if they contain only a single statement. So instead of this:

```
function f(n){return Math.pow(3,n);}

```

You can do this:

```
function f(n)return Math.pow(3,n);

```

An easy two bytes saved on many functions.

Even if a function must contain multiple statements, you can often save a byte by moving the `return` *outside the block:*

```
function f(a){var b=a*a;return a<0?-b:b;}
function f(a)return{var b=a*a;a<0?-b:b;}

```

This works because a block evaluates to the last expression inside the block.
> 1 votes

# Answer
# Use keywords in expressions

Another unusual feature of Haxe is that everything is an expression. For example, this code is perfectly valid:

```
function(n){while(n>0)n%4==1?return 6:n--;return 3;}

```

Okay, that's a fairly useless example, but hopefully you get my point. This works with most keywords:

```
function(n){while(n>0)n%4==1?break:n--;return n;}

```

This allows you to use `if`/`else` inline, like `p=if(n>1)7else 4;`, though of course `p=n>1?7:4;` is shorter.

### Keywords you cannot use inline

* `var` \- The compiler will complain about trying to use Void as a value.
* `for`/`while` \- Same as above, though you can use them in array comprehensions.
> 1 votes

# Answer
# Running a statement conditionally

Obviously you can run anything conditionally with `if`:

```
if(n>5)doSomething(n);

```

If, however, you have only one statement as above, you can use the ternary conditional operator to save a byte:

```
n>5?doSomething(n):0;

```

You can sometimes save another byte by using `&&`, though this is very rare because `&&` only works if both expressions return booleans:

```
n>5&&doSomething(n);

```

One major exception to this is keywords: if Haxe runs into a `return`, `break`, or `continue` *anywhere*, it will immediately run it and quit whatever expression it was working on. This means that instead of this:

```
if(n>5)return n;

```

You can do this to save 2 bytes:

```
n>5&&return n;

```
> 1 votes

---
Tags: code-golf, tips
---


title: Piet (Mondrian)'s Puzzle

text:
# Question
Title: Piet (Mondrian)'s Puzzle
*For more information, watch this video, and go to A276523 for a related sequence.*

The Mondrian Puzzle (for an integer `n`) is the following:

Fit non-congruent rectangles into a `n*n` square grid. What is the smallest difference possible between the largest and the smallest rectangle?

For `6`, the optimal difference for `M(6)` is `5`, and can be demonstrated like so:

```
 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)

```

The largest rectangle (L) has an area of `2 * 4 = 8`, and the smallest rectangle (S) has an area of `1 * 3 = 3`. Therefore, the difference is `8 - 3 = 5`.

*Keep in mind that currently, no optimal solutions for `n > 44` have been found.*

Your task is to create a program that generates a Mondrian grid that contains a (non-optimal) solution, given an integer `n`.

You will be tested on the numbers from 100 to 150. Your score for each test will be the difference between the largest and smallest rectangle. Your total score is the sum of your scores for all the tests from 100 to 150.

You must present your output like so:

```
{number}
{grid}

```

Where `number` is the score (the difference between largest and smallest), and `grid` is either:

* A multi-lined string, or
* A two-dimensional list.

The grid MUST clearly show where a rectangle starts and ends.

## Rules:

* Your program must fit within your answer.
* Your program must output a value for any number between 100 and 150 within 1 hour on a modern laptop.
* Your program must generate the same solution for an integer `n` every time the program is run.
* You must provide a link to the outputs of all 51 solutions (using Pastebin, Github Gist... anything, really).
* You must have at least two rectangles on the square grid for your solution.

# Answer
> 15 votes
# Piet, 9625

**(It finally works!)**

The people demanded it, so here it is. This is an extremely naive solution (essentially the same as the loose upper bounds on the OEIS page): it divides each square into just two rectangles.

This gist contains the details in two files:

* The program's output (using npiet v1.3) for all required inputs. Note that I only captured stdout, so the `?` is the input prompt, followed immediately by the output score, then the grid.
* The "pseudo-assembly" source I used to plan out the program.

## Explanation

This program takes a single number `N` as input. If the number is odd, the score is the number; if even, the score is twice the number.

After outputting the score, the rest of the left-hand side of the program is spent filling the stack with five lots of the following information:

* The grid width (which is `N`)
* A number of lines to print
* A character to print across the grid (either `_` or space)
* A character to print at each edge of the grid (either space or `|`)

The right-hand side of the program takes each set of four values and prints out that part of the grid.

# Answer
> 6 votes
# C 6108

This uses a recursive (really iterative) version of the minimal solution. Instead of dividing the square into two rectangles where one is a little bit bigger than half the area, it divides it into N rectangles. So the first rectangle is a bit larger than `1/N` the total area. Then taking the remainder, the program splits off a rectangle a bit larger than `1/(N-1)` of the remainder and so on until it just takes the remainder as the last rectangle. The rectangles are cut off of the remainder in a clockwise spiral, so first at the top, then on the right, etc.

Since this a very direct method instead of a search of a broad space, it runs quickly - taking about 25 seconds (on a Raspberry Pi) to look at 74 solutions each for the given problem set.

My intent is to use these results to better inform a search algorithm for a more sophisticated approach.

The output gives the score and both an (ascii) drawing and coordinates for the vertices of the rectangles. The vertices are in clockwise order, starting from the upper left hand corner of the rectangle in question.

Developed using gcc 4.9.2-10.

Results at https://github.com/JaySpencerAnderson/mondrian

**Code:**

```
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
    int y, x, height, width;
} rectangle;
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#ifndef TRUE
#define TRUE -1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#define MAXCOUNT 75

void initstack(rectangle *s, int n){
    int i;
    for(i=0;i<n;i++){
        s[i].y=s[i].x=s[i].height=s[i].width=0;
    }
}
int valid(rectangle *s,int n){
    int i,j;
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(min(s[i].height,s[i].width) == min(s[j].height,s[j].width) && max(s[i].height,s[i].width) == max(s[j].height,s[j].width)){

                initstack(s, n);
                return FALSE;
            }
        }
    }
    return TRUE;
}
int horizontal(rectangle s, int y, int x){
    if(s.y == y && x >= s.x && x < s.x+s.width){
        return TRUE;
    }
    else if(s.y+s.height == y && x >= s.x && x < s.x+s.width){
        return TRUE;
    }
    return FALSE;
}
int vertical(rectangle s, int y, int x){
    if(s.x == x && y > s.y && y <= s.y+s.height){
        return TRUE;
    }
    else if(s.x+s.width == x && y > s.y && y <= s.y+s.height){
        return TRUE;
    }
    return FALSE;
}
void graph(rectangle *s, int n, int side){
    unsigned int row,col,i;
    unsigned int line;
    printf("{\n");
/* vertical lines take precedence since "1" cell is 1 char high and 2 char wide */
    for(row=0;row<=side;row++){
        for(col=0;col<=side;col++){
            line=0;
/* Possible values are "  " (0), "__" (1), "| " (2) or "|_" (3). */
            for(i=0;i<n;i++){
                if(horizontal(s[i],row,col)){
                    line|=1;
                }
                if(vertical(s[i],row,col)){
                    line|=2;
                }
            }

            switch(line){
            case 0: printf("  ");   break;
            case 1: printf("__");   break;
            case 2: printf("| ");   break;
            case 3: printf("|_");   break;
            default: printf("##");  break;
            }
        }
        printf("\n");
    }
    printf("}\n");
}
unsigned int score(rectangle *s, int n){
    int i;
    unsigned int smallest,biggest;

    smallest=biggest=s[0].width*s[0].height;

    for(i=0;i<n;i++){
        smallest=min(smallest,s[i].width*s[i].height);
        biggest=max(biggest,s[i].width*s[i].height);
    }
    return biggest-smallest;
}
void report(rectangle *s, int n, int side){
    int i;

    printf("{%d}\n",score(s,n));
    graph(s, n, side);
    printf("{\n");
    for(i=0;i<n;i++){
        printf("[%d,%d] ",s[i].x,s[i].y);
        printf("[%d,%d] ",s[i].x+s[i].width,s[i].y);
        printf("[%d,%d] ",s[i].x+s[i].width,s[i].y+s[i].height);
        printf("[%d,%d]\n",s[i].x,s[i].y+s[i].height);
    }
    printf("\n}\n");
}
void locateandrotate(rectangle *stack, int n){
    unsigned int scratch,i;
    for(i=1;i<n;i++){
        /* Odd rectangles are on their side */
        if(i&1){
            scratch=stack[i].width;
            stack[i].width=stack[i].height;
            stack[i].height=scratch;
        }
        switch(i%4){
        case 0:
            stack[i].x=stack[i-1].x+stack[i-1].width;
            stack[i].y=stack[i-1].y;
            break;
        case 1:
            stack[i].x=stack[i-1].x+stack[i-1].width-stack[i].width;
            stack[i].y=stack[i-1].y+stack[i-1].height;
            break;
        case 2:
            stack[i].x=stack[i-1].x-stack[i].width;
            stack[i].y=stack[i-1].y+stack[i-1].height-stack[i].height;
            break;
        case 3:
            stack[i].x=stack[i-1].x;
            stack[i].y=stack[i-1].y-stack[i].height;
            break;
        default:
            printf("Woops!\n");
        }
    }
}
/* These are the height and width of the remaining area to be filled. */
void door(rectangle *stack, unsigned int height, unsigned int width, unsigned int n, unsigned int totaln){
    unsigned int thisheight, thiswidth;
    int i;

    for(i=0;i<totaln;i++){
/* Not yet used */
        if(stack[i].width == 0){
            stack[i].width=width;
            if(i+1 == totaln){
                stack[i].height=height;
            }
            else {
/* Sometimes yields congruent rectangles, as with 16x16, 8 rectangles */
                if(totaln&1 || height%n){
                    int j;
                    stack[i].height=height-(((n-1)*height)/n);
                }
                else {
                    stack[i].height=height-((((n-1)*height)-1)/n);
                }
                /* Exchange height and width to rotate */
                door(stack,width,height-stack[i].height,n-1,totaln);
            }
            return;
        }
    }
}
void usage(char *argv[],int side){
    printf("Usage: %s -s <side-length>\n",argv[0]);
    printf("Purpose: Calculate N non-congruent rectangles arranged to exactly fill a square with the specified side length.\n");
    printf("Defaults: %s -s %d\n",argv[0],side);
    exit(0);

}
int main(int argc, char *argv[]){
    int side=16;
    int n,bestscore,bestn=2;
    int status;

    while((status=getopt(argc,argv,"s:h")) >= 0){
        switch(status){
        case 's':
            sscanf(optarg,"%d",&side);
            break;
        case 'h':
        default:
            usage(argv,side);
        }
    }

    bestscore=side+side;

    rectangle stack[MAXCOUNT],best[MAXCOUNT];
    for(n=2;n<=MAXCOUNT;n++){
        initstack(stack,MAXCOUNT);
        door(stack, side, side, n, n);
        locateandrotate(stack, n);
        if(valid(stack,n)){
            if(score(stack,n) < bestscore){
                bestn=n;
                initstack(best,MAXCOUNT);
                door(best, side, side, n, n);
                locateandrotate(best, n);

                bestscore=score(best,n);
            }
        }
    }
    report(best,bestn,side);
}

```

# Answer
> 4 votes
# C - 2982

This program implements a search through a broad results set. The important part of making this search practical was to fail early and/or not go down bad paths.

This generates a set of rectangles to be considered for the solution. The set of rectangles generated avoids those with dimensions that would not be useful. For instance, if the program is trying to find the solution to a 128x128 square, divided into 8 rectangles, it will generate a rectangle that is 128x16. It will not generate that one is 120x17 because there is no prospect of a generating rectangle that is 8 wide to fill in the gap at the end of 120.

The initial strategy for placing rectangles is to place them on the inside of the perimeter of the square (buildedge function). In that way, the algorithm gets pretty quick feedback at each corner as to whether there is a problem with the sequence chosen. While placing rectangles, the logic keeps watching to see if any gaps of space develop which are too narrow for any rectangle. After the perimeter has been populated successfully, the strategy changes to trying to match the space remaining with the remaining rectangles (match function).

One other thing that might be of interest is that this implements transactions with rollback for the stacks of rectangles.

This program doesn't try to find the best possible fit. It is given a budget (64) and quits when it finds the first solution. If it never finds a solution, we bump up the budget (by 16) and try again. The time required (on a Dell laptop with an I7 processor) ranged from well under a minute to 48 minutes for 150 on a side (149 on a side took less than 2 minutes). All 51 solutions used 11 rectangles. The scores of the 51 solutions ranged from 41 to 78. The reasons I used 11 rectangles were that the score was lower than with fewer rectangles and it looked like 12 rectangles would take much more than the hour allotted.

The solutions and code may be found at https://github.com/JaySpencerAnderson/mondrian . They are the two my4\* files.

BTW, if you compile this to "my4" and execute it as follows: "./my4 -h", it will give you usage. If you want to see it in action working away, try something like "./my4 -l 50 -n 8". If you change the one "#if 0" to "#if 1" it will render the remaining space on the screen. If you want to change this to render the rectangles, look for the one spot where the code executes "graph(space,side)" and change that to "graph(callstack,side)" instead. I'd also suggest changing the initial budget from 64 to 32 if you want to play around with solutions for squares that are about 50 wide. The solution for smaller squares will have a better score with a smaller budget.

The program below is functional. Check github for the complete code (with usage, comments, etc).

```
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
    int y, x, height, width, created, deleted;
} rectangle;
#define NOTYET -1
#define TOPEDGE 1
#define RIGHTEDGE 2
#define BOTTOMEDGE 4
#define LEFTEDGE 8
#define CENTER 16
#define nextEdge(e) (e<<=1)
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#define MAXFACTORS 1000
#define EOL printf("\n")
#define isCurrent(r) (r.created != NOTYET && r.deleted == NOTYET)
#define deleteTxn(r,t) (r.deleted=t)
int area(rectangle r){
    return r.width*r.height;
}
void pop(rectangle *s){
    unsigned int k=0;
    while(s[k].width){
        k++;
    }
    s[k-1].width=s[k-1].height=0;
}
void rpush(rectangle *s, rectangle x){
    unsigned int k=0;
    while(s[k].width){
        k++;
    }
    x.deleted=NOTYET;
    s[k++]=x;
    s[k].width=s[k].height=0;

    return;
}
void dumprectangle(rectangle r){
    printf("%dX%d@[%d,%d] (%d,%d)\t",r.width, r.height, r.x, r.y, r.created, r.deleted);
}
void dumpstack(rectangle *s){
    unsigned int k=0;
    while(s[k].width){
        dumprectangle(s[k]);
        k++;
    }
}
rectangle initrectangle(int width, int height){
    rectangle r;
    r.x=r.y=0;
    r.width=width;
    r.height=height;
    r.created=0;
    r.deleted=NOTYET;
    return r;
}
void initstack(rectangle *s, int n){
    int i;
    for(i=0;i<n;i++){
        s[i].y=s[i].x=s[i].height=s[i].width=0;
    }
}
int bitcount(int x){
    int count=0;
    while(x){
        if(x&1){
            count++;
        }
        x>>=1;
    }
    return count;
}
int congruent(rectangle a, rectangle b){
    return min(a.height,a.width) == min(b.height,b.width) && max(a.height,a.width) == max(b.height,b.width);
}
void report(rectangle *s, int side){
    int i;
    unsigned int smallest,biggest,area=0;

    smallest=side*side;
    biggest=0;

    for(i=0;s[i].width;i++){
        if(isCurrent(s[i])){
            smallest=min(smallest,s[i].width*s[i].height);
            biggest=max(biggest,s[i].width*s[i].height);
        }
    }
    printf("{%d}\n",biggest-smallest);
    printf("{\nDimensions\tLocation\n");
    for(i=0;s[i].width;i++){
        printf("%dx%d\t\t[%d,%d]\n",
            s[i].width,         s[i].height,
            s[i].x,             s[i].y);
    }
    printf("}\n");
}
unsigned int sumstack(rectangle *s){
    unsigned int sum=0;
    int i;
    for(i=0;s[i].width;i++){
        if(isCurrent(s[i])){
            sum+=s[i].width*s[i].height;
            s++;
        }
    }
    return sum;
}
unsigned int minstack(rectangle *s){
    unsigned int area=400000;
    int i;

    for(i=0;s[i].width;i++){
        if(isCurrent(s[i])){
            area=min(area,s[i].width*s[i].height);
        }
    }
    return area;
}
void rollback(rectangle *r, int txn){
    int i;

    if(txn != NOTYET){
        for(i=0;r[i].width;i++){
            if(r[i].created == txn){
                r[i].created=r[i].deleted=NOTYET;
                r[i].x=r[i].width=r[i].y=r[i].height=0;
            }
            else if(r[i].deleted == txn){
                r[i].deleted=NOTYET;
            }
        }
    }
}
int overlap(rectangle a, rectangle b){
    if((a.x < b.x+b.width && a.x+a.width > b.x) && (b.y < a.y+a.height && b.y+b.height > a.y)){
        return TRUE;
    }
    return FALSE;
}
int stackoverlap(rectangle *callstack, rectangle next){
    int i,j;
    for(i=0;callstack[i].width;i++){
        if(overlap(callstack[i], next)){
            return TRUE;
        }
    }
    return FALSE;
}
rectangle rotate(rectangle a){
    int x=a.width;
    a.width=a.height;
    a.height=x;
    return a;
}
int buildedge(rectangle *stack, rectangle *callstack,int side, rectangle *space){
    int i,j,edge,goal,nextgoal,x,y,d,mindim,minarea,result=FALSE,spacetxn,stacktxn;
    mindim=side;
    minarea=side*side;
    for(i=0;stack[i].width;i++){
        mindim=min(mindim,min(stack[i].width,stack[i].height));
        minarea=min(minarea,area(stack[i]));
    }
    x=y=0;
    edge=TOPEDGE;
    i=0;
    while(edge == TOPEDGE && callstack[i].width != 0){
        if(callstack[i].x == x && callstack[i].y == y){
            x+=callstack[i].width;
            if(x == side){
                nextEdge(edge);
                y=0;
            }
            i=0;
        }
        else {
            i++;
        }
    }
    while(edge == RIGHTEDGE && callstack[i].width != 0){
        if(callstack[i].x+callstack[i].width == x && callstack[i].y == y){
            y+=callstack[i].height;
            if(y == side){
                nextEdge(edge);
                x=side;
            }
            i=0;
        }
        else {
            i++;
        }
    }
    while(edge == BOTTOMEDGE && callstack[i].width != 0){
        if(callstack[i].x+callstack[i].width == x && callstack[i].y+callstack[i].height == y){
            x-=callstack[i].width;
            if(x == 0){
                nextEdge(edge);
                y=side;
            }
            i=0;
        }
        else {
            i++;
        }
    }
    while(edge == LEFTEDGE && callstack[i].width != 0){
        if(callstack[i].x == x && callstack[i].y+callstack[i].height == y){
            y-=callstack[i].height;
            if(y == 0){
                nextEdge(edge);
            }
            i=0;
        }
        else {
            i++;
        }
    }
    if(edge == CENTER){
        /* rectangles are placed all along the perimeter of the square.
         * Now match will use a different strategy to match the remaining space
         * with what remains in stack */
        if(match(stack,callstack,space)){
            report(callstack,side);
            return TRUE;
        }
        return FALSE;
    }
    switch(edge){
    case TOPEDGE:
        goal=side-x;
        break;
    case RIGHTEDGE:
        goal=side-y;
        break;
    case BOTTOMEDGE:
        goal=x;
        break;
    case LEFTEDGE:
        /* Still a good assumption that callstack[0] is at 0,0 */
        goal=y-callstack[0].height;
        break;
    default:
        fprintf(stderr,"Error: buildedge has unexpected edge (b): %d\n",edge);
        exit(0);
    }
    nextgoal=goal-mindim;
    for(i=0;stack[i].width;i++){
        if(isCurrent(stack[i])){
            for(d=0;d<2;d++){
                switch(edge){
                case TOPEDGE:
                    if(stack[i].width == goal || stack[i].width <= nextgoal){
                        stack[i].x=x;
                        stack[i].y=y;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                case RIGHTEDGE:
                    if(stack[i].height == goal || stack[i].height <= nextgoal){
                        stack[i].x=x-stack[i].width;
                        stack[i].y=y;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                case BOTTOMEDGE:
                    if(stack[i].width == goal || stack[i].width <= nextgoal){
                        stack[i].x=x-stack[i].width;
                        stack[i].y=y-stack[i].height;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                case LEFTEDGE:
                    if(stack[i].height == goal || stack[i].height <= nextgoal){
                        stack[i].x=x;
                        stack[i].y=y-stack[i].height;
                        if(!stackoverlap(callstack, stack[i])){
                            spacetxn=nexttransaction(space);
                            stacktxn=nexttransaction(stack);
                            deleteTxn(stack[i],stacktxn);
                            removerectangle(space, stack[i], spacetxn);
                            if(narrow(space) >= mindim && smallest(space) >= minarea){
                                rpush(callstack, stack[i]);
                                if(buildedge(stack, callstack, side, space)){
                                    return TRUE;
                                }
                                pop(callstack);
                            }
                            rollback(space, spacetxn);
                            rollback(stack, stacktxn);
                            stack[i].x=stack[i].y=0;
                        }
                    }
                    break;
                default:
                    fprintf(stderr,"Error: buildedge has unexpected edge (c): %d\n",edge);
                    exit(0);
                }
                if(callstack[0].width != 0 && stack[i].width != stack[i].height){
                    stack[i]=rotate(stack[i]);
                }
                else {
                    break;
                }
            }
        }
    }
    return FALSE;
}
int populatestack(rectangle *stack, int score, int side, int rectangles){
    int offset,negative,area,mindim;
    rectangle local;

    int avg_area=(side*side)/rectangles;

    if(avg_area < 4){
        /* It's getting too small - really */
        return FALSE;
    }
    local.x=0;
    local.y=0;
    local.created=0;
    local.deleted=NOTYET;

    initstack(stack,MAXFACTORS);
    for(offset=1;offset<=score;offset++){
        negative=offset&1;
        area=avg_area + (negative?(0-(offset>>1)):(offset>>1));
        mindim=area/side;

        if(side*(area/side) == area){
            local.width=side;
            local.height=area/side;
            rpush(stack,local);
        }

        if(area > 0){
            for(local.width=side-mindim;local.width>=area/local.width;local.width--){
                if(local.width*(area/local.width) == area){
                    local.height=area/local.width;
                    rpush(stack,local);
                }
            }
        }
    }
    return TRUE;
}
int solve(int side,int rectangles,int score){
    rectangle stack[MAXFACTORS],callstack[MAXFACTORS];
    rectangle space[MAXFACTORS];
    rectangle universe;

    if(!populatestack(stack, score, side, rectangles)){
        return FALSE;
    }
    if(sumstack(stack) >= side*side){
        initstack(callstack,MAXFACTORS);
        initstack(space,MAXFACTORS);

        /* Initialize space (not occupied by a rectangle) to be side by side
         * where side is the height/width of the square into which the rectangles fit. */
        universe.width=universe.height=side;
        universe.x=universe.y=0;
        universe.created=0;
        universe.deleted=NOTYET;
        rpush(space, universe);

        if(buildedge(stack,callstack,side,space)){
            return TRUE;
        }
    }
    return FALSE;
}
int containsPoint(rectangle a, int x, int y){
    return a.x <= x && a.y <= y && a.x+a.width > x && a.y+a.height > y;
}
int containsRectangle(rectangle a, rectangle b){
    return containsPoint(a, b.x, b.y) && containsPoint(a, b.x+b.width-1, b.y) && containsPoint(a, b.x, b.y+b.height-1) && containsPoint(a, b.x+b.width-1, b.y+b.height-1);
}
int areEqual(rectangle a, rectangle b){
    return a.x == b.x && a.y == b.y && a.width == b.width && a.height == b.height;
}
int nexttransaction(rectangle *r){
    int i,n=NOTYET;

    for(i=0;r[i].width;i++){
        n=max(n,max(r[i].created,r[i].deleted));
    }
    return n+1;
}
void splitrectanglevertically(rectangle *space, int i, int x, int txn){
    rectangle left, right;
    left=right=space[i];
    right.x=x;
    left.width=right.x-left.x;
    right.width-=left.width;
    left.created=right.created=space[i].deleted=txn;
    rpush(space,left);
    rpush(space,right);
}
void splitrectanglehorizontally(rectangle *space, int i, int y, int txn){
    rectangle top, bottom;
    top=bottom=space[i];
    bottom.y=y;
    top.height=bottom.y-top.y;
    bottom.height-=top.height;
    top.created=bottom.created=space[i].deleted=txn;
    rpush(space,top);
    rpush(space,bottom);
}
int smallest(rectangle *space){
    int i,j,smallest;
    rectangle current;
    smallest=0;
    for(i=0;space[i].width;i++){
        if(isCurrent(space[i])){
            current=space[i];
            for(j=0;space[j].width;j++){
                if(isCurrent(space[j]) && i != j){
                    if(current.x+current.width == space[j].x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.width+=space[j].width;
                    }
                    else if(space[j].x+space[j].width == current.x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.x=space[j].x;
                        current.width+=space[j].width;
                    }
                    else if(current.y+current.height == space[j].y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.height+=space[j].height;
                    }
                    else if(space[j].y+space[j].height == current.y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.y=space[j].y;
                        current.height+=space[j].height;
                    }
                }
            }
            if(smallest == 0){
                smallest=current.width * current.height;
            }
            else if(smallest > current.width * current.height){
                smallest=current.width * current.height;
            }
        }
    }
    return smallest;
}
int narrow(rectangle *space){
    int i,j;
    rectangle smallest,current;

    smallest.width=0;
    for(i=0;space[i].width;i++){
        current=space[i];
        if(isCurrent(current)){
            for(j=0;space[j].width;j++){
                if(isCurrent(space[j]) && i != j){
                    if(current.width <= current.height
                    && current.x+current.width == space[j].x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.width+=space[j].width;
                    }
                    else if(current.width <= current.height
                    && space[j].x+space[j].width == current.x
                    && space[j].y <= current.y && space[j].y+space[j].height >= current.y+current.height){
                        current.x=space[j].x;
                        current.width+=space[j].width;
                    }

                    if(current.width >= current.height
                    && current.y+current.height == space[j].y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.height+=space[j].height;
                    }
                    else if(current.width >= current.height
                    && space[j].y+space[j].height == current.y
                    && space[j].x <= current.x && space[j].x+space[j].width >= current.x+current.width){
                        current.y=space[j].y;
                        current.height+=space[j].height;
                    }
                }
            }
            if(smallest.width == 0){
                smallest=current;
            }
            else if(min(smallest.width,smallest.height) > min(current.width,current.height)){
                smallest=current;
            }
        }
    }
    return min(smallest.width,smallest.height);
}
int notEmpty(rectangle *space){
    int i,count;

    for(i=0,count=0;space[i].width;i++){
        if(isCurrent(space[i])){
            count++;
        }
    }
    return count;
}
int isAdjacent(rectangle r, rectangle s){
    if(r.y == s.y+s.height && r.x < s.x+s.width && s.x < r.x+r.width){
        return TOPEDGE;
    }
    if(s.x == r.x+r.width && r.y < s.y+s.height && s.y < r.y+r.height){
        return RIGHTEDGE;
    }
    if(s.y == r.y+r.height && r.x < s.x+s.width && s.x < r.x+r.width){
        return BOTTOMEDGE;
    }
    if(r.x == s.x+s.width && r.y < s.y+s.height && s.y < r.y+r.height){
        return LEFTEDGE;
    }
    return NOTYET;
}

int adjacentrectangle(rectangle *space, int k, int k0){
    int i,edge;
    for(i=k0+1;space[i].width;i++){
        if(i != k && isCurrent(space[i])){
            if(isAdjacent(space[k],space[i]) != NOTYET){
                return i;
            }
        }
    }
    return NOTYET;
}
int expanse(rectangle *space, int j, int d){ /* Returns how far space[j] can expand in the d direction */
    int extent,k,giveUp,distance;
    rectangle result=space[j];

    extent=0;
    giveUp=FALSE;
    distance=0;
    if(d == TOPEDGE || d == BOTTOMEDGE){
        while(extent < space[j].width && !giveUp){
            giveUp=TRUE;
            for(k=0;space[k].width;k++){
                if(k != j && isCurrent(space[k]) && isAdjacent(space[j],space[k]) == d){
                    if(space[j].x+extent == space[k].x){
                        extent+=space[k].width;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                    else if(space[j].x+extent > space[k].x && space[j].x+extent < space[k].x+space[k].width){
                        extent=space[k].x+space[k].width-space[j].x;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                }
            }
        }
        if(extent < space[j].width){
            return 0;
        }
        return space[j].height+distance;
    }
    else if(d == LEFTEDGE || d == RIGHTEDGE){
        while(extent < space[j].height && !giveUp){
            giveUp=TRUE;
            for(k=0;space[k].width;k++){
                if(k != j && isCurrent(space[k]) && isAdjacent(space[j],space[k]) == d){
                    if(space[j].y+extent == space[k].y){
                        extent+=space[k].height;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                    else if(space[j].y+extent > space[k].y && space[j].y+extent < space[k].y+space[k].height){
                        extent=space[k].y+space[k].height-space[j].y;
                        if(distance == 0){
                            distance=expanse(space,k,d);
                        }
                        else {
                            distance=min(distance,expanse(space,k,d));
                        }
                        giveUp=FALSE;
                    }
                }
            }
        }
        if(extent < space[j].height){
            return 0;
        }
        return space[j].width+distance;
    }
    return 0;
}
int match(rectangle *stack, rectangle *callstack, rectangle *space){
    int i,j,k,d,goal,mn;
    int height;
    int spacetxn, stacktxn, calltxn;
    int map;
    rectangle r;

    for(i=0,goal=0;space[i].width;i++){
        if(isCurrent(space[i])){
            goal+=space[i].width*space[i].height;
        }
    }
    if(goal == 0){
        return TRUE;
    }
    mn=minstack(stack);
    if(goal < mn){
        /* The goal (space available) is smaller than any rectangle left in the stack */
        return FALSE;
    }
    spacetxn=nexttransaction(space);
    stacktxn=nexttransaction(stack);
    calltxn=nexttransaction(callstack);
    for(j=0;space[j].width;j++){
        for(i=0;stack[i].width;i++){
            if(isCurrent(stack[i]) && isCurrent(space[j])){
                if(congruent(space[j], stack[i]) && adjacentrectangle(space,j,NOTYET) == NOTYET){
                    r=space[j];
                    r.created=calltxn;
                    rpush(callstack, r);
                    deleteTxn(stack[i],stacktxn);
                    deleteTxn(space[j],spacetxn);
                }
            }
        }
    }
    if(!notEmpty(space)){
        return TRUE;
    }
    rectangle e;
    for(j=0;space[j].width;j++){
        if(isCurrent(space[j])){
            e=space[j];
            for(k=0,map=0;space[k].width;k++){
                if(k != j && isCurrent(space[k])){
                    d=isAdjacent(space[j], space[k]);
                    if(d != NOTYET){
                        map|=d;
                    }
                }
            }
            if(bitcount(map) == 1){ /* space[j] has adjacent space on only one side */
                if(map == TOPEDGE || map == BOTTOMEDGE){
                    e.height=expanse(space,j,map);
                }
                else if(map == LEFTEDGE || map == RIGHTEDGE){
                    e.width=expanse(space,j,map);
                }
                for(i=0;stack[i].width;i++){
                    if(isCurrent(stack[i])){
                        if(congruent(e, stack[i])){
                            e.created=calltxn;
                            rpush(callstack, e);
                            deleteTxn(stack[i],stacktxn);
                            if(!removerectangle(space, e, spacetxn)){
                                printf("Logic error in match/expanse.  Terminating\n");
                                exit(0);
                            }
                            if(match(stack,callstack,space)){
                                return TRUE;
                            }
                            else {
                                rollback(stack,stacktxn);
                                rollback(callstack,calltxn);
                                rollback(space,spacetxn);
                                return FALSE;
                            }
                        }
                        else if(congruent(space[j], stack[i])){
                            r=space[j];
                            r.created=calltxn;
                            rpush(callstack, r);
                            deleteTxn(stack[i],stacktxn);
                            if(!removerectangle(space, r, spacetxn)){
                                printf("Logic error in match/expanse.  Terminating\n");
                                exit(0);
                            }
                            if(match(stack,callstack,space)){
                                return TRUE;
                            }
                            else {
                                rollback(stack,stacktxn);
                                rollback(callstack,calltxn);
                                rollback(space,spacetxn);
                                return FALSE;
                            }
                        }
                    }
                }
            }
        }
    }
    if(notEmpty(space)){
        rollback(stack,stacktxn);
        rollback(callstack,calltxn);
        rollback(space,spacetxn);
        return FALSE;
    }
    return TRUE;
}
int removerectangle(rectangle *space, rectangle r, int ntxn){
    int i,status=TRUE;
    for(i=0;space[i].width;i++){
        if(space[i].deleted == NOTYET){
            if(areEqual(space[i], r)){
                space[i].deleted=ntxn;
                return TRUE;
            }
            else if(containsRectangle(space[i], r)){
                if(r.x > space[i].x){
                    splitrectanglevertically(space, i, r.x, ntxn);
                }
                else if(r.y > space[i].y){
                    splitrectanglehorizontally(space, i, r.y, ntxn);
                }
                else if(r.x+r.width < space[i].x+space[i].width){
                    splitrectanglevertically(space, i, r.x+r.width, ntxn);
                }
                else if(r.y+r.height < space[i].y+space[i].height){
                    splitrectanglehorizontally(space, i, r.y+r.height, ntxn);
                }
            }
            else if(overlap(space[i], r)){  /* we have to split both */
                rectangle aux;
                if(r.x < space[i].x){
                    aux=r;
                    aux.width=space[i].x-r.x;
                    r.x+=aux.width;
                    r.width-=aux.width;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(r.x+r.width > space[i].x+space[i].width){
                    aux=r;
                    aux.x=space[i].x+space[i].width;
                    aux.width=r.x+r.width-aux.x;
                    r.width-=aux.width;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(r.y < space[i].y){
                    aux=r;
                    aux.height=space[i].y-aux.y;
                    r.y+=aux.height;
                    r.height-=aux.height;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(r.y+r.height > space[i].y+space[i].height){
                    aux=r;
                    aux.y=space[i].y+space[i].height;
                    aux.height=r.y+r.height-aux.y;
                    r.height-=aux.height;
                    if(!removerectangle(space,aux,ntxn)){
                        return FALSE;
                    }
                }
                if(areEqual(space[i], r)){
                    space[i].deleted=ntxn;
                    return TRUE;
                }
                else {
                    if(!removerectangle(space,r,ntxn)){
                        return FALSE;
                    }
                    return TRUE;
                }
            }
        }
    }
    return TRUE;
}
int main(int argc, char *argv[]){
    int side=15;
    int n=5;
    int budget=0;
    int status;
    while((status=getopt(argc,argv,"l:n:")) >= 0){
        switch(status){
        case 'l':
            sscanf(optarg,"%d",&side);
            break;
        case 'n':
            sscanf(optarg,"%d",&n);
            break;
        }
    }
    budget=64;
    while(solve(side,n,budget) == FALSE){
        budget+=16;
    }
}

```

---
Tags: code-challenge, optimization, restricted-time, tiling
---


title: The Eratosthenes Shuffle

text:
# Question
Title: The Eratosthenes Shuffle
# Challenge

Write a function or program that accepts a line of input, performs a very specific and oddly familiar shuffle on its characters, and outputs the result.

The required shuffling can be described using the following algorithm:

1. Label each character in the input with a 1 based index.
2. Write character number 1 as output.
3. Starting with character number 2, write every other character to the output in order, *excluding* character 2 itself. In other words, write characters 4, 6, 8, 10, and so on as output.
4. Starting with the next character number n not yet written as output, write every nth character to the output, *excluding* character n itself, and excluding any other character (by numeric label) you may have already written to the output.
5. Repeat step 4 as long it continues to add new characters to the output.
6. Write the remaining characters to output, in order.

# Example

1. Label the characters.

```
 *1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27*
  O  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R

```

2. Write the first character to output:

```
 *~~**1**~~  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27*
  ~~**O**~~  L  D     D  O  C     Y  A  K  '  S     B  E  A  U  T  Y     C  O  R  N  E  R
**O**

```

3. Write every other character starting with 2, excluding 2.

```
 *~~1~~  2  3  ~~**4**~~  5  ~~**6**~~  7  ~~**8**~~  9 ~~**10**~~ 11 ~~**12**~~ 13 ~~**14**~~ 15 ~~**16**~~ 17 ~~**18**~~ 19 ~~**20**~~ 21 ~~**22**~~ 23 ~~**24**~~ 25 ~~**26**~~ 27*
  ~~O~~  L  D   D  ~~**O**~~  C   Y  ~~**A**~~  K  ~~**'**~~  S   B  ~~**E**~~  A  ~~**U**~~  T  ~~**Y**~~     ~~**C**~~  O  ~~**R**~~  N  ~~**E**~~  R
O **O A' EUYCRE**
```

4. The next character not yet written is character number 3; write every 3rd character starting with 3, but excluding character 3 itself, and any character already written.

```
 *~~1~~  2  3  ~~4~~  5  ~~6~~  7  ~~8~~  ~~**9**~~ ~~10~~ 11 ~~12~~ 13 ~~14~~ ~~**15**~~ ~~16~~ 17 ~~18~~ 19 ~~20~~ ~~**21**~~ ~~22~~ 23 ~~24~~ 25 ~~26~~ ~~**27**~~*
  ~~O~~  L  D   D  ~~O~~  C   ~~**Y**~~  ~~A~~  K  ~~'~~  S   ~~**B**~~  ~~E~~  A  ~~U~~  T  ~~Y~~   ~~C~~  O  ~~R~~  N  ~~E~~  ~~**R**~~
O O A' EUYCRE**YB R**
```

5. Repeat step 4 using the next character, character 5.

4. The next character not yet written is character number 5; write every 5th character starting with 5, but excluding character 5 itself, and any character already written. (This amounts to just character 25).

```
 *~~1~~  2  3  ~~4~~  5  ~~6~~  7  ~~8~~  ~~9~~ ~~10~~ 11 ~~12~~ 13 ~~14~~ ~~15~~ ~~16~~ 17 ~~18~~ 19 ~~20~~ ~~21~~ ~~22~~ 23 ~~24~~ ~~**25**~~ ~~26~~ ~~27~~*
  ~~O~~  L  D   D  ~~O~~  C   ~~Y~~  ~~A~~  K  ~~'~~  S   ~~B~~  ~~E~~  A  ~~U~~  T  ~~Y~~   ~~C~~  O  ~~R~~  ~~**N**~~  ~~E~~  ~~R~~
O O A' EUYCREYB R**N**
```

5. The next character is 7; but 14, 21 have already been written, so no more characters would be output if we repeat step 4. Thus, we're done with 5.

6. Write the remaining characters out in order.

```
 *~~1~~ **2  3**  ~~4~~ **5**  ~~6~~ **7**  ~~8~~  ~~9~~ ~~10~~ **11** ~~12~~ **13** ~~14~~ ~~15~~ ~~16~~ **17** ~~18~~ **19** ~~20~~ ~~21~~ ~~22~~ **23** ~~24~~ ~~25~~ ~~26~~ ~~27~~*
  ~~O~~ **L  D**  **D**  ~~O~~ **C**   ~~Y~~  ~~A~~ **K**  ~~'~~ **S**   ~~B~~  ~~E~~ **A**  ~~U~~ **T**  ~~Y~~   ~~C~~ **O**  ~~R~~  ~~N~~  ~~E~~  ~~R~~
O O A' EUYCREYB RN**LDDCKSATO**
```

# Rules

Input and output may be via standard input/standard output, strings, or arrays of characters.

If reading in as standard input you may at your convenience assume there's a trailing newline, or that the entire input contains the line. Newline characters do not participate in the shuffle.

Likewise, at your convenience, your output may either have a trailing newline or not.

Standard loopholes are disallowed.

This is a code golf competition. Smallest code in bytes wins.

# Test Cases

```
123456789ABCDEF -> 1468ACE9F2357BD

OLD DOC YAK'S BEAUTY CORNER -> O O A' EUYCREYB RNLDDCKSATO

Blue boxes use a 2600hz tone to convince telephone switches that use in-band signalling that the caller is actually a telephone operator.
->
Bebxsuea20h oet ovnetlpoesice htuei-adsgaln httecle satal  eehn prtre 0ncce ha nng aiuapootnt ihyon atallu o s 6z oi ehwstsnbilt lr clee.

```

# Answer
# Jelly, 10 bytes

```
JÆfṂ$ÞÆPÞị

```

**TryItOnline**

### How?

```
JÆfṂ$ÞÆPÞị - Main link: theString
J          - range(length), the 1-based indexes of theString
     Þ     - sort these by
    $      -     last two links as a monad
 Æf        -         prime factorization array (e.g. 20 -> [2,2,5])
   Ṃ       -         minimum
        Þ  - sort these by
      ÆP   - isPrime, i.e. move all the primes to the right
         ị - index into theString

```
> 4 votes

# Answer
# Mathematica, 61 bytes

```
#[[SortBy[Range@Length@#,FactorInteger[#][[1,1]]PrimeQ@#&]]]&

```

Unnamed function taking a list of characters as input and returning a list of characters.

`FactorInteger[#][[1,1]]` yields the smallest prime factor of `#` (and returns `1` if `#` equals `1`). Therefore `FactorInteger[#][[1,1]]PrimeQ@#` yields a strange expression: \[`#`'s smallest prime factor\] `False` if `#` is not prime, and `# True` if `#` is prime (these are unevaluated products of a number and a boolean).

`Range@Length@#` yields a list of the numbers up to the length of the input. Then `SortBy` sorts those numbers by the funny function described above. Mathematica is really type-sensitive in many ways, but cheerfully mixes them in other ways: expressions of the form \[number\] `False` are alphabetically sorted before expressions of the form \[number\] `True`, while ties are broken by sorting the numbers numerically. That produces exactly the permutation we want here, and `#[[...]]` permutes the characters of the input accordingly.
> 5 votes

# Answer
## C, 164 bytes

This takes input as the first command parameter and prints back to stdout. As we process each character, we clear it, allowing the final pass.

```
#define p putchar
main(c,s,i,j,t)char**s,*t;{c=strlen(t=s[1]);p(*t);for(;j++<c;)if(t[j])for(i=2*j+1;i<=c;i+=j+1)!t[i]?:p(t[i]),t[i]=0;for(j=0;j++<c;)!*++t?:p(*t);}

```
> 2 votes

---
Tags: code-golf
---


title: Time taken to print numbers

text:
# Question
Title: Time taken to print numbers
# Summary

Write a program or function, which doesn't take any input, and outputs all the integer numbers, between -1000 and 1000 in ascending order, to the stdout, one per line, like this:

```
-1000
-999
-998
-997
...

```

And after that you need to print the time taken to print these numbers, or the time from the start of the program's execution in milliseconds (if necessary, it can also contain some other things, for example: time taken:xxxms is ok). It can be a float, or an integer (if you print an integer, you need to round down to the nearest).

# Example code

```
using System;
using System.Diagnostics;
class P
{
    static void Main(string[] args)
    {
        Stopwatch st = Stopwatch.StartNew();
        for (int i = -1000; i <= 1000; i++)
        {
            Console.WriteLine(i);
        }
        Console.WriteLine(st.ElapsedMilliseconds);
    }
}

```

# Restrictions

Standard loopholes are not allowed

# Other infos

It's code golf, so the shortest submission wins.

# Answer
# MATL, 13 bytes

```
1e3t_y&:!DZ`*

```

Try it online!

```
       % Implicitly start timer
1e3    % Push 1000
       % STACK: 1000
t_     % Duplicate, negate
       % STACK: 1000, -1000
y      % Duplicate second-top number
       % STACK: 1000, -1000, 1000
&:     % Two-input range
       % STACK: 1000, [-1000, 999, ..., 1000]
!      % Transpose into column vector
       % STACK: 1000, [-1000; 999; ...; 1000]
D      % Display
       % STACK: 1000
Z`     % Push timer value, say t
       % STACK: 1000, t
*      % Multiply
       % STACK: 1000*t
       % Implicitly display

```
> 9 votes

# Answer
# Octave, ~~46~~ ~~43~~ ~~36~~ ~~30~~ 23 bytes

```
tic;(-1e3:1e3)',toc*1e3

```

This will print:

```
ans =

  -1000
   -999
   -998
   -997
   -996
   -995

```

If you don't like the `ans =` , then we have to add an additional 6 bytes for `disp`:

```
tic;disp((-1e3:1e3)'),toc*1e3

```

Saved a lot of bytes thanks to a few reminders from rahnema1.

**Explanation:**

```
tic;                              % Starts timer
         (-1e3:1e3)'              % A vertical vector -1000 ... 1000
    disp((-1e3:1e3)'),            % Display this vector
                      toc*1e3     % Stop the timer and output the time in milliseconds

```
> 9 votes

# Answer
# JavaScript, 60 bytes

```
(c=console).time();for(i=~1e3;i++<1e3;c.log(i));c.timeEnd();

```

In order to get all the events logged, you should use the script from the developer console (otherwise the logs are erased after the certain amount of them).
> 8 votes

# Answer
# Python 3.5, ~~80~~ ~~77~~ 73 bytes

```
import time
*map(print,range(-1000,1001)),
print(time.process_time()*1e3)

```

Previous solutions involved using `timeit` and `time.time()`, they were larger.

Sadly, `time.process_time()` was introduced in python 3.3.

Thanks to Dennis for saving 4 bytes!
> 7 votes

# Answer
# CJam, 18 bytes

```
es2001{1e3-n}/es\-

```

Try it online!

### How it works

```
es                  Push the current time (milliseconds since epoch) on the stack.
  2001{     }/      For each integer X from 0 to 2000:
       1e3-           Subtract 1000 from X.
           n          Print with a newline.
              es    Push the current time on the stack.
                \-  Swap and subtract.

```
> 7 votes

# Answer
# Bash (+coreutils), ~~41~~, ~~49~~, ~~46~~, ~~44~~, 42 bytes

EDITS:

* Refactored to use Bash-builtin (time), to address @Dennis precision concerns;
* Reduced by 3 bytes, by utilizing Bash 4+ `|&` for stderr redirection;
* Saved 2 more bytes by replacing `seq -1000 1000` with `seq -1e3 1e3` (Thanks @Dennis !);
* -2 bytes by removing unnecessary backslash, and using default precision (Thx @Dennis !).

**Golfed**

```
TIMEFORMAT=%R*1000;(time seq -1e3 1e3)|&bc

```

Try It Online !

**Sidenote**

Using a coreutils "time" utility, instead of the Bash-builtin, results in a ~~41~~, 35 byte solution:

```
\time -f "%e*1000" seq -1e3 1e3|&bc

```

***"\\"*** is here to make *bash* invoke the real command, instead of the builtin.

Unfortunately coreutils *time* precision is only 1/100s, which have raised concerns on if it is a valid solution.
> 5 votes

# Answer
# Bash + GNU utils, 43

* Saved 2 bytes thanks to @Dennis
* Saved 5 bytes thanks to @zeppelin

```
c=date\ +%s%3N
s=`$c`
seq -1e3 1e3
$c-$s|bc

```

The `date` command gives the number of seconds since the epoch concatenated with current nanoseconds. This command is run before and after. `bc` takes the difference and prints.

Try it online.

---

I was hoping to do this for 17:

```
time seq -1e3 1e3

```

But the output of time gives more than we need:

```
real    0m0.004s
user    0m0.000s
sys 0m0.004s

```
> 4 votes

# Answer
# JavaScript (ES6), ~~63~~ 59 bytes

```
for(c=console.log,i=~1e3;i<1e3;c(++i));c(performance.now())
```
> 4 votes

# Answer
## R, 42 bytes

```
system.time(cat(-1e3:1e3,sep="\n"))[3]*1e3

```

This will print

```
.
.
.
998
999
1000
elapsed
     60

```

To remove `elapsed`, two additional bytes are necessary:

```
system.time(cat(-1e3:1e3,sep="\n"))[[3]]*1e3

```
> 4 votes

# Answer
# PHP, ~~110~~ 70 bytes

still a little long; but saved 38 with @AlexHowansky´s hint, and two more with `1e3` and `~1e3`.

```
for($t=($m=microtime)($i=~1e3);$i++<1e3;)echo"$i
";echo($m(1)-$t)*1e3;

```

prints float. Run with `-r`.
> 3 votes

# Answer
## R, 66 bytes

```
x=proc.time();for(i in -1e3:1e3)cat(i,"\n");(proc.time()-x)[3]*1e3

```

Probably not the shortest but it works.
> 3 votes

# Answer
# Mathematica, 51 bytes

```
p[1*^3#]&@@AbsoluteTiming@Array[p=Print,2001,-1*^3]

```

**Explanation**

```
Array[p=Print,2001,-1*^3]

```

Store the `Print` function in `p`. Print 2001 numbers, starting at -1000, incrementing by 1.

```
AbsoluteTiming@ ...

```

Find the total time elapsed in seconds.

```
p[1*^3#]&@@ ...

```

Multiply that by 1000 (seconds -\> miliseconds) and `p` (`Print`) it.
> 3 votes

# Answer
## Powershell, 27 Bytes

```
$1=date;-1e3..1e3;(date)-$1

```

Thanks to AdmBorkBork for pointing out that the verbose default output is acceptable in the challenge.

Outputs result like:

```
994
995
996
997
998
999
1000

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 5
Milliseconds      : 679
Ticks             : 56799255
TotalDays         : 6.57398784722222E-05
TotalHours        : 0.00157775708333333
TotalMinutes      : 0.094665425
TotalSeconds      : 5.6799255
TotalMilliseconds : 5679.9255

```

for more contained result of just milliseconds, use original answer:

```
$1=date;-1e3..1e3;((date)-$1).TotalMilliseconds

```

Save time before as $1, print to stdout automatically, then get the time between the beginning and end of execution.
> 3 votes

# Answer
# Perl 6, 45 bytes

```
.put for -($_=1e3)..$_;put (now -INIT now)*$_

```

Try it

## Expanded:

```
# print the values

.put             # print with trailing newline ( method call on ｢$_｣ )

for              # for each of the following
                 # ( temporarily sets ｢$_｣ to the value )

-(
  $_ = 1e3       # store ｢Num(1000)｣ in ｢$_｣
)
..               # inclusive Range object
$_;

# print the time elapsed

put              # print with trailing newline

(now - INIT now) # Duration object that numifies to elapsed seconds
* $_             # times 1000 to bring it to milliseconds

# The ｢INIT｣ phaser runs code (the second ｢now｣) immediately
# as the program starts.

# There is no otherwise unrelated set-up in this code so this is a
# reliable indicator of the amount of time it takes to print the values.

```
> 2 votes

# Answer
# 8th, ~~61~~ 47 bytes

*Thanks to 8th\_dev for nice improvement* (saved 14 bytes)

```
d:msec ( . cr ) -1000 1000 loop d:msec swap - .

```

This will print all the integer numbers between -1000 and 1000 in ascending order and the time taken (in milliseconds) to print these numbers

```
-1000
-999
-998
-997
...
997
998
999
1000
4

```
> 2 votes

# Answer
# Pyth, ~~18~~ ~~15~~ 14 bytes

```
j}_J^T3J;*.d1J

```

Try it here!

**Explanation**

This is similar to my python answer.

```
    J^T3           Set J to 1000
  }_    J         List ranging from -1000 to 1000
j                 Join the list with new lines and implicitly print it
         ;*.d1J   Print time since execution of the program in milliseconds

```

**Edits**:
> 2 votes

# Answer
# , 22 bytes

```
1e3*timex'echo,.i:1e3'

```

Try it online!

`timex` is a builtin that executes the string and returns the time it took to evaluate it in seconds. The string forms the range \[-1000, 1000\] using `i:`, then columinizes it using `,.`, and prints it using the builtin `echo`.
> 2 votes

# Answer
# Groovy, ~~75~~ 73 bytes

```
t=System.&nanoTime
s=t()
(-1000..1e3).each{println it}
print((t()-s)/1e6)

```

Thanks to jaxad0127 for saving 2 bytes!

Try it here !
> 2 votes

# Answer
# Matlab, ~~16~~ 23 Bytes

```
tic;(-1e3:1e3)'
toc*1e3

```

Edit: I realised I was violating several of this challenge's rules. That'll teach me to skim read the challenge late at night. I also now realise that the corrected answer is almost identical to the Octave solution, but such is life.

Prints each element in the created linear space array -1000:1000 (the lack of ; prints to console).

tic/toc records the time and toc prints the time to the console with or without the ; . 1e3 is needed to print in milliseconds.
> 2 votes

# Answer
# Noodel, ~~17~~ 13 bytes

**13 bytes**

Tried a slightly different approach and saved 4 bytes.

```
ƇQjȥḶGQɱ⁻Ñ€Ƈ⁻

```

Try it:)

### How it works

```
Ƈ             # Pushes on the amount of milliseconds passed since 01/01/1970.

 Qjȥ          # Pushes 2001 onto the stack.
 Qj           # Pushes on the string "Qj"
   ȥ          # Converts the string into a number as base 98.

    ḶGQɱ⁻Ñ€   # Loops 2001 times printing -1000 to 1000.
    Ḷ         # Consumes the 2001 and loops the following code 2001 times.
     GQ       # Pushes on the string "GQ"
       ɱ      # Pushes on the current counter of the loop (i)
        ⁻     # Subtracts (i - "GQ") since i is a number, the "GQ" is converted to a number which will fail.
              # So, Noodel will treat the string as a base 98 number producing (i - 1000).
         Ñ    # Consume what is on the top of the stack pushing it to the screen followed by a new line.
          €   # The end of the loop.

           Ƈ⁻ # Calculates the duration of execution.
           Ƈ  # Pushes on the amount of milliseconds passed since 01/01/1970.
            ⁻ # Pushes on (end - start)

```

---

**17 bytes**

```
ƇGQȥḋɲṡ×2Ḷñ⁺1€ÑƇ⁻

```

Try it:)

### How it works

```
Ƈ                 # Pushes on the amount of milliseconds passed since 01/01/1970.

 GQȥḋɲṡ×2         # Used to create the range of numbers to be printed.
 GQ               # Pushes on the string "GQ".
   ȥ              # Converts the string into number as if it were a base 98 number. (which is 1000)
    ḋ             # Duplicates the number and pushes it onto the stack.
     ɲ            # Since the item on top is already a number, makes the number negative (random thing I threw in at the very beginning when made the langauge and totally forgot it was there)
      ṡ           # Swaps the first two items on the stack placing 1000 on top.
       ×2         # Doubles 1000 producing... 2000

         Ḷñ⁺1€Ñ   # Prints all of the numbers from -1000 to 1000.
         Ḷ        # Consumes the 2000 to loop the following code that many times (now -1000 is on the top).
          ñ       # Prints the value on top of the stack followed by a new line.
           ⁺1     # Increment the value on top of the stack by 1.
             €    # End of the loop.
              Ñ   # Since 1000 is still not printed, this consumes 1000 and prints it followed by a new line.

               Ƈ⁻ # Calculates the number of milliseconds to execute program.
               Ƈ  # Pushes on the amount of milliseconds passed since 01/01/1970.
                ⁻ # Pushes on (end - start) in milliseconds.
                  # At the end, the top of the stack is pushed to the screen.

```

---

The snippet uses the values -4 to 4 in order to not take so long to complete.

```
<div id="noodel" code="ƇFȥḶAɱ⁻Ñ€Ƈ⁻" input="" cols="10" rows="10"></div>

<script src="https://tkellehe.github.io/noodel/noodel-latest.js"></script>
<script src="https://tkellehe.github.io/noodel/ppcg.min.js"></script>
```
> 2 votes

# Answer
# TI-Basic, 22 bytes

```
startTmr
For(A,-ᴇ3,ᴇ3
Disp A
End
startTmr-Ans

```
* Many commands are represented by 1 or 2-byte tokens.
* Tested on an emulated TI-84 CSE.
> 2 votes

# Answer
# Japt, 23 bytes

There are two equivalent solutions:

```
Oo(Ð -(A³òA³n @OpXÃ,Ð¹n
K=Ð;A³òA³n @OpXÃ;OoÐ -K

```

The first one basically does the following:

```
output(-(new Date() - (1000 .range(-1000).map(X => print(X)), new Date())));

```

That is, the numbers are printed in the middle of the subtraction to avoid having to store the time in a variable. However, it's not any shorter than the variable route, which is basically:

```
K = new Date(); 1000 .range(-1000).map(X => print(X)); output(new Date() - K);

```

In the latest version of Japt (newer than this challenge), `K` is set up to automatically return `new Date()`. This cuts the first solution down to 21 bytes:

```
Oo(K-(A³òA³n @OpXÃK)n

```

Test it online!
> 2 votes

# Answer
## QBIC, 34 bytes

```
d=timer[-z^3,z^3|?a]?z^3*(timer-d)

```

Uses the QBasic `TIMER` function, which returns seconds in decimal notation. Making it look pretty adds some bytes.

Explanation

```
d=timer     Set 'd' to the current # seconds since midnight
[-z^3,z^3|  FOR -1000 to 1000  --  Note that 'z' = 10 in QBIC, and z^3 saves a byte over 1000
?a          Display the iterator
]           Close the FOR loop
    timer-d Take the current time minus the time at the start of the program -- 0.156201
?z^3*()     Multiply by a thousand and display it   156.201

```
> 1 votes

# Answer
## Racket, 72 bytes

```
(time(map(lambda(x)(display(exact-floor x))(newline))(range -1e3 1001)))

```
> 1 votes

# Answer
## C++ - 261

Just for a laugh I thought I'd post a C++ answer.

```
#include <iostream>
#include <chrono>
using namespace std::chrono; using c=std::chrono::system_clock; void p(){c::time_point n=c::now();for(int i=-1001;++i<1001;)std::cout<<i<<"\n";std::cout<<(duration_cast<milliseconds>(system_clock::now()-n)).count()<<"\n";}

```

I'll leave it as an exercise to determine what it is doing and how to call it - shouldn't be too difficult.
> 1 votes

# Answer
## C ~~134~~ 133 bytes

Thanks to @Thomas Padron-McCarthy for saving 1 byte.

```
f(){clock_t s,e;s=clock();for(int i=-1000;i<1001;i++)printf("%d\n",i);e=clock();printf("%lf",((double)((e-s))/(CLOCKS_PER_SEC))*1e3);}

```

Ungolfed version :

```
void f()
{
  clock_t s,e;

  s=clock();

  for(int i=-1000;i<1001;i++)
    printf("%d\n",i);

  e=clock();
  printf("%f",((double)((e-s))/(CLOCKS_PER_SEC))*1e3);

 }

```
> 1 votes

# Answer
# Scala, 77 bytes

```
def t=System.nanoTime
val s=t
Range(-1000,1001)map println
println((t-s)/1e6)

```
> 1 votes

# Answer
# ForceLang, 124

```
set t timer.new()
set i -1000
label 1
io.writeln set i i+1
if i=1000
 io.write math.floor 0.001.mult t.poll()
 exit()
goto 1

```

Note: You should supress `stderr` when running this. I believe the consensus on meta is that this does not incur a byte count penalty.
> 1 votes

# Answer
# SimpleTemplate, 92 bytes

What really killed me was the need to record the time.

```
{@callmicrotime intoX 1}{@for_ from-1000to1000}{@echol_}{@/}{@phpecho microtime(1)-$DATA[X]}

```

Since there's no math (yet), this makes things pretty hard, forcing me to write PHP directly.

**Ungolfed:**

```
{@call microtime into start_time true}
{@for i from -1000 to 1000 step 1}
    {@echol i}{@// echoes a newline after}
{@/}
{@php echo microtime(true) - $DATA["start_time"];}

```

---

**Disclaimer:**

I've ran this with the commit e118ae72c535b1fdbe1b80c847f52aa161854fda, from 2017-01-13.

The latest commit was to fix something that is un-related to the code in here.
> 1 votes

# Answer
# Gura, 75 bytes

```
t=datetime.now();println(-1000..1000);print((datetime.now()-t).usecs/1000);

```
> 1 votes

# Answer
# Clojure, 94 bytes

```
(let[t #(System/currentTimeMillis)s(t)](doseq[n(range -1e3 1001)](println n))(println(-(t)s)))

```

I'm disappointed at how long this got, but I guess no one ever claimed Clojure was a good language to golf in.

Naïve solution that just records the starting time, loops, then prints the current time minus the starting time. Unless Clojure has a ms-time getter than I'm missing, I don't know how this could get any shorter. Maybe some kind of implicit loop?

```
(defn time-print []
  (let [t #(System/currentTimeMillis) ; Alias the time-getter to "t"
        start (t)] ; Record starting time
    (doseq [n (range -1000 1001)] ; Loop over the range...
      (println n)) ; ... printing the numbers

    (println (- (t) start)))) ; Then print the current time minus the starting time.

```
> 1 votes

# Answer
# SAS, 36 bytes

Pretty straightforward, SAS prints out the time taken for a data step by default..

```
data c;do i=-1000 to 1000;put i;end;

```
> 1 votes

# Answer
# C# - 123

This isn't going to win anything but hey, here it goes :)

```
()=>{var t=DateTime.Now;var s="";for(int i=-1000;i<1001;i++)s+=i+"\n";Console.WriteLine(s+(DateTime.Now-t).Milliseconds);};

```

Run like this:

```
Action y = ()=>{var t=DateTime.Now;var s="";for(int i=-1000;i<1001;i++)s+=i+"\n";Console.WriteLine(s+(DateTime.Now-t).Milliseconds);};
y();

```
> 0 votes

# Answer
# Lua, 47 Characters

```
for i=-1e3,1e3 do print(i)end print(os.clock())

```

It's nice and simple, a basic printing for loop from -1e3 to 1e3, then just print the os.clock, which is conveniently the ms since program execution.
> 0 votes

# Answer
# tcl, 58

```
set i -1001;puts [time {time {puts [incr i]} 2001}]

```

testable on http://rextester.com/WQVC76600

Note: The answer is given as `microseconds per iteration` — The iterations here indicated belong to the outermost `time` command, which are implicitly `1` when its `iterations` parameter is omitted, which is the case; and not about the loop iterations!
> 0 votes

# Answer
# Pyth, 19 bytes

~~**Edit:** So apparently `.d1` is the process time. Saved 6 bytes.~~

**Edit:** `.d1` is the process time in µseconds, so I have to multiply it by 1000.

`K^T3FNr_KhKN;*K.d1`

This is a naive solution that pretty much does what's asked without any trick. I'm a beginner with Pyth and still getting the hang out of it. Any suggestion would be very appreciated!

## Explanation

```
K^T3FNr_KhKN;*K.d1
K^T3                     Assigns 10^3 to K
    FNr_KhK              Loops on N from -1000 to 1000
           N;            Each loop, print N
             *K.d1       Prints process time * 1000

```
> 0 votes

# Answer
# Forth, 60 bytes

`utime` \- *Report the current time in microseconds since some epoch.*

```
utime
: f 1001 -1000 do I dup . CR loop ; f
utime - 1000 / .

```
> 0 votes

# Answer
# Java 7, 125 bytes

```
void c(){long x=System.nanoTime(),i=-1001;for(;i<1e3;)System.out.println(++i);System.out.println((System.nanoTime()-x)/i/i);}

```

**Ungolfed:**

```
void c() {
  long x = System.nanoTime(),
       i = -1001;
  for(; i < 1e3; ){
    System.out.println(++i);
  }
  System.out.println((System.nanoTime() - x) / i / i);
}

```

**Test code:**

Try it here.

```
class M{
  static void c(){long x=System.nanoTime(),i=-1001;for(;i<1e3;)System.out.println(++i);System.out.println((System.nanoTime()-x)/i/i);}

  public static void main(String[] a){
    c();
  }
}

```

**Example output:**

```
-1000
-999
...
...
...
999
1000
13

```
> 0 votes

---
Tags: code-golf, number, date
---