title: Printing the Cracker Barrel Game

text:
# Question
Title: Printing the Cracker Barrel Game
**Revised formatting and instructions**

Given a list of moves for a Cracker Barrel peg board game, or as @Steveverrill stated, Peg Triangle Solitaire:

```
Game 1        Game 2         Game 3
1:  0 ,-1, -1   C, -1, -1     4, -1, -1  #starting point
2:  3, 1, 0     3, 7, C       B, 7, 4    #jump_from, jump_over, jump_to
3:  A, 6, 3     0, 1, 3       D, C, B
4:  8, 4, 1     6, 3, 1       5, 8, C
5:  B, 7, 4     5, 2, 0       1, 4, 8
6:  2, 4, 7     C, 8, 5       E, 9, 5
7:  D, C, B     A, B, C       6, 3, 1
8:  9, 5, 2     D, C, B       2, 5, 9
9:  1, 3, 6     9, 5, 2       B, C, D
10: 0, 2, 5     1, 4, 8       9, 8, 7
11: 6, 7, 8     0, 2, 5       0, 1, 3
12: 5, 8, C     5, 8, C       3, 7, C
13: B, C, D     B, C, D       D, C, B
14: E, D, C     E, D, C       A, B, C

```

**Here is your task**

* Write a program that takes a list of moves, each move has three arguments which are slots on the board (jump\_from, jump\_over, jump\_to). Move the peg from jump\_from to jump\_to and remove jump\_over. (If that is unclear then read the instructions linked at the top)
* Print the board for each move
    + The direction of the move a.k.a. the arrow
    + The slot jumped from a.k.a. the `*`
    + The slot jumped to (if peg 3 was in slot 3, and jumped to slot 0, then print a 3 in slot 0)
    + print a `.` for any empty slots

**How to play**

-If you don't understand these rules then there is a link at the top.

I've provided three different games that result in one peg remaining. The idea of the game is to start with one peg missing in the board and remove pegs until there is one left. A move is jumping over a peg into an empty slot and removing the peg you jumped over. Valid moves are diagonals and horizontal moves only. Example (assume slots 1, 2, 3, and 6 are open):

> 8 over 4 to 1 is valid
>
> 8 over 7 to 6 is valid
>
> 8 over 7 or 4 to 3 is invalid
>
> B over 7 and 4 is invalid

Your output should look like the following. Each board printed is one move

(Use hex instead of decimal since printing the board in decimal causes the last row to be too wide)

```
This is Game 1 from the move set at the top

       / 0 \        #This is the board with all slots filled
      / 1 2 \
     / 3 4 5 \
    / 6 7 8 9 \
   / A B C D E \

       / * \        #Move 1: remove the first peg which is 0
      / 1 2 \
     / 3 4 5 \
    / 6 7 8 9 \
   / A B C D E \

       / 3 \        #Move 2: Move peg 3 from slot 3 over slot 1 to slot 0
      / ↗ 2 \       Remove peg 1 from slot 1
     / * 4 5 \
    / 6 7 8 9 \
   / A B C D E \

       / 3 \        #Move 3
      / . 2 \
     / A 4 5 \
    / ↗ 7 8 9 \
   / * B C D E \

       / 3 \        #Move 4
      / 8 2 \
     / A ↖ 5 \
    / . 7 * 9 \
   / . B C D E \

       / 3 \        #Move 5
      / 8 2 \
     / A B 5 \
    / . ↗ . 9 \
   / . * C D E \

       / 3 \        #Move 6
      / 8 * \
     / A ↙ 5 \
    / . 2 . 9 \
   / . . C D E \

       / 3 \       #Move 7
      / 8 . \
     / A . 5 \
    / . 2 . 9 \
   / . D ← * E \

       / 3 \        #Move 8
      / 8 9 \
     / A . ↖ \
    / . 2 . * \
   / . D . . E \

       / 3 \        #Move 9:
      / * 9 \       Move peg 8 from slot 1 over slot 3 to slot 6
     / ↙ . . \      Remove peg A
    / 8 2 . . \
   / . D . . E \

       / * \        #Move 10
      / . ↘ \
     / . . 3 \
    / 8 2 . . \
   / . D . . E \

       / . \        #Move 11
      / . . \
     / . . 3 \
    / * → 8 . \
   / . D . . E \

       / . \        #Move 12
      / . . \
     / . . * \
    / . . ↙ . \
   / . D 3 . E \

       / . \        #Move 13
      / . . \
     / . . . \
    / . . . . \
   / . * → D E \

       / . \        #Move 14
      / . . \
     / . . . \
    / . . . . \
   / . . E ← * \

```

The `*` represents the most recent peg removed. That is why the board starts with a `*` at slot `0` instead of a `0`. `.` represents an empty slot. The slots stay in the same position but the pegs are numbered and move around so for the very last move `peg E moves from slot E over peg/slot D to slot C`

The direction of the move is the unicode characters `u2190` through `u2199`

This is code golf so lowest number of bytes wins. Good Luck!

**If something is unclear don't hesitate to ask. I will do my best to clarify.**

# Answer
> 10 votes
# Ruby `-pa`, 181 bytes

```
$_=b||=+-s=(1..5).map{|i|"/ #{[*:A6310[-i]..?E][0,i]*' '} \\".center 13}*$/+$/
f,o,t=$F.map{|i|s=~/#{i}/}
b.tr!(a='→↙↘*↖↗←',?.)?(b[t],b[o]=b[f],a[(o-f)/7]):$><<b
b[f]=?*

```

Try it online!

The score would be 169 if counted by characters. It's unfortunate that the arrow characters are 3 bytes each, but using them directly is shorter than every method I tried for generating their codepoints (which are irregularly spaced).

## Explanation

The board, stored as a multiline string, is padded out to a rectangular grid with leading and trailing spaces on each line. Let \\$f\\$ and \\$o\\$ be the indices within this string of the slots being jumped from and over, respectively. Then the following table describes all jumps, independent of the specific slots involved:

| Direction | \\$o-f\\$ | \\$\left\lfloor(o-f)/7\right\rfloor\\$ |
| --- | --- | --- |
|  | \\$\phantom{1}{-2}\\$ | \\$-1\\$ |
|  | \\$\phantom{-1}2\\$ | \\$\phantom{-{}}0\\$ |
|  | \\$-15\\$ | \\$-3\\$ |
|  | \\$-13\\$ | \\$-2\\$ |
|  | \\$\phantom{-{}}15\\$ | \\$\phantom{-{}}2\\$ |
|  | \\$\phantom{-{}}13\\$ | \\$\phantom{-{}}1\\$ |

Conveniently, we see that \\$\left\lfloor(o-f)/7\right\rfloor\\$ yields a unique value between \\$-3\\$ and \\$2\\$ for each jump direction, ideal for indexing into a string (`a`) containing the arrow characters.

##### Flags

`-p`: Loop through the code for every line of input and implicitly print the contents of `$_` at the end of each iteration.

`-a`: Form the array `$F` by splitting the input on spaces.

##### Line by line

```
$_=b||=+-s=(1..5).map{|i|"/ #{[*:A6310[-i]..?E][0,i]*' '} \\".center 13}*$/+$/

```

Two boards are saved: `s` is the starting configuration (all slots filled) whereas `b` (shadowed by `$_`) is the current configuration. For each line \\$i\in\[1,5\]\\$ in `s`, slot numbers are generated by taking the first \\$i\\$ elements of a character range beginning with `0`, `1`, `3`, `6`, or `A` and always ending with `E`. Each line is padded with leading and trailing spaces (`.center 13`), the lines are joined by newlines (`*$/`), and a trailing newline is appended (`+$/`).

On the first iteration only, `s` is cloned into `b` (`b||=+-s`). `$_` is set equal to `b` so that the board will be printed at the end of each iteration. Since `b` and `$_` point to the same string object, all subsequent operations on `b` affect `$_` too.

```
f,o,t=$F.map{|i|s=~/#{i}/}

```

Map the input slot numbers to indices in `s`, saving the results in `f` (jump\_from), `o` (jump\_over), and `t` (jump\_to). The mapping is as follows: `0 → 6, 1 → 19, 2 → 21, 3 → 32, 4 → 34, 5 → 36, 6 → 45, 7 → 47, 8 → 49, 9 → 51, A → 58, B → 60, C → 62, D → 64, E → 66`.

```
b.tr!(a='→↙↘*↖↗←',?.)?(b[t],b[o]=b[f],a[(o-f)/7]):$><<b

```

In `b`, replace the `*` and arrow character from the previous jump with `.`. The shouty `.tr!` modifies `b` in place, returning `nil` (falsey) on the first move (no previous jump so no replacements performed) and `b` (truthy) on all other moves. If it is the first move, print the board with all slots filled (`$><<b`). Otherwise, update the jump\_to slot with the peg from the jump\_from slot and set the jump\_over slot to the appropriate arrow character by indexing into `a` as described above.

```
b[f]=?*

```

Set the jump\_from slot to `*`, after which the board is implicitly printed.

---
Tags: code-golf, board-game
---


title: Yet Unused Pairs

text:
# Question
Title: Yet Unused Pairs
Let's define a sequence of positive integers. We will define the value of the sequence at every even index to be double the previous term. The odd indices of the sequence will be smallest positive integer not yet appearing in the sequence.

Here are the first couple terms.

```
1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30

```

You can also think of this as the list of concatenated pairs **(n,2n)** where **n** is the least unused positive integer so far.

## Task

Given a number **n** as input calculate the **n**th term in this sequence.

This is so you should aim to minimize the size of your source code as measured in bytes.

OEIS A036552

# Answer
> 11 votes
## Haskell, 40 bytes

```
l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)

```

Zero-based. `l` incrementally builds the sequence from a lazy list of remaining integers.

# Answer
> 7 votes
## JavaScript (ES6), ~~92~~ ~~82~~ ~~69~~ ~~67~~ 65 bytes

```
n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

```

### How?

We keep track of:

* The last inserted value ***b***.
* All previously encountered values in the lookup table ***a***.

Internally, we're using a 0-based index ***i***. Odd and even behaviors are therefore inverted:

* At odd positions, the next value is simply `2 * b`.
* At even positions, we use the recursive function ***g()*** and the lookup table ***a*** to identify the smallest matching value:

```
(g = k => a[k] ? g(k + 1) : k)(1)

```

To save a few bytes, ***i*** is initialized to `{}` rather than `0`. This compels us to use:

* `i^n` to compare ***i*** with ***n*** because `({}) ^ n === n` whereas `({}) - n` evaluates to `NaN`.
* `-~i` to increment ***i***, because `({}) + 1` would generate a string.

### Demo

```
let f =

n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

for(n = 1; n <= 20; n++) {
  console.log('a[' + n + '] = ' + f(n));
}
```

# Answer
> 5 votes
# Python 3, 80 72 69 bytes

-7 bytes thanks to Mr. Xcoder!

```
f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]

```

Try it online!

# Answer
> 3 votes
# Jelly, 15 bytes

```
Jḟ⁸ḢðḤṭṭ
0Ç¡Ḋị@

```

Try it online!

# Answer
> 3 votes
# PHP, 64 bytes

```
for(;$argn-$i++;)if($i&$$e=1)for(;${$e=++$n};);else$e*=2;echo$e;

```

Try it online!

# PHP, 77 bytes

```
for(;$argn-$i++;$r[]=$e)if($i&1)for(;in_array($e=++$n,$r););else$e*=2;echo$e;

```

Try it online!

# PHP, 78 bytes

```
for(;$argn-$i++;)$e=$r[]=$i&1?end(array_diff(range($i,1),$r?:[])):2*$e;echo$e;

```

Try it online!

# Answer
> 3 votes
# , ~~70~~ ~~69~~ 65 bytes

```
function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)[1]*1:2
F[n]}

```

Try it online!

An anonymous function that takes one argument. `F` defaults to `FALSE` or `0` so that the algorithm correctly assesses that no positive integers are in the sequence yet.

The algorithm generates the pairs in a `for` loop in the following manner (where `i` goes from `2` to `2n` by `2`):

```
           which(!1:n%in%l)[1]     # the missing value
                              *1:2 # keep one copy the same and double the next
l[i-1:0]=                         # store into l at the indices i-1 and i

```

# Answer
> 3 votes
# Mathics, 56 53 bytes

-3 bytes thanks JungHwan Min!

```
(w={};Do[w~FreeQ~k&&(w=w~Join~{k,2k}),{k,#}];w[[#]])&

```

Try it online!

Based on the Mathematica expression given in the OEIS link.

# Answer
> 3 votes
# PHP, 56 bytes

```
while($$n=$i++<$argn)for($n*=2;$i&$$k&&$n=++$k;);echo$n;

```

# PHP, ~~75~~ 72 bytes

```
for($a=range(1,$argn);$i++<$argn;)$a[~-$n=$i&1?min($a):2*$n]=INF;echo$n;

```

Try it online

# Answer
> 3 votes
# Python 2, ~~59~~ ~~51~~ 49 bytes

```
f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)

```

Try it online!

### Background

Every positive **n** integer can be expressed uniquely as **n = 2o(n)c(n)**, where **c(n)** is odd.

Let **⟨ann\>0** be the sequence from the challenge spec.

We claim that, for all positive integers **n**, **o(a2n-1)** is even. Since **o(a2n) = o(2a2n-1) = o(a2n-1) + 1**, this is equivalent to claiming that **o(a2n)** is always odd.

Assume the claim is false and let **2m-1** be the first odd index of the sequence such that **o(a2m-1)** is odd. Note that this makes **2m** be the first even index of the sequence such that **o(a2m-1)** is even.

**o(a2m-1)** is odd and **0** is even, so **a2m-1** is divisible by **2**. By definition, **a2m-1** is the *smallest positive integer not yet appearing in the sequence*, meaning that **a2m-1/2** must have appeared before. Let **k** be the (first) index of **a2m-1/2** in **a**.

Since **o(ak) = o(a2m-1/2) = o(a2m-1) - 1** is even, the minimality of **n** implies that **k** is odd. In turn, this means that **ak+1 = 2ak = a2m-1**, contradicting the definition of **a2m-1**.

### How it works

*yet to come*

# Answer
> 3 votes
# 05AB1E, ~~16~~ ~~15~~ 14 bytes

1-indexed.
Uses the fact that the binary representation of elements at odd indices in the sequence ends in an even number of zeroes: A003159.

```
Lʒb1¡`gÈ}€x¹<è

```

Try it online!

**Explanation**

```
L                 # range [1 ... input]
 ʒ      }         # filter, keep only elements whose
  b               # ... binary representation
   1¡             # ... split at 1's
     `gÈ          # ... ends in an even length run
         €x       # push a doubled copy of each element in place
           ¹<è    # get the element at index (input-1)

```

# Answer
> 2 votes
# Haskell, 63 bytes

```
g x=[2*g(x-1),[a|a<-[1..],a`notElem`map g[1..x-1]]!!0]!!mod x 2

```

Try it online!

This one abuses Haskell's lazy evaluation to the fullest extent.

# Answer
> 2 votes
# Perl 6, 50 bytes

```
{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}

```

Try it online!

* `1, { ... } ... *` is a lazily-generated infinite sequence where each term after the first is provided by the brace-delimited code block. Since the block references the `@_` array, it receives the entire current sequence in that array.
* If the current number of elements is odd (`@_ % 2`), we're generating an even-indexed element, so the next element is double the last element we have so far: `2 * @_[*-1]`.
* Otherwise, we get the first positive integer that does not yet appear in the sequence: `first * ∉ @_, 1..*`.
* `$_` is the argument to the outer function. It indexes into the infinite sequence, giving the function's return value.

# Answer
> 2 votes
# , 27 bytes

```
*|{x,*(&^x?!y;|2*x)2!y}/!2+

```

1-indexed. Try it online!

Using `(!y)^x` instead of `&^x?!y` works too.

# Answer
> 1 votes
# Mathematica, 82 bytes

```
(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&

```

Try it online!

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 82 bytes

```
x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}

```

Try it online!

-6 bytes thanks to @ASCIIOnly!

# Answer
> 1 votes
# JavaScript, 51 bytes

After golfing this down, it pretty much turned into edc65's solution.

```
n=>(g=x=>g[++x]?g(x):(g[y=x*2]=--n)?--n?g(x):y:x)``

```

Try it online!

# Answer
> 0 votes
## Clojure, 102 bytes

```
#(nth(loop[l[0 1 2 3]i %](if(= i 0)l(recur(conj l(*(last l)2)(nth(remove(set l)(range))0))(dec i))))%)

```

Iterates `n` times to build up the sequence and returns the `n`th item, 1-indexed.

# Answer
> 0 votes
# Ruby, 60 bytes

```
->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}

```

0-indexed. We loop `n/2+1` times, generating two values each time and storing them by populating an array at their indices. `v+v*n%2` gives the output, either `v` or `v*2` depending on the parity of `n`.

# Answer
> 0 votes
# Jelly, ~~13~~ ~~12~~ 10 bytes

```
ḤRọ2ḂĠZFị@

```

This uses the observation from my Python answer.

Try it online!

### How it works

```
ḤRọ2ḂĠZFị@  Main link. Argument: n

Ḥ           Unhalve; yield 2n.
 R          Range; yield [1, ... , 2n].
  ọ2        Compute the order of 2 in the factorization of each k in [1, ..., 2n].
    Ḃ       Bit; compute the parity of each order.
     G      Group the indices [1, ..., 2n] by the corresponding values.
      Z     Zip/transpose the resulting 2D array, interleaving the indices of 0
            with the indices of 1, as a list of pairs.
       F    Flatten. This yields a prefix of the sequence.
        ị@  Take the item at index n.

```

# Answer
> 0 votes
# Ruby, 49 bytes

```
->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}

```

Start with \[0\], add pairs to the array until we have at least n+1 elements, then take the n+1th (1-based)

Try it online!

# Answer
> 0 votes
# JavaScript (ES6), 60 ~~65~~ bytes

An iterative solution.

```
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

```

*Less golfed*

```
n=>{
  s = {}; //hashtable for used values
  for(i=0; n; )
  {
    if ( ! s[++i] )
    {
      s[i*2] = 1; // remember i*2 is already used
      if (--n)
        if (--n)
          0;
        else
          result = i*2;
      else
        result = i;
    }
  }
  return result;
}

```

**Test**

```
F=
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

for (a=1; a < 50; a++)
  console.log(a,F(a))
```

# Answer
> 0 votes
# Husk, 18 bytes

```
!ṁSeDfȯ¬%2öL→x1ḋḣ¹

```

Try it online!

Same method as the 05AB1E solution from Emigna.

Both are 1-indexed.

# Husk, 19 bytes

```
!!¡S+ȯSeD←S-ȯḣ→▲ḣ2¹

```

Try it online!

Uses infinite iteration to generate the sequence.

## Explanation

```
!!¡S+ȯSeD←S-ȯḣ→▲ḣ2¹
                ḣ2  array [1,2]
  ¡                 apply function repeatedly on array, yielding intermediate results
   S                hook: S f g x = s f x (g x)
    +               f → list addition
     ȯ              g → compose 3: ȯ f g h x = f (g (h x))
      S                 f → hook: S f g x = s f x (g x)
       e                    f → list of two elements
        D                   g → number doubled
         ←              g → decrement
          S             h → hook: S f g x = s f x (g x)
           -                f → list subtraction
            ȯ               g → compose 3: ȯ f g h x = f (g (h x))
             ḣ                  f → range 1..n
              →                 g → increment
               ▲                h → maximum
                    altogether, this appends the first element of
                    1..max+1 not in the array,
                    and it's double.
 !                  take the nth result
!                   take the nth value

```

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


title: Boustrophedon transform

text:
# Question
Title: Boustrophedon transform
Related: Boustrophedonise, Output the Euler Numbers (Maybe a new golfing opportunity?)

## Background

Boustrophedon transform (OEIS Wiki) is a kind of transformation on integer sequences. Given a sequence \\$a\_n\\$, a triangular grid of numbers \\$T\_{n,k}\\$ is formed through the following procedure, generating each row of numbers in the back-and-forth manner:

$$ \swarrow \color{red}{T\_{0,0}} = a\_0\\ \color{red}{T\_{1,0}} = a\_1 \rightarrow \color{red}{T\_{1,1}} = T\_{1,0}+T\_{0,0} \searrow \\ \swarrow \color{red}{T\_{2,2}} = T\_{1,0}+T\_{2,1} \leftarrow \color{red}{T\_{2,1}} = T\_{1,1}+T\_{2,0} \leftarrow \color{red}{T\_{2,0}} = a\_2 \\ \color{red}{T\_{3,0}} = a\_3 \rightarrow \color{red}{T\_{3,1}} = T\_{3,0} + T\_{2,2} \rightarrow \color{red}{T\_{3,2}} = T\_{3,1} + T\_{2,1} \rightarrow \color{red}{T\_{3,3}} = T\_{3,2} + T\_{2,0} \\ \cdots $$

In short, \\$T\_{n,k}\\$ is defined via the following recurrence relation:

$$ \begin{align} T\_{n,0} &= a\_n \\ T\_{n,k} &= T\_{n,k-1} + T\_{n-1,n-k} \quad \text{if} \\; 0\<k\le n \end{align} $$

Then the Boustrophedon transform \\$b\_n\\$ of the input sequence \\$a\_n\\$ is defined as \\$b\_n = T\_{n,n}\\$.

More information (explicit formula of coefficients and a PARI/gp program) can be found in the OEIS Wiki page linked above.

## Task

Given a finite integer sequence, compute its Boustrophedon transform.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[10] -> [10]
[0, 1, 2, 3, 4] -> [0, 1, 4, 12, 36]
[0, 1, -1, 2, -3, 5, -8] -> [0, 1, 1, 2, 7, 15, 78]
[1, -1, 1, -1, 1, -1, 1, -1] -> [1, 0, 0, 1, 0, 5, 10, 61]

```

Brownie points for beating or matching my 10 bytes in ngn/k or 7 bytes in Jelly.

# Answer
# Jelly, 7 bytes

```
;UÄµ\Ṫ€

```

Try It Online!

Given the previous row, we can reverse it, append it to the next element in the source list, and cumulatively sum. (Reverse + append-to is the same as append + reverse)

Therefore:

```
;UÄµ\Ṫ€    Main Link
    \      Cumulatively reduce the source list; each time, with the
           last row as the left and the next element as the right:
;          Append the element to the last row
 U         Reverse the whole thing
  Ä        Cumulative sum
     Ṫ€    Get the last element of each

```
> 7 votes

# Answer
# K (oK), ~~47~~ ~~42~~ 41 bytes

```
f:{i{$[y;o[x;y-1]+o[x-1;x-y];a x]}'i:!#a:x}

```

Try it online!

A function taking an array of numbers. -5 thanks to ngn. -1 thanks to Razetime.

```
{                          // A function returning...
  {                        // A function, returning
    $[                     // A switch statemnet
      y;                   // If y (second arg) is nonzero
      o[x;y-1]+o[x-1;x-y]; // Do a recursive call
      a x                  // Else index x into a
    ]
  }'i:                     // Call with the first argument as both arguments
  '!#a:x}                    // Map this over a range of the same length as the input, which we also assign to a for later use

```
> 4 votes

# Answer
# JavaScript (ES6), 56 bytes

```
a=>a.map(g=(k,n,x)=>x?g(n,n):k?g(k-1,n)+g(n-k,n-1):a[n])

```

Try it online!
> 3 votes

# Answer
# JavaScript (Node.js), 59 bytes

```
a=>a.map((_,i)=>(T=(n,k)=>k?T(n,k-1)+T(n-1,n-k):a[n])(i,i))

```

Try it online!

Copying the formula described in the question.

```
a => a.map(                           // Map a
  (_, i) =>                           // By index, we don't care about the content of a, just that it's the right length
  ( T = (n, k) =>                     // Declare a function T, taking n and k
      k ?                             // If k is nonzero...
        T(n, k - 1) + T(n - 1, n - k) // Do a recursive call
      : a[n]                          // Else index n into a
  )(i, i))                            // Call this function with i,i as arguments.

```
> 1 votes

# Answer
# Jelly, 22 bytes

```
’1ŀ_+1ŀ’}¥ð‘ị³ðṛ?
J’Ç€

```

Try it online!

Horrible recursive definition, I'm sure there's a better approach. Full program. Here's a modified version to run as a test suite.

## How it works

We just implement

$$T(n,k) = \begin{cases} a\_n & \text{if } k = 0 \\ T(n-1,n-k) + T(n, k-1) & \text{otherwise} \end{cases}$$

then calculate \\$T(i,i)\\$ for each index \\$i\\$ of \\$a\\$

The first line defines \\$T(n,k)\\$, and the second calculates \\$T(i,i)\\$ for each index \\$i\\$.

```
’1ŀ_+1ŀ’}¥ð‘ị³ðṛ? - Helper link. T(n,k).
               ṛ? - If k:
          ð       -   Then:
’                 -     n-1
   _              -     n-k
 1ŀ               -     T(n-1, n-k)
         ¥        -     Last two links as a dyad g(n,k):
       ’}         -       k-1
     1ŀ           -       T(n, k-1)
    +             -     T(n-1, n-k) + T(n, k-1)
              ð   -   Else:
           ‘      -     n+1 (due to Jelly's 1 indexing)
            ị³    -     Index into a

J’Ç€ - Main link. Takes a on the left
J    - Indices of a
 ’   - Decrement to 0 index
   € - Over each index i:
  Ç  -   Yield T(i,i)

```
> 1 votes

# Answer
# Charcoal, 20 bytes

```
ＦＡ«⊞υιＵＭυΣ…⮌υ⊕λＩ✂υ±¹

```

Try it online! Link is to verbose version of code. Explanation:

```
ＦＡ«

```

Loop over the input list.

```
⊞υι

```

Push the current input value to the Boustrophedon list.

```
ＵＭυΣ…⮌υ⊕λ

```

Take the sums of all the nontrivial suffixes of the list to produce the new list.

```
Ｉ✂υ±¹

```

Output the last member of the new list on its own line.
> 0 votes

# Answer
# Ruby, 62 bytes

```
->l{l.size.times.map &g=->n,k=n{k<1?l[n]:g[n,k-1]+g[n-1,n-k]}}

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 9 bytes

```
Å»ª.sO}€θ

```

Port of *@hyper-neutrino♦*'s Jelly answer, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
Å»      # Cumulative left-reduce the (implicit) input-list by:
  ª     #  Appending the current item to the list
   .s   #  Get the suffices of this list
     O  #  Sum each inner list together
 }€θ    # After the reduce, only leave the last element of each inner list
        # (after which the list is output implicitly as result)

```
> 0 votes

---
Tags: code-golf, math, sequence, integer
---


title: Write a JSON validator

text:
# Question
Title: Write a JSON validator
Write a program that determines whether its input is valid JSON.

* **Input:** ASCII text: `[\x00-\x7F]*`

*Note: if ASCII is problematic, feel free to use another encoding, but indicate it in your post.*
* **Output:** `Valid` or `Invalid`. Trailing newline may be omitted.
* **Example:**

```
 $ echo '{"key": "value"}' | ./json-validate
 Valid
 $ echo '{key: "value"}' | ./json-validate
 Invalid

```
* **Rules:**

+ Do not use a JSON parsing library.
    + Partially-correct solutions are allowed, but frowned upon.
    + Post your test suite score (see below).

The **shortest correct** solution wins.

Please run json-validate-test-suite.sh on your program, and post your score. Example:

```
$ ./json-validate-test-suite.sh ./buggy-prog
fail: should be invalid:  [ 0.1e ]
fail: should be invalid:  [ 0.1e+-1 ]
fail: should be invalid:  [ 0.1e-+1 ]
score: 297/300

```

**Resources:**

* json.org \- Concise definition of the JSON grammar with easy-to-follow pictures.
* RFC 4627 \- JSON specification
* json-validate.c \- A 200-line implementation that passes the testsuite.

---

The JSON grammar is as follows:

```
json: object | array

object: '{' members? '}'
    members: pair (',' pair)*
    pair:    string ':' value

array: '[' elements? ']'
    elements: value (',' value)*

value: string
     | number
     | object
     | array
     | 'true'
     | 'false'
     | 'null'

string: '"' char* '"'
    char: [^"\\\x00-\x1F]
        | '\' escape
    escape: ["\\/bfnrt]
          | u [0-9A-Fa-f]{4}

number: '-'? (0 | [1-9][0-9]*) ('.' [0-9]+)? ([Ee] [+-]? [0-9]+)?

```

Also, whitespace can appear before or after any of the six structural characters `{}[]:,`

```
ws = [\t\n\r ]*

```

Bear in mind the following:

* Be careful with functions like `isspace()`. Whitespace in JSON is `[\t\n\r ]`, but `isspace()` also treats `\v` (vertical tab) and `\f` (form feed) as space. Although word has it that `isdigit()` can accept more than just `[0-9]`, should be okay to use here, as we assume input is in ASCII.
* `\x7F` is technically a control character, but the JSON RFC doesn't mention it (it only mentions `[\x00-\x1F]`), and most JSON parsers tend to accept `\x7F` characters in strings. Because of this ambiguity, solutions may choose to either accept them or not.

# Answer
# PHP : ~~297~~ ~~285~~ ~~264~~ 253 characters

```
<?=preg_match(<<<'R'
~([\h
]*)({(?1)((("([^"\\\0- ]| |\\(["\\/bfnrt]|u[\dA-Fa-f]{4}))*")(?1):(?1)((?5)|-?(0|[1-9]\d*)(\.\d+)?([Ee][+-]?\d+)?|(?2)|true|false|null))(((?1),(?1))(?4))*)?}|\[(?1)((?8)((?13)(?8))*)?(?1)])(?1)\z~A
R
,`cat`)?'Valid':'Invalid';

```

**score: 300/300**

This is a full, recursive implementation of the JSON grammar.

It works only on PHP ≥ 5.3 due to nowdoc syntax (heredoc would have required to double all `\`).

Readable version:

(this is the same regex, with named capture groups and extended syntax):

```
#!/usr/bin/env php
<?php

$re = <<< 'RE'
~\A (?P<ws>[\t\n\r ])* (
    (?P<object>\{ (?P>ws)*
        (?P<members>
            (?P<pair>
                (?P<string>
                    "(?P<char>
                        [^"\\\x00-\x1F]
                        |\\(?P<escape>
                            ["\\/bfnrt]
                            |u [0-9A-Fa-f]{4}
                        )
                    )*"
                ) (?P>ws)* : (?P>ws)* (?P<value>
                    (?P>string)
                    | (?P<number>-? (0 | [1-9][0-9]*) (\. [0-9]+)? ([Ee] [+-]? [0-9]+)? )
                    | (?P>object)
                    | (?P>array)
                    | true
                    | false
                    | null
                )
            ) ( (?P>ws)* , (?P>ws)* (?P>pair) )*
        )?
    \})
    |(?P<array>\[ (?P>ws)*
        (?P<elements>
            (?P>value) ( (?P>ws)* , (?P>ws)* (?P>value) )*
        )?
    (?P>ws)* \])
) (?P>ws)* \z~x
RE;

if (preg_match($re, stream_get_contents(STDIN))) {
    echo 'Valid';
} else {
    echo 'Invalid';
}

```
> 8 votes

# Answer
## Python - ~~340~~ ~~314~~ ~~299~~ 292 chars

```
import re,os
r=x=re.sub
z=r('0\.0+','0',r('e[+-]?0+|[\t\n\r]',' ',r(r'"(\\["nrtb\\/]|[^\\"\0-\37])*"','1',r(r'true|false|null|\\u\w{4}|[1-9]\d*','0',os.read(0,99)))))
while z!=x:z,x=r('\{(1:\d)?(,\\1)*\}|\[(-?\d(,-?\d)*)?\]','0',r(' *([][{}:,]) *','\\1',z)),z
print['Inv','V'][z=='0']+'alid'

```

score

```
$ ./json-validate-test-suite.sh ./codegolf-474.py
score: 300/300

```
> 6 votes

# Answer
## Scala - 390 chars

```
import scala.util.parsing.combinator.JavaTokenParsers
object J extends JavaTokenParsers{def j=o|a
def o:Parser[Any]="{"~repsep(p,",")~"}"
def p=s~":"~v
def a:Parser[Any]="["~repsep(v,",")~"]"
def v=s|o|a|"true"|"false"|"null"
def s=stringLiteral
def n=floatingPointNumber}
object Main{def main(a:Array[String]){print(if(J.parseAll(J.j,readLine()).successful)"Valid"else"Invalid")}}

```

This is no-brainer soluton, using parser combinators. Written in 1 or 2 minutes, literally. Cannot get validator script, browser said that server not found.
> 3 votes

# Answer
# Bash \+ jq, 29 bytes

```
jq -r '"Valid"'||echo Invalid

```

Try it online!

TIO's bash instance conveniently has jq installed for us so try it online at your leisure!
> 1 votes

---
Tags: code-golf
---


# Question
Title: Convert JSON string to Key / Value Arrays
Convert JSON (key/value pairs) to two native arrays, one array of keys and another of values, in your language.

```
var X = '{"a":"a","b":"b","c":"c","d":"d","e":"e","f":"f9","g":"g2","h":"h1"}';

```

The value array could be an array of strings or integers.

So we need two functions **keys** & **vals**, returning native arrays on input of JSON string.

In above example the output would be:

```
keys : ["a", "b", "c", "d", "e", "f", "g", "h"]
vals : ["a", "b", "c", "d", "e", "f9", "g2", "h1"]

```

Here is my attempt at this using javascript:

**keys** : (53 Chars)

```
function keys(X){return X.match(/[a-z0-9]+(?=":)/gi)}

```

**vals** : (56 Chars)

```
function vals(X){return X.match(/[a-z0-9]+(?="[,}])/gi)}

```

Can other languages challenge this??

# Answer
> 7 votes
### Python, 27/30

To actually comply with the rules:

```
keys=lambda x:list(eval(x))
vals=lambda x:eval(x).values()

```

### Python, 30

Just using one function:

```
lambda x:zip(*eval(x).items())

```

This will separate the keys from the values and return them in a list.

### Python, 7

If returning a dictionary is allowed, then this is all you need:

```
eval(x)

```

# Answer
> 5 votes
## APL 32

Index origin 1. If you will accept the keys and values being returned as a two row array then a simple one liner will do the job in APL. This takes screen input via ←⍞

```
⍉((.5×⍴j),2)⍴j←(~j∊'{":;,}')⊂j←⍞

```

Taking the given example as input:

```
{"a":"a","b":"b","c":"c","d":"d","e":"e","f":"f9","g":"g2","h":"h1"};

a b c d e f  g  h
a b c d e f9 g2 h1

```

# Answer
> 2 votes
## Perl 28 bytes

Instead of 2 separate functions to return keys and values, I'm returning both in the form of a `hash`.

```
sub j2h{eval pop=~y/:"/,/dr}

```

Sample usage:

```
$_='{"a":"a","b":"b","c":"c","d":"d","e":"e","f":"f9","g":"g2","h":"h1"}';
%h=j2h($_);
print $h{f}; # prints f9
print $h{g}; # prints g2

```

It even works for arbitrarily deeply nested variables:

```
$_='{"a":{"b":{"c":"c3","d":"d4"},"c":"c5"},"b":"b6"}';
%h=j2h($_);
print $h{a}{b}{d}; # prints d4
print $h{a}{c};    # prints c5

```

# Answer
> 2 votes
# Tcl 69,69

first attempt 132 keys+vals

```
proc j {x n} {
regsub -all {(".*?"):(".*?")} $x "\[lappend o \\$n\]" x
subst $x
set o $o
}
proc keys x {j $x 1}
proc vals x {j $x 2}

```

second try 69 keys, 69 values

```
proc keys x {regsub -all {(".*?"):(".*?").} $x {\1 } x
lindex $x\} 0}

proc vals x {regsub -all {(".*?"):(".*?").} $x {\2 } x
lindex $x\} 0}

```

# Answer
> 1 votes
# K, 22

```
{+`$":"\:'","\:1_-1_x}

```

The double quotes in the input string have to be escaped

```
k){+`$":"\:'","\:1_-1_x} "{\"a\":\"a\",\"b\":\"b\",\"c\":\"c\",\"d\":\"d\",\"e\":\"e\",\"f\":\"f9\",\"g\":\"g2\",\"h\":\"h1\"}"
"a" "b" "c" "d" "e" "f"  "g"  "h"
"a" "b" "c" "d" "e" "f9" "g2" "h1"

```

For the same bytecount you could just read from stdin

```
+`$":"\:'","\:1_-1_0:0

```

.

```
k)+`$":"\:'","\:1_-1_0:0
{"a":"a","b":"b","c":"c","d":"d","e":"e","f":"f9","g":"g2","h":"h1"}
"a" "b" "c" "d" "e" "f"  "g"  "h"
"a" "b" "c" "d" "e" "f9" "g2" "h1"

```

# Answer
> 1 votes
## PHP, 56/58

Pssh, PHP has functions for this stuff (although it won't win the shortest answer award).

```
function keys($j){return array_keys(json_decode($j,1));}
function vals($j){return array_values(json_decode($j,1));}

```

# Answer
> 1 votes
# APL (Dyalog Unicode), 18 bytesSBCS

Anonymous tacit prefix function. Prints list of keys, then returns list of values.

```
'⍎¨⎕←⎕NL¯2'⍎⍨⎕JSON

```

Try it online!

`⎕JSON` convert JSON string to APL namespace object

`'``'⍎⍨` in that namespace, execute the following code:

`⎕NL¯2` name list for all all variables

`⎕←` print that list

`⍎¨` execute each name

# Answer
> 1 votes
# PowerShell, ~~34/36~~ 28/28 bytes

-14 bytes total thanks to @mazzy!

To fetch the keys:

```
&(gcm *F*son)"$args" -a|% k*

```

Try it online!

To fetch the values:

```
&(gcm *F*son)"$args" -a|% v*

```

Try it online!

Kinda cheap, as it uses the built-in method `ConvertFrom-Json -AsHashtable` to convert the data from JSON.

# Answer
> 1 votes
# ECMAScript

I'm surprised no one has proposed a better ECMAScript solution, so here's my simple attempt:

**keys**: (29 chars)

```
X=>Object.keys(JSON.parse(X))
```

**values**: (31 chars)

```
X=>Object.values(JSON.parse(X))
```

# Answer
> 1 votes
# C (gcc), 103 bytes

```
char*b[99],**o,*l;f(s,n)char*s;{for(o=b;*s++;l=*s-34?l:++n%4?s+1:(*o++=strndup(l,s-l)));*o=0;return b;}

```

Try it online!

Usage:

`f(input, 2)` returns an array with the keys

`f(input, 0)` returns an array with the values

# C (clang), 67 bytes

```
*l;f(*s,n){for(;*s++;l=*s-34?l:++n%4?s+1:printf("%.*ls\n",s-l,l));}

```

Writes the output to stdout instead of returning arrays.

Try it online!

# Answer
> 1 votes
# jq, 11–∞ bytes

Try it online!

This answer will take some refining, as I'm not yet clear on the rules. It states that two functions are required, but jq doesn't have functions and I don't know how much of our current meta consensus applies to such old posts

The essence is in two snippets:

* keys: `keys`
* values: `[.[]]`

These are both valid jq programs that each give their respective piece. Counted like this we have 11 bytes. We can also do:

```
# Return an array of arrays as [keys, values]
[keys, [.[]]]

```

```
# Return another nice JSON as {"keys": keys, "values": values}
{keys:keys, values:[.[]]}

```

I'll add a bit more explanation when the final entry is clearer.

# Answer
> 0 votes
# CoffeeScript:

```
vals = []
keys = []
vals.push(v) and keys.push(k) for own k, v of JSON.parse(X)

```

# Answer
> 0 votes
## **Ruby, 19**

`eval X.gsub':','=>'`

Similar, unsurprisingly, to the Perl solution. The Ruby 1.9 literal for a `Hash` would be identical to the input form if it weren't for the quoted keys; as it is we just need to convert the colons to `=>`.

# Answer
> 0 votes
# Lua

```
function keys(x)return loadstring("return"..x:gsub(':".-"',''))()end
function vals(x)return loadstring("return"..x:gsub('"[^"]*":',''))()end

```

68 and 71 chars

# Answer
> 0 votes
## Tcl 8.6, 82

```
 package r json;lmap keys [dict k [set d [json::json2dict $X]]] vals [dict v $d] {}

```

The Tcl core is (unlike php) very small.
This requires the tcllib, which is available as package for most linux distributions.
I use this library because too much languages have a json\_parse build in.

# Answer
> 0 votes
# PHP 7.4+, 39/41 bytes

(demo)

The keys via closure with PHP7.4 arrow function syntax: 39 bytes

```
(fn()=>array_keys(json_decode($X,1)))()

```

The values via closure with PHP7.4 arrow function syntax: 41 bytes

```
(fn()=>array_values(json_decode($X,1)))()

```

# Answer
> 0 votes
**Python 3 (Total 35 characters)**

*Input JSON String*

```
X = '{"a":"a","b":"b","c":"c","d":"d","e":"e","f":"f9","g":"g2","h":"h1"}'

```

**Get Keys(16 characters)**

```
k=eval(X).keys()

```

**Get Values(18 characters)**

```
v=eval(X).values()

```

Try online

# Answer
> 0 votes
# Burlesque, 12 bytes

```
'";;:an2cou[

```

Try it online!

```
'";; # Split by "s
:an  # Filter by alphanumeric
2co  # Group in pairs
u[   # Unzip giving array of vals and array of keys

```

---
Tags: code-golf, array, javascript, json
---


title: Distinct Subset Sums: Extending A276661

text:
# Question
Title: Distinct Subset Sums: Extending A276661
Consider the integer set \\$S = \\{3, 5, 6, 7\\}\\$. If we list all \\$2^n\\$ subsets of \\$S\\$ (its powerset) and calculate their sums, we get

$$ \mathcal{P}(S) = \\{\emptyset, \\{3\\}, \\{5\\}, \\{6\\}, \\{7\\}, \\{3, 5\\}, \\{3, 6\\}, \\{3, 7\\}, \\{5, 6\\}, \\{5, 7\\}, \\{6, 7\\}, \\{3, 5, 6\\}, \\{3, 5, 7\\}, \\{3, 6, 7\\}, \\{5, 6, 7\\}, \\{3, 5, 6, 7\\}\\} \\ \sum\_{s \in \mathcal{P}(S)} s = \\{0, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 21\\} $$

You'll note that this set of sums is distinct - no element is repeated. We'll say that \\$S\\$ is a **distinct subset sum set**. Note that we're only considering sets containing positive integers for this.

In fact, for \\$n = 4\\$, \\$k = 7\\$ is the smallest positive integer such that there is a set \\$S\\$ containing \\$n\\$ distinct elements from the set \\$\\{1, 2, ..., k\\}\\$ and that \\$S\\$ is a distinct subset sum set. The values of \\$k\\$ for \\$n = 0, 1, 2, 3\\$ are:

| \\$n\\$ | \\$k\\$ | \\$S\\$ |
| --- | --- | --- |
| \\$0\\$ | \\$0\\$ | \\$\emptyset\\$ |
| \\$1\\$ | \\$1\\$ | \\$\\{1\\}\\$ |
| \\$2\\$ | \\$2\\$ | \\$\\{1,2\\}\\$ |
| \\$3\\$ | \\$4\\$ | \\$\\{1,2,4\\}\\$ |

For any given \\$n\\$, we can say that \\$2^{n-1}\\$ is an upper bound, as the set \\$\\{2^0, 2^1, ..., 2^{n-1}\\}\\$ is always a distinct subset sum set.

However, as shown above, this upper bound can be improved. In fact, one of the current best upper bounds is the Conway-Guy sequence (A005318), given by:

$$ a\_0 = 0, a\_1 = 1\\ a\_{n+1} = 2a\_n - a\_{n - \lfloor 1/2 + \sqrt{2n} \rfloor} $$

However, it's been shown that \\$a\_{67} = 34808838084768972989\\$ can be improved as a bound to \\$34808712605260918463\\$, so the Conway-Guy sequence is currently only an upper bound (and a non-optimal one at that), rather than the exact terms. The exact terms are given by A276661.

This sequence has only been proven to be optimal up to \\$n = 9\\$. Your task is to improve this.

Your program should take a non-negative integer \\$n\\$ and output the smallest integer \\$k\\$ such that there exists a distinct subset sum set \\$S\\$ such that, for all elements \\$S\_i\\$, \\$1 \le S\_i \le k\\$. Note that this is *not* the Conway-Guy sequence; if given \\$n = 67\\$ as an input, the output should not be \\$34808838084768972989\\$.

Your program may fail *practically* due to integer constraints (e.g. if the output exceeds your language's integer maximum), but should work *theoretically* for all \\$n\\$.

This is , so the shortest code in bytes wins.

---

Additionally, I will offer a bounty for the answer for which:

* it can produce the correct output for a value \\$x \> 9\\$ within a minute (time using TIO if possible), and
* it can produce the correct output for all values \\$1 \le i \le x\\$ within a minute for each

The bounty will be awarded to the answer which can do this for the highest \\$x\\$. The amount I'll award will depend on the exact value of \\$x\\$ (e.g. \\$x = 20\\$ will be awarded more than \\$x = 10\\$), but it will be at least 150 reputation. Once someone can produce the output for \\$x = 10\\$, I'll wait 2 weeks for any answers to try to beat it, then start the bounty.

---

## Test cases

```
n   k
0   0
1   1
2   2
3   4
4   7
5  13
6  24
7  44
8  84
9 161

```

# Answer
> 3 votes
# Vyxal `R`, 13 bytes

```
λ?↔'ṗv∑:U⁼;;ṅ

```

Try it Online!

Outputs in a singleton list.

```
λ          ;ṅ # First integer for which the following is true:
   '      ;   # Any of...
 ?↔           # combinations_with_replacements(1..n,input)
   '      ;   # Has the property that...
    ṗv∑       # Sums of all subsets
       :U⁼    # Are all unique

```

# Answer
> 3 votes
# Python 3.8 (pre-release), 169 bytes

```
from itertools import*
f=lambda i,n=2:any(len(k:=[*map(sum,chain(*[combinations(x,r)for r in range(n)]))])==len({*k})for x in product(*[range(1,n)]*i))and~-n or f(i,n+1)

```

Try it online!

Mighty itertools

-15 thanks to @ovs

# Answer
> 3 votes
# Python 2 (PyPy), ~~111~~ ~~102~~ 96 bytes

Finishes for \\$n=7\\$ in three seconds, every larger \\$n\\$ takes too long on TIO.

```
f=lambda n,i=1,s=[(0,1)]:n>max(zip(*s)[0])and-~f(n,i+1,s+[(w+1,l|l<<i)for w,l in s if l<<i&l<1])

```

Try it online!

The list `s` keeps track of all valid sets up to size `k`, storing a set as its length and the possible sums represented by a bitmask. This improves performance over regular sets and makes adding a new number as simple as `l|l<<i`.

With some small optimizations this finishes in under a second for \\$n=7\\$: Try it online!
\\$n=8\\$ is still far out on TIO (1m30s and 15GB RAM locally)

# Answer
> 2 votes
# Jelly, 11 bytes

```
ṗŒP§QƑƊƇ¥1#

```

Try it online!

A monadic link taking and returning an integer. Terribly inefficient since it takes the powerset of the Cartesian power. Replacing  with `œc` improves efficiency at the cost of a byte, but still very slow.

# Answer
> 2 votes
# JavaScript (ES10), 136 bytes

Slightly shorter. Much slower.

```
n=>(g=k=>{for(v=++k**n;v--*!(new Set([...Array(n)].reduce((a,_,i)=>a.flatMap(x=>[x,x+v/k**i%k|0]),[0])).size>>n););return~v?0:1+g(k)})``

```

Try it online!

---

# JavaScript (ES7), 138 bytes

```
n=>(g=k=>{for(v=++k**n;v--*!(new Set([...Array(n)].reduce((a,_,i)=>[...a,...a.map(x=>x+v/k**i%k|0)],[0])).size>>n););return~v?0:1+g(k)})``

```

Try it online!

# Answer
> 1 votes
# Charcoal, ~~64~~ 46 bytes

```
Ｎθ≔¹η⊞υ¹Ｗ¬⊙υ⁼Σ↨κ²Ｘ²θ«≦⊗ηＦυ¿¬＆κ×ηκ⊞υ×⊕ηκ»Ｉ⊖Ｌ↨η²

```

Try it online! Link is to verbose version of code. Too slow to do `n>6` on TIO. Explanation:

```
Ｎθ

```

Input `n`.

```
≔¹η

```

Start with `2ᵏ=1`.

```
⊞υ¹

```

The empty set has one subset sum, `{0}`, represented here as a bitmask of `2⁰=1`.

```
Ｗ¬⊙υ⁼Σ↨κ²Ｘ²θ«

```

Repeat until a subset sum set of size `2ⁿ` is found.

```
≦⊗η

```

Increment `k`.

```
Ｆυ

```

Loop over all of the sets so far.

```
¿¬＆κ×ηκ

```

If adding `k` to each subset sum (achieved by shifting the bitmask left by `k` bits) does not duplicate any existing sum, then ...

```
⊞υ×⊕ηκ

```

... add the combined subset sum set to the list.

```
»Ｉ⊖Ｌ↨η²

```

Extract the value of `k` needed to get a set of size `n`.

# Answer
> 1 votes
# 05AB1E, 16 bytes

```
Āi∞.ΔLIãεæODÙQ}à

```

Try it online or verify increasing test cases until it times out.

**Explanation:**

```
Āi              # If the (implicit) input is not 0:
  ∞.Δ           #  Find the first positive integer which is truthy for:
     L          #   Pop the integer, and push a list in the range [1,n]
      Iã        #   Take the cartesian power of the input-integer
        ε       #   Map each inner list to:
         æ      #    Take the powerset of this list
          O     #    Sum each inner list
                #    Check if all items are unique by:
           D    #     Duplicating the list
            Ù   #     Uniquify the copy
             Q  #     Check if the lists are still the same
        }à      #   After the map: check if any were truthy (by taking the max)
                #  (after which the integer is output implicitly as result)
                # (implicit else: output the implicit input; the 0)

```

---
Tags: code-golf, sequence, combinatorics, set-theory
---


title: Draw constraint system #18762389

text:
# Question
Title: Draw constraint system #18762389
## Background

Page 219 of *A New Kind of Science* (a book by Stephen Wolfram, the creator of Mathematica) shows an interesting 2D pattern generated by constraints. The relevant section in the book starts at page 210; you can browse other pages for more context.

In short, the large binary image is the result generated by 12 **constraints** at the bottom, along with an extra condition that two black cells stacked vertically must appear somewhere on the grid. The constraints describe that, for every cell in the (infinite) pattern, the cell itself combined with its four neighbors must match one of the constraints given. The book describes this pattern as "the simplest system based on constraints that is forced to exhibit a non-repetitive pattern". An interesting fact is that the sequence of antidiagonals describes the binary pattern of all integers (including positive and negative).

## Task

The task is to replicate a finite region at the center of this infinite pattern. For this task, the **center** of this pattern is defined to be the endpoint of the semi-infinite antidiagonal of black cells (which does not include the part of the upper-right stripes).

The input is a positive odd number \\$n\\$. You may choose to take the value of \\$\left\lfloor \frac{n}{2}\right\rfloor\\$ (0-based integers) or \\$\left\lceil \frac{n}{2}\right\rceil\\$ (1-based) instead.

The output is the square region of \\$n \times n\\$ cells centered at the center cell defined above. See test cases below for exact output. The output format is flexible; you may choose any two distinct values (numbers or chars) for black and white cells respectively, and any structure that exhibits the 2D grid is acceptable (e.g. nested arrays or strings delimited by newlines).

Standard rules apply. The shortest code in bytes wins.

## Test cases

Uses `X` for black and `.` for white cells. Note that your program should (at least theoretically) give the correct pattern for arbitrarily large \\$n\\$.

```
n = 1
X

n = 3
.XX
.X.
X..

n = 7
.XXXXXX
.X.....
...XXXX
.X.X...
..X..XX
.X...X.
X......

n = 15
.XXXXXXXXXXXXXX
.X.............
...XXXXXXXXXXXX
.X.X...........
..X..XXXXXXXXXX
.X...X.........
.......XXXXXXXX
.X...X.X.......
..X...X..XXXXXX
...X.X...X.....
X...X......XXXX
.X.X.....X.X...
..X.......X..XX
.X.......X...X.
X..............

n = 25
X........................
..XXXXXXXXXXXXXXXXXXXXXXX
..X......................
....XXXXXXXXXXXXXXXXXXXXX
..X.X....................
...X..XXXXXXXXXXXXXXXXXXX
X.X...X..................
.X......XXXXXXXXXXXXXXXXX
X.....X.X................
.......X..XXXXXXXXXXXXXXX
X.....X...X..............
.X..........XXXXXXXXXXXXX
..X...X...X.X............
...X...X...X..XXXXXXXXXXX
X...X...X.X...X..........
.X...X...X......XXXXXXXXX
..X...X.X.....X.X........
...X...X.......X..XXXXXXX
X...X.X.......X...X......
.X...X..............XXXXX
..X.X.........X...X.X....
...X...........X...X..XXX
X.X.............X.X...X..
.X...............X......X
X...............X.....X.X

```

# Answer
> 14 votes
# Python 3 with numpy, ~~90~~ ~~87~~ ~~86~~ 84 bytes

```
from numpy import*
lambda n:2*((4<<(a:=(y:=c_[1-n:n])-y.T)//4)+a%4-2&a-2*y)-1<<a<y%2

```

Takes \\$\left\lceil \frac{n}{2}\right\rceil\\$.

-3 by removing `x`. -1 with a shorter expression for \\$-x - y\\$. -2 with a shorter combining method.

## How it works

Broadcasting is used in several places to produce the table.

### The bottom-left section

Change coordinates to \\$a = -x + y\\$ and \\$b = -x - y\\$, as shown here (\\$a\\$ blue, \\$b\\$ yellow):

This part is handled by the subexpression `(4<<(a:=(y:=c_[1-n:n])-y.T)//4)+a%4-2&a-2*y`. (`y.T` produces \\$x\\$.)

Looking at the lines of constant nonnegative even \\$a\\$, their squares are black when certain bits of \\$b\\$ are zero, specifically (1x, 10x, 11x, 100x, 111x, 1000x, 1111x, ...) -- the low bit does not matter as it is always 0 in \\$b\\$ here. These values are produced by taking a power of 2 and adding 0 or -2; then bitwise-ANDing with \\$b\\$ yields 0 for black squares and nonzero values for white squares.

The lines of constant nonnegative odd \\$a\\$ are all white. To get this to work, since the low bit of \\$b\\$ is 1 here, we just need to make sure the low bit of the value ANDed with \\$b\\$ is 1.

### The top-right section

Here, a square is black iff \\$y\\$ is odd, thus black iff `y%2` is 1.

### Combining the sections

Doubling the first part and subtracting 1 from it makes it negative for black squares and positive for white squares in the bottom-left section. In numpy arrays, shifting by a negative number produces zero, so `<<a` makes it zero in the top-right section while preserving its sign in the bottom-left section. Finally, it is less than `y%2` iff it is negative (for a black square in the bottom-left section) or it is 0 and `y%2` is 1 (for a black square in the top-right section).

# Answer
> 3 votes
# Charcoal, 44 bytes

```
ＮθＧ↖→→↓↓θ¶XＦθ«Ｐ↖⭆…⊕⁻ιθ⁻θι§ X¬＆κ⁻Ｘ²⊕÷ι²¬﹪ι²←←

```

Try it online! Link is to verbose version of code. Takes input as the 1-indexed distance from the centre. Explanation: Diagonal bit-twiddling shamelessly stolen from @m90's answer, because I can't work out what @Bubbler means regarding the antidiagonals.

```
Ｎθ

```

Input `⌈n/2⌉`.

```
Ｇ↖→→↓↓θ¶X

```

Draw alternate rows of `X`s in the upper right triangle, leaving the cursor at the bottom right of the final diagram.

```
Ｆθ«

```

Loop through each diagonal of the lower right triangle.

```
Ｐ↖⭆…⊕⁻ιθ⁻θι§ X¬＆κ⁻Ｘ²⊕÷ι²¬﹪ι²

```

Output `X`s where the distance from the centre antidiagonal does not have the given bits.

```
←←

```

Move to the next diagonal.

---
Tags: code-golf, array, grid, cellular-automata
---


# Question
Title: The Most Palindromy Code to Calculate Palindromy Numbers
The string

```
abaaba

```

Is a palindrome, meaning it doesn't change when it's reversed. However we can split it in half to make two palindromes

```
aba aba

```

We could also split it up this way:

```
a baab a

```

And all three of those are palindromes.

In fact there are only two ways to split the string into smaller strings such that *none* of them are palindromes:

```
abaa ba
ab aaba

```

Any other way we split this there is going to be at least one palidrome.

So we will say that this string has a **palindromy number** of 2. More generally a string's palindromy number is the number of ways to partition it into contiguous substrings such that none are a palindrome.

Your task will be to take a string as input and determine its palindromy number. Your answer must work correctly for inputs containing lowercase letters (`a`-`z`) along with any characters used in the source code of your program.

## Scoring

Your answer will be scored by it's own palindromy number. With a lower score being the goal. In the case of ties the tie breaker is

This scoring does mean if you solve this in brainfuck you can get a lenguage answer with a primary score of 0. So if you are a lenguage enthusiast this is just code-golf.

Here's a program to score your code.

## Test cases

```
a -> 0
aba -> 0
ababa -> 0
abababa -> 0
ffffffff -> 0
xyz -> 1
abaa -> 1
abaaa -> 1
abaaaaa -> 1
ooooooops -> 1
kvxb -> 2
kayak -> 2
abaaba -> 2
abaaaba -> 2
avakava -> 2
aaaaakykaaaaa -> 2
abaaaaba -> 3
ababab -> 4
abababab -> 8

```

# Answer
> 5 votes
# Jelly, score 3, 755962277730462996760664 bytes

```
...‘‘‘‘ṃØJV

```

Try it online!

-5 score and +tons of bytes thanks to @ovs's idea.

`...‘‘‘‘` part contains exactly 755962277730462996760660 copies of  character, whose length encodes the following program in base 256:

# Jelly, 10 bytes

```
ɠŒṖŒḂ€€§¬S

```

Try it online!

The main code is a minor variation of Dude's answer (use of alternative built-ins, and input method changed to "a single line from stdin"), so here goes an explanation for the encoding part instead:

```
...‘‘‘‘ṃØJV    Main link (niladic).
...‘‘‘‘        Increment from zero 755..whatever..660 times
       ṃØJ     Base decompress into Jelly's code page
          V    Eval as a nilad (input is handled in the code itself)

```

The 3 non-palindromic partitions of `...aaaabcde` are:

```
...aaaabcde
...aaaabc|de
...aaaab|cde

```

# Answer
> 3 votes
# Jelly, score ~~14~~ 12, 9 bytes

```
ŒṖŒḂ€€§¬§

```

Try it online!

I thought this would be more of a baseline contender, but any modification I make to it to try to make it more palindromy only increases it instead. So, this is just the straight forward implementation.

-2 points thanks to xigoi

## How it works

```
ŒṖŒḂ€€§¬§ - Main link. Takes a string S on the left
ŒṖ        - Get all partitions of S
     €    - Over each partition:
    €     -   Over each substring in the partition:
  ŒḂ      -     Is the substring a palindrome?
      §   - Get the sum of each (counting how many substrings are palindromic)
       ¬  - Logical not. Map zeros to one, everything else to zero
        § - Sum, counting the zeros

```

# Answer
> 2 votes
# 05AB1E, score 18 (9 bytes)

```
.œεεÂÊ]PO

```

Try it online or verify all test cases, including itself.

**Explanation:**

```
.œ      # Get all partitions of the (implicit) input-string
  ε     # Map over each partition:
   ε    #  Map over each part in this partition:
        #   Check that it's NOT a palindrome by:
    Â   #    Bifurcating it (short for Duplicate & Reverse copy)
     Ê  #    And check that this reversed copy is not equal to the original string
  ]     # Close both nested maps
   P    # Check for each partition whether no part was a palindrome
    O   # Sum to get the amount of truthy values
        # (after which the result is output implicitly)

```

I don't think this score nor byte-count can be improved, but I'd like to be proven wrong. Increasing the program size overall increases the score, otherwise `Ê]PO` to `Q]O_O` would have been a decent change with the palindrome `O_O` (this scores 22 at 10 bytes btw).

# Answer
> 1 votes
# Vyxal, 25 bytes, score 46368

```
LṄvṖ⁽JḭUƛvɾ:?f$•;'ƛḂ≠;A;L

```

Try it Online!

-3 thanks to Aaron Miller.

A big mess. Part of the code shamelessly stolen from Lyxal.

```
L                         # Length
 ṄvṖ                      # All permutations of partitions
    ⁽Jḭ                   # Flatten by 1 level
       U                  # Uniquify
        ƛ       ;         # Foreach
         vɾ:?f$•          # Mold input to those pieces (see above link)
                 '     ;L # Number of values where
                  ƛḂ≠;A   # All aren't palindromes.

```

# Answer
> 1 votes
# Stax, score 21 (9 bytes)

```
Æ₧ⁿ+Ü█>la

```

Run and debug it

the packed representation scores lesser, as shown in the tests.

Despite the existence of `f!f` and `{{` in the unpacked version, the number of characters simply doubles the score.

---
Tags: string, source-layout, palindrome, self-scoring
---


# Question
Title: How many iterations to reach the sequence?
Let's define a function \\$f\\$ which, given a positive integer \\$x\\$, returns the sum of:

* \\$x\\$
* the smallest digit in the decimal representation of \\$x\\$
* the highest digit in the decimal representation of \\$x\\$ (which may be the same as the smallest one)

For instance:

* \\$f(1)=1+1+1=3\\$
* \\$f(135)=135+1+5=141\\$
* \\$f(209)=209+0+9=218\\$

We now define the sequence \\$a\_k = f^k(1)\\$. That is to say:

* \\$a\_1=1\\$
* \\$a\_k=f(a\_{k-1})\\$ for \\$k\>1\\$

The first few terms are:

```
1, 3, 9, 27, 36, 45, 54, 63, 72, 81, 90, 99, 117, 125, 131, 135, 141, 146, ...

```

## Challenge

Given a positive integer \\$x\\$, you must return the smallest \\$n\\$ such that \\$f^n(x)\\$ belongs to the sequence. Or in other words: how many times \\$f\\$ should be applied consecutively to turn \\$x\\$ into a term of the sequence.

You can assume that you'll never be given an input for which no solution exists. (Although I suspect that this can't happen, I didn't attempt to prove it.)

You may also use 1-based indices (returning \\$n+1\\$ instead of \\$n\\$). Please make it clear in your answer if you do so.

Standard rules apply.

## Examples

* Given \\$x=45\\$, the answer is \\$0\\$ because \\$x\\$ is already a term of the sequence (\\$a\_6=45\\$).
* Given \\$x=2\\$, the answer is \\$3\\$ because 3 iterations are required: \\$f(2)=2+2+2=6\\$, \\$f(6)=6+6+6=18\\$, \\$f(18)=18+1+8=27=a\_4\\$. Or more concisely: \\$f^3(2)=27\\$.

(These are the 0-based results. The answers would be \\$1\\$ and \\$4\\$ respectively if 1-based indices are used.)

## Test cases

```
Input : 0-based output

1     : 0
2     : 3
4     : 15
14    : 16
18    : 1
45    : 0
270   : 0
465   : 67
1497  : 33

```

# Answer
# 05AB1E, 15 bytes

-2 bytes thanks to Kevin Cruijssen!

```
$‚€λDZsßO}`.i1k

```

Try it online!

```
$‚            # pair 1 and the input
  €           # for each k of those two values
   λDZsß++}   # calculate the infinite sequence given by f^n(k):
    D         # duplicate the previous value
     Z        # take the maximum digit of the copy without removing it from the stack
      sß      # swap to the copy and get the minimum digit
        O     # sum previous value, maximum digit and minimum digit

`             # push both infinite sequences seperately on the stack
 .i           # for each value in the sequence starting with the input:
              #  is it contained in the other (non-decreasing) sequence?
   1k         # print the index of the first 1

```
> 7 votes

# Answer
# Husk, ~~21~~ ~~20~~ 15 bytes

*Edit: -5 bytes thanks to Razetime*

```
V£₁1₁
¡S+o§+▲▼d

```

Try it online!

1-based output.

```
¡S+o§+▲▼d       # helper function ₁:
¡               # generate infinite sequence by repeatedly applying:
 S+o§+▲▼d       # function f:
 S+             # add the input to
    §+▲▼        # sum of the max and the min of
   o    d       # the digits of the input

V£₁1₁           # main program:
V               # index of first truthy result of ...
 £              # getting the index (or zero if absent) of
  ₁1            # the infinite sequence of helper function starting with 1
    ₁           # in the infinite sequence of helper function ₁ starting with the program input

```
> 6 votes

# Answer
# Charcoal, 45 bytes

```
Ｎθ≔¹η≔⁰ζＷ⁻θη¿‹ηθ≧⁺Σ⁺⌊Ｉη⌈Ｉηη«≧⁺Σ⁺⌊Ｉθ⌈Ｉθθ≦⊕ζ»Ｉζ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input `x`.

```
≔¹η

```

Start with `a=1`.

```
≔⁰ζ

```

Start with `n=0`.

```
Ｗ⁻θη

```

Repeat until `x=a`.

```
¿‹ηθ≧⁺Σ⁺⌊Ｉη⌈Ｉηη

```

If `a<x` then calculate `a=f(a)`.

```
«≧⁺Σ⁺⌊Ｉθ⌈Ｉθθ

```

Otherwise calculate `x=f(x)`, ...

```
≦⊕ζ»

```

... and increment `n`.

```
Ｉζ

```

Output `n`.
> 3 votes

# Answer
# , 109 bytes

(or **\>=4.1, 95 bytes** replacing both `function` appearances with `\`)

```
function(x,`!`=function(n)n+sum(range(n%/%10^(0:log10(n))%%10))){while({F=F+1;i=1;while(i<x)i=!i;i-x})x=!x;F}

```

Try it online!

Returns 1-based result.
> 3 votes

# Answer
## JavaScript (ES6), ~~104~~ ~~86~~ 82 bytes

*-2 thanks to @emanresuA and @Shaggy, and another -2 from @tsh (with an honorable mention for @m90 :p)*

```
r=x=>(f=x=>x+Math.min(...x+="")+Math.max(...x),g=y=>y<x?g(f(y)):y>x)(1)&&r(f(x))+1

```

Try it online!
> 2 votes

# Answer
# Scala, 100 bytes

```
a(_)indexWhere(? =>a(1)takeWhile?.>=toSet?)
val a=Stream.iterate(_:Int)(x=>x+s"$x".min+s"$x".max-96)

```

Try it in Scastie!

Pretty simple solution. `a` is a function that makes an infinite list of the sequence, given a starting number. We make a sequence starting at `x` using that, and find the first index where an item is inside the sequence starting at `1`. Since the sequence can only be added to, it's monotonic and therefore safe to only check the elements which are less than or equal to `x`.
> 2 votes

# Answer
# C (gcc), 114 bytes

```
d;s;m;x;f(n){for(s=m=n,x=0;n;n/=10)d=n%10,m=d<m?d:m,x=d>x?d:x;s+=m+x;}g(n){for(s=1;n>s;s=f(s));s=n<s?1+g(f(n)):0;}

```

Try it online!
> 2 votes

# Answer
# Python 2, <sup>~~128~~ \\$\cdots\\$ ~~98~~</sup> 94 bytes

```
f=lambda n:n+int(min(`n`))+int(max(`n`))
g=lambda n,s=1:n>s and g(n,f(s))or n<s and-~g(f(n),s)

```

Try it online!

Saved 17 bytes thanks to gsitcia!!!

\\$0\\$-based return value and returns `False` for \\$0\\$.
> 1 votes

# Answer
# Jelly, 21 bytes

```
;1DṀ+ṂƊ+Ɗ€</¦⁻/Ð¿Ḣ€QL

```

A monadic Link that accepts a positive integer and yields a positive integer (using the 1-indexed option).

**Try it online!**

### How?

Perhaps there is a more terse approach, but I have not thought of one yet.

Starts with the input and \\$1\\$ and applies \\$f\\$ to the minimum of the two while they are unequal, then counts the number of values visited from the input to the final value.

```
;1DṀ+ṂƊ+Ɗ€</¦⁻/Ð¿Ḣ€QL - Link: integer, x
;1                    - concatenate a one
               Ð¿     - collect while...
             ⁻/       - ...condition: reduce by not-equal
         €  ¦         - ...do: sparse application...
          </          -       ...to indices: reduce by less-than
        Ɗ             -       ...action: last three links as a monad, f(v)
  D                   -         decimal digits
   Ṁ+ṂƊ               -         minimum plus maximum
       +              -         add (v)
                 Ḣ€   - head each (all the values we got from x's side)
                   Q  - deduplicate
                    L - length

```

---

#### 0-indexed alternative

Also 21 bytes:

```
;1DṀ+ṂƊ+Ɗ€</¦⁻/Ð¿nƝSḢ

```
> 1 votes

# Answer
# Julia 1.0, 62 bytes

```
!a=a+sum(extrema(digits(a)))
>(x,a=1)=x<a ? 1+(!x>a) : a!=x>!a

```

Try it online!

### Explanation

* `!` is the function `f`
* `a` is `fⁿ(1)` (we don't care about n)
* `1+(!x>a)`: if `x<a`, we compute `f(x)` and add 1 to the result
* `a!=x>!a` is parsed `a!=x && x>!a`
    + returns `false` if `a==x` (false is equivalent to 0) and doesn't evaluate the second part
    + if `a!=x`, computes `x>!a`, which means we compute `f(a)` and return `x>f(a)`
> 1 votes

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


title: Arrow those variables!

text:
# Question
Title: Arrow those variables!
## Challenge

Robin likes having his variables declaration in the shape of an arrow. Here's how he does it:

* Input any number of strings
* Order them by ascending length
* Output them ordered by the middle to roughly form a negative arrowhead, like this (whichever order golfs the best):

```
5  or  4
3      2
1      1
2      3
4      5

```

## Test Cases

Input:

```
bow
arrows
sheriffOfNottingham
kingRichard
maidMarian
princeJohn
sherwoodForest

```

Output:

```
sheriffOfNottingham
kingRichard
maidMarian
bow
arrows
princeJohn
sherwoodForest

```

Input:

```
a
bb
cc

```

Output (both are valid):

```
bb
a
cc

cc
a
bb

```

Input:

```
one
four
seven
fifteen

```

Possible output (the only other valid output is its vertical mirror):

```
seven
one
four
fifteen

```

## Notes

* The strings are in camelCase and have no numbers or special characters, only lowercase and uppercase letters.
* The input can be anything you like: comma-separated as one string, array, ... Any I/O format is allowed.
* Between strings with the same length, any order is accepted.

# Answer
# Python 2, 47 bytes

```
lambda l:l.sort(key=len)or l[1::2][::-1]+l[::2]

```

Try it online!
> 15 votes

# Answer
# , ~~63~~ 48 bytes

```
function(L)c(rev(o<-L[order(nchar(L))]),o)[!0:1]

```

Try it online!

Sort by string lengths, then combine the reversed list with the sorted list, finally, take every 2nd element, starting at 1-based index 1.
> 9 votes

# Answer
# Javascript 77 bytes

Takes input as an array of strings, outputs an arrow-sorted array of strings.

```
s=>s.sort((a,b)=>a.length-b.length).reduce((m,x,i)=>i%2?[...m,x]:[x,...m],[])

```

## Explanation

```
s =>                                 // take input as an array of strings s
  s.sort((a,b)=>a.length-b.length)   // sort input by string length
  .reduce(                           // reduce
    (m,x,i)=>i%2?[...m,x]:[x,...m],  // if index is even, stick string x at the end of the memo
                                     // array, else at the beginning
    []                               // memo initialized to empty array
  )

```
> 7 votes

# Answer
# Ruby, 51 bytes

```
->l{r=1;l.sort_by!(&:size).map{l[r-=2]||(l*2)[~r]}}

```

Try it online!
> 6 votes

# Answer
# Jelly, ~~9~~ 8 bytes

```
LÞŒœm"-Ẏ

```

Try it online!

```
LÞŒœṚ;¥/

```

is also 8 bytes.

Thanks to @EriktheOutgolfer and @JonathanAllan for both offering golfs to save a byte.
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), 89 bytes

```
n=>(n=n.OrderBy(x=>x.Length)).Where((a,b)=>b%2>0).Reverse().Concat(n.Where((a,b)=>b%2<1))

```

Try it online!
> 5 votes

# Answer
# K (oK), 24 bytes

**Solution:**

```
x(<#:'x)(|&~w),&w:2!!#x:

```

Try it online!

**Explanation:**

Generate the `6 4 2 0 1 3 5` sequence, use that to index into the ascending lengths of input, and use that to index into the original array:

```
x(<#:'x)(|&~w),&w:2!!#x: / the solution
                      x: / save input as x
                     #   / count (#) of x
                    !    / range 0 to ...
                  2!     / modulo 2
                w:       / save as w
               &         / indices where true
              ,          / join with
        (    )           / do this together
           ~w            / not (~) w
          &              / indices where true
         |               / reverse
 (     )                 / do this together
   #:'x                  / count (#:) of each (') x
  <                      / indices to sort ascending
x                        / index into x

```
> 5 votes

# Answer
# , 11 bytes

```
,~`,/@\:#&>

```

Try it online!

We sort it down first.

Then we reduce the list form right to left, but alternating which side we put the new element on. Done.
> 5 votes

# Answer
# 05AB1E, ~~6~~ 5 bytes

Saved 1 byte thanks to *Kevin Cruijssen*

I/O is a list of strings.
Link is modified for newline separated I/O for easier testing.

```
éι`Rì

```

Try it online!

**Explanation**

```
é       # sort by length ascending
 ι      # uninterleave into 2 parts, both sorted ascending
   `    # push the 2 parts separately to the stack
    R   # reverse the second part
     ì  # and append it to the first

```
> 5 votes

# Answer
# PHP, ~~144~~ 141 bytes

```
function($a){usort($a,function($b,$c){return strlen($b)-strlen($c);});$e=[];foreach($a as$d)(array_.[unshift,push][++$i%2])($e,$d);return$e;}

```

Try it online!

-3 bytes thanks to @Ismael Miguel!
> 4 votes

# Answer
# PowerShell, 66 bytes

```
1..($a=$args|sort l*).count|?{$_%2}|%{$a[-$_];$x=,$a[-++$_]+$x};$x

```

Try it online!

Takes input via splatting, which manifests on TIO as separate command-line arguments. `sort`s on the `l`ength, stores that into `$a`, and constructs a range from `1` up to the `count` of input strings. We then pull out only the odd ones `?{$_%2}` and feed those into a loop `|%{...}`. Each iteration, we put the "last", then the "third from last", and so on onto the pipeline with `$a[-$_]`. Separately, we also accumulate into `$x` the "second from last", "fourth from last", etc. Out of the loop and the pipeline is flushed (so those elements are output) and then we output `$x`. In both instances, the default output gives us newlines between items automatically.
> 4 votes

# Answer
# MATLAB, 87 bytes

```
function f(y);[B,I]=sort(cellfun(@(x)length(x),y));{y{flip(I(1:2:end))},y{I(2:2:end)}}'

```

Takes input as cell array of strings, outputs column of strings (not sure if that's legal)

```
> s = {'qweq qwe qw','qweqw','12132132131231231','asdasdasda','qwe','w'};
> f(s)
> >>
> ans =
>
>   6×1 cell array
>
>     {'qweq qwe qw'      }
>     {'qweqw'            }
>     {'qwe'              }
>     {'1234'             }
>     {'asdasdasda'       }
>     {'12132132131231231'}

```

PS: Thanks Sanchises for pointing to a bug with odd-length inputs
> 4 votes

# Answer
# APL (Dyalog Unicode), 18 bytesSBCS

```
{⍵[⍋-@(2∘|)⍋⍋≢¨⍵]}

```

Try it online!

Fixed the bug thanks to @ngn.

Explanation:

```
{⍵[⍋-@(2∘|)⍋⍋≢¨⍵]}
{                } ⍝ Function. Takes a single argument: ⍵, list of strings
             ≢¨⍵   ⍝ The length of each element in the list
           ⍋⍋      ⍝ Sort the lengths
    -@(2∘|)        ⍝ At (@) elements divisible by 2 (|), negate (-)
                   ⍝     gives -1 2 -3 4 -5
   ⍋               ⍝ Sort this list again, gives the indices of that list ^ sorted
 ⍵[             ]  ⍝ Use these indices to index into the argument

```

---
> 3 votes

# Answer
# APL+WIN, ~~31~~ 38 bytes

See Adams comment

```
⊃n[(⍳⍴n)~a],⌽n[a←2×⍳⌊.5×⍴n←n[⍒∊⍴¨n←⎕]]

```

Try it online Courtesy of Dyalog Classic!

Prompts for a nested vector of strings
> 2 votes

# Answer
# Retina, 26 bytes

```
N$`
$.&
*\,2,^A`.+
,2,G`.+

```

Try it online! Explanation:

```
N$`
$.&

```

Sort the lines in ascending order of length (`$.&` returns the length of the line).

```
*\,2,^A`.+

```

Temporarily delete alternate lines and output the remaining lines in reverse order.

```
,2,G`.+

```

Keep the only lines that were temporarily deleted and output them.
> 2 votes

# Answer
# Japt, 8 bytes

```
ñÊó g0_w

```

-3 bytes thanks to Shaggy!

Try it
> 2 votes

# Answer
# Gaia, 10 bytes

```
el∫v:v+2%ụ

```

Try it online!

```
e		| eval as Gaia code (list of strings)
 l∫		| ∫ort by lengths (ascending)
   v:v		| reverse, dup, reverse
      +		| concatenate lists
       2%	| take every other element
         ụ	| join by newlines and output
```
> 2 votes

# Answer
# PowerShell, 49 bytes

```
$args|sort l*|sort{$_.Length*($global:x=-$x*2+1)}

```

Try it online!

The double distillation.
> 2 votes

# Answer
# T-SQL, 84 bytes

Input is a table variable

```
SELECT a FROM(SELECT*,row_number()over(order by len(a))r
FROM @)x order by(r%2-.5)*r

```

**Try it online**
> 2 votes

# Answer
# Perl 6, 31 bytes

```
*.sort(&chars).sort:{$++%2*$--}

```

Try it online!

Sort by string length, then by static sequence 0, -1, 0, -3, 0, -5, ...
> 2 votes

# Answer
# Javascript 95 Bytes

```
s=>s.sort((x,y)=>x.length-y.length).reduce((a,e,i)=>{i%2?a.push(e):a.unshift(e);return a;},[]);

```
> 1 votes

# Answer
# C (gcc), ~~136~~ 128 bytes

```
S(a,b)int**a,**b;{a=strlen(*b)-strlen(*a);}f(l,s,o,i,b,e)int**s,**o;{qsort(s,l,8,S);e=l-1;for(i=b=0;i-l;)o[i++%2?b++:e--]=s[i];}

```

Try it online!

-8 bytes thanks to ceilingcat.

The function `f` is the solution. It takes the number of strings, the strings themselves, and the output buffer as arguments (plus four more used internally).
> 1 votes

# Answer
# Red, ~~116~~ 101 bytes

```
func[b][sort/compare b func[x y][(length? x)> length? y]collect[forall b[keep take b]keep reverse b]]

```

Try it online!
> 1 votes

# Answer
# perl 5 (`-p0777F/\n/ -M5.01`), 59 bytes

```
for$x(sort{$b=~y///c-length$a}@F){--$|?$\="$x
".$\:say$x}}{

```

TIO
> 1 votes

# Answer
# Husk, 11 bytes

```
m!ÖL¹Ċ2§+ṡŀ

```

Try it online!
> 1 votes

# Answer
# Vyxal `a`, 7 bytes

```
µL;yṘ$"

```

Try it Online!

Outputs as a list of two lists of lines.

The header and footer allow for multiline IO.
> 1 votes

# Answer
# Japt, ~~8~~ 6 bytes

Input as an array of lines, output as an array of 2 arrays of lines, one for each half of the list.

```
ñÊó vw

```

Try it (Header & footer allow for I/O as newline separated string)

```
ñÊó vw     :Implicit input of array
ñ          :Sort by
 Ê         :  Length
  ó        :Uninterleave
    v      :Modify first element
     w     :  Reverse

```
> 0 votes

# Answer
# Julia 1.0, 41 bytes

```
!s=sort(s,by=length)[∪(end:-2:1,1:end)]

```

Try it online!

* input and output are vectors of strings
* `end:-2:1` takes every second index, starting from the end
* `1:end` is all indices
* (=`union`) removes duplicates
> 0 votes

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


title: 12 hour to 24 hour time converter

text:
# Question
Title: 12 hour to 24 hour time converter
Amazingly, this simple task doesn't seem to exist already, so...

Your task is to write a program that takes as input a 12 hour time, and converts it into "military time", or 24-hour time format.

Input will be in the form:

```
HH:MM am/pm

```

Although slight variations are allowed:

* The space separating the am/pm from the rest of the time is optional.
* The last part can either be "am"/"pm", or "a"/"p".
* Any capitalization is fine.

Output will be the inputted time, transformed into 24-hour format. It can be a number, or a string.

For both the input and output:

* 0s in the first place are optional. 0s in the last 3 places are mandatory.
* the delimiter separating hours and minutes can be a ":", " " (a space), or nothing.

Other notes:

* Midnight can be expressed either as 0000, or 2400.
* Midnight will be considered "am", while noon will be considered "pm".

Your program can be a function, or a full program, and should either return the result, or output it to the stdout. Trailing whitespace is ok.

Examples (you aren't required to support every format):

```
12:00am -> 0000
1200 pm -> 1200
1234Am  -> 00:34
134a    -> 134
01:34PM -> 13 34
1234pm  -> 1234

```

This is code golf, so the smallest number of bytes wins. Since this is so trivial to solve using a built-in, it would be nice to see some code that manually solves this (but use of built-ins are fine).

Just to clarify, you *aren't* required to support every possible format. Supporting only a single input and a single output format (of your choice) is fine. I would however like to limit the format as outlined above (which is already quite free). `{1134,'pm'}`, for example, would be unacceptable.

# Answer
> 8 votes
# , ~~21~~ 17 bytes

Thanks @DJMcMayhem for 4 bytes!

```
í12:/0:
çp/12
$x

```

Try it online! This takes the format `HH:MMx` where `x` is either `a` or `p`, and returns it in the format `HH:MM`

Hexdump:

```
00000000: ed31 323a 2f30 3a0a e770 2f31 3201 2478  .12:/0:..p/12.$x
00000010: 0ae7 612f 2478                           ..a/$x

```

Explanation:

```
í12:/0:   | find and replace 12: with 0: (to avoid replacing HH:12)
ç         | on every line
 p/       | that contains a p
   12^A   | increment 12 times (the first number, hours)
$x        | delete the character at the end of the line

```

# Answer
> 12 votes
# MATL, 4 bytes

```
15XO

```

Try it online!

### Explanation

Built-in function: date string conversion with automatic detection of input format and with output format `15`, which corresponds to `'HH:MM'`. This is equivalent to @StewieGriffin's Octave answer.

# Answer
> 10 votes
# Octave, ~~21~~ 17 bytes

Saved 4 bytes thanks to Luis Mendo. I could specify format number 15 instead of `'HHMM'`.

```
@(c)datestr(c,15)

```

**Explanation:**

This is an anonymous function taking a string `c` as input on the format: `'11:34 AM'`. `datestr` recognizes the format automatically as one of the standard date formats, and outputs it in the specified format number 15, which is `HH:MM`.

Since the specified output format doesn't have `AM` or `PM` Octave automatically converts it to what you refer to as Military time.

Try it online.

---

**A version not using `datestr` using 35 bytes**

```
@(c)[c(1:4)+[1,2,0,0]*(c(5)>97),'']

```

**Explanation:**

Takes an input string `c` on the format `1134am`.

```
@(c)                              % Anonymous function
[c(1:4)                           % First 4 elements of the string
       +[1,2,0,0]                 % Add 1 and 2 to the first to the ASCII-value of the
                                    first two characters
                 *)c(5)>97)       % if the fifth element is larger than 97
                                    (the ASCII code for `a`).
                            ,'']  % Implicitly convert to string

```

**Or, a different approach for 37 bytes:**

```
@(c)[c(1:4)+('1200'-48)*(c(5)>97),'']

```

# Answer
> 7 votes
# PowerShell, ~~23~~ ~~20~~ 19 bytes

```
date "$args"-f HHmm

```

Try it online!

(If you're on Windows, you can omit the `get-`, to get down to 19 bytes. On TIO, it apparently requires the full `Get-Date` name.)

Takes input as a string `$args[0]`, uses that as the input to the `Get-Date` cmdlet, which parses it into a .NET `datetime` object. That's passed with the `-f`ormat parameter of `HHmm` to convert it to military time (the capital `HH` specifies 24-hour time). Output is implicit.

The parsing engine is pretty robust, so additional inputs like `12am` or `12:00am` are allowed as well. Play around with the input on TIO and see what else works.

(*Saved 3 bytes thanks to @admalledd ... saved another byte thanks to @briantist*)

# Answer
> 6 votes
### Python 2, 44 bytes

```
lambda s:`int(s[:2])%12+12*("p"in s)`+s[3:5]

```

Input format: `01:23am`, optional `m` and spaces after minutes
Output format: `123`

# Answer
> 5 votes
### Pyth, ~~21~~ 20 bytes

```
Aczd++*12}\pH%sG12PH

```

Takes input of the form `01 23a` as "01:23 am". Initial 0 is optional.
Output is of the form `123`, with the initial 0 omitted.

In pseudocode:

```
                         z = input()
A                        G, H =
 czd                         z.split(" ")       # splits into the form ["1","23p"]
                         (
     +*12}\pH            12*('p' in H) +        # add 12 if 'p' is in the string
             %sG12         int(G) % 12
    +             PH     ) + H[:-1]             # prepend hour to minutes, with a/p removed

```

Try it online!

# Answer
> 4 votes
# PHP, ~~35~~ 32 bytes

input format: case insensitive, requires colon and the `m`, output format `hhmm`. uses built-ins:

```
<?=date(Hi,strtotime($argv[1]));

```

takes input from first command line argument.

# PHP, 45 bytes, no built-ins

input format `(h)h:mm a(m)` lowercase, output format `(h)hmm`.

```
<?=($s=$argv[1])%12+12*($s[6]>a).$s[3].$s[4];

```

# Answer
> 3 votes
# Java 7, ~~138~~ ~~106~~ ~~105~~ 104 bytes

```
String a(String a){return new java.text.SimpleDateFormat("Hmm").format(new java.util.Date("Ja1,0,"+a));}

```

Try it online!

Input is colon delimited and has a space between the time and the am/pm. Output is not colon delimited.

-1 byte thanks to Kevin Cruijssen

# Answer
> 3 votes
# GNU Coreutils (~~18~~ 16 bytes)

From a shell script:

Does not accept whitespace in the input

At which point, may as well use $1 and ignore additional args.

```
date -d$1 +%H%M

⇒ echo 'date -d$1 +%H%M' > time24
⇒ sh time24 1:45pm
1345
⇒ sh time24 1:45 pm
0145 # Wrong answer, “pm” ignored because of space

```

## Original

To allow whitespace in the input,

```
date -d"$@" +%H%M

```

# Answer
> 3 votes
# JavaScript (ES6), 40 bytes

```
a=>(new Date('1/1/1/'+a)+a).slice(16,21)

```

Input should be formatted like: `12:32 am`

# Answer
> 3 votes
## C#, 46 bytes

```
s=>System.DateTime.Parse(s).ToString("HH:mm");

```

Strings are taken in input like `12:00 AM`

Doing the same thing but substringing on the output from the default call to `ToString` (Assuming a culture of `en-GB`) is 3 bytes longer for 49 bytes:

```
s=>(System.DateTime.Parse(s)+"").Substring(11,5);

```

# Answer
> 3 votes
# `date`, 0 + 8 = 8 bytes

On the subject of using the right tool for the job…

Takes input as a command line argument. Run with `+%H%M -d` (8 byte penalty). There's no actual program here; the entire work is done by the command-line arguments. (This is a pretty good demonstration of *why* there's a penalty for command-line arguments!)

Example:

```
$ date +%H%M -d "12:05 am"
0005

```

# Answer
> 2 votes
# Perl, ~~45~~ ~~28~~ ~~37~~ bytes

## ~~28~~ 37 bytes

(c/o @Dada)

(36 bytes code, 1 byte for compiler `-p` switch)

Accepts `0145pm` type formats, with am/pm or a/p. Leading zeroes on inputs required.

```
s/(..)(.)$//;$_=$_%12+12*(p eq$2).$1

```

Test:

```
⇒ echo 0145pm | perl -p time24
1345
⇒ echo 0245pm | perl -p time24
1445
⇒ echo 1245pm | perl -p time24
1245
⇒ echo 1245am | perl -p time24
045

```

## My original answer

(also gently revised)

(39 bytes code, 1 byte for compiler `-p` switch.)

Accepts only the form like 0145p or 0145a, and no other, and requires `perl -p` mode to work.

```
s/(..)(..)([ap])/$1%12+12*($3eq"p").$2/e

```

test:

```
⇒ echo 0145p | perl -p time24
1345
⇒ echo 1222a | perl -p time24
022
⇒ echo 1234p | perl -p time24
1234

```

# Answer
> 2 votes
# Japt, 14 bytes

```
Ð"1/"+U s sG21

```

Try it online!

This only works on Chrome. Here's a version that works in all browsers:

```
Ð"1/"³+U s sG21

```

Thanks again to ETHproductions for the help!

# Answer
> 2 votes
# C, ~~87~~ 72 bytes

*Saved 15 bytes thanks to @Johan du Toit*

Call `f()` with a mutable string as an argument, the input is the output.

The format is `HH:MMa/p`, where `a/p` is either lowercase `a` or lowercase `p`. No space between the time and the meridian specifier is allowed.

```
i;f(char*p){i=atoi(p)%12+(p[5]^97?12:0);*p=i/10+48;p[1]=i%10+48;p[5]=0;}

```

Try it on ideone.

# Answer
> 2 votes
## C (clang), 94 bytes

```
h,m;f(){char a,b;scanf("%d:%d%c%c",&h,&m,&a,&b);printf("%02d%02d",a=='a'?(h%12):(12+h%12),m);}

```

Try it online!

I'm here to learn, so any tips on how i can optimize the code are welcome.

@ Johan du Toit Thanks, for saving a few bytes!

# Answer
> 2 votes
# tcl, 45 ~~47~~

Now using a built-in:

```
puts [clock f [clock sc $s -f %I:%M%p] -f %R]

```

Testable on http://rextester.com/TSRXI8802 where there is a script that runs it from 0100am to 1259pm

# Answer
> 2 votes
# Commodore 64 BASIC, 301 bytes before running, 321 bytes used once run

```
0 A$="12:34AM":A=VAL(LEFT$(A$,2)+MID$(A$,4,2)):ON-(RIGHT$(A$,2)="AM")+1GOSUB1,2:TI$=A$:PRINTTI$:END
1 ON-(A=>1200ANDA<=1259)GOTO3:A=A+1200:GOTO3
2 ON-(A=>1200ANDA<=1259)GOTO4:ON-(A<=959)GOTO7:RETURN
3 A$=RIGHT$(STR$(A)+"00",6):RETURN
4 A=A-1200:IFA=0THENA$="000000":RETURN
5 IFA<10THENA$="000"+RIGHT$(STR$(A),1)+"00":RETURN
6 A$="00"+RIGHT$(STR$(A),2)+"00":RETURN
7 A$="0"+RIGHT$(STR$(A),3)+"00":RETURN

```

In order to enter this on a real Commodore 64, you will need to use BASIC keyword abbreviations, such as LE\[shift\]F for `LEFT$`, M\[shift\]I for `MID$` etc... or you could try CBM PRG STUDIO.

The `TI$` variable in Commodore BASIC presents the time in 24 hour clock format as HHMMSS when printed. Taking the space out after the line number does not save any memory as Commodore BASIC adds in the space automatically anyway when you list the program after entering it.

When converting a number to a string with `STR$`, Commodore BASIC will add in the space (so if you `PRINT A` you will see a space before the number is shown), I've removed the opening space on the number to string conversion with the `RIGHT$` command. You could save a few bytes by amending line zero to:

```
0 A=VAL(LEFT$(A$,2)+MID$(A$,4,2)):ON-(RIGHT$(A$,2)="AM")+1GOSUB1,2:TI$=A$:PRINTTI$:END

```

so you will need to declare your time to convert before running the program, as follows:

```
A$="01:22AM":GOTO 0

```

At any moment thereafter, you can see the current time with:

```
? TI$

```

# Answer
> 2 votes
# SmileBASIC, 67 bytes

```
INPUT T$P=POP(T$)>"a
TMREAD"00:"+T$OUT,H,M?H MOD 12+12*P,T$[3];T$[4]

```

Input: `HH:MMa/p`

Output: `HH MM`

# Answer
> 2 votes
# Java, 171 bytes

```
enum t{;public static void main(String[] a){a=a[0].split("[: ]");System.out.format("%02d%02d",(Long.parseLong(a[0])+(a[2].charAt(0)=='p'?12:0))%24,Long.parseLong(a[1]));}}

```

Input format is `HH:MM a/p` and output format is `HHMM`. Abusing the fact that main function has an array of strings to split the input into 3 sections: hour, minute and a/p indicator.

Example input and output:

```
Input: 01:02 a
Output: 0102

Input: 01:02 p
Output: 13:02

Input: 12:22 p
Output: 0022

```

Ungolfed version:

```
enum t {
    ;

    public static void main(String[] a) {
        a = a[0].split("[: ]");
        System.out.format("%02d%02d", (Long.parseLong(a[0]) + (a[2].charAt(0) == 'p' ? 12 : 0)) % 24, Long.parseLong(a[1]));
    }
}

```

# Answer
> 2 votes
## REXX, 33 bytes

```
arg h':'m a
say h+((a=pm)*12)':'m

```

Use:

```
12:34 pm -> 24:34
1:34 pm -> 13:34
1:34 am -> 1:34
0:34 AM -> 0:34

```

This could be shortened by a few bytes if a colon as delimiter was not used.

# Answer
> 1 votes
## R, 68 bytes

```
x=substr(strptime(scan(,""),"%I:%M %p"),12,16);`if`(x=="","00:00",x)

```

Reads input from stdin and it's assumed to be in one of the following formats:

* `12:00 AM`
* `12:00 am`
* `12:00AM`
* `12:00am`

and output is on the format: `[1] "00:00"`

In most instances `strptime()` output is on the format: `"2017-01-06 12:00:00 CET"` where the date is the local date. As such we need to use `substr()` to only return the time, however, if the input is midnight (e.g. `12:00am`) the output is only `"2017-01-06 CET"` which is the reason for the `if` thing at the end (there must be some more clever workaround).

# Answer
> 1 votes
# tcl, 88 ~~102~~ ~~107~~ ~~110~~

Naïve attempt:

```
puts [format %03d [expr {[regsub p $s "" n]?([scan $n %d]+1200)%2400:[regsub a $s ""]}]]

```

testable on http://rextester.com/live/XUKJU62994 where there is a script that runs it from 0100a to 1259p

# Answer
> 1 votes
# C, ~~159~~ 152 bytes

```
#define C c[0]
main(i,c)char**c;{scanf("%s",C);i=atoi(C);if(C[5]-97){i+=i-12?12:0;sprintf(C,"%d",i);}else if(i==12)C[0]=C[1]=48;C[2]=58;C[5]=0;puts(C);}

```

Input format: `07:30am`

# Answer
> 1 votes
## Pyke, 15 bytes

```
4<bwӐi%\pQ{i*+

```

Try it here!

# Answer
> 1 votes
# Mathematica, 33 bytes

```
#~DateString~{"Hour24","Minute"}&

```

Anonymous function. Takes a string as input and returns a string as output. Works with most formats, including `hh:mm AM/PM`.

# Answer
> 1 votes
# tcl, 66 ~~67~~ ~~68~~

```
scan $s %d%c t c;puts [format %03d [expr $c>97?($t+1200)%2400:$t]]

```

in http://rextester.com/live/VDSG70132 there is a script that runs it from 0100a to 1259p

# Answer
> 1 votes
# JavaScript, 67 bytes

```
f=s=>!~s.indexOf`pm`?s.slice(0,5):((+s.slice(0,2)+12)+s.slice(2,5))

```

Input is like in the example

# Answer
> 1 votes
# Common Lisp (~~151~~122 bytes)

OK, CL isn't meant to be “terse” but I'm just surprised that it isn't the most verbose for this one.

Here's the 122 byte version, which requires fixed-position input. `0145pm` or `145p` are acceptable (with the leading space in the first character-position).

```
(defun a(x)(let((h(parse-integer(subseq x 0 2)))(m(subseq x 2 4)))(format nil "~a~a" (+(mod h 12)(if(find #\p x)12 0))m)))

```

PPRINT:

```
(DEFUN A (X)
  (LET ((H (PARSE-INTEGER (SUBSEQ X 0 2)))
        (M (SUBSEQ X 2 4)))
    (FORMAT NIL
            "~a~a"
            (+ (MOD H 12) (IF (FIND #\p X) 12 0))
            M)))

```

## Nicer but bigger

Using only the `Common-Lisp` package. Accepts (only) input in the form of integer hours (with or without leading `0`), literal `:`, two-digit minutes, and optional trailing `am` or `pm` (in lower-case only). Permits whitespace around the time and around the AM/PM, but not directly after the `:`.

```
(defun a(x)(let*((c(position #\: x))(h(parse-integer(subseq x 0 c)))(m(subseq x(1+ c)(+ 3 c))))(format nil "~a~a" (+(mod h 12)(if(find #\p x)12 0))m)))

```

Test:

```
GOLF> (a "  1:45 am ")
"1:45"
GOLF> (a "  1:45 pm ")
"13:45"
GOLF> (a " 12:45 am ")
"0:45"
GOLF> (a "12:45p")
"12:45"

```

`pprint` the function definition:

```
(DEFUN A (X)
  (LET* ((C (POSITION #\: X))
         (H (PARSE-INTEGER (SUBSEQ X 0 C)))
         (M (SUBSEQ X (1+ C) (+ 3 C))))
    (FORMAT NIL "~a~a"
            (+ (MOD H 12)
               (IF (FIND #\p X)
                   12
                   0))
            M)))

```

De-obfuscated:

```
(defun 12->24-hour (timestring)
  "Given a  TIMESTRING with  hours:minutes and a  trailing “am”  or “pm”
   \(lowercase-only), return the 24-hour time without a delimiter as
   a  string \(eg,  \"1:45am\" →  \"0145\"). Spaces  surrounding the
   time or  meridian markers are ignored  \(eg, \" 02:22 pm  \") but
   other junk in the string may cause incorrect behavior."
  (let ((colon (position #\: timestring)))
    (let ((hours (parse-integer (subseq timestring 0 colon)))
          (minutes (subseq timestring (+ 1 colon) (+ 3 colon))))
      (format nil "~a~a"
              (+ (mod hours 12) (if (find #\p timestring) 12 0))
              minutes))))

```

# Answer
> 1 votes
## Haskell, 61 characters

Short version:

```
c[a,b,c,d,e]=(mod(read[a,b]::Int)12+f e,[c,d])
f 'a'=0
f _=12

```

Input format: `HHMM(a/p)` where `(a/p)` is either 'a' or 'p' without parenthesis.

Output format: `(hs, MM)` – a tuple containing the hours as an integer and MM still as string.

Example:

```
> c "1200p"
(12,"00")
> c "1200a"
(0,"00")

```

Longer version (with more useful names and one substitution `hs`):

```
conv [h0,h1,m0,m1,ap] = (mod hs 12 + offset ap, [m0,m1])
    where hs = read [h0,h1] :: Int

offset 'a'=  0
offset  _ = 12

```

# Answer
> 1 votes
# Retina, ~~61~~ 60 bytes

```
^12(.*)a
00$1
^(12.*)p
$1
a

(\d\d)(.*)p
$1$*x12$*x$2
x+
$.&

```

Input is given without a separating colon, mandatory leading `0`, and using only `a` or `p` instead of `am` or `pm`, eg `0134a` is 01:34 am. Outputs in straight military time using 0000 as midnight. (I could save some bytes if I'm allowed to convert, for example, 12:30 am into `2430`, but I doubt that's acceptable).

Try it online!

**Explanation**

The initial two cases deal with the "12" hours, since am/pm is reversed for 12:

```
^12(.*)a
00$1

```

If the time is between midnight (12 am) and 1 am, change it to 00 instead of 12, and remove the `a`.

```
^(12.*)p
$1

```

If the time is between noon (12 pm) and 1pm, remove the p to simply get the 24 hour time.

For any other hour:

```
a

```

If the time is am, simply remove the `a` to get the 24 hour time.

```
(\d\d)(.*)p
$1$*x12$*x$2
x+
$.&

```

If the time is pm, remove the `p`. Convert the hour component to unary, add 12, and convert back to decimal. Leave the minutes unchanged.

# Answer
> 1 votes
## Batch, 40 bytes

```
@set/aa=0,p=12,h=%1%%12+%3
@echo %h% %2

```

Takes input as three arguments. Assumes second argument has leading zero where necessary, third argument is either `a` or `p`. Works by treating the third argument as an indirect variable name therefore adding it on to the number of hours; the number of minutes is unaffected so is just output directly. If mixing different formats is OK then the last space can be deleted to save a byte.

(Rather annoyingly, this question didn't appear on the questions page when I originally loaded it, and I only stumbled across it because I was searching for another question.)

# Answer
> 1 votes
# AWK, 25 ~~18~~ bytes

```
/p/{$1=1200+$1%1200}$0=$1

```

Try it online!

Input is `hhmm am/pm`, i.e. the time as a 3 or 4 digit number with whitespace separating the am/pm designator. Correction applied to account for 12 pm times. Thanks @cnamejj for pointing out issue

# Answer
> 1 votes
# T-SQL, 48 bytes

```
CREATE PROC t @ DATETIME AS PRINT FORMAT(@,'Hm')

```

Must be used in SQL Server 2012+. The input is converted to '1900-01-01 HH:mm:ss.sss' and the `FORMAT` function gets the hour and minute part.

Usage:

```
EXECUTE t @ = '10:45pm'

```

# Answer
> 1 votes
# Groovy, ~~49~~ 50 bytes

+1 byte because of invalid output format :(

```
{t=it.split();(t[0]as int)+(t[2]=="pm"?12:0)+t[1]}

```

Input is given in format HH MM am or HH MM pm. Output is in format HHMM.

**Quick explaination:**

it.split() splits the input in an array \[hour, minute, am/pm \] Then it returns the hours concatenated with the minutes, but adds 12 to the hours before returning if the last item of the array is "pm"

**Previous solution**

```
 {t=it.split();t[2]=="pm"?(t[0]as int)+12+t[1]:it}

```

# Answer
> 1 votes
# Retina, 46 bytes

```
.*p
12$0
\D

..(?=..)
$*!
!+
$.&
^12
00
^24
12

```

Try it online!

Input must supply at minimum 2 digits each for HH & MM and a "p" if applicable. Output only returns a leading 0 for the 12 AM hour (I'm unclear if the note on midnight should be interpreted literally, but if not, that would shave off 1 byte). Works on the example cases, provided you prepend `134a` with a 0.

Non-digit characters (besides p) are stripped. Lines lacking a "p/pm" are treated as AM. PM times are shifted up by 12 hours, and 12/24 are simply swapped at the end.

# Answer
> 1 votes
# Tcl, 76 bytes

```
if [scan $s %dp%n n -]>1 {set n [expr ($n+1200)%2400]};puts [format %03d $n]

```

Try it online!

# Answer
> 1 votes
# *Acc!!*, ~~101~~ 97 bytes

```
(N*10+N)%12*60+N*10+N-528+N/98*720
Write _/600+48
Write _/60%10+48
Write _%60/10+48
Write _%10+48

```

Expects input in the form `0123a` (all digits mandatory, no separators, lowercase am/pm indicator). Gives output like `0123`.

Try it online!

### Explanation

*Acc!!* reads one character code at a time using the `N` special value. With a sufficiently strict input format, we can read five characters and do a little math to compute the number of minutes since midnight, and from there it's easy to print out the 24-hour time.

Deobfuscated, the first line is

```
((N-48)*10 + N-48)%12*60 + (N-48)*10 + N-48 + N/98*720

```
* The first character is the tens digit of the hour, and the second character is the ones digit of the hour. We convert both from character codes to the associated digits (`N-48`) and combine them into a single number (`...*10 + ...`).
* If the hour is 12, we want it to become 0; otherwise, it should stay the same. This is accomplished by a mod 12 operation (`%12`). (*Note: in the golfed code, the `%12` also takes care of the `-48`s here.*)
* Multiply by 60 in preparation to add the minutes (`*60`).
* Process the next two characters as minutes digits, in the same way as the hours digits (`(N-48)*10 + N-48`).
* Now we want to add 12 to the hour if the next character is `p` (ASCII 112), or add nothing if it's `a` (ASCII 97).
    + We can distinguish the two by int-dividing by 98: `N/98` is `0` if `N` is 97 and `1` if `N` is 112.
    + Adding 12 hours is the same as adding 720 minutes: `+ ...*720`

This value is stored in the accumulator, `_`.

Now for our output, we need:

* Tens digit of the hour
* Ones digit of the hour
* Tens digit of the minute
* Ones digit of the minute

The hour is `_/60`, and the minute is `_%60`. The tens digit of a number (less than 100) is `.../10`, and the ones digit is `...%10`. Combining a few operations where possible gives the four expressions in the code (remembering that we need `+48` to convert digits back to corresponding character codes).

# Answer
> 1 votes
# 05AB1E, 17 bytes

```
Çт÷`Ž4µ©*Iþ®%4°O¦

```

Input-format as `HHmmx`, where `x` is `a`/`p`; output format as `HHmm`.

Try it online or verify all test cases.

**Explanation:**

```
Ç            # Convert the (implicit) input-string to a list of unicode values
 т÷          # Integer-divide each by 100 (0 for "a" and every digit; 1 for "p")
   `         # Pop and dump all these integers to the stack
    Ž4µ      # Push compressed integer 1200
       ©     # Store it in variable `®` (without popping)
        *    # Multiply it to the top dumped value (the 0/1 for "a"/"p")
Iþ           # Push the input-string again, and only leave its digits
  ®%         # Modulo it by the 1200 from variable `®`
4°           # Push 10^4: 10000
         O   # Take the sum of all values on the stack
          ¦  # Remove the leading "1"
             # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ž4µ` is `1200`.

# Answer
> 0 votes
# Clojure, ~~143~~ ~~108~~ 96 bytes

+54 bytes to fix a "noon/midnight bug" where times within the hour after noon/midnight would return wrong values.

-35 bytes by getting ideas from other answers. If the hour is == 12, I make it 0. This reduces the number of cases that need to be dealt with.

-12 bytes thanks to BRFennPocock.

I'm not sure if I'm allowed to compete. I can remove this or mark it as non-competing if necessary. It's not like I'm winning though :)

## V3

```
#(let[[h m[i]](clojure.string/split % #" ")](str(+(if(= i\p)12 0)(mod(Integer/parseInt h)12))m))

```

Ungolfed:

```
(defn to-24h [time-str]
  ; Split the string on spaces, then deconstruct out the hour,
  ; minute, and whether it's am or pm
  (let [[hours minutes [ampm]] (clojure.string/split time-str #" ")
        pm? (= ampm \p)
        h (mod (Integer/parseInt hours) 12)]
    (str (+ (if pm? 12 0) h)
         minutes)))

```

## V2

```
#(let[[h m[i]](clojure.string/split % #" ")h(Integer/parseInt h)h(if(= h 12)0 h)](str(if(= i\p)(+ h 12)h)m))

```

Ungolfed:

```
(defn to-24h [time-str]
  ; Split the string on spaces, then deconstruct out the hour,
  ; minute, and whether it's am or pm
  (let [[hours minutes [ampm]] (clojure.string/split time-str #" ")
        pm? (= ampm \p)
        h (Integer/parseInt hours)
        h (if (= h 12) 0 h)] ; 0-out the hours if they're equal to 12 to minimize cases
    (str (if pm?
           (+ h 12)
           h)
         minutes)))

```

## V1

```
#(let[[h m[i]](clojure.string/split % #" ")p(= i\p)h(Integer/parseInt h)t(= h 12)](str(cond(and(not t)p)(+ h 12)(and t (not p))(- h 12):e h)m))

```

The Java-interop and library reference are killer, but I think they're probably the best options here. Thank God for restructuring though. Easiest parse ever.

Takes input in the format `12 34 am`, and outputs as `034`. Drops 0s in the first place.

Ungolfed:

```
(defn to-24h [time-str]
  ; Split the string on spaces, then deconstruct out the hour,
  ; minute, and whether it's am or pm
  (let [[hours minutes [ampm]] (clojure.string/split time-str #" ")
        pm? (= ampm \p)
        h (Integer/parseInt hours)
        twelve? (= h 12)]
    ; Dispatching to figure out how much needs to be added/subtracted.
    (str (cond (and (not twelve?) pm?) (+ h 12)
               (and twelve? (not pm?)) (- h 12)
               :e h)
         minutes)))

```

# With Built-ins, 83 bytes

```
(fn[s](let[p #(java.text.SimpleDateFormat. %)](.format(p"km")(.parse(p"h m a")s))))
;                                                     Parse the 3 pieces ^
;                          Format into "squished" format ^

```

Basically the Java answer. Input must be in the format `12 34 pm`

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