Count Construct – Tabulation

Earlier today I read an article commenting about how the high temperatures are rising all over the USA. In Arizona and Nevada the forecasted highs should be about 115F and 112F respectively. The average temperature for a human adult is around 98F. That is quite warm if you ask me.

Today in the suburb in the Twin Cities of Minneapolis and St. Paul where I reside, we woke up with 72F. At some point we might be getting some rain. The high is forecasted to be 91F and we are still in spring 2021.

My wife and I have breakfast and then head out for a walk. We like to get the workout in first thing in the morning. After returning home, I watered some plants that were replaced outside a week or so ago. I have been informed that I need to water them 3 to 4 days a week for a month or so until the plants adapt to their current location; so far, so good. We do need some rain. The lawns in our area are starting to show some brown spots. We can see and hear the sprinklers in the morning, but seems that laws need additional water. A few good down pours each month would take care of the brown spots. Based on NOAA’s forecast, it is going to be a dry and hot summer for most parts in the USA.

Yesterday I mentioned that I requested a callback from a Delta agent. Based on the information at hand, I was expecting the callback in about two hours. I did receive the call. At that time I had performed enough searches on the web that I had solved the issue before talking with the agent. All is well at this time.

As you might know if you follow me on this blog, I am watching the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges and attempt to solve the problems and exercises. The instructor uses the JavaScript programming language. I am using the Java programming language.

We have solved this problem in a previous post Can Construct using dynamic programming without and with memoization. In this post we will solve the same problem using tabulation.

Write a function `countConstruct(target, wordBank)` that accepts a
target string and an array of strings.

The function should return the number of ways that the `target` can
be constructed by concatenating elements of the `wordBank` array.

You may reuse elements of `wordBank` as many times as needed.

The requirements for the function in question are similar, if not identical, to our previous pass.

int countConstruct(String target, String[] wordBank) {
}

As mentioned I will be solving the problem using the Java programming language, the VSCode IDE on a window 10 computer. You are welcomed to use any platform, IDE or programming language.


he,llo,w,o,rl,d
main <<< target ==><==
main <<< wordBank: [he, llo, w, o, rl, d]
main <<< countConstruct: 0


purple
purp,p,ur,le,purpl
main <<< target ==>purple<==
main <<< wordBank: [purp, p, ur, le, purpl]
<<< table: [1, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 0, 0, 1, 0, 0]
<<< i: 0 table: [1, 1, 0, 0, 1, 0, 0]
<<< i: 0 table: [1, 1, 0, 0, 1, 1, 0]
<<< i: 1 table: [1, 1, 0, 1, 1, 1, 0]
<<< i: 3 table: [1, 1, 0, 1, 2, 1, 0]
<<< i: 4 table: [1, 1, 0, 1, 2, 1, 2]
main <<< countConstruct: 2


abcdef
ab,abc,cd,def,abcd
main <<< target ==>abcdef<==
main <<< wordBank: [ab, abc, cd, def, abcd]
<<< table: [1, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 1, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 1, 1, 0, 0, 0]
<<< i: 0 table: [1, 0, 1, 1, 1, 0, 0]
<<< i: 2 table: [1, 0, 1, 1, 2, 0, 0]
<<< i: 3 table: [1, 0, 1, 1, 2, 0, 1]
main <<< countConstruct: 1


skateboard
bo,rd,ate,t,ska,sk,boar
main <<< target ==>skateboard<==
main <<< wordBank: [bo, rd, ate, t, ska, sk, boar]
<<< table: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0]
<<< i: 5 table: [1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0]
main <<< countConstruct: 0


enterapotentpot
a,p,ent,enter,ot,o,t
main <<< target ==>enterapotentpot<==
main <<< wordBank: [a, p, ent, enter, ot, o, t]
<<< table: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 2, 0, 0, 2, 0, 0, 0]
<<< i: 12 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 2, 0, 0, 2, 2, 0, 0]
<<< i: 13 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 2, 0, 0, 2, 2, 0, 2]
<<< i: 13 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 2, 0, 0, 2, 2, 2, 2]
<<< i: 14 table: [1, 0, 0, 1, 0, 1, 1, 1, 1, 2, 0, 0, 2, 2, 2, 4]
main <<< countConstruct: 4


eeeeeeeeeeeeeeeeeeeeeeeeeeeeef
e,ee,eee,eeee,eeeee,eeeeee
main <<< target ==>eeeeeeeeeeeeeeeeeeeeeeeeeeeeef<==
main <<< wordBank: [e, ee, eee, eeee, eeeee, eeeeee]
<<< table: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 0 table: [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 1 table: [1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 1 table: [1, 1, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 1 table: [1, 1, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 1 table: [1, 1, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 1 table: [1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 1 table: [1, 1, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 1, 2, 4, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 1, 2, 4, 4, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 1, 2, 4, 4, 4, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 1, 2, 4, 4, 4, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 1, 2, 4, 4, 4, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 2 table: [1, 1, 2, 4, 4, 4, 4, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 1, 2, 4, 8, 4, 4, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 1, 2, 4, 8, 8, 4, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 1, 2, 4, 8, 8, 8, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 1, 2, 4, 8, 8, 8, 7, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 1, 2, 4, 8, 8, 8, 7, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 3 table: [1, 1, 2, 4, 8, 8, 8, 7, 6, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 4 table: [1, 1, 2, 4, 8, 16, 8, 7, 6, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 4 table: [1, 1, 2, 4, 8, 16, 16, 7, 6, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 4 table: [1, 1, 2, 4, 8, 16, 16, 15, 6, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 4 table: [1, 1, 2, 4, 8, 16, 16, 15, 14, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 4 table: [1, 1, 2, 4, 8, 16, 16, 15, 14, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 4 table: [1, 1, 2, 4, 8, 16, 16, 15, 14, 12, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 1, 2, 4, 8, 16, 32, 15, 14, 12, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 1, 2, 4, 8, 16, 32, 31, 14, 12, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 1, 2, 4, 8, 16, 32, 31, 30, 12, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 1, 2, 4, 8, 16, 32, 31, 30, 28, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 1, 2, 4, 8, 16, 32, 31, 30, 28, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 5 table: [1, 1, 2, 4, 8, 16, 32, 31, 30, 28, 24, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 1, 2, 4, 8, 16, 32, 63, 30, 28, 24, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 1, 2, 4, 8, 16, 32, 63, 62, 28, 24, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 1, 2, 4, 8, 16, 32, 63, 62, 60, 24, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 1, 2, 4, 8, 16, 32, 63, 62, 60, 56, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 1, 2, 4, 8, 16, 32, 63, 62, 60, 56, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 6 table: [1, 1, 2, 4, 8, 16, 32, 63, 62, 60, 56, 48, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 60, 56, 48, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 123, 56, 48, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 123, 119, 48, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 123, 119, 111, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 123, 119, 111, 95, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 7 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 123, 119, 111, 95, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 119, 111, 95, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 244, 111, 95, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 244, 236, 95, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 244, 236, 220, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 244, 236, 220, 188, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 8 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 244, 236, 220, 188, 125, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 236, 220, 188, 125, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 484, 220, 188, 125, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 484, 468, 188, 125, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 484, 468, 436, 125, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 484, 468, 436, 373, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 9 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 484, 468, 436, 373, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 10 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 468, 436, 373, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 10 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 960, 436, 373, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 10 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 960, 928, 373, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 10 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 960, 928, 865, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 10 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 960, 928, 865, 740, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 10 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 960, 928, 865, 740, 492, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 11 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 928, 865, 740, 492, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 11 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 1904, 865, 740, 492, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 11 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 1904, 1841, 740, 492, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 11 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 1904, 1841, 1716, 492, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 11 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 1904, 1841, 1716, 1468, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 11 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 1904, 1841, 1716, 1468, 976, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 12 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 1841, 1716, 1468, 976, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 12 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 3777, 1716, 1468, 976, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 12 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 3777, 3652, 1468, 976, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 12 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 3777, 3652, 3404, 976, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 12 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 3777, 3652, 3404, 2912, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 12 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 3777, 3652, 3404, 2912, 1936, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 13 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 3652, 3404, 2912, 1936, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 13 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 7492, 3404, 2912, 1936, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 13 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 7492, 7244, 2912, 1936, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 13 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 7492, 7244, 6752, 1936, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 13 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 7492, 7244, 6752, 5776, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 13 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 7492, 7244, 6752, 5776, 3840, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 14 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 7244, 6752, 5776, 3840, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 14 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 14861, 6752, 5776, 3840, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 14 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 14861, 14369, 5776, 3840, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 14 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 14861, 14369, 13393, 3840, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 14 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 14861, 14369, 13393, 11457, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 14 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 14861, 14369, 13393, 11457, 7617, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 15 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 14369, 13393, 11457, 7617, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 15 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 29478, 13393, 11457, 7617, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 15 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 29478, 28502, 11457, 7617, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 15 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 29478, 28502, 26566, 7617, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 15 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 29478, 28502, 26566, 22726, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 15 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 29478, 28502, 26566, 22726, 15109, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 16 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 28502, 26566, 22726, 15109, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 16 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 58472, 26566, 22726, 15109, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 16 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 58472, 56536, 22726, 15109, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 16 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 58472, 56536, 52696, 15109, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 16 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 58472, 56536, 52696, 45079, 0, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 16 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 58472, 56536, 52696, 45079, 29970, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 17 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 56536, 52696, 45079, 29970, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 17 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 115984, 52696, 45079, 29970, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 17 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 115984, 112144, 45079, 29970, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 17 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 115984, 112144, 104527, 29970, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 17 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 115984, 112144, 104527, 89418, 0, 0, 0, 0, 0, 0, 0, 0]
<<< i: 17 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 115984, 112144, 104527, 89418, 59448, 0, 0, 0, 0, 0, 0, 0]
<<< i: 18 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 112144, 104527, 89418, 59448, 0, 0, 0, 0, 0, 0, 0]
<<< i: 18 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 230064, 104527, 89418, 59448, 0, 0, 0, 0, 0, 0, 0]
<<< i: 18 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 230064, 222447, 89418, 59448, 0, 0, 0, 0, 0, 0, 0]
<<< i: 18 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 230064, 222447, 207338, 59448, 0, 0, 0, 0, 0, 0, 0]        
<<< i: 18 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 230064, 222447, 207338, 177368, 0, 0, 0, 0, 0, 0, 0]       
<<< i: 18 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 230064, 222447, 207338, 177368, 117920, 0, 0, 0, 0, 0, 0]  
<<< i: 19 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 222447, 207338, 177368, 117920, 0, 0, 0, 0, 0, 0]  
<<< i: 19 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 456351, 207338, 177368, 117920, 0, 0, 0, 0, 0, 0]  
<<< i: 19 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 456351, 441242, 177368, 117920, 0, 0, 0, 0, 0, 0]  
<<< i: 19 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 456351, 441242, 411272, 117920, 0, 0, 0, 0, 0, 0]  
<<< i: 19 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 456351, 441242, 411272, 351824, 0, 0, 0, 0, 0, 0]  
<<< i: 19 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 456351, 441242, 411272, 351824, 233904, 0, 0, 0, 0, 0]
<<< i: 20 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 441242, 411272, 351824, 233904, 0, 0, 0, 0, 0]
<<< i: 20 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 905210, 411272, 351824, 233904, 0, 0, 0, 0, 0]
<<< i: 20 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 905210, 875240, 351824, 233904, 0, 0, 0, 0, 0]
<<< i: 20 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 905210, 875240, 815792, 233904, 0, 0, 0, 0, 0]
<<< i: 20 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 905210, 875240, 815792, 697872, 0, 0, 0, 0, 0]
<<< i: 20 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 905210, 875240, 815792, 697872, 463968, 0, 
0, 0, 0]
<<< i: 21 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 875240, 815792, 697872, 463968, 0, 0, 0, 0]
<<< i: 21 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 1795559, 815792, 697872, 463968, 0, 0, 0, 0]
<<< i: 21 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 1795559, 1736111, 697872, 463968, 
0, 0, 0, 0]
<<< i: 21 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 1795559, 1736111, 1618191, 463968, 0, 0, 0, 0]
<<< i: 21 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 1795559, 1736111, 1618191, 1384287, 0, 0, 0, 0]
<<< i: 21 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 1795559, 1736111, 1618191, 1384287, 920319, 0, 0, 0]
<<< i: 22 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 1736111, 1618191, 1384287, 920319, 0, 0, 0]
<<< i: 22 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 3561640, 1618191, 1384287, 920319, 0, 0, 0]
<<< i: 22 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 3561640, 3443720, 1384287, 920319, 0, 0, 0]
<<< i: 22 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 3561640, 3443720, 3209816, 920319, 0, 0, 0]
<<< i: 22 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 3561640, 3443720, 3209816, 2745848, 0, 0, 0]
<<< i: 22 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 3561640, 3443720, 3209816, 2745848, 1825529, 0, 0]
<<< i: 23 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 3443720, 3209816, 2745848, 1825529, 0, 0]
<<< i: 23 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 7064808, 3209816, 2745848, 1825529, 0, 0]
<<< i: 23 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 7064808, 6830904, 2745848, 1825529, 0, 0]
<<< i: 23 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 7064808, 6830904, 6366936, 1825529, 0, 0]
<<< i: 23 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 7064808, 6830904, 6366936, 5446617, 0, 0]
<<< i: 23 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 7064808, 6830904, 6366936, 5446617, 3621088, 0]
<<< i: 24 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 6830904, 6366936, 5446617, 3621088, 0]
<<< i: 24 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 14013632, 6366936, 5446617, 3621088, 0]
<<< i: 24 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 14013632, 13549664, 5446617, 3621088, 0]
<<< i: 24 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 14013632, 13549664, 12629345, 3621088, 0]
<<< i: 24 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 14013632, 13549664, 12629345, 10803816, 0]
<<< i: 25 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 13549664, 12629345, 10803816, 0]
<<< i: 25 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 27797200, 12629345, 10803816, 0]
<<< i: 25 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 27797200, 26876881, 10803816, 0]
<<< i: 25 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 27797200, 26876881, 25051352, 0]
<<< i: 26 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 26876881, 25051352, 0]
<<< i: 26 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 55138049, 25051352, 0]
<<< i: 26 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 55138049, 53312520, 0]
<<< i: 27 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 111196417, 53312520, 0]
<<< i: 27 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 111196417, 109370888, 0]
<<< i: 28 table: [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 111196417, 220567305, 0]
main <<< countConstruct: 0

The first input line contains the target string. The second input line contains a set of words that makes up the `wordBank` that we may use to compose the target string.

Our test code seems to read the two input lines, generate and populate the variables, and display them. This is done to verify that all is well so far.

Our test code displays some values that allow us to verify that the code is progressing as expected.

When all is wet and done the results are displayed.

Note in the first test case that the target string is a blank line. Since the `wordBank` does not contain an empty string the result is 0.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open a buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read target string ****
        String target = br.readLine().trim();

        // **** read word bank array ****
        String[] wordBank = br.readLine().trim().split(",");

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< target ==>" + target + "<==");
        System.out.println("main <<< wordBank: " + Arrays.toString(wordBank));

        // **** call function of interest and display result ****
        System.out.println("main <<< countConstruct: " + countConstruct(target, wordBank));
    }

The test code seems to follow closely the description of the test cases. I will not add comments at this time.

**** Tabulation Recipe ****
  
1. Visualize the problem as a table (determine data type)
2. Size the table based on the inputs
3. Initialize the table with some values (determine base case)
4. Seed the trivial answer into the table
5. Iterate through the table
6. Fill further positions based on the current position

We have a recipe to implement tabulation. The recipe contains six steps. The first four steps are the most difficult in the process. They require ingenuity and practice.

    /**
     * Write a function `countConstruct(target, wordBank)` that accepts a
     * target string and an array of strings.
     * 
     * The function should return the number of ways that the `target` can
     * be constructed by concatenating elements of the `wordBank` array.
     * 
     * You may reuse elements of `wordBank` as many times as needed.
     * 
     * m = target.length
     * n = wordBank.length
     * 
     * Time: O(m^2 * n)  Space: O(m)
     */
    static int countConstruct(String target, String[] wordBank) {

        // **** sanity check(s) ****
        if (target.length() == 0) return 0;

        // **** initialization ****
        int[] table = new int[target.length() + 1];
        table[0] = 1;               // seed value

        // ???? ????
        System.out.println("<<< table: " + Arrays.toString(table));

        // **** iterate through the table ****
        for (int i = 0; i < table.length; i++) {

            // **** check if this table entry may NOT contribute ****
            if (table[i] == 0)
                continue;

            // **** traverse the word bank looking for candidates ****
            for (int j = 0; j < wordBank.length; j++) {

                // **** for ease of use ****
                String word = wordBank[j];

                // **** if out of bounds (skip) ****
                if (i + word.length() > target.length())
                    continue;

                // **** extract prefix from target ****
                String prefix = target.substring(i, i + word.length());

                // **** compare word with prefix ****
                boolean match = word.equals(prefix);

                // **** word and prefix match ****
                if (match) {

                    // **** compute index to update ****
                    int ndx = i + word.length();

                    // **** if out of bounds (skip) ****
                    if (ndx >= table.length)
                        continue;

                    // **** update table at specified index ****
                    table[ndx] += table[i];

                    // ???? ????
                    System.out.println("<<< i: " + i + " table: " + Arrays.toString(table));
                }
            }
        }

        // ???? ????
        // System.out.println("<<< table: " + Arrays.toString(table));

        // **** return last table entry ****
        return table[table.length - 1];
    }

Our function starts with a sanity check. If we receive a blank target string then we can return a 0.

In this case we decided to use a table of int[]. The reason for this is that we are expected to return an integer, so it would be practical to use a table of integers.

We initialize the table with a specific size. The size comes from the length of the target string plus one. The plus one is typically used to fit the base case and then have enough entries to process the rest of the characters in the string. As usual the idea is to get the final answer in the last entry in the table.

The first entry is seeded to value 1. The rest of the entries are initialized to 0.

We now traverse the entries in the table.

If an entry is set to 0 it implies that the current location is not contributing to the solution so we can skip it.

We now traverse the words in the `wordBank` once per entry in the table.

We check if the current location plus the length of the word would exceed the length of our table.

We extract the prefix from the target string starting at the current position.

We then compare the word with the prefix and determine if there is a match.

If there is a match we compute the target index in the table we wish to update.

The index is check so it is not out of bounds.

The value in the table we wish to update is added to the current value.

After all the entries in the table have been processed, the result is found in the last table entry.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.