KX Community

Find answers, ask questions, and connect with our KX Community around the world.
KX Community Guidelines

Home Forums kdb+ Challenge 1 – Triangle Font

  • Challenge 1 – Triangle Font

    Posted by megan_mcp on January 30, 2023 at 12:00 am

    Hi all ! I want to introduce my first challenge Triangle Font. 

    I initially solved it in python as I am a bit more confident in that language then I attempted to solve it in q.  

    Problem 1 Triangle Font 

    You are given a positive integer?X. Print a numerical triangle of height?X – 1?like the one below: 

    1 

    22 

    333 

    4444 

    55555 

    .. 

    Python Solution:

    for i in range(1,int(input())): print((pow(10, i)//9)*i)

    This is where Ive got to in q: 

    1 "Type a number: "; //Prompt for user input 
    input: read0 0; //Save user input as variable 
    i: 1; //Assign variable i as 1 
    output:{[input] //Function with input as parameter 
              each[(floor((10 xexp i)%9)*i);input] //floor = to round down, 10 xexp i = 10 to the power of i, divide by 9, multiplied by i 
              i: i+1; //Increment i by 1 }

     

    I am trying to imitate the iterating of the for loop by using each while also incrementing i.  

    This is how I visualised my approach, but it is throwing a type error. 

    Hoping I can get some suggestions on how else I could approach this problem, and any advice would be greatly appreciated. 

     

    Thanks in advance,  

    Megan 

    megan_mcp replied 2 months, 2 weeks ago 5 Members · 10 Replies
  • 10 Replies
  • SJT

    Member
    January 2, 2023 at 12:00 am

    Sure!

    The rest of the expression returns a nested list of integers

     

    q){x#’x}1+til 4

    ,1

    2 2

    3 3 3

    4 4 4 4

     

    Remove those spaces? If your brain has been trained by the one potato, two potato* approach of C-like languages, it immediately sees a double loop to work through the result. The vector programmer sees an opportunity to index. Indexing has atomic iteration; it does all the looping we need.

    * This delightful expression was used by Joel Kaplan on the Array Cast podcast.

     

    q)"0123456789"[{x#'x}1+til 4] 
    ,"1" 
    "22" 
    "333" 
    "4444"

     

    Q syntax encourages us to replace nested argument brackets with Index (or Index At for unaries) so were not scanning code back and forth. And prefix notation is syntactic sugar for Index At, so the @s can disappear.

     

    q)count[distinct[[.Q.a[3 17 14 15 26 3 4 0 3]]]] 
    7 
    q)count@distinct@.Q.a@3 
    17 14 15 26 3 4 0 3 7 
    q)count distinct .Q.a 
    3 17 14 15 26 3 4 0 3 7 
    q) 
    q)"0123456789"{x#'x}1+til 4 
    ,"1" 
    "22" 
    "333" 
    "4444"

     

    Shifting to vector thinking from one potato, two potato takes practice, which is why the Vector Dojo exists. (Its also a lot of fun.)

    The last step is to remove the double quotes q uses to display strings. (And the comma it uses to mark a 1-item vector.)

    Q inherits much of ks design principle: no unnecessary typing. The console, stdout and stderr are simply the longs 0, 1 and 2, which (along with communication handles) have unary function syntax. Plainly put, a string argument to 1 is written to stdout as a side effect.

     

    q)1 “til 6”

    til 61

     

    But the result of 1 is still 1, and that got written to the console too and followed as usual by a newline. Terminating an expression with a semicolon stops its result being displayed at the console, and is the only good use for a terminating semicolon. (Multiline lambdas use them as separators, which is similar. An expression not followed by a semicolon separator becomes the lambdas result.)

     

    q)1 “til 6”; til 6

    q)

     

    OK, we ignored the expression result, but we lost the newline too. No unnecessary typing! Instead of joining a newline to the end of each output string, we use the negative of the system handle, which does it for us.

     

    q)1 “til 6n”; til 6

    q)-1 “til 6”; til 6

    q)-1 “0123456789”{x#’x}1+til 4;

    1 
    22 
    333 
    4444

     

    Of course stdout and stderr both default to the console, so where is 0 in all this? Well 0 does what the console does: give it a string and it returns the result of evaluating it.

     

    q)1+0 “til 6”

    1 2 3 4 5 6

     

     

  • SJT

    Member
    February 2, 2023 at 12:00 am

    BaiChens solution uses the Scan form of the Do iterator  rather than the Each iterator ' I used.

    Terse q helps us focus on the core of the algorithm. Lets use BaiChens solution as a practice example.

    We can rewrite to eliminate the local variable. And, all other things being equal, good q style prefers infix syntax to bracket notation.

     

    q)8{first[x+1]#x+1}1 
    1 
    2 2 
    3 3 3 
    4 4 4 4 
    5 5 5 5 5 
    6 6 6 6 6 6 
    7 7 7 7 7 7 7 
    8 8 8 8 8 8 8 8 
    9 9 9 9 9 9 9 9 9

     

    The addition surely only needs doing once?

     

    q)4{first[b]#b:x+1}1 
    1 
    2 2 
    3 3 3 
    4 4 4 4 
    5 5 5 5 5

     

    On each iteration the vector argument lengthens. But we need increment only its first item.

     

    q)4{b#b:1+first x}1 
    1 
    2 2 
    3 3 3 
    4 4 4 4 
    5 5 5 5 5

     

    The pattern N f1 is easily recognisable as: Do f N times, starting with 1.

    Tightening up the algorithm saves CPU, but the Each is faster still.

     

    q)ts:10000 {b:first x+1;b#x+1}[100;1] 
    438 64560 
    q)ts:10000 100{b#b:1+first x}1 
    301 63536 
    q)ts:10000 {x#'x} 1+til 100 
    174 63616

     

    On the next episode of the Array Cast (just recorded on Tuesday), Michael Higginson talks about how the terse and interactive APL and q REPLs encourage him to compare multiple solutions in a way he would rarely have time to do when writing Java.

  • SJT

    Member
    February 2, 2023 at 12:00 am

    This is my favourite, besides being faster! All the iteration is implicit. Lovely use of where on an int vector to generate all the items in one hit.

    Implicit iterations tend to be faster than iterators.

  • baichen

    Member
    February 2, 2023 at 12:00 am
    q){b:first x+1;b#x+1}[8;1] 
    1 
    2 2 
    3 3 3 
    4 4 4 4 
    5 5 5 5 5 
    6 6 6 6 6 6 
    7 7 7 7 7 7 7 
    8 8 8 8 8 8 8 8
  • jfealy

    Member
    February 2, 2023 at 12:00 am

    Another alternative

    q)ts:10000 {x#'x} 1+til 100 
    207 63616 
    q)ts:10000 {sums[-1_t]_where t:til 1+x}100 
    106 130112 
    q){x#'x}[1+til 100]~{sums[-1_t]_where t:til 1+x}100 
    1b

    However, when applied to a large vector, performance drops off as cut is expensive

    q)ts {x#'x} 1+til 50000 
    4099 14763251840 
    q)ts {sums[-1_t]_where t:til 1+x}50000 
    6454 31943645248

     

  • SJT

    Member
    March 19, 2024 at 10:55 am

     

    q){x#’x}1+til 4

    ,1

    2 2

    3 3 3

    4 4 4 4

    q)tf:{x#’x}1+til ::

     

    Breaking it down

    1. 1+til gives us the natural numbers to whatever
    2. {x#'x} gives us N of each N
    3. Suffixing the three unaries with :: gives us the composition to be known as tf

    Nice challenge! Who would like to come to another Vector Dojo?

  • SJT

    Member
    March 19, 2024 at 10:55 am

    Or to lose the spaces

    q)-1 "0123456789"{x#'x}1+til 5; 
    1 
    22 
    333 
    4444 
    55555
  • smdesai

    Member
    March 19, 2024 at 11:00 am

    Hello!
    I saw your python solution and came up with the following.

    input: “I”$read0 0

    output:{((10 xexp x) div 9) * x} each 1 + til input show each

    “j”$output

     

  • megan_mcp

    Administrator
    March 19, 2024 at 11:00 am

    Thank you for your reply! I forgot about the casting.

     

     

     

  • megan_mcp

    Administrator
    March 19, 2024 at 11:00 am

    Perfect! What’s more effective than one line of code?

    Can you explain the start  of the code? :

    q)-1 "0123456789"

     

Log in to reply.