title: Am I a 'Redivosite' Number?

text:
# Question
Title: Am I a 'Redivosite' Number?
<sub>*Redivosite is a portmanteau word invented for the sole purpose of this challenge. It's a mix of Reduction, Division and Composite.*</sub>

## Definition

Given an integer **N \> 6**:

* If **N** is prime, **N** is not a Redivosite Number.
* If **N** is composite:
    + repeatedly compute **N' = N / d + d + 1** until **N'** is prime, where **d** is the smallest divisor of **N** greater than 1
    + **N** is a Redivosite Number if and only if the final value of **N'** is a divisor of **N**

Below are the 100 first Redivosite Numbers (no OEIS entry at the time of posting):

```
14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835

```

## Examples

* **N = 13**: 13 is prime, so 13 is not a Redivosite Number
* **N = 32**: 32 / 2 + 3 = 19; 19 is not a divisor or 32, so 32 is not a Redivosite Number
* **N = 260**: 260 / 2 + 3 = 133, 133 / 7 + 8 = 27, 27 / 3 + 4 = 13; 13 is a divisor or 260, so 260 is a Redivosite Number

## Your task

* Given an integer **N**, return a truthy value if it's a Redivosite Number or a falsy value otherwise. (You may also output any two distinct values, as long as they're consistent.)
* The input is guaranteed to be larger than **6**.
* This is , so the shortest answer in bytes wins!

# Answer
> 9 votes
## Haskell, ~~91~~ ~~85~~ ~~83~~ ~~80~~ ~~75~~ 74 bytes

```
n#m=([n#(div m d+d+1)|d<-[2..m-1],mod m d<1]++[mod n m<1&&m<n])!!0
f x=x#x

```

Try it online!

```
f x=x#x                           -- call # with x for both parameters
n#m
         |d<-[2..m-1],mod m d<1   -- for all divisors d of m
    [n#(div m d+d+1)           ]  -- make a list of recursive calls to #,
                                  -- but with m set to m/d+d+1
   ++ [mod n m<1&&m<n]            -- append the Redivosite-ness of n (m divides n,
                                  -- but is not equal to n)
                           !!0    -- pick the last element of the list
                                  -- -> if there's no d, i.e. m is prime, the
                                  --    Redivosite value is picked, else the
                                  --    result of the call to # with the smallest d

```

Edit: -2 bytes thanks to @BMO, -3 bytes thanks to @H.PWiz and ~~-5~~ -6 bytes thanks to @Ørjan Johansen

# Answer
> 6 votes
# Husk, 14 bytes

```
?¬Ṡ¦ΩṗoΓ~+→Πpṗ

```

Try it online!

-3 thanks to H.PWiz.

# Answer
> 6 votes
# C (gcc), ~~94~~ 89 bytes

```
m,n;o(k){for(m=1;m++<k;)if(k%m<1)return m;}
F(N){for(n=N;m=o(n),m-n;n=n/m-~m);N=m<N>N%n;}

```

Try it online!

# Explanation

```
m,n;                  // two global integers
o(k){                 // determine k's smallest divisor
 for(m=1;m++<k;)      // loop through integers 2 to n (inclusive)
  if(k%m<1)return m;} // return found divisor
F(N){                 // determine N's redivosity
 for(n=N;             // save N's initial value
  m=o(n),             // calculate n's smallest divisor (no name clash regarding m)
  m-n;                // loop while o(n)!=n, meaning n is not prime
                      //  (if N was prime, the loop will never be entered)
  n=n/m-~m);          // redivosite procedure, empty loop body
 N=m<N>N%n;}          // m<N evaluates to 0 or 1 depending on N being prime,
                      //  N%n==0 determines whether or not N is divisible by n,
                      //  meaning N could be redivosite => m<N&&N%n==0
                      //  <=> m<N&&N%n<1 <=> m<N&&1>N%n <=> (m<N)>N%n <=> m<N>N%n

```

# Answer
> 4 votes
# Jelly, 14 bytes

```
ÆḌḊ
Ç.ịS‘µÇ¿eÇ

```

Try it online!

### How it works

```
ÆḌḊ         Helper link. Argument: k

ÆḌ          Yield k's proper (including 1, but not k) divisors.
  Ḋ         Dequeue; remove the first element (1).

Ç.ịS‘µÇ¿eÇ  Main link. Argument: n

     µ      Combine the links to the left into a chain.
      Ç¿    While the helper link, called with argument n, returns a truthy result,
            i.e., while n is composite, call the chain to the left and update n.
Ç             Call the helper link.
 .ị           At-index 0.5; return the elements at indices 0 (last) and 1 (first).
              This yields [n/d, d].
   S          Take the sum.
    ‘         Increment.
        Ç   Call the helper link on the original value of n.
       e    Test if the result of the while loop belongs to the proper divisors.

```

# Answer
> 4 votes
# Python 2, ~~97~~ 91 bytes

```
r=0;e=d=i=input()
while r-e:e=i;r=[j for j in range(2,i+1)if i%j<1][0];i=i/r-~r
d%e<1<d/e<q

```

Try it online!

Outputs via exit code.

### Ungolfed:

```
r = 0                             # r is the lowest divisor of the current number,
                                  # initialized to 0 for the while loop condition.
e = d = i = input()               # d remains unchanged, e is the current number
                                  # and i is the next number.
while r != e:                     # If the number is equal to its lowest divisor,
                                  # it is prime and we need to end the loop.
    e = i                         # current number := next number
    r = [j for j in range(2, i+1) # List all divisors of the number in the range [2; number + 1)
         if i%j < 1][0]           # and take the first (lowest) one.
    i = i/r+r+1                   # Calculate the next number.
                                  # We now arrived at a prime number.
print d%e == 0 and d != e         # Print True if our current number divides the input
                                  # and is distinct from the input.
                                  # If our current number is equal to the input,
                                  # the input is prime.

```

Try it online!

# Answer
> 3 votes
# 05AB1E, ~~17~~ 16 bytes

```
[Dp#Òć©sP+>]Ö®p*

```

Try it online!

**Explanation**

```
[                  # start loop
 Dp#               # break if current value is prime
    Ò              # get prime factors of current value
     ć©            # extract the smallest (d) and store a copy in register
       sP          # take the product of the rest of the factors
         +>        # add the smallest (d) and increment
           ]       # end loop
            Ö      # check if the input is divisible by the resulting prime
             ®p    # check if the last (d) is prime (true for all composite input)
               *   # multiply

```

# Answer
> 2 votes
# Pyth, 20 bytes

```
<P_QiI.WtPHh+/ZKhPZK

```

**Try it here!**

## How it works

```
iI.WtPHh+/ZKhPZK || Full program.

  .W             || Functional while. It takes two functions as arguments, A and B.
                 || While A(value) is truthy, turn the value into B(value). The
                 || starting value is the input.
    tPH          || First function, A. Takes a single argument, H.
     PH          || .. The prime factors factors of H.
    t            || .. Tail (remove first element). While truthy (H is composite):
       h+/ZKhPZK || The second function, B. Takes a single argument, Z:
         /Z      || .. Divide Z, by:
           KhP   || .. Its lowest prime factor, and assign that to K.
       h         || .. Increment.
        +      K || And add K.
iI               || Check if the result (last value) divides the input.

```

And the first 4 bytes (`<P_Q`) just check if the input is not prime.

With help from Emigna, I managed to save 3 bytes.

# Answer
> 2 votes
# Python 3, 149 bytes

```
def f(N):
	n=N;s=[0]*-~N
	for p in range(2,N):
		if s[p]<1:
			for q in range(p*p,N+1,p):s[q]=s[q]or p
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

```

Try it online!

Using a sieve approach. Should be fast (`O(N log log N)` = time complexity of the sieve of Eratosthenes) even with large `N` (but stores `O(N)` integers in memory)

Note:

* It can be proven that all intermediate values of `n` does not exceed `N`, and for `N > 7` `p` can be in `range(2,N)` instead of `range(2,N+1)` for sieving.
* `/` doesn't work, `//` must be used, because of list index.
* Storing `range` into another variable doesn't help, unfortunately.

Explanation:

* `-~N` == `N+1`.
* At first, the array `s` is initialized with `N+1` zeroes (Python is 0-indexing, so the indices are `0..N`)
* After initialization, `s[n]` is expected to be `0` if `n` is a prime, and `p` for `p` the minimum prime which divides `n` if `n` is a composite. `s[0]` and `s[1]` values are not important.
* For each `p` in range `[2 .. N-1]`:

+ If `s[p] < 1` (that is, `s[p] == 0`), then `p` is a prime, and for each `q` being a multiple of `p` and `s[q] == 0`, assign `s[q] = p`.
* The last 2 lines are straightforward, except that `n//s[n]-~s[n]` == `(n // s[n]) + s[n] + 1`.

---

# Python 3, 118 bytes

```
def f(N):
	n=N;s=[0]*-~N
	for p in range(N,1,-1):s[2*p::p]=(N-p)//p*[p]
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

```

Try it online!

At the cost of slightly worse performance. (This one runs in `O(N log N)` time complexity, assume reasonable implementation of Python slices)

---

The equivalent full program is 117 bytes.

# Answer
> 1 votes
# Haskell, 110 bytes

```
f n|mod(product[1..n-1]^2)n>0=1<0|1>0=n`mod`u n<1
u n|d<-[i|i<-[2..],n`mod`i<1]!!0=last$n:[u$n`div`d+d+1|d/=n]

```

Try it online!

Not very happy...

# Answer
> 1 votes
# Octave, 92 bytes

```
function r=f(n)k=n;while~isprime(k)l=2:k;d=l(~mod(k,l))(1);k=k/d+d+1;end;r=~mod(n,k)&k<n;end

```

Try it online!

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

```
{(0=n|⍵)∧⍵>n←{⍬≢k←o/⍨0=⍵|⍨o←2↓⍳⍵:∇1+d+⍵÷d←⌊/k⋄⍵}⍵}

```

Try it online!

# Answer
> 1 votes
# Japt, ~~25~~ 24 bytes

I fear I may have gone in the wrong direction with this but I've run out of time to try a different approach.

Outputs `0` for false or `1` for true.

```
j ?V©vU :ßU/(U=k g)+°UNg

```

Try it

# Answer
> 0 votes
# , 35 bytes

```
(~:*0=|~)(1+d+]%d=.0{q:)^:(0&p:)^:_

```

Try it online!

The minimum divisor being the first prime factor was stolen from @Dennis's Jelly solution (previously I was using `<./@q:`).

There should be a better way to do the iteration, but I can't seem to find it. I thought of avoiding doing the primality test (`^:(0&p:)`) and instead using adverse but it seems like that will be a bit longer since you'll need a `_2{` and some changes which might not give a net reduction.

I really feel like there must be a way to avoid having parens around the primality check, too.

# Explanation (expanded)

```
(~: * 0 = |~)(1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Input: N
             (1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Find the final N'
                                       ^:        ^:_  Do while
                                           0&p:       N is not prime
                                   q:                 Get prime factors (in order)
                               0 {                    Take first (smallest divisor)
                          d =.                        Assign this value to d
             1 + d + ] %  d                           Compute (N/d) + 1 + d
(~: * 0 = |~)                                        Is it redivosite?
      0 = |~                                          N = 0 (mod N'), i.e. N'|N
    *                                                 And
 ~:                                                   N =/= N', i.e. N is not prime

```

# Answer
> 0 votes
# Perl 5, 291+1(-a) = 292 bytes

Darn Perl for not having a native prime checker.

```
use POSIX;&r($_,$_);
sub p{$n=shift;if($n<=1){return;}if($n==2||$n==3){return 1;}if($n%2==0||$n%3==0){return;}for(5..ceil($n/2)){if($n%$_==0){return;}}return 1;}
sub r{$n=shift;$o=shift;if(&p($n)){print $o%$n==0&&$n!=$o?1:0;last;}for(2..ceil($n/2)){if($n%$_==0){&r(($n/$_)+$_+1, $o);last;}}}

```

Ungolfed version,

```
use POSIX;
&r($_,$_);
sub p{
    my $n=shift;
    if($n<=1){
        return;
    }
    if($n==2||$n==3){
        return 1;
    }
    if($n%2==0||$n%3==0){
        return;
    }
    for(5..ceil($n/2)){
        if($n%$_==0){
            return;
        }
    }
    return 1;
}
sub r{
    my $n=shift;
    my $o=shift;
    if(&p($n)){
        print $o%$n==0&&$n!=$o ? 1 : 0;
        last;
    }
    for(2..ceil($n/2)){
        if($n%$_==0){
            &r(($n/$_)+$_+1, $o);
            last;
        }
    }
}

```

Try it online!

# Answer
> 0 votes
# APL NARS, 43 chars, 85 bytes

```
{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}

```

(hoping that it converge for all number\>6) test:

```
h←{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}
v←⍳100
v,¨h¨v
   1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0  10 0  11 0
   12 0  13 0  14 1  15 0  16 0  17 0  18 0  19 0  20 0
   21 0  22 0  23 0  24 0  25 0  26 0  27 0  28 0  29 0
   30 0  31 0  32 0  33 0  34 0  35 0  36 0  37 0  38 0
   39 0  40 0  41 0  42 1  43 0  44 1  45 0  46 0  47 0
   48 0  49 1  50 0  51 0  52 0  53 0  54 0  55 0  56 0
   57 0  58 0  59 0  60 0  61 0  62 0  63 0  64 0  65 0
   66 1  67 0  68 0  69 0  70 1  71 0  72 0  73 0  74 0
   75 0  76 0  77 0  78 0  79 0  80 0  81 0  82 0  83 0
   84 0  85 0  86 0  87 0  88 0  89 0  90 0  91 0  92 0
   93 0  94 0  95 0  96 0  97 0  98 0  99 0  100 0

```

The idea of using 2 anonymous functions I get to other Apl solution.

```
 {(⍵≤60)∨π⍵:0⋄ -- if arg ⍵ is prime or <=6 return 0
  ⍵{1=⍴t←π⍵:0=⍵|⍺⋄ -- if list of factors ⍵ has length 1 (it is prime)
                    -- then return ⍺mod⍵==0
  ⍺∇1+↑t+⍵÷↑t}⍵}   -- else recall this function with args ⍺ and 1+↑t+⍵÷↑t

```

# Answer
> 0 votes
# Wolfram Language (Mathematica), 64 bytes

Straightforward implementation using recursive pattern replacement

(replacing "\\\[Divides\]" with the "∣" symbol saves 7 bytes)

```
(g=!PrimeQ@#&)@#&&(#//.x_/;g@x:>x/(c=Divisors[x][[2]])+c+1)\[Divides]#&

```

Try it online!

# Answer
> 0 votes
# Clean, ~~128~~ ~~117~~ 114 bytes

```
import StdEnv
@n#v=hd[p\\p<-[2..]|and[gcd p i<2\\i<-[2..p-1]]&&n rem p<1]
|v<n= @(n/v+v+1)=n
?n= @n<n&&n rem(@n)<1

```

Try it online!

# Answer
> 0 votes
# Pyt, 44 bytes

```
←⁻0`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹ṗ⇹3Ș⊽

```

See the code below for an explanation - the only differences are (1) that N is decremented before to account for the incrementation at the beginning of the loop, and (2) it uses NOR instead of OR.

Try it online!

---

I made this before I re-read the question and noticed that it only wanted a true/false.

# Pyt, 52 bytes

```
60`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹Đṗ⇹3Ș∨ł⇹Đƥ⇹ŕ1ł

```

Prints an infinite list of Redivosite numbers.

Explanation:

```
6                                                            Push 6
 0                                                           Push unused character
  `                   ł                     ł      ł         Return point for all three loops
   ŕ                                                         Remove top of stack
    ⁺                                                        Increment top of stack (n)
     ĐĐ                                                      Triplicate top of stack (n)
       ϼ↓                                                    Get smallest prime factor of n (returns 1 if n is prime)
         Đ                                                   Duplicate top of stack
          3Ș⇹                                                Manipulate stack so that the top is (in descending order): [d,(N,N'),d]
             ÷+⁺                                             Calculates N'=(N,N')/d+d+1
                Đṗ¬                                          Is N' not prime?
                   ⇹⁻⇹                                       Decrement N' (so the increment at the beginning doesn't change the value), and keep the boolean on top - end of innermost loop (it loops if top of stack is true)
                       ŕ                                     Remove top of stack
                        á                                    Convert stack to array
                         Đ                                   Duplicate array
                          0⦋Đ                                Get the first element (N)
                             ↔ĐŁ⁻⦋                           Get the last element ((final N')-1)
                                  ⁺                          Increment to get (final N')
                                   |¬                        Does N' not divide N?
                                     ⇹Đṗ                     Is N prime?
                                        ⇹3Ș∨                 Is N prime or does N' not divide N? - end of second loop (loops if top of stack is true)
                                             ⇹Đƥ⇹ŕ           Print N, and reduce stack to [N]
                                                  1          Push garbage (pushes 1 so that the outermost loop does not terminate)

```

Try it online!

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


title: Transposes and Diagonals

text:
# Question
Title: Transposes and Diagonals
For this challenge, you should write a program or function which outputs the diagonals of a given square matrix. However, if you transpose the rows and columns of your solution's source code, it should instead become a program or function which returns the matrix's antidiagonals. Read on for specifics...

## Rules

* The source code of your solution is considered as a 2D grid of characters, separated by a standard newline of your choice (linefeed, carriage return, or a combination of both).
* No line in your source code may be longer than the previous one. Here are some examples of valid layouts:

```
###
###
###

```

```
########
#######
###
###
#

```

And here is an example of an invalid layout (as the third line is longer than the second):

```
######
####
#####
###

```
* Your two solutions should be each others' transpose, that is you should obtain one from the other by swapping rows and columns. Here are two valid pairs:

```
abc
def
ghi

```

```
adg
beh
cfi

```

And

```
print 10
(~^_^)~
foo
bar
!

```

```
p(fb!
r~oa
i^or
n_
t^
 )
1~
0

```

Note that spaces are treated like any other characters. In particular, trailing spaces are significant as they might not be trailing spaces in the transpose.
* Each solution should be a program or function which takes a non-empty square matrix of single-digit integers as input. One solution should output a list of all diagonals of the matrix and the other should output a list of all antidiagonals. You may use any reasonable, unambiguous input and output formats, but they must be identical between the two solutions (this also means they either have to be both functions or both programs).
* Each diagonal runs from the top left to the bottom right, and they should be ordered from top to bottom.
* Each antidiagonal runs from the bottom left to the top right, and they should be ordered from top to bottom.

## Scoring

To encourage solutions that are as "square" as possible, the primary score is the number of rows or the number of columns of your solution, whichever is *larger*. Less is better. Ties are broken by the number of *characters* in the solution, not counting the newlines. Again, less is better. Example:

```
abcd
efg
h

```

This and its transpose would have a primary score of **4** (as there are 4 columns) and a tie-breaking score of **8** (as there are 8 non-newline characters). Please cite both values in the header of your answer.

## Test Cases

The actual task performed by the two solutions shouldn't be the primary challenge here, but here are two examples to help you test your solutions:

```
Input:
1 2 3
4 5 6
7 8 9
Diagonals:
3
2 6
1 5 9
4 8
7
Antidiagonals:
1
4 2
7 5 3
8 6
9

Input:
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
Diagonals:
0
1 1
0 0 0
1 1 1 1
0 0 0
1 1
0
Antidiagonals:
1
0 0
1 1 1
0 0 0 0
1 1 1
0 0
1

```

# Answer
> 19 votes
# Javascript, score ~~20~~ 14, (~~258~~ 176 non-newline characters)

```
///mmm()mu[=+r
///=.av=a,pr"=
///> p,>px=[ [
m=>//(yv()xp"]
m. ////.(=+]+)
map((////>y?u&
v,y)=>v//r]r:&
.map((u,x//[ur
)=>r[p=m.//p)
length-1-//],
x+y]=r[p]////
?r[p]+" "+u//
:u),r=[])&&r

```

and

```
///mmmv.)lx?:
///=.a,m=e+ru
///> pya>ny[)
m=>//()prg]p,
m. //(=([t=]r
map(//>(phr+=
(v,y//vu=-["[
)=>v.//,m1p ]
map((//x.-]")
u,x)=>r////+&
[p=x+y]////u&
=r[p]?r[p]//r
+" "+u:u),//
r=[])&&r

```

Example code snippet:

```
f=

///mmm()mu[=+r
///=.av=a,pr"=
///> p,>px=[ [
m=>//(yv()xp"]
m. ////.(=+]+)
map((////>y?u&
v,y)=>v//r]r:&
.map((u,x//[ur
)=>r[p=m.//p)
length-1-//],
x+y]=r[p]////
?r[p]+" "+u//
:u),r=[])&&r

console.log(f([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]))
```

and

```
f=

///mmmv.)lx?:
///=.a,m=e+ru
///> pya>ny[)
m=>//()prg]p,
m. //(=([t=]r
map(//>(phr+=
(v,y//vu=-["[
)=>v.//,m1p ]
map((//x.-]")
u,x)=>r////+&
[p=x+y]////u&
=r[p]?r[p]//r
+" "+u:u),//
r=[])&&r

console.log(f([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]))
```

# Answer
> 8 votes
# MATL, score 10 (100 non-newline characters)

```
%P!
  Q&%
  TXd!
  %d
     P!
      "@%
       Xz
      %z
         q
         !

```

There are 10 lines of 10 characters (note the trailing spaces).

The above code produces the diagonals. Try it online!

The transposed version produces the anti-diagonals. Try it online!

## Explanation

Note that

* `%` is a comment symbol, which causes the rest of the line to be ignored.
* Two-char functions like `Xd` cannot be split into an `X` and a `d` in consecutive lines.

### Original code

The original code, linearized and without the commented part, is

```
Q&TXd!P!"@Xzq!

```

which works as follows:

```
Q      % Implicit input. Add 1 to each entry to make them positive
&      % This modifes default inputs/ouputs of next function, which is Xd
       % Specifically, it specifies 2 inputs and 1 ouput
T      % Push true
Xd     % Diagonals of matrix. With second input true, it gives all diagonals,
       % starting from below. The columns are arranged as columns of a matrix,
       % padding with zeros
!P!    % Flip horizontally. This is to produce the correct display order
"      % For each column
  @    %   Push current column
  Xz   %   Remove zeros
  q    %   Subtract 1
  !    %   Transpose into a row
       % Implicit end. Implicit display of stack contents

```

### Transposed code

The transposed code, linearized, is

```
P!QT&Xd!P!"@Xzq!

```

which has the following two differences compared to the original code:

* `T` and `&` are swapped. This has no effect, because `T` is a literal, not a function, so it doesn't intercept the `&` specification.
* `P!` is added at the begining.

The added code modifies the input matrix so that the diagonals of the modified matrix are the anti-diagonals of the input:

```
P      % Implicit input. Flip vertically
!      % Transpose

```

# Answer
> 7 votes
# Jelly, Score 7, 49 non-newline bytes

# Diagonal printing program

```
......U
......Œ
......D
......ṙ
......L
......Ṛ
ŒDṙLṚUU

```

Try it online!

# Anti-diagonal-printing Program

```
......Œ
......D
......ṙ
......L
......Ṛ
......U
UŒDṙLṚU

```

Try it online!

## Older Answer(Unordered Output), Score 3, 6 non-newline bytes

## Diagonal-printing program

```
UU
UŒ
ŒD

```

Try it online!

## Anti-diagonal printing program

```
UUŒ
UŒD

```

Try it online!

# Answer
> 6 votes
# Jelly, score 4 (12 characters)

previous scores: 5 (16 characters), 4 (16 characters)

### Original

```
ŒDṙṚ
D  ñ
ṙLñL

```

Try it online!

### Transpose

```
ŒDṙ
D L
ṙ ñ
ṚñL

```

Try it online!

## Background

### Diagonals

The straightforward way of obtaining the diagonals (topmost to bottommost) of a square matrix is as follows.

```
ŒDṙLṚ

```

For an input matrix **M**, `ŒD` lists **M**'s diagonals, starting with the main diagonal and moving upwards.

For the input

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

```

this yields

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

```

`ṙL` then computes **M**‘s length with `L` and rotates the result **length(M)** units to the left.

For our example, the length is **3** and we get

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

```

Finally,  reverses the order of the diagonals, returning

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

```

for our example input.

### Anti-diagonals

The same building blocks can be used to obtain the anti-diagonals (again, topmost to bottommost) of a square matrix.

```
ṚŒDṙL

```

For an input matrix **M**,  first reverses the order of the rows.

For the input

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

```

this yields

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

```

As before, `ŒDṙL` generates the diagonals (bottommost to topmost) of the result.

For our example, this returns

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

```

as desired.

## How it works

In Jelly, each line defines a *link* (function). In particular, the last line defines the *main link*, which is executed when the program starts.

Other links must be called. This answer uses `ñ`, which executes the link below dyadically. `ñ` wraps around, so when it is called from the main link, it executes the link on the first line.

### Original

The main link

```
ṙLñL

```

takes an input matrix **M**, computes its length with `L`, then rotates the input **length(M)** units to the left with  (note that this doesn't alter **M**), and finally calls the first link with the result (**M**) and **length(M)** as arguments.

The first link

```
ŒDṙṚ

```

computes the diagonals of **M** with `ŒD` (as seen in the previous section), rotates the result **length(M)** units to the left with , then reverses the order of the result with .

The second link is never called.

### Transpose

The main link

```
 ṚñL

```

takes an input matrix **M** and computes its reverse with . It then computes the length of **M** with `L` and calls the first link with arguments **reverse(M)** and **length(M)**.

The first link

```
ŒDṙ

```

then computes the diagonals of **reverse(M)** with `ŒD` (as seen in the previous section), and finally rotates the result **length(M)** units to the left with .

The remaining links are never called.

# Answer
> 5 votes
# Husk, ~~7~~ ~~9~~ 4 characters, score ~~4~~ 3

```
∂T
m
↔

```

Try it online!

-4 characters thanks to BMO.

# Answer
> 5 votes
# R, score ~~14 13~~ 11 (~~99~~ 95 non-newline characters)

Thanks to @Giuseppe for improving the score by 1. Shaved off a few characters by making use of redundancies in the transpositions. Currently the best score for a non-golfing language!

```
######`,scr
`::`(#:fpoo
pryr,#:)llw
f)(###`(i((
split (#tmm
p,col(p#())
)+row#r#m-)
(p)))#y#,#)
######r

```

And transposed:

```
#`pfsp)(#
#:r)p,+p#
#:y(lcr)#
#`r#ioo)#
#(,#tlw)#
#### (###
`::`(pryr
,f)(####
split(m,
col(m)-#
row(m)))

```

Try it online!

---
Tags: code-challenge, source-layout, matrix
---


title: Strategic Vanishers

text:
# Question
Title: Strategic Vanishers
> This post is loosely inspired by this mathoverflow post.

A Vanisher is any pattern in Conway's Game of life that completely disappears after one step. For example the following pattern is a size 9 Vanisher.

An interesting property of Vanishers is that *any pattern* can be made into a vanishing one by simply adding more live cells. For example the following pattern can be completely enclosed into a vanishing pattern like so

However we can make that pattern into a Vanisher by adding even fewer live cells.

Your task is to write a program that does this task for us. That is given a pattern as input find and output a vanishing pattern containing the input. You do not necessarily have to find the optimal pattern just a pattern that works.

## Scoring

To score your program you will have to run it on all of the size 6 polyplets (not double counting symmetrically equivalent cases). Here is a pastebin containing each polyplet on its own line. There should be 524 of them total. They are represented as a list of six coordinates (`(x,y)` tuples) each being the location of a live cell.

Your score will be the total number of new cells added to make all of these polyplets into Vanishers.

### Ties

In the case of ties I will provide a list of the size 7 polyplets for the programs to be run on.

## IO

I would like IO to be pretty flexible you can take input and output in reasonable formats however you are probably going to want to take input in the same format as the raw input data I provided. Your format should be consistent across multiple runs.

## Timing

Your program should run in a reasonable amount of time (approx \<1 day) on a reasonable machine. I'm not going to really be enforcing this too much but I'd prefer if we would all play nice.

# Answer
> 5 votes
# Python + Z3, score = 3647

Runs in 14 seconds on my eight core system.

```
from __future__ import print_function

import ast
import multiprocessing
import sys
import z3

def solve(line):
    line = ast.literal_eval(line)
    x0, x1 = min(x for x, y in line) - 2, max(x for x, y in line) + 3
    y0, y1 = min(y for x, y in line) - 2, max(y for x, y in line) + 3
    a = {(x, y): z3.Bool('a_{}_{}'.format(x, y)) for x in range(x0, x1) for y in range(y0, y1)}
    o = z3.Optimize()
    for x in range(x0 - 1, x1 + 1):
        for y in range(y0 - 1, y1 + 1):
            s = z3.Sum([
                z3.If(a[i, j], 1 + ((i, j) != (x, y)), 0)
                for i in (x - 1, x, x + 1) for j in (y - 1, y, y + 1) if (i, j) in a
            ])
            o.add(z3.Or(s < 5, s > 7))
    o.add(*(a[i, j] for i, j in line))
    o.minimize(z3.Sum([z3.If(b, 1, 0) for b in a.values()]))
    assert o.check() == z3.sat
    m = o.model()
    return line, {k for k in a if z3.is_true(m[a[k]])}

total = 0
for line, cells in multiprocessing.Pool().map(solve, sys.stdin):
    added = len(cells) - len(line)
    print(line, added)
    x0, x1 = min(x for x, y in cells), max(x for x, y in cells) + 1
    y0, y1 = min(y for x, y in cells), max(y for x, y in cells) + 1
    for y in range(y0, y1):
        print(''.join('#' if (x, y) in line else '+' if (x, y) in cells else ' ' for x in range(x0, x1)))
    total += added
print('Total:', total)

```

Full output

---
Tags: code-challenge, test-battery, game-of-life, optimized-output
---


title: Minimum number of Jumps

text:
# Question
Title: Minimum number of Jumps
Given a sequence of numbers, find the minimum number of jumps to go from the starting position to the end and come back to the starting position again.

Each element of the sequence denotes the maximum number of moves that one can move from that position.

At any position, you can make a jump of at max k moves, where k is the value stored at that position. After reaching the end, you can use only those positions for jumping which have not been used previously for jumping.

The input will be given as a sequence of numbers separated by single-spaces. Output should be a single number which is the minimum number of jumps used. If its not possible to go to the end and come back to the starting position, then print **-1**

**Input:**

2 4 2 2 3 4 2 2

**Output:**

6 (3 to reach end and 3 to come back)

**Input**

1 0

**Output**

-1

**Note**

* Assume all the numbers of the sequence are non-negative

**EDIT 1**

The line "Thus, it should be clear that one can always jump from the last position." might be confusing, so I removed it from the question. It will have no effect on the question.

**Winning Criteria :**

The winner will be the one with the shortest code.

# Answer
> 4 votes
# Mathematica, ~~197~~ 193 chars

Brute force.

```
Min[Length/@Select[Join[{1},#,{n},Reverse@#2]&@@@Tuples[Subsets@Range[3,n=Length[i=FromDigits/@StringSplit@InputString[]]]-1,2],{}⋃#==Sort@#∧And@@Thread[i[[#]]≥Abs[#-Rest@#~Append~1]]&]]/.∞->-1

```

# Answer
> 4 votes
## APL(Dyalog), 116

```
f←{{⊃,/{2>|≡⍵:⊂⍵⋄⍵}¨⍵}⍣≡1{(⍴⍵)≤y←⊃⍺:⍵⋄⍵[y]=0:0⋄x←⍵⋄x[y]←0⋄∇∘x¨,∘⍺¨y+⍳y⌷⍵},⍵}
{0≡+/⍵:¯1⋄(⌊/+/0=⍵)-+/0=x}↑⊃,/f¨⌽¨f x←⎕

```

**Test cases**

```
      2 4 2 2 3 4 2 2
6
      1 0
¯1
      1 1 1 1
¯1
      3 1 2 0 4
3
      1
0

```

---

**Approach**

The approach is a brute force search using a recursive function.

Starting from position 1, set value at the current position to 0 and generate an array of the positions which can be jumped to from the current position. Pass the new position and the modified array to itself. Base cases are when the value at the current position is 0 (can't jump) or reaching the end.

Then, for each of the array generated, reverse it and do the search again. Because jumped positions are set to 0, we can't jump from there again.

For those array which we reached the end, find the ones which have the minimum number of 0's. Subtracting from it the number of 0's in the initial array gives the actual number of jumps performed.

# Answer
> 3 votes
# Mathematica 351

\[Note: This is not yet fully golfed; Also, the input needs to be adjusted to fit the required format. And the no-jumping-on-the-same-position-twice rule needs to be implemented. There are also some code formatting issues that need addressing. But it's a start.\]

A graph is constructed with nodes corresponding to each position, i.e. each input digit representing a jump. `DirectedEdge[node1, node2]` signifies that it is possible to jump from node1 to node 2. Shortest paths are found from start to end and then from end to start.

```
f@j_:=
(d={v=FromCharacterCode/@(Range[Length[j]]+96),j}\[Transpose];
w[n_,o_:"+"]:={d[[n,1]],FromCharacterCode/@(ToCharacterCode[d[[n,1]]][[1]]+Range[d[[n,2]]]
If[o=="+",1,-1])};

y=Graph[Flatten[Thread[DirectedEdge[#1,#2]]&@@@(Join[w[#]&/@Range[8],w[#,3]&/@Range[8]])]];

(Length[Join[FindShortestPath[y,v[[1]],v[[-1]]],FindShortestPath[y,v[[-1]],v[[1]]]]]-2)
/.{0-> -1})

```

**Usage**

```
f[{2,4,2,2,3,4,2,2}]
f[{3,4,0,0,6}]
f[{1,0}]

```

> 6
> 3
> -1

# Answer
> 3 votes
# Python 304

I think this new approach solves (I hope!) all the issues regarding the \[2,0\] case and similar:

In this version the input sequence is traversed (if possible) until the end and then we start the process again with the reversed sequence. Now we can garantee that for every valid solution one of the the jumps lands on the last element.

```
## Back and forward version

# Changed: now the possible jumps from a given L[i] position
# are at most until the end of the sequence
def AvailableJumps(L,i): return range(1,min(L[i]+1,len(L)-i))

# In this version we add a boolean variable bkw to keep track of the
# direction in which the sequence is being traversed
def Jumps(L,i,n,S,bkw):
    # If we reach the end of the sequence...
    # ...append the new solution if going backwards
    if (bkw & (i == len(L)-1)):
            S.append(n)
    else:
        # ...or start again from 0 with the reversed sequence if going forward
        if (i == len(L)-1):
            Jumps(L[::-1],0,n,S,True)
        else:
            Laux = list(L)
            # Now we only have to disable one single position each time
            Laux[i] = 0
            for j in AvailableJumps(L,i):
                Jumps(Laux,i+j,n+1,S,bkw)

def MiniJumpBF(L):
    S = []
    Jumps(L,0,0,S,False)
    return min(S) if (S) else -1

```

These are the golfed versions:

```
def J(L,i,n,S,b):
    if (i == len(L)-1):
        S.append(n) if b else J(L[::-1],0,n,S,True)
    else:
        L2 = list(L)
        L2[i] = 0
        for j in range(1,min(L[i]+1,len(L)-i)):
            J(L2,i+j,n+1,S,b)
def MJ(L):
    S = []
    J(L,0,0,S,False)
    return min(S) if (S) else -1

```

And some examples:

```
MJ( [2, 4, 2, 2, 3, 4, 2, 2] ) -->  6
MJ( [0, 2, 4, 2, 2, 3, 4, 2, 2] ) -->  -1
MJ( [3, 0, 0, 1, 4] ) -->  3
MJ( [2, 0] ) -->  -1
MJ( [1] ) -->  0
MJ( [10, 0, 0, 0, 0, 0, 10, 0, 0, 0, 10, 0, 0, 0, 0, 0, 10] ) -->  4
MJ( [3, 2, 3, 2, 1] ) -->  5
MJ( [1, 1, 1, 1, 1, 1, 6] ) -->  7
MJ( [7, 1, 1, 1, 1, 1, 1, 7] ) -->  2

```

# Answer
> 3 votes
## R - 195

```
x=scan(nl=1)
L=length
n=L(x)
I=1:(2*n-1)
P=n-abs(n-I)
m=0
for(l in I)if(any(combn(I,l,function(i)all(P[i[c(1,k<-L(i))]]==1,n%in%i,L(unique(P[i]))==k-1,diff(i)<=x[P][i[-k]])))){m=l;break}
cat(m-1)

```

Simulation:

```
1: 2 4 2 2 3 4 2 2   # everything after 1: is read from stdin
6                    # output is printed to stdout

1: 1 0               # everything after 1: is read from stdin
-1                   # output is printed to stdout

```

De-golfed:

```
x = scan(nlines = 1)       # reads from stdin
n = length(x)
index    = 1:(2*n-1)       # 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
position = c(1:n, (n-1):1) # 1  2  3  4  5  6  7  8  7  6  5  4  3  2  1
value    = x[position]     # 2  4  2  2  3  4  2  2  2  4  3  2  2  4  2
is_valid_path = function(subindex) {
  k = length(subindex)
  position[subindex[1]] == 1                  & # starts at 1
  position[subindex[k]] == 1                  & # ends at 1
  n %in% subindex                             & # goes through n (end of vector)
  length(unique(position[subindex])) == k - 1 & # visits each index once (except 1)
  all(diff(subindex) <= value[subindex[-k]])
}
min_length = 0
for(len in index) {
  valid_paths = combn(index, len, FUN = is_valid_path)
  if (any(valid_paths)) {
    min_length = len
    break
  }
}
min_jumps = min_length - 1
cat(min_jumps)             # outputs to stout

```

# Answer
> 2 votes
# Python 271

this is my solution:

```
## To simplify the process we unfold the forward-backward sequence
def unfold(L): return L + L[:-1][::-1]

## Possible jumps from a given L[i] position
def AvailableJumps(L,i): return range(1,L[i]+1)

# To disable a used position, in the forward and backward sites
# (the first one is not really necessary)
def Use(L,i):
    L[i] = 0
    L[ len(L) - i - 1] = 0
    return L

def Jumps(L,i,n,S):
    if (i >= len(L)-1):
        S.append(n)
    else:
        Laux = list(L)
        Use(Laux,i)
        for j in AvailableJumps(L,i):
            Jumps(Laux,i+j,n+1,S)

def MiniJump(L):
    S = []
    Jumps(unfold(L),0,0,S)
    return min(S) if (S) else -1

```

Examples:

```
print MiniJump([2,4,2,2,3,4,2,2])
print MiniJump([0,2,4,2,2,3,4,2,2])

```

And these are the (partially by now) golfed versions:

```
def J(L,i,n,S):
    if (i >= len(L)-1): S.append(n)
    else:
        La = list(L)
        La[len(La) - i - 1] = 0
        for j in range(1,L[i]+1):
            J(La,i+j,n+1,S)

def MJ(L):
     S = []
     J(L + L[:-1][::-1],0,0,S)
     return min(S) if (S) else -1

```

Some examples:

```
print MJ([2,4,2,2,3,4,2,2])
print MJ([0,2,4,2,2,3,4,2,2])
print MJ([3,4,0,0,6])

```

# Answer
> 2 votes
**Ruby - 246**

```
a=gets.split.map &:to_i
L=a.size;r=[];a.collect!{|v|([1,v].min..v).to_a};S=a[0].product *a[1..-1];S.each{|s|i=0;b=L==1&&s[i]!=0 ?0:1;(L*2).times{|c|r<<c if i==L-1&&b==0;break if !s[i]||s[i]==0;if i==L-1;b=i=0;s.reverse!end;i+=s[i]}}
puts r.min||-1

```

Simulation:

```
2, 4, 2, 2, 3, 4, 2, 2
6

0, 2, 4, 2, 2, 3, 4, 2, 2
-1

0
-1

1
0

```

# Answer
> 2 votes
Ruby - about 700 golfed. I started a golfed version, with single-character names for variables and methods, but after awhile I got more interested in the algorithm than the golf, so stopped trying to optimize code length. Nor did I worry about getting the input string. My effort is below.

To help you understand how it works I've included comments that show how a particular string (u = "2 1 4 3 0 3 4 4 3 5 0 3") is manipulated. I enumerate combinations of "rocks in the stream" that are available to hop on. These are represented with a binary string. I give the example 0b0101101010 in the comments and show how it would be used. The 1's correspond to the positions of rocks available for the initial trip; the 0's for the return trip. For each such allocation, I use dynamic programming to determine the minimal number of hops required in each direction. I also perform a few simple optimizations to eliminate some combinations early on.

I've run it with the strings given in other answers and get the same results. Here are some other results I obtained:

```
"2 1 4 3 0 3 4 4 3 5 0 3"                             # =>  8
"3 4 3 5 6 4 7 4 3 1 5 6 4 3 1 4"                     # =>  7
"2 3 2 4 5 3 6 3 2 0 4 5 3 2 0 3"                     # => 10
"3 4 3 0 4 3 4 4 5 3 5 3 0 4 3 3 0 3"                 # => 11
"2 3 2 4 5 3 6 3 2 0 4 5 3 2 0 3 4 1 6 3 8 2 0 5 2 3" # => 14

```

I would be interested in hearing whether others get the same results for these strings. Performance is reasonable good. For example, it took less than a minute to get a solution for this string:

"3 4 3 0 4 3 4 4 5 3 5 3 0 4 3 3 0 3 4 5 3 2 0 3 4 1 6 3 2 0 4 5 3 2 0 3 4 1 6 3 0 4 3 4 4 5 0 1"

The code follows.

```
I=99 # infinity - unlikely we'll attempt to solve problems with more than 48 rocks to step on

def leap!(u)
  p = u.split.map(&:to_i) # p = [2,1,4,3,0,3,4,4,3,5,0,3]
  s = p.shift        # s=2, p =   [1,4,3,0,3,4,4,3,5,0,3] # start
  f = p.pop          # f=3, p =   [1,4,3,0,3,4,4,3,5,0]   # finish
  q = p.reverse      #      q =   [0,5,3,4,4,3,0,3,4,1]   # reverse order
  # No path if cannot get to a non-zero rock from s or f
  return -1 if t(p,s) || t(q,f)
  @n=p.size                  # 10 rocks in the stream
  r = 2**@n                  # 10000000000 - 11 binary digits
  j = s > @n ? 0 : 2**(@n-s) #   100000000 for s = 2 (cannot leave start if combo number is smaller than j)
  k=r-1                      #  1111111111 - 10 binary digits

  b=I # best number of hops so far (s->f + f->s), initialized to infinity
  (j..k).each do |c|
    # Representative combo: 0b0101101010, convert to array
    c += r                     # 0b10 1 0 1 1 0 1 0 1 0
    c = c.to_s(2).split('').map(&:to_i)
                               # [1,0,1,0,1,1,0,1,0,1,0]
    c.shift                    #   [0,1,0,1,1,0,1,0,1,0] s->f: rock offsets available: 1,3,4,6,8
    d = c.map {|e|1-e}.reverse #   [1,0,1,0,1,0,0,1,0,1] f->s: rock offsets available: 0,2,5,7,9
    c = z(c,p)                 #   [0,4,0,0,3,0,4,0,5,0] s->f: max hops by offset for combo c
    d = z(d,q)                 #   [0,0,3,0,4,0,0,3,0,1] f->s: max hops by offset for combo c
    # Skip combo if cannot get from to a rock from f, or can't
    # get to the end (can always get to a rock from s if s > 0).
    next if [s,f,l(c),l(d)].max < @n && t(d,f)
    # Compute sum of smallest number of hops from s to f and back to s,
    # for combo c, and save it if it is the best solution so far.
    b = [b, m([s]+c) + m([f]+d)].min
  end
  b < I ? b : -1 # return result
end

# t(w,n) returns true if can conclude cannot get from sourch n to destination
def t(w,n) n==0 || (w[0,n].max==0 && n < @n) end
def l(w) w.map.with_index {|e,i|i+e}.max end
def z(c,p) c.zip(p).map {|x,y| x*y} end

def m(p)
  # for s->f: p = [2,0,4,0,0,3,0,4,0,5,0] - can be on rock offsets 2,5,7,9
  # for f->s: p = [3,0,0,3,0,4,0,0,3,0,1] - can be on rock offsets 3,5,8,10
  a=[{d: 0,i: @n+1}]
  (0..@n).each do |j|
    i=@n-j
    v=p[i]
    if v > 0
      b=[I]
      a.each{|h| i+v < h[:i] ? break : b << (1 + h[:d])}
      m = b.min
      a.unshift({d: m,i: i}) if m < I
    end
  end
  h = a.shift
  return h[:i]>0 ? I : h[:d]
end

```

# Answer
> 0 votes
# Haskell, ~~173~~ 166 bytes, 159 bytes in GHCi

Here is the normal version:

import Data.List

```
t=length
j[_]=0
j l=y[t f|f<-fst.span(>0)<$>permutations[0..t l-1],u<-f,u==t l-1,all(\(a,b)->abs(b-a)<=l!!a)$zip(0:f)$f++[0]]
y[]=0-1
y l=minimum l+1

```

Here is the GHCi answer (put the line one at a time):

```
t=length
y[]=0-1;y l=minimum l+1
j[_]=0;j l=y[t f|f<-fst.span(>0)<$>Data.List.permutations[0..t l-1],u<-f,u==t l-1,all(\(a,b)->abs(b-a)<=l!!a)$zip(0:f)$f++[0]]

```

Just a bruteforce. Generate the possible answer. (i.e. permutation of \[0..n-1\] with zero and following element dropped. Then check if the answer is correct. Get the minimum length and add by one. (Since the leading and trailing zeroes is delete).

How to use: `j[3,4,0,0,6]` -\> `3`

---
Tags: code-golf, puzzle-solver
---


title: Uh, is it a haiku?

text:
# Question
Title: Uh, is it a haiku?
So you want to create a haiku, but you're not sure if it follows the syllable rules for a haiku.

I couldn't be bothered to write a proper blurb like I usually do, so you'll have to make do with this. Let's get stuck right in.

## Finding a haiku out in the wild

For the purposes of this challenge, we will be checking if the given poem satisfies these criteria:

* There are three lines.
* The first line has 5 syllables.
* The second line has 7 syllables.
* The third line has 5 syllables.

Each line is composed of one or more words, separated by groups of spaces. These words are not necessarily valid English words.

Each word is split up into syllables, and then those syllables are counted to get the total syllable count of the line.

A syllable has either 2 or 3 parts to it: the beginning, the end, and possibly the middle. Each part is either a group of consonsants (also known as a consonant cluster, such as `s`, `sk` or `spl`) or a group of vowels (such as `i`, `ea` or `oui`).

If the beginning is a group of consonants, the middle will be a group of vowels and the end will be a group of consonants. If the beginning is a group of vowels, the end will be a group of consonants and there will be no middle.

For example, the word `example` is made up of three syllables, `ex`, `am` and `ple`. `ple` has no ending as it was cut short by the end of the word.

As another example, the word `syllable` also has three syllables, `syll`, `abl` and `e`, which also has no ending.

For one final example, the word `word` has one syllable, `word`, which ends with a group of consonants.

## The challenge

Given a string, list of strings, list of lists or any other reasonable format representing a poem with at least one line, determine if it meets the criteria of a haiku outlined above and return the result.

You may return the result in any of these formats:

* A truthy value if the poem is a haiku and a falsy one otherwise.
* A falsy value if the poem is a haiku and a truthy one otherwise.
* A value from a finite range of values specified in the submission if the poem is a haiku and a value from a mutually exclusive finite range of values also specified in the submission.

You may also assume the poem contains no non-alphabetical characters, but you may not assume that it is entirely in uppercase or lowercase.

For the purposes of this challenge, `Y` is a vowel.

## Test cases

### Truthy

```
This is a haiku
Yes it truly is one
See what I did man

```

---

```
I am so tired
of writing this already
when can I stop this

```

---

```
Writing another
Of these horrific things
Come on please

```

---

```
Consonant only
Counts as one syllable
ghjk tgh knmb wrts vbc

```

### Falsy

```
oh boy writing non haiku is so much easier

```

---

```
This is
so good
on my
poor dear brain

```

---

```
The syllables do not match
at least I do not think so
I have not checked

```

---

```
It does not really matter
these test cases will help
At least I think they will

```

---

```
I am done here
This is enough
Goodbye

```

## Scoring

Since this is
The shortest answer will win
Good luck to you all

# Answer
> 4 votes
# Jelly,  ~~25~~  23 bytes

-2 thanks to Erik the Outgolfer (use a list of lines as input)

```
e€Øy0;ŒgP€
ḲLÐfÇ€ḣ8µ€ḣ4

```

A monadic link taking a list of lists of characters (the lines) and returning a list of lists of lists of zeros and ones. Valid haiku will be length 3 and once any of the deepest lists that are a single zero are replaced by a single one the sum of the flattened lists will be 5, 7, and 5 respectively. The formation (whether *runs* of letters are consonants and only taking the first 8 words of each of up to only 4 lines) ensures there are only finite of each of the valid and invalid ranges.

**Try it online!** or see the (even more confusing!) test-suite

---

Here is a much easier to use  **~~32~~  30 byte** version, simply outputting 1 or 0:

```
e€Øy0;ŒgP€SȯL$
ḲLÐfÇ€Sµ€⁼5,7,5

```

Try this one or see its test-suite.

# Answer
> 3 votes
# JavaScript (ES6), ~~84~~ 75 bytes

Takes input as a list of lists of words. Returns `true` for haiku or `false` for non-haiku.

```
a=>a.map(s=>(s.map(w=>w.match(/[aeiouy]+/gi))+'').split`,`.length)=='5,7,5'

```

### Test cases

```
let f =

a=>a.map(s=>(s.map(w=>w.match(/[aeiouy]+/gi))+'').split`,`.length)=='5,7,5'

console.log('[Truthy]');

console.log(f([
  ["This","is","a","haiku"],
  ["Yes","it","truly","is","one"],
  ["See","what","I","did","man"]
]));
console.log(f([
  ["I","am","so","tired"],
  ["of","writing","this","already"],
  ["when","can","I","stop","this"]
]));
console.log(f([
  ["Writing","another"],
  ["Of","these","horrific","things"],
  ["Come","on","please"]
]));
console.log(f([
  ["Consonant","only"],
  ["Counts","as","one","syllable"],
  ["ghjk","tgh","knmb","wrts","vbc"]
]));

console.log('[Falsy]');

console.log(f([
  ["oh","boy","writing","non","haiku","is","so","much","easier"]
]));
console.log(f([
  ["This","is"],
  ["so","good"],
  ["on","my"],
  ["poor","dear","brain"]
]));
console.log(f([
  ["The","syllables","do","not","match"],
  ["at","least","I","do","not","think","so"],
  ["I","have","not","checked"]
]));
console.log(f([
  ["It","does","not","really","matter"],
  ["these","test","cases","will","help"],
  ["At","least","I","think","they","will"]
]));
console.log(f([
  ["I","am","done","here"],
  ["This","is","enough"],
  ["Goodbye"]
]));
```

# Answer
> 2 votes
# Retina, 49 bytes

```
i`[aeiouy]+
1
T`lL`2
2*12+
3
[12]+
3
%M`3
^5¶7¶5$

```

Try it online!

Outputs `1` for haiku,`0` for non-haiku.

# Answer
> 2 votes
# Python 2, ~~126~~ ~~125~~ ~~120~~ 121 bytes

```
lambda s:[len(split('\s+',sub('[aeiouy][^aeiouy ]+','X ',t,0,I).strip()))for t in s.split('\n')]==[5,7,5]
from re import*

```

Try it online!

# Answer
> 2 votes
# Perl 5, 63 + 1 (`-p`) = 64 bytes

```
$a[$.]=()=/([aeiouy]+|\b[^aeiouy ]+\b)\s*/ig}{$\="@a"eq" 5 7 5"

```

Try it online!

# Answer
> 1 votes
# Clean, ~~162~~ ... 115 bytes

```
import StdEnv,StdLib
@t=[sum[max(sum(map hd(group[sum[1\\v<-:"AaEeIiOoUuYy"|c==v]\\c<-w])))1\\w<-l]\\l<-t]==[5,7,5]

```

Defines the function `@`, taking `[[[Char]]]` (list of list of words), and giving `Bool`.
Returns `True` when the input is a haiku, `False` otherwise.

Try it online!

# Answer
> 1 votes
## Mathematica 119 Bytes

Here is a version that conforms to the given rules for syllables:

```
Tr/@Map[Length@StringCases[#,("a"|"e"|"i"|"o"|"u"|"y")..]/. 0->1&,(s=StringSplit)/@s[ToLowerCase@#,"\n"],{2}]=={5,7,5}&

```

Here is an 83 byte version that actually counts syllables:

```
Tr/@Map[Length@WordData[#,"Hyphenation"]&,(s=StringSplit)/@s[#,"\n"],{2}]=={5,7,5}&

```

e.g.

```
%@"This is a haiku
Yes it truly is one
See what I did man"

```

returns `False` since the second line has six syllables rather than the required seven.

---
Tags: code-golf, string, decision-problem
---


title: Single swaps of an array

text:
# Question
Title: Single swaps of an array
*~~Inspired by~~ Taken from a question at Stack Overflow*.

# The challenge

Given an integer `n>1`, output all arrays that can be obtained by swapping exactly two entries in the array `[1, 2, ..., n]`.

The arrays can be produced in any order.

You can consistently use `[0, 1, ..., n-1]` (0-based) instead of `[1, 2, ..., n]` (1-based).

# Additional rules

# Test cases

Input `2` gives output (assumed 1-based)

```
2 1

```

Input `3` gives output (note that the three arrays could be in any order)

```
1 3 2
2 1 3
3 2 1

```

Input `4` gives output

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

```

Input `7` gives output

```
1 2 3 4 5 7 6
1 2 3 4 6 5 7
1 2 3 4 7 6 5
1 2 3 5 4 6 7
1 2 3 6 5 4 7
1 2 3 7 5 6 4
1 2 4 3 5 6 7
1 2 5 4 3 6 7
1 2 6 4 5 3 7
1 2 7 4 5 6 3
1 3 2 4 5 6 7
1 4 3 2 5 6 7
1 5 3 4 2 6 7
1 6 3 4 5 2 7
1 7 3 4 5 6 2
2 1 3 4 5 6 7
3 2 1 4 5 6 7
4 2 3 1 5 6 7
5 2 3 4 1 6 7
6 2 3 4 5 1 7
7 2 3 4 5 6 1

```

# Answer
> 3 votes
# Jelly, ~~11~~ 8 bytes

```
ŒcżU$y€R

```

Try it online!

### How it works

```
ŒcżU$y€R  Main link. Argument: n

Œc        Take all 2-combinations of [1, ..., n].
  żU$     Zip the result with the reversed pairs.
       R  Range; yield [1, ..., n].
     y€   For each [[i, j], [j, i]] in the result to the left, yield the result to
          the right, with i replaced by j and vice versa.

```

# Answer
> 8 votes
# , 54 bytes

```
function(n)combn(n,2,function(x){z=1:n
z[x]=rev(x)
z})

```

Try it online!

Returns a matrix where each column is a permutation.

`combn(n,k)` generates all combinations of size `k` from the list `n`, or from `1:n` if `n` is a single integer. It also optionally takes a function `FUN` to be applied to the resultant combinations. So we write a function that performs the swap and returns the swapped list. The results are then all accumulated into an `array`, which is in this case 2-dimensional and hence a matrix.

# Answer
> 7 votes
# Python 2, 71 bytes

```
r=range(input())
print[map({i:j,j:i}.get,r,r)for i in r for j in r[:i]]

```

Try it online!

Uses this tip.

# Answer
> 6 votes
# Haskell, 62 bytes

```
f n=[[1..x-1]++y:[x+1..y-1]++x:[y+1..n]|x<-[1..n],y<-[x+1..n]]

```

Try it online!

I just generate the permutation, given the `x` and `y` to swap, for each `x,y`

# Answer
> 5 votes
# Python 2, 72 bytes

```
r=range(input())
for j in r:
 for i in r[:j]:t=r*1;t[i]=j;t[j]=i;print t

```

Try it online!

# Answer
> 5 votes
# Wolfram Language (Mathematica), 43 bytes

```
r/.{#->#2,#2->#}&@@@Subsets[r=Range@#,{2}]&

```

Try it online!

Explanation: `Subsets[Range@#,{2}]` generates all subsets of `{1,2,...,n}` of size 2, then for each subset, `/.` swaps those two things in the list `{1,2,...,n}`.

That approach is disappointingly similar to many of the other submissions, but here's one that's more unique to Mathematica, for 3 extra bytes:

```
r~Permute~Cycles@{#}&/@Subsets[r=Range@#,{2}]&

```

Try it online!

# Answer
> 5 votes
## Haskell, 62 bytes

```
g n|b<-[1..n]=[[last$k:[j|k==i]++[i|k==j]|k<-b]|i<-b,j<-b,j<i]

```

Try it online!

```
i<-b                -- loop 'i' through [1..n]
     j<-b           -- loop 'j' through [1..n]
          j<i       -- consider only cases where j<i
 [            k<-b] -- make a list by looping 'k' through [1..n]
  last              -- pick
          [i|k==j]  -- 'i' if k==j
       [j|k==i]     -- 'j' if k==i
     k              -- 'k' else

```

# Answer
> 4 votes
# Haskell, 71 bytes

```
f 0=[]
f x=map(++[x])(f$x-1)++[[1..y-1]++x:[y+1..x-1]++[y]|y<-[1..x-1]]

```

Try it online!

---

This adds the current number to the end of all the permutations of last and then computes all the swaps that include the new number.

# Answer
> 4 votes
# MATL, 12 bytes

```
:2XN!"G:@tP(

```

Try it online!

```
            %implicit input, say, 4
:           %range, stack is {[1,2,3,4]}
2           %push 2
XN          %nchoosek, compute all combinations of [1,2,3,4] taken 2 at a time
            %this results in a matrix where each row is a combination, i.e.,
            %[1, 2;
              1, 3;
              1, 4;
              2, 3;
              2, 4;
              3, 4]
!           %transpose, because "for" iterates over columns
"           %begin for loop
G:          %push input and range, stack is now [1,2,3,4]
@t          %push "for" index (the column), say, [1;2], twice
P           %flip array, so stack is now: {[1,2,3,4],[1;2],[2;1]}
(           %assignment index, sets [1,2,3,4]([1;2])=[2;1],
            %resulting in [2,1,3,4]
            %implicit end of loop, implicit end of program, print the stack implicitly.
```

# Answer
> 3 votes
# C, 93 bytes

```
i,j,k;f(n){for(i=0;i++<n;)for(j=i;j++<n;puts(""))for(k=0;k++<n;)printf("%d ",k-i?k-j?k:i:j);}

```

Try it online!

# Answer
> 3 votes
# Octave, 38 bytes

```
@(n)(p=perms(k=1:n))(sum(p~=k,2)==2,:)

```

Try it online!

Generates all permutations of 1:n and select from them those that have two elements different from 1:n.

# Answer
> 2 votes
# Clean, ~~90~~ 82 bytes

```
import StdEnv
$n#n=[1..n]
=tl(removeDup[[if(c<>b)if(c<>a)c b a\\c<-n]\\b<-n,a<-n])

```

It can be done in 80 bytes, but it turns into a direct translation of the Haskell answers.

Try it online!

# Answer
> 2 votes
# JavaScript (ES6), 81 bytes

Prints 0-indexed arrays.

```
n=>(a=[...Array(n).keys()]).map(i=>a.map(j=>i>j&&alert(a.map(k=>k-i?k-j?k:i:j))))

```

### Demo

`alert()` is replaced with `console.log()` in this snippet for user-friendliness.

```
let f =

n=>(a=[...Array(n).keys()]).map(i=>a.map(j=>i>j&&alert(a.map(k=>k-i?k-j?k:i:j))))

alert = s => console.log(JSON.stringify(s));

f(4)
```

# Answer
> 2 votes
# Python 2, 75 bytes

```
lambda n:[r(i)+[j]+r(i+1,j)+[i]+r(j+1,n)for j in r(n)for i in r(j)]
r=range

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~15~~ 9 bytes

```
LœʒD{αĀO<

```

Try it online!

**Explanation**

```
L            # push range [1 ... input]
 œ           # get all permutations
  ʒ          # filter, keep only elements that are true when
     α       # absolute value is taken with
   D{        # a sorted copy
      Ā      # each non-zero value in the resulting array is converted to 1
       O     # the array is summed
        <    # and the sum is decremented

```

# Answer
> 2 votes
# Husk, 9 bytes

```
!2§kδ#≠Pḣ

```

Try it online!

## Explanation

```
!2§kδ#≠Pḣ  Input is an integer n.
        ḣ  Range: r=[1,2,..,n]
       P   Permutations of r.
   k       Classify by
     #     number of elements
      ≠    that are different from
  § δ      the corresponding element of r.
!2         Take the second class.

```

# Answer
> 2 votes
# Ruby, ~~55~~ 53 bytes

```
->n{n.times{|x|x.times{|y|(w=*0...n)[w[x]=y]=x;p w}}}

```

Try it online!

0-based solution

The trick here is that the inner loop always "skips" an iteration: the first time it's not executed at all, then only once on the second pass, and so on.

I was happy with 55 bytes until I saw that **R** could be golfed down to 54, so I had to get it to 53.

# Answer
> 1 votes
# Python 2, 90 bytes

```
f=lambda n,r=range:n*[n]and[a+[n]for a in f(n-1)]+[r(1,i)+[n]+r(i+1,n)+[i]for i in r(1,n)]

```

Try it online!

# Answer
> 1 votes
# Ruby, 80 bytes

*-12 bytes thanks to Unihedron.*

```
->n{(r=1..n).map{|x|r.map{|y|r.map{|i|i==x ?y:i==y ?x:i}}}.flatten(1).uniq[1,n]}

```

Try it online!

I had an approach in mind that best translated to Ruby for some reason so... I don't even really know Ruby...

# Answer
> 1 votes
# Pyth, 9 bytes

```
t{.rLQ*=U

```

Demonstration

The easiest way to swap two values is to use `.r`, which is Pyth's rotary translation function. `.r<list>[A, B]` will swap all occurrences of `A` and `B` in `list`.

Therefore, by applying the translation function to `UQ`, the list from `0` to `n-1` with each two element list of different numbers in the list, we will generate the desired output. `Q` is the input, `n`, and `U` is the range function.

The easy way to do this would be:

```
.rLUQ.cUQ2

```

`.cUQ2` generates all 2 element combinations of distinct elements in the range, and `.rLUQ` maps the `.r` function over them and the list `UQ`.

However, that would be 10 bytes.

Instead of making `.cUQ2`, the distinct ordered pairs, we can make all pairs with `*=U`. This is implicitly equivalent to `*=UQQ`. It starts by overwriting `Q` with `UQ`, then taking the Cartesian product of `UQ` and `UQ`. This gives all pairs of numbers in the range, not necessarily ordered or distinct.

`.rLQ` swaps using each list. Recall that `Q` is now equal to the list from `0` to `n-1`, not `n`.

Because the pairs were not ordered, there are duplicates. `{` removes duplicates. Because the pairs were not distinct, the unchanged list is present. This list will always be first after deduplication, because `{` preserves the order of the first appearance and the unchanged list is produced by rotating by `[0,0]`. `t` removes the first element, giving the desired list of swaps.

# Answer
> 1 votes
# Pyth, 11 bytes

```
fq2snVTUQ.p

```

Try it online
Not as short as isaacg's approach, but different enough to post.

### Explanation

```
fq2snVTUQ.p
         .pQ  Take the permutations of the (implicit) range [0,...,input].
f     T       Filter to get the permutations...
   snV UQ     ... where the number of differences with [0,...,input]...
 q2           ... is 2.

```

# Answer
> 1 votes
# Java 8, ~~109~~ 105 bytes

```
n->{String r="";for(int i=0,j,k;i++<n;)for(j=i;j++<n;r+="\n")for(k=0;k++<n;)r+=k!=i?k!=j?k:i:j;return r;}

```

I'm rusty.. Haven't code-golfed in months.. Ended up porting @Steadybox' C answer.. Can probably be golfed some more.

Try it here.

# Answer
> 1 votes
# Ruby, 66 bytes

```
->n{a=*1..n
a.permutation.select{|b|b.zip(a).count{|c,d|c!=d}==2}}

```

Try it online!

---
Tags: code-golf, number, combinatorics, integer
---


title: Counting Moufang Loops

text:
# Question
Title: Counting Moufang Loops
A loop is a pretty simple algebraic structure. It is a tuple **(G,+)** where **G** is a set and **+** is a binary operator **G × G → G**. That is **+** takes two elements from **G** and returns a new element. The operator is also required to fulfill two properties

* Cancellation: For every **a** and **b** in **G** there exists unique **x** and **y** in **G** such that

```
a + x = b
y + a = b

```
* Identity: There is an **e** in **G** such that for every **a** in **G**

```
e + a = a
a + e = a

```

If you are familiar with the concept of a group you might notice that a loop is just a group that doesn't have an associative property.

Loops are pretty simple so people like to add more rules to make new structures that are more interesting. One such structure is a Moufang loop which is a loop that also satisfies the following four identities forall **x**, **y** and **z** in **G**

```
z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

```

For example the following Cayley table represents a Moufang loop:

```
0  1  2  3
1  0  3  2
2  3  0  1
3  2  1  0

```

*(If you are not familiar a Cayley table is a square matrix **M** where **Mi,j** is equal to **i + j**. It is a handy way for representing binary operators on a set.)*

We can show that there is an identity rather easily it is `0`. Cancellation is a little harder to show but a brute force approach yields this table

```
b a → 0 1 2 3
↓
0     0 1 2 3
1     1 0 3 2
2     2 3 0 1
3     3 2 1 0

```

Where our elements are the solutions to

```
a + x = b = x + a

```

*(You may notice that this table is identical to our Cayley table. I'll leave it as an exercise to the reader to figure out why this is the case for this Moufang loop)*

Now we need to verify the Moufang identities for our structure. There are two ways to do this for the particular structure the first way is to realize that it is associative and thus automatically fulfills the criteria, however this will not work in general so we would rather brute force the result. There are 3 free variables each with a potential of 4 values in every expression here. This means we have to perform 7\*43 or 448 computations. I'll leave out the raw computations but here is some Haskell you can use to verify this.

# Task

Given a positive integer **n** as input output the number of Moufang loops that have order **n**. (the order of a group is the size of the set)

This is so answers will be scored in bytes with fewer bytes being better.

# Test cases

Here is the number of Moufang loops for the first **71** inputs

```
1,1,1,2,1,2,1,5,2,2,1,6,1,2,1,19,1,5,1,6,2,2,1,20,2,2,5,5,1,4,1,122,1,2,1,18,1,2,2,19,1,7,1,5,2,2,1,103,2,5,1,6,1,17,2,17,2,2,1,18,1,2,4,4529,1,4,1,6,1,4,1

```

# Answer
# Python 3, ~~475~~ 410 bytes

Thanks to Mr.Xcoder for saving some bytes!

Use the symmetry of the formula to save 65 bytes. Yes, that's a lot.

```
from itertools import*
n=int(input())
P=permutations
R=[*range(n)]
u=[]
A=all
S=sorted
for T in P(P(R),n):u+=[T]*(A(A(R==S(x)for x in
t)and any([*x]==S(x)for x in t)and
A(t[z][t[x][t[z][y]]]==t[t[t[z][x]][z]][y]and
t[t[z][x]][t[y][z]]==t[t[z][t[x][y]]][z]for x in R
for y in R for z in R)for t
in(T,[*zip(*T)]))and A(A(1-A(p[T[i][j]]==U[p[i]][p[j]]for i in R
for j in R)for p in P(R))for U in u))
print(len(u))

```

Try it online!

---

Some `and` can be replaced by `*`, results in lower bytecount but at the cost of significantly slower execution time:

# Python 3, ??? bytes

\[TODO put code here\]

(of course not all `*` makes the program significantly slower, only some of them are critical)

---

Ungolfed:

```
from itertools import *
n = 4 # int(input())
rangeN = list(range(n))

def is_moufang_loop(T):
    A = tuple(zip(*T))
    return all(
        all(sorted(x) == rangeN for x in t)
        and any(list(x) == sorted(x) for x in t)
        and all(
                T[z][T[x][T[z][y]]] == T[T[T[z][x]][z]][y]
            and T[T[z][x]][T[y][z]] == T[T[z][T[x][y]]][z]
            for x in rangeN for y in rangeN for z in rangeN)
        for t in (T, A)
    )

def isomorphic(loop1, loop2):
    for p in permutations(rangeN):
        if all(
            p[loop1[i][j]] == loop2[p[i]][p[j]]
            for i in rangeN
            for j in rangeN
        ): return True
    return False

unique_moufang_loops = []
for x in [
        cayley_table
        for cayley_table in permutations(permutations(rangeN), n)
        if is_moufang_loop(cayley_table)
]:
    if all(not isomorphic(x, y) for y in unique_moufang_loops):
        unique_moufang_loops.append(x)

print(len(unique_moufang_loops))

```

Try it online!

No scroll bars...

---

Explanation:

The program is pretty simple.

* Each possible "binary operator" is represented by a Cayley table (0-indexing).
* The "identity" property implies that there exists `e` such that both the `e`'th row and the `e`'th column are equal to `[0, 1, 2, ..., n-1]`, which is the same condition as
> both the array `T` and its transpose has a row equal to `[0, 1, 2, ..., n-1]`.
* The "cancellation" property is equivalent to
> Every row and every column are a permutation of `[0, 1, 2, ..., n-1]`.

So, the part

```
all(
        all(sorted(x) == rangeN for x in t)
        and any(list(x) == sorted(x) for x in t)
        for t in (T, A))

```

of the code checks that. (for all row in the array `T` and its transpose `A`, it being sorted is equal to `rangeN`, and there exists a row in both `T` and `A` that equals to itself being sorted)

The four conditions of a Moufang loops are checked manually.

```
z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

```

In the code, `(a + b)` is represented as `T[a][b]`. (because of the representation as Cayley table). Use Python chaining equality comparison to avoid duplication of `(z + x) + (y + z)`.

However, because the formula is symmetric:

If we switch the operands of `+` in the first formula, we get the second formula; and if we switch the operands of `+` in the third formula, we get the fourth formula with `x` and `y` swapped place.

Note that the transposition of the Cayley table is equivalent to the binary operators having operands swapped. (`x + y -> y + x`)

Finally, all the candidates Cayley table are picked from

```
permutations(permutations(rangeN), n)

```

so that each row is a permutation of `rangeN` (which is `[0, 1, 2, ..., n-1]`) and there are `n` distinct rows.
> 4 votes

---
Tags: code-golf, math, abstract-algebra
---


# Question
Title: Shortest C \ C++ function to generate -1, 0 ,1
Let a function receive two integers `i` and `j` between `0` and `3`, it should return the value in position `(i,j)` in the following 2D array:

```
1, 0, -1, 0
1, 0, -1, 0
0, 1, 0, -1
0, -1, 0, 1

```

Shortest code in any variant of C / C++ wins.

# Answer
## 32

```
f(i,j){return~-(j+2-i*i/3&3)%2;}

```
> 7 votes

# Answer
# 40

```
f(i,j){return~-(2434352710>>8*i+2*j&3);}

```

A hackish **35** solution (xxd dump):

```
0000000: 6628 692c 6a29 7b72 6574 7572 6e7e 2d28  f(i,j){return~-(
0000010: 695b 2246 4619 9122 5d3e 3e32 2a6a 2633  i["FF.."]>>2*j&3
0000020: 293b 7d                                  );}

```

If proper octal escapes are used, it's the same **40** characters:

```
f(i,j){return~-(i["FF\31\221"]>>2*j&3);}

```
> 10 votes

# Answer
# C99, 34

```
f(i,j){return(i<3?1-j+i/2:j-2)%2;}

```
> 10 votes

# Answer
# C, 29

I know this one seems kinda unfair but does it actually work for anyone? ^\_^

```
f(i,j){j=("&&4+"[i]>>j)%3-1;}

```
> 5 votes

# Answer
# 38

```
f(i,j){return(i/2+j+1)*(1-(i-j&2))%2;}

```

# 37

```
f(i,j){return(i/2+j+1)*-~-(i-j&2)%2;}

```
> 4 votes

# Answer
# C++, ~~70~~, ~~45~~, 44

```
f(i,j){return(j/2&i^~i&~j>>1)*~-(j-i&2)%2;}

```

The Karnaugh map approach, mixed with a bit of fsw's solution.

If A is (j\>\>1) and D is (i&1), the function should return "-~-(j-i&2)%2" (fsw's solution) multiplied by the Karnaugh map ~A~D + AD.

I feel there is a better solution for this using the Karnaugh map, but it's too late to think of it. Maybe tomorrow :)

Thanks for the comments, shaved off many chars.
> 3 votes

# Answer
# C#

```
int f(int i,int j){return "2101210112101012"[i*4+j]-49;}

```
> 2 votes

# Answer
# 48

```
f(a,b){return 10308>>4*a+b&1?-1:43605>>4*a+b&1;}

```
> 2 votes

# Answer
## C, 45

```
f(i,j){i=i+(j>1)*(7-2*j)&3;return i&1?0:1-i;}

```
> 1 votes

---
Tags: code-golf, array, matrix, c, c++
---


title: Match the Striking Clock

text:
# Question
Title: Match the Striking Clock
## Introduction:

At home we have a clock that strikes the stated amount at each hour, but also strikes once at every half-hour. So from 0:01 to and including 12:00 it strikes in this order:

```
1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11, 1, 12

```

## Challenge:

Given an integer `n`, output a list of time-frames in which the total strikes are equal to `n`. In addition, always start at least 1 minute before this time-frame and end at least 1 minute after this time-frame (and at most 29 minutes).
For example, if the input is `n=8`, the output could be:

```
[00:59-03:01, 01:29-03:31, 02:59-04:01, 05:29-06:31, 06:29-07:01, 06:59-07:31, 07:59-08:01]

```

For which these time-frames have the following sums, all equaling `8`:

```
[1+1+2+1+3, 1+2+1+3+1, 3+1+4, 1+6+1, 1+7, 7+1, 8]

```

## Challenge rules:

* Output is flexible. You can output as Time (or Date/DateTime) objects, timestamps, strings (with or without leading zeroes), decimals with `.29`/`.31`/`.59`/`.01` (i.e. `0.29-3.01` instead of `00:29-03:01`), etc. As long as it's clear it's before and after the time-frame.
In addition, you can choose the amount yourself. In all my examples I use 1 minute, but you can also choose 5 minutes, 15 minutes, etc. This also means you can use `.4`/`.6`/`.9`/`.1` (i.e. `0.4-3.1` instead of `00:24-03:06`) for example. The list is also flexible. Can be a list/collection, array, delimiter-separated string, printing per line to STDOUT, etc.
**Please state which output choice you've made.** Note: You are not allowed to output the sums of the time-frames like above, this is only mentioned as clarification. You must output the time-frames, including slightly before and after it.
* The strikes do wrap around from `12:00` to `00:30`. So if `n=14`, two of the time-frames are `11:29-00:31` and `11:59-01:01`.
* Input will be in the range `1 <= n <= 90`, where 90 is the total sum of all possible strikes.
* The time-frames you return can be in any order.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

## Test cases:

(all using 1 minute before / after the time-frames and leading zeroes)

```
Input: 8
Ouput:
[00:59-03:01, 01:29-03:31, 02:59-04:01, 05:29-06:31, 06:29-07:01, 06:59-07:31, 07:59-08:01]

Input: 14
Output:
[00:29-04:01, 00:59-04:31, 02:59-05:01, 04:29-06:31, 05:59-07:01, 11:29-00:31, 11:59-01:01]

Input: 90
Output:
[00:29-00:01, 00:59-00:31, 01:29-01:01, 01:59-01:31, 02:29-02:01, 02:59-02:31, 03:29-03:01, 03:59-03:31, 04:29-04:01, 04:59-04:31, 05:29-05:01, 05:59-05:31, 06:29-06:01, 06:59-06:31, 07:29-07:01, 07:59-07:31, 08:29-08:01, 08:59-08:31, 09:29-09:01, 09:59-09:31, 10:29-10:01, 10:59-10:31, 11:29-11:01, 11:59-11:31]

Input: 1
Output:
[00:29-00:31, 00:59-01:01, 01:29-01:31, 02:29-02:31, 03:29-03:31, 04:29-04:31, 05:29-05:31, 06:29-06:31, 07:29-07:31, 08:29-08:31, 09:29-09:31, 10:29-10:31, 11:29-11:31]

Input: 2
Output:
[00:29-01:01, 00:59-01:31, 01:59-02:01]

```

# Answer
> 3 votes
# APL (Dyalog Classic), 34 bytesSBCS

```
∪12|.4 .1∘+¨.5×⍸⎕=⍉∘.-⍨+\,⍪⍨1,⍪⍳12

```

Try it online!

This solution uses `⎕io←1` (1-based indexing).

From right to left:

`⍳12` is `1 2 3...12`

turns it into a tall thin 12x1 matrix

`1,` adds a column of 1s to the left

`⍪⍨` concatenates the same matrix vertically, so it's now a 24x2 matrix

`,` flattens the matrix in row-major order, it becomes a vector of size 48: `1 1 1 2 1 3...1 12 1 1 1 2...1 12`

`+\` partial sums: `1 2 3 5 6 9...`

`∘.-⍨` the differences between each pair of elements, a 48x48 matrix

transpose

`⎕=` a 48x48 boolean matrix with 1s wherever the evaluated input () occurs

the pairs of coordinates of where the 1s are

`.5×` halve them

`.4 .1∘+¨` add 0.4 to the first and 0.1 to the second coordinate in each pair

`12|` modulo 12

unique

# Answer
> 5 votes
# JavaScript (ES6), 104 bytes

Prints time intervals in `H.MM,H.MM` format.

```
F=(n,f=0,s=n,t=f++)=>t<f+23?F(n,f,s-=t&1||t/2%12+1,++t,s||alert([f/2%12+.01,-~t/2%12+.01])):f<24&&F(n,f)

```

Try it online!

Uses essentially the same algorithm as the non-recursive version below.

---

# Non-recursive version, 117 bytes

Outputs a space-delimited string of time intervals in `H.MM,H.MM` format.

```
n=>[...Array(24)].map((_,f,a)=>a.map(_=>(s-=t++&1||t/2%12+.5)||(r+=[-~f/2%12+.01,-~t/2%12+.01]+' '),s=n,t=f),r='')&&r

```

### Test cases

```
let f =

n=>[...Array(24)].map((_,f,a)=>a.map(_=>(s-=t++&1||t/2%12+.5)||(r+=[-~f/2%12+.01,-~t/2%12+.01]+' '),s=n,t=f),r='')&&r

console.log(f(8))
console.log(f(14))
console.log(f(90))
console.log(f(1))
console.log(f(2))
```

### Commented

```
n =>                           // n = input
  [...Array(24)].map((_, f, a) // FOR f = 0 TO 23:
    => a.map(_ =>              //   FOR t = f TO f + 23:
      (                        //     update s
        s -=                   //       by subtracting:
          t++ & 1 ||           //         - 1 if t is odd (half hour)
          t / 2 % 12 + .5      //         - the current hour if t is even
      ) || (                   //     if s is equal to zero:
        r += [                 //       update the result string by appending:
          -~f / 2 % 12 + .01   //         - the formatted 'from' time
          ,                    //         - a comma
          -~t / 2 % 12 + .01   //         - the formatted 'to' time
        ] + ' '                //       and a padding space
      ),                       //     inner map() initialization:
      s = n,                   //     - s = target number of strikes
      t = f                    //     - 'to' time = 'from' time
    ),                         //   end of inner map()
    r = ''                     //   start with r = empty string
  )                            // end of outer map()
  && r                         // return r

```

# Answer
> 4 votes
# APL (Dyalog Unicode), ~~62~~ 59 bytesSBCS

Full program body. Prompts for `n`. Prints list of two-element lists using decimal hours.

```
∪(⎕=∊l+/¨⊂48⍴∊1,¨⍳12)/(¯.1 .1+⊃,⊢/)¨⊃,/(l←⍳48),/¨⊂.5×48⍴⍳24

```

Try it online!

`⍳24`**ɩ**ndices 1…24

`48⍴` cyclically **r**eshape to length 48, i.e. 1…12,1…12

`.5×` multiply a half by that

enclose (to use this entire array as right argument for each left argument)

`(``),/¨` for each of the following, return all the sub-lists of that length:

`⍳48`**ɩ**ndices 1…48

`l←` store in `l` (for **l**engths)

Now we have all the possible lists of runs of times for each possible run-length.

`,/` concatenate (lit. concatenation-reduction) the lists of sub-lists

disclose (because the reduction reduced the rank from 1 to 0)

`(` apply the following function to each:

`⊢/` the last (lit. right-reduction) element (the end time)

`⊃,` prepend the first element (the beginning time)

`¯.1 .1+` add negative and positive tenths to those

`(``)/` filter those begin-end pairs with:

`⍳12`**ɩ**ndices 1…12

`1,¨` prepend a `1` to each

**ϵ**nlist (flatten)

`48⍴` cyclically **r**eshape to length 48, i.e. 1,1,1,2…1,11,1,12

enclose (to use this entire array as right argument for each left argument)

`l+/¨` for each of `l` (1…48) return the sums of all the sub-lists of that length

**ϵ**nlist (flatten)

`⎕=` compare numeric input to that

return just the unique elements (begin-end pairs)

# Answer
> 3 votes
# Python 3, ~~118~~ 116 bytes

```
lambda n:[(a/2+.4,b%24/2+.1)for a in range(24)for b in range(48)if sum((sum(zip([1]*12,range(1,13)),())*2)[a:b])==n]

```

Try it online!

A timeframe is represented as `(t1, t2)`, `t1` and `t2` being decimals representing hours. The offset is `.1` or 6 minutes.

# Answer
> 1 votes
## Batch, 196 bytes

```
@for /l %%i in (0,1,23)do @set s=%1&for /l %%j in (0,1,23)do @call:c %%i %%j
:c
@set/at=%2+%1,s-=t%%2*(t/2%%12)+1,h=%1/2,i=%1%%2*30+15,t=-~t%%24/2,u=-~t%%2*30+15
@if %s%==0 echo %h%:%i% %t%:%u%

```

Explanation: `t` is the time in half hours, starting at `0` for `00:30`. The number of strikes at time t is then `1`, `1`, `1`, `2`, `1`, `3` etc. Subtracting `1` gives the sequence `0`, `0`, `0`, `1`, `0`, `2` etc. which is the integers interleaved with zeros. This can then be obtained by termwise multiplication of the sequence `0`, `0`, `1`, `1`, `2`, `2` etc. with the sequence `0`, `1`, `0`, `1`, `0`, `1` etc. Both of these sequences are readily calculated using modulo and (integer) division.

It then remains to loop over all 23 possible starting times, then taking all 24 striking times and subtracting the number of strikes from the input, printing the times when the result is zero.

The code falls through after the loop but no harm is done as the input cannot be more than 90.

# Answer
> 1 votes
# APL NARS, 559 bytes

```
∇r←l w;t;i;j;c;k;m;p
p←{0=2∣¯1+⍵:.01+2÷⍨¯1+⍵⋄¯0.19+2÷⍨¯1+⍵}
m←{0=2∣¯1+⍵:¯.41+2÷⍨¯1+⍵⋄¯0.21+2÷⍨¯1+⍵}
   r←⍬⋄i←0⋄t←∊(¯1+⍳13),¨13⍴1⋄t←t,2↓t⋄k←⍴t
A: j←i+←1⋄→0×⍳i≥k⋄c←0
B: c+←j⊃t⋄:if(c=w)∧(0≤(m i))∧(24≥(p j))⋄r←r,⊂(m i),(p j)⋄:endif⋄→A×⍳c≥w⋄j+←1⋄→B×⍳j≤k⋄→A
∇
∇r←g w;v;i;k;m
   v←{12≤⌊⍵:⍵-12⋄⍵}
   i←1⋄k←⍴w⋄r←⍬
A: →0×⍳i>k⋄r←r,⊂v¨i⊃w⋄i+←1⋄→A
∇
h←g∘l

```

h(n) or l(n) returns all representative intervals in 0-24 hours that has n clock strikes. h(n) has the clock format as 0..11.0..59; instead l(n) has clock format as 0..23.0..59 test

```
  h 8
    0.59 3.01  1.29 3.31  2.59 4.01  5.29 6.31  6.29 7.01  6.59 7.31
    7.59 8.01  0.59 3.01  1.29 3.31  2.59 4.01  5.29 6.31  6.29 7.01
    6.59 7.31  7.59 8.01
  h 14
    0.29 4.01  0.59 4.31  2.59 5.01  4.29 6.31  5.59 7.01  11.29 0.31
    11.59 1.01  0.29 4.01  0.59 4.31  2.59 5.01 4.29 6.31  5.59 7.01
  h 90
    0.29 0.01  0.59 0.31  1.29 1.01  1.59 1.31  2.29 2.01  2.59 2.31
    3.29 3.01  3.59 3.31  4.29 4.01  4.59 4.31  5.29 5.01  5.59 5.31
    6.29 6.01  6.59 6.31  7.29 7.01  7.59 7.31  8.29 8.01  8.59 8.31
    9.29 9.01  9.59 9.31  10.29 10.01  10.59 10.31  11.29 11.01  11.59 11.31
  h 1
    0.29 0.31  0.59 1.01  1.29 1.31  2.29 2.31  3.29 3.31  4.29 4.31
    5.29 5.31  6.29 6.31  7.29 7.31  8.29 8.31  9.29 9.31  10.29 10.31
    11.29 11.31  0.29 0.31  0.59 1.01  1.29 1.31  2.29 2.31  3.29 3.31
    4.29 4.31  5.29 5.31  6.29 6.31  7.29 7.31  8.29 8.31  9.29 9.31
    10.29 10.31  11.29 11.31
  h 2
    0.29 1.01  0.59 1.31  1.59 2.01  0.29 1.01  0.59 1.31  1.59 2.01
  l 2
    0.29 1.01  0.59 1.31  1.59 2.01  12.29 13.01  12.59 13.31  13.59 14.01

```

---
Tags: code-golf, arithmetic, date, clock
---