title: Multi-level free parking space finder

text:
# Question
Title: Multi-level free parking space finder
### Kids-related intro

Whenever I take my kids to an amusement park, the kids get more nervous the closer we are to the park, with the nerve peak when we are in the parking lot and find no place to park. So I've decided I need a method to find the closest free parking space to minimise the time spent parking.

### Technical intro

Imagine a representation of a parking lot like this one:

```
*****************
*               *
* ··CC··C··CC·· *
* ************* *
* ··CCCCCCCCC·· *
*               *
**********E******

```

In this representation a `*` means a wall, a `·` a free parking space, a `E` the entry point and a `C` a car already parked. Every whitespace is a position the car to be parked can use to move around the parking lot. Now let's extend this concept to 3D to create a multi-level parking lot:

```
    1st floor            2nd floor            3rd floor            4th floor
*****************    *****************    *****************    *****************
*               1    *               2    *               3    *               *
* CCCCCCCCCCCCC *    * CCCCCCCCCCCCC *    * ····C··CCCCCC *    * ······C······ *
* ************* *    * ************* *    * ************* *    * ************* *
* CCCCCCCCCCCCC *    * CCCCCCCCCCCCC *    * ···CCCCCCCCCC *    * ··C·······C·· *
*               *    *               1    *               2    *               3
**********E******    *****************    *****************    *****************

```

The numbers `1`, `2` and `3` represent the connections between levels. The `1` from the first floor connects with the `1` in the second floor so a car stepping into the `1` position in the first floor appears in the `1` position in the second floor.

### Challenge

Giving a scheme of a parking lot like the previously shown, write the shortest program that calculates the distance to the nearest free parking space, according to the following

### Rules

* The input will be a 3D char array or a 2D string array or equivalent, and the output will be a single integer representing the number of steps the car must take to get to the nearest free parking space. If you receive a 3D char array the first index may represent the floor number and the second and third indices the (x,y) position for each floor, but this is up to you.
* There won't be more than 9 ramps, represented by `[1-9]`.
* The car starts from the `E` position (there will be only one entry point per map) and moves around using the whitespaces in one of four directions each time: up, down, left, right. The car can also step into `·` positions and `[1-9]` positions.
* Every change of position (step) counts as 1, and every time the car goes from one floor to another counts as 3 as the car must take a ramp. In this case, the movement from a whitespace beside a `1` to the `1` itself is what counts as 3 steps, because as a result of this movement the car appears in the `1` position on the other floor.
* The car can't go beyond the matrix limits.
* The count will end when the car to be parked is in the same position as a `·`. If there are no reachable free parking spaces you can return zero, a negative integer, a null value or an error.

### Examples

In the example above the result would be 32, as it is cheaper to go to the fourth floor and park in the closest parking space near the `3`. The nearest free parking spaces in the third floor are at a distance of 33 and 34.

Other examples:

```
    1st floor            2nd floor            3rd floor            4th floor
*****************    *****************    *****************    *****************
*               1    *               2    *               3    *               *
* CCCCCCCCCCCCC *    * CCCCCCCCCCCCC *    * ····C··CCCCCC *    * ······C······ *
* ************* *    * ************* *    * ************* *    * ************* *
* CCCCCCCCCCCCC *    * ·CCCCCCCCCCCC *    * ···CCCCCCCCCC *    * ··C·······C·· *
*               *    *               1    *               2    *               3
**********E******    *****************    *****************    *****************

Answer: 28 (now the parking space in the 2nd floor is closer)

    1st floor            2nd floor            3rd floor            4th floor
*****************    *****************    *****************    *****************
*               1    4               2    5               3    6               *
* CCCCCCCCCCCCC *    * CCCCCCCCCCCCC *    * ····C··CCCCCC *    * ······C······ *
* ************* *    * ************* *    * ************* *    * ************* *
* CCCCCCCCCCCCC *    * CCCCCCCCCCCCC *    * ···CCCCCCCCCC *    * ··C·······C·· *
4               *    5               1    6               2    *               3
**********E******    *****************    *****************    *****************

Answer: 24 (now it's better to go to ramp 4 and then to ramp 5 to the third floor)

    1st floor            2nd floor            3rd floor            4th floor
*****************    *****************    *****************    *****************
*               1    *               *    *               3    *               2
* CCCCCCCCCCCCC *    * CCCCCCCCCCCCC *    * ····C··CCCCCC *    * ······C······ *
* ************* *    * ************* *    * ************* *    * ************* *
* CCCCCCCCCCCCC *    * ·CCCCCCCCCCCC *    * ···CCCCCCCCCC *    * ··C·······C·· *
*               *    *               3    *               2    *               1
**********E******    *****************    *****************    *****************

Answer: 16 (now the parking space in the 4th floor is closer)

 1st floor     2nd floor     3rd floor     4th floor     5th floor
************  ************  ************  ************  ************
*CCCCCCCCC 1  *CCCCCCCCC 2  *CCCCCCCCC 3  *·CCCCCCCC 4  *········C *
*          *  *          *  *          *  *          *  *          *
*CCCCCCCCC E  *CCCCCCCCC 1  *CCCCCCCCC 2  *··CCCCCCC 3  *·······CC 4
************  ************  ************  ************  ************

Answer: 29 (both the nearest parking spaces at the 4th and 5th floors are at the same distance)

 1st floor     2nd floor     3rd floor
************  ************  ************
*CCCCCCCCC 1  *CCCCCCCCC 2  *CCCCCCCCC *
*          *  *          *  *          *
*CCCCCCCCC E  *CCCCCCCCC 1  *CCCCCCCCC 2
************  ************  ************

Answer: -1 (no free parking space)

 1st floor
************
*          *
*          *
*         E*
************

Answer: -1 (no parking space at all)

 1st floor
************
* ·····    *
*·      ****
* ····· * E
*********

Answer: -1 (the parking lot designer was a genius)

```

### Alternatives

* You can use whatever characters you want to represent the parking lot map, just specify in your answer which are your chosen characters and what they mean.

This is , so may the shortest program/method/lambda/whatever for each language win!

*If you need help with the algorithm, please check my (ungolfed) implementation in C#.*

# Answer
> 6 votes
# JavaScript (ES6), 199 bytes

Takes input as an array of arrays of arrays of characters, using the characters described in the challenge. Returns \\$0\\$ if there's no free parking space.

```
a=>(m=g=(c,t,f,x,y,F=f||a.find(r=>r.some((a,i)=>~(y=i,x=a.indexOf(c)))),r=F[y])=>r&&(c=r[x])&&(r[x]=g,c>'z'?m=m<t?m:t:!f|c<1?[0,-1,0,1].map((d,i)=>g(0,-~t,F,x+d,y+~-i%2)):+c&&g(c,t+2),r[x]=c))('E')|m

```

Try it online!

### How?

The recursive function **g()** takes as input:

* **c** : the character of the entry point we're looking for if we've just left a floor or we are at the very beginning of the process; **0** otherwise
* **t** : the total number of moves so far (initially *undefined*)
* **f**, **x**, **y** : a pointer to the current floor and the current coordinates in this floor; they are all *undefined* if we're looking for a new floor

If **f** is defined, we simply copy it to the current floor **F**. Otherwise, we need to look for the new floor and the new coordinates by iterating over each floor and over each row until we find the entry point **c**:

```
F = f || a.find(r => r.some((a, i) => ~(y = i, x = a.indexOf(c))))

```

We define **r** as the current row in the current floor:

```
r = F[Y]

```

The next step is to make sure that the current cell **c** at **(x, y)** is defined:

```
r && (c = r[x]) && ...

```

If it is, we mark it as visited by setting it to **g**, a value that does not trigger any of the forthcoming tests:

```
r[x] = g

```

If **c** is a free parking space, we stop the recursion. And if the total number of moves is lower than our previous best score, we update **m** accordingly:

```
c > 'z' ? m = m < t ? m : t : ...

```

If we've just reached a new floor (**f** is *undefined*) or **c** is a space, we process a recursive call for each surrounding cell:

```
!f | c < 1 ?
  [0, -1, 0, 1].map((d, i) =>
    g(0, -~t, F, x + d, y + ~-i % 2)
  )
:
  ...

```

Otherwise, if **c** is a ramp marker (i.e. a non-zero digit), we process a single recursive call to reach the new floor:

```
+c && g(c, t + 2)

```

Finally, we restore the current cell to its initial value so that it can be visited again in other recursion paths:

```
r[x] = c

```

# Answer
> 4 votes
# Powershell, ~~299~~ 292 bytes

It is assumed that the map is rectangle.

It uses `x` instead `·`. To get `·`, you need to save script as ASCII (not UTF-8) and replace `x` on `·`.

```
filter f{$l=($_-split"
")[0].length
$p,$d,$e='x','\d',' '|%{"$_(?=E)|(?<=E)$_|$_(?=[\s\S]{$l}E)|(?<=E[\s\S]{$l})$_"}
for($r=1;$_-notmatch$p;$r++){$m=$_-replace'F','E'-replace'G','F'-replace'H','G'
if($m-match$d){$m=$m-replace$Matches[0],'H'}$m=$m-replace$e,'E'
if($m-eq$_){return -1}$_=$m}$r}

```

Ungolfed and test script:

```
filter f{
    #Write-Host "`nStep:`n$_" # uncomment this to display each step

    $l = ($_ -split "`n")[0].length
    $p,$d,$e = 'x', '\d', ' '| % {"$_(?=E)|(?<=E)$_|$_(?=[\s\S]{$l}E)|(?<=E[\s\S]{$l})$_"}

    for($r = 1;$_ -notmatch $p;$r++) {
        $m = $_ -replace 'F', 'E' -replace 'G', 'F' -replace 'H', 'G'
        if ($m -match $d) {
            $m = $m -replace $Matches[0], 'H'
        }
        $m = $m -replace $e, 'E'

        if ($m -eq $_) {
            return -1
        }

        $_=$m
    }
    $r
}

@(
    , (2, @"
****
*x E
****
"@)
    , (1, @"
****
* xE
****
"@)
    , (1, @"
****
* x*
* E*
****
"@)
    , (1, @"
****
* E*
* x*
****
"@)
    , (-1, @"
****
2 E1
*  *
****
"@)
    , (28, @"
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*               *
**********E******
*****************
*               2
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               1
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               *
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               3
*****************
"@)
    , (16, @"
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*               *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************
"@)
    , (29, @"
************
*CCCCCCCCC 1
*          *
*CCCCCCCCC E
************
************
*CCCCCCCCC 2
*          *
*CCCCCCCCC 1
************
************
*CCCCCCCCC 3
*          *
*CCCCCCCCC 2
************
************
*xCCCCCCCC 4
*          *
*xxCCCCCCC 3
************
************
*xxxxxxxxC *
*          *
*xxxxxxxCC 4
************
"@
    )
    , (-1, @"
************
*          *
*          *
*         E*
************
"@)
    , (-1, @"
************
* xxxxx    *
*x      ****
* xxxxx * E
*********
"@)
) | % {
    $e, $m = $_
    $r = $m|f
    "$($e-eq$r): $r $e"
}

```

Output:

```
True: 2 2
True: 1 1
True: 1 1
True: 1 1
True: -1 -1
True: 28 28
True: 16 16
True: 29 29
True: -1 -1
True: -1 -1

```

Extended output for parking with 16 steps:

```
Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*               *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*         E     *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*        EEE    *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*       EEEEE   *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*      EEEEEEE  *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*     EEEEEEEEE *
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCC *
*    EEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* ************* *
* CCCCCCCCCCCCCE*
*   EEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCC *
* *************E*
* CCCCCCCCCCCCCE*
*  EEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*               1
* CCCCCCCCCCCCCE*
* *************E*
* CCCCCCCCCCCCCE*
* EEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*              E1
* CCCCCCCCCCCCCE*
* *************E*
* CCCCCCCCCCCCCE*
*EEEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               1
*****************

Step:
*****************
*             EEH
* CCCCCCCCCCCCCE*
* *************E*
*ECCCCCCCCCCCCCE*
*EEEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               H
*****************

Step:
*****************
*            EEEG
* CCCCCCCCCCCCCE*
*E*************E*
*ECCCCCCCCCCCCCE*
*EEEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               G
*****************

Step:
*****************
*           EEEEF
*ECCCCCCCCCCCCCE*
*E*************E*
*ECCCCCCCCCCCCCE*
*EEEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*               F
*****************

Step:
*****************
*E         EEEEEE
*ECCCCCCCCCCCCCE*
*E*************E*
*ECCCCCCCCCCCCCE*
*EEEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxx *
*              EE
*****************

Step:
*****************
*EE       EEEEEEE
*ECCCCCCCCCCCCCE*
*E*************E*
*ECCCCCCCCCCCCCE*
*EEEEEEEEEEEEEEE*
**********E******
*****************
*               *
* CCCCCCCCCCCCC *
* ************* *
* xCCCCCCCCCCCC *
*               3
*****************
*****************
*               3
* xxxxCxxCCCCCC *
* ************* *
* xxxCCCCCCCCCC *
*               2
*****************
*****************
*               2
* xxxxxxCxxxxxx *
* ************* *
* xxCxxxxxxxCxxE*
*             EEE
*****************
True: 16 16

```

## Explanation

It's kind of Lee pathfinding algorithm. Only one smart thing: 3 steps on ramp are realized as a dummy states `H->G->F->E`

---

# Powershell for a genius parking lot designer, ~~377~~ 369 bytes

Parking design is an `2D string array`. No assumtions about map: any length strings, floors without walls, parking without an entry point, multi-floor-and-multi-exit-ramps. Genus cost is +26%.

```
filter f{for($r=1;$_-notmatch$p;$r++){$m=$_-replace'F','E'-replace'G','F'-replace'H','G'
if($m-match$d){$m=$m-replace$Matches[0],'H'}$m=$m-replace$e,'E'
if($m-eq$_){return-1}$_=$m}$r}$g={$l=($args|%{$_|%{$_.length}}|sort)[-1]
$p,$d,$e='x','\d',' '|%{"$_(?=E)|(?<=E)$_|$_(?=[\s\S]{$l}E)|(?<=E[\s\S]{$l})$_"}
(($args|%{$_.PadRight($l,'*')-join"
"})-join"
"+'-'*$l+"
")|f}

```

Ungolfed and test script:

```
filter f{
    #Write-Host "`nStep:`n$_" # uncomment this to display each step

    for($r = 1;$_ -notmatch $p;$r++) {
        $m = $_ -replace 'F', 'E' -replace 'G', 'F' -replace 'H', 'G'
        if ($m -match $d) {
            $m = $m -replace $Matches[0], 'H'
        }
        $m = $m -replace $e, 'E'

        if ($m -eq $_) {
            return -1
        }

        $_=$m
    }
    $r
}

$g = {

    $l = ($args| % {$_| % {$_.length}}|sort)[-1]
    $p,$d,$e = 'x', '\d', ' '| % {"$_(?=E)|(?<=E)$_|$_(?=[\s\S]{$l}E)|(?<=E[\s\S]{$l})$_"}
    (($args| % {$_.PadRight($l, '*') -join "`n"}) -join "`n"+'-' * $l+"`n")|f

}

@(
    , (2, @(, (
                "****",
                "*x E",
                "****"
            )))
    , (1, @(, (
                "****",
                "* xE",
                "****"
            )))
    , (1, @(, (
                "****",
                "* x*",
                "* E*",
                "****"
            )))
    , (1, @(, (
                "****",
                "* E*",
                "* x*",
                "****"
            )))
    , (-1, @(, (
                "****",
                "2 E1",
                "*  *",
                "****"
            )))
    , (28, @(, (
                "*****************",
                "*               1",
                "* CCCCCCCCCCCCC *",
                "* ************* *",
                "* CCCCCCCCCCCCC *",
                "*               *",
                "**********E******"
            ), (
                "*****************",
                "*               2",
                "* CCCCCCCCCCCCC *",
                "* ************* *",
                "* xCCCCCCCCCCCC *",
                "*               1",
                "*****************"
            ), @(
                "*****************",
                "*               3",
                "* xxxxCxxCCCCCC *",
                "* ************* *",
                "* xxxCCCCCCCCCC *",
                "*               2",
                "*****************"
            ), @(
                "*****************",
                "*               *",
                "* xxxxxxCxxxxxx *",
                "* ************* *",
                "* xxCxxxxxxxCxx *",
                "*               3",
                "*****************"
            )))
    , (16, @(, (
                "*****************",
                "*               1",
                "* CCCCCCCCCCCCC *",
                "* ************* *",
                "* CCCCCCCCCCCCC *",
                "*               *",
                "**********E******"
            ), @(
                "*****************",
                "*               *",
                "* CCCCCCCCCCCCC *",
                "* ************* *",
                "* xCCCCCCCCCCCC *",
                "*               3",
                "*****************"
            ), @(
                "*****************",
                "*               3",
                "* xxxxCxxCCCCCC *",
                "* ************* *",
                "* xxxCCCCCCCCCC *",
                "*               2",
                "*****************"
            ), @(
                "*****************",
                "*               2",
                "* xxxxxxCxxxxxx *",
                "* ************* *",
                "* xxCxxxxxxxCxx *",
                "*               1",
                "*****************"
            )))
    , (29, @(, (
                "************",
                "*CCCCCCCCC 1",
                "*          *",
                "*CCCCCCCCC E",
                "************"
            ), @(
                "************",
                "*CCCCCCCCC 2",
                "*          *",
                "*CCCCCCCCC 1",
                "************"
            ), @(
                "************",
                "*CCCCCCCCC 3",
                "*          *",
                "*CCCCCCCCC 2",
                "************"
            ), @(
                "************",
                "*xCCCCCCCC 4",
                "*          *",
                "*xxCCCCCCC 3",
                "************"
            ), @(
                "************",
                "*xxxxxxxxC *",
                "*          *",
                "*xxxxxxxCC 4",
                "************"
            )))
    , (-1, @(, (
                "************",
                "*          *",
                "*          *",
                "*         E*",
                "************"
            )))
    , (-1, @(, (
                "************",
                "* xxxxx    *",
                "*x      ****",
                "* xxxxx * E",
                "*********"
            )))
) | % {
    $e, $m = $_
    $r = &$g @m
    "$($e-eq$r): $r $e"
}

```

# Answer
> 3 votes
# Kotlin, 768 bytes

used period . instead of ·. Wish I understood Arnauld's answer because losing 500 bytes would be nice.

```
fun s(l:List<List<CharArray>>)={val b=listOf(l.size-1,l[0].size-1,l[0][0].size-1)
val e=Int.MAX_VALUE
var r=e
var t=listOf(e,e,e)
val d=Array(b[0]+1){Array(b[1]+1){Array(b[2]+1){e}}}
val f={c:Char,n:List<Int>->var a=t
(0..b[0]).map{f->(0..b[1]).map{r->(0..b[2]).map{var s=listOf(f,r,it)
if(l[f][r][it]==c&&!s.equals(n))a=s}}}
a}
fun m(p:List<Int>,c:Int){if(p[0]in 0..b[0]&&p[1]in 0..b[1]&&p[2]in 0..b[2]&&d[p[0]][p[1]][p[2]]>c){d[p[0]][p[1]][p[2]]=c
val h=l[p[0]][p[1]][p[2]]
when(h){' ','E'->(-1..1 step 2).map{m(listOf(p[0],p[1]+it,p[2]),c+1)
m(listOf(p[0],p[1],p[2]+it),c+1)}
'.'->if(r>c)r=c
in '1'..'9'->{val n=f(h,p)
d[n[0]][n[1]][n[2]]=c+2
(-1..1 step 2).map{m(listOf(n[0],n[1]+it,n[2]),c+3)
m(listOf(n[0],n[1],n[2]+it),c+3)}}}}}
m(f('E',t),0)
if(r<e)r
else-1}()

```

Try it online!

---
Tags: code-golf, array, path-finding, maze
---


title: Display a tally (in varying bases)

text:
# Question
Title: Display a tally (in varying bases)
Tallying is a simple counting system that works in base 5. There are various different tallying systems used around the world, but the one that is used in most English-speaking countries is perhaps the most simple - count units by marking vertical lines, then for each 5th mark put a horizontal line through the previous collection of four. This clusters the tally marks in groups of 5 (and makes them easier to quickly count).

You are going to write a program that displays tally marks up to a given value. But, tallying in only base 5 is boring! Therefore, your program should also be able to display tallies in different bases.

## Input

The input will be **either one or two non-negative integer values** separated by a comma (e.g. `9` or `8,4`). The first number is the value that should be displayed by the tally. The second value is the base of the tally. **If the second value is not given, use base 5**.

## Output

The output will be the inputted value represented as ASCII art tally marks. Here are some examples you can test your program against - your output should match them exactly!

Input: `12` or `12,5`

```
 | | | |   | | | |   | |
-+-+-+-+- -+-+-+-+-  | |
 | | | |   | | | |   | |

```

Input: `7,3`

```
 | |   | |   |
-+-+- -+-+-  |
 | |   | |   |

```

Input: `4,2`

```
 |   |
-+- -+-
 |   |

```

Input: `6,1` or `6,10` (notice the leading spaces)

```
 | | | | | |
 | | | | | |
 | | | | | |

```

Note also that base 1 is intended to be inconsistent - only vertical lines should be used.

If either of the inputted values is 0, there should be **no output whatsoever** (and your program should end gracefully).

## Rules

* This is , so the shortest correct implementation (in bytes) wins.
* Input/output can be in any suitable medium (e.g. stdin/stdout, file...).
* Input can be in the form of multiple command-line arguments or separated by spaces, etc. if it is more suitable for your target language.
* Trailing newlines are allowed in the output. Trailing spaces are not. This rule only applies when there is an output (i.e. not when the inputted value is 0).
* Your code must default to base 5 when no base is input.

# Answer
> 4 votes
## CJam *103* *85* **72** characters

Try it at http://cjam.aditsu.net/.

## original

```
q","/(i:A\_,{~i}{;5}?:B_@*{(_{" |"*S"l"++AB/*AB%}{;MA}?\:J" |l""-+ "er\" |"*N+_J\+@2$+@J\+++"l"Ser}{;}?

```

Works by defining one set of tallys with spaces, lines and an l for spaces that should remain spaces. Then takes advantage of er (tranliteration) function to make the second line. Most inefficient part is dealing with the 1 and 0 special cases. Will edit as I improve it. Tip I took too long to realize: as the second input being 1 is the same as infinity or the first input +1, redefining it when it is equal to 1 saves alot of work.

## most improved so far with comma delimited

```
l",":G/(i:A\_5a?~i:B_@*{(_" |":K*\{SG++AB/*AB%}{A}?\_KG+"-+ "er[\GSer_@@M]\K*N+*}{;}?

```

## most improved so far with space delimited input

Naturally as CJam is really designed for space delimited input. Placing the input at 20 3 instead of 20,3 is a huge benefit.

```
ri:Aq_5s?S-i(_)A)?:B*{B(" |":K*STs++ABmd@@*_K"-+"er[\_@@M]\K*N+*TsSer}M?

```

# Answer
> 5 votes
# Python 2 - ~~111 108 119 144 140 136 135~~ 134 - Try it

Ok, let's give it a try:

```
i=input()
n,b=[(i,5),i][i>[]]
o=b-1
a=[n,n%b][b>1]*' |'
m=(b>1)*n/b
s=(' |'*o+'  ')*m+a
print(s+'\n'+('-+'*o+'- ')*m+a+'\n'+s)*(b*n>0)

```

**Edit:** I've overlooked that there should be no output if `n==0` or `b==0`. This costs me 11 characters. :(

**Edit:** Ok, after fixing the second issue mentioned in the comments my solution basically converged to the one from BeetDemGuise.

# Answer
> 5 votes
# Bash, ~~239 228 199 189~~ 188

Here's my attempt, it could be golfed a lot.

Note: the second line does not subtract 5 from 2, it sets a default value if `$2` is empty!

```
n=$1
b=${2-5}
((n<1&b<1))&&exit
while ((n>b&b>1));do
n=$[n-b]
x+=\
y+=-
for i in `seq $[b-1]`;{
x+='| '
y+=+-
}
x+=\
y+=\
done
for j in `seq $n`;{
x+=' |'
y+=' |'
}
echo -e "$x\n$y\n$x"

```

# Answer
> 3 votes
## Python - ~~171~~ 143

```
i=input();t,b=i if[0]<i else(i,5);b=[b,t+1][b==1];l,d,m,o=' |',t/b,t%b,b-1;r=(l*o+'  ')*d+l*m
if t*b>0:print r,'\n',('-+'*o+'- ')*d+l*m,'\n',r

```

The program is pretty straight-forward:

* Get the input and try to unpack into `t,b`. If that fails, simply assign the correct values.
* If the base was `1`, change its value to something that can handle all vertical lines easily (`t+1`).
* Set some variables and create the bottom and top sections of the tallies.
* Print out the tallies if both `t` and `b` are non-zero.

**EDIT 1:** Use the `input` function instead of `raw_input` after some playing around.

**EDIT 2:** Thanks to Falko for pointing out a small bug with my non-zero checking. Now our code is basically identical, less some variable names and some small logic.

**EDIT 3:** Thanks to how Python compares sequences and different types, we can compare `i` to a `list` to get a shorter version of our `try...except` block.

Here is the ungolfed version:

```
i=input()

# If True, `i` must be a list
if [0]<i:
    t,b=i
# Otherwise, we know its a number (since `list` comes after `int` lexicographically.)
else:
    b=5
    t=i

b = b if b==1 else t+1
l=' |'
d=t/b
m=t%b
o=b-1

r=(l*o+'  ')*d+l*m
if t and b:
    print r,'\n',('-+'*o+'- ')*d+l*m,'\n',r

```

# Answer
> 3 votes
# C - 193

I'm so sorry. Dealing with the special case for 1 was a bit of a bad hack so I guess this could be golfed more with a better approach. Also, this code includes a new line at the beginning of the output, so if this is not allowed, please let me know.

Of course, very ugly-looking defines always help :)

Character count includes only necessary spaces and new lines.

```
#define P printf(
#define L P" |")
#define A P"\n");for(i=0;i<a;)b==1?i++,L:i++&&i%b==0?P
i;
main(a,b)
{
    scanf("%d,%d",&a,&b)<2?b=5:!b?a=0:a;
    if(a){
    A"  "):L;
    A"- "):a%b&&i>a/b*b?L:P"-+");
    A"  "):L;}
}

```

# Answer
> 3 votes
## Java, 343

```
class C{public static void main(String[]a){long n=new Long(a[0])+1,b=a.length>1?new Long(a[1]):5;if(b>0){if(b<2)b=(int)2e9;int i;for(i=1;i<n;i++)p(i%b>0?" |":"  ");p("\n");for(i=1;i<n-n%b;i++)p(i%b>0?"-+":"- ");if(n>b)p("- ");for(i=1;i<n%b;i++)p(" |");p("\n");for(i=1;i<n;i++)p(i%b>0?" |":"  ");}}static void p(String s){System.out.print(s);}}

```

Less golfed:

```
class C {
  public static void main(String[] a) {
    long n=new Long(a[0])+1, b=a.length>1 ? new Long(a[1]) : 5;
    if(b>0) {
      if(b<2) b=(int)2e9; // if the base is 1, pretend the base is 2 billion
      int i;
      for(i=1;i<n;i++) p(i%b>0 ? " |" : "  ");
      p("\n");
      for(i=1;i<n-n%b;i++) p(i%b>0 ? "-+" : "- ");
      if(n>b) p("- ");
      for(i=1;i<n%b;i++) p(" |");
      p("\n");
      for(i=1;i<n;i++) p(i%b>0 ? " |" : "  ");
    }
  }
  static void p(String s) {
    System.out.print(s);
  }
}

```

# Answer
> 3 votes
# Perl - ~~167~~ ~~165~~ 156

```
my($n,$b)=($ARGV[0]=~/(\d+)(?:,(\d+))?/,5);print$b>1?map{join(" ",($_ x($b-1))x int($1/$b)," | "x($1%$b))."\n"}(" | ","-+-"," | "):join" ",("---")x$1if$1*$b

```

## ungolfed

```
my($n,$b) = ($ARGV[0] =~ /(\d+)(?:,(\d+))?/, 5);
print($b>1 ?
    map{
        join(" ",($_ x ($b-1)) x int($1/$b)," | " x ($1%$b))."\n"
    } (" | ","-+-"," | ") :
    join " ", ("---") x $1
) if $1 * $b

```

# Answer
> 2 votes
## C# 271bytes

Not the shortest, I couldn't golf the input reading due to it needing to accept 0 as an input.

```
using C=System.Console;class P{static void Main(){var L=C.ReadLine().Split(',');int t=int.Parse(L[0]),f=L.Length>1?int.Parse(L[1]):5,r=3,i;for(var R="";t*f>0&r-->0;C.WriteLine(R.TrimEnd()))for(R="",i=0;i<t;R+=r==1&i++<t-t%f?(i%f<1?"- ":"-|"):i%f<1?"  ":" |")f+=f<2?t:0;}}

```

Formatted code:

```
using C=System.Console;

class P
{
    static void Main()
    {
        var L=C.ReadLine().Split(',');
        int t=int.Parse(L[0]),f=L.Length>1?int.Parse(L[1]):5,r=3,i;

        for(var R="";t*f>0&r-->0;C.WriteLine(R.TrimEnd()))
            for(R="",i=0;i<t;R+=r==1&i++<t-t%f?(i%f<1?"- ":"-|"):i%f<1?"  ":" |")
                f+=f<2?t:0;
    }
}

```

# Answer
> 1 votes
# Lua - ~~219~~ 203 bytes

I went for the make d copies of b copies of "|", then add r copies of "|" at the end. I feel like maybe I should have gone with the 'tally up' the "|"s to the string one at a time.

```
l=' |'s=string.rep _,_,a,b=io.read():find'(%d+)%D*(%d*)'b=tonumber(b)or 5 d=(a-a%b)/b f=b>1 and s(s(l,b-1)..'  ',d)g=b>1 and s(s('-+',b-1)..'- ',d)r=b>1 and a%b or a e=s(l,r)..'\n'print(f..e..g..e..f..e)

```

ungolfed:

```
l=' |'          --the base string
s=string.rep    --string.rep will be used a lot, so best shorten it

_,_,a,b=io.read():find'(%d+)%D*(%d*)' --reads a,b I'm probably way of the mark with this one

b=tonumber(b)or 5

d=(a-a%b)/b -- shorter than math.floor(a/b), d equal the vertical mark

f=b>1 and s(s(l,b-1)..'  ',d) or '' --creates d multiples of b multiples of "|" more or less
g=b>1 and s(s('-+',b-1)..'- ',d)or''--same as above but with the middle "-+-"

r=b>1 and a%b or a --idk maybe i should set r before d(a- a%b )/b

e=s(l,r)..'\n'  -- makes the remainder string, notice that if b==1  then e will output all the "|"

print(f..e..g..e..f..e) -- here's where the real magic happens!

```

Sample:

```
c:\Programming\AnarchyGolfMine>lua test.lua
13,5
 | | | |   | | | |   | | |
-+-+-+-+- -+-+-+-+-  | | |
 | | | |   | | | |   | | |

c:\Programming\AnarchyGolfMine>lua test.lua
6,2
 |   |   |
-+- -+- -+-
 |   |   |

c:\Programming\AnarchyGolfMine>lua test.lua
18,1
 | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | |

```

# Answer
> 1 votes
## JavaScript (193)

This might be overly complex.

```
s=prompt().split(",");a=+s[0];b=s[1];b=b?+b:5;o=b>1;v=" | ";q=w="";for(g=~~(a/b),c=o?a-g:a;g+1;g--,q+=" ",w+=" ")for(i=o;c&&i<b;i++)c--,q+=v,w+=g&&o?"-+-":v;if(a&&b)console.log(q+'\n'+w+'\n'+q)

```

---

**Commented version**

```
s=prompt().split(",");
a=+s[0];
b=s[1];
b=b?+b:5;   // convert b to int and default to 5
o=b>1;      // special handling for b0 and b1
v=" | ";
q=w="";
// calculate number of lines and number of groups
for(g=~~(a/b),c=o?a-g:a;g+1;g--,q+=" ",w+=" ")
    for(i=o;c&&i<b;i++)
        c--,  // decrease line count
        q+=v,
        w+=g&&o?"-+-":v; // use " | " for last group and "-+-" for others
if(a&&b) // handle b0
    console.log(q+'\n'+w+'\n'+q)

```

# Answer
> 1 votes
# Python - ~~127~~ ~~123~~ 122

Just sneaking in with a slightly shorter python version.

edit: Fixed 0 not printing nothing and rejigger, ended up the same length

```
k=input()
k=i,j=((k,5),k)[k>[]]
for m in[' |','-+',' |']*all(k):
 print(m*(j-1)+m[0]+' ')*(i/j*(j>1))+' |'*(i%(j+(j<2)*i))

```

# Answer
> 0 votes
# C (207 characters)

The newline right before `exit` is for legibility only.

```
#define P printf(
#define t(v)for(a=c;b<=a;a-=b)a-c&&P" "),P v+1),q(b,v);q(a," |");P"\n");
q(n,c){while(n--)P c);}a;b;c;main(){scanf("%d,%d",&c,&b)<2?b=5:0;b&&c||
exit();b==1?b=32767:0;t("| ")t("+-")t("| ")}

```

`scanf` usage shamelessy stolen from Allbeert. Notice that this solution does not compile with gcc as it tries to enforce a nonexistant prototype for `exit`. Compile with a working C compiler like `tcc`. Also, this function may or may not work on 64 bit platforms. Use with care.

Here is the original ungolfed implementation this is based on:

```
#include <stdio.h>
#include <stdlib.h>

static void
tally_line(int base, int count, const char *str)
{
     int follower = 0, i;

     /* full tallies first */
     for (; count >= base; count -= base) {
          if (follower++)
               putchar(' ');

          /* only print second character */
          printf(str + 1);

          for (i = 0; i < base; i++)
               printf(str);
     }

     /* partial tally */
     for (i = 0; i < count; i++)
          printf(" |");

     /* newline */
     puts("");
}

extern int
main(int argc, char **argv)
{
     int base, count;

     /* do away with program name */
     count = atoi(*++argv);

     base = argc - 3 ? 5 : atoi(*++argv);

     /* remove 0 later */
     base | count || exit(0);

     /* a crossed-out tally never appears for large numbers */
     if (base == 1)
          base = 32767;

     tally_line(base, count, "| ");
     tally_line(base, count, "+-");
     tally_line(base, count, "| ");

     return (EXIT_SUCCESS);
}

```

# Answer
> 0 votes
# Python 2, ~~134~~ ~~126~~ ~~123~~ 114 bytes

```
lambda i,j=5,a=" |":"\n".join(("",(a*~-j+"  ","-+"*~-j+"- ")[x%2]*(i/j))[j>1]+a*(i,i%j)[j>1]for x in(0,1,2)if i*j)

```

Try it online!

Old question I know but fun to have a go at anyway. Chance to try out a few tricks I've learned since joining.

---
Tags: code-golf, math, ascii-art, counting
---


# Question
Title: Generate an expression yielding near-equidistributed result
Create a program (any language) which, given positive integer `m`, outputs a valid C *expression* that:

1. Uses a single variable `x` assumed of 32-bit unsigned type (i.e. `uint32_t`)
2. Would evaluate to range \[0, `m`) for any of the 2³² possible `x`, reaching any of the `m` possible outcomes either 2³² / `m` or 2³² / `m` \+ 1 times (where / rounds down).
3. Is limited to use of
    * variable `x` as operand
    * constants from 0 to 2³²-1, in decimal (`42`) or hexadecimal (`0x2a`)
    * *operators* among (listed by groups of decreasing priority in C)
        + `+` `-` restricted to addition or subtraction of two operands
        + `<<` `>>` restricted to right argument constant in range \[0, 31\]
        + `&` restricted to bitwise and
        + `^` bitwise xor
        + `|` bitwise *or*
    * parenthesis for `(`*expression*`)`
    * sequence idiom `(x=`*expression1*`),`*expression2* which evaluates *expression1*, assigns it to `x`, then evaluates to *expression2*. The sequence idiom can only be used to form the overall expression or *expression2* in a sequence. `,` and `=` do not account as operator.

It is assumed all arithmetic is such that all quantities are truncated to 32-bit, and that right shift `>>` introduce zeroes.

When given input `m`, the first output of the program must be an expression valid for `m`, aiming at a minimal operator count. Further output, if any, should be expressions for incremental `m`.

Example outputs (believed optimum) for first few inputs `m`:

```
output                     m  count  alternative output
0                          1    0    (0)
x&1                        2    1    x>>31
(x-(x>>1)+(x>>2))>>30      3    5    (x=x-(x>>2)),(x=x-(x>>31)),x>>30
x&3                        4    1    x>>30

```

---

Following comment, this is a *code challenge*. Ranking criteria:

1. Producing conforming expressions with minimum operator count up to the highest `m`. Expressions posted or linked in other answers are used to assess minimum, after verification.
2. Minimal expression depth up to the highest `m`. Depth is 0 for `x` or constant. The result of an operator has the maximum depth of the two operands when they differ or in a sequence, or 1 more otherwise. Expressions in the example output have depth 1, except for `0`. The expression `x+1&x+2^x+3&x+4` has depth 3, and any shorter expression has lower depth.
3. Programs that convincingly produce minimal output (as defined above) are preferred.
4. Programs which can be evaluated at compile time by a C/C++ compiler for constant `m`, so that use of `R(x,m)` generates the same object code as the expression for `m` does, are preferred. Nice-to-have: not requiring C++, not requiring `inline`.

---

Motivation: starting from `x` uniformly random, we want to restrict it to \[0, `m`) with a distribution comparable to the expression `x%m`, in a way that is fast and constant-time. Count and depth match instruction and register count on LEG Brain M0, an imaginary 32-bit CPU.

---

Modifying the following C program changing `E` and `M`, then compiling and running it on a compiler with 32-bit int, exhaustively checks an expression against requirement 2, assuming that it is a well-formed C expression that matches requirements 1 and 3. Try it online!

```
// Verify an expression for requirement 2

// expression under test
#define E (x=x-(x>>2)),(x=x-(x>>31)),x>>30
#define M 3                     // value of m matching that expression

#define T uint32_t              // type for x (change at your own risk!)
#define N 32                    // number of bits in type T
#define C (T)                   // cast to type T; use in E only!

#include <stdint.h>
typedef T t;                    // type for x
#include <inttypes.h>
#if N==32
    #define pPRIuTN "%"PRIu32
    #define pPRIxTN "%08"PRIx32
#elif N==16
    #define pPRIuTN "%"PRIu16
    #define pPRIxTN "%04"PRIx16
#elif N==8
    #define pPRIuTN "%"PRIu8
    #define pPRIxTN "%02"PRIx8
#endif
#include <stdio.h>
#include <string.h>

#define m ((t)M)     // m per our type
#define R(z) #z      // stringizer
#define S(z) R(z)

t c[m];              // counter array (initialized to 0)

int main(void) {
    t fail = sizeof(t)*8!=N || (t)(-1)<0 || ((t)(-1)>>(N-1))!=1,
        lo, hi, xlo, xhi, v, x, y = 0;
    if (fail)
        printf("### fail, please check T: "S(T)" versus N: "S(N)"\n");
    else
        {
    // laboriously show the expression tested, without extra parenthesis
        #define LEN (sizeof(S((E)))-3)  // length of the expression
        char exp[LEN+1];                // the expression, NUL-terminated
        memcpy(exp,S((E))+1,LEN);
        exp[LEN]=0;
        printf("Testing expression %s for m="pPRIuTN"\n",exp,m);
    // compute counts
        do {
            x = y;
            x = (E);
            if (x<m)
                ++c[x];
            else if (!fail) {
                fail = 1;
                printf("### fail, value "pPRIuTN" at input x="pPRIuTN"=0x"pPRIxTN" should be less than m="pPRIuTN"\n",x,y,y,m);
            }
        } while(++y);
    // find minimum and maximum count, and where it occurs
        hi = xlo = xhi = 0;
        lo = (t)-1;
        v = m;
        do {
            y = c[--v];
            if (y>hi)
                hi = y, xhi = v;
            else if (y<lo)
                lo = y, xlo = v;
        } while(v);
    // show results
        if (hi==0 && m>1) // can occur if there was overflow or other error
            fail=1, printf("### fail, only the value "pPRIuTN" occurs\n",x);
        else {
            x = (t)(-m)/m+1;   // lower limit
            y = (t)(-1)/m+1;   // upper limit
            if (lo<x)
                fail=1, printf("### fail, value "pPRIuTN" occurs "pPRIuTN" times, minimum "pPRIuTN"\n",xlo,lo,x);
            if (hi>y)
                fail=1, printf("### fail, value "pPRIuTN" occurs "pPRIuTN" times, maximum "pPRIuTN"\n",xhi,hi,y);
            if (!fail)
                printf("### pass!\n");
            }
        }
    return fail;
}

```

# Answer
# Haskell

```
import Data.Bits

bitLen :: Int -> Int
bitLen n = finiteBitSize n - countLeadingZeros n

expr' :: Maybe Int -> Int -> String
expr' sh m =
  case sh of
    Nothing
      | m == 1 -> "0"
      | n == 0 -> "x" ++ s
      | o == 0 -> "x-(x-(x>>1)>>" ++ show (i - j - 1) ++ ")" ++ s
      | otherwise ->
        "x-(x-(" ++ expr' (Just j) o ++ ")>>" ++ show (i - j) ++ ")" ++ s
      where s
              | i == 32 = ""
              | otherwise = ">>" ++ show (32 - i)
    Just h
      | n == 0 -> "x>>" ++ show (h - i)
      | o == 0 -> "(x-(x>>" ++ show (i - j) ++ ")>>" ++ show (h - i) ++ ")-1"
      | otherwise ->
        "x-(x-(" ++
        expr' (Just j) o ++ ")>>" ++ show (i - j) ++ ")>>" ++ show (h - i)
  where
    i = bitLen (m - 1)
    n = bit i - m
    j = bitLen (n - 1)
    o = bit j - n

expr :: Int -> String
expr = expr' Nothing

```

Try it online!

The first few expressions are

1. `0`
2. `x>>31`
3. `x-(x-(x>>1)>>1)>>30`
4. `x>>30`
5. `x-(x-(x>>2)>>1)>>29`
6. `x-(x-(x>>1)>>1)>>29`
7. `x-(x-(x>>1)>>2)>>29`
8. `x>>29`
9. `x-(x-(x>>3)>>1)>>28`
10. `x-(x-(x>>2)>>1)>>28`
11. `x-(x-((x-(x>>2)>>1)-1)>>1)>>28`
12. `x-(x-(x>>1)>>1)>>28`
13. `x-(x-(x>>2)>>2)>>28`
14. `x-(x-(x>>1)>>2)>>28`
15. `x-(x-(x>>1)>>3)>>28`
16. `x>>28`
17. `x-(x-(x>>4)>>1)>>27`
18. `x-(x-(x>>3)>>1)>>27`
19. `x-(x-((x-(x>>2)>>2)-1)>>1)>>27`
20. `x-(x-(x>>2)>>1)>>27`

# C++ template version

```
template <unsigned m> unsigned Rs(unsigned x, unsigned h);

template <unsigned o>
unsigned Rs2(unsigned x, unsigned h, unsigned i, unsigned j) {
  return (x - ((x - Rs<o>(x, j)) >> (i - j))) >> (h - j);
}
template <> unsigned Rs2<0>(unsigned x, unsigned h, unsigned i, unsigned j) {
  return ((x - (x >> (i - j))) >> (h - i)) - 1;
}

template <unsigned n> unsigned Rs1(unsigned x, unsigned h, unsigned i) {
  constexpr unsigned j = bitlen<n - 1>();
  constexpr unsigned o = (1 << j) - n;
  return Rs2<o>(x, h, i, j);
}
template <> unsigned Rs1<0>(unsigned x, unsigned h, unsigned i) {
  return x >> (h - i);
}

template <unsigned m> unsigned Rs(unsigned x, unsigned h) {
  constexpr unsigned i = bitlen<m - 1>();
  constexpr unsigned n = (1 << i) - m;
  return Rs1<n>(x, h, i);
}

template <unsigned o> unsigned R2(unsigned x, unsigned i, unsigned j) {
  return (x - Rs<o>(x, j)) >> (i - j);
}
template <> unsigned R2<0>(unsigned x, unsigned i, unsigned j) {
  return (x - (x >> 1)) >> (i - j - 1);
}

template <unsigned n> unsigned R1(unsigned x, unsigned i) {
  constexpr unsigned j = bitlen<n - 1>();
  constexpr unsigned o = (1 << j) - n;
  return R2<o>(x, i, j);
}
template <> unsigned R1<0>(unsigned, unsigned) { return 0; }

template <unsigned m> unsigned R(unsigned x) {
  constexpr unsigned i = bitlen<m - 1>();
  constexpr unsigned n = (1 << i) - m;
  return (x - R1<n>(x, i)) >> (32 - i);
}

```

For example, `gcc -O2` generates the following identical code for `R<19>(x)` and `x-(x-((x-(x>>2)>>2)-1)>>1)>>27`:

```
movl    %edi, %edx
movl    %edi, %ecx
leal    1(%rdi), %eax
shrl    $2, %edx
subl    %edx, %ecx
movl    %ecx, %edx
shrl    $2, %edx
subl    %edx, %eax
shrl    %eax
subl    %eax, %edi
movl    %edi, %eax
shrl    $27, %eax

```

# How it works

The expression being computed is equivalent to \\$\left\lfloor \frac{mx + m - c(m)}{2^{32}} \right\rfloor\\$, where \\$c(m)\\$ satisfies \\$0 \< c(m) \le m\\$. The specific choice of \\$c(m)\\$ made for golfing reasons is

$$ \begin{align\*} c(2^{i + 2}k + 2^i) &= 1 \quad (k \ge 0, i \ge 0), \\ c(2^i - 2^j) &= 1 \quad (i \> j \ge 0), \\ c(2^{h + 1}k + 2^h + 2^i - 2^j) &= 2^h \quad (k \ge 0, h \> i \> j + 1 \ge 1). \\ \end{align\*} $$

The equivalence can be shown by repeated use of the identity

$$ -{\left\lfloor \frac{k}{2^i} \right\rfloor} = \left\lfloor \frac{2^i - 1 - k}{2^i} \right\rfloor. $$
> 4 votes

---
Tags: code-generation, atomic-code-golf
---


title: Einstein's Sorter

text:
# Question
Title: Einstein's Sorter
## Challenge

Given a list of integers and a velocity, \\$v\\$, implement a sorting algorithm which simulates a program sorting the list from smallest to biggest at the given velocity.

## Einstein's Theory of Special Relativity

What do I mean? Well assume your program takes a time, \\$T\\$, to sort a particular list. If you ran the program again at a higher velocity, \\$v\\$, according to a stationary observer your program would run slower and would take a different time, \\$T'\\$, to sort the same list.

How do you relate \\$T\\$ to \\$T'\\$? You use the equation for time dilation:

$$T' = \frac{T}{\sqrt{1-v^2}}$$

If we use geometrised units where \\$v\\$ is a fraction of the speed of light, and \\$0\leq v \lt 1\\$.

So you must change your program's running time by a factor of

$$\frac{1}{\sqrt{1-v^2}}$$

## Output

You must output the sorted list

## Rules

* You are allowed an error of \\$\pm0.1 \text{ s}\\$
* The length of the list, \\$l\\$, will be in the range \\$1 \leq l \leq 50\\$
* The list will contain only integers
* The velocity will be given in geometrised units
* You may sort the list then wait before outputting

## Examples

For these examples, assume my program takes a time of \\$T = l^2 \text{ s}\\$ to run, where \\$l\\$ is the length of the list, regardless of the contents of the list:

```
List, Velocity > Sorted list, Time taken
[9,8,7,6,4,3,2,1], 0.5 > [1,2,3,4,5,6,7,8,9], 93.5307
[8,0,0,5,6], 0.1 > [0,0,5,6,8], 25.1259
[7,7,7,7,7,7,7], 0.999 > [7,7,7,7,7,7,7,7], 453.684

```

Your timings do not need to be as accurate.

## Winning

Shortest code wins.

# Answer
> 5 votes
# Bash, ~~56~~ 55 bytes

-1 bytes thanks to Digital Trauma (using `z` instead of pushing 1)

```
for n in $2;{
sleep `dc -e"9k$n z$1d*-v/f"`&&echo $n&
}

```

Try it online!

### Explanation

Sleep sort loops over all the integers, for each \\$n\\$ it does the following in the background:

* set a timer of \\$n\\$ seconds (or another time unit)
* print \\$n\\$

Instead of using one second we divide \\$n\\$ by \\$\frac{1}{\sqrt{1-v^2}}\\$ which is achieved by the following dc code:

```
9k              # set precision to 9 digits
  $n            # push n                    [n]
     z          # push size of stack        [1,n]
      $1        # push v                    [v,1,n]
        d*      # duplicate & multiply      [v^2,1,n]
          -     # subtract                  [1-v^2,n]
           v    # square root               [sqrt(1-v^2),n]
            /   # divide                    [n/sqrt(1-v^2)]
             f  # print

```

# Answer
> 2 votes
# Python 2, ~~88~~ ~~87~~ 91 bytes

-1 byte thanks to Mr. Xcoder

```
from time import*
def f(l,v):t=time();s=sorted(l);d=time()-t;sleep(d/(1-v*v)**.5-d);print s

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog), 52 bytes

```
{t←2⊃⎕AI⋄r←⍵[⍋⍵]⋄r⊣⎕DL 1e¯3×s-(s←t-2⊃⎕AI)÷.5*⍨1-⍺*2}

```

Try it online!

# Answer
> 0 votes
# Clean, 168 bytes

```
import StdEnv,System.Time,System._Unsafe,Debug.Performance
?u=:(Clock m,l)n#!(Clock i)=accUnsafe clock
|toReal i>toReal m*1E4/sqrt(one-n*n)=l= ?u n

```

#

```
?o(measureTime sort)

```

Try it online!

A composed function literal which times the sorting of the list, and then loops until an appropriate additional number of ticks have passed.

---
Tags: code-golf, array, date, sorting, physics
---


title: HelolW rdlo (A threading challenge)

text:
# Question
Title: HelolW rdlo (A threading challenge)
I have a challenge for you:

* Print "Hello World" using any language.
* Each character must be printed from its own, unique thread

That's it. Obviously, as there's no guarantee that the threads will operate in the order you start them, you have to make your program thread safe to ensure the output is printed in the right order.

And, because this is code golf, the shortest program wins.

**Update:**

The winner is Marinus' APL entry, at 34 characters. It also wins the prize for the least readable entry.

# Answer
> 10 votes
## APL (Dyalog) (~~44~~  ~~43~~ ~~39~~ 34)

```
{⍞←⍺⊣⎕DL⍵}&⌿2 11⍴'Hello World',⍳11

```

Explanation:

* `2 11⍴'Hello World',⍳11` creates a matrix: (H,1), (e,2), ...
* `&⌿` means: for each column of the matrix, do on a separate thread:
* In a thread,  is now the character and  is now the time
* `⎕DL⊃⍵` waits for  seconds.
* Then, `⍞←⍺` outputs the character.

# Answer
> 19 votes
## C, 61 62 chars

```
i;main(){write(1,"Hello World\n"+i++,1);i>13||fork()||main();}

```

The pthread library functions all have loooooong names, so instead I fired up an entire separate process for each character. `fork()` is so much shorter.

It was necessary to use `write()` instead of `putchar()` because the stdio buffering functions are not thread-safe.

**Edited**: Back up to 62 chars. In my zeal, dropping down to 61 chars also dropped the thread-safety.

# Answer
> 9 votes
### Ruby, 46 characters

```
"Hello World".chars{|c|Thread.new{$><<c}.join}

```

It is synchronized due to the fact that the program waits for the thread to end before starting the next thread and continuing with the next char.

# Answer
> 7 votes
# Pythonect (35 chars)

http://www.pythonect.org

```
"Hello World"|list|_.split()->print

```

# Answer
> 6 votes
## Python (~~101~~ ~~93~~ 98)

This is Peter Taylor's solution. It works by delaying printing the N-th character by N seconds. See comments.

```
import sys.threading as t
for x in range(11):t.Timer(x,sys.stdout.write,"Hello World"[x]).start()

```

This is the original one:

```
import sys,threading as t
for x in "Hello World":t.Thread(None,sys.stdout.write,x,x).start()

```

It worked because the time it takes to print a single character is less than the time it takes Python to initialize a new thread, therefore the N-th thread would finish before the N+1-th thread was created. Apparently it is against the rules to rely on this.

# Answer
> 4 votes
# C# 73

```
"hello world".ToList().ForEach(c=>Task.Run(()=>Console.Write(c)).Wait());

```

# Answer
> 4 votes
# APL (Dyalog Unicode), 28 bytesSBCS

Full program. Prints to stderr. Inspired by marinus' solution.

```
'Hello World'{⍞←⍺⊣⎕DL⍵}&¨⍳11

```

Try it online!

`⍳11` first 11 integers

`'Hello World'{``}&¨` for each integer as right argument (), spawn the following function with the corresponding character as left argument ():

`⎕DL⍵`**d**e**l**ay right-argument seconds

`⍺⊣` discard that (the effective delay) in favour of the left-argument character

`⍞←` print that to stdout without trailing line break

# Answer
> 3 votes
## Java (160 chars)

```
class A{static int i;public static void main(String...a){new Thread(){public void run(){System.out.print("Hello World".charAt(i++));if(i<11)main();}}.start();}}

```

Yeah, I know this is the wrong language for code golf, I do it for fun.

# Answer
> 2 votes
### scala(~~81~~ 79 chars)

```
def?(l:String){if(l.size!=0)new Thread{print(l(0));?(l.tail)}}
?("Hello World")

```

# Answer
> 2 votes
## Haskell (~~120~~ 118)

```
import Control.Concurrent
t=threadDelay.(*3^8)
main=(\(x,y)->forkIO$t x>>putChar y)`mapM_`zip[0..]"Hello World">>t 99

```

I'm not all that sure about multiplying by 9999 - I have a 2Ghz Xeon on which it'll work fine even if you don't, but I also have a Pentium 4 that needs it (999 gave garbled output and 99 didn't do anything at all.)

# Answer
> 2 votes
## Bash (64)

```
:(){ [ "$1" ]&&(echo -n "${1:0:1}"&: "${1:1}")};: "Hello World"

```

# Answer
> 2 votes
# Groovy, 51 characters

```
"Hello World".each{a->Thread.start{print a}.join()}

```

# Answer
> 1 votes
## D (135 chars)

```
import std.concurrency,std.stdio;
void main(){
    p("Hello World");
}
void p(string h){
    write(h[0]);
    if(h.length>1)spawn(&p,h[1..$]);
}

```

I only start the next thread when I have already printed the current char

edit +2 chars for better bound check

# Answer
> 1 votes
### Scala 74

```
"Hello World".zipWithIndex.par.map(x=>{Thread.sleep(x._2*99);print(x._1)})

```
* zipWithIndex produces ((H, 0), (e, 1), (l, 2) ...).
* par makes it a parallel collection.

Tests:

```
(1 to 10).foreach {_ => "Hello World".zipWithIndex.par.map(x=>{Thread.sleep(x._2*99);print(x._1)});println()}
Hello World
Hello World
Hello World
...
Hello World

```

# Answer
> 1 votes
### scala(45)

Thread#join based solution

```
"Hello World"map{x=>new Thread{print(x)}join}

```

or

```
for(x<-"Hello World")new Thread{print(x)}join

```

# Answer
> 1 votes
## Javascript (72)

```
(function f(){console.log("Hello world"[i++]);i<11&&setTimeout(f)})(i=0)

```

# Answer
> 1 votes
This is my F# attempt. My first serious F# program. Please be kind.

```
let myprint c = async {
        printfn "%c"c
}
"Hello World"|>Seq.map myprint|>Async.Parallel|>Async.RunSynchronously|>ignore

```

# Answer
> 0 votes
### C# ~~90~~ 84

```
foreach(var c in"Hello World"){var t=new Thread(Console.Write);t.Start(c);t.Join();}

```

Running version: http://ideone.com/0dXNw

# Answer
> 0 votes
## Go

```
package main
import"fmt"
func main(){o:=make(chan int)
for _,c:=range"Hello World"{go func(c rune){fmt.Printf("%c",c)
o<-0}(c)}
for i:=0;i<11;i++{<-o}}

```

# Answer
> 0 votes
# Erlang (90)

```
-module(h).
r()->r("Hello World").
r([])->'';r([H|T])->spawn(h,r,[T]),io:format("~c",[H]).

```

Compile `erlc +export_all h.erl`

# Answer
> 0 votes
## Nimrod, 121

```
proc p(c:char){.thread.}=write(stdout,c)
for c in "Hello World":
 var t:TThread[char]
 createThread(t,p,c)
 joinThread(t)

```

# Answer
> 0 votes
## Python: too many characters, but it works.

```
# Ok. First we patch Threading.start to test wether our solution actually works

import threading
import random, time
original_run = threading.Thread.run

def myRun(self):
    tosleep = random.randint(0,200)/1000.0
    time.sleep(tosleep)
    original_run(self)

threading.Thread.run = myRun

# And now the real code:
import time, sys, threading
string_to_write = "Hello World\n"
current_char_index = 0 # This integer represents the index of the next char to be written
# It will act as a semaphore: threads will wait until it reaches
# the index of the single char that particular thread is due to output

class Writer(threading.Thread):
    def __init__(self, char_to_write, index_to_write):
        self.char_to_write, self.index_to_write = char_to_write, index_to_write
        super(Writer, self).__init__()
    def run(self):
        ch = globals()['current_char_index']
        while not self.index_to_write == ch:
            time.sleep(0.005)
        sys.stdout.write(self.char_to_write)
        # This will be atomic because no other thread will touch it while it has "our" index
        globals()['current_char_index'] += 1

for i, char in enumerate(string_to_write):
    Writer(char, i).start()

```

# Answer
> 0 votes
**Objective-C (183 characters)**

```
-(void) thread {[self performSelectorInBackground:@selector(printC) withObject:nil];}
-(void) printC {char *c = "Hello World"; for(int i = 0; c[i] != '\0'; i++) {printf("%c", c[i]);}}

```

# Answer
> 0 votes
## Haskell 99 Characters

```
import Control.Concurrent
f[]=return()
f(x:xs)=(putChar x)>>(forkIO$f xs)>>f[]
main=f"Hello World"

```

How it works is each thread starts the next after having displayed its character, so they actually useful stuff can not happen out of sequence.

# Answer
> 0 votes
# Bash, 43 bytes

```
xargs -n1 printf<<<'H e l l o \  W o r l d'

```

Try it online!

`xargs` forks a separate `printf` process for each character (and waits for it to exit).

# Bash, 45 bytes, no external utilities

```
eval \(printf\ {H,e,l,l,o,\\\ ,W,o,r,l,d}\)\;

```

Try it online!

Expands to `(printf H); (printf e); (printf l); (printf l); (printf o); (printf \ ); (printf W); (printf o); (printf r); (printf l); (printf d);` before evaluation. The parentheses make Bash fork a subshell for each letter (and wait for it to exit), but this time `printf` is the Bash builtin.

---
Tags: code-golf
---