[Advent Of Code] is a set of programming problems devised by Eric Wastl. They were originally posted in December 2015, one pair of problems per day.

The problems are suitable for all levels of programmer. Solutions are posted here to demonstrate J's value as a general-purpose programming language.

## Problem 1 (Count Parentheses)

input is a file containing randomly chosen parenthesis characters starting with "(". "(" means "go up a floor", ")" means "descend 1 floor". puzzle: On what floor does Santa finish? Start at 0.

### Part 1

```

mp=: +/ .*

PART1=: +/ 1 _1 mp '()'=/read'input'
```

-- contributed by David Lambert

### Part 2

```NB. part 2 puzzle: when does Santa enter the basement?
PART2=: >: _1 i.~ +/\ 1 _1 mp '()'=/read'input'
```

-- contributed by David Lambert

## Problem 2 (Wrapping Paper)

input is a file such as
```4x23x21
22x29x19```

### Part 1

```read=: 1!:1@:boxopen

SIZES=: |: _3 [\ _".(e.&(CR,LF,'x'))`(,:&' ')}read'input'
NB. observe that SIZES is the transposed matrix so that
NB. items are length, width, and height.

Note '(2 */\ (, {.))'
(, {.)'LWH'  is   'LWHL'
into which we insert multiply in length 2 infixes.
producing the areas LW, WH, and HL.
)

Note '(+: , <./)'
double the areas and concatenate the smallest.
)

PART1=: +/ , (+: , <./) (2 */\ (, {.)) SIZES
```

-- contributed by David Lambert

### Part 2

With SIZES as the 3 by package tally array from Part 1 we have this crazy formula for ribbon length. For minimal circumference I've summed length+height+width and subtracted the (per package) minimum.

```volume=: */

circumference=: +:@:(+/ - >./)

PART2=: ([: +/ [: , (volume + circumference)) SIZES
```

-- contributed by David Lambert

## Problem 3 (Package Delivery)

Here the input file contains a sequence of characters randomly chosen from <>v^ . How many homes on this 2D grid receive at least one gift? The characters indicate to move one cell in pointed direction.

```   NB. complex number review.  Successive multiplications give right, up, left, down increments.
NB. corresponding to 0 degrees, 90 degrees, 180 degrees, 270 degrees.  (North is to the right and the compass is right handed if your mental picture is geocentric.)
0j1(^i.)4
1 0j1 _1 0j_1
```

-- idea contributed by Alex Shroyer

### Part 1

The tour verb consists of two pieces. The right hand side of at (@:) converts the input to a vector of increments concatenated to the starting location. On the left hand side is a verb inserted. This verb takes as x the increment, and as y the vector of places visited. Tail of y is the current location. Result of this verb is the path traversed (all of y) with the new location appended. J does all this work from right to left and that explains the reversal (|.). Starting location and traversal direction shouldn't affect the solution. With the locations known we just need the tally of the nub.

```read=: 1!:1@:boxopen
tour=: (] , (+ {:))/@:(0 ,~  ((0j1(^i.)4) {~ '>^<v'&i.))
PART1=: # ~. tour ROUTE
```

-- contributed by David Lambert

### Part 2

The part 2 puzzle splits the deliveries among 2 Santas. Apply tour to each group, combine the result, and get the tally of the nub of the resulting locations. This solution uses information from Part 1.

```PART2=: # ~. ,/ tour"1 |: _2[\ROUTE
```

We can draw the path. One way, require'plot' then plot tour ROUTE . We can color the route by history using viewmat. xy separates the complex data to real and imaginary parts then shifts it from [min,max] to [0,max-min]. xy@:visits creates a matrix of grid coordinates, x in column 0, y in column 1. This list is input to... This expression: `((>:@:i.@:#@:[)`(<"1@:[)`(])} (0 \$~ >:@:(>./)))` is a hook. `(dyad monad) y` evaluates as `y dyad monad y` The dyad in the hook is dyadic amend values`indexes`array} which operates on the array of zeros given by `(0 \$~ >:@:(>./)`) . We increment the shape so the maximum index values are bounded. (If the tally is n then the valid non-negative indexes are on [0, n-1]).

```NB. draw the drunken walk

require 'viewmat'

xy=: (-"1 <./)@:+.

viewmat@:((>:@:i.@:#@:[)`(<"1@:[)`(])} (0 \$~ >:@:(>./)))@:xy@:visits ROUTE
```

-- contributed by David Lambert

## Problem 4 (MD5)

Given a key, say 'abcdef' append incremental numbers until the md5 hash starts with 5 zeros. Part 2 the hash starts with 6 zeros. Unfortunately, the md5 addon does not work universally. The 64 bit repair is as follows:

```NB. load'~addons/convert/misc/md5.ijs'

NB. convert/misc/md5
NB. RSA Data Security, Inc. MD5 Message-Digest Algorithm
NB. version: 1.0.2
NB.
NB. See RFC 1321 for license details
NB. J implementation -- (C) 2003 Oleg Kobchenko;
NB.
NB. 09/04/2003 Oleg Kobchenko
NB. 03/31/2007 Oleg Kobchenko j601, JAL
NB. 12/17/2015 G.Pruss j803-64

coclass 'pcrypt'

NB. lt= (*. -.)~   gt= *. -.   ge= +. -.   xor= ~:
'`lt gt ge xor and or sh'=: (20 b.)`(18 b.)`(27 b.)`(22 b.)`(17 b.)`(23 b.)`(33 b.)
rot=: 16bffffffff and sh or ] sh~ 32 -~ [ NB. (y << x) | (y >>> (32 - x))
hexlist=: tolower@:,@:hfd@:,@:(|."1)@(256 256 256 256&#:)

cmn=: 4 : 0
'x s t'=. x [ 'q a b'=. y
)

ff=: cmn (((1&{ and 2&{) or 1&{ lt 3&{) , 2&{.)
gg=: cmn (((1&{ and 3&{) or 2&{ gt 3&{) , 2&{.)
hh=: cmn (((1&{ xor 2&{)xor 3&{       ) , 2&{.)
ii=: cmn (( 2&{ xor 1&{  ge 3&{       ) , 2&{.)
op=: ff`gg`hh`ii

I=: ".;._2(0 : 0)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 6 11 0 5 10 15 4 9 14 3 8 13 2 7 12
5 8 11 14 1 4 7 10 13 0 3 6 9 12 15 2
0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9
)
S=: 4 4\$7 12 17 22 5 9 14 20 4 11 16 23 6 10 15 21
T=: 4 16\$<.16b100000000*|1 o.>:i.64 NB. Constants cache generated by sine

norm=: 3 : 0
n=. 16 * 1 + _6 sh 8 + #y
b=. n#0  [  y=. a.i.y
for_i. i. #y do.
b=. ((j { b) or (8*4|i) sh i{y) (j=. _2 sh i) } b
end.
b=. ((j { b) or (8*4|i) sh 128) (j=._2 sh i=.#y) } b
_16]\ (8 * #y) (n-2) } b
)

NB.*md5 v MD5 Message-Digest Algorithm
NB.  diagest=. md5 message
md5=: 3 : 0
X=. norm y
q=. r=. 16b67452301 16befcdab89 16b98badcfe 16b10325476
for_x. X do.
for_j. i.4 do.
l=. ((j{I){x) ,. (16\$j{S) ,. j{T
for_i. i.16 do.
r=. _1|.((i{l) (op@.j) r),}.r
end.
end.
end.
hexlist r
)

md5_z_=: md5_pcrypt_

NB. standart tests
assert 'd41d8cd98f00b204e9800998ecf8427e' -: md5 ''
assert '7215ee9c7d9dc229d2921a40e899ec5f' -: md5 ' '
assert '0cc175b9c0f1b6a831c399e269772661' -: md5 'a'
assert '900150983cd24fb0d6963f7d28e17f72' -: md5 'abc'
assert 'f96b697d7cb7938d525a2f31aaf161d0' -: md5 'message digest'
assert 'c3fcd3d76192e4007dfb496cca67e13b' -: md5 a=.'abcdefghijklmnopqrstuvwxyz'
assert 'd174ab98d277d9f5a5611c2c9f419d9f' -: md5 'ABCDEFGHIJKLMNOPQRSTUVWXYZ',a,'0123456789'
assert '57edf4a22be3c955ac49da2e2107b67a' -: md5 80\$'1234567890'
```

-- contributed by Moon S https://github.com/georgiy-pruss/2-J/blob/master/md5.ijs

With this code we continue to part 1. The hooked sentence (copy~ selection"_1)DATA is often useful.

### Part 1

Assume the solution is in the first million. This succeeds, but is dreadfully slow. A compiled version of the md5 algorithm helps.

```   key=: 'yzbqklnj'

A=:(key,":)&.>;/i.1000000

\$A
1000000

4{.A
┌─────────┬─────────┬─────────┬─────────┐
│yzbqklnj0│yzbqklnj1│yzbqklnj2│yzbqklnj3│
└─────────┴─────────┴─────────┴─────────┘

B=:md5&>A

(#~ ('00000' (-:"1) _ 5&{.))B
000002c655df7738246e88f6c1c43eb7
000009a91d3753055962a4758e9bca48

(i. (#~ ('00000' (-:"1) _ 5&{.)))B
282749 384166
```

-- contributed by David Lambert

### Part 2

And, not to be a language despot, a python solution is

```from hashlib import md5

key = b'yzbqklnj'

i = 0

while True:
a = md5(key+'{}'.format(i).encode('utf8')).hexdigest()
if a.startswith('0'*5):
print(a, i)
if a.startswith('0'*6):
break
i += 1
```

-- contributed by David Lambert

## Problem 5 (Find Nice Strings)

### Part 1

```read=: 1!:1@:boxopen

NB. part 1
enough_vowels=: 2 < ([: +/ e.&'aeiou')"1
letter_repeats=: 1 e. (=|.!.' ')
bad_words=: 1 e. [: , (_2[\'abcdpqxy')&(E."1/)

nice =: (1 1 0 -: enough_vowels,letter_repeats,bad_words)"1

PART1=: +/ nice STRINGS
```

-- contributed by David Lambert

`|.!.` customized shift reminded to us -- by Henry Rich

### Part 2

```NB. Read in the strings from the clipboard
i =. ];._2 wd 'clippaste'
NB. Direct implementation: Find all 2-atom infixes; examine (location of each)-(first occurrence of same value):
NB. a result > 1 means a repeated infix.  Also, go through 3-item infixes, see which ones have first
NB. letter = last.  Apply to each string.
+/ ([: +./ 3&(=/@:(0 _1&{)\)) *. (1 < >./@(i.@# - i.~)@(2&(]\)))"1 i
```

-- contributed by Henry Rich

## Problem 6 (Light Control)

### Part 1

```NB. Convert the action script into a J script.
NB. First, make each line an assignment statement and enclose block-sizes in parentheses
i =. <@('y =. y ' , ;@(<@('(' , ,&')');._2)@:(,&' '));._2 wd 'clippaste'
NB. Define the verbs: through (to create a 1000x1000 block with 1s in the active positions
through =: (1000 1000 {. ({. (\$&1)))/@(-~/\)@:-@(,:~ >:)
NB. turn: NOP
turn =: 1 : 'u'
NB. on/off/toggle - to combine the result of through with the previous state
'`off on toggle' =: >`+.`~:
NB. Treat the input as a single verb to be executed
+/@, 3 : i 1000 1000 \$ 0
```

### Part 2

```NB. Same idea, with different definition of off/on/toggle
'`off on toggle' =: (0 >. -)`+`(+ +:)
+/@, 3 : i 1000 1000 \$ 0
```

-- contributed by Henry Rich

## Problem 7 (Wiring Simulation)

### Part 1

```LC =: 'abcdefghijklmnopqrstuvwxyz'
'`NOT OR AND LSHIFT RSHIFT' =: (65535&-)`(23 b.)`(17 b.)`(65535 (17 b.) (33 b.)~)`(33 b.~ -)
NB. Read input, convert to words.  There seems to be an extra LF
NB. Extract signal-names (which start with lowercase), giving list of boxed names, where the last name
NB. is the output and the preceding are the inputs that produced it
Nm =: (#~ e.&LC@{.@>)&.> I =: a: -.~ <@;:;._2 wd 'clippaste'
NB. Perform topological sort on names.  Result is the list of names in the order
NB. they need to be evaluated.  The implementation is recursive: find names that need no inputs;
NB. make them the first results; recur on all the rest; join the first results with the result of the
NB. recursion.
Toponm =: ((;@#~ ([ , \$:@(-.L:1~)^:(*.&*&#)) (#~ -.)) 1&>:@#@>) Nm
NB. Sort lines by result-name, convert to executable J assignments, execute
([: ".@(;:^:_1) {: , '=:' ; _3&}.)@> I /: Toponm i. {:@> I
NB. Result?
a
```

-- contributed by Henry Rich

### Part 2

Part 2 has the same solution as part 1 but solved with a new input signal on wire "b". This solution uses the name space of a locale to track the known names from which a new sentence may be completed. The input is stored in a file named input. Completed sentences are removed from the list of sentences needing completion. x and y are capitalized to avoid name conflict in the explicit verb.

```read=: 1!:1@:boxopen

f=: 3 :0
AND=: 2b10001 b.
OR=: 2b10111 b.
BITS16=:16bffff
LSHIFT=: BITS16 AND (33 b.)~
RSHIFT=: LSHIFT -
NOT=: BITS16&(2b10110 b.)
while. ([smoutput)#y do.
if. (0 = [: # ([: ". {.) :: (''"_)) y do.
y =. 1 |. y
else.
smoutput {.y
y =. }. y
end.
end.
a
)

L=: 18!:3''
topological_eval__L=: f f.

PART1=: topological_eval__L SENTENCES

M=: 18!:3''
topological_eval__M=: f f.

PART2=: PART1 ([: topological_eval__M ({:@:\$@:]{.'b=:',[:":[)`([:I.'b=:'(-:"1)_ 3{.])`]})SENTENCES

```

-- contributed by David Lambert

## Problem 8 (Counting Escaped Characters)

### Part 1

```NB. Read in the data from the clipboard, one box per line, with blank lines removed
i =. a: -.~ <;._2 wd 'clippaste'
NB. On the left, find mask of \x sequences; on the right, the mask of unescaped \
NB. Add up: 2 (for " chars) + 2 * number of unescaped \x, plus number of unescaped \
+/ ('\x'&E. (2 + (2 * +/@:*.) + +/@]) >/\.&.|.@('\'&=))@> i
```

-- contributed by Henry Rich

Using sequential machine, and with file `input` containing the input

```read=: 1!:1@:boxopen
mp=: +/ .*

M=: (>:@:i.@:# mp a.&e.&>)(Num_j_,6{.26}.Alpha_j_);(;/'"\x')

Note'the sequential machine'
Puzzle solution is the count of boxes.
Each box contains an item for later count.
[0] start.
[1] error condition.   Use 1j3 to enter this state.
[2] escape \ found
[3] \xD
[4] \xDD
[5] unescaped "
)

S=:  +. ". }. [;._2 noun define
boring  hex     "       \       x
[0]  0j0     0j0     5j1     2j1     0j0     NB. normal
[1]  1j6     1j6     1j6     1j6     1j6     NB. error
[2]  1j3     1j3     0j3     0j3     3j0     NB. start of \ sequence
[3]  1j3     4j0     1j3     1j3     1j3     NB. \xH
[4]  1j3     0j3     1j3     1j3     1j3     NB. \xHH
[5]  0j3     0j3     5j2     2j2     0j3     NB. "
)

```

-- contributed by David Lambert

### Part 2

```NB. For each line: 2 for outer quotes, plus one for each character that must be escaped
+/ (2 + +/@(e.&'"\'))@> i
```

-- contributed by Henry Rich

## Problem 9 (Traveling Salesman)

### Part 1

```NB. Read in data, convert to array
i =: (+ |:) 0 ,~ 0 ,. |."1 |.@:((0&".)@>)/./ |: (0 _1&{)@;:;._2 }: wd 'clippaste'
NB. Find shortest path by enumerating all possibilities
<./ (i.@! ([: +/ i (<"1@[ { ])~ 2 ]\ A.)"0 _ i.) #i
```

-- contributed by Henry Rich

### Part 2

```NB. Same, but find longest path
>./ (i.@! ([: +/ i (<"1@[ { ])~ 2 ]\ A.)"0 _ i.) #i
```

-- contributed by Henry Rich

## Problem 10 (Look And Say)

### Part 1

```NB. The personal input
i =. '1113122113'
NB. Convert to integer; create mask where new value begins;
NB. Create (count,value) for each run of values;
NB. Run them together to end turn.  Take 40 turns, get size of result
# ,@((# , {.);.1~ (~: |.!.0))^:40 "."0 i
```

-- contributed by Henry Rich

### Part 2

Like part 1, but change the 40 to 50.

A good solution should be cleverer than simply incrementing through all possibilities, lest the input have a high-order 'o', 'i', or 'l' that would require many cycles.

### Part 1

```LC =: 'abcdefghijklmnopqrstuvwxyz'
i =: wd 'clippaste'
NB. Define the 3 conditions
hasoil =: (+./@:e.)&(LC i. 'oil')  NB. no o i l
straight =: [: +./ 3 (}:-:}.)\ (- (i.@#))
twopair =: 1 < 1 (i: - i.)~ 2 =/\ ]
NB. Increment, but skip over unallowed values
inc =: ]&.((8#26)&#.) @: (+    [: 1&((_1)})^:(0 = *./) (e.&(LC i. 'oil')))
smoutput npw =. inc^:(hasoil +. straight *: twopair)^:_@inc &.(LC&i.) i
```

-- contributed by Henry Rich

On account of the E. bug I used c patterned after what would have been the j program. This code used the trick noted in the introduction.

```/*
Let this be the file c.c .
adventofcode.com/day/11 tests and solution given by linux command
a=./c && make \$a && \$a hijklmmn abbceffg abbcegjk abcdefgh abcdffaa ghijklmn ghjaabcc cqjxjnds
*/

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

typedef unsigned char V[8];

/*
return the index of the first character oil, or -1 if not present
*/
int lionize(V v) {
int i;
for (i = 0; i < 8; ++i)
if ((('o'-'a') == v[i]) || (('i'-'a') == v[i]) || (('l'-'a') == v[i]))
return i;
return -1;
}

/*
Passwords must include one increasing straight of at least three letters,
like abc, bcd, cde, and so on, up to xyz. They cannot skip letters;
abd doesn\'t count;
return true iff the string has a straight.
*/
int straight(V v) {
int i;
for (i = 1; i < 7; ++i)
if ((v[i+2] == v[i]+2) && (v[i+1] == v[i]+1))
return 1;
return 0;
}

/*
Passwords may not contain the letters i, o, or l,
as these letters can be mistaken for other characters and are therefore confusing;
return 1 if the string does not contain oil.
*/
int lion(V v) {
return lionize(v) == -1;
}

/*
Passwords must contain at least two pairs of letters, like aa, bb, or zz.
return 1 iff the string meets this spec
*/
int pairs(V v) {
int i, j = 0;
for (i = 0; i < 5; ++i)
if (v[i] == v[i+1]) {
j = 1;
break;
}
if (!j)
return 0;
for (i += 2; i < 7; ++i)
if (v[i] == v[i+1])
return 1;
return 0;
}

/*
return true iff string ok
*/
int valid(V v) {
return lion(v) && straight(v) && pairs(v);
}

void inc(V v) {
int i, field = lionize(v);
if (field < 0)
field = 7;
++v[field];
for (i = field + 1; i < 8; ++i)
v[i] = 0;
for (i = field; 0 < i; --i)
if (25 < v[i])
v[i] = 0, ++v[i-1];
if (25 < v[i])
v[i] = 0;
}

void a2v(char*pc, V v) {
int i;
for (i = 0; *pc && (i < 8); ++i)
v[i] = *pc++ - 'a';
for (; i < 8; ++i)
v[i] = 0;
}

void v2a(V v, char pc[8]) {
int i;
for (i = 0; i < 8; ++i)
pc[i] = v[i] + 'a';
}

void next(V v) {
while (! valid(v))
inc(v);
}

/*
display several passwords starting at the program argument.
use: \$ a.out cqjxjnds
*/
int main(int ac,char*av[]) {
int i;
char a[8];
V v;
while (++av , --ac) {
a2v(*av, v);
printf("%s %d ", *av, valid(v));
for (i = 0; i < 7; ++i)
inc(v), next(v), v2a(v, a), printf(" %.8s",a);
putchar('\n');
}
return 0;
}
```

-- contributed by David Lambert

### Part 2

```smoutput inc^:(hasoil +. straight *: twopair)^:_@inc &.(LC&i.) npw
```

-- contributed by Henry Rich

## Problem 12 (JSON Parsing)

### Part 1

```NB. Read input, convert to J words
i =: <@;:;._2 iraw =. wd 'clippaste'
NB. ending with a number, which joins the '-' to the value; then sum the results
+/ (0&".@;;.2~ ~:&(<,'-')) (#~ '-0123456789' e.~ {.@>) ;i
```

-- contributed by Henry Rich

### Part 2

```NB. Find the (start,end) of {} enclosing the location of each :"red"
NB. Convert start,end to start,end+1 for each block
redblocks =: 0 1 +"1 (I. ':"red"' E. iraw) mep iraw;'{}'
NB. Discard red strings that are included in other red strings
NB. Sort strings into order of start, and discard ones that end before some
NB. previous string
culledred =: (#~   {."1 >: |.!.0@:(>./\)@:({:"1)) /:~ redblocks
NB. Discard the red strings from the input
culledi =: (_2 ,.@:(-~/\)\ 0 , (,culledred) , #iraw) ;@:(<;.0) iraw
NB. Calculate the requested result, as for part 1
+/ (0&".@;;.2~ ~:&(<,'-')) (#~ '-0123456789' e.~ {.@>) ;: culledi
```

This program uses the verb mep defined here. -- contributed by Henry Rich

## Problem 13 (Cyclic Permutations)

### Part 1

```NB. Read in data, keeping names & happiness
nms =: ~. {."1 nngv =: (0 _1 2 3&{)@;:;._2 '.' -.~ wd 'clippaste'
NB. Extract happiness
vals =: (-@]^:('l'={.@[)  0&".)&>/"1 (_2) {."1 nngv
NB. Create array of affinities.  Make it symmetric
i =: (+ |:) vals (<"1 nms i. 2 {."1 nngv)} (2##nms) \$ 0
NB. Enumerate all possible orders, add up the affinities for each, take largest
maxhap =: >./ (i.@! ([: +/ i (<"1@[ { ])~ [: (,. 1&|.) A.)"0 _ i.) #i
```

-- contributed by Henry Rich

### Part 2

```NB. Adding a dummy is equivalent to not closing the ring
maxhap2 =: >./ (i.@! ([: +/ i (<"1@[ { ])~ 2 ]\ A.)"0 _ i.) #i```

</pre> -- contributed by Henry Rich

## Problem 14 (Reindeer Speeds)

### Part 1

```NB. Read in data, convert to numeric.  Result is table where each row
NB. has (speed),(flying time),(resting time)
sfr =: 0&".@> sfr (3 8 16&{)@;:;._2 wd 'clippaste'
NB. Calculate distances.  Convert each fly,rest to (#full cycles),(remainder)
NB. Then clamp the remainder to the flying time, convert to time flown;
NB. then multiply by speed.
>./ (0&{ * (_,1&{) ([ #. <.) 2503 #:~ (0,+/@(1 2&{)))"1 sfr
```

-- contributed by Henry Rich

### Part 2

```NB. Totally rewritten. Create table of distance flown for each time-interval;
NB. create running total; assign points to winners for each interval; add and
NB. take the largest
>./ +/"1 (="1 >./) +/\"1 (2503 \$ *`(1 0 #~ ,)/)"1 sfr
```

-- contributed by Henry Rich

### Part 1

For the first problem I was worried that the search space was too large for an exhaustive search, so I implemented a greedy algorithm to look for a local maximum. The algorithm starts with the best point from a number of random ones, and then searches a region around the local maximum to see if improvement is possible. As it turned out, the final search was not required.

```NB. Read in data, convert to numeric.  Remove multiple LFs
i =: <@;:;._2 iraw =: ((#~ -.) (LF,LF)&E.) wd 'clippaste'
ing =: |: }:"1 nums =: (0&".@;;.2~ ~:&(<,'-'))@(#~ '-0123456789' e.~ {.@>)@> i

NB. Part 1.  Discrete optimization.
NB. Score a combination.  x is matrix, y is combination
NB. Illegal combinations (first calculation) get negative score
score =: ((0 > <./@]) _1:^:[ [: */ 0 >. +/ . *)"2 1

NB.  List of possible moves to neighboring point, plus a first line for 'no move'
neighbors =: 0 , (#~  (0 = +/"1) *. (2 = +/@:|"1)) _1 0 1 {~"1 (#: i.@:(*/)) 3 3 3 3

NB. Moves in a region around a point.
NB. The first line is the 0 line, for stability when we are at the maximum
nregion =: (#~  (0 = +/"1)) 0 5 _5 4 _4 3 _3 2 _2 1 _1 {~"1 (#: i.@:(*/)) 11 11 11 11

NB. Get max score on matrix y.  Verb u is the scoring verb.
NB. Not guaranteed.  Uses greedy algorithm plus search
maxscore =: 1 : 0
NB. Deal random feasible starting points, get highest score
startpt =: ({~ (i. >./)@:(y&u)) (,.   100 - +/"1) 1000 3 ?@\$ 33
assert. 0 < y u startpt

whilst. greedybest -.@-: startpt do.
NB. Greedy algorithm to find largest score
greedybest =: ({~ (i. >./)@:(y&u))@:(neighbors&(+"1))^:_ startpt

NB. Search in the region around the maximum to see if score can be improved
startpt =: ({~ (i. >./)@:(y&u))@:(nregion&(+"1)) greedybest
end.
y u startpt
)
score maxscore ing
```

-- contributed by Henry Rich

### Part 2

The method of part 1 is not applicable because the feasible solutions are sparse. But I realized that the search space is not too large for exhaustive search after all.

```NB. Part 2.  Total rewrite.  Enumerate all possible partitions, find ones
NB. with correct calories, choose largest score
allparts =: 2 -~/\"1 (0) ,. 100 ,.~ (#~ (*./@:>: |.!.0)"1) (#: i.@:(*/)) 101 101 101
NB. Cull to correct calories
cal500 =: (#~  500 = ({:"1 nums) +/@:*"1 ]) allparts
NB. Find best score
>./ ing score cal500
```

-- contributed by Henry Rich

## Problem 16 (Database Search)

### Part 1

```NB. Read the search data: take lines; convert to words; convert numeric to numbers
clue =: ([^:(__ e. ]) __&".)&.>@;:;._2 wd 'clippaste'
NB. Extract names and values
names =: {."1 clue
clueval =: 1 {::"1 clue
NB. Get list of boxes for each aunt, each containing a list of att:value
db =: <@:(2&}.)@(([^:(__ e. ]) __&".)&.>@;:);._2 ',' -.~ (#~ [: -. (LF,LF)&E.) wd'clippaste'
NB. Create list of values for each aunt, using _ for missing values
dbflat =: (names (1&{::"1@])`(i. {."1)`(_"0@[)} _2&(]\))@> db
NB. Find lines that contain at least as much in a given category as was found in the search
I. dbflat ([: *./ (_ ~: [) # =)"1 clueval
```

-- contributed by Henry Rich

### Part 2

```NB. Replace clueval with range, for each value from search
rclueval =: 2 #"0 clueval
NB. Change the datatypes called for in the problem
rcv =: (names i. ;:'cats: trees:') (1 _ +"1 {)`([)`]} rclueval
rcv =: (names i. ;:'pomeranians: goldfish:') (__ _1 +"1 {)`([)`]} rcv
NB. Test for within range
I. dbflat ([: *./ (_ ~: [) # ((>: {.) *. (<: {:))"_1)"1 2 rcv
```

-- contributed by Henry Rich

## Problem 17 (Integer Knapsack)

This problem could be solved by exhaustive search, but it can be solved quicker as an instance of the Integer Knapsack Problem.

### Part 1

```NB. Read in data, convert to list
i =: ".;._2 (#~ (LF,LF) -.@:E. ]) wd 'clippaste'
# solutions =: i iknapsack 150 2
```

This program uses the verb iknapsack defined here. -- contributed by Henry Rich

### Part 2

```(+/@:= <./) +/"1 solutions
```

-- contributed by Henry Rich

## Problem 18 (Game Of Life)

### Part 1

```NB. Read in data, convert to Boolean table
i =: '.#'&i.;._2 (#~ (LF,LF) -.@:E. ]) wd 'clippaste'

NB. Game Of Life - one step
NB. The next value, given (value in middle),(total of 9 values in 3x3)
lifeprog =: 2 10 \$ 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
NB. Expand board by 1 empty all around, then take next value for each 3x3
life =: (_2 ]\ 1 1 3 3) (lifeprog {~ ([: < (<1 1)&{ , +/@:,));._3 (0)&([ , [ ,~ [ ,. [ ,.~ ])

NB. Run 100 steps
+/@:, life^:100 i
```

-- contributed by Henry Rich

Untestable on my system: we can animate the frames using

```NB. i =: '.#'&i.;._2 (#~ (LF,LF) -.@:E. ]) wd 'clippaste' NB. this is the untestable sentence
FRAMES =: life^:(<101) i NB. hence I'm guessing that my frames are your frames.
VISIBLE_jviewmat_=:0

(' '&=`(,:&'0')}(":,.i.101))([:viewmat;~)"_1 FRAMES

NB. using imagemagick animate program, for example on unix
NB. pushd ~/j64-804-user/temp
NB. animate ???.png
NB. popd
```

-- contributed by David Lambert

### Part 2

```<cornerson =: 1&((<;~0 _1)})
+/@:, cornerson@life^:100 cornerson i
```

-- contributed by Henry Rich

## Problem 19 (String Replacement)

### Part 1

```NB. Read in data, convert to table of (pattern),(replacement)
repls =: ' => '&(taketo ; takeafter);._2 (#~ (LF,LF) -.@:E. ]) wd 'clippaste'
NB. Here is the target molecule
molecule =: 'CRnCaSiRnBSiRnFArTiBPTiTiBFArPBCaSiThSiRnTiBPBPMgArCaSiRnTiMgArCaSiThCaSiRnFArRnSiRnFArTiTiBFArCaCaSiRnSiThCaCaSiRnMgArFYSiRnFYCaFArSiThCaSiThPBPTiMgArCaPRnSiAlArPBCaCaSiRnFYSiThCaRnFArArCaCaSiRnPBSiRnFArMgYCaCaCaCaSiThCaCaSiAlArCaCaSiRnPBSiAlArBCaCaCaCaSiThCaPBSiThPBPBCaSiRnFYFArSiThCaSiRnFArBCaCaSiRnFYFArSiThCaPBSiThCaSiRnPMgArRnFArPTiBCaPRnFArCaCaCaCaSiRnCaCaSiRnFYFArFArBCaSiThFArThSiThSiRnTiRnPMgArFArCaSiThCaPBCaSiRnBFArCaCaPRnCaCaPMgArSiRnFYFArCaSiThRnPBPMgAr'

NB. The only way to get a duplication is for two patterns a => b and c => d to be such
NB. that ad = bc.  In that case the two replacements will produce the same result and get
NB. a total one too high.  So we find all the strings ad that qualify.
NB. Subtle point: if a string is replaced by itself, it will count as a 'change' each time;
NB. but it should count only once.  Since this doesn't seem to happen in the test input, we ignore the case
NB. (solution would be to add a pattern '';'' , which would remove ALL the self-replacements, and then
NB. add 1 if there is any self-replacement)
doublecounts =: a: -.~ , <@((-:&;/)@(,. |.) # ;@,&{.)"1/~ repls
NB. To count single replacements, take the number of replacement points minus the number of duplication points
-/ (({."1 repls) ,&< doublecounts) +/@:((+/@:E.)&>)&> <<molecule
```

-- contributed by Henry Rich

### Part 2

I spent hours thinking about part 2 before coding anything. Finally I decided that it would be unfeasible to try to construct the steps involved in synthesizing the molecule, owing to the amount of backtracking that might be required. Then I noticed the regularity of the production rules. Strictly speaking this program does not find out how many substitutions are needed, but rather how many would be needed if the target is reachable.

```NB. Every production increases the length by exactly 1, except for ones producing Rn/Ar, which add 3,
NB. and those including Y, which add 2 for each Y.  Thus the number of steps is the length of the
NB. input, minus one for each Ar and Rn, minus 2 for each Y, minus 1 since we start with a single
NB. symbol.
UC =: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
_1 + (+/@:e.&UC - 'Ar'&(+/@:E.) + 'Rn'&(+/@:E.) + [: +: 'Y'&(+/@:E.)) molecule
```

-- contributed by Henry Rich

```NB. The main approach for this deconstruction of the given "molecule"
NB.     (just to see if it could be done)
NB.     was to isolate first all the "xxRn...Ar" strings and work
NB.     on each in turn. Because those strings are often embedded
NB.     in other "xxRn...Ar" strings, those embeddings had to be
NB.     identified.
NB. The verb "depth" used here was taken from
NB.     http://code.jsoftware.com/wiki/Essays/Parentheses_Matching
NB. The "depth" levels are constructed by treating each xxRn...Ar
NB.     string as if they are parenthesis pairs as suggested by the
NB.     alignment of the next two lines.
NB.         xxRn....Ar
NB.         xx(n....A)

NB.   Warning, this approach is quite brittle and does not work for all cases, such as 'HOHOHO' in the example.
NB.   However, a "solution" for the 'HOHOHO' example is explored far below.

molecule =: 'CRnCaCaCaSiRnBPTiMgArSiRnSiRnMgArSiRnCaFArTiTiBSiThFYCaFArCaCaSiThCaPBSiThSiThCaCaPTiRnPBSiThRnFArArCaCaSiThCaSiThSiRnMgArCaPTiBPRnFArSiThCaSiRnFArBCaSiRnCaPRnFArPMgYCaFArCaPTiTiTiBPBSiThCaPTiBPBSiRnFArBPBSiRnCaFArBPRnSiRnFArRnSiRnBFArCaFArCaCaCaSiThSiThCaCaPBPTiTiRnFArCaPTiBSiAlArPBCaCaCaCaCaSiRnMgArCaSiThFArThCaSiThCaSiRnCaFYCaSiRnFYFArFArCaSiRnFYFArCaSiRnBPMgArSiThPRnFArCaSiRnFArTiRnSiRnFYFArCaSiRnBFArCaSiRnTiMgArSiThCaSiThCaFArPRnFArSiRnFArTiTiTiTiBCaCaSiRnCaCaFYFArSiThCaPTiBPTiBCaSiThSiRnMgArCaF'

r =: 0 3&{@;: ;._2] 0 : 0
Al => ThF
Al => ThRnFAr
B => BCa
B => TiB
B => TiRnFAr
Ca => CaCa
Ca => PB
Ca => PRnFAr
Ca => SiRnFYFAr
Ca => SiRnMgAr
Ca => SiTh
F => CaF
F => PMg
F => SiAl
H => CRnAlAr
H => CRnFYFYFAr
H => CRnFYMgAr
H => CRnMgYFAr
H => HCa
H => NRnFYFAr
H => NRnMgAr
H => NTh
H => OB
H => ORnFAr
Mg => BF
Mg => TiMg
N => CRnFAr
N => HSi
O => CRnFYFAr
O => CRnMgAr
O => HP
O => NRnFAr
O => OTi
P => CaP
P => PTi
P => SiRnFAr
Si => CaSi
Th => ThCa
Ti => BP
Ti => TiTi
e => HF
e => NAl
e => OMg
)

NB. As an example, imagine that the string "SiRnBPTiMgAr" needs
NB.    to be deconstructed because it has been isolated as part
NB.    of a "depth" analysis.
NB.    "snip" is initially the part between Rn and Ar: BPTiMg
NB.    and  the verb "back" attacks "snip" (backward) from
NB.    right to left, always attempting to find a pattern to
NB.    substitute for the rightmost pair of elements in "snip".
NB.       snip       is BPTiMg  (from y in "back")
NB.       tailofsnip is Mg      (using findtail)
NB.       pretail    is BPTi    (using pretailof)
NB.    Then, using findtail on pretail to get Ti,
NB.       the list of patterns is i.'d to find TiMg
NB.       in the if. control.
NB.    Because Mg=>TiMg is found in r, Mg becomes the tail of
NB.       "snip" and so on.
NB.       snip       is BPMg    (from successful if.)
NB.       tailofsnip is Mg      (using findtail)
NB.       pretail    is BP      (using pretailof)
NB.    If no pattern for TiMg had been found in r in the if., the
NB.       else. clause would have prepended TiMg to "undone"
NB.       and saved "undone" until the remaining snip was
NB.       completely reduced.
NB.    Eventually the processed and reduced "snip" and any "undone"
NB.       is returned to its calling verb, "RnAr"

UC =: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
cod =: (UC e.~])<;.1  ]       NB. codify element names in y into boxes
num =: UC +/@e.~ ]            NB. tally element names in y
findtail =: ] }.~ [: i:&1 UC e.~ ]  NB. finds rightmost element of y
findhead =: 2;@{.cod                NB. finds leftmost  2 elements of y
pretailof =: -@#@[}.]         NB. drops off tail from y (like }:)
rtake =: ([,' ',])&>/@{&r     NB. get y'th pattern from r

NB.     http://code.jsoftware.com/wiki/Essays/Parentheses_Matching
depth =: [: +/\ =/\@(''''&~:) * 1 _1 0 {~ '()' i. ]
NB. Verbs "lp" and "rp" place ( and ) in the molecule's string for "depth"
lp =: ('('"_)`( I.@E.)`]}     NB. left parenthesis replaces each R in Rn
rp =: (')'"_)`( >:@I.@E.)`]}  NB. right parenthesis replaces each r in Ar
decon =. verb define          NB. "decon molecule" to execute this script *******
max =. >./depth'Ar' rp 'Rn' lp y
max decon y
:
Count =: 0     NB. Count is the only global noun
level =. x
whole =. y
max =. >./depth'Ar' rp 'Rn' lp y
assert. level <: max
NB. level 0 is treated differently from levels>0
while. level> 0 do.
NB. while the current depth (ie, state) is >: level
while.  level <: state =. >./depth'Ar' rp 'Rn' lp whole  do.
whole =. state process whole   NB. this line calls the verb "process"
smoutput (1&":@([:depth'Ar' rp 'Rn' lp]);&(_25]\])])whole
end.
level=.level-1
end.
back whole,' _2'     NB. this is level 0
Count
)

NB. deconstruct levels > 0
level =. x
whole =. y
ffind =. level find whole
smoutput 'position: ',p =. ":-~/}:ffind
main =. whole{~(([+i.@])/)}.ffind
t =. ((-{.ffind){.(1{ffind){. whole)
smoutput 'process: ',(":level),' ',t,main
NB. right arg of "RnAr" is a space delimited pair of strings
NB.   first string is the elements to be deconstructed,
NB.   second string is start position
new =. ({.~i.&' ')t RnAr ;:(_2}.2}.main),' ',p
rot =.  (-~/}:ffind)&|.
drop =. (#t,main)&}.
append =. new&,
(append&drop)&.rot whole
)

NB. called by "process" for each xxRn..Ar snippet
xx =. x  NB. xx in xxRn..Ar (1 or 2 letters)
'snip position' =. y
'reduce position' =. ;:back snip,' ',":(".position)+#xx
p =. ". position
o =. #xx
t =. ({:|:r) i. < xx,'Rn',reduce,'Ar'
smoutput 'subst: ',(rtake t),' ',": p-o
Count =: Count +  1
(>t{{.|:r),' ',>:&.".":p+o+2
)

NB. called by "RnAr" to deconstruct elements between Rn and Ar
undone =. i. 0
'snip position'=. ;:y
p =. ". position
count =. 0
while. #snip,undone do.
snip =. snip,undone
undone =. i. 0
while. snip >&num tailofsnip=. findtail snip do.
pretail =. tailofsnip pretailof snip
NB. determine if the 2 rightmost elements can be substitued for
NB.     by comparing the result of i. with the tally of r
NB. if so, make the substitution, otherwise prepend the 2
NB.     elements to the list "undone"
if. (#r)>t =. ({:|:r) i. (<(s=.tailofsnip),~findtail pretail) do.
snip =. (snip}.~-#s,findtail pretail), >t{{.|:r
smoutput 'subst: ',(rtake t),' ',":p+2+(-count+2+#undone)#@;@}. cod >{.;:y
count =. count + 1
else.
smoutput 'undone: ',undone =. undone,~u=.tailofsnip,~findtail pretail
snip =. snip}.~-#u
end.
end.
break.
end.
Count =: Count +  count
snip,undone,' ',position
)

NB. finds first left paren at level x in y
NB. resulting triple of integers is
NB.    the number of characters before the Rn,
NB.    the starting index in y of the R,
NB.    the length of the string Rn...Ar in y
level =. x
whole =. y
ind =. ([:depth'Ar' rp 'Rn' lp]) whole
start =. level i.~ ind
length =. >: 1 i.~ level~:start}.ind
pr =.# findtail start{.whole
pr,start,length
)

NB. At level 0 in "depth", no  "xxRn...Ar" strings remain and a
NB.    different direction of parsing seemed to work, so instead
NB.    of the strategy of using the verbs "RnAr" and "back", which
NB.    are used for higher levels, only the verb "back"
NB.    was used for level 0.

Note 'Herein are a few specimen steps, annotated slightly'
(1&":@([:depth'Ar' rp 'Rn' lp]);&(_25]\])])molecule
+-------------------------+-------------------------+
|0111111111122222222211122|CRnCaCaCaSiRnBPTiMgArSiRn|
|2233333222333333222222222|SiRnMgArSiRnCaFArTiTiBSiT|
|2222222111111111111111111|hFYCaFArCaCaSiThCaPBSiThS|
|1111111111222222223333221|iThCaCaPTiRnPBSiThRnFArAr|
|1111111111111111222221111|CaCaSiThCaSiThSiRnMgArCaP|
|1111222211111111122221111|TiBPRnFArSiThCaSiRnFArBCa|
|1122222333322222222211111|SiRnCaPRnFArPMgYCaFArCaPT|
|1111111111111111111111222|iTiTiBPBSiThCaPTiBPBSiRnF|
|2111111222222111222233332|ArBPBSiRnCaFArBPRnSiRnFAr|
|3333444443333322222222222|RnSiRnBFArCaFArCaCaCaSiTh|
|2222222222222223333222222|SiThCaCaPBPTiTiRnFArCaPTi|
|2222221111111111111112222|BSiAlArPBCaCaCaCaCaSiRnMg|
|2111111111000000000000011|ArCaSiThFArThCaSiThCaSiRn|
|1111111122222211100000111|CaFYCaSiRnFYFArFArCaSiRnF|
|1110000011111110000001111|YFArCaSiRnBPMgArSiThPRnFA|
|0000011110001111222222111|rCaSiRnFArTiRnSiRnFYFArCa|
|1122222111112222222111111|SiRnBFArCaSiRnTiMgArSiThC|
|1111111110011110001111000|aSiThCaFArPRnFArSiRnFArTi|
|0000000000000111111111100|TiTiTiBCaCaSiRnCaCaFYFArS|
|0000000000000000000001111|iThCaPTiBPTiBCaSiThSiRnMg|
|10000                    |ArCaF                    |
+-------------------------+-------------------------+
NB. look at above to understand these results.
decon molecule         NB. start the process
position: 227             NB. index 227 in each box
process: 4 SiRnBFAr       NB. level 4, at 227, work on SiRnBFAr
subst: Mg BF 231          NB. at 231, replace using Mg>BF
subst: Ca SiRnMgAr 227    NB. at 227, replace using Ca>SiRnMgAr
+-------------------------+-------------------------+
|0111111111122222222211122|CRnCaCaCaSiRnBPTiMgArSiRn|
|2233333222333333222222222|SiRnMgArSiRnCaFArTiTiBSiT|
|2222222111111111111111111|hFYCaFArCaCaSiThCaPBSiThS|
|1111111111222222223333221|iThCaCaPTiRnPBSiThRnFArAr|
|1111111111111111222221111|CaCaSiThCaSiThSiRnMgArCaP|
|1111222211111111122221111|TiBPRnFArSiThCaSiRnFArBCa|
|1122222333322222222211111|SiRnCaPRnFArPMgYCaFArCaPT|
|1111111111111111111111222|iTiTiBPBSiThCaPTiBPBSiRnF|
|2111111222222111222233332|ArBPBSiRnCaFArBPRnSiRnFAr|
|3333333322222222222222222|RnCaCaFArCaCaCaSiThSiThCa|
|2222222223333222222222222|CaPBPTiTiRnFArCaPTiBSiAlA|
|1111111111111112222211111|rPBCaCaCaCaCaSiRnMgArCaSi|
|1111000000000000011111111|ThFArThCaSiThCaSiRnCaFYCa|
|1122222211100000111111000|SiRnFYFArFArCaSiRnFYFArCa|
|0011111110000001111000001|SiRnBPMgArSiThPRnFArCaSiR|
|1110001111222222111112222|nFArTiRnSiRnFYFArCaSiRnBF|
|2111112222222111111111111|ArCaSiRnTiMgArSiThCaSiThC|
|1110011110001111000000000|aFArPRnFArSiRnFArTiTiTiTi|
|0000000111111111100000000|BCaCaSiRnCaCaFYFArSiThCaP|
|000000000000000111110000 |TiBPTiBCaSiThSiRnMgArCaF |
+-------------------------+-------------------------+
NB. look at above to understand these results.
position: 25             NB. index 25 in each box
process: 3 SiRnMgAr      NB. level 3, at 25, work on SiMgAr
subst: Ca SiRnMgAr 25    NB. at 25, replace using Ca>SiRnMgAr
+-------------------------+-------------------------+
|0111111111122222222211122|CRnCaCaCaSiRnBPTiMgArSiRn|
|2222333333222222222222222|CaSiRnCaFArTiTiBSiThFYCaF|
|2111111111111111111111111|ArCaCaSiThCaPBSiThSiThCaC|
|1111222222223333221111111|aPTiRnPBSiThRnFArArCaCaSi|
|1111111111222221111111122|ThCaSiThSiRnMgArCaPTiBPRn|
|2211111111122221111112222|FArSiThCaSiRnFArBCaSiRnCa|
|2333322222222211111111111|PRnFArPMgYCaFArCaPTiTiTiB|
|1111111111111111222211111|PBSiThCaPTiBPBSiRnFArBPBS|
|1222222111222233332333333|iRnCaFArBPRnSiRnFArRnCaCa|
|3322222222222222222222222|FArCaCaCaSiThSiThCaCaPBPT|
|2223333222222222222111111|iTiRnFArCaPTiBSiAlArPBCaC|
|1111111112222211111111100|aCaCaCaSiRnMgArCaSiThFArT|
|0000000000011111111112222|hCaSiThCaSiRnCaFYCaSiRnFY|
|2211100000111111000001111|FArFArCaSiRnFYFArCaSiRnBP|
|1110000001111000001111000|MgArSiThPRnFArCaSiRnFArTi|
|1111222222111112222211111|RnSiRnFYFArCaSiRnBFArCaSi|
|2222222111111111111111001|RnTiMgArSiThCaSiThCaFArPR|
|1110001111000000000000000|nFArSiRnFArTiTiTiTiBCaCaS|
|0111111111100000000000000|iRnCaCaFYFArSiThCaPTiBPTi|
|000000000111110000       |BCaSiThSiRnMgArCaF       |
+-------------------------+-------------------------+

NB. skip a lot before the next example.

+-------------------------+-------------------------+
|0111111111111222222222222|CRnCaCaCaCaSiRnCaPTiTiBSi|
|2222222211111111111111111|ThFYCaFArCaCaSiThCaPBSiTh|
|1111111111122222222211111|SiThCaCaPTiRnPBSiAlArCaCa|
|1111111111112222211111111|SiThCaSiThSiRnMgArCaPTiBP|
|2222111111111222211111122|RnFArSiThCaSiRnFArBCaSiRn|
|2222222222221111111111111|CaCaPMgYCaFArCaPTiTiTiBPB|
|1111111111111122221111112|SiThCaPTiBPBSiRnFArBPBSiR|
|2222211122222222222222222|nCaFArBPRnCaCaCaCaSiThSiT|
|2222222222222222222222111|hCaCaPBPTiBCaPTiBSiAlArPB|
|1111111111112222211111111|CaCaCaCaCaSiRnMgArCaSiThF|
|1000000000000011111111112|ArThCaSiThCaSiRnCaFYCaSiR|
|2222211100000111111000001|nFYFArFArCaSiRnFYFArCaSiR|
|1111110000001111000001111|nBPMgArSiThPRnFArCaSiRnFA|
|0001111222222111112222211|rTiRnSiRnFYFArCaSiRnBFArC|
|1112222222111111111111111|aSiRnTiMgArSiThCaSiThCaFA|
|0011110001111000000000000|rPRnFArSiRnFArTiTiTiTiBCa|
|0000111111111100000000000|CaSiRnCaCaFYFArSiThCaPTiB|
|000000000000111110000    |PTiBCaSiThSiRnMgArCaF    |
+-------------------------+-------------------------+
position: 11             NB. index 25 in each box
process: 2 SiRnCaPTiTiBSiThFYCaFAr       NB. level 2
subst: F CaF 29          NB. at 25, replace using F>CaF
undone: YF           NB. no pattern exists for YF
subst: F SiAl 23     NB. and so on  ...
subst: Mg BF 22
subst: Mg TiMg 20
subst: Mg TiMg 18
subst: F PMg 17
subst: F CaF 15
subst: Ca SiRnFYFAr 11

NB. Then we look at the very ending
NB. at which the number 212 is print out of
NB. "Count", the total number of steps.
NB.
NB.  Now read from the bottom to the top to see
NB.    how the molecule can be constructed.

subst: F CaF 9
subst: Al ThF 7
subst: F SiAl 5 NB. etc.
subst: F CaF 3  NB. The third replacement, for F at 3
subst: Al ThF 1  NB. The second replacement, for Al at 1
subst: e NAl 0   NB. The "seed" pattern, apparently.
212
)
```

Another small example explores possible generalizations, extensions.

```
NB. frwd processes the molecule from left to right (forward).
NB.    I found it can be used after a backward deconstruction
NB.    if the deconstruction is then incomplete.
NB.    Such a case occurs with the 'HOHOHO' example.
snip =. y
count =. 0
while. #snip do.
if. ''-: cod snip do. break. end.
smoutput 'subst: ',(rtake t),'  0'
count =. count + 1
end.
Count =: Count +  count
snip,' ',":count
)

r =: 0 3&{@;: ;._2] 0 : 0
e => H
e => O
H => HO
H => OH
O => HH
)
rtake =: ([,' ',])&>/@{&r     NB. get y'th pattern from r
Count =: 0
back 'HOHOHO _2'
subst: H HO 4
subst: H OH 3
subst: O HH 2
undone: OO
HOO _2
frwd 'HOO'
subst: H HO  0
subst: H HO  0
subst: e H  0
e 3
Count
6

```

-- contributed by Brian Schott

## Problem 20 (Package Delivery/Divisors)

### Part 1

The old sum-of-divisors problem, solvable without enumerating them.

```   goal =: 29000000
NB. The sum-of-divisors problem
(goal%10) >:@]^:(> >:@#.~/.~&.q:)^:_ (1)
```

-- contributed by Henry Rich

### Part 2

For the modified problem the easiest and fastest solution is to realize the set of divisors and throw out ones that are too small.

```   NB. use */\ rather than ^ to keep things integral
sumoflargedivisors =: ([: +/ <.@%&50@<: ((< # ]) >) [: ,@:(*/)&.>/ [: */\@:(1 , #~)&.>/ __&q:)
goal >:@]^:(>   11 * sumoflargedivisors)^:_ (2)
```

-- contributed by Henry Rich

## Problem 21 (RPG Simulation I)

### Part 1

```NB. Get problem input: weapons, armor, rings.  Make armor negative, so everything is units of attack
'w a r' =: 1 1 _1&*"1&.> (<@:((0 ". 12&}.)@>);._1~ ':'&e.@>) <;._2 (#~ (LF,LF) -.@:E. ]) ,&LF wd 'clippaste'
NB. Get personal input, from the problem
ourpoints =: 100
bosspoints =: 100
bossstats =: _2 8
NB. Enumerate choices.  Add a 0 line to a and r to allow buying nothing;
NB. Take r by pairs to allow buying 2 but remove principal diagonal to prevent
NB. buying the same thing twice
choices =: ,/@:(+"1/)&:>/ w;(0,a);(~. ,/ (-. =/~ i.>:#r) * +"1/~ 0,r)
NB. Find ones that win, choose smallest cost
<./ ((<:/"1)@:>.@:((bosspoints,ourpoints)&%"1)@:(1&>."1)@:(bossstats&+"1)@:(}."1) # {."1) choices
```

-- contributed by Henry Rich

### Part 2

```NB. Find ones that lose, choose largest cost
>./ ((>/"1)@:>.@:((bosspoints,ourpoints)&%"1)@:(1&>."1)@:(bossstats&+"1)@:(}."1) # {."1) choices
```

-- contributed by Henry Rich

## Problem 22 (RPG Simulation II)

### Part 1

```NB. Timer actions.  Each row gives the changes when the given effect is operational
timeractions =: ".;._2 (0 : 0)
0  0 0 0 _1 0 0   NB. Shield - just decr timer (armor happens in boss turn)
_3 0 0 0 0 _1 0  NB. Poison - hurt the boss
0 0 101 0 0 0 _1  NB. Recharge - add to our mana
)

NB. Spell actions.  Gives the change in state at the moment the spell is applied
spellactions =: ".;._2 (0 : 0)
0 0 _113 113 6 0 0 NB. Shield
0 0 _173 173 0 6 0 NB. Poison
0 0 _229 229 0 0 5 NB. Recharge
_4 0 _53 53 0 0 0 NB. Missile
_2 2 _73 73 0 0 0 NB. Drain
)

NB. Simulate the game
NB. y is (boss start points),(boss damage)
NB. x is hard flag
gamesim =: 3 : 0
0 gamesim y
:
'bosspoints bossdamage' =. y
minwincost =: 1e8
NB. A game state is
NB. (boss points),(our points),(our mana),(our spend so far),timers
NB. where timers are: shield,poison,recharge
states =. ,: bosspoints , 50 500 0  0 0 0
while. #states do.
NB. Player's turn:  first, the hard flag.  Take away 1 point and check for losers
if. x do.
states =. 0 _1 0 0 0 0 0 +"1 states
if. # loselines =. 0 I.@:>: 1 {"1 states do.
states =. (<<<loselines) { states
end.
end.

NB. process timers
states =. states + (* _3 {."1 states) +/ . * timeractions

NB. Find winning states (ones knocked out by the timers); update min cost
NB. Since we need the best win, rather than the path to it, just remember the
NB. cheapest win.  We will continue casting spells on it and eventually remove it
minwincost =. minwincost <. <./ (<(0 I.@:>: 0 {"1 states);3) { states

NB. Get mask of allowable spells for each state.  Missile and Drain always allowed
allowspells =. (0 = _3 {."1 states) ,"1 (1 1)

NB. Perform the spell
states =. (+/"1 allowspells) # states  NB. Replicate state for each spell
states =. states + allowspells ;@:(<@#/) spellactions

NB. Remove states with negative mana - they were illegal moves
if. # implines =. 0 I.@:> 2 {"1 states do.
states =. (<<<implines) { states
end.

NB. Find winning states (knocked out by the spell); update min cost
NB. copied from above
minwincost =. minwincost <. <./ (<(0 I.@:>: 0 {"1 states);3) { states

NB. Remove any high-cost states, which could have come from an improved win or
NB. increased expense
states =. (minwincost > 3 {"1 states) # states

NB. Boss's turn: save armor state before timers are processed
armorvalue =. 7 * * 4 {"1 states

NB. process timers
states =. states + (* _3 {."1 states) +/ . * timeractions

NB. Find winning states (knocked out by timers); update min cost
NB. copied from above
minwincost =. minwincost <. <./ (<(0 I.@:>: 0 {"1 states);3) { states

NB. Calculate result of boss's move
NB. The damage inflicted depends on our armor, which depends on the shield timer
ournewpoints =. (1 {"1 states) - 1 >. bossdamage - armorvalue
states =. ournewpoints (<a:;1)} states

NB. Remove losing states
if. # loselines =. 0 I.@:>: ournewpoints do.
states =. (<<<loselines) { states
end.

NB. Remove duplicate states, which there seem to be plenty of
states =. ~. states
end.
minwincost
)
gamesim bossinfo
```

-- contributed by Henry Rich

### Part 2

```1 gamesim bossinfo
```

-- contributed by Henry Rich

## Problem 23 (Microprocessor Simulation)

### Part 1

```NB. Machine simulator
NB. Machine state is (register a),(register b),(pc)

NB. Read input and convert to internal instruction form, which is
NB. an AR for each instruction

NB. Converters for each opcode
NB. Each creates an AR that operates on machstate to create a new machstate
hlf =: (3 : '{. (0 0 1 + (y}~ <.@-:@(y&{)))`0:')
tpl =: (3 : '{. (0 0 1 + (y}~ 3 * (y&{)))`0:')
inc =: (3 : '{. (0 0 1 + (y}~ 1 + (y&{)))`0:')
jmp =: (3 : '{. (2}~ y + (2&{))`0:')
jie =: (4 : '{. (2}~ (2&{ + (y,1) {~ 2 | x&{))`0:')/
jio =: (4 : '{. (2}~ (2&{ + (1,y) {~ 1 = x&{))`0:')/
'a b' =: 0 1  NB. register numbers

NB. Read & convert the program
program =: ".;._2  (#~ (LF,LF) -.@E. ]) wd 'clippaste'

NB. Simulator.  y is the program, x is the initial state (default 0 0 0)
NB. Initialize machine state, run instructions until we get an error fetching one
simprog =: 4 : 0
machstate =. x
while. do.
if. 0 1 -.@-: (0,#y) > pc =. 2 { machstate do. break. end.
machstate =. (pc{y)`:6 machstate
end.
machstate
)
0 0 0 simprog program
```

-- contributed by Henry Rich

### Part 2

```1 0 0 simprog program
```

-- contributed by Henry Rich

```    p2 =.    cut"1 '-_' rplc~"1 ',+' -.~"1 a2  =. > cutLF wdclippaste
```
```    maybenum =: 0&".^:(] -:&(, \$~ 1 -.~ \$) ":@:(0&".^:(2 = 3!:0)))
lr =: 3 : '5!:5 < y'
```
```    DO =:  ] + ".@:([: ;: inv [: ({. , 1&{ , lr@maybenum leaf@{: ) 2 0 1  { {~)
jmp =: ]
inc =:  3 : '1 [ (y) =: >: y~'
tpl =:  3 : '1 [ (y) =: 3 *  y~'
hlf =:  3 : '1 [ (y) =: -:  y~'
jio =:  4 : '(1 , x) {~ 1 =  y~'
jie =:  4 : '(x, 1) {~ 2 |  y~'
```
```    p2 DO^:( #@[ > ])^:(_) 0  [ b =: 0x [ a =: 1x
```

--Pascal Jasmin (talk) 18:25, 27 December 2015 (UTC)

## Problem 24 (Divide The Weights)

### Part 1

The Integer Knapsack Problem again.

```NB. Read in data, convert to list of package weights
i =: ".;._2 (#~ (LF,LF) -.@:E. ]) LF ,~ wd 'clippaste'

NB. Get all the ways to add up to 1/3 the weight
solutionmask =: i iknapsack 2 ,~ goal =: 3 %~ +/ i
NB. Cull to ones that have minimum # packages
NB. For each solution, see if the remaining packages can be split into 2 equal parts.
NB. Keep only solutions that can.
feasmin =: (((-. minsolutions) # i) iknapsack goal,0) # minsolutions
NB. Find minimum QE
<./ */"1 feasmin # i

```

This program uses the verb iknapsack defined here. -- contributed by Henry Rich

```   combT =: ([: ; ([ ; [: i.@>: -~) ((1 {:: [) ,.&.> [: ,&.>/\. >:&.>@:])^:(0 {:: [) (<i.1 0),~ (< i.0 0) \$~ -~)
] a =.". > cutLF wdclippaste   NB. input
s =. 3 %~ +/ a
/:~ */"1 f =. (#~ s = +/"1) a {~ 6 combT #a
```

--Pascal Jasmin (talk) 18:18, 27 December 2015 (UTC)

### Part 2

```NB. Utility adverb: apply u to successive items of y.  Returns item when (u item) returns nonzero
NB. Returns empty if no match
first =: 1 : 0
for_i. y do. if. u i do. i return. end. end.
0\$0
)
NB. Get the feasible solutions
solutionmask =: i iknapsack 1 ,~ goal =: 4 %~ +/ i
NB. Cull to ones that have minimum # packages
NB. Order on QE
ordsolutions =: (/: +/"1 ,. */@:(#&i)"1) minsolutions
NB. Utility verb: x is all solutions, y is one solution, result is table of solutions in x that
NB. do not have any overlap with y
nonoverlaps =: (-.@:((+./@:*.)"1) # [)
NB. Process the solutions in order of desirability.  Remembering that solutionmask knows ALL the
NB. solutions, we find all the possible solutions for the second group given the first group.  The
NB. question then is whether the remaining half of the weight can be split evenly.  If it can, we have
NB. a winner.
NB. The search is done stopping on the first match, to save unnecessary computation
*@#@((goal iknapsack 0 ,~ #&i) first)@(+."1  solutionmask&nonoverlaps) first ordsolutions```

-- contributed by Henry Rich

```   s =. 4 %~ +/ a  NB. part 2 sum target
/:~ */"1 f =. (#~ s = +/"1) a {~ 5 combT #a  NB. if f has no items, then try longer group.
```

--Pascal Jasmin (talk) 18:18, 27 December 2015 (UTC)

### Part 1

```(20151125) 33554393&|@* (252533) 33554393&|@^ <: row (] + 2 ! <:@+) col
```

-- contributed by Henry Rich

```for input 3019 column, 3010 row.

next =: 33554393 | 253533 * ]
next^:(3019 ([ + [: +/@i. 2-~ +)  3010) 20151125
```

--Pascal Jasmin (talk) 18:13, 27 December 2015 (UTC)