title: Twelve-coin problem

text:
# Question
Title: Twelve-coin problem
## Background

The twelve-coin problem is a classic balance puzzle commonly used in job interviews. The puzzle first appeared in 1945 and was posed to my father by my grandfather when he asked to marry my mother! **In the puzzle there are twelve coins, one of which is either heavier or lighter than the others (you don't know which). The problem is to use a balance scales three times to determine the unique coin.** In some variations, it is also necessary to identify whether the coin is heavier or lighter.

The task here involves solving the *general problem* involving *n* coins, using the fewest weighings possible in the worst case. It is not necessary to identify whether the coin is heavier or lighter, only which one it is. Furthermore, you do not have access to any additional coins outside the given set (which, curiously, makes a difference).

It turns out that k weighings are sufficient for up to (3^k-1)/2 coins (so 4 weighings in this variation can actually handle 13 coins). Furthermore (and surprisingly), it is possible (but not required here) to select the full set of weighings in advance, rather than have future weighings depend on past results. For descriptions of two possible solutions, see this paper and this Quora answer.

## Task

Write a function or program, taking an integer *n* as input via STDIN, command-line argument or function argument, which solves the problem for *n* coins using the fewest weighings possible in the worst case. The program should:

* Print weighings to STDOUT in the format `1,2,3-4,5,6` to indicate the lists of coins on each side of the scale. Any coins not being weighed should not be mentioned. The coins are implicitly numbered from 1 to *n* and need not be printed in numeric order (so `2,1-3,4` is the same as to `1,2-3,4`).
* After each weighing the program should wait on an input via STDIN, which should be `<`, `=` or `>`, indicating whether the left side of the scale is lighter, the same, or heavier than the right side.
* After the last weighing result, the program should print or return the number of the unique coin.
* The program need not handle inconsistent result inputs from the user.
* The program need not handle *n* less than 3.

## Example outputs

```
>> 3
1-2
>> =
1-3
>> <
3

# using Quora algorithm
>> 13
1,2,3,4-5,6,7,8
>> <
1,2,5-3,4,6
>> >
3-4
>> <
3

# using paper algorithm
>> 13
1,2,3,4-5,6,7,8
>> <
2,6,7,9-3,8,10,11
>> >
6,8,10,12-4,5,7,11
>> =
3

```

## Scoring

Shortest code wins. Standard rules apply.

# Answer
# Python 3: 497 bytes

```
I=lambda a,b:input(",".join(a)+"-"+",".join(b)+"\n>> ")
def A(a,b):
 l,L=len(a),len(b)
 if l+L==1:return(a or b)[0]
 m=(2*l+1-L)//3;M=m+L-l;x,y,X,Y=a[:m],a[m:2*m],b[:M],b[M:2*M];r=I(x+X,y+Y);return A(a[2*m:],b[2*M:])if r=="="else A(x,Y)if r=="<"else A(y,X)
def B(a,n=[]):
 if len(a)==1:return a[0]
 m=len(n);l=(len(a)+1+m)//3;x,y,z=a[:l],a[l:2*l-m],a[2*l-m:];r=I(x,y+n);return B(z,a[:1])if r=="="else A(x+z[:1-m],y)if r=="<"else A(y+z[:1-m],x)
print(B(list(map(str,range(1,int(input("N= "))+1)))))

```

I suspect this could be shrunk down a bit more, but I don't see any obvious places any more (after about 5 different versions of each function).

The code implements a slightly modified version of the algorithm from this page using three functions. The `I` function does the IO (printing the options and returning the user's response). The `A` and `B` functions implement the main of the algorithm. `A` takes two lists which differ in size by exactly one element (though either list can be the larger one): one coin in `a` may be lighter than normal, or one coin in `b` may be heavier. `B` does double duty. It takes one list of coins `a` and optionally a second list with a single coin that is known to be the correct weight. The length-rounding behavior needs to be different between the two cases, which caused no end of headaches.

The two algorithm functions can find the unusually weighted coin in `k` weighings given inputs of up to the following sizes:

* `A`: `3^k` total coins, divided up into two list of `(3^k-1)/2` and `(3^k+1)/2`.
* `B`: `(3^k + 1)/2` coins if a known-good coin is supplied, `(3^k - 1)/2` otherwise.

The question posed here specifies that we don't have any known-good coins at the start, so we can solve find the bad coin in a set of `(3^k - 1)/2` in `k` weighings.

Here's a test function I wrote to make sure my code was not requesting bogus weighings or using more than the number of weighings it was supposed to:

```
def test(n):
    global I
    orig_I = I
    try:
        for x in range(3,n+1):
            max_count = 0
            for y in range(x*2):
                count = 0
                def I(a, b):
                    assert len(a) == len(b), "{} not the same length as {}".format(a,b)
                    nonlocal count
                    count += 1
                    if y//2 in a: return "<"if y%2 else ">"
                    if y//2 in b: return ">"if y%2 else "<"
                    return "="
                assert B(list(range(x)))==y//2, "{} {} not found in size {}".format(['heavy','light'][y%2], y//2+1, x)
                if count > max_count:
                    max_count = count
            print(x, max_count)
    finally:
        I = orig_I

```

This prints out the worst-case number of weighings for a given set after testing with each combination of coin and bad weight (heavy or light).

Here's the test output for sets of up to 125:

```
>>> test(150)
3 2
4 2
5 3
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 4
15 4
16 4
17 4
18 4
19 4
20 4
21 4
22 4
23 4
24 4
25 4
26 4
27 4
28 4
29 4
30 4
31 4
32 4
33 4
34 4
35 4
36 4
37 4
38 4
39 4
40 4
41 5
42 5
43 5
44 5
45 5
46 5
47 5
48 5
49 5
50 5
51 5
52 5
53 5
54 5
55 5
56 5
57 5
58 5
59 5
60 5
61 5
62 5
63 5
64 5
65 5
66 5
67 5
68 5
69 5
70 5
71 5
72 5
73 5
74 5
75 5
76 5
77 5
78 5
79 5
80 5
81 5
82 5
83 5
84 5
85 5
86 5
87 5
88 5
89 5
90 5
91 5
92 5
93 5
94 5
95 5
96 5
97 5
98 5
99 5
100 5
101 5
102 5
103 5
104 5
105 5
106 5
107 5
108 5
109 5
110 5
111 5
112 5
113 5
114 5
115 5
116 5
117 5
118 5
119 5
120 5
121 5
122 6
123 6
124 6
125 6

```

The breakpoints are exactly where you'd expect, between `(3^k - 1)/2` and `(3^k + 1)/2`.
> 2 votes

---
Tags: code-golf, combinatorics
---


title: Dead code elimination

text:
# Question
Title: Dead code elimination
Dead code sits there doing nothing, staring at us knowing it will never be executed... but today we can take revenge.

## Specification

The input will be a multiline string.

Each line may either be an **assignment** or an **expression** .

### Assignment

An assignment is of the form `<name> = number` where name is a sequence of letters, underscores and numbers, but not starting with a number.

Variables may be assigned any number of times.

### Expression

An expression is of the form `<var_name OR number> <operation> <var_name OR number> ...`

An expression may be any combination of:

* Variables already defined
* Basic arithmetic operators `+-*/`
* Numbers (integers)

## Expected output

You should output the string with redundant **assignments**, **assignments** that are never used by any of the **expressions** following it, removed. Please note that **assignments** can also be made redundant if an additional **assignment** to the same variable is performed before an **expression** using the variable is executed.

## Test cases

**in**

```
a = 10
a * 3

```

**out**

```
a = 10
a * 3

```

---

**in**

```
foo = 8
2 - 1
a = 18

```

**out**

```
2 - 1

```

---

**in**

```
a = 10
a = 8
b = 4
ab = 72
b / 6
b + 1

```

**out**

```
b = 4
b / 6
b + 1

```

---

**in**

```
a = 1
a = 2
a + 1

```

**out**

```
a = 2
a + 1

```

---

**in**

```
FooBar1 = 0
Fuz__ = 8
Fuz__ / 1

```

**out**

```
Fuz__ = 8
Fuz__ / 1

```

---

**in**

```
a = 1
a + 1
a = 2
a + 1

```

**out**

```
a = 1
a + 1
a = 2
a + 1

```

---

**in**

```
a = 1
1 / 5 * 8 + 4

```

**out**

```
1 / 5 * 8 + 4

```

---

**in**

```
a = 1
a + 1
a = 1
a + 1

```

**out**

```
a = 1
a + 1
a = 1
a + 1

```

---

**in**

```
a = 7
5 / a

```

**out**

```
a = 7
5 / a

```

# Answer
## PHP - 197 bytes

The function works by analysing each line, in the reverse order and one after the other, and maintaining an array of the used variables.

* If there is an equal character `=` in the line, it's an assignment.
    + It the variable is used, the assignment is useful, and the line is printed, but the variable isn't considered used any more.
    + Otherwise, do nothing.
* Otherwise, the line is an expression. We split the line after each space, and add each symbol to the list of used variables. Numbers (`1`, `2`, …) and operators (`+`, `-`, …) will be added too, but since they aren't valid variables names, it's not a problem. The line is then of course printed.

```
function($c){$u=[];foreach(array_reverse(split('
',$c))as$l){if($p=strpos($l,'=')){if(!isset($u[$x=substr($l,0,$p-1)]))continue;
unset($u[$x]);}else$u+=array_flip(split(' ',$l));$f="
$l$f";}echo$f;}

```

Here is the ungolfed version:

```
function removeDeadCode($code)
{
    $usedVariables = [];
    $finalCode = '';

    foreach (array_reverse(explode("\n", $code)) as $line)
    {
        if ($equalPosition = strpos($line, '='))
        {
            $variable = substr($line, 0, $equalPosition - 1);
            if (isset($usedVariables[$variable]))
            {
                $finalCode = "\n" . $line . $finalCode;
                unset($usedVariables[$variable]);
            }
        }
        else
        {
            $usedVariables += array_flip(explode(' ', $line));
            $finalCode = "\n" . $line . $finalCode;
        }
    }

    echo $finalCode;
}

```
> 9 votes

# Answer
# Retina, 45 bytes

```
m`^(\w+) =.*\n(?=((?!\b\1\b)[^!])*(^\1 =|\Z))
<empty>

```

For counting purposes, each line goes in a separate file (where `<empty>` is an empty file) and `\n` should be replaced with an actual line feed (0x0A).

This assumes that the string will always end with a line feed.

As this regex doesn't use any .NET-specific features, you can test it on regex101.

The idea is fairly simple: remove all assignments from which we can find (searching forward) another assignment to the same variable or the end of the string without passing another use of the variable.
> 7 votes

# Answer
# Pyth, 40 bytes

```
eMf|!}K\=eT&Jf}+dhceTK++dYdPT!}KeJ_.__.z

```

Seems kinda long. Maybe I can save one or two bytes tomorrow.

Try it online: Demonstration or Test Suite

### Explanation:

`_.__.z` gives all postfixes of the input lines in reversed order. E.g. the input `FooBar1 = 0; Fuz__ = 8; Fuz__ / 1` gives the list:

```
[['Fuz__ / 1', 'Fuz__ = 8', 'FooBar1 = 0'],
 ['Fuz__ / 1', 'Fuz__ = 8']
 ['Fuz__ / 1']]

```

Then I filter for list elements `T`, in which `=` doesn't is in the last element of `T` (expression) or (assignment) the last element in `T`, which contains the variable name, is an expression. Afterwards print the last element of each of the remaining elements on a separate line.

```
eMf|!}K\=eT&Jf}+dhceTK++dYdPT!}KeJ_.__.z
                                      .z  all input lines
                                     _    reverse order
                                   ._     all prefixes
                                  _       reverse order
  f                                       filter for elements T, which satisfy:
      K\=                                   K = '='
    !}K  eT                                 '=' is not in T[-1]
   |                                        or
             f             PT                 filter for elements Y in T[:-1],
                                              which satisfy:
                 hceTK                          extract variable name of T[-1]
                                                with an additional space at the end
               +d                               and at the beginning
              }       ++dYd                     ^ in space+Y+space
            J                                 assign these list to J
           &                                  J not empty and
                             !KeJ             '=' is not in J[-1]
eM                                        take the last element of each and print

```
> 6 votes

# Answer
# Python 2, ~~270~~ 267 bytes

```
import sys,re
d={}
s=list(enumerate(sys.stdin))
for n,l in s:
 try:v,_=l.split('=');v=v.strip();d[v]=d.get(v,[])+[[0,n]]
 except:
  for v in re.findall('[a-zA-Z_]\w*',l):d[v][-1][0]+=1
print''.join(l for n,l in s if n not in[n for x in d.values()for c,n in x if c==0])

```

Indentation is: 1. Space 2. Tab

Saved 3 bytes thanks to @Kamehameha!
> 4 votes

# Answer
# CJam, 49 bytes

```
LqN/W%{_'=#_){(<:V1$\e=_{\Va-\}&}{;S/+1}?},\;W%N*

```

Try it online

The approach here is that a list of unassigned variables is maintained while processing the input lines back to front:

* If the line is an expression, all variables in the expression are added to the list. Actually, in the implementation, all tokens are added to the list, since it saves code and having numbers and operators in the list does not do any harm.
* If the line is an assignment, it tests if the assigned variable name is in the list. If it is, the assignment is accepted, and the variable name removed from the list. Otherwise, the assignment is skipped.

Explanation :

```
L     Start with empty list.
qN/   Get input and split at newlines.
W%    Reverse to process lines back to front.
{     Start of filter block.
  _     Copy line.
  '=#   Find equal sign.
  _     Copy position of equal sign, will use original later to extract
        variable name from assignment.
  )     Increment to produce truthy/falsy value (-1 from find means not found).
  {     Start if-block that processes assignments.
    (<    Slice off everything but variable name.
    :V    Save in variable V for later re-use.
    1$\   Place copy of unassigned variable list and new variable name at
          top of stack.
    e=    Count occurrences. This tells us if variable name was in list.
    _     Copy the condition value because it will also be used as the
          overall filter result.
    {     Start of block that removes variable name from list.
      \V    Bring list to top, and push variable name.
      a-    Remove the variable name from list.
      \     Swap to get variable list to bottom of stack for next iteration,
            and filter result to top.
    }&    End of conditional block to remove variable name.
  }     End of if-block for assignment.
  {     Start of else-block for expression.
    ;     Pop result of find operation.
    S/    Split expression at spaces.
    +     Concatenate the new variables with the existing ones in the list.
    1     Filter result, expressions are always accepted.
  }?    End of if for assignment vs. expression.
},    End of filter.
\;    Get rid of variable list at bottom of stack.
W%    Reverse order of filtered result, since we worked back to front.
N*    Join with newlines.

```
> 4 votes

# Answer
# JavaScript (ES6) 164 ~~177~~

Using template strings, all newlines are signifcant and counted.

Test running the snippet in **FireFox** (required for ES6 compatibility including arrow functions)

```
f=s=>(k=>{s=s.split`
`,s.map((t,n)=>(r=t.match(/\w+/g)).map(v=>k[v]=f,~t.search`=`?k[s[k[v=r[0]]]=r[0]=0,v]=n:0))
for(v in k)s[k[v]]=0})([])||s.filter(r=>r).join`
`

ungolfed=s=>
{
  k={} // list line defining variables, by name, until used
  s=s.split`\n`
  s.forEach((t,n)=>
  {
    r=t.match(/\w+/g); // list variables in the line, operators are lost
    if (t.search`=` >= 0) // if it's an assignment
    {
      v=r[0] // new variable
      s[k[v]]=r[0]=0 // kill previous definition if not used
      k[v]=n
    }
    r.forEach(v=>k[v]='') // for each used variable, forget its definition line
  })
  for(v in k)s[k[v]]=0; // kill all remaining unused definitions
  return s.filter(r=>r).join`\n`
}

// TEST
out=x=>O.innerHTML+=x+'\n';

;[['a = 10\na * 3', 'a = 10\na * 3']
 ,['foo = 8\n2 - 1\na = 18','2 - 1']
 ,['a = 10\na = 8\nb = 4\nab = 72\nb / 6\nb + 1','b = 4\nb / 6\nb + 1']
 ,['a = 1\na = 2\na + 1','a = 2\na + 1']
 ,['FooBar1 = 0\nFuz__ = 8\nFuz__ / 1','Fuz__ = 8\nFuz__ / 1']
 ,['a = 1\na + 1\na = 2\na + 1','a = 1\na + 1\na = 2\na + 1']
 ,['a = 1\na + a\na = 2', 'a = 1\na + a']
 ,['a = 1\n1 / 5 * 8 + 4', '1 / 5 * 8 + 4']
 ,['a = 1\na + a\na = 2', 'a = 1\na + a']
 ,['a = 1\na + 1\na = 1\na + 1', 'a = 1\na + 1\na = 1\na + 1']
 ,['a = 7\n5 / a', 'a = 7\n5 / a']
]
.forEach(([i,k])=>(r=f(i),
  out('Test '+(r==k?'OK':'Fail')+'\nInput:  '+i.replace(/\n/g,',')
      +'\nResult: '+r.replace(/\n/g,',')
      +'\nCheck:  '+k.replace(/\n/g,',')+'\n')
));
```

```
Note: newlines trasformed to commas to save space in output
<pre id=O></pre>
```
> 2 votes

# Answer
## R 144

```
Q=R=c()
for(L in rev(scan(,"",,,"\n"))){W=strsplit(L," ")[[1]]
if("="%in%W)if(W[1]%in%R)R=R[R!=W[1]]else next else R=c(R,W)
Q=c(L,Q)}write(Q,"")

```

where

* `L` is a line from the input (starting from the last one)
* `W` are the symbols (variables, operators, numbers) in a line
* `R` is a vector of symbols that will be printed. It includes variables whose assignment is needed.
* `Q` is the vector of lines in the output
> 2 votes

# Answer
# JavaScript ES6, ~~79~~ ~~75~~ 118 bytes

```
s=>s.split`
`.filter((l,i,a)=>(q=l.split`=`)[1]?!~(a.slice(i+1)+0).search(q[0]+'=')&&~s.search(q[0]+'[^=]'):1).join`
`

```

Tell me if this doesn't work for a case. Any ideas for golfing are welcome.

---

## Explanation

```
s=>          // Function with argument "s"
  s.split`   // Splits each line
  `
  .filter(   // Filters through each line,
    (item,index,array)=>
      (q=l.split`=`)[1]? // If there is something after the equal sign
        !~ // XOR (~) will  essentially make -1, 0. NOT (!) will make 0, 1, vice-versa
         (a.slice(i+1)+0) // Gets following lines
         .search`^${z=q[0]}=` // Checks if following lines have the same variable name and then =
        && // AND...
         ~s.search(z+'[^=]') // Check if there is an expression with the variable
        :1) // If there is no equal sign, return 1 (true)
  .join` // Join everything back, seperated by newlines
  `

```

---

Tested on Safari Nightly. Firefox friendly version:

```
s=>s.split`
`.filter((l,i,a)=>(q=l.split`=`)[1]?!~(a.slice(i+1)+0).search(`^${z=q[0]}=`)&&~s.search(z+'[^=]'):1).join`
`

```

You can drop in in babeljs to get an ES5 version.
> 1 votes

# Answer
# Haskell, 187 bytes

Use `d`.

```
import Data.List
f=filter
(!)=map
b((v,e,w):t)=e||or((\(_,p,_)->p)!take 1(f(\(x,_,y)->v==x||v`elem`y)t))
d=unlines.(\l->snd!f fst(zip(b!tails(((\(v:o:w)->(v,o/="=",w)).words)!l))l)).lines

```
> 1 votes

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


# Question
Title: An optimization version of the Hadamard problem
First, some definitions.

A Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integer k.

A circulant matrix is a special kind of matrix where each row vector is rotated one element to the right relative to the preceding row vector. That is the matrix is defined by its first row.

It is known that, except for 4 by 4 matrices, there are **no circulant Hadamard matrices**.

A matrix with m rows and n \>= m columns is **partial circulant**, if it is the first m rows of some circulant matrix.

**The task**

For each even integer n starting at 2, output the size of the largest partial circulant matrix with +-1 entries and n columns that has the property that all its rows are mutually orthogonal.

**Score**

Your score is the highest `n` such that for all `k <= n`, no one else has posted a higher correct answer than you. Clearly if you have all optimum answers then you will get the score for the highest `n` you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.

**Languages and libraries**

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

**Leading entries**

* **64** by Mitch Schwartz in **Python**

# Answer
# Python 2

Table up to `n = 64`, verified optimal with brute force up to `n = 32`:

```
 4  4 0001
 8  4 00010001
12  6 000001010011
16  8 0000010011101011
20 10 00010001011110011010
24 12 000101001000111110110111
28 14 0001011000010011101011111011
32 14 00001101000111011101101011110010
36 18 001000101001000111110011010110111000
40 20 0010101110001101101111110100011100100100
44 18 00010000011100100011110110110101011101101111
48 24 001011011001010111111001110000100110101000000110
52 26 0011010111000100111011011111001010001110100001001000
56 28 00100111111101010110001100001101100000001010100111001011
60 30 000001101101100011100101011101111110010010111100011010100010
64 32 0001100011110101111111010010011011100111000010101000001011011001

```

where `0` represents `-1`. If `n` is not divisible by 4 then `m = 1` is optimal. Generated using this code (or small variations of it) but with more trials for higher `n`:

```
from random import *

seed(10)

trials=10000

def calcm(x,n):
    m=1
    y=x
    while 1:
        y=((y&1)<<(n-1))|(y>>1)
        if bin(x^y).count('1')!=n/2:
            return m
        m+=1

def hillclimb(x,n,ns):
    bestm=calcm(x,n)

    while 1:
        cands=[]

        for pos in ns:
            xx=x^(1<<pos)
            m=calcm(xx,n)

            if m>bestm:
                bestm=m
                cands=[xx]
            elif cands and m==bestm:
                cands+=[xx]

        if not cands:
            break

        x=choice(cands)

    return x,bestm

def approx(n):
    if n<10: return brute(n)

    bestm=1
    bestx=0

    for trial in xrange(1,trials+1):
        if not trial&16383:
            print bestm,bin((1<<n)|bestx)[3:]

        if not trial&1:
            x=randint(0,(1<<(n/2-2))-1)
            x=(x<<(n/2)) | (((1<<(n/2))-1)^x)
            ns=range(n/2-2)

            if not trial&7:
                adj=randint(1,5)
                x^=((1<<adj)-1)<<randint(0,n/2-adj)
        else:
            x=randint(0,(1<<(n-2))-1)
            ns=range(n-2)

        x,m=hillclimb(x,n,ns)

        if m>bestm:
            bestm=m
            bestx=x

    return bestm,bestx

def brute(n):
    bestm=1
    bestx=0

    for x in xrange(1<<(n-2)):
        m=calcm(x,n)
        if m>bestm:
            bestm=m
            bestx=x

    return bestm,bestx

for n in xrange(4,101,4):
    m,x=approx(n)
    print n,m,bin((1<<n)|x)[3:]

```

The approach is simple randomised search with hill climbing, taking advantage of a pattern noticed for small `n`. The pattern is that for optimal `m`, the second half of the first row often has small edit distance from the (bitwise) negation of the first half. The results for the above code are good for small `n` but start deteriorating not long after brute force becomes unfeasible; I would be happy to see a better approach.

Some observations:

* When `n` is odd, `m = 1` is optimal because an odd number of ones and negative ones can't add up to zero. (Orthogonal means dot product is zero.)
* When `n = 4k + 2`, `m = 1` is optimal because in order for `m >= 2` we need to have exactly `n/2` sign reversals among `{(a1,a2), (a2,a3), ... (a{n-1},an), (an,a1)}`, and an odd number of sign reversals would imply `a1 = -a1`.
* The dot product of two rows `i` and `j` in a circulant matrix is determined by `abs(i-j)`. For example, if `row1 . row2 = 0` then `row4 . row5 = 0`. This is because the pairs of elements for the dot product are the same, just rotated.
* Consequently, for checking mutual orthogonality, we only need to check successive rows against the first row.
* If we represent a row as a binary string with `0` in place of `-1`, we can check orthogonality of two rows by taking bitwise xor and comparing the popcount with `n/2`.
* We can fix the first two elements of the first row arbitrarily, because (1) Negating a matrix does not affect whether the dot products equal zero, and (2) We know that there must be at least two adjacent elements with same sign and two adjacent elements with differing sign, so we can rotate to place the desired pair at the beginning.
* A solution `(n0, m0)` will automatically give solutions `(k * n0, m0)` for arbitrary `k > 1`, by (repeatedly) concatenating the first row to itself. A consequence is that we can easily obtain `m = 4` for any `n` divisible by 4.

It is natural to conjecture that `n/2` is a tight upper bound for `m` when `n > 4`, but I don't know how that would be proven.
> 7 votes

---
Tags: math, code-challenge, optimization, coding-theory
---


# Question
Title: Shortest parser for a left-recursive grammar
Write the shortest parser for the grammar:

```
M -> M + n | n

```
* Output must be some representation of a structured value representing the concrete syntax tree produced by the input `n+n+n`.
* The code to produce the textual output from the structured value is not necessary.
* The code to read/validate input is not necessary.
* Solution is anything that can somehow be called; a function, an object, doesn't matter.
* How your solution receives input (currying character-by-character, whole-string, some kind of input reader) does not matter.

For example a bottom-up parser (Javascript, 284 characters):

```
function M(d){function c(a){throw"unexpected "+a;}function f(a){if("+"==a)return b.push(a),e;if(null==a)return b;c(a)}function e(a){if("n"==a)return b.push(a),b=[b],g;c(a)}function g(a){if("+"==a)return b.push(a),e;if(null==a)return b;c(a)}var b=[];if("n"==d)return b.push(d),f;c(d)};

```

When called:

```
 M('n')('+')('n')('+')('n')(null)

```

will return an array that in JSON-notation looks like this:

```
[["n", "+", "n"], "+", "n"]

```

---

Edit for the uninitiated in parsing: This is one of those questions where making a program produce the correct output is easy but the form of the program is essential for up-boats.

```
M -> M + n | n

```

Means that `M` consists of a previous `M`, a plus sign and a literal `"n"`. Or good `M` is a single `"n"` literal character.

There are several way of approaching this challenge, I'll describe my own solution, which is called bottom-up parsing. Character by character:

```
 Stack               Incoming Character         Action on stack
                     n
 n                   +                          reduce "n" to M
 M+                  n
 M+n                 +                          reduce "M + n" to M
 M+                  n
 M+n                 EOF                        reduce "M + n" to M
 M

```

The twist in this question is that the simplest form of parsers called "recursive-descent" parsers won't work because the grammar is left-recursive and that throws a recursive-descent parser into an infinite loop.

# Answer
## Ruby, 51 bytes

```
f=->s{s.split(/(\+)(?=n$)/).map{|t|t['+n']?f[t]:t}}

```

This seems weirdly cumbersome. It can be called like `f['n+n+n']`.
> 2 votes

# Answer
# CJam, 13 15

If I have understood what did you mean by "the code to validate input is not necessary" correctly:

```
{'+/{[\"+"@]}*}

```

### Example

```
{'+/{[\"+"@]}*}:T;
"n+n+n" T`
N
"n+n+n+n" T`

```

Output:

```
[["n" "+" "n"] "+" "n"]
[[["n" "+" "n"] "+" "n"] "+" "n"]

```

Or if I have to check the grammar:

# CJam, 24

```
{'+/_"n"a-L@{[\"+"@]}*?}

```
> 2 votes

# Answer
# Augeas, 42

```
module A=let rec l=[key"n".(del"+""+".l)?]

```

Example usage, by adding:

```
test l get "n+n+n" = ?

```

and launching:

```
$ augparse a.aug
Test result: a.aug:2.0-.22:
{ "n"
  { "n"
    { "n" }
  }
}

```

Due to the bidirectional nature of Augeas lenses, the provided code also manages the reverse transformation, e.g. by using:

```
test l put "n" after clear "n/n/n" = ?

```

then launch augparse:

```
$ augparse a.aug
Test result: a.aug:2.0-.38:
"n+n+n"

```
> 2 votes

# Answer
# Pyth, ~~20~~ 13 bytes

```
L.U[b\+Z)cz\+

```

Took me forever to shorten it, but I did! I changed pretty much the entire algorithm. Defines a function `y` that takes one string argument.

Live demo with 3-byte test harness and test cases.

## Original

```
?tJu?qH\n+GH,GHzkJ]J

```

Live demo and test cases.
> 0 votes

---
Tags: code-golf, parsing
---


title: Output ISO8601 date

text:
# Question
Title: Output ISO8601 date
# The Task

Given the positive value of unix timestamp output any of two valid ISO 8601 time formats:

* `YYYY-MM-DDTHH:mm:SS` or, alternatively,
* `YYYY-MM-DD HH:mm:SS`

You may ignore any leap seconds, if you wish, as well as the timezone part of the date.

Also, ignore the year 2038 problem.

# Rules

* You must not use any built-in date functions,
* You may not use any string formatting functions (like `printf`), however sorting, reversing, changing case etc. is allowed,
* Your program may not contain any numbers (ie. characters `0`, `1`, `2`, ... `9`) and letters which mean hexadecimal number (`A`, `a`, `B`, `b`, ... `f`), if used in context of hexadecimal number,
* The only exception are line numbers (or labels and `goto` statements), if your language requires them,
* You may use any function or method that returns a number, but **only once** (each) in your program:
> For example, you can use something like `zero = length('');` to have number `0`, but then you can't use `one = length('a');` because you would use the `length()` function twice, so you can consider using `one = cos(zero);`
* The same applies to built-in constants or variables
> You may use built-in constants like `__LINE__` etc., but only once for each value (for example, `__FILE__` is "really" constant in a file, so you can use it only once in a file, but `__LINE__` varies for each line, so you can use it once per line).
* If a function or a constant is used in a loop that has a chance to be executed more than once, it is considered to be used more than once and this is forbidden,
* All loopholes are forbidden (especially, loading the result from another site or executing an external program to do the calculations).
* Any errors, compiler warnings are allowed, however the ISO 8601 string must be valid (no error messages within the output string)

# Testing

Your code must return a valid value which will be tested with the site http://www.unixtimestamp.com/.

# Notes

This question is a popularity contest, so the highest scored answer wins (not earlier than at Midnight on Monday, September 7th UTC). The main idea is to show your skills when limited to not use numbers. When voting, please consider how numbers are represented by the author and what tricks they use. In my opinion such constructions like

```
 eighty_six_thousand_four_hundred = one;
 eighty_six_thousand_four_hundred++;
 eighty_six_thousand_four_hundred++;
 //... 86399 times

```

or

```
// 86399 empty lines
...
$eighty_six_thousand_four_hundred = __LINE__;

```

should be avoided.

I also kindly ask that you provide an online version of your program, so everyone can test it (the program must not be limited to your environment).

# Answer
> 5 votes
# Inform 7

```
"ISO Eight Six Zero One" by "Dannii Willis"

There is a room.
Sixty is a number variable.
Hundred is a number variable.
Days per year is a number variable.
Days per leap year is a number variable.
Leap year period is a number variable.
Days per leap year period is a number variable.
Epoch is a number variable.
Seconds per day is a number variable.
Months is a list of numbers variable.

To initialise number variables:
    let thirty be ten times three;
    let thirty one be thirty plus one;
    now sixty is five times twelve;
    now hundred is ten times ten;
    now days per year is sixty times six plus five;
    now days per leap year is days per year plus one;
    now leap year period is hundred times four;
    now days per leap year period is leap year period times days per year plus hundred minus three;
    now epoch is leap year period times five minus thirty;
    now seconds per day is sixty times sixty times twelve times two;
    truncate months to zero entries;
    let X be zero; add X to months;
    increase X by thirty one; add X to months;
    increase X by thirty minus two; add X to months;
    increase X by thirty one; add X to months;
    increase X by thirty; add X to months;
    increase X by thirty one; add X to months;
    increase X by thirty; add X to months;
    increase X by thirty one; add X to months;
    increase X by thirty one; add X to months;
    increase X by thirty; add X to months;
    increase X by thirty one; add X to months;
    increase X by thirty; add X to months;

To decide whether (year - a number) is a leap year:
    if the remainder after dividing year by four is zero:
        if the remainder after dividing year by hundred is not zero:
            yes;
        otherwise if the remainder after dividing year by leap year period is zero:
            yes;
    no;

To say zero padded (X - a number):
    if X is less than ten:
        say zero;
    say X;

[ This general algorithim is taken from the PHP source code ]
To say (X - a number) as an ISO Eight Six Zero One date:
    initialise number variables;
    [ Split the timestamp into days and seconds ]
    let days be X divided by seconds per day;
    let seconds be the remainder after dividing X by seconds per day;
    [ Calculate the date ]
    let year be epoch;
    let month be twelve;
    let day be zero;
    increase days by one;
    [ Year ]
    if days is at least days per leap year period:
        let leap year period count be days divided by days per leap year period;
        increase year by leap year period times leap year period count;
        decrease days by days per leap year period times leap year period count;
    while days is at least days per leap year:
        increase year by one;
        if year is a leap year:
            decrease days by days per leap year;
        otherwise:
            decrease days by days per year;
    [ Month ]
    if year is a leap year:
        decrease entry one of months by one;
        decrease entry two of months by one;
    while month is greater than one:
        if days is greater than entry month of months:
            break;
        decrease month by one;
    [ Day ]
    now day is days minus entry month of months;
    [ Calculate the time ]
    let hours be seconds divided by (sixty times sixty);
    let minutes be the remainder after dividing (seconds divided by sixty) by sixty;
    let secs be the remainder after dividing seconds by sixty;
    say "[year]-[zero padded month]-[zero padded day] [zero padded hours]:[zero padded minutes]:[zero padded secs]";

```

Inform 7 allows the numbers one to twelve to be written in words - from these we calculate the other numbers which are needed. With that it was just a matter of transferring over the simplest algorithm I could find, which happened to be PHP's. I haven't accounted for negative timestamps. Maybe another day.

Here are some tests:

```
When play begins:
    say "0: [0 as an ISO Eight Six Zero One date][line break]";
    say "1000000000: [1000000000 as an ISO Eight Six Zero One date][line break]";
    say "1234567890: [1234567890 as an ISO Eight Six Zero One date][line break]";

```

Which produce the following correct output:

```
0: 1970-01-01 00:00:00
1000000000: 2001-09-09 01:46:40
1234567890: 2009-02-13 23:31:30

```

# Answer
> 3 votes
# JavaScript (ES6)

So I'm not 100% sure I'm adhering to the rules totally, so please let me know if not and I'll remove.

```
var T = +prompt('Enter a timestamp'),
[one, two, three, four, five, six, seven, eight, nine, zero] = btoa('\xd7\x6d\xf8\xe7\xae\xfc\xf7\x40').split(''),
minute = six + zero,
hour = minute * minute,
day = hour * (two + four),
Y = one + nine + seven + zero,
M = one,
D = one,
H = zero,
I = zero,
S = zero;

while (T) {
    var monthLookup = [
        [],
        (three + one) * day,
        (+(two + eight) + !(Y%four)) * day,
        (three + one) * day,
        (three + zero) * day,
        (three + one) * day,
        (three + zero) * day,
        (three + one) * day,
        (three + one) * day,
        (three + zero) * day,
        (three + one) * day,
        (three + zero) * day,
        (three + one) * day
    ];

    if (T >= monthLookup[M]) {
        T -= monthLookup[M++];
        if (M == one + three) {
            M = one;
            Y++;
        }
    }
    else if (T >= day) {
        T -= day;
        D++;
    }
    else if (T >= hour) {
        T -= hour;
        H++;
    }
    else if (T >= minute) {
        T -= minute;
        I++;
    }
    else {
        S = T;
        break;
    }
}

// prepend leading zeroes
M = M < one + zero ? zero + M : M;
D = D < one + zero ? zero + D : D;
H = H < one + zero ? zero + H : H;
I = I < one + zero ? zero + I : I;
S = S < one + zero ? zero + S : S;

alert(Y+'-'+M+'-'+D+' '+H+':'+I+':'+S);

```

Basically I get all the numbers by encoding the string (I've used `\x??` notation for ease of testing, but these are just unprintable ASCII chars and so don't include numbers) and then use concatenation to get the numbers I need, to use a pretty basic decrementor approach to populate the various fields.

---
Tags: popularity-contest, date
---


title: Output optimal trill fingerings

text:
# Question
Title: Output optimal trill fingerings
Note: all array references in this post are zero-indexed.

When playing the piano, two notes on the same key must be pressed with two different fingers. You *could* use the same finger, but it doesn't sound as good. At least, according to my piano teacher. I can't hear any difference.

The challenge is to take a space-separated list of 3 integers: Starting finger, ending finger, and length of repeating notes, and output the optimal sequence of finger numbers to match the input.

All piano jargon aside, output a string of numbers based on the input, where each number is `+1`/`-1` the one before it, all numbers are between 1 and 5, the sequence is `args[2]` digits long, starting with `args[0]` and ending with `args[1]`, and is formatted as below.

The input can be command line arguments, values on the stack (for \>\<\> users), STDIN, or any other conventional method.

Output will be a list of numbers, with these being valid outputs.

* `[1, 2, 3, 4, 5]`
* `(1 2 3 4 5)`
* `"12345"`
* `12345`*
* `1-2-3-4-5`\**
* `1 2 3 4 5`\**

For each asterisk on the style above, compute the following to calculate your score:

```
final-score = code.length * (1.00 - (asterisks * 0.05));

```

You can assume the first two params will be between 1 and 5, but if it handles at least 0-9, multiply your code by 95%.

If the last digit is less than 2, or the input parameters are impossible, error **however you like**, or just exit.

---

Finger numbers on the piano work like this, however this is not integral to the challenge.

```
1 | Thumb
2 | Index finger
3 | Middle finger
4 | Ring finger
5 | Pinky (finger)

```

---

Sample input and output:

Input: `1 2 2`
Output: `1 2`

Input: `1 4 8`
Output: `1 2 3 2 3 2 3 4`

Input: `2 3 10`
Output: `2 3 2 3 2 3 2 3 2 3`

Input: `5 2 1`
Output: `Error`

Input: `1 2 5`
Output: `Error`

Input: `5 1 5`
Output: `5 4 3 2 1`

Input: `1 1 1`
Output: `1`

---

These do *not* have to be handled correctly.

Input: `1 6 6`
Output: `1 2 3 4 5 6`

Input: `0 9 8`
Output: `Error`

# Answer
# Pyth, 36 * .95 * .90 = 30.78

```
jd+JrFAQ<*vz,H.xeJhH?&%K-vzlJ2>K0K.q

```

Test suite

Outputs space separated integers and can handle arbitrary integer inputs, so it qualifies for both bonuses.

Input format:

```
length
starting finger, ending finger

```

The output is constructed by starting with a range from the starting finger to the ending finger, then repeating the end of that range and the ending finger the necessary number of times. Exiting is done via explicit checks for the length of the second step being odd and positive, or else `.q`, Pyth's exit function is called.
> 4 votes

# Answer
# Javascript (ES6), ~~148~~ 146 * 0.95 * (1.00 - (0 * 0.05)) = 138.7

```
(a,b,c)=>c<(m=Math.abs(a-b))?0:eval('l=a,q=Array(m+1).fill().map(_=>a<b?l++:l--);while(q.length-c)q=q.concat(q.slice(-2,-1));q[q.length-1]-b?0:q')

```

Note: My way of indicating an "error" is returning 0 (chosen to save bytes of course).

The normal return type is a Javascript array. I'm not sure if that's an acceptable output format. If it isn't, I guess I'll have to add `JSON.stringify(...)`.

I think I get the 5% reduction since this can technically handle any range of numbers you want.

**Edit:** Saved 2 bytes thanks to @Ypnypn
> 2 votes

# Answer
# CJam, 50 bytes * 0.9 * 0.95 = 42.75

```
q~_$_@<\~),>@1$,-_0<1$2%e|{];}{2/1$-2>*+S*\{W%}&}?

```

Try it online

Code length is 50 bytes. If I understand them correctly, it qualifies for all bonuses. It outputs space separated values (-10%), and works for values outside the range 1 to 5 (-5%).

The input format is:

```
length [startValue endValue]

```

The sequence produced is first the range from start value to end value, then the last 2 values repeated until the specified length is reached.

Explanation:

```
q~    Get and interpret input.
_$    Copy and sort start/end value pair.
_@<   Copy and compare sorted and unsorted start/end values. Will use the
      sorted one, but reverse the entire sequence at the end if the start
      value was larger than the end value.
\~    Get sorted start/end value to top, and unwrap it.
),    Generate range [0 .. endValue].
>     Slice off values to get range [startValue .. endValue].
@     Get specified number of values to top.
1$,   Get list length of values we already generated.
-     Subtract. This gives the number of values that still need to be generated.
_0<   Check if number is less than 0.
1$2%  Check if number is odd.
e|    Logical or. If one of the two conditions is true, there is no solution.
{     If branch for no solution.
  ];    Clear stack. Will produce empty output for no solution.
}     End of branch for no solution.
{     If branch for producing solution.
  2/    Divide remaining count by 2. Will repeat last two values this many times.
  1$    Copy already produced values to top.
  -2>   Slice off last 2 values.
  *     Repeat them.
  +     Add to already produced sequence.
  S*    Join with spaces.
  \     Swap condition for start value greater than end value to top.
  {W%}& Reverse sequence if needed.
}?    End of if for solution vs. no solution.

```
> 1 votes

---
Tags: code-golf, music
---


title: Text Processing #1: Hyphenation

text:
# Question
Title: Text Processing #1: Hyphenation
# Background

This is the first part of a 3-hole golf course on text processing. The over-arching idea is that if you take an input text and pipe it through the solutions to all three challenges (with a small amount of glue code), it will spit out a beautifully formatted paragraph. In this first challenge, your task is a hyphenate a piece of text using given hyphenation patterns.

# Input

Your program shall take two string inputs: a piece of text and a list of hyphenation patterns. The first input is simply a non-empty string of printable ASCII characters and spaces; it will not contain line breaks or tildes `~`. The second input is a comma-delimited list of words, which consist of tilde-delimited syllables of lowercase ASCII characters. An example is `ex~cel~lent,pro~gram~ming,abil~i~ties`.

# Output

Your program shall modify the first input in the following way. Any word (maximal substring of alphabetical ASCII characters) whose hyphenated lowercase version is found in the second input shall be replaced by that hyphenated version, but its case shall be preserved. With the above example list, if the text contains the word `Excellent`, it shall be replaced by `Ex~cel~lent`; however, `Excellently` shall *not* be modified. Your output shall be this modified string.

# Detailed Rules and Scoring

You can assume the following about the inputs:

* The first input contains no tildes, and no leading, trailing or repeated spaces. It is not empty.
* The second input contains at least one word, and each word in it contains at least two syllables. Each syllable is non-empty.
* The second input does not contain a word that occurs as a syllable in another word.

You can change the order of the two inputs, if desired, and optionally add one trailing newline to the output.

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

# Test Cases

These are listed in the format `1st input [newline] 2nd input [newline] output`.

```
Excellent programming abilities, you work excellently!
ex~cel~lent,pro~gram~ming,abil~i~ties
Ex~cel~lent pro~gram~ming abil~i~ties, you work excellently!

Superman (sometimes incorrectly spelled "Super-man") is super #&%@ing strong.
su~per,some~times,in~cor~rectly,spell~ing
Superman (some~times in~cor~rectly spelled "Su~per-man") is su~per #&%@ing strong.

IncONsISTent caPItalizATIon!
in~con~sis~tent,cap~i~tal~iza~tion
In~cON~sIS~Tent caP~I~tal~izA~TIon!

Such short words.
awk~ward
Such short words.

Digits123 are456cool789.
dig~its,dig~i~tal,are~cool
Dig~its123 are456cool789.

magic magic
ma~gic
ma~gic ma~gic

```

Any possible hyphenation error in this challenge is due to this hyphenation tool.

# Answer
# Pip, ~~60~~ 54 bytes

```
Fwa^`([A-Za-z]+)`O{aQ'~?'~w@++y}M(LCwQ_RM'~FIb^',Yv)|w

```

GitHub repository for Pip

Takes inputs as command-line arguments (which necessitates quotes around input 1, assuming it contains spaces). No trailing newline is printed (add an `x` to the end of the program to add one).

Somewhat ungolfed, with comments:

```
 ; Split 1st input on runs of letters, including the separators in the results
a^:`([A-Za-z]+)`
 ; Split 2nd input on commas
b^:',
 ; Iterate over the words w in that list
Fwa {
  ; Filter b for entries that match the current word (lowercase, with tildes removed)
 m:(LCw EQ _RM'~)FIb
  ; We expect this to be a list of 0 or 1 elements
  ; If it has one, m gets that element (the hyphenation pattern); if it's empty, m gets nil
 i:-1
 m:m@i
  ; Map this function to each character of pattern m: if it's tilde, return tilde;
  ; otherwise, return corresponding character of w
 m:{aEQ'~ ? '~ w@++i}Mm
  ; Output the result, unless it was nil (falsey), in which case output the original word
 Om|w
}

```

Sample run:

```
C:\Users\dlosc> pip.py hyphens.pip "IncONsISTent caPItalizATIon!" in~con~sis~tent,cap~i~tal~iza~tion
In~cON~sIS~Tent caP~I~tal~izA~TIon!

```
> 6 votes

# Answer
# Retina, 88 bytes

```
+is`(?<![a-z~])([a-z~]+)(?=([a-z]+)+[^a-z~].*(?<=[\n,]\1(?(2)!)(?<-2>~\2)+[\n,]))
$1~
\n.*
<empty>

```

For counting purposes, each line goes into a separate file, `\n` are replaced with actual newline characters and `<empty>` is an empty file. For convenience, you can run the above code from a single file (where `<empty>` is an empty line) if you use the `-s` interpreter flag.
> 8 votes

# Answer
# Javascript ES6, ~~117~~ 141 chars

```
f=(t,p)=>p.split`,`.map(p=>t=t.replace(RegExp("((?:^|[^a-z])"+p.replace(/~/g,")(")+")(?=$|[^a-z])","ig"),(...x)=>x.slice(1,-2).join("~")))&&t

```

Test:

```
document.querySelector(".question pre").textContent.split("\n\n").map(t=>(t=t.split("\n"))&&f(t[0],t[1])==t[2])
// Array [ true, true, true, true, true ]

```
> 2 votes

# Answer
# Javascript (ES6), ~~173~~ 169

Basic regex search and replace

```
(a,b)=>(b.split`,`.map(s=>a=a.replace(eval(`/(^|[^a-z])(${s.replace(/~/g,"")})(?=[^a-z]|$)/gi`),(_,n,o)=>(x=0,n+s.split``.map((q,i)=>(q=='~'&&++x?q:o[i-x])).join``))),a)

```

Fiddle

**Edit:** Fixed bug for test case `magic magic`, `ma~gic`
> 1 votes

# Answer
# Perl, 146

```
$a=<>;$d=$_=~s/~//rg,$a=~s/(?<!\pL)$d(?!\pL)/h($&,$_)/gie for(split/,|\n/,<>);
print$a;
sub h{($g,$h)=@_;while($h=~/~/g){substr($g,"@-",0)='~'}$g}

```

Just a first attempt, lots of things can be shortened - will continue tomorrow!
> 0 votes

---
Tags: code-golf, string, natural-language
---


title: Comparing powers.

text:
# Question
Title: Comparing powers.
Compare two numbers N1 = abc, N2 = def by constructing a function f(a,b,c,d,e,f) that:

* returns 1 if N1 \> N2
* returns -1 if N1 \< N2

**Note:** You are not required to return any value for any other relation between N1 and N2. e.g. when they are equal or when their relation is undefined (complex numbers).

other constrains:

* all numbers are integers
* a,b,c,d,e,f may be positive or negative but not zero.
* |a|,|d| \< 1000
* |b|,|c|,|e|,|f| \< 1010
* running time less than few seconds

Examples:

```
f(100,100,100,50,100,100) = 1
f(-100,100,100,50,100,100) = 1
f(-100,99,100,50,100,100) = -1
f(100,-100,-100, -1, 3, 100) = 1
f(535, 10^9, 10^8, 443, 10^9, 10^9) = -1

```

This is code golf. Shortest code wins.

# Answer
> 3 votes
### Mathematica, 110 chars

```
z[a_,b_,c_,d_,e_,f_]:=With[{g=Sign[a]^(b^c),h=Sign[d]^(e^f)},If[g!=h,g,g*Sign[Log[Abs[a]]b^c-Log[Abs[d]]e^f]]]

```

# Answer
> 7 votes
## Ruby 1.9, ~~280 227 189~~ 171 characters

```
z=->a,b,c,d,e,f{l=->a{Math.log a}
u=->a,b{[a.abs,a][b&1]}
a=u[a,b=u[b,c]]
d=u[d,e=u[e,f]]
d*a<0?a<=>d :b*e<0?b<=>e :(l[l[a*q=a<=>0]/l[d*q]]<=>f*l[e*r=b<=>0]-c*l[b*r])*q*r}

```

I know this is *a bit* longer than the other solutions, but at least this approach should work without calculating abc, def, bc or ef.

Edit:

* (279 -\> 280) Fixed a bug when `a**b**c < 0` and `d = 1`.
* (280 -\> 227) Removed an unnecessary check for a special case.
* (227 -\> 192) Removed some checks that aren't necessary with the given criteria (non-zero integers, no output necessary for complex values)
* (192 -\> 189) Due to all the other checks, I can safely calculate `log(log(a)/log(d))` instead of `log(log(a))-log(log(d))`.
* (189 -\> 171) Simplified way to transform equivalent problems into one another.

Testcases:

```
z[100, 100, 100, 50, 100, 100] == 1
z[-100, 100, 100, 50, 100, 100] == 1
z[-100, 99, 100, 50, 100, 100] == -1
z[100, -100, -100, -1, 3, 100] == 1
z[535, 10**9, 10**8, 443, 10**9, 10**9] == -1
z[-1, -1, 1, 2, 2, 2] == -1
z[1, -5, -9, 2, -1, 2] == -1
z[1, -5, -9, 2, -1, 3] == 1
z[3, -3, 3, -4, 1, 1] == 1
z[-2, 1, 1, 1, 1, 1] == -1
z[1, 1, 1, -1, 1, 1] == 1
z[1, 1, 1, 2, 3, 1] == -1
z[1, 1, 1, 2, -3, 2] == -1
z[1, 1, 1, 2, -3, 1] == 1
z[-1, 1, 1, 1, 1, 1] == -1
z[2, 3, 1, 1, 1, 1] == 1
z[2, -3, 2, 1, 1, 1] == 1
z[2, -3, 1, 1, 1, 1] == -1

```

# Answer
> 1 votes
# ShortScript, 89 bytes

```
{CP
$M^ η1 η2
$M^ ζ η3
↑Αζ
$M^ η4 η5
$M^ ζ η6
↔α>ζ↑Ζ1
↔α<ζ↑Ζ-1}

```

The implementation isn't exactly the described one, but it works.

This answer is non-competing, since ShortScript has been published after this challenge.

# Answer
> 0 votes
## Python 2.6 (this doesn't actually work)

```
import cmath
g=cmath.log
f=lambda a,b,c,d,e,f:-1+2*((c*g(b)+g(g(a))-f*g(e)-g(g(d))).real>0)

```

today i learnt python has a complex log function. so, blindly double log both sides and look at the real component. works for 4 out of the 5 tests. not sure what's happening with the fourth one.

```
print f(100,100,100,50,100,100) == 1
print f(-100,100,100,50,100,100) == 1
print f(-100,99,100,50,100,100) == -1
print f(100,-100,-100, -1, 3, 100) == 1 # failure, sadness.
print f(535, 10^9, 10^8, 443, 10^9, 10^9) == -1

```

# Answer
> -1 votes
## Python (99)

```
from math import*
from numpy import*
l=log
def f(a,b,c,d,e,f):return sign(l(a)*l(b)*c-l(d)*l(e)*f)

```

# Answer
> -2 votes
## Haskell, 44 characters

```
n True=1
n _=1-2
g a b c d e f=n$a^b^c>d^e^f

```

Runs under a second for all the test examples on *my* machine.

---
Tags: code-golf
---