Was a lot of time for me too. Most of it guessing on insertion order. In the
end, taking the last match in the molecule on each iteration is what worked.
(Though it turns out that some other patterns work too)
Even harder to notice than your substitution pattern math is why reverse order
or simple patterns would be the right way. Longest match first seemed
intuitive, considering wording of finding the shortest path.
solution amendment,
to overcome the "last step" bug in my last post, just add a leading blank to
input.
(EliRI~ (_1 ,&<~ ( ((0 Y) ,&<~ 1 Y)"1 a7) {~ (i: >./)@:( ,@:>)@:(( {:@:({:"1) )
every)@:((1 {"1 a7) Eli"1 1 L:1 1 ])))^:195 a:, inb
┌┬─┐
││e│
└┴─┘
----- Original Message -----
From: Henry Rich <[email protected]>
To: [email protected]
Sent: Saturday, December 19, 2015 9:05 PM
Subject: Re: [Jprogramming] Advent 19
After an OBSCENE amount of thought, consumed by worries about
recursions, I found the easy solution to part 2.
The more I worked on part 2 the less I liked it, because in the end the
solution is in an analysis of the data rather than the algorithm. But I
was pleased with part 1.
Spoiler...
10
9
8
7
6
5
4
3
2
1
0
NB. Read in data, convert to table of (pattern),(replacement)
repls =: ' => '&(taketo ; takeafter);._2 (#~ (LF,LF) -.@:E. ]) wd
'clippaste'
molecule =:
'CRnCaSiRnBSiRnFArTiBPTiTiBFArPBCaSiThSiRnTiBPBPMgArCaSiRnTiMgArCaSiThCaSiRnFArRnSiRnFArTiTiBFArCaCaSiRnSiThCaCaSiRnMgArFYSiRnFYCaFArSiThCaSiThPBPTiMgArCaPRnSiAlArPBCaCaSiRnFYSiThCaRnFArArCaCaSiRnPBSiRnFArMgYCaCaCaCaSiThCaCaSiAlArCaCaSiRnPBSiAlArBCaCaCaCaSiThCaPBSiThPBPBCaSiRnFYFArSiThCaSiRnFArBCaCaSiRnFYFArSiThCaPBSiThCaSiRnPMgArRnFArPTiBCaPRnFArCaCaCaCaSiRnCaCaSiRnFYFArFArBCaSiThFArThSiThSiRnTiRnPMgArFArCaSiThCaPBCaSiRnBFArCaCaPRnCaCaPMgArSiRnFYFArCaSiThRnPBPMgAr'
NB. Part 1
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
NB. Part 2
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 more 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 - [: +/ 1 1 2 * (;:'Ar Rn Y') +/@:E.&>/ <) molecule
Henry Rich
On 12/19/2015 5:31 PM, 'Pascal Jasmin' via Programming wrote:
replying to other message as it uses definitions there,
a7 =. ((0 { ]) ,&< 1 Y)"1 (\: (# * 1 + 4 * +/@((;: 'Ar')&e.) + 2 * +/@((;: 'Ar Rn Y'
)&e.))@(1&{::"1 )) a2 =.(0 Y ; [: <@(isupper <;. 1 ] ) 1 Y )"1 a =. > cutLF wdclippaste ''
NB. just keys mostly useless sorting, and simpler a2 would have done, though (0 { ])
,&< 1 Y)"1 is probably needed.
inb =. (isupper <;. 1 ] ) {. in =. wdclippaste '' NB. molecule
(EliRI~ (_1 ,&<~ ( ((0 Y) ,&<~ 1 Y)"1 a7) {~ (i: >./)@:( ,@:>)@:(( {:@:({:"1) )
every)@:((1 {"1 a7) Eli"1 1 L:1 1 ])))^:193 inb
┌─┬──┬─┬──┬──┐
│C│Rn│F│Ar│Al│
└─┴──┴─┴──┴──┘
bug that won't pick up first match in line (first 4 chars map to N, and NAl
maps to e). So solution is 2 higher than 193 iteration count.
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: Programming Forum <[email protected]>
Sent: Saturday, December 19, 2015 12:38 PM
Subject: [Jprogramming] an E. based delete/replace function
haven't finished latest advent prob, but felt I needed a more flexible replace
function
Y =: (&{::)(@:])
X =: (&{::)(@:[)
M=:@:]
T=:(&{)(>@)
R =: (&}.) M
comments placed on following line to escape line breaks. blank lines are line
breaks if it messes up.
delitem =: ;@:((1 X {. ]) ; (0 X + 1 X) }. ]) NB. len idx :X str :Y
delitemR =: ;@:((1 X {. ]) (,~ <)~ 2 R~ (, <) (0 X + 1 X) }. ])
NB. len idx item list:X str :Y
Eli =: ((#M~ ;"0 0 I.@E.) ) NB. returns len idx of matches
EliR =: (]delitemR~"1 (1 R)~,~("1)0 X Eli])
NB. replace based on Eli. 2items :X Eli/E. arg:0X list compatible with y :1X
EliRI =: (]delitemR~"1 ([: 1 R 0 X) ,~("1 1) 1 X { (0; 0) X Eli]) :: ]
NB. replace select indexes of Eli. 2 items tree :x EilR args :0X arg to { (0
first, _1 last etc) :1X. index error makes no replacement.
The first delitem is not needed, as delitemR has an optional rest argument.
The first 2 right arguments to these functions is length, index
(2 1 ) delitemR 3 4,i.8 NB. no boxing needed if just deleting.
3 1 2 3 4 5 6 7
above is same result as delitem
The 3rd argument if provided, inserts that at the deletion point. This works either as a
boxed list of compatible type to y, or an unlimited amount of "Rest" boxes that
are each a compatible type. Replace item can be different size.
2 ;1 ;99 ;44 ) delitemR 3 4,i.8
3 99 44 1 2 3 4 5 6 7
(2 ;1 ;99 44 11 ) delitemR 3 4,i.8
3 99 44 11 1 2 3 4 5 6 7
(_80 ; _5; 'ABCD' ) delitemR a. NB. negative length and idx do something.
Other functions produce results compatible with the delitem,
E.length-index
3 4 Eli 3 4,i.8
┌─┬─┐
│2│0│
├─┼─┤
│2│5│
└─┴─┘
EliR replaces 0X with 1X, but unlike rplc~ returns one string for each act.
(3 4; 88 33 ) EliR 3 4,i.8
88 33 0 1 2 3 4 5 6 7
3 4 0 1 2 88 33 5 6 7
if just 1 replacement, still returns a list
61 }."1 ( 'ABCD' ;' XXFFGG' ) EliR a.
=>?@ XXFFGGEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde ....
t =. <;._1 ' C Rn Ca Si Rn B Si Rn F Ar Ti B P Ti Ti B F Ar P B Ca Si Th Si Rn
Ti'
deleting string of boxed sequence 'Rn F'
( (;: 'Rn F') ; '' ) EliR t
+-+--+--+--+--+-+--+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
|C|Rn|Ca|Si|Rn|B|Si|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|Rn|Ti|
+-+--+--+--+--+-+--+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
to replace, make 1 item of (list) compatible type (boxed to make 1 item)
( (;: 'Rn F') ; < ;: 'FFF Gg' ) EliR t
+-+--+--+--+--+-+--+---+--+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
|C|Rn|Ca|Si|Rn|B|Si|FFF|Gg|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|Rn|Ti|
+-+--+--+--+--+-+--+---+--+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
EliRI selects the indexes of E. matches to delete/replace. indexes are in {
format. The X argument becomes a tree of 2 items. the left branch is the same
arg as EliR.
consider these 4 matches (deletes)
( (;: 'Rn') ; '' ) EliR t
+-+--+--+--+--+--+--+--+--+--+--+-+--+--+--+-+--+--+-+--+--+--+--+--+--+
|C|Ca|Si|Rn|B |Si|Rn|F |Ar|Ti|B |P|Ti|Ti|B |F|Ar|P |B|Ca|Si|Th|Si|Rn|Ti|
+-+--+--+--+--+--+--+--+--+--+--+-+--+--+--+-+--+--+-+--+--+--+--+--+--+
|C|Rn|Ca|Si|B |Si|Rn|F |Ar|Ti|B |P|Ti|Ti|B |F|Ar|P |B|Ca|Si|Th|Si|Rn|Ti|
+-+--+--+--+--+--+--+--+--+--+--+-+--+--+--+-+--+--+-+--+--+--+--+--+--+
|C|Rn|Ca|Si|Rn|B |Si|F |Ar|Ti|B |P|Ti|Ti|B |F|Ar|P |B|Ca|Si|Th|Si|Rn|Ti|
+-+--+--+--+--+--+--+--+--+--+--+-+--+--+--+-+--+--+-+--+--+--+--+--+--+
|C|Rn|Ca|Si|Rn|B |Si|Rn|F |Ar|Ti|B|P |Ti|Ti|B|F |Ar|P|B |Ca|Si|Th|Si|Ti|
+-+--+--+--+--+--+--+--+--+--+--+-+--+--+--+-+--+--+-+--+--+--+--+--+--+
replaces just first (if only 1 index, then return has no leading 1 shape)
(0 ,&<~ (;: 'Rn') ; < ;: 'FFF Gg' ) EliRI t
+-+---+--+--+--+--+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
|C|FFF|Gg|Ca|Si|Rn|B|Si|Rn|F|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|Rn|Ti|
+-+---+--+--+--+--+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
replace 2nd and last (and reorder last replace first)
(_1 1 ,&<~ (;: 'Rn') ; < ;: 'FFF' ) EliRI t
+-+--+--+--+---+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+---+--+
|C|Rn|Ca|Si|Rn |B|Si|Rn|F|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|FFF|Ti|
+-+--+--+--+---+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+---+--+
|C|Rn|Ca|Si|FFF|B|Si|Rn|F|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|Rn |Ti|
+-+--+--+--+---+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+---+--+
fold left recursive replace but only up to 2 times
(0 ,&<~ (;: 'Rn') ; < ;: 'FFF' ) EliRI^:2 t
+-+---+--+--+---+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
|C|FFF|Ca|Si|FFF|B|Si|Rn|F|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|Rn|Ti|
+-+---+--+--+---+-+--+--+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+--+--+
fold right recursive replace all
(_1 ,&<~ (;: 'Rn') ; < ;: 'FFF' ) EliRI^:_ t
+-+---+--+--+---+-+--+---+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+---+--+
|C|FFF|Ca|Si|FFF|B|Si|FFF|F|Ar|Ti|B|P|Ti|Ti|B|F|Ar|P|B|Ca|Si|Th|Si|FFF|Ti|
+-+---+--+--+---+-+--+---+-+--+--+-+-+--+--+-+-+--+-+-+--+--+--+--+---+--+
this differs from rplc~ in that a recursive approach has potential to create a
new match on replaced text. infinite loop potential. use rplc if you want
rplc behaviour.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
