Random Haskell Code Challenge

I was at work when a friend and colleague of mine showed me a funny meme, and it is about a student that tricked the teacher in a simple programming challenge, or probably a test. The requested output from the student is to create a program and produce the following result on the screen

ABCDEFGFEDCBA
ABCDEF_FEDCBA
ABCDE___EDCBA
ABCD_____DCBA
ABC_______CBA
AB_________BA
A___________A

At first, it seems that the challenge involves an algorithm "for loops" and manipulation/re-arranging of data inside the loop to achieve the desired result. The student presented a dummy non-working code that has two nested for loops and some index manipulation. These loops appear to be dead code, and the student then adds a procedure that prints the encoded output. After that, the teacher didn't bother to check the underlying logic and asked the student to run the code directly, yet the student managed to hide the encoded code in plain sight.

for(int i=0; i<arr.length; i++) {
  for(int j=0; i... ) {
    // some none working code..
  }
}
printsomething()

printSomething() {

  print("ABCDEFGFEDCBA")
  print("ABCD....")
  ...
}

That's very funny to think of, and it's quite challenging, and I thought perhaps "Why not solve this kind of challenge in Haskell code" I'm not an expert in Haskell, nor do I use Haskell in my day-to-day work, but in any case, it's a good exercise so let's jump in.

Without a problem definition, we assume that we need to print "A" to "G" and after that, it will go back from "F" to "A", and at the very least that's how it appears in the first line. We could then apply this rule for all the succeeding lines, and just with an added twist we also eliminate the characters in the middle until there's only one character left to print out.

First Step: Generate a Data

Generate a list of lists, and each list will have different lengths

list 1 of length 7
list 2 of length 6
list 3 of length 5
...

we then put this on a list, that would be

[ list1, list2, list3, ... ]

as of now this list contains ordered numbers incremented by 1, we achieve that by Haskell infinite list and take only the desired length.

take 5 [1..] -- take 5 elements in an infinite list.
-- [1, 2, 3, 4, 5]

Okay, so far we have a function to build a list of numbers incrementing by 1. Next, we generate a list of length 7 used as a row, this then will be mapped to generate a list as a length, let's call this rangeMatrix.

import Data.List

rangeMatrix = fmap (\n -> take n [1..]) [1..7]
-- [ [1]
-- , [1, 2]
-- , [1, 2, 3]
-- , [1, ... ]
-- ...
-- ]

The fmap here is like in javascript Array.map, which maps each element in the list using a mapper function, in our case the mapping function accepts an integer (n) and returns a list taking only (n) elements.

Now that we have a generated matrix of numbers, we convert these numbers to our desired characters "A" to "G", we then create a simple mapping function to achieve this

conv :: Int -> Char
conv 1 = 'A'
conv 2 = 'B'
conv 3 = 'C'
conv 4 = 'D'
conv 5 = 'E'
conv 6 = 'F'
conv 7 = 'G'
conv _ = ' '

then we map the rangeMatrix numeric to converted character.

rangeMatrixChars :: [[Int]] -> [[Char]]
rangeMatrixChars xss = fmap (fmap conv) xss
-- [ ['A']
-- , ['A', 'B']
-- , ['A', 'B', 'C']
-- , ['A', ... ]
-- ...
-- ]

Second step: Format Data

The next step and the most interesting part is to format this matrix to a readable string. It is a common practice in functional programming to design modular functions, each of which has responsibilities. In our case, we just currently designed a function that generates data, and now we will create a function that accepts our matrix characters and process it to a single list of characters (also equivalent to String in Haskell).

prettyFormat :: [[Char]] -> [Char]
prettyFormat xss =
 foldl prettyFormatStep [] xss

and each step of the format will do

prettyFormatStep :: Int -> [Char] -> [Char] -> [Char]
prettyFormatStep maxChar [] xs =
  xs
prettyFormatStep maxChar acc xs =
  xs
  ++ ['\n']
  ++ acc

ABCDEFG
ABCDEF
ABCDE
ABCD
ABC
AB
A

We're getting closer to the desired output. In addition, we need to tweak it out a little bit. Next, we add negative space, to show disappearing characters. As of now, we use the * character

negativeSpaceFormat maxChar whiteSpaceChar xs = 
  replicate (abs (length xs - maxChar)) whiteSpaceChar

and in prettyFormatStep will be

prettyFormatStep maxChar [] xs =
  xs
+ ++ (negativeSpaceFormat maxChar '*' xs ++ reverse xs)

prettyFormatStep maxChar acc xs =
  xs
+ ++ (negativeSpaceFormat maxChar '*' xs ++ reverse xs)
  ++ ['\n']
  ++ acc

ABCDEFG
ABCDEF*
ABCDE**
ABCD***
ABC****
AB*****
A******

and finally, we add the mirror of the output per row.

prettyFormatStep maxChar [] xs =
  xs
  ++ negativeSpaceFormat maxChar '*' xs
+ ++ (negativeSpaceFormat maxChar '*' xs ++ reverse xs)

prettyFormatStep maxChar acc xs =
  xs
  ++ negativeSpaceFormat maxChar '*' xs
+ ++ (negativeSpaceFormat maxChar '*' xs ++ reverse xs)
  ++ ['\n']
  ++ acc

Since the negative whitespace characters are in symmetry we don't need to reverse it, but in general, the reversed will also be applied. The final output would be

ABCDEFGGFEDCBA
ABCDEF**FEDCBA
ABCDE****EDCBA
ABCD******DCBA
ABC********CBA
AB**********BA
A************A

But wait! We have an error, the output so far is not the same as the expected output at the beginning of this article. If we notice the first row has a duplicate G and the second row has an extra * for each row. The problem is that we mirror exactly our data which is the exact inverse of the list. We could fix this by removing the first element of the inversed list. We can use the function tail to fix this.

prettyFormatStep maxChar [] xs =
  xs
  ++ negativeSpaceFormat maxChar '*' xs
- ++ (negativeSpaceFormat maxChar '*' xs ++ reverse xs)
+ ++ tail (negativeSpaceFormat maxChar '*' xs ++ reverse xs)

prettyFormatStep maxChar acc xs =
  xs
  ++ negativeSpaceFormat maxChar '*' xs
- ++ (negativeSpaceFormat maxChar '*' xs ++ reverse xs)
+ ++ tail (negativeSpaceFormat maxChar '*' xs ++ reverse xs)
  ++ ['\n']
  ++ acc

ABCDEFGFEDCBA
ABCDEF*FEDCBA
ABCDE***EDCBA
ABCD*****DCBA
ABC*******CBA
AB*********BA
A***********A

If you read the article up to this point you deserve applause 👏 we did arrive at the expected output.

There are a few optimization and syntax that needs to be adjusted, some of you may have a better understanding of Haskell may point out eta reduction, list comprehension, and many more. I leave it to you to tinker with this solution.

Thank you, and have fun coding

Full runnable source code: https://replit.com/@RonnelReposo/SimplisticAffectionatePackagedsoftware#Main.hs