# Question
Title: Count how many months are having a full 31 days by counting knuckles
How many of you that still use your own knuckle to determine whether a month is having a full 31 days or less?

You job is to write a program to count how many months, in a month range, are having a full 31 days and how many are having less than 31 days by "counting the knuckles".

*Courtesy: amsi.org.au*

---

## Input

A pair of months, the first of which doesn't have to come chronologically before the second, given in any suitable format. For instance: `201703 201902` — March 2017 to February 2019. Please describe the input format you choose. Note that the input must be able to include all years from 1 to 9999. The range of months specified includes both the starting and ending months.

## Output

Two integers: the number of months in the given range with 31 days and the number of months in the range with less than 31 days.

Example: `14 10` — 14 knuckles, 10 grooves (it means that in that month range we have 14 months that have a full 31 days, and 10 months that have less than 31 days).

For an input where the second month in the range comes chronologically before the first, for example `201612 201611`, you have to output a pair of zero.

## Examples of input and output

```
| Input         | Output      |
|---------------|-------------|
| 201703 201902 | 14 10       |
| 201701 202008 | 26 18       |
| 000101 999912 | 69993 49995 |
| 201802 201803 | 1 1         |
| 201601 201601 | 1 0         |
| 201612 201611 | 0 0         |

```

## Rules

* You may choose any language you like
* One input per line
* This is , so shortest code in bytes wins!
* The winner will be chosen in April 9
* Standard loopholes apply
* PS: this is my first question in PCG, it might have some inconsistencies. Feel free to edit and confirm what's unclear for you.

# Answer
# Jelly, 21 bytes

```
ḅ12r/ị7RḂṁ12¤żC$S×⁼Ṣ$

```

Takes input like `[[y, m], [y, m]]`.

Try it online!

### How it works

```
ḅ12r/ị7RḂṁ12¤żC$S×⁼Ṣ$  Main link. Argument: [[a, b], [c, d]]

ḅ12                    Unbase 12; yield [x, y] := [ 12a + b, 12c + d].
   r/                  Reduce by range; yield [x, ..., y].
           ¤           Combine the five links to the left into a niladic chain.
      7                  Set the return value to 7.
       R                 Range; yield [1, 2, 3, 4, 5, 6, 7].
        Ḃ                Bit; yield [1, 0, 1, 0, 1, 0, 1].
         ṁ12             Mold 12; repeat the Booleans to create an array of length
                         12. Yields [1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1].
     ị                 At-index; yield the elements of the array to the right at
                       the indices (1-based and modular) of the array to the left.
               $       Combine the two links to the left into a monadic chain.
              C          Complement; map t -> 1-t over the array.
             ż           Zip the original array with the complements.
                S      Take the sum of each column.
                    $  Combine the two links to the left into a monadic chain.
                  Ṣ      Sort [[a, b], [c, d]].
                   ⁼     Compare the result with [[a, b], [c, d]], yielding 1 if
                         the input is sorted, 0 if not.
                 ×     Multiply the results to both sides.

```
> 7 votes

# Answer
# Python 2, ~~92~~ ~~90~~ ~~86~~ 80 bytes

```
lambda a,b,c,d:[(bin(2741)[2:]*(c+1-a))[b-1:-12+d or None].count(x)for x in'10']

```

Try it online!

6 more by converting to a lambda, with thanks to @math\_junkie for the idea. Now outputs a list containing the two numbers.

Previous non-lambda version (86 bytes)

```
a,b,c,d=input()
for x in'10':print(bin(2741)[2:]*(c+1-a))[b-1:-12+d or None].count(x),

```

Try it online old!

2 saved with thanks to @ovs for helping me get rid of the `len(k)`. I hadn't thought about using `None`.

Input is a list of integers in the format `y1,m1,y2,m2`

Some credit due to @KeerthanaPrabhakaran who got `bin(2741)[2:]` before I did which saves 1 byte over hard coding the binary string.
> 5 votes

# Answer
## JavaScript (ES6), ~~70~~ ~~68~~ ~~67~~ 64 bytes

Takes input as two integers in `yyyymm` format, in currying syntax `(a)(b)`. Outputs an array of two integers `[knuckles, grooves]`.

```
a=>g=(b,c=d=0)=>a>b?[c,d-c]:g(--b,c+!((b%=100)>11||b/.87&!!++d))

```

### Formatted and commented

```
a =>                        // main function: takes start date (a) as input / returns g
  g = (                     // recursive function g, which takes:
        b,                  //   - b = end date
        c = d = 0           //   - c = number of knuckles
      ) =>                  // and also keeps track of: d = total number of months
    a > b ?                 // if a is greater than b:
      [ c, d - c ]          //   stop recursion and return the final result
    :                       // else:
      g(                    //   do a recursive call to g():
        --b,                //   - decrement the end date
        c +                 //   - increment the # of knuckles if
        !(                  //     both of these conditions are false:
          (b %= 100)        //     - the end month (now stored in b in 0-based indexing)
          > 11 ||           //       is greater than 11
          b / 0.87 & !!++d  //     - the number of days in this month is not 31
        )                   //       (at the same time, d is incremented if the first
      )                     //       condition is false)

```

### Test cases

**NB**: The third test case is not included in this snippet, because it won't work unless your browser has Tail Call Optimization enabled.

```
let f =

a=>g=(b,c=d=0)=>a>b?[c,d-c]:g(--b,c+!((b%=100)>11||b/.87&!!++d))

console.log(f(201703)(201902)); // 14 10
console.log(f(201701)(202008)); // 26 18
console.log(f(201802)(201803)); // 1 1
console.log(f(201601)(201601)); // 1 0
console.log(f(201612)(201611)); // 0 0
```
> 5 votes

# Answer
# PHP, ~~259~~ ~~256~~ ~~249~~ ~~248~~ ~~237~~ 221 bytes

Outgolfed by aross: https://codegolf.stackexchange.com/a/114512/38505

Input Format: `yyyymm,yyyymm`

```
$i=explode(",",fgets(STDIN));$_="DateTime::createFromFormat";foreach(new DatePeriod($_(Ym,$i[0]),new DateInterval(P1M),$_(Ym,$i[1])) as$f)date(t,mktime(0,0,0,$f->format(m),1,$f->format(y)))>30?++$x:++$y;
echo $x.' '.++$y;

```

Try it online!

---

### Older versions

```
$i=explode(",",fgets(STDIN));$_="DateTime::createFromFormat";$y=1;foreach(new DatePeriod($_("Ym",$i[0]),new DateInterval('P1M'),$_("Ym",$i[1])) as$f)date("t",mktime(0,0,0,$f->format("m"),1,$f->format("y")))==31?++$x:++$y;
echo $x.' '.$y;

```

Try it online!

```
$i=explode(",",fgets(STDIN));$_="DateTime::createFromFormat";$y=1;foreach(new DatePeriod($_(Ym,$i[0]),DateInterval::createFromDateString('1 month'),$_(Ym,$i[1])) as$f)date(t,mktime(0,0,0,$f->format(m),1,$f->format(y)))>30?++$x:++$y;
echo $x.' '.$y;

```

Try it online!

```
$i=explode(",",fgets(STDIN));$_="DateTime::createFromFormat";$y=1;foreach(new DatePeriod($_(Ym,$i[0]),DateInterval::createFromDateString('1 month'),$_(Ym,$i[1])) as$f)date(t,mktime(0,0,0,$f->format(m),1,$f->format(y)))==31?++$x:++$y;
echo $x.' '.$y;

```

Try it online!

```
$i=explode(",",fgets(STDIN));$_="DateTime::createFromFormat";foreach(new DatePeriod($_("Ym",$i[0]),DateInterval::createFromDateString('1 month'),$_("Ym",$i[1])) as$f)date("t",mktime(0,0,0,$f->format("m"),1,$f->format("y")))==31?++$x:++$y;
echo $x.' '.++$y;

```

Try it online!

```
$i=explode(",",fgets(STDIN));$_="DateTime::createFromFormat";$y=1;foreach(new DatePeriod($_("Ym",$i[0]),DateInterval::createFromDateString('1 month'),$_("Ym",$i[1])) as$f)date("t",mktime(0,0,0,$f->format("m"),1,$f->format("y")))==31?++$x:++$y;
echo $x.' '.$y;

```

Try it online!
> 4 votes

# Answer
# Python 3.5 (164 162 154 152 150 148 140 137 bytes)

```
n=int;a,b=input().split();t=k=0
for r in range(n(a[4:]),(n(b[:4])-n(a[:4]))*12+n(b[4:])+1):t+=1;k+=n('101010110101'[r%12-1])
print(k,t-k)

```

## repl.it

### takes input in the form of *yyyymm yyyymm*

### prints output as *number\_of\_knuckles number\_of\_grooves*

* **saved 2 bytes:** Thanks to Cole
* **saved 8 bytes:** removed unwanted variables
* **saved 2 bytes:** reduced t=0;k=0 as t=k=0
* **saved 2 bytes:** Thanks to Cole (I had missed this before)
* **saved 2 bytes:** Thanks to Keerthana
* **saved 8 bytes:** removed unwanted variables
* **saved 3 bytes:** Thanks to math\_junkie ( split(' ') to split() )
> 3 votes

# Answer
# Python 2, ~~147~~ ~~146~~ 142 bytes

```
def s(a,b):y=100;r=bin(2741)[2:];x=b/y-a/y;i=r*(x-1);return((0,0),map((i+r[a%y-1:]+r[:b%y]if i or x else r[a%y-1:b%y]).count,('1','0')))[a<=b]

```

Try it online!

* Saved 4 bytes - Thanks to @math\_junkie for suggesting the if-else clause with array lookup!

Breaking down the code,

```
def s(a,b):
 y=100
 r=bin(2741)[2:] #'101010110101'
 x=b/y-a/y #to get the difference between the two years
 i=r*(x-1)
 return((0,0),map((i+r[a%y-1:]+r[:b%y]if i or x else r[a%y-1:b%y]).count,('1','0')))[a<=b]

```
> 3 votes

# Answer
## Batch, 93 bytes

```
@set/ag=(y=%2/100-%1/100)*5+(x=%2%%100+6)*5/12-(w=%1%%100+5)*5/12,k=y*12+x-w-g
@echo %k% %g%

```

Accepts two parameters in ymm format (i.e. 101 - 999912). Previous 129-byte loop-based solution:

```
@set/al=%1-%1/100*88,u=%2-%2/100*88,k=g=0
@for /l %%i in (%l%,1,%u%)do @set/a"m=%%i%%12,k+=1451>>m&1,g+=2644>>m&1
@echo %k% %g%

```
> 3 votes

# Answer
# PHP, ~~120~~ ~~103~~ ~~97~~ 96 bytes

```
for($f=strtotime;$f($argv[2])>=$n=$f($argv[1].+$x++.month);)$k+=date(t,$n)>30;echo+$k,_,$x-1-$k;

```

Run like this:

```
php -nr 'for($f=strtotime;$f($argv[2])>=$n=$f($argv[1].+$x++.month);)$k+=date(t,$n)>30;echo+$k,_,$x-1-$k;' 0001-01 9999-12;echo
> 69993_49995

```

# Explanation

```
for(
  $f=strtotime;          # Alias strtotime function which is called twice.
  $f($argv[2]) >=        # Create end date timestamp. Iterate until the end
                         # date is reached.
  $n=$f(
    $argv[1].+$x++.month # Create timestamp from start date + X months.
  );
)
  $k+=date(t,$n) > 30;   # If "t" of current date (days in month) is 31
                         # increment $k (knuckles).

echo+$k,_,$x-1-$k;       # Compute grooves (iterations - $k) and output,
                         # implicit cast to int to account for 0 count.

```

# Tweaks

* Saved 17 bytes by using timestamp style instead of DateTime object style
* Saved 6 bytes by not assigning end date timestamp to variable `$e`, just compare directly
* Saved 1 byte by not keeping count of grooves, but just computing it after the loop
> 3 votes

# Answer
# PowerShell, 96 bytes

```
for($a,$b=[datetime[]]$args;$a-le$b;$a=$a.AddMonths(1)){$x++;$z+=$a.Month-in2,4,6,9,11};$x-$z;$z

```

Try it online!

Takes input as form `2017-03`. Uses the built-in .NET date libraries and loops through from inputs `$a` to `$b`, each iteration incrementing `$x++` and adding to `$z` if the current `.Month` is `-in` `2,4,6,9,11` (i.e., a non-31-day month). Then we output our total months minus the non-31-day months `$x-$z`, and the non-31-day months `$z`.

Tosses an error on the `0001-01` to `9999-12` test case, because .NET only supports years up to `9999`, so the final `.AddMonths(1)` causes an overflow. Still outputs the correct values, though, because it's a non-terminating error; it just causes the loop to exit.

Probably would be shorter to do this arithmetically, like the Python or JavaScript answers, but I wanted to show an approach using the .NET built-ins.
> 2 votes

# Answer
# Bash, 113 bytes

```
s="$1-1";e="$2-1";sort <(while [ "$s" \< "$e" ];do s=$(date +%F -d"$s+1month");date +%d -d"$s-1day";done)|uniq -c

```

Try it online!

needs golfing...

takes input as `2016-03` `2018-10`

outputs:

```
  1 28
  7 30
 12 31

```

ungolfed:

```
s="$1-1"
e="$2-1"                     # adds first day of month to the dates
sort <(
while [ "$s" \< "$e" ]; do   #iterates over dates
s=$(date +%F -d"$s+1month")  #adds one month to start date
date +%d -d"$s-1day"         #outputs last day of previous month
done) | uniq -c              #counts ocurrences of day number prevously sorted

```
> 2 votes

# Answer
# Swift, 151 bytes

```
let f={(m:[Int])->[Int] in var k=[0,0]
(m.min()!...m.max()!).map{$0%100}.filter{$0>0&&$0<13}.forEach{m in let n = m>7 ?m-7:m
k[(n%2+1)%2]+=1}
return k}

```

input is an array of two integers in the format as per the example
> 1 votes

---
Tags: code-golf, date, counting
---


title: How much time is remaining?

text:
# Question
Title: How much time is remaining?
# The Program

You are given two strings, **A** and **B**. **A** is the current position at which your timer is at, and **B** is the position at which your timer will stop. Both strings are in the format **m:ss**. You must write a program that determines the amount of time left which should also be formatted as **m:ss** or **mm:ss**.

# Example

```
0:00 0:01 -> 0:01
0:55 1:00 -> 0:05
1:45 3:15 -> 1:30

```

# Answer
> 91 votes
# Excel, 6 Bytes

```
=B1-A1

```

Assuming A is in cell `A1` and B is in cell `B1`

# Answer
> 15 votes
# MATL, ~~17~~ 7 bytes

```
YOd15XO

```

Input is a cell array of strings, in the form `{'1:45' '3:15'}` or `{'1:45', '3:15'}`.

Try it online!

### Explanation

```
YO     % Input cell array of strings (implicit). Convert to serial date numbers
d      % Difference
15XO   % Convert to format 15, i.e. 'HH:MM'. Display (implicit)

```

# Answer
> 8 votes
## Bash \+ coreutils, ~~44~~  39 bytes

```
tr : \ |dc -e?r60*+r-r60*-60~rn58PA~rnn

```

**Try it online!**

**Explanation:** using "1:45 3:15" as test case (last example). I show intermediary steps in quotes.

```
tr : \ |         # replace colons with spaces: "1 45 3 15"
dc -e?           # start dc script, push input to LIFO stack: "15 3 45 1"
     r60*+            # turn time B to total seconds: "195 45 1"
     r-r60*-          # turn time A to total seconds and get difference: "90"
     60~r             # turn difference (time left) to minutes and seconds: "1 30"
     n58P             # pop and print minutes, print colon (ASCII code 58): "30"
     A~rnn            # print seconds. Padding with zeroes is done by dividing by
                      #10 (A), and printing the quotient and the remainder.

```

Note that I don't check if the minute value needs zero padding, because the OP stated that the maximum value for `m` is 9.

---

Below is my original 44 bytes answer, that used the `date` command to turn the total time left in seconds to the `m:ss` format.

```
date -d@`tr : \ |dc -e?r60*+r-r60*-p` +%M:%S

```

# Answer
> 6 votes
# Python 2, ~~90~~ ~~87~~ ~~83~~ 80 bytes

Takes input like `"2:45","5:01"`.

```
a,b=[60*int(s[-5:-3])+int(s[-2:])for s in input()]
print'%d:%02d'%divmod(b-a,60)

```

**Try it online**

# Answer
> 5 votes
# C, ~~112~~ 100 bytes

*Thanks to @betseg for saving 11 bytes and thanks to @Johan du Toit for saving one byte!*

```
i,j;f(char*a,char*b){i=atoi(b)-atoi(a);j=atoi(b+2)-atoi(a+2);j<0?i--,j+=60:0;printf("%d:%02d",i,j);}

```

Try it online!

# Answer
> 5 votes
# c, 86

```
f(a,b,c,d){scanf("%d:%d%d:%d",&a,&b,&c,&d);d+=(c-a)*60-b;printf("%d:%02d",d/60,d%60);}

```

Reads space-separated times from STDIN.

Try it online.

# Answer
> 5 votes
## Batch, 74 bytes

```
@set t=%2-(%1)
@set/as=%t::=*60+1%,m=s/60,t=s/10%%6
@echo %m%:%t%%s:~-1%

```

Replacing the `:` in the time with `*60+1` converts it into an expression that calculates the number of seconds. Batch interprets leading zeros as octal so I prepend a `1` to the seconds to ensure decimal conversion; fortunately the two `1`s cancel out.

# Answer
> 5 votes
# MySQL, ~~13~~ 22 bytes

```
select right(timediff(B,A),5)

```

expects the times in `A` and `B`.

# Answer
> 4 votes
# ECMAScript 6, 99 91 85 bytes

## Single Line:

```
f=s=>s.split`:`.reduce((a,e,i)=>a+e*(!i?60:1),0);t=n=>~~(n/60)+":"+n%60;t(f(b)-f(a));

```

## Slightly formatted:

```
f=s=>s.split`:`.reduce((a,e,i)=>a+e*(!i?60:1),0);
t=n=>~~(n/60)+":"+n%60;
t(f(b)-f(a));

```

I feel there could be some some savings in there.. but I am not seeing them at present.

Edit - excellent suggestions in the comments.

# Answer
> 4 votes
# Bash + GNU utilities, 43

```
date -d@`date -f- +%s|dc -e??r-60/p` +%M:%S

```

Try it online.

### Explanation

```
         date -f- +%s                        # read in 2 line-delimited dates and output as number of seconds since the epoch
                     |dc -e                  # pipe to dc expression:
                           ??                # - read 2 input numbers
                             r-              # - reverse and subtract
                               60/           # - divide by 60
                                  p          # - output
        `                          `         # evaluate date|dc command
date -d@                             +%M:%S  # format seconds difference and output

```

Note the `dc` expression divides by 60, because `date` reads the input as H:MM instead of M:SS.

# Answer
> 4 votes
# PHP, ~~55~~ 53 bytes

```
<?=date('i:s',($s=strtotime)($argv[2])-$s($argv[1]));

```

takes input from command line arguments

# Answer
> 4 votes
# Rebol, 5 bytes

```
b - a

```

Assuming I didn't miss any rules..

Rebol has arithmetic built-in for a number of literal data types. This also applies to its descendants such as Red

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

```
using System;a=>b=>((DateTime.Parse(b)-DateTime.Parse(a))+"").Remove(5);

```

Takes input as strings. `b="3:15"` `a="1:45"`.

### Explanation:

Because `DateTime.Parse()` returns a Date in `hh:mm:ss` format, I am able to parse the result into a string using `+""`, then trim the trailing `:00`.

This works with `hh:mm` because there are both 60 seconds in a minute and 60 minutes in an hour.

`0:01` `0:00` returns `0:01`

`1:00` `0:55` returns `0:05`

`3:15` `1:45` returns `1:30`

# Answer
> 2 votes
# Haskell, ~~98~~ ~~127~~ 86 Bytes

```
r(m:_:s)=60*read[m]+read s
a#b|(d,m)<-divMod(r b-r a)60=show d++':':['0'|m<=9]++show m

```

Try it online!

But I wonder if there are some library functions for this

EDIT: Removed import, also fixed an error where it showed m:s instead of m:ss

Also, well-formatted version:

```
convert :: String -> Integer
convert (a:_:b) = (read [a])*60+(read b)

diffTime :: String -> String -> String
diffTime s1 s2 = let (d,m) = divMod (c b-c a) 60 in show d ++ ":" ++ pad2d m

pad2d :: Int -> String
pad2d n = ['0'|n<=9]++show n

```

EDIT2: Golfed off (30?) bytes thanks to Laikoni! Also golfed some other misc. bytes.

# Answer
> 2 votes
# Pyth, ~~47~~ ~~45~~ ~~44~~ 40 Bytes

```
J.U-Zbm+*60hdedmmvkcd\:.z%"%d:%02d".DJ60

```

Takes the input separated by newlines.

Pyth had no time built-ins useful for this. I tried some fancy eval() stuff but apparantly Pyth can't eval stuff with `*` or any leading zeroes whatsoever. This got much longer than i hoped. Quite some bytes are spent on adding a leading zero to the output. At least I'm shorter than bash. Will add explanation if asked.

Try this!

### alternative solution, 48 Bytes

```
J.U-Zbm+*60hdh_dmmvkcd\:.z
K%J60
s[/J60\:*<KT\0K

```

# Answer
> 2 votes
# T-SQL, 238 bytes

```
CREATE PROCEDURE d @a time,@b time AS BEGIN DECLARE @d int DECLARE @s varchar(2) SET @d=datediff(s,@a,@b);SET @s=CAST(@d%3600/60 AS VARCHAR(3)) SELECT CAST(@d/3600 AS VARCHAR(3))+':'+(SELECT CASE WHEN LEN(@s)=1 THEN '0'+@s ELSE @s END)END

```

Usage:

```
EXEC d '00:55','01:00'

```

Seeing the PostGres example earlier I realised I hadn't seen many golfing attempts in SQL so I had a go at it in T-SQL. Now I know *why* you don't see much golfing in SQL :D

# Answer
> 2 votes
# CJam, ~~34~~ ~~33~~ 25 bytes

*Saved 8 bytes thanks to Martin Ender!*

```
{r':/60b}2*\m60mds2Te[':\

```

Try it online!

**Explanation**

```
{             e# Start of block
 r            e#  Read one time from input
 ':/          e#  Split on colons, gives [minutes seconds]
 60b          e#  Convert from base 60
}2*           e# Run this block 2 times
              e# At this point, we have the two times in seconds on the stack
\             e# Swap top elements
m             e# Subtract
60md          e# Divmod the result by 60, to convert back to minutes and seconds
s             e# Convert the seconds to a string
2Te[          e# Pad it to 2 characters by adding 0s to the left (T = 0)
':            e# Push a colon character
\             e# Swap top elements, bringing seconds back to the top

```

# Answer
> 2 votes
# Python, 160 bytes

I am still new to code golf so if anyone has any suggestions, I would appreciate it.

```
a, b = input()
def z(x):
    x = x.split(":")
    return int(x[0])*60+int(x[1])
a, b = z(a),z(b)
s, m = b-a,0
while s >= 60:
    s -= 60
    m += 1
print(str(m)+":"+str(s))

```

# Answer
> 2 votes
## T-SQL, 82 Bytes

```
select left(cast(dateadd(minute, datediff(S,'0:00','0:01')/60,114) as time(0)), 5)

```

# Answer
> 1 votes
## REXX, 79 bytes

```
arg t q
say right(time(,f(q)-f(t),s),5)
f:return time(s,'00:'right(arg(1),5,0))

```

# Answer
> 1 votes
# Pyth, 28

```
%"%d:%02d".Dh.+misMcd\:60Q60

```

Try it.

### Explanation

```
                   cd\:      # lambda to split c on ":"
                 sM          # map to convert string to int
               mi      60Q   # convert from base-60 list to give seconds
             .+              # delta of the two seconds values
            h                # single-item list to int
          .D              60 # divmod by 60
%"%d:%02d"                   # format output

```

# Answer
> 1 votes
# TXR Lisp, 101 bytes

```
$ txr -e '(awk (:let (s "%M:%S"))
               ((mf (time-parse s))
                (prn (time-string-local (- [f 1].(time-utc) [f 0].(time-utc)) s))))'
13:49 14:49
01:00
0:13 1:47
01:34
5:01 5:59
00:58
6:00 6:00
00:00
6:00 5:00
59:00

```

Condensed: `(awk(:let(s"%M:%S"))((mf(time-parse s))(prn(time-string-local(-[f 1].(time-utc)[f 0].(time-utc))s))))`

# Answer
> 1 votes
# Java 7, 164 bytes

```
String c(String a,String b){long s=x(b,1)-x(a,1)+(x(b,0)-x(a,0))*60,m=s%60;return(s/60)+":"+(m>9?m:"0"+m);}long x(String s,int i){return new Long(s.split(":")[i]);}

```

**Explanation:**

```
String c(String a, String b){       // Method with two String parameters and String return-type
  long s = x(b,1) - x(a,1)          //  Get difference in seconds from input times
           + (x(b,0) - x(a,0)*60,   //   plus the difference in minutes times 60 to get the seconds
    m = s%60;                       //  Temp variable of seconds after we've subtracted the minutes (used multiple times)
  return (s/60)                     //  Return minutes
    +":"                            //   plus ":"
    +(m>9?m:"0"+m);                 //   plus seconds (with a leading 0 if necessary)
}                                   // End of method

long x(String s,int i){             // Separate ethod with String and Integer parameters and long return-type
  return new Long(s.split(":")[i];  //  Return either minutes or seconds of String parameter based on the index
}                                   // End of method

```

**Test code:**

Try it here.

```
class M{
  String c(String a,String b){long s=x(b,1)-x(a,1)+(x(b,0)-x(a,0))*60,m=s%60;return(s/60)+":"+(m>9?m:"0"+m);}long x(String s,int i){return new Long(s.split(":")[i]);}

  public static void main(String[] a){
    M m = new M();
    System.out.println(m.c("0:00", "0:01"));
    System.out.println(m.c("0:55", "1:00"));
    System.out.println(m.c("1:45", "3:15"));
  }
}

```

**Output:**

```
0:01
0:05
1:30

```

# Answer
> 1 votes
# Ruby, 91 bytes

```
require'time';t=Time;d=t.parse($*[1])-t.parse($*[0]);puts t.at(d.to_i).utc.strftime '%H:%M'

```

Try it online!

Takes input from command line arguments.

### Invocation:

```
ruby outatime.rb $A $B

```

### Example:

```
ruby outatime.rb 1:45 3:15

```

Output:

> 01:30

# Answer
> 1 votes
## PowerShell 47 Bytes

```
param($s,[timespan]$f)($f-$s).ToString("h\:mm")

```

Simple timespan math and coverting to hour and seconds string.

# Answer
> 0 votes
# JavaScript, 88 bytes

```
a=>b=>{c=a.split`:`,d=b.split`:`;return +c[0]-d[0]-d[1]>c[1]?1:0+":"+(+c[1]+60-d[1])%60}

```

Try it online!

## Explanation:

Splits the inputs on the colon

```
c=a.split`:`,d=b.split`:`;

```

Converts string to int

```
+c[0]

```

Gets the minute value

```
+c[0]-d[0]-d[1]>c[1]?1:0

```

Gets the second value

```
(+c[1]+60-d[1])%60

```

Returns the string minutes:seconds

```
return +c[0]-d[0]-d[1]>c[1]?1:0+":"+(+c[1]+60-d[1])%60

```

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


# Question
Title: March Madness - When Will Two Seeds Meet?
Each March in the United States, the NCAA holds a 68-team tournament for both men's and women's college basketball. Here's what the bracket looks like:

There are four regions, each with 16 teams seeded from 1-16.

Each region is seeded the same way, and across the four regions, the same matchups occur between seeds. For example, in the first round, #1 plays #16 and #8 plays #9, then the winners of those games play in the second round. So, possible options for the second round matchup are #1 vs #8, #1 vs #9, #16 vs #8, and #16 vs #9.

Teams with the same seed can only meet in two ways: the first is in the semifinals (round 5), where the champion of each of the four regions plays another regional champion.

The second has to do with a wrinkle in the tournament. There are also 4 "play-in" games, where two teams with the same seed play each other to enter the "true" game in the round of 64 teams. As you can see in the bracket, this only happens for seeds 11 and 16, so those seeds can play another team in the same seed in the play-in games (round 0).

**The Challenge**

Given two seeds from 1 to 16, inclusive, in any standard format, output the number of the earliest round a matchup between two teams with those integers as seeds could occur in the NCAA basketball tournament.

**Test Cases**

```
Input  Output
1,16   1
1,8    2
1,9    2
9,16   2
3,11   2
3,14   1
1,2    4
5,5    5
11,11  0
16,16  0
15,16  4
3,4    4
6,7    3
6,10   3
6,11   1
10,11  3
1,6    4
1,11   4
4,5    2
4,6    4
4,7    4
4,8    3
4,9    3
5,8    3
5,9    3
2,7    2

```

This is code-golf, so the submission with the fewest bytes wins.

# Answer
# Mathematica, 79 bytes

```
o={r=1,1}
Which[#==11o||#==16o,0,Tr@#==(c=32/2^r+1),r,0<r++,#0[Min[#,c-#]&/@#]]&

```

The second line defines a pure function taking a pair of numbers as input and returning the appropriate nonnegative integer. Inside the `Which` (which is an "if-then-else" construct): `#==11o||#==16o,0,` deals with the play-in special cases; `Tr@#==(c=32/2^r+1),r,` checks whether the sum of the two team seeds is equal to the magic number that means they could be matched up in round `r`; and `0<r++,#0[Min[#,c-#]&/@#]` is the "else" clause (since `0<r++` will always be true here) which recursively calls the function on `Min[#,c-#]&/@#`, which replaces any lower seed with the seed of the higher-ranked team it would have beaten to get to the next round.
> 1 votes

---
Tags: code-golf
---


title: No Singles Allowed

text:
# Question
Title: No Singles Allowed
This is a fairly simple challenge.

Write a program that computes the distance between two points on a 2D plane. However, you can't use any functions or operators (referred to here as symbols) that are 1 character long.

**Examples:**

* `-=`, `+=`, `*=`, `/=`, `%=`, etc. are allowed.
* `||`, `&&`, `--`, `++` are allowed as well.
* `+`, `-`, `/`, `*` are not allowed.
* `f(x)` is not allowed, but `fn(x)` is.
* `S 5 4` is not allowed, but `SUM 5 4` is.
* `if(lol==lel)` is allowed.
* Simply putting two separate single-character operators one after the other is not allowed, eg. `!!(true)` isn't allowed.

**Exceptions:**

* Single semicolons or the equivalent are allowed, e.g. `foo();`, as long as they are being used as an end-of-command symbol.
* Commas (`,`) and periods (`.`) are allowed.
* Parentheses (`()`) and other symbols that are used in such a way to require a second match are allowed. Examples:
    + `foo();` is allowed, as is `foo(x);`.
    + `[5,6]` is allowed.
    + `"strings"` are allowed.
    + `for(i+=5;;i++){}` is allowed
    + `if(1<2 && 2>3)` is not allowed, as the symbols are being interpreted as greater than and less than symbols, and so do not require the other.
    + `([{<>}])` is allowed.
    + `][` is not allowed, as the symbols do not match.
    + Essentially, the interpreter/compiler/etc.(?) should recognize the symbols as matching.

**Specifications:**

* Whitespace does not count for the single character rule, e.g. `this == that` and `this ==that` etc. are both allowed.
* Standard rules for loopholes etc. apply.
* Input can be in any reasonable format of two points. Examples:
    + `[{x:0,y:0},{x:9,y:786}]`*
    + `[[5,4],[6,8]]`
    + `"54,37,68,9760"`
    + `new Point(0,0), new Point(5,6)`
    + `["34,56","23,98657"]`
    + etc.
* Output should be a double or equivalent with 5 significant digits.
* **No eval!**
* This is code-golf, so shortest allowed and functioning code wins!

\*You would have to construct the objects a different way, as colons are single symbols.

Good luck without being able to use the `=` operator! :P

**Edit:** Imaginary 5 kudo points for not using a built-in.

# Answer
> 3 votes
# Python 2, 35 bytes

```
print abs(input().__sub__(input()))

```

Example input for points (5,4) and (6,8):

```
5+4j
6+8j
4.12310562562

```

or:

```
complex(5,4)
complex(6,8)
4.12310562562

```

Try it online!

# Answer
> 2 votes
# Mathematica, 17 bytes

```
EuclideanDistance

```

A function invoked like `EuclideanDistance[{5,4}, {6,8}]`. Works in other dimensions as well.

Mathematica and its long command names thank you for your support.

# Answer
> 1 votes
## JavaScript, 10 bytes

```
Math.hypot

```

Returns a function that does the job. For 13 bytes, I can do it using only paired puncutation:

```
Math['hypot']

```

# Answer
> 0 votes
# R, 33 bytes

```
cd<-function(a,b)dist(rbind(a,b))

```

Try it online!

# R, 26 bytes

```
dist(rbind(scan(),scan()))

```

# Answer
> 0 votes
# Octave, 20 bytes

```
abs(diff(input('')))

```

Takes input on the form: `[5+4j, 6+8j]`.

Anonymous functions can't be used since `@` is a single character. It takes a vector with two complex numbers as input, calculated the difference, and takes the absolute value.

---
Tags: code-golf, math, restricted-source, geometry
---


title: Match this random string

text:
# Question
Title: Match this random string
**To-Do: Come up with a Better Title**

---

### Specification:

This challenge is similar to , but with a twist. You goal is to output a finite string that resembles the following string of psuedo-random characters as closely as possible:

```
BABBBBAAABBAABBBBAABBBAABBBABBAABABABBBBABBBBBBAABABBAABABBBABBBABAAAAABAAAABBAAABAAABBBBAABBABBBAABBBAABAAAABAAAABABABBBBBAABAAABBABAABAABABABBAABAAABBBABBABABBABAABABABBAABBBAABABABBBABAAABAABBBBBAABBBABABAABAABBAABABBBAABBAABAAABABABBBBBAAAAABBBAAABABAABBAABAABAAAABABBBAABBABBBBBAABAAAAABABBBAAAAAABAAAABBABAABABBAAABBBBBBAABABBAAAAAABABBAAABBABBABBBBAAAAAABABBBBBABBBABBAABBABAABAAAAABBAABABBABAABABABBBAAAAAABBBBBABABBBBBAABAABBBAAABABBABBAAABBABBABABBAABBAABAABBBABBABABBABABABABABBBAAABBBBBBABAAAAAABBAABBAABBBAAAAAAABBBBABBBBAABAABAABBABBAAAAAABABBABAAAAABABABAABAABBBAABBABAAABABAAAAABAABABAABBABAABBABBABAABABBBBAAAAAABAAAAAAAAABAABAAAAAAAABABAABBBABAAABABBBBBAAABAAAABBBBBABBBAAAAABBBABBAAAABAABBBBAABBABABAAABAABAAAAABBABBBABBBBAABBABABBAABAAAABAABBABABBBAABABABABAABAAAAABBABBBABBABBAAABAAAABBABABBBABBABABBBBABAAABBBBAAAABBABAAABABBBBBABABBAABBABAAABBABAAAAAABBBAAAABBBAAABABAAAAABBBBABAAABBBAAAABABBBBAAAAABBBBAABAABABBABABBABAAAABBBBAAABAABAAABBBBBBABBABAABABAABBBBBBBBAABBBAABAABABAABBAAABABAABAABBBBBBABBA

```

The string is 1024 characters long, and consists only of uppercase `A` and `B` characters. You must write a program takes up less than or equal to 256 bytes. The above string was generated completely randomly.

This challenge is **not** code-golf! Since 256 bytes is far too few characters (even for golfing languages), you may output any finite string. Your score is Levenshtein Distance between the 1024 byte string, and the string your program outputs (where the lower score is the best.)

---

### Examples:

```
Input, Output
1024 "A" characters, 500 Points
1024 "B" characters, 524 Points
1024 characters alternating between "A" and "B" ("A" first), 348 Points
1024 characters alternating between "A" and "B" ("B" first), 346 Points

```

---

### Notes:

* The output must be finite and deterministic.
* Unfortunately, this challenge is limited to languages that can be scored in bytes.
* You may not substitute `A` and `B` for other characters. If your language cannot output such characters, it may not compete.
* If a language cannot compete, it is still welcome to post non-competing answers. Just make sure to explain how you are scoring the challenge.
* The winner of this challenge is on a **per-language basis**, since would be unlikely that an answer from Brainf\*** would ever beat one from Jelly.

# Answer
# PHP, 246 printable bytes, distance 0

```
while($c=ord(base64_decode("vGec7K9+WXdBDEebnIQr5GkrI7WlZyuifOpMuZFfBxTJC5vkFwIaWPywLG3gX3ZpBlpXA+vk4tjazJ2tVcfoGZwHvJNgWgqTmiglNNpeBAEgFOi+IfcHYTzUSDd5rITXKpBu2Ia7Xo8NF9Zo0DhxQejheDyWtDxI/aU/zkpik/Y")[$i++]))echo strtr(sprintf("%08b",$c),10,BA);

```

or

```
while($c=base64_decode("vGec7K9+WXdBDEebnIQr5GkrI7WlZyuifOpMuZFfBxTJC5vkFwIaWPywLG3gX3ZpBlpXA+vk4tjazJ2tVcfoGZwHvJNgWgqTmiglNNpeBAEgFOi+IfcHYTzUSDd5rITXKpBu2Ia7Xo8NF9Zo0DhxQejheDyWtDxI/aU/zkpik/Y")[$i++])echo strtr(sprintf("%08b",ord($c)),10,BA);

```

Remarkable: gnuzip fails on the binary string. `gzcompress` adds 11 bytes and `gzdeflate` adds 5.

The fact that no `0x00` byte is in there saves 2 bytes on the first version;
no `0x30` saves 2 bytes on the second one.
> 3 votes

# Answer
# Pyth, distance 0

```
."AB¼gì¯~YwAG+äi+#µ¥g+¢|êL¹_ÉäXü°,mà_viZWëäâØÚÌUÇè¼`Z
(%4Ú^ è¾!÷a<ÔH7y¬×*nØ»^
ÖhÐ8qAèáx<´<Hý¥?ÎJbö"

```

The code is 135 Bytes long
> 2 votes

# Answer
# JavaScript (ES6), distance 0

```
alert("¼gì¯~YwAG+äi+#µ¥g+¢|êL¹_ÉäXü°,mà_viZWëäâØÚÌUÇè¼`Z\n(%4Ú^ è¾!÷a<ÔH7y¬×*nØ»^\rÖhÐ8qAèáx<´<Hý¥?ÎJbö".replace(/[^]/g,c=>("0000000"+c.charCodeAt().toString(2)).slice(-8).replace(/./g,x=>"AB"[x])))

```

Contains lots of unprintables, so get the real code from this pastebin. The code is 232 bytes long.
> 2 votes

# Answer
# brainfuck, distance 283, 45 bytes

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

```

Try it online!

# brainfuck, distance 0 (non-competing)

Non-competing due to length (1548).

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

```

Try it online
> 2 votes

# Answer
# Bubblegum, distance 0

The code is 187 bytes long:

```
00000000: 6591 8911 c340 0c02 6b83 fe7b ca63 8915  e....@..k..{.c..
00000010: 33ce 1f90 11b7 b66c 5b92 adfd 998f 91b4  3......l[.......
00000020: 13f6 b8c8 deb7 24cd e7e4 e872 5479 4c4d  ......$....rTyLM
00000030: 22e2 44b0 8900 7905 2c92 6ef1 68b1 48a2  ".D...y.,.n.h.H.
00000040: 2081 b554 9b23 df2c cde8 4d3f e43e 261c   ..T.#.,..M?.>&.
00000050: 0a0b 3331 1274 32cc 7c29 0a7b 14f6 6d7a  ..31.t2.|).{..mz
00000060: f3ba eab5 063c 8ca0 f1ec b284 0baa 51a8  .....<........Q.
00000070: 0cc9 ee7f 40f0 ade8 b821 cb27 bc1a a318  ....@....!.'....
00000080: e637 e50b 17cc 6db8 c070 3b50 c29d 08eb  .7....m..p;P....
00000090: b3e3 9d10 e0af cbe0 1b0d 5530 cc81 ba32  ..........U0...2
000000a0: 8b22 829b e186 d559 22e3 ac90 2bfc 60a1  .".....Y"...+.`.
000000b0: 4333 8ec2 8d3d 19c4 7dd5 17              C3...=..}..

```

Try it online.
> 1 votes

---
Tags: string, code-challenge, kolmogorov-complexity
---


title: Oddly Even, Positively Negative

text:
# Question
Title: Oddly Even, Positively Negative
Given N, output the Nth term of this infinite sequence:

```
-1 2 -2 1 -3 4 -4 3 -5 6 -6 5 -7 8 -8 7 -9 10 -10 9 -11 12 -12 11 ... etc.

```

N may be 0-indexed or 1-indexed as you desire.

For example, if 0-indexed then inputs `0`, `1`, `2`, `3`, `4` should produce respective outputs `-1`, `2`, `-2`, `1`, `-3`.

If 1-indexed then inputs `1`, `2`, `3`, `4`, `5` should produce respective outputs `-1`, `2`, `-2`, `1`, `-3`.

To be clear, this sequence is generated by taking the sequence of positive integers repeated twice

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

```

and rearranging each pair of odd numbers to surround the even numbers just above it

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

```

and finally negating every other term, starting with the first

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

```

**The shortest code in bytes wins.**

# Answer
# Python 2, 23 bytes

```
lambda n:~n/2+n%2*(n|2)

```

Odd inputs give roughly `n/2`, even ones roughly `-n/2`. So, I started with `-n/2+n%2*n` and tweaked from there.

Try it online!
> 32 votes

# Answer
# Mathematica, 29 bytes

```
((#~GCD~4/. 4->-2)+#)/2(-1)^#&

```

Pure function taking a 1-indexed input. Other than the alternating signs `(-1)^#`, twice the sequence is close to the input, the differences being 1, 2, 1, -2 cyclically. It's nice that `#~GCD~4`, the greatest common divisor of the input and `4`, is 1, 2, 1, 4 cyclically; so we just manually replace `4->-2` and call it a day. I like this approach because it avoids most of the many-character Mathematica commands.
> 17 votes

# Answer
# Pip, ~~24~~ 22 bytes

```
v**a*YaBA2|1+:--a//4*2

```

Takes input, 1-indexed, as a command-line argument. Try it online or verify 1-20.

### Explanation

Observe that the sequence can be obtained by combining three other sequences, one zero-indexed and the others one-indexed:

* Start with `0 0 0 0 2 2 2 2 4 4 4 4` = `a//4*2` (0-indexed);
* Add `1 2 2 1 1 2 2 1 1 2 2 1` = `aBA2|1`, where `BA` is bitwise AND, and `|` is logical OR (1-indexed);
* Multiply the sum by `-1 1 -1 1 -1 1 -1 1 -1 1 -1 1` = `(-1)**a` (1-indexed).

If we start with `a` 1-indexed, we can compute the 1-indexed parts first (reading the expression left to right) and then decrement `a` for the 0-indexed part. Using the builtin variable `v=-1`, we get

```
v**a*((aBA2|1)+--a//4*2)

```

To shave two more bytes, we have to use some precedence-manipulation tricks. We can eliminate the inner parentheses by replacing `+` with `+:` (equivalent to `+=` in a lot of languages). Any compute-and-assign operator is of very low precedence, so `aBA2|1+:--a//4*2` is equivalent to `(aBA2|1)+:(--a//4*2)`. Pip will emit a warning about assigning to something that isn't a variable, but only if we have warnings enabled.

The only thing that's lower precedence than `:` is `Y`, the yank operator.\* It assigns its operand's value to the `y` variable and passes it through unchanged; so we can eliminate the outer parentheses as well by yanking the value rather than parenthesizing it: `YaBA2|1+:--a//4*2`.

<sub>* `P`rint and `O`utput have the same precedence as `Y`ank, but aren't useful here.</sub>
> 9 votes

# Answer
# Java 8, 19 bytes

```
n->~(n/2)+n%2*(n|2)

```

# Java 7, ~~47~~ 37 bytes

```
int c(int n){return~(n/2)+n%2*(n|2);}

```

First time Java (8) actually competes and is shorter than some other answers. Still can't beat the actual golfing languages like Jelly and alike, though (duhuh.. what a suprise.. \>.\> ;P)

0-indexed
Port from *@Xnor*'s Python 2 answer.
-10 bytes thanks to *@G.B.*

Try it here.
> 9 votes

# Answer
# Jelly, ~~8~~ 7 bytes

```
H^Ḃ~N⁸¡

```

This uses the algorithm from my Python answer, which was improved significantly by @GB.

Try it online!

### How it works

```
H^Ḃ~N⁸¡  Main link. Argument: n

H        Halve; yield n/2. This returns a float, but ^ will cast it to int.
  Ḃ      Bit; yield n%2.
 ^       Apply bitwise XOR to both results.
   ~     Take the bitwise NOT.
    N⁸¡  Negate the result n times.

```
> 9 votes

# Answer
# Jelly, ~~15~~ ~~12~~ 11 bytes

```
Ḷ^1‘ż@N€Fị@

```

Try it online!

### How it works

```
Ḷ^1‘ż@N€Fị@  Main link. Argument: n

Ḷ            Unlength; yield [0, 1, 2, 3, ..., n-1].
 ^1          Bitwise XOR 1; yield [1, 0, 3, 2, ..., n-1^1].
   ‘         Increment; yield [2, 1, 4, 3, ..., (n-1^1)+1].
      N€     Negate each; yield [-1, -2, -3, -4, ..., -n].
    ż@       Zip with swapped arguments;
             yield [[-1, 2], [-2, 1], [-3, 4], [-4, 3], ..., [-n, (n-1^1)+1]].
        F    Flatten, yield [-1, 2, -2, 1, -3, 4, -4, 3, ..., -n, (n-1^1)+1].
         ị@  At-index with swapped arguments; select the item at index n.

```
> 8 votes

# Answer
# RProgN 2, ~~31~~ ~~25~~ 22 bytes

```
nx=x2÷1x4%{+$-1x^*}#-?

```

## Explained

```
nx=                         # Convert the input to a number, set x to it.
   x2÷                      # Floor divide x by 2.
      1                     # Place a 1 on the stack.
       x4%{       }#-?      # If x%4 is 0, subtract 1 from x//2, otherwise...
           +                # Add the 1 and the x together.
            $-1             # Push -1
               x^           # To the power of x.
                 *          # Multiply x//2+1 by -1^x. (Invert if odd, do nothing if even)

```

Try it online!
> 6 votes

# Answer
# Ruby, ~~26 23~~ 18 bytes

```
->n{~n/2+n%2*n|=2}

```

0-based

-3 bytes stealing the -1^n idea from Greg Martin, Dennis and maybe somebody else, then -5 bytes stealing the n|2 idea from xnor.
> 6 votes

# Answer
# Stacked, ~~30~~ 28 bytes

```
:2%([:2/\4%2=tmo+][1+2/_])\#

```

Try it online! Returns a function, which as allowed per meta consensus.. Takes input from the top of the stack.

Using the same approach as the RProgN 2 answer.

---

Alternatively, 46 bytes. Try it online!:

```
{!()1[::1+,:rev,\srev\,\2+]n*@.n 1-#n 2%tmo*_}

```

This one generates the range then selects and negates the member as appropriate.
> 5 votes

# Answer
# Python 2,  ~~44~~  ~~33~~ 27 bytes

```
lambda n:(-1)**n*~(n/2^n%2)

```

*Thanks to @GB for golfing off 6 bytes!*

Try it online!
> 5 votes

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

```
|2×Ḃ+H~$

```

Try it online!

*-1 thanks to Dennis. Duh float conversions.*

Uses @xnor's Python 2 approach.

**EDIT**: \>\_\>
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
2‰`^±¹F(

```

**Try it online**

**Explanation**

```
2‰          divmod by 2
  `         flatten list
   ^        XOR
    ±       NOT
     ¹F(    Push 1st argument, loop N times, negate

```
> 4 votes

# Answer
## CJam, 16 bytes

```
{_(_1&)^2/)W@#*}

```

1-based input.

Try it online!

### Explanation

Here is a breakdown of the code with the values on the stack for each input from `1` to `4`. The first few commands only affect the two least significant bits of `n-1` so after `4`, this stuff just repeats cyclically, with the results incremented by 2, due to the halving.

```
Cmd             Stack: [1]       [2]       [3]       [4]
_    Duplicate.        [1 1]     [2 2]     [3 3]     [4 4]
(    Decrement.        [1 0]     [2 1]     [3 2]     [4 3]
_    Duplicate.        [1 0 0]   [2 1 1]   [3 2 2]   [4 3 3]
1&   AND 1.            [1 0 0]   [2 1 1]   [3 2 0]   [4 3 1]
)    Increment.        [1 0 1]   [2 1 2]   [3 2 1]   [4 3 2]
^    XOR.              [1 1]     [2 3]     [3 3]     [4 1]
2/   Halve.            [1 0]     [2 1]     [3 1]     [4 0]
)    Increment.        [1 1]     [2 2]     [3 2]     [4 1]
W    Push -1.          [1 1 -1]  [2 2 -1]  [3 2 -1]  [4 1 -1]
@    Rotate.           [1 -1 1]  [2 -1 2]  [2 -1 3]  [1 -1 4]
#    -1^n.             [1 -1]    [2 1]     [2 -1]    [1 1]
*    Multiply.         [-1]      [2]       [-2]      [1]

```
> 3 votes

# Answer
# Perl 6,  ~~55 27 24~~  22 bytes

```
{(-1,2,-2,1,{|($^a,$^b,$^c,$^d Z+ -2,2,-2,2)}...*)[$_]}

```

(Inspired by the Haskell `zipWith` answer)
Try it

```
{+^($_ div 2)+$_%2*($_+|2)}

```

(Inspired by several answers)
Try it

```
{+^($_+>1)+$_%2*($_+|2)}

```

Try it

```
{+^$_+>1+$_%2*($_+|2)}

```

Try it

## Expanded:

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

    +^          # numeric binary invert the following
      $_ +> 1   # numeric bit shift right by one
  +
      $_ % 2    # the input modulo 2
    *
      ($_ +| 2) # numeric binary inclusive or 2
}

```

(All are 0 based)
> 2 votes

# Answer
# Haskell, ~~37~~ 36 bytes

```
(([1,3..]>>= \x->[-x,x+1,-x-1,x])!!)

```

Try it online! This is an anonymous function which takes one number `n` as argument and returns 0-indexed the `n`th element of the sequence.
> 2 votes

# Answer
# Perl 5 47 + 1 (for flag) = 48 Bytes

```
print(((sin$_%4>.5)+1+2*int$_/4)*($_%4&1?1:-1))

```

### Old Submission 82 Bytes

```
@f=(sub{-$_[0]},sub{$_[0]+1},sub{-$_[0]-1},sub{$_[0]});print$f[$_%4](1+2*int$_/4)

```

Run like so:

```
perl -n <name of file storing script>  <<<  n

```
> 1 votes

# Answer
# Haskell, 56 bytes

```
f n=concat(iterate(zipWith(+)[-2,2,-2,2])[-1,2,-2,1])!!n

```

0-indexed
> 1 votes

# Answer
# JavaScript, ~~28~~ 22 bytes

Thanks @ETHproductions for golfing off 6 bytes

```
x=>x%2?~x>>1:x%4+x/2-1

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES7), 28 bytes

```
n=>(n+2>>2)*2*(-1)**n-!(n&2)

```

1-indexed. I haven't looked at any other answers yet so I don't know if this is the best algorithm, but I suspect not.
> 1 votes

# Answer
# dc, 98 bytes

```
?sa0sb1sq[lq1+dsqla!<i3Q]sf[lb1-lfx]su[lblfx]sx[lb1+dsblfx]sj[lqdd4%d0=u1=j2%1=xljxlfx]dsix_1la^*p

```

Gosh, this is the longest answer here, mainly because I went the path of generating the absolute value of each element of the sequence one by one based on the following recursive formula:

then outputting `(-1)^n * a_n`, rather than directly computing the `n`'th element. Anyways, this is `1`-indexed.

Try it online!
> 1 votes

# Answer
# R, 38 bytes

```
function(n)floor(n/2+1-2*!n%%4)*(-1)^n

```

Explanation

```
floor(n/2+1)                ->  1 2  2 3  3 4  4 5...
floor(n/2+1-2*!n%%4)        ->  1 2  2 1  3 4  4 3... (subtract 2 where n%%4 == 0)
floor(n/2+1-2*!n%%4)*(-1)^n -> -1 2 -2 1 -3 4 -4 3... (multiply odd n by -1)

```
> 1 votes

# Answer
# TI-Basic (TI-84 Plus CE), 31 bytes

```
.5(Ans+1+remainder(Ans+1,2)-4not(remainder(Ans,4)))i^(2Ans

```

TI-Basic is a tokenized language and each token used here is one byte, except `remainder(`, which is two.

This uses the 1-indexed version.

Explanation:

There is a pattern that repeats every four numbers. In the 1-indexed version, it is: -(x+1)/2, (x+1)/2, -(x+1)/2, (x-1)/2 for the input value x. This can be represented as a piecewise-defined function.

f(x) = -(x+1)/2 if x ≡ 1 mod 4; (x+1)/2 if x ≡ 2 mod 4; -(x+1)/2 if x ≡ 3 mod 4; (x-1)/2 if x ≡ 0 mod 4

Because the "x ≡ 1 mod 4" and "x ≡ 3 mod 4" parts are the same, we can combine them into "x ≡ 1 mod 2".

Now are piecewise function is:

f(x) = -(x+1)/2 if x ≡ 1 mod 2; (x+2)/2 if x ≡ 2 mod 4; (x-2)/2 if x ≡ 0 mod 4

This is where I start breaking it into actual commands. Since the value is positive for even indexes and negative for odd ones, we can use (-1)^x. However, in TI-Basic `i^(2X` (5 bytes) is shorter than `(-1)^Ans` (6 bytes). Note that parentheses are required due to order of operations.

Now that we have the way to negate the odd inputs out of the way, we move on to the mods (adding the negating back on later). I made the case of an odd input the default, so we start with `.5(Ans+1)`.

To fix the case of even input, just add one to the number in the parentheses, but only when x ≡ 0 mod 2. This could be represented as `.5(Ans+1+remainder(Ans+1,2))` or `.5(Ans+1+not(remainder(Ans,2)))`, but they have the same byte count, so it doesn't matter which.

To fix the case of multiple-of-4 input, we need to subtract 3 from the number in the parentheses, but also another 1 because all multiples of 4 are even, which would add one from our previous step, so we now have `.5(Ans+1+remainder(Ans+1,2)-4not(remainder(Ans,4)))`.

Now, just tack on the sign-determining part to the end to get the full program.
> 1 votes

# Answer
# Befunge 93, 25 bytes

Zero-indexed

```
&4/2*1+&4%3%!!+&2%2*1-*.@

```

Try it Online!

The number is given by `((2(n / 4) + 1) + !!((n % 4) % 3)) * (2(n % 2) - 1)`
> 0 votes

# Answer
## QBIC, 53 bytes

```
b=1:{[b,b+3|~b=a|_x(-(b%2)*2+1)*(q+(b%4>1)*-1)]]q=q+2

```

Explanation:

```
b=1     Set b to a starting value of 1
        QBIC would usually use the pre-initialised variable q, but that is already in use
:       Get an input number from the cmd-line, our term to find
{       Start an infinite loop
[b,b+3| FOR-loop: this runs in groups of 4, incrementing its own bounds between runs
~b=a|   If we've reached the term requested
_x      QUIT the program and print:

(-(b%2)*2+1)   The b%2 gives a 1 or a 0, times 2 (2,0), negged (-2,0) and plus one (-1,1)
*              That gives us the sign of our term. Now the value:
(q+(b%4>1)*-1) This is q + 1 if the inner loop counter MOD 4 (1,2,3,0...) is 2 or 3.
]       Close the IF that checks the term
]       Close the FOR-loop
q=q+2   And raise q by 2 for the next iteration of the DO-loop.

```
> 0 votes

# Answer
# Wise, 19 bytes

```
::>!:><^^~![!-!-~]|

```

Try it Online!

This is just a port of @Dennis' Jelly answer to Wise.
> 0 votes

# Answer
## Q, 52 bytes

```
{(1 rotate(,/){x,(-)x}each 1_((_)x%4)+til 3)x mod 4}

```

0 indexed solution.

1. Gets the block number ie. which \[-x x+1 -(x+1) x\] block within the sequence contains the index.
2. Gets the index of the value within the block based on the index of the value within the whole sequence.
3. Creates the block.
4. Indexes into it via index derived in step 2.
> 0 votes

---
Tags: code-golf, number, sequence, arithmetic, integer
---


title: Island Golf #2: The Eccentric Hermits

text:
# Question
Title: Island Golf #2: The Eccentric Hermits
<sup>*This is the second in a series of Island Golf challenges. Previous challenge*</sup>

Two hermits have arrived on a desert island. Since they came seeking solitude, they wish to live as far away from each other as possible. Where should they build their huts to maximize the walking distance between them?

Related reading

## Input

Your input will be a rectangular grid consisting of two characters, representing land and water. In the examples below, land is `#` and water is `.`, but you may substitute any two distinct characters you wish.

```
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........

```

There will always be at least two land tiles. The land tiles will all be contiguous (i.e. there's only one island). The water tiles will also be contiguous (i.e. there are no lakes). The outer border of the grid will all be water tiles. Land tiles will **not** be connected diagonally: i.e., you will never see something like

```
....
.#..
..#.
....

```

## Output

Your code must output the same grid, with two *hut locations* marked on it. In the examples below, the hut locations are marked with X, but you may substitute any character as long as it is distinct from your land and water characters.

The hut locations must be two land tiles, chosen so as to maximize the *walking distance* between them. We define walking distance as the length of the shortest path, entirely on land, between the two points. Land tiles are considered adjacent horizontally or vertically, but **not** diagonally.

A possible solution for the above island:

```
...........
...X#......
..#####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........

```

The walking distance between these two points is 11, which is the greatest distance between any two points on this island. There is another distance-11 solution:

```
...........
...##......
..X####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........

```

## Details

Your solution may be a full program or a function. Any of the default input and output methods are acceptable.

Your input and output may be a multiline string, a list of strings, or a 2D array/nested list of characters/single-character strings. Your output may (optionally) have a single trailing newline. As mentioned above, you may use any three distinct characters in place of `#.X` (please specify in your submission which characters you're using).

## Test cases

**A.** Islands with unique hut placements:

```
....
.##.
....

....
.XX.
....

......
......
..##..
...#..
......
......

......
......
..X#..
...X..
......
......

........
.#####..
.##..##.
.#..###.
.##..##.
........

........
.#####..
.##..##.
.#..###.
.#X..#X.
........

.........
.#####.#.
.#...#.#.
.#.###.#.
.#.....#.
.#######.
.........

.........
.#####.X.
.#...#.#.
.#.X##.#.
.#.....#.
.#######.
.........

```

**B.** Example of an island with multiple possible solutions:

```
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........

```

Possible outputs:

```
........
....#X..
...####.
..###...
.#####..
.X####..
..##....
........

........
....#X..
...####.
..###...
.#####..
.#####..
..X#....
........

........
....##..
...###X.
..###...
.#####..
.X####..
..##....
........

........
....##..
...###X.
..###...
.#####..
.#####..
..X#....
........

```

**C.** Large test case as a Gist

---

This is : the shortest code in each language wins.

# Answer
> 6 votes
# Python 3, ~~249~~ 246 bytes

Shaved off 3 bytes, thanks DLosc.

Input and output are single strings, with '.', '@', and 'X' representing water, huts, and land, respectively.

```
A='@'
def f(s):
 w=s.find('\n')+1;d=u={(k,k):0for k,c in enumerate(s)if A<c}
 while u:d.update(u);u={(k,j):d[(k,i)]+1for k,i in d for j in{i+1,i+w,i-1,i-w}if A<s[j]and(k,j)not in d}
 k,j=sorted(max(d,key=d.get))
 return s[:k]+A+s[k+1:j]+A+s[j+1:]

```

Prior version:

Input is a single string, with '.' and '#' representing water and land, respectively. 'X' represents the huts in the output.

```
def f(s):
 w=s.find('\n')+1;d=u={(k,k):0for k,c in enumerate(s)if'#'==c}
 while u:d.update(u);u={(k,j):d[(k,i)]+1 for k,i in d for j in{i+1,i+w,i-1,i-w}if'#'==s[j]and(k,j)not in d}
 k,j=sorted(max(d,key=d.get))
 return s[:k]+'X'+s[k+1:j]+'X'+s[j+1:]

```

Explanation:

It's basically doing a breadth first search from every possible starting point at the same time. Keep a dictionary, d, of path lengths keyed by the start and end of the path, e.g., d\[(k,i)\] is the distance from k to i. Then iterate over the keys in the dictionary, d, and create a new dictionary, u, with paths that are 1 unit longer by moving the end point 1 unit to the N,S,E,W, e.g., u\[(k, i+1)\] = d\[(k,i)\] + 1. Don't include paths that are already in d. If u is not empty, then add the new longer paths to d and repeat. When u is empty, that means no more paths could be made. Now d contains all the possible paths and their lengths. So its just a matter of getting the key with the longest path.

Less golfed, commented version:

```
def f(s):
  w=s.find('\n')+1                    # width of a row, or a move N or S

  d = {}                              # dictionary of all the paths.
                                      # The key is a tuple (k,j) and the
                                      # value is the distance from k to j.
  for k,c in enumerate(s):            # Initialize. Distance from k to k is 0
    if'#'==c:                         # Only do land.
      d[(k,k)] = 0

  u = d                               # dictionary of new paths. initialize it to d
                                      # so loop is entered. first d.update is
                                      # basically a NOP

  while u:                            # while there are new paths
    d.update(u)                       # add the new paths to the dict of old paths
    u={}                              #
    for k,i in d:                     # iterate over the known paths. k is the start, i is the end
      for j in{i+1,i+w,i-1,i-w}:      # iterate over squares 1 move to the E,S,W,N from i
        if'#'==s[j]and(k,j)not in d:  # if it's still land, and the path (k,j) isn't already in d,
          u[(k,j)] = d[(k,i)]+1       # then add the new path to u

  k,j=sorted(max(d,key=d.get))        # find the longest path

  return s[:k]+'X'+s[k+1:j]+'X'+s[j+1:]  # X marks the endpoints.

```

# Answer
> 3 votes
# C#, 387 bytes

Let's get the ball rolling...

```
using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z,n,q,h,b=0,c,a,i=0,j=0;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L+="\n";for(z=H;z-->0;){int[]S=new int[H],Q=new int[H*8];for(Q[h=q=0]=z;q<=h;)if((c=S[n=Q[q++]]-1)<0&D[S[n]=n]==35)for(a=4;a-->0;b=c<b?c+(i=z)*(j=n)*0:b)S[Q[++h]=new[]{1,-1,W,-W}[a]+n]=S[Q[h]]<1?c:1;}for(;++z<H;)C.Write(z==i|z==j?'X':D[z]);}}

```

Try it Online

Complete program, reads from STDIN, writes to STDOUT. It simply goes over each cell, and runs a BFS to compute the farthest cell, recording both if it is the farthest on record. Nothing to it really, and frustratingly little I can find to golf.

Formatted and commented code:

```
using C=System.Console;

class P
{
    // \n 10
    // \r 13
    // . 46
    // # 35
    // x 88

    static void Main()
    {
        string D="", // map
            L; // line of input

        int W=0, // width
            H=0, // length
            z, // outer position
            n, // next position to expand
            q, // queue position pointer
            h, // queue head pointer
            b=0, // best
            c, // distance to this cell (negative)
            a, // counter
            i=0, // hermit 1 pos
            j=0; // hermit 2 pos

        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and add to length
            D+=L+="\n"; // add a newline, and add the line to the map

        for(z=H;z-->0;) // for each cell
        {
            int[]S=new int[H], // 'seen' >0 -> seen, else it is the distance we have found to it
                Q=new int[H*8]; // due queue (fewer than H*4 expantions, two ints each)

            // standard BFS
            for(Q[h=q=0] // reset currect
                =z; // expand z first
                q<=h;)
                if((c=S[n=Q[q++]]-1)<0& // record 'seen', and check we havn't been seen
                    D[S[n]=n]==35) // mark as seen, and check we are a hash #
                    // 'move'
                    for(a=4;a-->0; // for each of the 4 neighbours
                            b=c<b? // if we have beaten the best
                            c+(i=z)*(j=n)*0: // set new best, record hermit positions
                            b)
                        S[Q[++h]=new[]{1,-1,W,-W}[a]+n]= // queue it for expantion
                        S[Q[h]]<1? // not seen? (this is BFS, don't need to check c is less thatn S[l+n]
                        c: // distance
                        1; // mark as seen (means it won't actually be expanded)
        }

        // z = -1
        for(;++z<H;) // for each cell
            C.Write(z==i|z==j?'X':D[z]); // print either the original char, or X if it is a hermit's home
    }
}

```

---
Tags: code-golf, ascii-art, grid, graph-theory, optimization
---


title: Simple Task Solved Thrice

text:
# Question
Title: Simple Task Solved Thrice
You should write 3 programs and/or functions in one language.

All of these programs should solve the same task but they all should give different (but valid) outputs. (I.e. for every pair of programs their should be some input which generates different (but valid) sets of output numbers.)

## The task

* You are given an integer `n`, greater than 1
* You should return or output `n` **distinct** positive integers, and **none of them should be divisible by `n`**.
* The order of the numbers doesn't matter and a permutation of numbers doesn't count as different outputs.

A valid triplet of programs with some `input => output` pairs:

```
program A:
    2 => 5 9
    4 => 5 6 9 10
    5 => 2 4 8 7 1

program B:
    2 => 1 11
    4 => 6 9 1 2
    5 => 4 44 444 4444 44444

program C (differs only in one number from program B):
    2 => 1 13
    4 => 6 9 1 2
    5 => 4 44 444 4444 44444

```

## Scoring

* Your score is the sum of the lengths of the 3 programs or functions.
* Lower score is better.
* If your programs/functions share code, the shared code should be counted into the length of every program that uses the code.

# Answer
> 4 votes
# Pyth, ~~17~~ 16 bytes

## 5 bytes:

```
^LhQQ

```

Outputs:

```
2: [1, 3]
3: [1, 4, 16]
4: [1, 5, 25, 125]

```

## 6 bytes:

```
mh*QdQ

```

Outputs:

```
2: [1, 3]
3: [1, 4, 7]
4: [1, 5, 9, 13]

```

## 5 bytes:

```
|RhQQ

```

Outputs:

```
2: [3, 1]
3: [4, 1, 2]
4: [5, 1, 2, 3]

```

Alternate version, in increasing order: `-ShQQ`

# Answer
> 8 votes
# J, 16 bytes

### Function 1, 5 bytes

```
p:^i.

```

### Function 2, 6 bytes

```
+p:^i.

```

### Function 3, 5 bytes

```
>:^i.

```

## How it works

### Function 1

```
p:^i.     Right argument: y

   i.     Compute (0 ... y-1).
p:        Compute P, the prime at index y (zero-indexed).
  ^       Return all powers P^e, where e belongs to (0 ... y-1).

```

Since **P** is prime and **P \> y**, **y** cannot divide **Pe**.

### Function 2

```
+p:^i.    Right argument: y

 p:^i.    As before.
+         Add y to all results.

```

If **y** divided **Pe \+ y**, it would also divide **Pe \+ y - y = Pe**.

### Function 3

```
>:^i.     Right argument: y

   i.     Compute (0 ... y-1).
>:        Compute y+1.
  ^       Return all powers (y+1)^e, where e belongs to (0 ... y-1).

```

If **y** divided **(y+1)e** some prime factor **Q** of **y** would have to divide **(y+1)e**.

But then, **Q** would divide both **y** and **y+1** and, therefore, **y + 1 - y = 1**.

# Answer
> 3 votes
## Dyalog APL, ~~16~~ 17 bytes

```
1+⊢×⍳

⊢+1+⊢×⍳

1+⊢*⍳

```

# Answer
> 2 votes
# Vitsy, 54 bytes

### Programs:

```
V1V\[DV*1+N' 'O1+]
```

```
V2V\[DV*1+N' 'O1+]
```

```
V3V\[DV*1+N' 'O1+]
```

### Outputs:

```
2 => 3 7
4 => 5 9 13 17
5 => 6 11 16 21 26
```

```
2 => 5 7
4 => 9 13 17 21
5 => 11 16 21 26 31
```

```
2 => 7 9
4 => 13 17 21 25
5 => 16 21 26 31 36
```

### How it works (using the first program as the explanation):

```
V1V\[DV*1+N' 'O1+]
V                  Capture the implicit input as a final global variable.
 1                 Push one to the stack for later use.
  V\[            ] Do everything in the brackets input times.
     D             Duplicate the top item of the stack.
      V            Push the global variable to the stack.
       *1+         Multiply, then add 1. This makes it non-divisible.
          N' 'O    Output the number followed by a space.
               1+  Add one to the number left in the stack.
```

Try it online!

# Answer
> 2 votes
## CJam, 8 + 8 + 8 = 24 bytes

```
{,:)))+}
{_,f*:)}
{)_(,f#}

```

These are three unnamed functions which expect `n` to be on the stack and leave a list of integers in its place. I'm not sure this is optimal, but I'll have to hunting for a shorter solution later.

Test suite.

Results:

```
{,:)))+}
2 => [1 3]
3 => [1 2 4]
4 => [1 2 3 5]
5 => [1 2 3 4 6]

{_,f*:)}
2 => [1 3]
3 => [1 4 7]
4 => [1 5 9 13]
5 => [1 6 11 16 21]

{)_(,f#}
2 => [1 3]
3 => [1 4 16]
4 => [1 5 25 125]
5 => [1 6 36 216 1296]

```

The first one also works as

```
{_),:)^}

```

or

```
{_(,+:)}

```

# Answer
> 2 votes
## Perl, 79

One char added to each program because this requires the `-n` flag.

```
for$a(0..$_-1){say$_*$a+1}
for$a(1..$_){say$_*$a+1}
for$a(2..$_+1){say$_*$a+1}

```

Fairly straightforward.

# Answer
> 2 votes
## Mathematica, 12 + 12 + 12 = 36 bytes

```
# Range@#-1&
# Range@#+1&
#^Range@#+1&

```

Tests:

```
# Range@#-1&[10]
(* -> {9, 19, 29, 39, 49, 59, 69, 79, 89, 99} *)
# Range@#+1&[10]
(* -> {11, 21, 31, 41, 51, 61, 71, 81, 91, 101} *)
#^Range@#+1&[10]
(* -> {11, 101, 1001, 10001, 100001, 1000001, 10000001, 100000001, 1000000001, 10000000001} *)

```

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

```
lambda n:range(1,n*n,n)
lambda n:range(1,2*n*n,2*n)
lambda n:range(1,3*n*n,3*n)

```

Three anonymous function that start at `1` and count up by each of `n, 2*n, 3*n` for `n` terms.

# Answer
> 1 votes
## Python 2, 125 bytes

```
N=input();print[i*N+1for i in range(N)]
N=input();print[i*N+1for i in range(1,N+1)]
N=input();print[i*N+1for i in range(2,N+2)]

```

Each line here is a complete program. The most obvious solution in my mind.

**EDIT** @Sherlock9 saved two bytes.

# Answer
> 1 votes
## Seriously, 20 bytes

```
,;r*1+

,;R*1+

,;R1+*1+

```

Yeah, this isn't optimal...

# Answer
> 1 votes
# Par, 16 bytes

The custom encoding, described here, uses only one byte per character.

```
✶″{*↑                   ## 3 => (0 1 2) => (0 3 6)  => (1 4 7)
✶″U{ⁿ↑                  ## 3 => (1 2 3) => (3 9 27) => (4 10 28)
✶U¡↑◄                   ## 3 => (1 2 3) =>             (1 2 4)

```

## Outputs

```
2 => (1 3)
3 => (1 4 7)
4 => (1 5 9 13)
5 => (1 6 11 16 21)

2 => (3 5)
3 => (4 10 28)
4 => (5 17 65 257)
5 => (6 26 126 626 3126)

2 => (1 3)
3 => (1 2 4)
4 => (1 2 3 5)
5 => (1 2 3 4 6)

```

# Answer
> 1 votes
# Haskell, 54 bytes

```
f n=n+1:[1..n-1]
g n=5*n+1:[1..n-1]
h n=9*n+1:[1..n-1]

```

These three functions are pretty straightforward so…

# Answer
> 1 votes
# Octave, 11 + 13 + 13 = 37 bytes

```
@(a)1:a:a^2
@(a)a-1:a:a^2
@(a)(1:a)*a+1

```

# Answer
> 1 votes
# Haskell, 50

```
f n=n+1:[1..n-1]
f n=1:[n+1..2*n-1]
f n=[1,n+1..n^2]

```

Examples:

```
 f1 5=[6,1,2,3,4]
 f2 5=[1,6,7,8,9]
 f3 5=[1,6,11,16,21]

```

# Answer
> 0 votes
# Golfscript, 50 ~~51~~ ~~57~~ bytes

A Golfscript version of what used to be quintopia's Python code. Each function takes `n` off the stack.

```
{.,{1$*)}%\;}:f;    i*n+1 for i in range(n)
{.,{)1$*)}%\;}:g;   i*n+1 for i in range(1,n+1)
{.,{1$)\?}%\;}:h;   (n+1)**i for i in range(n)

```

# Answer
> 0 votes
# TI-Basic (TI-84 Plus CE), ~~55~~ 40 bytes total

```
PRGM:C 12 bytes
    seq(AnsX+1,X,1,Ans

```

```
PRGM:B 14 bytes
    seq(AnsX+1,X,2,Ans+1

```

```
PRGM:C 14 bytes
    seq(AnsX+1,X,3,Ans+2

```

Simple, similar to many other answers here, each displays a list of the numbers (X+A)N+1 for X in range(N) and with A being which program (1, 2, or 3).

Old solution (55 bytes):

```
PRGM:C 17 bytes
    Prompt N
    For(X,1,N
    Disp XN+1
    End

```

```
PRGM:B 19 bytes
    Prompt N
    For(X,2,N+1
    Disp XN+1
    End

```

```
PRGM:C 19 bytes
    Prompt N
    For(X,3,N+2
    Disp XN+1
    End

```

Simple, similar to many other answers here, each displays the numbers (X+A)N+1 for X in range(N) and with A being which program (1, 2, or 3).

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


title: What are my chess moves?

text:
# Question
Title: What are my chess moves?
Chess is a game with 6 different types of pieces that can move in different ways:

* Pawns - They can only move up or capture diagonally (also forward). Capturing a piece behind them or beside them is illegal. The only exception is en passant. For this challenge, if a pawn reaches the 8th rank (or row), assume it becomes a queen.
* Bishops - They move diagonally and the squares they travel on will always have the same color (i.e if the square the bishop is currently on is white, the bishop can't move to a darker square for instance).
* Knights - They move pretty awkwardly. They can move two spaces up/down then one space to the right/left or two spaces right/left then on space up/down.
* Rooks - They can only move in straight lines, up or down or left or right.
* Queens - They can move diagonally like a bishop or in straight lines like a rook
* Kings - They can only move to squares they are touching (including diagonals).

This chess.com link to clarify the above. A chessboard and its coordinates are shown below:

So given an entirely empty chessboard except for one piece and the inputs -- the piece's type and its current position, what are the piece's legal moves?

**Examples**

```
Input: Rook a8
Output: a1 a2 a3 a4 a5 a6 a7 b8 c8 d8 e8 f8 g8 h8

Input: Pawn a2
Output: a4 a3

Input: Pawn a3
Output: a4

Input: Knight a1
Output: c2 b3

Input: Bishop h1
Output: a8 b7 c6 d5 e4 f3 g2

Input: King b2
Output: c2 c3 c1 b3 b1 a1 a2 a3

Input: Queen h1
Output: a8 b7 c6 d5 e4 f3 g2 h2 h3 h4 h5 h6 h7 h8 a1 b1 c2 d1 e1 f1 g1

```

**Rules and Specifications**

* A legal move is defined as a move in which the piece can go to while being on the board. So a rook at a1 can go to a8 (moving to the right) but not to b2 since you can't get there with a straight line (only possible in two or more moves)
* Pawns will never be in the first or eighth rank (it would then be another piece). If a pawn is in the second rank, it can move up two spaces (not for captures). Otherwise, it can only move forward a square.
* Notation for Queening a pawn is not needed
* Capitalization does not matter though the letter must come before and attached to the number
* The acceptable moves must be separated in some way (i.e commas, spaces, different lines, in a list)
* Always assume that the bottom left corner is a1 and you are playing as White
* The input can be a single string (i.e `rooka3` or `Rook a3` or `rook a3` or `Rook A3`) is acceptable and can be in any order (i.e the position before the type like `A3 rook`). Multiple strings are also acceptable.

**Winning Criteria**

Shortest code wins!

# Answer
## JavaScript (ES6), ~~256~~ ... ~~229~~ 227 bytes

Takes input as two strings `(p, s)`, where `p` is the case-insensitive name of the piece and `s` is the source square. Returns a space-separated list of destination squares.

```
f=(p,s,i=128)=>i--?f(p,s,i)+([x=255,x<<8,2,x,195,60][P=(I=parseInt)(p,32)*5&7]>>i/8&((d=i%8)<(S=(x=I(s,18)-181)/18|x%18*16,P>2?8:P<2|S>23||2))&!((S+=I('gfh1eivx'[i>>4],36)*(i&8?d+1:~d))&136)?'abcdefgh'[S&7]+(S+16>>4)+' ':''):''

```

### How it works

**Piece name decoding**

The name of the piece `p` is converted to an integer `P` by parsing it in base 32, multiplying the result by 5 and isolating the 3 least significant bits: `parseInt(p, 32) * 5 & 7`

```
 Piece    | As base 32 |        * 5 | & 7
----------+------------+------------+----
 "king"   |     674544 |    3372720 |  0
 "knight" |  695812669 | 3479063345 |  1
 "pawn"   |        810 |       4050 |  2    NB: 'pawn' is parsed as 'pa', because 'w'
 "queen"  |   28260823 |  141304115 |  3        is not a valid character in base 32
 "rook"   |     910100 |    4550500 |  4
 "bishop" |  388908825 | 1944544125 |  5

```

In addition to being a perfect hash, a good thing about this formula is that all sliding pieces (Queen, Rook and Bishop) appear at the end of the list, which allows to identify them with a simple `P > 2`.

**Source square decoding**

The source square `s` is converted to an integer `S` by parsing it in base 18 and converting the result to 0x88 coordinates.

That leads to the following board representation:

```
     a    b    c    d    e    f    g    h
8  0x70 0x71 0x72 0x73 0x74 0x75 0x76 0x77
7  0x60 0x61 0x62 0x63 0x64 0x65 0x66 0x67
6  0x50 0x51 0x52 0x53 0x54 0x55 0x56 0x57
5  0x40 0x41 0x42 0x43 0x44 0x45 0x46 0x47
4  0x30 0x31 0x32 0x33 0x34 0x35 0x36 0x37
3  0x20 0x21 0x22 0x23 0x24 0x25 0x26 0x27
2  0x10 0x11 0x12 0x13 0x14 0x15 0x16 0x17
1  0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07

```

**Directions encoding**

There are 16 possible directions: 4 along ranks and files, 4 along diagonals and 8 for the knights.

```
As hexadecimal:                     As decimal:

      +0x1F       +0x21                    +31         +33
+0x0E +0x0F +0x10 +0x11 +0x12        +14   +15   +16   +17   +18
      -0x01 [SRC] +0x01                     -1  [SRC]   +1
-0x12 -0x11 -0x10 -0x0F -0x0E        -18   -17   -16   -15   -14
      -0x21       -0x1F                    -33         -31

```

Therefore, the list of directions that a piece can move towards can be encoded as a 16-bit bitmask.

```
Bit:    |   F   E   D   C   B   A   9   8   7   6   5   4   3   2   1   0 | As
Vector: | +33 -33 +31 -31 +18 -18 +14 -14  +1  -1 +17 -17 +15 -15 +16 -16 | decimal
--------+-----------------------------------------------------------------+--------
King    |   0   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1 | 255
Knight  |   1   1   1   1   1   1   1   1   0   0   0   0   0   0   0   0 | 65280
Pawn    |   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0 | 2
Queen   |   0   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1 | 255
Rook    |   0   0   0   0   0   0   0   0   1   1   0   0   0   0   1   1 | 195
Bishop  |   0   0   0   0   0   0   0   0   0   0   1   1   1   1   0   0 | 60

```

The absolute values of the direction vectors can be stored in base 36:

```
[16, 15, 17, 1, 14, 18, 31, 33][n] <==> parseInt('gfh1eivx'[n], 36)

```

**Formatted and commented**

```
f = (p, s, i = 128) =>                     // given a piece p, a square s and a counter i
  i-- ?                                    // if i is >= 0:
    f(p, s, i) + (                         //   do a recursive call to f()
      [ x = 255, x << 8, 2, x, 195, 60 ][  //   take the direction bitmask for:
        P = (I = parseInt)(p, 32) * 5 & 7  //   P = piece index in [0 .. 5]
      ] >> i / 8 & (                       //   and test the bit for the current direction
        (d = i % 8) < (                    //   d = current move distance - 1
          S = (x = I(s, 18) - 181) / 18 |  //   S = source square in
              x % 18 * 16,                 //       0x88 representation
          P > 2 ? 8 : P < 2 | S > 23 || 2  //   compare d with the maximum move range for
        )                                  //   this piece
      ) ?                                  //   if the above test passes:
        (                                  //     we add to S:
          S += I(                          //       the absolute value of the vector of
            'gfh1eivx'[i >> 4], 36         //       the current direction,
          ) *                              //       multiplied by
          (i & 8 ? d + 1 : ~d)             //       the move distance with the vector sign
        ) & 136 ?                          //     if the result AND'd with 0x88 is not null:
          ''                               //       this is an invalid destination square
        :                                  //     else:
          'abcdefgh'[S & 7] +              //       it is valid: convert it back to ASCII
          (S + 16 >> 4) + ' '              //       and append a space separator
      :                                    //   else:
        ''                                 //     this is an invalid move
    )                                      //   end of this iteration
  :                                        // else:
    ''                                     //   stop recursion

```

### Test cases

```
f=(p,s,i=128)=>i--?f(p,s,i)+([x=255,x<<8,2,x,195,60][P=(I=parseInt)(p,32)*5&7]>>i/8&((d=i%8)<(S=(x=I(s,18)-181)/18|x%18*16,P>2?8:P<2|S>23||2))&!((S+=I('gfh1eivx'[i>>4],36)*(i&8?d+1:~d))&136)?'abcdefgh'[S&7]+(S+16>>4)+' ':''):''

console.log(f('Rook',   'a8'));
console.log(f('Pawn',   'a2'));
console.log(f('Pawn',   'a3'));
console.log(f('Knight', 'a1'));
console.log(f('Bishop', 'h1'));
console.log(f('King',   'b2'));
console.log(f('Queen',  'h1'));
```
> 7 votes

# Answer
# Python 2, ~~484~~ ~~472~~ ~~423~~ 406 bytes

This is a lot longer than I wanted it to be.

```
i=input()
a=ord(i[1][0])-97
c=int(i[1][1])
g=range(-8,8)
b=sum([[(a-x,c-x),(a-x,c+x)]for x in g],[])
r=sum([[(a-x,c),(a,c-x)]for x in g],[])
print[chr(x[0]+97)+str(x[1])for x in set([[(a,c+1)]+[(a,c+2)]*(c==2),b,sum([[(a-x,c-y)for x,y in[[X,Y],[X,-Y],[-X,Y],[-X,-Y]]]for X,Y in[[1,2],[2,1]]],[]),r,b+r,[(a-x,c-y)for x in[-1,0,1]for y in[-1,0,1]]]['wsioen'.find(i[0][2])])-set([a,c])if-1<x[0]<8and 0<x[1]<9]

```

-12 bytes by removing some unnecessary variable names
-49 bytes thanks to ovs by splitting s into multiple variables
-17 bytes thanks to ovs by switching from range to comparison

Input is taken as `['PieceName', '<letter><num>']`. Output is given as an array of strings in the same 1-indexed a-h format `<letter><num>`.
> 2 votes

---
Tags: code-golf
---


# Question
Title: Count the number of Hamming distance sequences
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Let `P` be a binary string of length `n` and `T` be a binary string of length `2n-1`. We can compute the `n` Hamming distances between `P` and every `n`-length substring of `T` in order from left to right and put them into an array (or list).

**Example Hamming distance sequence**

Let `P = 101` and `T = 01100`. The sequence of Hamming distances you get from this pair is `2,2,1`.

**Task**

For increasing `n` starting at `n=1`, consider all possible pairs of binary strings `P` of length `n` and `T` of length `2n-1`. There are `2**(n+2n-1)` such pairs and hence that many sequences of Hamming distances. However many of those sequences will be identical . The task is to find how many are distinct for each `n`.

Your code should output one number per value of `n`.

**Score**

Your score is the highest `n` your code reaches on my machine in 5 minutes. The timing is for the total running time, not the time just for that `n`.

**Who wins**

The person with the highest score wins. If two or more people end up with the same score then it is the first answer that wins.

**Example answers**

For `n` from `1` to `8` the optimal answers are `2, 9, 48, 297, 2040, 15425, 125232, 1070553`.

**Languages and libraries**

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

**My Machine** The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

**Leading answers**

* **11** in **C++** by feersum. 25 seconds.
* **11** in **C++** by Andrew Epstein. 176 seconds.
* **10** in **Javascript** by Neil. 54 seconds.
* **9** in **Haskell** by nimi. 4 minutes and 59 seconds.
* **8** in **Javascript** by fəˈnɛtɪk. 10 seconds.

# Answer
> 3 votes
## C++11 (should get to 11 or 12)

At the moment this is single-threaded.

To compile:

```
g++ -std=c++11 -O2 -march=native feersum.cpp

```

```
#include <iostream>
#include <unordered_set>
#include <vector>
#include <unordered_map>
#include <string.h>

using seq = uint64_t;
using bitvec = uint32_t;
using seqset = std::unordered_set<seq>;
using std::vector;

#define popcount __builtin_popcount
#define MAX_N_BITS 4

bitvec leading(bitvec v, int n) {
    return v & ((1U << n) - 1);
}
bitvec trailing(bitvec v, int n, int total) {
    return v >> (total - n);
}

bitvec maxP(int n) {
    return 1 << (n - 1);  // ~P, ~T symmetry
}

void prefixes(int n, int pre, int P, seqset& p) {
    p.clear();
    for (bitvec pref = 0; pref < (1U << pre); pref++) {
        seq s = 0;
        for (int i = 0; i < pre; i++) {
            seq ham = popcount(trailing(pref, pre - i, pre) ^ leading(P, pre - i));
            s |= ham << i * MAX_N_BITS;
        }
        p.insert(s);
    }
}

vector<seqset> suffixes(int n, int suf, int off) {
    vector<seqset> S(maxP(n));
    for (bitvec P = 0; P < maxP(n); P++) {
        for (bitvec suff = 0; suff < (1U << suf); suff++) {
            seq s = 0;
            for (int i = 0; i < suf; i++) {
                seq ham = popcount(leading(suff, i + 1) ^ trailing(P, i + 1, n));
                s |= ham << (off + i) * MAX_N_BITS;
            }
            S[P].insert(s);
        }
    }
    return S;
}

template<typename T>
void mids(int n, int npre, int nsuf, int mid, bitvec P, T& S, const seqset& pre) {
    seq mask = (1ULL << (npre + 1) * MAX_N_BITS) - 1;
    for(bitvec m = 0; m < 1U << mid; m++) {
        int pc = popcount(P ^ m);
        if(pc * 2 > n) continue; // symmetry of T -> ~T : replaces x with n - x
        seq s = (seq)pc << npre * MAX_N_BITS;
        for(int i = 0; i < npre; i++)
            s |= (seq)popcount(trailing(P, n - npre + i, n) ^ leading(m, n - npre + i)) << i * MAX_N_BITS;
        for(int i = 0; i < nsuf; i++)
            s |= (seq)popcount(leading(P, mid - 1 - i) ^ trailing(m, mid - 1 - i, mid)) << (npre + 1 + i) * MAX_N_BITS;
        for(seq a: pre)
            S[(s + a) & mask].insert(P | (s + a) << n);
    }
}

uint64_t f(int n) {
    if (n >= 1 << MAX_N_BITS) {
        std::cerr << "n too big";
        exit(1);
    }
    int tlen = 2*n - 1;
    int mid = n;
    int npre = (tlen - mid) / 2;
    if(n>6) --npre;
    int nsuf = tlen - npre - mid;
    seqset preset;
    auto sufs = suffixes(n, nsuf, npre + 1);
    std::unordered_map<seq, std::unordered_set<uint64_t>> premid;
    for(bitvec P = 0; P < maxP(n); P++) {
        prefixes(n, npre, P, preset);
        mids(n, npre, nsuf, mid, P, premid, preset);
    }
    uint64_t ans = 0;
    using counter = uint8_t;
    vector<counter> found((size_t)1 << nsuf * MAX_N_BITS);
    counter iz = 0;
    for(auto& z: premid) {
        ++iz;
        if(!iz) {
            memset(&found[0], 0, found.size() * sizeof(counter));
            ++iz;
        }
        for(auto& pair: z.second) {
            seq s = pair >> n;
            uint64_t count = 0;
            bitvec P = pair & (maxP(n) - 1);
            for(seq t: sufs[P]) {
                seq suff = (s + t) >> (npre + 1) * MAX_N_BITS;
                if (found[suff] != iz) {
                    ++count;
                    found[suff] = iz;
                }
            }
            int middle = int(s >> npre * MAX_N_BITS) & ~(~0U << MAX_N_BITS);
            ans += count << (middle * 2 != n);
        }
    }

    return ans;
}

int main() {
    for (int i = 1; ; i++)
        std::cout << i << ' ' << f(i) << std::endl;
}

```

# Answer
> 5 votes
## Haskell, score 9

```
import Data.Bits
import Data.List
import qualified Data.IntSet as S

main = mapM_ (print . S.size . S.fromList . hd) [1..9]

hd :: Int -> [Int]
hd n = [foldl' (\s e->s*m+e) 0 [popCount $ xor p (shiftR t i .&. m)|i<-[(0::Int)..n-1]] | let m=2^n-1,p<-[(0::Int)..2^n-1],t<-[(0::Int)..2^(2*n-1)-1]]

```

Compile with `-O3`. It takes 6min35s on my 6 year old laptop hardware to run up to `n=9`, so maybe it's under 5min on the reference hardware.

```
> time ./113785
2
9
48
297
2040
15425
125232
1070553
9530752

real  6m35.763s
user  6m27.690s
sys   0m5.025s

```

# Answer
> 4 votes
## JavaScript, score 10

```
findHamming = m => {
    if (m < 2) return 2;
    let popcnt = x => x && (x & 1) + popcnt(x >> 1);
    let a = [...Array(1 << m)].map((_,i) => popcnt(i));
    let t = 0;
    let n = (1 << m) - 1;
    for (let c = 0; c <= m; c++) {
        for (let g = 0; g <= c; g++) {
            let s = new Set;
            for (let i = 1 << m; i--; ) {
                for (let j = 1 << (m - 1); j--; ) {
                    if (a[i ^ j + j] != c) continue;
                    for (let k = 1 << m - 1; k--; ) {
                        if (a[i ^ k] != g) continue;
                        let f = j << m | k;
                        let h = 0;
                        for (l = m - 1; --l; ) h = h * (m + 1) + a[i ^ f >> l & n];
                        s.add(h);
                    }
                }
            }
            t += s.size * (g < c ? 2 : 1);
        }
    }
    return t;
};
let d = Date.now(); for (let m = 1; m < 11; m++) console.log(m, findHamming(m), Date.now() - d);

```

Explanation: Calculating `n=10` is difficult because there are over two billion pairs and over 26 billion potential sequences. In order to speed things up I split the calculation up into 121 bins. Because the sequences are invariant under bitwise complement, I can assume without loss of generality that the middle bit of `T` is zero. This means that I can determine the first and last elements of the sequence independently from the the top `n-1` and bottom `n-1` bits of `T`. Each bin corresponds to a different pair of first and last elements; I then loop through all the possible sets of top and bottom bits that correspond to each bin and calculate the remaining elements of the sequence, finally counting the unique sequences for each bin. It then remains to total all 121 bins. Originally taking 45 hours, this now completed in a little under three and a half minutes on my AMD FX-8120. Edit: Thanks to @ChristianSievers for a 50% speedup. Full output:

```
1 2 0
2 9 1
3 48 1
4 297 2
5 2040 7
6 15425 45
7 125232 391
8 1070553 1844
9 9530752 15364
10 86526701 153699

```

# Answer
> 4 votes
# C++, score ~~10~~ 11

This is a translation of @Neil's answer into C++, with some simple parallelization. `n=9` completes in 0.4 seconds, `n=10` in 4.5 seconds, and `n=11` in approximately 1 minute on my 2015 Macbook Pro. Also, thanks to @ChristianSievers. Due to his comments on @Neil's answer, I noticed some additional symmetries. From the original 121 buckets (for `n=10`), to 66 buckets when accounting for reversal, I've gotten down to just 21 buckets.

```
#include <iostream>
#include <cstdint>
#include <unordered_set>
#include <thread>
#include <future>
#include <vector>

using namespace std;

constexpr uint32_t popcnt( uint32_t v ) {
    uint32_t c = v - ( ( v >> 1 ) & 0x55555555 );
    c = ( ( c >> 2 ) & 0x33333333 ) + ( c & 0x33333333 );
    c = ( ( c >> 4 ) + c ) & 0x0F0F0F0F;
    c = ( ( c >> 8 ) + c ) & 0x00FF00FF;
    c = ( ( c >> 16 ) + c ) & 0x0000FFFF;
    return c;
}

template<uint32_t N>
struct A {
    constexpr A() : arr() {
        for( auto i = 0; i != N; ++i ) {
            arr[i] = popcnt( i );
        }
    }
    uint8_t arr[N];
};

uint32_t n = ( 1 << M ) - 1;
constexpr auto a = A < 1 << M > ();

uint32_t work( uint32_t c, uint32_t g, uint32_t mult ) {
    unordered_set<uint64_t> s;
    // Empirically derived "optimal" value
    s.reserve( static_cast<uint32_t>( pow( 5, M ) ) );

    for( int i = ( 1 << M ) - 1; i >= 0; i-- ) {
        for( uint32_t j = 1 << ( M - 1 ); j--; ) {
            if( a.arr[i ^ j + j] != c ) {
                continue;
            }

            for( uint32_t k = 1 << ( M - 1 ); k--; ) {
                if( a.arr[i ^ k] != g ) {
                    continue;
                }

                uint64_t f = j << M | k;
                uint64_t h = 0;

                for( uint32_t l = M - 1; --l; ) {
                    h = h * ( M + 1 ) + a.arr[i ^ ( f >> l & n )];
                }

                s.insert( h );
            }
        }
    }

    return s.size() * mult;

}

int main() {
    auto t1 = std::chrono::high_resolution_clock::now();

    if( M == 1 ) {
        auto t2 = std::chrono::high_resolution_clock::now();
        auto seconds = chrono::duration_cast<chrono::milliseconds>( t2 - t1 ).count() / 1000.0;
        cout << M << ": " << 2 << ", " << seconds << endl;
        return 0;
    }

    uint64_t t = 0;
    vector<future<uint32_t>> my_vector;

    if( ( M & 1 ) == 0 ) {
        for( uint32_t c = 0; c <= M / 2; ++c ) {
            for( uint32_t g = c; g <= M / 2; ++g ) {
                uint32_t mult = 8;

                if( c == M / 2 && g == M / 2 ) {
                    mult = 1;
                } else if( g == c || g == M / 2 ) {
                    mult = 4;
                }

                my_vector.push_back( async( work, c, g, mult ) );
            }

        }

        for( auto && f : my_vector ) {
            t += f.get();
        }

    } else {
        for( uint32_t c = 0; c <= ( M - 1 ) / 2; ++c ) {
            for( uint32_t g = c; g <= M - c; ++g ) {
                uint32_t mult = 4;

                if( g == c || g + c == M ) {
                    mult = 2;
                }

                my_vector.push_back( async( work, c, g, mult ) );
            }

        }

        for( auto && f : my_vector ) {
            t += f.get();
        }

    }

    auto t2 = std::chrono::high_resolution_clock::now();
    auto seconds = chrono::duration_cast<chrono::milliseconds>( t2 - t1 ).count() / 1000.0;
    cout << M << ": " << t << ", " << seconds << endl;
    return 0;
}

```

Use the following script to execute the code:

```
#!/usr/bin/env bash

for i in {1..10}
do
    clang++ -std=c++14 -march=native -mtune=native -Ofast -fno-exceptions -DM=$i hamming3.cpp -o hamming
    ./hamming
done

```

The output was as follows: (The format is `M: result, seconds`)

```
1: 2, 0
2: 9, 0
3: 48, 0
4: 297, 0
5: 2040, 0
6: 15425, 0.001
7: 125232, 0.004
8: 1070553, 0.029
9: 9530752, 0.419
10: 86526701, 4.459
11: 800164636, 58.865

```

`n=12` took 42 minutes to calculate on a single thread, and gave a result of 7368225813.

# Answer
> 2 votes
# JavaScript 2,9,48,297,2040,15425,125232,1070553,9530752

Run in console:

```
console.time("test");
h=(w,x,y,z)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal*Math.pow(w+1,z)};
sum=(x,y)=>x+y;
for(input=1;input<10;input++){
  hammings=new Array(Math.pow(input+1,input));
  for(i=1<<(input-1);i<1<<input;i++){
    for(j=0;j<1<<(2*input);j++){
      hamming=0;
      for(k=0;k<input;k++){
        hamming+=(h(input,(j>>k)%(1<<input),i,k));
      }
      hammings[hamming]=1;
    }
  }
  console.log(hammings.reduce(sum));
}
console.timeEnd("test");

```

Try it online!

Or as a Stack Snippet:

```
h=(w,x,y,z)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal*Math.pow(w+1,z)};

function findHamming() {
  console.time("test");
  input = parseInt(document.getElementById("input").value);
  hammings=new Array(Math.pow(input+1,input));
  for(i=1<<(input-1);i<1<<input;i++){
    for(j=0;j<1<<(2*input);j++){
      hamming=0;
      for(k=0;k<input;k++){
        hamming+=(h(input,(j>>k)%(1<<input),i,k));
      }
      hammings[hamming]=1;
    }
  }
  document.getElementById("output").innerHTML = hammings.reduce((x,y)=>x+y);
  console.timeEnd("test");
}
```

```
<input type="text" id="input" value="6">
<button onclick="findHamming()"> Run </button>
<pre id="output">
```

The code preinitializes the array to make adding 1s to the array much faster

The code finds all the hamming distance sequences and treating them as numbers base (input+1), uses them to place 1s in an array. As a result, this generates an array with the n 1s where n is the number of unique hamming distance sequences. Finally, the number of 1s is counted using array.reduce() to sum all of the values in the array.

This code will not be able to run for input of 10 as it hits memory limits

This code runs in O(2^2n) time because that's how many elements it generates.

---
Tags: sequence, combinatorics, fastest-code, binary
---


title: Create an ASCII art unjumble!

text:
# Question
Title: Create an ASCII art unjumble!
Given a string of ASCII art like such (This isn't ASCII art but it will do for the example):

```
abc
d e
fgh

```

Jumble it as if it was being displayed on a screen with one character per line, like so:

```
a
b
c
d

e
f
g
h

```

Print the result, wait one second, ±0.5 seconds before clearing the terminal and the print the same thing, but with 2 characters displayed per line instead of 1. Basically, the width of the display turns from 1 to 2.

```
ab
c
d
e
fg
h

```

Note the space after the `d`. Repeat waiting, then printing with an additional character per line until the inputted text is outputted.

If you hit the end of a line when trying to print characters, then you insert a newline and print the rest of them following this rule. For example the input:

```
abcdefg
ab

```

Would print the following when the display length is 4.

```
abcd
efg
ab

```

You can find the effect of the terminal resize here: https://repl.it/GoeU/1. Run the program, then drag the thing separating the terminal from the text editor back and forth.

**Clarification:**

Once a line appears exactly how it was inputted, you can leave that line alone for future larger character counts per line.

```
abc
ab

```

should print

```
ab
c
ab

```

when the sentence length = 2.

---

This is , so least amount of bytes wins!

Rules:

* Must print to STDOUT as the only output.
* Must clear the terminal, or create the illusion of clearing the terminal by adding 150 or so empty lines.
* Can take input through the standard methods.
* Default loopholes apply.
* Trailing stuff with the text is NOT OKAY.

This idea came to me when I was resizing a terminal with ASCII art on it. It looked interesting, so I decided to make a challenge out of it.

---

**Test cases:**

Since it would be too much work to show each step for each test case individually, I will review each answer to make sure it is valid. Make sure the answer can handle the test cases.

```
 ______   ______     __     __   __     ______      __    __     ______
/\  == \ /\  == \   /\ \   /\ "-.\ \   /\__  _\    /\ "-./  \   /\  ___\
\ \  _-/ \ \  __<   \ \ \  \ \ \-.  \  \/_/\ \/    \ \ \-./\ \  \ \  __\
 \ \_\    \ \_\ \_\  \ \_\  \ \_\\"\_\    \ \_\     \ \_\ \ \_\  \ \_____\
  \/_/     \/_/ /_/   \/_/   \/_/ \/_/     \/_/      \/_/  \/_/   \/_____/

```

This pastebin.

```
                        __/\__
                        \    /
                  __/\__/    \__/\__
                  \                /
                  /_              _\
                    \            /
      __/\__      __/            \__      __/\__
      \    /      \                /      \    /
__/\__/    \__/\__/                \__/\__/    \__/\__

```

# Answer
# Bash (with GNU coreutils), 69 bytes

```
n=`tee x|wc -L`;for i in `seq 1 $n`;do fold -w$i x;sleep 1;clear;done

```

Saves input in temporary file `x`, then counts the longest line (GNU coreutils' `wc` has `-L` flag for this) and iterates for each console width from 1 to the longest line length. `fold`, `sleep` and `clear` does the rest of the magic.
> 2 votes

# Answer
# Python 3.6, 124 bytes

Loops over length of input string like officialaimm's solution

```
import re,time
def d(s):
 for i in range(len(s)):print(*'\n'*75,*re.split(f'(.{{1,{i+1}}})',s)[1::2],sep='\n');time.sleep(1)

```

143 bytes to only go to width of longest line a al Frxstrem's Bash answer

```
import re,time
def d(s):
 for i in range(max(map(len,s.split()))):print(*'\n'*75,*re.split(f'(.{{1,{i+1}}})', s)[1::2],sep='\n');time.sleep(.5)

```

Uses "re.split((.{1,i+1}))" to break the string into groups of characters. Because '.' doesn't match '\n', the groups don't wrap around from one line to the next. If the regex uses a capturing group, then re.split() returns a list with the matched groups at the odd indexes. These are retrieved with \[1::2\].

Uses python 3.6 f-string to make the re pattern depend on group width i.

The * in front of re.split() uses python 3.6 unpacking to turn the list into arguments to the print statement. Similarly, \*'\n'\*75, turns into 75 '\n' arguments to the print statement. With the print keyword argument sep='\n', the result is printing about 150 blank lines to clear the screen, followed by each group of characters on a separate line.
> 3 votes

# Answer
# Python 3.5 (238 233 229 225 223 222 bytes)

### \- Works fine in the windows terminal; not sure about other platforms, because of the system-specific os.system("cls") command.

### \- The string passed should be marked by \n for newlines eg: 'abc\nd efgh\n'

```
import os,time
def b(s):
 p=len(s);z=print;r=range
 for i in r(1,p):
  os.system("cls");l=0
  for j in r(p):
   z(s[j],end="");l+=1
   if(s[j]=='\n'):l=0
   if(j+1<p and l==i and s[j+1]!='\n'):z();l=0
  z();time.sleep(.5)

```
* Saved 5 bytes: removed unwanted whitespaces
* Saved 4 bytes: shorthand for len(s)
* Saved 4 bytes: Thanks to sparklepony (shorthand for print)
* saved 2 bytes: Thanks to sparklepony (shorthand for range as r and r(0,i) as range(i))
* saved 1 byte: Thanks to steve (0.5 as just .5)
> 2 votes

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