For part 1, I recalled that the L1-norm (or Manhattan distance) is minimized by
the median. Fortunately, the sample and input data are well-behaved, so a
no-frills version of median works fine.
I used the same brute force approach for part 2. I plotted the cost curve
against the horizontal positions, and it is convex. Some optimization routine
would probably work, but I didn't try any. J instantaneously returned the
brute-force solution on my aging iPad, so I didn't get fancy.
Mike
NB. input l1norm median input
l1norm =: +/@:|@:-
median =: [: ({~ -:@:#) /:~
NB. solve input
solve =: {{)m
cost =. -:@:(* >:)@:|@:-
<./ +/ y cost"0 1 i. >./ y
}}
--
Michael P. Manti
[email protected]
> On Dec 28, 2021, at 15:10, Jan-Pieter Jacobs <[email protected]>
> wrote:
> I took pretty much the same approach as Raul (i.e. bruteforce), but
> expressed it tacitly:
>
> NB. Day 07: Crab alignment
> NB. find position globally closest to all input numbers, each step being 1
> fuel unit
>
> i07=: ".}:freads'07.txt'
> irg=: <./ ([+i.@>:@-~) >./ NB. integer range spanning the range of
> list y
> t07=: 16,1,2,0,4,2,7,1,2,14 NB. test data part a
> a07=: [: (#~ (=<./)) ] +/@: |@:(-"0 1/) irg
>
> NB. b: similar, but each sucessive step is >:i. fuel units
> b07=: [: (#~ (=<./)) ] +/@:(|@:(-"0 1/) { ([: +/\ i.@>:@(>./))@]) irg
> (a07;b07)i07
>
> I hope it comes through without any interfering line-wrapping (irg, a07,
> b07 should all be single line verbs).
>
> On Tue, Dec 28, 2021, 05:46 Raul Miller <[email protected]> wrote:
>
>> https://adventofcode.com/2021/day/7
>>
>> Day 7's puzzle also had a comma separated list as its data, so again
>> no parsing routine was necessary:
>>
>> sample=: 16,1,2,0,4,2,7,1,2,14
>>
>> Here, you are being rescued from a whale by a bunch of crab submarines
>> -- each number represents the position of a crab submarine.
>>
>> The puzzle is to find the one position to move them all to which
>> requires the least movement. Or, in puzzle terms the least "fuel" --
>> one crab changing its position by one unit costs one fuel. To solve
>> the puzzle you need to report how much fuel this "least fuel" costs.
>>
>> My approach here was just plain brute force: checking every candidate
>> position:
>>
>> leastfuel=:{{
>> min=.<./y
>> max=.>./y
>> options=.min+i.1+max-min
>> fuel=. +/|y-/options
>> optimum=. min+(i.<./)fuel
>> optimum{fuel
>> }}
>>
>> For part 2, the fuel cost was not constant, but increased by one each
>> step. 1 step is still 1 fuel, two steps is 1+2 fuel, three steps is
>> 1+2+3 fuel. In other the sum was a triangular number: -:@(*>:)distance
>>
>> So, I threw that expression into my routine:
>>
>> crab=:{{
>> min=.<./y
>> max=.>./y
>> options=.min+i.1+max-min
>> fuel=. +/-:@(*>:)|y-/options
>> optimum=. min+(i.<./)fuel
>> optimum{fuel
>> }}
>>
>> I am sure that there's better ways of expressing this. That said,
>> plotting the fuel costs for each of the position options suggests that
>> brute force was the only viable approach here. If I am wrong about
>> that, I would love to hear an explanation.
>>
>> --
>> Raul
>> ----------------------------------------------------------------------
>> 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
