title: Counting Goats to Sleep

text:
# Question
Title: Counting Goats to Sleep
Some people count sheep to get to sleep. Others count goats.

Write a program or function that takes in a positive integer N and outputs N-1 awake goats followed by one sleeping goat, as if someone was counting N goats and at the very last one they fell asleep.

Awake goats look like this:

```
      \
  ___/o>
-(___)"
 '' ''

```

Sleeping goats look like this:

```
      \
  ___/->
,(___)"
 `` ``

```

They are chained together with a single space between beard and tail of adjacent goats:

```
      \       \       \
  ___/o>  ___/o>  ___/->
-(___)" -(___)" ,(___)"
 '' ''   '' ''   `` ``

```

The output is allowed to have trailing spaces and a single trailing newline.

**The shortest code in bytes wins.**

## Examples

N = 1:

```
      \
  ___/->
,(___)"
 `` ``

```

N = 2:

```
      \       \
  ___/o>  ___/->
-(___)" ,(___)"
 '' ''   `` ``

```

N = 3:

```
      \       \       \
  ___/o>  ___/o>  ___/->
-(___)" -(___)" ,(___)"
 '' ''   '' ''   `` ``

```

N = 4:

```
      \       \       \       \
  ___/o>  ___/o>  ___/o>  ___/->
-(___)" -(___)" -(___)" ,(___)"
 '' ''   '' ''   '' ''   `` ``

```

Larger N should work just as well.

# Answer
> 31 votes
# MATL, ~~56~~ 53 bytes

:"'!!((!((!!#*```).?p0```!!!]'8eP!P]'p(.' '.a-'XE&hqc

Try it online!

### Explanation

**Awake goat**

The awake goat can be packed into the string

```
  '' ''  ")___(->o/___   \

```

and unpacked as will be explained shortly. However, the single-quote symbols would need to be *duplicated* in order to escape them, so the string literal would have to be defined as (note the enclosing single-quote symbols and the duplication of the original ones):

```
'  '''' ''''  ")___(->o/___   \'

```

To save bytes, we define the string using characters *one code point above* that, thus avoiding duplication. The string literal becomes

'!!((!((!!#*```).?p0```!!!]'

At the end of the code we will subtract 1 and convert to char. (We could do it now, right after the string literal; but leaving it for the end will save another single-quote duplication, as we will see).

To explain how the string is unpacked, we will work with the original characters (that are produced at the end of the code by subtacting 1), so the explanation is easier to follow. We first reshape the string

```
  '' ''  ")___(->o/___   \

```

into an 8-row 2D char array, in *column-major order* (down, then across). This automatically pads the last column with char 0 (at the end of the code, subtracting 1 will transform it into number −1, which converted to char gives again char 0). Char 0 is displayed as a space. So effectively we are padding with spaces. The result of reshaping is

```
  >
 "o\
')/
'__
 __
'__
'(
 -

```

We now flip vertically:

```
 -
'(
'__
 __
'__
')/
 "o\
  >

```

and then transpose and flip vertically again to produce the awake goat:

```
      \
  ___/o>
-(___)"
 '' ''

```

The two flip operations are needed because the original packed string is "in reverse". This is to exploit the fact that the actual 2D char array representing the goat has 6 initial spaces in its first row, which get automatically filled by padding when the string is reshaped into an 8-row 2D array. But the padding is done at the end (not beginning) of the last column (not row), hence the flips and transpose.

**Sleeping goat**

A sleeping goat is generated from an awake goat by transliterating chars `o`, `'`, `-` into `-`, ```, `,` respectively. Actually, because of the one-code-point-above transformation, we transliterate chars `p`, `(`, `'` into `.`, `a`, `-`, which again saves us from having to duplicate the single-quote symbol. This is why the subtract-one operation was left for the end of the program.

**Code structure**

1. Generate an awake goat `N` times, working with code points increased by 1.
2. Transform the last goat into a sleeping goat.
3. Concatenate all goats horizontally. Subtract 1 to code points and cast to char.

**Commented code**

<pre><code>:                              % (Step 1) Implicitly input N. Push range [1 2 ... N]
"                              % For each (i.e. repeat N times)
  '!!((!((!!#*```).?p0```!!!]' %   Push this string. Quotes are escaped by duplicating
  8e                           %   Reshape into an 8-row 2D array of char, in
                               %   column-major order, padding last column with
                               %   char 0
  P                            %   Flip vertically
  !P                           %   Transpose and flip vertically
]                              % End
'p(.'                          % (Step 2) Push this string: source for transliteration
'.a-'                          % Push this string: target for transliteration
XE                             % Transliterate. Transforms last goat into sleeping
&h                             % (Step 3) Horizontally concat all 2D char arrays
qc                             % Subtract 1 and convert to char. 0 becomes −1, which
                               % is converted to char 0, which is displayed as a space
                               % Implicitly display
</code></pre>

# Answer
> 13 votes
## Javascript, 122 bytes

**Answer**

```
f=(n,r='repeat')=>'      \\ '[r](n--)+`
${'  ___/o>'[r](n)}  ___/->
${'-(___)" '[r](n)},(___)"
`+` '' ''  `[r](n)+' `` ``'

```

---

**Side note**
In the following code (91 bytes) the goats are aligned verticaly. It does not comply with the output format but i though it could be interesting to note that the horizontal alignment required in the output format needs more bytes:

```
f=n=>`
      \\
  ___/${--n?'o':'-'}>
${n?'-':','}(___)"
 ${n?'`` ``':`'' ''`}`+(n?f(n):'')

```

# Answer
> 4 votes
## Batch, 234 bytes

```
@echo off
set/pn=
call:l "      \ " "      \"
call:l "  ___/o]" "  ___/-]"
call:l "-(___)@ " ",(___)@"
call:l " '' ''  " " `` ``"
exit/b
:l
set s=%~2
for /l %%i in (2,1,%n%)do call set s=%~1%%s%%
set s=%s:@="%
echo %s:]=^>%

```

Takes input from stdin. Batch has trouble with `"` and `>` for various reasons so I have to use placeholders and then switch them at the end.

# Answer
> 4 votes
## Pyke, ~~56~~ 54 bytes

```
Fhqd6*"\
  ___/o>
-(___)
 '' ''"+23\":RI"-o'"",-`".:(P

```

Try it here!

4 bytes too many because Pyke doesn't allow double quotes in strings :(

# Answer
> 3 votes
## JavaScript (ES6), ~~110~~ 109 bytes

```
f=
n=>`      \\       \\
  ___/o>  ___/->
-(___)" ,(___)"
 '' ''   `.replace(/^.{8}/gm,"$&".repeat(n-1))+"`` ``"
;
```

```
<input type=number min=1 oninput=o.textContent=f(this.value)>

```

Having to support all three kinds of quote characters was annoying, but fortunately @pinkfloydx33's comment gave me the flash of inspiration that I could add the backquotes at the end thus saving me 1 byte.

# Answer
> 3 votes
# Jelly, ~~62~~ 56 bytes

```
⁶ẋ6;“\   ___/o>-(___)"  '' ''  ”s8
¢“-,o-'`”yÐ€
’1£ẋ€ż¢Y

```

Test it at **TryItOnline**

How?

```
⁶ẋ6;“\   ___/o>-(___)"  '' ''  ”s8 - Link 1: make a goat, niladic
⁶ẋ6                                - space character, ⁶, repeated 6 times
    “\   ___/o>-(___)"  '' ''  ”   - rest of the awake goat text
   ;                               - concatenate
                                s8 - split into length 8 parts

¢“-,o-'`”yÐ€ - Link 2: put a goat to sleep, niladic
¢            - last link (make a goat)
 “-,o-'`”    - characters to remap
         yÐ€ - map for each (change "-" into ",", "o" into "-", and "-" into "`"

’1£ẋ€ż¢Y - Main link: n
’        - decrement (nAwakeGoats)
 1£      - call link 1 as a nilad (make an awake goat)
   ẋ€    - repeat nAwakeGoats times
      ¢  - last link (make a sleeping goat)
     ż   - zip
       Y - join with line feeds
         - implicit print

```

# Answer
> 3 votes
# GolfScript, 91 bytes

```
~:a 1-:b;"      \\ "a*n"  ___/o>"b*"  ___/->"n"-(___)\" "b*",(___)\""n" '' ''  "b*" `` ``"n

```

Input: `3`

Output:

```
      \       \       \
  ___/o>  ___/o>  ___/->
-(___)" -(___)" ,(___)"
 '' ''   '' ''   `` ``

```

### Explanation

```
~:a 1-:b;      # Parse and save the input
"      \\ "a*n # Repeat the first line 'a' times
"  ___/o>"b*   # Repeat the head 'b' times
"  ___/->"n    # Then add the sleeping goat's head
"-(___)\" "b*  # Idem
",(___)\""n    #
" '' ''  "b*   # Idem
" `` ``"n      #

```

Try it online!

# Answer
> 2 votes
## Knight, 96 bytes

```
;O*"      \ "=n+0P;O+*+=t'  ___/''->'=l-nT+t'o>';O+*+','=t'(___)" 'l+'-'tO+*' `` ``  'l" '' ''"

```

Pretty simple, nothing super fancy—You just print out `n-1` versions of the sleeping goat and then the woke goat. Repeatable elements are saved in `t` so they aren't typed out again.

Expanded:

```
# Print out the ears. They're the same for both goat types.
; OUTPUT (* "      \ " (= n (+ 0 PROMPT)))
; OUTPUT
    (+
        (* (+ (= tmp '  ___/')'->') (= m - n TRUE))
        (+ tmp 'o>'))
; OUTPUT
    (+
        (* (+ ',' (= tmp '(___)" ')) m)
        (+ '-' tmp))
OUTPUT (+ (* ' `` ``  ' m) (" '' ''"))

```

# Answer
> 1 votes
# PHP , 200 Bytes

```
$a=["      \ ","  ___/o>",'-(___)" '," '' ''  "," `` ``  "];$z=8*$n=$argv[1];for($i=0;$i<4;)$o.=str_repeat($a[$i],$i++==3?$n-1:$n);$o[$z*2-2]="-";$o[$z*3-8]=",";$o.=$a[4];echo chunk_split($o,$z,"\n");

```

# Answer
> 1 votes
## C++, 180 bytes

```
auto f(int n)
{
string a,b,c,d;
while(n--)
{
a+="      \\ ";
b+="  ___/";b+=n?"o>":"->\n";
c+=n?"-(___)\" ":",(___)\" \n";
d+=n?R"( '' ''  )":" `` ``  \n";
}
return a+'\n'+b+c+d;
}

```

# Answer
> 1 votes
## Pip, 60 + 1 = 61 bytes

One byte added for the `n` flag.

```
YsX6.\"\   ___/o>-(___)"  '' ''  \"<>8yXa-1.YyR^"-o'"Y^",-`"

```

Constructs an awake goat as a list of lines and yanks it into `y`. String-multiplies to get `a-1` awake goats. Replaces `-o'` with `,-`` in `y` and concatenates it to the end. Prints, newline-separated.

Try it online!

(I think this is my first time using Pip's escaped-string syntax `\"...\"`, which allows for literal double quotes in the string.)

# Answer
> 1 votes
# Python 2.7, 101 113 bytes

Edit: Added function definition

```
def f(n):
 m=n-1
 print "      \ "*n+"\n"+"  ___/o>"*m+"  ___/->\n"+'-(___)" '*n+"\n"+" '' ''  "*m+" ``"*2

```

de-golfified:

```
m=n-1              # Replacement variable. Saves 6 bytes
"      \ "*n+"\n"+ # Print ears, same for all goats!
"  ___/o>"*m+      # Print eyes of n-1 awake goat
"  ___/->\n"+      # Print eye of sleeping goat
'-(___)" '*m+      # Print body of n-1 awake goat
',(___)"\n'+       # Print body of sleeping goat
+" '' ''  "*m+     # Print the legs of n-1 awake goat
" ``"*2            # Print legs of sleeping goat using *2 operator to save 1 byte

```

Note Python2.7 is one byte shorter than Python3 due to that it doesn't need parentesis when printing.

# Answer
> 1 votes
# IBM/Lotus Notes Formula, ~~187~~ ~~174~~ 188 bytes ~~(not competing)~~

**EDIT** Found a space that shouldn't have been there and removed an unneeded @Implode

188 as I had missed the fact that the tail of the sleeping goat is different :-(

```
B:=@Repeat("      \\  ";a);C:=@Repeat("     /o> ";a-1)+"     /->";D:=@Repeat("  ---    ";a);E:=@Repeat(",(___)\"  ";a);F:=@Repeat(" `` ``   ";a);@Implode(B:C:D:E:F;@NewLine)

```

Ungolfed:

```
B:=@Repeat("      \\  ";a);
C:=@Repeat("     /o> ";a-1)+"     /->";
D:=@Repeat("  ---    ";a);
E:=@Repeat("`(___)\"  ";a-1)+",(___)\"  ";
F:=@Repeat(" `` ``   ";a);
@Implode(B:C:D:E:F;@NewLine)

```

Usage:

Create a Notes form with two fields named a and g.

a=editable, number, g=computed, text.

Paste the above formula into g and give a a default value of 0.

Set the form font to Terminal.

Create a new document with the form, enter a number in a and press F9 to update the goats.

Samples:

~~Not competing as the format messes up when the number of goats reaches the width of the page.~~

Given an infinitely wide screen it ~~should~~ will work for any number of goats ~~though~~. This is what it looks like when the page is not wide enough.

# Answer
> 1 votes
# CJam, 58 bytes

```
ri{S6*"\   ___/o>,(___)\"  '' ''  "+\{'o`"`-"er}|8/}%W%zN*

```

Try it online!

**Explanation**

```
ri                               e# Read an integer from input
{                                e# Map the following block to the range 0..input-1
 S6*                             e#  Push 6 space characters
 "\   ___/o>,(___)\"  '' ''  "+  e#  Push this string and concatenate with the spaces
 \                               e#  Bring the number being mapped to the top
 {                               e#  If it's 0, execute this block:
  'o`                            e#   Push the string "'o"
  "`-"                           e#   Push the string "`-"
  er                             e#   Transliterate the large string by replacing characters
                                 e#    from "'o" with respective characters from "`-"; this
                                 e#    makes the sleeping goat.
 }|                              e#  (end if)
 8/                              e#  Split the string into chunks of length 8
}%                               e# (end map)
W%                               e# Reverse the array, since the sleeping goat was made at
                                 e#  the beginning
z                                e# Transpose
N*                               e# Join with newlines

```

# Answer
> 1 votes
# 05AB1E, 66 bytes

```
’      \ 0  ___/1>02(___)" 0 33 33  ’0¡v123SDys…o-'S:I<×?ys…-,`S:,

```

Try it online!

### Explanation

```
’      \ 0  ___/1>02(___)" 0 33 33  ’0¡v123SDys…o-'S:I<×?ys…-,`S:,   Argument n
’      \ 0  ___/1>02(___)" 0 33 33  ’   The goat, newline replaced by 0 and the eye replaced by 1
0¡                              Split on 0
  v                             For each y in array, do:
   123SD                          Push the array [1,2,3] twice
        ys…o-'S:                  Replace [1,2,3] with ['o','-','\'']
                I<×?              Print that n-1 times without newline
                    ys…-,`S:,     Replace [1,2,3] with ['-',',','`'] and print

```

# Answer
> 1 votes
# Perl 5 `-n`, 105 bytes

```
say for'      \\ 'x(--$_+1),
'  ___/o>'x$_.'  ___/->',
'-(___)" 'x$_.',(___)" ',
" '' ''  "x$_.' `` ``  '

```

Try it online!

# Answer
> 0 votes
# Bash + GNU Coreutils, ~~165~~ 155 bytes

```
a=" \
>o/___
 \")___(-
  '' '' "
eval paste -d \'\' $(seq $1|while read;do
printf '<(echo "$a") '
done) | sed "s/-/,/;s/o/-/;s/'' ''/"'`` ``/'|rev

```

Run with:

```
bash my_pgm.bash N

```

Basically the program prints N times of the same goat (reversed), and substitutes the first `-`, for `,`, the first `o` for `-` and the first `'' ''` for the backticks. Then reverses the lines.

# Answer
> 0 votes
# PHP, ~~133~~ 131 bytes

```
for(;$y<32;$y+=8)for($x=$argv[1];$x--;)echo substr("      \   ___/".($x?"o>-(___)\"  '' ''  ":"->,(___)\"  `` ``  "),$y,8),"
"[$x];

```

I found two bytes to golf away from one of the version without curlys.

# Answer
> 0 votes
# Java 8, ~~236~~ ~~222~~ ~~218~~ 173 bytes

```
n->{String x="\n",a="",b=a,c=a,d=a;for(;n-->0;a+="      \\ ",b+="  ___/"+(n<1?"-":"o")+">",c+=(n<1?",":"-")+"(   )\" ")d+=(n<1?" `` ``":" '' ''")+"  ";return a+x+b+x+c+x+d;}

```

**Explanation:**

Try it online.

```
n->{                                // Method with integer parameter and String return-type
  String x="\n",                    //  New-line String to reduce bytes
         a="",                      //  Row 1 String, starting empty
         b=a,                       //  Row 2 String, starting empty
         c=a,                       //  Row 3 String, starting empty
         d=a;                       //  Row 4 String, starting empty
  for(;n-->0;                       //  Loop `n` times:
    a+="      \\ ",                 //   Append the horns to row 1
    b+="  ___/"+(n<1?"-":"o")+">",  //   Append the back and head to row 2
    c+=(n<1?",":"-")+"(   )\" ")    //   Append the tail, body, and beard to row 3
    d+=(n<1?" `` ``":" '' ''")+"  ";//   Append the legs to row 4
  return a+x+b+x+c+x+d;}            //  Return the four rows, separated by new-lines

```

# Answer
> 0 votes
## PowerShell v2+, 96 bytes

```
param($n)'      \ '*$n--
'  ___/o>'*$n+'  ___/->'
'-(___)" '*$n+',(___)"'
" '' ''  "*$n+' `` ``'

```

(ab)uses the default `Write-Output` formatting to include a newline between elements. Leverages string concatenation and multiplication to construct the goats line by line. The only real trick is the first line `$n--` to output the correct number of ears and then post-decrement `$n` so it's correct for the rest of the lines.

```
PS C:\Tools\Scripts\golfing>  1..4|%{.\counting-goats-to-sleep.ps1 $_}
      \
  ___/->
,(___)"
 `` ``
      \       \
  ___/o>  ___/->
-(___)" ,(___)"
 '' ''   `` ``
      \       \       \
  ___/o>  ___/o>  ___/->
-(___)" -(___)" ,(___)"
 '' ''   '' ''   `` ``
      \       \       \       \
  ___/o>  ___/o>  ___/o>  ___/->
-(___)" -(___)" -(___)" ,(___)"
 '' ''   '' ''   '' ''   `` ``

```

# Answer
> 0 votes
## Emacs Lisp, 241 bytes

```
(defvar s'("     \\""  ___/->"",(___)\""" `` ``"))(defun a()(dotimes(n 4 g)(setf(nth n g)(format"%s%s"(nth n'("     \\  ""  ___/o>""-(___)\" "" '' ''  "))(nth n g)))))(defun g(n)(let((g(copy-seq s)))(mapcar'message(dotimes(i(- n 1)g)(a)))))

```

"Slightly ungolfed"

```
(defvar s'("     \\""  ___/->"",(___)\""" `` ``"))
(defun a()(dotimes(n 4 g)(setf(nth n g)(format"%s%s"(nth n'("     \\  ""  ___/o>""-(___)\" "" '' ''  "))(nth n g)))))
(defun g(n)(let((g(copy-seq s)))(mapcar'message(dotimes(i(- n 1)g)(a)))))

```

where `s` is one sleeping goat, `a` adds an awake goat and `g(n)` is the counting function.

# Answer
> 0 votes
## Ruby, 102 bytes

```
m=-1+n=gets.to_i
puts'      \ '*n,'  ___/o>'*m+'  ___/->',(?-+a='(___)" ')*m+?,+a," '' ''  "*m+" ``"*2

```

# Answer
> 0 votes
# Python 3. 170 bytes

```
lambda n:'\n'.join(map(lambda*l:''.join(l),*map(lambda w:(' '*6+'\ ','  ___/'+(w and'o'or'-')+'>',(w and'-'or',')+'(___)" ',w and" '' ''  "or' `` ``  '),range(n)[::-1])))

```

hmm, apparently constructing the string without doing list manipulation yield shorter code

# Answer
> 0 votes
# Canvas, ~~58~~ 39 bytes

```
！－≥９A²］]ｋ１｛｛K４ｅdｒ↙FX‟×-２２╋,８３╋`` ``３４╋↔

```

Try it here!

Constructs the awake goat facing left from a compressed string, repeats it \\$n\\$ times horizontally, modifies the left-most goat to the sleeping goat, then flips the whole string horizontally.

# Answer
> 0 votes
# Brainfuck 420 bytes

Its not very golfed yet... but it works... whit numbers from 0 to 255 :)

```
>+[[-]>,[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<[->+>+>+>+<<<<]>>>>>>++++[<++++++++>-]>-[<+>---]<+++++++>>-[<+>-----]<---->>-[<-->-------]<+>>----[<+>----]<-><<<<<<[>......>.<.<-]++++++++++.>>+++<<<-[>>..>...>.>.>.<<<<<<-]>>..>...>.--.>>.[<]>.<<-[>>>>>.-----.<...>+.++++<<++.--.<<<-]>>>>>-.----.<...>+.<<++.--.>>[-<<<<+>>>>]<[<]>-->.<<<-[>>>>.<<..>>.<<..>>..<<<<-]>>>>>+<.>..<.>..<..

```

Try it online

Explained version:

```
Read number from 0 to 255 "thanks to esolangs ;)"
>+[[-]>,[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<

Its a little bit hard explain this part because it is creating letters and printing lines
at the same time
[->+>+>+>+<<<<]                              Make 4 copies of the number (one for every line)
>>>>>>++++[<++++++++>-]>-[<+>---]<+++++++>   Make space and '\'
>-[<+>-----]<----                            Make '/'
>>-[<-->-------]<+                           Make 'o'
>>----[<+>----]<->                           Make mayor sign
<<<<<<[>......>.<.<-]                        Print first line
++++++++++.>>+++<<                           Make line jump and '_'
<-[>>..>...>.>.>.<<<<<<-]                    Print second line
>>..>...>.--.>>.[<]                          Make minus sign and print the line of last sheep
>.<<-[>>>>>.-----.<...>+.++++<<++.--.<<<-]   Print thirth line
>>>>>-.----.<...>+.<<++.--.>>[-<<<<+>>>>]    Print the line of last sheep
<[<]>-->.<<<-[>>>>.<<..>>.<<..>>..<<<<-]     Print fourth line
>>>>>+<.>..<.>..<..                          Print the line of last sheep

```

# Answer
> 0 votes
# Zsh, 97 bytes

```
$1()O+=${s/o/-}
for s ('      \ '
"  ___/o>"
'-(___)" '
" '' ''  ")(eval {1..$1}'||O+=$s;';<<<$O)

```

Try it online!

Feels way too long.

# Answer
> 0 votes
# 05AB1E, ~~63~~ 61 bytes

```
•D:¨Mß²нĀùÜ<3¹º•“\
_/o>-()"'“ÅвJ.B×»R"-, o-"#vy`.;2F„'``.;]R

```

Try it online!

```
•...•“...“ÅвJ.B×»R"..."#vy`.;2F„'``.;]R  # trimmed program
                                      R  # push reversed...
             .B                          # list of lines in...
            J                            # joined...
          Åв                             # list of characters in...
     “...“                               # literal...
          Åв                             # with indices in base-10 values of base length of...
     “...“                               # literal...
          Åв                             # digits of...
•...•                                    # 258955905826915235144641900393055...
             .B                          # with length of longest line minus length of each line spaces appended to each line...
                                         # (implicit) with each element...
               ×                         # repeated...
                                         # implicit input...
               ×                         # times...
                »                        # joined by newlines...
                 R                       # reversed...
                           .;            # with first occurence of...
                          `              # second character of...
                         y               # variable...
                           .;            # replaced by...
                          `              # first character of...
                         y               # variable...
                        v                # for y in...
                  "..."                  # literal...
                       #                 # split by spaces...
                                   .;    # with first occurence of...
                                  `      # second character of...
                               „'`       # literal...
                                   .;    # replaced by...
                                  `      # first character of...
                               „'`       # literal...
                              F          # for n in [0, 1, 2, ...,
                             2           # ..., literal...
                              F          # ]
                                     ]   # exit loop
                                     ]   # exit loop
                                         # implicit output

```

---
Tags: code-golf, string, ascii-art, kolmogorov-complexity
---


title: Tape Measure String

text:
# Question
Title: Tape Measure String
**Motivation**: Sometimes you need to know where you are in a string. You want to be able to look at any part of a string and know exactly where you are, as far as possible.

**Challenge**: write a program to output a **tape measure string** of a given length. A **tape measure string** self describes its length-so-far as often as possible along it's own length.

**Rules**:

1. Your program must take one positive integer parameter, for the total length of the tape measure string
2. For each contiguous string of digits in the output, these digits must accurately report the length of the output so far - **inclusive**!
    1. Lengths are measured from the start of the string to the **end** of each number
3. As many length numbers as possible should be included in the string
4. Avoid ambiguity. Separators/delimiters can be used to avoid numbers being juxtaposed, i.e. `12` says twelve not one, two.
5. The string must always accurately report its total length at its end, with no trailing separators
6. You may need multiple separators to keep the lengths accurate, e.g. here's an example tape measure string of length 4: `1--4`

**Non prescriptive/exhaustive examples:**

* tape measure string of length 1: `1`
* tape measure string of length 2: `-2`
* tape measure string of length 3: `1-3`
* tape measure string of length 4: `1--4` or `-2-4` (both report lengths as often as possible, i.e. twice, and end with the correct total length)
* tape measure string of length 10: `1-3-5-7-10`
* tape measure string of length 11: `1-3-5-7--11` or `1-3-5--8-11` or `1-3--6-8-11` or `1--4-6-8-11` or `-2-4-6-8-11` (all have as many length numbers as possible, and finish with the total string length)

# Answer
> 13 votes
# Python, ~~50~~ ~~48~~ ~~47~~ 46 bytes

```
f=lambda x:x*"1"if x<2else f(x-len(`-x`))+`-x`

```

# Explanation

Pretty simple recursive lambda solution

Our base cases are 1 and 0 which are covered by `"1"*x` otherwise we get the string of `-x` with ``-x`` and prepend the result of calling the function on `len(`-x`)` less.

# Answer
> 5 votes
# Mathematica, ~~67~~ 57 bytes

*Thanks to Martin Ender for jettisoning 10 bytes!*

```
""["1"][[#]]/._@__:>#0[#-1-IntegerLength@#]<>ToString@-#&

```

Unnamed function taking a nonnegative integer argument and returning a string. Pretty much the obvious recursive algorithm: make sure the string ends with the input number preceded by a `"-"`, and then call the function again using `#0`.

But there's golfy fun to be had in implementing the algorithm. `""["1"][[#]]` denotes the `#`th argument of the expression `""["1"]`: the 0th argument is the head `""` and the 1st argument is visibly `"1"`, which provides the base cases of the recursion. If `#` exceeds 1, then `""["1"][[#]]` throws an error message and remains as an unevaluated function. But then `/._@__:>` is a rule that takes any unevaluated function and transforms it into the expression that comes next, which is the recursive call to the original function.

Original submission:

```
If[#<2,""["1"][[#]],#0[#-1-IntegerLength@#]<>"-"<>IntegerString@#]&

```

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

```
f=(n,s='',t=''+-n)=>n>1?f(n-t.length,t+s):n?n+s:s
```

```
<input type=number oninput=o.value=f(this.value)><br><textarea id=o></textarea>
```

# Answer
> 2 votes
# Pyth, 23 bytes

```
L?<b2*"1"b+y-bl+""_bs_b

```

Blatantly stole the recursive solution from Wheat wizard's answer. Also, I believe this is not golfed properly.

Try it here!

# Answer
> 1 votes
# Perl 6, 43 bytes

```
{[R~](-$_,{$_+.comb}...^*>-1).&{S/^\-1/1/}}

```

Explanation:

```
{                                         }  # A lambda.
                    ...                      # Generate a sequence...
      -$_                                    #   starting from the negated lambda argument,
         ,{        }                         #   continuing iteratively using the formula:
           $_+.comb                          #     Last element plus length of last element.
                        *>-1                 #   until we hit 0 or higher,
                       ^                         end-point not inclusive.
 [R~](                      )                # Reverse and concatenate the number sequence.
                             .&{         }   # Apply to this the transformation:
                                S/^\-1/1/    #   Remove the sign from a leading "-1".

```

So for example for input 10, it generates the sequence `(-10, -7, -5, -3, -1)`, and from that the string `-1-3-5-7-10`, and from that the final string `1-3-5-7-10`.

Try it online.

# Answer
> 0 votes
# C (gcc), 68 bytes

```
f(n){int*j;n<2?j="1"+!n:printf(f(n-asprintf(&j,"%d",-n)));return j;}

```

Try it online!
Borrows @Wheat Wizard's recursive solution.

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


title: Make them sum to 10,000

text:
# Question
Title: Make them sum to 10,000
We've recently reached the threshold of 10,000 questions on PPCG. Hooray! Let's celebrate this with a simple challenge.

## Input

Two integers \\$A\\$ and \\$B\\$, both in \\$\[1..9999\]\\$, such that \\$A+B\<10000\\$.

## Task

Your task is to add one single digit to one of these integers or one single digit to both of them such that \\$A+B=10000\\$. If adding a digit to both \\$A\\$ and \\$B\\$, it need not necessarily be the same digit.

The new digit can be added at the beginning, at the end or anywhere in the middle of the original integer. However, you can't add a leading zero.

*Example:*

For \\$A=923\\$, the following transformations are valid:

$$\color{red}1923\\92\color{red}73\\923\color{red}8$$

But these ones are **invalid**:

$$\color{red}{0}923\\\color{red}{10}923\\9\color{red}{4}2\color{red}{7}3$$

Given \\$A=923\\$ and \\$B=72\\$, there are two possible solutions:

$$923\color{red}8 + 7\color{red}62 = 10000\\92\color{red}73 + 72\color{red}7 = 10000$$

## Output

You must print or output a list of all possible solutions.

For the above example, the expected output would be `[[9238,762],[9273,727]]`.

## Rules

* I/O can be processed in any reasonable, unambiguous format. You may use strings, lists of digits, etc. instead of integers.
* The input is guaranteed to have at least one solution.
* You are allowed not to deduplicate the output. However, it would be appreciated if the test code is deduplicating it with some post-processing, for instance in the *footer* section of TIO.
* This is a challenge.

## Test cases

```
Input    --> Output

934, 654 --> [[9346,654]]

737, 628 --> [[7372,2628]]

9122, 88 --> [[9122,878]]

923, 72  --> [[9238,762],[9273,727]]

998, 3   --> [[9968,32],[9987,13]]

900, 10  --> [[9900,100],[9090,910]]    NB: solutions such as [9000,1000] are NOT valid
                                            (more than one digit added to 10)

363, 632 --> [[3673,6327],[3638,6362]]

288, 711 --> [[2881,7119],[2882,7118],[2883,7117],[2884,7116],[2885,7115],[2886,7114],
              [2887,7113],[2888,7112],[2889,7111]]

365, 635 --> [[365,9635],[1365,8635],[2365,7635],[3365,6635],[4365,5635],[5365,4635],
              [6365,3635],[7365,2635],[8365,1635],[9365,635],[3065,6935],[3165,6835],
              [3265,6735],[3465,6535],[3565,6435],[3665,6335],[3765,6235],[3865,6135],
              [3965,6035],[3605,6395],[3615,6385],[3625,6375],[3635,6365],[3645,6355],
              [3655,6345],[3675,6325],[3685,6315],[3695,6305],[3650,6350]]

```

# Answer
> 12 votes
# Haskell, ~~99 97 82~~ 81 bytes

<sup>-16 bytes thanks to Delfad0r (taking inputs as a list, using abusing that we don't need to deduplicate -\> n can always be in *\[0,4\]* & using a clever combination of input-format and `ap`)!</sup>

```
filter((==1e4).sum).mapM([read.(take n<>(c:).drop n)|c<-['0'..'9'],n<-[0..4]]<*>)

```

Try it online!

# Answer
> 9 votes
# , 96 bytes

```
function(a,b)(w<-grep(gsub("",".?",a?b),1:1e4?9999:0)?r<-1e4-w)[w+a<2&r+b<2]
"?"=paste
"+"=adist

```

Try it online!

## Explanation (ungolfed)

```
function(a,b){
    # Regex inserting ".*": (998,3) => ".?9.?9.?8.? .?3.?"
  regex <- gsub("",".?",paste(a,b))
    # Positions matching in the whole vector of strings that add to 10K ("1 9999", "2 9998", "3 9997", "4 9996", ...)
  w <- grep(regex,paste(1:1e4,9999:0))
    # 10K minus these matching positions
  r <- 1e4-w
    # Form position-string vector of ('pos1 10K-pos1', 'pos2 10K-pos2', ...)
  paste(w,r)[
  # Filter only those positions where the edit distance between the matched numbers and the originals are less than 2
    adist(w,a)<2 & adist(r,b)<2
  ]
}

```

We assign `?` to `paste`. That lets us do something cool: `a<-b?c<-d` does inline assignments within the `paste` call, which we couldn't do with any other operator than `?`, since it has lower precedence than `<-`.

Now as @JoKing kindly pointed out, there can be cases like `900 10` where two insertions could take place such as `9100 8100`. So we filter out matches where the number of characters in either number has increased by more than 1. The quick way to do this is with the Levenshtein edit distance `adist` which we bind to `+`.

# Answer
> 7 votes
# Pyth, ~~28~~ ~~27~~ ~~25~~ ~~24~~ ~~22~~ 20 bytes

```
fq^;4sT*FmvsmXLkdThl

```

Try it online here, or verify all the test cases here \- the test suite deduplicates the result by prepending a `{`.

Input is as a list of strings.

```
fq^;4sT*FmvsmXLkdThldQ   Implicit: Q=eval(input()), T=10
                         Trailing d, Q inferred
         m           Q   Map each input string, as d, using:
                   ld      Take the length of d
            m     h        Map 0 to the above (inclusive), as k, using:
             X  d            Insert into d...
               k             ... at position k...
              L  T           ... each number [0-9]
           s               Flatten the result
          v                Convert each back to an integer
       *F                Take the cartesian product of the result
                         (this generates all possible pairs of mutated numbers)
f                        Keep the pairs, as T, where...
     sT                  ... the sum of the pair...
 q                       ... is equal to...
  ^;4                    ... 10,000 (; == 10 here, so this is 10^4)

```

*Edit 4: Saved another 2 bytes, thanks to Mr Xcoder - `v` vectorises by default, and `L` uses `m` underneath, so mapping over range is implied, making the `U` unneccesary too*

*Edit 3: Introduced to global use of `;` operator to retain access to 10 to save 2 bytes, thanks to FryAmTheEggman and issacg:*

```
fq^T4sT*FmvMsmXLkdUThl

```

*Edit 2: I forgot the sum operator exists, how embarassing...*

*Edit 1: Previous version accepted a list of integers as input, performing string conversions manually, for 27 bytes:*

```
fq10000+FT*FmvMsmXLk`dUThl`

```

# Answer
> 4 votes
# Perl 6, 64 bytes

```
->\a{grep {all (a Z~$_)X~~/^(.*)(.*)$0.?$1$/},(^1e4 Z(1e4...1))}

```

Try it online!

This is a port of G B's answer using a regex to check if the numbers are valid. Thanks to **nwellnhof** for porting it.

## Old answer, ~~127 110~~, 88 bytes

*-22 bytes thanks to nwellnhof!*

```
->\a{grep {all ~<<a Z∈.map:{.comb.combinations(.comb-1..*)>>.join}},(^1e4 Z(1e4...1))}

```

Try it online!

Anonymous code block that takes in a list of two numbers and returns a list of pairs of numbers.

Rather than fiddle about with inserting the digits in, this solution checks every combination of numbers that sum to 10000 and filters that the given numbers are part of the pair.

### Explanation:

```
->\a{  # Anonymous code block that takes an argument a
     grep ... ,(^1e4 Z(1e4...1))    # Filter from all pairs that add to 10000
         {      ~<<a     # Stringify the contents of a
                     .map:{      # Map the pair to
                           .comb  # The digits of the number
                           .combinations(.comb-1..*)  # The combinations of the digits
                           >>.join  # Each combination joined
                           # Note that combinations preserve order
                           # "123" -> (12,13,123)
                          }
          all       Z∈   # Zip that each element of a is an element of the combination
         }
}

```

# Answer
> 3 votes
# , ~~179 161 150~~ 144 bytes

```
function(a,b,w=g(a),r=rep(g(b),e=1e4))paste(w,r)[w+r==1e4]
g=function(x,n=sum(x|1)){for(i in 0:n)for(j in 0:9)F=c(F,append(x,j,i)%*%10^(n:0));F}

```

Try it online!

35 bytes saved by @JayCe and @Giuseppe.

### Explanation

Helper function g gets all possible insertions.

```
g <- function(x,            # Input vector of digits
              n=sum(x|1)    # Length of x
              ) {
  for(i in 0:n)             # i is the insertion point
    for(j in 0:9)           # j is a digit from 0 to 9
      # Dot product of vector of digits with insert and 10^(n:0) performs the
      # conversion to integer (and gets rid of the leading 0s)
      F=c(F,append(x,j,i)%*%10^(n:0))  # F is a non-reserved built-in alias to FALSE (numerically 0)
  F
}

```

Main function.

```
f <-
function(a,                 # Input vectors of digits
         b,
         w=g(a),            # Get all possible insertions for a
         r=rep(g(b),e=1e4)  # Insertions for b replicated 1e4 times each
         )
  paste(w,r)[w+r==1e4]      # paste and w+r recycle w to match length of r
                            # Lots of duplication!

```

I've noticed after the fact that this is essentially the same logic as the Pyth answer.

# Answer
> 3 votes
# Ruby, ~~93~~ 91 bytes

```
->a,b{(1..r=10000).map{|x|/^(.*)(.*:)\1.?\2(.*)(.*):\3.?\4$/=~[a,x,b,y=r-x]*?:&&[x,y]}-[p]}

```

Try it online!

Try every single number up to 10000, and use the regex to check if the numbers match.

# Answer
> 2 votes
# Jelly, 30 bytes

```
DµJṬ€k€jþ9Ż¤;9R¤;€$ḌF)ŒpS=ȷ4ƊƇ

```

Try it online!

Kind of clumsy because Jelly has no insertion.

# Explanation

```
                                   Given [a, b].
Dµ                   )             Get [digits(a), digits(b)] then map:
  JṬ€k€jþ9Ż¤;9R¤;€$ḌF                Generate all the insertions.
                      Œp           Cartesian product: get all pairs.
                        S=ȷ4ƊƇ     Filter for: sum equal to ȷ4 (10000).

                       Given e.g. [6,3,5]:
J                      Get [1,2,3].
 Ṭ€                    Get [[1], [0,1], [0,0,1]].
   k€                  Split input with these: gets us
                         [[6],[3,5]] , [[6,3],[5]] , [[6,3,5],[]]
     jþ9Ż¤             Join table-wise with [0..9]
                         → [[[6,0,3,5], [6,3,0,5], [6,3,5,0]],
                            [[6,1,3,5], [6,3,1,6], [6,3,5,1]], …]
          ;9R¤;€$      Append the prefixings of the input by [1..9].
                           [[1,6,3,5], [2,6,3,5], [3,6,3,5]]…
                 ḌF    Undigits all, and flatten.

```

# Answer
> 2 votes
# Python 3, ~~165 160 153 125~~ 117 bytes

* Saved 5 bytes thanks to @JackBrounstein suggestion to remove `set` from the return value, as the output can contain duplicates.
* Saved 7 by replacing `range(len(s))` with `range(5)`.
* Saved 23 bytes thanks to @Eric Duminil's suggestion to replace `itertools` with nested list comprehensions (and removing a space).
* Saved 8 thanks to @Jo King's suggestion to replace nested list comprehension with a single loop and modulus operator.

~~Using `itertools` and a simple helper function.~~ Accepts strings as input, returns a set of ints as output.

```
c=lambda s:[int(s[:i%5]+str(i//5)+s[i%5:])for i in range(50)]
lambda a,b:{(i,j)for i in c(a)for j in c(b)if i+j==1e4}

```

# Answer
> 2 votes
# Javascript (Node) - 183 136 123 Bytes

**123 Bytes thanks to Shaggy**

```
a=>b=>(o={},g=(s,h)=>[...s+0].map((y,x)=>{for(y=10;y--;)h(s.slice(0,x)+y+s.slice(x))}))(a,x=>g(b,y=>1e4-x-y?0:o[+x]=+y))&&o

```

**136 Bytes thanks to Arnauld**

```
e=(h,c,i=h.length+1,j)=>{for(;i--;)for(j=10;j--;)c(h.slice(0,i)+j+h.slice(i))}
f=(a,b,c=[])=>e(a,n=>e(b,m=>1E4-n-m||c.push([+n,+m])))||c

```

**Old Code**

Not proud of it, but figured I'd submit anyways. Creates a string prototype function akin to map which takes up the bulk of the bytes. Function just iterates through both permutations, and finds when 1000-a-b is 0. Takes input as strings.

```
String.prototype.e=function(c){let h=this,L=h.length,i,j;for(i=0;i<=L;i++)for(j=0;j<=9;j++)c(h.slice(0,i)+j+h.slice(i,L));}
f=(a,b,c=[])=>a.e(n=>b.e(m=>1E4-n-m?c:c.push([+n,+m])))?c:c

```

Try it online!

**Ungolfed**

```
String.prototype.e=function(c) {
  let h=this,L=h.length,i,j;
  for(i=0;i<=L;i++)
    for(j=0;j<=9;j++)
      c(h.slice(0,i)+j+h.slice(i,L));
}
f=(a, b, c=[]) =>
  a.e(n =>
    b.e(m =>
      1E4-n-m ? c : c.push([+n,+m])
    )
  ) ? c : c

```

# Answer
> 2 votes
# Japt, ~~30~~ ~~29~~ ~~25~~ 23 bytes

Takes input as an array of strings, outputs an array of arrays of strings.

```
£L²ôs f_à øX
rï k@L²aXx

```

Try it

---

## Explanation

```
£L²ôs f_à øX
£                :Map each X
 L               :  100
  ²              :  Squared
   ô             :  Range [0,L²]
    s            :  Convert each to a string
      f_         :  Remove elements that return false
        à        :    All combinations of current element
          øX     :    Contains X?
rï k@L²aXx
r                :Reduce by
 ï               : Cartesian product
   k@            :Remove each X that returns true (not 0)
     L²          :  100 squared
      a          :  Absolute difference with
        Xx       :   X reduced by addition

```

# Answer
> 2 votes
# PHP, ~~162~~ 159 bytes

lovely example for a generator function!

```
function f($n){for($n+=.1;$n>=1;$n/=10)for($d=-1;$d++<9;)yield strtr($n,".",$d)/10|0;}foreach(f($argv[1])as$x)foreach(f($argv[2])as$y)$x+$y-1e4||print"$x+$y\n";

```

takes input from command line arguments; prints duplicates. Run with `-nr '<code>` or try it online.

# Answer
> 2 votes
# Pyth, 18 bytes

```
fqsT^;4*FsMvXLRRTT

```

Demonstration, test suite (test suite is deduplicated with leading `{`).

The input is in the form of a list of two strings.

`XLRRTT`: L and R perform nested maps. Since there are 3 of them, we will perform a triply nested map of the `X` function. In this case, the `X` function will insert a character at a designated position into a string.

The string is the input, which is implicit and placed by the first `R`. The character ranges over `0 ... 9`, so we have all possible inserted digits, and is placed by the `L`. The range is given by `T`, which is implicitly set to `10`, which is implicitly treated as `[0 ... 9]`. The position ranges over `0 ... 9`, which is sufficient, because inserting a number after the 10th position will never be useful. Duplicate results are fine. The range is placed by the second `R`, and given by the second `T`.

`v`: Nested cast strings to ints.

`sM`: Flatten the second level of lists, leaving us with a list of all possible numbers after digit insertion, for each of the input numbers.

`*F`: Take the Cartesian product of the two lists of possible numbers.

`fqsT^;4`: Filter on the pairs whose product is `10000`. `;` takes the value of `10` here, as `T` is in use as the filter variable, and `;` always as the value of the variable which is in use.

# Answer
> 1 votes
# Jelly, 23 bytes

```
œcL’$$€ċ"⁹o⁼"Ạ
ȷ4ḶṚĖDçƇ

```

A monadic link accepting a list of lists of digits
(e.g. for the example of 923 and 72 the input is `[[9,2,3],[7,2]]`)

**Try it online!** (footer makes it so I/O is a pair of two integers in and a \[formatted\] list of pairs of integers out)

Or see the test-suite.

### How?

Checks all the pairs of "numbers" (lists of digits) which sum to 10000 for validity by forming all ways to choose n-1 digits from those "numbers" maintaining order; and keeps those which are valid (where validity also allows for the "number" under test to be equal to the original "number").

```
œcL’$$€ċ"⁹o⁼"Ạ - Link 1, is piar valid?: pairToCheck, originalInputPair
      €        - for each list of digits in pairToCheck: e.g. [9,2,3]
     $         -   last two links as a monad:
    $          -     last two links as a monad:
  L            -       length                                 3
   ’           -       decremented                            2
œc             -     choices of that many items               [[9,2],[9,3],[2,3]]
         ⁹     - chain's right argument (originalInputPair)
        "      - zip with: (i.e. apply the following f(x,y) *respectively* across the results above and the originalInputPair)
       ċ       -   count occurrences
            "  - zip with (this time with an implicit right argument of originalInputPair)
           ⁼   -   equal (non-vectorising version)
          o    - locgical OR (vectorising version) i.e. we now have: [OR(isOneDigitLonger(item1),isEqual(item1)), OR(isOneDigitLonger(item2),isEqual(item2))]
             Ạ - all?

ȷ4ḶṚĖDçƇ - Main Link: list (pair) of lists of digits
ȷ4       - literal 10^4 -> 10000
  Ḷ      - lowered range -> [0,1,2,...,9998,9999]
   Ṛ     - reversed -> [9999,9998,...,2,1,0]
    Ė    - enumerate -> [[1,9999],[2,9998],...,[9998,2],[9999,1],[10000,0]] (N.B. last is redundant, but this does not matter)
     D   - to decimals -> [[[1],[9,9,9,9]],[[2],[9,9,9,8]],...,[[9,9,9,8],[2]],[[9,9,9,9],[1]],[[1,0,0,0,0],[0]]]
       Ƈ - filter keep those for which this is truthy:
      ç  -   call last link as a dyad (with a right argument of the pair of lists of digits)

```

# Answer
> 1 votes
# Stax, 24 bytes

```
⌐çΘ♠╖øû°-h∟ñµ%üw▲∞Ç╫[½π=

```

Run and debug it

Those program takes its two inputs as an array of strings, like this.

```
["934", "654"]

```

# Answer
> 1 votes
# Charcoal, 33 bytes

```
ΦＥ×χφＩ⟦ι⁻×χφι⟧⌊Ｅι№Ｅ⊕ＬλΦλ⁻ξρ§⟦θη⟧μ

```

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

```
   χ                                10
    φ                               1000
  ×                                 Multiply
 Ｅ                                  Map over implicit range
       ι    ι                       Current value
        ⁻×χφ                        Subtract from 10000
      ⟦      ⟧                      Pair of values
     Ｉ                              Cast to string
Φ                                   Filter
                ι                   Current pair
               Ｅ                    Map
                     λ              Current value
                    Ｌ               Length
                   ⊕                Increment
                  Ｅ                 Map over implicit range
                       λ            Current value
                      Φ             Filter over characters
                         ξ          Range value
                          ρ         Character index
                        ⁻           Subtract
                            ⟦θη⟧    Original inputs as a list
                                μ   Index of current value
                           §        Get input at that index
                 №                  Count matching values
              ⌊                     Minimum
                                    Implicitly print each pair double-spaced

```

In case you didn't understand that, it runs through all the pairs of values that add to 10000 (as strings), then counts how many times each input matches against the result of deleting up to 1 character from the respective value. If the minimum count is nonzero then both inputs matched and this is a possible solution.

# Answer
> 1 votes
# Ruby, 110 bytes

Accepts strings as input, returns an array of array of integers.

Based on the python version. For a given integer, `C` creates an array of numbers that can be created by adding a digit.

The lambda iterates over every possible pair and selects the one whose sum is 10000.

```
C=->n{(0..49).map{|i|([n[0...i%5],i/5,n[i%5..-1]]*'').to_i}}
->(a,b){C[a].product(C[b]).select{|i,j|i+j==1e4}}

```

Try it online!

# Answer
> 1 votes
# 05AB1E (legacy), 36 bytes

```
0ìε.œʒg3‹}εU9ÝεXDgiìësý}}}˜}`âʒOT4mQ

```

Can without a doubt be golfed substantially.. Especially inserting the digits, including a leading/trailing one.

Try it online or verify all test cases (`ê` in the footer is to Uniquify & Sort).

**Explanation:**

```
0ì                            # Prepend a 0 before each of the input numbers
  ε                        }  # Map each to:
   .œ                         #  Take all possible partitions
     ʒg3‹}                    #  Only keep those of length 1 or 2
          ε              }    #  Map each partition to:
           U                  #   Pop and store the partition in variable `X`
            9Ý                #   List in the range [0, 9]
              ε         }     #   Map each of those digits to:
               X              #    Get the variable `X`
                Dgi           #    If it's a single number (length == 1):
                   ì          #     Prepend `X` before this digit
                  ë           #    Else (length == 2):
                   sý         #     Join both numbers in `X` with the current digit
                  }           #    Close the if-else
                          ˜   #   Flatten the list of lists
`                             # Now push both lists to the stack
 â                            # Create all possible pairs (cartesian product)
  ʒ                           # Filter this list of pairs by:
   O                          #  Take the sum of the two numbers
    T4m                       #  Push 10000 (10^4)
       Q                      #  And check if they are equal

```

# Answer
> 1 votes
# Vyxal, 43 bytes

```
⌐ƛ⟨⟩n£¥Lʀ(x|n¬₀r(¥CC←x nSṀṅIJ));ḣhẊ'∑k2=

```

Try it Online! Takes input of the form: `"a,b"`

**Explanation:**

```
?⌐ƛ⟨⟩n£¥Lʀ(x|n¬₀r(¥CC←x nSṀṅIJ));ḣhẊ'∑k2= # full program
?⌐                                       # split implicit input on ","
  ƛ⟨⟩n£¥Lʀ(x|n¬₀r(¥CC←x nSṀṅIJ));         # "insert" lambda map over input
                                ḣh       # unlist them
                                  Ẋ      # cartesian product [a,b]*[c,d]=[[a,c],[a,d],[b,c],[b,d]]
                                   '∑k2  # filter lambda, sum of pair == 10000

```

The insert lambda can definitely be improved, but I am having trouble figuring out a way to map it instead of explicitly loop over it.

# Answer
> 0 votes
# Jelly, 25 bytes

```
LŻœṖ€z⁶ZjþØDVẎṢḊ)p/S⁼ȷ4ƊƇ

```

Try it online!

Not the shortest Jelly solution here but maybe someone can golf this? I am stumped

---
Tags: code-golf, integer
---


# Question
Title: Programming Less-Than, Greater-Than and Equal-To functions using Restricted Source
I'm currently working with a branchless language which does not have native Less-Than, Greater-Than or Equal-To functions. I do however have `min`, `max` and `abs` functions and standard arithmetic (`+`, `-`, `/` and `*`) available to me.

I'd like to create these three functions (as `L(a, b)`, `G(a, b)` and `E(a, b)` respectively, which will output `0` for `false` and `1` for `true`. So, for example, `L(3, 7)` would return `1` for `true` whereas `G(3, 7)` would return `0` for `false`, and `E(3, 7)` would also return `0`, etc.

The `min` and `max` functions only allow you to pass two parameters, `a` and `b`, and then spits out the respective minimum or maximum of the two parameters. The `abs` function takes the one parameter and returns the absolute value.

I've postulated that given that the `min(a, b)` is equivalent to:

`L(a,b) * a + (1 - L(a,b)) * b`

It would stand to reason that:

`L(a,b) = (min(a,b) - b) / (a - b)`

and similarly:

`max(a,b) = G(a,b) * a + (1 - G(a,b)) * b`

therefore:

`G(a,b) = (max(a,b) - b) / (a - b)`

But this is where I get stumped because, I'm not sure how to account for the possibility of `a-b` equalling `0` in both instances, which as a result stumps me on how to approach the `E(a, b)` function.

So my question is this... Given that I only currently have access to basic arithmetic functions as well as `min(a,b)`, `max(a,b)` and `abs(a)`, and because of the language being branchless (therefore no loops), is there a way to programmatically account for the `a-b` divide-by-zero issue such that if I do have a scenario where `a == b` that these functions can return zero for either `L()` or `G()`, otherwise output the original equations I have derived, and also be able to provide code for `E(a, b)`?

Given that this is fairly generic (hey, I've written it in psuedocode!) I'd appreciate some insight on how to proceed. In this case, the solution needs to work with both integers as well as floats.

Context: This is research for a personal project I'm working on relating to binary registers, thus the need for 1's and 0's for output and I'm kinda stuck at this point.

# Answer
> 6 votes
# Integers and round-to-zero integer division

```
// 1 if x >= y, 0 otherwise
GE(x, y) = (x - y + 1) / (abs(x - y) + 1)
LE(x, y) = GE(y, x)
E(x, y) = GE(x, y) * LE(x, y)
L(x, y) = LE(x, y) - E(x, y) = 1 - GE(x, y)
G(x, y) = GE(x, y) - E(x, y) = 1 - LE(x, y)

```

If `x - y` is negative, `x - y + 1` has smaller magnitude than `abs(x - y) + 1`, so the division rounds to 0.

If `x - y` is zero or higher, `x - y + 1` is the same as `abs(x - y) + 1`, so the result is 1.

# Integers and floored integer division

```
GE(x, y) = (x - y + abs(x - y) + 1) / (abs(x - y) * 2 + 1)

```

If `x - y` is negative, the numerator is fixed at 1, but the denominator is at least 3. Therefore the result is zero.

If `x - y` is zero or positive, the numerator and the denominator are the same, so the result is 1.

# Floating-point numbers

MarcMush pointed out a possible use of `eps`, the smallest representable number greater than 0. GE can be implemented for floating-point numbers using it:

```
GE(x, y) = (max(x - y, -eps) + eps)/(abs(x - y) + eps)

```

I haven't found any way without `eps` or the floor function. (If `floor` is available, flooring the second solution works for floats.) tsh pointed out that we can't get a (true) discontinuous function from a bunch of continuous functions, so I'm pretty sure it is impossible without `eps` or an additional built-in that provides discontinuity.

Assuming an IEEE floating-point representation, the solution above is expected to give exact results (exactly 0 or exactly 1) for all non-NaN, non-infinite floating-point values of `x` and `y`.

# Answer
> 4 votes
This answer only works on integer values :)

## Test Zero

We all know that

$$ (t+1)(t-1)=t^2-1 $$ $$ t\cdot t-(t+1)(t-1)=1 $$

As long as \\$t\\$ is integer.

$$ t\cdot t-|t+1|\cdot|t-1| = \begin{cases} 1 & t\ne 0 \\ -1 & t = 0\\ \end{cases} $$

So we have:

```
isZero(t) = (t*t-abs(t+1)*abs(t-1)+1)/2

```

## Build others

And then, you can have

```
GreaterThanOrEqual(a, b) = isZero(max(b-a, 0))
LessThanOrEqual(a, b) = GreaterThanOrEqual(b, a)
Equal(a, b) = GreaterThanOrEqual(a, b) * LessThanOrEqual(a, b)
GreaterThan(a, b) = GreaterThanOrEqual(a, b) - Equal(a, b)
LessThan(a, b) = LessThanOrEqual(a, b) - Equal(a, b)

```

# Answer
> -2 votes
Assuming floor division: E(x,y) = (1 - abs(x-y)) / (1 + abs(x-y)) L(a,b) = E(min(a,b), a) - E(a,b) G(a,b) = E(max(a,b), a) - E(a,b)

---
Tags: number, tips, atomic-code-golf, logic
---


title: Generate newspaper page number sets

text:
# Question
Title: Generate newspaper page number sets
A newspaper is made of several sheets; for the purposes of this question, each sheet of newsprint holds four pages of the final newspaper. Here is an example of three sheets of newsprint making up a newspaper with twelve pages:

```
 ___________
|2    |   11|
|  ___|_____|_
| |4    |    9|
|_|  ___|_____|_
  | |6    |    7|
  |_|     |     |
    |     |     |
    |_____|_____|

```

(Pages 1, 3, 5, 8, 10 and 12 are on the reverse of these sheets so you can't see them here.)

Your challenge, should you choose to accept it, is to output all the sets of pages that are on each sheet of a given newspaper.

You can take either the number of sheets (which is always a positive integer) or the number of pages (which is always a positive multiple of 4), but please indicate which.

You can output the sets of pages in any reasonable order, as long as it is clear which pages belong in which set.

For example, given an input of 3 sheets or 12 pages, you could output (1, 2, 11, 12), (3, 4, 9, 10) and (5, 6, 7, 8); or you could output (8, 5, 7, 6), (10, 3, 9, 4) and (12, 1, 11, 2); or any variant thereof, but you cannot of course output 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

This is code golf, so please make your program or function as short as possible. (I will even accept the shortest overall program as the answer on request of its author if doing so will earn me a Winter Bash hat.)

# Answer
# convey, 34 bytes

```
}
/1:`%""{
^1"v4!<
+"+v}+1
^<","-}

```

Try it online!

Pushes `n` and `n+1` to the right per loop.

For each value outputs `i` and `i-pages+1`.

Whenever the left loop passes through the top part, output a newline `/}`. Allow `n` to pass the loop only `pages % 4` times.
> 11 votes

# Answer
# , 18 bytes

Takes number of sheets as input

```
_4>:\2/:@(,|.)@#i.

```

Try it online!

```
_4>:\2/:@(,|.)@#i.
                i.  0…n: 0 1 2
     2         #    repeat each 2 times: 0 0 1 1 2 2
         (,|.)@     append its rotated version: 0 0 1 1 2 2 2 2 1 1 0 0
      /:@           get the indices to sort: 0 1 10 11 2 3 8 9 4 5 6 7
_4  \               group by 4: 0 1 10 11, 2 3 8 9, 4 5 6 7
  >:                and increment: 1 2 11 12, 3 4 9 10, 5 6 7 8

```
> 8 votes

# Answer
# Husk, 9 bytes

```
←½Sz+↔C2ḣ

```

Try it online!

Argument is the number of pages.

```
        ḣ   # list of all the page numbers 1..input
      C2    # split into groups of two
  S         # hook: S(fgx) means f(x,g(x))
   z        # zip together
    +       # by combining elements from both lists
            # x = the list of groups of two)
     ↔      # and itself reversed
←½          # now take just the first half of this list
            # of lists of 4-pages per sheet

```
> 5 votes

# Answer
# Perl 5 `-n`, 38 bytes

```
$,=$";say$.++,$.++,$_--,$_--while$_>$.

```

Try it online!

Takes the number of pages as input
> 4 votes

# Answer
# APL (Dyalog Extended), <sup>~~16~~</sup> 14 bytes

```
¯1 4⍴⍋2/,∘⌽⍨…⎕

```

Try it online!, Stax

A port of xash's solution.

a full program which returns a matrix.

-2 bytes from Bubbler.
> 4 votes

# Answer
# , 48 bytes

```
function(N)split(rbind(x<-1:N,N:1)[x],(x-1)%/%4)

```

Try it online!

Takes input as the number of pages.

# , 51 bytes

```
function(N)split(1:(4*N),c(x<-rep(1:N,e=2),rev(x)))

```

Try it online!

Takes input as number of sheets.
> 3 votes

# Answer
# Scala, 37 bytes

```
p=>1.to(p/2)zip p.to(p/2,-1)grouped 2

```

Try it online!

Returns an iterator of 2-element vectors, each containing a 2-tuple of page numbers opposite each other.
> 3 votes

# Answer
# Python 2, 46 bytes

```
def f(n,i=2):i>n>_;print~-i,i,n-1,n;f(n-2,i+2)

```

Try it online!

Takes the number of pages `n` as input.

A function that prints and terminates with error. If we avoid errors, many different ways to structure the code come out very close.

**50 bytes**: Try it online!

```
i=n=input()
while i*2>n:i-=2;print-~i,i+2,n+~i,n-i

```

**50 bytes**: Try it online!

```
n=input()
i=1
while i<n:print-~i,i,n-1,n;i+=2;n-=2

```

**51 bytes**: Try it online!

```
n=input()
i=1
while i*2<n:print-~i,i,n-i,n-i+1;i+=2

```

**51 bytes**: Try it online!

```
f=lambda n,i=1:n/i*[0]and[(i,i+1,n-1,n)]+f(n-2,i+2)

```

**51 bytes**: Try it online!

```
lambda n:[(i,i+1,n-i,n-i+1)for i in range(1,n/2,2)]

```
> 3 votes

# Answer
# AWK, 46 43 bytes

```
x=$1{for(;y<x;)$++v=++y","++y","x--","x--}1

```

Takes the number of pages.

```
x=$1{

```

Set `x` to the number of pages. That will always evaluate to true given the rules, so the block of code will always run.

```
     for(;y<x;)

```

Loop until the forward page counter `x` is larger then the backwards page counter `y`. It's effectively looping once for every 4 pages, since `x` and `y` both change by 2 each time through the loop.

```
               $++v=++y","++y","x--","x--

```

Set positional argument `v` (incremented before it's used) to the next set of 4 pages, adjusting the forward and backwards counters as they are used.

```
                                         }

```

Ends the code block.

```
                                          1

```

An unconditionally true test with no defined code block causes the default action, which is to print all the positional arguments joined by the `OFS` variable. The default for that is a space.

Try it online!
> 3 votes

# Answer
# K (oK), ~~21~~ 19 bytes

-2 bytes thanks to coltim

```
 {1+0N 4#<x,|x:&x#2}

```

Try it online!

A port of xash's J solution \- please upvote it too!
> 3 votes

# Answer
# Jelly, 7 bytes

```
ḶạÞH‘s4

```

A monadic Link accepting the number of pages (four times the number of sheets) which yields a list of lists of the page numbers belonging to each sheet.

**Try it online!**

### How?

```
ḶạÞH‘s4 - Link: integer, P   e.g.  12
Ḷ       - lowered range (P)        [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]
   H    - halve (P)                6
  Þ     - sort by:
 ạ      -   absolute difference  ( [ 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5] )
        -                       -> [ 6, 5, 7, 4, 8, 3, 9, 2,10, 1,11, 0]
    ‘   - increment                [ 7, 6, 8, 5, 9, 4,10, 3,11, 2,12, 1]
      4 - four                     4
     s  - split into chunks        [[7,6,8,5],[9,4,10,3],[11,2,12,1]]

```
> 3 votes

# Answer
# JavaScript (ES6), 47 bytes

```
f=(n,N=1)=>N<n?[[N,N+1,n-1,n],...f(n-2,N+2)]:[]

```

Try it online!
> 2 votes

# Answer
# Ruby 2.7, 43 bytes

```
->n{((1..n/2)%2).map{|v|[v,v+1,n-v,n-v+1]}}

```

No TIO link, as TIO supports an older version of Ruby.

---

# Ruby, 45 bytes

```
f=->n,k=1{k<n ?[[k,k+1,n-1,n]]+f[n-2,k+2]:[]}

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~72~~ 70 bytes

* -2 bytes thanks to ceilingcat

Takes the number of physical pages.

I compute the last page and then loop through each physical page, getting the distance from the bounds for each one starting from the last page (the middle page numbers).

```
f(n,i,j){for(i=n*4;n--;)printf("%d/%d/%d/%d ",j+1,i-j,++j,i-j,j=n*2);}

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 7 bytes

Input is the number of pages, output is in a different order, both the pages on each sheet and the sheets.

```
Lι€Âøιн

```

Try it online!

```
          # implicit input                          8
L         # push the range [1..input]               [1, 2, 3, 4, 5, 6, 7, 8]
 ι        # uninterleave, push [a[0::2],a[1::2]]    [[1, 3, 5, 7], [2, 4, 6, 8]]
  €Â      # duplicate and reverse each list         [[7, 5, 3, 1], [1, 3, 5, 7], [8, 6, 4, 2], [2, 4, 6, 8]]
    ø     # transpose the list of lists             [[7, 1, 8, 2], [5, 3, 6, 4], [3, 5, 4, 6], [1, 7, 2, 8]]
     ι    # uninterleave                            [[[7, 1, 8, 2], [3, 5, 4, 6]], [[5, 3, 6, 4], [1, 7, 2, 8]]]
      н   # take the first element                  [[7, 1, 8, 2], [3, 5, 4, 6]]

```

---

# 05AB1E, 8 bytes

Takes the number of pages as an input. Output is in the natural order.

```
Lι€Âø€{Ù

```

Try it online!

```
          # implicit input                          8
L         # push the range [1..input]               [1, 2, 3, 4, 5, 6, 7, 8]
 ι        # uninterleave, push [a[0::2],a[1::2]]    [[1, 3, 5, 7], [2, 4, 6, 8]]
  €Â      # duplicate and reverse each list         [[7, 5, 3, 1], [1, 3, 5, 7], [8, 6, 4, 2], [2, 4, 6, 8]]
    ø     # transpose the list of lists             [[7, 1, 8, 2], [5, 3, 6, 4], [3, 5, 4, 6], [1, 7, 2, 8]]
     €{   # sort each list                          [[1, 2, 7, 8], [3, 4, 5, 6], [3, 4, 5, 6], [1, 2, 7, 8]]
       Ù  # uniquify the list of lists              [[1, 2, 7, 8], [3, 4, 5, 6]]

```
> 2 votes

# Answer
# Charcoal, ~~17~~ 14 bytes

Thanks to Neil for -3 bytes!

```
ＩＥ⪪…⁰⊘θ²⁺⊕ι⁻θι

```

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

Input is (now) the number of pages.

### Explanation

```
Ｉ               Cast to string
  Ｅ             Map (forEach)
    ⪪    ²       Split on 2 (split into slices of length 2)
     …⁰          Range from 0...
       ⊘θ        ...to half of first input (θ)
          ⁺⊕ι    Add (concatenate) ι (current item, which is the slice), with every element incremented...
             ⁻θι ...to first input (θ) minus the slice (ι)

```
> 1 votes

# Answer
# PowerShell, 56 52 49 bytes

-4 bytes thanks to Neil!
-3 bytes thanks to mazzy!

Takes input as the number of pages:

```
param($x)for(;$x-$y){++$y,++$y,$x--,$x---join","}

```

Try it online!
> 1 votes

# Answer
# Bash, 42 bytes

***-1 bytes** from @pxeger*

```
for((x=$1;x>y;)){ echo {,}$[++y]\ $[x--];}

```

~~Try it online!~~  Try it online!

I'm usually the Zsh guy, but here Bash wins by a few bytes because it evaluates brace expansion **before** parameter expansion:

```
echo {,}{$[++y],$[x--]}
echo $[++y] $[x--] $[++y] $[x--]

```
> 1 votes

# Answer
# Vyxal , ~~14~~ 13 bytes

```
ƛd›D⁰4*ε:›^›W

```

Try it Online!
> 1 votes

# Answer
# 05AB1E, ~~20~~ 11 bytes

```
L2ô2ä`Rδ«Å\

```

Try it online!

*-9 thanks to @ovs*
> 0 votes

# Answer
# Jelly, 8 bytes

```
Żx2m0Ụs4

```

Try it online!

Another port of xash’s answer, drop that an upvote as well

## How it works

```
Żx2m0Ụs4 - Main link. Takes n on the left
Ż        - [0,1,2,...,n]
 x2      - [0, 0, 1, 1, 2, 2, ..., n, n]
   m0    - Append its reverse
     Ụ   - Grade up; sort the indices by values
      s4 - Split into runs of 4

```
> 0 votes

# Answer
# 05AB1E,  ~~10~~  9 bytes

-1 thanks to ovs!

```
LΣ<I;α}4ô

```

**Try it online!**

Port of my Jelly answer. Input is the number of pages (four times the number of sheets).

```
LΣ<I;α}4ô
L         - range
 Σ   }    - sort by:
  <       -   decrement
   I      -   push input
    ;     -   halve
     α    -   absolute difference
       4  - push four
        ô - split into chunks

```
> 0 votes

---
Tags: code-golf
---


title: Compute the Discrete Fourier Transform

text:
# Question
Title: Compute the Discrete Fourier Transform
Implement the Discrete Fourier Transform (DFT) for a sequence of any length. This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input.

The algorithm will compute a result based on standard DFT in the forward direction. The input sequence has length `N` and consists of `[x(0), x(1), ..., x(N-1)]`. The output sequence will have the same length and consists of `[X(0), X(1), ..., X(N-1)]` where each `X(k)` is defined by the relation below.

$$X\_k\overset{\text{def}}{=}\sum\_{n=0}^{N-1}x\_n\cdot e^{-2\pi ikn/N}$$

## Rules

* This is so the shortest solution wins.
* Builtins that compute the DFT in forward or backward (also known as inverse) directions are not allowed.
* Floating-point inaccuracies will not be counted against you.

## Test Cases

```
DFT([1, 1, 1, 1]) = [4, 0, 0, 0]
DFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j]
DFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j]
DFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]

```

### Help

There was a previous challenge for finding the DFT using a FFT algorithm for sequences with lengths equal to a power of 2. You may find some tricks there that might help you here. Keep in mind that this challenge does not limit you to any complexity and also requires your solution to work for sequences of any length.

# Answer
> 4 votes
# Jelly, ~~16~~ 15 bytes

```
LR’µ×'÷L-*²³÷S€

```

Try it online!

### How it works

```
LR’µ×'÷L-*²³÷S€  Main link. Argument [x(0), ..., x(N-1)].

L                Length; yield N.
 R               Range; yield [1, ..., N].
  ’              Decrement; yield [0, ..., N-1].
   µ             Begin a new, monadic chain. Argument: [0, ..., N-1]
    ×'           Spawned multiply [0, ..., N-1] with itself, yielding the matrix
                 of all possible products k×n.
      ÷L         Divide each product by N.
        -*       Compute (-1)**(kn÷L) for each kn.
          ²      Square each result, computing (-1)**(2kn÷L).
           ³÷    Divide [x(0), ..., x(N-1)] by the results.
             S€  Compute the sum for each row, i.e., each X(k).

```

# Answer
> 8 votes
# Python 3, 77 bytes

```
lambda x,e=enumerate:[sum(t/1j**(4*k*n/len(x))for n,t in e(x))for k,_ in e(x)]

```

Test it on Ideone.

The code uses the equivalent formula

# Answer
> 4 votes
# J, ~~30~~ 20 bytes

3 bytes thanks to @miles.

Uses the fact that `e^ipi = -1`.

The formula becomes `X_k = sum(x_n / ((-1)^(2nk/N)))`.

```
+/@:%_1^2**/~@i.@#%#

```

### Usage

```
>> DCT =: +/@:%_1^2**/~@i.@#%#
>> DCT 1 2 3 4 5
<< 15 _2.5j3.44095 _2.5j0.812299 _2.5j_0.812299 _2.5j_3.44095

```

where `>>` is STDIN and `<<` is STDOUT.

"Floating-point inaccuracies will not be counted against you."

# Answer
> 4 votes
# APL(Dyalog Unicode), 30 bytes SBCS

```
{⍵∘{+/⍺÷0j1*(4×⍵×⍳≢⍺)÷≢⍺}¨⍳≢⍵}

```

Adapted from the formula presented in this Python answer by Dennis

Try it on APLgolf!

# APL(Dyalog Unicode), 31 bytes SBCS

```
{⍵∘{+/⍺×*a÷⍨○0J¯2×⍵×⍳a←≢⍺}¨⍳≢⍵}

```

Try it on APLgolf!

A dfn submission, assumes `⎕IO←0`.

Ungolfed:

```
X ← {+/⍺×*(○0J¯2×⍵×⍳≢⍺)÷≢⍺}
f ← {⍵∘X¨⍳≢⍵}

```

APL translated to Python:

```
from math import *

def f(sequence):
    def X(n):
        return sum(
            sequence[b] # ⍺
            * e **      # ×*(...)
            (
                pi*-2j          # ○0J¯2
                * n             # ×⍵
                * b             # ×⍳≢⍺
                / len(sequence) # ÷≢⍺
            )
            for b in range(len(sequence))
        )
    return [X(i) for i in range(len(sequence))] # ⍵∘X¨⍳≢⍵

```

First it binds the sequence to a dfn, and runs the resulting function on each element in the range from \\$0\\$ to \\$N\\$ -- `{⍵∘{...}¨⍳≢⍵}`.

In the inner dfn it sums -- `+/` -- the sequence --  -- times \\$e\\$ to the power of -- `×*(...)` -- \\$\pi\\$ times \\$-2i\\$ -- `○0J¯2` -- times \\$k\\$ --  -- times each \\$n\\$ from \\$0\\$ to \\$N\\$ -- `⍳≢⍵` -- divided by \\$N\\$ -- `÷≢⍺`.

# Answer
> 3 votes
# MATL, ~~20~~ 16 bytes

```
-1yn:qt!Gn/E*^/s

```

Input is a column vector, i.e. use semicolon as separator:

```
[1; 1; 1; 1]
[1; 0; 2; 0; 3; 0; 4; 0]
[1; 2; 3; 4; 5]
[5-3.28571j; -0.816474-0.837162j; 0.523306-0.303902j; 0.806172-3.69346j; -4.41953+2.59494j; -0.360252+2.59411j; 1.26678+2.93119j]

```

This uses the formula in Leaky Nun's answer, based on the facts that exp() = −1, and that MATL's power operaton with non-integer exponent produces (as in most programming languages) the principal branch result.

**Try it online!**

Due to Octave's weird spacing when displaying complex numbers, the real and imaginary parts in each entry of the output are separated by a space, as are consecutive entries. If that looks too ugly, add a `!` at the end of the code (17 bytes) to have each entry of the output on a different line.

### Explanation

```
-1      % Push -1
y       % Get input implicitly. Push a copy below and one on top of -1
n:q     % Row vector [0 1 ... N-1] where N is implicit input length
t!      % Duplicate and transpose: column vector
Gn      % Push input length
/       % Divide
E       % Multiply by 2
*       % Multiply, element-wise with broadcast. Gives the exponent as a matrix
^       % Power (base is -1), element-wise. Gives a matrix
/       % Divide matrix by input (column vector), element-wise with broadcast
s       % Sum

```

# Answer
> 2 votes
# Pyth, 30

```
ms.e*b^.n1****c_2lQk.n0d.j0)QU

```

Test Suite

Very naive approach, just an implementation of the formula. Runs into various minor floating point issues with values which should be additive inverses adding to result in values that are slightly off of zero.

Oddly `.j` doesn't seem to work with no arguments, but I'm not sure if I'm using it correctly.

# Answer
> 2 votes
# Pyth, 18 bytes

Uses the fact that `e^ipi = -1`.

The formula becomes `X_k = sum(x_n / ((-1)^(2nk/N)))`.

```
ms.ecb^_1*cyklQdQU

```

Test suite.

# Answer
> 2 votes
# Julia, 45 bytes

```
~=endof
!x=sum(x./im.^(4(r=0:~x-1).*r'/~x),1)

```

Try it online!

The code uses the equivalent formula

# Answer
> 2 votes
## Python 2, 78 bytes

```
l=input();p=1
for _ in l:print reduce(lambda a,b:a*p+b,l)*p;p*=1j**(4./len(l))

```

The polynomial is evaluated for each power `p` of `1j**(4./len(l))`.

The expression `reduce(lambda a,b:a*p+b,l)` evaluates the polynomial given by `l` on the value `p` via Horner's method:

```
reduce(lambda a,b:a*10+b,[1,2,3,4,5])
=> 12345

```

Except, out input list is reversed, with constant term at the end. We could reverse it, but because `p**len(l)==1` for Fourier coefficients, we can use a hack of inverting `p` and multiplying the whole result by `p`.

Some equal-length attempts:

```
l=input();i=0
for _ in l:print reduce(lambda a,b:(a+b)*1j**i,l,0);i+=4./len(l)

l=input();i=0
for _ in l:print reduce(lambda a,b:a*1j**i+b,l+[0]);i+=4./len(l)

```

As a function for 1 byte more (79):

```
lambda l:[reduce(lambda a,b:a*1j**(i*4./len(l))+b,l+[0])for i in range(len(l))]

```

An attempt at recursion (80):

```
f=lambda l,i=0:l[i:]and[reduce(lambda a,b:(a+b)*1j**(i*4./len(l)),l,0)]+f(l,i+1)

```

Iteratively simulating `reduce` (80):

```
l=input();p=1;N=len(l)
exec"s=0\nfor x in l:s=s*p+x\nprint s*p;p*=1j**(4./N);"*N

```

# Answer
> 2 votes
# C (gcc), ~~86~~ 78 bytes

```
k;d(a,b,c)_Complex*a,*b;{for(k=c*c;k--;)b[k/c]+=a[k%c]/cpow(1i,k/c*k%c*4./c);}

```

Try it online!

This assumes the output vector is zeroed out before use.

# Answer
> 1 votes
# Python 2, 89 bytes

Uses the fact that `e^ipi = -1`.

The formula becomes `X_k = sum(x_n / ((-1)^(2nk/N)))`.

```
lambda a:[sum(a[x]/(-1+0j)**(x*y*2./len(a))for x in range(len(a)))for y in range(len(a))]

```

Ideone it!

# Answer
> 1 votes
# Mathematica, ~~49~~ ~~48~~ 47 bytes

```
Total[I^Array[4(+##-##-1)/n&,{n=Length@#,n}]#]&

```

Based on the formula from @Dennis' solution.

# Answer
> 1 votes
# Axiom, 81 bytes

```
g(x)==(#x<2=>x;[reduce(+,[x.j/%i^(4*k*(j-1)/#x)for j in 1..#x])for k in 0..#x-1])

```

using the formula someone post here. Results

```
(6) -> g([1,1,1,1])
   (6)  [4,0,0,0]
                                    Type: List Expression Complex Integer
(7) -> g([1,2,3,4])
   (7)  [10,- 2 + 2%i,- 2,- 2 - 2%i]
                                    Type: List Expression Complex Integer
(8) -> g([1,0,2,0,3,0,4,0])
   (8)  [10,- 2 + 2%i,- 2,- 2 - 2%i,10,- 2 + 2%i,- 2,- 2 - 2%i]
                                    Type: List Expression Complex Integer
(11) -> g([1,2,3,4,5])
   (11)
        5+--+4       5+--+3    5+--+2      5+--+
        \|%i   + 5%i \|%i   - 4\|%i   - 3%i\|%i  + 2
   [15, --------------------------------------------,
                           5+--+4
                           \|%i
    5+--+4       5+--+3    5+--+2      5+--+
    \|%i   + 3%i \|%i   - 5\|%i   - 2%i\|%i  + 4
    --------------------------------------------,
                       5+--+4
                       \|%i
    5+--+4       5+--+3    5+--+2      5+--+
    \|%i   + 4%i \|%i   - 2\|%i   - 5%i\|%i  + 3
    --------------------------------------------,
                       5+--+4
                       \|%i
    5+--+4       5+--+3    5+--+2      5+--+
    \|%i   + 2%i \|%i   - 3\|%i   - 4%i\|%i  + 5
    --------------------------------------------]
                       5+--+4
                       \|%i
                                    Type: List Expression Complex Integer
(12) -> g([1,2,3,4,5.])
   (12)
   [15.0, - 2.5 + 3.4409548011 779338455 %i, - 2.5 + 0.8122992405 822658154 %i,
    - 2.5 - 0.8122992405 822658154 %i, - 2.5 - 3.4409548011 779338455 %i]
                                      Type: List Expression Complex Float

```

# Answer
> 1 votes
# Octave, ~~43~~ 39 bytes

```
@(x)j.^(-4*(t=0:(s=rows(x))-1).*t'/s)*x

```

Try it online!

Multiplies the input vector by the DFT matrix.

# Answer
> 1 votes
# Raku, 40 bytes

```
{^$_ .map: ((1.roots($_)X**-*)Z*$_).sum}

```

Try it online!

* `$_` is the input list.
* `^$_` is the sequence of integers from zero to one less than the size of the list.
* `.map:` maps those indices over the following anonymous function, where the `*` which follows `X**-` assumes the value of each successive index.
* `1.roots($_)` returns the N complex roots of unity, where N is the size of the input list `$_`.
* `X** -*` cross-exponentiates those roots with the negative of the current index into the input list.
* `Z* $_` zips-with-multiplication those powers of the roots of unity with the input list.
* `.sum` sums the zipped list.

---
Tags: code-golf, math
---