title: ASCII Ice Cream

text:
# Question
Title: ASCII Ice Cream
Write a program or function that takes in a positive integer N, and prints or returns an N×N ASCII art string whose top half is a semicircle made of `(`'s and whose bottom half is a downward-pointing triangle made of `V`'s, with spaces used as padding.

In other words, make an ASCII ice cream cone: (output for N = 17)

```
      (((((
    (((((((((
  (((((((((((((
  (((((((((((((
 (((((((((((((((
 (((((((((((((((
(((((((((((((((((
(((((((((((((((((
VVVVVVVVVVVVVVVVV
 VVVVVVVVVVVVVVV
  VVVVVVVVVVVVV
   VVVVVVVVVVV
    VVVVVVVVV
     VVVVVVV
      VVVVV
       VVV
        V

```

# Examples

Here are the outputs for N = 1 to 5. **Note that for odd N, the triangle always must be the larger half.**

```
V

((
VV

(((
VVV
 V

 ((
((((
VVVV
 VV

 (((
(((((
VVVVV
 VVV
  V

```

Here's an N = 101 pastebin.

And here's an ungolfed Python 3 reference implementation:

```
N = int(input())
ic = [[' '] * N for _ in range(N)]
for y in range(N//2):
    for x in range(N):
        if (x - (N - 1) / 2)**2 + (y - (N - 1) / 2)**2 < (N / 2)**2:
            ic[y][x] = '('
for y in range(N//2, N):
    for x in range(y - N//2, N - (y - N//2)):
        ic[y][x] = 'V'
for line in ic:
    print(''.join(line))

```

# Details

* Take input from stdin, command line, or as function argument. Output to stdout or similar, or you may return the string if you write a function.
* The cone portion should exactly match the reference implementation for all N.
* The ice cream portion does *not* need to exactly match the reference implementation as long as it is clearly in the shape of a semicircle for all N. (This is so you don't have to worry about slight differences in the semicircle due to roundoff errors.)
* There should not be any unnecessary leading spaces but there may be superfluous trailing spaces.
* The output may optionally contain a trailing newline.
* You may optionally use any 3 other distinct printable ASCII characters in place of `(`, `V`, and space.

# Scoring

The shortest submission in bytes wins. Tiebreaker goes to the oldest submission.

# Answer
# CJam, 46 bytes

Try it online.

```
{:Z{Z{Z(2./:R-zYR<):P#YR-zP#+Z2./P#>SP?}/N}fY}

```

I believe this currently mimics the original specification exactly, which was required when I started producing this answer. There may be potential to save a few bytes by making the math less accurate to the original specification, but until I see a way to save more than one or two bytes doing so, I'll leave it as-is.

### Explanation

```
{               "Begin block";
  :Z{             "For each y from 0 to input-1";
    Z{              "For each x from 0 to input-1";
      Z(2./:R         "Calculate the radius as (input-1)/2.0";
      -z              "Calculate the horizontal distance from the center";
      YR<):P          "Calculate the power to raise distances to: (y<radius)+1
                       (This results in Euclidean distance being calculated for
                        the ice cream and Manhattan distance being calculated
                        for the cone)";
      #               "Raise the horizontal distance to the determined power";
      YR-zP#          "Calculate the vertical distance from the center and
                       raise it to the determined power";
      +               "Add the horizontal and vertical distances";
      Z2./P#          "Calculate the solid distance threshold and raise it to
                       the determined power";
      >SP?            "If the solid threshold is exceeded, produce a space;
                       otherwise, produce the determined power digit
                       (This results in ice cream being represented by the
                        digit '2' and the cone by the digit '1')";
    }/              "End x loop";
    N               "Produce a new line";
  }fY             "End y loop";
}               "End block";

```
> 7 votes

# Answer
## inca2 ~~129~~ ~~123~~ ~~121~~ ~~111~~ 107

This mostly uses the formulas from the python example, but using jot-dots and iotas instead of double-looping. The `i` function performs the circular test for the `j` function which invokes *jot-dot* upon it. And the `k` function performs the triangle test for the `l` function. The `c` function catenates the results of `j` and `l` and reshapes it to N×N.

*edit: -6* combine 2 maps into 1.
*edit: -2* remove useless ravels.
*edit:* nicer typescript.
*edit: -10* apply repeated expression array-wise.
*edit: -4* factor out repeated expression as a function.
*edit:* line-by-line commentary.

```
q:y-(n-1)%2
i:[((n%2)^2)>+/(qx y)^2
j:(~[y%2)i.(~y)
k:2*[x>[|qy
l:(@1+~]y%2)k.(~y)
c:y y#((jn<y),ly){' (V'

```

In more detail, the entry-point is the `c` function which takes one argument implicitly named `y`.

```
c:y y#((jn<y),ly){' (V'
         n<y            } assign y to 'n'
        jn<y            } call j(y)
              ly        } call l(y)
      ((    ),  )       } catenate the results
      (         ){' (V' } map 0 1 2 to ' ' '(' 'V'
  y y#                  } reshape to NxN

```

The `j` function receives the same input value as its `y` parameter.

```
j:(~[y%2)i.(~y)
     y%2         } y divided by 2
    [            } floor
   ~             } iota. this generates the row indices 0..y/2
            ~y   } iota y. this generates the column indices 0..y
  (     )i.(  )  } jot-dot with the function i

```

The jot-dot here does the double-loop. It calls the `i` function with every combination of elements from the left and right arrays (0..n/2 and 0..n). So the `i` function receives as `x` the *y* index of the table, and it receives as `y` the *x* index. The names got a little backwards here :).

```
i:[((n%2)^2)>+/(qx y)^2
     n%2                 } n divided by 2
    (n%2)^2              } squared
                 x y     } make a 2-element array (x,y)
                qx y     } call q on this array

```

where `q` does

```
q:y-(n-1)%2
     n-1    } n minus 1
         %2 } divided by 2
  y-        } y minus that

```

back to `i`

```
i:[((n%2)^2)>+/(qx y)^2
               (    )^2  } square the result from q(x,y)
             +/          } sum the two numbers
            >            } compare the left side (above) with the right (=> 0/1)
  [                      } floor

```

The floor should not be necessary. But apparently there's a bug in the interpreter.

The `l` function works similarly to the `j` function, using a jot-dot.

```
l:(@1+~]y%2)k.(~y)
        y%2         } y divided by 2
       ]            } ceiling
      ~             } iota 0..ceil(y/2)-1
    1+              } add 1 => 1..ceil(y/2)
   @                } reverse => ceil(y/2)..1
               ~y   } iota y  0..y-1
  (        )k.(  )  } jot-dot using k

```

The `k` function yields a boolean scaled by 2 so the values can be distinguished from the ice cream values later on, in the mapping.

```
k:2*[x>[|qy
     x       } k's left arg
         qy  } y-(n-1)%2
        |    } abs
       [     } floor
     x       } left-hand-side again
      >      } compare
    [        } floor (should be unnecessary)
  2*         } scale by 2

```

In action (piping through `tr` to remove tab chars which are the REPL's prompt):

```
josh@Z1 ~/inca
$ ./inca2 <icecream | tr -d '\t'

c1
V

c2
((
VV

c3
(((
VVV
 V

c4
 ((
((((
VVVV
 VV

c5
 (((
(((((
VVVVV
 VVV
  V

josh@Z1 ~/inca
$

```
> 3 votes

# Answer
# Python 2, ~~193~~ 192

Does not use strings, only math

```
N=input()
R=(N+1)/2;r=range(R)
s=lambda L,U:(10**U-10**L)/9
f=lambda N,m:s(0,N)+s(m,N-m)
g=lambda N,m:s(0,N)+s(m,N-m)*6
for i in r[1:]:print f(N,int(R-(2*R*i-i*i)**.5))
for i in r:print g(N,i)

```

`s(L,U)` returns a number of the form "`U`-digits with the rightmost `L` zeros and the rest ones"
`f(N,m)` returns an N-digit number with the inner section of `2` and an m-wide border of `1`on each side
`g(N,m)` does the same, but using `7` for the 'colour' of the inner section since it matches the texture of the cone more closely

Output

```
N=8         N=9
11122111    112222211
12222221    122222221
22222222    222222222
22222222    222222222
77777777    777777777
17777771    177777771
11777711    117777711
11177111    111777111
            111171111

```
> 2 votes

# Answer
# Perl 6, 175

Pretty straightforward implementation without much golfing, just extraneous whitespace/punctuation elimination:

```
sub MAIN($d){my$r=($d/2).Int;for 1..$r ->$n
{my$y=$n-$r;my$h=sqrt($r*$r-$y*$y).Int;my$w=2*$h+$d%2;say
' 'x($r-$h)~'('x$w};for 1..($d-$r) ->$y {say ' 'x($y-1)~'V'x($d-2*$y+2)}}

```
> 2 votes

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


title: The Staircase Challenge

text:
# Question
Title: The Staircase Challenge
Your work is to recreate this piece of art:

```
                        _____
                       |
                       |
                       |
                       |
                  _____|
                 |
                 |
                 |
                 |
            _____|
           |
           |
           |
           |
      _____|
     |
     |
     |
     |
_____|

```

The answer must recreate this and print this as a result. All languages allowed, no direct printing of art, ofc, some level of manipulation is required. The answer with the least bytes wins.

*Closes on Thursday 6:30 AM UTC or so.*

The original thing was shown to me by my friend who did this with Java, he refused to show me the source code and now I'll dazzle him with the brilliance of other languages possibly. :D

**You cannot use any alternative character** *(makes it easier?).*

---

**Current leader board**

1. *Pyth* \- 28 bytes - isaacg
2. *CJam* \- 30 bytes - Runer112
3. *CJam* \- 32 bytes - Martin Büttner

**Highest votes:** *C* \- 73 bytes - Paul R

---

isaacg takes the crown for passing the Staircase Challenge with Pyth. Watch out for more challenges like these on PPCG!

# Answer
# Pyth, ~~29~~ 28

```
V21++**6/-20N5d*5?d%N5\_<\|N

```

Try it here.

A pretty straightforward solution, with the "append five spaces or five underscores" trick from @xnor's solution, but with the loop from 0 to 20, not 20 to 0.
> 4 votes

# Answer
# C, ~~86~~ ~~80~~ ~~76~~ ~~75~~ 73 bytes

```
c;main(i){for(i=21;i--;c='|')printf("%*s%c\n",i/5*6+5,i%5?"":"_____",c);}

```
> 22 votes

# Answer
# Java, ~~198~~ ~~158~~ ~~156~~ 146 bytes

This can probably be shortened a lot. As usual, suggestions are welcome.

```
void a(){String a="",b="_____",c=b;for(int i=-1;i<20;b=i%5<1?b.replace(c,"     "):i%5>3?b+" "+c:b)a=b+(++i>19?"":"|")+"\n"+a;System.out.print(a);}

```

Indented (kinda):

```
void a(){
    String a="",b="_____",c=b;
    for(int i=-1;i<20;b=i%5<1?b.replace(c,"     "):i%5>3?b+" "+c:b)
        a=b+(++i>19?"":"|")+"\n"+a;
    System.out.print(a);
}

```

Thanks Martin Büttner, Rainbolt, and Geobits.
> 11 votes

# Answer
**Brainfuck (1065 Bytes)**

It's not pretty, it's not short...but i'll optimize later on!

```
++++[->++++++++<]>........................
[->+++<]>-.....>++++++++++.[->+++<]>++....
...................-[->++++<]>.>++++++++++
.[->+++<]>++.......................-[->+++
+<]>.>++++++++++.[->+++<]>++..............
.........-[->++++<]>.>++++++++++.[->+++<]>
++.......................-[->++++<]>.>++++
++++++.[->+++<]>++..................[->+++
<]>-.....[->++++<]>.>++++++++++.[->+++<]>+
+.................-[->++++<]>.>++++++++++.
[->+++<]>++.................-[->++++<]>.>+
+++++++++.[->+++<]>++.................-[->
++++<]>.>++++++++++.[->+++<]>++...........
......-[->++++<]>.>++++++++++.[->+++<]>++.
...........[->+++<]>-.....[->++++<]>.>++++
++++++.[->+++<]>++...........-[->++++<]>.>
++++++++++.[->+++<]>++...........-[->++++<
]>.>++++++++++.[->+++<]>++...........-[->+
+++<]>.>++++++++++.[->+++<]>++...........-
[->++++<]>.>++++++++++.[->+++<]>++......[-
>+++<]>-.....[->++++<]>.>++++++++++.[->+++
<]>++.....-[->++++<]>.>++++++++++.[->+++<]
>++.....-[->++++<]>.>++++++++++.[->+++<]>+
+.....-[->++++<]>.>++++++++++.[->+++<]>++.
....-[->++++<]>.>++++++++++.[--->++<]>+++.
....[->++++<]>.

```
> 9 votes

# Answer
# CJam, ~~36~~ 30 bytes

Try it online.

```
L{{S5*\+}/S'|5*+]'_5*+}5*1>zN*

```

My initial 36-byte solution generated the result in the output orientation. Despite my attempts to squeeze more bytes out of the algorithm, I couldn't. Then I saw Martin's brilliant strategy of generating *columns* instead of rows and transposing the result. I realized that was probably a better approach, so I set off to create a transposition-based solution.

However, my approach to implementing that strategy varies quite a bit. Instead of generating full columns, I use an iterative solution that indents any already-generated "steps" and adds adds a new step at each iteration. So the first iteration of the main loop generates this:

```
 |||||
_
_
_
_
_

```

The second iteration of the main loop indents the existing step and adds a new one after it:

```
      |||||
     _
     _
     _
     _
     _
 |||||
_
_
_
_
_

```

And the full five iterations of the main loop generate this:

```
                     |||||
                    _
                    _
                    _
                    _
                    _
                |||||
               _
               _
               _
               _
               _
           |||||
          _
          _
          _
          _
          _
      |||||
     _
     _
     _
     _
     _
 |||||
_
_
_
_
_

```

After this, all that needs to be done is eliminate the first line, which would otherwise become the unwanted riser for the bottom step, and transpose.
> 8 votes

# Answer
# Python 2, ~~80~~ ~~77~~ 74 bytes

```
n=24;exec"print' '*n+'_'*5+'|'*(n<24)+('\\n'+~-n*' '+'|')*4*(n>0);n-=6;"*5

```

Got rid of the double `exec` and fit everything into the one `print`!
> 7 votes

# Answer
# CJam, ~~36~~ 32 bytes

```
{5*S*'_+a5*~_W<S+5'|*+}5/;]W%zN*

```

Test it here.

I also tried using an explicit formula, but it's longer in CJam... maybe it helps someone else:

```
21,29,ff{_2$5/)6*(=@@6/5*=_++" |_|"=}W%N*

```

## Explanation

I found that the staircase can be built much more easily if you a) transpose the grid and b) reverse the lines:

```
_
_
_
_
_
 |||||
     _
     _
     _
     _
     _
      |||||
          _
          _
          _
          _
          _
           |||||
               _
               _
               _
               _
               _
                |||||
                    _
                    _
                    _
                    _
                    _

```

So first I'm building that, then reverse, then transpose.

```
{                     }5/        "For i in [0 .. 4].";
 5*S*'_+                         "Get a string of 5*i spaces and append _.";
        a5*~                     "Get five such lines.";
            _W<S+                "Duplicate the last, remove the _, add a space.";
                 5'|*+           "Add 5 copies of |.";
                         ;       "The above creates a row too many, so discard the last one.";
                          ]W%zN* "Wrap everything in an array, reverse, transpose, riffle
                                  with newlines.";

```
> 6 votes

# Answer
# Clip, 46

```
{:24S:5'_m[z{*4,:+5*6zS"|
":*6zS:5'_"|
"`}vR4`

```

## Explanation

```
{               .- Put everything in a list -.
 :24S           .- 24 spaces                -.
 :5'_           .- 5 underscores            -.
 m[z            .- Map...                   -.
    {           .- A list                   -.
     *4         .- 4 of the following       -.
       ,        .- Append                   -.
        :+5*6zS .- 5 + 6 * the iteration of spaces  -.
        "|      .- A pipe and newline       -.
"
     :*6zS      .- 6 * the iteration of spaces      -.
     :5'_       .- 5 underscores            -.
     "|         .- A pipe and newline       -.
"
    `           .- End list (per iteration  -.
   }vR4         .- The mapping is onto {3,2,1,0}    -.

```
> 6 votes

# Answer
# ECMAScript 6, ~~142~~ ~~138~~ ~~129~~ 91 bytes

Special thanks to @edc65 for really reworking this.

```
a=o='',[for(x of!0+o)(o=(a+'     |\n').repeat(4)+a+'_____|\n'+o,a+='      ')],a+'_____\n'+o

```

```
out.value=(a=o='',[for(x of!0+o)(o=(a+'     |\n').repeat(4)+a+'_____|\n'+o,a+='      ')],a+'_____\n'+o)
```

```
textarea{
  width:300px;
  height:400px;
}
```

```
<textarea id="out";></textarea>
```

The logic of the original version check @edc65 comment for how it morphed.

```
((f,l,p)=>                  //variables
f(24)+l+p[1]+               //add the non pattern line
[0,1,2,3].map(b=>f(18-6*b)) //add the right number of spaces in front of the 4 steps
.map((a,b)=>f(4,a+f(5)+p)   //the four repeating lines of the step
+a+l)                       //the landing line
.join(p)+p)                 //put it all together
((n,s=' ')=>s.repeat(n)     //create an variable array of some character
,'_____','|\n')             //string literals

```
> 6 votes

# Answer
# Python 2, 59

```
n=21
exec"n-=1;print n/5*6*' '+' _'[n%5<1]*5+'|'*(n<20);"*n

```

The 21 lines are indexed by `n` in `[20,19,...,1,0]`. First prints 6 spaces for each "step" we're up (minus 1), computed as `n/5*6`. Then, prints five spaces, except these are instead underscores for multiples of five. Finally, prints a vertical line, except for the top line `n=20`.
> 6 votes

# Answer
# JavaScript, ~~115~~ ~~107~~ ~~96~~ ~~94~~ ~~89~~ ~~87~~ 83 bytes

This is too long to win, but it's the first time I've come up with an answer on PCG.SE, and I'm kind of proud to have made something postable.

With some helpful syntactical advice I shortened the code significantly - even below the scrollbar threshold!

```
for(s='',y=22;--y;s+='\n')for(x=0;++x<29;)s+=6*~(~-y/5)-~x?4+5*~(x/6)+y?' ':'_':'|'

```
> 6 votes

# Answer
# MATLAB, 68 bytes

I have the strong feeling MATLAB should be able to do better, but I can't think of a way.

```
p(1:5,6)='|';p(1,1:5)=95;w=blkdiag(p,p,p,p);w(21,25:29)=95;flipud(w)

```

Creates the stairs upside-down and flips it. My thaumometer broke because of all the magic constants around.

`'|'` is intentionally left as-is (instead of ascii codepoint) to initialize `p` and `w` as a char array.
> 5 votes

# Answer
# Ruby, 48

```
25.times{|i|puts" "*(4-i/6)*5+(i%6==0??_*5:?|)}

```

## Old approach, 68

```
4.times{|i|(?_*5+"
|"*5).each_line{|l|puts" "*(4-i)*5+l}}
puts"_"*5

```
> 5 votes

# Answer
# Julia, 83 bytes

```
for n=24:-6:0 print(" "^n*"_"^5*"|"^(n<24)*"\n"*(" "^(n>0?n-1:0)*"|\n"^(n>0))^4)end

```

In Julia, string concatenation is performed using the `*` operator and string repetition is performed using `^`.
> 4 votes

# Answer
# \>\<\>, ~~108~~ ~~104~~ 100 bytes

```
cc+::?v~'_____'o\/' 'o  \
?:o'|'\' 'o1-30.o\v!?:-1<}:{oav!?:<4;!
-20.12^?(+cc:ooo/ \~1-'!|'o1. \~ao6

```

A simple \>\<\> solution, using the same strategy as my Python answer. The main difference is that \>\<\> doesn't have string multiplication (or even strings), so all of that is done with loops.

## Explanation

```
cc+                  Push 24 (call this "n")

[outer loop]
[loop 1, print n spaces]

:                    Copy n (call this "i")
:?                   If i is not zero...
' 'o1-30.                Print space, decrement i and go to start of loop 1

~'_____'ooooo        Pop i and print five underscores
:cc+(?               If n < 24...
'|'o                     Print a pipe
21.                  Otherwise skip pipe printing

[loop 2: print vertical parts of stairs]

?!;                  If n is zero, halt
4                    Push 4 (call this "j")
?!                   If j is zero...
~ao6-20.                 Pop j, print a newline, minus 6 from n and go to start of outer loop
ao                   Print a newline
}:{                  Copy n (call this "k")

[loop 3: print n-1 spaces]

1-                   Decrement k
:?!                  If k is zero...
    ~1-'!|'o1.           Pop k, decrement j, print a pipe and go to start of loop 2
' 'o                 Otherwise print a space and go to start of loop 3

```
> 4 votes

# Answer
# Perl, 50

```
#!perl -l
print$"x6x(-$_/5),($_%5?$":_)x5,"|"x$|++for-20..0

```

Try me.
> 2 votes

# Answer
# Visual FoxPro 9.0, 261 bytes

### n = Number of Steps

total of 175 characters, but had to output to file to display correctly - so minus 43 chars for file operations = 132 chars.

```
n=10
c=CHR(13)
f="st.t"
ERAS (f)
FOR i=n TO 1 STEP -1
    p=(i-1)*6
    =STRTO(PADL("_____",p+5)+IIF(i<n,"|","")+c+IIF(i>1,REPLI(PADL("|"+c,p+1),4),""),f,.t.)
    ?PADL("_____",p+5)+IIF(i<n,"|","")+c+IIF(i>1,REPLI(PADL("|"+c,p+1),4),"")
ENDFOR
MODI COMM (f)

```

**Note to answerer:** Byte count is for the absolute working source code, and the byte counter says that it's 261 bytes, so it is.
> 2 votes

# Answer
# T-SQL, 276 bytes

```
declare @x int declare @y int declare @w varchar(30) declare @l char(5) set @l='_____' set @x=23 while @x > 4 begin set @w=replicate(' ',@x) set @y=0 if @x=23 print @w+' '+@l else print @w+' '+@l+'|' while @y < 4 begin set @y=1+@y print @w+'|' end set @x=@x-6 end print @l+'|'

```
> 2 votes

# Answer
# Bash (+tac from coreutils): 110 bytes

This can be pasted directly into the terminal.

```
(n=;set {1..4};for i do echo "${n}_____|";n+='     ';for i do echo "$n|";done;n+=\ ;done;echo "${n}_____")|tac
```
> 2 votes

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


title: Write a Kolmogorov Complexity Solver

text:
# Question
Title: Write a Kolmogorov Complexity Solver
The Kolmogorov complexity of a string *S* is the length of the shortest program *P*, written in some programming language *L*, whose output is exactly *S*.
(Yes, the real definition is more formal but this will suffice for the challenge.)

Your task in this challenge is to write the shortest possible "Kolmogorov complexity solver", that is, a program written in *L* itself that takes in a string *S* and returns the shortest *P* written in *L* that outputs *S*.

The naive approach to this is to iterate over all length 1 programs, then all length 2 programs, then all length 3 programs, and so on, running each of them and measuring the output until a program that outputs *S* is found. The issue with this approach is that some of these programs may never stop running, which means that the solver itself may never stop. And due to the halting problem there is no surefire way to avoid the programs that don't stop.

A simple, though imperfect solution is to put a time limit on the execution time of each of the potential *P*'s. Programs that don't happen to halt in time may be passed over, but the solver will definitely stop (assuming that a program in *L* can indeed output *S* within the time limit).

# Challenge

Write your solver as a program or function that takes in three things:

* The string *S*.
* A positive integer *T* that is the time limit in seconds or some smaller time span (e.g. milliseconds).
* A string *A* of the alphabet of characters to use for potential *P*'s.

And outputs the shortest *P* that only contains characters in *A*, runs in less than *T* time units, and outputs *S*.

This is the general pseudocode:

```
Function KolmogorovComplexitySolver(S, T, A):
    Assign N to 0
    Loop until function returns:
        In any order, iterate over all strings of length N that only contain characters from *A*. Call the current string P:
            Execute P, saving the output to O, stopping the execution if it takes longer than time T
            If (P did not throw any errors) and (P did not timeout) and (O and S are identical):
                Return P
        Add 1 to N

```

# Details

* You may assume that there will always be a *P* made from the characters in *A* that runs in time *T* that outputs *S*.
* You may assume that the execution of the potential *P*'s will not have side effects that prevent the solver from running or working correctly (like messing with the solver's allocated memory).
* You may *not* assume that the potential *P*'s are error free. Be sure to include `try`/`catch` blocks or whatever applicable around the execution call.
* If there are multiple shortest *P*'s, then any will suffice. "Shortness" is measured in characters not bytes.
* The output of potential *P*'s is what's printed to stdout (or your language's usual output area). The empty string is a potential *P*.
* Ideally your solver will allow *A* to contain any characters. *A* must at least to be able to contain printable ASCII characters plus tabs and newlines.
* Input may come from file/stdin/command line/function args. Output goes to stdout or similar, or can be returned as a string if you wrote a function.

# Scoring

The submission with the fewest bytes wins. Tiebreaker goes to earliest posted submission.

# Answer
# Python 3, ~~240~~ 236 bytes

```
import subprocess as s,itertools as i
def f(S,T,A,N=0):
 while 1:
  for P in i.product(A,repeat=N):
   try:
    P="".join(P);open("a","w").write(P)
    if s.check_output(["py","-3","a"],timeout=T).decode()==S:return P
   except:1
  N+=1

```

**Don't run this.** On my computer, at least, I found the program really hard to stop once it started running due to the pop-up windows created per process.

`timeout`s were only added to `subprocess.check_output` in Python 3, which is why we're using this rather than Python 2.

Here's an alternative version with a `time.sleep` that also prints all valid programs found along the way, as well as their corresponding output:

```
import subprocess as s,itertools as i
import time
def f(S,T,A,N=0):
 while 1:
  for P in i.product(A,repeat=N):
   time.sleep(0.2)
   try:
    P="".join(P);open("a","w").write(P);C=s.check_output(["py","-3","a"],timeout=T).decode()
    print(P,repr(C))
    if C==S:return P
   except:1
  N+=1

```

The program uses the filename `a` for each program `P` to be tested, so if you run this make sure you don't already have a file of that name. Replace `["py","-3","a"]` with the appropriate command for your setup (e.g. `["python","a"]` or `["python3","a"]`).

Feel free to change the `sleep` duration at your own risk :). Call like `f("1\r\n",1,"1()print")`, where `T` is timeout in seconds.

First few lines of output from the tester with the above call:

```
 ''
1 ''
11 ''
() ''
111 ''
(1) ''
int ''
1111 ''

```

(If you want to help the program along a bit you can change `P="".join(P)` to `P="print"+"".join(P)`)

Since the above programs all have no output, here's the result for `f("1\r\n",1,["print","(",")","1"])` (tokens aren't part of the challenge, but I wanted to show what happens):

```
 ''
print ''
1 ''
() ''
11 ''
print() '\r\n'
(print) ''
(1) ''
111 ''
print(print) '<built-in function print>\r\n'
print(1) '1\r\n'

```

The return value is the string `'print(1)'`.

Finally, just for fun, here's what happens if the alphabet is `string.printable`, i.e.

```
0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c

```

Pastebin link of all valid 0-2 char Python 3 programs
> 11 votes

---
Tags: code-golf, kolmogorov-complexity, metagolf
---


title: Prelude Syntax-Checker

text:
# Question
Title: Prelude Syntax-Checker
Prelude is an esoteric programming language, which has very few, but unusual, restrictions on what constitutes a valid program. Any block of printable ASCII text ("block" meaning that lines of printable ASCII are separated by newlines - 0x0A) is valid provided that:

* Every (vertical) column of text contains at most one of `(` and `)`.
* Ignoring their vertical position, the `(` and `)` are balanced, that is, each `(` is paired with exactly one `)` to the right of it, and vice versa.

Write a program or function which, given a string containing printable ASCII and newlines, determines if it constitutes a valid Prelude program. You may take input via STDIN (or closest alternative), command-line argument or function argument. The result may be returned or printed to STDOUT, using any two *fixed* truthy/falsy values of your choice.

You must *not* assume that the input is rectangular.

This is code golf, so the shortest submission (in bytes) wins.

## Examples

The following are **valid** Prelude programs (in fact, they're even *real* Prelude programs):

```
?1-(v  #1)-
1   0v ^(#    0)(1+0)#)!
    (#)  ^#1-(0 #

```

```
1(#  1) v #  - 1+)
    vv (##^v^+
? v-(0 # ^   #)
?
  1+              1-!

```

And here are a number of inputs, all of which are **invalid**:

```
#(#(##)##)##(
)##(##(##)#)#

```

```
#(#)
)###

```

```
#(##
(##)

```

```
(##)
(#)#

```

```
(##)
(###

```

```
#(#)
(##)

```

```
#(#)
###)

```

```
#()#
()##

```

```
#(#)##
###
###(#)

```

# Answer
> 3 votes
# CJam, ~~57~~ 56 bytes

```
qN/z_{_"()"--W<},,\s:Q,{)Q/({_')/,\'(/,-}:T~\sT0e>+z+}/!

```

Too long, can be golfed a lot. Explanation to be added once I golf it.

**Brief explanation**

There are two checks in the code:

* First filter checks that each column as at most 1 bracket. The final output of the filter is the number of columns with more than 1 brackets.
* Second we convert the input into column major format and then split it on each index into two parts.
    + In each of these two parts, (`Number of "(" - Number of ")"`) should be complimenting each other. So when you add them up, it should result to 0. Any part that fails this property makes the whole input have non matching brackets.
    + I also have to make sure that "(" are to the left of ")". This means that the value of `Number of "(" - Number of ")"` cannot be negative for the right side block.

Try it online here

# Answer
> 6 votes
# Python 2, ~~128~~ ~~119~~ 105 bytes

```
def F(p):
 v=n=1
 for r in map(None,*p.split("\n")):A,B=map(r.count,"()");n+=B-A;v*=n<2>A+B
 return n*v>0

```

Did you know that you can map None in Python 2?

## Explanation

We want to start by transposing the Prelude so that columns become rows. Usually we would do this with `zip`, but since `zip` truncates to the shortest row length and `itertools.zip_longest` is far too long for code-golf, it seems like there's no short way to do what we want...

Except for mapping `None`:

```
>>> print map(None,*[[1,2,3],[4],[5,6]])
[(1, 4, 5), (2, None, 6), (3, None, None)]

```

Unfortunately (or rather, fortunately for all non-golf purposes), this only works in Python 2.

As for `n` and `v`:

* `n` acts like a stack, counting `1 - <number of unmatched '(' remaining>`. For every `(` we see we subtract 1, and for every `)` we see we add 1. Hence if `n >= 2` at any point, then we've seen too many `)`s and the program is invalid. If `n` doesn't finish on 1, then we have at least one unmatched `(` remaining.
* `v` checks validity, and starts at 1. If the program is ever invalid (`n >= 2` or `A+B >= 2`), then `v` becomes 0 to mark invalidity.

Hence if the program is valid, then by the end we must have `n = 1, v = 1`. If the program is invalid, then by the end we must either have `v = 0`, or `v = 1, n <= 0`. Therefore validity can be succinctly expressed as `n*v>0`.

*(Thanks to @feersum for a multitude of good suggestions which took off 14 bytes!)*

## Previous, more readable submission:

```
def F(p):
 p=map(None,*p.split("\n"));v=n=0
 for r in p:R=r.count;A=R("(");B=R(")");n+=A-B;v|=A+B>1or n<0
 return n<1>v

```

# Answer
> 2 votes
# J, 64 bytes

Input is a string with a trailing newline. Output is 0 or 1.

```
(0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)

```

Example usage

```
   ]in=.'#(#)##',LF,'###',LF,'###(#)',LF
#(#)##
###
###(#)

   ((0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)) in
0

```

The method is the following

* cut input at newlines and put into a matrix `];.2`
* map `(` / `)` / `anything else` into `1` / `-1` / `0` `1 _1 0{~[:'()'&i.]`
* define an `s=.+/@:` adverb which added to a verb sums the verbs array output
* add values in columns `]s`

+ check positive `()` balance in every prefix `[:(0>])s)[:+/\]`
    + check equal `()` balance in the whole list (i.e. in the last prefix) `|@{:@]`
* add abs(values) in columns and check every element for a max value of 1 `(1<|s)s`
* as all the previous checks yielded positive at failure we add them up and compare to 0 to get the validity of the input `0=]`

# Answer
> 2 votes
# J, 56 bytes

```
3 :'*/0<: ::0:(+/\*:b),-.|b=.+/+.^:_1]0|:''()''=/];.2 y'

```

That is an anonymous function accepting a string with a trailing newline and returning 0 or 1. Reading from right to left:

* `];.2 y`, as in the other J submission, cuts the string `y` at all occurrences of its last character (which is why the input needs a trailing newline) and makes a rectangular matrix whose rows are the pieces, padded with spaces if necessary.
* `'()'=/` compares every character in that matrix first with `(` and then with `)` returning a list of two 0-1 matrices.
* `+.^:_1]0|:` turns that list of two matrices into a single matrix of complex numbers. So far the program turns every `(` in the input into a 1, every `)` into i, and every other character into 0.
* `b=.+/` assigns the sum of the rows of that complex matrix to `b`.
* `-.|b` makes a list of 1-|z| for every z in `b`. The condition that every column contain at most a single parenthesis translates to all these numbers 1-|z| being nonnegative.
* `+/\*:b` is the vector of running sums of the squares of the numbers in `b`. If every column does contain at most one parenthesis, the squares of the numbers in `b` are all 0, 1 or -1. The `,` concatenates this vector with the vector of 1-|z|'s.
* now all we need to do is test that the entries of our concatenated vector `v` are nonnegative reals numbers, this is almost `*/0<:v`, except that that causes an error if some entries of `v` are not real, so we replace `<:` with `<: ::0:` which just returns 0 in case of error.

---
Tags: code-golf, string, decision-problem, balanced-string, syntax
---


# Question
Title: Identifying Sequences for Cellular Automata
# Background

For the purposes of this challenge, an *`n`-state cellular automaton* is simply a binary function `f` that takes two numbers from the state set `{0, 1, ..., n-1}` as inputs, and returns another number from that set as output. It can be applied to a list of numbers `L = [x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>k-1</sub>]` of length at least 2 by

```
f(L) = [f(x<sub>0</sub>, x<sub>1</sub>), f(x<sub>1</sub>, x<sub>2</sub>), f(x<sub>2</sub>, x<sub>3</sub>), ..., f(x<sub>k-2</sub>, x<sub>k-1</sub>)]
```

Note that the resulting list has one fewer element than the original. A *spacetime diagram* of `f` starting from `L` is the list of lists obtained by repeatedly applying `f` to `L`, and collecting the results in a list. The final list has length 1. We say that the list `L` is an *identifying sequence* for `f`, if every two-element list over the state set is a contiguous sublist of some row of the spacetime diagram starting from `L`. This is equivalent to the condition that no other `n`-state CA has that exact spacetime diagram.

# Input

Your inputs are an `n`-by-`n` integer matrix `M`, a list of integers `L` of length at least 2, and optionally the number `n`. The matrix `M` defines an `n`-state CA `f` by `f(a,b) = M[a][b]` (using 0-based indexing). It is guaranteed that `n > 0`, and that `M` and `L` only contain elements of the state set `{0, 1, ..., n-1}`.

# Output

Your output shall be a consistent truthy value if `L` is an identifying sequence for the CA `f`, and a consistent falsy value otherwise. This means that all "yes"-instances result in the same truthy value, and all "no"-instances result in the same falsy value.

# Example

Consider the inputs `n = 2`, `M = [[0,1],[1,0]]`, and `L = [1,0,1,1]`. The matrix `M` defines the binary XOR automaton `f(a,b) = a+b mod 2`, and the spacetime diagram starting from `L` is

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

```

This diagram does not contain `0 0` on any row, so `L` is not an identifying sequence, and the correct output is `False`. If we input `L = [0,1,0,0]` instead, the spacetime diagram is

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

```

The rows of this diagram contain all pairs drawn from the state set, namely `0 0`, `0 1`, `1 0` and `1 1`, so `L` is an identifying sequence and the correct output is `True`.

# Rules

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

# Test Cases

```
Trivial automaton
[[0]] [0,0] 1 -> True
Binary XOR
[[0,1],[1,0]] [1,0,1,1] 2 -> False
[[0,1],[1,0]] [1,0,1,0] 2 -> True
[[0,1],[1,0]] [0,1,0,0] 2 -> True
Addition mod 3
[[0,1,2],[1,2,0],[2,0,1]] [0,1,1,0,0,0,1,0,0] 3 -> False
[[0,1,2],[1,2,0],[2,0,1]] [0,1,1,0,0,0,1,0,1] 3 -> True
Multiplication mod 3
[[0,0,0],[0,1,2],[0,2,1]] [0,1,1,2,0,0,1,0,1] 3 -> False
[[0,0,0],[0,1,2],[0,2,1]] [0,1,1,2,2,2,1,0,1] 3 -> True
Some 4-state automata
[[3,2,2,1],[0,0,0,1],[2,1,3,1],[0,1,2,3]] [0,0,0,0,1,1,1,1] 4 -> False
[[3,2,2,1],[0,0,0,1],[2,1,3,1],[0,1,2,3]] [0,0,0,1,0,1,1,1] 4 -> False
[[3,2,2,1],[0,0,0,1],[2,1,3,1],[0,1,2,3]] [0,1,2,3,3,1,2,3,0] 4 -> True
[[0,1,2,1],[1,0,2,0],[2,2,1,0],[1,2,0,0]] [0,0,1,1,2,2,0,2,1] 4 -> False
[[0,1,2,1],[1,0,2,0],[2,2,1,0],[1,2,0,0]] [0,3,1,3,2,3,3,0,1] 4 -> False
[[0,1,2,1],[1,0,2,0],[2,2,1,0],[1,2,0,0]] [0,3,1,3,2,3,3,0,1,2] 4 -> True

```

# Answer
> 2 votes
# CJam, ~~53~~ ~~43~~ 42 bytes

```
l~:M;_,({_[\1>]zW<_{M\{=}/}%}*;](_*\L*_&,=

```

This is a very straight-forward implementation of the definition (I took some inspiration from Jakube after my first attempt). It expects input in reverse order on STDIN, using CJam-style arrays:

```
2 [1 0 1 1] [[0 1][1 0]]

```

Here is a test harness which runs the code against all inputs (converting them to the correct input format first). The results in the input field aren't actually used. Remove them if you don't trust me. ;)

# Answer
> 5 votes
# Python 2: 93 byte

```
M,L,n=input();a=[]
while L:z=zip(L,L[1:]);a+=z;L=[M[i][j]for i,j in z]
print len(set(a))==n*n

```

Straightforward implementation: Find all pairs by zipping, memorize them for later and apply M to L. Repeat. Compare the number of unique pairs found.

Input is of the form `[[0,1],[1,0]], [0,1,0,0], 2`.

# Answer
> 2 votes
# Mathematica, ~~90~~ ~~83~~ 82 bytes

```
f=Length[Union@@Last@Reap[#2//.l_List:>Extract[#,Sow/@Partition[l+1,2,1]]]]==#3^2&

```

Another straight-forward implementation.

Usage:

```
f[{{0, 1}, {1, 0}}, {0, 1, 0, 0}, 2]

```

> True

---
Tags: code-golf, array, decision-problem, cellular-automata
---


title: ICS Maritime Flag alphabet

text:
# Question
Title: ICS Maritime Flag alphabet
The International Code of Signals flag alphabet is used by ships for communication, particularly for static signals.

Your challenge is to write a program or function that will take a string from STDIN or as an argument, and display the corresponding text in the ICS flag alphabet. If your language does not display to the screen, saving to a file is acceptable.

Your program or function shall support letters **A-Z** in upper and lower case, plus **Space** and **Newline**. Behaviour with other characters is undefined.

The display shall be ~~large enough to display~~ *capable of displaying* at least 8 flags horizontally and 6 flags vertically. Behaviour is undefined if the right hand edge is reached before a newline is received, or if the message is too long to fit the display vertically.

The flag alphabet is as shown below (Roman letters are for reference only, they are not required in the output.)

**Dimensions**

There is no universally agreed standard for the dimensions of these flags, so for the purpose of this challenge the following shall apply:

Flags shall be 60x60 pixels, with a 30 pixel gap between them both horizontally and vertically.

The swallowtail cut on A and B shall be 15 pixels deep.

All other lines shall be horizontal, vertical, or at 45 degrees.

**The features shall be located by dividing the flag into an imaginary NxN grid of side 3,4,5 or 6 squares. Refer to the above image, but for further clarification:**

*A,E,H,K, L and U are based on a 2x2 grid : width of each colour zone shall be 30pixels. Also the points of the diamond in F shall be halfway along each side of the flag.*

*J and T are based on a 3x3 grid: each band shall be 20 pixels.*

*P,N and S are based on a 4x4 grid. Also the diagonal lines of Y shall split the edges of the flag into 4.*

*C,D,R and X shall be based on a 5x5 grid. Bands and arms of crosses shall be 12 pixels wide.*

*G,W,M,V are based on a 6x6 grid. Bands of G and borders of W shall be 10 pixels wide. Arms of crosses on M and V shall cover the first and last 10 pixels of each edge of the flag, leaving triangle zones measuring 40 pixels along the long edge.*

*The circle of I shall be in the centre of the flag and have diameter 30 pixels.*

An error of +/-1 pixel from the above text is permitted. If your language only supports scalable graphics, you may interpret "pixels" to mean "units."

**Colours**

Colours shall be red, white, blue, yellow and black as defined by your language or its documentation. If your language does not define colours, you may use the following: Red FF0000, White FFFFFF, Blue 0000FF, Yellow FFFF00, Black 0000000.

Background shall be grey (r,g and b channels equal, between 25% and 75% intensity.)

**Scoring /Loopholes**

This is codegolf. Shortest code in bytes wins.

Standard loopholes are disallowed.

No builtin or library functions for displaying flags may be used. Output shall be non-text (and in particular, unicode characters shall not be used to build up the flag shape.)

**Example**

```
JFK got
my VHS
PC
and XLR
web quiz

```

should produce the following

# Answer
> 15 votes
# CJam, 464 bytes

You thought CJam didn't have image manipulation functions? Well, you thought right! But I wasn't going to let that stop me.

```
"P3
690 690 4
"3a3*a690_@*a*qeuN/{0:U;{_'C<.5*:N;i[{XY+Z<[E8][9C]?XY<=}WWWW{XH<9F?}C{YC/[9FCF]=}{YC/3&9E?}{YH<9F?}{X29.5:R-zYR-z+H>FC?}{XA/1&9E?}{XH<FC?}{XR-_*YR-_*+F_*>E8?}{YK/(9F?}{XH<E9?}{XH<YH<^8E?}{XY+Z-A/XY-A/e&9F?}{XF/YF/^1&F9?}{XY<EC?}{XH-F/YH-F/|9F?}E{XHm6/YHm6/e&CE?}{XH-F/YH-F/|F9?}{XK/[CF9]=}{XH<YH<^FC?}{XY+Z-A/XY-A/e&FC?}{XR-zYR-ze>iA/[CF9]=}{XHm6/YHm6/e&F9?}{XY+F/1&CE?}]=:P~!!{60:Z{Z30:HYH-z-N*-{YV+_2$=XU+P2b1>4f*tt}fX}fY}*U90+:U;}/V90+:V;}/`"[]"-

```

This program outputs the image in the best way CJam can: as text that represents the image when saved as a PPM file. Don't even try running it with the online interpreter, by the way; you'll blow the stack. Run it with the Java interpreter and pipe the output to a file with a command like `java -jar cjam-0.6.4.jar flags.cjam > flags.ppm`. Once you've provided your input, send an EOF (may need to be immediately after a newline) with ctrl+D on Unix or ctrl+Z on Windows.

### Sample

If it's really desired, I can try to paste the original ~3MB image source somewhere. But here's the result opened in GIMP and conerted to a PNG:

```
ABCDEFG
hijklmn
OPQRSTU
vwxyz z

```

### Explanation

The image header, easily identifiable in the source, consists of the magic number, width, height, and maximum channel value. So the output is a 690\*690 image (enough for 8\*8 60px flags with 30px of spacing between them) with each R, G, and B value ranging from 0 to 4.

The image data is initialized as a 690\*690\*3 array filled with 3's, making the whole image light gray. Then the input is read, converted to uppercase, and split into lines. The lines are processed in a loop, incrementing the flag Y coordinate by 90 each iteration, and in each line, each character is processed in a loop, incrementing the flag X coordinate by 90 each iteration. Now the magic begins.

Each character is mapped to a flag's pixel function that, when called, returns the color of the pixel at the position (X, Y) on the flag. This is where most of the hard work went: concisely describing 26 images as mathematical functions. Each of these functions returns a color value from 8-15. This range takes advantage of the fact that, when converted to base 2, the resulting bit array can be interpreted as \[1, R, G, B\]. The first element can be removed and the rest multiplied by 4 to easily give a pixel value in the desired format that covers all the possible flag colors (as well as green, cyan, and magenta). It also works out nicely that there are one-character variables initialized to 10-15, and since varaibles don't need a space to syntactically separate them, any two colors besides black and blue can be entered next to each other without needing any spacing.

Once the function is retrieved, it's just a matter of iterating over both of X and Y from 0-60, calling the function at each step, and writing the result back to the image data array. An astute observer might notice that the color values returned by each flag function don't allow gray, though. So there's a bit of extra logic to skip spaces. But there are still the swallowtail cuts on 'A' and 'B'. So there's a bit of extra logic there, too. If the character value is less than 'C', a value is set such that the upper bound on the X loop varies correctly with respect to Y and the cut-out areas are never drawn.

Overall, I'm pretty happy with how this came out. It took a lot of work, but it was fun. Some flags don't perfectly match the reference image, but I think I got all the shapes to be within 1px of the target (if any are off by more than that, let me know and I'll fix them). And there's definitely still potential to optimize, as there's a fair amount of redundancy between the 26 flag functions.

---

# Ineresting first attempt, 559 bytes

Altough I never quite finished this, I'll post it too, because it's pretty interesting. Instead of modelling each flag by a function of (X, Y) → color, flags are drawn as a composition of simple shapes. But I was worried about needing to write a substantial amount of rendering code for each different shape. After a lot of pondering, I realized I could render them all, with some clever overlapping and overdrawing, with just one pseudo-shape: all the points within a specified distance of a specified point, where the definition of "distance" is variable. Chessboard distance gives a square, Manhattan distance gives a diamond, and Euclidean distance gives a circle. This meant every shape had the same five parameters (color, distance mode, x, y, and max distance) and I only needed to write one shape data decoder and one rendering function with a small bit of distance mode logic.

```
"P3
690 690 4
"3a3*a690_@*a*qeuN/{0:U;{_'C<.5*:N;i[[8EX30:Q0Q9X60:ZQQCXQZQ]LLLL[F9TTQQ]Ca[9FTQ42QCTQ54QFTQ66Q9TQ78Q][E9TIQI9T42QI][9FTQZQ][FCXQQQ][E9T40QQET50QQ9TZQQET70QQ9T80QQ][FCTZQQ][E8YQQF][9FTQAQ9TQ9~Q][E9TZQQ][8ETTTQETZZQ][F9XQTK9XZQK9XQZK9XTQK][F4{4{JW^1&6*9+TJ)F*W)F*F}fJ}fW][CEX0ZZ][9FTQQF]Ea[E[TZ]_m*{CT@~24}/][F9TQQF][9FTAQQCT9~QQ][FCTTTQCTZZQ]C9$1>9a/Fa*+[9FTQQKCTQQA]9 6$1>Ca/Fa*+[C7{7\-_1&2*C+X@TT@F*}/]]=_!!{([TQQQ]+\+}*5/{~:R;.5-:H;.5-:G;:M;2b1>4f*:O;Z{ZQWQ-z-N*-{JG-{zM_!+#}:P~WH-PM{+}{e>}?RP<{WV+_2$=JU+Ott}*}fJ}fW}/U90+:U;}/V90+:V;}/`"[]"-

```

# Answer
> 2 votes
# PHP, 811 bytes

```
function f($s){echo"<body bgcolor=#ccc>";$z=split("\n",gzinflate(base64_decode("vVfNasMwDL7vKQK7xlT+iaHQ9LDTLnuIQus6ENhgxS19+kmO0yRrkhbqGIxtyV8sWbIkZ/Prjtm52p9suYbMHqqjPdHMVYfzx/elhBzyNbXtZoXQ7dvm+Q9+dieb7csvZFkJToNlEq6Zqeq6fAcw2arDqCKXUPMCEYQicIc1xmNfUkBDzXgQkpMQ3W0PEGF7fz49dT7IuSCQ1APJ5h9IKAIhdGn1jIHH6oUzvCpZzhtGjoDiePzuzAPJEkG1JPk1uw29G5rC7pxAvAFxuHqd+nQxpCP65S4gR6wzAkphE4rPHfbYaAueky59BrmrZ4wU0Ss8SES/pCNugMduiBSYs25oJTeBSYNMbHO6+bUg22PPhA8E5LCWhT3SFBjEwxaWiOMYD1+FtZSZxateEAZ7pvsEL7w1aQxD3HxLcmayfNA9ZeXzcdteJLm0H5ZITzAwolDkXeGwVAvlSzUOSDDkMRqRxDkuLquVecbKMRKFaESLSYOMg4b6qVHQMnkMns5jyZLBAnksRehirQWrwClEqakDNrqKpjqKpZ8K5rVYTFE56ZmCyT68KinJX+n/puFpyHXg4RRLwg1oW6YipqfimfJTt6/c6XIv6Tnc/HxNXIj+a9nORdwN5Qa3qzvGHw==")));while($c=ord(ucfirst($s))){$s=substr($s,1);echo$c<32?'<br>':($c^32?$z[$c-64]:$z[0]);}}

```

The compressed blob contains SVG code for each of the 26 flags. A simple loop then extracts and outputs the SVG image corresponding to each character of the input.

## Sample output for "This is`\n`a test":

```
<body bgcolor=#ccc><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h20v60h-20z fill=#f00 /><path d=M20,0h20v60h-20z fill=#fff /><path d=M40,0h20v60h-20z fill=#00f /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h30v60h-30z fill=#fff /><path d=M30,0h30v60h-30z fill=#f00 /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h60v60h-60z fill=#ff0 /><path d=M15,30a15,15,0,0,1,30,0a15,15,0,0,1-30,0z fill=#000 /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h60v60h-60z fill=#fff /><path d=M15,15h30v30h-30z fill=#00f /></svg><svg width=90 height=90 viewBox=0,0,90,90></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h60v60h-60z fill=#ff0 /><path d=M15,30a15,15,0,0,1,30,0a15,15,0,0,1-30,0z fill=#000 /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h60v60h-60z fill=#fff /><path d=M15,15h30v30h-30z fill=#00f /></svg><br><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h30v60h-30z fill=#00f /><path d=M45,30l15-30h-30v60h30z fill=#fff /></svg><svg width=90 height=90 viewBox=0,0,90,90></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h20v60h-20z fill=#f00 /><path d=M20,0h20v60h-20z fill=#fff /><path d=M40,0h20v60h-20z fill=#00f /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h60v30h-60z fill=#00f /><path d=M0,30h60v30h-60z fill=#fff /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h60v60h-60z fill=#fff /><path d=M15,15h30v30h-30z fill=#00f /></svg><svg width=90 height=90 viewBox=0,0,90,90><path d=M0,0h20v60h-20z fill=#f00 /><path d=M20,0h20v60h-20z fill=#fff /><path d=M40,0h20v60h-20z fill=#00f /></svg>
```

(You can try it out at ideone, although it won't render the page for you.)

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


title: Water Balloon Wars

text:
# Question
Title: Water Balloon Wars
This king-of-the-hill game is a strategy game in which you must throw around a water balloon and avoid getting splashed by water. The goal is to obtain the most points. You will be given a map of the field and the location of the water balloon. You can either return that you want to hit the water balloon (if you are close enough) in a certain direction or that you want to move in a certain direction.

Specifically: The water balloon will start at `(0, 0)` 30 units high and drop. If the water balloon hits the ground, a player will randomly be chosen to lose 4 points, with more weight given to those who are closer to the balloon. In addition, the player who last hit the balloon will earn 3 points. Therefore, if you hit the balloon straight down, you will most likely lose 1 point.

You will write a class that extends `Player`. You are required to implement the constructor. The constructor will look like:

```
public Player1() {
    super(/* Some numbers */ 3, 3, 4)
}

```

These numbers are `double`s. The first number represents the player's speed, the second represents strength, and the third represents luck. The numbers must add up to 10 or less and no number may be less than **or equal to** zero.

Second, you must implement the `move` method. This is an example `move` method:

```
@Override
protected Action move(Map<Player, Point2D> map, Balloon b) {
    // Get my own location
    Point2D myself = map.get(this);
    // If I'm close enough to the balloon
    // then hit the balloon
    if (myself.distanceSq(b.getLocation()) <= 16) {
        double d = (r.nextDouble() - 0.5) * 3;
        // Random y direction, z direction is what's left
        return new Hit(0, d, Math.sqrt(9 - d*d));
    } else {
        double diffX = b.getLocation().getX() - myself.getX(),
                diffY = b.getLocation().getY() - myself.getY();
        // Move towards the balloon
        return new Movement(Math.signum(diffX)*3/Math.sqrt(2), Math.signum(diffY)*3/Math.sqrt(2));
    }
}

```

There are a number of important things here. First, notice that the field is passed as a `Map<Player, Point2D>`. The field is infinite - there is no limit to how far you can go. It is not a 2-dimensional array or anything like that. In addition, this means that you will have non-integer coordinates as your location. This is perfectly okay.

Another consequence is that players and the balloon may overlap. In fact, two players may be in the exact same location!

The balloon has a certain velocity and direction. In general, it will fall at a rate of 3 units/step. It also moves in an `x` direction and `y` direction. When you return a `Hit`, you pass the x, y, and z directions that you are pushing the balloon. You cannot hit a balloon whose height is greater than 10 or whose distance from you (only on two dimensions) is greater than 4. In addition, if it is true that `x^2 + y^2 + z^2 > s^2` where `s` is your strength, and `x`, `y`, and `z` are the directions that you hit, your action is discarded. The force of your hit is amplified by a random number between `0` and `luck` (which means it could go down if your luck is low).

Similarly, you can return a `Movement` with the `x` and `y` coordinates that you are moving (note that you cannot jump in the air). If `x^2 + y^2 > s^2` where `s` is your speed, your action is discarded.

If the water balloon hits the ground then a random player is chosen, with more weight given to those who are closest -- but less weight to those who have more luck. The player that is chosen loses 4 points.

Controller: https://github.com/prakol16/water-balloon-wars/tree/master

The game lasts 1000 steps. At the end, there will be a file called `log.out`. Copy and paste the data into this fiddle to view the game: https://jsfiddle.net/prankol57/s2x776dt/embedded/result/

Or even better, view it in 3D: http://www.brianmacintosh.com/waterballoonwars (thanks to BMac)

The player with the highest sum of scores after 100 (may be more, but not less) games wins.

If you wish to submit a solution, you may want to read the really specific details at https://github.com/prakol16/water-balloon-wars/tree/master.

**Edit 3/8**:

These are the final scores for now (1000 iterations, without including players 1 and 2). If you edit your post, you can comment, and I will redo the scores:

```
{
    class players.BackAndForth=-75.343,
    class players.Hydrophobe=-0.800,
    class players.KeepAway=-53.064,
    class players.Weakling=39.432,
    class players.Repeller=21.238,
    class players.LuckyLoser=-30.055,
    class players.AngryPenguin=-49.310
}

```

The winner was `Weakling` with an average of 39 points. 2nd place was `Repeller` with 21 points.

# Answer
> 7 votes
# BackAndForth

This bot tries to get close and hit the balloon until its height is too low and it tries to get away.

```
package players;

import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class BackAndForth extends Player {

    static int round = 0;
    static int speed = 3;
    static int strength = 1;
    static boolean hit = false;
    static double previousHeight = 30.0;

    public BackAndForth() {
        super(speed, strength, 10 - speed - strength);
    }

    @Override
    protected Action move(Map<Player, Point2D> map, Balloon b) {

        round++;

        Point2D me = map.get(this);
        Point2D balloon = b.getLocation();

        double distanceX = balloon.getX() - me.getX();
        double distanceY = balloon.getY() - me.getY();
        double distance = Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));

        double maxX = speed * distanceX / distance;
        double maxY = speed * distanceY / distance;

        if (previousHeight < b.getHeight())
            hit = false;

        if (hit || b.getHeight() < 3) {
            previousHeight = b.getHeight();
            return new Movement(-maxX, -maxY);
        } else {
            if (distance < 4 && b.getHeight() < 10) {
                hit = true;
                return new Hit(0, 0, strength);
            } else {
                if (Math.pow(distance, 2) <= Math.pow(speed, 2)) {
                    return new Movement(distanceX, distanceY);
                } else {
                    return new Movement(maxX, maxY);
                }
            }
        }

    }

}

```

# Answer
> 7 votes
# Simulator

I hope this is okay, since it isn't actually an entry. I really liked the idea of the visual simulator and I wanted to create my own that would make it a little easier to see everything at once (full 3D).

**2/28 9:06AM PST**: update with follow controls, colors

**3/4 8:47AM PST**: update with a slider for simulation speed, and made starting a new game actually work without refreshing the page (use Ctrl-F5 to reload cached script)

Online ThreeJS Visualizer

# Answer
> 5 votes
## AngryPenguin

This penguin is angry because he can't fly up to the balloon, so he tries to hit the balloon into the face of people standing around him.

```
package players;

import java.awt.geom.Point2D;
import java.util.Map;
import java.util.Map.Entry;

import balloon.Action;
import balloon.Action.Hit;
import balloon.Action.Movement;
import balloon.Balloon;
import balloon.Player;

public class AngryPenguin extends Player {
    private static final double HIT_Z = 3;
    public AngryPenguin() {
        super(4, 4, 2);
    }

    @Override
    protected Action move(Map<Player, Point2D> map, Balloon balloon) {
        Point2D myself = map.get(this);

        double distanceX = balloon.getLocation().getX() - myself.getX();
        double distanceY = balloon.getLocation().getY() - myself.getY();
        double distance = Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));

        if (balloon.getHeight() < 2) {
            double[] xy = shrink(distanceX, distanceY, Math.pow(getSpeed(),2));
            return new Movement(-xy[0], -xy[1]);
        } else if (distance <= 4 && balloon.getHeight() <= 10) {
            double lowestDistance = Double.MAX_VALUE;
            Point2D nearestPlayerLoc = null;
            for (Entry<Player, Point2D> e : map.entrySet()) {
                if (e.getKey() != this) {
                    double d = e.getValue().distanceSq(myself);
                    if (d < lowestDistance) {
                        lowestDistance = d;
                        nearestPlayerLoc = e.getValue();
                    }
                }
            }
            double dX = nearestPlayerLoc.getX() - myself.getX();
            double dY = nearestPlayerLoc.getY() - myself.getY();
            double d = Math.pow(getStrength() - HIT_Z, 2);
            double[] xy = shrink(dX, dY, d);
            return new Hit(xy[0], xy[1], -HIT_Z);
        } else {
            double[] xy = shrink(distanceX, distanceY, Math.pow(Math.min(getSpeed(), distance), 2));
            return new Movement(xy[0], xy[1]);
        }
    }

    private double[] shrink(double x, double y, double totalPow) {
        double[] xy = new double[2];
        double ratio = y == 0 ? 0 :
                       x == 0 ? 1 : Math.abs(x) / Math.abs(y);
        if (ratio > 1)
            ratio = 1/ratio;
        xy[1] = totalPow * ratio;
        xy[0] = totalPow - xy[1];
        xy[0] = x < 0 ? -Math.sqrt(xy[0]) : Math.sqrt(xy[0]);
        xy[1] = y < 0 ? -Math.sqrt(xy[1]) : Math.sqrt(xy[1]);
        return xy;
    }

}

```

# Answer
> 5 votes
## Weakling

This bot can only touch the balloon as it is so weak, instead it just relies on its high luck. It therefore performs similarly to LuckyLoser (from which this bot is inspired).

He seems to out perform all the current bots including Repeller.

```
package players;
import java.awt.geom.Point2D;
import java.util.Map;
import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class Weakling extends Player {

    static final private double STRENGTH = Double.MIN_VALUE;
    static final private double SPEED = 1.5;
    static final private double LUCK = 8.5;
    public Weakling() {
        super(SPEED,STRENGTH,LUCK);
    }

    protected Action move(Map<Player, Point2D> map, Balloon b) {
        Point2D start = map.get(this);
        Point2D balloon = b.getLocation();
        double distance = start.distance(balloon)+Double.MIN_VALUE;
        if(distance<=4 && b.getHeight()<=10){

            // just touch it :P
            return new Hit(0,0,0);
        }
        double x = start.getX()-balloon.getX();
        double y = start.getY()-balloon.getY();
        x /= distance;
        y /= distance;

        // move to directly underneath balloon
        x*=Math.min(SPEED, distance);
        y*=Math.min(SPEED, distance);
        return new Movement(-x, -y);
    }
}

```

EDIT: reduced speed in favour of luck

# Answer
> 3 votes
## Lucky Loser

This bot relies on its high luck score. If it is not near the balloon, it runs towards the balloon. Once near the balloon, if there are at least 2 other players in range of the balloon, he'll spike it to the ground. Otherwise, he'll knock it straight up.

```
package players;
import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class LuckyLoser extends Player {
    public LuckyLoser() {
        super(1,1,8);
    }

    protected Action move(Map<Player, Point2D> map, Balloon b) {
        Point2D start = map.get(this);
        Point2D bLocation = b.getLocation();
        double distance = start.distance(bLocation);
        if(distance<=4){
            boolean foundMe = false;
            int numPlayersInRange=0;
            for(Point2D point:map.values()){
                if( !foundMe && point.equals(start))
                {
                    foundMe=true;
                    continue;
                }
                if(point.distance(bLocation)<=4)
                    numPlayersInRange++;
            }
            if(numPlayersInRange>1)
                return new Hit(0,0,-1);
            else
                return new Hit(0,0,1);
        }
        double x = start.getX()-bLocation.getX();
        double y = start.getY()-bLocation.getY();
        x /= distance;
        y /= distance;
        return new Movement(-x, -y);
    }
}

```

EDIT: Fixed movement bug which actually made me run away not towards the balloon \>\_\< Now I just run straight towards the balloon if I can't hit it.

# Answer
> 3 votes
# Hydrophobe

This is one of the simplest possible bot possible but as it is competitive I will post it.

Strategy: well... this bots hates water so it just goes away.

As the bot will be splashed very rarely it will score a little under 0 point in average. The sum of all bots' scores are -1 * \[balloon hitting ground\] so Hydrophobe will probably score above average.

```
package players;
import java.awt.geom.Point2D;
import java.util.Map;
import balloon.*;

public class Hydrophobe extends Player {
    public Hydrophobe() {super(8, 1, 1);}
    @Override
    protected Action move(Map<Player, Point2D> map, Balloon balloon) {
        return new Action.Movement(5.65,5.65);
    }
}

```

# Answer
> 3 votes
# KeepAway

This player chases the balloon as long as its height is \> 2. As soon as it can hit the balloon, it hits the balloon **away from** the closest player. When the balloon's height is \< 2, this player runs away.

```
package players;

import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class KeepAway extends Player{

    public KeepAway() {
        super(5, 3, 2);
    }

    @Override
    protected Action move(Map<Player, Point2D> map, Balloon b) {

        Point2D myself = map.get(this);

        //if balloon is high up, run towards it
        if(b.getHeight() > 2){
            Point2D closest = getClosestPlayer(map);

            boolean canHit = b.getHeight() <= 10 && myself.distance(b.getLocation()) <= 4;

            //hit it when you can
            if(canHit){

                Point2D normHit = normalize(new Point2D.Double(myself.getX() - closest.getX(), myself.getY() - closest.getY()));
                Point2D forceHit = new Point2D.Double(normHit.getX() * getStrength(), normHit.getY() * getStrength());

                return new Hit(forceHit.getX(), forceHit.getY(), 0);
            }
            //if you can't hit it, keep running towards it
            else {

                Point2D normRun = normalize(new Point2D.Double(myself.getX() - b.getLocation().getX(), myself.getY() - b.getLocation().getY()));
                Point2D forceRun = new Point2D.Double(-normRun.getX() * getSpeed(), -normRun.getY() * getSpeed());
                return new Movement(forceRun.getX(), forceRun.getY());
            }
        }
        //if the balloon is low, run away
        else{
            Point2D normRun = normalize(new Point2D.Double(myself.getX() - b.getLocation().getX(), myself.getY() - b.getLocation().getY()));
            Point2D forceRun = new Point2D.Double(normRun.getX() * getSpeed(), normRun.getY() * getSpeed());
            return new Movement(forceRun.getX(), forceRun.getY());
        }

    }

    private Point2D getClosestPlayer(Map<Player, Point2D> map){

        double minDistance = Double.MAX_VALUE;
        Point2D closestPoint = null;
        Point2D myPoint = map.get(this);

        for(Player p : map.keySet()){
            if(this != p){

                if(myPoint.distance(map.get(p)) < minDistance){
                    minDistance = myPoint.distance(map.get(p));
                    closestPoint = map.get(p);
                }
            }
        }

        return closestPoint;
    }

    private Point2D normalize(Point2D p){
        double d = p.distance(0, 0);

        if(d == 0){
            return new Point2D.Double(0, 0);
        }

        return new Point2D.Double(p.getX()/d, p.getY()/d);
    }

}

```

Edit: I was playing with Player1 and Player2 included. This player wins in that case, but loses when I take them out. Booooo.

# Answer
> 3 votes
## Repeller

This bot relies has only one real move and that is to keep on pushing the balloon away from itself. i.e. repells the balloon.

It seems to perform well against the current crop of bots (LuckyLoser, AngryPenguin, Hydrophobe, BackAndForth ) nearly always winning. However Hydrophobe, by inaction, is always ready to win if the other bots all manage to get negative score :P

```
package players;
import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class Repeller extends Player {

    static final private double STRENGTH = 3.5;
    static final private double SPEED = 2.5;
    static final private double LUCK = 4;
    public Repeller() {
        super(SPEED,STRENGTH,LUCK);
    }

    protected Action move(Map<Player, Point2D> map, Balloon b) {
        Point2D start = map.get(this);
        Point2D balloon = b.getLocation();
        double distance = start.distance(balloon)+Double.MIN_VALUE;
        if(distance<=4 && b.getHeight()<=10){
            double x = start.getX()-balloon.getX();
            double y = start.getY()-balloon.getY();
            x /= distance;
            y /= distance;
            x*=STRENGTH;
            y*=STRENGTH;

            // push the balloon away with all our strength
            return new Hit(-x,-y,0);
        }
        double x = start.getX()-balloon.getX();
        double y = start.getY()-balloon.getY();
        x /= distance;
        y /= distance;

        // if we are directly underneath then move away from balloon
        distance=distance<1?-1:distance;

        // if we are just off of directly underneath then stay put
        distance=distance<2?0:distance;

        // move to the desired location
        x*=Math.min(SPEED, distance);
        y*=Math.min(SPEED, distance);
        return new Movement(-x, -y);
    }
}

```

---
Tags: king-of-the-hill, java
---


title: Find the maximum of ax+b

text:
# Question
Title: Find the maximum of ax+b
You are given a list of (*a,b*), and a list of *x*. Compute the maximum *ax+b* for each *x*. You can assume *a*, *b* and *x* are non-negative integers.

Your program or function must run in expected (to the randomness if your code involves that, not the input) **O(*n*log*n*) time** where *n* is the total input length (sum or maximum of the lengths of both lists).

This is code-golf. Shortest code wins.

### Example

```
[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]

```

Output:

```
[11 12 14 16 20]

```

Explanation:

```
11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0

```

### Note about the complexity:

If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.

That means, if your program can be tested to be in O(*n*log*n*), possibly with edge case exceptions because of the implementation of your language, but cannot be seen logically in your own code, we'll say it is O(*n*log*n*).

# Answer
# Pyth \- 99 98 bytes

This is pretty much a direct translation of @KeithRandall's Python answer. It can definitely be golfed a lot more. I will be posting an explanation soon.

```
K[_1Z;FNShQAkdNW&>K2>+*k@K_3d+*@K_2@K_3eK=K<K_3)~K[c-eKd-k@K_2kd;FNSeQW&>K2>N@K2=K>K3)aY+*hKN@K1;Y

```

Takes two comma delimited lists, separated by commas through stdin.

Try it here

```
K                  K=
 [  )              A List containing
  _1               Negative 1
  Z                Zero
FN                 For N in
 ShQ               Sorted first input
Akd                Double assign k and d
 N                 To N
 W                 While
  &                Logical And
   >K2             K>2
   >               Greater Than
    +*k@K_3d       K[-3]*k+d
    +              Plus
     *@K_2@K_3     K[-2]*K[-3]
     eK            K[-1]
  =K               K=
   <K_3            K[:-3]
  )                Close while loop
 ~K                K+=
  [      )         List constructor
   c               Float division
    -              Minus
     eK            K[-1]
     d             d
    -              Minus
     k             k
     @K_2          K[-2]
   k               k
   d               d
 ;                 End list and for loop
FN                 For N in
  SeQ              Sorted second input
  W                While loop
   &               Logical and
    >K2            K[2:]
    >              Greater than
     N             N
     @K2           K[2]
   =K              K=
   >K3             K[3:]
  )                Close while loop
  aY               Y.append - Y is empty list
   +               Plus
    *hKN           (K+1)*N
    @K1            K[1]
;                  Close out everything
Y                  Print Y

```
> 1 votes

# Answer
## Python, 214 bytes

```
S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b>H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x>H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R

```

Computes the convex hull by iterating through the input `a,b` in increasing `a` order. The convex hull is recorded in `H` using the format `-1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn` where `xi` is the x coordinate of the intersection of `a{i-1},b{i-1}` and `ai,bi`.

Then I iterate though the input `x`s in sorted order, truncating the convex hull to keep up as I go.

Everything is linear except for the sorts which are O(n lgn).

Run it like:

```
>>> print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}

```
> 10 votes

# Answer
# Haskell, 204 271 bytes

*Edit*: golfed much further by updating the convex hull as a list (but with the same complexity as the ungolfed version), using "split (x+1)" instead of "splitLookup x", and removing all qualified function calls like Predule.foldl.

This creates a function *f* which expects the list of (a,b) pairs and a list of x values. I guess it will be blown away length-wise by anything in the APL family using the same ideas, but here it goes:

```
import Data.Map
r=fromListWith max
[]%v=[(0,v)]
i@((p,u):j)%v|p>v#u=j%v|0<1=(v#u,v):i
(a,b)#(c,d)=1+div(b-d)(c-a)
o i x=(\(a,b)->a*x+b)$snd$findMax$fst$split(x+1)$r$foldl'(%)[]$r$zip(fmap fst i)i
f=fmap.o

```

Sample usage:

```
[1 of 1] Compiling Main             ( linear-min.hs, interpreted )
Ok, modules loaded: Main.
λ> f [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] [1..5]
[11,12,14,16,20]
λ> f [(1,20), (2,12), (3,11), (4,8)] [1..5]
[21,22,23,24,28]

```

It works in O(n log n) time; see below for analysis.

*Edit:* Here's an ungolfed version with the big-O analysis and a description of how it all works:

```
import Prelude hiding (null, empty)
import Data.Map hiding (map, foldl)

-- Just for clarity:
type X = Int
type Y = Int
type Line = (Int,Int)
type Hull = Data.Map.Map X Line
slope (a,b) = a

{-- Take a list of pairs (a,b) representing lines a*x + b and sort by
    ascending slope, dropping any lines which are parallel to but below
    another line.

    This composition is O(n log n); n for traversing the input and
    the output, log n per item for dictionary inserts during construction.
    The input and output are both lists of length <= n.
--}
sort :: [Line] -> [Line]
sort = toList . fromListWith max

{-- For lines ax+b, a'x+b' with a < a', find the first value of x
    at which a'x + b' exceeds ax + b. --}
breakEven :: Line -> Line -> X
breakEven p@(a,b) q@(a',b') = if slope p < slope q
                                 then 1 + ((b - b') `div` (a' - a))
                                 else error "unexpected ordering"

{-- Update the convex hull with a line whose slope is greater
    than any other lines in the hull.  Drop line segments
    from the hull until the new line intersects the final segment.
    split is used to find the portion of the convex hull
    to the right of some x value; it has complexity O(log n).
    insert is also O(log n), so one invocation of this
    function has an O(log n) cost.

    updateHull is recursive, but see analysis for hull to
    account for all updateHull calls during one execution.
--}
updateHull :: Line -> Hull -> Hull
updateHull line hull
    | null hull = singleton 0 line
    | slope line <= slope lastLine = error "Hull must be updated with lines of increasing slope"
    | hull == hull' = insert x line hull
    | otherwise = updateHull line hull''
    where (lastBkpt, lastLine) = findMax hull
          x = breakEven lastLine line
          hull' = fst $ x `split` hull
          hull'' = fst $ lastBkpt `split` hull

{-- Build the convex hull by adding lines one at a time,
    ordered by increasing slope.

    Each call to updateHull has an immediate cost of O(log n),
    and either adds or removes a segment from the hull. No
    segment is added more than once, so the total cost is
    O(n log n).
--}
hull :: [Line] -> Hull
hull = foldl (flip updateHull) empty . sort

{-- Find the highest line for the given x value by looking up the nearest
    (breakpoint, line) pair with breakpoint <= x.  This uses the neat
    function splitLookup which looks up a key k in a dictionary and returns
    a triple of:
        - The subdictionary with keys < k.
        - Just v if (k -> v) is in the dictionary, or Nothing otherwise
        - The subdictionary with keys > k.

    O(log n) for dictionary lookup.
--}
valueOn :: Hull -> X -> Y
valueOn boundary x = a*x + b
    where (a,b) = case splitLookup x boundary of
                    (_  , Just ab, _) -> ab
                    (lhs,       _, _) -> snd $ findMax lhs

{-- Solve the problem!

    O(n log n) since it maps an O(log n) function over a list of size O(n).
    Computation of the function to map is also O(n log n) due to the use
    of hull.
--}
solve :: [Line] -> [X] -> [Y]
solve lines = map (valueOn $ hull lines)

-- Test case from the original problem
test = [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] :: [Line]
verify = solve test [1..5] == [11,12,14,16,20]

-- Test case from comment
test' = [(1,20),(2,12),(3,11),(4,8)] :: [Line]
verify' = solve test' [1..5] == [21,22,23,24,28]

```
> 6 votes

# Answer
## Common Lisp - 648 ~~692~~

With an actual binary search.

```
(use-package :optima)(defun z(l e)(labels((i(n m)(/(-(cadr m)(cadr n))(-(car n)(car m))))(m(l)(match l((list* a b c r)(if(<(i a b)(i b c))(list* a(m(list* b c r)))(m(list* a c r))))(_ l)))(f(x &aux(x(cdr x)))`(+(*,(car x)x),(cadr x)))(g(s e)(let*((q(- e s))(h(+ s(floor q 2)))d)(if(> q 1)(let((v(g s h))(d(pop l)))`(if(< x,(car d)),v,(g(1+ h)e)))(cond((not(car (setq d (pop l))))(f d))((> q 0)`(if(< x,(car d)),(f d),(f(pop l))))(t(f d)))))))(setq l(loop for(a b)on(m(remove-duplicates(#3=stable-sort(#3# l'< :key'cadr)'< :key'car):key 'car)) by #'cdr collect`(,(when b(i a b)),(car a),(cadr a))))`(mapcar(eval(lambda(x),(g 0(1-(length l)))))',e)))

(z '((2 8) (4 0) (2 1) (1 10) (3 3) (0 4)) '(1 2 3 4 5))
=> (11 12 14 16 20)

```

# Explanation

Let *n* be the length of (a,b) and *k* the length of points.

* sort (a,b) by a, then b - *O(n.ln(n))*
* remove entries for duplicate `a` (parallel lines), retaining only the parallel line with the maximum `b`, which is always greater than the other (we prevent divisions by zero when computing intersections) - *O(n)*
* compress the result - *O(n)* : when we have consecutives elements (a0,b0) (a1,b1) (a2,b2) in the sorted list, such that the intersection point of (a0,b0) and (a1,b1) is *greater* than the one of (a1,b1) and (a2,b2), then (a1,b1) can safely be ignored.
* build a list of (x a b) elements, where *x* is the value up-to-which line *ax+b* is maximal for *x* (this list is sorted by *x* thanks to previous steps) - *O(n)*
* given that list, build a lambda that perform an interval check for its input and computes the maximum value - the binary tree is built in *O(n)* (see https://stackoverflow.com/a/4309901/124319). The binary search that will be applied has *O(ln(n))* complexity. With the example input, we build the following function (that function is then compiled):

```
(LAMBDA (X)
  (IF (< X 4)
      (IF (< X 2)
          (IF (< X -6)
              (+ (* 0 X) 4)
              (+ (* 1 X) 10))
          (+ (* 2 X) 8))
      (+ (* 4 X) 0)))

```
* apply that function for all elements - *O(k.ln(n))*

Resulting complexity: **O((n+k)(ln n)))** in a worst-case scenario.

We can't provide a complexity estimate for the total number of inputs (n+k), because *k* and *n* are independant. For example, if *n* is asymptotically negligeable w.r.t. *k*, then the total complexity would be *O(k)*.

But **if** we suppose that *k=O(n)*, then the resulting complexity is **O(n.ln(n))**.

## Other examples

```
(z '((1 10) (1 8) (1 7)) '(1 2 3 4 5))
=> (11 12 13 14 15)

```

And if we move backquotes to see what is being computed, we can see that we don't even need to make any comparison (once the first list is preprocessed):

```
(MAPCAR (LAMBDA (X) (+ (* 1 X) 10)) '(1 2 3 4 5))

```

Here is another example (taken from a comment):

```
(z '((1 20) (2 12) (3 11) (4 8)) '(1 2 3 4 5))
=> (21 22 23 24 28)

```

The effective function:

```
(MAPCAR
  (LAMBDA (X)
    (IF (< X 4)
        (+ (* 1 X) 20)
        (+ (* 4 X) 8)))
  '(1 2 3 4 5))

```
> 2 votes

---
Tags: code-golf, number, restricted-complexity
---


title: Finding all-but-one matches

text:
# Question
Title: Finding all-but-one matches
This challenge is about writing code to solve the following problem.

Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties.

* The substring of A should also match some substring of B with up to one substitution of a single character in the string.
* There should be no longer substring of A that satisfies the first property.

For example:

```
A = xxxappleyyyyyyy

B = zapllezzz

```

The substring `apple` with indices `4 8` (indexing from 1) would be a valid output.

**Score**

The score of your answer will be the sum of length of your code in bytes + the time in seconds it takes on my computer when run on strings A and B of length 1 million each.

**Testing and input**

I will run your code on two strings of length 1 million taken from the strings in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/

The input will be on standard in and will simply be two strings, separated by a new line.

**Languages and libraries**

You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also open source and freely available for Linux.

**My machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

# Answer
# C++ time: O(n^2), extra space: O(1)

It takes 0.2s to complete the 15K data on my machine.

To compile it, use:

```
g++ -std=c++11 -O3 code.cpp -o code

```

To run it, use:

```
./code < INPUT_FILE_THAT_CONTAINS_TWO_LINES_SPERATED_BY_A_LINE_BREAK

```

## Explaination

The idea is simple, for string `s1` and `s2`, we try to offset `s2` by `i`:

```
s1: abcabcabc
s2: bcabcab

```

When offset is 3:

```
s1: abcabcabc
s2:    bcabcab

```

Then, for each offset `i`, we perform a dynamic programing scan on `s1[i:]` and `s2`. For each `j`, let `f[j, 0]` be the maximum length `d` such that `s1[j - d:j] == s2[j - i - d: j - i]`. Similarly, let `f[j, 1]` be the maximum length `d` such that strings `s1[j - d:j]` and `s2[j - i - d:j - i]` differ by at most 1 character.

So for `s1[j] == s2[j - i]`, we have:

```
f[j, 0] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j]
f[j, 1] = f[j - 1, 1] + 1  // concat solution in f[j - 1, 1] and s1[j]

```

Otherwise:

```
f[j, 0] = 0  // the only choice is empty string
f[j, 1] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j] (or s2[j - i])

```

And:

```
f[-1, 0] = f[-1, 1] = 0

```

Since we only need f\[j - 1, :\] to calculate f\[j, :\], only O(1) extra space is used.

Finally, the max length will be:

```
max(f[j, 1] for all valid j and all i)

```

## Code

```
#include <string>
#include <cassert>
#include <iostream>

using namespace std;

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n1, n2;
    n1 = s1.size();
    n2 = s2.size();
    int max_len = 0;
    int max_end = -1;
    for(int i = 1 - n2; i < n1; i++) {
        int f0, f1;
        int max_len2 = 0;
        int max_end2 = -1;
        f0 = f1 = 0;
        for(int j = max(i, 0), j_end = min(n1, i + n2); j < j_end; j++) {
            if(s1[j] == s2[j - i]) {
                f0 += 1;
                f1 += 1;
            } else {
                f1 = f0 + 1;
                f0 = 0;
            }
            if(f1 > max_len2) {
                max_len2 = f1;
                max_end2 = j + 1;
            }
        }
        if(max_len2 > max_len) {
            max_len = max_len2;
            max_end = max_end2;
        }
    }
    assert(max_end != -1);
    // cout << max_len << endl;
    cout << max_end - max_len + 1 << " " << max_end << endl;
}

```
> 4 votes

# Answer
## C++

I tried thinking of a good algorithm to do this, but I'm a bit distracted today and couldn't think of anything that would work well. This runs at O(n^3) time, so it's veeeery slow. The other option I thought of could have been theoretically faster but would have taken O(n^2) space, and with inputs of 1M, it would have been worse even.

It's shameful, it takes 190 seconds for inputs of 15K. I'll try to improve it. **Edit:** Added multiprocessing. Now takes 37 seconds for 15K input on 8 threads.

```
#include <string>
#include <vector>
#include <sstream>
#include <chrono>
#include <thread>
#include <atomic>
#undef cin
#undef cout
#include <iostream>

using namespace std;

typedef pair<int, int> range;

int main(int argc, char ** argv)
{
    string a = "xxxappleyyyyyyy";
    string b = "zapllezzz";

    getline(cin, a);
    getline(cin, b);

    range longestA;
    range longestB;

    using namespace std::chrono;

    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    unsigned cores = thread::hardware_concurrency(); cores = cores > 0 ? cores : 1;

    cout << "Processing on " << cores << " cores." << endl;

    atomic<int> processedCount(0);

    vector<thread> threads;

    range* longestAs = new range[cores];
    range* longestBs = new range[cores];
    for (int t = 0; t < cores; ++t)
    {
        threads.push_back(thread([&processedCount, cores, t, &a, &b, &longestBs, &longestAs]()
        {
            int la = a.length();
            int l = la / cores + (t==cores-1? la % cores : 0);
            int lb = b.length();
            int aS = t*(la/cores);

            for (int i = aS; i < aS + l; ++i)
            {
                int count = processedCount.fetch_add(1);
                if ((count+1) * 100 / la > count * 100 / la)
                {
                    cout << (count+1) * 100 / la << "%" << endl;
                }
                for (int j = 0; j < lb; ++j)
                {
                    range currentB = make_pair(j, j);
                    bool letterChanged = false;
                    for (int k = 0; k + j < lb && k + i < la; ++k)
                    {
                        if (a[i + k] == b[j + k])
                        {
                            currentB = make_pair(j, j + k);
                        }
                        else if (!letterChanged)
                        {
                            letterChanged = true;
                            currentB = make_pair(j, j + k);
                        }
                        else
                        {
                            break;
                        }
                    }
                    if (currentB.second - currentB.first > longestBs[t].second - longestBs[t].first)
                    {
                        longestBs[t] = currentB;
                        longestAs[t] = make_pair(i, i + currentB.second - currentB.first);
                    }
                }
            }
        }));
    }

    longestA = make_pair(0,0);
    for(int t = 0; t < cores; ++t)
    {
        threads[t].join();

        if (longestAs[t].second - longestAs[t].first > longestA.second - longestA.first)
        {
            longestA = longestAs[t];
            longestB = longestBs[t];
        }
    }

    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);

    cout << "First substring at range (" << longestA.first << ", " << longestA.second << "):" << endl;
    cout << a.substr(longestA.first, longestA.second - longestA.first + 1) << endl;
    cout << "Second substring at range (" << longestB.first << ", " << longestB.second << "):" << endl;
    cout << b.substr(longestB.first, longestB.second - longestB.first + 1) << endl;
    cout << "It took me " << time_span.count() << " seconds for input lengths " << a.length() << " and " << b.length() <<"." << endl;

    char c;
    cin >> c;
    return 0;
}

```
> 2 votes

# Answer
#

Seems I was over complicating the problem with the previous solution. This is about 50% quicker (23 secs on 15k strings) than the previous one and pretty simple.

```
rm(list=ls(all=TRUE))
a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
matchLen=1
matchIndex=1
indexA = 1
repeat {
    i = 0
    repeat {
        srch = substring(a,indexA,indexA+matchLen+i)
        if (agrepl(srch,b,max.distance=list(insertions=0,deletions=0,substitutions=1)))
            i = i + 1
        else {
            if (i > 0) {
                matchLen = matchLen + i - 1
                matchIndex = indexA
            }
            break
        }
    }
    indexA=indexA+1
    if (indexA + matchLen > nchar(a)) break
}
c(matchIndex, matchLen + matchIndex)
print (substring(a,matchIndex, matchLen + matchIndex))
print(proc.time()-s)

```

This will never be a contender due to the language, but I did have a bit of fun doing it.
Not sure of the complexity of it, but over a couple of ~15k strings it takes 43 secs using a single thread. The largest portion of that was the sorting of the arrays. I tried some other libraries, but without significant improvement.

```
a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
N=nchar
S=substring
U=unlist
V=strsplit
A=N(a)
B=N(b)
a=S(a,1:A)
b=S(b,1:B)
a=sort(a,method="quick")
b=sort(b,method="quick")
print(proc.time()-s)
C=D=1
E=X=Y=I=0
repeat{
    if(N(a[C])>E && N(b[D])>E){
        for(i in E:min(N(a[C]),N(b[D]))){
            if (sum(U(V(S(a[C],1,i),''))==U(V(S(b[D],1,i),'')))>i-2){
                F=i
            } else break
        }
        if (F>E) {
            X=A-N(a[C])+1
            Y=X+F-1
            E=F
        }
        if (a[C]<b[D])
            C=C+1
            else
            D=D+1
    } else
        if(S(a[C],1,1)<S(b[D],1,1))C=C+1 else D=D+1
    if(C>A||D>B)break
}
c(X,Y)
print(proc.time()-s)

```

**Method:**

* Create a suffix array for each string
* Order the suffix arrays
* Step through each of the arrays in a staggered sort of way comparing the beginning of each
> 2 votes

---
Tags: code-challenge, fastest-code
---