"short circuit" tacit evaluation.
Solve PE#4 starting with the palindromes inclusively between *:100 999
Note 'Introducing "short circuit" tacit evaluation'
(* is_solution)^:unsolved/
where is_solution and unsolved are Boolean verbs,
and unsolved is inexpensive.
I hope this is a new J idea.
Please read through to the end.
Where possible I use assertions to demonstrate and test.
)
NB. factoring is expensive.
factor=: [:*/"1&>[:,[:{[:<@(^ i.@:>:)/"1[:|:2&p:
NB. tally of and factors of 12
assert (6 ; 1 2 3 4 6 12) -: (# ; /:~)@:factor 12
digits =: 10&#.^:_1
assert (i._3) -: digits 210
is_palindrome =: (-: |.)@:digits f.
assert 0 1 1 -: is_palindrome&> 48 68886 3
Filter =: (#~`)(`:6)
assert 8 9 11 -: is_palindrome&> Filter (+ i.)8
NB. A is (a vector of) the palindromes from squared 100 to 999
NB. Slow! Probably due to is_palindrome operating atomically.
NB. However, the important point is the increasing order.
A=:100 is_palindrome&> Filter@:(<. + [: i. >. >:@:- <.)&*: 999
assert 10001 997799 -: ({.,{:) A NB. true by inspection
1798 = # A NB. potentially factor this tally. I cannot assert this.
has_3_digits =: 3 = #@digits
assert 1 0 -: has_3_digits&> 234 9923
NB. or 2 = [: <. 10 ^. ]
NB. or 100&<: *. <&1000
NB. or 3 = #@":
three_digit_factors =: [: has_3_digits&> Filter factor
assert 125 625 250 100 500 200 400 -: three_digit_factors *:100
final_test =: 1 e. ((% e. ]) three_digit_factors)
assert 1 0 -: final_test&> 10000 10001
NB. this is it!
906609 = (* final_test)@:[^:(0=])/A,0
Date: Sun, 08 Jun 2014 12:31:53 -0400
From: Henry Rich<[email protected]>
To:[email protected]
Subject: Re: [Jprogramming] Project Euler Question 4
Message-ID:<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Tacit variant:
break2=:1 :'(": 13!:8 (15"_))^:u"u :: (LF taketo }.@(13!:12)@(''''"_) )'
(-: |.)@("."0@":)"0 break2 \:~ ~. , */~ 100+i.900
Henry Rich
On 6/8/2014 12:05 PM, 'Pascal Jasmin' via Programming wrote:
>an optimization to short circuit on first true, while sorting them in order.
>
> break1 =: (1 : 'for_i. y do. if. u i do. i return. end. end.')
>
> (-: |.)@": break1 \:~ ~. , */~ 100+i.900
>906609
>
> timespacex '(-: |.)@": break1 \:~ ~. , */~ 100+i.900'
>0.0350227 3.56737e7
> timespacex ' >./ (#~ (-: |.)@":"0) , */~ 100+i. 900'
>0.26438 1.78811e7
>
>----- Original Message -----
>From: Roger Hui<[email protected]>
>To: Programming forum<[email protected]>
>Cc:
>Sent: Sunday, June 8, 2014 11:10:07 AM
>Subject: Re: [Jprogramming] Project Euler Question 4
>
>Or apply the phrase to 900+i.100 instead of to 100+i.900.
>
>
>
>
>
>On Sun, Jun 8, 2014 at 8:07 AM, Roger Hui<[email protected]> wrote:
>
>>Slightly shorter if the formatted results are not converted back into
>>numbers:
>>
>> >./ (#~ (-: |.)@("."0@":)"0) , */~ 100+i. 900
>>906609
>> >./ (#~ (-: |.)@":"0) , */~ 100+i. 900
>>906609
>>
>>A different and perhaps less brutish method is to start with 6-digit
>>palindromes and see which ones have two 3-digits factors.
>>
>>
>>
>>
>>On Sun, Jun 8, 2014 at 8:00 AM, Henry Rich<[email protected]> wrote:
>>
>>>Brute force seems right for this problem. You could write your solution
>>>as
>>>
>>> >./ (#~ (-: |.)@("."0@":)"0) , */~ 100+i. 900
>>>
>>>Henry Rich
>>>
>>>On 6/8/2014 10:46 AM, Jon Hough wrote:
>>>
>>>>I am pretty pleased that I completed Project Euler Q4.
>>>>Question:
>>>>
>>>>
>>>>A palindromic number reads the same both ways. The largest palindrome
>>>>made from the product of two 2-digit numbers is 9009 = 91 99.
>>>>
>>>>Find the largest palindrome made from the product of two 3-digit numbers.
>>>>
>>>>
>>>>https://projecteuler.net/problem=4
>>>>
>>>>
>>>>My solution:
>>>>
>>>>base =. "."0 ":
>>>>
>>>>NB. Tests if y value is palindrome.
>>>>is_palindrome =. (# =)@:(=|.)@:base
>>>>NB. multiply all 3 digit nums (100 ~ 999)
>>>>mult =: (* is_palindrome"0) @ (*/)
>>>>NB. Create list of 3 digit nums.
>>>>list =. 100+ i.900
>>>>
>>>>(>./)@:, list mult list
>>>>Although I'm glad got the answer, I'm wondering if it could be made
>>>>terser, or if there is a much terser way to solve it? I went for a brute
>>>>force approach.
>>>>For comparison here is a Haskell answer I found:
>>>>maximum[a*b|a<-[100..999],b<-[a..999],reverse(show(a*b))==show(a*b)]
>>>>Regards.
>>>>----------------------------------------------------------------------
>>>>For information about J forums seehttp://www.jsoftware.com/forums.htm
>>>>
>>>> ----------------------------------------------------------------------
>>>For information about J forums seehttp://www.jsoftware.com/forums.htm
>>>
>>
>>
>----------------------------------------------------------------------
>For information about J forums seehttp://www.jsoftware.com/forums.htm
>
>----------------------------------------------------------------------
>For information about J forums seehttp://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
