Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- :
- Discussion Forums
- :
- kdb+ and q
- :
- Re: Q For Problems - Episode 4

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Q For Problems - Episode 4

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.25 02:10 AM

Hi everyone,

Please check out episode 4 of the Q For Problems video series.

This covers problem 4 from the Project Euler problem set. Project Euler - Problem 4

The problem wants us to find the largest palindrome made from the product of two 3-digit numbers.

Hopefully you enjoy the new intro, outro and section transitions! 😊

Feel free to share your own solutions and ideas in the comments.

Thanks

9 REPLIES 9

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.26 02:45 AM

Having just posted about this problem at GitHub.com/qbists/studyq, really interesting to see your approach to it, and attention to performance.

Minor quibble: I’m told composing a sequence of unaries by terminating it with the Identity function is an ‘accidental’ of the parser. Instead use Apply At `@`

, which is supported syntax.

Faster to compare by first Tok-ing to integers? Ah ha! I’ll incorporate that and credit you! 👏

On the next episode of the ArrayCast the panel discusses the difference between using symbols and keywords. We have a nice example of that difference here!

The keyword `max`

conveys clearly that it returns the highest item, which is what we want. Job done?

Its symbolic form `|/`

however is clearly an iteration, which suggests something to think about. The problem asks for the *largest* palindrome. Sorting is fast. We can sort the candidates and start testing from the top; stop at the first hit. We don’t need to test every candidate. Speed-up is 100×.

It is a subtle but profound point: the virtue of a “notation as a tool of thought” is not that that it lets us stop thinking about iteration but that it helps us think about iteration more clearly. (All that said, it is still good q style to prefer the q keywords to their symbolic definitions – but watch out!)

The GitHub page discovers an elegant q form for finding in a list the last item that passes a test.

Your memory economy of tackling the problem in ranges works very well with this – but starting from the highest candidates.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.26 04:18 AM

`Minor quibble: I’m told composing a sequence of unaries by terminating it with the Identity function is an ‘accidental’ of the parser. Instead use Apply At ``@`

, which is supported syntax.

I picked up the use of the :: to create a composition from the FunQ book by Nick Psaris. In this book, Nick describes the :: as a better alternative to @ because

- :: is not visible in the function train:
`q)sqrt sum abs:: sqrtsumabs q)sqrt sum abs@ sqrtsum@[abs]`

- @ creates a composition which can accept only a single argument, where as :: does not have this limitation:
`q)add:{x+y} q)f:1-add@ q)f[1;2] 'rank q)f:1-add:: q)f[1;2] -2`

I think it was a "happy" accident that this works, but I guess it may not be a good idea to use if it was going to be removed from the language in the future.

Its symbolic form

`|/`

however is clearly an iteration, which suggests something to think about. The problem asks for thelargestpalindrome. Sorting is fast. We can sort the candidates and start testing from the top; stop at the first hit. We don’t need to test every candidate. Speed-up is 100×.

Interesting point. I guess this shows both a pro an con of using keywords.

Pro: Development is faster and code is often simpler and easy to read.

Con: The ease of using the keyword meant that I did not think about the underlying iteration. Should I have though about the iteration level, I might have discovered and applied the optimisation.

Looking forward to the next Array Cast episode!

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.26 05:28 PM - edited 2022.10.26 05:34 PM

Good explaination of your approach here.

I've found a more novel approach where we can create palindromes and then check if it has products, rather than finding all products and checking if they are palindromes.

This has the benefit of not needing to create a matrix of products and keeps memory usage under control.

We can create the palindromes from inside out, going from 9 to 0. This means our list will be already be sorted in descending order.

Then using recursion, we can check if each palindrome has 2 products within our range and early exit once we have our solution.

This yields ~200ms for 5 digit numbers and 14s for 6 digit numbers.

f:{

// Create all palindromes in reverse order

digits:reverse string til 10;

palindromes:{[x;y;z]raze x,/:'y,\:/:x}[digits]/[;til x-1];

pals:"J"$palindromes 2#/:digits;

// create all 4 digit numbers

nums:reverse r[1]+til(-/)r:`long$10 xexp 0 -1+\:x;

// Recursively check each palindrome, early exit if found

{[pals;nums]

p:first pals;

b:and[first[nums]>n]not mod[;1]n:p%nums mod[p;nums]?0;

$[b;p;.z.s[1_pals;nums]]

}[pals;nums]

}

\ts f 3 / 906609 - 0 820208

\ts f 4 / 99000099 - 6 13649968

\ts f 5 / 9966006699 - 204 360770864

\ts f 6 / 999000000999 - 14273 8422339312

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

a month ago

Very efficient solution!

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

a month ago

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

a month ago

Thanks Stephen! I've created a pull request there.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

4 weeks ago

Hi, very nice. I'm pretty new to Q so it's cool to see how to handle recursion.

I see 2 potential issues which may not really affect the final answer, but are perhaps worth bearing in mind.

The list pals will contain non palindromes as the outer digit is allowed to be zero. So for example:

```
q)digits:reverse string til 10;
q)palindromes:{[x;y;z]raze x,/:'y,\:/:x}[digits]/[;til 3-1];
q)pals:"J"$palindromes 2#/:digits
q)(-5)#pals
4400 3300 2200 1100 0
```

The other thing is only even length palindromes are considered. You can have odd length palindromes 911*109=99299, so you can't for instance reverse pals to find the min.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

4 weeks ago

Hi gberkeley, well spotted! You are totally correct in what you have said here, the last 10% of "pals" will have been joined with "0" and will therefore not be palindromes when cast back to a long.

You're also right that I don't check any of the odd-digit palindromes. This is because for X-digit products, their even-digit palindromes will always be larger than their odd-digit palindromes.

eg for 3-digit products

odd-digit palindrome range = 10000 - 99999

even-digit palindrome range = 100000 - 999999

I figured I could get away with not checking odd-digit palindromes and not removing the last 10% of invalid "pals", if I could prove that there will always be at least 1 even-digit palindrome. And with a bit of trail and error, managed to find this:

909*902 / 819918

9009*9002 / 81099018

90009*90002 / 8100990018

900009*900002 / 810009900018

9000009*9000002 / 81000099000018

90000009*90000002 / 8100000990000018

I maybe should have added this into my original description, but I appreciate the question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

4 weeks ago - last edited 4 weeks ago

Which, now that I think about it, could have been used to reduce the total number of "nums" that need checked.

nums:reverse(n-m)+til m:div[;10]n:prd x#10;

This doubles performance from original code.

Further improvements could be made by not creating all of the last palindrome joins and only joining 8 and 9.

palindromes:{[x;y;z]raze x,/:'y,\:/:x};

pals:"J"$palindromes[2#digits]/[;0] palindromes[digits]/[2#/:digits;til x-2];

This has a 5 times speed improvement from original code.

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Resources

Popular Links

Follow Us

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.