title: Create a Boolean parser

text:
# Question
Title: Create a Boolean parser
What you need to do is create a Boolean parser.

---

Boolean expressions, in case you haven't heard of them yet, have two inputs and one output. There are four 'gates' in boolean arithmetic, namely OR (represented by `|`), AND (represented by `&`), NOT (which are used a bit like brackets : `/` and `\` ***note, I could have used `!`, but you can't use them as brackets, since `!!!!` is ambiguous (`//\\` or `/\/\`)***) and XOR (represented by `^`). These gates operate on their inputs which are either true or false. We can list the possible inputs (A and B in this case) and the outputs (O) using a **truth table as follows:**

```
XOR
A|B|O
-----
0|0|0
0|1|1
1|0|1
1|1|0

OR
A|B|O
-----
0|0|0
0|1|1
1|0|1
1|1|1

AND
A|B|O
-----
0|0|0
0|1|0
1|0|0
1|1|1

```

NOT is only 1 input, and it goes from true to false and vice versa.

In Boolean expressions, they are used like this:

```
1^((0&1&1)&/(1&0&1)\)

```

Evaluating as follows:

```
1^(( 1 |1)&/(1&0&1)\)  |  0 OR 1 = 1, order of operations left to right - no brackets
1^(( 1   )&/(1&0&1)\)  |  1 OR 1 = 1
1^(  1    &/(1&0&1)\)  |  Remove brackets
1^(  1    &/( 0 &1)\)  |  1 AND 0 = 0
1^(  1    &/( 0   )\)  |  0 AND 1 = 0
1^(  1    &/  0    \)  |  Remove brackets
1^(  1    &   1     )  |  NOT 0 = 1
1^(  1              )  |  1 AND 1 = 1
1^   1                 |  Remove brackets
0                      |  1 XOR 1 = 0

```

so 0 is the result.

**Task: create a program to do this!\***

## I/O examples

```
Input -> Output
1v(0.1) -> 1
1v(0.1./1\) -> 1
/0\v(0+1) -> 0
0v1v1 -> 0

```

## Notes

* There is no order of precedence. We will treat `0.1v0+1` as `(((0.1)v0)+1)`

### Leaderboard

```
var QUESTION_ID=77254,OVERRIDE_USER=42854;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# GNU Sed 4.2.2, 102

Score includes +1 for `-r` option to `sed`:

```
y/+./oa/
:
s%/0\\%1%
s%/1\\|\b(0o0|(\w)v\2)%0%
s%\b(\wo\w|\wv\w|1a1)%1%
s/\b\wa\w/0/
s/\((\w)\)/\1/
t

```

Ideone.

---

Incomplete Retina port.
> 1 votes

---
Tags: code-golf
---


title: Electrons bouncing in a wire

text:
# Question
Title: Electrons bouncing in a wire
Imagine a "wire" that has `n` spaces. Imagine further that there are "electrons" in that wire. These electrons only live for one unit of time. Any spaces in the wire that are adjacent to exactly one electron become an electron. In Game of Life terminology, this is `B1/S`.

For example, this is a wire of length 10, with period 62.

## Rules

* Input, `n`, is a single, positive integer.
* Output must be a single integer denoting the period of a wire of length n.
* The starting state is a single electron at one end of the wire.
* The period *does not necessarily* include the starting state. Some lengths never return to the starting state, but all of them are periodic.
* A static wire (i.e., one without electrons) has period 1.
* Boundary conditions are *not* periodic. That is, the wire is not toroidal in any way.

## Test cases

**Special thanks to orlp for producing this list.** (I have verified it up to n=27.)

```
1 1
2 2
3 1
4 6
5 4
6 14
7 1
8 14
9 12
10 62
11 8
12 126
13 28
14 30
15 1
16 30
17 28
18 1022
19 24
20 126
21 124
22 4094
23 16
24 2046
25 252
26 1022
27 56
28 32766
29 60
30 62
31 1
32 62
33 60
34 8190
35 56
36 174762
37 2044
38 8190
39 48
40 2046
41 252
42 254
43 248
44 8190
45 8188

```

You can see test cases for n=2 through 21 here with my Game-of-Life-esque simulator: Variations of Life.

---

**EDIT:** the sequence here has been published as A268754!

# Answer
# Python 2, 148 142 87 bytes

```
n=input()
p=l=1
t=1
h=2
while t!=h:
 if p==l:t,l,p=h,0,p*2
 h=h/2^h*2%2**n;l+=1
print l

```

Uses Brent's cycle detection algorithm, and thus actually runs fast.

---

I have also written an animation in Python (both 2 & 3 work). It needs `pyglet` to run. You can view the animation by running:

```
python -m pip install --user pyglet
curl -s https://gist.githubusercontent.com/orlp/f32d158130259cbae0b0/raw/ | python

```

(Feel free to download the gist and inspect the code before running.) You can press the + and - keys to increase/decrease the *n* being visualized.

---

And finally, for those interested in exploring this number sequence further, here is a readable version (this was used to generate the test cases above):

```
# Brent's cycle detection, modified from wikipedia.
def electron_period(n):
    wire_mask = (1 << n) - 1
    power = lam = 1
    tortoise, hare = 1, 2
    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = ((hare << 1) ^ (hare >> 1)) & wire_mask
        lam += 1
    return lam

```
> 10 votes

# Answer
# Mathematica, 127 bytes

```
p@n_:=Tr[#2-#]&@@Position[#,Last@#]&@NestWhileList[1~Table~n~ArrayPad~1*18~CellularAutomaton~#&,{1}~ArrayPad~{1,n},Unequal,All]

```

---

**Explanation**

*Rule 18*:

```
{0,0,0} -> 0
{0,0,1} -> 1
{0,1,0} -> 0
{0,1,1} -> 0
{1,0,0} -> 1
{1,0,1} -> 0
{1,1,0} -> 0
{1,1,1} -> 0

```

---

**Test cases**

```
p/@Range[10]
(* {1,2,1,6,4,14,1,14,12,62} *)

```
> 7 votes

# Answer
## Python 2, 68 bytes

```
f=lambda n,k=1,l=[]:k in l and-~l.index(k)or f(n,k/2^k*2%2**n,[k]+l)

```

The cycle detection could be better, but the iterative step is nice.

```
k -> k/2^k*2%2**n

```

By representing the array as a binary number `k`, the update can be done by taking the XOR of `k` shifted one left with `/2` and one right with `*2`, then truncating to `n` bytes as `%2**n`.
> 7 votes

# Answer
## Pyth, 39 36 bytes

```
L++Zmx@bd@bhhdQZ-lJ.uyN.[,Z1ZQ)xJyeJ

```

Uses the "cumulative fixed-point" function to iterate until just before a configuration recurs, and returns all intermediate configurations as a list of lists. This works because the rules are deterministic and the configuration of the next generation is a function of the current configuration. This means that once the same configuration appears again the automata have completed a cycle.

After reaching that (the last iteration of the cycle), it calls the next-gen function one last time on the last element of the "history" list, to obtain the next configuration (which is the starting configuration of a cycle), and find its index in the history. Now the period is simply the length ( 1 + index of cycle end) minus the index of cycle commencement.

**In pythonic pseudocode:**

```
                  Z = 0
                  Q = eval(input())
L                 def y(b):                # generates next-gen from current(param)
  ++Zm                return [Z] + map(    # adds head zero padding
    x@bd@bhhd             lambda d: b[d] ^ b[1+ 1+ d],  # xor the states of adjacent cells
    Q                     range(Q))        # implicit range in map
    Z                     + [Z]            # adds end zero padding
-lJ.uyN.[,Z1ZQ)   J = repeatTilRecur(lambda N,Y:y(N), padRight([Z,1],Z,Q)); print( len(J) -
                  # N:value; Y:iteration count
  JxJyeJ              J.index( y( J[-1] ) ) )

```

The test suite takes too much time that the server will kill it, so you'll need to use the regular program and test it one by one, or install Pyth (if you haven't) and use a script to test it.
> 4 votes

# Answer
## Python 3 2, 134 121 118 bytes

```
Q=input()
h=[]
n=[0,1]+Q*[0]
while n not in h:h+=[n];n=[0]+[n[d]^n[d+2] for d in range(Q)]+[0]
print len(h)-h.index(n)

```

Basically the same as my Pyth answer, but adapted it somewhat because of lack of certain built-in functions in Python.

Ungolfed version:

```
length = input()
history = []
new = [0] + [1] + length*[0]
while new not in history:
    history += [new]
    new = [0] + [new[cell]^new[cell+2] for cell in range(length)] + [0]
print len(history) - history.index(new)

```
> 4 votes

# Answer
# Jelly, ~~19~~ ~~18~~ 17 bytes

```
H^Ḥ%®
2*©Ç‘Ð¡UµiḢ

```

This code computes the first **2n** states, so it's not particularly fast or memory efficient...

Try it online! or verify the first 16 test cases.

### Alternate version, 13 bytes (non-competing)

Versions of Jelly that postdate this challenge have built-in loop detection, enabling a solution that is both shorter and more efficient.

```
H^Ḥ%®
2*©ÇÐḶL

```

This handles the last test case with ease. Try it online!

### How it works

```
2*©Ç‘Ð¡UµiḢ    Main link. Input: n (integer)

2*             Compute 2 ** n.
  ©            Store the result in the register.
     Ð¡        Do the following:
   Ç             Apply the helper link, which updates the state, ...
    ‘            2 ** n + 1 times.
               Collect all 2 ** n + 2 intermediate results in a list.
       U       Upend; reverse the list of results.

        µ      Begin a new, monadic chain. Argument: R (list of results)
          Ḣ    Yield and remove the first element of R (final state).
         i     Find its first index in the remainder or R.
               This is the length of the loop.

H^Ḥ%®        Helper link. Argument: s (state, integer)

H            Halve s. This yields a float, but ^ will cast to integer.
  Ḥ          Double s.
 ^           Compute (s ÷ 2) ^ (s × 2).
    ®        Retrieve the value stored in the register (2 ** n).
   %         Compute ((s ÷ 2) ^ (s × 2)) % (2 ** n).

```

Note that the helper link is applied to **2n** in the first iteration, which does not encode a valid state. However, **((2n ÷ 2) ^ (2n × 2)) % 2n = (2n - 1 \+ 2n + 1) % 2n = 2n - 1**, which is one of the possible starting states.

Since we loop **2n *\+ 1*** times, we are guaranteed to encounter a state twice, making the loop detection successful.
> 4 votes

# Answer
## CJam, ~~41~~ ~~34~~ ~~31~~ ~~27~~ 25 bytes

*Thanks to Dennis for saving 3 bytes. Borrowing an idea from his Jelly answer saved another 4.*

```
2ri#_){__4*^2/W$%}*]W%(#)

```

Test it here.

### Explanation

I'm representing the wire simply as an integer (whose bits indicate the positions of the electrons) instead of using an actual list of bits. The state is the updated via fairly simple bitwise computations.

To find the period we collect all intermediate results on the stack, run the simulation for 2n-1+1 steps, and then determine the period as the number of elements since the last occurrence of the final state(plus 1).

Here's a breakdown of the code:

```
2ri#   e# Compute 2^n. This has a 1 in the n+1-th bit and zeroes below it. This is
       e# itself not a valid state but will be turned into 2^(n-1) by the first
       e# update.
_)     e# Duplicate and increment to get number of steps to simulate.
{      e# Repeat that many times...
  __   e#   Duplicate the last state twice.
  4*   e#   Multiply by 4, shifting all bits to the left by two positions.
  ^    e#   XOR - we only keep keep those cells where we have exactly one 1-bit
       e#   between both copies, i.e. those that neighboured a single electron
       e#   but shifted up by one position. We don't need handle the survival rule
       e#   explicitly, since electrons can never be adjacent in the first place.
  2/   e#   Divide by 2 shifting all bits back to the right again.
  W$   e#   Copy the initial number 2^n.
  %    e#   Modulo - this simply sets the first bit to 0.
}*
]      e# Wrap all states in an array.
W%     e# Reverse it.
(      e# Pull off the latest state.
#      e# Find its position in the remainder of the array.
)      e# Increment.

```
> 3 votes

# Answer
# MATL, ~~38~~ ~~37~~ ~~36~~ 35 bytes

```
1Oi(`t0Y)5BX+8L)1=vt6#Xut0)=fdt?w}A

```

This uses a loop that keeps computing new states until the new state equals any of the preceding ones. Each state is a vector of zeros and ones. These vectors are stored as rows of a growing 2D array.

Computation of each new state is done by convolving the current state with the sequence `[1,0,1]`, keeping only the central part, and setting to `0` any entry that is not `1`.

*EDIT (May 13, 2016) The code in the following link has been slightly modified in accordance with changes introduced in the language after this answer was written*

**Try it online!**

```
1Oi(            % create initial vector [1,0,0,...,0], with size equal to input
`               % do...while loop
  t0Y)          %   duplicate. Get last row of array: most recent vector
  5BX+8L)       %   compute new vector by convolving the most recent one
                %   with [1,0,1] and keeping only the central part
  1=            %   set ones to 1, rest to 0
  v             %   append to 2D array
  t6#Xu         %   compute vector of unique numeric labels, so that equal rows
  t0)=f         %   indices of entries whose value equals that of the last entry.
                %   This will contain the index of the last entry and possibly
                %   another index, in which case we've found a repetition
  d             %   this will either be empty (which is falsy) or contain the
                %   period, which is a nonzero number (and thus truthy)
  t?            %   duplicate. If non-empty (and nonzero)
    w           %     swap to put the 2D-array at the top of the stack. This is
                %     falsy, because it contains at least one zero, even in the
                %     n=1 case (the array is initiallized to 0 in that case)
                %     So the loop will terminate, with the period left on the stack
  }             %   else
    A           %     this transforms the empty array at the top of the stack
                %     into a true value, so that the loop will continue
                %   implicitly end if
                % implicitly end loop
                % implicitly display stack contents (period)

```
> 2 votes

# Answer
# JavaScript (ES6) 99 ~~104~~

```
n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

```

**Test**

```
f = n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

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

;[...Array(45)].map((_, i) => console.log(++i + ' ' + f(i)))
```

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

# Answer
# Haskell, 170 bytes

`x!p` gives the element at index p if in bounds, else 0. `n` calculates the next step. `g i` gives the `i`th step. `c x` gives the period, if starting with `x`. `f` wraps it all together.

```
n x|l<-length x-1=[mod(x!(p-1)+x!(p+1))2|p<-[0..l],let y!q|q<0=0|q>=l=0|1<2=y!!p]
c x=[i-j|i<-[1..],j<-[0..i-1],let g k=iterate n x!!k,g i==g j]!!0
f n=c$1:map(*0)[2..n]

```

(Note: posted from phone that has the hugs interpreter, which is not full featured, so might have typos.)
> 2 votes

# Answer
# Perl 6, 81 bytes

```
{my@h=my$w=2;@h.push($w=$w/2+^$w*2%2**$_)while 2>@h.grep($w);[R-] @h.grep($w,:k)}

```

**Expanded and ungolfed a bit**

```
-> $n {
    my @history = my $wire = 2;
    while 2 > @history.grep($wire) {
        @history.push($wire = $wire/2 +^ $wire*2 % 2**$n)
    }
    [R-] @history.grep($wire,:k)
}

```

A bit of explanation:

* `[op]` reduces the list using op. For example `[+] @list` will sum `@list`
* `R` is a meta-op that reverses the arguments given to an op. For example `1 R- 3` will result in 2.
> 1 votes

# Answer
# C++, 211 bytes

Golfed

```
#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);int main() {int p,l;for(scanf("%d",&p);p--;m.set(p));
for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;return !printf("%d",l);}

```

With added whitespace for readability

```
#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);
int main() {
    int p,l;
    for(scanf("%d",&p);p--;m.set(p));
    for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;
    return !printf("%d",l);
}

```

Good practice for C++'s bitset; and a great education learning about Brent's cycle detection algorithm (as used by @orlp)
> 1 votes

# Answer
# Pyth, 95 bytes

```
J.[ZQ[1)K_1=bYW<K0=NY aN?hJZ?htJ1ZFTr1tlJ aN?@JTZ?x@JhT@JtT1Z) aN?eJZ?@J_2 1Z=JN=KxbJ abJ;-tlbK

```

You can try it out here.
> 0 votes

# Answer
# Pyth, 29 bytes

```
J^2QL%x/b2*b2JK.uyN1;-lKxKyeK

```

Uses the algorithm `a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N)`.
> 0 votes

# Answer
# Ruby, 72 bytes

Anonymous function.

```
->n{s=[w=1];c=p
(j=s.index w=w*2%2**n^w/2
j ?c=s.size-j:s<<w)while !c
c}

```
> 0 votes

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


title: Insert semi-sorted into unsorted array

text:
# Question
Title: Insert semi-sorted into unsorted array
Welcome to your first day at PPCG Inc. As our newest junior assistant document sorter, you are responsible for making sure all documents we sent down to you are archived in alphabetical order. It's so easy a monkey can do it. Well, metaphorically speaking, as we did hire a monkey to do it. Guess what? Turns out monkeys lack an understanding of our alphabet. Anyway, there's no time to fix the mess there is right now, so just try to not make the situation any worse, ok? Then get to it! If you get hungry, there's bananas over by the water cooler. Good luck!

## Job Description

### Input

* You will receive a list of strings (the archive) and a string that needs to be added to that list (the document)
* All strings will contain only uppercase letters, lowercase letters and spaces
* Strings will always start and end with a letter

### Task

Determine the target position of the document: the position it should receive in the archive. The target position can be determined as follows:

* For each position:
    + Count the amount of strings in the archive before that position that are alphabetically before the document
    + Count the amount of strings in the archive after that position that are alphabetically after the document
    + Define the score of the position as the sum of the above two counts
* The target position of the document is the position with the highest score
* In case of a tie, all positions with the highest score are equally valid as target position. Only one needs to be selected.

When sorting:

* Uppercase and lowercase letters are equivalent
* Spaces come before letters

### Output

* The archive with the document added to it in any form

OR

* The target position of the document, in either a 0-based or 1-based index

### Job evaluation

Fewest bytes wins!

### Example I/O

```
Archive:
    Applebuck Season
    Friendship is Magic
    The Ticket Master
    Griffon the BrushOff
    Boast Busters
    Bridle Gossip

Document: Dragonshy

Position scores (0-based index):
0: 0 + 3 = 3
1: 1 + 3 = 4
2: 1 + 2 = 3
3: 1 + 1 = 2
4: 1 + 0 = 1
5: 2 + 0 = 2
6: 3 + 0 = 3

Target position: 1

```

# Answer
## JavaScript (ES6), 81 bytes

```
(a,d)=>a.map((e,i)=>d[l="toLowerCase"]()<e[l]()?s--:++s>m&&(++m,p=++i),m=s=p=0)|p

```

Ungolfed:

```
function position(archive, document) {
    var score = 0;
    var max = 0;
    var pos = 0;
    var i = 0;
    while (i < archive.length) {
        if (archive[i++].toLowerCase() > document.toLowerCase()) {
            score--;
        } else {
            score++;
            if (score > max) {
                max++;
                pos = i;
            }
        }
    }
    return pos;
}

```

Edit: Saved a lot of bytes thanks to @user81655.
> 4 votes

# Answer
# Pyth, ~~40~~ 38 bytes

Credits to @Katenkyo for teaching me that `A xnor B` is basically `A==B`. (`A xor B` is also `A!=B`)

```
AQJ+],k0.e,rb0hkGteh.Msmq<hdrH0<edeZJJ

```

Try it online!

How it works:

It sums the XNOR of whether the entry is smaller than the document, and whether the entry's index is smaller than the document's index.

It finds the position in which this sum is the maximum, then outputs it.
> 3 votes

# Answer
# Python 3, 135 167 Bytes

```
def a(b,c):a=[sum(map(lambda x:x.lower()>c.lower(),b[i:]))+sum(map(lambda x:x.lower()<c.lower(),b[:i]))for i in range(0,len(b)+1)];b.insert(a.index(max(a)),c);print(b)

```
> 2 votes

# Answer
## Pyth, ~~54~~ ~~52~~ ~~47~~ 45 bytes

```
AQVhlG=Ys+m>rH0rd0:G0Nm<rH0rd0gGNI>YZ=ZY=kN;k

```

Expect input is a list, first element is a list of strings (archive), second element is a string (document)

```
AQ                                            # initialize G and H with the archive and the document
  VhlG                                        # iterate over the indexes on archive
      =Ys+                                    # concatenate and sum the following scores
          m>rH0rd0:G0N                        # map a string comparison between the document and the archives up to the index, returning true(1) for lower, and false(0) for higher
                      m<rH0rd0gGN             # same as above, but starts at the index and goes up to the end of the archive, returning false(0) for lower, and true(1) for higher
                                 I>YZ         # Check if score is higher than highest
                                     =ZY      # update highest score
                                        =kN;  # update index
                                            k # print index

```

Test here

* *Saved 5 bytes on input initialization (thanks @Kenny Lau)*
> 1 votes

# Answer
# Ruby, 97 bytes

Anonymous function, returns the target position.

```
->a,d{d.upcase!;(0...a.size).max_by{|i|a[0,i].count{|s|s.upcase<d}+a[i..-1].count{|s|s.upcase>d}}}

```

When actually inserting into the archive, **110 bytes**:

```
->a,d{t=d.upcase;a.insert (0...a.size).max_by{|i|a[0,i].count{|s|s.upcase<d}+a[i..-1].count{|s|s.upcase>d}},d}

```
> 1 votes

# Answer
# MATL, 32 bytes

```
hk4#S4#S%2#0)>t0whYsw~0hPYsP+K#X>

```

Input is a cell array of strings (several strings separated by spaces and enclosed in curly braces) for the archive, and a string for the document. Output is 1-based. In case of a tie the first position is returned.

**Try it online!**

### Explanation

```
h      % Concatenate archive and document as a cell array of strings
k      % Convert all strings to lowercase
4#S    % Sort and output the indices of the sorting
4#S    % Again. This gives the indices that applied to the concatenated
       % array would make it sorted
2#0)   % Separate last index (document) from the others (archive)
>      % Is it greater? Gives zero/one array the size of the archive
t      % Duplicate that array
0wh    % Prepend a 0
Ys     % Cumulative sum. This is first part of the score
w~     % Swap. Negate zero/one array
0h     % Postpend a 0
PYsP   % Reverse, cumulative sum, reverse. Second part of the score
+      % Add. This is the score of each position
K#X>   % Arg max

```
> 1 votes

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


title: Switching Gravity

text:
# Question
Title: Switching Gravity
### Challenge

You are given an ASCII-art representation of characters on a plane as input by any reasonable method. This will only contain:

* `[a-z]` representing moveable characters. Every letter will appear on the board at most once.
* `#` representing immovable walls
* `.` representing empty space

For example:

```
abcdef.gh#..
.......ij.#.
#..#.......#
...#.#...###
.#.......#q#
.........###

```

You are also given a string representing the changes in gravity. This will only contain:

* `>` representing a change to rightward gravity
* `<` representing a change to leftward gravity
* `^` representing a change to upward gravity
* `v` representing a change to downward gravity

For example:

```
v>^

```

Your program must simulate the each change in gravity sequentially until all characters stop moving (they hit a wall, or another character). Characters that "fall off the edge of the map" are permanently removed, and characters can "stack" on top of each other.

In this example, at the start there is downward gravity (`v`), so `c`, `e`, `g`, `h`, `i`, and `j` fall off the bottom of the map. All other characters slide downwards until hitting a wall, leaving the map like this:

```
.........#..
a..d......#.
#..#.f.....#
.b.#.#...###
.#.......#q#
.........###

```

Then, we move on to rightward gravity (`>`), which leaves us with this: Note how the `a` stacks next to the `d`.

```
.........#..
........ad#.
#..#......f#
..b#.#...###
.#.......#q#
.........###

```

Finally, we simulate upward gravity (`^`), during which the `a` and the `b` fall off the map.

```
.........#..
.........d#.
#..#......f#
...#.#...###
.#.......#q#
.........###

```

Your task is to output the remaining characters after the gravitational shifts. They can be given in any order. For this example, you could output any permutation of `dfq`.

### Testcases

For the following map:

```
abcde
.....
##.##

```

```
v   =  abde
v>  =  <nothing>

```

For the following map:

```
######
#....#
abcdef
#.gh..
######

```

```
>   = <nothing>
<   = gh
^>  = bcde
v<  = bghef

```

# Answer
## JavaScript (ES6), ~~251~~ 233 bytes

```
(m,d,r=`replace`)=>[...d].map(c=>[...`<^>v`].map(d=>m=[...(m=(c==d?m[r](/[.\w]+/g,s=>s[r](/\./g,``)+s[r](/\w/g,``))[r](/^\w+/gm,s=>s[r](/./g,`.`)):m).split`
`)[0]].map((_,i)=>m.map(s=>s[i]).join``).reverse().join`
`))&&m[r](/\W/g,``)

```

Edit: Saved 18 bytes thanks to @WashingtonGuedes.

Works by rotating the input grid four times for each directional character, but on the direction where the directional character matches the loop character we do the left gravity thing. Pseudocode:

```
function slideleft(map) {
    map = map.replace(/[.\w+]/g, match=>movedotstoend(match));
    map = map.replace(/^\w+/gm, match=>changetodots(match));
}
function rotate(map) {
    return joinrows(reverse([for each (column of rows(map)[0])
            joinrow([for each (row of rows(map)) row[column]])
           ]));
}
function gravity(map, directions) {
    for each (direction of directions) {
        for each (angle of '<^>v') {
            if (direction == angle) map = slideleft(map);
            map = rotate(map);
        }
    }
    return letters(map);
}

```
> 4 votes

# Answer
# JavaScript (ES6), 199

Same algortihm of @Neil's answer. The grid is rotated four times for each directional character, when in the right position the gravity shift to left is applied to each row.

```
x=>y=>(x=>{for(d of y){R='';for(e of'^>v<')x=[...x[0]].map((c,i)=>e!=d?x.map(r=>r[i]).join``:x.map(r=>(c=r[i])<'.'?(q+=p+c,p=''):c>'.'&&q?(q+=c,R+=c):p+='.',q=p='')&&q+p).reverse();}})(x.split`
`)||R

```

```
F=x=>y=>(x=>{for(d of y){R='';for(e of'^>v<')x=[...x[0]].map((c,i)=>e!=d?x.map(r=>r[i]).join``:x.map(r=>(c=r[i])<'.'?(q+=p+c,p=''):c>'.'&&q?(q+=c,R+=c):p+='.',q=p='')&&q+p).reverse();}})(x.split`
`)||R

// Less golfed

U=(x,y)=>
{
  x = x.split`\n`;
  for(d of y)
  {
    R = '';
    for(e of '^>v<')
      x = [...x[0]].map(
        (c,i) => e != d
        ? x.map( r => r[i] ).join`` // basic rotation
        : x.map( // rotation with gravity shift
          r=> (c=r[i])<'.' ? (q+=p+c,p='') : c>'.'&&q?(q+=c,R+=c) : p+='.', q=p=''
        ) && q+p
      ).reverse();
  }
  return R
}

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

;[
  ['abcdef.gh#..\n.......ij.#.\n#..#.......#\n...#.#...###\n.#.......#q#\n.........###',
   [['v>^','dfq']]
  ],
  ['abcde\n.....\n##.##',[['v','abde'],['v>','']]],
  ['######\n#....#\nabcdef\n#.gh..\n######',[['>',''],['<','gh'],['^>','bcde'],['v<','befgh']]]
].forEach(t => {
  var i=t[0]
  console.log(i)
  t[1].forEach(([d,k])=>{
    var r=F(i)(d),ok=[...r].sort().join``==k
    console.log((ok?'OK ':'KO ')+d+' : '+r+(ok?'':' (expected '+k+')'))
  })
  console.log('')
})
```

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

# Answer
# Pyth, 143 bytes

(Do we really need that much bytes?)

```
JhQKeQMe.u:N+"\."H+H"."G;DybVkI}NG=gkN;D'bVlJ=k@JNykVkI}HG=:kH\.).?B)=XJNk;VKIqN\<'J)IqN\v=C_J'J=_CJ)IqN\>=C_CJ'J=C_CJ)IqN\^=CJ'J=CJ;VJVNI}HGpH

```

Try it online!

## How it works

We define a function `left` which does the leftward gravity thing.

Then, the other directions are implemented by messing with the array so that the desired direction is leftwards, then do `left`.

The algorithm of `left` is here:

* Do the following until idempotent:
* Replace `".X"` with `"X."`, where `X` represents a letter.

The whole program is divided into the following 6 sections:

```
JhQKeQ
Me.u:N+"\."H+H"."G;
DybVkI}NG=gkN;
D'bVlJ=k@JNykVkI}HG=:kH\.).?B)=XJNk;
VKIqN\<'J)IqN\v=C_J'J=_CJ)IqN\>=C_CJ'J=C_CJ)IqN\^=CJ'J=CJ;
VJVNI}HGpH

```

### First section

```
JhQKeQ     Q auto-initialized to evaluate(input())
JhQ        J = Q[0]
   KeQ     K = Q[len(Q)-1]

```

### Second section

```
Me.u:N+"\."H+H"."G;   @memoized
M                 ;   def g(G,H):
  .u             G      repeat_until_idempotent(start:G, as N):
    :Nxxxxxxyyyyy         return N.replace(xxxxxx,yyyyy)
      +"\."H                               "\."+H
            +H"."                                 H+"."

```

### Third section

```
DybVkI}NG=gkN;    @memoized
Dyb          ;    def y(b):
   Vk               for N in k:     --TAKES GLOBAL VARIABLE k
     I}NG             if N in G:    --G pre-initialized to "abcde...z"
         =gkN           k = g(k,N)

```

### Fourth section

```
D'bVlJ=k@JNykVkI}HG=:kH\.).?B)=XJNk;  @memoized
D'b                                ;  def single_quote(b):
   VlJ                       )          for N in range(len(J)): --TAKES GLOBAL VARIABLE J
      =k@JN                               k = J[N] --SETS GLOBAL VARIABLE k
           yk                             y(k) --returns nothing, but MODIFIES GLOBAL VARIABLE k
             Vk                           for H in k:
               I}HG      )                  if H in G:
                   =:kH\.                     k = k.replace(H,".")
                          .?                else:
                            B                 break
                              =XJNk     J[N] = k --MODIFIES GLOBAL VARIABLE J

```

### Fifth section

```
VKIqN\<'J)IqN\v=C_J'J=_CJ)IqN\>=C_CJ'J=C_CJ)IqN\^=CJ'J=CJ;
VK                                                       ; for N in K:
  IqN\<  )                                                   if N == '<':
       'J                                                      single-quote(J)
          IqN\v          )                                   if N == 'v':
               =C_J                                            J = transpose(reverse(J))
                   'J                                          single-quote(J)
                     =_CJ                                      J = reverse(transpose(J))
                          IqN\>            )                 if N == '>':
                               =C_CJ                           J = transpose(reverse(transpose(J)))
                                    'J                         single-quote(J)
                                      =C_CJ                    J = transpose(reverse(transpose(J)))
                                            IqN\^            if N == '^':
                                                 =CJ           J = transpose(J)
                                                    'J         single-quote(J)
                                                      =CJ      J = transpose(J)

```

### Sixth section

```
VJVNI}HGpH
VJ           for N in J:
  VN           for H in N:
    I}HG         if H in G: --G = "abc...z"
        pH         print(H)

```
> 2 votes

# Answer
# Ruby, 306 bytes

Anonymous function. Pretty circuitous technique that could probably be optimized.

```
->s,d{w=[];x=y=0;m={}
s.chars.map{|c|c>?!?(c<?A?c<?.?w<<[x,y]:0:m[c]=[x,y]
x+=1):(x=0;y+=1)}
d.chars.map{|c|q=[c<?=?-1:c<?A?1:0,c>?a?1:c>?A?-1:0];e=1
(n=m.clone.each{|k,v|z=[v[0]+q[0],v[1]+q[1]]
w.index(z)||m.value?(z)?0:m[k]=z}
m.reject!{|k,v|i,j=v;i<0||i>=x||j<0||j>y}
e=(m!=n ?1:p))while e}
m.keys.join}

```
> 1 votes

---
Tags: code-golf
---


title: "Stair-ify" a string

text:
# Question
Title: "Stair-ify" a string
You must write a program or function that creates a "stair-ified" string. Here is how you "stair-ify" a string:

For each character in the string:

* If the character is an upper or lowercase vowel, not including 'y', output it then move the rest of the string *up* a column.
* If the character is a space or a tab, output it then move the rest of the string *down* a colum.
* If the character is neither, output it normally.

IO can be in any reasonable format. The input will not contain any newlines. If you want, you can remove any trailing whitespace.

If you choose to return the string, rather than printing it, please also include a short program that will print your string so that it can be visualized. This is not mandatory, nor will it go towards your byte-count. This is just a convenience for users who don't understand golf or esolangs (like me) to be able to verify output or tinker with the code.

# Sample IO:

Output for "bcdef ghijkl":

```
    f    jkl
bcde  ghi

```

Output for "Programming Puzzles And Code-Golf":

```
                               lf
                            -Go
                  s  nd   de
         ng   zzle  A   Co
      mmi   Pu
   gra
Pro

```

Output for "Abcdefghijklmnopqrstuvwxyz":

```
                     vwxyz
               pqrstu
         jklmno
     fghi
 bcde
A

```

As usual, this is code-golf, so shortest answer in bytes wins.

# Answer
> 2 votes
# MATL, ~~38~~ 37 bytes

```
Oj33<G13Y2m-IL)hYstX<-"@Z"GX@)h]Xh!c!

```

**Try it online!**

### Explanation

For each char, the code computes its vertical position, measured from above (0 is highest). It then builds the output string transposed: each char is on a line with as many leading spaces as its vertical position indicates. Then all lines are contatenated into a 2D char array, which is finally transposed and displayed.

```
O       % push a 0
j       % input a string
33<     % array of the same length as the input that contains true for spaces or tabs
G       % push input again
11Y2    % string 'aeiouAEIOU'
m       % array of the same length as the input that contains true for vowels
-       % subtract
IL)     % remove last element
h       % prepend the 0 that is at the bottom of the stack
Ys      % cumulative sum. This gives the vertical position of each char
tX<     % duplicate. Compute minimum
-       % subtract. This sets minimum vertical position to 0
"       % for each vertical position
  @     %   push vertical position of current character
  Z"    %   string with that many spaces
  G     %   push input again
  X@)   %   get the character corresponding to the current iteration index
  h     %   concatenate horizontally
]       % end for each
Xh      % concatenate all lines into a row cell array
!       % transpose into a column cell array
c       % convert into 2D array, padding with spaces if needed
!       % transpose. Implicitly display

```

# Answer
> 7 votes
# Pyth, 63 bytes

```
V_Q aY?}rN0"aeiou"=hZ?}N"     "=tZZ;Jh.mbYKh.MZYjC.b++*d+JNY*dK_YQ
                         ^^^^^
                         |||||
                         |tabs
                        space

```

The spaces in the middle is actually a single tab character, but StackExchange renders it as four spaces.

Try it online!

# Answer
> 4 votes
# Python 2, 141 137 bytes

```
def S(s,l=[0]):
 for c in s:l+=[l[-1]-(c in"aeiouAEIOU")+(c<"!")]
 for h in sorted(set(l)):print"".join([" ",c][i==h]for i,c in zip(l,s))

```

# Answer
> 3 votes
## JavaScript (Firefox 30-57), 151 bytes

```
s=>[...s].map((c,i)=>r[c<'!'?n++:/[AEIOU]/i.test(c)?n--:n][i]=c,n=s.length,r=[for(_ of s+s)[]])&&[for(a of r)if(s=[for(c of a)c||' '].join``)s].join`\n`

```

Where `\n` represents the literal newline character.

# Answer
> 1 votes
# Perl, 110 bytes *(108 bytes script + 2 bytes flags)*

```
$h=0;map{$h{$h}.=' 'x($p-$p{$h}).$_;$p{$h}=++$p;$h+=/[aeiou]/i-/\s/}split//;print for@h{sort{$b<=>$a}keys%h}

```

Run with `perl -nl script.pl`, input is on stdin, output is on stdout.

## Deobfuscated

I've renamed the variables more sensibly, made the code `use strict` and `use warnings` compliant, and made explicit a lot of the magic perl does automatically.

This is just run as `perl script.pl`, because it replicates the effects of the `-nl` flags inside the script.

```
use strict;
use warnings;
use English;

# The effect of -l in perl's flags
$INPUT_RECORD_SEPARATOR = "\n";
$OUTPUT_RECORD_SEPARATOR = "\n";

# These variables are magicked into existence
our $column = 0;
our %line_col = ();
our %lines = ();

# The implicit while-loop is the effect of -n in perl's flags
while (defined(my $line = <>)) {
    # The "chomp" is part of perl's -l flag too
    chomp $line;

    # Here starts the actual script. "$h=0" turns into...
    our $height = 0;
    for my $char (split '', $line) {
        if (!exists $line_col{$height}) {
            # Setting it to 0 is a bit of a white lie, but it might as well be 0.
            # Perl would otherwise have called the value "undef", which is
            # similar to 0 in numeric contexts.
            $line_col{$height} = 0;
        }

        $lines{$height} .= ' ' x ($column - $line_col{$height});
        $lines{$height} .= $char;

        $column++;
        $line_col{$height} = $column;

        $height++ if $char =~ /[aeiou]/i;
        $height-- if $char =~ /\s/;
    }

    # Sort line heights numerically descending (so the greatest is printed first)
    my @heights = sort { $b<=>$a } keys %lines;

    for my $line (@lines{ @heights }) {
        print $line;
    }
}

```

# Answer
> 1 votes
# C, 180 bytes

```
char s[99];i,j,p[99],m,M;main(c){for(gets(s);c=s[i];j+=strchr("aeiou",c|32)!=0,j-=c<33,m>j?m=j:M<j?M=j:0)p[i++]=j;for(;m<=M;putchar(10),M--)for(i=0;c=s[i];)putchar(M^p[i++]?32:c);}

```

Ungolfed:

```
char s[99];i,j,p[99],m,M;
main(c){for(gets(s);c=s[i];
j+=strchr("aeiou",c|32)!=0,j-=c<33,m>j?m=j:M<j?M=j:0)
  //move current height up or down, adjust minimum and maximum height
p[i++]=j;  //record height of character
for(;m<=M;putchar(10),M--)  //from maximum to minimum height
for(i=0;c=s[i];)putchar(M^p[i++]?32:c);}  //print only characters on this height

```

# Answer
> 1 votes
# JavaScript (ES6), 133

```
s=>s.replace(/[^aeiou ]*(.?)/gi,(z,x,c)=>(q=o[r]||'',o[r]=q+=' '.repeat(c-q.length)+z,x<'!'?++r:r?--r:o=[,...o]),o=[],r=0)&&o.join`
`

```

*Less golfed*

```
s=>(
  s.replace(/[^aeiou ]*(.?)/gi,(z,x,c)=>(
    q = o[r] || '',
    o[r] = q += ' '.repeat(c - q.length) + z,
    x == ' ' ? ++r : r ? --r : o = [,...o]
  ), o = [], r = 0),
  o.join`\n`
)

```

**Test**

```
f=s=>s.replace(/[^aeiou ]*(.?)/gi,(z,x,c)=>(q=o[r]||'',o[r]=q+=' '.repeat(c-q.length)+z,x<'!'?++r:r?--r:o=[,...o]),o=[],r=0)&&o.join`
`

function test() {
  i=I.value
  O.textContent=f(i)
}

test()
```

```
#I { width:90%}
```

```
<input id=I oninput='test()' value='Programming Puzzles And Code-Golf'>
<pre id=O>
```

# Answer
> 0 votes
# C,  ~~173~~   ~~160~~   ~~156~~  155 bytes

Edit: Borrowed idea of using strchr from @mIllIbyte to shave off 13 bytes

Edit2: Streamlined the min/max comparisons, -4 bytes

Edit3: c can have any value to begin with -\> into main(c) instead, -1 byte

Edit4: Added ungolf/explanation

```
p,l,j,m;main(c){char b[99],*s=gets(b);for(;j<m+2;p?putchar(c?l?32:c:10):l<j?j=l:l>m?m=l:0,l-=c?(c&=223)&&c-9?!!strchr("AEIOU",c):-1:(p=s=b,l+j++))c=*s++;}

```

Ungolfed and explained:

```
/* declare and initialize these variables to int and 0 */
p,l,j,m;

/* declares main, but also int c */
main(c)
{

  /* we can handle strings of length 98 (+1 for string-terminating 0) */
  /* we declare and initialize s to point to the beginning of the input
     string for the first pass through the for loop */
  char b[99],*s=gets(b);

  /* the for-loop actually contains nested loops, where the inner loops
     behave differently depending on the outer loop parameter p as follows:
     p attains the values false (0) and true (non-null pointer), in this order.

     p == false:
      the inner loop has the parameter s and passes through all the characters
      in the string until the string is exhausted (*s == 0). l is the vertical
      position of the current character relative to the first character
      (l = 0), smaller number = higher up. The purpose here is simply to find
      the range of vertical positions [j, m] present in the string. The
      commands in execution order are:

      -- loop over s --

      // test does not do anything since j <= m by design
      1. j < m+2

      // puts current char in c and increments string counter
      2. c = *s++

      // ensures that j (m) equals the min (max) of the vertical positions (l)
         encountered so far. At first step j = l = m = 0.
      3. l<j?j=l:l>m?m=l:0

      // c != 0, this updates the vertical position for the next character
      // c = SPC or C = TAB -> lower (l increases by 1)
      // c = "aeiouAEIOU" -> higher (l decreases by 1)
      4a. l-=(c&=223)&&c-9?!!strchr("AEIOU",c):-1

      -- loop over s ends --

      // c == 0, this resets the string pointer s and puts p = true, and
      //         thereby initiates the next phase of the algorithm
      //         see rest of the explanation at p == true)
      4b. p=s=b

    p == true:
     now there are two inner loops. The outer of these has the parameter j,
     which ranges from the smallest vertical position+1 (the value of j after
     the p == false pass) to the largest vertical position+1 (m+2 after the
     p == true pass). The innermost loop has the parameter s and passes through
     all characters in the string until the string is exhausted (*s == 0) just
     as in the p == false inner loop. Here l is now the vertical position
     relative to the current position j-1, so that l == 0 when a character is
     at the current level. Such characters are printed as is, whereas
     characters at other levels are replaced by space. The end-of-string
     marker 0 outputs a newline. The commands in execution order are:

      -- loop over j --

      // at first step increments j to point to be one more than the
      // current vertical position. At other steps moves the current position
      // (j-1) one vertical position downwards. Also, at all steps, this
      // biases the vertical position counter l to be zero at the current
      // vertical position (j-1)
      1. l=-j++

      // compare j to stopping criteria, exit if j > m+1
      2. j < m+2

       -- loop over s --

       // puts current char in c and increments string counter
       3. c = *s++

       // outputs character as follows:
       // c == 0 (end of string), output newline
       // c != 0 (middle of string)
       //  l == 0 (character at current vertcial position), output c
       //  l != 0 (character not at current vertical position), output space
       4. putchar(c?l?32:c:10)

       // c != 0, this updates the vertical position for the next character
       // c = SPC or C = TAB -> lower (l increases by 1)
       // c = "aeiouAEIOU" -> higher (l decreases by 1)
       5a. l-=(c&=223)&&c-9?!!strchr("AEIOU",c):-1

       -- loop over s ends --

      // c == 0, this resets the string pointer s for next loop over s
      //         algorithm (see rest of the explanation at p == true)
      5b. p=s=b

     -- loop over j ends --
  */

  for(;
      j<m+2;
      p?putchar(c?l?32:c:10):
    l<j?j=l:l>m?m=l:0,
      l-=c?(c&=223)&&c-9?!!strchr("AEIOU",c):-1:
       (p=s=b,l+j++))
    c=*s++;
}

```

# Answer
> 0 votes
## Haskell (within ANSI terminal), 75 bytes

```
("\27[2J"++).(h=<<)
h ' '="\27[B "
h c|elem c"aeiouAEIOU"=c:"\27[A"
h c=[c]

```

Usage example: `putStr $ ("\27[2J"++).(h=<<) $ "bcdef ghijkl"`

This uses ANSI escape codes to move the cursor up and down.

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


# Question
Title: Find the last position in a matrix walking like a spiral
This question will be deleted soon, do not read/answer it

### Introduction

Given one matrix `A x A` and a number of movements `N`.

You will need to walk like a spiral starting in `(1; 1)`:

1. right while possible, then
2. down while possible, then
3. left while possible, then
4. up while possible, repeat until got `N`.

### Challenge

You can only take as input the numbers `A` and `N`.

You must output the final `(row; column)` after walking `N` steps in the conditions explained above. You can not invert the output order.

You can use indexes starting with zero as well. Just state it in your answer.

Program or function allowed.

This is , shortest answer in bytes wins.

### Sample

For input (`A = 8; N = 54`).

The output should be (`5; 6`).

### Another samples

```
input: A=8, N=64
output: [5, 4]

```

---

```
input: A=15, N=14
output: [1, 14]

```

---

```
input: A=26, N=400
output: [22, 9]

```

---

```
input: A=1073741824, N=1152921504603393520
output: [536871276, 536869983]

```

### Restrictions

1 \<= A \<= 230

1 \<= N \<= (A2 **OR** the below higher number supported in your language).

---

And, if you want a generic formula.

# Answer
> 2 votes
# MATL, 24 bytes

This works in release 16.0.0 of the language, which predates the challenge.

```
2^Q6Y3GYLG2\?!P!}P]-=2#f

```

Output is 1-based, as in the examples.

`A^2` and `N` are limited to 2^53 as per the language's default data type (`double`). In addition, since the whole matrix is being generated, memory will limit `A` to significantly lower values.

**Try it online!** (In the online version I have changed the order of `G` and `6Y3` so it works in the new 16.1.0 release)

### Explanation

This uses MATL's builtin for generating an outward spiral. To make it inward, a subtraction and a reversal are needed. The direction of reversal depends on whether `A` is odd or even.

```
2^Q     % take input A implicitly. Compute A^2+1
6Y3GYL  % outward spiral of side length A
G2\     % is A odd?
?       % if so
  !P!   %   flip matrix horizontally
}       % else
  P     %   flip matrix vertically
]       % end if
-       % compute A^2+1 minus the matrix element-wise, so (1,1) contains 1
=       % take input N implicitly. Set matrix entry that contains that value to true
2#f     % row and column index of that true value

```

---
Tags: code-golf, matrix
---


title: Draw a spiral in a box

text:
# Question
Title: Draw a spiral in a box
This geometric spiral looks complicated, but it's fairly simple to draw; take the following box:

Draw a straight line between the corner of the box and some set distance above the next corner counter-clockwise.

Continue this pattern inward, always staying that set distance away from the corner of the next line. Here's a few more lines in.

As you can see, as the pattern continues, the spiral approaches the center and the boxes you draw begin to rotate. Note that the distance remains constant, regardless of angle.

## The Challenge

The Inspiration (and also thanks to the wonderful person who introduced me to this concept \<3)

Given a numerical (possibly fractional) input from 1 to 25, write an image to disk that uses this pattern or display the output on the screen, where the distance from each corner is the distance of one initial side of the box divided by the input. Continue the pattern inward until the distance from the corner specified is longer than the length of the next side.

## Rules

* You may not use built-ins for this spiral creation, but you may use image processing builtins.
* If you write to disk, you must output an image in any of .jpg, .gif, .tiff, .pbm, .ppm, and .png.
* The initial side length must be at least 500 pixels.
* The initial corner may be whichever you choose.
* As always, the Standard Loopholes are disallowed.

# Answer
# Shoes (Ruby) 163 bytes

Shoes is a ruby-based GUI toolkit.

```
Shoes.app{n=ask('').to_f
r=s=5E2
a=[0,s*i="i".to_c,s*i+s,s,0]
(q=a[-3]-a[-4]
r=q.abs/s*n
a<<a[-4]+q/r)while r>1
1.upto(a.size-1){|j|line *(a[j-1].rect+a[j].rect)}}

```

**Ungolfed**

```
Shoes.app{
  n=ask('').to_f                 #Open a dialog box with no message, get n from user
  r=s=5E2                        #Initialize s to sidelength=500. r can be initialized to any vale, we use the same one for convenience.
  a=[0,s*i="i".to_c,s*i+s,s,0]   #intialize array a with 5 points needed to draw a square, in complex number format (first point=0 is duplicated.)

  (
    q=a[-3]-a[-4]                #find the vector from point plotted 4 before to the following point (plotted 3 before)
    r=q.abs/s*n                  #r is the scale factor
    a<<a[-4]+q/r                 #add a new point derived from a[-4] by moving toward a[-3] by a distance s/n
  )while r>1                     #break loop when length of line is less than s/n

  1.upto(a.size-1){|j|           #for all points except 1st and last one
    line *(a[j-1].rect+a[j].rect)#take the two complex numbers correspondimg to the current and previous point,
  }                              #convert to 2-element arrays (rectangular coordinates
}                                #combine to make a 4-element array, use * to splat into 4 parameters, and draw using the line method.

```

**Outputs n=4 and n=25**

Note that the shape always ends in a triangle, which collapses further to a line. Replacing `size-1` with `size` makes no difference to the appearance of the output and would save 2 bytes, but I left it in for theoretical correctness.

**Output n=300**

Inspired by a comment by OP, the higher numbers do look great!
> 13 votes

# Answer
# Java, ~~1056~~ ~~1005~~ ~~985~~ ~~948~~ ~~522~~ ~~508~~ ~~507~~ ~~504~~ ~~502~~ ~~501~~ ~~493~~ ~~492~~ ~~488~~ ~~474~~ ~~465~~ 458 bytes

```
import java.awt.*;interface G{static void main(String[]a){new Frame(){int s=499,o=s,e,i,x,y;{o/=new Float(a[0]);add(new Component(){public void paint(Graphics g){g.drawRect(0,0,s,s);int[]p={s,s,s,0,0,0,0,s};for(double d=s,t;d>o;t=o/d,i=e*2,x=(int)((1-t)*p[i]+t*p[(2+i)%8]+.5),y=(int)((1-t)*p[1+i]+t*p[(3+i)%8]+.5),g.drawLine(p[(6+i)%8],p[(7+i)%8],x,y),p[i]=x,p[1+i]=y,e=++e%4,i=e*2,x=p[(2+i)%8]-p[i],y=p[(3+i)%8]-p[1+i],d=Math.sqrt(x*x+y*y));}});show();}};}}

```

Thanks to CoolestVeto and ECS for yet other ways to reduce size. :-)
> 4 votes

# Answer
# Groovy, ~~412~~ ~~411~~ ~~403~~ 398 bytes

```
import java.awt.*
new Frame(){
def s=499,o=s/(args[0]as float),e=0,i,a,b,d,t
{add new Component(){void paint(Graphics g){g.drawRect 0,0,s,s
p=[s,s,s,0,0,0,0,s]
for(d=s;d>o;d=Math.sqrt(a*a+b*b)){t=o/d
i=e*2
a=(int)((1-t)*p[i]+t*p[(2+i)%8]+0.5)
b=(int)((1-t)*p[1+i]+t*p[(3+i)%8]+0.5)
g.drawLine p[(6+i)%8],p[(7+i)%8],a,b
p[i]=a
p[1+i]=b
e=++e%4
i=e*2
a=p[(2+i)%8]-p[i]
b=p[(3+i)%8]-p[1+i]}}}
show()}}

```
> 1 votes

---
Tags: code-golf, graphical-output
---


title: Draw an indexed fractal

text:
# Question
Title: Draw an indexed fractal
## Introduction

In this challenge, a 2×2 matrix is indexed like this:

```
0 1
2 3

```

We define a family of fractal-like patterns `F(L)`, where `L` is a length-`n` list of these indices and `F(L)` has size `2<sup>n</sup>-1 × 2<sup>n</sup>-1`.

* If `L == []`, then `F(L)` is the 1×1 pattern `#`.
* If `L != []`, then `F(L)` is constructed as follows. Let `P` be the pattern obtained from `L` with first element removed. Take four grids of size `2<sup>n-1</sup>-1 × 2<sup>n-1</sup>-1` filled with periods `.`, and replace the grid indexed by `L[0]` with the pattern `P`. Then, glue the grids together using one layer of hashes `#` between them. Here are diagrams for the four cases:

```
L[0]==0  L[0]==1  L[0]==2  L[0]==3
   #...  ...#     ...#...  ...#...
[P]#...  ...#[P]  ...#...  ...#...
   #...  ...#     ...#...  ...#...
#######  #######  #######  #######
...#...  ...#...     #...  ...#
...#...  ...#...  [P]#...  ...#[P]
...#...  ...#...     #...  ...#

```

## Example

Consider the input `L = [2,0]`. We begin with the 1×1 grid `#`, and traverse `L` from the right. The rightmost element is `0`, so we take four copies of the 1×1 grid `.`, replace the first one by `#`, and glue them together with hashes. This results in the 3×3 grid

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

```

The next element is `2`, so we take four copies of the 3×3 grid of `.`s, and replace the third one with the above grid. The four grids are

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

```

and gluing them together with `#`s results in the 7×7 grid

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

```

This is our final output.

## Input

Your input is a list `L` of the indices `0, 1, 2, 3`. You can take it as a list of integers, or a string of digits. Note that it may be empty, and it may contain duplicates. The length of `L` is at most 5.

## Output

Your output is the pattern `F(L)` as a newline-delimited string.

## Rules and scoring

You can write a full program or a function. the lowest byte count wins, and standard loopholes are disallowed.

## Test cases

```
[]
#

[0]
##.
###
.#.

[3]
.#.
###
.##

[2,0]
...#...
...#...
...#...
#######
##.#...
####...
.#.#...

[1,1]
...#.##
...####
...#.#.
#######
...#...
...#...
...#...

[1,2,0]
.......#...#...
.......#...#...
.......#...#...
.......########
.......###.#...
.......#####...
.......#.#.#...
###############
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......

[3,3,1]
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
###############
.......#...#...
.......#...#...
.......#...#...
.......########
.......#...#.##
.......#...####
.......#...#.#.

[0,1,2,3]
.......#...#...#...............
.......#...#...#...............
.......#...#...#...............
.......#########...............
.......#.#.#...#...............
.......#####...#...............
.......#.###...#...............
################...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
###############################
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............

[0,0,1,2,3]
.......#...#...#...............#...............................
.......#...#...#...............#...............................
.......#...#...#...............#...............................
.......#########...............#...............................
.......#.#.#...#...............#...............................
.......#####...#...............#...............................
.......#.###...#...............#...............................
################...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
################################...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
###############################################################
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................

```

# Answer
## CJam, ~~59~~ ~~47~~ ~~43~~ ~~41~~ 40 bytes

*Thanks to Sp3000 for saving 1 byte.*

```
Sal~W%{_Bff|a4*I@t2/{zSf*z}:F%F}fI3ff+N*

```

Test it here.

### Explanation

*Slightly outdated. Will fix later.*

All the dimension reorderings of 4D lists are making me dizzy...

This code implements the specification very literally, using the iterative algorithm from the example section instead of its recursive definition.. One major golfing trick is that I'm using spaces instead of `#` during the computation and only replace them with `#` at the end, which simplifies the code in one place and allows me to use `S` instead of `'#` or `"#"` in several.

```
Sa       e# Push [" "], i.e. a 1x1 grid containing only a space as the
         e# initial fractal.
l~       e# Read and evaluate input.
W%       e# Reverse the list.
{        e# For each list element, assigning the element to variable I...
  _      e#   Duplicate the grid.
  Eff|   e#   Map (OR 14) over each character in the grid, turning spaces into
         e#   periods and leaving periods unchanged.
  a4*    e#   Create an array with four copies of this cleared grid.
  I@t    e#   Replace the Ith element in this list with the previous grid.
  2/     e#   Split this array into a 2x2 grid of subgrids...
         e#   Now it's getting a bit weird... we've got 4 dimensions now, which are:
         e#    - Rows of the 2x2 meta-grid.
         e#    - Cells in each row of the 2x2 meta-grid (i.e. subgrids).
         e#    - Rows of each subgrid.
         e#    - Characters in each row of each subgrid.
  :z     e#   Transpose each outer row, i.e. swap dimensions 2 and 3.
         e#   We've now got in each row of the meta-grid, a list of pairs of
         e#   corresponding rows of the subgrids.
  Sff*   e#   Join those pairs of rows with a single space each. We're now down
         e#   to three dimensions:
         e#    - Rows of the 2x2 meta-grid.
         e#    - Rows of each 1x2 block of the meta-grid.
         e#    - Characters in each row of those blocks.
  :z     e#   Transpose the blocks, i.e. turn the 1x2 blocks into a list of
         e#   columns of their characters.
  z      e#   Transpose the outer grid, i.e. turn it into a list of pairs of
         e#   corresponding columns in the two 1x2 blocks.
  Sf*    e#   Join each pair of columns with a single space. We've now got the
         e#   new grid we're looking for, but it's a list of columns, i.e. transposed.
  z      e#   Fix that by transposing the entire grid once more.
}I
N*       e# Join the rows of the grid with linefeeds.
S'#er    e# Replace all spaces with #.

```
> 6 votes

# Answer
# MATL, ~~42~~ 41 bytes

```
'.#'4:He!XIiP"Iq@=wX*1X@WZ(l5MY(]3Lt3$)Q)

```

**Try it online!**

### Explanation

This works iteratively using a Kronecker product to extend the array in each iteration. The array is built with `0` and `1` instead of `.` and `#`, and at the end they are replaced by the appropriate characters.

There will be as many iterations as the input size. Input is processed from right to left. Iteration index starts at `1`.

Using the example in the challenge, with input `[2,0]`, the array is initiallized as

```
1 2
3 4

```

This corresponds to the initial `1` (`#`) extended by one row and one column, whose purpose will be clear later. The values in those columns are not important, as they will be overwritten; they could equally be ones:

```
1 1
1 1

```

At each iteration, the existing array is Kronecker-multiplied by a 2×2 zero-one array that contains `1` at the position indicated by the current entry of the input, and `0` at the other entries. In the example at iteration *i* = 1, since the rightmost input entry is `0`, the zero-one array is

```
1 0
0 0

```

and the Kronecker product of these two arrays is

```
 1 1 0 0
 1 1 0 0
 0 0 0 0
 0 0 0 0

```

Next, the row and column with index `2^i` are filled with ones:

```
 1 1 0 0
 1 1 1 1
 0 1 0 0
 0 1 0 0

```

The first three rows and columns constitute the result of the first iteration. As before, there are an extra row and column, which are useful for extending the array in the next iteration.

At iteration *i* = 2, since the current input value contains `2` the array above is Kronecker-multiplied by

```
0 0
1 0

```

which gives

```
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 1 1 0 0 0 0 0 0
 1 1 1 1 0 0 0 0
 0 1 0 0 0 0 0 0
 0 1 0 0 0 0 0 0

```

Filling the `2^i`-th row and column with ones gives

```
 0 0 0 1 0 0 0 0
 0 0 0 1 0 0 0 0
 0 0 0 1 0 0 0 0
 1 1 1 1 1 1 1 1
 1 1 0 1 0 0 0 0
 1 1 1 1 0 0 0 0
 0 1 0 1 0 0 0 0
 0 1 0 1 0 0 0 0

```

Since this is the last iteration, the extra row and column are removed:

```
 0 0 0 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 1 0 0 0
 1 1 1 1 1 1 1
 1 1 0 1 0 0 0
 1 1 1 1 0 0 0
 0 1 0 1 0 0 0

```

and the character substitution is done to produce the final result:

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

```

Detailed description of the code follows:

```
'.#'      % Push this string. Will be indexed into
4:He!     % Push 2×2 array [1 2; 3 4]
XI        % Copy it into clipboard I
iP        % Input array and reverse it
"         % For each entry of the reversed input
  I       %   Push [1 2; 3 4] from clipboard I
  q       %   Subtract 1 to yield [0 1; 2 3]
  @=      %   Compare with current entry of the input. Gives 2×2 array
          %   with an entry equal to `1` and the rest `0`
  wX*     %   Swap. Kronecker product
  1       %   Push 1
  X@      %   Push iteration index, i
  W       %   Compute 2^i
  Z(      %   Write 1 into column 2^i
  l       %   Push 1
  5M      %   Push 2^i again
  Y(      %   Write 1 into row 2^i
]         % End for each
3Lt       % Push [1, -1j] (corresponding to index 1:end-1) twice
3$)       % Apply index. Removes last row and column
Q         % Add 1. Gives an array of values 1 and 2
)         % Index into initial string

```
> 3 votes

# Answer
## Haskell, ~~123~~ 122 bytes

```
unlines.foldr(#)["#"]
n#p=zipWith(++)(r++h:t)$('#':)<$>u++h:s where b='.'<$p<$p;h='#'<$p;(r:s:t:u:_)=drop n$cycle[p,b,b,b]

```

Usage example:

```
*Main> putStr $ (unlines.foldr(#)["#"]) [2,3,1]
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
###############
...#...#.......
...#...#.......
...#...#.......
########.......
...#.###.......
...#####.......
...#.#.#.......

```

How it works:

```
                ["#"]      -- starting with "#"
        foldr(#)           -- fold the function # from the right into the input
unlines                    -- and join the result with newlines

n#p=                       -- helper function #
                           -- n: next index, p: fractal so far
    zipWith(++)            -- join the left and right part elementwise
       (r++h:t)            -- left part
       ('#':) <$> u++h:s   -- right part (prepend '#' to each line for vertical
                           -- separator

                           -- helper
b='.'<$p<$p                -- b is a blank square of the same size as p
h='#'<$p                   -- h is a line of '#' of the same length as p
(r:s:t:u:_)=               -- drop the first n elements of the infinite
    drop n$cycle[p,b,b,b]  --   list [p,b,b,b,p,b,b,b,p,b,b,b,...] and
                           --   assign the next 4 element to r,s,t,u.
                           --   As r,s,t,u are always inserted at the
                           --   same position in the fractal, we get the
                           --   variants by assigning different values.

```
> 2 votes

# Answer
## JavaScript (ES6), ~~171~~ 152 bytes

```
([d,...a],h=`#`,r=`replace`)=>d<4?(s=f(a)[r](/.+/g,s=>(t=s[r](/./g,`.`),d&1?t+h+s:s+h+t)),t=s[r](/.+/g,w=t+h+t),w=`
${w[r](/./g,h)}
`,d&2?t+w+s:s+w+t):h

```

Takes the result of the recursive call, then replaces each line with itself plus a hash plus a string of dots of the same length, in reverse order if necessary, then from that partial result creates a string of dots except for the newlines and central column of hashes, and also a string of hashes with surrounding newlines, then joins those three strings together in the appropriate order.
> 1 votes

# Answer
# Ruby, ~~143~~ 134 bytes

An anonymous function.

1 byte saved by a rearrangement of the first line. 6 bytes saved by changing the way z is incremented from a formula to a table. 2 bytes saved by eliminating varable `w`.

```
->a{r=-1+u=2<<a.size
s=(?.*r+$/)*r
a<<0
z=r*u/2-1
a.each{|i|r/=2
(-r..r).each{|j|s[z+j]=s[z+j*u]=?#}
z+=-r/2*[u+1,u-1,1-u,-u-1][i]}
s}

```

**Ungolfed in test program**

```
f=->a{
  r=w=(u=2<<a.size)-1        #w=length of line excluding newline, u=length of line including newline.
  s=(?.*w+$/)*w              #initialize string s with w rows of w dots terminated by newlines.
  z=w*u/2-1                  #z is the centre of the fractal
  a<<0                       #add a dummy value to the end of a
  a.each{|i|                 #for each element in a
    r/=2                     #r is the radius of the current iteration: ....15,7,3,1
    (-r..r).each{|j|         #for j=-r to r
      s[z+j]=s[z+j*u]=?#     #overwrite . with #, forming horizontal and vertical lines
    }
    z+=-r/2*(u+1)+           #move z to centre of upper left quarter (where it should be if i=0)
      i%2*(q=r+1)+           #move across if i=1,3
      i/2%2*q*u              #and down if i=2,3
  }
s}                           #return string

puts $/,f[[]]

puts $/,f[[0]]

puts $/,f[[3]]

puts $/,f[[2,0]]

puts $/,f[[1,1]]

puts $/,f[[1,2,0]]

puts $/,f[[3,3,1]]

puts $/,f[[0,1,2,3]]

puts $/,f[[0,0,1,2,3]]

```
> 1 votes

# Answer
# Ruby, 150 bytes

Anonymous function. Uses a recursive call to build a list of strings, one string per line, then joins them all together at the end.

```
->i{f=->l{s=2**l.size-1;g=[[?.*s]*s]*4;m=->x,y{x.zip(y).map{|a,b|a+?#+b}}
s<1?[?#]:(g[l.shift]=f[l];m[*g[0,2]]+[?#*(2*s+1)]+m[*g[2,2]])}
f[i].join"
"}

```
> 0 votes

# Answer
# Python 3.5, 1151 bytes:

Not much of a code golf, but oh well. Will try to prune it more over time where I can.

```
def x(s):
 y=[''];l=['#'];k=[' ']
 for z in s[::-1]:y.append(z)
 y=y[::-1]
 for h in range(len(y)):
  if y[-1]!='':u=(int(y.pop())&3)
  else:u=y.pop()
  if len(l)<2:k.append(u);p=((2**(len(k)-1))-1);l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
  else:
   if len(l)>2:del l[0]
   p=((2**(len(k)-1))-1);a=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%((p*2)+2)==0 and _!=(((p*2)+2)*(p))];b=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%(int(((p*2)+2)/2))==0 and _!=(int(((p*2)+2)/2)*((p)*2))and _ not in[g for i in a for g in i]];W=[g for i in a[:len(a)-(int(len(a)/2)):1]for g in i];B=[g for i in b[:len(b)-(int(len(b)/2)):1]for g in i];C=[g for i in a[len(a)-(int(len(a)/2)):len(a):1]for g in i];T=[g for i in b[len(b)-(int(len(b)/2)):len(b):1]for g in i];f=list(l[1])
   for i in list(''.join(l[0].split())):
    if u==0:f[W[0]]=i;del W[0]
    elif u==1:f[B[0]]=i;del B[0]
    elif u==2:f[C[0]]=i;del C[0]
    elif u==3:f[T[0]]=i;del T[0]
   del l[0];k.append(u);p=((2**(len(k)-1))-1);l.append(''.join(f));l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
 print(l[-2])

```

A pretty naive way to do this, but, nonetheless, currently works perfectly and, as you can see, uses **no** external modules/libraries. Additionally, it can take on *way* more than 5 items in the provided list `s` without losing any accuracy (that is, if your hardware can handle it). It satisfies all the requirements, and I could not be happier with what I got. :)

It can also now not only accept any number within the range `0=>3` as any of the values, but *any number*, period, thanks to the `&` bitwise operator ! You can read more about them here. Now, for instance, `[4,4,1,2,3]` as the input list is the *same* as `[0,0,1,2,3]`.

**Note:** Input *must* be provided as a list

# Ungolfed with explanation:

```
def x(s):
 # Create 3 lists:
 # `y` is for the values of `s` (the list provided) and an empty element for the
 # first pattern
 # `l` is reserved for the pattersn created through each item in list `y`
 # `k` is created for the value of `p` which is the main value through which the
 # pattern is created.
 y=[''];l=['#'];k=[' ']
 # Reverse s, and then add each element from `s` to `y`
 # (in addition to the empty element)
 for z in s[::-1]:
     y.append(z)
 # `y` should now equal the list created, but reversed
 # If not reversed, then, if, for instance, the input is `0,1,2` and list `y`
 # therefore contains `'',2,1,0`, the empty element will be called at the end,
 # which is NOT what we want.
 y=y[::-1]
 # The main loop; will be iterated through the length of `y` number of times
 for h in range(len(y)):
  # Here is where each element from the end of `y` is recieved as `u` for
  # use in the pattern in each iteration.
  # As you can also see, a bitwise operator (`&`) is used here so that
  # ALL numbers can be accepted. Not just those in the range `0-4`.
  # However, that will happen only if the value of y[-1] (the last elment in y) is
  # NOT ''.
  if y[-1]!='':
      u=(int(y.pop())&3)
  else:
      u=y.pop()
  # If the length of list `l` is less than 2
  # (which means it only contains `#`), then do the following:
  if len(l)<2:
      # Append `u` to `k`
      k.append(u)
      # Use the length of `k` as `n` in the operation `(2^(n-1)-1)` to get the
      # length of the dot filled part of the new pattern.
      p=((2**(len(k)-1))-1)
      # Add that pattern to the list (currently empty,
      # i.e. containing no other pattern in any other quadrant)
      l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
  # Now, if the length of l is >=2, do the following:
  else:
   # If the length of l is >2, then delete the first element in list `l`
   # (this will happen only once, when the `#` is still the first element)
   if len(l)>2:
       del l[0]
   # Again, use the length of `k` as `n` in the operation `(2^(n-1)-1)`
   # to get the length of the dot filled part of the pattern.
   p=((2**(len(k)-1))-1)
   # Create a list with all the index values of all the dot elements on the left hand
   # side of the grid l[-1], and the index value + i where i is every integer in
   # the range `0-p` (this way, it will create lists within a list, each
   # which contain `p` number of integers, which are all indexes of all the dots on
   # the very left side of the grid)
   a=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%((p
      *2)+2)==0 and _!=(((p*2)+2)*(p))]
   # Create another list with all the index values of the dots using the same
   # strategy as above, but this time, those in the right half of the grid.
   b=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%(int(((p*2)+2)/2))==0
      and _!=(int(((p*2)+2)/2)*((p)*2))and _ not in[g for i in a for g in i]]
   # Create 4 lists, each containing index values specific to each of the
   # 4 quadrants of the grid.
   # W is the list, based on A, containing all the indexes for the 1st quadrant of
   # the grid in l[-1] containing dots (index 0 in the grid)
   W=[g for i in a[:len(a)-(int(len(a)/2)):1]for g in i]
   # B is the list, this time based on b, containing all indexes for the 2nd
   # dot-filled quadrant of the grid l[-1] (index 1 in the grid)
   B=[g for i in b[:len(b)-(int(len(b)/2)):1]for g in i]
   # C is the list, also, like W, based on a, containg all the index values for
   # the 3rd dot-filled quadrant of the grid in l[-1] (index 2 in the grid)
   C=[g for i in a[len(a)-(int(len(a)/2)):len(a):1]for g in i]
   # T is the final list, which, also like B, is based on b, and contains all the
   # index values for the final (4th) dot-filled quadrant of the grid in l[-1]
   T=[g for i in b[len(b)-(int(len(b)/2)):len(b):1]for g in i];f=list(l[1])
   # Finally, in this `for` loop, utilize all the above lists to create the new
   # pattern, using the last two elements in list `l`, where each character of grid
   # l[-2] (the second to last element) is added to the correct index of grid l[-1]
   # based on the value of `u`
   for i in list(''.join(l[0].split())):
    if u==0:
        f[W[0]]=i
        del W[0]
    elif u==1:
        f[B[0]]=i
        del B[0]
    elif u==2:
        f[C[0]]=i
        del C[0]
    elif u==3:
        f[T[0]]=i
        del T[0]
   # Delete the very first element of `l`, as it is now not needed anymore
   del l[0]
   # Append `u` to list`k` at the end of the loop this time
   k.append(u)
   # Update the value of `p` with the new value of length(k)
   p=((2**(len(k)-1))-1)
   # Append the new patter created from the for-loop above to list `l`
   l.append(''.join(f))
   # Append a new, empty pattern to list `l` for use in the next iteration
   l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
 # When the above main loop is all finished, print out the second-to-last elment in
 # list `l` as the very last element is the new, empty grid created just in case
 # there is another iteration
 print(l[-2])

```

# Broader & far more visually appealing explanation:

For a broader and far more visually appealing explanation, consider the second time going through the "main"-loop in the above code, in which the input list is `[0,2]`. In this case, the elements in the "main" list `l` would be:

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

```

and

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

```

and list `y` would only contain `0`. Taking advantage of Python's way of indexing the last element of grid `l[-1]`, we can label the very *left* elements of the grid like so:

```
 0 ...#...\n 7
 8 ...#...\n 15
16 ...#...\n 23
   #######\n <- Ignore this as it is nothing but `#`s and a new line
32 ...#...\n 39
40 ...#...\n 47
48 ...#...\n 55

```

What pattern do you see? Every index on the very left of the grid is a multiple of 8, and since, using the equation `2^(n-1)-1` yields the length of each segment of dots in the grid, we can do `((2^(n-1)-1)*2)+2` to find the length of the top edge of the grid as a whole (+2 to include the middle `#`s and the `\n` at the end). We can use that equation, which we will call `i` to find the index values of each element on the left side of a grid of any size by creating a list, and appending to the list every integer, which we will call `_`, in the range `0=>length of grid l[-1]`, such that that item is a multiple of `i`, AND also such that `_` does NOT equal `i*(2^(n-1)-1)`, so that we can exclude the middle segment of `#`s separating the top half from the lower half. But we want ALL the dot elements from the left, and not only the elements on the very left side. Well, there is a fix to that, and that would be to simply append to the list a list containing `i+h` where h is every integer in the range `0=>2^(n-1)` each time a value from range `0=>length of grid l[-1]` is added to the list, so that each time, there will be as many number of values added to the list as the length of one quadrant of dots. And that is list `a`.

But now, how about the dots on the right half? Well, let us look at the indexing a different way:

```
   0 ...# 4  ...\n 7
   8 ...# 12 ...\n 15
  16 ...# 20 ...\n 23
     #######\n <- Ignore this as it is nothing but `#`s and a new line
  32 ...# 36 ...\n 39
  40 ...# 44 ...\n 47
  48 ...# 52 ...\n 55

          ^
          |

          These are the values we are looking at now

```

As you can see, the values now in the middle are those that we need, as they are the *beginning* of the index of every segment of dots on the right hand side of the grid. Now, what is the pattern here? Well, if it's not already obvious enough, now the middle values are all multiples of `i/2`! With that information, we can now create another list, `b`, to which the multiples of `i/2` are added from the range `0=>length of grid l[-1]` such that each integer from that range, which we will again call `_`, is NOT equal to `(i/2)*(p*2)` to exclude the line of `#`s separating the top and lower halves, AND such that _ is NOT already in list a, since we don't really need 8,16,32,etc. in list `b`. And now, again, we don't only want those specific indexes. We want ALL the dot characters on the right side of the grid. Well, just like we did in list `a`, here we can also add to list `b` lists of `_+h` where `h` is each integer in the range `0=>2^(n-1)`.

Now, we have both lists `a` and `b` packed and ready to go. How would we bring these together now? This is where lists `W`, `T`, `G`, and `C` come in. They will hold the indexes to each specific quadrant of dots in grid `l[-1]`. For instance, let us reserve list `W` as the list for all the indexes equal to quadrant 1 (index 0) of the grid. In this list, we would then add the first `2^(n-1)` lists from list `a`, since list `a` contains all the indexes for dots in the left half of the grid, and then split them all up so that `W` now contains `(2^(n-1))*(2^(n-1))` elements. We would do the same for list `T`, but with the difference that `T` would contain elements from list `b`, since `T`is reserved for quadrant 2 (index 1). List `G` would be the same as list `W`, except it would contain the rest of the elements from list `a`, and list `C` is the same as list `T`, except it now contains the rest of the elements from list `b`. And, that's it! We now have out index values for *every* quadrant containing dots in the grid, all split up into four lists corresponding to each quadrant. We can now use these 4 lists (W,T,G,C) to tell the program which characters it should replace in grid `l[-1]` with each character from grid `l[0]`, which is the very first element of list `l`. Since the value is `0` here, it would replace all the dots in the first quadrant (index 0) with grid `l[0]` utilizing list `W`.

Therefore, we finally have the following:

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

```

Whew! Long process, isn't it? However, it works perfectly, and, again, I could not be happier. :)
> 0 votes

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


# Question
Title: Need help golfing Python 3 code to calculate volume & surface of spheroids in <150 bytes
I want to write a function `golf(C, A)` that takes the height (`C = 2*c`) and the width (`A = 2*a`) of an oblate (left image) or prolate (right image) spheroid or a sphere as parameters and returns the volume `V` and the surface area `S` of the shape as tuple. The output must be rounded to two decimal places.

All input and output numbers are floating point decimals.
The input numbers (`A` and `C`) are guaranteed to be greater than 0 and lower than 100.

Here are some example calls of the function (`golf(C, A)`) in Python 3 and the expected outputs given as test cases:

```
golf(4, 2)  # expected output (8.38, 21.48)
golf(2, 2)  # expected output (4.19, 12.57)
golf(2, 4)  # expected output (16.76, 34.69)

```

The challenge requires my code to be smaller than 150 characters.

I could not manage to solve it myself yet, my best solution in Python 3 still takes 220 characters:

```
from math import *
def golf(C,A):
 c,a,V=C/2,A/2,pi/6*A*A*C;F=c*c/a**2;E=sqrt(1-(F if a>c else 1/F));S=4*pi*a*a if a==c else 2*pi*a*a*(1+(((1-E**2)/E)*atanh(E)if a>c else(c/(a*E))*asin(E)))
 return round(V,2),round(S,2)

```

---

The necessary formulas are taken from Wikipedia: Spheroid, here's a summary:

***Vall spheroids = 4 π/3 a²c = π/6 A²C*** as ***A=2a*** and ***C=2c***.

---

This challenge was originally from checkio.org and got refactored into a code-golf challenge for empireofcode.com.

# Answer
> 7 votes
# 122 bytes

```
from cmath import*
def golf(C,A):e=sqrt(1-A*A/C/C);return round(pi/6*A*A*C,2),round(pi*A*abs(A+(e and C*asin(e)/e-A)/2),2)

```

The sphere can be special-cased by returning surface area **πA²** if **e = 0**.

While there are two different formulae for oblate and prolate spheroids, they are mathematically equivalent. If the involved operations support complex numbers, each formula can be used for both cases.

Since `asin(e)/e` will return a complex number of the form `x+0j` for prolate spheroids, `abs` can be used to turn it into the float `x`.

---
Tags: code-golf, math, tips, geometry, python
---


title: Roman Numeral Line Segments

text:
# Question
Title: Roman Numeral Line Segments
Write a program or function that accepts an integer in the range 1..3999 as input and returns the number of line segments required to express that integer in standard Roman numerals (so you would use XL but not VM). Examples:

```
   1 -> 1
   4 -> 3
   5 -> 2
   9 -> 3
  10 -> 2
  40 -> 4
  50 -> 2
  90 -> 3
 100 -> 1
 400 -> 3
 500 -> 2
 900 -> 5
1000 -> 4

```

Roman number conversion builtins *are* permitted, but you can solve the problem without them by repeatedly subtracting the largest remaining number from the above list. Example: 1234 = 4 + 1 + 1 + 2 + 2 + 2 + 3 = 15.

This is , so the shortest program wins.

# Answer
> 2 votes
# Pyth, ~~92~~ ~~76~~ 70 bytes

```
KsMc."/9hæ²z³Þ§ªW×Oû[Tnè,O¤"\/WQ=Q-Q=Nef!>TQ%2K aY@KhxKN;sY

```

Try it here!

Thanks to @FryAmTheEggman for some string packing suggestions which saved me some bytes!

I am still wondering if there is a mathematical way of encoding this list. Will try to figure something out.

# Explanation

This uses the given algorithm. `K` contains the given list with the numbers and the corrosponding number of line segments in alternation. This list gets constructed by splitting a packed string, which gets decoded to `0/0/1/1/4/3/5/2/9/3/10/2/40/4/50/2/90/3/100/1/400/3/500/2/900/5/1000/4`, on `/` and mapping each element to an integer.

```
KsMc."..."\/WQ=Q-Q=Nef!>TQ%2K aY@KhxKN;sY    # Q = input

   c."..."\/                                 # split the string on /
KsM                                          # map every number to int and assign to K
            WQ                               # while Q != 0
                     f    %2K                # only take every 2nd element of K and filter with T
                      !>TQ                   # T <= Q
                  =Ne                        # Take the last element of that and assign that to N
              =Q-Q                           # Q = Q - N
                                   xKN       # index of the first occurence of N in K
                                  h          # increment that index because we want the line segments
                              aA@K           # get the line segment from that index and append that to Y
                                      ;sY    # end the loop and print the sum of all line segments in Y

```

# Answer
> 4 votes
**C, ~~148~~ 129 chars**

```
d,x,n[]={1000,900,500,400,100,90,50,40,10,9,5,4,1,4,5,2,3,1,3,2,4,2,3,2,3,1};f(c){while(d+=(c/n[x])*n[x+13],c%=n[x++]);return d;}

```

My first code-golf :^). Since the question states I can use a function, I have changed main to a function to trim some chars (most importantly: pass c as parameter rather scanf)

unpacked

```
d,x,n[]={1000,900,500,400,100,90,50,40,10,9,5,4,1,4,5,2,3,1,3,2,4,2,3,2,3,1};
f(c){
  while(d+=(c/n[x])*n[x+13],
        c%=n[x++]);
  return d;
}

```

# Answer
> 2 votes
# Mathematica, ~~80~~ 72 bytes

```
Tr[Characters[#~IntegerString~"Roman"]/.{"I"|"C"->1,"M"->4,_String->2}]&

```

Anonymous function that just converts numbers to Roman numerals, replaces each character with its number of segments, and takes the total.

# Answer
> 2 votes
# Retina, 128 bytes

```
.+
$*
1{1000}
t'
1{900}
td
1{500}
d
1{400}
t
1{100}
'
1{90}
t
1{50}
d
1{40}
t'
1{10}
d
1{9}
t
1{5}
d
1{4}
t
1
'
t
d'
d
''
'+
$.0
```

Simple replacing until there's nothing left to replace. Then the apostrophes are counted and that's our number of line segments.

If input and output in unary are allowed, it's 115 bytes (although who would want to type 1234 ones?).

Try it online!
Try it online! (unary IO)

# Answer
> 2 votes
# Python 3, 95 bytes

```
def f(a,b=0):
 for e in'᝴ᔝ஺ॣəȟĮô>9 ':e=ord(e);d=e//6;b+=a//d*(e%6);a%=d
 return b

```

The Unicode string consists of the code points:

```
6004 5405 3002 2403 601 543 302 244 62 57 32 27 7

```

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

```
n=>"0123323453"[[,a,b,c,d]=1e4+n+'',d]-(-"0246424683"[c]-"0123323455"[b])+a*4

```

The strings represent the number of line segments for the units, tens and hundreds digits. (Thousands is simply four times the thousands digit.) This method seems to be shorter than other options such as the algorithm suggested in the question.

Edit: Saved 2 bytes thanks to @user81655.

# Answer
> 1 votes
## Java, 152 bytes

Because, ya know, Java.

```
n->{int c=0;int[]r={999,4,899,5,499,2,399,3,99,1,89,3,49,2,39,4,9,2,8,3,4,2,3,3,0,1};for(int i=0;i<26;i+=2)while(n>r[i]){n-=r[i]+1;c+=r[i+1];}return c;}

```

Simple literal implementation of the given algorithm. Array packs the transform information: even indexes are one less than the roman numeral and odd indexes are the count for that numeral.

This is a lambda that takes and returns an `int`/`Integer`. This includes `IntUnaryOperator` or `UnaryOperator<Integer>`.

---
Tags: code-golf, counting, roman-numerals
---