title: Average an image

text:
# Question
Title: Average an image
Here is an image:

```
%%%%%%%%%%%%%
% Hello,    %
%    world! %
%%%%%%%%%%%%%

```

But it is too confusing for our undersized brains to compute. So we average it like this:

1. Split it into 2 x 2 sections. If the picture ends before a section is complete, imagine that there are spaces there.
2. Average the values of the ASCII characters in each section.
3. Round this average and convert it to an ASCII character.
4. Finally, replace all characters in the section to the average character.

Repeat this for all sections.

So the average of the image above looks like this:

```
$$>>II99######
$$>>II99######
$$##88KKGG####
$$##88KKGG####

```

**Your task: Write a program that takes an ASCII image as input and outputs its average.**

*Note Integers are rounded by function `floor(x+0.5)` or similar function - in other words, round halves upwards.*

# Answer
> 7 votes
# JavaScript (ES6), 159 bytes

```
document.write("<pre>"+(

// --- Solution ---
s=>s.replace(/./g,(c,i)=>(a=String.fromCharCode([t=0,1,l=s.search`
`+1,l+1].map(o=>t+=(n=s.charCodeAt(p=i+o-i%l%2-(i/l|0)%2*l))>32?n:32)|t/4+.5))+(++p%l?"":a))
// ----------------

)(`%%%%%%%%%%%%%
% Hello,    %
%    world! %
%%%%%%%%%%%%%`))
```

Takes a multiline string as input.

# Answer
> 4 votes
# MATL, ~~32~~ 30 bytes

```
2thZCO32XEoYmYocGZy2/Xke2t3$Y"

```

Input is a 2D char array, with rows separated by `;`.

**Try it online!**

### Explanation

```
2th     % push array [2 2]
ZC      % take input implicitly. Arrange distinct 2x2 blocks as columns, padding with 0
O32XE   % replace 0 by 32 (space)
oYm     % convert to number. Take mean of each column
Yoc     % round. Convert to char
GZy     % size of input in the 2 dimensions
2/Xk    % divide each dimension by 2, and round up to account for the padding
e       % reshape into image with half original size in each dimension
2t3$Y"  % replicate by a factor of 2 in each dimension. Display implicitly

```

# Answer
> 1 votes
# Pyth, 58 bytes

```
J2A,lQlhQV:0GJ
Ksm*C+csmsm?&<kG<bHC@@Qkb32hBdhBN4 .5J:0HJK

```

Try it online!

# Answer
> 1 votes
# Lua, ~~382~~ ~~376~~ ~~367~~ ~~353~~ 348 bytes

```
r="\n"o=... n=o:find(r)-1
l=n+n%2
a=o:gsub(r,(n~=l and" "or"")..r).." "..(#o//(l+1)%2<1 and r..(" "):rep(l)or"")print(a:gsub("()([^\n])(.)",function(p,m,c)t=p//(l+1)%2==0return string.char(math.floor((m:byte()+c:byte()+(t and a:sub(p+l+1,p+l+1)or a:sub(p-l,p-l)):byte()+(t and a:sub(p+l+2,p+l+2)or a:sub(p-l-1,p-l-1)):byte())/4+.5)):rep(2)end).."")

```

Works on the command line; accepts a string like the test case.

# Answer
> 0 votes
# Ruby, ~~235~~ 230 bytes

```
->i{i=i.split($/).map{|s|s.bytes+[s.size%2>0?32:0]}
w=i[0].size;h=i.size;h+=h%2;r=[[]]*h
(h/2).times{|y|y*=2
(w/2).times{|x|x*=2
c=((i[y][x,2]+(i[y+1]||[32]*w)[x,2]).inject(:+)/4.0).round.chr
r[y+1]=r[y]+=[c,c]}}
r.map(&:join)*$/}

```

# Answer
> 0 votes
# Python, 319 bytes

```
def f(A):
 L,R,S=len,range,A.split('\n')
 if L(S[0])%2:S=[s+' 'for s in S]
 m=L(S[0])
 if L(S)%2:S+=[' '*m]
 C=[chr(int(sum(map(ord,[S[i][j],S[i+1][j],S[i][j+1],S[i+1][j+1]]))/4.0+0.5))for i in R(0,L(S),2)for j in R(0,m,2)]
 f=t='';i=0
 while i<L(C):
    t+=C[i]*2
    i+=1
    if i%(m/2)<1:f+=(t+'\n')*2;t=''
 f=f[:-1]
 print f

```

2nd indentation is tabs.

Stuff before `C` is padding, `C` is the averaging process to single letters and rest is output

# Answer
> 0 votes
# Ruby, ~~180~~ ~~158~~ ~~148~~ ~~128 + 4~~ 124 + 4 = 128 bytes

Run with `$ ruby -nl` (+4 bytes for `-nl` flags). Takes input on STDIN.

```
y,x=x,$_.scan(/..?/)
(puts [x.zip(y).map{|c|(("%2s"*2%c).bytes.reduce(:+)/4.0).round.chr*2}*""]*2
y,x=x,[])if$.%2<1||$<.eof?

```

See it on ideone: http://ideone.com/brmP3L

## Ungolfed & explanation

Per `man ruby`, the `-n` flag "\[c\]auses Ruby to assume the following loop around your script ... `while gets ... end`". The special variable `$_` contains the last line read by `gets`. The `-l` flag removes the `\n` from each line, equivalent to `$_.chop!`.

```
y, x = x, $_.scan(/..?/)

( puts [
    x.zip(y).map {|c|
      (("%2s" * 2 % c).bytes.reduce(:+) / 4.0).round.chr * 2
    } * ""
  ] * 2
  y, x = x, []
) if $. % 2 < 1 || $<.eof?

```

The special variable `$.` is the number of lines that have been read so far, and `$<` is STDIN. The pairs of characters from every second line gets zipped with the previous line's. The format string `%2s%2s` combines the characters and pads it with spaces, then the characters are averaged.

# Answer
> 0 votes
## R, ~~433~~ 399 bytes

```
y=scan(,'',sep="\n")
h=nchar(y[1])
v=length(y)
p=function(x)paste(x,collapse="")
if(h%%2){y=sapply(y,function(x)paste0(x," "));h=h+1}
if(v%%2){y=c(y,p(rep(" ",h)));v=v+1}
z=matrix(unlist(lapply(y,function(x)strtoi(charToRaw(x),16))),ncol=h,byrow=T)
a=array(,c(v,h))
for(i in 1:(v/2)){for(j in 1:(h/2)){r=2*i-1:0;s=2*j-1:0;a[r,s]=rawToChar(as.raw(floor(mean(z[r,s])+.5)))}}
cat(apply(a,1,p),sep="\n")

```

I am getting desperate because this thing seems to be non-competing as heck. It prints

```
$$>>II99######
$$>>II99######
$$##88KKGG####
$$##88KKGG####

```

for the test case.

If you feed in the 7×3

```
%%%%%%%
Example
%%%%%%%

```

the output will be

```
BBFFJJ33
BBFFJJ33
######!!
######!!

```

because of the divisibility by 2 etc. etc.

Ungolfed:

```
y <- scan(, '', sep="\n") # Read STDIN and make it a character vector
h <- nchar(y[1]) # Get line width: how many chars per line
v <- length(y)   # Get array height: how many lines
p <- function(x) paste(x, collapse="") # A function that merges a vector of strings
if (h%%2) {y <- sapply(y, function(x) paste0(x, " ")); h=h+1} # If height is odd, add an empty line
if (v%%2) {y <- c(y, p(rep(" ", h))); v=v+1} # If width is odd, add an empty column
z <- matrix(unlist(lapply(y, function(x) strtoi(charToRaw(x), 16))), ncol=h, byrow=T)
# z now stores ASCII codes in a matrix; analogous to C strtol
a <- array(, dim=c(v,h)) # Reserve an array for the final result
for (i in 1:(v/2)) {
  for(j in 1:(h/2)) {
    r <- 2*i - 1:0 # Range of rows to average
    s <- 2*j - 1:0 # Range of columns to average
    a[r, s] <- rawToChar(as.raw(floor(mean(z[r, s]) + .5))) # Average, round, convert the ASCII codes
  } # and write them to the same place as in the original array
}
cat(apply(a, 1 , p), sep="\n") # Prints the array row-wise (index 1 for rows)

```

Just look how it handles this one gorgeous example (courtesy of chris.com):

```
                                                M$$$$$$$$$$$$$$$$RMMMMM8MMX
                                               <$$$$$$$$$$$$R????!!?MMMR$RMMh.
                                              :M$$$$$$$R?!!~~~~!!!!!!!MMM$$$$X
                                             :M$$$$$$$X!~~~   ~~~~~!!MM8$MM$$M!
                                           :!XM$$$$$$R!~~~~~  ~~~~~!!M$$$$$$$R!
                                          <!XM$$$$$$MR!~~~~ ~~ ~:!!<:!M$$$$$$$!
                                         '<!XMBQQRMMMMX:::~~~<!?!!~~!!!!$$$M!$X
                                         ~!!MM$$$$$M8R!!!?!:~!!M$f?!~~~!M$8HXX?
                                       <!!!XMM$$$$$MMRM$$!~!~~~~~~~~~~~!XM?!!M!
                                      <!!!!XMM$$M$$MM$M!!~~~ ~~~ ~  :~!!!X!~~R!
                                      !!!!XMMM$MMMMMMMM!!~~~ ~~~~  ~~~!!!X~~X!~
                                      '~~!!MMMM@MMMX!!MM!:~!!!~~  `~~~~!!XXXX~
                                        ~!!!XMMMMMMMM!MMM!~~~~:: <<~~~~!!$$R!
                                        '!!!!MM888M$MXMMM!!!!()!!~~~~~<!X$$$>
                                         ~!!!M???M$MRRMM$X<~!!!!~~~~~:!XN$$M
                                          ~!!!!!M$$$$@$@$$!!~~'  ~~:XH8$$$WR
                                          !!!!MM$RM$RRMMMM?t!:::XX8$$$$$$$$>
                                         ~~!!MMM$$$$$WX!!!!!!$$$$$$$RR$$$R"
                                       '  <!!MT!!!~~~!#BX!!!~~?T#?!!!M$$$X.
                                         <!!!!~~~~~~~~~?$!!!~~~~~~:!M$$$$MXH:
                                         ~~~~~~~~~~~ ~~!M&!!!~~~<!!X$$$$$$$R$W>
                                        <~~~~~~~~    '~~!$!!!!!!!!MMRM$R?#!!$N!
                                       x~~~~~~~~~    ~~~!MX!!!!!!?!M!M!~~:!!$B!
                                      M!~~~~~~~~~~  <~~:!$R!!!!!!!X!!!~~!!~!RR!
                                    :M!~~~~~~~~~~~ `~~~!X$R!!!!!!!!~~~:!!~~tMM!
                                   dR!!~~~~~~~~~~~~~~~~!M$R!!!!!!!~!!!!!!~~@$@~
                                  tR!!!~~~~~~~~~~~~~~~!!M$R!!!!!!!!!!!!!~~!$$E~
                                 d!~~~~~~~~~~~~~~~~~~~!!$$X!!!!!!!!!!!!~~~X$$!~
                                8R~~~~~~~~~~~~~~~~~~~<!X$$!!!!!!!!!!!<~~~!MR$~~
                               8$~~~~~~~!~~~~~~~~~~~<!!$$R!!!MX!!!!~~~~~<XR$!~<
                             :$$!~~~~~~!!~~~~~~~~~~~!!M$$!!!!MM!!!~~~~~<!8$F~<!
                          .x8$$$!~~~~::!~~~~~~~~~~~!!X$$$!!!!MM!!~~~~~!!M$R~~~!
               .::xxxnHW8$$$$$$$$$$$$$$!!~~~~~~~~~~<!@$$X!!!!MM~~~~~<!!X$E~~~~!
          :t$$$$$$$$$$$$$$$$$$$$$$$$$$$!!~~~~~~~~~~!X$$$X~!!!MX~~~~~!!X$$~~~~!!
       ~~~~#R$$$$$RR8$$$$$$$$$$$$$$$$$$!!~~~~~~~~~<!M$$$B~!!!M!~~~~~!X$$!~~~~!!
     ~~~~~~~~?$$$$$$$$$$$$$$$$$$$$$$$$$!!~~~~~~~~~!!$$$$$X!!X$!~~~~!X$$R~~~~<!f
  :~~~~~~~~~`~?$$$$$$$$$$$$$$$$$$$$$$$$!!~~~~~~~~!!X$$$$$$X!M$~~~<!W$$R~~~~~!!
 ~~~~~~~~~~  ~~M$$$$$$$$$$$$$$$$$$$$$$$!!~~~~~~~~!!M$$$$$$$$$Bid$$$$$$!~~~~~!!
!~~~~~~~~~~~~~~~$$$$$$$$$$$$$$$$$$$$$$$!~~~~~~~~~!!$$$$$$$$$$$$$$$$$$!~~~~~~!~
!~~~~~~~~~~~~~~~M$$$$$$$$$$$$$$$$$$$$$$!:~~~~~~~<!X$$$$$$$$$$$$$$$$$!~~~~~~!!
~~~~~~~~~~~~~~!!!$$$$$$$$$$$$$$$$$$$$$R!!:~~~~~~!!M$$$$$$$$$$$$$$"XR~~~~~~~!!
~~~~~~~~~~~~~!!!!$$$$$$$$$$$$$$$$$$$$$R!<!~~~~~!!!X$$$$$$$$$$$P~  !~~~~~~~!!
~~~~~~~~~~~<!!!!!$$$$$$$$$$$$$$$$$$$$$X!!~~~~~<!!!@#""`           ~~~~~~~~!!
~~~~~~~~~~~!!!!!X$$$$$$$$$$$$$$$$$$$$$X!~~~~~~!!!                '~~~~~~~!!
~~~~~~~~~~~<!!!!M$$$$$$$$$$$$$$$$$$$$$X!~~~~~!!!f                '~~~~~~<!!
~~~~~~~~~~~~~!!!$$$$$$$$$$$$$$$$$$$$$R!~~~~~~!!!                 '~~~~~<!!>
~~~~~~~~~~~~~~!!M$$$$$$$$$$$$$$$$$$$" !~~~~~!!!!                 ~~~~~~!!!
~~~~~~~~~~~~~~!!!$$$$$$$$$$$$$$$$$R~ .!~~~~~!!!                  ~~~~~!!!!
~~~~~~~~~~~~~~~!!!$$$$$$$$$$$$$*?!!!~!!~~~~<!!~                  ~~~~!!!!!
~~~~~~~~~~~~~~~~!!!$$$$$$$$*"~!!!!!!!!!~~~~!!!                  <~~~:!!!!!
!~~~~~~~~~~~~~~~~!!M$$$$#~~~~~~~~~~~!!~~~~~!!                   ~~~~~~~!!!
!<~~~~~~~~~~~~~~~!!!R"~~~~~~~~~~~~~!!!~~~~<!!                  '~~~~~~<!!
!<~~~~~~~~~~~~~~~~!!!~~~~~~~~~~~~~~!!~~~~~!!!X:                ~~~~~~~!!~
!!~~~~~~~~~~~~~~~~!!!!~~~~~~~~~~~~<!!~~~~!!!9$MX:              ~~~~~~<!!
!!!!!~~~~~~~~~~~~~!!!!:~~~~~~~~~~~!!~~~~~!!X$$$X!~            '~~~~~~!!~
!!!!!!~~~~~~~~~~~<!!!!!!~~~~~~~~~~!!~~~~!!!M$$R!~~~~          ~~~~~~!!!
!!!!!!!<~~~~~~~~~~~!!!!!!!:<:~~~~~!!~~~~!!X$$R!~~~~~~         ~~~~~~!!
!!!!!!!!~~~~~~~~~~<!!!!!!!!!!!!!<!!!~~~~!!@$$!~~~~~~~~        ~~~~~!!~
!!!!!!!!!~~~~~~~~:<!!!!X!!!!!!!!!!!!~~~!!X$$!~~~~~~~~~~~~:   '~~~~~!!
'!!!!!!!!!!~~~~~~~!!!!!!?!!!!!!!!!!!~~<!!M$M!~~~~~~~~~~~~~~~ '~~~~~!~
 !!!!!!!!!!\~~~~~~~>!!!!  `"MMMHX!!~~~<!!$R!~~~~~~~~~~~~~~~~~<~~~~!!
  !!!!!!!!!!<~~~~~<!!!!!   .::<!!!!<~~!!X8X!~~~~~~~~~~~~~~~~~~~~~~!!
  `X!!!!!!!!~~~~~!<!!!!!!!!!!!!~~!!\~~!!M$MX!:~~~~~~~~~~~~~~~~<!~~!>
  !X!!!!!!!!~!!:!!!!!!!!!!~!!!:~~!!~~~!!$M!~~!!<~~~~~~~~~~~~~~~!!!!
  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!:!!~~:!9R!~~~~~~!~~~~~~~~~~~~~~<!!f
 'CHAT!!!!!!!!!!!!!!!!!!!!!!!!!!!!~~~!!MX~~~~~~~~~~~~~~~~~~~~~~!!X

```

After:

```
                                              ''..$$$$$$$$$$662266??MMIIDDEE66
                                              ''..$$$$$$$$$$662266??MMIIDDEE66
                                            ''>>$$$$$$<<WWOOOOggPP88,,HH99..;;
                                            ''>>$$$$$$<<WWOOOOggPP88,,HH99..;;
                                          ..HH..$$$$EEPP~~ggOOggVV??22..$$$$00!!
                                          ..HH..$$$$EEPP~~ggOOggVV??22..$$$$00!!
                                        99((PP77;;CCII5555VVVV4433WWPP88..<<==66
                                        99((PP77;;CCII5555VVVV4433WWPP88..<<==66
                                      ..!!==MM$$..99DD8899gggg~~ggOOmm88HH@@PP!!
                                      ..!!==MM$$..99DD8899gggg~~ggOOmm88HH@@PP!!
                                      ::88EEMM@@MMPP77BB??gg88~~88__~~88==kkTT88
                                      ::88EEMM@@MMPP77BB??gg88~~88__~~88==kkTT88
                                        ::!!EEHHCCCCEEMM77PPQQ00??nn~~??0000((
                                        ::!!EEHHCCCCEEMM77PPQQ00??nn~~??0000((
                                        8888,,00??..BB@@11??PP""ggmmVV55//GG
                                        8888,,00??..BB@@11??PP""ggmmVV55//GG
                                        8888,,MM00..HHEE77==((//>>));;$$00))
                                        8888,,MM00..HHEE77==((//>>));;$$00))
                                      ""''((,,\\PP~~ggII00!!~~ddXX''88$$;;<<''
                                      ""''((,,\\PP~~ggII00!!~~ddXX''88$$;;<<''
                                        VV~~~~~~ggOO99gg..!!88PP((EE::00++..;;((
                                        VV~~~~~~ggOO99gg..!!88PP((EE::00++..;;((
                                      BB~~~~~~~~gg  VVmm--;;!!!!))::,,gg??88CC!!
                                      BB~~~~~~~~gg  VVmm--;;!!!!))::,,gg??88CC!!
                                  11??PP~~~~~~~~~~__~~PP;;::!!!!!!PPPP''PPll@@88
                                  11??PP~~~~~~~~~~__~~PP;;::!!!!!!PPPP''PPll@@88
                                11YYPPgg~~~~~~~~~~~~~~!!..;;!!!!!!!!!!88~~00,,OO
                                11YYPPgg~~~~~~~~~~~~~~!!..;;!!!!!!!!!!88~~00,,OO
                              &&KK~~~~~~gg~~~~~~~~~~FF0000!!,,//!!88VV~~MMEEPP??
                              &&KK~~~~~~gg~~~~~~~~~~FF0000!!,,//!!88VV~~MMEEPP??
                          ::..$$PP~~mm??gg~~~~~~~~gg//..##!!777788~~~~??33OOnn!!
                          ::..$$PP~~mm??gg~~~~~~~~gg//..##!!777788~~~~??33OOnn!!
          <<""&&//NNLL::))$$$$$$$$$$$$##PP~~~~~~~~VV77$$TT!!77hh~~~~((==CC~~gg!!
          <<""&&//NNLL::))$$$$$$$$$$$$##PP~~~~~~~~VV77$$TT!!77hh~~~~((==CC~~gg!!
    88gg~~ggMM$$$$;;))$$$$$$$$$$$$$$$$##PP~~~~~~~~((..$$OO!!;;PP~~gg==00gg~~??22
    88gg~~ggMM$$$$;;))$$$$$$$$$$$$$$$$##PP~~~~~~~~((..$$OO!!;;PP~~gg==00gg~~??22
88mm~~~~~~gg__LL$$$$$$$$$$$$$$$$$$$$$$##PP~~~~~~PP::$$$$$$0066rrAA00$$\\~~~~!!
88mm~~~~~~gg__LL$$$$$$$$$$$$$$$$$$$$$$##PP~~~~~~PP::$$$$$$0066rrAA00$$\\~~~~!!
PP~~~~~~~~~~~~~~..$$$$$$$$$$$$$$$$$$$$##mm~~~~~~??00$$$$$$$$$$$$$$$$99~~~~gg88
PP~~~~~~~~~~~~~~..$$$$$$$$$$$$$$$$$$$$##mm~~~~~~??00$$$$$$$$$$$$$$$$99~~~~gg88
~~~~~~~~~~~~gg!!##$$$$$$$$$$$$$$$$$$$$::..~~~~gg!!;;$$$$$$$$$$FF""RR~~~~~~88
~~~~~~~~~~~~gg!!##$$$$$$$$$$$$$$$$$$$$::..~~~~gg!!;;$$$$$$$$$$FF""RR~~~~~~88
~~~~~~~~~~VV!!!!00$$$$$$$$$$$$$$$$$$$$==gg~~~~((!!))!!00        ""~~~~~~gg!!
~~~~~~~~~~VV!!!!00$$$$$$$$$$$$$$$$$$$$==gg~~~~((!!))!!00        ""~~~~~~gg!!
~~~~~~~~~~nn88!!..$$$$$$$$$$$$$$$$$$00FF~~~~PP!!22              $$~~~~nn((((
~~~~~~~~~~nn88!!..$$$$$$$$$$$$$$$$$$00FF~~~~PP!!22              $$~~~~nn((((
~~~~~~~~~~~~~~!!..$$$$$$$$$$$$$$$$FF$$PP~~~~!!!!                OO~~~~88!!
~~~~~~~~~~~~~~!!..$$$$$$$$$$$$$$$$FF$$PP~~~~!!!!                OO~~~~88!!
~~~~~~~~~~~~~~gg!!##$$$$$$&&::$$))!!88PP~~VV!!88                VV~~??!!!!
~~~~~~~~~~~~~~gg!!##$$$$$$&&::$$))!!88PP~~VV!!88                VV~~??!!!!
??~~~~~~~~~~~~~~PP,,//QQgg~~~~~~~~gg!!~~~~??!!                ""~~~~~~??!!
??~~~~~~~~~~~~~~PP,,//QQgg~~~~~~~~gg!!~~~~??!!                ""~~~~~~??!!
((~~~~~~~~~~~~~~~~!!88~~~~~~~~~~~~??PP~~gg!!66@@''            OO~~~~nn!!88
((~~~~~~~~~~~~~~~~!!88~~~~~~~~~~~~??PP~~gg!!66@@''            OO~~~~nn!!88
!!!!88~~~~~~~~~~nn!!!!??~~~~~~~~~~!!~~~~88::$$<<ggOO          hh~~~~8888
!!!!88~~~~~~~~~~nn!!!!??~~~~~~~~~~!!~~~~88::$$<<ggOO          hh~~~~8888
!!!!!!((~~~~~~~~~~??!!!!!!..??PPVV!!~~~~!!88//gg~~~~gg        ~~~~gg88
!!!!!!((~~~~~~~~~~??!!!!!!..??PPVV!!~~~~!!88//gg~~~~gg        ~~~~gg88
##!!!!!!88gg~~~~mm((!!//))!!!!!!!!!!~~??::..PP~~~~~~~~~~mmOO$$~~~~PP88
##!!!!!!88gg~~~~mm((!!//))!!!!!!!!!!~~??::..PP~~~~~~~~~~mmOO$$~~~~PP88
  !!!!!!!!00nn~~~~FF!!!!  44DD==//??~~((55;;~~~~~~~~~~~~~~~~nn~~~~!!
  !!!!!!!!00nn~~~~FF!!!!  44DD==//??~~((55;;~~~~~~~~~~~~~~~~nn~~~~!!
  LL!!!!!!!!ggVV88((!!!!!!88!!VVPPGG~~!!99QQ??VV~~~~~~~~~~~~~~??PP((
  LL!!!!!!!!ggVV88((!!!!!!88!!VVPPGG~~!!99QQ??VV~~~~~~~~~~~~~~??PP((
""3366!!!!!!!!!!!!!!!!!!!!!!!!!!''ggVV22RR~~~~~~gg~~~~~~~~~~~~VV//22
""3366!!!!!!!!!!!!!!!!!!!!!!!!!!''ggVV22RR~~~~~~gg~~~~~~~~~~~~VV//22

```

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


title: Print alphabet without using strings

text:
# Question
Title: Print alphabet without using strings
The challenge: Write a script to print the alphabet, but you can't use any ASCII strings in your program. Unicode escape characters are allowed (if thats what you call them).

External libraries are allowed, as long as a link to the documentation is provided, and an online example if possible.

As this is , the answer with the shortest byte count will win!

# Answer
# Silicon, 1 byte

```
A

```

`A` is preinitialized to the alphabet. Output is implicit.
> 1 votes

# Answer
## Neoscript, 27 bytes

```
{|65:[]:90:map(chr):fuse()}

```

Lambda returning the alphabet.
> 3 votes

---
Tags: code-golf
---


title: Testing for admissible sequences

text:
# Question
Title: Testing for admissible sequences
Executive summary: test whether an input sequence of integers is "admissible", meaning that it doesn't cover all residue classes for any modulus.

## What is an "admissible" sequence?

Given an integer m ≥ 2, the *residue classes modulo m* are just the m possible arithmetic progressions of common difference m. For example, when m=4, the 4 residue classes modulo 4 are

```
..., -8, -4, 0, 4, 8, 12, ...
..., -7, -3, 1, 5, 9, 13, ...
..., -6, -2, 2, 6, 10, 14, ...
..., -5, -1, 3, 7, 11, 15, ...

```

The kth residue class consists of all the integers whose remainder upon dividing by m equals k. (as long as one defines "remainder" correctly for negative integers)

A sequence of integers a1, a2, ..., ak is *admissible modulo m* if it fails to intersect at least one of the residue classes. For example, {0, 1, 2, 3} and {-4, 5, 14, 23} are *not* admissible modulo 4, but {0, 1, 2, 4} and {0, 1, 5, 9} and {0, 1, 2, -3} *are* admissible modulo 4. Also, {0, 1, 2, 3, 4} is *not* admissible modulo 4, while {0, 1, 2} *is* admissible modulo 4.

Finally, a sequence of integers is simply *admissible* if it is admissible modulo m for every integer m ≥ 2.

## The challenge

Write a program or function that takes a sequence of integers as input, and returns a (consistent) Truthy value if the sequence is admissible and a (consistent) Falsy value if the sequence is not admissible.

The input sequence of integers can be in any reasonable format. You may assume that the input sequence has at least two integers. (You may also assume that the input integers are distinct if you want, though it probably doesn't help.) You must be able to handle positive and negative integers (and 0).

Usual scoring: the shortest answer, in bytes, wins.

### Sample input

The following input sequences should each give a Truthy value:

```
0 2
-1 1
-100 -200
0 2 6
0 2 6 8
0 2 6 8 12
0 4 6 10 12
-60 0 60 120 180
0 2 6 8 12 26
11 13 17 19 23 29 31
-11 -13 -17 -19 -23 -29 -31

```

The following input sequences should each give a Falsy value:

```
0 1
-1 4
-100 -201
0 2 4
0 2 6 10
0 2 6 8 14
7 11 13 17 19 23 29
-60 0 60 120 180 240 300

```

### Tips

* Note that any sequence of 3 or fewer integers is automatically admissible modulo 4. More generally, a sequence of length k is automatically admissible modulo m when m \> k. It follows that testing for admissibility really only requires checking a finite number of m.
* Note also that 2 divides 4, and that any sequence that is admissible modulo 2 (that is, all even or all odd) is automatically admissible modulo 4. More generally, if m divides n and a sequence is admissible modulo m, then it is automatically admissible modulo n. To check admissibility, it therefore suffices to consider only prime m if you wish.
* If a1, a2, ..., ak is an admissible sequence, then a1+c, a2+c, ..., ak+c is also admissible for any integer c (positive or negative).

## Mathematical relevance (optional reading)

Let a1, a2, ..., ak be a sequence of integers. Suppose that there are infinitely many integers n such that n+a1, n+a2, ..., n+ak are all prime. Then it's easy to show that a1, a2, ..., ak must be admissible. Indeed, suppose that a1, a2, ..., ak is not admissible, and let m be a number such that a1, a2, ..., ak is not admissible modulo m. Then no matter what n we choose, one of the numbers n+a1, n+a2, ..., n+ak must be a multiple of m, hence cannot be prime.

The *prime k-tuples conjecture* is the converse of this statement, which is still a wide open problem in number theory: it asserts that if a1, a2, ..., ak is an admissible sequence (or *k-tuple*), then there should be infinitely many integers n such that n+a1, n+a2, ..., n+ak are all prime. For example, the admissible sequence 0, 2 yields the statement that there should be infinitely many integers n such that both n and n+2 are prime, this is the *twin primes conjecture* (still unproved).

# Answer
# Jelly, 10 bytes

```
JḊðḶḟ%@ð€Ạ

```

Try it online! or run all test cases.

```
               Input: L.
JḊ             Range of [2..len(L)].
  ð    ð€      For x in [2..len(L)]:
   Ḷ             [0..x-1] (residue classes)
    ḟ              without elements from
     %@            L % x.
         Ạ     All truthy (non-empty)?

```
> 4 votes

# Answer
# Brachylog, ~~25~~ ~~24~~ 19 bytes

**5 bytes thanks to Karl Napf.**

```
~~lybb'(eM-yA,?:[M]z:%aodA)~~
~~l:2'(eM-yA,?:[M]z:%aodA)~~
l:2'(eMg:?rz:%adlM)

```

Try it online!

Verify all testcases!

```
l:2'(eMg:?rz:%adlM)
l:2                  Temp = [2:length(input)]
   '(             )  true if the following cannot be proven:
     eM                  M is an element of the interval
                         indicated by Temp, i.e. from 2
                         to the length of input inclusive,
       g:?rz:%adlM       every element of input modulo M
                         de-duplicated has length M.

```
> 7 votes

# Answer
# Python, ~~61~~ 60 bytes

```
q=lambda l,d=2:d>len(l)or q(l,d+1)&(len({v%d for v in l})<d)

```

All test cases on **ideone**

Edit: replaced logical and with bitwise & to save one byte
> 4 votes

# Answer
# Python, ~~67~~ 64 bytes

As unnamed lambda:

```
lambda N:all(len({i%m for i in N})<m for m in range(2,len(N)+1))

```
* Edit1: replaced `set()` with `{}`
* Edit2: dont't need square brackets around generator in `all(...)`
* Edit3: As pointed out by Jonathan Allan, `range` must go up to `len(N)+1`

Old code as function (96 bytes):

```
def f(N):
 for m in range(2,len(N)+1):
    if len(set(i%m for i in N))==m:return False
 return True

```
> 2 votes

# Answer
## JavaScript (ES6), 59 bytes

```
a=>a.every((_,i)=>!i++|new Set(a.map(e=>(e%i+i)%i)).size<i)

```

Uses @KarlNapf's Set of remainders trick.
> 2 votes

# Answer
# MATL, 11 bytes

```
"X@QGy\un>v

```

Truthy is an array (column vector) containing all ones. Falsy is an array containing at least one zero. You can check these definitions using this link.

Try it online! Or verify all test cases: truthy, falsy (slightly modified code, each case produces a horizontal vector for clarity).

### Explanation

```
"       % Take input array. For each; i.e. repeat n times, where n is arrray size
  X@Q   %   Push iteration index plus 1, say k. So k is 2 in the first iteration,
        %   3 in the second, ... n+1 in the last. Actually we only need 2, ..., n;
        %   but the final n+1 doesn't hurt
  G     %   Push input again
  y     %   Duplicate k onto the top of the stack
  \     %   Modulo. Gives vector of remainders of input when divided by k
  un    %   Number of distinct elements
  >     %   True if that number is smaller than k
  v     %   Vertically concatenate with previous results
        % End for each. Implicitly display

```
> 2 votes

# Answer
# Mathematica, 51 bytes

```
And@@Table[Length@Union@Mod[#,i]<i,{i,2,Length@#}]&

```
> 2 votes

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


title: Minimal Word Search

text:
# Question
Title: Minimal Word Search
Last week, we worked to create the shortest 1-D string using the top 10,000 words in the English language. Now, lets try the same challenge in 2D!

What you need to do is to take all of the above words, and put them in a rectangle as small as possible, allowing for overlaps. For example, if your words were `["ape","pen","ab","be","pa"]`, then a possible rectangle would be:

```
.b..
apen

```

The above rectangle would give a score of 5.

Rules:

* Overlapping multiple letters in a word is allowed
* Words can go in any of the 8 directions
* Words cannot wrap around
* You can use any character for the empty locations

You need to create a word search that contains these top 10,000 words in English (according to Google). **Your score is equal to the number of characters in your word search** (excluding unused characters). If there is a tie, or if a submission is proven to be optimal, then the submission that is first posted wins.

# Answer
# Rust, ~~31430~~ 30081 used characters

This is a greedy algorithm of sorts: we start with an empty grid, and repeatedly add the word that can be added with the fewest new letters, with ties broken by preferring longer words. To make this run quickly, we maintain a priority queue of candidate word placements (implemented as a vector of vectors of deques, with a vector for each number of new letters, containing a deque for each word length). For each newly added letter, we enqueue all candidate placements that run through that letter.

Compile and run with `rustc -O wordsearch.rs; ./wordsearch < google-10000-english.txt`. On my laptop, this runs in 70 seconds, using 531 MiB RAM.

The output fits in a rectangle with 248 columns and 253 rows.

### Code

```
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::prelude::*;
use std::iter::once;
use std::vec::Vec;

type Coord = i16;
type Pos = (Coord, Coord);
type Dir = u8;
type Word = u16;

struct Placement { word: Word, dir: Dir, pos: Pos }

static DIRS: [Pos; 8] =
    [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)];

fn fit(grid: &HashMap<Pos, u8>, (x, y): Pos, d: Dir, word: &String) -> Option<usize> {
    let (dx, dy) = DIRS[d as usize];
    let mut n = 0;
    for (i, c) in word.bytes().enumerate() {
        if let Some(c1) = grid.get(&(x + (i as Coord)*dx, y + (i as Coord)*dy)) {
            if c != *c1 {
                return None;
            }
        } else {
            n += 1;
        }
    }
    return Some(n)
}

struct PlacementQueue { queue: Vec<Vec<VecDeque<Placement>>>, extra: usize }

impl PlacementQueue {
    fn new() -> PlacementQueue {
        return PlacementQueue { queue: Vec::new(), extra: std::usize::MAX }
    }

    fn enqueue(self: &mut PlacementQueue, extra: usize, total: usize, placement: Placement) {
        while self.queue.len() <= extra {
            self.queue.push(Vec::new());
        }
        while self.queue[extra].len() <= total {
            self.queue[extra].push(VecDeque::new());
        }
        self.queue[extra][total].push_back(placement);
        if self.extra > extra {
            self.extra = extra;
        }
    }

    fn dequeue(self: &mut PlacementQueue) -> Option<Placement> {
        while self.extra < self.queue.len() {
            let mut subqueue = &mut self.queue[self.extra];
            while !subqueue.is_empty() {
                let total = subqueue.len() - 1;
                if let Some(placement) = subqueue[total].pop_front() {
                    return Some(placement);
                }
                subqueue.pop();
            }
            self.extra += 1;
        }
        return None
    }
}

fn main() {
    let stdin = std::io::stdin();
    let all_words: Vec<String> =
        stdin.lock().lines().map(|l| l.unwrap()).collect();
    let words: Vec<&String> = {
        let subwords: HashSet<&str> =
            all_words.iter().flat_map(|word| {
                (0..word.len() - 1).flat_map(move |i| {
                    (i + 1..word.len() - (i == 0) as usize).map(move |j| {
                        &word[i..j]
                    })
                })
            }).collect();
        all_words.iter().filter(|word| !subwords.contains(&word[..])).collect()
    };
    let letters: Vec<Vec<(usize, usize)>> =
        (0..128).map(|c| {
            words.iter().enumerate().flat_map(|(w, word)| {
                word.bytes().enumerate().filter(|&(_, c1)| c == c1).map(move |(i, _)| (w, i))
            }).collect()
        }).collect();

    let mut used = vec![false; words.len()];
    let mut remaining = words.len();
    let mut grids: Vec<HashMap<Pos, u8>> = Vec::new();

    while remaining != 0 {
        let mut grid: HashMap<Pos, u8> = HashMap::new();
        let mut queue = PlacementQueue::new();
        for (w, word) in words.iter().enumerate() {
            if used[w] {
                continue;
            }
            queue.enqueue(0, word.len(), Placement {
                pos: (0, 0),
                dir: 0,
                word: w as Word
            });
        }

        while let Some(placement) = queue.dequeue() {
            if used[placement.word as usize] {
                continue;
            }
            let word = words[placement.word as usize];
            if let None = fit(&grid, placement.pos, placement.dir, word) {
                continue;
            }
            let (x, y) = placement.pos;
            let (dx, dy) = DIRS[placement.dir as usize];
            let new_letters: Vec<(usize, u8)> = word.bytes().enumerate().filter(|&(i, _)| {
                !grid.contains_key(&(x + (i as Coord)*dx, y + (i as Coord)*dy))
            }).collect();
            for (i, c) in word.bytes().enumerate() {
                grid.insert((x + (i as Coord)*dx, y + (i as Coord)*dy), c);
            }
            used[placement.word as usize] = true;
            remaining -= 1;

            for (i, c) in new_letters {
                for &(w1, j) in &letters[c as usize] {
                    if used[w1] {
                        continue;
                    }
                    let word1 = words[w1];
                    for (d1, &(dx1, dy1)) in DIRS.iter().enumerate() {
                        let pos1 = (
                            x + (i as Coord)*dx - (j as Coord)*dx1,
                            y + (i as Coord) - (j as Coord)*dy1);
                        if let Some(extra1) = fit(&grid, pos1, d1 as Dir, word1) {
                            queue.enqueue(extra1, word1.len(), Placement {
                                pos: pos1,
                                dir: d1 as Dir,
                                word: w1 as Word
                            });
                        }
                    }
                }
            }
        }
        grids.push(grid);
    }

    let width = grids.iter().map(|grid| {
        grid.iter().map(|(&(x, _), _)| x).max().unwrap() -
            grid.iter().map(|(&(x, _), _)| x).min().unwrap() + 1
    }).max().unwrap();
    print!(
        "{}",
        grids.iter().flat_map(|grid| {
            let x0 = grid.iter().map(|(&(x, _), _)| x).min().unwrap();
            let y0 = grid.iter().map(|(&(_, y), _)| y).min().unwrap();
            let y1 = grid.iter().map(|(&(_, y), _)| y).max().unwrap();
            (y0..y1 + 1).flat_map(move |y| {
                (x0..x0 + width).map(move |x| {
                    *grid.get(&(x, y)).unwrap_or(&('.' as u8)) as char
                }).chain(once('\n').take(1))
            })
        }).collect::<String>()
    );
}

```
> 8 votes

# Answer
# C++, 27243 character grid (248x219, 50.2% filled)

<sup>(Posting this as a new answer because I'd like to keep the 1D bound I originally posted as a reference)</sup>

This ~~blatantly rips off~~ is heavily inspired by @AndersKaseorg's answer in its main structure, but has a couple of tweaks. First, I use my original program to merge strings until the best available overlap is just 3 characters. Then I use the method AndersKaseorg describes to progressively fill a 2D grid using these generated strings. The constraints are a little different too: it still tries to add the fewest characters each time, but ties are broken by favouring square grids first, then small grids, and finally by adding the longest word.

The behaviour it displays is to alternate between periods of filling in space and rapidly expanding the grid (unfortunately it ran out of words just after a rapid expansion stage, so there's a lot of blank space around the edges). I suspect with some tweaking of the cost function it could be made to get better than 50% space filling.

There are 2 executables here (to avoid the need to re-run the whole process when iteratively improving the algorithm). The output of one can be piped directly into the other:

```
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>

std::size_t calcOverlap(const std::string &a, const std::string &b, std::size_t limit, std::size_t minimal) {
    std::size_t la = a.size();
    for(std::size_t p = std::min(std::min(la, b.size()), limit + 1); -- p > minimal; ) {
        if(a.compare(la - p, p, b, 0, p) == 0) {
            return p;
        }
    }
    return 0;
}

bool isSameReversed(const std::string &a, const std::string &b) {
    std::size_t l = a.size();
    if(b.size() != l) {
        return false;
    }
    for(std::size_t i = 0; i < l; ++ i) {
        if(a[i] != b[l-i-1]) {
            return false;
        }
    }
    return true;
}

int main(int argc, const char *const *argv) {
    // Usage: prog [<stop_threshold>]

    std::size_t stopThreshold = 3;

    if(argc >= 2) {
        char *check;
        long v = std::strtol(argv[1], &check, 10);
        if(check == argv[1] || v < 0) {
            std::cerr
                << "Invalid stop threshold. Should be an integer >= 0"
                << std::endl;
            return 1;
        }
        stopThreshold = v;
    }

    std::vector<std::string> words;

    // Load all words from input and their reverses (words can be backwards now)
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
        std::reverse(word.begin(), word.end());
        words.push_back(std::move(word));
    }

    std::cerr
        << "Input word count: " << words.size() << std::endl;

    // Remove all fully subsumed words

    for(auto p = words.begin(); p != words.end(); ) {
        bool subsumed = false;
        for(auto i = words.begin(); i != words.end(); ++ i) {
            if(i == p) {
                continue;
            }
            if(i->find(*p) != std::string::npos) {
                subsumed = true;
                break;
            }
        }
        if(subsumed) {
            p = words.erase(p);
        } else {
            ++ p;
        }
    }

    std::cerr
        << "After subsuming checks: " << words.size()
        << std::endl;

    // Sort words longest-to-shortest (not necessary but doesn't hurt. Makes finding maxlen a tiny bit easier)
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t maxlen = words.front().size();

    // Repeatedly combine most-compatible words until we reach the threshold
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 2) {
        auto bestA = words.begin();
        auto bestB = -- words.end();
        std::size_t bestOverlap = 0;
        for(auto p = ++ words.begin(), e = words.end(); p != e; ++ p) {
            if(p->size() - 1 <= bestOverlap) {
                continue;
            }
            for(auto q = words.begin(); q != p; ++ q) {
                std::size_t overlap = calcOverlap(*p, *q, bestPossible, bestOverlap);
                if(overlap > bestOverlap && !isSameReversed(*p, *q)) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap && !isSameReversed(*p, *q)) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        if(bestOverlap <= stopThreshold) {
            break;
        }
        std::string newStr = std::move(*bestA);
        newStr.append(*bestB, bestOverlap, std::string::npos);

        if(bestA == -- words.end()) {
            words.pop_back();
            *bestB = std::move(words.back());
            words.pop_back();
        } else {
            *bestB = std::move(words.back());
            words.pop_back();
            *bestA = std::move(words.back());
            words.pop_back();
        }

        // Remove any words which are now in the result (forward or reverse)
        // (would not be necessary if we didn't have the reversed forms too)
        std::string newRev = newStr;
        std::reverse(newRev.begin(), newRev.end());
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos || newRev.find(*p) != std::string::npos) {
                std::cerr << "Now subsumes: " << *p << std::endl;
                p = words.erase(p);
            } else {
                ++ p;
            }
        }

        std::cerr
            << "Words remaining: " << (words.size() + 1)
            << " Latest combination: (" << bestOverlap << ") " << newStr
            << std::endl;

        words.push_back(std::move(newStr));
        words.push_back(std::move(newRev));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

    std::cerr
        << "After merging: " << words.size()
        << std::endl;

    // Remove all fully subsumed words (i.e. reversed words)

    for(auto p = words.begin(); p != words.end(); ) {
        bool subsumed = false;
        std::string rev = *p;
        std::reverse(rev.begin(), rev.end());
        for(auto i = words.begin(); i != words.end(); ++ i) {
            if(i == p) {
                continue;
            }
            if(i->find(*p) != std::string::npos || i->find(rev) != std::string::npos) {
                subsumed = true;
                break;
            }
        }
        if(subsumed) {
            p = words.erase(p);
        } else {
            ++ p;
        }
    }

    std::cerr
        << "After subsuming: " << words.size()
        << std::endl;

    // Sort words longest-to-shortest for display
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t len = 0;
    for(const auto &word : words) {
        std::cout
            << word
            << std::endl;
        len += word.size();
    }
    std::cerr
        << "Total size: " << len
        << std::endl;
    return 0;
}

```

```
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <limits>

class vec2 {
public:
    int x;
    int y;

    vec2(void) : x(0), y(0) {};
    vec2(int x, int y) : x(x), y(y) {}

    bool operator ==(const vec2 &b) const {
        return x == b.x && y == b.y;
    }

    vec2 &operator +=(const vec2 &b) {
        x += b.x;
        y += b.y;
        return *this;
    }

    vec2 &operator -=(const vec2 &b) {
        x -= b.x;
        y -= b.y;
        return *this;
    }

    vec2 operator +(const vec2 b) const {
        return vec2(x + b.x, y + b.y);
    }

    vec2 operator *(const int b) const {
        return vec2(x * b, y * b);
    }
};

class box2 {
public:
    vec2 tl;
    vec2 br;

    box2(void) : tl(), br() {};
    box2(vec2 a, vec2 b)
        : tl(std::min(a.x, b.x), std::min(a.y, b.y))
        , br(std::max(a.x, b.x) + 1, std::max(a.y, b.y) + 1)
    {}

    void grow(const box2 &b) {
        if(b.tl.x < tl.x) {
            tl.x = b.tl.x;
        }
        if(b.br.x > br.x) {
            br.x = b.br.x;
        }
        if(b.tl.y < tl.y) {
            tl.y = b.tl.y;
        }
        if(b.br.y > br.y) {
            br.y = b.br.y;
        }
    }

    bool intersects(const box2 &b) const {
        return (
            ((tl.x >= b.br.x) != (br.x > b.tl.x)) &&
            ((tl.y >= b.br.y) != (br.y > b.tl.y))
        );
    }

    box2 &operator +=(const vec2 b) {
        tl += b;
        br += b;
        return *this;
    }

    int width(void) const {
        return br.x - tl.x;
    }

    int height(void) const {
        return br.y - tl.y;
    }

    int maxdim(void) const {
        return std::max(width(), height());
    }
};

template <> struct std::hash<vec2> {
    std::size_t operator ()(const vec2 &o) const {
        return std::hash<int>()(o.x) + std::hash<int>()(o.y) * 997;
    }
};

template <class A,class B> struct std::hash<std::pair<A,B>> {
    std::size_t operator ()(const std::pair<A,B> &o) const {
        return std::hash<A>()(o.first) + std::hash<B>()(o.second) * 31;
    }
};

class word_placement {
public:
    vec2 start;
    vec2 dir;
    box2 bounds;
    const std::string *word;

    word_placement(vec2 start, vec2 dir, const std::string *word)
        : start(start)
        , dir(dir)
        , bounds(start, start + dir * (word->size() - 1))
        , word(word)
    {}

    word_placement(vec2 start, const word_placement &copy)
        : start(copy.start + start)
        , dir(copy.dir)
        , bounds(copy.bounds)
        , word(copy.word)
    {
        bounds += start;
    }

    word_placement(const word_placement &copy)
        : start(copy.start)
        , dir(copy.dir)
        , bounds(copy.bounds)
        , word(copy.word)
    {}
};

class word_placement_links {
public:
    std::unordered_set<word_placement*> placements;
    std::unordered_set<std::pair<char,word_placement*>> relativePlacements;
};

class grid {
public:
    std::vector<std::string> wordCache; // Just a block of memory for our pointers to reference
    std::unordered_map<vec2,char> state;
    std::unordered_set<word_placement*> placements;
    std::unordered_map<const std::string*,word_placement_links> wordPlacements;
    std::unordered_map<char,std::unordered_set<word_placement*>> relativeWordPlacements;
    box2 bound;

    grid(const std::vector<std::string> &words) {
        wordCache = words;
        std::vector<vec2> directions;
        directions.emplace_back(+1,  0);
        directions.emplace_back(+1, +1);
        directions.emplace_back( 0, +1);
        directions.emplace_back(-1, +1);
        directions.emplace_back(-1,  0);
        directions.emplace_back(-1, -1);
        directions.emplace_back( 0, -1);
        directions.emplace_back(+1, -1);

        wordPlacements.reserve(wordCache.size());
        placements.reserve(wordCache.size());
        relativeWordPlacements.reserve(64);

        std::size_t total = 0;
        for(const std::string &word : wordCache) {
            word_placement_links &p = wordPlacements[&word];
            p.placements.reserve(8);
            auto &rp = p.relativePlacements;
            std::size_t l = word.size();
            rp.reserve(l * directions.size());
            for(int i = 0; i < l; ++ i) {
                for(const vec2 &d : directions) {
                    word_placement *rwp = new word_placement(d * -i, d, &word);
                    rp.emplace(word[i], rwp);
                    relativeWordPlacements[word[i]].insert(rwp);
                }
            }
            total += l;
        }
        state.reserve(total);
    }

    const std::string *find_word(const std::string &word) const {
        for(const std::string &w : wordCache) {
            if(w == word) {
                return &w;
            }
        }
        throw std::string("Failed to find word in cache");
    }

    void remove_word(const std::string *word) {
        const word_placement_links &links = wordPlacements[word];
        for(word_placement *p : links.placements) {
            placements.erase(p);
            delete p;
        }
        for(auto &p : links.relativePlacements) {
            relativeWordPlacements[p.first].erase(p.second);
            delete p.second;
        }
        wordPlacements.erase(word);
    }

    void remove_placement(word_placement *placement) {
        wordPlacements[placement->word].placements.erase(placement);
        placements.erase(placement);
        delete placement;
    }

    bool check_placement(const word_placement &placement) const {
        vec2 p = placement.start;
        for(const char c : *placement.word) {
            auto i = state.find(p);
            if(i != state.end() && i->second != c) {
                return false;
            }
            p += placement.dir;
        }
        return true;
    }

    int check_new(const word_placement &placement) const {
        int n = 0;
        vec2 p = placement.start;
        for(const char c : *placement.word) {
            n += !state.count(p);
            p += placement.dir;
        }
        return n;
    }

    void check_placements(const box2 &b) {
        for(auto i = placements.begin(); i != placements.end(); ) {
            if(!b.intersects((*i)->bounds) || check_placement(**i)) {
                ++ i;
            } else {
                i = placements.erase(i);
            }
        }
    }

    void add_placement(const vec2 p, const word_placement &relative) {
        word_placement check(p, relative);
        if(check_placement(check)) {
            word_placement *wp = new word_placement(check);
            placements.insert(wp);
            wordPlacements[relative.word].placements.insert(wp);
        }
    }

    void place(word_placement placement) {
        remove_word(placement.word);
        int overlap = 0;
        for(const char c : *placement.word) {
            char &g = state[placement.start];
            if(g == '\0') {
                g = c;
                for(const word_placement *rp : relativeWordPlacements[c]) {
                    add_placement(placement.start, *rp);
                }
            } else if(g != c) {
                throw std::string("New word changes an existing character!");
            } else {
                ++ overlap;
            }
            placement.start += placement.dir;
        }
        bound.grow(placement.bounds);
        check_placements(placement.bounds);

        std::cerr
            << draw('.', "\n")
            << "Added " << *placement.word << " (overlap: " << overlap << ")"
            << ", Grid: " << bound.width() << "x" << bound.height() << " of " << state.size() << " chars"
            << ", Words remaining: " << wordPlacements.size()
            << std::endl;
    }

    int check_cost(box2 b) const {
        b.grow(bound);
        return (
            ((b.maxdim() - bound.maxdim()) << 16) |
            (b.width() + b.height() - bound.width() - bound.height())
        );
    }

    void add_next(void) {
        int bestNew = std::numeric_limits<int>::max();
        int bestCost = std::numeric_limits<int>::max();
        int bestLen = 0;
        word_placement *best = nullptr;
        for(word_placement *p : placements) {
            int n = check_new(*p);
            if(n <= bestNew) {
                int l = p->word->size();
                int cost = check_cost(box2(p->start, p->start + p->dir * l));
                if(n < bestNew || cost < bestCost || (cost == bestCost && l < bestLen)) {
                    bestNew = n;
                    bestCost = cost;
                    bestLen = l;
                    best = p;
                }
            }
        }
        if(best == nullptr) {
            throw std::string("Failed to find join to existing blob");
        }
        place(*best);
    }

    void fill(void) {
        while(!placements.empty()) {
            add_next();
        }
    }

    std::string draw(char blank, const std::string &linesep) const {
        std::string result;
        result.reserve((bound.width() + linesep.size()) * bound.height());
        for(int y = bound.tl.y; y < bound.br.y; ++ y) {
            for(int x = bound.tl.x; x < bound.br.x; ++ x) {
                auto c = state.find(vec2(x, y));
                result.push_back((c == state.end()) ? blank : c->second);
            }
            result.append(linesep);
        }
        return result;
    }

    box2 bounds(void) const {
        return bound;
    }

    int chars(void) const {
        return state.size();
    }
};

int main(int argc, const char *const *argv) {
    std::vector<std::string> words;

    // Load all words from input
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(std::move(word));
    }

    std::cerr
        << "Input word count: " << words.size() << std::endl;

    // initialise grid
    grid g(words);

    // add first word (order of input file means this is longest word)
    g.place(word_placement(vec2(0, 0), vec2(1, 0), g.find_word(words.front())));

    // add all other words
    g.fill();

    std::cout << g.draw('.', "\n");

    int w = g.bounds().width();
    int h = g.bounds().height();
    int n = g.chars();
    std::cerr
        << "Final grid: " << w << "x" << h
        << " with " << n << " characters"
        << " (" << (n * 100.0 / (w * h)) << "% filled)"
        << std::endl;
    return 0;
}

```

And finally, the result:

---

Alternative result (after fixing a couple of bugs in the program which were biasing certain directions and tweaking the cost function, I got a more compact but less optimal solution): 29275 chars, 198x195 (75.8% filled):

Again I haven't done much to optimise these programs, so it takes a while. But you can watch as it fills in the grid, which is quite hypnotic.
> 6 votes

# Answer
# C++, 34191 character "grid" (with minimal human intervention, 6 or 7 can easily be saved)

This should be taken more as a bound for the 2D case, because the answer is still a 1D string. It's just my code from the previous challenge, but with the new ability to reverse any string. This gives us a lot more scope for combining words (particularly because it caps the worst case of non-overlapping superstrings to 26; one for each letter of the alphabet).

For some slight 2D visual appeal, it puts linebreaks in the result if it can do so for free (i.e. between 0-overlap words).

Pretty slow (still no caching). Here's the code:

```
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::size_t calcOverlap(const std::string &a, const std::string &b, std::size_t limit, std::size_t minimal) {
    std::size_t la = a.size();
    for(std::size_t p = std::min(std::min(la, b.size()), limit + 1); -- p > minimal; ) {
        if(a.compare(la - p, p, b, 0, p) == 0) {
            return p;
        }
    }
    return 0;
}

bool isSameReversed(const std::string &a, const std::string &b) {
    std::size_t l = a.size();
    if(b.size() != l) {
        return false;
    }
    for(std::size_t i = 0; i < l; ++ i) {
        if(a[i] != b[l-i-1]) {
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<std::string> words;

    // Load all words from input and their reverses (words can be backwards now)
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
        std::reverse(word.begin(), word.end());
        words.push_back(std::move(word));
    }

    std::cerr
        << "Input word count: " << words.size() << std::endl;

    // Remove all fully subsumed words

    for(auto p = words.begin(); p != words.end(); ) {
        bool subsumed = false;
        for(auto i = words.begin(); i != words.end(); ++ i) {
            if(i == p) {
                continue;
            }
            if(i->find(*p) != std::string::npos) {
                subsumed = true;
                break;
            }
        }
        if(subsumed) {
            p = words.erase(p);
        } else {
            ++ p;
        }
    }

    std::cerr
        << "After subsuming checks: " << words.size()
        << std::endl;

    // Sort words longest-to-shortest (not necessary but doesn't hurt. Makes finding maxlen a tiny bit easier)
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t maxlen = words.front().size();

    // Repeatedly combine most-compatible words until we have only 1 word left (+ its reverse)
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 2) {
        auto bestA = words.begin();
        auto bestB = -- words.end();
        std::size_t bestOverlap = 0;
        for(auto p = ++ words.begin(), e = words.end(); p != e; ++ p) {
            if(p->size() - 1 <= bestOverlap) {
                continue;
            }
            for(auto q = words.begin(); q != p; ++ q) {
                std::size_t overlap = calcOverlap(*p, *q, bestPossible, bestOverlap);
                if(overlap > bestOverlap && !isSameReversed(*p, *q)) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap && !isSameReversed(*p, *q)) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        std::string newStr = std::move(*bestA);
        if(bestOverlap == 0) {
            newStr.push_back('\n');
        }
        newStr.append(*bestB, bestOverlap, std::string::npos);

        if(bestA == -- words.end()) {
            words.pop_back();
            *bestB = std::move(words.back());
            words.pop_back();
        } else {
            *bestB = std::move(words.back());
            words.pop_back();
            *bestA = std::move(words.back());
            words.pop_back();
        }

        // Remove any words which are now in the result (forward or reverse)
        // (would not be necessary if we didn't have the reversed forms too)
        std::string newRev = newStr;
        std::reverse(newRev.begin(), newRev.end());
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos || newRev.find(*p) != std::string::npos) {
                std::cerr << "Now subsumes: " << *p << std::endl;
                p = words.erase(p);
            } else {
                ++ p;
            }
        }

        std::cerr
            << "Words remaining: " << (words.size() + 1)
            << " Latest combination: (" << bestOverlap << ") " << newStr
            << std::endl;

        words.push_back(std::move(newStr));
        words.push_back(std::move(newRev));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

    std::cerr
        << "After non-trivial merging: " << words.size()
        << std::endl;

    if(words.size() == 2 && !isSameReversed(words.front(), words.back())) {
        // must be 2 palindromes, so just join them
        words.front().append(words.back());
    }

    std::string result = words.front();

    std::cout
        << result
        << std::endl;
    std::cerr
        << "Word size: " << result.size() // Note this number includes newlines, so to get the grid size according to the rules, subtract newlines manually
        << std::endl;
    return 0;
}

```

Result: http://pastebin.com/UTe2WMcz (4081 characters less than the previous challenge)

It's pretty clear that some trivial savings can be made by putting the `xd` and `wv` lines vertical, intersecting the monster line. Then `hhidetautisbneudui` can intersect with the `d`, and `lxwwwowaxocnnaesdda` with `w`. This saves 4 characters. `nbcllilhn` can be substituted in to an existing `s` overlap (if one can be found) to save another 2 (or just 1 if no such overlap exists and it must be added vertically instead). Finally `mjjrajaytq` can be added vertically somewhere to save 1. This means with minimal human intervention, 6–7 characters can be saved from the result.

I would like to get this into 2D with the following method, but I'm struggling to find a way to implement it without making the algorithm O(n^4), which is quite impractical to compute!

1. Run the algorithm as above, but stop short when the overlaps reach 1 character
2. Repeatedly:
    1. Find a group of 4 words which can be arranged into a rectangle
    2. Add as many words as possible on top of this rectangle where each word overlaps at least 2 characters of the current shape (check all 8 directions) — this is the only stage where we can actually get an advantage over the current code
3. Combine the resulting grids and lone-words looking for single-letter overlaps each time
> 2 votes

# Answer
# PHP

this one does the job theroratically; but 10000 are probably too many words for recursion. The script is running now. (still ran 24 hours later)
works fine on small directories, but I may make an iterative version next week.

`$f=array("pen","op","po","ne","pro","aaa","abcd","dcba");
will output`abcdapenaropao..`although this is not an optimal result (scoring was changed ... I´m working on a generator). One optimal result is this:`open.r.a.o.adcba\`

It is also not very fast; only removes substrings and sorts the remains by length,
the rest is brute force: try to fit the words into a rectangle, try on a larger rectangle if it fails.

btw: The substring part needs 4.5 minutes on my machine for the large directory
and cuts it down to 6,190 words; the sort on them takes 11 seconds.

```
$f=file('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt');
// A: remove substrings - forward or reversed
$s=join(' ',$f);
$haystack="$s ".strrev($s);
foreach($f as$w)
{
    $r=strrev($w=trim($w)); // remove trailing line break and create reverse word
    if(!preg_match("%$w\w|\w$w%",$haystack)
        // no substr match ... now: is the reverse word in the list?
        // if so, keep only the lower one (ascii values)
        &!($w>$r&&strstr($s,$r))
        // strstr does NOT render the reverse substr regex obsolete:
        // this is only executed for $w=abc, not for $w=bca!
    )
        $g[]=$w
    ;
}

// B: sort the words by length
usort($g,function($a,$b){return strlen($a)-strlen($b);});

// C1: function to fit $words into $map
function gomap($words,$map)
{
    $h=count($map);$w=strlen($map[0]);
    $len=strlen($word=array_pop($words));
    // $x,$y=position; $d=0:horizontal, $d=1:vertical; $r=0: word, $r=1: reverse word
    for($x=$w-$len;$x>=0;$x--)for($y=$h-$len;$y>=0;$y--)for($d=0;$d<2;$d++)for($r=0;$r<2;$r++)
    {
        // does the word fit there?
        $drow=$r?strrev($word):$word;
        for($ok=1,$i=0;$ok&$i<$len;$i++)
            $ok=in_array($map[$y+$d*$i][$x+$i-$d*$i], [' ',$drow[$i]])
        ;
        // it does, paint it
        if($ok)
        {
            for($i=0;$i<$len;$i++)
                $map[$y+$d*$i][$x+$i-$d*$i]=$drow[$i];
            if(!count($words))      // this was the last word: return map
                return $map;
            else                    // there are more words: recurse
                if ($ok=gomap($words,$map))
                    return $ok;
            // no fit, try next position
        }
    }
    return 0;
}

// C2: rectangle loop
for($h=0;++$h;)for($w=0;$w++<$h;)   // define a rectangle
{
    // and try to fit the words in there
    if($map=gomap($g,
        array_fill(0,$h,str_repeat(' ',$w))
    ))
    {
        // words fit; output and break loops
        echo '<pre>',implode("\n",$map),'</pre>';
        break 2;
    }
}

```
> 0 votes

---
Tags: string, code-challenge, grid
---


title: Langford strings

text:
# Question
Title: Langford strings
# Challenge description

A **Langford string** of order `N` is defined as follows:

* The length of the string is equal to `2*N`,
* The string contains first `N` letters of the English alphabet, each letter appearing twice,
* For each pair of the same letters, there are `M` letters between them, where `M` is that letter's position in the alphabet (`A = 1`, `B = 2`, `...`, `Z = 26`).

For instance, the only two possible Langford strings of order `3` are `BCABAC` and `CABACB`. As you can see, in both of these strings there is one letter between two `A`'s, two letters between `B`'s and three letters between `C`'s. Given a positive integer `N`, output all Langford strings of order `N` (in any reasonable format: print them one by one separated by a newline, return a list/array...).

# Sample inputs / outputs

```
3: [CABACB, BCABAC]
4: [DACABDCB, BCDBACAD]
5: # no output #
7: [GCFBECBDGFEADA, GBFCBDECGFDAEA, GBDFBCEDGCFAEA, GCAFACDEGBFDBE, GADAFCEDGCBFEB, GACAFDCEGBDFBE, GDAEAFDCGEBCFB, GBDEBFCDGECAFA, EGBFCBEDCGFADA, CGDFCBEDBGFAEA, EGDAFAEDCGBFCB, EGBCFBECDGAFAD, AGABFDBECGDFCE, EGADAFECDGBCFB, AGABEFBCDGECFD, BGDBCEFDCGAEAF, FBGDBCEFDCGAEA, BFGBAEADFCGEDC, CFGACADEFBGDBE, EAGAFBEDBCGFDC, BCGBFCEADAGFED, DAGAFDBECBGFCE, EBGCBFECDAGAFD, CEGDCFBEDBGAFA, CEGBCFBEDAGAFD, BDGBCFDECAGAFE, EFAGACEDFCBGDB, DFAGADEBFCBGEC, AFAGBDEBFCDGEC, DFAGADCEFBCGBE, ECFGBCEBDFAGAD, DEFGADAECFBGCB, CDFGCBDEBFAGAE, EBDGBFEDACAGFC, CDEGCFDAEABGFB, AEAGCDFECBDGBF, FAEAGCDFECBDGB, DFCEGDCBFEBAGA, BFCBGDCEFADAGE, ECFDGCEBDFBAGA, DAFAGDCEBFCBGE, BCFBGCDEAFADGE, AEAFGBDEBCFDGC, ADAFGCDEBCFBGE, AFACEGDCFBEDBG, BFCBEGCDFAEADG, EBFDBGECDFACAG, BEFBCGDECFADAG, EBDFBGEDCAFACG, AEAFCGDECBFDBG, AEADFGCEDBCFBG, ADAEFGDBCEBFCG]
12: # <216288 strings> #

```

# Notes

* Langford strings of order `N` can only be produced when `N ≡ 0 (mod 4)` or `N ≡ 3 (mod 4)`,
* You can use both lower-case and upper-case letters,
* You may use subsequent numbers as well (`012...` or `123...` instead of `ABC...`)
* Order of strings in which they should appear as output is unspecified,
* Output can be quite lengthy (for instance, there are over 5 trillion distinct Langford strings of order `20`), so your program doesn't actually need to output them all, but it has to work in theory (given enough time and memory).
* This challenge has been taken from /r/dailyprogrammer, all credit goes to /u/XenophonOfAthens

# Answer
> 3 votes
## CJam (23 bytes)

```
{,2*e!{__f{\a/1=,(}=},}

```

Online demo. This is an anonymous block (function) which takes input on the stack and leaves output on the stack in the form of an array of arrays of 0-based sequential integers.

# Answer
> 2 votes
# Brachylog, 43 bytes

```
:1fd.
ybB:1jp.,B:[.]z:2a
:3f-+$_~h?
t:.m~h?

```

Try it online!

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


title: The infinitely admissable sequence

text:
# Question
Title: The infinitely admissable sequence
In this challenge we'll compute an infinite minimal admissible sequence.

The sequence for this challenge starts with `a(1) = 1`.

We continue this sequence by finding `a(n)` as the smallest possible number such that `a(n) > a(n-1)` and for every prime `p`, the set `{a(i) mod p : 1 ≤ i ≤ n}` has at most `p-1` elements.

Write a program or function that takes positive integer `n` and outputs `a(n)`. Shortest code in bytes wins.

---

Example:

`a(6)` is `19`, rather than, say `17` because `[1,3,7,9,13,19]` (the previous terms) is admissible while `[1,3,7,9,13,17]` is not.

`[1,3,7,9,13,17]` is not admissible, because for the base `3`, after taking the modulo of each term with `3`, we obtain `[1,0,1,0,1,2]` which contains every non-negative number smaller than `3`, our chosen base.

For `[1,3,7,9,13,19]` however, it would be impossible to come up with a base such that the list after modulo contains every non-negative integer smaller than such base.

---

Reference:

---

Testcases:

```
a(1) = 1
a(2) = 3
a(3) = 7
a(4) = 9
a(5) = 13
a(6) = 19
a(7) = 21
a(8) = 27
a(9) = 31
a(10) = 33
a(100) = 583

```

# Answer
> 2 votes
# Brachylog, 44 bytes

```
-:[1]r:[1]cit.
t<gX=:?rc.'(l:2eLg:.rz:%adlL)

```

Try it online!

`100` takes about a minute here, so be patient if you want to try `100`.

### Predicate 0 (main predicate)

```
-:[1]r:[1]cit.
-:[1]r:[1]c     create array [[1], input-1, 1]
           i    iterate: [1] as input, iterate (input-1) times, predicate 1
            t.  last element is the output

```

### Predicate 1 (auxiliary predicate)

```
t<gX=:?rc.'(l:2eLg:.rz:%adlL)
t<                              last element of input < Temp
  gX                            [Temp] = X
   X=                           Assign a value to X, which assigns
                                a value to Temp
   X :?rc.                      [Input,X] concatenated is output
         .'(                )   The following about the output cannot
                                be proven:
            l:2eL                   L is a number between 2 and length
                                    of output, inclusive
                Lg:.rz:%a           every element of output, taken modulo L,
                         dlL        after removing duplicates, has length L

```

# Answer
> 1 votes
## ES6, 91 bytes

```
(n,a=[i=1])=>a[n]||f(n,a.every((_,j)=>(j+=2)>new Set(b.map(e=>e%j)).size,b=[...a,+++])?b:a)

```

Zero-indexed. Due to its recursive nature, only works for the first 450 terms, but computes a(99)=583 almost instantly.

---
Tags: code-golf, sequence, number-theory
---


title: Verify a ballot triangle

text:
# Question
Title: Verify a ballot triangle
A *ballot number*, which we'll label *B*, is the number of ways of arranging the numbers from 1 through B(B+1)/2 into a triangle, such that each row and column is in any increasing order. The first four ballot numbers are:

```
a(0) = 1
a(1) = 1
a(2) = 1
a(3) = 2

```

`a(3)` is 2, which means that there are 2 ways of arranging the numbers from 1 to `3(3+1)/2 = 6` in such a triangle:

```
1          1
2 3    or  2 4
4 5 6      3 5 6

```

See the OEIS sequence entry for more details.

Your challenge, given a ballot triangle, is to verify its correctness. If it satisfies the conditions of a ballot triangle (rows and columns increasing), you should output how many *other* ways (excluding the one in the input) there are to arrange the triangle correctly. If the input triangle is incorrectly constructed, you should output nothing.

Trailing newlines are allowed.

## Input

A triangle of numbers, which may or may not be a valid ballot triangle. For example:

```
1
2 3
4 5 6

1
10 5
9 8 2
7 6 4 3

1
3 2

9
2 11
14 3 5
12 8 1 7
15 13 10 4 6

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21

```

## Output

If the input is a valid ballot triangle, the remaining number of ways to arrange the same numbers in a valid ballot triangle. If the input is not a valid ballot triangle, nothing. For example, the inputs above produce these outputs (`<nothing>` is a placeholder for an actual empty output):

```
1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

```

## Scoring

This is : as usual, lowest byte-count wins. Tiebreaker is earliest posted.

# Answer
# Jelly, 20 bytes

```
;Zµ⁼Ṣ€
ẋÇFŒ!ṁ€⁸ÇÐfL’

```

For valid ballot triangles, run time and memory usage are at least **O(n!)**, where **n** is the number of entries of the triangle. Invalid ones are recognized by crashing, thus printing nothing.

Try it online!

### Test run

Locally, I was able to verify that **a(4)** is calculated correctly.

```
$ time jelly eun ';Zµ⁼Ṣ€¶ẋÇFŒ!ṁ€⁸ÇÐfL’' '[1],[2,3],[4,5,6],[7,8,9,10]'
11

real    6m9.829s
user    6m7.930s
sys     0m2.579s

```

### How it works

```
;Zµ⁼Ṣ€         Helper link. Argument: T (triangular array)

 Z             Zip/transpose T.
;              Concatenate the original and the transposed copy.
  µ            Begin a new monadic chain, with the previous result (R) as argument.
    Ṣ€         Sort each array in R.
   ⁼           Test for equality with R.
               This returns 1 if T is a ballot triangle, 0 if not.

ẋÇFŒ!ṁ€⁸ÇÐfL’  Main link. Argument: A (triangular array)

 Ç             Call the helper link with argument A.
ẋ              Repeat A that many times.
               This yields an empty array if A is not a ballot triangle.
  F            Flatten the result.
   Œ!          Generate all permutations of the digits of A.
     ṁ€⁸       Mold each permutation like A, i.e., give it triangular form.
               This crashes if permutation array is empty.
        ÇÐf    Filter; keep permutations for which the helper link returns 1.
           L’  Compute the length and decrement it.

```
> 4 votes

# Answer
# Brachylog, 44 bytes

```
{:{o?}a,?z:2a},?ly+yb:3flw
p~c.:laBtybB,.:1&

```

Try it online!

This runs in double-exponential time, so for truthy testcases you would need to believe me that it theoretically produces the correct result, for triangles with length greater than or equal to `3`.

You can still test for falsey testcases, those should terminate rather quickly.
> 3 votes

# Answer
## JavaScript (ES6), 143 bytes

```
a=>a.some((b,i)=>b.some((c,j)=>c<b[j-1]||i&&c<a[i-1][j]))?'':(f=n=>n<2||n*f(n-1),g=(n,m=f(n*n+n>>1))=>n<2?m:g(--n,m*f(n)/f(n+n+1)),g(a.length))

```

Searches the triangle for an invalid entry and then uses a recursive formulation of the formula in OEIS to calculate the result.
> 2 votes

---
Tags: code-golf, math, sequence, combinatorics
---


# Question
Title: One out of Infinity: Interpolating polynomials
For this challenge, **when given a list of (x,y) points your submission needs to output a polynomial function that goes through all of them**.

For example, if your points were `[(0,0), (2,5)]`, you could return `y = 2.5*x` or `y = x + 1/4x^2`.

* All points passed in will consist only of integers
* Two points will never have the same `y` value
* Your function be of the form `y = a*x^n + ... b*x^m`. Reducing of terms is allowed.
* Constants (the exponent and coefficient) can either be in decimal or fractional form. Decimals should be accurate to at least 3 decimal places
* You should be able to handle an arbitrary number of points
* Output must be a string starting with "y=". Whitespace anywhere in the string is fine.

# Test cases

Note, the given output is not the only valid output, just one of the possibilities.

```
(1,4)                                                    -> y=x+3
(0,0), (1,8)                                             -> y=8x
(0,6), (-1,90)                                           -> y=-84x+6
(6,4), (70,4), (-1,-6)                                   -> y=−10/497x^2+760/497x−316/71
(4,5), (5,6), (6,7)                                      -> y=x+1
(20,1), (-20,1), (0,5), (10, 4), (11,12), (17,4), (2,4)  -> y=488137/10424165400x^6−643187/473825700x^5−87561839/10424165400x^4+550999039/1042416540x^3−21590713027/5212082700x^2+300110420/52120827x+5

```

This is a , so make your answers as short as possible in your favorite language!

# Answer
# MATL, 38 bytes

```
ynq3$ZQ'y=' '%+fx^%i'btn:qP&vYDh1J3-h)

```

Inputs are an array with the *x* values and an array with the *y* values.

**Try it online!**

```
y          % Inplicitly take the two inputs, and push another copy of the first
nq         % Get its length minus 1. This is the required polynomial degree.
3$ZQ       % Coefficients of polynomial fitted to those data (`polyfit`)
'y='       % Push this string
'%+fx^%i'  % Push format string for `sprintf`
b          % Bubble up the polynomial coefficients to the top of the stack
tn:qP      % Duplicate and produce [n n-1  ... 0] where n is the polynomial degree.
           % These are the exponents
&v         % Concatenate vertically. This gives a 2D array with the coefficients in
           % the first row and the exponents in the second
YD         % Apply `sprintf` to this array with previous format string. The array
           % is read in column-major order: down, then across
h          % Concatenate 'y=' and formatted string representing the polynomial
1J3-h)     % The string ends in '...x^0'. Remove last three chars to delete this.
           % Implicitly display

```
> 3 votes

# Answer
# Python2 + sympy, 61 58 bytes

```
from sympy import*;print interpolate(input("y="),var("x"))

```
> 1 votes

# Answer
# Matlab (with Symbolic Toolbox), 52 bytes

Using builtins for calculating an interpolation polynomial, and then converting it to a symbolc expression for pretty printing and back to a string for the actual output. This function takes two lists of coordinates, e.g. `[6,70,-1]` and `[4,4,-6]` for the fourth test case.

```
 @(x,y)['y=',char(poly2sym(polyfit(x,y,numel(x)-1)))]

```
> 1 votes

---
Tags: code-golf, polynomials
---


title: Right and tfeL truncatable primes

text:
# Question
Title: Right and tfeL truncatable primes
A right-truncatable prime is a prime where every prefix is a prime (in base 10). A left-truncatable prime is exactly the opposite, where every postfix is a prime (primes that start with 0 aren't allowed). Both of these sequences are finite (There are only 83 Right-truncatables, while there are 4260 Left-truncatables).

You need to write a program that accepts a single number as input, and produces the *n*th right-truncatable prime. However, when the program is read **arranged backwards**, it should produce the *n*th left-truncatable prime.

To arrange a program backwards, we split the program into words, then reverse the order of the words. A word can consist of any number of characters.

For example, if the following was your program:

```
hello world
1234567890

```

The following would all be allowed as possible backwards arrangements:

Splitting on each character:

```
0987654321
dlrow olleh

```

Splitting on whitespace:

```
1234567890
world hello

```

Splitting arbitrarily (pipes added for clarity):

```
hel|lo w|orld
1|23456|7|8|90

908723456orld
1lo whel

```

When arranging your program backwards, all whitespace must be considered and reversed, just like any other character.

## Forward test inputs:

```
1:  2
2:  3
21: 379
60: 239933
83: 73939133

```

## Backward test inputs:

```
1:    2
2:    3
39:   647
187:  29173
4260: 357686312646216567629137

```

Programs should be able to run in a reasonable amount of time (less than a minute)

This is a , so the program with the fewest bytes wins!

# Answer
# Jelly, ~~26~~ 23 bytes

## Forward

```
Ñ¶p9¶7ÆR2ĿV€$ÆPÐf$ÐĿFị@

```

Try it online!

### Words

`Ñ`  `p` `9`  `7ÆR2ĿV€$ÆPÐf$ÐĿFị@`

## Backward

```
7ÆR2ĿV€$ÆPÐf$ÐĿFị@¶9p¶Ñ

```

Try it online!

### Words

`7ÆR2ĿV€$ÆPÐf$ÐĿFị@`  `9` `p`  `Ñ`

## How it works

All Jelly programs consist of links (Jelly's take on functions), which are separated by linefeeds or pilcrows (). The last of them is the *main link*; it is called automatically when the program is run.

The forward program works as follows.

```
Ñ                   Helper link. Unused.

p9                  Helper link. Take the Cartesian product with [1, ..., 9].

7ÆR2ĿV€$ÆPÐf$ÐĿFị@  Main link. Argument: n

7ÆR                 Yield all primes up to 7.
             ÐĿ
            $ÐĿ     Combine the two quicklinks to the left into a monadic chain,
                    and call it repeatedly until the results are no longer unique.
                    Return the array of all intermediate results.
       $              Combine the two links to the left into a monadic chain.
   2Ŀ               Call the helper link on line 2.
     Ṿ€                 Eval each array in the product. This casts to string
                        before evaluating, thus concatenating both numbers.
        ÆPÐf        Filter by primality; keep only primes.
               F    Flatten the resulting array.
                ị@  Retrieve the element at index n.

```

The backward program does almost exactly the same; there are only two differences.

* The main link is now `Ñ`, which simply calls the link below it (wrapping around), i.e., the main link of the forward program.
* `9p` instead of `p9` return the reversed Cartesian product.
> 6 votes

# Answer
# Python 2, ~~143~~ 139 bytes

```
I=1
a={2}
def f(s):
 for d in'123456789':u=d[I:]+s+d*I;z=int(u);z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
f('')
lambda n:sorted(a)[~-n]
I=0

```

Consists of five parts:

1. `I=1`
2. A newline
3. `a={2}…[~-n]`
4. A newline
5. `I=0`

So reversal is just flipping the value of `I`.

## Explanation

The function `f` performs a recursive search for either left-truncatable primes (LTPs) or right-truncatable primes (RTPs), depending on the value of the global `I`. These values get added to the set `a`. Then, `lambda n:sorted(a)[~-n]` returns the `n`-th one.

Let’s define a **leaf** as either an LTP, an RTP, some non-zero digit + an LTP, or an RTP + some non-zero digit. These are all the values that `f` could ever want to check for primality.

I designed a Fermat pseudoprime test that works for all leaves:

>

(63973 is a Carmichael number.)

If this test returns true, then `z` should be added to the set `a` and we should recurse on `str(z)`. The responsible bit of code is:

> ```
> z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
>
> ```

First, we wish to deal with the case `z == 2`. We do so by simply dodging it here and hard-coding `2` when we initially define `a`! (EDIT: And nothing harmful happens if we also catch `z == 1`.) So we can assume that `z ≥ 3` now.

I’ve translated some “and”s into a short-circuiting chained comparison: the first three comparisons have to succeed before `a.add(z)` and `f(u)` are ever evaluated. Here are all their roles:

> 1. `z%91>0` encodes our first condition. (63973 is divisible by 91, which is not a leaf itself, so that’s how we recognize it.)
> 2. `0<2` is always true, but chaining is shorter than `and`.
> 3. `2==pow(2,z,z)` encodes our second condition.
> 4. `pow(2,z,z)>a.add(z)` triggers the addition, and is always true, since `set.add` returns `None`, and integers are always greater than `None`.
> 5. `a.add(z)<f(u)` triggers the recursion. Its truth value is unimportant.

## Acknowledgements

* Dennis saved four bytes (`u=[d+s,s+d][I]``u=d[I:]+s+d*I`; `z==2``z<3` and the **mod 91** trick). Thanks!
> 4 votes

---
Tags: code-golf, primes, source-layout
---


title: Pretty Smooth Moves

text:
# Question
Title: Pretty Smooth Moves
In arithmetic, an n-smooth number, where n is a given prime number, is mathematically defined as a positive integer that has no prime factors greater than n. For example, 42 is 7-smooth because all its prime factors are less than or equal to 7, but 44 is not 7-smooth because it also has 11 as a prime factor.

Define a *pretty smooth* number as a number with **no prime factors greater than its own square root.** Thus, the list of pretty smooth numbers can be formulated as follows:

* *(EDITED!)* 1 is a pretty smooth number, due to its complete lack of any prime factors. (Note that in the original version of this question, 1 was erroneously excluded from the list, so if you exclude it from your outputs you won't be marked wrong.)
* Between 4 (= 22) and 8, the pretty smooth numbers are 2-smooth, meaning they have 2 as their only prime factor.
* Between 9 (= 32) and 24, the pretty smooth numbers are 3-smooth, and can have 2s and 3s in their prime factorizations.
* Between 25 (= 52) and 48, the pretty smooth numbers are 5-smooth, and can have 2s, 3s, and 5s in their prime factorizations.
* And so on, upgrading the criteria every time the square of the next prime number is reached.

The list of pretty smooth numbers is fixed, and begins as follows: 1, 4, 8, 9, 12, 16, 18, 24, 25, ...

Your challenge is to write code that will output all pretty smooth numbers up to and including 10,000 (= 1002). There must be at least one separator (it doesn't matter what kind -- space, comma, newline, anything) between each number in the list and the next, but it is completely irrelevant what character is used.

As per usual, lowest byte count wins -- obviously, simply outputting the list isn't going to be too beneficial to you here. Good luck!

# Answer
## Actually, 11 bytes

```
4╤R`;yM²≤`░

```

Try it online!

Does not include 1.

Explanation:

```
4╤R`;yM²≤`░
4╤R          range(10**4)
   `;yM²≤`░  filter: take values where
    ;yM²       the square of the largest prime factor
        ≤      is less than or equal to the value

```
> 1 votes

# Answer
# Jelly, 12 bytes

```
Æf>½S
³²ḊÇÐḟ

```

Try it online!

### How it works

```
³²ḊÇÐḟ  Main link. No arguments.

³       Yield 100.
 ²      Square it to yield 10,000.
  Ḋ     Dequeue; yield [2, ..., 10,000].
   ÇÐḟ  Filter-false; keep elements for which the helper link returns 0.

Æf>½S   Helper link. Argument: n

Æf      Compute the prime factorization of n.
  >½    Compare the prime factors with the square root of n.
    S   Sum; add the resulting Booleans.

```
> 7 votes

# Answer
# Brachylog, ~~21~~ 19 bytes

**1 byte thanks to Fatalize, for inspiration of another 1 byte.**

```
100^:4reP$ph^<=P@w\

```

Try it online!

Takes about 6 seconds here.

```
100^:4reP$ph^<=P@w\
100                      100
   ^                     squared
    :4                   [10000,4]
      r                  [4,10000]
       eP                P is an integer in that interval (choice point),
        P$ph^<=P         P, prime factorized (from biggest to smallest),
                         take the first element, squared, is less than
                         or equal to P
               P@w       Write P with a newline,
                  \      Backtrack to the last choice point and make
                         a different choice until there is no more
                         choice and the program halts.

```

## Previous 21-byte solution

```
100^:4reP'($pe^>P)@w\

```

Try it online!

Takes about 6 seconds here.

```
100^:4reP'($pe^>P)@w\
100                      100
   ^                     squared
    :4                   [10000,4]
      r                  [4,10000]
       eP                P is an integer in that interval (choice point),
        P'(      )       The following about P cannot be proved:
           $pe               one of its prime factor
              ^              squared
               >P            is greater than P
                  @w     Write P with a newline,
                    \    Backtrack to the last choice point and make
                         a different choice until there is no more
                         choice and the program halts.

```
> 7 votes

# Answer
## Haskell, 53 bytes

```
r=[1..10^4]
[n|n<-r,product[x|x<-r,x*x<=n]^n`mod`n<1]

```

I don't have time to golf this now, but I want to illustrate a method for testing if `n` is pretty smooth: Multiply the numbers from `1` to `sqrt(n)` (i.e. compute a factorial), raise the product to a high power, and check if the result is a multiple of `n`.

Change to `r=[2..10^4]` if `1` should not be output.
> 4 votes

# Answer
# Pyth, ~~16~~ 15 bytes

**1 byte thanks to Jakube.**

```
tf!f>*YYTPTS^T4

```

Try it online!

```
tf!f>*YYTPTS^T4
             T   10
            ^T4  10000
           S^T4  [1,2,3,...,10000]
 f               filter for elements as T for
                 which the following is truthy:
         PT          prime factorization of T
   f                 filter for factor as Y:
     *YY                 Y*Y
    >   T                greater than T ?
  !                  logical negation
t                remove the first one (1)

```
> 2 votes

# Answer
## 05AB1E, ~~16~~ ~~14~~ 13 bytes

```
4°L¦vyf¤yt›_—

```

**Explanation**

```
4°L¦v             # for each y in range 2..10000
      yf¤         # largest prime factor of y
         yt       # square root of y
           ›_     # less than or equal
             —    # if true then print y with newline

```

Try it online
> 2 votes

# Answer
## Matlab, ~~58~~ ~~57~~ ~~56~~ ~~52~~ 48 bytes

```
for k=1:1e4
if factor(k).^2<=k
disp(k)
end
end

```

For each number it checks if all factors squared are not larger than the number itself. If yes, displays that number.

*Thanks to @Luis Mendo for golfing this approach*

---

Another approach (50 bytes):

```
n=1:10^4;for k=n
z(k)=max(factor(k))^2>k;end
n(~z)

```

For each number computes whether its maximum prime factor squared is less than the number itself. Then uses it for indexing.
> 2 votes

# Answer
# SQF, ~~252~~ ~~227~~ 220

Standard script format:

```
#define Q(A,B) for #A from 2 to B do{
Q(i,10000)if([i]call{params["j"];u=sqrt j;a=true;Q(k,u)a=a and((j%k!=0)or(j/k<u)or!([j/k]call{params["x"];q=true;Q(z,sqrt x)q=q and(x%z!=0)};q}))};a})then{systemChat format["%1",i]}}

```

Include the pre-processor in the compilation chain when calling eg:

* `execVM "FILENAME.sqf"`
* `call compile preprocessFile "FILENAME.sqf"`

This writes to the System Chat log, which is the closest thing SQF has to stdout
> 1 votes

# Answer
# C, 113 bytes

```
#include<stdio.h>
main(a){for(;++a<10001;){int n=2,c=a;for(;n*n<=a;n++)while(c%n<1)c/=n;if(c<2)printf("%d ",a);}}

```

Ideone it!
> 1 votes

# Answer
## Pyke, ~~13~~ ~~12~~ 11 bytes

```
T4^S#DP#X<!

```

Try it here!

(Link only goes up to 10^3 because 10^4 times out)

```
T4^S        -  one_range(10^4)
    #DP#X<! - filter_true(V, ^): (as i)
      P     -   factors(i)
       #X<! -  filter_true(V, ^):
        X   -   ^ ** 2
         <! -    not (i < ^)

```
> 1 votes

# Answer
# J, 20 bytes

```
(#~{:@q:<:%:)2+i.1e4

```

Result:

```
   (#~{:@q:<:%:)2+i.1e4
4 8 9 12 16 18 24 25 27 30 32 36 40 45 48 49 50 54 56 60 63 64 70 72 75 80...

```

Try it online here.
> 1 votes

# Answer
# Python 2, 90 bytes

```
for i in range(4,10001):
 n=2;j=i
 while n*n<=j:
  while i%n<1:i/=n
  n+=1
 if i<2:print j

```

Ideone it!
> 0 votes

# Answer
# R, 97 bytes

```
b=F;for(j in 1:1e4){for(i in which(!j%%1:j)[-1])if(which(!i%%1:i)[2]==i)b=i<=j^0.5;if(b)print(j)}

```

ungolfed

```
b <- F                               #Initializes
for (j in 1:1e4){                    #Loop across integers 1..10^4
    a <- which(!j%%1:j)[-1]          #Finds all factors
    for (i in a)                     #Loop across factors
         b <- which(!i%%1:i)[2]==i   #Tests primeness
         if(b) c <- i<=j^0.5         #If prime, tests smoothness
    if(c) print(j)                   #If biggest prime factor gives smooth
}                                    #result, Prints the number.

```
> 0 votes

# Answer
# Pyth, 12 bytes

```
g#^ePT2tS^T4

```

Does not include 1.
> 0 votes

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


# Question
Title: Evaluate an expression of ternary operators
Consider a grammar over the alphabet **{**`0`**,** `1`**,** `?`**,** `:`**}** defined by the production rule

> s → `0``1``0` `?` s `:` s ┃ `1` `?` s `:` s

Given a string generated from *s*, parse it as an expression where `?:` is right-associative (for example, `a?B?X:Y:c?d:e?f:g` means `a?(B?X:Y):(c?d:(e?f:g))`) and evaluate it with the following semantics:

```
eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)

```

If the result is **0**, output some fixed value; if the output is **1**, output a different fixed value. Specify your chosen output values (e.g. `0`/`1`, or `False`/`True`) in your answer.

## Test cases

```
0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0

```

## Rules

* You may not use language built-ins that interpret strings as code in some programming language and run it (such as JavaScript/Perl/Ruby/Python’s `eval`).
* That said, your code doesn’t *actually* have to parse and then evaluate the input string. You can take any approach the achieves equivalent results and doesn’t violate the previous rule.
* Your program will be checked against `perl -le 'print eval<>'`.
* The shortest code (in bytes) wins.

# Answer
## GolfScript, 21 bytes

```
2/-1%{)2%{0`=@@if}*}/

```

This outputs `0` or `1`. Input is assumed to have a single trailing newline. Using `~` (which evaluates strings) would save a byte:

```
2/-1%{)2%{~!@@if}*}/

```

This is based on http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails\_1462638030&gs .
> 5 votes

# Answer
## Retina, 23 bytes

```
r-1=+`0\?.:|1\?(.):.
$1

```

Try it online! (The first line enables a linefeed-separated test suite.)

### Explanation

It's fairly simple actually. The input is reduced to the result by repeatedly (`+`) evaluating ternaries that contain only literals. To make sure this is done right-associatively, we look for matches from right to left (`r`) and replace only the last match we find (`-1=`).

The regex itself either matches `0\?.:` and removes it (leaving only the stuff after `:`) or `1\?.:.` and replaces it with the value after the `?`.
> 17 votes

# Answer
# Haskell, ~~106 101 100 90~~ 83 bytes

This heavily relies on pattern Haskell's pattern matching capabilities. First of all, we reverse the string such that we can just seach for the first occurence of `b:a?x` (which would normally read as `x?a:b`) and replace it with it's value. This automatically provides the *right associativity*. Here we make use of `x:xs` pattern. This is what the function `f` is doing. Then we basically apply `f` to it's output over and over again, until we have a single number (0 or 1) left.

Thanks @Lynn for 12 bytes!

```
f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse

```
> 10 votes

# Answer
## Brainfuck, ~~82~~ ~~64~~ 63 bytes

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

```

The output is `\xff` for `0` and `\x00` for `1`. The brainfuck implementation must allow going to the left of the starting cell.

This uses essentially the same approach as xsot's Python answer, but the branching is probably harder to follow compared with my initial 82-byte submission:

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

```

(For this solution, the output is `\xfe` for `0` and `\xff` for `1`, and wider compatibility is achieved when the input ends with a newline.)

If you can't be bothered to analyse xsot's solution, the idea is this: Proceed from left to right. If you see `1?` then greedily discard it. If you see `0?` then discard everything between that and the corresponding `:`. When `?` does not appear as the second character, stop looping and print the first character of the remaining string.

So, the 82-byte solution actually mirrors that scheme pretty closely. The inner loop handles `0?`, just like xsot's inner loop. Some care is taken in order to enter the main loop without checking any input characters; i.e., we want to check whether the second character is `?` just once at the end of the main loop, and not also at the beginning before entering the main loop.

The 63-byte solution essentially combines the inner and outer loops into one, which I suspected was possible given the similarity between those loops. The memory layout in the main loop could be described as:

```
[s] d c

```

where `[x]` means current cell -- the `s` starts as a dummy nonzero value that just indicates we are still looping, and is immediately overwritten with an input character (either `0` or `1`). The `d` cell holds the (negative) depth in case we are in the middle of a `0?`, otherwise `0`. The `c` is going to be either `?` or `:` or newline or EOF.

After updating `s` and `c`, we handle the `0?` case by updating `d` accordingly and adjusting the pointer, otherwise we use the current value of `c` as the value of `d` in the next iteration, or stop if we are done.
> 8 votes

# Answer
## Python 2, ~~76~~ ~~74~~ ~~73~~ 72 bytes

```
a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a

```

With input as string literal to avoid `raw_`.

The output is `0` or `1` followed by `<built-in function id>`.
> 7 votes

# Answer
# Python 2, 89 bytes

```
s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]

```

Input is taken as a string literal.
> 5 votes

# Answer
## Grime, ~~34~~ 31 bytes

```
E=d|d\?E.E
e`\1|\1\?_.E|\0\?E._

```

Prints `1` for truthy inputs and `0` for falsy ones. Try it online! The last test case unfortunately runs out of memory on TIO.

## Explanation

The right-associativity essentially means that in `a?b:c`, `a` is always either `0` or `1`, never a longer expression. I'll just recursively define a pattern that matches a truthy expression like that, and check the input against it. It's also unnecessary to check that every `:` is really a `:`, if the `?`s are all checked: there is an equal number of `?`s and `:`s in the input, and if some `?` is incorrectly classified as a `:`, the corresponding `:` will fail to match, and Grime's matching engine will backtrack.

```
E=d|d\?E.E
E=                      Define nonterminal E (for "expression") as
  d|                     a digit, OR
    d                    a digit,
     \?                  a literal ?,
       E                 a match of E,
        .                any character (will match a :), and
         E               another match of E.
e`\1|\1\?_.E|\0\?E._
e`                      Match entire input against this pattern (truthy expression):
  \1|                    a literal 1, OR
     \1\?                a literal 1?,
         _               a recursive match of truthy expression,
          .              any character (will match a :), and
           E|            any expression, OR
             \0\?E._     the same, but with 0 in front, and _ and E swapped.

```
> 5 votes

# Answer
# Haskell, ~~79 71 70 62 60~~ 56 bytes

**Edit:** Thanks to @Zgarb for 3 bytes and to @nimi for 4 bytes!

```
e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x

```

This a recursive approach ~~that somewhat abuses the "some fixed value"-output rule~~. Edit: Getting rid of the tuples doesn't only save 8 bytes, it also yields a nicer output: `"0"` or `"1"`.

**Ungolfed version:**

```
eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
    where (a,':':r2) = eval r1
          (b, r3)    = eval r2
eval (x:r) = (x,r)

```

**How does it work?**
The `eval` function traverses the implicit tree of the expressions

```
eval 1?0?0:1:0?1:0 -> eval 1?          :
                             eval 0?0:1 eval 0?1:0

```

and returns a tuple of the form `(result, rest)`.
The first pattern `(x:'?':r1)` matches `x` to `'1'` and `r1` to `"0?0:1:0?1:0"`. Recursively applying `eval` to `r1` evaluates the sub-expression `0?0:1` and returns `(0,":0?1:0")`. Matching this to the pattern `(a,':':r2)` yields `a=0` and `r2=0?1:0`. This sub-formula is also recursively evaluated so that `b='0'` and `r3=""`. Check if `x` is `'1'` or `'0'` and return either `(a, r3)` or `(b, r3)`.
> 5 votes

# Answer
## Perl, 32 + 1 (`-p` flag) = 33 bytes

*Full credit to @Mitch Swartch, as his solution was 14 bytes shorter than mine!*
*Thanks also to @Neil who suggested a solution 1 byte longer than Mitch.*

```
s/.*\K(0\?..|1\?(.)..)/\2/&&redo

```

Needs `-p` flag, as well as `-M5.010` or `-E` to run. For instance :

```
perl -pE 's/.*\K(0\?..|1\?(.)..)/\2/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1"

```

**Explanations** : It basically reduces the blocks of `a?b:c` (starting from the end to be sure no `?` follows) into `b` or `c` depending on the truthness of `a`, over and over until the string only contains `1` or `0`.
> 3 votes

# Answer
## JavaScript (ES6), 53 bytes

```
f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"$1")):s

```

Returns `0` or `1` for valid input; hangs for invalid input. Explanation: because reversing a string is awkward in JavaScript, my first 71-byte attempt worked by using a negative lookahead for a `?` which would otherwise disturb the associativity:

```
f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s

```

Since this was somewhat long I wondered whether I could improve matters by incorporating the decision making into the regexp. As it turned out, it wasn't an immediate success, as it also took 71 bytes:

```
f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"$1$2")):s

```

Then it occurred to me that `0?0:` and `0?1:` are always no-ops, without concern for associativity. This saved me almost 25%.
> 3 votes

# Answer
## Python 3, ~~93~~ 69 bytes

```
def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r

```

Input is the string as a list of characters, output is either `"0"` or `"1"`

```
>>>f(list("0?0:1"))
<<<"1"

```

---

Ungolfed version:

```
def parse(s):
    predicate = s.pop(0)
    if s and s.pop(0) == '?':
        left, right = parse(s), parse(s)
        if predicate == '0':
            return right
        return left
    return predicate

```

---

Another try, but with considerably more bytes:

```
i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])

```
> 2 votes

# Answer
# SED, 75 74 68 (40 + 1 for -r) 41

```
:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t

```
> 1 votes

# Answer
# Bash + GNU utilities, 42

```
rev|sed -r ':
s/(.):.\?0|.:(.)\?1/\1\2/
t'

```

Similar idea to most of the other pattern-matching answers.

Ideone.
> 0 votes

---
Tags: code-golf, syntax
---