# Question
Title: Output a primitive element for each field size
A primitive element of a finite field is a generator of the multiplicative group of the field. In other words, `alpha` in `F(q)` is called a primitive element if it is a primitive `q−1`th root of unity in `F(q)`. This means that all the non-zero elements of `F(q)` can be written as `alpha^i` for some (positive) integer `i`.

All elements of the field `F_{2^k}` can be written as polynomials of degree at most `k-1` with coefficients that are either `1` or `0`. In order to make this complete, your code also needs to output an irreducible polynomial of degree `k` which defines the field you are using.

The task is write code that outputs a primitive element of `F_{2^k}` of your choosing for each `k = 1 .. 32` in order.

Your output must simply list the `k` coefficients of the primitive element in any format that you like and then on a separate line the `k+1` elements of the irreducible polynomial. Please separate the outputs for each value of `k` if possible.

Your code may take as long as you like but you must have run it to completion before submitting your answer.

You may not use any builtin or library function which returns primitive elements of a finite field or tests whether an element is primitive.

**An example**

For `k = 1` the only primitive element is `1`.

For `k = 2` we have `F_4`. The 4 elements are `{0, 1, x, x + 1}` so there are two primitive elements `x` and `x + 1`. So the code could output

```
1 1
1 1 1

```

as the coefficients for example where the second line is the irreducible polynomial which in this case is `x^2+x+1` which has coefficients `1 1 1`.

# Answer
> 2 votes
# Pari/GP, 114 bytes

Inspired by isaacg's answer in another question.

```
for(n=1,32,for(i=1,2^n,if(sumdiv(2^n-1,d,Mod(x,f=Mod(Pol(binary(2*2^n-i)),2))^d==1)==1,print([x,lift(f)]);break)))

```

Try it online!

---

If built-ins are allowed:

### Pari/GP, 61 bytes (non-competing)

```
for(i=1,32,print([ffprimroot(ffgen(f=ffinit(2,i))),lift(f)]))

```

Try it online!

# Answer
> 4 votes
# Mathematica, 127 bytes

```
Do[For[i=2*2^n,PolynomialMod[x^Divisors[2^n-1]+1,i~IntegerDigits~2~FromDigits~x,Modulus->2]~Count~0!=1,i--];Print@{2,i},{n,32}]

```

### Explanation:

If we choose a primitive polynomial as the irreducible polynomial, then \\$x\\$ is a primitive element. A irreducible polynomial of degree \\$n\\$ is primitive if and only if it has order \\$2^n - 1\\$, i.e., it is divisible by \\$x^{2^n - 1} - 1\\$, but not divisible by any \\$x^i - 1\\$, where \\$i\\$ runs through all the proper divisors of \\$2^n - 1\\$.

### Output:

Outputs integers whose bits are the coefficients of the polynomials. For example, \\$8589934581\\$ is \\$111111111111111111111111111110101\\$ when written in binary, so it represents the polynomial $$x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+\\x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+\\x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+\\x^8+x^7+x^6+x^5+x^4+x^2+1$$

```
{2,3}

{2,7}

{2,13}

{2,25}

{2,61}

{2,115}

{2,253}

{2,501}

{2,1019}

{2,2041}

{2,4073}

{2,8137}

{2,16381}

{2,32743}

{2,65533}

{2,131053}

{2,262127}

{2,524263}

{2,1048531}

{2,2097145}

{2,4194227}

{2,8388589}

{2,16777213}

{2,33554351}

{2,67108849}

{2,134217697}

{2,268435427}

{2,536870805}

{2,1073741801}

{2,2147483533}

{2,4294967287}

{2,8589934581}

```

---
Tags: code-golf, math, abstract-algebra, restricted-time
---


title: Tweetable hash function challenge

text:
# Question
Title: Tweetable hash function challenge
In this you will write a hash function in 140 bytes1 or less of source code. The hash function must take an ASCII string as input, and return a 24-bit unsigned integer (\[0, 224-1\]) as output.

Your hash function will be evaluated for every word in this large British English dictionary2. Your score is the amount of words that share a hash value with another word (a collision).

### The lowest score wins, ties broken by first poster.

## Test case

Before submitting, please test your scoring script on the following input:

```
duplicate
duplicate
duplicate
duplicate

```

If it gives any score other than 4, it is buggy.

---

Clarifying rules:

1. Your hash function must run on a single string, not a whole array. Also, your hash function may not do any other I/O than the input string and output integer.
2. Built-in hash functions or similar functionality (e.g. encryption to scramble bytes) is disallowed.
3. Your hash function must be deterministic.
4. Contrary to most other contests optimizing specifically for the scoring input is allowed.

1 I am aware Twitter limits characters instead of bytes, but for simplicity we will use bytes as a limit for this challenge.
2 Modified from Debian's wbritish-huge, removing any non-ASCII words.

# Answer
Alright fine I’ll go learn a golfing language.

# CJam, 140 bytes, 3314 colliding words

```
00000000: 7b5f 3162 225e d466 4a55 a05e 9f47 fc51  {_1b"^.fJU.^.G.Q
00000010: c45b 4965 3073 72dd e1b4 d887 a4ac bcbd  .[Ie0sr.........
00000020: 9c8f 70ca 2981 b2df 745a 10d0 dfca 6cff  ..p.)...tZ....l.
00000030: 7a3b 64df e730 54b4 b068 8584 5f6c 9f6b  z;d..0T..h.._l.k
00000040: b7f8 7a1f a2d3 b2b8 bcf5 cfa6 1ef7 a55c  ..z............\
00000050: dca8 795c 2492 dc32 1fb6 f449 f9ca f6b7  ..y\$..2...I....
00000060: a2cf 4772 266e ad4f d90c d236 b51d c5d5  ..Gr&n.O...6....
00000070: 5c46 3f9b 7cb4 f195 4efc fe4a ce8d 9aee  \F?.|...N..J....
00000080: 9dbc 223d 6962 3443 2329 257d            .."=ib4C#)%}

```

Defines a block (anonymous function). To test, you could add `qN%%N*N` to take the newline-separated list of words on stdin and write a newline-separated list of hashes on stdout. Equivalent Python code:

```
b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,ord('^\xd4fJU\xa0^\x9fG\xfcQ\xc4[Ie0sr\xdd\xe1\xb4\xd8\x87\xa4\xac\xbc\xbd\x9c\x8fp\xca)\x81\xb2\xdftZ\x10\xd0\xdf\xcal\xffz;d\xdf\xe70T\xb4\xb0h\x85\x84_l\x9fk\xb7\xf8z\x1f\xa2\xd3\xb2\xb8\xbc\xf5\xcf\xa6\x1e\xf7\xa5\\\xdc\xa8y\\$\x92\xdc2\x1f\xb6\xf4I\xf9\xca\xf6\xb7\xa2\xcfGr&n\xadO\xd9\x0c\xd26\xb5\x1d\xc5\xd5\\F?\x9b|\xb4\xf1\x95N\xfc\xfeJ\xce\x8d\x9a\xee\x9d\xbc'[b(s,1)%125]))%(8**8+1)

```

# Pyth, 140 bytes, ~~3535~~ 3396 colliding words

```
00000000: 4c25 4362 2d68 5e38 2038 2a36 3643 4022  L%Cb-h^8 8*66C@"
00000010: aa07 f29a 27a7 133a 3901 484d 3f9b 1982  ....'..:9.HM?...
00000020: d261 79ab adab 9d92 888c 3012 a280 76cf  .ay.......0...v.
00000030: a2e5 8f81 7039 acee c42e bc18 28d8 efbf  ....p9......(...
00000040: 0ebe 2910 9c90 158e 3742 71b4 bdf5 59c2  ..).....7Bq...Y.
00000050: f90b e291 8673 ea59 6975 10be e750 84c8  .....s.Yiu...P..
00000060: 0b0f e7e8 f591 f628 cefa 1ab3 2e3c 72a3  .......(.....<r.
00000070: 7f09 6190 dbd2 d54e d6d0 d391 a780 ebb6  ..a....N........
00000080: ae86 2d1e 49b0 552e 7522 4362            ..-.I.U.u"Cb

```

Defines a function named `y`. To test, you could add `jmyd.z` to take the newline-separated list of words on stdin and write a newline-separated list of hashes on stdout. Equivalent Python code:

```
b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,256)%(8**8+1-66*ord("\xaa\x07\xf2\x9a'\xa7\x13:9\x01HM?\x9b\x19\x82\xd2ay\xab\xad\xab\x9d\x92\x88\x8c0\x12\xa2\x80v\xcf\xa2\xe5\x8f\x81p9\xac\xee\xc4.\xbc\x18(\xd8\xef\xbf\x0e\xbe)\x10\x9c\x90\x15\x8e7Bq\xb4\xbd\xf5Y\xc2\xf9\x0b\xe2\x91\x86s\xeaYiu\x10\xbe\xe7P\x84\xc8\x0b\x0f\xe7\xe8\xf5\x91\xf6(\xce\xfa\x1a\xb3.<r\xa3\x7f\ta\x90\xdb\xd2\xd5N\xd6\xd0\xd3\x91\xa7\x80\xeb\xb6\xae\x86-\x1eI\xb0U.u"[b(s,256)%121]))

```

# Theoretical limits

How well can we expect to do? Here is a plot of x, the number of colliding words, vs. y, the entropy in bytes required to get at most x colliding words. For example, the point (2835, 140) tells us that a random function gets at most 2835 colliding words with probability 1/256\**140, so it’s exceedingly unlikely that we’ll ever be able to do much better than that with 140 bytes of code.
> 12 votes

# Answer
# Python, 5333 4991

I believe this is the first contender to score significantly better than a random oracle.

```
def H(s):n=int(s.encode('hex'),16);return n%(8**8-ord('+%:5O![/5;QwrXsIf]\'k#!__u5O}nQ~{;/~{CutM;ItulA{uOk_7"ud-o?y<Cn~-`bl_Yb'[n%70]))

```
> 22 votes

# Answer
# Python 2, 140 bytes, 4266 colliding words

I didn’t really want to start with the non-printable bytes thing given their unclear tweetability, but well, I didn’t start it. :-P

```
00000000: efbb bf64 6566 2066 2873 293a 6e3d 696e  ...def f(s):n=in
00000010: 7428 732e 656e 636f 6465 2827 6865 7827  t(s.encode('hex'
00000020: 292c 3336 293b 7265 7475 726e 206e 2528  ),36);return n%(
00000030: 382a 2a38 2b31 2d32 3130 2a6f 7264 2827  8**8+1-210*ord('
00000040: 6f8e 474c 9f5a b49a 01ad c47f cf84 7b53  o.GL.Z........{S
00000050: 49ea c71b 29cb 929a a53b fc62 3afb e38e  I...)....;.b:...
00000060: e533 7360 982a 50a0 2a82 1f7d 768c 7877  .3s`.*P.*..}v.xw
00000070: d78a cb4f c5ef 9bdb 57b4 7745 3a07 8cb0  ...O....W.wE:...
00000080: 868f a927 5b6e 2536 375d 2929            ...'[n%67]))

```

# Python 2, 140 printable bytes, ~~4662~~ ~~4471~~ 4362 colliding words

```
def f(s):n=int(s.encode('hex'),16);return n%(8**8+3-60*ord('4BZp%(jTvy"WTf.[Lbjk6,-[LVbSvF[Vtw2e,NsR?:VxC0h5%m}F5,%d7Kt5@SxSYX-=$N>'[n%71]))

```

Inspired by the form of kasperd’s solution, obviously—but with the important addition of an affine transformation on the modulus space, and entirely different parameters.
> 20 votes

# Answer
# CJam, ~~4125~~ ~~3937~~ ~~3791~~ 3677

```
0000000: 7b 5f 39 62 31 31 30 25 5f 22 7d 13 25 77  {_9b110%_"}.%w
000000e: 77 5c 22 0c e1 f5 7b 83 45 85 c0 ed 08 10  w\"...{.E.....
000001c: d3 46 0c 5c 22 59 f8 da 7b f8 18 14 8e 4b  .F.\"Y..{....K
000002a: 3a c1 9e 97 f8 f2 5c 18 21 63 13 c8 d3 86  :.....\.!c....
0000038: 45 8e 64 33 61 50 96 c4 48 ea 54 3b b3 ab  E.d3aP..H.T;..
0000046: bc 90 bc 24 21 20 50 30 85 5f 7d 7d 59 2c  ...$! P0._}}Y,
0000054: 4a 67 88 c8 94 29 1a 1a 1a 0f 38 c5 8a 49  Jg...)....8..I
0000062: 9b 54 90 b3 bd 23 c6 ed 26 ad b6 79 89 6f  .T...#..&..y.o
0000070: bd 2f 44 6c f5 3f ae af 62 9b 22 3d 69 40  ./Dl.?..b."=i@
000007e: 62 31 35 32 35 31 39 25 31 31 30 2a 2b 7d  b152519%110*+}

```

This approach divides domain *and codomain* into 110 disjoint sets, and defines a slightly different hash function for each pair.

### Scoring / Verification

```
$ echo $LANG
en_US
$ cat gen.cjam
"qN%{_9b110%_"
[125 19 37 119 119 34 12 225 245 123 131 69 133 192 237 8 16 211 70 12 34 89 248 218 123 248 24 20 142 75 58 193 158 151 248 242 92 24 33 99 19 200 211 134 69 142 100 51 97 80 150 196 72 234 84 59 179 171 188 144 188 36 33 32 80 48 133 95 125 125 89 44 74 103 136 200 148 41 26 26 26 15 56 197 138 73 155 84 144 179 189 35 198 237 38 173 182 121 137 111 189 47 68 108 245 63 174 175 98 155]
:c`"=i@b152519%110*+}%N*N"
$ cjam gen.cjam > test.cjam
$ cjam test.cjam < british-english-huge.txt | sort -n > temp
$ head -1 temp
8
$ tail -1 temp
16776899
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(uniq -u < temp | wc -l)
$ echo $[all - unique]
3677

```

The following port to Python can be used with the official scoring snippet:

```
h=lambda s,b:len(s)and ord(s[-1])+b*h(s[:-1],b)

def H(s):
 p=h(s,9)%110
 return h(s,ord(
  '}\x13%ww"\x0c\xe1\xf5{\x83E\x85\xc0\xed\x08\x10\xd3F\x0c"Y\xf8\xda{\xf8\x18\x14\x8eK:\xc1\x9e\x97\xf8\xf2\\\x18!c\x13\xc8\xd3\x86E\x8ed3aP\x96\xc4H\xeaT;\xb3\xab\xbc\x90\xbc$! P0\x85_}}Y,Jg\x88\xc8\x94)\x1a\x1a\x1a\x0f8\xc5\x8aI\x9bT\x90\xb3\xbd#\xc6\xed&\xad\xb6y\x89o\xbd/Dl\xf5?\xae\xafb\x9b'
  [p]))%152519*110+p

```
> 16 votes

# Answer
## Python, 6446 6372

---

This solution achieves lower collision count than all previous entries, and it needs only 44 of the 140 bytes allowed for code:

```
H=lambda s:int(s.encode('hex'),16)%16727401

```
> 11 votes

# Answer
# JavaScript (ES6), 6389

The hash function (105 bytes):

```
s=>[...s.replace(/[A-Z]/g,a=>(b=a.toLowerCase())+b+b)].reduce((a,b)=>(a<<3)*28-a^b.charCodeAt(),0)<<8>>>8

```

The scoring function (NodeJS) (170 bytes):

```
h={},c=0,l=require('fs').readFileSync(process.argv[2],'utf8').split('\n').map(a=>h[b=F(a)]=-~h[b])
for(w of Object.getOwnPropertyNames(h)){c+=h[w]>1&&h[w]}
console.log(c)

```

Call as `node hash.js dictionary.txt`, where `hash.js` is the script, `dictionary.txt` is the dictionary text file (without the final newline), and `F` is defined as the hashing function.

*Thanks Neil for shaving 9 bytes off the hashing function!*
> 7 votes

# Answer
# CJam, 6273

```
{49f^245b16777213%}

```

XOR each character with **49**, reduce the resulting string via **x, y ↦ 245x + y**, and take the residue modulo **16,777,213** (the largest 24-bit prime).

### Scoring

```
$ cat hash.cjam
qN% {49f^245b16777213%} %N*N
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(cjam hash.cjam < british-english-huge.txt | sort | uniq -u | wc -l)
$ echo $[all - unique]
6273

```
> 7 votes

# Answer
# Python, 340053

A terrible score from a terrible algorithm, this answer exists more to give a small Python script that displays scoring.

```
H=lambda s:sum(map(ord, s))%(2**24)

```

To score:

```
hashes = []
with open("british-english-huge.txt") as f:
    for line in f:
        word = line.rstrip("\n")
        hashes.append(H(word))

from collections import Counter
print(sum(v for k, v in Counter(hashes).items() if v > 1))

```
> 5 votes

# Answer
## Mathematica, 6473

The next step up... instead of summing the character codes we treat them as the digits of a base-151 number, before taking them modulo 224.

```
hash[word_] := Mod[FromDigits[ToCharacterCode @ word, 151], 2^24]

```

Here is a short script to determine the number of collisions:

```
Total[Last /@ DeleteCases[Tally[hash /@ words], {_, 1}]]

```

I've just tried all bases systematically from `1` onwards, and so far base 151 yielded the fewest collisions. I'll try a few more to bring down the score a bit further, but the testing is a bit slow.
> 5 votes

# Answer
# Javascript (ES5), 6765

This is CRC24 shaved down to 140 Bytes. Could golf more but wanted to get my answer in :)

```
function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

```

Validator in node.js:

```
var col = new Array(16777215);
var n = 0;

var crc24_140 =
function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

require('fs').readFileSync('./dict.txt','utf8').split('\n').map(function(s){
    var h = crc24_140(s);
    if (col[h]===1) {
        col[h]=2;
        n+=2;
    } else if (col[h]===2) {
        n++;
    } else {
        col[h]=1;
    }
});

console.log(n);

```
> 5 votes

# Answer
# Python, ~~6390~~ ~~6376~~ 6359

```
H=lambda s:reduce(lambda a,x:a*178+ord(x),s,0)%(2**24-48)

```

May be considered a trivial modification to Martin Büttner's answer.
> 4 votes

# Answer
## Python, 9310

---

Yeah, not the best, but at least it is something. As we say in crypto, never write your own hash function.

This is exactly 140 bytes long, as well.

```
F=lambda x,o=ord,m=map:int((int(''.join(m(lambda z:str(o(z)^o(x[-x.find(z)])^o(x[o(z)%len(x)])),x)))^(sum(m(int,m(o,x))))^o(x[-1]))%(2**24))

```
> 3 votes

# Answer
## Matlab, 30828 8620 6848

It builds the hash by assigning a prime number to each ascii character/position combo and calculating their product for each word modulo the largest prime smaller than 2^24. Note that for testing I moved the call to primes outside into the tester directly before the while loop and passed it into the hash function, because it sped it up by about a factor of 1000, but this version works, and is self-contained. It may crash with words longer than about 40 characters.

```
function h = H(s)
p = primes(1e6);
h = 1;
for i=1:length(s)
    h = mod(h*p(double(s(i))*i),16777213);
end
end

```

Tester:

```
clc
clear variables
close all

file = fopen('british-english-huge.txt');
hashes = containers.Map('KeyType','uint64','ValueType','uint64');

words = 0;
p = primes(1e6);
while ~feof(file)
    words = words + 1;
    word = fgetl(file);
    hash = H(word,p);
    if hashes.isKey(hash)
        hashes(hash) = hashes(hash) + 1;
    else
        hashes(hash) = 1;
    end
end

collisions = 0;
for key=keys(hashes)

    if hashes(key{1})>1
        collisions = collisions + hashes(key{1});
    end
end

```
> 2 votes

# Answer
# Java 8, 7054 6467

This is inspired by (but not copied from) the builtin java.lang.String.hashCode function, so feel free to disallow according to rule #2.

```
w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

```

To score:

```
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

public class TweetableHash {
    public static void main(String[] args) throws Exception {
        List<String> words = Files.readAllLines(Paths.get("british-english-huge.txt"));

        Function<String, Integer> hashFunc = w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

        Map<Integer, Integer> hashes = new HashMap<>();
        for (String word : words) {
            int hash = hashFunc.apply(word);
            if (hash < 0 || hash >= 16777216) {
                throw new Exception("hash too long for word: " + word + " hash: " + hash);
            }

            Integer numOccurences = hashes.get(hash);
            if (numOccurences == null) {
                numOccurences = 0;
            }
            numOccurences++;

            hashes.put(hash, numOccurences);
        }

        int numCollisions = hashes.values().stream().filter(i -> i > 1).reduce(Integer::sum).get();
        System.out.println("num collisions: " + numCollisions);
    }
}

```
> 1 votes

# Answer
# C#, 6251 6335

```
int H(String s){int h = 733;foreach (char c in s){h = (h * 533 + c);}return h & 0xFFFFFF;}

```

The constants 533 and 733 889 and 155 give the best score out of all of the ones I've searched so far.
> 1 votes

# Answer
## Ruby, 9309 collisions, 107 bytes

```
def hash(s);require'prime';p=Prime.first(70);(0...s.size).reduce(0){|a,i|a+=p[i]**(s[i].ord)}%(2**24-1);end

```

Not a good contender, but I wanted to explore a different idea from other entries.

Assign the first n primes to the first n positions of the string, then sum all prime\[i\] \** (ascii code of string\[i\]), then mod 2\**24-1.
> 1 votes

# Answer
# Python, ~~6995~~ ~~6862~~ 6732

Just a simple RSA function. Pretty lame, but beats some answers.

```
M=0x5437b3a3b1
P=0x65204c34d
def H(s):
    n=0
    for i in range(len(s)):
        n+=pow(ord(s[i]),P,M)<<i
    return n%(8**8)

```
> 1 votes

# Answer
# C++: 7112 6694 6483 6479 6412 6339 collisions, 90 bytes

I implemented a naïve genetic algorithm for my coefficient array. I'll update this code as it finds better ones. :)

```
int h(const char*s){uint32_t t=0,p=0;while(*s)t="cJ~Z]q"[p++%6]*t+*s++;return t%16777213;}

```

Test function:

```
int main(void)
{
    std::map<int, int> shared;

    std::string s;
    while (std::cin >> s) {
        shared[h(s.c_str())]++;
    }

    int count = 0;
    for (auto c : shared) {
        if ((c.first & 0xFFFFFF) != c.first) { std::cerr << "invalid hash: " << c.first << std::endl; }
        if (c.second > 1) { count += c.second; }
    }

    std::cout << count << std::endl;
    return 0;
}

```
> 1 votes

# Answer
# tcl

## 88 bytes, 6448 / 3233 collisions

I see people have been counting either the number of colliding words, or else the number of words placed in nonempty buckets. I give both counts - the first is according to the problem specification, and the second is what more posters have been reporting.

```
# 88 bytes, 6448 collisions, 3233 words in nonempty buckets

puts "[string length {proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}}] bytes"

proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}

# change 2551 above to:
#   7: 85 bytes, 25839 colliding words, 13876 words in nonempty buckets
#   97: 86 bytes, 6541 colliding words, 3283 words in nonempty buckets
#   829: 87 bytes, 6471 colliding words, 3251 words in nonempty buckets

# validation program

set f [open ~/Downloads/british-english-huge.txt r]
set words [split [read $f] \n]
close $f

set have {};                        # dictionary whose keys are hash codes seen
foreach w $words {
    if {$w eq {}} continue
    set h [H $w]
    dict incr have $h
}
set coll 0
dict for {- count} $have {
    if {$count > 1} {
        incr coll $count
    }
}
puts "found $coll collisions"

```
> 1 votes

# Answer
## JavaScript, 121 bytes, ~~3268~~ ~~3250~~ ~~3244~~ 6354(3185) collisions

```
s=>{v=i=0;[...s].map(z=>{v=((((v*13)+(s.length-i)*7809064+i*380886)/2)^(z.charCodeAt(0)*266324))&16777215;i++});return v}

```

Parameters (13, 7809064, 380886, 2, 266324) are by trial and error.

Still optimizable I think, and there is still room for adding extra parameters, working for further optimization...

## Verification

```
hashlist = [];
conflictlist = [];
for (x = 0; x < britain.length; x++) {
    hash = h(britain[x]);                      //britain is the 340725-entry array
    hashlist.push(hash);
}

conflict = 0; now_result = -1;
(sortedlist = sort(hashlist)).map(v => {
    if (v == now_result) {
        conflict++;
        conflictlist.push(v);
    }
    else
        now_result = v;
});

console.log(conflictlist);

var k = 0;
while (k < conflictlist.length) {
    if (k < conflictlist.length - 1 && conflictlist[k] == conflictlist[k+1])
        conflictlist.splice(k,1);
    else
        k++;
}

console.log(conflict + " " + (conflict+conflictlist.length));

```

---

3268 \> 3250 - Changed the 3rd parameter from 380713 to 380560.

3250 \> 3244 - Changed the 3rd parameter from 380560 to 380886.

3244 \> 6354 - Changed the 2nd parameter from 7809143 to 7809064, and found I've used the wrong calculation method ;P
> 1 votes

# Answer
## Python 3, 89 bytes, 6534 hash collisions

```
def H(x):
 v=846811
 for y in x:
  v=(972023*v+330032^ord(y))%2**24
 return v%2**24

```

All the large magic numbers you see here are fudge constants.
> 1 votes

# Answer
Here are a few similar constructs, which are quite "seedable" and makes incremental parameter optimization possible. Damn it is difficult to get lower than 6k! Assuming the score has the mean of 6829 and std of 118 I also calculated the likelihood of getting such low scores by random.

**Clojure A, 6019, Pr = 1:299.5e9**

```
 #(reduce(fn[r i](mod(+(* r 811)i)16777213))(map *(cycle(map int"~:XrBaXYOt3'tH-x^W?-5r:c+l*#*-dtR7WYxr(CZ,R6J7=~vk"))(map int %)))

```

**Clojure B, 6021, Pr = 1:266.0e9**

```
#(reduce(fn[r i](mod(+(* r 263)i)16777213))(map *(cycle(map int"i@%(J|IXt3&R5K'XOoa+Qk})w<!w[|3MJyZ!=HGzowQlN"))(map int %)(rest(range))))

```

**Clojure C, 6148, Pr = 1:254.0e6**

```
#(reduce(fn[r i](mod(+(* r 23)i)16777213))(map *(cycle(map int"ZtabAR%H|-KrykQn{]u9f:F}v#OI^so3$x54z2&gwX<S~"))(for[c %](bit-xor(int c)3))))

```

**Clojure, 6431, Pr = 1:2.69e3 (something different)**

```
#(mod(reduce bit-xor(map(fn[i[a b c]](bit-shift-left(* a b)(mod(+ i b c)19)))(range)(partition 3 1(map int(str"w"%"m")))))16776869)

```

This was my original ad-hoc hash function, it has four tunable parameters.
> 1 votes

# Answer
# tcl

~~#91 bytes, 6508 collisions~~

# 91 bytes, 6502 collisions

```
proc H s {lmap c [split $s ""] {incr h [expr [scan $c %c]*875**[incr i]]};expr $h&0xFFFFFF}

```

Computer is still performing a search to evaluate if there is a value that causes less collisions than the ~~147~~ 875 base, which is still the recordist.
> 0 votes

# Answer
## Ruby, 6473 collisions, 129 bytes

```
h=->(w){@p=@p||(2..999).select{|i|(2..i**0.5).select{|j|i%j==0}==[]};c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+179)%((1<<24)-3)}}

```

The @p variable is filled with all the primes below 999.

This converts ascii values into primes numbers and takes their product modulo a large prime. The fudge factor of 179 deals with the fact that the original algorithm was for use in finding anagrams, where all words that are rearrangements of the same letters get the same hash. By adding the factor in the loop, it makes anagrams have distinct codes.

I could remove the \**0.5 (sqrt test for prime) at the expense of poorer performance to shorten the code. I could even make the prime number finder execute in the loop to remove nine more characters, leaving 115 bytes.

To test, the following tries to find the best value for the fudge factor in the range 1 to 300. It assume that the word file in in the /tmp directory:

```
h=->(w,y){
  @p=@p||(2..999).
    select{|i|(2..i**0.5).
    select{|j|i%j==0}==[]};
  c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+y)%((1<<24)-3)}
}

american_dictionary = "/usr/share/dict/words"
british_dictionary = "/tmp/british-english-huge.txt"
words = (IO.readlines british_dictionary).map{|word| word.chomp}.uniq
wordcount = words.size

fewest_collisions = 9999
(1..300).each do |y|
  whash = Hash.new(0)
  words.each do |w|
    code=h.call(w,y)
    whash[code] += 1
  end
  hashcount = whash.size
  collisions = whash.values.select{|count| count > 1}.inject(:+)
  if (collisions < fewest_collisions)
    puts "y = #{y}. #{collisions} Collisions. #{wordcount} Unique words. #{hashcount} Unique hash values"
    fewest_collisions = collisions
  end
end

```
> -1 votes

---
Tags: code-challenge, restricted-source, hashing
---


title: Line editor (more text here)

text:
# Question
Title: Line editor (more text here)
In the misty years of yore, when fanfold terminals walked the earth, there lived a strange creature. Oddly crippled and yet oddly powerful, the line editor teemed across the programming landscape in untold numbers; covering the earth as far as the eye could see.

Now it is fallen on hard times. That vast population hunted, hounded, and driven to the brink of extinction. Only a few specimens remain, most in cramped and unembelished cages in the less enlightened kind of zoo, though a few stuffed and mounted examples can be seen in backwater museums. Oh, and there is `ed`.

**Frankenstein-like, we shall resurrect the noble beast!**

## Commands

Our editor is fairly minimal and will support the following commands

**Focus moving commands**

* `<number>[,<number>]` -- move the focus to the stated line and if the second argument is given to the state column. Excessive line number gets the last line. Excessive column number gets the end of the line.
* `,<number>` -- move to column number on the current line
* `e` -- move the focus to the end of the file but do not begin a new line.
* `b` -- move the focus to the beginning of the file.

**Informational commands**

* `L` -- Echo the current context. The five lines centered on the current line are printed. All five lines are indented by one character; the current line is marked with a "\>", the others with a " ". Under these lines another line is printed consisting entirely of spaces except for a "^" in the current column (a total of six lines are printed).
* `l` -- echo the current line
* `p [[<start>],[<end>]]` -- Print the file from starting to ending address. These value default to 1 and 0 (the end of the file).

**File altering commands**

* `A [<text>]` -- Move to the line beyond the end of the file (that is begin a new line) and (possibly) append text.
* `<return>` (alone) -- Insert a newline. Thus `a <return> <return>` inserts a newline after the current one.
* `r <text>` -- replaces everything from the focus to the end of the line with text.
* `i [<text>]` -- inserts text followed by by newline at the current focus. Any portion of this line beyond the focus ends up on the next line.
* `I <text>` -- inserts text at the current focus, preserving the rest of the line. Focus remains on this line.
* `d` -- Delete the contents of the current line or if the current line is already empty, remove the line.
* `j` -- join this line to the next

Of this last group the first four end with the focus moving to the next line, while `I` preserves the focus at the end of the added text. When deleting or joining focus remains at the same line and column *number*.

**The Interpretation of line numbers in commands**

Number beginning with '+' or '-' are interpreted as *offsets* from the current line number. Numbers without a sign are interpreted as absolute line numbers, except that '0' means the last line of the file.

## Prompt and interaction

The editor functions as a shell, and the prompt has the form `<line>','<column>'>'` where line is the line number except that "end" is used when the focus is at the last character of the file.

Each command is accepted only when the user presses newline. And takes affect.

Readline support is allowed but not required.

No feedback is provided except the changing values of and in the prompt, unless explicitly stated in the commands description.

# Scoring

This is , so the shortest answer in each language wins.

### Special thanks to dmkee for making this in sandbox where I adopted it.

# Answer
## C (gcc), 1288 1212 1188 1171 1146 bytes

```
#define P printf(
#define A case
#define B break
#define L(i,e,t,f,s)for(o=i;o e;){strcpy(l[o t],l[o f]);c[o t]=c[s o];}
#define R(m,o){return b<1|b>m?m o:b;}
#define N(f)sscanf(f,"%d,%d",&i,&j)||sscanf(f,",%d",&j)
r,i,j,o,z,c[999],*C,x=1,y=1;char a[999],l[999][999],(*L)[999];D(){L(r,>y,,-1,--)r++?strcpy(l[o],l[o-1]+--x),c[o-1]=x,l[o-1][x]=0:0;c[y++]=strlen(l[o]);x=1;}U(){strcat(*L,l[y]);*C=strlen(*L);L(y+1,<r,-1,,++)--r;*l[r]=c[r]=0;}X(b)R(c[y-1],+1)Y(b)R(r,)main(){for(;;){z=i=y;L=l+--z;C=c+z;j=x;!r||y/r&&x>*C?P"end> "):P"%d,%d> ",y,x);scanf("%[^\n]%*c",a)?a[2]*=!!a[1],N(a)?y=Y(i+(i<0|*a=='+')*y),x=X(j+(j<0||strchr(a+1,'+'))*x):0:(*a=D(),scanf("%*c"));switch(*a){A'e':y=r;x=c[r-1]+1;B;A'b':y=1;x=1;B;A'L':for(o=y-4;++o<y+2;)o<0^o<r&&P"%c%s\n",o^z?' ':'>',l[o]);for(o=x+1;--o;)P" ");P"^\n");B;A'l':puts(*L);B;A'p':i=1;j=0;N(a+2);for(o=Y(i)-1;o<Y(j);++o)puts(l[o]);B;A'A':y=r++;strcpy(l[y],a+2);x=c[y]=strlen(a+2);++x;++y;B;A'i':D();--y;x=X(0);A'r':strcpy(*L+x-1,a+2);*C=strlen(*L);x=1;++y>r&&++r;B;A'I':o=strlen(a+2);memmove(*L+x+o-1,*L+x-1,*C-x+1);*C+=o;memcpy(*L+x-1,a+2,o);x+=o;B;A'd':**L?**L=*C=0,x=1:U();y=y>r?r:y;B;A'j':y<r&&U();}}}

```

## Demo

First time trying to do something like this, so there are probably some missed opportunities for making it smaller. (Thanks Jerry Jeremiah for pointing out some)

Here's a (slightly) more readable version:

```
// often used functions/keywords:
#define P printf(
#define A case
#define B break

// loops for copying rows upwards/downwards are similar -> macro
#define L(i,e,t,f,s)for(o=i;o e;){strcpy(l[o t],l[o f]);c[o t]=c[s o];}

// range check for rows/columns is similar -> macro
#define R(m,o){return b<1|b>m?m o:b;}

// checking for numerical input is needed twice (move and print command):
#define N(f)sscanf(f,"%d,%d",&i,&j)||sscanf(f,",%d",&j)

// room for 999 rows with each 999 cols (not specified, should be enough)
// also declare "current line pointers" (*L for data, *C for line length),
// an input buffer (a) and scratch variables
r,i,j,o,z,c[999],*C,x=1,y=1;char a[999],l[999][999],(*L)[999];

// move rows down from current cursor position
D()
{
    L(r,>y,,-1,--)
    r++?strcpy(l[o],l[o-1]+--x),c[o-1]=x,l[o-1][x]=0:0;
    c[y++]=strlen(l[o]);
    x=1;
}

// move rows up, appending uppermost to current line
U()
{
    strcat(*L,l[y]);
    *C=strlen(*L);
    L(y+1,<r,-1,,++)
    --r;
    *l[r]=c[r]=0;
}

// normalize positions, treat 0 as max
X(b)R(c[y-1],+1)
Y(b)R(r,)

main()
{
    for(;;)
    {
        // initialize z as current line index, the current line pointers,
        // i and j for default values of positioning
        z=i=y;L=l+--z;C=c+z;j=x;

        // prompt:
        !r||y/r&&x>*C?P"end> "):P"%d,%d> ",y,x);

        // read a line of input (using scanf so we don't need an include)
        scanf("%[^\n]%*c",a)?

        // no command arguments -> make check easier:
        a[2]*=!!a[1],

        // numerical input -> have move command:
        // calculate new coordinates, checking for "relative"
        N(a)?y=Y(i+(i<0|*a=='+')*y),x=X(j+(j<0||strchr(a+1,'+'))*x):0:

        // check for empty input, read single newline and perform <return> command:
        (*a=D(),scanf("%*c"));

        switch(*a)
        {
            A'e':y=r;x=c[r-1]+1;B;
            A'b':y=1;x=1;B;
            A'L':for(o=y-4;++o<y+2;)o<0^o<r&&P"%c%s\n",o^z?' ':'>',l[o]);for(o=x+1;--o;)P" ");P"^\n");B;
            A'l':puts(*L);B;
            A'p':i=1;j=0;N(a+2);for(o=Y(i)-1;o<Y(j);++o)puts(l[o]);B;
            A'A':y=r++;strcpy(l[y],a+2);x=c[y]=strlen(a+2);++x;++y;B;
            A'i':D();--y;x=X(0);
            // Commands i and r are very similar -> fall through from i to r
            // after moving rows down and setting position at end of line:
            A'r':strcpy(*L+x-1,a+2);*C=strlen(*L);x=1;++y>r&&++r;B;
            A'I':o=strlen(a+2);memmove(*L+x+o-1,*L+x-1,*C-x+1);*C+=o;memcpy(*L+x-1,a+2,o);x+=o;B;
            A'd':**L?**L=*C=0,x=1:U();y=y>r?r:y;B;
            A'j':y<r&&U();
        }
    }
}

```

---

This challenge leaves quite a lot of corner cases to explore -- I *guess* I fixed all bugs by now, but if somebody finds one more, please comment. Regarding the revisions, I removed byte counts for earlier versions that contained subtle bugs.
> 7 votes

# Answer
# AWK, ~~747 807 829~~ 807 bytes

```
func d(D){if(D>0){for(;D<NR;)f[D++]=f[D+1];NR--}else{for(c=NR;x>-D;x--)f[x+1]=f[x];NR++}}
{f[r=NR]=$0}
END{while(1){printf"%s,%d>",r==NR?"end":r,c
getline v<"-"
split("  >  ",l,"")
if(v=="e")r=NR
if(v=="b")r=1
if(v=="L"){for(i=-2;i<3;i++)print l[i+3] f[r+i];printf"%"c+1"s\n","^"}if(v=="l")print f[r]
if(v=="d")z=f[r]=""?d(r):f[r]=""
if(v=="j"){f[r]=f[r] f[r+1];d(r+1)}
S=index(v," ")
z=S?substr(v,S+1):v
a=substr(v,1,1)
n=split(z,N,",")
x=N[1]~/[-+].*/?r+N[1]:N[1]
y=N[2]~/[-+].*/?c+N[2]:N[2]
if(!S&&v~/[0-9+-,]+.*/){r=x?x>NR?NR:x:x=="0"?NR:r
C=length(f[r])
c=n>1?y>C?C:y:c}
if(a=="p")for(i=x?x:1;i<=(y?y:NR);)print f[i++]
if(a=="r"||a=="i"||a=="I"){k=substr(f[r],c)
if(a=="i"){if(c<length(f[r])){d(-r-1);f[r+1]=k}f[r]=substr(f[r],1,c) z (a=="I"?k:"")}if(a="a"||a=="A"){if(a=="A")r=NR;r=r+1;d(r);f[r]=z}}}}

```

Try it online!

Removing the `else`s makes the lines a bit shorter/readable but the cursor assignment is a bit more complicated.

Just for giggles, I created a version to add a bit more "functionality":

`q` quits the program

`w <outfile[defaults to input file]>` writes the changes.

Try it online!
> 5 votes

# Answer
## 6502 Assembly (C64, BASIC loader), 5761 5352 bytes

```
0fOa=49152to50573:rEb:pOa,b:nE:sY49152
1dA162,54,134,1,162,1,134,7,134,8,202,142,0,96,134,251,162,96,134,21,162,128
2dA142,145,2,162,23,142,24,208,166,8,169,0,160,253,32,98,194,32,126,195,32,173
3dA195,166,2,240,103,202,202,16,2,162,0,142,160,191,173,162,191,201,69,240,93
4dA201,66,240,95,201,204,240,97,201,76,240,96,201,80,240,100,201,193,240,99,201
5dA73,240,123,201,82,240,122,201,201,240,121,201,68,240,123,201,74,240,122,162
6dA0,32,108,196,165,34,166,251,32,81,194,201,255,240,10,133,8,170,169,0,160,253
7dA32,98,194,160,0,177,253,170,232,165,35,201,255,208,2,165,7,32,81,194,133,7
8dA16,134,32,156,194,76,30,192,169,0,133,35,240,204,169,1,133,35,208,198,76,76
9dA193,166,8,32,198,193,76,30,192,76,233,192,166,251,232,134,251,134,8,169,0
10dA160,253,32,98,194,169,0,168,145,253,200,132,7,32,244,193,76,30,192,76,153
11dA193,76,178,193,32,244,193,76,30,192,76,45,193,32,8,195,76,30,192,166,251
12dA240,249,162,1,134,34,202,134,35,162,2,173,160,191,240,3,32,49,196,165,34
13dA166,251,32,81,194,201,255,208,2,169,1,133,34,166,251,165,35,201,255,208,2
14dA169,0,32,81,194,141,37,193,166,34,32,198,193,166,34,224,255,240,190,232,134
15dA34,208,242,160,0,177,253,208,17,165,8,197,251,208,5,198,8,200,132,7,32,8
16dA195,76,30,192,152,145,253,200,132,7,208,245,166,251,240,70,166,8,160,3,202
17dA240,6,200,202,240,2,200,202,232,140,120,193,142,122,193,228,8,240,7,169,32
18dA32,210,255,208,5,169,62,32,210,255,32,198,193,160,255,162,255,136,240,4,228
19dA251,208,219,169,32,166,7,32,210,255,202,208,250,169,94,32,210,255,169,13,32
20dA210,255,76,30,192,32,156,194,198,8,160,0,177,253,133,7,230,7,32,244,193,230
21dA8,162,1,134,7,76,30,192,160,0,166,7,202,138,145,253,32,244,193,230,8,162,1
22dA134,7,76,30,192,169,193,160,219,32,98,194,174,219,193,232,142,229,193,174
23dA220,193,142,230,193,174,255,255,240,16,142,236,193,160,0,185,255,255,32,210
24dA255,200,192,255,208,245,169,13,76,210,255,165,253,24,101,7,141,38,194,141
25dA57,194,165,254,105,0,141,39,194,141,58,194,173,38,194,109,160,191,141,41
26dA194,173,39,194,105,0,141,42,194,160,0,177,253,56,229,7,48,11,170,24,189,255
27dA255,157,255,255,202,16,247,174,160,191,202,16,1,96,189,164,191,157,255,255
28dA202,16,247,160,0,177,253,24,109,160,191,145,253,165,7,24,109,160,191,133,7
29dA96,141,93,194,201,255,240,9,201,0,240,4,224,255,16,1,138,96,141,154,194,141
30dA146,194,140,153,194,200,140,145,194,202,138,41,7,168,138,74,74,74,170,169,0
31dA24,202,48,4,105,3,144,249,141,161,191,185,129,197,41,3,109,161,191,105,96
32dA141,255,255,185,129,197,41,240,141,255,255,96,166,251,232,134,251,142,172
33dA194,169,195,160,120,32,98,194,162,255,202,142,194,194,228,8,240,16,48,14
34dA169,195,160,117,32,98,194,32,101,195,162,255,16,220,173,120,195,141,244,194
35dA141,235,194,173,121,195,141,245,194,141,236,194,160,0,177,253,141,240,194
36dA198,7,56,229,7,72,165,7,145,253,104,170,142,255,255,240,11,160,255,177,253
37dA157,255,255,136,202,208,247,162,1,134,7,166,8,228,251,240,3,232,134,8,96
38dA166,8,228,251,240,86,232,169,195,160,53,32,98,194,173,53,195,141,39,195,173
39dA54,195,141,40,195,160,0,177,253,174,255,255,240,18,142,48,195,24,105,255
40dA145,253,168,189,255,255,145,253,136,202,208,247,166,8,232,228,251,240,30
41dA142,79,195,169,195,160,120,32,98,194,162,255,232,142,95,195,169,195,160,117
42dA32,98,194,32,101,195,162,255,208,222,198,251,96,173,117,195,141,114,195,173
43dA118,195,141,115,195,174,255,255,189,255,255,157,255,255,202,16,247,96,165,8
44dA197,251,144,22,160,0,177,253,197,7,16,14,162,0,189,137,197,32,210,255,232
45dA224,5,208,245,96,165,8,32,196,196,169,44,32,210,255,165,7,32,196,196,162,3
46dA208,225,162,0,134,2,134,204,32,228,255,240,251,36,21,240,17,166,2,224,30
47dA240,241,32,210,255,157,162,191,232,134,2,16,230,201,13,208,19,169,0,166,2
48dA157,162,191,230,204,169,32,32,210,255,169,13,76,210,255,201,20,208,203,166
49dA2,240,199,32,210,255,202,134,2,16,191,141,11,196,141,22,196,32,117,197,160
50dA0,189,162,191,240,44,201,43,208,7,169,1,133,255,232,208,9,201,45,208,8,169
51dA255,133,255,232,189,162,191,240,19,201,48,48,15,201,58,16,11,153,194,191
52dA232,200,192,3,16,2,48,232,96,142,69,196,160,0,132,25,132,32,136,132,34,132
53dA35,169,25,32,244,195,224,255,240,10,142,81,196,32,31,197,133,34,162,255,189
54dA162,191,201,44,208,18,232,142,99,196,169,32,32,244,195,224,255,240,5,32,31
55dA197,133,35,96,32,49,196,169,1,36,25,240,36,16,21,165,34,197,8,48,6,169,1
56dA133,34,208,22,165,8,56,229,34,133,34,208,13,165,8,24,101,34,133,34,144,4
57dA169,0,133,34,169,1,36,32,240,36,16,21,165,35,197,7,48,6,169,1,133,35,208,22
58dA165,7,56,229,35,133,35,208,13,165,7,24,101,35,133,35,144,4,169,0,133,35,96
59dA32,215,196,162,0,189,194,191,240,3,32,210,255,232,224,3,208,243,96,133,20
60dA32,117,197,162,8,160,2,185,194,191,201,5,48,5,105,2,153,194,191,136,16,241
61dA160,2,165,20,10,133,20,185,194,191,42,201,16,41,15,153,194,191,136,16,242
62dA202,208,215,173,196,191,9,48,141,196,191,160,1,185,194,191,240,8,9,48,153
63dA194,191,136,16,243,96,173,196,191,208,19,173,195,191,141,196,191,173,194
64dA191,141,195,191,169,0,141,194,191,240,232,160,2,185,194,191,240,5,41,207
65dA153,194,191,136,16,243,162,8,160,125,24,185,69,191,144,2,9,16,74,153,69,191
66dA200,16,242,165,20,106,202,208,1,96,133,20,160,2,185,194,191,201,8,48,5,233
67dA3,153,194,191,136,16,241,48,211,169,0,141,194,191,141,195,191,141,196,191
68dA96,0,96,192,33,129,225,66,162,69,78,68,62,32

```

## Demo

This entry is *just for fun* and will probably never reach a decent byte count. It's just because the challenge is about some "ancient" tool, why not implement it for an ancient machine ;)

In the course of creating this thing, I was reminded once again that the C64 system doesn't provide any sensible way of converting between strings and integers -- only strings and floats are covered and this is ridiculous, so this piece of code contains own conversion routines. In fact, the only OS routines called are `GETIN` (read a single character from keyboard) and `CHROUT` (write a single character to the screen).

Now, assembly is probably the "least golfy" language ever. For how to "golf" this, my idea as seen here is a BASIC loader, writing the bytes of the final binary to some memory location and jumping there. It's a working BASIC program this way ;) If anyone has a better idea how to golf this, please leave a comment!

The text buffer is quite limited, using up the space between `$6000` and `$BFFF` (BASIC ROM is turned off as it's not needed) and the program itself resides at `$C000`. All in all, there's room for 255 lines with 95 characters each, and the program doesn't do *any* bounds checking, so playing with it, make sure your lines don't grow too large ;)

Finally, look here for the readable source, including my "golfing tool".

---

As this is pretty limited stuff, and the C64 *can* do better, here comes the "deluxe edition" using 80 columns display. To do this, the Kernal must be deactivated, so basic things like a keyboard driver, a font, bitmap manipulation logic for output, interrupt handling etc must be included, therefore it's quite a challenge to fit all this in the 4K area `$C000-$CFFF` (and this is needed for loading the program from a BASIC program to work).

Some random facts about this version:

* fits in the 4K, but narrowly ... got 6 "spare" bytes now 3686 3841 bytes ;)
* the basic loader is 13743 13385 13963 bytes (used the saved bytes for new feature "line editing")
* screen color and sprite data is hidden in the ram "below" the MMIO area `$D000-$DFFF`
* The PC-style text cursor is a "hardware cursor", using a sprite
* the bitmap uses the area `$E000-$FF3F`, freely accessible because the kernal is switched off
* There's an additional command implemented: `q` exits the editor
* Extra feature: command line editing using cursor `RIGHT` and `LEFT`, Pos1 (`HOME`), End (`SHIFT + HOME`) and backspace (`DEL`)

## Demo

Program to type in yourself, if you want 80s computer mag feeling:

```
0fOa=49152to52992:rEb:pOa,b:nE:sY49152
1dA162,2,181,0,157,0,207,232,208,248,173,32,208,133,2,173,33,208,133,3,173,17
2dA208,133,5,120,169,0,141,21,208,169,52,133,1,169,15,162,0,32,67,196,32,96,196
3dA162,127,169,0,157,0,218,202,16,250,169,240,141,18,218,141,21,218,169,104,141
4dA248,223,169,53,133,1,169,25,141,0,208,169,50,141,1,208,169,0,141,16,208,141
5dA29,208,141,23,208,141,28,208,169,1,141,39,208,141,27,208,141,21,208,169,228
6dA141,250,255,169,195,141,251,255,169,0,141,14,221,141,4,221,141,5,221,169,129
7dA141,13,221,169,1,141,14,221,173,0,221,41,252,141,0,221,173,24,208,133,4,32
8dA241,195,32,39,196,169,0,133,6,133,7,141,32,208,88,162,1,134,46,32,156,196
9dA120,32,25,196,173,0,221,9,3,141,0,221,165,4,141,24,208,169,55,133,1,169,1
10dA141,13,221,173,13,221,165,5,141,17,208,165,2,141,32,208,165,3,141,33,208
11dA169,0,141,21,208,162,2,189,0,207,149,0,232,208,248,88,96,133,10,169,0,133
12dA11,165,10,10,38,11,10,38,11,10,38,11,133,10,169,1,24,101,10,133,10,169,203
13dA101,11,133,11,96,169,0,133,9,165,6,10,10,10,10,38,9,10,38,9,10,38,9,133,8
14dA165,9,101,6,105,224,133,9,165,12,10,10,10,144,3,230,9,24,101,8,144,2,230,9
15dA133,8,96,160,224,132,9,200,132,11,160,64,132,10,160,0,132,8,162,50,169,0
16dA168,224,3,48,2,177,10,145,8,200,192,160,208,243,202,240,23,169,159,101,8
17dA133,8,144,3,230,9,24,169,160,101,10,133,10,144,218,230,11,176,214,96,72,132
18dA21,76,199,193,72,132,21,201,13,240,15,201,17,240,30,32,241,193,230,7,160,80
19dA196,7,208,52,160,0,132,7,230,6,160,25,196,6,208,40,198,6,32,59,193,240,33
20dA169,32,164,7,240,5,136,132,7,16,19,160,79,132,7,164,6,240,5,136,132,6,16,6
21dA160,0,132,7,240,3,32,241,193,165,6,10,10,10,105,50,141,1,208,169,0,141,16
22dA208,165,7,10,10,144,4,238,16,208,24,105,24,144,3,238,16,208,141,0,208,32
23dA229,195,104,164,21,96,24,74,176,67,32,235,192,160,7,177,10,41,240,153,13,0
24dA136,16,246,165,7,74,133,12,176,18,32,12,193,160,7,177,8,41,15,25,13,0,145,8
25dA136,16,244,96,32,12,193,160,7,177,8,41,240,74,74,74,74,74,25,13,0,106,106
26dA106,106,145,8,136,16,235,96,32,235,192,160,7,177,10,41,15,153,13,0,136,16
27dA246,165,7,74,133,12,176,25,32,12,193,160,7,177,8,10,10,10,10,10,25,13,0,42
28dA42,42,42,145,8,136,16,237,96,32,12,193,160,7,177,8,41,240,25,13,0,145,8,136
29dA16,244,96,174,113,202,236,114,202,240,11,181,22,202,16,2,162,15,142,113,202
30dA24,96,169,0,133,43,133,38,133,40,169,127,141,0,220,173,1,220,73,255,240,25
31dA170,41,4,240,6,165,43,9,128,133,43,138,41,251,240,9,230,40,32,161,195,105
32dA56,133,38,169,191,141,0,220,173,1,220,73,255,240,25,170,41,16,240,6,165,43
33dA9,64,133,43,138,41,239,240,9,230,40,32,161,195,105,48,133,38,169,223,141,0
34dA220,173,1,220,73,255,240,9,230,40,32,161,195,105,40,133,38,169,239,141,0
35dA220,173,1,220,73,255,240,9,230,40,32,161,195,105,32,133,38,169,247,141,0
36dA220,173,1,220,73,255,240,9,230,40,32,161,195,105,24,133,38,169,251,141,0
37dA220,173,1,220,73,255,240,9,230,40,32,161,195,105,16,133,38,169,253,141,0
38dA220,173,1,220,73,255,240,25,170,41,128,240,6,165,43,9,64,133,43,138,41,127
39dA240,9,230,40,32,161,195,105,8,133,38,169,254,141,0,220,173,1,220,73,255,240
40dA7,230,40,32,161,195,133,38,165,40,208,5,169,128,133,39,96,165,38,197,39,240
41dA51,133,39,162,25,134,41,162,1,134,42,5,43,174,114,202,149,22,202,16,2,162
42dA15,142,114,202,236,113,202,208,8,202,16,2,162,15,142,113,202,96,162,7,74
43dA176,4,202,16,250,96,138,24,96,166,41,240,4,202,134,41,96,166,42,240,4,202
44dA134,42,96,162,1,134,42,76,132,195,133,44,134,45,198,46,208,12,169,24,133,46
45dA169,1,77,21,208,141,21,208,32,141,194,169,255,141,25,208,166,45,165,44,64
46dA120,160,1,140,21,208,160,24,132,46,88,96,169,127,141,13,220,173,13,220,169
47dA1,141,26,208,141,25,208,169,16,141,18,208,173,17,208,41,127,141,17,208,169
48dA196,141,254,255,169,195,141,255,255,96,169,0,141,26,208,141,25,208,169,131
49dA141,13,220,96,173,17,208,9,32,141,17,208,169,121,141,24,208,96,173,17,208
50dA41,223,141,17,208,169,114,141,24,208,96,134,47,10,10,10,10,101,47,162,220
51dA134,48,160,0,132,47,162,4,145,47,200,208,251,230,48,202,208,246,96,169,0
52dA168,133,47,162,224,134,48,162,31,145,47,200,208,251,230,48,202,208,246,160
53dA63,145,47,136,16,251,96,32,121,194,184,176,24,170,16,3,44,115,202,41,127
54dA170,189,116,202,80,2,9,128,201,31,176,3,44,115,202,24,96,162,1,134,56,134
55dA55,202,142,0,96,134,54,166,55,160,57,32,208,198,32,188,199,32,235,199,166
56dA65,240,108,202,202,16,2,162,0,134,49,165,128,201,69,240,99,201,66,240,101
57dA201,108,240,103,201,76,240,102,201,80,240,105,201,97,240,103,201,73,240,124
58dA201,82,240,122,201,105,240,120,201,68,240,121,201,74,240,119,201,81,208,1
59dA96,162,0,32,104,201,165,67,166,54,224,0,240,167,32,191,198,201,255,240,8
60dA133,55,170,160,57,32,208,198,160,0,177,57,170,232,165,68,201,255,208,2,165
61dA56,32,191,198,133,56,16,131,32,0,199,16,63,169,0,133,68,240,203,169,1,133
62dA68,208,197,76,10,198,166,55,32,87,198,80,41,240,42,166,54,232,134,54,134,55
63dA160,57,32,208,198,169,0,168,145,57,200,132,56,32,118,198,16,14,240,82,240
64dA104,32,118,198,16,5,240,122,32,94,199,76,168,196,166,54,240,249,162,1,134
65dA67,202,134,68,162,2,165,49,240,3,32,49,201,165,67,166,54,32,191,198,201,255
66dA208,2,169,1,133,67,166,54,165,68,201,255,208,2,169,0,32,191,198,141,167,197
67dA166,67,32,87,198,166,67,224,255,240,191,232,134,67,208,242,32,0,199,198,55
68dA160,0,177,57,133,56,230,56,32,118,198,230,55,162,1,134,56,208,162,160,0,166
69dA56,202,138,145,57,32,118,198,166,54,228,55,240,124,230,55,162,1,134,56,208
70dA116,160,0,196,54,240,110,177,57,208,24,165,55,197,54,208,5,198,55,200,132
71dA56,32,94,199,160,1,196,55,48,86,132,55,16,82,152,145,57,200,132,56,208,74
72dA166,54,240,70,166,55,160,3,202,240,6,200,202,240,2,200,202,232,140,54,198
73dA142,56,198,228,55,240,7,169,32,32,125,193,208,5,169,62,32,125,193,32,87,198
74dA160,255,162,255,136,240,4,228,54,208,219,169,32,166,56,32,125,193,202,208
75dA250,169,38,32,125,193,169,13,32,125,193,76,168,196,160,50,32,208,198,160,0
76dA177,50,240,15,141,110,198,230,50,177,50,32,125,193,200,192,255,208,246,169
77dA13,76,125,193,165,57,24,101,56,133,50,165,58,105,0,133,51,165,50,101,49,133
78dA52,165,51,105,0,133,53,160,0,177,57,56,229,56,48,8,168,177,50,145,52,136,16
79dA249,164,49,136,16,1,96,185,130,0,145,50,136,16,248,160,0,177,57,24,101,49
80dA145,57,165,56,24,101,49,133,56,96,141,203,198,201,255,240,9,201,0,240,4,224
81dA255,16,1,138,96,140,254,198,200,140,247,198,202,138,41,7,168,138,74,74,74
82dA170,169,0,24,202,48,4,105,3,144,249,133,63,185,244,202,41,3,101,63,105,96
83dA133,255,185,244,202,41,240,133,255,96,166,54,232,134,54,134,64,160,59,32
84dA208,198,198,64,166,64,228,55,240,14,48,12,160,61,32,208,198,32,175,199,166
85dA64,16,227,165,59,141,74,199,165,60,141,75,199,160,0,177,57,141,70,199,198
86dA56,56,229,56,72,165,56,145,57,104,160,0,145,59,170,240,11,160,255,177,57
87dA157,255,255,136,202,208,247,162,1,134,56,166,55,228,54,240,3,232,134,55,96
88dA166,55,228,54,240,74,232,160,61,32,208,198,165,61,141,134,199,165,62,141
89dA135,199,160,0,177,61,240,20,170,177,57,134,64,24,101,64,145,57,168,189,255
90dA255,145,57,136,202,208,247,166,55,232,134,64,228,54,240,21,160,59,32,208
91dA198,230,64,166,64,160,61,32,208,198,32,175,199,166,64,208,231,198,54,96,160
92dA0,177,61,168,177,61,145,59,136,16,249,96,165,55,197,54,144,22,160,0,177,57
93dA197,56,16,14,162,0,189,252,202,32,125,193,232,224,5,208,245,96,165,55,32
94dA192,201,169,44,32,125,193,165,56,32,192,201,162,3,208,225,166,7,134,74,166
95dA6,134,75,160,0,132,65,132,66,132,76,164,76,240,6,169,13,32,125,193,96,32
96dA125,196,176,241,112,86,164,65,192,80,240,233,196,66,240,7,182,127,150,128
97dA136,16,245,32,125,193,166,6,134,72,166,7,134,73,208,8,166,6,228,75,208,2
98dA198,75,153,128,0,200,132,66,230,65,196,65,240,23,185,128,0,32,125,193,165,7
99dA208,10,169,24,197,72,208,4,198,72,198,75,200,16,229,166,72,134,6,166,73,134
100dA7,32,119,193,16,153,201,13,208,4,230,76,208,40,201,11,208,10,166,66,228,65
101dA240,135,230,66,16,30,201,12,208,8,166,66,240,46,198,66,16,18,201,15,208,6
102dA162,0,134,66,16,8,201,16,208,31,166,65,134,66,166,75,134,6,24,165,74,101
103dA66,201,80,133,7,144,6,233,80,133,7,230,6,32,119,193,76,251,199,201,17,208
104dA249,164,66,240,245,136,198,65,132,66,196,65,240,7,182,129,150,128,200,16
105dA245,32,125,193,166,6,134,72,166,7,134,73,164,66,196,65,240,9,185,128,0,32
106dA125,193,200,16,243,169,32,32,125,193,166,72,134,6,166,73,134,7,32,119,193
107dA76,251,199,141,12,201,141,23,201,32,104,202,160,0,181,128,240,43,201,43
108dA208,7,169,1,133,255,232,208,9,201,45,208,7,169,255,133,255,232,181,128,240
109dA19,201,48,48,15,201,58,16,11,153,209,0,232,200,192,3,16,2,48,233,96,134,71
110dA160,0,132,69,132,70,136,132,67,132,68,169,69,32,246,200,228,71,240,9,134
111dA71,32,24,202,133,67,166,71,181,128,201,44,208,17,232,134,71,169,70,32,246
112dA200,228,71,240,5,32,24,202,133,68,96,32,49,201,169,1,36,69,240,36,16,21
113dA165,67,197,55,48,6,169,1,133,67,208,22,165,55,56,229,67,133,67,208,13,165
114dA55,24,101,67,133,67,144,4,169,0,133,67,169,1,36,70,240,36,16,21,165,68,197
115dA56,48,6,169,1,133,68,208,22,165,56,56,229,68,133,68,208,13,165,56,24,101
116dA68,133,68,144,4,169,0,133,68,96,32,210,201,162,0,181,209,240,3,32,125,193
117dA232,224,3,208,244,96,133,212,32,104,202,162,8,160,2,185,209,0,201,5,48,5
118dA105,2,153,209,0,136,16,241,160,2,165,212,10,133,212,185,209,0,42,201,16,41
119dA15,153,209,0,136,16,242,202,208,215,165,211,9,48,133,211,160,1,185,209,0
120dA240,8,9,48,153,209,0,136,16,243,96,165,211,208,14,165,210,133,211,165,209
121dA133,210,169,0,133,209,240,238,160,2,185,209,0,240,5,41,207,153,209,0,136
122dA16,243,162,8,160,125,24,185,84,0,144,2,9,16,74,153,84,0,200,16,242,165,212
123dA106,202,208,1,96,133,212,160,2,185,209,0,201,8,48,5,233,3,153,209,0,136,16
124dA241,48,211,169,0,133,209,133,210,133,211,96,15,15,127,9,5,3,1,7,11,13,17,0
125dA69,83,90,52,65,87,51,88,84,70,67,54,68,82,53,86,85,72,66,56,71,89,55,78,79
126dA75,77,48,74,73,57,44,64,58,46,45,76,80,43,47,94,61,0,15,59,42,124,21,81,19
127dA32,50,0,0,49,10,6,4,2,8,12,14,18,0,101,115,122,36,97,119,35,120,116,102,99
128dA38,100,114,37,118,117,104,98,40,103,121,39,110,111,107,109,48,106,105,41
129dA60,64,91,62,45,108,112,43,63,94,61,0,16,93,42,124,22,113,20,32,34,0,0,33,0
130dA96,192,33,129,225,66,162,69,78,68,62,32,34,20,34,85,119,85,85,0,82,5,34,85
131dA119,85,85,0,34,20,119,68,102,68,119,0,82,5,119,68,102,68,119,0,34,20,34,85
132dA85,85,34,0,82,5,34,85,85,85,34,0,65,34,85,85,85,85,34,0,82,5,80,85,85,85
133dA34,0,0,34,20,102,17,51,119,0,0,82,5,102,17,51,119,0,0,34,20,34,119,68,34,0
134dA0,82,5,34,119,68,34,0,0,34,20,34,85,85,34,0,0,82,5,34,85,85,34,0,0,65,34
135dA85,85,85,51,0,0,82,5,80,85,85,51,0,2,2,2,2,2,0,2,0,102,102,15,6,15,6,6,0
136dA37,113,66,98,18,100,37,0,34,82,4,0,0,0,0,0,36,66,66,66,66,66,36,0,0,82,34
137dA119,34,82,0,0,0,0,0,7,0,32,32,64,1,1,2,2,2,36,36,0,33,83,117,113,81,81,33
138dA0,34,85,17,34,33,69,114,0,23,52,86,113,17,21,18,0,39,65,65,98,82,82,34,0
139dA34,85,85,35,81,81,34,0,0,34,34,0,0,34,34,4,0,16,39,64,39,16,0,0,2,69,33,18
140dA34,64,2,0,32,80,118,81,115,69,39,0,64,64,99,84,84,84,99,0,16,16,50,85,87
141dA84,50,0,16,32,115,37,37,35,33,2,66,64,98,82,82,82,82,0,36,4,37,38,38,38,37
142dA64,32,32,38,39,37,37,37,0,0,0,98,85,85,85,82,0,0,0,99,85,85,99,65,65,0,0
143dA98,84,70,65,70,0,32,32,117,37,37,37,19,0,0,0,85,85,87,119,34,0,0,0,85,37
144dA37,34,82,4,1,2,114,36,34,66,113,0,36,34,34,33,34,34,36,0,82,165,5,6,5,5,6
145dA4,34,37,21,7,5,5,5,0,99,84,84,100,84,84,99,0,103,84,84,86,84,84,103,0,118
146dA69,68,103,69,69,71,0,87,82,82,114,82,82,87,0,21,21,22,22,22,85,37,0,69,71
147dA71,69,69,69,117,0,82,85,117,117,117,85,82,0,98,85,85,101,69,71,67,0,98,85
148dA84,98,97,85,82,0,117,37,37,37,37,37,34,0,85,85,85,85,87,119,37,0,85,85,37
149dA34,34,82,82,0,115,18,34,34,34,66,115,0,6,50,66,114,226,66,54,0,48,64,67,68
150dA68,51,17,34,221,235,221,170,136,170,170,255,173,250,221,170,136,170,170
151dA255,221,235,136,187,153,187,136,255,173,250,136,187,153,187,136,255,221
152dA235,221,170,170,170,221,255,173,250,221,170,170,170,221,255,190,221,170
153dA170,170,170,221,255,173,250,175,170,170,170,221,255,255,221,235,153,238
154dA204,136,255,255,173,250,153,238,204,136,255,255,221,235,221,136,187,221
155dA255,255,173,250,221,136,187,221,255,255,221,235,221,170,170,221,255,255
156dA173,250,221,170,170,221,255,255,190,221,170,170,170,204,255,255,173,250
157dA175,170,170,204,255,253,253,253,253,253,255,253,255,153,153,240,249,240
158dA249,249,255,218,142,189,157,237,155,218,255,221,173,251,255,255,255,255
159dA255,219,189,189,189,189,189,219,255,255,173,221,136,221,173,255,255,255
160dA255,255,248,255,223,223,191,254,254,253,253,253,219,219,255,222,172,138
161dA142,174,174,222,255,221,170,238,221,222,186,141,255,232,203,169,142,238
162dA234,237,255,216,190,190,157,173,173,221,255,221,170,170,220,174,174,221
163dA255,255,221,221,255,255,221,221,251,255,239,216,191,216,239,255,255,253
164dA186,222,237,221,191,253,255,223,175,137,174,140,186,216,255,191,191,156
165dA171,171,171,156,255,239,239,205,170,168,171,205,255,239,223,140,218,218
166dA220,222,253,189,191,157,173,173,173,173,255,219,251,218,217,217,217,218
167dA191,223,223,217,216,218,218,218,255,255,255,157,170,170,170,173,255,255
168dA255,156,170,170,156,190,190,255,255,157,171,185,190,185,255,223,223,138
169dA218,218,218,236,255,255,255,170,170,168,136,221,255,255,255,170,218,218
170dA221,173,251,254,253,141,219,221,189,142,255,219,221,221,222,221,221,219
171dA255,173,90,250,249,250,250,249,251,221,218,234,248,250,250,250,255,156,171
172dA171,155,171,171,156,255,152,171,171,169,171,171,152,255,137,186,187,152
173dA186,186,184,255,168,173,173,141,173,173,168,255,234,234,233,233,233,170
174dA218,255,186,184,184,186,186,186,138,255,173,170,138,138,138,170,173,255
175dA157,170,170,154,186,184,188,255,157,170,171,157,158,170,173,255,138,218
176dA218,218,218,218,221,255,170,170,170,170,168,136,218,255,170,170,218,221
177dA221,173,173,255,140,237,221,221,221,189,140,255,249,205,189,141,29,189,201
178dA255,207,191,188,187,187,204,238,221

```

Readable source code.
> 5 votes

---
Tags: code-golf
---


# Question
Title: Identify the direction of lines in an ASCII-figure
## Challenge:

Take a rectangular figure consisting of the two characters `#` and  (whitespace, ASCII-32), and identify which direction the lines are. The options are: 'Vertical', 'Horizontal', 'Left Diagonal' and 'Right Diagonal'.

### Input:

The input will be a figure of size **n-by-m** where **5 \<= m,n \<= 20**. There will be two spaces between horizontal lines, two spaces between lines in the horizontal/vertical direction. Note that the lines doesn't have to start or end in a corner. The input will look like this:

Horizontal:

```
##########

##########

##########

```

Vertical (note that there can be leading spaces):

```
 #  #  #
 #  #  #
 #  #  #
 #  #  #
 #  #  #

```

Left diagonal:

```
#  #  #
 #  #
  #  #
#  #  #
 #  #

```

Right diagonal:

```
#  #  #  #  #
  #  #  #  #
 #  #  #  #  #
#  #  #  #  #
  #  #  #  #

```
* The input format is optional. You may substitute the visual newlines by `\n`, or create the grid by concatenating the rows with ASCII-10 (relevant for MATLAB/Octave).
* You may not take the input as numbers (`1/0`) instead of `#` and `0`.

### Output:

The output shall be 4 distinct values/outputs for each of the four different cases. It can for instance be **1,2,3,4**, or **V,H,L,R**.

### Test cases:

There will be an asterisk over the top left corner of the figure, and an asterisk below the bottom left corner of the figures. This is to indicate where the figure starts and ends.

```
Horizontal:
*
#####

#####

    *
*

###########

          *
*

##########################

##########################

##########################
                         *

Vertical:
*
#  #  #  #
#  #  #  #
#  #  #  #
#  #  #  #
#  #  #  #
         *
*
 #  #  #  #  #  #
 #  #  #  #  #  #
 #  #  #  #  #  #
 #  #  #  #  #  #
 #  #  #  #  #  #
                  *

Left diagonal
*
#  #  #
 #  #
  #  #
#  #  #
 #  #
      *
*
#  #  #  #  #
 #  #  #  #
  #  #  #  #
#  #  #  #  #
 #  #  #  #
  #  #  #  #
            *
*
  #  #  #
#  #  #  #
 #  #  #
  #  #  #
#  #  #  #
         *

Right diagonal
*
#  #  #  #  #
  #  #  #  #
 #  #  #  #  #
#  #  #  #  #
  #  #  #  #
             *
*
 #  #  #  #  #  #  #
#  #  #  #  #  #  #
  #  #  #  #  #  #
 #  #  #  #  #  #  #
#  #  #  #  #  #  #
                   *

```

---

This is so the shortest code in each language wins.

# Answer
# Slip, 6 + 2 = 8 bytes

+2 bytes for the `f` flag.

```
^*`#`#

```

Try it here!

Prints one of the following:

```
##

```

```
#
#

```

```
#
 #

```

```
 #
#

```

### Explanation

The `^*` sets the IP's direction to any one of the eight octilinear directions. Then ``#`#` simply matches two hash symbols in that direction. The `f` flag limits Slip to looking only for the first match, and by default the bounding box of that match is printed to STDOUT.

The pattern itself would be two bytes shorter in Snails (`z\#2`), but I don't think Snails can print the match itself, it only has numeric output (and adapting the pattern to printing 4 different numbers based on the direction would most likely take a lot more bytes).
> 6 votes

# Answer
## Grime, 4 bytes

```
s./$

```

Try it online!

Prints one of the following 2x2 blocks (which should be padded with spaces, some of which are swallowed up by SE):

```
##

```

```
#
#

```

```
#
 #

```

```
#

```

Where the last one indicates lines along antidiagonals.

### Explanation

The pattern matches a 2x2 square starting from the first `#` in reading order. The `#` is matched with `s` (the "symbol" character class), the following character with `.` (which can be any character). To this 2x1 rectangle we concatenate another one vertically with `/`. That other rectangle is just `$` which always matches, so this simply fills up the 2x2 square with the two characters below. This unique identifies all four cases.
> 6 votes

# Answer
# Retina, 48 bytes

```
ms`^(.*¶)?( *)( ?#)((#)|[^¶]*¶\2( ?#)).*
$3$5¶$6

```

Try it online! Returns the same results as @MartinEnder's Slip answer.
> 1 votes

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


title: Convert Between Percentages and Decimal

text:
# Question
Title: Convert Between Percentages and Decimal
I, uh....honestly can't believe we don't have this one yet.

# Challenge

Write two functions or programs that:

1. Convert from decimal to percentage
2. Convert from percentage to decimal

You may also write a single program that does both of the above.

# Format

Percentages *must* be taken and returned with a percent sign. (In many languages, this means they will be strings.) They may be integers or floating point numbers.

Decimals are just floating point numbers.

You do not need to handle rounding errors involving very large or very small floating point numbers.

In cases where the numbers are integers (such as 56.0) you may return `56`, `56.`, or `56.0`. (This is intended to make I/O more flexible.)

# Test Cases

```
    0.0% <-> 0.0
  100.0% <-> 1.0
   56.0% <-> 0.56
  123.0% <-> 1.23
  -11.0% <-> -0.11
-214.91% <-> -2.1491

```

# Scoring

This is , so the shortest answer in each language wins. If you write two separate programs, add their sizes for your score.

# Answer
# Mathematica, 34+20=54

to Decimal

```
ToExpression@StringDrop[#,-1]/100&

```

to Percentage

```
ToString[100#]<>"%"&

```
> 4 votes

# Answer
# Python 2, 59 bytes

This one does both.

```
lambda s:'%'in s and`float(s[:-1])/100`or`float(s)*100`+'%'

```

Try it online!

# Single functions, score 27 + 28 = 55

## Decimal to percent, 27 bytes

```
lambda s:`float(s)*100`+'%'

```

Try it online!

## Percent to decimal, 28 bytes

```
lambda s:`float(s[:-1])/100`

```

Try it online!
> 3 votes

# Answer
# Japt, 7 bytes

From percentage:

```
/L

```

Test it online!

To percentage:

```
*L+'%

```

Test it online!
> 3 votes

# Answer
# Java, 45 bytes

-4 bytes thanks to musicman523.

From decimal, to percent:

```
a->new Float(a.split("%")[0])/100

```

To percent, from decimal:

```
a->a*100+"%"

```
> 3 votes

# Answer
# Dyalog APL, 20 bytes

To percentages

```
'%',⍨100∘×

```

From percentages

```
.01×∘⍎¯1↓⊢

```

Try it online!
> 2 votes

# Answer
# Perl 6, 10 + 10 = 20 bytes

Decimal to percentage:

```
*×100~'%'

```

Percentage to decimal:

```
*.chop/100

```
> 2 votes

# Answer
# Python 3, ~~81~~ ~~77~~ 74 bytes

```
def a(m):e=m.strip("%");f=float(e);return f/100if e!=m else str(f*100)+"%"

```

Try it online!

EDIT: Saved 4 bytes by removing some whitespace.
EDIT: Saved another 3 bytes by setting float(e) to a variable.
> 1 votes

# Answer
# PHP, ~~62 bytes~~ 61 bytes

Thanks @ckjbgames

```
$i=readline();echo strstr($i,'%')?(float)$i/100:($i*100).'%';

```

Try it online!
> 1 votes

# Answer
# Haskell 16+19 = 35 bytes

Percent to decimal:

```
(/100).read.init

```

Decimal to percent:

```
(++"%").show.(*100)

```
> 1 votes

# Answer
# JavaScript (ES6), 20+12=32 bytes

## To Decimal

```
p=>parseFloat(p)/100

```

## To Percentage

```
d=>d*100+'%'

```
> 1 votes

# Answer
# 05AB1E, 8 bytes

From % to decimal

```
¨т/

```

Try it online!

And from decimal to %

```
т*'%«

```

Try it online!

### Explanations

```
¨т/
¨   # Cut of last character
 т/ # Divide by 100 (I know. Very creative)

 т*'%«
 т*    # Multiply by 100
   '%« # Append '%'

```
> 1 votes

# Answer
# Jelly, 5 + 5 = 10 bytes

% → number

```
ṖV÷ȷ2

```

Try it online!

number → %

```
×ȷ2”%

```

Try it online!

Full program only.
> 1 votes

# Answer
# Excel, 15 + 4 = 19 bytes

Assuming that the values to be converted are stored in field A1

**Percentage to decimal**

```
=NUMBERVALUE(A1)

```

**Decimal to percentage**

```
=A1%

```
> 1 votes

# Answer
# Python 3, ~~26~~ ~~24~~ 23 bytes + 27 bytes = 50 bytes

First program (% -\> decimal)

```
float(input()[:-1])*.01

```

Second program (decimal -\> %):

```
str(float(input())*100)+'%'

```

Rather similar to the other one. Pretty easy, too.
> 0 votes

# Answer
# Python 2, 67 bytes

```
lambda x:`float(x.strip('%'))*[100,.01]['%'in x]`+['%','']['%'in x]

```

Try it online!
> 0 votes

# Answer
# Python 3, 71 bytes

```
i=input()
print(float(i[:-1])/100if'%'in i else'%.2f%%'%(float(i)*100))

```

Try it online!
> 0 votes

# Answer
# **Haskell, ~~60~~ 42 bytes**

Decimal to percentage (21 bytes)

```
f x = show(x*100)++"%"

```

Percentage to decimal (21 bytes)

```
f x = read(init x)/100

```
> 0 votes

# Answer
# ES6, 34 bytes

```
n=>1/n?n*100+'%':n.slice(0,-1)/100

```

(Now works with `0.0` and `0%`)

Try it online!

This works because `1/n` is `NaN` if a "%" is present and `NaN` is like `false`.

(`1/n` with `n = 0` is `Infinity` (not `NaN`) and `Infinity` is not considered `false` by JS)
> 0 votes

# Answer
# Retina, 77 bytes

```
^-?
$&00
\b%?$
00%$&
\.(..)
$1.
(....)\.(.*)%%
.$1$2
^(-?)0+\B|\B0+(%?)$
$1$2

```

Try it online! Link includes test cases. Requires and returns input with at least one digit before and after the decimal point. Explanation: The first stage inserts two leading zeros after any sign, while the second stage inserts two trailing zeros and a `%` sign before any `%` sign. (The `\b` is needed to stop the pattern matching twice for percentages.) The third stage then multiplies by 100. This results in the correct numerical value for floats converted into percentages, but percentages are now 10,000 times too big and now have a duplicated `%` sign, so the fourth stage corrects this. The final stage then trims leading and/or trailing zeros as necessary.
> 0 votes

# Answer
# perl 5: 24 bytes

**From % to decimal: 8 bytes** (7 + 1 for p flag)

```
$_/=100

```

*Usage:*

```
echo '-214.91%' | perl -pe '$_/=100'

```

*Output:*

```
-2.1491

```

**From decimal to %: 16 bytes** (15 + 1 for p flag)

```
$_*=100;$_.="%"

```

*Usage:*

```
echo -2.1491 | perl -pe '$_*=100;$_.="%"'

```

*Output:*

```
-214.91%

```
> 0 votes

# Answer
# ,,,, score 19

## Percent to decimal, 10 bytes

```
-1⇆⊣f100⇆÷

```

### Explanation

Take 56.0% for example.

```
-1⇆⊣f100⇆÷

               implicit input                               ["56.0%"]
-1             push -1                                      ["56.0%", -1]
  ⇆            switch "56.0%" and -1                        [-1, "56.0%"]
   ⊣           pop -1 and "56.0%" and push "56.0"           ["56.0"]
    f          pop "56.0" and push 56.0 (convert to float)  [56.0]
     100       push 100                                     [56.0, 100]
        ⇆      switch 56.0 and 100                          [100, 56.0]
         ÷     pop 100 and 56.0 and push 56.0 / 100         [0.56]
               implicit output                              []

```

## Decimal to percent, 9 bytes

```
100×s'%⇆+

```

### Explanation

Take 0.56 for example.

```
100×s'%⇆+

               implicitly take input and convert to float    [0.56]
100            push 100                                      [0.56, 100]
   ×           pop 0.56 and 100 and push 100 * 0.56          [56.0]
    s          pop 56.0 and push "56.0" (convert to string)  ["56.0"]
     '%        push "%"                                      ["56.0", "%"]
       ⇆       switch "56.0" and "%"                         ["%", "56.0"]
        +      pop "%" and "56.0" and push "56.0%"           ["56.0%"]
               implicit output                               []

```
> 0 votes

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


title: How much Mana do I need?

text:
# Question
Title: How much Mana do I need?
Dungeon Master was one of the first ever real-time role-playing games, originally released in 1987 on the Atari ST. Among other exciting things for the time, it offered a rather sophisticated spell system based on runes.

Your task today is to write a program or function that evaluates the number of Mana points required to cast a given spell in Dungeon Master.

<sup>*The 'spell cast' system is the top right cyan box in the above picture.*</sup>

## Spells, runes and Mana

Dungeon Master spells are composed of 2 to 4 runes, picked among the following categories, in this exact order:

1. Power (mandatory)
2. Elemental Influence (mandatory)
3. Form (optional)
4. Class / Alignment (optional)

It means that valid spells are either:

* Power + Elemental Influence
* Power + Elemental Influence + Form
* Power + Elemental Influence + Form + Class / Alignment

Each category contains 6 runes, and each rune has an associated base Mana cost:

```
=============================================================================
| Power               | Rune      |   Lo |   Um |   On |   Ee |  Pal |  Mon |
|                     +-----------+------+------+------+------+------+------+
|                     | Base cost |    1 |    2 |    3 |    4 |    5 |    6 |
=============================================================================
| Elemental Influence | Rune      |   Ya |   Vi |   Oh |  Ful |  Des |   Zo |
|                     +-----------+------+------+------+------+------+------+
|                     | Base cost |    2 |    3 |    4 |    5 |    6 |    7 |
=============================================================================
| Form                | Rune      |  Ven |   Ew | Kath |   Ir |  Bro |  Gor |
|                     +-----------+------+------+------+------+------+------+
|                     | Base cost |    4 |    5 |    6 |    7 |    7 |    9 |
=============================================================================
| Class / Alignment   | Rune      |   Ku |  Ros | Dain | Neta |   Ra |  Sar |
|                     +-----------+------+------+------+------+------+------+
|                     | Base cost |    2 |    2 |    3 |    4 |    6 |    7 |
=============================================================================

```

## Evaluating the Mana cost

The Mana cost of the spell is the sum of the Mana cost of all runes:

* The cost of the Power rune always equals its base cost (from 1 to 6).
* For the other runes, the following formula applies:

where ***power*** is the base cost of the Power rune.

## Examples

```
Spell: Lo Ful
Cost : 1 + floor((1 + 1) * 5 / 2) = 1 + 5 = 6

Spell: Um Ful
Cost : 2 + floor((2 + 1) * 5 / 2) = 2 + 7 = 9

Spell: Pal Vi Bro
Cost : 5 + floor((5 + 1) * 3 / 2) + floor((5 + 1) * 7 / 2) = 5 + 9 + 21 = 35

```

## Clarifications and rules

* Your input will consist of 2 to 4 strings designating the runes of the spell. You can take them in any reasonable format, such as 4 distinct parameters, an array of strings (e.g. `['Lo', 'Ful']`), or just one string with a single-character separator of your choice (e.g. `'Lo Ful'`). Please specify the selected input format in your answer.
* The runes are guaranteed to be valid.
* The order of the categories must be respected. Unused categories may be either missing or replaced with some falsy value.
* You can accept the runes in any of these formats: 1. A capital letter followed by lower case (`'Ful'`) 2. All lower case (`'ful'`) 3. All upper case (`'FUL'`). But you *can't* mix different formats.
* Quite obviously, we do not care to know whether the spell actually has some effect in the game (for the curious, useful spells are listed here.)
* This is , so the shortest code in bytes wins.
* And remember: Lord Chaos is watching you!

## Test cases

```
Spell          | Output
---------------+-------
Lo Ful         | 6
Um Ful         | 9
On Ya          | 7
Lo Zo Ven      | 12
Pal Vi Bro     | 35
Ee Ya Bro Ros  | 31
On Ful Bro Ku  | 31
Lo Zo Kath Ra  | 20
On Oh Ew Sar   | 35
Ee Oh Gor Dain | 43
Mon Zo Ir Neta | 68
Mon Des Ir Sar | 75

```

# Answer
> 6 votes
# SOGL V0.12, ~~110~~ 78 bytes

```
θKKι"LUOEPM”;W:A≤{B"⁶Μ↓§QΕņj“L─"¶Ζq«╝γDyΜ2¶S◄Μ$‘č¹I6nēwι{_Cb:ƧRA=┌*ΚKι=?aIc*»+

```

Try it Here!

Could probably golf a byte or two from redoing everything

Explanation:

```
θ            split on spaces
 K           pop the 1st item
  K          pop from the string the 1st character
   ι         remove the original string from stack
    "”;W     get the chars index in "LUOEPM"
        :A   save a copy to variable A
          ≤  put the power (used as the mana) on the bottom of the stack (with the thing above being the input array)

{            for the leftover items in the input do
 B             save the current name on B
  "..“         push 456779223467234567
      L─       base-10 decode it (yes, silly, but it converts it to an array of digits)
        ".‘    push "VEKIBGKRDN-SYVOFDZ"

      č        chop to characters
       ¹       create an array of those two
        I      rotate clockwise
         6n    group to an array with sub-arrays of length 6 (so each array in the array contains 3 items, corresponding to the categories, each with 6 arrays with the runes 1st letter (or "-" in the case of Ra) and base cost)
           ē   push variable e (default = user input number, which errors and defaults to 0) and after that increase it (aka `e++`)
            w  get that item in the array (the array is 1-indexed and the variable is not, so the array was created shifted (which somehow saves 0.9 ≈ 1 byte in the compression))

 ι             remove the original array
  {            for each in that (current category) array
   _             dump all contents on stack (so pushing the runes name and then base cost)
    C            save pop (base cost) on variable B
     b:          duplicate the name
       ƧRA=      push if pop = "RA"
           ┌*    get that many (so 0 or 1) dashes
             Κ   prepend the "" or "-" to the name
              K  pop the 1st letter of the name
               ι remove the modified name, leaving the 1st letter on the stack

         =?      if top 2 are equal (one of the dumped items and the 1st letter of the current inputs)
           a       push variable A (the power)
            I      increase it
             c     push variable C (the current base cost)
              *    multiply
               »   floor-divide by 2
                +  add that to the power

```

# Answer
> 18 votes
# Python 2, ~~135~~ ~~119~~ 115 bytes

```
b=[int('27169735 2  4567 435262'[int(x,36)%141%83%50%23])for x in input()]
print b[0]+sum(a*-~b[0]/2for a in b[1:])

```

Try it online!

Input is list of strings from stdin

# Answer
> 11 votes
# 05AB1E, ~~83~~ 82 bytes

```
.•Y<εΔ•¹нk©.•M₄Pç•²нkÌ.•Jrû •³нkD(i\ë4 3‡4+}.•A1Δ#•I4èkD(i\ë3LJ012‡Ì})ćsv®>y*;(î(+

```

Try it online!

-1 thanks to Emigna.

SOOOOOOO ungolfed :(

Explanation:

```
.•Y<εΔ•¹нk©.•M₄Pç•²нkÌ.•Jrû •³нkD(i\ë4 3‡4+}.•A1Δ#•I4èkD(i\ë3LJ012‡Ì})ćsv®>y*;(î(+ Accepts four runes as separate lines, lowercase. Use Ø for missing runes.
.•Y<εΔ•¹нk©                                                                        Index first letter of first rune into "aluoepm" ("a" makes 1-indexed)
           .•M₄Pç•²нkÌ                                                             Index first letter of second rune into "yvofdz", 2-indexed.
                      .•Jrû •³нkD(i\ë4 3‡4+}                                       Index first letter of third rune into "vekibg", 0-indexed, if it's not there pop, else, if index is 4 replace with 3, else keep as-is, then increment by 4.
                                            .•A1Δ#•I4èkD(i\ë3LJ012‡Ì}              Index fourth letter (modular wrapping) of fourth rune into "kodnra", if it's not there pop, else, if index is one of 1, 2 or 3, replace with 0, 1 or 2 respectively, else keep as-is, then increment by 2.
                                                                     )ćs           Wrap all numbers into a list, keeping the power rune behind.
                                                                        v          For each
                                                                         ®>y*;(î(   Apply the formula
                                                                                +  Add to total sum

```

# Answer
> 11 votes
# JavaScript (ES6), ~~157~~ ~~156~~ ~~116~~ ~~112~~ ~~100~~ ~~99~~ 97 bytes

Takes input as an array of strings.

```
a=>a.map(c=>t+=(v=+`27169735020045670435262`[parseInt(c,36)%141%83%50%23],+a?a*v+v>>1:a=v),t=0)|t

```
* Saved a massive 44 bytes by borrowing the indexing trick from ovs' Python solution \- if you're upvoting this answer, please upvote that one too.
* Saved 13 bytes thanks to Arnauld pointing out what should have been an obvious opportunity to use a ternary.

Try it Online!

---

## Explanation

Hoo, boy, this is gonna be fun - my explanations to *trivial* solutions suck at the best of times! Let's give it a go ...

```
a=>

```

An anonymous function taking the array as an argument via parameter `a`.

```
a.reduce((t,c)=>,0)

```

Reduce the elements in the array by passing each through a function; the `t` parameter is the running total, the `c` parameter is the current string and `0` is the initial value of `t`.

```
parseInt(c,36)

```

Convert the current element from a base 36 string to a decimal integer.

```
%141%83%50%23

```

Perform a few modulo operations on it.

```
+`27169735 2  4567 435262`[]

```

Grab the character from the string at that index and convert it to a number.

```
v=

```

Assign that number to variable `v`.

```
+a?

```

Check if variable `a` is a number. For the first element `a` will be the array of strings, trying to convert that to a number will return `NaN`, which is falsey. On each subsequent pass, `a` will be a positive integer, which is truthy.

```
a*v+v>>1

```

If `a` is a number then we multiply it by the value of `v`, add the value of `v` and shift the bits of the result 1 bit to the right, which gives the same result as dividing by 2 and flooring.

```
:a=v

```

If `a` is not a number the we assign the value of `v` to it, which will also give us a `0` to add to our total on the first pass.

```
t+

```

Finally, we add the result from the ternary above to our running total.

---

## Original, 156 bytes

```
a=>a.reduce((t,c)=>t+(p+1)*g(c)/2|0,p=(g=e=>+`123456234567456779223467`["LoUmOnEePaMoYaViOhFuDeZoVeEwKaIrBrGoKuRoDaNeRaSa".search(e[0]+e[1])/2])(a.shift()))

```

# Answer
> 6 votes
# JavaScript, ~~212~~ ~~210~~ ~~207~~ 206 bytes

Straight-forward searching algorithm, the search strings are just contributing to the total bytes.

**Code**

```
s=>eval('p=q=+(e=s.map(r=>"1 2 3 4 5  6  2 3 4 5  6  7 4  5 6   7 7  9  2 2  3   4   6 7"["LoUmOnEePalMonYaViOhFulDesZoVenEwKathIrBroGorKuRosDainNetaRaSar".search(r)])).shift();e.map(c=>p+=((q+1)*c)>>1);p')

```

**Input Format**

String array, each item is a first-letter-capitalized string. Example: \["Mon", "Zo", "Ir", "Neta"\]

**Explanation**

```
e=s.map(r=>"1 2 3 4 5  6  2 3 4 5  6  7 4  5 6   7 7  9  2 2  3   4   6 7"["LoUmOnEePalMonYaViOhFulDesZoVenEwKathIrBroGorKuRosDainNetaRaSar".search(r)])

```

This queries for the basic costs.

```
p=q=+(/*blah*/).shift()

```

Initializes 2 variables with the first item from the array result above, and remove that item. Must be cast to number first, otherwise it will be considered as string concatenation in the next part.

```
e.map(c=>p+=((q+1)*c)>>1);

```

Adds the costs of the non-power runes to the base power. Shifting is used instead of floor(blah)/2.

```
eval(/*blah*/;p)

```

Evaluate the last result. (Credit: Step Hen)

**Test Cases**

```
Lo Ful | 6
Um Ful | 9
On Ya | 7
Lo Zo Ven | 12
Pal Vi Bro | 35
Ee Ya Bro Ros | 31
On Ful Bro Ku | 31
Lo Zo Kath Ra | 20
On Oh Ew Sar | 35
Ee Oh Gor Dain | 43
Mon Zo Ir Neta | 68
Mon Des Ir Sar | 75

```

Edit 1: 212 \> 210 - Removed a pair of braces

Edit 2: 210 \> 207 - Thanks **Step Hen** for reminder on JS rules and some hint on using eval() function. Since AS3 forbids the use of eval() I haven't use that for long time

Edit 3: 207 \> 206 - Thanks **Shaggy** for the idea replacing indexOf() with search()

# Answer
> 3 votes
# Python 2, ~~320 318 314 311~~ 307 bytes

**Input Format -** List of Strings. Full program:

```
i=input()
t=[x.split()for x in"Lo Um On Ee Pal Mon|Ya Vi Oh Ful Des Zo|Ven Ew Kath Ir Bro Gor|Ku Ros Dain Neta Ra Sar".split('|')]
c=t[0].index(i[0])+1;r=c+1;s=c+r*(t[1].index(i[1])+2)/2
if len(i)>2:s+=r*(t[2].index(i[2])+4-(i[2]=='Bro'))/2
if len(i)>3:s+=r*(t[3].index(i[3])+1+(i[3]in'KuRaSar'))/2
print(s)

```

**Try it online!**

# Answer
> 3 votes
# Excel, 339 bytes

Inputs entered in `A1` through `D1`. Formula in any other cell.

```
=CHOOSE(MOD(CODE(A1),12),2,,,1,6,,3,5,4)+INT((CHOOSE(MOD(CODE(A1),12),2,,,1,6,,3,5,4)+1)*CHOOSE(MOD(CODE(B1),12),,3,,,2,7,4,6,,5)/2)+INT((CHOOSE(MOD(CODE(A1),12),2,,,1,6,,3,5,4)+1)*CHOOSE(MOD(CODE(C1),12),7,4,6,,,7,,,5,,9)/2)+INT((CHOOSE(MOD(CODE(A1),12),2,,,1,6,,3,5,4)+1)*CHOOSE(MOD(CODE(SUBSTITUTE(D1,"Ra","E")),11),4,3,6,,2,7,,,2,0)/2)

```

Alternatively, importing as CSV:

## Excel & CSV, 228 bytes

```
,,,
=CHOOSE(MOD(CODE(A1),12),2,,,1,6,,3,5,4)+1
=A2-1+INT(A2*CHOOSE(MOD(CODE(B1),12),,3,,,2,7,4,6,,5)/2)+INT(A2*CHOOSE(MOD(CODE(C1),12),7,4,6,,,7,,,5,,9)/2)+INT(A2*CHOOSE(MOD(CODE(SUBSTITUTE(D1,"Ra","E")),11),4,3,6,,2,7,,,2,0)/2)
```

Input entered in first row, `SPACE` for nulls. Result displayed in A3.

# Answer
> 3 votes
# Haskell, 159 156 148 133 130 127 bytes

```
k(p:y)=sum$floor<$>c p:map(\x->c x*(c p+1)/2)y
c s=read["3764529516342767"!!(foldl(\c n->c*94+fromEnum n-9)0s%7086%17)]
(%)=mod

```

Try it online!

# Answer
> 2 votes
# SCALA, 1106 chars, 1106 bytes

This is quite long, probably optimizable, but it was fun to do :)

**Input format** : space-separated runes in a string. If there is only 2 inputs (like "Lo Ful") my code completes it with `while(k.length<4)k:+=""` (so I can save **24 bytes** by changing the parameters, if I require it to be "A B C D").

```
def n(i:Int,p:String):Int={Math.floor(i*((""+p(0)).toInt+1)/2).toInt}
def m(s:String):Int={var k=s.split(' ')

```

**`while(k.length<4)k:+=""`**

```
k match{case Array(p,i,f,a)=>{p match{case "Lo"=>1+m(1+"/ "+i+" "+f+" "+a)
case "Um"=>2+m(2+"/ "+i+" "+f+" "+a)
case "On"=>3+m(3+"/ "+i+" "+f+" "+a)
case "Ee"=>4+m(4+"/ "+i+" "+f+" "+a)
case "Pal"=>5+m(5+"/ "+i+" "+f+" "+a)
case "Mon"=>6+m(6+"/ "+i+" "+f+" "+a)
case _ if p.contains("/")=>i match{case "Ya"=>n(2,p)+m(p+" / "+f+" "+a)
case "Vi"=>n(3,p)+m(p+" / "+f+" "+a)
case "Oh"=>n(4,p)+m(p+" / "+f+" "+a)
case "Ful"=>n(5,p)+m(p+" / "+f+" "+a)
case "Des"=>n(6,p)+m(p+" / "+f+" "+a)
case "Zo"=>n(7,p)+m(p+" / "+f+" "+a)
case _ if p.contains("/")=>f match{case "Ven"=>n(4,p)+m(p+" / "+"/ "+a)
case "Ew"=>n(5,p)+m(p+" / "+"/ "+a)
case "Kath"=>n(6,p)+m(p+" / "+"/ "+a)
case "Ir"=>n(7,p)+m(p+" / "+"/ "+a)
case "Bro"=>n(7,p)+m(p+" / "+"/ "+a)
case "Gor"=>n(9,p)+m(p+" / "+"/ "+a)
case _ if p.contains("/")=>a match{case "Ku"=>n(2,p)
case "Ros"=>n(2,p)
case "Dain"=>n(3,p)
case "Neta"=>n(4,p)
case "Ra"=>n(6,p)
case "Sar"=>n(7,p)
case _=>0}
case _=>0}
case _=>0}
case _=>0}}}}

```

Thanks for this superb challenge. Try it online!

# Answer
> 2 votes
# Shakespeare Programming Language, 4420 bytes

```
,.Ajax,.Ford,.Page,.Puck,.Romeo,.Act I:.Scene I:.[Enter Romeo and Page]Page:You big big big big big big cat.[Exit Romeo][Enter Ajax]Page:Open thy mind!Ajax:Open thy mind!Open thy mind!You is the sum of Romeo and the sum of a big big cat and a cat.Am I as big as you?If not,let us return to Scene V.Page:You is the sum of a big big cat and a cat.Let us return to Act V.Scene V:.Ajax:You is the sum of you and the sum of a big big big cat and a pig.Am I as big as you?If not,let us return to Scene X.Page:You big cat.Let us return to Act V.Scene X:.Ajax:You is the sum of you and the sum of a big cat and a cat.Am I as big as you?If not,let us return to Scene L.Page:You big big cat.Let us return to Act V.Scene L:.Ajax:You is the sum of you and the sum of a big big cat and a big cat.Am I as big as you?If not,let us return to Scene C.Page:You is the sum of a big cat and a cat.Let us return to Act V.Scene C:.Ajax:Am I as big as the sum of you and a big big big pig?Page:You is the sum of a big big cat and a big cat.If so,you is the sum of you and a cat.Ajax:Open thy mind!Act V:.Scene I:.[Exit Ajax][Enter Ford]Page:Open thy mind!Ford:Open thy mind!Open thy mind!You is the sum of Romeo and the sum of a big big big big cat and a pig.Am I as big as you?If not,let us return to Scene V.Page:You big big cat.Let us return to Act X.Scene V:.Ford:You is the sum of you and the sum of a big big big cat and a pig.Am I as big as you?If not,let us return to Scene X.Page:You is the sum of a big cat and a cat.Let us return to Act X.Scene X:.Ford:You is the sum of you and a big big cat.Am I as big as you?If not,let us return to Scene L.Page:You is the sum of a big big big cat and a pig.Let us return to Act X.Scene L:.Ford:Am I as big as the sum of you and a pig?If not,let us return to Scene C.Page:You big cat.Let us return to Act X.Scene C:.Ford:Am I as big as the sum of Romeo and a big big cat?Page:You is the sum of a big big cat and a cat.If so,you is the sum of you and a cat.Ford:Open thy mind!Act X:.Scene I:.[Exit Page][Enter Puck]Ford:You is the sum of the sum of Ajax and a pig and the quotient between the product of Ajax and I and a big cat.Puck:Open thy mind!Is you as big as a pig?If so,let us return to Act D.[Exit Puck][Enter Page]Ford:Open thy mind!Open thy mind!You is the sum of Romeo and the sum of a big big cat and a cat.Am I as big as you?If not,let us return to Scene V.Page:You is the sum of a big big cat and a cat.Let us return to Act L.Scene V:.Ford:Am I as big as the sum of you and a big big cat?If not,let us return to Scene X.Page:You is the sum of a big big big cat and a pig.Let us return to Act L.Scene X:.Ford:Open thy mind!Am I as big as the sum of Romeo and a big cat?If not,let us return to Scene L.Page:You is the sum of a big big big cat and a pig.Let us return to Act L.Scene L:.Ford:You is the sum of Romeo and the sum of a big big big cat and a pig.Am I as big as you?If not,let us return to Scene C.Page:You is the sum of a big big big cat and a cat.Let us return to Act L.Scene C:.Ford:Am I as big as the sum of you and a big big cat?If so,let us return to Scene D.Page:You big big cat.Let us return to Act L.Scene D:.Page:Open thy mind!You is the sum of a big big cat and a big cat.Act L:.Scene I:.[Exit Page][Enter Puck]Ford:You is the sum of you and the quotient between the product of Ajax and I and a big cat.Puck:Open thy mind!Is you as big as a pig?If so,let us return to Act D.[Exit Puck][Enter Page]Ford:You is the sum of Romeo and a big big cat.Am I as big as you?If not,let us return to Scene V.Page:You is the sum of a big cat and a cat.Let us return to Act C.Scene V:.Ford:You is the sum of you and the sum of a big big big cat and a pig.Am I as big as you?If not,let us return to Scene X.Page:You big cat.Let us return to Act C.Scene X:.Ford:Am I as big as the sum of you and the sum of a big cat and a cat?If not,let us return to Scene L.Page:You big big cat.Let us return to Act C.Scene L:.Ford:Am I as big as the sum of you and a big big big cat?If not,let us return to Scene C.Page:You is the sum of a big big big cat and a pig.Let us return to Act C.Scene C:.Page:Open thy mind!Is you as big as the sum of Romeo and a cat?You big cat.If so,you is the sum of you and a big big cat.Act C:.Scene I:.[Exit Page][Enter Puck]Ford:You is the sum of you and the quotient between the product of Ajax and I and a big cat.Act D:.Scene I:.Ford:Open thy heart![Exeunt]

```

Takes the input as an uppercase string.

Explanation coming soon... For now, **Fun fact:** `Microsoft` is a negative noun in SPL. All other accepted words appeared in the works of Shakespeare.

Try it online!

# Answer
> 1 votes
# Java (OpenJDK 8), 252 bytes

```
r->{int c[][]={{2,3,4,5,6,7},{4,5,6,7,7,9},{2,2,3,4,6,7}},l=r.length,p="LUOEPM".indexOf(r[0].charAt(0))+1,a=p,i=0;String[]s={"YVOFDZ","VEKIBG","KRDNXS"};for(;i<l-1;)a+=(p+1)*c[i][s[i++].indexOf((l>3?r[i].replace("Ra","X"):r[i]).charAt(0))]/2;return a;}

```

Try it online!

The runes are input as a `String[]` (array of `String`), in the first case form (first letter is an uppercase, rest is lowercase).

It's the standard "find the n-th letter" method, with the twist that both `Ros` and `Ra` exist in the 4th segment. I treated that with an inline and explicit replacement of `Ra` to `X`.

# Answer
> 1 votes
# Retina, ~~124~~ 123 bytes

```
Gor
9
[ZIBS]\w+
7
Mon|Des|Kath|Ra
6
..l|Ew
5
Ee|Oh|Ven|Neta
4
[OVD]\w+
3
[UYKR]\w+
2
Lo
1
\d
$*
(?<=^(1+) .*1)
$1
\G1
11
11

```

Try it online! Link includes test cases. Takes space-separated runes. Explanation: The initial stages simply convert each rune to a digit, which is then converted to unary. The numbers after the first are multiplied by one more than the first number, following which the first number is doubled. The final stage integer divides all the result by 2 and takes the sum.

# Answer
> 1 votes
# C, 222

**Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter**

```
i;b(r,s)char**r;{for(i=17;i--&&"& ; $ # 4 %        ; B * 6 $ 8          6 5 - >3  +  A@( .   6 5    "[s*17+i]-3-(*r[s]^r[s][1]););return~i?i/2+1:0;}main(n,r)int**r;{n=b(++r,0);printf("%d\n",n-(b(r,1)+b(r,2)+b(r,3))*~n/2);}

```

Try it online!

A more ungolfed version of my original answer:

```
#include<stdio.h>
char*a="& ; $ # 4 %      "
       "  ; B * 6 $ 8    "
       "      6 5 - >3  +"
       "  A@( .   6 5    ";
int b(char*r,int s){
  for(int i=0;i<17;i++)
    if(a[i+s]-3==(r[0]^r[1]))
      return i/2+1;
  return 0;
}
#define c(p,r,i)(p+1)*b(r[i+1],i*17)/2
int main(int n,char**r){
  int x=b(r[1],0);
  printf("%d\n",x+c(x,r,1)+c(x,r,2)+c(x,r,3));
}

```

You need to supply four command line arguments - so for the first test case you need to run `./a.out Lo Ful "" ""`

# Answer
> 1 votes
# Go, 205 bytes

```
func c(s []string)int{f,l:=strings.IndexByte,len(s)
p:=f("UOEPM",s[0][0])+3
r:=p-1+p*(f("VOFDZ",s[1][0])+3)/2
if l>2{r+=p*(f("war o",s[2][1])+5)/2}
if l>3{r+=p*(f("it Ra",s[3][len(s[3])-2])+3)/2}
return r}

```

It's a callable function, takes runes as a slice of strings, e.g. `[]string{"Um", "Ful"}`.

Try it on the Go Playground.

# Answer
> 0 votes
## Haskell, 623 bytes

Using ADTs instead of numerical voodoo.

**NOTE: Add 36 for `{-# LANGUAGE GADTs,ViewPatterns #-}`**

* Score is computed assuming that it is compiled/run with `-XGADTs -XViewPatterns`

```
data P=Lo|Um|On|Ee|Pal|Mon deriving(Enum,Read,Eq)
data E=Ya|Vi|Oh|Ful|Des|Zo deriving(Enum,Read,Eq)
data F=Ven|Ew|Kath|Ir|Bro|Gor deriving(Enum,Read,Eq)
data C=Ku|Ros|Dain|Neta|Ra|Sar deriving(Enum,Read,Eq)
data S where
  S::P->E->S
  Q::P->E->F->S
  R::P->E->F->C->S
k(a:b:x)=let{p=read a;e=read b}in case x of{[]->S p e;[c]->Q p e(read c);[c,d]->R p e(read c)(read d)}
c,d::Enum a=>a->Int
c=succ.fromEnum
d=(+2).fromEnum
e Bro=7
e x=(+2).d$x
f x|c x`elem`[1,5,6]=d x|2>1=c x
g p f x =(`div`2).(*f x).succ$c p
h(S x y)=c x+g x d y
h(Q x y z)=h(S x y)+g x e z
h(R x y z t)=h(Q x y z)+g x f t
main=print.h.k.words=<<getLine
```

Input: a single spell as a normal string e.g.

`Lo Ful`

`Um Ful`

Multilining can be done by replacing the last line with

```
main=interact$unlines.map(show.h.k.words).lines
```

But this would add bytes to the count

---
Tags: code-golf, game, conversion
---


title: Fastest Gun in the West

text:
# Question
Title: Fastest Gun in the West
You are the roughest, toughest, coolest cowboy west of the Mississippi. However, some weird guy on a wacky nerd website decided that it would be cool to plop you into random unfinished landscapes and fight. No matter, you'll still win. However, to help you win those grueling gunfights you'll write home about, it's helpful to know how many bullets the coward lurking in the landscape has.

How about you help this poor guy out. Given an ASCII landscape, find the gun inside it and tell him how many bullets are loaded into it. This is the gun:

```
  (X)
(X\ /X)
 (XVX)
  \X/

```

Each `X` in the above picture is a potential slot for a bullet. The slot will either contain a space or one of `0,O,o` (may not be consistent - the cowboy may have loaded different types of bullets in his gun).

There will always be exactly one gun, matching the above description, in the landscape. However, please note that the spaces around and inside the gun can contain anything.

# Input

You will be given a string containing printable ASCII (so not tabs) and newlines to separate lines. You may also take a list of strings, if you wish. Strings will all be padded with spaces, so they will all be the same length. The input will be at least 4 rows high and 7 columns wide.

There will always be exactly one gun in the landscape.

# Output

You will output how many bullets (`0, O, o`) there are in the gun, so your output will always between `0` and `6`.

# Test Cases

```
  (0)   ( )
(o\ /o( \ / )
 (oVo) ( V )
  \o/   \ /

0

----------------------------
////////////////////////////
////////////////////////////
/////////////(o)////////////
///////////(0\// )//////////
////////////( Vo)///////////
/////////////\ /////////////
////////////////////////////
----------------------------

3

()()()()()()()()()()()()()()()()\)/)()()()()()()()()()()()()
()()()()()()()()()()()()()()()()(V)()()()()()()()()()()()()(
()()()()()()()(\0/)()()()()()()()()()()()()()()()()()()()()(
()()()()()()()()()()()()()()()()()()()()()()()( )()()()()()(
()()()()()()(o)()()()()()()()(00)()()()()()(( \(/0)()()()()(
()()()()()()()()()()()()()()()()()()()()()()(( V )()()()()()
()()()()()()()()()()()()()()()()()()()()()()()\O/()()()()()(

2

------(0)---
||||(0\|/0)
-----(0V0)--
||||||\0/
-------_------
|||||||-|
------|-|
|||||||-|
------|-|

6

00ooOO(0)/\\/V

  ( )
( \\/ )
 ( V )
 \\ /

00OOoo()()()())))

0

  (\)     (0)
(0\\/0) ( \0/ )
 (0V0)   ( V )
 \\0/     \ /

1 (left gun is invalid because of the `\` in the bullet slot)

-00(0)00\0
-(O\0/o)\
- (OVo)o\0
-o \ /oo/

5

```

This is , so shortest answer in bytes wins.

# Answer
> 19 votes
# Snails, 71 bytes

Try it online.

```
A
\/a=\)2w\V={\\u\(}c=\/b={\\c\(2}u!{(nb|.|.n.)=^o=^O=^0^ }{nb|.|.n.}^

```

# Answer
> 6 votes
# Mathematica, 170 bytes

```
Catch@BlockMap[b="O"|"o"|"0";MatchQ[#,p=Characters@{"  (X)  ","(X\\ /X)"," (XVX) ","  \\X/  "}/." "->_/."X"->$;p/.$->b|"X"|" "]&&Throw@Count[Pick[#,p,$],b,2]&,#,{4,7},1]&

```

Takes an array of strings/chars. Returns the number of bullets.

# Answer
> 4 votes
# JavaScript, ~~215~~ ~~211~~ 209 bytes

Thanks to Shaggy for -4 bytes!

```
f=

i=>[...i].map((_,x)=>eval(String.raw`a=i.match(/(\n|^).{${x}}..\(${Z='([oO0 ])'}\).*\n.{${x}}\(${Z}\\.\/${Z}\).*\n.{${x}}.\(${Z}V${Z}\).*\n.{${x}}..\\${Z}\//);a&&alert(a.filter(i=>/^[oO0]$/.test(i)).length)`))

tests = [["  (0)   ( )\n(o\\ /o( \\ / )\n (oVo) ( V )\n  \\o/   \\ /",0],["----------------------------\n////////////////////////////\n////////////////////////////\n/////////////(o)////////////\n///////////(0\\// )//////////\n////////////( Vo)///////////\n/////////////\\ /////////////\n////////////////////////////\n----------------------------",3],["()()()()()()()()()()()()()()()()\\)/)()()()()()()()()()()()()\n()()()()()()()()()()()()()()()()(V)()()()()()()()()()()()()(\n()()()()()()()(\\0/)()()()()()()()()()()()()()()()()()()()()(\n()()()()()()()()()()()()()()()()()()()()()()()( )()()()()()(\n()()()()()()(o)()()()()()()()(00)()()()()()(( \\(/0)()()()()(\n()()()()()()()()()()()()()()()()()()()()()()(( V )()()()()()\n()()()()()()()()()()()()()()()()()()()()()()()\\O/()()()()()(",2],["------(0)---\n||||(0\\|/0)\n-----(0V0)--\n||||||\\0/\n-------_------\n|||||||-|\n------|-|\n|||||||-|\n------|-|",6],["00ooOO(0)/\\\\/V\n\n  ( )\n( \\\\/ )\n ( V )\n \\\\ /\n\n00OOoo()()()())))",0],["  (\\)     (0)\n(0\\\\/0) ( \\0/ )\n (0V0)   ( V )\n \\\\0/     \\ /",1]]

alert = x => i = x;

tests.forEach((t, index) => {
    i = 'Not Found'
    f(t[0]);
    document.getElementById('a').textContent += t[0] + '\n\n' + i + '\n\n';
    if (i != t[1]) {
        document.getElementById('a').textContent += 'Failed test ' + index + '! Expected '  + t[1] + '\n\n';
        document.getElementById('a').style = 'color: red'
    }
})
```

```
<pre id="a"></pre>
```

Basically, tries to match a gun `n` characters after a line break, for `n` from `0` to the length of the string.

# Answer
> 3 votes
# Python 2, ~~219~~ ~~224~~ 227 bytes

```
import re
f=lambda s:sum(sum(g>' 'for g in m.groups())for m in[re.match(r'.*@..\(X\)..@\(X\\./X\)@.\(XVX\).@..\\X/.*'.replace('X','([0Oo ])').replace('@',r'[^\n]*\n.{%d}'%i),'\n'+s,re.DOTALL)for i in range(0,s.find('\n'))]if m)

```

EDIT: Fixed a bug which cost me 5 bytes :(... found 3 bytes of extra `r''`s that weren't needed. And then Grrr!! Was not counting `\` chars in my code correctly, so added 6...

Takes a string with newlines; retuns the number of bullets found.

Basically, applies a regex that looks for the gun pattern with 0, 1, ... lineLength characters of pad at the beginning of the lines.

# Answer
> 3 votes
# C (gcc), 357 351 bytes

```
#define M(F,C)F(i){i=s[i]==C;}
b,i;char*s,c;M(L,'(')M(R,')')M(A,'/')M(D,'\\')M(V,'V')B(i){i=b=(c=s[i])==32?b:c==111?b+1:c==79?b+1:c==48?b+1:0;}(*t[])(int)={L,B,R,L,B,D,A,B,R,L,B,V,B,R,D,B,A};main(j,v,k,l)char**v;{for(s=v[1];s[l++]!=10;);for(;k=i,s[i++];){for(j=17;j--;)if(!(t[j])(k-=j==13?l-3:j==8?l-5:j==5?2:j==2?l-4:1))break;b=j<0?putchar(b+47):1;}}

```

Try it online! (golfed) (expanded) (357 golfed) (357 expanded)

I wondered how bad a solution would be in a language without built-in pattern matching. It came out a lot smaller than I feared.

Basically, this approach breaks the gun down into a series of individual parts it expects to see in specific locations relative to a specific index. If all parts are found where they are expected, it's a gun! The bullet test increments a global counter to keep track of how many bullets were in it, which we print when we have found the one and only gun in the landscape.

*Note 1: I padded the test cases with spaces to ensure consistent row widths.*

*Note 2: Add 10 bytes if you don't like the assign instead of return trick. For clarity, I used actual return statements in the expanded code.*

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