PROJECT 1: NONOGRAMS (LANGUAGE: JAVA)

PROJECT OVERVIEW

Nonograms, also known as hanjies, are a type of graphical logic puzzle. In their simplest form, they take a piece of single colour pixel art and present the player with only information about the number of contiguous pixels on each row and column of that image. Based on this information, the player must use logic to deduce and reconstruct the original image.

Figure 1: A screenshot of a 15x15 pixel incomplete nonogram.

The numbers at the top and left of the image represent the number of pixels that are shaded on the respective row or column. Each value states the number of pixels that are shaded in a contiguous block (a block with no gaps). If multiple values are shown, then each contiguous block must be separate by at least one pixel that is not shaded. The order of the values given for each row/column is also consistent with the order of the contiguous blocks of pixels.

For example, in the diagrams above a yellow square indicates an unknown value. A black square is shaded, and white square is not shaded. We can see that the 7th row has a single value (15) stated. As there are only 15 squares on the row, all the pixels on that row must be shaded, as in the solution. The 8th row has the values (1,1,1,1,1,1,1) meaning that the solution for that row has 7 single pixels shaded, each separate by

Figure 2: A screenshot of a 15x15 pixel completed nonogram. a non-shaded square, as in the solution.

More advanced puzzles also support an additional colour, such that there are three colours overall. In this case, the rules are the same, but the number values are also coloured to indicate which colour each contiguous block of pixels should be. Also, contiguous blocks of pixels may be separated by any change in colour (not necessarily just white). See here for an example.

THE TASK

Your challenge is to write an interactive nonogram puzzle game. The program should:

• Generate and visualize a nonogram grid containing the correct informational values given an image represented by a two-dimensional boolean array.
• Interactively allow the user to shade/unshade each square.
• Determine if the user has solved the puzzle by shading in the correct squares.
• Students studying SCC131 should also allow any single colour Windows Bitmap (.bmp) image file to be read into your program from which the puzzle can be generated. We have provided some sample images alongside this specification. You should parse this .bmp file from first principles (i.e. without the use of any image specific library functions or classes) to determine which pixels are set or unset in the image.

GETTING STARTED

If you’re unfamiliar with nonograms, you’ll need to do some research to learn the rules of these puzzles. Also, you’ll need to understand more about the format of Windows .bmp files. To get started, we recommend that you:

• Visit the Hanjie website and try to complete some of the easy and moderate examples:

http://www.hanjie.co.uk/hanjie1.php

• Refresh your knowledge of the Swing classes we discussed in lectures and consider which graphical components and layout manager might help you!
• Research the basic Java classes that allow you to open, read and write bytes from files. This tutorial provides  a  nice  introduction:  https://www.tutorialspoint.com/java/java_files_io.htm
• Study the section below that outlines the simplified format of a Windows Bitmap file. This will help you to interpret the bytes that you read from the file.

WINDOWS BITMAP (.BMP) FILE FORMAT

The Windows Bitmap format is one of the simplest ways to record image data in a file. It does not make use of compression, so its files can get quite large, but the way in which the data is stored is much simpler than other formats such a JPEG or GIF.

Windows BMP allows for graphical data to be stored at any image width, height, or colour depth (the number of bits used to represent the colour of each pixel). As such, all this information is also stored in the file itself, before the pixel data. This is very common in file formats and is known as a file header. The following diagram illustrates a simplified view of the Windows BMP file. (See this article for a more detailed overview of the full specification for those of you that are interested!).

The left-hand column shows which byte in the file is being described (0 is the first byte, 1 is the next byte etc). The next columns describe what data is held in that location, and the final column illustrates the content using the ‘elephant.bmp’ file provided alongside this specification.

Note that many fields use multiple bytes. Such fields are all represented using unsigned, little-endian values.

i.e. the least significant byte comes first, and the most significant is last. The pixel data itself uses however

many bits are defined in the BITS_PER_PIXEL field to represent each pixel. The order of the pixels in left-to-right, bottom-to-top. Each row is also padded with zeros to ensure each row of pixels starts on a multiple of 4 bytes.

e.g. in the example above, the first 0xF0 0x00 bytes indicate that the first four pixels on the bottom row of the image are “colour 1” and the remaining 11 pixels are “colour 0”. The row is than padded to a multiple of four bytes with the following 0x00, 0x00 byes. The values 0x15 0xB8 then describe the next row up.

MARKING SCHEME

Marks will be awarded according to the marking scheme shown at the start of this document. Marks for the ‘Functionality’ section will be awarded based on individual merit, but the following table gives an indicative overview of the level of functionality expected for each grade band:

SCC Major Students Studying SCC.111, SCC.121 and SCC.131

1. Working program that meets the criteria for a B, plus:

• • Allows loading of arbitrary Windows Bitmap images of any size.

                     •    Supports puzzles containing at least two colours.                    

2. Working program that meets the criteria for a C, plus:

• • Allows the users to load single colour 15x15 pixel Windows BMP files to solve.
  • Highlights any incorrect squares when the puzzle is completed.

3. Working program that meets the criteria for a D, plus:

• • Dynamically computes and displays the numbers at the top and left-hand side of the puzzle.
  • Image to solve is hardcoded inside an array in the program.
  • Determines when game is complete, with an indicative message.

PROJECT 2: SOCIAL NETWORKS (LANGUAGE: JAVA)

PROJECT OVERVIEW

When users engage with social media, they form connections that can emerge into complex social networks. Online social networks can influence opinion on wide-ranging topics from politics to culture to marketing and advertising. By analysing such networks, we can understand more about how information (and disinformation) flows.

In social networks, such as X and LinkedIn, there is the idea of a person following another person. The concept that one person follows another can be thought of as a binary relation, for example “Xenia follows Rahul”. Social networks use this “follows” relation for various purposes, for example, to show content that might be relevant to a person.

This project will focus on analysing a fictious social network called “Dapper” which is described below. You will be provided with a file that represents the social network (list of users and whom they follow), based upon which you must accomplish the tasks described below.

TASKS

Some general details on Dapper are first given which you should read carefully to understand more about the network you will be analysing. The individual tasks to complete are then given below.

Assume you have an input file that specifies the social network. Each line in the file represents a person and the people they follow. Specifically, the first name on each line is a person in the network and any remaining names on the line are the people in the network whom they follow (you may assume no person follows themselves). Let’s say the contents of the input are as given the figure below.

This means that Raman follows Abe, Carla, Anwar and Cat; Cat follows Abe; Carla follows Raman and Abe; Abe doesn’t follow anyone; and Anwar follows Abe, Carla and Raman. An input may contain several such lines.

A diagram corresponding to the input in the previous graph input is given below.

12

Figure 5: A representation of a social network that will be the input for your tasks. Each line represents a person and the people they follow.

Figure 6: Representation of the “follows” relation for the social-network file given in Figure 1. Node X -> Node Y means X follows Y.

13

Your tasks are to read the input and write a program that performs the following tasks.

Task 2: Name a person who has the highest number of followers. In general, more than one person may have the same number of followers. If there is more than one person with the highest number of followers, then the name you give must be the one that is alphabetically first.

Task 3: Name a person who follows the highest number of people. Again, if there is more than one such person, again, the name you give must be the one that is alphabetically first

Task 4: A degree of separation is a measure of social distance between people. For example, people who are friends are separated by one degree. Two people who are not friends, but have a common friend are separated by two degrees.

For a person P in Dapper, we define people at two degrees of separation from P as follows.

• P’s followers are at one degree of separation from P.

• Followers of P’s followers who are neither P nor at one degree of separation from P are at two degrees of separation from P.

For the first person who appears in the input (for the input in Figure 1, this person is Raman), give the number of people at two degrees of separation from that person.

Task 5: Give the median value for the number of followers in the network, that is, over the data set whose elements consist of the number of followers for each person in the network. Note that the median value is the middle element in a data set – half the data elements are smaller than the median value and half the data elements are larger. Make sure you handle the case when the number of elements is even, in which case you have no unique middle element, but two middle elements. CLARIFICATION: In such a case, you must average the two middle elements, which means that the answer may not be an integer.

Task 6: In Dapper, a message originating from a person is automatically propagated to their followers and the followers’ followers, and so on (obviously in an acyclic manner; that is, a person doesn’t get the same message more than once). So, based on the social network of Figure 1, if Carla sends a message, then it is propagated to Anwar and Raman because they both follow Carla. Raman is Anwar’s only follower but he

14

has already seen the message; Carla and Anwar are Raman’s only followers but they too have seen the message. So a message sent by Carla propagates to Anwar and Raman.

Imagine you are an advertiser (you yourself are outside the social network) who wants to spread information about a new product to as many people as possible in Dapper. However, the catch is you can enrol only one person in the network to spread information on your behalf. Whom would you enrol? Again, if you determine that two or more people are equally worthy of being enrolled, you must give the name that is alphabetically first.

RUNNING YOUR PROGRAM

You will run your program by invoking at the command line in a terminal:

where <inputFile> is a command-line argument that stands for the name of the file that contains the input for your program.

So, for example, if the input file is named social-network.txt, then you would invoke:

Your program must not prompt the user for any input once executed as described above.

REQUIRED OUTPUT

Upon executing the program as described above, it must print in the terminal the answers for all tasks that you have accomplished. Print sufficiently informative statements such as “The person with the highest number of followers is Abe”, and so on.

The output for all tasks that you accomplish must be printed in one go, that is, without requiring any input from the user.

15

TESTING YOUR PROGRAM

A zip containing some example inputs and the corresponding answers has been made available to you. You may use them to test your program.

PRACTICING FOR THE IN-LAB EVALUATION

For your in-lab demonstration, you will be required to run the code you submitted to Moodle. Be sure the zip you upload to Moodle has everything you need in it and that you can compile the code and run it.

Make sure you test and practice this before you submit!

MARKING SCHEME

Marks will be awarded according to the marking scheme shown at the start of this document. Marks for the ‘Functionality’ section will be awarded based on individual merit, but the following table gives an indicative overview of the level of functionality expected for each grade band:

1. Working program that meets the criteria for a B, plus:

• • Meets the requirements of Tasks 6

2. Working program that meets the criteria for a C, plus:

• • Meets the requirements of Tasks 4 and 5 (Joint majors (students not taking 131) need only do one of these tasks

3. Working program that meets the criteria for a D, plus:

• • Meets the requirements of Tasks 2 and 3 (Joints majors need do only one of these tasks)

16

4. Working program that:

• • Meets the requirements of Task 1

F             No working program demonstrated, or program does not meet any requirements listed above

17

PROJECT 3: BUILD YOUR OWN STEP COUNTER (C++ AND ARM ASSEMBLY)

PROJECT OVERVIEW

Smartwatches are a popular platform to measure a user’s level of exercise. They typically utilize microcontrollers and n accelerometer sensors to enable this. They implement an algorithm to extrapolate the user’s direction and movement from simple acceleration measurements. The goal of this project is to design and implement a secure step tracker using the BBC micro:bit. The micro:bit's accelerometer will be used to detect steps, and the LED panel will display relevant information to the user. You will be using your micro:bit device to code your custom step counter functionality in C, a simple encryption algorithm in assembly.

Figure 7: image showing X axis across front of micro:bit, y axis up and down, z axis running back to front

The primary objective is to create a step tracker that:

• Count steps using the micro:bit accelerometer sensor.
• Displays the step count on the LED panel.

18

• Logs accelerometer data.
• Implements basic data security principles in assembly to ensure user data are protected.

THE TASK

This project will exercise the knowledge you acquired from modules SCC.111, SCC.121, SCC.131. You will have to use C++ and assembly to complete this project and you will use the knowledge of the micro:bit CoDAL APIs. To get full marks you are expected to complete the following activities. Marks will be awarded based on the number of tasks you complete. A starting point for your coursework can be the example   project   from   https://scc-source.lancs.ac.uk/scc.Y1/scc.131/microbit-v2-samples.

Task 1: Accelerometer measurements

Figure 8: Sample serial output of the step counter

An accelerometer is a sensor that measures the force of acceleration acting on it in all three spatial dimensions (X, Y, and Z), allowing it to detect orientation, tilt, and motion as well as the rate of change in velocity. A step tracker uses an accelerometer to detect the distinct patterns of movement associated with walking or running. Each step typically generates a specific acceleration signature, characterized by a high downwards acceleration followed by high acceleration upwards. By continuously monitoring the

19

accelerometer data, the software can apply algorithms to filter and interpret these patterns, distinguishing steps from other movements. This capability enables the step tracker to count the number of steps taken by the user by identifying and tallying these unique acceleration signatures, providing a practical tool for monitoring physical activity.

For this first task, you are expected to use the built-in micro:bit accelerometer, accessible by the CoDAL runtime accelerometer class and collect measurements. You must develop code that handles new accelerometer measurements and prints a message of “UP”, when the direction of movement changes from down to up (i.e., acceleration on the y axis changes from negative to positive) and “DOWN” when the direction of acceleration changes from UP to DOWN (i.e., acceleration on the y axis changes from positive to negative). Your solution should process raw accelerometer data and you should not use the built-in gesture API of the accelerometer class.

Hint: The accelerometer offers a dedicated event that can be managed by your program to handle programmability when the accelerometer values change in any of the 3 axes.

You can find the API of the Accelerometer class here and the serial port class here.

Task 2: Counting steps

For the second task, you are expected to implement an algorithm for counting steps. The accelerometer returns as measurement the acceleration on each axis in mG (1G = 1000 mG). Your algorithm should count a step as a consecutive up to down or down to up movement in the Y-axis. To reduce the sensitivity of the detection mechanism, you should record the movement only when the acceleration is more than 200 mG. For example, a movement that goes from UP to DOWN will count as one step. If the next measurement registers an UP movement, then this will count as a second step. For each step you should increment a global step counter variable, so that your micro:bit can keep track of the number of steps.

Task 3: Raw Data Logging

For this third task you are expected to develop functionality to improve the interaction with your step counter. Firstly, you are expected to use the CoDAL API to display the number of steps that the user has

20

Figure 9: Sample logging page on the micro:bit.

21

taken since the last boot of the system on the LED display. A user should be able to access this information by pressing button A on the micro:bit board. Secondly, we expect you to implement a logging functionality, which stores raw accelerometer data (Y-axis acceleration measurements when an UP or DOWN movement is detected). Specifically, in each movement you code should store in memory the current and the previous measured acceleration on the Y-axis. You code should store data only for the last 30 UP or DOWN movements. To realize this logging functionality, you can use you own data structure and an array or a doubly linked list to store data for the 30 most recent movements. If you already store data for the last 30 measurements, then your code should discard the oldest measurement, before adding a new one.

Additionally, your code should log this data into the micro:bit MYDATA.html file when pressing button B. The logging API of the CoDAL platform can help you in this functionality- you can find details about the logging system here.

Task 4: Improve step counting and displaying information

As you might have noticed so far, our simple step counter is far from perfect, and it is prone over records steps. For this last task, you must implement a better step detection algorithm. During a step, the accelerometer will record multiple accelerometer readings (the CPU is fast enough to fetch and process multiple accelerometer readings/sec) and a step will record acceleration changes in all three dimensions. As a result, your code should be able to associate many micro-movements and maintain some memory to avoid double counting steps.

One possible algorithm can be the following:

• Firstly, your code should analyse acceleration data on all three dimensions and detect direction changes (change of acceleration from positive to negative, or vice-versa). In addition, a step is expected to generate acceleration greater than 400 mG. When these two conditions are true, the measurement should be classed as a micro-movement.
• Secondly, in order to record a step, you should receive four accelerometer measurements that meet the micro-movement criteria.
• Once you detect a step, you should allow a cooldown period, until a next step is recorded. The cooldown period should vary depending on the type of steps. If no micro-movements are detected in the next 10 measurements, then you should reset the step counter. This would reflect a slow mild walk.

22

If though, you continue recording micro-movements, then your code should ignore the next 20 micro movement, as these micro-movement are part of the same step. This would reflect an intensive fast passed walk.

• Once the cooldown has elapsed, you should reset the step counter state and start measuring movement for the next step.

MARKING SCHEME

Marks will be awarded according to the marking scheme shown at the start of this document. Marks for the ‘Functionality’ section will be awarded based on individual merit, but the following table gives an indicative overview of the level of functionality expected for each grade band:

1. Working program that meets the criteria for a B, plus:

• • Meets the requirements of Task 4

2. Working program that meets the criteria for a C, plus:

• • Meets the requirements of Task 3

3. Working program that meets the criteria for a D, plus:

• • Meets the requirements of Task 2 D            Working program that:
  • Meets the requirements of Task 1

F             No working program demonstrated, or program does not meet any requirements listed above

The precision of step counting will not be assessed, so do not worry if you step counting is a bit off. Our focus will be to ensure that you implement the described functionalities.

Figure 10: Sample logging page on the micro:bit using xor-based encryption.

24