# Question
Title: Is this Game of Go configuration fully alive?
## Background

This challenge is about the Game of Go. Here are some rules and terminology relevant to this challenge:

* Game of Go is a two-player game, played over a square board of size 19x19.
* One of the players plays Black, and the other plays White. The game is turn-based, and each player makes a single move each turn, starting with Black. In the diagrams below, we use `O` for White and `X` for Black. Any other symbol is a blank.
* A *move* consists of placing a new stone of the player's own color on an empty spot on the board.
* Given a group of orthogonally connected stones of single color, the *liberty* is the number of empty positions orthogonally around it. For example, the following group has liberty of 7:

```
. . . .
. O O .
. O . .
. . . .

```

and the following configuration has two groups having liberties of 6 and 4 respectively:

```
. . . . .
. O O . .
. . . O .
. . . . .

```
* The opponent can reduce the liberty by placing their own stones around the target group. The following group of `O` has liberty 1 (the only empty adjacent position being `a`):

```
. X X .
X O O X
X O X .
. a . .

```
* If the Black places another black stone at `a`, the white group's liberty reduces to 0, where *capture* happens, and the white group is removed from the board.
* A player cannot make a move where their own stone(s) would be captured, unless it is itself a capturing move. For example, the Black cannot make a move at `a` or `b` (where one or two black stones would be captured immediately), but they *can* make a move at `c` because it captures two White stones on its right.

```
. . . . . O . . . O X .
. O . . O X O . O X O X
O a O . O b O . O c O X
. O . . . O . . . O X .

```

Finally, some terminology that is exclusive to this challenge:

* A *configuration* is one or more groups of stones of the same color.
* A configuration of White (color fixed for ease of explanation) is *fully alive* if Black cannot capture any of the given white stones even if arbitrarily many turns are given to Black.

## Challenge

Given a Game of Go configuration, test if it is fully alive.

The input is a rectangular 2D array representing the state of the board, where each cell is either occupied (`O` in the example below) or empty (`.`).

* You can choose any two distinct values to represent an occupied and an empty cell respectively.
* You can assume the input is always rectangular, and contains at least one stone.
* You can assume the input will always contain a margin of empty cells around the entire configuration of stones. For example, you don't need to handle this:

```
O O O .
O . O O
. O . O
. . O O

```

which will be given as the following instead:

```
. . . . . .
. O O O . .
. O . O O .
. . O . O .
. . . O O .
. . . . . .

```
* You may assume that the entire input (including the margin) will not exceed 19 rows and 19 columns.
* For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
    2. use two distinct values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code wins.

## Test cases

### Truthy (fully alive)

```
. . . . . . .
. . O O O O .
. O . O . O .
. O O O O . .
. . . . . . .

. . . . . .
. O O . . .
. O . O O .
. O O . O .
. . . O O .
. . . . . .

. . . . . .
. . O O . .
. O . O O .
. O O . O .
. . O O . .
. . . . . .

. . . . . .
. O O . . .
. O . O . .
. O O . O .
. . O O O .
. . . . . .

Truthy since both eyes must be filled in order to capture any of the two groups
. . . . . . .
. . O O O . .
. O . . O O .
. O O O . O .
. . . O O . .
. . . . . . .

Ditto
. . . . . . . .
. . O O O . . .
. O . . O O O .
. O O O . . O .
. . . O O O . .
. . . . . . . .

. . . . . . .
. . O O O . .
. . O . . O .
. O . O O O .
. O O . O . .
. . . O O . .
. . . . . . .

. . . . . . .
. . . O O O .
. . . O . O .
. O O . O O .
. O . O . . .
. O O O . . .
. . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . O . . O .
. O . . O . . O .
. O O O O O O . .
. . . . . . . . .

```

## Falsy (not fully alive)

```
. . .
. O .
. . .

. . . . .
. O O O .
. O . O .
. O O . .
. . . . .

. . . . . . . . .
. O O O . . O O .
. O . O . O . O .
. O O . . O O O .
. . . . . . . . .

. . . . . . .
. O O . O O .
. O . O . O .
. O O . O O .
. . . . . . .

The right group can be captured by Black, since Black doesn't need to fill
the upper area (of size 2) to capture it
. . . . . . .
. O O O . . .
. O . . O O .
. O O O . O .
. . . . O O .
. . . . . . .

The center singleton can be captured by Black
. . . . . . . . .
. . . O O O . . .
. O O O . O O O .
. O . . O . . O .
. O O O . O O O .
. . . O . O . . .
. . . O O O . . .
. . . . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . . O . O .
. O . . . O . O .
. O . . . O . O .
. O O O O O O . .
. . . . . . . . .

One part is fully alive but the other is not
. . . . . . . . . .
. O O O . . . O O .
. O . O O . O . O .
. . O . O . O O . .
. . O O . . . . . .
. . . . . . . . . .

```

# Answer
# JavaScript, 178 bytes

```
(a,w,Q=(a,v)=>q=o=>a[o]?a[o]-v?0:[o+w,o-w,o+1,o-1].map(q,a[o]++).some(x=>x):a[o]=v/2)=>!a.some((c,i)=>c&&(E=Q(b=[...a],2)(i),b.map((d,j)=>d==1&&!Q([...b],1)(j)&&--b[E++,j]),E<3))

```

```
f=

(a,w,Q=(a,v)=>q=o=>a[o]?a[o]-v?0:[o+w,o-w,o+1,o-1].map(q,a[o]++).some(x=>x):a[o]=v/2)=>!a.some((c,i)=>c&&(E=Q(b=[...a],2)(i),b.map((d,j)=>d==1&&!Q([...b],1)(j)&&--b[E++,j]),E<3))

testcases = `
. . . . . . .
. . O O O O .
. O . O . O .
. O O O O . .
. . . . . . .

. . . . . .
. O O . . .
. O . O O .
. O O . O .
. . . O O .
. . . . . .

. . . . . .
. . O O . .
. O . O O .
. O O . O .
. . O O . .
. . . . . .

. . . . . .
. O O . . .
. O . O . .
. O O . O .
. . O O O .
. . . . . .

Truthy since both eyes must be filled in order to capture any of the two groups
. . . . . . .
. . O O O . .
. O . . O O .
. O O O . O .
. . . O O . .
. . . . . . .

Ditto
. . . . . . . .
. . O O O . . .
. O . . O O O .
. O O O . . O .
. . . O O O . .
. . . . . . . .

. . . . . . .
. . O O O . .
. . O . . O .
. O . O O O .
. O O . O . .
. . . O O . .
. . . . . . .

. . . . . . .
. . . O O O .
. . . O . O .
. O O . O O .
. O . O . . .
. O O O . . .
. . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . O . . O .
. O . . O . . O .
. O O O O O O . .
. . . . . . . . .

. . .
. O .
. . .

. . . . .
. O O O .
. O . O .
. O O . .
. . . . .

. . . . . . . . .
. O O O . . O O .
. O . O . O . O .
. O O . . O O O .
. . . . . . . . .

. . . . . . .
. O O . O O .
. O . O . O .
. O O . O O .
. . . . . . .

The right group can be captured by Black, since Black doesn't need to fill
the upper area (of size 2) to capture it
. . . . . . .
. O O O . . .
. O . . O O .
. O O O . O .
. . . . O O .
. . . . . . .

The center singleton can be captured by Black
. . . . . . . . .
. . . O O O . . .
. O O O . O O O .
. O . . O . . O .
. O O O . O O O .
. . . O . O . . .
. . . O O O . . .
. . . . . . . . .

. . . . . . . . .
. . O O O O O O .
. O . . . O . O .
. O . . . O . O .
. O . . . O . O .
. O O O O O O . .
. . . . . . . . .

One part is fully alive but the other is not
. . . . . . . . . .
. O O O . . . O O .
. O . O O . O . O .
. . O . O . O O . .
. . O O . . . . . .
. . . . . . . . . .

`.trim().split('\n').filter(x => !/[^\.O ]/.test(x)).join('\n').split('\n\n');
testcases.forEach(test => {
  grid = test.match(/[\.O]/g).map(v => v == 'O' ? 2 : 0);
  width = test.match(/(?<!\n.*)[\.O]/g).length;
  table = document.body.appendChild(document.createElement('table'));
  grid.forEach((v, i) => {
    if (i % width == 0) row = table.appendChild(document.createElement('tr'));
    ceil = row.appendChild(document.createElement('td'));
    ceil.textContent = v ? '◯' : '';
  });
  output = document.body.appendChild(document.createElement('output'));
  output.value = f(grid, width);
  document.body.appendChild(document.createElement('hr'));
});
// P=(a,n=[],o='')=>{for(i=0;i<w*w;i++){if(n[i])o+='+';else o+='.XO'[a[i]];if((i+1)%w==0){print(o);o=''}}}
```

```
table { font-family: monospace; table-layout: fixed; border-collapse: collapse; }
table, tr, td { padding: 0; border: 0; }
td { line-height: 22px;width: 22px; height: 22px; text-align: center;
background: linear-gradient(to bottom, transparent 0, transparent 10px, #80808080 10px, #80808080 11px, transparent 11px, transparent 100%), linear-gradient(to right, transparent 0, transparent 10px, #80808080 10px, #80808080 11px, transparent 11px, transparent 100%); }
```

Input two parameters. First one is the board. The board is an 1d array, 2 for white, 0 for empty. Second one is its width, an integer.

Details (with comments):

```
(a, // input board as 1d array; 2 = white; 0 = empty
 w, // input width of board
 Q= // test if some stones on board `a` is alive
 (a, // board to test
  v  // color of stone to test
 )=>q=o=> // stone to test (when invoke by outside, a[o]==v always hold)
 /*
    We modify the board in-place. So caller need to duplicate a board if it requires the original one.
    For input, we test if stones with color `v` connected to `a[o]` has at least 1 liberty.
    And we modify connected stones by +1; modify all liberty by +v/2
    Here, {0, v/2, v} should / would not be equal.
  */
   a[o]? // If current ceil is not a liberty
    a[o]-v?
     0: // If current stone is something already visited or with wrong color (opposite color)
        // It is not a liberty, we return 0
     // If current ceil is connected stone which never visited
     [o+w,o-w,o+1,o-1].map(q, // visit all its neighbors
       a[o]++ // modify current ceil to remeber we had visited it
     ).some(x=>x): // Is there any liberty?
    a[o]=v/2 // Current ceil is a liberty; mark it as visited, also return something truthy
)=>
  !a.some( // Try to find out any stones may be captured
   (c, // stone on board
    i // position of stone
   )=>c&& // current ceil is white stone (not empty)
   (E= // Initial E to true (1)
       // Input only contains white, and have an empty border
       // So every white stones on inputed board has liberty as we known
       // And Q(...)(...) would always return true
       // We use this value to initialize variable E
    Q(
      b=[...a], // b is a duplicate of board, also used later
      2 // White = 2
    )(i),
    b.map( // Try to find some black (black = 1 here) stones without liberty
      (d,j)=>
       d==1&& // Current ceil is black
       !Q([...b],1)(j)&& // Current ceil has no liberty
       --b[
       E++, // We found a real eye for white, count it
       j] // Pick current black stone up, as it should be placed as final move
    ),
    E<3 // If white stones has less than 2 real eyes
        // (E is initialized to 1, so E<3 means less than two E++ happened)
        // we would be able to capture these white stones
        // thus, we found some white stones not fully alived
  ))

```
> 15 votes

---
Tags: code-golf, decision-problem, graph-theory, go
---


title: Interpret loose ranges

text:
# Question
Title: Interpret loose ranges
## Interpret loose ranges

ListSharp is an interpreted programming language that has many features, one of those features is a 1 index based range creator that works like this:

You define a range as `(INT) TO (INT)` or just `(INT)` where both or the single int can go from min to max int32 value

Then you can use those ranges to extract elements of an array without fearing to overstep it's boundaries

---

**therefore:**

`1 TO 5` generates: `{1,2,3,4,5}`

`3` generates: `{3}`

Ranges can be added up using the `AND` operator

`1 TO 5 AND 3 TO 6` generates: `{1,2,3,4,5,3,4,5,6}`

remember this works with negative numbers as well

`3 TO -3` generates: `{3,2,1,0,-1,-2,-3}`

---

# The challenge is the following:

## Input

A character array and the previously defined range clause as a string

## Output

The elements at the 1 index based locations of the range (non existing/negative indexes translate to an empty character)

---

# How to win

As a challenge you are supposed to create the program with the shortest byte count to win

---

### It has been pointed out empty characters do not exist, therefore you should be ignoring them (I only showed them here to make it easier to understand yet it confused people)

## Test cases:

```
input array is:
{'H','e','l','l','o',' ','W','o','r','l','d'}

range clause:
"1 TO 3" => "Hel"
"5" => "o"
"-10 TO 10" => "Hello Worl"
"0 AND 2 AND 4" => "el"
"8 TO 3" => "oW oll"
"-300 AND 300" => ""
"1 TO 3 AND 3 TO 1" => "HelleH"
"-20 TO 0 AND 1 AND 4" => "Hl"

```

# Answer
> 5 votes
# Python 2 - 239 211 210 bytes

Thanks to @mbomb007 and @Cyoce for further golfing this solution!

```
def r(s):
 t=[]
 for x in s.split("AND"):
  if"T"in x:a=map(int,x.split("TO"));b=2*(a[0]<a[1])-1;t+=range(a[0],a[1]+b,b)
  else:t+=int(x),
 return t
lambda p,v:[(['']+p+['']*max(map(abs,r(v))))[x]for x in r(v)]

```

Straight-forward approach. Tried generators and a recursive version, but they couldn't beat the simple for each loop. I'm a golfing noob, so this can most likely be improved quite a bit. Also, the major flaw of this snippet is that the range as a list object is computed again each time an element is retrieved from the character array (see last line, list comprehension). This means `r(s)` is executed `len(r(s)) + 1` times.

### Ungolfed code:

```
def find_range(string):
    result = []

    # Split at each AND and look at each element separately
    for element in string.split("AND"):
        # Element is just a number, so add that number to the result list
        if "TO" not in string:
            result += [int(string)]

        # Generate a list with all the values in between the boundaries
        # (and the boundaries themselves, of course) and append it to the result list
        else:
            boundaries = map(int, string.split("TO"))
            ascending = boundaries[0] < boundaries[1]

            # range(start, stop, step) returns [start, ..., stop - 1], so extend the stop value accordingly
            # range(8, 3, 1) returns just [], so choose respective step (negative for a descending sequence)
            result += range(boundaries[0], boundaries[1] + (1 if ascending else -1), 1 if ascending else -1)

# Make the char array 1-indexed by appending an empty char in 0th position
# Add enough empty chars at the end so too large and negative values won't wrap around
interpret = lambda chars, range_expr: [(['']+chars+['']*max(map(abs, find_range(range_expr))))[x] for x in find_range(range_expr)]

```

### Test cases:

```
c = list("Hello World")
print interpret(c, "1 TO 3")
print interpret(c, "5")
print interpret(c, "-10 TO 10")
print interpret(c, "0 AND 2 AND 4")
print interpret(c, "8 TO 3")
print interpret(c, "-300 AND 300")

```

### Output:

```
['H', 'e', 'l']
['o']
['', '', '', '', '', '', '', '', '', '', '', 'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l']
['', 'e', 'l']
['o', 'W', ' ', 'o', 'l', 'l']
['', '']

```

# Answer
> 3 votes
# Scala, 165 bytes

```
(s:String,r:String)=>r split "AND"map(_ split "TO"map(_.trim.toInt))flatMap{case Array(a,b)=>if(a<b)a to b else a to(b,-1)
case x=>x}map(i=>s lift(i-1)getOrElse "")

```

Explanation:

```
(s:String,r:String)=> //define a function
r split "AND"         //split the range expression at every occurance of "AND"
map(                  //map each part...
  _ split "TO"          //split at to
  map(                  //for each of these splitted parts, map them to...
    _.trim.toInt          //trim all whitespace and parse as an int
  )
)                     //now we have an Array[Array[Int]]
flatMap{              //map each inner Array...
  case Array(a,b)=>if(a<b)a to b else a to(b,-1) //if it has two elements, create a Range
  case x=>x             //otherwise just return it
}                     //and flatten, so we get an Array[Int]
map(i=>               //for each int
  s lift(i-1)         //try to get the char with index i-1, since Scala is zero-based
  getOrElse ""        //otherwise return ""
)

```

# Answer
> 3 votes
# Groovy (~~99~~ 97 Bytes)

```
{n,v->Eval.me("[${n.replaceAll(" TO ","..").replaceAll(" AND ",",")}]").flatten().collect{v[it]}}

```

Try it here: https://groovyconsole.appspot.com/edit/5155820207603712

Explanation:

* `.replaceAll(" TO ","..")` \- Replace the to with a traditional range.
* `.replaceAll(" AND ", ",")` \- Replace all ands with a comma.
* `"[${...}]"` \- Surround it with the "list" notation in Groovy.
* `Eval.me(...)` \- Evaluate string as Groovy code.
* `.flatten()` \- Flatten the mixture of 2D array and 1D array into a 1D array.
* `.collect{v[it]}` \- Collect the indices from the array into a single structure.

Here's a ~~115~~ 113 byte solution removing nulls from the output: https://groovyconsole.appspot.com/edit/5185924841340928

Here's a 117 byte solution if you say it MUST be indexed at 1 instead of 0: https://groovyconsole.appspot.com/edit/5205468955803648

If you want me to swap out the original for the 113/117 byte one, let me know.

# Answer
> 2 votes
# C#, 342 bytes

```
a=>r=>{var s=r.Replace(" AND","").Replace(" TO ","|").Split();int b=a.Length,i=0,n,m,j,o;var c=new List<char>();for(;i<s.Length;){var d=s[i++].Split('|');if(d.Length<2)c.Add(b<(n=int.Parse(d[0]))||n<1?' ':a[n-1]);else{o=(m=int.Parse(d[0]))<(n=int.Parse(d[1]))?1:-1;for(j=m;o>0?j<=n:j>=n;j+=o)c.Add(b<j||j<1?' ':a[j-1]);}}return c.ToArray();};

```

Ungolfed method:

```
static char[] f(char[] a, string r)
{
    var s=r.Replace(" AND","").Replace(" TO ","|").Split();
    int b=a.Length,i=0,n,m,j,o;
    var c=new List<char>();
    for(;i<s.Length;)
    {
        var d=s[i++].Split('|');
        if(d.Length<2)
            c.Add(b<(n=int.Parse(d[0]))||n<1?' ':a[n-1]);
        else
        {
            o=(m=int.Parse(d[0]))<(n=int.Parse(d[1]))?1:-1;
            for(j=m;o>0?j<=n:j>=n;j+=o)
                c.Add(b<j||j<1?' ':a[j-1]);
        }
    }

    return c.ToArray();
}

```

Full program with test cases:

```
using System;
using System.Collections.Generic;

namespace InterpretLooseRanges
{
    class Program
    {
        static void PrintCharArray(char[] a)
        {
            for (int i=0; i<a.Length; i++)
                Console.Write(a[i]);
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            Func<char[],Func<string,char[]>>f= a=>r=>{var s=r.Replace(" AND","").Replace(" TO ","|").Split();int b=a.Length,i=0,n,m,j,o;var c=new List<char>();for(;i<s.Length;){var d=s[i++].Split('|');if(d.Length<2)c.Add(b<(n=int.Parse(d[0]))||n<1?' ':a[n-1]);else{o=(m=int.Parse(d[0]))<(n=int.Parse(d[1]))?1:-1;for(j=m;o>0?j<=n:j>=n;j+=o)c.Add(b<j||j<1?' ':a[j-1]);}}return c.ToArray();};

            char[] ar = {'H','e','l','l','o',' ','W','o','r','l','d'};

            PrintCharArray(f(ar)("1 TO 3"));
            PrintCharArray(f(ar)("5"));
            PrintCharArray(f(ar)("-10 TO 10"));
            PrintCharArray(f(ar)("0 AND 2 AND 4"));
            PrintCharArray(f(ar)("8 TO 3"));
            PrintCharArray(f(ar)("-300 AND 300"));
        }
    }
}

```

A naive solution, using a char list, which uses `' '` as an empty character and gets the job done. Hoping to improve soon.

# Answer
> 2 votes
# JavaScript (ES6), 141

Unnamed function with 2 parameters, the first being the character array (can be a string either), the second the string containing the range definition.

The return value is an array where each element can either be a single character or the js value `undefined`. When stringified, this result in a sequence of comma separated chars having undefined shown as the "empty" char - as the test cases in the first version of the question.
Using `.join` you can get a string result similar to the test case output in the current version of the question.

```
(l,r,u,z=[])=>(r+' E').replace(/\S+/g,x=>x>'T'?u=t:x>'A'?[...Array((t-(w=(u=u||t)-(d=+u<t?1:-1)-1)-1)*d)].map(_=>z.push(l[w+=d]),u=0):t=x)&&z

```

*Less golfed*

```
(
 l, r, // input paramaters, array/string and string
 u,    // local variable start at 'undefined'
 z=[]  // local variable, will contain the ouput
) =>
  (r+' E') // add an end marker
  .replace( /\S+/g, x=> // execute for each nonspace substring
    x > 'T' // check if 'TO'
    ? u = t // if 'TO' save first value in u (it's a string so even 0 is a truthy value)
    : x > 'A' // check if 'AND' or 'E'
      ? (
          u = u||t, // if u is falsy, it's a single value range t -> t
          d = +u < t ? 1 :-1, // direction of range up or down,comparison has to be numeric, so the leading +
          w = u - d - 1, // starting value (decrement by 1 as js array are 0 based)
          u = 0, // set u to falsy again for next round
          [...Array((t - w - 1) * d)] // build the array of required number of elements
          .map(_ => z.push(l[w+=d])) // iterate adding elements of l to z
        )
      : t = x // if not a keyword, save value in t
  ) && z // return output in z

```

**Test**

```
f=
(l,r,u,z=[])=>(r+' E').replace(/\S+/g,x=>x>'T'?u=t:x>'A'?[...Array((t-(w=(u=u||t)-(d=+u<t?1:-1)-1)-1)*d)].map(_=>z.push(l[w+=d]),u=0):t=x)&&z

function run(x)
{
  R.value=x;
  O.textContent=f(L.value,x)
}

run("10 TO 5 AND 5 TO 10")
```

```
<table>
<tr><td>Base string</td><td><input id=L value="Hello World"></td></tr>
<tr><td>Custom range</td><td><input id=R ><button onclick='run(R.value)'>-></button></td></tr>
<tr><td>Output</td><td><pre id=O></pre></td></tr>
<tr><td>Test case ranges</td><td>
<select id=T onchange='run(this.value)'>
<option/>
<option value="1 TO 3">1 TO 3 => {'H','e','l'}</option>
<option value="5">5 => {'o'}</option>
<option value="-10 TO 10">-10 TO 10 => {'','','','','','','','','','','','H','e','l','l','o',' ','W','o','r','l'}</option>
<option value="0 AND 2 AND 4">0 AND 2 AND 4 => {'','e','l'}
"8 TO 3" => {'o','W',' ','o','l','l'}</option>
<option value="-300 AND 300">-300 AND 300 => {'',''}</option>
<option value="1 TO 3 AND 3 TO 1">1 TO 3 AND 3 TO 1 => "HelleH"</option>
<option value="-20 TO 0 AND 1 AND 4">-20 TO 0 AND 1 AND 4 => "Hl"</option>
</select>
</td></tr>
</table>
```

# Answer
> 2 votes
# R, 142 bytes

Assuming I understood the challenge correctly, here I am assuming that `r` is the pre-defined range clause in string format, and that the input array ("Hello world", in the examples) is read from stdin.

```
r=eval(parse(t=paste("c(",gsub("AND",",",gsub("TO",":",r)),")")))
o=strsplit(readline(),e<-"")[[1]][r[r>0]]
o[is.na(o)]=e
c(rep(e,sum(r<1)),o)

```

Some test cases:

```
r="1 TO 3"
[1] "H" "e" "l"

r="5"
[1] "o"

r="-10 TO 10"
[1] ""  ""  ""  ""  ""  ""  ""  ""  ""  ""  ""  "H" "e" "l" "l" "o" " " "w" "o" "r" "l"

r="0 AND 2 AND 4"
[1] ""  "e" "l"

r="8 TO 3"
[1] "o" "w" " " "o" "l" "l"

r="-300 AND 300"
[1] "" ""

```

## Ungolfed/explained

### Line 1

```
r=eval(parse(t=paste("c(",gsub("AND",",",gsub("TO",":",r)),")")))

```

R has a nice infix operator `:` which generates sequences. `1:5` gives `[1, 2, 3, 4, 5]`, and `0:-2` gives `[0, -1, -2]`. So, we replace the `TO` in the loose range clause with `:`.

```
                                         gsub("TO",":",r)

```

Interpreting `AND` is just concatenation. We can use the function `c` for that, which handily is able to take an arbitrary number of arguments, comma-separated. So we replace `AND` with `,`

```
                          gsub("AND",",",      ...       )

```

and then wrap the whole thing in `c(`, `)`.

```
               paste("c(",              ...               ,")")

```

This yields a character string that could look like `c( 1 : 5 , 7 )`. We call `parse` to convert to type "expression" and then `eval` to evaluate the expression. The resulting sequence of numbers is then re-assigned to the variable `r`.

```
r=eval(parse(t=                     ...                        ))

```

### Line 2

```
o=strsplit(readline(),e<-"")[[1]][r[r>0]]

```

Now for the ugly part - dealing with strings in R, which gets messy quickly. First we define `e` to be an empty string (we will need this later).

```
                      e<-""

```

We read from stdin and convert the character string to an array of individual characters by splitting at the empty string. (E.g. we go from "Hi" to \["H", "i"\].) This returns a list of length 1, so we have to ask for the first element `[[1]]` to get an array that we can work with. Ugh, I warned you this was messy.

```
  strsplit(readline(), ... )[[1]]

```

R indexes beginning at 1, and has a nice feature with negative numbers. Suppose `x` is `['a', 'b', 'c']`. Calling `x[1]` unsurprisingly returns `'a'`. Calling `x[-1]` returns all of `x` *except* index `1`, i.e. `['b', 'c']`. This is a cool feature, but means that we have to be careful with our negative indices for this problem. So for now, we just return the elements of the input array with index `>0`, and assign the result to `o`.

```
o=               ...             [r[r>0]]

```

### Line 3

However, there's a problem! For indices that are greater than the length of the array, R just returns `NA` values. We need it to return empty strings. So we redefine the elements of `o` for which `is.na(o)` is `TRUE` to be the empty string.

```
o[is.na(o)]=e

```

### Line 4

```
c(rep(e,sum(r<1)),o)

```

Finally, how do we deal with the negative (and zero) indices? They all need to return the empty string, so we repeat the empty string N times, where N is the number of indices that are `<1`.

```
  rep(e,sum(r<1))

```

Finally, we concatenate the previously-defined `o` to this (potentially empty) list.

```
c(      ...      ,o)

```

# Answer
> 2 votes
# Python 2, ~~156~~ 155 bytes

My answer has some similar ideas as 1Darco1's answer, but by using a different approach from the start (string slicing rather than lists), it ended up quite a bit shorter. It would be four bytes shorter if 0-indexing was allowed.

```
s,r=input()
o=""
for x in r.split("AND"):
    i=map(int,x.split("TO"));d=2*(i[0]<i[-1])-1
    for _ in-1,0:i[_]-=11**9*(i[_]<0)
    o+=s[i[0]-1:i[-1]+d-1:d]
print o

```

**Try it online**

Fortunately, I can parse strings containing spaces into integers. Negative indexing in Python indexes from the end of the string, so I use `i[-1]` to either be the same as `i[0]` or the second value, if there is one. Then I have to adjust any negative range values to *more* negative, so they won't mess with the slicing. Multiplying negative values by `11**9` (`2357947691`) will account for ranges using integer min value. Then, simply slice the string, using reverse slice if the range is reversed.

### With zero-indexing (151 bytes):

```
s,r=input()
o=""
for x in r.split("AND"):
    i=map(int,x.split("TO"));d=2*(i[0]<i[-1])-1
    for _ in-1,0:i[_]-=11**9*(i[_]<0)
    o+=s[i[0]:i[-1]+d:d]
print o

```

# Answer
> 1 votes
# Jelly, ~~28 27 25~~ 19 bytes

-3 Thanks to caird coinheringaahing

```
ḟØẎṣ”Aṣ€”OVr/€FfJ}ị

```

A dyadic Link accepting the range clause on the left and the array on the right (both as lists of characters) that yields the resulting list of characters.

**TryItOnline**

How?

```
ḟØẎṣ”Aṣ€”OVr/€FfJ}ị - Link: range-clause, C; array, W
 ØẎ                 - upper-case consonants ['B','C','D','F',...,'Z']
ḟ                   - filter remove (from C) (i.e. TO->O, AND->A)
   ṣ”A              - split at 'A's
      ṣ€”O          - split each at 'O's      e.g. [["-1","2"],["7"]]
          V         - evaluate as Jelly code       [[-1,2],[7]]
            /€      - rescue each by:
           r        -   inclusive range            [[-1,0,1,2],[7]]
              F     - flatten                      [-1,0,1,2,7]
                J}  - range of length (of W)
               f    - filter keep (those of F that are in bounds of W)
                  ị - index into (W)

```

# Answer
> 1 votes
# Perl - 110 bytes

Calling the script in the command line with the string as the first argument, and the range as the second.

```
for(split AND,pop@ARGV){$_>0?print+(split//,"@ARGV")[$_-1]:0for(/(.+)TO(.+)/?($1>$2?reverse$2..$1:$1..$2):$_)}

```

De-obfuscated :

```
for $subrange (split 'AND', $ARGV[1]) {
    for $index ($subrange =~ /(.+)TO(.+)/
        ? ($1 > $2 ? reverse $2..$1 : $1..$2) # All indices of that range
        : $subrange) # Otherwise, an index only
    {
        if ($index > 0) {
            # Here, 'split' returns an array of all characters
            print((split //, $ARGV[0])[$index - 1]);
        }
    }
}

```

# Answer
> 1 votes
# Python 2, 146 bytes

```
lambda s,a:[a[i]for x in[map(int,c.split('TO'))for c in s.split('AND')]for i in range(x[0]-1,x[-1]-2*(x[-1]<x[0]),1-2*(x[-1]<x[0]))if 0<=i<len(a)]

```

All tests are at **ideone**

Splits the clause, `s`, on "AND", splits each of the resulting sub-clauses on "TO", converts the resulting strings to `int` using `map`. The results will each have either 1 or 2 items (1 if no "TO" was present in the sub-clause).
Constructs 0-based ranges for each of these using the step parameter of range as 1 or -1 by inspection of the values at indexes 0 and -1 (a list with one entry has that entry at both indexes).
Runs through these ranges and constructs a list of the output, if the indexes provided are in-range (`if 0<=i<len(a)`).

# Answer
> 1 votes
**Clojure ~~232~~ ~~230~~ 229 bytes**

Oh what a monster I have created... But actually this was 260 when I was about to submit it.

Edit: removed a space from `#(get r %_"")`, `(if_(< f t)` and `(take-nth 2_%)` (indicated as `_`).

```
(let[S clojure.string/split](fn[r s](apply str(map #(get r %"")(mapcat #(apply(fn([f][(dec f)])([f t](if(< f t)(range(dec f)t)(reverse(range(dec t)f)))))%)(map #(mapv read-string(take-nth 2%))(map #(S % #" ")(S s #" AND "))))))))

```

Less golfed:

```
(def f (let[S clojure.string/split]
         (fn[r s] (->> (map #(S % #" ") (S s #" AND "))
                       (map #(mapv read-string (take-nth 2 %)))
                       (mapcat #(apply(fn
                                        ([f][(dec f)])
                                        ([f t](if (< f t)
                                                (range (dec f) t)
                                                (reverse (range (dec t) f)))))  %))
                       (map #(get r % ""))
                       (apply str)))))

```

Uses `clojure.string/split` to split by " AND " and " ", `take-nth` drops "TO" between integers, function argument matching handles the case of 1 or 2 arguments and that is about it.

Calling convention: `(f "Hello World" "1 TO 3 AND 2 AND 8 TO 2")`

# Answer
> 0 votes
# Scala, 151 bytes

```
_.split(" AND ").flatMap{case s"$a TO $b"=>a.toInt-1 to(b.toInt-1,(b.toInt-a.toInt).sign);case x=>Seq(x.toInt-1)}flatMap _.map("".+).orElse{case _=>""}

```

Try it in Scastie!

---
Tags: code-golf, array, parsing
---


# Question
Title: Score Tarzan's Olympic Vine-Swinging Routine
Olympic vine-swingers perform their routines in standard trees. In particular, Standard Tree `n` has vertices for `0` up through `n-1` and edges linking each nonzero vertex `a` to the vertex `n % a` below it. So, for example, Standard Tree 5 looks like this:

```
3
|
2   4
 \ /
  1
  |
  0

```

because the remainder when 5 is divided by 3 is 2, the remainder when 5 is divided by 2 or by 4 is 1, and the remainder when 5 is divided by 1 is 0.

This year, Tarzan will be defending his gold with new routines, each of which begins at vertex `n - 1`, swings to vertex `n - 2`, continues to vertex `n - 3`, etc., until finally he dismounts to vertex `0`.

The score for a routine is the sum of the scores for each swing (including the dismount), and the score for a swing is the distance within the tree between its start and end points. Thus, Tarzan's routine on Standard Tree 5 has a score of 6:

* a swing from `4` to `3` scores three points (down, up, up),
* a swing from `3` to `2` scores one point (down),
* a swing from `2` to `1` scores one point (down), and
* a dismount from `1` to `0` scores one point (down).

Write a program or function that, given a positive integer `n`, computes the score of Tarzan's routine on Standard Tree `n`. Sample inputs and outputs:

```
 1 ->  0
 2 ->  1
 3 ->  2
 4 ->  6
 5 ->  6
 6 -> 12
 7 -> 12
 8 -> 18
 9 -> 22
10 -> 32
11 -> 24
12 -> 34
13 -> 34
14 -> 36
15 -> 44
16 -> 58
17 -> 50
18 -> 64
19 -> 60
20 -> 66
21 -> 78
22 -> 88
23 -> 68
24 -> 82

```

Rules and code scoring are as usual for .

# Answer
> 12 votes
# C, ~~98~~ 97 bytes

```
F(i){int c[i],t=i-2,n=0,p;for(;++n<i;)for(p=c[n]=n;p=i%p;c[p]=n)t+=c[p]<n-1;return i>2?t*2:i-1;}

```

This calculates the distance between each pair of points with the following formula:

* Add the distance from the root to node A
* Add the distance from the root to node B
* Subtract 2\* the length of the common root of A and B

This has the advantage that when applied to all pairs, it's the same as:

* Add 2\* the distance from the root to each node
* Subtract 2\* the length of the common root of each node pair
* Subtract the distance from the root to the first node
* Subtract the distance from the root to the last node

To make the logic simpler, we assume we're going from node 0 to node n-1, rather than n-1 to 0 as the question states. The distance from the root node to node 0 is obviously 0 (they're the same). And we can see that for (most) trees, the distance from the last node to the root is 2:

```
                    n+1 % n = 1  for all n > 1
and:                  n % 1 = 0  for all n >= 0
therefore:  n % (n % (n-1)) = 0  for all n > 2

```

This means we have some special cases (n\<2) but we can account for those easily enough.

Breakdown:

```
F(i){                               // Types default to int
    int c[i],                       // Buffer for storing paths
        t=i-2,                      // Running total score
        n=0,                        // Loop index
        p;                          // Inner loop variable
    for(;++n<i;)                    // Loop through all node pairs (n-1, n)
        for(p=c[n]=n;p=i%p;c[p]=n)  //  Recurse from current node (n) to root
            t+=c[p]<n-1;            //   Increase total unless this is a common
                                    //   node with the previous path
    return i>2?   :i-1;             // Account for special cases at 1 and 2
               t*2                  // For non-special cases, multiply total by 2
}

```

Thanks @feersum for 1 byte saved

---

### Bonus: Trees!

I wrote a quick-and-dirty program to see what these trees look like. Here's some of the results:

```
6:

5 4
| |
1 2 3
 \|/
  0

```

---

```
8:

  5
  |
7 3   6
|  \ /
1   2   4
'--\|/--'
    0

```

---

```
13:

   08
    |
11 05   10 09 07
 |   \ /    |  |
02   03    04 06 12
 '-----\  /---'--'
        01
         |
        00

```

---

19:

```
   12
    |
   07   14
     \ /
     05    15 11
       \  /    |
17      04    08 16 13 10
 |       '-\  /--'   |  |
02          03      06 09 18
 '---------\ |/-----'--'--'
            01
             |
            00

```

---

```
49:

                         31
                          |
           30            18   36
            |              \ /
           19   38 27      13    39 29    32
             \ /    |        \  /    |     |
   26        11    22 44      10    20 40 17   34
    |         '-\  /--'        '-\  /--'    \ /
47 23   46       05               09        15    45 43 41 37 33 25    35 28
 |   \ /          '--------------\ |/-------'-----'   |  |  |  |  |     |  |
02   03                           04                 06 08 12 16 24 48 14 21 42
 '----'--------------------------\ |/----------------'--'--'--'--'--'    \ |/
                                  01                                      07
                                   '-----------------\  /-----------------'
                                                      00

```

# Answer
> 7 votes
# Python 2, 85 bytes

```
def f(a,i=1):h=lambda n:n and{n}|h(a%n)or{0};return i<a and len(h(i)^h(i-1))+f(a,i+1)

```

# Answer
> 7 votes
# Perl, ~~65~~ ~~59~~ ~~55~~ 54 bytes

Includes +2 for `-ap`

Run with the tree size on STDIN:

```
for i in `seq 24`; do echo -n "$i: "; vines.pl <<< $i; echo; done

```

`vines.pl`:

```
#!/usr/bin/perl -ap
$_=map{${"-@F"%$_}|=$_=$$_|$"x$p++.1;/.\b/g}1-$_..-1

```

## Explanation

If you rewrite the tree

```
3
|
2   4
 \ /
  1
  |
  0

```

to one where each node contains the set of all its ancestors and itself:

```
 {3}
  |
{2,3}   {4}
   \    /
    \  /
  {1,2,3,4}
      |
 {0,1,2,3,4}

```

Then we can describe e.g. all the nodes the path from 4 to 3 as:

* All nodes that contain 3 but not 4 (going down from 3)
* All nodes that contain 4 but not 3 (going down from 4)
* The highest node that contains both 3 and 4 (the join)

The number of edges is one less than the number of nodes so we can use that to ignore the join point, so the number of edges on the path from 4 to 3 is 3 because:

* The number of nodes that contain 3 but not 4: 2 nodes
* The number of nodes that contain 4 but not 3: 1 node

Notice that this also works for a path that directly goes down to its target, e.g. for the path from 3 to 2 the number of edges is 1 because:

* The number of nodes that contain 2 but not 3: 0 nodes
* The number of nodes that contain 3 but not 2: 1 node

We can then sum over all these combinations.

If you instead look at just a node, e.g. node 2 with ancestor set `{2,3}`. This node is going to contribute once when processing the path `2 to 1` because it contains a 2 but not a 1. It will contribute nothing for the path `3 to 2` since it has both 2 and 3, but it will contribute once when processing the path `4 to 3` since it has 3 but no 4. In general a number in the ancestor set of a node will contribute one for each neighbour (one lower of higher) that is not in the set. Except for the maximum element (4 in this case) which only contributes for the low neighbour 3 since there is no path `5 to 4`. Simular 0 is one sided, but since 0 is always at the root of the tree and contains all numbers (it is the ultimate join and we don't count joins) there is never any contribution from 0 so it's easiest to just leave node 0 out altogether.

So we can also solve the problem by looking at the ancestor set for each node, count the contributions and sum over all nodes.

To easily process neighbours I'm going to represent the ancestor sets as a string of spaces and 1's where each 1 at position p represents that n-1-p is an ancestor. So e.g. in our case of `n=5` a 1 at position 0 indicates 4 is an ancestor. I will leave off trailing spaces. So the actual representation of the tree I will build is:

```
" 1"
  |
" 11"   "1"
   \    /
    \  /
   "1111"

```

Notice that I left out node 0 which would be represented by `"11111"` because I'm going to ignore node 0 (it never contributes).

Ancestors with no lower neighbour are now represented by the end of a sequence of 1's. Ancestors with no higher neighbour are now represented by the start of a sequence of 1's, but we should ignore any start of a sequence at the start of a string since this would represent the path `5 to 4` which doesn't exist. This combination is exactly matched by the regex `/.\b/`.

Building the ancestor strings is done by processing all nodes in the order `n-1 .. 1` and there set a 1 in the position for the node itself and doing an "or" into the descendant.

With all that the program is easy enough to understand:

```
-ap                                                  read STDIN into $_ and @F

   map{                                    }1-$_..-1 Process from n-1 to 1,
                                                     but use the negative
                                                     values so we can use a
                                                     perl sequence.
                                                     I will keep the current
                                                     ancestor for node $i in
                                                     global ${-$i} (another
                                                     reason to use negative
                                                     values since $1, $2 etc.
                                                     are read-only
                       $$_|$"x$p++.1                 "Or" the current node
                                                     position into its ancestor
                                                     accumulator
                    $_=                              Assign the ancestor string
                                                     to $_. This will overwrite
                                                     the current counter value
                                                     but that has no influence
                                                     on the following counter
                                                     values
       ${"-@F"%$_}|=                                 Merge the current node
                                                     ancestor string into the
                                                     successor
                                                     Notice that because this
                                                     is an |= the index
                                                     calculation was done
                                                     before the assignment
                                                     to $_ so $_ is still -i.
                                                     -n % -i = - (n % i), so
                                                     this is indeed the proper
                                                     index
                                     /.\b/g          As explained above this
                                                     gives the list of missing
                                                     higher and lower neighbours
                                                     but skips the start
$_=                                                  A map in scalar context
                                                     counts the number of
                                                     elements, so this assigns
                                                     the grand total to $_.
                                                     The -p implicitly prints

```

Notice that replacing `/.\b/` by `/\b/` solves the roundtrip version of this problem where tarzan also takes the path `0 to n-1`

Some examples of how the ancestor strings look (given in order `n-1 .. 1`):

```
n=23:
1
 1
  1
   1
    1
     1
      1
       1
        1
         1
          1
          11
         1  1
        1    1
       1      1
      11      11
     1          1
    11  1    1  11
   1              1
  1111  11  11  1111
 111111111  111111111
1111111111111111111111
edges=68

n=24:
1
 1
  1
   1
    1
     1
      1
       1
        1
         1
          1
           1
          1 1
         1   1
        1     1
       1       1
      1         1
     1  1     1  1
    1             1
   11    1   1    11
  1   1         1   1
 1        1 1        1
1                     1
edges=82

```

# Answer
> 4 votes
# APL (Dyalog Extended), 36 bytes

```
{+/0 0⍉1↓⌊.+⍨⍛⌊⍨⍣≡⍵∨∘.(∨/,∊⍵|⍨,)⍨⍳⍵}

```

```
{+/0 0⍉1↓⌊.+⍨⍛⌊⍨⍣≡⍵∨∘.(∨/,∊⍵|⍨,)⍨⍳⍵}
                      (v/,∊⍵|⍨,)       are either of the arguments equal to 5 mod another argument
                  ⍵∨∘.(∨/,∊⍵|⍨,)⍨⍳⍵    matrix of distances
         ⌊.+⍨⍛⌊⍨⍣≡                     find minimum distances between each points
 +/0 0⍉1↓                              drop the first row, diagonal, sum

```

Try it online!

# Answer
> 3 votes
# Mathematica, ~~113~~ ~~103~~ 102 bytes

```
(r=Range[a=#-1];Length@Flatten[FindShortestPath[Graph[Thread[r<->Mod[a+1,r]]],#,#2]&@@{#,#-1}&/@r]-a)&

```

-10 bytes thanks to @feersum; -1 byte thanks to @MartinEnder

The following is *far* quicker (but longer, unfortunately, at **158 bytes**):

```
(a=#;If[a<4,Part[-{1,1,1,-6},a],If[EvenQ@a,-2,1]]+a+4Total[Length@Complement[#,#2]&@@#&/@Partition[NestWhileList[Mod[a,#]&,#,#!=0&]&/@Range@Floor[a/2],2,1]])&

```

# Answer
> 2 votes
# J, 37 bytes

```
[:+/2(-.+&#-.~)/\|:@(]|~^:(<@>:@[)i.)

```

Usage:

```
   f=.[:+/2(-.+&#-.~)/\|:@(]|~^:(<@>:@[)i.)
   f 10
32
   f every 1+i.20
0 1 2 6 6 12 12 18 22 32 24 34 34 36 44 58 50 64 60 66

```

Try it online here.

# Answer
> 1 votes
## JavaScript (ES6), ~~118~~ 116 bytes

```
n=>[...Array(n)].map(g=(_,i)=>i?[...g(_,n%i),i]:[],r=0).reduce(g=(x,y,i)=>x.map(e=>r+=!y.includes(e))&&i?g(y,x):x)|r

```

Lack of a set difference function really hurts, but some creative recursion reduces the byte count a bit. Edit: Saved 2 bytes by removing an unnecessary parameter.

---
Tags: code-golf, math, number, number-theory
---


title: Impatiently wait for input

text:
# Question
Title: Impatiently wait for input
Your task today is to implement a time limit for getting input, a task I've found rather annoying to achieve in most languages.

You will create a program function which prompts the user for input. Immediatly after the user supplies input, print the message `input received` and end execution/return. However, if the user waits for more than 10 seconds to provide input, output the message `no input received` and end execution/return.

Input must be from `stdin` (the console) or equivalent, not function or program arguments, however output can be either to `stdout`, your function's return value, or any other accepted output method.

You may ask for any amount of input, it can be a single character, a line, a word, or whatever method is shortest in your language as long as it waits for at least one character.

You must output as soon as the input is received, not after the 10 seconds have passed.

After 10 seconds have passed, you *must* end, you cannot continue waiting for input after `no input received` has been printed.

You may assume that input is not passed in the time between 10 seconds elapsing and text being printed to the screen, as this is an extremely small window. You may also assume that your language's builtin equivalent of `sleep` is consistently, absolutely perfect.

This is , fewest bytes wins!

# Answer
> 26 votes
## bash, 38 bytes

```
read -t10||a=no;echo $a input received

```

This uses the `-t` (timeout) option to bash's `read`, which causes it to fail and return a nonzero exit code if no input is given in the specified number of seconds.

# Answer
> 12 votes
## Haskell, ~~97~~ 89 bytes

```
import System.Timeout
timeout(10^7)getChar>>=putStr.(++"input received").maybe"no "mempty

```

If `timeout` times out it returns `Nothing` and `Just Char` (`Char`, because we're using `getChar`) otherwise. This return value is converted to `"no "` or `""` by function `maybe "no " mempty`. Append `"input received"` and print.

Edit: @BMO suggested `maybe` and saved some bytes.

# Answer
> 11 votes
# POSIX C99, 71 63 bytes

```
main(){puts("no input received"+3*poll((int[]){0,1},1,10000));}

```

Ungolfed:

```
#include <unistd.h>
#include <poll.h>
#include <stdio.h>
int main()
{
  struct pollfd pfd;
  pfd.fd = STDIN_FILENO;
  pfd.events = POLLIN;
  puts("no input received"+3*poll(&pfd,1,10000));
}

```

Since `poll` will return 1 in case of success, we multiply the result by 3 and shift the string accordingly. Then, we use the fact that `struct pollfd` has the following layout:

```
     struct pollfd {
     int    fd;       /* file descriptor */
     short  events;   /* events to look for */
     short  revents;  /* events returned */
 };

```

and that `STDIN_FILENO` is `0`, `POLLIN` is `1` to replace `pfd` with `int pfd[] = {0,1}`, which we finally make a compound litteral (as allowed by C99).

# Answer
> 8 votes
# Applescript, 113

Applescript doesn't really do reading from STDIN. Hopefully a `display dialog` is acceptable here:

```
({"","no "}'s item((display dialog""default answer""giving up after 10)'s gave up as integer+1))&"input received"

```

# Answer
> 7 votes
# APL (Dyalog), ~~41~~ 40 bytes

```
'no input received'↓⍨{3*⍨⎕RTL←10::0⋄3⊣⍞}

```

This is an anonymous tacit function which needs a dummy argument to run.

`'no input received'` the full string

`↓⍨` drop as many characters from the front of that as the number returned by the

`{` anonymous explicit function ( denotes the argument)

`⎕RTL←10` set **R**esponse **T**ime **L**imit to ten seconds

`3*⍨` raise that number (ten) to the power of three (a thousand means "all")

`::` upon those exceptions (all),

`0` return 0

try:

get input

`3⊣` discard that and instead return 3

`}` end of function (note that the argument  was never mentioned)

# Answer
> 7 votes
# Perl, ~~74~~ 67 bytes

```
$m="input received";$SIG{ALRM}=sub{die"no $m\n"};alarm 10;<>;say$m

```

### Old Version

```
$m="input received";$SIG{ALRM}=sub{die "no $m\n"};alarm 10;<stdin>;say $m;

```

(Run via perl -M5.10.1 ...)

# Answer
> 6 votes
# Perl 6,  ~~72~~  66 bytes

```
my $s='input received';Promise.in(10).then:{say "no $s";exit};get;say $s

```

Try it with no input
Try it with input

```
my$s='input received';start {sleep 10;say "no $s";exit};get;say $s

```

Try it with no input
Try it with input

```
my $s = 'input received'; # base message

start {         # create a Promise with a code block
                # that is run in parallel
  sleep 10;     # delay for 10 seconds
  say "no $s";  # say ｢no input received｣
  exit          # exit from the process
}

get;            # get a line from the input
say $s          # say ｢input received｣

```

# Answer
> 5 votes
# C#, ~~180~~ ~~171~~ ~~148~~ 131 bytes

```
()=>{var t=new System.Threading.Thread(()=>{System.Console.ReadKey();});t.Start();return(t.Join(10000)?"":"no ")+"input recieved";}

```

*Saved 17 bytes thanks to @VisualMelon.*

Full/Formatted version:

```
class P
{
    static void Main()
    {
        System.Func<string> f = () =>
        {
            var t = new System.Threading.Thread(() =>
            {
                System.Console.ReadKey();
            });
            t.Start();

            return (t.Join(10000) ? "" : "no ") + "input recieved";
        };

        System.Console.WriteLine(f());
        System.Console.ReadLine();
    }
}

```

# Answer
> 5 votes
# TI-BASIC, ~~84~~ 77 bytes

-7 thanks to @kamoroso94

```
:startTmr→T         //Start Timer, 5 bytes
:Repeat checkTmr(T)=10 or abs(int(.1K)-8)≤1 and 1≥abs(3-10fPart(.1K  //Loop until the timer is 10 seconds or a number key is pressed, 32 bytes
:getKey→K           //get key code, 4 bytes
:End                //end loop, 2 bytes
:"NO INPUT RECEIVED //Push string "NO INPUT RECEIVED" to Ans, 18 bytes
:If K               //If input was received, 3 bytes
:Disp sub(Ans,3,15  //Diplay "INPUT RECEIVED", 9 bytes
:If not(K           //If no input, 3 bytes
:Ans                //Display "NO INPUT RECEIVED", 1 byte

```

Waits until a number is pressed.

I am trying to figure out how to golf the sequence `{72,73,74,82,83,84,92,93,94}`. It is taking up a lot of space.

# Answer
> 4 votes
# AHK, ~~67~~ 65 bytes

<sup>*2 bytes saved by Blauhirn*</sup>

```
InputBox,o,,,,,,,,,10
s:=ErrorLevel?"no ":
Send %s%input received

```

AHK has a built-in timeout for input boxes.
I tried to get clever and use `!o` instead of `ErrorLevel` but that fails if the user inputs a falsey value.
Almost half of the answer is just the command names and fixed text.

# Answer
> 4 votes
# NodeJS, ~~105~~ ~~103~~ 101 bytes

*-2 bytes thanks to @apsillers*
*-2 bytes by moving `console.log()` into `exit()`*

```
with(process)stdin.on('data',r=x=>exit(console.log((x?'':'no ')+'input received'))),setTimeout(r,1e4)

```

Run by saving to a file and running it with node or run it straight from the command line by doing `node -e "<code>"`

# Answer
> 4 votes
# Go, 149 bytes

```
package main
import(
."fmt"
."time"
."os"
)
func main(){
o:="input received"
go func(){Sleep(1e10)
Print("no "+o)
Exit(0)}()
i:=""
Scan(&i)
Print(o)}

```

# Answer
> 4 votes
# JavaScript (ES6) + HTML, ~~86~~ ~~84~~ ~~82~~ 79+11 = ~~97~~ ~~95~~ ~~93~~ 90 bytes

```
setTimeout(oninput=_=>i.remove(alert(`${i.value?"":"no "}input received`)),1e4)

```

```
<input id=i

```
* 2 bytes saved thanks to apsillers pointing out that I'm dumb!

---

## Try it

Requires a closing `>` on the `input` in order to work in a Snippet.

```
setTimeout(oninput=_=>i.remove(alert(`${i.value?"":"no "}input received`)),1e4)
```

```
<input id=i>
```

# Answer
> 4 votes
# Python 3, 158 bytes

```
import os,threading as t,time
def k(t=10):time.sleep(t);print("No input received"[(10-t)//3:]);os.kill(os.getpid(),t)
t.Thread(None,k).start()
if input():k(0)

```

# Answer
> 3 votes
## VB.Net - 174 bytes

```
Module M
Sub Main()
Dim t=New Threading.Thread(Sub()Console.Read()):t.Start():Console.WriteLine(If(t.Join(10000),"","no ") & "input received"):End
End Sub
End Module

```

COBOL version coming tomorrow ;-)

# Answer
> 3 votes
# Python3, ~~100~~ ~~89~~ ~~83~~ 71 bytes

```
import pty
print("no input received"[3*any(pty.select([0],[],[],10)):])

```

First try at golfing.

-4 for `any()`, -7 for slicing, thanks @user2357112!

-6, get `select()` from `pty` instead of `select`.

# Answer
> 3 votes
## PowerShell, 110 bytes

```
$s1=date;while(![console]::KeyAvailable-and($i=((date)-$s1).seconds-lt10)){}
"{0}input received"-f(,'no ')[$i]

```

# Answer
> 3 votes
# Scratch 2/3.x, 41 points (Explanation)

1: When GF clicked

1: ask \[\] and wait

1 + 14 chars: say \[input received\]

1: stop \[all v\] (note: since "all" was its default setting I counted the block as 1)

1 + 2 digits: wait (10) seconds

1 + 17 chars: say \[no input received\]

1: stop \[all v\]

# Answer
> 3 votes
# Scratch 3.0 (scratchblocks3 syntax), 129 bytes/40 points

Beats @Syntax Error's answer by 1 point, but loses to it by 8 bytes.

```
define
broadcast[w v
ask[]and wait
say[input received
stop[all v
when I receive[w v
wait(10)secs
say[no input received
stop[all v

```

Ungolfed:

```
define // custom blocks (functions) do not need names. functions are shorter than programs when counting bytes, because programs that run require "when gf clicked"
broadcast [w v]
ask [] and wait // contrary to what the name of this block would suggest, there is no "ask [] (without waiting)" block - this is why the broadcast is necessary to allow other blocks to run while this block is waiting
say [input received]
stop [all v]

when I receive [w v]
wait (10) secs // although the actual block reads 'seconds', 'secs' is valid in scratchblocks syntax
say [no input received]
stop[all v]

```

# Answer
> 2 votes
## Tcl, 99 bytes

```
after 10000 {set () no}
vwait [fileevent stdin r {gets stdin (x)}]
puts [lappend () input received]

```

# Answer
> 2 votes
# SmileBASIC 3, 74 bytes

"Accepts input" by waiting for any button press (that should count as input.)

```
M=MAINCNT@L
N=MAINCNT-M>599CLS?"NO "*N;"INPUT RECEIVED
ON N+BUTTON()GOTO@L

```

# Answer
> 1 votes
# \>\<\>, 43 + 6 = 49 bytes

```
a/!/i0(?\~"input recieved"r>o<
o "\?:-1/r"n

```

Try it online!

+5 for the `-t.08` flag, which sets the tick to 0.08 seconds, and +1 for the `a` flag, which counts whitespace and skipped instructions as ticks.

The program checks for input about once every second, and exits the loop if input is detected. If input is not received, it exits the loop from the bottom, appending `no` to the beginning of the string. The initial `/` is to ensure that the last check for input is exactly on the 10 second mark.

It then takes about 5-6 seconds to print the string itself.

# Answer
> 1 votes
# Java 1.4+, 284 bytes

```
import static java.lang.System.*;public class X{public static void main(String[]x){new Thread(){public void run(){try{Thread.sleep(10000L);}catch(Exception e){}out.print("no input recieved");exit(0);}}.start();new java.util.Scanner(System.in).nextLine();out.print("input recieved");}}

```

**Ungolfed:**

```
import static java.lang.System.*;

public class InputAndWait {
    public static void main(String[] x) {
        new Thread() {
            public void run() {
                try {
                    Thread.sleep(10000L);
                } catch (Exception e) {
                }
                out.print("no input recieved");
                exit(0);
            }
        }.start();
        new java.util.Scanner(System.in).nextLine();
        out.print("input recieved");
    }
}

```

---

Please don't suggest Version-specific Java improvements, this is a generic Java answer that works in all currently stable Java Environments (1.4 and above).

---

Very freaking wordy... The catch is required, can't throw it. System import shaves off like 5 bytes... Overloading is also wordy, so it ends up a wordy poorly-golfed-looking mess.

# Answer
> 1 votes
# Julia 0.6, 78 bytes

Longer than I expected. See comments for "no input recieved" TIO link.

```
s="input recieved"
Timer(x->(show("no "*s);exit()),10)
readline(STDIN)
show(s)

```

Try it online!

# Answer
> 0 votes
# SmileBASIC, ~~74~~ 73 bytes

```
M=MAINCNT
WHILE!I*M>MAINCNT-600I=INKEY$()>"
WEND?"no "*!I;"input received

```

Takes 1 character of input.

And a 39 byte solution which probably isn't valid (doesn't actually accept text input, just has an `OK` button that you can press)

```
?"no "*!DIALOG("",,,10);"input received

```

---
Tags: code-golf, interactive, concurrency
---


# Question
Title: Dennis, Doorknob, Martin Büttner, Chris Jester-Young - Pizzeria!
Programming Puzzles & Code Golf is about to get a new moderator, Dennis! This challenge is a tribute to him and our other active (or recently active) moderators: Doorknob, Martin Büttner, and Chris Jester-Young. The challenge title is meant to be read to the tune of the Pepto Bismol song.

Basically, we're going to treat them all to pizza at The Nineteenth Bite Pizzeria, but we need to make sure they share it fairly because some of the mods are known to be pizza addicts!

The pizzas sold by the pizzeria are all rectangular blocks of text. The width and length of a pizza may be any non-negative integers as long as their product is divisible by four. Each grid space in the block of text pizza represents a slice, so it's always possible to split the slices up into four equal groups.

The mods will collectively order a single pizza, providing its width and length parameters to their server in any reasonable format such as `[width],[length]`. Just before the pizza arrives at their table, you need to label each slice with the initial of the mod who gets to eat it to ensure they all share fairly. Everyone should get the same number of slices.

* `E` is for Dennis
* `D` is for Doorknob
* `M` is for Martin
* `C` is for Chris

The mods are a little persnickety, however, and require that their respective sets of slices be path-connected, that is, that all their slices can be reached from one another by moving up, down, left, and right, not crossing anyone else's slices (and not moving diagonal). The don't care *how* you do this as long as it is done.

Once you've accurately labeled each slice, deliver the pizza to the mods with an optional trailing newline.

Your labeler may be a program or a function and can print or return the labeled pizza. The shortest labeler in bites wins.

# Examples

**Example 1**

Order: `4,1`

Some Possible Labeled Pizzas:

```
EDMC
```

```
MEDC
```

```
CDEM
```

**Example 2**

Order: `4,4`

Some Possible Labeled Pizzas:

```
MMMM
CCCC
DDDD
EEEE
```

```
DEMC
DEMC
DEMC
DEMC
```

```
CCCC
DEEM
DEEM
DDMM
```

**Example 3**

Order: `8,3`

Some Possible Labeled Pizzas:

```
MMMMMMCC
DDDDCCCC
DDEEEEEE
```

```
DDDCMMMM
DCDCMEEE
DCCCMEEE
```

**Example 4**

Order: `20,5`

A Possible Labeled Pizza:

```
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
```

(The `D`'s here are not simply-connected but that's ok.)

# Answer
> 22 votes
# CJam, 20 bytes

```
q~1$*4/"CEDM"e*/:$N*

```

I think this should work :)

Try it online

**Explanation:**

This first makes a pizza labeled CC…EE…DD…MM… from left to right and top to bottom, then sorts each row in alphabetical order. The only disconnections can happen between the C-E border and E-D border, or E-D border and D-M border (if they fall on adjacent rows). But the sorting ensures that the E's go to the right side and the D's go to the left side, as C\<E\>D\<M, so the E's and the D's remain connected.

```
q~          read and evaluate the input
1$          copy the width
*4/         multiply with the height and divide by 4
"CEDM"e*    repeat each letter in "CEDM" that many times
/           split into rows of the given width
:$          sort each row
N*          join with newlines

```

# Answer
> 7 votes
# K, 61 bytes

```
{[a;b]{((+:;|:)@x!2)[r@x]}'!#r:(b;a)#,/{(_(a*b)%4)#x}'"EDMC"}

```

Examples:

```
ryan@DevPC-LX:~/golf$ rlwrap k2
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
Evaluation. Not for commercial use.
\ for help. \\ to exit.

  `0:{[a;b]{((+:;|:)@x!2)[r@x]}'!#r:(b;a)#,/{(_(a*b)%4)#x}'"EDMC"}[4;1]
EDMC
  `0:{[a;b]{((+:;|:)@x!2)[r@x]}'!#r:(b;a)#,/{(_(a*b)%4)#x}'"EDMC"}[4;4]
EEEE
DDDD
MMMM
CCCC
  `0:{[a;b]{((+:;|:)@x!2)[r@x]}'!#r:(b;a)#,/{(_(a*b)%4)#x}'"EDMC"}[8;3]
EEEEEEDD
MMMMDDDD
MMCCCCCC
  `0:{[a;b]{((+:;|:)@x!2)[r@x]}'!#r:(b;a)#,/{(_(a*b)%4)#x}'"EDMC"}[20;5]
EEEEEEEEEEEEEEEEEEEE
DDDDDDDDDDDDDDDEEEEE
DDDDDDDDDDMMMMMMMMMM
CCCCCMMMMMMMMMMMMMMM
CCCCCCCCCCCCCCCCCCCC

ryan@DevPC-LX:~/golf$

```

I would hate to be the person who has to slice these things...

# Answer
> 7 votes
# Pyth, ~~30~~ 25 bytes

```
jb.eu_GkbceQs*R/*FQ4"EDMC

```

Live demo and all test cases.

Cut off 5 bytes thanks to @Jakube!

Same algorithm as my K answer...but a *lot* shorter.

30-byte version:

```
jb.e?%k2_bbcjkm*/*FQ4d"EDMC"hQ

```

Live demo and all test cases for 50-byte version.

# Answer
> 7 votes
# Pyth, 20 bytes

```
VceQs*L/*FQ4"CEDM"SN

```

Uses @aditsu's sorting trick.

Demonstration.

I came up with a large number of alternative programs of the same length while trying to golf this:

```
VceQs*L/*FQ4"CEDM"SN
VceQsCm"CEDM"/*FQ4SN
VceQs*L*FQ"CEDM"%4SN
VceQ%4s*L*FQ"CEDM"SN
VcQs*L/*Qvz4"CEDM"SN    (Newline separated input)
jbSMceQs*L/*FQ4"CEDM
Vcs*L/*FQ4"CEDM"hQSN

```

# Answer
> 6 votes
# Stuck, ~~42~~ 33

It returns! And in awfully long form. :( -- I stole aditsu's sort idea to save 9 bytes :)

```
t;g*4/[4*"CEDM"z"];F*":j0GK'$:Nj

```

### Explanation:

```
t;g*4/                              # Take |-separated input,
                                    #   store the first value in var stack,
                                    #   multiply the two numbers and divide by 4.
      [4*"CEDM"z                    # Wrap that value in an array, make 3 copies
                                    #   to get a list of length 4, zip with "EDMC"
                "];F*":j0GK         # For each item, multiply letter by value to
                                    #   to get string, join the result, split into
                                    #   segments the size of the saved variable.
                            '$:Nj   # For each item, sort so the letters are in the correct
                                    #   order, join by newline, print.

```

### Example input:

```
20|5

```

### Example output:

```
CCCCCCCCCCCCCCCCCCCC
CCCCCEEEEEEEEEEEEEEE
DDDDDDDDDDEEEEEEEEEE
DDDDDDDDDDDDDDDMMMMM
MMMMMMMMMMMMMMMMMMMM

```

# Answer
> 4 votes
# Rev 1 C, 74

```
i;f(w,h){for(i=w*h;i--;i%w||puts(""))putchar(h-i/w*2==1^"CDEM"[i*4/w/h]);}

```

For a 1-byte saving, this version reverses (only) the middle row of slices for any odd number of rows.

# Rev 0 C,75

```
i;f(w,h){for(i=w*h;i--;i%w||puts(""))putchar(h==3&i/w==1^"CDEM"[i*4/w/h]);}

```

Many answers here zigzag, but in most cases, just outputting the letters in order (left to right, top to bottom) works fine:

No need to zigzag for heights 1,2 or 4

No need to zigzag for heights greater than 4 (each mod's pizza ration will wrap around.)

Therefore we only actually need to zigzag when the height is 3, and then we only need to reverse the middle row.

As it turns out, Dennis and Doorknob are the only mods on that row. And they can be interchanged by XORing their ASCII codes with 1.

This is handy given that there's no easy way to reverse a string in C.

Ungolfed in test program

```
i;
f(w,h){
  for(i=w*h;i--;i%w||puts(""))            //loop through all squares. puts inserts a newline at the END of each line.
  putchar(h==3&i/w==1^"CDEM"[i*4/w/h]);   //put the letter, XORing D and E for the middle row of height 3.
}

W,H;
main(){
  scanf("%d%d",&W,&H);
  f(W,H);
}

```

# Answer
> 1 votes
# JavaScript (ES6) 107

Zigzag solution. Using template string, the newline is significant and counted.

Test running the snippet with FireFox.

```
f=(w,h)=>{for(i=o=r='',z=l=1;--l?l:c='CDEM'[l=w*h/4,i++];r[w-1]&&(o+=r+`
`,r='',z=!z))r=z?r+c:c+r;return o}

//TEST

(test=_=>([w,h]=I.value.match(/\d+/g),O.innerHTML=f(w,h)))()
```

```
<input id=I value='8 3'><button onclick='test()'>-></button>
<pre id=O></pre>
```

# Answer
> 1 votes
## Retina, 83 bytes

The features used in this answer are newer than this challenge (not that it matters...). Byte count assumes ISO 8859-1 encoding.

```
\d+
$*#
#(?=.*¶(.+))
$1
\G####
CDEM
S_`((.)+?(?=.*¶(?<-2>#)+$))|\D
O`.
T`DE`ED
O%`.

```

Try it online!

This implements aditsu's solution which is now somewhat feasible thanks to the new sort stages.

# Answer
> 0 votes
# Jelly, 14 bytes

```
×:4“CEDM”xsṢ€Y

```

Try it online!

Implements aditsu's algorithm

## How it works

```
×:4“CEDM”xsṢ€Y - Main link. Takes h on the left and w on the right
×              - Yield h×w
 :4            - Integer divide by 4; Yield R = (h×w):4
   “CEDM”      - Yield "CEDM"
         x     - Repeat each character R times
          s    - Split into rows of length w
           Ṣ€  - Sort each row
             Y - Join by newlines

```

---
Tags: code-golf, geometry, grid, set-partitions
---


title: List all multiplicative partitions of n

text:
# Question
Title: List all multiplicative partitions of n
Given a positive number *n*, output all distinct multiplicative partitions of *n* in any convenient format.

A multiplicative partition of *n* is a set of integers, all greater than one, such that their product is *n*. For example, 20 has the following distinct multiplicative partitions:

```
2 * 2 * 5
2 * 10
4 * 5
20

```

Order does not matter, so `2 * 2 * 5` is the same partition as `2 * 5 * 2`.

---

Examples:

```
1 -> {}
2 -> {2}
4 -> {2, 2}, {4}
20 -> {2, 2, 5}, {2, 10}, {4, 5}, {20}
84 -> {2, 2, 3, 7}, {2, 2, 21}, {2, 14, 3}, {2, 6, 7}, {2, 42}, {4, 3, 7}, {28, 3}, {4, 21}, {6, 14}, {12, 7}, {84}

```

# Answer
# Brachylog, 16 bytes

```
>~l:{1<}a.*?,.=o

```

This is a *function* (not a full program) which takes a positive number as input and generates all multiplicative partitions of it. (I also avoided using any prime factorization builtins in this solution, mostly because I wasn't sure they'd help; I might try a more builtin-heavy solution too at some point.)

Try it online! (Extra code has been added around the function here to make it into a full program; if you provide the function shown above to TIO directly, it will run the function but not print its output anywhere, which is kind-of useless as a demonstration.)

This program really disappoints me, because much of it is working around bugs in the Brachylog interpreter and deficiencies in its specification, rather than actually solving the problem; but the interpreter is what it is. (Even with the program like this, the interpreter uses much more memory than it logically should, and crashes due to memory exhaustion, but luckily on small problems it manages to produce the desired output first.) In a hypothetical "perfect version of Brachylog" you could just write `~*.o.:{>1}a,`, which would be 4 bytes shorter, but I needed to add extra constraints to help the interpreter out a bit. (I don't really like Brachylog much, and would rather stick to Prolog, but it needed similar hints to make the program work and they're much longer to write. So Brachylog it is.)

Explanation:

As usual, a Brachylog program is a set of constraints; by default, the first constraint constrains the input against an unknown (which I'll call *A*), the second constraint constrains *A* against a second unknown *B*, and so on until we reach the output. Some characters, such as `{}`, can change this general flow, so I use a different set of letters (e.g. *X*/*Y*) to represent unknowns in nested predicates.

```
>       A is smaller than the input
~l      B has length A
  1<    X is 1, Y is larger
:{1<}a  For each element X of B, it corresponds to an element Y of C
.       C, the output, and D are all identical
*       E is the product of D's elements
?       E, the input, and F are all identical
,       There's no constraint between F and G
.       G, the output, and H are all identical
=       H and I are identical, and need to be evaluated early
o       The output can be produced by sorting I

```

It's still unclear how the program works, so let's try simplifying the constraints a bit. *C*, *D*, *G*, *H*, and *I* are all the same (and equal to the output). *E* and *F* are also the same (and equal to the input). So our constraints boil down to this:

* *A* is the length of *B* and of the output, and is smaller than the input.
* *B* consists of all 1s, and isn't particularly useful (it's part of the program simply because in the existing Brachylog interpreter, `:{1<}a` needs its left argument to have a constrained length, or else the interpreter goes into an infinite loop).
* The output consists entirely of numbers greater than 1 (i.e. greater than the corresponding element of *B*).
* The product of the elements of the output is equal to the input.
* The output is unchanged by sorting it (i.e. is in sorted order).

Incidentally, I didn't *explicitly* specify that all the elements of the output are integers, something which might seem to be required; however, Brachylog's constraint solver can't handle non-integers, so it'll conveniently produce only the solutions that involve integers.

Clearly, "the length of the output is smaller than the input" is going to be true whenever the output is a multiplicative partition of the input (because 2*x* \> *x* for all nonnegative *x*, i.e. positive 2*x*). So we can disregard that constraint; it's only there to give the Brachylog interpreter a working strategy for evaluating the program. The other constraints (that the output is sorted, that its product is the input, and that its elements are all greater than 1) are the definition of a multiplicative partition, and therefore this function is basically just a direct implementation of the question.
> 7 votes

# Answer
# Brachylog 1, 14 bytes

```
:{$pp~c:*ao}fd

```

Try it online!

# Brachylog 2, ~~11~~ 10 bytes, language postdates challenge

```
{ḋp~c×ᵐo}ᵘ

```

Try it online!

Maltysen answered this question in 17 bytes of Pyth, so I came up with a 16-byte Brachylog solution that worked by translating the specification of the question to Brachylog. While I was doing that, Dennis wrote a 15-byte Jelly solution. So I had to go down to 14 bytes. This is a *function* that takes the input as an argument, and returns a *list* of all partitions (rather than a generator, as with my other solution).

Some time after I wrote this answer, Dennis and I managed to cooperatively get the Jelly solution down to 11 bytes. It turns out there's a new version of Brachylog out, with a terser syntax; it postdates the challenge, so doesn't actually count, but it could manage the 11-byte total too pretty much as soon as it released; later revisions of the language (inspired by other challenges) can go as low as 10, as seen here. The two programs are identical, with the only difference being the syntax.

Unlike my other solution, which didn't make much use of "golfing primitives" but rather stated the problem directly, this one ignores pretty much all the power of Brachylog constraints and does its best Jelly impression instead, writing a chain of constraints for which the left argument is already known (and thus the constraints simply act like Jelly monads rather than full-blown constraints). It therefore uses the same algorithm as @Maltysen's Pyth solution, which is probably the easiest way to solve this using typical golfing primitives. (Interestingly, the "just state the problem" solution in my other answer would be shorter if not for bugs/deficiencies in the Brachylog interpreter, despite its lack of use of golfing primitives. Some day I need to write an "improved Brachylog" in order to get a good solution for this kind of problem; as golfing languages go, Brachylog is actually really verbose.)

The program consists of a generator, and a wrapper around it. First, here's an explanation of the generator:

```
$pp~c:*ao  ḋp~c×ᵐo
$p         ḋ        Prime factor decomposition of the input
  p         p       Generate all permutations
   ~c        ~c     Generate all inverse concatenations (i.e. partitions)
     :*a       ×ᵐ   Take the product of each list element in each partition
        o        o  Sort each partition

```

This almost solves the problem, but we end up generating many of the partitions many times each. So we need a wrapper to deduplicate the solutions:

```
:{…}fd
:{…}f     Convert generator to list
     d    Remove duplicate elements

{…}ᵘ      Convert generator to list of unique elements

```
> 6 votes

# Answer
## Mathematica, 61 bytes

```
±1={{}}
±n_:=Union@@(Sort/@Append[n/#]/@±#&/@Most@Divisors@n)

```

Defines a (recursive) unary operator `±` which returns the list of partitions.
> 5 votes

# Answer
# Pyth - 17 bytes

Takes all permutations of the prime factorization, then partitions each one and then products all the partitions, then only retains distinct partitions.

```
{mS-*Md1s./M.p+1P

```

Test Suite.
> 4 votes

# Answer
## Python 2, 70 bytes

```
f=lambda n,k=2,l=[]:n/k and(n%k<1)*f(n/k,k,l+[k])+f(n,k+1,l)or 1/n*[l]

```

Outputs a list of sorted lists. For example `f(20)` is `[[2, 2, 5], [2, 10], [4, 5], [20]]`.
> 4 votes

# Answer
# Jelly, ~~14~~ ~~13~~ 11 bytes

```
Ḋx³ŒPQP=¥Ðf

```

Try it online!

I was fairly sure @Dennis's Jelly solution could be improved. Unfortunately, I didn't manage to beat the Brachylog record, but I did manage to tie it. **Update**: With @Dennis' help, it's improved now; I guess Jelly takes back the crown.

This program is incredibly inefficient, having O(2*n*2) performance (which is why the test case above shows it for input 4). It completes quickly on 4, very slowly on 5, and may not be practically possible to run for larger numbers.

Interestingly, the Brachylog was improved by going from a solution that described the problem (which Brachylog is good at) to a solution that used an algorithm based on factorising the input (which Jelly is good at); meanwhile, the Jelly solution was improved by moving away from *its* strengths, and going back to a solution that just describes the problem.

Explanation:

```
Ḋx³ŒPQP=¥Ðf
Ḋ              List of integers from 2 to the input (apparently undocumented)
 x³            Make a number of copies of each that's equal to the input
   ŒP          Take all (possibly noncontiguous) subsequences of that list (!)
     Q         Remove duplicates
         Ðf    Filter, keeping elements where:
      P=         their product is equal to {the original input, by default}
        ¥      Parse preceding two links as a unit

```

Because the output of `Ḋx` is sorted, each subsequence must also be sorted, and thus we don't have to sort them individually. So the "the same output in different orders is a duplicate" part of the problem, and the "all values in the output are \> 1" part of the problem, get solved by the generation. Apart from that, what we're basically doing here is "find all lists for which `P=³`", which we do (in an incredibly inefficient way) by generating all the lists in question and then filtering out the incorrect ones.

(Clearly, someone needs to go invent a hybrid of Jelly and Brachylog, plus a *really good* constraint solver, so that we could write something along the lines of `{P=³}~` plus some deduplication code, and solve the program in a much shorter length. That might be some distance away, though.)
> 3 votes

# Answer
# JavaScript (ES6), ~~74~~ 67 bytes

```
f=(n,m=2,a=[])=>n>1?m>n?[]:f(n,m+1,a).concat(f(n/m,m,[...a,m])):[a]

for (var i = 1; i < 31; i++) console.log(JSON.stringify(f(i)));
```

Directly solves the problem recursively: for each integer **m** from **2** to **n**, we take each of the partitions of **n / m** with a minimum element of **m** (to avoid duplicate partitions) and append **m**. (For any **m** that does not divide **n**, this gives the empty array, as no arrangement of integers multiplies to a decimal.) We define a base case of the empty array for **1** so as to avoid infinite recursion.
> 2 votes

# Answer
# Jelly, 9 bytes

```
ḊœċRẎP=¥Ƈ

```

Try it online!

This is fairly slow, timing out for \\$n \ge 13\\$ on TIO

## How it works

```
ḊœċRẎP=¥Ƈ - Main link. Takes n on the left
Ḋ         - Dequeue; Yield [2, 3, ..., n]
   R      - Range; Yield [1, 2, 3, ..., n]
 œċ       - For each 1 ≤ k ≤ n, yield the combinations with replacement
             of length k, choosing from [2, 3, 4, ..., n]
    Ẏ     - Tighten these into a single list of lists
       ¥Ƈ - Keep those lists for which the following is true:
     P    -   The product...
      =   -   ...equals n

```
> 2 votes

# Answer
# Python2, ~~198~~ ~~191~~ ~~172~~ 180 bytes

```
from itertools import*
n=input()
for i in range(2,len(bin(n))):
 for P in combinations_with_replacement(range(2,n),i):
  if reduce(lambda a,b:a*b,P)==n:print(P)
print[(n,),()][n<2]

```

A full program. This could be improved a lot, so suggestions are deeply welcome!

Outputs from the range 1 to 31 (inclusive):

```
(1,)
(2,)
(3,)
(2, 2), (4,)
(5,)
(2, 3), (6,)
(7,)
(2, 4), (2, 2, 2), (8,)
(3, 3), (9,)
(2, 5), (10,)
(11,)
(2, 6), (3, 4), (2, 2, 3), (12,)
(13,)
(2, 7), (14,)
(3, 5), (15,)
(2, 8), (4, 4), (2, 2, 4), (2, 2, 2, 2), (16,)
(17,)
(2, 9), (3, 6), (2, 3, 3), (18,)
(19,)
(2, 10), (4, 5), (2, 2, 5), (20,)
(3, 7), (21,)
(2, 11), (22,)
(23,)
(2, 12), (3, 8), (4, 6), (2, 2, 6), (2, 3, 4), (2, 2, 2, 3), (24,)
(5, 5), (25,)
(2, 13), (26,)
(3, 9), (3, 3, 3), (27,)
(2, 14), (4, 7), (2, 2, 7), (28,)
(29,)
(2, 15), (3, 10), (5, 6), (2, 3, 5), (30,)
(31,)

```
> 1 votes

# Answer
# Jelly, 15 bytes

```
ÆfŒ!ŒṖ€;/P€€Ṣ€Q

```

Try it online!
> 1 votes

# Answer
## Clojure, 91 bytes

```
(defn f[n](conj(set(for[i(range 2 n):when(=(mod n i)0)j(f(/ n i))](sort(flatten[i j]))))n))

```

Example runs:

```
(map f [20 84])
(#{20 (2 2 5) (4 5) (2 10)} #{(7 12) (2 2 3 7) (2 3 14) (2 2 21) (2 6 7) (6 14) (3 4 7) (3 28) (4 21) (2 42) 84})

```

The value itself is returned as a single number (not a `list`), others come out as lists. The `n` at the end could be replaced by `[n]` to make it a sequence as well, or `(list n)` to make it a list.
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~58~~ ~~56~~ ~~52~~ 47 bytes

```
#0[#/i,##2,i]~Do~{i,2,#>1||Print@{##2};Min@##}&

```

Try it online!

Prints the partitions.
> 1 votes

# Answer
# J, 35 bytes

```
([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:

```

Based on the solution to a time-constrained factorization challenge.

This version is much more inefficient and runs in factorial time based on the number of prime factors. Creates partitions by generating factoradic numbers.

Try it online! (Don't try large values online!)

## Explanation

```
([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:  Input: integer n
                                 q:  Prime factorization
(                              )@    Operate on them
                              #        Length
                            !@         Factorial
                         i.@           Range [0, i)
                     #\                Range [1, i]
                       #:              Mixed based conversion - Creates factoradic values
     ]                                 Get factors
            (    )"$~                  For each factoradic value
               /.                        Partition the factors based on equal
                                         digits in the factoradic value
             */                          Get the product of each block
        /:~@                             Sort it
      <@                                 Box it
 [:~.                                  Deduplicate

```
> 0 votes

# Answer
# D, 95 bytes

```
void g(int n,int[]r){for(int i=r[0];i*i<=n;i++)(n%i)?0:g(n/i,i~r);r.back=n;r.writeln;}g(n,[2]);

```

Just a recursive solution. In `g(n,r)`, `r` is the partition so far, and `n` is the value still left to break into factors. To get each unordered partition only once, we sort the factors in `r` in non-increasing order. The last element of `r` starts at `2` as the least possible factor, and gets overwritten by `n` in each copy just before each output operation.

For `n = 60`, the output is as follows:

```
[3, 2, 2, 5]
[2, 2, 15]
[3, 2, 10]
[5, 2, 6]
[2, 30]
[4, 3, 5]
[3, 20]
[4, 15]
[5, 12]
[6, 10]
[60]

```

Try it online!
> 0 votes

# Answer
# D, 109 bytes

```
import std.stdio;void g(T)(T n,T[]r=[2]){if(n-1){for(T i=r[0];i*i<=n;i++)n%i?0:g(n/i,i~r);r[$-1]=n;r.write;}}

```

Try it online!
> 0 votes

---
Tags: code-golf, number-theory, combinatorics, set-partitions
---