title: Together Everyone Achieves More

text:
# Question
Title: Together Everyone Achieves More
*(related: one, two, three)*

An acrostic is a style of poem/writing where the beginning character of each line, when read vertically, also produces a word or message. For example,

```
Together
Everyone
Achieves
More

```

also spells out the word `TEAM` when the first column is read vertically.

Acrostics are a subset of mesostics, where the vertical word can be anywhere in the horizontal words. For example, the `TEAM` one above could also be written as a mesostic as follows

```
   togeTher
everyonE
       Achieves
       More

```

along with several other variations.

The challenge here will be to produce an acrostic or mesostic from a given list of input words.

### Input

* A list of words in any any suitable format.
* The list will only contain words made from lowercase `[a-z]`.
* The list is guaranteed to form an acrostic or a mesostic (no need to handle bogus input).
* One of the words in the input will form the vertical word, while the rest make the horizontal words - part of the challenge here is to find the appropriate vertical word, so it *cannot* be taken separately.

### Output

* The ASCII-art acrostic or mesostic formed from the input words, written to STDOUT or returned, in any reasonable format.
* The corresponding vertical word must be capitalized (as in the examples).
* Leading spaces to get the vertical word to line up appropriately are **required**. Trailing spaces, and leading/trailing newlines are optional. *Extra* leading spaces are fine as well, so long as the words align correctly.
* If *both* an acrostic and mesostic are possible, output *only* the acrostic.
* If more than one acrostic/mesostic is possible, your code can output any or all of them.

### Rules

* Either a full program or a function are acceptable.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

### Examples

```
['together', 'team', 'everyone', 'achieves', 'more']
Together
Everyone
Achieves
More

['aaa', 'aaa', 'aaa', 'aaa']
Aaa
Aaa
Aaa
# One output, or multiple (of the same) output is allowed

['aaa', 'aaa', 'aab', 'baa']
Aaa
Aaa
Baa
# This is the only allowed output, since others would be mesostic, which are lower priority

['live', 'every', 'love', 'very', 'ohio']
Live
Ohio
Very
Every
# Note that 'live' couldn't be the vertical word since then it would be a mesostic, which is lower priority output

['cow', 'of', 'fox']
cOw
 Fox
# A shorter mesostic test case

['late', 'ballroom', 'anvil', 'to', 'head']
anviL
   bAllroom
    To
   hEad

```

# Answer
# Pyth, ~~52~~ ~~49~~ ~~47~~ 46 bytes

```
jm++*;-lsQhAd<HGr>HG4hhMDfhhShMTm.b,xNYNtdhd.p

```

Try it online.

This is probably very golfable. It prints a bunch of leading spaces.
> 2 votes

# Answer
# Brachylog, 145 bytes

```
p~c[A:B:C],Bl1,A:CcP@pz:cahgB,P:1a~@nw|lL,?:laot:" "rjg:Ljb:sa:?z:cap~c[A:B:C],Bl1,A:Cc@pz:caZ:LmgB,Zl-yM,Z:M:Lz:2az:ca~@nw
bB,?h@u:Bc
b#=,?h@u|h

```

Try it online!

(Takes half a minute, so be patient.)
> 6 votes

# Answer
# JavaScript (ES6), 255 ~~263 269 286~~

*Edit* 17 bytes saved as arbitrary number of leading spaces is allowed
*Edit2* some shuffling, 6 byte saved
*Edit3* return a list of string instead of a single string with newlines (OP comment to feersum's answer), 8 more bytes saved

For each word in the input list, I use a recursive DFS to find all possibile mesostics/acrostics. Each one is stored as an array with word and target letter position inside the word. Every result found is saved in global result array at position 1 (if it's an acrostic) or 0 if it's a mesostic.

After the complete scan for all words, I get the result at last position in array and build and return its ascii art rapresentation.

```
l=>(l.map((w,i)=>(r=(p,v,i,a)=>(l[i]='.',w[p]?l.map((v,i)=>~(j=v.search(w[p]))&&r(p+1,v,i,a|j,m[p]=[j,v])):l[p+1]?0:s[+!a]=[...m],l[i]=v))(0,w,i,m=[]),s=[]),m=s.pop(),m.map(([j,v])=>' '.repeat((l+0).length-j)+v.slice(0,j)+v[j].toUpperCase()+v.slice(j+1)))

```

*Less golfed*

```
f=l=>(
  l.map((w,i)=>
    // r: recursive DFS function
    // defined here as it uses local w variable
    (r = (p,v,i,a) => (
     l[i] = '.'
     , w[p]
     ? l.map(
       (v,i) => ~(j=v.search(w[p])) &&
                r(p+1, v, i, a|j, m[p] = [j,v])

     )
     : l[p+1] ? 0 // invalid if there are still unused words
              : s[+!a]=[...m] // a is 0 if acrostic
     , l[i] = v)
    )(0, w, i, m=[])
  , s=[]),
  m = s.pop(), // get last result
  // m.map(([j]) => o = o<j ? j : o, o=0), // find offset for alignment
  // no need to find the optimal offset as leading blanks are allowed
  m.map(([j,v]) => ' '.repeat((l+0).length-j)
                   + v.slice(0,j)
                   + v[j].toUpperCase()
                   + v.slice(j+1)
  )
)

```

**Test**

```
f=l=>(l.map((w,i)=>(r=(p,v,i,a)=>(l[i]='.',w[p]?l.map((v,i)=>~(j=v.search(w[p]))&&r(p+1,v,i,a|j,m[p]=[j,v])):l[p+1]?0:s[+!a]=[...m],l[i]=v))(0,w,i,m=[]),s=[]),m=s.pop(),m.map(([j,v])=>' '.repeat((l+0).length-j)+v.slice(0,j)+v[j].toUpperCase()+v.slice(j+1)))

console.log=x=>O.textContent+=x+'\n\n'

;[
 ['together', 'team', 'everyone', 'achieves', 'more']
,['aaa', 'aaa', 'aaa', 'aaa']
,['aaa', 'aaa', 'aab', 'baa']
,['live', 'every', 'love', 'very', 'ohio']
,['cow', 'of', 'fox']
,['late', 'ballroom', 'anvil', 'to', 'head']
].forEach(l=>console.log(f(l).join`\n`))
```

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

# Answer
# Mathematica 10.0, 139 bytes

An unnamed function returning a list of lines:

```
Sort[{q=Max[p=Min/@Position@@@({z={##2},#})],Array[" "&,q-#2]<>ToUpperCase~MapAt~##&@@@({z,p})}&@@@Permutations@Characters@#][[1,2]]&

```

Example usage:

```
In[144]:= f = Sort[{q=Max[p=Min/@Position@@@({z={##2},#})],Array[" "&,q-#2]ToUpperCase~MapAt~##&@@@({z,p})}&@@@Permutations@Characters@#][[1,2]]&;

In[145]:= f @ {"late","ballroom","anvil","to","head"} // Column

 *... several pages of warnings ...*

Out[145]= baLlroom
            Anvil
            To
           hEad

```

~~I'm looking for suggestions on better ways to do the capitalization.~~ I found a very nice function `MapAt` for capitalizing the letter in the string.
> 3 votes

# Answer
## Perl6, ~~287~~ ~~277~~ 269 bytes

```
my @w=$*IN.words;my ($q,$r)=gather for ^@w {my @v=@w.rotate($_);my \d=@v.shift;for @v.permutations {my @o=flat($_ Z d.comb).map:{$^a.index: $^b};take $_,@o if @o>>.defined.all}}.sort(*[1].sum)[0];for @$q Z @$r ->(\a,\b){say " "x($r.max -b)~a.substr(0,b)~a.substr(b).tc}

```
> 3 votes

# Answer
## Haskell, ~~214~~ ~~206~~ ~~204~~ 202 bytes

```
import Data.List
z=zipWith
h i j t|(u,v:w)<-splitAt j t=([1..sum i-j]>>" ")++u++toEnum(fromEnum v-32):w
f x=uncurry(z=<<h)$sort[(head<$>z elemIndices w l,l)|w:l<-permutations x,(True<$w)==z elem w l]!!0

```

Returns a list of space padded strings, e.g. `f ["late","ballroom","anvil","to","head"]` -\> `[" baLlroom"," Anvil"," To"," hEad"]` or more display friendly:

```
*Main> mapM_ putStrLn $ f ["late", "ballroom", "anvil", "to", "head"]
 baLlroom
   Anvil
   To
  hEad

```

`f` selects the words that are written horizontally together with a list of offsets. `h` pads each word according to the corresponding offset and inserts the uppercase letter. In detail:

```
                permutations x       -- for each permutation of the input list x
         w:l<-                       -- bind w to the first word and l to the rest
             (True<$w)==z elem w l   -- keep it if the list of other words
                                     -- containing the next letter of w
                                     -- equals (length w) times True, i.e. we have
                                     -- as many matching letters as letters in w.
                                     -- This rules out combinations shortcut by zipWith

                                     -- for all the remaining w and l make a pair
         head<$>z elemIndices w l    -- the first element of the list of list of
                                     -- indices where the letter appears in the word
                                l    -- and l itself
   sort                              -- sort the pairs (all 0 indices, i.e. acrostics
                                     -- go first)
                               !!0   -- pick the first
                                     -- now we have a pair like
                                     -- ([2,0,0,1],["ballroom","anvil","to","head"])
 uncurry(z=<<h)                      -- loop over (index,word) and
                                     -- provide the third parameter for h

 h i j t                             -- h takes the list of indices and
                                     -- an index j and a word t
       (u,v:w)<-splitAt j t          -- split the word at the index and bind
                                     --   u: part before the split
                                     --   v: letter at the split
                                     --   w: part after the split
         [1..sum i-j]>>" "           -- the spaces to pad
           ++ u                      -- followed by u
           ++ toEnum(fromEnum v-32)  -- and uppercase v
           :                         -- and w

```
> 2 votes

# Answer
# Python, 249 bytes

Probably still very golfable

```
from itertools import*;e=enumerate;lambda l:[[[' ']*(max(j for k,(j,c)in o[1:])-i)+l[k][:i]+[c.upper()]+l[k][i+1:]for k,(i,c)in o[1:]]for p in product(*[list(e(w))for w in l])for o in permutations(list(e(p)))if[c for k,(i,c)in o[1:]]==l[o[0][0]]][0]

```

Takes and returns a list of list of characters.
\- e.g. `" bAllroom"` is `[' ',' ',' ','b','A','l','l','r','o','o','m']`

Only ever returns the first result and checks in an order such that all the acrostics are checked first.

See all test cases printed in the display format on **ideone**

---

Here is a more readable functional form that does the same (except it returns the first result immediately rather than evaluating and then returning the first result):

```
from itertools import*
def f(l):
    for p in product(*[list(enumerate(w)) for w in l]):
        for o in permutations(list(enumerate(p))):
            if [c for k,(i,c) in o[1:]] == l[o[0][0]]:
                return [ [' '] * (max(j for k,(j,c) in o[1:]) - i)
                       + l[k][:i]
                       + [c.upper()]
                       + l[k][i+1:]
                       for k, (i, c) in o[1:]
                       ]

```
> 2 votes

# Answer
# Perl 6, 177 bytes

```
->\a{for first({.[0] eq[~] .[1]»[1]},map |*,[Z] map {.[0]X [X] map {.comb[(^$_,$_,$_^..* for ^.chars)]},.[1..*]},a.permutations)[1] ->$/ {say [~] " "x a.comb-$0,|$0,$1.uc,|$2}}

```

Brute-force solution.

### How it works

```
-> \a {
    for first({.[0] eq[~] .[1]»[1]},          # For the first valid candidate
            map |*, [Z]                       # among the transposed
            map {                             # lists of candidates
                .[0] X [X] map {
                    .comb[(^$_,$_,$_^..* for ^.chars)]
                }, .[1..*]
            },
            a.permutations                    # for all permutations of the input:
        )[1] ->$/ {
        say [~] " "x a.comb-$0,|$0,$1.uc,|$2  # Print the candidate as ASCII art.
    }
}

```

Each candidate looks like:

```
"of", (("c"),"o",("w")), ((),"f",("o","x"))

```

Transposing the list of lists of candidates is necessary to ensure that an acrostic, if it exists, is found before any mesostic.
> 1 votes

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


# Question
Title: The beautiful pattern drawer (Little cubes included)
# The beautiful pattern drawer

Good morning PPCG !

The other day, when I was trying to help someone on Stack Overflow, a part of his problem gave me an idea for this challenge.

First of all, check the following shape :

Where all black numbers are the index of the points in the shape and all dark-blue numbers are the index of the links between the points.

Now, given an hexadecimal number for 0x00000 to 0xFFFFF, you need to draw a shape in the console using only character space and "■" (using the character "o" is okay too).

Here are some examples where hexadecimal number is input and shape is output :

```
0xE0C25 :
■ ■ ■ ■ ■ ■ ■ ■ ■
■               ■
■               ■
■               ■
■ ■ ■ ■ ■       ■
        ■       ■
        ■       ■
        ■       ■
        ■ ■ ■ ■ ■
0xC1043 :
■ ■ ■ ■ ■ ■ ■ ■ ■
              ■
            ■
          ■
        ■
      ■
    ■
  ■
■ ■ ■ ■ ■ ■ ■ ■ ■
0xE4F27 :
■ ■ ■ ■ ■ ■ ■ ■ ■
■       ■       ■
■       ■       ■
■       ■       ■
■ ■ ■ ■ ■ ■ ■ ■ ■
■       ■       ■
■       ■       ■
■       ■       ■
■ ■ ■ ■ ■ ■ ■ ■ ■
0xF1957 :
■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■           ■ ■
■   ■       ■   ■
■     ■   ■     ■
■       ■       ■
■     ■   ■     ■
■   ■       ■   ■
■ ■           ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■
0xD0C67 :
■ ■ ■ ■ ■ ■ ■ ■ ■
  ■             ■
    ■           ■
      ■         ■
■ ■ ■ ■ ■       ■
      ■ ■       ■
    ■   ■       ■
  ■     ■       ■
■ ■ ■ ■ ■ ■ ■ ■ ■
0x95E30 :
■ ■ ■ ■ ■       ■
  ■     ■     ■ ■
    ■   ■   ■   ■
      ■ ■ ■     ■
■ ■ ■ ■ ■ ■ ■ ■ ■
        ■ ■
        ■   ■
        ■     ■
        ■       ■
0x95622 :
■ ■ ■ ■ ■       ■
  ■     ■     ■
    ■   ■   ■
      ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■
        ■
        ■
        ■
■ ■ ■ ■ ■
0xC5463 :
■ ■ ■ ■ ■ ■ ■ ■ ■
        ■     ■
        ■   ■
        ■ ■
■ ■ ■ ■ ■
      ■ ■
    ■   ■
  ■     ■
■ ■ ■ ■ ■ ■ ■ ■ ■
0xE5975 :
■ ■ ■ ■ ■ ■ ■ ■ ■
■       ■     ■ ■
■       ■   ■   ■
■       ■ ■     ■
■       ■       ■
■     ■ ■ ■     ■
■   ■   ■   ■   ■
■ ■     ■     ■ ■
■       ■ ■ ■ ■ ■
0xB5E75 :
■ ■ ■ ■ ■       ■
■ ■     ■     ■ ■
■   ■   ■   ■   ■
■     ■ ■ ■     ■
■ ■ ■ ■ ■ ■ ■ ■ ■
      ■ ■ ■     ■
    ■   ■   ■   ■
  ■     ■     ■ ■
■       ■ ■ ■ ■ ■
0xF4C75 :
■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■     ■       ■
■   ■   ■       ■
■     ■ ■       ■
■ ■ ■ ■ ■       ■
      ■ ■ ■     ■
    ■   ■   ■   ■
  ■     ■     ■ ■
■       ■ ■ ■ ■ ■
0xF5D75 :
■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■     ■     ■ ■
■   ■   ■   ■   ■
■     ■ ■ ■     ■
■ ■ ■ ■ ■       ■
■     ■ ■ ■     ■
■   ■   ■   ■   ■
■ ■     ■     ■ ■
■       ■ ■ ■ ■ ■

```

Here are some explanation about how it works :

```
0xFFFFF(16) = 1111 1111 1111 1111 1111(2)

```

You here have 20 bits, each bit says whether a link exists or not.

Index of the Most Significant Bit (MSB) is 0 (picture reference) or the Less Significant Bit (LSB) is 19 (picture reference again).

Here's how it works for the first shape given as example :

```
0xE0C25(16) = 1110 0000 1100 0010 0101(2)

```

Meaning you'll have the following existing links : 0,1,2,8,9,14,17,19.

If you highlight the lines on the reference picture with those numbers, it will give you this shape :

```
■ ■ ■ ■ ■ ■ ■ ■ ■
■               ■
■               ■
■               ■
■ ■ ■ ■ ■       ■
        ■       ■
        ■       ■
        ■       ■
        ■ ■ ■ ■ ■

```

Here is a simple and ungolfed Python implementation if you need more help :

```
patterns = [
  0xE0C25, 0xC1043, 0xE4F27, 0xF1957,
  0xD0C67, 0x95E30, 0x95622, 0xC5463,
  0xE5975, 0xB5E75, 0xF4C75, 0xF5D75
]

def printIfTrue(condition, text = "■ "):
  if condition:
    print(text, end="")
  else:
    print(" "*len(text), end="")

def orOnList(cube, indexes):
  return (sum([cube[i] for i in indexes]) > 0)

def printPattern(pattern):
  cube = [True if n == "1" else False for n in str(bin(pattern))[2::]]
  for y in range(9):
    if y == 0: printIfTrue(orOnList(cube, [0, 2, 3]))
    if y == 4: printIfTrue(orOnList(cube, [2, 4, 9, 11, 12]))
    if y == 8: printIfTrue(orOnList(cube, [11, 13, 18]))
    if y in [0, 4, 8]:
      printIfTrue(cube[int((y / 4) + (y * 2))], "■ ■ ■ ")
      if y == 0: printIfTrue(orOnList(cube, [0, 1, 4, 5, 6]))
      if y == 4: printIfTrue(orOnList(cube, [3, 5, 7, 9, 10, 13, 14, 15]))
      if y == 8: printIfTrue(orOnList(cube, [12, 14, 16, 18, 19]))
      printIfTrue(cube[int((y / 4) + (y * 2)) + 1], "■ ■ ■ ")
    elif y in [1, 5]:
      for i in range(7):
        if i in [2, 5]:
          print(" ", end=" ")
        printIfTrue(cube[y * 2 + (1 - (y % 5)) + i])
    elif y in [2, 6]:
      for i in range(5):
        if i in [1, 2, 3, 4]:
          print(" ", end=" ")
        if i in [1, 3]:
          if i == 1 and y == 2:
            printIfTrue(orOnList(cube, [3, 4]))
          elif i == 3 and y == 2:
            printIfTrue(orOnList(cube, [6, 7]))
          if i == 1 and y == 6:
            printIfTrue(orOnList(cube, [12, 13]))
          elif i == 3 and y == 6:
            printIfTrue(orOnList(cube, [15, 16]))
        else:
          printIfTrue(cube[(y * 2 - (1 if y == 6 else 2)) + i + int(i / 4 * 2)])
    elif y in [3, 7]:
      for i in range(7):
        if i in [2, 5]:
          print("  ", end="")
        ri, swap = (y * 2 - 2) + (1 - (y % 5)) + i, [[3, 6, 12, 15], [4, 7, 13, 16]]
        if ri in swap[0]: ri = swap[1][swap[0].index(ri)]
        elif ri in swap[1]: ri = swap[0][swap[1].index(ri)]
        printIfTrue(cube[ri])
    if y == 0: printIfTrue(orOnList(cube, [1, 7, 8]))
    if y == 4: printIfTrue(orOnList(cube, [6, 8, 10, 16, 17]))
    if y == 8: printIfTrue(orOnList(cube, [15, 17, 19]))
    print()

for pattern in patterns:
  printPattern(pattern)

```

Of course it's not perfect and it's pretty long for what it should do, and that's the exact reason why you're here !

Making this program ridiculously short :)

This is code-golf, so shortest answer wins !

# Answer
> 8 votes
## JavaScript (ES6), ~~202~~ ~~188~~ 187 bytes

```
let f =

n=>`0${x=',16,-54,21,-26,21,21,-26,21,166'}${x},16`.split`,`.map((d,i)=>(k-=d,n)>>i&1&&[..."ooooo"].map(c=>g[p-=(k&3||9)^8]=c,p=k>>2),g=[...(' '.repeat(9)+`
`).repeat(9)],k=356)&&g.join``

console.log(f(0xE0C25))
console.log(f(0xC1043))
console.log(f(0xE4F27))
console.log(f(0xF1957))
```

### How it works

```
n =>                                                 // given 'n':
  `0${x = ',16,-54,21,-26,21,21,-26,21,166'}${x},16` // build the list of delta values
  .split`,`.map((d, i) =>                            // split the list and iterate
    (k -= d, n) >> i & 1 &&                          // update 'k', test the i-th bit of 'n'
    [..."ooooo"].map(c =>                            // if the bit is set, iterate 5 times:
      g[                                             //
        p -= (k & 3 || 9) ^ 8                        // compute the direction and update 'p'
      ] = c,                                         // write a 'o' at this position
      p = k >> 2                                     // initial value of 'p'
    ),                                               //
    g = [...(' '.repeat(9) + `\n`).repeat(9)],       // initialization of the 'g' array
    k = 356                                          // initial value of 'k'
  )                                                  //
  && g.join``                                        // yield the final string

```

We work on a grid `g` of 9 rows of 10 characters. The grid is initially filled with spaces, with a LineFeed every 10th character.

Each segment is defined by a starting position and a direction.

Directions are encoded as follow:

```
ID | Dir.| Offset
---|-----|-------
 0 |  W  |  -1        Offset encoding formula:
 1 | NE  |  -9        -((ID || 9) ^ 8)
 2 |  N  |  -10
 3 | NW  |  -11

```

Each segment is encoded as an integer:

* the direction is stored in bits #0 and #1
* the starting position is stored in bits #2 to #8

For instance, segment #3 starts at position 55 and uses the 3rd direction. Therefore, it's encoded as `(55 << 2) | 3 == 223`.

Below is the resulting list of integers, from segment #19 to segment #0:

```
356,340,394,373,399,378,357,383,362,196,180,234,213,239,218,197,223,202,36,20

```

Once delta-encoded, starting at 356, it becomes:

```
0,16,-54,21,-26,21,21,-26,21,166,16,-54,21,-26,21,21,-26,21,166,16

```

Which is finally encoded as:

```
`0${x=',16,-54,21,-26,21,21,-26,21,166'}${x},16`

```

# Answer
> 5 votes
# Python 3, 289 bytes

```
def f(n):
 for r in range(9):print(*(" o"[any(n&1<<ord(c)-97for c in"trq|t|t|t|tspon|s|s|s|sml|r|q||p|o|n||m|l|r||qp||o||nm||l|r|p||q|o|m||n|l|rpkih|k|k|k|qomkjgfe|j|j|j|nljdc|i|h||g|f|e||d|c|i||hg||f||ed||c|i|g||h|f|d||e|c|igb|b|b|b|hfdba|a|a|a|eca".split("|")[r*9+c])]for c in range(9)))

```

Nothing smart, just hardcoding.

# Answer
> 3 votes
# Ruby, 116 bytes

```
->n{s=[' '*17]*9*$/
20.times{|i|j=i%9
n>>19-i&1>0&&5.times{|k|s[i/9*72+(j>1?~-j/3*8+k*18:j*16)+k*(2--j%3*2)]=?O}}
s}

```

This relies on a couple of patterns I observed. Firstly, the pattern repeats every 9 lines. Secondly, if the start points of the horizontal lines are chosen appropriately, the x directions cycle continuously through right, left, straight.

**Ungolfed in test program**

```
f=->n{
   s=[' '*17]*9*$/                    #Setup a string of 9 newline separated lines of 17 spaces.
   20.times{|i|                       #For each of the 20 bits..
     j=i%9                            #The pattern repeats every 9 bits.
     n>>19-i&1>0&&                    #If the relevant bit is set,
     5.times{|k|                      #draw each of the 5 points on the relevant line.
       s[i/9*72+                      #There are 9 lines starting on each row. Row y=0 starts at 0 in the string, row y=1 at 72, etc.
       (j>1?~-j/3*8+k*18:j*16)+       #~-j=j-1. For j=2..8, the starting x coordinates are (0,0,1,1,1,2,2)*8. For j=0 and 1 starting x coordinates are 0 and 16.
       k*(2--j%3*2)                   #From the starting points, draw the lines right,left,straight. Down movement if applicable is given by conditional k*18 above.
       ]=?O                           #Having described the correct index to modify, overwrite it with a O character.
     }
   }
s}                                    #Return the string.

[0xE0C25, 0xC1043, 0xE4F27, 0xF1957,
  0xD0C67, 0x95E30, 0x95622, 0xC5463,
  0xE5975, 0xB5E75, 0xF4C75, 0xF5D75].map{|m|puts f[m],'---------'}

```

I believe there is a 112 byte solution using a 20-character string and some decoding to define the parameters of the 20 lines. I will try this later if I have time.

# Answer
> 2 votes
# PHP, ~~142~~ ~~150~~ 149 bytes

```
for($r="";$c=ord(",(NMKJIGFHDjigfecbd`"[$i]);)if(hexdec($argv[1])>>$i++&1)for($p=96^$c&~$k=3;$k++<8;$p+=7+($c&3?:-6))$r[$p]=o;echo chunk_split($r,9);

```

prints the shape as far as needed; i.e. if the lower part is empty, it will be cut.
Run with `php -nr '<code>' <input>`. Do not prefix input

**Test it online**

Add 11 bytes for no cutting: Insert `,$r[80]=" "` after `$r=""`.

**encoding explained**

Every line can be described with a starting point and one of four directions.
Drawing on a 9x9 grid, the starting position ranges from `0,0` to `8,4`; or, combined, from `0` to `8*9+4=76`. Luckily, all starting points `[0,4,8,36,40,44,72,76]` are divisible by 4; so the direction code `[0..3]` can be squeezed into bits 0 and 1 -\> no shifting needed at all.

For an easy calculation of the cursor movement, `0` is taken for east (only direction with no vertical movement) and `[1,2,3]` for south-west, south, south-east, where the offset is `9` (for vertical movement) plus `[-1,0,1]` -\> `[8,9,10]` -\> `delta=code?code+7:1`.

The direction for the first and last lines being east, that results in codes ranging from 0 to 76 `[0+0,4+0,0+2,0+3,4+1,4+2,4+3,8+1,8+2,...,44+1,44+2,72+0,76+0]`; and bitwise xor 96 on each value results in printable and unproblematic ascii codes `[96,100,98,99,101,102,103,105,106,68, 72,70,71,73,74,75,77,78,40,44]` -\>  ``dbcefgijDHFGIJKMN(,`. The code uses the LSB for bit 0, while line 0 corresponds to the MSB, so the string has to be reversed. Finito.

**breakdown**

```
for($r="";                  // init result string, loop through line codes
    $c=ord(",(NMKJIGFHDjigfecbd`"[$i]);)
    if(hexdec($argv[1])>>$i++&1)// if bit $i is set, draw line 19-$i:
        for($p=96^$c&~$k=3          // init $k to 3, init cursor to value&~3
            ;$k++<8;                // loop 5 times
            $p+=7+($c&3?:-6)            // 2. map [0,1,2,3] to [1,8,9,10], move cursor
        )
            $r[$p]=o;                   // 1. plot
echo chunk_split($r,9);     // insert a linebreak every 9 characters, print

```

**some golfing explained**

* Since `^96` has no effect on the lower two bits, it can be ignored when extracting the direction; so there is no need to store the value in a variable, which saves 5 bytes on the cursor init.
* Using `~3` instead of `124` saves one byte and allows the next golfing:
* Initializing the looping counter `$k=3` inside the `$p` assignment saves two bytes
and it doesn´t hurt the pre-condition (since the upper value still has one digit).
* Using a string for the result has the shortest initialization and plotting possible: When a character is set beyond the end of a string, PHP implicitly sets the missing characters to space. And `chunk_split` is the shortest way to insert the linebreaks.
I don´t even want to know how much more anything else would take.
* `7+($c&3?:-6)` is one byte shorter than `$c&3?$c%4+7:1`.
* Added `hexdec()` (8 bytes) to satisfy the input restriction.

# Answer
> 2 votes
## JavaScript, ~~184~~ ~~183~~ ~~178~~ ~~168~~ 167 bytes

```
f=
n=>[...`<>K[LM]NO\\^k{lm}no|~`].map((e,i)=>n>>i&1&&[0,2,4,6,8].map(i=>a[(e&102)*4+(e&17||15)*i]=`o`,e=~e.charCodeAt()),a=[...(` `.repeat(31)+`
`).repeat(9)])&&a.join``
```

```
<input oninput=o.textContent=f(+this.value)><pre id=o>
```

Was originally 206 bytes but @Arnauld's answer inspired me to investigate a one-dimensional array solution. Edit: Saved 1 byte thanks to @edc65. Saved ~~5~~ 15 bytes thanks to @Arnauld. Saved a further byte by tweaking the choice of characters.

# Answer
> 1 votes
## Batch, 491 bytes

```
@set n=%1
@for %%i in ("720896 524288 524288 524288 843776 262144 262144 262144 268288" "131072 65536 0 32768 16384 8192 0 4096 2048" "131072 0 98304 0 16384 0 12288 0 2048" "131072 32768 0 65536 16384 4096 0 8192 2048" "165248 1024 1024 1024 89312 512 512 512 10764" "256 128 0 64 32 16 0 8 4" "256 0 192 0 32 0 24 0 4" "256 64 0 128 32 8 0 16 4" "322 2 2 2 171 1 1 1 17")do @set s=&(for %%j in (%%~i)do @set/am=%1^&%%j&call:c)&call echo(%%s%%
:c
@if %m%==0 (set s=%s%  )else set s=%s%o

```

Note: The last line ends with a space. Putting an `if` conditional with a variable inside a `for` loop is beyond batch so that needs its own subroutine. Since it does nothing visible I fall through into it to exit. The `~` unquotes the strings in the outer loop allowing the inner loop to loop over the numbers. The numbers are simply the bitmasks for all the places where `o`s should be drawn.

# Answer
> 1 votes
# C, 267 262 260 256 characters

Counting escapes as 1 character

```
void f(int i){char*k="\0\x1\x2\x3\x4\x4\x5\x6\x7\x8\0\x9\x12\x1b\x24\0\xa\x14\x1e\x28\x4\xc\x14\x1c\x2d\x4\xd\x16\x1f\x28\x4\xe\x18\x22\x2c\x8\x10\x18\x20\x28\x8\x11\x1a\x23\x2c\x24\x25\x26\x27\x28\x28\x29\x2a\x2b\x2c\x24\x2d\x36\x3f\x48\x24\x2e\x38\x42\x4c\x28\x30\x38\x40\x48\x28\x31\x3a\x43\x4c\x28\x31\x3a\x43\x4c\x28\x32\x3c\x46\x50\x2c\x35\x3e\x47\x50\x48\x49\x4a\x4b\x4c\x4c\x4d\x4e\x4f\x50";for(int n=0,s,l;n<81;!(++n%9)&&putchar(10))for(s=l=0;s<20;!(++l%5||++s^20)&&putchar(32))if(i<<s&1<<19&&k[l]==n&&putchar(111))break;}

```

k is a lookup referring to which boxes to put an 'o' in.

Try it online!

# Answer
> 1 votes
# Befunge, 468 bytes

```
~:85+`!#v_86*-:9`7*-48*%\82**+
3%2:/2\<$v0%2:/2\*g02*!g03%2:/2\*!+4g07%2:/2\*g02*!-8g06%2:/2\*g02*!-4g0
g!*20g*^00>50g*\2/:2%00g8-!*40g*\2/:2%30g8-!*20g*\2/:2%60g66+-!*\2/:2%70
`\5:p00:<g^*!-8g00%2:\-10:\p07-g00:p06+g00:p05`3:p04`\5:p03:<0\p02`3:p01
#o 8`#@_^4>*50g*\2/2%00g!*40g*0\>:#<1#\+_$!1+4g,48*,\1+:8`!#^_55+,$\1+:
g03%2:/2<-^!g00%2:/2\*g01*!g03%2:/2\*g01*!g07%2:/2\*!-4g06%2:/2\*g01*!-4
70g4-!*\^>!*50g*\2/:2%00g4-!*40g*\2/:2%30g8-!*10g*\2/:2%60g8-!*10g*\2/:2%

```

Try it online!

The first line reads a string from stdin, evaluating it as a hexadecimal number. The rest of the code is essentially just a double loop over the x/y coordinates of the grid, with a massive boolean calculation determining whether an `o` should be output for each location.

There's basically a separate condition for each of the 20 grid points, for example (the first four):

```
(y==0) * (x<5) * bit0
(y==0) * (x>3) * bit1
(x==0) * (y<5) * bit2
(x==y) * (y<5) * bit3

```

And then once we've calculated all 20 of them, we OR the lot together, and if that result is true, we output a `o`, otherwise we output a space.

Befunge doesn't have anything in the way of bit manipulation operations, so to extract the bits from the input, we're just repeatedly evalating `n%2` and then `n/=2` as we make our way through the 20 condition calculations.

---
Tags: code-golf, ascii-art, grid, base-conversion
---


title: Golf Me A Bubble Sort

text:
# Question
Title: Golf Me A Bubble Sort
Your task is to create a program that performs a bubble sort on a given array until it is sorted.

---

## Algorithm

In order to qualify as a bubble sort, the program must operate as follows:

* Each pass goes through the array, looks at every two adjacent elements in turn, and potentially swaps them.
* Each pass goes through the array in the same direction and without gaps. There are no partial passes - each pass must go through the whole array.
* The program must never compare or swap array elements that aren't adjacent.
* A sufficient (and finite) number of passes must be performed, such that the output array is guaranteed to be sorted. (E.g. you can safely stop if there was a whole pass without any swaps, or after `len(array)` passes have been made, etc.)

---

## Rules

1. You must provide a sufficient explanation for how your answer does a bubble sort.
2. You may *not* use built-in or standard library sorting algorithms. You must make your own code.
3. Your program should take an array of numbers as input and output them in the correct order.
    * Input: `10 5 9 2 . . . (and so on)`
    * The program should *always* output the sorted array.
    * Output can be an array returned by the program when run, or it can modify the input array in-place.
    * Output can also be the correctly ordered values separated by whitespace.
4. Speed does not matter as much as if the program functions.

---

## Test Cases

* `10 5 9 2 1 6 8 3 7 4` (you can format it differently depending on your language)
* `1 2 5 4 3`

---

This is , so the shortest answer in bytes wins.

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

```
f(a:b:c)=min a b:f(max a b:c)
f x=x
foldr(\_->f)=<<id

```

Usage example: `foldr(\_->f)=<<id $ [3,1,6,4,3,8,3,1,1,2]` -\> `[1,1,1,2,3,3,3,4,6,8]`. Try it online!.

How it works: `f` does one iteration by keeping the minimum of the first two elements and appending a recursive call with the maximum of the first two elements and all the other elements. It stops when there are less than two elements in the list. The main function calls `f` `length <input>` times by iterating over the input list via `fold` but ignoring the elements.

# Answer
> 1 votes
# Octave, ~~77~~ 75 bytes

```
i=1;while any(diff(x)<0),i=mod(i,rows(x)-1)+1;x(i:i+1)=sort(x(i:i+1));end,x

```

A crude first attempt. I'm sure I'll be able to golf this a bit. Takes input as a row vector.

**Explanation:**

```
i=1;                           % Initialize iterator to 1;
    while                      % Start loop
              diff(x)     % diff(x) creates a vector with the difference between
                          % adjacent elements

              diff(x)<0   % Checks if there are less than 0 (unsorted vector)

          any(diff(x)<0)  % True if there's at least one negative difference

i=mod(i,rows(x)-1)+1      % i++, but loop around if it's equal to the number of rows
x(i:i+1)=sort(x(i:i+1);   % Take two adjacent elements, sort them and put them back in
end,x                     % End loop and display result

```

# Answer
> 1 votes
# Perl 6, 44 bytes

```
{.[*]=.[1,0]if [<] $_ for |(.[1..*]Z$_)xx$_}

```

Takes an array of numbers, and modifies it in-place (so that it is sorted after calling the lambda).

### How it works

```
{                                          }  # A lambda taking one argument.
                                              # e.g [a,b,c]
                            .[1..*]Z$_        # Zip it with itself offset by one.
                                              # e.g. (b,a),(c,b),(d,c)
                          |(          )xx$_   # Repeat this by the input's length.
                                              # e.g. (b,a),(c,b),(d,c),(b,a),(c,b),(d,c),(b,a),(c,b),(d,c)
                      for                     # For each of those pairs:
            if [<] $_                         # If its 1st element is less than the 2nd:
 .[*]=.[1,0]                                  # Swap their values.

```

This works because the elements of a Perl 6 array are actually mutable item containers (akin to pointers in C except that they hide themselves well). So in the list we iterate over, each pair consists of two item containers from the array.

# Answer
> 1 votes
## SmileBASIC, 79 bytes

```
DEF S A
FOR Z=0TO I
FOR I=1TO LEN(A)-1SWAP A[I-(A[I-1]>A[I])],A[I]NEXT
NEXT
END

```

This one is pretty simple. It just runs `LEN(A)` (actually LEN(A)+2 just in case) iterations of bubble sort, which is guaranteed to sort the array.

The only slightly interesting part is how I avoided using IF/THEN: `SWAP A[I-(A[I-1]>A[I])],A[I]`. If the two adjacent values are in the wrong positions (if `(A[I-1]>A[I])` is true), it swaps `A[I-1]` with `A[I]`, otherwise it swaps `A[I-0]` with `A[I]`, which does nothing.

# Answer
> 1 votes
**Javascript ~~98~~, ~~97~~, 91 Bytes**

edit: removed unneeded semicolon and fixed broken code. Also moved some variable declarations and increments around.

```
x=>{for(h=1;h--;){for(i=d=0;d<x.length;i=d++){if(x[i]>x[d]){y=x[i];x[i]=x[d];x[d]=y;h=1}}}}

```

Ungolfed:

```
x=>{
    for(h=1;h--;){
        for(i=d=0;d<x.length;i=d++){
            if(x[i]>x[d]){
                y=x[i];
                x[i]=x[d];
                x[d]=y;
                h=1
            }
        }
    }
}

```

Explanation:

```
x=>{
    for(h=1;h--;){  //set the change tracker, h, to true. On the start of each loop, evaluate it, then decrement it.
                    //If true, sets to false. If false, exits the loop and sets it to -1.

        for(i=d=0;d<x.length;i=d++){ //i and d are our array indexers. They're both set to null for the first loop, then on subsequent loops i is set to d, then d is incremented.
                                     // Therefore, on each subsequent loop, d will be 1 more than i.

            if(x[i]>x[d]){ //if the previous value, i, is greater than the current value, d, switch their places using the temporary variable y.
                y=x[i];
                x[i]=x[d];
                x[d]=y;
                h=1     //set the change tracker to true.
            }
        }
    }
}

```

It's rather simple and embarrassingly long, so any suggestions are greatly appreciated!

# Answer
> 0 votes
# Python 2, 104 bytes

Straightforward implementation.

```
L=input()
while L!=sorted(L):
 for i in range(len(L)-1):
    if L[i]>L[i+1]:L[i],L[i+1]=L[i+1],L[i]
print L

```

**Try it online**

While not sorted, for each index in the list, swap with next item if greater.

---
Tags: code-golf, sorting, algorithm
---


title: Letter Interpolate

text:
# Question
Title: Letter Interpolate
This is a fairly simple challenge. Given a lower-case word, you must "interpolate" between letters. Here's some examples to hopefully clarify this:

Input: `test` Output: `tsrqponmlkjihefghijklmnopqrst`

Between letters you must add, in alphabetical order, the letters between those two letters. So if you have `ad`, you must output `abcd`. If you are given `da`, you must output `dcba`.

If the letters are next to each other in the alphabet, nothing happens:

Input: `hi` Output: `hi`

Assume the input contains a lower-case word consisting of ASCII letters only; no spaces, symbols, etc. The input is also never empty.

Lowest byte count wins; this is code-golf. If you have any questions please comment.

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
ÇŸçJ

```

Try it online!

Honestly? I don't know why this works.

```
Ç    # Push characters as ASCII.
 Ÿ   # Supposed to be range from [a, .., b], apparently vectorizes on lists...
  çJ # Turn back into characters, join stack.

```

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


title: Bubble sorting in progress

text:
# Question
Title: Bubble sorting in progress
Create a function or program that takes two inputs:

* A list of integers that shall be sorted (less than 20 elements)
* A positive integer, `N`, saying how many comparisons you should take

The function shall stop, and output the resulting list of integers after `N` comparisons. If the list is fully sorted before `N` comparisons are made, then the sorted list should be outputted.

---

The Bubble sort algorithm is well known, and I guess most people know it. The following Pseudo-code and animation (both from the linked Wikipedia-article) should provide the necessary details:

```
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

```

The animation below shows the progress:

An example (taken directly from the linked Wikipedia article) shows the steps when sorting the list: `( 5 1 4 2 8 )`:

**First Pass**

```
1: ( 5 1 4 2 8 ) ->  ( 1 5 4 2 8 ) // Here, algorithm compares the first two elements,
                                   // and swaps since 5 > 1.
2: ( 1 5 4 2 8 ) ->  ( 1 4 5 2 8 ) // Swap since 5 > 4
3: ( 1 4 5 2 8 ) ->  ( 1 4 2 5 8 ) // Swap since 5 > 2
4: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 ) // Now, since these elements are already in order
                                   // (8 > 5), algorithm does not swap them.

```

**Second Pass**

```
5: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 )
6: ( 1 4 2 5 8 ) ->  ( 1 2 4 5 8 ) // Swap since 4 > 2
7: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
8: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )

```

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

**Third Pass**

```
9: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
10:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
11:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
12:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )

```

## Test cases:

Format: `Number of comparisons (N): List after N comparisons`

```
Input list:
5  1  4  2  8
Test cases:
1: 1  5  4  2  8
2: 1  4  5  2  8
3: 1  4  2  5  8
4: 1  4  2  5  8
5: 1  4  2  5  8
6: 1  2  4  5  8
10: 1  2  4  5  8
14: 1  2  4  5  8

Input list:
0: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
Test cases:
1: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
21: -6  15  18   9  -7  -1   7  18  19  -5  19  19   5  15  -5   3  18  14  19  20
41: -6   9  -7  15  -1   7  18  18  -5  19  19   5  15  -5   3  18  14  19  19  20
60: -6  -7  -1   9   7  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
61: -6  -7  -1   7   9  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
81: -7  -6  -1   7   9  15  -5  18  18   5  15  -5   3  18  14  19  19  19  19  20
119: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
120: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
121: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
122: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
123: -7  -6  -1  -5   7   9   5  15  -5  15   3  18  14  18  18  19  19  19  19  20
201: -7  -6  -5  -1  -5   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20
221: -7  -6  -5  -5  -1   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20

```

---

* Yes, built-in Bubble sort algorithms are permitted.
* No, you can not assume only positive integers, or unique integers.
* The sorting must be in the order described above. You can't start at the end of the list

# Answer
> 2 votes
# Jelly, 25 bytes

```
ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ¥
JḊṁ¹³W¤;ç/

```

Based on my answer in J.

Try it online!

Verify number of comparisons.

## Explanation

The helper link modifies the list at index `[i-1, i]` by sorting it which produces the same result as the bubble sort comparison.

```
ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ¥  Helper link - Input: list A, index i
ḣ               Take the first i values
 ©              Save a copy of it
  ṫ-            Take the last two values
    Ṣ           Sort them
         ;      Append them to
     ®            Get the copy
      ṖṖ¤         Pop the last two values (Ṗ is pop)
          ;     Prepend it to
           ṫ      Take the last i values
            Ḋ¥    Dequeue - remove the head

JḊṁ¹³W¤;ç/  Input: list A and # of comparisons n
J           Enumerate the indices of A
 Ḋ          Dequeue - remove the head
  ṁ         Reshape it cyclically to length n
   ¹        Identity function (Just to avoid parsing rules)
       ;    Append it to
    ³         The list A
     W¤       Wrap it as an array
        ç/  Reduce from left to right using the helper link and return

```

# Answer
> 9 votes
# JavaScript (ES6), ~~102~~ ~~82~~ ~~80~~ ~~86~~ 80 bytes

*Bug fix and 1 byte saved thanks to @edc65*

```
(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")

```

Recursion ~~may not be~~ ~~is definitely not~~ is probably the best approach, but I'm sticking with a loop for now.

### Try it out:

```
f=(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")
```

```
Enter your numbers:<br>
<input id=A rows=10 value="5 1 4 2 8"><br>
Enter the number of steps:<br>
<input type="number" min=0 id=B rows=10 value="1"><br>
<button onclick="C.innerHTML=f((A.value.match(/-?\d+/g)||[]).map(Number),B.value)">Run</button><br>
<pre id=C></pre>
```

# Answer
> 7 votes
## Haskell, ~~83~~ ~~82~~ 81 bytes

```
y%x@(a:b:c)=(y++x):(y++[min a b])%(max a b:c)
y%x=[]%(y++x)
[x]!_=[x]
x!n=[]%x!!n

```

Usage example: `[5,1,4,2,8] ! 5` -\> `[1,4,2,5,8]`.

In function `%` `y` keeps track of the elements visited so far during the current pass, `x` are ones yet to examine. `a` and `b` are the next two, i.e. the candidates to swap. If we reach the end of the list, we start from the beginning: `y%x = []%(y++x)`. All steps are stored in a list where the main function picks the `n`th element.

Edit: previous versions didn't work for single element lists, luckily the new version is even shorter.

# Answer
> 5 votes
# Python 3, ~~77~~ 74 bytes

-3 bytes thanks to @Maltysen (init `j` in declaration)

```
lambda l,n,j=0:exec('j*=j<len(l)-1;l[j:j+2]=sorted(l[j:j+2]);j+=1;'*n)or l

```

Test cases at **ideone**

Uses `sorted` to do each compare and swap operation, but it is performing a bubble sort.

Sets `j=0` (the left index), then performs `n` compare and swaps of adjacent list items, resetting `j` to `0` whenever this window goes out of bounds.

The `j*=j<len(l)-1` will multiply `j` by `False` (i.e. `0`) at that point, whereas every other time it will multiply `j` by `True` (i.e. `1`).

(It will still work for an empty list too.)

# Answer
> 3 votes
## PowerShell v2+, ~~135~~ 129 bytes

```
param($a,$n)for($s=1;$s){($s=0)..($a.count-2)|%{if($a[$_]-gt$a[$_+1]){$a[$_],$a[$_+1]=$a[$_+1],$a[$_];$s=1}if(!--$n){$a;exit}}}$a

```

So. Many. Dollars.

(*Saved six bytes by realizing that this challenge doesn't include the "for free" optimization of skipping the last element(s) on each pass since that's guaranteed sorted, and instead runs through a full pass each time. This moved the `$a.count` into the `for` loop and eliminated the `$z` variable.*)

Straight up bubble sort, with one nifty spot, doing the swap in one step --
`$a[$_],$a[$_+1]=$a[$_+1],$a[$_]`

The exiting logic is handled via `if(!--$n){$a;exit}`

### Test Cases

(The array is shown as space-separated here because the default Output Field Separator for stringifying an array is a space. The stringification happens because we're concatenating with the labels `"$_ -> "`.)

```
PS C:\Tools\Scripts\golfing> 1,2,3,4,5,6,10,14|%{"$_ -> "+(.\bubble-sorting-in-progress.ps1 @(5,1,4,2,8) $_)}
1 -> 1 5 4 2 8
2 -> 1 4 5 2 8
3 -> 1 4 2 5 8
4 -> 1 4 2 5 8
5 -> 1 4 2 5 8
6 -> 1 2 4 5 8
10 -> 1 2 4 5 8
14 -> 1 2 4 5 8

PS C:\Tools\Scripts\golfing> 1,21,41,60,61,81,119,120,121,122,123,201,221|%{"$_ -> "+(.\bubble-sorting-in-progress.ps1 @(15,18,-6,18,9,-7,-1,7,19,19,-5,20,19,5,15,-5,3,18,14,19) $_)}
1 -> 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19
21 -> -6 15 18 9 -7 -1 7 18 19 -5 19 19 5 15 -5 3 18 14 19 20
41 -> -6 9 -7 15 -1 7 18 18 -5 19 19 5 15 -5 3 18 14 19 19 20
60 -> -6 -7 -1 9 7 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
61 -> -6 -7 -1 7 9 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
81 -> -7 -6 -1 7 9 15 -5 18 18 5 15 -5 3 18 14 19 19 19 19 20
119 -> -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
120 -> -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
121 -> -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
122 -> -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
123 -> -7 -6 -1 -5 7 9 5 15 -5 15 3 18 14 18 18 19 19 19 19 20
201 -> -7 -6 -5 -1 -5 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20
221 -> -7 -6 -5 -5 -1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20

```

# Answer
> 3 votes
## R, ~~132~~ ~~131~~ ~~112~~ 136 bytes

The programme receives the input as follows: first `N`, then the vector itself. For example, if you want `v = [5 1 4 2 8]` and `n = 1`, the input that goes into the `scan` is `1 5 1 4 2 8`. So in order to run this programme, you **run the first line**, *feed the numbers one by one in the console*, and **then run the rest** (this is a REPL answer).

Then the following code does the trick:

```
v=scan()
s=m=0
while(!s){s=T;for(i in 3:length(v)){m=m+1
if(m>v[1]){s=T;break}
if(v[i-1]>v[i]){v[c(i-1,i)]=v[c(i,i-1)];s=F}}}
cat(v[-1])

```

Test:

```
Input: a vector with N first and the elements to be sorted next
1 5 1 4 2 8
5 5 1 4 2 8
14 5 1 4 2 8
60 15 18 -6 18  9 -7 -1  7 19 19 -5 20 19  5 15 -5  3 18 14 19

Output:
1 5 4 2 8
1 4 2 5 8
1 2 4 5 8
-6 -7 -1  9  7 15 18 -5 18 19  5 15 -5  3 18 14 19 19 19 20

```

Update: golfed 1 byte owing to Vlo.

# Answer
> 2 votes
# Pyth, ~~34~~ 32 Bytes

```
AQVH=*<ZtlGZ=GsXJcG,Zh=hZ1ShtJ;G

```

A translation of Jonathan Allan's Python answer.

Try it here!

# Answer
> 2 votes
## JavaScript (ES6), ~~82~~ ~~80~~ 79 bytes

```
f=(a,m,n=0,_,b=a[n+1])=>1/b?m?f(a,m-1,n+1,a[n]>b?a[a[n+1]=a[n],n]=b:0):a:f(a,m)

```

Based on @ETHproduction's original answer. Edit: Saved 2 bytes thanks to @JonathanAllan. Saved 1 byte thanks to @edc65.

# Answer
> 2 votes
# , ~~62~~ 60 bytes

```
>@([:({.,(2/:~@{.}.),]}.~2+[)&.>/]|.@;<:@#@]<@|i.@[)^:(]1<#)

```

This is a verb that takes two arguments: the number of comparisons on the LHS and the list of integers on the RHS. First it checks if the length of the list if greater than one. If it isn't, it returns the list unmodified, otherwise it operates on it by performing the specified number of comparisons before returning the result.

## Usage

For the first test case, extras commands are used to format multiple input/output. The second test case is shown as single input/output.

```
   f =: >@([:({.,(2/:~@{.}.),]}.~2+[)&.>/]|.@;<:@#@]<@|i.@[)^:(]1<#)
   1 2 3 4 5 6 10 14 ([;f)"0 1 ] 5 1 4 2 8
┌──┬─────────┐
│1 │1 5 4 2 8│
├──┼─────────┤
│2 │1 4 5 2 8│
├──┼─────────┤
│3 │1 4 2 5 8│
├──┼─────────┤
│4 │1 4 2 5 8│
├──┼─────────┤
│5 │1 4 2 5 8│
├──┼─────────┤
│6 │1 2 4 5 8│
├──┼─────────┤
│10│1 2 4 5 8│
├──┼─────────┤
│14│1 2 4 5 8│
└──┴─────────┘
   1 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
   123 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
_7 _6 _1 _5 7 9 5 15 _5 15 3 18 14 18 18 19 19 19 19 20
   221 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
_7 _6 _5 _5 _1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20

```

## Explanation

It's hard to write terse code in J that uses mutability, so instead I convert the problem into reducing a list on a set of indicies. I think this code is messy so I will walkthrough the job of each phrase instead of each primitive. The first part grabs the length of the list and produces a range. Then, operate on each infix of size 2 to emulate one pass of comparisons.

```
   i. # 5 1 4 2 8
0 1 2 3 4
   2 <\ i. # 5 1 4 2 8
┌───┬───┬───┬───┐
│0 1│1 2│2 3│3 4│
└───┴───┴───┴───┘
   2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┐
│0│1│2│3│
└─┴─┴─┴─┘

```

These are the start indicies of each comparison. If 7 comparisons are being performed, reshape it to get the desired amount. J parses right to left, so its reduces right to left, like fold-right. Append the initial list and reverse it.

```
   7 $ 2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│0│1│2│
└─┴─┴─┴─┴─┴─┴─┘
   |. 5 1 4 2 8 ; 7 $ 2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┬─┬─┬─┬─────────┐
│2│1│0│3│2│1│0│5 1 4 2 8│
└─┴─┴─┴─┴─┴─┴─┴─────────┘

```

Alternatively, the range \[0, 7) can be made and each value taken modulo the length of the list minus 1 to create the same range.

```
   (<: # 5 1 4 2 8) <@| i. 7
┌─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│0│1│2│
└─┴─┴─┴─┴─┴─┴─┘

```

The last part is a verb that takes a list on the RHS and an index on the LHS which marks the start index of the comparison. Select the two elements starting at that index, sort them, and plug them back into the list and return it.

```
   > ({.,(2/:~@{.}.),]}.~2+[)&.>/ |. 5 1 4 2 8 ; 7 $ 2 <@{.\ i. # 5 1 4 2 8
1 2 4 5 8

```

# Answer
> 1 votes
# Groovy (101 Bytes)

```
{l,n->(l.size()..0).each{i->(0..i-2).each{if(l[it]>l[it+1] && n>0 && it>-1){l.swap(it,it+1)};n--}};l}

```

*EDIT: I didn't need to write my own swap closure, groovy had this built in.*
Try it here: https://groovyconsole.appspot.com/script/5104724189642752

## Example Output Trace:

```
4:[1, 5, 4, 2, 8]
3:[1, 4, 5, 2, 8]
2:[1, 4, 2, 5, 8]
1:[1, 4, 2, 5, 8]
0:[1, 4, 2, 5, 8] - Locks in the final answer.
-1:[1, 4, 2, 5, 8]
-2 (Return):[1, 4, 2, 5, 8]

```

---

# Old Implementation (122 Bytes)

```
m={l,n->s={x,y->t=l[x];l[x]=l[y];l[y]=t};((l.size()-2)..2).each{i->(0..i).each{if(l[it]>l[it+1] && n){s(it,it+1)};n--}};l}

```

Try it here: https://groovyconsole.appspot.com/script/6316871066320896

# Answer
> 1 votes
# Matlab, ~~93~~ 91 bytes

```
function l=f(l,m)
n=numel(l)-1;i=0;while n&m;i=mod(i,n)+1;m=m-1;l(i:i+1)=sort(l(i:i+1));end

```

Saves 11 bytes by omitting `if l(i)>l(i+1);l(i:i+1)=l([i+1,i])`, and instead just sort the two elements every time. Works for lists of length 1. Could save a byte or two using Octave's `m--` operator, but that's not much.

Saves two more bytes by setting `n=numel(l)-1;`, because then I can just do `while n` instead of `while n>1`, and `i=mod(i,n)+1` instead of `i=mod(i,n-1)+1`.

---

For the record, this answer was written many hours after the challenge was created.

# Answer
> 1 votes
# php, ~~148~~ 145 bytes

```
<?php for($i=2,$a=$argv;$a[1]--;$i=$i==count($a)-2?2:$i+1)if($a[$i]>$a[$i+1])list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]];echo substr(join(' ',$a),5);

```

I'm not very happy with the loop structure but I like the list switch and it does work so I'm posting it anyway. php7.1 would allow me to save at least 4 bytes.

With nicer formatting:

```
<?php
for($i=2,$a=$argv;$a[1]--;$i=$i==count($a)-2?2:$i+1)
  if($a[$i]>$a[$i+1])
    list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]];
echo substr(join(' ',$a),5);

```

Edit: Jörg Hülsermann reminded me of join, instead of implode.
note: needs to be in a file with a single character filename.

# Answer
> 1 votes
## Ruby, ~~52~~ 50 bytes

Wait... no Ruby?

```
->l,n{n.times{|a|l[s=a%~-l.size,2]=l[s,2].sort};l}

```

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


title: Holiday Headache

text:
# Question
Title: Holiday Headache
**Warning: DO NOT take medical advice from this post. If you want medical advice, go to a qualified professional.**

I have a headache. I need headache pills.

I'll tell you the last few doses I've had, and you tell me when I can have my next dose, without overdosing.

I'll give you this string: `P: 00:00, I: 02:00, P: 04:00, I: 06:00`

And you'll give me this: `Next P: 08:00, I: 10:00`

# Input:

String representing the times each medication has been taken, in the following format:

```
P: 00:00, I: 02:00, P: 04:00, I: 06:00

```

This means Paracetamol was taken at 00:00 and 04:00, and Ibuprofen was taken at 02:00 and 06:00

# Output (updated):

String with the time the next does of each medication can be taken, in the following format:

```
Next P: 08:00, I: 10:00

```
* The output order should be in the order which the medication is to be taken. - If Ibuprofen is to be taken at 09:35 and Paracetamol and 10:22, then the output should be `Next I: 09:35, P: 10:22`
* If the times for the next dose of each medication are the same, the output order doesn't matter: `Next P: 08:00, I: 08:00` OR `Next I: 08:00, P: 08:00`
* If only one medication is being taken (in the input string), then only that medication should be in the output string: `Next P: 02:00`

# Rules:

* There will only ever be two types of medication, Paracetamol 'P' and Ibuprofen 'I'.
* Paracetamol can be taken once every 4 hours, a maximum of 4 times within a 24-hour period.
* Ibuprofen can also be taken once every 4 hours, a maximum of 4 times within a 24-hour period.
* Paracetamol and Ibuprofen can be taken together, or at separate times. One doesn't count towards the dosage of the other.
* The times in the input string will always be consecutive, but may roll over midnight (23:00 -\> 03:00)
* The times in the input string will not span more than 24 hours
* Maximum of 4 times for each medication (8 max in total)
* Input will always be non-empty and contain at least one medication and one time

# Examples:

Two doses of each at two hour intervals:

`"P: 00:00, I: 02:00, P: 04:00, I: 06:00" -> "Next P: 08:00, I: 10:00"`

Single dose of Paracetamol

`"P: 22:00" -> "Next P: 02:00"`

Maximum Paracetamol dose within 24 hours, single Ibuprofen dose

`"P: 04:05, P: 08:10, P: 12:15, I: 12:30, P: 16:25" -> "Next I: 16:30, P: 04:05"`

# Test cases:

```
"I: 06:00" -> "Next I: 10:00"
"P: 22:00" -> "Next P: 02:00"
"P: 22:00, P: 02:00, I: 06:00" -> "Next P: 06:00, I: 10:00"
"P: 00:00, I: 02:00, P: 04:00, I: 06:00" -> "Next P: 08:00, I: 10:00"
"P: 04:05, P: 08:10, P: 12:15, I: 12:30, P: 16:25" -> "Next I: 16:30, P: 04:05"
"I: 06:32, P: 08:15, I: 10:44, P: 13:03" -> "Next I: 14:44, P: 17:03"
"P: 07:30, I: 07:30, P: 11:30, I: 11:30, P: 15:30, I: 15:30, I: 19:30" -> "Next P: 19:30, I: 07:30"
"I: 07:30, P: 11:30, I: 11:30, P: 15:30, I: 15:30, P: 19:30, I: 19:30" -> "Next P: 23:30, I: 07:30"
"P: 07:30, I: 07:30, P: 11:30, I: 11:30, P: 15:30, I: 15:30, P: 19:30, I: 19:30" -> "Next P: 07:30, I: 07:30" OR "Next I: 07:30, P: 07:30"

```

This is code golf, so the shortest answer int bytes wins.

# UPDATE:

The output can now be abbreviations of Paracetamol and Ibuprofen; `P` and `I`

# Answer
# JavaScript (ES6), ~~367~~ ~~362~~ ~~354~~ 358 bytes

Golfed version:

```
A=i=>i>9?""+i:"0"+i,B=(s,a=":")=>s.split(a),C=(a,b,c,d)=>[...[s,t]=B((b>3?c:d)||":"),a+` ${A(s=b>3?+s:(+s+4)%24)}:`+A(t=+t)],F=s=>{a=B(s,m=", ");for(b=c=d=e=f=p=q=0;f<a.length;g=="P:"?(b++,d=d?h:p=h):(c++,e=e?h:q=h))[g,h]=B(a[f++]," ");[i,j,k]=C("P",b,p,d),[n,o,l]=C("I",c,q,e),r=B(h)[0];return"Next "+c?b?n*60+(n<r)*1440+j<i*60+(i<r)*1440+o?l+m+k:k+m+l:l:k}

```

Ungolfed/commented:

```
// Returns a zero-padded string of the argument.
A=i=>i>9?""+i:"0"+i,

// Since we do a lot of splitting, alias it. Making the
// second argument optional (and defaulting to ':') saved
// 3 bytes
B=(s,a=":")=>s.split(a),

// Constructs a string for output, along with the time
// of the next dose, in the format [hour, minute, string].
// Arguments:               type
// a -> type (P/I)          String
// b -> amount of doses     Number
//      taken
// c -> first dose taken    String
// d -> last dose taken     String
//
// The first two values are split from the string, but
// before the array is returned, they are converted to
// integers (during the string construction).
C=(a,b,c,d)=>[...[s,t]=B((b>3?c:d)||":"),a+` ${A(s=b>3?+s:(+s+4)%24)}:`+A(t=+t)],

// Main function. Returns the time(s) for the next dose.
// Argument:                type
// s -> list of times of    String
//      and types of
//      doses taken
F=s=>{
    a=B(s,m=", "); // Split the input by comma + space,
                   // and save that string, since we
                   // need it later when constructing
                   // the output string.
    // For loop has been restructured. Original:
    // for(b=c=f=0;f<a.length;g=="P:"?(b++,d=d?h:p=h):(c++,e=e?h:q=h))
    //     [g,h]=B(a[f++]," ");
    b = 0; // P-dose counter
    c = 0; // I-dose counter
    d = 0; // Last P-dose
    e = 0; // Last I-dose
    p = 0; // First P-dose
    q = 0; // First I-dose
    for (f = 0; f < a.length; f++) {
        [g, h] = B(a[f], " ");  // g contains the type,
                                // h contains the time
        if (g == "P:") {
            b++;                // increase the counter

            if (d == 0) {   // store h in p if this is
                p = h;      // the first dose of this
            }               // type
            d = h;
        } else {
            // See the above code block for comments
            c++;

            if (e == 0) {
                q = h;
            }
            e = h;
        }
    }
    // End of restructured for loop.

    // Construct the output strings, and get the times.
    // See comments at C function.
    [i, j, k] = C("P", b, p, d);
    [n, o, l] = C("I", c, q, e);

    // Get the amount of hours of the dose taken last.
    // We use this to get the correct order of the two
    // times.
    r = B(h)[0];

    // Return statement has been restructured. Original:
    // return "Next "+c?b?n*60+(n<r)*1440+j<i*60+(i<r)*1440+o?l+m+k:k+m+l:l:k
    //==================================================
    // Start creating the output string.
    output = "Next "
    // Use the following checks to figure out what needs
    // to be part of the output and in what order.
    if (c > 0) {
        if (b > 0) {
            // Compare the times of next doses
            // P_time = (i + (i < r) * 24) * 60
            // I'm using implicit conversion of
            // booleans to numbers. If the next
            // dose is past midnight, add 1 * 24
            // to the time, so it is compared
            // correctly.
            // Then add the minutes to the number.
            P_time = i*60+(i<r)*1440+o;
            I_time = n*60+(n<r)*1440+j;

            if (I_time < P_time) {
                output += l + m + k; // I first
            } else {
                output += k + m + l; // P first
            }
        } else {
            output += l; // Just I
        }
    } else {
        output += k; // Just P
    }

    // Finally, return the output
    return output;
}

```

To use it, call F with the string as argument like so:

```
F("P: 04:00, I: 06:00")

```
> 4 votes

# Answer
# Python 3 - 437 bytes

```
a=input();i=p=l=-1;j=q=0
for x in a.split(", ")[::-1]:
    for y, z in [x.split(": ")]:
        s=lambda q,r,t:[t,sum([a*b for a,b in zip([60,1],map(int,q.split(':')))])][r%4<2]+[0,240][r<2]
        if y=="I":j+=1;i=s(z,j,i)
        else:q+=1;p=s(z,q,p)
        l=[l,p+i-239][j+q<2]
r=lambda d,e:("","%s: %02d:%02d, "%(d,(e/60)%24,e%60))[e>-1];p+=[1440,0][p>=l];i+=[1440,0][i>=l];print("Next "+[r("I",i)+r("P",p),r("P",p)+r("I",i)][p<i][:-2])

```

Explanation:

```
a=input();i=p=l=-1;j=q=0
for x in a.split(", ")[::-1]: #Read in reverse order, a="P: 01:00"
    for y, z in [x.split(": ")]:#Y="P", Z="00:00"
        s=
        lambda q,r,t:[t,sum([a*b for a,b in zip([60,1],map(int,q.split(':')))])]#Convert "01:01" to 61
        [r%4<2]#In case it's the first or fourth string calculate a new value, otherwise: return the original value
        +[0,240][r<2]#In case it's the last string: add 4 hours. Otherwise, leave it.
        if y=="I":j+=1;i=s(z,j,i)#Calculate for i
        else:q+=1;p=s(z,q,p)#Calculate for p
        l=[l,p+i-239][j+q<2]#Sets the last record. Since we read in reverse order, this should be the first one. We've added 4 hours though so remove those again
r=lambda d,e:("","%s: %02d:%02d, "%(d,(e/60)%24,e%60))[e>-1];#Print function, don't print anything when we have no value
p+=[1440,0][p>=l];i+=[1440,0][i>=l];    #Add a day if record is before the last record so we can correctly calculate the order
print("Next "+[r("I",i)+r("P",p),r("P",p)+r("I",i)][p<i][:-2])#print it and remove the last ","

```
> 1 votes

# Answer
# PHP, ~~228~~ ~~241~~ ~~239~~ ~~227~~ 226 bytes

requires PHP 7

```
Next<?foreach(explode(", ",$argv[1])as$d){[$m,$h,$i]=explode(":",$d);$x[$m][++$$m]=24+$h+$i/60;}foreach($x as$m=>$d)$r[$m]=$d[$$m-3]?:$d[$$m]-20;sort($r);foreach($r as$m=>$t)$o[]=" $m: ".date("i:s",$t%24*60);echo join(",",$o);

```

**breakdown**

```
Next<?                              // print "Next"
foreach(explode(", ",$argv[1])as$d) // loop through string split by comma+space
{
    [$m,$h,$i]=explode(":",$d);         // separate drug, hours and minutes
    $x[$m][++$$m]=24+$h+$i/60;          // append time to array, track count in ${$m}
}                                       // (i.e. $P for drug "P" etc.)
foreach($x as$m=>$d)                // loop through drugs
    $r[$m]=                             // add time to result
        $d[$$m-3]                           // if more than 3 medications, use $$m-3
            ??$d[$$m]-20                    // else use last medication - 20 hours
    ;
sort($r);                           // sort results by time
foreach($r as$m=>$t)$o[]=" $m: "    // prepare for output: drug name and formatted time:
    .date("i:s",$t%24*60)           // use hrs as mins and mins as secs to avoid TZ problems
;
echo join(",",$o);                  // print

```
> 1 votes

# Answer
## JavaScript (ES6), 246 bytes

```
s=>s.split`, `.map(s=>(m[s[0]].unshift(t=s.replace(/\d+/,h=>(h=(1+h)%24)>9?h:`0`+h),s),l=l||t.slice(1)),l=0,m={I:[],P:[]})&&`Next `+[].concat(m.I[7]||m.I[0]||[],m.P[7]||m.P[0]||[]).sort((i,p)=>((i=i.slice(1))<l)-((p=p.slice(1))<l)||i>p).join`, `

```

Explanation:

Looping over each dose, the `I` and `P` doses are separated into two arrays. 4 hours is also added to each dose, and those times are saved too. The arrays are populated in reverse to make detecting 8 entries easier. The time 4 hours after the first dose is also saved for use during sorting. At this point each array can be in one of three states:

* 8 entries, in which case the last entry is the first dose, and the next dose must be 24 hours after this dose (i.e. the same time tomorrow)
* 2, 4 or 6 entries, in which case the first entry is 4 hours after the last dose, and therefore the time of the next dose
* 0 entries, in which case we concatentate `[]`, which gets flattened and therefore excluded from the result

Having extracted the next dose times from the two arrays, it remains to sort them into order. This is done by comparing them against the time 4 hours after the first dose. If one of the two times is before this time, this must refer to tomorrow, and that dose comes last. Otherwise, the times are simply compared directly. (Rather inconveniently, the medicine is before the time, so I have to strip it to compare properly.)
> 0 votes

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


# Question
Title: Counting unit squares circle passes through
Write a program or function that given an integer radius *r* returns the number of unit squares the circle with radius *r* centered at the origin passes through. If the circle passes exactly through a point on the grid that does not count as passing through the adjacent unit squares.

Here's an illustration for *r = 5*:

Illustration by Kival Ngaokrajang, found on OEIS

Examples:

> 0 → 0
> 1 → 4
> 4 → 28
> 5 → 28
> 49 → 388
> 50 → 380
> 325 → 2540
> 5524 → 44180
> 5525 → 44020

# Answer
# Python 2, 54 bytes

```
f=lambda r,x=0:r-x and-~((r*r-x*x)**.5%1>0)*4+f(r,x+1)

```

Try it online!

Less golfed (55 bytes) (TIO)

```
lambda r:8*r-4*sum((r*r-x*x)**.5%1==0for x in range(r))

```

This estimates the output as `8*r`, then corrects for vertex crossings. The result is `8*r-g(r*r)`, where `g(x)` counts the number of ways to write `x` as a sum of two squares (except `g(0)=0`).

If the circle never went through any vertices, the number of cells touched would equal the number of edges crossed. The circle passes through `2*r` vertical gridlines and `2*r` horizontal gridlines, passing each one in both directions, for a total of `8*r`.

But, each crossing at a vertex counts as two edge crossings while only entering one new cell. So, we compensate by subtracting the number of vertex crossings. This includes the points on axes like `(r,0)` as well as Pythagorean triples like `(4,3)` for `r=5`.

We count for a single quadrant the points `(x,y)` with `x>=0` and `y>0` with `x*x+y*y==n`, then multiply by 4. We do this by counting the numer of `sqrt(r*r-x*x)` that are whole number for `x` in the interval `[0,r)`.
> 12 votes

# Answer
## Mathematica, 48 bytes

```
4Count[Range@#~Tuples~2,l_/;Norm[l-1]<#<Norm@l]&

```

Looks at the first quadrant and counts the number of grid cells for which the input falls between the norms of the cell's lower left and upper right corners (multiplying the result by 4, of course).
> 5 votes

# Answer
# Python 2, 72 bytes

```
lambda n:sum(0<n*n-x*x-y*y<2*(x-~y)for x in range(n)for y in range(n))*4

```

Try it online!
> 4 votes

# Answer
# Jelly, ~~21~~ ~~13~~ ~~12~~ 11 bytes

```
R²ạ²Æ²SạḤ×4

```

Try it online!

### How it works

```
R²ạ²Æ²SạḤ×4  Main link. Argument: r

R            Range; yield [1, 2, ..., r].
 ²           Square; yield [1², 2², ..., r²].
   ²         Square; yield r².
  ạ          Absolute difference; yield [r²-1², r²-2², ..., r²-r²].
    Æ²       Test if each of the differences is a perfect square.
      S      Sum, counting the number of perfect squares and thus the integer
             solutions of the equation x² + y² = r² with x > 0 and y ≥ 0.
        Ḥ    Un-halve; yield 2r.
       ạ     Subtract the result to the left from the result to the right.
         ×4  Multiply by 4.

```
> 3 votes

# Answer
# Perl 6, 61 bytes

```
->\r{4*grep {my &n={[+] $_»²};n(1 X+$_)>r²>.&n},(^r X ^r)}

```

### How it works

```
->\r{                                                    } # Lambda (accepts the radius).
                                                (^r X ^r)  # Pairs from (0,0) to (r-1,r-1),
                                                           #   representing the bottom-left
                                                           #   corners of all squares in
                                                           #   the top-right quadrant.
       grep {                                 }            # Filter the ones matching:
             my &n={[+] $_»²};                             #   Lambda to calculate the norm.
                              n(1 X+$_)>r²                 #   Top-right corner is outside,
                                          >.&n             #   and bottom-left is inside.
     4*                                                    # Return length of list times 4.

```
> 2 votes

# Answer
## AWK, 90 bytes

```
{z=$1*$1
for(x=$1;x>=0;x--)for(y=0;y<=$1;y++){d=z-x*x-y*y
if(d>0&&d<2*(x+y)+2)c++}$0=4*c}1

```

Usage:

```
awk '{z=$1*$1
    for(x=$1;x>=0;x--)for(y=0;y<=$1;y++){d=z-x*x-y*y
    if(d>0&&d<2*(x+y)+2)c++}$0=4*c}1' <<< 5525

```

Just a simple search through quadrant 1 to find all boxes that will intersect the circle. Symmetry allows for the multiply by 4. Could go from `-$1 to $1`, but that would take a more bytes and be less efficient. Obviously this is not the most time efficient of algorithms, but it only takes about 16 seconds to run the 5525 case on my machine.
> 1 votes

# Answer
# Haskell, 74 bytes

```
f n=sum[4|x<-[0..n],y<-[0..n],(1+n-x)^2+(1+n-y)^2>n^2,(n-x)^2+(n-y)^2<n^2]

```

Pretty straightforward, count the number of squares between (0,0) and (n,n) where the bottom left is inside the circle and the top right is outside the circle, then multiply by 4.
> 1 votes

# Answer
# Pyth, 29 bytes

```
Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2

```

Try it!

### Explanation

```
Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2  # implicit input: Q
Lsm*ddb                        # define norm function
 s                             # sum
  m   b                        #     map each coordinate to
   *dd                         #                            its square
                         ^UQ2  # cartesian square of [0, 1, ..., Q - 1]
                               #     -> list of coordinates of all relevant grid points
          f                    # filter the list of coordinates T where:
           }*QQ                # square of Q is in
               r               #     the range [
                hyT            #         1 + norm(T),
                               #                  ^ coordinate of lower left corner
                   ym+1dT      #         norm(map({add 1}, T))
                               #              ^^^^^^^^^^^^^^^ coordinate of upper right corner
                               #     ) <- half-open range
         l                     # size of the filtered list
                               #     -> number of passed-through squares in the first quadrant
       *4                      # multiply by 4
                               # implicit print

```
> 0 votes

# Answer
# Bash \+ Unix utilities, 127 bytes

```
c()(d=$[(n/r+$1)**2+(n%r+$1)**2-r*r];((d))&&echo -n $[d<0])
r=$1
bc<<<`for((n=0;n<r*r;n++));{ c 0;c 1;echo;}|egrep -c 01\|10`*4

```

Try it online!

Just go through all the points in the first quadrant, count them up, and multiply by 4. It can be very slow, but it works.
> 0 votes

# Answer
## Batch, 147 bytes

```
@set/an=0,r=%1*%1
@for /l %%i in (0,1,%1)do @for /l %%j in (0,1,%1)do @set/a"i=%%i,j=%%j,a=i*i+j*j-r,i+=1,j+=1,a&=r-i*i-j*j,n-=a>>31<<2
@echo %n%

```

Somewhat inspired by the AWK and Haskell answers.
> 0 votes

# Answer
# JavaScript (ES7), 76 bytes

```
n=>4*(G=k=>k<n?Math.ceil((n**2-k++**2)**0.5)-(0|(n**2-k**2)**0.5)+G(k):0)(0)

```
> 0 votes

---
Tags: code-golf, math, geometry, grid
---