### Nickolas's blog

By Nickolas, 6 years ago, translation,

#### 470A - Crystal Ball Sequence

As usual, the first problem tests competitors' ability to do basic math, and in this case it is even easier than the sample — without any loops.

^'0-
$1+*3*1+. #### 470B - Hexakosioihexekontahexaphobia This problem uses more advanced language concepts — loop, conditional execution and even named variables! Variables are convenient to use as loop counters and result accumulators, so as to avoid stack manipulations for the same purpose. An if-then-else in FALSE looks like this: (true/false condition on top of stack)$
[(then statements)] ?
~ [(else statements)] ?

Solution:

0n:    {number of 6s found uninterrupted so far}
0r:    {true, if 666 found}
[^$1_=~] [ '6=$ [n; 1+ n:] ?
~ [0n:] ?
n; 2 > r; | r:
]
#
%
#

0i:
[n;2*i;>]
[% i;1+i:]
#

#### 470G - Hamming Distance

Same principle as in the previous problem — read characters of two strings into the stack (store the length of the strings into a named variable), then extract pairs of corresponding characters from it and accumulate the result in another named variable.

0n:
[^ $10=~] [n;1+n:] #% [^$ 1_=~]
[]
#%

0i:
0d:
[n;i;>]
[n;i;-1- O
n;n;+i;- O
=~ [d;1+d:] ?
i;1+i:]
#

0i:
[n;2*i;>]
[% i;1+i:]
#

d;. 

#### 470H - Array Sorting

Same as the regular sorting task, this problem can be solved in many ways.

You could write a "simple counting sort", as recommended by Egor: do an outer loop from 1 to 100, in the inner loop iterate over all array elements and print each element that equals the counter of the outer loop. Here is the code.

Or you could store array elements in named variables (since there are very few of them) and generate a code which would compare pairs of variables and swap them if needed. Thus, instead of a[0] you use variable a, instead of a[1] — b etc. The first such solution I've seen was nab's: the code.

I chose yet another approach: read array elements into a stack and use selection sort, but each time you need a swap, copy the whole array (with elements swapped already) onto the top of the stack. After at most n swaps the top of the stack will hold a sorted array. Unfortunately, stack size is limited, and with n around 20 it overflows. So I reduced array size a lot, which also allowed other approaches :-)

[0[^  47> \58\> &]['0- \ 10*+]#%] r:

r;! n:   {read the number of elements in array}

0i:
[n;i;>]
[r;! i;1+i:]
#        {read the elements of the array}

1s:      {# of array copies stored in memory}

0i:
[n;1-i;>]
[ i;m:          {index of min element between i and n-1, inclusive}
i;1+j:
[n;j;>]
[ n;m;-1- O   {extract a[m]}
n;j;- O     {extract a[j], knowing that a[m] is on top}
>
[j;m:] ?    {if a[j] > a[m], m := j}
j;1+j:
]#

i;m;=~
[ 0k:
[n;k;>]
[ k;e:     {index of element we're extracting now}
k;i;=
[m;e:] ?
k;m;=
[i;e:] ?
n;k;+e;-1- O
k;1+k:
]#
s;1+s:      {+1 copy of array in memory}
] ?           {if i != m, copy all elements, while swapping a[i] and a[m]}

i;1+i:]
#

0i:
[n;i;>]
[n;i;-1- O . " "
i;1+i:]
#

0i:
[n;s;*i;>]
[% i;1+i:]
#

• +55

 » 6 years ago, # | ← Rev. 2 →   +1 For problem D, I am confused by the answer checker. If you will look at My Submission here, you will see that the output matches exactly. Many other contestants had the same problem. What happened?
•  » » 6 years ago, # ^ |   +1 Probably some mix-up with end-of-line characters. You read string to be encrypted till end-of-file, but end-of-file is preceded by end-of-line, so your output probably has some invisible characters.
 » 6 years ago, # |   0 missed it :(
 » 6 years ago, # | ← Rev. 2 →   0 470H has a couple of other easier approaches than selection sort (now that I'm somewhat familiar with the language).I wrote a bubble sort in 103B (code). The logic is pretty simple, we repeat N times (copy array, but swap top two if needed).I also came up with a solution in 95B (code) that at most has about maybe n+3 elements on the stack, but takes O(sum(a)) instruction stack size and O(sum(a)*n) time. Again we use a bubble sort, but we temporarily hide portions of the stack (storing the values in the instruction stack) and only do swaps at the top of the stack. This was actually super easy to get right, since all of the logic was "local" (i.e. operating on the top few stack values).
•  » » 6 years ago, # ^ |   0 That’s pretty damn awesome.
•  » » 6 years ago, # ^ |   0 I didn't participate in the contest, but my solution was similar to what was described as the counting sort, except I didn't iterate over all possible values — instead, I found the smallest number that I haven't printed yet (in other words, it is greater than the lasts number I printed), and how many of them are in the array. Then I printed that number several times and looped. The complexity is O(n^2) and uses linear stack size. Its quite a bit longer than yours but I'm sure its possible to shorten with some tricks I see you using: 7804834
 » 6 years ago, # |   0 This type of contest is so interesting. O(∩_∩)O~
 » 6 years ago, # | ← Rev. 2 →   +3 My solution for problem B: click :D
 » 6 years ago, # | ← Rev. 3 →   +8 i had addicted to this... and wrote a simple interpreter to solve C~H besides, i thought this this resolution is better by using a placeholder and persistent insertion sort.