title: Draw the shadows of buildings

text:
# Question
Title: Draw the shadows of buildings
Input:

```
1
      X
      X
      X
      X      XX    XXXXXX     X X X
      X      XX    XXXXXX     X X X
XXX   X      XX    XXXXXX     X X X
XXX   X      XX    XXXXXX     X X X

```

Output:

```
      X.
      X..
      X...
      X....  XX.   XXXXXX.    X.X.X.
      X..... XX..  XXXXXX..   X.X.X..
XXX.  X......XX... XXXXXX...  X.X.X...
XXX.. X......XX....XXXXXX.... X.X.X....

```

Input:

```
2
         XX
         XX
         XX
         XX
         XX
     XX  XX
     XX  XX
     XX  XX
     XX  XX

```

Output:

```
        .XX
       ..XX
      ...XX
     ....XX
    .....XX
   ..XX..XX
  ...XX..XX
 ....XX..XX
.....XX..XX

```

Specification:

* You must take as input
    1. A flag signifying whether the light is coming from the top left or top right. This can be `1` or `2`, `-1` or `1`, `0` or `65536`, or whatever is convenient for you, as long as both flags are integers.
    2. Rows composed of either `X` or , all of the same length in characters (i.e. padded with )
        + All `X`s will either be on the last row or have an `X` under them (meaning no floating buildings)
* You must output the rows (buildings) with shadows added. This is done with the following procedure:
    + If the light is coming from the top left, draw a right triangle of `.`s with the same height and width as the height of the building, starting from one space past its right edge and going rightwards.
    + Otherwise, if it's from the top right, do the same thing but start from one space past its left edge and pointing left.
    + Remember, do not alter `X`s by changing them to `.`s; leave them as they are.
    + There will always be "room" for your shadows, i.e. if there's a 3-space tall building at the end there will be at least 3 spaces of padding after it.
* This is , so the shortest code in bytes will win!

# Answer
### GolfScript, 67 characters

```
n%(~:S\zip\%.0=\{.' '3$);+{{\(@[\].~<=}%+}:M~'X'/'.'*@@M}%S%zip\;n*

```

1/-1 for shadows going right/left. Run the example online:

```
      X.
      X..
      X...
      X....  XX.   XXXXXX.    X.X.X.
      X..... XX..  XXXXXX..   X.X.X..
XXX.  X......XX... XXXXXX...  X.X.X...
XXX.. X......XX....XXXXXX.... X.X.X....

```
> 6 votes

# Answer
# Perl - 85

```
BEGIN{$d=-<>}$d?s/X /X./g:s/ X/.X/g;s/ /substr($p,$+[0]+$d,1)eq'.'?'.':$&/ge;$p=$_;

```

EDIT: I totally forgot about the `-p` flag this needs to be run with. Added 2 to char count.
The flag specified at the first line is `0` for shadows going left and `2` for shadows going right.
> 11 votes

# Answer
# Python 3 - 233

Well, that turned out longer than expected...

1 for shadows going right, -1 for shadows going left.

```
d,x=int(input()),[1]
while x[-1]:x+=[input()]
x,o,l,h=list(zip(*x[1:-1]))[::d],[],0,len(x)-1
for i in x:o+=[''.join(i[:len(i)-l])+''.join(i[len(i)-l:]).replace(' ','.')];l=max(l-1,i.count('X'))
for i in zip(*o[::d]):print(''.join(i))

```

EDIT: Didn't see the either side padding in the rules. Ehehe. ^^'
> 4 votes

# Answer
# JavaScript - 14

```
eval(prompt())

```

The flag on the first line is `for(p='';l=prompt();)console.log(p=l.replace(/ /g,function(a,b){return p[b+1]=='.'||p[b]=='.'||l[b+1]=='X'?'.':a}));` for shadows facing the left or `for(p='';l=prompt();)console.log(p=l.replace(/ /g,function(a,b){return p[b-1]=='.'||p[b]=='.'||l[b-1]=='X'?'.':a}));` for shadows to the right.

This *might* abuse the "whatever is convenient for you" rule for the flag :P

---

**Edit:** without abuse (127):

```
c=prompt();for(p='';l=prompt();)console.log(p=l.replace(/ /g,function(a,b){return p[b+c]=='.'||p[b]=='.'||l[b+c]=='X'?'.':a}));

```

The flag for this is `1` or `-1`
> 3 votes

# Answer
## Python 2.7 - 229

```
p,s,M,J,L=input(),__import__('sys').stdin.readlines(),map,''.join,len
n,s,r,f=L(s),M(str.strip,M(J,zip(*s[::-1]))),0,[]
for l in s[::p]:f,r=f+[(l+'.'*(r-L(l))+' '*n)[:n]],max(r-1,L(l))
print'\n'.join(M(J,zip(*f[::p])[::-1]))

```

**Ungolfed Version**

```
def shadow(st, pos):
    _len = len(st)
    st = map(str.strip, map(''.join,zip(*st[::-1])))
    prev = 0
    res = []
    for line in st[::[1,-1][pos-1]]:
        res +=[(line+'.'*(prev-len(line)) + ' '*_len)[:_len]]
        prev = max(prev - 1, len(line))
    return '\n'.join(map(''.join,zip(*res[::[1,-1][pos-1]])[::-1]))

```
> 1 votes

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


# Question
Title: Print "Hello World" in Ascii Art ... without its characters
Your mission is to write a program that prints "Hello World!". Simple?

The text must be human readable and should not be "|-| € |\_ |\_ 0 // 0 |? |\_ |) \\./" or something like that.

The program should not contain:

* Newline character
* Any characters in the string "Hello World!" including whitespace (whitespace outside strings is allowed)
* Graphics (it must be run on text console (or master boot record in text mode)
* Number constants that represent chars (Ascii-values, Hex chars)
* Any simple tricks that create above numbers (ex. 36\*2 or 176/2-1 (72, ASCII code of "H") )
* Non-ASCII chars
* Web request
* User input
* Over 1000 chars
* Random numbers

It can contain:

* Ascii-art
* system calls that do not return letters (a-z and A-Z)
* h, e, l, o, w, r, d and ! chars outside strings or equal datatypes

It is possible and allowed to change line by going over line max width (program must detect that itself). Linux command

```
stty size

```

may help.

Fewer chars are better.

Basically, write 'Hello World' in Ascii Art.

# Answer
> 9 votes
# Mathematica

`n` is an integer (in base 10).

`IntegerDigits[n, 2]` is a list of digits {0,1} that, when concatenated, represent `n` in base 2.

`a=ArrayReshape[ IntegerDigits[n, 2], {19, 130}]` is the same digit list rearranged as a grid of 0's and 1's with the dimensions {19, 130}.

`a/. {1 -> Style["b", 0], 0 -> Style["*", 16]}` replaces each 1 with "b" of font size 0 (hence it is invisible) and replaces each 0 with "\*" of font size 16.

`Grid[%, Spacings-> 0]` tightly displays the array, with replacements. (`%` stands for the line of code just preceding.)

```
n = 35001712241657190367892609813472861877431771881809334927846103886350214620897333001318391750688831360911930936377842577561578307677143958805011717980866099960819297494949545473701708671861367649525697579614849813048033148938384921009819295565066663593631828895192249784580492554132824237605034894192899878952441264004931502456152233835512128208573340080592412541607535529943162874085478980356198477815840725568296012406592398594861031009108478191718964371749381682556005188569781665817649936105396104242935885784130227679335972626450197115544027612921177483696531170727698036575934297259107966503600164537149096917592511980213534973597038276657982204662616524347887277731541480128061438343931154467720012975561086600146498015257664764847849471;
Grid[ArrayReshape[ IntegerDigits[n, 2], {19, 130}] /. {1 -> " ", 0 -> Style["*", 16]},
   Spacings -> 0]

```

# Answer
> 4 votes
# J - 59 or 84 char

Two versions, depending on how you define 'human-readable'. Any modifications to the resulting ASCII art would ultimately be based on this kind of compression scheme.

```
,.'#'#~"0#:86235578437 123845917517 91625269844 92707043917
,._45#&'#'"0\#:36761300340830444705259651524275206394141032533795647996053048645081x

```

The first version works by taking its list of numbers, expanding them into bitvectors (`#:`), using those to select (`#~`) how many '#' to take for each point (`"0`) in the matrix, and then running the result (a 2D matrix of strings of length at most 1) into a matrix of characters (`,.`).

The second does the same thing, except it's shorter—by one character, mind you!—to pack all of its bitvectors into a single extended precision number, which you then take 45 bit cuts (`_45(blah)\`) of.

Here's what they look like:

screenshot of jconsole running code http://i.snag.gy/XzYYa.jpg

# Answer
> 1 votes
# Bash + tr, 82 79 bytes

```
a=({q..s});a=${a[@]};s=${a:1:1};t${a:2:1} "[$s-~]" "[u-~][$s-v]"<<<Tqxx{,c{~xp-

```

Output:

```
$ a=({q..s});a=${a[@]};s=${a:1:1};t${a:2:1} "[$s-~]" "[u-~][$s-v]"<<<Tqxx{,c{~xp-
Hello World!
$

```

# Answer
> 1 votes
# Java generating the Strings only from a 0 as integer; 391 chars

```
class A{static int a=0,b=a++,e=a++,f=a/a;static char p(String s){return(char)Byte.parseByte(s,a);}public static void main(String[]z){long x=e,y=b;String c=((Long)x).toString(),d=((Long)y).toString();char l=p(c+c+d+c+c+d+d),m=p(c+c+d+d+c+d+c),o=(char)(l+a+f),_=p(c+d+d+d+d+d),$=_++;System.out.print(new char[]{p(c+d+d+c+d+d+d),m,l,l,o,$,p(c+d+c+d+c+c+c),o,(char)(o+a+f),l,(char)(m-f),_});}}

```

in that code the only literal variable is an Integer 0, the rest is made via Wizardry and other math tricks

---
Tags: code-golf, string, restricted-source
---


# Question
Title: Generate a (completely deterministic) pseudorandom bit stream
Inspired by Random with your hands tied:

---

## The Goal

The goal of this challenge is to write a program that generates a pseudorandom bit stream, which is a string of 1s and 0s that appears to be purely random, but is actually generated in a deterministic way. Your program should output a string of 1 and 0s (with optional whitespace) and should pass the following requirements:

1. Given unlimited time and memory, your program must continue to output a string of 1s and 0s forever
2. Your program must output more than 1000 random bits in about one minute, on a reasonable machine. If this requirement is impossible, then I will lessen it.
3. The string of bits can repeat, but the length of the repeating section must be more than 1000 bits.
4. The string of bits must pass as many of the randomness tests (described below) as possible.
5. The program must not take any input from any external sources or use any built-in rand()-like function.
6. Because of the above requirement, the program must output the same exact string of bits each time that it is run.

---

## Randomness Test #1

The string of pseudorandom bits must not include any obvious pattern upon visual inspection.

## Randomness Test #2 (subject to change based on comments)

The string of bits must contain an equal distribution of 1s and 0s. To test this (and other things too), the stream of bits is broken into segments that are 3 bits long, such as `101|111|001`.

Out of all of these segments, 1/8 of them should have three 1s and no 0s, 3/8 of them should have two 1s and one 0, 3/8 of them should have one 1 and two 0s, and 1/8 of them should have no 1s and three 0s.

## Randomness Test #3

A "run" is defined as a consecutive series of bits that all have the same value. The string `1001001110` has three runs of size 1 (`1..1.....0`), two runs of size 2 (`.00.00....`) and one run of size 3 (`......111.`). Notice that runs do not overlap.

Out of a string of 1000 random bits, there should be about 250 runs of size 1, 125 runs of size 2, 62 runs of size 3, etc. In general, for run size R, there should be about `1000/(2**(R+1))` runs of that size.

## Randomness Test #4

The first 840 bits are split into two halves of 420 bits each. Each bit on the first half is compared to the corresponding bit on the second half. The two bits should match about fifty percent of the time.

---

Here is the source code of a Perl program that performs tests 2 through 4. As of now, it requires that the string of bits not contain any whitespace.

---

## Objective Winning Criterion Time!

The winner is the program that passes all of the 6 requirements and all of the randomness tests to the degree that it is indistinguishable from randomness. If multiple programs accomplish this, then the one that takes the longest amount of time to repeat will win. If multiple programs accomplish this, then I might have to find more randomness tests to act as tie-breakers.

# Answer
# Mathematica 78 53 chars

The digits of the binary representation of Pi seem to behave as if they are chaotically produced although this is unproven.

The following simple routine deterministically returns as a string the binary digits of pi, corresponding to `d` decimal digits:

```
f[d_]:=ToString@FromDigits@RealDigits[N[Pi,d],2][[1]]

```

**Usage**

If we request the counterpart of 301 decimal digits of Pi, we receive 1000 binary digits.

```
f[301]
StringLength[%]

(* out *)
1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111000001000100010100110011111001100011101000000001000001011101111101010011000111011000100111001101100100010010100010100101000001000011110011000111000110100000001001101110111101111100101010001100110110011110011010011101001000011000110110011000000101011000010100110110111110010010111110001010000110111010011111110000100110101011011010110110101010001110000100100010111100100100001011011010101110110011000100101111001111110110001101111010001001100010000101110100110100110001101111110110101101011000010111111111101011100101101101111010000000110101101111110110111101110001110000110101111111011010110101000100110011111101001011010111010011111001001000001000101111100010010110001111111100110010010010010100001100110010100011110110011100100010110110011110111000010000000000111110010111000101000010110001110111111000001011001100011011010010010000011011000011100011

1000 (* characters *)

```

Because Pi is an irrational number, there is no period. However, there will be practical constraints due to the hardware one is running.

**Test 1** Looks good to me.

**Test 2**

```
d=301;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]
(* out *)
{{{1,1,0},35},{{0,1,0},45},{{0,0,0},41},{{1,1,1},40},
{{0,1,1},50},{{1,0,1},32},{{1,0,0},43},{{0,0,1},47}}

```

More thorough check:

```
d=10^6;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]

{{{1,1,0},138565},{{0,1,0},138146},{{0,0,0},138260},{{1,1,1},138427},
{{0,1,1},139119}, {{1,0,1},138404},{{1,0,0},137926},{{0,0,1},138462}}

```

**Test 3: Runs**

```
d=10^6;
res3=SortBy[Tally@Split@RealDigits[N[Pi,d],2][[1]],Last]/.{a_,b_}:> {Length[a],b}
ListPlot[res3 ,AxesLabel-> {"Run Length","Runs"},AxesOrigin->{0,0}]

```

I ran a large number of cases to systematically check out the distribution of runs. In approximately 3 million binary digits, there were 830k runs of 1, 416k runs of 2, 208k runs of 3, 104k runs of 4, etc.

**Test 4: Matching of first and second half of data**

The matches are the 212 cases of 0 and 2; the mismatches are the 208 cases where the sum of the respective digits is 1.

```
d=301;
Tally[Plus@@Partition[Take[RealDigits[N[Pi,d],2][[1]],840],420]]

(* out *)
{{1,208},{0,108},{2,104}}

```

**Timing**

It takes under two seconds to calculate 3321928 binary digits (corresponding to 10^6 decimal digits).

```
(r=f[10^6]);//AbsoluteTiming
StringLength[r]

(*out*)
{1.785928,Null}
3321928

```
> 9 votes

# Answer
## C, 61

```
main(s,n){for(n=1u<<31;putchar((s%=n)/(n/2)&1|48);s*=65539);}

```

Yeah, I know it's not code golf. This is obviously rather an anti-solution... but it sure enough fulfills your criteria.

> $ ./a.out | head -c840 000000001000111101100110110011100100011101110001101001101110011101100111010111010010001001110001111110010001010101101000110101000011110010100101001101110100011111000101000110000111100100010101010100110101101010001110101000011011001010111011110110101000001110011000010100001111110110001000000101100011000110000010110011000010101101011100010011011111111100001010111110111010110001000010110111000010101001000011001001110110001001101011011110111011010100000000001001010100111000000100010011110001010111001110101111100110110111010001101001100000101000111000101000110100001111010110100001100110011011110001011011100010111011100001110100110001010011001110001010110100111111111010110101100110000101111111111000111101100011000111010111010100110001001110101110100011101110001100110110000001100101110100101000101011100000110111101101100110000000101110
> $ ./a.out | head -c840 | perl tester.pl
> Test 2: 1 (1) 2.93333333333333 (3) 3.1 (3) 0.966666666666667 (1)
> Test 3: 214 99 71 24 7 5 1 1 2 2
> Test 4: 0.495238095238095

Period length is 2²⁹.
> 8 votes

# Answer
## Python, 90

```
g=[19]
print(''.join("01"[(g.append((11*g[-1]+13)%1024)or g[-1])>512]for i in range(1000)))

```

`g` is the seed value. Random sampling exhibits a remarkably normal distribution repeated random sampling of sample means yielded a mean of `0.506` and a a standard deviation of `.0473` (sample size of 1000). Unfortunately, randomness is highly sensitive to initial seed. The seed in the above code gave me the best randomness :p

**UPDATE**

Let's see how this code holds up to the OP's tests:

## Test #1

This one's a bit subjective... but it looks pretty irregular to me.

## Test #2

> Three 1's: 0.141
> Two 1's: 0.371
> One 1: 0.353
> Zero 1's: 0.135

## Test #3

Runs by size:

```
8: 11
7: 3
6: 7
5: 13
4: 32
3: 67
2: 119
1: 216

```

## Test #4

> ~~Ratio of equalities: 0.94~~  This is a typo. Will update with the correct number soon.
> 3 votes

# Answer
## Haskell ~~74~~ 58

```
main=print$iterate(read.take 9.show.(^3))7>>=show.(`mod`2)

```

Thanks to **shiona** for the simplification. Results:

> $ ~/golf$ ./pseudorandom | head -c 1000 111110110101011110001011110101011110001111011001110101100100111000100100000011000100011101010111000000001110100111100010110000100000001001111011100001101101001111110100111011111110011011101111010110001110011100010000001011011100010111011110011110100110100000110110010011101010001111101011111110000110110110011111011101000011110010000011011010011110110100010011100011011111011010110001100111100100100001110100001110111011111000001101001010100001100111010111011011011001110000100000100000010111011010111011111011011101001100100011111101110101101010111101001111110101110101001011111011111100111110001001001010001011100100101000010101011001101011011001100111101010001110001011110001011111110110100110011000010101100010011011010100000110100001000010110110111101101010000001110001100011010100000011111010111100101110101001000111001000000101111110010110001011011000011111011001100001101000101001111000101011101010001010110010111111110111111101000111010001001010010011101011100101011101000101101000010101100
>
> ./pseudorandom | head -c 1000 | perl test.pl
>
> Test 2: 0.966666666666667 (1) 2.4 (3) 3.3 (3) 1.33333333333333 (1)
>
> Test 3: 260 108 66 33 15 11 5 2
>
> Test 4: 0.495238095238095

This is also a terrible pseudo-random generator (similar to one used by von-Neuman). For those that were not aware `concatMap == (=<<) == flip . (>>=)` (for lists)
> 2 votes

# Answer
## C, 52 chars

```
main(a){for(a=1;putchar(48+a%2);a=a/2^-(a%2)&576);}

```

This is a 10 bit LFSR, test results:

```
$ ./a.out |head -c 1000 | perl randtest.pl
Test 2: 1.13333333333333 (1) 2.86666666666667 (3) 3.16666666666667 (3) 0.833333333333333 (1)
Test 3:  251 122 64 32 16 8 4 2  1
Test 4: 0.466666666666667

```
> 2 votes

# Answer
**Java, 371 317**

Based on a 128 bit LFSR (bit taps are from xilinx app note 52)

**EDIT:** I was not satisfied with using BigInteger so this version does not. Saved some characters. Output might be a little less random as I could not think of a good 'seeding' method.

**New Code:** Arguments: BITS\_TO\_PRINT

```
class R{public static void main(String[]a){int L=65536;int[]v={0,128,126,101,99};int[]b=new int[L];for(int x=0;x<L;x++)b[x]=(x*x)&1;for(int i=0;i<Integer.parseInt(a[0])+L;i++){if(1!=(b[v[1]]^b[v[2]]^b[v[3]]^b[v[4]]))b[v[0]]=1;else b[v[0]]=0;if(i>L)System.out.print(b[v[0]]);for(int j=0;j<5;j++)v[j]=(v[j]-1)&(L-1);}}}

```

**Old Version:** Arguments: SEED, BITS\_TO\_PRINT

```
import java.math.BigInteger;class R{public static void main(String[]a){BigInteger v=new BigInteger(a[0]);BigInteger m=new BigInteger("ffffffffffffffffffffffffffffffff",16);for(int i=Integer.parseInt(a[1]);i>0;i--){v=v.shiftLeft(1);if(!(v.testBit(128)^v.testBit(126)^v.testBit(101)^v.testBit(99))){v=v.setBit(0);}v=v.and(m);java.lang.System.out.print(v.testBit(0)?1:0);}}}

```

**New Version:** Example output, bits=100:

```
011001100111000110010100100111011100100111000111001111110110001001100000100111111010111001100100011

```
> 1 votes

# Answer
The question is essentially equivalent to "implement a stream cipher". So I implement RC4, since it's relatively simple.

I use no key, and drop the first 100000 bits, because the beginning of RC4 is a bit biased, especially since I skipped the key schedule. But I'd expect it to pass your test even without that (saving 20 chars of code).

Normally one would output a full byte per cycle, but converting to binary is rather ugly in C#, so I simply discard everything except the least significant bit.

```
var s=Enumerable.Range(0,256).ToArray();
byte i=0,j=0;
for(int k=0;;k++)
{
    i++;
    j+=(byte)s[i];
    var t=s[i];s[i]=s[j];s[j]=t;
    if(k>99999)
        Console.Write(s[i]+s[j]&1);
}

```

Or without spaces:

```
var s=Enumerable.Range(0,256).ToArray();byte i=0,j=0;for(int k=0;;k++){i++;j+=(byte)s[i];var t=s[i];s[i]=s[j];s[j]=t;if(k>99999)Console.Write(s[i]+s[j]&1);}

```

C#, 156 chars, works in LinqPad's statement mode. For a full C# program add the usual boilerplate.

---

We could also use built in crypto primitives(Cheater solution):

```
var h=SHA256.Create();for(BigInteger i=0;;i++){Console.Write(h.ComputeHash(i.ToByteArray())[0]%2);}

```

(C#, 99 chars, works in LinqPad's statement mode. For the normal C# compiler you'll need to add a bit of boilerplate)

The output of cryptographic hash functions is designed to be indistinguishable from random data, so I expect it to pass all randomness tests(die harder,...) you throw at it, but I'm too lazy to test.
> 1 votes

# Answer
## Sage/Python

This program prints the rightmost binary digits that are common to every sufficiently tall exponentiation tower of form 3333... For all that could ever be feasibly generated, these are the rightmost binary digits of Graham's number. The digit sequence is infinite, and is not periodic.

```
m = 1; x = 3; last = 0
while True:
    m *= 2; x = pow(3,x,m); l = len(bin(x))
    print '1' if l > last else '0',
    last = l

```

For 1000 digits, this took less than 2 seconds; however, the time will increase much faster than linearly in the number of digits.

The test results using the OP's program are

```
Test 2: 1.26666666666667 (1) 3.16666666666667 (3) 2.8 (3) 0.766666666666667 (1)
Test 3:  268 126 61 30 20 7 2  1 1
Test 4: 0.466666666666667

```

(See Are the rightmost digits of G random? for more than 32000 digits and additional statistical tests.)
> 1 votes

# Answer
**JavaScript - 1ms to 2ms for 1000 pseudo-random bits (139ms to 153ms for 100000 bits)**

This solution uses the fact that square roots are irrational, and thus pretty much random. Basically, it takes the square root of 2 to start, converts it to binary, throws out the leading part that matched the previous root, appends that to the random string, repeats with the next higher number (or back to 2 if the number repeated and was at least 30 bits long), and returns the random string once it is long enough.

```
var getDeterministicPseudoRandString = function(length){
    var randString = '';

    var i = 2;
    var prevRand = '';

    outerLoop:
    while(randString.length < length){
        var nextRand, nextFullRand = Math.sqrt(i++).toString(2).substring(1).replace('.', '');
        nextRand = nextFullRand;
        for(var j = prevRand.length; j > 0; j--){
            var replaceString = prevRand.substring(0, j);

            nextRand = nextFullRand;

            if(nextFullRand.indexOf(replaceString) == 0){
                if(j == prevRand.length && j > 30){
                    //start i over at 2
                    console.log('max i reached: ' + i);

                    i = 2;
                    continue outerLoop;
                } else {
                    nextRand = nextFullRand.replace(replaceString, '');
                }

                break;
            }
        }
        prevRand = nextFullRand;

        randString += nextRand;
    }

    return randString.substring(0, length);//Return the substring with the appropriate length
};

```

I haven't ran it through the tests yet, but I imagine it will do well on them. Here's a fiddle so you can see it in action. For my times, I just ran the program several times and took the fastest and slowest values as the ranges.
> 0 votes

# Answer
# perl, 44 bytes

I know this isn't code golf, but I've always been a fan of taking the low order bits of a simple quadratic function, eg:

```
$x=1/7;print substr($x*=4-4*$x,9,1)%2while 1

```

Period is longer than 3 billion, but I've run out of disk space to calculate more.
> 0 votes

# Answer
## Python

```
import hashlib
x=''
while 1:
    h=hashlib.sha512()
    h.update(x)
    x=h.digest()
    print ord(x[0])%2

```

Should have a period of about 2^512.
> 0 votes

---
Tags: code-challenge, random
---


title: Output the nth digits of an integer

text:
# Question
Title: Output the nth digits of an integer
**Without using strings** (except when necessary, such as with input or output) calculate the nth digit, **from the left**, of an **integer** (in base 10).

Input will be given in this format:

```
726433 5

```

Output should be:

```
3

```

as that is the fifth digit of "726433".

Input will **not** contain leading zeros, e.g. "00223".

Test cases / further examples:

```
9 1  ->  9
0 1  ->  0
444494 5  ->  9
800 2  ->  0

```

This is code golf; least amount of characters wins, but any built in functions such as "nthDigit(x,n)" are **not acceptable**.

Here's some pseudo-code to get you started:

```
x = number
n = index of the digit
digits = floor[log10[x]] + 1
dropRight = floor[x / 10^(digits - n)]
dropLeft = (dropRight / 10 - floor[dropRight / 10]) * 10
nthDigit = dropLeft

```

As you can see I'm new to code golf, and though I think it's a bit unfair that I ask a question before I've even answered one, I would really like to see what kind of responses this generates. :)

**Edit**: I was hoping for mathematical answers, so I cannot really accept answers that rely on converting strings to arrays or being able to access numbers as a list of digits.

# We have a winner

Written in "dc", **12** bytes. By *DigitalTrauma*.

# Answer
# dc, 12 bytes

```
?dZ?-Ar^/A%p

```

This is a mathematical answer. Here's how it works:

* `?` read input number and push to stack
* `d` duplicate top of stack
* `Z` Pops value off the stack, calculates and pushes the number of digits
* `?` read digit index and push to stack
* `-` subtract digit index from digit count
* `A` push 10 to the stack
* `r` swap top 2 values on stack
* `^` exponentiate 10 ^ (digit count - digit index)
* `/` divide number by result of exponentiation
* `A` push 10 to the stack
* `%` calculate the number mod 10 to get the last digit and push to top of stack
* `p` pop and print the top of stack

In action:

```
$ { echo 987654321; echo 1; } | dc ndigit.dc
9
$ { echo 987654321; echo 2; } | dc ndigit.dc
8
$ { echo 987654321; echo 8; } | dc ndigit.dc
2
$ { echo 987654321; echo 9; } | dc ndigit.dc
1
$

```
> 2 votes

# Answer
## GolfScript (10 bytes)

```
~(\10base=

```

This assumes input is as a string (e.g. via stdin). If it's as two integers on the stack, the initial `~` should be removed, saving 1 char.

If the base conversion is considered to fall foul of the built-in functions rule, I have a 16-char alternative:

```
~~)\{}{10/}/=10%

```
> 5 votes

# Answer
# Haskell 60 bytes and readable

```
nth x n
        | x < (10^n) = mod x 10
        | True = nth (div x 10) n

```

no strings involved!

```
*Main> nth 1234567 4
4

```
> 4 votes

# Answer
# CJam - 7

```
l~(\Ab=

```

CJam is a new language I am developing, similar to GolfScript - http://sf.net/p/cjam. Here is the explanation:

`l` reads a line from the input
`~` evaluates the string (thus getting the two numbers)
`(` decrements the second number
`\` swaps the numbers
`A` is a variable preinitialized to 10
`b` does a base conversion, making an array with the base-10 digits of the first number
`=` gets the desired element of the array

The program is basically a translation of Peter Taylor's solution.
> 4 votes

# Answer
# J - 15 24 char

A sufficiently "mathematical answer".

```
(10|[<.@*10^]-10>.@^.[)/

```

Same results as below, but is endowed with the mystical quality of being mathematical.

---

The short version, using base-10 expansion.

```
({0,10&#.inv)~/

```

We prepend a 0 to adjust for 1-based indexing.

Usage:

```
   ({0,10&#.inv)~/ 1234567 3
3
   ({0,10&#.inv)~/ 444494 5
9

```
> 3 votes

# Answer
# bc (driven by bash), 41 29

I think this is the first answer to do this mathematically and not with strings:

```
bc<<<"$1/A^(length($1)-$2)%A"

```

The use of `length()` perhaps seems a bit stringy, but the bc man page talks about number of digits and not length of string:

> ```
>   length ( expression )
>           The value of the length function is the  number  of  significant
>           digits in the expression.
>
> ```

Output:

```
$ ./ndigits.bc.sh 726433 5
3
$ ./ndigits.bc.sh 9 1
9
$ ./ndigits.bc.sh 0 1
0
$ ./ndigits.bc.sh 444494 5
9
$ ./ndigits.bc.sh 800 2
0
$

```
> 2 votes

# Answer
# Python 127

```
def f(i,n):
 b=10;j=i/b;k=1;d=i-j*b
 while j>0:
  k+=1;j/=b
 if n>k:
  return -1
 while k>n:
  k-=1;j/=b;i/=b;d=i-j*b
 return d

```
> 2 votes

# Answer
# C, 50

This uses arrays.

```
main(int c,char**a){putchar(a[1][atoi(a[2])-1]);}

```

Just ignore all the warnings.

And yes, in C, strings are really just arrays, so this is sort of cheap.

---

More Mathematical:

# C, 83

```
main(int c,char**a){printf("%d",(atoi(a[1])/pow(10,strlen(a[1])-atoi(a[2])))%10);}

```
> 2 votes

# Answer
## Tcl (42 bytes, lambda):

```
{{x y} {expr $x/10**int(log10($x)+1-$y)%10}}

```

## (49 bytes, function):

```
proc f {x y} {expr $x/10**int(log10($x)+1-$y)%10}

```

## (83 bytes, if we need to accept input from shell):

```
puts [expr [lindex $argv 0]/10**int(log10([lindex $argv 0])+1-[lindex $argv 1])%10]

```
> 1 votes

# Answer
# Mathematica - ~~24~~ 23

This one is kind of obvious :)

```
IntegerDigits[#][[#2]]&

```

Example:

```
IntegerDigits[#][[#2]]& [726433, 5]

```

Output:

```
3

```

You can get it shorter by hard-coding two integers, e.g.

```
IntegerDigits[n][[m]]

```

but then you first have to write `n = 726433; m = 5;`. The function call felt more similar to a program.
> 1 votes

# Answer
# Haskell, 142

I'm not sure I understood the question correctly, but this is what I think you wanted: read stdin (string), make the two numbers int (not string), do some algorithmic things, and then output the result (string). I crammed it into 142 chars, which is way too much:

```
import System.Environment
a%b|a>9=div a 10%(b+1)|1<2=b
x#n=x`div`10^(x%1-n)`mod`10
u[a,b]=read a#read b
main=fmap(u.words)getContents>>=print

```

example usage:

```
> echo 96594 4 | getIndex
9

```
> 1 votes

# Answer
## Scala (~~133~~ 99 bytes):

Works for all positive inputs. Divides by 10 to the power of the digit looked for from the right, then takes it modulo 10.

```
def k(i:Array[String])={val m=i(0).toInt
(m*Math.pow(10,i(1).toInt-1-Math.log10(m)toInt)).toInt%10}

```

Thank you for noticing the bug in the previous formula. This one is shorter.
> 1 votes

# Answer
**C 145**

Program finds distance from end of integer and divides until index is reached then uses modulus 10 to get the last digit.

```
int main()
{
int i,a,b,d,n;
scanf("%d %d",&i,&a);
d=(int)(log(i)/log(10))+1;
n=d-a;
while(n--){i=(int)(i/10);}
b=i%10;
printf("%d",b);
}

```
> 1 votes

# Answer
# Wolfram Alpha - between 40 and 43

Of course, I can totally defend that using `IntegerDigits` is a trick that does not fall under

> any built in functions such as "nthDigit(x,n)"

But because my previous answer still felt like cheating a little bit, here's an alternative. Unfortunately it's quite a bit longer, but I didn't see how to shorten it any more than I did.

Counting in a similar way as before (with the ampersand, without passing in any arguments),

```
Mod[Trunc[#/10^(Trunc[Log10[#]]-#2+1)],10]&

```

has 43 characters. By negating the exponent and shuffling the terms around, I can lose one arithmetic operator (`10^(...)x` will be interpreted as multiplication)

```
Mod[Trunc[10^(#2-Trunc[Log10[#]]-1)#],10]&

```

~~I don't have Mathematica at hand to test, I doubt that it will be~~As I suspected (and as was kindly verified by kukac67) in Mathematica this is not accepted, but it runs in WolframAlpha.

I am in doubt about the use of `RealDigits`, because I restricted myself from using `IntegerDigits` for this answer and they are quite similar. However, if I allow myself to include it (after all, it doesn't return the integers directly, just how *many* of them there are), I can slash off another two characters:

```
Mod[Trunc[10^(#2-RealDigits[#]-1)#],10]&

```
> 1 votes

# Answer
# R (60)

Solved the problem using log10 to calculate the number of digits. The special case x==0 costs 13 character, sigh.

```
f=function(x,n)if(x)x%/%10^(trunc(log10(x))-n+1)%%10 else 0

```

Ungolfed:

```
f=function(x,n)
  if(x)
    x %/% 10^(trunc(log10(x)) - n + 1) %% 10
  else
    0

```

Usage

```
> f(898,2)
[1] 9

```
> 1 votes

# Answer
# JavaScript - 84

```
p=prompt,x=+p(),m=Math;r=~~(x/m.pow(10,~~(m.log(x)/m.LN10)+1-+p()));p(r-~~(r/10)*10)

```

Purely mathematical, no strings, none of them. Takes the first number in the first prompt and the second number in the second prompt.

**Test Case**:

```
Input: 97654 5
Output: 4

Input: 224658 3
Output: 4

```

**Ungolfed Code:**

```
p = prompt,
x = +p(), // or parseInt(prompt())
m = Math;

r = m.floor( x / m.pow(10, m.floor(m.log(x) / m.LN10) + 1 - +p()) )
//                                               ^-- log(10) ^-- this is `n`

p(r - ~~(r / 10) * 10) // show output

```
> 1 votes

# Answer
## perl,  ~~38, 36~~  no *30* characters

(not counting the linefeed)

This is arguably cheating due to the command switch, but thanks for letting me play :-)

```
~/$ cat ndigits.pl
say((split//,$ARGV[0])[$ARGV[1]-1]);
~/$ tr -cd "[:print:]" < ndigits.pl |wc -m
36
~/$ perl -M5.010 ndigits.pl 726433 5
3

```

**edit**:

Was able to remove 2 characters:

```
 say for(split//,$ARGV[0])[$ARGV[1]-1];
 say((split//,$ARGV[0])[$ARGV[1]-1]);

```

... then 6 more:

```
 say((split//,shift)[pop()-1]);

```

**How**

We split the input of the first argument to the script `$ARGV[0]` by character (`split//`) creating an zero indexed array; adding one to the second argument `$ARGV[1]` to the script then corresponds to the element at that position in the string or first argument. We then hold the expression inside `()` as a one element list which `say` will iterate through. For the shorter short version we just `shift` in the first argument and use the remaining part of @ARGV to use for the index - once `shift`ed only the second argument remains so we `pop()` it and subtract 1.

Is this supposed to be a math exercise? I just realized I'm indexing a string read from input, so ... I guess I lose?? Mark me up if I make sense in parallel golf course and I will try again - more mathematically - in a separate answer.

cheers,
> 1 votes

# Answer
# C, 94

```
main(x,y,z,n){scanf("%d%d",&x,&y);for(z=x,n=1-y;z/=10;n++);for(;n--;x/=10);printf("%d",x%10);}

```

# C, 91, invalid because of using arrays.

```
main(x,y,z){int w[99];scanf("%d%d",&x,&y);for(z=0;x;x/=10)w[z++]=x%10;printf("%d",w[z-y]);}

```
> 0 votes

# Answer
# PHP, 58

Using math only

`<?$n=$argv[1];while($n>pow(10,$argv[2]))$n/=10;echo $n%10;`
> 0 votes

# Answer
# ~-~! - ~~94~~ 93

Bends the rules a bit - it's a function that takes n as input and assumes the number to find digit n of is stored in `'''''` \- and ~-~! doesn't support floats.

```
'=~~~~~,~~:''=|*==~[']<''&*-~>,'|:'''=|*==%[%]~+*/~~~~/~~|:''''=|'''''/''&<<'''&'''''>-*-~>|:

```

`'''''=~~~~,~~,~~,~~,~~,~~:''''''=''''&~:` will result in `''''''` being `~~` (2) (''''' = 128).
> 0 votes

# Answer
## Python 2.7 (89 bytes)

I transform the integer into a "polynomial" by using a list of digits. I know you say you can't accept that, but I don't see why not since it uses the mathematical concept of numbers being represented as polynomials of their bases. It will only fail when the integer passed in is `0`, but you said no padded zeroes ;)

```
import sys;v=sys.argv;p,x,n=[],int(v[1]),int(v[2])
while x:p=[x%10]+p;x//=10
print p[n-1]

```

Run as `test.py`:

```
$ python test.py 726489 5
8

```

I assume you wanted shell input and that I couldn't make use of the fact that the input would be strings. Skipping shell input it's just 43 bytes, with:

```
p=[]
while x:p=[x%10]+p;x//=10
print p[n-1]

```

Although I use some unnecessary iteration, I save some bytes by not adding an additional decrement on `n`.
> 0 votes

# Answer
# Extended BrainFuck: 49

```
+[>>,32-]<<-[<<-],49-[->>>[>>]+[<<]<]>>>[>>]<33+.

```

Usage:

```
% bf ebf.bf < nth-digit.ebf > nth-digit.bf
% echo "112234567 7" | bf nth-digit.bf
5

```

I'm not ectually using any special features of EBF except the multiplication operator (eg. `10+ => ++++++++++`). Other than that it's mostly pure BrainFuck

How it works:

```
+                ; Make a 1 in the first cell
[>>,32-]         ; while cell is not zero: read byte 2 to the right and reduce by 32 (space)
<<-[<<-]         ; move back to the first cell by reducing every cell with 1
,49-             ; read index, reduce by 49 so that ascii 1 becomes 0
[->>>[>>]+[<<]<] ; use that to fill a trail of breadcrumbs to the desired number
>>>[>>]          ; follow the breadcrumbs
<33+.            ; go to value part, increase by 33 (32 + 1 which we substracted) and print

```

# Scheme (R6RS): 100 (without unnecessary whitespace)

```
(let*((x(read))(n(read))(e(expt 10(-(floor(+(/(log x)(log 10))1))n))))
  (exact(div(mod x(* e 10))e)))

```
> 0 votes

# Answer
# awk - 53

```
{for(d=10^9;!int($1/d)||--$2;d/=10);$0=int($1/d)%10}1

```
1. trim digits by division, starting with max possible for 32 bit unsigned int
2. when we hit the left side of the integer, int($1 / d) returns non-zero
3. continue n ($2) digits past that

Ungolfed:

```
{
    for(d = 1000000000; int($1 / d) != 0 || --$2; d /= 10);
    print int($1 / d) % 10;
}

```
> 0 votes

# Answer
# Scala (83)

Does not use any Scala special features. Rather the standard solution.

```
def f(x:Int,n:Int)=if(x==0)0 else x/(math.pow(10,math.log10(x).toInt-n+1)).toInt%10

```

Ungolfed:

```
def f(x:Int,n:Int) =
  if(x==0)
    0
  else
    x / (math.pow(10, math.log10(x).toInt - n + 1)).toInt % 10

```
> 0 votes

# Answer
# Julia 37

```
d(x,y)=div(x,10^int(log10(x)-y+1))%10

```

Owing to the builtin ^ operator. Arbitrary precision arithmetic allows for any size int.

Sample

```
julia> d(1231198713987192871,10)
3

```
> 0 votes

# Answer
## perl (slightly more mathy/not very golfy) - 99 chars

```
 ~/$ cat ndigits2.pl
  ($n,$i)=@ARGV;
  $r=floor($n/10**(floor(log($n)/log(10)+1)-$i));
  print int(.5+($r/10-floor($r/10))*10);

```

Run it as:

```
 perl -M5.010 -MPOSIX=floor ndigits.pl 726433 1

```
> 0 votes

# Answer
## Perl6 - 85 chars

```
my ($n,$i)=@*ARGS;
my$r=$n/10**(log10($n).round-$i);
say (($r/10-floor($r/10))*10).Int;

```
> 0 votes

# Answer
# Smalltalk, 44

Although dc is unbeatable, here is a Smalltalk solution:

arguments, n number; d digit-nr to extract:

```
[:n :d|(n//(10**((n log:10)ceiling-d)))\\10]

```
> 0 votes

---
Tags: code-golf, math
---


title: Modifiable quine

text:
# Question
Title: Modifiable quine
For this challenge, write program `A` that when given no input, prints the code for `A` (a quine), but when given input, the output will be modified. The input for `A` will be 0 or more statements in whichever language `A` is programmed. The output of `A` will be the code for program `B` which runs the input to `A` and then does the function of `A`. If the input to `A` ends with a comment, then `B` will only run the input of `A`.

---

Example: (assume that the source is `main=makeAQuine` in Haskell)

*

input: none

output: `main=makeAQuine`

*

input: `putStrLn"Hello, world!"`

output: `main=putStrLn"Hello, world!">>makeAQuine`

*

input: `{-`

output: `main=return`

*

input: `putStr"Hello, world!!"{-`

output: `main=putStr"Hello, world!!"`

---

Whoever has the fewest bytes/chars wins, but you can subtract 20 from your count for each of

* Comment Freindly: Accepts line-comments *and* block-comments
* Multiline Input: Accepts more than one statement as input

# Answer
> 1 votes
# Python, 83 (- Comment Bonus)

```
import sys;v=sys.argv
for a in v[1:]:print(a)
if v[-1].find('#')>=0:quit()
print(open(__file__).read())

```

If the source is ASCII and line endings are '\n', it's 103 bytes long.

There are issues that make me unsure about how many comment bonus points it would get, or if it's a complete answer at all.

* it uses '#' to detect a comment in the last argument, which:
    + only detects line comments
    + detects '#' as a comment even if it's inside a string, which is wrong.
* if the arguments contain an unfinished string comment (which, if triple-quoted, is as close as it gets to a block comment), running B indeed will only execute A's input, but then finish with a SyntaxError.

It does, however, accept an arbitrary number of input statements, so it gets at least 20 bonus if it is a valid answer.

# Answer
> 1 votes
# Befunge '98, 74

There are no comments in Befunge, so I guess I can't subtract those 20. On the other hand, you can pass as many Befunge statements as you like, so I get that 20. Actual length of the code is 94.

```
0>:#;1+:0gff2++-#;_01-0pac+:y+>:#;1+:y#;_1->:#;1+::y:!j,#;_#;1+:y\1-\#;_0>:0#;g,1+:01-0g`!#;_@

```

Two things to note:

* if the input contains spaces, program B will not behave correctly, because the first part of A scans east from (0,0) until it finds a space, to determine the code's length. You can pass several arguments separated by spaces, but no arguments containing spaces like "why not".
* Befunge is a 2D language, but this quine only handles linear input correctly. With 2D input, B will only be able to execute A if the input ends at its last line, execution flowing east. Even then, A in B will only output the first line of B.
However, AFAIK it's not possible to pass command line arguments containing newlines?

Using one character more (and a LOT of time and memory), we can instead scan west until we wrap around and find the eastern-most non-space, which produces correct (but equally slow) B even if A gets input containing spaces:

```
0>:#;1-:0gff2++-!#;_01-0pac+:y+>:#;1+:y#;_1->:#;1+::y:!j,#;_#;1+:y\1-\#;_0>:0#;g,1+:01-0g`!#;_@

```

## Explanation:

1. `0>:#;1+:0gff2++-#;_` ensures that a 0 is on top of the stack, duplicates TOS, skips the `;`, increments TOS, gets cell (TOS, 0), subtracts 32 (`' '`) from its content, skips the next `;`, turns west if not 0 (was not a space). Heading west, it skips over `:#;...;` and turns back east at the `>`.
2. `01-0pac+:y+` puts the determined length to cell (-1, 0), calculates 22 and executes `y` to get the number of stacks, adds that to the 22, resulting in the correct argument to `y` for obtaining the size of the top-most stack, after which `y` would return the args. Using this method, B will operate correctly even if B creates more stacks before A in B executes.
3. `>:#;1+:y#;_1-` duplicates the incremented previous result (now pointing to the first char of args), gets a char using `y`, and repeats until that char is '\0'. This is to skip the first argument (which is the file name of the program). Finally, it decrements the counter so that the following code will find the same '\0' again.
4. `>:#;1+::y:!j,#;_` does much the same thing as step 3.), ie. it reads one argument through `y`, but it prints each char of it except the delimiting '\0'.
5. `#;1+:y\1-\#;_` checks if there follows another '\0' and in case there isn't, it decrements the counter so that the first character of each argument doesn't get truncated, and goes west, skipping over `:#;...;_#;...;`, back to step 4.)
6. ```
0>:0#;g,1+:01-0g`!#;_@
```
initializes a new TOS counter to 0, then enters a loop to get cell (TOS, 0), print it, increment the counter, get cell (-1, 0) and terminate if that's less than the counter, else repeat.

# Answer
> 0 votes
## JavaScript, 25

65 characters, minus 40 bonus points. Complete with abuse of `escape`! \o/

```
(_=$=>eval(prompt()+";alert(unescape('(_="+escape(_)+")()'))"))()

```

But for fewer characters, shell is always good.

## zsh, −28

```
cat|zsh
<$0

```

# Answer
> -1 votes
## GTB, 12

```
`_~_+":prgmA

```

---
Tags: code-golf, quine
---


title: Thwarting the Fry King

text:
# Question
Title: Thwarting the Fry King
## Setting

The Fry King is a small criminal mastermind from the western european nation of Belgium, more specifically Flanders. He has acquired every single fastfood restaurant in a large part of Belgium and set them out on a 101X49 grid (102 intersections horizontally, 50 vertically, including the borders), 5100 restaurants in total located on the intersections. The next step in his diabolical plan is to orchestrate the closing hours of these restaurants so that on any one day of the year (bar 2 explained later), only 1 corner of each square will have an open restaurant.

Example with a 6X2 grid:

```
1---2---3---4---1---2
|   |   |   |   |   |
3---4---1---2---3---4

```

A year has 365 days. On the first Monday of the year, only the restaurants with number 1 will be open. On the next day, Tuesday, only those with the number 2. On the next day, Wednesday, only those with number 3. On the next day, Thursday, only those with number 4. after that, it starts again at 1. The days before the first Monday count back. For example, if the first Monday falls on January 3rd, the Sunday before the 4s will be open. This might mean that when the year changes, a store might be open twice or might be skipped in the rotation.

There are 2 exceptions: the 21st of July is the national holiday. All restaurants are open. Another is the 29th of February. Because this is the Fry King's birthday, all restaurants are also open. These exceptions replace a normal day, so if the 20th is for the restaurant with number 1, the 22nd is for the joints with number 3.

## Assignment

You are a vigilante coder who has setup a toll-free texting number. It accepts 3 values, delimited by an \*: A number between 1 and 101 denoting the column value you're in, a number between 1 and 49 to denote the row number you're in (these 2 determine which joints are eligible) and a date in the format of DD/MM/YYYY (day/month/year). The number returns 2 letters indicating which corner of your square contains today's open restaurant (NW-NE-SE-SW). If there are multiple options, it returns the first eligible one from the previous series.

## Example:

Input

```
1*1*06/01/2014

```

Output

```
NW

```

Input:

```
2*1*20/01/2014

```

Output

```
NE

```

Calculation is code golf. Shortest code in bytes wins. There are no special bonuses to win or limitations involved, apart from 1: no external resources.

# Answer
> 4 votes
# Python 2 (228 209 208 207)

(not counting the last newline)

```
import time
s=time.strptime
f=raw_input().split('*')
t=s(f[2],"%d/%m/%Y")
if t[1:3]in[(2,29),(7,21)]:t=s("%s%s"%(t[0],t[7]-1),"%Y%j")
print"NNSSWEWE"[(t[7]+s(str(t[0]),"%Y")[6]-int(f[0])-int(f[1])*2+3)%4::4]

```

**Edits:**

* substituted variables that were used only once, further golfed the print statement.
* Removed the space after print as isaacg suggested.
* Changed `from time import*;s=strptime` to `import time;s=time.strptime` to shave off one extra byte

# Answer
> 0 votes
# Mathematica: 272

```
S=ToExpression
T=StringSplit
{a,b,c}=T[i,"*"]
{d,m,y}=S@T[c,"/"]
{{e}}=Position[DayOfWeek[{y,m,#}]&/@Table[i,{i,7}],Monday]
{o,p,q}=DateDifference[Join[{y},#],{y,m,d}]&/@{{1,e},{7,21},{2,29}}
{"NW","SE","SW","NE"}[[1+If[p==0||q==0,0,Mod[2*Mod[S@b-1,2]+Mod[S@a-1,4]+o,4]]]]

```

Assumes that the input string is in a variable named `i` like so (perhaps add 4 chars for `i=""`?):

```
i = "2*1*20/01/2014"

```

Also I leave the following out of the character count (perhaps add 18 for that):

```
Needs["Calendar`"]

```

And the trailing `;` on each of the non-output lines (perhaps add 9 for those). Below is a slightly ungolfed version of the code for testing/editing:

```
i = "2*1*20/01/2014";
Needs["Calendar`"];
R = Mod[#, 4] &;
S = ToExpression;
T = StringSplit;
{a, b, c} = T[i, "*"];
{d, m, y} = S@T[c, "/"];
{{e}} = Position[DayOfWeek[{y, m, #}] & /@ Table[i, {i, 7}], Monday];
{o, p, q} = DateDifference[Join[{y}, #], {y, m, d}] & /@ {{1, e}, {7, 21}, {2, 29}};
{"NW", "SE", "SW", "NE"}[[1 + If[p == 0 || q == 0, 0, Mod[2*Mod[S@b - 1, 2] + Mod[S@a - 1, 4] + o, 4]]]]

```

---
Tags: code-golf, date, grid
---


title: Line up the CSV

text:
# Question
Title: Line up the CSV
### Overview:

Your job is to take CSV input in `key=value` format and line it up in a more organized (see below) way.

### Input:

Always via **stdin**. Records will always be in the following form `key=value`:

```
foo=bar,baz=quux
abc=123,foo=fubar
baz=qwe,abc=rty,zxc=uiop,foo=asdf

```
* There will be no list of possible keys in advance, you must find them in the input text.
* End of input will be signalled by `EOF`, whatever implementation of `EOF` is appropriate for your OS.

### Output:

The first row of your output will be a list of all the keys, in alphabetical order (even if the keys are all numbers). After that, print each record in the same CSV format the appropriate number heading, without the keys listed. So, for the example above, the correct output would be:

```
abc,baz,foo,zxc
,quux,bar,
123,,fubar,
rty,qwe,asdf,uiop

```

### FAQ:

* Do I have to worry about improperly formatted input?
    + No. Your program may do whatever it wants (throw an exception, ignore, etc.) if the input is not correctly formatted, e.g. a line of `foo,bar,baz`
* How do I handle escaping special characters?
    + You may assume that there will be no additional `,` or `=` in the data that are not part of the `key=value` format. `"` does not have any special meaning in this contest (even though it does in traditional CSV).  is also not special in any way.
    + Lines should match the following regex: `^([^=,]+=[^=,]+)(,[^=,]+=[^=,]+)*$`
        - Therefore, both keys and values will match `[^=,]+`
* What about `CRLF` vs. `LF`?
    + You may choose whatever delimiter is appropriate for your platform. Most languages handle this without special delimiting code.
* Do I need to print trailing commas if the last few columns don't exist?
    + Yes. See the example.
* Are CSV parsers or other similar external tools allowed?
    + No. You must parse the data yourself.

# Answer
> 3 votes
### GolfScript, 64 characters

```
n%{','/{'='/}%}%:I{{0=}/}%.&$:K','*n{`{{(2$=*}%''*\;}+K%','*n}I/

```

The code is a straight-forward implementation in GolfScript, you can test the example online.

*Annotated code:*

```
# Split the input into lines, each line into tuples [key, value]
# and assign the result to variable I
n%{','/{'='/}%}%:I

# From each tuple take the 0'th element (i.e the key)
{{0=}/}%

# Take the unique items (.&), sort ($) and assign the result to variable K
.&$:K

# Output: join values with , and append a newline
','*n

# {...}I/: Loop over all lines of the input
{

  # `{...}+K%: Loop over all keys and initially push the current
  # line for each of the keys
  `{
    # stack here is [current key, current line]
    # {}%: map to all the items of the current line
    {
      # extract the key from the current item and compare
      (2$=
      # if equal keep [value], otherwise multiply with 0, i.e. discard
      *
    }%
    # join the results (may be one or zero) and drop the key
    ''*\;
  }+K%
  # Output: join values of current line with , and append a newline
  ','*n
}I/

```

# Answer
> 2 votes
# perl, 129/121

129 bytes, no command line switches:

```
for(<>){push@x,{%g=map{split/=/}split/[,
]/};@h{keys%g}=()}@k=sort keys%h;$"=",";sub P{print"@_
"}P@k;for$x(@x){P map{$$x{$_}}@k}

```

As @Dennis points out below, you can get this to 120+1=121 by using -n:

```
push@x,{%g=map{split/=/}split/[,
]/};@h{keys%g}=()}@k=sort keys%h;$"=",";sub P{print"@_
"}P@k;for$x(@x){P map{$$x{$_}}@k

```

Basically, for each line, we split by commas to get the list of pairs. For each pair, we split by the equals sign to get the key and value. We set the key/value pair in %h and a local hashref. The former is used to determine the list of keys. The latter is used to remember the values for this line.

# Answer
> 2 votes
# Perl 6: 119 characters, 120 bytes

```
my@l=lines.map:{/[(\w+)\=(\w+)]+%\,/;push $!,~«@0;$%(@0 Z=>@1)}
say .join(",") for$!.=sort.=uniq,($(.{@$!}X//"") for@l)

```

De-golfed:

```
my@l=lines.map: {
    # Parse the key=value pairs,
    # put all the keys in $/[0] (or $0)
    # put all the values in $/[1] (or $1)
    / [ (\w+) \= (\w+) ]+ % \, /;

    # Push all the keys into $!
    # (@0 just means @$0 or $/[0].list)
    push $!, ~«@0;

    # Return a hash of keys zipped into pairs with the values
    $%( @0 Z=> @1 )
}

$!.=sort.=uniq;
# …i.e., $! = $!.sort.uniq;

# Print the CSV for the keys ($!),
# followed by the CSVs for the hashes we made for each line,
# as accessed by our sorted key list. (… .{@$!} …)
# If the value doesn't exist, just use "" instead. (… X// "" …)
say .join(",") for $!, ($( .{@$!} X// "" ) for @l)

```

# Answer
> 1 votes
# JavaScript (*ES5*) 191 183 179 168 bytes

Assuming the code is run in spidermonkey command line:

```
for(b=[a={}];l=readline(i=0);b.push(c))for(c={},d=l.split(/,|=/);e=d[i++];)c[a[e]=e]=d[i++];for(;c=b[i++];)print(Object.keys(a).sort().map(function(x){return c[x]})+[])

```

Result:

```
> js test.js < input.txt
abc,baz,foo,zxc
,quux,bar,
123,,fubar,
rty,qwe,asdf,uiop

```

This shim can be used in a browser to simulate spidermonkey's `readline` and `print`:

```
var I = 0, LINES = '\
foo=bar,baz=quux\n\
abc=123,foo=fubar\n\
baz=qwe,abc=rty,zxc=uiop,foo=asdf'.split('\n'),
readline = function(){
    return LINES[I++];
}, print = function(){
    return console.log.apply(console, arguments);
};

```

Ungolfed:

```
a = {};                        // this object holds all keys found
b = [a];                       // array key:value pairs of each line, initialized with our key holder object in position 0
for(;l = readline();){         // store each line in l, loop until blank/undefined line
    c = {};                    // create a new object for this line's key:value pairs
    d = l.split(/,|=/);        // split line by commas and equals
    for(i = 0; e = d[i++];){   // loop through each key
        a[e] = e;              // set the key=key for key holder object
        c[e] = d[i++];         // set key=value for the line object
    }
    b.push(c);                 // push line object onto array
}
for(i = 0; c = b[i++];){       // loop through all line objects until undefined
    print(                     // print line
        Object.keys(a).sort(). // get sorted list of keys
        map(function(x){
            return c[x]        // map values from line object
        })
        + []                   // cast array to string
    );
}

```

# Answer
> 1 votes
# Bash + coreutils, 188 138 bytes

```
p=paste\ -sd,
f=`cat`
h=`tr , '\n'<<<$f|cut -d= -f1|sort -u`
$p<<<"$h"
for l in $f;{
join -o2.2 -a1 - <(tr =, ' \n'<<<$l|sort)<<<"$h"|$p
}

```

Output:

```
$ ./lineupcsv.sh < input.csv
abc,baz,foo,zxc
,quux,bar,
123,,fubar,
rty,qwe,asdf,uiop
$

```

# Answer
> 0 votes
# Haskell, 357 334

```
import Data.List
o=1<2
s u|u==""=""|o=tail u
t=takeWhile
d=dropWhile
c=(/=',')
e=(/='=')
p x|x/=""=Just((t e x,t c.s.d e$x),s.d c$x)|o=Nothing
g=m(unfoldr p).lines
k=nub.sort.(m fst=<<).g
[]#_=[]
(t@(x,u):z)#n@(a,b)|x==a=n:z|o=t:z#n
i=intercalate
main=interact$ \d->i"\n"$(i","$k d):m(i",".m snd.foldl(#)(m(flip(,)"").k$d))(g d)
m=map

```

`g` is doing the parsing - it splits the input into lines and maps each line to a list of `(key,value)` pairs. `k`, by concatenating all the keys into a list and removing duplicates, creates a list with all unique keys which I can later use for sorting. I do this by creating a "Set" inside `main` (`m(flip(,)"").k$d == [("abc",""),("baz",""),("foo",""),("zxc","")]`) for each line, and then taking every `(key,value)` pair from a line and put it where it belongs in the list (`foldl`). Line 1 from the example yields `[("abc",""),("baz","quux"),("foo","bar"),("zxc","")]`, which I concatenate into a single String (`",quux,bar,"`), concatenate with the other lines, and print.

```
>>> csv.exe < input.txt
abc,baz,foo,zxc
,quux,bar,
123,,fubar,
rty,qwe,asdf,uiop

```

# Answer
> 0 votes
# Python 2.7 - 242 bytes

bleh

```
import os
c=[r.split(',')for r in os.read(0,99).split('\n')]
k=sorted(list(set(sum([[s.split('=')[0]for s in r]for r in c],[]))))
print','.join(k)
for l in c:
 t=[''for i in k]
 for s in l:
    o,v=s.split('=')
    t[k.index(o)]=v
 print','.join(t)

```

Note that the second layer of indentation is a single tab character, not four spaces like SE renders it.

Ungolfed:

```
#!/bin/python2

import os

# I do input as a list comprehension in the original but this is equivalent
c = []

# For each line in the input
for r in os.read(0,99).split('\n'):
    # Add a list of key=value pairs in that row to c
    c.append(r.split(','))

# Another thing done as a list comprehension, but I'll space it out
k = []

# For each list of key=value pair s in c
for r in c:
    # For each actual key=value pair in that list
    for s in r:
        # Get the key
        k.append(s.split('=')[0])

# Discard dupes by converting to set and back, then sort
k = sorted(list(set(k)))

# Seperate these keys by commas, then print
print ','.join(k)

# For each line in c
for l in c:
    # t has one empty string for each key in the input
    t = ['' for i in k]
    # For each key=value pair in the line
    for s in l:
        # o = key, v = value
        o, v = s.split('=')
        # Find the position that the key is in the list of keys, then put the
        # value in t at that position
        t[k.index(o)] = v

    # Now each value is in the right position and the keys with no values on this
    # line have an empty string. Join everything with commas and print
    print ','.join(t)

```

# Answer
> 0 votes
## C# - 369

(in LINQPAD)

```
void C(string a){var k=a.Split(new[]{',','\n'}).Select(s=>s.Split('=')[0]).OrderBy(o=>o).Distinct();var t=string.Join(",", k)+"\n";foreach(var x in a.Split('\n')){for(int i=0;i<k.Count();i++){foreach(var y in x.Split(',').OrderBy(o=>o.Split('=')[0]))if(k.ElementAt(i)==y.Split('=')[0])t+=y.Split('=')[1];t+=",";}t=t.Remove(t.LastIndexOf(','),1)+"\n";}Console.Write(t);}

```

**Ungolfed**

```
void C(string a)
{
    var k=a.Split(new[]{',','\n'}).Select(s=>s.Split('=')[0]).OrderBy(o=>o).Distinct();
    var t=string.Join(",", k)+"\n";
    foreach(var x in a.Split('\n'))
    {
        for(int i=0;i<k.Count();i++)
        {
            foreach(var y in x.Split(',').OrderBy(o=>o.Split('=')[0]))
                if(k.ElementAt(i)==y.Split('=')[0])
                    t+=y.Split('=')[1];
            t+=",";
        }
        t=t.Remove(t.LastIndexOf(','),1)+"\n";
    }
    Console.Write(t);
}

```

**Test string input**

```
C("foo=bar,baz=quux\nabc=123,foo=fubar\nbaz=qwe,abc=rty,zxc=uiop,foo=asdf");

```

**Output**

```
abc,baz,foo,zxc
,quux,bar,
123,,fubar,
rty,qwe,asdf,uiop

```

# Answer
> 0 votes
# Python 3: ~~200~~ ~~195~~ ~~192~~ ~~189~~ 187

```
import sys
r=[dict(p.split('=')for p in l[:-1].split(','))for l in sys.stdin]
x=set()
for d in r:x|=d.keys()
k=sorted(x)
for l in[k]+[[r.get(k,'')for k in k]for r in r]:print(*l,sep=',')

```

# Answer
> 0 votes
## k4 (40? 51? 70? 46?)

the basic expression is

```
","0:{(x@<x:?,/?!:'x)#/:x}(!).'"S=,"0:/:

```

this both accepts and returns a list of strings

to match the spec, we could interactively do

```
-1","0:{(x@<x:?,/?!:'x)#/:x}(!).'"S=,"0:/:."\\cat";

```

which accepts the input from stdin and prints the output to stdout

for a standalone app accepting input from a pipe, we could do this:

```
$ cat i.k
.z.pi:{t,:`\:x}
.z.exit:{-1","0:{(x@<x:?,/?!:'x)#/:x}(!).'"S=,"0:/:t}
$ cat i.txt|q i.k
abc,baz,foo,zxc
,quux,bar,
123,,fubar,
rty,qwe,asdf,uiop
$

```

altho if you're willing to consider my pre-existing k-as-filter wrapper, awq.k, as an acceptable tool for this kind of puzzle, then we can do this:

```
$ cat i.txt|awq.k '","0:{(x@<x:?,/?!:'\''x)#/:x}(!).'\''"S=,"0:/:'

```

which is either 46 characters or 40, depending on how you count shell quote wrangling

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


title: Predict where the man will go

text:
# Question
Title: Predict where the man will go
A man lives in the north-west corner `(0, 0)` of a town with height `h` and width `w` . Everyday he walks from his home to the border `(?, w)` or `(h, ?)`. In the following example, the man goes to `(3, 3)` today.

```
(0, 0) +--+  +  +  . (0, 4)
          |
       +  +--+--+  .
                |
       +  +  +  +  .
                |
(3, 0) .  .  .  .  . (3, 4)

```

The man records a bit at each points (`+` in example above). Every time he reaches a point, he goes east if the bit is `1` and south otherwise. The bit is flipped after he leaves. For example:

```
Day 1: 1--0  1  1    Day 2: 0  1  1  1    Day 3: 1--1--1--1--  Day 4: 0  0  0  0
          |                 |                                         |
       0  1--0  0           0  0  1  0           1  0  1  0           1--0  1  0
             |              |                                            |
       1  0  1--0           1--0  0  1           0  1  0  1           0  1--0  1
                |              |                                            |
Destination: (3, 3)  Destination: (3, 1)  Destination: (0, 4)  Destination: (3, 2)

```

Given the size of the town and the man's record, calculate the man's destination after `n` days.

### Input:

In the first line are three integers, `h`, `w` and `n`.

In the following `h` lines are `w` integers, denoting the man's record.

`h <= 1000, w <= 1000, n <= 1000000000`

### Output:

Two integers, denoting the man's destination after `n` days.

### Sample Input:

```
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

```

### Sample Output:

```
0 4

```

### Sample Code:

```
#include <iostream>
using namespace std;
bool d[1000][1000];
int main(){
    int h, w, n;
    cin >> h >> w >> n;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            cin >> d[i][j];
    int i, j;
    while(n--)
        for(i = 0, j = 0; i < h && j < w;){
            bool &b = d[i][j];
            d[i][j] ? j++ : i++;
            b = !b;
        }
    cout << i << " " << j << endl;
}

```

### Scoring:

* Lowest byte count in UTF-8 wins.
* If the running time of your code is independent of `n`, reduce your score by 50%.
    + **Don't** just calculate the results of all 1000000000 days or do anything similarly stupid to get this bonus. Find an efficient algorithm!

# Answer
> 7 votes
### GolfScript, 52.5 (105 characters with 50% bonus)

```
~](;(\((2$(1,*+\@/{]zip 0\{~@@+.2$!+2/\@+.2/\@[\1&]}%zip~@;}%\;[{.0=0=\1${{1>}%}{1>}if.{~}%}do;].1-,n@0-,

```

The version is very efficient and can be tested online even for large values.

It uses an approach similar to user2357112's solution.

# Answer
> 13 votes
## Python 2, 192 bytes * 0.5 bonus = 96

To solve this problem efficiently, the key realization is that we can compute how many times each cell is visited based on the number of times the cells above and to the left are visited, without needing to determine the exact paths taken. Effectively, we simulate `n` trips at once and keep track of how many times each cell is used.

Substantial improvement due to push-based approach inspired by johnchen902's solution:

```
r=lambda:map(int,raw_input().split())
h,w,n=r()
v=[n]+w*[0]
x=y=0
for i in range(h):
 for j,b in enumerate(r()):
    if i-x==j-y==0:d=v[j]&1^b;x+=d;y+=1^d
    f=v[j]+b>>1;v[j]-=f;v[j+1]+=f
print x,y

```

Previous, pull-based implementation:

```
r=lambda i:map(int,raw_input().split())
h,w,n=r(0)
x=range(h)
g=map(r,x)
v=[w*[0]for i in x]
v[0][0]=n-1
for i in x:
 for j in range(w):v[i][j]+=(i and(v[i-1][j]+(1^g[i-1][j]))/2)+(j and(v[i][j-1]+g[i][j-1])/2)
i=j=0
while i<h and j<w:f=g[i][j]^v[i][j]&1;j+=f;i+=1^f
print i,j

```

Original, ungolfed version:

```
h, w, n = map(int, raw_input().split())
grid = [map(int, raw_input().split()) for i in xrange(h)]

# Determine the number of times each cell was visited in the first n-1 trips
visits = [[0]*w for i in xrange(h)]
visits[0][0] = n-1
for i in xrange(h):
    for j in xrange(w):
        if i:
            # Count visits from above cell
            visits[i][j] += (visits[i-1][j] + (not grid[i-1][j])) // 2
        if j:
            # Count visits from left cell
            visits[i][j] += (visits[i][j-1] + grid[i][j-1]) // 2

# Flip the bits corresponding to each cell visited an odd number of times
for i in xrange(h):
    for j in xrange(w):
        grid[i][j] ^= visits[i][j] & 1

# Figure out where the final trip ends
i = j = 0
while i < h and j < w:
    if grid[i][j]:
        j += 1
    else:
        i += 1

print i, j

```

# Answer
> 8 votes
# Ruby, ~~159~~ 143

```
n,*l=$<.read.split$/
i=->a{a.split.map &:to_i}
x=y=l.map!{|k|i[k]}
(n=i[n])[-1].times{x=y=0
(x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}
p x,y

```

The first line uses the `*` operator to grab the first line of input in one variable, and the rest of the input in another. Then an `i` function is defined to convert `"1 2 3 4"` into `[1, 2, 3, 4]`, which is applied to both `l` and `n`. (`x` and `y` are saved for later.)

`n[-1]` is the last element of `n`, so the following block (the simulation) is executed that many times. First, `x` and `y` are initialized to zero (they are declared outside the block so that their scope is large enough), and then the simulation line is executed, ~~which is pretty self-explanatory, but here's some commentary anyway:~~

~~```
l[x][y]<1?            is it zero (less than one)?
x+=l[x][y]=1          if it's zero, set it to one, and (conveniently) we can add that to x
:y+=(l[x][y]=0)+1     otherwise, set it to zero, add one, and add that to y
 while x<n[0]&&y<n[1] keep doing this while we're still inside the array

```~~

Edit: new simulation line provided by Howard, thanks! I'm pretty sure I understand how it works but I don't have time to add an explanation, so one will be added later.

Finally, `p x,y` outputs the numbers, and we are done!

# Answer
> 4 votes
# Delphi XE3 (437 bytes|| 897874 without bonus counted)

When thinking about how to solve this with the bonus I thought of the following.
If you walk 4 days cell 0,0 is changed 4 times. The cell on its right is changed twice aswell as the cell beneath it.
If there is an uneven number of days and the number in the cell starts with 1 the cell on the right gets one more than the cell beneath, and the other way around if the cell is 0.

By doing this for every cell you can see if the end value should be changed by: Cell was changed X times. if X mod 2\>0 then change the cell.

Results in the following code:
**{Whispers at JohnChen902} do I get your upvote now? :P**

```
uses SysUtils,Classes,idglobal;var a:TArray<TArray<byte>>;b:TArray<TArray<int64>>;h,w,x,y,t:int16;n:int64;s:string;r:TStringList;tra:byte;begin r:=TStringList.Create;readln(h,w,n);h:=h-1;w:=w-1;for y:=0to h do begin readln(s);r.Add(StringReplace(s,' ','',[rfReplaceAll]));end;SetLength(a,h);SetLength(b,h);for y:=0to h do begin SetLength(a[y],w);SetLength(b[y],w);for x:=1to Length(r[y])do a[y][x-1]:=Ord(r[y][x])-48;end;b[0][0]:=n-1;for Y:=0to h do for X:=0to w do begin t:=b[y][x];if x<w then b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);if y<h then b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);end;for Y:=0to h do for X:=0to w do if b[y][x]mod 2=1then a[y][x]:=iif(a[y][x]=1,0,1);y:=0;x:=0;repeat a[y][x]:=iif(a[y][x]=1,0,1);if a[y][x]=1then inc(y) else inc(x);until(y>h)or(x>w);write(Format('%d %d',[y,x]));end.

```

### Ungolfed

```
uses
  SysUtils,Classes,idglobal;
var
  a:TArray<TArray<byte>>;
  b:TArray<TArray<int64>>;
  h,w,x,y,t:int16;
  n:int64;
  s:string;
  r:TStringList;
  tra:byte;
begin
  r:=TStringList.Create;
  readln(h,w,n);
  h:=h-1;w:=w-1;
  for y:=0to h do
  begin
    readln(s);
    r.Add(StringReplace(s,' ','',[rfReplaceAll]));
  end;
  SetLength(a,h);
  SetLength(b,h);
  for y:=0to h do
  begin
    SetLength(a[y],w);
    SetLength(b[y],w);
    for x:=1to Length(r[y])do
      a[y][x-1]:=Ord(r[y][x])-48;
  end;
  b[0][0]:=n-1;
  for Y:=0to h do
    for X:=0to w do
    begin
      t:=b[y][x];
      if x<w then
        b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);
      if y<h then
        b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);
    end;
  for Y:=0to h do
    for X:=0to w do
      if b[y][x]mod 2=1then
        a[y][x]:=iif(a[y][x]=1,0,1);
  y:=0;x:=0;
  repeat
    a[y][x]:=iif(a[y][x]=1,0,1);
    if a[y][x]=1then
      inc(y)
    else
      inc(x);
  until(y>h)or(x>w);
  write(Format('%d %d',[y,x]));
end.

```

# Answer
> 4 votes
# C++ 213 bytes * 0.5 = 106.5

Here is my solution. It's similar to user2357112's solution, but there are several difference:

* First, I *dispatch* visiting times to the right and bottom, instead of compute them from the top and left.
* Second, I do everything (reading input, dispatching, tracking the man's location) simultaneously.
* Third, I keep only one row of memory.

```
#include <iostream>
int o[1001],h,w,r,c,i,j,t,u;int main(){std::cin>>h>>w>>*o;for(;i<h;i++)for(j=0;j<w;)std::cin>>t,u=o[j],o[j]/=2,u%2&&o[j+t]++,r-i|c-j||((u+t)%2?r:c)++,o[++j]+=u/2;std::cout<<r<<" "<<c<<"\n";}

```

Here is the ungolfed version:

```
#include <iostream>
using namespace std;
int o[1001];
int main(){
    int h, w, n;
    cin >> h >> w >> n;
    o[0] = n;
    int r = 0, c = 0;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            bool t;
            cin >> t;
            int u = o[j];
            o[j + 1] += u / 2;
            o[j] = u / 2;
            if(u % 2)
                (t ? o[j + 1] : o[j])++;
            if(r == i && c == j)
                ((u + t) % 2 ? r : c)++;
        }
    cout << r << " " << c << endl;
}

```

# Answer
> 3 votes
# Python, 177 bytes

My first try ever in Code Golfing, so sorry if I got something wrong here! Code used to grab the input based on user2357112's code.

```
l=lambda:map(int,raw_input().split())
h,w,n=l()
m=[l() for i in[1]*h]
while n>0:
 n-=1;x=y=0
 while x!=w and y!=h:
  if m[y][x]>0:m[y][x]=0;x+=1
  else:m[y][x]=1;y+=1
print y,x

```

Input:

```
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

```

Output:

```
0 4

```

# Answer
> 2 votes
# R, 196 bytes * 0.5 = 98

```
f=function(h,w,n,x){I=J=rep(1,n);for(i in 1:h)for(j in 1:w){M=which(I==i&J==j);N=length(M);if(N){z=seq(1,N,by=2);if(x[i,j])z=-z;f=M[-z];s=M[z];I[f]=i;J[f]=j+1;I[s]=i+1;J[s]=j}};cat(I[n]-1,J[n]-1)}

```

Ungolfed:

```
f=function(h,w,n,x) {
  I = J = rep(1,n)

  for(i in 1:h) for(j in 1:w) {
    M = which(I==i&J==j)
    N = length(M)
    if (N) {
      z = seq(1,N,by=2)
      if (x[i,j]) z = -z
      f = M[-z]
      s = M[z]
      I[f] = i
      J[f] = j+1
      I[s] = i+1
      J[s] = j
    }
  }
  cat(I[n]-1, J[n]-1)
}

```

Usage:

```
f(3,4,4,matrix(c(1,0,1,0,1,0,1,0,1,1,0,0),3))
3 2

```

---
Tags: code-golf, simulation
---


# Question
Title: Build a minifloat adding machine using NAND logic gates
A minifloat is a binary representation of a floating-point number that has very few bits.

The minifloat in this question will be defined as an 6-bit number `m`, which has the following representation:

* 1 bit to repesent the sign of the number. This bit will be `0` if the number is positive, and `1` if the number is negative.
* 3 bits to represent the exponent of the number, offset by `3` (i.e. an exponent of `110` actually represents a factor of 23, not 26).

+ An exponent of `000` refers to a subnormal number. The mantissa refers to the fractional part of a number with an integer part of `0` multiplied by a factor of the lowest possible exponent (in this case, 2-2).
* 2 bits to represent the mantissa of the number. If the exponent is anything other than `000` or `111`, the 2 bits represent the fractional part after a `1`.

+ An exponent of `111` represents `infinity` if the mantissa is `0`, and `NaN` (not a number) otherwise.

In the Wikipedia article, this would be referred to as a (1.3.2.3) minifloat.

Some examples of this minifloat's representation:

```
000000 =  0.00 = 0
000110 =  1.10 × 2^(1-3) = 0.375
001100 =  1.00 × 2^(3-3) = 1
011001 =  1.01 × 2^(6-3) = 10
011100 = infinity
011101 = NaN
100000 = -0.00 = -0
100011 = -0.11 × 2^(1-3) = -0.1875 (subnormal)
101011 = -1.11 × 2^(2-3) = -0.875
110100 = -1.00 × 2^(5-3) = -4
111100 = -infinity
111111 = NaN

```

Your task is to build a network of two-input NAND gates that takes 6 inputs representing a minifloat `a` and 6 inputs representing a minifloat `b`, and returns 6 outputs representing the minifloat `a + b`.

* Your network must properly add subnormals. For example, `000001` \+ `000010` must equal `000011`, and `001001` \+ `000010` = `001010`.
* Your network must add and subtract infinities properly. Anything finite added to an infinity is the same infinity. Positive infinity plus negative infinity is `NaN`.
* A `NaN` plus anything must equal a `NaN`, although which `NaN` it equals is up to you.
* How you handle adding positive zero and negative zero to each other is up to you, although zero plus zero must equal zero.

Your network can implement any of the following rounding rules depending on convenience:

* Round down (toward negative infinity)
* Round up (toward positive infinity)
* Round toward zero
* Round away from zero
* Round to nearest, with halves rounded according to any of the above rules

To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

* `NOT: 1`
* `AND: 2`
* `OR: 3`
* `XOR: 4`

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to correctly implement all the above requirements wins.

# Answer
> 12 votes
# 830 NANDs

It uses **24** NOTs, **145** ANDs, **128** ORs, **33** XORs. It always rounds towards zero, it may return either -0 or +0 for zero values, and I believe it treats Infinities and NaNs correctly:

* ± INF ± INF = ± INF
* ± INF + NaN = ± INF
* ± INF ∓ INF = NaN
* ± INF + *number* = ± INF
* NaN + NaN = NaN
* NaN + *number* = NaN

Below I have a coded representation of the circuit. I have little experience annotating these types of things, so I don't really know what the typical way to do this is, but every variable is a Boolean so it's clear to see that it describes a circuit. Another thing, I have neither the know-how nor probably the tenacity to try and make a diagram of this, but if there is any easy to use software out there anyone wants to point out I would be interested in taking a look.

```
a0,a1,a2,a3,a4,a5 = mini0
b0,b1,b2,b3,b4,b5 = mini1

neg = XOR(a0,b0)
nneg = NOT(neg)

na1 = NOT(a1)
na2 = NOT(a2)
na3 = NOT(a3)

a2_a3 = AND(a2,a3)
a2_na3 = AND(a2,na3)
na2_a3 = AND(na2,a3)
na2_na3 = AND(na2,na3)

a123 = AND(a1,a2_a3)
l0 = AND(a1,a2_na3)
l1 = AND(a1,na2_a3)
l2 = AND(a1,na2_na3)
l3 = AND(na1,a2_a3)
l4 = AND(na1,a2_na3)
l5 = AND(na1,na2_a3)
l6 = AND(na1,na2_na3)

a45 = OR(a4,a5)
a_nan = AND(a123,a45)
a_inf = AND(a123,NOT(a45))

m0 = l0
m1 = OR(l1,AND(l0,a4))
m2 = OR(l2,OR(AND(l1,a4),AND(l0,a5)))
m3 = OR(l3,OR(AND(l2,a4),AND(l1,a5)))
m4 = OR(l4,OR(AND(l3,a4),AND(l2,a5)))
m5 = OR(l5,OR(AND(l4,a4),AND(l3,a5)))
l5_l6 = OR(l5,l6)
m6 = OR(AND(l4,a5),AND(l5_l6,a4))
m7 = AND(l5_l6,a5)

nb1 = NOT(b1)
nb2 = NOT(b2)
nb3 = NOT(b3)

b2_b3 = AND(b2,b3)
b2_nb3 = AND(b2,nb3)
nb2_b3 = AND(nb2,b3)
nb2_nb3 = AND(nb2,nb3)

b123 = AND(b1,b2_b3)
k0 = AND(b1,b2_nb3)
k1 = AND(b1,nb2_b3)
k2 = AND(b1,nb2_nb3)
k3 = AND(nb1,b2_b3)
k4 = AND(nb1,b2_nb3)
k5 = AND(nb1,nb2_b3)
k6 = AND(nb1,nb2_nb3)

b45 = OR(b4,b5)
b_nan = AND(b123,b45)
b_inf = AND(b123,NOT(b45))

n0 = k0
n1 = OR(k1,AND(k0,b4))
n2 = OR(k2,OR(AND(k1,b4),AND(k0,b5)))
n3 = OR(k3,OR(AND(k2,b4),AND(k1,b5)))
n4 = OR(k4,OR(AND(k3,b4),AND(k2,b5)))
n5 = OR(k5,OR(AND(k4,b4),AND(k3,b5)))
k5_k6 = OR(k5,k6)
n6 = OR(AND(k4,b5),AND(k5_k6,b4))
n7 = AND(k5_k6,b5)

first = n0,n1,n2,n3,n4,n5,n6,n7

i7 = n7
i6 = XOR(n6,n7)
carry_6 = OR(n6,n7)
i5 = XOR(n5,carry_6)
carry_5 = OR(n5,carry_6)
i4 = XOR(n4,carry_5)
carry_4 = OR(n4,carry_5)
i3 = XOR(n3,carry_4)
carry_3 = OR(n3,carry_4)
i2 = XOR(n2,carry_3)
carry_2 = OR(n2,carry_3)
i1 = XOR(n1,carry_2)
carry_1 = OR(n1,carry_2)
i0 = XOR(n0,carry_1)
i_sign = OR(n0,carry_1)

n7 = OR(AND(nneg,n7),AND(neg,i7))
n6 = OR(AND(nneg,n6),AND(neg,i6))
n5 = OR(AND(nneg,n5),AND(neg,i5))
n4 = OR(AND(nneg,n4),AND(neg,i4))
n3 = OR(AND(nneg,n3),AND(neg,i3))
n2 = OR(AND(nneg,n2),AND(neg,i2))
n1 = OR(AND(nneg,n1),AND(neg,i1))
n0 = OR(AND(nneg,n0),AND(neg,i0))
n_sign = AND(neg,i_sign)

r7 = XOR(m7,n7)
carry_7 = AND(m7,n7)
hr6 = XOR(m6,n6)
hcarry_6 = AND(m6,n6)
r6 = XOR(hr6,carry_7)
carry_6 = OR(hcarry_6,AND(hr6,carry_7))
hr5 = XOR(m5,n5)
hcarry_5 = AND(m5,n5)
r5 = XOR(hr5,carry_6)
carry_5 = OR(hcarry_5,AND(hr5,carry_6))
hr4 = XOR(m4,n4)
hcarry_4 = AND(m4,n4)
r4 = XOR(hr4,carry_5)
carry_4 = OR(hcarry_4,AND(hr4,carry_5))
hr3 = XOR(m3,n3)
hcarry_3 = AND(m3,n3)
r3 = XOR(hr3,carry_4)
carry_3 = OR(hcarry_3,AND(hr3,carry_4))
hr2 = XOR(m2,n2)
hcarry_2 = AND(m2,n2)
r2 = XOR(hr2,carry_3)
carry_2 = OR(hcarry_2,AND(hr2,carry_3))
hr1 = XOR(m1,n1)
hcarry_1 = AND(m1,n1)
r1 = XOR(hr1,carry_2)
carry_1 = OR(hcarry_1,AND(hr1,carry_2))
hr0 = XOR(m0,n0)
hcarry_0 = AND(m0,n0)
r0 = XOR(hr0,carry_1)
carry_0 = OR(hcarry_0,AND(hr0,carry_1))
r_sign = XOR(n_sign,carry_0)

s7 = r7
s6 = XOR(r6,r7)
carry_6 = OR(r6,r7)
s5 = XOR(r5,carry_6)
carry_5 = OR(r5,carry_6)
s4 = XOR(r4,carry_5)
carry_4 = OR(r4,carry_5)
s3 = XOR(r3,carry_4)
carry_3 = OR(r3,carry_4)
s2 = XOR(r2,carry_3)
carry_2 = OR(r2,carry_3)
s1 = XOR(r1,carry_2)
carry_1 = OR(r1,carry_2)
s0 = XOR(r0,carry_1)

n_r_sign = NOT(r_sign)
r0 = OR(AND(n_r_sign,r0),AND(r_sign,s0))
r1 = OR(AND(n_r_sign,r1),AND(r_sign,s1))
r2 = OR(AND(n_r_sign,r2),AND(r_sign,s2))
r3 = OR(AND(n_r_sign,r3),AND(r_sign,s3))
r4 = OR(AND(n_r_sign,r4),AND(r_sign,s4))
r5 = OR(AND(n_r_sign,r5),AND(r_sign,s5))
r6 = OR(AND(n_r_sign,r6),AND(r_sign,s6))
r7 = OR(AND(n_r_sign,r7),AND(r_sign,s7))

h0 = r0
rest = h0
h1 = AND(r1,NOT(rest))
rest = OR(rest,h1)
h2 = AND(r2,NOT(rest))
rest = OR(rest,h2)
h3 = AND(r3,NOT(rest))
rest = OR(rest,h3)
h4 = AND(r4,NOT(rest))
rest = OR(rest,h4)
h5 = AND(r5,NOT(rest))
rest = OR(rest,h5)
h6 = AND(r6,NOT(rest))
rest = OR(rest,h6)
h7 = AND(r7,NOT(rest))

e0 = OR(h0,OR(h1,h2))
e1 = OR(h0,OR(h3,h4))
e2 = OR(h1,OR(h3,h5))

ne0 = NOT(e0)
ne1 = NOT(e1)
ne2 = NOT(e2)

e0e1 = AND(e0,e1)
e0ne1 = AND(e0,ne1)
ne0e1 = AND(ne0,e1)
ne0ne1 = AND(ne0,ne1)

x0 = AND(e0e1,  ne2)
x1 = AND(e0ne1, e2 )
x2 = AND(e0ne1, ne2)
x3 = AND(ne0e1, e2 )
x4 = AND(ne0e1, ne2)
x5 = AND(ne0ne1,e2 )
x6 = AND(ne0ne1,ne2)

u0 = AND(x0,r1)
u1 = AND(x1,r2)
u2 = AND(x2,r3)
u3 = AND(x3,r4)
u4 = AND(x4,r5)
u5 = AND(x5,r6)
u6 = AND(x6,r6)

v0 = AND(x0,r2)
v1 = AND(x1,r3)
v2 = AND(x2,r4)
v3 = AND(x3,r5)
v4 = AND(x4,r6)
v5 = AND(x5,r7)
v6 = AND(x6,r7)

f0 = OR(u0,OR(u1,OR(u2,OR(u3,OR(u4,OR(u5,u6))))))
f1 = OR(v0,OR(v1,OR(v2,OR(v3,OR(v4,OR(v5,v6))))))
sign = XOR(a0,r_sign)

either_nan = OR(a_nan,b_nan)
either_inf = OR(a_inf,b_inf)
ans_nan = OR(AND(AND(a_inf,b_inf),XOR(a0,b0)),AND(NOT(either_inf),either_nan))
nans_nan = NOT(ans_nan)
ans_inf = AND(nans_nan,OR(either_nan,either_inf))
ans_none = AND(nans_nan,NOT(ans_inf))
nans_none = NOT(ans_none)

result0 = OR(OR(AND(a_inf,a0),AND(b_inf,b0)),AND(ans_none,sign))
result1 = OR( nans_none, AND(ans_none,e0) )
result2 = OR( nans_none, AND(ans_none,e1) )
result3 = OR( nans_none, AND(ans_none,e2) )
result4 = OR( ans_nan, AND(ans_none,f0) )
result5 = OR( ans_nan, AND(ans_none,f1) )

```

---
Tags: atomic-code-golf, logic-gates
---