title: Sort some apples!

text:
# Question
Title: Sort some apples!
## Problem

Imagine 7 buckets lined up in a row. Each bucket can contain at most 2 apples. There are 13 apples labeled 1 through 13. They are distributed among the 7 buckets. For example,

```
{5,4}, {8,10}, {2,9}, {13,3}, {11,7}, {6,0}, {12,1}

```

Where 0 represents the empty space. The order in which the apples appear *within* each bucket is not relevant (e.g. {5,4} is equivalent to {4,5}).

You can move any apple from one bucket to an adjacent bucket, provided there is room in the destination bucket for another apple. Each move is described by the number of the apple you wish to move (which is unambiguous because there is only one empty space). For example, applying the move

```
7

```

to the arrangement above would result in

```
{5,4}, {8,10}, {2,9}, {13,3}, {11,0}, {6,7}, {12,1}

```

## Objective

Write a program that reads an arrangement from STDIN and sorts it into the following arrangement

```
{1,2}, {3,4}, {5,6}, {7,8}, {9,10}, {11,12}, {13,0}

```

using as few moves as possible. Again, the order in which the apples appear *within* each bucket is not relevant. The order of the buckets does matter. It should output the moves used to sort each arrangement seperated by commas. For example,

```
13, 7, 6, ...

```

Your score is equal to the sum of the number of moves required to solve the following arrangements:

```
{8, 2}, {11, 13}, {3, 12}, {6, 10}, {4, 0}, {1, 7}, {9, 5}
{3, 1}, {6, 9}, {7, 8}, {2, 11}, {10, 5}, {13, 4}, {12, 0}
{0, 2}, {4, 13}, {1, 10}, {11, 6}, {7, 12}, {8, 5}, {9, 3}
{6, 9}, {2, 10}, {7, 4}, {1, 8}, {12, 0}, {5, 11}, {3, 13}
{4, 5}, {10, 3}, {6, 9}, {8, 13}, {0, 2}, {1, 7}, {12, 11}
{4, 2}, {10, 5}, {0, 7}, {9, 8}, {3, 13}, {1, 11}, {6, 12}
{9, 3}, {5, 4}, {0, 6}, {1, 7}, {12, 11}, {10, 2}, {8, 13}
{3, 4}, {10, 9}, {8, 12}, {2, 6}, {5, 1}, {11, 13}, {7, 0}
{10, 0}, {12, 2}, {3, 5}, {9, 11}, {1, 13}, {4, 8}, {7, 6}
{6, 1}, {3, 5}, {11, 12}, {2, 10}, {7, 4}, {13, 8}, {0, 9}

```

Yes, each of these arrangements has a solution.

## Rules

* Your solution must run in polynomial time in the number of buckets per move. The point is to use clever heuristics.
* All algorithms must be deterministic.
* In the event of a tie, the shortest byte count wins.

# Answer
> 2 votes
## C, ~~426~~ 448

This sorts apples one at a time from 1 to 13 similar to yasen's method, except whenever it has an opportunity to move a larger number up or a smaller number down, it will take it. ~~Sadly, this only improves performance on the first test problem, but its a small improvement.~~ I made a mistake when running the test problems. It seems I've simply reimplemented yasen's method.

```
#1: 62    #6: 40
#2: 32    #7: 38
#3: 46    #8: 50
#4: 50    #9: 54
#5: 40    #10: 36

```

It takes input without braces or commas, e.g.

```
8 2 11 13 3 12 6 10 4 0 1 7 9 5

```

Here is the golfed code coming in at 423 bytes counting a few unnecessary newlines (could probably be golfed more, but I expect this score to be beaten):

```
#define N 7
#define F(x,y) for(y=0;y<N*2;y++)if(A[y]==x)break;
#define S(x,y) x=x^y,y=x^y,x=x^y;
#define C(x,y) ((A[x*2]==y)||(A[x*2+1]==y))
A[N*2],i,j,d,t,b,a,n,s,v,u,w,g;main(){for(;i<N*2;i++)scanf("%d",A+i);g=1;while
(!v){F(0,i);b=i/2;F(g,u);w=u/2;d=b<w?1:-1;n=(b+d)*2;a=(b+d)*2+1;if(A[n]>A[a])
S(n,a);t=d-1?a:n;printf("%d,",A[t]);S(A[i],A[t]);while(C((g-1)/2,g))g++;v=1;for
(j=0;j<N*2;j++)if(!C(j/2,(j+1)%(N*2)))v=0;}}

```

And the ungolfed code, which also prints the score:

```
#include <stdio.h>
#include <stdlib.h>

#define N 7

int apples[N*2];

int find(int apple)
{
    int i;
    for (i = 0; i < N*2; i++) {
        if (apples[i] == apple)
            return i;
    }
}

void swap(int i, int j)
{
    int temp;
    temp = apples[i];
    apples[i] = apples[j];
    apples[j] = temp;
}

int contains(int bucket, int apple)
{
    if ((apples[bucket * 2] == apple) || (apples[bucket * 2 + 1] == apple))
        return 1;
    return 0;
}

int is_solved()
{
    int i, j;
    for (i = 0; i < N * 2; i++) {
        j = (i + 1) % (N * 2);
        if (!contains(i / 2, j))
            return 0;
    }
    return 1;
}

int main()
{
    int i, j, dir, bucket, max, min, score;
    int target_i, target_bucket, target;

    /* Read the arrangement */
    for (i = 0; i < N*2; i++) {
        scanf("%d ", apples + i);
    }

    target = 1;
    while (1) {

        i = find(0);
        bucket = i / 2;
        target_i = find(target);
        target_bucket = target_i / 2;

        /* Change the direction of the sort if neccesary */
        if (bucket < target_bucket) dir = 1;
        else dir = -1;

        /* Find the biggest and smallest apple in the next bucket */
        if (apples[(bucket + dir) * 2] < apples[(bucket + dir) * 2 + 1]) {
            min = (bucket + dir) * 2;
            max = (bucket + dir) * 2 + 1;
        } else {
            min = (bucket + dir) * 2 + 1;
            max = (bucket + dir) * 2;
        }

        /* If we're going right, move the smallest apple. Otherwise move the
           biggest apple */
        if (dir == 1) {
            printf("%d, ", apples[min]);
            swap(i, min);
            score++;
        } else {
            printf("%d, ", apples[max]);
            swap(i, max);
            score++;
        }

        /* Find the next apple to sort */
        while (contains((target - 1) / 2, target))
            target++;

        /* If we've solved it then quit */
        if (is_solved())
            break;
    }
    printf("\n");
    printf("%d\n", score);
}

```

# Answer
> 4 votes
# Score: 448

My idea is to sort them consecutively, starting with 1. This gives us the nice property that when we want to move the space to the previous/next basket, we know exactly which of the two apples there we have to move - the max/min one, respectively. Here is the test breakdown:

```
#1: 62     #6: 40
#2: 32     #7: 38
#3: 46     #8: 50
#4: 50     #9: 54
#5: 40    #10: 36

Total score: 448 moves

```

The code can be golfed a lot more, but better quality of the code will motivate additional answers.

# C++ (501 bytes)

```
#include <cstdio>
#define S(a,b) a=a^b,b=a^b,a=a^b;
int n=14,a[14],i,j,c,g,p,q;
int l(int x){for(j=0;j<n;++j)if(a[j]==x)return j;}
int sw(int d){
    p=l(0);q=p+d;
    if(a[q]*d>a[q^1]*d)q^=1;
    printf("%d,", a[q]);
    S(a[q],a[p])
}
int main(){
    for(;j<n;scanf("%d", a+j),j++);
    for(;++i<n;){
        c=l(i)/2;g=(i-1)/2;
        if(c-g){
            while(l(0)/2+1<c)sw(2);
            while(l(0)/2>=c)sw(-2);
            while(l(i)/2>g){sw(2);if(l(i)/2>g){sw(-2);sw(-2);}}
        }
    }
}

```

Further improvements may be switching to C and trying to lower the score by starting from the large values downwards (and them eventually combining both solutions).

# Answer
> 2 votes
# Python 3 - 121

This implements a depth-first searching with increasing depth until it finds a solution. It uses a dictionary to store visited states so that it doesn't visit them again unless with a higher depth window. When deciding which states to check, it uses the number of misplaced elements as a heuristic, and only visits the best states possible. Note that since the order of the elements within their bucket does not matter, it always maintains an ordering within the buckets. This makes it easier to check if an element is misplaced.

The input is an array of ints, with the first int being the number of buckets.

So for instance, for #8 (this one takes a very long time to run on my machine, the others finish in seconds):

```
c:\python33\python.exe apples.py 7 3 4 10 9 8 12 2 6 5 1 11 13 7 0

```

Here are the results on the test set: #1: 12, #2: 12, #3: 12, #4: 12, #5: 11, #6: 11, #7: 10, #8: 14, #9: 13, #10: 14

Here is the code:

```
import sys

BUCKETS = int(sys.argv[1])

# cleans a state up so it is in order
def compressState(someState):
  for i in range(BUCKETS):
    if(someState[2*i] > someState[2*i + 1]):
      temp = someState[2*i]
      someState[2*i] = someState[2*i + 1]
      someState[2*i + 1] = temp
  return someState

state = compressState([int(x) for x in sys.argv[2:]])
print('Starting to solve', state)
WINNINGSTATE = [x for x in range(1, BUCKETS*2 - 1)]
WINNINGSTATE.append(0)
WINNINGSTATE.append(BUCKETS*2 - 1)
maxDepth = 1
winningMoves = []
triedStates = {}

# does a depth-first search
def doSearch(curState, depthLimit):
  if(curState == WINNINGSTATE):
    return True
  if(depthLimit == 0):
    return False
  myMoves = getMoves(curState)
  statesToVisit = []
  for move in myMoves:
    newState = applyMove(curState, move)
    tns = tuple(newState)
    # do not visit a state again unless it is at a higher depth (more chances to win from it)
    if(not ((tns in triedStates) and (triedStates[tns] >= depthLimit))):
      triedStates[tns] = depthLimit
      statesToVisit.append((move, newState[:], stateScore(newState)))
  statesToVisit.sort(key=lambda stateAndScore: stateAndScore[2])
  for stv in statesToVisit:
    if(stv[2] > statesToVisit[0][2]):
      continue
    if(doSearch(stv[1], depthLimit - 1)):
      winningMoves.insert(0, stv[0])
      return True
  return False

# gets the moves you can make from a given state
def getMoves(someState):
  # the only not-allowed moves involve the bucket with the 0
  allowedMoves = []
  for i in range(BUCKETS):
    if((someState[2*i] != 0) and (someState[2*i + 1] != 0)):
      allowedMoves.append(someState[2*i])
      allowedMoves.append(someState[2*i + 1])
  return allowedMoves

# applies a move to a given state, returns a fresh copy of the new state
def applyMove(someState, aMove):
  newState = someState[:]
  for i in range(BUCKETS*2):
    if(newState[i] == 0):
      zIndex = i
    if(newState[i] == aMove):
      mIndex = i
  if(mIndex % 2 == 0):
    newState[mIndex] = 0
  else:
    newState[mIndex] = newState[mIndex-1]
    newState[mIndex-1] = 0
  newState[zIndex] = aMove
  if((zIndex % 2 == 0) and (newState[zIndex] > newState[zIndex+1])):
    newState[zIndex] = newState[zIndex+1]
    newState[zIndex+1] = aMove
  return newState

# a heuristic for how far this state is from being sorted
def stateScore(someState):
  return sum([1 if someState[i] != WINNINGSTATE[i] else 0 for i in range(BUCKETS*2)])

# go!
while(True):
  triedStates[tuple(state)] = maxDepth
  print('Trying depth', maxDepth)
  if(doSearch(state, maxDepth)):
    print('winning moves are: ', winningMoves)
    break
  maxDepth += 1

```

---
Tags: code-challenge, sorting, restricted-complexity
---


title: Crack the code to the combination lock

text:
# Question
Title: Crack the code to the combination lock
Given a standard combination lock like the one in the picture. The way to unlock it is to align the 4 numbers in the code on the combination line. After years of loyal service you have been fired from the lock factory and have decided to exact revenge by not jumbling up the locks before you send them off, thus leaving every lock with the combination to unlock it on the combination line.

You also know that by looking at the order of the numbers in the other lines it is possible to work out what numbers must be on the combination line (and therefore the combination to unlock it is).

If every line on the lock is given a number starting from line 0 for the combination line (the line which unlocks the lock) to line 9. For example, if the numbers on line 4 are `5336`, then the combination to unlock it would be `1992`.

Unfortunately the locks have already been packaged and your view of each lock is obscured, so you can only see numbers on different lines of the lock.

**The Challenge**

Given 4 pairs of digits, where the first digit of the integer represents the line number and the second digit represents the the number which appears on that line, work out the combination to the lock. For example if you input:

```
57 23 99 45

```

Then it should output:

```
2101

```

Or

```
25 78 63 15

```

and

```
3174

```

Assume the input will always be 4 positive integers in the form \`25 64 72 18.

This is , so the shortest programs in number of bytes wins.

Also this is my first question, so any feedback is appreciated.

# Answer
> 32 votes
# CJam, ~~9~~ 8 bytes

```
ea9fbAf%

```

Reads the digit pairs as command-line arguments. To try the code online, change `ea` to `lS/` to read from simulated STDIN.

### Example run

```
$ cjam <(echo ea9fbAf%) 57 23 99 45; echo
2101
$ cjam <(echo ea9fbAf%) 25 78 63 15; echo
3174

```

### How it works

The character code of the digit **d** is **48 + d**. Thus, considering the two-digit string **xy** a base 9 number yields **9 * (48 + x) + (48 + y) = 10 * (48 + x) + y - x ≡ y - x (mod 10)**.

```
ea       " Push the array of command-line arguments.                                      ";
  9fb    " Mapped base 9 conversion; replace each string 'xy' with (9 * ord(x) + ord(y)). ";
     Af% " Take the results modulo 10.                                                    ";

```

# Answer
> 13 votes
# CJam, ~~13~~ ~~12~~ 11 characters

Thanks to user23013, its now down to 11 characters :)

```
4{Ar:--A%}*

```

Explanations:

```
4{       }*     "Run the code block 4 times";
   r            "Read the next input token (whitespace separated)";
    :-          "Subtract 2nd number from the first treating r as a 2 numbered string";
  A   -         "Subtract the result of above from 10";
       A%       "Take modulus of 10 and store it on stack";

```

Try it online

I know it can be golfed more. But this is my first real attempt on CJam and I am limited by experience :)

---

Alternatively, the other methods to do the same thing in 1 extra character:

```
l~]{_A/-A%}/     // My previous solution

```

or

```
4{ri_A/-A%}*     // As pointed out by Ingo

```

or

```
ea{i_A/-A%}/     // If input is passed through command line

```

# Answer
> 6 votes
# Golfscript (14 ~~13~~)

Try it online here

It's pretty much the same as Optimizer's solution, but in a different language. It's hard to approach it in a different way because the problem is fairly simple~~, so the tie definitely goes to Optimizer, whose entry was earlier anyway.~~

```
~]{.10:^/-^%}/

```

For the same number of bytes you can do

```
~]{.10/- 10%}/

```

# Answer
> 6 votes
**C 64 63 56 or 61**

If the input can be piped from file

```
main(a){while(scanf("%d",&a)>0)putchar(48+(a-a/10)%10);}

```

If the input should be typed to stdin

```
i;main(a){for(;i++-4;putchar(48+(a-a/10)%10))scanf("%d",&a);}

```

Reads the four numbers in a loop and then processes each by subtracting the first digit from the value and printing the result modulo 10.

Savings thanks to various comments below and also using putchar instead of printf

# Answer
> 6 votes
# GNU dc, 14 bytes

Borrowing @Dennis's clever base 9 trick:

```
9i[?A%nd]dxxxx

```

Input integers read from STDIN, one per line.

### Explanation:

```
9i                # Set input radix to 9
  [     ]         # push a macro, defined thus:
   ?              #   read number from STDIN and push
    A             #   push literal 10
     %            #   calculate number mod 10
      n           #   print, with no newline
       d          #   duplicate macro
         d        # duplicate macro
          xxxx    # execute the macro 4 times

```

### Output:

```
$ for i in 57 23 99 45; do echo $i; done | dc ./combolock.dc
2101$
$ for i in 25 78 63 15; do echo $i; done | dc ./combolock.dc
3174$
$

```

---

### Previous Answer, 18 bytes:

Because I thought I could get closer to the "golfing" languages with this (but didn't):

```
[A?A~--A%n]dddxxxx

```

# Answer
> 5 votes
## Python 3 , 64

Straightforward.

```
print(''.join([(i-i//10)%10 for i in map(int,input().split())]))

```

It can be shorter if I'm allowed to print, say, `[2, 1, 0, 1]` instead (**46**):

```
print([i%10-i//10 for i in map(int,input().split())])

```

# Answer
> 4 votes
# C, 92

```
#define a(n) ,(10+v[n][1]-*v[n])%10
main(int c,char**v){printf("%d%d%d%d"a(1)a(2)a(3)a(4));}

```

Input from commandline. Subtracts the first ASCII code of each argument from the second, adds 10 and takes modulo 10.

I think this is the first time I've written a `printf` with four `%`s and no comma (the comma is in the `#define.`)

# Answer
> 4 votes
## Java - 203 bytes

Just because there *has* to be a Java entry, I saw a nice opportunity to give this code golfing a chance (first submission ever).

```
class M{public static void main(String[] a){String r="";for(int i=0;i<4;i++){int l=Byte.valueOf(a[i].substring(1));int f=Byte.valueOf(a[i].substring(0,1));r+=(l-f<0)?l-f+10:l-f;}System.out.print(r);}}

```

If there's room for some improvements, I'd glad to know about them ;-)

# Answer
> 3 votes
# Lua - 46 characters

```
while''do a,b=io.read(1,1,1)print((b-a)%10)end

```

Reads three characters at a time (grant me the small mercy of inputing a space at the end), and eventhough a and b are string-y... b-a MAGICALUALY allows them to conceive a healthy baby integer. Does the wrap-around check while printing.

# Answer
> 3 votes
# JavaScript ES6 – ~~53~~ 43 bytes

```
f=n=>n.replace(/.. ?/g,a=>(1+a[1]-a[0])%10)

```

Fairly straightforward function, uses regex to get the numbers. Try it out at http://jsfiddle.net/efc93986/1/. If functions are not allowed, a standalone program at 52 bytes:

```
alert(prompt().replace(/.. ?/g,a=>(1+a[1]-a[0])%10))

```

As ES6 currently only works on Firefox, the following code works on any modern browser, at 70 bytes:

```
alert(prompt().replace(/.. ?/g,function(a){return(1+a[1]-a[0])%10}))

```

# Answer
> 2 votes
# Python 2 - 33 bytes

```
for i in input():print(i-i/10)%10

```

Accepts comma-delimited user input. E.g. Input:

```
29,26, 31, 88

```

Output:

```
7
4
8
0

```

If output is required to exactly match the example then it is much longer. 47 bytes:

```
print"%d"*4%tuple((i-i/10)%10 for i in input())

```

# Answer
> 2 votes
## APL, 14

```
10|{--/⍎¨⍕⍵}¨⎕

```

**Explaination**
takes input from screen. Space-separated values are parsed as an array.
`{...}¨` for each number, feed it into function.
`⍎¨⍕⍵` takes the argument, create an array of its digits.
`--/` calculates units minus tens.
`10|` mod 10.

# Answer
> 2 votes
# Haskell 60 58

```
main=interact$show.map((\x->mod(x-x`div`10)10).read).words

```

Single character digits, a real nemesis in Haskell golfing.

# Answer
> 2 votes
## J - 20 15

The non-verb form (as statement instead of function definition) it's 5 characters shorter:

```
10|-~/|:10#.inv

```

The verb form which is a nice train:

```
10|[:-~/[:|:10#.inv]

```

This verb used on the example inputs:

```
   10|-~/|:10#.inv 57 23 99 45
2 1 0 1
   10|-~/|:10#.inv 25 78 63 15
3 1 7 4

rotd =: 10|[:-~/[:|:10#.inv] NB. verb form

   rotd 25 78 63 15
3 1 7 4
   rotd 57 23 99 45
2 1 0 1

```

# Answer
> 2 votes
# Perl: 38 40

```
print abs($_-int$_/10)%10for split" ",<>

```

Output:

```
% perl code.pl
57 23 99 45
2101

25 78 63 15
3174

```

# Answer
> 1 votes
## Ruby, 35 bytes

```
$*.map{|n|a,b=n.bytes;$><<(b-a)%10}

```

### Explanation

Input is taken as command line arguments. `String#bytes` returns an Array of Integers (ASCII character codes). Only the difference between the last and first character code is of importance, not the Integers themselves.

# Answer
> 1 votes
## C++ 118

```
int main()
{
int a,b,c;
for(int i=0; i<4; i++)
{
cin>>a;
b=a/10;
a=a%10;
c=a-b;
if(c<0)c+=10;
cout<<c;
}
}

```

# Answer
> 1 votes
**C# & LinqPad: 104**

```
Util.ReadLine<string>("").Split(' ').Select(s =>(s[1]-s[0])).Aggregate("",(r,a)=>r+(a<0?10+a:a)).Dump();

```

# Answer
> 1 votes
# PHP - 90 characters

Thought I'd give code golf a try so here it is, my first attempt - can probably be golfed more.

```
<?php $a=array(57,23,99,45);foreach($a as$b){echo abs(substr($b,0,1)-substr($b,1,1)%10);}

```

## 58 characters (courtesy of Ismael Miguel)

```
for($i=0,$a=$_GET[n];$i<8;)echo abs($a[$i++]-$a[$i++]);

```

Access file using

```
file.php?n=57239945

```

# Answer
> 0 votes
# Python 3, 60

```
for x in input().split():print(-eval('-'.join(x))%10,end='')

```

Input and output exactly as specified, although it doesn't print a trailing newline. Two interesting tricks here: 1) replacing two calls to `int()` with one call to `eval()`, and 2) using `join()` to get `a-b`, then negating it for `b-a` as required. Fortunately Python's modulo operator gives positive values even if the first argument is negative!

---
Tags: code-golf
---


# Question
Title: Approximate square root from algorithm time complexity
There have been a few square root challenges lately, but I think this one is different.

# Challenge

Find an algorithm such that the worst case time complexity is proportional to `n^2` and the best case is proportional to `n` where `n` is the size of the algorithm input. Given a value `x`, find the approximate square root of `x` by running the chosen algorithm with some number of inputs (to be decided in code) arranged to give worst case performance; rearrange the algorithm input values to give best case performance, which will approximate the square root of the worst case run time.

Psuedocode example to help explain the challenge:

```
input target is 9 // find square root of 9
// target time is then 9000 ms

do
{
    create array with 10000 elements
    populate array in reverse order (array[0] = 10000; array[1] = 9999; etc)
    time how long it takes to bubble sort array
    if (time to sort > 9000 ms + margin of error)
    {
        sorting took too long; decrease array size
    }
    else if (time to sort < 9000 ms - margin of error)
    {
        sorting didn't take long enough; increase array size
    }
} while (run time is outside of 9000 ms +/- margin of error)

// the number of elements it takes to sort in n^2 time is now known
create array with correct number of elements
fill array with zeros
return the amount of time it takes to bubble sort

```

Implementing the above in C as a rough prototype takes 110 seconds to determine the square root of 9 is 3.781.

# Rules

* Input is read from stdin, file, hard-coded, wherever, as long as any positive integer can be used for input, and the program will approximate the square root. For hard-coded values, changing the input constant should be the only change needed to approximate another square root.
* An algorithm must be used and must have worst case time complexity of `n^2` and best case time complexity of `n`.
* When changing form worst case to best case run time, the number of inputs must be the same.
* I'm assuming that measuring run time will actually be difficult and probably slightly inaccurate. Additionally, time complexity does not mean that run time is exactly equivalent to input size, therefore the answer only needs to be accurate to within +/- 25% of the actual square root. Bonus points for improved accuracy.
* Any built in math functions are available for use, but the actual square root calculation must come from measuring the best case run time. That is, calculating the square root of the input and then searching for a best case run time equivalent to the square root is allowed, but somewhat discouraged. The spirit of the challenge is to find the square root by measuring worst case run times.
* Program run time must be "reasonable," say, less than an hour.

# Answer
# C(++), 93 Bytes

My solution:

```
int s(int a){int b=0;for(int i=1<<15;i>0;i/=2){if((b+i)*(b+i)<=a)b+=i;else{for(int j=1;j<i;j*=2);}}return b;}

```

It is O(n) for a = 0xFFFF..., and O(n^2) for a = 0x1000... And it returns floor(sqrt(x)), which is an approximation of sqrt(x)

However, If you want an algorithm that works in O(n) time, you can shave off 28 bytes.

For test cases, append:

```
int main()
{
    int a = 1024;
    return s(a); //returns sqrt(1024) = 32
}

```
> 2 votes

---
Tags: popularity-contest, math, restricted-complexity
---


title: Make a WaterOverflow

text:
# Question
Title: Make a WaterOverflow
You and a friend are playing a game - who can overflow the most containers? There are `n` containers numbered 1 to `n`. Each container has a certain maximum capacity of water, in litres.

You take turns with your friend to pour discrete amounts of water into the containers. On your turn, you *may* pour 2 litres of water into *one container* (you can't distribute into multiple containers), and on your friend's turn, he *must* pour `3` litres. You may also choose, on your turn, to *not* pour water in any of the containers (you cannot, however, choose to only pour 1 litre). The person who manages to overflow the container - that is, after they finish their turn, the litres of water inside the container is greater than its maximum capacity - gets a point.

The input comes in the form of space separated integers. The leftmost one is labelled 1 and the rightmost one is labelled `n`. For instance:

```
Y 2 1 4 3

```

Note that the letter indicates who goes first. `Y` means that you go first, and `F` means that your friend goes first. The 2 litre container is labelled `1`, the 1 litre container is labelled `2`, etc. So we would call the 2 litre container "Container 1", because it is labelled `1`.

Now, your friend has a very naïve strategy. He always pours all his 3 litres of water into the container that is closest to overflowing. If there is more than one container that is equally closest to overflowing, he will pour all his water in the one that is labelled with the lowest number.

Suppose I use the same naïve strategy of pouring all my 2 litres of water into the container that is closest to overflowing. The example input would work out like this:

1. I pour all my water into Container 2. It overflows, and I get one point.
2. My friend pours all his water into Container 1. It overflows, and he gets one point.
3. I pour all my water into Container 4. It now has 2L of water in it, so it needs another 2L to overflow.
4. My friend pours all his water into Container 4. It overflows, and he gets one point.
5. I pour all my water into container 3. It now has 2L of water in it, so it needs another 3L to overflow.
6. My friend pours all his water into Container 3. It overflows, and he gets one point.

Altogether, I only got one point, and my friend got three. That's not good. I can do better than that if I make use of my ability to pass on my turn without pouring water:

1. I pour all my water into Container 2. It overflows, and I get one point.
2. My friend pours all his water into Container 1. It overflows, and he gets one point.
3. I *pass*.
4. My friend pours all his water into Container 4. It now has 3L of water in it, so it needs another 1L to overflow.
5. I pour my water into Container 4. It overflows, and I get one point.
6. My friend pours all his water into Container 3. It has 3L of water in it now, so it needs another 2L to overflow.
7. I pour my water into Container 3. It overflows, and I get one point.

By strategically choosing which container to pour my water in, I have managed to obtain 3 points instead of 1. The output format is a list of space separated instructions, where `P` indicates a pass, and an integer from `1` to `n` indicates which container I poured water into. For instance, the naïve nonoptimal strategy listed above could be represented as:

```
2 4 3

```

Which means I poured into Container 2, then Container 4, then Container 3. The more optimal strategy would be represented as:

```
2 P 4 3

```

Which means I poured into Container 2, then passed, then Container 4, then Container 3 (This, by the way, is the output format).

Your program will take in input as described above and return the most optimal solution to get as many points as possible. If there is more than one optimal solution, output either.

# Answer
> 2 votes
## Python, ~~217~~ ~~202~~ 176

```
import sys
A=sys.argv[1:]
t=A>["G"]
C=[[int(A[i]),i]for i in range(1,len(A))]
while C:
 c=min(C);d=1.5
 if t:d=c[0]%5<2;print["P",c[1]][d],
 c[0]-=2*d;t^=1
 if[0]>c:C.remove(c)

```

Reads input from the command line.

**Strategy:**

* If the remaining capacity in the container with the least remaining capacity is congruent *0* or *1* modulo *5*, pour *2* litres (it either overflows, or our friend pours *3* more litres into the same container, bringing us back to the same point.)
* Otherwise, no move improves our position, so do nothing (note that this isn't necessarily the *shortest* optimal strategy.)

# Answer
> 1 votes
# Java - 718

To generalize, the optimal amount of water in the bucket at the beginning of my turn should be capacity-1 or full. So the previous turn (ideally) it should have been capacity-4 or capacity-3, and capacity-7 or capacity-6.

So the only option that is bad for me would be capacity - n where n % 3 == 2. So my strategy is to wait until the end, then grab the bucket at the last minute, taking care to keep the bucket level in the "ok range". If all the buckets are in the range, then do nothing!

Because you cannot win when the capacity is 2, I simply ignored it.

I think this could be the optimal solution. It beats the friend 100% of the time when the capacities are greater than 2.

Here is the function (for use in simulator above):

```
BucketChoice makeMove(){
    ArrayList<Bucket> bucketsNotOk = new ArrayList<Bucket>();
    ArrayList<Bucket> bucketsOk = new ArrayList<Bucket>();
    //sort buckets
    for(Bucket b:buckets){
        if(b.litersLeft() % 3 == 2){bucketsNotOk.add(b);}
        if(b.litersLeft() % 3 == 0){bucketsOk.add(b);}
        if(b.litersLeft() % 3 == 1){bucketsOk.add(b);}
    }
    //first I want to grab any buckets ready for overflowing
    for(Bucket b:bucketsOk){
        if(b.litersLeft()<2){System.out.println(buckets.indexOf(b));return new BucketChoice(b,2);}
    }
    //next change buckets to OK
    for(Bucket b:bucketsNotOk){
        //no use adding water if it is doomed
        if(b.litersLeft()>2){System.out.println(buckets.indexOf(b));
            return new BucketChoice(b,2);
        }
    }
    return new BucketChoice(buckets.get(0),0);
}

```

golfed...hmmm seems long :(

```
import java.util.*;class o{List<int[]>b=new ArrayList<int[]>(),r=new ArrayList<int[]>();public o(String[]a){for(int x=1;x<a.length;x++){b.add(new int[]{Integer.valueOf(a[x]),0});}while(b.size()>0){if(a[0].equals("F")){e();}int m=0,n=-1,i=0;for(;i<b.size();i++){int[]g=b.get(i);if(g[0]-g[1]<2){n=i;m=1;g[1]+=2;break;}}for(i=0;i<b.size();i++){int[]g=b.get(i);if((g[0]-g[1])%3==2&&m==0){n=i;g[1]+=2;break;}}for(int[]h:b){if(h[0]-h[1]<0){r.add(h);}}for(int[]h:r){b.remove(h);}if(a[0].equals("Y")){e();}if(n!=-1){System.out.print(n+" ");}else{System.out.print("p ");}}}void e(){int[]r={99999,0};for(int[]i:b){if(i[0]-i[1]<r[0]-r[1]){r=i;}}r[1]+=3;if(r[0]-r[1]<0){b.remove(r);}}public static void main(String[]a){new o(a);}}

```

# Answer
> 0 votes
# A Java Simulator

I know there are lazy people out there! Here it is:

To continue, just press any key + enter in the console.

OverflowChallenge:

```
import java.util.ArrayList;
import java.util.Scanner;

    public class OverflowChallenge {
        ArrayList<Bucket> buckets = new ArrayList<Bucket>();
        int myScore=0,friendScore=0;
        public static void main(String[] args) {
            new OverflowChallenge(args);
        }
        public OverflowChallenge(String[]args){
            for(int x=1;x<args.length;x++){
                buckets.add(new Bucket(Integer.valueOf(args[x])));
            }
            while(buckets.size()>0){
                Scanner s = new Scanner(System.in);
                if(args[0].equals("F")){naivePlayerMove();}

                BucketChoice myMove=null;
                if(buckets.size()>0){myMove = makeMove();}else{System.exit(0);}
                myMove.bucket.addWater(myMove.litersAdded);
                if(myMove.bucket.overflowing){buckets.remove(myMove.bucket);}

                System.out.println("you added "+myMove.litersAdded+" to bucket "+buckets.indexOf(myMove.bucket));
                if(myMove.bucket.overflowing){System.out.println("...and you overflowed it!");}

                if(!args[0].equals("F")){naivePlayerMove();}
                for(Bucket b:buckets){
                    System.out.println("bucket "+buckets.indexOf(b)+" has " + b.litersFilled +"/"+b.capacity);
                }
                System.out.println("friend score = "+friendScore);
                System.out.println("my score = "+myScore);
                s.next();
            }
        }
        BucketChoice makeMove(){
            return new BucketChoice(buckets.get(0),2);
        }
        void naivePlayerMove(){
            Bucket lowestBucket=new Bucket(999999999);
            for(int x=0;x<buckets.size();x++){
                if(buckets.get(x).litersLeft()<lowestBucket.litersLeft()){
                    lowestBucket=buckets.get(x);
                }
            }
            lowestBucket.addWater(3);
            System.out.println("your friend added 3 liters to bucket "+buckets.indexOf(lowestBucket));
            if(lowestBucket.overflowing){
                friendScore++;
                buckets.remove(lowestBucket);
                System.out.println("...and overflowed it!");
            }
        }
}

```

Bucket:

```
public class Bucket {
    int capacity,litersFilled;
    boolean overflowing = false;
    public Bucket(int capacity){
        litersFilled=0;
        this.capacity=capacity;
    }
    public int litersLeft(){
        return capacity-litersFilled;
    }
    public void addWater(int liters){
        litersFilled+=liters;
        if(litersFilled>capacity){
            overflowing=true;
        }
    }
}

```

BucketChoice:

```
public class BucketChoice {
    public BucketChoice(Bucket myBucket, int liters){
        bucket = myBucket;
        litersAdded = liters;
    }
    public Bucket bucket;
    public int litersAdded;
}

```

Enjoy!

---
Tags: code-golf
---


title: Minimal Boggle-like Arrangements

text:
# Question
Title: Minimal Boggle-like Arrangements
Consider how a word could be arranged on an arbitrarily large Boggle grid ***if the rule about not using the same letter cube more than once is ignored***. Also assume that you have an unlimited number of letter cubes (with all letters present), and `Qu` is just `Q`.

The word `MISSISSIPPI` could be arranged using only 6 cubes. Here is one possible arrangement:

```
 S
MIS
 PP

```

Starting at the `M` we repeatedly take any step horizontally, vertically, or diagonally until the entire word is spelled out.

Surprisingly, a longer phrase like `AMANAPLANACANALPANAMA` also only needs 6 cubes:

```
MAN
PLC

```

However, the minimum number of cubes needed for longer, more complex strings is not always obvious.

# Challenge

Write a program that takes in a string and arranges it in this Boggle-like fashion **such that the minimum number of cubes are used**. (The dimensions of the resulting grid and the number of empty cells are irrelevant.)

Assume you have have an unlimited number of cubes for each printable ASCII character except space (hex codes 21 to 7E), since it's used as an empty grid cell. Only printable ASCII strings (without spaces) will be input.

Input should be taken from stdin or the command line. Output should go to stdout (or closest alternative).

Leading or trailing newlines and spaces in the output are fine (but hopefully there aren't an inordinate amount).

The search space blows up exponentially as the string gets longer, but you are not required to attempt to make your algorithm efficient (though that would be nice :) ). This is code-golf, so the shortest solution in bytes wins.

# Example

If the input were `Oklahoma!` (8 character minimum), these would all be valid outputs because the all have exactly 8 filled grid cells and they follow the (revised) Boggle reading pattern:

```
Oklaho
   !m

```

or

```
  !
Oamo
klh

```

or

```
   lkO
  !amo
    h

```

etc.

# Answer
## Python 342 ~~355~~ ~~398~~

```
R=(-1,0,1)
A=[];b={}
def s(w,x,y):
 if w: # not at the end of the word yet?
  for I in R: # search adjacent squares
   for j in R:
    if I|j: # skip the square we are on
     i=I+x;j+=y;c=b.get((i,j)) # get square in board
     if c==w[0]:s(w[1:],i,j) # square is what we are looking for?
     elif not c:b[i,j]=w[0];s(w[1:],i,j);del b[i,j] # we can set square?
 else:A.append(dict(b)) # all solutions
s(raw_input(),9,9) # run the search
A=min(A,key=len) # A is now the shortest solution
C=sum(map(list,A),[]) # put all board coords together
C=range(min(C),max(C)+1) # find the board biggest square bound
for r in C:print"".join(A.get((c,r)," ") for c in C)

```

Indent at four spaces is actually a tab character.

`AMANAPLANACANALPANAMA`:

```
MC
NA
PL

```

`MISSISSIPPI`:

```
S
SI
PPM

```

`Oklahoma!`:

```
oh
 ma
 ! l
    k
     O

```

`Llanfairpwllgwyngyll` is *lethal* ;)
> 5 votes

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


title: Animation of Code Golf

text:
# Question
Title: Animation of Code Golf
When I see code-golf entries that knock a few characters off, whittling down the code, I go look at the edit history for a side-by-side diff. See and learn :)

This challenge is to make a program that produces the prettiest animated diffs.

* The input will be any ordered series of text versions.
* The program may be written in any programming language.
* It is allowed that the program limit itself to input data in some specific programming languages.
* The program should not be tuned to the specific input data; the program should be generic and work for any ordered series of text versions.
* For each version in the input there must be a corresponding time in the output animation where the full text of the version is displayed. You must animate the diff between version stages, and all version stages must be present and in order in the output. On these key frames, the version size must be shown and the viewer should understand this is a complete version they are seeing at that point.
* The program may not use any third party code to compute the diffs.
* Syntax highlighting output is optional. If the program colours syntax, it may not use any third party code to do so.
* The output will be an animated GIF.
* The program may use a third party library to author the GIF.
* This is a , so as per the definition of *popularity-contest* on this site, *the entry with the most votes wins*.

Here's a simple example script that uses Python's ndiff and Pillow's rudimentary animated GIF support and animates each add and remove step:

Personally, I think this a pretty poor job. It doesn't do syntax highlighting, it doesn't try and move code chunks that get rearranged, it doesn't feel like someone is live editing it, and so on. It also breaks the rules regards showing the size of the input in bytes on key frames, and it uses a third party library to do the diffing. Lots of room for improvement!

And hopefully the popular entries will become useful fun tools for the codegolf.stackexchange.com community too. So its appreciated if the programs are easy for others to get running and use.

# Answer
<sub>(OP)</sub>

This is based on the example Python script in the question.

I used the simplest edit distance rather than a cleverer patience diff.

For aligning genomes there's Multi Sequence Alignment algorithms and they could well make an even better job than just considering each pair of adjacent frames?

I was pleasantly surprised how straightforward it was to implement edit distance for the diff, and made it compatible with Python's `difflib.ndiff` format. There are plenty of Python implementations of edit distance to be found on the web, but I think my formulation is that little bit tidier and deals with the tricky but essential part of actually determining the path in the table too; in our context, we need to know the steps to turn one into another and not just how many steps there are.

I introduced syntax highlighting using a very simple tokenizer that ought to be able to cope with most c-like languages including, by its laxity, Python and such. It splits the source into punctuation, whitespace, strings (with escape support) and everything else is an identifier and checked against a list of keywords. The colouring is also easy to change.

It was easy to integrate the syntax highlighting into a dynamic language; the highlighter outputs a list of character and colour pairs, and the differ is agnostic to whether its diffing strings or any arbitrary iterables of comparables! An interesting - and deliberate - effect of highlighting first and then diffing is that characters that remain unchanged but change colour get animated. I didn't want to compute the highlight each frame as that would mean that as you delete a closing string you'd suddenly flash a big chunk of text up as string.

Python's support for authoring GIF is rather limited. PIL doesn't do it, and Pillow does it rather badly. I use Pillow, but then have to run through gifsicle to compress and add looping etc; Pillow doesn't correctly write frame timing and doesn't let you manage disposal methods etc, which is a shame as the differ has so much better understanding of the scene than a post-processing step dealing with flattened frames :(

Sourcecode
> 11 votes

---
Tags: popularity-contest, graphical-output, animation
---


title: Countdown and recycle

text:
# Question
Title: Countdown and recycle
# Countdown

Your goal for this code-golf challenge is to count down and meanwhile *recycle* numbers. Let me explain.

First your application reads a number, either as program argument or using stdin. Next you'll simply need to count down like this: `10 9 8 7 6` (in *descending* order)

But wait, there is more!

# Recycling

There are situations where we can print every number, but don't list every number, we can do recycling! Let me give a quick example:

```
Input: 110

Output:   11091081071061051041031021010099... etc
Recycled:  10                        1

```

We've now still listed all the numbers, 110, 109, 108, but we've recycled a **0** and a **1**.

Another example:

```
Input: 9900

Output:   9900989989897989698959894... etc
Recycled:        9 98

```

# Code-golf challenge

* Read a number (argument or stdin)
* Output the countdown in *descending* order while recycling **all** possible numbers (to stdout or file)
* Stop when you reach 1 OR the moment you've recycled 0 to 9 (whatever happens first)

Simple example (until 1 reached):

```
Input: 15
Output: 15141312110987654321

(Notice the 110 instead of 1110)

```

More advanced example (all recycled):

```
Input: 110
Output:   110910810710610510410310210100998979695949392919089887868584838281807978776757473727170696867665646362616059585756554535251504948474645443424140393837363534332313029282726252423221
Recycled:  10                            9                    8                    7                    6                    5                    4                    3                    2

(We've recycled all 0-9)

```

# Answer
> 11 votes
## T-SQL - 291 277 267 217 199 191 166 158 153 145 142 128 117

After approaching this in a new way, I managed to get down to 145(142 after a couple minor tweaks), not too shabby. That means I might be able to compete for silver or bronze. ^^

```
DECLARE @ INT=100;WITH N AS(SELECT 1A UNION ALL SELECT A+1FROM N WHERE A<@)SELECT LEFT(A,LEN(A)-1+A%11)FROM N ORDER BY-A

```

This doesn't print a list, it selects the results. The question never gave specifics about output, so this should be fine. This still has the same limit of 100 on the input, partly because I'm abusing the fact that every 11th term under 100 loses a character and partly because of the default 100 recursion limit on common table expressions.

```
DECLARE @ INT=100;

WITH N AS
(
    SELECT 1A
    UNION ALL
    SELECT A+1
    FROM N
    WHERE A<@
)

SELECT LEFT(A,LEN(A)-1+A%11)
FROM N
ORDER BY-A

```

# Answer
> 7 votes
## Python 143 147

```
def t(n):
 p=o='';r=0 # p is previous string, o is output string, r is recycled bitmap
 while n and r<1023: # 1023 is first 10 bits set, meaning all digits have been recycled
    s=`n`;i=-1 # s is the current string representation of n
       # i is from end; negative offsets count backwards in strings
    while p.endswith(s[:i])-1:i-=1 # find common ending with prev; s[:0] is '',
       # which all strings end with
    for j in s[:i]:r|=1<<int(j) # mark off recycled bits
    o+=s[i:];p=s;n-=1 # concatenate output, prepare for next number
 print o # done

```

First level indent is space, second level is tab char.

# Answer
> 5 votes
# Haskell, ~~154~~ ~~149~~ ~~147~~ ~~145~~ ~~128~~ ~~120~~ ~~119~~ 117 bytes

```
import Data.List
(r%x)n|n>0&&r<":"=[(r\\t)%(x++(show n\\t))$n-1|t<-tails x,isPrefixOf t$show n]!!0|0<1=x
h=['0'..]%""

```

adding in the recycling-checking cost **a lot** of characters... sigh

golfed a bit by remembering what digits weren't recycled yet and stopping when the list is empty. then golfed a bit more by moving to explicit recursion and a few more tricks.

example output:

```
*Main> h 110
"110910810710610510410310210100998979695949392919089887868584838281807978776757473727170696867665646362616059585756554535251504948474645443424140393837363534332313029282726252423221"

```

# Answer
> 5 votes
# Python 2: 119 117

Marking this as community wiki because it is just a more golfed version of Will's answer.

```
n=input()
d=s,={''}
exec"t=`n`;i=len(t)\nwhile(s*i)[-i:]!=t[:i]:i-=1\ns+=t[i:];d|=set(t[:i]);n-=len(d)<11;"*n
print s

```

# Answer
> 4 votes
## Ruby, ~~145~~ ~~139~~ 130 bytes

```
n=gets.to_i
d=*?0..?9
s=''
n.times{|i|j=(t=(n-i).to_s).size;j-=1 while s[-j,j]!=u=t[0,j];d-=u.chars;s=t;$><<t[j..-1];exit if[]==d}

```

Similar approach to Will's, except I'm not using a bit mask, but a set-like array of unused digits instead. Input is via STDIN.

There's an alternative version using `while` instead of `times` but whatever I try, the number of bytes is the same:

```
n=gets.to_i
d=*?0..?9
s=''
(j=(t=n.to_s).size;j-=1 while s[-j,j]!=u=t[0,j];d-=u.chars;s=t;$><<t[j..-1];exit if[]==d;n-=1)while 0<n

```

# Answer
> 4 votes
## CJam, ~~80~~ ~~77~~ ~~65~~ ~~57~~ 54 Characters

~~Probably not at all optimized, but a~~ After a lot of optimizations and debugging here is the direct conversion of my ES6 answer in CJam:

```
Mr{s:C_,{:H<M_,H->=!_CH@-@}g:T>+:MCT<_O@-+:O,A<Ci(*}h;

```

Try it online here. The function takes the number as STDIN and outputs the recycled countdown, stopping in between if recycling is complete.

I will try to golf it further.

**How it works:**

Basic idea is that for each countdown number C, check if the first H digits are equal to the last H digits of the resultant string, where H goes from number of digits in C to 0

```
Mr                                    "Put an empty string and input on stack";
  { ... }h;                           "Run while top element of stack is true, pop when done";
s:C                                   "Store string value of top stack element in C"
   _,                                 "Put the number of characters in C to stack";
     { ... }g                         "Run while top element of stack is true";
:H<                                   "Store the digit iteration in H and slice C";
   M                                  "M is the final output string in making";
    _,H-                              "Take length of M and reduce H from it";
        >                             "Take that many digits of M from end and..."
         =!_                          "Compare with first H digits of C, negate and copy";
            CH@                       "Put C and H on stack and bring the above result to top of stack";
               -                      "Reduce H if the matched result was false";
                @                     "Bring the matched result on top in order continue or break the loop"
             :T                       "Store top stack element in T after the loop";
               >+:M                   "Take everything but first T digits of C and add it to M and update M";
                   CT<_               "Take first T digits of C and copy them";
                       O@             "Put saved digits on stack, and rotate top three elements";
                         -            "Remove all occurence of first T digits of C from O";
                          +:O         "Add first T digits of C to O and update O";
                             ,A<      "Compare number of saved digits with 10";
                                Ci(   "Decrement integer value of C and put it on stack";
                                   *  "If number of saved digits greater than 9, break loop";

```

# Answer
> 2 votes
## JavaScript ES6, ~~149~~ 146 characters

Such verbose, much characters, wow.

```
C=n=>{s=c='';while(n>0&s.length<10){j=1;while(t=(n+'').slice(0,-j++))if(c.endsWith(t)){s+=~s.search(t)?'':t;break}c+=(n--+'').slice(1-j)}return c}

```

Run it in latest Firefox's Web Console.

After running, it creates a method `C` which you can use like

```
C(12)
12110987654321

```

**UPDATE**: Sometimes, plain old `return` is shorter than arrow function closure :)

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


title: Triangle Puzzle

text:
# Question
Title: Triangle Puzzle
# Triangle Puzzle

Consider the triangle below. This triangle would be represented by the following input file.

```
   **5**
  **9** 6
 4 **6** 8
0 **7** 1 5

```

By starting at the top and moving to adjacent numbers on the row below, one creates a path to the bottom of the triangle. There are many such paths in a triangle, which may have different weights. The weight of a path is the sum of all numbers encountered along the way. Write a program to find the weight of the path with the highest weight for a given triangle.

In above example, the maximum sum from top to bottom is 27, and is found by following the bold text above path. 5 + 9 + 6 + 7 = 27.

(More formally: The triangle is an acyclic digraph, and each number represents the value of a node. Each node has either two or zero direct successors, as shown by the arrows above. A complete path is a path which begins at the root node—the one with no immediate predecessors—and ends at a node with no immediate successors. The weight of a complete path is the sum of the values of all nodes in the path graph. Write a program which finds the weight of the complete path with the largest weight for a given triangle.)

Bigger test sample data :

```
9235
9096 637
973 3269 7039
3399 3350 4788 7546
1739 8032 9427 976 2476
703 9642 4232 1890 704 6463
9601 1921 5655 1119 3115 5920 1808
645 3674 246 2023 4440 9607 4112 3215
660 6345 323 1664 2331 7452 3794 7679 3102
1383 3058 755 1677 8032 2408 2592 2138 2373 8718
8117 4602 7324 7545 4014 6970 4342 7682 150 3856 8177
1966 1782 3248 1745 4864 9443 4900 8115 4120 9015 7040 9258
4572 6637 9558 5366 7156 1848 2524 4337 5049 7608 8639 8301 1939
7714 6996 2968 4473 541 3388 5992 2092 2973 9367 2573 2658 9965 8168
67 1546 3243 752 8497 5215 7319 9245 574 7634 2223 8296 3044 9445 120
7064 1045 5210 7347 5870 8487 3701 4301 1899 441 9828 3076 7769 8008 4496 6796

```

# Answer
> 2 votes
> (More formally: The triangle is an acyclic digraph, and each number represents the value of a node. \<snip /\> A complete path is a path which begins at the root node—the one with no immediate predecessors—and ends at a node with no immediate successors. The weight of a complete path is the sum of the values of all nodes in the path graph. Write a program which finds the weight of the complete path with the largest weight for a given triangle.)

This easily generalises to any dag `G(V,E)` with weighted nodes. Perform a topological sort, and then iterate through the nodes in that order setting `weight[v] += max {weight[v'] : v' in predecessors(v)}`. Assuming a suitable representation, this is `O(E)`.

As an implementation note, it may be convenient to add a dummy "sink" node with weight 0 to which all the successor-less nodes of the original graph gain an edge. Alternatively it might be convenient to iterate through the topologically sorted nodes in reverse order using successors instead of predecessors.

The latter is the case given the special structure of the triangle, for which in addition it's possible to do an implicit topological sort and to use only `O(sqrt(V))` extra space (assuming that we mustn't alter the original graph and hence require extra space).

```
input: a triangular array T of n rows increasing in length from 1 to n

scratch = clone T[n-1]
for y = n-2 downto 0
    for x = 0 to y-1
        scratch[x] = T[y][x] + max(scratch[x], scratch[x+1])

output: scratch[0]

```

# Answer
> 1 votes
# Groovy

Here's a groovy script with two solutions, one using recursion and one using a "bottom-up" approach. The file "test\_sample\_data.txt" is assumed to be in the classpath.

```
// Read the sample data file, store as List<List<int>>
def triangle = getClass().
        getResource('test_sample_data.txt').        // get the file resource
        text.                                       // contents as string
        split('\n').                                // split into lines
        collect { line ->                           // collect rows
            line.split().collect { it as int }      // collect columns
        }

println "Recursive: ${findLargestWeightRecursively(triangle)}"
println "Bottom up: ${findLargestWeightBottomUp(triangle)}"

def findLargestWeightRecursively(List triangle, row = 0, col = 0) {
    def current = triangle[row][col]
    if (row < triangle.size() - 1) {
        def w1 = findLargestWeightRecursively(triangle, row + 1, col)
        def w2 = findLargestWeightRecursively(triangle, row + 1, col + 1)
        return Math.max(w1, w2) + current
    } else {
        return current
    }
}

def findLargestWeightBottomUp(List triangle) {
    def weights = triangle[triangle.size() - 1].clone()
    for (int row = triangle.size() - 2; row >= 0; row--) {
        def nextRow = triangle[row]
        for (int col = 0; col < nextRow.size(); col++) {
            def largest = Math.max(weights[col], weights[col + 1])
            weights[col] = nextRow[col] + largest
        }
        weights.remove(weights.size() - 1)
    }
    return weights[0]
}

```

**Output:**

```
Recursive: 108146
Bottom up: 108146

```

# Answer
> 1 votes
# My Perl Solution

## input file is named as input.txt

```
$refarray;
open TRIG, "input.txt";
while(<TRIG>){
$i++;
$_ =~ s/^\s+//g;
$_ =~ s/\s+$//g;
@num=split(/\s+/);
for $j (0...$#num) {
  $refarray[$i]->[$j]=$num[$j];
}
}
close TRIG;
while($i>0){
   for $j (0...$i-2){
      if($refarray[$i]->[$j]>$refarray[$i]->[$j+1])
    {
    $refarray[$i-1]->[$j]+=$refarray[$i]->[$j];
    }
      else{
    $refarray[$i-1]->[$j]+=$refarray[$i]->[$j+1];
    }
      $total=$refarray[$i-1]->[$j]."\t";
   }
$i-=1;
}
print $total;

```

# Answer
> 0 votes
Ruby, 2nd version

```
t=%w{
     1
    2 1
   3 2 1
  4 3 2 1
 5 4 3 2 1
1 2 3 4 5 10000
}.map &:to_i

l = []
i=1

loop do
    l.push t.slice!(0,i)
    i += 1
    break if t == []
end
trees = [0, 1].repeated_permutation(l.length-1).to_a.map! do |tree|
    [0].concat tree
end

trees.map! do |tree|
    newt = []
    tree.each_with_index do |e, i|
        newt.push tree.slice(0, i+1).inject :+
    end
    newt
end

rr = []
trees.each do |t|
    r = 0
    t.each_with_index do |v, i|
        r += l[i][v]
    end
    rr.push r
end
p rr.max

```

Code above outputs: `10005` Sample of data in the question results to `108146`

# Answer
> 0 votes
I solved this problem many years ago in a training for programming contest. Now I just translated to a modern language as C#.

```
int MaximumSum(List<List<int>> values)
{
    // Making a copy by values of all list and validating the data at same time.
    var numbers = new List<List<int>>();
    int index = 0;
    while ((index < values.Count) && (values[index] != null) && (values[index].Count == index + 1))
    {
        numbers.Add(new List<int>());
        for (int j = 0; j <= index; j++)
            numbers[index].Add(values[index][j]);
        index++;
    }
    if (index == values.Count)
    {
        /* Applying dinamic programming principles we can obtain the maximum value starting from the last row until the first one.
         * Storing only the optimum result until the specific value being analized.
         * At the end the value on the top of the triangle will be the maximum needed.
         */
        for (int row = numbers.Count - 2; row >= 0; row--)
            for (int col = 0; col <= row; col++)
                numbers[row][col] += (numbers[row + 1][col] > numbers[row + 1][col + 1]) ? numbers[row + 1][col] : numbers[row + 1][col + 1];
        return numbers[0][0];
    }
    else
    {
        throw new Exception("Invalid data");
    }
}

```

# Answer
> 0 votes
Python

Put the triangle in a file called "triangle.txt", with whitespace only between the numbers.

```
f=open("triangle.txt", "r")
triangle=eval("[["+f.read().replace(" ", ",").replace("\n", "],[")[:-4]+"]]")
f.close()
for i in range(len(triangle)-2, -1, -1):
    for j in range(len(triangle[i])):
        triangle[i][j]+=max(triangle[i+1][j+1],triangle[i+1][j])
    del triangle[i+1]
print triangle[0][0]

```

Example Triangle:

```
1      (   1   )
2 3    (  2 3  )
4 5 6  ( 4 5 6 )

```

The 2 has 4, 5 below it. 5\>4, so replace the 2 with 2+5=7.
The 3 has 5, 6 below it. 6\>5, so replace the 3 with 3+6=9.

```
1    (  1  )
7 9  ( 7 9 )

```

The 1 has 7, 9 below it. 9\>7, so replace the 1 with 1+9=10.

There are no more rows to process, so the maximal sum is 10.

# Answer
> 0 votes
# Q

```
t:"I"$'/:" "vs'read0`t;
{(-2_x),enlist (1_mmax[2;last x])+last -1_x}/[count[t]-1;t]
exit 0

```

It assumes the triangle is a space separated triangle of integers stored in a file called t.

On the second test case:

```
$ time q tri.q -q
108146

real    0m0.018s
user    0m0.010s
sys     0m0.010s

```

# Answer
> 0 votes
Here is my solution implementation in java. I got idea from this https://stackoverflow.com/a/8002423/205585

```
    package com.euler.problems;

    import java.util.*;

    public class Problem18
    {
       private static Map<Integer,List<Integer>> triangle = new HashMap<Integer,List<Integer>>();

       public static void main(String args[])
       {
         _init();
         int res = maxSum(triangle);
         System.out.println("Sum = "+res);
       }

       //max sum from top to bottom of right angled triangle
       public static int maxSum(Map<Integer,List<Integer>> triangle)
       {
         int sum = 0;
         if(triangle == null || triangle.isEmpty())
           return 0;
         int size = triangle.size();
         if(size == 1)
           return triangle.get(0).get(0);
         int i=size-2,tmp,tmp_max,max_value;
         while(i>=0)
         {
           List<Integer> current_row = new ArrayList<Integer>();
           current_row = triangle.get(i);
           for(int index=0; index<current_row.size(); index++)
           {
             tmp = current_row.get(index);
             tmp_max = tmp+triangle.get(i+1).get(index);
             max_value = tmp+triangle.get(i+1).get(index+1);
             if(tmp_max > max_value)
               max_value = tmp_max;
             current_row.set(index,max_value);
           }
           triangle.put(i,current_row);
           current_row = null;
           i--;

        }
      return triangle.get(0).get(0);
    }

    private static void _init()
    {
      List<List<Integer>> tuples = new ArrayList<List<Integer>>();
      tuples.add(Arrays.asList(75));
      tuples.add(Arrays.asList(95,64));
      tuples.add(Arrays.asList(17,47,82));
      tuples.add(Arrays.asList(18,35,87,10));
      tuples.add(Arrays.asList(20,4,82,47,65));
      tuples.add(Arrays.asList(19,1,23,75,3,34));
      tuples.add(Arrays.asList(88,2,77,73,7,63,67));
      tuples.add(Arrays.asList(99,65,4,28,6,16,70,92));
      tuples.add(Arrays.asList(41,41,26,56,83,40,80,70,33));
      tuples.add(Arrays.asList(41,48,72,33,47,32,37,16,94,29));
      tuples.add(Arrays.asList(53,71,44,65,25,43,91,52,97,51,14));
      tuples.add(Arrays.asList(70,11,33,28,77,73,17,78,39,68,17,57));
      tuples.add(Arrays.asList(91,71,52,38,17,14,91,43,58,50,27,29,48));
      tuples.add(Arrays.asList(63,66,4,68,89,53,67,30,73,16,69,87,40,31));
      tuples.add(Arrays.asList(4,62,98,27,23,9,70,98,73,93,38,53,60,4,23));
      int i=0;
      for(List<Integer> tuple : tuples)
      {
        triangle.put(i++,tuple);
      }
      //print
      for(Integer key : triangle.keySet())
     {
       System.out.println(triangle.get(key));
     }
    }
   }

```

# Answer
> 0 votes
Haskell solution

```
maximizeTree tree
    | length tree == 1 = head . head $ tree
    | otherwise = maximizeTree (take (length tree - 2) tree ++ [zipWith (\a b -> maximum a + b) (pairUpList . last $ tree) (tree !! (length tree - 2))])
    where pairUpList list = [[list !! n, list !! (n + 1)] | n <- [0 .. (length list - 2)]]

maximizeTree [[5], [9, 6], [4, 6, 8], [0, 7, 1, 5]]

```

# Answer
> 0 votes
Python solution where the file is read as list of lists and processed bottom up:

```
from io import open

def parse_file(fpath):
    return [[int(i) for i in l.strip('\n').split()] for l in open(fpath, "r").readlines()]

def process_row(lower, upper):
    results = []
    for i in range(0,len(upper)):
        results.append(upper[i] + max(lower[i], lower[i+1]))
    return results

def traverse_triangle_bottom_up(triangle):
    triangle.reverse()
    results = triangle.pop(0)
    for row in triangle:
        results = process_row(results, row)
    return results[0]

triangle = parse_file("triangle.txt")
max_weight = traverse_triangle_bottom_up(triangle)
print(max_weight)

```

---
Tags: code-challenge, math, number, fastest-code
---


title: Graph Google Search Results

text:
# Question
Title: Graph Google Search Results
When you search for something on Google, it conveniently gives a message near the top of the page saying something like `About 53,000,000 results (0.22 seconds)`. (The numbers change depending on what was searched of course.)

In this challenge you will write a program that draws a logarithmic ASCII graph of the number of results given by Google when all the non-empty prefixes of a given *search-phrase* are searched.

A *search-phrase* is defined as one or more strings of lowercase alphanumeric characters, separated by one space from each other. In Regex a search-phrase is `(?:[a-z0-9]+ )*[a-z0-9]+`.

So `im ok`, `r`, and `1a 2` are all search-phrases, but `I'm OK`, `R`, `1a 2`, and , are not.

(The character restrictions are in place because Google rarely takes case or special symbols into account. Escaping non-alphanumeric characters in URLs is also a hassle.)

# Spec

Your program must take in a search-phrase and a positive floating point number H from either stdin or the command line. (You can assume they are valid and it's fine if you need quotes or something around the search-phrase.)

As a working example let's assume the search phrase is `a car` and H = 0.75.

**Step 1:**
Gather the non-empty prefixes of your search-phrase, **and put them in double quotes**. The quotes ensure that that the exact phrase will be searched for, avoiding any 'did you mean...' redirections.

Exclude all prefixes that end in a space such as `a[space]`.

```
Prefixes
"a"
"a c"
"a ca"
"a car"

```

**Step 2:**
Search each of these terms exactly as they appear using https://www.google.com, and note the number of results returned.

```
Search Term    Message                                       Results
"a"            About 6,950,000,000 results (0.27 seconds)    6950000000
"a c"          About 861,000,000 results (0.27 seconds)      861000000
"a ca"         About 2,990,000 results (0.30 seconds)        2990000
"a car"        About 53,900,000 results (0.39 seconds)       53900000

```

**If the search term did not match any documents, put a 0 in the `Results` column.**

**Step 3:**
Compute `y = floor(H * log10(r + 1))` for each row, where r is the `Results` value. H is still 0.75 here.

```
Search Term    Results       y
"a"            6950000000    7
"a c"          861000000     6
"a ca"         2990000       4
"a car"        53900000      5

```

**Step 4:**
Arrange `y` number of vertical bars (`|`) above the last character of each unquoted search term, using spaces to fill empty areas, in a sort of bar graph.

```
|
| |
| | |
| |||
| |||
| |||
| |||
a car

```

This graph is the final result of your program and the only thing it needs to output. It should go to stdout.

# Scoring

This is , so the shortest program in bytes wins.

# Notes

* You may use URL shorteners or other search tools/APIs as long as the results would be the same as searching https://www.google.com.
* I know that double quotes are not a surefire way to exclude "did you mean..." redirections. Adding `&nfpr=1` to the URL doesn't always work either. Don't worry about these inaccuracies. Just look for the `About X results...` message no matter what pops up, or set `Results` to 0 if there is none.
* There is an empty column above any space in the search-phrase in the graph.
* The graph should not be wider or taller than it needs to be (e.g. with whitespace).
* It's ok if your program has side effects like opening a web browser so the cryptic Google html/js pages can be read as they are rendered.

# Answer
## Ruby, ~~316~~ 295 bytes

```
require 'open-uri'
s,h=*$*
r=[]
s.size.times{|i|r<<(s[i]==' '?'':?|*(h.to_f*Math.log10((URI.parse("http://google.com/search?q=#{URI::encode ?"+s[0..i]+?"}").read[/About [\d,]+ results/]||?0).gsub(/\D/,'').to_i+1)).floor)+s[i]}
puts r.map{|l|l.rjust(r.map(&:size).max).chars}.transpose.map &:join

```

Unfortunately, the requests just stopped working on the online tester I was using, so I need to golf this down further tonight or tomorrow.

Explanation: I'm taking the input via ARGV. Then I'm just sending a request for each substring that doesn't end in a space, find the results via regex (and default to `0` if the regex doesn't match), and then build the histogram with horizontal bars. At the end, I'm reversing all lines and transposing them to create the vertical histogram.
> 4 votes

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


title: Restricted memory optimization

text:
# Question
Title: Restricted memory optimization
The edit (or Levenshtein) distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other. If the two strings have length n each, it is well known that this can be done in O(n^2) time by dynamic programming. The following Python code performs this calculation for two strings `s1` and `s2`.

```
def edit_distance(s1, s2):
    l1 = len(s1)
    l2 = len(s2)

    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
      matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
      for sz in range(0,l1):
        if s1[sz] == s2[zz]:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
        else:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
    return matrix[l2][l1]

```

In this task you have to get as close are you can to computing the edit distance but with a severe memory restriction. Your code is allowed to define one array containing 1000 32-bit integers and this is to be the only temporary storage you use in your computation. All variables and data structures are to be contained in this array. In particular, you would not be able to implement the algorithm above as for strings of length 1000 as it would require you to store at least 1,000,000 numbers. Where your language doesn't naturally have 32 bit integers (for example Python) you simply need to make sure you never store a number larger than 2^32-1 in the array.

You may read in the data using any standard library of your choice without worrying about the memory restrictions in that part. In order to make the competition fair for the main part of your code, you may only use operations that are functionally equivalent to those in the C programming language and cannot use any external libraries.

To be extra clear, the memory to store the input data or used by your language's interpreter, JVM etc. does not count towards your limit and you may not write anything to disk. You must assume the input data is read-only when in memory so you can't reuse that to gain more working space.

**What do I have to implement?**

Your code should read in a file in the following format. It will have three lines. The first line is the true edit distance. The second is string 1 and the third is string 2. I will test it with the sample data at https://bpaste.net/show/6905001d52e8 where the strings have length 10,000 but it shouldn't be specialised for this data. It should output the smallest edit distance it can find between the two strings.

You will also need to prove your edit distance actually comes from a valid set of edits. Your code should have a switch which turns it into a mode that may use more memory (as much as you like) and outputs the edit operations that give your edit distance.

**Score**

Your score will be the `(optimal edit distance/divided by the edit distance you find) * 100`. To start things off, notice that you can get a score by just counting the number of mismatches between the two strings.

You can use any language you like which is freely available and easy to install in Linux.

**Tie break**

In the case of a tie-break, I will run your code on my Linux machine and the fastest code wins.

# Answer
# C++, Score 92.35

Estimation Algorithm: The algorithm finds the first place the two string differ, and then tries all possible N operation permutations (insert, delete, replace - characters that match are skipped without consuming an operation). It scores each possible set of operations based on how much farther that set of operations successfully matches the two strings, plus how much it causes the string lengths to converge. After determining the highest-scoring set of N operations, the first operation in the set is applied, the next mismatch is found, and the process repeats until the end of the string is reached.

The program tries all values of N from 1-10 and selects the level that gave the best results. N=10 is generally the best now that the scoring method takes the string length into consideration. Higher values of N would probably be even better, but take exponentially more time.

Memory Usage: Since the program is purely iterative, it needs very little memory. Only 19 variables are used to track the program state. These are set by #defines to act as global variables.

Usage: The program is used the same as feersum's: the first parameter is assumed to be the file, and any additional parameters indicate that the edits should be shown. The program always prints the estimated edit distance, and the score.

Verification Output: The verification output it formatted in three rows:

```
11011111100101100111100110100 110 0 0000   0 01101
R I          IR     R        D   D D    DDD D     D
01 1111110010 0001110001101000110101000011101011010

```

The top row is the target string, the middle is the operations, and the bottom is the string being edited. Spaces in the operation line indicate that the characters match. 'R' indicates that the edit string has it's character in that position replaced with the target string's character. 'I' indicates that the edit string has the target string's character inserted at that position. 'D' indicates that the edit string has it's character in that position deleted. The edit and target strings have spaces inserted when the other has a character inserted or deleted so they line up.

```
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <fstream>

int memory[1000];
#define first (*(const char **)&memory[0])
#define second (*(const char **)&memory[1])
#define block_ia memory[2]
#define block_ib memory[3]
#define block_n memory[4]
#define block_op memory[5]
#define block_o memory[6]
#define block_x memory[7]
#define n memory[8]
#define opmax memory[9]
#define best_op memory[10]
#define best_score memory[11]
#define score memory[12]
#define best_counter memory[13]
#define la memory[14]
#define lb memory[15]
#define best memory[16]
#define bestn memory[17]
#define total memory[18]

// verification variables
char printline1[0xffff]={};
char *p1=printline1;
char printline2[0xffff]={};
char *p2=printline2;
char printline3[0xffff]={};
char *p3=printline3;

// determine how many characters match after a set of operations
int block(){
    block_ia=0;
    block_ib=0;
    for ( block_x=0;block_x<block_n;block_x++){
        block_o = block_op%3;
        block_op /= 3;
        if ( block_o == 0 ){ // replace
            block_ia++;
            block_ib++;
        } else if ( block_o == 1 ){ // delete
            block_ib++;
        } else { // insert
            if ( first[block_ia] ){
                block_ia++;
            }
        }
        while ( first[block_ia] && first[block_ia]==second[block_ib] ){ // find next mismatch
            block_ia++;
            block_ib++;
        }
        if ( first[block_ia]==0 ){
            return block_x;
        }
    }
    return block_n;
}

// find the highest-scoring set of N operations for the current string position
void bestblock(){
    best_op=0;
    best_score=0;
    la = strlen(first);
    lb = strlen(second);
    block_n = n;
    for(best_counter=0;best_counter<opmax;best_counter++){
        block_op=best_counter;
        score = n-block();
        score += block_ia-abs((la-block_ia)-(lb-block_ib));
        if ( score > best_score ){
            best_score = score;
            best_op = best_counter;
        }
    }
}

// prepare edit confirmation record
void printedit(const char * a, const char * b, int o){
    o%=3;
    if ( o == 0 ){ // replace
        *p1 = *a;
        if ( *b ){
            *p2 = 'R';
            *p3 = *b;
            b++;
        } else {
            *p2 = 'I';
            *p3 = ' ';
        }
        a++;
    } else if ( o == 1 ){ // delete
        *p1 = ' ';
        *p2 = 'D';
        *p3 = *b;
        b++;
    } else { // insert
        *p1 = *a;
        *p2 = 'I';
        *p3 = ' ';
        a++;
    }
    p1++;
    p2++;
    p3++;
    while ( *a && *a==*b ){
        *p1 = *a;
        *p2 = ' ';
        *p3 = *b;
        p1++;
        p2++;
        p3++;
        a++;
        b++;
    }
}

int main(int argc, char * argv[]){

    if ( argc < 2 ){
        printf("No file name specified\n");
        return 0;
    }

    std::ifstream file(argv[1]);
    std::string line0,line1,line2;
    std::getline(file,line0);
    std::getline(file,line1);
    std::getline(file,line2);

    // begin estimating Levenshtein distance
    best = 0;
    bestn = 0;
    for ( n=1;n<=10;n++){ // n is the number of operations that can be in a test set
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            first++;
            second++;
        }
        total=0;
        while ( *first && *second ){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            total ++;
            first += block_ia;
            second += block_ib;
        }
        // when one string is exhausted, all following ops must be insert or delete
        while(*second){
            total++;
            second++;
        }
        while(*first){
            total++;
            first++;
        }
        if ( !best || total < best ){
            best = total;
            bestn = n;
        }
    }
    // done estimating Levenshtein distance

    // dump info to prove the edit distance actually comes from a valid set of edits
    if ( argc >= 3 ){
        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        n = bestn;
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            *p1 = *first;
            *p2 = ' ';
            *p3 = *second;
            p1++;
            p2++;
            p3++;
            first++;
            second++;
        }
        while ( *first && *second){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            printedit(first,second,best_op);
            first += block_ia;
            second += block_ib;
        }
        while(*second){
            *p1=' ';
            *p2='D';
            *p3=*second;
            p1++;
            p2++;
            p3++;
            second++;
        }
        while(*first){
            *p1=*first;
            *p2='I';
            *p3=' ';
            p1++;
            p2++;
            p3++;
            first++;
        }

        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        int ins=0;
        int del=0;
        int rep=0;
        while ( *p1 ){
            int a;
            for ( a=0;a<79&&p1[a];a++)
                printf("%c",p1[a]);
            printf("\n");
            p1+=a;
            for ( a=0;a<79&&p2[a];a++){
                ins += ( p2[a] == 'I' );
                del += ( p2[a] == 'D' );
                rep += ( p2[a] == 'R' );
                printf("%c",p2[a]);
            }
            printf("\n");
            p2+=a;
            for ( a=0;a<79&&p3[a];a++)
                printf("%c",p3[a]);
            printf("\n\n");
            p3+=a;
        }
        printf("Best N=%d\n",bestn);
        printf("Inserted = %d, Deleted = %d, Replaced=%d, Total = %d\nLength(line1)=%d, Length(Line2)+ins-del=%d\n",ins,del,rep,ins+del+rep,line1.length(),line2.length()+ins-del);
    }

    printf("%d, Score = %0.2f\n",best,2886*100.0/best);
    system("pause");
    return 0;
}

```
> 4 votes

# Answer
# C++ 75.0

The program is designed to work with arbitrary text strings. They can be of any different lengths as long as neither exceeds 13824 characters. It uses 1,897 16-bit integers, which is equivalent to 949 32-bit integers. At first I was writing it in C, but then realized there was no function for reading a line.

The first command-line argument should be a filename. If a second argument exists, a summary of the edits is printed. The first line in the file is ignored while the second and third are the strings.

The algorithm is a doubly blocked version of the usual algorithm. It performs basically the same number of operations, but is of course much less accurate, since if a common subsequence gets split over the edge of a block, much of the potential savings are lost.

```
#include <cstring>
#include <inttypes.h>
#include <iostream>
#include <fstream>

#define M 24
#define MAXLEN (M*M*M)
#define SETMIN(V, X) if( (X) < (V) ) { (V) = (X); }
#define MIN(X, Y) ( (X) < (Y) ? (X) : (Y) )

char A[MAXLEN+1], B[MAXLEN+1];
uint16_t d0[M+1][M+1], d1[M+1][M+1], d2[M+1][M+1];

int main(int argc, char**argv)
{

    if(argc < 2)
        return 1;

    std::ifstream fi(argv[1]);

    std::string Astr, Bstr;
    for(int i = 3; i--;)
        getline(fi, i?Bstr:Astr);
    if(!fi.good()) {
        printf("Error reading file");
        return 5;
    }
    if(Astr.length() > MAXLEN || Bstr.length() > MAXLEN) {
        printf("String too long");
        return 7;
    }

    strcpy(A, Astr.c_str());
    strcpy(B, Bstr.c_str());

    uint16_t lA = Astr.length(), lB = Bstr.length();
    if(!lA || !lB) {
        printf("%d\n", lA|lB);
        return 0;
    }
    uint16_t nbA2, nbB2, bA2, bB2, nbA1, nbB1, bA1, bB1, nbA0, nbB0, bA0, bB0; //block, number of blocks
    uint16_t iA2, iB2, iA1, iB1, jA2, jB2, jA1, jB1; //start, end indices of block

    nbA2 = MIN(M, lA);
    nbB2 = MIN(M, lB);
    for(bA2 = 0; bA2 <= nbA2; bA2++) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        for(bB2 = 0; bB2 <= nbB2; bB2++) {
            if(!(bA2|bB2)) {
                d2[0][0] = 0;
                continue;
            }
            iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
            d2[bA2][bB2] = ~0;
            if(bB2)
                SETMIN(d2[bA2][bB2], d2[bA2][bB2-1] + (jB2-iB2));
            if(bA2)
                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2] + (jA2-iA2));

            if(bA2 && bB2) {
                nbA1 = MIN(M, jA2-iA2);
                nbB1 = MIN(M, jB2-iB2);
                for(bA1 = 0; bA1 <= nbA1; bA1++) {
                    iA1 = iA2 + (jA2-iA2) * (bA1-1)/nbA1, jA1 = iA2 + (jA2-iA2) * bA1/nbA1;
                    for(bB1 = 0; bB1 <= nbB1; bB1++) {
                        if(!(bA1|bB1)) {
                            d1[0][0] = 0;
                            continue;
                        }
                        iB1 = iB2 + (jB2-iB2) * (bB1-1)/nbB1, jB1 = iB2 + (jB2-iB2) * bB1/nbB1;
                        d1[bA1][bB1] = ~0;
                        if(bB1)
                            SETMIN(d1[bA1][bB1], d1[bA1][bB1-1] + (jB1-iB1));
                        if(bA1)
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1] + (jA1-iA1));

                        if(bA1 && bB1) {
                            nbA0 = jA1-iA1;
                            nbB0 = jB1-iB1;
                            for(bA0 = 0; bA0 <= nbA0; bA0++) {
                                for(bB0 = 0; bB0 <= nbB0; bB0++) {
                                    if(!(bA0|bB0)) {
                                        d0[0][0] = 0;
                                        continue;
                                    }
                                    d0[bA0][bB0] = ~0;
                                    if(bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0][bB0-1] + 1);
                                    if(bA0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0] + 1);
                                    if(bA0 && bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0-1] + (A[iA1 + nbA0 - 1] != B[iB1 + nbB0 - 1]));
                                }
                            }
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1-1] + d0[nbA0][nbB0]);
                        }
                    }
                }

                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2-1] + d1[nbA1][nbB1]);
            }
        }
    }
    printf("%d\n", d2[nbA2][nbB2]);

    if(argc == 2)
        return 0;

    int changecost, total = 0;
    for(bA2 = nbA2, bB2 = nbB2; bA2||bB2; ) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
        if(bB2 && d2[bA2][bB2-1] + (jB2-iB2) == d2[bA2][bB2]) {
            total += changecost = (jB2-iB2);
            char tmp = B[jB2];
            B[jB2] = 0;
            printf("%d %d deleted {%s}\n", changecost, total, B + iB2);
            B[jB2] = tmp;
            --bB2;
        } else if(bA2 && d2[bA2-1][bB2] + (jA2-iA2) == d2[bA2][bB2]) {
            total += changecost = (jA2-iA2);
            char tmp = B[jA2];
            A[jA2] = 0;
            printf("%d %d inserted {%s}\n", changecost, total, A + iA2);
            A[jA2] = tmp;
            --bA2;
        } else {
            total += changecost = d2[bA2][bB2] - d2[bA2-1][bB2-1];
            char tmpa = A[jA2], tmpb = B[jB2];
            B[jB2] = A[jA2] = 0;
            printf("%d %d changed {%s} to {%s}\n", changecost, total, B + iB2, A + iA2);
            A[jA2] = tmpa, B[jB2] = tmpb;
            --bA2, --bB2;
        }
    }

    return 0;
}

```
> 7 votes

# Answer
# Python, 100

I did manage to calculate the edit distance perfectly in the allotted memory limit. Sadly, this entry violates two rules of the challenge, in letter if not in spirit.

First, I have not actually stored my data in 1000 32-bit ints. For 10000-character strings, my program creates two 10000-element arrays that will only contain +1, 0, or -1. At 1.585 bits per ternary number, it would be possible to pack those 20000 trits into 31700 bits, leaving 300 bits as more than enough for my 7 remaining 16-bit integers.

Second, I have not implemented the required mode for showing edits. I have, alternately, implemented a mode that prints out the full edit matrix. It is absolutely possible to calculate the edit path from that matrix, but I don't have time right now to implement it.

```
#!/usr/bin/env python

import sys

# algorithm originally from
# https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows

print_rows = False
if len(sys.argv) > 2:
    print_rows = True

def LevenshteinDistance(s, t):
    # degenerate cases
    if s == t:
        return 0
    if len(s) == 0:
        return len(t)
    if len(t) == 0:
        return len(s)

    # create two work vectors of integer distance deltas

    # these lists will only ever contain +1, 0, or -1
    # so they COULD be packed into 1.585 bits each
    # 15850 bits per list, 31700 bits total, leaving 300 bits for all the other variables

    # d0 is the previous row
    # initialized to 0111111... which represents 0123456...
    d0 = [1 for i in range(len(t)+1)]
    d0[0] = 0
    if print_rows:
        row = ""
        for i in range(len(t)+1):
            row += str(i) + ", "
        print row

    # d1 is the row being calculated
    d1 = [0 for i in range(len(t)+1)]

    for i in range(len(s)-1):
        # cummulative values of cells north, west, and northwest of the current cell
        left = i+1
        upleft = i
        up = i+d0[0]
        if print_rows:
            row = str(left) + ", "
        for j in range(len(t)):
            left += d1[j]
            up += d0[j+1]
            upleft += d0[j]
            cost = 0 if (s[i] == t[j]) else 1
            d1[j + 1] = min(left + 1, up + 1, upleft + cost) - left
            if print_rows:
                row += str(left+d1[j+1]) + ", "

        if print_rows:
            print row

        for c in range(len(d0)):
            d0[c] = d1[c]

    return left+d1[j+1]

with open(sys.argv[1]) as f:
    lines = f.readlines()

perfect = lines[0]
string1 = lines[1]
string2 = lines[2]
distance = LevenshteinDistance(string1,string2)
print "edit distance: " + str(distance)
print "score: " + str(int(perfect)*100/distance) + "%"

```

example input:

```
2
101100
011010

```

example verbose output:

```
0, 1, 2, 3, 4, 5, 6,
1, 1, 1, 2, 3, 4, 5,
2, 1, 2, 2, 2, 3, 4,
3, 2, 1, 2, 3, 2, 3,
4, 3, 2, 1, 2, 3, 3,
5, 4, 3, 2, 1, 2, 3,
6, 5, 4, 3, 2, 2, 2,
edit distance: 2
score: 100%

```
> 3 votes

---
Tags: string, code-challenge, optimization, edit-distance
---


title: Golfscript Diagonal Array

text:
# Question
Title: Golfscript Diagonal Array
Is there a way in Golfscript to bring all of the diagonals of an array into a single array?

For example, for the array

```
[[1 2 3][4 5 6][7 8 9]]

```

return

```
[[7][4 8][1 5 9][2 6][3]]

```

(not necessarily in that order) and for

```
["ABCD""EFGH""IJKL"]

```

return

```
["I""EJ""AFK""BGL""CH""D"]

```

(not necessarily in that order). Assume the lengths of the arrays are the same.

I am struggling with figuring it out. I tried doing something with `=` and iterating through the `(length+1)`th character of the strings, but that didn't work. Can someone help me?

I'd like the shortest way to do this, if possible.

# Answer
Consider

```
[
    "ABCD"
    "EFGH"
    "IJKL"
]

```

To obtain the main diagonal and the diagonals above it, we can shift out the first char of the second row and the first two of the third:

```
[
    "ABCD"
    "FGH"
    "KL"
]

```

Note that all columns correspond to a diagonal, so "zipping" the array (i.e., transposing rows and columns) will yield an array containing the aforementioned four diagonals:

```
[
    "AFK"
    "BGL"
    "CH"
    "D"
]

```

We're still missing the diagonals below the main diagonal.

If we zip A itself and repeat the above process, we'll obtain an array containing the main diagonal and all diagonals *below* it. All that's left it to compute the set union of both arrays.

Putting it all together:

```
[.zip]{:A,,{.A=>}%zip}/|

[.zip]{              }/  # For the original array and it's transpose, do the following:
       :A                # Store the array in A.
         ,,{    }%       # For each I in [ 0 1 ... len(A) ], do the following:
            .A=>         # Push A[I] and shift out its first I characters.
                  zip    # Transpose the resulting array.
                       | # Perform set union.

```

Try it online.

Finally, if we only need the diagonals because we're searching for a string inside them (like in the Word Search Puzzle, which I assume inspired this question), a "less clean" approach might also be suitable.

You can use

```
..,n**\.0=,\,+)/zip

```

to obtain all diagonals, plus some unnecessary linefeed characters.

I've explained the process in detail in this answer.

Try it online.
> 8 votes

---
Tags: code-golf, array, tips, golfscript
---


title: Writing Phrases with Code

text:
# Question
Title: Writing Phrases with Code
This is my first contest, so please tell me what I can do to improve.

The object of this contest is to write program lines in your language of choice that are both valid code and self-descriptive in English, such as this Golfscript program:

```
This program outputs 4 twice.

```

You may use any language features, libraries, #defines, etc. that you want; however, a setup must not be over 10 lines (no, you can't cheat using ; or any such line separator :P).

The program with the most upvotes by midnight on October 1st wins.

# Answer
## Python

```
# This "program" does nothing and assumes "valid code" means it doesn't throw an error.

```

You *might* want to tighten up the rules a bit.
> 7 votes

# Answer
# C

This was too easy...

```
#define This int
#define program main(){
#define prints printf(
#define and );
#define exits }

This program prints "Hello world!" and exits

```

## English

```
This program outputs 99 verses in the manner:
"N bottles of beer on the wall
N bottles of beer
Take one down and pass it around
N-1 bottles of beer on the wall",
where N is replaced by numbers from 99 to 1
and 1-1=0 is replaced by "No more".
After that there is hundredth verse:
"No more bottles of beer on the wall
No more bottles of beer
Go to the store and buy some more
99 bottles of beer on the wall".

```
> 2 votes

# Answer
# OS X say

```
say whatever you want man!

```
> 1 votes

---
Tags: popularity-contest, source-layout
---


title: Moore Iteration

text:
# Question
Title: Moore Iteration
## Info

The numbers 1 to 9 each represent a cell in the Moore's Neighbourhood, with 5 being the central cell. So:

```
123
456
789

1={-1,-1} 2={-1, 0} 3={-1, 1}
4={ 0,-1} 5={ 0, 0} 6={ 0, 1}
7={ 1,-1} 8={ 1, 0} 9={ 1, 1}

```

## The Challenge

You may take input via STDIN, ARGV or function argument and either return the result or print it to STDOUT. Input is a N x N grid (torus topology, meaning if x or y is \< 1 then x or y = N, and if x or y \> N then x or y = 1), and your program must output one interation of that grid by replacing each cell with the value at its Moore's Neighbourhood cell.

Example Input grid (2 x 2):

```
13
79

```

Output:

```
97
31

```

Explanation:

Starting at position 1,1 we have the value 1, since value 1={-1,-1} we have to retrieve 1+(-1),1+(-1) = 0,0. And because it's a torus 0,0 we wrap around to N. So we retrieve the cell value at position 1,1 (1) with the cell value at position 2,2 (9).

For the next cell 1,2 we have value 3 (=-1, 1) so 1+(-1),2+(1) = 0,3. Wraps around to 2,1 which is value 7.

Next cell value at 2,1 is 7 (= 1,-1) so 2+(1),1+(-1) = 3,0. Wraps around to 1,2 which is value 3.

Next cell value at 2,2 is 9 (= 1, 1) so 2+(1),2+(1) = 3,3. Wraps around to 1,1 which is value 1.

## More Examples

Input Grid (3 x 3):

```
123
456
789

```

Expected Output:

```
987
654
321

```

Input Grid (5 x 5):

```
77497
81982
32236
96336
67811

```

Expected Output:

```
28728
37337
11923
73369
77433

```

## Final Notes

If you have any question, don't hesitate to comment. This is a code golf challenge, **shortest code wins!**

# Answer
## APL (33)

APL was *made* for this. This is a function that takes the input grid as an N-by-N matrix and returns the output grid as an N-by-N matrix.

```
{(⍳⍴⍵)⌷¨(,∆∘.⊖(∆←2-⌽⍳3)∘.⌽⊂⍵)[⍵]}

```

Test:

```
      ⍝ define input matrices
      ∆1 ← ↑(1 3)(7 9)
      ∆2 ← ↑(1 2 3)(4 5 6)(7 8 9)
      ∆3 ← ↑(7 7 4 9 7)(8 1 9 8 2)(3 2 2 3 6)(9 6 3 3 6)(6 7 8 1 1)
      ⍝ show input matrices
      ∆1 ∆2 ∆3
 1 3  1 2 3  7 7 4 9 7
 7 9  4 5 6  8 1 9 8 2
      7 8 9  3 2 2 3 6
             9 6 3 3 6
             6 7 8 1 1
      ⍝ apply function to input matrices giving output matrices
      {(⍳⍴⍵)⌷¨(,∆∘.⊖(∆←2-⌽⍳3)∘.⌽⊂⍵)[⍵]} ¨ ∆1 ∆2 ∆3
 9 7  9 8 7  2 8 7 2 8
 3 1  6 5 4  3 7 3 3 7
      3 2 1  1 1 9 2 3
             7 3 3 6 9
             7 7 4 3 3

```
> 9 votes

# Answer
## Python, 174

```
def t(b):b=b.split("\n");E=enumerate;C=[-1]*3+[0]*3+[1]*3+[-1,0,1]*3;print"\n".join("".join(b[(i+C[int(x)-1])%len(b)][(j+C[int(x)+8])%len(y)]for j,x in E(y))for i,y in E(b))

```

Python was *not* made for this... APL was!
> 5 votes

# Answer
## Python, 105

Takes and returns a list of lists:

```
def f(a):e=enumerate;n=len(a);return[[a[(y+(v-1)/3-1)%n][(x+(v-1)%3-1)%n]for x,v in e(u)]for y,u in e(a)]

```

Takes and returns a string (148 characters):

```
def f(s):
 a=[map(int,l)for l in s.split()];n=len(a);e=enumerate
 for y,u in e(a):print''.join(`a[(y+(v-1)/3-1)%n][(x+(v-1)%3-1)%n]`for x,v in e(u))

```
> 3 votes

# Answer
# MATLAB - 121 bytes

```
function O=X(I),m=size(I,1);n=3*m;o=-1:1;c=o<2;M=c'*o+n*o'*c;D=repmat(I,3);C=D;C(:)=1:n*n;t=m+(1:m);O=C+M(D);O=D(O(t,t));

```

MATLAB was slightly less made for this than APL, but slightly more made for this than Python. ;)

### Test Output

```
X( [1 2 3; 4 5 6; 7 8 9] )

ans =

     9     8     7
     6     5     4
     3     2     1

X( [7 7 4 9 7; 8 1 9 8 2; 3 2 2 3 6; 9 6 3 3 6; 6 7 8 1 1] )

ans =

     2     8     7     2     8
     3     7     3     3     7
     1     1     9     2     3
     7     3     3     6     9
     7     7     4     3     3

```
> 2 votes

---
Tags: code-golf
---