title: Help me untangle these wires!

text:
# Question
Title: Help me untangle these wires!
# My wires are all tangled!

Isn't it annoying when wires get all tangled up? Well, that just happened to me, so I'd like to to help me untangle them! For your convenience, I've disconnected them all from the device, but they're all still connected to the outlet. Your challenge is to figure out how to untangle them!

# Input

The input will consist of spaces, pipes, and Xs (both cases). The input will look something like this:

```
| | | |
 X  | |
| |  x
|  X  |
| | | |

```

A capital X means that the left wire crosses over the right wire, and a lowercase x means the opposite. The first and last lines will always be `| | | |...`. You may take the input as a comma separated string, an array of strings, etc. The format is not strict, as long as it makes sense and doesn't contain any extra information.

# Output

For this challenge, not only do I need to know how long I will take, I need to know exactly what to do. So, output a list of integer pairs with the character R or L, case insensitive, representing which two wires to untangle and which way (R means right over left, and vice versa for L). You need to tell me which way to uncross them; I can't figure that out myself. Output is pretty flexible too, as long as you output all of the integer pairs + character in the correct order and you don't output any extra nonsense text (brackets, commas, etc. are fine). The wires can be zero or one indexed, but the index must start from the left. Note that you must untangle from the bottom, not the top. Output style must be consistent, and please specify how you are outputting if it is not obvious. The case of the character doesn't have be consistent, if that helps at all.

# Sample Output

For the example input above, the output would be something like:

```
2 3 R
3 4 L
1 2 R

```

The output format here is a newline separated list of space separated values. This is 1-indexed.

# Further specifications

It is valid to have X and x stacked vertically over each other in either order. Since I'm lazy, I don't want to switch wires around unnecessarily, so don't output anything for these cases; if I find that, I'll just pull the wires gently to get them straight.

It is also valid to have multiple X and x stacked vertically, and as long as neither wire is involved in other crossings, I don't want any extra moves (because I'm lazy). Thus, if the characters `X X x X x x` show up in a column without any other crossings, the output should still be blank!

In case this isn't clear, R eliminates X and L eliminates x.

There could be two wire crossings in the same row, in which case the order of these two swaps does not matter. You will never get something like `| X X |` (this does not make sense because it implies that the middle wire is being crossed over the wires on both its left and its right).

There aren't always crossings...

The input could be a single pipe. However, the input will never be blank.

Shortest valid solution wins on December 20th!

# More Examples

As I promised:

### Example 1

**Input**

```
| | | | | |
| |  X   x
 X  |  x  |
|  x  |  X
 X   X  | |
| | | | | |

```

**Output**

```
1 2 R
3 4 R
2 3 L
5 6 R
1 2 R
4 5 L
3 4 R
5 6 L

```

### Example 2

**Input**

```
| | |
 X  |
|  x
| | |
|  X
|  x
| | |

```

**Output**

```
2 3 L
1 2 R

```

### Example 3

**Input**

```
|

```

**Output** is blank. Yes, you have to deal with this case.

### Example 4

**Input**

```
| |
 X
 x
 X
 x
 X
 x
 X
 x
 X
 x
| |

```

**Output** is blank. Just for fun :).

### Example 5

**Input**

```
| |
 X
 X
 x
 X
 x
 x
| |

```

**Output** is still blank...

# Answer
# Befunge, 173 bytes

Input is read from stdin in the exact format given in the challenge description, although it's crucial that every line be the correct length and the final line must include a newline (i.e. not just EOF at the end of that line).

```
$1>>05p~$~:55+-#v_
$_^#`"N":+1g50$<>:2+3%1-05g6g+0v>!#:v#
vg50-1*2p51:-1_^#:<*2!!-*84p6g5<
 +#,.#$"R"\#\-#+5<^g51$_:0`6*\25g\v@_:#!.#:1#,
>+::25p6g\48*\6p48 *-:!^!:--1*2`0:<

```

Try it online!

The basic idea for this solution is that we have an "array" keeping track of the twist counts for each wire. So every time we encounter a twist in one direction we increment the count for the associated wire, while a twist in the other direction will decrement the count.

At the same time as we process the twist for a particular wire, we also look at the twist count for the wires to the left and right of it. If either of them are non-zero, we need to "flush" those twists onto the stack, since it will no longer be possible for them to be unravelled by later twists in the opposite direction.

After the last line of input, the input stream returns EOF repeatedly, and these EOF characters are interpreted as twists in every wire, at least for the purposes of flushing. This forces the program to flush any outstanding counts in the array, but it will not generate any new twist counts.

Once we've finished processing the input, all the commands for untangling the wires will now be on the stack. This means we can simply pop them off in reverse order to output the instructions needed to untangle the wires from the bottom up.
> 1 votes

# Answer
# Pyth - ~~26~~ 25 bytes

Very straightforward, maybe I can golf the filtering.

```
fhhT_m+hB/xrdZ\x2@"RL"}\x

```

Try it online here.
> 5 votes

# Answer
## JavaScript (ES6), 178 bytes

```
f=([t,...a],r=[])=>a[0]?t.replace(/x/gi,(c,i)=>(c=c<'x'?'R':'L',i=++i/2,r.reduce((f,[j,,d],n)=>f||i<j+2&&j<i+2&&(j-i|c==d||r.splice(n,1)&&2),0)<2?r=[[i,i+1,c],...r]:r))&&f(a,r):r

```

Takes input as an array of strings representing lines and returns an array of arrays of values e.g. `[[2, 3, "R"], [3, 4, "L"], [1, 2, "R"]]`. The reverse ordering helps with the eliminations.
> 5 votes

# Answer
## Python 2, ~~244~~ 241 bytes

```
m=[]
for l in input():
 for i in range(len(l)):
  c=l[i];a=i/2+1;L,R=[a,a+1,'LR'[c>'v']],[a,a+1,'RL'[c>'v']];x=m.index(L)if L in m else-1;M=zip(*m[:x+1])
  if c in'xX':
   if x>=0and(a in M[1]or a+1in M[0])<1:del m[x]
   else:m=[R]+m
print m

```

Takes input as list of strings

**Example:**

Input: `['| | | |', ' X | |', '| | x ', '| X |', ' x | |']`

Output: `[[1, 2, 'L'], [2, 3, 'R'], [3, 4, 'L'], [1, 2, 'R']]`

Edit: Fixed for case:

Input: `['| | |', ' X |', ' X |', ' x |', '| X', ' X |', ' x |', ' x |', '| | |']`

Output: `[[1, 2, 'L'], [2, 3, 'R'], [1, 2, 'R']]`
> 3 votes

---
Tags: code-golf, string
---


title: Uniquely removable subsequences

text:
# Question
Title: Uniquely removable subsequences
## Introduction

Consider a sequence of integers and one of its subsequences, say **A = \[4 2 2 4 4 6 5\]** and **B = \[2 4 5\]**. We want to remove the elements of **B** from **A** in order, and there are several ways of doing that:

```
A = 4 2 2 4 4 6 5
B =   2   4     5
 -> 4   2   4 6

A = 4 2 2 4 4 6 5
B =     2 4     5
 -> 4 2     4 6

A = 4 2 2 4 4 6 5
B =   2     4   5
 -> 4   2 4   6

A = 4 2 2 4 4 6 5
B =     2   4   5
 -> 4 2   4   6

```

In all cases, the remaining sequence is the same, **\[4 2 4 6\]**. If this happens, we say that **B** is *uniquely removable from* **A**.

## The task

Your inputs are two sequences of nonnegative integers, **A** and **B**, where **B** is guaranteed to be a subsequence of **A**. The inputs may be equal, and they may be empty. You can take them in any order you want, in any reasonable format.

Your output shall be a truthy value if **B** is uniquely removable from **A**, and a falsy value if not.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins.

## Test cases

```
[] [] -> True
[0,3] [] -> True
[1,0,1] [1] -> False
[0,2] [0,2] -> True
[2,2,1,1,2,2,2] [2,1] -> True
[4,2,2,4,4,6,5] [4,5] -> False
[10,5,10,10,5,10] [10,5,10] -> False
[4,2,2,4,4,6,5] [2,4,5] -> True
[1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True
[0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False
[0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True
[0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True
[1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False
[0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False
[5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False
[5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False
[0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True

```

# Answer
> 6 votes
# Haskell, ~~90~~ 84 bytes

```
a%[]=[a]
(t:z)%x@(s:y)=[a|a<-z%y,t==s]++[t:s|s<-z%x]
_%_=[]
((all=<<(==).head).).(%)

```

Construct the list of all possible subtracted sequences nondeterministically and checks whether they are all equal.

Usage:

```
*Main> mapM_(\(a,b)->let r=(((all=<<(==).head).).(%)) a b in putStrLn$concat[show a," ",show b," -> ",show r]) [([],[]), ([0,3],[]), ([1,0,1],[1]), ([0,2],[0,2]), ([2,2,1,1,2,2,2],[2,1]), ([4,2,2,4,4,6,5],[4,5]), ([10,5,10,10,5,10],[10,5,10]), ([4,2,2,4,4,6,5],[2,4,5]), ([1,1,1,0,0,0,1,1,1,0],[1,0,1,1]), ([0,1,0,0,0,0,1,1,0,1],[1,0,1,1]), ([0,4,0,0,4,1,4,2,2],[0,0,0,1,4]), ([0,2,2,25,0,2,2,26,0,0,2],[2,0,0,0,2]), ([1,1,1,3,2,1,3,2,2,3,3,2],[1,1,2,3,2]), ([0,3,2,0,1,3,2,0,0,0,3,2],[0,1,2,0,3]), ([5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5],[2,7,5,7,7,2]), ([5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1],[4,0,1,1,2,1]), ([0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4],[0,1,0,0,2,0,1,4])]
[] [] -> True
[0,3] [] -> True
[1,0,1] [1] -> False
[0,2] [0,2] -> True
[2,2,1,1,2,2,2] [2,1] -> True
[4,2,2,4,4,6,5] [4,5] -> False
[10,5,10,10,5,10] [10,5,10] -> False
[4,2,2,4,4,6,5] [2,4,5] -> True
[1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True
[0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False
[0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True
[0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True
[1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False
[0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False
[5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False
[5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False
[0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True

```

Thanks to @Zgarb for saving 6 bytes!

# Answer
> 4 votes
# JavaScript (ES6), 141 ~~152 156 159~~

Recursive function - quite long

```
f=(a,b,i=0,j=0,r=a,S=new Set)=>(1/b[j]?1/a[i]&&f(a,b,i+1,j,r,S,a[i]-b[j]||f(a,b,i+1,j+1,r=[...r],r[i]=S)):S.add(0+r.filter(x=>1/x)),S.size<2)

```

*Less golfed*

```
f=(a, b,
   i = 0, // current position to match in a
   j = 0, // current position to match in b
   r = a, // current result so far, A with elements of B removed - start == A
   S = new Set // set of possible "A removed B"
) => (
    1 / b[j] // check if j is still inside B
    ? 1 / a[i] // if i is inside A
      && (
        // in any case try to find current element of B in the remaining part of A
        f(a, b, i+1, j, r, S),
        a[i] == b[j] // if match was found between A and B
        &&
          // mark current element in a copy of r and
          // look for the next element of B in the remaining part of A
          f(a, b, i+1, j+1, r=[...r], r[i]=S),
      )
    // else - j is not inside B, we have a solution in r
    // use filter to get a copy without the marked elements
    //  (note: 1/any_number == number_not_0, 1/Object == NaN)
    // then convert to string, to use as a key in S
    : S.add(0+a.filter(x=>1/x)),
    S.size<2 // return true if S has only 1 element
)

```

**Test**

```
f=(a,b,i=0,j=0,r=a,S=new Set)=>(1/b[j]?1/a[i]&&f(a,b,i+1,j,r,S,a[i]-b[j]||f(a,b,i+1,j+1,r=[...r],r[i]=S)):S.add(0+r.filter(x=>1/x)),S.size<2)

out=(...x)=>O.textContent+=x.join` `+'\n'
;`[] [] -> True
[0,3] [] -> True
[1,0,1] [1] -> False
[0,2] [0,2] -> True
[2,2,1,1,2,2,2] [2,1] -> True
[4,2,2,4,4,6,5] [4,5] -> False
[10,5,10,10,5,10] [10,5,10] -> False
[4,2,2,4,4,6,5] [2,4,5] -> True
[1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True
[0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False
[0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True
[0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True
[1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False
[0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False
[5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False
[5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False
[0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True`
.split('\n').forEach(t=>{
  var [a,b,_,k]=t.match(/\S+/g)
  var r=f(eval(a),eval(b))
  out(r==(k[0]=='T')?'OK':'KO',a,b,r,k)
})
```

```
<pre id=O></pre>
```

# Answer
> 3 votes
# Pyth - 27 bytes

On mobile in school right now, so not fully golfed.

```
JE!t{.DLQfqJ@LQT{I#{SM^UQlJ

```

Test Suite

# Answer
> 3 votes
## JavaScript (ES6), ~~116~~ ~~114~~ 113 bytes

Returns `false` or `true`.

```
(a,b,p)=>((F=(a,i,m)=>1/b[i]?a.map((n,j)=>m>j|n-b[i]||F(a.filter((_,k)=>j-k),i+1,j)):p?r|=p!=a:p=a+'')(a,r=0),!r)

```

### Formatted and commented

```
(                                     // given:
  a, b,                               // - a, b = input arrays
  p                                   // - p = reference pattern, initially undefined
) => (                                //
  (F = (                              // F is our recursive search function, with:
    a,                                // - a = current working copy of the main array
    i,                                // - i = index in 'b'
    m                                 // - m = minimum index of matching values in 'a'
  ) =>                                //
    1 / b[i] ?                        // if we haven't reached the end of 'b':
      a.map((n, j) =>                 //   for each element 'n' at index 'j' in 'a':
        m > j | n - b[i] ||           //     if 'n' is a valid matching value,
        F(                            //     do a recursive call to F(), using:
          a.filter((_, k) => j - k),  //     - a copy of 'a' without the current element
          i + 1,                      //     - the next index in 'b'
          j                           //     - 'j' as the new minimum index in 'a'
        )                             //
      )                               //
    :                                 // else:
      p ?                             //   if the reference pattern is already set:
        r |= p != a                   //     check if it's matching the current 'a'
      :                               //   else:
        p = a + ''                    //     set the current 'a' as the reference pattern
  )(a, r = 0),                        //  initial call to F() + initialization of 'r'
  !r                                  //  yields the final result
)                                     //

```

### Test cases

```
let f =

(a,b,p)=>((F=(a,i,m)=>1/b[i]?a.map((n,j)=>m>j|n-b[i]||F(a.filter((_,k)=>j-k),i+1,j)):p?r|=p!=a:p=a+'')(a,r=0),!r)

console.log(f([],[]));                                                        // -> true
console.log(f([0,3],[]));                                                     // -> true
console.log(f([1,0,1],[1]));                                                  // -> false
console.log(f([0,2],[0,2]));                                                  // -> true
console.log(f([2,2,1,1,2,2,2],[2,1]));                                        // -> true
console.log(f([4,2,2,4,4,6,5],[4,5]));                                        // -> false
console.log(f([10,5,10,10,5,10],[10,5,10]));                                  // -> false
console.log(f([4,2,2,4,4,6,5],[2,4,5]));                                      // -> true
console.log(f([1,1,1,0,0,0,1,1,1,0],[1,0,1,1]));                              // -> true
console.log(f([0,1,0,0,0,0,1,1,0,1],[1,0,1,1]));                              // -> false
console.log(f([0,4,0,0,4,1,4,2,2],[0,0,0,1,4]));                              // -> true
console.log(f([0,2,2,25,0,2,2,26,0,0,2],[2,0,0,0,2]));                        // -> true
console.log(f([1,1,1,3,2,1,3,2,2,3,3,2],[1,1,2,3,2]));                        // -> false
console.log(f([0,3,2,0,1,3,2,0,0,0,3,2],[0,1,2,0,3]));                        // -> false
console.log(f([5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5],[2,7,5,7,7,2]));            // -> false
console.log(f([5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1],[4,0,1,1,2,1]));      // -> false
console.log(f([0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4],[0,1,0,0,2,0,1,4]));  // -> true
```

# Answer
> 1 votes
# JavaScript (Firefox 30+), ~~159~~ 147 bytes

```
f=(a,b,i=f(a,b,0))=>i?i.every(x=>x+""==i[0]):b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1),0))[...a.slice(0,i-1),...x]]:[a]

```

Here's a couple of alternate approaches, both anonymous functions:

```
(a,b,f=(a,b,i=0)=>b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1)))[...a.slice(0,i-1),...x]]:[a],c=f(a,b))=>c.every(x=>x+""==c[0])
(a,b,f=(a,b,i=0)=>b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1)))[...a.slice(0,i-1),...x]]:[a])=>new Set(f(a,b).map(btoa)).size<2

```

### Test snippet

```
f=(a,b,i=f(a,b,0))=>i?i.every(x=>x+""==i[0]):b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1),0))[...a.slice(0,i-1),...x]]:[a]

T.textContent = T.textContent.split`
`.map(x => x + ` (${f(...x.split` `.slice(0,2).map(eval))})`).join`
`
```

```
<pre id=T>[] [] -> True
[0,3] [] -> True
[1,0,1] [1] -> False
[0,2] [0,2] -> True
[2,2,1,1,2,2,2] [2,1] -> True
[4,2,2,4,4,6,5] [4,5] -> False
[10,5,10,10,5,10] [10,5,10] -> False
[4,2,2,4,4,6,5] [2,4,5] -> True
[1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True
[0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False
[0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True
[0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True
[1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False
[0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False
[5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False
[5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False
[0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True</pre>
```

# Answer
> 1 votes
# MATL, 27 bytes

```
n:inXN!"1G@&)w2G=?}x]]tvdz~

```

The longest test cases run out of time in the online compiler.

Try it online!

# Answer
> 1 votes
# Mathematica, 128 bytes

```
h=Length;n=ToExpression;g=ToString;y=Array;h@Union@ReplaceList[#2,n@Riffle[y["a"<>g@#<>"___"&,t=h@#+1],#]->n@y["a"<>g@#&,t]]==1&

```

Unnamed function taking two list arguments, where the first is the subsequence and the second is the full sequence; outputs `True` or `False`.

The core part is the following sequence, ungolfed for readability:

```
ReplaceList[#2, ToExpression @
  Riffle[
    Array["a" <> ToString@# <> "___" &, Length@# + 1]
    , #
  ] -> ToExpression @
    Array["a" <> ToString@#& , Length@# + 1 ]
]

```

Here `#` represents the subsequence—for example, `{2,4,5}`. The first `Array` command creates a list of strings like `{"a1___","a2___","a3___","a4___"}`, which is then `Riffle`d together with `#` to yield a weird list like `{"a1___",2,"a2___",4,"a3___",5,"a4___"}`; then this list is cast into an actual Mathematica expression. For the example `{2,4,5}`, a partial evaluation of this core code is

```
ReplaceList[#2, {a1___,2,a2___,4,a3___,5,a4___} -> {a1,a2,a3,a4}]

```

which exactly gives a list of all possible ways to remove the subsequence `{2,4,5}` from `#2` and leave the rest of the list alone.

After this list is generated, we simply remove duplicates using `Union` and test whether the length of the resulting output is 1 or not.

---
Tags: code-golf, array, decision-problem, subsequence
---


title: Numpad Word Search

text:
# Question
Title: Numpad Word Search
Given an integer from 1 to 999 inclusive, output a truthy value if it appears horizontally, vertically, or diagonally, either forwards or backwards, anywhere in the 3x3 square of digits 1-9 on a standard number pad:

```
789
456
123

```

If the number does not appear, output a falsy value.

The exact 65 numbers you need to output truthy for are:

```
1
2
3
4
5
6
7
8
9
12
14
15
21
23
24
25
26
32
35
36
41
42
45
47
48
51
52
53
54
56
57
58
59
62
63
65
68
69
74
75
78
84
85
86
87
89
95
96
98
123
147
159
258
321
357
369
456
654
741
753
789
852
951
963
987

```

Everything else is falsy.

The shortest code in bytes wins.

# Answer
## JavaScript (ES6), ~~83~~ ... ~~74~~ 73 bytes

Takes input as a string.

```
n=>1/([a,b,c]=[...n].map(v=>--v+v/3|0))||45242>>(a^b)&(~c&&n<99|b*2==a+c)

```

*Saved 3 bytes thanks to ETHproductions*

### How it works

We transform the number pad by applying an offset to each digit according to the row it belongs to:

* +1 for the top row
* 0 for the middle row
* -1 for the bottom row.

All codes below are represented in hexadecimal.

```
7 8 9      8 9 A  (+1)
4 5 6  =>  4 5 6  (unchanged)
1 2 3      0 1 2  (-1)

```

Let's consider all XOR combinations of these new key codes. Contiguous keys are highlighted with brackets.

```
XOR|  0   1   2   4   5   6   8   9   A
---+------------------------------------
 0 |  0  [1]  2  [4] [5]  6   8   9   A
 1 | [1]  0  [3] [5] [4] [7]  9   8   B
 2 |  2  [3]  0   6  [7] [4]  A   B   8
 4 | [4] [5]  6   0  [1]  2  [C] [D]  E
 5 | [5] [4] [7] [1]  0  [3] [D] [C] [F]
 6 |  6  [7] [4]  2  [3]  0   E  [F] [C]
 8 |  8   9   A  [C] [D]  E   0  [1]  2
 9 |  9   8   B  [D] [C] [F] [1]  0  [3]
 A |  A   B   8   E  [F] [C]  2  [3]  0

```

We can see that two keys are contiguous if and only if XORing their codes leads to one of the following values:

```
1, 3, 4, 5, 7, C, D, F

```

This list can be packed into the following binary mask:

```
  FEDCBA9876543210
  ----------------
0b1011000010111010 = 0xB0BA = 45242

```

Hence the test to determine if two key codes (a, b) correspond to two contiguous keys:

```
45242 >> (a ^ b) & 1

```

For three key codes (a, b, c), we need this additional test:

```
b * 2 == a + c

```

Example:

```
a = 0xA
b = 0x6
c = 0x2

0xB0BA >> (0xA ^ 0x6) & 1 == 0xB0BA >> 0xC & 1 == 1
=> 0xA and 0x6 are contiguous key codes

0x6 * 2 == 0xA + 0x2
=> 0xA, 0x6 and 0x2 are contiguous key codes on the same row, column or diagonal

```

### Demo

This snippet outputs the list of truthy values.

```
let f =

n=>1/([a,b,c]=[...n].map(v=>--v+v/3|0))||45242>>(a^b)&(~c&&n<99|b*2==a+c)

console.log([...Array(1000).keys()].filter(n=>n && f(n+'')).join(' '))
```
> 16 votes

# Answer
# Python3, 72 bytes

```
lambda n,s="123 456 789 741 852 963 42 753 86 26 159 84 ":n in s+s[::-1]

```

Input is taken as a string.

Golfing suggestions welcome! :D
> 5 votes

# Answer
# Befunge, ~~169~~ ~~161~~ 159 bytes

```
38*:2+"*0>DTV{51"3*\3*"kV"3*\3*"{w"3*\3*"mr"v
v:\&+*83:++66:+"c":+"?":+"$":++66:+"W":*6\*4<
_v#:\_v#*-+%+55g00*+55g02\*-g02\*-g00\`9::::p02/+55p00%"d":
0<@.!!<

```

Try it online!

The first two lines are just pushing the list of test numbers onto the stack. This is done in order of size, since it can sometimes be easier to generate a number as an offset from the previous one in the series rather than generating it from scratch. Once we get to the larger numbers, we can also sometimes save a byte by generating them in pairs, e.g. `"kV"3*\3*` gives us 258 and 321 in nine bytes, where individually they would take five bytes each.

The main loop is on line three, executing right to left with wrap around. This just iterates through all the test numbers on the stack, comparing the value itself, value%100, and value/10. If any of those match the input number or the number \<= 9 then we output 1 and exit. If there is no match, we continue looping. If we run out of test numbers on the stack then we output 0 and exit.

Thanks to Mistah Figgins for saving me a couple of bytes.
> 4 votes

# Answer
# Jelly, ~~29~~ ~~24~~ 19 bytes

*Saved 5 bytes thanks to @Dennis's suggestion of `K` and `Ɠ`.*

```
9s3µUŒD;;Z;ŒDµ;UKƓẇ

```

Try it online!

### Explanation

```
9Rs3µUŒD;;Z;ŒDµ;UKƓẇ  Main link. Argument: number
9s3                   Split [1..9] into [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
   µ                  New monadic chain
    U                 Reverse the rows
     ŒD               Take the diagonals of the result
       ;              Append the original rows
        ;Z            Append the original columns
          ;ŒD         Append the original diagonals
             µ        New monadic chain
              ;U      Append the reverse of everything
                K     Join by spaces
                 Ɠẇ   Check if a line from STDIN is in the result

```
> 3 votes

# Answer
# Ruby, 77 bytes

```
->n{!!((s='123 456 789 147 258 369 753 951 86 62 24 48 ')+s.reverse)["#{n}"]}

```
> 2 votes

# Answer
# bash, 75

```
printf %s\\n 123 456 789 741 852 963 42 753 86 26 159 84|tee >(rev)|grep $1

```

outputs something and returns 0 for all the values in that list

prints nothing and returns 1 in all other cases
> 0 votes

# Answer
# Java, 397 bytes

```
public class Numpad {public static void main(String[] args){Scanner input=new Scanner(System.in);int in=input.nextInt();int h=in/100;int u=in%10;int t=(in%100)/10;boolean out=false;input.close();if(in<10)out=true;else if( h==0){int decider=Math.abs(t-u);if((decider==1)||(decider==3)||(decider==4))out=true;}else{if ( Math.abs(h-t) == Math.abs(t-u))out=true;}System.out.println("RESULT : "+out);}}

```
> 0 votes

---
Tags: code-golf, number, decision-problem, integer
---


title: Nostalgic prime number generator

text:
# Question
Title: Nostalgic prime number generator
Remember the good old days when opening a simple document or web page was painfully slow as it hogged all the meager resources your computer had? And today, doing the same is even slower, despite your processor being hundreds of times faster and having access to thousands of times more memory?

To simulate the effect of bloat in current document viewers and similar applications, **write a program which has visible performance problems when run on more powerful machines**.

To have a common task for everyone, **make it a prime number generator**.

* The program has to print consecutive prime numbers, starting from 2, each in a new line, and nothing else. It should to this forever (or until running out of memory). Like this:

> ```
> 2
> 3
> 5
> 7
> 11
> 13
> 17
>
> ```

* There should be a delay between printing each line, enough to be perceivable by a human.
* This delay should be longer as the machine the program is running on gets faster. The faster the machine, the slower the program.
* I won't specify exact benchmarks as it might become subjective, but there should be a human-perceivable difference in the speed on two different machines if there is significant difference between the performance of the two machines.
* The speed of the program doesn't have to be monotonically decreasing across all existing machines ever created. This would be hard to specify, and even harder to verify. I trust the common sense of the contestants about what can be considered a **significantly different performance** between to machines, and it is enough to satisfy that.
* I also won't specify exact upper or lower time limits, but it should be under reasonable limits, so no days or years between printing two lines please.
* I won't require it to run on everything from the Eniac to modern day, but it should be general enough, for example, it's not allowed to say it only works on two specific CPU types, and specifically detects the name of one specific CPU on which it will run slower or faster.
* The code shouldn't rely on compiler or interpreter version. It should work if the same version of the compiler/interpreter is installed on both a slower and faster machine, or even if the binary / bytecode is compiled on one machine and then run on two different machines.
* Please explain the principles of how your program is operating. As it will be difficult to reproduce the results, the validity of the answer might depend on the the feasibility of the method.

Although I would have liked it to become an underhanded contest, sadly this site is no longer "Programming Puzzles & Code Golf" but just simply "Code Golf", so the shortest code wins.

# Answer
> 4 votes
# Perl, ~~80~~ ~~78~~ 71 bytes

-9 bytes thanks to @Dada

```
$_++;`lscpu`=~/z:\s+(\d+)/,sleep$1,(1x$_)!~/^(11+?)\1+$/&&say while$_++

```

Runs the command `lscpu` and finds the CPU speed in MHz. The faster the CPU, the more time it sleeps between outputs, 1 second for every 1 MHz. Runs on Ubuntu 14.04.5. On my particular machine, this tests each number every 800 seconds (13 minutes, 20 seconds). On faster machines, this can be over 50 minutes. Change it to `sleep$a/400` to get something much more sane for testing purposes.

---
Tags: code-golf, sequence, primes
---


title: Implement division

text:
# Question
Title: Implement division
Implement a division algorithm in your favourite language which handles integer division. It need only handle positive numbers - but bonus points if it handles negative and mixed-sign division, too. Results are rounded down for fractional results.

The program may not contain the `/`, `\`, `div` or similar operators. It must be a routine which does not use native division capabilities of the language.

You only need to handle up to 32-bit division. Using repeated subtraction is not allowed.

**Input**

Take two inputs on stdin separated by new lines or spaces (your choice)

```
740
2

```

**Output**

In this case, the output would be `370`.

The solution which is the shortest wins.

# Answer
> 27 votes
## Python - 73 chars

Takes comma separated input, eg `740,2`

```
from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z

```

# Answer
> 14 votes
## JavaScript, 61

```
A=Array,P=prompt,P((','+A(+P())).split(','+A(+P())).length-1)

```

This makes a string the length of the dividend `,,,,,,` (6) and splits on the divisor `,,,` (3), resulting in an array of length 3: `['', '', '']`, whose length I then subtract one from. Definitely not the fastest, but hopefully interesting nonetheless!

# Answer
> 10 votes
## JavaScript - 36 characters

```
p=prompt;alert(p()*Math.pow(p(),-1))

```

# Answer
> 10 votes
## Python, 37

Step 1. Convert to unary.

Step 2. Unary division algorithm.

```
print('1'*input()).count('1'*input())

```

# Answer
> 9 votes
## Python - 72 chars

Takes comma separated input, eg 740,2

```
x,y=input();z=0
for i in range(32)[::-1]:z+=(1<<i)*(y<<i<=x-z*y)
print z

```

# Answer
> 9 votes
## Mathematica: 34 chars

Solves symbolically the equation (x a == b)

```
Solve[x#[[1]]==#[[2]],x]&@Input[]

```

# Answer
> 8 votes
## Python - 41 chars

Takes comma separated input, eg `740,2`

```
x,y=input();z=x
while y*z>x:z-=1
print z

```

# Answer
> 6 votes
## Python, 70

Something crazy I just thought (using comma separated input):

```
from cmath import*
x,y=input()
print round(tan(polar(y+x*1j)[1]).real)

```

If you accept small float precision errors, the `round` function can be dropped.

# Answer
> 5 votes
## APL (6)

```
⌊*-/⍟⎕

```

`/` is not division here, but `foldr`. i.e, `F/a b c` is `a F (b F c)`. If I can't use `foldr` because it's called `/`, it can be done in 9 characters:

```
⌊*(⍟⎕)-⍟⎕

```

Explanation:

* : `input()`
* `⍟⎕`: `map(log, input())`
* `-/⍟⎕`: `foldr1(sub, map(log, input()))`
* `*-/⍟⎕`: `exp(foldr1(sub, map(log, input())))`
* `⌊*-/⍟⎕`: `floor(exp(foldr1(sub, map(log, input()))))`

# Answer
> 4 votes
## Yabasic - 17 characters

```
input a,b:?a*b^-1

```

# Answer
> 3 votes
## PHP - 82 characters (buggy)

```
$i=fgets(STDIN);$j=fgets(STDIN);$k=1;while(($a=$j*$k)<$i)$k++;echo($a>$i?--$k:$k);

```

This is a very simple solution, however - it doesn't handle fractions or different signs (would jump into an infinite loop). I won't go into detail in this one, it is fairly simple.

Input is in stdin, separated by a new line.

## PHP - 141 characters (full)

```
$i*=$r=($i=fgets(STDIN))<0?-1:1;$j*=$s=($j=fgets(STDIN))<0?-1:1;$k=0;$l=1;while(($a=$j*$k)!=$i){if($a>$i)$k-=($l>>=2)*2;$k+=$l;}echo$k*$r*$s;

```

Input and output same as the previous one.

Yes, this is almost twice the size of the previous one, but it:

* handles fractions correctly
* handles signs correctly
* won't ever go into an infinite loop, UNLESS the second parameter is 0 - but that is division by zero - invalid input

Re-format and explanation:

```
$i *= $r = ($i = fgets(STDIN)) < 0 ? -1 : 1;
$j *= $s = ($j = fgets(STDIN)) < 0 ? -1 : 1;
                                    // First, in the parentheses, $i is set to
                                    // GET variable i, then $r is set to -1 or
                                    // 1, depending whether $i is negative or
                                    // not - finally, $i multiplied by $r ef-
                                    // fectively resulting in $i being the ab-
                                    // solute value of itself, but keeping the
                                    // sign in $r.
                                    // The same is then done to $j, the sign
                                    // is kept in $s.

$k = 0;                             // $k will be the result in the end.

$l = 1;                             // $l is used in the loop - it is added to
                                    // $k as long as $j*$k (the divisor times
                                    // the result so far) is less than $i (the
                                    // divided number).

while(($a = $j * $k) != $i){        // Main loop - it is executed until $j*$k
                                    // equals $i - that is, until a result is
                                    // found. Because a/b=c, c*b=a.
                                    // At the same time, $a is set to $j*$k,
                                    // to conserve space and time.

    if($a > $i)                     // If $a is greater than $i, last step
        $k -= ($l >>= 2) * 2;       // (add $l) is undone by subtracting $l
                                    // from $k, and then dividing $l by two
                                    // (by a bitwise right shift by 1) for
                                    // handling fractional results.
                                    // It might seem that using ($l>>=2)*2 here
                                    // is unnecessary - but by compressing the
                                    // two commands ($k-=$l and $l>>=2) into 1
                                    // means that curly braces are not needed:
                                    //
                                    // if($a>$i)$k-=($l>>=2)*2;
                                    //
                                    // vs.
                                    //
                                    // if($a>$i){$k-=$l;$l>>=2;}

    $k += $l;                       // Finally, $k is incremented by $l and
                                    // the while loop loops again.
}

echo $k * $r * $s;                  // To get the correct result, $k has to be
                                    // multiplied by $r and $s, keeping signs
                                    // that were removed in the beginning.

```

# Answer
> 3 votes
## Ruby 1.9, 28 characters

```
(?a*a+?b).split(?a*b).size-1

```

Rest of division, 21 characters

```
?a*a=~/(#{?a*b})\1*$/

```

Sample:

```
a = 756
b = 20
print (?a*a+?b).split(?a*b).size-1  # => 37
print ?a*a=~/(#{?a*b})\1*$/         # => 16

```

For Ruby 1.8:

```
a = 756
b = 20
print ('a'*a+'b').split('a'*b).size-1  # => 37
print 'a'*a=~/(#{'a'*b})\1*$/          # => 16

```

# Answer
> 2 votes
## PHP, 55 characters

```
<?$a=explode(" ",fgets(STDIN));echo$a[0]*pow($a[1],-1);

```

Output (740/2): http://codepad.viper-7.com/ucTlcq

# Answer
> 2 votes
## Haskell, 96 characters

```
main=getLine>>=print.d.map read.words
d[x,y]=pred.snd.head.filter((>x).fst)$map(\n->(n*y,n))[0..]

```

Input is on a single line.

The code just searches for the answer by taking the divisor `d` and multiplying it against all integers `n >= 0`. Let `m` be the dividend. The largest `n` such that `n * d <= m` is picked to be the answer. The code actually picks the least `n` such that `n * d > m` and subtracts 1 from it because I can take the first element from such a list. In the other case, I would have to take the last, but it's hard work to take the last element from an infinite list. Well, the list can be proven to be finite, but Haskell does not know better when performing the filter, so it continues to filter indefinitately.

# Answer
> 2 votes
## Scala 77

```
def d(a:Int,b:Int,c:Int=0):Int=if(b<=a)d(a-b,b,c+1)else c
d(readInt,readInt)

```

# Answer
> 2 votes
### Common Lisp, 42 charaacters

```
(1-(loop as x to(read)by(read)counting t))

```

Accepts space or line-separated input

# Answer
> 2 votes
## Python - 45 chars

Takes comma separated input, eg 740,2

```
x,y=input()
print-1+len((x*'.').split('.'*y))

```

# Answer
> 2 votes
# Bash, ~~72~~ 64 characters

```
read x y;yes ''|head -n$x>f;ls -l --block-size=$y f|cut -d\  -f5

```

Output an infinite number of newlines, take the first x, put them all into a file called f, then get the size of f in blocks the size of y. Took manatwork's advice to shave off eight characters.

# Answer
> 2 votes
# Python, 37

```
x,y=input()
print len(('0'*x)[y-1::y])

```

Constructs a string of length `x` (`'0'*x`) and uses extended slicing to pick every `y`th character, starting from the index `y-1`. Prints the length of the resulting string.

Like Gnibbler, this takes comma separated input. Removing it costs `9` chars:

```
i=input
x,y=i(),i()
print len(('0'*x)[y-1::y])

```

# Answer
> 2 votes
# Retina 0.7.3, 33 bytes

Takes space-separated input with the divisor first. Dividing by zero is undefined.

```
\d+
$*
^(.+) (\1)+.*$
$#+
.+ .*
0

```

**Try it online**

# Answer
> 1 votes
## Python, 46 bytes

Nobody had posted the boring subtraction solution, so I could not resist doing it.

```
a,b=input()
i=0
while a>=b:a-=b;i+=1
print i
```

# Answer
> 1 votes
# Python, 94 characters

A recursive binary search:

```
a,b=input()
def r(m,n):return r(m,m+n>>1)if n*b>a else n if n*b+b>a else r(n,2*n)
print r(0,1)

```

# Answer
> 1 votes
# Python, 40 characters

```
print(float(input())*float(input())**-1)

```

# Answer
> 1 votes
# C, 43 bytes

Implements `a/b` in a linear search. Handles only positive arguments.

```
i;f(a,b){i=0;while(1)if(++i*b>a)return--i;}

```

Ungolfed:

```
i;
f(a, b){
  i = 0;
  while (1)
    if (++i * b > a)
      return --i;
}

```

# Answer
> 0 votes
**Smalltalk**, Squeak 4.x flavour

define this binary message in Integer:

```
% d
    | i |
    d <= self or: [^0].
    i := self highBit - d highBit.
    d << i <= self or: [i := i - 1].
    ^1 << i + (self - (d << i) % d)

```

Once golfed, this quotient is still long (88 chars):

```
%d|i n|d<=(n:=self)or:[^0].i:=n highBit-d highBit.d<<i<=n or:[i:=i-1].^1<<i+(n-(d<<i)%d)

```

But it's reasonnably fast:

```
[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n%d)]].
] timeToRun.

```

-\> 127 ms on my modest mac mini (8 MOp/s)

Compared to regular division:

```
[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n//d)]].
] timeToRun.

```

-\> 31 ms, it's just 4 times slower

I don't count the chars to read stdin or write stdout, Squeak was not designed for scripting.

```
FileStream stdout nextPutAll:
    FileStream stdin nextLine asNumber%FileStream stdin nextLine asNumber;
    cr

```

Of course, more stupid repeated subtraction

```
%d self>d and:[^0].^self-d%d+1

```

or plain stupid enumeration

```
%d^(0to:self)findLast:[:q|q*d<=self]

```

could work too, but are not really interesting

# Answer
> 0 votes
# DC: 26 characters

```
?so?se0[1+dle*lo>i]dsix1-p

```

I do admit that it is not the fastest solution around.

# Answer
> 0 votes
# Python 54

Takes comma delimited input.

1. Makes a string of dots of length x
2. Replaces segments of dots of length y with a single comma
3. Counts commas.

Words because markdown dies with a list followed by code?:

```
x,y=input()
print("."*x).replace("."*y,',').count(',')

```

# Answer
> 0 votes
# Q, 46

```
{-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}

```

.

```
q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;2]
370
q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;3]
246

```

---
Tags: code-golf, arithmetic, division
---


title: Travelling Salesman

text:
# Question
Title: Travelling Salesman
You are given, as a list or vector or whatever, a bunch of 3-tuples or whatever, where the first two things are strings, and the third thing is a number. The strings are cities, and the number is the distance between them. The order of the cities in the tuple is arbitrary (i.e. it doesn't matter which comes first and which comes second) since it is the same distance each way. Also, there is exactly one tuple for each pair of connected cites. Not all cities may be connected. Also, the distance is always positive (not `0`). You do not need to check these conditions, you may assume input will be well formed. Your job is to return the cities in a cyclic sequence, such that, if you start at any one city, and go around the sequence back to the same city, the total of the distances between the cities will be minimum (exactly and in all cases.) You may assume a solution exists. For example, let us say you are given

```
[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]

```

You could output any of the following (but you only need to output one):

```
["Detroit","Hong Kong","Dillsburg","New York"]
["Hong Kong","Dillsburg","New York","Detroit"]
["Dillsburg","New York","Detroit","Hong Kong"]
["New York","Detroit","Hong Kong","Dillsburg"]
["Dillsburg","Hong Kong","Detroit","New York"]
["New York","Dillsburg","Hong Kong","Detroit"]
["Detroit","New York","Dillsburg","Hong Kong"]
["Hong Kong","Detroit","New York","Dillsburg"]

```

because it is the shortest trip: 13.9

but not

```
["Dillburg","Detroit","New York","Hong Kong"]

```

because it is not the shortest.

See en.wikipedia.org/wiki/Travelling\_salesman\_problem

**Scoring**

This is where it gets interesting. You take the number of characters you have, and then plug them into the bare worst case O-notation formula. For example, let us say you write a brute force program that is 42 characters. As we all know, the worst case is `n!` where `n` is the number of cities. 42!=1405006117752879898543142606244511569936384000000000, so that is your score. The **lowest score wins**.

Note: I relieved this afterwards too, but wasn't sure how to solve it and hoped that no one would notice. People did, so I will go with issacg's suggestion:

> the only options are O(n!) and O(b^n*n^a*ln(n)^k), and all bounds must be as tight as possible given that notation

# Answer
> 5 votes
# Haskell, 259

I thought I would be able to get it shorter. maybe I will.
this has time complexity of O(n^2\*2^n)\* so score is about 6.2e82

<sub>\*i'm not actually sure, but if there is any "addition" to the complexity it's not more than polynomial, so this shouldn't change the score much.</sub>

```
import Data.List
g e=tail$snd$minimum[r|r@(_,b)<-iterate(\l->nubBy((.f).(==).f)$sort[(b+d,c:a)|(b,a)<-l,c<-h\\init a,d<-a!!0%c])[(0,[h!!0])]!!length h,b!!0==h!!0]where h=sort$nub$e>>= \(a,b,_)->[a,b];a%b=[z|(x,y,z)<-e,x==a&&y==b||x==b&&y==a]
f(_,x:b)=x:sort b

```

# Answer
> 5 votes
# Python 2, 237 231 228 225 characters

Since this is a naive algorithm, its score is probably about 225! ≈ 1.26e433.

```
from itertools import*
a=input()
n=lambda*a:tuple(sorted(a))
d=dict((n(*x[:2]),x[2])for x in a)
print min(permutations(set(chain(*[x[:2]for x in a]))),key=lambda x:sum(d.get(n(x[i],x[i+1]),1e400)for i in range(-1,len(x)-1)))

```

# Answer
> 4 votes
# Julia, 213 chars

Probably goes like `n!n`, so ~2e407.

```
a=[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]
f(a)=(
d(x,y)=(r=filter(z->x in z&&y in z,a);r==[]?Inf:r[1][3]);
m=Inf;
q=0;
c=unique([[z[1] for z=a],[z[2] for z=a]]);
n=length(c);
for p=permutations(c);
    x=sum([d(p[i],p[mod1(i+1,n)]) for i=1:n]);
    x<m&&(m=x;q=p);
end;
q)
f(a)

```

For readability and to demonstrate use I left in some unscored newlines and tabs as well as example input and a call to the function. Also I used an algorithm that requires `n!` time, but not `n!` memory, its slightly more feasible to run.

# Answer
> 2 votes
# Python 3 - 491

I did not count the length of the input graph variable `g`. This solution uses dynamic programming, and has a complexity of n^2 * 2^n, for a total score of ~6.39e147. I am still pretty new to golfing, so please chime in if you see a big waste of code somewhere!

```
g=[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]
s=''
c={s:1}
D={}
for t in g:c[t[0]]=1;c[t[1]]=1;D[(t[0],t[1])]=t[2];D[(t[1],t[0])]=t[2];D[('',t[0])]=0;D['',t[1]]=0
V={}
y=[x for x in c.keys() if x!='']
f=''
def n(z,p):
 if(len(p)==len(y)-1):
  global f;f=z
 if(0==len(p)):
  return (D[(z,f)] if (z,f) in D else float('inf'))
 Y=[(float('inf'),'')]
 for P in p:
  if((z,P) in D):
   Y.append((D[(z,P)] + n(P,[m for m in p if m!=P]), P))
 V[(z,tuple(p))]=min(Y)
 return min(Y)[0]
n('',y)
for i in range(len(c)-1):
 N=V[(s,tuple(y))][1]
 print(N)
 s=N
 y.remove(N)

```

# Answer
> 1 votes
## Mathematica, 66 bytes

```
Most@Last@FindShortestTour@Graph[#<->#2&@@@#,EdgeWeight->Last/@#]&

```

No idea on the complexity, so the score is somewhere between `10^23` and `10^93`.

# Answer
> 0 votes
# Ruby, ~~198~~ 180 bytes

```
G=eval(gets.tr("()","[]"))
C=G.map{|t|[t[0],t[1]]}.flatten.uniq
D=Hash.new(+1.0/0)
G.map{|p|D[[p[0],p[1]]]=D[[p[1],p[0]]]=p[2]}
p C.permutation.map{|l|d=0;p=l[-1];l.map{|c|d+=D[[p,c]];p=c};[d,l]}.sort[0][1]

```

The first line that reads the input is unscored, as that seems to be what everyone else is doing. Also, there is no final newline needed for ruby.

It just dumbly generates all permutations of cities, so put me down for `O(n!*n)`. Actually, on second thoughts, it's slower even than that, because it sorts all `O(n!)` paths rather than keeping track of the best so far.

---
Tags: code-challenge, optimization
---


title: Parse a raw IRC message

text:
# Question
Title: Parse a raw IRC message
In the IRC protocol, raw messages look similar to this:

```
command arg1 arg2 :arg3 with spaces :arg4 with spaces :arg5

```

In a shell environment (e.g. bash), that would be equivalent to:

```
command arg1 arg2 "arg3 with spaces" "arg4 with spaces" arg5

```

The format specification is as follows:

* Raw messages will only contain printable ASCII characters (ordinals 32-126).
* Raw messages will start with a command, which will not contain any spaces.
* Any number of arguments may follow a command. Arguments are delimited by one or more spaces followed by a colon (`<space>:` and `<space><space>:` are both valid delimiters).
    + Any arguments that do not contain spaces may omit the colon from the delimiter so long as all previous arguments (if any) have omitted the colon.
* Colons will not appear within arguments or commands.
* Arguments will not begin with a space.

For example, these are all valid raw messages:

```
join #foo #bar #baz
msg person hi
msg #channel :hello world
help :how do I use IRC
foo bar :baz bip :abc def :ghi

```

These are all invalid raw messages:

```
error :n:o colons within arguments
error ::need spaces between colons
:error no colons in commands
error non-ASCII character Ω

```

Given a valid raw IRC message as input, output a list containing the command and the arguments, properly parsed.

## Test Cases

```
"join #foo #bar #baz" -> ["join", "#foo", "#bar", "#baz"]
"msg person hi" -> ["msg", "person", "hi"]
"msg #channel :hello world" -> ["msg", "#channel", "hello world"]
"help :how do I use IRC" -> ["help", "how do I use IRC"]
foo bar :baz bip :abc def :ghi :xyz -> ["foo", "bar", "baz bip", "abc def", "ghi", "xyz"]

```

# Answer
# Jelly, 19 bytes

```
;⁷œṣ⁾ :µḢḲ;œr€⁶ỴF$€

```

A monadic link that returns a list.

Note: As a full program the implicit print that Jelly performs may be a little confusing in this case, since a list containing strings (really lists of characters in Jelly) is printed as if it were a single string. So, for completeness here are test harnesses employing the quick `Ç` which calls the previous link monadically:

1. shows the Jelly representation of a list of character lists;
2. `Y` joins the list with line feeds;
3. `ŒṘ` shows the underlying Python representation (showing the actual lists of characters).

### How?

Handling the edge case of possible trailing spaces for the ultimate argument (the only one which may have trailing spaces) is quite an expense at 6 bytes; maybe there is a shorter way?

```
;⁷œṣ⁾ :µḢḲ;œr€⁶ỴF$€ - Link expecting a single list of characters as input
;                   - concatenate
 ⁷                  - a line feed (to avoid right trimming spaces from ultimate argument)
  œṣ                - split on sublists equal to
    ⁾ :             -     two character list [' ',':']
       µ            - monadic chain separation (call the split result z)
        Ḣ           - head - pop first element (modifies z)
         Ḳ          - split at spaces
          ;         - concatenate with z
              ⁶     - space
           œr€      - right-strip from €ach
                 $€ - last two links as a monad for €ach
               Ỵ    -     split on line feeds
                F   -     flatten (removes the line feed from the beginning)

```
> 0 votes

# Answer
# PHP, 87 bytes

```
$a=($s=preg_split)("# +:#",$argv[1]);array_splice($a,0,1,$s("# +#",$a[0]));print_r($a);

```

The first regex splits the argument by one or more spaces followed by a colon.
The second regex splits the first element by one or more spaces with no colon.
`array_splice` replaces the first element with the result of the second `preg_split`.
`print_r` prints the resulting array.

**function version for testing**

```
$cases=[
    "join #foo #bar #baz" => ["join", "#foo", "#bar", "#baz"],
    "msg person hi" => ["msg", "person", "hi"],
    "msg #channel :hello world" => ["msg", "#channel", "hello world"],
    "help :how do I use IRC" => ["help", "how do I use IRC"],
    "foo bar :baz bip :abc def :ghi :xyz" => ["foo", "bar", "baz bip", "abc def", "ghi", "xyz"],
];
function i($argv_1_){$a=($s=preg_split)("# +:#",$argv_1_);array_splice($a,0,1,$s("# +#",$a[0]));return $a;}
foreach($cases as$x=>$e)
{
    $y=i($x);
    echo "case '$x': ['",join("','",$y),'"]: ',($y<>$e?"FAIL. Expected: ['". join("','",$e)."']":OK),"\n";
}

```
> 2 votes

# Answer
# Retina, 24 bytes

```
M!`:.+?(?=\s+:|$)|\S+
:

```

(note there is a trailing newline)

Try it online!
> 2 votes

# Answer
## PowerShell v2+, ~~43~~ 34 bytes

```
$a,$b=$args-split' +:';-split$a;$b

```

This `-split`s the input string `$args` on the regex `+:` (i.e., one or more spaces and a colon), stores the left-most (i.e., first result) into `$a` and any remaining results into `$b`. We then need to `-split` `$a` on spaces (here done by leveraging that whitespace is the default for unary `-split`), and that's left on the pipeline. We then simply put `$b` on the pipeline. Output via implicit `Write-Output` inserts a newline between elements.

### Test cases

```
PS C:\Tools\Scripts\golfing> .\parse-raw-irc.ps1 'join #foo #bar #baz'
join
#foo
#bar
#baz

PS C:\Tools\Scripts\golfing> .\parse-raw-irc.ps1 'msg person hi'
msg
person
hi

PS C:\Tools\Scripts\golfing> .\parse-raw-irc.ps1 'msg channel :hello world'
msg
channel
hello world

PS C:\Tools\Scripts\golfing> .\parse-raw-irc.ps1 'help :how do I use IRC'
help
how do I use IRC

PS C:\Tools\Scripts\golfing> .\parse-raw-irc.ps1 'foo bar :baz bip :abc def :ghi :xyz'
foo
bar
baz bip
abc def
ghi
xyz

```
> 1 votes

# Answer
# Mathematica, 44 bytes

```
Flatten@MapAt[s=StringSplit,#,1]&@s[#," :"]&

```
> 0 votes

# Answer
# C, 140 bytes (excluding sample usage)

```
void p(char*m){char*c=strchr(m,':');if(c) {*c=0;c++;}
char*n=strtok(m," ");while(n) {puts(n);n=strtok(NULL," ");}
if(c){puts(c);}}

```

Sample usage:

```
#include <string.h>
#include <stdio.h>
void parse(char*msg){char*c=strchr(msg,':');if(c) {*c=0;c++;}
char*n=strtok(msg," ");while(n){puts(n);n=strtok(NULL," ");}
if(c){puts(c);}}
main(){char msg[]="sample : abcnsjd hajs";parse(msg);}

```

Try me: http://codepad.org/GQ51MO4l
> 0 votes

# Answer
# JavaScript (ES6), ~~59~~ ~~57~~ ~~56~~ 49 bytes

This is my first entry on PPCG, any input appreciated!

```
(s,[a,...b]=s.split(/ +:/))=>a.split` `.concat(b)

```

---

**EDIT History:**

* Thanks @Mego for saving 2 bytes by making it an anonymous function.
* Replaced `\s` with  to save 1 byte.
* Thanks @BassdropCumberwubwubwub for showing me the `split` `` syntax and the `[a,...b]=array_expression_here` syntax. I didn't know these were possible, thank you very much! Very clever!

### Test snippet

```
let f = (s,[a,...b]=s.split(/ +:/))=>a.split` `.concat(b)
```

```
<input id=I type="text" size=70 value="command arg1 arg2 :arg3 with spaces :arg4 with spaces :arg5"><button onclick="console.log(f(I.value))">Run</button>
```
> 0 votes

# Answer
# Python 2, ~~64~~ 60 bytes

```
import re;a=re.split(' +:',input());print a[0].split()+a[1:]

```

Edit:
Requires quoted input to use `input`.
Preserves trailing spaces on last argument.
> 0 votes

# Answer
# Perl 6,  ~~49~~  47 bytes

```
{m/(<-[\ :]>+)+%%" "+":"?(.+?)*%[" "+":"]$/.flat}

```

Perl 6 version of the Python answer

```
{$/=.split(/" "+":"/);|$0.split(" "),|$/[1..*]}

```

The to `|`s are there to flatten the list.

## the first entry expanded:

```
{    # bare block lambda with implicit parameter ｢$_｣

  m/               # regex match implicitly against ｢$_｣

      (               # capture
        <-[\ :]>+     # at least one non-space non-colon character
      )+              # at least once

    %%                # separated (with optional trailing separator)

      " "+            # by at least one space

    ":"?              # optionally match a colon ( needed for rest of regex )

      (               # capture
        .+?           # at least one character as short as possible
      )*              # any number of times

    %                 # separated (no optional trailing separator)

      [ " "+ ":" ]    # by at least one space, and a colon

    $                 # match end of string (needed because of ｢.+?｣)
  /

 .flat         # flatten the captures
}

```
> 0 votes

---
Tags: code-golf, string, parsing
---


# Question
Title: Find the shortest pangrams from a word list
A *pangram* is a string that contains every letter `a`-`z` of the English alphabet, case-insensitive. (It's OK if the pangram contains more than one copy of a letter, or if it contains non-letter characters in addition to the letters.)

Write a program or function whose input is a list of strings, and which outputs one or more strings which have the following properties:

* Each output string must be a pangram.
* Each output string must be formed by concatenating one or more strings from the input list, separated by spaces.
* Each output string must be the shortest, or tied for the shortest, among all strings with these properties.

Many programs will choose to output only one string; you'd only want to output more than one string if you'd otherwise have to write extra code to limit the output.

You may assume that the input contains no unprintable characters or spaces, and that no word in it is more than (26 times the natural logarithm of the length of the list) characters long. (You may not assume, however, that the input contains nothing but letters, or only lowercase letters; punctuation marks and uppercase letters are entirely possible.)

Input and output can be given in any reasonable format. For testing your program, I recommend using two test cases: a dictionary of English words (most computers have one), and the following case (for which a perfect (26-letter) pangram is impossible, so you'd have to find one containing duplicate letters):

```
abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz

```

You should include a sample of your program's output along with your submission. (This may well be different for different people as a result of using different word lists.)

# Victory condition

This is a challenge. The winner is the shortest program (in bytes) that runs in *polynomial time*. (A summary for people who don't know what that means: if you double the size of the word list, the program should become slower by no more than a constant factor. However, the constant factor in question can be as large as you like. For example, it's valid for it to become four times slower, or eight times slower, but not for it to become smaller by a factor of the length of the word list; the factor via which it becomes slower must be bounded.)

# Answer
> 3 votes
# Ruby 159 (iterative)

# Ruby ~~227~~ ~~220~~ ~~229~~ ~~227~~ 221 (recursive)

New iterative solution (based on the algorithm described by @Niel):

```
c={('A'..'Z').to_a=>""}
while l=gets
d=c.clone
c.map{|k,v|j=k-l.upcase.chars
w=v+" "+l.strip
d[j]=w if !c[j]||c[j].size<w.size}
c=d
end
x=c[[]]
p x[1..-1] if x

```

Old recursive solution:

```
W=[]
while l=gets
W<<l.strip
end
I=W.join(" ")+"!!"
C={[]=>""}
def o(r)if C[r]
C[r]
else
b=I
W.map{|x|s=r-x.upcase.chars
if s!=r
c=x+" "+o(s)
b=c if c.size<b.size
end}
C[r]=b
end
end
r=o ('A'..'Z').to_a
p r[0..-2] if r!=I

```

The byte measurement is based on leaving off the final newline in the file, which does not matter to `ruby 2.3.1p112`. The byte count went back up after fixing a small bug (adding ~~`.downcase`~~ `.upcase` for case-insensitivity as required by the problem statement).

Here is an earlier version from before shortening identifiers and such:

```
#!/usr/bin/env ruby

$words = [];

while (line=gets)
  $words << line[0..-2];
end

$impossible = $words.join(" ")+"!!";

$cache = {};

def optimize(remaining)
  return $cache[remaining] if ($cache[remaining]);
  return "" if (remaining == []);

  best = $impossible;

  $words.each{|word|
    remaining2 = remaining - word.chars;
    if (remaining2 != remaining)
      curr = word + " " + optimize(remaining2);
      best = curr if (curr.length < best.length);
    end
  };

  $stderr.puts("optimize(#{remaining.inspect})=#{best.inspect}");

  return $cache[remaining] = best;
end

result = optimize(('a'..'z').to_a);

puts(result[0..-1]);

```

How does it work? It basically maintains a set of characters still to cover and only recurses on a word if it would reduce the uncovered set. Additionally, the results of recursion are memoized. Each subset of 2^26 corresponds to a memoization table entry. Each such entry is calculated in time proportional to the size of the input file. So the whole thing is `O(N)` (where `N` is the size of the input file), albeit with a huge constant.

# Answer
> 1 votes
## JavaScript (ES6), ~~249~~ 248 bytes, possibly competing

```
a=>a.map(w=>w.replace(/[a-z]/gi,c=>b|=1<<parseInt(c,36)-9,b=0,l=w.length)&&(m.get(b)||[])[0]<l||m.set(b,[l,w]),m=new Map)&&[...m].map(([b,[l,w]])=>m.forEach(([t,s],e)=>(m.get(e|=b)||[])[0]<=t+l||m.set(e,[t+l+1,s+' '+w])))&&(m.get(-2^-1<<27)||[])[1]

```

Explanation: Transforms the array by converting the letters into a bitmask, saving only the shortest word for each bitmask in a map. Then iterating over a copy of the map, augment the map by adding each combined bitmask if the resulting string would be shorter. Finally return the string saved for the bitmap corresponding to a pangram. (Returns `undefined` if no such string exists.)

# Answer
> -1 votes
# Python 3, 98, 94, 92 bytes

```
print([s for s in input().split()if sum([1 for c in range(65,91)if chr(c)in s.upper()])>25])

```

Iterates through the ASCII representation of the alphabet and adds a 1 to a list if the letter is found in the string. If the sum of the list is greater than 25 it contains all letters of the alphabet and will be printed.

---
Tags: code-golf, string, natural-language, restricted-complexity
---


# Question
Title: Help my maniacal wife decorate our Christmas tree
My wife is very, let's say, particular when it comes to putting ornaments on our Christmas tree. Let's get her some code to help her in this trying time.

### Input

Given an input `2 < n < 10` the height of the tree and `0 < k < n` the distinct number of ornaments.

### Task

Decorate the tree starting with `1` and increment to `k` as we wrap the ornaments around the tree. If we reach `k` and we have more branches to decorate then start back at `1`.

It is okay if there are not the same number of each ornament on the tree, as long as the pattern is satisfied.

The ornaments should appear above each branch `^` except for the top row.

The tree is structured by starting with one branch then the next level has + 1 branches with a space between each, staggered from the top like:

```
 ^
^ ^

```

For a third row you would add one more branch and stagger them again such that no branch is on the same column (if you think of it like a grid).

```
  ^
 ^ ^
^ ^ ^

```

### Output

Output your decorated tree.

### Examples

### 1.

`n = 3, k = 2`

```
  ^      //Height is 3
 ^ ^
^ ^ ^

```

Now we decorate each branch starting with 1 and increment to k:

```
  ^
 1 2
 ^ ^
1 2 1
^ ^ ^

```

### 2.

`n = 6, k = 5`

```
     ^    //Non-Decorated
    ^ ^
   ^ ^ ^
  ^ ^ ^ ^
 ^ ^ ^ ^ ^
^ ^ ^ ^ ^ ^

     ^    //Decorated
    1 2
    ^ ^
   3 4 5
   ^ ^ ^
  1 2 3 4
  ^ ^ ^ ^
 5 1 2 3 4
 ^ ^ ^ ^ ^
5 1 2 3 4 5
^ ^ ^ ^ ^ ^

```

### 3.

`n = 5, k = 1`

```
    ^
   ^ ^
  ^ ^ ^
 ^ ^ ^ ^
^ ^ ^ ^ ^

    ^
   1 1
   ^ ^
  1 1 1
  ^ ^ ^
 1 1 1 1
 ^ ^ ^ ^
1 1 1 1 1
^ ^ ^ ^ ^

```

This is so the shortest code wins! Have fun and good luck!

# Answer
> 46 votes
# C# 226 221 Bytes

*Saved 5 Bytes thanks to @Mukul Kumar and @aloisdg*

Golfed:

```
string C(int n,int k){string o="",x;int j=1,i=1,m;for(;i<=n;i++){o+=string.Concat(Enumerable.Repeat("^ ",i)).PadLeft(n+i)+"\n";m=0;x="";if(i<n){while(m<i+1){if(j>k)j=1;x+=j+++" ";m++;}o+=x.PadLeft(n+i+1)+"\n";}}return o;}

```

Ungolfed:

```
public string C(int n, int k, WifeMode wifeMode = WifeMode.Maniacal)
{
  string o = "",x;
  int j = 1,i=1,m;

  for (; i <= n; i++)
  {
    o += string.Concat(Enumerable.Repeat("^ ", i)).PadLeft(n+i) + "\n";

    m = 0;
    x = "";

    if (i < n)
    {
      while (m < i + 1)
      {
        if (j > k) j = 1;
        x += j++ + " ";
        m++;
      }

      o += x.PadLeft(n + i + 1) + "\n";
    }
  }

  return o;
}

```

Testing:

```
Console.Write(new ChristmasTreeDecorating().C(20, 9));

                   ^
                  1 2
                  ^ ^
                 3 4 5
                 ^ ^ ^
                6 7 8 9
                ^ ^ ^ ^
               1 2 3 4 5
               ^ ^ ^ ^ ^
              6 7 8 9 1 2
              ^ ^ ^ ^ ^ ^
             3 4 5 6 7 8 9
             ^ ^ ^ ^ ^ ^ ^
            1 2 3 4 5 6 7 8
            ^ ^ ^ ^ ^ ^ ^ ^
           9 1 2 3 4 5 6 7 8
           ^ ^ ^ ^ ^ ^ ^ ^ ^
          9 1 2 3 4 5 6 7 8 9
          ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
         1 2 3 4 5 6 7 8 9 1 2
         ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
        3 4 5 6 7 8 9 1 2 3 4 5
        ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
       6 7 8 9 1 2 3 4 5 6 7 8 9
       ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
      1 2 3 4 5 6 7 8 9 1 2 3 4 5
      ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
     6 7 8 9 1 2 3 4 5 6 7 8 9 1 2
     ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
    3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
    ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
   1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
   ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
  9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

```

*Edit: I had a play casting `int` to `ConsoleColor`... Tis the season :)*

*MerryChristmas.gif*

# Answer
> 13 votes
# 05AB1E, ~~29~~ ~~27~~ 24 bytes

Saved three bytes thanks to Adnan!

```
>GN„^ ×NÝNLO<+²%>ðý}\».c

>G                       For N in [1, ..., input[0]]
  N„^ ×                  Push a string of "^ " N times
       NÝ                Push [0, ..., N]
         NLO<            Compute the decoration offset, sum([1, ..., N])-1
             +           Add the offset value to each array cell
              ²%         Modulo input[1]
                >        Add 1 so that it is in range [1, k] instead of [0, k-1]
                 ðý      Join with spaces, now we have a string with the full decoration for the current layer
                   }     End for
                    \    Remove the last decoration
                     »   Join everything with newlines
                      .c Center all and implicitly display

```

Try it online!

# Answer
> 12 votes
## JavaScript (ES6), 97 bytes

It seems like your wife *really* is maniacal, so this doesn't include any leading or trailing newline, nor any leading or trailing space. :-)

```
f=(n,k,x,s=`^
`)=>n--?(p=' '.repeat(n)+s,x?p.replace(/\^/g,_=>x++%k+1)+p:p)+f(n,k,x||k,'^ '+s):''

```

### Demo

```
f=(n,k,x,s=`^
`)=>n--?(p=' '.repeat(n)+s,x?p.replace(/\^/g,_=>x++%k+1)+p:p)+f(n,k,x||k,'^ '+s):''

console.log(f(6, 5))
```

# Answer
> 8 votes
# C++ 214 - 13 - 3 - 1 -1 - 10 = 186 bytes

golfed

```
#define s std::cout<<
int f(int n,int k){int N=++n,K=0,i=0,I;for(;i<n;i++,N--){for(I=N;I--;)s' ';for(I=0;I++<i&&i-1;)s' '<<(K++%k)+1;s'\n';for(I=N;I--;)s' ';for(I=0;I++<i;)s" ^";s'\n';}}

```

Thanks @ cyoce for saving 1 byte.
Thanks @ conor for *chopping* it down to 186!

Ungolfed + copy&compile

```
#include<iostream>
#include<conio.h>

#define s(a) std::cout<<a;

int main()
{
    int n,N,k,K=0,i,I;
    std::cin>>n>>k;
    N=++n;
    for(i=0;i<n;i++,N--)
    {
        for(I=N;I--;)

            s(' ')

        for(I=0;I<i&&i-1;I++)

            s(' '<<(K++%k)+1)

        s('\n')

        for(I=N;I;I--)

            s(' ')

        for(I=0;I<i;I++)

            s(" ^")

        s('\n')

    }
    getch();//or any func to pause the console
}

```

# Answer
> 3 votes
## Python 2, 133 bytes

```
n,k=input()
d=-1
j=' '.join
for i in range(1,n+1):s=' '*(n-i);print(['',s+j(`x%k+1`for x in range(d,d+i))+'\n'][i>1]+s+j('^'*i));d+=i

```

# Answer
> 2 votes
**Clojure, 223 bytes**

My first go at golfing with Clojure:

```
(let[r repeat](defn d[n k](apply str(concat(r(dec n)\ )"^\n"(flatten(for[i(range 2(inc n))m[nil true]](concat(r(- n i)\ )(butlast(interleave(if m(r\^)(rest(iterate #(inc(mod % k))(dec(/(* i(dec i))2)))))(r i\ )))"\n")))))))

```

When called like `(println (str "\n" (d 6 5)))` a newline makes it nicer on REPL:

```
     ^
    1 2
    ^ ^
   3 4 5
   ^ ^ ^
  1 2 3 4
  ^ ^ ^ ^
 5 1 2 3 4
 ^ ^ ^ ^ ^
5 1 2 3 4 5
^ ^ ^ ^ ^ ^

```

Un-golfed:

```
(defn tree-row [n k index mode]
  (concat
    (repeat (- n index) \ ) ; Left padding
    (butlast ; Removing trailing space
      (interleave
        ; Either printing carets or numbers...
        (if mode
          (repeat \^)
          ; Using "rest" as the iteration starts from a large value
          ; from which the modulo has not been calculated yet.
          (rest (iterate #(inc (mod % k)) (dec (/ (* index (dec index)) 2)))))
        ; ...and interleaved with spaces
        (repeat index \ )))
    "\n"))

(defn decorate [n k]
  (apply str (concat
               (repeat (dec n) \ ) "^\n"
               (flatten (for [index (range 2 (inc n)) mode [nil true]]
                          (tree-row n k index mode))))))

```

I had some issues with lazy sequences and nested lists but I was able to save some characters by not repeating `repeat` ;) and using `\^` characters instead of `"^"` strings. I could also leave out surprisingly many spaces.

# Answer
> 1 votes
## Ruby 107 bytes

```
t=->(n,k){d=[*1..k]*n*n;o=0;(1..n).each{|b|s=' '*(n-b);b>1&&(puts(s+d[o,b].join(' '));o+=b);puts s+'^ '*b}}

```

Called like this

```
t.call(5,4)

```

Output:

```
    ^
   1 2
   ^ ^
  3 4 1
  ^ ^ ^
 2 3 4 1
 ^ ^ ^ ^
2 3 4 1 2
^ ^ ^ ^ ^

```

# Answer
> 1 votes
# C, 170 bytes

```
i=0;d,j,l;t(n,k){char s[20],r[20];d=k-2;l=n;for(;i++<n;){for(j=0;j<l;++j)s[j]=r[j]=32;for(j=n-i;j<l;j+=2){s[j]=94;r[j]=(++d%k)+49;}s[l]=r[l++]=0;if(i-1)puts(r);puts(s);}}

```

Call with:

```
int main()
{
   t(5,4);
}

```

As a bonus, here's a 4-bit binary version:

```
m=0;b(n,k){char*a="000100100011010001010110011110001001";char s[20],r[20];d=k*4-2;l=n;for(;m++<n;){for(j=0;j<l;++j)s[j]=r[j]=32;for(j=n-m;j<l;j+=2){s[j]=94;r[j]=a[++d%(k*4)];}s[l]=r[l++]=0;if(m-1)puts(r);puts(s);}}

```

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